本站原创
摘要：联系数据库用来存储结构化数据,并利用SQL语言对数据进行查询,这种方式需要用户掌握这种语言的语法以及数据库的方式知识,由此对用户来说门槛比较高。而互联网上信息检索常常利用关键字查询的方式,这种方式简单、易用,受到普通用户的欢迎。由此,在联系数据库上进行关键字查询已经成为近来数据库领域的探讨热点。现有的探讨工作绝大部分都是用单个元组作为结果单元,我们通过对探讨的总结浅析,发掘出将多个元组的组合作为结果单元将会给用户带来更大的实际价值,由此本论文提出了联系数据库上基于组的关键字查询的概念。这里的组即为多个元组的组合。利用倒排索引技术,首先我们想到了直接的解决办法,枚举查询关键字倒排链表的所有元组的组合,再去除不满足查询限制条件的那些组,最后去除结果集中的冗余。这种Naive算法效率低下,因为它搜索了不足的所有解空间,计算复杂度很高,由此有时候常常出现无法计算出结果的情况。针对Naive算法有着的不足我们深入浅析了算法的计算历程,做出了一些重要的观察,提出了一些剪枝对策：去除包含所有关键字的元组,提前利用限制条件,保持最优候选集。在整合这些对策的时候,我们尽可能地减少算法的计算量,最后得到一个启发式的优化算法。优化算法不再搜索不足的所有解,而是通过部分搜索加上判断来减少枚举的次数,以而减少计算复杂度。我们增加了对于结果的排序处理,通过我们观察的性质将结果按照合理的顺序排序,利用户对查询结果更加满意。最后通过真实数据集和人工数据集上进行的一系列实验,验证了优化算法的查询时间在绝大部分情况下均优于Naive算法。关键词：元组组合论文组查询论文倒排链表论文关键字查询数据库论文
摘要5-6
Abstract6-8
第一章 绪论8-12
1.1 结构化查询和关键字查询8-9
1.2 本论文工作和贡献9-11
1.3 文章结构11-12
第二章 背景知识和相关工作12-19
2.1 结构化查询和关键字查询的技术12-15
2.1.1 结构化查询12-13
2.1.2 关键字查询13-15
2.2 联系数据库与关键字查询结合的必要性15-16
2.3 相关工作16-18
2.4 本章小结18-19
第三章 不足定义19-23
3.1 不足场景19-21
3.2 不足形式和定义21-22
3.3 本章小结22-23
第四章 查询结果排序23-28
4.1 排序的必要23
4.2 浅析如何排序23-26
4.3 排序算法26-27
4.4 本章小结27-28
第五章 不足初步求解28-33
5.1 初步浅析28-29
5.2 Naive算法29-31
5.3 本章小结31-33
第六章 不足优化33-41
6.1 深入浅析33-36
6.1.1 去除包含所有关键字的元组33-34
6.1.2 提前利用查询中的限定条件34-35
6.1.3 保持最优候选集35-36
6.2 优化算法36-40
6.3 本章小结40-41
第七章 实验结果与浅析41-50
7.1 实验环境41
7.2 实验结果41-48
7.2.1 真实数据集DBLP上的结果41-44
7.2.2 人工数据集上的结果44-48
7.3 实验浅析48-49
7.4 本章小结49-50
第八章 总结与展望50-51