（计算机应用技术专业论文）基于xquery和语义缓存的xml查询处理技术的研究与实现.pdf

基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现中文摘要 中文摘要 随着计算机、通信和网络技术的不断发展以及x m l 技术的日益成熟，以x m l 作为载体的w e b 信息量增长快速、访问日趋频繁。但网络和移动计算环境存在的带 宽限制、频繁断接性等缺陷，造成了w e b 环境中分布式或c s 访问模式下信息存取 和查询处理的瓶颈。 本课题针对上述背景提出了一种基于x q u e r y 和语义缓存的查询处理技术，旨 在减少对w e b 信息和分布式x m l 数据源的访问次数以及网络数据的传输延迟，从 而提高w e b 环境下的数据查询性能。本文的研究内容主要有： 1 研究了x q u e r y 查询核心语法子集的语义及其特征，提出了x q u e r y 查询的 规范化规则，简化了查询的表现形式，降低了查询匹配和重写的复杂度； 2 通过对x q u e r y 语义的深入研究，解析由x q e n g i n e 查询引擎生成的抽象语 法树，并对其进行相应的处理，构造了能够精确刻画x q u e r y 语义的树型结 构语义抽象树( s a t ) 和标签关系树( t i 玎) ； 3 研究和分析了现有查询匹配技术，针对f w r 表达式以变量为中心的特点， 借鉴了传统树型同态算法的核心思想，提出了基于s a t 同态的查询匹配条 件，并给出了相应的算法； 4 根据f w r 查询块的嵌套层次，设计了一种基于t i 盯的查询重写方案，并 对其进行了优化，提出了基于反向匹配的重写算法，降低了查询重写实现 的复杂度； 5 针对x m l 数据及x q u e r y 语言的特点，提出了结合路径表达式的缓存替换 策略，为缓存腾出空间的同时保证了其命中率。 本文最后实现了一个基于上述技术的客户端x q u e r y 语义缓存，并在c s 访问 模式下对查询处理和语义缓存管理进行了性能测试和分析。从实验结果可以看出， 基于x q u e r y 和语义缓存的查询处理技术能有效地提高w e b 环境下x m l 数据的查 询性能。 关键字：x q u e r y 、语义缓存、语义抽象树、查询匹配、标签关系树 作者： 指导老师： a b s t r a c t w i t ht h e d e v e l o p m e n to f t h ec o m p u t e r , c o m m u n i c a t i o n ，n e t w o r ka n dx m l t e c h n o l o g y , t h ea c c o u n to fw e bi n f o r m a t i o nw h i c hf o r m a ti nx m li n c r e a s eq u i c k l ya n dt h e i n f o r m a t i o na c c e s s i n gb e c o m em o r ea n dm o r ef r e q u e n t l ya tt h es a m et i m e b u ti ni n t e r n e t a n dm o b i l ec o m p u t i n ge n v i r o n m e n t ，m a n yd i s a d v a n t a g e s ，s u c ha sn a r r o wb a n d w i d t h ， f r e q u e n td i s c o n n e c t i o na n dt h ep e r f o r m a n c ep r o b l e m so ft r a d i t i o n a ld i s t r i b u t e dd a t a b a s e ， b o t t l e n e c k e dq u e r y i n ga n da c c e s s i n gi n f o r m a t i o nf r o mw e bu n d e rc so rd i s t r i b u t e d p a t t e r n c o n s i d e r i n ga b o v et h e s e ，t h i sp a p e rp r o p o s e daq u e r yp r o c e s s i n gt e c h n o l o g yb a s e do n x q u e r ya n ds e m a n t i cc a c h ef o rx m ld a t ai no r d e rt or e d u c et h en e t w o r kc o m m u n i c a t i o n c o s ta n de n h a n c et h ep e r f o r m a n c eo fq u e r y p r o c e s s i n g t h em a i nc o n t e n t so ft h i sp a p e ra r e a sf o l l o w s ： 1 d e e pr e s e a r c ho ns e m a n t i cc h a r a c t e r so fc o r ex q u e r y , a n dp r o p o s e das e r i a lo f n o r m a l i z a t i o nr u l e si no r d e rt o s i m p l i f yt h eq u e r ya n dr e d u c et h ec o m p l e x i t yo fq u e r y p r o c e s s i n g ； 2 w i t hd e e pr e s e a r c h i n go nx q u e r ys e m a n t i c ，w ep r o c e s st h ea s tt h a tp a r s e db y x q e n g i n ea n dc o n s t r u c ts a t a n dt r tw h i c hc a nd e s c r i b et h ex q u e r ys e m a n t i ce x a c t l y ； 3 r e s e a r c ha n da n a l y z et h ee x i s t e dq u e r ym a t c h i n gt e c h n o l o g y s i n c et h ef w r e x p r e s s i o ni sc e n t e r so nv a r i a b l e s ，w ep r o p o s e df o u rq u e r ym a t c h i n gc o n d i t i o n sb a s e do n s a th o m o m o r p h i s mw i t ht h ec o r eo ft r a d i t i o nt r e eh o m o m o r p h i s ma r i t h m e t i c ，a n dd e s i g n t h ea r i t h m e t i c ； 4 w i t hc o n s i d e r i n gt h en e s tl e v e l so ff w r ，w ed e s i g naq u e r yr e w r i t i n gp l a nb a s e d o nt a g - r e l a t i o nt r e e ( t r t ) a n do p t i m i s ei tf o rt h ep u r p o s eo fr e d u c i n gt h ed i f f i c u l t yo fi t s i m p l e m e n t a t i o n ； 5 w i t ht h ec h a r a c t e r so fx m ld a t aa n dx q u e r y , p r o p o s ear e p l a c e m e n ts t r a t e g y t h a tc o m b i n et h ep a t he x p r e s s ，b o t hv a c a t i n gs p a c ea n dk e e p i n gt h eh i g h tc a c h er a t i n g f i n a l l y , w ei m p l e m e n tas e m a n t i cc a c h eo fx q u e r yb a s e do i la b o v et e c h o n o l o g i e s ， a n dm a d et h ep e r f o r m a n c et e s t su n d e rt h ec l i e n t s e r v e rd a t a s h i p p i n ga r c h i t e c t u r e t h er e s u l t s h o w st h a tt h eq u e r yp r o c e s s i n gt e c h n o l o g yb a s e do nx q u e r ya n ds e m a n t i cc a c h ec a n e n h a n c et h ep e r f o r m a n c eo fx m l q u e r yo nw e b k e y w o r d s ：x q u e r y , s e m a n t i cc a c h e ，s a t , t a g r e l a t i o nt r e e ，q u e r ym a t c h i n g w r i t t e nb y ：乙jn j 收 轧p e r v i s e db y ：u n y m9 ( ia 图表目录 图2 1 查询q 1 和q 2 ，7 图2 2 查询q 8 图2 3x q u e r y 核心语法子集的b n f 定义9 图3 1 语义缓存的一般模型1 0 图3 2 三表间的逻辑关系1 2 图3 3 查询的三种包含关系1 3 图3 4 a m 的一元树型结构匹配1 4 图4 1 规范化的x q u e r y 核心语法子集的b n f 定义一1 8 图4 2l e t 子句消除流程1 9 图4 3 原子查询消除流程2 0 图4 4w h e r e 子旬中本地变量消除流程2 1 图4 5 规范化的q 2 2 1 图4 6q 1 的s a t 和t r t 2 3 图4 7s a t 同态匹配示意图2 5 图4 8x q u e r y 语义匹配流程2 6 图4 9s a t l 与t r t 2 的映射示意图3 0 图4 1 0 改进前后的查询重写示意图3 1 图4 1 1q 1 与q 2 的关系3 2 图5 1 语义缓存的系统结构3 6 图5 2x q u e r y 语义缓存的查询处理流程3 7 图5 3q l 的抽象语法树3 9 图5 4s i m p l e n o d e 类图4 0 图5 5x q u e r y 语义缓存主界面一4 l 图5 6m i n i m i z e 类图4 2 图5 7s a t 的构造流程4 6 图5 。8n 玎构造流程4 7 图5 9c o n t a i n m e t 类图4 9 图5 10x q u e r y r e w r i t e 类图5 1 图5 1 1q 2 重写示意图5 5 图5 1 2q 2 的语义分解界面5 5 图5 1 3 某时刻q 2 的返回表达式参数的统计信息5 7 图5 1 4c a e h e m a n a g e r 类图5 8 图5 15 某时刻缓存状态参数5 9 图6 1q l 在两种查询模式下的查询结果6 0 图6 2 三种替换策略的命中率对比6 2 图6 3 三种替换策略下查询响应时间对比6 3 图6 4 数据源为5 0 0 k 时某查询的处理界面6 4 图6 5 不同数据源大小的查询响应时间比较( 完全包含) 6 4 图6 6 不同数据源大小的查询响应时间比较( 部分交迭) 6 5 图6 7 不同查询深度的查询响应时间比较，6 6 表4 1 韶返回表达式的参数统计3 3 表5 1s i m p l e n o d e 的主要属性和方法说明4 0 表5 2s i m p l e n o d e 的添加属性一4 0 表5 3c o n t a i n m e t 类的方法说明5 l 表5 4c a c h e m a n a g e r 类的方法说明：5 8 表6 ，l “x m p ”查询集的处理情况6 1 表6 2p r o b eq u e r y 和r e m a i n d e rq u e r y 的平均获取时间一6 5 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发 表或撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使 用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式 标明。本人承担本声明的法律责任。 研究生签名： e t 期：垫z ! ! u 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国 社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可 以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的 内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办 办理。 研究生签名：墨l 丝：同期：雹：! ! ：! 别磁轧蕊芬， 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现第一章绪论 第一章绪论 本章首先介绍了课题的选题背景，然后重点介绍了目前国内外的基于x m l 的语义 缓存技术的研究现状，为了提高w e b 环境下半结构化信息的查询性能，提出了一种基 于x q u e r y 和语义缓存的x m l 查询处理技术，随后介绍了论文的相关工作，最后介绍 了论文的组织结构 1 1 选题背景 随着信息技术的迅猛发展以及社会信息化程度的不断提高，分布式数据库或大型 数据库管理系统需要管理的数据日益剧增，甚至达到了p b 级，而用户并发访问的数 量和复杂度也在不断提高，这种日益尖锐的矛盾已经成为网络环境下，尤其是c s 和 分布式访问模式下制约信息系统查询性能和效率提升的瓶颈。同时，伴随着互联网技 术和移动技术的不断进步，用户不必停留在固定的位置，甚至可以携带移动( 如笔记 本、手机和p d a 等) 设备自由移动，随时随地查询异地的数据库服务器。在这种带宽 低、费用高、断接频繁【l 】的通信环境中，数据库服务器长时间的处理用户提交的查询 ( 检索记录或者处理数据) ，或者通过网络传输大量的数据都是不现实的【2 1 ，长时间的 连接将加重用户的经济负担，并且加大了这种不稳定连接的断线概率【3 1 1 4 。 在众多的查询优化方法中，缓存技术得到了业界的广泛关注。类似于程序执行的 局部性，用户的查询也存在局部性。在许多情况下，不到5 的关系表占用了数据库 系统超过5 0 的i o 时间【5 j ，这表明用户的访问往往具有语义局部性，即用户一般按 照下述模式访问数据库：首先提交一个查询，接着调整选择条件，或者施加更多的选 择条件。显然，后来的查询可以由先前查询的结果全部或者部分导出。因此，语义缓 存【6 】技术通过在客户端缓存查询的结果及其语义描述信息，能够发掘蕴藏在查询谓词 中的语义信息来组织查询结果，可以尽可能地在本地回答查询，从而避免了从数据库 服务器提取数据，并借助通信网络传输到客户端。相比传统缓存而言，语义缓存能更 有效地利用缓存，极大地减轻了数据库服务器和网络的负担，同时加快了查询的响应 第一章绪论 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现 速度。但一直以来，语义缓存技术主要被运用于关系数据库系统中，人们的研究也都 集中在结构化查询语言( s q l ) 的查询优化技术上。 由于互联网技术的蓬勃发展，传统紧耦合的网络分布式组件( d c o m 、c o r b a ) 已经逐步被动态、松耦合、数据驱动的w e b 服务所取代。半结构化数据( x m l ) 的 出现为w e b 服务中异构信息的整合、交互和共享提供了新的方案；同时，作为一种 新的数据模型，x m l 以其自身的显著特点，已经成为i n t e r n e t 上数据表示和交换的实 际标准，被广泛的运用于各种w e b 应用中，如s o a p 7 1 、x m l r f c 8 1 消息等。而x m l 的查询语言，如x p a t h 、x q u e r y 也在w e b 上得到广泛的研究和应用。因此，如果将 语义缓存技术结合到x m l 数据的查询处理过程中，就可以有效的避免网络传输延时 和频繁的断接，极大地提高w e b 环境下半结构化数据的查询性能。 本课题正是为了满足上述日益复杂的应用需求和适应计算机技术进步的需要，研 究并实现了一种基于x q u e r y 和语义缓存的x m l 查询处理技术。x q u e r y 是针对x m l 数据而设计的查询语言，是现有半结构化查询语言中功能最强大，最完善的一个。本 文在深入研究了x q u e r y 查询语言的基础上，根据其特点设计了一对可以代表查询语 义的树型结构，并利用这对树型结构对x q u e r y 查询进行语义匹配和重写等处理，最 后按查询关系来决定是否能从本地缓存直接获得所需的全部或部分数据，从而减少对 w e b 信息和分布式数据源的访问量以及网络的数据传输量，从而提高查询响应速度。 1 2 国内外研究现状 语义缓存的查询处理技术主要包括查询语义包含关系的判断和查询重写两部分， 它们因查询数据模型及其查询语言的不同而各异。对于关系数据的语义缓存技术，不 论是缓存的数据组织和存储模型还是查询处理( 包括语义包含关系匹配、查询重写) 都得到了国内外学者广泛而深入的研究，技术已经比较成熟。下面将重点介绍基于 x m l 查询语言的语义缓存查询处理技术在国内外的研究现状。 由于x m l 及其相关技术的广泛流行，各种技术联盟相继提出了针对x m l 数据 的查询语言，其中x p a t h 9 1 和x q u e r y 1 0 】是这些查询语言中最有影响力、使用最频繁的 两种。x p a t h 是众多x m l 查询语言的基础，其语义包含关系问题的研究对其他语言 的查询优化、查询重用、视图物化等方面有重要意义，而且也是其它语言语义匹配的 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现 第一章绪论 基础。因此，国外有很多文献对这一问题进行了研究【i l 】【1 2 】【1 3 】1 1 4 】。基于x p a t h 查询是 单个规则路径表达式，最早有人提出利用规则路径视图对查询路径表达式进行重写 i ”j ，随后d c a l v a n e s e 等人又对这一研究结果进行了扩展，他们研究了带有反向操作 符的路径表达式，将表达式表示为图，通过对图进行遍历来重写查询【1 5 】【1 6 】。与上述 不同，文献f 1 4 】中提出将每个x p a t h 路径表达式表示为一棵无序树，表达式中的每个 符号都由树中的一个结点表示，这样就可以将查询语义的匹配问题转化为树型结构间 的嵌套问题，通过树型同态匹配来判断查询语义的包含关系：同时，该文也指出他们 的研究只是针对x p a t h 语法全集的一个常用核心子集，因为很难设计一个完备有效语 义匹配算法来判断x p a t h 查询的查询包含关系。语义匹配和查询重写算法的复杂度也 一直是该领域研究的重点，构造x p a t h 查询表达式所用的导航符号和谓词不同会导致 查询语义匹配算法的复杂度不同。另外有研究表明，在数据源有d t d 和没有d t d 限制两种情况下，同一查询的复杂度也不尽相同【1 7 】【l8 1 。因此，目前的研究对象主要 是常用的核心语法子集或特定应用场景下的查询子集。 x q u e r y 查询的主要成分是x p a t h 路径表达式。但与x p a t h 相比，x q u e r y 特有的 f l w o r 表达式能定义绑定变量，构造更复杂的查询逻辑。正是由于x q u e r y 与x p a t h 之间的这种关系，其查询语义匹配和重写技术可以以x p a t h 的现有技术为基础但又不 能完全照搬。针对x q u e r y 可以任意定义变量的特点，文献 1 9 着重研究了x q u e r y 查询中变量之间的关系，将冗余变量从查询中剔除，从而简化查询匹配的复杂度；对 于简化后的x q u e r y 查询，文中又提出了两种树型结构，用来代表变量关系和查询结 果的标签层次关系，再对这两棵树分别进行树型同态匹配，只有两次匹配都成功才能 断定查询语义具有包含关系，过程比较复杂。在查询视图的重写研究方面，为了判断 重写前后的查询相等，i g o rt a t a r i n o v 等人也提出了一种查询语义匹配算法【2 0 1 ：将结果 结构的标签层次关系构建为一棵树型框架，而每层标签中所含的x m l 文档结点又构 成一棵树嵌套在上述树型框架中，通过这两个树型结构的同态匹配来判断重写前后的 查询是否相等。但该算法主要侧重于查询结果重构的层次关系，没有考虑变量间的关 系。与x p a t h 一样，目前x q u e r y 语义匹配问题地研究还主要是针对各自特定的应用 场景，并不具有通用性。另外，x q u e r y 还没有作为正式的标准发布，这方面的研究 还比较有限。 国内对于半结构化数据查询处理技术的研究主要还是集中在如何实现关系数据 第一章绪论 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现 库中x m l 数据的查询及其性能的提高或某一具体语言的实现机制和查询优化等方 面，鲜有对于半结构化查询语言在语义缓存方面的查询处理技术的研究。文献【2 l 】曾 涉及到这方面的内容，它提出构建一个以x q u e r y 为查询语言的客户端缓存，通过提 取绑定变量中的选择条件，给出了基于析取合取范式的语义分解的理论方案，但该 方案更倾向于采用关系模型的语义匹配方法来解决问题。随着x m l 和w e b 服务技术 的不断成熟以及x q u e r y 自身的不断完善，基于x q u e r y 的语义缓存技术的研究将更 有利于满足人们对信息获取日益复杂的需求。 1 3 研究内容和意义 1 3 。1 研究内容 本文在介绍了x q u e r y 和语义缓存技术的基础上，重点研究了基于x q u e r y 核心 语法子集和语义缓存的查询处理的相关问题，提出了一个w e b 环境下基于x q u e r y 和语义缓存的x m l 查询处理方案，从而可以缩短查询响应时间，提高查询性能。 论文的主要工作如下： 1 ) 介绍了x q u e r y 语言及其核心语法子集，并对其特征进行了深入研究； 2 ) 研究和分析了现有语义缓存中关键技术的研究现状，包括缓存数据模型、查 询匹配和重写、替换策略和一致性； 3 ) 针对x q u e r y 语义的特点，设计了x q u e r y 查询的规范化规则，简化了查询匹 配和重写的复杂度； 4 ) 根据半结构化数据及x q u e r y 的特点，设计了两种树型结构语义抽象树 ( s a t ) 和标签关系树( t r t ) 来刻画x q u e r y 查询中f w r 表达式的语义，并将它们作为 缓存的语义描述模型； 5 ) 在x p a t h 一元树型同态匹配思想的基础上，设计了一种基于s a t 同态的查询 匹配算法： 6 ) 通过构建s a t 和t r t 之间的映射，分别给出了f o r 子句和r e t u r n 子句的重写 方案，并根据t l 玎的结构特点，针对整个查询设计了一种基于t r t 的反向匹配重写 算法； 4 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现第一章绪论 7 ) 通过分析x q u e r y 查询，设计了一种结合路径表达式的缓存替换策略，在清 理出缓存空间的同时保持较高的命中率； 8 ) 在上述技术的基础上提出了一个语义缓存系统框架，并实现了一个基于内存 的客户端x q u e r y 语义缓存，包括查询规范化、查询解析、查询匹配和查询重写、语 义缓存管理等子模块。最后通过实验测试了该语义缓存的x m l 查询处理的性能，实 验结果显示性能良好。 、 1 3 2 研究意义 本文的研究意义主要有以下几点： 1 ) 本课题所提出的查询优化处理是针对半结构化数据及其查询语言的，是一种 在本质上与关系模型体系完全不同的查询处理技术； 2 ) 跟踪x q u e r y 草案的发展动向，研究最新的x q u e r y 语义及其查询引擎的实 现机制，并应用到客户端的语义缓存中，体现了一定的前沿性和先进性； 一 3 ) 在语义抽象树s a t 中增加了对f w r 查询块的语义描述，将变量与其所在的 f w r 查询块结合在一起，使x q u e r y 查询语义匹配更完备； 4 ) 论文给出的查询语义匹配方案针对s a t 树型结构的特点，在x p a t h 一元树型 模式匹配的基础上，扩展了传统的树型同态匹配算法，丰富了语义缓存理论系统； 5 ) 提出了基于t i 盯的反向匹配重写算法，减少了变量匹配的复杂度，简化了查 询重写过程； 6 ) 论文针对x q u e r y 查询而设计的缓存替换算法，采用了数据粒度更小的路径 表达式作为替换单位，提高了缓存空间利用率并保持了较高的“保鲜度”； 7 ) 为在网络和分布式数据源环境下提高x m l 信息查询性能提供了一种可行的 解决方案，测试证明基于x q u e r y 和语义缓存的查询处理技术可以缩短查询响应时间， 减少客户端与服务器的连接次数和网络负载，提高查询性能。 1 4 本文的组织结构 本文分为七个章节内容进行讨论： 第一章为“绪论”部分。本章首先介绍了选题背景，然后对本课题的国内外研究 第一章绪论 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现 现状作了详细介绍，最后给出了本文的研究内容和意义。 第二章为“x q u e r y 简介 部分。本章主要对x m l 的查询语言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 的语义特征，构建了能描述查询语义的语义抽象树 s a t 和标签关系树t l 玎作为语义缓存的数据模型：并以此模型为基础，提出了基于 s a t 同态的查询匹配算法和基于t r t 的反响匹配重写算法；最后针对半结构化数据 的特点，设计了一种结合路径表达式的替换策略，来提高缓存命中率。 第五章为“基于x q u e r y 和语义缓存查询处理的实现 部分。本章利用上述查询 处理技术，设计并实现了一个客户端的x q u e r y 语义缓存。首先给出了该语义缓存的 应用框架和查询处理流程，然后详细介绍了该语义缓存中基于x q u e r y 和语义缓存的 查询处理和缓存管理模块的具体实现。 第六章为“性能测试与分析 部分。本章设计了3 个实验，分别对查询匹配的正 确性、替换策略性能和查询响应速度进行了测试，测试结果表明本文设计的x m l 查 询处理技术在w e b 环境下能有效的提高数据查询性能。 第七章为“总结与展望”部分。本章是对上述工作的总结，并对今后进一步的研 究工作作了展望。 6 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现第一二章x q u e r y 简介 第二章x o u e r y 简介 x q u e r y 是本文语义缓存技术研究的语言主体，本章对其做了详细的介绍。首先介 绍了两个x q u e r y 查询实例，说明了x q u e r y 与x p a t h 联系和区别；然后介绍了x q u e r y 的语法结构和特点，最后给出了x q u e r y 语义核心子集的范畴及其b n f 定义 2 1 两个x o u e r y 查询 过去几年里，在以数据为中心和文档为中心【2 2 1 的环境下，作为信息的一种格式化 语言，x m l 迅速得到了广泛地欢迎，高效地存取x m l 信息变得越来越重要，这就 必须要有一个强大的、优雅的查询语言来准确地获取所需信息，x q u e r y 正是这样的 语言。 下面列出了两个x q u e r y 查询实例，分别为q j 和q 2 ，它们都调用了嵌套的f l w r 查询块从x m l 文档中抽取数据，并重新组织查询结果的结构。 -， 7 i l e ts d ：= d o c ( ”b i b j c m l 。) b i b ， f o r s b o o k i n s d b o o k y e a r = 2 0 0 0 1 ， r e t u r n ， f o r $ t i t l ei n $ b o o k t i t l e ，$ a u t h o ri n $ b o o k a u t h o r r e t u r n $ t i t l e $ a u t h o r 加，) 一 ” ， f o r $ b o o ki nd o c ( ”b i b x m l ”) b o o k ，w h e r e $ b o o k y e a r 1 9 9 0 ? ，。 ， r e t u r n f o rs t i t l e 加$ b o o kit i t l er e t u r n $ t i t l e s b o o k 妇 扣，$ a u t h o ri n $ b o o k a u t h o rr e t u r n $ a u t h o r 加t ( $ a u t h o r l a s t ) )、 q 2 ， 图2 1 查询q 1 和q 2 观察以上实例，发现绑定变量是x q u e r y 查询的主体。从变量定义开始，查询将 x m l 文档中的数据按一定的结构与变量绑定，作为中间数据；在r e t u r n 子句中，绑 第二苹x q u c r y 简介 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现 定了数据的变量又按用户的需求将数据组织成一定的层次结构，最后返回给用户。 x p a t h 路径表达式用于定义变量绑定并作为r e t u r n 子句中的返回内容，是构成 x q u e r y 查询的基本成分。因此，x p a t h 包含关系的判定算法为解决x q u e r y 查询的包 含关系判定问题奠定了基础。但x q u e r y 毕竟还有其自身的显著特征，不能简单地套 用x p a t h 的语义匹配算法来解决x q u e r y 的查询匹配问题。 2 2x q u e r y 的语法结构及特点 x q u e r y 是在q u i l t l 2 3 1 语言的基础上提出的，综合了s q l 、o o l 、x m l q l 、x q l 及l o r e l 等诸多语言的特点，其语法结构采用b n f 定义，与我们所熟悉的s q l 结构 上有些相似，它包括名字空间和模式声明、函数定义和查询表达式三部分。 语法结构的第一部分和第二部分合在一起，构成x q u e r y 的查询序，它包括了一 系列声明和定义，建立了查询处理的环境，主要包括命名空间声明、模式导入、 x m l s p a c e 声明、缺省的c o l l a t i o n 以及函数定义，查询序为x q u e r y 的可选项。查询的 第三部分包含了查询表达式，这是x q u e r y 的主体，为必要项。 由于x q u e r y 与x p m h 2 0 同源，它除了兼容x p a t h 的路径表达式查询外，最显著 的特点就是能通过构造f l w o r 嵌套子句来创建复杂查询。x q u e r y 的f l w o r 表达 式看上去与s q l 的s e l e c t - f r o m w h e r e 语句相似，它代表力，1 e t w h e r e o r d e r b y - r e t u r n 五个子句。f o r - l e t 子句生成绑定变量元组的有序序列；w h e r e 子句提供过滤元组流的 条件；o r d e r b y 子旬要求对元组流进行排序；r e t u r n 子句构造f l w o r 表达式的结果， 其中w h e r e 和o r d e r b y 子句为可选项。下面是w 3 c 提出的x m lq u e r yu s ec a s e 2 4 】中 的一个x q u e r y 例子。 图2 2 查询q 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现 第二章x q u e r y 简介 2 3 x 0 u e r y 的核心语法子集 w 3 c 在提出x q u e r y 语法和数据模型的同时也给出了它的形式语义。它用严格的数 学形式精确地描述t x q u e r y 的语法和含义，为查询引擎的实现者提供了一个能够将 表面语法特性直接构造为底层代数的映射。x q u e r y 的语法全集内容丰富，其语义包 含匹配是一个n p c o m p l e t e l h - 题。出于性能和代价方面的考虑，本文只讨论它的核心 语法子集【2 卯，本文后面所说的x q u e r y 都是指其核心语法子集。该核心语法子集涵盖 t x q u e r y 的主要特点，包括f l w r 嵌套、多重变量绑定和条件选择等。它的b n f 定义 形式如图2 3 所示： 图2 3x o u e r y 核心语法子集的b n f 定义 在图2 3 所示的定义中，印表示x p a t h 查询的路径表达式， e i ( i _ l ，2 ，) 表示r e t u r n 子句中的返回表达式序列， ，和c 分别表示绑定变量和选择条件。【v 】表示l o r - l e t 子句 中定义的变量序列， e 贝j j 是变量对应的绑定表达式。此外，为了避免查询递归计算， 本文讨论的x q u e r y 中使用的x p a t h 路径表达式为c o r ex p a t h 2 6 1 ，c o i ex p a t h 只允许 含有，口四个运算符，即x p ，, t - l ，不包括“i ”、否定和表达式递归运算。 文献【1 4 】证明c o r ex p a t h 的查询匹配的复杂度是p t i m e 。 2 4 本章小结 本章通过对x q u e r y 查询语言的语法结构和特点的进行了详细介绍，了解了 x q u e r y 与x p a t h 的联系与区别，为下文阐述查询处理技术打下了铺垫；同时，还给 出了x q u e r y 常用核心子集的范畴，本文基于语义缓存的查询处理技术就是围绕它而 展开的。 9 第三章语义缓存技术概述基于x q u c r y 和语义缓存的x m l 查询处理技术的研究。j 实现 第三章语义缓存技术概述 本章首先给出了语义缓存技术的一般处理模型，然后对其关键技术做了详细介 绍，包括缓存数据模型的构造、基于树型同态的查询处理技术、缓存替换策略和一致 性维护技术，并分析了它们的不足之处。本文研究的重点是数据模型、查询处理和替 换策略这三方面的技术 3 1 语义缓存的一般模型 缓存数据的根本目的是通过缓存查询的语义描述信息及其结果，尽可能地发掘蕴 藏在查询谓词中的语义信息，并利用客户机的处理器和存储器资源处理查询，从而减 轻服务器和网络的负担。它的一般模型如图3 1 所示。当进行一个新的查询时，首先 由查询引擎解析查询，然后将新查询的语义与缓存查询进行匹配，根据匹配结果将查 询分解成两部分：一部分查询是从缓存系统中能够直接或间接获得查询结果的那部 分，称为试探查询( p r o b eq u e r y ) ：另一部分查询是不能从缓存系统中获得查询结果的 那部分，称为剩余查询( r e m a i n d e rq u e r y ) ，此部分被发送到服务器端去处理。最后， 在客户端合成两部分的查询结果，形成最终的结果集。除了查询处理，还必须对缓存 的查询语义和查询结果进行必要的维护，包括缓存替换和一致性等问题。 接 口 一、 1r ，瞻在，- r - - i 查询解析 k 结果 接 、一 远程 l i 瑟毒摇舯i ， 厂语艾厂 数据库 信息 【 服务器 口 替换策略 一致性维护 t i 图3 1 语义缓存的一般模型 l o 基于x q u e r y 和语义缓存的x m l 查询处理技术的研究与实现第三章语义缓存技术概述 3 2 语义缓存的主要技术 语义缓存技术的价值主要体现于它能在网络通信能力较弱的环境下进行快速查 询求值，并为用户返回查询结果，但这个价值又是以语义缓存自身数据管理和维护的 内耗为代价的，即缓存替换策略和一致性等数据维护管理工作。从语义缓存技术的价 值和内耗展开，目前语义缓存的研究领域主要分为两个方面【”1 ：一是属于语义缓存技 术价值范畴的研究，主要是对语义缓存查询处理策略和方法的研究；二是属于语义缓 存技术内耗范畴的研究，主要包括对语义缓存替换策略和一致性等数据维护管理策略 的研究，而这两方面的研究，都是以一定的语义缓存存储模型为基础的。 3 2 1 语义缓存的数据模型 与传统的元组缓存和页面缓存不同，语义缓存的数据模型不再是大小固定的元组 或页面，而是由查询语义描述构成的查询语义特征【2 8 1 ，而语义缓存数据模型就是泛指 缓存对查询结果数据及语义描述的存储机制，当前有两种方法比较流行【2 7 1 ：一种是基 于集合论进行形式化定义，我们称之为逻辑模型，逻辑模型形式化地描述了语义缓存 中包含的数据和语义，以及这些被包含项之间的逻辑关系：另一种是直接给出语义缓 存的物理存储机制，我们称之为物理模型，物理模型有些是基于内存的，有些是基于 移动数据库的。 在关系数据领域，语义缓存的数据模型主要是针对s q l 查询语言的特征设计的， 因此通常使用逻辑模型来构建缓存的数据模型。通过对数据库和谓词等概念的定义， 一般用四元组 代表缓存中的一个s q l 查询，其中q r 表示该查询 所作用的数据库关系集合，q a 表示该查询所投影的属性集合，q r 和o a 有时也合起 来表示为一项，q p 表示比较谓词的合取，q c 表示该查询结果产生的析取范式定义； 对于查询结果记录集则用四元组 表示，其中s r ，s a 分别代表该查 询结果作用的关系和属性集合，s p 是比较谓词的合取，s c = zs ros p