面向Top-k分级的数据库关键词查询系统体系结构摘要：关系数据库关键词查询系统目前存在的主要问题是查询效率不高、查询效果不令人满意,其根源在于查询系统的体系结构不合理。捉出了一种新型的面向top-k分级的数据库关键词查询系统体系结构，并用提出的新的评分函数公式、基于索引的候选网络预处理方法、绑定实时过滤阈值的top-k搜索算法对该体系结构进行实例化。结果显示该系统结构具冇很好的可行性，并R由实例化后的体系结构实现的系统具冇很好的查询性能。关键词：关系数据库；关键词；索引；top-k中图分类号：0引言关系数据库是一种主要的信息存储机制，SQL语言是关系数据库的标准查询语言，而对普通用户来说，SQL语言既难学习，又难使用，并且用户在查询关系数据库中的数据时，必须知道这个数据库的数据模式。如图1所示的DBLP数据库，当用户查询MVangelis发表的关于keyword方面的论文”，用SQL语言表示这个查询SELCETp.titleFROMAuthora.WritesPaperspWHERa.anthorid=w.anthoridANDw.paperid^p.paperidANDcontains(a.nante9VagelisJ)>0ORDERBYScore(l)DESC;显然对于普通用户而言，书写这些复杂的SQL查询语句是困难的。采用基于关键词的关系数据库查询技术后，使得普通用户不需要任何SQL语言和数据库模式的知识，也不需要学习和使用关系数据库的定制的查询界面，通过关键词查询方式来访问关系数据库，就像使用WEB搜索引擎来检索Web信息一样，使得普通用户或者Web用户访问关系数据库变得直观、易用。近年来，基于关键词的关系数据库查询技术正是在这样的背景下成为了数据库、信息检索领域学者共同关注的研究热点之一。关系数据库上的关键词查询的相关研究按照其查询处理机制的不同可分为三类：离线系统、在线系统和混合型系统。离线系统通过预先计算生成中间结果，当用户提交关键词吋，根据中I'可结果牛成查询结果。在线系统将关键词查询转换为SQL查询，通过实时查询数据库来生成查询结果⑴。按照在线系统模型的搜索算法，又可分为两种：搜索数据库数据图的系统(SDDS)和搜索数据库模式图的系统(SDSS)oSDDS直接搜索最终结果,BANKS・『,BANKS・II⑶,QCRD⑷是典型的搜索数据库数据图的系统；SDSS搜索结果是连接表达式，Z后需要将其转化为相对应的SQL语句，IR-STYLE闻，SEEKER"1,SPARK-I⑹,SPARK-0堤典型的搜索数据库模式图的系统。混合型系统是基于搜索数据库模式图的系统和搜索数据库数据图的系统查询处理机制混合而成的系统，QuickCN⑻是典型的混合型系统。现在大多数研究工作都是基于搜索数据库模式图的系统。SDSS主要有三部分组成：元组集生成器、候选网络产生器、候选网络执行器，用户响应时间Tqrl=TLs+Tcn+TsqI,其中Rs为元组集生成器消耗的时间，％是候选网络产生器消耗的时间，Tsql是候选网络执行器消耗的时间。Ten是影响基丁•搜索数据库模式图的系统查询效率重耍因素。IR-STYLE、SPARK-I、SPARK-II原型系统中的候选网络执行器采用执行CN的算法，是通过绑定的阈值，來选择那些潜在的CN需要被执行。rti于阈值是估计值，致使基于搜索数据库模式图的系统的查询效果往往不太令人满意。本文针对目前SDSS存在的关键的性能(查询效率和查询效果)问题，提出了一个新型的关系数据库Top-k关键词查询原型系统体系结构，并用给出的新的评分函数公式，提出的基于索引的候选网络的预处理方法、绑定实时过滤阈值的top-k搜索算法对该系统体系结构进行实例化，结果显*国家自然科学基金(60773100),国家“-一五''科技支撐计划(2006BAK05B02)，河北省自然科学基金(F2009000475)。示该系统结构具有很好的可行性，并且由实例化后的体系结构实现的系统具有很好的查询性能。1基本定义定义1:关系数据库模式•假设关系数据库的模式,SdZFK),R={RhR2t...Rk}是一组关系模式,FK是中关系模式间引用关系的映射,如果FK(R戶％,记为RiTRj(lM,/</?),它表示①•一个外键引用了尺主键。定义2:数据库模式图.假设Gs=(VfE)表示模式Sdb=(R,FK)的关系数据库DB对应的模式图。Gs是一个有向图，将DB中的每一个关系模式心仃&9)看作是G•的一个顶点，当且仅当关系模式RfG$,关系模式RjwGs,(RiTRj)wFK时，(&,Rj)eEo定义3:连接元...