1、2022-4-71空間數(shù)據(jù)模型空間數(shù)據(jù)模型空間索引空間索引空間數(shù)據(jù)庫管理系統(tǒng)空間數(shù)據(jù)庫管理系統(tǒng)1 空間數(shù)據(jù)庫中涉及到的知識空間數(shù)據(jù)庫中涉及到的知識2022-4-722 空間數(shù)據(jù)模型空間數(shù)據(jù)模型12.1空間數(shù)據(jù)模型空間數(shù)據(jù)模型 特點:模型的提出、引入與相應的實際應用密切相關。 空間數(shù)據(jù)庫的一個重要應用領域是GIS。通常就以GIS為應用背景，介紹其中的基本空間數(shù)據(jù)類型。2022-4-73在GIS中，基本空間數(shù)據(jù)類型由下述三種空間對象組成：（1）點點（Point） 例如城市。點只表示其空間位置，不表示其范圍（extent）（2）線線（Line）例如河流、道路、管道、航線、等高線、等降雨線、通信或電力

2、線路等。線不僅表示線上各點在空間的位置，而且還有長度，即表示其在空間的延伸范圍。（3）區(qū)域區(qū)域（Region）例如森林、湖泊、行政區(qū)域等。區(qū)域不但有位置，而且有面積、周長等參數(shù)，以表示其覆蓋范圍。2022-4-74以上三種是最基本空間數(shù)據(jù)類型，以此為基礎，還可以導出下面兩種空間數(shù)據(jù)類型：（4）劃分劃分（Partition）一個區(qū)域可以是按其自然、行政或其他特征，分成若干個區(qū)域。如果這些子區(qū)域互不相交，但其“并”覆蓋該區(qū)域，則此子區(qū)域的集合就稱為該區(qū)域的一個劃分。國家行政區(qū)域劃分圖，土地利用圖等都是劃分的例子。劃分可嵌套，例如國家分成省市，省市分成縣區(qū)、縣區(qū)分成鄉(xiāng)鎮(zhèn)等。2022-4-75（5）網(wǎng)

3、絡網(wǎng)絡（Network）網(wǎng)絡是由若干點和一些點與點之間的聯(lián)線組成。例如公路網(wǎng)、河網(wǎng)、電力網(wǎng)、電話網(wǎng)、交通線路圖等都是網(wǎng)絡的例子。2022-4-762.2空間對象所處的環(huán)境空間對象所處的環(huán)境1.歐氏空間歐氏空間 設R表示實數(shù)域，V是R上向量的非空集合，如果在V上定義了滿足如下條件并稱之為內(nèi)積的一個二元函數(shù)，則稱V為R的歐氏空間：非負性 0，=0 x=0， xV對稱性 = 線性性 = +，R；x，y，zV直線R，平面R2和空間R3通過適當?shù)亩x內(nèi)積都是歐氏空間。2022-4-772. 空間對象間的關系空間對象間的關系 集合 拓撲 方位 度量2022-4-782.3 空間對象之間關系空間對象之間關系

4、1.基于集合的關系基于集合的關系 基于集合的空間對象關系主要有元素與集合的屬于及不屬于的關系，集合與集合的包含、相交、并等關系。在空間對象間的層次關系就適合用集合的關系理論來討論，例如城市包含公園，公園包含樹林等。2022-4-792.基于拓撲的關系基于拓撲的關系 基于拓撲的空間對象關系主要有鄰接（meet）、包含（within）和交疊（overlap），這三類拓撲關系也是空間數(shù)據(jù)查詢中最有可能出現(xiàn)的情況。空間數(shù)據(jù)庫中，基于拓撲的查詢需要解決這樣兩個問題： 查詢所有與給定對象具有某種拓撲關系R的空間對象。 對象A和B具有怎樣的拓撲關系。2022-4-710在平面上，兩個對象A和B之間的二元拓撲

5、關系時基于以下對象成分的相交（insection）關系：A的內(nèi)部A?，A的邊界A，A的外部A-。B的內(nèi)部B?，B的邊界B，B的外部B-。2022-4-711對象的這六個部分分別構成九種相交情況：A?B，A?B，A? B- ； AB?，A B，A B-；A- B? ， A-B， A-B-。2022-4-712考慮到0，1取值情況0，1，可以確定有29=512種二元拓撲關系，這里，人們研究其中的八種彼此互斥關系：相離（disjoint），鄰接（meet），交疊（overlap），相等（equal），包含（contain），在內(nèi)部（inside），覆蓋（cover）和被覆蓋（covered by）。

6、2022-4-7133.基于方位的關系基于方位的關系 絕對方位 即在全球定位系統(tǒng)背景下定義的方位，例如東、西、南、北，東南、西南、東北等。 相對方位 即根據(jù)與給定目標的方向來定義的方位，例如左右、前后、上下等。 基于觀察者的方位 即按照專門指定的稱為觀察者參照對象來定義的方位。2022-4-7144.基于度量的關系基于度量的關系設有一個集合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）稱為

