（计算机软件与理论专业论文）基于双拟关系的xml结构摘要索引技术的研究.pdf

基于双拟关系的x m l 结构摘要索弓i 技术的研究摘臻 论文题日：基于双拟关系的x m l 结构摘要索引技术的研究 专业；计算机软件与理论 硕士生：丁明镜 指导教师；郭清顺研究员 摘要 近年来，随着x m l 数据的受到越来越多应用开发者的欢迎，对x m l 的标 签树和标签图数据模型的检索处理成为了一个重要的研究课题。而x m l 索引是 有效检索x m l 的自然途径。 结构摘要作为一种重要的半结构数据索引技术，经常地用子x m l 索引中。 结构摘要在x m l 检索孛充当动态提取并自动维护的模式信息。从d a t a g u i d e s 开 始，已经在文献中出现了若干可应用于x m l 的结构摘要索引。 本文致力予建立一种支持分支路径表达式的自适应x m l 结构摘要索引。为 此，本文引入一种双拟关系以及基于双拟关系的结构摘要索引。在已经发表的结 构摘要索孳| 中，f & b 索弓| 通过从正反两个方向计算双拟关系的方法使索弓| 支持 分支路径表达式。但实验证明f & b 的空间效率不能满足应用的需要。本文从另 一个焦度作出了尝试，扩震双拟关系丽褥到一种双向双拟关系。根据双向双拟关 系划分节点得到的索引与f & b 索引同样地可以支持分支路径但在应用方式上更 为自由。通过在m 0 【) 一i n d e x 的基础上应用局部纯双向双拟关系可以得到一种支 持分支路径表达式的自适应x m l 结构摘要索引。研究表明该索引可以安全地检 索分支路径表达式并准确检索高频访问的分支路径表达式。本文在最惹为该索引 在应用中如何进步优化提供了建议。 关键字：结构摘要索引，x m l 索引，双拟，分支路径表达式 基于双拟关系的x m l 结构摘要索引技术的研究a b s t r a c t t i t l e ：t h er e s e a r c ho fx m ls t r u c t u r a ls u m m a r yt e c h n o l o g yb a s e do nb i s i m i l a f i t y m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：d i n gm i n g j i n g s u p e r v i s o r ：r e s e a r c h e rg u oq i n g s h u n a b s t r a c t i nt h er e c e n ty e a r s ，s i n c et h er a p i d l yi n c r e a s i n gp o p u l a r i t yo fx m lf o rd a t a r e p r e s e n t a t i o ni na p p l i c a t i o nd e v e l o p e r s ，q u e r yp r o c e s s i n go v e rd a t at h a tc o n f o r m st o al a b e l e d t r e eo rl a b e l e d g r a p hd a t am o d e lb e c a m ea ni m p o r t a n ti s s u e 。a n dx m l i n d e x i n gi st h en a t u r a la p p r o a c ht oe f f i c i e n t l yp r o c e s sx m lq u e r y s t r u c t u r a ls u m m a r y ，a sa ni m p o r t a n ts e m i s t r u c t u r a ld a t ai n d e x i n gt e c h n o l o g y ，i s f r e q u e n t l yu s e di nx m l d a t ai n d e x i n g i nx m lq u e r yp r o c e s s i n g , t h es t r u c t u r a l s u m m a r ys e r v e sa sd y n a m i ce x t r a c t e da u t o m a i n t a i n e ds c h e m ai n f o r m a t i o n 。a f t e r d a t a g u i d e s ，t h e r ea l ea l r e a d yan u m b e r so fs t r u c t u r a ls u m m a r yi n d e x e su s e di nx m l p u b l i s h e d t h et h e s i sc o n c e n t r a t e so nb u i l d i n ga l la d a p t i v e b r a n c h i n gp a t he x p r e s s i o n s u p p o r t i n gx m ls t r u c t u r a ls u m m a r y 。f o rt h i sr e a s o n ，t h et h e s i si m p o r t sab i n a r y r e l a t i o n - - b i s i m i l a r i t ya n ds t r u c t u r a ls u m m a r yi n d e xb a s e do nb i s i m i l a r i t y i nt h e p u b l i s h e ds t r u c t r a ls u m m a r yi n d e x e s ，f & bi n d e xa c h i e v e sb r a n c h i n gp a t hc o v e t i n gb y c o m p u t i n gb i s i m i l a r i t yf o r w a r d sa n db a c k w a r d s b u tt h ee x p e r i m e n ts h o w st h a tt h e s p a c e c o s to ff & bi n d e xi st o ol a r g ef o ra p p l i c a t i o n 。t h et h e s i s 缄甜a n o t h e rw a y b y e x t e n d i n gb i s i m i l a r i t yt oat w o s i d e sb i s i m i l a r i t y t h ei n d e xb u i l tb yp a r t i t i o nb a s e d o nt h i st w o s i d e sb i s i m i l a r i t yc o u l da l s os u r p p o r tb r a n c h i n g p a t he x p r e s s i o n b u tt h e r e a r ev a r i o u sw a y so fu s i n gt h i sb i n a r yr e l a t i o n b ya d o p t i n gl o c a lt w o - s i d e sb i s i m i l a r i t y o nm 承) 一i n d e xc o u l dg e n e r a t ea na d a p t i v eb r a n c h i n gp a t he x p r e s s i o ns u p p o r t i n gx m l s t r u c t r a ls u m m a r y t h er e s e a r c hs h o w st h a tt h i si n d e xc a np r o c e s sa l lb r a n c h i n gp a t h e x p r e s s i o nq u e r ys a f e l ya n dp r o c e s sf r e q u e n t l yu s e db r a n c h i n gp a t he x p r e s s i o nq u e r y p r i c e l y t h e s i sa l s op r o v i d e ss u g g e s t i o nf o rf u r t h e ri m p r o v i n gs p a c ep e r f o r m a n c eo f 2 基于双拟关系的x m l 结构摘要索引技术的研究a b s t r a c t t h i si n d e xi na p p l i c a t i o n k e yw o r d s ：s t r u c t u r a ls u m m a r yi n d e x i n g , x m li n d e x i n g , b i s i m i l a r i t y ，b r a n c h i n g p a t he x p r e s s i o n 3 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明粤l 用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：j 谛诲幻 日期：沁寺r 年l ，月j e i 学位论文使用授权声明 本人完全了解中出大学有关保露、使用学位论文的规定，郎：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：j 托w 哟 导师签名：却荔。恢 日期：沁? 年t 胃y f 囡f t 期：h 薛；，月le l 基于双拟关系的x m l 结构摘要索引技术的研究第1 章引言 1 1 课题背景和意义 第1 章引言 x m l 结构摘要索引的研究是在两个背景下产生的。首先是x m l 应用的普及。 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 s d 文件和d t d 文件。 针对一个具体的应用而言，模式往往是相对稳定的，而数据变化比较频繁。可以 想象，针对这类x m l 数据的检索技术往往强烈地依赖于模式，一般称为模式相 关的。与之相对是另一类表示半结构数据的x m l 文档。半结构数据中，数据间 具有与结构数据类似的关系，往往可以用数据图来表示。与结构数据的差别在于 半结构化数据很难找到一个模式或者模式频繁变化需要很大的维护开销。半结构 数据的检索中，模式不再作为输入的一步分出现。半结构数据的出现体现出一种 趋势，开发人员和用户希望把精力投入到数据的管理上而非模式的维护上。 如同上文所说的x m l 的d t d 或x s d 同样，传统的关系和面向对象数据库 管理系统往往强制要求数据关联到一个显示定义的模式上。模式除了定义了数据 结构以外还至少有两个重要的作用： 1 一个模式，无论是关系数据库中的表还是面向对象数据库中的类层次都使 用户明确了数据库的结构。数据库的使用者或管理员依赖数据库的模式编写 查询语句。 2 检索处理器依赖模式来规划检索的计算。 6 基于双拟关系的x m l 结构摘要索引技术的研究第1 章弓l 言 在没有模式的帮助下，两个工作的难度都明显地提高了。首先，使用者很难 给出一个意义明确的查询请求。其次，检索处理器由于不清楚数据库的结构会陷 入低效的遍历搜索。对于小规模的数据尚可人工地遍历，但对于大型应用这显然 是不能满足需要的。半结构数据对模式的需求使结构摘要索引技术得到发展。结 构摘要索引是一种动态提取并自动维护数据模式信息的索引技术，它同时满足两 个方面的需要。一方面，它满足半结构数据对模式信息的需要。另一方面它满足 了开发人员需要集中于数据本身而不是元数据更新的需要。 分支路径表达式是一种灵活而且特性丰富的表达式规则。由于b i s i m i l a r i t y 关 系是一种描述节点祖先相似特征的等价关系，依赖于这一二元关系建立的索引大 多只能满足向前检索的需要。而在逻辑层面的索引中，f & b 通过从正反两个方 向计算b i s i m i l a r i t y 关系来覆盖分支路径表达式，但实验表明f & b 的空间效率不 能满足应用的。因此，本文致力于寻找一种不同于f & b 的支持分支路径查询的 结构摘要索引。 1 2 国内外研究现状 x m l 的检索是指在一个x m l 文档中，对指定的路径表达式找出文档中匹配 这个表达式的元素。一种最直观的检索就是深度优先搜索文档的d o m 树，顺序 的检验所有的节点是否匹配表达式，检索的结果就是所有匹配的节点。对于大规 模数据这样的搜索无论是时间开销还是空间开销都是不能接受的。为了解决检索 的效率问题，x m l 数据库要创建索引来辅助检索。半结构数据的索引方法大体 可以分为两大类，一种是结构索引，一种是节点记录索引。 结构索引的致力于通过合并节点而缩小的图的规模。结构索引的通常要基于 一种等价关系，根据这种等价关系将原节点集划分成数个割集，将每个割集合并 - 成一个索引节点来缩小图的规模。结构索引实质上是在运行时从原数据提取出一 个模式，并自动地维护这个模式。通过缩小图的规模，结构摘要索引可以减小数 据的存储空间以及检索时的搜索规模。 节点记录索引尝试通过改变数据的管理方式来避免检索中对数据图的遍历。 节点记录索引常常将原文档中的数据单元如文档中的元素、属性、标签等作为一 条记录保存。在节点记录索引中，数据的结构信息可能作为一种辅助信息保存在 7 基于双拟关系的x m l 结构摘要索引技术的研究第1 章引言 记录中。 本文重点研究结构摘要索引。以下简单介绍结构摘要索引： 最早的结构摘要索引是出现在s t a n f o r d 大学l o r e 项目中的d a t a g u i d e s n 。 d a t a g u i d e s 通过归并相同路径的方法最终将n f a 转换为d f a 。但在d a t a g u i d e s 发表时，对结构摘要索引的形式描述和论证还不够充分。 随后 2 1 文中发表了1 - i n d e x 和t - i n d e x l 2 】索引。该文中定义的精化关系， b i s i m i l a r i t y 2 1 关系以及查询的安全性和准确性的概念，成为之后许多结构摘要索 引形式描述和论证的重要基础。 2 0 0 2 年， 3 1 文中介绍了a ( k ) i n d e x 3 】索引，在结构摘要索引上提出了关注频 繁访问路径而放弃过长路径的思想。该文定义的局部的k - b i s i m i l a r i t y 关系很大程 度上提高了结构摘要索引的空间表现。 同年发表的a p e x 4 】索引用类似于寄存器的思想建立了一种使用哈希树缓存 频繁访问路径查询结构的结构摘要索引。a p e x 将自适应的思想引入了结构摘要 索引的研究中。 同年的另一篇文献中介绍了一种通过反复计算b i s i m i l a r i t y 得到的覆盖分支路 径表达式的最小结构- f & b 【5 1 索引。 2 0 0 3 年发表了d ( k ) i n d e x l 7 1 索引。d ( k ) i n d e x 吸收了a p e x 的自适应思想，建 立了一种基于k b i s i m i l a r i t y 的结构摘要索引。在介绍d ( k ) i n d e x 理论基础中，给 出了k - b i s i m i l a r i t y 与检索准确性的关系。这个理论使结构摘要索引中可以动态调 整局部相似度同时也减少了无谓的细分。 在d ( k ) i n d e x 的基础上，m ( k ) i n d e x 8 1 与d ( k ) i n d e x 同样是基于k - b i s i m i l a r i t y 的自适应结构摘要索引，但m ( k ) - i n d e x 使用了不同的构造方法。m ( k ) - i n d e x 在两 方面更具优势。首先，在自适应方面，m ( k ) i n d e x 与频繁访问路径集直接关联而 使局部相似度的分配更为合理。其次，m ( k ) i n d e x 在节点细化中将无关节点剔除 避免了过度细化。同文中发表的m 宰( k ) - i n d e x 【8 】则通过保存节点细化的历史保证 了节点细化计算过程中不会出现过度细分，进一步地消除了过度细化。 2 0 0 5 年发表的d i s k b a s e df & b 1 9 】提出基于磁盘存储的f & b ，通过聚合属性和 序号对等技术优化了f & b 。 8 基于双拟关系的x m l 结构摘要索引技术的研究 第1 章引言 1 3 本文在研究方面的工作 本文致力于基于b i s i m i l a r i t y 结构摘要索引技术的研究。在研究中做了如下 工作： 1 定义了k ，i b i s i m i l a r i t y 二元关系，并证明了k ，i b i s i m i l a r i t y 与局部检索准 确性的关系。 2 基于k ，i b i s i m i l a r i t y 建立了m ( k ，i ) i n d e x 索引。并证明了分支路径表达式 在该索引上的局部检索准确性。 3 给出了m ( k ，i ) i n d e x 的自适应构造方法。并讨论了m ( k ，i ) - i n d e x 在具体应 用中进一步优化的方法。 4 给出了一种使用辅助结构记录细分过程的中间节点以避免m ( k ，i ) i n d e x 建立过程中的过分细分现象的m 木( k ，i ) i n d e x 索引。 1 4 本文的组织结构 本文分为6 章： 第1 章，引言。主要介绍了课题的背景意义以及国内外的研究现状和本文的 主要工作。 第2 章，x m l 文档的模型。介绍了使用有根有标签有向图模型表示x m l 的方法。简单地分析了边标签和节点标签的不同。 第3 章，路径表达式。介绍了x m l 检索语言的核心部分，路径表达式。着 重介绍了分支路径表达式。 第4 章，结构摘要索引。介绍了结构摘要索引的基本概念，以及d a t a g u i d e s ， 1 - i n d e x ，a ( k ) i n d e x ，d ( k ) - i n d e x ，m ( k ) - i n d e x 和f & b 等重要的结构摘要索引。 第5 章， m ( k ，i ) - i n d e x 。本文的核心内容。介绍了扩展k - b i s i m i l a r i t y 以表达 正反两个方向相似的k ，i b i s i m i l a r i t y 。也介绍了基于k ，i b i s i m i l a r i t y 的自适应结构 摘要索引m ( k ，i ) - i n d e x 。讨论了它的检索特性和构造算法。 第6 章，总结和展望。对本文的研究工作作出总结，指出进一步的研究方向。 9 基于双拟关系的x m l 结构摘要索引技术的研究第2 章x m l 文档的模型 第2 章x m l 文档的模型 2 1 建立x m l 模型考虑的因素 在这一章中将讨论如何使用标签图模型描述x m l 的文档，这是下文讨论 x m l 检索的基础。x m l 由可嵌套的有层次的元素组成。一个元素包含标签，属 性以及嵌套的子元素或文本，在文档当中元素从一个起始标签开始到一个结束标 签截止。目前在不同领域已有多种不同的x m l 模型，这些x m l 的模型几乎都 基于一个公用的结构有序树。较为粗糙的模型会只表示出文档中的文档结点和 元素。以文档节点为根，其余的每个节点对应于一个文档中的元素，用边表示元 素间的父子关系，用兄弟节点的左右顺序表示同一元素子元素间的先后顺序来建 立一棵有序树。更为细致的模型中，属性和文本也各作为一类节点，元素与属性 的包含关系，元素属性的顺序关系也各用两类边类表示。d o m 树就是这类模型 的典型，在一般的应用中d o m 模型已经足够了。 考虑本文所要讨论的问题，着重于元素的检索，为了唯一地确定一个节点， 我们假定文档中每个元素都有一个唯一的标示称为o l d ，它的值是一个正整数。 在插入元素时，元素也同样被分配这样一个标示。在实际应用当中要么要求系统 输入的文档中每个元素都包含这样一个属性，要么在运行时进行一些预处理为它 们分配一个，相对于建立索引所需的时间开销而言这个预处理带来的开销几乎是 可以忽略的。另一个本文关注的x m l 的特性就是引用。引用是一种常见的数据 关系，数据引用可以减少数据冗余，提高数据的可维护性，这与其他领域中引用 机制的作用并没有什么不同。在x m l 应用中引用有多种不同的方式，如实体引 用，x l i n k 标准或具体应用定义i d i d r e f 。在引用的逻辑意义相同的情况下， 使用不同的引用形式并不会影响本文所讨论的索引或检索技术，针对不同的引用 形式调整索引并不会带来太大的工作量。未了讨论的一致性，我们在讨论中使用 如下的引用方式：本文中将只讨论元素引用元素而不讨论属性引用或实体引用 等。引用通过i d i d r e f 方式实现。由于前面已经假设每个元素都有了唯一标示， 一个元素引用另一个元素只需要给出索被引用元素的o i d 。一下是一个引用的例 子，这个例子演示电影元素中引用了一个导演元素： 1 0 基于双拟关系的x m l 结构摘要索引技术的研究第2 章x m l 文档的模型 d i r e c t o r a 在例子中， 称为引用元素，它并没有实际的意义仅仅 表示引用另一个元素，引用元素本身没有o i d 。在建立的模型中，用引用边来表 示引用关系。 2 2x m l 的边标签图模型 以下描述了本文使用的x m l 文档的数据模型： x m l 文档的数据图：x m l 文档用有根有标签有向图，表示 为：g ，e ，r o o t ，r ，t ，彳) ，其中： 丁为标签集，包含文档中全部的标签，其中元素为字符串。 y 为数据图中的节点集合，其中每项代表一个文档中的非引用元素。 为数据图中的有向边集。 e e 如果 ，。e va e v al a b e le t 且在文档中心表示的元素嵌套表示的有l a b e l 标签的 元素。 r o o t 表示数据图的根节点。r o o t e v 且对应x m l 文档中的文档元素。为了 讨论地方便假设r o o t 的o l d 总是o 。 尺为数据图中的引用边， e r 如果v 。e vav 6 矿al a b e le t ， 在文档中，v a 对应的元素嵌套了一个标签为l a b e l 的引用元素，该元素引用了 对应的元素。 a 为元素的属性集合，用三元组表示，v ，p ，v a l u e ) a 如果v e v ，且v 对应 节点有属性p ，值为v a l u e 。 定义2 ：下文讨论中使用的其他表示： o i d ( v ) ：p e - - b v n 的映射，表示节点，的d 谢。即o i d ( ) = i d o ，其 1 1 基于双拟关系的x m l 结构摘要索引技术的研究 第2 章x m l 文档的模型 中o i d o a t o r 。 l a b e l ( e ) 是一个e ur _ r 的映射，表示边e 的标签。即 l a b e l ( ) = l a b e l ，其中匕e va e v al a b e le t 。 若有 e e v e r ，匕e v v be v al a b e l t 则， s t a r t ( ) = v 。 ， e n d ( ) = e e - ，口- 坚屿d ，6 ， 地表 e r 奢1 ，口鲤，6 。 示嵌套 边和引用边 e e v e r 墨 ，。鲤，6 若有属性，p ，v a l u e ) e a 则，p = v a l u e 。 图二表示一个数据图的例子： m o v i e a j o h nf a l c o n c e r nb u f f y i m e o nc a l e r a l u n d o r 1 2 那么统 为 基于双拟关系的x m l 结构摘要索引技术的研究第2 章x m l 文档的模型 ( b ) 性质1 ：一个x m l 文档的数据图g ( 圪，e o ，r o o t 。，r o ，t o ，a 。) 在忽略引用边的情 况下g ( 圪，e o ，r o o t o ，t o ，a 。) 是一棵以r o o t o 为根的有标签无序树。为讨论方便称 g 是g 的退化树。 这个显而易见的性质说明x m l 文档的数据图可以通过一般的树的遍历算法 遍历全部的节点，这是x m l 数据图检索的基础。另外注意到我们没有在模型中 表示兄弟节点的次序，这意味着在此模型上讨论的索引和检索方法是不保序的。 2 3 节点标签模型和边标签模型 最后需要说明在x m l 数据的建模中标签的处理可能对索引带来的差别。具 体地说是数据图如何关联标签会给索引带来差别。在本文中使用标签与边关联的 方式建立数据图，在一些相关文献中使用节点与标签关联的模型，它们的节点与 边可以如下的描述： v 为数据图中的节点集合，其中每项代表一个文档中的非引用元素。其中 yi f fo i de n & f z 且原文档中存在一个标签为t ，标示为o i d 的元 1 3 p 一 基于双拟关系的x m l 结构摘要索引技术的研究 第2 章x m l 文档的模型 素。 e 为数据图中的有向边集。 e e 如果y 。e v v b v 且在文档中屹对 应元素嵌套屹对应的元素。 在这样的模型上，每个节点都对应唯一的标签，可以用l a b e l ( v ) 表示，的标签。 在本文的一些参考文献中可以看到标签分裂索引，这是一种将相同标签的节点归 为一个等价类的结构摘要索引，这种索引经常用于其他索引建立算法的初始状 态。 关于模式和数据结构的观念会让节点标签模型看起来更自然。例如： 这样的元素就很容让人想象到一个标注着”d i r e c t o r 标签的节点。但作为一个 用于半结构数据索引研究的基础模型来说，它对数据间关系带来了额外的限制。 在这样的模型下要求一个节点的所有输入边都必须具有相同的标签，而在实际应 用中这可能是不必要的。本文中引用的一些索引或索引相关的性质最初是在这样 的环境下建立和描述的，在本文中它们在边标签的模型下被重新表述了，部分命 题重新地证明了。一些索引的建立和维护算法上也是依赖于节点标签的模型的，“ 尤其是前面所说的标签分裂图经常用于索引的建立算法，在本文中它们都被其它 索引替代了。关于这一部分的工作都在“结构摘要索引”一章中。 1 4 基于双拟关系的x m l 结构摘要索引技术的研究 第3 章路径表达式 第3 章路径表达式 随着x m l 应用的推广，近年来产生了多种用x m l 检索语言。路径表达式 是各种x m l 检索语言的基本构成块。它实际是用于描述一个模式的字符串，不 同规范的路径表达式具有不同的文法以及用于支持不同的元素间关系。简单路径 是各种路径表达式的共同基础。简单表达式用于描述一个最基本的模式，我们称 为标签路径。以下的定义是基于检索不区分子节点和引用的子节点的假设下的。 定义3 1 ： 标签路径是一个用“分隔的标签序列，对于一个x m l 文档的数据图 g ，e ，r o o t ，r ，t ) ，l o 1 。是图g 的一条标签路径，其中，l21 ，z fe t ，i e i l n 】。 数据路径是一个用“”分隔的节点序列，对于一个个x m l 文档的数据图 g ，e ，r o o t ，r ，z ) ，d o 彳1 五。是图 g的一条数据路径，其中 d fe va j d f “vf = 月) ，l o , i c o ，l 】。 定义3 2 ： 称图g 中一条数据路径d 。彳r 彳。匹配标签路径乇r 。如果有 ，d 们山d oad f 一1 噍，i e 1 , n l 。 路径表达式形式上是一些由分隔符分隔的标签。最简单的路径表达式只有一 种用于表示父子关系的分隔符号“ ，例如“m o v i e d i r e c t o r 表示电影的导演。 _ - 个简单路径表达式可以用于描述一个标签路径。例如l = l o i ，l ：l 。表示标签 路径毛- r 。一个节点d 。满足路径表达式如果存在数据路径d 。彳，彳：彳。匹配 标签路径三。分支路径表达式在简单路径表达式的基础上，加入了一些新的分隔 符号以提供更多的查询功能。如果，露m 被一下分隔符分隔： 同简单路径表达式相同，表示+ 。是，l ；的子节点或吃引用n m 。 1 6 基于双拟关系的x m l 结构摘要索引技术的研究第3 章路径表达式 表示咒m 是n ，的后代节点。特别地，在“ 出现在表达是首时表示根节点 的后代节点也就是任意节点。 表示n 是n ，的父节点或n 引用n ，即与“ 相反的关系。 表示他+ 。是n 。的祖先节点。即与“相反的关系。 一般称“ 、“为向前分隔符，“ 、“ 为向后分隔符。由于本文讨论的 检索中不区分引用和父子关系，所以在这里向前和向后分隔符中都对应的包含了 引用和被引用关系。 在节点分隔以外，“”符号在路径表达式中若用于分隔一个节点和一个属性 则表示查找该节点的属性，例如，d i r e c t o r , n a m e 表示d i r e c t o r 元素的n a m e 属性。 另一种使用“的场合是查找一个节点中的文本，例如以下的表达式表示查找 一个导演的国籍“d i r e c t o r c o u n t r y t e x t ”。 除去节点分隔符和元素分隔符以外，分支路径表达式还提供了另外一类条件 分支分隔符。“【】”用于表示一个分支条件。其中包含的内容是一个布尔表达式。 条件分支的作用接近于s q l 中的“w h e r e 字句。例如，我们可以查询一个电影 数据库中美国导演指导的电影“m o v i e d i r e c t o r c o u n t r y t e x t = ”u s a t i t l e ”。条 件分支表达式很大程度上提高了路径表达式的实用性。显然地，为了条件查询能 实际的工作，必须提供一些常用的布尔运算符以及一些用于构造条件表达式的函 数。我们在此只定义用于表示与的“a n d ”表示或关系的“o r 和表示非关系的 “n o t 。其余的运算符或函数在使用时在具体解释。这些运算和函数的定义不会 影响到索引和检索的算法。 定义3 3 ： 条件分支表达式的文法： l a b e l s e p 一l i i l a b e l p a t he x p r - 1 a b e l il a b e ll a b l e s e pl a b l e p a t he x p r b o o l e ve x p r 呻t r u el 丘西eil a b e i s e pl a b e l p a t h 2 a b l e l = s t r i n g b o o i e x p r 一 b o o l e v e x p ri b o o l e v e x p ra n db o o l p a t h e x p ri b o o l e v e x p r o rb o o l p a t he x pr ln o tb o o l p a t he x p r 1 7 基于双拟关系的x m l 堕塑垫壅鲞! ! 垫查丝婴窒 笙! 兰堕丝耋垄茎 b l a b e l p a t he x p r _ l a b e l p a t he x p ril a b e l p a t he x p r b o o le x p r l a b e l s e p b l a b e l p a t he x p r b p a t he x p r r o o ti b l a b e l p a t he x p rir o o t b l a b e l p a t he x p r 基于双拟关系的x m l 结构摘要索引技术的研究第4 章结构摘要索引 第4 章结构摘要索引 4 1 结构摘要索引的简介 在x m l 索引的简介中已经介绍过，结构摘要索引是一种通过合并相似节点 以减少图规模的索引方法。对于一个源文档中的数据图g ，是一个索引算法， 则图g 的索引数据图表示为i ( g ) 。由于基于结构摘要索引合并的思想，源图中 节点与索引图节点往往具有一种多对一关系，对于原图中节点s 和索引算法j 用 ，( s ) 表示s 在索引图中对应的节点，相对地，对于索引图中节点d ，和索引算法 j 用e x t e n t ， ) 表示节点d 在源图中对应的节点集，称为d 的扩展集，在不引起混 乱的情况下简单记做e x t e n t ( d ) 。本文中讨论的结构摘要索引至少要满足以下的两 个性质： 性质4 1 ： 对于一个数据图g 和g 的索引图，f g ) ，v 是g 中的节点集， 巧( g ) = 似。，d 。，d 。)是吖回 中所有 的 索引 节点。 则 e x t e n t ( d o ) ue x t e n t ( d 1 ) u ue x t e n t ( d 。) y 。 性质4 2 ： 对于数据图g 的索引图，中两个索引节点d 0 、d 。若d 。一d 。当且仅当存在 s o 、s 1 其中s oe e x t e n t ( d o ) ，s l e x t e n t ( d 1 ) 且一5 l 。 一个索引图是否能满足性质2 是由索引图的创建算法决定的。如果一个索引 图是按照以下的算法来建立边的，那么这个索引图一定满足以上性质： b u i l d _ e d g e s ( i ( g ) ) f o r e a c hd ji ni ( g ) d o 基于双拟关系的x m l 结构摘要索引技术的研究 第4 章结构摘要索引 f o r e a c hd ，i ni ( g ) d o f o r e a c h s i i ne x t e n t ( d j ) d o f o r e a c hs j i n e x t e n d ( di 、) d o i f 瓯当s ，a n d d o e s n th a v ed f 旦d t h e n c r e a t ee d g e e n di f e n df o r e a c h e n df o r e a c h e n df o r e a c h e n df o r e a c h e n do fb u i l d e d g e s 以下关于x m l 索引安全性和正确性的讨论中可以看到这两个性质是用于保 证一个索引基本的可用性的。这个粗糙的边建立算法是本文所讨论的其它索引建 立算法的基础。这个算法在这里为了展示可以通过边的建立来保证前面讨论的基 本性质，在实际应用中，这个算法可以远比这里的地高效的。 在x m l 索引中，使用安全性和正确性1 2 1 来评价一个索引对表达式的是否有 效地检索。 定义4 1 - 索引的安全性：一个索引算法，是安全的如果对于任意的数据图g 中的任何 标签路径，一l o f r 。o 芑0 ) ，若有节点s 满足，则在图g 的索引图吖q 中必须 存在一个节点d ，d 满足，_ s e e x t e n t ( d ) 。 定义4 2 ： 索引的准确性：一个索引算法，是准确的如果这个索引算法是安全的且对于 任意的数据图g 中的任何标签路径，= 1 0 厶厶0 苫0 ) ，若有节点s 其中删满足 标签路径z ，则j 也满足标签路径z 。 2 1 基于双拟关系的x m l 结构摘要索引技术的研究第4 章结构摘要索引 索引的安全性实际上保证了对于任何路径表达式的在索引图上的检索结果 必然包含在源数据图上的检索结果。若索引是准确的则对任何表达式在索引图上 的搜索结果与在源数据图上的搜索结果是完全相同的。一个结构索引为了满足检 索的需要至少要满足安全性。 满足性质4 1 和性质4 - 2 的结构摘要索引都是安全的。这可以很容地通过递 归来证明。首先，对于根节点，根节点只能满足空路径而索引图中的根结点同样 是满足空路径的。对于任何一条路径z l o - f 。o 1 ) ，若原数据图中有节点5 满 足标签路径z 。s 。至少有一个父节点s 柚满足路径，= l o 厶_ 。若假设有索引节 点d 。- l ，d 一其中j e x t e n t ( d 。- 1 ) ，s 。e x t e n t ( d 。) 且d “满足标签路径z 。则由 性质4 - 2 可知有d 。q 上d 。，所以d 。满足，。由此可知该索引是安全的。 以下介绍于本文有关的第一种结构摘要索引d a t a g u i d e s 。 4 2 d a t a g u i d e s 和s t r o n gd a t a g u i d e s 结构摘要索引的最初形式是s t a n f o r d 大学l o r e 项目中的d a t a g u i d e s l l 】索引。 d a t a g u i d e s 用相当简单的思想尝试为x m l 文档建立一种索引用于代替传统文档 中的模式。通过减少相同标签路径的重复出现，以减少路径表达式的计算时间。 定义4 3 ： 原数据图g 中的任何标签路径z 在索引数据图中有且只有一条数据路径p 与 其匹配，则这个索引d a t a g u i d e s 。 d a t a g u i d e s 的定义无法唯一地为一个x m l 文档确定一个索引而更接近于定 义了一种索引性质。将源数据图建立d a t a g u i d e s 索引等价于将一个不确定有限自 动机( n f a ) 转化为确定有限自动机( d f a ) 。这个性质体现的d a t a g u i d e s 的设计 意图，在d a t a g u i d e s 上查找一个长度为n 标签路径的时间至多为万。这个性质同 时确定了一个建立d a t a g u i d e s 索引的算法。虽然同一源数据的d a t a g u i d e s 有多个， 但由这一性质说明这些d a t a g u i d e s 是等价确定有限自动机，根据根据状态最小化 算法，可以转化为一个最小化的状态自动机。最小化d a t a g u i d e s 可以很好的压缩 2 2 基于双拟关系的x m l 结构摘要索引技术的研究第4 章结构摘要索引 空间，但难于增量维护。 在这里需要注意到d a t a g u i d e s 在含有引用的数据图上它不是一个完全的节点 合并索引。索引中的所有节点d o ，d 1 ，d 。的扩展集e x t e n t ( d o ) ，e x t e n t ( d 1 ) ， e x t e n t ( d 。) 不是构成原图节点集的一个划分，而是原图节点集的一个覆盖。在这 里特别指出这一点是因为它与本文讨论的其他索引是不同的。 同文提出的s t r o n gd a t a g u i d e s i l 】一类条件更强的d a t a g u i d e s 。s t r o n gd a t a g u i d e s 的意图是在索引节点上可以有效地缓存从该节点出发特定路径的查询结果。 定义4 - 4 ： ，是数据图g 中的一个标签路径，5 是数据图中一个节点，用t u ) 表示从s 出发经过路径z 所能到达的所有节点，称为z 在s 上的目标集。若有标签路径m 与z 在s 上有相同的目标集，称m 与z 在j 上是等价的，用l ，( f ) 表示z 在s 上所 有的等价路径，l ，1 5 f ) = ，li l ( m ) = 瓦( f ) ) 。对于一个索引算法，索引节点d ， s e e x t e n t ( d ) ，若对于任何标签路径z 有l s u ) = l d p ) 则称d 是s 的s t r o n g d a t a g u i d e s t r o n gd a t a g u i d e s 具有这样的性质：在s t r o n gd a t a g u i d e s 的一个节点上对记 录一条