（计算机软件与理论专业论文）semantictree—时态xml索引方案.pdf

山东大学硕士学位论文 摘要 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 ( 可扩展标识语言) 由于具有简单、 可扩展、互操作性强，开放性强等特点，正迅速成为一种与技术无关的数据交换 的标准和传输格式。鉴于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 i 路径索引方法， 其中心思想是对路径索引树中的各个节点进行编码，存储在结点表中能够快速判 断x m l 文档树中节点间的祖先后裔关系和双亲孩子关系，能有效的支持x p a t h 路径表达式查询和关键字搜索，同时建立语义树，能够快速的构成语义的相对关 系，并同语义结点聚合，划分时间段，形成语义时间划分表，快速查找到某时间 区间对应的节点集合。同时本文给出了索引的建立算法，以及更新，删除和查询 算法。最后我们通过实验证实了创建的索引是可行的和有效的。 关键词：时态x m l ，前序编码，语义树 山东大学硕士学位论文 a b s t r a c t t h ex m l ，f u l ln a m ei se x t e n s i b l em a r k u pl a n g u a g e , 谢t 1 1t h ea d v a n t a g e so f s i m p l i c i t y ，s c a l a b i l i t y ，i n t e r o p e r a b i l i t y ，a n ds t r o n go p e n i n gc h a r a c t e r i s t i c s ，i sf a s t b e c o m i n gs t a n d a r d sf o rd a t ae x c h a n g ea n dt r a n s m i s s i o nf o r m a th a v i n gn o t h i n gt od o 、历也t h et e c h n i q u e s i nv i e wo ft h ew i d er a n g eo fa p p l i c a t i o n si nm a n ya r e a s m a n y o ft h ex m lr e s e a r c h e sa r eo nt h ef o r e f r o n ta n dh o tt o p i c s f o re x a m p l e ，i nt h ef i e l d o fd a t a b a s e ，i nas e n s et h eu s eo fx m la sad a t a b a s ec a nd e n o t en e s t e dd a t an a t u r a j l y a n dh a v es t r o n g e re x p r e s s i o nt h a nt h er e l a t i o n a ld a t a b a s e h o w e v e r , t h ex m l i n d e x e sh a v eal o to fi m p e r f e c tp l a c e s ，t oq u e r yt h ex m ld o c u m e n t sd i r e c t l yt h a n t h er e l a t i o n a ld a t a b a s ei sm u c hf a rf r o mu po ne f f i c i e n c y a c a d e m i cr e s e a r c ho nt h e x m li n d e xh a sb e e nal o n gt i m e ，e v e nt h o u g ht h e r ea r es o m es u c c e s s e s ，al o to f p l a c e sn e e dt oi m p r o v e i no r d e rt od e a lw i t ht h et e n s ei n f o r m a t i o nw h i c hp l a ya ni m p o r t a n tr o l ei n e - c o r n l t l e r c ea n de - g o v e r n m e n ti n c r e a s i n ga r e a s ，t h et e n s ex m lg e n e r a t e s ，a n d b e c o m e sa ne m e r g i n gr e s e a r c hb r a n c ho fx m l t e c h n o l o g y c o m p a r e d 、矶mt h et e n s e r e l a t i o n a ld a t a b a s e ，t h et e n s ex m lh a st h ed a t am o d e lw h i c hi sm o r ei n t u i t i v et o e x p r e s st e m p o r a li n f o r m a t i o n o t h e r w i s e ，t h em a i na p p l i c a t i o no fx m li s d a t a s t o r a g ei nc u r r e n t t oi m p r o v ei n q u i r ye f f i c i e n c y0 1 1t h et e m p o r a lx m ld o c u m e n t s ， t h et r a d i t i o n a lx m li n d e x i n gi sn o tv e r ye f f e c t i v e ，i tc a nb es a i dt h a tt h es t a t es t i l l l a c kan u m b e ro fx m l s p e c i f i ci n d e x i n gt e c h n o l o g i e s ，a n dr e s e a r c h e si nt h i sa r e ai s c u r r e n t l yb l a n k i nt h i sp a p e r ，t h ed a t am o d e lo ft e m p o r a lx m li ss t u d i e d , b a s e do nw h i c ht h e i n d e x i n gm o d e li sc r e a t e d t h r o u g ht h ec r e a t i o no fi n d e x , aq u e r yb a s e do nt i m ei s o p t i m i z e d t h ex m lm o d e la n dt e m p o r a lx m l m o d e la r ei n t r o d u c e di nt h i sp a p e r f i r s t l y ；f o l l o w e db yd i s c u s s i o no ft h eg e n e r a ls i t u a t i o no fr e s e a r c ha n da p p l i c a t i o no f t h ex m l c o d i n ga n da n a l y s i so ft h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ec u r r e n t s e v e r a lp o p u l a rc o d i n gm e t h o d s ，s i m u l t a n e o u s l y ，t h et h o u g h to fr e s e r v ep r e o r d e r i i 山东大学硕士学位论文 c o d i n gb a s e do np r e o r d e rc o d i n gi sb r o u g h tf o r w a r d ；a n dt h e na l li m p r o v e dm e t h o d o ft h ex m i n d e xp a t hi sp r o m o t e d ，t h r o u g hc o m b i n i n gn o d et a b l e ，t h es e m a n t i ct r e e ， a n dt h es e m a n t i ct i m ed i v i s i o nt a b l et o g e t h e r , t h ec e n t r a li d e ao fw h i c hi st oe n c o d e e a c hn o d eo fi n d e xt r e eo ft h ep a t h ，s t o r e di nt h en o d et a b l ec a ne x p r e s sx m l d o c u m e n tt r e et od e t e r m i n ei n t e r - n o d ea n c e s t o r d e s c e n d a n tr e l a t i o n s h i pa n dp a r e n t c h i l dr e l a t i o n s h i p ，c a ne f f e c t i v e l ys u p p o r tt h ep a t he x p r e s s i o nx p a t hq u e r ya n d k e y w o r ds e a r c h ，a tt h es a m et i m es e m a n t i ct r e ei ss e tu pt oc o n s t i t u t eas e m a n t i c r e l a t i o n s h i pb e t w e e nt h er e l a t i v ea n dt h es a m es e m a n t i cn o d ep o i n to fa g g r e g a t i o n ，t o d i v i d et i m ep e r i o d ，t of o r mas e m a n t i cf o r mo ft i m ed i v i s i o n ，a n df a s ts e a r c ht oa c e r t a i nt i m ei n t e r v a lc o r r e s p o n d st ot h en o d es e t ；i ns u c c e s s i o n ，t h es e t t i n gi n d e x i n g a r i t h m e t i c ，a sw e l la su p d a t i n g ，d e l e t i n ga n dq u e r y i n ga r i t h m e t i ca r ep r e s e n t e d ； f i n a l l y , t h ec r e a t i o no ft h ei n d e xi sc o n f i r m e df e a s i b l ea n de f f e c t i v ee x p e r i m e n t a l l y k e y w o r d s ：t e m p o r a lx m l ，r e s e r v ep r e o r d e rc o d i n g ，s e m a n t i ct r e e i i i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均己在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 墅缁 e l 期： 丝堡：生： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 墅型 导师签名： 山东大学硕士学位论文 1 1 课题研究背景 第一章绪论 随着互联网的迅猛发展和普及，人们可以通过计算机与互联网联接，从世 界各地实时的接收和发送大量、最新的信息，但在信息交换的过程中存在着一 个突出的问题，就是多种多样的数据格式。给信息的有效使用带来了障碍。所 以在信息时代，如何以最便捷、最可靠、最有效的方式获取所需的信息是一个 很大的困扰。人们期待着能够找到一种可以描述任何逻辑关系的数据格式来统 一电子数据的存储，从而不再因为数据格式的不统一而苦恼和困惑。目前，能 够担当此任的就是x m l 1 2 1 ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展符号化语言) 。 x m l 是由w 3 c ( w o r l d w i d ew e bc o n s o r t i u m ) 的团体提出并构想出来的。 x m l 与t r r m l ( 超文本标记语言) 类似，也是一种基于标记的标记语言，但却有 着h t m l 所无法比拟的卓越的性能表现1 3 , 4 】： l ，开放性x m l 技术根据标准规范，允许数据在任何平台上用读取和处理， 通过开放性数据标准进行通信，不必使用专用通信协议。 2 简单性x m l 为程序员和文档作者提供了一个友好的环境。x v l l 的严 格定义和规则集使人类和机器都能更容易地阅读文档。x m l 文档语法包含一 个非常小的规则集，使开发者能立刻开始工作。x l v l l 文档建立在基本嵌套结 构的一个核心集的基础之上。当一层又一层的细节增加使结构变得越来越复 杂时，作者或开发者为内部结构的复杂化付出的努力将是很少的。这些基本 结构可以用来代表复杂的信息集合，而不需要改变结构自身。x m l 的语法分 析器也非常容易创建。 3 高效可扩展x m l 在两个意义上是可扩展的。首先，它允许开发者创建 他们自己的d t d ，有效地创建可被用于多种应用的“可扩展的”标志集。其 次，使用几个附加的标准，可以对x m l 进行扩展，这些附加标准可以向核心 的x m l 功能集增加样式、链接和参照的能力。作为一个核心标准，x m l 为 可能产生的其他标准提供了一个坚实的基础。 4 操作性x m l 可以在多种平台上使用并且文档的结构是相容的，所以 山东大学硕士学位论文 分析文档的解析器可以很容易地建立。 5 自描述性数据内容和表示分离，自定义标签使得数据本身就具有意义， x ml 的数据组织方式也是的信息容易阅读和理解。 6 国际化新的编码标准支持世界上所有以主要语言编写的混合文本，从而 使得x m 文档能在不同计算机系统乃至跨国界和不同文化疆域内交换信息。 正是由于具有以上的优点，x m l 作为数据访问领域的最新技术，正迅速成 为一种与技术无关的数据交换的标准和传输格式，为在自定义的文档格式中构 造数据类型定义了一种标准格式，使数据独立与处理它的程序和平台。x m l 可 以作为一个数据交换的标准，其原因就在于x m l 能够应用于各种领域的原因， x m l 具有到目前为止其他方法所不具备的数据描述特点，控制信息不是采用应 用软件的独有形式，而是采用谁都可以看得懂的标记形式来表现。 x m l 的目的就是便于软件开发人员和内容创作者在网页上组织信息。它不 仅能满足不断增长的网络应用需求，同时能够确保在通过网络进行交互合作时， 具有良好的可靠性与可操作性。x m l 是一种自我描述的定义语言，即使用者可 以定义标记来描述文件中的任何数据，从而突破了h t 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 2 国内外研究现状 学术界对非时态x m l 索引技术的研究由来己久，有一定的成果，这些成果的 2 山东大学硕士学位论文 应用大大的提高了对于x m l 的查询速度，而非时态x m l 索引的研究较少，处于 前期阶段，所以非时态x m l 索引相对成熟的节点结构关系以及编码的处理思想 对时态x m l 索引研究具有重要的指导意义。本节分两个部分介绍x m l 索引研究 的现状：非时态x m l 索引和时态x m l 索引。 1 2 1 非时态x m l 索引研究现状 非时态x m l 作为一种自定义的数据格式，具有许多传统数据形式所不具 备的特点尤其在i n t e m e t 领域，普遍认为h t m l 将逐步为x m l 所取代。正因 为如此，近年来无论是学术界还是在商业领域，对非时态x m l 数据查询的研 究异常活跃。很多查询语言被相继提出，例如l o r e l ，x m l 2 q l ，xp a t h ，x q u e r y 等等。这些语言规范的一个共同特征是都支持规则路径表示( r e g u l a rp a t h e x p r e s s i o n s ，简称r e , e ) r p e 是一种适合非时态x m l 数据表示的基于图模式的 路径表示机制。为了有效地处理基r p e 的查询，先前的研究提出了很多新的索 引技术，例如l o r e l ，x s e t , t 2 i n d e x , t o x i n ，x i s s ，s p h i n x 以及i n d e xf a b r 等等。 当前对非时态x m l 索引类型的研究大致分为两类：结构摘要类索引和节点记 录类索引。下面我们将分别介绍这两种类型索引。 结构摘要类索引是以x m l 树结构中节点的路径信息为基础，采取某种约简方 式，使得约简后的树结构只维护不同的路径信息，而不会存在具有相同路径的两 个节点。在这类结构摘要索引中，为了达到简化x m l 树的目的，最初多采用自动机 理论中的n f a 到d f a 转化的思路【4 l 】在文献 4 2 中引入了双拟和双似的概念以后， 由于双似概念能够准确地表述结构摘要问题，所以，后续的这类索引多基于这个 概念【4 3 4 8 1 下面我们将详细介绍双拟关系( b i s i m i l a r i t y ) r r l 。这个概念可以说 是结构摘要类索引的基础。 定义l - 1 给定一棵有向树g ，g ( 以d ，其中堤g 中节点的集合，e 是g 中边的 集合：对g 进行转换，可以得到另外一种表达形式g ，( 矿，e ) ，它与原来的g 应具有 如下的关系：g 的点元素集合矿与g 中的曜一样的，同时g 元素间的关系f 与g 中 的e 是一致的，但是二者的表现形式是不同的：否则，g ，- g 基于g 和g ，可以定义一 个二元关系r ，它是g 中节点所口g 的节点矿的笛卡尔积：r = f ，g ) l p 以并且q e 矿) 如果r 满足如下条件，则称尺是g 年 1 g 的一个双拟关系： 3 山东大学硕士学位论文 1 如果在g 中存在一个节点p ，它钸具有关系p 与 即在g 中有边q 将p 和p 连结，那么，在g 中必也存在一个元素g ，它与g 的元素 g 存在关系 2 类似地可以定义g 中元素关系到g 中节点间关系的映射： 如果在口中存在一个节点矿，使得从q 至：l j c 经过元素间关系q ，即g 与矿，那 么，在砷必然也有一个节点，使得从某一节点谚0 也有q 关系，即p 与 由上面的定义我们可以推出：图g 的节点集v g 上的二元双拟关系，记为 ，对任意两个节点u 、v v g ，如果u = v ，则u v ；否则u v ，当且仅当下 面的条件成立： 1 u 、v 有相同的标记； 2 对u 的每一个双亲节点u ，都存在v 的一个双亲节点v ，使得u v ， 反之也成立。 文献【1 8 】提出了1 - i n d e x 索引图，这是一种完全基于双拟关系的索引。为了 增加结构摘要树便利的灵活性，文献【1 9 】进一步提出了f & b 索引，并指出f & b 索引是同类索引中回答t w i g 查询存储空间最小的数据结构，它可以满足全部分 支路径查询的要求。但是，由于f & b 索引在实现上必须依赖内存，而且在基于 它处理查询的优化上还存在进一步的空间。这些因素都限制了f & b 索引在实际 中的应用。其中突出的问题，就是当文档较大时，索引规模较大，对内存提出 了较高的要求。针对这个问题，演化出两类解决方案，一是所谓近似结构摘要 索引，如x s k e t c h ，a ( k ) i n d e x ，d ( k ) - i n d e x ，以及m ( k ) 一i n d e x ；另一个就是文 献 2 0 】提出的基于磁盘存储的并引入序号对的f & b 索引，其主要贡献是提出了 d i s k b a s e df & b 索引，编码使用z h a n g 编码。 文献 2 0 1 放松了对双拟关系的限制，引入了k 阶双拟的概念，用于捕捉x m l 数据中路径的局部特征以满足结构片段查询的特点。在k 阶双拟的基础上，可 以创建相应阶的x m l 索引。a ( k ) i n d e x 1 9 】索引的创建过程是一个逐渐细化的过 程：k 阶索引的建立是在( k 1 ) 阶索引的基础上实现的。在1 - i n d e x 2 0 】和 a ( k ) i n d e x 的基础上，d ( k ) i n d e x l 2 2 1 借鉴了a p e x 中动态反映查询分布的优点， 将二者进行了结合，并具有如下的特征：对任意两个节点u 和v ，如果u 和v 4 山东大学硕士学位论文 之间存在一条边，那么，k ( u ) k ( v ) 一l 。其中，k ( u ) 和k ( v ) 分别表示节点u 和v 的局部相似性( 1 0 c a ls i m i l a r i t y ) ，即父节点的k 值不应小于孩子节点的k 值一l 。 节点记录类索引本质上即是将x m l 数据分解为数据单元的记录集合，同 时在记录中保存该单元在x m l 数据中的位置信息。主要有两种获取位置信息 的方法，一种是节点序号方法( n o d en u m b e r i n gm e t h o d ，有时也称为节点标签 方法，n o d el a b e l i n gm e t h o d ) ，另一种是节点路径方法( n o d ep a t hm e t h o d ) 。对 它们的研究占了x m l 数据处理研究文献中相当大的部分。根据路径信息表现 形式的不同，节点记录类索引分为3 大类：基于节点序号的索引、基于节点路径 信息的索引和二者相结合的混合索引。 节点序号类x m l 索引的基本思想是：基于x m l 文档设计某种遍历策略， 得到由元素组成的序列，节点的标签在序列中就具有唯一的次序，将序列与某 指标集( 最常用的就是自然数) 建立一一映射的关系，对应序列中某个标签就有 唯一的序号；对任意两个具有节点序号信息的节点，可以构建某种运算，该运 算的结果可以表征节点间的结构关系，即 ( 独立单元属性，位置信息) ) _ ， 结构关 系 映射。这种运算就涉及到结构连接算法的范畴。节点序号的选取过程就是所 谓的编码过程。目前已经提出的编码方案主要包括：位向量编码( b i t v e c t o r e n c o d i n g ) 1 5 1 , 前缀编码( p r e f i xe n c o d i n g ) 【6 】，区间编码( r e g i o ne n c o d i n g ) 和 二叉树编码( p b i t r e ee n c o d i n g ) 7 1 等。我们将在第三章详细的介绍节点编码， 在这里不在详细介绍。 节点路径方法的路径信息同样蕴含节点在x m l 数据中结构的信息：如果 给定两节点的路径信息，同时预知两节点存在结构关系的情况下，就必然可以 获知它们之间的结构关系。即节点a 的标签路径包含节点b 的标签路径，那么， 在x l v l l 树中a 和b 之间一定具有祖先子孙的结构关系，且b 是a 的祖先。 所以，基于路径信息来获取节点的结构关系就成为另一组x m l 数据处理技术 的思路来源，并演化出基于节点路径的x m l 索i j l t n , 1 2 。这类索引的核心技术 是字符串的模式匹配。因而，这类索引记录数据的管理方法，有许多是来自于 信息获取领域的。例如，t i l e ，p a t r i c i at r i e 以及s u f f i xt r e e ，甚至s u f f i xa r r a y 等 结构。索引记录的基本模式为( 数据单元标识，路径信息) 。由于这类索引的大 部分处理模式与传统的模式匹配有很深的关系，在此不再展开叙述。仅对基于 山东大学硕士学位论文 路径的多维索引的概念进行简单的叙述。 同时保留节点的序号信息以及节点的路径作为索引记录的位置信息，就构 成了混合索引。这类索引记录的模式多为多个模式的组合，基本的模式为( 数 据单元的标识，路径d ，序号位置信息) 和( 路径，标签路径) 的组合。例 如，文献 1 3 ，1 4 都采用了标签路径与序号对结合的方式。与之不同的是，文献 【1 5 】采取了将后缀树【1 6 】与序号对结合的方式。混合索引吸收了节点记录索引和 路径索引的优点：既具有路径模式匹配是不必分解为最小片断的要求，同时还 能够保证得到的结果符合保序的要求。但是，在支持x m l 数据修改问题上鲜 见有益的探讨。 1 2 2 时态l 索引研究现状 时态x m l 的数据模型一般是由非时态x m l 数据模型扩展而成的，时态x m l 索引领域的研究虽然刚刚开始，但日益引起人们的关注。 在时态x m l 领域，为了有效表示x m l 文档中的时态信息，许多文献提出了不同 的数据模型和相应的查询语言 2 1 , 2 2 , 2 3 , 2 4 。多伦多大学的a l b e r t o0 m e n d e l z o n 等人提出t e m p i n d e x 索引f 3 l , 3 2 ，通过对x m l 树的相同深度的结点划分按时问段的结 点集合构建索引，从而提高了查询的效率。这种索引是用结构索引和时态信息用 紧祸合的方法构造出来的，结点的分类既包含了结构信息也包含了时间信息。这 种索引的工作方式是在给定的查询表达式后，索引在查找满足结构约束的结点的 同时查找满足时态约束的结点。显然加入了时间信息的索引会比原来的索引更加 复杂。它的好处是，索引有一个紧凑的数据结构，占用的空间不会太多，缺点是 增加了索引更新的难度。陈丽冰 2 9 等人通过时间连通的等价性提出扩展的时态 索引技术，但是并未提出具体的实现，同时在时间聚合时扩大了结点时间区间。 文档 4 9 提出t x i d m 模型，介绍了基于结点有效时间的前缀编码方案，并对t x q d m 引入时态连通的等价关系和基于时态包含的拟序关系。 1 3 本文的主要工作 本文针对目前应用背景广泛的时态x m l 索引进行研究，提出新的索引方案 6 山东大学硕士学位论文 s e m a n t i c t r e e 索引。本文的主要工作是针对时态x m l 文档特点，借鉴非时态舰 索引在处理查询上的经验，建立了一套较为完整的索引结构。接着进一步研究 了该结构上的查询算法，并给出了在时态x m l 文档更新时，s e m a n t i c t r e e 索引 的维护算法。最后，通过实验数据与其他索引进行性能比较，发现该索引具有 较好的查询处理速度。 本文的只要内容如下： 1 x m l 索引和时态x m l 索引技术的研究，首先我们介绍了当前的x i d l 索引 技术，给出了索引技术的分类和各种方法的优缺点。 2 x m l 文档编码方法的研究，x m l 文档编码方法使x m l 元素间的结构化关 系更加清晰，总结了几种主流的编码方法，并对其中前缀编码进行扩展，应用 到本文索引方法中，使得文档更新时，不需进行重新编码。 3 s e m a n t i c t r e e 索引模型将结点表、语义树和语义时间划分表三者结合构 成了s e m a n t i c - t r e e 索引。 4 在s e m a n t i c t r e e 索引模型下，讨论时态x m l 的更新和查询算法，并在实 验中证明索引的查询效率。 1 4 本文的组织结构 本文是按照下面的结构组织的： 第一章引言部分介绍了本文研究的背景，分析了本文研究涉及的相关领域 的研究现状和不足；并介绍了本文所做工作的主要贡献及创新点，最后介绍了 本文的组织结构。 第二章是介绍本文涉及到的基本概念，介绍了x m l 模型和时态x m l 模型。 第三章是介绍了各种编码方案以及它们的优缺点，并详细介绍了预留前缀编 码，本文提出的s e m a n t i c t r e e 索引就是采用预留前缀编码技术。 第四章是介绍了s e m a n t i c t r e e 索引模型，通过构建结点表，语义树以及语 义时间划分表从而构成了s e m a n t i c t r e e 索引，并介绍了索引的构建算法。 第五章介绍了s e m a n t i c t r e e 索引查询算法，并根据时态x m l 文档更新的情 况，分增加、删除和更新三种情况研究s e m a n t i c t r e e 索引的维护算法，提高了 7 山东大学硕士学位论文 索引的效率，并通过实验对比了基于了s e m a n t i c - t r e e 索引时态查询算法和其 他时态x m l 索引算法的效率。 第六章对全文进行了总结，分析了本文研究成果的理论意义和应用前景，并 指出了今后需要进一步研究的工作。 山东大学硕士学位论文 2 1x m l 模型 2 1 1x m l 文档 第二章论文基本概念介绍 x m l 规范规定了x m l 数据必须满足的条件，其基本的形式是x m i , 文档。 从逻辑上讲，一个x m l 文档通常由5 部分组成：声明、元素、注释、字符引 用和处理指令，为叙述方便，统称为x m l 数据单元。图2 1 是一个舰文档 片段的举例。 图2 1x 眦文档举例 一个xml 文档是由一些嵌套的元素结构组成元素及其属性由d t d ( 文档类 型定义) 描述，d t d 中的元素类型和属性组织为一个树形结构。d t d 的形式化 定义如下： ： 定义2 1 ：d t d 定义为d = ( e ，a ，e r r ) ，其中： 1 ) e 表示元素类型的有限集合： 2 ) a 表示属性的有限结合； 9 协 一 。渺 一一 一一 。 一一一一一一一一一一一一一一 1 3 5 o o 矽妇元素大于3 5 0 0 的b o o k 元蠢 选取b o o k a t o r e 笛点下的所有包含 ，6 ；d i a | 鼬d 理，如嘲脾 3 5 o o t i t k 声妇元囊大子3 5 。的6 d 砧节点下的 t i t l e 元素 表2 3x p a t h 表达式中使用谓词示例 在x p a t h 标准中，谓词操作的实质是对查询的中间结果进行过滤，包含谓 词的x p a t h 表达式不再是线性的，由于谓词操作在每次对当前节点集进行过滤 时都要执行，因此如何处理表达式中的谓词是影响查询时间空间复杂度的一个 关键因素 4 0 】。y d ) a t h 中谓词通常有三种形式：元素位置，属性比较和分支选择， 而分支选择中每个分支由前两种形式组成。 2 2t x m l 模型 2 2 。1t x m l 文档 为了有效表示半结构化数据中的时间信息，在文献 7 】中，作者提出了时态 x m l 模型( t e m p o r a lx m l d a t am o d e l ) 。这种时态x m l 模型将x m l 文档表示成一 个有向树状图的形式，边上标记有相应的时间。一个t e m p o r a lx m l 文档是由不 同种类的结点所构成的图：文档的根结点，记作r ，r 是没有入边的：值结点，它代表 字符数据；属性结点，记录每个元素的属性以及i d 号：元素结点，由一个元素名做 标记，而且包含着属性结点、值结点和其他元素结点的出边。每个结点都被一个 唯一的整数值作为标识。每条边都被一个时间间隔i 所标记，它代表这条边的有 效时间，即时间间隔i 上这条边才是有效的。如果一条边被一个时间间隔i 所标记， 它代表这条边的有效时间，即时间间隔i 上这条边才是有效的。如果一条边被 1 4 山东大学硕士学位论文 个时间间隔i 所标记，我们将使用一个数对 来表示时间间隔i 。由于每 条边都有有效时间，每个结点也就都有自己的生命周期，它被定义为每个结点的 入边的有效时间之和。由以上性质得出t e m p o r a lx m l 文档具有以下性质：每个结 点出边的有效时间一定包含在此结点的生命周期内：每个结点入边的时间标记一 定是连续的；对于任意时间点t ，t e m p o r a l xm l 文档的子图要么为空，要么是一棵以 r 为根的树。 在图2 4 中，我们给出了一个t e m p o r a lx m l 文档的例子，在例子中我们可以看 到在s t o r a g e - - ) b o o k 路径上，有时间的标识( 其他标识为 o ，n o w 的边的时间标识省 略) 。他们代表的是某本书在某个图书馆中的存放时间，而在传统的x m l 文档及 其使用的查询优化方式中，虽然也会有时间的概念，但大多只是作为一种普通的 属性，而并没有采取过这种存取方式，这也是t e m p o r a lx m l 文档与传统的x m i 文档的最大的区别之处。 2 2 2t x p a t h 图2 4 时态x m l 文档模型举例 t x p a t h 7 是从非时态x m l 查询语言x p a t h2 0 的基础上扩展而来的，符合 x p a t h 2 0 语法规范，同时包含时间操作符，可以有效表示上面的时态数据和时 态文档模型中的查询。 在x p a t h2 0 中，查询表达式是由一系列的标签序列组成，该序列的最后一 个标签标明要求的满足前面表达式的节点。在t a t h 中，表达式本质上是 ( n o d e ，i n t e r v a l ) 对的序列，表达式的结果不仅要满足表达式的结构关系，还 要求在所有的时间限定上具有连续性。为了说明这个连续性，我们引用文献 7 】 山东大学硕士学位论文 给出的最大连续路径的概念。 定义2 3 最大连续路径( m a x i m a lc o n t i n u o u sp a t h ) 设在文档图中，存在从 节点n 1 到n k 的路径，包含的边为e l ( n l ，n 2 ，t 1 ) ，e 2 ( n 2 ，n 3 ，t 2 ) e l ( n k l ，n k ，t k ) 。 令t = n 。扣。t i 。若t 不为空，我们说存在从n 1 到n k 时间区间为t 的连续路径。 若t 不为空，且t 为所有t i 交集的最大子集，我们说存在从n 1 到n k 时间区 间为t 的最大连续路径。 根据这个定义我们可以看出，1 x p a 吐l 表达式的结果是要求找到一条满足表 达式结构要求的连续路径。既满足路径的结构要求，又满足所有的时间限制条 件。由此可见，时态x m l 查询较非时态查询更为复杂。 t x p a t h 在非时态模型x p a t h 的基础上进行扩展，我们对于扩展过程中的时 间有效性部分进行讨论。 定义2 4 ：设g 是一个时态x m l 文档，v ( g ) 为g 的结点集合，g 中的结点 类型分别为根结点、元素结点、属性结点和值结点，分别表示为：r 、v e ( g ) 、v a ( g ) 和v v ( o ) ，则v ( g ) = r ) uv e ( g ) u v a ( g ) uv v ( g ) 。 定义2 5 ：设g 是一个时态x m l 文档，v ( g ) 为g 的结点集合，e ( g ) 为g 的边的集合，任意边为e l ( v k ，v g ) t i ，t j 】，其中e l e ( g ) ，v kev ( g ) ，v g v ( g ) ， 【t i ，t j ) 为边e l 的有效时间，则两结点间可以有多条时间段不同的边。 定义2 6 ：设g 是一个时态x m l 文档，任意v e v ( g ) r - r ) ) ，t l 、t 2 t n 为v 的入边的有效时间，m 1 、m 2 m n 为任意v 的入边的有效时间，则t 1n t 2 n t n = ，m 1n m 2 n m n = ，t 1u t 2 u t n 冬m 1u m 2 u m n 。 本章小结 本章介绍了论文相关的基本概念和理论，分别详细介绍了x m l 模型和时态 x m l 模型，为论文下面的论述准备了理论基础。 1 6 山东大学硕士学位论文 第三章时态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 q u e r y x p a t h 的所有功能 学者已经提出了很多支持高效查询的x m l 文档树的编码格式，常见的编码 格式包括基于包含关系的区域编码和基于路径的路径编码等。近期，为了更好地 支持x m l 查询和更新操作，学者提出了很多巧妙的编码方法。目前已经提出的 编码方案可以分为三类：路径编码 5 0 - 5 3 】，区间编码1 5 4 5 7 1 和其他编码 5 8 - 6 1 】。 路径编码方法将x m l 文档看作是嵌套的，x m l 文档元素的编码是基于该文 档的嵌套结构，或者从文档根节点到达该元素的路径。一种典型的编码是d e w e y 编码【5 3 1 ，由根节点到某个x m l 文档元素的路径向量唯一的标示了该元素，并且 可以用作该元素的编码。在d e w e y 编码中定义每个节点的编码由两部分组成，一 部分继承它的父亲节点的编码作为其编码的前缀，另一部分是用来存储文档