论文部分内容阅读
近年来，随着数据规模快速增长，数据质量问题日益凸显，已经成为数据库领域的重要研究方向。不一致性是数据质量问题中的一个重要方面，数据质量规则是处理数据不一致性的重要工具。为检测和修复不一致数据，各种约束规则被提出来，包括函数依赖、条件函数依赖、编辑规则以及修复规则等，这些数据质量规则大多规定元组在某些属性上的值能在一定程度上提供该元组在其他属性上值的信息。现有规则都描述宏观不一致性，也就是将每个属性值看做一个不可分割的整体，这也是符合关系数据库的设计规范的。然而在大量的实际应用中，一些属性值中的某一部分就能确定其他属性值，而现有数据质量规则尚未考虑这类重要信息。为了将这类微观信息加以利用，本文提出了一种新的数据质量规则：微函数依赖，用于处理数据中的微观不一致性。围绕数据的宏观不一致性，现有研究主要包括规则的定义及分析、规则的自动挖掘、基于规则检测数据的不一致性，以及基于规则修复数据的不一致性等问题。类似的，本文关于数据微观不一致性的研究也从这四个方面展开：
首先，为描述微观不一致性，提出了微函数依赖的概念。通过引入提取函数，对微函数依赖进行语法和语义的定义，并研究其基本性质，包括可满足性、蕴含性以及公理系统。可满足性用于判断给定的微函数依赖集是否合法。蕴含性用于判断给定的微函数依赖集是否包含冗余。公理系统是对应蕴含问题的若干推理规则，本文证明了可满足性以及蕴含性的判定问题分别是NP-完全和CoNP-完全的，对可满足性问题分析了其可近似性，最后给出了正确且完备的公理系统。
其次，本文研究了特定类型微函数依赖的挖掘问题。由于实际应用中大多数的“微信息”都存在于字符串类型的属性值的某一片段中，因此本文只考虑字符串属性上的微函数依赖。这种微函数依赖的约束前件为正则表达式加位置下标的形式。本文通过将字符串按照字符相似性进行聚类和对齐，并归纳成正则表达式形式。聚类过程和对齐过程都是微函数依赖挖掘中的关键步骤，本文证明对齐问题是NP-完全的，并提出一个自底向上的基于合并操作的贪心算法。该贪心算法的优点是能够同时完成聚类和对齐操作，且不需要对聚类问题指定任何参数；其缺点是时间复杂度依然很高。为降低算法运行时间，本文还提出了一些裁剪策略以提升算法效率，并给出理论保障。在多组真实数据和合成数据上的实验结果表明，本文所提挖掘算法能挖出有意义的微函数依赖，裁剪策略也能大幅度提升算法性能。
再次，本文利用微函数依赖的特性，研究了外存数据对多条依赖违反情况检测的问题。本文研究基于聚簇的数据微观不一致性的检测算法，外存数据的聚簇算法一般通过排序实现。当数据量很大时，通常需要对数据进行多次读写操作。为了降低数据的读写次数，本文结合微函数依赖的特性，研究有多条待检测依赖情况下的中间结果的共享技术。根据适用条件的不同，给出了两个检测任务之间的三种共享技术。在检测任务很多的情况下，形式化定义了以最小化磁盘读写总代价为目标的多检测任务的调度问题。文章证明该调度问题是NP-完全的，并给出了有近似比保证的基于贪心的启发式调度算法。通过实验，证明了本文所提共享技术能很大程度的降低数据读写次数，提升不一致数据的检测速度。
最后，本文研究了数据微观不一致性的修复问题，同时考虑了数据源之间的宏观不一致性和数据源内部的微观不一致性，前者对应基于真值发现的方法，后者对应基于规则的修复。目前真值发现和数据修复的研究都是独立进行，而很多应用场景下两个问题可能同时存在，在同一个框架中同时考虑两个问题会使分析更加全面。本文提出了一个基于模式分解的方法，在真值发现框架下同时解决数据中违反主键约束的宏观不一致性和违反微函数依赖的微观不一致性，以尽可能的改善数据质量。首先给出了基于微函数依赖的模式分解规则，将关系型数据转换为“源-键-值”的三元组作为真值发现问题的输入。在计算真值发现框架中数据源权重以及候选值的得分时，利用对微函数依赖的违反情况给出相应的计算公式，这些公式中考虑了比以往算法更全面的信息。最后对真值发现的输出进行后处理，得到的最终结果直接满足主键约束以及微函数依赖。在真实数据以及合成数据上的实验结果表明了算法的效果和效率。
首先，为描述微观不一致性，提出了微函数依赖的概念。通过引入提取函数，对微函数依赖进行语法和语义的定义，并研究其基本性质，包括可满足性、蕴含性以及公理系统。可满足性用于判断给定的微函数依赖集是否合法。蕴含性用于判断给定的微函数依赖集是否包含冗余。公理系统是对应蕴含问题的若干推理规则，本文证明了可满足性以及蕴含性的判定问题分别是NP-完全和CoNP-完全的，对可满足性问题分析了其可近似性，最后给出了正确且完备的公理系统。
其次，本文研究了特定类型微函数依赖的挖掘问题。由于实际应用中大多数的“微信息”都存在于字符串类型的属性值的某一片段中，因此本文只考虑字符串属性上的微函数依赖。这种微函数依赖的约束前件为正则表达式加位置下标的形式。本文通过将字符串按照字符相似性进行聚类和对齐，并归纳成正则表达式形式。聚类过程和对齐过程都是微函数依赖挖掘中的关键步骤，本文证明对齐问题是NP-完全的，并提出一个自底向上的基于合并操作的贪心算法。该贪心算法的优点是能够同时完成聚类和对齐操作，且不需要对聚类问题指定任何参数；其缺点是时间复杂度依然很高。为降低算法运行时间，本文还提出了一些裁剪策略以提升算法效率，并给出理论保障。在多组真实数据和合成数据上的实验结果表明，本文所提挖掘算法能挖出有意义的微函数依赖，裁剪策略也能大幅度提升算法性能。
再次，本文利用微函数依赖的特性，研究了外存数据对多条依赖违反情况检测的问题。本文研究基于聚簇的数据微观不一致性的检测算法，外存数据的聚簇算法一般通过排序实现。当数据量很大时，通常需要对数据进行多次读写操作。为了降低数据的读写次数，本文结合微函数依赖的特性，研究有多条待检测依赖情况下的中间结果的共享技术。根据适用条件的不同，给出了两个检测任务之间的三种共享技术。在检测任务很多的情况下，形式化定义了以最小化磁盘读写总代价为目标的多检测任务的调度问题。文章证明该调度问题是NP-完全的，并给出了有近似比保证的基于贪心的启发式调度算法。通过实验，证明了本文所提共享技术能很大程度的降低数据读写次数，提升不一致数据的检测速度。
最后，本文研究了数据微观不一致性的修复问题，同时考虑了数据源之间的宏观不一致性和数据源内部的微观不一致性，前者对应基于真值发现的方法，后者对应基于规则的修复。目前真值发现和数据修复的研究都是独立进行，而很多应用场景下两个问题可能同时存在，在同一个框架中同时考虑两个问题会使分析更加全面。本文提出了一个基于模式分解的方法，在真值发现框架下同时解决数据中违反主键约束的宏观不一致性和违反微函数依赖的微观不一致性，以尽可能的改善数据质量。首先给出了基于微函数依赖的模式分解规则，将关系型数据转换为“源-键-值”的三元组作为真值发现问题的输入。在计算真值发现框架中数据源权重以及候选值的得分时，利用对微函数依赖的违反情况给出相应的计算公式，这些公式中考虑了比以往算法更全面的信息。最后对真值发现的输出进行后处理，得到的最终结果直接满足主键约束以及微函数依赖。在真实数据以及合成数据上的实验结果表明了算法的效果和效率。