空間數(shù)據(jù)庫復習題

1、Chap ter 1: Introduction to Sp atial Databasesspatial queries）和非空間1舉例說明什么是空間數(shù)據(jù)、非空間數(shù)據(jù)？如何理解空間查詢（查詢的區(qū)別（Non-spatial queries）？答：河流的泛洪區(qū)，衛(wèi)星影像數(shù)據(jù)、氣象氣候數(shù)據(jù)等都可以是空間數(shù)據(jù)書店名稱 店員人數(shù)，去年的銷售量，電話號碼等是非空間數(shù)據(jù)空間查詢是對空間數(shù)據(jù)的查詢或命令2、什么是GIS，什么是SDBMS ?請闡述二者的區(qū)別和聯(lián)系。答：1 GIS是一個利用空間分析功能進行可視化和空間數(shù)據(jù)分析的軟件。它的主要功能有:搜索、定位分析、地形分析、流分析、分布、空間分析/統(tǒng)計、度量G

2、IS可以利用SDBMS來存儲、搜索、查詢、分享大量的空間數(shù)據(jù)集2、SDBMS是一個軟件模塊。它可以 、利用一個底層的數(shù)據(jù)庫管理系統(tǒng)ADT ）以及一種能夠調(diào)用 、支持多種空間數(shù)據(jù)模型、相應的空間抽象數(shù)據(jù)類型（這些ADT的查詢語言 、支持空間索引、高效的空間操作算法以及用于查詢優(yōu)化的特定領域規(guī)則3、區(qū)別與聯(lián)系：、利用GIS可以對某些對象和圖層進行操作，而利用 SDBMS則可以對更多的對象集和圖層進行更加簡單的操作、SDBMS可以在GIS不能使用的某些領域進行使用，例如基因組學、天文學、多媒體信息系統(tǒng)等、GIS可以作為SDBMS的前端，利用一個高效的 SDBMS可以大大提高GIS的效率和生產(chǎn)率。3、

3、從GIS這一縮寫的三種含義來理解GIS的發(fā)展歷程。答：地理信息系統(tǒng)：為專業(yè)人員提供的軟件地理信息科學：為地理信息系統(tǒng)和服務提供使用和發(fā)展的定義、框架和理論PC機上的地理和空間服務地理信息服務：為普通用戶提供的網(wǎng)點和服務中心，例如7、SDBMS的三層體系結(jié)構(gòu)（Three Layer Architecture ）是什么？借此深入理解 SDBMS的4、用傳統(tǒng)數(shù)據(jù)庫系統(tǒng)管理空間數(shù)據(jù)，存在什么不足之處?答：1）無法用遞歸和嵌套的方式來描述復雜關系的層次和網(wǎng)狀結(jié)構(gòu)，模擬和操作復雜地理對象的能力較弱;2）用關系模型描述本身具有復雜結(jié)構(gòu)和涵義的地理對象時，需對地理實體進行不自然的分解，導致存儲模式、查詢途徑及

4、操作等方面均顯得語義不甚合理;3）由于概念模式和存儲模式的相互獨立性，及實現(xiàn)關系之間的聯(lián)系需要執(zhí)行系統(tǒng)開銷較大的聯(lián)接操作，運行效率不夠高4）空間數(shù)據(jù)通常是變長的，而一般 RDBMS只允許記錄的長度設定為固定長度，此外，通用DBMS難于存儲和維護空間數(shù)據(jù)的拓撲關系。5） 一般RDBMS都難以實現(xiàn)對空間數(shù)據(jù)的關聯(lián)、連通、包含、疊加等基本操作。6） 一般DBMS不能支持GIS需要的一些復雜圖形功能。7） 般RDBMS難以支持復雜的地理信息，因為單個地理實體的表達需要多個文件、多條記錄，包括大地網(wǎng)、特征坐標、拓撲關系、屬性數(shù)據(jù)和非空間專題屬性等方面信息。8） GIS管理的是具有高度內(nèi)部聯(lián)系的數(shù)據(jù)，為了

