数据完整性模型及评估算法的研究

摘要

随着现代信息技术的发展,数据信息呈现急剧的增长趋势,但是数据信息丰富的同时,其中往往伴随着数据质量问题,质量差的数据严重地影响了信息在数字化社会的作用。错误的理解信息,会给人们带来极大的损失。因此数据质量问题是迫切需要解决的问题,数据质量的相关问题也成为了研究的热点。
　　不完整的数据的处理是数据质量问题中常见的问题之一,如何评价数据的完整性,是数据质量研究中的基本问题之一。现有的数据完整性推理方法不能全面的反映数据集合的完整性,同时需要参考额外的完整性信息。现有的完整度计算方法,没有考虑数据集合中的空值可以被集合中其它值填充的特性,因而往往低估了数据集合的完整性。本文针对不完整数据的完整性计算问题,提出了一种可以适用于不同应用的数据完整性计算模型,这个模型由属性值完整性,元组完整性,关系完整性来刻画不同粒度的完整性。通过定义不同的计算函数,可以根据不同的应用来反映三者间的关系。其中属性值的完整性是模型的基础。通过使用函数依赖,可以判断属性值的完整性的真实情况,因而可以真实的评估数据集合的完整程度。在此模型的基础上研究了数据完整性的评估问题,并形式化地定义了这个问题,通过分析不同应用的限制,给出了这个问题的下界,当给出模型中的具体的计算函数时,给出了到达此下界的精确评估算法。为了应对海量数据完整性评估的挑战,提出了基于均匀抽样的数据完整性近似评估算法,理论分析表明这个算法可以满足任意的相对误差精度。通过在抽样方法中采用水库抽样机制,可以提高近似算法评估未知数据集合的完整性的效率,并证明了这种机制同样能保证近似算法的结果能够达到任意给定的误差精度。通过在真实数据集合上的实验证明了本文提出完整性模型能够反映数据集合真实的完整程度,以及精确算法的高效性,同时近似算法的实验结果也显示出近似算法的结果能够控制在给定的相对误差范围内。通过合成数据上的实验分析了精确算法和近似算法在不同空值分布上的数据集合上运行的性能,并分析了在不同应用限制下的算法的选择。

目录

封面

中文摘要

英文摘要

目录

第1章 绪论

第2章 预备知识

第3章 数据完整性模型和评估问题的下界

第4章 数据完整性的评估算法

结论

参考文献

声明

致谢