空间数据库复习题讲解

1、Chapter 1: Introduction to Spatial Databases1举例说明什么是空间数据、非空间数据？如何理解空间查询(spatial queries)和非空间查询的区别(Non-spatial queries)？答：河流的泛洪区，卫星影像数据、气象气候数据等都可以是空间数据书店名称 店员人数，去年的销售量，电话号码等是非空间数据空间查询是对空间数据的查询或命令2、什么是GIS，什么是SDBMS ?请阐述二者的区别和联系。答：1 GIS是一个利用空间分析功能进行可视化和空间数据分析的软件。它的主要功能有： 搜索、定位分析、地形分析、流分析、分布、空间分析/统计、度量GI

2、S可以利用SDBMS来存储、搜索、查询、分享大量的空间数据集2、SDBMS是一个软件模块。它可以 、利用一个底层的数据库管理系统 、支持多种空间数据模型、相应的空间抽象数据类型(ADT )以及一种能够调用这些ADT的查询语言 、支持空间索引、高效的空间操作算法以及用于查询优化的特定领域规则3、区别与联系：、利用GIS可以对某些对象和图层进行操作，而利用 SDBMS则可以 对更多的对象集和图层进行更加简单的操作、SDBMS可以在GIS不能使用的某些领域进行使用，例如基因组学、天 文学、多媒体信息系统等、GIS可以作为SDBMS的前端，利用一个高效的SDBMS可以大大提高GIS的效率和生产率。3、

3、从GIS这一缩写的三种含义来理解GIS的发展历程。答：地理信息系统：为专业人员提供的软件地理信息科学：为地理信息系统和服务提供使用和发展的定义、框架和理论PC机上的地理和空间服务地理信息服务：为普通用户提供的网点和服务中心，例如4、用传统数据库系统管理空间数据，存在什么不足之处？答：1）无法用递归和嵌套的方式来描述复杂关系的层次和网状结构，模拟和操作复杂地理 对象的能力较弱；2）用关系模型描述本身具有复杂结构和涵义的地理对象时，需对地理实体进行不自然的分解，导致存储模式、查询途径及操作等方面均显得语义不甚合理；3）由于概念模式和存储模式的相互独立性，及实现关系之间的联系需要执行系统开销较大 的

4、联接操作，运行效率不够高4）空间数据通常是变长的，而一般 RDBMS只允许记录的长度设定为固定长度，此外，通 用DBMS难于存储和维护空间数据的拓扑关系。5）一般RDBMS都难以实现对空间数据的关联、连通、包含、叠加等基本操作。6）一般DBMS不能支持GIS需要的一些复杂图形功能。7）般RDBMS难以支持复杂的地理信息，因为单个地理实体的表达需要多个文件、多条记录，包括大地网、特征坐标、拓扑关系、属性数据和非空间专题属性等方面信息。8）GIS管理的是具有高度内部联系的数据，为了保证地理数据库的完整性，需要复杂的安全维护系统，而这些完整性约束条件必须与空间数据一起存储，由地理数据库来维护系统数据

5、的完整性。否则，一条记录的改变会导致错误、相互矛盾的数据存在，而一般RDBMS难以实现这一功能。5、What is a SDBMS ？答：SDBMS是一个软件模块。它可以 、利用一个底层的数据库管理系统 、支持多种空间数据模型、相应的空间抽象数据类型（ADT ）以及一种能够调用这些ADT的查询语言 、支持空间索引、高效的空间操作算法以及用于查询优化的特定领域规则6、什么是后关系数据库模型？后关系数据库模型有哪些？答：后关系数据库模型支持用户定义抽象数据类型，空间数据的类型可以添加。包括面向对象的数据库模式 OOBDMS和面向关系ORDBMS的数据库模式。7、 SDBMS的三层体系结构（Thre

6、e Layer Architecture ）是什么？借此深入理解 SDBMS的 作用。答：空间应用一空间数据库一DBMS教材P11的图8、空间数据库主要涉及哪些内容？答：数据模型、查询语句、查询处理与优化、文件组织和索引、数据挖掘9、举例说明单遍扫描查询和多遍扫描查询的概念。答：单边扫描查询中，被查询的表（关系）中的一条记录（元组）最多只被访问一次；例如列出武大周围5km内的书店的名字”。多遍扫描查询是被查询的表（关系）中的一条记录（元组）至少被访问一次，例如“找出其代表的选取范围大于 200公顷并且在这区拥有公司的女议员的名字”10、过滤一精炼策略的作用？两个步骤的内容是什么？提示： ppt

