（计算机科学与技术专业论文）xquery引擎中twig查询技术研究.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 纠o 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：搦型塑 导师签名：壶盘亟日期：丝! 竺：山 ，0，i 摘要 摘要 随着互联网技术的飞速发展，x m l ( e x t e n s i b l em a r l 叫) l a i l g u a g e ) 已逐渐成为 互联网环境中数据交换和表示的事实标准。如何有效地使用l 并实现对l 数据的查询成为互联网发展的重要课题。 为了标准化x m l 数据查询和处理，国际万维网组织提出了x q u e 叫，并将 其作为x 】l 查询推荐标准。x q u e r y 是一种功能强大的数据查询语言，适用于 各种类型x m l 数据源的查询。它能够从m ，文档中选择并提取数据，并把查 询结果重构为用户所需要的新的x m l 文档。x q u e r y 语言具有良好的查询能力、 数据组织能力和算法描述能力，其应用领域也越来越广泛。x q u e r y 语言的实现 与应用技术逐渐成为一个重要的研究方向。 x m l 数据具有半结构化的特点。x q u e w 所表示的查询请求中，大量任务是 针对x m l 数据的结构特征进行查询。t w i g 查询技术根据l 数据的树形结构 采用模式匹配的方法来获取查询结果。目前t w i g 查询已经成为x m l 查询研究 的一个热点问题，已有的研究提出了一些关于树模式匹配的查询算法，如 t w i g s t a c k 、t w i 9 2 s t a c k 和t w i g “s t 等。为增强t w i g 查询树模式的表达能力，已 有的研究提出了一种新的树模式一通用树模式( g e n e r a l i z e dt r e ep a t t e m ，简称 g t p ) 。 本文对x q u e w 语言的实现技术展开研究，为x q u e r y 引擎扩展t w i g 查询的 功能。在研究中，采用g t p 查询来取代传统的t w i g 查询，并根据g t p 查询对 弱绑定和分组枚举等功能需求，改进t w i g “s t 查询算法。同时将t w i g 查询功能 嵌入到查询计划描述框架中。对x q u e r y 的查询计划描述语言f x q l 进行扩展， 使其能够描述t w i g 查询功能，并为x q u e 拶引擎设计并实现一个专用的t w i g 查 询模块。 本文对t w i g 查询模块进行了功能测试和性能测试。实验结果表明：扩展后 的x q u e r y 引擎能够有效地支持t w i g 查询，且执行性能也得到了提升。 关键词x q u e r y ；t w i g 查询：g t p 查询 北京工业大学1 二学硕十学位论文 a b s t r a c t a b s t r a c t a st h ei n t e m e tt e c h n o l o g yh a sd e v e l o p e dr a p i d l y x m l ( e x t e n s i b l em a r k u p l a n g u a g e ) h a sg r a d u a l l yb e e nm ef a c t u a ls t a n d a r do fd a t ae x c h a n g ea j l de x p r e s s i o ni n t h ei n t e m e te n v i r o m e m h o wt ou s ex m le m c i e n t l ya n da c h i e v et h eq u e r yo fx m l d a t ah a sb e e na ni m p o r t a n ts u b je c to fi n t e n l e td e v e l o p m e n t i i lo r d e rt os t a n d a r d i z et h eq u e 巧a l l dp r o c e s s i n go f ) ( 】ld a t a ，w 3 c ( w b r l dw i d e w 曲c o n s o r t i u m ) p u t sf 0 刑a r dt 0x q u e r ya s 孤x m lq u e r yl a n g u a g e ，a n dm a k e si t a st h er e c o m m e n d “o n x q u e r yi sap o w e r 凡ld a t aq u e r yi a n g u a g e ，w h i c hs u i t st h e q u e r yo fv 撕o u st y p e so f ) ( m ld a t as o u r c e s nc a i lc h o o s ea 1 1 d e x t r a c td a t a 仔o m x m ld o c 啪e n t s ，a n dr e c o n s t m c tt h eq u e r yr e s u l t si n t on e wx m ld o c u m e n t st h a t t h eu s e rr e q u i r e d x q u e r yp o s s e s s e sm ea b i l i t yo fq u e r y i n gd a t a ，o r g a n i z i n gd a t aa n d d e s c r i b i n ga l g o r i t h m ，t h e 印p l i c a t i o no fw h i c hh a sb e e nm o r ew i d e l yu s e d t h e i m p l e m e n t a t i o na n da p p l i c a t i o no ft e c l l i l o l o g yo fx q u e r yh a s 伊a d u a l l yb e e i l a i l i m p o n a n tr e s e a r c hd i r e c t i o n s e m i s t m c t u r ec h a r a c t e n z e st h ex m ld o c u m e n t ht h eq u e r yr e q u e s te x p r e s s e d i nx q u e r y al a r g en u l n b e ro ft a s k sa i ma tt h es t n j c t u r eo fx m ld a t at oq u e a c c o r d i n gt om et r e es t m c t u r eo fx m ld o c u m e n t s ，t h et w i gq u e r yt e c h n i q u e s o b t a i nt h eq u e 巧r e s u l t sb yu s i n gp a t t e mm a t c h i n gm e t h o d a tp r e s e n t ，t w i gq u e r y f o rx m lq u e 叫a 1 9 0 r i t h mh a sb e c o m eap r e v a l e n ti s s u e ，a n ds o m ex m lq u e r y a l g o r i t h m sh a v e b e e np r o p o s e d ，s u c ha st w i g s t a c k ，t w i 9 2 s t a c k ，t w i g l i s ta n ds oo n i no r d e rt oe x t e n dt h ep a t t e mo ft w i gq u e r ya n de n h a n c et h ee x p r e s s i o na b i l i t yo f t h et r e ep a t t e m ，am o r ep o w e r m lf o 砷o f 似r i gq u e r i e s ，n 锄e l y ，g e n e r a l i z e dt r e e p a t t e m ( g t p ) ，i sr e q u i r e d t h i sa r t i c l ea i m sa tt h er e s e a r c h i n go fi m p l e m e n t a t i o nt e c h n i q u e so ft h ex q u e r y l a n g u a g e ，a j l de x t e n d st h et w i gq u e r ya b i l i t yf o rt h ex q u e r ye n g i n e i i lt h i ss t u d y t h e g t pq u e r yi su s e dt or e p l a c et h et r a d i t i o n a lt w i gq u e a n di m p r o v e st h e7 r w i g l i s t q u e r ya l g o r i t 量u i l b a s e do nt h en e e dt ow e a l (b i n d i n ga n d伊o u pe n u m e r a t i o n m e a n w h i l e ，t h et w i gq u e r yw i l lb ep u ti n t ou s ei nm eq u e r yp l a n 仔a m e w o r k t h e x q u e r yq u e r yp l a nd e s c r i p t i o nl a n g u a g ec a l l e df x q lw i hb ee x t e n d e di no r d e rt o d e s c n b et h et w i gq u e r yf u n c t i o n a n dad e d i c a t e dt w i gq u e r ym o d u l ew i l lb e d e s i g n e da n di m p i e m e n t e df o rt h ex q u e r ye n g i n e t h r o u 曲t h em n c t i o n a la n dp e r f o n n a n c et e s to ft h e r w i gq u e r ym o d e l ，i ts h o w s t h a tt h ee x t e n d e dx q u e r ye x e c u t i o ne n g i n ec a ne m c i e n t l ys u p p o r tt h ei m p l e m e n t a t i o n 1 t t 北京工业人学工学硕_ 学位论文 o ft w i gq u e r y ，a n dt h ep e r f o 肿a n c eo u t p e r f 0 砷st h ef o m e re n g i n e k e y w o r d sx q u e r y ；t w i gq u 9 r y ；g t pq u e r y i v 目录 目录 摘要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 1t w i g 查询的研究现状3 1 3 2x q u e r y 实现技术的研究现状。4 1 4 课题来源5 1 5 本文的研究工作5 1 6 本文结构6 第2 章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 1 3x q u e r y 表达式和特点8 2 2x q u e r y 引擎系统_ g e o q u e r y 1 2 2 2 1g e o q u e r y 系统结构1 2 2 2 2 查询处理流程13 2 3g e o q u e 呵系统扩展t w i g 查询功能1 4 2 3 1 原系统处理路径表达式的问题1 4 2 3 2g t p 查询的引入1 5 2 3 3 系统结构和解决方案1 6 2 4 本章小结1 7 第3 章t w i g “s t 算法的研究与扩展1 9 3 1t w i g 查询1 9 3 2t w i g l i s t 算法及其扩展2 1 3 2 1t w i g “s t 算法2 1 3 2 2t w i g l i s t 算法扩展2 3 3 3 本章小结2 5 第4 章g t p 查询在g e o q u e r y 系统中的描述2 7 v 北京工业大学t 学硕十学位论文 4 1f x q l 语言2 7 4 1 1f x q l 数据模型2 8 4 1 2f x q l 语法2 9 4 1 3f x q l 的原语3 0 4 2f x q l2 o 3 1 4 2 1f x q l 2 o 文法扩展31 4 2 2g t p 查询描述规则3 2 4 2 3g t p 查询描述实例3 3 4 3f x q l 2 0 语法树类体系的设计3 4 4 4 本章小结3 9 第5 章f x q l 2 o 执行引擎的设计与实现4 1 5 1 引擎的执行机制4 1 5 1 1 执行环境4 3 5 1 2 执行引擎的算法设计4 3 5 2g t p 查询模块的设计与实现4 6 5 2 1g t p 查询模块类体系4 6 5 2 2g t p 查询模块类设计4 7 5 3 本章小结5 1 第6 章系统测试5 3 6 1 测试方案5 3 6 1 1 测试环境。5 3 6 1 2 数据集5 3 6 1 3 测试方法5 3 6 1 4 测试用例5 4 6 2 测试结果与分析5 4 6 2 1d b l p 数据集上的测试5 4 6 2 2x m a r k 数据集上的测试5 5 6 2 3t r e e b a n k 数据集上的测试5 6 6 3 本章小结5 7 结1 沦5 9 参考文献6 1 攻读硕士学位期间发表的学术论文6 5 致谢6 7 v i 第l 章绪论 1 1 课题背景 第l 章绪论 x m 卜可扩展标记语言( 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 ( w 6 r l dw i d ew 曲c o n s o n i 啪) 于1 9 9 8 年2 月发布的一种数据标准。 x 】l 技术在互联网环境中扮演着越来越重要的角色，它事实上已经成为互联网 环境中数据交换和表示的标准。该技术被广泛应用在银行、证券、电子商务等各 个领域。 x m l 具有可扩展性，允许使用者创建和使用自己的标记来定义领域相关的 特殊标记语言。订l 具有灵活性，它提供了一种半结构化的数据表示方式，可 以灵活地扩充数据的结构【2 3 】。x m l 文档通常包含一个文档类型声明，具有自描 述性，不仅易于阅读，也方便计算机处理。x 】l 表示数据的方式独立于应用系 统。 ) ( m l 不仅在数据交换和描述方面有着自己的优势，在数据存储与管理方面， 纯x m l 数据库( n a t i v ex m ld a t a b a s e s ) 和使能数据库( le n a b l ed a t a b a s e ， x e d b ) 的研究和产品也层出不穷。正因为如此，人们对x m l 的查询有着广泛 的需求。煳l 数据与传统的关系数据库中的数据相比，有以下一些特点：( 1 ) x m l 数据是自描述的，内容与结构混杂在一起；( 2 ) x m l 数据具有完整的嵌 套层次，是半结构化的数据；( 3 ) x m l 数据是有序的【4 1 。 w 3 c 组织为了满足v i l 的查询需求，针对l 数据的特点，于2 0 0 7 年 发布了x m l 查询语言标准：x q u e 巧语言( x m lq u e r yl a n g u a g e ) 【5 1 。x q u e r y 以x p a t h 2 0 【6 】为基础，使用序列来表示值，主要语言结构有路径表达式、f l o w r 表达式、构造表达式、条件表达式等。它支持条件选择、结果转换，还支持自定 义函数与类型描述1 1 。x q u e r y 适用于查询各种类型的x m l 数据源，它能够从 l 文档中选择并提取出文档片段，进而把查询结果重构为用户所需的新的 x m l 文档结构【1 2 ，1 3 】。x q u e q 是一种功能强大的订l 查询语言，具有查询语言 的各种特性。同时，x q u e r y 又是一种图灵完全的函数式语言【1 4 】，即除了进行煳l 数据查询外，x q u e r y 还可以作为一种程序设计语言进行程序设计。随着x q u e 巧 应用数量的不断增长，x q u e w 语言的实现已经成为x m l 数据查询领域一个重 要的研究方向。 在各种x q u e r y 的相关研究中，如何高效地实现x q u e r y 语言是研究的核心 问题之一。x m l 数据具有半结构的特点。x q u e r y 所表示的查询请求中，大量任 北京t 业大学t 学顾十学位论文 务是针对x m l 数据的结构特征进行查询。一个x q u e 叫路径表达式可以通过小 枝模式( t w i gp a t t e m ) 进行建模，称为小枝模式查询( 15 1 ，简称t w i g 查询。小枝 模式查询亦称为树模式查询( t r e ep a t t e mq u e r y ，t p q ) 。t w i g 查询根据x m l 查 询中的树结构特征形成模式树，采用模式匹配的方法完成高效处理。它是处理 x m l 查询的重要操作之一。目前t w i g 查询已成为研究的一个热点问题。本研究 将t w i g 查询技术和x q u e r y 引擎的实现相结合，为使x q u e r y 引擎系统支持t w i g 查询提出了解决方案。 1 2 研究意义 为x q u e r y 引擎系统提供处理t w i g 查询的功能，目的是提高x q u e w 程序的 执行效率。 x q u e r y 作为w 3 c 发布的推荐标准，对于x m l 查询有了种统一标准的描 述方式，使用这种描述方式可以使x m l 的查询更加规范。目前，有些公司以及 组织都研究并开发了自己的x q u e r y 执行引擎，推出了不同的x q u e w 实现方式， 如i b m 的d b 2p u r e x m l 【1 6 - 19 1 ，o r a c l e 的x m l d b f 2 0 ，2 ，a x y a n a 的q i z x o p e n f 2 2 】 等都实现了对x q u e r y 程序的良好支持。由于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 q u e r y 程序负责x m l 数据的查询和组织，因此有许多研究将x m 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 眄翻译为查询计划，并基于某种查询代数进行查询重写，执行重写后的 计划。 x m l 文档的结构查询通常被转化为两个结点列表之间的包含关系或文档位 置关系的结构连接操作，同时关键字操作也被转化为两个结点列表之间的包含关 系的结构连接操作。因此，有效地支持结构连接对x m l 查询的有效实现是解决 问题的关键。x m l 文档包含具有层次嵌套关系的元素信息，可以很自然地用一 棵文档树来表示，t w i g ( 树) 模式查询就是从文档树中找到与模式树匹配的元素 序列。采用t w i g 查询的整体模式匹配方法可以提高x m l 查询的执行效率，减 少中间结果的产生，降低查询执行的时间和空间开销。然而，在x q u e r y 引擎中 实现对t w i g 查询功能的支持将面临以下问题：( 1 ) x q u e r y 引擎采用的x m l 查 第1 章绪论 询代数中缺少对t w i g 查询整体匹配的支持；( 2 ) 由于x q u e r y 是一种函数式语言， 其查询计划难以采用函数的方式来描述t w i g 查询请求和结果引用。 本课题组设计并实现的g e o q u e r y 【2 3 。2 6 】系统，是一个面向空间数据集成的 x q u e r y 查询系统，其中采用中间语言f x q l ( f 叽c t i o n a lx m lq u e 巧l a n g u a g e ) 来描述查询计划。f x q l 作为一种中间语言，具有函数式语言的特点，支持函数 定义和调用，支持函数作为参数，并且提供了丰富的原语函数完成各种x m l 数 据处理和程序逻辑控制的任务。在f x q l 的基础上，实现了去相关性的优化【2 7 1 、 动态编译的优化【2 8 1 和基于部分求值的优化【2 9 3 2 】，并且扩充为基于延迟求值3 3 1 的 x q u e r y 查询引擎。为了进一步提高执行效率，本文的研究课题是为现有的 x q u e 巧引擎扩展t w i g 查询的处理功能。在研究中通过扩展f x q l ，引入对t w i g 查询的描述，使x q u e 巧引擎支持t w i g 查询，从而提高系统的执行效率。 1 3 相关研究与研究现状 1 3 1 t w i g 查询的研究现状 t w i g 查询，又称做树模式匹配，是一种结构连接计算。t w i g 查询通常以模 式树的方式来描述。在t w i g 模式树中有两种边：“”表示父子关系( p c ) ，“” 表示祖先后代关系( a d ) 。t w i g 查询的目的便是找到x m l 文档中所有满足t w i g 查询模式树描述的结构关系的元素。如图1 1 是一个简单的t w i g 查询模式树， 其对应的x p a t h 为a b c 。 il a bc 图1 - lt 叭g 查询模式树 f i g u r el lt w i gp a t t e mt r e e t w i g 模式匹配是x m l 查询处理过程中最重要的操作之一。目前，学术界对 于t w i g 模式匹配算法进行了较为深入的研究，并取得了显著的成果。 在早期的t w i g 查询算法研究中，首先将树模式分解为一组二元结构关系( 双 亲孩子关系或祖先后代关系) ，然后针对每组二元关系采用结构连接的算法得到 查询结果，最后将每组关系的查询结果进行归并从而得到树模式匹配的结果。在 众多的研究中，c z h a n g 等人提出了多谓词合并连接算法( m p m d j n ) 【3 4 】，该 北京丁业大学工学硕j j 学位论文 算法采用反向链表和区域编码的数据结构来处理x m l 查询。在后来的研究中， a l k j l a r l i f a 等人提出了一个基于栈算法一s t a c k t r e e d e s c a n c 【3 5 】。以上算法的主 要缺点在于产生大量的冗余中间结果。 为了避免产生大量的中间结果，n b r u n o 等人首次提出采用整体匹配的方法 处理t w i g 查询。在文献 3 6 】中提出了两个h o l i s i t i ct w i g 结构连接算法：p a t h s t a c k 算法和t w i g s t a c k 算法。p a t h s t a c k 算法即路径模式查询算法，用来处理不包含分 支的树模式查询。t w i g s t a c k 算法将t w i g 查询分为两个阶段：在第一个阶段中， 将树查询中的一些从根到叶的单个路径查询局部匹配结果被计算；在第二个阶段 中，这些单个路径查询的局部匹配结果被归并成树模式查询的最终匹配。为了提 高t w i g 模式匹配的效率，在此后的研究中采用了索引技术，例如香港科技大学 的h j i a n g 等人提出了x r t r e e 的数据结构，使用动态的外部存储索引结构来设 计x m l 数据，根据这种索引结构，提出了一个新算法t s g e n e r i c + 【3 7 】。 s c h e n 等人在文献 3 8 中提出了一种层次栈编码方案( h i e r a r c h i c a ls t a c k e n c o d i n gs c h e m e ) ，该方案采用层次栈的结构描述t w i g 查询匹配的部分结果，并 基于这种结构，提出了针对通用树模式匹配的t w i 孑s t a c k 算法。该算法使用层次 栈的结构可以同时保存l 结点间的“祖先后代( a d ) ”和“双亲孩子( p c ) ” 关系。在构建t w i 矿s t a c k 的算法中将匹配t w i g 查询的x m l 结点保存在层次栈 中，然后利用枚举算法得到t w i g 查询的结果。t w i 9 2 s t a c k 算法有效地解决了以 往算法中产生中间结果较多的问题，并能有效地处理p c 关系。但是由于它采用 的数据结构相对复杂，在层次栈构造和维护结点关系时会带来一定的时间和空间 开销。 在随后的研究中，基于t w i 矿s t a c k 算法的思想，q l u 等人提出了t w i g “s t 算法【3 9 】。该算法与t w 霄s t a c k 算法类似，使用构建算法将x m l 结点保存在特定 的数据结构中，并通过相应的枚举算法得到查询结果。而t w i g l i s t 通过采用简单 线性表的数据结构取代复杂的层次栈结构，从而提高了算法的效率。但t w i g “s t 算法只支持t w i g 查询，而不支持通用树模式查询。 为了更好地描述x q u e 巧查询，z c h e n 等人在文献 4 0 中对常见的树模式进 行扩展，将x q u e r y 程序中不同片段中的路径表达式作为一个整体树模式，并加 入了一些反映x q u e r y 特性的信息，如嵌套层次、强弱绑定等，从而增强了树模 式的表达式能力，这种增强的树模式被称为通用树模式( g e n e r a l i z e dt r e ep a t t e m ， g t p ) 。 1 3 2 x q u e 巧实现技术的研究现状 随着x q u e r y 的应用越来越广泛，为了实现x q u e r y 语言规范，越来越多的 第l 章绪论 组织开始研究x q u e r y 的实现技术，并推出了一系列x q u e r y 引擎。这些引擎采 用不同的实现方式，从不同的技术角度考虑，并采用了不同的优化策略。 q i z ) ( o p e n 【2 2 】是a x y a l l a 从2 0 0 j 年开始提供的一个开源的x q u e r y 引擎，使用 j “a 语言实现。它基本实现了x q u e r y 规范中规定的语言特性。它被设计为一个 嵌入到j a v a 应用中的x m l 查询和数据库引擎，并提供了q i z xa p i 作为类库。 该系统对于x q u e r y 查询内部采用纯解释执行的方式，将x q u e r y 翻译为一种抽 象表达式树，逐一解释执行。 g a l a x 【4 3 】是一个轻量级可移植的x q u e r y 的开源实现系统。起初g a l a ) 【目的 是作为x q u e r y 的参考实现。随着工作的进展，j a g a d i s h 等人为g a l a ) 【加入了x m l 专用的查询代数t a x 【4 4 1 ，包括带标签的有序树模型以及专用的查询算子：g a l a x 将x q u e r y 编译为查询计划，最后由引擎解释执行查询计划，返回结果。g a l a x 系统的设计借鉴了数据库查询优化的思路，在x q u e r y 实现中引入了查询代数。 由于数据库中针对查询代数的实现和优化技术非常成熟，在x q u e r y 实现中可以 使用类似的查询优化手段，可以提升系统的性能。 s a x o n 【4 5 1 是由英国的m i c h a e lk a y 开发的x s l t 与x q u e 巧处理器，自从1 9 9 9 年以开源产品发布。从2 0 0 3 年开始s a x o n 增加了对x q u e 叫的支持。它对x q u e r y 的支持由一个x q u e r y 解析器组成，解析器与x s l t 处理器一样产生相同的内部 可解释的代码。 中国人民大学研制的o n e n t x 是一个n a t i v ex m l 数据库系统【4 引，并提出将 o d e n t x a 作为x q u e 科优化处理的有效代数系统【4 7 | 。 现在国内外已经展开了对与编译实现x q u e r ) r 语言的研究。q e x o 【4 8 ，4 9 】是g n u k a w a 【5 0 】实现的x q u e r y 执行引擎，它使用编译实现的方式，将一个x q u e 叫源程 序编译为可执行的j a v a 字节码，并加载到j a v a 虚拟机中执行。 作者所在实验室开发了一套x q u e w 编译实现系统- x q c 【5 1 j ，它采用s e c d 抽象机指令序列和j a v a 字节码技术实现。 1 4 课题来源 本课题研究得到了北京市自然科学基金( 项目编号：4 0 8 2 0 0 3 ) 的支持，项 目名称为：x q u e r y 语言动态编译技术的研究。 1 5 本文的研究工作 g e o q u e 拶系统是作者所在实验室前期研制的一套x q u e r y 实现系统。该系 统采用解释执行方式：输入的x q u e r y 程序被翻译为抽象语法树，然后被转换为 中间语言f x q l ，最后由一个解释程序完成f x q l 代码的执行。 5 - 北京工业人学工学硕e 学位论文 本文主要研究x q u e r y 引擎系统中t w i g 查询技术，为已有的x q u e w 查询系 统一g e o q u e r y 扩展支持t w i g 查询的整体匹配功能，并提供一套支持t w i g 查询 的x q u e r y 引擎实现方案。 本文的研究工作如下： 1 采用整体匹配的t w i g 查询方法，利用g t p 查询来表示查询模式树，将 t w i g 查询作为x q u e q 引擎的一个功能模块。 2 根据g t p 查询的需求，对t w i g l i s t 算法进行扩展，使其支持弱绑定、具 有重复元素的模式树和枚举分组的g t p 查询处理。 3 分析f x q l 语言的特点与g t p 树查询表示的需求，扩展f x q l 表示功能 使其能够描述g t p 树查询。 4 设计并实现了一套支持g t p 查询的x q u e r y 引擎系统。对x q u e 巧引擎 系统进行功能测试和性能测试。实验表明，与原系统相比，采用g t p 查询后 x q u e r y 系统的执行性能得到了提高。 1 6 本文结构 本文的内容组织如下： 第l 章绪论。主要介绍研究课题的背景、来源，分析x q u e r y 引擎中t w i g 查询技术的目的和意义，国内外相关研究的研究现状，以及本文的主要工作内容。 第2 章x q u e r y 引擎系统的扩展。首先介绍x m l 以及x m l 查询语言一 x q u e r y ，其次介绍课题组原有的x q u e r y 引擎系统一g e o q u e r y ，这些内容是课题 研究的基础。然后，对原x q u e r y 引擎系统进行扩展，使其支持t w i g 查询的功 能；同时，说明x q u e r y 系统中使用g t p 查询来实现。最后对引入g t p 查询功 能后的x q u e 叫引擎系统框架进行详细说明。 第3 章t w i g 查询和t w i g “s t 算法的扩展。本章首先具体介绍t w i g 查询， 然后详细介绍t w i g l i s t 算法，并介绍根据g t p 查询的要求对t w i g “s t 算法进行 了一些扩展工作。 第4 章g t p 查询在g e o q u e r y 系统中的描述。本章首先介绍查询计划描述 语言f x q l ，随后扩展f x q l 的表示功能，使其能够描述树查询。 第5 章f x q l 2 o 执行引擎的设计与实现。本章首先介绍了中间语言 f x q l 2 o 执行引擎的设计，包括实现该执行引擎采用的具体算法；然后介绍了 g t p 查询模块的详细设计与实现。 第6 章系统测试。本章通过多个测试用例，对扩展了g t p 查询功能的 g e o q u e r y 系统进行了测试，并给出测试结果与分析。 结论部分对本课题的研究工作进行了整体总结，并探讨了未来研究的方向。 第2 章x q u e r y 引擎系统的扩展 第2 章x q u 9 拶引擎系统的扩展 随着x q u e r y 语言的应用范围越来越广泛，如何提高x q u e r y 程序的执行效 率成为一个重要的研究课题。t w i g 查询能够充分利用x m l 文档半结构化的特 点，提高x q u e w 程序的执行效率。本章首先介绍x q u e r y 语言，并简要介绍已 有x q u e 巧引擎系统一g e o q u e r y ，并对g e o q u e r y 系统展开扩展，使其支持t w 追 查询的整体匹配。 2 1 x q u e 哆语言 2 1 1x m l 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 的 x m l 工作组于1 9 9 8 年2 月发布的一种标准。工作组对删l 语言的描述：“x m l 是s g m l ( s t a l l 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 ，标准通用标记语言) 的子集， 其目标是允许普通的s g m l 在w 曲上以目前h t m l ( h y p e n e x tm a r k u p l a i l g u a g e ，超文本标记语言) 的方式被服务、接收和处理。 x m l 具有两个基本特点：( 1 ) 自描述性。x m l 数据本身包含元数据一关于 数据本身的信息，表现为不同语义的标记( 例如元素、属性等) 。在所有标记中， 元素标记最为重要。一个元素标记由两个起止标签构成，起止标签所含的文本就 是对应的语义单元。通过) ( i l 文件的d t d ( d o c u m e n t 聊ed e c l a u r a t i o n 一文档 类型声明) 和x m ls c h e m a 可以定义x m l 数据集的信息。( 2 ) 半结构化。不同 于传统的关系数据库，x m l 数据是半结构化的，表现为语义单元相互嵌套的层 次关系。x m l 数据的基本形式为x m l 文档。 ) a l 作为一种文档标记语言，已被广泛接受和使用。传统的数据库生产商 纷纷把支持x m l 作为一个重要的发展方向。o r a c l e 和d b 2 都支持x m l 数据库， 将删l 按照层次结构进行分解，并在关系数据库中创建与之相对应的数据表， 用父表和子表来描述层次结构。同时提供一个支持a t h 语言的软件包，将x p a t h 表达式转换为s q l 语句后对数据库进行查询，并将查询结果组成x m l 文档的方 式返回【4 1 。 由于x m l 可以根据具体应用灵活地表现异构数据源中的各种信息，包括应 用程序之间交换的数据、结构化和半结构化的文档等。越来越多的信息开始采用 l 进行存储、交换和表现。因此如何有效且高效地存取x m l 信息，提供跨 越不同数据源的基于x m l 信息的查询检索能力变得日益重要。开发人员迫切需 7 北京1 二业大学t 学顾七学位论文 要一种灵活易用、针对各种类型x m l 数据源的查询语言。 于是w 3 c 组织成立了x m l 查询工作组，其任务是为x m l 文档建立一个数据 模型、基于该数据模型的一组查询运算符和建立在这些查询运算符操作之上的查 询语言。 2 0 0 7 年，w 3 c 的x m l 查询工作组制定出了x m l 查询语言规范一x q u e r y 语言。 2 1 2x q u e 巧 x q u e r y 是x m lq u e r y 的缩写，是一种基于l 的数据查询语言。x q u e r y 是 根据x q u e r y l o 和x p 2 l t h 2 0 数据模型( x q u e r y l 0a n dx p a t h 2 0d a t am o d e l ，简称 x d m ) 定义的【5 1 。 x q u e r y 适用于查询各种类型的x m l 数据源，能够从x m l 文