（计算机应用技术专业论文）时空数据库索引研究.pdf

中国科学技术大学硕士论文 时空数据库索引研究 致谢 感谢赵振西教授和数据库课题组的龚育昌教授和岳丽华教授，本论文 是在他们的关心指导下完成的。在课题组的每次讨论中，我都会从你们那 罩得到许多启发，正是你们亲切的鼓励和帮助才使得本研究课题得以存在 和发展。 感谢课题组其他同事给我的帮助。本课题提出伊始，他们就跟我一起 做这方面的研究工作，由于我们共同的努力才使得本文如期完成。金培权 老师及韩凯、杨晓宇、杨洋等几位同学都给了我们很多的建议和帮助。还 有周英华、刘晓红、韦鹏、陈安、翟小栋等几位同学也给了我们很多的帮 助，在此一并表示感谢! 感谢项目合作单位电子工程系的徐守时教授、陈学俭教授、吴秀清教 授、谭勇副教授、张荣副教授以及电子工程系的同学。两年多的合作使我 从你们那里学到了很多知识，也使我的思维更加开阔。 感谢学校对我的培养，这三年学习和科研生活使我在各个方面都得到 完善和提高，感谢所有帮助过我的同学和老师! 感谢我的家人对我的关心、鼓励和支持，正是他们的无私奉献才使我 顺利完成学业。 中国科学技术大学硕士论文时空数据库索引研究 摘要 时空数据库作为数据库研究领域中的一个重要分支，经过近十年的发展，在 时空数据模型、时空查询优化与索引和时空本体论等方面取得了许多成果。现 实世界中的许多实体都具有空间特性和时态特性，需要数据库管理系统提供有 效的时空数据管理能力，如地籍管理系统中的地块，交通管理系统中的车辆等。 时空数据库用于管理形状和位置随时间变化的对象。为了快速访问其庞大 的数据量，必须建立有效的时空索引以提高各类时空查询的效率。本文对时态、 空间和时空索引技术进行了系统的研究，并讨论了索引的性能评估和实现技术。 主要的工作及特色为： 1 对基于对象关系模型的时空数据库体系结构进行了研究，选取了一种实用 的时空数据库系统实现方案。 2 从时态索引和空间索引两个方向扩展，讨论了时空索引的设计思路。分析 了在历史时空数据和活跃时空数据上建立时空索引的区别，并设计和实现 了一种针对活跃时空数据上的时空索引，给出了试验结果评估和性能分析。 该索引相对己有的同类型索引能有效地提高查询效率和节省磁盘空间，能 较好的支持多种时空操作，具有较强的适应性。 3 研究了在大型商用对象关系数据库中集成用户设计的索引相关技术， 设计并实现了部分时空操作和支持操作的索引，并给出了测试结果。 所实现的索引和数据库系统核心紧密集成。它在提高查询性能的同时， 还支持数据库的并发与恢复机制。 关键词：时空数据库时空索引数据刀片唧 中国科学技术大学硕士论文时空数据库索引研究 a b s t r a c t s p a t i o t e m p o r a ld a t a b a s ei sa ni m p o r t a n tb r a n c hi nt h er e s e a r c hf i e l do fd a t a b a s e a f t e ra b o u tt e ny e a r sd e v e l o p m e n t ，r e s e a r c h e r sh a v em a d es i g n i f i c a n tp r o g r e s si n a r e a so f s p a t i o t e m p o r a lo n t o l o g y , s p a t i o t e m p o r a lm o d e l ，s p a t i o t e m p o r a lq u e r y o p t i m i z a t i o na n di n d e x m a n ye n t i t i e si nr e a lw o r l dh a v eb o t hs p a t i a la n dt e m p o r a l c h a r a c t e r i s t i c s ，s u c ha sp a r c e l si nl a n dm a n a g e m e n ts y s t e m s ，v e h i c l e si nt r a f f i c m a n a g e m e n ts y s t e m sa n d s oo n a sm o r e c o m p l i c a t e da p p l i c a t i o n sc o n c e r n i n gt h e s e e x a t i t i e s a p p e a r , i ti sn e c e s s a r yf o rm o d e md a t a b a s em a n a g e m e n ts y s t e m st o b e c a p a b l eo fp r o v i d i n ge f f e c t i v ea n de f f i c i e n t m e a n st o m a n i p u l a t es p a t i o t e m p o r a l d a t a s p a t i o t e m p o r a ld a t a b a s ei s u s e dt om a n a g eo b j e c t st h a tc h a n g et h e i rl o c a t i o n s a n ds h a p e sa st i m ep a s s e s i ti se s s e n t i a lt ob u i l de f f e c t i v es p a t i o t e m p o r a li n d i c e si n o r d e rt oi m p r o v eq u e r yp e r f o r m a n c eb e c u a s eo ft h eh u g em o u n to fs p a t i o t e m p o r a l d a t ai nt h ea p p l i c a t i o n s t i l i st h e s i sd e m o n s t r a t e sm yr e s e a r c ho nt e m p o r a l s p a t i a l a n d s p a t i o t e m p o r a l i n d e x t e c h n o l o g i e s ，d i s c u s s e s t h ee v a l u a t i o no ft h ei n d e x p e r f o r m a n c ea n di m p l e m e n t a t i o no fi n d i c e s m a i nf e a t u r e s o ft h et h e s i si n c l u d e f o l l o w s ( 1 ) s c h e m e so fi m p l e m e n t i n gas p a t i o t e m p o r a ld a t a b a s e a r ed i s c u s s e da n da p r a c t i c a ls p a t i o t e m p o r a ld a t a b a s ea r c h i t e c t u r eb a s e d o no b j e c t r e l a t i o n s h i pm o d e li s g i v e n ( 2 ) b a s e do nt h ee x t e n s i o no fb o t ht e m p o r a la n ds p a t i a li n d i c e s ，t h e d e s i g n p r o c e s so fs p a t i o t e m p o r a li n d i c e sa n dt h ed i f f e r e n c eb e t w e e n h i s t o r i c a la n da c t i v e s p a t i o t e m p o r a li n d i c e sa r ed i s c u s s e d ；a na c t i v es p a t i o t e m p o r a li n d e x i sd e s i g n e da n d i m p l e m e n t e dw h i c hc a ne f f e c t i v e l yi m p r o v eq u e r ye f f i c i e n c y c o m p a r e dw i t hi t s c o u n t e r p a r t s a p p m i s e m e n t r e s u l t so f t h e d e s i g n e ds p a t i o t e m p o r a li n d e x a r eg i v e ni n d e t a i lt o o ( 3 ) e m b e d d i n ga u s e r - d e f i n e di n d e xi n t o ac o m m e r c i a lo b j e c t - r e l a t i o n s h i p d a t a b a s ei si l l u s t r a t e da n dd e m o s t r a t e d i na d d i t i o n ，r e a l i z a t i o na n dt e s t i n gr e s u l t sa r e g i v e n 。w h i c hs h o w t h ee f f e c t i v e n e s so ft h ei n d e x a l s o ，t h ei n d e xi si n t e g r a t e dw i t h t h ed b m s c l o s e l ya n d c a l le f f e c t i v e l yi m p r o v eq u e r yp e r f o r m a n c e ，s u p p o s i n gt h e c o n c u r r e n c ea n dr e c o v e rm e c h a n i s mo f t h ed a t a b a s es y s t e m a tt h es a m et i m e k e y w o r d s ：s p a t i o t e m p o r a ld a t a b a s e s p a t i o t e m p o r a l i n d e x d a t a b l a d e 3 ， 中国科学技术大学硕士论文 时空数据库索引研究 第一章绪论 1 1 引言 管理对象空间和时态属性的数据库分别称之为空间数据库和时念数据库， 管理空间状态如形状大小，位置坐标随时间变化的对象的数据库则称之为时空 数据库。时空数据库从九十年中期开始引起了数据库研究工作者的极大兴趣。 经过十余年的发展，在时空本体论，时空数据模型，时空查询优化和时空索引 技术等方面取得了很大的进步”“。现实世界中有许多实体具有时空特征，如交 通监控的车辆，森林火灾的火灾区域和动物研究中的候鸟迁移等，需要使用时空 时空数据库来管理。 由于时空数据库里的数据随时间不断地积累，尺寸十分庞大，因此建立有 效的索引结构来访问这些数据非常重要。时空数据库管理系统应当可以有效支 持时空数据检索。要达到这个目的，需要对现存的多维数据访问方法进行扩展。 数据库研究者们在这个领域已经作出了相当多的工作。对r - t r e e s 和q u a d t r e e 扩展构建新的索引是时空索引研究的两条重要的途径。在时空索引的性能测试 中，研究者使用合成数据集做了大量的试验工作，并考虑了在大型对象关系数 据库上实现提出的时空数据模型和索引。在检索到的文献中，有许多有效的空间 索引算法，但是它们都没有考虑到时间的因素；另一方面，也有相应于事务时 i 日j 有效时间的时态索引算法，但是这些算法没有考虑到空间因素。到目前为止， 综合考虑时间和空间因素的索引算法仅有四种，即m r t r e e s “、r t t r e e s “、 3 dr - t r e e s 和h r t r e e s “力。 目前这些算法对于时空数据库查询都有一些局限性，它们要么只针对某些 的数据类型，要么索引数据存储空间十分庞大。目前时空索引研究着重于从三 个方面展开： ( 1 ) 支持多种数据类型和数据集，如空间对象有点目标、区域目标等，对象 的运动方式有连续运动、非连续运动等。 ( 2 ) 支持多种索引构造方式。索引结构的构造可以是在数据库批量载入数据 时批处理构造，也可以是事务处理时动态的构造。好的索引结构应该可以支持 两种构造方式。 ( 3 ) 支持多种查询。时态数据查询有时间片和时间区间之分，而空间数据的 查询有空间范围查询、最邻近查询和空间连接等，二者的结合使得时空查询种 类十分丰富，应该设法找到好的时空索引结构支持多种查询。 本章综述了时空数据库和时空索引的发展现状，讨论了时空索引的实现技 ! 旦登垫查厶堂塑主鲨窒 堕窒塑堡堕塞! ! 堕壅 术。最后概述了本论文的主要工作。 1 2 时空数据库与时空查询 y a n n i st h e o d o r i d i s 等人一1 定义时空数掘库为：时空数据库是一个包含了时 态数据，空间数据和时空数据，并能同时处理数据对象的时间和空间属性的数 据库。 在时空数据库系统的实现中，我们采用了从对象关系数据库管理系统上进 行时空扩展的策略。对象关系数据库管理系统提供了用户定义数据类型( u s e r d e f i n e dd a t at y p e ，u d t ) 以及用户定义过程( u s e rd e f i n e dr o u t i n e u d r ) 的扩展功能，因此，可以在对象关系数据库系统上扩展新的时空数据类型和时 空操作，同时将时空索引通过u d r 和其它插件技术扩展到系统中。这种实现方 式极大地减低了时空数据库管理系统的实现成本，同时可以充分利用对象关系 数据库的强大功能。 支持形式多样时空查询是时空数据库的一个重要特色，最基本的空间查询 是窗口查询”1 ，它返回所有和查询窗口相交的空间对象。空间查询再加上时态 限制就形成了时空查询。时空查询是针对时空数据特点的查询，y a n n i s t h e o d o r i d i s 等人 9 1 把时空查询分为三类： ( 1 ) 时间片窗口查询：q = ( r ，t ) ，其中r 是在t 时刻的一个超立方体，即一 个空间窗口一个简单的例子就是在交通监控数据库中查找t 时刻在区域r 内 所有交通车辆。这是最简单也是最常用的时空查询。可以把它看作空间数据库 中的空间选择操作和时态数据库中的时间片选择操作的积。 ( 2 ) 时间段窗口查询：q = ( r ，t ，t j ) ，如果r 是n 维空间的超立方体，r 和时 间轴t 构成n + l 维的超立方体。同样的以交通监控为例，此查询返回在时间t 。 到t ：之间经过区域r 的所有交通车辆。可以把它看作空间数据库中的空间选择 操作和时态数据库中的时间段选择操作的积。 ( 3 ) 移动查询：q ；( r 。，r ：，t ，t ：) ，指定了在n + l 维空间上的超台体。 这里是指区域的面积在t ，时刻为r 。，到t ：时刻变为r 。如森林火灾中的火灾面 积从t 。时刻的r 。蔓延到t 。时刻的r ：，查询此过程中遭到焚烧的树木。 时空数据库管理系统中，不但具有复杂的时空类型管理功能，还具有实现 复杂的时空操作的功能。虽然当前的商业数据库都提供自定义类型与操作的功 能，但这种扩展功能并没有改变查询优化器，也就是查询优化器并没有提供相 应的优化机制，在这种优化器中，复杂类型的操作和简单类型的操作是等价的， 所以创建一个时空查询优化器以提高查询效率就显得非常重要。 目前国内外对时空查询优化的研究尚属于起步阶段，大都是局限于时态查 中国科学技术大学硕士论文 时空数据库索引研究 询优化或者空间查询优化。文献 4 提出了一种实现时态查询处理的中间件技 术，该中间件把查询处理分成两部分，一部份即复杂的时态操作由中间件处理， 而简单的操作则交给底部数据库实现，并通过这种方法来提高时态查询优化的 效率。 1 3 时空索引 虽然时空数掘处理对于现实世界建模非常重要，但是出于时空数据的复杂 性，目前好的时空索引却不是很多。索引的研究多集中在支持多维数据的纯空 问索引研究和对于一般传统数据类型如( 数字，字符串) 上的时态索引上。由 于r 树及其变体在在空间索引上的优势，在过去十年里，研究者们提出了许多 基于r 树的时空索引版本，可以把它们大致分为如下几类：( 1 ) 把时间维当作空 间的另一维处理“；( 2 ) 把时间信息集成到空间索引结构的节点中去，而不认为 它是另外一维“；( 3 ) 使用重叠索引结构来表达数据库在不同时刻( 事务时间 或是有效时间) 的不同时间状态“。假定时间维当作空间的另一维处理是一 个最简单的想法，处理多维空间数据的索引技术比较成熟，例如r 树以及其变 体。3 dr 树的实现过程中认为时间是二维空间之外的另一维，简单地把二维空 间转换成三维空间最小外接立方体。t z o u r n m a n i st 等人“”提出的基于四分树 的时空索引方案也是采用了多版本技术。区域四分树是对二维二值光栅图象分 解成一系列的四分象限( q u a n d r a n t ) ，每个象限具有2 ”。2 ”1 个象素。如果某 部分不是完全全黑或者全白，则该部分需要递归分解成四个子象限，直到每个 子四分块具有同一种颜色为止。基于四分树的技术对于珊格图象的索引更为有 效，但是对于空间矢量化的对象不是很有效。本文主要探讨了对基于r 树算法 的时空索引的扩展，以满足更多应用。在第四章中，给出了对3 dr t r e e 的扩展， 并给出了设计和实现过程，以及详细的性能评估。 时空数据库涉及到对静态或动态的空间对象的有效操作，因此，它必须能 有效地支持该类型数据。研究者对一些多维访问方法进行扩使得它们能够支持 索引和检索时空数据，从而满足用户要求。为了客观地比较这些提出的索引访问 机制，还有必要从对象的表达、查询处理和索引维护方面给出一个时空索引应 当满足的基本规范。 1 4 时空索引实现与评估 一个针对时空数据访问方法有效的评估基准环境应该包括以下凡方厩模 块：( 1 ) 能产生合成数据集；( 2 ) 能保存数据集( 包括真实数据集) 到非易失存 储介质；( 3 ) 具有收集数据和运行结果的访问机制；( 4 ) 能可视化试验结果。 本文针对以上几方面对时空索引算法的数据集进行了合成。 中国科学技术人学硕十论文 时空数据库索引研究 许多具有市场潜力的涉及到复杂数据库技术的应用，如地理信息，医疗， 空间信息和多媒体应用都需要有对新的复杂的数据类型的有效支持。因此，主 要的数据库厂商在他们提供的数据库系统中不再仅仅满足提供简单二进制对象 ( b l o b s ) ，而是提供了更多的扩展特色。这些特色包括允许用户添加他们自己 的数据类型和访问方法。现在比较流行的方案包括d b 2e x t e n d e r ，i n f o r m i x d a t a b l a d e 和o r a c l ec a r t r i d g e s 。对于时空数据库研究者来说，一个可扩展的 系统提供了新的机会，使得开发大的复杂应用成为可能。 在实现扩展3 dr - t r e e 的数据刀片( d a t a b a d e ) 过程中，我们使用了c 和c + + 程序设计语言以及i n f o r m i x 服务器提供的d a t a b l a d ea p i “、虚拟表接口a p i ” 和虚拟索引接口a p i “。在i n f o r m i x 提供的技术资料中，一个第二类访问方法 ( s e c o n da c c e s sm e t h o d ) 也是一个索引类型，例如b + t r e e 。而一个虚拟索引 是指一个特定的用户自定义第二类访问方法的索引实例。可以通过提供一个被 i n f o r m i x 服务器使用的函数集来访问和操纵访问方法的多个实例，即虚拟索引。 通过创建新的访问方法，就可以提供对特定数据的用户自定义的访问策略。我 们在i n f o r m i x 中实现了扩展3 dr - t r e e 时空索引。论文最后给出了实现过程和 集成测试结果。 1 5 本文的主要工作 本文对时空数据库中时态，空间和时空索引进行了系统的研究，并讨论了索 引的性能评估和实现技术。主要的工作及特色为： ( 1 ) 对基于对象关系模型的时空数据库体系结构进行了研究，选取了一种实 用的时空数据库系统实现方案。 ( 2 ) 对时态索引和空间索引两个方向做了扩展，讨论了时空索引的设计思 路。研究了在历史时空数据和活跃时空数据上建立时空索引的区别，最后设计 和实现了一种针对活跃时空数据上的时空索目l ，并给出了试验结果评估和性能 分析。该索引相对己有的同类型索弓l 能有效地提高查询效率和节省磁盘空间， 能较好的支持多种时空操作，同时具有较好的适应性。 ( 3 ) 研究了在大型商用对象关系数据库中集成用户设计索引的相关技 术，设计并实现了部分时空操作和支持这些操作的索引，并给出了测试结 果。所实现的索引和数据库紧密集成。它在提高查询性能的同时，还支持 数据库的并发与恢复机制。 本文第二章重点讲述了时空数据库，时空模型和时空数据库实现技术。 第三章介绍了时空索引技术，详细地描述了时空索引的规范定义以及我们 提出的扩展3 dr t r e e 的设计、实现和性能分析。第四章给出了一个索引 性能评估基准。它给出了测试数据的生成过程和对索引性能的评价方法。 中国科学技术大学硕士论文时空数据库索引研究 利用此基准，我们对提出的时空索引和已有的时空索引从时间和空间的角 度进行了比较，并给出了比较结果的说明。第五章介绍了如何将提出的索 引技术集成到大型对象关系数据库中。论文最后进行了总结和提出了下一 步的工作目标。 中国科学技术人学硕士论文 时空数据库索引研究 第二章时空数据库 2 1 引言 具有管理对象空间和时态属性能力的数据库分别称之为空间数据库和时态 数据库。能描述和管理对象空间状态如形状大小、位置坐标等随时间变化的数 据库则称之为时空数据库。 为了说明时空数据库的具体引用，这里以动物研究中的候鸟迁移应用来说 明。科学家跟踪候鸟的迁移，保存迁移过程中各个时刻的位置记录，并以( i d ， 1 3 x ，1 3 y ，t ) 的形式保存起来。其中i d 是被跟踪的候鸟标记，1 3 是位置记录， t 是记录时间。在积累相当多的数据到时空数据库后，为了某些特定的科研需要， 用户可以向数据库递交查询，如找出在t 。时刻经过矩形区域( x 。，y ，x 。y 2 ) 的候 鸟，在时间t 。到t 。期间离目标0 ( x ，y ) 最近的候鸟记录。时空数据库提供相应的 数据类型描述保存候鸟的迁移记录，给出相应的时空查询语句满足以上查询， 并能同时提供相应的机制优化查询性能。 在以往的研究中，空间和时态数据模型作为各自独立的领域进行研究。空 间数据库的研究集中于如何对数据库中的几何对象建模和查询处理。研究者们 提出了用转换，重叠，裁减和分层处理等存取访问机制对多维几何对象( 如点， 线，面和立方体) 进行存取访问。但在这些过程中，却没有考虑到时间的因素。 关于空间数据的存取方法比较可以参阅g a e d e 和g u e n t h e r 的调查报告。 时 态数据库则在保留当前现实世界状态的同时，还记录了对象的历史信息。在时 态数据库中有两种时间概念，即事务时间和有效时间。事务时间是指当某个对 象状态记录进入数据库的时间，而有效时间是该对象状态在现实世界中变为有 效的实际时间。时态访问方法都没有特别考虑所访问对象的空间属性。一个时 态数据库系统至少应该支持两种时间概念中的一种。按照对时间概念的支持程 度划分，可将时态数据库分为事务时间数据库，有效时间数据库和双时态数据 库。更详细的关于时态数据库存取访问方法的可以参阅s m z b e r g 等的调查报告 【2 】 时态数据库和空间数据库都是数据库研究的两个重要方向。随着对两个领 域的研究的深入和成熟，二者的结合也就是必然的事情。许多应用如地理信息 系统( g i s ) ，多媒体技术和环境信息系统中需要管理随时间变化的空间对象，这 些都对时空数据库的深入研究提出了要求。 时空数据库是一个包含了时态数据，空间数据和时空数据，并能同时处理 数据对象的时间和空间属性的数据库。根据对象的空间特征来划分，有三种不 中国科学技术人学硕士论文 时空数据库索引研究 同的时空数据库应用： ( 1 ) 应用中仅涉及到对象的连续运动。例如对于一个交通监控系统，仅对车 辆运行情况，即位置关系感兴趣，而车辆的形状是不感兴趣的。也就是说，此 类应用中主要处理对象的位置随时间变化的情况，如图2 一l 。 ( 2 ) 应用中主要涉及到对象本身的变化。例如地籍管理中，土地大小面积随 时间变化。例如g i s 系统中河流，道路的变化等，如图2 2 。 ( 3 ) 既涉及到对象的连续运动，又涉及到对象本身形态的不断变化。这是最 复杂的一类情况。如在环境信息系统中对风暴移动过程的描述，风暴本身的形 念，密度和位置在不停地随时间变化。 图2 1 ：随时间位置变化的运动目标图2 2 ：随时间形状变化的区域目标 根据时态特征来划分，可以分为基于事务时间的时空数据库，基于有效时 间的时空数据库和双时态时空数据库。其中时间的定义和时态数据库中的时态 定义一致。 本章将着重讨论时空数据模型和时空数据库的实现技术。选择合适的时空 数据库体系结构和实现方案，为时空索引的实现和性能发挥提供了好的基础。 2 2 基于对象关系模型的时空体系结构 在时空数据库系统的实现中，我们采用了从对象关系数据库管理系统上进 行时空扩展的策略。对象关系数据库管理系统提供了用户定义数据类型( u s e r d e f i n e dd a t at y p e ，u d t ) 以及用户定义过程( u s e rd e f i n e dr o u t i n e ，u d r ) 的扩展功能，因此，可以在对象关系数据库系统上扩展新的时空数据类型和时 空操作，同时可以将时空索引通过u d r 和其它插件技术扩展到系统中。这种实 现方式极大地减低了时空数据库管理系统的实现成本，同时可以充分继承对象 关系数据库的强大功能。 2 中国科学技术人学硕十论文 时空数据库索引研究 我们在对象关系模型上建立了一个时空数据模型，称之为时空对象关系模 型( s t o r m ) 。该模型采用对象关系模型来表示时空数据。该模型中空间数据，时 态数据以及时空数据用抽象数据类型( a d t ) 的形式表示，主题数据则用普通的 数据类型表示。时空抽象数据类型( 包括空间抽象数据类型和时态抽象数据类 型) 以对象的方式进行组织，数据库模式则是以关系形式表示。图2 3 表示了 一个时空实体 旧r i m a y t h e m a t i c s p a t i a l s p a t i o t e m p o r a l v a l i dt i m e a t t r i b u t e sa t t r i b u t e sa t t r i b u t e sa t t r i b u t e s ( c h a r ，i n t e g e r ，)( p o i n t ，l i n e ，)( s t - p o i n t ，s t - l i n e ，)( i n s t a n t ，p e r i o d 。) t r a n s a c t i o nt i m e a 廿r i b u t e s p e r i o d ) 图2 3 ：时空实体 在扩展对象模型中。定义了三类时空a d t 和1 2 个空间操作和7 个时态操作。 三类时空a d t 是空间数据类型、时态数据类型和时空数据类型，如图2 4 所示。 黔p o i n t , l i n e , 船s t r i n g , 黜c h r o n o n , i n m e n s t a n 。t | 嚣粼t - l i n e , s t 凛- s t r i 罗n 图2 4 时空a d t s 时空操作是数据库管理系统操纵时空数据的手段，时空操作定义如图2 5 ： 空间捞作 。88。9decompose,。compos。：。isnjolaininst,intersect e x c e p ta r e al e n g t h m e e t ，。v e r i a p ， 空间搽作。 。 二。” p e r i m e t e r 。 时态操作 u n i 。n i n l e r s e c l ；茧热；翟兽j n ，e q u 8 i 图2 5 时空操作 2 3 时空查询 2 3 1 时空查询分类 最基本的空间查询是窗1 ：3 查询。1 ，它返回所有和查询窗口相交的空间对象a 空间查询再加上时态限制就形成了时空查询。时空查询是包含对时空数据特点 1 3 中国科学技术大学硕士论文 时空数据库索引研究 的查询，可以大致地分为三类： ( 1 ) 时间片窗1 ：3 查询：q = ( r ，t ) ，其中r 是在t 时刻的一个超立方体，即一 个空阳j 窗口。如图2 6 所示，查询t ；时刻与矩形相交的所有空间对象。一个简 单的例子就是在交通监控数据库中查找t 时刻在区域r 内所有交通车辆。这是 最简单也是最常用的时空查询。可以把它看作空间数据库中的空i 刨选择操作和 时态数据库中的时间片选择操作的积。 ( 2 ) 时间段窗口查询：q = ( r ，t ，t ! ) ，如果r 是n 维空问的超立方体，r 和时 问区间t t ! 构成n + l 维的超立方体。同样的以交通监控为例，此查询返回在时 划l 到t ! 之间经过区域r 的所有交通车辆。可以把它看作空间数据库中的空间 选择操作和时态数据库中的时间段选择操作的积。 ( 3 ) 移动查询：q = ( r ，r ：，t ，t ：) 指定了在n + l 维空间上的超台体。这 里是指区域的面积在t 。时刻为r 、，到t ：时刻变为r 2 。如森林火灾中的火灾面积 从t 。时刻的r 。蔓延到t ：时刻的r ：，查询此过程中遭到焚烧的树木。 2 3 2 时空查询优化 图2 - 6 时间片时空查询 查询优化包括逻辑优化和物理优化，逻辑优化对查询进行语法分析，并使用 关系代数运算改进逻辑查询计划，找出代价最小的查询计划。物理查询优化是 根据具体的系统资源，硬件性能给出衡量代价参数。传统的物理查询操作的实 现有如下几类：基于排序、基于散列、基于索引。对于多维数据类型的二元操 作，使用基于排序或是散列的i o 操作量很大，必须基于索引的算法。 时空数据库管理系统中，不但有复杂的时空数据类型，还有复杂的时空操 作。虽然当前的主要商业数据库都提供自定义类型与操作的功能，但这种扩展 中国科学技术大学硕士论文 时空数据库索引研究 功能并没有改变查询优化器，也就是说查询优化器并没有提供相应的优化机制。 在这种优化器中，复杂类型的操作和简单类型的操作是等价的，所以创建一个 时空查询优化器以提高查询效率就显得非常重要。 目前国内外对时空查询优化的研究尚属于起步阶段，大都是局限于时态查 询优化或者空间查询优化。文献 4 提出了一种实现时态查询处理的中间件技 术，孩中间件把查询处理分成复杂时态操作和简单操作两部分。复杂的时态操 作由中阳j 件处理，而简单的操作则交给底部数据库实现，通过这种方法可以提 高时态查询优化的效率。 当同时操作于空间和时态数据时，仅用当前商业数据库的优化机制达不到优 化的效果，因此，有必要实现一个扩展的时空优化器。虽然到目前为止，国内 外针对时空数据的查询优化技术还很少，但根据所奄到的文献可知，时空数据 库的查询优化主要考虑下面几个方面：1 ) 开发有效的策略来处理空间、时态和 时空数据；2 ) 开发有效的代价模型。 当前常用的查询优化器产生器主要有s t a r b u s t ，v o l c a n o 和o p t + + 。 s t a r b u r s t 通过两步对查询进行优化；先是使用启发式规则把查询转换成一 个等价的新查询；接若使用类似语法的产生规则指定查询处理的方法。这种方 法的缺点是：在第一个阶段中，因为使用的是启发性规则，并没有估计代价， 生成的等价查询有可能效率较低。而在第二阶段中使用的类似语法的规则建立 的计划只适合于列举带有连接操作的访问计划，当查询中包含非关系的操作和 复杂的转换时。这种方法就无法使用。 v o l c a n o 的查询过程也有两步：对于一个查询，它先使用代数等价规则把该 查询的操作树转换成等价的操作树，接着使用实现规则来确定使用哪些算法来 实现不同的算符。 o p t + + 使用了面向对象的设计。因为在o p t + + 中，“搜索策略”、“代数”和“搜 索空间”都是用虚类实现，所以使用这种设计不但易于扩展查询代数，而且对 搜索空间、使用的搜索策略方面的工作有相当程度的简化。 时空查询优化器的流程图如下： ! 旦型兰燮兰堡主迨塞 堕至墼堡壁室型婴窒 图2 7 时空查询优化器的流程图 2 3 3 时空查询优化的实现 1 ) 实现查询分析器 查询分析器虽然不是优化器的一部分，但它关系到了优化器的输入，所以 有必要先实现查询分析器。实现该分析器的关键是要了解时空数据类型及时空 操作。 2 ) 实现逻辑计划产生器 实现逻辑计划产生器的难点是研究时空转换规则。时空转换规则与传统的 转换规则不同，在传统的转换规则中不需要考虑谓词操作，但时空数据库中却 有大量的复杂谓词操作，所以在研究时空转换规则时要考虑时空谓词操作。在 实现逻辑计划产生器的过程中，先把查询分析器传递过来的分析树转换成代数 形式，也就是逻辑计划，再利用转换规则对该逻辑计划进行改进，然后把它们 传递给物理计划产生器。 3 ) 实现物理计划产生器 实现逻辑计划产生器的难点是确定代价模型。代价模型是根据系统目录提 供的信息用公式描述不同算符的代价。在实现这一步前要先了解时空索引，确 定搜索策略。物理计划产生器接受逻辑计划后，根据时空索引和搜索策略把逻 辑计划转换成物理计划，再根据代价模型计算不同计划的代价，并选出具有最 小估计代价的物理计划进行输出。 中国科学技术人学硕士论文 时空数据库索引研究 对于时空查询优化器的各部分，使用c c + + 来实现。现在关于查询优化过 程中的算法很多，而且有些还能从互联网上找到源码，同时新的可用于简化查 询优化实现的工具不断地被推出。由于o p t + + 酐j 良好的可扩充行和可移植性， 在实现过程中采用了o p t + + 。 2 4 时空数据库的实现 2 4 1 体系结构 研究者们提出了许多关于时空数据库体系结构的设计，这些体系结构主要 借鉴了空间数据库和时态数据库中的研究成果，但都具有一些不足之处，难以 保证时空数据库管理系统的有效实现。时空体系结构的不完善对时空数据库管 理系统的实现造成了很大的困难，因此需要研究一种更有效的时空体系结构。 好的时空体系结构应着力于解决如下关键技术： ( 1 ) 具有优化型时空体系结构。1 。该结构结合了扩展型时空体系结构和层 次型时空体系结构的优点，同时又克服了这两种结构的主要缺点，综合考虑了 时空数据库管理系统实现的便利性和数据查询性能。 ( 2 ) 基于对象关系模型进行时空体系结构的设计。对象关系模型综合了面 向对象模型和关系模型的优点，比面向对象模型更易实现和实用化，同时又具 有比关系模型更强的表达能力。目前主流的数据库厂商如o r a c l e ，i n f o r m i x ， i b m 都推出了自己的对象关系数据库管理系统，因此采用对象关系模型为基础 进行时空数据库系统实现也具有更强的生命力。 ( 3 ) 能以时空对象关系模型为基础对对象关系数据库管理系统进行扩展， 使模型与体系结构之间的衔接更为流畅。基于时空对象关系模型的体系结构可 以有效地表示和操纵时空数据，并具有很好的时空表达能力。 优化型时空体系结构沿用了对象关系数据库管理系统扩展的基本思想。时空 数据类型和时空操作采用扩展技术注入到底层对象关系数据库管理系统的内核 中，使其能够有效表示和操纵时空数据。另外，由于时空数据是一类复杂的高 维数据，如果不对时空查询采取特定的优化处理，时空数据库的性能将无法满 足应用的需求，因此必须考虑时空查询优化问题。但由于扩展型时窆体系结构 中底层数据库管理系统的查询优化规则不可更改，无法使用一般的扩展技术进 行扩展， 因此可以增加一层查询优化层来完成对时空查询的逻辑优化，物理优化则仍 通过底层扩展的时空索引技术来实现。由于在这种新的时空体系结构中，时空 查询优化层只负责查询的逻辑优化，都按照时空查询优化算法和时空查询转换 规则重写查询，不需要对查询语句进行类似层次型时空体系结构那样的翻译， 中国科学技术大学硕士论文时空数据库索引研究 因此，时空查询优化层不会导致层次型体系结构中的效率瓶颈问题。优化型时 空体系结构如图i - 8 所示。 2 4 2 实现技术 廊 m i o r s o l慧t ；坡洲 l i 滋滋瀛鎏囊瀛蘸鋈j 簇蒸 o r s q l躬蒙父茉璇势： 1 名笛邕函 图2 - 8 优化型时空体系结构 我们使用了i n f o r m i xd y n a m i cs e r v e r 作为基础数据库管理系统，以 i n f o r m i xd a t ab l a d e 和c 语言为主要的扩展工具进行时空数据库管理系统的 实现。在实现的过程中，我们还将结合卫星对地观测数据融合应用对时空数据 库的实际应用进行探讨。 对象关系数据库管理系统的时空扩展，包括时空数据类型的扩展、时空操作 的扩展，时空索引的扩展( 时空索引的扩展和时空操作的扩展类似，也通过u d r 来实现以及时空查询优化层的实现。时空扩展的基础是一个有效的时空数据模 型。我们提出了一个新的时空对象关系模型( s t o r m ) 附。该模型采用对象关系 模型来描述时空数据和时空操作。在该模型中，空间数据、时态数据以及时空数 据以抽象数据类型( a d t ) 的形式表示，主题数据则以普通的数据类型表示。时 空a d t ( 包括空间a d t 和时态a d t ) 以对象的方式进行组织，数据库模式则以关 系形式表示。 时空a d t 和时空操作的扩展结构如图2 9 所示。其中c 函数库是实现时空数 据类型和时空操的代码库，可以在运行时被链接到数据库管理系统中。时空扩 展模块提供了对对象关系数据库管理系统的时空支持，一旦被注册到底层的数 据库管理系统中，就成为了底层数据库管理系统内核的一部分，不需要提供任 何的外部模块来完成对时空数据的支持。时空扩展模块一般用c 语言编写，并 且依赖于c 函数库。它也可以包含一些由s q l 语言编写的函数。时空扩展模块 中国科学技术人学硕士论文 时空数据库索引研究 被注册后，用户应用就可以通过s q l 方便地获得时空数据管理的支持，不需要 任何额外的工作。 图2 - 0 时空a d t s 和时空操作的扩展 2 5 本章小结 本章首先给出了时空数据库的描述和定义，提出了在对象关系系统上实现时 空数据模型，包括实现时空数据类型和时空操作。定义了时间片时空查询，时 间段时空查询和移动时空查询。给出了实现时空查询的关键技术。最后给出了 在对象关系模型上实现一个时空数据库体系结构的框架。 中国科学技术大学硕士论文 时空数据库索引研究 3 1 引言 第三章时空索弓 目前国内对时空数据库索引研究尚属于起步阶段，大都是局限于时念索引 或者空阳j 索引。国外对时空索引研究在近年十分活跃，并已经针对不同类型的时 空数据提出了一些索引算法。时空索引的研究发展基于如下几个方面： a ) 对空间存储结构的合适扩展，提出适合于运动的空间对象的存储结构。 b ) 关于测试基准的研究 c ) 对纯空间或时态的研究和扩展。 时空数据库管理系统应当可以有效的支持时空数据检索。要达到这个目的， 现存的多维数据访问方法需要被扩展。数据库研究者们在这个领域已经作出了 相当多的工作。对r - t r e e s 和q u a d t r e e 进行扩展是时空索引研究的两条重要的 途径。在时空索引的性能测试中，研究者使用合成数据集做了大量的试验工作。 关于对时空索引测试基准的最早研究可参见文献 9 。该文引给出了时空索 引应当满足的的基本规范，同时根据其定义的规范对已经提出的时空索引给出 了比较，着重分析了时空对象表达，查询处理和索引维护三方面的问题。接下 来，一个集成了存取访问方法，数据产生，查询处理和结果分析的基础环境被 给出。在文献 1 0 中设计和实现个评估时空查询处理策略的平台，并用它来 评估了时空连接查询策略。 在空间结构研究方面，研究者已经提出了许多基于层次规则空间分解且具 有区域重叠或非重叠特征的有效空间数据访问方法。在某些情况下如果要进行 批操作，如需要批量插入数据或连接操作，如果采用对待单个数据项的方法重 复操作，这显然是很低效的。文献 1 1 给出了一个通用的桶装入算法，该算法 既可用于空间索引，也可用于非空间索引。该算法具有外部排序相同运行时间， 是渐进最优的。 在时态研究方面，文献 1 2 提出了采用重叠b + - t r e e 用来构造事务时间索 引。文献 1 3 中提出了一个使用渐进最优的方法支持事务时间。一些研究者在 r - t r e e 的基础上开发了一些新的算法。如g r t r e e 允许其索引中的数据区域和 树中的对象外接区域能随时间膨胀。该索引可以有效地索引一般的双时态数据 ( 数据项支持事务时间和有效时间) , - i