包含完整性约束的概率关系数据库更新和查询优化方法研究

摘要

随着数据清洗、传感器网络、追踪移动物体等应用对不确定数据的管理要求越来越高，概率关系数据模型作为一个对不确定数据进行有效管理的重要模型，自2003年开始引起学术界和工业界开始高度关注。从形式上说，一个概率关系数据库是一组传统关系数据库上（可能世界）的概率分布，而完整性约束是关系数据上的重要信息，因此，提出一个包含完整性约束的概率关系数据库模型，并研究该模型上的更新与查询方法具有重要意义。
　　针对目前大部分的不确定数据模型研究着重于描述具体数据之间的约束关系，而没有考虑模式级别的约束关系的问题，提出了一个包含完整性约束的概率关系数据库模型。不确定数据模式级别的完整性约束信息能捕捉动态更新下的数据间的关联关系，因此，利用基于约束的概率关系数据库更新，自动更新数据间的关联关系，有效防止了概率关系数据库包含不合理的可能世界的发生。由于现有将不确定数据从可能世界集合表示方式转化为基于变量的表示方式的数据模型转化方法导致元组表达式十分冗长，通过分析元组表达式的生成规则，提出了一个高效的数据模型转化方法。该转化方法基于一个消除表达式中重复变量的公式，减少了后续查询在处理元组表达式的计算开销。实验表明该数据模型转化方法在没有增加额外时间开销的前提下，大大简化了元组表达式，且提高了后续查询的处理效率。
　　为了解决目前基于约束的概率关系数据库更新方法枚举概率关系数据库中元组的表达式里出现的所有变量的取值，而导致的高时间复杂度的问题，提出了一个高效的更新方法。该方法只需考虑在约束中出现的变量取值，且采用变量替换机制更新元组的表达式，避免了概率关系数据库中其他变量的参与。实验表明该方法在各种参数配置下，都优于现有的更新方法。
　　针对目前基于约束的概率关系数据库更新方法，在获取相关变量满足约束的取值集合这个十分耗时的重要步骤中，没有考虑针对常见的函数依赖约束的特征进行优化的问题，提出了两种更新优化策略。剪枝策略将相关元组的表达式单独遍历，避免了遍历一个由各相关元组表达式组合而成的复杂表达式，减少了遍历到的变量数量，从而减少了获取相关变量满足约束的取值集合的时间。在剪枝策略的基础上，变量消除策略合并多个满足约束且对应相同可能世界的变量取值来最小化新生成的变量数目，利于后续的查询处理。实验结果表明剪枝策略能进一步提高基于约束的概率关系数据库更新方法的效率，而变量消除策略能在不带来额外开销的情况下减少新生成的变量数量。
　　针对目前大部分的概率关系数据库上的一般查询优化方法着重于研究加速查询结果世系逻辑表达式，而没有考虑在查询处理过程中生成简化的结果世系表达式的问题，提出了一个利用模式级别的约束信息来简化查询结果世系数据表达式的优化方法。分别利用函数依赖约束和引用完整性约束这两种模式级别的信息对两种关系操作的世系数据给出了简化的生成方式。假设查询对于概率关系数据库有重要应用价值。为了避免目前基于生成新数据库版本通用处理方法会带来额外更新开销的问题，提出了一种利用条件概率来处理假设查询的优化方法。该方法通过计算结果在假设条件下的条件概率，避免了不必要的概率关系数据库更新。实验结果验证了一般查询优化方法和假设查询优化方法的有效性。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 存在的问题分析

1.4 本文研究的主要内容

1.5 论文的组织结构

2 概率关系数据库的数据模型

2.1 引言

2.2 包含完整性约束的数据模型

2.3 模型的可能世界语义

2.4 模型中完整性约束的效用

2.5 数据模型转化方式

2.6 实验评估

2.7 本章小结

3 基于约束的概率关系数据库更新方法

3.1 引言

3.2 C based更新方法

3.3 获取满足约束的取值集合

3.4 变量表的更新

3.5 数据表的更新

3.6 基于约束的更新算法

3.7 实验评估

3.8 本章小结

4 函数依赖约束的更新优化策略

4.1 引言

4.2 针对函数依赖约束的剪枝策略

4.3 针对函数依赖约束的变量消除策略

4.4 实验评估

4.5 本章小结

5 概率关系数据库上的查询优化

5.1 引言

5.2 模式级别约束下的一般查询优化策略

5.3 假设查询优化策略

5.4 时间复杂度分析

5.5 实验评估

5.6 本章小结

6 全文总结和研究展望

6.1 全文总结

6.2 研究展望

致谢

参考文献

附录1 攻读学位期间发表论文目录

附录2 攻读博士学位期间参加课题目录