（计算机应用技术专业论文）xml+twig查询优化研究.pdf

摘要 摘要 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 w i g 查询，其中整体t w i g 查询可以避免结构连接产生大量的中间结果而具有很大的优越性，得到了广泛的 研究。 本文对整体t w i g 查询优化展开研究，主要做了以下几个方面的工作： ( 1 ) 提出了d b l 排序算法，用于决定叶子查询结点的处理顺序，更重要的是 在构造与查询结点相关联的列表中起到过滤对查询结果没有贡献的元素 的作用。 ( 2 ) 提出了一种新型的整体t w i g 查询算法t w i g s t a c k f a s t ，它是个单阶段算法， 采用e x t e n d e dd e w e y 编码，能够处理带a d 关系、p c 关系的查询，而 且是c p u 和i o 最优的。t w i g s t a c k f a s t 算法没有第二阶段的合并连接操 作，因而可以消除了大量的时间和空问开销。 ( 3 ) 通过把t w i g s t a c k f a s t 算法与四个经典的t w i g 查询算法t w i g s t a c k 、 h o l i s t i c t w i g s t a c k 、t w i 9 2 s t a c k 、t j f a s t 进行实验对比后可以看出， t w i g s t a c k f a s t 具有更优越的性能。 关键词：x m l ；整体t w i g 查询；e x t e n d e dd e w e y 编码 a b s t r a c t a b s t r a c t b e c a u s eo ft h ec h a r a c t e r i s t i c so fs e l f - d e s c r i p t i o n ，e x t e n s i b i l i t ya n do p e n n e s s ， x m lh a sb e c o m et h ef a c t u a ls t a n d a r do ft h ed a t ar e p r e s e n t a t i o na n de x c h a n g ei nt h e w e b w i t hx m ld a t ar a p i d l yi n c r e a s i n g ，e s p e c i a l l yw i t ht h el a r g ex m ld a t ae m e r g i n g , x m l q u e r yr e s e a r c hi sb e c o m i n gt h eh o t s p o ti nb o 廿li n d u s t r ya n da c a d e m i a w i t ht h e c h a r a c t e r i s t i co fs e m i s t r u c t u r e ，t h et r a d i t i o n a ls q lq u e r ya l g o r i t h m sf o rt h er e l a t i o n a l d a t a b a s ea r en ol o n g e ra p p l i c a b l et ox m ld a t a s oh o wt oe f f i c i e n t l yq u e r yx m ld a t a b e c o m e san e w s t u d y i no r d e rt oa c h i e v et h ex m ld a t aq u e r yo p t i m i z a t i o n ，i nr e c e n ty e a r sr e s e a r c h e r s h a v ep r o p o s e dal o to fa l g o r i t h m s ，s u c ha st r e ee n u m e r a t i o nb a s e do np a t hi n d e x e s ， a p p r o a c h e sb a s e do ns e q u e n c e s ，s t r u c t u r a lj o i n sa n dh o l i s t i ct w i gj o i n s h o l i s t i ct w i g j o i na l g o r i t h m sy i e l ds i g n i f i c a n t l yl e s si n t e r m e d i a t er e s u l t st h a ns t r u c t u r a lj o i n s ，s oa l o to fr e s e a r c hh a sb e e nm a d eo nt h i s i nt h i sp a p e r , r e s e a r c hh a sb e e n d o n ei nt h ef o l l o w i n ga s p e c t s ： ( 1 ) t h i sp a p e rp r o p o s e sd b l s o r ta l g o r i t h m ，w h i c hd e c i d e st h eo r d e rf o r p r o c e s s i n gl e a fq u e r yn o d e sa n dp l a y sa ni m p o r t a n tr o l ei nf i l t e r i n gx m l d e m e n t sw h i c hd o n tm a k ec o n t r i b u t i o nt oq u e r yr e s u l t s ( 2 ) t h i sp a p e rp r o p o s e st w i g s t a c k f a s t ，an o v do n e - p h a s eh o l i s t i ct w i gj o i n a l g o r i t h m ， w h i c hu s e se x t e n d e dd e w e ye n c o d i n g i tc a l ls u p p o r te f f i c i e n t e v a l u a t i o no fq u e r i e sw i t hp co ra dr e l a t i o n s h i p i ti sc p ua n di oo p t i m a l i td o e s n tn e e dt op e r f o r mm e r g eo p e r a t i o no ft h es e c o n dp h a s et h a to t h e r a l g o r i t h m sd o ，w h i c he l i m i n a t e ss i g n i f i c a n ta m o u n t so ft i m ea n ds p a c e o v e r h e a d s ( 3 ) t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt w i g s t a c k f a s th a sb e t t e rp e r f o r m a n c ef o r x m lt w i gq u e r i e st h a no t h e rt y p i c a l a l g o r i t h m s s u c ha s t w i g s t a c k ， h o l i s t i c t w i g s t a c k ，t w i 9 2 s t a c ka n dt j f a s t k e yw o r d s ：x m l ；h o l i s t i ct w i gq u e r y ；e x t e n d e dd e w e ye n c o d i n g 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ： 及一 硼年么月；e l 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办法 等规定保留和使用此学位论文，并向主管部门或其指定机构送交学位 论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书馆及 其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博士、 硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇 编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文，于 年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“ 或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) ：昔磐轧 吲年名月，日 第一章绪论 1 1 研究背景及意义 第一章绪论 随着i n t e m e t 不断地介入社会生产的各个领域、人们生活的方方面面，i n t e m e t 与人类的关系越来越密切，成为人们获取和传递信息的主要渠道之一。i n t o n e t 上的资源各种各样，不仅有传统的关系型数据，也有半结构型数据如h t m l 和 无结构型数据。传统上用关系型数据库来存储和查询i n t e m e t 上的所有数据的方 法变得越来越困难。 作为一个精简的s g m l 子集，x m l 具有自我语义描述，便于创建和传输， 易于对数据进行封装等诸多特性，所以x m l 成为i n t e r n e t 上数据表示和数据交 换的事实标准。x m l 的数据量正在呈指数级增长，随着大规模x m l 数据的出 现( 如x m l 数据库) ，对x m l 数据的查询正在成为学术界和工业界的研究热点。 x m l 作为一种半结构型数据，与传统的关系型数据有很大的差别。关系型 数据采用s q l 语言进行查询，s q l 语言已经是一个成熟的关系数据查询标准， 有一整套成熟的理论作为支撑。关系型数据由行列的二维数组的形式组织，列的 长度是固定的、可预测的。而x m l 是按照树状结构的形式组织，树的深度和广 度是不可预测的。由于数据组织形式上的差别，对关系型数据的查询结果是一个 二维数组，而对x m l 的查询结果是一棵树状结构。 正是由于结构上的巨大差别，用s q l 语言来查询x m l 数据显得笨拙和低效。 因此，大量的x m l 数据查询规范和查询技术被提出来，如l o r d ，x m l q l 2 1 ， x q l 3 1 ，q u i l t 钔，x q u e 5 1 等等。这些查询语言尽管各有特点，但它们的一个共 同特点是将路径表达式作为其核心内容，可以用路径表达式来描述x m l 元素在 数据层次中的定位。 一般来说，x m l 查询的核心是通过对多个元素的树形结构关系( 如父一子 关系，祖父一后代关系) 的模式匹配，实现对x m l 元素的选择运算。针对x m l 查询处理的方法有基于路径索引的树遍历【6 。引、基于序列的方法【9 。1 1 】以及结构连接 1 2 - 2 2 1 和整体t w i g 2 3 - 3 3 】查询。目前应用最广泛的是结构连接和整体t w i g 查询。结 构连接是把一个t w i g 模式分解成系列的二元结构关系( 譬如父- 子结构和祖先一 x m l t w i g 查询优化研究 后代结构) ，通过结构连接算法从x m l 数据库获得这些二元结构的匹配数据，然 后把查询结果合并连接起来。这种分解的缺点就是可能会产生大量的无用的中间 结果，而且会有大量的空间和时间的开销，所以有人提出了整体t w i g 查询算法。 整体t w i g 查询算法就是对整个t w i g 查询树进行处理而不会产生大量的中间结果， 所以整体t w i g 查询成为一个热门的研究课题。 1 2 国内外研究现状 文献 2 3 1 最早提出了整体t w i g 查询算法t w i g s t a c k ，为每个查询结点q 维护 一个s t a c k ，s t a c k 中的元素为p c 关系或a d 关系，每个元素还包含一个指针指 向父亲查询结点的s t a c k 的匹配元素，采用这种s t a c k 结构来表示查询结果，可以 避免结构连接产生大量的中间结果，并且该算法对只含a d 关系的查询是最优 的。文献 1 3 1 提出了如何利用索引来加速整体t w i g 查询，从而提高算法效率。 文献【2 7 】提出t w i g s t a c k 的改进算法t w i g s t a c k l i s t ，为每个查询结点增加一 个l i s t ，l i s t 的最大长度为x m l 文档的深度，从而使得一部分包含p c 关系的查 询达到最优。文献 2 9 研究了如何处理t w i g 查询中包含o r 谓词的情况。文献 3 0 】 研究了如何处理t w i g 查询中包含n o t 谓词的情况。 文献 2 4 提出了基于t a g + l e v e l 和p p s 流的方法来改善整体t w i g 查询。 t a g + l e v e l 对只包含或只包含或只包含一个分支结点的查询是最优的。文 献 2 5 提出了扩展的d e w e y 编码，它可以通过叶子结点的编码推出整个路径，因 此查询时，只需读取叶子查询结点的元素流，从而减少了一部分i 0 操作。文献 【2 6 提出了基于p r e f i xp a t hs t r e a m i n g ( p p s ) 的方法来改善整体t w i g 查询，它对于 只包含或只包含或只包含一个分支结点的查询是最优的。文献【2 8 】证明了对于 和谓词任意混合的查询，普通的t a g 流是不能达到最优的。 文献 3 1 提出了t w i 9 2 s t a c k 算法，它采用了一种新的分层s t a c k 结构h s ( h i e r a r c h i c a ls t a c ke n c o d i n gs c h e m e ) ，为每个查询结点n 维护一个h s n ， 该算法采用后序遍历x m l 文档来从叶子结点匹配到根结点，把每个查询结点n 对 应的查询结果放在h s n 中，该算法避免了其他整体t w i g 查询算法的的第二阶 段路径合并连接运算，并且可以消除重复的查询结果，还可以对查询结果进行排 序、分组等等。文献 3 2 1 提出了单阶段的整体t w i g 查询算法，通过改进s t a c k 的 2 第一章绪论 结构，可以避免其他t w i g 查询算法如t w i g s t a c k 的路径合并阶段的空间和时间开 销。文献 3 3 】提出了t w i g b u f f e r 算法，采用一种新的缓存策略，对于带有和 谓词的查询，可以完全避免输出无用的查询结果。 1 3 研究动机 文献 2 3 最早提出了整体t w i g 查询算法t w i g s t a c k ，极大地提高了查询效率。 但是由于t w i g s t a c k 是两阶段算法，在对第一阶段产生的中间结果进行合并连接 时会消耗大量的时间和空间。所以人们又提出了各种单阶段算法，譬如 t w i 9 2 s t a c k t 3 1 1 、h o l i s t i c l w i g s t a c k 【3 2 】等等。这些算法采用的都是区间编码，在查 询处理时要读取大量的元素，因此算法也要对大量的元素进行过滤处理、压入堆 栈等操作，产生大量的时间和空间开销。e x t e n d e dd e w e y 编码是前缀编码，其优 点在于给定一个元素的编码，可以知道它的所有祖先结点的编码和名称。采用 e x t e n d e dd e w e y 编码，可以减少查询处理时读取的元素的数量，所以本文研究的 内容是：提出一种基于e x t e n d e dd e w e y 编码的单阶段算法，对于带a d 关系、 p c 关系的查询在时间复杂度、空间复杂度上都是最优的。 1 4 主要研究工作 本文研究了x m l 查询优化处理，重点研究了整体t w i g 查询处理算法，主要 做了以下几个方面的工作： ( 1 ) 提出了d b l 排序算法，用于决定叶子查询结点的处理顺序，更重要的是 在构造与查询结点相关联的列表中起到过滤对查询结果没有贡献的元素 的作用。 ( 2 ) 提出了一种新型的整体t w i g 查询算法t w i g s t a c k f a s t ，它是个单阶段算法， 采用e x t e n d e dd e w e y 编码，能够处理带a d 关系、p c 关系的查询，而 且是c p u 和i o 最优的。t w i g s t a c k f a s t 算法没有第二阶段的合并连接操 作，因而可以消除了大量的时间和空间开销。 ( 3 ) 通过把t w i g s t a c k f a s t 算法与四个经典的t w i g 查询算法t w i g s t a c k 、 h o l i s t i c t w i g s t a c k 、t w i 9 2 s t a c k 、t j f a l s t 进行实验对比后可以看出， t w i g s t a c k f a s t 具有更优越的性能。 3 x m lt w i g 查询优化研究 1 5 论文的组织结构 第一章介绍了本文的研究背景、意义以及国内外研究现状，并对本文的主要 研究工作和内容安排进行了介绍。 第二章对x m l 的一些背景知识，譬如x m l 概念、x m l 文档树模型、x m l d t d 和x m l 查询语言进行了简单介绍，同时对x m l 文档树的两种基本编码方 法一区间编码和前缀编码进行了介绍。 第三章先介绍了t w i g 模式查询和t w i g 模式匹配，然后对已有的整体t w i g 查 询算法进行了总结分类，接着详细介绍了四种已有的整体t w i g 查询算法，如 t w i g s t a c k ，h o l i s t i c t w i g s t a c k ，t w i 9 2 s t a e k 和t j f a s t 。 第四章先介绍了e x t e n d e dd e w e y 编码，然后介绍了算法用到的数据结构和相 关函数，接着给出了d b l 排序算法，随后详细讲述了t w i g s t a c k f a s t 算法，并对 算法的正确性、时间复杂度和空间复杂度进行分析，最后对算法进行了实例说明。 第五章先介绍了实验环境和测试数据集，然后给出了实验系统的总体架构， 最后把t w i g s t a c k f a s t 与t w i g s t a c k 、h o l i s t i c t w i g s t a c k 、t w i 9 2 s t a c k 、t j f a s t 进行 了实验对比分析。 第六章是对本文的总结，并指出了将来进一步的研究方向。 其中核心部分在第四章和第五章。 4 第二章x m l 背景知识 2 1x m l 简介 第二章x m l 背景知识 x m l 是w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ，万维网协会) 制定的用于描述数据 文档中数据的组织和安排的结构语言。它是一种标记语言，类似于h t m l 语言。 但它的主要用途不是用于w e b 页面的显示，而是在w e b 的应用之间、应用与用 户之间进行数据交换。 x m l 是s g m l 的一个分支，作为一种自描述的元标记语言，具有以下特点： 半结构化、自描述性、扩展性和灵活性。 ( 1 ) 半结构化 半结构化是x m l 的一大特点。用户可以通过文档类型定义规范为x m l 定 义语法、数据结构以及元素类型，并且可以根据用户的需要增加、删除标记。 x m l 文档可以用不同的样式进行显示。利用标记自身所包含的语义，x m l 可以 将异构的数据集成在一起。利用x m l 半结构化特性可以解决异构数据转换的问 题。 ( 2 ) 自描述性 x m l 文档通常包含一个文档类型声明，因而x m l 文档是自描述的。x m l 表示数据的方式真正做到了独立于应用系统，并且数据能够重用。x m l 文档被 看作是文档的数据库化和数据的文档化。 ( 3 ) 可扩展性 x m l 允许使用者创建和使用他们自己的标记。这一点至关重要，企业可以 用x m l 为电子商务和供应链集成等应用定义自己的标记语言，甚至特定行业一 起来定义该领域的特殊标记语言，作为该领域信息共享与数据交换的基础。 ( 4 ) 灵活性 在x m l 中，数据和显示格式是分离设计的，h t m l 提供显示的内容，而 x m l 描述数据本身。所以，x m l 具有灵活的w e b 应用。 图2 - 1 是一个示例的x m l 文档。x m l 文档是基于文本格式的，它的最基本 构成包括x m l 声明，处理指令和x m l 元素三部分，也可以有注解，元素中可 以包含属性或者子元素等。 5 x m lt w i g 查询优化研究 x m l 声明一般出现在文档开头部分，包括版本号、可能的语言编码、可选 的文档类型定义( d t d ) 等。如图2 - 1 中， 就是x m l 声明。 x m l 文档的定义形式是一个简单的层次树，每个文档都有一个而且只有一 个根结点，它被称为文档实体或文档根。根元素出现在声明之后，它包括文档剩 余部分，这部分包括元素、处理指令、属性、注释、实体引用等。如图2 1 中， “班级”就是该x m l 文档的根结点。 x m l 文档中，标记应成对出现，即每个元素必须有开始标记及其对应的结 束标记，并且标记可以逐层嵌套。属性是元素的性质，在元素的开始标签内定义。 注释以“ 结束，它可以出现在文档的任何位置。一个x m l 文档必须有良好的格式和符合语法定义。 2 2x m l 文档模型 图2 - 1x m l 文档示例 x m l 文档是一个自描述的嵌套结构，通常我们把一个x m l 文档的模型看 成是一棵有根、有序、带标记的树，树中的结点表示文档中的元素、属性和文本 结点。每个结点都对应惟一的一个标签，树中的边表示结点之间的嵌套关系，兄 6 第二章x m l 背景知识 弟元素的顺序由树结点的先序遍历得到。以下就是图2 1 对应的x m l 文档树， 图中省略了文本结点。 2 3x m l 与d t d 民族 图2 - 2x m l 文档树示例 别 文档类型定义d t d ( d o c u m e n tt y p ed e f i n i t i o n s ) 定义了x m l 文档的逻辑结 构，是描述x m l 文档语法和语义的一种正式语法，它规定了文档中的元素命名、 位置及组合方式等。它可以内嵌在文件中，也可以是一个外部文件。d t d 有三 个基本用途：对x m l 标记编制文档、加强标记参数内部的一致性、使x m l 语 法分析器验证x m l 文档的合法性。 d t d 使用一种特殊的语法来声明出现在x m l 文档中的每个对象( 元素、属 性等) 。 语句表示对元素的声明，里头的内容为元素的名称及其内 容模型，内容模型列出了该元素可能的子元素。假设e 代表元素名称，则在d t d 中，e 奉代表e 可以出现零次或多次；e ? 代表e 可以出现零次或一次；c + 代表e 必须出现一次或多次。 语句表示对属性的声明，里头的内容为：该 属性的父元素的名称、该属性的名称、属性类型、属性的默认值。如图2 3 为图 2 1 的x m l 文档所对应的文档类型定义。 7 x m lt 撕g 查询优化研究 2 4x m l 查询语言 图2 - 3d t d 示例 x m l 数据的查询语言主要有l o r e l t l l ，x m l q l t 2 1 ，x q l t 3 1 ，q u i l t 4 1 ，x q u e 5 1 ， x p a t h 蚓等等，其中最重要的是x q u e r y 和x p a t h 。 ( 1 ) x q u e r y 语言 x q u e r y 是x m lq u e r y 的缩写，它始于q u i l t 查询语言。w 3 c 的x m lq u e r y 工作组对x q u e r y 的研究工作开始于19 9 9 年。x m lq u e r y 工作组旨在设计一种 语言能够达到以下要求：能够满足结构化和半结构化文档协议独立性；能够在任 何系统下获得可以预期的结果；定义一种声明式语言而非过程式语言；强类型， 能够识别潜在异常以及进行查询优化；能够跨文档集查询；尽可能共享和使用 w 3 c 标准，例如x m l l 0 ，n a m e s p a c e s ，x m ls c h e m a 和x p a t h 。 2 0 0 7 年1 月x q u e r y l 0 正式成为w 3 c 标准。x q u e r y 在很大程度上借鉴了 s q l ，而且很多x q u e r y 的设计人员同时也参与了s q l 的设计。x q u e r y 和s q l 的区别非常清晰，x q u e r y 用于x m l 而s q l 用于关系数据。但是，现在它们之 间的区别日渐模糊，因为很多关系数据库开始增加x m l 支持，允许将x m l 数 据存储到关系数据库当中。x q u e r y 不可能代替s q l 在关系数据库中查询结构 化数据。这两种查询语言将同时存在，并用于不同的数据查询当中，x q u e r y 用 于非结构化数据查询和基于x m l 的应用程序；s q l 继续用于结构化的关系数 据查询。 x q u e r y 构建在x p a t h 规范之上。x q u e r y l 0 和x p a t h 2 0 有很大程度的重叠， 它们有相同的数据模型和内建函数及操作符。x p a t h 2 0 可以说是x q u e r y l 0 的 子集，x q u e r y 包含了很多x p a t h 所不具备的功能，如f l w r 和x m l 构造器， 这是因为它们和选取无关而和构造存储查询结果有关。x q u e r y 中最强大的特性 第二章x m l 背景知识 是f l w r 表达式，f l w r 表达式可以完成很多在x s l 样式表中所完成的任 务。 x o u e r y 依照句法在数据操作上支持许多x s l 不直接支持的操作，但是其 底层的引擎还是必须读取每篇文档、解析它，然后使用查询语言对它操作。因 此，对于已建立索引的文档资源库，x q u e r y 是快速访问文档具体内容的好解决 方案；但是对于未建立索引的文档，它不是一个好的解决方案。x q u e r y 包含一 些用来访问资源库中多个文档的机制。x q u e r y 允许以编程方式在同一个查询中 访问多个文档，但仍需要装入并解析每个文档。因此，要达到最佳性能，最好 使用x m l 数据库或其它形式的索引模型。 x q u e r y 最擅长处理“混合 文档一一同时包含叙述流和量化数据的文档。 此类文档不适合存储在关系型数据库中，但是，x q u e r y 却适合于处理此类文档， 它能直接从x m l 文档中抽取出量化信息。但是，如果文档是纯数据，那么将 该文档引入到关系型数据库中进行操作会更有意义。x q u e r y 还具有从多种数据 库中检索信息的特点，并且能够对各种数据和文档进行查询。 ( 2 ) x p a t h 语言 x p a t h 是由w 3 c 创建的。在w 3 c 的规范里，对x p a t h1 0 的描述是这样 的：“x p a t h l 0 是致力于为x s l t 和x p o i n t e r 的公共功能提供一种共同的语法 和语义的结果。x p a t h 的主要目的是对一个x m l 文档进行寻址。为了支持这个 主要目的，它也为操纵字符串、数值和布尔值提供了一些基本功能。x p a t h 使用 一种紧凑的、非x m l 的语法，以方便在u r l 和x m l 属性值中使用x p a t h 。 x p a t h 是在x m l 文档的一个抽象逻辑结构上进行操作，而不是在它的表面语法 上。x p a t h 因为使用类似u r l 的路径表示法，在一个x m l 文档的层次结构中 进行导航而得名。除了用来寻址外，x p a t h 也被设计为包含一个能够用于匹配的 自然子集，x p a t h 的这种用法定义在x s l t 的规范中。 x p a t h l 0 是一个简单有效的标准，x p a t h l 0 推荐标准和最新的x p a t h 2 0 工作 草案中都这样说：“x p a t h 是用于对x m l 文件的部分进行定址( a d d r e s s i n g ) 的语 言”。这是对x p a t h1 0 特性的恰当描述。x p a t h 2 0 是x q u e r y 的一个严格的语法 子集，对x p a t h l 0 的增强，通常反映在五个方面： 1 序列 9 x m l t w i g 查询优化研究 x p a t h l 0 通常返回结点集，而x p a t h 2 0 返回序列。序列与结点集相似，但 提供了更多的功能。结点集和序列之间最重要的差异之一是：与结点集的无序不 同，序列是有序的。每个x p a t h 2 0 表达式都返回一个序列，即使它是只有一项 的。 作为一种处理序列的语言，x p a t h 2 0 中一切都是序列。一个“数字 或“字 符串 的表达式，实际上意味着一个“数值序列 或一个“字符串序列”。 没有序列之序列。如果你试图在序列中嵌套序列，当然在句法上可以接受， 不过你得到的是一个“膨胀的”序列，子序列和包含它的序列仍然是依次排列的。 与x p a t h l 0 的结点集( 或一般的集合) 不同，序列内可以有重复。如表达式 ( f o o b a r , f o o ，f o o b a r ) ，这个序列的组成是b a r 元素，之后是f o o 元素，接着还 是同样的b a r 元素。在x p a t h l 0 中，我们无法构造这样的集合，因为根据定义， 结点集内不能包含同样的元素一次以上。 2 数据类型 x p a t h1 0 中的表达式只支持四种数据类型：结点集、字符串、布尔型和数 字。这种取值虽然简单，不利之处是在处理其他类型数据( 比如日期) 时受到限制。 x p a t h 2 0 引入了对x m ls c h e m a 内建数据类型的支持，使用户能直接访问1 9 种 简单类型，包括日期、年、月、u r i 等等。此外，为了处理和构造这些不同的数 据类型，还提供了几个函数和操作符。这些内容可以在“x q u e r y1 0a n dx p a t h 2 0 f u n c t i o n sa n do p e r a t o r s ”文件中找到。x p a t h 2 0 不仅包含对x m ls c h e m a 内置数 据类型的支持，而且还包含对用户定义的数据类型的支持。 3 增强的函数集 x p a t h 2 0 包含丰富的用于操作数据的函数，就像x q u e r y 一样。实际上， x p a t h 2 0 和x q u e r y 是共用一个核心函数库的，它们在“x q u e r y1 0a n dx p a t h 2 0 f u n c t i o n sa n do p e r a t o r s ”中被定义。x p a t h 2 0 提供的核心函数库中定义的函数有 1 6 类之多，而在x p a t h1 0 中只有四类。x p a t h 2 0 还允许用户自定义函数。 4 多个数据源 x p a t h 2 0 具有显式地为表达式设置数据源的能力，从而可将多个数据源中 的数据合并到单个查询。 5 许多新的表达式 1 0 第二章x m l 背景知识 x p a t h 2 0 既支持传统的x p a t h 路径表达式，另一方面，又提供了一些新的 表达式，如f o r 表达式、条件表达式和定量表达式等。 在x p a t h 2 0 处理序列的新运算符中，最强大的大概就是f o r 表达式。它可 以对序列进行列举，为引用序列的每个成员返回一个新值。这一点与x s l ：f o r - e a c h 很相似，不同之处在于它实际上返回的是一个序列，你然后可以按照序列对这个 返回值进行操作。 x p a t h 2 0 最强大的结构之一就是条件表达式。这里是x p a t h 2 0 工作草案中 的一个例子： 图2 - 4 条件表达式示例 总而言之，x p a t h 2 0 是x p a t h l 0 的一个非常重要的升级。x p a t h 2 0 一方面 引进了许多新的特性，另一方面也保持了一定程度上的兼容性。 x p a t h 中的基本要素是和x m l 文档中的组成要素是相对应的，具体包括： 1 根结点 根结点是一棵树的开始，根结点是唯一的。树中的其它所有元素结点都是它 的子结点或后代结点。对根结点的处理机制与其它结点相同。在x p a t h 中对树 的匹配总是从根结点开始。 2 元素结点 元素结点对应于文档中的每一个元素，一个元素结点的子结点可以是元素结 点、注释结点、处理指令结点和文本结点。可以为元素结点定义一个唯一的标识 i d 。元素结点可以有扩展名，包括命名空间u r l 和本地命名。 3 文本结点 文本结点包含了一组字符数据，即c d a t a 中包含的字符，文本结点没有扩 展名。 x m lt w i g 查询优化研究 4 属性结点 每一个元素结点有一个相关联的属性结点集合，元素是每个属性结点的父结 点，但属性结点却不是其父元素的子结点，也就是说通过元素可以查到属性结点， 而反之不成立，原因在于x p a t h 规定元素的属性结点是单向的。此外，元素的 属性结点不能被共享，不同的元素结点不能同享一个属性结点。 5 命名空间结点 每一个元素结点都有一个相关的命名空间结点集。在x m l 文档中，命名空 间是通过保留属性声明的，因此，在x p a t h 中该类结点与属性结点很相似，它们 与父元素之间的关系是单向的，并且不具有共享性。 6 处理指令结点 处理指令结点对应于x m l 文档中的每一条处理指令。它也有扩展名，扩展 名的本地命名指向处理对象，而命名空间部分为空。 7 注释结点 注释结点是对x m l 文档的注释。 x p a t h 的目的是在匹配x m l 文档结构树时能够准确地找到某一个结点元 素，能够完成x q u e r y 的基本功能。在x p a t h 语法中，是通过一系列的路径匹 配规则来实现的。 1 路径匹配 路径匹配与文件路径的表示相仿，主要有以下几种路径操作： ( 1 ) 用“”表示结点之间的父一子关系，女n a a c d 表示结点“a ”的子结 点为“b ”，并且“c 的子结点为“d ，这里“a ”表示根结点。 ( 2 ) 用“”表示结点之间的祖先一后代关系，如“d ”表示所有在x m l 文 件中出现的d 元素。再比如“a e ”表示所有的以“a ”为祖先结点的e 元素。 ( 3 ) 用“表示通配符，如“a b c * ，表示a 元素一b 元素一c 元素下 的所有子元素。 2 位置匹配 对于每个元素，它的各个子元素是有序的。如“a b c 1 表示a 元素 一b 元素一c 元素之下的第一个子元素；“a b c 1 a s t 】 表示a 元素一b 元素一 c 元素之下的最后一个子元素；“a b c p o s i t i o n 0 1 】 表示a 元素一b 元素一 1 2 第一二章x m l 背景知识 c 元素之下的位置大于l 的c 元素。 3 属性及属性值 在x p a t h 中，可以利用属性及属性值来匹配元素，要注意的是元素的属性 名前要有“ ”前缀。例如，“b i d ”表示所有具有属性i d 的b 元素。再如 “b d = “m 】 表示i d 值为“m ”的b 元素。 4 亲属关系匹配 x m l 文件是树型结构，任何一个结点都不是孤立的，它们之间具有亲属关 系，如父子关系、祖先后代关系、兄弟关系等。在对元素进行匹配时，可以利用 上述关系进行匹配。 例如“e p a r e n t ：表示所有e 结点的父结点元素；“e a n c e s t o r ：， 表示e 结点的所有祖先结点元素。其它的关键词还有c h i l d 、d e s c e n d a n t 、 f o l l o w i n g - s i b l i n g 、p r o c e e d i n g s i b l i n g 、a n c e s t o r - o r - s e l f f o l l o w i n g 、p r o c e e d i n g 等。 5 条件匹配 条件匹配就是利用一些函数的运算结果的布尔值来匹配符合条件的结点。这 些函数通常包括结点函数、字符串函数、数值函数等，例如l a s t ( ) ，p o s i t i o n ( ) 等。 2 5x m l 文档树编码 目前提出的x m l 编码主要分为区间编码【1 5 】【3 5 - 3 7 1 、前缀编码【3 8 4 1 1 和素数编码 【4 2 】三种。按照编码是否支持x m l 文档中结点的动态插入、删除，x m l 编码又 可以分为静态编码和动态编码两种( 动态编码：当插入或删除x m l 结点时，不需 要对已有的x m l 结点进行重新编码) 。 2 5 1 区问编码 区间编码方法采用深度优先遍历的方法给文档中的每个结点赋予一对整数 值( s t a r t ，e n d ) ，使它们形成的区间包含其后代结点的编码范围，这样对结点的结 构关系的判断等价于区间包含关系的判断。 在z h a n 9 1 5 】编码中，每个结点的编码为多元组( d o c n o ，b e g i n ：e n d ，l e v e l ) ， d o c n o 为x m l 文档号，b e g i n 为前序遍历时第一次访问到x m l 结点时的序号， e n d 为前序遍历时最后访问到该x m l 结点时的序号，l e v e l 为结点的深度。对于 1 3 x m lt w i g 查询优化研究 文本结点，它的b e g i n 与e n d 的值相等。对任意的两个x m l 结点u 和v ，u 是v 的祖先结点当且仅当u d o c n o - - v d o c n o ，u s t a r t v s t a r t 而且v e n d u e n d ；u 是v 的父亲结点当且仅当u d o c n o - - v d o e n o ，u s t a r t v s t a r t ，v e n d e l = b 4 ，e 2 - - b 2 ，m a x = l ，m i n = 2 ，e m a x = b 4 输出结果( a 2 ，b 2 ，c 3 ) 7d m b ( d ，b ) = ( b 4 ) ，m b ( c ，b ) 2 1 2 i e l = b 4 ，e 2 = o ，m a x = 2 ，m i n = l ，e r r l a x = 1 2 i 输出结果( a 1 ，b 4 ，d 4 ) 由表3 1 可知第一阶段的查询结果为：( a 3 ，b l ，d 1 ) ，( a 3 ，b l ，c 1 ) ，( a 4 ， b 3 ，d 2 ) ，( a 2 ，b 2 ，d 2 ) ，( a 4 ，b 3 ，d 3 ) ，( a 2 ，b 2 ，d 3 ) ，( a 4 ，b 3 ，c 2 ) ，( a 2 ，b 2 ， c 3 ) ，( a l ，b 4 ，d 4 ) ，然后进行第二阶段的合并连接运算，如t j f a s t 主算法第l o 行所示，最后对于t w i g 查询模式( a ，b ，c ，d ) 的匹配结果为( a 3 ，b l ，e l ，d 1 ) ， ( a 4 ，b 3 ，c 2 ，d 2 ) ，( a 4 ，b 3 ，c 2 ，d 3 ) ，( a 2 ，b 2 ，c 3 ，d 2 ) ，( a 2 ，b 2 ，c 3 ，d 3 ) ， 无用的中间结果为( a l ，b 4 ，d 4 ) 。 3 3