（计算机软件与理论专业论文）xquery查询语句的解析、分析和查询优化.pdf

摘要 摘要 x m l 已经成为互联网上数据发布和交换的事实标准，而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 r y 查询语言。 其次，在考察当前的一些y & i l 存储和查询技术和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 r y 查询特点的分析上。 对批量查询的模式树森林，文章应用上述算法挖掘出其频繁子树，并根据 条件挖掘出频繁子树的各个节点上的频繁约束，这样就能得到频繁查询的x m l 文档节点信息。将这些频繁查询存储到物化视图中。利用物化视图和用户查询 的交叉部分，直接从物化视图中获取用户的查询内容。对于物化视图和用户查 询不完全匹配的部分，文章给出了相应的补充规则，使得能够部分使用物化视 图，以达到提高查询效率的目的。 最后，本文实现了基于用户查询特点的x m l 查询优化系统，也给出了该系 统对d b l p 上的几个查询优化前后的查询性能测试比较。 关键词：x m l ，x q u e r y ，模式树，物化视图，查询优化，树挖掘，约束 挖掘 兰塑! 璺：奎塑至望盟堡堑：坌塑塑壅塑垡些 a b s t r a c t x m lh a sb e e nt h ed ef a c t os t a n d a r df o rd a t a r e p r e s e n t a t i o na n d e x c h a n g eo nw e b ，a n dx o u e r yh a sb e e nw i d e l ya c c e p t e da st h es t a n d a r dq u e r y l a n g u a g eo fx m l a n a l y s i st ox q u e r ys e c t i o n sw i i lb eu s e f u lt oi m p r o v e t h eq u e r yp e r f o r m a n c ea n do p t i m i z ex m lq u e r i e s b a s eo nt h a t ，w ea n a l y s i s a1 a r g es e to fx q u e r ys e c t i o n s 。a n da c r o s st oi t sr e s u l t ，w eo p t i m i z e t h ex m lq u e r y f i r s t l y ，w ep r e s e n tc o m p l e t e l yb u ti nd e t a i lw h a tl a n g u a g ex q u e r y i s s e c o n d l y ，a f t e rd e e p l yi n v e s t i g a t i o no nt h et e c h n o l o g i e sa b o u tt h e x m ls t o r a g ea n dq u e r ya n dx q u e r yp a r s e r ，w ed e s i g nap r o p e rx q u e r yp a s e r ( x o p a r s e r ) f o ro u r ls t o r e q u e r ys y s t e m ，r e d e f i n et h eo p t i o n o f p a t t e r nt r e e ，p r o v ei t sc h a r a c t e r s ，a n du s ei ta st h ed a t am o d a lf o rt h e x q u e r ys e c t i o n s t h i r d l y ，a c c o r d i n gt o s o m ee x i s te x c e l l e n ta l g o r i t h m ，e s p e c i a l t h o s et r e em a t c h i n ga n dt r e em i n e r ，w eb r i n gf o r w a r do u rp a t t e r nt r e e m a t c h i n ga l g o r i t h m ( x q g a t c h ) a n df r e q u e n t s u bp a t t e r nt r e ed i s c o v e r a l g o r i t h m ( o x s p a n n e r ) w et e s te a c ha l g o r i t h m a n d g i v ee a c hp e r f o r m a n c e o t h e r w i s e w ef i r s tw o r ko u ta na l g o r i t h m ( f c m i n e r ) t od i s c o v e rt h e f r e q u e n tc o n d i t i o n so ft h et r e en o d e a n da p p l ya l lt h e s ea l g o r i t h m so n d i s c o v e r i n gx m lq u e r i e s f o ral a r g es e to ft h ex q u e r y ，w ed i s c o v e ri t sc h a r a c t e r ，s u c ha s f r e q u e n t l yq u e r i e ds u bp a t t e r nt r e ea n dw i t hi tt h ef r e q u e n tc o n d i t i o n ， w h i c hw ec a l lu s e r sq u e r yc h a r a c t e r a c c o r d i n gt ot h e s ec h a r a c t e r s ， w eu s em a t e r i a l i z e dv i e wt os t o r et h ef r e q u e n t l yq u e r i e dx m ld a t a s o t h a tw ec a ng e ta n s w e rf o rt h o s eq u e r i e sw h oa r es i m i l a rt ot h ef r e q u e n t q u e r yf r o mt h em a t e r i a l i z e dv i e wi n s t e a do ff r o mt h e m a s sx m ld a t a b a s e s l a s t l y ，w er e a l i z e dax m ls t o r ea n dq u e r ys y s t e mw h oi n c l u d e st h e o p t i m i z i n gs u bs y s t e mb a s e d o nt h eu s e r sq u e r yc h a r a c t e r s ，a l s ow et e s t t h iss y s t e m sp e r f c ，r m a n e e k e yw o r d s ：x m l ，x q u e r y ，p a t t e r nt r e e ，m a t e r i a l i z e dv i e w ，q u e r yo p t i m i z e ， t r e em i n i n g ，e o n d i t i o nm i n i n g x q u e r y 查询语句的解析、分析和查询优化 第一章绪论 1 1 w e b 数据、x m l 和数据库 互联网的出现带给人们一个问题，那就是如何表示互联网上的数据，即 w e b 数据。w e b 数据和传统的数据中的数据不一样，它们一般不遵循任何广为 使用的结构( 如关系结构或对象层次) ，所以不能直接使用传统的数据库来保 存这些数据。为此，人们提出了各种方法用来存放和表示w e b 数据。h t m l 就 是其中广为流行的一种w e b 数据表示形式。h t m l 是从s g m l ( 标准通用标记语 言) 演化而来，它放弃了s g m l 定义中复杂的数据定义，仅仅保留很小的标签 集合用来定义数据的表现形式，由于其短小精悍，易于掌握，特别是它在w e b 数据呈现方面的优越特性，使得h t m l 流行起来。但是，随着一些新应用开始 在互联网上出现，如电子商务等，各种应用终端和服务器之间的数据交换变 得非常重要。再者，由于h t m l 数据抛弃了数据的结构信息，也使得大量的h t m l 格式的内容只能通过全文检索的方式进行查询，准确率不高。为了解决h t m l 信息的结构不确定性和w e b 数据交流问题，w 3 c 万维组织，在1 9 9 8 年提 出了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 数 据和文档结构。 和h t m l 一样，x m l 也是从s g m l 中演化而来的，但和h t m l 旨在表现数据 不一样的是，x m l 则旨在描述数据和数据的逻辑结构，它不但保持了s g m l 的 功能，还减少了s g m l 的复杂性。随着x m l 的应用深入，它的优秀性能在很多 领域都呈现出来了，如软件开发、网站运营、移动互联等，它还可以解决网 络中跨平台的数据交流问题，使不同的网络信息可以以精确的、可供人和机 器分析并加工的结构化、半结构化数据的形式向外界提供。事实上，x m l 已经 成为w e b 数据表示和交流的国际标准。 为了能被浏览器正确处理，x m l 文档在创立时就应该遵从一些既定的规 则，如x m l 文档的元素名、属性名、元素之间的关系和元素之间的顺序等， 这些规则一般写进一个独立d t d 文档或s c h e m a 文档。任何x m l 文档只有遵循 了它的d t d 或s c h e m a 才是正确的。可以说，d t d 或s c h e m a 就是x m l 文档的数 据结构描述。d t d 一般呈树状，也就是说，x m l 也遵循某种数据结构，正是这 一点，使得x m l 数据库的建立成为可能。 为了要利用那些蕴含在x m l 文档中的信息，也由于他们遵循了一定的d t d ( 或s c h e m a ) ，人们提出使用数据库来保存x m l 文档。使用数据库来保存x m l 文档具有以下优点：，可以长久地保存x m l 数据，便于充分利用已有的x m i 信息；二，可以借鉴已有的数据操作技术和查询优化技术来优化x m l 查询。 三，使得x m l 数据和已有的大量的传统数据库数据一起使用成为可能。 目前，许多主流的数据库厂商都把x m l 支持结合到其产品中，或者提供 可在其数据库中使用x m l 的工具。i b m 提供的x m le x t e n d e rf o rd b 2 ，允许 用户在d b 2 中存储x m l 文档，并提供些新功能协助用户处理x m l 文档： m i c r o s o f t 的s q ls e r v e r6 5 和7 0 也进行了x m l 扩充，能将关系数据库中 的数据以x m l 的形式对外发布。o r a c l e 也拥有功能强大的x m l 索引引擎。 可以说，在未来的信息领域，x m l 数据，和传统数据库一样，是一种非常 重要的信息来源。而且，x m l 数据库也将变得海量，对查询系统的响应时间要 求也将越高。因此，对) n l 查询的分析及其在查询优化方面的应用的研究也 就变得重要了。 1 2 相关工作 1 2 1 x m l 查询语言和x q u e r y 的实现 到目前为止，工业界和科研界提出了不下十种x m l 查询语言，根据语言 提出者的学术背景，它们可以分为两类：一类来自文档研究领域，如x s l 和 x q l ；另一类来自数据库研究领域，如l o r e 【a 伽9 7 】、x m l g l 【c c d 9 9 】、x m l q l d f f 9 9 和q u l i t c r f 9 9 等。关于其中比较流行的查询语言，请参见2 1 节。 但随着x q u e r y x q u e r y l 的问世，由于它功能完整，灵活性高，且易于 理解和实现，越来越多的系统都以它为x m l 查询语言。事实上，x q u e r y 已经 成为了标准的x m l 查询语言。 近两年来，国内外许多大的公司、组织机构和科研单位都在研究x q u e r y 的实现。到目前为止，已经有一些开发成功的x q u e r y 解析器，如：x h i v e 公 司开发的x q u e r y 编译器 x h i v e 、x s m 系统【l m p 0 2 】、威斯康星大学开发的 x p 系统 o m 0 2 、x p e r a n t o 系统 s k s 0 1 】、伍斯特工艺研究院开发的r a i n b o w 系统等，已经是一些比较成熟的x q u e r y 编译器：还有一些解析器还处在原型 阶段，如：f a t d o g 公司的x q e n g i n e 编译器 x q e n g i n e 、b r a i n f o o d 公司开 发的q e x o 系统，另外【m j 0 3 1 等文章也可以说明了科研届在这一方面的研究 成果。这些系统的实现方式多种多样，每一个的编译能力也有所不同，但其 主要技术思路一般都遵循下面两种：1 直接将x q u e r y 语句翻译成s q l 语句， 如上述x p e r a n t o 系统；2 将x q u e r y 查询表示成某种数据模型，如上述x s m 系统，它将x q u e r y 查询表示成名为x s m 的图形模式，而x q g m 则将x q u e r v 查 询表示成作者自定义的一系列函数和操作。他们的实现方式依赖于包含他们 的x m l 存储查询系统。使用关系型数据库存储x m l 数据的系统，多半将它的 x q u e r y 语句直接或稍傲处理地翻译成s q l 语句。这种做法存在以下缺点： 1 导致查询失真。有些x q u e r y 的语言成分不能直接用s q l 语句表示，如 t y p e s w j t c h 、i f - e l s e 语句，s o l 语句也没有x q u e r y 语句那么丰富的 表达式，不能区分值比较和一般比较，也没法表达节点比较； 2 无法对x q u e r y 查询做一些x m l 查询特有的优化。x m l 查询的数据结构 是树，有一些自己的查询优化特点，如果直接将它翻译成s q l 查询， 那么其查询优化策略只能是关系数据库管理系统的优化策略； 为了克服这些缺点，本文的解析器使用模式树来表示x q u e r y 查询，在适当的 查询优化之后将它映射为s q l 查询，再通过关系数据库管理系统的优化策略 ( 如索引等) 来优化查询。和其他采用某种数据模型表示x 啪e r y 查询的解析 器不同的是，本文使用的模式树，是一个有理论依据( j l s 0 1 】) ，被证明了的， 且广为接受的x m l 数据模型。 1 2 。2x m l 查询代数的研究 关于x m l 查询代数的研究中，典型的有：t a x 代数系统( 3 l s 0 1 】) ，该系 统定义了x m l 数据的存储形式、数据模型和各种数据结构，它使用模式树表 示x m l 数据，详细说明了x m l 查询中的选择、投影、连接等操作，它所提出 的模式树的概念，在x m l 查询中，得到了广泛的应用；w i s c o n s i n 大学开发的 n i a g a r a 系统( 【g a l a 0 1 】， v g d 0 2 】) ，这是一个x m l 查询系统，该系统定义了 x m l 数据的操作符s e l e c t 、s o u r c e 、f o l l o w 等；v a t l ( c d s 9 8 】) ，它从数据 交换的角度定义规则，以实现不同的数据操作，后来， c c s o o 在y a t l 的基 础上定义了两个操作：t r e e 和b i n d ：a t & t 代数系统( 【f s w 0 1 】) ，它使用循环 结构对每个x m l 元素进行处理。 1 - 2 3x m l 存储查询系统设计 x m l 存储查询系统很多，其中比较著名的有s t a n f o r d 大学开发的l o r e l 系统【m a r 】【a q 旧7 】【p g w 、t i m b e r 系统【j a l 0 2 】和n i a g a r a 系统。归结起 来，它们大体采用下面几种技术路线：一，使用文件系统来存储和检索x m l 数 绪论 掘。这种方法直接将x m l 文档以文件的形式存储，在文档存储和查询结果发布 时，无需进行数据格式的转换。但文件系统没有数据查询检索的功能，每次查 询都要将x m l 文档解析d o m ，而且在查询中，整个文档都需要驻留在内存中， 所以这种方法不适合于数据量大的x m l 文档的查询，而且它的查询效率也是最 低的。一般基于流的x m l 数据查询系统都采用这种技术。二，使用半结构化数 据仓库来管理x m l 数据，这种方法将x m l 存储为有向图，上述l o r e l 系统就是 一个例子，l o r e l 系统在管理半结构化数据方面很出色，但在x m l 数据的管理 中，却没有得到广泛认可。三，使用关系数据库或者面向对象数据库来管理x m l 数据。使用这种方法，每一个) 【m l 文档导入数据库时，以及查询结果发布时， 都要进行x m l 和二维表之间的转换，但数据库成熟的查询优化技术和索引技术， 使得这种方法下的查询效率很高。而且，目前已经有很多比较成熟的x m l 映射 算法，完全可以很好地解决上述x m l 和二维表之间的转换。另外，x m l 文档可 以长久地保存下来，和结构化数据交互，一同为人们所使用。商用的关系数据 库管理系统已经得到了广泛使用，很多已有的数据也都存放在它们中，它们的 稳定性、安全性和健壮性也为数据使用者提供了保障，所以这种方法是最值得 提倡的一种。四，使用n a t i v e 系统进行x m l 数据管理，上述t i m b e r 就是一例。 这种系统一般使用某种内部数据模型来表示x m l 数据，以文档作为数据处理的 单元，不要求特定的物理存储模型。它的优点在于它能完整地保存x m l 的分层 结构，而且在进行数据处理时无需进行格式转换，但它不适合细粒度的查询， 对现存的大量以关系模式存储的数据不能很好地加以利用，投入成本较高，而 且它的查询性能也不是很好。目前，很多公司都在进行n a t i v ex m l 系统的开发， 如d b y 0 l l 、e x c e l o n 和x h i v e d b ，它们分别由美国的d b x m lg r o u pl l c 公司、 e x c e l o n 公司和荷兰的t h ec o n n e c t i o nf a c t o r y 公司研制。 由于使用关系型数据库管理系统存储数据库具备上述种种有点，我们的 x m l 存储查询系统采用了第三种技术路线。 1 2 4 频繁子树发现算法和树匹配算法的研究 目前，已经有一些工作探讨了频繁树的抽取问题。【z a k i 0 2 】【k u r a o l 】 d t k 9 8 】【m h m 9 9 】 m s u 2 0 0 1 】 w h 9 7 1 w s s 9 6 1 就是一些这方面的工作。其中 z a k i 0 2 】【w h 9 7 】 w s s 9 6 1 主要集中在频繁子树的挖掘问题上，【w s s 9 6 】利用 a p r i o r i 算法的思想，在有序树中挖掘频繁路径集；而【w h 9 7 】则尝试使用有 向生成测试的方法；另外，利用m d l 原则发现图模式的s u b d u e 系统【c h 9 4 】， 由于它采用了一些“贪婪”的搜索算法，因而会丢失一些重要的模式； d t k 9 8 1 x q u e r y 查询语句的解析、分析和查询优化 提出的基于挖掘频繁子结构的i l p ，这些子结构用于描述化合物的致癌作用， 它主要实现的是图的频繁模式的挖掘，并不适合用于频繁树的挖掘；其他诸如 a g m 等算法都是基于a p r i o r i 算法的思想，在运行过程中产生大量侯选集成为 了算法性能的瓶颈。【z a k i 0 2 k u r a 0 1 】和本文采用本小组提出的x s p a n n e r 算 法运用最右扩展技术在森林中寻找频繁树，也就是说，在树中添加节点的时候， 使其节点仅添至树的最右分支上。 因为树的匹配可能非常复杂，所以其算法的研究一直是计算机理论研究中 的一个难点。早期的树匹配算法多基于胁和h o f f m a n 算法的基础上，或从上到 下地进行比较，或从下到上地进行比较，如 h d 8 2 ：。但由于树结构的内嵌性， 这些算法的时间复杂度一般都是指数级的。后来也有很多研究者提出了一些性 能更好的算法，如 k r e 9 9 y l h 0 3 s w g 0 2 】等：其中 s w g 0 2 使用后缀数 组优化树匹配算法的时间性能。该算法将树分解成根到叶子路径集，然后为这 些根到叶子路径建立后缀数组，最后通过比较这些根到叶子路径，来计算两棵 树的距离。这种方法将树匹配这一n p 难问题转化为字符串的比较，大大地降低 了树匹配的时间复杂度，使得可以在线性时间复杂度上进行树的匹配。 但包括 s w g 0 2 在内的大部分树匹配算法，都没有考虑边的情况。实际存 在的很多树中，有的边是父子边( 即边所连接的两个节点之间是父子关系) ，而 有的边是祖先后代边( 即边所连接的两个节点之间是祖先后代关系) 。这种现象 在x q u e r y 查询应用中特别频繁，人们经常要通过某个x m l 元素来访问它的后代 元素或它的祖先元素。x o u e r y 语句的路径表达式也支持模糊路径的表达。这些 都要求树匹配算法支持非父子边的比较。 鉴于上述考虑，本文设计了一种适合x q u e r y 查询特点的匹配算法 ( x q m a r c h ) 。该算法同样认为树是根到叶子路径的有序集合，并建立x m l 文档的 d t d 数据库，通过每一个叶子节点来查询其完整的根到叶子路径，然后通过根 到叶子路径的比较，来确定两个查询是否匹配。同样地，x q m a t c h 也避开了树 内嵌的结构，将它转变成字符串来比较，以减少算法的时间复杂度。但d t d 数 据库的使用，使得该算法能支持x o u e r y 的查询匹配。 1 2 5 物化视图在传统数据库查询中的应用 在数据库的查询中，相当一部分查询是复杂的，通常需要涉及大量的数据， 而且一般要对数据进行投影、连接、分组等复杂处理，这是一个非常耗时的过 程。然而数据库应用系统却要求它的查询能够被快速响应。解决这个矛盾可能 所采用的方法是：数据库针对可能的查询对原始数据进行投影、连接、分组等 预处理，建立许多“物化视图( m a t e r i a l i z e dv i e w ) ”。物化视图与数据库的“视 图”概念不同之处在于：它不是虚拟的，而是经过计算，含有大量数据，并存 储在数据库的一张实实在在的表中的。通过这些预计算，数据库的数据操作引 擎基本上不再需要对原始数据进行复杂处理，而只需在物化视图的基础上进行 一些简单的计算便可以完成复杂的查询。 作为一种查询优化技术，物化视图已经在传统数据库的应用领域内得到了 认可。那么物化视图能不能引入x m l 数据库的查询优化中呢? 答案是肯定的， 其优势甚至更为明显。不管x m l 是以怎样的方式映射到数据库中的，在查询x m l 时，都需要将x m l 各个元素按其语义进行连接，这种连接可能涉及很多个表( 由 x m l 的存储策略决定) ，如果数据量大的话，其时间消耗是非常大的，所以对于 复杂的查询，和传统数据库一样，我们可以将可能查询到的数据事先选择、连 接，形成x m l 的物化视图，并以此来优化x m l 查询。 使用物化视图主要存在两个主要的问题：一是如何选择物化视图，另一个 就是如何维护物化视图。在传统数据库中，有的两种物化策略比较简单，如i b m 的v i s u a ld a t aw a r e h o u s e o l a ps e r v e r 。在这种策略中，用户可以在第一次 访问物化视图时初始化它，此后的访问就可以直接访问物化视图中的数据，而 不必即时算，其优点是实现简单，且在系统中填充数据不是很多的时候效率较 好；缺点是首次发出一个查询可能要经过很长时间才能得到结果，并且在填充 的视图越来越多以后，怎样挑选一些不常用的，填充代价小的视图，将其清除 出数据仓库也是一个很复杂的问题。也有的系统尝试使用贪心算法来选择物化 视图。 物化视图的维护问题可以分成两个方面，其一是物化视图中数据的维护问 题：视图中的数据来源于其它独立的传统数据库，当这些数据库的原始数据发 生变化时，物化视图也必须与原始数据的变化保持同步，这种同步通常采用增 量更新的方式进行，在传统数据库领域中，【z l c 】、 c k p 9 5 等对这一问题进行 了深入的研究；其二是物化视图本身模式的维护：数据库系统的特征决定了用 户的兴趣点和使用数据仓库的方式会不断地发生变化，从而要求物化视图的选 择也随之变化，以确保查询响应时间是满足用户要求的、最优的。 1 3 本文主要工作 本文是国家8 6 3 项目“w e b 新数据库技术”中的一部分。下图就是该项目 中x m l 存储查询系统的总体结构图。该存储查询系统使用关系数据库存放x m l 数据，将所有的x m l 文档通过映射器转换为关系。而用户提交一个x m l 查询 ( x q u e r y 语句) 以后，系统使用x q p a s e r 解析它。解析的结果分两部分，一部分 x q u c r y 查询语句的解析、分析和查询优化 和查询条件相关，另一部分是查询结果的格式，包括用户在查询中自定义的x m l 元素等。查询条件将被解析成模式树，而查询结果格式将被解析到结果文档格 式中。对于模式树，系统先按照x m l 的代数系统( 参照 j l s 0 1 】定义的) 进行 查询优化，再将这些查询通过查询重写模块改写为s q l 查询，并向关系数据库 提交这个s q l 查询。得到查询结果以后，根据查询结果文档，并通过x m l 发布 器将查询结果表转换成x m l 文档，返回给用户。 本文的主要研究目标是对系统中收集到的多个x q u e r y 查询语句进行分析， 以发现各种用户的查询特点，并根据这些特点做相应的查询优化。用户查询特 点主要体现在两个方面：一是频繁查询到的节点信息，另一个是查询中频繁出 现的查询约束。我们认为，用户的查询兴趣虽然会随着时间的改变而改变，但 在一段时间内，仍然能保持这样的兴趣。频繁查询就是用户的查询特点，我们 对用户已提交的x q u e r y 查询语句进行解析和分析，得到频繁查询，并建立频繁 查询的物化视图，以便快速地响应那些和频繁查询匹配的查询。 图1 ：x l l 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 的大部分语言要素。 在前人的基础上，扩展了模式树的概念，并证明了模式树的许多性质。 设计了x q u e r y 查询的特点挖掘算法，如图2 ( a ) ( c ) 所示，也就是频 繁子树挖掘算法、频繁约束挖掘算法以及树的匹配算法。给出了这些 算法的详细描述和性能测试结果。 设计了种适合x q u r e y 的查询匹配算法。如图2 ( b ) 所示，该算法利 用x m l 树的特点进行查询匹配。和其他查询匹配算法相比，该算法更 能解决x m l 查询匹配的特殊性，性能也很不错。 设计了一种使用物化视图进行x m l 查询优化的系统。如图2 ( b ) 所示， 该系统根据用户查询的特点构造物化视图，在查询时，将用户查询和 频繁查询进行匹配，匹配部分直接从物化视图中得到查询结果，不匹 配部分从原数据库中获得查询结果。 ， x q u e r y 语句群 l 用户查询特点挖掘器 ( a ) 频繁查询发现模块 ( b ) ：查询匹配模块 ( c ) ：用户查询特点挖掘器详解 图2 ：本论文的查询优化系统图解 x q u c r y 查询语句的解析、分析和矗询优化 1 4 文章结构 在接下来的章节中，文章是这么安排的： 在第二章中，我们将系统地介绍x q u e r y 查询，包括相关x m l 查询语言 比较和x q u e r y 的体系结构，重点讲述x q u e r y 的语言成分。 在第三章中，我们将完整地介绍x q p a r s e r 本文所使用的x q u e r y 解 析器，包括解析器的数据模型、解析技巧和x q p a r s e r 的性能测试。 在第四章中，我们将介绍用户查询特点挖掘器和相关的特点挖掘算法， 重点会介绍算法的实现和算法的性能。 在第五章中，我们将介绍本文的优化策略。 第六章给出整个查询优化系统的性能测试结果。 第七章是结论和展望 9 x q u e m 鸯洵语言 第二章x q u e r y 查询语言 2 1x m l 查询语言的演变 早在x m l 正式推出之前，数据库研究人员就注意到现实世界中存在的大量 的半结构化的数据。这些数据中同样存在大量有用的信息，但出于结构的不确 定，我们不能使用传统的数据库管理系统，像管理传统数据一样，来管理他们。 因此，研究人员提出了各种适合他们的数据模型和查询语言，其中最著名的就 是加州大学计算机系提出的l o r e l 。它是在o q l 的基础上发展起来的，其语法 结构也是s e l e c t f r o m - w h e r e 。x m l 正式推出以后，l o r e l 也能用于查询x m l 数 据。因此l o r e l 是第一批删l 查询语言的典型代表。 随着互联网的飞速发展和x m l 数据格式的推广，怎样才能快速有效地查询 x m l 信息也就变得越来越重要了。为了解决这个问题，研究人员又陆续提出了 多种富有影响的x m l 查询语言，包括著名x s l c l a r 9 8 、x q l r l s 9 8 1 、x m l q l 、 q u i l t 、x m l g l 、x p a t h 【b e r 9 0 2 等： x s l 由w 3 c 组织的x s l 工作小组设计，是一门扩展样式语言。一个x s l 样式表集合了一系列设计规则，用以从x m l 文件中提取信息，并将其 转换成h t m l 等其他格式。x s l 使用x p a t h 导航节点和定义筛选条件。 x q l 是微软公司提出的一种x m l 查询语言，是x s l 的一种自然扩充。x o l 在x s l 的基础上提供了筛选操作和布尔操作，并能对节点集进行索引。 x q l 的基本语法模仿了u r i 目录导航语法，通过c o n t e x t ，x q l 可以导 航到具体的节点。x q l 的设计目标简单、紧凑，可作为u r i 的一部分， 但因此也降低了部分表达能力。 x m l q l 是贝尔实验室专为查询x m l 文档而设计的，是一门s q l 式的查 询语言。支持多文档的连接和合并，并能将查询结果构造成新的x m l 文档。其基本结构是w h e r e c o n s t r u c t ，通过w h e r e 子旬指定查询的节 点，通过c o n s t r u c t 子句指定查询结果的形式。x m l q l 通过元素模式 匹配进行查询处理，能对多数据源的x m l 查询和转换。同时它还借鉴 了一些语言例如o q l 和l o r e l 。 x m l - g l 是一门图像化的) ( m l 查询语言。 q u i l t 最大的特点就是博采众长。它从x p a t h 和x q l 中汲取了非常适合 于查询层次结构文档的路径表示法；继承了x m l q l 中的变量绑定的概 念，并使用它来创建新的文档结构；吸取了s o l 的易于接受的文法结 x q u e r y 查询语句的解析、分析和查询优化 构( 即s e l e c t f r o m w h e r e 结构) ，使用f l w r 文法结构来表达查询； 在元素构造方面又采用了标准的x m l 语法。q u i l t 不仅可以灵活地查询 x m l 数据，还能查询关系数据，在x q u e r y 推出来之前，它的表达能力 是最强的。它也是x q u e r y 的前身。 x p a t h 由w 3 c 组织设计，是一种微型x m l 查询语言。x p a t h 将x m l 文档 看作是树，将元素、属性、注释和文本看作是树的节点。x p a t h 数据模 型提供一些操作，它能够导航文档的树结构并能访问树的各个组成成 分。这些操作包括访问根节点、访问节点的父节点、访问节点的子节 点、访问节点的内容、访问属性的值、选择x m l 文档中的特定的节点 和跳过不定数量的子节点等等。x p a t h 查询语句允许将一定的条件放在 表达式的任何节点后面，用以过滤不符合条件的节点。 上述语言在语法形式和查询能力上各不相同，且多半具有极强的针对性， 往往对某种数据类型的查询十分有效，但对另种数据类型的查询却无能为 力。比如x s l 和x q l ，就不支持连接操作和正规路径表达式匹配。而x m l q l 和 x m l g l 则不支持全局变量。 正是在这种情势下，w 3c 公布了一种有别于其他查询语言的全新的x m l 查询语言一x q u e r y 。这种全新的查询语言适用于各种类型的x m l 数据源的查询 是一种功能极强的查询工具。特别需要提及的是，在该方案中x q u e r y 被设计成 一种精干灵活且易实现的查询语言，用其形成的查询式简洁易懂。它不但继承 了q u i l t 的全部优点：如变量绑定、路径表示法、x m l 构造和易于理解的f l w r 表达式，还增加了自定义函数，形式语义、名字空间和对s c h e m a 的支持。正因 为这样，x o u e r y 已经成为事实上的x m l 查询语言标准。 2 2 x q u e r y 语言简介 x q u e r y 语言目前的最高版本是2 0 0 3 年1 2 月1 5 日版，由于本系统开发时 的最高版本是2 0 0 3 年5 月2 日版，所以下面就以该版本为例介绍x q u e r y 语言。 x q u e r y 标准的完整内容包括六个部分：1 x m lq u e r yr e q u i r e m e n t s x q r e 0 3 】 ( x q u e r y 语言需求定义) ，该文档定义了x q u e r y 语言设计的动机和应该具有的 能力，以及x q u e r y 语言要解决的问题和需求列表：2 x m lq u e r yu s ec a s e s u s e c 0 3 】( x m l 查询实例) ，该文档列举了各种x q u e r y 的实例程序；3 x q u e r y 1 0 和x p a t h2 0d a t am o d e l d a m d 0 3 】( x q u e r y 和x p a t h 的数据模型) ，该文 档定义了这两种语言的数据模型；4 x q u e r y1 0 f o r m a ls e m a n t i c s s e m a 0 3 ( x q u e r y 语言的正则语义) ，该文档对x q u e r y 的语义作了详细的说明，如：动 态语义、静态语义、选择和投影的语义，从形式上定义了语言的语义代数，是 x q u e r 矗询语言 ) ( q u e r y 的核心文档；5 x q u e r y 1 o ：a nx m lo u e r yl a n g u a g e x q u e r y 】，这是 x q u e r y 语言的总体介绍，对该语言的主要特征进行描述；6 x q u e r y 1 0a n d x p a t h2 0f u n c t i o na n do p e r a t o r sv e r s i o n1 0 f u n c 0 3 】( x q u e r y 和x p a t h 支持的函数和操作符的定义) ，该文档说明了x o u e r y 语言支持的函数、操作和 类型转换规则。下面从语法的角度，介绍一下x q u e r y 语言。 2 2 1 表达式环境 表达式环境指的是一切能影响表达式的最后结果的元素。表达式环境可以 分成两类：静态环境和动态环境。 静态环境：指所有在静态分析阶段影响表达式的值的元素，如：允许的名 字空间，支持的类型、元素、函数的名字空间，支持的x m l 结构，内部定义的 变量和函数等。 动态环境：指所有在动态分析阶段影响表达式的值的元素，不仅包括所有 的静态环境元素，还包括：项目指针( c o n t e x ti t e m ) ，位置指针( c o n t e x t p o s i t i o n ) ，大小变量( c o n t e x ts i z e ) ，文档指针( c o n t e x td o c u m e n t ) 、动态 变量、当前日期和时间以及输入系列。项目指针指向当前正在处理的节点或原 子值，类似于数据库中的当前指针概念，因为当前节点可能是一个序列，项目 指针指向序列中当前正在处理的那个项目；同理，位置指针就指出当前处理的 项目在系列中的位置：大小变量则指出该系列中的项目的个数；文档指针指向 当前处理的文档。 2 2 3 输入函数 x o u e r y 提供三种输入函数，接受外界的数据输入，这三种函数分别是： i n p u t0 ，将用户输入的序列读入查询程序，若输入序列为空，该函数会引发一 个动态错误；c o l l e c t i o n s 0 返回输入集合中能找到的所有的节点，集合可以是 本地的，也可以来自网络。每一个集合都有自己的名字。这个名字就是函数的 参数：d o c u m e n t 0 ，参数为 ( m l 文档名( 注意：若文档不在当前目录中，文档 名之前应该指定文档所在的路径) ，根据指定的文档构造一个d o c u m e n t 节点。 一般来说，d o c u m e n t 节点是一棵查询树的根结点。假如该文档包含了其他的x m l s c h e m a 定义，那么该定义也为x q u e r y 认可。 x q u e r y 查咖语句的解析、分析和查询优化 2 2 4 类型 x q u e r y 是一门对类型有严格要求的语言，其类型主要基于x m ls c h e m a 定 义的类型系统。包括内置类型和导入类型。其中内置类型包括内置原子类型和 内置导出类型，而导入类型指那些在) 【m ls c h e m a 中定义的类型，通过i m p o r t s c h e m a 语句导入到x q u e r y 程序中，x o u e r y 能支持这些类型。 一般来说，表达式处理的对象都是系列元素的有序集合( 称为序列) ，面 不是单个的元素。序列是x q u e r y 自己定义的类型。序列中的元素可能的类型是： ”n o d e ”、”p r o c e s s i n g i n s t r u c t i o n ”、”c o m m e n t ”、”t e x t ”、”d o c u m e n t ”、”i t e m ”、 ”u n k n o w n ”、”a t o m i cv a l u e ”，当然也可以是从s c h e m a 中导入的类型。序列中 每一种类型的元素出现的次数可以任意，用出现标记来表示，分别为：“? ”， 表示出现o 次或1 次；“”，表示出现0 次或多次；“十”，表示出现1 次或多次。 处理表达式时，要对每一个语言因素进行类型检验，这又分成静态分析和 动态分析两种。在静态分析阶段，分析器浏览整个表达式，标明各个元素的所 有可能类型；在动态分析阶段，分析器真正根据读进来的值确定各元素的类型， 这时定出的类型是某个确定值，假如某个运算中的两个数的类型不符合要求， 那么要进行类型的转