（计算机软件与理论专业论文）空间数据库中空间连接和查询优化研究.pdf

哈尔滨理工大学t 学硕上学位论文 空间数据库中空间连接和查询优化研究 摘要 空间数据库是随着地理信息系统的开发和应用而发展起来的数据库新技 术。空间数据库的性能问题严重制约了它的应用与发展。空间数据库中最重 要的一种空间查询是空间连接查询，即从两个数据集合中检索出所有满足某 一空间谓词( 如交、包含等) 的空间对象。由于空间连接运算是空间数据库中 最复杂、最耗时的基本操作，因此其处理效率在很大程度上决定了空间数据 库的整体性能。尽管目前已经有许多空间连接算法，但空间连接运算的代价 估计和查询优化仍然有待进一步研究。 本课题在仔细研究目前多种空间数据库查询方法的基础上，提出了一种 新的空间对象的近似一栅格近似。这种新的近似方法在m s q p 中作为一种 过滤器来处理空间连接，包括三种基本数据类型和它们之间不同的空间连 接。论文提出了三色栅格图( 3 c r s _ t h r e e c o l o rr a s t e rs i g n a t u r e ) 。3 c r s 是在4 c r s 的基础上提出的。3 c r s 是一种基于栅格单元的空间对象的压缩 和近似表示。每一种颜色代表了对象和单元格之间的一种相交类型。事实 上，3 c r s 是一个4 c r s ，其中4 c r s 中的w e a k 和s t r o n g 单元类型分别被i n c o n c l u s i v e 单元类型所代替。w e a k 类型代表一种多边形，这种多边形和单 元格相交的区域小于等于5 0 ，而s t r o n g 类型代表了另一种类型的多边 形，这种多边形与单元格相交的区域大于5 0 而小于1 0 0 。3 c r s 的i n c o n c l u s i v e 类型代替了4 c r s 的这两种类型，它代表单元格和对象相交，但是并 没有完全被多边形占据。这种特性使得3 c r s 能用来表示多线和点这两种空 间数据类型。 3 c r s 的优点是加快产生时间而且可以用于表示多边形，多线和点( 没 有任何具体特征) 。同时，可以用算法来评估包含这三种数据类型的连接谓 词。分析了3 c r s 单元格的基本类型，给出了3 c r s 的生成算法和标度变化 算法。最后，给出了基于3 c r s 的空间连接比较算法。同时对其进行了分 析，分析结果表明本文所提方法是有效的。 关键词空问数据库；空间连接；查询优化；三色栅格图 哈尔滨理工大学工学硕十学位论文 r e s e a r c ho fs p a t i a lj o i na n dq u e r yo p t i m i z a t i o n i ns p a t i a ld a t a b a s e s a b s t r a c t s p a t i a ld a t a b a s e i san e wd a t a b a s et e c h n o l o g y ，p r o m o t e db yk i n d so f d e v e l o p m e n t a n da p p l i c a t i o n so fg e o g r a p h i c a l i n f o r m a t i o n s y s t e m s t h e p e r f o r m a n c ep r o b l e mo fs p a t i a ld a t a b a s el i m i t si t sa p p l i c a t i o na n dd e v e l o p m e n t s e r i o u s l y a m o n gs p a t i a lo p e r a t i o n s ，s p a t i a lj o i ni so n e o ft h em o s tu s e f u l s p a t i a l i o i ni st h em o s tc o m p l e xa n dt i m e - c o n s u m i n go p e r a t i o ni ns p a t i a ld a t a b a s e s y s t e m i t se f j f i c i e n c yd e t e r m i n e st h ep e r f o r m a n c eo ft h ew h o l es p a t i a ld a t a b a s e s y s t e mt oag r e a te x t e n t a l t h o u g ht h e r ea r em a n ys p a t i a lj o i na l g o r i t h m s ，c o s t e s t i m a t i o na n dq u e r yo p t i m i z a t i o no fs p a t i a ljo i no p e r a t i o nn e e df u r t h e rs t u d y b a s e do na n a l y z i n gs o m es p a t i a l t e m p o r a ld a t a b a s eq u e r ym e t h o d s ，t h i s t h e s i sp r o p o s e dan e wr a s t e ra p p r o x i m a t i o ns u i t a b l et op e r f o r m i n gs p a t i a lj o i n sa s af i l t e ri nt h es e c o n ds t e po ft h em u l t i - s t e pq u e r yp r o c e s s o r ，i n v o l v i n gt h e s e t h r e ec o m m o nd a t at y p e s ( p o l y g o n ，p o l y l i n ea n dp o i n t ) a n dt h e c l a s s e so f d i f f e r e n ts p a t i a lj o i n si n v o l v i n gt h e m w ep r o p o s e dar a s t e rs i g n a t u r en a m e d t h r e e c o l o rr a s t e rs i g n a t u r e ( 3 c r s ) t h e3 c r si sb a s e do n4 c r s 3 c r si sa c o m p a c ta n da p p r o x i m a t e dr a s t e rr e p r e s e n t a t i o no fo b j e c t su p o nag r i do fc e l l s t h a tu s e sf e wc o l o r s e a c hc o l o rr e p r e s e n t sa ni n t e r s e c t i o nt y p eb e t w e e nt h e o b j e c ta n dt h ec e l l a c t u a l l y 3 c r si sa4 c r sw h e r et h ew e a ka n ds t r o n gc e l l t y p e sa r er e p l a c e db ya ni n c o n c l u s i v et y p e t h ew e a k4 c r s e e l lt y p er e p r e s e n t s t h a tt h ep o l y g o nh a sa ni n t e r s e c t i o ne q u a lo rl e s st h a n5 0 w i t ht h ec e l l ，a n dt h e s t r o n gt y p er e p r e s e n t sa ni n t e r s e c t i o ng r e a t e rt h a n 5 0 a n dl e s st h a n10 0 t h e 3 c r si n c o n c l u s i v ec e l lt y p er e p l a c e st h e s et w ot y p e s ，a n di tr e p r e s e n t st h a tt h e r e i sap o r t i o no ft h eo b je c tw i t h i nt h e t h i sc h a r a c t e r i s t i ca l l o w s3 c r st o w a y i tr e p r e s e n t sp o l y g o n s c e l l ，w h i c hd o e sn o to v e r l a pt h ew h o l ec e l l r e p r e s e n tp o l y l i n e sa n dp o i n t si nt h es a m e t h e3 c r ss i g n a t u r eh a st h em a i na d v a n t a g eo ff a s t e rg e n e r a t i o nt i m ea n d i i t h a ti tc a nb eu s e dt or e p r e s e n tp o l y g o n s ，p o l y l i n e sa n dp o i n t s ( w i t h o u ta n y s p e c i f i cc h a r a c t e r i s t i c ) w ea n a l y z e dt h et y p eo f t h ec e l l so ft h e3 c r s ，p r o v i d e d a na l g o r i t h mt og e n e r a t e3c r sa n dg a v ea na l g o r i t h mf o rc h a n g eo f s c a l e i nt h e e n d ，t h i st h e s i sg a v ea na l g o r i t h mf o rs p a t i a lj o i n sq u e r yo p t i m i z a t i o nw h i c h i s b a s e do nt h e3 c r s b e s i d e s ，w ea n a l y z e d t h ea l g o r i t h ma n dt h er e s u l t s d e m o n s t r a t e dt h ee f f e c t i v e n e s so ft h ea p p r o a c h k e y w o r d s s p a t i a ld a t a b a s e s ，s p a t i a ljo i n ， s i g n a t u r e 1 1 1 q u e r yo p t i m i z a t i o n ，t h r e e c o l o rr a s t e r 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文空间数据库中空间连接和查询 优化研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期问独立进 行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己发 表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以 明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：奔睃；舌日期：护8 年：；月勿日 哈尔滨理工大学硕士学位论文使用授权书 空间数据库中空间连接和查询优化研究系本人在哈尔滨理工大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工 大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨 理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文 和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、 缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 年解密后适用授权书。 作者签名： 谈i 舌日期：嗒年罗月加日 导师签名：善弼日期： 。子年弓月口日 哈尔滨理工大学工学硕十学位论文 1 1 研究背景和意义 1 1 1 研究背景 第1 章绪论 空间数据库系统是描述、存储和处理空间数据及其属性数据的数据库系 统。空间数据库是随着g i s 的开发和应用而发展起来的数据库新技术。它并不 是独立存在的系统，它与应用紧密结合，通常是g i s 的核心。 经过2 0 多年的发展，空间数据库已成为一个热点研究领域，其研究成果 ( 如空间多维索引) 开始应用于许多不同领域。正是已有应用的需求推动了空 间数据库管理系统的研究，这些应用包括地理信息系统( g e o g r a p h i c a l i n f o r m a t i o ns y s t e m ，i s ) 矛i 计算机辅助设计( c o m p u t e r - a i d e dd e s i g n ，c a d ) ，以 及诸如多媒体信息系统( m u l t i m e d i ai n f o r m a t i o ns y s t e m ，m m i s ) 、数据仓库 ( d a t aw a r eh o u s e ，d w h ) 、美国国家航天航空局( n a t i o n a la e r o n a u t i c sa n ds p a c e a d m i n i s t r a t i o n ，n a s a ) 的地球观测系统等潜在应用。 人类在2 l 世纪将全面进入信息时代，在信息技术蓬勃发展的今天，有关 地球科学和地理信息管理方面的问题引起了大量学者的关注，地理信息系统 ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，g i s ) 的研究辅以信息科学以及高效的信息技术 手段，使地理信息系统的发展达到了一种前所未有的高度。地理信息管理是与 人类生存、发展、进步密切相关的一门信息科学与技术，是地球空间信息科学 的重要组成部分，是信息产业发展的重要支柱，它被广泛应用于国民经济的很 多部门，如城市规划与设计、资源环境管理、生态环境监测与保护、地质勘探 测量、城市管网配电网、灾害监测防治等多个领域。 跨入2 1 世纪，使用数据库管理包括地图及其属性的空间数据，成为空间 数据库应用系统发展的潮流。与传统文件方式相比，空间数据库技术有明显的 技术优势，包括海量数据管理能力、图形和属性数据一体化存储、多用户并发 访问、完善的访问权限控制和数据安全机制等。空间数据库技术正在逐步取代 传统文件，成为越来越多的大中型空间数据库应用系统的空间数据存储和查询 的解决方案。近些年来，随着地理信息系统、计算机辅助设计、多媒体系统、 医学或卫星图像数据处理等领域的发展，空间数据库以及对空间数据进行查询 哈尔滨理工大学t 学硕上学位论文 的研究倍受关注。由于空间数据量的庞大以及空间对象、空间查询的高度复杂 性，空间查询优化成为了空问数据库应用的难点和突破点。而现有的关系数据 库查询优化技术不能完全适用于空问数据。优化空间查询从而提高空间数据库 的性能，对空间数据库的应用具有重要意义。 自1 9 8 4 年j n i e v e r g e l t ，h h i n t e r b e r g e r 和k c s e v e i k 最先提出网格索引技术 以来，网格索引就成为了研究的热点。在此之后，各国研究人员相继提出了许 多的变种：m u l t il e v e lg f ( 1 9 8 5 年k w h a n g 和r k r i s h n a m u r t h y ) 、m u l t i l a y e r g f ( 1 9 8 8 年h s i x ，p w i d m a y e r ) 、p a r a l l e lg f ( 1 9 9 3 年l j i a n z h o n g ，d r o t e m 和 j s r i v a s t a v a ) 等。它们都在原有的基础上对网格索引进行了一定的改进，使其性 能得到了很大的提高，但它们都不能避免由于数据的冗余度过大所造成的空间 索引效率明显下降的缺点，特别是对于日益增长的海量空间数据。 将地理区域的平面表象按一定分解力作行和列的规则划分，形成密集格 网，每个网格单元称为象元。栅格数据结构实际上就是象元阵列，即象元按矩 阵形式的集合，栅格中的每个象元是栅格数据中最基本的信息存储单元，其坐 标位置用行号和列号确定，即实体位置关系是隐含在行号、列号之中的。网格 中每个元素的代码代表了实体的属性或属性的编码，根据所表示实体的表象信 息差异，各象元可用不同的“灰度值”来表示。本课题主要研究了基于栅格的 空间连接查询优化技术。 1 1 2 研究意义 空间数据库中查询优化技术的研究，特别是空间连接和查询优化技术的研 究在空间数据库领域具有深远的影响和巨大的作用。实际应用如地理信息系统 ( g i s ) ，c a d c a m 等对空间数据库的查询性能提出了迫切要求。同时由于空间 连接运算是空间数据库中最复杂、最耗时的基本操作。因此其处理效率在很大 程度上决定了空间数据库的整体性能。同时，g i s 用户提出的大部分问题都可以 表达为查询的形式。查询功能是g i s 面向用户的窗口，是用户感觉g i s 台g 力的最 直接的具体表现。近些年来，随着g i s 的迅猛发展，广大用户对空间查询提出 了更高更复杂的要求，简单的图文互查已远远不能满足g i s 用户的需求。虽然 已有许多专家学者致力于空间查询方面的研究，并取得了一些可喜的研究成 果，但距离用户的复杂查询要求还有一定的差距，还有待进一步深入和加强。 对空间连接查询技术的研究已成为当前g i s 研究领域需要进一步深入解决的重 大前沿课题之一。 哈尔滨理工大学工学硕十学位论文 空间查询效率评估是空间数据库中一个重要问题。空间连接是空间操作中 最重要操作之一。精确几何图形的测试是一个耗时的操作，无论是i o 时间或c p u 时间。用平面扫描算法测试精确几何图形的c p u 代价是很高的。和测试精确 几何图形相关的i o 代价通常是由访问大空间对象的实际表示造成的。已经有 很多专家和学者研究了空间连接，也有很多方法来处理空间连接操作。本课题 的着眼点是空间数据库中的查询技术，主要是对其中的空间连接和查询优化技 术方法进行了研究。 1 2 国内外研究现状 早期的研究者大多注重于借鉴关系数据库查询优化技术来优化空间数据库 中属性数据的查询，对优化空间数据的查询则研究得较少。近年来，空间查询 优化的研究逐渐以空间数据查询的优化为主要内容，且这样韵研究已取得了很 大进展，出现了以下几类适用于空间数据查询的优化技术： 1 空间索引技术较早的空间查询优化研究集中在空间索引这一领域。 索引是快速、有选择地存取数据的一种机制。它相当于一个映射机制，将属性 的值转换为相应记录的地址或地址集。对于空间数据，其存取主要依赖于空间 对象之间的位置关系，而不是像传统数据那样，依赖于某个属性的取值。这就 使得空间索引机制与传统索引机制不同，并且许多对传统数据有效的索引机制 不能有效地应用于空间数据。空间数据库的研究经过近三十年的发展，涌现了 大量的空间索引技术。其中，r 树及其变形树幢1 是公认的最有效的空间索 引，它们也是目前最常用的空间索引。 国内外已有很多学者进行了基于r 树的空间连接查询处理方面的研究。空 间连接查询是基于空间关系的查询，常采用过滤一精炼两步策略，目前大部分 的研究情况都集中在过滤阶段，典型的有：h u ay u n w u 和j i n gn i n g 等曲1 、 d i m i t r i sp a p a d i a s n l 等进行了基于r 树的空间连接方法研究，p l l i n 1 提出了一 种在空间数据库中进行基于拓扑关系连接查询的有效方法，h y o s e o ps h i n 阳1 等、g i s l ir h j a l t a s o n n l 等、t s i ns h uy e h 旧1 等、分别进行了基于距离关系连接查 询的研究，y a n n i st h e o d o r i d i s 1 叫等、h o n g j u nz h u 1 等、肖予钦2 1 等进行了基 于方向关系的连接查询研究。在精炼阶段的研究相对较少，主要的研究 有，j i t i a nx i a o 【l 引等、s h a s h is h e k h a r 1 引等。 此外，刘宇n 朝等、及g a n gl u o n 6 1 等对空间连接查询的并行处理算法进行了 一些研究。 哈尔滨理工大学工学硕上学位论文 2 查询处理算法的优化空间查询处理过程一般分为两步过滤和求 精，即首先在过滤步骤中判断空间对象的近似描述( 如m b r ) 是否满足查询条 件，这些满足条件的对象构成候选集，在求精步骤对候选集中的对象进行几何 计算，从而得到最终结果。由于空间数据自身的特点，几何计算所耗时间和所 占空间巨大。优化查询处理算法、从而提高查询处理效率，是空间查询优化研 究的一个重要内容。避免或减少几何计算是优化空间查询处理过程的出发点。 在过滤和求精之间插入一个中间步骤，使用另一种近似对候选集做进一步的过 滤，减少候选集对从而避免一些不必要的几何计算，此项研究己应用于o r a c l e 空间数据库中n7 1 。空间对象的形状大多为多边形，改进多边形检测算法可提高 查询效率。例如，w a e l m b a d a w y ，w a l i dg a r e f 提出利用启发式信息来判断两 个空间数据集中的对象是否相交从而减少复杂的几何计算量n8 1 9 1 。此外，将复 杂多边形分解为简单多边形也有利于减少几何计算量，多边形分解在模式识 别、图像处理、数据压缩等领域也有研究和应用n 。 3 代价估算模型利用代价估算模型寻找较优的查询执行计划，这是空 间查询中常用的优化方法之一。空间选择和空间连接是两种最常用的空间查询 操作，大多数的估算模型针对它们而提出。目前空间查询代价的研究主要集中 在i o 代价的估算上。而i o 代价又分为读取操作对象的i o 代价和输出查询 结果的i o 代价乜训。在查询过程中需要访问参与查询的空间对象，这些对象往 往通过空间索引来访问，读取操作对象的i o 代价可从访问索引的代价反映出 来。r 树目前最常用的空间索引，因此基于r 树的代价模型被广泛研究口h2 铂。 在未执行查询操作时，输出查询结果的i o 代价可表示为查询选择性因子与读 取操作对象的i o 代价的乘积，而查询选择性因子又为查询结果集的大小与源 数据集大小的比值。由此，估算出查询结果集的大小后，输出查询结果的i o 代价就可估算得到。研究者从空间数据的特点出发，使用直方图来估算查询结 果集的大小姐引。 空间对象的近似描述对空间数据的存取和处理具有重要作用。通常以 m b r 心4 1 作为二维空间对象的近似描述。但是，这样的描述并不精确，在很多情 况下会影响查询优化的效果。人们开始采用近似精度更高的描述形式来表示空 间对象( 如五角形、直角多边形等) ，并在此基础上进行查询优化的研究。这 样的研究已成为空间查询优化研究的趋势。 由于空间数据的复杂性，上述技术对空间查询的优化程度还比较低，仍有 待进一步研究。不少研究者从整体的角度建立了查询优化系统，如美国马里兰 大学的s a n d 空间数据库查询优化系统、韩国某研究所的o m e g a 面向对象 哈尔滨理丁大学t 学硕十学位论文 空间数据库的查询优化系统、国内北京大学w e bg i s 项目中的空间查询优化系 统f q p r o 幢5 1 等。但是，至今还没有提出一个完整的空间查询优化系统。s a n d 空间数据库具有一定的查询优化能力，并使用了一个空间连接操作的执行代价 和选择性的分析模型，部分实现了操作顺序的重组和子查询结果的合并。但 是，s a n d 对属性数据和空间数据的查询基本上是分别优化的，没有将两者有 机地结合起来。 1 3 课题的来源及研究内容 1 3 1 课题来源 本课题来自省自然科学基金：f 2 0 0 6 0 1 。 1 3 2 研究的主要内容 本文研究的重点是以地理信息系统中海量空间数据的管理技术为出发点， 探讨了当前主流的数据库访问技术和作为实现海量数据管理关键技术的空间快 速索引技术，并在此基础上实现了地理空间数据的查询操作。在分析和总结大 量空间数据库理论知识的基础上，主要对以下几个方面进行了研究，具体概括 如下： 1 分析了空间数据库技术的基础上，研究了空间连接和查询优化技术， 总结了其研究现状； 2 空间数据库概述。具体分析空间数据库的空间数据表达、空间数据建 模、空问数据索引、空间数据查询、空间数据库体系结构和空间数据库应用等 各个方面的研究进展； 3 对当前的空间索引技术进行了分类比较； 4 空间连接和查询优化技术。系统地对空间连接查询进行了研究，同时 预测了空间连接查询和优化技术的研究热点和发展趋势； 5 针对各种空问连接和查询优化方法中存在的不足，本文提出了一种性 能更好、效率更高的空间连接和查询优化方法。 哈尔滨理工大学工学硕十学位论文 1 4 本文的组织结构 本文共分为五章，各章节的内容编排如下： 第1 章首先介绍了本文的研究背景及意义，然后给出了空间数据库的发展 历程及研究现状，最后研究了空间连接和查询优化技术，总结了其研究现状。 第2 章详细阐述了空间数据库的空间对象的类型、对象间的关系及操作， 空间查询，查询优化及其技术等方面，空间数据库领域的最新研究成果，并作 了相应的分析、归纳和比较。 第3 章具体阐述了空间连接查询优化和索引技术。首先给出了空间连接查 询优化的概念，然后明确了什么是空间索引，并给出了两种常用的空间索引技 术；然后研究了基于空间索引的空间连接查询。 第4 章详细介绍了本课题的主要研究内容。首先介绍了空间连接查询的处 理体系，研究了空间连接操作算法。提出了一种新的空间对象近似方法一 3 c r s ，具体阐述了3 c r s 的特点及生成算法。 第5 章是对基于3 c r s 的空间连接算法的总体设计和性能评价。给出了基于 3 c r s 的空间连接测试算法，对此算法进行了分析，结果表明本文所提方法是 有效的。 最后总结本文完成的主要工作，并对下一步将要进行研究的工作进行展 望。 哈尔滨理t 大学工学硕十学位论文 第2 章空间数据库技术概述 第l 章主要讨论了空间数据库及其空间连接和查询优化研究技术的研究背 景、意义及本文将要研究的具体内容。本章首先明确了空间数据库的概念和研 究内容，然后对空间数据库的空间对象表达、空间数据建模、空间数据索引、 空间数据查询、空间数据库体系结构和空间数据库应用等研究方向的最新研究 进展做一具体讨论。 2 1 空间数据库概述 空间数据库是作为一种应用技术而诞生和发展起来的，其目的是为了存 储、管理和检索各种地理空间数据( 包括空间数据和非空间数据) 。它把被管 理的数据从一维推向了二维、三维甚至更高维。 空间数据库是g i s 的核心，也是最具特色的一部分，其基本功能包括两个 方面，一是对空间数据的存储，二是提供对空间数据查询的支持。空间数据库 由于其对象的特性，使其与通用的数据库技术相比有着自身的特点： 1 数据量特别大，地理系统是一个复杂的综合体，要用数据来描述各种 地理要素，尤其是要素的空问位置，其数据量往往很大。 2 空间数据模型复杂，空间数据库存储的不是单一性质的数据，而是涵 盖了几乎所有与地理相关的数据类型。 3 数据应用十分广泛，如地理研究、环境保护、土地利用与规划、道路 建设、市政管理等心副。 2 2 空间对象 2 1 1 空间数据 空间数据是指用来表示空间实体的位置、形状、大小及其分布特征等诸方 面信息的数据，它可以用来描述来自现实世界的目标。它具有定位、定性、时 问和空间关系等特性。定位是指在已知的坐标系里空间目标都具有唯一的空间 位置；定性是指有关空问目标的自然属性，它伴随着目标的地理位置；时间是 指空间目标是随时间的变化而变化；空间关系通常一般用拓扑关系表示陀引。 哈尔滨理t 大学t 学硕上学位论文 在实际应用中，空间数据也常常被称为图形数据，它包括点、线、面和体 等类型幢引。空间数据适合于描述呈二维、三维甚至更多维分布的现象，它不仅 能表示实体本身的信息，还能表示实体之间关系的信息。在g i s 应用中，一个 点可以表示一个城市，一条线可以表示一条河流或一个街道，而一个面可以表 示一片深林或一个湖泊。由这些点、线、面等构成了一个整体就可以表示真实 的地形地貌，而它们之间的位置关系就可以表示真实的实体之间的位置关系。 这样，通过将现实生活的实体抽象为一些空间的数据类型，就可以用处理空间 数据的技术来解决现实生活中很多难以解决的问题。 空间数据库处理的主要是和空间位置、空间关系有关的数据。一般来说， 数据具有选择性、可靠性、时间性、完备性、详细性和综合性。空间数据除了 具有一般数据的特征外，还具有一些区别于其他数据的特性： 1 数据量大、结构复杂、关系多样化空间对象是多种多样的，空间对 象之间的关系也是多样化的，而且与应用有关。 2 空间性空间数据描述了空间物体的位置、形态，甚至需要描述物体 的空间拓扑关系。空间性是空问数据区别于其他数据的标志特征。 3 多尺度与多态性不同的观察尺度具有不同的比例尺和不同的精度， 同一地物在不同的情况下就会有形态差异。 4 多时空性一个g i s 中的数据源既有同一时间不同空间的数据系列， 也有同一空间不同时间序列的数据。g i s 数据是包括不同时空和不同尺度数据 源的集成。 5 非结构化特征空间数据库不满足当前关系数据模型的范式要求，这 也是空间数据难以直接采用通用的关系数据库的主要原因。 6 空间关系特征空间数据除了记录空间位置分布外，还包含拓扑信 息。这些拓扑信息表达了多种空间关系。这种拓扑结构一方面方便了空间数据 的查询和空间分析，另一方面也给空间数据的一致性和完整性维护增加了复杂 度。 7 分类编码特征一般而言，每一种空问对象都有一种分类编码，而这 种分类编码往往属于囤家标准，行业标准或地区标准。每一种地物的类型在某 个g i s 这的属性项是相同的。 8 海量数据特征空间数据量数巨大的，通常称海量数据。一个城市地 理信息系统的数据量可能达几十g b ，如果考虑影像数据的存储，可能达几百 g b 。这样的数据量在城市管理和其他的数据量中是很少见的瞳引。 此外，与空间数据有关的一个重要特性是空问搜索算子中几何运算符需要 哈尔滨理t 大学工学硕十学位论文 物理层的支持。 空间数据不仅能够表示实体本身的空间位置及形态信息，而且还有表示实 体属性和空问关系( 如拓扑关系) 的信息。在空间数据中不可再分最小单元现 象称为空间实体，空间实体是对存在于这个自然世界中地理实体的抽象，主要 包括点、线、面以及实体等基本类型。在空间对象建立后，还可以进一步定义 其相互之间的关系，这种相互关系被称为“空间关系”，如可以定义点一线关 系、线一线关系、点一面关系等。因此可以说空间数据是一种可以用点、线、 面以及实体等基本空间数据结构来表示人们赖以生存的自然世界的数据。 空间数据是数字地球的基础信息，数字地球功能的绝大部分将以空间数据 为基础。随着科学和社会的发展，人们已经越来越认识到空间数据对于社会经 济的发展、人们生活水平提高的重要性，这也加快了人们获取和应用空间数据 的步伐。 2 1 2 空间数据类型 在实际应用中，空间数据也常常被称为图形数据。空间数据有以下几种类 型： 1 点例如城市。点只表示其空间位置，不表示其范围。 2 线例如河流、道路、管道、航线、等高线、等降雨量线、通信或电 力线路等。线不仅表示线上各点在空间的位置，而且还有长度，即表示它在空 间中延伸的范围。 3 面( 也称为区域)例如森林、湖泊、省市区域等面状对象。区域不 但有位置，而且有面积、周长等参数，以表示其覆盖的范围心9 。 以上述三种基本空间数据类型为基础，还可以导出下面一些空间数据类 型： 1 划分一个区域可以按其自然的、行政的或者其他特征，分成若干子 区域，这些子区域互不相交，但它们的并集覆盖该区域，则这些子区域共同构 成该区域的一个划分。国家的行政区域划分图、土地利用图等都是划分的例 子。划分可以嵌套，例如国家分成省、省分成县、县分成乡镇等。 2 网络网络是由若干点以及一些点和点之间的连线组成。公路网、河 网、电力网、电话网、交通路线图等都是网络的例子心引。 哈尔滨理工人学丁_ 学硕上学位论文 2 1 3 空间对象间的关系 空间数据带有空间坐标，它不仅能表示对象本身的空间位置及形态，而且 还包含了空间对象之间的空间关系这一信息。 空间关系是指空间对象之间的一些具有空间特性的关系。空间关系主要分 为度量、方位和拓扑等三大类关系。度量空间关系是用某种度量空间中的度量 指标来描述对象间的关系( k r e y s z i g1 9 8 7 ，r o b i n s o n e t a1 9 8 7 ) ，例如对象间的距 离；方位空间关系是用来描述对象在空间中的某种顺序的关系( k a i n z1 9 9 0 ， f r e e m a n1 9 7 5 ，h e r n a n d e z1 9 9 1 ) ，如前后、上下、左右、东西南北等；拓扑空 间关系是指拓扑变换下的拓扑不变量( e g e n h o f e r1 9 8 9 ，e g e n h o f e ra n dh e r r i n g 1 9 9 0 ) ，如空间对象的相交、重叠、包含等关系。一般说来，对象间的空间关 系与对象的维数、形态、大小及其所在空间的维数有关。各类拓扑空间关系也 存在着一定的联系。对象间空间关系的描述形式各不相同，因此对象间的空间 关系是极为复杂多样的。空间推理( s p a t i a lr e a s o n i n g ，s r ) 是指利用空间理论和 人工智能( a n i f i c i a li n t e l l i g e n c e ，a i ) 技术对空间对象进行建模、描述和表示， 并据此对空间对象间的空间关系进行定性或定量分析和处理的过程。空问关系 表示和推理的研究将有助于设计有效的空间查询和数据处理方式。目前，空问 关系的研究取得了长足的发展，涌现了大量的研究成果佟引。 2 3 空间查询 空间数据的查询实质上是按照一定条件对空间对象的空间数据和属性数据 进行查询，以形成一个新的数据子集。传统的用于关系数据库的查询方法由于 不能保持空间对象的空间近似性，而不适用于空问查询。 目前，空间数据库既不存在一种标准的空间代数，也没有一种标准的空间 查询语言，一些操作也是根据实际的应用需求提出来的。查询命令通常是用扩 展的s q l 语言来表示。这种扩展的s q l 允许用抽象的数据类型来表示空间对 象和它们相关的操作。空间数据库中的查询主要分为三类：基于空间特征的查 询、基于属性特征的查询和基于空间关系与属性特征的联合查询。 目前，大多数成熟的商品化g i s 软件的查询功能都可根据给定的空间特征 实现对空间对象的简单查询。如根据使用者确定的空间位置，查找出位于该位 置的空间对象和空间范围( 由若干个空间对象组成) 以及它们的属性，并显示 该空间对象的属性列表。这类查询一般分两步完成：首先借助于空间索引和空 哈尔滨理工大学丁学硕一 ：学位论文 间关系分析，在空间数据库中快速检索出被选空间对象，然后，根据空间对象 与属性数据的连接找到相关空间对象的属性列表。 一般来说，基于属性特征的查询主要是在属性数据库中完成的。目前大多 数g i s 的属性数据是通过关系数据库系统来管理的，因此，可以通过关系数据 库的s q l 方便地实现基于属性特征的查询。当筛选出满足属性要求的空间对 象标识后，再到空间数据库中检索空间对象。 在一次查询的结果中的空问对象既满足给定的空间关系约束又满足给定的 属性特征，这样的查询即是基于空间关系与属性的联合查询，它是前两种查询 的综合。 就目前g i s 的技术水平，比较系统地完成这三类查询任务还比较困难，有 待于空间查询语言( s p a t i a lq u e r yl a n g u a g e ) 的进一步研究与发展。相关的工作 都还处于理论发展和技术探索阶段。 空间选择也称为范围查询( r a n g es e l e c t i o n ) ，在地图上划出一个区域( 称为 查询区域) ，查询该区域内的所有空间数据。此外，也可以检索以点、线、面 为中心的一定范围内的空间数据。查询区域的形状可以是矩形或任意多边形。 例如，查找纽约市方圆1 0 英里以内的书店，该查询以一个圆形区域为查询区 域，这个圆以纽约为中心，其半径为1 0 英里。当查询区域是一个矩形时，称 这个查询为窗口查询( w i n d o wq u e r y ) ，该矩形区域被称为查询窗口( q u e r y w i n d o w ) 。空间选择在空间查询操作中最为重要，因为它不仅代表本身这类查 询，也是其他空间查询如空间连接的基础。而目前大多数文献资料中的空间选 择操作主要指的是窗口查询。 空间连接依据空间查询条件找出两个数据集中满足条件的对象对。空间连 接等价于一系列的窗口查询。对参加连接操作的两个数据集，一个可以看作是 数据集( 内层遍历集) ，另一个可以看作是查询窗口集( 外层遍历集) 。例如， 判断两张地图上的空间对象是否相交，可在过滤步骤中将其中一张地图上的 m b r 作为查询窗口( 一个对象m b r 作为一个查询窗口) 在另一张地图上做空 间选择操作，经过求精步骤的几何计算后，对所有的结果取并集，从而得到查 询结果。 空间查询条件由空间谓词来描述。空间谓词刻画了空间对象之间的关系， 它的确立和空间关系的表示与推理密切相关。随着空间关系理论研究的深入， 空间谓词能更好、更准确地表达人们的查询要求。例如：“查找某个城市里的 所有公园 ，空间谓词为“包含( c o n t a i n s ) ”；“查找所有穿过某片森林的铁路 ， 空间谓词为“相交( i n t e r s e c t s ) ”。此外，还有以下的空间谓词： 哈尔滨理工大学t 学硕一嶙位论文 1 n o r t h w e s t ( 西北) 2 d i s t a n c e ( 距离) 3 e n c l o s e db y ( c o n t a i n e d ，被包含) 4 a d j a c e n t ( 邻接) 5 m e e t s ( 接触) 6 o v e r l a p ( 交叠) 因为空间数据结构复杂并具有多维性，所以在空间查询中判断空间数据是 否满足空间查询条件是一个复杂的问题( 例如，空问对象是否与查询窗口相交 要涉及复杂几何计算) 。 2 3 1 空间查询方式 由于空间对象及其之间的关系非常复杂且数据量大，因此，各种空间操作 不仅计算量巨大，而且涉及复杂且代价高昂的几何操作。在空间查询操作中， 常用的有：精确匹配查询、点查询、窗口查询、域查询、空间连接查询、拓扑 查询、相邻查询和最近邻查询。下面分别介绍这些查询方式乜引： 精确匹配查询( e x a c tm a t c hq u e r y ) ：找出所有和空间查询对象0 7 具有完全 相同空间内容( 即空间属性) 的空问数据对象，即e m q ( o ) = oo g = o g ( g e 8 ，e 8ed 为d 维的欧几里德空间) 。 点查询( p o i n tq u e r y ) - 给定一个查询点p ，找出所有包含它的空间对象， 最| n n q ( 0 7 ) = oo o ：d i s t ( o g ，o g ) d i s t ( 0 7 g ，o o g ) ， p q ( p ) = opno g = p ( p e 4 ) 。 考虑下面一个查询：“找出包含址b 的河流冲积平原 ，址b 是点类型的常 量，城市在空间数据库中就可以被抽象成一个点类型常量。 开窗查询( w i n d o wq u e r yo rr a n g eq u e r y ) ：找出和d 维查询窗口1 8 有至少 一个公共点的空间数据对象，即w q ( 1 8 ) = o1 4n 0 g o ) 。 相交查询，区域查询或重叠查询( i n t e r s e c t i o nq u e r y r e g i o nq u e r y o v e r l a p q u e r y ) ：找出所有和查询对象o 有至少一个公共点的空间数据对象，即 i q ( 0 7 ) = o l o g n o g 矽) 。 包含查询( e n c l o s eq u e r y ) ：找出所有包含查询对象o 的空间数据对象，即 e q ( o ) = oio gno g = o g ) 。 被包含查询( c o n t a i n m e n tq u e r y ) ：找出所有被查询对象0 包含的空间数据 对象，即c q ( o ) = oo gno g = o g 。 哈尔滨理工大学t 学硕士学位论文 相邻查询( a d j a c e n c yq u e r y ) ：找出所有和查询对象o 相邻的空间数据对 象。如果两个对象有共同边界没有相互包含，那么称这两个对象相邻。即 a q ( 0 ) = olo gn o - g 1 2 ia0