第 1 章 绪论
1.1 研究目的与意义
在当今大数据信息爆炸时代，对信息进行获取在人类生活至关重要。信息的载体是数据，优秀的数据质量是各种数据分析能够得到有效结果的前提。为了使数据能够有效的满足所需要求，对数据提出准确无误的特征，能够给人类准确呈现现实世界的状况。在各种数据应用领域，数据质量是一个关系到应用系统成败的关键问题。而数据质量中的质量评估是数据管理时面临的第一个问题，同时也是可能会改变数据结果的一个重要因素。提高数据质量的策略多种多样，可以从不同的方面进行划分。其中数据质量可以由数据维度来衡量。文献[1]指出，数据质量维度是一组数据质量属性的集合，每一种属性代表着数据的某一特征。经Wang 和 Strong 等人调查研究报告显示，可以将这些数据质量属性分为 20 种不同的维度，根据这些维度将会从数据的不同角度对数据质量进行相应的评估，常用的数据质量维度包括准确性，完整性，时效性，一致性等。对各个维度来分析其“好”或“坏”是目前数据质量的评估方法。本文就将以一致性、完整性、准确性以及数据冗余这四个数据质量维度为基础进行数据的划分。我们将在 1.2 节中对这四个数据质量维度进行相关介绍。
...........................
1.2 数据质量维度
1.2.1 一致性
一致性是数据质量的核心衡量标准之一，当数据的值符合相应的数据模型所定义的一系列约束条件时，该数据是一致的。例，在表 1-1 中，t1-t6中 t1-t2为同一个人信息，t3-t4为同一人信息，t5，t6为另外两人的信息，图中我们可以看出，t1，t2的国家编号（CC），地区编号（AC），电话号码（PN），地址（STR），国家（CT）和邮编（ZIP）信息均相同，我们就可以说 t1和 t2为同一人。但是我们可以从图中信息看出在这些属性栏中，名字属性（NM）t1为 Mike 而 t2为 Rick，我们就可以说t1和 t2的数据是不一致的。现实世界中大多数都是脏数据，包含着不一致，冲突和错误。对于数据不一致，在现实生活中很常见，例如同一用户在不同网站上登记出生年月可能是不一样的。
在数据被用户高度重视的时代，为了得到更多或存储更多的数据，建设了大量的信息系统。由于这些信息系统是孤立建设和维护的，将出现无法避免的语义异构、数据不一致现象，造成孤立信息系统互操作的困难，使得信息孤岛现象尤为突出。就会出现在一组数据源中进行数据融合，不同数据源指代同一实体时包含错误或矛盾的数据，使得数据源选择难度增大，数据源的可靠性降低。目前关于数据不一致的研究主要在以下三个方面：（1）为了有效提高数据源选择的效率，需要先对数据源进行检测，检测出数据出现错误时是否存在数据不一致现象，（2）对数据不一致进行修复，（3）对不同的修复数据不一致的模型进行评估。在现如今的数据不一致检测方法中，最基本的方法为建立一组一致性规则，若数据集中存在不一致信息，则通过检测信息违反相应规则发现不一致信息。数据修复则是在尽可能减少修改数据的次数或频率，使得数据集合满足一致性规则。
1.2.2 完整性
完整性是对于一切实体的所有属性，其对应的值是否完整的程度[2]。如表1-2 中，t1和 t2表示同一实体的信息，将 t1和 t2进行对比，我们可以发现 t2缺失信息，所以我们可以说 t2是不完整的。不完整的信息一直个长期存在的问题，通常解决此问题是从数据库中找出缺少的关键信息。如，Master Data Management（MDM）是一个高质量数据的单一存储库，它为各种应用程序提供了企业核心业务实体的同步一致的视图，它是一个关于企业某方面的封闭数据库，如雇员和客户，这部分通常是关闭的，但是数据库的其他部分是开放的，如销售交易和服务记录。引起数据不完整性一般是数据集合中没有包含足够的信息来回答查询或进行知识发现。当前对不完整性的研究一般分为以下三个方面：（1）对数据不完整性的检测，（2）对数据不完整性的修复，（3）对数据不完整性方法的评估。
............................
第 2 章 预备知识
2.1 引言
本章主要介绍了本文所研究的问题中的数据类型，以及规则和需要用到的技术。本章的结构如下：2.1 节概述了数据源选择问题；2.2 节详细阐述了定义中提到的规则和技术；2.3 节详细阐述基于该规则的数据源选择问题的算法；2.4 节对全章的内容作了总结。
对于描述性的规则（约束）集合∑，数据集合 I 称为一致的，当且仅当满足 I╞ ∑，否则 I 称为不一致数据集。在 2.3 中介绍本文所需要用的规则。
........................
2.2布隆过滤器和最小哈希
2.2.1布隆过滤器（BloomFilter）
布隆过滤器是一个很长的二进制向量和 k 个哈希函数组成，用于在大数据集合中快速有效地判断元素是否在集合中。判断元素的过程如下：将过滤器中哈希函数与该元素对应的值位数组置 1，在查找元素中通过查找是否与所有哈希函数对应位都是 1 来判断元素是否存在，如果全为 1，说明该元素存在。
首先，我们先介绍布隆过滤器是如何用位数组表示集合的。
如图 2-1 所示，假设集合里面有 3 个元素{x，y，z},哈希函数的个数为 3。具体步骤如下：
1）将位数组初始化，每个位都置为 0。
2）将集合中每一个元素依次通过这几个哈希函数进行映射，映射后得到相应哈希值，将哈希值对应位数组上相关位置，将该位置置为 1。
3）判断 Y 元素是否处于集合中时，采用上述同样的方法将 Y 通过哈希函数映射到位数组上，得到相应位置的点，将该位置置为 1。
4）在判断过程中，如果有任意一个点不为 1，我们可以判断该元素一定不在集合中。相反，如果每个点均为 1，则该元素可能存在集合中。
..........................
第 3 章 基于函数依赖的数据源选择方法 ..............................15
3.1 引言 .........................15
3.2 问题定义 .......................... 17
3.3 算法介绍 .......................20
第 4 章 基于匹配依赖的数据源方法 ..................................31
4.1 引言 .......................31
4.2 问题定义 ..................... 33
4.3 算法分析 ............................ 35
第 4 章 基于匹配依赖的数据源方法
4.1 引言
第 3 章的算法考虑到了多个数据源基于函数依赖的数据源选择问题。而本章则基于另外一个规则，匹配依赖对数据源进行选择[40]。本章利用最小哈希对数据构造一级签名[41]，再利用布隆过滤器技术设计二级签名后进行数据源选择。 本文余下的部分将对此算法进行详细描述，4.2 节介绍问题定义和算法基本思想，4.3 节介绍该算法的理论基础，4.4 节给出算法实验。
第 3 章提出了一种基于函数依赖的数据源选择进行不一致性的检测算法。算法将待检测的目标数据集与一组数据集进行不一致性检测[42]，其中两个数据集在相同函数依赖条件下，将数据集中数据压缩[43]，通过布隆过滤器求两个数据集的交集。
匹配依赖是函数依赖的扩展，将数据从“精确匹配”扩展到“模糊匹配”[44]。本章提出一种基于匹配依赖的数据源选择算法，在更大程度上在同一条件下选取更多的数据信息，检测出更多的潜在错误。
..........................
结论
同一个实体在相同规则的不同数据源上可能表示为不同形式的数据信息。这些不一致信息会在我们进行数据质量管理中造成不便（如数据冗余，成本增高），导致在数据质量管理的可用性降低。不一致数据检测已经成为数据质量领域里重要的研究课题。
本文分析了现有的不一致检测工作，发现当前的工作主要考虑如何在检测数据是否违反规则下做不一致检测工作，而面对多个数据源内数据未违反规则，且在不耗费大量成本时，未能有较好地解决方法。为了能准确有效地解决这种情况，本文提出基于函数依赖和匹配依赖对数据源进行选择的方法。
本文首先介绍了函数依赖、匹配依赖和相关数据特征以及在算法中我们需要利用的相关技术。接着在第三章，本文提出基于函数依赖的数据源选择问题，在对真实数据和合成数据上，与近似最优 Greedy 进行效率和可扩展性的结果比较，证明了该算法的有效性。在第四章中，提出基于匹配依赖的数据源选择问题，并且进行了相关实验的比较，也证明了该算法的有效性。
由于时间有限，本文的方法仍存在缺点：在相关参数上还未达到更高的近似比，需要对算法进行近一步优化。
参考文献（略）