高級數(shù)據(jù)庫技術-第10章空間數(shù)據(jù)庫.ppt

2019/7/16,1,第10章 空間數(shù)據(jù)庫,10.1 空間數(shù)據(jù)庫概述,2019/7/16,2,10.1.1空間數(shù)據(jù)庫的意義,從本體論的角度，研究和開發(fā)空間數(shù)據(jù)庫的意義主要基于下述幾個方面。 1時間和空間是物質存在的基本方式 2空間數(shù)據(jù)是某些重要應用的基本形式 3復雜的非空間數(shù)據(jù)可以作為空間數(shù)據(jù)處理,2019/7/16,3,10.1.2空間數(shù)據(jù)基本特征,1數(shù)據(jù)量大 結構復雜 數(shù)據(jù)聯(lián)系多樣化 2查詢過程復雜 3空間對象間難以定義次序,2019/7/16,4,10.1.3空間數(shù)據(jù)庫作為常規(guī)數(shù)據(jù)庫擴充,由于空間數(shù)據(jù)庫系統(tǒng)理論和技術還處于發(fā)展過程當中，而實際應用的需求又非常迫切，同時常規(guī)數(shù)據(jù)庫（關系數(shù)據(jù)庫）仍然是當今主流數(shù)據(jù)庫，所以目前空間數(shù)據(jù)庫是作為常規(guī)、傳統(tǒng)數(shù)據(jù)庫的擴充出現(xiàn)。在這種情況下，空間數(shù)據(jù)庫主要包括下述一些方面的內容：,2019/7/16,5,空間數(shù)據(jù)模型 基于實際應用，引入各種必須的空間數(shù)據(jù)類型，并討相應的數(shù)據(jù)操作。 空間索引 由于空間對象之間難以合適的定義“序”，所以空間數(shù)據(jù)的索引就成為空間數(shù)據(jù)庫技術的一個重要課題，在這方面已經(jīng)取得了相當成熟的結果，并且應用到其他的領域。 空間數(shù)據(jù)庫管理系統(tǒng) 空間數(shù)據(jù)模型和當前主流數(shù)據(jù)模型關系數(shù)據(jù)模型具有較大的差異，需要研究如何在RDBMS基礎上有效擴充空間數(shù)據(jù)管理功能的問題。,2019/7/16,6,10.2 空間數(shù)據(jù)模型,10.2.1空間數(shù)據(jù)模型 空間數(shù)據(jù)模型與其它數(shù)據(jù)模型相比，一個突出的特點就是其模型的提出、引入與相應的實際應用密切相關。 空間數(shù)據(jù)庫的一個重要應用領域是GIS。人們通常就以GIS為應用背景，介紹其中的基本空間數(shù)據(jù)類型。我們這里的介紹主要以二維空間數(shù)據(jù)類型為主，但完全可以推廣到三維以上的情形。,2019/7/16,7,在GIS中，基本空間數(shù)據(jù)類型由下述三種空間對象組成： （1）點（Point） 例如城市。點只表示其空間位置，不表示其范圍（extent） （2）線（Line）例如河流、道路、管道、航線、等高線、等降雨線、通信或電力線路等。線不僅表示線上各點在空間的位置，而且還有長度，即表示其在空間的延伸范圍。 （3）區(qū)域（Region）例如森林、湖泊、行政區(qū)域等。區(qū)域不但有位置，而且有面積、周長等參數(shù)，以表示其覆蓋范圍。,2019/7/16,8,以上三種是最基本空間數(shù)據(jù)類型，以此為基礎，還可以導出下面兩種空間數(shù)據(jù)類型： （4）劃分（Partition）一個區(qū)域可以是按其自然、行政或其他特征，分成若干個區(qū)域。如果這些子區(qū)域互不相交，但其“并”覆蓋該區(qū)域，則此子區(qū)域的集合就稱為該區(qū)域的一個劃分。國家行政區(qū)域劃分圖，土地利用圖等都是劃分的例子。劃分可嵌套，例如國家分成省市，省市分成縣區(qū)、縣區(qū)分成鄉(xiāng)鎮(zhèn)等。,2019/7/16,9,（5）網(wǎng)絡（Network）網(wǎng)絡是由若干點和一些點與點之間的聯(lián)線組成。例如公路網(wǎng)、河網(wǎng)、電力網(wǎng)、電話網(wǎng)、交通線路圖等都是網(wǎng)絡的例子。,2019/7/16,10,10.2.2空間對象所處的環(huán)境,1.歐氏空間 設R表示實數(shù)域，V是R上向量的非空集合，如果在V上定義了滿足如下條件并稱之為內積的一個二元函數(shù)，則稱V為R的歐氏空間： 非負性 0，=0x=0， xV 對稱性 = 線性性 = +，R；x，y，zV 直線R，平面R2和空間R3通過適當?shù)亩x內積都是歐氏空間。,2019/7/16,11,2.在歐氏空間中討論空間對象間的關系 我們主要在歐氏空間的環(huán)境中定義所有空間對象相互間關系的，這些關系可以分為基于集合、拓撲、.方位和.度量的關系，我們在下面分別討論。,2019/7/16,12,10.2.3 空間對象之間關系,1.基于集合的關系 基于集合的空間對象關系主要有元素與集合的屬于及不屬于的關系，集合與集合的包含、相交、并等關系。在空間對象間的層次關系就適合用集合的關系理論來討論，例如城市包含公園，公園包含樹林等。,2019/7/16,13,2.基于拓撲的關系 基于拓撲的空間對象關系主要有鄰接（meet）、包含（within）和交疊（overlap），這三類拓撲關系也是空間數(shù)據(jù)查詢中最有可能出現(xiàn)的情況?？臻g數(shù)據(jù)庫中，基于拓撲的查詢需要解決這樣兩個問題： 查詢所有與給定對象具有某種拓撲關系R的空間對象。 對象A和B具有怎樣的拓撲關系。,2019/7/16,14,在平面上，兩個對象A和B之間的二元拓撲關系時基于以下對象成分的相交（insection）關系： A的內部A，A的邊界A，A的外部A-。 B的內部B，B的邊界B，B的外部B-。,2019/7/16,15,對象的這六個部分分別構成九種相交情況： AB， AB，A B- ； AB， A B，A B-； A- B ， A-B， A-B-。,2019/7/16,16,考慮到0，1取值情況0，1，可以確定有29=512種二元拓撲關系，這里，人們研究其中的八種彼此互斥關系： 相離（disjoint），鄰接（meet），交疊（overlap），相等（equal），包含（contain），在內部（inside），覆蓋（cover）和被覆蓋（covered by）。,2019/7/16,17,3.基于方位的關系 絕對方位 即在全球定位系統(tǒng)背景下定義的方位，例如東、西、南、北，東南、西南、東北等。 相對方位 即根據(jù)與給定目標的方向來定義的方位，例如左右、前后、上下等。 基于觀察者的方位 即按照專門指定的稱為觀察者參照對象來定義的方位。,2019/7/16,18,4.基于度量的關系 設有一個集合E，如果在E上定義了一個二元函數(shù)d（x，y），x，yE，滿足如下條件： （1）非負性 d（x，y）0 （2）對稱性 d（x，y）= d（y，x） （3）三角不等性 d（x，y）d（x，z）+ d（z，y） 則稱V是一個度量空間，d（x，y）稱為V上的度量函數(shù)。,2019/7/16,19,考察一個空間的“測度”，例如線段的長度，平面圖形的面積，空間立體的體積，以及一個空間對象相對于另一個空間對象的距離等都是基于度量的關系。,2019/7/16,20,10.2.4空間數(shù)據(jù)操作的謂詞描述,從理論上講，空間數(shù)據(jù)操作特別是空間數(shù)據(jù)查詢的基礎是空間對象之間的相互關系，從實際上看，由于空間數(shù)據(jù)類型取決于實際應用，空間數(shù)據(jù)操作主要也由現(xiàn)實中的應用所決定。下面主要介紹一些從空間對象相互關系角度考慮的相對比較基本的通用操作，而由應用的多樣性，與應用密切相關的操作不擬一一介紹?？臻g數(shù)據(jù)操作的描述可以有謂詞形式、集合形式和代數(shù)形式三種。,2019/7/16,21,1.基本符號 先定義空間數(shù)據(jù)操作中的一些記號。 SDT 空間數(shù)據(jù)類型 ZS 大小為零（zero size）空間數(shù)據(jù)類型，例如點 NZS 大小非零（non-zero size）的空間數(shù)據(jù)類型，例如線、區(qū)域等 ADT 原子（atomic）空間數(shù)據(jù)類型 例如點、線、區(qū)域 CDT 集合型（collection）空間數(shù)據(jù)類型，例如網(wǎng)絡、劃分等,2019/7/16,22, PT 點 LN 線 RG 區(qū)域 PTN 劃分 NTW 網(wǎng)絡,2019/7/16,23,2.基于拓撲的描述 兩個同類型空間數(shù)據(jù)是否相等（= 或 ） PTPT Bool LNLN Bool RGRG Bool 空間數(shù)據(jù)SDT是否在區(qū)域RG中（INSERT） SDT RG Bool,2019/7/16,24,兩個大小非零的空間數(shù)據(jù)是否相交（INTERSECTS） NZS NSZ Bool 兩個區(qū)域是否鄰接（ISNEIGHBOROF） RGRGBool,2019/7/16,25,3.基于集合運算的描述 （1）相交（Intersection） 兩條線相交為點的集合 LNLN PT 線與區(qū)域相交為線的集合 LNRGLN 區(qū)域與區(qū)域相交為區(qū)域的集合 RGRGRG,2019/7/16,26,（2）重疊（OVERLAP） PTNPTNFG （3）中心點（CENTER） NZSPT,2019/7/16,27,4.基于度量的描述 兩點間距離（DIST） PTPT NUM DIST 兩空間圖形間的最大、最小距離（MAXDIST，MINDIST） SDTSDTNUM MAXDIST或MINDIST,2019/7/16,28,多點的直徑（DIAMETER） PT NUM DIAMETER 線的長度（LENGTH） LN NUM LENGTH 區(qū)域的周長（PERIMETER）或面積（AREA） RG NUM PERIMETER 或AREA,2019/7/16,29,10.2.5空間關系的集合描述與判斷,在空間數(shù)據(jù)庫中，空間關系主要用于查詢。為了獲得可以接受的查詢效率，常常把空間對象用點、矩形和方盒等簡單，規(guī)則的圖形表示。因此，只需要討論這些規(guī)則幾何圖形的空間關系即可。這里，規(guī)則的幾何圖形可以看做空間中標準的“點集合”，因此，空間數(shù)據(jù)操作的集合描述就是這些標準集合間關系的描述。,2019/7/16,30,1.一維空間中兩個線段的關系 一維空間中兩個線段的7種可能的關系，分別用記號“=、%、/、|、”表示。圖10-4表示了這些關系，其中，（1）（5）是相交關系，（6）（7）是非相交關系。 設A、B線段的起點和終點分別為x1A，x2A，x1B，x2B，則（1）（5）的關系可以歸納為maxx1A，x1Bminx2B，x2B,2019/7/16,31,2019/7/16,32,2.二維空間中邊平行于坐標軸矩形間的關系 設A、B為這種矩形，其左下角坐標和右上角坐標分別為（x1A，y1A），（x2A，y2A）和（x1B，y1 B），（x2 B，y2 B）?？梢缘玫?，如果A和B在x軸和y軸上的投影分別相交，則A、B相交。因此，A，B相交的條件可以表示為 max x1A，x1B min x2A，x2B 和max y1A，y1B min y2A，y2B ,2019/7/16,33,10.2.6空間關系的代數(shù)描述與運算,空間代數(shù)運算的特點在于選擇條件或連接條件中出現(xiàn)空間謂詞。投影、集合運算不涉及空間謂詞，與關系代數(shù)沒有本質區(qū)別。下面討論空間選擇和空間連接。,2019/7/16,34,1.空間選擇 例10-1 寫出下列空間選擇表達式。 選擇廣東省所有城市： F（城市）其中，F(xiàn)=CENTER（城市地圖）INSIDE 廣東; 城市是關系名，其中有屬性“城市名”、“人口”、“城市地圖”。城市地圖表示市區(qū)及其周邊地區(qū)，“廣東”是一個區(qū)域名稱。顯然，如果城市中心點在廣東省區(qū)域內，則該城市一定屬于廣東省,2019/7/16,35,選擇廣東省的所有河流： F（河流）其中 F=ROUTE（河流）INSIDE廣東; “河流”是關系名，其中有屬性“河流流域圖”。ROUTE是空間數(shù)據(jù)庫中的一個函數(shù)，計算河流、道路等的中心線。 選擇距離廣州小于等于100000米，人口大于等于50萬的所有城市： F（城市，廣東區(qū)域圖）其中F=DIST（城市名，廣州）500000; 城市是個關系，“廣州”是城市名，F(xiàn)中的第一個謂詞是空間謂詞，要用到廣東省地圖。,2019/7/16,36,2.空間連接 例10-2 對每條河流找出沿河10000米的所有城市 設“河流”、“城市”是兩個關系。在關系“河流”中，有屬性“河流流域圖”。如果城市中心距離河流小于等于10000米，則該城市和河流匹配。可以用空間連接表示如下： 河流名，城市名（河流 F城市） 其中，F(xiàn)=Mindist（城市名，ROUTE（河流流域圖）10000,2019/7/16,37,10.2.7空間數(shù)據(jù)查詢語言,一般在SQL語言基礎上擴充空間數(shù)據(jù)類型及其操作和相應的保留字。由于這些擴充與應用有關，目前還未形成標準，以下列舉一些例子予以說明。,2019/7/16,38,例 10-3 選擇廣東省所有城市及其人口： select 城市名，人口 from 城市 where center（城市地圖）inside廣東??；,2019/7/16,39,選擇流經(jīng)廣東省所有河流的河流名及其在廣東省境內的長度： select 河流名，length（intersection（route（河流流域圖），廣東） from 河流 where route（河流流域圖）intersects廣東；,2019/7/16,40,選擇距離廣州小于等于100000米，人口大于等于50萬的所有城市： select 城市名，人口 from 城市，廣東區(qū)域圖 where dist（城市名，廣州）500000；,2019/7/16,41,例10-4 將例10-2表示的查詢用SQL風格表示出來 select 河流名，城市名 from 河流，城市 where mindist（城市名，ROUTE（河流流域圖）=10000,2019/7/16,42,10.3 空間索引,空間數(shù)據(jù)庫查詢的開銷一般比關系數(shù)據(jù)庫大，特別是空間謂詞求值的開銷遠比數(shù)值或字符串的比較要大。若采用順序掃描方法進行查詢，則效率就會很低，因此采取空間索引十分必要的。,2019/7/16,43,10.3.1空間索引概述,1.空間索引的思路 為了減少開銷，通常是采用近似規(guī)則圖形例如邊平行于坐標軸的最小矩形來代替不規(guī)則土星進行查詢。這種矩形就稱為不規(guī)則區(qū)域的最小限定矩形（minimum bounding rectangle ，MBR）。設MBR左下角坐標為（x1，y1），右上角為（x2，y2），則x1，y1就分別為空間對象的最小橫坐標和縱坐標，x2，y2分別為空間對象的最大橫坐標和縱坐標。不但區(qū)域可以用MBR近似表示，線也可以用MBR近似表示；進一步，不但單個空間對象可以用MBR近似表示，有時MBR還可以包含多個空間對象。最小限定矩形如下圖所示。,2019/7/16,44,2019/7/16,45,如果一個MBR還含有另外的MBR，則稱其為目錄MBR，否則就稱為對象MBR。 如果兩個空間對象相交，則相應的MBR也相交；如果兩個MBR不相交，則對應的兩個空間對象也不相交。這樣，用MBR代替空間對象檢查相交情況，就可以排除一批不相交的對象。,2019/7/16,46,當然，兩個MBR相交，并不能得出對應的空間對象一定相交，此時還需要用精確方法對MBR相交的空間對象逐個進行檢驗，找出真正相交的情形。先用高效率的近似方法進行粗選，再用精確方法 進行精選，這是空間數(shù)據(jù)庫中常用的搜索方式。,2019/7/16,47,2.空間索引的特點,（1）索引對象的無序性 （2）索引對象的不規(guī)則性 （3）索引對象的交叉性,2019/7/16,48,10.3.2空間對象的近似表示,1.點 點不但是基本的空間數(shù)據(jù)類型之一，而且多屬性的檢索也相當于多維空間點的搜索。有些規(guī)則圖形也可以用高維空間的點表示。例如一維空間的線段a,b可以用二維空間的點（a，b）表示。二維空間的邊平行于坐標軸的矩形（x1，y1），（x2，y2）可以用四維空間的點（x1，y1，x2，y2）表示，式中（x1，y1），（x2，y2）分別為矩形的左下角和右上角坐標。,2019/7/16,49,2.矩形或方盒 矩形和方盒不但是近似表示不規(guī)則空間對象的簡單、有效手段，也是劃分子空間的首選圖形。,2019/7/16,50,3.柵格（grid） 用柵格表示空間對象，類似于用點陣、像素陣列表示二維圖像，原則上可以推廣到高維空間，但主要用于二維空間,2019/7/16,51,2019/7/16,52,2019/7/16,53,每個區(qū)域都可以近似表示為二進制串的集合。這種二進制串的集合稱為該區(qū)域的Z元素（Z-element）。要檢查兩個區(qū)域是否相交或包含，可以按序比較兩個區(qū)域的Z元素。比較時，如果一個二進制串是另一個二進制串的前綴，則后者所代表的區(qū)域必然包含于前者所代表的區(qū)域中，例如100101一定包含在1001中。,2019/7/16,54,用Z次序的柵格表示區(qū)域，可以把本是二維的空間對象，用一維的有序二進制串序列表示。因此，空間對象所占的區(qū)域，可以用二進制串作為索引鍵，組成一個B樹。下面是A，B區(qū)域的Z元素，經(jīng)掃描比較，可以找出它們的重疊部分。,2019/7/16,55,重疊部分：（A1,B1）, （A1,B2）（A1,B3），（B1,A2），（B1,A3），。 在上面的重疊欄中，二元組的第一項覆蓋第二項。,2019/7/16,56,10.3.3 基于大小非零空間對象查詢的R樹,空間索引按照其操作對象的不同可以分為兩類。 以空間點為查詢對象的索引 例如kd樹和G-樹技術（kd樹和G樹可以參考有關的空間數(shù)據(jù)庫書籍）。 以非點的空間圖形為查詢對象的索引，例如R-樹等技術。 下面，我們主要討論基于測度非零的空間圖形的R-樹技術。,2019/7/16,57,R樹主要以矩形（Rectangle）為檢索對象，這就是R樹命名的 由來。R樹是由Guttmann于1984年提出。與B+樹相似，G樹是一種平衡多分樹；與B+樹不同，R樹不是通過逐級比較索引鍵的值來搜索要找的對象。而是通過逐級縮小搜索的空間范圍來定位要找的對象。搜索的空間范圍在二維空間中就用MRB表示。,2019/7/16,58,如果一個MRB中含有其他的MRB，則稱其為目錄MRB，否則就稱為對象MRB。在R樹中，每個索引項都是一個二元組（r，p），其中r表示MBR，p表示相應指針。對于葉結點，p指向r所近似表示的空間對象；在非葉結點，p指向含有r的子節(jié)點。,2019/7/16,59,一個結點最多可有M個索引項，至少有m個索引項。M一般在2與M/2之間選擇。由于R樹在分裂時涉及到區(qū)域的優(yōu)化與調整，開銷較大，為了減少分裂概率，m宜選擇較低數(shù)值。有實驗結果，m在0.4M左右可以獲得較好的性能。,2019/7/16,60,R樹具有如下基本性質 根結點至少有兩個索引項，除非個結點是R樹的唯一結點； 每個非葉結點有m到M個索引項； 在上述約束條件下，保持樹的平衡。 下圖（a）表示了外包矩形的取法，（b）是其對應的R樹的取法。,2019/7/16,61,2019/7/16,62,2019/7/16,63,2.R樹的查詢 設給定矩形Rq=（x1，y1），（x2，y2），其中（x1，y1），（x2，y2）分別為Rq的左下角和右上角坐標，要查詢其中所包含的空間對象。在查詢時，首先從R樹的根結點開始。,2019/7/16,64,如果根結點中的索引項是對象，由于這些索引項是無序的，需要逐個檢查每個對象MBR是否包含在Rq中，如果包含在Rq中，則此對象就是選中的對象之一。設對象MBR為R0=（x3，y3），（x4，y4），式中（x3，y3），（x4，y4），分別為R0的左下角和右上角坐標。R0包含在Rq中的條件為 x3x1 and y3y1 and x4x2 and y4y2,2019/7/16,65,如果根結點中的索引項是目錄MBR，則逐個檢查個目錄MBR是否與Rq相交。如果相交，則此目錄MBR中的對象MBR就有可能包含在Rq中，需要沿此目錄MBR繼續(xù)搜索；如果目錄MBR與Rq不相交，則其中的對象MBR就不可能包含在Rq中，就不必沿此目錄繼續(xù)向下搜索，相交的條件參見前述小節(jié)。當搜索到葉結點時，則與前面一樣，逐個檢查其中對象MBR是否包含在中。如果目錄MBR之間有重疊，雖然重疊區(qū)中的對象只屬于一個目錄MBR，但是判定它屬于哪一個目錄MBR，仍然需要多路搜索。,2019/7/16,66,3.R樹的插入 插入是R樹中開銷最大的操作，對其性能影響很大，因而研究較多。設（R1，p）是待插入的對象MBR及其指向對象的指針。與R+樹不同，插入哪個葉結點以及在葉結點的次序不是唯一的。R1插入哪個葉結點決定于它屬于哪個目錄MBR，至于它在葉結點中的次序是無關緊要的，因為空間對象本來是無序的。R1可能與多個目錄MBR相交或相鄰，這些目錄MBR只要其中的對象MBR不超過最大值，經(jīng)過必要的擴大后，都可被選來覆蓋R1。因此，R1的插入方式可能有多種選擇，