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

江苏大学顾士学位论文 摘要 随着移动计算、全球定位系统、g i s 等相关技术的发展，数据库需要存储和 管理大量现实世界中带有时空信息的物理对象，并且它们的空间位置或范围会随 着时间的变化而变化，促使时空数据库发展。时空数据库的应用范围遍及交通( 如 车辆监控) 、气象监测、军事等多个领域。在时空数据库系统中，索引机制是保 证对时空对象进行有效存取的关键技术，已成为时空数据库研究的焦点。 目前还没有一种普遍应用于所有需求环境且高效的时空索引技术。基于r 树的3 dr - t r e e 把时间看作空间的另一维，其查询过程十分直观，避开了时间查 询和空间查询之间的区别，较适合于表示位置和范围均不随时间发生变化或变化 较小的时空对象，但是它没有考虑时间维的特殊性，只能处理离线数据，而且对 于那些长期保持静止的对象，会形成许多长条的立方体，使得索引性能大大下降。 为此，本文提出优先考虑沿着时间轴分裂方法，来减少索引中长条立方体的数量； 通过将历史数据和在线数据分开索引的方法，实现对“在线”数据的索引，最终 形成3 dr - g e e 的扩展版3 dr + t r e e ，并提出一种新的代价模型，优化3 dr * - t r e e 。 该索引比3 dr t r e e 时间性能提高4 0 。时间段查询比h r - t r e e 查询提高3 0 ， 时间片查诲略低，但空间使用减少了4 0 0 , 5 左右，最好实现了3 dr t r e e 与数据库 的集成，成功实现了时空数据库的索引。 本文研究的主要贡献如下： 1 ) 提出了“分裂机制”，对历史演变周期长的时空对象优先沿时间轴分裂， 很大程度上减少了时空对象数据集的密度，提高索引效率。 2 ) 根据在线数据的特点，建立两个3 dr - t r e e ：活跃3 dr - t r e e 和历史3 d r t r e e ，使得索引机制能索引在线数据。 3 ) 结合“分裂机制”和双3 dr - t r e e ，提出3 dr + - t r e e ：其能够索引离线数 据和在线数据，且索引性能有明显提高。 4 ) 提出一种新的代价模型，优化3 dr t r e e 。 5 ) 利用i n f o r m i x 数据库服务器的扩展模块d a t a b l a d e 模块，实现了3 d r * - t r e e 与i n f o r m i x 对象关系数据库的集成。 关键词：3 dr + 树，分裂机制，时空索引，在线数据。数据刀片 江苏大学硕t 学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h er e l a t e dt e c h n o l o g i e ss u c ha sm o b i l ec o m p u t i n g g l o b a lp o s i t i o n i n gs y s t e m , g i s ，e t c ，d a t a b a s en e e ds t o r ea n dm a n a g el a r g eq u a n t i t i e s o f p h y s i c a lo b j e c t sw i t hs p a t i o t e m p o r a li n f o r m a t i o ni nr e a l i s t i cw o r l d ，a n dt h e i rs p a t i a l l o c a t i o no rs c o p ew i l l v a r y 、j l ，i t ht i m e w h i c hw i l lp r o m o t et h ed e v e l o p m e n to f s p a t i o t e m p o r a ld a m b a s e t h ea p p l i c a t i o no fs p a t i o t e m p o r a ld a t a b a s es p r e a d so v e r m a n yd o m a i n sa st r a n s p o r t a t i o n ( s u c h 嚣v e h i c l es u p e r v i s i o n ) ，w e a t h e rm o n i t o r i n g ， m i l i t a r ya n ds oo n i nt h es p a t i o t e m p o r a ld a t a b a s es y s t e m ，i n d e x i n gm e c h a n i s mi sa k e yt e c h n o l o g yt oe n s u r et h ee f f e c t i v ed e p o s i ta n dw i t h d r a w a lo ft h es p a t i o t e m p o r a l o b j e c t sa n dt h u sh a sb e c o m et h er e s e a r c hf o c u so fs p a t i o t e m p o r a ld a t a b a s e c u r r e n t l yt h e r ei sn o tah i g h l ye f f i c i e n ti n d e x i n gt e c h n o l o g yw h i c hi su n i v e r s a l l y a p p l i c a b l et oa l le n v i r o n m e n t a lr e q u i r e m e n t s t h e3 dr - t r e e ，b a s e do nr - t r e e ，r e g a r d s t i m ea sa n o t h e rd i m e n s i o n i t ss e a r c h i n gp r o c e s si sv e r yd i r e c t - v i e w i n ga n da v o i d st h e d i f f e r e n t i a t i o nb e t w e e nt i m es e a r c ha n ds p a c es e a r c l lm o r es u i t a b l et ot h e s p a t i o t e m p o r a lo b j e c t sw h o s ei n d i c a t i n gp o s i t i o na n ds c o p ed on o tv a r yo rv a f yl i t t l e w i t ht i m e h o w e v e r , i tf a l l st oc o n s i d e rt h es p e c i a ln a t u r eo ft h et i m ed i m e n s i o i l ，a n d c a l lo n l yh a n d l et h eo f f - l i n ed a t a m o r e o v e r , f o rt h o s el o n g - t e r n ls t a t i co b j e c t s 。m a n y l o n gc u b e sw i l lb ef o r m e d , m a k i n gt h ei n d e x i n gf u n c t i o nd e s c e n dd r a m a t i c a l l y f o r t h i s ，t h i sp a p e rp r o p o s e st h ei d e ao fg i v i n gt h ep r i o r i t yt ot h ec o n s i d e r a t i o no ft h e f i s s i o nm e t h o da l o n gw i t ht h et i m ea x i s ，t or e d u c et h en u m b e ro ft h e1 0 n gc u b e s ；t o r e a l i z et h e o n - l i n e ”d a t ai n d e xt h r o u 曲s e p a r a t i n gt h ei n d e x i n go ft h eh i s t o r i c a ld a t a a n dt h ea c t i v ed a t a , f i n a l l yf o r m i n g3 dr * - t r e e - - t h ee x p a n d e dv e r s i o no ft h e 3 d r - t r e e ，a n dp r o p o s e i n gan e wc o s tm o d e lf o ro p t i m i z i n g3 dr * - t r e e ，w i t hi t st i m i n g f u n c t i o ne n h a n c e db y4 0 ，i t st i m es e c t i o ni n q u i r i n ge n h a n c e db y3 0 c e m p a r e d w i t l lh r - t r e e t h o u g ht h et i m es e c t i o ni n q u i r i n gi ss l i g h t l yl o w , t h eu s eo fs p a c eh a s d m p p e db y4 0 ，a c h i e v i n gt h eb e s ti n t e g r a t i o no f3 dr * - t r e ea n dd a t a b a s e ，c a r r y i n g o u tt h ei n d i c e so f s p a t i o t e m p o r a ld a t a b a s es u c c e s s f u l l y t h em a i nc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s 儿 江苏大学硕上学位论文 ni tp r o p o s e sa ”s p l i t t i n gm e c h a n i s m ”f o rt h es p a t i o t e m p o r a lo b j e c t sw i t l la l o n g t i m eh i s t o r i c a le v o l u t i o n , s p h tt h e mf i r s ta l o n gt h et i m ea x i s ，c o n s i d e r a b l y r e d u c i n gt h ed e n s i t yo ft i m eo b j e c td a t as e t sa n di m p r o v i n gt h ei n d e x i n g e f f i c i e n c y 2 ) a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fo n l i n ed a t a , e s t a b l i s h e st w o3 dr - t r e e ：a c t i v e 3 dr - t r e ea n dh i s t o r i c a l3 dr - t r e e ，w h i c he n a b l e st h ei n d e x i n gm e c h a n i s mt o i n d e xa c t i v ed a t a 3 ) c o m b i n i n gt h e ”s p l i t t i n gm e c h a n i s m ”w i t hd o u b l e3 dr - t r e e ，p r o p o s e s3 d r - t r e e ：i tc a ni n d e xo f f i i n ed a t aa n do n l i n ed a t a , a n di n d e x i n gp e r f o r m a n c e i m p r o v e sr e m a r k a b l y 4 1i tp r o p o s e san e wc o s tm o d e lf o ro p t i m i z i n g3 dr * - t r e e 5 ) u s i n ge x p a n s i o nm o d u l eo fi n f o r m i xt h ed a t a b a s es e r v e r - d a t a b l a d em o d u l e ，i t h a sr e a l i z e dt h ei n t e g r a t i o no f3 dr * - t r e ea n dt h ei n f o r m i xo b j e c td a t a b a s e k e yw o r d s ：3 dr * - t r e e ，s p l i t t i n g m e c h a n i s m s ，s p a t i o t e m p e r a li n d e x ，o n l i n ed a t a , d a t a b l a d e 】l l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口在年解密后适用本授权书。 本学位论文属于 不保密幽 学位论文作者签名；f 蓟寻叫 签字日期：五砷年石月，户 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：a 乎酬 日期：浙7 年厂月fp 日 v 江苏大学硕七学位论文 第一章绪论 伴随着信息化革命的深入发展，新的科学技术的发展同新世纪的脚步发展形 影不离。在当今强劲发展的互联网世界，无线技术与定位技术相互结合，共同发 展，使现在的应用程序能够处理移动的对象的位置数据，比如车辆、无线设备的 用户、海上运输等。也有其他的一些非时空对象应用程序依靠无线定位技术来取 样一些连续的、多维的变量信息。这类应用程序都建立在大量时空对象信息的收 集的基础之上，于是空间时问数据库( 简称时空数据库) 就产生了。时空数据 库用来管理大量动态数据对象，在现在出现的大量处理动态对象的应用程序中越 来越重要( 比如，交通控制、气象监测、移动计算等) 。这类系统可以分为三大 主要应用类型：对时空对象的历史数据、当前数据以及将来数据进行索引。本文 重点研究对时空对象的历史数据、当前数据进行索引，亦即假设数据库中存储时 空对象历史和当静的位置数据信息，使用这些数据信息，索引可以回答对过去某 时间点( 段) 和当前时刻的查询。 1 1 研究背景 管理对象空自j 和时态属性的数据库分别称之为空间数据库和时惫数据库，管 理空间状态如形状大小，位置坐标随时间变化的对象的数据库则称之为时空数据 库。时空数据库从九十年中期开始引起了数据库研究工作者的极大兴趣。经过十 余年的发展，在时空本体论，时空数据模型，时空查询优化和时空索引技术等方 面取得了很大的进步。现实世界中有许多实体具有时空特征，如交通监控的车辆， 森林火灾的火灾区域和动物研究中的候鸟迁移等，需要使用时空数据库来管理。 由于时空数据库里的数据随时间不断地积累，尺寸十分庞大，因此建立有效的索 引结构来访问这些数据非常重要。时空数据库管理系统应当可以有效支持时空数 据捡索。要达到这个目的，需要对现存的多维数据访问方法进行扩展。数据库研 究者们在这个领域己经作出了相当多的工作。对r t r s 【l l 和q u a d t r e e 2 1 扩展构建新 的索引是时空索引研究的两条重要的途径。在时空索引的性能测试中，研究者使 用合成数据集做了大量的试验工作，并考虑了在大型对象关系数据库上实现提出 江苏大学硕士学位论文 的时空数据模型和索引。 虽然时空数据处理对于现实世界建模非常重要，但是由于时空数据的复杂 性，目前好的时空索引却不是很多。索引的研究多集中在支持多维数据的纯空间 索引研究和对于一般传统数据类型如( 数字，字符串) 上的时态索引上。由于r 树及其变体在空间索引上的优势，在过去十年曩，研究者们提出了许多基于r 树 的时空索引版本，可以把它仍大致分为如下几类：( 1 ) 把时间维当作空间的另一 维处理 3 1 ；( 2 ) 把时间信息集成到空间索引结构的节点中去，而不认为它是另外 一维【4 ；( 3 ) 使用重叠索引结构来表达数据库在不同时刻( 事务时间或是有效时 间) 的不同时间状态5 1 6 1 。假定时间维当作空间的另一维处理是一个最简单的想 法，处理多维空间数据的索引技术比较成熟，例如r 树以及其变体。3 dr t r e e 3 1 的实现过程中认为时间是二维空间之外的另一维，简单地把二维空间转换成三维 空间最小外接立方体。t z o u m m a n i s t 阴等人提出的基于四分树的时空索引方案也 是采用了多版本技术。区域四分树是对二维二值光栅图象分解成一系列的四分象 限( q u a n d r a n t ) ，每个象限具有2 x 2 个象素。如果某部分不是完全全黑或者全 白，则该部分需要递归分解成四个子象限，直到每个子四分块具有同一种颜色为 止。基于四分树的技术对于珊格图象的索引更为有效，但是对于空间矢量化的对 象不是很有效。本文主要探讨了对基于r 树算法的时空索引的扩展，以满足更多 应用。在第三章中，给出了对3 d r - t r e e 的扩展，并给出了设计和实现过程，以及 详细的性能评估。时空数据库涉及到对静态或动态的空间对象的有效操作，因此， 它必须能有效地支持该类型数据。研究者对一些多维访问方法进行扩使得它们能 够支持索引和检索时空数据，从而满足用户要求。为了客观地比较这些提出的索 引访问机制，还有必要从对象的表达、查询处理和索引维护方面给出一个时空索 引应当满足的基本规范。 目前大多时空索引算法对于时空数据库查询都有一些局限性，它们要么只针 对某些的数据类型，要么索引数据存储空间十分庞大。目i i 时空索引研究着重于 从三个方面展开： ( 1 ) 支持多种数据类型和数据集，如空间对象有点目标、区域目标等，对象 的运动方式有连续运动、非连续运动等。 ( 2 ) 支持多种索引构造方式。索引结构的构造可以是在数据库批量载入数据 2 扛苏大学硕士学位论文 时批处理构造，也可以是事务处理时动态的构造。好的索引结构应该可以支持两 种构造方式。 ( 3 ) 支持多种查询。时态数据查询有时间片和时间区间之分，而空间数据的 查询有空间范围查询、最邻近查询和空间连接等，二者的结合使得时空查询种类 十分丰富，应该设法找到好的时空索引结构支持多种查询。 在应用开发方面，许多具有市场潜力的涉及至0 复杂数据库技术的应用，如地 理信息，医疗，空间信息和多媒体应用都需要有对新的复杂的数据类型的有效支 持。因此，主要的数据库厂商在他们提供的数据库系统中不再仅仅满足提供简单 二进制对象( b l o b s ) ，而是提供了更多的扩展特色。这些特色包括允许用户添 加他们自己的数据类型和访问方法。现在比较流行的方案包括d b 2e x t e n d e r ， i n f o r m i xd a t a b l a d e 和o r a c l ee a r t r i d g e s 。对于时空数据库研究者来说，一个可扩展 的系统提供了新的机会，使得开发大的复杂应用成为可能。 1 2 研究内容和目标 许多现代的基于时空对象的索引技术大多从g u t m a a n 提出的r 树空问索引 发展过来。虽然r 树索引在商业中得到广泛的应用和发展，但是由于时空对象 随时间的积累，数据量十分庞大，它的查询效率越来越跟不上应用技术的发展。 因此建立高效的索引结构来访问这些数据非常重要。 建立高效的索引结构是为了更好的在现实中应用，单独的在数据库系统外实 现索引不能真正的评价一个提出索引的实际性能。因此在一个对象关系数据库中 实现提出的索引更能客观地观察和评价该索引的性能，并使之具有更广泛的应用 价值。 针对以上所述，本文主要对如下几方面内容进行了研究，具体概括如下： 1 1 时空数据库概述。具体分析时空数据库的时空对象表达、时空数据建模、 时空数据库体系结构、时空数据查询、时空数据索引等各个研究方向的 研究进展。 2 ) 在分析3 dr t r e e 算法的优缺点的基础上，对3 dr - t r e e 进行扩展。要解 决几个问题：a ) 如何进行扩展? b ) 如何使得扩展后的3 dr - t r e e 可以索引 在线数据? c ) 扩展后索引的各项性能如何? 江苏大学颂上学位论文 3 ) 利用i n f o r m i x 数据库服务器的扩展模块d a t a b l a d e 模块，如何实现3 d r * - t r c e 与i n f o r m i x 对象关系数据库的集成? 通过上述四个方面内容的研究，达到如下的研究目标： i 建立3 dr * - t r e e ，使得其能够索引在线数据，且在索引的各项性能比 3 dr - t r e e 有很大的提高。 i i 实现3 dr + - t r e e 与i n f o r m i x 对象关系数据库的集成，并测试集成后 的索引性能，体现此索引算法的实际意义。 1 3 本文组织结构 本文的以下内容编排如下：第二章详细阐述目前时空数据库各个方向的研究 进展，即主要从时空对象表达、时空数据建模、时空索引、时空数据查询、时空 数据库体系结构、时空数据库原型系统、时空数据库应用、进一步研究等几方面 进行具体论述；并对一些主要的时空索引方法进行简单的性能评价与分析比较。 第三章提出的扩展3 dr t r e e 的设计、实现和性能分析。第四章介绍了在时空对 象关系模型( s t r o m ) s l 下，如何将提出的索引技术集成到大型对象关系数据 库中。论文最后进行了总结和提出了下一步的工作目标。 4 江苏大学硕士学位论文 2 1 引言 第二章时空数据库技术 第一章主要讨论进行时空数据库及其索引技术研究的背景及本文将要研究 的具体内容和研究目标。本章就对时空数据库的时空对象表达、时空数据建模、 时空数据索引、时空数据查询，时空数据库体系结构、时空数据库原型系统、时 空数据库应用等研究方向的最新研究进展做一具体讨论。 2 2 时空数据库概述 时空数据库( s p a t i o - t e m p o r a ld a t a b a s e s ，s t d b ) 在二十世纪八十年代末开 始受到人们的重视。时空数据库是时态数据库( t e m p o r a ld a t a b a s e s ，t d b ) 与空 间数据库( s p a t i a ld a t a b a s e s ，s d b ) 的统一体，即包括时间与空间要素，主要用 于存储与管理位置或形状随时闻而变化的各类空阗对象。时空数据库的研究内容 相当丰富，主要涉及时空对象表达、时空数据建模、时空数据索引、时空数据查 询、时空数据库体系结构等，同时时空数据库原型系统、时空推理、时空查询代 价模型等也为时空数据库的研究带来了一定的挑战。高云君【9 1 等综述了时空数据 库方面的研究。 时空数据库主要是针对对象的时空信息进行分析处理，它通常涉及时空对象 表达、时空数据建模、时空数据库体系结构、时空数据查询和时空数据索引等几 个方面的研究内容。 时空数据库的应用非常广泛，根据时空应用所处理数据类型的不同，将对空 数据库应用主要归纳为如下三类。 1 ) 处理时空对象的应用，如导航系统。 2 ) 涉及到空间对象定位的应用，对象的特征与位置可能随时间而变化，但 却不移动，如在土地信息系统中，土地随形状的变化而改变位置。 3 ) 结合上述两种情况的应用，如在生态环境应用中，污染既作为一个移动 现象而被测量，同时它的特性和形状又随时间而变化。 5 江苏大学硕七学位论文 2 3 时空数据的表达 时空对象表达主要是对时空对象的时间与空间属性进行合理表达，其目的是 在数据库中有效的存储这些对象。下面归纳两种常用的时空对象表达方法。 清晰与确切的表达对象 清晰与确切的表达对象是指在假定时空对象具有边界、对象之间的关系被精 确定义以及对象的位置被确切测定等的基础上来表达对象。例如h o m s b y 等在对 被跟踪对象特性的变化进行分类的基础上，提出一种清晰表达可标识对象状态变 化的时空对象表达方法。该方法主要由原语集与操作集组成，其中原语主要包括 对象特性状态( i d e n t i t ys t a t e so f o b j e e t s ) 与变迁( t r a n s i t i o n s ) ，因此它能较好地 表达对象在时间与空间上的变化，并且易于对空间数据模型进行扩展；e r w i g 等 在分析时空对象二维跟踪基础上，提出一种可用于描述时空对象空间关系变化的 表达方法，并能有效地将其转换成时空谓词( s p a t i o t e m p o r a lp r e d i c a t e ) 以描述 对象的空间关系变化。该方法既可直接作为一个查询接口而用于时空数据库，又 可作为时空谓词规约结合到文本查询语言中而得到其它文本查询语言。 模糊与不确切的表达对象 由于大量有关时空应用方面的研究成果都是在假定时空模型中的对象具有 边界、对象之间的关系被精确定义以及对象的位置被确切测量等的基础之上而得 到的。然而现实世界中，对象的实际情况却往往与之不符，即对象之问的边界往 往不是很明显，并且对象之间存在一个变迁( t r a n s i t i o n ) 。例如，在环境系统中 的不同土地地带( 如沙漠与大草原) 是没有精确边界的。此时就需要引入一个模糊 概念，用模糊来描述它们之间的变迁；另外，对于在导航系统中定位一辆汽车的 移动位置，虽然原则上需要精确地定位，但是事实上不可能非常确切地知道其位 置，而是存在一定的误差。此时，就需要引入一个不确定性概念，用不确定性 ( u n c e r t a i n t y ) 描述对象的位置，从而来表达其相对于对象的实际位置的误差。 针对上述情况，一些科研工作者采用了模糊与不确定的方式来表达对象。所谓模 糊与不确定的表达对象是指用模糊与不确定的概念来对对象的各种属性进行表 达。例如p f o s e r 等提出用模糊与不确定性概念来表达时空对象的属性、关系、时 间点、时间段、事件以及变化的方法，并且概述了离散和连续变化的四个场景 ( s c e n a r i o ) 及其如何用不确定性概念来分别对其进行建模。 6 江苏大学硕上学位论文 2 4 时空数据的建模 时空数据建模主要是要建立空间对象的数据模型，以便对时空数据进行索 引、查询等操作。下面本文从时空概念模型、时空数据模型以及时空对象模型三 个方面来进行阐述。 2 4 1 时空概念建模 时空概念模型主要是用来构建对空间对象进行抽象描述所必需的符号与形 式化表示，它是时空数据库系统应用开发的一个重要步骤。下面归纳几种时空概 念模型。 1 ) 扩展现有传统概念模型。 2 ) 基于现有的时空概念模型。 表2 1 时空数据模型的优缺点比较 时空数据模型优点缺点 快照数据模型非常简单数据重复问题 时空复合数据模型减少了数据重复问题 不能区分同一时间段 ( h i s t o r y ) 内的对象 面向事件数据模型部分记录时空对象的变化历史 必须结合状态变化才能 褥剑对象的虽近状态 历史图像模型 可描述空间数据集的变化特性不易描述对象的持续性变化 三域数据模型 能处理空间对象的运动与变化不易实现 面向对象数据模型容易表达时空对象实现困难 2 4 2 时空数据建模 时空数据模型是指建立时空对象的数据模型。一般地，可以通过时态数据库 或空间数据库扩展来对时空数据进行建模。这就意味着时空建模主要有两种方 法，具体如下： 1 ) 在时态数据库中加入空间属性与空间操作来进行时空建模。 7 江苏大学硕上学位论文 2 ) 在空间数据库中加入时间属性与时间操作来进行时空建模。 表2 1 比较了各种时空数据模型的优缺点，在实际应用中，需根据情况柬选 择合适时空数据模型。 2 5 时空数据库体系结构 由于时空应用有许多特殊需求，并且需要处理诸如三维空间中的移动点与移 动区域等的复杂对象，因此设计一个合理有效地支持时空数据库管理系统 ( s p a t i o - t e m p o r a ld a t a b a s e sm a n a g e m e n ts y s t e m s ，s t d b m s s ) 的体系结构是极 其重要的。时空数据库系统的实现结构继承了过去对空间数据库和时态数据库的 研究成果。目前己提出的实现结构主要有三种：完全型实现结构【1 0 1 、层次型实现 结构【1 1 1 和扩展型实现结构【1 2 1 。 2 5 1 完全型实现结构 完全型实现结构直接在操作系统之上实现一个时空数据库管理系统。这种实 现结构需要完全实现一个数据库管理系统中的模块，包括查询编泽与执行、事务 管理、存储管理等，并且为了满足实际应用，还要设计时空数据库的数据驱动程 序。这种结构的实现工作量巨大，而且难以满足一般时空应用开发的需求。 2 5 2 层次型实现结构 层次型实现结构( 如图2 t 所示) 在传统的关系数据库管理系统之上附加了 一个时空层，通过时空层来完成对时空数据的操作，不需要对底层的数据库管理 系统内核进行任何变化，时空层承担了时空数据库语言与s o l 间的翻译、时空查 询优化等几乎所有的时空数据管理工作，所有的时空数据请求都要通过时空层进 行处理。时空查询翻译成s q l 之后将会十分复杂，因而不利于底层的关系数据库 管理系统进行查询优化。而且，时空层也会成为应用开发的瓶颈，因为所有的请 求都要首先通过它转换为标准的s q l 。 江苏大学硕士学位论文 i应用程序 l s t s q l | rl 时空数据 = q l i 关系数据 数据库管理系统 口口口 图2 1 层次型实现结构 应用程序 。r s q li l 对象关系； f 了”篙黼黼鞘黼鬻f 霹 ：玉e 3 黪| | = 茗煎= 】 蘸箍篆j ：纛美豢黧磁繇篡篓羹猫纛懑纛溺 2 5 3 扩展型实现结构 图2 2 扩展型实现结构 扩展型实现结构指的是在对象关系数据库管理系统之上进行时空扩展。图 2 2 表示了这种结构，其中阴影部分是时空扩展。由于对象关系数据库管理系统 提供了用户定义数据类型( u s e r d e f i n e d d a t a t y p e ，u d t ) 以及用户定义过程( u s e r d e f m e dr o u t i n e ，u d r ) 的扩展功能，因此，可以在对象关系数据库管理系统之 上扩展新的时空数据类型和时空操作，并将时空索引也通过u d r 和其它技术扩展 到核心中。这种结构是目前最受关注的结构。扩展型实现结构使得时空数据库管 理型系统的实现和使用成为了可能。但其主要的问题是：虽然底层的数据库管理 系统可以使用扩展的时空索引来加快查询速度，但它对时空查询优化的支持也仅 局限于此。底层的数据库管理系统仍采用关系数据库的查询优化规则来处理一个 时空查询，而这对于时空查询是不适合的。 9 江苏大学顷上学位论文 2 6 时空查询 时空对象表达与时空数据建模是肘空数据库中研究较多的两个问题，而时空 数据查询也是近年来被广泛关注研究热点，它是指对时空数据进行有效查询。下 面归纳几种目前常用的时空查询。 1 ) 窗口查询：给定查询区域q r 和时间间隔q t ，查找所有q t 内与q r 区域相 交的所有对象。w q 的正确估计对于查询优化是必要的。 2 ) k 最近邻接查询：给定查询点q p 与时间间隔q t ，查找所有q t 内与q p 的 距离为最小邻接对象。 3 ) w d j ( w i t h i n - d i s t a n c ej o i n ) 套询：给定两个数据集s 1 与s 2 和两个对象o i 与0 2 ，查找q t 内在s i x s 2 里0 1 与0 2 之间的距离比某个给定阂值d 更小的 对象对( o l ，0 2 ) 。 4 ) k c p ( 1 【c l o s e s tp a i r ) 查询：查找q t 内在s l x s 2 里0 i 与0 2 之间距离为最小 的对象对( o l ，0 2 ) 。 5 ) n a v i g a t i o n a lw q ：对于历史的数据库( h i s t o r i c a ld a t a b a s e s ) ，p f o s e r 等 提出n a v i g a t i o n a lw q ，即给定两个查询区域q r l 与q r 2 和两个时间戳q 丌 与q t 2 查找q t i 内与q r ! 相交以及q x 2 内与q m 相交所有对象。 6 ) i t ( t i m e - p a r a m e t e r i z e d ) 查询：对于预测性的时空数据库( p r e d i c t i v es p a t i o t e m p o r a ld a t a b a s e s ) ，t a o 与p a p a d i a s ! ”1 指出由于对象的运动性可能使由 传统查询( 如w q ，k n n ，w d j ，k c p ) 得到结果发生变化，因此传统 的查询结果对于时空数据库而言是不够的。针对这种情况，他们提出t p 查询。该查询可应用于任何传统查询方法，并且查询结果不仅返回由一 般传统查询得到的结果r ，而且也返回结果r 失效时间t ( e x p i r yt i m e ) 以及在t 后的结果变化c 。随后t a o 与p a p a d i a s 又将t p 概念扩展到连 续查询，其目的是连续跟踪查询结果变化直到满足某个条件为止。 7 ) l b ( 1 0 c a t i o n - b a s e d ) 查询：z h a n g 等提出l b 查询。该查询可应用于w q 和 k n n 查询，并且既可得到查询结果又能得到查询的有效区域。例如一个 l bn n 查询可能既返回一个离旅游者最近的宾馆，又返回一个使该宾馆 保持最近的有效范围。 除了上述所阐述的几种常用的时空查询之外，有些时空数据库的科研工作者 l o 江苏大学硕士学位论文 也在从事时空数据查询代价模型研究。如c h o i 1 4 i 等提出一个使用t p r e e 的时 空查询代价模型：t a o 与p a p a d i a s f 15 1 等提出一个针对重叠b t r e e ( o v e r l a p p i n gb t r e e ) 与多版本b - t r e e ( m u l t i - v e r s i o nb t r e e ，m v b t r e e ) 的代价模型。该模型可以估计查 询树、访问结点以及查询选择大小；最近t a o 与z h a n g 等又提出一个近似描述 n n 查询性能的代价模型。 2 7 时空索引机制 时空索引的主要目的是对时空数据建立各种索引机制，以便有效的访问这些 数据。它是时空数据库研究领域最活跃的研究方向之一，有大量研究者在从事这 方面的研究，提出了许多时空索引技术。本文将时空索引分为三类，即根据时空 索引方法的基本结构和处理的数据将已有的各种时空索引方法分为基于r - t r e e 的、基于q u a d t r e e 的以及其它时空索引技术共三类。下面本文就分别对这三类 时空数据索引进行介绍。 2 7 1 基于r 树的时空索引技术 本文仅仅考虑各种基于r - t r e e 及其变体的时空索引方法。由于时空对象的查 询可能跟时空对象的现在、过去以及将来的位置布局有关，因此本文也将该类索 引技术分成三类：即索引过去、索引现在、索引现在与将来位置。下面就分别对 这三类索引技术及其各自相应索引方法分别进行具体讨论。 2 7 1 1 索目i 过去 根据所处理的时空对象数据的不同，将其分为如下二类： 1 ) 处理时间维：即将时间维添加到己有的空间索引方法( 如r - t r e e ，r - t r e e 等) 中，从而将原有的空间索引方法转变成支持时空的时空索引方法。 目前已提出的属于该类的时空索引方法主要有r tt r e e l l 6 l ，3 dr t r e e ， s t r t r e e 1 7 1 ，以及a p r - t r e e 。 r t - t r e e 是一种混合的索引结构，由于它优先考虑空间信息，而时间信息次 之，因此该索引结构对于时间片查询( t i m e s l i c eq u e r y ) 与时间间隔查询 ( t u n e i n t e r v a lq u e r y ) 的效率比较差，可能需要遍历整棵r t - t r e e 。 江苏大学硕上学位论文 3 dr - t r e e 将时间看作一维，并与二个空间维共同构成三维，故称为三维 r - t r e e 。它可能是一种最简单的时空索引方法，容易实现。其优点是耗费的存储 空间较低，时闻间隔查询效率较高；而缺点是时间片查询性能较低，索引性能随 时间而逐渐地退化( 降低) 。 s t r - t r e e 是对r - t r e e 的扩展，具有不同的插入拆分算法。其主要设计思想是 考虑了时空对象的空间属性与轨迹( t r a j e c t o r y ) 保护，即通过保持属于相同对象 轨迹的直线分段来保持空间的封闭性。s t r - t r e e 可用来索引时空对象的过去( 或 历史) 信息与轨迹信息，其优点是处理基于轨迹查询效率高，并且与r - t r e e 相比 较，它的索引空间大小较小和空间利用率较高。 最新提出的a p r - t r e e 是基于自适应划分技术( a d a p t i v ep a r t i t i o n i n gt e c h n i q u e ) 的时空索引方法，它可以通过自动调整时问片查询和时间间隔查询的工作量来有 效的索引时空对象的过去( 历史) 数据。a p r - t r e e 由多个3 dr - t r e e 组成，并且 把自适应查询分方法( q u e r y a d a p t i v e p a r t i t i o n i n g m e t h o d ) 引入到3 dr - t r e e 中， 每一棵3 dr - t r e e 负责随查询工作量而变化的固定时闯间隔查询。a p r - t r e e 的缺 点是其索引结构容量与更新代价受到查询工作量的影响，即随着时间间隔查询比 率的增加，它的索引结构容量与更新代价反而减少。另外，与3 dr - t r e e 相比较， a p r - t r e e 的索引结构容量比3 dr - t r e e 稍大，但是它们的更新代价却几乎一样。 下面的图2 3 显示一个a p r - b e e 结构。在图中，l i ，l 2 l 1 分别用来表示r l ，r 2 r i 的权限间隔长度；a = 表示一个对象运动的记录，其中的 和t e l d 是该记录插入和逻辑删除时间。逻辑删除用来改变一个活动记录的生命周 期的结束时间。生命周期结束时间用表示的记录是一个活动记录。因为a = 在r l 和r 2 的边界之间相交，所以它被分割成a 1 = 和 a 2 = ，并且分别将a l 和a 2 插入到r l 和r 2 中。因此，当一个记录 生命周期与边界相交时，拷贝记录将会发生。另外，与h r t r e e 索引结构所不同 的是a p r - t r e e 中的相邻r - t r e e 之间不共享结点。 1 2 江苏大学顾士学位论文 a = b o u n d a r y l l = = t 2 - t 1l 2 - - t 3 t 2 l i = “l 一乜 r t t l ，t 2 ) 一 + ) 公4 k r _ l如 t3 t缸 图2 3a p r - t r e e 结构 综上所述，属于处理时间维的各种时空索引方法是将时间维添加到已有的空 间索引方法( 如r - t r e e ，r * - n e e 等) 中，从而将原有的空间索引方法转变成支持 时空的时空索引方法。 2 ) 处理时间与空间维：即在时空索引方法中既考虑时间维又考虑空间维。 目前已提出的属于该类的时空索引方法主要有m r - 慨【埘，h r t r e e 1 8 1 ， h r + t r e e 1 9 1 ，m v 3 r t r e e 2 0 1 以及e x t e n d e dp p r - t r e e 。下面将分析这些索引方法的 优缺点与主要设计思想，并对某些方法进行性能评价与分析比较。 m r - t r e e 将重叠b 树( o v e r l a p p i n gb - t r e e ) 的思想