7、 : Efficient algorithms to answer spatial queriesCommon Strategy - filter and refine （过滤一精炼 ）Filter Step:Query Regio n overlaps with MBRs ofB,C and D过滤：查询区域与 B、C、D的最小外接矩形有重叠部分，保留B、C、D，其他的舍弃Refine Step: Query Regi on overlaps with B and C精炼：查询区域与 B、C有重叠，舍弃 D11、平面扫描（plane sweep）技术主要解决什么问题？其主要步骤？答：主要解决

8、的是如何在过滤阶段中尽可能多的淘汰不符合条件的对，从而减少几何计算的计算代价。Step 1:从左至右移动一条扫描线（例如，垂直于x轴的线），停在RU S的第一个元素处。这就是具有最小T. xl值的矩形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的数组索引为序，即 S仁S2、S2= S1、S3=S3。这样S2就是一个可能与R4交叠的候选矩形。Step 3:如果对任意 I j W

9、f,关系T. yl, T. yu n Sj. yl, Sj. yu存在，则 Sj 与 T 相交。因此，这一步就确定了 R4与S2的确是交叠的，并且 R4，S2是连接结果的一部分。记录 所有这样的信息，然后将矩形T (R4)从集合RU S中去掉，它不再需要参与结果集中的其他相交对。Step 4:继续移动扫描线来穿过集合RUS,直至碰到下一个矩形，在本例中是S2。这时进行步骤2和3。Step 5:当 RU S=?时，处理结束；12、从程序员的观点和 DBMS设计者的观点看，影响系统效率的因素有何不同。答：在程序员看来，计算机主要包括两个部分：CPU和无限量的内存在DBMS设计者看来，计算机主要包括

10、三个部分：CPU、有限的内存、无限的硬盘空间。访问硬盘的速度要远远小于访问内存的速度，因此前者关注减少算法的计算时间，后者强调的是将计算时间和 I/O时间的总和减少到最小。13、查询优化和数据挖掘的概念。答：查询优化：基于数据集的特点对查询中的操作进行排序，为每一步操作选择有效策略数据挖掘：即进行系统的搜索，找出隐藏在电子信息中潜在的有用信息。Chapter 2: Spatial Concepts and Data Models1、什么是数据模型？举例说明数据模型的重要性。答、数据模型是数据集的特定结构和模式，是对数据的文件描述，有利于某些性质的前期分析。作用：、属性的前期分析；、重利用多媒体

11、应用中的共享数据；、组织中交换数据 、将数据传递给新软件或环境例子：千禧年危机 正确的使用数据模式可以显著的降低成本，如果软件中的时间和数据被 定义成抽象数据模型，只有一小部分的软件会执行数据，ADT数据要被重新修改。2、掌握两种常用的空间信息模型：要素模型和场模型，矢量、栅格数据结构。森林模型中分段函数表示，区域中每个点被映射成主要树种对应的值要素模型：、对象：把空间信息抽象成明确的，可识别的事物或实体；、对象具有 属性和操作森林模型中多边形表示（林分），每个对象有唯一的标示符、主要树种和一 块区域。矢量数据结构栅格数据结构：栅格结构用密集正方形（或三角形，多边形）将地理区域划分为网格 阵列

12、。位置由行，列号定义，属性为栅格单元的值。点：由单个栅格表达。线：由沿线走向 有相同属性取值的一组相邻栅格表达。面：由沿线走向有相同属性取值的一片栅格表达。3、 基于场模型的操作有哪些，举例说明区基于场模型的局部操作、聚焦（focal）和区域操作？基于对象模型的操作有哪些？答：基于场模型：局部操作：空间框架内一个给定位置的新场的取值只依赖于同一个位置场的输入值。书上 P31。聚焦操作：在指定位置的结果场的值依赖于同一位置的一个假定小领域输入场的值。极限、高程场的梯度区域操作：与聚集运算符或微积分中的积分运算有关。计算每个树种的平均高度。基于对象模型：面向集合、拓扑、方位、度量空间4、什么是拓扑

