（计算机应用技术专业论文）空间数据库中轮廓查询技术的研究.pdf

摘要 摘要 空间查询及优化是空间数据库相关技术研究的难点和突破点，轮廓查 询技术已经成为空间查询及优化领域的热点课题。目前轮廓查询技术还处 于起步阶段，各方面的技术还不成熟，存在一定的缺陷。本文对轮廓和轮 廓体的查询及更新技术进行了综合分析，在此基础上提出了新的查询和更 新处理方法，具体内容如下。 首先，对轮廓查询技术进彳亍了研究，提出并证明了修剪空间定理，给 出有效区的形式化定义，在此基础上提出了基于动态窗口查询的轮廓查询 算法，对算法的正确性进行了证明，并通过实例对算法进行了分析说明。 其次，对轮廓更新技术进行了研究，给出了查询区和空白区的定义， 提出并证明了添加数据点轮廓更新判定定理和删除数据点轮廓更新判定定 理，在此基础上提出了a d d p o i n _ t _ s k y l i n e 算法和d e l e t c p o i n t _ _ s k y l i n e 算法， 并对算法的正确性进行了证明，对时间复杂度进行了计算。 再次，对轮廓体更新技术进行了研究，提出并证明了不同值定理，根 据该定理设置了不同值条件，在此基础上提出了a d d p o i n t算法和_skycube d e l e t e p o i n ts k y c u b e 算法，并对算法的正确性进行了证明，对时间复杂度 进行了计算。 然后，对数据流中轮廓体查询技术进行了研究，提出并证明了单点定 理，给出了数据流中轮廓体查询框架，对其各模块的功能及算法进行了分 析说明，并对算法的正确性和时间复杂度分别进行了证明和计算。 最后，对上述算法进行了实验验证，通过分析实验结果发现，轮廓查 询算法无需访阀整个数据集就能渐进地返回完整的轮廓结果，更薪算法能 够准确地完成轮廓和轮廓体的更新操作，数据流中轮廓体的查询框架能够 快速追踪轮廓体的变化，并实时更新轮廓体，且保证查询结果准确有效。 关键词轮廓；轮廓体；支配；有效区；支配区 燕山大学工学硕士学位论文 a b s t r a c t s p a t i a lq u e r ya n do p t i m i z a t i o na l ed i f f i c u l tp o i n t sa n db r e a k t h r o u g ho f t h e r e l a t e dt e c h n o l o g i e si ns p a t i a ld a t a b a s e ，t h et e c h n o l o g yo fs k y l i n eq u e r yh a s b e c o m eah o ts u b j e c to f s p a t i a lq u e r ya n do p t i m i z a t i o n n o w , t h et e c h n o l o g yo f s k y l i n eq u e r yi ss t i l la tt h ei n i t i a ls t a g e ，a n dt h et e c h n i c a la s p e c t sa l en o tm a t u r e ， w h i c hs t i l lh a ss o m es h o r t c o m i n g s i nt h i sp a p e r , t h eq u e r ya n du p d a t i n g t e c h n o l o g i e so fs k y l i n ea n ds k y c u b ea l ea n a l y z e ds y n t h e t i c a l l y , a n ds o m ed e w m e t h o d sa l ep r o p o s e db a s e do nt h e s e ，t h em a t e r i a lc o n t e n t sa l ea sf o l l o w s f i r s t l y , t h et e c h n o l o g yo fs k y l i n eq u e r y i ss t u d i e d t h ep r u n i n gs p a c e t h e o r e mi sp r e s e n t e da n dd e m o n s t r a t e d ，a n dt h ef o r m a ld e f i n i t i o ni sg i v e n b a s e do nt h e s e ，t h ea l g o r i t h mf o rs k y l i n eq u e r yb a s e d0 1 1d y n a m i cw i n d o w q u e r yi sp r o p o s e d i na d d i t i o n , t h ec o r r e c t n e s so f t h ea l g o r i t h mi sp r o v e da n d a n a l y z e dt h r o u g he x a m p l e s s e c o n d l y , t h et e c h n o l o g yo fs k y l i n eu p d a t i n gi ss t u d i e d t h ed e f i n i t i o n so f q u e r yr e g i o na n db l a n kr e g i o na l ep r e s e n t e d ，a n dt h e nt h es k y l i n eu p d a t i n g d e t e r m i n a n tt h e o r e m so fi n s e r t i n ga n dd e l e t i n gp o i ma l ep r e s e n t e da n d d e m o n s t r a t e d b a s e do nt h e s e ，t h ea d d p o i n ts k y l i n ea l g o r i t h ma n d d e l e t e p o i n t _ s k y l i n ea l g o r i t h ma l ep r o p o s e d i na d d i t i o n , t h ec o r r e c t u e s si s p r o v e d ，a n dt h et i m ec o m p l e x i t yi sc o m p u t e d t h i r d l y , t h et e c h n o l o g yo fs k y c u b eu p d a t i n gi ss t u d i e d t h ed i s t i n c tv a l u e t h e o r e mi sp r e s e n t e da n dd e m o n s t r a t e d , a c c o r d i n gt ot h i st h e o r e m ，t h ed i s t i n c t v a l u ec o n d i t i o ni sc o n f i g e d b a s e do nt h e s e ，t h ea d d p o i n t _ s k y c u b ea l g o r i t h m a n dd e l e t e p o i n t _ s k ) 7 c u b ea l g o r i t h ma r ep r o p o s e d , t h e nt h ec o l - r e c t n e s si s p r o v e d ，a n dt h e t i m ec o m p l e x i t yi sc o m p u t e d f o u r t h l y , t h et e c h n o l o g yo fs k y c u b eq u e r yi nd a t as t r e a me n v i r o n m e n ti s s t u d i e d t h es i n g l ep o i n tt h e o r e mi sp r e s e n t e da n dd e m o n s t r a t e d , b a s e do nt h i s ， a b s t r a c t t h ea r c h i t e c t u r eo fs k y c u b ei nt h es t r e a me n v i r o n m e n ti sp r o p o s e d , a n dt h e n e v e r ym o d u l ea n d i t sa l g o r i t h ma r ea n a l y z e di nd e t a i l i na d d i t i o n , t h e c o r r e c t n e s so fe v e r ya l g o r i t h mi sp r o v e d ，a n dt h et i m ec o m p l e x i t yi sc o m p u t e d f i n a l l y , t h ea l g o r i t h m si nt h i sp a p e ra r ev a l i d a t e d n l ea l g o r i t h mf o r s k y l i n eq u e r yb a s e do nd y n a m i cw i n d o wq u e r yc a nr e t u r nt h ew h o l es k y l i n e r e s u l tp r o g r e s s i v e l ya n di ti sn o tn e s s a r yt oa c c e s st h ew h o l eq u e r ys p a c e ，t h e u p d a t i n ga l g o r i t h m sc a l lq u i c k l ya n de x a c t l yc o m p l e t et h eu p d a t i n go p e r a t o r so f s k y l i n ea n ds k y c u b e ，a n dt h ea r c h i t e c t u r eo fs k y c u b ei nt h es t r e a me n v i r o n m e n t c a l l q u i c k l y t r a c k s k y c u b ec h a n g e s ，g u a r a n t e e t h e u p d a t i n g o fs k y c u b e r e a l - t i m ea n dt h er e s u l t sa r ee x a c ta n de f f e c t i v e k c y w o r d ss k y l i n e ；s k y c u b e ；d o m i n a t e ；v a l i dr e g i o n ；d o m i n a n c er e g i o n l l i 燕山大学硕士学位论文原刨性声明 本人郑重声明：此处所提交的硕士学位论文空间数据库中轮廓查询技 术的研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行 研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已 发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体， 均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字：言t l ，欠 日期：知。6 年尹月2 6 日 燕山大学硕士学位论文使用授权书 空间数据库中轮廓查询技术的研究系本人在燕山大学攻读硕士学位 期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所 有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了 解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送 交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学， 可以采用影印、缩印或其它复制手段保存论文，可以公布论文的全部或部分 内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密回。 ( 请在以上相应方框内打“4 ”) 作者签名：吉t l 冗欠 日期：卫年尹月彳日 导师签名。o , 1 1日期。砷年7 月彩日 第1 章绪论 1 1 研究背景 第1 章绪论 人类在2 l 世纪将全面进入信息时代，在信息技术蓬勃发展的今天，有 关地球科学和地理信息管理方面的问题引起了大量学者的关注，地理信息 系统g i s ( 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 ) 的研究辅以信息科学以及高效的 信息技术手段，使地理信息系统的发展达到了一种前所未有的高度【l ，2 】。地 理信息管理是与人类生存、发展、进步密切相关的一门信息科学与技术， 是地球空间信息科学的重要组成部分，是信息产业发展的重要支柱，它被 广泛应用于国民经济的很多部门，如城市规划与设计、资源环境管理、生 态环境监测与保护、地质勘探测量、城市管网配电网、灾害监测防治等多 个领域。 地理信息系统起源于北美，世界上第一个投入运行的地理信息系统是 在1 9 6 3 年加拿大土地调查局为了处理大量的土地调查资料，经由测量学家 r f t o m i n s o n 提出并建立的。虽然人们很早就用计算机技术管理空间地理 数据，但直到1 9 8 1 年e s r i 公司推出地理信息产品a r c i n f o ，才真正将 空间地理数据表示技术与关系数据库数据表示技术集成在一起，其中，空 间地理数据存储于专用文件结构中，并与数据库管理系统中的非空间数据 相连接。这种解决方案存在很多缺点，最主要的就是缺乏对多用户及数据 共享和交互问题的支持。为了解决该问题，人们引入了空间数据库系统。 空间数据库是随着g i s 的开发和应用而不断发展起来的数据库新技 术。空间数据库系统是用来描述、存储和处理空间数据及其属性数据的数 据库系统。该系统并不是独立存在的系统，它与应用紧密结合，通常是g i s 的核心。 空间数据库是近年的热点研究领域，是一门非常前沿的交叉学科，它 在地理信息系统、计算机辅助设计c a d ( c o m p u t e ra i d e dd e s i g n ) 、多媒体 燕山大学工学硕士学位论文 信息系统m m i s ( 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 ) 及数据仓库d w h ( d a t a w a r eh o u s e ) 技术等诸多应用领域中都起着非常重要的作用。 跨入2 1 世纪，使用数据库管理包括地图及其属性的空间数据，成为空 间数据库应用系统发展的潮流。与传统文件方式相比，空间数据库技术有 明显的技术优势，包括海量数据管理能力、图形和属性数据一体化存储、 多用户并发访问、完善的访问权限控制和数据安全机制等。空间数据库技 术正在逐步取代传统文件，成为越来越多的大中型空间数据库应用系统的 空间数据存储和查询的解决方案。 近些年来，随着地理信息系统、计算机辅助设计、多媒体系统、医学 或卫星图象数据处理等领域的发展，空间数据库以及对空间数据进行查询 的研究倍受关注。由于空间数据量庞大，数据结构复杂，操作代价昂贵， 空间查询优化及处理势必成为空间应用的难点和突破点。 2 0 0 1 年，“轮廓”这个概念在文献【3 】中首次被提出来，它是作为一个 操作被提出来的。为了提高轮廓查询的渐进性、在线处理等能力，相应的 研究机构投入了大量的人力和物力来从事该领域的研究。轮廓的查询优化 及处理在许多数据库应用中都起着非常重要的作用，成为空间查询研究中 的难点和热点。轮廓查询技术的研究也促进着相关技术的发展和研究，如 多目标优化、最大矢量i 州、等高线【”等问题。 1 2 研究现状 由于轮廓查询技术有着重要的理论研究价值和实际应用价值，所以一 直是相关领域专家们的研究重点。目前，已经有多种轮廓查询方法被提出。 下面分别介绍国内外的研究成果。 2 0 0 1 年i c d e ( i n t e r n a t i o n a lc o n f e r e n c eo nd a t ae n g i n e e r i n g ) 会议上， b o r z s o n y i 等人提出分治轮廓查询方法d & c t 3 1 ( d i v i d e a n d - c o n q u e r ) ，该方 法将数据集划分成多个分区，然后利用主存算法来分别计算每个分区内的 局部轮廓，最终的轮廓通过将局部轮廓筛选合并获得。该方法仅对小数据 集有效，因为如果整个数据集符合内存大小，那么仅需要应用一次主存轮 2 第1 章绪论 廓算法即可。对于大数据集，分区的过程就需要至少一次读和写整个数据 集，因此导致严重的i 0 代价。这种方法不适合在线处理，因为它不能在 分区阶段完成之前返回任何轮廓点。 计算轮廓的一个直接方法就是将每个数据点p 与其他的每个数据点进 行比较，如果点p 不被支配，那么它就是轮廓的一部分。2 0 0 1 年i c d e 会 议上，b o r 7 _ s o n y i 等人提出块嵌套循环轮廓查询方法b n l l 3 1 ( b l o c kn e s t e d l o o p ) ，这种方法就是基于这个思想扫描数据文件，在主存中保存一个轮廓 点的候选列表，开始的时候列表中包含第一个数据点，之后每个数据点p 都通过支配定义来判断该点是否是轮廓点。b n l 的一个问题就是列表可能 变得比主存还要大，当这种情况发生时，所有溢出的数据点都被添加到一 个临时文件中，这就需要多次执行b n l 。b n l 的优点就是它广泛的应用性， 因为它无需索引或将数据文件排序就可以应用到任意维上。b n l 的主要问 题就是对主存的依赖和在渐进处理方面存在缺陷。 2 0 0 1 年v l d b ( v e r yl a r g ed a t ab a s e s ) 会议上，k i a n l e et a n 等人提出位图 轮廓查询方法l s l ( b i 廿i l a p ) ，将所有的信息在位图中编码来确定一个点是否在 轮廓上。位图法的效率依赖于位图操作的速度。这个轮廓的计算是昂贵的， 因为对于每一个要检测的数据点，必须检索所有点的位图来得到对应位。 如果不同值的数目非常的大，那么空间代价可能会很高，而且这种方法不 适合动态数据集。 2 0 0 1 年v l d b 会议上，k i a n l e et a n 等人提出了索引轮廓查询方法【s 1 ( i n d e x ) ，它把d 维的点集分成d 个列表，如果在第i 轴上的坐标在所有维 上是最小的，也就是说，对于所有j i 存在p i p j ，那么将点p = ( p i ，p 2 ，p d ) 放到第i 个列表中( 1 i 蜘) 。这种方法能够快速返回列表前端的轮廓点，但 是返回轮廓点的顺序是固定的，不支持用户定义的优先选择标准。 2 0 0 2 年v l d b 会议上，d o n a l dk o s s m a n n 等人提出最近邻轮廓查询方 法n n 9 ( n e a r e s tn e i g h b o r ) ，它利用最近邻查询的结果来递归划分数据空 间，分别求得轮廓。最近邻方法的查询速度比前几种方法都快，但是对于 高维数据来说，该方法存在严重的空间重合问题。 2 0 0 3 年i c d e 会议上，c h o m i c k i 等人提出了b n l 的改进方法排 燕山大学工学硕士学位论文 序过滤轮廓查询方法s f s t l 0 ( s o r tf i l t e rs k y l i n e ) ，根据一个优先选择函数首 先对整个数据集进行排序，候选点按照分值以升序插入到列表中，因为具 有低分值的点可能支配大量的点，这样使得修剪更有效。s f s 展现出渐进 的特点，因为数据的预排序能够确保支配点p 的点p 必须在p 之前被访问， 因此能够立即将插入到列表中的点作为轮廓点进行输出。然而s f s 不得不 扫描整个数据文件才能返回一个完整的轮廓。 2 0 0 5 年t o d s ( t r a n s a c t i o n so nd a t a b a s es y s t e m s ) & ，d i m i t r i sp a p a d i a s 等人提出分支限界轮廓查询方法b b s 【l l , 1 2 1 ( b r a n c ha n db o u n ds k y l i n e ) ，它与 前面的最近邻轮廓查询方法类似，采用分支限界矩形图，通过深度优先遍 历算法【1 3 1 来进行轮廓查询，该方法没有考虑到用户后期筛选计算的方便 性，缺少一定的实际应用性，不能很好的满足用户的需求。 2 0 0 5 年v l d b 会议上，y i d o n gy u a n 等人提出轮廓体查询方法【1 4 l ，它将 单个轮廓问题加深为多个轮廓查询的复杂问题，首次提出了轮廓体的概念， 并提出了轮廓体的求解方法，但是没有提出数据集更新时轮廓体更新的解 决方法。 以上的方法都是根据轮廓的基本定义而提出的单纯计算轮廓的方法， 还有其他几种针对特殊环境和数据的轮廓查询的变体，它们根据轮廓的一 些特性，分别提出新的概念和新的思想，如大数据集的密集轮廓挖掘【”1 、 数据流中的滑动窗口轮廓查询【1 6 1 、获得轮廓最佳视图的方法【1 7 】、半序域的 轮廓查询方法f l s 】，k - 支配轮廓求解方法【伸1 。下面分别介绍一下。 2 0 0 4 年p k d d ( p r i n c i p l e sa n dp r a c t i c eo fk n o w l e d g ed i s c o v e r yi nd a t a - b a s e s ) 会议上，w e nj i n 等人提出大数据集的密集轮廓挖掘方法，它在轮廓 对象与其近邻的距离约束的基础上提出密集轮廓的概念，并分别采用采样 修剪法、索引评估法和基于微簇的方法来查找大数据集中的密集轮廓。密 集轮廓及其挖掘方法不仅扩展了数据库查询中的轮廓操作，而且为数据挖 掘工作提供了一个有意义的模式。 2 0 0 5 年i c d e 会议上，x u e m i nl i n 等人提出数据流环境中轮廓的计算 方法，它只需考虑一个覆盖所有最近元组的滑动窗口来进行查询处理，连 续地监控新出现的数据，并且保持轮廓的不断更新，利用数据流的轮廓属 4 第1 章绪论 性来提高时间复杂度和空间复杂度。 2 0 0 5 年v l d b 会议上，j i a np e i 等人提出基于决策予空间的获得轮廓 最佳视图的方法，该方法通过研究轮廓的语义将整个空间轮廓计算扩展到 子空间轮廓计算，并提出s k y e y 算法来计算轮廓组的集合和在每个子空间 轮廓上的对象集合。 2 0 0 5 年i c d e 会议上，c h e e y o n gc h a n 等人提出半序域的轮廓查询计 算方法。以前的相关工作都是全有序域内的轮廓计算方法，而该方法主要 是针对部分有序属性域的轮廓查询计算和评价问题提出了解决方法，对每 个半序属性应用一个近似的区间表示( 整数属性对) ，产生一个有效的且合 理的近似域映射，将查询空间进行转化，在转化后的空间内采用现有的索 引技术组织转化后的属性来计算轮廓。 2 0 0 6 年s i g m o d ( s p e c i a li n t e r e s tg r o u po l lm a n a g e m e n to fd a m ) 会议 上，c h e e y o n gc h a n 等人给出k 支配轮廓的定义，证明了k _ 支配轮廓的多个 性质，并提出一次扫描算法、二次扫描算法和排序检索算法来求解k - 支配 轮廓。 1 3 研究内容 本文在对现有的轮廓查询技术进行了分析比较的基础上，对现有方法 的不足进行了补充，并提出了本文的观点，主要分为以下四个方面。 ( 1 ) 轮廓查询技术针对现有轮廓查询算法在渐进性、在线处理和实际 应用性方面存在的缺陷，本文从一个全新的角度，给出基于动态窗口查询 的轮廓查询技术，不用访问整个数据空间就能返回完整的轮廓结果，并顺 序输出结果，且保证结果的正确性和完整性。 ( 2 ) 轮廓更新技术针对空间数据集中数据点的两种更新情况( 添加数 据点和删除数据点) ，分别给出并证明轮廓更新的判定定理，并在此基础上 提出轮廓的更新方法。 ( 3 ) 轮廓体更新技术当空间数据集中数据点更新时，单纯地通过轮廓 更新计算是非常复杂和困难的，而现有技术都不能很好地解决轮廓体的更 燕山大学工学硕士学位论文 新问题，本文给出轮廓体的更新方法。 ( 4 ) 数据流中轮廓体查询技术数据流环境中的数据是连续到达和终 止的动态数据，现有针对静态数据的算法不能应用到数据流环境中，针对 该问题，给出具体的数据流环境中轮廓体查询方法。 1 4 研究意义 空间数据库中查询优化技术的研究，特别是轮廓查询技术的研究在空 间数据库领域具有深远的影响和巨大的作用。近些年来，轮廓操作和轮廓 计算越来越受到人们的重视，这主要是由于轮廓在多种实际应用中起到非 常重要的作用，如多标准决策脚、数据挖掘和可视化【1 6 1 、用户偏好查询2 0 】 等等。 数据库管理系统在决策支持的应用中越来越多，这些应用有以下四个 特点。 第一，查询通常是基于多个目标，且这些目标有时是冲突的。例如， 在旅行中有很多的旅馆，根据它们的价格和离我们的距离决定哪一个适合 我们。有离当前位置近的和远的旅馆，可能离的近一些的旅馆价格高，离 的远一些的价格低。 第二，与传统的应用不同，该结果不是单个的最优结果( 或结果集) 。 在上面旅行的例子中，不可能只存在一个价格低且距离市中心又近的旅馆。 第三，由于第二点，用户通常查找令他们满意的结果。 第四，对于相同的查询，不同的用户根据他们个人的偏好可能找到不 同的结果。有的用户可能愿意多花费一些钱选择距离市里近一些的旅馆， 而有的用户愿意住稍微便宜一些的旅馆，只要去市里方便一些就行。 综上可知，对于数据库管理系统来说，通过提供所有满足用户条件的 结果来满足用户的需求是非常重要的。轮廓查询可以根据用户的偏好通过 对数据点进行筛选来得到最佳的候选集，这个最佳候选集是满足用户条件 的最佳结果，用户可以根据自己的实际情况再作出相应的选择。 轮廓查询技术在现实生活中都是很常见的问题，轮廓计算是解决空间 6 第1 章绪论 数据库领域内类似问题的一种新的而且是非常重要的方法。 本文的研究成果指出了现有轮廓查询技术的不足之处，并从一个全新 的角度给出了轮廓查询方法、轮廓更新方法、轮廓体更新方法以及数据流 环境中轮廓体查询方法。本文所提出的基于动态窗口查询的轮廓查询技术 能够渐进地顺序输出结果，为后期数据选择带来极大的方便。本文所提出 的轮廓更新技术可以自动的完成数据集更新时轮廓的相应更新，有着很好 的应用前景。本文所提出的轮廓体更新技术能够简单地完成对多个轮廓的 更新，减少了计算量和复杂度。本文所提出的数据流中轮廓体查询技术能 够快速追踪轮廓体的变化，保证轮廓体的实时更新，且保证查询结果准确 有效。 1 5 本文组织结构 本文总体上分为7 章，从第2 章开始具体布局如下。 第2 章主要介绍了空间查询技术的基础知识。对空间数据、空间索引 和空间查询的相关知识进行了简要介绍。 第3 章主要研究了基于动态查询窗口的轮廓查询技术。首先，给出并 证明了修剪空间定理，定义有效区的概念，在此基础上提出了基于动态窗 口查询的轮廓查询技术的基本思想，并给出了具体算法；然后，对算法的 正确性进行证明；最后，通过实例对算法进行分析说明。 第4 章主要研究了轮廓更新技术。首先，给出并证明了添加和删除数 据点时轮廓更新的判定定理；然后，针对添加和删除数据点这两种情况给 出了轮廓更新算法，并对算法的正确性进行了证明，对时间复杂度进行了 计算。 第5 章主要研究了轮廓体更新技术。首先，介绍了自底向上的方式和 共享结果的策略以及不同值定理；然后，针对添加和删除数据点这两种情 况给出了轮廓体更新算法，并对算法的正确性进行了证明，对时间复杂度 进行了计算。 第6 章主要研究了数据流环境中轮廓体查询技术。首先，给出了数据 7 燕山大学工学硕士学位论文 流环境中轮廓体查询的基本框架；然后，给出了单点定理；最后，对各个 模块的功能、处理过程及算法进行详细介绍。 第7 章主要是对本文所提出的算法进行了实验验证，并在实验的基础 上分析了实验结果。 最后，总结了本文的工作并提出了下一步设想。 第2 章基础知识 2 1引言 第2 章基础知识 空间数据的查询和检索是空间数据库中使用最频繁的功能之一【2 l l 。由 于空间对象的表达形式复杂且数据量大，各种空间操作不仅计算量巨大， 而且涉及复杂且高代价的几何操作。遍历检查对象集合中每个对象是否满 足查询要求，需要大量的磁盘存取操作和复杂的几何计算。如果能在各种 查询操作之前对操作对象进行过滤，则可大大减少参加空间查询操作的空 间对象数量，从而缩短计算时间，提高查询的效率，空间索引就是为此而 设计的，因此，空间数据的查询操作一般都是基于某种空间索引机制。 2 2 空间数据 空间数据是指用来表示空间实体的位置、形状、大小及其分布特征等 诸多方面信息的数据，它可以用来描述来自现实世界的目标。 空间数据库处理的主要是和空间位置、空间关系有关的数据。一般来 说，数据具有选择性、可靠性、时间性、完备性、详细性和综合性。空间 数据除了具有一般数据的特征外，还具有一些区别于其他数据的特性1 2 2 1 。 ( 1 ) 数据量大、结构复杂、关系多样化空间对象是多种多样的，空间 对象之问的关系也是多样化的，而且与应用有关。 ( 2 ) 空间性空间数据描述了空间对象的位置、形态，甚至需要描述空 间对象的空间拓扑关系。空间性是空间数据区别于其他数据的标志特征。 ( 3 ) 多尺度与多态性不同的观察尺度具有不同的比例尺和不同的精 度，同一空间对象在不同的情况下就会有形态差异。 ( 4 ) 多时空性空间数据源既有同一时间不同空间的数据系列，也有同 一空间不同时间序列的数据。空间数据是包括不同时空和不同尺度数据源 9 燕山大学工学硕士学位论文 的集成。 ( 5 ) 查询过程复杂空间数据一般按空间特征和空间关系查询。由于空 间对象的形状常常不规则，验证查询条件比较复杂。 ( 6 ) 难以定义多维空间对象的空间次序为了加快数据检索而建立空 间索引是首先必须解决的难题。 此外，与空间数据有关的一个重要特性是空间搜索算子中几何运算符 需要物理层的支持。 空间数据适用于描述所有呈二维、三维甚至多维分布的关于区域的现 象，空间数据不仅能够表示实体本身的空间位置及形态信息，而且还有表 示实体属性和空间关系( 如拓扑关系) 的信息。在空问数据中不可再分最小 单元现象称为空间实体，空间实体是对存在于这个自然世界中地理实体的 抽象，主要包括点、线、面以及实体等基本类型。在空间对象建立后，还 可以进一步定义其相互之间的关系，这种相互关系被称为“空间关系”，如 可以定义点一线关系、线一线关系、点一面关系等。因此可以说空间数据 是一种可以用点、线、面以及实体等基本空间数据结构来表示人们赖以生 存的自然世界的数据。 空间数据是数字地球的基础信息，数字地球功能的绝大部分将以空间 数据为基础。随着科学和社会的发展，人们已经越来越认识到空间数据对 于社会经济的发展、人们生活水平提高的重要性，这也加快了人们获取和 应用空间数据的步伐。 2 3 空间索弓 空间索引1 2 3 ，2 4 】是指存储空间数据时依照空间对象的位置和形状或空间 对象之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空 间对象的概要信息，如对象的标识、外接矩形及指向空间对象的指针。空 间索引是对存储在介质上的数据位置信息的描述，作为一种辅助性的空间 数据结构。空间索引介于空间操作算法和空间对象之间，通过筛选，大量 与特定空间操作无关的空间对象被排除，从而提高空间操作的效率。 l o 第2 章基础知识 海量空间数据管理使得索引机制显得尤为重要，为了提高对空间数据 的处理效率，必须引入合适的索引技术。至今为止，人们提出的空间索引 结构种类繁多，可以按其支持的空间对象类型来进行分类。比如，对点对 象进行支持的空间索引结构有网格文件1 2 5 1 ，对空间区域对象( 包括线对象和 面对象) 进行支持的空间索引结构有四叉树 2 6 】。但从设计上讲，人们探索新 的索引结构主要有两个思路。 ( 1 ) 分区的方法将空间划分成很多小的分区。 ( 2 ) 基于空间对象的最小边界矩形二维以上空间对象称之为包络体， 空间对象的边界矩形能够粗略反映出空间对象的空间特性，从而加速空间 对象的定位过程。 2 3 1 空间索引的分类 目前，已经研究出许多高效的空间索引方法2 7 0 引，大致分为如下四类， 其中主流方法都是采用树索引结构。 ( 1 ) 基于二叉树的索引技术基于二叉树索引结构的典型范例包括k d 树1 2 9 、m k d 树3 0 1 、s k d 树【3 j 】等。这种索引结构的典型k d 树是一种二分索 引树结构，主要用于索引多维数据点，但对复杂的空间目标的索引必须采 用近似方法和空间映射技术。因此针对空间关系的查询效率非常低，索引 树非常庞大，需要存储在外存的缺点，同时为了能够索引复杂的空间目标， 提出了适合索引二维空间目标的基于实体标志重复存储技术的m k d 树。 s k d 树的提出避免了空间目标的重复存储和空间映射，用空间目标的中心 点来对空间目标集进行二分索引。但是所有这些方法对非点状空间目标的 索引效率都较低。 ( 2 ) 基于b 树的索引技术b 树及其变体1 3 2 1 ，被广泛应用于常规的数据 库管理系统之中，实践证明其对大型数据库的索引具有出色表现。目前的 空间数据索引技术，很多都基于b 树，如r 树 3 3 】。从r 树的结构上可以看出， 让空间上靠近的空间对象拥有尽可能近的共同祖先，能提高r 树的查询效 率。但是怎样衡量空间对象的聚集，是一个非常复杂的问题。由于衡量的 方法不同，也产生了众多的r 树的变体，如r + 树 3 4 1 、r + 树【3 5 1 、t p r 树1 3 6 、 燕山大学工学硕士学位论文 t p r * 树【3 7 1 、h i l b e r tr 树【3 s 】和r 1 i n k 树1 3 9 1 等等。 ( 3 ) 基于哈希的网格技术这种基于哈希方法f 4 0 】的基本思路是将索引 空间划分为相等或者不相等的些小方网格，与每个网格相关联的空间目 标存储在同一磁盘页上，而网格的访问地址则可以直接通过求数组下标或 应用某种算法得到，常见的方法有网格文件等，这类方法主要适用于索引 多维空间点。 ( 4 ) 空间目标排序法这种方法的基本思想是将索引空间划分为许多 小的格子，然后对每个格子指定一个唯一的数字或编码，空间目标用与其 相交的一个或多个格子的数字来表示，或者用与其相交格子的编码求得的 另一个唯一的编码来表示。这种方法的实质是将多维空间的实体映射到一 维空间，然后采用一维的数值对多维的空间目标进行排序，常见的方法有 四叉树【2 6 , 4 ”、z 序f 4 2 1 等。 2 3 2r 树 g u t t m a n 受到b + 树1 4 3 1 的启发，1 9 8 4 年在文献f 3 3 】中创造性地提出了r 树。 r 树是目前应用最广泛的一种空间索引结构，其实际是对b + 树的扩充，因 而它不仅具有b + 树特有的动态平衡性( 所有叶结点都在同一层上) ，而且能 进行多维索引。r 树中用对象的最小边界矩形m b r ( m i n i m u mb o u n d i n g r e c t a n g l e ) 来表示对象。r 树有如下七条特性。 ( 1 ) 每个叶结点包含m 至m 条索引记录( 其 m s m 2 ) ，除非它是根结点。 ( 2 ) 一个叶结点上的每条索引记录7 ( 1 ，元组标识符) ，i 是最小边界矩形， 在空问上包含了所指元组表达的k 维数据对象。 ( 3 ) 每个非叶结点都有m 至m 个子结点，除非它是根结点。 ( 4 ) 对于非叶结点中的每个条目( i ，子结点指针) ，i 是在空间上包含其子 结点中矩形的最小边界矩形。 ( 5 ) 根结点至少有两个子结点，除非它是叶结点。 ( 6 ) 所有叶结点出现在同一层。 ( 7 ) 所有m b r 的边与一个全局坐标系的轴平行。 以上是r 树区别于其他索引结构的特性，下面通过一个例子来分析。 第2 章基础知识 图2 1 是在二维空阃中的一组空间对象( m b r ) 。 f i g u r e2 - 1s e to f s p a t i a lo b j e c t s 图2 2 是对应图2 1 中一组m b r 的r 树。树中叶结点上的对象在图 2 1 中用阴影标出。 1 6 图2 - 2r 树 f i g u r e2 - 2r - t r e e 考虑搜索图2 - 2 中与矩形5 交叠的对象。根结点中的项x 与矩形5 交 叠，搜索沿着r 树的这一分支继续。在x 中，项b 和c 与矩形5 交叠，因 而继续搜索。最后矩形4 、5 和6 确定为与查询矩形5 交叠的叶结点项。 由于r 树是一棵平衡树，在与插入对象对应的叶结点已满的情况下， 插入操作可能会导致结点向根部分裂。虽然叶面分裂算法非常复杂，但是 r 树已经在许多商用数据库系统中实现了。r 树的优点是它按数据来组织索 引结构，具有很强的灵活性和可调节性，即无须预知整个空间对象所在的 茎当奎芏三兰堡主堂垡笙苎 空间范围，就能建立空间索引。由于它具有与b 树相似的结构和特性，使 其能很好的与传统的关系型数据库相融合。 2 4 空间查询 查询与检索是空间数据库的最基本的操作，也是g i s 空间分析的功能 之一，常用的空间查询操作主要有两大类：空间选取和空间结合。 2 4 1 空间选取 空间数据查询的结果通常是满足查询性质的空间对象的集合。应用在 空间数据库上的空间选取查询操作主要如下八种，复杂空间查询大多在这 八种查询的基础上进行的。 ( 1 ) 精确匹配查询找出所有和空间查询对象o 具有完全相同空间内容 ( 即空间属性) 的空间对象。 f 2 ) 点查询找出所有和查询点p 重叠的空间对象。 ( 3 ) 包含查询找到所有包含查询对象o 的空间数据对象。 ( 4 ) 相交查询、区域查询或者重叠查询找出所有和查询对象o 有至少 一个公共点的空间数据对象。 ( 5 ) 窗口查询或者范围查询找出和d 维查询窗d w 有至少一个公共点 的空间数据对象。 ( 6 ) 被包含查询找出所有被查询对象o 包含的空间数据对象。 ( 7 ) 相邻查询找出所有和查询对象o 相邻的空间数据对象。如果两个 对象有共同的边界并且没有互相包含，那么称这两个对象相邻。 ( 8 ) 最近邻查询找出所有和查询对象o 具有最小距离的空间数据对 象，通常以两者最近点的距离作为空间对象间的距离似矧。 2 4 2 空间结合 空间结合是给定两个空间对象集合r 和s ，以及空间谓词【5 3 】，找出所 有空间对象对( o ，0 3 e r x s ，使该对象对满足关系0 。对于空间谓词0 可以有 1 4 第2 章基础知识 多种形式，如相交( i n t e r s e c 0 、包含( c o n t a i n ) 、被包含( i se n c l o s e db y ) 等等。 其中最常用的是相交，相交运算符也是最重要的空间谓词。对于诸如包含、 被包含、相邻等谓词，相交结合是一个有效的过滤器，通过相交结合可产 生比笛卡尔积r x s 要小很多的查询候选集合。 m b r 空间结合是经常使用的结合方法，其中心思想是如果两个空间对 象的m b r 不相交，那么它们所包含的空间对象也不相交。使用该性质，通 过检查空间对象m b r 的相交情况，即可过滤要进行空间结合查询操作的空 间对象对。 空间结合的查询过程可概括为以下三个关键步骤。 首先，计算两个空间对象集的m b r 结合，并用简单的几何过滤去判别 明确不相交的空间对象对( 不命中) 和相交的空间对象对( 命中) ，从而减少进 一步处理的空间候选集，这一过程可以通过高效的空间存取方法来实现。 其次，在需要进一步处理的空间对象对中，为了识别不符合要求的对 象，采用精确的凸起多边形近似法计算候选集的每个对象，同时进行新一 轮的相交检查。例如，通过对每个候选空间对象对最小内接矩形 m e r ( m a x i m u me n c l o s e dr e c t a n g l e ) 的相交检查，过滤出符合查询条件的空 间对象集。对象的m e r 指的是空间对象的空间范围所能包含的最大d 维矩 形。如果两个对象的m e r 相交，则对象肯定相交。 最后，剩下的候选集就需要使用更加复杂的几何处理( 如空间对象分解) 去找出符合查询条件的空间对象集。在整个查询过程中，空间对象经历了3 次几何精化操作。 2 5 本章小结 本章对空间数据的定义和特点作了简单的叙述，并介绍了空间索引和 空间查询的分类及相关技术，为本课题理论的提出奠定了基础。 与一般的数据库系统相比，空间数据库系统中空间对象的表达形式复 杂，数据量大，各种空间操作不仅计算量巨大，而且大多具有面向邻域的 特点。如果能在各种查询操作之前对操作对象进行过滤，则可大大减少参 燕山大学工学硕士学位论文 加空间查询操作的空间对象数量，从而缩短计算时间，提高查询的效率。 因此，空间索引对于空间查询操作有着非常重要的作用。空间索引结构的 好坏直接影响空间查询效率。