（计算机软件与理论专业论文）基于路径表达式的xml索引查询技术.pdf

原创性声明 j | i i i ll 1iiii i ji iijjjjj l i i j l l l j il u j ， y 18 3 3 8 5 4 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者：了予为日期：。j d 年5 月弓f 日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者： 日期：山? o 年5 月弓7 日 摘要 摘要 如何在海量的x m l 数据中检索到人们需要的信息是当前学者研究的一个热 点问题。结构连接是x m l 查询的核心操作，在对结构连接算法的改进方面有了 大量的研究成果。为提高查询效率，研究者引入了索引技术。目前的结构连接 算法和索引技术依然存在着一定的问题，还有改进的空间。目前的结构连接算 法需要频繁的磁盘i 0 操作，x l d l 索引技术存在着存储空间过大的缺点，在实 际的应用中，不能完全发挥自身的优势。性能和占用空间大小是一对矛盾，如 何采取更好的方式在二者之间达到一个平衡，是值得研究的问题。 本文针对以上问题展开研究，通过建立索引来减少结构连接操作的磁盘访 问次数。在查询过程中，针对包含操作过多的情况，减少无用的连接。以提高 查询效率。本文工作主要包括以下几点： 首先，本文提出了一种新的索引结构，在标签流的概念上，引入了标签路 径，在路径索引中，标签路径和x m l 路径相结合，在包含操作中，只返回所在 标签路径的位置，只经过一次磁盘i o ，就能输出目标节点集合。同时，引入 位图，并分析比较了位图更新的代价。该索引需要较少的存储空间，在查询性 能上也有良好的表现。 其次，当前的索引大都不能处理包含值谓词的路径表达式，而关键字查询 又没有考虑x m l 的路径信息。本文提出了一种基于实体语义的关键字查询方法， 在处理包含谓词的路径表达式时，对相同标签的文本建立索引，采取路径匹配 和关键字匹配相结合的方式，提高了查询效率。 关键词：结构连接，x m l 索引技术，编码方法，路径表达式，关键字查询 i a b s t r a c t a b s t r a c t h o wt or 咖e v et h ei n f o r m a t i o nt h a tp e o p l en e e df r o mv a s ta m o u n t so fx m l d a t ai sah o ti s s u ei na c a d e m i cr e s e a r c hc u r r e n t l y s t r u c t u r a lc o n n e c t i o n ，a st h ec o r e o p e r a t i o no fx m lq u e r y , h a sal a r g en u m b e ro fr e s e a r c hr e s u l t si nt e r m so fh o wt o i m p r o v es t r u c t u r a lj o i na l g o r i t h i n t oi m p r o v eq u e r yp e r f o r m a n c e ，t h er e s e a r c h e r s i n t r o d u c e dt h ei n d e xt e c h n i q u e s t h ec u r r e n ts t r u c t u r a lj o i na l g o r i t h m sa n di n d e x t e c h n i q u e ss t i l lh a v es o m ep r o b l e m s ，i nw h i c ht h e r ei sr o o mf o ri m p r o v e m e n t a t p r e s e n t , t h es t r u c t u r a lj o i na l g o r i t h mt h a tr e q u i r e sf r e q u e n td i s ki 0o p e r a t i o n s ，a n d x m li n d e xt e c h n i q u e sh a v et o ol a r g e s t o r a g es p a c et of u l l yu t i l i z e 也e i ro w n a d v a n t a g e si np r a c t i c e h o wt ot a k eb e t t e rw a y st oa c h i e v eab a l a n c eb e t w e e n p e r f o r m a n c ea n df o o t p r i n ts i z e ，w h i c hc o n t r a d i c t 、7 l ，i t he a c ho t h e r , i sw o r t hs t u d y i n g d e v e l o p i n gt h es t u d yf r o mt h ep r o b l e mm e n t i o n e da b o v e ，t h i sp a p e re r e a t e s i n d e xt or e d u c ea c c e s st i m e so ft h es t r u c t u r a lc o n n e c t i o no p e r a t i o nt od i s k i nt h e c o u r s eo fi n q u i r i n g ，i nt e r m so fe x c e s s i v ec o n t a i n i n go p e r a t i o n ，u s e l e s sc o n n e c t i o ni s r e d u c e dt oe n h a n c et h ei n q u i r ye f f i c i e n c y t h i sp a p e rm a i n l yi n c l u d e st h ef o l l o w i n g t w o a s p e c t s ： f i r s t , t h i sp a p e rp r e s e n t sa 嗍i n d e xs t r u c t u r e ，i nw h i e ht h el a b e lp a t hi s i n t r o d u c e di n t ot h ec o n c e p to ft h el a b e ls t r e a m ，t h el a b e lp a t ha n dt h ex m l p a t ha le i n t e g r a t e di nt h ep a t hi n d e x ，a n di nt h ec o n t a i n i n go p e r a t i o n ，谢mt h eo p e r a t i o nt o r e t u r nt ot h e 耐# n a lp o s i t i o no ft h el a b e lp a t ho n l ya n dt op a s so n c em a g n e t i cd i s c i 0o n l y , as e to ft a r g e tn o d ec a nc o m ei n t ob e i n g m e a n w h i l e ，b i t m a pi si n t r o d u c e d a n dt h ec o s to ft h eb i t m a pu p d m ei sa n a l y z e da n dc o m p a r e d t h ei n d e xr e q u i r e sl e s s s t o r a g es p a c e , a n dh a sg o o dp e r f o r m a n c ei nq u e r y s e c o n d l y , m o s to fc u r r e n t i n d e x e sc a l ln o th a n d l et h e p a t he x p r e s s i o n c o n t a i n i n gt h ep r e d i c a t e ，a n dk e y w o r dq u e r yd o e sn o tc o n s i d e rt h ep a t hi n f o r m a t i o n x m l t h i sp a p e rp r e s e n t sak e y w o r dq u e r ym e t h o d sb a s e do i ls e m a n t i c ，i nw h i c h , w h e nt h el a b e le x p r e s s i o nc o n t a i n i n gp r e d i c a t ei sd e a l tw i t h ，t h ei n d e xi se s t a b l i s h e d i i 堂壁 f o rt h es a m el a b e lv e r s i o n , a n dp a t hm a t c h i n ga n d k e y w o r dm a t c h i n ga r ec o m b i i l e d t o g e t h e ri no r d e rt oe n h a n c eq u e r ye f f i c i e n c y k e y w o r d s ：s t r u c t u r a lc o n n e c t i o n , x m li n d e x t e c h n i q u e ，c o d i n gm e t l l o d ，p a m 、 e x p r e s s i o n ，k e y w o r dq u e r y i i i 目录 目录 摘要i a b s t r a c t j i i 目录 l 绪论1 1 1 引言一1 1 2国内外研究现状1 1 2 1 ) 。存储技术：。1 1 2 2x m l 查询技术2 1 2 3x 札查询优化技术3 1 2 4x 札数据索引技术：二3 1 2 5 研究存在的问题和不足4 1 3 研究内容及文章组织结构4 2 x m l 技术基础6 2 1 基本概念：6 2 1 1 儿概述6 2 1 2x 虬的存储技术6 2 1 3 ) 凹。路径查询7 2 2x m l 编码技术8 2 2 1 区间编码方法8 2 2 2 其它类编码方法1 0 2 3x m l 索引技术1 2 2 3 1x m l 元素索引13 目录 2 3 2x m l 路径索引1 3 2 3 3 ) 。文本索引1 4 2 4 结构连接1 4 2 4 1 直接归并算法。1 5 2 4 2 基于缓存的结构连接算法1 5 2 5 本章小结1 7 3 一种新的索引查询技术1 8 3 1 索引结构的建立18 3 1 1 基于结构摘要的索引技术1 8 3 1 2x m 。路径索引2 0 3 1 3 索引查询模型2 2 3 2 路径表达式的查询2 3 3 2 1 对非法查询路径的处理2 3 3 2 2 线性路径的处理。2 4 3 2 3 包含谓词约束的路径。2 6 3 2 4 标签路径位图2 7 3 3 实验与分析2 8 3 3 1 试验环境和数据集2 8 3 3 2 实验结果分析2 9 3 4 本章小结3 3 4 基于包含值谓词的路径表达式查询3 5 4 1 问题的提出3 5 4 2 s r t 语义3 6 4 2 1 基本概念3 6 4 2 2 实体语义3 6 4 2 3 查询算法。3 8 4 3基于包含谓词的索引结构4 0 v 旦三三一一 4 3 1 索引结构。4 0 4 3 2 查询算法：4 0 4 4 实验及分析4 1 4 4 1 $ r t 实验- 4 1 4 4 2 算法实验4 2 4 5 本章小结。4 3 5 总结与展望。4 4 参考文献4 6 致谢4 9 仑人简历、在学期间发表的学术论文与研究成果5 0 v i 1 绪论 1绪论 1 1引言 当前，互联网与人们的生活、工作息息相关，人们可以很方便地从互联网 上获取信息。然而，随着互联网上信息的爆炸式增长，传统的信息检索技术 ( i n f o r m a t i o nr e t r i e v a l ) 已经不能满足人们的需要。其中部分原因是h 跏l 造成的，h t m l 数据是静态的，标记集合固定。 x m l 数据由于以上优势，在互联网上大量出现，如何在海量的信息里搜索 到自己需要的数据，成为困扰人们的新问题。由于不同于以前数据的独特格式， 传统的查询技术不能完全照搬在对x m l 的查询之上，因而要求我们拓展数据 库理论，开发新的技术。 。 1 。2 国内外研究现状 上世纪7 0 年代以后，e e c o d d 等人通过数学工具建立了关系数据库模型， 2 0 世纪8 0 年代又出现了面向对象的数据库模型。现在x m l 的兴起引发了数据 库研究的新方向。x m l 数据模型既能描述半结构化的数据又能描述结构化的数 据，因此x m l 数据库将给数据库技术带来新的变革。 1 2 1x m l 存储技术 目前，x m l 成为w e b 上数据交换、数据表示的标准，x m l 成为互联网， 上数据重要的存储方式。x m l 存储主要有两种方法：一种是在已有的关系数据 库或面向对象数据库的基础上扩充功能，这种数据库称为支持x m l ( l e n a b l e d ) 数据库，另外一种方式称为原生数据库。 x m l - e n a b l e d 数据库研究主要集中在关系数据库1 1 1 1 2 1 3 1 ，使用关系数据库存 放x m l 数据有以下几个优点：关系数据库技术发展非常成熟，应用最为广泛。 n a t i v ex m l 数据库被用来专门存储和管理x m l 数据，数据库内部模型是基于 x m l 的，保持了x m l 的树结构和相关的元数据。它不关心数据的底层存储格 式，可能建立在数据库或文件系统之上，但只能通过x m l 相关的技术对数据 库进行操作。 l 绪论 o r i e n t x 【4 】是国内第一个n a t i v ex m l 数据库系统，是由中国人民大学开发 的。它以记录为单位进行存储管理，存储系统建立在操作系统的文件系统上， 将查询转换为由x m l 代数运算构成的操作树，采用基于代价估计的查询优化 策略。 、 t i m b e r 【5 j 是密歇根大学于1 9 9 9 年开始开发的个n x d b m s ，系统基于操 作树的块( b u l k ) 代数，主要贡献在于一次一集合的查询处理能力。t i m b e r 基于 非常流行的后端存储系统s h o r e 【6 】，s h o r e 负责磁盘存储器管理、缓冲和并发控 制。支持x q u e l y 查询语言，查询分析器将x q u e r y 转换成代数操作树。 j l o r e ( l i g h t w e i g h to b j e c tr e p o s i t o r y ) 0 7 】由斯坦福大学数据库研究组开发。 它以半结构化数据模o e m ( o b j e e te x c h a n g em o d e l ) 为基础，能够管理x m l 数据 等半结构化数据。在l o r e 开发中，存在不少开创性的工作，如提出l o r e l 语 言用于半结构化查询，提出d a t a g u i d e 用于数据导航等。 1 2 2x m l 查询技术 蹦l 查询是当前x _ , m l 研究的热点。很多研究者作了大量的研究。l 查询通常由路径表达式来实现x m l 的路径查询。结构连接操作被认为是x m l 查询中的核心操作，目前，在结构连接方面已经进行了大量研究，提出了一系 列有效的结构连接算法。这些结构连接算法很多都基于归并的思想【8 】【9 1 ，有的在 归并的基础上，利用索引来提高算法的效率【1 0 】。文献【8 】提出了m p m g t n ( m u l t i - p r e d i c a t em e r g e j o i n ) 算法，该算法使用区域编码实现连接操作。文献 9 1 在m p m g j n 的基础上，提出了s t r u c t u r a lj 0 i n 算法，该算法处理二元结构关系 匹配，包含两类子算法：t r e e m e r g e 算法和s t a c k t r e e 算法。在s t a c k - t r e e 算 法中，利用堆栈保存中间结果，从而提高匹配效率。文献1 1 1 在s t r u c t u r a lj o i n 算法的基础上提出了完整小枝连接算法t w i g s t a c k ，利用紧密堆栈保存小枝中间 结果，实现完整的分支路径匹配。文献【1 2 】【1 9 】在t w i g s t a e k 算法的基础上，提出 了t w i g s t a c k l i s t 算法，提高了p a r e n t c h i l d 类路径匹配效率。文献【1 0 】提出了处 理包含分支的小枝模式的查询，但需要先计算从根到叶的单个路径查询，然后 再将这些单个路径查询的局部匹配结果归并成最终匹配结果，归并过程中需要 大量中间结果的连接操作，大大降低了查询效率。文献【l3 】提出了p f i l t e r 算法， 该方法使用两个索引，l p t r e e 索引和u p e t 索引，分别过滤路径和不同标签的 结点。文献【1 3 】【1 4 1 提出的查询策略都是基于标签和路径的匹配，缺点是需要较大 2 1 绪论 的存储空间来存储索引，存储空间与x 3 v i l 文档中结点个数线性相关，并且以 上方法都是建立在结点有序的基础上。 1 2 3x m l 查询优化技术 x l v i l 查询优化是比较新的领域。文献【1 5 】总结了x 3 v l l 查询优化研究的现 状，主要包括x i v i l 逻辑优化、x i v i l 路径查询选择性估计、x 3 v i l 代价模型和 x m l 统计维护等方面。x m l 查询通常由x p a t h 查询组成，每个x p a t h 查询可 能由多个组先后裔连接和谓词组成，对一个x p a t h 查询，连接的求解顺序经常 有很多种。不同的连接次序执行的开销不同。因此，如何选择恰当的连接次序 是一个很重要的问题。 文献【1 6 】中提出了通过x m l 模式信息简化x m l 查询路径表达式的策略， 并试验证明其有效性。文献【1 7 】提出完全基于路径表达式的查询优化方法。 本文主要研究x m l 数据查询技术，结构查询是x m l 查询语言所特有的， 通常以路径表达式形式出现。以路径表达式为代表的x m l 结构查询是x m l 查 询处理的关键。为提高查询效率，本文对索引结构进行了研究，针对目前查询 会产生不必要的路径归并，在结构连接操作时，不能跳过明显不符合要求的节 点元素，因此，产生了大量无用的连接。现有的连接技术都是建立在节点有序 的情况下，对节点元素列表排序也需要花费时间，并且实际中不一定能满足： 现有的索引技术对值谓词支持度不够，而这种查询普遍存在，如何使用索引技 术，使得对值谓词的操作能高效完成，是值得研究的课题。同时，索引的动态 更新会花费一定的代价，如何能支持数据的动态更新，索引结构本身的动态调 整，也是值得关注的地方。 1 2 4x m l 数据索引技术 ， 文献【l8 】对x m l 数据索引技术进行了总结。将x m l 数据索引分为两大类： 节点记录类索引和结构摘要类索引。节点记录类索引直接针对节点集合的划分 得到最后结果的方式，弥补了要想得到最终满足查询路径的节点，必须顺序依 次访问标签路径对应的节点路径的缺陷。结构摘要类索引只保存x i v i l 数据中 不同的路径，将具有相同路径的节点集合索引在一起，在路径查询过程中，在 这种约简结构中得到相同的结果节点集合。 3 1 绪论 1 2 5 研究存在的问题和不足 如前所述，y j v l 查询和索引方面工作已经得到了广泛研究，并取得了不少 成果，但仍存在不足之处： 1 ) 目前没有公认的包含连接算法和索引结构标准，各种方法只适用于具体 的环境，在这两方面的研究都还处于探索阶段。 2 ) 在目前的索引技术中，存在着性能不高或者存储空间太大的缺点，不能 在两者之间寻找一个平衡点。 3 ) 在查询优化方面还有很多值得研究的地方，查询速度还有提升的空间。 在结构连接次序等方面，还有很多值得挖掘的地方。 1 3 研究内容及文章组织结构 x m l 查询技术是目前研究的热点问题，为了提高查询效率，引入了索引技 术。目前的索引技术存在着存储空间过大的缺点，在实际的应用中，不能完全 发挥自身的优势。性能和占用空间大小是一对矛盾，如何采取更好的方式在二 者之间达到一个平衡，是值得研究的问题。 本文针对目前的问题展开研究，力争在性能和存储空间大小上进行折中。 在查询过程中，针对包含操作过多的情况，力争减少无用的连接。以提高查询 效率。本文工作主要包括以下几点： 本文提出了一种新的索引结构，在标签流的概念上，引入了标签路径，在 路径索引中，标签路径和x m l 路径相结合，在包含操作中，只返回所在标签路 径的位置，只经过一次磁盘i 0 ，就能输出目标节点集合。同时，引入数据仓 库常用的查询优化使用的位图，并分析比较了位图更新的代价。最后，用实验 证明了本索引与同类索引比较，具有一定的性能优势。 提出了一种基于语义实体的关键字查询方法，与传统关键字查询返回共同 祖先节点为根的子树不同，该方法只返回相关的实体子树，具有更好的差准率。 在此基础上，对包含值谓词的路径表达式，采用关键字匹配和路径匹配相结合 的方式，并对相同标签的文本建立索引，对此类表达式有较好的查询效率。 本文共分为5 章，每章的主要内容如下： 第1 章主要介绍了课题的研究背景、研究意义、课题来源、主要研究内容 以及本论文的大致内容框架结构。 4 l 绪论 第2 章介绍了x m l 的技术基础，包括编码技术、现有的索引技术、结构连 接算法，并分析了这些技术的优缺点，为本文的研究奠定了基础。 第3 章给出了基于结构摘要的索引技术，介绍了该索引的查询模型、对不 同路径表达式的处理过程、位图优化操作等，最后实验验证了该索引技术的查 询性能。 第4 章介绍了基于语义实体的关键字查询技术，在该技术的基础上，提出 了针对包含谓词的路径表达式处理技术，对相同标签的文本建立索引，通过路 径匹配和关键字匹配完成查询工作。最后，实验验证了该技术的可行性。 第5 章主要是对本文的研究内容进行总结，同时总结了本文的不足之处， 指出了今后的研究方向。 5 2x m l 技术基础 2 x m l 技术基础 本章将介绍x m l 基本技术概念，主要包括本文应用到的x m l 技术。x m l 索引技术大都是基于编码技术之上的，x m l 查询的核心操作是结构连接，结构 连接算法效率的高低决定了查询效率。 2 1 基本概念 x m l 的基本概念包括其语法概念、存储技术、路径表达式的基本概念。 其中路径表达式是x p a t h 语言的基础。 2 1 1x m l 概述 x m l 依靠d t d 和x m ls c h e m a 来制定文档结构的一系列规则。与d t d 相比，x m ls c h e m a 扩展了d t d 的功能，。使用x m l 语法，具有易于扩展j 约 束力强、支持数据类型丰富等优点，因此，具有更好的发展前景。 x m l d o m 定义了访问x m l 文档的标准。把x m l 文档看成一个树结构， 解析器将x m l 文档读入内存，转换为可被访问的x m ld o m 对象。它的优点 在于对于重复访问和随机访问支持度更好，而缺点是需要将x m l 文档解析到 内存中，容易受空间限制。 s a x ( s i m p l ea p if o rx m l ) 是另外一种提供x m l 访问程序接口的方法。该 方法的优点在于不需要将整个x m l 文档读入内存，节省了空间，在处理大规 模的x m l 数据上具有优势。通过事件驱动接口来实现对x m l 文档的访问， d o m 在灵活性上更胜一筹，s a x 在灵活性上稍有欠缺，优点在于占用内存较 少。 2 1 2 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 6 2x m l 技术基础 文档原有的数据结构和相关的元数据，不关心数据的底层存储格式。目前支持 x m l 存储的数据库主要有面向对象数据库和关系数据库，关系数据库的应用更 为广泛，受到更大的关注。 把x m l 数据存储在关系数据库中，首先要建立映射模型，也就是把x m l 模式影射为关系模型，然后解析x m l 文档导入数据，其中第一步是难点也是 重点。目前建立影射模型主要有两种方法：模型影射( m o d e lm a p p i n g ) 和结构 影射( s t r u c t u r em a p p i n g ) 。 模型映射方法又称为模式无关的映射方法，对所有的x m l 文档采取固定 的关系模式。模型映射方法有基于边的映射和基于节点的映射。结构映射方法 主要依靠) ( i l 文档的d t d 或者s c h e m a ，映射对应的关系数据库，主要分为： 基本内联法、共享内联法、混合内联法。 j ， 2 1 3x m l 路径查询 下面对路径表达式的基本概念给出定义。 定义2 1 主要路径：查询的树模式中，从根节点到输出节点的路径称为主 要路径。 定义2 2 主节点：在主要路径上的节点叫作主节点。 定义2 3 谓词节点：不在主路径上的节点，叫作谓词节点。 定义2 4 主要路径长度：主要路径上的节点数称为主要路径长度。 定义2 5 线性路径表达式：只包含形如“u ”、“u 的表达式是线性路径 表达式。设s 是一个线性表达式，则形如“s u ”、“s u 的表达式是线性表达式， ( 其中u 是标签) 。 定义2 6 分支路径表达式：若占，、s 2 是线性路径表达式，f 是一个整数， 形如“占，m 、“s t i l l 为分支路径表达式。若三是一个分支路径表达式，j 是一 个线性路径表达式，则形如“三嘲”、“题明 的为分支路径表达式。其中k 为一 个整数。 对路径表达式处理的方式有很多种，其基本的方法是对x m l 树进行遍历， 可以分为自顶向下和自底向上两种方法。采取这种方式，效率不高，需要遍历 整个文档，时间复杂度较高。另外种处理方式是基于分解归并的思想，将复 杂路径分解成若干个简单路径，先进行简单路径的查询，最后将结果合并起来。 这种方法的关键之处在于判断节点之间的关系。这种方法不关心具体的路径， 7 2x m l 技术基础 避免了对整个文档的遍历。为提高效率，可以采取索引来实现。特别是包含值 谓词的路径，可以通过值索引和全文索引来提高查询效率。 2 2x m l 编码技术 在信息检索中，广泛采用了倒排索引数据结构，该结构是把一个单词映射 为一个二元组( d o c l d ，f i r s t p o s ) 的列表。d o c l d 表示文件标识符，f i r s t p o s 表示 这个单词在标号为d o c i d 的文件中的位置。由于x n i l 文档具有嵌套的特征， 故该方法不适用于讧l 文件。 目前对于) 【1 v i l 文档树的编码方法，大致可以划分为两类：一类是基于区 间的编码；另一类是基于路径的编码。 2 2 1区间编码方法 区间编码方法的思想是这样的：对x m l 树中的每一个节点元素赋予一组 值，通过值间的关系判断节点之间的关系。该运算只需要常数时间，能快速判 断两节点元素之间的关系。并且易于与传统关系数据库技术融合，应用较为广 泛。如给x m l 树中每一个节点元素赋予一个二元组，元组中的数字分别是该 节点在树中按某种次序遍历的编号。判断一个节点元素是另外一个节点元素的 祖先时，只需判断两组数字之间的关系，若判断两个节点元素的父子关系，加 上两个节点元素的层数就可以很轻松的判断。 区间编码主要分为以下几类：d i e t z 编码、“一m o o n 编码、z h a n g 编码等。 1 ) d i e t z 编码 d i e t z 编码1 1 9 思想为使用树遍历顺序来确定节点对间的祖先后裔关系， d i e t z 编码是第一个采用该方式的编码机制。具体规则为，对x m l 树分别按先 序和后序遍历，对x m l 树中的每一个节点赋予一个二元组 f i r s t ，l a s t ，f i r s t 为节 点的先序遍历编号，l a s t 为节点的后序遍历编号，如图3 1 所示。根据树前序遍 历和后序遍历的概念可知，树中两个节点“是，的祖先当且仅当满足 f i r s t ( u ) f i r s t ( v ) l a s t ( 功 l a s t ( u ) 。在查询时，就可以依据节点的前序遍历和后 序遍历的编码来确定节点之间的关系。 由于x m l 树中任意节点u 、，之间的祖先后裔关系的判断只需判断表达式 ( f i r s t ( u ) f i r s t ( v ) 八l a s t ( v ) l a s t ( u ) ) 是否为真，因此，两个节点的祖先后裔关 8 2x m l 技术基础 系可以在常数时间内计算出来。在此编码方案中，缺点在于缺少灵活性，当有 节点更新时，比如插入新的节点或删除节点时，需要重新计算树节点的前序号 和后序号。如图2 1 所示。 图2 1d i e t z 编码 2 ) z h a n g 编码 z h a n g 编码埔j 的编码规则为：树中的节点元素区分叶子节点和非叶子节点， 对他们分别编码。每一个节点元素赋予一个四元组( d 0 6 n 1 1 l n ，f i r s t , l a s t ，l e v e l ) ，其 中d o c n u m 为该节点元素所在文档的编号，f i r s t 表示在遍历该节点后裔节点之 前访问该节点的编号，l a s t 表示访问该节点所有后裔节点元素之后访问该节点。 l e v e l 代表该节点所在文档树中的层数。判断任意节点之间的关系可以通过位置 编码来决定。如判断任意两节点口和b ，若a 是b 的祖先节点，只需判断节点 元素a 的编码区间包含节点元素b 的编码区间。若要判断两节点之间的父子关 系，则只需在祖先后裔关系的基础上判断两节点层数的关系即可。这种编码方 式的缺点在于当有新的节点插入的时候，需要重新编码。当删除节点时，也需 要重新编码，更新代价较大。如图2 2 所示。 3 ) l i m o o n 编码 图2 2z h a n g 编码 9 2x m l 技术基础 l i m o o n 2 0 】编码的编码规则为：树中的每个节点赋予一个- - 元组 p r e ，s i z e ， p r e 为该节点的扩展先序遍历编号，它的取值是非连续的，为节点的插入预留序 号空间，s i z e 为节点的后裔范围。树中节点“是，的祖先节点，当且仅当 o r d e r ( u ) o r d e r ( v ) 八o r d e r ( v ) + s i z e ( v ) r o r d e r ( u ) + s i z e ( u ) 。同样，如果判断两节点 之间的父子关系，只需加上一个层数即可。如图2 3 所示。l i ，m o o n 编码的优点 是为以后可能的插入保留了额外的空间，在数据更新时，不需要重新编码。缺 点是插入节点过多，会造成预留空间满，无法插入。 图2 3l i - g o o n 编码 2 2 2 其它类编码方法 1 ) d e w e y 编码 d e w e y 编码【2 l 】也称为前缀编码，该编码的编码规则为：直接将一个节点的 双亲节点的编码作为该节点编码的前缀。根据这个性质，可以很方便地判断两 个节点之间的关系。在x m l 树中，如果节点a 是节点b 的祖先，当且仅当满 足a 节点地编码是b 节点编码的前缀，即b 编码从分隔符隔开前缀等于a 的编 码。若判断父子关系，则满足a 是b 的祖先，前缀编码后只有一个分隔符。前 缀编码满足字典有序，同一个节点的孩子节点，其左孩子的编码小于右孩子的 编码。该编码方案能支持包含关系得计算。当x m l 文档较深时，编码会有很 多的分隔符，需要更多的存储空间，影响了编码的效率。如图2 4 所示。 d e w e y 编码 1 0 2x m l 技术基础 2 ) 位向量编码 位向量编码【捌的基本思想是：树中的每个节点被译码为一个刀位向量( 刀 为树t 中的节点数量) ，位置i 上“1 表示第f 个节点，在自顶向上( 或自低 向上) 的编码方案中，每个节点继承表示其祖先( 或后裔) 的所有位上的“1 。 利用二元与运算a n d ( & ) 、或运算o r ( i ) ，能快速判断节点间的关系：对于 继承祖先的位向量编码，节点”是节点v 的祖先，当且仅当c ( “) & c ( v ) = c ( “) ；对 于继承后裔的位向量编码，当且仅当c ( “) i c ( v ) = c ( 甜) 。利用位运算高效的特点， 该方法能提高查询效率。缺点是会造成编码的长度迅速增长，加重存储的负载， 不支持动态更新，当插入数据时，需要重新编码。如图2 5 所示。 图2 5 位向量编码 3 ) 支持数据更新的编码 基于区间的编码大都不支持数据更新，l i m o o n 编码为插入节点预留空间， 但空间满后就将无法插入。d e w e y 编码由于节点继承了祖先节点的编码，故 d e w e y 编码在插入节点后不需要对节点重新编码，但过多的分隔符增大了 编码长度，影响了效率，并且在删除节点后，还需要重新编码。 文献 2 3 】提出了一种支持数据更新的编码方法c s s u ，文献【2 4 1 提出了改编 码的改进编码c s s u l ，该编码方案的基本思想是：将x m l 树中的每个节点赋 予一个三元组 a n c e s t o r , c o d e ，l e v e l ，l e v e l 表示节点在树中的层数，根节点层数为 0 ，a n c e s t o r 为祖先节点的编码，根节点的a n c e s t o r 为空，非根节点的a n c e s t o r 为父节点的a n c e s t o r 加上父节点的c o d e ，c o d e 为节点在兄弟节点按字典序的编 码，根节点的c o d e 为a ，根节点的孩子节点的c o d e 依次为b 、z 、 z b 、。 该方法能有效支持数据更新操作，在插入和删除数据时都不需要重新编码， 但当一个节点的孩子节点数量较大时，编码长度会很长，c s s u l 采取新的策略， 减少了编码的长度，但是在插入、删除时，操作较复杂。 】1 2x m l 技术基础 2 3 x m l 索引技术 按照索引的对象分类，可以分为文本索引、元素索引和路径索引；按照索 引与查询负载的关系，可以分为静态索引和自适应索引。 文献【2 5 1 提出了可索引理论可以作为) | l , m l 索引理论分析的工具。索引评价 需要在特定的负载环境下进行，索引负载包括某种数据定义域的有限子集和一 组查询。 定义3 1 索引负载形是一个三元组胆( d ，1 ，q ) ，其中d 是非空集合( 称 为定义域) ，1 _ c d 是非空有限集( 称为实例) ，q = q j ，q ，q g ) 是，的子集组 成的集合( 称为查询集合) 。 定义3 2 索引负载胆( d ，j ，q ) 的一种索引方案s 是块( b l o c k ) 的集合 鼯 s ，& ，最) ，其中sf s 厶且i s f l = b ( 1 内) ，常量b 称为块大小。s 是，的一个覆盖，其中： ， j2 u s i i - 1 基本标签索引是种简单的x m l 索引结构，能够快速对节点进行定位， 主要思想是将具有相同标签名的元素映射在一起。 定义3 3 基本标签索引s i g将文档t中的元素和属性名称映射到具有_index 该名称的节点i d 的列表。对于w ，s i g _ i n d e x ( w ) = ， 其中l a b ( v i ) - - w ，1 f 七，且d o c v j l o c v 2 l o c 。 基本标签索引使用b + 树来实现。基本标签索引结构简单、易于实现，其缺 点是只考虑了节点标签，无法区分不同路径上的同名节点元素。 文献【2 6 】提出了双拟关系( b i s i m u l a f i o n ) 的概念应用于半结构化数据。 定义x m l 数据模型z 上的双拟关系是两个节点之间的一种对称二元关 系，对于任意两个节点u 和1 ，“1 ，成立，当且仅当 1 ) u 和v 具有相同的标签，即l a b ( u ) = l a b ( 。 2 ) 且”的父节点与v 的父节点具有双拟关系，即( “)