（计算机科学与技术专业论文）面向xquery语言的xml树模式整体匹配方法的研究.pdf

1jj 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：盔叠兰鱼 导师签名： 摘要 摘要 随着因特网的普及与发展，m ，语言被普遍用于异构信息和异构平台的数 据交换和数据共享。为了推动) a l 数据查询和处理的标准化，国际万维网组织 w 3 c 组织发展了x q u e 巧语言，并将其作为l 数据查询语言标准发布。鉴于 x m l 数据的半结构化特征和x q u e 巧语言的函数式语言特征，高性能的l 查 询处理与x q u e r y 语言实现技术得到了普遍的重视，近年来已经成为数据库技术 领域的研究热点之一。 ) a l 文档不同于关系数据，具有半结构化的特点。标准的x m l 查询语言所 表示的查询请求中，很大程度都是针对讧l 数据的结构特征进行查询。t w i g 查询技术能够综合讧l 查询中的树结构特征形成模式树，利用模式匹配等算法 完成高效的处理。在众多x m l 查询处理技术中，t w i g l i s t 等整体查询匹配方法 由于很好地利用了) q 订l 数据的树结构特征，成为了高性能x q u e r y 实现技术的 核心技术之一。 本文分析了t i g 整体查询匹配算法的发展现状及其存在的问题，解决了在 x q u e r y 引擎中引入t w i g 整体查询匹配方法所带来的问题。首先，通过对t w i g “s t 算法进行扩展，提出了新型的t w i g l i n k e d l i s t 算法，解决了查询结果的顺序问题， 并且针对t w i g 查询中父子关系的处理进行优化，进一步提高了查询的效率。随 后，本文提出了引入t w i g 查询后的枚举方法以及谓词的处理方法，使得t w i g 查询模块可以高效地集成在x q u e u 引擎中。 针对t w i g 查询的执行时间与内存使用情况，对扩展前后的t w i g l i s t 算法进 行了测试。实验结果表明，t w i g l i i l l ( e d “s t 算法有效地减少了冗余的中间结果， 从而提高了t w i g 查询效率，有效地支持了x q u e r y 语言的高性能实现。 关键词x q u e r y ；t w i g 查询；谓词处理 北京工业大学工学硕士学位论文 i i | 一 一 _ 卜 k a b s t r a c t w i t ht h ep o p u l a r i z a t i o na n dd e v e l o p m e n to ft l l ei n t e m e t ，蹦l i sw i d e l yu s e di n h e t e r o g e n e o u sp l a t f 0 皿sa n dd a t ae x c h a l l g e s h a r ef o rh e t e r o g c n e o u si n f o m l a t l o n h l o r d e rt 0s t a l l d a r d i z e d ) 口lq u e r ya n dp r o c e s s i n g ，m ew o d dw i d ew 曲c o n s o r t i 啪 ( w 3 c ) d e v e l o p e dx q u e a i l d r e l e a s e di t 猫as t a l l d a r dq u e 巧l 觚g u a g ef o rx 】ld a t a 、聃t ht h ec o n s i d e r a t i o no ft 1 1 es e m i s 伽l c t u r e dc h a r a c t e r i s t i co fx m ld a t a 砒l dm e 向n c t i o n a l l a n 聃a g ef e a t u r eo fx q u e h i g l l p e r f o 姗a i l c ex m l q u e 巧p r o c e s s m g 锄d x q u e r yl a l l g u a g ei m p l 锄e n t a t i o nt e c l l l l o l o g y g a i n c dw i d e s p r e a da t t e n t i o n ，a i l d b e c 锄eap o p u l a rr e s e a r c ht o p i co fd a t a b 嬲et e c l l i l o l o g ) ，i i lr e c e n ty e a r s b e i n gs e m i s t m c t u r e d ，x m ld a t ai sd i 彘r e n t 舶mr e l a t i o n a ld a t a m o s tp a r t so f q u 甜e se x p r e s s e di ns t a n d a r d 压lq u 吖l a n g u a g ef o c u so ns t m c t u m lf e a t u r e o t x m ld a t a t w i gq u e r yc 孤f o mp a t t e mt r e ea c c o r d i n gt 0t h et r e es t m c t u r a lf e a t u r em x m l q u e r i e s ，a j l dp r o c e s si te f r e c t i v e l yu s i n gp a t t e m m a t c h i n ga l g o r i t s a m o n g t h em a l l y 订lq u e r yp r o c e s s i n gt e c h n i q u e s ，h o l i s t i cm a t c h i n ga p p r o a c hs u c h a s t w i g l i s th a sb e c o m eo n eo ft h ec o r et e c t l o l o 西e s i nh i 曲一p e r f o m a n c ex q u e r ) ， i m p l e m e n t a t i o nt e c h n o l o g yb e c a u s ei tm l l ye m p l o y e dt h et r e es t r u c t u r a l f e a t u r eo f x m l d a t a t h i sp a p e ra n a l y z e dt h ed e v e l o p m e n ta n dp r o b l e m so fh o l i s t i ct w i gm a t c h i n g a l g o r i t h m s ，r e s o l v e dv 撕o u si s s u e s a n e ri n t r o d u c i n gt w i gm a t c h i n gi n t ox q u e r y e n g i n e f i r s to fa l l ，w ep r o p o s e dan o v e lw a y t oh a n d l eb o t hm eo u t 。0 0 0 r d e m e s s1 s s u e a n do p t i m i z a t i o no fp a r e n t c h i l dr e l a t i o n s h i pb yi m p r 0 v i n gt w i g l i s t ， n 锄e d t 叭g l i n k e d “s t s u b s e q u e n t l y ， w er 印r e s e n t e da ne n u m e r a t l o nm e t h o da n d a n a p p r o a c hd e a l i n gw i t hp r e d i c a t ea r e ri n t r o d u c i n g1 1 w i gq u e 哆t h e s e m a d ei te f f e c t i v e f o r t w i gq u e r ym o d u l et ob ei n t e 伊a t e di n t ox q u e r ye n g i n e o u ra l g o r i t h mw a st e s t e da g a i n s tt w i g l i s ti nt e n n so ft h eq u e r yp r o c e s s l n gt l m e a i l dm e m o r yu s a g e e x p e r i m e n t a l r e s u l t ss h o w e dm a t ，t w i g l i l l l ( e d l i s ta l g o r i t c a n r e d u c et h er e d u n ( 1 a n ti n t e m l e d i a t er e s u l t s ，t h e r e b ye n h a n c et h et w i gq u e r ye f l i c l e n c y ， a i l ds u p p o r tf o r h i 曲p e r f o 姗a i l c ei m p l e m e n t a t i o no fm ex q u e r y1 a n g u a g e k e y w o r d sx q u e r y ；t i gq u e r y ；p r e d i c a t e u i 北京工业大学工学硕士学位论文 i v i 一 目录 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 课题背景1 1 2 研究意义2 1 3 研究背景一3 1 3 1x q u e r y 实现的研究现状3 1 3 2t w i g 查询技术研究现状3 1 4 课题来源4 1 5 本文的研究工作和主要贡献4 1 6 本文组织结构5 第2 章t w i g 查询与x q u e r y 查询引擎7 2 1x q u e r y 语言7 2 1 1x m l 语言7 2 1 2x q u e r y 简介8 2 2t w i g 查询1 0 2 2 1t w i g 查询简介1 0 2 2 2t w i g 查询与x q u e r y l 1 2 3 支持t w i g 查询的x q u e r y 查询引擎1 2 2 3 1g e o q u e r y 系统简介1 2 2 3 2g e o q u e r y 系统的体系结构1 3 2 3 3g e o q u e u 系统查询处理流程1 4 2 3 4 对t w i g 查询的支持：f x q l2 0 1 5 2 3 5 案例1 6 2 4 本章小结1 7 第3 章t w i g 查询算法的研究1 9 3 1t w i g 查询算法介绍1 9 3 1 1t w i 9 2 s t a c k 算法1 9 3 1 2t w i g l i s t 算法。1 9 3 1 3t w i g m i x 算法和t w i 萨a s t 算法2 0 3 1 4t w i g 查询算法需要解决的问题2 0 v 北京工业大学工学硕七学位论文 3 2t 州g “s t 算法2 0 3 2 1t w i g l i s t 算法简介2 0 3 2 2t w i g l i s t 数据结构与算法2 1 3 3t w i g l i n k e d l i s t 算法2 2 3 3 1 解决顺序问题2 3 3 3 2 针对p c 关系的优化2 5 3 4 枚举结果2 7 3 4 1 基于变量的枚举方法2 7 3 4 2t w i g l i n k e d l i s t 枚举算法2 8 3 5t w i g 查询模块的设计与实现3 1 3 5 1 类体系设计3 1 3 5 2 类的具体设计3 2 3 6 本章小结3 9 第4 章t w i g 查询中的谓词处理4 1 4 1 谓词处理介绍4 1 4 1 1 谓词简介4 l 4 1 2g e o q u e 巧系统中的谓词处理4 l 4 2t w i g 查询中谓词处理的关键问题4 2 4 3 4 4 第5 章 5 1 5 2 4 2 1 处理时机问题4 2 4 2 2 谓词顺序问题4 3 4 2 3a d 关系中谓词的处理4 3 4 2 4 谓词处理对t w i g 查询结果的影响4 3 谓词处理的实现4 4 4 3 1 谓词处理的方案4 4 4 3 2 谓词处理的实现一4 4 本章小结4 5 系统测试4 7 测试方案4 7 5 1 1 数据集4 7 5 1 2 测试指标4 7 5 1 3 测试用例4 8 测试结果与分析4 8 5 2 1d b l p 数据集上的测试4 8 5 2 2x m 破数据集上的测试4 9 5 2 3t r e e b a n k 数据集上的测试4 9 v i 目录 5 3 本章小结5 0 结：沦51 参考文献：5 3 攻读硕士学位期间发表的学术论文5 7 致谢5 9 v i i 北京工业大学工学硕士学位论文 v i i i 第1 章绪论 1 1 课题背景 第1 章绪论 伴随互联网的繁荣，讧l 【卜3 】( e x t e i l s i b l em a r k u pl a l l g l l a g e ，可扩展标记语 言) 从国际万维网组织w 3 c 提出的规范成长为了互联网上数据描述与交换的事 实标准。目前，删l 凭借着其内容与形式分离、易于扩展和易于移植等诸多特 点，已经被广泛地应用于分布式计算、电子商务、电子政务等很多领域。 越来越多的数据都由以l 来表示、保存，人们急需能够高效查询和处理l 的方法。1 9 9 9 年w 3 c 发布了，a c h1 0 【4 】推荐标准。此标准用于在x m l 文档中 定位和查找信息。a t h 虽然可以满足简单的对煳l 处理的需求，但是无法表 示复杂的算法逻辑。因此，w 3 c 发展了x q u e 巧语言【5 6 】( lq u e r yl a n g u a g e ) ， 用于标准化x m l 的查询和处理，并于2 0 0 7 年1 月将其作为x m l 数据查询语言 标准发布。 x q u e r y 语言是一套针对订l 数据的查询语言。它在x m l 处理领域的作用 类似于s q l 语言在关系数据库领域的作用。x q u e r y 语言具有灵活强大的查询功 能，同时，它又具有函数式语言的特征，能够对l 数据进行十分复杂的处理。 尽管x q u e 珂语言面世不久，它已经成为了x m l 领域的研究热点。人们正在积 极研究数据集成、x m l 数据流和x m l 数据库等环境下x q u e r y 的优化实现技术。 同时，鉴于该语言具有较强的程序描述能力，适用于描述应用业务逻辑，人们试 图将其发展为新型的软件开发语言，扩展语言功能，发展专用开发环境与工具。 在x q u e r y 语言相关的研究中，如何高效地实现x q u e r y 语言，提高查询效 率是研究的核心问题之一。在各种x q u e r y 的优化手段之中，基于t w i g 查询( 小 枝查询) 的方法是最重要的研究方向之一。) a l 文档不同于关系数据，具有半 结构化的特点。x q u e w 语言表示的查询中，很大程度都是针对l 数据的结 构特征进行查询。t w i g 查询技术能够综合x q u e r y 查询中的树结构特征形成模式 树，利用模式匹配等算法完成高效的处理。通过t w i g 查询，可以减少查询处理 过程中冗余的中间结果，从而提高查询效率。本课题组针对x q u e r y 语言的函数 式语言的特点，设计并实现了一套以函数式语言f x q l ( f u n c t i o n a lx m lq u e r y l a n g u a g e ) 为中间语言的x q u e r y 查询引擎g e o q u e r y 系统【m j 。在f x q l 的 基础上，实现了去相关性的优化【l o j 、动态编译的优化【l l 1 2 】和基于部分求值的优化 【1 3 椰j ，并且扩充为基于延迟求值【1 8 1 的x q u e 巧查询引擎。本文将就t w i g 查询算 法在g e o q u e r y 系统上的实现与优化展开研究，给出解决方案。 北京工业大学丁学硕士学位论文 1 2 研究意义 l ( e x t e n s i b l em a r k u pl a n g u a g e ) 是由w 3 c 提出和维护的数据交换标准， 是一种平台无关的数据表示方法。自提出之日起，订l 在很短的时间内便渗透 到了i t 相关的各个领域。 在x m l 广泛应用于以互联网为主的各个领域的今天，如何对x m l 数据进 行高效的处理是摆在学术界与工业界面前最重要的问题之一。x q u e r y 语言的发 布无疑对这个问题给出了一流的答案。x q u e r y 语言不仅汲取了s q l 语言的精华， 能够灵活的表示各种查询需求，而且它的函数式语言的特点更加强了它描述复杂 算法逻辑的能力。业界的许多公司、组织都推出了自己的x q u e r y 实现，如o r a c l e 的x m ld b f l 9 ，2 0 1 、m 的d b 2p u r e x m l 【2 1 _ 2 3 】等等。随着基于x m l 的应用规模 越来越大，使得相应的x q u e r y 程序愈加复杂。因此，x q u e r y 程序执行效率的 高低变得十分重要，如何通过优化手段提高查询效率具有很重大的研究意义。目 前，x q u e r y 语言实现技术的研究一直十分受人关注。 x q u e 巧语言是一种x m l 查询语言，其地位类似关系数据库中的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 q u e r y 实现的优化。 值得注意的是，x q u e r y 语言所查询的目标x m l 语言不同于关系数据，它具 有半结构化的特性。一个x m l 文档可以表示为一棵以标签为节点名的树，叫做 l 文档树。v i l 的查询语言x p a t h 、x q u e r y 中最重要的查询就是通过轴操 作等方法对l 的结构特征进行查询。因此，任何的对于x q u e r y 的优化实现 技术只有充分考虑到x m l 的结构特征，才能达到最佳的效果。在众多的优化手 段之中，基于t w i g 查询的优化方法正是此类方法。它很好地利用了x m l 数据 的结构特征，成为了x q u e r y 优化方面的核心优化方法之一。t w i g 查询技术能够 将x m l 查询中的结构特征进行综合形成模式树，利用模式匹配等算法高效地处 理。t w i g 查询不仅能够有效地减少求值过程中的中间结果，而且可以减少对l 文档的扫描次数，从而显著提高查询效率。鉴于t w i g 查询对x q u e r y 优化的重 要意义，已有许多研究集中在如何提高t w i g 匹配算法的效率和对t w i g 查询进行 扩展并引入到x q u e r y 实现系统中。 第l 章绪论 1 3 研究背景 1 3 1x q u e 巧实现的研究现状 x q u e 巧语言已经成为w 3 c 的推荐标准，目前已有很多x q u e r ) r 引擎的实现。 按照实现过程中是否引入查询代数可以大致分为两类。 一类研究中未引入查询代数。由x m l r n i n d 提供的q i z ) 【o p e n 【2 4 】是一个开源的 x q u e r y 引擎，基本实现了x q u e d ，规范的特性。q i z ) ( o p e n 采用纯解释实现，无 查询代数或中间语言。b e as 骶锄i n gx q u e r y 肌百n e 【2 5 】是一个高性能的讧l 流 查询引擎。它直接将x q u e r y 编译为查询计划，并无查询代数。这些x q u e r y 引 擎由于没有使用查询代数或中间语言，很难实现复杂的优化方法。 另一类研究中引入了查询代数。这类x q u e r y 引擎将x q u e r y 程序翻译为一 颗由查询代数操作符组成的树，然后根据相关的重写规则进行优化，随后生成查 询计划树，最后进行求值计算。如f l u x q u e 2 6 1 ，g a l a x 【2 7 2 8 1 ，b i z q u e r y 【2 9 1 ， o r i e m x 3 0 1 ，o r a c l e v i l d b 等。这些x q u e r y 查询引擎的实现主要做一些关于查 询代数的查询重写。 另外，有些研究的重点是查询代数，而非引擎的实现。贝尔实验室采用函数 式语言h a s k e l l 【3 1 1 作为描述方法提出了一种查询代数【3 2 】。有些研究采用编译的方 法实现x q u e r y 语言。q e x o 【3 3 3 4 j 是q 叮u 实现的x q u e 巧执行引擎，它部分实现 了x q u e r y 语言jq e x o 使用了编译实现的方式，将一个x q u e r y 源程序编译为可 执行的j a v a 字节码，并加载到j a v a 虚拟机中执行。 1 3 2t w i g 查询技术研究现状 t w i g 查询是x m l 查询中重要的优化手段。为了将t w i g 查询引入x q u e r y 查询中，有些研究工作【3 0 ，3 5 ，3 6 】尝试将t w i g 查询操作结合到查询代数当中。其中 t a x f 3 5 】提供了一组基于树模式的代数算子，通过模式树和实例树( w i t n e s st r e e ) 的 概念来表示树查询。但t a x 中的模式树存在一定的局限性，难以表示x q u e r y 查询中的复杂谓词表示，而且难以实现去除相关性等基于元组的逻辑优化。 o r i e n t x a 代数在简单的模式树基础上扩充了强绑定、弱绑定、节点绑定与序 列绑定的概念，增强了模式树的描述能力，并且引入了用于结果构造操作的算子。 但同样难以实现去除相关性等基于元组的逻辑优化。m i c h i e l s 方法p 6 j 能够将树模 式结合到查询代数中，在基于元组的查询代数中扩充了树模式算子。该方法对树 模式有一定的限制，要求树模式只能有单一的输出节点。 另外，很多研究工作都通过各种不同的数据结构和算法提高t w i g 查询的效 北京工业大学工学硕士学位论文 率。早期的t w i g 查询算法【3 7 ，3 8 】先将t w i g 查询分解为不同的查询路径，再对每条 路径分别求值，最后合并结果。这种方法会产生大量的中间结果，从而影响t w i g 查询的效率。为了减少中间结果，h o l i s t i c 觚i gp a t t e mm a t c h i n g 【3 9 】被提了出来。 此方法利用t a gs t r e a m i n g ( 标签流) 【4 0 】，通过一个递归的函数洲赢彬保证算 法在处理t w i g 查询中的“祖先后代”关系时是最优的。然而，如果t w i g 查询中 含有“父亲孩子”关系时，此方法仍会产生大量的冗余中间结果。 为了解决过去t w i g 查询算法的问题，t w 霄s t a c k 算法【4 i j 引入一种叫做层次 栈( h i e r a r c h i c a l s t a c ke n c o d i n gs c h 锄e ) 的数据结构来描述t w i g 查询的结果。这 种层次栈的结构可以同时保存讧l 节点间的“祖先后代 和“父亲孩子 关系。 在t w i 9 2 s t a c k 算法中，通过构建算法将匹配t w i g 查询的x m l 节点保存到层次 栈中，然后利用枚举算法得到t w i g 查询的结果。t w 留s t a c k 算法有效地解决了 中间结果较多的问题。同时，t 而矿s t a c k 算法支持g e n e m l i z e d 1 r e e p a t t 锄( g t p ) 查询 4 2 1 。所谓g t p 查询是在t 丽g 查询的基础上进行了扩充，能够更好地描述 x q u e r y 查询。 与此同时，l uq i i l 提出了t w i g l i s t 算法【4 3 】。与t w i 9 2 s t a c k 算法类似，t w i g l i s t 算法同样通过构建算法将x m l 节点保存在特定的数据结构中，并通过相应的枚 举算法得到结果。t w i g “s t 由于采用简单高效的线性表数据结构取代了复杂的层 次栈结构，从而提高了算法的效率。j i a n g “和j u n h uw 抽g 在t w i g “s t 的基础上， 结合t a gs t r e 锄i n g ，提出了t w i g m i x 和t 叭萨a s t 算法【4 4 】，进一步提高了t w i g 查询的效率。 1 4 课题来源 本研究得到北京市自然科学基金( 项目编号：4 0 8 2 0 0 3 ) 的支持，项目名称： x q u e r y 语言动态编译技术的研究。 1 5 本文的研究工作和主要贡献 本文的主要研究工作是基于t w i g 查询的x q u e r y 查询优化技术，在原有的 x q u e r y 执行引擎g e o q u e r y 的基础上进行研究。 本文的研究工作包括以下内容： 1 通过扩展t w i g l i s t 算法，设计了t w i g l i n k e d “s t 算法。此新型的 t w i g l i l l l ( e d “s t 算法解决了查询结果的顺序问题，并且针对t 叭g 查询中的父子 关系进行优化，进一步提高了查询效率。 2 在g e o q u e r y 系统上实现t w i g “n k e d “s t 算法。设计了g e o q u e r y 系统 t w i g 查询模块的体系结构，并且分别实现了每个子模块，完整地实现了 第1 章绪论 t w i g l i l l l ( e d l i s t 算法。 3 在t 丽g l i l l l 【e d l i s t 的基础上，实现了对谓词的处理。首先对谓词处理中 遇到的各种问题进行了研究，并给出了相应的解决方案。然后在t w i g l i i l l 【e d l i s t 的基础上实现了对谓词的处理。 4 通过测试对比t w i g l i s t 算法扩展前后的执行效率。针对t w i g 查询的执 行时间与内存使用情况，对扩展前后的t w i g l i s t 算法进行了测试。实验结果表明， t w i g l i i l l 【e d l i s t 算法有效地减少了冗余的中间结果，从而提高了t w i g 查询效率， 有效地支持了x q u e 巧语言的高性能实现。 本文的主要贡献为：提出了一种新型的t w i 豇i 1 1 l ( e d l i s t 算法，并在g e o q u e 巧 系统上予以实现。通过分析处理谓词中的关键问题，提出解决方案并实现。通过 测试表明t w i g l i n k e d l i s t 算法有效地提高了查询效率。 1 6 本文组织结构 本文内容组织如下： 第一章介绍本课题的背景，研究意义，相关工作以及课题的来源。 第二章本章首先介绍了x q u e r ) r 语言和t w i g 查询技术，然后介绍本实验室基 于t w i g 查询的x q u e d r 查询引擎一g e o q u e r y 系统。 第三章首先简介了各种t w i g 查询算法，然后详细介绍了t w i g l i s t 算法，随 后介绍了通过扩展t w i g l i s t 算法而设计的t w i g l i l l l 【e d “s t 算法，最后说明了如何 在g e o q u e 珂系统中实现t w i g l i i l k e d “s t 算法。 第四章主要介绍了如何处理t w i g 查询中的谓词，并给出了在g e o q u e 叫系统 中实现谓词处理的方法。 第五章通过多个测试案例，测试了1 w i g “s t 算法和t w i g l i n k e d “s t 算法的查 询效率，并通过图表的形式进行说明。 最后，在结论部分对全文进行了总结，并分析进一步研究的方向。 北京工业大学t 学硕士学位论文 6 第2 章1 w i g 查询与x q u e r y 查询引擎 第2 章t w i g 查询与x q u e 巧查询引擎 随着l 的广泛应用，为了标准化l 数据查询和处理，国际万维网组 织w 3 c 组织发展了x q u e r y 语言，2 0 0 7 年1 月将其作为订l 数据查询语言标 准发布。同时，x q u e r y 实现技术的研究得到普遍的重视。本课题组针对x q u e 巧 语言具有的函数式语言特点，设计并实现了一套以函数式语言f x q l ( f 眦c t i o n a l 。x m l q u e r ) rl a l l g u a g e ) 为中间语言的x q u e r y 查询引擎g e o q u e 巧系统。 鉴于t w i g 查询技术能够充分利用) a l 半结构化的特点，提高查询效率j 本 课题组在g e o q u e r y 系统的基础上，对中间语言f x q l 进行升级，支持t w i g 查 询。并且，研制了一套基于t w i g 查询的x q u e 巧查询引擎。 2 1 x q u e r y 语言 2 1 1x m l 语言 x m l 是一种简单灵活的文本形式的语言，用于描述各种数据。它是一种标 记语言，通过“标记”计算机可以识别数据中的信息。 1 9 9 5 年x m l 开始形成雏形，并向w 3 c 提案，在1 9 9 8 年2 月发布为w 3 c 的标准( x m l l o ) 。x m l 的前身是s g m l ( t h es t a n d a r dg e n e r a l i z e dm a r k u p l a n g u a g e ) 【4 5 】，是m m 从1 9 6 0 年就开始发展的g m l ( g e n e r a l i z e dm a r l ( u p l a n g u a g e ) 标准化后的名称。 组成x m l 文件的字符被分为标记( m 破u p ) 和内容( c o n t e n t ) 两部分。标 记是指一段由“ ”结束的字符串，或者一段由“& 开始、以“； 结尾的字符串。除了标记以外的的部分就是内容。其中由“ ”结 束的字符串所组成的标记叫做标签( t a g ) 。标签包含三种形式：开始标签 ( s t a n t a g ) ，例如 ；结束标签( e n d t a g ) ，例如 ；和空元素标 签( e n l p t y - e l e m e m t a g ) ，例如 。 由一对开始标签和结束标签组成的文档片段，或者一个空元素标签被称作元 素( e l e m e n t ) 。开始标签和结束标签之间的字符是元素的内容，而且元素之中可 以包含元素( 子元素) 。例如： h e l l o w b r l d 。 在元素的开始标签或者空元素标签中包含的多个名值对叫做属性( a t t 舶u t e ) ， 例如 ，其中包含属性s r c ，用来说明图片的文件名。除 此之外，l 文档中还包含声明信息、注释、处理指令等。表2 1 是一个简单 的x m l 。 北京工业大学工学硕士学位论文 表2 1x m l 样例 t a b l e2 l 蹦l e x 撇p l e t h i si sr 印h a e l s f o l i g n o ”m a d o 彻a ，p a n e di 1 1 1 5 1 l t 叫d a t e 钗d a t e 1 5 1 2 x m l 具有诸多的优点，主要包括：纯文本表示，具有平台无关性；信息内 容与信息的表示分开；自描述性，可以通过d t d ( d o c u m e n t 聊ed e c l a r a t i o n ， 文档类型声明) 和x m ls c h e m a 【4 6 1 定义数据集的结构信息。由于这些优点，x m l 被广泛的用于跨平台的数据交换，数据存储。 2 1 2x q u e r y 简介 随着l 语言被广泛的用来描述不同数据源、不同数据格式的各种信息， 鉴于x m l 语言的半结构化特性和灵活性，人们需要一种十分灵活强大的x m l 查询语言用于从讧l 数据中获取和解释信息。 x q u e r y 语言由w 3 c 的x m lq u e r yw 6 r k i n gg r o u p 设计来应对这些需求。 x q u e 叫语言既简洁易懂，同时又足够的灵活，可以进行复杂的查询。x q u e r y 语 言源于一种叫做q u i l t 的x m l 查询语言，并且借鉴了? a t h1 o 、x q l 、删l q l 、 s q l 、和o o l 的很多特点。2 0 0 7 年1 月2 3 日，x q u e 巧1 o 成为了w 3 c 的推荐 标准。x q u e r y 语言是一种强类型的、函数式语言，支持自定义函数、s c h e m a 导 入等特性。x q u e r y 语言使用x p a t h 2 o 作为在l 文档中导航、选择和提取数 据的子语言。 一个x q u e r y 查询包含一个或多个查询表达式。以下是一些常用的x q u e r y 表达式：f l w r 表达式、p a t h 表达式和条件表达式。 ( 1 ) f l w r 表达式 f l w r 表达式( 读作“n o w e r ”) 是x q u e 巧最常用的表达式类型之一。f l w r 代表“f o 卜l e t w h e r e r e t u l l l ”这四种子句。每个f l 、v r 表达式都有一个或多个 f o r 子句或l e t 子句、一个可选的w h e r c 子句以及一个r e t u m 子句。 下面举一个f l w r 表达式的例子： 第2 章t w i g 查询与x q u e r y 查询引擎 表2 2f l w r 表达式样例 t a b l e2 2f l w re x p r e s s i 叽e x 锄p l e f o r $ ai nd o c ( ”d b o 删”) l e t $ b = $ a m e t a d a t a ， w h e r e $ b d e s 谢p t i o 眺u b j e c 卢”交通” r e t i i m $ b m m e ， $ b d a 上a s o u e t ”e ， $ b d e s c 却t i o i l a r e a 卜：s o u r c e 此例的含义是从x m l 文档d b o x m l 中获取所有s 材龟加c f 为“交通”的掰p 而奶口纪 元素，并按照r e t u m 子句中的形式组织输出。f l w r 表达式类似于s q l 语言中 的s e l e c t - f r o m w h e r e 语句，它们具有相似的功能： ( 1 ) f o r 子句把变量口绑定到l 文档d b o x m l ，把变量6 绑定到口的子结 点的肌p f 扣口幻元素。x q u e r y 中的f o r 子句的功能类似于s q l 中的f r o m 子句。 ( 2 ) l e t 子句定义变量6 。x q u e r ) ，中的l e t 子句类似于s q l 中的定义别名。 ( 3 ) x q u e 巧中的w h e r e 子旬与s q l 中的w h e r e 子句相似。 ( 4 ) r e t u m 子旬构建包含，z 口小p 属性、如纪勋“陀p 聊e 属性和口旭n 元素的s d “坩口 元素。x q u e 秽中的r c t u m 子旬与s q l 中的s e l e c t 子句大致类似，不过它可以 指定比s q l 中丰富得多的结构。 ( 2 ) p a t h 表达式 在x q u e r y 中，p a t h 表达式遵循x p a t h2 o 的语法，使用路径标记“”从x m l 文档中选择感兴趣的结点。可以把l 文档看作是结点树，那么p a t h 表达式描 述了浏览结点树从而找到感兴趣的结点的方式。 上面例子中的$ b d e s c 邱t i o n s u b j e c t 就是_ 个p a t h 表达式。 ( 3 ) 条件表达