13、关系，举例说明拓扑与非拓扑特性、拓扑与非拓扑操作。答：是指满足拓扑几何学原理的各空间数据间的相互关系。即用结点、弧段和多边形所表示的实体之间的邻接关联和包含等关系。拓扑特性：弹性变形后临近物体之间的拓扑关系没有发生改变非拓扑特性：弹性变形后临近物体之间的拓扑关系发生了改变拓扑操作与非拓扑操作拓朴的endfKMiiUpiMRL arc)m pic-曲口记 f-i okrsec ion( arc on-btwndaryfpoini. rcgionl irisiddpi)iii. reo ion)点翩的端点丰自交蹶探哥华曲拿大和牺的边界上明削翻斯市倒尼苏达州内ouisidc(point, regio

14、n)贞迪逊市左明尼拂达州之外upciif region)加F大的肉部建亍JT嫌不包括其边界）doseiiegioiv3kw聯是个阖域（包括其边界）co肺ecledirc苦 iurU瑞上径个世通域（対于区域1:的任两点都彳沈 全内含打谈K域上的踣泾将这两点连按爬来h MH 本不企连通域insidefpoint loop)点百;环中vi HsNCN(ir236、如何有效利用磁盘硬件?提示：ppt :Using Disk Hardware EfficientlySize of sectors 扇区面积? Larger sector provide faster tran sfer of large

15、data sets? 数据集大时大扇区提供更快的传输速度? But waste storage space in side sectors for small data sets? 但浪费了小数据集的存储空间Placement of most frequently accessed data items 放置频繁使用的数据? On middle tracks rather tha n inn ermost or outermost tracks? 在中间的磁道而不是最里面或最外面的磁道?Reas on: mi ni mize average seek time 可以减少寻道时间Placemen

16、t of items in a large data set requiring many sectors 放置一个需要很多扇区的大数据集? Choose sectors from a single cylinder 尽量放在同一个柱面?Reas on: Mini mize seek cost in sca nning the en tire data set. 减少扫描全集花费的时间7、域（filed）、记录（record）、文件（file ）的概念,提示： Mapping Records and files to Disk.? Records?Often smaller tha n a s

17、ector? Many records in a sector? Files with many records 文件是记录的集合? Many sectors per file8、页面的概念：磁盘与主存之间的最小传输单位。一个文件可能跨越多个页面。一个页面 是槽的集合，一个槽包含一条记录9、 文件结构的含义，举例说明几种常用文件结构一heap，Ordered、Hashed、Clustered。 答：文件结构是指文件中记录的组织形式。堆：无序文件。记录没有特定的顺序。，根据给定的关键码（如name）查找一条记录需要扫描文件中的记录。在最坏情况下，文件的所有记录都要被检查，所有存储该文件数据的磁盘

18、 页面都要被访问。平均来说，需要检索一半的磁盘页面。 优点是在进行插入操作时可以很容 易地在文件末尾插入一条新记录。存储河流表散列文件：使用散列函数吧记录分到一系列散列单元中。可取之处在于它能够把数量大致相同的记录放入每个散列单元中。对于点查询、插入、删除都很有效。不适合范围查询。 按字符个数存储城市名称。有序文件：根据给定的主码与对记录进行组织。折半法非常有效。不能直接运用在空间领域例如，除非对多维空间中的点定义一个全序，否则无法对城市的位置排序。有序文件组织方式还可以根据对空间数据集的文件组织方式而概括成空间聚类。聚类：聚类的目的就是降低响应常见的大查询的寻道时间（ts）和等待时间（t1）

19、。对于空间数据库来说，这意味着在二级存储中，空间上相邻的和查询上有关联性的对象在物理上应当存储在一起。10、使用空间填充曲线组织空间数据的意义？提示： Chapter 1 , Organizing spatial data with space filling curves? Impose an ordering on the locations in a multi-dimensional space? 加强了多维空间中的位置排序? Allow use of traditi onal efficie nt search methods on spatial data? 允许在空间数据中使用传

20、统的有效搜索11、 掌握Z-曲线、hilbert曲线的生成。（要求给IJ号，能够写出对应Z码和Hilbert码的计 算过程）12、基于Z-曲线，如何进行区域匹配的？（匹配有效性？）答：用z1和z2分别代表两个z值，其中z1是较短的一个，并未失去一般性；对于相应的区域（比如块）r1和r2，只有两种可能：1）如果z1是z2的前缀（例如，z1=l* ，z2=11* 或z1=*l*，z2=11*），则r1完全包含r2 ； 2）两个区域不相交（例如，z1= *0*，z2=11*）。13、 什么是索引？索引文件的内容。主索引和二级索引。A table can have at most one primar

21、y in dex. Why?答：索引文件是用来提高数据文件查询效率的辅助文件。记录的只有码值和数据文件中的页 面地址。索引记录被排序，数据文件本身可以是不按关键码排序。主索引，如果数据文件的记录是按照主码排列的，那么索引就只需要保存数据文件的每个磁盘页面第一个主码域值。每个索引记录一个数据页面。二级索引：堆数据文件，一个索引记录一个数据。一个磁盘最多只有一个主索引，因为主索引决定了数据在磁盘上的存储顺序。14、什么是空间索引？有哪些空间索引方法？答：空间索引结构用一组桶（通常对应二级存储的页面）来组织对象。空间索引呢就是依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种

22、数据结构， 其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。方法：1）在系统中加入专门的外部空间数据结构，为空间属性提供如同 B树之于线性属性的功能。2）使用空间填充曲线（如Z序、Hilbert曲线）将空间对象映射到一维空间，以便空间对 象存储在标准的一维索引（例如B树）中。15、 网格文件包含哪两部分内容？建立格网索引的思路和步骤？ 了解R树索引和R+树索引 的思想？答：包含n维网格目录，目录只能够的每一项指向一个数据桶。第二部分是由称为线性比例的一维数组组成的结构。思路：是将研究区域用横竖线条划分大小相等或不等的格网，记录每一个格网所包含的空间实体。当用户进行空

23、间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。步骤：划分行列（M X N）；计算网格大小及每个格网的矩形范围；开辟目标空间（记录目标穿过的网格）和格网空间（记录格网内的目标）；注册点、线、面、注记等目标，并记录之；提取窗口所覆盖的目标关键字 （采用数据位方法，以降低排序时间，及避免数据的绘制顺序 等）;提取目标所涉及的网格。Chapter5 Query Processing and Optimizationi从查询处理的角度来看，空间数据库与关系数据库之间有哪些主要区别？答：至少有三个主要区别：、与关系数据库不同，空间

24、数据库没有固定的运算符集合可以充当查询计算的基本构件 、空间数据库要处理非常大量的复杂对象，这些对象具有空间范围，不能自然的排列成一维数组。 、检测空间谓语要用到计算量极大的算法，所以不能再假定I/O代价在CPU的处理代价中只能主导地位2、空间查询的基本构件有哪些？提示： ppt5.1.2 Choice of building blocks ， List of building blocksPoint Query， Range Query， Spatial Join， Nearest Neighbor ；点查询：给定一个查询点P,找出所有包含它的空间对象0范围或区域查询：给定一个查询多边形P,

25、找出所有与之相交的空间对象0空间链接：两个表 R和S基于一个空间谓语 B进行连接时，该连接成为空间连接。最近邻居：空间聚集，即给定一个对象0,找出所有距离 0最近的对象P3、 空间查询处理的过滤-精炼模式”是什么，其目的？（对象操作的两步查询处理）目的：用两步算法高效地处理复杂的数据类型过滤：寻找Q最终结果的超集 S;精炼：利用 GIS处理S来找到精确的 Q的答案4、空间查询处理中，一般是采用什么（ MBR）来替代不同类型的空间实体（如线、面）？ 这样做有何好处？提示： Ppt： Approximating spatial data typesMi nimum orthogo nal bou

26、nding rectan gle （MOBR or MBR）最小外接矩形approximates line string, polygon, 近似的线串； 多边形See Examples below (Black recta ngle are MBRs for red objects)MBRs are used by spatial in dexes, e.g. R-treeMAlgorithms for spatial operations MBRs are simple 空间操作 MRS 的算法很简单5、 举例说明SDBMS是如何利用空间实体的MBRs来加快处理速度的？Ppt: Appro

27、ximate Spatial Operations6、对于点查询、区域查询、空间连接查询操作，各自有哪些处理算法(策略)？它们与什么因素有关？提示： Strategies for Point Queries,Strategies for Range Queries，Strategies for Spatial Joins与包含待查询的关系的文件的组织方式有关。答：点查询：数据未排列且没有索引：穷举法，扫描整个文件并判断每条记录是否满足谓语建立空间索引：在索引中使用find操作；需要查找的磁盘扇区等于索引的深度空间填充曲线散列：运用折半法寻找点；检验大约logB(n),的磁盘扇区区域查询：数据未

28、排列且没有索引：穷举法，扫描整个文件并判断每条记录是否满足谓语建立空间索引：在索引中使用范围查询操作空间填充曲线散列：验证Z值满足范围查询要求；使用折半查询找到最低的Z值；扫描前面的数据文件直至满足查询要求的最大的Z值空间连接：嵌套循环，检验所有可能的空间谓语对；基于空间分块，只检验普通空间区域的对象对树匹配：从每张表中找出分层的的对象组7、什么是查询优化器？查询优化器所承担的主要任务是什么？答：查询优化器是数据库软件中的一个模块，它用于产生不同计算计划并确定适当的执行策略。主要任务：逻辑转换、动态规划。8、 查询语言与查询树之间的互换？语法分析器执行9、对查询树进行逻辑转换的目的和一般方法是

29、什么？答：方法：将非空间的选择和投影操作下推目的：减少连接操作所涉及的关系大小，从而减少计算代价。10、Distributed Environments的概念？在分布式环境下，空间数据库系统面临哪些挑战？提示 ppt: New issues for SDBMS)答：自治异质计算机的集合，通过网络连接，服务器框架：服务器提供定义明确的服务，用 户使用服务。挑战：概念模型上：不同种类模式之间的转换逻辑模式上：在其他 SDBMS上命名、查询表；其他 SDBMS上的表要复制原始表查询过程与优化：通过网路的数据传输代价将会主导CPU和I/O代价，需要新的策略来控制数据的传输成本。11、 举例说明分布式空

