（模式识别与智能系统专业论文）xml数据存储管理系统.pdf

x m l 效维仁储管删系统 摘要 s e t o i 随着i n t e r n e t 的迅速发展，x m l 逐渐成为互联网上信息存储和交换的事实 标准。x m l 阻其语言自身的规范性、灵活性、可扩展性以及强大的语言表达能力， 在诸多的领域得到广泛的应用，诸如数字图书馆、电子商务等。届时，互联网上 将会有大量的x m l 数据信息。因此，如何高效的存储管理x m l 数据信息，是一个 很有研究价值和应罱前景能漾题。 本文从数据存储与更新、数据查询的角度来考虑系统的实现，研究重点放在 数据存储和数据索引两方面。 对于数据存储，采用基于模型的原生x m l 存储方法数据模型为树模型吼 b 树作为存储结构，底层存储采用面向对象的存储管理系统。此外，为了改进存 储的更新性能，对每个元素节点对象进行标识，该标识既可以作为元素对象的逻 辑引用，又可以作为b 树的键。 对于数据霉弓l ，采用改选鸽分层p a r r i o t at r i e s 素弓作为主索 ，甬于对 x m l 数据层欠进行导航，并且对x m l 文档的结构和内容同时进行索引。此外，为 了解决主索引对于相对路径查询需要大规模遍历的问题，我们设计了模式路径哈 希表作为辅助索引，用于在主索引执行相对路径查找之前计算相对路径查询的绝 对路径，使主萦引的遍历负荷大大减轻，从而使相对查询的效率提高。 关键词：x m l 数据库，存储，索引，查询，检索 f l ! ；i 论史x m l 数话存储管理系统 a b s t r a c t w i t h 口r o m d td e v e l o p m e n to fi n t e r n e t ，x m li se m e r g i n ga s t h ec o 0 m l e n s t a n d a r df 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 x m li sa p p l i e dw i d e l yi n v a r i o u sk in d so ff i e l d s ，s u c ha sd i g i t a ll i b r a r y ，e - c o m m e r c e ，a n ds oo n ， b e c a u s eo fi t si n h e r e n tn o r m a l i t y f l e x i b i l i t y ，e x t e n s i b i l i t ya n d e x p r e s s i v ec a p a c i t y ，t h e r ew i l lb eah u g ea m o u n to f 轧d a t af l o o d i n gjn t h ew o r l dw i d ew e bb e f o r el o n g t h e r e f o r e ，h o wt oe f f i c i e n t l ys t o r e ， r e t r i e v e a n dm a n a g ex i ld a t ai sav a l u a b l er e s e a r c ht o p i cw i t hb r i g h t a p p l i c a t i o np e r s p e c t i v e t h isp a p e rm a i n l yt a k e sd a t as t o r a g e ，u p d a t ea n dq u e r ya se m p h a s e sf o r i m p l e m e n t a t i o no fx m ls t o r a g em a n a g e m e n ts y s t e m ，a n dt h er e s e a r c ht o p i c 1ie so nx m ls t o r a g ea n di n d e xs t r u c t u r e s f o rs t o r a g e w ec h o o s en a t i v ex 瓣，m o d e lb a s e ds t o r a g e ，d a t am o d e l i s t r e em o d e l ，a n db a s i cs t o r a g es t r u c t u r ei sb - t r e eo nt o po fo b j e c to r i e n t e d d a t a b a s es y s t e m i no r d e rt o i m p r o v eu p d a t ep e r f o r m a n c e ，w ea s s i g n a u n i q u ei d e n t i f i c a t i o nt oe v e r ye l e m e n ta sr e f e r e n c et h a ti sa l s ot h ek e y o fb t r e e ， a sf o ri n d e x ，w ed e s i g nt w ot y p e so fi n d e x e sf o rq u e r i e s o n ei se n h a n c e d l a y e r e dp a t r i c i at r i e si n d e x ，w h i c hi sd e s i g n e df o rs t r u c t u r a ln a v i g a t i o n t h r o u g hx m lh i e r a r c h i e s i ti n d e x e sd o c u m e n t s t r u c t u r e sa n dc o n t e n t s s i m u l t a n e o u s i y t h eo t h e ri ss c h e m ap a t hl o o k u ph a s ht a b l ei n d e x i t ls u s e dt oe v a l u a t ea b s o l u t ep a t h sf o rg e n e r a lr e g u l a rp a t he x p r e s s i o n s ，s u c h a sr e l a t i v ep a t he x p r e s s i o n s ，s oa st or e l i e v et h ew o r k l o a do fl a r g es c a l e o f n a v i g a t io r la n ds p e e du pq u e r i e s k e y w o r d s ：x m l ，d a t a b a s e s ，s t o r a g e ，i n d e x ，q u e r y ，r e t r i e v a l 顺f 。论上x m l 数把存储管理系统 1 绪论 随着互联网的发展，x m l 逐渐成为一种通用的数据存储与信息交换的数据格 式。x m l 由于其语言自身的规范性、灵活性、可扩展性和强大的语吾表达能力， 被普遍应用于诸多领域，如数字图书馆、电子商务等。不久的将来，大量x m l 格 式的数据文档随之出现。因此，如何有效的存储和管理x m l 数据将是一个颇有研 究价值的重要课题。 1 1 】眦简介 1 1 。1 半结构化数据 - 传统的数据库系统通常是基于固定的模式定义和数据类型。随着近年来互联 网应用欧迅速发展，越来越多的应用程序产生了大量的格式不固定的不规则数 据，这些数据通常不遵循固定的数据模式或者数据模式经常变化，因此称之为半 结构化数据 4 5 6 儿7 。x m l 就是一种带标记的半结构化数据。 半结构化数据通常单独存储，除了一些结构验证符外，并不遵循事先定义的 固定模式。半结构化数据模型通常用图来表示，并且图是动态的。对半结构化数 据而言，数据的结构是数据的部分，具有自描述性，所以更新图结构和更新数 据一样容易。在实际应用串，来自不滴数据来源的数据。可能具有各自不同白勺图 结构。如果要将它们存储在同一图结构中，图结构必须进行调整以适应不同的数 据，这就使半结构化数据具有异构的特性。因此，半结构化数据的模式是自描述 性的、可演化的。图1 1 ，ll 表示了半结构化数据模式的动态演化过程。 大多数半结构化数据模型用有向图来组织半结构化数据，顶点表示对象，带 标记的边表示对象之间的关系。有向图中的数据具有自描述性。有些对象是原子 类型。其值是某羊申基本数据类型( 如整型，实型，字符型等) ；有些对象是复合 类形，其值是该对象的对象标示符( o l d ) ，对象标示符即为指向对象存储的指针 或引用。 坝f 论文x m l 数据存储管理系统 数据库系统 j a v a 编程+ j a v a 编程 图1 1 2 1 中用圆表示元素或属性节点，方框表示文本，并且此种表示把元一 豫i ： 素节点和属性节点同等对待，边及边标记( 元素名或属性名) 表示节点间的关系。 x m l 文档的图表示很类似与半结构化数据的图表示，但是通常情况下，x m l 中的 元素或属性节点是有顺序的，而半结构化数据中的元素没有顺序之分，且没有属 性。 1 2x m l 存储方法概述 随着近年来对x m l 数据库技术的深入研究，出现许多存储x m l 的方法以及各 种数据库产品 2 6 。 按照我们的理解，根据x m l 在存储时逻辑层模型与x m l 数据模型是否一致这 一原则，可以分为原生x m l 存储( n a t i v ex m ls t o r a g e ) 和非原生x m l 存储 ( 1 0 l l n a t i v ex m ls t o r a g e ) 。对于原生x m l 存储，其逻辑存储模型保留了x m l 文档的固有特性，即与原有x m l 文档结构保持一致。根据底层物理存储模型的差 异可以分为基于文本的和基于模型的；对于非原生x m l 存储，其逻辑存储模型通 常与其底层数据库模型保持一致，所以在将x m l 文档存入数据库之前需要按照一 定的规则将x m l 文档的结构映射到相应的数据库模式。根据底层数据库类型的不 同可以分为面向关系型、面向对象型等。 倾 j 论文 x m l 数据存储管理系统 1 2 i 面向关系 面向关系的x m l 存储方法以关系数据库作为底层存储，它是以关系数据模型 为基础，所以x m l 文档存储时需要按照一定的方法映射到关系数据库的一系列表 中进行存储 1 9 。 当x m l 文档进行存储时，首先要根据x m l 文档的d t d ( d o c u m e n tt y p e d e f i n i t i o n ) 生成关系数据库的关系模式，再对符合该d t d 的文档进行解析并存 入现有商业关系数据库( 如o r a c l e9 i ，i b md b 2 等) 的一系列表中；当要对x m l 文档进行查询时，首先x m l 查询语言( 如x o u e r y 2 8 等) 语句转换成s q l 查询 语句对关系数据库进行查询，在将查询结果转换为x m l 形式返回。 面向关系的x m l 存储方法最大的好处在于可以利用成熟的关系数据库技术 对x m l 数据进行存储，并以相同的查询方式( s q l ) 来对一般数据和x m l 数据进 行查询。 当然，面向关系的x m l 存储方法也存在一些缺陷 8 。首先，它必须根据x m l 文档的d t d 产生关系模式，并制定一些映射规则将x m l 元素或属性映射到关系表 中。当x m l 文档较为松散或不规则时，制定映射规则通常较困难。由于一个x m l 文档的元素可能存于多个表中，每次查询往往要由多个中间结果集通过连接运算 产生最终结果集，从而使查询变得困难，效率大大降低。 1 2 2 面向对象 面向对象的f 4 l 存储方法以对象数据库作为底层存储，它是以对象数据模型 为基础。与面向关系的存储方法类似，面向对象的方法首先要利用d t d 或x m l s c h e m a 建立x m l 数据的o o d b 模式，再将文档按照一定的规则将x m l 文档的元素 映射成对象数据库中的一系列对象 9 。 此种对象模型并不是文档对象模型d o m ( d o c u m e n to b j e c tm o d e l ) 2 7 。所 有x m l 文件的d o m 都是一样的，而此对象模型对于每个d t d 所定义的x m l 文档都 不一样。图1 2 2 1 是一销售订单及其对象模型树，该对象树由四个类组成： s a l e s o r d e r ，c u s t o m e r ，i t e m ，和p a r t 。 面向对象的存储方法支持复杂数据类型，可以较为直观的建立x m l 数据的对 象模式，从而可以利用对象查询语言( o q l ) 实现对x m l 数据的结构化查询。同 时，对象方式存储具有较高的存储与查询效率。 但是对于没有d t d 或s c h e m a 的x m l 文档，无法定义映射规则。虽然文献 i0 3s t o r e d 系统可以采用数据挖掘技术来抽取x m l 文档的部分模式，但对于不 坝i 论文x m l 数绝_ i 享储管理系统 符合的模式的数据必须单独处理。而且对于模式经常变化的x m l 文档，该方法基 本上不可能实现。 1 2 3 基于文本 图1 2 2 1 销售订单及对象树 基于文本的x m l 存储方法通常有两耳中：一种是以义本文件形式存储在文件系 统中，为了提高查询效率，还需建立相应的索引。另一种是以v a r c h a r s 或者b l o b s 类型数据存储于关系数据库中。 基于文本的x m l 存储可以利用标准的文本索引技术，通常具有较高的查询效 率。但是基于文本的存储一个很严重的缺陷就是，索引维护困难。每次修改x m l 文档中的数据都可能导致文档索引的重新构建，因为谚方法索引定血通常是蛆数 据在文件中的物理位置或物理指针来定位的，一旦数据修改都可自e 导致其它数冤 指针的变化。 1 2 4 基于模型 基于模型的x m l 存储通常需要定义逻辑存储模型，底层可以用关系数据库、 面向对象数掘库或者文件系统来实现存储。该存储方法基本保留原有x m l 文档的 结梅。所h 存储时无需进行晚射。与基于文本的方准一样，基于馕型的方法也要 为x m l 文档建立相应的索引来提高数据的访问与查询效率。此种方法具有较高的 综合性能，如存储效率、更新效率、查询检索效率。目前对x m l 存储的研究大鄯 是基于模型宫毫方法。本文后续章节还椿洚缀论述， 坝卜论文x m l 数妊存储管理系统 1 3x m l 索引方法概述 和以往的数据库一样，设计x m l 数据库也需要建立相应的索引来提高数据访 问及查询效率。根据上一节的论述，我们可以把m l 数据库分为原生和非原生 踟l 数据库，圆此，我 i j 为x 瓯数疆建立素弓逊有两种选择。对子菲凉生x m 乙数 据库，因为数据在存储之前已经按照底层数据存储模型进行相应转化，所以我们 可以利用其底层数据库的索引系统。如关系数据库我们就可以利用关系数掘库的 索引系统；对于原生x m l 数据库，因为其存储保留了原有数据特性所以可以根 据其数据特性来定制索引系统，使其更好的满足各 十性能要求，下面我们主要研 究原生x m l 数据库的索引方法。 1 3 1 索引方法分娄 近年来，对于像x m l 这样的半结构化数据的索引结构，人们进行了大量的研 究。对于原生x m l 数据库索引，大致可以分为三类基本索引、路径查找索引、 结构导航索；i 。 f 1 基本索引 基本囊引。顾名恩义，是x m l 文档最简单、最基本数索弓i 结捣运絮电籁擎 的查找表构成。基本索引不考虑x m l 文档的层次结构概念，如路径、树、有向图 等概念，它只是按照元素、或者属性、或者文本或值等对文档节点进行索引。按 照索引依据的不同，基本索引可以是元素索引( 或者说标记索引) 、属性索引， 文本索弓i 、值囊弓 等。 基本索引不直接支持路径查询，但是查询引擎可以通过将多个基本索引查询 得到的结果进行连接来支持结构化查询。由于每个基本索引的查询只是执行单一 的查询步骤。对于处理复杂的结构化查询。使用基本震弓i 要执行大量匏连接运算 来得到最终的查询结果，只使用基本索引来实现结构化查询通常是低效的。 因此，基本索引通常作为更高级的结构索引的辅助索引来使用，这样就把大 量的查询工作负荷从查询引擎转移到索引引擎。 值得提出的是，基本索引对自顶向下。自底向上的查询计划都适用。 2 路径查找索引 路径查找索引，是对整个文档的所有路径进行索引。与基本索引不同的是， g a 弪查找索引保荐了每个节点的结构上下文信息 ，所以不需要查询引擎在查询计算时重新构建路径。 f _ ! i f f 。论义x m l 数据存储管理系统 路径查找索引一般只适用于自底向上的查询计划。 为了理解路径查找索引，我们举一个具体的例子。文献 1 2 中提到的c i s 索 引就是一种路径查找索引方案，以及文献 2 4 中提到的e 1 e m e n tl o c a t o rs c h e m e 。 c i s 索引结构包括一个将关键字映射到带对象标识的标记路径的表。图1 3 1 1 晚明了该索引结构。 ”二n d e x ”砖 ” 冀l ” ”j d ( ” 图i 3 1 1 路径查找索g 3 结构导航索引 结构导航索引使用树或者有向圈作为其主要数据结构来表示x m l 文档的结 构纲要信息，并保存了x m l 文档的所有路径。索引中的每条路径可以看作是多个 基本索引查找的一个预连接。 与路径查找标索引不同的是，大多数结构导航索引以一种紧凑的表示来描述 数据库图的结构纲要，而不重复保存相同的路径前缀。 结构导航索引通常采用自项向下的查询计划。 f 鲫f 论义 x m l 数据存储管璀系统 1 3 2 几种典型的索引方案 根据以上分类，我们选择以下几个典型的系统来说明相应索引方案的优点以 及存在的缺陷。对于如何评判索引机制的优劣，我们主要从以下五个重要方面柬 考虑。 数据表示( d a t ar e p r e s e n t a t i o n ) 数据表示包括数据在数据库中的逻辑表示以及索引结构的逻辑表示。 由前面章节可知，半结掏化文档可以用有向图来表示。通常数据库中所有又 档的图都包含在一个统一数据库根结点下形成单一的数据库图，然后对整个图进 行索引。但是，也可以对每个文档图单独进行索引，查询时返回所有单个索引查 询返回的结果集。 素弓1 的逻辑结构通常可以用表、树或有向图来表示。 导航性( n a v i g a t i o i l 导航是指在查询过程中，沿着结构索引的路径，对查询计划的各步进行依次 匹配的过程。与查询执行策略类似，索引导航也有四种策略：鱼底向上、自顶向 下、混合、由里向外。最常用的导航方法是自顶向下的方法是沿着树或图的自煞 方向，如树的导航从根节点到叶结点；自底向上的方法与自顶向下的导航方法相 反；混合包括自顶向下和自底向上两个方向的导航，并且在结果节点相遇；由单 向外的方往是凰串菜个节点向上稻向下两个方向导航。 节点标识( n o d ei d e n t i f i c a t i o n ) 节点标识是对文档中单个节点进行唯一标识。不同的索引方寒可以采用不同 的节点标识方案。有的索引方案可以采用特殊的节点标识方案来编玛父子关系或 者祖先子孙关系等。 索引更新( i n d e xu p d a t e ) 由于数据库中的数据可能会修改，索引也要随之变化。一种良好的索引结构 蔓荥索弓 2 够增量更耨，也就是说当数据痒鄯分数据改受讨，索g 维构中只是稻 应的索引部分随之改变，而不需要对整个索引进行重构。 索引存储( i n d e xs t o r a g e ) 索引同数据库中数据一样也要进行存储，必然会占根一定的存储空间，而且 索引大小决定了索引是否能常驻内存。不同的索引结构其大小差别很大。基本系 引和路径查找索引通常较小，可以直接装入内存；而结构导航索引通常很大，以 致于很难直接装入内存。所以设计索引应尽可能小， 坝i 论文x m l 数据存储管理系统 x i s s x i s s ( x m li n d e x i n ga n ds t o r a g es y s t e m ) 11 是个针对规则路径表达 式查询的索引引擎系统。它提出一种特殊的节点标识方案，称为扩展前序编码 用来快速决定x 札数据元囊之间的租先子孙关系。节点标识表示为 ，o r d e r 裹示节点前序顺序值，s i z e 表示该节点所能容纳的最大 子孙数目。此外，它还提出了几种处理规则路径表达式的连接算法：e j o i n 、 a j o i n 、kc j o i n 。 ( 1 ) e e j o i n 用来查找从元素到元素的路径。对查找长路径或长度未知 的路径尤为有效。 ( 2 ) e a - j o i n 用来对排序的元素和属性进行扫描以发现元素属性对。 ( 3 ) kc j o i n 用来发现重复路径上的e l e e n e c l o s u r e ， x i s s 系统有五种索引，其中主要三种索引为：元素索引、属性索引、结构 索引，这三种索引都是基本索引。元素索引与标记索引相似，输入标记和文档 i d 。返回旭应元素集；属性素引与元襄囊引类似，只是返回的是羼性集：结媳客 引用于为给定元素查找父元素、所有子元素、及属性，也可以为给定属性查找父 元素。 1 数据表示 狐s s 系统采用树结构泉存储x 乩数据，树节点可以表示l 魏据的元素、 属性或文本数据，节点之间的父子关系用来表示x m l 数据的嵌套关系。同时，为 了快速计算和确定任何两个节点之间的祖先子孙关系，该系统采用了种特殊 的节点标识方案，即扩展煎序编码，垓系统的索引系缝包括五种震 【。其中三转 主要索引( 元素索引、属性索引、结构萦引) 都是基本索引。尽管x i s s 系统提 出了三种连接算法来提高查询过程中连接运算的效率，但是对于一个复杂的结构 化查询仍然要花费执行大量的连接操作的开销。 2 导航性 x i s s 系统采用的都是基本索引，而基本索引没有比节点更复杂的结构化单 元，所以该系统的索引机制不具备导航性。 3 节点标识 x i s s 系统采用了特殊的扩展前序编码来快速计算以确定节点z 间的祖先子 孙关系。 4 索引更新 x i s s 系统也予采用了特殊的节点标识，当插入节矗时子孙节点数目不超过 插入基点的最大子孙节点数目时，索引更新是增量的。但是当超过时，则整个震 坝f j 论义x m l 数捌存储管理系统 引都要重新构建；删除节点更新是增量的。 j 索引存储 x i s s 系统采用的都是基本索引，所以空间消耗较小，并且即使对于大型敛 据库也可能适于常驻主存。这些基本索引可以用标准的索引结构b 树来实现。 c i s 文献 1 2 提出的c i s 索引基于唯一节点标识对路径进行标注，以区分标记路 径的二义性并对这些路径按照关键字进行索引，形成由关键宰映射到路径的表 所以称为带标注的路径查找索引。国l3 1 1 表示了该索引的结构。 i 数据表示 c i s 索引与普通的路径查找索引一样本身是扁平的，它将层次结构信息( 如 标记路径) 以原子的形式保存在查找表串。路径查找索5 1 只局限于 蜀状的数据库 而不适用于图状数据库，原因有两点：( 1 ) 对于图结构，节点可由多条路径达到， 如果是有环图则可能有无限多个，从而使得前缀匹配更复杂。( 2 ) 每一次关键字 查找，都可能返回同文档节点许多路径，这往往不是希望的结果。 2 导航l 生 c i s 索引为路径查找索引并不能构建数据库的树状或图状表示，所以该索引 不具备导航性。 3 节点标识 c i s 索引只要求每个节点有唯一的节点标识，但并不要求节点标识采用特殊 的编码方案，所以c i s 可以兼容其他特殊节点标识方案( 如x i s s 系统使用的扩 展前序节点标识方案) 以提高查询性能。 4 索引更新 c i s 索引如果不采用特殊的节点标识，则更新该索引可以是增量的。 5 索引存储 c i s 索引查找表的存储赝占用的空阊主要取决予数据库中关键字的个数，由 于路径查找索引存储的是简单路径，即从根结点到被索引节点的路径，所以会保 存许多冗余的路径前缀。对于大型数据库，随着数据量的增大，索引的冗余数据 也增大，可能使得该索引不适于常驻内存。 l o r e b o r g ( l i g h t w e i g h to b j e c tr g p o s i t o r y ) e 1 33 是为毒传半结构化数掘 鲡 x m l ) 而专门设计的一个数据库管理系筑。在l o r e 数据库系统中，为了提高查御 倾j | 义x m l 数蛞存储管理系统 处理的速度，可以创建四种不同类型的索引结构 1 4 ：值索引( v i n d e x ) 、文本 囊引( t i n d e x ) 、链接索引( h i n d e x ) 和路径索引( n n d e x ) ， 值索引用于定位特定数据值的原子数据对象；文本索引用于定位包含特定词 或词组的字符串型的原子对象：链接索引用于定位特定对象的父对象；路径索引 用于快速访问经由一条给定标记路径所能到达的所有对象。 上述四种素弓1 钓莳三种素弓1 都是基本索弓1 ，本文只对第四种索引加以分桥。 路径索引( p i n d e x ) 采用d a t a g u i d e 2 3 作为其数据结构。d a t a o u i d e 是数据库 ( 图结构) 任一给定时间点所有可能路径的动态结构纲要，是动态生成和动念更 新的。d a t a g u i d e 也可以作为树结构文挡的索引结构。d a t a g ul d e 既可以为查啦 计算服务，也可以用来浏览数据库的当前结构模式。此外，文献 2 3 还定义了一 种更为特殊的d a t a g u i d e 称为s t r o n gd a t a g u i d e 。我们的论述重点放在上s t r o n g d a t a g u i d e 。 1 数据表示 和其它的结构索引一样，d a t a g u i d e 只对数据库的结构进行索引，而把原子 的内容留给辅助索引处理。d a t a g u i d e 对源数据库中的每条唯一的标记路径 ( 1 a b e lp a t h ) 只描述一次。而不管该路径在源数据库中出现的次数。对于s t 【_ o f l g d a t a g u i d e ，每一给定标记路径在源数据库中所能到达的目标集与其在s t r o n g d a t a g u i d e 中所能到达的对象一一对应，从而保证了结构导航过程不会出现错误 的匹配结果。d a t a g u i d e 本身不支持对多文档图索引。 2 导航性 d a t a g u i d e 支持从根结点开始的臼顶向下的导航，所以d a t a o u i d e 可以用来 执行自顶向下的查询计划并与辅助内容索引结合使用。 d a t a g u d e 本身只支持简单路径( 从根节点到叶结点的不包含通配符的路径) 的导航，不支持相对路径以及一般正则路径的导航。 3 节点标识 d a t a g u i d e 没有要求采用特殊的节点标识方案，因此可与其它特殊节点标识 方案兼容，艽莫当节点投有父指针对，b 果要向上导航鸽话。祷会十分困难，部 果结合我们 i 面讨论的x i s s 采用的扩展前序编码，就可以通过计算来确定节点 之间的祖先子孙关系。 4 索引更新 d a t a g u 】d e 的索引更撕与其索引构建很相似。当数据库插入元素或文档时 d a t a g u i d e 只需在相对应的部分插入索引节点，所以d a t a g u i d e 索引更新是增量 的。但是，索引结构中每个单独的文档节点可能在多个点被引用索引更新时多 条路径需要被检查，可能导致磁盘i o 访闻开销钓掘大。 f 叭i j 论文x , i l 数蛞存储管理系统 5 索引存储 如前面所蜕，为了保证结构导航过程中不出觋错误的匹配结果d a t a g u l d e 必须是s t r o n gd a t a g uj d e ，这样就需要在d a t a g u i d e 构建过程中对些节点进 行复制。当数据库图为有环且深度较深的图时，索引的大小将会呈指数增长，从 而消耗大量的存储空间。下图1 3 21 展示了有环时索引的增长。 图1 3 2 i 有环时d a t a g u i d e 增长 b 尽管文献 2 3 的实验结果表明，在大多数情况下纽对于车砖结构、无环雷、 扇出较大深度较浅的有环图，索引的增长不是很明显。但是，我们可以看出该索 引对数据库结构的依赖性大，而且导致索引复杂性的原因目前尚不清楚。 i n d e xf a b r i e i n d e xf a b r i c 1 5 1 6 1 7 是种基于平衡化的分层p a t r i c i at r i e s 3 的 对数据库的路径和内容同时进行索引的索引结构，【n 幽xf a b r i c 不依赖于数据 存储模型，因此适用于多种数据模型，如关系数据模型、面向对象数据模型。对 于半结构化数据，i n d e xf a b r i c 与前面提到的d a t a g u i d e 很相似。 i n d e xf a b r i c 索引的主要数据结构p a t r i c i at r l e s 是神在信息检索领域 普遍使用的以字符串为索引键的压缩索8 树，它将路径信息编码于字符串型的索 引键中，并且p a t r i c i at r i e s 只对路径的不同部分进行索引，而把相同的部分 略去，从而实现对路径的压缩。其中的路径的包括两种：一种叫r a wp a t h ，是 从原始x m l 数据层息中提取出来的路径信息( 从根节点到叶节点) ：另种叫 r e f i n e dp a t h 是为了优化特定的复杂查询预连结的一些路径( 如从节点到兄弟 f ：i ：i s 义x m l 数据存储管理系统 节点的路径) 。在此基础上，i n d e xf a b r i c 对p a t r i c i at r i e s 进行分层平衡优 化以提高查找平均效率。 它先将p a t r i c i at r i 8 s 分成大小近似相等的块，每个块都包含一棵浚树的 子树。然后分别对每一个块进行索引形成新的一层索引，当该层索引大小超过块 大小时，也对其进行分块，再新建一层对该层进行索引，以此类推。查询时首先 对最上一层索弓 进行查找，每层查找一个块，由于块的大小和磁盘块大小近似， 所以查找一个块，只需要一次磁盘i o 。然后逐层往下查找，直到最后一层，即 最开始的一层。所以每次查询所需的磁盘访问i o 数与索引层数相同。如果每层 的扇出较大的话，那么层数就会相对较少，则磁盘访问的次数也较少，而且与查 找键的长度无关，从而整个索引结构是平衡的，具有较高的效率。图1 3 2 2 展 示了该索引结构。 图1 3 2 2i n d e xf a b r i c 索g 1 数据表示 i n d e xf a b r i c 对数据存储没有特定的要求，它可以适用于关系数据库，对 象数据库以及半结构化数据库的。i n d e xf a b r i c 采用了一种高效的分页策略以 及平衡策略，使查询过程中的磁盘访问次数最小，并且对于长的复杂的查找键的 匹配不敏感。同时对索引信息进行压缩，使索引数据量减小。i n d e xf a b r i c 适 用于树结构或有向无环图结构的数据库，对有环图结构数据库不适用，且它只对 单一数据库图( 所有文档在同一数据库图中存储) 适用。i n d e xf a b r i c 同时对 元素标记和元素内容进行索引，索引不需要辅助的内容索引。 2 导航性 和大多数结构导航索引样，i n d e xf a b r i c 也是自顶向下的导航索引。由 坝f 。论文x m l 数摧存储管理系统 于i n d e xf a b r i c 不需要辅助索引，所以查询只需要单一的索引导航。在范围查 询或树查询过程可能会有回溯操 乍，所以。i n d e xf a b r i c 要支持向上的导肮。 3 节点标识 i n d e xf a b r i c 本身并没有要求特殊的编码，所以可以利用其它的节点标识 方案来提高某些性能，如前面提到的扩展前序编码。 4 索引更新 i n d e xf a b r i c 在最坏晴况下，插入节点时，可能导致块分裂操作，丽且同 一水平层次上所有相关块都要更新。同理在删除节点时，可能导致块的合并操作。 但在一般情况下，只要不引入特殊的节点标识方案，索引的更新是增量的。 5 索引存储 i n d e xf a b r i c 由于对路径信息的存储采用了压缩的方法，所以其深度较浅， 空间消耗相对较少，并且长路径的插入对索引的大小和性能都没有显著的影m i n d e xf a b r i c 在概念上与d a t a g u i d e 很相似，郝是确定的导航索引，对数 据库中的所有简单路径只描述一次。在最坏的情况下，也会出现类似于d a t a g m d e 的存储消耗星指数增长的风险。 索引方案比较表 下表1 3 2 1 是以上几种典型索引方案的对照表。 类别数据表示导节点编索引更新索引 d bi n d e x航码 存储 性 x i s s e l e m e n t a r yg r a p h t a n en o s p e c i f i c s t o a t j c i sp a t hl o o k u pt r e et a b l en o g e n e r a ii n c r e m e n t a ls m a l l d a t a g u i d e n a v i g a t i o n a lg r a p h g r a p h y e sg e n e r a l i n c r e m e n t a l l a r g e 【n d e x f a b r i c n a v i g a t i o n a l n e et t e ey e s g e n e r a li n c r e m e n t a l l a r g e 表1 3 2 1 索引方案对照表 坝f j 论史 1 4 本文实现方法提出 x m l 数据存储管理系统 数据库系统的实现通常可以分为三部分 1 2 ：存储管理、查询处理以及事 务管理。本文只对前两部分加以论述，事务管理部分是我们今后的研究重点。 根据以上关于x m l 存储与索引的概述，我们可以看出x m l 数据存储、数据查 询、数据更新之间存在一定的矛盾。比如要提高x m l 数据的查询性能，通常要为 其建立相应的索引，索引本身是要占用存储空间的。而且，查询效率越高，通常 索引也越复杂，索引构建、更新也越困难。此外，为了建立索引，往往数据存储 时要存储一些辅助信息，占用一定空间，而且如果引入特殊节点标识会使数据更 新更困难。所以，为了使x m l 存储管理系统获得较好的综合性能，必须从这几方 面综合考虑。必要时采取一定的平衡折衷策略。 本文的研究重点放在数据存储与索引，实现方法主要从数据存储、数据查询、 数据更新三方面综合考虑来实现对x m l 数据的存储管理，并设计一套索引机制来 满足x m l 数据查询的要求。 1 4 1 存储方案 在前面1 2 节中我们提到了四种) ( 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 8 对x m l 存储的五种策略进行了分析和性能比较。这五种策略分别 是：基于边表的方法、基于存储管理器的对象方法、基于b 树的方法、基于文件 蛳l 论文x m l 数维存储管堙系统 系统对象的方法、基于a s ci i 文件的方法。按照我们的理解，前四种方法是基于 模型的存储它们把x m l 文档看成有向图。基于边表的方法把有向图存储在关系 数掘库的关系表中，基于存储管理器的对象方法把有向图以对象的方式存储在存 储管理器中，基于b 树的方法把有向图存储在b 树中，基于文件系统对象的方法 把有向图以对象的方式存储在文件系统中。而基于a s c i i 文件的方法则是基于文 本的存储。实验结果表踞基于存储管理器的对象方洼具有最优的综合性能。基 于b 树的方法的综合性能与基于存储管理器的对象方法接近，且其数据更新性能 比基于存储管理器的对象方法好，且容易实现。所以，我们的存储方法采用基于 b 树的方法其底层采用对象存储管理器来进行存储管理。 1 4 2 索引方案 在前面1 3 节中，我们对当前一些素弓l 方法送行了分类，并对些典型懿索 引方法进行了分析。 基本索引结构简单，占用空间小，一般都可以主存驻留。但它没有保存x m l 数据的结构信息，不能数据导航，因此不能直接支持结构化查询。要实现结构化 查询，通常需要几种基本索弓j 结合使用将各索引查询结果进行连接，从而使效 率降低。 路径查找索引结构也相对简单，它将节点的路径上下文信息保存在映射表 中，但信息有一定的冗余。并且当对路径信息用节点实甥! 信息( 如节点如或箕 在兄弟节点中的下标) 进行标注时，信息的冗余量将会更大。 结构导航索引通常是树结构或有向图，它保存了整个数据库的结构纲要信 息，包括所有的路径，支持路径导航，因此可以直接支持路径表达式的结构化查 询。但是，结构导航索引通常是对简单路径( t o o l t d l e a f ) 进行编码的，例如 d a t a g u i d e 、i n d e xf a b r i c 。i n d e xf s b r i c 与d a t a o u i d e 相比，i n d e xf a b r i c 是单一的索引结构，而d a t a g u i d e 还需要辅助索引的支持。对于一般的j 下则表达 式( 比如相对路径) 的查询。d a t 弱u l 北和i n d e xf a b r i c 都需要套邈 l 擎在索 引结构中反复导航，以匹配目标节点，从而使效率大大降低。 根据以上各种索引的优缺点的综合考虑，我们提出了一种新的索引方案。我 们的索引结构包括两个索引：主索引和辅助索引。主索引吸收借鉴了i n d e x f a b r i c 的分层平镛舔思想，两时在其基础上进行一定的改进，比查口我们的主索 引只对内容信息进行压缩，对结构信息不进行压缩，从而减少误壹的概率；对内 部节点进行桥注，使对于一般的正则路径表达式查询更适用。此夕卜，我们设计7 个适于主存驻留的辅助索引。我们称之为模式路径哈黎衰，该索5 l 为路径查找 索引，但只对x m l 数据的结构模式迸i 亍索引，而不牵涉具体得x m l 数据，从而便 坝i 论义x m l