（计算机软件与理论专业论文）空间数据库中的选择性估计方法研究.pdf

摘要 摘要 空间查询及优化是空间数据库相关技术研究的难点和突破点，选择性 估计技术已经成为空间查询及优化领域的热点课题。目前选择性估计还处 于起步阶段，各方面的技术还不成熟，存在一定的缺陷。本文对空间数据 库的选择性估计技术进行了综合分析，在此基础上提出了新的选择性估计 方法，具体内容如下。 首先，利用空间对象的m b r 缓冲区，根据数据集在空间连接时的特 点和线段集的分布规律，给出了线段缓冲区，关键点和点缓冲区的概念， 在此基础上提出了一种基于线段缓冲区和点缓冲区的选择性估计方法，用 于线段集的距离连接选择性估计，而且通过重建点缓冲区还可以实现对特 征线段集的估计。 其次，对运动对象窗口查询的选择性估计技术进行了研究，给出了空 间密度，空间斜率和桶的定义，提出了一种对空间划分的桶分层的估计方 法，并把这种方法推广到多维空间。 最后，对上述方法进行了实验验证，通过分析实验结果发现，基于点 缓冲区的选择性估计方法可以适用于特征线段集的选择性估计。对桶进行 分层的选择性估计方法也可以明显减少运动对象的窗口查询的选择性估计 误差。 关键词选择性估计；点缓冲区；线段缓冲区；空间密度；桶 燕山大学工学硕士学位论文 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 r 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 f s e l e c t i v i t ye s t i m a t i o n h a sb e c o m eah o ts u b j e c to fs p a t i a l q u e r ya n do p t i m i z a t i o n n o w , t h e t e c h n o l o g yo fs e l e c t i v i t ye s t i m a t i o ni 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 l a s p e c t sa r 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 e t e c h n o l o g i e so fs e l e e t i v i t ye s t i m a t i o na r 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 en e w s e l e c t i v i t ye s t i m a t i o nm 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 l c o n t e n t sa r ca sf o l l o w s f i r s t l y , u s i n gt h em b r b u f f e rb i e ra n dl i n es e g m e n tb u f f e ra r e ao fs p a t i a l o b j e c t , a c c o r d i n gt ot h ed a t as e t sc h a r a c t e r i s t i ci ns p a t i a lj o i na n dd i s t r i b u t e d l a wo fc h a r a c t e r i s t i cd a t a , l i n es e g m e n tb u f f e ra r e a , k e yp o i n ta n dp o i n tb u f f e r b i e ad e f i n i t i o ni sg i v e n p u t t i n gf o r w a r das e l e c t i v i t ye s t i m a t i o nm e t h o db a s e d o nl i n es e g m e n tb u f f e rb i e aa n dp o i mb u f f e ra r e a , w h i c ha r eu s e di ns p a t i a l j o i n s e l e c t i v i t y e s t i m a t i o no fl i n e s e g m e n ts e t , a n dc a l l u s ei ne s t i m a t i o no f c h a r a c t e r i s t i cl i n es e g m e n ts e tb yr e b u i l d i n gt h ep o i n tb u f f e r 揶e 乱 s e c o n d l y , t h et e c h n o l o g yo fw i n d o wq u e r ts e l e c t i v i t ye s t i m a t i o na b o u t m o v i n go b j e c t si ss t u d i e d t h ed e f i n i t i o n so fs p a t i a ld e n s i t y , s p a t i a ls k e wa n d b u c k e ta l ep r e s e n t e d , a n dt h e np u t t i n gf o r w a r das e l e c t i v i t ye s t i m a t i o nm e t h o d b yd i v i d i n gt h eb u c k e tg e n e r a t e db ys p a c ep a r t i t i o ni n t os o m el a y e r s ，a n de x t e n d t h em e t h o dt os e l e c t i v i t ye s t i m a t i o no f m u l t i - d i m e n s i o n a ls p a c e s 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 b ya n a l y i n gt h e r e s u l t s ，w ef o u n dt h a tt h es e l e c t i v i t ye s t i m a t i o nm e t h o db a s e do np o i mb u f f e r b i g ac a l lb e9 0 0 di nu s eo ft h es p a t i a lj o i ns e l e c t i v i t ye s t i m a t i o no f 一 c h a r a c t e r i s t i c l i n es e g m e n ts e t t h e s e l e c t i v i t ye s t i m a t i o nm e t h o dt h r o u g h d i v i d i n gt h eb u c k e ti n t ol a y e r sc a nd e c r e a s et h er e l a t i v ef i l l o rd e a r l yw h e n a b s t r a c t m o v i n go b j e c t s sw i n d o wq u e r yi se s t i m a t i n g k e y w o r d ss e l e c t i v i t ye s t i m a t i o n ；p o i n tb u f f e ra r e a ；l i n es e g m e n tb u f f e ra r e a ； s p a t i a ld e n s i t y ；b u c k e t h i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文空间数据库中的选择性 估计方法研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立 进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人 和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承 担。 作者签字自锰 isi剪l：日年3聊elel e l ：纠年3 黟f 燕山大学硕士学位论文使用授权书 空间数据库中的选择性估计方法研究系本人在燕山大学攻读硕士 学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大 学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人 完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有 关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权 燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文 的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 ，一，t 不保密b ( 请在以上相应方框内打“”) 作者签名。喃锰 导师签名：疹i l l i e i 期：稚了月刃日期：枷年j 月日 e l 期：z 司年3 月司e l期：驯年月叫 第1 章绪论 1 1 研究背景 第1 章绪论 人类正处在一个信息变革的时代，数据作为推动这场革命的原料通过 传感器和其它数据采集设备源源不断地收集起来。在这些数据中，有一类 数据与空间位置有关一空间数据。它们是与二维、三维或更高维空间的 空间坐标或空间范围相关的数据，代表数量庞大的空间实体，从简单的位 置( 例如饭店或者旅馆的坐标) 到有复杂外形的物体( 例如河流或者城市等) 。 和普通数据比较，空间数据包含许多几何特征，不仅包括描述空间位置和 形状的坐标信息，而且包括描述空间关系的拓扑关系。其中，地理信息系 统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 ) 的研究辅以信息科学以及高效的信 息技术手段，使人们对空间数据的研究达到了前所未有的高度【1 2 1 。地理信 息管理是与人类生存、发展、进步密切相关的一门信息科学与技术，是地 球空间信息科学的重要组成部分，是信息产业发展的重要支柱，它被广泛 应用于国民经济的很多部门，如城市规划与设计、资源环境管理、生态环 境监测与保护、地质勘探测量、城市管网配电网、灾害监测防治等多个应 用领域。 地理信息系统起源于北美，世界上第一个投入运行的地理信息系统是 在1 9 6 3 年加拿大土地调查局为了处理大量的土地调查资料，经由测量学家 r e t o m i n s o n 提出并建立的。虽然人们很早就用计算机技术管理空间地理 数据，但直到1 9 8 1 年e s r i 公司推出地理信息产品a r c i n f o ，才真正将 空间地理数据表示技术与关系数据库数据表示技术集成在一起，其中空间 地理数据存储于专用文件结构中并与数据库管理系统中的非空间数据相连 接。这种解决方案存在很多缺点，其中最重要的就是缺乏对多用户及数据 共享和交互问题的支持。为了解决这一问题人们引入了空间数据库管理系 统( s p a t i a ld a t a b a s em a n a g e m e n ts y s t e m ，s d b m s ) 。 燕山大学工学硕士学位论文 s d b m s 是描述、存储和处理空间数据及其属性数据的数据库系统。 空间数据库是随着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 世纪，使用数据库管理包括地图及其属性的空间数据，成为空 间数据库应用系统发展的潮流。与传统文件方式相比，空间数据库技术有 明显的技术优势，包括海量数据管理能力、图形和属性数据一体化存储、 多用户并发访问、完善的访问权限控制和数据安全机制等。空间数据库技 术正在逐步取代传统文件，成为越来越多的大中型空间数据库应用系统的 空间数据存储和查询的解决方案。 近些年来，随着地理信息系统、计算机辅助设计、多媒体系统、医学 或卫星图象数据处理等领域的发展，空间数据库以及对空间数据进行查询 的研究倍受关注。由于空间数据量庞大，数据结构复杂，操作代价昂贵， 因此空间查询优化及处理势必成为空间应用的难点和突破点。s d b m s 提 供了便于分析空间数据的机制，可以根据需求方便地处理空间数据和空间 查询。将空间数据和其它形式的数据区别对待的概念，已经逐渐渗透到所 有主要的数据库厂商的考虑和计划之中。在市场上出现了专门的空间产品， 用来提高d b m s 的空间处理能力。 空间数据的一个特点是数据量大，一个对地观测系统每天收集的数据 超过i t b ，再加上空间数据本身的复杂性造成的查询复杂，结果是与传统 数据库相比，空间数据的处理是一项空间和时间开销更大的操作。关系数 据库技术的一项主要优势是通过产生一个完善的查询评估计划来高效地执 行查询，提高数据处理的效率。在数据处理更复杂的s d b m s 中，完善合 理的查询评估系统对提高数据处理效率有更重要的意义。 选择性估计是设计空间数据库的查询优化器的关键步骤，选择性估计 能以非常小的代价估计出空间算子的近似结果集的大小，d b m s 可以依据 2 第1 章绪论 得到的结果进行查询优化，找到最佳的查询顺序。为了设计更好的查询优 化器，就需要寻找优秀的选择性估计方法。 1 2 研究现状 由于选择性估计技术有着重要的理论研究价值和实际应用价值，所以 一直是相关领域专家们的研究重点。对空间算子的选择性估计研究从上世 纪九十年代开始，主要可以分为基于空间划分【3 】和基于某种分布定律的技 术。目前，已经有几种估计方法被提出。下面分别介绍国内外的研究成果。 s w a m p a c h a r y a 等人1 9 9 9 年利用了划分空间的概念，利用量化的空间 密度1 4 】划分空间，用m i n s k e w 方法将空间划分为着干小空间，以小空间上 均匀假设取代全局进行均匀分布假设，可以得到比较准确的效果，但它没 有考虑对象的规模和复杂度。 c h r i s t o sf a l o u t s o s 等人2 0 0 0 年针对实际空间数据库中的对象集的分布 特点，提出了幂律规则【5 1 ，认为空间对象集像自然界中许多物体一样具有 自相似性，可以利用相关分形维度上的幂率实现选择性估计计算，适用于 静态自然分布的数据点集估计。y u f e it a o 等人2 0 0 5 年又将幂律方法推广 到数据集分布不均匀的估计中嘲。 y o n g - j i nc h o i 等人2 0 0 2 年针对运动对象的选择性估计【7 一，提出了速 度边界矩形【9 】，根据空间对象集的边界移动速度生成边界矩形，按照局部 速度分布一致的思想建立直方图，并每隔一定时间对数据对象采样并重建 直方图。这种方法考虑了运动物体的速度对估计的影响，但是存在估计结 果随着时间推移误差不断变大的缺点。 i a r i o $ h a d j i d e r h e r i o u 等人2 0 0 3 年将空间时间表示法【1 0 ，1 1 l 转换为 速度空间表示法【l “，利用m i n s k c w 算法划分空间，得到的直方图随 空间对象位置的变化而更新，并在直方图更新次数超过某阈值时重建直方 图。这种方法减少了系统开销，也减缓了随着时间的推移估计的准确度下 降的问题。h i c h a m 等人2 0 0 5 年提出一种时间空间直方图【1 3 】，改进了 直方图的更新开销。 3 燕山大学工学硕士学位论文 j i m e n gs u n 等人2 0 0 5 年放弃了关于一定范围内物体速度分布均匀的 假设，设计了一个包含空间对象位置【1 4 1 和速度信息的四维直方图协】，在空 问的划分上同时考虑了位置和速度的分布问题，因此得到分布更加均匀的 各个区域。这种方法在一定程度上平衡了速度和空间位置的关系，适合自 由空间中速度变化不大的空间对象的估计，但它不适用于对非自由空间内 的对象进行估计【1 6 ”7 1 。 y u f e i t a o 等人2 0 0 5 年提出了一种针对不均匀分布数据集的选择性估 计方法【1 8 1 ，它对数据集采样进行精确查询计算，再放大采样结果得到估计 值，可以解决复杂分布数据对象的选择性估计。 x i o n gw e i 等人2 0 0 6 年提出了一种基于最小边界矩形( m i n i m a l b o u n d i n gr e c t a n g l e ，m b r ) 缓冲区【1 9 】的估计方法，它把相交连接技术应用 在通过闵柯夫斯基和扩展的m b r 上面，只需要几个较少的直方图统计量 就能得到结果。这种方法需要的计算代价小，适合在假设数据空间局部均 匀分布的前提下使用。它没有考虑数据集的分布特征和数据对象间的相互 关系。 1 3 研究内容 课题的研究内容是如何实现对空间数据库中空间数据查询操作的结果 集的估计，主要包括以下两个方面：一方面是对已知数据集，能够按照查 询要求和数据分布特征，使估计值和真值之间尽可能符合，从而达到一致 性。另一方面是根据数据库查询优化器的要求，使选择性估计方法适应多 种类的数据分布特征，提高其应用范围。通过对现有的选择性技术进行了 分析比较的基础上，对现有方法的不足进行了补充，并提出了本文的观点， 主要分为以下两个方面。 第一，点线距离连接选择性估计。数据集的分布特征关系到查询估计 值的准确程度，研究空间划分方法把不同分布差异的数据集分开。根据现 有的m b r 缓冲区的概念，研究线段缓冲区。m b r 缓冲区估计应用在线段 的选择性估中带来很大误差，线段缓冲区的建立可以减少m b r 空间带来 4 第1 章绪论 的距离连接估计值的误差；通过分析线段对象之间的关系，研究基于点缓 冲区的选择性估计方法，将数据线段集的扩展点缓冲区重复区域合并，从 而减少了结果的估计值，降低计算误差，提高了估计的准确程度。 第二，运动对象窗口查询的选择性估计。可以从空间均衡性的角度对 运动对象划分，研究运动点的划分并计算相关数据集的估计值。对于线性 运动和速度已知的空间点集，可以通过对桶分层将运动状态相似的点集分 类，利用分层计算相交范围的方法进行选择性估计，减少运动物体的速度 对估计结果的影响。 1 4 研究意义 选择性估计技术的研究在数据库领域具有着很深远的影响和巨大的作 用，对空间数据库优化技术有着重要的研究意义。下面就从两个方面来简 要阐述。 空间信息随着i t 技术的发展在各个领域中应用的比例越来越大，范围 越来越广。这些数据量巨大、结构复杂多样的信息如果不经过优化就进行 处理的话，会浪费大量的时间和精力，并会随着数据的迸一步增大而变得 难以处理和维护。选择性估计满足优化空间信息、提高查询效率的要求， 避免上述结果的发生。准确的估计结果集的大小可以用于优化复杂的查询。 由于空间操作高昂的空间消耗和i o 代价，采用比较好的选择性估计技术 能够以非常小的计算代价给出空间操作结果集的大小的近似估计，根据简 单的运算得到的估计值就可以在查询优化器中构造出好的查询计划，减少 实际查询时的无效开销，数据库管理系统会依据得到的计划进行查询优化， 找出最佳的查询顺序，尽量减少操作代价，提高处理效率，使空间查询操 作变得更方便快捷。 在对空间数据库的数据进行信息统计的应用中，用户需要得到“有多 少”而不是“是什么”的查询占有很大一部分，此时对空间数据库的查询 操作仅仅要求得到查询的结果数据集的大小，而以找到精确查询对象为目 标的各种查询方法在这种情况下就失去了意义，因为用户需要花费很长时 5 燕山大学工学硕士学位论文 问等待系统的计算结果，然后再统计结果之和，大量时间被浪费在没有必 要的精确计算上面。这时候，选择性估计就成为处理这种查询最有效的办 法，它使用了一些系统开销低的方法，避免了精确的查询运算，在短时间 内得到计算结果，既避免了大时间进行的没有意义的空间运算，又在更短 的时间得到用户所需数据。 在空间数据库的移动领域中，对未来一段时间的信息统计的应用会越 来越广泛，交通控制和调度系统需要掌握未来时间的车辆分布状况，随时 根据收集的信息控制交通运行的畅通。移动设备服务提供商可以根据统计 的空间数据在合适的地点建立服务网点。这些应用都要求选择性估计提供 支持。 本文提出的点线距离连接选择性估计技术的解决方法可以看作是现有 的估计方法的发展，这项研究成果指出了更适合点线距离连接选择性的估 计方法，不仅适用于非特征线段集的连接，而且适用于特征线段集的连接； 所提出的针对运动对象窗口查询的选择性估计研究能够解决速度对估计结 果影响的问题，分析了运动对象相互间的联系并给出准确的选择性估计结 果集。 1 5 本文组织结构 本文总体上分为5 章，从第2 章开始具体布局如下。 第2 章主要介绍了空间查询技术的基础知识。对空间数据、空间索引 和空间查询的相关知识进行了简要介绍。 第3 章主要研究了点线距离连接的选择性估计技术。定义了线段缓冲 区，关键点和点缓冲区的概念，并提出了基于线段缓冲区的点线距离连接 选择性估计技术的计算方法，给出了用于计算重复缓冲区的关键点插入算 法和窗口划分算法，给出了该计算方法在数据集线段为特征数据条件下的 计算方法。 第4 章主要研究了运动对象窗口查询选择性估计技术。首先定义了空 间密度，空间斜率和桶的概念，然后提出了在一维条件下运动点集窗口查 6 第1 章绪论 询的分层算法，用于对不同状态的运动点进行空间划分。给出了选择性估 计方法及计算公式，并把这种计算方法推广到不同距离定义下的多维空间。 第5 章主要是对前面2 章所提出的选择性估计方法进行了实验验证， 并在实验的基础上分析了实验结果。 最后，总结了本文的工作并提出了下一步设想。 7 燕山大学工学硕士学位论文 2 1引言 第2 章基础知识 空间数据的查询和检索是空间数据库中使用最频繁的功能之一。由于 空间对象的表达形式复杂且数据量大，各种空间操作不仅计算量巨大，而 且涉及复杂且高代价的几何操作。遍历检查对象集合中每个对象是否满足 查询要求，需要大量的磁盘存取操作和复杂的几何计算。如果能在各种查 询操作之前对操作对象进行过滤，则可大大减少参加空间查询操作的空间 对象数量，从而缩短计算时间，提高查询的效率，空间索引就是为此而设 计的，因此空间数据的查询操作一般都是基于某种空间索引机制。 2 2 空间数据 空间数据是指用来表示空间实体的位置、形状、大小及其分布特征等 诸多方面信息的数据，它可以用来描述来自现实世界的目标。 空间数据库处理的主要是和空间位置、空间关系有关的数据。一般来 说，数据具有选择性、可靠性、时间性、完备性、详细性和综合性。空间 数据除了具有一般数据的特征外，还具有一些区别于其他数据的特性。 ( 1 ) 数据量大、结构复杂、关系多样化空间对象是多种多样的，空间 对象之间的关系也是多样化的，而且与应用有关。 ( 2 ) 空间性空间数据描述了空间物体的位置、形态，甚至需要描述物 体的空间拓扑关系。空间性是空间数据区别于其他数据的标志特征。 ( 3 ) 多尺度与多态性不同的观察尺度具有不同的比例尺和不同的精 度，同一地物在不同的情况下就会有形态差异。 ( 4 ) 多时空性一个g i s 中的数据源既有同一时间不同空间的数据系 列，也有同一空间不同时间序列的数据。g i s 数据是包括不同时空和不同 第2 章基础知识 尺度数据源的集成。 ( 5 ) 查询过程复杂空间数据一般按空间特征和空间关系查询。由于空 间对象的形状常常不规则，验证查询条件比较复杂。 ( 6 ) 难以定义多维空间对象的空间次序为了加快数据检索而建立空 间索引是首先必须解决的难题。 此外，与空间数据有关的一个重要特性是空间搜索算子中几何运算符 需要物理层的支持。 空间数据适用于描述所有呈二维、三维甚至多维分布的关于区域的现 象，空间数据不仅能够表示实体本身的空间位置及形态信息，而且还有表 示实体属性和空间关系( 如拓扑关系) 的信息。在空间数据中不可再分最小 单元现象称为空间实体，空间实体是对存在于这个自然世界中地理实体的 抽象，主要包括点、线、面以及实体等基本类型。在空间对象建立后，还 可以进一步定义其相互之间的关系，这种相互关系被称为“空间关系”，如 可以定义点一线关系、线一线关系、点一面关系等。因此可以说空间数据 是一种可以用点、线、面以及实体等基本空间数据结构来表示人们赖以生 存的自然世界的数据。 空间数据是数字地球的基础信息，数字地球功能的绝大部分将以空间 数据为基础。随着科学和社会的发展，人们已经越来越认识到空间数据对 于社会经济的发展、人们生活水平提高的重要性，这也加快了人们获取和 应用空间数据的步伐。 2 3 空间索引 空间索引1 2 雌l 】是指存储空间数据时依照空间对象的位置和形状或空间 对象之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空 间对象的概要信息，如对象的标识、外接矩形及指向空间对象的指针。空 间索引是对存储在介质上的数据位置信息的描述，作为一种辅助性的空间 数据结构。空间索引介于空间操作算法和空间对象之间，通过筛选，大量 与特定空间操作无关的空间对象被排除，从而提高空间操作的效率。 9 燕山大学工学硕士学位论文 海量空间数据管理使得索引机制显得尤为重要，为了提高对空间数据 的处理效率，必须引入合适的索引技术。至今为止，人们提出的空间索引 结构种类繁多。可以按其支持的空间对象类型来进行分类。比如，对点对 象进行支持的空间索引结构有网格文件田】，对空间区域对象( 包括线对象和 面对象) 进行支持的空间索引结构有四叉树】。但从设计上讲，人们探索新 的索引结构主要有两个思路。 ( 1 ) 分区的方法将空间划分成很多小的分区。 ( 2 ) 基于空间对象的最小边界矩形二维以上空间对象称之为包络体， 空问对象的边界矩形能够粗略反映出空间对象的空间特性，从而加速空间 对象的定位过程。 2 3 1 空间索引的分类 目前，已经研究出许多高效的空间索引方法 2 4 , 2 5 1 ，大致分为如下四类， 其中主流方法都是采用树索引结构。 ( 1 ) 基于二叉树的索引技术基于二叉树索引结构的典型范例包括k d 树阴、m k d 树【2 7 】、s k d 树口8 l 等。这种索引结构的典型k d 树是一种二分 索引树结构，主要用于索引多维数据点，但对复杂的空间目标的索引必须 采用近似方法和空间映射技术。因此针对空间关系的查询效率非常低，索 引树非常庞大，需要存储在外存的缺点，同时为了能够索引复杂的空间目 标，提出了适合索引二维空间目标的基于实体标志重复存储技术的m k d 树。s l e d ) 树的提出避免了空间目标的重复存储和空间映射，用空间目标的 中心点来对空间目标集进行二分索引。但是所有这些方法对非点状空间目 标的索引效率都较低。 ( 2 ) 基于b 树的索引技术b 树及其变体【2 9 j ，被广泛应用于常规的数据 库管理系统之中，实践证明其对大型数据库的索引具有出色表现。目前的 空间数据索引技术，很多都基于b 树，如r 树【3 0 】。从r 树的结构上可以 看出，让空间上靠近的空间对象拥有尽可能近的共同祖先，能提高r 树的 查询效率。但是怎样衡量空间对象的聚集，是一个非常复杂的问题。由于 衡量的方法不同，也产生了众多的r 树的变体，如r + 树【3 “、l h 树【3 2 1 、t p r l o 第2 章基础知识 树【3 3 】、即r + 树】、h i l b e r tr 树和r 1 i n k 树 3 6 1 等等。 ( 3 ) 基于哈希的网格技术这种基于哈希方法 3 7 1 的基本思路是将索引 空间划分为相等或者不相等的一些小方网格，与每个网格相关联的空间目 标存储在同一磁盘页上，而网格的访问地址则可以直接通过求数组下标或 应用某种算法得到，常见的方法有网格文件等，这类方法主要适用于索引 多维空间点。 ( 4 ) 空间目标排序法这种方法的基本思想是将索引空间划分为许多 小的格子，然后对每个格子指定一个唯一的数字或编码，空间目标用与其 相交的一个或多个格子的数字来表示，或者用与其相交格子的编码求得的 另一个唯一的编码来表示。这种方法的实质是将多维空间的实体映射到一 维空间，然后采用一维的数值对多维的空间目标进行排序，常见的方法四 又树 2 3 , 3 射、z 序口9 】等。 2 3 2r 树 g u t t m a n 受到b + 树 4 0 l 的启发，1 9 8 4 年在文献f 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 t 2 ) ，除非它是根结 点。 ( 2 ) 一个叶结点上的每条索引记录了( i ，元组标识符) ，i 是最小边界矩 形，在空间上包含了所指元组表达的k 维数据对象。 ( 3 ) 每个非叶结点都有m 至m 个子结点，除非它是根结点。 ( 4 ) 对于非叶结点中的每个条目( i ，子结点指针) ，i 是在空间上包含其 子结点中矩形的最小边界矩形。 ( 5 ) 根结点至少有两个子结点，除非它是叶结点。 ( 6 ) 所有叶结点出现在同一层。 ( 7 ) 所有m b r 的边与一个全局坐标系的轴平行。 燕山大学工学硕士学位论文 以上是r 树区别于其它索引结构的特性，下面通过一个例子来分析。 图2 - 1 是在二维空间中的一组空间对象( m b r ) 。 f i g u r e2 - 1t h es 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 中用阴影标出。 图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 树的优点是它按数据来组织 第2 章基础知识 索引结构，具有很强的灵活性和可调节性，即无须预知整个空间对象所在 的空间范围，就能建立空间索引。由于它具有与b 树相似的结构和特性， 使其能很好的与传统的关系型数据库相融合。 2 4 空间查询 查询与检索是空间数据库的最基本的操作，也是g i s 空间分析的功能 之一，常用的空间查询操作主要有两大类：空间选取与空间连接。 2 4 1 空间选取 空间数据查询的结果通常是满足查询性质的空间对象的集合。应用在 空间数据库上的空间选取查询操作主要有八种，复杂空间查询大多在这八 种查询的基础上进行的。下面简要介绍一下。 ( 1 ) 精确匹配查询找出所有和空间查询对象o 具有完全相同空间内容 ( 即空间属性) 的空间对象。 ( 2 ) 点查询找出所有和查询点p 重叠的空间对象。 ( 3 ) 包含查询找到所有包含查询对象。的空间数据对象。 ( 4 ) 相交查询、区域查询或者重叠查询找出所有和查询对象。有至少 一个公共点的空间数据对象。 ( 5 ) 窗口查询或者范围查询找出和d 维查询窗口w 有至少一个公共点 的空间数据对象。 ( 6 ) 被包含查询找出所有被查询对象o 包含的空间数据对象。 ( 7 ) 相邻查询找出所有和查询对象o 相邻的空间数据对象。如果两个 对象有共同的边界并且没有互相包含，那么称这两个对象相邻。 ( 8 ) 晟近邻查询找出所有和查询对象0 具有最小距离的空间数据h 3 】 对象，通常以两者最近点【4 4 6 1 的距离作为空间对象间的距离1 4 7 9 1 。 2 4 2 空间连接 空间连接的定义为：给定两个空间对象集合r 和s ，以及空间谓词【5 0 1 ， 1 3 燕山大学1 二学硕士学位论文 找出所有空间对象对( o ，o ) r x s ，使该对象对满足关系0 。对于空间谓词0 可以有多种形式，如相交( i n t e r s e c t ) 、包含( c o n t a i n ) 、被包含( i s _ e n c l o s e d _ b 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 m e 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 本章小结 本章对空间数据的定义和特点作了简单的叙述，并介绍了空间索引和 空间查询的分类及相关技术，为本课题理论的提出奠定了基础。空间数据 的索引对于空间查询操作有着非常重要的作用。索引结构的好坏可以对空 1 4 第2 章基础知识 间查询效率有着很大的影响。目前人们已经提出了许多空间索引结构，各 种索引各有各的优缺点和适用范围。但是，最广泛应用的是r 树。这是由 于r 树的查询效率高，且适用范围广，并支持高维的空间对象。 燕山大学工学硕士学位论文 第3 章点线距离连接选择性估计 3 1 引言 选择性估计是设计空间数据库的查询优化器的关键步骤。选择性估计 能以非常小的代价估计出空间算子的近似结果集的大小。根据估计值就可 以在查询优化器中构造出好的查询计划，尽量减少空间连接时系统的操作 代价。 衡量选择性估计技术性能的标准主要有两个方面。 ( 1 ) 正确性选择性估计的结果要能够反映符合查询条件的数据集的 大概结论。 ( 2 ) 适应性选择性估计方法要能够适应因为空间数据情况复杂造成 的空间数据集特点的变化，使针对不同特点数据集的估计保持稳定的估计 结果。 距离连接选择性估计是选择性估计当中重要的一种，点线距离连接作 为一种重要的空间连接又有其自身的特点，现有的各种方法都分别存在一 定的缺陷，并不能完全满足上述标准，本课题研究的选择性估计技术将以 上述评价标准为目标，判断其各方面的性能。根据点线距离连接的特征， 下面具体介绍本课题研究的可以应用于点线距离连接的选择性估计方法的 研究。 3 2 基本定义 本节将分别对点线距离连接选择性估计方法中所需要用到的定义进行 解释说明。 定义3 1 ：选择性估计。空间算子的选择性估计为空间查询的求解结 果集的大小x 与全部结果集大小y 的比值。对空间算子的选择性进行的估 1 6 第3 章点线距离连接选择性估计 算属于选择性估计，实际中最常见的是下面两种选择性： ( 1 ) 范围查询选择性( r a n g es e a r c hs e l e c t i v i t y ) 给定查询点q 和半径r ， 寻找对象o ( o 为被查询数据集s 中的任意对象1 ，则： x = n u m o l d i s t a n c e ( o ，们r y = n u m d lo es ) s e l b s = x y ( 2 ) 距离连接选择。眭( d i s t a n c ej o i ns e l e c t i v i t y ) 给定连接距离距离d ，集 合a 和b ，数据对 ，则： x = n u m i o = ea a n d0 2 eba n dd i s t a n c e ( o l ，d 2 ) d ) y = n u m o l 0 2 1 0 t e a a n dd 2 b s e l d j 2 x | y 范围查询又称作窗口查询，是空间查询中的一种重要空间操作，窗口 可以是矩形，圆形或空间内的任意指定区域；距离连接是按照指定连接距 离对不同数据集之间的空间对象进行关联的空间操作，当连接距离为零时， 距离连接就变为相交连接。 定义3 2 ：线段缓冲区。给定空间线段集s 和选择性估计要求的连接 距离r ，对线段l ( 1 s ) 按照m b r 缓冲区的方法扩展得到的区域为线段l 的 线段缓冲区，该缓冲区满足：缓冲区内的任意点与线段l 的距离d r ；与 线段l 的距离d r 的点全部在缓冲区以内。 定义3 3 ：关键点。给定空间线段集s 和选择性估计要求的连接距离r ， 从线段的任意一个端点开始以长度为2 r 的距离在线段上截取点，截取的点 作为一个关键点和下一次截取的初始点，重复上述操作直到下一次截取的 点落入线段之外为止。最后再加上线段的另一个端点作为一个关键点。假 设线段长度l ，关键点的截取次数为n ，则应该满足：n ( 2 r ) l n ( 2 r 十1 ) 。 定义3 4 ；点缓冲区。给定空间线段集s ，选择性估计要求的连接距离 r 和空间线段集s 的关键点集k ，通过遍历集合k 而得到的以关键点f ( f k ) 为圆心，r 为半径的缓冲区称为点f 的点缓冲区。与m b r 缓冲区的圆角矩 形不同，点缓冲区都是圆形的缓冲区。 简单地说，关键点是参与选择性估计的空间线段根据选择性估计的连 燕山大学工学硕士学位论文 接距离而得到的采样点，点缓冲区是依照采样点而得到的和关键点一一对 应的圆型扩展缓冲区。 本文通过实例来解释说明关键点和点缓冲区的概念。图3 1 显示了二 维空间线段集s 的缓冲区扩展情况。 图3 - 1 线段关键点和点缓冲区 f i g u r e3 - 1k e y p o i n ta n d p o i n t b u f f e r a r e a o f l i n es e g m e n t 图3 - 1 中的线段a d ，线段e f ，线段g i 是参与点线距离连接选择性估 计的线段集中的3 条线段，已知需要进行选择性估计的距离连接的连接距 离长度为r ，图中最右边的线段的长度为l ，并且知道l 的长度恰好为4 r 。对 于线段g i 来说，g ，h 和i 三个点是它的关键点，阴影区域是关键点的扩 展点缓冲区，对于线段g i 来说，其关键点的扩展点缓冲区域是圆g ，圆h 和圆l 三个点缓冲区。从图中可以看出，线段a d 和e g 的扩展缓冲区的 重叠区域在变换为点缓冲区后转化为点缓冲区e 和点缓冲区b ，c 的重叠 区域。 3 3 线段集的采样 如果线段集组成的是具有实际意义的特征数据，就不能把线段视为单 独的对象，而需要考虑参与选择性估计的特征数据线段集的扩展缓冲区应 当剔除线段集中重复的区域，本文通过对特征线段集上的点进行采样重建 缓冲区，剔除线段集中重复的区域，从而使估计结果仍然正确有效，采样 点就是关键点。下面将通过i n s e r tk e y p o i n t 算法来实现对特征线段集的采 第3 章点线距离连接选择性估计 样处理。 3 3 1 符号和函数 算法说明和分析中用到的符号表示如下。 ( d s 表示空间数据线段集： ( 2 ) n 表示关键点的截取次数； ( 3 ) m 表示空间线段集s 中线段的个数； ( 4 ) p r e c 表示计算下一个关键点的当前点； ( 5 ) 表示空间线段集s 中线段i 的长度； ( 6 ) r 表示选择性估计的距离连接的连接距离； ( 7 ) k p 表示关键点结果集。 算法说明和分析中用到的函数表示如下。 d i s t a n c e p ，g ) 表示计算线段上与q 距离