基于关键字的数据库搜索研究综述朱凡微,吴明晖,金苍宏,吕嘉,应晶(浙江大学计算机学院,杭州310027)摘要:介绍了基于关键字的关系数据库搜索技术的研究成果,从数据建模、体系结构、关键算法等几个方面详细分析和比较了各种技术的特点和优劣,并指出了现有技术中存在的一些问题,提出数据库关键字搜索技术未来的研究方向。关键词:基于关键字的搜索;数据库模式;相关性排序;top2k查询中图分类号:TP391文献标志码:A文章编号:100123695(2008)1123238205Surveyofkeyword2basedsearchoverdatabasesZHUFan2wei,WUMing2hui,JINCang2hong,LVJia,YINAbstract:Thispaperintroducedtherelatedresearchofkeyword2basedsearchtechnologiesoverrelationaldatabases,analyzedandcomparedthemodels,architectures,andalgorithmsoftheexistingsystems.Also,mentioneddeficienciesandproblemsandprospectedthefuturework.Keywords:keyword2basedsearch;databaseschema;relevanceranking;top2kquery基于关键字的搜索引擎是人们在互联网上搜索信息的重要方式。然而,现有的互联网搜索引擎主要针对静态网页进行索引。在网络应用中,大量数据保存在后台数据库中,以动态网页的形式提供给用户,不能被现有的搜索引擎索引;同时,存储在数据库尤其是关系数据库中的数据,由于需要特定的查询接口也不能被搜索引擎直接访问[1]。互联网上大量的关系数据库构成了DeepWeb的主要组成部分,也是现有互联网搜索技术所面临的一大难题。基于关键字的数据库搜索技术正是在这样的背景下成为数据库、信息检索、互联网等领域的学者共同关注的研究热点。本文详细介绍了基于关键字的关系数据库搜索的研究现状,比较数据库搜索中经典的数据模型和搜索模型,概括出各种模型的优缺点,并介绍了改进的模型。基于应用系统实例,总结出数据库搜索系统的两种体系结构及各自特点,着重对数据库搜索中的关键算法进行了分析评价,并提出了改进意见。基于关键字的搜索引擎DBXplorer。Aditya等人提出将搜索结果进行排序的思想,并实现了支持相关性排序和结果展现的BANKS系统[4]。V.Hristidis等人[5]在文献[3,4]的基础上对体系结构和算法优化作了进一步的研究,提出了DISCOVER系统。2003年V.Hristidis等人[6]又将IR领域已经很成熟的排序策略运用于数据库搜索中,提出IR2Style排序策略。2004年A.Balmin等人[7]在Google的PageRank算法启发下,提出了一种基于权威(authority2based)的相关性排序算法ObjectRank。b)第二个阶段是对搜索准确性的探讨和提高,研究主要涉及排序算法、搜索性能、搜索结果显示的优化等。2005年文继军等人[8]对数据库搜索语言进行了扩展,基于三类关键字,即Keyword、Keyword:Keyword、Keyword:〈op〉Value实现的SEEKER系统不仅可以支持属性值的搜索,而且还可以对元数据进行搜索;并对相关性评分机制作了改进,将[9]top2k结果返回给用户。2006年LiuFang等人通过对影响搜索有效性的关键因子的识别和规范化定义,提出一种有效的新的排序策略,并通过大量实验证明了搜索的有效性。DingBo2lin等人[10]针对寻找最小代价的Steinertree问题提出了新的参数化解决方案,将动态规划法与Best2First策略相结合,有效地降低了原有搜索算法的时间/空间复杂度。PengZhao2hui等人[11]针对搜索结果的显示问题,提出了一种新的聚类方法———TreeCluster。该方法包含模式聚类和关键字聚类两个步骤,将同一主题的搜索结果归入同一个cluster中,为用户提供了一种根据cluster的描述方便地选择感兴趣结果的方式。2007年,HeHao等人[12]提出一种新的双层索引机制Bi2level索引,很好地减小了逆向搜索的时间代价。LuoYi等人[13]在研究现状由于关系数据库是使用最为广泛的数据库,也是DeepWeb的主要构成部分,基于关键字的关系数据库搜索主要也是针对关系数据库进行的。纵观近十年来该领域的研究成果,可以分为三个阶段:a)第一阶段是对基础理论和算法的研究,包括对关系数据库的建模、系统实现的体系结构和搜索排序算法的研究。1998年,R.Goldman等人[2]首先将信息检索中的邻域搜索方法引入数据库中,在学术界掀起了数据库搜索引擎的研究热潮。2002年,S.Agrawal等人[3]针对关系数据库实现了一...