5、保證地理數(shù)據(jù)庫的完整性，需要復雜的安全維護系統(tǒng)，而這些完整性約束條件必須與空間數(shù)據(jù)一起存儲,由地理數(shù)據(jù)庫來維護系統(tǒng)數(shù)據(jù)的完整性。否則，一條記錄的改變會導致錯誤、相互矛盾的數(shù)據(jù)存在，而一般RDBMS難以實現(xiàn)這一功能。5、What is a SDBMS ？答：SDBMS是一個軟件模塊。它可以、利用一個底層的數(shù)據(jù)庫管理系統(tǒng)、支持多種空間數(shù)據(jù)模型、相應的空間抽象數(shù)據(jù)類型（ADT ）以及一種能夠調(diào)用這些ADT的查詢語言、支持空間索引、高效的空間操作算法以及用于查詢優(yōu)化的特定領域規(guī)則6、什么是后關系數(shù)據(jù)庫模型？后關系數(shù)據(jù)庫模型有哪些?答：后關系數(shù)據(jù)庫模型支持用戶定義抽象數(shù)據(jù)類型，空間數(shù)據(jù)的類型可以添加。包

6、括面向?qū)ο蟮臄?shù)據(jù)庫模式 OOBDMS和面向關系ORDBMS的數(shù)據(jù)庫模式。作用。答：空間應用一空間數(shù)據(jù)庫一 DBMS教材P11的圖8、空間數(shù)據(jù)庫主要涉及哪些內(nèi)容?答：數(shù)據(jù)模型、查詢語句、查詢處理與優(yōu)化、文件組織和索引、數(shù)據(jù)挖掘9、舉例說明單遍掃描查詢和多遍掃描查詢的概念。答：單邊掃描查詢中，被查詢的表（關系）中的一條記錄（元組）最多只被訪問一次；例如“列出武大周圍5km內(nèi)的書店的名字”。多遍掃描查詢是被查詢的表（關系）中的一條記錄（元組）至少被訪問一次，例如“找出其代表的選取范圍大于 200公頃并且在這區(qū)擁有公司的女議員的名字”10、過濾一精煉策略的作用？兩個步驟的內(nèi)容是什么?提示：ppt :E

7、fficient algorithms to answer spatial queriesCommon Strategy - filter and refine （過濾一精煉 ）Filter Ste p:Query Regio n overla ps with MBRs ofB,C and D過濾：查詢區(qū)域與 B、C、D的最小外接矩形有重疊部分，保留 B、C、D，其他的舍棄Refine Step: Query Regi on overla ps with B and C精煉：查詢區(qū)域與 B、C有重疊，舍棄D11、平面掃描（plane sweep）技術主要解決什么問題？其主要步驟?答：主要解決的

8、是如何在過濾階段中盡可能多的淘汰不符合條件的對,從而減少幾何計算的計算代價。Step 1:從左至右移動一條掃描線（例如，垂直于x軸的線），停在RU S的第一個元素處。這就是具有最小T. XI值的矩形T,例子為是矩形 R4。Step2:搜索S中已排序的矩形，直到抵達第一個矩形Sf，這里有Sf. xl T . xu。顯然，對于所有1 wjf，關系T. xl, T . xu n Sj. xl, Sj. xu存在（非空），在本例中Sf就是S1。注意f是以圖1-9c的數(shù)組索引為序，即 S仁S2、S2= S1、S3=S3。這樣S2就是一個可能與R4交疊的候選矩形。Ste P 3:如果對任意 I j f,關

9、系T. yl, T. yu n Sj. yl, Sj. yu存在，則 Sj 與 T 相交。因此，這一步就確定了R4與S2的確是交疊的，并且 R4，S2是連接結(jié)果的一部分。記錄所有這樣的信息，然后將矩形T (R4)從集合RU S中去掉，它不再需要參與結(jié)果集中的其他相交對。SteP 4:繼續(xù)移動掃描線來穿過集合RUS,直至碰到下一個矩形，在本例中是S2。這時進行步驟2和3。SteP 5:當 RU S=?時，處理結(jié)束;12、從程序員的觀點和 DBMS設計者的觀點看，影響系統(tǒng)效率的因素有何不同。答：在程序員看來，計算機主要包括兩個部分:CPU和無限量的內(nèi)存在DBMS設計者看來，計算機主要包括三個部分：

