论文部分内容阅读
数据不完整是web异构数据库、多关系数据库和时空数据库中普遍存在的问题。Skyline查询作为一种能够满足用户多目标决策需求的数据库操作，在多目标实时决策系统、数据挖掘、电子商务和推荐系统等领域中有着巨大的应用价值。目前非完整数据库中的Skyline查询存在着支配性丢失和结果集过小或不具参考性等问题，概率Skyline可以有效解决上述问题，因而研究非完整数据库中的概率Skyline查询具有重要的意义。
针对当前非完整数据库概率Skyline查询研究在多关系、动态数据库和离散型数据上的不足，本文主要做了如下工作：
（1）目前非完整数据库中的概率Skyline查询仅关注于单关系的研究，并未考虑查询涉及到多关系的情况。本文对于非完整数据库中的概率Skyline查询定义进行了扩充，并提出能有效处理多关系 Skyline 查询的算法，该算法通过多层次分组、全局 Skyline 概率下界及局部Skyline上界对Skyline概率计算进行了高效的剪枝。通过多个维度与现有算法的对比，验证了算法的可用性。
（2）针对当前算法不能有效处理动态非完整数据库中的概率Skyline查询问题，本文给出了在数据集状态发生变化时更新Skyline概率的方法，并提出了一种在数据库状态发生变化时高效更新Skyline结果集的算法。该算法利用支配链与被支配链高效维护数据项的Skyline概率上界及Skyline概率。此外，利用预排序快速定位受影响数据集合，进一步提升算法效率。
（3）在解决连续型数据集中概率Skyline查询的基础上，进一步研究了离散型数据集中的Skyline查询问题。为非完整数据集中的离散型数据建立概率支配模型，基于该模型提出能有效处理离散型数据集Skyline查询的算法。该算法利用桶划分及Skyline概率上下界大幅减少了支配计算。此外，给出了一种缺失数据填充方法，并验证利用该填充方法可以预判数据项间的Skyline概率大小关系并减少支配计算，从而提高算法效率。
针对当前非完整数据库概率Skyline查询研究在多关系、动态数据库和离散型数据上的不足，本文主要做了如下工作：
（1）目前非完整数据库中的概率Skyline查询仅关注于单关系的研究，并未考虑查询涉及到多关系的情况。本文对于非完整数据库中的概率Skyline查询定义进行了扩充，并提出能有效处理多关系 Skyline 查询的算法，该算法通过多层次分组、全局 Skyline 概率下界及局部Skyline上界对Skyline概率计算进行了高效的剪枝。通过多个维度与现有算法的对比，验证了算法的可用性。
（2）针对当前算法不能有效处理动态非完整数据库中的概率Skyline查询问题，本文给出了在数据集状态发生变化时更新Skyline概率的方法，并提出了一种在数据库状态发生变化时高效更新Skyline结果集的算法。该算法利用支配链与被支配链高效维护数据项的Skyline概率上界及Skyline概率。此外，利用预排序快速定位受影响数据集合，进一步提升算法效率。
（3）在解决连续型数据集中概率Skyline查询的基础上，进一步研究了离散型数据集中的Skyline查询问题。为非完整数据集中的离散型数据建立概率支配模型，基于该模型提出能有效处理离散型数据集Skyline查询的算法。该算法利用桶划分及Skyline概率上下界大幅减少了支配计算。此外，给出了一种缺失数据填充方法，并验证利用该填充方法可以预判数据项间的Skyline概率大小关系并减少支配计算，从而提高算法效率。