论文部分内容阅读
关系数据库是一种主要的信息存储机制。传统上,SQL是存取关系数据库中数据的主要界面。但是,对于没有经验的用户来说,学习复杂的SQL语法是一件困难的事情。并且,当用户要查询一个关系数据库中的数据时,必须知道这个数据库的数据模式。当关系数据库隐藏在网页后面或在P2P网络里共享时,用户很难获知它们的数据模式,因此无法直接用SQL语言进行查询。关键词查询是查询文档和网页的最简单、最流行的信息检索技术。关键词查询直观易用,不需要学习查询语言,也不需要知道查询对象的底层结构。实现基于关键词的关系数据库信息检索,将使用户不需要任何SQL语言和底层数据库模式的知识,用搜索引擎的方式来获取数据库中的相关数据。 现在的关系数据库基本上都集成了全文搜索功能,Oracle、IBM的DB2、Microsoft的SQL Server,PostgreSQL,MySQL等都提供了和数据库引擎紧密集成的文本搜索引擎扩展。但这些索引只能以属性或元组为索引单位,而用户要求将包含部分关键词的元组连接起来,生成更全面和完整的查询结果。 现有的关系数据库关键词查询系统大多是建立在这些文本搜索引擎上的。已经有几个关系数据库关键词查询系统被开发出来:BANKS,DBXplorer,DISCOVER,IR-Style,EKSO和ObjectRank等。这些系统可以分为在线查询和离线查询两大类。 关系数据库关键词查询是结构化查询和关键词查询相结合的产物。信息检索技术和算法可以有效地提高关系数据库关键词查询系统的性能。一些信息检索技术已经被采用,例如全文索引,相关性排序,Top-k等。关系数据库关键词查询系统应该考虑采用更多的信息检索技术和算法。 本文描述了一个基于关键词的关系数据库信息检索系统SEEKER的设计和实现。现有的关系数据库关键词查询系统只能检索关系数据库中的文本属性,SEEKER还可以检索数据库元数据以及数字属性的系统。并且,SEEKER采用了更合理的排序公式,支持Top-k查询。SEEKER由以下几个模块组成:语法分析,IR引擎,候选评分表连接树集合生成和Top-k查询结果生成。语法分析模块将不同形式的关键词识别出来,以便于IR引擎采用不同的方法进行处理。SEEKER利用了RDBMS提供的全文索引来对文本属性进行关键词查询。为了支持对元数据的查询,SEEKER中建立了两个匹配表,分别用于关系和属性的关键词匹配。对于四类不同的关键词,IR引擎采用不同的方法进行查询。IR引擎对文本属性和数字属性的评分方法完全不同,对文本属性的评分将由RDBMS的全文索引给出,对数字属性的评分由SEEKER的公式给出。对每个关键词,IR引擎为数据库中的每一个关系创建一个基本评分表,在基本评分表的基础上生成评分表。候选评分表连接树集合生成模块根据数据库模式图和IR引擎生成的评分表集合来生成候选评分表连接树集合。Top-k查询结果生成模块的主要功能是将候选评分表连接树转换为SQL查询,从数据库中查询出数据,将k个得分最高的结果返回给用户。SEEKER的查询结果用XML文件格式表示,这样可以保持查询结果的语义。缓冲区技术和Universal Relation的思想被用来提高SEEKER的查询性能。实验结果显示,SEEKER具有良好的查询性能。 P2P是一种网络体系结构,网络中的每一台计算机或设备有相等的能力和责任。P2P系统具有五个主要特性:网络中的Peer间能够实时传输数据和消息;Peer可以同时充当Server和Client;网络中的主要内容由Peer提供;网络对Peer既有控制,也允许Peer自治;Peer不需要始终连接在网络上,Peer可以没有固定的IP地址。目前,绝大多数的P2P系统只提供文件级的共享,共享粒度较粗,缺乏数据管理的能力。将P2P技术和数据库技术结合起来,构建P2P数据管理系统是大势所趋。 在SEEKER的基础上,提出了一种P2P环境下共享关系数据库的新框架,将Top-k查询扩展到P2P环境下的数据库共享系统上。系统中每个共享的数据库都提供一个关键词查询的接口,不同Peer返回的结果合并后生成最终的结果。系统共分为四层:P2P层、关键词检索层、Top-k查询层和数据库管理层。数据库管理层采用RDBMS来管理数据;关键词检索层在数据库管理层之上,对本地数据库进行关键词查询,采用SEEKER作为关键词检索层;Top-k查询层主要负责将各个节点(包括本地节点)的查询结果汇集生成全局的Top-k结果;P2P层主要负责节点之间的网络通讯。系统将每个数据库看成一个文档集,简化了不同节点之间模式映射的过程。节点可以自由地加入和退出系统,节点上的数据库模式也可以自由地改变,系统不需要维护节点之间模式映射的关系,较好地适应了P2P网络分散和动态的特性。还提出了一种基于直方图的分层Top-k算法来提高搜索的效率。由于P2P中每个查询过程都可以用一棵查询树来表示,可以分层进行Top-k查询。儿子节点返回Top-k结果给父亲节点,父亲节点聚集所有儿子节点的Top-k结果和本地的Top-k结果产生全局的Top-k结果。分层的Top-k查询将结果的合并和排序分散到P2P网络中的各个节点上,充分利用了网络中的资源。由于结果自底向上进行合并,只取合并后的Top-k结果向上传递,一些不相关或者较差的结果就在合并的过程中被过滤掉,因此大大节省了网络带宽;其次,根据Peer返回的结果为节点构建直方图,利用直方图为将来的查询估计Peer可能的分数上限,对Peer进行选择,裁剪查询树的一些无用分枝,提高了搜索的效率。父亲节点为每个儿子节点建立直方图,直方图也是分层的。由于直方图根据儿子节点返回的结果建立,因此不需要儿子节点事先建立直方图。随着查询的进行,直方图可以自动更新,是自适应的。维护直方图的代价也很小。此外,还采用邻居节点自调整策略来提高查询性能。实验证明,直方图的分层Top-k查询算法和邻居节点自调整策略是有效的。 本文的主要创新性研究成果有: 1.实现了一个基于关键词的关系数据库信息检索系统:SEEKER,与现有的关系数据库关键词查询系统相比,SEEKER不仅可以检索关系数据库里的文本属性(CHAR、VARCHAR、CLOB等),还可以检索数据库的元数据(关系名、属性名等)以及数字属性(DATE、TIME、INT、FLOAT、NUMERIC等)。 2.对关键词查询的语言进行了扩展,提出了四类关键词:(1) Keyword;(2)Keyword: Keyword;(3) Keyword: Value;(4) Keyword: Value。第一类就是简单的关键词,包括词和短语;第二类的关键词用来对文本属性进行包含元数据的查询,“:”前的Keyword用来匹配关系或属性,“:”后的关键词用来对匹配上的关系或属性进行关键词查询。第三类的关键词用于对数字属性的查询,“:”前的Keyword用来匹配属性,“ Value”部分对匹配上的属性进行条件查询,是关系操作符。第四类关键词用来对数字属性进行模糊查询,“:”前的Keyword用来匹配属性,“Value”是属性的值,用来对匹配上的属性进行模糊查询,属性的值越接近Value越好。用户提交的查询是这四类关键词的组合。 3.提出了一个更合理的评分公式对查询结果排序。提出了第三类和第四类关键词的权重计算公式。 4.为了提高SEEKER的查询速度,减少查询响应时间,为SEEKER增加了缓冲区,将用户经常进行的关键词查询的查询结果以及中间结果放在缓冲区中。现有的关系数据库关键词查询系统都没有考虑用缓冲区来提高查询速度。 5.针对SEEKER存在的主要缺陷,用Universal Relation的思想对SEEKER进行了改进,有效地提高了系统的查询速度,并实现了真正的对数字属性的模糊查询。 6.在SEEKER的基础上,提出了一种P2P环境下共享关系数据库的新框架,将Top-k查询扩展到在P2P环境下共享的关系数据库上。还提出了一种基于直方图的分层Top-k算法来提高搜索的效率。 研究工作的最终目的是用基于关键词的查询作为无结构文本文档、半结构化数据(XML)和结构化数据(关系数据库)的统一访问界面。无结构文本文档的关键词检索已经是一个非常成熟的领域,SEEKER为关系数据库提供了有效的基于关键词的信息检索方法,现在已经有一些论文开始研究XML的关键词检索。下一步研究的重点是实现一个基于关键词的XML信息检索系统。