2

假设我使用 BDD 来表示关系中的元组集。为简单起见，考虑具有 0 或 1 值的元组。例如：R = {<0,0,1>, <1,0,1>, <0,0,0>} 表示 BDD 中的三元关系，它具有三个变量，例如 x、y 和 z（一个用于每个元组的元素）。我想要的是实现一个操作，给定一个像 R 的 bdd 和一个多维数据集 C 在 C 中的变量被抽象时返回包含唯一元组的 R 的子集。

例如，如果 C 包含变量 x（表示每个元组中的第一个元素），则函数的结果必须是 {<0,0,0>}。请注意，当 x 被抽象出来时，元组 <0,0,1> 和 <1,0,1> 变得“相同”。

现在假设 R = {<0,0,1>, <1,0,1>, <0,0,0>, <1,0,0>} 我们想再次抽象 x。在这种情况下，我希望结果是常量 false，因为在抽象 x 之后 R 中没有唯一的元组。

非常感谢任何帮助。

4

1 回答 1

1

这可以通过三个简单的步骤完成：

  • 使用要抽象的变量的限制值制作两个 BDD：
    • R[x=0] = 用 x = 0 限制 R
    • R[x=1] = 用 x = 1 限制 R
  • 对这个新的 BDD 应用XOR操作
    • Q = R[x=0] xor R[​​x=1]
  • 枚举Q的所有模型

将此应用于您的示例：

  • R = {<0,0,1>, <1,0,1>, <0,0,0>} = (¬x ∧ ¬y ∧ z) ∨ (x ∧ ¬y ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z)
  • R[x=1] = {<0,1>} = (¬y ∧ z)
  • R[x=0] = {<0,1>,<0,0>} = (¬y ∧ z) ∨ (¬y ∧ ¬z)
  • Q = R[x=1] xor R[​​x=0] = (¬y ∧ ¬z)

这里的直觉是 XOR 将取消两个 BDD 中出现的条目。
这很容易（但具有指数复杂性）推广到具有几个抽象变量的情况。

于 2014-04-02T11:29:02.190 回答