（计算机软件与理论专业论文）基于xml半结构数据索引的研究.pdf

哈尔滨三 l 程大学硕十学位论文 摘 要 近年来，随着 w w w ( w o r l d w i d e w e b )的迅猛发展，半结构数据的管理 已成为数据库领域中的一个十分重要的研究方向。 特别是 x m l ( e x t e n s i b l e m a r k u p l a n g u a g e ) 作为一种新的数据交换事实上的 标准， 使得w w w 上的数据 交换和集成成为可能。将w e b 上的半结构数据迁移到x m l 上是对 w w w 上巨大 数据进行有效管理的一项十分有意义的工作。因而， 基于x m i 的半结构数据 管理的研究目前已成为国际数据库界的一个重要研究方向之一。 半结构数据索引的研究是半结构数据管理的研究的一部分。半结构数据 索引既有与传统数据库相同的部分，也有不同于传统数据库的部分。传统数 据库的一部分成熟技术可以比较方便地移植到半结构数据上来。但是，由于 半结构数据的特点，半结构数据索也引带来一些新的研究问题。 由于x m l的数据表达能力强大，x m l 完全可以在互联网和数据库之间扮 演 卜 分重要的角色。本文对半结构数据索引的研究都基于x m l 的图模型。目 前对半结构数据索引的研究已较为深入，已经有一些较成熟的基于x m l 的半 结构数据索引。针对半结构数据索引的特点，我们主要从数据表示、索引接 口、路径模版的形式、索引的导航方式、节点的定义、索引的更新和索引的 存储七 个方面对这些半结构数据索引进行分析和分类。我们对已有的半结构 数据索引都进行了较为详尽的介绍和其特点的分析。特别地，对b u s 索引给 出详尽的介绍并分析该索引存在的不易文档动态更新的缺点。于是，我们建 立了 一 个支持文档动态更新的半结构数据索引原型系统。我们建立的原型系 统，采用与关系数据库结合的模式，具有适应文档频繁更新的优点，使文档 节点的插入和删除实现较为容易。最后，我们通过实验数据的分析和比较， 验证了在文档内容和结构频繁更新情况下该原型系统半结构数据索引的执行 效率。 关键词:半结构数据;x m l ;索引技术;数据模型 哈尔滨上程大学硕 学位论文 a b s t r a c t f n r e c e n t y e a r s t h e r e h a s b e e n a n i n c r e a s e d i n t e r e s t i n 门 0 : 1 + 日 之 1 卞 r e l a t i o n a l d o e s n o t c o n f o r m t o t r a d i t i o n a l d a t a m o d e l s , m a n a gi n g l i k e t h e o r o b j e c t o r i e n t e d d a t a m o d e 土 s . t h e r e f o r e , s e m i s t r u c t u r e d d a t a m a n a g e m e n t a n d r e s e a r c h l a n g u a g e t o p i c 1 n i n t e g r a t i o n h a v e r e c e n t l y d a t a b a s e s . s p e c i f i c a l l y , b e c o m e a n i m p o r t a n t t h e e x t e n d e d m a r k u p ( x m l ) h a s e m e r g e d a s a s i m p l e , p r a c t i c a l s t a n d a r d t o m o d e l a n d e x c h a n g e s e m i s t r u c t u r e d d a t a o v e r t h e w o r l d w i d e w e b , w i t h o u t t h e r i g i d c o n s t r a i n t s o f t r a d i t i o n a l d a t a b a s e s y s t e m s . s o i t i s a n i m p o r t a n t a n d s i g n i f i c a n t w a y t o m a n a g i n g a n d i n t e g r a t i n g s e m i s t r u c t u r e d d a t a o v e r t h e w w w w h i l e m i g r a t e s e m i s t r u c t u r e d d a t a o n t h e w e b t o x m l . n o w t h e d a t a m a n a g e m e n t a n d i n t e g r a t i o n f o r x m l - b a s e d s e m i s t r u c t u r e d d a t a h a s b e c o m e a h o t r e s e a r c h t o p i c i n t h e i n t e r n a t i o n a l d a t a b a s e c o m m u n i t y . r e s e a r c h o f i n d e x f o r s e m i s t r u c t u r e d d a t a i s o n e a s p e c t o f t h e d a t a m a n a g e m e n t f o r s e m i s t r u c t u r e d d a t a .工 n d e x f o r s e m i s t r u c t u r e d d a t a i s n o t o n l y t h e s a m e a s i n d e x t e c h n i q u e s o f t r i d i t i o n a l d a t a b a s e , b u t a l s o d i f f e r e n t t o t h e m . s o m e o f m a t u r e t e c h n i q u e s o f t r i d i t i o n a l d a t a b a s e c a n b e d i v e r t e d i n t o s e m i s t r u c t u r e d d a t a e a s i l y . b u t s e m i s t r u c t u r e d d a t a h a s s o m e i n h e r e n t c h a r a c t e r i s t i c s w h i c h a r e d i f f e r e n t f r o m t r i d i t ( 日 a l d a t a b a s e , s o r e s e a r c h o f i n d e x f o r s e m i s t r u c t u r e d d a t a b r i n g s s o m e n e w q u e s t i o n s . a s x m l i s s t r o n g i n d a t a r e p r e s e n t a t i o n a n d e x c h a n g e o n t h e w o r l d - w d i e - w e b , x m l i s m u c h m o r e t h a n t h e b r i d g e b e t w e e n w o r l d - w d i e 一 w e b a n d d a t a b a s e . i n t h i s a r t i c l e , t h e r e s e a r c h o f i n d e x f o r s e m i s t r u c t u r e d d a t a b a s e s o n x m l g r a p h i c m o d e l . n o w , t h e r e a r e m a n y r e s e a r c h i n i n d e x o f s e m i s t r u c t u r e d d a t a a n d m a n y m a t u r e i n d e x m o d e l s . 哈尔滨工 程大学硕十学位沦 文 b a s e d o n t h e c h a r a c t e r s o f s e m i s t r u c t u r e d d a t a , w e r e s e a r c h a n d c l a s s i f y i n d e x f r o m s e v e n a s p e c t s , d a t a r e p r e s e n t a t i o n , i n d e x i n t e r f a c e , p a t h t e m p l a t e s , n a v i g a t i o n , n o d e i n d e n t i f i c a t i o n , i n d e x u p d a t e a n d s t o r a g e . t h e a u t h o r d i s c u s s e d m o s t i n d e x o 士 s e m i s t r u c t u r e d d a t a w h i c h h a d b e e n b r i n g e d f o r w a r d . e s p e c i a l l y , d e t a i l o f b u s i n d e x a n d s h o r t c o m i n g o f d y n a m i c c h a n g e d i f f i c u l t l y w e r e b r i n g e d . s o t h e a u t h o r b u i l t a n e w p r o t o m o d e l o f s e m i s t r u c t u r e d d a t a i n d e x w h i c h c o u l d s u p p o r t d o c u m e n t c h a n g i n g f r e q u e n t l y . t h e n e w i n d e x m o d e l c o n j o i n t w 土 t h r e l a t i o n d a t a b a s e m o d e l , a n d m a k e i t e a s y t o i n s e r t n o d e s a n d d e l e t e n o d e s . t h e l a s t , t h e p r o t o m o d e l a r e i m p l e m e n t e d t o v a l i d a t e t h e e f f i c i e n c y o f i n d e x w h e n c o n t e n t a n d s t r u c t u r e o f d o c u m e n t s c h a n g e f r e q u e n t l y , t h r o u g h t h e r e s u l t o f e x p e r i m e n t a t i o n . k e y w o r d : s e m i s t r u c t u r e d d a t a ; x m l ; i n d e x ; d a t a m o d e 丁 哈尔滨工程大学 学位论文原创性声明 本人郑重声明: 本论文的所有工作， 是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外， 本论文不包含任何其他个人或集体己 经公开发表的作品成果。 对本文的研究做出重要贡献的个 人和集体， 均已在文中以明确方式标明。 本人完全意识到 本声明的法律结果由本人承担。 作者 ( 签字) : 利 日 期: 买,* 年 卫月勿 日 哈尔滨工程大学硕士学位论文 第1 章 绪论 1 . 1研究课题目的及意义 近年来， i n t e r n e t 正以令人难以置信的速度飞速发展， 越来越多的机构、 团体和个人在 工 。 t e r n e t上发布信息、查找信自 、 。工 n t e r n e t的迅速发展，使 其成为全球信息传递与共享的日 益重要和最具潜力的资源。虽然 工 n t e r n e t 上有海量的数据，但由于 w e b 是无结构的、动态的，并且w e b 页面的复杂程 度远远超过了文本文档，人们想找到自己想要的数据犹如大海捞针一般。如 何管理 w w w上的大量信息，以 满足用户不断增长的高质量的信息需求? w w w 作为一种新的环境资源，为新技术的产生开辟了新的领域，同时也为传统技 术 ( 如数据库技术、人工智能技术)的研究提出了新的方向。 要想对这种半结构数据进行有效的管理是十分困难的，因为传统的数据 库管理系统， 如关系数据库或面向对象数据库主要是用于管理结构化数据的， 因而，传统的数据库技术不适合用于半结构数据的管理。目 前，国际数据库 界已 把“ 半 结 构 数 据的 有 效管 理问 题” 列 入 未 来1 0 年的 重 要 研 究 方向 之 一仁 x m i 作为w e b 上一种新的数据表示及交换标准， 使得通过 i n t e r n e t 进行 数据交换和集成成为可能。x m l是一种面向正文的数据模型，这种数据模型 非常类似于半结构数据模型。我们知道，h t m l语言是面向表现 ( p r e s e n t a t i o n )格式 ( 布局)的，信息的内容靠用户来理解;而x m i 语台 则是面向内容的，其语义是隐含在语言的标记之中，因此 x m l 更适合用来表 t数据。基于 x m t 的w e b 数据不仅是一种新的w e b 数据组织形式，而且面向 数据交换的特性推动了w e b 应用模式的发展，它反映的是有结构且有自 描述 能力的数据. x m l 另 一 个令人感到振奋的特点是， 它的出现将把w e b 变成d q o 因此，将w e b 上的半结构数据迁移到x m l 上是对w e b 上海量数据进行有效管 理的十 分有意义的一步，该领域也是目前国际上一个新的研究热点。 综r . 所述，建立一个高效的基于x m l 的半结构数据的索引机制对于海量 哈尔滨工程大学硕士学位论文 的w e b 数据的管理是十分重要的。 1 . 2半结构数据的问题与挑战 目 前 w w w己成为全球信息传递与共享最具潜力的信息资源。w e b 提供了 信息交换简单而通用的标准。正是由于w e b 的出现，使得电子数据的管理从 最初直接以传统的、 具有良 好结构的数据库， 以及后来使用h t m l 页面的大量 手写的无结构数据，发展到了今天的爆炸性增长的半结构数据阶段。 随着工 。 t e r n e t 的出现， w e b 数据库成为一个新的研究领域。 新的环境使 数据库面临着4 个方面的变化圈 : . 数据容量的变化;数据量的急剧增长使数据库技术面临一个海量数 据的管理问题。 . 数据内容的变化:数据内容呈现一个多方位的方式，要处理的东西 也越来越复杂甚至包括了过程、程序等行为模型这样的一系列内容。 . 系统本身的变化:系统体系结构上的变化对数据库系统本身的系统 结构和处理能力也提出了挑战，其中包括主储存器及外存储器的容 量和价格的变化、通信速度的变化等。 . 数据应用的变化:数据应用呈现出多样化的空间，数字图书馆、电 子出版物及电子商务、远程教育等移动计算给数据库技术提出了新 的问题。 现在， 数据库技术首先要解决的问 题是: 数据库与i n t e r n e t 之间 有没有 可能的结合点。原有的数据库技术面对的空间是若干数据库在一定的网络空 间上 连结起来的 4 个世界，在这个世界上它可以实施相应的技术，使用户有 效地管理各自 地数据库。并集成起来去完成一定的任务。在w e b 世界中，这 一 情况发生了本质的改变。w e b上存储的是一些无结构的数据。每个站点上 的数据都是在无序的状态下自生自 灭。如何在这上面有效实施数据库管理技 术，这与传统的数据库管理技术存在本质上的差异。 从广义数据库理解的角度来说w e b 是一个数据库，它是指一组相关的有 用信息的集合:从狭义的角度来说w e b 不是一个数据库，因为它不是按一定 数据模型组织的数据的集合。 哈尔滨工程大学硕士学位论文 定义w e b 数据管理建立在广义数据库理解的基础上，它是指在w e b 环境 下，对复杂信息的有效组织与集成，方便而准确的信息查询与发布。 1 . 3基于x m l 的半结构数据 1 . 3 . 1 x m l 简介 x m l ( e x t e n d e d m a r k u p l a n g u a g e ) l3 作 为 一 种 新 的w w w 上 的 数 据 交 换 标 准， 正在引起人们极大的关注。 x m l 是标准通用标记语言s g m l ( i s 0 8 8 9 7 ) 的 一个子集，用于支持 工 n t e r n e t 上结构文档的交换。和h t m l 相比，x m l 是面 向内容的。x m l因具有更多的语义、良好的可扩展性、简单易用、自 描述等 特点而特别适用于w e b上的数据交换。可以预言，x m l 将成为数据组织和交 换的事实标准; 同时， 大量的x m l 数据也将很快出 现在w e b 上。 目 前， 对x m l 数据的 存储和查询方面的 研究方兴未艾 . x m l 数据模型与半结构化数据模 型有很多相似性。可以说，x m l是w w w上的半结构数据，它既为半结构数据 的研究提供了广阔的应用前景，同时也推动了半结构数据研究的发展。 x m l 具有以下主要性质: . 扩展性。x m l 是一种用于设计标记语言的原语言，而不是象 h t m l 那 样， 是一种只有一个固定标记 集的 特定 标记语言。 x m l 允许用户根据 其需要创建自己 的标记， 这些标记可通过 x m l d t d ( d o c u m e n t t y p e d e f i n i t i o n ) 加以定义， 枷114l 的 可扩展性就 在于此。 . 灵活性。 x m l 提供了一种结构化的数据表现方式， 从而使用户界面与 结构化数据相分离。 . 自 描述性。x m l文档通常包含一个文档类型 ( d t d )声明，从而便于 机器理解数据的意义。 x m l 文档中的数据可被任何能够对x m l 数据进 行解析的应用程序所提取、分析和处理，并以所需格式显示。 1 . 3 . 2半结构数据简介 目 前，w w w上存在着各种形式的数据， 其数据结构的组织方式也各不相 同。 一种极端情况是: 传统的关系或面向对象的数据是完全具有结构的数据; 另一种极端是: 还存在着一些完全没有结构的数据， 如影像 ( i m a g e s ) 文件、 3 哈尔滨工程大学硕士学位论文 声音文件以及原始的文本文件等。然而，现实世界中大多数数据则处于两种 极端情况之间，究其原因也是多方面的: ( 1 ) 数据可能是有结构的，但用户对其并不知晓; ( 2 ) 用户可能知道其结构，但为了浏览有意将其忽略掉; ( 3 ) 结构可能隐含在数据中 ( 如具有格式的文本文件中的数据) ， 而不 是象传统d b 中那样，具有明显、严格及规整的结构; ( 4 ) 数据可能具有非传统的格式，如a s n . 1 交换格式; ( 5 ) 数据的模式可能十分巨大且经常变化，因而不得不将其忽略。 由 此，人们提出了半结构数据的概念19 1 。 半结构数据是介于严格结构化 的数据( 如关系或面向对象d b 中的数据) 和完全无结构的数据( 如声音文件、 图象文件等)之间的数据形式。半结构数据具有如下一些特点: ( 1 ) 隐含的模式信息。 半结构数据具有一定的结构， 但其结构与数据混 在一起，没有显示的模式定义， 如h t m l 文件。 ( 2 ) 不规则的结构。一个数据集合可能由异构的元素组成，例如学生集 合中某些学生有电子邮件地址，而另一些学生则没有。同样的信息 可能由不同类型的数据表示，例如某些姓名是字符串，而另外一些 则是由f i r s t n a m e 和 l a s t n a m e 组成的复杂结构。 ( 3 ) 没有严格的类型约束。由于没有一个预先定义的模式，以及数据在 结构上的不规则性，所以缺乏对数据的严格类型约束。 w e b数据的不断增长和异构数据源集成的 应用，导致了 大量半结构数据 的产生。这些数据的一个显著特点是结构隐含、不规则或不完整。例如:对 于一 个有关商品信息的w e b 页面集合，虽然每一个页面描述的商品不同，但 它们都包含了相似的信息 ( 货号、单价、颜色、外型、规格、单位、产地、 性能等) 。 这一信息框架隐含在数据中， 通常需要通过分析工具 ( 如文本分类 器等)刁能获得。由于没有严格的结构限制，有的页面则可能会多出若干信 息。另外， 每条信息的表达方式也可能不尽相同。例如对产品性能的表示， 有的可能用表格形式表示，而有的则可能使用一段有关产品性能的文字描述 来表示。 从传统的关系数据库来看，数据结构不规则的原因是缺少预先定义的、 固定的，且独立于数据的模式框架。由于半结构数据是自 描述数据，数据中 4 哈尔滨工程大学硕士学位论文 可能存在模式，但模式与数据间的界限模糊，新数据的加入没有预先定义的 模式约束，所以这种由数据描述的模式会随着数据的不断增多而扩展。 由上面的讨论我们可以给出这样一个定义:半结构数据是介于严格结构 化的数据 ( 如关系或面向对象 d b 中的数据) 和完全无结构的数据 如声音文 件、图象文件等)之间的数据形式。 1 . 3 . 3 x m l 与半结构数据关系 x m l 数据模型与半结构数据之间的对应是非常明显的。可以说x m l 就是 半结构数据的一个特例,0 1 。 许多 用于半结构数据管理的技术都可以 很容易地 应用到x m l 数据上。 例如， 用于描述半结构数据的。 e m 模型 ，1， 2 幻 就可以 稍加 改进后用来表示x m l 数据。 s t a n f o r d 大学数据库研究组就将其开发的用于半 结构数据管理的原型系统l o r e e l2 1 ， 移植到完全基于x m l 的数据模型上， 并相 应地对其查询语言进行了扩充。 半结构数据地结构类似于图或树。这种结构通常称为有向标记图。x m l 图也可以认为是一种非常灵活的数据模型。一个x m l 图通常满足下列条件: ( 1 ) 图的顶点由唯一的字符串标识，称为对象标识 ( 0 工 d ) ; ( 2 ) 图的边用元素标记 ( e l e m e n t t a g )来标记; ( 3 ) 图的结点用一组属性值标记; ( 4 ) 图的叶结点由值 ( 字符串) 标记; ( 5 ) 图有一个根结点。 由此可见， x m l 图非常合适描述分布的、多态的、动态变化的w e b 数据。 而另一方面，数据 ( 包括不规则数据)与x m l 图也能很方便地直接映射。 例 如， o e m 模型与x m l 图之间的对应关系就非常简单: o e m 对象对应于x m l 中的 元素 ( e l e m e n t ) ; o e m中的子对象关系反映了x m l中元素嵌套。它们之间的 不同 之处在于x m l 的子元素可能是有序的，并且x m l 元素可能包含 ( 属性， 值)的列表。为了支持x m l 的这两个特点，可以 在o e m 模型中引入如下三个 新特性:( 1 ) 有序的子对象;( 2 )( 属性， 值) 列表: 以及 3 ) 引用边( r e f e r e n c e e d g e ) 。通过上述修改，o e m 就能很容易地成为支持x m l 的数据模型了。 哈尔滨工程大学硕士学位论文 1 . 3 . 4 x m l 文档索引概述 索引x m i 文档和关系数据库索引以及面向 对象数据库索引，在很多方面 是相通的。都期望能实现信息的快速访问，都要在访问时间和存储空间之间 选择一 个折衷方案。利用存储空间来记录数据项的位置，这在一定程度上减 少了访问时间，可以执行较快的查询。在数据库中，可以在数据值上创建索 引，例如，数字和字符串，同时也可以在结构化的连接上 创建索引。 x m l文档又是相当特殊的，它有一个共享的 ( 虽然也是易变的)结构， 可以 跨多维进行浏览， 例如， 元素/ 子元素， 元素/ 属性， 元素/ 字符数据， 节 点/ 兄弟。 开发支持快速访问的数据结构时， 可以将每一维单独处理。 在关系 数据库中，可以浏览的唯一的结构化维是跨连接的，例如，在主键和外键约 束之间。关系数据库中的结构化索引，主要包括创建数据结构以便高效地访 问那些给定了主键值的表记录。而在面向对象数据库中，对象可以有一个特 殊的互连结构，这取决于每个类的定义。虽然它与关系数据库的连接类似， 但其访问模式可能有很大的不同。因为，访问发生在面向对象数据库编程语 言的方法中， 而不发生在陈述性语言中， 例如， s q l 。 面向对象数据库可以创 建与关系数据库相似的索引。但是，面向 对象数据库的索引 通常更关注于: 给出最可能访问的对象，使用映射对象标识符的虚拟内存存储模式，来达到 最高效的 物理存储。 可以 通过父/ 子元素关系、 元素兄弟关系、 文档次序、 或 者链接等来浏览x m l 文档。 1 . 4国内外研究现状 目前数据库研究界把数据分为了三大类型，即:无结构数据、结构数据 和半结构数据。 半结构数据有其内在的结构， 但这种数据可能表现得不规则， 或者其结构可能经常变化，甚至可能不完整，并且同样的概念还可能使用不 同的类型表示。另外，在给定的时间内，数据的结构可能不是完全清楚知晓 的。目 前w e b 页面上所包含的信息绝大部分均是这种半结构类型的数据。因 为w e b 上的数据通常是嵌入在h t m l 中的， 故这种数据的一 个显著特点是具有 易变性和无规则性，也就是说整个结构是经常变化不定的。另外，异构数据 源上的数据集成也同样存在着半结构数据的问 题，因为相同 类型的数据在不 6 哈尔滨工程大学硕十学位论文 同的数据源中，可能使用不同的模型表示 17- 19 1 数据库是从6 0 年代初发展起来的计算机技术。 经过二三十年的发展， 数 据库技术己经趋于成熟。从应用领域、采用的数据模型及相关技术的三维空 间可以看到数据库形成的门类:数据库与相关技术相结合形成的分布式数据 库、并行数据库、知识数据库、演绎数据库等;数据库在具体应用需求的基 础上形成了工程数据库的研究领域、地理分析系统数据库、数据分析决策等 一系列分支;同时，数据大量积累形成了一个新的应用需求，它带来了数据 仓库、联机分析处理等技术。 以数据库观点， x m l 文档可看作数据库， 它的d t d 看作是数据库的模式。 但数据库与x m l 文档是有区别的，数据库的数据结构性很强，而x m l 更适合 描述半结构化数据。x m l数据库是可以对 x m l 文档进行存取管理和数据查询 的数据库。 x m l 数据库可以通过三个方法集成w e b 技术和数据库系统: ( 1 )通过把文档转换为关系或对象，x m l文档可以存储在一个关系 型或面向对象的数据库管理系统中; ( 2 )用数据库软件把数据库中现有的关系或对象表示为x m l ; ( 3 )用一个基于x m l 的数据模型创建一个新的d b m s . 目前，x m l 数据库主要有两种类型:x m l 本源数据库 ( n x d , n a t i v e x m i d a t a b a s e )和支持 x m l 的数据库 ( x e d b，x m l - e n a b l e d a t a b a s e ) 。因此，对 半结构化数据的索引主要有两种处理方法，即将关系型或面向对象型数据库 的索引应用于半结构化数据，例如:e n a b l e x m l d a t a b a s e和建立新的索引 结构来适应半结构化数据，例如:n a t i v e x m l d a t a b a s e 。两者之间的比较见 表 1 . 1 。 表1 . 1 x m l 数据库的比较 特点 关系比较成熟，结构简单，稳定，叶子节点聚具较好 对象善于管理大对象，可扩展性差 n a t i v ei r 风格，没有很好利用s c h e m a 信息来帮助，浏览，查询处理， 优化 n x d 是专门对 x m l数据格式的文档进行存取管理和数据查询的数据库。 哈尔滨工程大学硕士学位论文 目 前截止2 0 0 2 年6 月， 正式公布的n x d 产品有2 3 种， 其功能各具特色。在支 持对x m l 文档管理的同时，不同程度的增加了一些附加功能。比较著名的产 品有 t a m i n o , d b x m l , e x c e l o n和 x h i v e / d b ，分别由美国的 s o f t w a r e a g 公司、 d b x m l g r o u p l l c 公司、 e x c e l o n 公司 和荷兰的t h e c o n n e c t i o n f a c t o r y 公司研制。 比如， t a m i n 。 是第一个商用n a t i v e - x m l 数据库， 其最新版为2 . 3 . 1 ( 2 0 0 2 - 5 ) ，系统除了具有n x l 的基本功能外，还提供与其它数据源的调用 接口，可以对关系型收据进行存储管理。其管理界面是基于w e b 的，与主流 的关系数据库管理系统相似， 包括与 数据库交互和对数据模板 ( e d i t t i n g s c h e m a s ) 进行编辑的 g u i 工具. 其查询语言是基于x p a t h ，有直接x m l 检索 和特殊检索的能力，可实现对任意数据元的检索，其功能在某些方面甚至超 过传统s q l ( 根据g a r t n e r g r o u p 的 研究报告) a t a m i n a 有w i n d o w s n t , w i n d o w s 2 0 0 0 , s o l a r i s 和s c o u n i x 等版本。 t a m i n 。 适用于需要从多种不同平台和 格式整合信息并向 业务伙伴或客户散发这些信息的机构。 x e d b 是在传统数据 库的基础r . ,通过增加对x m l 数据的管理功能，从而实现对x m l 数据的管理 的数据库。 x e d b 的主要用途是实现数据关系不太复杂的x m l 文档与传统数据 库之间的转换。 目 前己 经知道的x e d b 产品 有a c c e s s 2 0 0 2 , s q l s e r v e r 2 0 0 0 , i b m 的 d b 2 x m l e x t e n d e r , 、f i l e m a k e r、f o x p r o、i n f o r m i x o b j e c t i v i t y / d b、o r a c l e 8 i , 9 i . . x m l 数据库的主要用途可以 概括为两方面:对基于x m l的数据进行有效 的管理、对基于w e b的各种数据源进行集成。如果建立的数据库是基于w e b 的， 同时管理的信息具有半结构化特征， 那么最好使用 x m l 数据库。 目前x m l 数据库在有效的存储组织、 合理索引结构、 数据库系统的安全性、 事务处理、 数据完整性、触发器、多用户处理机、数据的聚合能力等方面还有待提高。 另外，标准众多，缺乏统一的数据库开发标准。 目 前，国内外关于半结构数据的研究主要集中在新的数据模型、 查询模 式、存储技术以 及优化技术等方面。基于x m l 的半结构数据索引的研究主要 集中于文档数据的表示( 节点的数据结构) 、 索引的结构和检索的算法， 在算 法中会考虑索引的存储空间和索引的更新。另外，文档数据的表示和索引的 结构不同，对检索的算法影响也较大。索引的结构主要有倒排文件 ( 工 n v e r t f i l e ) 、 文档/ 条目 矩阵( d o c u m e n t 八e r m m a t r i x ) , t r i e ( 带标记的树状索引) 、 哈尔滨工程大学硕士学位论文 p a t r i c i a t r i e( 带字符串压缩的t r i e ) 、 后缀树 ( s u f f i x t r e e ) 和p a t t r e e ( p a t r i c i a的s u f f i x t r e e ) 。 检索算法主要有从根到叶、从叶到根、从根和 叶分别开始在中间相遇和从任意一个节点开始到另一个节点终止四种。在不 同的索引中，会根据其索引结构选择相应的检索算法。下面列举几种在国内 外常见的半结构化数据索引: 川 b u s 索引 ( b o t t o m - u p s c h e m e ) z0 - 2 ， 支持 结构和内 容两 类查 询。 从全部节点中找出与查询的结构相匹配的部分，并将这部分按查询中关键词 的出现频率排序。 b u s 索引由d o n g w o o k s h i n 在文献 2 0 中 提出。 b u s 己 经被 应用于s u n公司开发的s o l a r i s 操作系统并且工作正常。目前，b u s 可应用 于s g m l 文档， 如果将s g m l 解析器用x m l 解析器替换， b u s 也将能应用于x m l 文档。 ( 2 ) x i s s ( x m l i n d e x i n g a n d s t o r a g e s y s t e m ) u 是一 种适用于规则 路径查询的索引引擎( i n d e x e n g i n e ) . x i s s 以 间隔 编码( i n t e r v a l e n c o d i n g ) 为基础。 x 工 s s系统有五种基本索引结构组成。 x i s s 系统适用于树型结构， 有 利于半结构数据结构的动态改变;主要缺点是需要对树型结构的半结构化数 据进行广度遍历。x i s s索引是亚利桑那州立大学b o n g k i m o o n 教授及其学生 李全中在文献 2 2 中提出的。 ( 3 ) l o r e ( l i g h t w e i g h t o b j e c t r e p o s i t o r y )以 半结构化数据模 型o e m ( o b j e c t e x c h a n g e m o d e l ) 为 基础， 是一 个为 管理半 结构 化数 据而 特 别设计的数据库管理系统。 用于半结构数据管理的原型系统l o r e 由s t a n f o r d 大学数据库研究组开发。 ( 4 ) t o x ( t o r o n t o x m l e n g i n e ) 【， ， ， 是一个x m l 数据库，它支持多种查 询语言和不同的存储模式 ( 关系型、 面向 对象型、原型 n a t i v e ) ， 采用那种 存储类型依文档属性而定。t o x i n ( t o x工 n d e x )是一种最小节点数的弱 d a t a g u i d e型索引，由多伦多大学提出，用来克服通常的半结构化数据索引 只能够处理一部分查询处理的局限。 t o x i n是一种 x m l数据的索引，在查询 处理中采用数据库的全路径结构，综合了面向对象的路径索引和其在半结构 化数据领域的扩展所用到的思想。目 前，t o x i n索引在索引结构的排序、图 形索引结构的实现等方面还需改进。 除了以上四种索引之外，还有 i n d e x f a b r i c e _: , , d a t a g u i d e _,a 和 哈尔滨工程大学硕士学位论文 t - i n d e x 等索引也较为著名。 . 5主要研究工作 本文的主要研究工作主要有两部分。 第一部分，分析己有的典型半结构数据索引，总结半结构数据索引的研 究的主要方面并对索引分类。研究的主要方面包括:索引的数据结构、索引 的检索过程、索引的更新机制和索引的存储等。 第二部分，建立一个支持文档动态更新的高效的半结构数据索引。本文 在b u s 索引的基础上， 提出了一种新的半结构数据索引机制， 该索引具有适 于x m l 文档频繁更新的特点。 . 6论文组织 全文共分五章，第一章是绪论。介绍了半结构数据管理的国内外研究现 状及由半结构数据产生的问题与挑战。并且简要介绍了半结构数据和x m l 文 档以及两者之间的关系，最后提出本文主要的研究工作。 第二章主要介绍了半结构数据的数据模型。首先介绍半结构数据的三种 常用表示形式， 即句法形式、 对象交换模型和o d m g 规范。 并且给出半结构数 据模型基于图论的理论基础。还介绍了x m l 的数据模型，并以x m l 作为本论 文的研究模型。 第三章主要介绍了索引的概念和半结构数据索引的特点和在功能上的要 求。并介绍了研究半结构数据索引的七个方面:数据表示、索引接口、路径 模版的形式、索引的导航方式、节点的定义、索引的更新和索引的存储。 第四章主要介绍了已有的几种典型的半结构数据索引。首先介绍了索引 的建立策略:完全索引、无索引和部分索引。然后介绍依据索引结构的索引 分类:基本索引、路径索引和导航索引。最后分别介绍了三种类型的索引， 由于第三种索引较为复杂，列举了四种最具代表性的半结构数据索引。 第五章在分析了b u s 索引不易于结构文档更新缺点的基础上，提出了一 种支持文档动态更新的半结构数据索引。给出了系统的设计方案，以及索引 哈尔滨工程大学硕士学位论文 的更新算法和查询处理过程，比较提出的新索引较b u s 索引的优势。最后给 出系统的实现和试验结果及其分析。 哈尔滨工程大学硕士学位论文 第2 章 半结构数据的数据模型 半结构数据的模型是对半结构数据进行有效管理的基础，也是基于 x m 1 . 半结构数据管理系统的基础。 本章首先探讨了半结构数据的各种表示形式及 半结构数据模型的理论基础，然后对x m l 数据模型进行了研究。 2 . 1引言 半结构数据通常称为“ 无模式” 或 “ 自 描述”的【1 1 5 1 。也就是说，半结 构数据不存在独立的结构和类型描述。一 般来说，在对数据进行存储或处理 时， 应事先描述出数据的结构 ( 类型、 模式) ， 然后再生成该类型或模式的实 例值。 对半结构数据来说， 通常可以 使用一种简单的句法直接对其进行描述。 我们先来考察以下使用类l 工 s p 语言中的 联合表、 以 标记一 值( l a b e l - v a l u e ) 偶 对的 形 式 描 述 记录 类 型或 元 组 类 型 数 据结 构的 形 式: n a m e : s u n - w e i , t e l : 8 2 5 3 3 4 4 6 , e m a i l : s u n 9 7 6 1 1 s i n a . c o m . c n 。 这种描述形式是一种简单 地含有“ 标记”( 如n a m e , t e l 和e m a i l 等) 和“ 值”( 如， s u n - w e i , 8 2 5 3 3 4 4 6 和 “ s u n 9 7 6 1 1 s i n a . c o m . c n ) 地偶对集合。 要说明的是， 这里的于 值” 本身 还可以 是 其 他的 结 构 形式; n a m e : f i r s t : w e i , l a s t : s u n ,r ， t e l : 8 2 5 3 3 4 4 6 , e m a i l : s u n 9 7 6 1 1 s i n a . c o m . c n ) 。上面这种描述方式亦可使用图 的形式表示之，其中图的结点表示对象，如图2 . 1 所示 name name f i r s t 八8 2 5 3 3 4 4 6 l a s t s u n 一w e i 8 2 5 3 3 4 4 6 s u n 9 7 6 1 1 s i n a . 舍 n 9 7 6 1 1 s in a .c om .c n co m. c n s u n 图2 . 1 简单结构的图形表示 哈尔滨工程大学硕士学位论文 2 . 2半结构数据的表示方法 2 . 2 . 1 半结构数据的句法形式 下面我们使用类 l i s p语