10、CPU、有限的內(nèi)存、無限的硬盤空間。訪問硬盤的速度要遠遠小于訪問內(nèi)存的速度,因此前者關注減少算法的計算時間，后者強調(diào)的是將計算時間和I/O時間的總和減少到最小。13、查詢優(yōu)化和數(shù)據(jù)挖掘的概念。答：查詢優(yōu)化：基于數(shù)據(jù)集的特點對查詢中的操作進行排序，為每一步操作選擇有效策略數(shù)據(jù)挖掘：即進行系統(tǒng)的搜索，找出隱藏在電子信息中潛在的有用信息。Cha pter 2: Sp atial Conce pts and Data Models1、什么是數(shù)據(jù)模型？舉例說明數(shù)據(jù)模型的重要性。答、數(shù)據(jù)模型是數(shù)據(jù)集的特定結(jié)構(gòu)和模式，是對數(shù)據(jù)的文件描述，有利于某些性質(zhì)的前期分 析。作用：、屬性的前期分析；、重利用多媒體應用

11、中的共享數(shù)據(jù)；、組織中交換數(shù)據(jù) 、將數(shù)據(jù)傳遞給新軟件或環(huán)境ADT數(shù)據(jù)要被重新修改。例子：千禧年危機正確的使用數(shù)據(jù)模式可以顯著的降低成本，如果軟件中的時間和數(shù)據(jù)被 定義成抽象數(shù)據(jù)模型，只有一小部分的軟件會執(zhí)行數(shù)據(jù),2、掌握兩種常用的空間信息模型：要素模型和場模型，矢量、柵格數(shù)據(jù)結(jié)構(gòu)。答：場模型：、空間分割框架、場函數(shù) 、場操作：并、復合森林模型中分段函數(shù)表示，區(qū)域中每個點被映射成主要樹種對應的值要素模型：、對象：把空間信息抽象成明確的，可識別的事物或?qū)嶓w；、對象具有屬性和操作 森林模型中多邊形表示（林分），每個對象有唯一的標示符、主要樹種和一 塊區(qū)域。矢量數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)：柵格結(jié)構(gòu)用密集正方

12、形（或三角形，多邊形）將地理區(qū)域劃分為網(wǎng)格 陣列。位置由行，列號定義，屬性為柵格單元的值。點：由單個柵格表達。線：由沿線走向3、有相同屬性取值的一組相鄰柵格表達。面：由沿線走向有相同屬性取值的一片柵格表達?；趫瞿Ｐ偷牟僮饔心男?，舉例說明區(qū)基于場模型的局部操作、 聚焦（focal）和區(qū)域操作?基于對象模型的操作有哪些?答:基于場模型:局部操作:空間框架內(nèi)一個給定位置的新場的取值只依賴于同一個位置場的輸入值。上 P31。4、聚焦操作:區(qū)域操作:在指定位置的結(jié)果場的值依賴于同一位置的一個假定小領域輸入場的值。極限、高程場的梯度與聚集運算符或微積分中的積分運算有關。計算每個樹種的平均高度?；趯ο竽?/p>

13、型：面向集合、拓撲、方位、度量空間什么是拓撲關系，舉例說明拓撲與非拓撲特性、拓撲與非拓撲操作。答：是指滿足拓撲幾何學原理的各空間數(shù)據(jù)間的相互關系。即用結(jié)點、弧段和多邊形所表示的實體之間的鄰接關聯(lián)和包含等關系。拓撲特性：彈性變形后臨近物體之間的拓撲關系沒有發(fā)生改變非拓撲特性：彈性變形后臨近物體之間的拓撲關系發(fā)生了改變拓撲操作與非拓撲操作拓樸的eiidpoinHpoinu arc)sim pic-nonseh-inlersec ion( arc) on-kwrdar)piiini. region I nisi lid point, region)點是刪端點料交的K鑑時釧拿大和期刪邊畀E 明俄科斯市

