【毕业学位论文】（Word原稿）关系数据库CoDB中XML全文检索的设计与实现-计算机软件与理论数据库与信息系统

北京大学硕士学位论文 关系数据库 文检索的设计与实现 1 硕士研究生学位论文 题 目： 关系数据库 文检索的设计与实现 姓 名： 学 号： 10108046 系 别： 信息科学技术学院 专 业： 计算机软件与理论 研究方向： 数据库与信息系统 导 师： 杨冬青 教授 二零零 四 年 五 月 北京大学硕士学位论文 关系数据库 文检索的设计与实现 2 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 北京大学硕士学位论文 关系数据库 文检索的设计与实现 3 摘要 随着社会的信息化 ， 传统的关系数据库 已经不能满足人们的某些应用。 在关系数据库上增加新的功能特性成为当前的主流的研究方向。例如全文 检索 就是数据 库系统急待 增加 的一个 功能 。 一旦数据库拥有了全文检索的功能，用户 就 可以通过 句进行关键字的查询，而且可以完成聚集、连接等一系 列复杂的查询。这是一般搜索引擎所不能办到的。 另一方面 伴随着 渐成为数据交换的标准 ，对 档的 查询 也是当前的 一个 研究热点。目前主要的研究工作还是集中在对 档的结构化查询上，而对 关键字检索的工作还处于刚刚起步的阶段。结构化的 键字的检索有自己的特点： 用户 不需要知道结构信息也不需要知道复杂的 询语言。 对于 普通 用户 来说他们更喜欢这种简单 关键字 的检索。 因此 关键字检索有着非常广阔的应用前景。 本文以北京大学数据库教研室开发的 系数据库为基础，在其上设计并 实现了 文检索的功能 。 我们的系统有如下一些特点： 支持 档的检索，查询的精度可以控制，可以是 在 档的元素别也可以是 在 文档级别。 的 全文检索功能和数据库 查询引擎 句紧密 地结合 在了一起， 用户 可以完成一些较为复杂的 基于关键字的 查询。 设计 了一种新的自索引的倒排结构可以很好的 应用于 文 检索 。 支持对 档的重要度和 素的重要度排序。 实验证明 使用 我们 的 全文 检索 进行 检索 时 查询 速度要比 一些 ，而且在全文检索的功能上 还 要 略 强于 关键字 文 检索 、查询引擎 、 自索引的 倒排索引、 D 北京大学硕士学位论文 关系数据库 文检索的设计与实现 4 s of of of to of is a is as be in On of ML is in ML on is at we ML It t to ML or be ML ML be in we a a is as We ML be at be by ML QL QL We a in a ML We on is S ML is in 关系数据库 文检索的设计与实现 5 目录 ： 摘要 . 3 关键字 . 3 . 4 . 4 1. 引言 . 7 系数据库面临的挑战 . 7 目背景 . 8 文组织 . 8 2. 问题的引出及相关研究 . 10 前商业数据库中的全文检索 . 10 . 11 介 . 11 档结构 . 12 询 . 13 数据模型 . 14 点编码方式 . 14 文检索带来的挑战 . 16 支持关键字检索的意义 . 17 心数据结构倒排索引 . 17 关工作 . 18 3. 系统简介 . 20 功能特性 . 20 统结构图 . 22 要模块功能介绍 . 22 存储 . 25 件管理 . 25 面管理 . 25 组的存储 . 26 组的数据结构 . 28 查询 . 29 询分析器 . 30 询计划器和优化器 . 31 询执行器 . 33 系统函数 . 34 4. 文检索的设计 . 35 统结构 . 35 索引的倒排索引 . 36 据结构描述 . 37 要算法 . 37 查询引擎的结合 . 39 要度的计算方法 . 40 5. 文 检索 的实现 . 42 北京大学硕士学位论文 关系数据库 文检索的设计与实现 6 引的存储 . 42 用索引进行检索 . 44 增加索引类型 . 48 立索引 . 49 用索引进行检索 . 50 现界面 . 50 6. 测试结果 . 53 7. 总结和展望 . 55 附录 . 56 1 构（ . 56 2 构（ . 57 3 构（ . 58 4 构 （ / . 59 5 构 （ . 59 6 构（ . 60 参考论文 . 62 参考书籍 . 63 致谢 . 65 北京大学硕士学位论文 关系数据库 文检索的设计与实现 7 1. 引言 系 数据库 面临的挑战 产生于 70 80 年代的关系数据库技术已经非常的成熟。 当时的数据库发展主要集中 在结构化数据 的 应用 上。在数据库领域应用 的发展始终是数据库系统进步的动力。 随着社会的发展和时代的进步，传统的关系数据库 系统在很多方面越来越不能满足需求。大 文本数据、多媒体数据、时空数据 、 据 等各种新型数据的涌现， 暴露出 关系数据库在诸多 应用上的限制 。 因此当前关系数据库的发展 趋势 也是在向着 支持更多更全的应用上发展。考虑到兼容性，关系数据库还是核心，在关系数据库基础上搭建 各种 新 的 功能成为了关系数据库新的发展方向。 随着网络的普及，搜索引擎称为人们上网最常用的工具之一。搜索引擎的核心就是全文检索技术。目前的国内外的搜索引擎大部分都使用都是自己特有的数据库和全文 检索 。如果能够在通用的关系数据库增加全文 检索 的功能 ，一定 会有广阔的 应用 市场。 同时 档已经逐渐成为互联网上数据交换标准。 富灵活的表现形式和扩展性为网络环境下分布、异构的数据集成、共享和交换奠定了基础 。 如何在关系数据库中存储和 查询这种半结构化的数据 也成为了一个关系数据库的研究热点。 当前的研究主要集中在基于结构的 询上，对于关键字的查询研究比较少。对于普通的用户来说，他们更喜欢的是基于关键字的 索，他们不需要 知道 档 的结构信息，也不需要知道 询语言的语法。我们的工作 主要 集中在 关键字检索上。 综上所述， 在 关系数据库 增加 档 的 全文 检索 是我们当前急待解决的问题。该项 工作的意义主要有两点：一是在传统的关系数据库中加入了全文检索的功能 ，使关键字查询和 询引擎紧密的结合起来 ； 二 是我们的全文检索不仅仅是简单普通文本，而是实用性更强的 档。 我们 工作 面临 的挑战 主要有 四 ：一是在于 数据库中的 如何 存储；二北京大学硕士学位论文 关系数据库 文检索的设计与实现 8 是 文检索如果 和关系数据库查询引擎的无缝结合；三是 如何索引 它和普通文本的 在处理上 有何区别 ；四是对于检索的结果如何按照重要度排序 。 本文将会详细的说明我们 所采用的方法。 目背景 上面讲到 本文的 主要工作是在 据库管理系统上增加 档 全文检索的功能。在此 之前， 我们 有必要 先简要介绍一下项目 的 背景。 是由北京大学数据库实验室开发的大型通用数据库管理系统。它具有自主知识产权，以国家“八五”“九五”科技攻关支持并获得电子科技部科技进步特等奖的 据库管理系统为基础，同时借鉴了国外开发源码数据库管理系统（如 ）的部分成果，具有国内领先水准，达到了国际同类产品的水平。 据库系统适合中国的国情和需求，能够满足各行业和领域的需求，并以促进 国内电子政务、电子商务、企业信息化等领域的发展为己任。 北京大学 数据库实验室所承担了 “国家重点基础研究发展规划”项目（ 973）中的“面向内容的海量信息集成、分析处理和服务” 课题的研究。 本课题的目标是发现海量 息的内容组织方式，并使用 基于动态规则库的 息模式提取 方法将 息提取为统一的 档，并在其上建立 面向内容的海量息集成、分析处理与服务的原型系统 。这里一个重要的问题就是如何对提取后的 件的提供检索服务。 据库系统 迫切需要 扩展 对 据 的检索 功能。 目前的解决思路有 两种 ：一种是 将 档变为关系 数据库 存储，然后将相应的 询语句变为 询。另外一种就是 按照文本的方式存储，然后在其上建立倒排索引进行检索。本文主要 完成了 后者，也就是在 关系数据库 增加 对 索 的工作。 文组织 本文的组织分为 七 个部分，第一部分是引言，介绍了 关系数据库 当前面临的北京大学硕士学位论文 关系数据库 文检索的设计与实现 9 挑战 、本文的项目背景和论文的组织；第二部分 引出了对 文检索的需求并简述了当前的 相关研究 。第三部分 简要 地 介绍 系数据库系统，描述了 统的体系结构 ， 并对 处于 核心 地位 的 、和全文检索紧密相 关 存储和查询处理模块进行了 较为详细的介绍。 第 四部分详细地说明了 文检索 的 设计，我们给出了一种自索引倒排 索引结构 。 第五部分 给出了具体的 实现 。第六部分 我们在大数据量的情况下和 据库进行了比较。试验的结果表明我们的系统 比 检索速度要快 ， 而且查询的实用性更好。第七部分 作为全文的总结并对今后的工作给出了方向。 附录主要说明了一些数据结构的定义。最后为致谢和 参考文献。 北京大学硕士学位论文 关系数据库 文检索的设计与实现 10 2. 问题的引出 及相关研究 本章 我们 将 介绍一些 背景知识和当前的相关 研究 。 前商业 数据库中的 全 文 检索 商业数据库，如 3， ， 6都 在自己原有的数据库上增加了全文检索的功能。 他们的基本功能是基本相似的 。 支持各种常用文件格式。 纯文本、 。 支持 R 尔表达式的查询 支持 *的模糊查询 支持结果的排序 文 检索 的体系结构图 图 述了 系结构 ， 可以看出 一个全文检索的进程 责建立索 引和 对关键字 的检索。在 询时， 关系数据库 文检索的设计与实现 11 的查询引擎会和全文检索的进程通信完成查询。另外 从图中可以看出 存储和数据库的存储是分离的。 我们认为这种方法虽然在实现上比较简单但是全文检索 进程和数据库查询的分离会在检索速度上大打折扣。 介 近 几 年来成为数据交换和 数据 共享标准。 整的名称是可扩展的标记语言（ 伴随着超文本标记语言 蓬勃发展而产生的。 区别在于： 的标签 以任意的，而 的标签是有统一的格式的；而且 标签必须是封闭的，标签必须配对的出现。 例如下面的 档： 例 句在所有的 膏 牙刷 京大学硕士学位论文 关系数据库 文检索的设计与实现 12 出现的 ，这 是 档的标志。 像“所有商品”、“商品”、“商品编号”等 标签被为 档的元素 素必须是封闭的，也就是说每个元素之间没有交叉。 “所有商品”为根元素 个 档只能有一个根元素 。“单位”为“商品价格”的属性 牙膏”、“元” 等 为元素或属性的值。 可以看到 就既包括了数据的结构信息又包括了数据的信息。但是它的结构的信息并不完整，比如从 档中我们不能知道商品价格 一个数还是一个字符串，即我们不知道它的类型。所以我们称之为半结构化数 据（ 它介于结构化数据和无结构化数据之间。 目前 究有很大一部分是将如何将 储到数据库中。因此我们的 全文检索 要支持 文本的数据。 纯文本都是 此我们的工作重点放在了 档上。解决了 档的 全文检索 ， 纯 文本可以类似地处理。 档结构 用来规定文档语法规则的。 这是 一个 件必须遵守文件类型 描述 定义的种种规定。 例 描述例 档的 例 它要求 表示 “ 所有商品 ” 是 元素 。 北京大学硕士学位论文 关系数据库 文检索的设计与实现 13 *)是说“所有商品”可以包括多个“商品”元素。“ *”表示元素可以不出现或出现多次，这与正则语言中的 *、 +号的概念是一样的。 表示元素 “ 商品价格 ” 有一个属性 “ 单位 ”， 属性类型是字符串 #示这个属性必须要说明。 除了 ， 还有 可以用来规范 档结构。 传统的 询 就 需要用户知道 结构信息，而且 询不适用于满足不同 档 。 询 虽然 档具备了模式信息，但是 据模型是嵌套关系模型的扩展，因而传统的结构化查询语言 都不具备查询 档的能力。设计新的适应 据模型的查询语言成为一个研究 方向 。 在有许多中查询语言： 等。其功能和查询语言的形式也各不相同。 我 们简单介绍一下 言 89来加深对 询语言的理解。 言 是在 据中搜索特定 结构 信息的功能 非常 强大的 一种查询语言 。 它是由国际化的标准组织 出的。它的主要查询语句是 句。 缩写 ， 它描述了典型 询语言 的结构。 其中 描述了对于哪些节点满足什么条件的情况下生成什么样的档。 句可以将 数据被绑定到变量，然后后续步骤使用该变量。 例如：使用 例 2. 3 中 的 句 可以 查询 版商出版的所有书籍。例 例子 in )/ = $ $ 北京大学硕士学位论文 关系数据库 文检索的设计与实现 14 从 上 例中 可以看出 询语言是很复杂的， 而且查询的时候需要知道结构信息，如 标签，很不适合于普通 用户学习和使用。 数据模型 一般认为 数据模型 有两种：一种是无序树模型 ； 一种 是有序树模型。目前更多学者认为保持 节点顺序还是很重要的。 因此我们采用有序树模型。 例 档可以表示为 图 的树结构 。 商 品所 有 商 品商 品商 品 编 号 商 品 名 称 商 品 价 格 商 品 编 号 商 品 名 称 商 品 价 格1牙 膏3 . 0 0 2单 位 = 元 单 位 = 元1 . 0 0牙 刷图 结构 档中的元素 树的内部节点。元素的值和属性为叶节点。 节点的 顺序为 在 出现的顺序 。 大部分应用需要 对 树结构中 节点 给出一种编码方式。 点编码方式 节点编码方式 也有许多种。 为什么我们要将编码方式呢？这是因为我们后面讲 我们 这里 列出了一些常用的编码方式。 层次 周游 北京大学硕士学位论文 关系数据库 文检索的设计与实现 15 2135 846 7 9图 次周游编码 前 序 和后序 2134 875 6 91952 683 4 7图 序和后序周游编码 D 杜维 D 编码 10是一种保留树路径信息的表示方法。 1 . 111 . 21 . 2 . 1 1 . 3 . 11 . 31 . 2 . 2 1 . 2 . 3 1 . 3 . 2图 次周游编码 码是由 人 11引入的 ，它的 目的是为了可以快速判断父子关系和兄弟关系。 码定义如下： 1. 每个元素 有两个数值 (l, r)， , 31 , 1 74 , 1 05 , 6 1 2 , 1 31 1 , 1 67 , 8 8 , 9 1 4 , 1 5图 码 文 检索 带来的挑战 面将到的 关系数据库的 全文检索都有所不同。它有如下的一些特点： 档上 的关键字检索 并不是总是返回一 篇 文档，而是 可能 返回一个元素 这和商业关系数据库的全文检索 不同。 例如在 文档 例 查询关键字“李四”和“数据库”时 ， 不 应该 仅返回整篇文档， 而 应该返回的是粗体字的部分 ，也就是包括了所有关键字的 素 。 这样的 查询可以更加准确 ，精度更高。 当然在用户需要查看整篇文档的时候，也要能够返回整篇文档给用户。 例 询结果 李四 据库查询 张三 息提取 北京大学硕士学位论文 关系数据库 文检索的设计与实现 17 由于 档关键字检索的粒度在于元素 此结果 的重要度 排序也和普通的文本不同 。每篇文档有 ，每个 有 。 关键字在每个 的作用 是不一样的。 档中的标签要比内容更加重要。在计算文档权重和元素权重的 时候要分开考虑。 多个关键字检索时，关键字之间的距离度量更加复杂。关键字可能属于不同的层次，因此度量取决于两个参数一个是关键字之间的距离，一个是 元素次之间的距离。 支持关键字检索的意义 为什么 支持关键字检索呢？通常搜索引擎采用基于关键字的检索方式， 而数据库中普遍 使用的 是结构化 询 。他们各有各自的特点，关键字检索使用起来简单，但是查询的准确性差 ，所完成的功能也有限 ； 言功能强大，查 询方式丰富，但是用户需要学习 言 ， 并且在查询的时候需要知道数据库的模式信息。 一般来说 普通用户更喜欢的是关键字检索，而高级 程序员 和数据库管理员 更喜欢使用 言。从实用 性上看 ，关键字的检索要比结构化的查询更能被 普通人 接受，因为它不需要知道 语法，也不需要知道数据库的模式，只要输入几个关键字就可以查询。虽然查询的结果可能不是很精确，但是可以 通过 增加关键字或者辅助排序的方法 来 提高查询的 准确度 。 因此 我们认为把关键字检索结合到 言中有着更好的使用前景。一方面编程人员可以使用 句进行一些复 杂的操作，另外一方面编程人员可以使用简单 句就可以完整搜索引擎的功能。 这就是本文工作初衷。 心数据结构 倒排索引 全文 检索 的核心技术是倒排索引 这一技术在一般的数据结构的书籍中都有讲述。 它的基本思想是把正文看作一个长的字符串 处理 ，每个索引项记录每个词出现文档及其位置，索引按 照 关键字的 顺序 来 存储的。如表 检索一个关键字时可以快速 地 返回所有出现该词的文档。 索引项可以是关键字也可以是单个字母、 两个字母的组合、几个字母的组合北京大学硕士学位论文 关系数据库 文检索的设计与实现 18 或 字根等。基于关键词的倒排 索引存储量小但是检索的关键字可能受到限制；基于字母的倒排索引会 占用较多的存储空间，但是检索时不受关键词的限制。 可以采用 一些压缩方法可以减少存储空间 ，这里不再详细叙述。 对于 排索引的结构不能完全适用，需要做一些结构上的调整。后面我们会给出一种特殊的 自索引的倒排索引适用于 关键词 出现总次数 所在文档 所在位置 3 94 19 7 19 212 2 66 19 213 29 45 5 43 11 3 11 70 34 40 表 排 索引 关工作 首先 对于全文检索的功能 ， 前面讲到 商业数据库如 但是他们并不支持 别 全文检索。而且他们对于结果的排序只是简单的基于内容的排序，而且没有返回最有用的位置信息。 返回关键字在文档中的位置信息还是很有用途的。因此 我们希望能在这些方面进行一些改进。 在关系数据库中的支持关键字查询也成为一个新的研究方向。它和 全文检索不同，它是为了满足用户 在不知道数据库模式信息的情况下对数据库中的数据进行整体的查询。 也就是说