30、间数据库的半连接操作。(书上P161)答：1)只将连接属性和主码从站点1发送到站点22)只将有关元组从站点2发送到站点1.12、 了解基于 Web的空间数据库系统的体系结构。(书上P162)Chapter 6: Spatial Networks1、 举例理解空间网络、空间网络查询。铁路网络、密西西比河河网，查询YW线沿途车站 数量，最后一个车站，密西西比河的支流名称2、图及其相关概念。答：一个图G=(V，E)是由一个有限顶点集 V顶点之间的边集 E组成的。边集E顶点集V 的一个二元关系。如果构成边集的各个顶点对是有序的，那么图 G就是有向的(directed);否则该图是无向的(undirec

31、ted)。顶点和边有时也分别称为结点(node)和链接(1ink)。有序顶点对的第一个顶点称为前驱(predecessor)或者源(source)，第二个顶点称为后继(successor) 目的(destination)或汇点(sink)。图的结点和链接有时要添加标号(Label)和权重(weight)，以便表示附加的信息。如果两条边共享一个结点，那么它们是邻接的(adjacent)，一系列邻接边组成一条路径(path)。例如，序列(v0 , v1), (v1 , v2)，(vn-2 , vn-1), (vn-1 , vn)表示一条路径，因为每条边都与前一条边或者后一条边有一个公共结点。如果端

