（计算机应用技术专业论文）基于索引的xquery实现的优化.pdf

摘要 摘要 随着x m l 日益普遍的应用，如何快速准确地访问x m l 文档中的数据已成 为急需解决的关键问题，这涉及到对x m l 查询语言x q u e r y 实现的优化研究。 目前可以通过多种途径对x q u e r y 进行优化，如：执行策略、物理优化、代数优 化等。执行策略主要是根据路径条件选择遍历节点的方式，如自底向上或自顶 向下的遍历策略，以减小遍历节点的代价。物理优化主要是采用高速缓存来缓 冲c p u 运算与内存访问之间的差距，从而达到整体速度的提高。代数优化主要 是基于x m l 的数据模型和传统的逻辑操作对路径表达式进行优化，从而达到优 化x q u e r y 的目的。 当前已存在多种基于索引的x q u e r y 实现优化的方法，如l o r e 系统中的 d a t a g u i d e 、x i s s 、d b x i 等。d a t a g u i d e 对x q u e r y 中经常出现的“”操作没有 提供特殊的支持，并且只记录了从文档根节点出发的路径，从而丧失了许多优 化的可能性。在x i s s 系统中，对于复杂的路径表达式在) 【m l 数据树中要搜索很 多空间，处理每个x m l 文档所需的结构连接运算的次数至少有n 一1 次，加大了 查询的复杂度，从而影响查询效率。d b x i 是一种基于d t d 的x m l 索引方法，当 d t d 中存在环路时搜索空间会很大。 本文首先分析这些优化方法，指出他们的优缺点，并在此基础上引入一种 基于r 树的索引机制，解决了快速判断x m l 文档中节点间祖先、子孙关系的问 题。将x m l 文档以r 树的形式进行存储，对树中的节点建立索引。在查询时将 节点关系的判断转化为节点域的包含关系的判断，同时利用r 树范围查询快速、 高效的特征提高查询效率。另外还引入了索引关键字的分割表和最小分割表跳 过与查询不相关的节点，减少了磁盘i ，0 次数，进一步提高查询效率。 在本文的最后，我们还给出使用基于r 树索引对x q u e r y 的实现进行优化 的实例，并针对存在的一些问题，提出今后进一步的工作。 关键词：x m l ，x q u e r y ，优化，索引，查询 基于索引的x q u e r y 实现的优化 a b s t r a c t w i t hw i d e s p r e a da p p l i c a t i o no fx m lf o re x c h a n g i n ga n de x p r e s s i n gd a t ao nt h e w e b ，e f f i c i e n ta c c e s st ox m ld a t ah a sb e c o m eak e yp r o b l e mn e e dt ob e s o l v e d ，w h i c ht o u c ho nt h er e s e a r c ho nt h eo p t i m i z a t i o no fx q u e r y , ax m lq u e r y l a n g u a g e t h e r ea r em a n yw a y st oo p t i m i z ex q u e r y ：b yu n d e r t a k i n gs t r a t e g y ，p h y s i c a l o p t i m i z i n g ，a l g e b r ao p t m a i z i n ga n d8 0o n u n d e r t a k i n gs t r a t e g y ：b ym e a n $ o fs e l e c t i n g t r a v e l i n gn o d em e t h o d ，e x p ，b o t t o m - u po rt o p - d o w n , o nt h eb a s i so fp a t hc o n d i t i o n p h y s i c a lo p t i m i z a t i o n ：r a i s i n gi n t e g r a t er a t eb ye m p l o y i n gf a s t - c a c h et oc a s h i o nt h e d i f f e r e n c eb e t w e e nc p uo p e r a t i n ga n dm e m o r yv i s i t i n g a l g e b r ao p t i m i z a t i o n ： o p t i m i z i n gp a t he x p r e s s i o no nt h eb a s i so fx m l d a t am o d e la n dt r a d i t i o n a ll o 百c o p e r a t o r ，t oa c h i e v et h ep u r p o s eo f o p t i m i z i n gx q u e r y c u r r e n t l yt h e r ea r em a n yw a y st oo p t i m i z ex q u e r yp r o c e s s i n go nt h eb a s i so f i n d e x ，e x p ，d a t a g u i d ei nl o r es y s t e m ，x i s s ，d b x i i nd a t a g u i d e ，s p e c i a ls u p p o r to n o p e r a t o r , w h i c ht u r nu pi nx q u e r y , w a sn e v e ro f f e r e d a n dp a t h , w h i c hd e p a r tf r o m r o o tn o d e ，w a sr e c o r do n l y s oi td e p r i v a t em a n yp r o b a b i l i t i e so fo p t i m i z a t i o n i nx i s s s y s t e m , m o r es p a c e s m u s tb es e a r c h e di nx m ld a t a t r e e ，i n v o l v e dp a t h e x p r e s s i o n t h ef r e q u e n c y o f d e a l i n g w i n lf a b r i cc o n n e c t i o n o p e r a t i n g i n x m l - s t r u c t u r e dd a t a 啦l e a s eh a sn 一1 s oi ta g g r a n d i z e dt h eq u e r y i n gc o m p l i c a t i o n a n de f f e c tq u e r y i n ge f f i c i e n c y d b x ii sax m li n d e xm e t h o do nt h eb a s i so f d t d s e a r c h i n gs p a c e sm a yb ev e r y l a r g ew h i l ec i r c l e sa r ee x i s t e di nd t d t h i s p a p e r f i r s ta n a l y z et h e s e o p t i m i z a t i o nm e t h o d s ，a n dp o i n to u t t h e i r a d v a n t a g e sa n df a u l t s w ee x p o u n dai n d e xm e c h a n i s mb a s e do nr t r e e t h ep r o b l e m o f f a s t - s p e 烈lj u d e 妞ga n c e s t o r , d e s c e n d a n tr e l a t i o n s h i p b e t w e l 奠ln o d e si n x m l - s m m u r e dd a t ai sr e s o l v e d w es t o r ex m l - s t r u e t u r e dd a t ab yr 慨a n di n d e x t h en o d e si nt h et r e e ，a n dc o n v e r s et h ej u d g e m e n to fr e l a t i o n s h i pb e t w e e nn o d e st o c o n t a i n i i l gr e l a t i o n s h i pw h i l eq u e r y i n g a tt h e $ a m et i m e ，q u e r y i n ge f f h c i e n c yw a s i n c r e a s e db yu s eo ff a s t s p e e d ，h i g h - e f f i c i e n tf e a t u r eo frt r e er a n g eq u e r y i n g i n a d d i t i o n , p a r t i t i o n - t a b l ea n dl e a s tp a r t i t i o n t a b l eo fi n d e xk e y w o r dw a sl e a dt os k i p n o d e sn e 、，e ri n t e r a c t i n gw i t hq u e r y i n g t h i si n d e xm e c h a m s md e c r e a s et h ef r e q u e n c y o f d i s ki o ，a n de n h a n c eq u e r y i n ge f f i c i e n c y a tt h ee n do ft h i sp a p e r , w ew i l lg i v es o m ee x a m p l e so fo p t i m i z i n gx q u e r yb y u s eo fi n d e xb a s e do nrt r e e a n da c c o r d i n gt os o m ee x i s t i n gp r o b l e m sf u r t h e rw o r k s a n dd e v e l o p m e n t sw i l la l s ob eg i v e n k e yw o r d s ：x q u e r y , x m l ，o p t i m i z a t i o n , i n d e x ，q u e r y h i 目录 图表清单 图2 1x q u e r y 处理器的构造1 2 图4 一l 索引结构3 8 图5 1 一个x l f l 元素文档树5 3 图5 2 分配节点域后的脚l 文档树5 4 图5 3 在x i d l 元素文档树上建立的基于r 树的索引5 5 表5 1 索引关键字及其最小分割表。 表5 3v s l j 的范围 5 4 5 5 夏j 电叁b 拄譬；：旧 、k o 。如_j 二蔓厂：0 本人声明所呈交的学位论文是奉人在导师指导下进行的研究工作及取得的 研究成果。捂我所知，除了文中特别加以标注和致讶的地方井，论文中不包含其 他人已经发表或撰写过的研究成果，遣l 不包含为获得安徽炙荨或其德教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了铜确的说臻并表示谢意， 学位论文作者签名：磊蒲霞签字日期：2 # 。占年箩月9 日 学位论文版权使用授权书 本学位论文作者完全了怨安徽天擘有美保留、使用学位论文的规定， 有权保留并岛雷家有关部门或机均送交论文婚复印俘每磁盘，免许沦文被奎阕和 借阕。本人授权i 狼火拳可以将学位论文的垒芬或部分内窑绕入有关数撂牵进行 检索，可以采用影印、缩印或扫描等复制手段黎存、汇缀掌垃论天。 ( 保密约学位谗宠在解密彦适周本授衩蕊) 第1 章引言 1 1x m l 简介 第1 章引言 x m l t l 】全名为e x t e n s i a b l em a r k u pl a n g u a g e ，即“可扩展标记语言”。它是 继h t m l f 2 】后新兴的互联网信息交换标准。与h t m l 一样，x m l 也是源于 s g m l 例( s t a n d a r dg e n e r a l i z em a r k u pl a n g u a g e ) 的一种标记语言。它保留了 s g m l8 0 的功能，却使复杂程度降低了2 0 。x m l 具有巨大的伸缩性和灵活 性，使得使用者可以定义各种标记来描述文件中任何元素数据，从而突破了 h t m l 固定标记集合的约束，使文件的内容更加丰富、更加复杂并且形成了一 个完整的信息体系。 v i i ，是由w 3 c 的x m l 工作组制定的一组规范，以便于软件开发人员和 内容创作人员在网页上组织信息，其目的不仅在于满足不断增长的网络应用需 要，同时还能确保在通过网络进行交互合作时，具有良好的可靠性和互操作性。 由于x m l 能针对特定的应用领域而定义特定的标记集合，所以x m l 可以在电 子商务、政府文档、报表、出版和中介信息交互等领域，根据不同的系统和应 用提出各具特色的独立解决方案。x m l 给网络上的各种应用带来了第二次的革命 性变化，在各个应用领域创造出了无穷的应用机遇。 1 2x m l 的查询语言x q u e r y 随着用x m l 存储、交换和表述信息的应用日益增多，人们对其研究也越来 越深入，如何从x m l 数据源中准确有效地查询所需的信息，也就变得越来越重要。 目前已有的查询语言多半具有极强的针对性，往往对某种数据类型的查询十分有 效，但对另一种数据类型的查询却无能为力。在这种情势下，在1 9 9 8 年由w 3 c 成立的查询语言工作组( q u e r yl a n g u a g ew o r k i n gg r o u p ) 提出了x m l 查询语言 x q u e r y 的一系列规范。虽然x i 如e 习规范的设计早在1 9 9 8 年就己启动，但由 于x m l 应用领域的差异，规范制订的过程相当漫长。直到2 0 0 1 年2 月，规范 的发布工作才开始较快地进行，大量的规范文档开始推出，并先后于2 0 0 1 年6 基于索引的x q u c r y 实现的优化 月和1 2 月、2 0 0 2 年8 月和1 1 月、2 0 0 3 年5 月和1 1 月、2 0 0 4 年7 月、2 0 0 5 年 2 月和4 月和2 0 0 6 年1 月陆续进行更新。x q u e r y 是一个从x m l 格式的文档中 获取数据的查询语言。它起源于x m l 数据鱼询语言q u i l t l 6 , 并将x p a t h l 7 1 版本2 0 作为其子集。这种全新的查询语言适用于各种类型的x m l 数据源的查询，是一种 功能极强的查询工具。特别需要提及的是，在该方案中x q u e r y 被设计成一种精干 灵活且易于操作的查询语言，用其形成的查询表达式简洁易懂。 1 3 研究背景与动机 本文以安徽省教育厅自然科学研究项目一( x q u e r y 引擎及基于x q u e r y 的 信息集成软件开发工具包研究为背景，引入基于r 树的索引机制，对x q u e r y 实现的优化进行研究。 目前对x m l 查询处理的研究主要有两种思路：一是将x m l 看作数据库， 这方面研究多的是基于关系数据库的查询处理；二是将x m l 看作文档，这方面 的研究热点是基于内存的查询处理和优化。 ( 1 ) 基于关系数据库的查询 x m l 查询处理建立在关系数据库系统之上的优点是可以直接利用关系数 据库成熟的优化和索引技术，同时不用为并发控制、安全性等问题作额外的工 作。但是由于关系数据库的数据需要以x m l 的格式对外发布，在实现上有些复 杂，需要做以下四步额外的工作： 0 x m l 文档类型定义( d r d ) 生成关系数据库的表定义； 将x m l 数据转存到关系数据库中的表中； 将x m l 查询转换为s q l 查询； 将关系数据库查询结果构造成x m l 文档。 ( 2 ) 基于主存的x m l 文档的查询处理 与基于关系数据库的x m l 查询处理不同的是，x m l 文档的查询处理必须 实现逻辑优化、物理优化、索引优化和查询执行的各个环节。在这几个环节中， 最难的还是x m l 文档索引的设计。因为x m l 的数据模型比较复杂，采用任何 一种单一的索引结构都不能很好的解决问题，通常需要多种索引机制的联合使 2 第1 蕈引言 用才可以收到良好的效果。 在对x q u e r y 的深化研究中，如何提高对数据的查询速度变得越来越重要。 x q u e r y 的优化包括很多方面：执行策略、物理优化、代数优化。但在其中，通 过建立索引对其进行优化是最有效也是最重要的一种方法。目前已存在多种索 引机制的系统，如：d a t a g u i d e 引、x i s s t g l 、d b x i 1 0 1 等。d a t a g u i d e 对x q u e r y 中 经常出现的“，”操作没有提供特殊的支持，并且只记录了从文档根节点出发的 路径，从而丧失了许多优化的可能性。在x i s s 系统中，对于复杂的路径表达式 在x m l 数据树中要搜索很多空间，处理每个x l l 文档所需的结构连接运算的次 数至少有n 一1 次，加大了查询的复杂度。d b x i 是一种基于i y f d 的x m l 索引方法， 当d t d 中存在环路时搜索空间会很大。对于这些存在的问题，我们有必要对 x q u e r y 的优化进行进一步深化的研究。 1 4 国内外研究现状 x q u e r y 的强大功能既满足了以文档为中心的x m l 应用，又满足了以数据 为中心的x m l 应用。x q u e r y 作为一种全新的数据查询语言，已经被众多的科 研机构与企业所接受和采纳。目前微软、i b m 和o r a c l e 公司数据库核心都采用 x q u e r y 的标准。随着x m l 日益普遍的应用，如何快速准确地访问x m l 文档值 的数据已成为急待解决的关键问题，也就是对x q u e r y 的实现进行优化。x q u e r y 的优化包括很多方面，最主要的是基于索引的优化。业界也有很多关于x q u e r y 处理引擎的优化的研究。 l o r e 1 l 】是斯坦福大学开发的x m l 文档数据库管理系统它的数据模型是 o e m ( o b j e e te x c h a n g em o d e l ) ，它支持多索引技术和相似查找技术。l o r e 系统针 对自身的o e m ( o b j e c te x a n g em o d e l ) 结构和d a t a g u i d e 结构建立了4 种不同的 索引，以加快对的查询速度。d a t a g u i d e 是源文档结构的一种概括，本身也是一 个文档，可看成一颗树，其中包含了源文档中所有可能存在的路径，并且源文 档中相同的路径在d a t a g u i d e 中只出现一次。d a t a g u i d e 在处理常规路径查询时可 以收到良好的效果。但d a t a g u i d e 对x q u e r y 中经常出现的“，”没有提供特殊 的支持，而且只记录了从文档根节点出发的路径，从而丧失了许多优化的可能 基于索引的x q u c r y 实现的优化 性。特别的，当路径索引带有谓词表达式的时候，路径索引操作就由此截断， 不能再继续做下去。 x r s 【l2 】是基于b u s ( b o t t o mu ps c h e m e ) 技术的用j a v a 实现的一个搜索引擎。 它采用的基本思想是：在最低结构层次上建立索引，在进行查询的时候在较高 结构层次上计算词的权重信息。在已知文档的结构定义的情况下能够很好地在 数据记录一级进行文档的查询。i n f o g l i d e 的核心技术是“相似性搜索( s e e ) ”。 它能够在数据和查询都有误差的情况下，按照记录相似的百分比返回记录，并 且它还能够跨多个数据库进行数据的相似性查找。x d e x 可以对h r r p 数据源， f r p 数据源和本地文件数据源建立索引，还提供了让用户输入要查找的关键词和 关键词的上下文标签的查询界面。 d b x i 采用了新的编码方法，对x m l 文档及其遵循的d t d 同时建立索弓i 。它 能够精确定位x m l 文档中参与结构连接的节点集；对一个由n 个元素属性组成 的具有1 个谓词约束的路径表达式，d b x i 将处理每个x i d l 文档所需的结构连接 运算的次数降低至0 或1 次；对于在待查x m l 文档中不存在匹配结构的路径查 询，d b x i 能够在较短的时间内给出无查询结果的判断。但是当d t d 中存在环路 时，搜索空间会很大。同时，d b x i 现阶段只处理单d t d 、多x m l 文档的情况。 x i s s 系统能够存储和索引) ( m l 数据，并能有效地处理有规则路径表达式的 查询，在这样的系统中使用基于扩展的预编号机制在固定的时间内就可以确定 x m l 数据层次结构中结点的祖先，子孙关系通过分配一个具有额外空间的预 编号区，编号机制能很好地适应x m l 数据的动态变化但在x i s s 系统中，对于复 杂的路径表达式，在x m l 数据树中要搜索很多空间，加大了查询的复杂度，从而 影响查询效率。 1 5 研究重点和主要内容 x q u e r y 虽然作为一种语言规范被提出，但是其涉及的内容相当广泛。首先， 作为一种描述型的语言和函数型语言，它在编译阶段就具有过程型语言的不同 特点和要求；其次，作为一个对数据进行查询的语言，它需要有严格的数据模 型支持。x q u e r y 是建立对建立在x q u e r y 数据模型上的对) m 几进行查询的语言 4 第1 章引言 目前对该语言的编译实现，可以较好地对x m l 文档中的数据进行查询，但是从 实践的角度出发如何对x q u e r y 进行优化是很具有研究价值的一个问题。 x q u e r y 的优化包含多个方面，最重要的是基于索引的优化。现有的方法有 基于t i l e 树的索引i n d e xf a b r i c l l “、s t a n f o r d 大学的l o r e 系统中的d a t a g u i d e s 、 x i s s 系统索引方案、基于共享根节点的后缀树的索引r i s t l 0 7 1 和基于d o m 模型 的索引【1 8 等。本文研究的重点是对当前已存在的几种索引机制进行对比和分析， 提出他们的优点和缺点，并在此基础上建立一种基于r 树的x m l 数据的索引机 制。在查询时将节点关系的判断转化为节点域的包含关系的判断，解决了快速 判断x m l 文档中节点间祖先、予孙关系的问题。同时利用r 树范围查询快速， 高效的特征提高查询效率。另外还引入了索引关键字的分割表和最小分割表跳 过与查询不相关的节点，减少了磁盘的次数，进一步提高查询效率。 1 6 论文的成果和组织 本文通过对x 1 2 u ，实现进行优化的研究，主要在以下几个方面取得了一定 的研究成果： 1 对x q u e r y 语言进行综述，介绍x q u e r y 优化的几种大致的方法和途径。 2 分析了目前相关的几种基于索引的x q u 屺r y 实现优化的方法，并指出其 优缺点。 3 引入一种基于r 树的索引机制，实现对x q u e r y 的优化，从而提高对x m l 文档进行查询的效率。 4 对x q u e r y 优化中的结构连接算法进行优化。 5 举例说明设计和实现基于r 树的索引的过程，达到对x q u e r y 进行优化 的目的。 本文的组织安排如下： 第一章：引言 简单介绍x m l 技术及其查询语言x q u e r y ，提出对x q u e r y 进行优化的几 个方面。并且介绍本文的研究重点和主要内容，最后介绍了本文的研究成果和 组织。 5 基于索引的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 优化的几个方面的研究成果。 第三章：x q u e r y 优化的研究 首先介绍搜索引擎的结构和对它的改进，然后分析目前相关的基于索引的 x q u e r y 优化的方法，指出它们的优缺点。 第四章：基于索引的x q u e r y 实现的优化 介绍路径索引的概念和建立步骤，提出一种基于r 树的索引机制，实现对 x q u e r y 的优化。并对x q u e r y 优化中的结构连接进行优化。 第五章：过程分析 用实例说明基于r 树建立索引的过程，并对其进行分析。 第六章：结论和进一步的工作 总结全文，并针对现存在的问题提出进一步的工作。 6 第2 章x q u e r y 语言综述 第2 章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 1 x o u e r y 语言简介 2 1 1 一个x q u e r y 查询的例子 假设有如下的x m l 数据，这是关于员工的资料描述，并且该数据保存在文 件e m p l r a r d 中： 7 基于索引的x q u e r y 实现的优化 代码2 1e m p l x m l 文档内容 该x m l 定义了一个e m p l 元素，并且该元素有2 个e m p l o y e e 子元素。每个 e m p l o y e e 元素描述了一个员工的信息：该员工的名字( n a m e 子元素) 、年龄( a g e 子元素) 、性另r ( s e x 予元素) 、地址( a d d r e s s 子元素) 、电子邮件( e m a i l 子元素) 和电 话( t e l 子元素) 。 一个关于该x m l 的x q u e r y 查询如下： 代码2 2 一个x q u e r y 查询 该查询返回性别为男性并且年龄小于3 5 的员工的姓名。 此例的查询结果输出为： 代码2 3 查询结果 2 1 2x o u e r y 中的基本操作 1 f l w r 表达式 一般的x q u e r y 查询通常不仅要包括模式匹配，而且应该支持选择过滤 和结果构造。在x q u e r y 中f l w r 表达式是典型的能够完成具有某种实衔；意义的 8 第2 章x q u e r y 语言综述 查询的表达式f l w r 表达式是由f o r l e t w h e i 砸一i 也t u r n 四个关键字 定义的子旬构成的表达式，特别适用于对数据进行连接查询，以及重新构造结 果的x m l 数据结构。f l w r 发音为“f l o w e r ”是四个子句的缩写。它的形式定 义为： f l w r e x p r ：2 ( f o r c l a u s e l e t c l a u s e ) + w h e r e c l a u s e ? ”r e t u r n ”e x p r f o r c l a u s e ：2 ”f o r ”v a r i a b l e ”i n ”e x p r ( ”，”v a r i a b l e ”i n ”e x p r ) + l e t c l a u s e ：5 ”l e t ”v a r i a b l e ”：2 ”e x p r ( ”，”v a r i a b l e ”：2 ”e x p r ) + w h e r e c l a u s e ：= ”w h e r e 。e x p r r e t u e n c l a u s e ：2 * r e t l l l l l e x p r f o r 予句用于将表达式的值依次绑定到变量，例如f o rs xi ne x p r 将表达 式e x p r 的值依次绑定到变量$ x 。 l e t 子句用于将表达式的值整个绑定到变量，例如l e t $ x = e x p r 将表达式 e x p r 的值一次性绑定到变量$ x 。 w h e r e 子句用于过滤f o r 和l e t 语句绑定的变量，w h e r e 子句的返回 值是布尔类型的，只有满足w h e r e 条件的变量才能在后面的r e t u r n 语句中 返回结果。 r e t u r n 予句用于返回结果，结果的x m l 数据结构也在r e t u r n 语句中 定义，对于满足w h e r e 子旬条件的每个f o r 和l e t 语句传来的变量，r e t u r n 语句按照其定义的结构返回结果。 每个f l w r 表达式都有一个或多个f o r 子句、一个或多个l e t 子旬、一 个可选的w h e r e 子句以及一个r e t u r n 子句。 2 x q u e r y 基本操作的实现方式 ( 1 ) 模式匹配 给出一个x m l 文档，一个路径表达式，模式匹配操作使用路径表达式，在 x v l l 文档中选取出满足条件的路径集合。模式匹配操作主要为从) 叫l 文档中 选出符合某一模式的节点而工作。直接的进行模式匹配操作的算法如下： 9 代码2 4 模式匹配算法 ( 2 ) 选择 选择操作在模式匹配的基础上，从满足条件的路径集中选出符合条件的路 径。选择操作又可称为选择过滤。在x m l 文档中，选择操作除了要选出满足条 件的路径之外，还要保持x m l 文档的结构，即使用选出来的路径可以继续访问 这些路径上的节点以及节点的子孙。进行选择操作的算法简单描述为： 代码2 5 选择算法 ( 3 ) 结果构造 在沮，查询中，需要变化数据的格式，构造查询结果。构造出来的查询结 果仍应符合x m l 的格式所以x q u e r y 中，也要有构造结果) m 几的能力。在 x q u e r y 使用x m l 的语法格式来构造结果，而对查询中可变的部分用大括号( ) 1 0 第2 章x q u e r y 语言综述 代码2 6 结果构造算法 2 2 x q u e r y 的编译实现 从开发人员的角度看，一个x q u e r y 处理器的实际输入由4 个部分组成： 待查询的x m l 文档；通常这个x m l 从物理存贮的文档或者由其他程序 生成的x m l 数据流组成。 待查询x m l 文档的格式说明；这个输入同样也是有两种方式：物理存 贮的和其他应用生成的数据流。格式说明有两种方式：d o c u m e n tt y p e d e f i n e ( d t d t l 9 1 ) 和x m ls c h e m a l 2 0 1 。 用户输入的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 数据库代数语言【2 1 1 ( a l g e b r a i cl a n g u a g ef o r x m l d a t a b a s e ) 、q u l x o t c 圈的查询处理方式、b e l l 实验室的g a l a x t z 3 l 模型等查询 基于索引的x q u c r y 实现的优化 语言实现机制的分析，提出了如下的x q u e r y 编译器的设计方案f 2 4 】： 图2 1x q u e r y 处理器的构造 在图2 一i 中，我们可以看出这个x q u e r y 语言器处理大致有5 个部分组成： 1 x q u e r y 数据模型构造器：该部分完成将待查询的x m l 文档和文档格式 说明转换为查询处理器可识别的格式。这个可识别的格式称为该文档的数据模 型。数据模型的构造分为两个部分：x m l 信息集的构造和x q u e r y 数据模型。 2 x q u e r y 语法分析器：这部分负责将x q u e r y 查询代码转换为语法树。语 法树的形成分为两个阶段：第1 阶段形成的是x q u e r y 的语法解析语法树；第2 阶段形成一个规范化的语法树。， 3 类型处理部分：这部分主要包括x q u e r y 的类型说明处理器、静态类型 检查和查询结果类型分析模块。它的主要任务是负责将x q u e r y 源程序的类型说 明转换为类型环境供类型分析模块进行查询的类型检查和分析。该部分的另外 一个重要的功能是将c o r e 语法树进行剪枝操作，删除那些计算时根本不可能经 过的语法树分支，从而形成一个经过剪枝简化后的c o r e 语法树。 第2 章x q u c r y 语言综述 4 运行环境部分：x q u e r y 的运行环境包括静态环境和动态环境。 静态类型环境主要负责处理类型信息和运行时保持不变的映射表等。它包 括下面6 个部分： 元素声明环境：它负责处理元素声明的名称到元素类型体的映射关系， 并由此可以提供元素类型供x q u e r y 引用。 属性声明环境：它负责处理属性声明的名称到属性类型体的映射关系， 并由此可提供属性类型供x q u e r y 引用。 类型声明环境：它管理类型的名称到类型体的映射关系。注意它与1 ，2 的区别在于它定义的是类型而不是具体的元素或者属性。这从后面的例子中可 以看出。 内建函数签名：负责x q u e r y 内建函数的函数签名的管理。这里的函数 签名包括下面的信息：函数名、函数参数个数、参数列表、返回类型以及函数 对应的类和操作。这部分信息供类型分析和赋值计算时查找以检查函数的参数 是否匹配和从哪里加载该函数的实现。 命名空间环境；负责处理命名空间名称与实际地址的映射关系。因为 x m l 的名称是建立在q n a m e ( ：= n s + l o c a l n a m e ) 的基础上的，而如果两个名称 即使命名空间名不同但他们却指向同一个地址，那么仍然认为他们是相同的。 变量类型环境：负责管理变量的名称与该量类型的映射关系。这在类型 检查和分析时被使用到。 动态运行环境除了包含静态环境的所有组件外，添加了两个模块： 自定义函数环境：它负责维护自定义函数的信息。这些信息包括用户定 义的函数名、函数参数个数、参数类型、返回类型和自定义的函数体等信息。 变量值环境：负责维护执行时变量的名称到值的映射关系。 从本质上说，运行环境是由一个个的系统表组成的。 5 查询执行部分：这是x q u e r y 查询被真正计算出结果的模块。它的输入 有两个部分组成：一个是由语法转换器直接输出的c o r e 语法树；另一个是由静 态类型检查和查询结果分析器输出的经过剪枝操作后的c o r e 语法树。直观的说， 经过剪枝后的语法树在规模上比未经剪枝的语法树要小很多。 图中边界是虚线的处理模块和输入输出，他们表示可选的信息。而且图中 基于索引的x q u c r y 实现的优化 的静态类型检查和查询结果类型推断也是可选的。 在以上部分对x q u s t y 的编译实现中并没有涉及到关于x m l 查询优化的问 题，因此本文在此基础上对x q u e r y 实现的优化进行研究。 2 3x o u e r y 优化的大致方法 2 3 1 执行策略 查询可以有多种执行策略。最简单的方法是根据路径条件深度优先遍历所 有节点，检查它是否满足谓词条件。这种执行策略是沿着路径表达式自顶向下 的查询方法，称为自顶向下( t o p _ d o w n ) 策略另一种方法正好相反，从谓词条件 开始，沿着路径表达式反向进行查询，称为自底向上( b o t t o m _ u p ) 策略。第三种方 法是先自顶向下的方法寻找符合路径条件的对象，再用自底向上的方法寻找符 合谓词条件的原子对象，最后对两者进行结合，称之为混合( h y b r i d ) 策略。 采用何种策略最优取决于下列几个因素： ( 1 ) 和查询有关，如果查询语句中不含谓词条件只能采用自顶向下的策略。 ( 2 ) 和索引有关，如果未定义子元素的值索引只能采用自顶向下的策略。 ( 3 ) 和x m l 的数据特点有关。 需要说明的是采用自底向上和混合策略条件是要有相应的索引存在。三种 策略各有千秋，很多情况下，采用自底向上和混合策略条件比较好，但两种策 略都会破坏x i l 数据间的顺序，则输出前需重新排序，而自顶向下策略可以采用 路径索引来加速查询。 2 3 2 物理优化 查询处理在内存中进行，有两个因素制约查询的优化：一个是c p o 运算和内 存访问是紧密相关的，但是它们的速度差距很大，如可采用高速缓存来缓冲c p u 和内存间的差距，从而达到整体速度的提高；另一个是和查询优化一样，数据 访问也在内存中进行，则需要考虑优化本身对查询的影响。在查询处理时需要 采用一些方法来估计物理操作上的代价，并在这个基础上得出物理代价，最后 1 4 第2 章x q u e r y 语言综述 从不同计划中选择代价最小的一个作为真正执行的计划。 基于内存的查询处理和优化在物理实现上必须仔细考虑数据的物理组织方 式，这是因为c p u 速度和内存访问速度之间的差距越来越大，现代计算机通常 都提供了一级或二级的高速缓存，以缓和c p u 与主存之间的失配。但由于缓存 通常都比较小，因此必须采用各种方法以降低运行时的缓存失配率。通常有三 种数据组织方式用于降低缓存失配率【2 5 】：聚簇( c l u s t e d n g ) 、染色( c o l o r i n g ) 和 压缩( c o m p r e s s i o n ) 。聚簇将经常会破同时访问的多个数据放到一个缓存块中， 从而使c p u 访问这些数据的时候最多只造成一次缓存失配；染色将数据分为常 用数据和不常用数据，通过某种组织方式使得这两种数据映射到缓存中的时候 不相互冲突，从而使常用数据能够长久的停留在缓存中；压缩则使得更多的数 据可以被聚簇到一个缓存块中。 2 3 3 代数优化 代数优化的技术是关系数据库系统研究者建立在关系代数的基础上仓i 造 的。用代数表示有两个目的：一是可以用定义精确的代数语言来定义，以便能 完整地定义这个代数的操作；二是作用代数可以支持查询的优化，所以这种代 数拥有丰富的规则集。 1 路径表达式中谓词计算的提前 路径表达式中的谓词是按顺序计算的，在有些情况下可以提前到路径表达 式之前进行计算。由于谓词表达式每次对当前节点集进行过滤时都要计算，所 以所有过滤都有相同的形式。如果谓词不和当前节点相关，则可以提前对其进 行计算，实际上只要计算一次就行了，因此可以显著的提高性能。以下情况谓 词表达式不和当前节点相关； ( 1 ) 表达式中没有路径表达式； ( 2 ) 表达式中有路径表达式。但是此路径表达式是以变量开始或以函数开 始，该函数不依赖于当前节点，并且返回节点列表。 2 f l w r 表达式中变量的计算顺序 回顾f l w r 表达式的计算过程可知，按顺序，对每一个变量的每一个绑定 基于索引的x q u e r y 实现的优化 值。它的下一个变量都需要重新计算一遍。在实际中，有些变量是不依赖于上 一个变量的，也不和其具体的值相关，这样算法就有很多重复的计算。对这种 情况进行优化，需要首先分析变量日j 的依赖关系。变量之间的依赖关系形成一 个有向无环图( d a g ) 。分析这种关系时，对每个表达式增加一个属性，记录其 引用的变量。每个表达式所引用的变量都是组成它的那些子表达式引用变量的 和。基本表达式中只有路径表达式引用变量。f o r 、l e t 表达式中的变量，依 赖于该表达式的子表达式所引用的变量。有了依赖关系后，就可以进行些优 化。很简单的一种是记录已经计算过的结果，如果出现的表达式和记录的情况 吻合，则可以直接读取它的结果。 3 x a l x a l 2 6 1 ，即x m l a l g e b r a ，是对x q u e r y 进行优化的一种代数。基于它的简 单的数据模型和定义的逻辑操作，可以简化查询语言优化规则的定义。x a l 的 核心在于集成。x a l 定义了适用于x m l 查询语言组成、优化和语义的逻辑操 作，这些操作独立于基本的存储描述。包括以下三种操作： ( 1 ) 抽取操作一从x m l 文档中抽取需要的信息 包括投影( ) 、选择( o ) ，