基于关键字的XML数据Top_K近似查询方法研究

I 摘 要 随着网络技术的飞速发展， 益成为 数据表达和转换的标准，并在电子商务、金融等很多方面得到了广泛的应用。面对网络中呈指数级增长的 档，对 据的检索吸引了很多研究者们的眼光，其中关键字查询由于其查询的友好性得到了很大的关注。 本文首先分析了现有的关键字查询方法的优缺点，发现现有的关键字查询方法大都使用 “与”的语义，返回包 含全部关键字的结果。而对 于查询用户来说，有时候包含部分查询关键字的结果同样很有意义， 构查询由于了解到 档的结构特点能够较为准确的捕捉用户的查询意图而具有较高的查询精确率。若将 构查询的一些相关知识与关键字查询方法相结合会具有很高的现实意义。 为此，本文将面向对象的思想和松弛的查询引入到关键字查询中，提出了一种通过关键字和 档结构信息判定用户查询需求的方法。此方法首先考虑到 档的结构特点，引入对象化的概念，通过将 档划分成彼此具有某种关联的不同的对象体； 然后判定用户输入关键字的数目和在 档的位置返回相应的结果对象体，并通过相似对象体判定的方法得到子树相似阈值小于 U 的相似结果对象体集合； 最后在这些相似对象体集合上构建结构查询进行相应的小枝查询。 其次， 在查询结果打分阶段，我们采用内容查询打分和结构内容查询打分相结合的方式对结果进行打分，首先结合松弛查询的结构特点对结构查询进行 相应的打分，然后以属性- 元素作为处理单元，将用户的属性偏好考虑进去，得出元素在内容查询中的相关分数，最后结合两者的分数得出最后的打分结果。 在此基础上，本文提出了一种基于语义和结构松弛的 键字查询方法框架，通过引入松弛结构查询，使得返回的结果不但包括全部匹配结果，同样包括部分匹配和近似匹配结果，并通过有效的排序方法得出与用户需求最相关的 查询结果。最后将提出的方法与现有的 键字查询方法 行实验对比，实验结果表明此方法能够较好的捕捉用户的查询意图，在查询有效性和效率方面都具有很大的改进。 关键词： 键字；对象；松弛查询；用户偏好 of is of It in so ML in of ML a of of of of to it to of of ML it to ML of to a of by ML ML of ML It of of ML to of At in of we of to of of we as s of in At we of of On a on In it it to we do by us ML by us a in 目 录 摘 要 . 绪论 . 1 题背景及意义 . 1 询的国内外研究现状 . 1 构查询 . 1 键字查询 . 2 文的主要研究内容 . 3 文的组织框架 . 4 2 据库查询理论 . 5 基本概念 . 5 介 . 5 语义约束 . 6 询方式 . 7 据模型 . 7 析器 . 7 询语言 . 7 询语言 . 8 键字查询方式 . 9 引技术 . 10 缀编码 . 10 间编码 . 12 章小结 . 14 3 基于语义和结构松弛的 键字近似查询 . 15 究动机及问题描述 . 15 究动机 . 15 题描述 . 15 似对象体 . 17 象化 . 17 似对象体的判定 . 17 据关键字和 构信息推断用户查询的结果对象体算法 . 21 弛结构查询 . 22 弛方法 . 23 V 储结构 . 25 分方式 . 25 果排序方法 . 28 关索引 . 30 章小结 . 30 4 实验测评 . 32 验平台及测试数据集 . 32 验方法 . 33 效性测试实验 . 33 确度和召回率测试 . 33 . 37 率测试实验 . 38 章小结 . 38 5 总结与展望 . 39 参考文献 . 40 攻读硕士期间发表学术论文情况 . 43 致 谢 . 44 1 1 绪论 题背景及意义 一种具有自描述， 半结构化数据特点的可扩展标记语言。现已成为互联网上数据表示，存储和交换的标准之一。它在数字图书馆，电子商务与 务等领域作为数据的表示形式和交换形式。随着网络应用的快速发展，符合 范的数据（ 据）在当前的信息社会已大量的出现，如何对 据进行有效的存储管理和查询引起研究者们越来越多的关注。 询可分为结构查询和关键字查询。对于结构查询，其查询语言的使用者需要对相关的语法机制进行学习，此外，还需了解 档的结构才能写出较为准确的查询语句。 由于结构化查询考虑到文档的结构信息因而能够较为准确的捕捉用户的查询意图。如何快速地确定任意两个元素间的结构关系是实现此类查询模式的关键。对于关键字查询，用户不需要了解 关的查询语言和内部结构，直接输入关键字便可进行相关的查询。对于关键字查询，最近的研究大多利用 据的特征，快速获得所有满足关键字组成语义的最紧致 段的问题，研究者们一般将其转化为求解输入关键字的 1,2的问题。此方法在获取所有包含给定关键字的 段后的一个重要问题就是 段相似程度的计算，在这一过程中需要考虑其结构上的相似性。 但是此类算法并不能够考虑 内部结构问题，也不能够解决关键字的部分匹配问题。 询的国内外研究现状 构查询 在 构查询中，研究者们提出了很多的查询语言，例如， , 和 等等。其中最常用的两种语言，即 者是后者的基石。对于 询来说，首先要解决的是 问题。在 构查询处理中，目前大多的文献是专注于 达式的处理。 从 询的执行策略角度来看可分为以下三种： （ 1）基于导航的 询执行策略。 档采用树状数据模型和路径表达式语法，采用树遍历方法模型进行遍历，并根据 路径在 中进行导航，即在查询处理中按查询轴一步步地导航到最终结果。 由于对 档的导航遍历很费时，因而在 档上通过建立树状结构的概要索引，对元素进行聚集，并遍历概要索引来得出查询结果。由于此方法实行了聚集，容易忽略了某些元素信息，使得有时在概要索引上的查询结果可能并不太准确。 2 （ 2）基于连接的 询执行策略，分为结构连接和小枝连接。通过此策略可以将一个 询分解成为多个结构连接进行查询或者多个小枝连接进行查询，最后将连接结果组装得到最后的查询结果。 （ 3）将基于导航的策略和基于连接的策略混合起来。也是将一个查询分为若干个子查询，子查询可能采用导航的策略计算，而子查询之间则进行连接7。 目前，在 构查询中研究的热点问题是 询模式，它的主旨就是搜索得到满足树状结构的查询模式的结果。对 询模式通行的求解算法大多采取如下步骤： （ 1）将 询模式分解为二元结构关系（父亲 先关系，子孙关系等） ； （ 2）利用结构连接的算法（ 据库中寻找所有满足上述结构关系的节点集合； （ 3）将得到的中间结果合并为满足全部结构关系的最终结果8。 为提高 法的性能，可以通过提高结构连接操作的性能，增加分解粒度，和流式处理等实现。 键字查询 在 键字查询中，研究者们提出了多种包含全部关键字的紧致片段的查询语义， 2， 9， 5等。其中 到了广泛的关注， 在文献 1中提出了 定义， 对于给定的一系列 n 个关键字 k1, 并且相对于该子树中其他包含全部关键字的节点位于该子树的最低层， 并提出了三种计算 算法： 法， 法和 法1。 基于 研究者们提出了 1， 5， 3， ，0， 8等方法来解决 键字搜索。 持扩展的关键字搜索而且集中在结果的语义和排名。它采用有意义地相关节点的语义来回答关键字查询。采用的语义是 一个变种，两个节点如果在一个提前定义的集合中它们是有意义地，这一点可以由管理员给定， 它是用一个所有节点间的相互索引来检查是否两个节点是连接的和有意义的。 重于语义和结果的排名，把 tf*R 排列与树的大小和节点间的联系来排名结果， 因此需要用户知道 构架信息， 所以限制了查询的通畅性。文献 15提出了成组地距离最小连接树（ 通过将相关的子树集合到一起回答关键字查询问题。他们的算法首先鉴定了最小连接树，它是一个拥有最小数量边的子树，然后将这些子树集合到一起来回答关键字搜索。文献 13中提出了 排序方法并与谷歌的搜索方法 比。他们实现了一种基于栈的算法（ ，给出了一个排序方法：给定一个包含关键字的树 t，使用 3 档的 变种对 t 给定一个分数来排序， 但此排序方法并未考虑节点间的结构关系，并且不返回 解释关键字是怎样互相连接的，只输出最具体的结果。 为利用嵌入在 档中的丰富的结构关系来武装关键字查询过程。文献 10中他们开发了一个考虑 档结构信息的索引方法（ ，同时提出最小价值树的概念， 并利用提出的索引方法去鉴别最小价值树。 为降低索引大小他们整合了编号方案。在这一索引中，不仅对那些包含关键字节点的构建索引，而且同样对那些后代也包含关键字的节点进行索引。提出两种排序技术，一种基于对连接（ 分析，另一种是基于关键字对（ 的相关度。最后采用基于阈值的方法（ 16进行排序。 低公共实体祖先）是采用实体作为基本的语义单元的方法进行查询，并提出基于 查询算法。 目前基于 结构的关键字近似搜索的算法大多比较昂贵，以启发式为基础，通过使用各种形式的预计算来提高性能。 7系统使用一个近似 的问题来发现标记图的 步计算每个包含关键字的距离达到 K 的节点 i， 在 集中发现生成树的根节点时便把生成树输出。 大多数的 键字排序方法只考虑关键字的与操作，即返回包含全部关键字的相关结果，其中返回包含关键字最紧致片段问题成为了研究的热点。在文献 12,14中考虑到查询关键字之间存在的与和或两种关系。 在 段相似性的判定方面，考虑到 段的结构信息，提出了很多相似性计算方法。文献 20中提出了通过树编辑操作判定相似 树片段的方法，认为对于两颗 ， 它们的编辑脚本是将一颗子树转化为另一颗子树的一系列编辑操作。将这些操作中代价最小的称为树编辑距离。文献 21中作者将字符串比较功能整合到传统的有序树编辑距离中，来计算 档中的近似连接。 文的主要研究内容 键字查询由于不需要用户掌握相关的查询语言和了解 档的内部结构而得到了广泛的关注，具有很大的发展前景。目前，关于 键字查询的研究大多集中在寻找包含所有关键字的最紧致片段上，提出了 语义进行表示和求解。在实际应用中，包含部分关键字查询的结果对用户来说可能同样很重要，这些结果在包含所有关键字的最紧质片段语义上是很难实现的。但在 构查询中，对于得到部分关键字匹配的结果这一问题可以得到很好的解决，可通过松弛查询得以解决。因此，将 构查询的相关知识引入到关键字查询中是一个很好的研究点。本文对此进行了相关的研究，将面向对象的思想和松弛查询知识引入到关键字查询中，提出了由输入的关键字和 档结构信息判定用户查询意图的对象体的算法， 4 并进一步提出基于松弛的关键字查询框架。 本文主要做了以下几个方面的工作： （ 1）分析了 构查询和关键字查询的现状，通过分析各种 键字查询算法的特点，提出了现有的关键字查询算法存在的不足。 （ 2）针对 键字查询存在的不足，提出了一种结合 构查询知识的新的关键字查询方法。将面向对象的思想引入到关键字查询中，将 型文档进行对象化处理，并提出 “结果对象体 ”这一概念及相应的算法来推断用户的查询意图。利用构松弛查询对结果对象体进行相应的查询。 （ 3）对现有的打分策略进行了一定的改善， 通过引入属性的权重，使在打分阶段考虑用户的偏好，从而可以得到更为准确的查询结果。 （ 4）在数据集合上对多种 键字查询方法进行实验对比，验证查询方法的有效性和效率性。 文的组织框架 本文是按照以下结构组织的： 第一章，对本文研究领域的背景以及意义进行了简要的介绍，阐述了国内外的研究现状，并介绍了本文研究的主要的内容。 第二章，介绍与课题相关的基本知识，包括 基本概念知识， 询方式， 键字查询技术及索引编码技术等。 第三章，介绍本文所提出的基于结构和语义松弛的 据关键字查询方法，包括阐述对象化的概念，相似对象体的判定方法，以及根据关键字和 构信息推断用户查询的结果对象体算法。后面给出考虑用户查询偏好的结果打分方式，以及排序方法。 第四章，给出测评实验方法和结果，在精确度、召回率和效率三个方面将本文提出的关键字查询方法与查询方法 行了对比，表明本文提出的方法在查询效果上有良好的表现。 第五章，对本文的主要内容进行了总结，并展望了下一步的研究方向及内容。 5 2 据库查询理论 基本概念 介 可扩展标记语言 )是由 作组定义的。它和 样，都是 一个子集。 于过于复杂，所以很难流行起来，而 过于简单且缺乏灵活性。 以通过在文本文件中增加额外的标记来传递更多的信息，它不再侧重于数据的显示和表示，而是更多的侧重于数据的存储和传输，它是一种元标记语言，并逐渐演变成为了一种跨平台的数据交换格式。 相对于 言， 有很多优点： （ 1） 自描述的。它不仅允许用户定义自己的一套标记，而且这些标记没有必要像 样受到对于显示格式描述的局限。 （ 2） 持对文档内容的验证。 档的结构和内容需要遵守一定的文档规则，并使用 者 义语义约束。有了语义约束便可方便地验证文档的有效性。 （ 3） 许各行业开发不同专业的特定领域的标记语言。基于 多行业定义了自己的标记语言，专业人士就可以方便地交换短文、数据和信息。 （ 4） 持高级搜索，通过语法规则可以得到文档内容的结构和含义。所以，在 档中进行搜索会很高效7。 图 档示例 ML K. 005 ML 005 28 6 语义约束 一个 档一般由声明， 元素， 属性， 处理指令， 注释和命名空间组成。 一 得到有效的 件，还需要有一种用来描述 档中信息结构的机制， 这种机制不仅建立了 档中可以使用的 汇表， 还建议了 素的嵌套关系和内容模型，建立了文档数据的数据类型。目前有两种为 档定义的约束方式， 一种是采用 为语义约束， 另一种是采用 为语义约束。 义约束简单易用，功能相对较弱， 义约束是用 档定义的，支持更详细的约束规则，功能更加强大，使用起来也相对复杂。 档的约束主要包括以下几个方面： （ 1）定义 档根元素、结构和内容。 （ 2）定义 档里可以接受哪些元素，不可以接受哪些元素。 （ 3）定义 档里每个元素能接受哪些属性等。 （ 4）定义每个属性的类型，元素对属性的约束，以及能接受哪些值等。 （ 5）定义属性的默认值和固定值。 （ 6）定义 档里每个元素能接受的合法内容。 当 义了合法的语义约束后，需要将 档引入该语义约束，用来表明该文档遵循哪种语义约束。 引入的 分为 3 种方式： 内部 部 公用 部 指在 件的序言部分加入一 述，将此描述放在紧接 明之后的位置。这样是定义了一个。如果有一批文档都需要遵守相同的语义约束，若为每份文档增加相同的 义是相当繁琐的， 这种情况下采用外部 是更好的选择，当需要对 行改动时，不用一一改变每个引用它的 件，只需要改动一个公用的 件就可以实现。还有一种 由某个权威机构制定的，提供给特定行业或公众使用的 种 为公用 持丰富的数据类型，提供了比 强大的语义约束，并且允许开发者自定义数据类型。它本身就是一个 档，可读性比 。由于 用非 语法来描述 语义约束，不支持多样的数据类型，可扩展性差，而这些可以通过 现，它具有以下的优势： （ 1）可读性好。 （ 2）支持为元素内容或属性值指定数据类型，功能更加完善，更强大。 （ 3）可针对未来的需求进行扩展。 身是由 写的，因此所有对 档有效的技术都可作用于它。 7 询方式 据模型 描述 数据模型有树模型和图模型两种。目前，对于 研究大多基于一个树状模型，如图 示：其中的每个节点都是以下 7 种类型之一：根结点，元素结点，属性结点，命名空间结点，处理指令结点，注释结点，文本结点。树状模型很容易表达出 据的层次结构，节点表示文档中的元素、属性和值，边代表元素间的嵌套关系。 析器 由于 档是结构化文档，为了更好的解决 档的解析问题， 出了 模型的推荐标准， 目前最新的版本是 , 它把结构化的文档映射为一系列的具有父子、兄弟关联关系的节点对象集，并且允许应用程序调用这些节点对象的方法、 属性来读取或更改 点的内容。 解析 将整个文档读入，并且把该文档转换成常驻内存的树状结构 。对文档的所有查询或修改的操作均在 上进行。 另一规范 采取基于事件处理的方式对 档进行解析。首先 析器顺序扫描文档，并在 档中依次触发文档开始、元素开始、文本、元素结束、文档结束等事件，这些事件会被应用程序监听，通过触发相应的事件对 档进行访问并获取其内容。 对于 两种解析机制， 提供了相应的技术支持， 析 PI ，另外一些 析器（如 同样支持 析。 析操作简单， 由于它将 档分解成单个的对象， 并一次性将整个 ）贮存在内存中，因而可以引用和操作每个元素对象，但是占用内存空间比较大。 析器在读取文档相应的内容时，就会向外产生并发送一次事件。它比 用内存少，并且当 找到需要的信息时可以停止对 档的解析， 因而处理速度更为迅速。 系统资源紧缺的情形下适合处理大型的 是它不能够实现对文档的随机访问。 询语言 由 建的，它是一种专门用在 档中查找信息的语言，目前的版本是 它使用的是一种紧凑的， 非 语法格式， 并主要用于为 其他 术提供相应的服务。 用类似于 路径表示法进行导航。 持的节点类型有根节点，元素节点，属性节点，处理指令节点，注释节点， 8 命名空间节点和文本节点。它所支持的节点关系有父节点，子节点，祖先节点，后代节点和兄弟节点。在 ，最重要的表达式是定位路径表达式，分为相对路径和绝对路径两种。每个定位路径的表达式包括一个或多个定位步（ ，定位步之间用正斜杠（ /）分开。 下面给出一个简单的定位路径表达式： / （ （ 上式中， （ 对路径， （ 相对路径。绝对路径以磁盘的根路径开始，在任何位置都是指向相同的文件或文件夹。上式（ 的 达式匹配文档中 根元素下 子元素所包含的 子元素。相对路径需要依赖于当前的路径。 一个定位路径一般是由多个定位步组成，每个定位步由三部分构成： 轴：定义了所选节点与上下文节点之间的结构关系（树状关系） 。 节点测试：指定定位步所选节点的节点类型或节点名。 零个或多个限定谓词：使用专有谓词表达式进行进一步的限定，并筛选定位步所选的节点集合。 其中， 义了 13 个轴，如 ， ， ， 等，每个轴都有基本的节点类型，对于属性轴，基本的节点类型是属性。节点测试对轴中的节点进行测试。若给定的节点的测试值为 保留在结果节点集中，否则将其从结果节点集中删除。限定谓词处于定位步末端的方括号里，它对通过轴和节点测试得到的原结果节点集进行测试筛选，并且生成新的测试结果节点集。对于原结果节点集中的每个节点，把它作为上下文来计算谓词表达式的值，并强制将其转换为布尔值，如果结果为 节点将被保留在新结果节点集中，否则被丢弃。 询语言 一种可以智能的使