（计算机软件与理论专业论文）xml模式树匹配查询算法的研究与改进.pdf

山东大学硕士学位论文 摘要 咀。作为w 曲发展所带来的新技术中的代表，逐渐成为了学术界和工业界 所关注的焦点。帆是一种自描述、可扩展的标记语言，广泛地用于w 曲环境 下数据的表示和共享。要搭建各种基于沮。的应用，必须提供处理咀。数据 的核心技术来高效地生成、查询、过滤、变换皿，数据。由于沮。数据具有 不同于传统数据形式的特点，使得传统的数据库技术不能有效地发挥作用，因此 需要针对其特点研究新的处理方法。 由于帆文档有类似树状的结构，所以和文件路径类似的路径查询表达式 是咀，数据查询和过滤的基础，同时咀，查询也指定了那些在某些特定的树 结构关系上的选择谓词的样式。原始的) 0 咀树结构关系是父子关系或者是祖先 后代关系，在) m 几文档中发现这些匹配关系是) m 几查询处理的核心操作，在 沮。文档中找到所有查询模式树的匹配是咀。查询代价估计中的核心问题， 在本文中重点讨论了模式树匹配的查询优化问题。 本文详细探讨了一种典型的结构化连接算法1 锄gj o i i l 算法，并针对其存在 的不足提出了一种基于c 仃e e 索引的模式树匹配算法- p a t t 哪m a t c h 算法。通过具 体分析可以看出，与1 锄g j o i n 算法相比，p a n e n l m a t c h 算法能够在咀。文档中 直接找到一个查询模式树的匹配结果，不会产生无用的中间结果集，而且所有的 中间结果集在堆栈中保存起来，通过连接运算能够很方便地形成最后的查询匹配 结果，提高了查询匹配的成功概率。 本文首先介绍了模式树匹配算法的研究背景和研究现状，回顾了结构化连 接算法的研究成果，接着对咀。查询语言和v 儿索引进行了详细的说明。然 后引入了模式树的概念，并结合具体算法喇gj o i i l 探讨了目前结构化连接算法 的缺点，这类算法容易大量无用的中间结果或者对一些子模式树进行重复匹配， 下面给出了改进算法p 甜t e m m a t c h ，并通过具体的性能分析阐述了算法的优点。 最后对论文的研究工作和成果进行一个总结，指出了其中的不足，并对今后进一 步的工作进行展望。 关键词：) 口诅。；c 仃索引；模式树匹配；咀。查询估计；路径概要 山东大学硕士学位论文 a b s t r a c t x 。( e x t 觚曲l em a r k 叩l 越g _ i l a g e ) h 私b 啪m e1 l l ef o c 懈o f 磷哪c h 锄d i n d 峭仃i a lc o m m i l i 石器a st h er 印嘲e n t a t i v eo f n e wt e d m o l o 百铭t i l ew 曲x 一i s as e l f - d e s c r i b e da n df l e 五b l ed a 协f o n n a ta n di sf h s te m e 西n g 嬲t l l ed o m i i l a m s f 锄d a r df o rf 印n t h l g 锄d 既c h 锄舀n gi n f o 册a l i o v e rt l l ei n t e m e t t o 伽f i ui 协 p o t 踟t i a lt 0b l l i l de f f 6 v ed i s m b u t e dc o m p 妇gp l a 饪b 眦锄dw e ba p l p l i c 撕。璐，w e n e e de f 宅c t i v e 锄d 锄c i 锄t l yq u e 哆锄df i l t e r i n gt 1 1 i l i q u e st o 懿仃a 肚，s y n l l l e s i z e 锄d 锄a l y z e1 1 1 e i rc o n t 吣r a d i t i o n a ld a t a | b 豳et e c 岫o l o 百翳咖t 、哟r k 桶c i e n t l yo 、】l i i n g t om e 仃e e l i k en 砒l l r eo f ：n 仉d a t a 趴dn e wa p p i i c 鲥o n 衄v i 砌衄啪tn e 、 r t 。c h n o l o 画豁s p e c i a l i yd e 啦皿e d6 玎ld a l aa e d e dt op r o c e 嚣x m ld a t a e m c i 跚t l y q u e 黟i so n eo ft l l em o s ti m p o n a n ti s s u 嚣i 1 1d a l ap r o c e 鲻i i l gp a m 唧r e s s i o ni s 1 量增c o r eo f 咀。q u e i y 锄df i l t e i i n gl 锄g u a g e ，h o w 幻e 曲c t i v e 肌de 街c i n y e v a l u a _ t ep 抽唧r e s s i o n sp l 掣ak 锣r o l e ：j ( m lq u e r i 嚣1 y p i c a l l ys p e c i 如p 毗咖so f s e l e c t i o np r 耐i c a t e so nm i 】1 t i p l ee i e m 锄t sm a th a v es o 眦s p e d f i e d 订e e 蛐m c t l l d r e l 甜i o n s h i p s 1 h ep r i i l l i t i v e 慨s t n l c t i | r e d 槽l a 土i o n s h i p s a r ep a 姗t - c l l i l d 锄d 锄c e s t o r - d e s c d 锄t 肌d 丘n d i n ga l lo c c i l r r c 韶o f 协嚣er e l a l i o n s l l i p si i l 锄x j d a t a b 罄ei sac o r eo p e 枷0 nf o r 沮q u e r yp r o c e 韶i n g f i n d i i l ga l ld i s t i n c tm a l c h i n g o f 也eq u e r y 仃e ep a 撕mi st h e r eo p e r 撕o f x m lq u e r ye v a d u 撕o n t h e 酬s t e l l tm e t l l o d sf o r 仃p a t 懈mm 种c h i n ga md e c o m p o s i t i 伽一m a t c l l i n g - m e r g i n gp r o c 嚣s e s ，s u c h 罄t 嘶gj o i na l g o r i t h m w h i c hm a yp r o d u c em 躯s i v e u s e l e 褐i n t e r m e d i a l er e s d i to rr e ( 她i er 印e a t e dm a 土c _ 1 1 i n go f m es u b - p 戤t e r n s t i l i s 1 l i e s i sp r o p o s e san e 虹b l e 仃p a t t e mm a t c l l i n ga l g o r i m mc a l l e dp a t t e i m 咄i 甜lt of m d a l ld i s 6 n c tm a t d l i n go fa q u e i y 仃p a t f e md i r e c t l y t h ep ；m 既i l i 讧a t c ha l 窘o r i 也md o 嚣 n o tp r o d u c e 粕yl l s e l 器si n 锄_ i i l e d i a t ef e s i i l 住狮dt l l e 丘n a lr e s l l i 乜a r ec o m p t l y c o d e di ns t k s ，丘d m 、】i l = h i c ht i l e 唧i i c i tr 印r e s 即t a l i 啪b ep r o d l i c e d 嘶c i e i l t l y h il l l i s p a p e r ，w ef i r s ti 1 1 仃o d u t l l eb k 掣饥m do f 仃e ep 砒t e mm a t c i l i n g i i 山东大学硕士学位论文 a l g o r i t l l m 缸dt t l er e a r d l 枷吼懈m d i c so fs t m c t l l m lj o i n sa l g o r i m m 湖d l y t h i s p a p e r 西v e sad e t a i l e dd e s 耐如o no f 沮。q u e 黟l 锄g u a g e 趾d ) m 几i i l d 懿f u 血e r l n o f e t l l r o u g hp a n i c l | l a l l y 锄a l y 五n gar 印r 皓就删v ea l g o f i m m 删gj o i l l ，w e 捌v 舒 l o 侣o f 出! t e c t s 行咖p r 器t 劬m c t 眦mj o i l l sa l g o f i l l l m ，w l l i c hc a n 删ti nm 越s i v e u l 髓s 硫e m l e d i a t e 螨l | l to rr 印e t i 石o no fs o m e 飘l b 一臼p a n 哪m 融i n g b a d 血i s ，w ep r o p o s 髂ab n do fi m p v e da l g o r i t l i m - p a t t e m m a l c l l 锄de l a b o 埔：t e st l l e a l g o r i t l l ma d v 锄t a 喀e sl 量l r o u g ht t l eo 叫c r e t ep e 0 珊锄c ea n a l y s i s a tl a 观w e 训酷 o nas 咖1 i i l a | yo ft h i s p a p e r ，p o i i l t e so l l tt l l es h 酬n l i n 擎o fp a t t e m m a t c h 锄d p r o s p e c t st 1 1 ef i l n l l e rw o r k k e yw o r d s ：咀。；c o r n p a c tt r e eh l d 敬i l l g ；t r e ep a t t e mm 眦l l i n g ：) m 几q u e r y 酬删o n ；王，a ms m n i i l a r y i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：毖啦日期： 1 2 ：兰： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：盘盘导师签名： 山东大学硕士学位论文 第一章绪论 1 1 本文的研究背景 随着h l t e m e t 信息技术的迅速发展，i n t e m e 已经成为人类社会信息共享与交 换、信息发布与传递的平台。同时，当今的h l t e m 吐又面临信息格式松散、缺乏 必要标准和元数据的问题，各内容提供者和服务提供者大多以自治的方式存在。 、w c 在1 9 9 8 年制定了儿i l 】( 龇i b l em a r k 印l 锄g u a g e ) 的标准，启动了整个 h t e m e t 信息标准化的进程。儿以其自描述性、可扩展性以及计算机易处理性 迅速取得了学术界和企业界的广泛认同，日益超出其作为标注语言的初衷而成为 m t 咖e t 上数据表示和交换的标准。 沮。最大的优点是它强大的数据表达能力，目前大量以) m 几表达的数据 在h l 蜘l e t 上迅速地增长。大量咀。数据的存在，使得如何管理，如何查询这 些数据成为迫切的问题。由于关系数据库的技术已经十分成熟，现在的关系数据 库系统都具有高性能的关系查询引擎、良好的可扩展性、安全性和健壮性等优点， 所以人们想到了采用关系数据库来管理沮。数据，并且利用关系数据库系统管 理沮。数据可以保证) m 几数据的一致性和完整性。 但是目前广泛应用的关系数据库管理系统并不适合管理) m 几数据，最主 要的原因在于) m 几数据和关系数据在数据模型上存在较大差异。沮。是典型 的半结构化数据，关系模型的一维表结构在表达树形结构的咀，数据上存在很 大的困难，不但转化算法复杂，而且数据的冗余度很大，简单的咀，数据往往 需要表示成多个表。另外从查询语言上来说，咀。数据的查询语言包括数据绑 定和结构重构两个部分，查询语言的基本成分是路径表达式，而关系模型也没有 路径表达式的概念。 目前如何在) 。儿文档中高效的查询是一个关键的问题，尤其是路径表达式 的计算。例如，x 蹦l 嘲使用路径表达式来浏览儿文档的嵌套层次结构。在w 3 c 联盟提出的儿查询语言x q u e 丐【3 】中，路径表达式不仅是结构化文档上的一个 基本操作，而且成为几乎所有复杂操作的组成部分，所以处理路径表达式是咀。 查询计算的一个重要部分。直接处理路径表达式的简单方法是浏览儿文档中 山东大学硕士学位论文 所有可能的路径来找出匹配路径表达式的全部节点元素，这种简单计算方法需要 遍历整个) 0 儿文档，效率低下。 使用索引是一种有效处理路径表达式查询的方法，它可以减少查询语言处 理数据时连接操作的次数。但是从路径表达式的计算从本质上来说，尽管这些查 询语言在具体的处理路径表达式语法上都不甚相同，但是它们都有一个共同的特 征：不但查询v 儿文档中具体的数据而且查询具体的结构，这些查询语言的查 询语句都可以表示成相应得查询模式树，然后使用查询模式树去匹配札文档 中的数据，这也是查询模式树在帆查询中广泛使用的重要原因。本文将讨论 运用c 仃e e 索引在x m l 文档中进行查询模式树匹配的问题。 1 2 课题研究现状 1 2 1x m l 查询方法 ) 口诅。数据的查询方法大体上可分为两类：近似查询与精确查询。) 函几的 近似查询是以关键字查询为基础的，它实际上是将文本检索技术引入v i l 研究 领域，将整个咀。数据库视为一个带关键字索引的文本库，来近似匹配待查找 的查询模式集，从而得到最终的查询结果。这一方面不是本文中要详述的研究内 容，本文的查询算法属于精确查询的范畴，所谓精确查询是指以多种查询语言为 基础的，通过模式树匹配，得到精确查询结果文档的查询方法。下面从不同角度 对查询方法进行讨论。 从存储血角度讲，主要有两类方法，一类是使用特殊的存储半结构化数 据的查询引擎，因为一个儿文档可被看作是一个半结构化数据集的实例，) m 几 中的数据被映射成半结构化数据模型，用基于图遍历嘲的查询处理器来处理x m l 查询：另一类是使用传统的数据库，如关系数据库或面向对象数据库来存储和查 询儿文档，虽然使用传统数据库引擎有一定好处，但由于儿数据模型和传 统数据库模型间存在不同，所以这一类方法受到很大的阻碍。 从查询帆文档角度讲，包括两类方法：( 1 ) 模式匹配m ，所谓模式匹配，就 是将模式树与) m 几数据库中的相关文档相匹配，以求得匹配该模式树的结果文 档，如“查找包含字符串s 的所有x 元素”，模式匹配又分为两类方法，一类是整 树匹配，整树匹配就是将儿查询转化成模式树与札文档树之间的匹配问题， 文献【l8 】【2 2 】中提出的数据模型和查询代数的核心之处就在于它们均将查询语句 2 山东大学硕士学位论文 首先转换成模式树，再到x m l 数据库中去匹配模式树得到查询结果；另一类是 基于倒排索引的匹配，目前研究不是很广泛，在这里不再展开讨论；( 2 ) 基于树 导航访问儿数据，儿利用一种结构化数模型来表示数据，原始的树结构关 系是父子关系和祖先后代关系。目前，为每个元素编码的存储方式在一些系统 中使用，这种编码模式能够很快决定在儿数据层次中元素间的祖先后代关系。 过去对于) 。札查询处理的研究中，人们一度把模式匹配所用到的倒排表过 滤方法与树导航技术分开，虽然这两种技术各自有一定的优化方向，但有很多方 面的不足。2 0 0 3 年美国w i s c o 哪i n 矗江a d i s o n 大学的舢m 等人把这两种处理方法紧 密结合起来，已证明利用这种混合模式的查询处理方式f 8 1 能够获得更快的查询响 应时间。其中描述的两种算法都有各自的优化路径表达式形式，结合起来将产生 更好的查询计划。 1 2 2 结构化连接算法研究现状 结构化联接算法就是要找到两个元素序列之间的匹配对序列，这些匹配对 满足祖先后代关系或父子关系。在) a 诳。文档树节点编码的基础上，人们提出 了各种结构化连接算法。在目前已经提出的结构连接算法中，基于排序合并的算 法是其中的主流。该类算法普遍采用区域编码，假设输入数据集合满足如下的条 件之一或全部：( 1 ) 两个输入集合中的元素有序；( 2 ) 在输入集合中的元素上存在 索引。在前提条件满足的情况下，该类算法具有较高的效率。 z h 孤g 【9 】等人针对x m l 数据查询中的路径表达式计算问题，提出了多种结构 连接算法，包括基于索引的嵌套循环算法和多谓词合并连接算法( m m 矗p r e d i c a l e m e 玛ej o i n ) 。基于索引的嵌套循环结构连接算法利用在后代集合上的b + 树索引， 对祖先集合中的每个元素，查找其后代节点，输出结果。多谓词合并连接算法与 传统的排序合并连接算法的不同之处在于它利用了所有的连接条件来指导合并 的过程，从而可以避免一些不必要的比较，提高算法的效率。 s s 【7 】在其提出的( o r d e r ，s i ) 编码的基础上，提出了路径表达式的分解计 算方法和多个连接算法。正则路径表达式可以被分解为如下的基本子表达式：单 个元素或属性，一个元素和一个属性，两个元素的子表达式，带嘲ec l o s u 叫+ ) 的子表达式，及两个子表达式的并集，各个基本表达式所产生的中间结果被进 一步连接产生给定查询的最终结果。为了处理各种类型的子表达式，s s 提出 3 山东大学硕士学位论文 了三个路径连接算法：( 1 ) e a j o i n ：连接两个子表达式的中间结果，一个是元素 列，另一个是属性列。( 2 ) e e j o i n ；连接两个子表达式的中间结果，两个都是元 素列。( 3 ) k c j o i n ：处理带有+ 的表达式。这里的基本路径连接算法e e j o i i l 与 m 队弼心算法类似，也是排序合并类的结构连接算法，要求输入的元素集合按 编码的顺序排列。采用该算法，输入的祖先集合a 只扫描一次，但后代集合d 可能被扫描多次。 文献【n 1 中提出了一类基于栈的结构连接算法，称为s t a c k - t f e e 算法。该类 算法在排序合并的基础上，利用江数据的树状本质，通过在内存中保留一个 栈结构来达到对输入的集合只扫描一遍的效果。该类算法有两个：s t a c k t r e e a 皿。 和s t 粒k - 1 h e - d 酷c ，分别按照祖先节点和后代节点的编码顺序来排列输出结果。 s t a c k - t r e e d e s c 算法在栈结构中保留着一个祖先节点的序列，序列中的每个节点 是所有它前面节点的子孙节点，栈的最大深度不会超过数据树的高度。基于栈的 算法保证了对两个输入集合只有一遍扫描，在最坏的情况下比前一类算法有更好 的性能。 文献【1 2 】提出利用索引结构来进一步改善s t a c k 1 r e e d e 算法的效率，主 要思想是在元素的编码上建立特定的索引结构来辅助跳过不可能发生连接的节 点，从而避免对这些节点的处理。可以利用的索引结构包括b + 树，改进的b + 树，以及r 树。基于b + 树的算法的基本过程与k - t r e e d 鹊c 算法类似，但利 用b + 虹来跳过祖先和后代列表中不会参加连接的节点，从而减少对输入列表 的扫描代价，提高效率。但是这种方法的问题在于：在b + 树中检索是要花代价 的，当检索b 怕e 的代价超过直接扫描不参加连接的节点的代价时，效率不会 提高。 为了解决这个问题，对b + t d 的结构进行了改进，在其叶子节点中附加了 额外的结构，叫做c o n t a i n m tf o r e s t ( c - f o r e s t ) 。在这个结构中，同名的数据元素 通过三个指针p a r e n t 、丘r s t c h i l d 以及r i g h t - 曲l i i l g 连接在一起，这样在跳过祖先 节点时可以直接找到下一个应当处理的节点，而不必查找b 慨e 。这种方法的负 面影响是增大了存储，从而导致扫描代价的增大。该类算法依赖于索引的存在， 而且只有在输入的祖先、或者后代集合中不参与连接的节点数目较多时，才会取 得比s t a i 出1 h e 类算法更高的处理效率。 4 山东大学硕士学位论文 文献【1 3 】针对文献【1 2 仲的算法不能有效跳过祖先节点的问题，提出了一种 索引结构x r 1 k e 来辅助跳过不参与连接的祖先节点。e 索引建立在元素 节点的区域编码( s t a r t ，d ) 上，它的主干结构类似于b + 树，对节点集合根据其 编码的s t a n 进行索引，但与b + 树不同的是，树中的每个内部节点都带有一个元 素列，记录了包含该内部节点中键值的元素编码。该索引支持的两个基本操作是 f i n d d 髓c e n d a n 乜和f i n d a n c e s t 0 硌，分别可以找到一个给定的元素e 的所有后代 和所有祖先。利用这两个基本操作在结构连接中可以有效地跳过不需要处理的祖 先和后代节点。 1 3 本文的研究内容 沮。查询匹配是先将查询语句转化成一棵模式树，然后再到咀。数据库 中去进行查询匹配。可分为两种方法：一种是将) a 儿文档看成树结构，用模式 树去匹配树型的) a 诅。文档；另一种方法是将) m 几文档中的结点进行索引标记， 将其变换成一个带标记的结点序列首先从该序列中找出与模式树相匹配的部分， 再组装成查询结果文档。本文的研究内容是基于第一种方法，把查询条件首先转 化成模式树，然后去匹配v 儿文档。 由于舢文档可看作树型的，对舭的查询可以看成是基于值 ( v a l m _ b 勰e d ) 谓词的子树( 厕g ) 匹配，也就是从咀，文档找到和给定查询条件相 匹配的子树。因此能够高效找到子树匹配成为。中的一个核心问题。但是目 前的模式树匹配算法大都是基于分解匹配合并步骤进行查询匹配处理。这类方 法的缺点是产生了大量无用的中间结果，这些中间结果远远超过了想得到的最终 结果，并且产生了无用的重复匹配。 而本文根据以往结构化连接算法和咀。查询的相关研究成果，提出了一 种灵活的模式树匹配算法p a n 踟l 【a t c h ，算法能够直接从) m 儿文档中找到和查 询模式树( q u e r yt r e ep a n e m ) 匹配的所有结果集合。和基于分解- 匹配一合并步骤的 查询匹配算法相比，有以下两个优点：( 1 ) p a t t 锄1 m a 曲算法不需要分解查询模式 树，直接用查询模式树在儿文档中进行查询匹配：( 2 ) 中间子模式节点匹配结 果被存储在堆栈中，利用连接操作能够方便的从这些匹配结果中得到最终查询模 式树匹配结果。 山东大学硕士学位论文 1 4 论文组织安排 【第二章咀。研究概况】首先给出了x m l 基础和沮。查询语言的基 本理论基础，并且给出了相关的例子进行了详细的说明。然后引入了咀索引 的概念和分类，最后介绍了) m 几相关的标准集合。 【第三章结构化连接概述和相关算法】首先介绍了模式树的概念，然后 对本文所用到的模式树匹配和结构化连接概况的前人所作的成果以及相关领域 的知识背景作概括性的介绍，然后详细介绍了典型的结构化连接算法1 嘶gj o i n ， 并说明了算法中存在的典型缺点和改进的方向，然后介绍引入算法p 砒咖m a l c h 的必要性。 【第四章p a 船h l m a c h 算法】首先给出了算法p a t 咖m a t c h 用到的数据结 构的介绍，为了更好的说明算法的运行过程，给出了一个简单的c 仃索引的例 子，然后给出了p a t t 朗删嘶c h 的算法和相关的代码的分析，最后进行了详细的性 能分析。 【第五章总结和展望】对论文的研究工作和成果进行一个总结，指出了 其中的不足，并对今后进一步的工作进行展望。 6 山东大学硕士学位论文 第二章x 胤相关理论与研究 2 1x m l 简介 咀。是由w 3 c ( 、) i ，0 n d 晰d e w e b c 伽s o n i 肿) 组织的皿工作小组定的。 这个儿小组是这样描述该语言的：扩展标记语言o 【m l ) 是s g m l 的子集，其 目标是允许普通的s g m l 在w 曲上以目前h 卟几的方式被服务、接收和处理。 ) 口帆被设计成易于实现，且可在s g m l 和h n 之间互相操作。这段话是从正 式的沮，规范l ，o 版本中引述的，该规范是沮。工作组在1 9 9 8 年2 月完成的。 正如所提到的，皿。设计的初衷是让它成为一种专门在w 曲上传递信息的语言， 就像m ，( 超文本标记语言) 一样( 自从w 的出现以来，i m l 已经成为了创建 w 曲页的标准语言1 。 与h n 缸不同，儿具有如下一些特征：儿具有自描述性( 元素的标记描 述了信息) ：儿具有可扩展性( 用户可以通过d 巾或s c h 嘲来定义新的元素) 血提供了更为灵活的机制来表达更为复杂的链接关系，x l 址龇“n k i n g l a n g u a g e ) h 1 和) 0 i n 把f 眦p o 硫e rl 锄g u a g e ) 嘲允许定义灵活的链接日标；把 信息的结构、内容和显示分离开来，x m l 主要表示信急的内容和结构，而把显 示方法交给x s l ( e x t e i l s i b l es t y l e s h e e tl 趴g u a g e ) 或c s s 处理。 x m l 是、w c ( 、杨r dw i d ew 的c o n s o 而眦) 的恤。工作组为适应h l t 咖e t 的发展，实现快速的电子商务和电子数据交换而推出的新型w 曲语言。这个工 作组是这样描述该语言的，x m l 是s g m l ( s t 锄d a r d g e r a l i z e d m a 出叩 l a n g l l a g e ，标准通用标记语言) 的子集，其目标是允许普通的s q l 在w 曲上以 目前m m l ( h y p 蝴m a f k u pl 啪g u a g e ，超文本标记语言) 的方式被服务、接收 和处理。血被设计成易于实现，且可在s g m l 和m ，之间互相操作。”由 于咀提供了一种灵活的文档结构来描述数据，因此，x 砌l 在网络上得到了 迅速的普及，成为i l l 锄e t 以及各种信息集成中的数据交换格式。沮。结构的灵 活性，是沮。与关系数据库的最大差别，咀，也被人们普遍认为是一种典型 的半结构数据。 x m l 是一套定义语义标记的规则，这些标记将文档分成许多部件并对这些 7 山东大学硕士学位论文 部件加以标识。帆不是类似于h r 也的预定义的标记语言，而是用于定义其 它标记语言的一种元语言，与m m l 中有固定数量的标记，用来描述一定数目 的元素不同，咀。用于描述信息的各种标记都可以由设计者自行建立，以强化 特定专业数据的结构和关联，) m 几标记描述的是文档内容的结构和含义，而不 是描述页面元素的格式化。可用c s s ( c a s c a d i n gs t y l es h e e t ，级联式样式单) 和 x s l 但蛆s i b l es t y l el a l l g u a g e ，可扩展样式语言) 为皿。文档增加格式化信息。 ) m 几文档本身只说明文档包括什么标记，而不是说明文档看起来是什么样的。 下面给出一个简单的沮文档的例子。 例2 i 一个咀。文档例子 s t e v e n s f i 塔口i w 。 6 5 9 5 咖r i c e a d v a l l c e dp r o 掣a 砌【i l i n gi l l1 l i eu n i ) 【即啊r o 叫n t 刮m l d a u t h o r l a s p s t e v 锄s 6 5 9 5 唧r i c e x m 匝t ( ，t i t l p 龟n m l o r l 嬲伊a b i t e b o l j l ，l a s 伊 a u 山。闪嬲伊s u c i u 矾孤；护h m o 唱眦k a l l n np i l b l i s h e r s 帆文档是一种树状的结构，包含了从根元素开始的嵌套元素结构，所以 经常把诅。文档称作咀文档树。皿。文档的n 个元素有一个标签与之对 应。除了字符串数据，元素还可以包含属性值对和嵌套子元素。例2 ，1 给出了一 个描述书籍信息的儿文档。根元素b i b 包含多个b o o k 子元素，b o o k 元素又 包含y e 盯属性以及d t i e 、锄l l i o r 、p u b l i s l l e f 、研等子元素，其中卸t l l o r 子元素 可以有多个，粕t h o r 元素又包含l a s t 和矗r s t 子元素。 山东大学硕士学位论文 帆虽然并不是专门为了表示数据而设计的。其最初被设计通过分立内容 和格式来面对大规模的电子出版业的挑战。但是由于其自身所具有的特点而被广 泛应用于网络上数据的表示，并成为事实上的网络数据表示标准。 x 池具有其他表示方法所不具备的特点，主要包括： ( 1 ) x m l 是自描述的。沮的最大能量来源子他不仅允许定义自己的一套 标记，而且这些标记不必局限于对于显示格式的描述。 ( 2 ) 皿。具有集成数据和文档的能力。大多数语言或者在表示严格的、绝对 的内容和数据结构上设计得好一点，或者在表示灵活的、自由形式的文档文本上 设计得好一些，而) 圆几在两个方面都做得很好。它能表示数据和自由格式的文 本，也能在同一个文档上做到这两个方面。 ( 3 ) ) 0 沮。具有相当的表现力和可扩展性。实际上我们可以在所选择的主题 上表述任何想表述的内容。它具有一致的语法，这使得它很容易被解析。 ( 4 ) 咀，用一种灵活的可扩展的表式来实现内容通信。沮。允许开发各种 不容专业的特定领域的标记语言。有了这些语言，这个领域的实践者们可以相互 自由的交换短文、数据和信息，而不必担心对方是否利用特殊的、专用的软件来 创建数据。事实上，目前已经开发出了一些特定领域的标记语言，如m a 彻( 用 于数学领域的一种标记语言) 。这样，非常复杂的领域可以使用) m 几很好的合理 的表示出来。 f 5 ) x m l 是非专有并易于阅读和编写的。这使得) m 几成为在同同应用间交 换数据的理想格式。 正是由于具有上述的这些优点，) m 几作为网络上的数据表示方式为人们所 接受和使用，并迅速普及，成为事实上的网络上的数据表示标准。 2 2x m l 查询语言 随着利用x 眦。格式存储和表示的信息日益增多，在各种各样的帆数据源 中查询咀。数据的需求也越来越迫切。) m 几的提出是为了灵活的表示不同数据 源的不同信息。为了使这种灵活性得到最大程度的发挥，研究者设计了许多咀。 查询语言来从x m l 中查询数据。沮。查询语言可以像数据库那样访问沮。文 档或) 。皿文档集合，以儿数据作为查询对象的查询语言有很多，如 x q u e i ) r 1 1 1 ，x p a l l l l 2 】，q l l i l t ，) 函几一q l ，x m l - g l ，l 0 r e 等等。其中血路径语 9 山东大学硕士学位论文 言a l 和儿查询语言x q u e r y 最常用。这两种语言都是w 3 c 发布的标准。 为咀，文档提供了一个数据模型、一组基于这个模型的查询操作以及在这些操 作基础上的查询语言。这两种语言一脉相承，其中a m 是x q l l e r y 的子集。 2 2 1x p a t i i a 血( 沮。p a l h l 锄g l l a g e ) b 是一种对诅，文档的内容进行定位查询的语 言，是血查询语言如x q u e 哆网的基础，伽l 因使用路径标记在儿文档的层 次结构中进行导航而得名。其工作方式与语法有些类似于操作系统中用于文件定 位得路径以及互联网中用于资源定位的u r l 。当然，a m 比后两者复杂得多。 啪1 不独立使用，主要嵌入在x s u ，o i m e r ，d o m 等宿主语言中应用，比如 在x s l t 的应用中，a n l 用在模板( 钯m p l a l e ) 中来查询数据以及定位匹配模式。 x p a l l l 提供了关于路径导航如a mn a “g a l i o n ) 、节点定位( n o d el o c a l i ) 、谓词 选择等方面的一份精确的规范，并且被作为x q u e 玎的核心部分。a l h 中最重 要的组成部分是定位路径( 1 0 c 撕o np a c h ) ，具体分为绝对定位路径( a b l u t el o c 戤i o n p a i l l ) 和相对定位路径( r e l a l i v el o c 撕o np a l l l ) 两种。前者是从根节点到某个节点的 路径，后者是从当前选定的节点到某个节点的路径。在伽l 中路径表达式是 其核心组成部分，对于一个路径表达式可以写成p a i h ：= ( s 印) 的形式，而每个s t e p 又可以定义s t 印：= a 】【i s ：d e t e s t d p r e d i c a t e 】的形式。在每个s t e p 中轴( 崩s ) 专门指 定了文档定位的方向，- g l l l 支持1 1 种定位轴( 不考虑a 缸b u t ea 五s 和n a i l l e s p a c e a ，( i s ) ，x p a m 中的轴分成两类前向轴( f 0 n v 盯d a 菇s ) 和反向轴( b a c k w a r d a 虹s ) 前 向轴包括c h i l d d e s c 胁d a l l t s e l f ，d e s c e n d 柚r - s e l f o l l o 谢n 乎s i b l 访& f o l l o 而n g 共 6 个轴反向轴包括p 牡e n t ，锄c e s 垂o p f e c e d i n g s i b i i n g ，p m c e d i 呜趾c e s 衄o r - s e i f o a t h 将x m l 文档视为一个节点树，节点有七类，包括根节点、元素节点、 属性节点、文本节点、命名空间节点、处理指令节点、注释节点。a i l l 对每个 节点都定义了计算其字符串值的方法，不同的节点计算方法可能不同。文档顺序 ( d o c 哪e n to f d e r ) 定义了每个节点在沮。文档中出现的顺序。甜l 认为的文档 顺序与沮。文档中节点的物理顺序( 起始标签) 一致。例如，根节点为文档的第 一个节点，每个元素节点出现在其子节点之前。 a _ l l l 使用路径表达式去确定沮。文档中的节点。我们将利用例2 1 的 m 。文档描述) 口瞻也语法。x m l 文挡可以表示为树结构节点形式，而) a p 础使 山东大学硕士学位论文 用模式表达式识别沮。文档的节点。一个) 口抽的模式是使用反斜杠“广分开子 元素名称描述路径。下面的 甜l 表达式选择元素b i b 下元素b o o k 中的所有p r i c e 元素 b i b b 0 0 k p r i c e 注意，用，路径开始代表元素的绝对路径，不用厂路径开始代表元素的相 对路径，而用，路径开始代表整个文档满足条件的所有元素。如果表达式中间 用，路径代表元素下面满足条件的所有子孙元素。下面的x 蹦l 表达式选择文 档中所有的b o o k 元素下的l a s t 子孙元素。 朋) o o k ，l a s t x p g i h 和x q u e 黟中最基本的构筑部分是表达式。它们提供了若干种表达式， 这些表达式由关键字、符号和操作数组成。通常情况下，一个表达式的操作数是 另外一个的表达式。，柚和x q u e 可是函数性的查询语言，它们允许多种表达 式任意层次的嵌套。同时，它们也是强类型的语言，其表达式中的操作数、操作 符和函数等等必须对应有特定的类型。在a t i 中，有以下类型的表达式： ( 1 ) 主表达式口r i 眦l r ye 冲螨s i s ) 。主表达式是) 口a m 语言的基本原语，包 括变量、字面量、函数调用等等。 ( 2 ) 路径表达式口a t i le 印r e s s i o n s ) 。路径表达式是x p a m 语言的核心，它用来 在x 。树上定位结点，按照文档序返回一个不重复的结点序列。计算必须依靠 表达式上下文。 ( 3 ) 序列表达式( s e q u 饥c ee 冲r 嚣s i o n s ) 。序列表达式用来在) 田a l l l 语言中构 筑和合成序列，序列是一个包含零个或更多元素的有序集合，序列中的元素可以 是一个简单的值或者是一个结点。 ( 4 ) 算术表达式( a 劬m e t i ce 冲r 鹤s i o n s ) 。算术表达式提供了a t l l 语言中的 加、减、乘、除等运算。 ( 5 ) 比较表达式( c o m p a r i 啪e 冲r e s s i o n s ) 。比较表达式用来支持“大于”、“小 于以及判等等一系列的比较运算。在x p 劬中，比较运算包括值的比较、序列的 比较、文档结点的比较以及文档序的比较等等。 ( 6 ) 逻辑表达式g i c a le 冲r 髂s i o n s ) 。逻辑表达式表示逻辑上的与、或、非 等运算，返回值是一个逻辑值。 山东大学硕士学位论文 ( 7 ) 迭代表达式 o re 冲r e s s i o n s ) 。) a l l l 提供了迭代表达式用来执行迭代运 算，这种表达式经常用来计算两个或者更多文档之间的连接以及数据的重构。 ( 8 ) 条件表达式( c 0 n d i t i o n a le 冲r e s s i o n s ) 。条件表达式允许根据不同的条件而 使表达式返回不同的值。 ( 9 ) 量词表达式( q u a l l 临e de 印r e s s i o n s ) 。量词表达式允许通过全称量词或存 在量词测试表达式的值，其返回结果是一个逻辑值。 2 2 2x s i 卫 根据w 3 c 的规范说明，最早设计x s l t ( v 几s y s t l e s h e e tl a n g u a g e t r m s o 咖血o n l 的用意是帮助咀。文档转换为其它文档。但是随着技术的发展， x s l t 已不仅仅用于将沮，转换为h n 几或其它文本格式，更全面的定义应该 是：x s 是一种应用于操作咀。文档的完整高级语言，x s l t 是一种用来转换 沮，文档结构的语言。 x s 【t 最主要的功能是将咀。转换为h r m 【，。 x s u 有类似数据查询的语法，是一种转换沮。文档的语言，它包含两个 过程：转换和格式化。x s l ，t 中包含了一系列的模板规则与命令来控制数据的结 构，它具有以下特点： ( 1 ) x s l t 基于严格的沮。文档格式，可以自动使用v 儿的所有词汇设备 ( 如u n i c o d e 字符编码和转义) 。x s l t 可以容易地将期望的v 几输出块嵌人样式 表，如多个简单的样式表可以写为期望输出文档的模板，并且可以将一些特殊指 令嵌入文本中，以便插入输人中的变量数据或计算某个值。 ( 2 ) x s l ，t 样式表是易于移植的，任何符合x s l t 推荐标准的处理程序都可 以使用它。 ( 3 ) 基本处理范例是模式匹配。x s l t 样式表包括一组模板规则，每条规则 都使用以下方式：“如果在输人中遇到此条件，则生成下列输出”。x s 将输人 v 儿文档视为树状结构，每条模板规则都适用于树中的一个节点，模板规则本 身可以决定下一步处理哪些节点，因此不必按照输入文档的原始顺序来扫描输 人。 ( 4 ) x