（计算机应用技术专业论文）基于xml树结构的索引技术研究.pdf

摘要 摘要 由于x m l ( e x t e n s i b l em a k e u pl a n g u a g e ) 被广泛接受成为网上数据表 示和交换数据的新标准，因而越来越多的数据被保存在x m l 文档中，如 何有效地存储、查询和索引这些数据成为关键问题。本文在对国内外研究 现状进行综合分析的基础上，进一步对x m l 索引技术进行了深入的研究。 本文的主要研究内容有：对当前已经提出的各种索引技术进行了分析 研究，首先给出了一个x m l 文档树数据模型的形式化定义。讨论了x m l 编码方法的研究和应用概况，并分析了当前比较流行的几种编码方法和结 构连接的优缺点。同时在前缀数字编码的基础上提出了前缀字符编码方法 的思想。然后将编码方法、倒排表和路径索引的思想相结合，提出了一种 改进的x m l 路径索引方法，其中心思想是对路径索引树中的各个节点进 行编码，能够快速判断x m l 文档树中节点间的祖先后裔关系和双亲孩子 关系，有效的支持x p a t h 路径表达式查询和关键字搜索，不需要进行大量 的结构连接操作，从而提高x m l 路径查询的效率，同时给出了两个连接 算法。最后对基于序列的x m l 索引技术进行了分析和研究，指出了由于 同名兄弟节点的存在，导致了假警报，出现了查询不等价问题。提出了基 于约束序列的x m l 索引方法，给出了约束的一系列定义和引理通过引入 约束匹配，消除了歧义，并能保证结构匹配和子序列匹配的等价性，并证 明了定义、引理的正确性，分析了算法的性能。提出了利用模式信息和统 计技术来提高约束匹配性能的思想。 关键词x m l ；查询；索引；编码方法；路径表达式 燕山大学t 学硕士学位论文 a b s t r a c t x m lh a sb e c o m ep o p u l a ra saf l e x i b l em e d i u mo fd a t ae x c h a n g ea n d s t o r a g eo n t h ew w w t h e d e v e l o p m e n to f x m l b r i n g so nm o r er e q u i r e m e n t s f o rp e r f o r m a n c eo fx m l q u e r y i no r d e r t or e t r i e v et h er e s u l t st op a t hq u e r i e s e f f i c i e n t l y , p e o p l ep a ym u c h a t t e n t i o nt ox m l i n d e x i n g t h i sp a p e rf o c u s e so n i n d e x i n gx m lb y t r e es t r u c t u r e m a i na c h i e v e m e n t so f t h er e s e a r c hi n c l u d e ： f i r s t l y , t h i sp a p e rg i v e saf o r m a ld e f i n i t i o no fx m l t r e ed a t am o d e li n c o n t e x te n v i r o n m e n t s e c o n d l y , t h ei d e n t i f y i c a t i o no f s t r u c t u r a lr e l a t i o na m o n ge l e m e n t s p l a y i n g ac r u c i a li nx m ls t r u c t u r a l q u e r ya n ds t o r e ，r e s e a r c h o nx m ld o c u m e n t c o d i n g s c h e m ea n ds t r u c t u r ej o i ni si n t r o d u c e d ，ac l a s s i f i c a t i o no fx m l d o c u m e n t c o d i n g s c h e m ea n ds t r u c t u r e j o i n i s p r e s e n t e d s a n d a n a l y z e d , p r o p o s ep r e f i xb a s e d c h a r a c t e rc o d i n gs c h e m e t h i r d l y , t h i sp a p e rp r o p o s e sp r o p o s ea ni m p r o v e di n d e x s t r u c t u r a lt o r e t r i e v ex m ld a t a b a s e do nt h ei d e ao f t h en u m b e r i n gs c h e m e ，t h ei n v e r t e dl i s t ， s t r u c t u r a lj o i nm e t h o da n dp a t hi n d e x i n gm e t h o d t h i sp a p e rp r e s e n tt w o a l g o r i t h m sf o rp r o c e s s i n gs t r u c t r e lj o i n so f a n c e s t o r d e s c e n ta n d p a r e n f f c h i l d i t c 船e 簿c i 翻t l ys p e e d 廿pt h ee v a l u a t i o no f ) ( p a t hq u e r ya n dk e y w o r d ap a t h q u e r y w i t he l e m e n t sa n dap r e d i c a t er e s t r i c t i o nc a l lb ei m p l e m e n t e dw i t hl i t t l e s t r u c t u r a lj o i no p e r a t i o n s f o ra p a t he x p r e s s i o n i sn o t c o m p l y i n g w i t ha n y p a t h s i nx m l d o c u m e n t s ，g i v ea j u d g m e n t o f n oa n s w e ri nm u c hs h o r t e rt i m e f i n a l l y , t h ee x i s t i n gs e q u e n c e - b a s e d m e t h o di s a n a l y z e d ，t h e i rm a i n p r o b l e m i s q u e r yn o n e q u i v a l e n c e ，f o r t h i s p u r p o s ep r o p o s e as e r i e so f c o n s t r a i n tm e t h o d sa n da a l g o r i t h mt h a t e n s u r et h e q u e r ye q u i v a l e n c e i t i m p r o v ec o n s t r a i n ts e q u e n c em a t c h i n gp e r f o r m a n c eb yt h es c h e m aa n dn o d e p r o b a b i l i t y k e y w o r d sx m l ；q u e r y ；i n d e x i n g ；n u m b e r i n gs c h e m e ，a t he x p r e s s i o n i i 第1 章绪论 第1 章绪论 随着i n t e m e t 的迅速发展，互联网已经成为新经济时代的标志，它极大 地影响了人类的生活力 式、商业模式，并将在新世纪继续对人类社会的进 步起着巨大的推动作用。随着w e b 上数据的激增，面对庞大的信息海洋， 人们却遇到了w e b 上存在的大问题：虽然可以在线获得各种信息，但是找 到所需要的信息常常极为困难。其中虽然有硬件方面的原因，但是主要是 由目前w e b 语言一h t m l 的性质引起的。尽管h t m l 从发明以来，已成为 最成功的电子发布语言，但是它仅注重信息的表现形式，它的标记仅仅反 映了信息应该如何在页面上表现，并没有对信息本身进行描述，并且它的 标记集合是固定的，不能够根据需要进行扩展。随着w e b 应用的目益广泛， 它的局限性越来越明显，不适于作为i n t e m e t 上信息交换和标识的工具。 可扩展标记语言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 ) 正是为了解决这类 问题而提出的。1 9 9 8 年2 月w 3 c ( w o r l d w i d e w e b c o n s o r t i u m 全球互联网 联盟) 给出了其正式的x m l l o 【lj 式推荐x m l 成为下一代互联网标准。x m l 从提出到现在不过只有几年时间，但是它作为一种跨产品、跨界面、跨平 台的互联网的世界语，具有极大的应用前景，正引起政府、企业和各大软 件厂商的极大兴趣。关于x m l 实际上有一系列标准，x m l l 0 只是其基本 的语言规范。 其他标准包括x l i n k ( 用于描述将超链接加入x m l 文档的方法的标 准) 、x p o i n t e r ( 关于x m l 文档中特定部分的定位的标准1 【2 1 、 x s l 吲( e x t e n s i b l es t y l e s h e e tl a l l g u a g e ，有关x m l 文档的显示样式的标准) 、 d o m 4 1 ( d o c u m e n to b j e c tm o d u l e ，供应用程序处理x m l 文档的对象模型及 接口标准的定义) 、x m l n a m e s p a c e s i 副( 关于如何将帆文档中的元素标识、 属性与u r l 相关联的标准) 、x m ls c h e m a sl a n d2 ( 供应用开发者精确地定 义基于x m l 的类型) 旧以及x m lq u e r y 7 1x p a t h 8 x q u e r y 9 1 等等，其中很多 准还正在制定中。总之，对于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 p a t h ，由于查询语 句的复杂性，很难找到一种通用的索引结构能有效支持任意查询。因此， 在近十年的研究历程中，为了实现x m l 数据的快速查询，人们提出了大量 索引结构。 x m l 索引结构与传统的文本索引存在很大的不同，它的研究并不关一t l , x m l 文档中的文本内容，而是快速查找出满足某一特定路径的节点集，除 了与查询需求密切相关，x m l 索引结构还在很大程度上依赖于被索引的文 档集。比如这些文档的存储方式( 纯文本或者存放在关系数据库中等) ，是否 有文档类型的定义d t d 、文档模式( s c h e m a ) 及数据集的动态性等。现在 主要研究现实世界大量存在的x m l 文档，由于其结构的不可预测性导致结 构的复杂性。 在数据库系统里，索引在提高查询效率上发挥了非常明显的作用。关系 数据库中，索引是基于关系元组的某一个属性建立的，可以快速地通过索引 得到所要查询的元组。而在x m l 数据管理系统中，仅用值索引作用是非常 有限的。在x m l 数据的查询中，索引的作用是至关重要的，它可以明显的 提高查询效率，索引x m l 文档和关系数据库所有以及面向对象数据库索 引，在很多方面是相通的。都期望能实现信息的快速访问，都要在访问时 间和存储空间之间选择一个折中方案。利用存储空间来记录数据项的位置， 这在一定程度上减少了访问时间，可以执行较快的查询。在数据库中可以 在数据值上创建索引。同时也可以在结构化的连接上创建索引。因为x m l 元素数据结构具有更加灵活的内部结构，所以需要与关系或者面向对象数 据库采用不同的索引策略。与对象的索引结构不同，一个元素的结构信息 不断的变化，所以要建立一个静态的索引结构并不可行。元素数据的索引 2 第1 章绪论 结构要求创建索引数据结构。以访问基于元素和元素类型、属性、链接关 系的子元素关系。对于出现在文档中的字符数据，也需要建立索引。 1 1x m l 简介 x m l 是标准通用标记语言( s g m l ；s t a n d a r d g e n e r a l i z e dm a r k u p l a n g u a g e ) 的一种变体，它采用了优化浏览器显示文档视图的严格的规则集合。 从s g m l 中经过精心修剪而来的x m l 既保持了s g m l 的功能，同时又减 少了s g m l 的复杂性。与h t m l 不同，x m l 允许文档开发人员创建描述 数据的标记， 并使开发人员可以创建被称为文档类型定义( d t d ) 的规则集 合。 x m l 作为一种扩展标记语言，它主要有以下些特点： ( 1 ) 内容的自描述性x m l 是面向内容的标记语言，在x m l 中的语义 标识一方面限定了元素的层次结构，另一方面说明了元素的含义。在x m l 文档中由标记就可以知道内容的含义，这使得标记更有意义。 ( 2 ) 内容的独立性由于x m l 是自描述的，所以x m l 可以脱离具体应 用来描述保存在异构环境中的各种数据，其它应用系统能直接对这些自描 述的x m l 文件中的数据进行操作。由于x m l 的语义与数据独立性，它也 成为跨平台数据交换和操作的标准模式。 ( 3 ) 能描述不同复杂程度的数据x m l 提供了数据的结构化表示，并且 易于操作。它可以以一种统一的数据模式来描述来自不同数据源的数据， 屏蔽数据源中应用环境和数据结构的异构性，以x m l 查询语言对数据源进 行统一访问。 ( 4 ) 可扩展性通过x m l 文件中命名空间的声明，x m l 可以通过互联 网被其他组织或个人使用，这样可以使用一种统一的数据查询和操作模式， 而不必关心数据所在的具体系统和应用环境。另一方面，x m l 可以在不破 坏现有结构和系统的情况下增加新的数据字段，利用x m l 对所有数据建 模，而不需要更改现有的对象。 ( 5 ) 显示的多样性x m l 一个鲜明的特点是把数据的显示格式与数据 燕山大学工学硕士学位论文 的表示分离。在x m l 中，可以用格式文件x s l 来定义x m l 数据的显示格 式，分离数据的表示和内容。这种分离可以实现不同数据源数据的无缝连 接。各种数据可以在中间件上转换成x m l 格式，使得数据很容易地进行在 线交易和传输。 1 2 国内外研究现状 随着i n t e m e t 的迅速发展，x m l 已成为i n t e m e t 网上数据表示与交换的 事实标准，大量应用采纳了x m l ，例如w e bs e r v i c e 中的数据表示和交换、 m p e g 7 中定义的多媒体特征描述子等。x m l 数据的急剧增多给x m l 文档 的维护工作带来了很大的挑战，为了更好地对x m l 文档进行维护，使得其 他应用程序更容易对x m l 文档进行操作，人们从存储到索引、再到查询做 了积极深入地研究。这些研究促进了x m l 的发展，解决了现实中的诸多问 题，许多优秀的研究成果已经有了一定的规模的应用如l o r d 1 0 l 。但是由于 x m l 数据的多样性以及用户日益增长的查询需求，人们很难找到一种能同 时适应不同的数据来源( x m l 纯文本，关系型数据库以及其他各种应用数据 等) 并能够有效的处理各种查询请求的通用索引结构。因此，针对不同的 x m l 应用，人们提出了不同的索引结构，这些索引结构能够满足特定环境 下的需求。 人们在近十年中提出了很多索引结构，它们的存储媒质、构造索引的 方法以及所能够支持的查询种类各不相同，根据各自特点，给出几种分类： 当前的索引方法可主要分为三大类：节点索引【1 1 d5 1 ，是对x m l 文档结 构进行编码，即按照某种方法对文档中的每一节点进行标注。如果一种编 码方法被嵌入到x m l 文档标记树中那么就不需要遍历整个x m l 文档就可 以快速判断元素间结构关系( 例如祖孙，父子关系) 。在这种处理策略下，基 本结构关系( 包括父子关系和祖先后代关系) 的计算成为查询处理的关键操 作。这种操作被称为结构连接( 或包含连接) i 6 - 2 0 l 。路径索引 2 1 - 2 9 ，根据x m l 文档的带根标记有向图来创建x m l 文档的结构概括，这种方法是保留所有 路径，然而留有较少的结点和边。序列索引f 3 0 。3 2 1 ，是要把x m l 数据和查询 4 第1 章绪论 转换为序列，通过子序列匹配来应答x m l 查询。 同时根据索引的存放媒质不同，可分为文件系统、关系数据库和两者 的混合方式。x m l 数据及其索引结构往往作为文本文件存放在文件系统中， 如文献1 1 ，2 6 ；为了充分利用关系数据库的成熟技术，将x m l 文档存放在 关系数据库中以解决x m l 文档的查询和维护工作；利用关系数据库和文件 系统联合做索引，如文献 2 9 1 。 根据索引的组织形式不同，可以将x m l 索引结构分为结构型和离散型 结构型。结构型只索引中直接保存原始文档中的结构( 路径) ，相当于x m l 文档的s c h e m a ，如文献 2 2 ，2 3 ，2 4 等；而离散型则是将原始文档的节点聚类 存储，原始文档中的结构索引中的附加信息计算获得，如x i s s ，m a s s 。 根据索引支持的查询语句的种类，可以将x m l 索引结构分为可以支持 简单类查询和可支持正则类查询。前者指可有效支持简单查询语句的索引 结构，如d a t a g u i d e 、1 - i n d e x 、a ( k ) 、d ( k ) 等；后者则是那些能够支持正则 查询语句的索引结构，如x i s s 、m a s s 等。 可支持简单查询的索引结构能很好支持简单查询语句，但是对于正则 查询的效率则显得很低。 下面根据索引存放的介质的不同分别进行介绍： 索引存放在文件系统中这一类索引也可称为路径索引。这些索引技术 主要是根据x m l 文档的带根标记有向图来创建x m l 文档的结构概括，这 种方法是保留所有路径，然而留有较少的结点和边，结构概括直接从数据 中提取结构信息。然而不像模式，他们不是静态的，可能随数据的更新而 改变，他们是近似的、大概的，他们需要处理那些长的，但很少用的查询 路径，从而导致增加了复杂度，这种索引技术典型由带有从概括结点到数 据结点的已存储的映射图构成的结构概括组成，它可以通过修减搜索空间 来直接估计路径表达式，但是由于结构概括不包含所有的数据结点，许多 路径仍然需要被检查，它通过一些诸如节点等价、路径等价的技术来抽取 x m l 文档中隐含的结构( 类似于s c h e m a ) ，对原始文档进行无损压缩，来得 到比原始文档小的很多的结构索引，构造这一类索引结构的过程实际上一 系列的节点合并策略。 燕山大学工学硕士学位论文 d a t a g u i d e 是最早出现的一种结构概括，并且这以算法在l o r ed b m s 中得到实现。d a t a g u i d e 首先提出了一种路径合并的策略：d a t a g u i d e 实际 上是对文档结构的概括，它反映了x m l 数据的实际结构。d a t a g u i d e 中存 在的路径表达式在实际文档中也是肯定存在的。构造d a t a g u i d e 的过程实际 上就是从非确定性自动机变为确定性自动机，即把源数据作为非确定性自 动机，然后获得等价的确定性自动机。源数据中具有相同标注的路径在 d a t a g u i d e 中有且只有一条路径与之对应，d a t a g u i d e 系统实现了任意结构 的半结构数据的索引，它是关于半结构数据路径信息的一个精确，简洁的 索引结构，d a t a g u i d e 是一种有效的路径索引结构，在很多情况下可以提高 数据访问的效率，由于d a t a g u i d e 是确定性自动机，它的大小在通常情况比 源数据小，因而通过路径索引查找的复杂度要低于直接查找源数据，但建 立d a t a g u i d e 的代价可能是非常高的，同时当源数据环路较多时，d a t a g u i d e 的空间可能会很大，最坏的情况下会达到源数据的指数级。 1 - i n d e x 与d a t a g u i d e 的出发点不一样，1 - 1 n d e x 不是从路径而是从节点 着手来考虑构造索引的，它采用了一种合并相似节点的技术来对原始文档 中相似节点进行合并。下面给出节点相似的定义。d b 表示原始文档数据， 那么如果作用在d b 节点上的二元关系“”满足下面四个条件，则称之为一 种双向相似关系( b i s i m u l a t i o n ) ： ( 1 ) 如果v - v ，而且v 是根节点，那么v 也是根节点； ( 2 ) 相反，如果v v ，而且v 是根节点，那么v 也是根节点； ( 3 ) 如果v v ，而且对于任何u 斗v 边，如果存在另一条边u 斗v ，则 u u ： r 4 ) 相反，如果v v ，而且对于任何边u 斗v ，而且对于任何边u 一v 如果存在另一条边u _ v ，则u - u 。 如果仅仅满足( 1 ) 、( 3 ) 条，则将两元关系“”称为单向相似关系 ( s i m u l a t i o n ) 。设e 是任意节点，定义“e ) = l = e o e 卜e n ，其中e o 是根节点) 。 能够证明：u v 寸l ( 1 j ) = l ( v ) 因此也就是容易证明根据这样一种相似的规则来对原始文档中的节点 进行合并所得到的索引结构，其路径涵盖了原始文档中的所有路径，也就 6 第1 章绪论 是说这样的索引结构是安全的，不会遗漏返回的结果。 双向相似性( b i s i m u l a t i o n ) 是7 0 年代图论中提出的概念，表示原始文档， 这种索引结构的减小是因为d a t a g u i d e 中会存在重复节点，而1 - i n d e x 中不 会存在重复节点。 上面提到1 i n d e x 仅仅适应简单路径表达式查询，不能有效的支持正则 表达式查询，文献 2 2 是为了支持正则表达式查询语句而提出来的，但是这 种索引结构有非常大的局限性，它仅仅能支持由节点、“一”以及“一组成的 非常简单的正则表达式查询语句。也提出了另一种索引结构t - i n d e x ，仅适 用有合适摸板的数据的索引，源数据中每一个对象在t - i n d e x 仅有一个对 应结点，因而t - i n d e x 的空间复杂度较低不过，源数据中一条标注路径可能 对应于t - i n d e x 中的多条路径，从而使查询效率受到影响。 1 - i n d e x 完全保存了原始文档中的所有信息，这样的索引结构可以看作 是对原始文档的一种无损压缩。有些时候，这种无损压缩的结果可能仍然 会很大，达不到期望的大小，因为这种无损压缩完全决定于原始文档相似 节点的数量。 1 - i n d e x 是精确的结构概括，在索引图中可以直接估计路径表达式，不 需要参考原始数据就可以检索匹配标记结点，但是，1 - i n d e x 结构概括通常 太大，加速估计效率不高。a ( k ) i n d e x 放宽了等价条件，利用局部相似性的 概念，仅考虑输入边路径长度不大于k 的路径，通过利用短路径的相似性， 在很大程度上减少索引的大小，1 - i n d e x 和a ( k ) i n d e x 都不能根据查询加载 来调整他们的索引图，这些结构索引并没有提出增量更新算法。d m ) 利用 局部相似性的概念，能根据查询加载信息和源数据来相应调整他们的索引 图。 文献 2 5 1 是一种适应性的路径索引，把它作为动态索引方法来讨论不 像传统技术，它运用数据挖掘技术来概括频繁出现在查询加载中的路径， 当查询加载改变时，他做相应的更新。他不保持所有从根开始的路径，只 维持路径长度不超过2 的路径，当大于2 时，得依赖连接( j o i n ) 操作。没有 提出根据源数据变化而更新的算法 文献 2 8 1 ( 称f + b l n d e x ) 类似于文献 2 9 i n d e x f a b r i c 优化分支查询集合是 7 燕山大学工学硕士学位论文 基于文献 8 】( 称f & b i n d e x ) f & b i n d e x 太大而不能有效地支持查询估计， f + b l n d e x 在很大程度上加速了预定义查询类型，但对普通的查询得依赖 f & b i n d e x 。 i n d e x f a b r i c 索引的方法是在x m l 文档中以字符串的形式把路径进行 编码，并把这些字符串插入到索引中，从而对查询进行优化。然后，将索 引块和x m l 数据存储到一个常用的关系数据库中。这种方法有以下好处： 这里不需要任何文档的模式信息，因为路径能够从文档本身抽取出来；无 论文档的结构怎样的多样和不规则，这种方法都有很强的适应能力；索引 技术使查询快速高效。 当前的索引技术大多是针对正则路径表达式r p e ( r e g u l a rp a t h e x p r e s s i o n ) ，用户可以根据r p e 在x m l 数据中搜索任意长的路径，针对 r p e 的查询处理和优化已提出很多索引技术，但是这些索引技术大多集中 在对x p a t h 的和序列的定位步的有效支持。而对其他序列的定位步没有提 供有效的支持，文献 1 2 a c c e lx p a t hl o c a t i n ss t e p 是针对x p a t h 查询而建 立的索引技术，它可以处理所有的x p a t h 轴，它是关系存储结构，索引可 以仅用关系技术来实施和查询，如果索引通过r t r e e 来实现性能更好。 但是路径步很长( 2 ) 时需要多次递归计算，影响效率，而且对于原子值需要另 加计算。x i s s 以单个元素或属性作为最基本的索引单位，一个复杂的路径 表达式可被分解为基本路径表达式的集合，即一个个的原子表达式( 一个单 个元素或属性) 通过访问索引结构直接可以得到。所有其他形式的表达式都 要涉及到联结( j o i n ) 操作。x i s s 运用单个索引结构，而m a s s 是多轴存储 结构，对，a t h 表达式提供可升级性索引同时保证更新性能。随着x q u e r y 1 0 和x p a t h 2 0 规范进入w 3 c 的建议书。可以预见针对x p a t h 的索引技术 将成为一大热点，人们的目光将转向x q u e r y 和x p a t h 。 以上介绍的方法索引的结果是返回节点的集合，而基于序列的x m l 索 引方法支持一个比较通用的查询界面：树模式j p ( 文档i d 集) ，也就是说， 给定一个树模型，索引返回一个包含这种模式的x m l 文档集、记录集，把 x m l 数据和查询转换为序列，通过子序列匹配来应答x m l 查询，这样可 以整体回答结构查询。 第1 苹绪论 上面讨论了许多索引技术。但完善的索引技术应当是什么样的昵? 本 文认为一个完善的高效的x m l 索引技术应当具有以下功能： ( 1 ) 对任意结构查询包括任意x p a t h 表达式，分枝，通配符等的高效支 持。 ( 2 ) 索引结构应支持动态的数据插入、删除和更新，同时可根据源数据 和查询加载的变化能自动更新。 ( 3 ) 索引应能提供了- - , q 统一索引机制既可实现对数据内容又可实现对 x m l 文档结构的索引。 ( 4 ) 索引的实现应被d b m s 很好的支持，利用成熟的d b m s 管理技术。 ( 5 ) 当前的索引技术大多集中在路径索引，路径索引提供了对路径表达 式的高效查询，但值索引对x m l 数据查询是不可缺的，值索引对于谓词条 件上的查询是很有用，这两种索引对于x m l 的数据查询不可缺的。应把传 统的值索引集成到路径索引，以实现高效的索引。 ( 6 ) 当x m l 文档中存在一种模式，一个d t d 或一个x m ls c h e m a 。如 何利用这个模式中包含的信息来建立索引机制，并不是所有的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 索引技术中涉及到的相关技术进行分析研究的基础上， 针对一些问题提出了自己的观点，本文研究的主要内容有； ( 1 ) 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 查询处理的核心操作。讨论了几种结构化连 接操作算法的性能。j ( 3 ) 将编码方法与路径索引相结合，使得对路径表达式得计算不仅可以 使用编码连接法，而且还可以使用路径法( 选择代价比较小的方法) ，以加快 路径表达式得计算。给出了索引方法的体系结构，讨论原有的连接算法， 并对其进行改进，提出了新的连接算法，实验验证分析了在x m l 文档上索 引技术的有效性。 ( 4 ) 提出了基于约束序列的x m l 索引技术，给出了约束序列的概念、 引理、子序列匹配算法并分析了算法性能。 1 4 文章结构 以下是本文的结构安排： 第l 章为绪论，对x m l 进行了简单介绍，论述了本论文的研究背景、 研究现状、研究内容和研究成果。 第2 章论述了x m l 文档的模型、x m l 文档的形式化定义，查询操作 以及x m l 查询语言具有的特征。探讨了x m l 查询语言应当具有的一些基 本特性，如简单路径表达式、一般路径表达式等，并简要介绍了现今已提 出的主要的x m l 存储方法，以及索引策略。 第3 章对编码方法和连接算法进行了研究，详细介绍了各种编码方法 和结构连接算法，对现有的编码方法进行了分类，重点探讨了对节点位置 进行标注的编码方法以及有效的结构连接算法。 第4 章将编码方法、值索引和路径索引的思想相结合，提出了一种改 进的x m l 数据的索引方法，他能够快速判断x m l 文档树中任意节点对之 间得祖先后裔关系和双亲，孩子关系，有效的支持x p a t h 路径表达式查询和 关键字搜索不需要进行大量得结构连接操作。 第1 章绪论 第5 章讨论了基于序列的x m l 索引技术，对其进行了分析和总结，并 指出了其优缺点，提出了基于约束序列的x m l 索引技术，给出了约束序列 的概念、引理、子序列匹配算法并分析了算法性能。从理论证明了他们的 正确性。 最后总结全文，对未来的研究方向进行了展望。 本章对当前的x m l i 索引技术的研究工作做了详细的介绍，阐述了目前 在该方面的研究现状、已经取得的成果，同时指出了本文要研究的内容。 可以看出，在该领域已经取得了丰硕的成果。然而仍然需要进一步的完善 和改进，仍需要有大量的工作要做，今后x m l 索引的研究需要加强如下几 个方面包括： ( 1 ) 研究适用范围更加广泛的索引结构，能更加全面的支持x p a t h 查询 语句。 ( 2 ) 目前的索引结构大多是静态的，今后应该加强动态索引结构的研究。 ( 3 ) 利用索引提高查询效率实际上是空间换时间的做法。如何针对不同 的查询需求建立。使用和维护合适的索引是研究者面临的一个问题。 ( 4 ) 不同的索引目标也不相同，如何在一个查询中综合地使用不同的索 引。随着x m l 数据在电子商务中广泛应用，x m l 数据更新需求迫切，更 多的研究应该关注如何动态地维护索引以适应不断的数据更新的问题。 燕山大学工学硕士学位论文 第2 章x m l 树与查询语言 2 1 x m l 文档树模型的形式化定义 x m l 可以看作是半结构化数据的一个通用的逻辑表示。它的模型和查 询语言的研究可以借鉴半结构化数据研究的已有成果，同时又要结合x m l 自身的特点。x m l 数据表现形式灵活，可以描述非常复杂的结构，但其本质 仍然是树状的模型。树中的每个节点对应于一个元素，树中的边描述了元素 之间的父子关系。下面给出一个x m l 文档树模型的形式化定义。图2 1 显 示了一个简单的x m l 文档树。 y e a r 2 0 0 2 ” “t i t l e _ l a u t h o r _ l “a u t h o r2 t i t l e2 a u t h o r _ l ” 图2 - 1 一棵x m l 文档树 f i g 2 - 1a x m ld o c u m e n tt r e e 一个x m l 文档可以由x m l 文档树模型形象地表示。x m l 文档树是 七元组( l n e ，n a ，e ，占o r d e r , v e ，v a ) ，其中：n e 和n a 分别为文档中出现的元素 和属性节点( 对类型为i d r e f 的属性作特殊处理，x m l 文档图中不出现该 属性节点，而直接包含一条从父元素节到属性所指向元素节点的有向边) 的 集合。除了根元素，每个元素都有一个对应的父元素。 映射v e ：n e - p c d a t a u n u l l 。为元素节点确定相应的数据值；若该 元素没有字符串值，则映射值为n u l l 。 映射v a ：n ajc d t a ua t y p e ，为属性节点确定相应的属性值。其中 第2 章x m l 树与查询语言 a t y p e 表示一些特殊类型的属性值域，如i d 、i d r e f 、i d r e f s 等。 e 是一个n e u n a 上的二元关系，满足：( 1 ) v n l n e ，n 2 n e u n a , 若n l 是n 2 的父元素，则有( n l ，n 2 ) e ：( 2 ) n l n a ，1 1 2e n e ，若n l 的类型为 i d r e f i d r e f s ，其父元素节点为n p ，n 2 有一类型为i d 的属性1 1 3 ，且 v a ( n 0 = v a ( n 3 ) ，则有( n p ，n 2 ) e 。映射8o r d e r ：e 一 1 ，2 ，3 ，) ，规定同一父元 素下具有相同标签的觅弟子元素的相对顺序。 由该定义可以看出，如果不考虑由i d r e f 属性构成的元素引用关系， 一个良构的x m c 文档对应了一棵以r 为根的树。每一个元素可以包含字符 串值或( 和) 嵌套的子元素或( 和) 属性值的集合。 类型为i d r e f 的属性构成了对文档中另一元素的引用，同时同一父元 素下具有相同标签的子元素具有相对顺序的语义。 文档数据模型中只保存了有关元素和属性的数据，而忽略了有关注释、 操作指令等信息。 2 2x m l 查询语言 x m l 是具有非凡表达能力的数据格式。通过对信息加各种标记( t a g ) ， 不同种类的数据都可以用x m l 格式来表示，不论数据是结构化的关系表、 还是半结构化的文档，或者是来自于某个数据源的数据流。可以肯定， i n t e m e t 上越来越多的信息将以x m l 的形式存储、交换和显示。目前已经 提出很多种x m l 查询语言，比如x m l q l 以及w 3 c 标准x q u e r y 等，不 同的x m l 查询语言之间的一个重要区别是数据模型的不同。查询x m l 文 档的关键是如何从输入中选择出所需的数据。大多数x m l 查询语言都使用 了正规路径表达式( r p e ) 来描述从文档的“根结点”到数据值所走过的路径。 由于l 可能含有递归嵌套的元素或不规则的结构，因而可使用正规表达 式运算符，如通配符、k l e e n e 运算符和选择运算符等。 对于树结构的查询语言来说，存在一条从根结点到给定结点的唯一路 径。但是，如果数据模型是图结构的，则可能存在着多条从根结点到给定 结点的路径。在这种情况下，语言的语义通常限定了路径表达式中的结点 燕山大学工学硕士学位论文 仅能出现一次。即使是在图结构数据模型中，也存在着对文档中的子元素 进行遍历、或者是将i d r e f 作为属性而不是直接进行查询的情况。x m l q l 对这些并不做区分：l o r e l 查询语言则为用户提供了一种图结构与树结 构模式的转换机制以支持上述的查询情况。 不同的查询语言所使用的路径表达式有很大的不同，但其功能确实类 似，即供沿路径导航式的查询方式。在本节，我们简要介绍两种有代表性 的查询语言，即x p a t h 和x q u e r y 。 2 2 1 路径表达式 目前，涌现出不少针对x m l 之类成为半结构化数据的查询语言，其共 同特征是路径表达式。他们所定义的路径表达式能够让用户制定相关结构 中符合一定条件的任意路经，这也是其与关系数据库的一个重要差异。 路经表达式是由节点与节点间的关系约束一次间隔构成的有限长度的 列表。表达式的表达能力是衡量和划分表达式的重要指标。对表达式表达 能力的鉴定可以从以下若干方面进行： ( 1 ) 节点名节点名是否是由确定的字符组成；是否允许通配符“”与 匹配0 个至多个或任意单个字符；是否允许用户使用正则操作“+ ”、“一、 “? ”和“l ”来表达更为复杂的概念。 ( 2 ) 节点构造节点是否允许嵌套递归，即允许节点由其他的一条子路 经或节点构造组成；节点是否允许正则操作；节点是否允许为其附加相应 的谓词约束。 ( 3 ) 节点间的关系约束节点间的关系约束是固定的直接连接，还是允 许用户指定其在数据中的具体表现形式，如后继和祖先关系等等。 根据各项指标的复合程度，我们可将路经表达式按照表达能力化分为 以下两类：简单路径表达式( s i m p l ep a t he x p r e s s i o n ) 和一般路径表达式 ( g e n e r a lp a t he x p r e s s i o n ) 。下面分别加以讨论： ( 1 ) 简单路径表达式当查询x m l 数据时，尤其当不能事先知道精确 结构时，使用基于路径表达式的“导航式”查询是很方便的。主要思想就是 第2 章x m l 树与查询语言 规定在x m l 文档结构中的基于节点名的序列的路径。简单路径表达式( s p e ) 是一个节点名的序列，n 1 n 2 n m ，其中n l ，n 2 ，n m 是节点名，u i n j 代表从节 点n i 到n j 的路径。n i + - 是n i 的子节点。节点包括元素节点、属性节点、文 本节点，元素节点的节点名就是该元素的标记，属性节点的节点名是该属 性的属性名，文本节点的节点名是t e x t 。例如简单路径表达式 p u b l i c a t i o n b o o k a u t h o r 。在x m l 文档的查询中引入简单路径表达式，可以 使用户写查询方便。 ( 2 ) 一般路径表达式对于x m l 数据而言，由于它的模式不是事先知 道的，而且模式不是固定的。x m l 数据的灵活性和模式与数据并存，引入 一般路径表达式是必要的。一般路径表达式( 简称g p e ) 扩展了简单路径表达 式，对于查询数据和模式提供了强有力的机制。例如p u b l i c a t i o n # a u t h o r 中，“社”通配符指以元素实例集合p u b l i c a t i o n 为初始集合，经过任意路径f 零 条或多条) 到达节点名为a u t h o r 的元素，找出所有该元素的子元素。 从这个例子可以看出，一般路径表达式与简单路径表达式相比，提供 了更多的功能，主要分为以下四项： ( 1 ) 正则表达式这是广义路径表达式对简单路径表达式最重要的扩 充。正则表达式( 简称r p e ) ，如果e