7、V上的度量函數(shù)。2022-4-715考察一個空間的“測度”，例如線段的長度，平面圖形的面積，空間立體的體積，以及一個空間對象相對于另一個空間對象的距離等都是基于度量的關系。2022-4-7162.4空間數(shù)據(jù)操作的謂詞描述空間數(shù)據(jù)操作的謂詞描述 從理論上講，空間數(shù)據(jù)操作特別是空間數(shù)據(jù)查詢的基礎是空間對象之間的相互關系，從實際上看，由于空間數(shù)據(jù)類型取決于實際應用，空間數(shù)據(jù)操作主要也由現(xiàn)實中的應用所決定。 空間數(shù)據(jù)操作的描述可以有謂詞形式、集合形式和代數(shù)形式三種。 2022-4-7171.基本符號基本符號先定義空間數(shù)據(jù)操作中的一些記號。 SDT 空間數(shù)據(jù)類型 ZS 大小為零（zero size）空間

8、數(shù)據(jù)類型，例如點 NZS 大小非零（non-zero size）的空間數(shù)據(jù)類型，例如線、區(qū)域等 ADT 原子（atomic）空間數(shù)據(jù)類型 例如點、線、區(qū)域 CDT 集合型（collection）空間數(shù)據(jù)類型，例如網(wǎng)絡、劃分等2022-4-718 PT 點 LN 線 RG 區(qū)域 PTN 劃分 NTW 網(wǎng)絡2022-4-7192.基于拓撲的描述基于拓撲的描述兩個同類型空間數(shù)據(jù)是否相等（= 或 ）PTPT BoolLNLN BoolRGRG Bool空間數(shù)據(jù)SDT是否在區(qū)域RG中（INSERT）SDT RG Bool2022-4-720兩個大小非零的空間數(shù)據(jù)是否相交（INTERSECTS）NZS N

9、SZ Bool兩個區(qū)域是否鄰接（ISNEIGHBOROF）RGRGBool2022-4-7213.基于集合運算的描述基于集合運算的描述（1）相交（Intersection）兩條線相交為點的集合LNLNPT線與區(qū)域相交為線的集合LNRGLN區(qū)域與區(qū)域相交為區(qū)域的集合RGRGRG2022-4-722（2）重疊（OVERLAP）PTNPTNFG（3）中心點（CENTER）NZSPT2022-4-7234.基于度量的描述基于度量的描述兩點間距離（DIST）PTPT NUM DIST兩空間圖形間的最大、最小距離（MAXDIST，MINDIST）SDTSDTNUM MAXDIST或MINDIST2022-

10、4-724多點的直徑（DIAMETER）PT NUMDIAMETER線的長度（LENGTH）LN NUM LENGTH區(qū)域的周長（PERIMETER）或面積（AREA）RG NUM PERIMETER 或AREA2022-4-7252.5空間關系的集合描述與判斷空間關系的集合描述與判斷 在空間數(shù)據(jù)庫中，空間關系主要用于查詢。為了獲得可以接受的查詢效率，常常把空間對象用點、矩形和方盒等簡單，規(guī)則的圖形表示。 規(guī)則的幾何圖形可以看做空間中標準的“點集合”，因此，空間數(shù)據(jù)操作的集合描述就是這些標準集合間關系的描述。 2022-4-7261.一維空間中兩個線段的關系一維空間中兩個線段的關系一維空間中兩

11、個線段的7種可能的關系，分別用記號“=、%、/、|、”表示。圖10-4表示了這些關系，其中，（1）（5）是相交關系，（6）（7）是非相交關系。設A、B線段的起點和終點分別為x1A，x2A，x1B，x2B，則（1）（5）的關系可以歸納為maxx1A，x1Bminx2B，x2B2022-4-7272022-4-7282.二維空間中邊平行于坐標軸矩形間的關系二維空間中邊平行于坐標軸矩形間的關系設A、B為這種矩形，其左下角坐標和右上角坐標分別為（x1A，y1A），（x2A，y2A）和（x1B，y1B），（x2B，y2B）。可以得到，如果A和B在x軸和y軸上的投影分別相交，則A、B相交。因此，A，B相交

12、的條件可以表示為max x1A，x1B min x2A，x2B 和max y1A，y1B min y2A，y2B 2022-4-7292.6空間關系的代數(shù)描述與運算空間關系的代數(shù)描述與運算空間代數(shù)運算的特點在于選擇條件或連接條件中出現(xiàn)空間謂詞。投影、集合運算不涉及空間謂詞，與關系代數(shù)沒有本質區(qū)別。2022-4-7301.空間選擇空間選擇例例1 寫出下列空間選擇表達式。選擇廣東省所有城市：F（城市）其中，F(xiàn)=CENTER（城市地圖）INSIDE 廣東;城市是關系名，其中有屬性“城市名”、“人口”、“城市地圖”。城市地圖表示市區(qū)及其周邊地區(qū)，“廣東”是一個區(qū)域名稱。顯然，如果城市中心點在廣東省區(qū)域

