（计算机软件与理论专业论文）原生数据库动态编码方案探讨.pdf

a b s t r a c t ab s t r a c t wi t h t h e r a p i d d e v e l o p m e n t o f n e tw o r k t e c h n o l o g i e s a n d n e t w o r k s e r v i c e s in r e c e n t y e a r s , x ml ( e x t e n s i b l e m a r k u p l a n g u a g e ) h a s b e e n in c r e a s i n g l y a n d p o p u l a r l y u s e d i n s o c i e t y , a n d m a k e i t s e lf a s ta n d a r d f o r d a t a e x c h a n g e a n d d a t a d e s c r i p t i o n o f c r o s s - p l a t f o r m a n d c r o s s - la n g u a g e . t h e e m e r g e n c e o f l a r g e a m o u n t o f x m l d a t a p o s e s a n e w c h a l l e n g e t o d a t a b a s e f o r s t o r i n g a n d q u e ry i n g x m l d a t a . a n d n a t i v e x m l d a t a b a s e r i s e s i n r e s p o n s e t o t h e p r o p e r t i m e a n d c o n d it i o n s . s t o r a g e a n d q u e r y i n g i s t h e p r i m a ry f u n c t i o n o f n a t i v e x ml d a ta b a s e , a n d t h e y p l a y a k e y r o l e i n t h e in t e g r a l p e r f o r m a n c e o f t h e d a ta b a s e . s o t h e s t u d y o f n u m b e r i n g s c h e m e o f n a t i v e x m l d a t a b a s e i s v e ry i m p o r ta n t , a n d s t o r a g e n u m b e r i n g s c h e m e t o o . o n t h e b a s is o f a n a l y z i n g n a t i v e x ml d a t a b a s e re s e a r c h i n g r e s u l t s b o t h a t h o m e a n d a b ro a d , t h i s p a p e r m a k e s a d e e p re s e a r c h o n t h e n u m b e r i n g s c h e m e o f n a t i v e x ml d a ta b a s e a n d p u t s f o r w a r d a n e w n u m b e r in g s c h e m e , w h i c h i s n a m e d a s d o n . b e s i d e s t h e c h a r a c t e r i s t i c s o f p re fi x a n d d y n a m i c s , d o n a l s o p o s s e s s e s t h e v i r tu e s o f o r d e r a n d r e c o n s tr u c t i o n , w h i c h e ff e c t i v e l y s u p p o rt x ml s t r u c t u r e q u e r y i n g o f v a r i o u s e x t e n s i o n s . a ft e r a n a l y z i n g s t o r a g e e n c o d i n g re s e a r c h i n g re s u l t s , t h i s p a p e r s u g g e s t a s t o r a g e e n c o d i n g s c h e m e f o r d o n , m a k d i n g a c o m p a r i s o n w it h t h e o t h e r o n s t o r a g e p e r f o r m a n c e o b j e c t i v e l y . f i n a l l y , t h e t h e s i s r o u g h l y d i s c u s s e s d o n q u e r y i n g s c h e m e a n d n o d e r e c o n s t r u c t i o n a l g o r it h m s , a n a l y z i n g a n d c o m p a ri n g t h e p e r f o r m a n c e v i s i t i n g d i s k 1 / o o f d o n w i t h p re f i x n u m b e r i n g s c h e m e w h i le e x t e n s i b l y q u e ry i n g x ml d a t a . k e y w o r d s : n a t i v e x ml d a t a b a s e , n u m b e ri n g s h c e m e , n o d e r e c o n s tr u c t i o n , e x t e n s i b l e q u e ry i n g 1 1 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、保存、使用学位论文的规定，同意如下 各项内容:按照学校要求提交学位论文的印 刷本和电子版本;学校有权保存学 位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存 论 文;学校有权提供目 录检索以 及提供本学位论文全文或者部分的阅览服务; 学 校有权按有关规定向国家有关部门或者机构送交论文的复印件和电 子版;在 不以 赢利为目 的的前提下，学校可以 适当复制论文的部分或全部内容用于学术 活动。 学位论文作者签名: 年s月 材日 四 经指导教师 同意，本学位论文属于保密，在 年解密后适用本授权书。 指导教师签名:学位论文作者签名: 解密时间: 年月日 各密级的最长保密年限及书写格式规定如下: 内部5 年 ( 最 民 5年，可少于5 年) 秘密*1 0年 ( 最长1 0年，可少于 1 0年) 机密2 0年 ( 最长 2 0年，可少于 2 0年) 南开大学学位论文原创性声明 本人郑重声明:所呈交的学位论文，是本人在导师指导下， 进行研究工作 所取得的成果。除文中已经注明引用的内 容外，本学位论文的研究成果不包含 任何他人创作的、己 公开发表或者没有公开发表的作品的内 容。 对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已 在文中以明确方式标明。 本学 位论文原 创性声明的 法律责任由本人承担。 学位论文作者签名 第一章绪论 第一章绪论 第一节课题研究背景 i n t e r n e t 发展初期， h t m l扮演了相当重要的角色，为i n t e rn e t 的蓬勃发展 发挥了 突出的作用。随着网 络信息的不断扩充膨胀，使得h t m l无法满足海量 结构化和半结构化数据更复杂、 更大规模的需求。 1 9 %年， 全球信息网协会( wo r d w i d e w e b c o n s o r ti u m , w 3 c ) 开始制定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 ， 可扩 展 标记 语言) 1 ) ， 希望它 能 具备比h t m l 更严谨的 架构， 同时 又比s g m l ( s t a n d m r d g e n e r a li z e d m a r k u p l a n g u a g e ) 更 容易 使 用。 在 这 种背 景 下， 新的 标 准 标 记语言 x m l应用而生。 x ml 是一种自 描述的、 半结构化、 可扩展的标记语言。 它是一套无限延伸、 用来设计各式各样标注语言的准则，是一种自 我描述的语言。目前它已经成为 i n t e rn e t 上数据交换和数据描述的事实标准， 使基于w e b 服务的互操作性变得简 单可行; 将语义内容和外观显示相分离使得x m l更专注于数据的语义信息; 基 于x ml 通用高 效的x m l 解析器和访问 接口 在各个平台 上都易于获取，开发基 于x ml的应用变得异常简单:用户自 定义标签和无限嵌套的能力赋予x ml 无 限扩张能力，几乎可以 清晰自 然表达各类数据。 由于x ml的各种优势，使得x ml在各个领域得到广泛的支持和应用。如 电 子 商 务 全 球 化 标 准e b x m l t2 1( e c ) ， 中 国 国 情 的 电 子 政 务 语 言 规 范c n g x m l (3 1 数学领 域的m a t h m l 0 1 等 等比比皆 是。 随 着x m l 和w e b 技术的 广泛应用和发展， s e n m a t i c w e b提出了一种通用框架，使数据能跨企业、地域、平台的得到共享 和重用， 但是这些信息资 源通常以半结构化数据的形式特别是x ml数据的形式 存在.半结构化数据成了人们获取、传播和交换信息的重要途径，整个we b形 成了一个巨大的异构数据环境。 但是将数据表示为x m l只是第一步， 如何对海 量的x ml文档数据进行有效存储和管理，如何实现更快、更精确的x ml查询 等己经成为迫切需要解决的研究课题。 第一章绪论 x ml 数据量随着x m l的广泛应用呈指数级增长， 对这些海量的x ml 数据， 至少可以利用四 种方式来进行存储和管理， 但前两种管理系统并非针对x m l 设 计， 在管理x m l 数据时有一定的局限性。 第一种方式是文件系统， 它不提供事 务索引查询、事务管理、并发控制、 安全恢复机制等技术，无法保证数据的完 整 性 和 一 致 性 ; 第 二 种 方 式 是x m l e n a b l e d ls l数 据 库 ( x e d 玛 ， 在 关 系 或 面 向 对 象数据库基础上扩充相应的功能， 使其能够胜任x ml 数据的处理。 它的局限性 在于对于格式复杂的x m l 数据支持程度较差，而且不支持x ml 标准的查询语 言x p a th 161 , x q u e ry 7) ， 更 新 语 言x u p d a te e 1等 各 种 技 术 。 这 种 方 式 使 得 在 处 理 x m l 数据的时候要经过多级复杂的转换，这必将带来效率的降低:第三种方式 是n a ti v e x m l d a t a b a s e 9 1( 又 名 原 生 数 据 库 ， 文 中 简 称 为n x d ) ， 它 是 应 用 需 要 推动诞生和发展出 来的新技术。它充分考虑到x m l 数据的特点，将x m l 文档 和元素作为 基本结构， 是专门 设计用于存储和管理x m l 文档的数据库， 从各个 方面都很好支持x m l的查询和存储等各项功能。第四种方式是x e d b和n x d 的 混 合方 式h y b ri d x m l d a t a b a s e ( h x d ) ， 即 混 合x m l 数 据 库， 它 将 传 统数 据 库 和n x d结 合 起 来， 典 型 的 例 子 是o z o n e ll o ) e 第二节 n a t i v e x ml数据库的发展 n x d是最 近几年才提出的概念，是一个比 较崭新的发展领域， 主要是为了 解决大量x m l 数据的存储和管理问题。 许多公司和研究机构都纷纷致力于n x d 的研究和发布，目 前就n x d的产品情况来看， 学术界的原型系统和商业产品之 间存在微妙差别，尽管主流技术是一致的。 工业界的n x d产品强调实用，这与学术界原型系统特点不同: ( 1 ) 在底层 提供“ 集合” 的 数据结 构， 以 存储x m l 元素结点， 通过b - 树结 构建立索引。 “ 集合”之上一般还会一级或二级索引，加快了查询处理速度，显 得更加高效使用。 ( 2 ) 引入日 志管理， 建立完善的事务处理机制。 这些事务处理功能包括提交、 回滚和日 志文件， 保证系统出 现问题后的完全恢复。 口 ) 异构数据的 集成管理。 市场n x d拥有集成异构数据源的强大能力， 克 服树型结构数据难以管理的局面。 学术界的原型系统有如下特点: 第一章绪论 ( 1 ) 强调平台 无关性。在n x l 研究早 期， 业界曾争论x m l数据是存储在 关系数据库中， 还是另外在开发存 储)ml的 物理数据库。 这影响了大多数学者 的研究，在设计时必须考虑索引过的x m l数据可以存储在多种数据库结构中。 ( 2 ) 强调存 储与 查询性能的提高. 为提高 查询效率， 学 术界相比工业界更注 意索引结构的设计。 ( 3 ) 强 调研究 n x d 的 模式设计规范 化的 数据理论模型，在如 何优化 x m l 数据库设计、消除数据冗余和一致方面有了一些实质上的进展。 目前市场上大约至少有三十多种不同的 n x d 产品。其中商业数据库包括 t a m in o ,x -h iv e / d b 和e x c e lo n 等 。 另 外 还 有 开 放 源 代 码 的 数 据 库， 包 括a p a c h e 的b e r k e l e y d b x m l , d b x m l , x i n d i c e , c x i ，和o z o n e 等。 还有些是基于关系 数 据库的， 如d b d o m, e y i s t . e x t c , x d b , x p s q l等，还 有些是基于面向 对 象数 据库的， 如b i r d s t e p r d m x m l , o z o n e , s o n i c x m l s e r v e r , x - h i v e / d b 等; 还 有些 基于其他专 用的 存储格式， 比 如d b x m l , x i n d i c e , i p e d o , l o r e , t e r a t e x t d b s等。目 前一些主流数据库厂商已经实现了对 x ml的支持，如 o r a c l e 公司 的o r a c l e 数 据库软 件， i b m公司的d b 2 x m l e x t e n d e r , s y b a s e 公司的a s e ， 微 软公司的s q l s e r v e r 等，他们也开始 将目 光专注n x d数据库。 国外对 n x d的研究比国内早一些，国内目前的研究刚刚开始，目前己有了 一些产品，比如中国人民大学的 i d k e实验室开发的 o r i e n t x，支持了x ml数 据库的存 储、 查询、更 新等操作。国内n x d理论 研究1 1 相对较少。 第三节n a t i v e x m i l 编码方案面临的挑战 在早期，数据库编码被认为一一个颇具有挑战性的研究课题，吸引了众多 研究者。对于编码方案，从是否支持文档更新来说，可以分为两类:静态编码 方案和动态编码方案;从设计思想和编码特点来说可以分为三类:基于区间的 编码p 2 - 1 5 1 、 基于 路径的 编码 1 6 - 2 0 】 和基于数学 计算的 编码2 1 - 2 5 1 。 基于区 间的编 码 方案能快速支持文档结点结构关系判定，通过预留区间来支持动态更新，但随 着结点插入会发生结点重新编码，造成效率低下;基于路径策编码方案，通过 增加字典有序性，既能支持文档结构关系的快速判定，也能很好支持文档的动 态 更新， 但是 对于扩展的次 序敏感性结构查 询的 效率有待提高，编码存储代 价 较大;基于数学计算的编码方案是存储代价小，查询速度快，但也存在上述两 第一章绪论 种方案的类似缺点。 编码方案直 接关 系到x m l 数据库的 存储代价、 查询 速度和更新速度。 继承 现有数据库编码方案的 优点，避开它们的缺点， 这是数据 库编码 方案的研究者 们所面临的难题。 第四节本文主 要研究工作及内 容安排 本 文在国内 外现有的n x d的编码方 案进行了深入的分析 研究， 总结了 这些 编码方案的优缺点，提出了一种功能更强更全的动态编码方案和相应的存储编 码方案， 探讨了在 此基础之上的 扩展结构查 询的1 / 0性能。 主要研究工 作和创新 成果如下: ( 1 ) 对国内 外己 有的 各种经典n x d编码方案进行了 全面总 结和分析，总结 出三种类 型的 编码方案，并比 较了 各自 的 优缺点。 ( 2 ) 提出 一种新的动态有序编码方案 d o n ， 它不仅具备前 缀编码方案的 优 点，而且还具备结点重构的能力。d o n很好地支持了扩展性的结构查询，也提 高了 次序敏感性 结构查询的速 度。 侈 ) 在 分 析 现 有 存储 编 码 技 术 基 础 之 上 ， 提 出 适 合d o n的 存 储 编 码 方 案， 并进行了存储性能的对比。 () 探 讨 了d o n 的 重构 算 法， 举 例 分 析了d o n 和 前 缀 编 码 的 扩 展 性结 构 查 询的u o性能，最后给出了二者的扩展结构性查询的u o性能对比结果。 论文的组织结构和内容安排如下: 第一章主要介绍课题研究背景， 描述n x d发展现状和编码方案所 面临的 挑 战; 第二 章是对n x d编码方案的 一个概述， 分析了国内 外现有的 各类编码 方案， 并总结了它们的各自优缺点.第三章主要内容是根据编码方案的设计要求，提 出新的编码方案 d o n。第四章主要总结了现有存储编码技术，提出适合 d o n 的 存储编码方案， 并对它们进行了 存储 性能 对比。 第五章主要分析d o n和前 缀 编码方 案的 查询处理性能， 并给出 扩展查询时的1 / 0性能对比结果。 最后对全文 进行了总结，并阐述需要进一步研究的问题。 第二章 n a t i v e x m l 数据库编码方案概述 第二章 n a t i v e x ml数据库编码方案概述 第一节n a t i v e x b ii . 数据库概述 2 . 1 . 1 ) c a l绘述 w 3 c的x m l工 作 组 是 这 样 描 述) c iv il的 (2 6 1 : ) c m l是s g m l ( s t a n d a r d g e n e r a liz e d m a r k u p l a n g u a g e ， 标 准 通用 标 记 语言 ) 的 子 集。 它的目 标是 允 许 普 通 的s g m l 在w e b 上以目 前的h t m l ( h y p e rt e x t m a r k u p l a n g u a g e . 超文本标记 语言) 方式被服务、 接受和处理. x m l被设计成易于实现，并且可在s g ml 和 h t m l 之间互相操作气 x m l是一种自 描述、半结构化和可扩展化的标记语言，是一种定义语言的 语言，也就是一种元语言。作为s g m l的一个简化子集，它将s g m l 的丰富功 能和h t m l的易用性结合到一起，具有如下的特性: ( 1 )可扩展性。 x m l 允许使用者创建和使用他们自己的标记， 因此x m l 允许 开发各种不同专业的特定领域的标记语言。 ( 2 )可分离性。 x m l 提供了 一种结构化的 数据表示方式， 实现了数据内 容和 外观形式的真正分离。因此w e b 用户所追求的许多先进功能在x m l 环境下更容 易实现。 ( 3 )自 描述性。 x m l 文档通常包含一个文档类型声明， 它是自 我描述的。 x m l 这种表示数据的方式真正做到了独立于应用系统，并且数据能够重用。 ( 4 )可移植性。由于 x m l是以文本形式描述的， 所以适合各种平台 环境的 数据交换，在一种平台上编写的x m l 文档无须任何更改即可移植到其它平台上。 ( 5 )半结构化。 x m l 文档的结构可以 通过模式来描述， 通过模式验证文档的 有效性会非常容易。 2 . 1 .2 x ml文档结构和类型 x ml文档可以划分为两种类型:以数据为中心的文档和以文档为中心的文 第二章 n a t i v e x 1 4 . 数据库编码方案概述 档。 ( i ) 以 数据为中 心的文档 以数据为中心的文档就是将x m l 用作数据的传输载体， 只提供给机器消费 的文档，如公司销售订单、航班时刻表、科研数据及股市汇率等。这种文档的 特点 是: 结构相当 规 整， 数据粒 度精 细伍 n e - g r a in e d d a t a ) ( 即 最小的 独立数据 单位只存在于p c d a t a元素或属性这一级别) ， 很少或没有混合内容。 除非在对 文档进行验证的时候，同级元素或p c d a t a的出现次序一般来说并不重要。 这 类数据可以 来自 数据库 ( 此时要输入给 x m l ) 或在数据库之外 ( 此时要将其存 入数据库). ( 2 )以 文档为中 心的 文档 以 文档为中心的文档通常是供人消费的。例如书籍、e m a il 、广告以及几乎 所有人工写成的x h t m l 文件. 其特性为结构不太或根本不规则、数据粒度大， 混合内容多。同级元素或p c d a t a出现的次序一般来说总是非常重要的。以文 档为中心的文档通常是以x m l 手工写成， 或从其他格式( 如r t f , p d f , s g m l ) 转换到x m l ，与以 数据为中心的文档不同，它们的来源通常不是数据库。 在现实中以数据为中心和以文档为中心的文档之间的差别不一定很明显。 例 如，一种以 数据为中心的文档比 如发票， 可能含有大粒度的、结构不规则的数 据，比如零件说明:另一种以文档文中心的文件如用户手册，可能包含细粒度 的结构规则的数据 ( 通常为元数据)比如作者和修订日期。 2 . 1 . 3 n a t i v e x i a l数据库的定义 n a t v i e x ml数据库” 这个术语首先在s o f t w a re a g为t a m i n o 所做的营销 宜传中露面。r o n a ld 日 o u r r e t 在 “ x ml a n d d a t a b a s e s 一文中给出了n x d的定 义2 7 j 。一个纯x m l 数据库是指: ( 1 ) 为x m l 文档定义了 一 个 ( 逻辑) 模型， x m l 数据的存储和查询都基于 这个模型.这个的模型至少应该包括元素、属性、p c d a t a等，并保持文档顺 序。如x p a t h 数据模型， x m l i n f o s e t 以 及d o m和s a x 1 .0 的事件所隐含的模 型都是这类数据模型。 ( 2 ) 以x m l 文档 作为逻 辑 存储的 基 本单 位， 就像关系数据 库以 行( 元组 ) 作为 表的逻辑存储基本单位一样。 第二章 n a t i v e x m l 数据库编码方案概述 ( 3 ) 不要求任 何特殊的基本物理存 储模型，它可以建 立在关系层次上或面向 对象的数据 库之上， 或者使 用诸如 索引文 件、 压缩文件此类的专门 存储格式。 从这个至少可以简单地总结一下三点:n x d是专门用来存储 x m l 数据的， 而且完整无缺的存储 x m l 模型的所有成分。不过， n x d 实际所能存储的信息比模 型中定义的要多: n x d的基本存储单位是x m l 文档。基本存储单位就是可以容 纳一份数据的最低级的上下 0文( c o n t e x t ) ，相当于关系数据库中的行:q 3 n x d 可能根本就不是真正的独立的数据库。 n x d 底层的数据存储格式并不重要，正如 关系数据库所用的物理存储格式与数据库是不是关系型之间毫无关系。 2 . 1 . 4 n a t i v e x ml数据库特性 n x d作为专用于存储 x m l文 档的 数据库， 应该具有一般数据库的 特征， 比 如事务 管理、并发控制、查询语言、安 全机制、 二次开 发接口 等。 一般来说， x x d具有 如下几个特性: ( 1 ) 文 档集合 “ 文档集合”的概念比文档更高一层.一般来说，一个 “ 文档集合”关联 一种模式，它把一类文档聚集在一起。将文档加入到有模式的 “ 文档集合”时， 会对要加入的文档进行模式检查，只有符合 “ 文档集合”模式的文档才可以加 入。 集合可以 方便用户操作，这种级别上的查询、 修改操作都会反映到集合内 的 每个文档中。 “ 文档集合” 与“ 文档” 的关系 类似于关系数据库中“ 关系模式” 与“ 关系” 的 关系。 不同于 关系数据库管 理系统中 模式的严格 特性， 纯x m l 数 据库还提供 “ 无模式”的文档集合.即将一个文档放入该集合时，不必验证该 文档的模式。 这 种文档一般用来存放 存储格式很难统一、 半结构化的x m l文 档。 ( 2 ) 查询语言 n x d至少 要支持某种或者几种查 询语言，这些语言可以 是专有的， 也可以 由标准化组织制定的。目前 x p a t h是主流的查询语言，各种产品都提供了或多 或少的 支持， 但 x p a t h作为数据库查 询语言还有不少缺陷，比 如不能分组、排 序、 连接等。作为x p a t h 的替代品， x q u e ry功能要强大的多， 它支持循 环、分 组、排序、连接等，是 w3 c推荐的针对x ml文档的查询语言。 ( 3 ) 更新 语言 大多数n x d对 x ml文档的更新是通过调用其提供的 a p i 完成，或者通过 第二章 n a t i v e x 6 1 l 数据库编码方案概述 简单的替换整个文档来实现。 一些n x d提供专用的更新语言来允许数据更新， 同时 也有不少开放源代码的n x d支持x u p d a t e o ( 4 ) 事务处理和并发控制 几乎所有n x d都支持事务处理和并发控制。目 前n x d产品虽然都提供了 一定程度的支持，但是锁的粒度通常都比 较大，所以多用户并发性的支持相对 较低， 这方面远不像关系数据库那样令人满意。 ( 5 ) 编程接口 良 好的编程接口 是一个数据库系统成熟的重要标志。 一个好的n x d系统应 该提供类似于o d b c或j d b c那样的数据库连接的接口， 还应提供浏览元数据、 执行查询和返回结果的方法。 6 . 往返存取( r o u n d - t r ip p i n g ) n x d一个重要特性是它为x m l 文档提供了“ 往返存取即 功能: 可以 将x m l 文档存放在n x d中，而且能再取回“ 同样的”文档。这种性质对于以“ 文档为 中 心” 的应用程序来说非常重要， 因为易被忽略的c d a t a部分， 实体应用、 注 释和处理指令是这些文档不可缺少的组成部分，特别是对于法律和医学领域中 格式不允许随意篡改的数据文档。 第二节编码方案的引入 提高存储和查询x m l数据的性能是当前研究的一个热点。 x ml查询通常 应包括两种查询: ( 1 ) 值查询: 在元素内 容上的查询， 即 通过限定在元素内 容或属性值上的取 值而进行的选择查询，称为值查询。 ( 2 ) 结构查询: 通过路径表达式， 对文档中 标记的元素之间的结构关系进行 查询，称为结构查询。 x m l 元素有两类基本结构关系。 x m l 文档元素结点之间的基本结构关系包 括: 祖先/ 后代关系( a n c e s t o r / d e s c e n d a n t ) 、 双亲/ 孩子关系( p a r e n t/ c h i l d ) 、之前 / 之 后关 系 ( p re c e d i n g / f o l l o w i n g ) 、 左兄 弟 / 右 兄弟关系( p r e c e d i n g - s ib l i n g / f o l l o w i n g - s i b l i n g ) 等。 前两者称为包含关系， 后两者称为文档位置关系。 查询可以 利用路径表 达式来导航x m l文档树中的任意长度的路径。 但是一个单一路径步的查询， 比 如b o o k / a u t h o r ， 将仅查找b o o k 元素的孩子a u t h o r 元素。因此， 对于多个路径步 第二章 n a t i v e x m 1 . 数据库编码方案概述 的x m l 文档结 构查询， 将导 致 结 构连接1 1 3 1 的 计算。 为了 有效支持x ml 查询， 特别是结构查询，研究者提出了) c a l 数据的各 种索引技术和编码方案。 对于x ml结构查询，一种实现方法是建立x m l文档 树的路径索引， 并通过路径索引来加速x ml 结构查询的计算; 另一种方法是对 x m l 文档树中的结点进行编码， 即 给x m l 文档树中的 每一 个结点 ( 或边) 赋予一 个唯一的编码， 以便能够通过编码直接判断结点之间的结构关系， 而不是对原x m l文档树进行遍历。也就是说，通过编码将x m l 结构查询的计算转化为结构 连接的计算。 第三节 现有编码方案的分类 对于x ml的编码方案， 就文档树中是否有结点插入的情况来分， 可以分为 静态编码和动态编码两大类。 但按照其设计思想和编码特点来分，又可以分为 三大类: 基于区间的编码方案、 基于路径的编码方案和基于数学计算的编码方 案。下面将分类来阐述各类编码方案。 2 .3 . 1 基于区间的编码方案 基于区间 ( re g i o n - b a s e d ) 的 编码方案利用x m l 文档有序的 特点， 根据一个元 素结点在原x ml 文档中字典顺序的位置给每一个元素结点赋予一个编码。 第一 种区间 编码方 案是d i e t z 编码【 12 1 。 它的 编码规 则 为: 树t 中 的 每一 个结 点都被赋予 一个先 序遍历号 和一 个后序遍历号的 二元 组 p r e , p o s y 。由 于树中 的一 个祖先结点u 在先序遍历( 后序遍历) 中必然出现在它的后裔结点v 之前( 之 后) 。 因 此， 结点u 和v 是 祖 先 / 后 裔关系， 当 且仅当p r e ( u ) p r e ( v ) p o s t ( v ) p o s t ( u ) o 有一种推广改进， 是在x m l 文档树中的每一个结点再赋予一个值p ar ， 表示该 结点的 双亲结点的 先 序遍历 序 号p re ， 以 反映结点 之间 的 双 亲 / 孩子关系。 区间 编 码举例见图2 . 1 所示。 第 二 种区 间 编 码是q . l i 和b .m o o n 编码 113 。 它 的 编 码 规 则 为 : x m l 文 档 树t中的每一个结点都被赋予一个二元组 ，其中，o r d e r 为结点的 扩展先序遍历序号， 它的取值是非连续的， 为结点的插入预留序号空间: s i z e 为 结点的后裔范围。对于该编码方案，树结点的 必须满足如下两点: 第二章 n a t i v e x m l 数据库编 码方案 概述 ( 1 ) 对于树中的 结点y 和它的双亲结点x ， 有。 r d e r ( x ) o r d e r ( y ) o r d e r ( y 卜 s i z e 切- o r d 州x ) + s i z e ( x ) o ( 2 ) 对于 树中 的兄弟结点x 和y ， 如果在先序遍历中 结点y 是结点x 的 右兄 弟，则。 r d e r ( x ) + s i z e ( x ) o r d e r ( y ) o 这种编码方案可以 进一步改 进为 增加一个 层信息， 它相比d i e t z 编码， 能 更 好支持文档的修改。 编码举例见图2 . 1 所示。 第 三 种 区 间 编 码 是山 a n g 编 码 141 . 它 的 编 码 规 则 为 : x m l 文 档 树 中的 每 一 个结点 被赋予一个 二元组 。 对树中 的所 有结点进 行先序遍历， 每一 个结点在遍历时 分别被访问 两次并产生两个序号。 一次是在遍历该结点的所有 后 裔结 点 前 访 问 该 结 点 ， 并 产 生 该 结 点的 序号b e g in ; 另 一 次 是 在遍 历完 该 结 点 的所有后裔结点之后再一次访问该结点，并产生该结点的另一个序号 e n d 。编码 举例见图2 . 1 所示。 第四 种区间 编码称为w a n 编 码 15 l ， 它的编码 规则 为: x m l 文档树种的每一 个结点 被赋予一个二元组 ， 其中， o r d 。为 结点的 扩展先序遍 历序号， 它与l i - m o o n 编码的 含义相同; m a x o r d e r 为 结点的 后裔中 最大的扩展 先序遍历序号，即以该结点为根结点的子树中 最右下角结点的 扩展先序遍历序 号。wa i ， 编码举例见图2 . 1 所示。 图2 . 1 x m l数据的各种 编码方案 1 0 第二章 n a t i v e x 6 1 l 数据库编码方案概述 2 . 3 .2 基于路径的编码方案 基于路径( p a t h - b a s e d ) 的编码方案是利用x m l文档的 嵌套特点， 根据x m l 文档的嵌套结构，给从文档根结点开始所能达到的每个路径和元素结点赋予一 个编码。 第一种路径编码是n . w ir t h 提出的位向 量编码11 6 1 : 树t 中 每个结点被编码 为一个n 位向量， 其中n 是树中的结点数量， 在某个位置i 上的一个 1 ” 位唯 一地表示第i 个结 点; 并且在一 个自 顶向 下 ( 或自 底向 上) 的 编 码方 案中， 每 一个 结点 继承标识它祖先 ( 或后裔) 的 所有位上的“ i n . 位向 量编码举例说明见图2 . 1 0 第 二 种 路 径 编 码 是 前 缀 编 码 ， 前 缀 编 码 也 可 以 称 为d e w e y 编 码 【1 71 。 前 缀 编 码的规则是直接将一个结点的双亲结点的编码作为该结点编码的前缀。例如， 设树t 的 一 个结点u 的 前 缀编码 位c ( u ) ， 则结点u 的 孩子结点v 的 前缀编码c ( v ) = c ( u ) .n ， 这里n 是结点v 在结点u 的所有孩子结点中的 序号。 对于前缀编码， 要 判断一个结点v 是否是另一个结点u 的后裔， 只需判断字符串c ( u ) 是否是字符串 c ( v ) 的前缀。 增加了 字典有序的前缀编码的一个重要性质， 是它们的字典有序:以结点r 为根的 子 树中 的 任 意 一个结点u ， 它的前 缀编码c ( u ) 大于( 小于 ) 左兄弟 子树( 右兄 弟子树) 中 所有结点的前 缀编码。因此，字典 有序的前缀编码不仅能 够有效地支 持包 含关系的 计算， 而且 还能 够有效支持文 档 位置关 系的计 算。 d e w e y编码举 例说明见图2 . 1 所示。 o r d p a t h 编 码 方 案 1 18 1在 基 于d e w e y 编 码 方 案 的 基 础上 做 了 对 动 态 更 新 的 改进，以 1 . 5 .9 .9 .5 ”为例: ( 1 ) o r d p a t h是 一 个分级 编 码方案， 每 个 分 量 值用逗点“ ” 隔开， 它由 多 个分量值构成。 ( 2 ) 文档根结点总是以勺”开始，子结点 首先从父结点获得o r d p a t h值， 然后追加一个逗点后，再增加一个由左到右的顺序分量值。 ( 3 ) 在d o m树 初始 化时， o r d p a t h结点 分量 值以 正 奇数作为 分量值， 它的 个数表示该结点在树中的深度。 ( 4 ) 当 在树的最右边增加一个新的结点时， 理论上表示兄弟结点顺序增加的 分量值没有限制。当在树的最左边增加一个新的结点时，以一个顺序减少的方 式完成，可以使用负数。 第二 章 n a t i v e x 6 1 l 数据库编码方案概述 ( 5 ) 当 在两 个兄弟结 点中 插 入一个新结 点时， 如果没有 可 用的 表 示顺序的分 量值时，需要使用 “ 脱字符”的技术，此时需要先插入一个偶数值，然后再追 加一个奇数分量值。 注意，偶数分量值对结点在树中的深度并没有贡献。 d l n 编 码 方 案 19 1在d e w e y 前 缀 编 码 方 案 的 基 础 上 ， 做 了 与 上 述 功 能 雷 同 的 改进，它使用了增加子层分隔符和子分量值的概念.这两种方案都没有考虑到 在增加新结点时预留 一定编码空间的能力， 在特殊情况下， 编码长度会迅速增 加。 x t c 系 统中 的 动 态 编 码 方 案 120)， 吸 收 上d e w e y 编 码 方 案 优点 的 同 时 ， 还 增 加了 一个平均距离参数( 图2 .2 中 距离参数为4 ) ， 通过预测来将来可能插入的结 点附近预留一定的结点编码空间，从而一定程度上减少了前缀编码的平均长度. a t t r i b u t e t e x t n o d e t 9 5.5南 1.5.5.9. it o巳 图2 . 2 x t c系统中的动态编码举例 这三种方案不仅具有基于路径编码方案的前缀特点， 而且又具备基于区间 编码的文档位置信息的特点，同时具备了适合更新操作的功能。但是在编码方 案的最大长度或平均长度方案还有待优化，在结点的重构和次序敏感性查询上 还需要进一步加强。 第 二章 n ati v e 7 d 11 数据库编 码方案概述 2 . 3 . 3 基于数学计算的编码方案 基于数学计算编码方案 包括完全完全树编码， 素数编码， b i r d编码等。 这 种编码方案利用了d o m树的 深度优先遍历对每个结点 进行遍历， 采取自 底向上 或者 自顶向下的方式进行结点的编码，然后利用某个数学理论或者方法约束计 算得到以后遍历到的结点的编码。 完全树编码方案的核心设计思 想是:先 构造一颗完 全k 叉 树， 然后将x m i . 文档转换为k叉 树后嵌入到这颗完全k 叉 树中， 以 结点 在完全k 叉树中的前序( 后 序) 遍历号作为其编码。 文献 2 1 - 2 3 1 提出的 都是完 全树编码方案及其 变型。 素数编码标识方案 24 1 基于素数的 特性， 对x m i . 文档树进行遍历时， 对每个 结点赋予一个素数。 这个编码方案确保每一个编码能仅仅被它自 己的祖先结点 整除。结点无序的 素数编码标识 方案有自 顶向下和自 底向上两种方式。 下面将 以自 顶向 下的方式为例。 无序素数编码标识方案对每个结点的编码为父结点编 码和自身编码两部分编码的乘积， 根结点编码为1 = 1 x1 ， 它的左结点则编码为: 1 ( 父结点 编码) x 2 ( 自 编码片 。 如图2 . 3 所示。 (3 票 3 ) 图2 .3 自 顶向下基 本素数编码方案 这种无序素数编码标识方案 在树的深度加 深时， 编码的整数 值上升的极 快。 而且，不 能很 好的 处理 三种次 序敏感性 (p r e c e d in g - s ib lin g if o llo w in g - s ib lin g , p o s i ti o n = n , p r e c e d i n g / f o l l o w i n g ) 的 查询。 为了 解决 次序敏感性的查询问题，该 文提出一种结点有序的素数编码标识方案， 该方法充分利用了中国 剩余定理12 3 1 来解决素数 编码方案中 的次序问 题，也以 较小的 代价来处理动态更新问题。 先介绍中国 剩余定理: 设函数g c d ( m , ,m 2 , . . . m k ) 表示为 一组整数m ( , m 2 , . . . m k 的最大公约数;m= m i , m 2 , . . . m k l 和 n = n ( , n 2 , . . . n k 表示为两个整数序列。如果 g c d ( m , , m 2 , . . . m k ) = 1 ， 则联立同余数s c ( m, n ) = x o 第二章 n a t i v e 1 m l 数据 库编码方案概述 联立同余式: m o d m , 二 n i m o d m 2 =气 x m o d m , = a t k c = i z m i i =1 k x = e ( c / m i) * r4 * 4, ( m ) ) m o d c i=1 甘几va c 和x的 公 式 如 上 所示 ， x 值 在。 与c 之 间 。 该 文 献 中小( m i) 是欧拉商 函数，它的复杂度是 0 ( n ) 。它在素数编码中的应用举例如下图 2 . 4 所示。 . ， 肠日巨峥 翻 .侧 卜甘 图2 . 4