14、任明K蘇達州內(nèi)uiiiide(piMrUt region)麥迪遜山百明尼耳達州之外iipciKregioiiiiJ加彳大的內(nèi)部是牛開誠彳、包旅兀邊界Uose (region JC胡皿n邯址孑閉域1包括JI邊界丨oiinicvlckh region)瑞;址亍連通域1 0TJA域r的仃:兩點，都有完 全內(nèi);tfl該K域1：的賂衿將這兩點連接他來）,Ml 4U；楚逢通域iTidc(p(jini, loop)點環(huán)中vnissestEiR, region)路（）穿過味林f K域）iiiuchcsfregion, region切圧JX込州（恢域）是威斯年；州（區(qū)域）的押 州州降曲卅i速豎躋t?。┙疬^常枇根

15、湖t K域1hniLhcsCJfL Tcgimii Jimerliip(regain, rcioiv 非拓撲的土地RUi 1236、如何有效利用磁盤硬件?提示：ppt : Using Disk Hardware EfficientlySize of sectors 扇區(qū)面積Larger sector p rovide faster tran sfer of large data sets? 數(shù)據(jù)集大時大扇區(qū)提供更快的傳輸速度But waste storage space in side sectors for small data sets但浪費了小數(shù)據(jù)集的存儲空間Placement of m

16、ost frequently accessed data items 放置頻繁使用的數(shù)據(jù)On middle tracks rather tha n inn ermost or outermost tracks? 在中間的磁道而不是最里面或最外面的磁道Reas on: mi ni mize average seek time 可以減少尋道時間Placement of items in a large data set requiring many sectors 放置一個需要很多扇區(qū)的大數(shù)據(jù)集Choose sectors from a single cylinder 盡量放在同一個柱面Reas

17、on: Mini mize seek cost in sca nning the en tire data set. 減少掃描全集花費的時間7、域（filed）、記錄（record）、文件（file ）的概念,提示：Mapp ing Records and files to Disk.RecordsOfte n smaller tha n a sectorMany records in a sectorFiles with many records 文件是記錄的集合Many sectors per file8、頁面的概念：磁盤與主存之間的最小傳輸單位。一個文件可能跨越多個頁面。一個頁面是槽的集

18、合，一個槽包含一條記錄9、文件結(jié)構(gòu)的含義，舉例說明幾種常用文件結(jié)構(gòu)一heap. Ordered、Hashed、Clustered。答：文件結(jié)構(gòu)是指文件中記錄的組織形式。堆：無序文件。記錄沒有特定的順序。，根據(jù)給定的關鍵碼（如name）查找一條記錄需要掃描文件中的記錄。在最壞情況下，文件的所有記錄都要被檢查，所有存儲該文件數(shù)據(jù)的磁盤頁面都要被訪問。平均來說，需要檢索一半的磁盤頁面。優(yōu)點是在進行插入操作時可以很容易地在文件末尾插入一條新記錄。存儲河流表散列文件：使用散列函數(shù)吧記錄分到一系列散列單元中?？扇≈幵谟谒軌虬褦?shù)量大致相同的記錄放入每個散列單元中。對于點查詢、插入、刪除都很有效。不適合范

19、圍查詢。按字符個數(shù)存儲城市名稱。有序文件：根據(jù)給定的主碼與對記錄進行組織。折半法非常有效。不能直接運用在空間領域例如，除非對多維空間中的點定義一個全序，否則無法對城市的位置排序。 有序文件組織方式還可以根據(jù)對空間數(shù)據(jù)集的文件組織方式而概括成空間聚類。聚類：聚類的目的就是降低響應常見的大查詢的尋道時間（ts）和等待時間（t1）。對于空間數(shù)據(jù)庫來說，這意味著在二級存儲中， 空間上相鄰的和查詢上有關聯(lián)性的對象在物理上應當存儲在一起。10、使用空間填充曲線組織空間數(shù)據(jù)的意義?提示： Chap ter 1 , Organizing sp atial data with sp ace filling cu

