（计算机软件与理论专业论文）一种新的纯xml数据库索引机制.pdf

论文题目：一种新的纯x m l 数据库索引机制 专业：计算机软件与理论 硕士生：黄国强 指导教师：李才伟副教授 摘要 随着x m l 应用的普及，对x m l 文档查询的要求也就越来越高。如果不对 x m l 文档建立索引结构，那么针对x m l 数据的任何查询都很可能导致对整个 文档树的遍历。随着x m l 数据集的增大，这种遍历所花费的开销是不可忍受的， x m l 索引结构的提出正是为了提高查询的效率，在速度与准确性两方面为查询 提供更大的灵活性，通过减少访问那些与查询不相关的数据集来实现快速查询。 本文在结合x i s s 系统和l s d x 编码方法的基础上，提出一种新的索引机制 i m d x ( i n d e x i n gm e c h a n i s mf o rd y n a m i c a l l yu p d a t i n gx m ld a t a ，支持动态更 新x m l 数据的索引机制) 。该索引机制引入了一种新的编码方法，对x m l 数据 树的每个结点进行唯一编码。通过结点的编码，可以快速地得到任何两个结点间 的关系。i m d x 在结构上由元素索引，属性索引，名字索引和值索引组成，通过 这些索引，我们可以由元素或属性的名字快速地得到同名元素或属性的结点。对 于给定的路径表达式语句，采用分解的方法分成足够小的查询单位，再对它们根 据结点间的关系进行连接，最后得到查询结果。 本文的创新点主要体现在以下几个方面：提出了一种新的对结点进行编码的 方法，有效地解决已有的x i s s 系统中不完全支持结点更新的问题。并给出了一 次遍历就可以建立索引的算法，提高了索引建立的效率。从结点的编码中可以判 断出结点的路径，从而简化了索引机制，减少了索引文件占用的空间。对传统的 路径连接算法进行了改进，解决了路径连接时将无用结点也参与连接的问题，从 而提高计算和存储效率。 通过实验，我们把i m d x 系统和x i s s 系统进行了比较，i m d x 不仅比x i s s 系统更好地支持结点的更新，而且索引的建立时间和查询的复杂度都得到很好的 改善。 关键词：纯x m l 数据库，x m l 索引，编码方法，数据检索 t i t i e ：an e wi n d e xm e c h a n i s mf o rn a t i v e x m ld a t a b a s e m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：g u o q i a n gh u a n g s u p e r v i s o r ：c a i w e il i a b s t r a c t a st h ea p p l i c a t i o no fx m li su s e dm o r ea n dm o r ew i d e l y , t h er e q u i r e m e n to f x m l q u e r yi sh i g h e ra n dh i g h e r a n yq u e r yo nx m l d a t am a yc a u s et h et r a v e r s i n go f t h ew h o l ex m ld o c u m e n tt r e e ，i ft h e r ei sn oi n d e xs t r u c t u r ei nx m ld o c u m e n t a s t h ex m ld a t as e tb e c o m el a r g e ra n dl a r g e r , t h ec o s to ft h i s t r a v e r s i n gm a yb e i n s u p p o r t a b l e t h ei n d e xs t r u c t u r ew a sp r o p o s e dj u s tt oi m p r o v et h ee f f i c i e n c yo f q u e r y , m a k ei tm o r ef l e x i b l ei nb o t hs p e e da n da c c u r a c y , a n dq u i c k e nt h eq u e r yb y r e d u c i n gt h ea c c e s so fi r r e l e v a n td a t as e t t h i s p a p e rp r o p o s e si m d x ( an e wi n d e x i n gm e c h a n i s mf o rd y n a m i c a l l y u p d a t i n gx m ld a t a ) b a s e do nx i s sa n dl s d x i tr a i s e san e wc o d i n gm e t h o dt o g i v eau n i q u ec o d eo rl a b e lt oe v e r yn o d eo ft h ex m lt r e e t h r o u g ht h i sc o d e ，w ec a n g e tt h er e l a t i o n s h i pb e t w e e na n yt w on o d e s i m d xi sc o n s t i t u t e db ye l e m e n ti n d e x ， a t t r i b u t ei n d e x ，n a m ei n d e xa n dv a l u ei n d e xi ns t r u c t u r e t h r o t l ：g ht h e s ei n d e x e s ，w e m a yg e tt h ee l e m e n to ra t t r i b u t en o d e ss e tw i t ht h es a m en a m eb yt h e i rn a m e s a sf o r t h eg i v e np a t he x p r e s s i o n ，w ed e c o m p o s ei ti n t oq u e r yu n i t ss i m p l ee n o u g h ，a n dt h e n j o i nt h e mt o g e t h e rb yn o d e s r e l a t i o n s h i p ，a n dg e tt h eq u e r yr e s u l ts e tf i n a l l y t h ei n n o v a t i o n so ft h i sp a p e ra r ea sf o l l o w s ，f i r s t l y , w ep r o p o s e dan e wc o d i n g m e t h o d ，w h i c hs o l v e dt h ep r o b l e mi nx i s st h a ti tc a nn o ts u p p o r tt h ed y n a m i c a l l y u p d a t i n gx m ld a t ac o m p l e t e l y , a n dg a v eo u tt h ea l g o r i t h m st ob u i l dt h ei n d e x t r a v e r s i n gt h ex m l t r e eo n l yo n c e ，w h i c hp r o m o t e st h ee f f i c e n c yo fb u i d i n gi n d e x t h e nw es i m p l i f yt h ei n d e xs t r u c t u r ef o rw ec a ng e tt h ep a t hb yt h en o d ec o d e a n d t h e n ，w ei m p r o v eo nt h et r a d i t i o n a lp a t hj o i na l g o r i t h m s ，a v o i d i n gt h a ti r r e l a t e dn o d e s t a k ep a r ti nt h ep a t hj o i n i n g ，w h i c hi m p r o v e st h ec o m p u t ea n ds t o r ee f f i c i e n c y i i i t h r o u g ht h ee x p e r i m e n t ，c a m p a r e dw i t hx i s s ，i m d xn o to n l ys u p p o r t s t h e u p d a t i n gx m ld a t a ，a n dt h et i m ea n ds p a c ec o m p l e x e so fb u i d i n gi n d e xa n dq u e r y h a v e b e e ni m p r o v e dd i s t i n c t l y k e yw o r d s ：n a t i v ex m ld a t a b a s e ，x m li n d e x ，n u m b e r i n gs c h e m e ，d a t a r e t r i e v a l 1 1 x m l 简介 1 引言 x m l 推荐标准1 0 版由w 3 c ( w o r l dw i d ew e dc o n s o r t i u m ，万维网协会) 发布于1 9 9 8 年2 月。之后，迅速在全球掀起了x m l 应用的浪潮。简要的讲， x m l 是一种描述型的标记语言，与h t m l 同为s g m l ( 标准通用标记语言，一 种十分强大但也非常复杂的标记语言，是i s o 8 8 7 9 国际标准) 的一种应用，到 目前为止，最新的推荐版本为1 1 “。设计之初，x m l 的目标之一就是取代h t m l 为新出现的复杂的w e b 应用提供标准的i n t e r n e t 语言。然而，由于x m l 在可扩 展性、可移植性和结构性等方面的突出优点，它的应用范围早已突破了h t m l 所达到的范围。 x m l 的主要特点如下【2 l ： 1 ) 可扩充性 s g m l 是一种具有高度可扩展性的开放的标记语言，x m l 也一样。x m l 提 供了一些基本的语法，但是没有定义确切的标记，标记集可以由任何人根据自己 的目的进行扩充。x m l 允许各种不同的专业( 如音乐、化学、数学等) 开发与自 己的特定领域有关的标记语言。这就使得该领域中的人们可以交换笔记、数据和 信息，而不用担心接收端的人是否有特定的软件来创建数据。 2 ) 较好的保值性 x m l 的保值性同样来自它的先驱s g m l 。s g m l 是一套有着十几年历史的 国际标准，它的最初设计目标之一是为文件提供5 0 年以上的寿命。x m l 在基本 水平上使用的是非常简单的数据格式。可以用1 0 0 的纯a s c i i 文本来书写，也 可以用几种其他定义好的格式来书写。a s c i i 文本是几乎不会“磨损”的。 3 ) 适合应用间交换数据 在现在的计算机世界里，不同的企业，不同的部门存在着许多不同的操作系 统和数据库系统。要想在这些不同的平台和数据库软件之间传递信息，不得不使 用一些特殊软件，很不方便。另外，从界面的角度，从工作站，个人微机到手机， 这些信息个性化的显示方式也很困难。有了x m l 之后，各种不同系统之间可以 采用x m l 作为交流媒介。这样就极大地方便了应用间的数据交换。 1 2 国内外研究现状 随着因特网和信息技术的高速发展，x m l 已经成为因特网上信息交换和表 示的重要标准，x m l 数据数量正在呈级数级增长，如何高效、系统、科学地管 理这些大规模的数据已经成为数据库研究领域中的一个重要课题。 传统的以及最有用的提高查询性能的技术是建立有效的索引。一个构建良好 的索引在查询时不需要对整张表进行查询就可以得到结果。目前已经提出的 x m l 的索引机制可以分为三类：基于路径的索引、基于序列的索引和基于联接 的索引。 1 2 1 基于路径的索弓 第一类是基于路径( p a t h ) 的索引，比如s t a n d f o r d 大学的l o r e 系统中的 d a t a g u i d e s 3 j 和基于t r i e 树的索引i n d e xf a b r i c 。通过路径表达式进行查询一直 是x m l 文档索引和查询研究领域内主要的研究焦点之一。 d a t a g u i d e s 的工作原理是，首先从x m l 文档中抽象和概括出文档的结构， 并通过这种结构加速x m l 查询过程。使用结构指导查询处理，这也是d a t a g u i d e s 名称的由来。如图1 - 1 ，通过数据源( a ) ，可能得到( b ) 或( c ) 两种d a t a g u i d e s 。 路径索引处理简单路径查询有非常高的效率。但它不能很好的支持分支查询 和带有通配符的查询。可以采取一些改进的策略来解决这个问题，但那样往往使 索引结构过大，以至于不能高效的执行查询。 2 1 2 2 基于序列的索弓 灾 ab 审审 cc 0 il d 6 d 6 ( 8 ) b ) 图1 - 1 数据源及其对应的两种d a t a g u i d e s 第二类是基于序列的索引，如v i s t ( 卯，p r i x l 6 】和l m i x i ”。这种索引方法把 x m l 文档和查询表达式都转化成某种序列。然后通过子序列匹配，寻找数据库 中匹配的模式。比如在l m i x 系统中，我们把x m l 文档看作一条线，文档的每 个元素和值看作是线的子线段。如果按照文档序对元素和值进行编号，对于格式 正确的x m l 文档，每个元素和值都将得到一个由一个值对组成的区间 ，这样查询x m l 文档就等价于指定相应的匹配子线段。例如， 如图1 2 到图1 4 所示，假设有查询”n w e i n c ”，该查询的结果应该是区间 ， 。 刚啪 o v i 舶肾睁q 碌静胡泌一婚姘，范c 叫c h 瑚怿 图1 - 2 把x m l 文档看作是一个序列 宓一举。审。6 3 v 嘲，8 ， 图1 - 3 每个元素和值都赋予一个空间 1 2 3 基于联接的索弓 图1 4 利用模式匹配的方法进行查询 最后一种是基于联接( j o i 操作的索引方法。使用这种方法时，一个复杂的 路径表达式被分解成多个被称为原子表达式的基本路径表达式。通过访问索引结 构，可以直接得到原子表达式的查询结果。所有其他形式的查询表达式都包括联 接操作。x i s s 8 】和t w i g s t a c k 9 l 就是属于这种索引方法。 x i s s 首先对每个结点按( o r d e r , s i z e ) 编码，其中o r d e r 代表结点前序遍历的序 号，而s i z e 则表示这个结点最多有多少个孩子，这样我们根据任何两个结点的编 码就可以得到他们的关系( 如父子祖先后代关系) 。x i s s 的主要索引结构有元 素索引、属性索引和结构索引，其主要思想是将复杂路径查询分解为简单路径， 然后对各简单路径的处理结果进行联接。x i s s 对路径查询处理，无须遍历x m l 文档。 但是这种现有的设计存在这不足之处。首先，基于这种思想提出的快速确定 4 x m l 层次结构中，祖先，子孙关系的编号机制中很难再区分出父亲，孩子关系，因 此很难建立结构索引。其次，因为在简单表达式的进行连接操作时，同名元素或 属性的所有节点都参加连接。这其中无疑有很多是无用的结点，所以降低了索引 的效率。再次，虽然x i s s 的编码方案中，结点中的s i z e 值一般大于该结点实际 的孩子个数，从而相当于为以后结点的插入预留编码，在一定程度上支持结点的 更新操作，但是当孩子结点个数超过s i z e 值时，还是需要对所涉及的结点重新编 码。因而这它不是完全支持结点更新的编码方案。 1 3 本文研究内容 随着x m l 应用的普及，对x m l 文档查询的要求也就越来越高。如果不对 x m l 文档建立索引结构，那么针对x m l 数据的任何查询都很可能导致对整个 文档树的遍历。随着x m l 数据集的增大，这种遍历所花费的开销是不可忍受的， x m l 索引结构的提出正是为了提高查询的效率，在速度与准确性两方面为查询 提供更大的灵活性，通过减少访问那些与查询不相关的数据集来实现快速查询。 本文在结合x i s s 系统和l s d x ”编码方法的基础上，提出一种新的索引机 制，这种机制可以解决已有的x i s s 系统中存在的问题。本文的研究内容如下： 1 x m l 索引技术的研究。本文总结了主流的索引技术，分析了各种索引 技术优点和缺点 2 i m d x 文档编码方法的研究。对x m l 文档的结点进行编码可以使结点 问的结构化关系更加清晰而且容易判断。本文总结了几种主流的编码方 法，在此基础上提出一种新的编码方法。该方法可以支持结点更新的标 注编码方法和更新。这种编码方法有效地解决已有的x i s s 系统编码中 不完全支持结点更新的问题。 3 i m d x 索引机制的研究。本文对x i s s 系统的索引机制进行了改进，因 为采用了i m d x 编码方法，无需结构索引就可以知道结点间的关系和根 结点到给定结点的路径，简化了索引的结构。并从算法上解决了x i s s 系统路径连接时将无用结点也参与连接的问题，从而提高计算和存储效 率。 4 i m d x 索引机制解决了在x i s s 系统中，很难从一般的祖先子孙关系中 区分出父亲孩子结点，因而很难建立结构索引的问题。在本文提出的 i m d x 系统中，从结点的编码很容易得到结点问祖先子孙关系或父亲 孩子关系，从而提高了索引的效率。 5 对i m d x 索引机制进行了实现和性能分析。本文对提出的i m d x 进行了 实现，并与x i s s 系统做了比较。实验表明，除了在功能上增加了支持 结点的更新操作外，时问复杂度、空间复杂度和可扩充性等方面也得到 了提升。 在接下来的章节里，我们先介绍本文涉及的一些相关概念和技术，包括对 x m l 文档的分类和x m l 数据库的分类，常用的查询语言x q u e r y 和x p a t h 以及 x m l 索引技术的总结与分类，然后提出我们改进后的i m d x ( i n d e x i n g m e c h a n i s m f o rd y n a m i c a l l yu p d a t i n g x m l d a t a ) 编码方法，最后介绍我们i m d x 系统的原理 总体结构，并提供具体实现和性能分析。 2 1 订l 文档的分类 2 相关概念 x m l 本身为数据建模提供了很多的选择。r b o u t t e t i ”】曾经比较了两种不同 的建模思路：以数据为中心的文档和以文档为中心的x m l 文档。当然，处于这 两种极端文档格式之间的任何文档都是可能。 2 1 1 以数据为中心 ”以数据为中心”( d a t a c e n t r i c ) 的x m l 文档着重于文档中的数据，而非文 档格式，如航班信息、销售定单、科学计算结果等。这种文档的数据一般由机器 产生，来源于传统数据库中的数据。主要应用在电子商务、e r p 、e a i 等领域， 集成不同数据源的数据，交换信息。这种信息一般存放在关系数据库或面向对象 数据库中。 ”以数据为中心”的x m l 文档具有以下特点； 1 结构化的数据 2 数据粒度大小适中 3 很少或没有混和内容( m i x e dc o n t e n t ) 4 文档顺序( d o c u m e n t o r d e r ) 不重要 清单2 - 1s t u d e n t x m l 就是一个典型的”以数据为中心”的x m l 文档，记录了学 生的信息。每个学生的信息都很规整，而且粒度合适，同级元素( e l e m e n t ) f 司的顺 序不重要，交换两个同级元素( e l e m e n t ) 并不会破坏文档的可读性。 1 9 8 0 3 0 0 1 j o h n s o n j a c k j a c k i p e d o c o m | s t u d e n t 2 1 2 以文档为中心 清单2 - 1s t u d e n t x m l ”以文档为中心”( d o c u m e n t c e n t r i c ) 的x m l 文档主要是用来表示人类自然 语言描述的数据，如电子邮件、书和用户手册。这种文档具有更复杂的结构，一 般不是机器自动产生的。目前，w e b 上的大部分数据都可以表示成这种文档。 ”以文档为中心”的文档具有以下特点： 1 半结构化或非结构化的数据 2 较多的混和内容( m i x e dc o n t e n t ) 3 文档顺序( d o c u m e n t o r d e r ) 重要 清单2 2 就是典型的一个”以文档为中心”的x m l 文档。 t h e i p e d on a t i v ex m l d b f r o m i p e d o ，i n c i s l i k eat r u e n a t i v ex m l d a t a b a s e ， 2 2 x m l 数据库分类 清单2 - 2p r o d u c t s x m l 那么数据库在x m l 应用中的角色如何呢? 事实上，x m l 作为数据交换的标 准，更着重于统一数据格式，而不是提供数据库的特性。因此在x m l 应用中， 数据库作为数据管理的位置依然没有改变。 x m l 数据本身的树形结构不同于关系模型中的二维表结构，这种差别反映 在数据库产品处理x m l 数据的技术上，形成两大阵营：x m l 使能数据库和原 生x m l 数据库。 2 2 1x m l 使能数据库 x m l 使能数据库( x e d ，x m l - e n a b l e dd b m s ) 是在原有数据库基础上扩 展了x m l 支持模块，完成x m l 数据和数据库之间的格式转换和传输。从存储 粒度上，可以把整个x m l 文档作为r d b m s 表中一行，也可以把x m l 文档进 行解析为字段后，存储到相应的表格中，当检索x m l 时，这些字段再被拼接成 原状。为了支持w 3 c 的一些x m l 操作标准，如x p a t h ，x e d 提供一些新的原 语( 如o r a c l e 9 i r 2 增加了一些数据包来操作x m l 数据等) ，并优化了x m l 处理 模块。目前主流的关系数据库厂商，如i b m ，o r a c l e 和m i c r o s o f t 等，都在其新 的版本中增加了对x m l 数据的支持。 x e d 是基于人们熟知的而且是久经考验的传统的关系数据库，因此用户不需 将传统数据库中原有的数据重新移植到新系统中，只是稍加改变就可以支持 x m l 应用。另外，传统数据库的技术，如并发控制、事务等已经很成熟，而且 用户不必为了应用x m l 而再去学习一套新的数据库技术。但是，我们知道，x m l 最具吸引力的特性之一在于其分层结构，而关系数据库却将x m l 映射为关系表， 从而x m l 的结构变成了平面的行和列。而且，遇到大型的或复杂的文档时，在 x m l 与数据库之间进行来回转换要耗费相当多的处理时间，从而降低了数据的 存取速度。 2 2 2 原生x m l 数据库 1 9 9 9 年，s o f t w a r e a g 公司发布了纯x m l 服务器t a m i n o 的第一个版本，它 包括一个纯x m l 数据库。从那时起，“纯”( 或“原生”) 这个词变得非常流行。 原生x m l 数据库( n x d ，n a t i v ex m ld b m s ) 出现在x m l 数据处理领域 内，一般采用层次数据存储模型，保持x m l 文档的树形结构，省掉了x m l 文 档和传统数据库的数据转换过程。 对于”以数据为中心”的x m l 文档，x m l 使能数据库可以方便地将其中的数 9 据抽取，存储在传统数据库中，但对于”以文档为中心”的x m l 文档则显得力不 从心了。原生x m l 数据库由于无需在两种模型之间转换数据，因此在处理”以 文档为中心”的x m l 文档就很有优势。x m l 文档存取时无需进行模式转换，所 以存取速度快，特别是对于格式复杂的“以文档为中心”的x m l 文档。 原生x m l 数据库的商业产品以上面所说的t a m i n o 数据库为代表，t a m i n o x m l 服务器拥有一个内置的完整数据库系统，它提供事物处理、安全认证、并 发用户访问、可扩充性等功能。同时，t a m i n o 设计时充分考虑了x m l 操作的需 求：它支持有关的x m l 标准并为x m l 处理过程进行了优化。另外也有开放源 码系统，如e x i s t 1 2 】和x i n d i c e 1 3 】等。 2 3x m l 查询语言 面对着x m l 数据量级数级地增长，必然要求更有效的数据管理能力和更快、 更精确的查询。因此，如何从x m l 数据源中准确有效地查询所需信息，也变得 越来越重要。目前世界上仍然没有对x m l 查询进行标准化，但是w 3 c 正在进 行一种x m l 查询语言的定义工作。如x p a t h 和x q u e r y ，不过目前它们还处于草 案阶段。 x q u e r y 第一个公共工作草案在2 0 0 1 年2 月由w 3 c 的x m l 查询工作组完成， 而x p a t h2 0 需求文档是由w 3 c 的x s l 工作组和x q u e r y 工作组共同完成，这表 明了x p a t h2 0 和x q u e r y1 0 之间的重要联系。 2 3 1x p a t h x p a t h 是一种能在x m l 文档中查找定位和导航信息的路径语言，它能从 x m l 文件中抽取单个项目或一组项目。x p a t h 类似于平时我们在计算机系统中 使用的文件路径，就像我们熟知的c ：w i n d o w s 那样。通过x p a t h 路径表达 式，可以在x m l 文档中轻松地定位数据，确定节点。比如下面这个基本类型的 x p a t h 表达式( 对应上面的x m l 文档) ：b i b v e n d o r i d 。这个表达式从文档根 开始，选择所有b i b 子元素，然后选择b i b 的所有v e n d o r 子元素，最后选择v e n d o r 子元素的所有i d 属性。当然，x p a t h 表达式所提供的能力远远超过用这条简单语 句所做的工作。 使用x p a t h 可在x m l 层次结构中快速定位和提取信息，它的内建函数提供 了全面的功能，可以方便的处理数值及文本数据。 首先来看一个描述书籍信息的x m l 文档b i b x m l 。 机械工业出版社 2 0 0 2 j a v a 编程思想 b r u c ee c h e l 9 9 中国电力出版社 2 0 0 3 | y e a r c + + p r i m e r c h a r l e seg o l d f a r b 1 2 8 径) 清单2 - 3b i b x m l 下面列举一些典型的x p a t h 路径表达式( 用“，路径开始代表元素的绝对路 表2 - 1 典型的x p a t h 路径表达式 路径表达式选择的x m l 文档部分 选择x m l 文档的根结点 | 4 选择根结点的所有子节点，+ 匹配任意子节点 b j b 选择根结点的所有b i b 元素 b o o k选择根结点的所有后代节点中的b o o k 元素 试 选择含有i d 属性的子节点 b i b v e n d o r 2 】 选择b i b 的第2 个子元素 v e n d o r 【 i d = i d l j 】 选择符合“属性i d = i d l2 ”的所有b o o k 元素 b o o k b i b v e n d o r b o o k 选择符合“元素y e a r 2 0 0 2 ”的所有b o o k 元素 【y e a r 2 0 0 2 】 当然，x p a t h 还能实现很多其他的功能，具体请参看w 3 c 的x p a t h 规范【“1 。 2 3 2x q u e r y x o u e r y 工作组于1 9 9 9 年9 月正式成立，其任务是创建一种灵活的查询语言 以便从x m l 文档中抽取数据。目前w 3 c 所公布的最新x q u e r y 草案【15 】是2 0 0 5 年1 1 月3 日的版本，它还在不断的修订和完善之中。作为一种新型的查询语言， x q u e r y 汲取了其它多种查询语言的优点，适用于各种类型的x m l 数据源的查 询，不仅查询功能强大，而且简洁灵活且易于实现。而且，x o 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 q u e r y 表达式可以 完全嵌套，也支持子查询。目前，数据库业界的三大主流厂商o r a c l e 、i b m 、 m i c r o s o f t 都已经在各自的产品中提供了对x q u e r y 规范的支持。 x q u e r y 具有强大的查询和检索功能，它通过各种由关键字、符号、操作数构 成的表达式完成查询，其表达式的操作对象可以又是另一个表达式。作为一种函 数语言，它还允许各种表达式进行相互嵌套。同时它也是一种对数据类型有严格 要求的语言，表达式中的操作数，运算符和函数都必须是指定的类型。 除了支持x p a t h 的路径查询外，x q u e r y 中最强大的特性是f l w r 表达式 ( 发音为f l o w e t ) ，它是一种典型的能够完成具有某种实际意义的查询的表达 式。f l w r 表达式包含模式匹配、过滤选择和结果构造这三种操作。f l w r 语 句是x q u e r y 所具有的最接近于s q l 的语句。使用f l w r 语句，可以用比 x p a t h1 0 语句更自然的方法来创建特定的查询。 f l w r 表达式是由f o r ie t 一w h e r e - 一r e t u r n 四个关键字定义的子句 构成的，在最新的标准中则更新为f l w o r ，o 代表新加入的o r d e r b y 子句。 f l w o r 表达式分别代表f o r je t _ 一w 玎! r e _ 一o r d e rb y r e t u r n 的 首字母缩略词。由此组成的f l w o r 表达式可以完成很多在x s l t 中难以完成 的任务。它支持迭代并且可以把变量绑定到中间结果。对两个或多个文档进行连 接和重构数据时这种表达式非常有用。每个f l w o r 表达式都有一个或多个f o r 子旬、一个或多个l e t 子旬、一个可选的w h e r e 子句、一个o r d e rb y 子句以及 一个r e t u r n 子句。f o r 子句通过将节点绑定到变量，以便继续去循环遍历序列 中的每一个节点；l e t 子句为一个变量赋一个值或一个序列； e t u m 子句定义每 个元组要返回的内容；对于w h e r e 子句，如果其有效布尔值为真，那么该元组就 被保留，并且它的变量绑定用在r e t u r n 子句中，如果其有效布尔值为假，那么该 元组就被废弃。 下面是一个简单例子： f o r $ ii nd o c u m e n t ( ”b i b x m l ”) b i b v e n d o r b o o k w h e r e $ i p r i c e 8 0 r e t u r n $ i t i t l e ，$ i p r i c e 清单2 - 4f l w o r 表达式查询的例子 此例没有用到1 e t 语句，它只是可选的。要注意的是，变量都是以符号$ 开头 的，这些变量被绑定到不同的节点序列，然后通过语句进行传递。花括号 ) 代表 输出信息，以及要进行求值的信息。可以看出，f l w o r 表达式是一个有多种变 化的表达式类型，它可以生成大量不同的查询实例。“r e t u r n ”关键字后面的操作 项本身可以被另一个f l w o r 表达式替代，可以不断将f l w o r 表达式首尾相 接，使x q u e r y 具有非常丰富的表达能力。 其查询结果为： 9 9 除了路径表达式查询和f l w r 表达式之外，x q u e r y 还有5 中基本的表达式 模式：元素构造符、算子和函数表达式、限定表达式、列表构造符、数据类型表 达式等。通过它们的多种组合，可以产生具有丰富而强大的查询检索功能的查询 语句。 2 4 x m l 索引技术分类 x m l 数据的半结构化特性对数据库的索引方法提出了挑战。设计针对x m l 的高效索引机制，显然是解决当前x m l 数据管理中众多问题的一个有效方法。 目前有几种方法对x m l 文档建立索引。文献把结构化文档的索引方法分 为基于路径的、基于位置的和基于内容的三种。文献【9 按照索引方法使用文档 结构信息的层度，把x m l 索引的类型分为以下三种： 1 平面文件索引 2 半结构化索引 3 结构化索引 平面文件索引f f l a t - f i l ei n d e x i n g ) 。把x m l 文档看作平面文本文件。最简单 的索引方法是丢掉x m l 的标记，直接索引x m l 文档的内容。这种方法最明显 的好处是简单，但它丢掉了蕴涵在x m l 标记中也许对检索过程非常有价值的附 加信息。 半结构化索 ( s e m i s t r u c t u r e di n d e x i n g ) 。使用半结构化索引，或者需要预先 定义一个结构，然后把信息装入，或者需要文档具有确定的结构用于建立索引。 它包含以下几种索引理论背景引方法。 基于域的索弓 ( f i e l d b a s e dh d e x i n 曲：通过把x m l 文档表示成域的集合来建 立索引。例如，x m l 文档也许含有a u t h o r 域，t i t l e 域和p u b l i s h e r 域。通过组合 1 4 域的名字和内容建立索引，使检索限定在特定的域。基于段的索引( s e g m e n t b a s e d i n d e x i n g ) ：i l 匝过把文档分成一个个的区段建立索引。s a l m i n e n 和t o m p a ( 1 9 9 2 ) 介 绍的p a t 模型是这种方法的一个高效实现。不过，它不允许区段的重叠。c l a r k e ， c o r m a c k ，& b u r k o w s k i ( 1 9 9 5 ) 提出的重叠列表模型允许重叠，但它不支持任意嵌 套，而嵌套对x m l 文档是必须的。列表参考模型f m a c l e o d ，1 9 9 1 ) 用来处理层状 结构的文档。然而，查询结果只返回文档顶层的元素，并且所有的返回元素类型 必须是相同的。基于树的索i ( t r e e b a s e di n d e x i n g ) ：使用基于树的索引，x m l 文 档被看作树形或分层的结构。l e e ，y k ，y o o 和、o o n ( 1 9 9 6 ) 研究了各种用于s g m l 文档的基于树的索引模式这些模式把文档看作完全的k 叉树。通过这种方法， 每个节点被赋予一个唯一的整数值来建立索引。结构化索 ( s t r u c t u r e dl n d e x i n 【曲 结构化索引通常应用于具有固定结构的文档，这种结构通常表现为某种模式。利 用结构信息建立索引的好处是明显的：速度快，通常可以优化，而且检索结果可 以非常精确。i r d b 索引( i r d b i nd e x i n g ) ：这是目前关系数据库系统使用的索 引方式，它还包括通过把x m l 文档映射到关系表来存储的x m l 数据管理方式。 基于路径的索弓 ( p a t h b a s e di n d e x i n g ) ：使用基于路径的索引，要分别对内容和 结构建立两个索引。这样，x m l 中的每个元素和特定的x p a t h 相联系f w 3 c ) 1 2 1 。 每个x p a t h 被赋予一个唯一的标志，称为x i d 北京交通大学硕士学位论文基于 位置的索 ( p o s i t i o n b a s e d i nd e x i n g ) ：空i r a l 索引f 比如r t r e e 或k d t r e e ) 可用来 建立x m l 文档的索引。基于位置的索引把文档看作两维对象，不同的标记覆盖 不同的矩形区域。x m l 文档的基本结构是树形的，只有区内嵌套没有区间嵌套， x m l 元素问的逻辑关系能够方便的转化成位置关系用于检索匹配。多维索引 ( m u l t i d i m e n s i o n a li n d e x i n g ) ：为了满足空间数据库索引空间数据的需要而产生了 多维数据索引机制。b 树被一般化到高维空间而变成r 树( g u t t m a n ，1 9 8 4 ) 。使用 边界方框和关系机制定义对象的范围和大小。空间被分成一个个区，使用r 树 或r 。树对x m l 文档建立索引，提高检索效率。 随着x m l 应用越来越广泛，x m l 数据的存储和查询也成了一大研究课题。 本文提出的是一种高效的支持结点更新的索引机制，正是基于这样的背景。在本 章我们介绍了本文的理论背景，包括了对x m l 文档的两种分类，与之对应有两 种x m l 数据库，然后我们介绍了x m l 的主流查询语言，虽然x p a t h 和x q u e r y 还未成为国际标准，但它们是w 3 c 工作组的公共工作草案，在逐渐完善的同时 必定会得到越来越广泛的应用，本文提出的索引，也是基于x p a t h 的路径表达式。 最后我们对x m l 索引技术进行了归纳和分类。 3 i m d x 编码方案 近年来，x m l 作为一种网络数据表示和交换的格式越来越流行。w 3 c 工作 组已经为x m l 开发了如x p a t h 和x q u e r y 等查询语言。x p a t h 和x o u e r y 均是利 用路径表达式遍历x m l 数据。传统的以及最有用的提高查询性能的技术是建立 有效的索引。一个构建良好的索引在查询时不需要对整张表进行查询就可以得到 结果。 为了达到这个目的，可以赋给x m l 树中的每个结点一个唯一的标识符，这 样对于任何两个给定的结点都可以从标识符中得到他们的关系，如祖先或兄弟关 系。做到了这点，结构查询就可以利用索引来完成，而不需要访问实际的数据。 对x m l 文档进行有效编码成为当前热点研究问题。本章首先分析了几种编 码方法，然后提出i m d x 编码方法。 3 1 编码方案综述 为了建立有效的索引，已经提出了很多的技术。典型的有路径索引和编码方 法。路径索引方法如g r u s t ，a m a t o ，d e b o l e ，r a b i t t i 和z e z u l a 等人做的工作，这里 我们讨论的是编码方法。现有的主流方法主要分为两大类： 第一类，基于区位的编码方法，主要是基于节点在x m l 文档结构树中的遍 历值的编码方法，有基于前序、后序遍历值的编码方法及其扩展的方法，节点在 文档中的开始值和结束值( 即从文档的开始到确定节点开始以及到确定点的结束 的计算值) 及其扩展的方法； 第二类，基于前缀的编码方法，有十进制数字编码，二进制数字编码以及字 符编码。 3 1 1 区位编码方法 第一个提出用树遍历来来决定树的两个结点间子孙后代关系方法的是 d i e t z 1 6 】的编码方法。它的原理是：对于树两个给定的结点x 和y ，x 是y 的祖先 当且仅当x 在先序遍历中出现在y 之前，且在后序遍历中出现在y 之后。这个编 1 7 码好在可以根据树的前序和后序编码在常数时间内判断两个结点的关系，但是缺 乏灵活性，例如，当一个新的结点插入时，很多结点的先序和后序编码可能要重 新计算。 ( 3 ，1 )( 75 ) 挺习 图3 - 1d i e t z 的编码方法 l i 和m o o n 提出的x l s s l 8 】系统的编码方案对d i e t z 的编码方法进行了改进， 对树的每个结点赋予( p r e o r d e gs i z e ) 二元组编码。如图3 2 所示，其中p r e o r d e r 是 该结点在先序遍历树中的