数值属性错误检测与NFDs技术解析

### 数值属性错误检测与NFDs技术解析 #### 1. NFDs概述与推理 NFDs（Numeric Functional Dependencies）是一种强大的数据质量规则工具，它能够检测CFDs（Conditional Functional Dependencies）所能捕捉的所有错误，还能检测CFDs无法检测的数值属性错误。从表达能力上看，NFDs严格强于CFDs，它不仅包含了CFDs的功能，还能指定数值属性之间的算术关系，而这些是CFDs无法表达的。 在使用NFDs作为数据质量规则时，需要考虑两个经典问题： - **可满足性问题**：给定一组依赖关系Σ，判断是否存在一个非空实例D，使得D满足Σ。该分析用于检查规则是否存在冲突，帮助我们找出规则中的问题。 - **蕴含问题**：给定Σ和另一个依赖关系ϕ，判断Σ是否蕴含ϕ。如果Σ蕴含ϕ，那么使用Σ就足够了，无需再使用Σ∪{ϕ}，这样可以优化规则。 对于传统的函数依赖，任何有限子集都是可满足的，并且蕴含问题可以在线性时间内解决。但对于NFDs，情况变得复杂。为了理解这种复杂性的来源，我们引入了AFDs（Arithmetic Functional Dependencies），它是NFDs的一种特殊形式，条件为e op c，其中e是定义在数值属性上的线性算术表达式，c是常数。AFDs和CFDs不能相互表达。存在一组AFDs是不可满足的，即使所有属性的域是无限的；而CFDs不可满足时，必须定义在某些有限域的属性上。 例如，考虑关系模式R(A, B)，A和B具有无限整数域，Σ由两个AFDs φ1 = (TP, T ′C1)和φ2 = (TP, T ′C2)组成，TP由单个元组(x, y)组成，T ′C1的条件是x - y = 0，T ′C2的条件是y - x > 0。那么不存在非空实例D使得D满足Σ，因为对于任何实例D中的元组t，φ1要求t[A] = t[B]，而φ2要求t[A] ≠ t[B]。 不过，好消息是NFDs相对于CFDs增加的表达能力并没有增加静态分析的复杂度。对于NFDs，可满足性问题是NP完全的，蕴含问题是coNP完全的；对于AFDs，可满足性和蕴含问题也分别是NP完全和coNP完全的。 #### 2. NFDs可满足性和蕴含问题的证明 - **NFDs证明**： - 下界：由于CFDs是NFDs的特殊情况，NFDs的可满足性和蕴含问题的下界与CFDs相同。 - 上界：如果NFDs允许任意算术表达式，可满足性问题将是不可判定的，因此我们将算术表达式限制为线性。对于可满足性问题，NFDs具有小模型属性，即如果存在一个非空实例满足Σ，那么存在一个由单个元组t0组成的实例D0满足Σ，并且只需要考虑t0的属性值来自一个由属性域和Σ中的常数确定的有限域。基于此，可以开发一个NP算法进行可满足性检查： 1. 从有限域中猜测一个元组t0。 2. 检查{t0}是否满足Σ。 - 对于蕴含问题，通过建立一个由两个元组组成的小模型属性，可以证明它是coNP的。 - **AFDs证明**： - 上界：由于AFDs是NFDs的特殊情况，其上界与NFDs相同。 - 下界：可满足性问题的下界通过从NP完全的线性整数规划问题（LIP）归约得到；蕴含问题的下界通过从LIP的补问题归约得到。 #### 3. 在SQL中验证NFDs 我们引入NFDs的目的是检测数据不一致性。下面介绍一种在关系型DBMS中使用SQL检测NFDs违规的技术。 给定一组定义在关系模式R上的NFDs Σ、R的一个实例D和Σ中的一个NFD ϕ = (Tp, Tc)，其中Tp由两个模式元组p1和p2组成，Tc是条件e op z。如果存在一个元组t′ ∈ D，使得{t, t′}不满足ϕ，即要么t⊵p1且t′ ⊵p2，要么t′ ⊵p1且t⊵p2，但不满足e op z，则称元组t ∈ D是ϕ的一个违规元组。错误检测问题就是找到D中所有违反Σ中某些NFD的元组集合vio(Σ, D)。 主要结果如下： - 对于任何定义在模式R上的NFD ϕ，存在一个SQL查询Qϕ，对于R的任何实例D，Qϕ(D)返回D中所有违反ϕ的元组。 - 对于任何定义在R上的NFD集合Σ和R的任何实例D，vio(Σ, D)可以在最多O(||Σ|||D|2)时间内计算，其中||Σ||是Σ的基数，|D|是D的大小。 为了证明上述结果，我们展示如何从ϕ自动生成Qϕ。假设ϕ = (Tp, Tc)，Tp = {p1, p2}，Tc是条件e op z，则Qϕ为： ```sql select t from R t, R t′ where(Ω1(t, t′, p1, p2) and C1(t, t′, e, z)) or (Ω2(t, t′, p1, p2) and C2(t, t′, e, z)) ``` 其中，Ω1(t, t′, p1, p2)将t ⊵p1和t′ ⊵p2编码为SQL中的合取项，对于R的每个属性A： - 如果p1[A]是常数c，则t[A] = c是一个项；同理，t′[A] = c也是一个项。 - 如果p1[A]和p2[A]是相同的变量xA，则t[A] = t′[A]是一个项。 C1(t, t′, e, z)通过将t和t′的属性替换e或z中的变量来编码¬(e op z)。Ω2(t, t′, p1, p2)和C2(