（计算机软件与理论专业论文）时空数据库数据操纵及查询优化的研究与实现.pdf

华中科技大学硕士学位论文 摘要 时空数据库理论的产生是伴随着现代生产生活的需要而产生的。在许多现实应 用中实体本身及实体之间的时态、空间、时空关系特别是时空关系往往成为人们需 要对实体进行处理的主要方面。时空数据库要处理好实体之间的时空关系必须解决 时态和空间的无缝结合问题。 时态和空间的无缝结合主要体现在如下几个方面：( 1 ) 一种能够方便、有效描 述实体的空间信息随时态变化而变化的过程的数据模型；( 2 ) 一套描述实体之间时 空关系的拓扑理论；( 3 ) 针对相应时空操作的数据操纵策略；( 4 ) 有效的时空索引 机制；( 5 ) 建立在特定时空语义基础上的查询优化策略；( 6 ) 具有时空特性的事务 处理机制。 数据操纵策略和查询优化策略是提高查询效率的两个主要方面。其中，数据操 纵策略的研究主要在：( 1 ) 如何减小空间搜索范围：( 2 ) 如何减少时空运算代价；( 3 ) 如何选择最优的存取路径等三个方面展开。这三个方面是相互影响的。界定和转化 数据操纵中的时空关系是减小空间搜索范围的一条途径，但同时，时空关系的转化 可能会影响时空运算代价和存取路径的变化，因此，如何在这三者中作出有效的权 衡是数据操纵策略的宗旨。 查询优化策略是提高查询效率的另一个方面。目前的数据库理论大多基于关系 数据库理论，关系数据库中的大多数查询优化策略和原则在时空数据库中还能适用， 但必须注意到时空数据库中时态信息和空间信息的特殊性。时空运算的代价不再是 可以忽略不计的c p u 运算时间，必须将减小时空运算代价提高到提高查询效率的日 程上来。时间和空间信息的特殊性还决定了语义查询优化的可行性和重要性，恰当 的获取和运用时态和空间的语义规则，将会为查询优化作出重大的贡献。 时空数据库的查询效率是影响时空数据库理论的推广和应用的主要方厦，研究 高效的数据操纵策略和获取并恰当的运用时空语义规则是在提高查询效率方面的有 益的尝试和探索。 关键词：时空数据库，时空关系，最近邻居，时空语义规则，数据驱动 华中科技大学硕士学位论文 a b s t r a c t t h e a p p e a r a n c eo f t h es p a t i o - t e m p o r a ld a t a b a s et h e o r yi ss t i m u l a t e db yt h er e a l l i f e a p p l i c a t i o n s i nm a n ya p p l i c a t i o n s ，t h et e m p o r a lr e l a t i o n s ，t h es p a t i a lr e l a t i o n s ，t h e s p a t i o - t e m p o r a lr e l a t i o n sa r et h em a i np r o b l e m sn e e d e dt r e a t e dw i t h t h es p a t i o t e m p o r a l d a t a b a s et h e o r ym u s tm a k eg o o dd e a lw i t ht h es p a t i a la n dt h et e m p o r a lr e l a t i o n si no r d e r t oe s t a b l i s ht h ei n t e g r a t i o no f t h e s p a t i a li n f o r m a t i o na n dt e m p o r a li n f o r m a t i o n t h ei n t e g r a t i o no ft h es p a t i a li n f o r m a t i o na n dt h et e m p o r a li n f o r m a t i o nl i e so nt h e u n d e r l i n es i xa s p e c t s ：f i r s t ，t h ed a t am o d e lm u s tb ea b l et od e s c r i b et h et r a n s f o r m a t i o no f t h e s p a t i a la n dt h et e m p o r a li n f o r m a t i o nb e c a u s eo ft h es p a t i a l - t e m p o r a lr e l a t i o n s h i p s ； s e c o n d ，t h ed e f i n i t i o no ft h es p a t i o - t e m p o r a lr e l a t i o n s h i p s ；t h i r d ，t h es t r a t e g yo ft h ed a t a o p e r a t i o n ；f o u r t h , t h es p a f i o t e m p o r a li n d e x i n g ；f i f t h ，t h es p a t i o t e m p o r a ls e m a n t i cq u e r y o p t i m i z a t i o n ；s i x t h ，t h es t r a t e g y o ft h es p a t i o t e m p o r a lt r a n s a c t i o n s 1 1 1 e s t a t e g y o ft h ed a t ao p e r a t i o na n dt h eq u e r yo p t i m i z a t i o na r et h et w om a i n m e t h o d si m p r o v i n gt h eq u e r ye f f i c i e n c y b yn o w , w ec a l lm a k et h er e s e a r c hi nt h eb e l o w t h r e ea p e c t s ：f i r s t ，m i n i s h i n gt h e q u e r y i n ga r e a ；s e c o n d ，d e c r e a s i n gt h ec o s to ft h e s p a t i o t e m p o r a lc o m p u t a t i o n ；t h i r d ，c h o o s i n g t h el o w c o s ta c c e s s i n gp a t h t h ea b o v e t h r e ea s p e c t sa f f e c te a c ho t h e r 1 1 1 ed e f i n i t i o na n dt r a n s f o r m a t i o no ft h es p a t i a lr e l a t i o n si s o n em e t h o dt om i n i s ht h es p a t i a lq u e r ya r e a ，b m ，a tt h es a m et i m e ，t h i sw i l la f f e c tt h ec o s t o ft h es p a t i o - t e m p o r a l c o m p u t a t i o na n dt h ea c c e s s i n gp a t h s o ，t h et e n e to ft h e d a t a o p e r a t i o n i st oc o u n tt h ec o s ta n dc h o o s et h eb e s ts t a t e g y t h e q u e r yo p t i m i z a t i o ni sa n o t h e ra s p e c ti m p r o v i n gt h eq u e r ye f f i c i e n c y n o wm o s t o ft h ed a t a b a s et h e o r yi sb a s e do nt h ec o n v e n t i o n a lr e l a t i o nd a t a b a s et h e o r y ，m o s to ft h e s t r a t e g yo fq u e r yo p t i m i z a t i o nm a y b ea p p l i e di nt h es p a t i o t e m p o r a ld a t a b a s e ，b u t ，w e m u s tr e a l i z et h es p e c i a l i t yo f t h e s p a t i a li n f o r m a t i o na n dt h et e m p o r a li n f o r m a t i o n t h ec o s to f t h e s p a t i o t e m p o r a lc o m p u t a t i o n c a nn o tb ei g n o r e d t h e s p e c i a l i t yo f t h e s p a t i a l a n d t e m p o r a l i n f o r m a t i o nm a k et h a tt h e s p a t i o - t e m p o r a l s e m a n t i c q u e r y o p t i m i z a t i o ni si m p o r t a m a n de s s e n c i a l t h ea c q u i r e m e n ta n dt h er i g h t m a n a g e m e n t o ft h e s e m a n t i cr u l e sw i l lc o n t r i b u t et ot h eq u e r y o p t i m i z a t i o n t h ee f f i c i e n c yo ft h es p a t i o t e m p o r a l q u e r yi s t h em a i na s p e c tw h i c ha f f e c t st h e l i 华中科技大学硕士学位论文 a p p l i c a t i o ni nr e a ll i f e t h er e s e a r c hi nt h ed a t ao p e r a t i o na n d t h es p a t i o t e m p o r a ls e m a n t i c q u e r y i sa nb e n e f i c i a la t t e m p t m e n ti ns p a t i o t e m p o r a ld a t a b a s et h e o r y k e yw 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 lr e l a t i o n s ，n e a r e s t n e i g h b o u r s ，s p a t i o - t e m p o r a ts e m a n t i cr u l e s ，d a t ad r i v e i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果a 尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名 呵套导 日期：圳年等月鸪曰 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不傈密瓯 ( 请在以上方框内打“”) 学位论文作者签名：何蛩唔 日期：抽尹年仁月吗日 指导教师 目期：砂叩年够廖 华中科技大学硕士学位论文 1 引言 1 1 课题研究意义 时空数据库理论的产生是伴随着现代生产生活的需要而产生的。任何实体都有 其时间( 时态) 、空间特性。在许多现实应用中实体本身及实体之间的时态、空间、 时空关系往往成为人们需要对实体进行处理的主要方面。例如：天文、地理信息管 理、城市规划、交通管理、天气预报、生态管理等等，这些应用的共同点是：要求 能够比较真实的记录并处理实体的时态信息、空间信息、空间信息随时态的变化而 发展变化的信息等。这就要求面向这类应用的数据库系统除了能处理基本类型( b a s e t y p e s ) 【1 l 的数据外，还必须能处理空间类型( s p a t i a lt y p e s ) 1 1 ( 描述静态的空间对象的 空间信息) ，时态类型( t e m p o r a lt y p e s ) 】( 描述对象的时态信息) ，时空复合类型 ( s p a t i a l - t e m p o r a l d a t a t y p e s ) 1 1 ( 描述动态空间对象的空间信息随时态的变化而发展变 化的信息) 。但是现有的特种数据库或者只能有效处理时态对象( 时态数据库) ，或 者只能有效处理静态的空间对象( 空间数据库) 口1 ，目前为止还没有能够有效处理动 态空间对象的数据库管理系统产品出现。因此有必要将时态和空间相结合，将时空 作为整体来研究一种新的特种数据库时空数据库【3 1 。 1 2 时空数据库理论研究现状 到目前为止，时空数据库理论大致经历了如下几个发展阶段： 1 将空间信息随时间变化的实体作为静态的空问对象来处理，注重空间信息的处 理，而忽略实体的空间信息和时态信息的关联。这一阶段的主要成果是7 0 年代至8 0 年代末期的g i s 的广泛应用，g i s 的理论基础是空间数据库理论。 2 将实体作为动态的空间对象处理，但是对象的空间信息和时态信息在很大程 度上是相互孤立的，不是一个有机的整体。这一阶段的主要成果是l a n g r a n 和 c h r i s m a n 于1 9 8 8 年时间地理信息系统( t e m p o r a lg i s ，简称t g i s ) 概念的提出，即将 时间特性融入g i s 数据的表示和处理，在同一框架内管理时空数据，t g i s 就是时空 华中科技大学硕士学位论文 数据库的雏形。 3 将实体看作是随时态的变化而发展变化的时宅对象，力求把对象的时态信息 和空间信息看作是有机的整体。这一阶段的主要标志是时空数据库概念的明确提出。 但是从9 0 年代初直到现在，在时间、空间的无缝结合上还没有突破性进展。 时唰和空间的无缝结合主要体现在：( 1 ) 在数据表示上，要有一种能方便有效 的描述运动空间对象的空间信息及运动状态的数据类型；( 2 ) 在拓扑关系上，时空 数据操纵要能完整的描述各种类型对象之间的拓扑关系；( 3 ) 在数据操纵策略上要 针对各种不同类型的对象提出有效的操纵策略：( 4 ) 在查询优化上，要能针对时空 数据库的特殊性提出相应的查询优化策略；( 5 ) 在索引机制上，要有一种能有效描 述时空数据存取路径的索引结构；( 6 ) 在事务处理上，要根据相应的数据操纵行为 给出相应的事务控制机制来保证数据的完整性和一致性。 13时空数据库数据操纵研究现状 数据操纵从实现的层面来分可以分为逻辑上的数据操纵和物理上的数据操纵。 数据操纵物理实现的本质就是如何选择合适的存取路径在物理空间上定位块，并读 ( 写) 块；数据操纵逻辑实现的本质是如何在逻辑上规划操纵各种类型对象的策略。 传统数据库和现代特种数据库在数据操纵的物理实现策略上没有本质的不同，但剥 于逻辑上的实现策略来说，特别是对于时空数据库这样一个需要处理空间类型数据、 时态类型数据、时空复合类型数据的不同于常规类型数据的数据库而言传统数据 库的数据操纵理论显得力不从心。 时空数据库中数据操纵的主要任务就是：( 1 ) 描述时态、空间、时空复合类型 等各种类型对象的行为，即如何定义各种类型实体之间的拓扑关系；( 2 ) 采用一定 的策略完成时态、空间、时空复合类型等各种类型对象的行为。 时空数据库中对象之l 、日j 的拓扑关系主要有：空间关系 4 j 、时态关系口1 、时空关系 6 】等 个方面。时态关系理论已在时态数掘库理论中成功运用，理论相对成熟。空间 关系包括拓扑空削关系、顺序空间关系和度量空间关系，其中，拓扑空间关系是空 间关系理论的重点和难点。e g e n h o f e r 于1 9 8 9 年提出拓扑空削关系的定义i ”，认为拓 2 华中科技大学硕士学位论文 扑空f 司关系指拓扑变换条件下的拓扑不变量，是空间对象之间在拓扑变换条件下仍 保持稳定的那些联系。 1 9 8 8 年，g u t t i n g 基于集合运算理论定义了五种空间关系1 相等、不相等、包 含、相离、相交。但这1 i 种空间关系提法的缺点是不具有唯一性和完备性，如相等、 包含关系被相交关系包含。同年，p u l l e r 运用空间点集的边界( b o u n d r y ) 和内部 ( i n t e r i o r ) 的概念给h ：1 了覆盖( o v e r l a y ) 和相邻( n e i g h b o u r ) 两种空间关系的概念 和定义引，w a g n e r 在此基础上进一步细化，定义了相邻、相离、包含、相交等拓扑 关系【8 1 。上面所有这些提法的共同缺点是不完备。1 9 9 1 年e g e n h o f e r 提出了4 一 i n t e r s e c t i o n 理论 9 , 1 0 1 。4 - - i n t e r s e c t i o n 理论基于边界和内部的概念建立了四元组表达 式的拓扑关系描述的数学模型，同年e g e n h o f e r 又提出了使空间关系的划分更为详细 的9 一i n t e r s e c t i o n 理论】，由4 - - i n t e r s e c t i o n 到9 一i n t e r s e c t i o n 的扩展对所有能够确 定的空间关系的数日没有优势，同时无论是4 - - i n t e r s e c t i o n 还是9 - - i n t e r s e c t i o n 理论， 它们虽然从集合论的角度给出了基本拓扑关系的数学模型，但只是在一般拓扑空间 中考虑问题，难以得到具体简明的算法，也不便于应用。它在推导拓扑关系的完备 集、概念邻域及复合表时依据的是人的直觉，理论上说服力不够。1 9 9 2 年r a n d e l l 等人基于空涮演算逻辑公理提出了r c c l l 2 - 1 4 1 空间拓扑关系理论，r c c 理论的目的是 建立完备而又简单的公理化逻辑理论，没有针对基本拓扑关系建立有效的数学模型 1 2 - 1 4 1 。1 9 9 7 年廖士中等人针对r c c 理论及4 - - i n t e r s e c t i o n 和9 - - i n t e r s e c t i o n 的不足 以拓扑学为基础为r c c 理论建立了数学模型一一闭球模型 1 ”，闭球模型能够直接推 导出拓扑关系的完备集、概念邻域和复合表，比4 一i n t e r s e c t i o n 和9 一i n t e r s e c t i o n 更 为简单、有效，同时也弥补了原有r c c 理论的不足。 时空数据库中还有一类非常重要的拓扑关系：时空关系。时空关系的概念是由 m a r t i ne r w i g 等人以空削拓扑关系理论和时态拓扑关系理论为基础提出来的。时空拓 扑关系的实质是一种动态的空间拓扑关系，它与空间拓扑关系的本质不同是：时空 拓扑关系能够描述运动对象之间的空间关系的变化过程。运动对象之制的空间关系 是随着时态的发展而不断变化的，实体之间在不同时刻点或时间段内的空日j e t 拓扑关 系不一定相同，并且相邻时态之间的空间拓扑关系的变化规律符合空间拓扑关系中 华中科技大学硕士学位论文 的概念邻域的要求。 数据操纵的宗旨是：找到一条最有效的存取路径，通过访问最小数量的物理块， 以最小的时空运算时间代价实施对数据的增、删、改、查。目前，数据操纵策略的 研究主要集中在如何选择最优的存取路径、减少时空运算代价、缩小查询空间范围 等三个方面展开，国内外众多研究者针对特定的时空数据操纵提出了相应的操纵策 略，第四章将详细介绍运动对象的运动过程中的最近邻居的查询算法的研究现状、 存在的问题及改进算法。 1 4 时空数据库查询优化研究现状 目前，大多数数据库的查询优化都是基于传统的关系数据库的查询优化理论， 到目前为止，国内外鲜有专门针对时空数据库的查询优化方面的研究。传统的关系 数据库的查询优化理论主要包括：( 1 ) 关系代数优化1 6 - 1 9 ；( 2 ) 依赖于存取路径的 规则优化1 1 6 - 1 9 1 ：( 3 ) 代价估算优化f 1 6 - i 9 1 。 随着数据库技术的应用与发展，传统的关系数据库的查询优化理论面对丰富多 彩的应用显得捉襟见刖。1 9 8 1 年，j j k i n g 在他的系统q u i s t ( q u e r yi m p r o v e m e n t t h r o u g h s e m a n t i ct r a n s f o r m a t i o n ) 中提出了“基于知识的查询优化( k n o w l e d g e b a s e d q u e r yo p t i m i z a t i o n ) ”理论【2 0 _ 2 6 1 ，该理论的主要思想是：将一组完整性限制作为知识 运用语义逻辑把一个原始的查询语句转换为个优化的查询语句。j j k i n g 的“基于 知识的查询优化”理论是语义优化的雏形。1 9 9 0 年，u s c h a r k r a v a r t h y 提出了演绎 数据库 2 3 , 2 7 , 2 8 1 ( 具有演绎推理能力的数据库，一般地，它用一个数据库管理系统和一 个规则管理系统来实现) 的概念，它包括数据完整性( d a t ai n t e g r i t y ) 2 3 j 、内涵数据 库( i n t e n s i o n a l d a t a b a s e ) 1 2 3 j ( 用逻辑规则定义要导出的事实) 、外延数据库吲 ( e x t e n s i o n a ld a t a b a s e ) ( 将推理用的事实数据存放在数掘库中) 三个方面，通过这三 个方面完成语义查询优化。语义查询优化理论提出之后，国内外很多学者在如何自 动获取数据库中有用的语义舰则( 语义信息) 作出了很火贡献。 语义规则的自动获取研究主要在两个方面展开：查询驱动陋2 9 1 和数据驱动 3 0 - 3 3 i ， 但数据驱动方法和查咖驱动方法存在很多不足。数据驱动方法在进行语义规则获取 华中科技大学硕士学位论文 时缺乏针对性，可能得到大量的无用的语义信息，这主要是由于数据库的应用领域 的广泛性及所研究的对象信息无规律性决定的；查询驱动方法获得的规则可能针对 性太强而缺乏通用性，降低系统的效率。 对于时空数据库而言，它所研究的内容针对性很强，即对象的空间信息和时态 信息以及对象之间的拓扑关系。针对时空数据库的这一特点，在时空数据库中运用 数据驱动方法或查询驱动方法来获取语义规则进行查询优化是比较合适的。第五章 中将详细介绍时空数据库中的语义优化策略。 1 5 主要工作及创新点 本文的主要工作在如下三方面展开：( 1 ) 补充并完善了s a i l i 系统中的时态关 系、空间关系，并新增了时空关系；( 2 ) 针对现有的运动对象的最近邻居查询算法 存在的不足提出了改进算法；( 3 ) 提出了时空数据库中运用时空语义规则进行查询 优化的策略。本文的主要创新之处将在1 5 1 小节和1 5 2 小节进行介绍。 1 5 1 运用拓扑空间关系理论解决运动对象最近邻居的度量空间关系问题 求解运动对象最近邻居的问题是一个度量空间关系问题。现有的以 t p r t r e e f 3 4 。3 8 1 索引结构为基础的t pn nq u e r y 3 9 1 算法存在的问题是不能充分利用 索引遍历过程的中间结果，导致同一信息的多次访问。解决问题的关键是如何确定 那些中间结果是有用的信息。 通过分析，不难发现，有用的中间结果信息是那些可能成为运动对象的最近邻 居的对象的信息，而可能成为某个运动对象的最近邻居的对象与运动对象的运动轨 迹是有关系的。假设某个空间中任何两个相邻对象之间的空间距离的最大值为 m a x d i s t ，那么，可能成为某个运动对象的最近邻居的对象一定分布在以这个运动对 象的运动轨迹上的点为圆心，以m a x d i s t 为半径的矩形空间范围内，即凡是可能成为 该运动对象的最近邻居的对象它们的运动轨迹一定与矩形空间范围相交或落在该矩 形空间范围内。因此，求运动对象的最近邻居的度量空间关系的问题转化为一个拓 扑空间关系问题。 本文通过分析运动对象最近邻居求解问题的实质，将空间关系进行转化，有效 华中科技大学硕士学位论文 利用了索引遍历过程中的有用的中间结果信息，能够避免对相同信息的重复访问 提高查询效率。 1 5 2 运用时空语义规则进行时空查询优化 时空数据库所描述的时态信息和空间信息的特殊性决定了时空查询优化策略和 原则的特殊性，很多传统的关系查询优化策略和原则不再适用于时空数据库。 通过分析时空数据库中的主要语义规则，提出了获取语义规则的三种途径：( 1 ) 通过谓词的增加、删除和替代来优化查询，基本的时态关系、空间关系和时空关系 是谓词增加、删除和替代的理论根据：( 2 ) 谓词的推导，时空关系的复合表和概念 邻域是谓词推导的依据：( 3 ) 通过在查询的w h e r e 子旬中增加时空限定条件来提高 查询效率，w h e r e 子旬中增加限定条件的目的是减少查询的空间搜索范围，对象的空 间分布规律对减少空间搜索范围有很大帮助。 本文提出了如何提取及运用上面三种途径获取的语义规则的策略，优化了查询， 提高了查询效率。 1 6 小结 本章首先从时空数据库的应用背景出发阐述了时空数据库课题研究的现实意 义，时空数据库理论在天文、地理信息管理、城市规划、交通管理、天气预报、生 态管理等等领域都有广泛的应用。 同时，介绍了时空数据库理论的研究现状，目前，时空数据库理论研究的主要 问题是在时态和空间的无缝结合上存在不足。通过时空数据库理论研究现状的阐述， 说明了时空数据库理论研究的紧迫性和重要性。在此基础上，主要讲述了时空数据 库在数据操纵和查询优化这两个方面的研究现状，并指明了时空数据库在这两个方 面的研究方向。 最后，指出了本文所做的主要工作及创新之处。本文研究的重点是时空数据库 的数据操纵策略及查询优化技术。 华中科技大学硕士学位论文 2s a i l i 改进方案 p o s t g r e s q l ( 简称p o s t g r e s ) 是一种对象关系型数据库管理系统( o r d b m s ) ，也 是目前功能最强大，特性最丰富和最复杂的自由软件数据库管理系统。p o s t g r e s 起源 于伯克利( b e r k e l e y ) 的数据库研究计划，目前已经衍生成一项国际开发项目。p o s t g r e s 拥有极其强大的扩展能力，而且，p o s t g r e s 的所有源程序都是开放的， 理论上你可 以做任何你可以做的事情。 s a i l i 4 0 4 2 1 数据库管理系统是在数据库管理系统p o s t g r e s q l 基础上的改进和扩 展，它是一种支持时空信息处理的对象关系的时空数据库管理系统。下面将从主要 从s a i l i 系统的体系结构、数据类型、拓扑关系、数据操纵几方面介绍s a i l i 系统。 21s a | l l 系统结构 2 11三种流行的系统结构 根据对时空属性数据和常规属性数据的处理方法的不同，时空数据库系统的系 统结构可分为( 1 ) 分层结构：( 2 ) 混合结构；( 3 ) 统一结构三种。 时、空数据管理层 王 通用r d b m s 图2 1 分层结构 分层结构如图2 1 所示。在分层结构中，利用r d b m s 所支持的数据类型及操作 为基础，在它的上面增加一层，以实现时空数据类型及其操作。分层结构的缺点是： 常规的r d b m s 不提供用户扩充合适的存储结构和存取路径的接口而常规的 r d b m s 支持的存储结构、存取路径和方法往往不适合于要表示的时空属性数据类 型，用户要解决对时空对象的操纵，必须编写复杂的查询程序，这可能会使查询优 化器无法工作。当然，分层结构最大的缺点是扩充的时空数据管理层本质上是面向 华中科技大学硕士学位论文 特定应用的，缺乏通用性。 数据集成及用户接口 王 王 l 通用r d b m s时、空数据子系统 图2 2 双重结构 双重结构如图2 2 所示。为了克服分层结构对时、空数据有限支持的不足，双重 结构在r d b m s 之外增加了一个专门管理时、空数据的子系统。双重结构将时空属 性和非时空属性分开存储，它们之间用逻辑指针相连，但是在用户接口上看到的是 一个不分割的元组。双重结构的缺点是( 1 ) 时空属性和非时空属性的分解和合并增 加了系统开销；( 2 ) 时空数据子系统的数据处理不能由r d b m s 直接支持，需要单 独开发。 图2 3 集成结构 集成结构如图2 3 所示。统一结构是在开放型的o d b m s 或o r d b m s 基础上扩 充表达时空数据的功能，时空数据和非时空数据可以同样处理，这为研制集成时空 数据库系统创造了条件。 2 12s a i l i i 系统结构 s a i l i 系统是一种运用集成结构思想的对象关系数据库管理系统，它的设计强 调系统分层。s a i l i 将系统分为功能互相独立的层次，层次之间界面清晰，衔接得当。 每个系统层次构成一个虚拟机( 抽象数据类型) ，它定义的数据结构和运算构成一个 基本机器提供给它的上一系统层，而它自己又是以它的下一系统层作为基本机器， 以下一系统层提供的数据结构和运算作为基础来实现的。s l i 的具体系统结构如下 华中科技大学硕士学位论文 表2 1 所示 表21s a i l i 数据库系统的系统层次及接口 系统层次系统层任务系统层接口( 数据结构)系统层运算 应用接口为应用提供接口 编译逻辑数据结构：关系、关系代数、关 存取检查视图、元组系演算 数据系统完整性检查 专用视图支持 存取优化 记录管理逻辑存取路径结构及逻扫描、排序、 存取路径管理辑数据记录：关系、视事务控制、封 排序子系统图、元组、表、索引锁、恢复、增、 存取系统 事务管理删、改、查元 并发控制组 恢复管理 缓冲区管理系统缓冲区：页面、段打开、关闭、 内外存交换分配、释放段， 存储系统 外存管理申请、释放、 读、写页 o s 或裸机的设备接口基本内外存存 存储分配结构 取 s a i l l 清晰的系统层次结构为在它基础上的迸一步扩展提供了良好的基础。 2 2s a i l i 数据类型 s a i l i 数据库管理系统为了支持时态和空间信息的处理，除了定义常规数据类 型( 如i n t e g e r ，c h a r ，b 0 0 1 ) 外，还定义了一些非常规数据类型，如时态数据类型、 9 华中科技大学硕士学位论文 空间数据类型。抽象的时态数据类型包括时间点( i n s t a n t ) 、时间段( i n t e r v a l ) 。抽象 的空间数据类型如静态点( p o i n t ) 、静态线( 1 i n e ) 、静态面( r e g i o n ) ，这些时态和空 间数据类型的扩充为时空信息的处理提供了方便。 在现实应用中，可能需要处理空间信息随着时态的发展而发展变化的动态对象。 因此，时空数据库除了描述静态的空间对象外，还必须能够描述动态的空间对象。 现有的s a i l i 系统对动态的空间对象的处理方法是：通过关系中元组的不同属性列 分别描述动态空间对象的时态和空间信息来反映它的发展变化过程。这种处理方法 的弊端是： ( 1 ) 动态空间对象的时态和空间信息实际上是一个逻辑上的整体，分开描述时 态和空间信息有悖于时态和空间的无缝结合： ( 2 ) 不利于形象直观的描述空间对象的运动变化过程； ( 3 ) 不便于运用面向对象的方法对运动对象的属性和方法进行封装和继承。 鉴于此，需要对s a i l i 系统的数据类型进行扩充。 2 3s a 拓扑关系 s a i l l 系统中的拓扑关系包括时态关系和空间关系两种，系统定义的对象之间的 各种时态关系的种类比较丰富，下面将重点阐述s a i l i 中的空间关系。 s a i l i 系统中的空间关系包括顺序空间关系【4 4 1 、拓扑空间关系h 钔、度量空间关 系【4 4 l 三种。其中顺序空间关系包括：上、下、左、右；度量空间关系包括：距离、 周长等；拓扑空间关系包括：线与线垂直、线与线水平、面与面重叠、面与面交叉。 不难看出，s a i l i 系统中的空间关系特别是拓扑空间关系的种类相当有限，空间 对象之间的很多空间关系它都无法描述。时态和空间关系的有限性决定了s a i l i 系 统所支持的数据操纵的不丰富性。因此，s a i l i 系统中数据操纵的一个主要任务是扩 充系统中的空间关系。 2 4s a i l i 查询优化 s a i l i 系统的查询优化策略主要是基于关系数据库理论的逻辑优化和物理优化， 0 华中科技大学硕士学位论文 还没有针对时态和空间的特殊性提出特定的优化方案，因此有必要对s a i l i 的查询 优化策略进行改进。 2 5 s a i l i 改进方案 综上所述，要使s a i l i 成为一个真正的能支持时空数据操纵的时空数据库管理 系统，实现时态和空间的无缝结合，必须对s a i l i 系统进行改进，改进后的系统为 s a i l i i 。s a i l i 系统的改进方案如下： ( 1 ) 数据类型：扩充s a i l i 系统现有数据类型，将运动对象的空间信息随时态 发展的变化看作是时态的行为序列，把对象的时态和空间信息作为一个整体来看； ( 2 ) 拓扑关系：扩充现有时态和空间关系，使时态关系和空间关系的种类更丰 富，能够描述时态和空间实体之间的各种关系： ( 3 ) 数据操纵：数据操纵方面的修改和扩展在两个方面展开：扩充数据操纵的 种类，同时改进现有数据操纵策略： ( 4 ) 查询优化：充分利用时空数据库应用的特殊性，运用时空语义规则进行查 询优化。 2 6 小结 本章通过对s a l l i 系统的在体系结构、数据类型、拓扑关系、查询优化等方面 的分析，指出了s a i l i 系统在体系结构方面的优点及其它方面的不足，并分别提出 了这几个方面的改进方案。 华中科技大学硕士学位论文 3s a l l | l 数据操纵 3 1s a i l i i 数据类型 s a i l i i 是在s a i l i 基础上改进而成的一个时空d b m s ，s a l l l l 系统所支持的数 据类型的形式化描述为 s t d b ：= l ：= i ：= l ：= ：= ( t s l ，t s 2 ) ：； t s i lt s i d ( t ) ，i = l ，2 ，3 ：= ：= n o ns p a t i o t e m p o r a la t t r i b u t e ：= t h ei do f ：= l l ：=( x l ，x 2 ，x 一x n ) ：= 2 * ：= ( ， ) + ：= a b i ts i g n ：= a 2b i t ss i g n 其中： s t d b 指时空复合数据类型。 t t 、v t 分别指事务时间和有效时间。 i n s t a n t 表示时唰点，t s d ( t ) 是时间域中的一个值，i n t e r v a l 是一个二 元n t s l ，t s 2 表示时间区间，t s i ，t s 2 d ( t ) 。 - o i d 是对象标志符，用来唯一标识一个时空对象；a t t r 表示非时空属性，即常 1 2 华中科技大学硕士学位论文 规属性，如对象的速度等。 s o 描述空间位置信息。 p o i n t 描述点的静态空间信息；l i n e 描述线的静态空间信息；r e g i o n 描述 面的静态空间信息，其中，n 的具体取值由空间的维数决定。 f l a g 是一个两个字节长度的属性标识位，对应于上一章中所提到的s a i l i 采 用的将时空数据分为非时空属性库p a d 、时空属性库s t d 两部分存储区域的方法， 用来表示对象分别在上述两个区域的存在状态，“1 ”为“真”，“o ”为“否”。 t a g 是一个一字节长度的属性标识位，对应于属性划分为不变属性和多变属 性，用来区分属性是多变属性还是不变属性，“1 ”为“多变属性”，“o ”为“不变属性”。 s a i l i i 系统中数据类型的形式化描述描述了时态数据类型和空间数据类型两种 数据类型。时态数据类型有包括事务时间和有效时间两个方面，用时间点( i n s t a n t ) 或时间段( i n t e r v a l ) 描述。空间数据类型有两种：描述静态空间对象的数据类型和 描述动态空间对象的数据类型，对于静态的空间对象可以有两种数据类型来描述， 和 t t ， 把静态的空间对象看作是一种变化速度为零的 特殊的动态空间对象。 3 2s a i 时态谓词 表3 1 时态关系 p r e d i c t i o ns y m b o ls y m b o if o ri n v c l s cp i c t o r a ie x a m p l e ab e f o r e bx x x y y y a e q u a l b x x x y y y a m e e t s bx x x y y y a o v e r l a p sb x x x y y y a d u r i n g b dd ix x x y y y y y y as t a r t s b x x x y y y y y y a f i n i s h e s bfnx x x y y y y r y 谓词是对现时世界中某种事实的真、假判断。空间谓词表示从空间对象映射到 华中科技大学硕士学位论文 布尔值( b 0 0 1 ) 的函数，它是对空间对象之间空间关系的真、假判断。时态谓词由时 态对象和时态关系两个部分组成，如果时态对象满足某种空间关系，那么时态谓词 的返回值为真，否则为假。 s a i l l l 中的抽象时态数据类型有i n s t a n t 和i n t e r v a l 两种，i n s t a n t 类型的时态关系 比较简单，下面将重点介绍时间段类型的时态对象之间的时态关系。假定a 和b 为 两个时间段类型的时态对象，则基本的时态关系及对应的时态谓词如表3 1 5 1 所示。 对于任意给定的三个时间段类型的时态对象a 、b 、c ，任意给定的两种时态关 系r l 和r 2 ，如果如下条件：a r l b ，且b r 2 c 则有如表3 2 【5 】中给出的a t 3 c 成立。 表中表示没有定义。 表3 2 时态关系的复合表 br 2 cdd ifn ar 1b ， ， 0 ， 0 f ，o j ， 口f - l小，m 1 m j d ， d d ，d ， j|f| ， ， ddd o l - d o - 口， 口f ， 卅f m 脚m d ，d ， f 5 d ，d ， s f ，qo ，0 l - o ， 0 ， 出。 曲 d 1 d ， 0 ，0 f 酿 讲 d l ， 曲 d f 讲 j ， 曲 曲 d ， - ，； j ， o 洲 西坍i ，曲 一 j ，= 1 4 华中科技大学硕士学位论文 表3 2 时态关系的复合表( 续) br 2 cd d i fn ar