20、rvesImpose an orderi ng on the locati ons in a multi-dime nsional space? 加強了多維空間中的位置排序Allow use of traditi onal efficie nt search methods on sp atial data? 允許在空間數(shù)據(jù)中使用傳統(tǒng)的有效搜索11、掌握Z-曲線、hilbert曲線的生成。（要求給IJ號，能夠?qū)懗鰧猌碼和Hilbert碼的計算過程）12、基于Z-曲線，如何進行區(qū)域匹配的？（匹配有效性？）答：用z1和z2分別代表兩個z值，其中z1是較短的一個，并未失去一般性；對于相應的區(qū)域（比

21、如塊）r1和r2，只有兩種可能：1）如果z1是z2的前綴（例如，z1=l* , z2=11*或z1=*|* ，z2=11*），貝U r1完全包含r2 ； 2）兩個區(qū)域不相交（例如，z1=*0* ，z2=11*）。13、什么是索引？索引文件的內(nèi)容。主索引和二級索引。A table can have at most onep rimary in dex. Why?答：索引文件是用來提高數(shù)據(jù)文件查詢效率的輔助文件。記錄的只有碼值和數(shù)據(jù)文件中的頁面地址。索引記錄被排序，數(shù)據(jù)文件本身可以是不按關鍵碼排序。主索引，如果數(shù)據(jù)文件的記錄是按照主碼排列的，那么索引就只需要保存數(shù)據(jù)文件的每個磁盤頁面第一個主碼域值

22、。每個索引記錄一個數(shù)據(jù)頁面。二級索引：堆數(shù)據(jù)文件，一個索引記錄一個數(shù)據(jù)。一個磁盤最多只有一個主索引，因為主索引決定了數(shù)據(jù)在磁盤上的存儲順序。14、什么是空間索引？有哪些空間索引方法?答：空間索引結(jié)構(gòu)用一組桶（通常對應二級存儲的頁面）來組織對象?？臻g索引呢就是依據(jù)空間對象的位置和形狀或空間對象之間的某種空間關系按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)， 其中包含空間對象的概要信息，如對象的標識、外接矩形及指向空間 對象實體的指針。方法：1）在系統(tǒng)中加入專門的外部空間數(shù)據(jù)結(jié)構(gòu)，為空間屬性提供如同 B樹之于線性屬性的功能。2）使用空間填充曲線（如Z序、Hilbert曲線）將空間對象映射到一維空間，以便空間對象

23、存儲在標準的一維索引（例如B樹）中。R樹索引和R+樹索引15、網(wǎng)格文件包含哪兩部分內(nèi)容？建立格網(wǎng)索引的思路和步驟？ 了解 的思想?答：包含n維網(wǎng)格目錄，目錄只能夠的每一項指向一個數(shù)據(jù)桶。第二部分是由稱為線性比例的一維數(shù)組組成的結(jié)構(gòu)。記錄每一個格網(wǎng)所包含的空間思路：是將研究區(qū)域用橫豎線條劃分大小相等或不等的格網(wǎng),實體。當用戶進行空間查詢時，首先計算出用戶查詢對象所在格網(wǎng)，然后再在該網(wǎng)格 中快速查詢所選空間實體，這樣一來就大大地加速了空間索引的查詢速度。步驟: 劃分行列（M X N）；計算網(wǎng)格大小及每個格網(wǎng)的矩形范圍;開辟目標空間（記錄目標穿過的網(wǎng)格）和格網(wǎng)空間（記錄格網(wǎng)內(nèi)的目標） 注冊點、線、面

24、、注記等目標，并記錄之;提取窗口所覆蓋的目標關鍵字（采用數(shù)據(jù)位方法，以降低排序時間，及避免數(shù)據(jù)的繪制順序 等）；提取目標所涉及的網(wǎng)格。Chapter5 Query Processing and Optimization1從查詢處理的角度來看，空間數(shù)據(jù)庫與關系數(shù)據(jù)庫之間有哪些主要區(qū)別?答：至少有三個主要區(qū)別：、 與關系數(shù)據(jù)庫不同，空間數(shù)據(jù)庫沒有固定的運算符集合可以 充當查詢計算的基本構(gòu)件、空間數(shù)據(jù)庫要處理非常大量的復雜對象，這些對象具有空間范圍，不能自然的排列 成一維數(shù)組。I/O代價在CPU的處理代、檢測空間謂語要用到計算量極大的算法，所以不能再假定 價中只能主導地位2、空間查詢的基本構(gòu)件有哪些

