（计算机软件与理论专业论文）双时态xml模型及其查询和更新技术研究.pdf

双时态x m l 模型及其查询和更新技术研究 计算机软件与理论 硕士生：蔡苗苗 指导教师：汤庸教授 摘要 随着计算机网络技术的发展，x m l 作为w e b 上一种新的数据发布语言，将 成为w e b 上下一代“数据表达”和“数据交换”的统一标准。然而，时间是自 然界无所不在的客观属性，所有信息都具有相应的时态属性，x m l 也不例外。 如何表达，查询和更新x m l 中的时态信息已经逐渐引起不少学者们的兴趣。我 们称能够根据时序进行访问的x m l 文档为时态x m l 。 x m l 文档很少是静止的一成不变的，它经常会被修改。引入“时态表达” 后，时态x m l 本身就能够记录x m l 文档的一系列修改痕迹，它为我们提供了 一种高效可行的x m l 版本管理方案。另一方面，由于“传统关系模型”的灵活 性差以及“s o l 语言”的可扩展性低等原因，至今还没有解决如何在已有的商 业数据库系统中支持时态的有效可行的方案。相比之下，x m l 和x q u e r y 比“传 统的关系模型”和s q l 能够更好地支持时态信息表达和时态查询，目前不少学 者开始转向研究如何利用时态x m l 来实现时态信息处理。 本文研究了双时态x m l 的数据模型，以及它的查询和更新技术。首先，我 们提出了一个双时态x m l 数据模型，并探讨和实现了两种将该数据模型映射到 一个具体的双时态x m l 文档的映射方案。接着，我们基于双时态关系下，分析 了时态变量的复杂语义并给出了时态变量的绑定算法。然后，我们用x q u e r y 自 定义了一系列时态函数，用于实现双时态x m l 的时态查询，并提供了支持时态 变量复杂语义的机制。最后，我们借鉴双时态数据库的s n o d g r a s s 表示数据模型 中的更新机制，探讨并实现了双时态x m l 数据模型的更新算法。 关键词：双时态x m l ，数据模型，时态变量，x q u e r y r e s e a r c ho fb i t e m p o r a lx m l sm o d e l i n g ，q u e r y i n ga n du p d a t i n g c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：m i a o m i a oc a i s u p e r v i s o r ：y o n gt a n gp r o f e s s o r a b s t r a c t a st h ef a s td e v e l o p m e n to fc o m p u t e rt e c h n i q u ea n dn e t w o r k ，x m lw h i c hi sa n e wl a n g u a g ef o rd a t ar e p r e s e n t i n g ，i se x p e c t e dt ob e c o m eau n i v e r s a lf o r m a tf o rd a t a e x c h a n g eo nt h ew e b o fc o u r s e ，t i m ei sp r e s e n ti na l m o s ta n yi n f o r m a t i o n ，a n dt h e s a m et ox m lt h et o p i co fr e p r e s e n t i n g ，q u e r y i n ga n du p d a t i n gt e m p o r a li n f o r m a t i o n i nx m lh a sr e c e i v e ds o m ea t t e n t i o n g e n e r a l l ys p e a k i n g , w em a k es o m ec h a n g e so nx m l d o c u m e n t sa st i m eg o e sb y t h e n ，w em a y w a n tt oq u e r ya b o u tp a s ts t a t e so f s u c hd o c u m e n t s b e c a u s et e m p o r a l x m lc a ns t o r et h es u c c e s s i v ev e r s i o n so fad o c u m e n ti na ni n c r e m e n t a lf a s h i o n ，i t p r o v i d e su sah i 曲e f f e c t i v em e t h o df o rv e r s i o nm a n a g e m e n t o nt h eo t h e rh a n d ， a l t h o u g ht h ed e s i g ns p a c eo ft e m p o r a lr e l a t i o n a ld a t a b a s eh a sb e e ns oe x t e n s i v e l y e x p l o r e da st o d a y , n ot e m p o r a ld a t am o d e la n dq u e r yl a n g u a g ee x i s t sw h i c hi s g e n e r a l l ya c c e p t e di nt h er e s e a r c hc o m m u n i t y , o rs u p p o r t e db ym a j o rv e n d o r s t h e t r o u b l e s o m ee x p e r i e n c eo fr e l a t i o n a ls y s t e m sw i t ht e m p o r a li n f o r m a t i o ni sd u et ot h e i n f l e x i b i l i t yo ft h er e l a t i o n a ld a t am o d e la n dt h el a c ko fe x t e n s i b i l i t yo fs q i a n di t d o e sn o tn e c e s s a r i l yc a r r yo v e rt ox m la n dx q u e r y h e n c e ，t h ed a t ad e f i n i t i o n m a n i p u l a t i o nf r a m e w o r ko fx m l x q u e r yc a l ls u p p o r tt e m p o r a lm o d e l sa n d t e m p o r a lq u e r ys i g n i f i c a n t l yb e t t e rt h a nt h et r a d i t i o n a lf r a m e w o r ko fr e l a t i o nt a b l e s s o l a n d t h e r ei sm u c hi n t e r e s ti np u b l i s h i n ga n dv i e w i n gt h eh i s t o r i e so f d a t a b a s ea st e m p o r a lx m ld o c u m e n t s w ea d d r e s st h ep r o b l e mo fm o d e l i n g ，q u e r y i n ga n du p d a t i n gb i t e m p o r a ld a t ai n x m li n t h i sp a p e r f i r s t ，w ep r o p o s eab i t e m p o r a lx m ld a t am o d e lf o rt r a c k i n g i i h i s t o r i c a li n f o r m a t i o ni na nx m ld o c u m e n t a f t e rp r e s e n t i n ga na b s t r a c tm o d e lf o r b i t e m p o r a lx m l ，w e d i s c u s st w od i f f e r e n t w a y s o fm a p p i n gt h i sa b s t r a c t r e p r e s e n t a t i o n i n t o a ( b i t e m p o r a l ) x m ld o c u m e n t t h e n ，w e i n t r o d u c eo u r u s e r - d e f i n e dt e m p o r a lf u n c t i o n s ，a n ds h o wh o wt oq u e r yt h eb i t e m p o r a lx m lw i t ht h e x q u e r yl a n g u a g ea n dt h e s et e m p o r a lf u n c t i o n s f i n a l ly ，w eg i v et h ea l g o r i t h mf o r u p d a t i n gt h eb i t e m p o r a lx m l d a t am o d e l k e yw o r d s ：b i t e m p o r a lx m l d a t am o d e l ，t e m p o r a lv a r i a b l e ，x q u e r y i i i 1 1 引言 第1 章概述 随着互联网的迅猛发展和普及，人们可以通过计算机和互联网连接，从世界 各地实时地接收和发送大量、最新的信息。h t m l ；是信息技术应用上的一个奇迹， 由于其具有简单特性，加上制定了统一标准，使得w e b 技术从计算机界走向社会， 走向干家万户。到目前为止，我们看到几乎所有w e b 页面都是用h t m l 编写的。 但是，随着w e b 的应用越来越广泛，h t m l 过_ 于简单的弱点也越来越明显， 它已经不能满足用户的需求了，这表现在h t m l 菇j 格式的支持、信息应用的支持 及数据交换等多方面的痼疾。正是由于这些缺点，人们开始转向研究能改进或替 代h t m l 的w e b 页面制作语言。其中最有成效的，并已初步投入使用的技术有多 种，其中，可扩展标记语言x m i 就是一个生动的典型。 v i l 作为i n t e m e t 上一种新的数据发布语言，由w 3 c ( w o r l dw i d ew e b c o n s o r t i u m ) 提出。和r i t m l 类似，x m l 也是一种基于标记的标记语言，但是， x m l 具有许多h t m l 所无法比拟的卓越特性，比如，高效可扩展性、操作型、自 描述性、国际化等。由于x m l 的这些优点，它驱动了i n t e m e t 应用程序编写方式 的动态改变，现在已有越来越多的软件向它提供支持，也许在不久的将来它将会 成为w e b 上下一代“数据交换”和“数据表达”的统一标准。 然而，x m l 3 之档很少是静止的一成不变的，它经常会被修改。虽然已经有了 各种形式存储x m l 3 件的方法【1 l 被提出，但仍然无法保留使用者对文件一连串修 改的痕迹。因此，为了避免重要数据的丢失，“旧版本”必须保存。这就出现“如 何保留对文件一连串的修改痕迹”、“如何查询某一时期版本的内容”等一系列问 题，即“x m l 版本管理”问题。为了解决这个问题，人们提出了各种x m l 版本 方案 撕 。然而，这些方案大部分都是将每次修改后的x m l 3 件另存为一份新的 文件，造成很大的信息冗余和管理上的困难：另外，这些方案也较难支持一些复 杂的“时态查询”，比如，当要查询某个x m l 元素的“演变历史”时，则要一一 搜索并比较所有版本，然后再合并查询结果，效率低下。 第1 章概述 随着“时态信息处理”的普及，过去几年出现了大量关于如何在“传统关系 数据库”中支持“时态”的研究i ”，即“时态关系数据库”。既然“x m l 文档” 和“传统关系数据库”类似，都是用于保存数据，同样地，我们也可以考虑将“时 态”引入x m l 。在这里，我们称能够根据时序进行访问的x m l 文档为“时态 x m l ”。通过引入“时态表达”，我们就可以在“时态x m l ”文档中记录它的一 系列“修改痕迹”。因此，我们只需要用一个文件就可以保存不同时间所修改的 x m l ，文档的内容，避免了信息冗余，并简化了时态查询，大大提高了查询效率。 另一方面，虽然在过去几年，出现了大量关于“时态关系数据库”的研究， 其中，文献【8 列举出四十多种不同的解决方案；但是，至今还没有解决如何在 已有的商业数据库系统中支持时态的有效可行的方案，这主要归结于“传统关系 模型”的灵活性差以及“s o l 语言”的可扩展性低等原因。 c l i f f o r d 等人在文献 9 中将时态数据模型分为“t e m p o r a 砂u n g r o u p e d ”( 如表 1 - 1 1 ) 和“t e m p o r a l l y g r o u p e d ”( 如表1 1 2 ) 两类。对比表1 1 1 和表1 1 2 ，我 们容易看出第二种类型的时态数据模型具有更强的表达能力，并且由于它是面向 历史，因此也更自然；相反地，第一种数据模型会造成较多的数据冗余，并会导 致“时态合并”等问题【1 0 1 。因为传统关系数据模型必须符合1 n f ( 即只能描述“结 构化”数据) ，所以它无法支持“t e m p o r a l l yg r o u p e d ”时态数据模型。然而，跟 传统关系数据模型不同，x m l 可以表达“非结构化”数据，因此，它可以很好 地支持“t e m p o r a l l y g r o u p e d ”时态数据模型。另一方面，和s q l 语言不同，x m l 的查询语言x o u e r v 是图灵完备”和自身可扩展( n a t i v e l ye x t e n s i b l e ) 的【1 2 】【13 1 ， 即它本身可以定义各种复杂的时态查询，而不需要依赖于“标准协会”对标准的 扩展。相比之下，x m l 和x q u e r y l l “传统关系数据模型”和s o l 能够更好地支 持“时态表达”和“时态查询”。因此，目前有不少学者开始转向研究如何将时 态关系数据库发布为时态x m l 1 4 】【1 5 】，以及如何扩充s q l 以支持x q u e r v 【16 1 。 可见，“时态x m l ”的研究对于增强x m l 的表达能力、完善小版本管理以 及推动时态信息处理技术具有重要的意义。近年来，如何表达、查询和更新x m l 中的时态信息逐渐引起人们的关注。但是，综观国内外提出的时态x m l 数据模 型，都是基于单时态关系下的，还没有关于双时态x m l 数据模型的研究。因此， 本文将主要探讨双时态x m l 的数据模型，以及它的查询和更新技术。 第1 章概述 表卜卜1 “t e n ；p o r a l l yu n g r o u p e d h is t o r yo f ：e m p i o y e e s i dn a m es a l a r yt i f i e d e p t n o s t a r te n d 1 0 0 1b o b6 0 0 0 0 e n g i n e e r d 0 11 9 9 5 0 1 0 11 9 9 5 0 5 3 l 1 0 0 1b o b7 0 0 0 0 e n g i n e e r d 0 11 9 9 5 0 6 - 0 11 9 9 5 0 9 3 0 1 0 0 1b o b7 0 0 0 0s re n g i n e e rd 0 21 9 9 5 1 0 0 11 9 9 6 0 1 3 1 1 0 0 1b o b7 0 0 0 0t e c h l e a d e rd 0 21 9 9 6 0 2 0 11 9 9 6 1 2 - 3 1 表卜1 2 “t e t r c 加r a l yg r o u p e d h is t o r yo fe m 口io y e e s 讨n a m es a l a r y t i f i e d e p t n o 1 9 9 5 0 1 0 11 9 9 5 0 1 0 11 9 9 5 0 1 0 1 1 9 9 5 0 1 0 11 9 9 5 。0 1 一0 1 6 0 0 0 0 e n g i n e e r d 0 1 1 9 9 5 一0 5 3 11 9 9 5 0 9 - 3 01 9 9 5 0 9 - 3 0 1 9 9 5 0 6 - 0 11 9 9 5 1 0 - 0 11 9 9 5 1 0 - 0 1 1 0 0 1 b e bs re n g i n e e r 7 0 0 0 01 9 9 6 0 1 3 1d 0 2 1 9 9 6 0 2 0 1 t e e h l e a d e r 1 9 9 6 1 2 3 11 9 9 6 1 2 - 3 1 1 9 9 6 1 2 3 11 9 9 6 1 2 - 3 1 1 9 9 6 1 2 - 3 1 1 2 国内外研究现状 1 2 1 时态x m l 在文献【1 7 】中，a m a g a s a 等人基于x p a t h 数据模型，提出了一个支持“有效 时间”的时态x m l 数据模型。该模型将一个时态x m l 文档表示成一棵带有“时 第1 章概述 态边标记”的有向树。模型中，每条边都带有一个“有效时间戳”标记。另外， 他们还探讨了两种将该数据模型映射成时态x m l 文档的方法。在映射后的时态 x m l 文档中，每个元素都带有一个t i m e ：v a l i d 属性来描述该元素的有效时间。但 是，a m a g a s a 等人没有在该文中具体阐述如何查询和更新时态x m l 。 v a i s m a n 和m e n d e l z o n 等人则在文献 1 8 】中将一个时态x m l 文档表示成一个 有向无环图，通过引入“v e r s i o nn o d e ”概念和为每条边增加一个“时态元素标 记”来支持“有效时间”。在该文中，他们通过扩充x p a t h 语法，增加一些“时 态函数”( b u i l t i nf u n c t i o n s ) 来实现时态查询。另外，他们还讨论并实现了四种 将数据模型映射成时态x m l 的方法。在映射后的时态x m l 文档中，任何一个 属性或元素后面都带有一个有效时间区间字符串。最后，他们还根据映射后时态 x m l 文档的大小，对这四种映射方法进行了比较。 与“给边增加时态标记”相反，s h u o h a oz h a n g 和c u i f i se d y r e s o n 在文献【1 9 中则是为每个结点增加一个“有效时间戳”来支持“有效时间”；在时态查询方 面，他们则通过扩充) ( p a t h 增加一个“有效时间轴”来实现。 与上述几篇文献不同，d y r e s o n 等人则首次研究如何在x m l 中支持“事务 时间”。跟文献 1 9 1 类似，他们在文献【2 0 中通过为每个结点增加一个“事务时 间戳”来支持“事务时间”；另外，他们通过为x p a t h 增加一些“事务时间轴”、 “事务时间结点测试”、“事务时间上下文”等来支持时态查询。但是，文献 1 9 1 和文献 2 0 1 都没有提到如何将所提出的数据模型映射成一个具体的时态x m l 文 档，即他们没有探讨时态x m l 文档中是如何具体表达时态信息的。 g r a n d i 和m n a d r e o l i 在文献【2 1 】中，利用x m ls c h e m a 定义了一个 元 素标记。然后，他们在时态x m l 文档中通过为每个元素增加一个 子元素 来描述该元素的有效时间：另外，他们是利用x s l 技术来过滤时态信息以实现 某些时态查询。 另一方面，w a n g f u s h e n g 认为订l 和x q u e r y 比传统关系数据库和s q l 能 够更好地支持“时态模型”和“时态查询”，因此，他们关于时态x m l 的研究 主要集中于如何利用时态x m l 来实现时态数据库。在文献【1 4 】中，他们在“时 态x m l ”和传统的“回滚数据库”( 支持事务时间) 之间引入“h t a b l e ”概念， 通过这些“h t a b l e ”将传统的“回滚数据库”发布为时态x m l ，并称这些时态 第1 章概述 x m l 文档为“h d o c u m e n t ”。所有的h t a b l e 都符合“t e m p o r a 脚g r o u p e d ”时态 数据模型，“h d o c u m e n t ”和传统的“回滚数据库”之间可以通过“h 。t a b l e ”相 互转换。最后，他们还在该文中介绍了如何使用x q u e r y 对“h d o c u m e n t ”进行 时态查询。基于文献 1 4 】的思想，w a n gf u s h e n g 等人在文献 1 5 中利用时态 x m l 实现了回滚数据库系统a r c h l s 。在该系统中，用户使用x q u e r y 对发布后 的时态x m l ( 即“h d o c u m e n t ”) 进行时态查询。这些x o u e r y 语句接着被翻 译成对相应h t a b l e 的s q l 查询语句，最后，系统将对h t a b l e 的查询结果发布 成时态x m l 返回给用户。另外，a r c h i s 还利用了传统关系数据库的“c l u t e r i n g ” 等技术来大大提高时态查询速度。 另外，w a n gf u s h e n g 等人在文献【2 2 】和文献 2 3 】中分别将文献【1 4 的思想应 用到传统的“历史数据库”( 支持有效时间) 和“双时态数据库”( 支持有效时间 和事务时间) 中，介绍了如何将传统的“历史数据库”和“双时态数据库”发布 成“v - d o c u m e n t ”和“b h d o c u m e n t ”，但没有具体实现。 在“h d o c u m e n t ”、“v - d o c u m e n t ”和“b h d o c u m e n t ”中，w a n gf u s h e n g 是 通过为x m l 文档中的每个元素增加时态属性t s t a r t 、t e n d 和v s t a r t 、v e n d 来分别 描述事务时间和有效时间。 1 2 2 时态x m l 索弓 虽然这几年，时态x m l 的研究逐渐引起了学者们的关注，但是，目前对时 态x m l 的研究主要集中于“数据模型”和“查询机制”，关于时态x m l 索引的 研究较少。 其中，a m a g a s a 等人基于他们在文献【1 7 提出的时态x m l 数据模型，在文 献 2 4 q b 提出了一种用有效路径建立索引的方法，并采用时态关系数据来存放这 些有效路径。但是，由于索引没有反映时态信息，因此，每次都要从头到尾地扫 描时态关系数据表，以找到符合时态约束的有效路径，效率较为低下。m e n d e l z o n c 等人在文献 2 5 中则是通过建立一系列的。屉表对文献 1 8 】中的数据模型建立索 引，虽然该索引使得在进行某些时态查询时( 如时态映射时) ，查询效率非常高， 但却以牺牲较大的存储空间为代价。 第1 章概述 1 2 3 更新x m l 在过去几年，x m l 研究者们主要集中于研究x m l 查询语言的标准制定，较 少关注x m l 的更新语言。因此，x m l 的更新语言还没有形成统一的标准。目 前，x m l 工彳乍组已经开始探讨如何定义x q u e r y 的更新语法标准1 2 6 1 。 目前，较少纯x m l 数据库能够支持x m l 更新，e x c e l o n 系统 2 7 1 是其中一种。 它通过扩充x p a t h 语言，能够支持一些简单的插入和删除语句。另外，i g o r t a t a r i n o v 等人在文献f 2 8 】中探讨了如何扩充x q u e r y 以实现x m l 更新机制。 1 3 本文的研究思路及创新点 从前文对时态x m l 研究现状的论述可知，目前对时态x m l 的研究主要针 对单时态关系下的时态x m l ，而关于“双时态x m l ”的研究较少；在我们所掌 握的材料中，目前国内外还没有关于双时态x m l 数据模型的研究。 另外，在时态关系中，变量“n o w ”和“u c ”是时态关系中两个重要的时 态变量，分别表示有效时问和事务时问的不确定终止点。引入交量有助于对问题 的整体表述与研究，但也会带来新问题，这主要是在具体数据操作( 查询和更新) 过程中，需要讨论变量语义以确定变量取值。虽然学者们在文献【1 7 1 【a 8 ，【2 0 l ， 【2 1 】， 2 2 】， 【2 4 】和【2 5 中都讨论了如何为x m l 查询语言( 如，x p a t h 、x q u e r y ) 增添一些时态查询机制，以实现对时态x m l 的时态查询，但他们都没有在相应 文献中探讨如何支持时态变量的复杂语义。 最后，目前关于时态x m l 的研究主要集中于时态x m l 的“数据模型”和 “查询机制”，较少有文献具体探讨了时态x m l 数据模型的更新机制。 本论文研究工作的主要贡献及创新点可以总结为如下三个方面： ( 1 ) 提出一个双时态x m l 数据模型 我们扩充x p a t h 数据模型，提出了一个双时态x m l 数据模型并给出了形式 化定义。另外，我们讨论并实现了两种将该数据模型映射到一个具体的双时态 x m l 文档的方法。最后，根据实验结果，我们比较了这两种映射方法，并将本 文的双时态x m l 数据模型和d o m 数据模型进行了对比。 第1 章概述 ( 2 ) 实现双时态x m l 的时态查询并支持时态变量的复杂语义 首先，我们在“双时态关系”下，探讨了时态变量在各种情况下的语义，并 给出了时态变量的绑定算法。接着，我们通过自定义了一个x o u e r y 时态函数库 l i b ，实现了对双时态x m l 的时态查询；并且，该时态函数库l i b 提供了实现上 述时态变量绑定算法的机制，以支持时态变量的复杂语义。 ( 3 ) 探讨并实现了双时态x m l 数据模型的更新机制 我们参考了双时态数据库的s n o d g r a s s 表示数据模型中的更新机制，设计了双 时态x m l 数据模型的更新算法。 1 4 论文的组织结构 本文共分为六章，其组织结构如下： 第一章，介绍了时态x m l 的研究背景和意义，总结了时态x m l 的研究现 状和其不足之处，并提出了本文的研究目标。 第二章，首先简要地介绍一些x m l 的基础知识：然后，从时态数据库的角 度介绍一些跟时态x m l 相关的时态背景知识；最后，讨论了什么是x m l 的时 态扩充。 第三章，本文研究工作之一，首先提出了一个双时态x m l 数据模型，并形 式化地定义了该数据模型的三条时态约束；接着，我们探讨并实现了两种模型到 双时态x m l 文档的映射方法；最后，根据实验结果，我们比较了这两种映射方 法，并将本文的双时态x m l 数据模型和d o m 数据模型进行了对比。 第四章，本文研究工作之二，首先在“双时态关系”下，分析了时态变量 “n o w ”和“u c ”的复杂语义，并给出了时态变量“n o w ”和“u c ”的绑定 算法；最后，我们自定义了一个x q u e r y 时态函数库1 i b ，实现了双时态x m l 的 时态查询。 第五章，本文研究工作之三，参考双时态数据库的s n o d g r a s s 表示数据模型 的更新机制，给出了双时态x m l 数据模型的更新算法。 第六章，对本文工作做了一个总结性的介绍，并提出了进一步的研究方向。 1 1 引言 第1 章概述 随着互联网的迅猛发展和普及，人们可以通过计算机和互联网连接，从世界 各地实时地接收和发送大量、最新的信息。h t m l ；是信息技术应用上的一个奇迹， 由于其具有简单特性，加上制定了统一标准，使得w e b 技术从计算机界走向社会， 走向干家万户。到目前为止，我们看到几乎所有w e b 页面都是用h t m l 编写的。 但是，随着w e b 的应用越来越广泛，h t m l 过_ 于简单的弱点也越来越明显， 它已经不能满足用户的需求了，这表现在h t m l 菇j 格式的支持、信息应用的支持 及数据交换等多方面的痼疾。正是由于这些缺点，人们开始转向研究能改进或替 代h t m l 的w e b 页面制作语言。其中最有成效的，并已初步投入使用的技术有多 种，其中，可扩展标记语言x m i 就是一个生动的典型。 v i l 作为i n t e m e t 上一种新的数据发布语言，由w 3 c ( w o r l dw i d ew e b c o n s o r t i u m ) 提出。和r i t m l 类似，x m l 也是一种基于标记的标记语言，但是， x m l 具有许多h t m l 所无法比拟的卓越特性，比如，高效可扩展性、操作型、自 描述性、国际化等。由于x m l 的这些优点，它驱动了i n t e m e t 应用程序编写方式 的动态改变，现在已有越来越多的软件向它提供支持，也许在不久的将来它将会 成为w e b 上下一代“数据交换”和“数据表达”的统一标准。 然而，x m l 3 之档很少是静止的一成不变的，它经常会被修改。虽然已经有了 各种形式存储x m l 3 件的方法【1 l 被提出，但仍然无法保留使用者对文件一连串修 改的痕迹。因此，为了避免重要数据的丢失，“旧版本”必须保存。这就出现“如 何保留对文件一连串的修改痕迹”、“如何查询某一时期版本的内容”等一系列问 题，即“x m l 版本管理”问题。为了解决这个问题，人们提出了各种x m l 版本 方案 撕 。然而，这些方案大部分都是将每次修改后的x m l 3 件另存为一份新的 文件，造成很大的信息冗余和管理上的困难：另外，这些方案也较难支持一些复 杂的“时态查询”，比如，当要查询某个x m l 元素的“演变历史”时，则要一一 搜索并比较所有版本，然后再合并查询结果，效率低下。 第1 章概述 表卜卜1 “t e n ；p o r a l l yu n g r o u p e d h is t o r yo f ：e m p i o y e e s i dn a m es a l a r yt i f i e d e p t n o s t a r te n d 1 0 0 1b o b6 0 0 0 0 e n g i n e e r d 0 11 9 9 5 0 1 0 11 9 9 5 0 5 3 l 1 0 0 1b o b7 0 0 0 0 e n g i n e e r d 0 11 9 9 5 0 6 - 0 11 9 9 5 0 9 3 0 1 0 0 1b o b7 0 0 0 0s re n g i n e e rd 0 21 9 9 5 1 0 0 11 9 9 6 0 1 3 1 1 0 0 1b o b7 0 0 0 0t e c h l e a d e rd 0 21 9 9 6 0 2 0 11 9 9 6 1 2 - 3 1 表卜1 2 “t e t r c 加r a l yg r o u p e d h is t o r yo fe m 口io y e e s 讨n a m es a l a r y t i f i e d e p t n o 1 9 9 5 0 1 0 11 9 9 5 0 1 0 11 9 9 5 0 1 0 1 1 9 9 5 0 1 0 11 9 9 5 。0 1 一0 1 6 0 0 0 0 e n g i n e e r d 0 1 1 9 9 5 一0 5 3 11 9 9 5 0 9 - 3 01 9 9 5 0 9 - 3 0 1 9 9 5 0 6 - 0 11 9 9 5 1 0 - 0 11 9 9 5 1 0 - 0 1 1 0 0 1 b e bs re n g i n e e r 7 0 0 0 01 9 9 6 0 1 3 1d 0 2 1 9 9 6 0 2 0 1 t e e h l e a d e r 1 9 9 6 1 2 3 11 9 9 6 1 2 - 3 1 1 9 9 6 1 2 3 11 9 9 6 1 2 - 3 1 1 9 9 6 1 2 - 3 1 1 2 国内外研究现状 1 2 1 时态x m l 在文献【1 7 】中，a m a g a s a 等人基于x p a t h 数据模型，提出了一个支持“有效 时间”的时态x m l 数据模型。该模型将一个时态x m l 文档表示成一棵带有“时 第1 章概述 1 2 3 更新x m l 在过去几年，x m l 研究者们主要集中于研究x m l 查询语言的标准制定，较 少关注x m l 的更新语言。因此，x m l 的更新语言还没有形成统一的标准。目 前，x m l 工彳乍组已经开始探讨如何定义x q u e r y 的更新语法标准1 2 6 1 。 目前，较少纯x m l 数据库能够支持x m l 更新，e x c e l o n 系统 2 7 1 是其中一种。 它通过扩充x p a t h 语言，能够支持一些简单的插入和删除语句。另外，i g o r t a t a r i n o v 等人在文献f 2 8 】中探讨了如何扩充x q u e r y 以实现x m l 更新机制。 1 3 本文的研究思路及创新点 从前文对时态x m l 研究现状的论述可知，目前对时态x m l 的研究主要针 对单时态关系下的时态x m l ，而关于“双时态x m l ”的研究较少；在我们所掌 握的材料中，目前国内外还没有关于双时态x m l 数据模型的研究。 另外，在时态关系中，变量“n o w ”和“u c ”是时态关系中两个重要的时 态变量，分别表示有效时问和事务时问的不确定终止点。引入交量有助于对问题 的整体表述与研究，但也会带来新问题，这主要是在具体数据操作( 查询和更新) 过程中，需要讨论变量语义以确定变量取值。虽然学者们在文献【1 7 1 【a 8 ，【2 0 l ， 【2 1 】， 2 2 】， 【2 4 】和【2 5 中都讨论了如何为x m l 查询语言( 如，x p a t h 、x q u e r y ) 增添一些时态查询机制，以实现对时态x m l 的时态查询，但他们都没有在相应 文献中探讨如何支持时态变量的复杂语义。 最后，目前关于时态x m l 的研究主要集中于时态x m l 的“数据模型”和 “查询机制”，较少有文献具体探讨了时态x m l 数据模型的更新机制。 本论文研究工作的主要贡献及创新点可以总结为如下三个方面： ( 1 ) 提出一个双时态x m l 数据模型 我们扩充x p a t h 数据模型，提出了一个双时态x m l 数据模型并给出了形式 化定义。另外，我们讨论并实现了两种将该数据模型映射到一个具体的双时态 x m l 文档的方法。最后，根据实验结果，我们比较了这两种映射方法，并将本 文的双时态x m l 数据模型和d o m 数据模型进行了对比。 第1 章概述 ( 2 ) 实现双时态x m l 的时态查询并支持时态变量的复杂语义 首先，我们在“双时态关系”下，探讨了时态变量在各种情况下的语义，并 给出了时态变量的绑定算法。接着，我们通过自定义了一个x o u e r y 时态函数库 l i b ，实现了对双时态x m l 的时态查询；并且，该时态函数库l i b 提供了实现上 述时态变量绑定算法的机制，以支持时态变量的复杂语义。 ( 3 ) 探讨并实现了双时态x m l 数据模型的更新机制 我们参考了双时态数据库的s n o d g r a s s 表示数据模型中的更新机制，设计了双 时态x m l 数据模型的更新算法。 1 4 论文的组织结构 本文共分为六章，其组织结构如下： 第一章，介绍了时态x m l 的研究背景和意义，总结了时态x m l 的研究现 状和其不足之处，并提出了本文的研究目标。 第二章，首先简要地介绍一些x m l 的基础知识：然后，从时态数据库的角 度介绍一些跟时态x m l 相关的时态背景知识；最后，讨论了什么是x m l 的时 态扩充。 第三章，本文研究工作之一，首先提出了一个双时态x m l 数据模型，并形 式化地定义了该数据模型的三条时态约束；接着，我们探讨并实现了两种模型到 双时态x m l 文档的映射方法；最后，根据实验结果，我们比较了这两种映射方 法，并将本文的双时态x m l 数据模型和d o m 数据模型进行了对比。 第四章，本文研究工作之二，首先在“双时态关系”下，分析了时态变量 “n o w ”和“u c ”的复杂语义，并给出了时态变量“n o w ”和“u c ”的绑定 算法；最后，我们自定义了一个x q u e r y 时态函数库1 i b ，实现了双时态x m l 的 时态查询。 第五章，本文研究工作之三，参考双时态数据库的s n o d g r a s s 表示数据模型 的更新机制，给出了双时态x m l 数据模型的更新算法。 第六章，对本文工作做了一个总结性的介绍，并提出了进一步的研究方向。 第2 章相关基础知识 2 1x m l 基础知识 2 1 1 什么是x 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 ，可扩展的标记语言) 是一套定义语义标 记的规则，这些标记将文档分成许多部件并对这些部件加以标识。它不像h t m l 或格式化程序。这些语言定义了一套固定的标记，用来描述一定数目的元素。 x m l 是一种元标记语言，用户可以定义自己需要的标记。这些标记必须根据某 些通用的原理来创建，x m l 标记描述的是文档内容的结构和含义，而不是描述 页面元素的格式化。可用样式单为文档增加格式化信息。文档本身只说明文档包 含什么标记，而不是说明文档看起来是什么样的。 所有的x m l 文档都应该是“良构”的。“良构”的x m l 文档应该是这样的： 所有的构造从语法上都是正确的；只有一个顶层元素，即“根元素”；所有的起 始标记都有与之对应的终止标记，或者使用空元素速记语法；所有的标记都正确 嵌套；每一个元素的所有属性都是不同名的。 另外，我们可以通过d t d 或x m ls c h e m a 来描述x m l 文档中信息结构的 数据模型，并通过它们来验证x m l 文档的有效性。 2 1 2x m l 查询语言 在过去几年，x m l 研究者们提出了多种x m l 查询语言，如q u i l t 2 9 1 ，x q l l 3 0 1 ， x m l - q l l 3 、x p a t h l 3 2 】和x q u e r y 1 1 1 。其中，x p a t h 和x q u e r y 由w 3 c 提出。x p a t h 的主要目的是对一个x m l 文档进行寻址，它在逻辑结构层上将x m l 文档解析 成一个“树状模型”，然后对该模型进行操作。我们将在后面的章节详细介绍该 “树状模型”。 。 第2 章相关基础知识 x p a t h 是x q u e r y 的一个子集，它们有公共的数据模型、公共的正式语义、 公共的函数和操作符以及公共的全文规范。x q u e r y 用于对x m l 数据集进行查 询，, x m l 数据不仅指x m l 文档，还指一切看起来像x m l 的数据，包括关系数 据库中的数据。每个x q u e r y 查询包括一个或多个查询表达式。常用的x q u e r y 表达式有：路径表达式、序列表达式、算术表达式与布尔表达式、f l w o r 表达 式、条件表达式、构造器、定量表达式以及函数调用等【”】。 2 2 时态数据库基本概念 本节将从时态数据库的角度，简单介绍与“时态x m l ”相关的一些时态背 景知识。 2 2 1 时间模型 在自然界中，时间是每时每刻都存在、连续发生且一去不复的，它在时间轴 上是连续存在的。在我们日常生活中，我们常常用日历来表达时间，用年、月、 日、小时、分、秒等不同的时间单位来表示时间的某一点、某段时间或某个时间 长度。例如，“今天是2 0 0 3 年6 月1 日，从凌晨到早上8 点，我已经睡了8 个小 时”，在这段描述中我们使用了不同的时间粒度( 天、小时) 来表达时间的某个 点( 2 0 0 3 年6 月1 日) ，某段时间( 从凌晨到早上8 点) 和一个时间跨度( 8 个 小时) 。这里要指明的是：我们在讲某个时间点，某段时间或某个时间长度总是 有一个“潜台词”基于某个“时间粒度”而言的。 要在计算机中处理时间，首先要解决时间的模型化问题。在时态信息的研究 领域存在三种主要的观点：一种观点主张时间是离散的，时间可以映射成一个关 于“ ”谓词的一个全序结构