13、內(nèi)，則該城市一定屬于廣東省 2022-4-731選擇廣東省的所有河流：F（河流）其中 F=ROUTE（河流）INSIDE廣東;“河流”是關系名，其中有屬性“河流流域圖”。ROUTE是空間數(shù)據(jù)庫中的一個函數(shù)，計算河流、道路等的中心線。選擇距離廣州小于等于100000米，人口大于等于50萬的所有城市：F（城市，廣東區(qū)域圖）其中F=DIST（城市名，廣州）500000;城市是個關系，“廣州”是城市名，F(xiàn)中的第一個謂詞是空間謂詞，要用到廣東省地圖。2022-4-7322.空間連接空間連接例例2 對每條河流找出沿河10000米的所有城市設“河流”、“城市”是兩個關系。在關系“河流”中，有屬性“河流流域圖

14、”。如果城市中心距離河流小于等于10000米，則該城市和河流匹配。可以用空間連接表示如下：河流名，城市名（河流 F城市）其中，F(xiàn)=Mindist（城市名，ROUTE（河流流域圖）100002022-4-7332.7空間數(shù)據(jù)查詢語言空間數(shù)據(jù)查詢語言一般在SQL語言基礎上擴充空間數(shù)據(jù)類型及其操作和相應的保留字。2022-4-734例例 3選擇廣東省所有城市及其人口：select 城市名，人口from 城市where center（城市地圖）inside廣東省；2022-4-735選擇流經(jīng)廣東省所有河流的河流名及其在廣東省境內(nèi)的長度：select 河流名，length（intersection（ro

15、ute（河流流域圖），廣東）from 河流where route（河流流域圖）intersects廣東；2022-4-736選擇距離廣州小于等于100000米，人口大于等于50萬的所有城市：select 城市名，人口from 城市，廣東區(qū)域圖where dist（城市名，廣州）500000；2022-4-737例例4 將例2表示的查詢用SQL風格表示出來select 河流名，城市名from 河流，城市where mindist（城市名，ROUTE（河流流域圖）=100002022-4-7383 空間索引空間索引空間數(shù)據(jù)庫查詢的開銷一般比關系數(shù)據(jù)庫大，特別是空間謂詞求值的開銷遠比數(shù)值或字符串的比

16、較要大。若采用順序掃描方法進行查詢，則效率就會很低，因此采取空間索引十分必要的。2022-4-7393.1空間索引概述空間索引概述1.空間索引的思路空間索引的思路為了減少開銷，通常是采用近似規(guī)則圖形例如邊平行于坐標軸的最小矩形來代替不規(guī)則土星進行查詢。這種矩形就稱為不規(guī)則區(qū)域的最小限定矩形（minimum bounding rectangle ，MBR）。設MBR左下角坐標為（x1，y1），右上角為（x2，y2），則x1，y1就分別為空間對象的最小橫坐標和縱坐標，x2，y2分別為空間對象的最大橫坐標和縱坐標。不但區(qū)域可以用MBR近似表示，線也可以用MBR近似表示；進一步，不但單個空間對象可以用

17、MBR近似表示，有時MBR還可以包含多個空間對象。最小限定矩形如下圖所示。2022-4-7402022-4-741如果一個MBR還含有另外的MBR，則稱其為目錄MBR，否則就稱為對象MBR。如果兩個空間對象相交，則相應的MBR也相交；如果兩個MBR不相交，則對應的兩個空間對象也不相交。這樣，用MBR代替空間對象檢查相交情況，就可以排除一批不相交的對象。 2022-4-742當然，兩個MBR相交，并不能得出對應的空間對象一定相交，此時還需要用精確方法對MBR相交的空間對象逐個進行檢驗，找出真正相交的情形。先用高效率的近似方法進行粗選，再用精確方法 進行精選，這是空間數(shù)據(jù)庫中常用的搜索方式。202

18、2-4-7432.空間索引的特點空間索引的特點（1）索引對象的無序性）索引對象的無序性（2）索引對象的不規(guī)則性）索引對象的不規(guī)則性（3）索引對象的交叉性）索引對象的交叉性2022-4-7443.2空間對象的近似表示空間對象的近似表示1.點點點不但是基本的空間數(shù)據(jù)類型之一，而且多屬性的檢索也相當于多維空間點的搜索。有些規(guī)則圖形也可以用高維空間的點表示。例如一維空間的線段a,b可以用二維空間的點（a，b）表示。二維空間的邊平行于坐標軸的矩形（x1，y1），（x2，y2）可以用四維空間的點（x1，y1，x2，y2）表示，式中（x1，y1），（x2，y2）分別為矩形的左下角和右上角坐標。2022-4-7452.矩形或方盒矩形或方盒矩形和方盒不但是近似表示不規(guī)則空間對象的簡單、有效手段，也是劃分子空間的首選圖形。2022-4-7463.柵格（柵格（grid）用柵格表示空間對象，類似于用點陣、像素陣列表示二維圖像，原則上可以推廣到高維空間，但主要用于二維空間2022-4-7472022-4-7482022-4-749每個區(qū)域都可以近似表示為二進制串的集合。這種二進制串的集合稱為該區(qū)域的Z元素（Z-eleme