基于关系数据库的关键词搜索系统的研究

摘要

随着Web服务的发展和网络上的数据量呈几何式的增长,人们认识到将关系数据库和信息检索的技术融合到一起可以给用户提供更高效的信息检索服务。
　　 论文讨论了在关系数据库上进行基于q个关键词(k1,k2,k3,…,kq)的搜索方法。这里的关系数据库可以被建模为带权图模型G(V,E)。其中的V是指图上的结点(即数据库中的元组)；E是指数据图上的边,它表示的是元组间的外主键关联。假设Si表示一组包含关键词ki的结点,并且Si∈V。我们研究的问题是怎样找到权重最小的k个结果树,并且结果树要包含每个集合Si中的至少一个结点。当k等于1时,该问题等价于最小斯坦纳树问题(Steiner Tree Problem),该问题是NP难的。
　　 该问题还有两个前提,即关键词的个数q很小,因为用户一般不会输入过多的关键词；而且图中的边的数目m和结点数的关系,通常满足不等式m<　　 基于上述特性,本文最主要的工作是提出了一个在数据图上进行关键词搜索的算法,并以此为基础,实现了适用于带权数据图模型的关键词搜索系统DBSearch。通过本文的实验可以看到,该系统在搜索时间和结果质量上,比实验中的其他系统都有所提升。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景

1.2 相关工作

1.2.1 结果定义

1.2.2 打分函数

1.2.3 查询算法

1.2.4 查询结果呈现

1.2.5 其他方向

1.3 论文的研究内容及其组织结构

第二章 查询模型

2.1 数据图

2.2 查询与查询结果

2.2.1 查询与候选元组集

2.2.2 查询结果

2.3 打分函数

2.3.1 结点权重的计算

2.3.2 边权重的计算

2.3.3 相关性得分的计算

第三章 体系结构

3.1 预处理模块

3.2 查询处理模块

3.3 结果展示模块

第四章 搜索算法

4.1 搜索算法的框架

4.1.1 数据结构

4.1.2 算法框架

4.2 扩展操作

4.3 实验结果

4.3.1 扩展性实验

4.3.2 关键词数目的变化

第五章 结论

5.1 总结

5.2 展望

参考文献

致谢