（计算机应用技术专业论文）面向移动区域的移动对象数据库研究.pdf

摘要 摘要 移动对象数据库是管理移动点和移动区域的位置和范围的复杂系统。当前 涉及移动区域的时空应用( 火灾模拟、海啸监控等) 越来越多，然而移动对象 数据库研究多集中于移动对象位置管理，因此迫切需要针对移动区域的移动对 象数据库进行深入的研究。本论文针对面向移动区域的移动对象数据库关键问 题进行了系统深入的研究。 论文首先系统研究了移动对象的时空语义。时空语义是构建数据模型乃至 整个移动对象数据库的基础。首先对时空变化进行了系统分类，提出了一套完 备的时空变化描述方法，该方法以对象标识和描述符为基础，通过对象级时空 变化和属性级时空变化来描述时空变化。其中对象级时空变化是显式的，而属 性级时空变化是隐式的。 在时空语义研究的基础上，我们提出了新的基于抽象数据类型和约束数据 库理论的对象关系数据模型网格划分模型( g r i dp a n i t i o nm o d e l g p m ) 。 g p m 以时空关系和时空元组来表示移动对象，以扩充的关系代数操作作为时空 关系的查询操作。移动对象的时空数据和时空变化以时空数据类型和演化拓扑 类型来表示，时空数据和时空变化的查询则通过这些类型上的操作来实现。论 文详细讨论了g p m 模型的数据结构、查询操作和语言以及g p m 使用单元网格对 移动区域复杂外形进行建模的算法，并提供了模型参数用于表示建模的精度。 模拟实验验证了该建模方法的有效性。 为了支持基于g p m 的时空查询，论文针对基于t p r 树的预测时空查询提出 了时空选择查询和连接查询的代价模型，用于预测查询的磁盘访问代价。这些 代价的计算仅与数据集以及t p r 自身的设置参数相关，而与实际t p r 树底层的数 据分布和结构无关，从而简化了代价的计算。在不同规模模拟数据集上的实验 表明，这些代价模型能够有效预测时空查询在t p r 上执行时的访问代价。在上述 代价模型的基础上，本文提出了一种基于t p r 树和鲥df i l e 索引结构的混合索引 方法，并分析了各自的预测时空查询代价。移动区域模拟数据集上的实验和分 析表明其中一种混合索引结构在查询性能上明显优于已有的单独索引结构，能 够有效支持移动区域的预测时空查询。 在g p m 模型和时空金询研究的基础上，本论文提出了移动对象数据库管理 摘要 系统的原型实现方案，并在对象关系数据库管理系统上实现了原型系统。为了 实现复杂的审问操作，文中提出了基于逆时针有向三角形的空间操作实现方法， 并给出了各种移动区域空问操作的实现算法。论文进一步分析了在开源 p o s t g r e s q l 数据库上实现基于g p m 的移动对象数据库管理系统的数据处理流 程，表明g p m 模型是易于实现的。 与已有的研究相比较，本文的新贡献在于： ( 1 ) 针对面向移动区域的移动对象数据库，提出了一套系统完备的研 究方法和实现框架，包括：时空语义、数据模型和建模方法、时空查询和索引 方法以及数据库实现原型。弥补了已有研究工作中的缺失。 ( 2 ) 提出了一种显式的对象级时空变化与隐式的属性级时空变化相结 合的时空语义描述方法，克服了已有研究缺乏完备性的缺点( 缺少对主题属性 连续变化的研究) ，从理论上保证了时空变化的完备性描述。 ( 3 ) 提出了一个新的基于抽象数据类型和约束数据库理论的数据模型 g p m 。g p m 可以有效表示和有询移动区域和移动点的各种时空变化，可以使用 类型扩展的方法顺利地转换到对象关系数据库管理系统上实现，解决了已有数 据模型难以实现的困难。g p m 创新性的利用单元网格软取移动区域的离散和连 续表示。 ( 4 ) 提出了针对预测时空查询的代价分析模型以及混合索引结构，弥 补了目前移动对象数据库研究中的空白。 ( 5 ) 提出了针对移动区域建模的实现原型，改进了基于逆时针有向三角 形的空间操作实现方法。该方法可以有效地实现各种复杂空间操作，避免了直 接基于顶点坐标计算各种卒间操作的值时对效率的影响。 关键词：移动对象数据库移动区域数据模型代价模型时空索引 木本论文研究工作得到国家8 6 3 计划7 0 8 项目( 编号2 0 0 2 a a 7 8 3 0 5 5 ) 和国家自然 科学基金( 编号6 0 4 0 3 0 2 0 ) 的支持。 a b s t m c t a b s t r a c t m o v i n go b j e c td a t a b a s ei sac o m p l e xs y s t e mr e l a t e dt om a n a g et l l ep o s i t i o n sa n d e x t e n t so fm o v i n gp o i n ta n dm o v i n gr e g i o n w i t h i n c r e a s i n gs p a t i o t e m p o r a l a p p l i c a t i o n sb a s e do nm o v i n gr e g i o ns u c ha sf i r es i m u l a t i o na n dt s u n a m im o n i t o r i n g ， l t sv e 巧n e c e s s a d ，t or e s e a r c ho nm o v i n gr e g i o nb e c a u s ec u j l r e n t r e s e a r c ho n l v f o c u s e so nt h el o c a t i o ni m n a g e m e n to fm o v i n go b j e c t s n i sd i s s e n a t i o nm a k e sa s y s t e m a t i ca l l dt h o r o u 曲s t u d yo nk e yi s s u e so nm o v i i l gr e g i o no e n t e dm o v i n g o b j e c t sd a t a b a s e t h es p a t i o t e m p o r a ls e m a n t i c so fm o v i n go b j e c t sa r e6 r s t l ys t u d i e d ，w h i c ha r e t h eb a s i st 0c o n s t n j c td a t am o d e l s 缸l de v e nt 0t l l ew h o l er e s e a r c ho n m o v i n go b i e c t s d a t a b a s e s as y s t e m a t i cc l a s s i f i c a t i o no ns p a t i o t e m p o r a lc h 锄g e si sp r e s e n t e di nt h e d l s s e r l a t l o na n dan e wc o m p l e t ea p p r o a c bt o t h ed e s c r i p t i o no fs p a t i o t e n l p o r a l c h a n g e si sp r o p o u n d e d ，b a s e do nw h i c has p a t i o t e m p o r a ls e m a n t i cm o d e l i s 如n h e r d e s i g n e d t h en e wa p p r o a c ht or e p r e s e n t i n gs p a t i o t e m p o r a lc h a n g e s ，w h i c hi sb a s e d o n o b j e c ti d e n t i t ya n dd e s c r i p t o r s ，d e s c b e s s p a t i o t e m p o m lc h a n g e su s i n g o b j e c t l e v e ls p a t i o t e m p o r a lc h a n g e sa n da t t r i b u t e 1 e v e ls p a t i o t e m p o r a lc h a n g e s t h e f o 咖e ri se x p l i c i t l yr e p r e s e n t e d ，w h i l et 1 1 el a t t c ri si m p l i c i t 1 1 1 h e t e df - r o mt l l er e s e a r c ho ns p a t i o t e m p o r a l s e m a n t i c s ，an e wd a t am o d e l 肋m e dg p m ( g r i dp a n i t i o nm o d e l ) i sp r e s e n t e d ，w h i c hi sb a s e da b s 仃a c td a t at y p c s a 1 1 dc o n s t i a i n td a 讪a s et h e o 巧g p mi sf o u n d e do nt h eo b ! i e c t r e l a t i o n a ld a t am o d e l i ng p m m o v i n go b j e c t s a r e r e p r e s e n t e d 硒 s p a t i o t e i n p o r a l r e l a t i o n sa n d s p a t l o t e m p o r a lt u p l e s ，a i l dq u e n e so ns p a t i o t e m p o r a lr e l a t i o n sa r ei m p l e m e n t e d t 1 1 r o u g ha ne x t e n d e dr e l a t i o n a la l g e i b r a s p a t i o t e m p o r a ld a t at y p e sa n dd e v e l o p m e n t t o p o i o g yt y p e sr e p r e s e n tt h es p a t i o t e m p o r a ld a t aa n dc h a n g e so fm o v i n go b j e c t s q u e r i e so ns p a t i o t l e m p o i a ld a t aa n dc h a n g e sa r es u p p o n e db yt h eo p e r a t i o n sd e f i n e d o nt h e s ed a t at ) ，p 雌t h ed a t as t m c t u r e s 髓da l g o r i t h m sf o rm o d e l i n gt l l e i 盯e g u i a r e x t e r i t so fm o v i n gr e g i o na r ed i s c u s s e di i ld e “1 q u e 叮o p e r a t i o n s 柚dl a n g u a g ea r e a l s oi n v o l v e d s e v e r a lp a r a m e t e r sa r ep r o p o s e dt os t a l l df o rt l l ep r e c i s i o no f m o d e l i n g 1 a b s t m c t e x p e r i m e n t s r e s u l t sp r o v et l l ee f f e c t i v e n e s so fm o d e l i n gm e t h o d t os u p p o ns p a t i o t e m p o r a lq u e r i e sb a s e do ng p ma n de s t i m a t et h ed i s kc o s to f p r e d i c t i v eq u e r i e s ，t h ed i s s e n a t i o np r o p o s e sc o s tm o d e l sf o rs p a t i o t e m p o r a ls e l e c t i v e a n dj o i nq u e r i e sb a s e do nt p r - t r e es t l l j c t u r e s t h ec o s tc o m p u t a t i o no ft h em o d e l si s o n l yr e l a t i v ew i t ht h ep r o p e n i e so fd a t a s e t sa n dt p r - t r e e ，a n dn e e dn ok n o w l e d g eo f t h eu n d e r l y i n gt p r - t r e es 扛u c n j r e sa n d ( h t ad i s t r i b u t i o n ，s ot h ec o m p u t a t i o no fc o s t w i l lb er e d u c e d e x p e r i m e n t sr e s u l t so ns i m u l a t e dd a t a s e t ss h o w 吐l a tt h ec o s tm o d e l s a r ee f f e c t j v ef o re s t i m a t i n gt h ec o s to fs p a t i o t e m p o r a lq u e r i e s b a s e do nt h ep r o p o s e d c o s tm o d e l s ，t p r - t r e ea n dg r i d6 l e ，h y b r i di n d e xs t n j c t u r ei sp r o p o s e dt os u p p o r t s p a t i o t e m p o r a lp r e d i c t i v eq u e 巧i n go ft h ec u r r e n ta n dp r e d i c t e d6 j n l r e e x t e n t s e x p e m e n t a lr e s u l t sp e o n n e do ns i m u l a t e d ( 1 a t a s e t ss h o wt h a tt h ep r o p o s e di n d e x s t l l j c t u r e sa r ee f k c t i v ef o rq u e r y i n gt h ee x t e n t so fm o v i n go b j e c t s o nt h eb a s i so fg p ma n ds p a t i o t e m p o r a l q u e 拶，t h ea p l ) r o a c h e s t ot h e i m p l e m e n t a t i o no fm o v i n go b j e c t sd a t a b a s em a n a g e m e n ts y s t e m sa r ed j s c u s s e d a sa r e s u l t ，t h eg p m b a s e ds t d b m so no b j e c t - r e l a t i o n a ld a t a b a s em a n a g e m e n ts y s t e m s p r o t o t y p ew a sd e v e l o p e d t os u p p o nc o m p l i c a t e ds p a t i a io p e r a t i o n s ，w ep r o p o s ea n e wm e t h o dt h a ti sf o u n d e do nc o u m e r c l o c k w i s ed i r e c t e dt r i a n g l e ，a n dt h ea l g o r i t h m s f o rc o m p l i c a t e ds p a t i a lo p e r a t i o n sa r et h e nd e f - m e dt o o 1 1 1 r o u g ht h ed e t a i l e da n a l y s i s o nt h ei m p l e m e n t a t i o np r o c e s s e sa n dr e s u l t so ft h eg p m - b a s e dd a t a b a s em a n a g e m e n t s y s t e m ，i ti so b s e n ，a b l et h a t 也eg p mm o d e li se a s yt ob ei m p l e m e n t e d c o m p a r e dw i t hp r e v i o u sr e s e a r c h e s ，t h en e w c o n t b u t i o n so ft h et h e s i sa r e ： 1 s y s t e m a t i c a n d c o m p l e t ea n a j y t i c m e t h o d sa n d i m p j e m e n t a t i o n f r a m e w o r ka r ep r o p o s e dt or e s e a r c ho nm o v i n gr e g j o n so r j e n t e dm o v i n go b j e c t s d a t a b a s e t h es t u d i e si n c l u d es p a t i o t e m p o r a ls e m a n t i c s ，d a t am o d e la n dm o d e l i n g m e t h o d ，s p a t i o t e m p o r a lq u e 巧a n di n d e xs t r u c t u r ea n dt h ei m p l e m e n t a t i o np r o t o t y p e o fm o v i n go b j e c t sd a f a b a s e t h ew o r kc o m p l e t e st h ec u l l r e n tr e s e a r c ho nm o v i n g o b j e c t sd a t a b a s e 2 p r o p o s e san e wa p p r o a c ht ot h ed e s c r i p “o no fs p a t i o t e m p o r a ls e m a n t i c s i nt h en e wa p p r o a c ht h ee x p l i c i to b j e c t l e v e ls p a t i o t e m p o r a lc h a n g e sa n dt h ei m p l i c i t a t t r i b u t e l e v e l s p a t j o t e m p o r a lc h a n g e sa r es y n t h e t i c a l l yu s e d ，s ot h ea p p r o a c hc a n o v e r c o m et h es h o n c o m i n g so fp r e v i o u sr e s e a r c h e sm a tl a c ki n c o m p l e t e n e s sa n d i v a b s t r a c t s y s t e m a t i z a t i o ns u c h 淞t h e m a t i cc o n t i n u o u sc h 锄g e ，a 1 1 dc a ng u a r a n t e et l l ec o m p l e t e d e s c r i p t i o no fs p a t i o t e l p o r a lc h a n g e si nt l l e o w 3 p r e s e t sa ni n n o v a t i v ed a t am o d e ig p m ，w h i c hi sb a s e do na b s t r a c td a t a 锣p e sa n dc 仰s t r a i n td a t a b a s e st h e o r y g p mc 姐r e p r e s e n t 锄dq u e 拶v a o u s s p a t i o t e n l p o r a lc h a j l g e se f f e c t i v e l y m e a n w h i l e ，b e c a u s eg p mi sf o u n d e do nt ) ，p e e x t e n s i o n ， s oi tc a nb e呦s f o 加e di n t oa n di m p l e m e n t e do no b j e c t - r e l a t i o n a l d a t a b a s em a n a g e m e n ts y s t e m sa n dc a no v e r c o m et i l ed i 伍c u l t i e so fi m p l e m e n t a t i o n t l l a te x i s ti np r e v i o u s s p a t i o t e m p o r a l d a t am o d e l s i ng p mt l l ed i s c r e t ea n d c o n t i n u o u sr 印r e s e n t a t i o no fm o v i n gr e g i o na r em o d e l e d b yu i l j t 鲥d 4 p r o p o s e sc o s tm o d e i sf o rp r e d i c t i v es p a t i o t e m p o r a iq u e r i e sa n dh y b r i d i n d e xs t r u c t u r e ，w h i c hc 彻叩l e t e s 也er e s e a f c ho nm o v i n go b j e c t sd a 协b a s e s 5 p r o p o s e sa ni m p i e m e n t a “o np r o t o t y p et om o d e lt h em o v i n gr e g i o na n d a ni m p r o v e d a p p r o a c ht oi m p i e m e n t i n gs p a h a lo p e r a t i o n s ，w h i c hi sb a s e do n c o u n t e r c l o c k w i s e d i r e c t e dt r i a n g l e d i 仃e r e n tt y p e so fs p a t i a lo p e 豫t i o n sc a nb e i m p l e m e n t e de f r e c t i v e l yf o u n d e do nt h i sa p p r o a c h t h ea p p i i o a c ha v o i d s 也ei i l n u e n c e o f e 佑c i e n c yw r h e nt oc o m p u t es p a t i a lo p e r a t j o n st l l r o u 曲t l l el i s to fv e r t e x e sd c t l y k e yw o r d s ：m o v i n go b j e c td a t a b a s e ，m o v i n gr e g i o n ，d a t am o d e l ，c o s tm o d e l ， s p a t i o t e m p 0 帆li n d e x t l h er e s e a i hi ss u p p o n e db yt h ef o u n d a t i o no fp r i o j e c t8 6 3 ( g r a n t2 0 0 2 a a 7 8 3 0 5 5 ) a n dt h en a t i o 越lf o u n d a t i o no fs c i e n c e ( g r a n t6 0 4 0 3 0 2 0 ) v 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签 一矿年6 月j 日 秀 乃 磊1 一 第1 章绪论 1 1 研究背景 第1 章绪论 本论文主要研究用于支持在数据库中存储和查询移动区域的方法，即面向 范围的移动对象数据库。随着g p s 、无线通信以及遥感图像等空间定位和可视化 技术的发展，越来越多的应用需要计算随时间不断变化的移动对象信息，自上 世纪9 0 年代后期，出现了针对移动对象的研究。移动对象是随着时间变化的空 间对象，属于时空数据库的研究范畴。其研究基础包括空间数据库( 研究空间 数据在数据库中的表示方法) 和时态数据库( 研究数据随着时间变化的特性) 。 与传统时空数据库仅支持离散变化不同，移动对象数据库重点研究移动对象的 空间属性随着时间连续变化( c o n 缸u o u s l yc h a n g i n g ) 的特性。本节提供一些综 述和研究背景介绍，在简要介绍空间数据库和时态数据库研究后，将介绍移动 对象数据库的起源。 1 1 1 空间数据库 空间数据库的研究目的是为了提供d b m s 数据模型和查询语言的扩展来表 示和查询空间属性数据。( g u t i n g ，1 9 9 4 ) 给出了空间数据库的一个定义：“空间数 据库首先是一个数据库管理系统( d b m s ) ；其次，在空间数据库的数据模型和 查询语言中支持空间数据类型和空间操作；第三，在空间数据库的实现中支持 空间数据类型，提供空间索引，支持空间选择和空间连接。”空间数据库存储的 空间对象o b j e c t s ) ( p a r e d a e n s ，1 9 9 5 ) 信息由两类数据构成：( 1 ) 与空间无关的描 述性数据，通常称为主题属性( t h e m a t i ca 州b u t e ) ； ( 2 ) 描述对象空间状态的 信息，称为空间属性。在空间数据库中，空间对象的主题属性一般用整型、浮 点型和字符型等传统数据类型来表示，而空间数据的管理需要增加新的空间数 据类型和空间操作。 为了实现空间数据库，需要研究描述几何形状的数据结构，几何计算的算 法，多维空间的索引方法以及空间查询的优化方法( 翻译规则和代价估计等) 。 第l 章绪论 审间数据库的主要应用于g i s 应用， i n f o m i x 等) 都提供空间数据扩展， d m b s 上层。 现有的商用d b m s ( o r a c l e 、i b md b 2 和 冈此目前很容易将g i s 等空间应用建立在 空间数据库的核心问题在于空问数据的表示和操作。按照空间概念建模分 类，空间对象分为单个对象( s i n g l eo b i e c t ) 和空间相关对象集合( s p a t i a l l y r e l a t e d c o l l e c t i o no fo b i e c t s ) 。单个对象的三种基础抽象类型为点、线和区域。空间相 关对象集合的两种常见类型为划分( p a n i t i o n ) 和网络( n e t 、o r k ) ，其中划分定 义为一组相互不相交的区域对象，而网络定义为平面上的一组作为节点的点对 象和一组描述边界的线对象。按照空间数据的表示方法分类，空问数据的模型 分为栅格模型和矢量模型。栅格模型以栅格矩阵来表示空间数据。实际应用中 通常以一个栅格来表示一个像素点，因此栅格数据通常以图像的形式存在。栅 格模型的优点是可直接利用遥感、数字摄影测量等图像数据，数据结构比较简 单，方向、邻接及连通计算易实现，但栅格模型对设备的存储空间要求过高( 一 般以栅格图像方式存储) ，而且不存储空间坐标，这使得空间实体的识别和标 识比较困难，查询速度也相对较慢。栅格模型对于按实体组织数据的数据库来 说并不合适。矢量模型以基本几何对象( 点、线、面等) 来表示空间数据。基 本几何对象以采样点的空间坐标表示。例如一个二维区域可以通过个由区域 的边界点构成的多边形来表示。矢晕模犁存储了空间数据的边界坐标，可以方 便地表达空问数据之间的空间拓扑关系。而且在矢量模型中容易对单个目标进 行定义和操作。其缺点是不能直接处理图像数据，而且数据结构相对复杂。矢 量模型是目前流行的空i 日j 数据表示方法，在g i s 等应用中得到广泛的应用。 d b m s 通常使用空间数据类型( s p a t i a ld a t a t y p e ，s d t ) 来封装数据结构及 其操作。空问数据的操作包括空间拓扑操作、空间几何操作和空间属性操作。 空问拓扑操作b u 空问谓词，它判断两个空间数据之间的空间拓扑关系并返回 t r u e 或f a l s e 。典型的空间拓扑关系包括相邻、相离、相交、部分覆盖、完全 覆盖和包含等。空间几何操作是对空间数据执行的几何运算，如求空问数据的 交、空间数据的并等。空间几何操作一般将空间数据视作点集，并以集合操作 的方式来实现。空间属性操作计算空间数据本身的特性值，如求面积、周长等。 一组空问数据类型及其相关操作的集合构成空间代数( s p a t i a la l g e b r a ) 。为 了实现闭包关系，必须仔细设计数据类型。r o s e 代数( g f i t j n ga n ds c i l e i d e r ，1 9 9 5 ) 提供了三种数据类型：点( p o i n t s ) 、线( 1 i n e ) 和区域( r e g i o n ) 。点表示一组 2 第l 章绪论 点集合，线表示一组曲线，区域表示一组可能存在空洞的多边形。r o s e 代数在 这三种数据类型基础上提供了一系列数据操作，如相交、减、轮廓、求和以及 长度等数据操作。在空间数据类型定义后，需要将其扩展至d b m s 的数据模型中， 成为和标准数据类型( 整型、浮点型和字符型等) 一样可以直接使用的数据类 型。空问数据的查询通过标准查询语言s q l 等转换为空间数据类型操作来实现。 要实现这样的数据模型，需要设计数据类型的数据结构以及数据操作的算法， 需要实现空间选择( s e l e c t i o n ) 和连接( j o i n ) 。为了提高空间选择的效率，需 要索引结构的支持，例如主流的r 树索引结构( g u 蛐a n ，1 9 8 4 ) ，将数据类型的值 转换为最小外接矩形( m i n i m 啪b o u n d i n gr e c t a n g l e ，m b r ) 表示，在组织成平 衡树结构。设计新的算法实现空间相交操作，同样需要索引结构的支持。 要实现以上这些功能，一般是在现有d b m s 体系结构上扩展，现有的d b m s 需要提供如下注册接口：数据类型的数据结构，数据类型操作的算法，空间索 引结构及其存取方法，空间相交算法，代价模型算法( 用于查询优化) ，对象 在空间中的分布统计( 用于选择性预测) ，查询优化器，查询语言注册数据类 型的方法以及表达空间数据的用户界面等。 1 1 2 时态数据库 现实世界中任何对象或事件的存在总是与某个时间相关联的。常规数据库 总是只保存一个应用中数据的当前状态。随着时间的推移，数据的状态不断地 变化，数据库也不断更新。每次数据库更新都以新的数据替代旧的数据，因此 数据库的旧的状态就不再保留。如果应用需要查询旧的状态，必须要在数据库 中显式存储该信息，难以实现并且查询执行效率低下。 时态数据库是不仅包含当前数据同时也包含历史数据的数据库( t a i l s e l ， c l i l f f l o r de ta 1 ，1 9 9 3 ) 。在时态数据库中，所有数据都是与时间相关联的，我们把 与时间关联的数据称之为时态数据。在许多应用中，不仅要查询当前的数据， 还要查询历史状态数据，例如医疗系统、证券系统、信用管理等。这些应用需 求也正是时态数据库研究的动机。 时态数据库一般采用版本技术( v e r s i o 血g ) ( t a i l s e l ，c l i 仟o r de ta 1 ，1 9 9 3 ) 来管 理历史数据，即给每个数据都加上一个时间戳( t i m es t a m p ) 。时间戳称为版本 时间( v e r s i o n i n gt i m e ) ，它可以是一个时刻，也可以是一个时间区间。如果时 3 第l 章绪论 间戳加在整个数据库之上，就是数据库版本( d a t a b a s ev e r s i o n i n g ) ，相当于每次 保存整个数据库的个快照。如果时间戳加在关系上，就是关系版本( r e l a t i o n v e r s i o n j n g ) ( g a d i aa n dv a i s h n a v ，1 9 8 5 ) 。如果时间戳加在每个实体( 或元组) 上， 就是对象版本( ob ：j e c tv e r s i o n i n g ) 或称元组版本( t l l p l ev e r s i o n i n g ) ( s n o d g m s sa n d a j l n ，1 9 8 5 ) 。如果时间戳加在每个属性上，就是属性版本( a t t m u t ev e r s i o n i n g ) ( g a d i aa n dy e u n g ，1 9 8 8 ) 。具体采用哪种版本依赖于时态数据模型的设计。 时态数据模型首先需要考虑如何对时间进行建模。在时态数据库中，时间 可看成是一个线性有序的数值集合，因此时间可以等同于某个己知的数值集合， 例如n ( 自然数) 、z ( 整数) 、q ( 有理数) 或r ( 实数) 等。这种时问结构( t i m e s t r u c t u r e ) 称为线性时间结构。线性时间结构是最常用的，也是最简单的一种时 间结构。线性时间结构可以表示为一段线段，称为时间轴。时间轴可以足无界 的( u n b o u n d e d ) ，即无始点无终点；也可以是左有界( 1 e r b o u l l d e d ) ( 有始点 无终点) 或右有界( 一曲tb o u n d e d ) ( 无始点有终点) 的；如果有始点也有终点， 称时间轴是有界的( b o u n d e d ) 。时问也被区分为绝对时间和相对时间，也被称 为确定时间( a n c h o r e dt i m e ) 和非确定时间( u n a n c h o r e dt i m e ) 。 时态数据库中的另一个问题是时问的表示。目前时态数据库中一般采用三 个概念来表示时间：时间子( c h r o n o n ) 、时刻( i n s t a n t ) 和时间区间( t i m ep e r i o d ) 。 时间子是不可分的最小的时间单位( j e n s e n ，1 9 9 8 ) 。时间子长短的选择与所描述的 问题有关，例如出生日期可以取日为时间子，而t 资变化可以取月为时间子。 时间子的长度在时态数据库中称为时间的粒度( g r a n u l 撕t y ) 。时间轴上的一个 时刻( i n s t a n t ) 是该点所在的时间子在时问轴上的序号。时刻可以用一个整数表 示。如果时间轴上的两点同处于一个时间子中，则认为它们是同一时刻。因此， 不能抽象地断定时问轴上a 点与b 点是否代表同一时刻，这个结论只有在指明了 时问的粒度之后才有明确的意义。用时间子来度量时刻实际上是将连续的时间 离散化了。一个时间区间是指两个时刻间的时间，它有明确的起止时刻。时间 的这些概念通过一系列数据类型来表达：i n s t a n t ，p e r i o d ，p e r i o d s ，i n t e r v a l 。 对于时间域的语义，涉及到时态数据库的第三个核心问题：时间的维度( t i m e d i m e n s i o n s ) 。在时态数据库中存在两个不同的时间维，即有效时间( v a l i dt i m e ) 和事务时问( t r a n s a c t i o nt i m e ) ( j e n s e n ，1 9 9 8 ) ，这两个时间维从不同的方面描述 了事物的时态特性。数据的有效时间是指数据在此期间是有效的，即其所代表 的事实在此期间足成立的。事务时间是数据在数据库中插入、删除或修改的时 4 第l 章绪论 间。例如，一个商品的销售时间为“【1 9 9 9 ，2 0 0 2 】”，这一时间是有效时间。但 这一信息不一定在1 9 9 9 年就进入数据库，可能是在2 0 0 0 年，这一时间就是事 务时间。时态数据库是否支持有效时间或事务时间依赖于时态数据模型的设计。 如果时态数据库仅支持有效时间，称为历史数据库( h i s t o r i c a ld a t a b a s e ) ；如果 仅支持事务时间，称为回滚数据库( r o l l b a c kd a t a b a s e ) ；如果同时支持有效时 间和事务时间，则称为双时态数据库( b i t 锄p o m ld a t a b a s e ) 。常规数据库既不 支持有效时间，也不支持事务时间，可称为快照数据库( s n a p s h o td a t a b a s e ) 。 ( s n o d 伊a s s ，1 9 9 5 ) 扩展了时态查询语言，提出了基于b c d m 数据模型的 t s q l 2 ，作为s q l 9 2 标准的一个超集。t s q l 2 语言支持六种时态关系：快照关系， 有效时间状态关系( v a l i ds t a t e ) ，有效时间事件关系( v a l i de v e n t ) ，事务时间 关系( t r a l l s a c t i o n ) ，双时态状态关系( v a l i ds t a t ea i l dt 砌s a c t i o n ) ，双时态时间 事件关系( v a l i de v e n ta n d 仃a n s a c t i o n ) 。状态关系和事件关系的不同在于状态关 系记录某一个时间区间的事实，而事件关系记录某个特定时间点发生的事实。 1 1 3 移动对象数据库 以前，空间数据库和时态数据库是两个相互独立、毫不相关的研究领域。 自2 0 世纪9 0 年代开始，空间数据库和时态数据库的研究者才逐渐认识到各自研 究领域里存在的一些问题以及两者之间存在的联系，开始探索将空间数据库和 时态数据库相结合的相关技术，由此产生了一个新的研究领域时空数据库 ( s p a t i o t e m p o r a ld a t a b a s e ) 。 ( w a n g ，z h o ue ta 1 ，2 0 0 0 ) 认为时空数据库是支持空间、时态和时空概念，并 可以同时捕捉数据的空间特性和时间特性的数据库管理系统。更简单地讲，时 空数据库就是支持空间对象随时间而发生的变化的数据库管理系统。空间对象 随时间而发生的变化在时空数据库里称为时空变化( s p a t i o t e m p o r a lc h a n g e s ) 。 连续时空变化指空间对象随时间连续变化，在时空数据库中称为运动( m o t i o n ) ； 离散时空变化指空间对象的时空变化是间隔的。具有时空变化的空间对象称为 时空对象。我们把时空对象随时间而变化的空间数据称为时空数据。对时空数 据的管理能力是时空数据库与时态数据库