关系数据库上基于组的关键字查询研究.pdf

《关系数据库上基于组的关键字查询研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关系数据库上基于组的关键字查询研究TheResearchofKeywordQueriesoverRelationalDatabasesBasedonTeam陶岳指导小组成员名单导师汪卫教授指导小组成员汪卫教授何震瀛讲师关系数据库上难于组的关键字杏洵研究S录录般3Abstract4第一章绪论61.1结构化查询和关键字查询61.2本文工作和贡献71.3文章结构9第二章背景知识和相关工作102.1结构化查询和关键字查询的技术102.1.1结构化查询102.1.2关键字查询112.2关系数据库与关键字查

2、询结合的必要性132.3相关工作142.4本章小结16第三章问题定义173.1问题场景173.2问题形式和定义193.3本章小结20第四章查询结果排序214.1排序的必要21■4.2分析如何排序214.3排序算法244.4本章小结25第五章问题初步求解265.1初步分析265.2Naive算法275.3本章小结29第六章问题优化316.1深入分析316.1.1去除包含所有关键字的元组316.1.2提前利用查询中的限定条件326.1.3保持最优候选集336.2优化算

3、法34关系数据库.h基于组的关键字査询研究H录6.3本章小结38第七章实验结果与分析397.1实验环境397.2实验结果397.2.1真实数据集DBLP上的结果397.2.2人工数据集上的结果427.3实验分析467.4本章小结47第八章总结与展望4849硕士研究生期间主要工作51翻t522>关系数据库上基于组的关键字査询研究摘要摘要关系数据库用来存储结构化数据，并使用SQL语言对数据进行查询，这种方式需要用户掌握这种语言的语法以及数据库的模式知识，因此对用户来说门槛比较高。而互联网上信

4、息检索常常使用关键字查询的方式，这种方式简单、易用，受到普通用户的欢迎。因此，在关系数据库上进行关键字查询已经成为近來数据库领域的研究热点。现有的研究工作绝大部分都是用单个元组作为结果单元，我们通过对研究的总结分析，发掘出将多个元组的组合作为结果单元将会给用户带来更大的实际价值，因此本文提出了关系数据库上基于组的关键字查询的概念。这里的组即为多个元组的组合。利用倒排索引技术，首先我们想到了直接的解决办法，枚举查询关键字倒排链表的所有元组的组合，再去除不满足查询限制条件的那些组，最后去除结果集中的冗余。这种Naive算法

5、效率低下，因为它搜索了问题的所有解空间，计算复杂度很高，因此有时候常常出现无法计算出结果的情况。针对Naive算法存在的问题我们深入分析了算法的计算过程，做出了一些重要的观察，提出了几点剪枝策略：去除包含所有关键字的元组，提前利用限制条件，保持最优候选集。在整合这些策略的时候，我们尽可能地减少算法的计算量，最后得到一个启发式的优化算法。优化算法不再搜索问题的所有解，而是通过部分搜索加上判断來减少枚举的次数，从而减少计算复杂度。我们增加了对于结果的排序处理，通过我们观察的性质将结果按照合理的顺序排序，使用户对查询结果更加

6、满意。最后通过真实数据集和人工数据集上进行的一系列实验，验证了优化算法的查询时间在绝大部分情况下均优于Naive算法。关键字：元组组合，组查询，倒排链表，关键字查询，关系数据库中图分类号：TP3923关系数据库

7、二基子组的关键字査洵研究AbstractAbstractRelationaldatabasesareusedtostorestructureddata,ausermustlearnhowtouseSQLandhavetheknowledgeofschemaofthedatabase,ifhewantstoque

8、ryinformationoverrelationaldatabases.Itisahighthresholdfortheuser.Atthesametime,keywordqueryisoftenusedtoretrieveinformationontheInternet,thisissimpleandeasytouse,andiswelcomedbycommonusers.Thus,Keywordqueryoverrelationaldatabaseshasattractedmuchinterestrecently

9、.Mostofworksbynowareaimedtoobtainindividualtuplestoanswerqueries.Weanalyzetheseresearchworks,andmakeanobservationthatusethecombinationofseveraltuplestoanswerquerieswi