（计算机软件与理论专业论文）一种改进的空间连接代价模型.pdf

哈尔滨t 程大学硕士学位论文 摘要 由于空间数据的数据量庞大、多维、缺乏全序关系，使得空间数据查询 的效率成为了空间数据库性能的瓶颈，空间查询优化势必成为空闻数据库应 用的难点和突破点。查询代价模型是空间查询优化的主要技术之一，在各种 各样的查询之中，空间连接查询是空间数据库应用的一个基础性的而且代价 离昂的操作，因此空间连接查询的代价评估对于空间优化策略有着重要的意 义。 本文从研究空间索引和空间查询等基础技术知识入手，深入研究了 y a n n i s t h e o d o r i d i s 等人提出的基于r - t r e e 的空间连接代价模型。对该模型中 获得数据实际密度的抽样算法进行了深入的分析，提出将随机数表抽样算法 应用于空间连接代份模型中，并给出了相应的计算公式；本文对非均匀分布 的整体数据空间按一定原则划分子空间并抽样获取实际密度：对于连接查询 中每一个查询窗口的实际密度，本文给出了一套计算规则，通过这些规则只 增加非常小的计算量就可避免大量的随机抽样操作；对缓冲区策略l r u 置换 算法进行改进，提出了优先保存查询集合树的最新访问路径中的有效中间结 点的p p - l r u 算法，该算法在理论上大大降低了空问连接查询的代价。在以 p p l r u 算法作为缓冲区策略基础上，对空间连接代价模型进行了扩展和改 进，使其具有了较好的性能。 最后，通过仿真实验对改进的代价模型进行了验证，实验结果表明，改 进后的代价模型的相对误差保持在1 3 以内，并且改进模型的时间开销比原 模型有了很大的改善。 关键词：r - t r e e ；空间连接；代价模型；随机数表抽样；p p l r u 算法 哈尔滨 ：程大学硕士学位论文 a b s t r a c t b e c a u s et h es p a t i a ld a t ai sv a s t , m u l t i d i m e n s i o n a la n do u t - o f - o r d e r , t h e e f f i c i e n c yo fs p a t i a l d a t aq u e r yb e c o m e st h eb o t t l e n e c ko fi m p r o v i n gt h e p e r f o r m a n c eo fs p a t i a ld a t a b a s e ，s p a t i a lq u e r yo p t i m i z a t i o nb e c o m e st h ed i f f i c u l t y a n di n n o v a t i o no fs p a t i a ld a t a b a s ea p p l i c a t i o nc o n s e q u e n t i a l l y t h ec o s tm o d e li s o n eo fc h i e ft e c h n o l o g i e so fq u e r yo p t i m i z a t i o n , d u r i n gv a r i o u sq u e r i e s ，s p e c i a l j o i nq u e r yi sab a s a la n dh i g h - - c o s to p e r a t i o n , s oe s t i m a t i n gt h ec o s to f j o i nq u e r y i sv e r yi m p o r t a n tf o rs p a t i a lq u e r yo p t i m i z a t i o n t h i st h e s i ss t a r t i n gw i t hs t u d y i n gs p a t i a li n d e xa n ds p a t i a lq u e r yt e c h n o l o g i e s ， i n v e s t i g a t e sy a n n i st h e o d o r i d i s ss p a t i a lj o i nc o s tm o d e lf o a n d e do nr - t r e e d e e p l y t h i st h e s i sa n a l y z e st h es a m p l ea r i t h m e t i co fo b t a i n a gt h ea c t u a ld a t a d e n s i t yd e e p l y , r e s e a r c h e su s i n gr a n d o md a t at a b l ei nt h ec o s tm o d e la n dg i v e s c o r r e s p o n d i n gf o r m u l a s ；t h i st h e s i sd i v i d e st h ew h o l es p a c ei n t op l e n t i f u lc h i l d s p a c e sa n do b t a i n st h e 觚t l | a ld e i l s i t yu s i n g 戤w a p l m gp a r t i c u l a r l y ；t h i st h e s i sg i v e s as e r i e so fr e g u l a t i o n su s e dt oo b t a i ne v e r yq u e r yw i n d o w sd e n s i t y , u s i n gt h e s e r e g u l a t i o n sc a na v o i dan , h 篮so fs a m p l i n go p e r a t i o na n do n l ya d das p o to f c o m p u t i n g ；t h i st h e s i si m p r o v e st h el r up e r m u t a t i o na r i t h m e t i ca n dg i v e p p - l r ua r i t h m e t i c 。w h i c hc o l l l w ev a l i dm i d d l on o d e si nt h en e w e s t 、，i s i t e dw a y i nt h eq u e r yt r e e ，t h e o r e t i c a l l yt h i sa r i t h m e t i cc a l lr e d u c et h ec o s to f j o i nq u e r y g r e a t l y o nt h eb a s eo fu s i n gp p l r ua r i t h r a e t i ca sb u f f e rs 仃a t e g y , t h e s e e x p a n d a t i o n s a n d i m p r o v e m e n t s i t l a k et h ec o s tm o d e lt oh a v eag r e a t e r p e r f o r m a n c e i nt h ee n d ，t h i st h e s i sv e r i f i e st h ei m p r o v e dm o d e lt h r o u g he m u l a t i o n a l e x p e r i m e n t s t h er e s u l to ft h ee x p e r i m e n t ss h o w st h a tt h er e l a t i v ee r r o ro ft h e i m p r o v e dc o s tm o d e lk e e p sb e l o w1 3 ，a n dt h et i m es p e n d i n go ft h ei m p r o v e d m o d e lh a sa g r e a t e rm e l i o r a t i o nc o m p a r e dw i t ht h eo l do n e 哈尔滨丁程大学硕士学位论文 k e y w o r d s ：r - n e e ；s p a t i a lj o i n s ；c o 吼m o d e l ；r a n d o md a t at a b l es a m p l i n g ；p p - l r u a r i t h m e t i c 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：丝筮立 日期：9 , o 护7 年月7 日 哈尔滨r 程大学硕十学位论文 1 1 引言 第1 章绪论 支持大量多维的空间数据是当代数据库应用的内在要求，例如地理信息 系统( g e o g r a p h i c a li n f o r m a t i o ns y s t e m , g i s ) ，计算机辅助设计( c o m p u t e r - a i d e d d e s i g n , c a d ) ，图像与多媒体数据库等。由于表示与操作空间数据比较复杂， 为了支持空间数据，需要对传统的数据库进行扩展( 查询语言，数据模型， 索引方法) n - 。当今，已有应用的需求推动了空间数据库管理系统的研究，也 使得空间数据库技术成为数据库领域的一个研究热点。 空间数据库的查询效率是衡量空间数据库性能的重要指标。由于空间数 据量的庞大以及空间对象、空间查询的高度复杂性，实际应用如地理信息系 统( o i s ) 、c a d 等对空间数据库的查询性能提出了迫切要求。原有的关系数 据库查询优化技术并不能完全适用于空间数据。这迫使人们开始研究适合于 空间数据的查询优化技术。近年来，空间查询优化的研究逐渐以空间数据查 询的优化为主要内容，且这方面的研究已经取得了很大进展。 随着空间数据的广泛应用，以及空间查询优化技术的不断创新，研究的 热点逐渐转向了通过创建空间查询代价模型来优化空间查询，这个代价模型 要求能对一系列空阋查询的代价做出准确的评估，从而，可以在多个查询计 划中找出较优的查询计划来执行。空间查询主要包括选择查询和连接查询。 选择查询主要包括点查询和范围查询，连接查询与选择查询相比要复杂的多。 国内外专家早期研究的代价模型主要都是针对选择查询的，只是在最近几年， 很多专家才开始研究连接查询的代价模型。现今，一部分专家研究的连接代 价模型同时支持均匀和非均匀的空间数据分布，这样的代价模型很有现实意 义。此外，一些专家也研究了缓冲区策略对代价模型的影响，这方面的研究 对于提高代价模型的性能具有重要的意义。 本文主要以y a n n i st h e o d o r i d i s 等人提出的空间连接代价模型为基础，重 哈尔滨t 稃大学硕士学位论文 点分析数据非均匀分布和缓冲策略对空间连接查询的影响，通过深入研究抽 样算法给出了非均匀分布情况下的密度估算公式，并采用了一种有效的页面 置换算法，进一步提高了代价模型的性能。文章最后通过具有代表性的实验 数据和结果证明了给出的代价模型的优越性。 1 2 本文研究背景 空间对象存储在空间数据库中，它们由空间数据和属性数据来描述。空 间数据描述空间对象的位置、形状和分布特征等空间信息，属性数据描述空 间对象的名称、专题属性等非空间信息m 。在空间数据库里，既要存储空间对 象的空间数据，又要存储空闻对象的属性数据，并且还要对空间对象进行管 理和查询。 由于空间数据量的庞大以及空间对象、空间查询的高度复杂性，空间查 询优化成为了空间数据库应用的难点和突破点。而现有的关系数据库查询优 化技术不能完全适用于空间数据。优化空间查询从而提高空间数据库的性能， 对空间数据库的应用具有重要意义n - 。 利用代价模型寻找较优的查询执行计划，这是空间查询中常用的优化方 法之一。大多数的代价模型都是针对空间选择和空间连接这两种最常用的空 间查询操作而提出的，而在这两种查询操作中，空间连接又是相对复杂且代 价高昂的操作，所以，空间连接查询的代价评估对于空间优化策略有着重要 的意义。另外，空间索引主要代表有r - t r e e 及其变种树“- ，这些变种树各有优 缺点，为了衡量这些变种树查询性能的优劣，也需要准确的代价模型对其进 行评估。因此，本文研究的空间查询代价模型就是基于r - t r e e 的空间连接代 价模型。 1 3 国内外研究现状 关于r - t r e e 及其变体的代价模型的研究对于空间查询优化意义重大，国内 外专家在该领域的研究已有十几年的历史了。隧着研究的不断深入，代价模 2 哈尔滨工程大学硕十学位论文 型的技术和实用性得到不断地完善和拓展。 2 0 世纪8 0 年代末，f a l o u t s o s 等人最先尝试分析r - t r e e 的域查询性能。他们 提出的代价模型有一个理想的限制条件：假设空间数据是均匀分布的，并且 索引树的每个结点都被填满p a c k e dr - t r e e 。该代价模型是第一个对r - t r e e 性能 进行分析的代价模型，尽管其中的公式都是针对一维对象( 线段) 提出的， 但它们可以很容易的扩展到多维对象“，。该代价模型是之后的几乎所有的代价 模型的基础。 1 9 9 3 年，k a m e l 和p a g e l 提出，在满足r - t r e e 预先建立，且数据和查询窗口 是均匀分布的条件下，对任一查询窗口，可以得到查询的平均磁盘访问次数 1 1 。1 9 9 5 年，f a l o t s o s 和k a m e l 利用点数据集的分形维属性，使得他们的代价模 型能够预测磁盘访问次数”，。该代价模型是第一个能够处理非均匀分布数据的 代价模型，但只能针对点数据集。p a g e l 等人又提出了一个优化算法，计算静 态r - t r e e 的下界，从而能够在不同空间索引结构之间进行绝对性能比较n ，。1 9 9 6 年，p a g e l 等人通过对结点矩形的面积、周长和数量三要素的迸一步研究，得 出一个重要结论：窗口查询性能在一般情况下可以代表其它各种域查询的性 能m 。同年，t h e o d o r i d i s 和s e l l i s 提出了一个不同于以往的代价模型“”。该模型 只使用数据集本身的特性：数据的个数和数据密度。因为该模型中没有涉及 索引属性，所以，可以在r - t r e e 9 1 建之前评估其查询性能。2 0 0 3 年，j i n 等采 用数据密度思想提出了自己的查询代价模型n 一，。根据作者的实验结果，该模 型的域查询代价评估的相对误差不超过5 。 上述的代价模型都是以结点访问次数作为性能评价的基准，而没有考虑 缓冲区的存在。1 9 9 8 年，l e u t e n e g g c r 等人提出了一个崭新的代价模型，他们 将基于l r u 算法的缓冲区尺寸引入到r - t r e e 查询代价模型中n “。作者通过研究 三种著名的r - t r e e 变体的加载性能，得出一个重要结论：如果忽略缓冲区的影 响，只把结点访问次数作为性能评价基准，将会得出错误的结果。因此，在 r - t r e e 的性能研究中，应该把基于缓冲区的磁盘访问次数作为性能评价基准。 这是对以往理论的一个重大突破。 另外，还存在不同于数据密度的思想，1 9 9 9 年，p r o i e t t i 等人首次引入了 r - t r e e 结点的最小外包矩形的思想，通过研究发现这些最小外包矩形的分布遵 循它们所依赖数据的分布。作者利用结点的最小外包矩形得出新的域查询的 3 哈尔滨t 程大学硕士学位论文 代价模型“”。实验结果显示该代价模型的i o 次数的相对误差保持在3 0 以内。 国内专家这方面的应用和研究起步晚些。2 0 0 1 年，北京大学的方裕和楚 放提出了一个空间查询优化方案f q p r o ，重点实现了基于r t r e e 的代价模型， 并扩展了关于谓词选择性的部分，使之能够计算空间谓词的选择性“。2 0 0 3 年，华中科技大学的张志兵等在基于r - t r e e 的空间查询代价模型和y a n n i st h - e o d o r i d i s 等人提出的矩形密度模型的基础上，提出了代价估计的概率模型， 并通过实验验证了概率模型的估计精确度较矩形密度模型有了显著的提高 n ”。2 0 0 5 年，齐齐哈尔大学的金梅等对基于r - t r e e 的空间连接代价模型进行了 分析，提出了代价模型的公式，该公式对基于r - t r e e 的各类数据集是相当有效 的，相对误差大约在1 0 - 1 5 t w 。国内近年在这方面的研究还有很多，并取 得了一定的进展“”。 综上所述，目前国内外在空间连接代价模型这一领域的研究很多。大多 数的代价模型都有比较理想化的前提条件，不符合真实数据的情况。并且， 目前还少有入同时对非均匀数据集和缓冲策略进行深入的分析建模。 1 4 本文主要研究内容 空间连接查询是最重要的空间查询操作之一，本文研究的是空间连接操 作两个步骤中的过滤步骤。本文的研究内容将为完善空间连接代价模型在数 据非均匀分布和缓冲策略方面做些探索性的工作。 论文的研究内容主要包括以下几个方面： ( 1 ) 了解空间数据库查询优化的基本概念和方法。 ( 2 ) 学习代价模型的基本概念、公式，重点研究基于r - t r e e 的代价模型。 利用代价模型寻找较优的查询执行计划，这是空间查询中常用的优化方法之 一。r - t r e e 是目前最常用的空间索引，因此基于r - t r e e 的代价模型被广泛研 究“r l i ”“。 ( 3 ) 认真研究y a n n i st h e o d o r i d i s 提出的空间连接代价模型，分析其优 缺点。y a n n i st h e o d o r i d i s 等人研究出来的代价模型是比较成功的。该模型没 有利用r - t r e e 结构本身的属性，只是利用数据集合本身的属性，并且，该模 型考虑到了缓冲区对代价模型的影响。 4 哈尔滨t 程大学硕士学位论文 ( 4 ) 针对于y a n n i st h e o d o r i d i s 的代价模型的主要缺陷，给出改进的代 价模型。 ( 5 ) 对改进的代价模型，设计实验并根据实验结果验证其优越性。 1 5 论文的组织结构 基于研究的目的和内容，本论文组织结构如下： 第1 章介绍了课题的来源和背景，以及国内外研究现状，确定了论文的 研究内容。 第2 章介绍了相关的概念和目前流行的空间索引技术和空间查询技术， 并对查询优化过程、查询技术分类进行了论述。 第3 章简单的介绍了连接代价模型的基础性理论，详细的介绍了y a n n i s t h e o d o r i d i s 等人提出的代价模型的推导过程，介绍了该代价模型在无缓冲区、 基于缓冲区以及数据非均匀分布情况下的代价计算公式。 第4 章分析了原有代价模型的优缺点，研究了随机数表抽样方法，并给 出了非均匀分布数据集的实际密度计算方法，提出了改进的p p l r u 缓冲算 法，并给出最终改进的代价模型。 第5 章通过对三种空间数据集合的实验验证了改进模型在窗口查询和连 接查询比原模型在性能和估算精确度方面都有很大的提高。 哈尔滨t 稃大学硕七学位论文 第2 章空间索引与空间查询 空间索引技术和空间查询技术是研究空间查询优化的基础。由于空间对 象的特有特征，使得空间索引技术和空间查询技术与传统关系数据库都大不 相同。r - t r e e 索引结构是当前最流行的空间索引结构，空间连接查询是当前 最流行且代价高昂的空间查询方式之一，因此，研究基于r - t r e e 的空间连接 查询优化具有重要的意义。 2 1 空间对象 一个简单的点或一组任意分布的多边形都是空间对象。空间对象存储在 空间数据库中，它们由空间数据和属性数据来描述。空间数据描述空间对象 的位置、形状和分布特征等空间信息，如距离某地l o 公里的城市。而属性数 据描述空间对象的名称、专题属性等非空间信息，如城市的人口数量、地区 降雨量、粮食产量等n ，。 2 1 1 空间数据 空间数据是指用来表示空间实体的位置、形状、大小及其分布特征诸多 方面信息的数据，它可以用来描述来自现实世界的目标，它具有定位、定性、 时间和空间关系等特性。定位是指在已知的坐标系里空间目标都具有唯一的 空闭位置；定性是指有关空间目标的自然属性，它伴随着目标的地理位置； 时间是指空间目标是随时间的变化而变化；空间关系通常一般用拓扑关系表 示。“。 在实际应用中，空间数据也常常被称为图形数据，它包括点、线、面和 体等类型m ，。空间数据适合于描述呈二维、三维甚至更多维分布的现象，它 不仅能表示实体本身的信息，还能表示实体之间关系的信息。在g i s 应用中， 一个点可以表示一个城市，一条线可以表示一条河流或一个街道，而一个面 6 哈尔滨丁程大学硕士学位论文 可以表示一片深林或一个湖泊。由这些点、线、面等构成了一个整体就可以 表示真实的地形地貌，而它们之间的位置关系就可以表示真实的实体之间的 位置关系。这样，通过将现实生活的实体抽象为一些空间的数据类型，就可 以用处理空间数据的技术来解决现实生活中很多难以解决的问题。 2 1 2 空间数据的特征 空间数据除了具有一般数据的特征之外，还具有一些区别其它数据的特 征。构成空间数据的特征主要有； 1 空间性 这是空间数据最主要的特征，空间数据描述了空间物体的位置、形态、 甚至需要描述物体的空间拓扑关系。空间性是空间数据区别于其他数据的标 志特征。 2 抽象性 空间数据描述的是显示世界中的地物和地貌特征，非常的复杂，必须经 过抽象处理。不同主题的空间数据库，人们所关心的内容也有差别，所以空 间数据的抽象还包括认为的取舍数据。 3 多尺度与多态性 不同的观察尺度具有不同的比例尺和不同的精度，同一地物在不同的情 况下就有形态差异。 4 多时空性 g i s 数据具有很强的时空性。一个g i s 系统状的数据源既有同时间不 同空间的数据系列，也有同空间不同时间序列的数据。g i s 数据是包括不 同时空和不同尺度数据源的集成一。 空间数据除具有上述主要特征外，还具有数据量巨大、空间关系复杂等 特征。因为空间数据具有这些不同于其它数据的特征，所以，处理空间数据 就要比处理其它普通数据要复杂的多，通常处理空间数据所需要的时空消耗 都是处理其它数据所不能相比的。传统的关系数据库技术并不能完全适用于 空间数据，因此。要想有效的管理空间数据，必须从空间数据的这些特征出 发，用适用于空间数据特征的技术来处理空间数据。 7 哈尔滨t 程大学硕七学位论文 2 1 3 空间关系 空间数据是以空间坐标的形式存储的，空间坐标可以表示空间对象的尺 寸、位置等信息，也能够表示空间对象间的关系信息。空闻关系是指空间对 象之间的一些具有空间特性的关系m 。空间关系理论的研究进展直接影响着 g 1 s 空间数据模型、空间数据库查询、空间分析、空间推理、制图综合，地 图理解、自然语言界面标准化等方面的发展与应用。 人们对空间关系的研究主要包括拓扑、方向、度量三大类空间关系“。 拓扑关系指拓扑变换如平移、旋转、缩放下的拓扑不变量，如空间目标关联、 相邻与连通关系；方向关系是用来描述对象在空间中的某种顺序的关系，如 前后、上下、左右、东西南北等；度量关系是用某种度量空间中的度量来描 述的目标间的关系，如目标间的距离方位关系用来描述目标在空间中。这三 类关系中拓扑关系最为重要，因此也被研究得最多。 空间对象间的空间关系与对象的维数、位置、尺寸等因素有关，空间数 据较一般数据要复杂的多，而空间对象的三类空间关系也并不是完全相互独 立的，它们之间是存在着一定的关系的，因此，描述和理解空间关系并不容 易。为了提高空间关系描述的唯一性和空间关系推理的准确性，需要从整体 来考虑拓扑、方向和度量的关系，将这三者有机的结合起来，分析它们潜在 的相互影响，创建种拓扑、方向和度量关系的集成描述、推理模型，这样 才有助于设计有效的空间查询和数据处理方式。目前，国际上对空间关系理 论的研究得到不断发展，形成了不少理论成果。 2 2 空闫索引技术 空间数据库索引技术m 是对存储在介质上的数据位置信息的描述，用来 提高系统对数据获取的效率。它的提出由两方面因素决定的：其一是由于计 算机存储器分为内存和外存两种，访问这两种存储器一次所花费的时间大约 相差十万倍以上，丽实际应用中，绝大部分数据存储在外存，如果对磁盘上 8 哈尔滨工程大学硕士学位论文 的数据不加以索引和组织，访问磁盘数据的代价将会严重影响系统的效率； 其二，关系数据库索引技术并不适用于空间数据，因此，需要研究特殊的能 适应空间数据多维特性的索引方式。空间数据库索引技术是提高空间数据库 查找性能的关键技术，直接影响到空间数据库系统的成败。 2 2 1 空间索引技术分类 索引的要求是支持动态的更新以使得索引和数据库保持一致。空间索 引技术可分为如下四大类，其中主流方向都是采用树型索引结构： 1 基于二叉树的索引技术 基于二叉树的索引技术的典型范例有k d 树、k d b 树、l s d 树等。这 种索引结构的典型k d 树是一种二分索引结构，主要用于索引多维数据点，但 对复杂的空间对象，如折线、多边形、多面体等的索引却必须采用近似方法 和空间映射技术。由此针对空间关系的查询效率将非常低，另外，索引树非 常庞大，需要存储在外存。为了能索引复杂的空间对象，提出了适合索引二 维空间对象的基于实体标志重复存储技术的m k d 树；为了将k d 树存储到外 存，将k d 树与b 树结合起来，提出了k - d b 树；s k d 树的提出避免了空间 对象的重复存储和空间映射，用空间对象的秩序带来对空间对象集进行二分 索引，但所有这些方法对非点状空问对象的索引效率都较低。 2 基于b 树的索引技术 b 树及其变形，被广泛应用于常规的数据库管理系统之中，实践证明其 对大型数据库的索引具有出色表现。目前的空间数据库索引技术，很多都是 基于b 树。如g t m m a n 提出的r - t r e e ，r - t r e e 的思想是将空间对象及其索引 空间用其外接矩形来近似表示。可以简化计算、减少存储空间；将空间上邻 近的对象组织在同一结点或同一分枝，可以减少外存访问次数。然而它允许 区间重叠，导致了搜索路径的平均数量的增加；每一维的区间都要存储，需 要较多的存储空间。为此，为了避免索引空间重叠的问题，提出了r - t r e e ； 为了减少查询中对外存的访问次数出现了c e l l 树等。总之，这类索引结构需 要解决的主要问题仍然是减少区域的重叠，提高搜索效率。 3 基于h a s h i n g 的格子技术 q 哈尔滨= 丁= 程大学硕士学位论文 这种方法的基本思想是将索引空间划分为相等或不相等的一些小方格， 与每个格子相关联的空间对象则存储在同一磁盘页，而格子的访问地址则可 以直接通过求数组下标或某种算法得到。如格子文件，r - f i l e 等。这类方法 主要是用于索引多维点状空间数据。 4 空间对象排序法 其基本思想是：将索引空问划分为许多小的格子，然后每个格子制定一 个唯一的数字或编码，空间对象则用与其相交的个或多个格子的数字来表 示，或用与其相交格子的编码求得另一唯一编码来表示。实质是将甩维空间 的实体映射到一维空阀。用一维的数值对多维的空间对象进行排序，常见的 方法有：l o c a t i o nk e y s ，z - o r d e r ，h i l b e r t 等o 。 也有的分类方法将空间索引结构分为基于点数据的空间数据结构和基于 非点数据的空间数据结构两大类。 2 。2 2r - o l ：r e e 及其变体 r - t r e e 是g u t t m a n 在1 9 8 4 年提出的，和b + 树一样是一棵高度平衡树，是 b + 树在万维空间的扩展，。因为，r - t r e e 支持多维空间对象，且有较高的查询 效率，所以被广泛的研究，进而产生了r - t r e e 的多种变体。r - t r e e 及其变体 是空间数据库中最常用的索引技术。r - t r e e 不是存储最初的多维空间对象， 而是存储对象的m b r ( m i n i m u mb o u n d i n gr e c t a n g l e ，最小边界矩形) 。 r t r e e 管理的m b r 是包含初始对象的最小多维矩形，r - t r e e 常常用来在过滤 步骤中找出那些其m b r 与查询对象的m b r 相交的空间对象。 尽管r - t r e e 的变体很多，但万变不离其中，r - t r e e 是所有变体的基础。 r - t r e e 及其变体的组成包括中问结点和叶子结点。中问结点的索引结构为( p 伊， 矗) ，其中p t r 表示该子结点的地址，r 表示包含子结点中所有项的最小外包 矩形m b r 。叶子结点的索引结构为( d 眭矗) ，其中o l d 标识多维的空间数据 对象，盂是包围该空间对象的m b r 。r - t r e e 中每个结点所包含的子结点的数 目是有上下限的，上下限保证了对磁盘空间的有效利用。 r - t r e e 具有下列性质： ( 1 ) 假设每一个结点( 根结点除外) 最多包含m 个子结点，最少包含 1 0 哈尔滨t 程大学硕+ 学位论文 i 1 i 个子结点，那么要求m m 2 ： ( 2 ) 根结点最少包含两个子结点： ( 3 ) 叶结点的深度相等即每一个叶结点到根结点的距离是相等的； ( 4 ) 所有m b r 的边与一个全局坐标系的轴平行； ( 5 ) 如果被索引的空间对象总数为个，那么r - l a e e 的深度最多为 l o g ，“0 v 1 ) 。 图2 1 举例说明了为一个数据集( 图2 1 中只显示了这些对象的m b r ) 构建它的r - t r e e 索引。虚线矩形是目录m b r ，实线矩形是存储在叶子结点上 的对象m b r 。注意：在同一结点所包含的m b r 可能同另一个m b r 相交。 图2 i 一组二维矩形的r - t m e 搜索的性能取决于两个参数：覆盖( c o v e r a g e ) 和交叠( o v e r l a p ) 。树的 某一层的覆盖是指这一层所有结点的m b r 所覆盖的全部区域。所以，覆盖 是对静态空间的间接衡量，或者是树覆盖的空白区。树中某一层的交叠是指 在该层上被多个与结点关联的矩形所覆盖的全部空间区域。交叠使得查找一 个对象时必须访问树的多个结点m 。 r - t r e e 的搜索过程为：当查找与一查询窗口相交的所有空间对象时，搜 索算法是从根结点开始向下逐层来搜索相应的子树。当发现查询窗口与某一 结点相交，那么继续向该结点的子树进行搜索，如果不相交，则不进行其子 树的搜索。以此类推，当到达叶结点时，最d , j b 包矩形中的元素被取出并澳9 试其是否与查询窗口相交，所有与查询窗口相交的叶结点即为要查找的空间 对象。r - t r e e 的查询效率会因重叠区域的增多而大大减弱，在最坏情况下， 对树的搜索甚至会退化成线性搜索。为了避免这个问题，提出了r - t r e e 的变 体r + - t r e e 。 r + - t r e e 的基本思想是：目录m b r 不相交，那么，相交的对象m b r 将 哈尔滨丁= 程大学硕士学位论文 j l i m l l 被分割，并存储在几个不同的叶结点中，这增加了存储空间。对图2 1 中的 二维空间对象建立的p , + - t r e e ，如图2 2 所示。从图中可以看到，对象d 在r + - t r e e 中被分割成两部分并存储在两个叶结点中，对象应的情况亦如此。 图2 2 一组二维矩形的r + t r e e r - t r e e ”是最有效的r t r e e 变种，它由b e c k m a n n 等人提出。r - 仃。e 继承 了r - t r e e 的索引结构，但在算法上做了较深入的改进，使性能得到显著的提 高。r - - t r e e 能对覆盖区域、重叠面积和边界周长进行启发式地优化，并通过 重新插入节点重建r - t r e e 以提高其性能，但重新插入结点的过程并不简单， 需要消耗较长的时间。 基于r - t r e e 的变体还有很多，r - t r e e 系列空间索引具有其它索引无法企 及的优势：( 1 ) 它按数据来组织索引结构，这使其具有很强的灵活性、可调 节性，无须预知整个空间对象所在空间范围就能建立空闻索引；( 2 ) 由于具 有与b - t r e e 相似的结构和特性，使其能很好的与传统关系型数据库相融合， 更好地支持数据库的事务、并发等功能。这是许多国外空问数据库系统选择 r - t r e e 作为空间索引的一个主要原因。 2 3 空间查询技术 2 3 1 空间查询方式 由于空间对象及其之间的关系非常复杂且数据量大，因此，各种空间操 作不仅计算量巨大，而且涉及复杂且代价高昂的几何操作。空间查询操作是 最常用的空间操作之一，如果能在各种查询操作之前对空间对象进行过滤， 1 2 哈尔滨丁= 程大学硕士学位论文 从而减小要操作的空闯对象的数量，则可以大大缩短计算时间，提高查询的 效率。空间索引就是为了这个目的而设计的。因此空间查询操作一般都基于 空问索引机制。 充分利用空阆索引有效地进行空间检索，是空间数据库的一项关键技术。 空间索引r - t r e e 流行的一个重要原因就是其能够有效支持多种空间操作。近 年来，许多专家学者针对基于r - t r e e 的空间查询算法进行了大量的研究。在 空间查询操作中，常用的有：精确匹配查询、点查询、窗口查询、域查询、 空间连接查询、拓扑查询、相邻查询和最近邻查询* m 。下面介绍其中的几种 基础的查询方式。 点查询( p o i n tq u e r y , p q ) ：给定一个查询点p ，找出所有包含它的空间对 象d ：p q ) = d 驴d g 匆，其中o , g 为对象的几何信息。考虑下面一 个查询：。找出包含h r b 的河流冲积平原”，h r b 是点类型的常量，城市在空间 数据库中就可以被抽象成一个点类型常量。 范围查询或区域查询( r a n g eo rr e g i o n a lq u e r y , r q ) ；给定一个查询多边 形p ，找出所有与之相交的空间对象d 。当查询多边形是一个矩形时，称这 个查询为窗口查询。这类查询有时也称作范围查询；r q ( p ) - - 0 嵋g n d g p a 精确匹配查询( e x a c tm a t c hq u e r y ) ：找出所有和空间查询对象d ，具有完 全相同空闻内容( 即空间属性) 的空间数据对象，即e m q ( 口) = 酬o ：g = n g ( 6 属于，为d 维的欧几里德空间) 。 相邻查询( a d j a c 七n c yq u e r y ) ：找出所有和查询对象d 相邻的空间数据对 象。如果两个对象有共同边界没有相互包含，那么称这两个对象相邻w 。 本论文研究的查询操作就是空间连接查询，而空间连接查询以点查询和 范围查询为基础。 2 3 2 空间连接查询 空间连接查询是空间查询中的一种重要的多路查询，即从两个空间数据 集合中检索出所有满足某一空间谓词( 如交、包含等) 的空间对象。如给定 两个对象集彳和挽其空间连接是从a 中的对象到b 中的对象应用谓词s 的 1 3 哈尔滨下程大学硕+ 学位论文 结果，谓词s 包括覆盖、距离、方向、邻接和包含等m ，。当两种空间对象关 系连接在一起时，称之为空间连接m ，。 空间连接操作算法包括很多“。比较常用的连接算法有：嵌套循环连接 方法、树匹配策略、基于分块的空间归并连接方法、空间哈希连接方法、种 子树连接方法和槽索引空间连接方法( s i s j ) 等。实验表明t w ，在众多的连 接方法中，在当两个数据集均有索引时，r - b e e 连接性能最佳；当只有一个 数据集具有空间索引时，s i s j 最有效；而对都没有索引的两个数据集，哈希 连接为最理想的方法。 对于本文的空问连接查询，假设参与连接的数据集合已经建立r - t r e e 索 引，因此，本文采用树匹配策略的s j 算法。树匹配策略的s j 算法描述为： 设两个矩形的集合且l 与舵，这两个集合分别表示两个其空间对象用r - t r e e 检索的空间关系。该算法使用r - t r e e 结构来设计空间连接操作。空间谓词为 两个矩形的交：若( r l ，r 2 ) 满足下列条件，则属于连接关系： r e c t ( r 1 ) n r e c t ( ，2 ) m 如果而和拖分别为关系置l 与r 2 的索引树的结点占用的页面树，那么 i o 代价的下限为厶l + 惋。该算法基于这样一条规律：非叶结点的矩形能够容 纳所有子结点中的矩形的m b r 。因此。如果两个目录项e r l 和e r 2 不相交， 那么它们子树中的所有数据矩形必然也不相交。如果目录项相交，那么子树 的某个数据矩形则有可能相交。 树匹配算法s j 如下： s j 1 ，r 2 ：r j o d e ) ；严s p a t i a lj o i na l g o r i t h m + ， 0 lb e g i n 0 2 f o r 叫l e r 2i n r 2 ) d o 0 3 f o r ( a l l e r li n r l ) d o 0 4 i f ( o v e r l a p ( e r l 托c t ，e r 2 r e c t ) ) t h e n 0 5 i f 限1a n dr 2a 佗l e a f p a g e s ) t h e n 0 6 o u t p u t ( e r l o i d ，e r 2 o i d ) 0 7e l s e i f 限1i sal e a f p a g e ) t h e n 0 8 r e a d p a g e ( e r 2 p t r ) ； 0 9 s j ( e r l p t r , e r 2 p t r ) 1 4 哈尔滨丁程大学硕士学位论文 1 0e l s ei f ( r 2i sal e a t p a g e ) t h e n 1l r e a d p a g e ( e r l p t r ) ； 1 2 s j ( e r l p 仕，e r 2 ，p t r ) 1 3e l s e 1 4 r e a d p a g e ( e r l p t r ) ；r e a d p a g e ( e r 2 p t r ) ； 1 5 s j ( e r l p t r , e r 2 p t r ) 1 6e n d i f 1 7e n d i f 1 8烈d - f o r 1 9 e n d f o r ； 2 0e n d m - 算法s j 展示了对两棵r - t r e e 的空间连接操作的搜索过程。从算法中可以 看出，在两棵树都没有到达叶子结点时，算法同步地遍历足l 和舵的每一层。 空间连接操作的代价是以实际的磁盘访问次数作为衡量基准的，两磁盘访闯 通常是指访问驻留在磁盘上的两棵树的索引项。s j 算法中的r e a d p a g e 操作 过程可能是一次实际的磁盘读取操作，也可能是从驻留在存储器缓冲区中读 取相关的结点信息，因为存储器缓冲区速度很高，一般的，认为从存储器缓 冲区读取结点信息不增加连接操作的访问代价。 2 4 空间查询优化 空间奄询的优化过程大致分为如下4 个阶段： ( 1 ) 将查询转换为某种内部表示 其一般是将查询条件用语法树的形式表示。 ( 2 ) 进行某些提高效率的表达式变换 如先进行选择再连接，先进行投影再连接等的变换，而且变换规则通常 是有正确性保证的。 ( 3 ) 谓词代价计算 ( 4 ) 选择代价最小的执行计划 其中，前两个阶段与关系数据库优化的相应阶段类似，本文不做详细介 1 5 哈尔滨工程大学硕士学位论文 绍；而谓词代价的计算与具体代价模型有关“。 根据上述的查询优化过程，可以将查询优化技术分为以下几类： 1 空间索引 一 这是从数据存取的角度来优化空间查询。因为，通常空问数据的数据量 都是很庞大的，有效读写海量数据是优化空间查询操作的重要方法。 2 查询处理算法 这是从提高查询执行效率的角度来优化空间查询的。通过尽可能少的复 杂几何计算就能得到正确的查询结果、提高查询执行的效率是优化查询处理 算法的主要目标。 3 代价模型 这是从指导查询过程( 即采用哪一种查询计划) 的角度来优化空间查询。 这一过程在处理含有多个空间查询条件的查询时起到了重要的作用。 本文主要研究的就是第三类查询优化技术，即提出一个有效的空间连接 查询代价模型。 2 5 本章小结 本章介绍了空间对象的基本概念、特点和对象间的关系。空间对象由空 间数据和属性数据来共同描述。属性数据与传统关系数据库中的数据类似， 空间数据与空间对象的空间位置有关，它有点、线、面( 区域) 三种数据类 型。本章对空间索引技术特别是r - t z e e 索引结构进行了详细的介绍。r - t r e e 及其变体是空间数据库中最常用的索引，适合于多种连接操作。本章对空间 查询的各种方法也进行了简单的介绍，重点论述了空间连接操作，并给出