25、?提示： PPt5.1.2 Choice of building blocks ， List of building blocksPoint Query， Range Query， Sp atial Jo in ， Nearest Neighbor;點查詢：給定一個查詢點 P,找出所有包含它的空間對象 O范圍或區(qū)域查詢：給定一個查詢多邊形P,找出所有與之相交的空間對象O空間鏈接：兩個表 R和S基于一個空間謂語 0進行連接時，該連接成為空間連接。最近鄰居：空間聚集，即給定一個對象0,找出所有距離 0最近的對象P3、空間查詢處理的 過濾-精煉模式”是什么，其目的？（對象操作的兩步查詢處理） 目的：

26、用兩步算法高效地處理復雜的數(shù)據(jù)類型過濾：尋找Q最終結(jié)果的超集 S;精煉：利用 GIS處理S來找到精確的 Q的答案4、空間查詢處理中，一般是采用什么（ MBR）來替代不同類型的空間實體（如線、面）？這樣做有何好處?提示： Ppt： Approximating spatial data typesMi nimum orthogo nal bou nding rectan gle (MOBR or MBR)最小外接矩形approximates line string, polygon,近似的線串；多邊形See Examples below (Black recta ngle are MBRs for

27、 red objects)MBRs are used by sp atial in dexes, e.g. R-treeMAlgorithms for sp atial op eratio ns MBRs are simp le 空間操作 MRS 的算法很簡單5、舉例說明SDBMS是如何利用空間實體的 MBRs來加快處理速度的?Ppt: Approximate Spatial Operations6、對于點查詢、區(qū)域查詢、空間連接查詢操作，各自有哪些處理算法(策略)？它們與什么因素有關?提示： Strategies for Point Queries,Strategies for Range

28、Queries，Strategies for Sp atial Jo ins與包含待查詢的關系的文件的組織方式有關。答：點查詢：數(shù)據(jù)未排列且沒有索引：窮舉法，掃描整個文件并判斷每條記錄是否滿足謂語建立空間索引：在索引中使用find操作；需要查找的磁盤扇區(qū)等于索引的深度空間填充曲線散列：運用折半法尋找點；檢驗大約logB(n),的磁盤扇區(qū)區(qū)域查詢：數(shù)據(jù)未排列且沒有索引：窮舉法，掃描整個文件并判斷每條記錄是否滿足謂建立空間索引：在索引中使用范圍查詢操作 空間填充曲線散列：驗證 Z值滿足范圍查詢要求；使用折半查詢找到最低的值；掃描前面的數(shù)據(jù)文件直至滿足查詢要求的最大的 空間連接：嵌套循環(huán)，檢驗所有可

29、能的空間謂語對;基于空間分塊，只檢驗普通空間區(qū)域的對象對 樹匹配：從每張表中找出分層的的對象組7、什么是查詢優(yōu)化器？查詢優(yōu)化器所承擔的主要任務是什么?答：查詢優(yōu)化器是數(shù)據(jù)庫軟件中的一個模塊，它用于產(chǎn)生不同計算計劃并確定適當?shù)膱?zhí)行策 略。主要任務：邏輯轉(zhuǎn)換、動態(tài)規(guī)劃。8、查詢語言與查詢樹之間的互換？語法分析器執(zhí)行 9、對查詢樹進行邏輯轉(zhuǎn)換的目的和一般方法是什么?答：方法：將非空間的選擇和投影操作下推目的：減少連接操作所涉及的關系大小，從而減少計算代價。10、Distributed Environments的概念？在分布式環(huán)境下，空間數(shù)據(jù)庫系統(tǒng)面臨哪些挑戰(zhàn)?提示 PPt： New issues f

