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

关系数据库上基于组的关键字查询研究
T h e R e s e ar ch o f K e yw o r d Q u er i e s
o v e r R e l a t i o n a l D a t a b a s e s
B a s e d o n T e a m
陶岳
指导小组成员名单
导师
汪卫教授
指导小组成员
汪卫教授
何震瀛讲师
关系数据库上难于组的关键字杏洵研究 S 录
录
般˺ꭓ 3
A b s t r a c t ˺ꭓ 4
第一章绪论˺ꭓ 6
1. 1 结构化查询和关键字查询˺ꭓ 6
本文工作和贡献˺ꭓ 7
1.˺ꭓ3 文章结构˺ꭓ 9
第二章背景知识和相关工作˺ꭓ 10
2.˺ꭓ1 结构化查询和关键字查询的技术˺ꭓ 10
2. 1. 1 结构化查询˺ꭓ 10
2. 关键字查询˺ꭓ 11
2. 2 关系数据库与关键字查询结合的必要性˺ꭓ 13
2.˺ꭓ3 相关工作˺ꭓ 14
2 .4 本章小结˺ꭓ 16
第三章问题定义˺ꭓ 17
3 . 1 问题场景˺ꭓ 17
3 .2 问题形式和定义˺ꭓ 19
3 .˺ꭓ3 本章小结˺ꭓ 2 0
第四章查询结果排序˺ꭓ 2 1
4 .˺ꭓ1 排序的必要˺ꭓ 2 1 ■
4 . 2 分析如何排序˺ꭓ 2 1
4 . 3 排序算法˺ꭓ 2 4
4 .˺ꭓ4 本章小结˺ꭓ 2 5
第五章问题初步求解˺ꭓ 26
5.˺ꭓ1 初步分析˺ꭓ 2 6
5 .2 Naive 算法˺ꭓ 27
5 .˺ꭓ3 本章小结˺ꭓ 29
第六章问题优化˺ꭓ 3 1
6.˺ꭓ1 深入分析˺ꭓ 3 1
6. 1. 1 去除包含所有关键字的元组˺ꭓ 3 1
6. 提前利用查询中的限定条件˺ꭓ 32
6. 保持最优候选集˺ꭓ 33
6 . 2 优化算法˺ꭓ 34
基于组的关键字査询研究˺ꭓ H 录
6.˺ꭓ3 本章小结˺ꭓ 38
第七章实验结果与分析˺ꭓ 39
7. 1 实验环境˺ꭓ 39
7.˺ꭓ2 实验结果˺ꭓ 39
7 . 2 . 1 真实数据集 DBLP 上的结果˺ꭓ 39
7 . 2 . 2 人工数据集上的结果˺ꭓ 4 2
7. 3 实验分析˺ꭓ 4 6
7. 4 本章小结˺ꭓ 4 7
第八章总结与展望˺ꭓ 4 8
˺ꭓ 4 9
硕士研究生期间主要工作˺ꭓ 5 1
翻 t˺ꭓ 52
2
>
关系数据库上基于组的关键字査询研究摘要
摘要
关系数据库用来存储结构化数据,并使用 SQL 语言对数据进行查询,这种方
式需要用户掌握这种语言的语法以及数据库的模式知识,因此对用户来说门槛比
较高。而互联网上信息检索常常使用关键字查询的方式,这种方式简单、易用,
受到普通用户的欢迎。因此,在关系数据库上进行关键字查询已经成为近來数据
库领域的研究热点。
现有的研究工作绝大部分都是用单个元组作为结果单元,我们通过对研究的
总结分析,发掘出将多个元组的组合作为结果单元将会给用户带来更大的实际价
值,因此本文提出了关系数据库上基于组的关键字查询的概念。这里的组即为多
个元组的组合。
利用倒排索引技术,首先我们想到了直接的解决办法,枚举查询关键字倒排
链表的所有元组的组合,再去除不满足查询限制条件的那些组,最后去除结果集
中的冗余。这种 Naive 算法效率低下,因为它搜索了问题的所有解空间,计算复
杂度很高, 因此有时候常常出现无法计算出结果的情况。
针对 Na ive 算法存在的问题我们深入分析了算法的计算过程,做出了一些重
要的观察,提出了几点剪枝策略:去除包含所有关键字的元组,提前利用限制条
件,保持最优候选集。在整合这些策略的时候,我们尽可能地减少算法的计算量,
最后得到一个启发式的优化算法。优化算法不再搜索问题的所有解,而是通过部
分搜索加上判断來减少枚举的次数,从而减少计算复杂度。
我们增加了对于结果的排序处理,通过我们观察的性质将结果按照合理的顺
序排序,使用户对查询结果更加满意。
最后通过真实数据集和人工数据集上进行的一系列实验,验证了优化算法的
查询时间在绝大部分情况下均优于 Na ive 算法。
关键字: 元组组合,组查询,倒排链