（计算机应用技术专业论文）xml查询处理技术研究与实现.pdf

摘要 1 2 3 6 3 9 卅夕毋。弓 x m l 已经成为互联网上数据发布和数据交换的事实标准。然而由于其强大 的数据表达能力，x m l 完全可以在互联网和数据库之间扮演更加重要的角色。 x m l 是典型的半结构化数据，关系数据库管理系统由于关系模型本身的缺陷， 并不适合管理x m l 数据。现在互联网上已经存在大量以文件形式存放的x m l 数据，这些数据包含了丰富的信息，因此一个可以从文档中抽取信息的x m l 文 档查询工具是很必要的。 近年来，随着x m l 相关技术的深入研究，x m l 查询已经具备了坚实的技 术基础。传统数据库的大部分成熟技术可以比较方便地移植到x m l 查询上来。 半结构化数据查询技术方面的研究成果也可以直接应用于x m l 查询。更为重要 的是，w 3 c 已经为x m l 定义了模式、查询语言和查询形式语义等数据库才具备 的特征，这使得采用类似用s q l 查洵关系数据库的方式进行x m l 查询成为可 能。 、 ， 一虽然x m l 查询已经有了很好的技术基础，但由于x m l 数据自身的特点， 以度和传统数据模型的差别，x m l 查询在理论上和实现上都还存在很多难点。 本文结合我们实现的x m l 文档查询系统x d q u e r y 探讨了x m l 查询的各种实现 技术。由于w 3 c 提出的x q u e r y 已得到广泛的支持，很有可能成为正式的标准， 因此x d q u e r y 采用它作为查询语言。x q u e w 包括的内容非常丰富，通过分析它 的使用案例，并考虑到实现的难度，我们着重于实现一个核心的功能子集，同时 针对需要扩充了更新的能力。根据x q u e r y 的形式语义，并参照l o r e 系统，我 们定义了x q u e r y 的逻辑操作和物理操作。与关系模型不同，x m l 数据是树状 结构，路径表达式在查询中非常关键，而单纯的值索引远不够用。我们借鉴l o r e 系统的d a t a g u i d e 实现一个更适合x m l 数据的路径索引。此外，我们还考虑了 索引的存储问题，将索引存成x m l 文档，使其具有和源文档同样的可移植性。 x d q u e r y 采用基于代价的查询优化策略，同时也利用启发式规则做一定的逻辑 优化。和传统数据库系统不同，x d q u e r y 是内存查询处理系统，不存在内外存 的传输瓶颈，于是我们采用的是基于基准操作次数的代价模型。最后，我们通过 实验数据分析和验证了x d q u e r y 采用各项技术，包括索引及其存储技术、文档 规模和查询优化本身的代价等对查询性能的影响。p 关键词：x m l 查询，x d q u e r y ，x q u e r y ，索引技术，查询优化 塑望查兰堡生兰生堡苎； a b s t r a c t x m li sf a s t e m e r g i n g a st h ed ef d c t os t a n d a r df o rd a t ar e p r e s e n t a t i o na n d e x c h a n g eo nt h ew o r l d w d i e w e b h o w e v e r , x m li s m u c hm o r et h a nt h eb r i d g e b e t w e e nw o r l d w d i e w e ba n dd a t a b a s e x m ld a t ai ss e m i s t r u c t u r e d 。a n dr e l a t i o n a l d a t a b a s ei s n ts u i t a b l ef o rm a n g e m e n to fi tf o rt h ei n h e r e n tl i m i t a t i o no fr e l a t i o n a l d a t am o d e l o nt h eo t h e rh a n d t h e r ei s1 0 r so fx m ld a t as t o r i n ga sf i l e so nt h e w o r l d w d i e - w e b t h e s ef i l e sc o n t a i nag r e a td e a lo fi n f o r m a t i o n s oa nx m l d o c u m e n t sq u e r yt o o li sn e c e s s a r yt or e t r i e v ei n f o r m a t i o nf r o mt h e s ef i l e s r e s e a r c ho nx m l q u e r yc a nb e n e f i tf r o mt h ep r e v i o u sr e s e a r c ho nd a t a b a s ea n d x m l t h e q u e r yt e c h n i q u e so f t r i d i t i o n a ld a t a b a s ea r em a t u r ee n o u g ht ob em i g r a t e d t ox m l q u e r y w h i l et h o s eo fs e m i s t r u c t u r e dd a t a b a s ec a nb ea p p l yt ox m lq u e r y d i r e c t l y t h em o s ti m p o r t a n tt h i n gi st h a tw 3 c h a sd e f i n e ds c h e m a ，q u e r yl a n g u a g e a n df o r m a ls e m a n t i c sf o rx m l ，w h i c h b r i n g st h ep o s s i b l i t yo fq u e r yx m l d o c u m e n t s j u s tl i k eq u e r y r e l a t i o n a ld a t a b a s e u s i n gs q l w b e c a u s eo fi t si n h e r e n tc h a r a c t e r i s t i ca n dt h ed i f f e r e n c eb e t w e e ni ta n dt r i d i t i o n a l d a t am o d e l ，t h e r ea r es t i l lm a n y p r o b l e m sa b o u tx m lq u e r y i nt h i sa r t i c l e ，w ed i s c u s s m o s tt e c h n i q u e so fx m lq u e r ya n di n t r o d u c eh o wt o i m p l e m e n tt h e m i nt h e x d q u e r y , a nx m ld o c u m e n t sq u e r ys y s t e md e v e l o p e db yu s x d q u e r ya d o p t s x q u e r y a si t sq u e r y l a n g u a g e x q u e r yi n c l u d e ss om u c h c o n t e n tt h a ti ti st o od i f f i c u l t f o ru st oi m p l e m e n ta l lo fi t sf u n c t i o n s w ed e c i d et o i m p l e m e n tac o r es u b s e to f x q u e r ya n de x t e n dt h ea b i l i t yo f u p d a t i n gb ya n a l y z i n gt h eu s ec a s e so fi t b a s e do i l t h ef o r m a ls e m a n t i c so fx q u e r ya n dr e f e r i n gt ot h el o r es y s t e m ，w ed e v e l o pt h e l o g i c a lo p e r a t o r sa n dp h y s i c a lo p e r a t o r so fx d q u e r y x m ld a t ai st r e e s t r u c t u r e da n d p a t he x p r e s s i o n sa r eo fg r e a ti m p o r t a n c ei nx m l q u e r y s ow ed e v e l o pap a t hi n d e x b a s e do nt h ed a t a g u i d eo fl o r eb u tm o r es u i t a b l ef o rx m l d a t aa n dx m l q u e r y f u r t h m o r e ，i n d i c e so fx d q u e r yc a r lb es t o r e da s lf i l e sa n dt r a n s f e r r e dt o g e t h e r w i t ht h e s o u r c ex m ld o c u m e n t s x d q u e r y a d o p t s c o s t - b a s e d s t r a t e g y f o r o p t i m i z a t i o n ，a n da l s ou s e sa d d i t i o n a lh e u r i s t i c st of u r t h e rp r u n et h es e a r c hs p a c e x d q u e r y i sa m e m o r y - b a s e dq u e r ys y s t e m ，a n di t sc o s tm o d e li sb a s e do nt h ec o u n t o fr e f e r e n c eo p e r a t o r , w h i c hi sq u i t ed i f f e r e n tf r o m t h a to ft r i d i t i o n a ld a t a b a s e m o s t o ft h et e c h n i q u e sd i s c u s s e di nt h i sa r t i c l ea r ei m p l e m e n t e di n x d q u e r ya n dd e t a i l p e r f o r m a n c e r e s u l t sa r er e p o r t e d k e y w o r d s ：x m l q u e r y ，x d q u e r y ，x q u e r y ，i n d e x ，q u e r yo p t i m i z a t i o n 儿 浙江人学硕卜学位论文 第一章绪论 1 1 互联网、数据库与x m l 查询 x m l 以其数据和表现相分离的特性和强大的数据表达能力，已经成为互 联网和数据库之间沟通的桥梁，它的出现使文本的互联网转变为数据的互联网一 一一个全球范围的分布式数据库i z j ! 然而，x m l 不仅仅是互联网和数据库之间的中间媒介，它完全可以做更多 的事情。x m l 最大的优点是它强大的数据表达能力，不仅可以表达关系模型和 对象模型的数据，而且还可以表达不规则的，易变的数据，它是典型的半结构化 数据( s e m i s t m c t u r e dd a t a ) 【3 】。既然x m l 包含着数据，那么就存在着如何查询， 如何管理这些数据的问题，而目前应用最广泛的关系数据库管理系统并不适合管 理x m l 数据。这是因为关系模型的二维表结构在表达树形结构的x m l 数据上 存在很大的困难，不但转化算法复杂，而且数据的冗余度很大，简单的x m l 数 据往往需要表示成多个表【4 ，5 1 。不仅如此，关系模型还会丢失x m l 数据包含的 一些重要信息，比如数据之间的相对次序，以及数据在文档中的绝对次序。受关 系模型的限制，直接用s q l 语句查询x m l 数据也存在表达不自然，查询效率 低的问题f 4 ，5 1 。如果先用比较自然的查询语言书写查询语句，再将其转化为s q l 语句，又会带来冗余j o i n 的问题，而消除冗余j o i n 的代价是非常高的【6 】。 目前对x m l 的应用也还处于比较简单的层次。大部分应用都是将x m l 作 为一种更好的数据发布技术，用来将关系数据库中的数据发布到互联网上，而没 有考虑到x m l 文档本身也是数据，本身也是可以查询的。除了上面提到的用关 系模型表达x m l 数据的各种问题外，这类应用还存在其他一些缺陷，举个例子 来说，比如网上购书。一开始很可能用户并不知道具体的书名，而只知道大概的 范围。于是，他要反复进行查询搜索，逐渐缩小查询范围，直到找到自己需要的 书。在这个过程中，每个查询都要访问远端的后台数据库，而且都是在同样的原 始数据集中查询。由于用户的要求越来越明确，每次查询都是在上一次查询基础 上进行，因此查询只需要在上次查询的结果集上进行，而不需要访问全部的原始 数据集。此外每次查询都要将查询结果构造成x m l 文档。显然，在这个查询过 程中，数据库服务器上进行了多次查询，而且这些查询都要访问原始的数据集， 因此不但服务器负担重，而且对原始数据集的多次重复访问也是一种浪费。对于 这类访问，完全可以在数据集不是很大的情况下将其构造成x m l 文档，后续的 查询就可以直接在x m l 文档上进行，这样可以充分利用x m l 本身包含数据的 浙江大学硕士学位论文 特点，而且可以避免上述的问题。甚至可以将x m l 文档发到客户端，用户就可 以在本地直接查询这个文档，这样不仅降低了服务器的负担，而且可以提高查询 的响应速度。 事实上，现在互联网上已经存在大量的x m l 数据，这些数据基本上仍是以 文件的形式存放。这些x m l 文档一般都不大，但包含了丰富的数据，因此需要 一个可以从文档中抽取信息的x m l 文档查询工具。近年来，随着x m l 相关技 术的深入研究，x m l 查询已经具备了峰实的技术基础。传统数据库的查询技术 无论是理论还是实现都已经相当成熟，大部分技术都可以比较方便地移植到 x m l 查询上来。x m l 是典型的半结构化数据，因此半结构化数据查询技术方面 的研究成果可以直接应用于x m l 查询p 7 1 。更为重要的是，w 3 c 在x m l2 1 2 作 文本【8 9 1 0 】中为其定义了模式( x m ls c h e m a ) 、查询语言( x q u e r y ) 、查询形式 语义( f o r m a ls e m a n t i c s ) 等数据库才具备的特征，并已得到广泛的支持，这使 得采用类似用s q l 查询关系数据库的方式进行x m l 查询成为可能。此外，随 着计算机硬件技术的发展，现代计算机的内存容量越来越大，可以在内存中处理 更多的数据，对x m l 数据的查询完全可以在内存中进行。x d q u e r y i “l i e 是一个 基于内存的x m l 文档查询系统，它实现了w 3 c 提出的x q u e r y 主要功能，提供 了对x m l 文档的高效查询能力。 1 2x i q l t 查询研究现状 虽然x m l 查询已经有了很好的技术基础，但由于x m l 数据自身的特点， 以及和传统数据模型的差别，x m l 查询在理论上和实现上都还存在很多难点。 文献【”】指出了需要解决的一系列问题： 由于x m l 是一个文档而不是一个数据模型，需要将其转换成真正的数 据模型。 当使用者将x m l 文档和数据库概念混合起来时，需要处理各种可能出 现的冲突。 在相当自由的x m l 格式情况下，在一定程度上需要有新的理论和实现 技术来设计x m l 数据库。 需要很好地理解x m l 的可选d t d 或其它模式定义和传统数据库模式之 间的关系，并加以利用。 需要定义一种适宜的x m l 查询语言。在建立以数据为中心的x m l 应 用之前，用户对查询语言的要求是不清楚的，所以这任务是相当艰巨 的。 虽然在因特网上x m l 的应用主要是只读环境，但是必须考虑可能的数 2 浙江大学硕士学位论文 据库修改。 对于x m l 查询，需要同时考虑传统的数据库查询处理方式和新的方式 来对结构化、半结构化和自由文档进行有效的处理。 如何将传统数据苦中的视图机制在x m l 数据库中加以有效的实现。 随着研究的深入，目前这些问题已经得到了不同程度的解决i l 。 对x m l 查询研究中出现了不少的原型语言，其中比较著名的有l o r e l i l ， x m l q l 【1 5 1 ，x m l g l t l 6 1 等，这些语言各有优点【1 7 1 ：x m l q l 和x m l 文档的集 成性比较好，l o r e l 的功能比较强，而x m l g l 在图形化界面方面做得比较好。 q u i l t 综合先前各种语言的优点i l 驯：它的路径表达式参考了x p a t h ，变量绑定借 鉴了x m l q l ，f l w r 表达式类似于s q l ，而且它还支持用户自定义函数。q u i l t 不仅可以查询x m l 数据，也可以方便地查询关系数据，因此它的表达能力是很 强的。正因为如此，w 3 c 在它的基础上提出了x q u e r y 语言【1 0 】，该语言已经获 得广泛的支持，因此很有可能成为x m l 查询的标准语言。针对x m l 数据缺少 模式的缺点，w 3 c 为x m l 定义了模式1 8j ，这使得x m l 很有希望成为和关系模 型，对象模型并列的新型数据库数据模型，而不仅是数据表达方式。对于x m l 查询来说，仅有查询语言是不够的，因此w 3 c 为x m l 查询定义了查询数据模 型【1 9 】和形式语义【9 】，这两者都是基于x m l 模式的，前者定义了x m l 的数据模 型，后者对语言的各方面做了精确的定义。w 3 c 的初衷是设计一种既适合人阅 读，又适合程序处理的x m l 查询语邑x q u e r y 满足了前一种要求，在它的基 础上，w 3 c 又将其用x m l 表示，称为x q u e r y x 2 0 1 ，这种表示方法更适合程序 处理。 由于关系数据库产品的广泛使用，如何利用关系数据库管理和查询x m l 数 据亦成为研究的重点。文献| 4 1 提出了利用数据挖掘将没有d t d 的x m l 数据转化 为关系数据的方法，该方法将x m l 数据中比较规则的部分转化为关系数据，而 不规则部分则不转化，从而降低了转化的难度。文献【5 】提出了一种利用d t d 将 x m l 数据转化为关系数据的方法，该方法先化简d t d ，然后将d t d 中每一种 包含子元素的元素都转化为一个表，这样，一个简单的d t d 可能转化为1 0 多个 关系表。这两种方法都存在着转化效率低，数据冗余大的问题，而且适用范围也 不是很广。在此基础上如何查询、表达和更新存储在r d b m s 中的x m l 数据的 问题也得到了一定的研究。文献【5 】在转化算法的基础上还给出了将x m l o l 和 l o r e l 查询转化为关系查询的方法。文献【2 l 】提出一种利用关系数据的x m l 视图 查询x m l 文档方法，由于查询是建立在x m l 视图上的，和x m l 数据到关系 数据的转化没有关联，因此这种查询方法对于所有的数据转化算法都是适用的。 文献1 2 2 】在x q u e r y 语言上扩展了更新功能，并能将其转化为相应的s q l 更新语 句。总的来说，由于关系模型的固有缺陷，这些方法的效率都不高5 ，2 1 ，2 2 1 。随着 浙江人学埘! 卜学位论文 x m l 研究的发展，出现了大量的x m l 数据库产品和原型系统【2 ”，如l o r e l 2 ”， t a m i n 0 1 2 5 1 ，p o e t l 2 6 1 ，e x c e l o n 27 1 ，s t o r e d 4 1 等。如何评估这些系统的性能也成 为研究的课题之一。文献【2 8 提出了一个x m l 数据库系统的测试基准，而文献 概述了建立x m l 数据库测试基准需要考虑的一系列问题。综上所述，在结合 x m l 和数据库技术方面已经有了非常广泛的研究，也取得了很多成果，但也遇 到了许多问题，这需要在数据库理论和x m l 技术有更多的突破1 6 j 。 x m l 是典型的半结构化数据，因此半结构化数据管理方面的研究成果对 x m l 查询有特别重要的借鉴作用。l o r e 2 4 1 系统是斯坦福大学开发的半结构化数 据库管理系统，它在半结构化数据的查询处理技术方面做了深入的研究。l o r e 采用o e m ( o b j e c te x c h a n g em o d e l ) 1 2 4 1 模型表示半结构化数据，该模型基于图， 表示x m l 也比较自然。l o r e 的查询语言l o r e l 基于o q l 语言【l ”。l o r e 采用基 于代价的查询优化技术，同时也应用了一些启发式规则以减小搜索空间1 3 0 】；它 针对半结构化数据的特点提出了包括边索引，父子索引在内的几种新型索引i3 1 】： 它的d a t a g u i d e p2 ，”j 不仅可以用作路径索引，还可以记录优化所需的统计信息， 甚至可以作为可视化用户界面的一部分：它还提出了利用d a t a g u i d e 展开正则路 径表达式的方法1 3 ”。文献1 3 j 也阐述了如何应用l o r e 管理x m l 数据。鉴于l o r e 系统在半结构化数据查询处理技术方面的研究己取得大量成果，我们在开发 x m l 文档查询系统时很多技术都借鉴了该系统。 传统数据库技术是x m l 查询研究的基础，它的最新发展也为x m l 查询研 究提供了很好的参考。现在计算机的硬件技术发展不平衡，c p u 速度的增长远 远超过了内存速度的增长，两者之间的速度鸿沟越来越大。随着内存容量的增大， 更多的数据可以在内存中处理，因此外存与内存之间的i o 瓶颈逐渐转移到内存 和c a c h e 之间。文献1 35 】通过实验数据定量分析了内存和处理器体系结构对数据 库运行速度( 主要指查询) 的影响，指出二级数据c a c h e 和一级指令c a c h e 对性 能影响最大，因此也是优化的重点。文献1 3 6 】提出了种优化数据库在内存中的 运算速度的方法：关系表的垂直分割，以及基于基数聚簇的h a s h j o i n 。文献【”】 则提出一种新的外存数据组织方法，即将每页的数据由按行存储改为按列存储， 从而提高了数据的c a c h e 利用率，因此显著提高了系统的性能。x d q u e r y 的查 询处理是基于内存的，因此对传统数据库的内存c a c h e 瓶颈研究的成果对于 x d q u e r y 的查询优化技术的研究有很好的启迪。 1 3 本文的工作 本文主要围绕“x m l 的索引和查询优化技术”这一主题展开，结合我们实 现的x m l 文档查询系统x d q u e r y i 】探讨了x m l 查询需要的新型索引和内存查 4 浙江人学硕士学位论文 询处理的各种优化技术。论文以下内容组织如下： 第二章：介绍x q u e r y 语言。w 3 c 制定的x q u e r y 工作草案包括了x q u e r y 语言，数据模型，形式语义，操作与函数等，本章一一介绍了这些内容。 第三章：介绍我们实现的x m l 文档查询系统x d q u e r y 。在这个原型系 统上我们实现并验证了一系列的索引和查询优化技术。这一章主要介绍 该系统的体系结构以及实现环境。 第四章：介绍x d q u e r y 中x q u e r y 的实现技术。x q u e r y 包括的内容非 常丰富，我们通过分析它的使用案例，对其进行了裁剪，舍去一些很少 使用的功能，而着重于实现一个核心的功能子集，同时针对需要扩充了 更新的能力。参照l o r e 系统，我们定义了x q u e r y 的逻辑操作和物理操 作。 第五章：介绍x d q u e r y 采用的索引技术。与关系模型不同，x m l 数据 是树状结构，路径表达式在查询中非常关键，而单纯的值索引远不够用。 我们借鉴l o r e 系统的d a t a g u i d e 实现一个更适合x m l 数据的路径索引。 此外，我们还考虑了索引的存储问题，使索引具有和文档相同的可移植 性。 第六章：介绍x m l 的查询优化技术。x d q u e r y 采用基于代价的查询优 化策略，同时也利用启发式规则做一定的逻辑优化。和传统数据库系统 不同，x d q u e r y 是内存查询处理系统，它的代价估算要复杂得多。我们 采用的是基于基准操作次数的代价模型。另外对优化本身的代价也做了 初步的研究。 第七章：通过实验数据验证我们采用的技术，包括索引的存储技术，索 引在查询中的作用，文档规模对查询性能的影响，查询优化本身的代价 等。 第八章：总结全文，展望未来。 浙江大学硕士学位论文 第二章x m l 查询语言 2 1x m l 查询语言研究历史 早在x m l 推出以前，数据库研究人员就注意到现实生活中存在着大量的不 规则数据，称其不规则，是指数据没有固定的模式、结构易变，而传统的数据库 只能表达结构化的数据，因此研究人员提出了半结构化数据模型，以其相应的查 询语言，l o r e l l l 4 是其中比较著名的一个。l o r e l 是l o r e 系统的查询语言，它是以 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 o r e l 也可以用来查询x m l 数据。 随着互联网的飞速增加，x m l 以其强大的数据表达能力及其简单、跨平台 的优点逐渐成为信息存储、交换和表示的事实标准，因此如何有效查询x m l 信 息这个问题也日益变得重要。在这种背景下，研究人员提出了很多种x m l 查询 原型语言，其中比较著名的有x m l q l l l ”，x s l 38 1 ，x q l 39 1 ，x m l g l 1 6 1 ，q u i l t 1 8 1 等。 x v i l q l 是a t & t 实验室的数据库研究人员设计的。x m l q l 通过加 入明确的构造语句c o n s t r u c t 扩展s q l ，使用元素模式匹配进行查 询处理。x m l q l 能表达对多数据源的x m l 查询和转换。 x m l - g l 是意大利p o l i t e c n i c od im i l a n o 大学设计的一种图形化查询语 言，它利用边标记图来图形化表达x m l 数据和d t d 。在x m l g l 中， 所有的元素都是可视的，适于作为友好的人机界面( 类似q b e ) 。 x s l 由w 3 c 的x s l 工作组设计，一段x s l 程序包含一组模板规则 ( t e m p l a t er u l e s ) ，每个模板规则由两部分构成：与数据源中某类结点 匹配的模式和一个示例模板构成输出树。x s l 利用x p a t h 4 0 1 定义的语言 处理选择、条件和文本产生。 x q l 是微软公司设计的，它的作用是选择和过滤x m l 文档的元素和文 本。x q l 可以看成是x s l 模式语法的自然扩展，它的设计目标是简单、 紧凑，可以作为u r i 的部分，所以降低了部分表达能力。 q u i l t 综合很多语言的优点【l8 j ：它的路径表达式参考了x p a t h ，变量绑 定借鉴了x m l q l ，f l w r 表达式类似于s q l ，而且它还支持用户自 定义函数。q u i l t 不仅可以查询x m l 数据，也可以方便地查询关系数据， 因此它的表达能力是很强的。 正是因为q u i l t 综合了先前多种语言的优点，具有强大的表达能力，w 3 c 提 浙江人学硕七学位论文 出的x q u e r y 语言是以它为基础改进的，主要增加了形式语义和对x m l s c h e m a 的支持。目前x q u e r y l 0 工作草案包括了x q u e r y 语言定义、查询数据模型、形 式语义、函数与操作、x q u e r y 的x m l 语法( x q u e r y x ) 、查询案例和查询要求 等内容。2 0 0 1 年2 月w 3 c 推出x q u e r y 的最初版本，当时还没有函数与操作和 x q u e r y x ，形式语义还称为查询代数。这个版本只是初步确定了语言，对很多细 节还没有精确的描述，对查询代数也没有系统的介绍。2 0 0 1 年6 月w 3 c 推出了 第二个版本，将查询代数改为形式语义，同时增加了函数与操作【4 l 】和 x q u e r y x 20 1 。这个版本对语言细节做了改动，并且提出了x q u e r y l 0 的核心语法 ( c o r es y n t a x ) 一j ，所有x q u e r y 表达式都可以转化为核心语法。同时这个版本 为x q u e r y l 0 和x p a t h 2 0 提供了公共的数据模型，并定义了公共的操作和函 数。w 3 c 要求x m l 查询语言不仅要方便普通用户理解，还应具备基于x m l 的 语法 1 “。x q u e r y 首先满足了第一个要求，这个版本制定了x q u e r y x ，它定义了 x q u e r y 的x m l 表示。2 0 0 1 年1 2 月w 3 c 推出了第三个版本，也是目前最新的 版本。这个版本明确指出x p a t h 2 0 是x q u e r y l 0 的一个子集【1 0 】，并因此重新组 织了整个文档。在新的草案中，x q u e r y 对每个表达式都做了精确的定义，公共 数据模型，以及操作和函数也做了一些修改。 2 2x q u e r y l 0 x q u e r y 最新的版本是2 0 0 1 年1 2 月发布的，而我们在开发x d q u e r y 时采用 的是2 0 0 1 年6 月发布的第二版。从单纯的语言要素来看，新版本只是做了一些 细节的改动，因此在介绍时以最新的版本为主，同时会指出重要的修改之处。 2 2 1x q u e r y 语言 x q u e r y 是一个功能性语言，它的各种表达式之间可以相互嵌套；它又是一 个强类型化的语言，所有的操作、表达式和函数都必须有一定的类型；和x m l 一样，它也是大小写敏感的，所有的关键字都必须小写。 2 2 1 1 预备知识 定义 序列( s e q u e n c e ) ：0 个或多个数据项的有序集合；表达式的结果总是一个序 列；只包含一个数据项的序列称为s i n g l e t o n 序列；不包含数据项的序列称 为e m p t y 序列。 浙江大学硕l 学位论文 数据项( i t e m ) ：一个简单值或者节点。 简单值( s i m p l e v a l u e ) ：x m ls c h e m a 中定义的基本数据类型，或者引用。 名域( n a m e s p a e e ) ：名字的集合，用u r i 表示，它与元素和函数名构成一 个( 名域，非正规名) 对，可以区分来自不同名域具有相同非正规名的元素 和函数。 节点( n o d e ) ：在x q u e r y l 0 和x p a t h2 0 数据模型中定义，包括d o c u m e n t ， e l e m e n t ，a t t r i b u t e ，t e x t ，n a m e s p a c e p r o c e s s i n gi n s t r u c t i o n 和c o m m e n t 。 名字( n a m e ) ：由名域和非正规名( 即字符串) 构成，在x m l s c h e m a 中定 义。 表达式上下文( e x p r e s s i o nc o n t e x t ) ：一个给定表达式的上下文包括所有会 影响到它的结果的信息。表达式上下文分为静态和动态两类。静态上下文是 在编译阶段可以确定的信息；动态上下文是在运行时才可确定的信息。 数据类型 x q u e r y 有一个基于x m ls c h e m a 的类型系统。每个操作，表达式或者函数 都要求数据具有一定韵类型，如果实际执行中数据的类型和期望的类型不一 致，就要进行类型转化。x q u e r y 定义了一系列隐含的类型转化规则，此外 它还支持语句中显式的类型转化。 基本表达式 x q u e r y 基本表达式包括变量，文字，元素与函数名，通配符，k i n d t e s t 和 括号表达式。变量用“$ ”加上名字表示，女n $ b o o k ；元素和函数名都必须是 正规的名字；文字包括字符串和数值；通配符可以代替整个名字，也可以代 替其中的名域或者非正规名；k i n d t e s t 用于获得相应节点的值。 2 2 1 2 表达式的运算 作为查询语言，x q u e r y 显然支持包括算术表达式、比较表达式、逻辑表达 式和量词表达式这些基本的表达式。此外，x q u e r y 还支持类似程序设计语言的 条件控制语句，如 i f $ p e r s o n m a r r i e de q ”y e s ” t h e n $ p e r s o n s p o u s e n a m e e l s e $ p e r s o n n a m e x q u e r y 的比较表达式很特殊，一共分为四类： 1 值的比较运算：即数值，字符串的大小比较，用操作e q ，i t ，g t 等表示。 2 通用比较运算：即序列上的比较运算，用操作= ， 等表示。这里需 要注意的是，序列上的比较运算是隐含的存在量词操作，即两个序列中 浙江大学硕十学位论文 只要有任意一对数据项运算结果为真，整个表达式的结果也就为真：仅 当两个序列中任意一对数据项运算结果都为假时，整个表达式的结果才 为假。 3 节点的比较运算：即比较两个节点的对象标识，只有等于( = = ) 和不等 ( f _ = ) 两种操作。如果相等则表示两个节点实际上是同一个节点。 4 次序的比较运算：即比较两个节点在文档中的次序，有在前( ) ，祖先节点( p r e c e d e s ) ，子孙节点( f o l l o w s ) 四种操作。 在上一个版本中，x q u e r y 对比较的定义很含糊，没有区分对象标识比较，值比 较和序列比较，也没有定义次序的比较。 和s q l 一样，x q u e r y 支持排序表达式，可以对一个序列按多个数据项进行 排序。如下例表示对价格大于1 0 0 的书按第一作者和标题的升序( 缺省的) 排序。 b o o k 【p r i c e i 0 0 】s o r t b y ( a u t h o r 【1 】，t i t l e )( 1 在x q u e r y 中，所有的表达式运算结果都是一个序列，序列和集合类似，只 不过它是有序的。x q u e r y 允许用户构造序列，以及多个序列之间的u n i o n ， i n t e r s e c t 和e x c e p t 垛作，如下例所示。 ( 1 0 j 1t o4 ) 等价于( 1 0 ，1 ，2 ，3 ，4 ) ( 2 ) 若$ s e q l = ( ， ) ，$ s e q 2 = ( ， ) ，则 s s e q lu n i o ns s e q 2 等于( ， ， ) s s e q 2i n t e r s e c t $ s e q 2 等于( )( 3 ) 2 2 1 3 路径表达式 x m l 数据具有树状结构，因此在x q u e r y 查询中，路径表达式起着非常关 键的作用。x q u e r y 的路径表达式的表达能力非常强，从下列几个表达式中就可 以看出： d o c u m e n t ( ”b i b x m l ”) c h i l d ：b i b d e s c e n d a n t o r s e l f ：a u t h o r d o c u m e n t ( ”b i b x m l ”) b i b a u t h o r $ b i b a u t h o r n a m e $ b i b a u t h o r a g e b i b ( a r t i c l elp a p e r ) a u t h o r b i b a u t h o r + $ b i b a r t i c l ec t i t l e = “u p d a t i n gx m l ” a u t h o r ( 1 ) ( 2 ) 1 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) 首先我们注意到式( 1 ) 和式( 2 ) 结构类似，实际上它们含义一样，都表示b i b x m l 文档根元素的b i b 子元素的a u t h o r 子孙元素。x q u e r y 的路径表达式有两种表示 方法，一种是显式的a x i s 表达式，一种是简化的表达式。这里( 2 ) 式是( 1 ) 式的简 浙江人学颂士学位论文 化形式。表2 1 列出了路径表达式的几种重要元素及其简化形式。为了简便起见， 如没有特别指出，本文所有的查询都采用简化的表示方法。除了“”操作表示 子孙节点外，还有一个“”操作表示当前节点的父元素，如式( 3 ) 所示。路径表 达式还支持属性上的操作，如式( 4 ) 所示。式( 5 ) 和式( 6 ) 表明，x q u e r y 的路径表达 式允许正则表达式。式( 5 ) 表示根元素的b i b 子元素的a r t i c l e 子元素或者p a p e r 予 元素的a u t h o r 子元素，式( 6 ) 表示根元素的b i b i 子元素的a u t h o r 子孙元素的所有 子元素。x q u e r y 还允许在路径的中间插入谓词条件，如式( 7 ) ，这不仅大大增强 了路径的表达能力，还可以缩小查询的中间结果，从而优化查询性能。x q u e r y 支持两类路径表达式：绝对路径和相对路径。上面路径表达式中( 5 ) 和式( 6 ) 是绝 对路径，其余是相对路径。 a x i s简化形式含义 c h i l d ：p a r ap a r a选择当前节点的p a r a 子元素 a t t r i b u t e ：n a m e n a m e 选择当前节点的n a m e 属性 d e s c e n d a n t - o r - s e l f ：p a r a “p m a选择当前节点名为p a r a 的子孙元素 如果当前节点名为p a r a ，则选择它，否则什 s e l f i ：p a r a v 么都不做 如果当前节点的父节点名为p a r a ，则选择它， p a r e n t ：p a r a 否则什么都不做 2 2 1 4f l w r 表达式 表2 1 x q u e r y 提供f l w r ( 发音同f l o w e r ) 表达式用于迭代运算和将变量绑定到 中间结果上。这个表达式也经常用于实现多个文档之间的j o i n 操作和查询结果重 构。f l w r 代表关键字f o r ，l e t ，w h e r e 和r e t u r n ，即表达式中的四个子句，它们 的含义如下： f o r 子句：将一个或者多个变量关联到表达式( 通常是路径表达式) 上， 这些表达式计算结果的序列的笛卡儿积就对应着这些变量绑定的元组 集。 l e t 予句：将变量直接绑定到整个表达式上。如果存在着f o r 子句，则l e t 予句创建的变量绑定就加到f o r 子句创建的变量绑定元组中，否则1 e t 子句为所有的变量绑定创建一个元组。 w h e r e 子旬：用作f o r 子旬和1 e t 予旬创建的变量绑定元组的过滤器。 w h e r e 子句中的表达式，称为w h e r e 表达式，是对上述元组集进行迭代 计算。对于每一个元组，如果w h e r e 表达式计算结果为真，则该元组可 以用于r e t u r n 子句计算，否则该元组就被舍弃。 r e t u r n 子旬：包含用于构造f l w r 表达式结果的表达式。r e t u r n 子句也 浙江大学硕l 学位论文 是对w h e r e 表达式筛选过的变量绑定元组进行迭代计算。 以下是几个f l w r 表达式的例子