（计算机软件与理论专业论文）xquery语言的查询实现.pdf

摘要 摘要 下p 多，岁7 3 j x m l 已经成为互联网上数据表示和交换的标准格式。它的原理 很简单：标记用来表示数据元素的语义，元素之间的嵌套和引用来表 示它们之间的关系。这些特性使得x m l 不仅可以表示结构化数据， 也可以表示半结构化数据，在数据集成，元数据管理，w e b 数据管 理方面都有大量的应用。随着x m l 数据的大量涌现，有效的存储x m l 并提供查询能力是x m l 发挥作用的关键。为此我们研究了x m l 查 询语言一x q u e r y 的实现以及支持查询实现的存储技术，主要包括以下 内容： 1 x m l 数据模型和代数：f 代数作为查询语占的理论基础，对 查询处理和优化有着十分重要的地位，而数据模型又是代数 操作的对象，所以对x m l 查询语言的研究必然要涉及到 x m l 的数据模型以及定义在其上的代数，尸本文将简单说明 一下x m l 的数据模型和代数。 7 2 x m l 存储方法：对于一个数据库来说，它底层的数据存储 方式有着和查询语言一样重要的地位，是效率的关键夕本文 介绍了我们在实现时使用的存储策略，同时也简要介绍了其 他的x m l 数据的存储方式。 3 x q u e r y 的实现：( x q u e r y 语言是w 3 c 提出的x m l 查询语 言。在x q u e r y 草案形成以前就有很多x m l 的查询语言。 有的是从以前的系统修改而成，如l o r e l ；有的是图形方式 的查询语言，如x m l g l ；有的语言则是根据x m l 数据 的特点而单独提出的，如x q l 和x m l q l 。x q u e r y 在这 些语言的基础上，继承了众多语言的优点，是一个强大，灵 活的语言。虽然目前x q u e 吖还没有成为一种规范，对它的 改进仍在进行中，但是很多大型公司以及科研机构都看好 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 q u e r y ，代数，关系数据库 a b s t r u c t _ ，_ _ _ - ，_ _ ，_ _ _ - _ _ _ _ ，_ _ - _ _ _ _ _ _ _ - _ _ _ _ _ 一 m p l e m e n t a t i o n o fx q u e r yl a n g u a g e c h e n gl e i ( c o m p u t e r s o f t w a r ea n d t h e o r y ) d i r e c t e db yl ig u o j i e x m li sas 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 de x c h a n g eo nt h e i n t e r n e tt h eb a s i ci d e a su n d e r l y i n gx m l a r em e r ys i m p l e ：t a g so nd a t a e l e m e n t si d e n t i f yt h em e a n i n go ft h ed a t aa n dn e s t i n ga n dr e f e r e n c e s r e p r e s e n t 佗l a t b n s h i 口sb e t w e e nd a t ae t e m e r i t s t h e s ef e a t u r e sm a k e x m ls u i t a b l ef o rb o t hs t r u c t u r e dd a t aa n ds e m i s t r u c t u r e dd a t a a n d x m lj sw i d e l yu s e di nd a t ai n t e g r a t i o n m e t a d a t am a n a g e m e n t ，a n d w e bd a t am a n a g e m e n t w i t hl h ee m e r g i n go fv o l u m e so fx m l d a t a t h ee 衔c i e n ts t o r a g ea n dq u e r ym e c h a n i s mo fx m ld a t ab e c o m ev e r y i m p o r t a n t l nt h i sp a p e r , w ec o n c e n t r a t e0 ni m p l e m e n t a t i o no fx m l q u e r yl a n g u a g e - x q u e r y - a n d t h es t o r a g em e c h a n i s mt h a t s u p p o r t s e 仟i c i e n tq u e r y , i n c l u d i n g ： 1 x m ld a t am o d e ia n da l g e b r a ：a l g e b r ai s t h e o r yt h a t i st h e f o u n d a t i o no faq u e r yl a n g u a g e a n di sm e r yi m p o r t a n tf o rq u e r y e v a l u a t i o na n do p t i m i z a t i o n a l g e b r ao p e r a t e so nd a t am o d e l s o i ti sn e c e s s a r yt oi n v e s t i g a t et h ed a t am o d e la n d a l g e b r ao fx m l d a t at ou n d e r s t a n dx m lq u e r y l a n g u a g e ，a n d t h i s p a p e r i n t r o d u c e sx m ld a t am o d e ia n d a l g e b r ab r i e f l y 2 s t o r a g e m e t h o do fx m ld a t a ：t h es t o r a g em e t h o di sa si m p o r t a n t a sq u e r yl a n g u a g ef o rad a t a b a s e t h i sp a p e ri n t r o d u c e st h e s t o r a g es t r a t e g yw e u s e dw h e nw ei m p l e m e n tx q u e r y l a n g u a g e ， a n da l s os o m eo t h e rs t o r a g em e t h o d s 3 i m p l e m e n t a t i o no fx q u e r y ：x q u e r yi s t h ex m l q u e r yl a n g u a g e p r o d u c e db yw 3 c t h e r ea r em a n yx m lq u e r yl a n g u a g eb e f o r e x q u e r yd r a f t s o m eo ft h e ma r eb a s e do nl a n g u a g eo fp r e v i o u s p r o j e c t ，s u c h a sl o r e l s o m eo ft h e ma r e g r a p h i c a lq u e r y l a n g u a g e s u c ha sx m l g l s o m ei a n g u a g e sa r eb a s e do nt h e n a t u r eo fx m ld a t a s u c ha sx q la n dx m l q l x q u e r yh a s b o r r o w e df e a t u r e sf r o mt h e s el a n g u a g e sa n di ti sap o w e r f u l l a n g u a g e f o rq u e r y i n gx m l x q u e r y i so n l yi nad r a f ts t a t u s a n d i t se n h a n c e m e n t sa r e u n d e r g o i n g ，b u tm a n yc o m p a n i e sa n d r e s e a r c hi n s t i t u t e ss h o wg r e a ti n t e r e s t si nt h i sl a n g u a g e t h e y h a v ei m p l e m e n t e dm a n yd e m o e so fx q u e r yi a n g u a g ew ea l s o i m p l e m e n t e do n e 。a n dt h i sp a p e ri n t r o d u c e sa l g o r i t h m st h a tw e d e s i g n e d t oi m p l e m e n t x q u e r y k e yw o r d s ：x m l ，x q u e r y ，a l g e b r a ，r e l a t i o n a l d a t a b a s e 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究：l ：作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 刁i 包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：程，爹日期：7 加功z 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 名诬营翩躲才囝 嗍? 一 第一章引言 1 1 应用背景 x m l 1 的出现最初是因为h t m l 标记语言的不足。h t m l 语言有固定的格式， 它注重的是如何显示，并不关心实际数据的含义。这就给应用带来很大的困难。 由此也引出了不同厂商的浏览器对相同标记显示的差异，而且厂商间为了自己 的竞争力，又增加了许多特殊的标记，使得各个浏览器互不兼容。 x m l 则不关心数据的显示，只是用来表示数据，侧重于数据的意义。x m l 允许用户自定义标记，这样就给了x m l 数据具体的含义。而x m l 数据的显示则 由x s l 2 或其他手段来完成。除了数据内容的表示外，x m l 还有以下一些重要 的应用。 由于x m l 语言是自描述的，而且以文本方式存在，所以可以用来进行数 据的保值。其他的如w o r d ，p d f 等都是二进制的文件格式，只要有一处损坏， 整个文件就可能都不可用了，而x m l 由于是文本方式的，所以中间即使有很多 数据丢失了，仍不影响对整个文件的理解。同时由于软件升级和新软件的不断 出现，二进制的文件格式也不断的变化，现在流行的一些文件格式若干年后可 能就没有人在使用了，相应的程序也不存在了。所以二进制的格式不适合长久 的保存文件，而x m l 则是理想的选择。 由于x m l 的简单性，它可以很容易的实现异质系统问的信息互通。当今 的计算机世界中，不同企业、不同部门中存在着许多不同的系统，大到数百万 美元的m a i n f r a m e ，小到掌中型笔记本电脑。操作系统有n t 、u n i x ，数据库系 统有s q ls e r v e r 、o r a c l e 等等。要想在这些不同的平台、不同的数据库软件之 间传输信息，不得不使用一些特殊的软件，非常的不便。而不同的显示界面， 从工作站、个人微机、到手机，使这些信息的个性化显示也变得很困难。有了 x m l ，各种不同的系统之间可以采用x m l 作为交流媒介，见图l 3 。x m l 不但简 单易读，而且可以标注各种文字、图像甚至二进制文件，只要有x m l 处理工具， 就可以轻松地读取并利用这些数据。 图1 x m l 适合异构系统之间的交换 x q u e r y 语奇的a 咖实现 x m l 文件的简单性和易读性非常适合在电子商务上应用。e d i ( e 1 e c t r o n i c d a t ai n t e r c h a n g e ) 是目前电子商务文书交换的标准，实现e d i 的公司可以通过 电子形式相互交换订单发票等，节省大量文书往返的时阳j 和纸张的消耗。但是 e d i 需要使用昂贵的软件，聘请专业顾问，租用专门的网络，所以一直没有普 及丌柬，只有大型企业爿用的起。x m l 的出现使得中小企业使用e d l 成为可能。 x m l 非常适合用来作为交换文书的格式，而且又有很多低廉或免费的处理软件， 它们也可以在普通的网络上传输，这些特性使得不少公司开始研发基于x m l 的 新一代e d i 交换标准。 x m l 还在医学，化学，数学，音乐等领域有很广泛的应用，将是以后通用 的数据描述语言。对于大量的x m l 数据，它的有效查询就是一个很大的问题。 在x m l 语言的发展过程中，它的查询语言和存储方法一直是人们研究的重点， x o u e r y 4 是w 3 c 在o u i l t 5 语言的基础上改进而提出来的，具有很多查询语 言的优点，将是以后) 【m l 查询语言的标准。下面简单介绍一下x m l 及其查询语 言发展过程中的一些相关研究。 1 2x m l 简介 x m l 的全称是可扩展性标记语言( e x t e n s i b l em a k e u pl a n g u a g e ) ，正如上 节所说，x m l 的起源主要是因为h t m l 的局限。h t m l 算是s g m l 的一个应用，而 x m l 可以说是一个简单版本的s g m l ，所以x m l 的功能肯定比h t m l 强大。s g m l 2 1 是由g o l d f a r b 在6 0 年代提出，用来建立一个能够存储，查找，管理和发布法 律文档的系统。由于s g m l 非常复杂，所以它的应用一直没有推广开。 可以用两种观点来看一个x m l 文档。一种观点是从逻辑的角度，也就是看 文档中元素的意义和它们之间的关系。逻辑上一个x m l 文档由序言，根元素和 一些杂项元素( 如注释和处理指令等) 组成，每一个元素都由一些属性和子元 素组成，在子元素之间还可以有文本，注释和c d a t a 段。另一种观点是从物理 的观点来看，主要是把) ( m l 文档看做是由一些实体( e n t i t y ) 组成，每一个实体 都是一个处理的基本单元，按实体和文档问的联系实体可以分为内部实体，外 部实体，按照对实体的处理方式，实体又可分为可析实体和不可析实体。 w 3 c 在制定瑚l 的规范的时候是以下面几点作为目标的 x m l 应该可以直接在因特网( i n t e r n e t ) 上使用。 x m l 应该支持大量不同的应用。 x m l 应该与s 伽l 兼容。 处理x m l 文件的程序应该容易编写。 x m l 中的可选项应无条件地保持最少，理想状况下应该为0 个。 x m l 文件应该能够让人直接阅读，而且应该有足够的可读性。 x m l 的设计应快速完成。 x m l 的设计应该是形式化的，简洁的。 x m l 文件应易于创建。 x m l 标圮的简洁性是最不重要的设计目标。 可以看出目前的x m l 规范还是很好的满足了这些要求的。对于查询来说， 把x m l 文档分为两类是很有好处的，这两类是以数据为中心的文档 ( d a t a c e n t r i c ) 和以文档为中心的文档( d o c u m e n t c e n t r i c ) 。以数据为中心 2 t j i 占 的文档特点是存储的重点是数据，结构比较规范，一般来说都有一个s c h e m a 或d t d 来描述结构，图2 是一个该类文档的例子。以文档为中心的文档存储 的中心是文档信息，它的结构很不规范，各种标记性的元素分布在很多地方， 而且可能包含很多的递归结构，图3 是这类文档的一个例子。 图2 以数据为中心的文档图3 以文档为中心的文档 对于x m l 的理解和应用，每个人都有不同的看法，以下是比较普遍的十种 看法 2 2 ： x m l 是文本化的小型数据库表达语言。可以对其进行l o a d s a v e 。 i n s e r t ，r e m o v e ，u p d a t e s e l e c t 等操作；甚至可以把x m l 应用成为 一个中间层的虚拟数据库。 x m l 是客户端计算的数据结构载体。通过联合使用j a v a s c r i p t ，d h t m l 技术 实现客户端的小型信息过滤、查询、计算与通讯应用。 x m l 是信息的高层封装与运输的标准。据此x m l 也是不同应用系统之间的 数据接口标准，是所有信息的中间层表示；是中间层应用服务器( a s ) 的通用数 据接口。甚至可以用于数据仓库技术的数据迁移过程、数据库报告格式中。 x m l 是h t m l 的高层扩展。h t m l 面向文本、信息发布h t m l 容许混乱； x m l 面向数据、数据处理，x m l 要求工整( w e l l - f o r m e d ) 合法( v a l i d ) ；j j 户可 用x m l 创建自己的h 丁m l 。 x m l 是信息的对象化语言。d t d s c h e m a 是界面或类i n t e r f a c e c l a s s ， x m l 是对象实例o b j e c t x s l 是方法定义i m p l e m e n t m e t h o d ， x m l - d a t a 解决了x m l 类的继承问题。而x m l 中的资源( u r b 寻自k ( u r l ) 、 物理实体等又构成了信息的组件c o m p o e n t 。x m l 的r d f 是信息导航、浏 览、搜索的用户接口u l 标准。 x m l 是不同数据结构体的文本化描述语言它可以描述线性表、树，图形等 数据结构，也能描述文件化的外部数据结构。甚至可以制造类似x m l 的 c o m p i l e r ，可使文档在文本与二进制文件间互相转换，x m l d a f a 中严格定义 了x m l 中数据的物理类型。也可以说x m l 是一种通_ l j 的数据结构。 3 x q u e r y 语占的盘瑚实脱 x m l 是行业h t m l 扩展标记的定义语言。x m l 与h t m l 结合描述行业的 与h j 信息文档，如c d f ，c m l ，m a t h m l ，s m i l 甾。 x m l 是在冈特网时代与j a v a 、c o r b a 等鼍齐观的一个概念。j a v a 解决了 语言实施的同一，c o r b a 解决了通讯协议的同一，x m l 解决了信息表示、 笑联的同一；o o 面向对象是这三者的共同理论基础。万维网接口定义语言 w i d l 就是x m l 与i d l 技术结合的产物。 x m l 是国际标准化组织的标准通用标记语言s g m l 的子集。s g m l 面向请 于b 机设计文档的大规模、长生命周期的信息储存，x m l 则面向短期的临时 数据处理、面向万维网络；二者是相互补充的关系。 x m l 是巴斯克范式b n f 的语言化、标准化、电子化。元素是其基本构成单 位。 l _ 3x q u e r y 简介 x q u e r y 是w 3 c 在q u i i t 语言的基础上改进而成的，目前还处于工作草案的 状态，是一种函数式的查询语言，包含了许多其他查询语言的优点：x q u e r y 吸 收了x p a t h 和x q l 中的路径表达式；x q u e r y 的变量最早出现在x m l q l 语言中； x q u e r y 根据s q l 的s e l e c t f r o m - w h e r e 模式，产生了( f o rl e t ) + 一w h e r e r e t u r n 表达式；x q u e r y 中的函数来源于0 q l 语言。 w 3 c 在制定x m l 查询语言的时候提出了以下几点必须的要求 2 3 ： 有一个易读并且可以用x m l 格式来表示的语法结构 语言应该是说明性的 应该有错误处理机制 协议无关性 对有限的文档定义 要有更新能力 第一点要求查询语言对人机都是友好的，目前的x o u e r y 能很好满足， x q u e r y 本身的可读性很好，而且也有一个可以用x m l 来表示的方法 2 4 。语言 的说明性是说查询语言本身并不唯一决定一个实现算法，x q u e r y 也满足这一点。 协议无关性是指查询语言不应该依赖于其他的协议，目前还不能满足。x o u e r y 对更新和错误的处理也不够。由于这些缺点，w 3 c 没有把x q u e r y 做为正式的规 范提出。 x q u e r y 主要由以下几部分组成，下面逐一说明 路径表达式： 在文档b o o k s x n l l 中查找所有文章的标题 d o e u m e n t ( b o o k s x m i ) l l c b a p t c r l t i t l e 元素构建表达式： 建立一个具有y e a r 属性和t i t l e 子元素的b o o k 元素 fs b y e w ) $ b t i t l e 4 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 语句用来绑定变量， w h e r e 语句进行过滤，最后表达式的结果由r e t u r n 语句生成。f o r 和l e t 语句的区别是，f o r 绑定变量到该子句中每一个结果元素， 而l e t 绑定变量到整个子旬的结果( 可以是一个包含很多元素的 列表) 。 返回a d d i s o n - w e s l e y 出版社所出书的书名和平均价格 f o rs ti nd i s t i n c t ( d o c u m e n t ( 一s x m l ) p r i c e s b o o k t i t l e l l e t $ p ：。a v g ( d o c u m e n t ( ”p r i c e s x m l ”) p r i c c s b o o k t i t l e = $ t p r i c e 、 w h e r e ( d o c u m e n t ( ”b i b x m l 。) b o o k t i t t e - 锶t p u b l i s h e r ) = ”a d d i s o n w e s i e v ” r e t u r n 。 n ：s u l 伊 $ t ) $ p 条件表达式 瓤酾嘲醚， $ d n s m e i f ( e m p t y ( $ b ) ) t h e n i 蚺o t i v e e l s e 1 9 9 1 ) ) 在l o r e l 9 语言中s e l e c t 子句构建元素，匹配模式出现在f r o m 子句中， 而w h e r e 子句即包含匹配又包含过滤条件。在这个查询语句中，b i b 是被查询 文档数据的入口点，f r o m 子句绑定变量b ，t ，y 到满足匹配模式的那些元素， w h e r e 子句选出符合条件的那些元素。 1 4 3x m l q l c o n s t r - i j c t w h e r e b o q k 秽9 学豁 ： a d d i s o n - w e s l e y i n w w w b n c o r n b i b x m l ” s y 1 9 9 1 c o n s t r u c t $ t 一 引占 在一个x l l q l n 7 查询语言中，模式和过滤条件出现在w b e r e 子句中，构 建符出现在c o n s t r u c t 子句中。在这个例子中，w h e r e 子句把所有满足条件的 y e a r 和t i t l e 绑定到变量$ y 和$ t 上，对每一个这样的绑定，内部c o n s t r u c t 子旬生成一个以y e a r 为属性，t i t l e 为子元素的b o o k 元素。而外部c o n s t r u c t 子句将所有b o o k 元素组合起来作为b i b 元素的子元素。 1 4 4y a l t m a k e b i b f * b o o k 【 弦甜f 帮】 t i t l ee 瓤1 1 】 m a t c h ”v 嗍b n c o m m i b 。m l ”w i t h b i b f b o o k 逼洳韶f 嚣y 】 t 琏协霉毫0 暑 在y a t l 1 9 语言中，构建符出现在m a k e 子句中，匹配模式出现在m a t c h 模式子句中，过滤条件出现在w h e r e 子句中。每一个重复元素都以芈为前缀。本 例中，匹配模式为b i b x m l 文档中的一个b i b 元素，它由很多b o o k 元素构成， 每一个b o o k 元素有一个y e a r 属性，一个p u b l i s h e r 元素和一个t i t l e 元素。 w h e r e 子旬选出满足条件的元素，然后m a k e 子句构造结果元素。 d o c u m e n t ( h 弹0 撕1 、h i 七o m ”抛i b b 0 0 k f p u h l i 的酬n 舯铲”a d d i s o n - w e s l e y a n d y e a r 1 9 9 1 在这个x q l 1 8 】查询语句中，模式d o c u m e n t ( ”h t t p ：w w w b n c o m ”) b i b 选出所有输入文档的顶层b i b 元素，对每个b i b 元素都进行过滤。下一个递 归的模式b o o k 选出满足方括号中条件的b i b 的b o o k 予元素，在下一个递归的 模式 y e a rlt i t l e 选出b o o k 元素的y e a r 属性和t i t l e 子元素。x q l 没有元素 构建子句，它的匹配模式表达式决定了查询的结果。在这个例子中，结果为一 个b i b 元素包含满足条件的b o o k 元素，每一个b o o k 元素包含y e a r 属性和t i t l e 元素。 1 5 各个语言的比较以及x q u e r y 的优势 本节中我们对各种查询语言进行一下功能的比较，见图4 ，部分数据参考 文献f 3 1 】。 7 。)_：。 饕 x q u e r y 语占的赍咖实现 l o r e lx m l o lx q l x q u e r y 有特定的数据模型有有无有 支持查询的联接操作有有无有 支持路径表达式有有有有 支持全称量词有无有有 支持条件语句无有无有 有构建新兀素的功能有有无有 支持组的概念有无无有 支持聚集操作有无部分有 支持查询的嵌套有有无有 支持集合操作有部分有有 支持文档的序有有无有 支持排序操作有有无有 支持类型检查有无无有 支持变量有有无有 支持函数有有无 有 支持名字空间无无无有 支持更新语句有无无无 有煳l 格式的语言无无无有 语言的可读性差一般一般好 图4 各种查询语言的比较 由图中可知x q u e r y 有很多优点，而且是w 3 c 正在制定的规范，它的更新 功能也正在制定中，所以以后将是事实上的x m l 查询标准语言，对它的实现非 常必要，本论文的主要工作就是描述实现x q u e r y 语言的算法。 1 6 我们所做的工作和本论文各章组织 我们对x m l 文件查询语言的实现是从数字图书馆开始的，我们用x m l 来 存储各种资源的元信息，通过x m l 的查询语言来取出这种元信息，那时的查询 语言是我们自己定义的，名叫s a v a n n aq l ，可以进行简单的查询，附录a 对 这个语言进行了简单介绍。 自从2 0 0 1 年5 月，w 3 c 推出第一个x q u e r y 语言的草案开始，我们就一 直跟踪它的最新状态，以及它的改进。目前我们实现的系统可以完全解析 x q u e r y 语句，还可以对在内存中的x m l 文档进行x q u e r y 查询。我们还实现 了另一种查询的方式，将x m l 数据拆分放到数据库中，然后对数据库进行查询， 将结果在组装成x m l 格式的数据返回给用户。本论文中将详细讨论这些实现的 算法。 本论文的组织如下：第二章讲述x m l 代数和数据存储的方法：第三章论述 我们实现x q u e r y 的本地存储时使用的算法；第四章论述我们提出的x q u e r y 的 基于关系数据库实现的算法。 8 x m l 代数和存储实现 第二章x m l 代数和存储实现 代数是查询语言的理论基础，而数据模型是代数操作的对象。由于x m l 数 据远比关系数据复杂，x m l 的查询语言1 7 前还没有很好的像关系代数那样的代 数。本章将介绍一下目前比较认可的数据模型和代数。 数据模型由数据的存储方式来体现，这种实现一般都是n a t i r e 的数据存 储。这一章中我们介绍一下基于关系数据库的存储方式。 2 1x m l 代数 这一节介绍文献 2 6 中的关于x m l 的数据模型和代数。 2 1 1x m l 的数据模型 在x m l 的数据模型中，一个x m l 文档被视为一个有向图。这个图中有两类 节点。一类是组成x 札文档的元素，另一类是x m l 文档的数据。每一个x m l 元 素都被赋予一个全局唯一的标识符。文档中的每一个元素都有一个父元素，对 于根元素有一个虚构的父元素。 文档图还包含三种类型的边。第一种是元素关联边，表示元素之间的父子 关系，孩子节点可以是元素或具体的数据。第二种是属性边，联系元索和它属 性的值。第三种是引用边，联系元素和它通过i d r e f ，i d r e f s ，x 1 i n k s ，和u r l s 等引用的元素。 兄弟元素之间的次序由它们和父节点关联的元素关联边的次序来决定，这 个次序就是在文档中元素出现的次序。元素的属性之间是没有次序的。多值引 用的元素之间的次序，由引用边的次序来决定，如同兄弟元素之间的次序。 图中的每个节点和边都有自己的一些属性，可以供代数语言来操作图。下 面对这些属性进行一下简要的说明。 元素节点： v a l u e 返回元素的表示符 t y p e 返回元素的类型( 当前只有元素一种类型) 返回这个节点元素的名称 p a r e n t 返回父节点 r e f e r r e d b y 返回引用本节点的节点集 c h i l d e l e m e n t s 返回源于本节点的所有元素关联边 a t t r i b u t e s 返回源于本节点的所有属性边 r e f e r e n c e s 返回源于本节点的所有引用边 数据节点： t y p e 返_ 回节点的类型( c d a t a ，i d r e f 等) v a l u e 返回书蠢的值 边具有以下属性： p a ，e n t 相关于该边的父节点 c h i l d 相关于该边的子节点 n s e 边的名字( 元素标签名，d a t a ，c o m m e n t 等) t y p e 边的类型( 元素关联，属性，引j _ ) 9 x q u e r y 语；的矗询实现 2 1 2 x m l 的代数 x m l 的代数对一个文档集的数据模型表示进行操作，它应该能够选出满足给 定条件的那些x m l 元素节点。它还应该可以很好的处理x m l 文档的一些独有的特 点： 图结构 类型和图结构的异构性 父子关系和引州关系 次序 同时还要保持一个代数所应有的可优化的特性。代数主要有操作算子组成， 下面将进行详细的介绍。每一个操作都将数据模型上一个输入的图结构变化成另 一个图结构作为下一个操作的输入。 d i i s t i n c t 语法为8 ( e x p r e s s i o n ) ，d i s t i n c t 去除f h e x p r e s s i o n 生成的结果集中的重 复的元素。 u n o r d e r 语法为z ( e x p r e s s i o n ) ，u n o r d e r 操作将e x p r e s s i o n 生成的结果集变为 一个无序的集合，一般和d i s t i n c t 操作一起用，8 ( x ( e x p r e s s i o n ) ) ，以确保生 成的是一个集合。 s i o r t 语法y g z v e u e _ e x p r ( x ) ( e ：e x p r e s s i o n ) ，e x p r e s s i o n 会生成一个节点 集，s o r t 操作用v a l u e _ e x p r 对这个集中的每一个节点求值，在根据求出的值 对相应的节点进行排序。 代数中并不关心各个语种独有的次序问题。 f o l l o w 语法为仲 e d g e t y p e , n a m e ( v e r t e x - e x p r e s s i o n ) 。f o l l o w l 操作提供了路 径遍历的功能。v e r t e x - - e x p r e s s i o n 返回遍历的起始节点集，f o l l o w j 限据 n a m e 和f e d g e t y p e 对这个节点集遍历，并返回满足条件的边的集合。 e d g e t y p e 的类型为元素关联边，属性边和引用边，以及它们之间的组合。 n a m e i 可以是一个有效的边的名字，也可以是一个正则表达式。例如 币( e c ( c h i l d ( c e , b ( c h i l d ( c e , a ( v e r ) ) ) ) ) 这个表达式从v a n 产生的节点集开始依次遍历元素关联边a b 最后定位 于边c 。 n a m e 还可以是正则表达式之间的合集，交集，差集等。如例子 母【e ，d ( c h i l d ( c e , b i c ( c h i l d ( 硝 e , a ( r o o i c ) ) ) ) ) 。 有的时候f o l l o w 算子很可以简写为并1 x p a t h 表达式相似的简单形式： a b 表示f o l l o w e ，b ( a ) ，e 是元素关联边 a b 表示f o l l o w a b ( 丑) ，a 是属性边 a b 表示f o l o w r ，h i ( a ) ，r 是引用边 闭包运算 语法为* f ( x ) ( x ：e x p r e s s i o n ) ，闭包运算以e x p r e s s i o n 求得的结果集为 种子集开始重复运行函数f 多次( 可能无限) 。每次运算后，得出的结果都 1 0 x m l 代数和存储实现 加入种子集，直到最后种子集不在增加时停l e 运算。闭包运算还有一科，形 式为水 厂( ，n j ( j ：e x p r e s s o n ) ，求函数fn 次，或到种子集不在增加为止 ( 严格的说，这不属于闭包运算) 。一个例子为： + 【e 。c 】( 【c h i l d ( 【e 卅( y ) ) 2 】( y ：+ 【c h i i d ( 十【e b ( c h i l d ( 十 e a 1 ( ) ) ) ) 1 ( x ：r 0 0 1 ) ) ) 相当于x p a t h 中的t o o t ( a b ) * # 2 c 以r o o t 元素开始，遍历连续为a ， b 的边多次，然后在向下遍历两层的边，最后求出名为c 的边。 s e l e c t i o n 语法为6 c o n d i t i o n ( e ) ( e ：e x p r e s s i o n ) 。类似于关系代数中的选择算子， 以e x p r e s s i o n 产生的节点集为输入，将满足条件c o n d i t i o n 的节点作为结果输 出。c o n d i t i o n 可以包括标准的比较和布尔运算。看一个例子，选出所有在 今天有订货( o r d e r ) 的顾客( c u s t o m e r ) 的名字( n a m e ) = a ：= 蚍e c u s t o m e r ( * c h i l d ( + e 嗣( x ) ) 1 ( x ：r d o o ) ： b ：= e v a m e ( c h f l d ( 十 e o a t e ( c h f l d ( + e ，o r d e r ( c h i l d ( c ) ) ) ) ) ) = t o d ay ( ) 】( c ：a ) ： c ：= c h i l d ( c ) e n a m e 】( 叻删( b ) ) ) ： 这个查询中变量a 绑定到所有的顾客，变量b 绑定到在今天有订货的顾 客，变量c 求出顾客的名字。 e x i e t e n t i a la n du n i v e r s a lq u a n t i 行c a t o n 存在和全称量词用a n y 和a n 来表示，上一个例子中变量b 的语义为a n y ， 也就是说只要顾客有一个订单在今天就可以了，如果要求顾客的所有订单 都在今天，可以使用全称量词如下 b ：= a a l l ( v a l u e ( c h i d ( 十 e ，d a t e ( c h i l d ( 十 e ，o r d e r ( c h i l d ( c ) ) ) ) ) ) = t o d ay ( ) ) j ( c ：a ) ： j o i n s 语法为( a ：e x p r e s s i o n ) o 【c o n d i t i o n ( a ，b ) ( b ：e x p r e s s i o n ) 。正如关系代