（计算机应用技术专业论文）p2p环境中xml索引及其安全模型研究.pdf

内容摘要 内容摘要 x l i l 是互联网中表示结构化信息的一种标准文本格式 它没有复杂的语法和 包罗万象的数据定义 但却利用半结构化的数据表达 良好的实现了互联网中的 数据交换 x m l 利用可扩展性 灵活性和自描述性的特点 得到了越来越多的实 际应用 特别是在p 2 p 环境中需要用网络共享达到更好的资源分配效果 由于 x m l 可以良好的对数据进行承载和表达 因此在p 2 p 环境中采用x n 技术将有效 的提高系统的资源搜索能力 本文在天津市科技计划项目 压缩环境中基于 n 札的数据集成系统关键 技术研究 的研究背景下 通过x m l 索引 结构连接算法 x m l 安全等基础研究 讨论如何在p 2 p 环境中建立x m l 索引及安全算法 本文提出了一种基于p 2 p 环境 的 n 也资源共享模型 目的是为了解决捌l 文件共享及提高索引效率等诸多问题 并在该种模型的前提下 提出了一种以二进制为依托的x m l 索引及共享算法一 摘要x m l 索引 d x i 该模型以j x t a 作为p 2 p 环境平台 在j a v a 程序平台上实 现点对点资源通信 关键词 x 乩x m l 索引p 2 pd x i 数据隐藏 第l 页 a b s t r a c t x m li sas t a n d a r dt e x tf o r mt oe x p r e s ss t r u c t u r e di n f o r m a t i o ni n i n t e r n e t w i t h o u tc o m p l i c a t e dg r a m m a ra n dd a t ad e f i n e x m lu s e sak i n d o f s e m i s t r u c t u r ed a t a e x p r e s s i o n t o i n t e r c h a n g e d a t a t h e c h a r a c t e r i s t i c so fx m li n c l u d e e x p a n s i b i l i t y f l e x i b i l i t ya n d s e l f d e s c r i p t i o n i nt h i sc o n d i t i o n x m lg e t sm o r ea n dm o r ep r a c t i c a l a p p l i c a t i o n e s p e c i a l l yn e t w o r kn e e d sb e t t e rr e s o u r c ea l l o c a t i o ni np 2 p e n v i r o n m e n ta n dx 1 4 lc a nh a n d l ew i t hm o r ed a t a t h e r e f o r e x m lt e c h n o l o g y c a ni m p r o v et h ea b i l i t yt os e a r c hr e s o u r c ei np 2 pe n v i r o n m e n t u n d e rt h eb a c k g r o u n do fs t u d y i n go f t h er e s e a r c ho fk e yt e c h n o l o g y o fd a t ai n t e g r a t e ds y s t e mb a s e do nx m lt e c h n o l o g yi nc o m p r e s s e d e n v i r o n m e n t s u p p o r t e db yt i a n j i ns c i e n c ea n dt e c h n o l o g yp l a ni t e m s 町 t h e s i sa i m sa th o wt oe s t a b l i s ha na l g o r i t h m sb a s e do n 弛也i n d e xa n d s e c u r i t yt h r o u g ht h eb a s i cs t u d yo fx m li n d e x s t r u c t u r ej o i na l g o r i t h m s a n dx m ls e c u r i t y t h i sp a p e rp r o p o s e dak i n do fx m lr e s o u r c es h a r i n g m o d e lb a s e do f fp 2 pe n v i r o n m e n tt os o l v ex m lf i l es h a r i n ga n di m p r o v ei n d e x e f f i c i e n c y i tc r e a t e da nx m li n d e xb a s e do nb i n a r ya l o g o r i t h 甄w h i c hi s c a l l e d d i g e s t x m li n d e x d x i t h i sm o d e l r e g a r d sj x t aa sp 2 p e n v i r o n m e n t a lp l a t f o r m w h i l er e a l i z i n gp o i n t t o p o i n tr e s o u r c e sa n d c o m m u n i c a t i o no nj a v ap l a t f o r m k e yw o r d s x m l 眦i n d e xp 2 pd x ii n f o r m a t i o nh i d i n g 第 页 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果 尽我 所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写过的研 究成果 也不包含为获得云洼题菹太堂或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明井表示了谢意 签名 学位论文版权使用授权书 本人完全了解天津师范大学有关保留 使用学位论文的规定 即 学校有权将学位论文 的全部或部分内容编入有关数据库进行检素 并采用影印 缩印或扫描等复制手段保存 汇 编以供查阅和借阅 同意学校向国家有关部门或机构送交论文的复印件和磁盘 保密的论文在解密后应遵守此规定 签名 导师签名 日期 第1 章绪论 1 绪论 1 1 选题背景 m i l l 是一种越来越受到广泛使用的网络置标语言 越来越多的得到了实际应 用 x i l 作为一种可扩展的标记语言 具有可扩展 可读性强 半结构化 保值 等特点 由于 也采取了用户自定义标签的形式用以定义半结构化数据 这就给 予了用户更多的自由来实现更多的个性化选择 因而在实际的网络应用中 x 礼 也越来越多的承载着重要信息 为了有效的保护和索引这些数据 b i l 索引 札 安全等技术应运面生 本文在天津市科技计划项目 压缩环境中基于b i l 的数据集成系统关键 技术研究 的研究背景下 通过x 礼索引 结构连接算法 x 虬安全等基础研究 讨论如何在p 2 p 环境中建立x 札索引及安全算法 1 2 研究意义 利用 叫 纯文本文件可以用来存储数据 而大量的数据可以存储到x 札文 件中或者数据库中 应用程序可以读写和存储x m l 数据 一般的程序可以显示数 据 通过y 3 1 l 技术 纯文本文件还可以用来共享数据 既然 凸也数据是以纯文本 格式存储的 那么 礓儿提供了一种与软件和硬件无关的共享数据方法 这样就可 以创建一个能够被不同的应用程序读取的数据文件 基于x m l 的优点 在p 2 p 环境中用户信息 网络地址 数据索引等都可以利 用 n 儿进行数据储存及数据交换 我们设想的模型在p 2 p 环境中仅利用 f i l l 可以 进行完全的数据存储 利用x m l 建立的索引来提高查询效率 包括图形及影音等 类型文件都可以通过x m l 建立相应的目录对相应信息进行保存 用户的隐私信息 可以通过个性化的选择来进行保护 论 1 3 本文研究的重点 本文在阐述基于p 2 p 环境的 n 也系统模型研究时 重点从以下几个方面来讨 第1 页 第1 章绪论 1 对于x 1 4 l 索引和查询算法的研究 在综述了x m l 索引的概念 分类等 内容基础上 详细的分析了多种x m l 索引的建立方法 在结构连接算法中 阐述 了在索引方法上实现查询的多种具体算法 2 对于x m l 安全的研究和探索 首先阐述了x m l 安全的重要意义 分类 等 在已有分类中说明了几种可行的安全实现方法 并在模型中尝试实现信息隐 藏 3 在比较了各种索引方法和结构连接算法后 本文将采用j x t a 作为p 2 p 环境开发平台 实现基于x m l 技术的系统模型 在模型中实现了一种具体的索引 方法d x i 和信息隐藏方法 通过节点之间的通信实现了 n 也的信息交互 1 4 本文的组织结构 本文组织结构如下 第一章是绪论 介绍本文的选题背景 研究意义 研究重点 并说明文章的 组织机构 第二章x m l 索引 主要介绍瑚l 索引的概念及优缺点 之后讨论了建立x m l 索引的几种重要方法 通过对数字编码索引的对比研究 分析出现有编码索引共 通点 第三章将介绍结构连接算法 通过在数字编码基础上实现的 强札查询算法 说明如何实现基于x m l 的查询技术 利用堆 栈等多种数据结构算法 阐述结构 连接算法如何与编码方案相结合 第四章主要x 帆安全的相关内容 并介绍了x m l 安全的分类 重要意义和主 要实现方法等 第五章详细介绍了o x i 算法以及相关定义 详细说明了该种算法的优势和存 在的问题 并对存在的问题提出了改进思路 第六章将在以上几章的基础上构建一个在p 2 p 环境中的x m l 系统模型 并在 该模型中实现x m l 索引和 强几安全的结合 本章中首先提出了瑚l 系统模型的基 本结构 并在该结构中实现了基本的通信模块 第七章是论文的总结 总结了论文的不足之处和需要改进的地方 第2 页 第2 章x b i l 索引 2 1 眦技术 2x m l 索引 埘l e x t e n s i b l em a r k u pl a n g u a g e 可扩展的标记语言 是互联网中表示 结构化信息的一种标准文本格式 它没有复杂的语法和包罗万象的数据定义 但 却利用半结构化的数据表达 良好的实现了互联网中的数据交换 著名的商用数 据库s q ls e r v e r o r a c l e 都实现了与飙l 数据格式的兼容 n o r m a nw a l s h 曾经说过 从网络使用之初 我们一直在所有文件中都使用 近乎相同的格式 h t m l 格式等 使用具有周定语法的固定标记集具有一定的好 处 即简单性 但是 h t 札非常有限 网页设计者希望能够对页面的表现能力 具有更多的控制 这就需要求助于 n l l 几作为一种标记性的语言使得在网络 环境中的格式表达更为明确 它采取了用户自定义的标记形式 并允许在标签中 携带更多的信息 n 也是一套定义语义标记的规则 这些标记将文档分成许多部件并对这些部 件加以标识 它不像h t 札或格式化程序 这些语言定义了一套固定的标记 用 来描述一定数目的元素 x 札是一种元标记语言 用户可以定义自己需要的标记 这些标记必须根据某些通用的原理来仓i 建 m l 标记描述的是文档内容的结构和 含义 而不是描述页面元素的格式化 可以利用样式单为文档增加格式化信息 x m l 作为一种可扩展的标记语言 具有良好的可扩展性 可读性强 保值性 等特点 x 札采用了一种用户自定义标签的构建方式 可以很好地定义半结构化 数据 随着 也技术的不断成熟 关系数据库数据与 n 也数据的相互转化 强也 在关系数据库中的存储和提取 x m l 索引 眦查询及 凸也原生数据库都成了极 为热门的研究领域 x m l 语言区别于其他语言的巨大优势还在于其对数据的表达 利用 也 纯 文本文件可以用来存储数据 大量的数据可以存储到 叫 文件中或者数据库中 应用程序可以读写和存储数据 一般的程序可以显示数据 通过x i l l 技术 纯文 本文件可以用来共享数据 既然 a 儿数据是以纯文本格式存储的 那么聊l 提供 了一种与软件和硬件无关的共享数据方法 这样创建一个能够被不同的应用程序 第3 页 第2 章x m l 索 读取的数据文件就交得十分简单了 当今的计算机世界中 不同企业 不同部门中存在着许多不同的系统 操作 系统有n t u n i x 数据库系统有s o ls e r v e r o r a c l e 等 要想在这些不同的平 台 不同的数据库软件之间传输信息 不得不使用一些特殊的软件 非常之不便 而不同的显示界面 从工作站 个人微机 到手机 使这些信息的个性化显示也 变得很困难 然而利用x m l 各种不同的系统之问可以采用x m l 作为交流媒介 儿不但简单易读 而且可以标注各种文字 图像甚至二进制文件 只要有x m l 处理工具 就可以轻松地读取并利用这些数据 使得x m l 成为一种非常理想的网 际语言 2 2x m l 索引概述 索引是提高查询速度的最重要的工具 由于i o 代价对于数据库操作的重要 性 必然要通过d b m s 在磁盘的上组织数据记录文件来减少i o 代价 索引就是 在磁盘上组织数据记录的一种数据结构 用于优化某类数据检索的操作 x m l 文件中的元素关系基于一种嵌套结构 x 眦文件被描绘成一种节点被标 记的树形模型 查询则是以一种统一的表达方式 通过文件结构和节点取值来进 行对文件的搜索 在大多数的x m l 查询语言中 x m l 文档结构都以线性路径或枝 叶模式来表示 其中x m l 元素的取值成为选择谓词的一部分 x m l 文件是一种半 结构化的数据表达 索引的作用就是将x m l 文档标签甚至内容映射成易于处理的 表达方式 为了清晰的方式阐明x m l 树形结构中数据彼此之间的关系 人们通常 采用数字编码来实现 利用数字编码方式 可以方便的确定出一棵树中祖先与后 裔之间的关系 通过查询来解决对x m l 数据的搜索 索引的构建方式主要有两种 即结构索 引和数字编码 数字编码模式则利用 a 也的节点位置进行相应的编码 目前大多 数的数字编码模式都基于树遍历模式 节点之间的结构关系通过索引编码进行的 确认 这类方法首先需要分别处理在枝叶中每个根到叶子的路径 然后再将各个 结果进行合并 结构索引通过处理路径和枝叶查询 t w i gp a t t e r n 来减少搜索 空间 第4 页 第2 章x m l 索 z 2 1x 札索引优点 酬l 索引作为一项新兴的研究领域 需要更多的参考及借鉴其他的数据索引方 式 并在这个过程中发挥x 虬半结构化的优势 对x 虬文档建立索引的优点在于 1 维护顺序 由于对于 函也文档中所包含的大规模数据记录 如果被频繁的修改 保存顺 序的代价将会有很大的提高 不利于查询 即得到数据集合 另外当查询的记 录集很大 但只包含少量的符合条件的记录 那么效率也会非常低 采用索引方 式 不但可以有效地保存数据集合 还可以在索引的同时对某类数据进行提取 从而达到隐私保护的目的 2 支持多限制查询 当查询具有多个限制条件时 通过多个索引的限制可以有效的帮助查询快速 得到结果集合 避免了重复扫描整个文件来得到记录集 支持一次使用两种不同 方法对数据行进行捧序 同在关系数据库中相同 由于涉及多表连接查询 就会使得索引的优势更加 明显的发挥 未加索引时 我们必须通过多表连接的所有可能数据组合来确定是 否满足条件 当多表的数据项数日可观时 就造成了大量的运行时间 引入索引 后 只需顺序查找第一个表中数据项 针对该锁定数据项使用其他表上的索引 与其进行关联定位 这样 除了第一个外的其他表 我们不必遍历其所有的数据 项 大大减少了运行时间 以三个1 0 0 0 记录的查询为例 通过加入索引 理论 上采用这种方式运行上面的查询会快一百万倍 3 保存x 札文档结构 由于 函儿具有半结构化数据的特点 在 凸儿中可以包含整个文档的结构 因 此在建立 q 儿索引的同时可以利用索引保存结构信息 例如 t w i g 结构索引等 将索引和数据相结合有效的提高了 强也文档的查询效率 使得在针对文档进行的 查询中可以采取更多的方法和语法 2 2 2x m l 索引缺点 虽然x 札所建立的索引会为查询带来诸多便利 但是不可否认 礓儿索引同 其他数据索引方法一样 也会产生相应的闯题 因此高效索引的建立必须要考虑 第5 页 第2 章x m l 索 到如何解决这些存在的问题 1 插入及删除 索引加快了检索的速度 但是减慢了插入和删除的速度 同时还减慢了更新 被索引的数据列中的值的速度 也就是说 索引减慢了大多数涉及写操作的速度 发生这种现象的原因在于插入一项数据的时候不但需要写入标签项 还需要改变 所有标签或数据的索引 文档所包含的索引项越多 需要做出的修改就越多 平 均性能的降低程度也就越大 2 磁盘空间 建立索引是在文件的基础上重新组织数据结构的方法 索引会花费磁盘空 间 多个索引相应地花费更多的磁盘空同 这可能导致更快地到达数据表的大小 限制 2 3 向量编码 v e c t o re n c o d i n g n g i r t h 1 率先提出了向量编码 树r 中的每个节点被译码为一个斗位向量 一是树r 中的节点数量 在某个位置j 上的一个 1 位唯一的表示第f 个节点 并且在一个自顶向下 或自低向上 的编码方案中 每一个节点继承表示它祖先 或后裔 的所有位上的 l 例如 树r 的一个节点越的位向量编码记为 6 l 乩 如果树r 的第f 个节点是节点 或它的祖先 则6 f l 否则 0 对于继承祖先的位向量编码 利用二元为运算a n d 能够快速检测一个 节点 是否是另一个节点 的祖先 是v 的祖先 当且仅当c h c 一 c u 对于继承后裔的位向量编码 利用二元位运算o r i 能够快速检测一个节点 是否是另一个节点 的后裔 却是 的后裔 当且仅c u ic v c 因此 位向量编码能够有效支持包含关系的计算 利用位运算的特点 该种方法将提高 比较运算的执行效率 从而缩短检索时间 但向量编码在节点增长的同时也会造 成编码的长度迅速增长 加重数据存储的负担 兄弟节点之间的为其后裔分配的 编码不能造成范围重叠 因此对节点的更新可能需要较大变动 图2 1 为向量编 第6 页 第2 章x m l 索5 码的示例 图2 1 向量编码 2 4 于前缀的编码 p r e f i xe n c o d i n g 前缀编码也称为d e w e y 编码田 前缀编码直接将一个节点的双亲节点的编码 作为该节点编码的前缀 这看来似乎和我们所介绍的位向量编码有些相似之处 例如 树r 的一个节点 的前缀编码记为o j 则节点 的孩子节点1 的前缀编 码 v 2 d 咖 这里弹是节点y 在节点 的所有孩子结点中的序号 对于前缀编码 要判断一个节点 是否是另一个节点 的后裔 只需要判 断字符串c 是否是字符串 力的前缀 前缀编码的一个重要性质是它们的字典 有序 以节点 为根的予树中的任意一个节点 它的前缀编码 协j 大于 小于 它的左兄弟子树 右兄弟子树 中所有节点的前缀编码 因此 前缀编码不仅能 够有效的支持包含关系的计算 而且能够有效的支持文档位置的计算 图 2 为 前缀编码的示例 第7 页 第2 章x m l 索 图2 2 前缀编码 2 5 区域编码 r e g i o ne n c o d i n g 由于 也文件本身就具有一种树形结构 节点之间较为容易形成对应关系 因此 基于数字编码的方案大多借助对树的遍历来得到节点之间的联系 而这种 联系由于遍历方法的差异也不尽相同 一般说来 遍历分为前序遍历 中序遍历 和后序遍历 还有一些根据它们改进的遍历方法 2 5 1 基于遍历的编码 1 9 8 2 年 d i e t z 最先提出了一种以数对 确定 也文件结点的方 法咖 其中朋代表对 凸也文件树形结构的前序遍历的序号 p 珊f 代表对x m l 文 件树形结构的后序遍历的序号 这种方法依靠前序遍历和后序遍历的编码关系来 确定节点之间的联系 查询中就可以利用确定的范围来进行节点的搜索 图2 3 为一个d i e t z 的简单示例 第8 页 第2 章x m l 索g 图2 3d i e t z 编码 一个x m l 文档树的先序遍历顺序等价于它的文档顺序 即如果对文本形式的 x 札文档进行顺序读取 则每一个元素被访闯的顺序就是它们的先序遍历序号 反之 x m l 文档的文本表示能够以先序遍历它的文档树的形式进行重构 虽然这 种方法使用了一种简易方式对 礓也文件进行标注索引 但却不能很好的解决x 扎 文件更新的问题 当需要插入一个新的结点时 将引起索引文件的大规模变动 很多方法中提出的x m l 数据的区间编码方案都是d i e t z 编码的推广 例如 t g r u s t 1 在d i e t z 编码的基础上 给瑚l 文档树t 中的每一个节点再赋予一个 值p a r 表示该节点的双亲节点的先序遍历序号p r e 以反映节点之间的双亲 孩子关系 2 5 2l i m o o n 编码 l i 等人提出了m m o o n 方法嘲 利用数对 来分别表示扩展的 x m l 文件的前序遍历序号以及后裔结点的数目范围 基于x m l 文件树形结构的特 点 以及众多可行方法的实践论证 建立在前序遍历上的索引可以极大的提高对 于x m l 文件的搜索效率 m m o o n 编码与d i e t z 编码相比 能够更好的支持文档 的修改 对于该编码方案 o r d e r 作为唯一的标识 但这种方法对节点编码进行 扩充的同时 也对节点资源造成了一定的浪费 在不清楚节点数目和更新数量的 前提下 这种固定的更新范围 实际上很难满足实际的需要 图2 4 为一个 l i m o o n 编码的简单示倒 第9 页 第2 章x m l 索 图2 4m m o o n 编码 在对索引方法的整理中 我们不难发现 大多数的编码索引方案都可以被分 为基于范围的和基于前缀的 基于前缀的标签方案即向量编码 前缀编码等 通 过索引的适当顺序 决定祖先节点和后裔节点之间的关系 而范围编码 即索引 建立在数对的基础之上 利用范围关系决定祖先节点和后裔节点之间的关系 多数的 n 也数据索引结构 也元素的取值决定于真实值 鉴于在x m l 文档 中元素问的结构关系 如果源数据被更新 那么我们就不得不重新审查这些真实 值 重构需要索引文件的大规模更新 当 c 虬数据内容被频繁的更新时 这将引 起严重的问题 d a o 等人提出了一种基于相关域坐标的索引结构对l i h i o o n 进行扩展 来有 效的解决了索引更新的问题旧 捌l 文件中的内容取值基于它的父母元素域建立 叫做相关域坐标 使用相关域坐标来标识x 眦文档 可确定元素对于其父母元素 的域何时开始和结束 同时采用了一种建立树结构索引的算法 使得相关值可以 被存储在一起 索引结构在更新时只需要针对小部分索引文件的更新 x 札在于 允许用户使用一种用户自定义字典的数据结构来描述对数据的翻译过程 通过这 种翻译语言 可以得到源数据来用于互联网上的数据交换 凸儿文件的数据系统 应该支持基于内容和结构的查询 w a n 编码实际上是一种扩充了m m o o n 编码方案 x m l 文档树中的每一个节 点被赋予一个二元组 o r d e r m a x o r d e r 其中o r d e r 为节点的扩展先序遍历序 号 r 锄x o r d e r 为节点的后裔中最大的扩展先序遍历序号 即为该节点为根节点 的子树中最右下角节点的扩展先序遍历序号 另外 树中的每一个节点再被赋予 第1 0 页 第2 章x m l 索引 两个值p a r e n t o r d e r 和p a r e n t m n x 分别表示该节点的双亲节点的o r d e r 和 m a x o r d e r p a r e n t m a x 用来加速结构连接的计算 2 5 3 可扩展范围的编码 基于范围的标签方案可以在常数时间内 决定两个节点之间的祖先关系 缺 点在于当进行插入操作的时候 将不可比避免需要进行标签的重新定义 因此 k i n g 等人提出可扩展范围的编码m 考虑将基于范围编码的扩展方案与基于前缀 的编码方案相结合 得在进行插入操作对避免引起标签的重新定义 采用范围分 配方法还可以有效的改进标签索引方法性能 对于范围编码 节点v 的s i z e 是以其为根节点的后裔个数的上界 对于前 缀索引 一个节点的级别就是标签的长度 可扩展方法将这两种方法进行了适度 的结合 创建了一种新的标签索引方法 在这种方法中 每个节点v 都被赋予一 个整数对 且这个整数对有一个整数序列作为前缀 形如a p o s 我们将n 称为节点v 的级别 o 代表同级别的前序遍历序号 s 代表与v 同级别的后裔的 数目 图2 5 为可扩展范围编码的简单示例 图2 5 扩展范围编码 扩展的先序遍历标签方案在进行插入操作时 也会产生无范围可插入的情 形 因此我们分析如下情形 1 当有范围可使用时 可依照一般方法进行节点的插入 2 当无范围可使用时 插入的节点将被标记为p i 口 o l 前缀p i p 用来记录祖先信息 o 用来创建一个新子树的 伪根 并且这种新子树 第1 i 页 第2 章x m l 索引 也是建立在扩展的先序遍历的基础之上的 这种将范围索引和前缀索引相结合的方法 有效的实现了对树形文档结构的 扩展 而这种扩展是以扩大节点标签为代价的 换句话说 节点的前缀长度是不 能确定的 因为它要包含其祖先节点的前缀信息 如果在最坏的情况下 新的子 树不断被创建 形成一个以新予树为主的树形结构 必然会影响查询的执行效率 因此 d t d 和对文档的分析可以帮助优化范围的分配 2 5 4z h a n g 编码 z h a n g 等人提出了z h a n g 编码嗍 它的编码规则为 x m l 文档树中的每一个节 点给赋予一个二元组 对树t 的所有节点进行先序遍历 每一个节 点在遍历时分别被访问两次并产生两个序号 一次是在遍历该节点所有的后裔节 点之前访问该节点 并产生该节点的序号b e g i n 另一次是在遍历该节点所有的 后裔节点之后访问该节点 并产生该节点的序号e n d 因此 树t 的任意两个节 点是祖先 后裔关系 当且仅当b e g i n u b e g i n v e n d v e n d u 即祖先节点 的区域编码包含了后裔节点的区域编码 图2 6 为z h a n g 编码的简单示例 图2 6z h a n g 编码 2 6 二叉树编码 p b i t r e e p b i t r e e 编码啪针对嵌套的连接处理 适用于类似 函几文件的树形结构数据 这种嵌套的连接将两个x 眦节点元素集作为输入 返回在两个集合中可以建立嵌 套关系的元素对 为了实现嵌套连接的应用算法 就需要保证元素集被储存且被 第1 2 页 第2 章x m l 索g 索引 p b i 树由此应运而生 它提出了一种新颖的完全嵌套的查询处理框架 基 于p b i 树的编码机制可以允许我们高效的确定祖先和后裔之间的关系 在所涉及 的算法中 提出了优化集合结合方式的方案 其中包含的分解算法可以不通过捧 序和索引 高效的处理嵌套连接 嵌套关系等同于树形数据模型中的祖先 后裔关系 嵌套查询也是x 札查询 处理引擎的核心组成部分 现有的嵌套连接算法 都基于如下假设之一 所有的 元素都有索引 所有的元素集都被捧序 兼有前两者 但在x m l 数据库中并不是 所有的与元素都被排序或索引 受这一特性的启发 p b i 树编码则可以支持祖先 后裔关系的校验 p b i 树编码是一种基于遍历编码的结构 它利用的二叉树中序遍历编码的特 性 在该模型中 将树的中序遍历编码二进制化 可以通过这种二进制化的数码 得到相应的树高 祖先节点的数字关系等 显然 利用这种方法构建的p b i 树可 以仅仅根据编码就快速确定祖先 后裔关系 但另一方面 这种方法使得在构建 之初 就必须建立一棵完全的二叉树与实际的x 札文档进行对应 其中使用不到 的节点被称为虚节点 当然这种虚节点是完全虚拟的 不需要建立它们 更不要 说建立相应的存储空间 之后 再通过实际x m l 树与p b i 树的对照关系 将实际 的树形进行p b i 树转化 由于p b i 编码采取了二进制的形式 对于一棵完全二叉 树 某个节点 和其祖先一 则啊的编码为f n 2 m b 2 1 j 2 其中h 为 川的高度 玎为珂 的编码 p h i 编码采取了二进制编码 因此对于任意一个节点 玎 它在p b i 树中所处的高度正好是p b i 编码中最右一个非 0 位 即 l 位 的位置 对祖先编码的确定就只涉及到移位和整数运算 不需要浮点运算 由于p b i 树的编码方式 使得编码本身就携带了丰富的结构信息 与区域码 每个节点需要两个编码相比 该方法对于每个节点只需要一个编码 p b i 树编码 的可以转化成区域编码 也是它的特点之一 只要得到节点的高度和相关信息 我们不难想象 在二叉树特点的帮助下 就很容易得到该节点的区域码 图2 7 图2 8 图2 9 为p b i t r e e 编码的简单示例 第1 3 页 第2 章x m l 索 图2 7 个舭文档 l m 2 h l i a l 蝴 t s v e 3 i 幅o h t l l e v q h e 蝌巾 o 图2 8 一棵 儿文档树 图2 9p b i t r e e 编码 对一棵数据树的二进制数形化可以通过下面的途径 二进制化当前节点和其 孩子节点 递归的二进制化其孩子节点作为根的子树 由于p b i 树是基于一种二 叉树的树形结构方式 因此对于多孩子的情形 就需要向下扩展节点级别 二进 制化树的算法对这种p b i 编码与相应自上而下的p b i 编码进行转化 时间复杂度 为d o 2 7 本章小结 根据对上述数字编码方案的总结 这些方案主要根据如下特点来进行设计 1 支持祖先 后裔 双亲 孩子 文档位置等关系的结构查询 2 被编码数据的结构 例如 树 图等 第1 4 页 潞 淼 第2 章x m l 索 3 编码算法的复杂度 4 编码后的查询执行时间 5 插入操作导致的重新编码代价 由于基于x m l 的编码方案需要有效的支持树形结构 因此对于祖先 后裔 双亲 孩子的结构支持是最基本的要求 例如d i e t z 方法和位向量编码等 对x m l 文档节点进行数字编码的目的在于只有通过结构的连接 才能满足结构化或半结 构化数据的查询需要 在多数的编码中 都需要利用多个标识来唯一确定一个节点 仞如z h a n g 编 码 但也有一些编码制需要利用一个编码就能得到结构关系并确定唯一节点 伪 如p b i t r e e 编码 各神编码的长度和结构关系检测比较如下表卜l 所示 表i i 各种编码方案比较 编码方案编码长度祖先 后裔关系检测 前缀编码0 n 前缀操作 d i e t z 编码o 1 0 9 n 两个非等值操作 l i m o o n 编码o 1 0 9 n 两个非等值操作 附加整数运算 z h a n g 编码o 1 0 9 n 两个非等值操作 w a n 编码o 1 0 9 n 两个非等值操作 p b i t r e e 编码0 n 等值操作 附加位运算和整数运算 第1 5 页 第3 章结构连接算法 3 结构连接算法 l 文档经过某一编码方案进行数字化后 每个节点就对应了一个或一组编 码 利用这种编码 才可以进行x m l 的查询 x m l 文档的结构查询通常被转化为 两个节点列表之间的包含关系或文档位置关系的结构连接操作 同时关键字操作 也被转化为两个节点列表之问的包含关系的结构连结操作 因此 有效地支持结 构连接对x 蛆查询的有效实现是解决问题的关键 目前所提出的结构连接算法大 都是基于归并的思想 充分利用x 地数据的结构特点来减少扫描的代价 有些算 法在归并的基础上 根据 也数据的结构特点利用索引来进一步减少连接的扫描 代价 上面所提出编码方案的目的在于将实际树形结构索引化 并根据编码方案 提出查询算法 从而实现数据查询需要 所谓的查询算法 是一类在编码方案基 础上实现结构连接的执行算法 下面的部分 将具体讨论如何在已建立的编码方 案上 通过结构连接算法实现查询 3 1x m l 查询 强儿查询的核心是路径表达式查询 路径查询是在半结构化数据中广泛应用 的查询方法 例如x p a t h x q u e r y 等 这种查询以路径的方式得到查询结果 在 越来越广泛的应用中 x p a t h 等查询语言与s o l 语言的相互转换也是处于成长中 的技术 一个复杂的x p a t h 路径表达式查询能够被分解成几个分裂路径表达式 也就 是查询的结构分解 根据节点之问的相互关系 结构查询主要分为三类 其中包 括包含关系 c o n t a i n j o i n 文档位置关系 o r d e r j o i n 和拥有关系 h o l d j o i n 包含关系 祖先 后裔关系或双亲 孩子关系 返回的是满足包含关系的节点 对的序列 或者是相应后裔的节点序列 x p a t h 的查询形式为 由两个元素或一 个元素与一个属性构成的满足包含关系表达式 如c h a p t e r t i t l e b o o k c h i l d 牛 b o o k s t i n g b o o k a t t r i b u t e 文档位置关系返回的是满足文档位置关系的序列 或者是相应后裔的序列 x p a t h 的查询形式为 由两个元素构成的满足文档位置关系的表达式 如 第1 6 页 第3 章结构连接算法 b o o k p r e c e d i n g c h a p t e r c h a p t e r p r e c e d i n g p r e c e d i n g s i b l i n g 拥有关系返回的是满足拥有关系的祖先 或双亲 节点的序列 x p a t h 的查 询形式为 1 由两个元素或一个元素与一个属性构成的满足拥有关系的表达式 如 b o o k d e s c e n d a n t s e c t i o n s e c t i o n c h i l d b o o k c h a p t e r b o o k 昏 e a r 2 由一个元素或一个属性与一个搜索关键字构成的表达式 如 c o n t a i n s t i t l 岛 s e a r c h 3 2 结构连接算法引述 大多数提出的处理结构连接的算法主要包括两类 即包含关系的结构连接问 题和文档位置关系的结构连接问题 解决包含关系的算法包括肿i i g j n 算法 t r e e m e r g e 算法 x r s t a c k 算法和h o l d j o i n 算法等 解决文档位置关系的算 法包括x p a t ha c c e l e r a t o r 索引技术和p r e f o 卜s i b j o i n 算法等 下面要介绍的大多数算法都基于c z h a n g 和j n a u g h t o n 嘲等提出的z h a n g 编码 基于区域的x m l 标签模式 被很多结构连接算法作为x m l 文件的表示 在 x m l 文件中通过一个三元组 d o c i d b e g i n e n d l e v e l 或将b e g i n e n d 拆开 称为四元组 来表示节点出现的位置 其中d o c l d 代表文件的唯一标识 b e g i n 和e n d 通过从d o c i d 的首个元素开始 然后针对元素开始和结束的数字编码来产 生 l e v e l 是针对d o c i d 文档的元素深度 a l i s t d l i s t 分别表示祖先 或双亲 元素列表 后裔 或孩子 元素列表 每个别表都按 d o c l d b e g i n 有序存储或 索引聚集存储 这样 如果节点 d i b i e 1 l 1 是节点 d 2 b 2 e 2 l 2 的祖先 当 且仅当d 1 d 2 b i b 2 且e 2 e 1 如果节点 m b l e 1 l i 是节点 d 2 b 2 e 2 蚴 的双亲 当且仅当d i d 2 8 1 8 2 e 2 e 1 且l i l 2 1 对于区间编码方案 有如下两条结论 将被后面的众多算法所引用 1 假设列表l i s t 按 d o c i d b e g i n 有序 任意给定一个节点 l i s t 则 节点r 在列表l i s t 中的所有后裔节点将是在列表l i s t 中紧接着节点r 的一串连 续节点 2 假设列表l i s t 按 d o c i d b e g i n 有序 任意给定一个节点r 则节点r 第1 7 页 第3 章结构连接算法 在列表中的第一个可能后裔节点是满足b e g i n y r b e g i n 的第一个节点 同时还必 须满足b e g i n r e n d 否则说明节点r 在列表l i s t 中不存在后裔节点 即在列 表l i s t 中满足b e g i n y r b e g i n 且b e g i n 取最小值的节点 并且节点r 在列表l i s t 中的所有后裔节点将是紧挨着第一个后裔节点的一串连续节点 直到条件 d o c i d r d o c l da n db e g i n r e n d 不成立为止 利用这种特点 区间编码可以在编码的基础上利用索引有序 完成针对节点 的全部索引 当然 也可以在l i s t 列表上关于 d o c l d b e g i n 建立诸如矿树聚 集索引等 这样对于一个给定的节点r 就可以利用 d o c i d b e g i n 作为索引关 键字 3 3 关系数据库的连接算法 对于x 礼索引技术的研究 由于应用的差剐也有所不同 这写应用领域包括 原生数据库 n a t i v ed a t a b a s e 关系数据库和面向对象数据库等 关系数据库 由于其发展的完备性 人们对其与x 札技术的结合进行了大量的工作 目前 o r a c l e 9 等数据库系统已经完全支持x m l 格式的数据 但由于x m l 是一种半结构 化的数据 在使用中显然会与传统数据有所区别 因而在该部分将讨论一些应用 于关系数据库的x 札结构连接算法 在关系数据库系统中 比较高效的连接算法 有排序归并连接 s o r t m e r g e j o i n s m j 算法 索引嵌套循环连接 i n d e x n e s t e d l o o pj o i n i n l j 算法和h a s h 连接算法 由于包含连接的特点是多谓词连接 且连接条件中既有等值连接又有非等值连接 而h a s h 连接算法只能进行等值连 接 因此它不适用于包含连接的运算 3 3 is i j 算法 目前商用关系数据库系统的s t o 算法一般都是先进行连接条件中的等值连 接操作 然后再对连接结果进行连接条件中的非等值操作 即将包含连接分两个 步骤来实现 例如 对于连接条件 第一步是按条件a d o c l d d d o c l d 进行等值 连接操作 结果是将关系表a l i s t 或d l i s t 中没有对应的d o c i d 列的取值分别划 分为m 个对应元组子集4 鸽 和d i d 2 d 其中元组子集4 和d l 中 的元组有相同的d o c l d 取值 且关系表a l i s t 和i l i s t 中没有对应d o c i d 取值的 第1 8 页 第3 章结构连接算法 元组已经被去掉 第二步就是对第一步等值连接的结果按4 蚴 d b e g i n d h e g i n a b e g i n 结束码谓词 即连接谓词 是d o c l l a d o c i d a n db e g i n a e n d i n l j 算法是一种按内表有序捧列的算法 对输入的结果来讲 即是按照d d o c i d 和d b e g i n 有序 第1 9 页 第3 章结构连接算法 3 4 直接归并结构连接算法 3 4 1m p m g j n c z h a n g 和j n a u g h t o n 嘲等提出的z h a n g 编码在区域编码领域得到了很大的 应用 本章节中的大部分算法也是基于z h a n g 编码的假设 因此下面我们将探讨 z h a n g 等人是如何根据其编码最初实现结构连接算法的 枝叶模式大多需要将查 询进行拆分 各自在x m l 文件中对应一系列的结果集 再根据查询需要将各个结 果集进行合并 为了解决结构关系的匹配子问题 z h a n g 等人提出了这种传统合 并连接算法的变种 多假设合并连接算法 m p m c j n 这种算法基于 d o c l d l e f t p o s r i g h t p o s l e v e l n u e 用以代表了x 札元素和字符串的取值 肝m g j n 算法的基本思想是 设参加连接的两个关系表a l i s t 和d l i s t 则对 外表a l i s t 中的第一个元组4 首先在内表d l i s t 中顺序搜索到可能与元组口i 进 行连接的第一个元组 称为扫描起始点 然后在内表d l i s t 中从扫描起始点开始 顺序扫描 对满足昭矗 q 朋d 条件的所有元组d 再判断是否满足连接条件 若满足则产生连接结果元组4 l 叫 继续对外表a l l s t 或内表o l i s t 中的元组连 接完毕 除第一次搜索外 该算法的每次搜索并不需要从内表o l i s t 的第一个元组开 始 只需要从上一次的扫描点开始搜索 注意 并不是从上一次扫描的结束点开 始本次搜索 这是因为一个元素节点可以是多个祖先元素节点的后裔 也就是说 好 j n 算法是一种支持嵌套标记的算法 例如 个b o o k 文档中嵌套了多层 s e c t i o n 元素节点 每一个s e c t i o n 元素节点中又直接嵌套了一个t i t l e 元素节 点 则一个t i t l e 元素节点可能是多个s