（计算机软件与理论专业论文）xml复杂路径表达式查询处理技术研究.pdf

查! 坠! 翌主兰堡垒墨 塑墨 _ - - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ - _ _ - _ _ - _ _ _ _ _ _ - _ _ - _ - _ _ _ _ _ _ - 、 龇复杂路径表达式查淘处理技术研究 摘要 x m l 是可扩展标记语言( e x t e n s i b l e m a r k u pl a n g u a g e ) 的简称，它为w e b j 半结构化文档和数据提供了通用格式。x m l 是一种元语言，通过对一组标签设定 特定的意义，可以创建出其它的标记语言。随着i n t e r a c t 的发展尤其是w e b 技术的 广泛应用，越来越多的应用采用了x m l 技术作为信息表示和数据交换的标准，这 使得通过数据库技术对x m l 数据进行存储、查询等操作变得越来越重要。 在众多x m l 查询语言中，路径查询是最重要、使用最频繁的组成部分。目前 提出的大多数查询方法都是在实例空间中进行的，也就是说，使用这些方法查询 时，直接面对的操作对象是x m l 文档。这类方法中比较有代表性的是x m l 文档 树遍历的方法和包含连接的方法。根据自动机技术，我们提出了一种通过用查询 自动机匹配x m l 模式树来计算查询路径表达式的方法，称为自动机匹配算法 ( a u t o m a t am a t c h ，a m ) ，来解决x m l 正则路径和复杂路径查询表达式的策略。自 动机匹配算法可以在模式空间内高效地计算路径表达式，因此这种方法可以适应 在海量数据上执行复杂查询的需要。 本文提出了如何将具有各种运算符的正则表达式转化为查询自动机的方法。 针对x p a t h 规范中规定的“”操作符，即祖先一后代关系操作符，我们提出了一 个称为模式自动机( s c h e m aa u t o m a t a ) 的数据结构，模式自动机可以接收所有可能 出现在x m l 文档中的片断，也就是说，它可以匹配任何可能出现在x m l 文档中 的路径模式：而传统的自动机要想支持包含连接这一类非正则运算符是非常困难 的。为了进一步提高模式自动机的性能，本文还提出了两种优化方法p s a 和r w s 。 前者将模式自动机作为索引的一部分存储在磁盘上，避免了每次计算都要生成模 式自动机的开销，后者则是通过f o l l o w i n g 集合和p r e c e d i n g 集合来过滤掉模式自动 机中多余的状态和转换函数来达到提高查询效率的目的。为了支持自动机匹配算 法，本文还提出了高效地支持自动机匹配算法的数据结构：路径模式树和路径实 例树。通过与结构连接算法进行性能测试对比，我们发现自动机匹配算法的效率 远远高于结构连接算法，p s a 和r w s 对自动机匹配算法的优化也很显著。 与传统的关系数据库中的查询不同，针对半结构化数据的查询更多的是要找 到满足某些特定模式的节点。近来，在简单路径查询的问题得到较好解决的基础 上，人们将注意力转移到t w i g 查询中来。本文提出了如何利用索引技术来更好地 解决t w i g 查询的问题。根据路径模式树索引，我们给出了利用自动机匹配路径模 式树索引解决这一问题的方法，围绕这一方法，本文对t w i g 查询自动机的构建， i l 东北大学硕士学位论文 摘要 t w i g 查询自动机与路径模式树的匹配等算法进行了讨论，并与用传统的结构连接 方法解决t w i g 查询进行了实验对比，结果证明，基于自动机的方法在性能上具有 较大优势。 关键词：可扩展标记语言，自动机，模式自动机，路径表达式查询，t w i g 查询 i i i 东北大学硕士学位论文 a b s t l 4 c t s t u d y o nx m l q u e r yp r o c e s s i n gt e c h n i q u e so f c o m p l e x p a t he x p r e s s i o n s a b s t r a c t x m i 。( e x t e n s i b l em a r k u pl a n g u a g e ) p r o v i d e sg e n e r a l f o r m a tf o r s e m i s t r u c t u r e dd o c u m e n t sa n dd a t ao nt h ew e b i ti sas i m p l ea n df l e x i b l e f o r m a ta n dw a s o r i g i n a l l yd e s i g n e d f o re l e c t r o n i c p u b l i s h i n g n o w a d a y s ， x m l p l a y sm o r ea n dm o r ei m p o r t a n tr o l ei nw e bb a s e da p p l i c a t i o n s i nx m l ， t a g s a r eu s e dt od e s c r i b et h es t r u c t u r ei n f o r m a t i o n so fd o c u m e n t s x m li s w i d e l yu s e da s as t a n d a r dl a n g u a g ef o rr e p r e s e n t i n ga n de x c h a n g i n gd a t ai n w e bs i t e c o n s t r u c t i o n ，d i s t r i b u t e da p p l i c a t i o np l a t f o r m sa n do t h e rs y s t e m s t h e r e f o r e ，i tb e c o m e sm o r ea n dm o r ei m p o r t a n tt om a n a g ex m l d a t at h r o u g h d a t a b a s e s r e c e n t l yal o to f r e s e a r c hw o r kh a sb e e nd o n ef o rm a n a g i n gx m l d a t a p a t hq u e r yi so n eo ft h em o s tf r e q u e n t l yu s e dc o m p o n e n t sb yt h ev a r i o u s x m l q u e r yl a n g u a g e s m o s to f t h ep r o p o s e dm e t h o d sc o m p u t ep a t hq u e r i e si n i n s t a n c es p a c e s ，i e t h ex m ld a t a ，s u c ha sx m l t r e et r a v e r s a la n dc o n t a i n m e n t jo i nw a y s a saq u e r ym e t h o db a s e do na u t o m a t at e c h n i q u e ，a u t o m a t a m a t c h i n gf a m lc a n e v a l u a t ep a t he x p r e s s i o nq u e r i e si ns c h e m as p a c es ot h a ti t a l l o w se f f i c i e n tc o m p u t a t i o no fc o m p l e xq u e r i e so nm a s s i v ex m l d a t a t h i st h e s i sf i r s ti n t r o d u c e sh o wt oc o n s t r u c tq u e r ya u t o m a t ai no r d e rt o e v a l u a t ev a r i o u sr e g u l a re x p r e s s i o nq u e r i e si n c l u d i n gt h o s ew i t hw i l d c a r d s f u r t h e r m o r e ，ad a t as t r u c t u r en a m e d s c h e m aa u t o m a t ai sp r o p o s e dt oe v a l u a t e c o n t a i n m e n tq u e r i e st h a ta r ev e r yd i m c u l tt oh a n d l ef r o mt h ec o n v e n t i o n a l a u t o m a t ap o i n to fv i e w t oi m p r o v et h ee f f i c i e n c yo fs c h e m aa u t o m a t a ，w e p r o p o s e dt w oo p t i m i z a t i o ns t r a t e g i e s ，p s aa n dr w a f o rp s a ，w e s t o r et h e s c h e m aa u t o m a t ao nt h ed i s ka sap a r to ft h ei n d e x t h es c h e m a a u t o m a t an e e d n o tt ob ec o n s t r u c t e dd y n a m i c a l l ye v e r yt i m e ，w h i c ht h e r e b y r e d u c e st h e r e s p o n s et i m e w i t hr e s p e c t t or w a ，w er e d u c et h es c h e m aa u t o m a t ab y f i l t e r i n g t h eu s e l e s ss t a t u s e sa n dt h et r a n s f o r mf u n c t i o n sa c c o r d i n gt o t h e f o l l o w i n gs e ta n dt h ep r e c e d i n gs e t i n t h i st h e s i s ，t w od a t as t r u c t u r e s ，p a t h i n s t a r t c ei r e ea n dp a t hs c h e m at r e e ，w e r ep r o p o s e dt os u p p o r tt h e a u t o m a t a m a t c h a l g o r i t h me f f i c i e n t l y t h e e x p e r i m e n t a l r e s u l t ss h o wt h a tt h ea m d e r f o r m sm u c hb e t t e rt h a nt h e c o n t a i n m e n tj o i n ，a n dp s aa n dr w sa r e 东北大学硕士学位论文 a b s t r a c l _ w - - _ _ _ _ _ _ _ _ h h h - 一 h m _ h _ _ _ e f f e c t i v eo p t i m i z a t i o u so na m d i f f e r e n tf r o mt h ec o n v e n t i o n a l q u e r i e s i nr d b m s x m l q u e r i e s t y p i c a l l ys p e c i f yt w i gp a t t e r n so fs e l e c t i o np r e d i c a t e so i lm u l t p l ee l e m e n t s t h a th a v es o m es p e c i f i e ds t r u c t u r a l r e l a t i o n s h i p s f i n d i n ga l l o c c u r r e n c e so f s u c hat w i gp a t t e r ni na nx m i d a t a b a s ei sac o r eo p e r a t i o nf o rx m l q u e r y p r o c e s s i n g at w i gq u e r yc a nb et r a n s f o r m e dt oa na u t o m a t o n p e r f o r m a n c eo f c o n v e n t i o n a le v a l u a t i o n a p p r o a c h e s b a s e do ns t r u c t u r a l j o i n s d e c l i n e sa s i n c r e a s i n go fd a t aa n dq u e r yc o m p l e x i t y i nt h i st h e s i s ，an o v e la p p r o a c hi s p r o p o s e dt oc o m p u t et w i gq u e r i e sb ym a t c h i n gt w i gq u e r ya u t o m a t aa n dp a t h s c h e m at r e e s ，m o r e o v e r ，w eg i v et h ep e r f o r m a n c ee v a l u a t i o nt od e m o n s t r a t e 1 t h eh i g hp e r f o r m a n c eo fo u rm e t h o d s k e yw o r d s ：x m l ，a u t o m a t a ，s c h e m aa u t o m a t a ，p a t he x p r e s s i o nq u e r y ，t w i g q u e r y - v 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论 文中取得的研究成果除加以标注和致谢的地方外，不包含其他 人已经发表或撰写过的研究成果，也不包括本人为获得其他学 位而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 本人签名： f 虱丁考 日 表弛走学硕士学位论文 第一章蔻言 第一章前言 睫蕾w e b 技术的飞速发展，基于嘲络技术的应用领域舅濒增多，网络信息爨 也变褥越来越大。目前主要用于表示w e b 文档和数据的h t m l 语言着重于数据的 外部表现形式，两不是内部的数据结构，已经不能满足w e b 上信息表示和数据交 换的要求。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 ) 是一种简单酶、自描述的、内容 与表现栩分离的语言，已经被大家广泛接受作为w e b 上信息表示与数据交换的新 标准。随着m i c r o s o f t 在箕n e t 体系中全蟊使蘑x m l 佟为英各灏 幸蠲信惑载体， 以及o r a c l e ，i b md b 2 等大型商业数据库产品纷纷将地的存储和查询功能纳入 箕核心部分，越窳越多瓣璃菇鼓及w e b 虚爰霞鹅tx m l 送行售意豹发东，w e b 上用x m l 表示的数据越来越多，x m l 已经成为目前w c b 上最蹙瞩目以及被认为 跫援其笈震蓑最麴技术。然恧，瞧于x m l 鹣半结构化特性，馒褥簧统熊数据管耀 技术不能完全满足对x m l 数据的存储以及查询管理的需要。因此。研究针对x m l 数据豹数据库管理技术势在必行。旦翦，x m l 数据库的主要工作集中在查询处理 及优化技术，知路径表达式查询优化技术，t w i g 查询优化技术，包含连接查询技 术研究，x m l 索引技术等，但是由于x m l 具肖十分复杂的半结构化特性，目黼 的研究成果还不能完全支持x m l 标准凌询语言x q u e r y ，因虼在世界蒗围肉，无 论是学术界还悬工业界，对x m l 查询处理和优化技术都正在进行更加深入的研 究。 1 1x m l 相关技术 1 1 1 一个x m l 数据实例 q x 攥lv e r s i o b = 1 。0 ”s t a n d a l o n e - - = - | n o ”? s 鞋e h a c l a c ti ne p i l o g u e f i n i s h t h ea c t1 、 烫l ， x m l 实铡文梢 f i g u r e1 1x m ls a m p l ed o c u m e n t 东北大学硕士学位论文第一章前言 鹜 1 怒一令x m l 文楼实翻，文禚静蘩一雩亍是一令x m l 声疆，绘鲞了x m l 文档采用的x m l 版本号，怒否和外部d t d 配合使用 以及数据历采用的编码方 式等信塞。文档熬篱2 雩亍据瞧了当曼示该x m l 文档瓣获应搜蠲的撑蔑文馋。文挡 第3 行是文档的外部d t d 使用说明。从第4 行起是文档所表示的数据。x m l 通 过元素寒缰织x m l 数提，元素是x m l 文搂内容鲍基本单元，x 1 w l 元素包摄标 记和字符数据。从谮法角度上看，一个元素包含了个起始标记、一个结束标记 以及标记之闼的数据皮容。x m l 中宥元素、属性、文本等几摊基本的数据类型， 因为本文主瓣探讨x m l 文档路径查询，因此我们主臻研究这几种数据类型。每个 x m l 文档有且仅有一个根元素，图1 1 中的根元素的标签为a c t ，它有两个子元 素，其标签分剐是p r o l o g u e 鞠e p i l o g u e 。 j 。 1 。l 。2d 0 搬模型及d o m 标准 图1 2 怒与图1 1 中的x m l 文档相对应的d o m 树。d o m 模型以有层次的结 点霹象耱款形式来袭疆文档。这些蘩患中鸯熬可滋霄孩子结点，有懿只戆 擘隽时 子结点存在。通过用图形表示的d o m 树，我们可以很清楚地了解x m l 文档的数 辗之闯戆缝稳。建繁篱头数线段表示实倒之阙鲍实辩的父予关系或滋元素与属性 之间的关系。图形中的数字代表这一缩点实例的唯一标识( o b j e c t i d ) ，如果d o m 键在内存中实理，它霹能是结点款摆针或旬援，如聚d o m 被持久他在数据库中， 它可能是记录的主镳或者对浆的i d 。符号下面的字符串标明了元素结点或满性结 点的名字。如标记为“9 ”的结点就对应于魏睡示例文档中“a c t i np r o l o g u e ”这段 文本，它是a c t 元索( 编号为5 ) 节点的子节点。 d o m ( d o c u m e mo b j e c tm o d e l ) 是w 3 c 报荐的组应用于x m l 和h t m l 的编 程接口。d o m 定义了文档静逻辑结构以及文档静诱滔帮修潋方法。警x m l 文挡 以d o m 的方式呈现时，可以被看作数据而不单纯是文件。d o m 规范为程序开发 图1 2 示例文档的d o m 树 f i g u r e 2 d o m t r e e o f s a m p l e d o c u m e n t 。一 鱼w 、 ， #， 芝一 一；土尚一一 瓣 一 查! ! 查堂翌主堂堡笙查 茎二主堕童 者提供了一系列的应用程序接口的描述，通过d o m ，程序开发者可以创建个 x m l 文档，按文档的结构进行遍历、增加、删除或修改x m l 文档中的元素和内 容。w 3 c 在制定d o m 接口时即要求该标准具有平台无关性，使它能够在任何平 台上以任何语言实现，所以d o m 标准使用o m gi d l 编写。d o m 标准定义的所 有的a p i 都是接口( i n t e r f a c e s ) 定义而不是类( c l a s s ) 定义。这意味着标准的任 何实现都只需要按照名字和定义好的操作来实现该方法。 1 1 3d t d 简介 图1 3 给出了个与图】1 中的x m l 文档对应的d t d 图。 仍蕊卜 & i d h 。e p i l o 畔弧 下 l 图1 3 示例文档的d t d 图 f i g u r e l 3d t dg r a p h o f s a m p l ed o c u m e n t d t d 是w 3 c 推荐的针对h t m l 和x m l 文档的类型定义标准。它对x m l 文 档的层次结构和内容做了描述。x m l 解析器利用d t d 来验证x m l 文档的正确性。 虽然d t d 提供了一定的模式信息，但是还十分不全面，为了解决这一问题，w 3 c 又提出了x m ls c h e m a 标准。另外，d t d 本身是可以动态改变的。这就为x m l 的扩展提供了方便。 x m l 的本质意义是通过提供给文档的编写者以制定基于信息描述、体现数据 之间的逻辑关系的能力来保证文档的语义清晰和易检索性。因此，一个x m l 文档 不仅要是“格式良好的”，而且还应该是使用了一个自定义标记的“有效的”x m l 文档，也就是说，它必须遵守文档类型定义d t d 中已经声明的规定和限制。d t d 描述了标识语言的语法和词汇表，也就是定义了文档的整体结构以及文档的语法。 也就是说，d t d 实际上规定了一个语法分析器为了解释一个“有效的”x m l 文档 所需要了解的全部细节。一个d t d 可以是内部的，包含在x m l 文档的前面说明 部分；也可以是外部的，作为一个外部文档被引用。外部d t d 的好处是可以被多 东北大学硕士学位沦文 第一章前言 个x m l 文档方便地共享。表1 1 给出了图1 3 对应的d t d 。 表1 1 实例文档的d t d t a b l e1 1d t do fs a m p l ed o c u m e n t 1 2 3 4 5 6 从表1 1 中可以看到：a c t 元素包含两个子元素e p i l o g u e 和p r o l o g u e 它们后面各自的一个“? ”称为元字符。表1 2 列出了d t d 的正则表达式中可能 出现的元字符及其意义。 表1 2 d t d 中的元字符 1 b b l e1 2m e t a c h a r a c t e r si nd t d 元字符含义 元素a 元素b 元素c元素列表，无须遵从顺序要求 并( a n d ) ，要求严格遵从顺序要求 出现一次或多次 出现零次或多次 ( ) 一组要共同匹配的表达式 i 或( o r ) 可选，不出现或出现一次- 1 _ 2x m l 数据的存储策略 j 二面给出的图1 2 中的d o m 树只给出了x m l 数据在数据库中存储的逻辑模 型，而x m l 数据在数据库中的物理存储却是因数据库的不同而差别很大，归纳起 来，主要有以下四种方式：文本文档格式，关系表格式，对象类模式和专门为x m l 设计的存储模式。对应于不同的存储模式，也有不同的数据管理技术。以上四种 方法由于出发点不同，在存储，查询的效率七各有所长。 除了最近出现的x m l 数据流，x m l 数据的表现形式基本都是x m l 文本文 t 一， 因此管理x m l 数据的最直接的方法就是将其存储于文件系统中。目前有三种方式 是基于文本的存储方式的：基于信息检索技术( i n f o r m a t i o n r e t r i e v a l ，i r ) 的关键 词查询和用户定制的基于d o m 或s a x 接f 的用户定制查询。这种存储方式的优 点是：存储方便，成熟的i r 技术可以直接得到应用，可以使用基于d o m 或s a x 4 东北大学硕士学位论文第一章前言 的工具。缺点有很多：i r 方法仅仅是对关键词的查询，而忽视了结构信息，也就 是忽视了x m l 数据的本质。因为d o m 占用的内存将是原文档大小的1 0 倍左右， 所以将文档以d o m 的形式解析到内存进行查询的方式只适合于小文档，而且每一 次查询都需要重新解析x m l 数据。 基于关系数据库的管理方式由于关系数据库产品本身在数据库市场的统治性 地位而成为x m l 数据管理技术中最重要的一种，因此也有许多研究注重于这一方 面。当我们将x m l 数据存入关系数据库中时，必须根据x m l 数据的模式为其设 计若干子模式做为存储x m l 数据的表模式。使用关系数据库管理x m l 数据主要 包含以下几个步骤： 1 为x m l 数据定义合适的表模式，并将其存储到关系表中。 2 利用文档d t d 信息和文档本身的信息将x p a t h ( x q u e r y ) 查询语句转化为 s q l 语句。 3 查询优化，查询执行。 4 将查询结构以x m l 的格式提交给用户。 使用关系数据库技术来管理x m l 有两个比较明显的缺点，一是x m l 数据是半结 构化的，而关系表是二维表结构，存储和查询都不可避免的要在两种格式之间相 互转化。另外，x m l 查询语言支持许多复杂的语义，比如正则表达式中的闭包操 作符，这在s q l 中是找不到与之对应的部分的，要想解决这个问题，避免不了要 做多次表连接操作，查询效率会受到很大的影响。 o d m g 标准为面向对象数据库定义了对象模型( o b j e c t m o d e l ) ，对象定义语言 f o d l ) 和对象查询语言( o q l ) 。因为x m l 在描述数据时采用在不同层次上的嵌套 关系，理论上将这种树形结构数据映射为嵌套对象模型比映射为关系表更为自然， 而且对象路径查询也与x m l 数据的遍历策略很相似，因此一些系统采用了对象技 术来管理x m l 数据。由于对象数据库在高效地处理大规模数据方面相对于关系库 来说还不成熟，因此还有很多需要完善的地方。 x m ln m i v e 数据库技术以斯坦福大学的l o r e 系统 2 1 为代表，其它比较著名 的还有t a m i n o ，t i m b e r 2 0 1 等。这些系统专门为x m l 这一特殊的数据类型设计存 储模型与索引技术。对于x m l 路径表达式的查询处理，比较典型的是三种基于 d a t a g u i d e s 的查询算法，自顶向下( t o p d o w n ) 、自底向上( b o t t o m u p ) 和混合策略 ( h y b r i d ) 。自顶向下方法是从一个x m l 文档树的根节点开始遍历直到找到f 确的 结果；自底向上则是借助值索引的帮助从文档树底部向上遍历直到根节点；而混 合策略则是首先把一个长路径分割成若干子路径，对每个子路径可以使用自顶向 f 或自底向上计算，最后对所有子路径结果做基于元素父子关系的连接操作，以 得到最终结果。由于x m ln a t i v e 数据库采用了针对x m l 本身特点而设计的存储 方案和查询策略，因此，虽然它现在还不算成熟，但被认为是四种方案中最有前 5 东北失学硕士举位论文 第一章前言 途的熊决方案。 。3 x m l 查诲语言 随着利用x m l 格式存储和表示的信息闷益增多，在各种各样的x m l 数撼源中查询x m l 数据的需求也越来越迫切。x m l 的提i i j 是为了烫活酌表示不 同数据源的不同信息。为了使这种灵活性得到最大程度的发挥，研究者设计了许 多x m l 查询语言来从x m l 中查询数据。葜牢最有代表惶静是w 3 c 发希的x m l 路径语言x p a t h 和x m l 查询语言x q u e r y ，它们首先为x m l 文档提供一个数据模 型，并且撬檄了一缀基于这个模型静查询搡傣。x p a t h 是x q u e r y 静一个子鬃。 1 、3 1x p a t h 规范 x p a t h 4 1 提供了关于路径导航( p a t hn a v i g a t i o n ) ，节点定位( n o d el o c a t i o n ) ，谓调选 择等方瑟戆一份穰确靛蕊蓬，荠置狻 乍为x q u e r y 熬核心部分。x p a t h 中最纛要豹 组成部分是怒位路径( 1 0 c a t i o np a t h ) ，具体分为绝对定位路径( a b s o l u t el o c a t i o np a t h ) 窝撵对定霞鼹径( r e l a t i v el o c a t i o np a t h ) 涮。蓠者燕簌辍苇纛到菜令节纛熬爨径， 后者是从当前选定的节点的路径到巢个节点的路径。在x p a t h 中，路径表达式是 冀棱心蕴藏部分。对予一个鼹径表达式，哥苏写袋p a t h ：= ( s t e p ) * 魏形式，瑟每个s t e p 又可以定义为s t e p ：= a x i s ：n o d e t e s t p r e d i c a t e 的式。在每个s t e p 中，轴( a x i s ) 专 门撵定了文楼定位懿“方自”。x p a t h 支持l 静寇位辘不考虑a t t r i b u t ea x i s 弱 n a m e s p a c ea x i s ) 。节点测试n o d e t e s t 指选择x m l 文档中满足该模式的节点。谓词 p r e d i c a t e 遴一步限制了节袁溅试黪选择范曩。x p a t h 中的辘分戏隧类：浆囱轴 ( f o r w a r d a x i s ) 和反向轴( b a c k w a r d a x i s ) ，其中前向轴包括c h i l d ，d e s c e n d a n t ，s e l f ， d e s c e n d a n t - o r - s e l f ，f o l l o w i n g - s i b l i n g ，f o l l o w i n g 共6 个辘；反向辘包括p a r e n t ， a n c e s t o r ，p r e c e d i n g s i b l i n g ，p r e c e d i n g ，a n c e s t o r - o r - s e l f 。本文以讨论前向轴为主。 x p a t h 昶x q u e r y 中最繁本的构筑部分怒表达式。它们掇供了若于弛表达式， 这些表达式由关键字、符号和操作数组成。通常情况下，一个表达式的操作数是 另外一个的裘达式。x p a t h 秘x q u e r y 是函数性的查询语言，它们允许多种袭达式 任意层次的嵌套。同时，它们也是强类型的语言，其表运式中的操作数、搡作符 和函数等等必须对皮有特定的类型。 在x p a t h 中，有以下类型的表达式： 1 主表达式( p r i m a r ye x p r e s s i o n s ) 。主表达式是x p a t h 诺言的基本原语，包括变 量、字砸量、溺数调用等等。 2 路径表达式( p a t he x p r e s s i o n s ) 。路径袭达式是x p a t h 语言的核心，它用来在 。6 东北大学硕士学位论文第一章前言 x m l 树上定位结点，按照文档序返回一个不重复的结点序列。路径表达式的 计算必须依靠表达式上下文。 3 序列表达式( s e q u e n c ee x p r e s s i o n s ) 。序列表达式用来在x p a t h 语言中构筑和 合成序列，序列是一个包含零个或更多元素的有序集合，序列中的元素可以 是一个简单的值或者是一个结点。 4 算术表达式( a r i t h m e t i ce x p r e s s i o n s ) 。算术表达式提供了x p a t h 语言中的加、 减、乘、除等运算。 5 比较表达式( c o m p a r i s o n e x p r e s s i o n s ) 。比较表达式用来支持“大于”、“小于” 以及判等等一系列的比较运算。在x p a t h 中，比较运算包括值的比较、序列 的比较、文档结点的比较以及文档序的比较等等。 6 逻辑表达式( l o g i c a le x p r e s s i o n s ) 。逻辑表达式表示逻辑上的与、或、非等运 算，返回值是一个逻辑值。 7 迭代表达式( f o r e x p r e s s i o n s ) 。x p a t h 提供了迭代表达式用来执行迭代运算， 这种表达式经常用来计算两个或者更多文档之间的连接以及数据的重构。 8 条件表达式( c o n d i t i o n a le x p r e s s i o n s ) 。条件表达式允许根据不同的条件而使 表达式返回不同的值。 9 量词表达式( q u a n t i f i e de x p r e s s i o n s ) 。量词表达式允许通过全称量词或存在量 词测试表达式的值，其返回结果是一个逻辑值。 1 3 2x q u e r y 简介 x q u e r y 被设计成用来实现w 3 c 的标准“x m l 查询要求”( x m lq u e r y 1 0 r e q u i r e m e n t s ) 。x q u e r y 是一种小的、易于实现的语言，用它来表示的查询简单并 且容易理解。x q u e r y 十分灵活，可以在包括数据库和文档的多种x m l 数据源之 上进行查询。x q u e r y 的1 0 版本包含了x p a t h 的2 0 版本作为它的一个子集。所 有在x q u e r y l 0 和x p a t h 2 0 中语法上均有效而且均可成功执行的表达式，在这两 种语言中必然得到相同的结果。由于这两种语言有着如此紧密的联系，它们在语 法和语言的描述以及数据模型的表示上都是统一的。 x q u e r y 中包含了上面描述的x p a t h 中的所有表达式，除此之外还包括f l w r 表达式和排序表达式等等。 1 3 3 正则路径表达式 路径表达式查询是x m l 查询最基本的要求，几乎所有的x m l 查询语言的核 山都是基于路径表达式的查询，而且很多关于x m l 的查询处理器都是针对路径表 茎查奎兰塑查兰竺笙查 ： 茎二主蔓主 - _ - - m h _ _ _ _ _ w w _ _ _ - v h _ _ _ _ _ - - _ w m w _ _ ，_ _ _ _ m u 一一 一 达式的。各种查询语言及查询处理器使用的路径表达式基本上很相似，其中最常 使用的就魁使用f 则路径表达式( r p er e g u l a rp a t he x p r e s s i o n ) ，正则路径表达式是 玉刘表达式在路径查谗巾簿应溺，冀形式哥以翔表1 3 定义： 从表1 3 中我们可以看出，一个r p e 可 能是一个绝对的r p e ( a b s t r p e ) 也可能是 表1 3r p e 的b n f 定义 个相对的r p e ( r i w r p e ) 。一个绝对蛉 r p e 表示爻曹文挡查询要从x m l 文档船根元 素开始，而一个相对的r p e 可能从x m l 文 档中的任一位置开始查渤，查询的具体位置 要蔽据查壤时懿上下文动态决定。在淡示形 式上，绝对的r p e 由表示根元素的符号“” 和一个相对的r p e 表示。无论是绝对的r p e 还是褶对的r p e ，都是由r p e s t e p 和r p e 操作餐秘袋豹。r p e s t e p 表示了r p e 森谗中 的个单一操作，如取得某个元素结点的孩 子，或者取得这个结点的指定名字的属性结 点等。一个r p e s i e p 哥缝带毫限定部分，限 定帮分表示了一些比较簸杂的搡作，其中最 常见的就鼹谓词。在查询处理中，谓词意味 着对阶段性的查询结果根据制定的祭件执 t a b l e1 3b n f s y n t a xo fr p e r p e ：_ _a b s t r p e r i i v r p e a b s t r p e ：=，r l l v r p e r l t v r p e ：=r l t v r p e1 ，r l t v r p e r l t v r p e 。1 1r i i v r p e | 魏l l v r p e w i r f l v r p e + i ( r i t v r p e ) 1 lr p e s t e p r p e s t e p ：= s m p l r p e s t e p n o d e q u a l i f i e r ) s m p l r p e s t e p ：= n a m e l n a m e l t e x t ( ) n o d e q u a l i f i e r ：= t p r e d i c a t e 】 李亍过滤撩俘。r p e 撩 擘籀霜亲把r p e s t e p 合成复杂蠡每r p e ，这臻搽俘害孥蹶饯表懿 运算可以任意嵌套，怒完全正交的。r p e 中常见的操作符和它们所代表的意义如 表1 4 所示。 w 3 c 蛉标准x p a t h 电是一种基予路径 表达式静裘途语言，x p a t h 匏路径表示菲辜 类似于上丽定义的r p e ，最明显的麓别是 x p a t h 中没有闭包运算( 没有“”和“+ ” 这两令撩髂符) ，取代它们黥是 a n c e s t o r d e s c e n d a n t 谍作符“”，它代表了 x m l 文档中结点的毫h 先后代关系，如 “s i t e i t e m ”就表示所有具有“s i t e ”祖先的 名秀“i t e m ”靛结点。 表1 , 4 r p e 操作符 t a b l e1 4r p e o p e r a t o r s 操作搡怍符的意义 符 ，连蓰薅条路经 | 台并两条路径( 或揉 ：) 闭包运算( 零次或多次) +1 空闭包运算( 次或多敬) ( ) 数变表运戴优先缀 东北大学硕士学位论文第一章前言 用模式自动机来解决“”和在模式空间中遍历路径模式树来解决“”的两种方 法，这两种方法都不需要人为去统计文档信息d 1 4x m l 路径查询概述 1 4 1 包含连接技术简介 在处理路径查询的各种方法中，x m l 文档树遍历是最基本，最简单的一种。 它以某种特定的顺序遍历并检查x m l 文档树中的每个节点，看其是否满足给出的 查询表达式。不难看出，x m l 文档树遍历的方法查询效率是很低的。另外一种比 较流行的处理方法是包含连接( c o n t a i n m e n tj o i n ) 的方法，人们通常也称其为结 构连接。采用包含连接方法的基本思想如下： 1 先对x m l 文档树中的每个节点进行编码并将编码存储在数据库中。 2 将一条查询语句分解成若干个二元关系查询( 即父子关系和祖先一后代关系) ， 对每一个二元关系进行计算，得到查询的结果。 3 ，将2 中得到的结果连接起来得到最终结果。 为了解决上面的第2 环节，在文献【3 1 中提出了一种传统的关系数据库中的归并连 接算法的变体，称为多谓词归并连接算法( m p m g j n ) 。该算法依赖于将x m l 文档 中的每个元素按( s t a r t p o s ，e n d p o s ，l e v e l ) 三元组编码得到的索引结构，实验证明，在 关系数据库中，m p m g j n 算法比传统的归并连接快一个数量级左右。 在执行每个二元关系查询时通过索引对节点的编码进行访问，并按照特定的 连接算法( 如m p m g j n ) 进行连接。通常将参与连接的两个集合分别称为祖先集 合( a l i s t ) 和后代集合( d l i s t ) 。参考文献【2 3 1 咔，提出了一种遍历两个集合各一次就可以 找到连接全部结果的高效s t a c k t r e e 算法。后来研究者们进一步提出了一些索引结 构如b + 树 和x r 树【2 1 来进一步提高s t a c k t r e e 算法的效率，其基本思想是在查 询过程中通过索引来跳过一些一定不