32、点v0和vn是同一个结点，那么这条路径称为一个环(cycle)。河流网中没有环，而在铁路系统中，一条往返旅行线路构成一个环。3、 图的物理存储。邻接矩阵、邻接表(书上P182)4、关系代数对于空间网络查询的主要缺陷？传递闭包的概念5、 答：无法计算传递闭包。图G(V, E)的传递闭包 G*是满足下列条件的图，它与G有相同的顶点集V，但它的边集则由 G的所有路径组成。6、SQL2 Connect语句的使用，会书上的例子。7、SQL3 With Recursive 语句的使用8、路径查询处理的种类：单对、单源、所有对。9、 答：一个常用的图操作就是确定道路网中两个点A和B之间的最短路径，路径计算可

33、以 分为：单对(single pair):给定一个图 G=(V, E)和N中的顶点u与v,找出u与v之间的最优路径。单对的一个特例就是最短路径问题。单源(single source):给定一个源结点 u,找出从u到G中所有可达结点之间的最优路径。-部分传递闭包(partial transitive closure)问题。所有对(all pairs):在G中找出y的所有结点u和v之间的最优路径。-有关传递闭包 的问题。10、 图遍历的含义，图遍历的方法-Breadth first search 和 Depth first search答：图遍历(graph traversal)算法是所有路径查询的计算基础，它沿着图的边，通过从一个结点到另一个结点的遍历来搜索路径。路径搜索