（计算机应用技术专业论文）基于pat代数的xml数据查询优化方法研究.pdf

，百一 ，r ，1 1y1_-1，。， 学校代号：1 0 7 3 1 学号：0 8 2 0 8 1 2 0 3 0 2 2 密级：公开 兰州理工大学硕士学位论文 i i i i ii ii ii i ii ii i i ii if y 18 8 5 7 0 6 基于p a t 代数的x m l 数据查询优化 方法研究 堂僮由请厶娃名；王整 昱哑娃名区驱塑；韭毯金硒究虽 墙差篁僮! 盐簋扭曼通信堂院一一一 童些名塑；让簋扭廛且撞苤 诠室提童旦期i2 q ! l 生q 垒旦q 墨目 论室筌趱目期； 2 q ! ! 生垒耋目煎日 筌避委虽金圭廑；：塑盔盈熬整 一 ， h s t u d yo fx m l d a t aq u e r yo p t i m i z a t i o nm e t h o d b a s e do np a ta l g e b r a b y a n gm i n b e ( n o r t h w e s tn o r m a lu n i v e r s i t y ) 2 0 0 7 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o m p u t e ra p p l i c a t i o nt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f l a n z h o uu n i v e r s i t yo ft e c h n o l o g y s u p e r v i s o r r e s e a r c h e rz h a n g q i u y u m a y , 2 0 1 1 ， ， 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作尹签名：王惫、 日期：z ) 年么月否 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收 录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 日期：2 f 年 日期：研厂年 乡月召 日 石月o 日 臻缈 硕+ 学何论文 曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼鼍曼曼曼曼皇鼍i i i i 一 l, 一 i 曼曼曼曼曼量量璺 目录 摘要i a b s t r a c t i i 插图索引i v 第l 章绪论1 1 1 课题的研究背景和意义1 1 2x m l 查询优化技术研究现状1 1 2 1 国外研究现状2 1 2 2 国内研究现状3 1 3x m l 数据查询的特点3 1 4 存在的缺陷与不足：4 1 5 论文的主要研究内容与主要贡献4 1 6 论文的组织结构与安排5 第2 章x m l 查询优化相关理论基础7 2 1x m l 概述7 2 2x m l 的数据模式8 2 2 1d t d 数据模式8 2 2 2x m ls c h e m a 数据模式9 2 3x m l 的查询语言1 0 2 3 1x p a t h 路径语言1 0 2 3 2x q u e r y 查询语言1 0 2 4x m l 查询优化体系1 1 2 4 1 查询解析1 l 2 4 2 逻辑优化1 2 2 4 3 物理优化1 3 2 4 4 查询执行13 2 5x m l 查询优化技术1 3 2 5 1 基于路径索引的优化技术1 4 2 5 2 基于x m l 数据模式的优化技术1 4 2 6p a t 代数基础1 4 2 7 本章小结l6 第3 章基于x m l 查询的扩展p a t 代数系统研究j 1 7 一 基于p a t 代数的x m l 数据杏询优化方法研究 3 1x m l 关系结点17 3 2p a t 查询等价式19 3 2 1 面向集合的等价式2 0 3 。2 2 基于d t d 约束的等价式2 1 3 2 3 基于特殊x m l 结构特性的等价式2 2 3 4 确定性x m l 查询转化2 4 3 4 1 结构索引2 5 3 4 2 转化规则体系2 6 3 4 本章小结3 2 第4 章基于扩展p a t 代数的优化方法研究3 3 4 1p a t 代数表达式的转化3 4 4 1 1p a t 代数的操作对象3 4 4 1 2p a t 代数的操作范围3 5 4 1 3p a t 代数的具体操作3 5 4 1 4f l o w r 查询语句与p a t 代数表达式的转化3 5 4 2 优化策略研究3 6 4 2 1 结构索引引入策略3 6 4 2 2 语义优化策略3 7 4 3p a t 代数表达式优化一3 9 4 3 1 优化实例3 9 4 3 2 优化性能解析4 0 4 4 本章小结4 1 总结与展望4 2 参考文献4 4 致j 射4 8 附录a 攻读硕士学位期间所发表的学术论文4 9 i i ， 硕十学位论文 摘要 互联网中包含着大量的半结构化的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 a t 代数系统，提出了一种基于p a t 代数的查询优化方法。 论文首先通过对现有x m l 查询优化技术和x m l 数据的查询优化体系进行研究与 分析，提出了一种基于结构索引的查询优化方法。该方法能够缩短查询路径，从而 提高查询效率；然后，通过对p a t 代数系统的查询等价式进行分析，并根据这些等 价式转化方法对p a t 代数进行扩展，结合启发式的思想提出了基于p a t 代数的确定性 转化规则体系以及基于结构索引的规则转化方法。 最后，论文通过使用扩展后的p a t 代数表达式转化规则对x m l 查询表达式进行代 数转化，并结合文中提出的语义优化策略，能够较为合理地清除冗余操作，化简查 询表达式，从而减少了代数操作次数；运用文中提出的索引引入策略，把结构索引 引入到查询表达式代数转化过程中，有效缩短了查询路径。经实例验证与性能分析， 论文提出的查询优化方法能够较为有效地提高了x m l 数据查询的查询效率。 关键词：x m l 代数；p a t 代数；结构索引；查询优化；x m l 数据查询 ， a bs t r a c t ln e r ea r eal a r g en u m b e ro f s e m i s t r u c t u r e dx m ld a t ao nt h ei n t e m e t b e c a u s eo f t h es e m i _ s t r u c t u r e df e a t u r e ，i ti sv e r yd i f f i c u l tt or e t r i e v ed a t aw i t ht h e t r a d i t i o n a lq u e r y o p t i m i z a t i o no fd a t a b a s e t h em e t h o do fd e p e n d i n go na l g e b r a i c s y s t e mt ot r a n s f o 瑚 x m lq u e r ye x p r e s s i o na n d u s i n ga l g e b r a i ct r a n s f o r m a t i o nr u l e st oo p t i m i z et h e e x p r e s s l o nm a k eu so p t i m i z et h eq u e r i e sf o rx m l d a t am o r ee f f e c t i v e l y t h er e s e a r c h m e t h o dh a sb e c o m et h ef o c u so fx m l d a t aq u e r y o p t i m i z a t i o nf i e l da tp r e s e n t t h er e s e a r c ho fx m la l g e b r a c u r r e n t l yf o c u s o nn o r m a l i z i n gx m lq u e r y s 锄a n t l c s ，a n dd on o tc o n s i d e rt h ef a c t o ro f q u e r yo p t i m i z a t i o n b e c a u s et h ea l g e b r ah a s 0 d v i o u s l yp r o c e d u r a lt h i n k i n g ，i ti sh a r dt of u r t h e ro p t i m i z e ，a n ds o l v i n gt h ep r o b l e m o n l yb yt r a v e r s i n g s ot h eq u e r ye f f i c i e n c yi sv e r yl o wa n dt h em e t h o dd o e sn o ts u i tt o t h el a r g e _ s c a l ex m l d a t aq u e r y a f t e rs t u d y i n ga n da n a l y s i z i n gt h ec u 玎e n tx m l d a t a q u e r yo p t i m i z a t i o n ，w eh a v ed r a w e do nt h ee x i s t i n gx m l q u e r yo p t i m i z a t i o n a n du 8 e d t h es e t 。o r i e n t e dp a ta l g e b r a s y s t e m ，a n dt h e np r o p o s e dt h em e t h o do fq u e r y o p t i m i z a t i o nb a s e do np a t a l g e b r a f i r s t l y , t h ee x i s t i n gx m lq u e r yo p t i m i z a t i o na n dt h es y s t e mo fx m l d a t aq u e r y o p t l m i z a t i o nh a v eb e e ns t u d i e da n da n a l y s i z e d ，a n dt h em e t h o do f q u e r yo p t i m i z a t i o n b a s e do nt h es t r u c t u r a li n d e xh a sb e e np r o p o s e d i nt h em e t h o dt h eq u e r y p a t hc a nb e s n o r t 髓a n dt h e n ，w eh a v ea n a l y s i z e dt h eq u e r ye q u i v a l e n t so fp a t a l g e b r as y s t e m ， e x t e n d e dp a t a l g e b r aw i t ht h ee q u i v a l e n t s ，a n dw i t ht h eh e u r i s t i ct h i n k i n gp r o p o s e dt h e s y s t e mo ft h ed e t e r m i n i s t i ct r a n s f o r m a t i o nr u l e s b a s e do np a ta l g e b r aa n dt h e t r a n s f o r m a t i o nm e t h o do ft h er u l e sb a s e do nt h es t r u c t u r a li n d e x a tl a s t ，t h r o u g h u s i n gt h et r a n s f o r m a t i o nr u l e so ft h ee x p a n d e da l g e b r aa n d c o m b i n i n gw i t ht h es e m a n t i co p t i m i z a t i o ns t r a t e g i e so ft h ep a p e r , w et r a n s f o mt h e x m lq u e r ye x p r e s s i o n s s u c c e s s f u l l y t h er e d u n d a n to p e r a t i o n sa r er e m o v e dm o r e r e a s o n a b l ya n dt h eq u e r ye x p r e s s i o n sa r es i m p l i f i e d t h e r e b yt h en u m b e r so f a l g e b r a i c o p e r a t i o n sa r er e d u c e 彤t h eq u e r y p a t hi ss h o r t e n e de f f e c t i v e l yd e p e n d i n go nu s i n gt h e i n t r o d u c t i o ns t r a t e g yo fi n d e xt oi n t r o d u c et h es t r u c t u r a li n d e xi n t ot h ep r o c e s so f t h e a j g e b r a i ct r a n s f o r m a t i o no fq u e r ye x p r e s s i o n s t h r o u g hv a l i d a t i n ga n da n a l y s i z et h e e x a m p l e ，u s i n gt h ep r o p o s e dq u e r yo p t i m i z a t i o nc a ni m p r o v et h ee f f i c i e n c yo fx m l d a t aq u e r ym o r ee f f e c t i v e l y i i ， 硕士学f 7 = 论文 k e yw o r d s ：x m la l g e b r a ；p a ta l g e b r a ；s t r u c t u r a li n d e x ；q u e r yo p t i m i z a t i o n ；q u e r y f o rx m ld a t a i i i i v 硕+ 学位论文 皇曼曼曼曼量曼曼曼皇曼曼曼曼曼曼皇皇曼皇曼曼曼量曼曼皇曼量曼曼皇曼曼曼皇曼曼曼曼曼量曼曼曼! 曼曼曼曼曼曼曼曼曼曼曼曼曼曼皇曼量曼量曼曼曼曼曼曼曼! 鼍曼曼曼曼 。 第1 章绪论 1 1 课题的研究背景和意义 为适应i n t e r n e t 的发展，解决数据的半结构化问题，w 3 c u q l ( w o r l dw i d ew e b c o n s o r t i u m ) 推出了一种新型的w e b 语言x m l ，即可扩展标记语言。它提供了一种标 准化、可扩展的方法，克服了h t m l 不支持非结构数据存储的缺点。目前x m l 语言已 经成为网络上进行信息描述和信息交换的标准，并且被广泛采用到电子商务、电子 图书、异构数据集成和电子政务等领域。 从数据检索的角度来看，x m l 文档中所包含的大量数据可以进行提取和分析， 如何高效检索这些文档的内容变得越来越重要。由于w e b 的数据特性，x m l 文档中所 描述的数据必然是不规范的，也就是所谓的半结构化数据。同时，x m l 的树形结构 模型比关系模型更加复杂，使得x m l 的查询优化空间要比关系模型要大的多口1 。由 于目前对基于x m l 的数据查询优化技术的研究刚刚起步，特别是语法优化和语义优 化的研究还处于探索阶段。因此，研究x m l 数据查询优化技术具有很高的理论价值 和应用价值。 论文将采用面向集合的p a t ( p r a c t i c a la l g e b r at u t o r ) 代数系统对x m l 查询表 达式进行优化处理。p a t 代数理论很早就被提出，但主要应用在文本查询中，由于 x m l 文档与普通的文本文档具有一些类似的性质，因而在x p a t h 结构中能够应用p a t 代数“1 ，p a t 代数系统从此被真正应用至u x m l 查询优化领域。发展到现在，p a t 代数 形成了较为完整的查询代数体系以及基于语义的代数等价式转化方法哺吲，能够对 x q u e r y 表达式嵌套语句进行较为准确的代数转化，从而进行优化处理，但不会改变 原嵌套表达式的语义。因此，采用p a t 代数系统对x m l 数据进行查询优化具有很高的 实用性与研究价值。 1 2x m l 查询优化技术研究现状 论文在研究了基于x m l 数据查询优化技术的相关文献后，总结出四种目前主要 的x m l 数据库查询优化方法如下所示： 1 基于路径查询表达式的优化方法。在该方法中，优化规则是根据x m l 文档的 模式信息产生的，然后通过使用优化规则对路径表示式进行重写。s p h i n x 口1 是第一 个利用x m l 文档的模式信息对x m l 文档中的数据进行查询检索的方法。 基于p a t 代数的x m l 数据奇询优化方法研究 2 利用x m l 查询代数的进行优化。该方法将建立一个查询代数，并且定义出有 关查询的各种代数操作，提出基于这些代数操作的表达式转化规则，利用这些转化 规则来实现查询优化。这个方面也将是论文研究的重点。 3 查询最小化。查询最小化就是找出与输入查询等价的规模最小的查询，而等 价问题又可以转化为查询的包含问题。查询最小化也会用到查询代数系统，因此也 属于对查询代数的研究。 4 查询结构连接次序优化。在x m l 查询中结构连接操作较为常见，有效优化各 种操作的连接次序能够较好得缩小查询空间。该研究主要分为两种方法，它们分别 是估计连接代价方法哺。9 1 和搜寻枚举空间策略n 们。 1 2 1 国外研究现状 目前国外对基于x m l 查询代数的优化研究中比较有代表性的有： 文献 1 1 提出了一个x m l 查询代数标准。该标准把x m l 文档转化为有向标记图， 用五元组g ( v ，e ，a ，r ，o ) 来表示该有向标记图，并且规定了选择、导航、构造、连接 等操作，而有向标记图的遍历由导航操作提供。 w o o d 最早提出t x p a t h 路径最小化方法n 羽。该方法把x p a t h 表达式转化为合取范 式，使得x p a t h 等价性检查的复杂度类似于对合取范式的等价性检查，从而把x p a t h 最小化的问题转化为合取范式最小化的问题。 m a r y 等人提出了基于简化的x s l t 数据模型3 1 钔。该方法增加了文档树中的引用 结点，合并了属性结点和元素结点，并且删除了文档树中不利于查询优化的注释结 点。 d a ns u c i u 在文献 1 5 中提出根据x p a t h 构造n f a 自动机，然后在n f a 自动机上执 行确定性操作。由于在任意时刻系统的运行只有一个状态，使得系统处理效率得到 了一定的提高。 在t i m b e r 数据库n 6 1 中，通过使用t a x 代数n 7 1 把x m l 数据模式看作树，把x m l 查询语 句也看作树，在模式树与查询树二者之间做模式匹配，从而得到满足查询条件的结 果树集合。 s t a n d f o r d 大学开发的l o r e 系统n 8 。2 们针对系统本身提供的访问操作和查询操 作，提出了相应的物理代数、逻辑代数以及相应的表达式转换规则。 x a l 心基于集合的概念提出了逻辑代数的三种相关操作，它们分别是元操作、 抽取操作以及构造操作，并且为各种代数操作提供了一组启发式的表达式转换规 则。 其它如x o m 代数c 2 2 该代数具有较为完整的操作集，但它不支持表达式优化； o p a l 代数心3 1 是一种基于半结构化的数据模型，该代数将有穷状态自动机理论用于查 硕十学位论文 询计划的生成过程；还有s a l 等瞳4 。冽。根据查询代数的操作方式，可将查询代数分 为导航代数和面向的集合代数两种。导航代数中的操作对象是单个的数据，这种方 法不利于进一步的优化；而面向集合的代数的操作对象是某种类型集合，虽然这种 方法的操作对象具有很好的优化基础，但可能会造成数据顺序的丢失。 论文研究中将要采用的面向集合的p a t ( p r a c t i c a la l g e b r at u t o r ) 代数系统是一 套较为完整的查询代数标准，它最早被用在文本检索技术中心 。由于在检索过程中 结合了词汇检索、上下文检索、逻辑检索以及频度检索等检索方法，并且通过它能 够对文档定义结构，然后在查询操作中可以使用这些结构，因此使用p a t 代数检索 文本文档更为高效。文献 2 8 中提出了在x m l 优化过程中进行代数转化时需要用到 的p a t 代数等价式，通过使用这些等价式能够对x m l 查询表达式进行代数优化。由于 等价式转化是双向的，虽然查询效率得到了提高，但对于x m l 查询表达式使用等价 式进行代数转化具有不确定性，优化效果会受到一定程度的影响。 172 2 国内研究现状 在国内，基于x m l 查询代数的优化研究中比较有代表性的有： 罗道锋等人设计了一种新的x m l 查询代数o r i e n t x a 乜引。在o r i e n t x a 代数中，模 式树被扩展为源模式树以及输出模式树，并且把x m l 树的集合做为操作符的处理对 象。 张剑妹等人提出了一个x m l 结构完整性约束体系n 叫。这个体系描述了x m l 文档中 结点或路径之间的五种结构关系，包括路径蕴涵、路径同现、路径互斥、必需性包 含和排它性包含，并且给出了这些结构完整性约束的语法和语义定义。 邓梦浪等人提出两集合间的双向映射规则口，从而实现关系模式至u x m ls c h e m a 的转化。 路燕等人提出了d b x i ( d t db a s e dx m li n d e x i n g ) 方法b 剀，该方法利用了d t d 模 式信息对x m l 查询表达式进行优化，大大减小了查询空间，从而提高了查询效率。 孙伟等人提出了一种e t a 代数系统以及相应的查询优化策略口引，主要包括抽取 下移与分合、选择谓词下移、抽取替代自连接以及x m l 函数依赖等查询优化方法。 赵威等人在r t a 代数基础上，通过对原子数据采用简单操作，对列表类型采用结 构递归操作，并且定义出x q u e r y 至u r t a 代数的转换方法，将x m l 查询表达式通过等价 式变换规则转化为代数表达式口钔。 1 3x m l 数据查询的特点 目前，虽然关系数据库的查询研究已取得一定的成果，但由于x m l 数据的半结 基于p a t 代数的x m l 数据查询优化方法研究 构化特点，使得x m l 数据查询研究比关系数据库查询研究要复杂得多。因此，在研 究x m l 查询之前首先要了解x m l 数据的特点和x m l 查询的特点。 与传统的关系数据库中的数据相比，x m l 数据具有下面三个特点： 1 x m l 数据具有自描述性，结构与内容相互混杂在一起； 2 x m l 数据具有较为完整的嵌套层次结构； 3 x m l 数据具有有序性。 与传统的查询语句相比，x m l 查询具有下面三个特点： 1 查询的核心语句是长路径表达式，并且包含多个分支路径； 2 查询表达式具有嵌套结构，条件判断嵌套常出现在查询表达式中； 3 查询路径中包含很多不确定因素，例如查询对象以及结果类型不确定。 1 4 存在的缺陷与不足 早期对x m l 代数的研究主要集中在x m l 查询语义的规范化，而没有考虑到查询优 化相关因素；加之这些代数程序化思想过于明显，要进行进一步优化非常困难，只 能通过遍历x m l 树进行查询，查询效率非常低，对于大规模x m l 数据的查询需求很不 适用。而基于集合论提出的一些面向集合的代数，具有很好的代数优化基础。因此， 目前对于查询优化的研究也多以面向集合的代数为背景，但也存在一些问题口副。 1 查询表达式的嵌套问题。在使用面向集合的代数将嵌套查询转换为逻辑树的 同时，不可避免地引入了嵌套结构非嵌套化的问题。尽管在关系数据库中有一些优 化方法可以借鉴，但由于x m l 数据的半结构化特性，这个问题同样难以解决。 2 x m l 数据的有序性问题。目前的一些较为经典的处理连接算法，如排序连接、 h a s h 连接等，使用这些算法会打乱结点的顺序。因此，在连接完成后需要对结点重 新进行排序操作，而进行结点排序操作将会降低查询效率。 3 不同的代数标准。现在已经出现了很多x m l 查询代数标准，但这些标准风格 迥异，很难有相通性，而对执行方法的研究也处在起步阶段，不能形成完整的x m l 查询代数体系。 1 5 论文的主要研究内容与主要贡献 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 a t 代数系统，从而把x m l 查 询语句转换为p a t 表达式，应用优化策略对p a t 表达式进行优化处理，从而提高了查 4 硕十学位论文 询效率。 论文的主要研究内容包括以下几个方面： 1 对现有x m l 代数系统进行研究，分析了现有x m l 代数的特点和相应的查询优化 方法。 2 对基于路径索引的优化技术和基于模式的优化技术进行研究，分析了它们的 优化思想以及优缺点。 3 对p a t 代数系统进行研究，分析了x m l 关系结点以及基于p a t 代数的等价式转 化方法。 4 对结构索引进行研究，分析了x m l 的特性结构以及索引的引入时机和方式。 5 以“论文集的x m l 文档为例，把输入的查询表达式首先转化为p a t 代数表达 式，然后通过论文提出的转化规则以及x m l 查询优化方法进行表达式转化，从而验 证了通过扩展p a t 代数系统进行x m l 查询优化的有效性。 论文的主要贡献包括以下几个方面： 1 对p a t 代数进行扩展，提出了基于确定性转化的p a t 代数转化规则体系，并且 定义了扩展后的p a t 代数对应于x m l 查询优化的操作符、操作对象以及操作范围。 ， 2 通过对基于路径索引的优化技术和基于模式的优化技术的研究，提出了基于 结构索引的优化策略以及索引引入方法。 3 结合基于启发式思想和基于结构索引的优化思想，提出了一种新的语义优化 策略，从而提高了查询效率。 1 6 论文的组织结构与安排 论文共分为四章，各章的内容简要介绍如下： 在第l 章中，首先介绍了x m l 数据库查询优化的研究背景及研究意义；然后根据 相关文献重点介绍了x m l 查询优化以及x m l 查询代数的国内外研究现状，并且总结出 现有研究中的不足；最后介绍了论文的主要研究工作的内容。 在第2 章中，首先从两个方面介绍了x m l 的相关基础理论，它们分别是x m l 的数 据模式以及x m l 的查询语言；然后介绍了有关x m l 查询优化的相关理论，阐述了x m l 数据查询的特点、x m l 查询体系以及目前较为典型的x m l 查询优化技术；最后介绍了 p a t 代数的基础知识。 在第3 章中，首先阐述了x m l 关系结点的基本特点与相关性质，研究了基于p a t 代数的查询等价式；然后根据这些等价式对p a t 代数进行扩展，结合确定性转化的 思想提出了基于p a t 代数的确定性转化规则体系以及基于结构索引的规则转化方 法。 在第4 章中，首先定义了查询表达式转化为p a t 代数表达式的操作对象、操作范 5 基丁p a t 代数的x m l 数据有询优化方法研究 围以及操作符，并且把具体的f l o w r 查询语句转化为p a t 代数表达式；然后对优化策 略进行研究，提出了索引引入策略以及语义优化策略，并且根据这两种优化策略， 运用在前一章中提出的表达式转化规则，对具体的p a t 代数表达式进行优化处理， 并对优化后的p a t 代数表达式进行了简单的性能解析。 最后，对论文中的研究工作进行了较为全面的总结，指出研究中的不足点，并 为下一阶段将要进行的后续工作进行了简要的阐述。 6 硕+ 学位论文 第2 章x m l 查询优化相关理论基础 2 1x m l 概述 x m l 语言目前已经成为w e b 上进行数据表示与数据交换的标准，通过它可以达到 信息共享的目的，其主要作用是：1 ) x m l 作为一种w e b 上的元标记语言，能够通过它 定义出各种实例标记语言；2 ) x m l 作为一种信息交换语言，使得w e b 上的各种异构数 据能够进行数据交换与共享。它不仅可以满足日益增长的网络应用需求，还能保证 交互操作具有较高的可靠性。正是由于x m l 语言具有数据和表现相分离的特性，才 使得它成为了互联网中进行数据交换的媒介。x m l 语言具有如下四个特点： 1 半结构化 用户可以通过x m l 数据的模式信息自由地定义x m l 文档的数据结构、元素类型以 及相应的语法，并且能够对标记进行增加或删除。x m l 文档可以利用标记中所含的 语义信息，将w e b 上大量的异构数据集成在一起，并且还可以使用不同的样式进行 显示。 2 自描述性 由于x m l 文档通常能够对文档类型进行声明，因而x m l 文档具有自描述性。这种 自描述性决定了x m l 表示数据的方式独立于应用系统。因此，x m l 文档被看作是数据 的文档化和文档的数据库化。 3 可扩展性 用户可以定义和使用有助于理解的标记。在各个行业领域，企业可以用x m l 语 言定义出适用于自己行业的标记语言，从而有助于行业内部进行数据共享与交换。 4 灵活性 x m l 具有结构化的数据表示方式，从而使得数据表示形式与用户界面相分离， 这样就使得w e b 中许多较为先进的功能在x m l 环境下更容易实现。 如图2 1 所示，该x m l 文档描述了出版物信息。p u b 是根元素，一个x m l 文档只能 有一个根元素。每个b o o k 元素包含一个t i t l e 子元素、一个p r i c e 子元素和至少一个 a u t h o r 子元素，y e a r 为b o o k 的元素属性。2 0 0 0 、d a t a b a s es y s t e mc o n c e p t s 、2 6 5 0 是属性或元素的值。我们从该文档中可以看出它既包含了数据的内容信息，同时又 包含了数据的结构信息。但这种结构信息并不完整，比如从x m l 文档中我们不能知 道元素p r i c e 的值2 6 5 0 是一个字符串还是一个数值。因此，我们通过x m l 文档不能 准确知道某个标签的数据类型，这也就是x m l 数据的半结构化特性之所在。 7 基于p a t 代数的x m l 数据杏询优化方法研究 2 2x m l 的数据模式 图2 1 网上购书系统x m l 文档 x m l 数据的模式信息是关于标记的语法规则，模式信息中包含了对x m l 文档结构 的定义。为了验证一个x m l 文档的有效性，必须要通过模式信息明确该文档必须遵 循什么样的文档结构。在模式信息中不仅定义了x m l 文档中所定义的元素顺序和元 素嵌套关系的内容模型，而且还定义了文档中每个元素的数据类型。x m l 的数据模 式主要包括d t d 与x m ls c h e m a 两种。 2 2 1o i l ) 数据模式 d t d 数据模式是一种基于正则表达式的x m l 数据模式，它定义了文档的逻辑结 构，可用来描述x m l 文档的语法和语义信息。d t d 定义了x m l 文档中的元素类型、属 性等信 外部。 文档。 的一致 硕+ 学位论文 ! e l e m e n ta u t h o r ( n a m e ! e l e m e n tt i t l e ( # p c d a t a p ! e l e m e n tp r i c e ( # p c d a t a p 图2 2 网上购书系统d t d 文档 d t d 数据模式是近几年来x m l 技术领域使用最为广泛的一种数据模式，虽然d t d 在定义元素类型等方面能够给用户带来极大的便利，但同时d t d 数据模式也存在着 许多不足，例如d t d 是基于正则表达式的数据模式，描述能力非常有限；d t d 的约束 能力不足，我们无法通过d t d 对x m l 文档做出非常精确的语义限制；o t d 文档结构化 程度不高，重复利用价值相对较低；d t d 没有使用x m l 语言作为描述手段，不能做相 应扩展。 2 2 2x m ls c h e m a 数据模式 x m ls c h e m a 是在2 0 0 1 年5 月由w 3 c 正式发布的模式标准，由于它弥补了d t d 的诸 多不足，已经取代d t d 成为首选x m l 环境下的建模工具。x m ls c h e m a 由提前规定的 x m l 元素和属性所创建，这些元素和属性定义了文档的内容模型和数据结构。因为 x m ls c h e m a 本身是基于x m l 的，所以用于定义x m l 文档的结构集合是可扩展的。 数据模式必须以某种格式来表示，d t d 的格式与x m l 格式完全不同，而x m l s c h e m a 的格式与x m l 的格式是完全相同的。x m ls c h e m a 与x m l 在格式上的相似性给用 户带来了诸多便利，主要有以下几个方面： 1 用户不必为了理解x m ls c h e m a 而重新学习，从而节省了大量的时间。 2 x m ls c h e m a 继承了x m l 文档的自描述性和可扩展性，从而使得x m ls c h e m a 同x m l 文档一样具有很好的可读性和灵活性。 3 由于s c h e m a 文档的格式完全与x m l 一样，因此我们可以把x m l 文档与s c h e m a 文档存储在一起，从而方便了存储管理。 4 s c h e m a 可以用于进行x m l 数据交换的应用系统中，使得在异构数据源之间进 行模式交换更加方便。 9 基于p a t 代数的x m l 数据奄询优化方法研究 2 3x m l 的查询语言 x m l 查询语言中包含很多原型语言，h l x m lq l 、x q l 、x m lg l 、q u i i t 和x q u e r y 等，这些查询语言各有优缺点。w 3 c 组织提出的x q u e r y 查询语言是一种最新的x m l 查询语言标准，它继承了现有的x m l 查询语言的诸多优点，已成为目前大家公认的 x m l 查询语言标准。由于x p a t h 是x q u e r y 的核心组成部分，这里将重点介绍x p a t h 与 x q u e r y 。 2 3 1x p a t h 路径语言 x p a t h 刚把整个x m l 文档看成树，为我们提供了查询x m l 文档和其它文档的通用 机制。x p a t h 语言定义了如何在x m l 文档中进行类型匹配和精确定位。路径表达式是 x p a t h 中最重要的表达式，通过路径表达式我们能够选择出满足表达式定义的结点 集合。x p a t h 通过正则路径表达式来进行x m l 文档的提取和匹配等操作，每个正则路 径表达式都可以等价地转换为模式树。 正则路径表达式定义如下： q ：= 占i 彳iq qiq u qjq qq 木iq g 】 q ：_ qiq t e x t ( ) = c i1 qq 人qq vq 其中，g 表示路径为空，u 表示连接操作，表示孩子，表示祖先后代，木表 示闭包关系， q 表示条件，q 为正则表达式，c 为字符串常量，八、v 、_ 1 分别为 布尔表达式与、或、非。在x p a t h 语法中，通过一系列的匹配规则来实现查询。 路径匹配中主要有以下两种路径操作： 1 ) 用“表示结点之间的父子关系，如a b 表示“a ”的子结点为“b ”，并 且“a 表示路径的根结点。 2 ) 用“表示结点之间的祖先后代关系，如“a e ”表示所有以“a ”为祖先 结点的e 元素。 2 3 2x q u e