（计算机软件与理论专业论文）时空数据库的存储组织研究.pdf

华中科技大学硕士学位论文 摘要 时空数据库管理系统是管理既具有时间属性又具有空间属性的数据集合的数据 库管理系统。近年来，随着g p s 、g i s 以及环境数据管理系统等技术的应用和发展， 时空数据库管理系统逐渐成为数据库技术的一个重要分支。 s a i l 系统是个时空数据库管理系统的原型系统，支持双时态二维空间模型。 存储管理子系统处于s a i l 系统的底层，负责如何高效存放时空数据，并使数据能够 被快速的存取，为上层的查询处理和事务管理提供有效的支持。 s a i l 系统将时空属性和时空记录分为定长和变长两类，采取不同的存储策略。 包含有变长时空属性的记录是变长时空记录。定长时空属性或记录存储空间的大小 固定，变长属性或记录存储空间的大小可以动态改变。变长时空记录在首部维护一 个偏移鼍衷，偏移量表的每个元组保存变长记录中的对应字段的偏移量，从而实现 变长属性的存储。在每个磁盘块的首部也维护一个偏移量表，每个表元组对应一个 时z 记录，记录可以是变长的也可以是定长的，从而实现记录的存储。 s a i l 、i n d e x 是一个双时态二维空间索引，总共有四维，属于高维索引。s a i l - i n d e x 将四维索引分解成双时态子索引和基于事务时间的时空子索引，两个子索引通过双 向链表整合在一起。而每个单独的予索引由一棵2 r 树来实现，2 r 树根据事务时间 分为表示当前状态的前r 树，和表示历史状态的后r 树。双时态子索引支持事务时 间和有效时间，属于二维索引，前r 树和后r 树用二维r 树来实现；基于事务时间 的时空索引支持事务时间和二维空间，前r 树和后r 树用3 d r 树来实现。皿、 s a i l 系统是在数据库管理系统p o s t g r e s q l 的基础上经过扩展得到的原型系统， 运行在l i n u x 平台上。 关键宇：时空数据库时空索引、 弱 匿 华中科技大学硕士学位论文 a b s t 隐c t s p a t i o - t e m p o r a ld b m s i sad b m s m a n a g i n g d a t as e tw i t hb o t ht e m p o r a la n d s p a t a a t t r i b u t e r e c e n t l y , w i t ht h ed e v e l o p m e n to fg p s ，g i sa n de n v i r o n m e n t a ld a t am a n a g e s y s t e m ，s p a t i o - t e m p o r a ld b m s b e c o m e so n eo ft h em o s ti m p o r t a n tb r a n c h e so fd a t a b a s e t e c h n o l o g y s a i l ，ap r o t o t y p eo fs p a t i o t e m p o r a ld b m s ，s u p p o r t sb i t e m p o r a l & 2 ds p a t i a ld a t a m o d e l s t o r a g em a n a g e m e n ts u b s y s t e m ，w h i c hi st h eb a s e m e n t o ft h es a 虬d e c i d e sh o w t ot a k eb e s tu s eo fm e m o r ya n di nw h i c hs t r a t e g yd a t at a i lb ea c c e s s e dr a p i d l y q u e r y p r o c e s sa n d t r a n s a c t i o nm a n a g e m e n ta g es u p p o r t e db yt h i ss u b s y s t e m s a l ld i v i d e ss p a t i o - t e m p o r a la t t r i b u t e sa n ds p a t i o - t e m p o r a lr e c o r d si n t ot w ot y p e s ： s i z e f i x e da n ds i z e v a r i a b l e r e c o r dw i t hs i z e - v a r i a b l ea t t r i b u t e si sc a l l e ds i z e - v a r i a b l er e c o r d s i z e f i x e do n eh a v es i z e - f i x e ds t o r a g es p a c e , w h i l et h es i z eo ft h ev a r i a b l eo n e ss t o r a g e s p a c em a yc h a n g e 。t h e r e i sao f f s e tt a b l ei nt h eh e a do fs i z e - v a r i a b l er e c o r d ，e a c hi t e mi nt h e o f f s e tt a b l ec o r r e s p o n d st oaf i e l d + i nt h i sw a y , s i z e - v a r i a b l ea t t r i b u t ec a nb es t o r e da n d a c c e s s e d t h e r ei sa l s oa no f f s e tt a b l ei nt h eh e a do fb l o c ka n da l s oe a c hi t e m c o r r e s p o n d s t o ar e c o r d ，r i om a t t e ri ti ss i z e - f i x e do rs i z e - v a r i a b l e b yt h i sm e a n s ，r e c o r d sc a nb es t o r e da n d a c c e s s e di nb l o c k 。 s a i l - i n d e xi sab i t e m p o r a l & 2 d i m e n s i o n s p a t i a li n d e x , w i l h 4d i m e n s i o n sa n di ti s h i 曲d i m e n s i o n i n d e x s a i l - i n d e xd i v i d e st h e4 - d i m e n s i o ni n d e xi n t oab i t e m p o m li n d e x a n das p a t i o - t e m p o r a li n d e xb a s e do nt r a n s a c t i o nt i m e 。t h e s et w oi n d e x e sa g ei n t e g r a t e d b yb i d k e c t i o n a ll i n k s 。e a c hs n b i n d e xi sa2 r - t r e e , w h i e hi sd i 、，j d e di n t ot h ef r o n tr t r e e a n dt h eb a c kr t r e e ，r e p r e s e n t i n gt h ec u r r e n ts t a t ea n dh i s t o r i c a ls t a t e t h eb i t e m p o r a l s u b i n d e x ，2d i m e n s i o ni n d e x ，s u p p o r t sv a l i dt i m ea n dt r a n s a c t i o nt i m ea n di t sf r o n tr t r e e a n db a c kr t r e ei s2 d - r t r e e w h i l es u b i n d e xo f s p a t i o t e m p o r a li n d e xb a s e do n t r a n s a c t i o n t i m ei sc o m p o s i t eo ft w o3 d r t r e e s a i li st h e p r o t o t y p eb ye x t e n d i n gd b m sp o s t g r e s o l , a n d i t sr u n n i n ge n v i r o n m e n t j s1 i n u x 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 ；v a l i dt i m e ；t r a n s a c t i o nt i m e ； s p a t i o - t e m p o r a li n d e x 华中科技大学硕士学位论文 1 1 现代数据库技术 1引论 从2 0 世纪8 0 年代以来，数据库技术在商业领域的巨大成功刺激了其它领域对数据 库技术需求的迅速增长。这些新的领域一方面为数据库应用开辟了新的天地，另一方面 在应用中提出的些新的数据管理需求也直接推动了数据库技术的研究与发展l l j 。 大量新的数据库应用，例如：地理信息系统( g i s ) 、计算机超大规模集成电路辅 助设计( v l s ic a d ) 、人工智能( 舢) 和实时系统等，对数据库技术提出了新的需求， 而传统的数据库无法良好的支持这些需求，例如：要求存储和处理复杂对象，支持 复杂的数据类型，需要常驻内存的对象管理以及支持对大对象的存取和计算，实现 程序设计语言和数据库语言的无缝集成，支持长事务和嵌套事务的处理等等。 因此传统的数据库技术需要进一步发展，现代数据库应运而生。现代数据库在 数据模型、具体技术以及应用领域和传统的数据库技术有很大的差别。 数据库技术发展的核心是数据模型的发展。现代数据库对传统的关系模型进行 了扩充，引入了少数构造器，使它能够表达较复杂数据类型，增强其结构建模能力。 提出全新的数据构造器和数据处理原语，能够表达复杂的结构和丰富的语义，例如： 提出了函数数据模型( f d m ) 、语义数据模型( s d m ) 等。另外在数据库技术中引入了面 向对象的思想，提出了面向对象的数据模型。 传统的数据库技术和其它计算机技术相结合，产生了很多新的数据库技术。例 如：数据库技术和分布处理技术相结合，产生了分布式数据库，和多媒体数据库相 结合产生了多媒体数据库，和并行技术相结合产生了并行数据库。 另外数据库技术应用到特定的领域中，出现了数据仓库、工程数据库、统计数 掘库、空问数据库、科学数据库等多种数据库，使得数据库的应用范围不断扩大。 现代数据库正是通过数据模型、和其它计算机技术结合以及和具体的应用领域 结合三个方面不断发展的。 1 2 时空数据库的提出 在现实问题中，许多数据对象都会同时涉及到空间和时间的概念，需要描述对 华中科技大学硕士学位论文 = = = = = ；目= = j = ；目。= = = ；= = = ；目= = = = = = ；= = ；= = ；= = = 象的空间位置和存在时间，例如：作战指挥系统需要记录各兵种、火力在不同时间 的配置，g p s 系统中需要跟踪车辆位置，移动通信网络( m o b i l ep h o n en e t w o r k s ) 中不 同移动用户之间需要保持交互，环境管理系统中需要管理地形地貌随时间变化的数 据。传统的数据库技术并不适合管理时空数据，因为时空数据必然是多维的，因而 在处理上更为复杂，另外时空数据的数据量非常大，存储上也更为复杂。时空数据 库需要新的数据模型，数据库架构，对象存储结构，多维索引机制，查询评估策略。 但是目前，支持时间数据的时态数据库，和支持空间数据的空间数据库都是各 自独立发展的，时空并没有有效的结合起来。这些问题都需要时空数据库 ( s p a t i o t e m p o r a ld a t a b a s e ，简记为s t d b ) 的支持，才能得以高效的解决。 1 3 地理信息系统、空间数据库和时态数据库 时空数据库是地理信息系统( g i s ) 、空间数据库和时态数据库深入研究和发展的 必然结果。目前g i s 、空间数据库和时态数据库的各种技术问题都得到了比较深入和 充分的研究，为时空数据库的相关技术问题的解决奠定了坚实的基础。时空数据库 的实现主要从两个方向进行：向空间数据库中引入时态属性，或者向时态数据库引 入空间属性。但是前者更被研究者看好【2 j 。 1 3 1 地理信息系统 地理信息系统( 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 ，简称g i s ) 是以采集、储存、管理、 分析和描述整个或者部分地球表面以及空间和地理分布有关的数据的空间信息管理 系统。 g i s 技术的主要内容包括【3 】： 1 空间数据的表达：用何种方式表达空间数据对象，目前主要有三种方式：栅 格表达方式、矢量表达方式、栅格和矢量混合表达方式。 2 空间数据的处理：指对空间数据的计算和变换、包括空间数据的基本算法、 图形编辑、拓扑关系的自动建立、图形的裁剪和合并、图幅接边、坐标变换、矢量 栅格数据的相互转换和三维空间数据处理等。 3 空间数据的管理：包括空间数据的组织和空间索引等。 4 空间查询与分析：包括空间查询、叠置分析、缓冲区分析、网络分析、三维 2 华中科技大学硕士学位论文 = = 2 = = ；= = = = = = = 自= = ；= = ；= _ ；= = 自= 目= j = = 自z ；= 目 ： 空问分析和空间统计分析等。 目前国内外的g i s 技术已经相当成熟了，国际上流行的g i s 软件有：a u t o d e s k 公司的m a p g u i d e ，e s r i 公司的m a p o b j e c ti m s ，i n t e r g r a p h 公司的g e o m e d i aw e b m a p ，m a p l n f o 公司的m a p l n f op r o s e r v e r 。国内经过若干年的发展也诞生了一批具有 竞争力的g i s 产品，例如g e o s t a r ，m a p g i s 。c i t y s a r , v i e w g i s 等。 1 3 2 空间数据库 空间数据库( s p a t i a ld a t a b a s e ，简记为s d b ) 是解决空间数据( 点、线、面、体) 的表示、存储、查询等处理的数据库系统。从数据模型的角度而言，必须支持空间 数据类型和空间查询语言。从实现的角度而言，必须提供空间索引以及有效的空间 连接算法【4 1 。 空间数据库技术的主要内容包括川： i 空间数据模型：它是描述空间实体和空间实体关系的数据模型。一般来说可 以用传统的数据模型加以扩充和修改来实现，也可以用面向对象的数据模型来实现。 2 空间查询语言：空间数据查询包括位置查询、空间关系查询和属性查询，前 两种是空间数据库特有的。 3 空间数据库管理系统：提供对空间数据的空间关系定义和描述；提供空间数 掘查询语言，实现对空伺数据的高效查询和操作；提供对空间数据的存储和组织： 提供对空间数据的直观显示等。空间数据库管理系统比传统的数据库管理系统在数 掘的查询、操作、存储和显示方面要复杂许多。 g i s 和空间数据库既有联系又有区别。早期的g i s 对空间数据的管理不是通过数 据库，而是通过文件系统来实现的。后来发展到g i s 用数据库作为底层平台来管理 数据，但是这种数据库只是传统意义上的数据库，空间数据类型几乎没有得到有效 的支持。而现代g i s 是以空间数据库作为底层数据库平台的。 空间数据库的技术已经比较成熟了。很多学者对空间数据库的相关问题做了深 入的研究，例如：g u e t i n g 提出了针对空间数据类型的r o s e 代数【5 】 r a p e r 和 l i v i n g s t o n e 提出了空间数据模型【切。目前出现了很多原型系统和商业产品。例如： s a n d ，g r a l ，p r o b e ，g e o + + ，这些系统都是在传统的关系模型系统的基础上扩展得到 华中科技大学硕士学位论文 = = 。= # = = # = 自；= = _ = = ；女目= # 自2 = ；# 2 # ；目 ； 豹辩空数据淳管理系统l 电7 ，8 t 9 l 。 1 3 3 时态数据库 时态数据库( t e m p o r a ld a t a b a s e , 越记为r o b ) 是勰决时态对象表示、存姥、查询等 处理的数攒痒系绕。时态数据库魄发展经j 建嫂令过程：瓣像数攒痒( s n a p s h o t d a t a b a s e ) 、圆滚数拶库( r o l l b a c kd a t a b a s e ) 、历史数撰库f f l i s t o r yd 舔纛b 觞坟羁双时态数 握麾( b i 把m p o r a ld a t a b a s e ) 。对态数据库涉及到瓣题躲下f l o l ： 1 薅态数据蛉表达，墩就是魏侮表示瓣闻。需要躲决翔下懿翔题：基本露闯攀 位懿选择，辩痔静选择，露阔缭梅说明，霹闯赛限说明| 三i 及时阉度鬟静弓| 入。 2 对溺数据的推骜：毽括鲶理不同时态数据溺的稻关髋，摊算数据值韵有效期， 处璞实际或者近似的不一致性，识掰不正确数攒，处理不完全的时态数据。 时态数据库已经得翔比较深入的理论研究和实际应用，例如：学者b o h l e n 专门 从事过辩态数攒库实现的研究工作。目前，育较多的时态数掰库的原型系统出现， 我国也开发出自己琢型系统h b a s e 1 z 。 1 4 豳内外的磷究发震与现状 时空数据库系绞与g i s 、空间数据麾、时态数掇库魄发展紧密期关。2 0 世纪5 0 年代木欺，诞尘了第一令g i s 系统，空闻数据以援揍摸型表示。醚震的g i s 系统鸯 的使躅锻接窆瞄数攒模型，毒酌馒思矢鳖空阕数据模型。笺世纪弼年代拓羚矢霆空 闫数据模型成为主流。矢量空潮数据模嫠使得空阂数据毵容易表达帮蘧解，也便予 处璞吲。更重要的疑，矢蠢数据模狴穰容荔和关系数嚣库鹃关系模登缩合在一起， 自戤空间数据瘁应运而生。2 0 世纪7 0 年代，学者已经注意劐数据瘁系统中的时间问 题，8 0 年代时态数据库的问题得到了更为热烈的讨论。在讨论时态数掇库的同时， 学者们也丌始考虑在g i s 系统上扩充时态的问题【1 4 1 。时定数据库在8 0 年代来期开始 为人们所重视。 从总体上看当前，阑内外对时空数据麾的研究都非常不成熟，尚处于原型系统 的研究阶段，没有大规模应用的产品。研究的比较多方蕊是：数据模型，查询谗言， 索引技术：颓对查询优化，存储结枣句，事务处理等涤入磺究遴圣亍的不是缀充分。 4 华中科技大学硕士学位论文 = = = = = 昌篁昔；鲁宣置= 互= 昔毒罱= = = 掌鲁= = = 鲁鲁宣= 鲁= = 鲁= = 耸= 壹= ； w o r b o y s 、p e u q u e t 等人提出并讨论了时空数据模型【1 5 1 6 1 。a l - t a h a 、f r a n k 和c o h n 等 人在时间和空间推理方面展开了研究【1 8 , 1 9 , 2 0 1 。v o i g t m a r m 等人设计了时空数据库查询 语言。t z o u r a m a n i s 提出了重叠线性四分索引树【2 1 1 ，x u 提出了索引树m r t r e e s 和 r t t r e e s ，t h e o d o r i d i s 提出了3 d r 树【2 2 】，n a s c i m e n t o 提出了索引树h r t r e e s 矧。 对时空数据库研究得最好是欧洲。在1 9 9 6 年，欧洲启动了一个为期4 年名为 c h o r o c h r o n o s 的项目，将欧洲一批在时态数据库或者空间数据库领域颇有成就的学 者联合起来，专门研究时空数据库。其间发表了大量的论文，开发出了实验性的原 型系统d e d a l e ，并且有一定的应用。其中的代表人物是德国r a f t h a r t m u tg u e f i n g 、 m a r t u ss c h n e i d e r 、m a r t i ne r w i g ，希腊的m i c h a l i sv a z i r g i a n n i s 。在美国的伊利诺斯州 ( i l l i n o i s ) 大学在时空模型和时空查询语言的研究上也卓有成就【2 4 ，2 5 】。值得注意的是 在亚洲韩国也在时空数据库的数据模型、索引技术上也做了大量的研究工作1 2 6 , 2 7 1 。 国内时空数据库的研究尚处于起步阶段，而且主要集中在数据模型的研究。浙 江大学、中科院、原武汉测绘科技大学，西南交通大学等科研院校都对时空数据模型 做过一定程度的研究 2 8 , 2 9 , 3 0 , 3 1 , 4 0 】。虽然国内对时空数据库研究的深度和广度远不及国 外，但是国内在时态数据库和空间数据库的研究上还是卓有成果的，四川大学的计 算机学院早在1 9 9 5 年就开发出了时态数据库原型系统h b a s e 1 1 】，而原武汉测绘科技 人学和中国地质大学也有g i s 的商用产品。这些对于科研成果对时空数据库的研究 作了充分的理论和技术的储备。 时空数据库的研究包括以下几个方面1 3 2 】： 1 时间和空间对象的特点及其结构和表示的研究； 2 空数据库的数据模型和查询语言； 3 时空信息的图形用户界面； 4 时空数据库的查询处理； 5 时空数据的存储结构以及索引技术； 6 空数据库的体系结构； 7 时空数据库的事务处理。 5 华中科技大学硕士学位论文 1 5 本文内容 本文以时空数据库管理系统的原型系统s a i l 的研究为背景，讨论了时空数据库 的关键技术，着重研究了时空数据库的存储策略和索引机制。第一章介绍了时空数 掘库的背景、国内外研究现状以及关键技术。第二章讨论了s a i l 系统的体系结构。 第三章讨论了s a i l 系统的数据模型。第四章讨论了s a i l 系统的存储策略。第五章 讨论了s a i l 系统的索引机制。第六章为结束语，对全文所作的工作进行了概括和总 结。 6 华中科技大学硕士学位论文 2s a i l 系统的体系结构 s a i l 系统是我们在l i n u x 环境下扩展d b m sp o s t g r c s q l 后的时空数据库管理系 统( 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 es y s t e m ，简称嘞m s ) 的原型系统。 2 1s a l l 系统的总体结构 + s a i l 系统是客户服务器体系结构( c l i e n t s e r v e r a r c h i t e a u m ) ，如图2 1 所示。 客户端和服务器可以在不同的主机上，一台服务器可以处理来自多个客户端的请求， 它们之间通过t c p i p 网络联接通讯。 图2 1s a i l 系统整体结构图 s e r v e r 端运行s a i l 系统的核心程序，实现时空数据的查询、存储和以及事务控 制等各项功能。 c l i e n t 端主要是用户界面( u i ) 程序。用户通过用户界面向s e r v e r 端提交数据库 操作请求，并显示数据库操作结果。c l i e n t 对s e r v e r 端数据库的操作是通过o d b c 接口支持完成。 2 2s a i l 服务器端的系统结构 s a i l 从查询处理、存储管理和事务管理三个方面扩展了p o s t g r e s s q l , 使得系统 支持时空数据模型、时空查询语言、时空数据的索引存储以及时空事务控制等时空 特性。s a i l 系统s e r v e r 端的体系结构如图2 2 所示。 7 匈蓊i疆藿蒜 一 虱一 华中科技大学硕士学位论文 数据库管理员 图2 2s a i l 系统服务器端系统结构图 2 2 1s a i l 查询处理子系统 据 s a i l 查询处理子系统包括：s a i l 查询编译器、s a i ld d l 编译器、执行引擎三 个部分。 s a i l 语言编译器，将时空查询语言s a i l - s o l 翻译成时空查询计划。s a i l 的编 译过程包括三步：首先分析文本形式的s 越l s q l 查询语言，生成查询分析树；然 后对查询进行语义检查，并对查询分析树进行转换，得到表示最初查询计划的代数 操作符树；最后将最初的查询计划转换为对于实际数据的最有效的序列操作序列。 a 询编译器利用元数据和关于数据的统计信息来确定哪一个操作序列可能是最快的， 例如：一个索引的存在可能会使得某个查询计划比另一个计划快许多。 s a i ld d l 编译器是专门进行d d l 语言处理的编译器。d d l 共分为两种：定义 8 华中科技大学硕士学位论文 模式的d d l ，定义子模式的d d l 3 3 】： 1 模式d d l 是用来定义数据库整体结构的。包括定义记录类，文件名，数据项 名，数据类型，长度，文件间的联系，完整性、安全性约束等。用模式d d l 描述以 上信息得到的程序就是数据库的模式，是数据库的一个框架，即结构图。模式经过 d d l 编译器编译后，生成目标模式，是一组表，s a i l 系统将它装入数据字典，它是s a i l 系统进行一切操作必须参照的标准。 ， 2 子模式d d l 是用来定义局部逻辑数据结构的。包括局部所需的文件名，记录 类，数据项名及其来源于何种文件记录、何种数据项。子模式的各项命名、数据项 的个数以及次序，它们均可不同于模式。同一子模式可为多个应用程序共用。予模 式d d l 描述的模型经过d d l 编译器编译以后产生目标子模式，也是放在数据字典中， 供s a l 系统参照使用。 执行引擎负责执行查询编译器产生的查询计划。执行引擎与s a i l 系统中的大多 数其他成分都有交互：为了对数据进行操作，必须从数据库取得数据并放到缓冲区 - h 还需要同并发控制器进行交互，以避免非法访问被加锁的数据：还需要和日志 管理器进行交互，以确保对数据库的所有修改都正确的记录了日志。 2 2 2s a i l 存储管理子系统 s a i l 存储管理子系统负责如何高效的利用磁盘空间来存放数据，并使得数据能 够被快速存取。s a i l 存储管理器由三部分组成：s a i l 索引、文件和记录管理器， 缓冲区管理器和s a i l 存储管理器f 3 4 】。 索引、文件和记录器接受执行引擎发送过来的对索引、文件和记录的请求，向 缓冲区发送页面命令实现对数据、元数据和索引的操作。s a i l 系统采用了s a i l - i n d e x 索引机制，实现双时态二维空间数据的四维索引，提高了数据访问效率。 时空数据是存储在外存中的，然而必须在主存中才能对数据进行有效的操作。 缓冲区管理器负责对数据库中的数据块和缓冲区的页面进行数据交换。 存储管理器负责和外存介质打交道，将磁盘上存储的数据块，取出并发送到缓 冲区，以页面的形式供上层使用。同时负责将缓冲区的页面数据以数据块的形式存 储在磁盘上。 9 华中科技大学硕士学位论文 = = = = = ；= = = = = = = = = = = ；= = = = = = = ；= = = = = ；= = = ； 2 2 3s a i l 事务管理子系统 s a i l 事务管理子系统负责时空事务处理，它从应用系统接受事务命令，得知什 么时候事务开始，什么时候事务结束，以及应用系统的期望信息。总共包括日志记 录，并发控制和死锁解决三个功能f 删： 1 曰志记录：为了保证持久性，对于s a i l 系统的每一个变化都在磁盘上登记 同志。日志管理器遵循某种策略保证在任何情况下s a i l 系统发生了故障或者挡机， 恢复管理器都能看到关于数据库变化的日志，能够恢复到某一个一致的状态。开始 时，日志管理器将日志写到缓冲区中，然后它与缓冲区管理器协调，保证在适当的 时候将缓冲区写到磁盘中。 2 并发控制：并发控制管理器保证在多个事务并发执行的情况下，执行结果和 某一种串行的执行结果相同。采用的策略是在数据库的某些部分上维护若干个锁， 这螳锁防止两个事务以错误的方式存取数据的相同部分。锁存储在封锁表中。并发 控制管理器按照一定的原则控制执行引擎访问数据库中被封锁的部分，从而对查询 和其他数据库操作的执行发生影响。 3 死锁解决：多个事务竞争s a i l 系统资源时，因为资源被某个事务占用而没 有任何一个事务能够进行下去，这种情况就是死锁。在这种情况下，事务管理器中 止一个或者多个事务，从而使得其它事务能够进行下去。 2 3 本章小结 本章给出了s a i l 系统的体系结构以及各部分的功能。s a i l 是一个在p o s t g r e s q l 基础上改进的c l i e n t s e r v e r 模式的时空数据库原型系统。s e r v e r 端主要包括三个 子系统：s a i l 查询处理子系统，s a i l 存储管理子系统和s a i l 事务管理子系统。三 个子系统协调工作保证s a i l 能够从语言、存储索引以及事务等各个不同的层面上支 持时空数据类型。 华中科技大学硕士学位论文 3s a i l 系统时空数据特征 3 。1 时空数据类型的引入 时空数据库是支持时空对象的数据库系统。时空对象除了具有普通的属性外， 还具有时间属性和空间属性。时间属性在时空数据库中用时间数据类型来实现，空 间属性在时空数据库中用空间数据类型来实现。 3 1 1时间数据类型 从s t d b m s 的实现上来看，时间数据类型包括时间点( e v e n t ) 、时间区间( p e r i o d ) ， 时蚓区间段集合( i n t e r v a l ) - - - 种。p e r i o d 是两个e v e n t 之间的时间段，i n t e r v a l 是p e r i o d 的有限集合。 从功能上区分，时空对象的时间属性可以分为有效时间( v a l i dt i m e ) 乘l 事务时间 ( t r a n s a c t i o nt i m e ) ，简记为v t 和t t 。 一个事实的有效时间是在建模的现实世界中真实存在的时间。有效时间可用 单一的时间点、时间区间来表示，或者表示为多个时间点或时间区间的有限集的 有效时间元素，即一个事实可以联系任意个时间点和时间区间，以单一的时间点 或者时间区间作为重要的特例。有效时间对应于应用或者现实世界变化历史，它 是应用依赖的，即它的值来自应用，或由用户经由应用提供。有效时间可以是“未 来”时间【1 0 , 3 5 】。 一个数据库事实在某一时间点存储到数据库中，此后就是当前状态了，直至 被逻辑地删除。一个数据库事实的事务时间就是它在数据库中存在并且可以被取 h 的时间。通常事务时间是一个时间区间而不是时间点。事务时间对应于现有事 务或哲现有数掘库状念变迁的历史。它是应用独立的，也就是它的值仅根据系统 时钟导出，因而它是应用不可操纵的。事务时间值不能晚于当前事务时间，也不 能改变【1 0 , 3 5 】。 前面提到的回滚数据库仅仅支持事务时间，历史数据库仅仅支持有效时间，而 双时态数据库同时支持事务时间和有效时间。 l l 华中科技大学硕士学位论文 = 崔皇昌；= 皇= 罩昌鲁皇昌= = 鲁= = = = 兰皇罩高= 昌= = 鲁鲁= = = = 皇昌；= = 昌： 3 1 2 空间数据类型 现实世界中的空间对象，经过分析、归类和抽象总可以表达成点、线、面或者 它们的组合。 城镇、乡村居民地、交通枢纽、车站、工厂、学校、医院、机关、火山口、震 中、山峰、隘口、基地等空间对象，从较大地空间规模上来观测它们，可以把它们 归结为点状分布的，因此可以引入空间数据类型点( p o i n t ) 。河流、海岸、铁路：公路、 地下管网、行政边界等空间对象可以归结为线装分布空间对象。为此可以引入空间 数据类型线( t h r e a d ) ，具体地的：可能是线段( 1 s c g ) ，可能是折线( p a t h ) ，有时为了研究 的需要还要用直线0 i n c ) 。而耕地、森林草原、沙漠等空间对象具有大范围连续分布 现象，可以归结为面状分布的空间对象。为此可以引入空间数据类型面( f a c e ) ，具体 的：可能是矩v ( b o x ) ，可能是圆形( c i r c l e ) 还g 能是多边j r ( p o l y g o n ) 。 空间数据除了具有一般数据的特征之外，还具有其特殊性【3 6 】： 1 数据量大、结构复杂、关系多样化：空间对象是多种多样的，空间对象之间 的关系也是多样化的，而且与应用有关； 2 空间性：空间数据描述了空间物体的位置、形态，甚至需要描述物体的空间 拓扑关系，空间性是空间数据区别于其它数据的标志特征； 3 多尺度与多态性：不同的观察尺度具有不同的比例尺和不同的精度，同一地 物在不同的情况下就会有形态差异； 4 查询过程复杂：空间数据一般按空间特征和空间关系查询，由于空间对象的 形状常常不规则，验证查询条件比较复杂； 5 难以定义多维空间对象的空间次序：为了加快数据检索而建立空间索引是首 先必须解决的难题。 3 1 3s a i l 系统的时空数据类型 s a i l 系统的数据支持的数据类型总结如图3 1 。总共包括7 种空间数据类型和3 种时间数据类型。空间数据类型包括一维的p o i n t 和二维的l i n e 、l s e g 、p a t h 、b o x 、 c i r c l e 和p o l y g o n 。时间数据类型包括e v e n t 、p e r i o d 和i n t e r v a l 。 1 2 时空数据类型，空间数据t二：二：薹蓁兰；j。， ， l 时间数据丁筹：妻二8 v 。p e n 。r t 。) 。， 1 3 华中科技大学硕士学位论文 状态改变的简洁描述。本模型按照事先设定的时间间隔采样，它只存储某个时间的 数据状态( 基本状态) 和对于基本状态的变化量。更新式模型也有矢量更新式和栅格更 新式模型。基本状态更新的每个对象只需存储一次，每变化次，只有很小的数据 量记录。只有在对象发生变化时才存入系统中，而且只存储其变化的部分。虽然和 时间片快照模型相比，减少了相同内容重复存储的空间，但是为了得到完整的当前 状态必须参考以前的基本状态的数据。这个模型对于将整个地理区域作为处理对象 时，处理方法难度较大，效率较低。 时空复合模型( s p a c e t i m ec o m p o s i t em o d e l ) 1 2 6 3 7 q 辱空间分隔成具有相同时空过 程的最大的公共时空单元，每次时空对象的变化都将在整个空间内产生一个新的对 象。对象把在整个空间内的变化部分作为它的空间属性，变化部分的历史作为它的 时态属性。时空单元中的时空过程可以用关系表来表达。若时空单元分裂时，用新 增的元组来反映新增的空间单元。这种设计保留了沿时间的空间拓扑关系。所有更 新的特征都被加入到当前的数据集中，新的特征之间的交互和新的拓扑关系也随之 生成。这个模型和前面提到的基本状态更新模型有点像，但是随着时间的推移，快 照会分解成越来越多的小区域，每一块小区域代表一个特定时间。 t e m p e s t 三角模型( t e m p e s tt r i a dm o d e l ) t 2 6 , 1 6 l 由三部分组成：基于特征的o b j e s t 模型、基于位置的l o c e s t 模型和基于时间的e s ) m 模型。o b j e s t 模型管理对 象的一般信息，例如：o i d ，对象名等。l o c e s t 模型管理对象的空间信息，例如： 对象的位置，对象间的拓扑关系。而e s t d m 模型则管理对象的历史信息，当某个 特定对象的属性发生了变化，e s t d m 模型的事件表中就存入一个事件。 3 2 2s a i l 数据模型 上一节的各种时空数据模型虽然关注对象各属性的随着时间的变化，但是时间 属性分为事务时间和有效时间两种，以上的各种时空数据模型只提到了一种时间， 而且没有明确具体是事务时间还是有效时间。 为此s a i l 系统采用的s a i l 数据模型解决了以上的问题。s a i l 数据模型支持双 时态二维空间( b i t e m p o r a l 2 - d e m e n s i o n s p a t i a l ) 的时空数据。s a i l 的形式化定义如 下： 华中科技大学硕士学位论文 s t d b ：= t t ：= l v t = ：= i t t p ：= v t p ：= t t s ：= r r e ：= v t f ：= v t t ：= t 玎s t s ：= t s i jt s i e d ( t ) ，i = 1 ，2 ，3 ) s ：= a t t r ：- - n o n _ s p a t i o t e m p o r a la t t r i b u t e o i d ：- - t h ei do f s 0 ：= l l p o i n t ：= ap o i n t t h r e a d ：= l i f a c e ：= l l f l a g ：= a3 b i t ss i g n 其中，t t ，v t 分别是指事务时间和有效时间，t i p 表示事务时间点，v t p 表示 有效时间点，r r s 表示事务时间区间的起点，t t e 表示事务时间区间的终点，v t f 表 示有效时间区间的起点，v t t 表示有效时间区间的终点，t s e d ( t ) 是时间域中的一个 值，s 指空间对象。a t t r 表示非时空属性，即常规属性三位标志符f l a g 用来标记内 存中时空对象的特性：1 0 0 表示非没有空间属性的对象；0 1 0 表示普通的当前状态的 空间对象，0 0 1 表示历史状态的空间对象，之所以这样标记是为了优化时空对象的事 务处理。 3 3 本章小结 本章讨论了时空数据类型以及时空模型。首先，引入了时间数据类型和空间数 据类型，并给出了s a i l 系统支持的时空数据类型；然后介绍并评价了已有的各种时 空数据模型，最后给出了s a i l 系统的所使用的s a i l 数据模型。 华中科技大学硕士学位论文 4s a i l 的存储管理 时空数据库必须支持时空数据。而时空数据必须以有效方式存储起来，数据库 才能稳定高效的运转。s a i l 系统实现的空间数据类型包括：p o i n t 、l i n e 、l s e g 、p a t h 、 b o x 、c i r c l e 、p o l y g o m 实现的时间属性包括：e v e n t 、p e r i o d 、i n t e r v a l 。本章讨论了以 上各时空数据类型的存储管理，主要侧重于存储结构的研究。 4 1 s a i l 的存储结构 一个数据库对象由各种属性的组合来描述。在存储系统中，属性用“字段”来 实现，字段是最基本的数据元素。许多定长字段如整数或者定长字符串被简单的分 配适当的字节数就可以了。而变长字段则需要用指针控制存储空间的大小。 数据库对象的完备描述是通过“记录”来实现的。记录由几个字段再加上个 记录首部组成。首部包括有关记录的信息，可能包括像时间戳、模式信息和记录长 度这样的信息。有的记录包含有一个或多个变长字段，记录首部的偏移量指针可以 用于定位记录内的变长字段。 记录存储在一个或者多个中“块”里面，块是i o 的基本单位。块首部是有关块 的信息，占用块中的一些空间，其余空间由一条或者多条记录占用。如果记录不能 存储在一个块里面，则将记录分成两个或者多个片段，不同的片段存储在不同块上， 不同的块通过块首的指针连接起来【3 ”。 4 2 s a i l 空间属性的存储实现 4 2 1 点p o i n t 点是空间数据类新类型的基本构造单位。在s a i l 系统中存储点的x 和y 坐标： p o i n t ( x ，y ) ，x 和y 均为d o u b l e 类型，总共需要存储空间1 6 b y t e 。p o i n t 的存储结 构如图4 1 。 二工二 8 b y t e8 b y t e 图4 1 p o i n t 的存储结构 华中科技大学硕士学位论文 = = = = = ；= = = e = ；= = = = 自= = = = ；= = ；= = j i ；= = = = = = = ；自= ：； ； ； 4 2 2 直线l i n e s a i l 系统中存储直线l i n e 上的不重合的两个点p 1 ，