概率关系查询评估与Top-k查询技术研究

论文摘要

在信息检索、传感器数据和图像识别中,其数据的发生都是不确定性的,而传统数据库都是确定性的,不能对不确定性信息进行处理,因而概率数据库的研究也显得越来越重要。本文通过分析概率数据库模型,讨论了目前概率关系模型的不能进行合理投影操作等缺点。把概率关系中的元组重新分类,定义了两类不同的元组,对于不同的元组进行不同的投影操作顺序,得到较为合理的投影结果。由于不同的查询方案和不同操作顺序,都可能导致查询线性时间内不可计算或者计算得到是错误的结果,本文对概率关系里的不同元组定义了不同的操作顺序,提出了概率关系有效查询的算法。对于连接查询,若满足相互不相容投影,本文采用先进行不相容投影；若还满足相互独立投影,本文提出了再次进行相互独立投影；若连接查询可以分为两个分别是线性时间内可计算的查询,本文采用了把此查询分解为两个线性查询,并用连接标记符将两个查询连接起来。本文基于传统的Top-k语义在概率数据库中提出了新的概率方法Top-K和排序聚集查询方法。若通用处理方法支持两种类型的查询,并利用现有RDBMS的查询处理和索引能力,本文实现了Top-k计算。为了能够更好的计算结果,对原概率关系进行了编码。本文包含一个总的空间模型和有效的搜索算法来计算查询的结果,以减少元组的访问和规模实现搜索空间来计算查询的答案。实验表明,提出的算法都是在线性时间内可计算的,并且算法执行的效果与数据相互之间的关联性相关。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 课题研究的背景
• 1.2 课题研究的现状
• 1.3 课题研究的意义
• 1.4 本文的主要工作
• 1.5 论文的结构安排
• 第2章 概率关系概述
• 2.1 概率关系的广泛应用
• 2.1.1 现代企业中的应用
• 2.1.2 传感器数据流
• 2.1.3 数据流数据库
• 2.2 概率关系模型
• 2.2.1 概率理论基础
• 2.2.2 概率关系基本定义
• 2.2.3 概率关系基本操作
• 2.3 概率关系查询技术
• 2.3.1 概率关系查询基础
• 2.3.2 概率关系连接查询
• 2.3.3 概率关系空值处理
• 2.4 本章小结
• 第3章 概率关系有效查询的评估
• 3.1 概率关系可能世界
• 3.2 概率关系的元组操作
• 3.2.1 概率关系的元组分类
• 3.2.2 合并操作
• 3.2.3 概率关系代数
• 3.3 查询的有效评估
• 3.3.1 有效查询评估算法
• 3.3.2 实验过程及分析
• 3.4 本章小结
• 第4章 概率关系中Top-k查询技术的研究
• 4.1 Top-k查询概述
• 4.1.1 Top-k聚集查询的应用
• 4.1.2 基本思想概述
• 4.2 Top-k相关问题
• 4.2.1 相关简单规则
• 4.2.2 U-Topk查询
• 4.2.3 U-k Ranks查询
• 4.2.4 Top-k概率聚集查询
• 4.3不确定的Top-k概率查询
• 4.3.1 查询空间
• 4.3.2 生成查询空间
• 4.3.3 概率Top-k聚集查询
• 4.4 Top-k实现算法及实验分析
• 4.4.1 概率关系转换过程
• 4.4.2 U-Topk查询算法
• 4.4.3 U-k Ranks查询算法
• 4.4.4 实验分析
• 4.5 本章小结
• 结论
• 参考文献
• 致谢