（计算机应用技术专业论文）基于结构连接的xml查询处理与研究.pdf

摘要 x m l 自从1 9 9 8 年由w 3 c 提出以来，就迅速的成为i n t e m e t 上用于数据表 示和数据交换的标准。x m l 文档大量涌现，x m l 的有效管理受到广泛关注。由 于x m l 数据具有不同于传统数据形式的树状结构，使得传统的数据库技术不能 有效地发挥作用，因此需要针对其特点研究新的处理方法。为了解决x m l 路径 查询处理中的关键技术问题，为较大规模的x m l 查询应用提出切实可行的解决 方案，本文给出了x p a t h 查询的系统框架，定义了系统可以处理的x p a t h 的语法， 实现了一个x m l 文档的查询处理系统。 作为x m l 查询处理的核心操作，结构连接操作的高效实现是提高查询处理 性能的关键所在。本文针对结构连接操作的高效问题，在x m l 数据区间编码的 基础上，把基于过滤的小枝结构连接技术应用到查询系统中。把源路径以及路径 包含的概念引入过滤算法，减少了p s e t 集合中的路径数目。对使用过滤算法与 不使用过滤算法的整体小枝连接技术进行了实验比对，试验结果显示使用过滤算 法的整体小枝连接具有更好的性能。 现有的x m l 结构连接算法都是在节点编码的基础上提出的。目前，各种节 点编码方式及其对应的结构连接算法很多。本文针对多种结构连接算法进行了系 统的总结和比较，并分析了各种算法的不同性能。 关键字：x m l ，x p a t h ，编码方法，过滤，结构连接 a b s t r a c t x m lh a sb e c o m en e wc r i t e r i ao fd a t ar e p r e s e n t i o na n de x c h a n g ei ni n t e r n e ta n d i th a sb e e na c c e p t e di nm a n yf i e l d ss i n c ei tw a sp u tf o r w a r db yw 3 ci n19 9 8 t h i si s c r e a t i n gan e ws e to fd a t am a n a g e m e n tr e q u i r e m e n t si n v o l v i n gx m l t r a d i t i o n a l d a t a b a s et e c h n o l o g i e sc a n tw o r ke f f i c i e n t l yo w i n gt ot h et r e e l i k en a t u r eo fx m l d a t aa n dn e wa p p l i c a t i o ne n v i r o n m e n t n e wt e c h n o l o g i e ss p e c i a l l yd e s i g n e df o rx m l d a t aa r en e e d e dt op r o c e s sx m ld a t ae f f i c i e n t l y i nt h i sp a p e r , w ef o c u so nt h ep a t h e x p r e s s i o np r o c e s s i n g s u c ht h a tt h ek e yi s s u e si nt h el a r g e s c a l ex m lq u e r y a p p l i c a t i o nc a nb es e t t l e db yf e a s i b l ea p p r o a c h e s w ep r o p o s eas y s t e mf r a m e w o r ko f x p a t hq u e r y , d e f i n i n gt h ex p a t hg r a m m a rt h a tt h es y s t e mc a nd e a lw i t h ，g i v i n gt h e q u e r yp r o c e s s i n gs y s t e m a st h ec o r eo p e r a t i o no fx m lq u e r yp r o c e s s i n g , t h ee f f i c i e n ti m p l i m e n a t i o no f s t r u c t u r a lj o i ni st h ek e yt oi m p r o v ex m lq u e r yp r o c e s s i n g b a s e do nt h er e g i o n n u m b e r i n gs c h e m eo fx m ld a t a w el e d i n t of i l t e r - b a s e dt w i gs t r u c t u r a lj o i n t e c h n o l o g y d i f f e r e n tf o r mp r e v i o u sa l g o r i t h m s ，f i l t e r a t i o na l g o r i t h mf i l t e r st h eq u e r y p a t t e r na n dt h ed a t as e tw i t ht h ep a t he n c o d e di n f o r m a t i o n ，l e a v i n gt h ee l e m e n t st o j o i nt h es t r u c t u r a lj o i n t h e n w eu s et w i gj o i na l g o r i t h mf o rt h e s ee l e m e n t s w e i n t r o d u c et h ec o n c e p to fs o u r c ep a t ha n dp a t hc o n t a i n m e n t ，d e c r e a s i n gt h ea m o u n to f p s c t w eh a v ac a r r i e do u ta ne x p e r i m e n tt oc o m p a r et h et e c h n o l o g y sa b o u tw h e t h e r u s i n gf i l t e r i n ga l g o r i t h mo rn o t t h er e s u l t so fo u rc o m p r e h e n s i v ee x p e r i m e n ts h o w t h a tt h et w i gj o i na l g o r i t h mw i t hf i l t e r i n gp r o c e s sp e r f o r m sw e l lb o t hs y n t h e t i ca n d r e a l - w o r dd a t a s e t s ，a n dh a sg o o ds c a l a b i l i t y t h ex m lc o n t a i n m e n tj o i na l g o r i t h mi sp r o p o s e db a s e do nx m le n c o d i n g m a n yr e s e a r c h e r sh a v ap r o p o s e da l lk i n d so fe n c o d i n ga n dr e l e v a n tc o n t a i n m e n tj o i n a l g o r i t h m s w es u mv a r i o u ss t r u c t u r a lj o i na l g o r i t h m su p a tl a s t ，w ea n a l y s et h e p e r f o r m a n c eo ft h e s ea l g o r i t h m s k e y w o r d s ：x m l ，x p a t h ，n u m b e r i n gs c h e m e ，f i l t e r , s t r u c t u r a lj o i n 天津师范人学顾i ：学位论义 独创性声明 本人卢明所早交的论文是我个人在导师指导下进行的研究：i ：作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得苤鲞竖堇叁堂或其它教育机构的学位或证j 侈而使朋过的材料。 与我一同j i ：作的同忠对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：蜂 日期：丝址 学位论文版权使用授权书 本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文 的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇 编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：一通缉吐导师签名：堑亚 灭津师范人学硕i ：学位论义 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 ) 已经成为一种网上通 用的数据存储与信息交换的标准格式。x m l 由于自身的规范性、灵活性、可扩 展性和强大的语言表达能力，被普遍应用于诸多领域，如数字图书馆、电子商务 等。近年来，w e b 上已经出现了大量的x m l 数据，但是，在今天的w 曲环境中， 大的w e b 站点和搜索引擎却主要用文件系统来存储信息，利用信息检索技术来 检索静态的h t m l 页面，效率低下而且极不准确。随着w e b 页面数量的快速增 长，新的w e b 应用要求w e b 能够管理动态的内容，而且能在大量的w e b 信息中 准确、快速地找到所需信息。由于x m l 本身具有结构信息，可以很好的满足这 种需求：使用类似于数据库的查询语言的方式来检索x m l 文档，搜索引擎的功 能将变的更加强大和准确。 随着x m l 文档数据的同益增多，其查询处理将是一个重要的课题，为此 w 3 c 制定了x m l 文档的查询标准x p a t h ，由于x m l 文档内的元素之间有结构 关系，可以形成一个树状结构，从该树中可构成条路径用来表示x m l 文档内 的元素，这称为路径表示法( x p a t he x p r e s s i o n ) 。因此本篇论文将着重于x p a t h 的处理，探讨如何做数据查询。 1 2 国内外相关研究及本文贡献 近年来，x m l 数据应用越来越广泛，如何在众多的x m l 文档中寻找使用 者所需要的文件与数据，也成为了一个很重要的议题。由于x m l 文档如同h t m l 文件一样，是属于文本格式的，所以很多研究者延续信息检索( i n f o r m a t i o n r e t r i e v a l ) 的技术，希望能取出包含特定关键词( k e y w o r d ) 的x m l 文档。在【l 】 中，作者将x m l 文档内属于数据的部份看作字词，将每个字词去除同样的前缀 字尾，使字词的数量降到最低，再用所获得的字词来建立索引。如此可减少索引 的大小，进而缩短了索引与查询的时间。另外，除了单一的关键词外，在x m l 文档内也可利用x p a t h ，来取出位于特定位置或符合限制条件的数据。有些研究 者特别针对无法预先取得的大量数据，像是股票数据等，做符合x p a t h 叙述的信 息检索。【2 中的作者将多条x p a t h 依照节点来转换成s u b s t r i n g ，然后再将 天津师范人学硕i j 学位论义 s u b s t r i n g 当做关键词，使用x t r i e 来建立索引结构，之后便可以此x t r i e 来实时 的过滤数据。 上述方法主要着重在筛选出包含特定数据的文件，不能快速地处理一般化的 查询语句。所以很多研究者利用了目6 订在关系数据库使用的查询处理技术，以期 对x m l 文档作复杂的限制与特定数据的选择。最基本的查询处理方法，是各自 选出符合限制的节点后，再依照它们在x m l 文档结构上的关系去做结构连接。 但是结构连接是费时且花费空间的方法，所以很多研究者提出编码或是索引的方 式，以减少不必要的连接次数。 在编码方面，研究 3 】中，作者将x m l 文档上的每一个节点x 给予两个编码 数字，分别对应到节点的起点与终点，代表x 节点所包含的范围。若节点x 是y 的祖先，则x 所描述的范围会包含y 所描述的范围。我们让x 所描述的范围有剩 余的空间，于是若x 要新增子节点，就可以不必修改其范围而可继续使用。【3 】 中同时也提供了一系列的算法与索引，来做节点问的结构连接。研究 4 】则进一 步利用b + 树为节点的起点编码做了索引，并且加上s i b l i n gp o i n t e r 等指针来指向 标签名称一样的节点。如此在做两元素的结构连接时，可以先将对应到两元素的 节点各自放到两个串行内，并按照它们的节点起点编码来排序，然后就可通过指 针略过不用参与结构连接的节点，从而加速结构连接的速度。研究【5 】亦考虑了 更新节点的问题，所以不采用绝对位置方式的节点编码，而是让节点编码的起点 与终点是相对于自己父节点编码的起点与终点。采用此种相对位置的节点编码， 当有节点要更新时，所影响到的节点，只有要被更新节点的祖先以及这些祖先的 兄弟节点。依照此特性将相对位置的节点编码聚集起来储存在一起，那么在更新 时会有较佳的i o 效率。 研究 6 】则是提出多种索引来加快查询的速度，包括了针对节点名称的n a m e i n d e x 、对节点值做索引的v a l u ei n d e x 、与加快x p a t h 查询的p a t hi n d e x 。在这篇 论文中，作者首先利用n a m ei n d e x 与v a l u ei n d e x ，将输入的x p a t h 分割成两个 部分，再利用p a t hi n d e x 处理其中一部份取出答案，然后再作另一部分，重复的 做下去直到找到答案。因为将把查询句分解成数个小查询句，进而缩小了查询范 围，同时因为小查询句之间互不影响，可利用平行处理来加快运算。 由于关系型数据库已成为数据库的主流，因此有许多研究者对于如何将 天津帅范人学硕l ：学位论文 x m l 数据存入关系型数据库中，相继提出不同的做法。这罩不做深入地探讨。 本文主要贡献在于： ( 1 ) 本文围绕“基于结构连接的x m l 查询技术”这一主题展开，对有代 表性的x m l 结构连接算法进行了深入的研究。在综述了x m l 结构连接的概念、 分类和编码方式等的基础上，详细的分析比较了多种x m l 的结构连接算法。阐 述了已有算法在性能上的差异。 ( 2 ) 把路径过滤应用于查询处理中，并验证了其有效性。实现了基于过滤 的x p a t h 查询转换方法。 ( 3 ) 在比较了各种索引方法和结构连接算法后，本文实现了使用路径过滤 的结构连接技术的查询处理系统。利用真实数据集d b l p 和x m a r k 及合成数据 集x o r d e r 进行查询实验，并通过结果比较和性能分析获得了结论。实验结果表 明使用路径过滤的结构连接方法可以有效地提高x m l 查询的效率。 1 3 本文主要内容及结构 论文共分为七章： 第一章介绍x m l 的发展和特点，阐述了国内外学者对x m l 的相关研究。 第二章论述了x m l 查询的相关技术，探讨了树模式匹配模型在x m l 查询中的 应用，着重介绍了x m l 路径查询处理技术，并对x p a t h 语言作了介绍。第三章 介绍了x m l 数据编码和结构连接的基本概念。对现有的有代表性的结构连接技 术进行了总结和研究。第四章介绍了路径过滤技术，详细阐述了基于过滤技术的 x m l 结构连接算法。第五章介绍x m l 查询系统的设计过程。包括系统组成、 功能，系统能处理的x p a t h 语句的范围以及系统每部分具体的数据结构，算法。 第六章以实验方式讨论了x m l 查询系统中的关键技术的有效性，并分析了其代 价。第七章对本文的研究工作作了总结，指出存在的问题及今后的工作。 3 天漳师范人学顾j j 学位论文 第二章x m l 查询 2 1x m l 文档 x m l 是e x t e n s i b l em a k e u pl a n g u a g e ( 可扩展标记语言) 【7 1 的缩写，和 h t 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 ) 的子集。但 是h t m l 的标签主要是显示输出用，而x m l 则允许定义标签，进而使用自定的 标签来说明数据的意义。x m l 文档是一种简单、弹性很大的纯文字格式文档， 如图2 1 的x m l 文档示例所示，通过适当的自定义标签可以表达某一期数据库 期刊内的论文数据，譬如论文标题、作者与关键词等。 j + 在图2 1 中第l 0 1 行的o i p 元素，是这一篇x m l 文档的根元素( r o o t e l e m e n t ) ，一篇x m l 文档内只能有一个根元素。图2 1 中l 0 2 行的v o l u m e 元 素包含在o i p 元素下，它是o i p 的子元素( c h i l de l e m e n t ) ，相应地，o i p 就是 v o l u m e 元素的父元素( p a r e n te l e m e n t ) 。在图2 1 的第l 0 8 行与第l 0 9 行的a u t h o r 元素同属于一个父元素a r t i c l e 之下，这两个a u t h o r 元素互为兄弟元素( s i b l i n g e l e m e n t ) ，这表示它们有共同的父元素，并且它们的元素名称相同。 一个元素必须包含开始标签与结束标签，标签成对出现并且不可交叉。这样， 元素之间就呈现出一种树状结构来，如图2 2 的x m l 树状结构图所示。 在图2 2 中，以矩形来表示x m l 文档内的实体元素，箭头是从实体父元素 开始指到实体子元素结束，代表它们的父子关系；以椭圆来表示值的部分，实体 元素与值之间以线段相连代表该元素拥有此值；另外我们称带有值的实体元素为 叶元素( l e a fe l e m e n t ) 。通过以上的规定之后，这篇x m l 文档就可以称做格 式规范( w e l l f o r m e d ) 的x m l 文档。 由图2 2 的x m l 树状结构图，我们可以看出x m l 文档的数据模型是一棵 有根，有序，节点上有标签的树。树中每个节点对应x m l 文档中的一个元素， 树的边表示元素之间的父子关系。兄弟节点问有序，且兄弟节点问的顺序隐式地 定义了树中节点的总体顺序，为深度优先，从左至右的遍历顺序。进一步，x m l 数据库就是由这样一些有根，有序，节点上有标签的树组成的森林。 4 天津师范人学硕i ：学位论文 乙0 l l 0 2 2 7 l 0 3 4 一0 4 l 0 5 j o i n 一0 6 二0 7 t w i gj o i n s 2 0 8 b r u n o 埝9 k o u d a s 二1 0 t w i g 一1 l 二1 2 二1 3 s t r u c t u r a lj o i n s 二1 4 c h i e n l 1 5 n u m b e r i n gs c h e m e 二1 6 二1 7 二1 8 二1 9 e n c o d e 2 2 0 2 2 1 s t o r i n ga n dq u e r y i n g 2 2 2 v i g l a s 上3 d e w e y 2 4 2 5 2 6 上7 上8 2 9 。3 0 2 1 1 文档类型定义d t d 图2 ix l l 文档示例 因为x m l 文档允许使用自定义的标签名，且元素问存在着树状结构关系， 所以，为了确定x 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 ) 来检查，称为验证( v a l i d 时) 。图2 1 的x m l 文 档，可用图2 3 的d t d 示例，来验证是否符合d t d 所要求的标签名称与结构关 系。 d t d 可以是一个完全独立的文件，也可以在x m l 文档中直接设定。所以， 天津师范人学倾i ：学位论文 d t d 分为外部d t d ( 在x m l 文档中调用另外已经编辑好的d t d ) 和内部d t d ( 在x m l 文档中直接设定d t d ) 两种【8 】。d t d 具有如下优点：d t d 使得x m l 文档保持一致；d t d 可以共享；d t d 提供了对x m l 语汇的形式化和完整的定 义；每个x m l 文档有单个的d t d 来限制。 在d t d 中，使用e l e m e n t 来定义元素，如图2 3 的第l 0 1 行定义o i p 元 素，其下有v o l u m e 、n u m b e r 、s e c t i o n 等三个元素。图2 3 的第l 0 2 行说明v o l u m e 元素所存放的数据为可解析的文字数据# p c d a t a ( p a r s a b l ec h a r a c t e rd a t a ) 。需 要特别注意的是图2 3 的第l 0 1 行，o i p 元素下的s e c t i o n 元素，木代表s e c t i o n 子元素可不出现或重复出现一次以上。 图2 2x m l 树状图 6 天津帅范人学顾i ：学位论文 l 0 1 l 0 2 l 0 3 l 0 4 l 0 5 l 0 6 l 0 7 l 0 8 l 0 9 幽2 3d t d 示例 2 1 2x m l 编程接口：d o m ，s a x 和j d o m 2 1 2 1d o m 简介 d o m 是相当复杂的a p i ，将x m l 文档表示成树型结构，所有的后续操作 都是对这个树型结构的x m l 文档执行，如增加或删除元素。不同于s a x ，d o m 是读写a p i ，可以分析现有的x m l 文档和生成新的x m l 文档。每个x m l 文档 表示为一个d o c u m e n t 对象。搜索、查询和更新文档时，调用这个d o c u m e n t 对 象及其包含对象的方法。这就使得d o m 更适合随机访问原文档中的各个不同部 分。 除了数据的表达方式外，d o m 也提供了在文件中移动的方法，如 t r e e w a l k e r ( ) 和n o d e l t e r a t o r s ( ) 。t r e e w a l k e r ( ) 中包括f i r s t c h i l d ( ) 和n e x t s i b l i n g ( ) 等方法，让d o m 文件可以像树一样被操作。n o d e l t e r a t o r s o 贝j j 提供了完全相反的 操作，它把d o m 看作一个平面文件，通过n e x t n o d e 0 和p r e v i o u s n o d e 0 等函数 来取得其中的内容。 由于d o m 把整个x m l 文档树放在内存中，因此便于操作，支持删除、修 改、重新排列等多种功能。但将整个文档调入内存，却浪费了时问和空间，因为 文档中包括很多无用节点。因此，d o m 适用于一旦解析了文档还需多次访问这 些数据并且有充足的硬件资源如：内存、c p u 的情况。 2 1 2 2s a x 简介 s a x 是w 3 c 推荐的最为完整的x m la p i 规范，它是事件驱动的a p i 。s a x 提供了一种对x m l 文档进行顺序访问的模式。当使用s a x 解析器对x m l 文档 7 天津帅他人学颂i j 学位论义 进行解析时，会触发一系列事件，并激活相应的事件处理函数，从而完成对x m l 文档的访问，因此，s a x 接口也被称为事件驱动接口。 大多数s a x 实现都会产生以下类型的事件： ( 1 ) 在文档的开始和结束时触发文档处理d o c u m e n t 事件。 ( 2 ) 在文档内每一x m l 元素将要被解析的前后触发元素e l e m e n t 事件。 ( 3 ) 在处理文档的d t d 或s c h e m a 时产生d t d 或s c h e m a 事件。 ( 4 ) 产生错误时触发错误事件，用来通知主机应用程序解析错误。 d o m 结构占用内存较多，并且不太适合流式应用程序。s a x 解析器提供的 是一种对x m l 文档的顺序访问机制，对于已经解析过的部分，不能再倒回去重 新处理。s a x 解析器在实现时，只是顺序地检查x m l 文档中的字节流，判断当 前字节是x m l 语法中的哪一部分，检查是否符合x m l 语法并触发相应的事件。 对于事件处理函数本身，要由应用程序自己来实现。同d o m 解析器相比，s a x 解析器对x m l 文档的处理缺乏一定的灵活性。在可读性上，s a x 也不如d o m 操作清楚简单。因此在文档不是特别大的时候，还是采用x m l 方法比较合适。 s a x 适用于只需x m l 文档的少量内容，很少回头访问且机器内存少的情况。 2 1 2 3j d o m 简介 j d o m 也是一种解析x m l 的a p i ，它是一种基于j a v a 2 的完整a p i ，同样 具有s a x 的高效，快速的特点，而且还可以像d o m 那样从整体上操纵文档， 提供一种比d o m 更简单的生成和访问元素节点的方法。j d o m 利用纯j a v a 的 技术对x m l 文档实现解析、生成、序列化以及多种操作。它直接为j a v a 编程 服务，利用更为强有力的j a v a 语言的诸多特性( 方法重载、集合概念以及映射) ， 把s a x 和d o m 的功能有效地结合起来。在使用设计上尽可能地隐藏原来使用 x m l 过程中的复杂性。j d o m 可以将d o md o c u m e n t 对象转换为j d o m d o c u m e n t 对象，这样就可以将现有d o m 程序的输出转为j d o m 程序的输入。 而且在从磁盘或网络读取x m l 数据流时，使用s a x 产生j d o m ，这样可以避 免两种不同表示法两次建立内存树的开销。j d o m 适于当要实现的功能比较简单 如解析、创建等的情况。 2 2x m l 查询技术 近年来，随着x m l 相关技术的广泛和深入研究，x m l 查询已经具备了坚实的 天津师范人学硕f ：学位论文 技术基础。传统数据库的大部分成熟技术可以比较方便地移植到x m l 数据库查 询上来。半结构化数据查询技术方面的研究成果也可以直接应用于x m l 查询。 更为重要的是，w 3 c 已经为x m l 定义了模式、查询语言和查询形式语义等数据 库才具备的特征，这就为采用类似于s q l 查询关系数据库的方式进行x m l 查询 奠定了基础。 但是由于x m l 数据自身的特点及其与传统数据模型的差别，x m l 查询在 理论上和实现上都还存在很多难点。随着x m l 应用范围的扩展以及x m l 信息 的同益普及，人们对x m l 信息处理的能力也提出了更高的要求。如何实现高效 的x m l 查询处理也因此成为人们关注的研究课题。 2 2 - 1x m l 查询语言( x m lq u e r yl a n g u a g e ) x m l 查询语言是一种定位x m l 文档中数据元素位置的方法。它提供一种 在一个或多个x m l 文档中查找特定对象的方法。现在已提出了许多x m l 查询 语言，如：l o r e l 13 1 、x m l q l 1 4 1 、x m l - g l 1 5 1 、x p a t h 9 、q u i l t 16 1 、x q u e r y t l 7 1 等。这些语言的共同特点是都使用了j 下则路径表达式并具有从x m l 数据中抽取 信息的能力。用户可以使用正则路径表达式沿着x m l 数据树的任意长的路径进 行导航。 2 2 2x p a t h 的基本语法 x p a t h 是w 3 c 所提出的一个标准，使用x p a t h 可以在x m l 层次结构中快 速定位和提取信息。它的内建函数提供了全面的功能，可以方便的处理数值及文 本数据。 x p a t h 本质上是与具有层次结构的x m l 数据模型相匹配的查询语言。它 可以通过按任何方向浏览树来选择节点，并根据节点的值和位置应用谓词。它还 包括用于基本字符串处理、数字计算和布尔代数的工具。 2 2 2 1 定位路径表达式 x p a t h 使用定位路径表达式来选取x m l 文档中的节点或节点集。定位路 径表达式也简称为路径表达式。定位路径分为相对定位路径和绝对定位路径两 种。每个定位路径表达式都由一个或多个定位步组成，每个定位步之间用“ 9 天津师范人学硕1 j 学位论文 分开。绝对路径表达式以“”开始，它是从文档树的根结点( 即文档结点) 开 始定位路径；而相对路径表达式则直接从某个定位步开始定位路径。 每个定位步都由三个部分组成：轴( a x i s ) 、节点测试( n o d et e x t ) 和谓词 ( p r e d i c a t e ) ( 零个或多个) 。一般形式如下： 轴标识符：节点测试 谓词1 】【谓词2 】 轴标识符和节点测试之间用两个冒号分隔，而每个谓词表达式都包装在中括 号中。两个或多个定位路径表达式可以通过“i ”操作符组合在一起以合并其结果节 点集。 定位路径表达式的计算过程是从左到右计算每一个定位步。每一个定位步的 计算是基于上下文节点集进行的，需要基于它的上下文节点集的每一个节点进行 求值。如果定位路径是绝对的，则初始的上下文节点集中仅包含文档节点；如果 定位路径是相对的，则初始的上下文节点集中包含当前上下文节点( 集) ，它依 赖于表达式使用的位置。第一个定位步的计算是基于初始的上下文节点集进行 的，计算得到的结果节点集将成为下一个定位步计算的上下文节点集。这样，处 理依次对定位路径中的每一个定位步进行，最后的定位步产生的结果节点集就是 该定位路径表达式的结果。下面给出的是x p a t h 的语法描述。 q u e r y ：= p a t h e x p r p a t h e x p r ：= r e g u l a r e x p r t r e g u l a r e x p r i r e g u l a r e x p r ib a s i c e x p rp r e d i c a t e 幸yr e g u l a r e x p r ib a s i c e x p r p r e d i c a t e 宰7 r e g u l a r e x p r r e g u l a r e x p r ：产s t e pp r e d i c a t e 木jr e g u l a r e x p r s t e pp r e d i c a t e ir e g u l a r e x p r ，s t e pp r e d i c a t e 事 。 s t e p ：= n a m e t e s t l n a m e t e s t p r e d i c a t e ：= 【c o m p a r i s o n 】l b a s i c e x p r ：= cc o m p a r i s o n ) il i t e r a l ln u m b e r c o m p a r i s o n ：= a r i t h e x p r 2 - 2 2 2x p a t h 轴和节点测试 x p a t h 定义了几种相对于上下文节点的节点关系。这种关系引用的节点集称 1 0 天津帅范人学顾l j 学位论义 为节点轴。轴用在定位步中，用于指定通过定位步其余部分( 节点测试和谓词) 筛选的初始节点集。而一个定位步的计算先从轴和节点测试开始，产生初始节点 集合；然后再利用各个谓词对初始节点集合进行过滤，得到最后的结果节点集合。 x p a t h 定义了如下1 3 个轴，表2 1 给出了这1 3 个轴及其描述： 表2 1x p a t h 轴 名称描述 s e l f选择上下文节点自身 p a r e n t 选择上下文节点的父节点，如果存在父节点的话 c h i l d选择上下文节点的所有子节点，不包括属性节点和命名空 间节点 a n c e s t o r 选择上下文节点的后裔，直到文档根节点，文档根节点的 a n c e s t o r 轴为空节点集 a n c e s t o r - o r - s e l f 和a n c e s t o r 相同，只是包括了上下文节点本身 d e s c e n d a n t 选择上下文节点的祖先，不包括属性节点和命名空间节点 d e s c e n d a n t o r - s e l f 和d e s c e n d a n t 相同，只是包括了上下文节点 p r e c e d i n g 选择上下文节点之前的所有节点，不包括祖先节点、属性 节点和命名空间节点 p r e c e d i n g - s i b l i n g选择上下文节点之前的所有兄弟节点，如果上下文节点为 属性节点或命名空间节点则此轴为空 f o l l o w i n g 选择上下文节点之后的所有节点，不包括后裔节点、属性 节点和命名空间节点 f o l l o w i n g - s i b l i n g 选择上下文节点之后的所有兄弟节点，如果上下文节点为 属性节点或命名空间节点则此轴为空 n a m e s p a c e 选择上下文节点的命名空间节点 a t t r i b u t e 选择上下文节点的所有属性节点 定位步节点测试的目的是进一步提炼由轴标识符标识的初始节点集。节点测 试可以根据名称或类型从轴节点集中筛选节点。最普通的节点测试根据名称选择 节点，当根据名称标识节点时，选中的节点不仅要匹配提供的名称，而且还要匹 天津师范人学硕l ：学位论义 配轴的节点类型。 2 2 - 2 - 3 谓词( p r e d i c a t e s ) x p a t h 中的过滤器被称作谓词( p r e d i c a t e ) ，写在方括号内。一个谓词作用 在一个节点集上，它被用来查找某个特定的节点或者包含某个指定值的节点。谓 词用于进一步筛选轴标识符和节点测试所标识的节点集。谓词是一种布尔表达 式，用于对当前节点集的每个节点进行测试。对于某个给定节点，如果谓词的值 为t r u e ，则该节点保留在当前节点集中；如果谓词的值为f a l se ，则删除该 节点。 2 3 路径查询的处理 2 3 1 路径查询模式 我们通常习惯用路径表达式来指代路径查询。 x m l 查询语言，例如x p a t h , x q u e r y 都使用节点上带有选择谓词的树模式来 匹配( 抽取) x m l 数据库中相应部分的数据。这个节点上带谓词的树模式也称 为查询模式【l o l 。即针对x m l 数据的路径表达式可以表示为一棵查询树。对于 查询模式中的每个节点，都对应一个选择谓词，该选择谓词针对元素的名字，属 性值或文本值( 字符串) 作出限制。而查询模式中的边或者表示父子关系( 使用“ 来表示) ，或者表示祖先后裔关系( 使用“ 来表示) 。 例如：x p a t h 查询表达式：b o o k t i t l e = x m l a n dy c 舻2 0 0 0 】可表示 成图2 4 ( a ) 所示的树模式，使用该模式可从x m l 数据库中抽取出满足如下条件 的b o o k 元素：( 1 ) 包含子元素t i t l e 且t i t l e 元素具有值x m l 。( 2 ) 包含子元 素y e a r ，且y e a r 元素具有值2 0 0 0 。该例中使用了父子关系边。再如：x p a t h 查 询b o o k t i t l e = x m l a u t h o r = j a n e 】从x m l 数据库中抽取这样的a u t h o r 元素： ( 1 ) a u t h o r 的文本内容是j a n e 。( 2 ) a u t h o r 元素是b o o k 元素的后裔，而作为a u t h o r 祖先的这个b o o k 元素有一个子元素t i t l e ，且t i t l e 的文本内容是x m l 。这个查询 可以表示成图2 4 ( b ) 中的有根树模式。注意到，b o o k 和a u t h o r 元素间使用了祖先 后裔边。 1 2 天津帅地人学顺i ：学位论文 b o o k 瓜 t i t l ea u t h o r x m l j a n e 图2 4 ( a ) 树模式图2 4 ( b ) 树模式 在实际的查询树模式中，通常只有一个节点在x m l 数据中的映射节点是查 询所需要的最后输出结果，其余的查询节点和节点之间的边只是对该节点的约束 限制条件。基于这样的事实，我们给出如下的一些定义。 定义2 2 ：x m l 查询树中存在一个节点n ，x m l 数据中与n 匹配的部分是 查询的最终输出结果，则该节点称为查询的目标节点。 定义2 3 ：在x m l 查询树中，所拥有的孩子节点数目大于一的节点( 1 i p 产生 路径分叉的节点) 称为分支节点。 定义2 4 ：在x m l 查询树中，如果节点上除了针对元素名的选择谓词条件 ( 即标签) 外，还定义了针对元素值或元素属性值的谓词条件，这样的节点称为 值谓词节点。 图2 5 对定义2 2 2 4 中的三种节点作了注释。 2 3 2 传统的路径查询的计算方法 x m l 查询语言的共同特点是利用路径表达式在x m l 文档中进行导航。而 针对路径表达式的处理问题，已经进行了大量的研究工作【i l 】。在树状的x m l 数 据中匹配路径表达式的基本方法就是对数据进行导航式的遍历。即沿着树中节点 之间的边对x m l 数据的层次结构进行遍历，从而完成路径表达式的匹配，得到 符合查询条件的节点。 最直接的处理路径查询表达式的方法就是遍历整个x m l 文档，或者自顶向 下，或者自底向上【l2 1 。当使用自顶向下的方法从某元素丌始查询时，需要遍历 该元素通往叶节点的所有可能路径。并且需要对x m l 数据库中所有符合此选择 谓词条件的节点重复此操作。如果丌始查询的元素恰好是x m l 树的根，则整个 树结构都需要被遍历。因此，这种方式的效率通常是非常低的。相比较而言，采 用自底向上的方法则更为简便，因为从树中某元素的向上路径只有一条。但当符 盯 啪k 呷i 加 0 的 k l t m i i 煳 天津师范人学顾f j 学位论文 合选择谓词条件的节点数目很大而符合路径表达式的路径很少时，此遍历方式的 代价同样会很高。因此，可以同时按照自顶向下和自底向上两种方法进行遍历， 并在路径表达式的中间位置交汇，这称为混合方式。当路径上某节点的入度很大 而符合选择谓词条件的节点很少时，该方式可以达到最优。虽然混合方式针对某 些数据情况能够利用自顶向下和自底向上两种方式的优点，但它的有效性并不能 够在任何情况下都得到保证。特别当数据量很大时，此方式的效率同样很低。 总的说来，导航的方式简单直接，但执行效率不能得到保证，尤其是在大数 据量的情况下。基本导航式遍历方法的低效性促使了新的路径查询计算策略的提 出，类似于关系数据库中“一次一集合 1 3 】【1 0 】的处理策略逐渐获得了人们的认 同。该策略在元素节点一级来处理x m l 数据，利用结构连接操作来计算路径约 束条件。 2 3 3x m l 路径查询的分解 图2 5x p a t h 查询树 对x m l 数据的查询方式应当比传统的数据库所提供的方式更加灵活和丰 富，不但查询内容，而且查询结构。 x m l 查询的核心是x p a t h 路径表达式。一个复杂的x p a t h 路径表达式查询 能够被分解成几个简单路径表达式。这样，对复杂x m l 查询模式的匹配就可以 1 4 天津师范人学硕i ：学位论文 降低为对含有单一连接操作符的单个二元结构关系( 简单路径表达式) 的处理。 简单路径表达式的一种计算方法就是逐步结构连接法【l o 】1 3 0 1 ，即把这些简单路径 的计算转换为一系列的结构连接操作，之后，再把这些简单路径表达式的计算结 果合并起来产生给定复杂x p a t h 路径表达式查询的最后结果。 这种路径分解的查询处理方法吸取了关系数据库中处理查询的思想，试图实 现“一次一集合”的查询执行。采用这种方法就解决了“一次一元组”的导航式 遍历方法所存在的低效问题。 在这样的查询执行策略中，元素节点编码和结构连接操作扮演了重要的角 色。借助元素节点编码可以快速判断元素节点之间的结构关系，使得结构连接操 作成为可能。所谓的结构连接操作【1 0 】，就是对给定的潜在祖先( 或父亲) 节点集合 和后裔( 或孩子) 节点集合，计算两个集合中节