（计算机软件与理论专业论文）网络环境下xpath查询集冗余去除的研究.pdf

山东大学硕士学位论文 摘要 由于舭数据具有自描述特点，可以支持用户自定义的标记，符合h l t 锄e t 上数据描述和存储的需求，所以。正在逐渐成为h l t e m e t 上数据表示和数据 交换的实际标准。随着其规模和复杂性的快速增长，以x 池格式表示和存储的 数据得到了h l t e m e t 领域和数据库领域研究人员的重视。i n t e m e t 上的应用对儿 数据的查询、定位和获取的需求不断增加，也引发了对x 地数据进行合理存储 和快速查询的要求。 随着舭成为目前信息交换和表示的标准，x m 【数据库的应用也变得十 分广泛，在所有儿数据库应用中，儿的相关查询占主要地位，尤其网络 方面也存在多种儿数据库查询的应用。通常情况下，在帆数据库网络查 询模式中客户端向远程皿数据库所在的服务器端提交一个儿查询，服务 器端查询后，通过网络返回给客户端查询的结果。 网络环境下的舳数据库查询应用，已存在多种优化技术，如查询重写， 语义缓存。多种优化技术均是为了加快查询的响应速度或者减少查询的网络流 量。不同于现有的工作，本文从种新的角度对舭数据库网络查询进行优化， 使用了一种新的优化技术，来减少网络流量，相关两个或者多个查询之间往往存 在冗余，舭的树形机构更是加重了这种冗余的存在，所以在本文中，通过x p a m 查询集冗余去除一去除用户提交的两个或者多个关联x p a 血查询集合查询结果 内存在的冗余来优化网络流量。 本文首先介绍了龇，x p a 吐1 查询的树模式，x 池数据库查询网络应用方 面相关概念和知识。接着，对目前儿数据库网络查询模式中存在的几种优化 技术：语义缓存，利用物化视图进行查询重写等进行了详细的讲解，并与本文提 出的冗余去除技术进行了比较，指出了其相同点和不同点，阐述了本文使用的优 化技术的创新之处。 文章主体部分给出了自主设计的黜查询集冗余去除系统的框架，讲解了 框架中各个模块的功能，框架的主体部分采用文中的冗余去除算法。a m 查询 集冗余去除算法也是本文的主体部分，针对简单和带谓词的两种类型a m 查询 山东大学硕士学位论文 集对算法进行了讲述：先通过实例阐述算法，再对相关的结论进行了证明。其中， 算法对存在谓词分支的x p a ：吐l 查询集，利用了a _ t h 查询树模式进行改进。 系统对原有a t l l 查询集冗余去除的解决方案提出了改进，引入了查询相关 性判断模块和d ，r d 判断模块，后者利用d ，r d 树对查询集在不同x m l 文档结构 下的冗余度进行评估，并在算法中权衡选择网络流量和，a t h 查询复杂度，使之 更能满足用户实际需求。最后，文章通过实验对算法相关的结论进行了验证，通 过分析试验结果指出了算法优化和扩展的先进性。 本文所做的工作对于当前网络流量仍占相关考核项重要地位的x 池数据库 网络查询模式应用有着重要意义，尤其是对某些依据网络流量进行计费的网络 x 地数据库应用。 关键词：x p a t h ；查询集；冗余去除；x p a t h 树模式；d t d 树 i i 山东大学硕士学位论文 a b s t r a c t xmi ，d a t ai ss e l f d e s c r i b e d ，c 狮s 印p o r t 憾e r d e f r m e dm a r k e r s 锄dm e e t 也en e e d o ft h ed a t ad e s c r i 砸o n 觚ds t o r a g eo nn l eh l t e m e t s ox m l 掣a d u a j l yb e c o m 髓t 量1 e a c n l a ls t a n d a r do ft l l ed a ：t ad e s c r i p t i o n 锄de x c h a n g eo nt 量1 eh l t e m e t w i mt h er a p i d g r o w 吐lo fi t ss i z e 髓dc 0 i n p l e x i 锣，t h ed a t ad e s c r i b e d 锄ds t o r e di nx m l f o m l a th 嬲 砒仃a c t e dm ea ：t t e n 石o no fr e s e a r c h e r si nt h ef i e l do fh l t e m e ta n dd a t a b a s ef i e l d s t h e d e m a l l do fxm 【。d a t aq u e 猡i n g ，l o c 撕n ga 1 1 da c c e s s i n gi nm ea p p l i c 撕o no fm e h l t e m e ti n c r e a s e s ，锄da l s ol e a d st 1 1 er e q u e s to fx m ld a t a sr e 嬲0 n a b l e 哟r a g e 肌d f 如tq u e r y w i 血x 砌lb e c 0 1 1 1 i n gt 1 1 es t 狮d a r do fi n f o n i l a t i o ne x c h a i l 百n ga i l dd e s 嘶曲衄， t l l e v 几d a t a b 嬲e 印p l i c 撕o n sh a v eb e c o m ev e 巧e ) 【t e n s i v e h la l lx m l d a t a b a s e a p p l i c a t i o n s ，t 量l ex m lq u e 巧a u c c o u n t e df o rad o i n i n a n tp o s i 缸o n ；e s p e c i a l l ym e r e 盯e a l s 0av 撕e 锣o fx m ld a t a b 弱eq u e 巧a p p l i c 撕o n si nm en e t v 旧r ke n 、，i r o n m t u n d e r n o 衄a jc i r c 眦i l s t a i l c e s ，t 量l ec l i e n ts u b r i l i t sax m lq u e 秽t oas e r v e r s i d eo ft l l er e m o t e x n 几d a t a b 嬲ei 1 1 l ex ，d a t a b 弱eq u e 巧i n gm o d e lf o rt l l en e t v v o r k ，t l l es e r v e r - s i d e q u e 巧a n dr e t u m sm er e s u l t so fi n q u i r i e st 0 l ec l i e n tm r o u 曲t 量l en e 佃o r k t h e r eh a sb e e nm u l t i p l eo p t i t n i 撕o nt e c h n i q u e smt h ea p p l i c a t i o no fq u e 可i n g xmld a t a b 嬲ei n 血en 嘶v o r ke n 啊r o n m e n t ，s u c h 舔：q u e 巧r e 疵i n g ，s 锄锄t i c c a c h i n gt e c i u l o l o 影av 丽e 锣0 fo 皿i n j z 撕o nt e c h n i q u e si si no r d e rt 0s p e e du pt l l e o r 幻r e d u c et h en e t w o r kt r a f j c i c d i 疏r e n tf - r o me x i s t i n g w o r k ，t 量l ep a p e ro 砸l i l i z e sm e 舳d a t a b a s eq u e r ) ri nn e t w o r ke n v i r o m e n tf i r o ma n e wp e r s p e 甜v e ；w eu s ean e w0 p t i r n i z 撕0 nt e c h n i q u et or e d u c en e t 、7 v o r k 仃a m c ， n 锄e l y ，b yr e m o v i i l gr e d u n d a l l c yf o r a t hs e t t 0r 锄o v er e d u n d a n c yi nt w o o r m o r er e l a t e de n q u i r i e s 黜q u e 巧r e s u ns e t st 0o 皿i i l i z en e 铆o r k 仃a f f i c i i l “sp a p e r ，w ei n 仃o d u c et l l ex m 。，) ( p a t hq u e 丐t r e em o d e l ，x m l 妣a b 嬲e q u 唧n e t v 旧r ka p p l i c a t i o n s 锄dr e l a t e dc o n c 印t s 锄dk n o 谢e 电ef i r s y t h 鸭w e 砷的d l l c ei i ld e t a i ls e v e r a lo p t i i l l i z 撕o nt e c h n o l o 百e si nm ec u 玎e n tm o d e lf o r l d a t a b 嬲en 酿v o r kq u e 巧印p l i c 撕o n s ：s e m a n h cc a c h e ，t 量l eq u e 巧r e w r i 6 n gu s i n go fa i i i 山东大学硕士学位论文 m a t e r i a l i z e dv i e wa n ds 0o n ，a n dc o m p a r e dm e m 谢mm er e d u i l d a n 锣r e m o v a l t e c h n o l o 舒i nm i sp a p e r w ep o i n t e do u t 也e i rs i 耐l a r i t i e s a i l dc i i 船r 肌c e s 锄d d e s c 曲e dm ei 衄o v 撕o no fo p t i r i l i z 撕0 nt e c l l i l o l o 器i n “sp a p e r h l 锄sp a p e rw ei n 仃o d u c e s 锄义p 砒s e tr e d u i l d a i l c yr e m o 、，i n g $ s t e m 锄di t s f r a m e w o r k ，e x | p l a i nm ef u n c t i o no fe a c hm o d u l ei nm ef r a m e w o r k ，m em a i np a r to f t h e 行锄e w o r ki sm er e d m d a i l c yr e m o v i n ga 1 9 0 r i t h m so ft h i sp a p e r r e d u n d a n c y r e m o v a la l g o r i t h mo fx p a 1s e ti s 恤em e m eo fm i sp a p e r 1 1 l i sp a p e r ( 1 e s c r i b e dm e a l g o r i t l l m 、) v i n l 铆。够p e so fx p a t h ：m es i m p l e 锄dn l ec o m p l e xx p 劬s e t 、7 l ，i 吐l p r e d i c a t e s i tf i r s t l ye ) ( p l a i n e dn l ea l g o r i l mm r o u 曲e ) 【锄p l 箦，锄dt l l e np r 0 v e dn l e r e l e v 锄tc o n c l u s i o n s t h ea l g o r i t l l 】 1 1u s e s a t ht r e ep 毗e mt 0o 曲i n i z et 量l ei n s t a l l c e o fc o n l p l e xx p 础s e t 、蕊t hp r e d i c a f e s w ei m p r o v e l eo r i g i n a lr e d u n d a l l c yr e i n o v 面s o l 埘o n sb yi m p o n i n gm e 朗q u i r i e sr e l a t e de s t i m a t em o d l d ea n d 廿l ed t d e s t i m a t em o d l d e t h el a s t0 n eu s e s d t dt r e et 0 嬲s e s sr e d 吼d a l l c yi nd i f f e r e n tx m ld o c 啪e n ts c n i c t i l r ea i l db a l a i l c e l e n e t w o r kf l o wa n dx p a me n q u i r i e sc o m p l e ) 【i 够i n 吐l ea l g o r i n l mt 0m e e tu s e r s n e e d s b e t t e r f i n a l l y ，t 1 1 ep a p e rv 丽f i e dm er e l a t e dc o n c l u s i o n so fm ea 1 9 0 r i m mb y e 冲e r i m e n t s 趾dp o i n t e do u t 也ea d v a n c e dn 锨鹏o f 吐l ea 1 9 0 r i t h m so p t i 疵z a 蛀o na n d e 冲a 1 1 s i o nb ya 1 1 a l y 五n gt e s tr e s u l t s t h ew o r kd o n ei n “sp a p e rh a s 锄i m p o r t a n ts i 驴i f i c a n c ef o rc u 玎e n tm e 舢 d a t a b 嬲en 咖r kr n o d e li nw h i c hm en 咖r kt r a f 伍cs 缸1 1p l a y sa ni m p o r t 趾tr o l e ， e s p e c i a l l yf o rs o m eo fb i l l i n gx n 几d a t a b 嬲e 印p l i c a t i o n so nt l l eb a s i so ft h en e t w o r k t r a f ! f i c k e y w o r d s ：) ( p a t h ；q u e r ys e t ；r e d u n d 粕c yr e m o v a l ；x p a t hp a t t e r n ；d t dt r e e 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：盆支蘼 日期：些鲨：生! 互 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：盥塾垡扛导师签名： 山东大学硕士学位论文 1 1 背景介绍 第一章绪论 由于舭数据具有自描述特点，可以支持用户自定义的标记，符合i n t e m e t 上数据描述和存储的需求，所以近年来h l t e m e t 上信息的表示和存储越来越多地 向v 几格式迁移，) 几也正在逐渐成为h l t e m e t 上数据表示和数据交换的实际 标准。随着其规模和复杂性的快速增长，以帆格式表示和存储的数据得到了 h 1 t e m e t 领域和数据库领域研究人员的重视。i i l t e m e t 上的应用对v 几数据的查 询、定位和获取的需求不断增加，也引发了对儿数据进行合理存储和快速查 询的要求。 随着舳成为目前信息交换和表示的标准，x m i 数据库的应用也变得十 分广泛，所有儿数据库应用中帆查询占了主要地位，尤其在网络方面也 存在多种x 池查询的应用。通常情况下，在网络x 池数据库查询模式中客户 端向远程) ( 】帆数据库所在的服务器端提交一个x 池查询，服务器端查询后， 通过网络返回给客户端查询的舳文档片段形式的结果。 订l 的查询技术主要是使用，a ：1 1 1 【l 】，x q u e 哆嘲等v 几查询语言进行查询， 对于x 池数据库查询网络应用，考虑到查询响应速度的优化和查询结果在网络 流量减少方面的需求，存在着不同的查询优化方案及相关的算法。 目前帆数据库网络查询模式及应用下已经存在大量相关优化技术，包括 查询重写3 ，4 ，5 ，6 1 ，即在中间代理层使用已存的物化舳查询视图来应答舳查 询，从而减少了直接访问数据库的频率，提高查询的效率；而客户端则可以使用 语义缓存技术川，查询之前先从缓存区中查找是否存在匹配的结果，如果存在， 则不用再提交查询，直接从缓存中提取查询结果，减少网络的传输量，加快查询 的响应速度。 上述技术一般是用在单个，a d l 查询的情况，服务器端接收到此查询后，配 合利用已存儿查询片段，回答此查询，除了上述技术，还可以采用其他技术 进行优化，例如本文中即将讨论的技术：可以对客户端在最近一段时间内提交的 两个或者多个相关的a 血查询进行重写优化，减少查询结果集内可能存在的由 山东大学硕士学位论文 于查询关联造成的冗余，在最大程度上减少要传输的网络流量。 1 2 国内外研究现状 上文指出的查询重写及语义缓存等技术，由于其对网络环境下儿查询优 化的重要理论研究意义及应用价值，国内外许多人士及文章对其进行了深入的研 究。在关系数据库上两种技术已经十分成熟，扩展到皿数据库查询时，可以 借鉴关系数据库方面的技术和经验。 目前国内外对于查询重写做了大量的研究，无论在关系数据库还是x m l 数据 库都已经有了一定的研究成果，已经能够处理多种类型的查询，在文献 8 ，9 中 论述了关系数据查询的重写；文献 1 0 ，1 1 研究了如何重写含有聚集函数的查询； 文献 1 2 论述了递归查询的重写；文献 1 3 ，1 4 论述了半结构化数据查询重写； 文献 1 5 论述了正则路径表达式的查询重写。文献 1 6 使用模式树来解析 x q u e 哆查询语句，将查询频率高的结点放在物化视图中，并使用查询代数树来 表示用户的查询和物化视图，利用物化视图和用户查询的交叉部分，直接从物化 视图中获取用户的查询内容，还给出了模式树的匹配算法。 语义缓存最早也在关系模型中被广泛研究【1 7 1 。由于其灵活性，语义缓存在 x m l 查询缓存中也开始受到人们的关注nh r i s t i d i s 和p e 仃o p o u l o s 提出了一个 压缩结构m i t ( m o d i f i e dh l c o m p l e t et r e e ) 用来表示沮。查询的语义区域【1 8 】。 a c e x q 1 9 】是一个基于x q u e 珂的语义缓存系统，作者讨论了怎样判断一个新查 询是否包含在缓存查询中以及怎样回写与缓存查询一致的新查询。在文献 2 0 】中 c h e ne ta l 考虑使用缓存中己存x q u e 巧查询来回答新的查询。在文献【2 1 】中y 抽g e ta l 为了回答新的查询挖掘频繁子树模式来缓存他们的结果。在文献 2 2 】中，作 者考虑使用前缀选择查询，它们也可以用一棵树表示。 本文要讨论的利用x p a i i l 查询集的冗余去除进行查询结果的优化，从一种新 的角度考虑查询的优化，此技术目前国内外研究的比较少，文献【2 3 】中作者已进 行了一些理论研究，使用自动机产生x p a 吐l 查询集冗余去除算法。 1 3 论文主要工作和组织结构 本文的查询重写技术参考了上述查询重写，物化视图，语义缓存等方面已有 2 山东大学硕士学位论文 的优化技术和算法，基于相关文献 2 3 】中的础查询集冗余去除问题的对其算 法进行了扩展和改进，相关文献的算法在减少网络流量方面比较有效，但改进后 的查询集比原查询集合的查询代价要大。我们在算法进行之前先利用沮。文档 模式d t d 对v 几文档进行过滤判断，对查询集的冗余度进行估计，根据评估 结果来决定采用是否采用新的查询集，从而在网络流量和查询计算量之间取得一 个均衡点。 本文根据优化方案的具体运行流程设计一个，a t h 查询集冗余去除系统，并 详细说明了系统框架中各个模块的功能，其中系统的主体部分即是后面章节讲述 的冗余去除的算法；冗余去除算法中分析了不同类型x p a m 查询集查询冗余去除 的处理算法；并在其后对算法正确性进行了分析和证明；最后，通过实验对算法 的执行及正确性进行了验证。 本文是按照下面的结构组织的： 第二部分在绪论基础上对文章的背景知识进行了详细的说明，介绍了a l l l 查询及舭数据库网络查询应用的背景知识，其中包括物化视图，语义缓存等 相关优化技术的原理以及当前详细的研究现状，并与本文采用的冗余去除的优化 技术进行比较，最后引出文章优化技术的启发实例，并阐述了文章的应用背景及 意义： 第三部分中首先给出了自主设计的x p 抽查询集冗余去除系统，并给出系统 总体架构图，详细介绍和分析了框架内各模块的功能，之后从总体上讲解了系统 运行的流程； 。 第四部分是文章的主体部分，在此部分中，首先讲述简单a t h 查询中不同 类型的? a i l l 查询集重写冗余去除后得出最小查询集的过程，然后讲述冗余去除 系统对原有冗余去除方案进行的改进，之后讨论了x p a m 存在谓词结点时冗余去 除的具体操作和相关结论，也即复杂x p 抽查询集的冗余去除； 在第五部分中，用实验结果来证明算法的有效性并进行了效率分析； 最后一部分对全文工作进行总结，并展望未来的工作，指出文章及此方向仍 需要改进和继续研究的几个方面。 3 山东大学硕士学位论文 第二章x m l 数据库查询网络应用及优化技术 2 。1x m l 数据库相关背景知识 2 1 1x m l 介绍 v 几( e 鸷e n s i b l e 丛a r k u p 里御g u a g e ，可扩展标记语言) 是由w b r l dw i d ew 曲 c o n s o n i u m ( w 3 c ) 的x m l 工作组定义的。这个工作组是这样描述该语言的： “v 几是s g m l ( 墅锄d a r d ! b n e r a l i z e d 丛酞u p 里硼g u a g e ，标准通用标记语言) 的子集，其目标是允许普通的s g 池在w 曲上以目前删，( 勘p e r 野哪丛a r k u p g u a g e ) 的方式被服务、接收和处理。诅。被设计成易于实现，且可在s g m l 和删，之间相互操作。”【2 4 1 儿是一套定义语义标记的规则，这些标记可将文档分成许多部件并对这 些部件加以标记。它不像删，或格式化程序。这些语言定义了一套固定的标 记，用来描述一定数目的元素。x 地是一种元标记语言，用户可以定义自己需 要的标记。这些标记必须根据某些通用的原理来创建，标记描述的是文档 内容的结构和含义，而不是描述页面元素的格式化。文档本身只说明文档包含什 么标记，而不是说明文档看起来是什么样的。 从逻辑上讲，一个x m 文档通常包含五个部分，分别是x 池声明，元素， 属性，处理指令，注释。 x 皿之所以成为事实上的网络数据表示标准，是因为它具有其它表示方式 所不具备的特点，主要包括： 1 舭是自描述的 x 地的最大能量来源于它不仅允许定义自己的一套标记，而且这些标记不 必局限于对于显示格式的描述。 2 沮，具有集成数据和文档的能力 大多数语言或者在表示严格的、绝对的内容和数据结构上设计得好一点，或 者在表示灵活的、自由形式的文档文本上设计得好一些，而) ( 】帆在两个方面都 做得很好。它能表示数据和自由格式的文本，也能在同一文档上做到这两个方面。 4 山东大学硕士学位论文 3 沮，具有相当的表现力和可扩展性 实际上，我们可以在所选择的主题上表述任何想表述的内容。它具有一致的 语法，这使得它很容易被解析。 4 舢用一种灵活的可扩展的表示来实现内容通信 x 池允许开发各种不同专业( 如音乐、化学、数学等) 的特定领域的标记 语言。有了这些语言，这个领域的实践者们可以相互自由的交换短文、数据和信 息，而不必担心对方是否利用特殊的、专用的软件来创建数据。事实上，目前已 经开发出了一些特定领域的标记语言，如m a t h ，( 用于数学领域的一种标记语 言) 。这样，非常复杂的领域可以使用x m 很好的合理的表示出来。 5 缸是非专有并易于阅读和编写的 这使得舳成为在不同应用间交换数据的理想格式。 正是由于具有上述的这些优点，帆作为网络上的数据表示方式为人们所 接受和使用，并迅速普及，成为事实上的网络上的数据表示标准。但同时舳 文档以及对应的a l l l 查询的树形结构决定了其比关系数据库查询多了嵌套，循 环，递归等特点，在多个查询结果之间出现交叉冗余的可能性更大，本文正是基 于这点进行讨论。 2 1 2x m l 数据库网络应用 如何对皿文档进行有效管理与快速查询是当前学术界的研究热点，即所 谓的x m l 数据库。帆数据库是可以对儿文档进行存取管理和数据查询的数 据库。 x m l 本身是不是数据库，儿仅仅意味着x a 缸文档。当诅。文件被用于数 据存储管理时，血和它相关的技术结合就组成一个数据库管理系统。 目前，儿数据管理系统主要有两种形式：一种是所谓的“纯儿数据库，如 s o m 哪ea g 公司推出的t a m j n o 和s t 锄f i o r d 大学研制的l 0 r e 等。它们针对儿数据 的树型结构，结合x 地查询中结构信息查询的要求，提出特定的查询方法，其中最 主要的技术是以结构化连接2 5 】为基础的查询方法这种方法对舳数据的结点进 行合理的编码，通过对不同标签在文档中的位置进行比较，获得标签间的结构关 系，从而完成查询：另一种形式仍然采用原有的关系数据库引擎，以关系表存储 山东大学硕士学位论文 经过拆分的v 几数据。当用户进行x m l 查询或其他处理时，数据库重新组合这些 数据。这个过程的关键是选择和设计儿在关系数据库中的存储模式，即物化视 图的方案选择方法，良好的方案将会极大地提高舳数据的查询效率。 x m l 数据库的主要用途可以概括为两方面：对基于沮，的数据进行有效的 管理、对基于w 曲的各种数据源进行集成。如果建立的数据库是基于w 曲的，同 时管理的信息具有半结构化特征，那么最好使用舭数据库。 目前舭数据库在有效的存储组织、合理索引结构、数据库系统的安全性、 事务处理、数据完整性、触发器、多用户处理机、数据的聚合能力等方面还有待 提高。另外，标准众多，缺乏统一的数据库开发标准。不同数据库产品之间的兼 容性值得怀疑。 与传统关系数据库相比，x 数据库具有以下特点： 1 皿数据库的数据模型可以是树、图等层次数据模型，而传统的关系数 据库是以关系数据模型理论为基础的，所以x 皿的数据结构比关系数据库更具 有表现力，它能够对诸如网页等半结构化数据进行有效的存取和管理，而且更加 便于对层次化的数据进行操作。 2 传统数据库语言允许对数据元素的值进行操作，但不能对元素名称进行 操作，而舳数据库则提供了对标签名称的操作，并且包括了对路径的操作。 3 x m l 数据库的显示丰富多样，其多样性由x s l ( e ) 哟n s i b l es t l i ，l es h e e t l a n g u a g e 可扩展样式表语言) 指定，而传统关系数据库的显示方式相对简单。 4 传统关系数据库只能采用s q l 查询语言，而舳文档查询语言包括 x q u e 巧【2 1 ，a t h 【l 】，v 儿q l ，q 唧等。 5 皿数据库的模式主要由d t d ，皿s c h e m a 确定，而传统关系数据库由 数据字典决定；不过以文档为中心的儿文档其内容是有顺序的，顺序性使得查 询操作尤其是连接和修改操作更加复杂，而在传统数据表中，表项之间的顺序是 可以互换的。 x 池数据库在管理复杂数据结构中所表现出来的超强能力已逐渐为用户所 认同。对于异构信息系统的集成，比如b 2 b ，b 2 c 集成、电子信息的发布、电子 销售等，以及在数字图书馆、视频媒体中心、电子邮件管理、企业信息和知识管 理中心等以文档为中心的应用中，舭数据库也显示出了它的潜力。就算是对 山东大学硕士学位论文 遗留系统有较高要求的用户，也可以从支持x 地的数据库中找到足够的支持。 网络方面存在多种舢数据库查询的应用。例如能够在网络上提供交互查 询接口的儿实时查询系统，儿流数据库系统，在线舭数据库。舭实时 查询系统采用p u s h - b a s e d 信息服务方式，用户先注册查询到服务器，服务器检测 它们的数据，当出现与用户查询符合的数据时，就把这些数据发送给对应发出请 求的用户；x 池流数据库系统中，服务器发送给客户端一些x a 皿数据流，客户 端检测这些流数据并挑选自己感兴趣的数据。在上述各类查询系统中，用户可以 采用各种不同的查询语言，但目前它们大多都采用x p 劬，x q u e 巧等查询语言查 询x 缸远程数据库，并将结果返回给用户。下一章节将会就查询语言，a ：吐l 单独 做出介绍。 2 1 3x p a t h 查询介绍 数据自身的结构特点、查询语言的特性等都会对语义缓存的组织结构，查 询的优化等造成影响。在x 池查询语言方面，目前比较广泛使用的查询语言有 x q u e 黟和x p a m 。其中作为主流查询语言的x q u e 巧是程序化语言与描述化语言 结合的产物，其最新版本是由w 3 c 在2 0 0 5 年1 月发布的1 o 版工作草案。x q u e 巧 以f 1 胍( 】r - l 晦w h e r e r e t l 咖) 表达式为基本构架，以复杂的长路径表达式为核 心语句。查询表达式中不但规定了查询语义，而且限制了查询的执行顺序。a 血 的最新版本是由w 3 c 在2 0 0 5 年发布的2 0 版工作草案，它是x q u e 巧的一个关 键组件。单独的x p a m 路径本身就是完全有效的x q u e r y 语句，两种语言有相同 的公共数据模型。复杂的x p a ：l l l 或x q u e 珂查询语句都能对查询的优化技术造成 影响。因为本文主要讨论a m 查询集的优化，所以本节详细介绍了a m 的语 法及相关概念。 ) 口 a l l l 的主要构件是表达式，其中，最重要的表达式是定位路径( l 0 c 撕0 n p a 山) 表达式，这也是它为什么命名为a t h 的原因。定位路径表达式是这种类型 的表达式：p u b b o o k a u 吐1 0 r 。粗看起来，定位路径表达式很像文件系统中的路径。 定位路径的思想和文件系统中的路径却是很相似，当然，更复杂一些。定位路径 有两种，相对的定位路径和绝对的定位路径。每种定位路径都是由个或多个定 位步组成，每个定位步之间用正斜杠( ) 分开。绝对路径以正斜杠( ) 开始，而相 7 山东大学硕士学位论文 对路径则没有。x p a 1 中用上下文结点集合来描述定位路径的求值过程是如何进 行的。上下文结点集定义为：表达式中给定点确定的当前结点集，而上下文则定 义为：正在处理的当前结点。定位步按照顺序从左到右一次一个地求值。 一个定位路径由若干个定位步组成，而一个定位步有三个部分： 一个轴，它指定了定位步选择的结点与上下文结点之间树状关系： 一个结点测试，它指定定位步选择结点的结点类型以及结点扩展名； 零个或零个以上的谓词( 判定词) ，它使用专有的表达式进一步细化定位步 选择的结点集合； 下面介绍说明本文中常用的x p a m 语法，具体来说，如果路径以单正斜杠( ) 开始，那么该路径就表示到一个元素的绝对路径；如果路径以双斜杠( ) 开头， 则表示选择文档中所有满足双斜杠之后查询规则的元素( 无论层级关系) 。举例表 示如下： 1 ，b o o k 选择所有b o o k 元素，是指返回b 0 0 k 所在的) m 几片断( 子树) ，而不是单 纯的一个元素，此处b o o k 无论处在儿文档的哪个层次都符合查询要求； 2 p u b b 0 0 k 选择所有父元素是p u b 的b o o k 元素； 3 ，星号书 表示选择所有由星号之前的路径所定位的元素； 4 属性：，b o o k a u t l l o r 】 选择有a u i l l o r 属性的b o o k 元素； 按照上述，a t h 基本语法介绍，我们根据x p a ：吐l 查询中有无谓词存在将其分为 两种类型，简单，a c h 查询和带谓词分支的复杂x p a m 查询，前者所有的查询结点 都在查询的主路径，不存在谓词分支。下文在算法中将按这两类查询进行讨论。 2 1 4x p a t h 查询树模式 文中的算法还需要用到x p a m 查询树模式，d a i ls u c i u 引入了，a c h 树模式 的概念。给定一个支持 ，木，【】) 的x p a m 查询，可以构建一个等价的树模 式，反之亦然。a _ c h 路径查询可以描述为一棵查询树，称为a t l l 树模式。其 山东大学硕士学位论文 形式化的描述如下： 定义1 x 池查询树 针对v 匝数据的路径查询可以表示为一棵查询树q = 代e ，r 0 0 t ，p r e d i c a t e ) ，v 是树中结点的集合，i b o t 是查询树的根，e 是树中结点之间边的集合，边分为两 种，分别表示父子包含关系和祖先后代包含关系，即“和“ ；除了根结 点之外，函数p r e d i c a t e 赋给查询树中的每个结点一个谓词条件( ) ，该条件针 对元素的名字、属性值及文本值等。 在实际的查询树中，往往只有一个结点在数据中的映射结点是查询需要的输 出结果，其余结点之间的边只是对该结点的条件约束。基于这样的考虑，我们同 时给出如下的一些定义。 定义2 返回结点 舭查询树中存在一个结点n ，它在数据中的映射是查询的最终输出结果， 该结点称为查询的返回结点或者目标结点。 定义3 查询的主路径 在) a 帆查询树q 中，从根结点到目标结点之间的路径称为查询的主路径。 其中，x p a t l l 查询中“或者“的个数表示查询层次数。 定义4 在儿查询树q 中，孩子结点数目大于1 的结点( 即出现路径分叉 的结点) 称为分支结点。 定义5 在x 池查询树q 中，如果结点上除了针对元素名的谓词条件外， 还定义了针对元素值或元素属性值的谓词条件，这样的结点称为值谓词结点，这 类谓词条件所在的子树称为谓词子树。 我们利用一个例子来简要说明x p a t h 查询树模式，查询q = a 【v 伽【 、) 1 7 = t 1 ”】 x y 】c 【疹t 2 】对应的树模式如下图2 - l 所示，其中查询的返回 结点是c ，查询主路径是加c ，存在多个分支结点，如a ，b ；上述查询中出现 了4 个谓词结点与谓词子树，分别是【v 】，【 w = ”t l ”】，【x 【y 】，【庐诩： 9 山东大学硕士学位论文 图2 1x p a 吐l 查询树模式举例 2 1 5x m l 文档类型定义d t d 沮。文档类型定义d t d 是对x 1 帆文档模式的定义，d t d 主要用来指定文件 的结构，是一套关于在，文档中使用的标记符的语法规则。它告诉你可以在 文档中使用哪些标记符，它们应该按什么次序出现，哪些标记符可以出现于其它 标记符中，哪些标记符有属性等。它可以是舭文档的一部分，但是它通常是 一份单独的文档或者一系列文档。帆本身并没有一个通用的d t d ，想使用皿 进行数据交换的行业或组织可以定义它们自己的d t d 。 v 几文档所对应的树状结构，我们称之为文档树。与之对应，d t d 所对应 的树状结构，称之为d t d 树。 d t d 树与其对应的x 池文档树相比，结点少很多，本文利用d t d 树判断 x 池文档的结构特点。通常我们用到的x 地文档的结点规模很大，而d t d 树与 其对应的，文档树相比，结点规模却少得多，若利用d t d 树来优化文档查询， 只要扫描一遍规模较小的d t d 树，即可省去大量的对文档树所做的无用的遍历。 平均来说，文档树的结点数与d t d 树的结点数的比越大，我们方法的效率越高。 l o 山东大学硕士学位论文 2 2x m l 数据库查询网络应用相关优化技术 在x 地数据库网络查询应用中，为提高查询的响应速度，或者减小网络传输 流量，出现了大量的查询优化技术，考察查询执行的效果，除了准确地返回符合 查询条件的所有数据之外，另一个关键的指标就是查询的响应速度。对于同样的 查询条件，返回结果的速度越快则查询执行的效率越高。传统的关系数据库( 包 括基于关系表、关系代数的分布式数据库) 为了提高查询响应速度，除了进行查 询语句改写、查询计划优化和基于代价的执行顺序选择之外，数据库管理系统 ( d a t a b a s em 锄a g e m e n t 趼s t e m ，d b m s ) 还会采用各类技术对数据库的查询进行优 化；在数据库网络查询模式下，除了以上传统的技术，还会针对网络查询模式的 特性进行查询改进，如利用物化视图进行查询重写，语义缓存等，这些查询优化 技术也被用在针对舳数据半结构化特点的查询中，由于这类技术与本文所提 的优化技术关联较大，下面将分别介绍其在关系数据库和x m l 数据库中的发展。 2 2 1 查询重写 查询重写是数据库研究的一个基本问题，它和数据库管理的若干问题如查询 优化、数据仓库、语义缓存、数据集成等问题密切相关。 目前的数据集成系统一般遵从w i e d e r h o l d 提出的m q s 体系结构瞄l 。为提高系 统的查询效率，系统选择频繁提交的查询在中间层建立物化视图。考虑到数据源 访问的不确定性和网络传输的代价，当用户提交查询后，系统尽可能利用中间层 视图，而不是访问数据源来回答查询，这个问题实际可以归结为半结构化查询重 写问题。考虑到中间视图层空间的有限性，已有视图应当尽可能回答更多的查询。 本质上，这个问题可以抽象为查询重写问题给定数据库d 和在数据库上定 义的视图集合v = v 1 ，v 2 ，1 ) ，对数据库d 的查询q ，如果存在查询q t ，其 中q t 至少查询了视图集合v 中一个视图，而且q 的查询结果和q 在数据库中的查 询结果一致，则称q 是q 的查询重写。 在传统的集成系统中，用户发出查询到查询重写部件，查询重写部件将它分 解为视图中能够回答的部分和需要访问数据源的部分。文献 6 在传统模式下进 行改进，讨论的查询重写部件包含集成数据语义约束的信息，在用户发出查询后， 山东大学硕士学位论文 查询重写部件利用约束信息转换得到用户查询的等价集合，如果视图能够回答等 价集合中的任一查询，则用户查询重写成功，通过这种方式增加了中间视图层的 表达能力。 传统集成模式和基于语义重写的集成模式下，物化视图的查询重写分别采用 如下图2 2 中左边和右边所示的框架： 查询重写语义查询重写 图2 2 传统集成模式和基于语义的集成模式下的查询重写 基于查询重写的重要理论意义和应用价值，目前国内外相关人士对于查询重 写做了大量的研究：文献 8 ，9 论述了关系数据查询的重写；文献 1 0 ，1 1 研究了 如何重写含有聚集函数的查询；文献 1 2 论述了递归查询的重写；文献 1 3 ，1 4 论述了半结构化数据查询重写；文献 1 5 论述了正则路径表达式的查询重写；文 献 1 6 使用模式树来解析x q u e 秽查询语句，将查询频率高的结点放在物化视图 中，并使用查询代数树来表示用户的查询和物化视图，利用物化视图和用户查询 的交叉部分，直接从物化视图中获取用户的查询内容。总之，查询重写技术已经 在关系数据库和) ( m l 数据库的查询优化中得到了很好的应用，其原理也可以被其 它优化技术借鉴。 1 2 山东大学硕士学位论文 2 2 2 语义缓存 缓存技术最早是在关系数据库中提出的，这是数据库系统的一个重要功能。 把一些在一段时间内不发生改变的数据放到缓存中，当以后需要这些数据时，就 不必每次从本地磁盘或服务器读取数据，而直接从缓存中取得，这样就加快了查 询响应的速度。 语义缓存是近年来数据库缓存领域出现的一个新方向。所谓“语义缓存” 是指把用户的查询与结果数据对应起来，一起保存到缓存中。这样，缓存中保存 的就不只是一些单纯的数据，由于加入了对数据的描述性语义信息