（计算机软件与理论专业论文）基于前缀编码xml查询新策略的研究.pdf

山东大学硕士学位论文 摘要 x m l 正迅速取代h t m l 成为w e b 上信息表示、集成和交换的标准。与h t b i l 相比， x m l 具有简单、自我描述的特点，并且实现了内容、结构和表现三者的分离，更 适合于i n t e r n e t 上数据表示和交换。近年来，x m l 在各种领域得到了广泛的应用， w e b 上，信息系统以及电子商务中涌现了大量的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 数据查询所 需要的i o 时间和计算工作量增加。而前缀编码各段字典有序性，其编码算法比 较简单，不但可以很好保存双亲子女，祖先后裔结点之间的包含关系，更可以 保存x m l 文档中结点之间位置关系的信息，因而可以成为方便的比较x m l 文档中任 意两结点位置关系的工具。 利用前缀编码这些良好的特性，本文提出一个利用前缀编码来支持x m l 数据 查询的新策略。在这个策略中，本文提出一种最长前缀编码匹配的策略。对于基 于关系存储的x m l 数据，在其处理复杂路径查询表达式时，利用最长前缀编码匹 配算法，我们可以对x m l 数据查询中结构连接所得到的中间结果集合进行筛选， 通过最长前缀编码匹配策略直接得到) ( l 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 l d l 编码方案以及现有的几种典 山东大学硕士学位论文 型x m l 数据库技术。 关键词：x m l 查询，x m l 存储，d e w e y 编码，路径表达式 i i 山东大学硕士学位论文 a b s t r a c t x m li sb e c o m i n gt h ed ef a c t os t a n d a r df o ri n f o r m a t i o np u b l i c a t i o na n d e x c h a n g e o nt h ew e b ，s u b s t i t u t i n gf o rh t m l c o m p a r i n gt oh t m l ，x m li ss i m p l e ， s e l f - d e s c r i b i n ga n dt h ec o n t e n t ，s t r u c t u r ea n dr e p r e s e n t a t i o no fx m ld o c u m e n t sa r e i n d e p e n d e n t , w h i c hm a k e sx m lm o r es u i t a b l ef 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 e o nt h ei n t e m e t r e c e n t l y ，x m lh a sb e e nw i d e l yu s e di nv a r i o u sa p p l i c a t i o n s ，a n d v e r yl a r g ev o l u m e so fx m ld a t ah a v e b e e na p p e a r e di nt h ew e b ，i n f o r m a t i o ns y s t e m a n de b u s i n e s s t oo r g a n i z e ，m a n a g e ，s t o r ea n dq u e r yx m ld a t ae f f i c i e n t l yi s c o n c e r ni s s u e so fx m lr e s e a r c h d i f f e r e n tq u e r yl a n g u a g e sa n ds t o r a g ea p p r o a c h e s h a v e b e e np r o p o s eb yr e s e a r c h e r a sav i a b l ea n dp r o m i s i n ga p p r o a c h ，u s i n gr d b m st om a n a g ex m ld a t ai s e x t e n s i v e l ys t u d i e di nr e c e n ty e a r s h o w e v e r ，x m ld a t ao fr e l a t i o ns t o r a g en e e dt o c o n s t r u c ta n dc o n ju n c ti n t e r m e d i a t er e s u l t so fm u l t i p l es u b - i n q u i r ea td e a l i n gw i m x m lc o m p l i c a t e dp a t h w a ye x p r e s s i o nc o n s u l t a t i o n t h e r e f o r e ，i tn e e d st or e a l i z et h e d e f i n i t i o nc o n s t r u c t i o nr e l a t i o n s h i pa tm u l t i p l ec o r r e l a t i o nc h a r t s t h a tw i l ll e a dt o i n c r e a s eo ft i m ea n dc a l c u l a t i o nl o a do fx m ld a t ac o n s u l t a t i o n h o w e v e r ，p r e f i x e n c o d ei si ns e q u e n c e ，i t se n c o d i n gc a l c u l a t i o ni sc o m p a r a t i v e l ys i m p l e i tc a l ln o t o n l yp r e s e r v et h ec o n t a i n i n gr e l a t i o n sb e t w e e np a r e n t s c h i l d r e n ，a n c e s t o r d e s c e n d a n t c o n j u n c t i o n ，b u ta l s oi tc a nk e e pt h ei n f o r m a t i o no fp o s i t i o nr e l a t i o n so fx m lf i l e s i t c a nb eac o n v e n i e n tt o o lt oc o m p a r ea n yt w oju n c t i o nr e l a t i o n s h i p w ep u tf o r w a r dam e t h o dt os u s t a i nx m ld a t as e a r c hw i t ht h e g o o d c h a r a c t e r i s t i c so fp r e f i xc o d e i nt h en e wm e t h o d ，w ep r e s e n tt h el o n g e s tp r e f i xc o d e m a t c h i n g f o rt h ex m ld a t ao nt h eb a s i so fr e l a t i o n s h i p ，w h e nw ed e a l 嘶t hc o m p l e x p a t hs e a r c he x p r e s s i o n ，w ec a nf i l t r a t ef r o mt h er e s u l t so fs t r u c t u r el i n ka n do b t a i nt h e f i n a lr e s u l t su s i n gt h el o n g e s tp r e f i xc o d em a t c h i n g c o m p a r e dt ot h et r a d i t i o n a lx m l m e m o r ys e a r c hm e t h o do nt h eb a s i so fr e l a t i o n s h i p ，o u rm e t h o di sm o r ee f f e c t i v e w h e nw ed e a lw i t hc o m p l e xx m l p a t hs e a r c h 山东大学硕士学位论文 t oi m p r o v es e a r c hx m ld a t au s i n gt h el o n g e s tp r e f i xc o d em a t c h i n gm e t h o d a c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft w os t a g e si nx m lp a t hs e a r c he x p r e s s i o n ，w ea l s o p r e s e n tt w od i f f e r e n tp a t t e r n so fx m ld a t am e m o r ym e t h o d s a n dw ed e s c r i b et h e s p e c i f i cs e a r c hp r o c e s so fx m ld a t a , c o m p a r ew i t hc a p a b i l i t yo fo t h e rm o d e l s ，a n d i n t r o d u c et h ee x p e r i m e n tp r o c e s sa n dr e s u l t s t ou n d e r s t a n dt h et e x tb e t t e r , w ea l s o s i m p l yd e s c r i b et h er e l a t e dk n o w l e d g ea n dt h e o r yt ox m l ，x m ls e a r c ht e c h n i q u e s ， x m l c o d i n gm e t h o d sa n ds e v e r a lt y p i c a lx m l d a t a b a s et e c h n i q u e s k e y w o r d s ：x m lq u e r y ，x m ls t o r a g e ，d e w e yc o d e ，p a t he x p r e s s i o n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 圣这 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：豇导师签名：篮e t 期：竺! 篁! 坠日 山东大学硕士学位论文 1 1 本文研究背景 第一章绪论 随着网络技术的不断发展，越来越多的信息资源可以通过网络得到更广泛的 应用。w e b 己经成为信息制造、发布、加工和处理的主要平台。由于h t m l 语言仅 注重信息的表现形式，它的标记仅仅反映了信息应该如何在页面上表现，而没有 对信息本身进行描述，并不能够表示数据和管理数据。数据的内容和网页的显示 没有分离，不能满足搜索、数据交换、自适应表示和个人化的标准、扩展性以及 自适应检查功能的要求。同时它的标记集合是固定的，不能够根据需要进行扩展， 因此给信息的表示，交换和存储带来了较大的局限性，随着w e b 应用的日益广泛， 它的局限性越来越明显。而x m l 语言的出现为信息交流带来极大的便利，由于 x m l 数据具有自描述特点，可以支持用户自定义的标记，符合i n t e m e t 上数据描 述和存储的需求，所以近年来i n t e m e t 上信息的表示和存储越来越多地向x m l 格 式迁移，x m l 也正在逐渐成为i n t e m e t 上数据表示和数据交换的事实上的标准。 随着x m l 格式信息的规模和复杂性的快速增长，以x m l 格式表示和存储的数据 得到t i n t e m e t 领域和数据库领域研究人员的重视。i n t e m e t 上的应用对x m l 数据 的查询、定位和获取的需求不断增加，也引发了对x m l 数据进行合理存储和快 速查询的要求。 i n t e r n e t 发展的今天，x m l 和数据库的关系也业已密切，如何有效地存储和 查询x m l 数据成为当前研究的一个热点。在存储和查询x m l 数据这一领域，目前大 致主要分为两种方法：第一种存储方式就是为x m l 数据本身量身定做的数据库即 纯x m l 数据库 1 ( n a t i v ex m ld a t a b a s e ) ，它为x m l 文档定义了一个逻辑上的模 型，x m l 数据的存储和查询都基于这个模型。这个模型至少要包含元素，属性以 及p c d a t a 等，并保持文档顺序；将x m l 文档作为逻辑存储的基本单位，正如关系 数据库系统将元组作为存储的基本单位一样：不要求只能使用某一特定的底层物 理模型或某种专有的存储格式。因此纯x m l 数据库充分考虑到) ( m l 数据的特点，以 一种自然的方式来处理x m l 数据，能够从各个方面很好的支持x m l 的存储和查询， 并且能够达到较好的效果，但是，纯x m l 数据库要走向和关系数据库那样成熟还 山东大学硕士学位论文 有很长的路要走；另一种存储方式是在已有的关系数据库系统或面向对象数据库 系统的基础上扩充相应的功能，使其能够胜任x m l 数据的处理要求，这种数据库 又称为x m l 使能数据库 2 ，3 ，4 0 ( ) ( m le n a b l ed a t a b a s e ) 。目前，x m l 使能数 据的研究主要是基于关于关系数据库系统。这种方法的优点是可以充分利用已有 的非常成熟的关系数据库技术，集成现有的大量存储在关系数据库中的商用数 据。但是目前这种处理方法不能利用x m l 数据自身良好的优点，如半结构化 1 8 等，并且在查询时，由于x m l 数据查询结构化 5 的特征，使得基于关系数据库存 储的x m l 查询需要在较多的表上进行连接 6 ，使得查询的响应时间不能很好的满 足客户的要求。 将x m l 数据转化为关系数据，存储在关系数据库系统中，利用已经成熟的关 系数据库理论和技术，来实现对x m l 数据的存取和访问，并尽量减少x m l 数据查询 时的中间操作，以提高查询效率。本文正是基于此背景写出的。 1 2 国内外研究现状 因为x m l 成为信息表示和交换的事实上的标准，x m l 的应用也越来越广泛，关 于其存储和查询的问题也越来越受到关注。国内外大量的企业和研究机构的研究 人员，在x m l 数据的存储和查询方面做了大量的工作，取得了很多有意义和富有 成效的结果。 t a m i n o 7 是第一个商用的纯k m l 数据库系统，它的技术资料还不多见。从文 献 8 中可以得知它的数据存储采用的是一种称之为“a d a b a s 的可嵌套的关系 引擎的改进版本，它的主要创新之处在于其索引结构，模式信息处理和w e b 接口。 t i m b e r 9 是一个底层采用面向对象数据库s h o r e 的x m l 数据库，它很好的借 用了s h o r e 系统本身具有的良好的存储管理，缓冲机制和并发机制等，它的数据 存储粒度是结点级的，在重组文档时可以避免不必要的转换和结构。 s t a n d f o r d 大学开发的x m l 数据库l o r e 系统 1 0 针对系统本身提供的访问操 作和索引情况，提出了一套独特的代数操作，包括逻辑代数，物理代数和相应的转 换规则l o r e 的存储管理策略很简单，首先将x m l 数据分解为一些基本的要素 ( e l e m e n t ) ，属性和文本字符串，采用直接深度优先聚集方法进行物理存储。l o r e 将对象组织在物理磁盘页上，每个页上有很多的槽( s l o t ) ，每个槽中有一个单独 2 山东大学硕士学位论文 的对象。l o r e 支持跨越多个页的大对象，对多媒体类型是有用的。采用深度优先 的方法将对向聚集在页上，这主要是由于系统采用深度优先的数据库策略。当一 个对象有多个父对象时，它与任一父对象聚集在一起。查询计划生成器将这个查 询生成一个查询计划，并将这个查询计划提交给查询优化器。优化器需要对执行 计划进行一些变化并确定一些索引的使用，最后将优化后的执行计划提交给数据 引擎层处理。数据引擎层由o e m 对象管理器、查询操作执行部分、外部数据管理 器和其他的工具组成。查询操作执行部分主要完成上一层提交的查询执行计划。 对象管理器用来完成o e m 与底层文件结构的映射。它支持基本的原语，如取一个 对象，比较两个对象等。 中国人民大学孟小峰教授等历时2 年多研究开发的x m l 数据库系统 o r i e n t x 1 l ，2 5 ，3 3 是国内第一个纯x m l 数据库系统，它的纪录级别是文档级的， 按物理块划分，使记录之间联系的指针得以减少，消除了较多的冗余空间，提高 了存储效率。实现了以语义相近的记录尽量聚集存储的按逻辑意义存储策略，判 断语义相近的方法是根据记录类型是否相同。 复旦大学的v x m l r 系统 1 2 把x m l 文档存储到关系数据库中。v x m l r 系统先把 x m l 模式映射为关系模式。然后把数据x m l 文档存入关系数据库中。查询时，先把 x m l 查询语言重写为s q l 语句，最后把查询结果重构为x m l 文档。 另外，文献 1 3 还提到d b d o m ，e x i s t 2 4 ，x d b 等构建在关系数据库上x m l 数据 库系统。 1 3 论文的主要工作和组织结构 本文提出了一种基于关系数据库系统存储的新的x m l 查询策略。由于x m l 数据具有半结构化的特点，对x m l 文档查询的关键部分是对元素之间结构关系的 判断，例如父子祖先关系，左兄弟右兄弟关系等。对于这种x m l 结构查询的 计算，一种实现方法是建立x m l 文档树的路径索引，并通过路径索引来加速 x m l 结构查询的计算。另一种方法是对x m l 文档树的结点进行编码，通过编 码直接判断结点之间的结构关系。在以前的研究文献中可以看出，这些编码方案 在处理包含分支谓词的复杂查询时，要对所涉及的所有中间结果集上的结点编码 作数值上的比较来确定最终的结果。这时需要涉及到多个表。而前缀编码不仅保 3 山东大学硕士学位论文 持了结构关系上的信息，还保存了整个文档的位置关系，利用这种性质，我们提 出了一个利用前缀编码对复杂分支查询中间结果的筛选策略，以便选出符合条件 的结果集，并针对这个策略提出了相应的存储结构。 本文是按照以下结构组织的： 第二章介绍了x m l 相关知识和理论，包括x m l 语言的特点，与h t m l 相比有利于 信息表示传输的优点，然后介绍了第四部分涉及到的x m l 应用技术，比如x m l 文档 树模型，x m l 查询语言包括x q u e r y ，x p a t h ，以及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 查询的有效性进行了 验证。 第六章对全文的工作进行了总结，并对未来下一步工作进行展望。 4 山东大学硕士学位论文 2 1x m l 语言介绍 第二章x m l 相关理论 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展标记语言) 是由w o r l dw i d ew e b c o n s o r t i u m ( w 3 c ) 的x m l 工作组定义的。这个工作组是这样描述该语言的：“x m l 是s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记语言) 的子集， 其目标是允许普通的s g m l 在w e b 上以目前h t m l ( h y p e rt e x tm a r k u pl a n g u a g e ) 的方式被服务、接收和处理。x m l 被设计成易于实现，且可在s g m l 和h t m l 之间相 互操作。 x m l 是一套定义语义标记的规则，这些标记可将文档分成许多部件并对这些 部件加以标记。它不像h t m l 或格式化程序。这些语言定义了一套固定的标记，用 来描述一定数目的元素。x m l 是一种元标记语言，用户可以定义自己需要的标记。 这些标记必须根据某些通用的原理来创建，x m l 标记描述的是文档内容的结构和 含义，而不是描述页面元素的格式化。文档本身只说明文档包含什么标记，而不 是说明文档看起来是什么样子的。 x m l 文档的准确含义见万维网联盟( w 3 c ) 发表的x m l 文档规范 h t t p ：w 、i n v w 3 o r g t r r e c - x m l 。这个规范详细定义了x m l 文档是什么和不是 什么。x m l 文档应有一个根元素，所有开始标志要有相应的结束标志，所有属性 只要放在引号中，文档中只能使用x m l 中合法的u n i c o d e 字符。简单的说，一个x m l 文档主要有以下几个部分构成： x m l 声明 如在图2 1 中的第一行 就是 一个x m l 声明。这是x m l 规范中所必须有的，并且必须要放在第一行，其中的字 母是区分大小写的，表示程序以此句为开头。x m l 声明主要包括两个部分：一是 x m l 的版本号，如图2 - 1 示例中的v e r s i o n = ”1 0 ”；二是文字编码声明，如图 2 - 1 中的e n c o d i n g = ”i s o 一8 8 5 9 - 1 ”，要放在版本声明之后。 山东大学硕士学位论文 图2 1x m l 文档 元素 通常，元素组成了) ( m l 文档中的大部分内容。元素由一对标记( 开始标记和结 束标记) 和字符数据组成，开始标记的形式为 ，结束标记的形式为 ，字符数据位于开始标记和结束标记之间。如果元素没有字符数据，则成 为空元素，空元素可以用一种速记法来表示，即 。 属性 6 山东大学硕士学位论文 属性通常用来给元素提供所表示内容的额外信息。元素的属性在元素的开始 标记中给出，形式为“属性名= 属性值”，属性值必须出现在单引号或者上引号 中。一个元素可以有任意数目的属性，但是它们的名称不能相同。 处理指令 处理指令通常用来为处理x m l 文档的程序提供信息，这些信息包括如何处理 文档、如何显示等。在图2 - 1 中没有用到处理指令。 注释 x m l 支持注释。注释分别使用字符序列“ ”和” ”作为开始和结 束，注释的文本内容在这两个字符序列之间 除了上面的五个部分，一个x m l 文档还包括命名空间等。 2 2x m l 的优势 x m l 之所以成为事实上的网络数据表示标准，是因为它具有其它表示方式 所不具备的特点，主要包括： 1 x m l 是自描述的。 x m l 最大的能力来源于它不仅允许定义自己的一套标记，而且这些标记不 必局限于对于显示格式的描述。 2 x m l 具有集成数据和文档的能力。 大多数语言或者在表示严格的、绝对的内容和数据结构上设计得好一点，或 者在表示灵活的、自由形式的文档文本上设计得好一些，而x m l 在两个方面都 做得很好。它能表示数据和自由格式的文本，也能在同一个文档上做到这两个方 面。 3 x m l 具有相当的表现力和可扩展性。 实际上，我们可以在所选择的主题上表述任何想表述的内容。它具有一致的 语法，这使得它很容易被解析。 4 x m l 用一种灵活的可扩展的表示来实现内容通信。 x m l 允许开发各种不同专业( 如音乐、化学、数学等) 的特定领域的标记 语言。有了这些语言，这个领域的实践者们可以相互自由的交换短文、数据和信 息，而不必担心对方是否利用特殊的、专用的软件来创建数据。事实上，目前已 7 山东大学硕士学位论文 经开发出了一些特定领域的标记语言，如m a t h m l ( 用于数学领域的一种标记语 言) 。这样，非常复杂的领域可以使用x m l 很好的合理的表示出来。 5 x m l 是非专有并易于阅读和编写的。 这使得x m l 成为在不同应用间交换数据的理想格式。 正是由于具有上述的这些优点，x m l 作为网络上的数据表示方式为人们所 接受和使用，并迅速普及，成为事实上的网络上的数据表示标准。 2 3x m l 文档树 本文使用的文档树模型是由b r u n o 提出的 1 】。根据模型理论定义，x m l 文 档定义为一棵有根并且有序的标签树。x m l 文档中的元素，属性和数据值都表 示为文档树中的结点，其中属性使用 前缀标识以和元素加以区别；元素与子元 素之间，元素和属性之间，元素和数据值之间以及属性和数据值之间的关系表示 为文档树中边。图2 2 为图2 1 所对应得文档树模型。 2 4x m l 查询语言 图2 2x m l 文档树 在x m l 出现的早期，x m l 使用者就意识到了查询语言 1 5 ，1 8 的必要性。为了 达到这个目的，w 3 c 提出了多种查询语言，其中最重要的有两个：x p a t h 和x q u e r y ， 山东大学硕士学位论文 其它的还有q u i l t ，x m l q l 等。 2 4 1x q u e r y x q u e r y 是w 3 c 的一个推荐规范，它在2 0 0 1 年被首次推出，并在随后做了几次 更新。关于x q u e r y 的一个比较恰当的定义是：”x q u e r y 是定义为对x m l 数据集进行 查询，x m l 数据不仅指x m l 文档，还指一切看起来像x m l 的数据，包括关系数据库 中的数据。”x q u e r y 对于x m l 数据，就像s q l 对于关系数据库中的数据一样 1 0 。 下面，以x q u e r y 中具有典型代表性的f l w o r ( 读作f l o w e r ) 表达式为例，来介绍使 用x q u e r y 如何对x m l 数据进行查询。 f l w o r 表达式是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 l w o r 代表f o r ，l e t ，w h e r e ，o r d e r 和r e t u r n 表达式。每一个f l w o r 表达式都有一个或多个f o r 子句、一个或多个l e t 子句、一个可选的w h e r e 子句和一个r e t u r n 子句。对图2 - 1 中的x m l 文档 a r t i c l e s x m l ，给出一个f l w o r 查询的例子如下所示： 图2 3x q u e r y 查询语言 9 山东大学硕士学位论文 该查询的功能是查询b i b a r t i c l e 下的t i t l e 元素。 上面的查询中用到了f l w o r 表达式中的f o r e , r e t u r n 两种子句。有关x q u e r y 查询的其他知识，可以参考有关的w 3 c 规范。 2 4 2x p a t h x p a t h 的最新版本是由w 3 c 在2 0 0 5 年发布的2 0 版工作草案，它是x q u e r y 的一 个关键组件，在x q u e r y 中模式匹配的工作是由x p a t h 的路径表达式实现的。单独 的x p a t h 路径本身就是完全有效的x q u e r y 语句，两种语言有相同的公共数据模 型。基于以上情况，本文将重点介绍x p a t h 。 在x p a t h 语言中，把x m l 文档看成是带有各种结点的文档树结构来访问。使 用x p a t h 可以定位x m l 文档树的任意结点。x p a t h 的使用方式是：通过路径表达 式，匹配x m l 文档中的不同部分。路径表达式提供了许多选项用于在x m l 文件内 部定位。x p a t h 的主要构件是路径表达式，其中，最重要的表达式是定位路径 ( l o c a t i o np a t h ) 表达式，这也是它为什么命名为x p a t h 的原因。定位路径表达式 是这样一种类型的表达式：p u b b o o k a u t h o r 。粗看起来，定位路径表达式很像文 件系统中的路径。定位路径的思想和文件系统中的路径确实很相似，当然，定位 路径要更复杂一些。定位路径有两种，分别是相对的定位路径和绝对的定位路径。 每种定位步都是由一个或多个定位步组成，每个定位步之间用正斜杠( ) 分开。 绝对路径以正斜杠( ) 开始，而相对路径则没有。x p a t h 中用上下文结点集合上 下文结点来描述定位路径的求值过程是如何进行的。上下文结点集定义为：表达 式中给定点确定的当前结点集；而上下文则定义为：正在处理的当前结点。定位 步按照顺序从左到右一次一个地求值。 一个定位路径由若干个定位步组成，而一个定位步有三个部分： 一个轴，它指定了定位步选择的结点与上下文结点之间树状关系； 一个结点测试，它指定定位步选择结点的结点类型以及结点扩展名； 零个或零个以上的判定词谓词，它使用专有的表达式进一步细化定位步选择 的结点集合。 下面介绍说明一下本文中常用的几个语法，具体来说，如果路径以斜线开 始，那么该路径就表示到一个元素的绝对路径；如果路径以双斜线开头，则表 1 0 山东大学硕士学位论文 示选择文档中所有满足双斜线2 _ 后规则的元素( 无论层级关系) 。 1 a r t i c l e 选择所有a r t i c l e 元素 实际是指返回a r t i c l e 所在的x m l 片断( 子树) ，而不是单纯的一个元素，此 处a r t i c l e 在哪个层次都可以。 2 a r t i c l e a u t h o r 选择所有父元素是a r t i c l e 的a u t h o r 元素。 3 星号 表示选择所有由星号之前的路径所定位的元素。 4 属性： a r t i c l e i d 】：选择有i d 属性的a r t i c l e 元素。 虽然针对x m l 有很多种查询语言，包括上面介绍的x q u e r y 和x p a t h ，但是 它们的核心内容都是类似于x p a t h 的路径查询表达式 2 7 】，在第三章我们将以路 径查询表达式的复杂程度对查询模式进行分类讨论。 2 5x m l 查询树模式 文中的算法还需要用到x p a t h 查询树模式。x p a t h 路径查询可以描述为一棵 查询树，称为x p a t h 树模式。其形式化的描述如下 定义2 1 查询树模式 针对x m l 数据的路径查询可以表示为一棵查询树q = e ，r o o t ，p r e d i c a t e ) ，v 是树中结点的集合，r o o t 是查询树的根。e 是树中结点之间边的集合。边分为两种， 分别表示父子包含关系和祖先后代包含关系，即和；除了根结点之外， 函数p r e d i c a t e 赋给查询树中的每个结点一个谓词条件【】，该条件针对元素的名字、 属性值及文本值等。 在实际的查询树中，往往只有一个结点在数据中的映射结点是查询需要的输 出结果，其余结点之间的边只是对该结点的条件约束。基于这样的考虑，本文给出 如下的一些定义。 定义2 2 返回结点 x m l 查询树中存在一个结点n ，它在数据中的映射是查询的最终输出结果， 该结点称为查询的目标结点或者返回结点。 山东大学硕士学位论文 定义2 3 查询的主路径 在x m l 查询树q 中，从根结点到目标结点之间的路径称为查询的主路径。 其中，x p a t h 查询中“ 的个数表示其层次数。 定义2 4 分支结点 在x m l 查询树q 中，孩子结点数目大于1 的结点( 即出现路径分叉的结点) 称为分支结点。 定义2 5 谓词子树 在x m l 查询树q 中，如果结点上除了针对元素名的谓词条件外，还定义了 针对元素值或元素属性值的谓词条件，这样的结点称为值谓词结点，这类谓词条 件所在的子树称为谓词子树。 生成方法： 1 查询树模式中边对应于x p a t h 中的每一个路径符号( “”或者“”) 。 2 查询树模式中的结点对应与x p a t h 中的每一个标签符号。 3 如果一个标签带有一个选择条件( 即ov ) ，那么将0v 作为一个整体也生 成一个标签，附属在原标签上。 举例说明：查询q = a v = ”s ”i b x 1 2 0 0 d = t c 。对应的查询树模式如下 图，其中查询的返回结点是c ，查询主路径是l a b l c ，存在多个分支结点，如a ，b ； 上述查询中出现了4 个谓词结点，谓词子树： 1 2 山东大学硕士学位论文 2 6 本章小结 图2 4x m l 查询树 本章介绍了x m l 相关知识与理论，包括x m l 语言的特点，与h t m l 相比有利于信 息表示传输的优点，然后介绍了第四部分所要涉及到的x m l 应用技术，比如x m l 文档树模型，x m l 查询语言包括x q u e r y ，x p a t h ，以及x m l 查询树模型的概念。通 过这一章叙述希望对x m l 及相关技术有了一个大致的了解，以更好的理解本文提 出的策略理论。 山东大学硕士学位论文 第三章x m l 数据库技术 3 1x m l 数据的编码方案 对x m l 数据的查询，特别是使用x p a t h 查询语言，实际上是利用给出的查询路 径表达式，在目标x m l 文档模式树上进行导航，最终得到查询的目标结点。在这 个查询过程中，必然包括了对祖先后裔，双亲孩子等包含关系以及之前之后， 左兄弟右兄弟等文档位置关系的结构查询，而这些x m l 文档上的结构查询将会导 致结构连接 2 l ，3 0 ，2 6 的计算。为了有效的支持x m l 查询，特别是结构查询，研 究者提出了) ( m l 数据的各种索引技术 3 1 ，3 9 和编码方案 2 4 ，2 8 。对于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 文档嵌套结构，给从文档根结点开 始所能到达的每个路径元素和元素结点赋予一个编码。目前已经提出的编码方案 主要包括：位向量编码 1 7 ( b i t - v e c t o re n c o d i n g ) ，区间编码 2 3 ( r e g i o n e n c o d i n g ) ，二叉树编码 4 ( p b i t r e ee n c o d i n g ) 和前缀编码 2 9 ( p r e f i x e n c o d i n g ) 。 位向量编码 x m l 文档树t 中的每一个结点被编码为一个n 位的向量，n 是树t 中的结点数量， 在某个位置i 上的一个“1 ”位惟一的标示第i 个结点；并且在一个自顶向下的( 或 自底向上) 的编码方案中，每一个结点继承标示它祖先( 或后裔) 的所有位上的 1 4 山东大学硕士学位论文 “1 。对于继承祖先的位向量编码，利用二元位运算a n d ( ) ，能够快速的检测 一个结点u 是否为另一个结点v 的祖先。位向量编码能够有效支持包含关系得计 算。 区间编码 x m l 文档树t 中的每一个结点被赋予一个区间编码 s t a r t ，e n d ，并且满足： 一个结点的区间编码包含它的后裔结点的区间编码。也就是说，树t 中的结点u 是结点v 的祖先，当且仅当s t a r t ( u ) ( s t a r t ( v ) 八e n d ( v ) ”或“ ”操作符的连接) 的问题然后用这一祖先集上的等值 1 9 山东大学硕士学位论文 连接取代e 连接。然而，这一方法相对于原始文档将导致数据规模爆炸性增长， 关系连接的数量也非常大。x p a r e n t 在查询表达式中需要将l a b e l p a t h ，d a t a 和 a n c e s t o r 表连接起来。这些连接的代价相当昂贵，特别是在连接a n c e s t o r 表时。 3 3 本章小结 本章介绍了主要介绍了x m l 文档的四种编码方案的介绍，位向量编码，区间 编码，二叉树编码$ 1 3 d e w e y 编码。在介绍中给出以上编码对x m l 文档结点位置关系 的比较方法并说明各种方案的优缺点。然后介绍了基于关系模式的x m l 数据存储 方案。虽然，目前关系数据库系统使用广泛，数据处理能力强，查询性能好，但 是由于x m l 数据查询中结构查询的特点，关系数据库在处理x m l 数据查询时还存在 着很多不足，针对这些不足，本文提出了一种利用前缀编码支持x m l 查询的策略， 下一章将给出详细的描述。 山东大学硕士学位论文 第四章利用前缀编码的x m l 数据查询策略 在上一章介绍中可以看到，关系数据库由于其使用广泛，数据处理能力强， 查询性能好，基于关系数据库模式存储处理x & i l 数据模型的成为商业和研究领域 关心的热点。但是由于x m l 数据查询结构化的特点，在关系模式上进行结构查询 往往要涉及多个关系表，在多个关系表作连接，增加了数据查询的计算量和响应 时间。因此，如何有效的判断x m l 文档中结点之间的相互位置关系，以便减少结 构查询中计算量，达到满意的查询时间要求就显的尤为重要。在各种编码方案中， 前缀编码不仅能够保存x m l 文档中结点之间的如双亲孩子，祖先后裔这样的包 含关系，更保存了之前之后，左右兄弟这样的x m l 文档结点之间的位置关系。 因此本文提出了一种利用前缀编码对基于关系存储的x m l 数据进行查询的策略， 采用这种策略，可以减少复杂路径表达式查询中结构查询的计算量，从而提高x m l 数据的查询效率