（计算机应用技术专业论文）插入友好的xml索引编码技术研究.pdf

摘要 摘要 随着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 编码索引方案面对 的主要任务做了阐述。归结出已有的编码方案之所以对x m l 数据插入不友好 的原因，并在分析了数据模型的情况下提出了一种结合了局部编码思想和全局 编码思想的编码方案。同时为提高编码在进行各种操作时的效率，在数据结构 的设计上参考借鉴了段式内存管理中的内存地址的编码思想。从而对解决x m l 索引编码的x m l 数据写操作提供了一种较新颖的解决思路。 关键字：数据管理；x m l ；编码索引；插入操作 北京l 。、i k 人：乏p ：0 硕十。：之何沦文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，x m lh a sb e c o m et h es t a n d a r d so f e x c h a n g i n gd a t ao nw 曲，ag r o w i n gn u m b e ro fi n f o r m a t i o n - p r o c e s s i n gs y s t e m e su s e s t h ex m ld o c u m e n ta sav e c t o ro fi n f o r m a t i o ns t o r a g e ，e x c h a n g ea n dd i s s e m i n a t i o n ， a n d h o wt om a n a g et h e s em a s so fx m ld a t ah a sb e c o m eam a t t e ro fu r g e n c y a sa m a t t e ro ff a c t i n d e x i n gt h e s em a s s i v ed a t ai sa ni n e v i t a b l ec h o i c e ad i r e c tw a yt o i n d e xt h e s ei st oa s s i g nac o d ef o re a c hn o d ei nt h ed o c u m e n tt r e e n o wt h e r ea r e m a n yx m le n c o d i n gs o l u t i o n s b u tt h e s es o l u t i o n sh a v es o m ep r o b l e m sw i t hh a n d l i n g d a t ai n s e r t i o n t h i sa r t i d ei sa i m e dt os o l v et h e s ep r o b l e m s b a s e do nt h er e s e a r c ho fs o l u t i o n s a l r e a d yh a v ec o m b i n e dw i t ht h em a i nt a s kx m lc o d i n gs o l u t i o n sn e e dt os o l v e t h i s a r t i c l eg i v e sa ni n s e r tf r i e n dc o d i n gs o l u t i o n f i r s t l y , t h i sa r t i c l em a k e sac o n c l u s i o n o ft h es o l u t i o n sa l r e a d yh a v e ，a n d a n a l y z e st h em a i nt a s ko fc o d i n gp l a nn e e dt of a c e t h e nd e s c r i b e st h ed a t am o d u l e u s e di nt h i sa r t i c l e t h et h i r dp a r to ft h i sa r t i c l eg i v e st h ec o d i n gs o l u t i o n t h em a i n p o i n to ft h i ss o l u t i o ni st oc o m b i n et h el o c a lw a ya n dg l o b ew a yo fc o d i n g a n dt h e d e s i g no fd a t as t r u c t u r ei ss i m i l a rt ot h em e m o r ym a n a g e m e n to ft h eo p e r a t i n g s y s t e m s b a s e do nt h e s em e t h o d s ，t h i sa r t i c l eg i v e san e wt h i n k i n gw a yo fs o l v i n gt h e p r o b l e m so fx m ld a t ai n s e r t i o n k e y w o r d s ：d a t am a n a g e m e n t ；x m l ；c o d i n g ；i n s e r t i o no p e r a t i o n i l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 一 签名：攀k 日期盥 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 画之2 叁导师签名： 鲞：置日期：星q q 鱼生墨旦 l 第1 幸绪论 1 1 研究背景 第1 章绪论 网络技术的飞速发展改变了人们的学习、生活和工作方式，拓宽了人们获 得知识和信息的途径并且也改变了人们的思维方式。x m l 就是这样一种迅速发 展的技术。随着大量x m l 数据的出现，如何有效地存储、管理和查询这些 x m i 数据就成为一个值得研究的重要课题。 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 的缩写。它源于s g m l ，s g m l 是标 准通用标记语言( s t a n d a r dg e n e r i cm a r k u pl a n g u a g e ) ，用于定义怎样描述不同 种类的电子文档数据的结构和内容的一种语言标准。x m l 提供了一种标准来描 述在一篇文档中数据是如何组织和存放的。相对于s g m l ，x m l 更加精炼、简 洁，更易于理解和使用，从而更适合在网络环境下使用。x m l 是一种标识语 言，在这点上，它类似于h t m l ，但x m l 关注的不是数据在浏览器中如何布 局和显示，而是关注于怎样描述数据内容的组织和结构。 x m l 最初主要是为了增强应用程序从w e b 上获得文档的解释和操作能力 而产生的。但是在近些年来随着i n t e m e t 的快速发展，以“云计算”为代表的基 于i n t e m e t 的网络应用越来越普遍，x m l 已经成为w e b 数据表示和交换的事实 上标准。同时鉴于x m l 半结构化及自描述的特点，使得它的应用不仅仅限于 i n t e m e t 领域和数据交换领域，越来越多的平台都开始采用x m l 作为描述信息 对象甚至是数据模型的工具，甚至操作系统等系统级的平台都采用x m l 作为 保存配置信息的载体。而在软件工程和开发领域，x m l 更是无处不在，在一些 用于开发和部署的平台中起到了核心作用。然而，从数据库的角度来看x m i 从 另一个方面提出了一个令人兴奋的可能性t 查询这些文档的内容。 证是由于广泛的应用，x m l 数据的数量正在呈指数级增长，如何高效、系 统、科学的管理这些g b 、t b 、乃至p b 级的x m l 文档已经成为数据库研究领 域中的一个重要挑战。正式源于这种数据管理的需求，x m l 数据库成为现在数 据库研究领域的一个热点。 对x m l 数据库系统的研究主要有两种途径：一是纯( n a t i v e ) x m i 数据库系 统，它是为x m l 数据量身定做的数据库。它的优点是充分考虑到x m l 数据的 特点，以一种自然的方式来处理x m l 数据，能够从各个方面较好地支持x m l ，i l 京i i 、l k 人学l ：学硕 学化论文 的存储和查询但是，纯x m l 数据库要走向成熟还有很长的路。二是x m l 使能 ( x m l e n a b l e d ) 数据库系统，它足在已有的关系数据库系统或面向对象数据库系 统的基础上扩充相应的功能，使其能够胜任x m l 数据的处理。目前，x m l 使 能数据库的研究主要是基于关系数据库的。这种方法的优点是町以充分利用已 有的非常成熟的关系数据库技术，集成现有的大量存储在关系数据库中的商用 数据。 1 2 研究现状 目前，x m l 数据库技术是数据库领域的研究热点，近年来国际重要的数据 库学术会议都收录了大量关于x m l 数据库方而的论文，仅以2 0 0 8 年的v l d b 为例，在所有被录用论文中，涉及x m l 数据库的论文就超过l o 篇，超过了录 用数量的1 0 。而在产品方面，主流的商用关系数据库基本上都加入了对x m l 数据类型的支持，在纯x m l 数据库方面，大部分的产品仍然处于实验原型阶 段，其中比较受关注的是密歇根大学安阿伯分校的t i m b e r 、西雅图华盛顿大 学的t u k w i l a 2 】和威斯康星大学麦迪逊分校的n i a g a r a 3 一。在国内方面，这方 面的论文也是三大学报中常客。而在数据库原型方面也有万常选等人提出的x - r e s t o r e 数据库等。 对x m i 数据库系统的研究主要集中在6 个方面：一是对x m l 的查询数据 模型、查询语言和查询代数等进行研究；二是对x m i 数据的编码方案和索引结 构进行研究；三是对纯x m l 数据库系统进行研究，包括存储结构、索引技 术、查询技术和事务管理等；四是对基于关系的x m i 使能数据库进行研究，包 括x m l 数据的关系存储模式、x m l 查询技术和查询算法、x m l 文档发布关 系数据的技术，以及通过中间件实现以x m l 格式和x m i 查询语言查询关系数 据并进行异构数据源的信息集成等；五是对x m i 的查询技术、查询算法， x m l 查询的包含与等价、树模式查询最小化，以及查询优化技术等进行研究； 六是对x m l 查询测试数据集、测试查询范例进行研究。 同关系型数据管理系统及其他的数据管理系统一样，x m l 数据管理的最终 目标是如何高效的完成对x m l 数据的检索、删除和插入。上述各研究方向的 最终目的也基本都是为了解决上述问题。在高级语言方面，为解决高效的数据 检索，w 3 c 工作组开发了x p a t h 5 】和x q u e 6 】查询语言，其共同特征是通过路 径表达式来实现x m l 文档查询。 这些查询处理语言仍然处于一个较高的层次，为提高x m l 数据管理的效 率，在较低层次对x m l 数据建立高效的索引是必要的。建立起来的索引应当 能避免使查询扫描整个文档，同时还应能够快速计算出x m l 文档中任意两个 2 第1 章绪论 节点之间的关系。如何对x m l 数据建立索引影响着x m l 数据库研究的方方面 面，可以说是x m l 数据库技术的基础。而对x m l 数据建立索引的一个重要问 题如何确定文档树中的每个节点，解决这个问题的一个重要思路是对节点进行 编码。因此，可以说x m l 编码技术是整个x m l 数据管理技术的基石。 根据文献【7 】，x m l 索引技术主要可以分为两类： ( 1 ) 面向x m l 有向树的节点记录类索引 节点记录类索引的本质就是将x m l 有向树( 简称有向树) 分解为节点的 记录集合，同时在记录中保存该节点在x m l 树中的位置信息( 如节点编码、 节点所在路径的信息) ；记录通常集中存储在关系数据库中，这样查询时就能 快速获取节点的位置信息，并通过简单运算迅速判断出节点之间的结构关系， 目前获取位置信息的方法主要有2 种：一是节点编码法，二是节点路径法。根 据位置信息表现形式的不同，节点记录类索引可分为3 类：基于节点编码的索 引、基于节点路径信息的索引和二者相结合的混合索引。 ( 2 ) 面向x m l 有向图的节点记录类索引 与有向树相比，有向图的结构要复杂得多，其中包含大量的引用边、交叉路 径和环路，而且同一节点可能出现在多条路径中。为了快速确定图结构x m l 文档中任意两个节点之间的结构关系，研究人员提出了结构摘要索引方法。该 方法已成为目前最为重要的图结构x m l 索引方法。该方法的描述已超出本文 的论述范围，在本文中将不对该方法进行描述。 但是无论采用何种方法，在建立索引的时候都必须要解决对x m l 文档树 编码的问题。目前，针对x m l 数据的编码已有多种方案。这些方案根据记录 信息的不同可以分为基于节点编码的方式、基于路径的编码方式和两者的混合 模式三种模式【8 】或者是全局方法、局部方法和d e w e y 方法三种方法【9 1 ，他们的 区别将在后边详细介绍。 这些编码方案对处理x m l 查询时的效率都是比较高的，然而在处理x m l 的“写操作”时需要重新建立索引或者重新编码，这在文档的量级比较大时或 者“写操作 比较频繁时，会导致整个效率的低下。 产生问题的主要原因在于进行“写操作”时会导致整个文档结构发生变 化。已有的编码方案在编码时编码的主码( 唯一标识某个节点的编码) 要么是 包含路径的完整信息，如位向量编码、前缀编码等编码方案；要么体现了节点 在文档树中的绝对位置，如区间编码。这样，在处理插入或删除时由于文档结 构发生了变化，因此节点的绝对位置发生了变化，因此，必须要对节点的编码 进行部分或全部重新编码。并且，当插入或删除的节点离根节点越高的话，重 现编码的节点数量越多。对于另外的一些方案，如区间编码，虽然有些扩展方 案部分支持插入操作，但当插入的数量超过预留值时仍然需要对整个文档树进 3 北j j ! i 。业人学l 。、乎硕 j 学f 声沦丈 行重新编码。 虽然也有部分方案针对该问题进行了优化，例如c s s u t l 0 1 编码方案，但这 些方案在解决该问题的过程中编码的数据结构采用的足不定长字符串结构，这 样虽然能解决插入的重新编码问题，但增加了编码时问，且在判断节点问的关 系时的效率也较低。 1 3 研究内容 本文的研究内容是插入友好的x m l 编码方案。主要工作包括以下几个方 面： 1 ) 对已有的编码方案进行归纳和总结。该部分是整个论文的基础，在该部 分中，首先对已有的编码方案进行了归纳和总结，且结合x m l 数据写操作出 现的各种情况，对他们可能产生的问题进行了简要的分析；然后总结了在设计 x m l 编码方案时必须考虑的问题。为下一步的工作打下了基础。 2 ) 对x m l 数据模型进行简单的归纳总结。数据模型是任何数据管理系统 都必须研究的基础，也是建立索引和设计编码方案的重要基础。本文在归纳了 x m l 数据模型的同时，也对本文中使用的数据模型进行了简单描述。 3 ) 提出一种评价插入友好程度的评价标准插入友好因子。对于x m l 编码的插入友好程度目前并没有一个统一的标准。为此，本文提出一种简单的 评价插入效率的方法。考虑到在设计x m l 编码方案时，插入数据导致的重新 编码的节点的数量是一个必须考虑的问题，但不同的x m l 文档树包含的节点 数量是不同的，故单纯使用节点数量作为评判标准并不能准确的反应插入效 率，因此本文中插入友好因子的值为重新编码的节点数量和文档树中的总节点 数量之比。 4 ) 提出一种插入友好的x m l 编码方案。这是本文的核心。在本部分中首 先总结了已有x m l 编码方案在面对数据插入时产生问题的根本原因；然后结 合已有编码方案提出一种插入友好的x m l 编码方案。对编码方案研究工作主 要包括以下几个部分：一是对编码进行了形式化的定义；二是针对编码的形式 化定义设计了数据结构，并讨论了数据结构与x m l 文档之间是如何相互影响 的；三是提出了对核心的编码方案和插入数据的算法。 该部分中的编码的结构设计是本文的核心也是创新之处，本文的编码思想 结合了局部编码、全局编码的思想，而在具体结构设计上又吸收了前缀编码方 式中字符串有序和段式内存管理中的分段思想。 5 ) 最后对本文提出的编码方案进行了实验验证。 4 第1 章绪论 1 4 论文的结构说明 本文共分五章，文章结构及各章的主要内容组织如下： 第1 章阐述x m l 编码的研究背景、现状，然后介绍了本文的研究内容和 组织结构。 第2 章对x m l 数据模型进行了总结，并提出了本文采用x m l 数据模型。 第3 章在对已有的x m l 编码进行总结的基础上，对x m l 编码方法需要解 决的关键问题进行了分析，并提出了一种评价编码插入友好程度的评价标准一 一插入友好因子。 第4 章提出了一种插入友好的x m l 编码方法。针对该方法提出了使用的 数据结构，并详细介绍了编码算法、插入算法。 第5 章则针对第4 章提出的编码方法给予了实验验证，探讨了该方法存在 的不足，并对今后的研究做出展望。 5 第2 幸数据榄唧j 及其选择 第2 章数据模型及其选择 数据模型是x m l 数据管理研究领域的核心问题之一，用来给出x m l 数据 以及数据上操作的精确语义，是x m l 数据的查询处理和优化的基础【1 1 1 。 2 1x m l 数据模型及其特点 目前，在x m l 数据访问方面的数据模型主要包括三类：第一类是面向对 象的半结构化模型，如l o r e 和x m l q l 等，这些模型的共同点是x m l 数据被 表示为有向图。第二类是采用关系数据库的数据模型，在这种数据模型中首先 将x m l 数据保存在关系数据库中，然后利用关系数据库管理系统的现有机制 对x m l 数据进行操控。第三类是采用面向对象数据库的对象模型，一般是将 x m l 数据存储在面向对象数据库中，然后对其进行操控。 2 1 1x m l 文档的结构 x m l 文档一般包含有六个部分组成：x m l 声明、x m l 元素、属性、处理 指令、注释和命名空间。 x m l 声明必须在文档的第一行，并且其中的字母是大小写敏感的。在 x m l 声明中，必须包含x m l 版本号，在版本号之后可以含有编码( 这里的 “编码 含义与本文中所指的“编码 含义不同，为文件的编码，例如 “u t f 8 或“g b 2 3 1 2 ，不特别指出的情况下本文中的“编码 特指“索引 编码 ) 。 x m l 元素组成了x m l 文档的大部分内容。元素有名字，也可以由后裔， 后裔可以是元素、处理指令、注释、字符数据或者字符。一个格式正确的x m l 文档必须至少包含一个元素。 x m l 元素可以用属性加以限制。属性通常用来给元素提供所显示内容的额 外信息。元素的属性在元素的起始标记中给出，形式为：属性名= 属性值。属性 名与元素名有相同的构造规则，属性值必须出现在单引号或者双引号中。一个 元素可以有任意数目的属性。 处理指令通常用来处理x m l 文档的应用程序提供信息，这些信息包含如 何处理文档，如何显示文档等。 同计算机编程语言一样，x m l 文档也支持注释。注释可以看成是特殊的元 一7 一 ，i 匕j j ! i 、i k 人。、p ：乏倾p 何沦丈 素。 命名空间是x m l 文档中的一个重要概念。x m l 文档是一个自描述性质的 文档，允许设计者自己选择记名，所以出现重名的可能性很大。为解决这个问 题，x m l 提供了命名空间的方式来解决这个问题。命名空间相当于一个词汇 表，他限定了与之关联的所有元素的作用范围。关于命名空间的详细信息不再 赘述，请参考相关文献。 所有的x m l 文档都必须是结构良好的。结构良好的x m l 文档必须满足以 下条件：所有的构造从语法上都是正确的；只有一个根元素；所有的起始标记 都必须有一个对应的结束标记与之对应；所有的标记都必须正确的嵌套；每个 元素的所有属性都是不同名的。 图2 1 给出了一个结构良好的x m l 文档的例子。 r g b h i n t s l i g h t 图2 i 一个结构良好的x m l 文档 f i g u r e2 1a ne x a m p l eo fw e l l f o r m e dx m l d o c u m e n t 该文档是l i n u x 系统中f o n t c o n f i g 的一个配置文件，用以自定义字体的替换 顺序。 值得注意的是文档中的两个 标签内的两个值是在第二行中的d t d 中定义的。引入d t d 的目的是为了有效的规范不同人所定义的不同x m l 文 档，同样能起到该目的还有x m ls c h e m a ，他们之间的区别在此不予讨论。但 在他们中，数据类型是一个重要的概念。由于d t d 的数据类型描述能力不如 x m ls c h e m a ，且x m ls c h e m a 的应用越来越广泛，在此主要讨论x m ls c h e m a 中的数据类型。 x m ls c h e m a 中的数据类型分为两种。 一种是简单类型，简单类型可进一步分为三种：原子类型、列表类型和联 合类型。原子类型是不可分割的数据类型；列表类型为用空白符分割的原子值 得列表；联合类型的值可以是原子值也可以是列表值，它是多种类型的值空间 r 第2 章数据模型及其选择 的参考。 另外一种是复杂类型。复杂类型的出现源于简单类型不能完全满足实际应 用的需要。复杂数据类型使用户可以自定义想要的任意复杂的数据类型。它可 以包含子元素或属性。它的内容模式( 即包含的) 共有四种：简单内容、纯元 素内容、混合内容和空内容，所有这些内容类型都允许具有属性。 2 1 2 图状模型 从上节对x m l 文档的简单介绍可以看出，x m l 数据的一个重要性质是半 结构化的。o e m 1 2 】模型是定义于斯坦福大学的t s i m m i s 系统中的o e m ( o b j e c te x c h a n g em o d e l ) 是简单的、自描述的和嵌套的对象模型，该系统主要用于 异构数据源的集成。很多类似的系统也使用该模型或该模型的变体，实际上 o e m 己经成为通用的半结构化数据的模型。因此，使用o e m 描述x m l 数据 也是一个合适的选择。 o e m 模型可以定义如下【1 3 - 1 5 】： 定义2 1一个o e m 对象是一个四元组 。其 中，l a b e l 是一个变长字符串，用以描述对象的意义；t y p e 表示对象值的类型， 包括原子类型和复杂类型；v a l u e 表示对象的值；o l d 用以表示o e m 对象的唯 一标识( “a ”表示空) 。 o e m 模型中，每个对象允许由多个父对象，因此在有向图中，允许环的存 在。 使用o e m 模型描述x m l 数据时，存在一个重要的结论： 定理2 1 使用o e m 模型描述的结构良好的x m l 文档时，产生的有向图 中不包含环( 该环指的是平凡的环，至少含有两个节点的环) 。 证明：采用反证法。 某x m l 文档d ，采用o e m 描述该文档生成的有向图为g 。假设g 中存在环 c = e 1 ，e 2 ，e 3 e n ，c 1 ) ( 佗 1 ) ，其中e i ( 1 i 佗) 是g 中的节点，c i 对应在f 】! 中的 元素为e ( e 1 ) 。由于构成环，因此c 中的节点必然满足以下两个条件中的任意一 个： 1 ) 存在2 个或2 个以上的e 3 ( j i ) ，使得e j 是c i 的直接前驱。 2 ) v e c ，e 是e i + l 的直接前驱，且e n 是e 1 的直接前驱 若满足条件1 ) ，则e i 存在两个以上的节点，这说明在d 中，存在一个元 素，其存在两个以上的上级元素，根据2 1 1 对x m l 文档的描述，该x m l 文 档必然不是一个结构良好的x m l 文档，因此，此时不满足结构良好的条件。 若满足条件2 ) ，则说明e i 在d 中对应的元素e ( e ) 即是自己的上级元素，又 9 北京i 、i p 人硕十何论文 是自己的下级元素，显然，这在一个结构良好的x m l 文档中足不町能出现 的。 综上所述，假设不成立。证毕。 2 1 3 面向对象模型 x m l 文档的最大特点是“半结构化”和“自描述”，同时，x m l 文档中 的数据类型定义也十分复杂。而这些特性和面向对象的描述方法有些相似之 处，因此，采用面向对象的模型来描述x m l 也是一个较好的选择。 o d m g ( o b j e c td a t a b a s em a n a g e m e n tg r o u p ) 1 6 】的对象模型是一个基于类 型的系统，所有的对象都是某种类型的实例。o d m g 对象模型主要包括对象 ( o b j e c t ) 、文字( l i t e r a l ) 、类型( t y p e ) 、特征( p r o p e r t y ) 、属性 ( a t t r i b u t e ) 、关系( r e l a t i o n s h i p ) 和操作( o p e r a t e ) 等概念。对象和文字是 数据模型的基本原语，都有一个类型；对象的状态通过一组特征来表示，属性 和关系是特征的两个种类；操作反映的是对象的行为。 o d m g 的模型的模式描述可以用对象定义语言o d l ( o b j e c td e f i n i t i o n l a n g u a g e ) 来描述。且，用o d m g 来描述半结构化的数据也是十分方便的，例 如将图2 - 1 所示的x m l 文档转化成一个基于o d m g 的模型x d u c e 1 7 ，1 8 1 来描述 则如图2 2 所示： f o n t c o n f i g m a t c h q t a r g e t ”f o n t ” ， e d i t n a m e i i r g b a ” ， c o n s t ”r g b ” ， e d i t n a m e ”h i n t s t y l e 】， c o n s t ”h i n t s l i g h t ” 】 图2 - 2 一个用o d m g 描述的x m l 文档实例 f i g u r e2 - 2a ne x a m p l eo fd e s c r i b i n gx m l d o c u m e n tu s i n go d m g 在本例中，采用o d l 对模型的定义没有给出，而是直接给出了最后的结 果，关于o d l 的定义，可参阅文献 1 6 。 1 0 。 第2 章数据模型及其选抒 2 1 4 标签有向树模型 在实际进行x m l 查询处理时还出现了另外一种描述x m l 数据的形式，即 x m l 标签有向图模型【1 9 】。该种模型中最重要的模型就是d o m 模型。 x m l 文件由嵌套的带标记的元素组成。每一个标记元素又可以拥有零个或 多个属性值对( a t t r i b u t e v a l u e ) 以及零个或多个子元素( s u be l e m e n t ) 。每 个子元素本身也是标记元素或“不带”标记的文本( p c d a l 队) 。由于x m l 被定 义为一种标记语言而不是数据模型，因此x m l 是一种有序的数据文件。结构 良好的( w - e 1 1 f o r m e d ) x m l 文件不对其中的标记、属性名以及嵌套模式作任 何限制，如果它符合一定的文档类型定义( d t d ) 则被称为是合法的x m l 文 档2 0 1 。为了有效使用x m l 数据，w 3 c 组织为x m l 数据定义了文档对象模型 d o m ( d o c u m e n to b j e c tm o d e l ) 2 1 】，用于将x m l 数据映射到一定的数据结构 中。d o m 模型完整的定义了访问和操作x m l 文档的标准，d o m 在一个x m l 文档中是以一颗树的形式存在的，其中包含了元素、属性以及节点形式定义的 文本。 本文将对d o m 模型的一些基本的思想进行描述，而对其中设计x m l 文档 操作的部分将不予讨论。 ( 1 ) d o m 节点 根据d o m 的定义，x m l 文档中的每个成分都是一个节点，它是这样定义 的： 整个文档是一个文档节点。 每个x m l 标签是一个元素节点。 包含在x m l 元素中的文本是文本节点。 每一个x m l 属性是一个属性节点。 注释属于注释节点。 例如图2 1 所示的x m l 文档，在该文档中， 是根节点。文档 中所有其他的节点包含在 节点之内。根节点有一个 子节 点。该子节点包含两个 子节点。 在d o m 节点中需要注意的一个问题是文本是单独存储在文本节点中的， 例女1 r g b 标签中的文本“r g b ”，一个的错误认识是认为该本文是存 在于 节点中的，实际上，该本文是存在于一个单独的文本节点中的。 ( 2 ) d o m 节点树 x m ld o m 把x m ld o m 文档视为一棵节点树( n o d e t r e e ) 。树中的所有节 点彼此之间都有关系。可通过这棵树访问所有节点。可以修改或删除它们的内 容，也可以创建新的元素。这颗节点树展示了节点的集合，以及它们之间的联 1 1 北i ! 州k 人硕十。伊论艾 系。这棵树从根节点开始，然后在树的最低层级向文本市点长出枝条，图2 1 所示的文档用d o m 节点树表示可以如图2 3 所示 图2 3d o m 。1 了点树不意图 f i g u r e2 - 3t h ed o mn o d et r e eo ff i g u r e2 - 1 d o m 节点树中的节点彼此之间都有等级关系。父、子和同级节点用于描述 这种关系。父节点拥有子节点，位于相同层级上的子节点称为同级节点( 兄弟 或姐妹) 。 在节点树中，顶端的节点成为根节点。 根节点之外的每个节点都有一个父节点。 节点可以有任何数量的子节点。 叶子是没有子节点的节点。 同级节点是拥有相同父节点的节点。 从上述描述可以看出，d o m 节点树节点的定义基本上和数据结构中树中的 概念是一致的，只是有一点要特别指出的是同级节点的概念，同级节点和树中 同层的概念不同，要满足同级节点必须要求他们的服节点相同。如图2 1 中的 两个 节点是同级节点，而两个 贝l j 不是同级节点。 d o m 节点树的一个好处是因为是按照树的结构形式组织的，因此可以在不 了解树的确切结构的情况下遍历树。 1 2 第2 章数据模1 q 及其选择 2 2 本文采用的数据模型 由文献【1 1 可以知道，x m l 数据模型除了需要给出数据的定义外，还要对 给出在数据上定义的精确操作。但在研究x m l 编码时，考虑的问题如上所 述，只需要考虑如何可以反映出数据的结构信息即可，而数据的精确操作则不 需要进行考虑。 本文的研究焦点在于x m l 文档的索引编码，对x m l 数据建立索引的过程 只与x m l 文档的结构有关系，因此，本文采用的数据模型不是一个完全意义 上的数据模型，因为它只关心x m l 数据的结构。 根据定理2 1 可知，在用o e m 描述x m l 数据时，生成的有向图中不含有 环。因此，若在x m l 数据中不存在引用关系时( 引用关系的含义为某个节点 的值引用本文档内某个节点的值) ，该生成图实际上是一颗有向树。同时，在 实际应用中，x m l 数据的查询多采用x p a t h 和x q u e r y 等查询语言，对于 x p a t h 和x q u e r y 查询语言，w 3 c 专门为其设计了“x q u e r y1 0 a n dx p a t h2 0 d a t am o d u l e ”( x x d m ) ，同时该模型也是x s l t 2 0 使用的数据模型。因此，该 模型适用性较强。同时，该模型在表达上与d o m 模型类似，两者都是基于节 点的树状模型。两者之间最大的区别在d o m 模型是一个a p i 驱动的模型，而 x x d m 则不是一个a p i 驱动的模型。 因此，本为采用d o m 和x x d m 中节点树或文档树( 为研究方便，称为文 档树) 作为主要研究对象，实际上该模型也是在研究x m l 编码是普遍采用的 一个简单但有效的数据模型。 定义2 2 文档树是一颗树，且该树满足如下条件： 1 ) 树中任意一个内部节点i n _ n o d e ，对应x m l 文档中的一个元素，表示为 e ( i n _ n o d e ) ； 2 ) 树中任意一个外部节点m z t _ n o d e ，对应x m l 文档中的一个属性或文 本，当是一个属性节点时表示为a ( o u t _ n o d e ) ，当是一个文本节点时表示为 t ( o u t _ n o d e ) 。 图2 3 所示的d o m 节点树用定义2 2 所述的文档树表示如图2 4 所示。 该定义的一个主要特点是将d o m 模型和x x d m 模型中的属性节点和文本 节点作为外部节点。这主要是基于以下两点的考虑： 1 ) 在d o m 节点树和x x d m 文档树中所有的属性节点和文本节点都是叶 节点； 2 ) 将属性节点和文本节点作为外部节点可以更好的集中精力处理文档的结 构，同时也可以采用其他更为高效的方式组织这些节点。 1 3 r | 匕j 蠢i ：、l k 人i ，、硕十学何沦丈 2 3 本章小结 ( m a t c h ) 八 、 fe d i t1 、 、r t ： 。- 。 。 。 _ - 。_ - 。_ - _ _ _ - _ _ 。- _ _ _ 一_ _ _ _ - _ _ _ 。_ _ 文本：h i n t s l i g h t i一_j j 。一 n a m e | lt a r g e t 图2 4 文档树模型示意幽 f i g u r e2 - 4t h ed o c u m e n tt r e eo ff i g u r e2 - 1 数据模型是x m l 数据管理研究领域的核心问题之一。本章对比较常用的 数据模型进行了数据模型进行了归纳总结。最后归纳出了一个精简的可以体现 x m l 文档结构的数据模型作为以后章节的基础。 1 4 t 一 址 ， 一丁扣、一习 、 三 第3 章x m l 编码技术及问题分析 第3 章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 编码方案插入友好程度的评价标准。 3 1 主要x m l 编码技术 3 1 1x 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 文档树的编码方案，与文献【7 】中提及的面向x m l 有向树的节点 记录类索引是一样的，这类编码方案采用的数据模型是树型模型。该类编码方 式可分为三类【8 】：基于节点编码的方式、基于路径的编码方式和两者的混合模 式。 3 1 2 基于节点的编码方式 基于节点的编码方式中，最为常用的是区间编码。区间编码利用x m l 文 档有序的特点，根据每个节点在文档中的位置，对每个节点赋予一个编码。区 间编码可以描述如下，对树t 中的任意节点e 赋予一个区间值 ，并且满足 如下条件：节点e 的任意子孙节点的编码为 ，那么，o d 。 1 5 ，i 匕京l ：、l k 人。学l 。学硕p 乎何论文 b j d 图3 1x m l 文档数两个节点l 剧的关系 f i g u r e3 - 1r e l a t i o n s h i pb e t w e e nn o d e si nx m l d o c u m e n tt r e e 最早的区间编码方案是由p f d i e t z 提出的d i e t z 编码【2 2 1 。它的编码方法简 述如下：假定树t ，则对该树中每个节点e 赋予一对编码 ，其中， p r e 和p o s t 分别代表节点e 在树t 中先序遍历和后序遍历的顺序。可以证明，在树t 中，某节点t 在先序遍历时必然出现在它的子孙节点之前，在后序遍历时必然出 现在它的子孙节点之后。假定节点2 t 的某个子孙节点为v ，那么在d i e t z 编码 中，节点乱的编码c ( “) = 和节点v 的编码c ( v ) = 必然 满足c ( u ) ) c ( v ) u p p r e u p o s t u 。因此，在d i e t z 编码方案中，给 定任意两个节点，他们之间的祖先子孙关系的检测能够在常数关系内被计算出 来。在该方案中，p r e 或p o s t 中的任何一个均可以作为节点的唯一标识。 其他的区间编码方案大多是对d i e t z 编码的推广。常见方案为l i m o o n 编 码【2 3 1 、z h a n g 编码【9 ，2 铊7 1 和w a n 编码。以下对他们的主要思想进行简要描 述。 ( 1 ) l i m o o n 编码【2 3 】 对x m l 文档树t 中的每个节点赋予一对编码 ，其中，o r d e r 为节点的扩充先序遍历序号，它的取值是非连续的，为节点的插入预留序号空 间；s i z e 是节点的子孙范围。因此，在该编码方案中，任意节点u 的编码 必须满足：若v 是仳的子孙节点，u 的编码为 ， 则有o r d e r 牡 o r d e r t ，ao r d e r 口+ s i z e o r d e r 让十s i z e “；若v 是乱的兄弟节点，且 在先序遍历中是“的右兄弟，则有o r d e r + s i z e u o r d e r 口。 可以看到，在该编码方法中，可以很容易的判断树中任意两个节点之间的 兄弟关系和祖先子孙关系。该编码方案对文档修改的支持要好于d i e t z 方案。 一1 6 、乡、 。 、 第3 章x m l 编码技术及问题分析 ( 2 ) z h a n g 编码【9 , 2 4 - 2 7 】 该编码对x m l 文档树中的每个节点赋予一组编码 。他们的 含义为，b e g i n 为在访问该节点的所有子孙节点之前产生一个序号，e n d 是在访 问完所有的子孙节点之后对再次访问该节点并对该节点赋予的序号。因此，对 于某x m l 文档树t 中的任意两个节点和钉。如果让是t ，的祖先节点，那么有 b e g i n u b e g i n ae n d v e n d u ，另外，树中的每个节点都在被另外赋予一个值 l e v e l ，标识该节点在文档树中所处的层数。显然，该编码中，b e g