（计算机软件与理论专业论文）时空数据库查询语言及其实现技术.pdf

华申科技大学硕士学位论文 摘要 对空间地理信息和时间信息的存储和管理分别导致了空间数据库和时态数据库 的产生和发展，但两者的研究基本上处于相互独立的状态。随着地理信息系统( g i s ) 在各个领域的广泛应用，需要将时间特性融入空间数据的表示和处理，在同一框架 内管理随时间变化的空间对象，因此出现了一种新的数据库技术时空数据库。 时空数据库在g i s ，交通、气象、土地管理等方面具有广阔的应用前景。) 夕一一 在时空数据库管理系统原型s a j l 中，较好地实现了时态数据库和空间数据库的 理论、技术和机制的集成。系统通过在标准关系数据库语言s o l 的基础上扩充时态、 空间特性，设计了一种新的时空数据库查询语言s a m _ s o l , 并实现了s a i l _ s o l 的 预编译系统。 s a i l 的数据模型是一个支持双时态二维空间的时空模型，它引入了时态和空间 的相关概念对数据类型进行扩充，能够用来表示时间点、时间段等时间类型和点、 线、面等空间类型，定义了新的时空操作和谓词。同时系统以提出的数据模型为理 论依据对s q l 进行了扩展，对相关概念进行了的形式化定义，给出了时空对象的插 入、删除、修改、查询等数据操纵的描述机制，从而设计出了一种新的时空数据库 查询语言s a i ls o l 。该语言既保持了s q l 原有的特点，又能支持时空定义和操纵。土 时空查询语言s a i l的实现是开发 系统中一个重要的组成部分。它涉_ s o l s a i l 及到了预编译系统的体系结构、工作流程以及词法j 语法和语义分析、出错处理的 设计和实现技术。在介绍实现策略的同时，还描述了预编译系统的主要数据结构， 提出了查询的执行算法。 关键词：时空数据库；查询语言；预编译系统：时空数据模型， 华中科技大学硕士学位论文 j = _ l = ；e _ _ 目 q _ i l e = = - - _ _ 目_ _ - _ - _ _ - - _ l _ _ - - | _ i a b s t r a c t t h e r e q u i r e m e n tf o rs t o r a g ea n dm a n a g e m e n t o fs p a t i a la n d t e m p o r a li n f o r m a t i o nh a s l e a dt ot h ea p p e a r a n c eo fs p a t i a la n dt e m p o r a ld a t a b a s er e s p e c t i v e l y h o w e v e r , t h e yh a v e l o n gb e e ns e p a r a t e ，i m p o r t a n ta r e a so fd a t a b a s er e s e a r c h o nt h eo t h e rh a n d ，g e o g r a p h y i n f o r m a t i o ns y s t e m ( g i s ) h a sb e e nw i d e l yu s e di na p p l i c a t i o nf i e l d sr e c e n t l 5i ti sn e e dt o m a n a g e t h et e m p o r a la n d s p a t i a ld a t ai na n u n i f i e ds c h e m e a sar e s u l t ，t i m ec h a r a c t e r i s t i c s h o u l db ea d d e di n t os p a t i a ld a t aw h e n t h e y a l er e p r e s e n t e da n d m a n a g e d t h e r e f o r ea n e w d a t a b a s et e c h n o l o g y , n a m e ds p a t i o t e m p o r a ld a t a b a s e ，h a sd e v e l o p e di nr e c e n ty e a r s t h e s p a t i o t e m p o r a l d a t ah a s b r i g h tf u t u r ei nt h ea r e a so fg i s ，t r a n s p o r t a t i o n , m e t e o m l o g ye t c i nt h e s p a t i o t e m p o r a ld a t a b a s em a n a g e m e n ts y s t e mp r o t o t y p es a i l , t h et h e o r i e s ， t e c h n o l o s i e sa n dm e c h a n i s mo fs p a t i a l a n dt e m p o r a ld a t aa r ep e r f e c t l yi n t e g r a t e da n d i m p l e m e n t e d t h es y s t e md e s i g n e dan e ws p a t i o t e m p o r a lq u e r yl a n g u a g es a ls q l o n t h eb a s e do ft h es t a n d a r ds q ll a n g u a g e b ye x p a n d i n g t h e s p a t i a l a n dt e m p o r a l c h a r a c t e r i s t i c s m o r e o v e r t h ec o m p l i e rs y s t e mo fs a ls q l h a sa l s ob e e n i m p l e m e n t e d t h ed a t am o d e lo fs a i li sas p a t i o t e m p o r a lm o d e lt h a ts u p p o r t sb i t e m p o r a la n d t w o d i m e n s i o ns p a c e i ti n t r o d u c e st h er e l a t e dc o n c e p t so fs p a c ea n dt i m ea n de x p a n d s c e r t a i nd a t at y p e st or e p r e s e n t st e m p o r a la n ds p a t i a ld a t at y p e s ，s u c ha st h ee v e u t ，p e r i o d ， p o i n t ，l i n e ，p o l y g o ne t c a n dd e f i n e st h en e wo p e r a t i o n s a n d p r e d i c a t i o n s s i m u l t a n e i t y , t h e c o m m o ns q li sa p p r o p r i a t e l ye x p a n d e da c c o r d i n gt ot h ed a t am o d e lw e p r o p o s e da n d a n e w s p a t i o t e m p o r a iq u e r yl a n g u a g e ，n a m e ds a i l _ s q l i sp r o d u c e t h es y s t e mg i v e st h e f o r m a ld e f m i t i o no ft h en e wc o n c e p t sa n dd e s c r i b e st h ee x t e n d e di n s e r t i o n , d e l e t i o n ， u p d a t ea n d s e l e c t i o no p e r a t i o n s t h ed e s i g na n di m p l e m e n t a t i o no fs a i l _ s q li so n eo ft h ei m p o r t a n tp a r t so fs a i l i ti n v o l v e st h ea r c h i t e c t u r ea n d w o r k i n g f l o wo f c o m p i l e rs y s t e m ，t h et e c h n o l o g y o f s y n t a x a n a l y s i s ，t h es e m a n t i ca n a l y s i sa n de r r o rm a n a g e m e n t a tt h es a m et i m e ，t h em a i nd a t a s t r u c t u r e so fs y s t e ma n de x e c u t i o na l g o r i t h ma r ea l s op r o p o s e d 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 ；q u e r yl a n g u a g e ；p r e 。c o m p i l i n gs y s t e m ； s p a t i o t e m p o r a ld a t a m o d e l n 华中科技大学硕士学位论文 1引言 1 1 时空数据库概述 时空数据库是近年来数据库技术发展的一个新方向，它的研究与发展得益于空 间数据库特别是地理信息系统( g i s ) 的研究与广泛应用。地理信息系统( 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 1 。自从上个世纪7 0 年代以来，g i s 技术在国防、城市规 划、环境保护等与国民经济乃至国家命脉相关的重要领域发挥了重要作用，极大地 推动了社会生产力的发展。但是，传统的g i s 应用只考虑空间对象的空间特性，忽 略其时间特性。而越来越多的应用领域在问题求解过程中非常强调时间因素，如交 通管理、环境检测、地震救灾等等。因此，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 数据的 表示和处理，在同一框架内管理时空数据，它的组织核心就是时空数据库【2 , 3 l 。 时空数据库就是同时能够处理时态和空间数据的数据库系统。在此之前，对空 间数据库和时态数据库的研究基本上是处于相互独立的状态【钔。空间数据库的研究侧 重于对数据库中对象的集合模型和空间查询方面的支持，仅能存储空间信息的当前 状态；时态数据库的研究则主要关注当前信息和历史信息的处理和扩展，即有效时 时间和事务时间的表达。不能处理空间信息，也不能表示和处理移动的空间对象。 正是由于两者所处理的对象均具有空间和维的概念，在此基础上集成两方面的研究 就很有必要。时空数据库正是包括时间和空间要素在内的数据库系统，一般认为是 在空间数据库的基础上增加时间维构成的。时间维的加入大大丰富了数据库的内容。 它一方面增加了数据库管理的复杂性：另一方面，海量的数据为空间和时间分析提 供了极其广阔的舞台。 时间数据库有下列几个方面的特性：( 1 ) 动态性。传统的数据库系统对数据进行 静态或准动态的数据库管理。在数据库更新时，过时的数据将从数据库中删除- 在时 间数据库中，过时的数据不再从数据库中删除，对历史数据也可以进行更新，使系统和 现实世界一直保持着全方位的动态交换。( 2 ) 全面性。由于时间数据库是所有数据的 集合体，它与现势数据库不同，可以提供任何时刻和时间段的数据，使数据库成为真正 华中科技大学硕士学位论文 l = _ _ l _ l _ l _ _ i _ _ i l l l _ _ 目目= = i _ - _ _ _ - - i _ _ _ 意义上的数据库。时间数据库在下列两个方面具有重要意义：( 1 ) 使数据库成为真正 意义上的资源清单。目前的数据库基本上不存储旧的、过时的数据，而时间数据库则 包括任何历史数据，使数据库可以成为任何一个系统和部门的完整的电子信息档案 库。( 2 ) 为动态监测和分析提供了丰富的数据。一方面，它可以为分析提供横向的现势 和纵向的历史数据，对历史、当前和将来进行对比、分析、监测和预测预报。从而为预 测预报系统、决策支持系统和其他分析系统服务【5 一。时空数据库和时间地理信息系 统对所有与地理信息有关的领域有广泛的应用前景。特别是对经常性变化的空间信 息的管理具有重要的意义，在地籍、土地利用、房地产、交通、能源等方面有着良 好的应用。 1 2 时空数据库的研究现状 目前，时空数据库的研究涉及到数据库研究的诸多领域，如数据模型和语言、 数据结构、查询处理、索引算法等方面。由于时空数据库中具有大量的历史信息以 及空间数据本身在存储和表达方面的异构性，因此时空数据库的研究还涉及元数据 管理、拓扑表达等方面的研究。当前的研究重点主要在以下几个方面【7 ，8 】： 1 时空分析和推理：即如何根据数据库中的大量的时间序列数据和空间数据进 行包括时间推理和空闻推理在内的数据分析； 2 时空数据库模型和查询语言：如何提出并建立一个有效的数据库结构来存储 时空数据并设计出支持该模型的查询语言来查询时空对象； 3 时空数据库的存储结构和索引技术：这个方面的研究主要着眼于将已有的时 态或空间数据的存储和访问机制进行集成和融合； 4 时空数据库的查询处理：主要研究查询的优化技术； 5 时空数据的可视化研究：着重探讨不同时间数据的显示、制图和符号化等问 题。 1 2 1 时空数据模型 对时空数据模型的研究具有多种出发点【9 】。一种出发点是从时态数据库的研究出 发进行扩展得到时空数据模型。由于时态模型支持数据库实体特征的时态信息，通 常的做法是将空间信息关联到实体上得到时空数据模型。在这方面的具体的模型有 2 华中科技大学硕士学位论文 3 = 。，i ；_ l 目= = - 自_ _ i t i l - _ l l - _ - - _ - _ _ - l - _ - _ _ l t a n s e l 、g a d i a 等人提出的时态模型【1 0 ，1 1 l 以及b o h l e n 等人提出的s t s q l 模型1 2 1 等。 这些模型提供了用于时空操作的函数和查询语言，但是没有定义时空数据类型的整 体框架。 另一方面可以从空间数据模型出发扩展得到时空数据模型。w o r b o y s 从空间数据 模型出发结合时空数据模型的特点，通过定义一种时空对象一时空复合型( s t c o m p l e x ) 来描述空间属性，时态特性则通过简单复合型所附带的双时态要素进行描 述，该模型提供了用于查询的运算集合，但没有提供表达抽象数据类型的系统1 1 3 l 。 另外，地理信息系统在发展过程中也提出了以下几种时空模型体1 6 1 ：简单快照模型， 更新模型，时空复合模型，四维模型和集成复合模型。这些模型都能够用来描述时 空数据，但各有优缺点。快照模型能够很好的存储数据，但难以做出很好的时间分 析；更新式模型虽然很容易在当前g i s 上实现，但它对于时间的分析也比较困难； 时空复合模型包括了时间分析的拓扑，是一种比较理想的数据结构，可惜难以在当 前的g i s 上实现；四维模型现在还停留在理论研究上。 上述这些模型只是处理了时空对象的特征变化的离散情况而没有表达特征连续 变化的情况。从语义和逻辑建模的角度看，其原因在于传统的数据库管理系统提供 的语义概念和基本数据类型是有限的，不能充分处理时空数据。 近几年，时空数据库的研究开始关注时空对象的连续变化特征，并试图从语义 层次上建立时空数据库的概念模型，其思路在于通过对空阉对象的对态特征进行分 析建立具有一般性的连续模型，然后将其离散化以便于系统实现。如y e h 和c a m b r a y 提出的基于行为时间序列( b o h a v i o r a lt i m es e q u e n c e s ) 的时空模型【1 7 埘，一个时间序 列就是由空间属性，日期时间和行为函数组成的一个三元组。行为函数用来描述本 序列元素到下一个元素的变化情况，这种行为函数包括点函数、阶梯函数、线性函 数和插值函数；c p a r e n t 和s s p a c c a p i e t r a 等人从地理信息系统的应用出发设计了面 向应用数据的时空模型m a d s ( 1 9 , 2 0 l ，该模型为g i s 的设计提供了支持时态信息的辅 助建模工具，模型提供了对象类型、关系类型和约束机制的定义，但它本身只是将 时态信息和空间信息进行组合，还没有进行真正的时空集成：从地理信息系统的应 用角度出发对时空进行定程度的集成模型有d o n n ap e u q u e t 等人提出的基于时间 和时间分析的模型e s t m d m 2 1 , 2 2 1 ，这一模型难于同现代的主流数据库( r d b 、o r d b 、 3 华申科技大学硕士学位论文 ； l = z = = _ _ l = = 目= _ 目_ l _ l l l - _ - - _ _ l - _ _ _ _ - o o d b ) 技术进行紧密结合。 随着对移动对象的深入研究，时空数据库也开始用移动对象的方法来对时空对 象进行研究。这种观点认为空间对象随时间的变化可以看作是空间对象在时空空间 中的运动，描述这种运动现象所采用的基本概念是移动( m o v i n g ) ，移动的本质是建 立时间维到空间维的映射关系。典型有m a r t i ne r w i g ，r a l fh a r t m u tg u t i n g 和l u c a f o r l i z z i 等人的研究工作 2 3 , 2 4 】。 人们运用移动对象的思想并基于集合论和拓扑理论首先从概念语义方面对时空 集成进行了研究，该模型提出了移动点( m o v i n gp o i n t ) 和移动区域( m o v i n gr e g i o n ) 的概念，并以连续变化的观点对时空模型的数据类型和数据操作进行了形式化的描 述，建立了相应的时空代数，同时扩展了s q l 语句并接提出了实现时空集成的语义 操作模型和数据结构，该模型还给出了一种离散化的数据模型和结构，在实现上可 用于r d b m so r d b m s 和o o d b m s ，具有较好的独立性。所不足的是模型只关注 空间对象矢量特征的变化而忽略了其他属性的变化，在时空拓扑表达方面不够完备， 无法满足时空对象的分解和合并处理及跟踪。另外模型只是考虑时空对象的有效时 间，对于事务时间没有考虑。d o n g h ok i l n 等人根据s q l 3 和t s q l 提出了一种考虑 双时态特征的形式化的概念模型【瑚，但该模型对数据抽象比较简单，只是结合了时 态和空间数据类型并研究了。各种数据类型的数据操作集合，仍然没有解决前面提到 的问题。从面向对象角度出发，g l a u c i af a r i a 等人建立了面向对象模型，该模型对面 向对象概念进行了扩充和实现，并通过提供类库来支持时空数据的集成f 2 6 j 。 在国内，对于时空数据模型的研究虽然起步较晚，但同样取得了一定的成果。 在时空数据模型方面，【2 7 】给出了时态对象结构的形式化定义和时态拓扑关系点集拓 扑理论描述及逻辑谓词描述；f 2 8 】对空间和时间语义的抽象和形式化方法进行了研 究，设计了基于状态和变化的统一时空数据模型s c u d m ；【2 9 】探讨了连续时间变化 的空间实体建模理论，提出了9 类抽象时空数据类型；探讨了连续时空变化的空间实 体建模理论。 1 2 2 时空查询语言 s q l 语言是最流行的数据库语言，并且已经形成标准，容易被广大数据库用户 4 华中科技大学硕士学位论文 5 e 自l = _ # = 1 4 目i t _ = - i _ l l i _ l _ _ l - - - _ _ _ _ - _ _ _ - _ _ i _ - _ _ _ _ - _ _ _ _ l - _ i _ - _ _ _ - _ l l - 使用和接受，因此时空数据库查询语言采用的仍然是s o l 语言。但在不同的原型系 统都在不同程度上对s q l 语言进行了扩充以支持时空数据的查询，扩充的程度取决 于采用的数据模型【3 0 l 。目前的两个比较明显的研究方向是： 1 在理论上注重完成时空查询功能，不涉及可视化。这个方向的典型代表是 m a r t i ne r w i g 和m a r k u ss c h n e i d e r 共同研究的s t q l ( s p a t i o - t e m p o r a lq u e r y l a n g u a g e ) 1 3 1 , 3 2 1 。 s t q l 的数据模型为行为时态时空数据模型( b e h a v i o r t e m p o r a ls e q u e n c e ) 。此数 据模型将时态的变化看成是空间属性的行为时态序列，把空间属性的变化看成是一 个时态函数。这种语言的优点是很容易处理同一空间对象随时态变化的空间属性的 发展变化，也容易处理不同空间对象在同一时态下的空间关系，但是这种模型没有 给出对有效时间和事务时间的处理方式。这种语言目前尚处于理论研究阶段，对于 定义时空操作的时空谓词的闭包性，完备性上没给出证明，它的查询效率如何尚没有 经过实践的检验。 2 在实现上注重达到时空查询效果，侧重可视化；这个方向的主要代表是 j e c o r c o l e s 、j g a r c i a - c o n s u e g r a 、j p e r a l t a 和e r e g o n a l 研究小组提出的g m l ( g e o g r a p h ym a r k u pl a n g u a g e ) 和a l e x a n d e rz i p f 和s v e nk r u g e r 提出的在g m l 基 础上发展了的时空查询语言t g m l 羽e m p o r a lg e o g r a p h ym a r k u pl a n g u a g e ) g m l 是建立在x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) i 吾言理论基础上的专门用来处 理空间对象的查询语言。虽然它的可视化效果很好但时态的语义相当弱，同时对数 据的存储结构有很大限制，必须是树形结构【3 3 1 。 t g m l 对g m l 进行了改进，加入了对时态语义的处理功能 3 4 1 ，是建立在层次模 型理论基础上的时空查询语言。在这种模型中，时态信息作为主要框架决定层次的 结构，时态信息包括四个方面：t e m p o r a lh i s t o r y 、t e m p o r a lo r d e r 、t e m p o r a l s t r u c t u r e 、 t e m 【p o r a lr e p r e s e n t a t i o n 。每个方面的具体含义为：t e m p o r a l h i s t o r y 表示时态信息的 种类，它包括v a l i dt i m e ，t r a n s a c t i o nt i m e ，e v e n tt i m e 三类；t e m p o r a l o r d e r 表示时态变 化的逻辑形式，它包括l i n e a r , s u b 1 i n e a r , b r a n c h i n g 三类；t e m p o r a ls t r u c t u r e 表示时 态的变化序列是i n s t a n t ，i n t e r v a l 还是s p a n ，是离散的，还是连续的。这种语言目前尚处 理论研究阶段，而且同样要求数据结构为树形。很难在关系理论上实现，普遍推广 的难度也很大。 5 华中科技大学硕士学位论文 1 2 3 索引技术和查询处理 对于时空数据库其他方面的研究主要涉及到索引算法。目前多集中在对空间和 时间的索引，对于属性的索引采用传统d b m s 所使用的索引方法如h a s h ，b 树和 b + 树等。对时间和空间的索引大部分仍然基于传统的b 树和b + 树进行扩展和改进， 时态索引算法有t i m es p l i tt r e e ，c h e c kp o i n ti n d e x 等等 3 5 1 ；空间索引算法包括四叉树、 八叉树、k - d 树等等【3 6 】。 查询处理和优化研究主要集中于( a ) 时态、空间和时空操作的有效机制；( b ) 查询 优化的成本模型；( c ) 时态和空间的约束机制。 正如我们研究关系数据库一样，时空数据库的研究的最终目标是开发出一套通 用的时空数据库管理系统( s p a t i o t c m p o r a ld b m s ) ，虽然现在不同的研究机构根据 各自的应用要求已经开发出了一些原型系统，但在商业软件方面，一个完全的时空 d b m s 还没有出现，但现在流行的数据库能在不同程度上支持时空数据。如i n f o r m i x 的d a t a b l a d e 模块，分别支持时间和空间数据类型，但没有将其集成；o r i c a l 提供了 空间数据选件模块s p a t i a lc a r t r i d g e ，它仅仅支持空间数据类型1 3 7 1 ；e s 提供一个统 一管理大容量的图形和属性数据的空间数据库引擎s d e 3 剐。 总的来看，时空数据库的研究还处于不成熟阶段，还没有一个通用的数据模型， 对于数据库的诸多理论如查询优化、安全性、完整性、一致性等方面研究甚少。 1 3 本课题研究的意义和目标 时空信息应用领域的重点是地理信息，随着信息技术的发展，对地理信息系统 的市场需求越来越大，国民经济的许多方面都需要地理信息管理系统，例如：国防 军事、国土资源管理、矿产资源管理、海洋资源管理、交通管理、旅游信息管理、 房地产管理、城市规划、市政建设以及农林牧副渔业等。另一方面，随着 i i l t e m e t i n t r a n e t 的广泛应用以及“数字地球”概念的提出，世界各国特别是一些发达 国家都在积极进行“数字地球”相关的基础研究。“数字地球”所关注的空间信息是 动态的，如何将各种动态数据有效的进行集成管理就成为“数字地球”中空间信息 管理面临的挑战，时空数据库的建立正是解决上述挑战的有效方法。 我国对时空数据库的研究起步较为晚，虽然取得了一些研究成果，但是仍然处 6 华中科技大学硕士学位论文 = - - _ = e = ，= = - i _ = = = l l _ - _ _ _ - _ l _ _ _ l _ - _ _ _ _ _ _ _ _ - _ - _ - _ _ n _ _ _ _ _ _ _ _ _ - _ _ _ l _ - _ l 目l _ _ _ _ - _ - i i _ i 在初始阶段。在开展时空数据库的研究之前，我们己经在实时、时态数据库方面进 行了大量的研究，积累了比较丰富的研究经验，取得了一定的研究成果。本课题的 研究目标是通过对时空数据库在数据模型、查询语言、事务处理、存储管理等方面 的研究，实现一个支持时空定义、存储和访问的时空数据库管理系统原型。 1 4 本文的工作 s a i l 是一个基于客户机朋艮务器的时空数据库管理系统。本文以s a i l 的研制为 背景，讨论了时空数据库查询语言的设计和实现技术，着重研究时空数据模型、时 空数据库查询语言设计、预编译系统的实现技术。主要从事了以下几个方面的工作： 1 介绍了时空数据库国内外时空数据库及其查询语言的发展和研究现状，本课 题的研究目标和意义。 2 提出了一个支持双时态二维空间的时空数据模型，定义了相关的数据结构和 数据操纵。 3 以提出的数据模型为理论依据对s q l 进行了扩展，给出了相关概念的形式化 定义和时空对象的插入、删除、修改、查询等数据操纵的描述机制，设计出了一种 新的时空数据库查询语言s a i l _ s q l 。 4 设计并实现了时空数据库管理系统s a i l 查询语言的预编译系统，使其能够 完成数据定义、数据操纵等基本功能。 7 华中科技大学硕士学位论文 2 时空数据库管理系统s a i l 结构 s a i l 是我们以l i n u x 为平台，在开放源码的对象关系数据库p o s t g r e s s q l 上开 发的一个时空数据库管理系统原型。它使用比较成熟的客户机服务器模式，采用消 息驱动机制，支持扩充的时空数据类型和操作类型。 2 1 s a i l 的c l i n t j s e r v e r 模式 s a i l 系统采用了c l i e n t s e r v e r 模式的体系结构。系统由多个服务器和客户机组 成，服务器使用高档微机，客户机由较低档次的微机充当。客户机通过网络和服务 器相连，用户程序必须以消息通信的方式与位于服务器上的s a i l 的核心进程联系。 消息是应用程序和核心系统认可的通讯规范，是客户机和服务器交互的重要媒介。 整个系统需要完成工作包括通讯处理、事务处理、消息执行和存储管理。最后将访 问数据库的结果回送给用户进程。整个系统的执行模型如图2 - 1 所示。 用户发送的消息首先都是由核心进程进行处理的。它和一个f o 处理核心进程组 成了s a i l 的核心系统。当核心进程接收到一个服务请求消息需要对某一物理块进行 读取时，如果它不在缓冲区内，核心进程则在释放某一物理块同时向i o 处理进程发 出请求，要求其从物理d b 中调入所需的物理块，完成操作。当核心进程启动之后， 处于不断地接收消息、处理消息的循环之中。消息的处理包括：首先进行必要的正 确性检查和准备工作，然后进行相应的消息处理，既对数据字典、数据库实施增、 删、改、查等操作，控制消息处理的并发执行，最后将访问数据库的结果返回给用 户进程。 2 2s a i l 系统的结构和功能 s a i l 系统是我们在p o s t g r e s q l 系统上实现的一个时空数据库管理系统原型。它 的内部结构可以用图2 2 表示。从图中可知，s a i l 系统的功能可以划分为用户界砸 和接口；数据说明处理；数据操纵；事务处理；存储管理等五个模块。 8 华中科技大学额士学位论文 。e _ _ 目e = _ _ - - 目_ l = _ _ e i _ _ _ - _ i _ l - - - l - _ _ _ _ i _ - - _ l _ - _ l l - - l - i l _ l _ _ - - i n e t w o r k 2 2 1 用户界面和接口 图2 - 1s a i l 系统的执行模型 该模块负责用户界面，提供客户端与服务器的o d b c 接口。用户可以通过交互 式和嵌入式两种方式进行数据库的管理和应用程序的开发。在嵌入方式下，操作的 语句可以嵌入在c 语言程序中使用，从而可以在用户c 程序中对时空对象进行增、 删、改及查询操作，也能够在应用程序中定义、修改、删除或查询对象的结构模式； 在交互方式下用户直接从交互式接1 ：3 输入o s q l 语句，预编译系统接收到该语句后 对其解释执行。 9 华中科技大学硕士学位论文 用户应用数据库管理员 图2 - 2s a i l 系统体系结构图 2 2 2 数据说明处理 说明模块的功能是对用户的数据定义、控制定义进行预处理，建立与维护系统 表和各种安全控制表并存入数据字典。 华申科技大学硕士学位论文 l = l 目_ = l = e # 日= _ - i - _ _ i _ _ _ _ _ - _ - _ l _ _ _ - 一- 2 2 3 数据操纵 数据操纵的功能是对由词法和语法分析过的s q l 语句转换成具体的增、删、改、 查操作。数据操纵部分首先进行完整性检查，然后转换成数据操作命令交给事务处 理器进行处理，最后交给存储系统进行f o 操作。 2 2 4 事务处理 事务处理是进行数据库操作的执行单位。它的主要功能是对数据库的操作进行 控制。 在s a i l 中，针对时空数据的复杂性和多样性，为了提高对数据的访问效率和并 发速度，将时空数据分为三部分存储，非时空属性库( p r i m i t i v ea t t r i b u t ed a t a b a s e ) 有效时空属性库( n o ws p a t i o - t e m p o r a l d a t a b a s e ) ，历史时空属性库( h i s t o r y s p a t i o t e m p o r a ld a t a b a s e ) 。并同时用一个三个字节长度的标识位来表示一个数据对 象在三个存储区的状态。当该模块接收到数据操作命令时，首先查看标志位，根据 标识位的值确定在该数据对象所在的存储区域再进行事务处理。采用这种策略，可 以大大提高数据的访问效率。 另外，事务处理还负责对多个用户访问数据库实行并发控制，为事务的故障恢 复及数据库的完整性与一致性提供服务。 2 2 5 存储管理 负责数据的存储、索引的组织以及缓冲区的管理。 s a i l 的索引是一个双时态二维空间索引。通过两棵2 r 树来实现的，由前r 树即 双时态子索引和后r 树即基于事务时间的时空子索引组成，总共有四维，两个子索 引通过二维链表整合在一起。前r 树索引对象的当前版本，后r 树索引对象的历史 版本。因此对于不同时间版本的检索就到相应的索引树中查找。比起通常使用的时 空索引结构，如基于r 树的各种变形来说，这种索引策略查询效率高，开销小。 2 3 小结 本章主要介绍了时空数据库管理系统s a i l 的执行模型、体系结构以及功能模块。 该原型采用了客户机服务器模式，通过消息完成服务器和客户机之间的通信。系统 1 1 华中科技大学硕士学位论文 = _ _ i i _ _ _ l _ _ _ _ _ _ - l _ _ _ l l _ l i _ _ l _ _ _ - - - - _ 一_ 的功能划分为用户界面和接口、数据说明处理、数据操纵、事务处理、存储管理五 个模块。分别负责用户界面和o d b c 接口、预处理数据定义和控制定义、将s q l 预 编译结果转化成数据库操作同时进行并发控制、故障恢复和完整性控制，完成数据 库的物理存储。 华中科技大学硕士学位论文 = = = = 2 。2 _ t 目= j _ _ _ 口l l j _ - - l _ _ - _ i _ - _ - - _ _ - 3 s a i l 的数据模型 数据模型是用来描述数据的一组概念和定义，是数据库的框架结构，也是用户 对数据库的逻辑视图【3 9 1 。模型不同，d b m s 的功能、存储方法及一系列的功能模块 就完全不同。 时态数据库和空间数据库已经分别得到了较广泛的研究，然而同时支持时间和 空间的数据建模和时空数据库只是近加年才引起人们的注意。在面向记录的数据模 型( 关系模型) 中，数据库由一系列定长记录表达实体和关系。它虽然具有比较完 备的数学基础和形式化、规范化的建模方法，却缺乏丰富的数据语义描述能力和灵 活的数据组织能力，不适合于复杂的时空数据，因此需要建立一种适合表达和处理 时空数据的切实可行的时空数据模型。数据模型一般包括数据的基本结构、数据操 纵和数据约束，这里重点讨论数据结构和数据操纵。 3 1 时空数据的基本特征 要研究时空数据模型，必须先对时空数据的特征有一定的了解。由于时空数据 库的发展主要得益于时态g i s f r g i s ) 的发展，因此具有空间数据的许多特点。 时空数据与其他大多数由计算机处理的科学数据是不同的。它首先以点、线、 面等方式采用编码技术对空间物体进行特征描述及在物体间建立相互联系的数据 集。图像数据、地图数据、地理统计数据以及环境检测数据等都是空间数据的组成 内容【柏1 。 时空数据的一个特点是数据量大，如一副典型的比例尺为1 ：2 5 0 的地形图，需 要1 3 百万对坐标，才能使其获得的数字地图的几何精度达到一定的要求。 另一个特点是时空数据都具有定位、定性和时间的特性。有效的时空数据管理， 要求定位数据( 又称几何数据或图形数据) 与非定位数据( 亦称属性数据或描述数 据) 彼此独立的进行变换，即当属性改变具体性质时，空间位置保持不变；反之亦 然。而时间是物体存在的形式之一，时间信息反映空间物体的时序变化和发展的过 程和规律。 根据时空数据的特点，如何设计和实现一个时空数据模型是本文的一个重要工作。 华中科技大学硕士学位论文 = = = 自= l = = = = = 目_ ；_ - _ - - _ _ _ _ _ _ - - _ i - _ _ - _ - - _ - - l _ - - l _ _ _ - 3 2 s a i l 数据模型的基本概念 时空数据库是时态和空间数据库的有效结合，因此涉及到了时态数据库和空间 数据库的一些相关概念【4 1 矧。 1 时间的表示结构 时间的表达主要有离散的( d i s c r c t c ) 、紧致的( d c n s e ) 和连续的( c o n t i n u o u s ) 三种结 构。离散的时间表示和自然数相似，每一个时刻之后都有一个后继者。紧致的时间表 示类似于有理数，在两个时刻中间都可插入一个时间点。连续的时间类似于实数。在 这几种方式中，基本上均采用离散的时刻表示时间，如1 2 ：0 0 ：0 0 ( 虽然时间本身是连续 的) ，而空间数据的表示均采用实数的方式表示。 2 基本时间单位 在时态数据库中根据时间形式模型的不同有两种基本的时间单位，一种称为时 间点或“瞬时点”，因此时间段可以表示为时间点的偏序集： 1 2 其中p _ - - p l ，p 2 ，p n 为时间点的有限集， t 表示p 上的偏序关系。 在第二种时间形式模型中，基本的时间单位为时间段或时间区间。因此，时间 点可以定义为两个相邻时间区间的交。 在s a i l 数据模型采用的是第一种基本时间单位。 3 有效时间( v a l i dt u n e ) 和事务时间( t r a n s a c t i o nt i m e ) 一个事件的有效时间就是在建模的现实世界中它存在的时间。有效时间可以是 时间点、时间段或者是时间点和时间段的有限集合。一个事件可以存在于任意个时 间点和时间区间，单一的时间点或时间区间只是它的特例。 有效时间对应于现实世界，它依赖于应用，它的值由用户通过应用提供，随着 应用的变化而变化，可以是未来的时间。可替换名称有现实世界时间( r e a l - w o r l d t i m e ) ，内在时间( i n t r i n s i c t u n e ) ，逻辑时间( l o g i c a l t i m e ) 和数据时间( d a t a t u n e ) 。 事务时间就是指一个数据库事实被存放在数据库中的整个时间，即在某个时间 点存储到数据库直到被逻辑的删除这一段在数据库中存在的时间。 事务时间对应于现有事务和数据库状态变迁的历史。它是独立于应用的，其值 仅根据系统时钟导出，完全由系统管理，用户无法更改。事务时间的值不能晚于当 1 4 华中科技大学硕士学位论文 前事务时间，也不能改变( 事务时间的值一般被记录在事务日志中) 。可替换名词有 注册时间( r e g i s t r a t i o nt i m e ) ，外在时间( e x t r i n s i ct i m e ) ，物理时间( p h y m c a lt u n e ) 。 在数据库中，实际时间和数据库时间是任何一个对象均具有的时间属性。时间从 本质上讲是一维的。任何一个空间对象在空间上都可以用三维坐标系进行描述。而 时间对空间对象来说只是一维的。即任何一个空间对象只有一维的实际存在时间或发 生时间。但在数据库中，对象的存在或发生的时间是用数据库时间记录的，这两个时间 对对象来说是相互独立的( 如图3 1 ) ，即数据库时间可以是在实际时间之前、相等或之 后。因此可以说，对在数据库中的任意对象，其时间属性是二维的。 t lt 2 图3 1 对象时间的二维性 对象在时间上的这种二维性导致了数据库的分类。若在数据库中，主体对象的数 据库时间都有大于实际时间的情形，则可称此数据库为历史数据库o d s t o d c a l d a t a b a s e ) ；若实际时间都有和数据库时间相等( 或非常接近) 的情形，可称此数据库为实 时数据库( r e a l t i m ec l a t a b a s e ) 。若实际时间小于数据库时间，可称为预测数据库 ( p r e d i c a t i v ed a t a b a s e ) a 3 3 时空数据模型 时空数据库中的对象都是时空对象，时间和空间特性是他们的基本属性