（计算机软件与理论专业论文）时态xml文档更新的一致性检查及处理.pdf

时态x m l 文档更新的一。致性检查及处理( 2 0 1 0 )摘要 时态x m l 文档更新的一致性检查及处理 专业：计算机软件与理论专业 硕士生：石磐 指导老师：汤庸教授 汤娜讲师 摘要 随着时态信息处理技术和互联网应用的广泛深入，为了更方便地反映现实世 界的时态数据，实现不同网络环境之间的信息共享和数据交换，时态x m l 的研 究已成为当今的一个研究热点。目前对时态x m l 研究主要集中在时态x m l 索 引、查询优化等方面，对时态x m l 文档的一致性约束研究相对较少。 时态x m l 的一致性作为规范时态v i l 的重要约束条件，如何更有效地保 证时态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 c h e m a 的传统x m l 一致性和时态x m l 致性约束，从这两方面进行一致性增 量检查的研究：一方面是基于s c h e m a 模式验证进行一致性的增量检查；另一方 面，从时态约束性的角度对四种不同的时态x m l 一致性进行增量检查。进而将 时态x m l 更新操作与一致性增量检查和修复相结合，并给出了满足时态x m l 一致性的增量更新算法，进一步对时态x m l 更新查询语句t x p a t h 进行一致性 检查和修复的语义扩展。 最后，本文通过仿真实验，对时态x m l 致性增量检查算法以及满足时态 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 ) 摘要 x m l 一致性的增量更新算法进行实验验证，通过实验比较和对算法性能的分析， 本文所提出的算法具一定的可行性和灵活性。同时保证在更新之前就发现一致性 的冲突并及时修复，避免了更新后的重复检查和修复，提高了时态x m l 更新操 作的执行效率。 关键词：时态x m l ，一致性约束，增量检查，时态x m l 更新，t x p a t h 扩展 i i 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 )a b s t r a c t c h e c k i n ga n df i x i n go fc o n s i s t e n c yw h e nt e m p o r a l x m ld o c u m e n t u p d a t e d m a j o r ：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 ：s h ip a n s u p e r v i s o r ：p r o f e s s o rt a n gy o n g l e c t u r e rt a n gn a a b s t r a c t w i t ht h ed e v e l o p m e n to ft h et e c h n o l o g yo ft e m p o r a li n f o r m a t i o np r o c e s s i n ga n d t h ea p p l i c a t i o no fi n t e m e t ，t h es h a r i n ga n de x c h a n g i n go ft e m p o r a ld a t ah a sb e c o m e m o r ea n dm o r ep o p u l a r i no r d e rt or e f l e c tt e m p o r a ld a t ai nt h er e a lw o r l d c o n v e n i e n t l ya n di m p l e m e n tt h es h a r i n go fi n f o r m a t i o nb e t w e e nd i f f e r e n tn e t w o r k e n v i r o n m e n t s ，t h er e s e a r c ho nt e m p o r a lx m lh a sb e e nb e c o m i n gt h eh i ts p o t t h e r e s e a r c ho nt e m p o r a lx m lf o c u sr n a i l yo nt h et e m p o r a lx m li n d e xa n dq u e r y o p t i m i z a t i o n , b u tl i t t l ei sc o n c e r n e d o nt e m p o r a lx m l c o n s i s t e n c y t e m p o r a lx m lc o n s i s t e n c y a sa l li m p o r t a n tc o n s t r a i n to ft e m p o r a lx m l d o c u m e n t ，h o wt oe n s u r et h a tt e m p o r a lx m lc o n f o r mt ot h et e m p o r a ls e m a n t i c c o n s t r a i n t si nt h er e a lw o r l de f f e c t i v e l yh a sb e c o m et h ep r i n c i p a lp r o b l e m a l t h o u g h s o m er e s e a r c ha c h i e v e m e n t sw e r ea t t a i n e do nt e m p o r a lx m lc o n s i s t e n c y , m o s to f t h e mf o c u so nf u l l - t e x tv a l i d a t i o no ft e m p o r a lx m l t l l e yi g n o r et h ec o n f l i c to f t e m p o r a lx m lc o n s i s t e n c yw h e n t h ed o c u m e n tu p d a t e ds ot h a tt h ec o n s i s t e n c yh a st o b ec h e c k e da n df i x e di t e r a t i v e l y , w h i c hw i l li n f l u e n c et h ee x e c u t i n ge f f i c i e n c yt o s o m ee x t e n t w i t hr e s p e c tt ot h ed i s a d v a n t a g e so fc u r r e n tr e s e a r c ho nt e m p o r a lx m l c o n s i s t e n c y , w el e a mt h er e l a t i v e r e s e a r c ho ni n c r e m e n t a l c h e c k i n g o ft h e c o n v e n t i o n a lx m l c o n s i s t e n c yf o rr e f e r e n c ea n da p p l yt ot h em e t h o do nt h ec h e c k i n g a n df i x i n gw h e nt e m p o r a lx m l u p d a t e d i nt h i sp a p e r , w ep r o p o s eat e m p o r a lx m l 1 1 1 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 ) a b s t r a c t d a t am o d e la tf i r s t o nt h eb a s i so ft h em o d e l ，w ep r o p o s et h ed e f i n i t i o no nt h e c o n s i g e n c yo ft r a d i t i o n a lx m lb a s e ds c h e m aa n dt e m p o r a l x m ld o c u m e n t s e p a r a t e l y t h e n ，w eg i v et h ea l g o r i t h m so fi n c r e m e n t a lc h e c k i n gr e f e r e dt od i f f e r e n t k i n d so ft e m p o r a lx m l c o n s i s t e n c yi ti sd i s c u s s e df r o mt w oa s p e c t s ：o n ec h e c k i n gi s b a s e do ns c h e m av a l i d a t i o n ，t h eo t h e rc h e c k i n gf o c u s e so nt h et e m p o r a lc o n s t r a i n t s n e x t ，w ed i s c u s st h et e m p o r a lx m lu p d a t i n ga l g o r i t h m so nc o n d i t i o nt h a tn o u p d a t i n go p e r a t i o n w o u l dv i o l a t et h e t e m p o r a lc o n s i s t e n c y w ee x p a n dt h e i n c r e m e n t a lc h e c k i n ga n df i x i n go fc o n s i s t e n c yi n t ot h et e m p o r a lx m lu p d a t i n g o p e r a t i o na n de x t e n dt h es e m a n t e m eo ft x p a t hq u e r yl a n g u a g e a tl a s t ，p r e l i m i n a r ye x p e r i m e n t sa n da n a l y s i so fo u ra l o g r i t h m ss h o wt h a tt h e r e s e a r c ho nc h e c k i n ga n df i x i n go fc o n s i s t e n c yw h e nt e m p o r a lx m ld o c u m e n t u p d a t e di sn o to n l yf e a s i b l eb u ta l s of l e x i b l e a tt h es a m et i m e ，o u rm e t h o d sw i l l a s s u r et h a tt h ec o n f l i c to ft e m p o r a lx m l c o n s i s t e n c yc a nb ed e t e c t e db e f o r eu p d a t i n g a n db ef i x e di nt i m e ，w h i c hw i l la v o i dc h e c k i n ga n df i x i n gi t e r a t i v e l ya f t e ru p d a t e d a n di m p r o v et h ee x e c u t i n ge f f i c i e n c yo ft e m p o r a lx m lu p d a t i n go p e r a t i o n k e y w o r d s ：t e m p o r a lx m l ，t e m p o r a lc o n s i s t e n c y , i n c r e m e n t a lc h e c k i n go f c o n s i s t e n c y , u p d a t i n go ft e m p o r a lx m l ，t x p a t he x p a n d i n g i v 本人郑重声明： 论文原创性声明 所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 敝作者虢乃锄 日期：p 1 一年y 曩) 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 日期：铲l 口年r 月i 日 导师签名：f 飞力 日期：叫律舌月 日 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 )第一章引言 第一章引言 近些年来，随着计算机技术和信息技术的飞速发展以及个人计算机和互联网 的进一步普及，人类进入了一个信息膨胀和数据爆炸的时代。为了方便处理人们 现实生活中日益复杂的数据，数据库与信息系统面临着许多新的应用和新的挑 战。时间作为自然界客观存在的物质属性，常常需要反映在实际的信息系统中， 因此对时态信息处理的需求也越来越迫切。时态信息处理已成为许多信息系统与 新一代数据库的核心技术，特别是在数据仓库【7 1 【引、数据挖掘【9 】【10 1 、决策支持系 统【1 、电子商务、电子政务、计算机辅助设计【1 2 】【1 3 】等信息系统中扮演着e j 益重 要的角色。 随着信息共享和数据交换的日益频繁，传统的关系数据库在处理数据时也遇 到了瓶颈：首先数据库技术的实现是基于数据库管理系统之上的，各种商业的数 据库管理系统之间差异较大，且它们所依赖操作系统更是风格迥异，在一定程度 上限制了数据共享和信息交换；另外，数据库技术对现实世界的语义描述能力较 差，复杂的概念模型在异构应用数据交换时，不利于计算机描述现实语义，进行 准确的数据处理和应用。x m l 文档正是为了解决数据库中的这些瓶颈应运而生 的。 1 1 研究背景 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 ，可扩展标记语言) ，于1 9 9 8 年2 月由 w o r l dw i d ew e bc o n s o r t i u m ( w 3 c ) 工作组提出，它与h t m l 类似，也是一种 基于标记的标记语言，继承了s g m l 语言的很多特性，但使用了较为简单的实 现技术。x m l 具有高效可扩展性，自描述性，国际化性【4 】等，特别是在数据传 送方面，x m l 使数据的传送获得真正的独立性、跨平台性【3 】。正如w 3 c 工作组 描述的那样：“x m l 是s g m l 的子集，其目标是允许普通的s g m l 在w e b 上以 目前h t m l 的方式被服务和处理。它是易于实现，且可在s g m l 和h t m l 之间 互相操作d , 2 】。”另外，由于其数据表示形式灵活，使其更容易地在异构环境下 进行数据的传输与交换。尤其是在互联网领域，它将成为异构环境下新一代w e b 应用的通用数据语言和转换协议。x m l 作为数据访问领域的最新技术，x m l 数 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 ) 第章引言 据管理成为当前信息系统研究热点f 5 】f 6 】。 时态信息处理技术伴随着数据库技术的产生与发展，已成为新一代数据库技 术与信息技术的重要领域。时态数据库领域的权威学者a t a n s e l 等人在1 9 9 3 年共 同主编的 t e m p o r a ld a t a b a s e s ：t h e o r y , d e s i g n ，a n di m p l e m e n t a t i o n ) ) 【1 4 】中收集了 此前时态数据库几乎所有的重要研究成果。关于时态信息技术的起源与发展我们 大致可分成以下三个重要时期：开创性( 1 9 8 2 年以前) 、理论与模型探索阶段 ( 1 9 8 3 1 9 9 3 年) 、应用与发展阶段( 1 9 9 4 年以来) 1 5 1 。 国内外在基于x m l 的时态扩展的研究都比较活跃，包括建立时态x m l 的数 据模型【1 6 】，时态信息在x m l 文档中的表示【1 7 】【博1 ，以及时态x m l 的存储1 8 1 【19 1 等方 面都进行了深入的研究。中山大学协同软件技术实验室时态数据库研究小组从 2 0 0 4 年开始对时态x m l 进行研究，在x m l 时态表示、时态x m l 数据模型、时态 x m l 查询、时态索引、时态更新等方面都取得了比较多的研究成果。本文在这 些研究成果的基础上，对时态x m l 数据模型，时态信息在x m l 文档中表示及时 态l 一致性约束等更进一步研究，扩展时态x m l 更新操作，对时态x m l 更新 进行了一致性约束的检查和修复，从而保证了时态x m l 更新操作满足时态一致 性的约束。 1 2 研究的出发点及意义 伴随着人们对时态信息处理需求的日益增加，以及互联网上异构数据交换的 日益频繁，结合时态数据库与x m l 语言的优点，研究时态x m l 具有理论和现 实的意义。 一方面，x m l 作为反映现实世界的数据表示，文档的内容与结构随着时间 的变化而变化。虽然目前已经提出了很多存储x m l 文件的方法和形式【2 0 l ，但仍 然无法有效存储对文件一连串修改痕迹，对于x m l 来说，其面临的版本管理和 实时的查询，驱动其引入“时态”的相关技术。 另一方面，随着时态信息处理技术研究的不断深入，出现了大量关于在传统 关系数据库中支持“时态信息，的研究【2 l 】，例如文献列举出多种不同的支持“时 态信息”解决方案。针对传统关系模型灵活性较差，c l i f f o r d 等人在文献【2 3 l 中证明 了像x m l 这种支持“非结构化”数据的格式，可以很好的支持 t e m p o r a l l yg r o u p e d ” 2 时态x m l 文档更新的致性检查及处理( 2 0 1 0 )第一4 章引言 数据模型；另外和s q l 不同的是，x m l 的查询语言x q u e r y 2 4 】具有“图灵完备” 和自身可扩展( n a t i v e l ye x t e n s i b l e ) 的特性【2 5 2 6 1 ，这些都为x m l 的时态扩展提 供了理论的依据。 本文正是从这两方面出发，结合x m l 和时态信息处理近些年的研究成果， 对x m l 进行时态的扩展，提出时态x m l 数据模型，并在此模型的基础上研究 了时态一致性的约束。但是作为时态x m l 数据模型的重要约束条件，如何更有 效地保证时态x m l 文档满足现实世界的时态语义约束成为时态x m l 一致性研 究的一个难点，特别是当时态x m l 文档不断进行更新时，如何保证每次更新操 作不会带来时态x m l 一致性的冲突，如何更高效地进行时态x m l 文档一致性 约束的检查和修复，这些都成为时态x m l 一致性研究必然要解决的问题。 针对现今时态x m l 一致性研究的不足，本文改进时态x m l 文档更新一致 性检查算法，提出增量更新以及冲突修复的算法，避免传统更新的时态x m l 全 文检查和重复检查，不仅提高了时态x m l 更新一致性检查的效率，也改善了一 致性冲突修复的正确率。 除了在理论方面，时态x m l 一致性的研究对于完善x m l 和推动时态信息 技术的发展都具有重要的意义。在实际应用领域，时态x m l 一致性也具有广阔 的应用范围，诸如电子政务中处理具有时效规范性的政策信息和与时间约束相关 的统计数据等，工作流中各种异构时态数据的传输与校验，以及数据仓库中进行 时态数据的挖掘，在满足一定约束条件下进行实时的决策支持等。 1 3国内外研究现状 1 3 1x m l 的时态扩展 时态信息在x m l 上进行扩展一般有两种扩展方法，属性扩展法和元素扩展 法。c l i f f o r d 对时态数据模型进行分类：t e m p o r a l l yt m g r o u p e d 和t e m p o r a l l y g r o u p e d t 2 3 1 ，从这里最早提出了不同的x m l 时态扩展方法。在属性扩展法中， f u s h e n gw a n g 将t e m p o r a l l yg r o u p e d 模型引入x m l ，提出了x b i t 数据模型2 7 1 ； 在元素扩展法中，b e l as t a n t i c 等人利用f e r n a n d e z t 2 8 j 等人的方法进行元素扩展， 并提出d i r e c t 数据模型2 9 。尽管x m l 的时态信息扩展模型提出很多，且很多模 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 )第一章引言 型都涉及了定性分析，但在性能上的做定量分析对比的还比较少。 1 3 2 时态x m l 数据模型 v a i s m a n 等人提出了“版本结点”的概念，并为每条边增加一个“时态元素标 签”来记录有效时间，将时态x m l 模型转化为有向无环图【3 0 1 。除此之外，他们还 研究了在映射后的时态x m l 文档中，在任何一个属性或元素上添加一个有效时 间区间字符串，简化了时态x m l 文档的表示。在时态查询上，扩充x p a t h 语言， 增加一些“时态函数”( b u i l t i nf u n c t i o n s ) 来实现时态查询1 3 0 1 。 s z h a n g 和c d y r e s o n 对时态x m l 文档的每个结点增加“有效时间戳”来支 持“有效时间”；在时态信息查询上则是通过扩展x p a t h 语句增加一个“有效时间 轴来实现【3 l 】。 t o s h i y u k ia m a g a s a 等人通过对x p a t h 数据模型进行扩展，增加“有效时间”的 时态标签，建立时态x m l 数据模型，该数据模型将一个时态x m l 文档表示成一 棵带有“时态边标记( 有效时间戳) ”的有向树【3 2 1 。在对该数据模型映射成时态 x m l 文档方面，他们采用了f u l li m p l e m e n t a t i o n 和s i m p l i f i e di m p l e m e n t a t i o n 两种 方法进行映射。在映射后的时态x m l 文档中，每个元素都带有一个“t i m e ：v a l i d 属性来描述该元素的有效时剐3 2 1 。 另外，他们还讨论了如何在时态关系数据库中实现该数据模型，并进一步将 此模型转化为一个有向无环图，给出了简单的查询操作，却没有对更新方面进行 细致的讨论【3 3 1 。 1 3 3 时态x m l 一致性研究 对于传统的x m l 文档的一致性研究，很多学者提出了增量验证x m l 文档 一致性的模型和方法。其中k a n e 等人提出了x m l 文档约束规则的模型，对x m l 更新操作提出了一种约束检查机制，保证每次对x m l 文档的更新都满足相应的 一致性约束1 3 8 】，这种方法主要是通过重写更新x m l 的查询语句，实现增量的检 查。c h i e n 等人提出利用s c h e m a 模式来记录更新x m l 文档的版本信息，对每次 版本的改动进行一致性的校验【3 9 】，这种方法由于要维护s c h e m a 文件，对于致 性的校验开销较大。 4 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 )第一章引言 以上大量学者对一致性的研究基本是基于传统的x m l 文档，据我们掌握的 资料，目前国内外对于时态x m l 一致性的研究还处于一个崭新的阶段。其中 f l a v i or i z z o l o 和a a v a i s m a n 在文献【4 0 】中讨论到了有效时间的时态约束问题， 并给出了其定义下时态冲突的解决算法。m a r c e l ac a m p o 在这个的基础之上，在 文献】中进一步探讨将时态不一致问题的解决方法，并给出各类时态约束类别 之间的联系。虽然这些研究成果给出了时态x m l 一致性冲突的解决方法，但都 是基于全文档的检查，未能进行增量的验证和修复，会导致更新的一致性冲突以 至于修复不完全或者反复检查，影响更新操作的实现效率。 1 3 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 文档更新的研究，“e x c e l o nx m lr e p o s i t o r y ”是其中较少支持x m l 更新的一种系统，它主要是通过扩展x p a t h 语言来支持一些简单的插入和删除操 作【3 4 】。i g o rt a t a r i n o v 和z a c h a r yg i v e s 等人是通过扩展x q u e r y 语言来讨论x m l 的 更新机制，他们还讨论在关系数据库上进行x m l 更新的问趔3 5 1 。k u ny u e 等人在 文献m 中提出将关系数据库中的完整性约束以函数依赖的规则映射到相应的 x m l 数据模型，用来保证更新操作的数据完整性约束。 与传统x m l 文档更新研究不同，时态x m l 文档的更新涉及时态元素的更新， 很难通过传统的关系数据库来实现。另外，由于时态x m l 文档的查询都是基于 时态x m l 索引进行的，时态x m l 文档的更新操作需要保证索引文件与时态x m l 同步更新。f l a v i or i z z o l o 和a a v a i s m a n 在文献【4 0 】中通过扩展的t x p a t h 更新语句 来支持时态元素的更新，并通过更新时态x m l 索引文件，将更新后的索引文件 映射到时态x m l 文档上来实现的。但这种方法仍然会面临时态x m l 更新时一致 性约束冲突的问题。 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 )第一章引言 1 4 研究思路与本文贡献 针对以上关于时态x m l 的最新研究成果，本文分别从传统x m l 文档和时态 数据库两方面出发，在x m l 文档上扩展时态属性，给出时态x m l 数据模型，提 出一种易于表达时态x m l 一致性的模型映射，在此模型映射的基础上，对时态 x m l 文档进行一致性的检查。 考虑到当前研究成果 4 0 , 4 1 】主要集中在时态x m l 一致性的全文检查，忽略了 更新所带来的新的一致性冲突。因此，本文借鉴了文献f 3 8 1 中所提出的增量检查 传统x m l 一致性约束的思想，将其运用到时态x m l 文档更新的一致性检查和处 理上，分别从两方面进行了时态x m l 一致性的增量检查：方面从传统x m l 文 档约束出发，通过增量的验证s c h e m a 模式文档，发现x m l 文档的一致性冲突； 另一方面从时态x m l 一致性出发，分别对四种一致性冲突进行增量的检查和修 复，并扩展重写了时态x m l 更新查询语句t x p a t h ，更新操作与增量的一致性检 查和修复相结合，这样可以在更新之前就发现一致性的冲突并及时修复，避免了 更新后的全文检查和反复校验更新。最后通过仿真实验来分析和验证以上的研究 思路。 因此，本文研究工作的主要贡献和创新点可以概括如下： ( 1 ) 讨论了一种x m l 时态扩展的数据模型，并给出了一种易于表达时态 ) a l 一致性的模型映射，详细探讨了四种时态x m l 一致性约束； ( 2 ) 讨论了时态x m l 一致性增量检查的算法，分别从传统x m l 一致性增量 检查和四种时态x m l 一致性增量检查出发，设计了时态l 一致性检测引擎的 框架流程以及各个一致性增量检查的实现算法； ( 3 ) 讨论了时态x m i 一致性冲突的增量修复算法，结合基于索引的增量更 新操作，对时态x m l 的更新操作进行一致性增量检查的扩展，并给出满足时态 x m l 一致性的更新算法，最后还扩展了时态x m l 更新查询语句t x p a t h ，使得更 新语句具备时态x m l 一致性增量检查和修复的功能； ( 4 ) 通过较大数据量的仿真实验，分析以上时态x m l 模型的性能，验证时 态) ( m l 一致性增量检查及修复的算法的性能，并与当今的满足时态一致性的时 态x m l 更新算法进行比较，从相对宽泛角度说明了基于时态x m l 文档更新的一 致性检查和处理的可行性和灵活性。 6 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 )第一章引言 1 5 论文组织结构 本文共分七章，论文组织结构如下： 第一章首先引入时态x m l 的研究背景和研究意义，然后介绍了时态x m l 相关领域的国内外研究现状，又介绍了本文的研究思路和创新点等。 第二章介绍了本文研究需要的相关理论与技术基础，包括时态数据库的基础 知识和) ( 】l 相关的基础知识。 第三章给出了x m l 数据模型和一个时态x m l 数据模型，并探讨和实现了 四种将时态x m l 数据模型映射到一个具体的x m l 文档的映射方案。 第四章给出了x m l 数据模型一致性和时态x m l 数据模型一致性的定义， 给出了时态x m l 一致性检查的算法，并设计出时态x m l 一致性检测引擎的框 架流程。 第五章给出了时态x m l 一致性冲突的修复算法，以及满足时态x m l 一致 性的更新操作的算法，包括结点插入、删除算法以及对t x p a t h 语句进行时态 x m l 一致性检查修复的扩展。 第六章通过大量的仿真实验分析时态x m l 一致性检查与修复的性能，以及 验证满足时态x m l 一致性的更新操作的可行性和灵活性。 第七章对前面的工作进行了总结，并提出了下一步研究工作的展望。 7 时态x m l 文档更新的，致性检查及处理( 2 0 1 0 ) 第二章相关背景知识 第二章相关理论与技术基础 2 1时态数据库基础知识 自2 0 世纪8 0 年代初时态数据库技术产生以来，经过2 0 多年的研究和实践， 时态数据库在基础理论、数据模型、数据库语言、应用技术等方面都取得了丰盛 的成果，已经成为数据库与信息系统中一个重要的、充满活力的学科方向b 】。 我国学者唐常杰也对时态数据库技术的发展进行了研究和总结 3 6 , 3 7 】。下面，本文 就涉及到的相关的时态数据库概念进行介绍。 2 1 1 基本术语 以下是基本的时态术语： ( 1 ) 时间粒度：时间在时间轴上是客观存在，单向连续的，但从计算机的 数字化特点来说，要对时态信息进行研究，需要先对时间进行离散化处理，将时 间表示为离散的时间点，其中最小的基本单位就是时间粒度。例如，以小时作为 时间粒度，则表示时间时就只能以小时作为最小的单位。 ( 2 ) 时间点：又称为时刻，是建立在时间粒度之上，可以看成是某个离散 的时间点。例如2 0 1 0 年7 月1 日，就是一个时间点。 ( 3 ) 时间区间：用于描述某一段连续的时间段，它有固定的起始时间点和 终止时间点。例如，从2 0 1 0 年7 月1 日到2 0 1 0 年7 月1 9 日，这就是一个时间 区间。 ( 4 ) 时间跨度：指时间区间上持续的一段时间，表示时间的长度。例如对 于2 0 1 0 年7 月1 日到2 0 1 0 年7 月1 9 日，时间跨度就是1 9 天了( 其中以“天” 作为时间粒度) 。 2 1 2 三种基本时间 ( 1 ) 用户自定义时间【1 5 】 指用户根据自己的需要或理解定义的时间。这种时间的属性值一般是时间 8 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 )第一章相关背景知识 点，用户本身会解释他所给出的时间信息，数据库系统不需要解释该数据的含义， 只需将此时间域等同于其他般的属性域来理解，对它的操作和对普通字符串的 操作几乎没有什么差别。例如，“生日”本来不是一种标准数据类型，但是当用户 根据自己的需要定义了一个“生日”类型的属性，一个记录相对应的该属性的值为 “1 9 8 5 0 9 2 3 ”，那么这个时间就是一种用户自定义时间。系统不会对它有特别的 处理，它的提供和更新都是由用户自己完成的。 用户在一般传统数据库中都可以使用自定义数据类型，即在原来数据类型的 基础上定义自己的数据类型。在数据表建立或结构被修改时，这些用户自定义的 数据类型和其它标准数据类型一样被用户使用。同样，用户也可以在时态数据库 中使用自定义数据类型。时态数据库不对用户自定义时间做任何处理，不需要专 门的语言支持。用户自定义时间值是完全依赖应用的，由用户和系统以常规方式 存取。 ( 2 ) 有效时间 有效时间指一个对象( 事件) 在现实世界中发生并保持的那段时间，即该对 象在现实世界中为真的时间。既可以反映过去和现在的时间，也可以反映将来的 时间，记录了现实模型随时间而变化的状态信息。【1 5 】 有效时间可以是单一的时间点、单一的时间区间，或者是时间点的集合、时 间区间的有限集合，也可以是整个时间域。和用户自定义时间不同，当查询语句 被检测到有时态语义的时候，有效时间是由数据库系统解释的。有效时间的提供 和更新都是由用户来完成的。【1 5 】 有效时间对事物的描述比较直观、容易理解。下表是一个有效时间的例子。 表2 - 1 一个包含有效时间的历史关系 姓名身份 起始有效时间终止有效时间 石小硕高中生 2 0 0 1 9 12 0 0 4 7 1 石小硕大学生2 0 0 4 9 12 0 0 8 7 1 石小硕研究生2 0 0 8 9 1n o w ( 3 ) 事务时间 9 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 )第- 章榭关背景知识 记录了对数据库修改或更新的各种操作历史，对应于现有事务或现有数据库 状态变迁的历史。事务时间是应用独立的，用户不可以修改事务时间。数据库中 的数据录入数据库的时间、修改和删除的时间是由系统时钟决定的，而修改后的 数据也是不能够改变的。1 1 5 1 事务时间可能与有效时间相同，但在大多数应用中两者并不一致。例如，在 2 0 0 4 年7 月1 9 日，某大学通知学生石小硕已经被录取，9 月1 号去报到，同时 该大学将石小硕录入新生数据库。那么7 月1 9 日是新的学生记录的事务时间， 而9 月1 日是新的学生记录的有效时间起点。在这个例子中，事务时间是早于有 效时间的。如果石小硕2 0 0 3 年已入学，但该大学2 0 0 4 年才将石小硕录入数据库， 则事务时间就会晚于有效时间。 事务时间不能晚于现在时间，因为它反映着数据库实际操作的时间。与有效 时间不同，事务时间不能指未来。1 1 5 ( 4 ) 3 种时间数据的应用 在目前的时态数据库中，3 种基本时间都得到了广泛的应用。一个时态关系 是一个历史状态的序列，每个历史状态是能够表示有效时间的完整的历史关系。 每个事务的提交将导致一个新的历史状态的产生，因此时态关系是不断增加的。 表2 - 2 是一个三种时间的综合应用示例。 t 5 1 表2 2 三种时间的综合应用示例 姓名 出生年月工资部门 2 0 0 9 0 ，9 4 】数学系 9 0 ，9 2 】 张三 1 9 7 0 0 1 0 8 3 6 0 9 5 ，9 8 】 物理系 9 3 ，9 8 】 5 5 0 9 9 ，n o w 软件所 9 9 ，n o w 1 9 0 1 8 9 ，9 1 】物理系 8 9 ，9 5 】 2 5 0 9 2 ，9 5 】软件所 9 6 ，9 9 】 李四 1 9 6 8 0 8 1 8 4 0 0 9 6 ，9 9 】 计算机系 6 0 0 2 0 0 0 ，n o w 【2 0 0 0 ，n o w 在表2 2 中，每一个元组的工资属性值都是由两个部分构成的，前一个部分 1 0 时态x m l 文档更新的。致性检查及处理( 2 0 1 0 )第二章相关背景知识 是工资的值，后一部分是工资的有效时间，例如张三的工资中的2 0 0 元对应的 【9 0 ，9 4 ，即张三工资为2 0 0 元的时间有效值，也就是我们所说的有效时间。出生 年月中的时间1 9 7 0 0 1 0 8 就是数据库的设计者或用户定义的时间，即用户自定 义时间。在这个图表中没能清楚的表明出事务时间，但是至少该图表建立的时间 就是一个事务时间。 2 1 3 时态数据库 按表示时态信息的方式，可以将数据库分成基本的4 种类型：快照数据库 ( s n a p s h o td a t a b a s e ) 、回滚数据库( r o l l b a c kd a t a b a s e ) 、历史数据库( h i s t o r i c a l d a t a b a s e ) 和双时态数据库( b i t e m p o r a ld a t a b a s e ) 。通常将后3 种称为时态数据 库( t e m p o r a ld a t a b a s e ) 1 1 0 1 。 ( 1 ) 快照数据库：旧 快照数据库是指以特定时刻的瞬间快照来建立模型，考虑现实世界。一般由 静态的二维关系表组成：属性维与元组维。快照数据库无法表示属性与时间的关 系，只能进行当前数据库状态的增、删、查、改等操作。从时态数据库的观点来 看，快照数据库不区分事务时间和有效时间。 ( 2 ) 回滚数据库：【1 5 】 回滚数据库( r o l l b a c kd a t a b a s e ) 支持事务时间，它按事务时间进行编址， 保存了过去每次事务提交、状态演变之前的状态。 回滚数据库由三维的回滚关系组成，在属性维和元组维的基础上增加了事务 时间维，因此可看作是一个按时间编址的瞬象的序列。其中每一个时间点都对应 于一个二维的快照数据库。 每个事务都产生一个新的静态关系保留在数据库中，即使数据库毫无变迁， 回滚数据库也保持了数据变迁的历史，这样就会产生很多冗余。 回滚数据库记录了数据库事务变化历史。任何一个更新语句的执行将产生一 个新的数据库状态，新状态不会覆盖旧的状态，因此没有数据会被物理删除。通 过将一个元组的事务结束时间设为执行语句的当前时间，从而实现元组在语义上 的“删除”。事务时间区间可以看成是该元组在快照数据库中存在的历史。 ( 3 ) 历史数据库：f 1 5 】 时态x m l 文档更新的一致性检查及处理( 2 0 1 0 ) 第一章棚关背景知识 记录事实的有效时间的数据库称为历史数据库，它由“历史关系”组成，每一 个元组记录了数据的一个“历史”的状态，可以是过去、现在或将来，存储和管理 客观对象在有效时间点的事件或状态变化的经历。 真实世界中事实的每一个变化将产生一个新的状态。历史数据库支持有效时 间，数据冗余度小，结构相对简单。但是它不支持事务时间，不可以像回滚数据 库一样对以前的某一个状态进行查询。 ( 4 ) 双时态数据库：f 1 5 j 双时态数据库既支持事务时间又支持有效时间，集成了前3 种类型数据库的 功能特性，储存了数据库和现实世界两者发展的历史。这种数据库才是真正的对 数据时态属性支持的数据库。但是应当值得注意的是，双时态数据库是以牺牲大 容量的存储空间为代价的，对双时态数据库的储存进行优化是时态数据库研究的 一个重要工作。 2 2x m l 基础知识 2 2 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 ，可扩展标记语言) ，是一种可由用户自行 创建标记的标记语言。它由w 3 c ( w r o r l dw i d ew e bc o n s o r t i u m ，万维网协会) 的工作组创建，用以克服h t m l 的局限。这个工作组这样描述该语【1 ，2 】：“x m l 是s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记语言) 的子集， 其目标是允许普通的s g m l 在w e b 上以目前h t m l 的方式被服务、接收和处 理。” x