冉 艾 谈子敬

(复旦大学计算机科学与技术学院 上海 200433)

0 引 言

互联网的广泛使用使得数据集的来源变得多样化。很多用户参与内容生成或提供的数据集允许在互联网上传播和同步修改。比如维基百科、百度百科中词条的解释是面向全网开放编辑的，即允许所有网民进行自定义的修改。在上述操作过程中，数据的真实性或者准确性无法得到有效的保证。学术数据库或者知识图谱之中也经常出现错误论文信息，比如信息缺失或论文重复记录。数据一致性成了数据质量的一个重要指标之一。发现数据里的约束，再使用数据约束去修复数据集已经成了数据处理的基本流程。

数据约束对后续的数据处理非常重要，目前已有大量数据约束方面的研究。常见的数据约束包含字段级约束和表级约束。其中，字段级约束指只对单个元组或者单个字段有约束，比如域约束、检查约束等；表级约束指定义在两个元组间的多个字段的约束，常见有函数依赖、条件函数依赖、次序依赖和差分依赖等。在现实中，字段级约束与表级约束可以同时存在于同一个数据中，且数据间的关系不仅仅有等于或者不等，还有着大于、小于的次序关系。否定约束[1]是一个表达能力极强的数据依赖的形式，它满足了以上的需求。常见的域约束、主键约束、函数依赖、条件函数依赖和次序依赖等都可以转为相应的否定约束形式。

在数据约束的相关工作中，数据约束的发现是一个基础的问题。……