30、or SDBMS)答：自治異質(zhì)計算機的集合，通過網(wǎng)絡連接，服務器框架：服務器提供定義明確的服務，用 戶使用服務。挑戰(zhàn)：概念模型上：不同種類模式之間的轉(zhuǎn)換邏輯模式上：在其他 SDBMS上命名、查詢表；其他 SDBMS上的表要復制原始表查詢過程與優(yōu)化：通過網(wǎng)路的數(shù)據(jù)傳輸代價將會主導CPU和I/O代價，需要新的策略來控制數(shù)據(jù)的傳輸成本。11、舉例說明分布式空間數(shù)據(jù)庫的半連接操作。(書上P161)答：1)只將連接屬性和主碼從站點1發(fā)送到站點2)只將有關元組從站點2發(fā)送到站點1.(書上P162)12、了解基于 Web的空間數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)。Cha pter & Sp atial Networks1、

31、舉例理解空間網(wǎng)絡、空間網(wǎng)絡查詢。鐵路網(wǎng)絡、密西西比河河網(wǎng)，查詢YW線沿途車站數(shù)量，最后一個車站，密西西比河的支流名稱2、圖及其相關概念。答：一個圖G=(V , E)是由一個有限頂點集V頂點之間的邊集 E組成的。邊集E頂點集V的一個二元關系。如果構(gòu)成邊集的各個頂點對是有序的，那么圖G就是有向的(directed);否則該圖是無向的(undirected)。頂點和邊有時也分別稱為結(jié)點(node)和鏈接(1ink)。有序頂點對的第一個頂點稱為前驅(qū)(Predecessor)或者源(source)，第二個頂點稱為后繼(successor) 目的(destination)或匯點(sink)。圖的結(jié)點和鏈接

32、有時要添加標號(Label)和權重(weight)，以便表示附加的信息。如果兩條邊共享一個結(jié)點，那么它們是鄰接的(adjacent), 一系列鄰接邊組成一條路徑(path)。例如，序列(v0 , v1), (v1 , v2)，(vn-2 , vn-1), (vn-1 , vn)表示一條路徑，因為每條邊都與前一條邊或者后一條邊有一個公共結(jié)點。如果端點v0和vn是同一個結(jié)點，那么這條路 徑稱為一個環(huán)(cycle)。河流網(wǎng)中沒有環(huán)，而在鐵路系統(tǒng)中，一條往返旅行線路構(gòu)成一個環(huán)。3、圖的物理存儲。鄰接矩陣、鄰接表(書上P182)“路徑”，然后再返回到頂層去走其他的“路徑”。4、關系代數(shù)對于空間網(wǎng)絡查詢的

33、主要缺陷？傳遞閉包的概念5、答：無法計算傳遞閉包。圖G(V , E)的傳遞閉包 G*是滿足下列條件的圖，它與G有相同的頂點集V，但它的邊集則由 G的所有路徑組成。6、SQL2 Connect語句的使用，會書上的例子。7、SQL3 With Recursive 語句的使用8、路徑查詢處理的種類：單對、單源、所有對。9、答：一個常用的圖操作就是確定道路網(wǎng)中兩個點A和B之間的最短路徑，路徑計算可以分為:單對(single pair):給定一個圖 G=(V, E)和N中的頂點u與v,找出u與v之間的最優(yōu)路徑。單對的一個特例就是最短路徑問題。單源(single source):給定一個源結(jié)點 u,找出從

34、u到G中所有可達結(jié)點之間的最優(yōu)路徑。-部分傳遞閉包(Partial transitive closure)問題。所有對(all pairs):在G中找出y的所有結(jié)點u和v之間的最優(yōu)路徑。-有關傳遞閉包的問題。10、圖遍歷的含義，圖遍歷的方法-Breadth first search 和 Dep th first search答：圖遍歷(graph traversal)算法是所有路徑查詢的計算基礎，它沿著圖的邊，通過從一個結(jié)點到另一個結(jié)點的遍歷來搜索路徑。路徑搜索是一個遞歸的操作,需要不斷把結(jié)點的鄰接表從磁盤讀到內(nèi)存緩沖區(qū)中。所以，為了使圖操作的查詢處理更加快速、有效，必須對圖算法進行特別的設計，以使其 I / O代價達到最小。Bre