论文部分内容阅读
大多数用户在查询的时候都会使用搜索引擎,即他们只需指定一些关键词,搜索引擎就能返回包含这些关键词的文档列表。然而通过搜索引擎只能找到互联网上的一小部分数据,这些互联网上搜索引擎搜索不到的数据构成了所谓的Hidden Web,Lawrence和 Giles中。估计互联网上有80%的内容存储在Hidden Web中。存储在 Hidden Web中的信息是通过搜索引擎可以找到的信息的400到550倍,并且还在不断增长。用户之所以找不到Hidden Web中的数据,是因为它们都被存储在数据库中,只有通过特定的查询语言才能访问这些数据。如果数据库系统能够支持关键词查询,那么用户就能够以和搜索引擎同样的方式来访问数据库,用户既不需要学习复杂的SQL查询语言,也不需要事先了解数据库的模式,而只需要输入查询的关键词就可以得到最终的查询结果。为此,必须建立能够统一处理结构化、半结构化、无结构数据的系统,也就必须实现基于数据库的关键词查询系统。 目前数据库上的关键词查询系统,已经引起人们越来越多的重视,其研究目的都是在寻找快速、有效的查询算法,主要研究方向可以分为系统模型、体系架构、打分函数、查询算法、结果展现等。 系统模型:包含数据库的表示方法、用户查询的表示方法以及查询结果的表示方法。 系统体系架构:包括预处理模块和查询处理模块。大多数系统的预处理分别创建需要的模式图或数据图,而ObjectRank的预处理模块负责计算出所有结点和关键词组合的分数,存储在分数索引文件中。 查询算法:负责在数据图或模式图上进行查询,寻找具有最短查询处理时间的查询算法。 打分函数:为了有效地对查询结果进行排序,需要选择合适的打分函数。目前常用的打分因素为:元组和关键词的关联程度;答案树的分数;链接的语义等。 结果展现,即查询结果的展现方法。BANKS系统使用嵌套表格的方式显示答案树;系统以文字形式显示与连接树有关的信息,以表格的形式显示连接后生成的结果元组。 目前很多流行的数据库检索系统都能够有效地支持基于数据库的关键词查询,但是它们还是存在一定的问题: (1)目前的数据库关键词系统往往都是基于特定的数据库应用或是在预处理阶段需要了解数据库的模式信息。系统本身仍然需要了解数据库的模式以及主外码约束条件;还需要指定全文索引、显示列等元信息。当移植到其他的数据库应用中,需要修改预处理模块和查询处理模块,降低了系统的通用性和灵活性。 (2)目前的数据库关键词系统往往都是基于静态的数据库,很少关注于其他用户对数据库系统的更改。当数据库系统发生改变时,只能暂停查询服务,需要重新生成数据图并装载到内存中,具有很高的时间代价。虽然基于模式图的算法是在生成结果时才构建查询语句,可以保证获得最新的元组信息,但是模式图本身也面临不一致的问题,同样也需要维护模式图的更改。 (3)目前的系统只是支持AND或OR查询,而且只能支持在一次查询中使用其中一种运算符,也不能支持NOT查询。使用NOT查询,可以过滤用户不希望出现的关键词,可以让用户更关注于需要进行查询的关键词。同时,支持多种运算符的组合,可以提供满足复杂查询条件的需求。 基于上面的问题,本文描述了基于动态数据库的、通用关键词查询系统DETECTOR。它有效地解决了预处理模块、查询模块同数据库模式相关性的问题,可以统一地处理不同的数据库应用。DETECTOR系统在查询过程中创建了基于关键词的状态表,有效地支持复杂的AND/OR/NOT语义及其混合查询。DETECTOR系统提出的增量更新机制有效地解决了数据图和模式图的不一致的问题,体现了系统的实时性。 DETECTOR系统利用有向模式图表示数据库的模式信息,用无向数据图表示存储在数据库中的数据;将用户查询表示为以关键词为参数,以AND/OR/NOT为运算符的查询函数;将查询结果表示为没有特定根节点的子树。DETECOTR系统架构分为两大部分:即系统管理程序和查询处理模块。系统管理程序负责准备查询系统数据图,进行模式级别系统信息管理,可以分为预处理、模式信息更新和浏览系统信息三大模块。查询处理模块负责处理用户的关键词查询并返回结果,可以分为初始化、增量更新、查询解析、IR索引、查询处理、结果展现6个基本模块。 DETECTOR系统总的处理流程为:处理一个新的数据库管理系统时,系统管理程序只需对数据库系统进行一次预处理,创建与之对应的数据图。查询处理模块读入需要处理的数据图,利用状态驱动的动态规划算法搜索数据图、返回 Topk个查询结果。同时,DETECTOR系统的更新机制记录下数据库所进行的所有的更新操作,并在数据图上重做这些操作。当需要向现有的模式图中增加或删除应用时,运行系统管理程序进行模式图更新,从而保证了模式级别和数据级别两个层面的一致性。DETECTOR系统的创新和特色在于: 1.解决了关键词查询系统和数据库模式相关的问题,实现了自动抽取模式图,创建数据图、表描述信息,增强了系统的通用性。 2.提出了划分模式子图的思想来分离同一个数据库下的不同应用,从而可以根据用户的具体需求,在特定的数据图上进行查询,提高查询效率。 3.提出了数据图增量更新的解决方案,建立的触发器监测到数据库所进行的数据级别的更新操作后,查询处理模块动态地更新内、外存数据图,保证数据图与数据库数据在内存和外存两个层面上的一致性,使得用户可以查询到数据库最近的一致性状态下的结果。 4.提出了模式图增量更新的解决方案,可以批量的导入创建的表和主外码约束,解决了模式图和数据库不一致的问题,保证了数据库模式级别的一致性。 5.根据用户的具体应用需要,可以利用增量更新机制在模式图或数据图中添加任意数据库中并不存在的连接,进一步扩展用户的应用需求。 最后,本文还通过实验验证了 DETECTOR系统的功能和性能。实验表明,DETECTOR系统能够有效地解决系统通用性以及数据图和数据库不一致性的问题,并具有较短的查询处理时间。