Source: Fast Algorithms for Denial Constraint Discovery, VLDB 2022.
动机：手工设定 DCs 费时费力，且可能出错，因此有一些工作提出了自动发现 DCs 的算法。
问题：现有算法遵循两步骤（1）从 records 构建 intermediate 数据结构（2）从 intermediate 枚举（enumerate）DCs. 但是现有算法在计算 intermediates 时效率较低。
intro 里举了一个 DC 的例子：
Overall, DCs are essential building blocks in quantifying database inconsistency [18], being at the core of several state-of-the-art data cleaning systems [6, 9, 24].
这个很有用，用于说明 DCs 的重要性和广泛应用。
The higher the expressive power of a constraint type, the higher the computational complexity of its discovery.
这个也特别有用，可以用来回答”为什么不选择比 DCs 更 general 的表示方法“，因为表达能力的提高，伴随着自动发现这些 rules 的复杂度的增大。具体地，
- 对于 FD，复杂性在元组数方面是二次的，在列数方面是指数级的
- 对于 DC，在元组数上仍然是二次的，但在谓词（predicate）数上是指数的，更加复杂
- 对于 approximate DCs，其发现过程相较于 exact DCs 更加 expensive
- approximate DC（又名 partial DC），在一定比例的数据上成立即可，无需在全部数据上成立
Sec.2.1
对于 approximate DC 而言，需要一个函数来度量“近似性”，本文采用了一个最常用的：
即发生 violations 占可能的 tuples paris 的比例。
Sec2.2 DC discovery
第一步：构建可能的 predicate space
- 这一步里，需要用到 predicate restrictions 来减少无意义的 predicates；具体地，对于 categorical 的列，只考虑
$=, \neq$ 关系，对于 numeric 的列，考虑全部$=, \neq, <\ \leq, >, \geq$ 关系；跨两个不同列时，仅当两列类型相同，且列里的值重叠度高于阈值时才考虑。
对于下面这个 employee 的表：
构建出的 predicate 空间如下：
第二步：构建 evidence set
-
给定一对 tuples
$t,t'$ ，其 evidence 指的是在这对 tuples 上成立的 predicates 的子集，形式化而言：$e_{t, t'} = {p | p \in P, t, t' \models p}$ - 例如：对于
$t_1, t_2$ 而言，其 evidence$e_{t_1, t_2}={p_2, p_4, p_6, p_9, p_{10}, p_{11}, p_{13}, p_{15}}$
- 例如：对于
-
evidence set
$E_r$ 则是全部可能的 tuples pairs 的 evidences 的集合。现实中，不同的 tuples pairs 可能产生相同的 evidence，因此 evidence set 一般比全部可能的 tuples pairs 数小很多。
第三步：DC 枚举（enumeration）
- DC discovery 与枚举超图（hypergraph）中的命中集（hitting sets）有关：谓词空间作为顶点集，而每个 evidence 作为一个超图的 edge
- 思路是，如果一个 DC
$\varphi$ 是 valid，那么就不存在 tuples pair$t, t'$ 满足$\varphi$ 的全部 predicates - 而由于 evidence set 包含全部可能的 tuples pairs 的 evidence（满足的 predicates 集合）
- 因此，可以验证 evidence set 中的任意元素
$e$ 不包含$\varphi$ 的全部 predicates
- 思路是，如果一个 DC
- 可见，枚举 DC 对于列数的复杂度是呈指数的
结论
- DC 能够从数据中自动化地发现，且有效率优化方法