BFASTDC：挖掘拒绝约束的位运算算法

# BFASTDC：挖掘拒绝约束的位运算算法 在数据处理和分析领域，挖掘拒绝约束（Denial Constraints，DCs）是一项重要任务。传统的FASTDC算法在计算证据集时存在较高的计算成本，而BFASTDC算法通过位运算的方式有效降低了这一成本。下面将详细介绍相关算法及其实验结果。 ## 1. FASTDC算法及改进 ### 1.1 FASTDC算法核心 FASTDC算法使用深度优先搜索（DFS）树来寻找最小覆盖。为了优化搜索过程，会优先将覆盖证据集更多元素的谓词添加到路径中。当发现最小覆盖时，推理系统会修剪DFS中不必要的分支。树的任何路径都是一个候选覆盖，它标识了一个尚未覆盖的元素集 $E_{path} \subset E_r$。当候选覆盖包含一个谓词 $P$ 时，包含 $P$ 的元素会从其对应的 $E_{path}$ 中移除。当 $E_{path}$ 中没有更多谓词时，该分支的搜索停止。如果候选覆盖满足最小性属性且 $E_{path}$ 为空，则它是最小覆盖。 ### 1.2 改进算法 FASTDC的作者还提出了两种改进算法：A - FASTDC和C - FASTDC。 - **A - FASTDC**：用于发现近似DCs，即违反次数有界的DCs。该算法使用与FASTDC相同的证据集 $E_r$，但修改了最小覆盖搜索以适应近似级别 $\epsilon$。搜索优先考虑出现在 $E_r$ 中最频繁谓词组中的谓词。当搜索树的分支的谓词覆盖频繁谓词组时，搜索停止。这意味着未在搜索中使用的谓词组的频率低于阈值 $\epsilon |r| (|r| - 1)$。 - **C - FASTDC**：用于发现具有常量谓词的DCs。它从属性域构建一个常量谓词空间，然后采用Apriori方法来识别 $\tau$ - 频繁常量谓词组。如果 $\frac{|sup(C, r)|}{|r|} \geq \tau$，则常量谓词组 $C$ 是 $\tau$ - 频繁的，其中 $sup(C, r)$ 是满足 $C$ 所有谓词的元组集。当识别出 $\tau$ - 频繁谓词组 $C$ 时，FASTDC会发现 $sup(C, r)$ 上的变量谓词，并输出 $C$ 和变量谓词的组合作为DCs。 ### 1.3 FASTDC的挑战 FASTDC通过对关系 $r$ 的每对元组评估谓词空间 $P$ 中的每个谓词来构建证据集。这种计算需要 $|P| \times |r|^2$ 次谓词评估，如果考虑谓词组 $\{P, P, ...\}$，至少一半的评估结果为假。接下来介绍的BFASTDC算法旨在降低这种计算成本。 ## 2. BFASTDC算法 ### 2.1 数据结构 #### 2.1.1 属性 - 值映射 属性值被组织为条目 $\langle k, l \rangle$，其中键 $k$ 是属性 $A_j$ 中值集的一个元素，$l$ 是一个元组标识符列表，使得 $\forall id \in l$ 都有 $t_{id}[A_j] = k$。`Search(Aj, k)` 过程用于在 $A_j$ 中查找 $k$ 对应的列表 $l$。`Predecessors(Aj, k)` 用于数值属性，它返回由与小于 $k$ 的值 $k_2$ 相关联的 `Search(Aj, k2)` 列表组成的集合 $L_2$。需要注意的是，如果没有找到与 $k$ 相关联的元组标识符，`Search(Aj, k)` 和 `Predecessors(Aj, k)` 可能返回 $\varnothing$。 #### 2.1.2 位向量 位向量 $B$ 与谓词 $P$ 相关联，用于表示 $P$ 与满足 $P$ 的元组对之间的关系。一个大小为 $|r|$ 的关系实例会生成元组对：$(t_0, t_0), (t_0, t_1), ..., (t_{|r|}, t_{|r|})$。以下函数返回给定元组对 $(t_{\mu}, t_{\nu})$ 的唯一标识符 $\lambda$： $\lambda(t_{\mu}, t_{\nu}, r) = (|r| \mu) + \nu$ 只有当 $\lambda$ 对应于满足 $P$ 的元组对时，位向量 $B$ 在位置 $\lambda$ 处才为 1，否则为 0。 例如，考虑谓词 $P_5 : t_x.Manager = t_y.Manager$ 和关系 `employees`。在样本中，谓词 $P_5$ 由元组对 $(t_0, t_3)$ 和 $(t_3, t_0)$ 满足。假设实例大小 $|employees| = 4$，通过函数计算可得 $\lambda(t_0, t_3, employees) = 3$ 和 $\lambda(t_3, t_0, employees) = 12$，这些 $\lambda$ 就是位向量 $B_5$ 为真的索引。 ### 2.2 构建位向量 #### 2.2.1 谓词形式说明 谓词涉及一个或两个属性，通常为 $\{A_1\}$ 和 $\{A_1, A_2\}$，并且可以针对两个元组 $(t_x, t_y)$ 或一个元组 $(t_x, t_x)$ 定义。用 $P_{\alpha}$ 和 $P_{\beta}$ 分别区分二元组和单元组谓词。设 $P_{w_o}$ 是一个带有运算符 $w_o$ 的谓词，$w_o \in W : \{=, \neq, <, \leq, >, \geq\}$。例如，$P_{w_1}^{\alpha} : t_x.A_1 = t_y.A_1$ 是一个关于属性 $\{A_1\}$ 的二元组相等谓词，$P_{w_2}^{\beta} : t_x.A_1 \neq t_x.A_2$ 是一个关于属性 $\{A_1, A_2\}$ 的单元组不等谓词。为了简化（不）相等谓词的表示，当 $o = 1$ 和 $o = 2$ 时，假设 $\overline{P}_{\alpha} \equiv P_{w_1}^{\alpha}$，$\underline{P}_{\alpha} \equiv P_{w_2}^{\alpha}$，$\overline{P}_{\beta} \equiv P_{w_1}^{\beta}$，$\underline{P}_{\beta} \equiv P_{w_2}^{\beta}$。 逻辑运算足以设置一些位向量，但需要辅助位掩码来防止位向量 $B$ 持有错误值。例如，位掩码 $mask_{st} = (z_1, ..., z_{|r|})$，其中 $z_n = 10^{|r|}$，有助于单元组谓词的操作，因为如果 $t_{\mu} \neq t_{\nu}$，单元组谓词与元组对 $(t_{\mu}, t_{\nu})$ 无关。类似地，位掩码 $mask_{tt} = (z_1, ..., z_{|r|})$，其中 $z_n = 01^{|r|}$，有助于二元组谓词的操作，因为如果 $t_{\mu} = t_{\nu}$，二元组谓词与元组对 $(t_{\mu}, t_{\nu})$ 无关。 #### 2.2.2 构建策略 下面介绍四种构建与谓词空间 $P$ 相关的位向量集 $B$ 的策略，每个 $B \in B$ 初始都填充为 0。 1. **涉及一个分类属性的谓词** - 对于形式为 $\overline{P}_{\alpha} : \{t_x.A_1 = t_y.A_1\}$ 的谓词及其关联的位向量 $\overline{B}_{\alpha}$，给定 $A_1$ 中的一个条目 $\langle k, l \rangle$ 且 $|l| > 1$，从 $l$ 中取出的两个元素的排列表示满足 $\overline{P}_{\alpha}$ 的元组对 $(t_{\mu}, t_{\nu})$。根据函数 $\lambda$，这些排列生成的元组对标识符 $\lambda$ 处，位向量 $\overline{B}_{\alpha}$ 被设置为 1，即 $\overline{B}_{\alpha, \lambda} \leftarrow 1$。 - 对于谓词 $\underline{P}_{\alpha} : \{t_x.A \neq t_y.A\}$ 及其关联的位向量 $\underline{B}_{\alpha}$，$\underline{B}_{\alpha}$ 是 $\overline{B}_{\alpha}$ 的逻辑补。因此，$\underline{B}_{\alpha}$ 通过析取（$\vee$）和异或操作（$\oplus$）得到：$\underline{B}_{\alpha} \leftarrow (\underline{B}_{\alpha} \vee mask_{tt}) \oplus \overline{B}_{\alpha}$。 2. **涉及两个分类属性的谓词** - 假设要在 `employees` 中找到从 `Name` 属性值到 `Manager` 属性值的关联。`Name` 中的条目 $\langle Jim, \{2\} \rangle$ 和 `Manager` 中的