（计算机应用技术专业论文）基于重写机制的xquery查询优化技术研究.pdf

摘要 随着基于i n t e m e t 商业应用的迅速发展，x m l ( e x t e n s i b t em a r k u pl a n g u a g e ， 可扩展标记语言) 已经成为i n t e m e t 上数据表示和数据交换的标准格式，提出了对 x m l 数据查询的要求。关系数据库系统技术已经十分成熟，在商业数据管理中占 据着主导地位，如何利用关系数据库来实现x m l 数据管理已经受到了广泛的关注 与重视。x m l 数据资源的查询与检索是x m l 获得广泛应用的关键，在w e b 数据 管理中占有重要地位。在众多x m l 查询语言中，x q u e r y 语言是w 3 c ( w o d dm d e w e bc o n s o r t i u m ，互联网联盟) 标准草案的一部分，已经得到了广泛的应用。因此， 基于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 查询处理上提出了一种混合执行策略，其中主要 是将x q u e r y 转化成s q l 来进行相应的处理。其实质就是在x q u e r y 上进行静态分 析和类型检查，并将它转化成本地带有x m l 扩展操作符的s q l 数掘结构，并对 原先的x m l q u e r y oj 函数进行替换。若x q u e r y 表达式不能重写成s q l ，那么将 x m l q u e r y o 函数完整无缺的保留。 对于多数掘源重写机制而言，主要是通过一个目标模式，并给定一个源模式 和目标模式之f h j 的映射，以及给定源模式中的数据来有效的进行查询重写。以前 关注的焦点是关系数据和模式，现在我们关注的是关系和x m l 模式之间的查询和 映射，而且我们还要考虑映射的多种可能情况。基于此给出了一个重写算法，其 中涉及到规则产生，查询转化，查询优化以及查询整合四个步骤。 最后给出基于物化视图查询重写机制。首先给出一般视图查询机制的运行原 理，并基于此提出了一个视图重写查询机制模型。最后引申到物化视图的研究上， 并针对x p a t h 物化视图提出了一套基本匹配算法，并对该基本匹配算法进行扩展， 从而可以解决记录匹配以及谓词处理等操作。 关键词；x m l ，x q u e r y ，重写，多数据源，物化视图 a b s t r a c t a l o n g 谢t ht h eq u i c kd e v e l o p m e n to fi n t e r a c tb u s i n e s sa p p l i c a t i o n , x m lh a s a l r e a d yb e c o m et h es t a n d a r d f o r m a to fd a t a e x p r e s s i o na n dd a t ae x c h a n g e so n i n t e m e t t h e r e f o r eal o to fb u s i n e s sa p p l i c a t i o n sp u tf o r w a r das e a r c ht ot h eq u e r yo f x m ld a t a r e l a t i o n a ld a t a b a s es y s t e mh a sb e e na l m o s tp e r f e c ti nt h ed o m a i no f t e c h n i q u e s ，a n di t sd o m i n a n ti nb u s i n e s sd a t am a n a g e m e n ta r e a i t sb e e np a yw i d e a t t e n t i o na n dr e g a r d st oh o wt or e a l i z ex m ld a t am a n a g e m e n tt a k i n ga d v a n t a g eo f r e l a t i o n a ld a t a b a s e n l ek e y sf o rw i d ea p p l i c a t i o n so f x m ll i ei nq u e r ya n ds e a r c h i n g i nx m ld a t as o u r c e s i t s v e r yi m p o r t a n tt ow e bd a t am a n a g e m e n t w i t h i nal a r g e n u m b e ro fx m lq u e r yl a n g u a g e s ，x q u e r yi so n ep a r to ft h es t a n d a r dd r a f t so f w 3 c ( w o r l d w i d ew e b c o n s o r t i u m ) a n d i th a sb e e nu s e di n a p p l i c a t i o n w i d e l y ，a e c o r d i n g l y , x q u e r yp r o c e s s i n ga n do p t i m i z a t i o nt e c h n i q u ei se m a e r g i n go n eo f t h em a i ne o n t c h a t so fx m l m a n a g e m e n t i tm a k e ss i g n i f i c a n te f f e c to nt h ea p p l i c a t i o n s o f x m l i nt h i st h e s i s ，t h ep r o b l e mi sd i s c u s s e dm a i n l yf r o mt h r e ea s p e c t s ：p r o c e s s i n gf o r q u e r yl a n g u a g et r a n s f o r m a t i o no fx q u e r yt os q la n dq u e r yr e w r i t i n gb a s e do n m u i r - d a t a s o u r c ea n dq u e r yr e w r i t i n gb a s e do nm a t e r i a l i z e dv i e w t h ep r o c e s s i n gc o t l e s c a n dr e a l i z i n gm e t h o d sh a v eb e e na n a l y z e d m a n yc u r r e n tr e p r e s e n t a t i v es o l u t i o n sh a v e b e e nc o m p a r e d t h ef e a s i b l er o u t et or e s o l v et h ep r o b l e ma n dt oa t t a i nt h er e q u i r e m e n t s o f a p p l i c a t i o ni sg o ta st h er e s u l t o nt h ex q u e r yq u e r yp r o c e s s i n go fb a s e do nr e l a t i o nd a t a b a s e ，ip u tf o r w a r d a k i n do fm i x - p r o c e s s i n gs t r a t e g y m a i n l yi st h ep r o c e s s i n gt h a tt r a n s f o r mx q u e r yt o s q l i nf a c tt h ep r o c e s s i n gi st h a ts t a t i ca n a l y s i sa n dt y p ec h e c k i n g ，a n dt r a n s f o r m i n gi t i n t ot h es q ld a t as t r u c t u r et h a tt h el o c a l i z e da n dx m l e x p a n d e d o p e r a t e r ，a n dc a r r y i n g o nr e p l a c e m e n to nx m l q u e r y 0f u n c t i o n ，i ft h ex q u e r ye x p r e s s i o nc a n tr e w r i t ei n t o s q l ，p r e s e r v i n gt h ex m l q u e r y 0f u n c t i o ni n t a e t n e s s l y o nq u e r yr e w r i t i n gb a s e do nm u l t - d a t a s o u r e e f i r s t l y g i v e nat a r g e ts c h e m a , a m a p p i n gb e t w e e nas o n r c es c h e m aa n dat a r g e ts c h e m aa n dt h ed a t ao ft h es o u r c e s c h e m a , t h e np r o c e s s i n go fq u e r yr e w r i t i n g n l ef o c u st h a tp a i da t t e n t i o nt ob e f o r ei st h e r e l a t i o nd a t aa n ds c h e m a s ，w ep a ya t t e n t i o nt ow h a ti st h eq u e r i e sa n dm a p p i n g so ft h e r e l a t i o na n dx m ls c h e m an o w a n dw es t i l ln e e dt oc o n s i d e rt om a p p i n go fv a r i o u s p o s s i b l es c e n e s a c c o r d i n gt ot l 缸s ，ig i v ear e w r i t ea l g o d t l u r bi n v o l v i n gt ot h er u l e c r e a t i o n , s e a r c ht r a n s f o r m a t i o n q fa i l d ,ery o p t i m i z a t i o n q u e r yi n t e g r a t i o n 2 a tl a s t ig i v eq u e r yr e w r i t i n gm e c h a n i s mb a s e do nm a t e r i a l i z e dv i e w f i r s t l y s p e c i f y i n gt h ep r o c e s s i n gp r i n c i p l et h a tt h ev i e wq u e r ym e e h a n i s mg e n e r a l l y ，a n d p u t t i n gf o r w a r dav i e wr e w r i t eq u e r ym e c h a n i s mm o d e la c c o r d i n gt ot h i s t h e n i n v o l v i n gt ot h er e s e a r c ho ft h em a t e r i a l i z e dv i e w , m a i n l yp u t t i n gf o r w a r dt oas e to f b a s i cm a t c h i n ga l g o r i t h ma c c o r d i n gt ox p a t hm a t e r i a l i z e dv i e w f i n a l l y ，ie x t e n dt h e b a s i cm a t c h i n ga l g o r i t h m ，w h i c hc a ns o l v er e c o r d sm a t c h i n ga n dp r e d i c a t ep r o c e s s i n g p r o b l e ma n ds oo n k e y w o r d s ：x m l ，x q u e r y ，r e w r i t i n g ，m u l t d a t a s o u r c e ，m a t e r i a l i z e dv i e w 3 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果， 也不包含为获得江西财经大学或其他教育机构的学位或证书所 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 吕期：2 塑二22 。h 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规 定，即：学校有权保留送交论文的复印件，允许论文被查阅和借 阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印 或其他复制手段保存论文。 ( 保密的论文在解密后遵守此规定) 签名：! 凳量冀师签名：互圭兰曰期：必) 。沁 1 绪论 1 绪论 x m l ( e x t e n s i b l e m a r k u p l a n g u a g e ，可扩展标记语言) 1 1 j 是一种通用标记语言， 能够非常灵活地标记w e b 上多种不同数据源中的信息，具有开放性、灵活性、易 读性和平台无关性等特点。随着基于i n t e m e t 商业应用的迅速发展，x m l 已经成 为i n t e m e t 上数据表示和数据交换的标准格式，而且在i n t e m e t 上存在大量和重要 的x m l 文档，这些应用提出了一系列新的涉及x m l 数据管理的要求。就现状和 发展趋势来看，关系数据库经过多年发展已经非常成熟，在商业数据管理领域中 占据着主导地位。x m l 在过去几年的时间里得到了极大地发展，它从最开始的为 文档保留语义的标记语言变成了异构系统间交换数据的格式。不仅如此，越来越 多的研究项目把纯x m l 数据库作为他们的研究对射2 1 。随着有效地存储和查询 x m l 的需求不断升温，这样就涌现出许多查询语言来解决存在的一系列问题。其 中最有代表性的x m l 查询语言就是x p a t h 和x q u e r y 。 1 1 研究背景 x m l 是w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ，互联网联盟) 于1 9 9 8 年2 月推 出的一种标记语言。由于其独特的技术优势，x m l 推出后很快就成为网络中数据 表示及交换的标准。因此，要构建基于x m l 的各种应用，准确高效地从x m l 数 据源中查询并获取数据就成为关键的一步。而且x m l 数据资源的查询与检索是 x m l 获得广泛应用的关键，在w e b 数据管理中占有重要地位。现在国内外提出了 很多种x m l 查询语言方案，如x q u e r y 、x q l 、x m l - q l 、q u i l t ，x m l - g l 、x p a t h 、 y a t l 、l o r e l 等。很多x m l 查询语言有极强的针对性，受限于数据类型的种类， 不具备通用性。与此不同，x q u e r y 语言【3 - 9 是w 3 c 标准草案的一部分，适用于各 种类型的x m l 数据源，是一种功能极强的查询语言。x q u e r y 是在其他多种查询 语言精华的基础上形成的，也借鉴了s q l 和o q l ，兼具各种查询语言的优点，具 有灵活方便、符合x m l 文档特点、功能全面等优点，是“x m l 中的s q l ，i ，有 着很广阔的应用前景。 从现在国内外的研究情况来看，x m l 数据管理包括：使用某种映射方法完成 x m l 文档到关系数据库的存储【儿以3 】；用户针对原x m l 文档提出查询要求，理解 具体的x q u e r y 查询语句，然后从关系数据库或n a t i v ex m l 数据库中获取正确的 结果数据【1 4 1 ，并以x m l 的文档结构形式返回给用户。现在对x m l 的研究主要是 把x m l 当作半结构化数据进行研究。x q u e r y 语言能够支持x m l 文档的转化和查 询，它能够通过路径表达式进行数据的抽取，也可以将多个x m l 文档进行连接， 甚至还可以构造新的x m l 文档【1 5 l 。基于此，各种各样的实现技术应运而生，对于 基于重写机制的x o u e r y 查询优化技术研究 每一种不同的实现技术就有各自一套优化技术相对应。正如关系数据库一样，查 询优化在x m l 数据库中具有重要作用，是一个正在被广泛、深入研究的课题。 使用x q u e r y 语言对x m l 数据进行查询与使用s q l 语言进行查询数据有相似 之处：一般来说，s q l 语言由数据库编程人员和数据库管理人员使用，他们是s o l 用户，s q l 查询建立在关系表之上；相似地，) ( q u e r y 的用户是那些使用x q u e r y 编制更高层应用程序和对x m l 数据进行管理的人员，他们认为是将x q u e r y 语言 建立在x m l 文档之上的。然而，在查询处理中却存在很大的差异：x q u e r y 查询 是针对x m l 文档，而在基于关系的x m l 数据库中，数据却是按照各种映射方法 存储在关系表中，查询对象与其数据来源不一致。对于) q u e r y 用户来说，必须满 足他们的要求，使得他们在使用x q u e r y 查询x m l 数据时，就像使用s o l 查询关 系数据一样方便。因此，在关系数据库之上执行x q u e r y 查询时，处理过程中的矛 盾必须得到很好地解决。 1 1 1 x o u e r y 优化背景 过去几年里，在以文档为中心和以数据为中心的环境里，作为信息的一种格 式化语言，x m l 迅速得到了广泛的欢迎。基于x m l 的标准( x m l - b a s e ds t a n d a r d s ) 爆炸似地增长，表观x m l 受到了许许多多不同技术联盟( c o m m u n i t i e s ) 的关注。 现在，许多应用程序使用x m l 来传送消息，如s o a p 、x m l - r p c 消息；或者作 为数据的永久性存储，如x m l 数据库、内容管理系统。一个以x m l 为基础的 w e b ，将替代以h t m l 为基础的w e b ，听起来不再是幻想。 由于w e b 数据的特点，传统的数据库技术和信息检索技术已经不能满足用户 的要求，而随着存储在x m l 文档中信息量的增长，能有效并且高效地存取x m l 信息就变得越来越重要。要做到这一点，必须要有一个让你能够准确地获得所需 信息、更新x m l 数据源中数据的可表达的查询语言。x q u e r y 正是这样的语言。 有了相应的查询语言，但在x m l 数据查询处理研究中，需要关注下列问题： 1 ) 如何定义完善的查询代数。众所周知，关系代数的目的之一是约束明确的 查询语义，之二是用于支持查询优化。关系代数的优势来自简单明确的数据模型 关系，具有完善的数学基础和系统的转换规则。而x m l 数据模型本身具有的 半结构化特点是定义完善的代数运算的最大障碍。x m l 查询语言中的不确定性是 另一个难以克服的困难。目前提出的x o u e r y f o r m a l s e m a n t i c t s l 标准基于f u n c t i o n l a n g u a g e 的思想，为查询优化带来了新的困难。因此，基于x q u c r y 的查询代数 优化技术不断出现。 2 ) 复杂路径表达式是x m l 查询语句的核心，必须将复杂、不确定的路径表 达式转换为系统可识别的、明确的形式。因此现在出现了比较多的关于x q u e r y 路 经表达式的优化策略，例如路径缩短策略以及补路径策略等。 2 1 绪论 3 ) x m l 数据信息统计和代价计算。传统的对值的统计对x m l 查询是不够的。 x m l 数据中的数值分布在类似树状结构的树叶上，即使相同类型的数据，由于半 结构化特点，其分布情况也可能完全不同。因此，需要把对结构的统计信息和对 值的统计信息结合到一起，才能得到足够精确的统计信息。 基于上面的各种问题，为了满足用户查询的需要，高效的查询性能对于查询 来说非常重要。因此，本文主要针对x q u e r y 的查询优化技术进行研究。 1 1 2x 0 u e r y 优化特点 x q u e t y 是将查询表示成表达式的功能语言，支持若干种表达式，其查询可以 有几种不同的结构形式。各种x o u e r y 表达式可以完全嵌套，而且还支持子查询。 x o u e r y 和x p a t h 有非常紧密的联系，x q u c r y 用x p a t h 来表示路径信息。 1 1 3x o u e r y 查询优化的各种方法 目前x q u e r y 查询优化技术主要集中在以下几个方面： 1 ) x q u e r y 形式化语义机制。它的基本思想是将查询映射为一种核心表示形式， 从而消除冗余。 2 ) x q u c r y 代数机制。它有很多种设计代数式的方法，其中比较典型的是使用 x a l i t s 】，它定义了一个逻辑操作集合，并且这个集合与x q u e r y 操作匹配。它的计 算思想是将查询表示成一棵树，将代数运算生成查询优化计划。不仅如此，它还 可以和形式化语义机制结合来使用，能够将x q u e r y 核心表达式转化为抽象的与代 数式一一对应的语法树。 还有一种称作t a x 19 】的优化技术，它是对关系代数表达式进行扩展，扩展的 结果是二个运算集合。同样它是以树模式来表示查询，结果是二个逻辑树代数表 达式。 与上面提到的机制一样，对于代数式的产生是一个很复杂的问题，而且要把 x m l 文档顺序考虑进去，并且采用代数机制不能适用于各种优化方案，因此新的 优化机制不断出现。 3 ) 索引机制。索引机制永远都是优化机制的首选。因为索引机制的适用性和 扩展性相对比较好。而且实现起来相对比较容易，因此研究学者对索引优化机制 的研究最多丽且发展最快。般可以将索引机制分成以下几类： ( 1 ) 名字索引。它使用标签名把结点链表和对应的索引入口点连接起来。这种 索引机制最大的优点就是简单，而且可以根据用户的需求随时改变索引结点，对 于索引的大小也有很好的控制，以至于索引不会占据很大的空间。 ( 2 ) 值索引。顾名思义就是把元素值作为索引关键字。它和名字索引机制类似。 基于重写机制的x o u e r y 查询优化技术研究 ( 3 ) 结构索引。伴随着最小化模式概念的出现，随之就有很多结构索引技术出 现，典型的有d a t a g u i d e s 2 0 1 、a i n d e x 2 1 1 等等，结构索引技术可以解决名字索引 技术中出现的问题。 上面的分类又可以进行重新划分，这种划分将索引机制分成两类，分别是路 径索引和结构索引。 ( 1 ) 路径索引是基于代价优化的两阶段方法。两阶段中高层是一个基于代价的 存取选择方法，底层是一个基于代价的优化方法。对于高层的存取选择方法涉及 到两个存取：支持x m l 文档流模式匹配；路径索引结构匹配先前x m l 文档 模式。它的适用范围是路径索引将模式简化，合并路径索引将查询计划的搜索空 间限制在一定的范围内，并可在x m l 统计信息上建立代价模型。其中使用比较多 的路径索引机制有a ( k ) i n d e x 和f & b i n d e x 2 2 】索引机制。其中a ( k ) i n d e x 索引机制 的基本原理是：对结构化汇总信息进行近似化。它是基于k - b i s i m i l a r i t y 2 3 l 概念提出 的一种索引机制，它实质上是将复杂路径转化为精确的结构概要路径，然后运用 短路径的相似性来减少结构大小口l 。而f & b i n d e x 索引机制的基本原理是：为所 有分支路径表达式查询提供一种覆盖索引( c o v e t i n gi n d e x e s ) 机制。但是这种索 引机制有不足之处，即占用空间太大以至于查询性能下降。 ( 2 ) 结构索引是在x m l 数据库中用数据图g 来表示结构索引，记作l ( g ) 。i ( g ) 是一个带有标签的有向图，这个图包括了g 的每一条路径，并且有最少的结点和 结构路径表达式r ，结果是与r 匹配的索引结点的扩展结点的并集。 4 1 选择估计机制。在x m l 查询中，一个给定的查询或逻辑查询计划在转换 为物理查询计划的时候往往有很多种选择，通常要对多个物理查询计划进行评价， 选择最好的物理查询计划，这种评价往往都是基于代价的，即评价该物理计划执 行的代价。合理地估算操作结果的大小对物理计划的选择有着至关重要的作用， 它将直接决定着查询优化的效果。 操作结果大小的估算与具体操作有关。对于任何操作，其结果大小的估算有 两个方面：首先获得关于数据分布的一些统计信息，用这些统计信息来近似实际 数据的分布；然后基于这一近似，根据某一估算法则估算操作的大小。 路径树1 2 4 堤选择估计用到的最多的一种方案。它的基本思想是：去除低频访 问的结点，进行汇总。它与x m l 文档树的结构很相似，不同之处在于路径树中对 于那些同名的兄弟结点只记录一次，而且每个结点保持一个频数信息，表示在原 文档中该名称的结点个数。路径树虽然能够很好地计算路径表达式的选择度，但 是问题在于这样的路径树规模可能会很大，因此需要进行概括。这样就涉及到删 除低频结点，并且还要为删除结点保留一些信息，这是通过将删除结点归为“”结 点来实现。有五种汇总方案i 巧1 ： 4 f 绪论 ( 1 ) s i b l i n g - * 首先将频数最低的那些路径树的结点加上删除标记。如果兄弟 结点都标上了删除标记或者其中有“事”结点，则将这些兄弟结点合并为一个“”结 点，它们的孩子结点也都成为“”结点的孩子，如果这些结点有同名的则将其合并。 孩子结点的合并可能又会导致后裔结点的合并，依此类推。对于”结点，其频数 为它所代表的所有结点的频数的平均值，对于那些标记名不为“”的合并结点，则 需同时保留其频数之和以及平均频数。 ( 2 ) l e v e l ：将所有在同一层的删除结点归并为一个“”结点，这些结点的双亲 也就成为了“”结点的双亲，它们的孩子都是”结点的孩子，同理如果这些孩子同 名，则将其合并。这种概括方法更加不精确，但能更快降低路径树的规模。基于 这种方法的估算过程与s i b l i n g - * 策略类似。这种概括结构形成的是一个有向无环 图。 ( 3 ) g l o b a l ：整个路径树中只有一个“”结点，所有被删除的结点都用这个“” 结点表示，类似的被删除结点的双亲成为“”结点的双亲，它们的孩子成为“”结点 的孩子，这种概括后的结构实际上是一个有环图。 ( 4 ) n o ：删除的结点不保留任何信息，也不用“”结点表示。在这种结构里路 径成为了森林。 1 2 研究现状 运用重写机制对x q u e r y 查询进行优化是本文的研究重点。目前国内外的重写 机制的研究工作主要集中在结构重写和视图重写上。比如由a l i nd e u t s c h 、y a n n i s p a p a k o n s t a n t i n o u 和y ux u 三人提出的n e x tf r a m e w o r k ”j ，就涉及到标准x q u e r y 重写规则和g r o u p b y 重写规则。莫斯科大学的m a x i mg r i n e v 以及s e r g e yk u z n e t s o v 实现了b i z q f i e r y l 2 7 墟拟数据整合系统的一部分，其中涉及到重写代数，f l w r 表 达式的重写规则以及x q u e r y 函数和递归函数的重写规则，并且还指出了在重写中 x m l 模式的重要性。江西财经大学的万常选等提出的基于x - r e s t o r e 查询x m l 视图幽】，实质上就是x m l 视图查询的合成重写技术，它能够消除视图查询中所有 在视图结构上的路径导航操作，并将视图查询中所有在原文档结构上的路径导航 操作以及所有谓词操作下推到视图定义中去，与视图定义中的路径导航操作相结 合，形成统一的在原文档结构上的路径导航操作。i b ma l m a d e nr e s e a r c hc e n t e r 的f a t m a6 z c a n 提出了d b 2 的重写机制【2 ”，提出了一套查询重写转化规则，这个 规则主要是基于启发式原则，例如使得选择操作尽量早做，而且这个规则是基于 规则引擎的一部分，例如将规则组织成类；同时将表达式进行简化，谓词操作进 行下推等。加利福尼亚大学的y a n n i sp a p a k o n s t a n t i n o u y 和斯坦福大学的v a s i l i s v a s s a l o s z 提出的半结构化数据的查询重写机制四】，主要是用于半结构化查询语言 的重写，基本思想是给定一个半结构化查询和一个半结构化视图来找到重写查询， 5 基于重写机制的x o u e r y 查询优化技术研究 这个查询重写机制用在t s i m m i s 系统中。由以色列耶路撒冷h e b r e w 大学的 c a t f i db e e f i 和美国新泽西州人工智能原理研究部门的a l o ny k v y 以及法国的 m a d e c h r i s t i n er o u s s e t 提出的用逻辑描述来进行查询重写口“，基本思想就是仅仅 运用视图集合的表达式来进行重写。其中分成两种情况，第一种是视图定义中包 含有存在变量的情况；第二种是没有包含存在变量的情况。但无论对于哪种情况， 由一个算法来产生递归重写，使得这个重写成为最大化重写。 1 3 本文主要研究内容 本文讨论的是x q u e r y 语言的查询优化问题。基于这样的前提，文章对问题存 在的三个方面作了分析，分别进行了三部分讨论： 第一部分是采用x q u e r y 到s q l 的查询语言转换方案【3 2 3 9 1 ，目的不仅是实现 x q u c r y 在关系数据库中的查询处理，更具现实意义的是能够充分利用关系引擎的 已有功能，降低问题难度并可提高解决问题的效果。 第二部分是对于已有x q u e r y 查询语句的基础上，对x q u e r y 语句进行逻辑上 的优化。具体就是首先输入一条x q u e r y 语句，其中这条原始语句可能涉及到多个 数据源，可能涉及到嵌套查询甚至还有可能有g r o u p b y 操作等等，然后通过重写 机制进行重写，生成逻辑x q u * r y 语句。最后将重写后的x o u c r y 语句进行最小化 处理，其实质就是消除冗余，最终达到优化的目的。基于此，对于有多个数据源 的情况，首先要从该文档的目标模式，源模式到目标模式的映射集，以及源模式 中的数据入手；对于给定的查询表达式，则通过构造物化视图来进行相关处理。 第三部分是根据研究方向侧重点的不同，主要研究重写机制，而这个重写主 要集中在视图重写上，其中主要集中在x p a t h 物化视图重写的研究上。根据上面 的特点，将用户查询表达式建模成x p a t h 查询表达式，然后给出物化视图，通过 它们之间的匹配进行重写查询。 1 4 本文的组织结构 第2 章概括介绍了x o u e r y 相关知识。主要介绍了x q u e r y 语法以及x q u e r y 编译器相关内容。 第3 章详细讨论了x q u c r y 到s q l 的语言转换处理，并对典型解决方案进行 了实验分析与对比。 第4 章讨论了本文面临问题的实质，从目标模式，源模式和目标模式之间的 映射以及源模式中的数据分析了该问题，详细讨论了重写机制的概念以及多数据 源重写机制。 第5 章详细讨论了基于x p a t h 物化视图的查询重写机制。其中重点是对匹配 算法进行了详细地设计，并在此基础上给出了一个具体的实例演化过程。 第6 章对全文进行总结，并提出了进一步的改进工作。 6 2 x o u e r y 相关知识 2 x q u e r y 相关知识 2 1 x q u e r y 语言 自从计算机网络普及后，互联网便成为了人们获取信息的重要手段之一，随 着技术的日新月异，人们在互联网上查询数据的需求也愈加强烈，鉴于非结构化 数据的查询工作以及结构化的关系数据库查询已经相当成熟，但对于半结构化数 据的查询人们需要一种更优化的数据查询机制，x q u e r y 以其良好的设计和强大的 功能扮演了这个角色。x q u e r y 是一个从x m l 格式的文档中获取数据的查询语言， 起源于x m l 数据查询语言q u i l t 删。q u i l t 有很多非常优秀的特性，集s q l 、o d m g 、 x p a t h l 0 、x q l 1 】以及x m l - q l l 4 2 】的诸多特性于一身。 x q u e r y 规范启动于1 9 9 8 年w 3 c 发起的查询语言波士顿专题讨论会，根据对 x m l 的使用，与会的成员可以划分为两类，第一类是将x m l 主要作为文档使用 的人，第二类是将x m l 作为数据使用的人。直到2 0 0 1 年2 月，工作组的发布工 作开始大踏步地进行，大量的文档开始推出。在2 0 0 1 年6 月和1 2 月、2 0 0 2 年8 月和1 1 月、和2 0 0 3 年5 月进行了重要更新。在2 0 0 3 年5 月加入了一个x q u e r y 序列化和两个全文相关的工作草案后，1 2 个文档基本完成，工作草案正在接近收 尾工作。这1 2 份重要的文档包括： 1 1x m l q u e r yr e q u i r e m e n t s 4 ：此文档是工作组的规划文档。包含x q u e r y 需求列表。 2 1x m l q u e r yu s ec a s e s t s l ：此文档提供了解决特定问题的几个实际方案和 x q u e r y 代码片段。 3 1 x o u e r y1 o ：a n x m l q u e r yl a n g u a g e 6 ：此文档是工作草案中的核心文 档 介绍语言本身，以及对大多数其他内容的概述： 4 1x q u e r y1 0a n dx p a t h2 0d a t am o d e l l 7 1 ：此文档是x m l 信息集的扩展。 描述查询实现必须理解的数据项和形式语义的基础。 5 ) x q u e r y1 0a n dx p a t h2 0f o r m a ls e m a n t i c s 【8 】：此文档从形式上定义语言 的底层代数。， 6 ) x m l s y n t a x f o r x q u e r y l 0 ( x q u e r y x ) 【3 l ：此文档为喜欢使用x m l 的人 提供的另一种语法。任何地方的机器都可以使用。 7 ) x q u e r y1 0a n d x p a t h2 0f u n c t i o n sa n do p e r a t o r sv e r s i o n1 o 【9 l ：此文档描 述了s c h e m a 数据类型、x q u e r y 节点和节点序列的基本函数和操作符。 8 ) x m l p a t hl a n g u a g e ( x p a t h ) 2 0 【3 】：此文档是单独分离的x p a t h 文档a 9 ) x p a t hr e q u i r e m e n t sv e r s i o n2 0 1 3 1 ：此文档是x p a t h 的需求文档。 1 0 ) x s l t2 0a n dx q u e r y1 0s e r i a l i z a t i o n 3 l ：此文档介绍了x s l t2 0 和 x q u e r y1 0 的详细情况。 7 基于重写机制的x o u e r y 查询优化技术研究 1 1 ) x m lq u e r ya n dx p a t hf u l l t e x tr e q u i r e m e n t 3 】：此文档描述了f u l l t e x t r e c o m m e n d a t i o n 需要达到的功能需求。 1 2 ) x m lq u e r ya n dx p a t h f u l l t e x tu s ec a s e s l 3 1 ：此文档提供了f u l l t e x t 规 范范预期能够处理的实际情况。 2 1 1 查询结构和表达式 x q u e r y 遵循一定的查询结构l 矧，一个完整的查询包含两个部分：查询序言 ( q u e r yp r o l o g ) 和查询体( q u e r yb o d y ) 。查询序言包括一系列处理查询体的定义声 明；查询体是一段查询表达式，是x q u e r y 的主体部分。当查询体需要用到名字空 间、模式信息、或函数时，就需要在查询序言部分有相应的声明。x q u e r y 表达式 是x o u e r y 中每一个元素的最高程度的抽象，并且是x o u e r y 中的基本构建块，是 x q u e r y 查询的基础。x q u e r y 定义的表达式由关键字、符号以及操作数组成。通 常，表达式中的操作数也是表达式。x q u e r y 是函数化的语言。x q u e r y 也是一种 强结构化的语言，表达式中的操作数、算子、函数必须遵循已经定义好的模式。 x q u e r y 中共有七种表达式： 1 1 路径表达式：路径表达式是在x p a t h 语法基础上发展而来的，提供了一个 方法来寻找x m l 文件以及一些操作字符串、数字和布尔值的基本函数。x m l 文 件建模成结点树模型，这些结点包括有元素结点、文字结点、属性结点、命名空 间结点、处理函数结点和批注结点。 2 ) 构造器( c o n s t r u c t o r ) ：一个查询通常需要创建新的元素。x o u e r y 提供了查 询中的构造器来创建x m l 片断。构造器可生成元素、属性、c d a l a 段、过程说 明和注释。一个元素构造器可以构造生成一个x m l 格式的元素。如果新元素的名 字、属性和内容都是常量，那么元素构造器就可以使用标准的x m l 格式标记。 x o u e r y 提供了两种构造器：直接构造器和计算式构造器。前者使用x m l 式的表 示法，后者使用闭合表达式的表示法。下面介绍这两种构造器： ( 1 ) 直接构造器 当元素和属性值为常量的时候，元素构造器的x m l 标记语法和x m l 的语法 一样。元素构造器必须遵循和x m l 一样的规则。但是元素的内容也可以是动态的， 这就要使用闭合表达式。例如： h e r e i st h er e s u l to ft h eq u e r y ( e g $ 袱i t l e ) 其中用 ) 括起来的的就是闭合表达式。它与一般表达式的不同之处在于里面 8 2 x o u e r y 相关知识 一般含有变量，它的值是动态计算出来。 ( 2 ) 计算式构造器 下面给出了一个计算式构造器的实例，如下： e l e m e n tb o o k a t t r i b u t ey e a r 2 0 0 6 ”) ， e l e m e n tt i t l e ”代码大全( 第二版) ” ， e l e m e n ta u t h o r e l e m e n tf i r s t s t e v e ” ， c l e m e n tl a s t m c c o n n e l l ” 这个例子构造了一个b o o k 元素，它有一个y