数据库细化 - F 的最小覆盖（无关属性）

Question

模式 R = (A, B, C, D, E, F)

FD F = {ABC → D、CD-> B、BCF→ D、CDF-> BE、BCDF-> E}

找到 Fc，F 的最小覆盖（又名规范覆盖）。

这是我书中使用的方法：

示例：abc -> xyz

a 是冗余的（无关的）如果 (bc)+ bas a;如果 (abc)+ Axis x 则 x 是冗余的。

注意：这里，闭包是使用 F 计算的，其中 a 或 x 被从 abc -> 中删除。分别是xyz。

我不明白最后一个粗体句子。

一种解决方案是：

考虑 CDF -> BE

B 是多余的： (CDF)+ = (CDFBE) bas (B)

F 变为 { ABC -> D、CD-> B、BCF→ D、CDF-> E}

但我不明白。

根据这个逻辑：

E 也可以是冗余的，

因为：

考虑 CDF -> BE

E 是冗余的： (CDF)+ = (CDFBE) bas (E)

F 变为 { ABC -> D、CD-> B、BCF→ D、CDF-> B}

我知道我必须忽略一些重要的标准。谁能告诉我那是什么？

Answer 1

如果 r(R) 是定义函数依赖集 F 的关系模式，则 R 中的属性 A 与函数依赖关系 x->Y 无关

if A belongs to X and A is extraneous then
  (F - {X->Y}) U {(X-A) -> Y} is equivalent to F

if A belongs to Y and A is extraneous then
  F is equivalent to (F - {X->Y}) U {X -> (Y-A)}

要计算 A 是否与 X 无关

1. Find (X-A)+ under F
2. If Y is a subset of (X-A)+ under F then A is extraneous

想法是检查如果我们可以获取该函数依赖项左侧被删除的属性，并且仍然能够通过 F 中的其他函数依赖项来导出它。如果是，那么 A 是多余的，因为它可以从其他 FD 中推断出来。

计算 A 是否与 Y 无关

1. Find F' = (F - {X->Y}) U {X -> (Y-A)}
2. Find X+ under F'

3. 如果 F' 下的 X+ 包含 A，则 A 与 Y 无关

这里，我们从左侧删除 A，并检查是否可以从具有以下属性的 FD 集合中推断出删除的属性： A 从这个中删除。一种模拟，如果我们有 FD {X -> (YA)} 并与集合 F 中的其他 FS 一起找到该模拟 FD 下 X 的闭包。如果我们看到 X+ 包含从原始属性中删除的属性，那么它在原始集合中是多余的，因此我们将 A 声明为与 Y 无关的属性，并保留删除 A 的集合，我们将其称为 F'，因为 F' 具有与 F 相同的闭包。

请注意，我们不会像秒的情况那样用删除的 A 来计算 F'。这是因为 (XA) 是 X 的子集，因此在属性闭包计算的某个步骤中，F 下的 (XA)+ 始终会生成 (XA) UY。这与我们构造 F' = (F - {X->Y}) U {(XA) -> Y 相同。 Y} 并计算该 F' 下 (XA) 的闭包，因为 (XA) 是其自身的子集，并且 F' 中修改后的 FD 也将计算为 (XA) U Y。这就是如果 A 属于的原因X ，我们不计算 F'。虽然我们可以，但这对闭包计算没有影响。

另一方面，当A属于Y时，我们必须计算从Y中删除A的F'，这是因为当我们在F'下找到X+时，我们在一步中得到XU（YA），并且如果我们找到X的闭包在 F 下我们得到 XUY，这是没有意义的，因为它只是计算 X 在其原始集合下的闭包，从中我们无法判断某些属性是否无关。

简单地，检查是否可以从集合中的其他 FD 推断出删除的属性。从原始集合中删除目标FD，并检查是否可以从其他属性中逻辑推断出删除的FD的删除属性。阿姆斯特朗公理也可以应用。

请注意，如果两个属性与左侧或右侧的 FD 无关，则无法同时删除这两个属性。在这种情况下，会生成两个 FD，每个 FD 都删除了一个无关属性。正如您的示例中

F = {ABC ->; D、CD-> B、BCF→ D、CDF-> BE、BCDF-> E}
由于CDF->BE，B是无关的，E也是无关的。所以这产生了两种可能性：
F1 = {ABC ->; D、CD-> B、BCF→ D、CDF-> B、BCDF-> E}
F2 = {ABC ->; D、CD-> B、BCF→ D、CDF-> E、BCDF→ E} （在这里您也可以删除 CDF->E，因为 BCDF->E 意味着 CDF->E）

您可以找到一组函数依赖关系的多个规范覆盖/最小覆盖。所以它并不独特。您不需要跟踪这样生成的所有可能性。就选一个吧。

根据快速计算，这是我发现的规范覆盖/最小覆盖：

Fc = {AC->D, CD->B, CF->DE}

如果还有其他问题，请告诉我们。

编辑1：

考虑一下

r(A, B, C)

，FD集合是

 F = {A->BC, B->AC, C->AB}

在这里你可以看到在F下，B与A->BC<无关/代码>。此外，“C”与 F 下的 A->BC 无关。但你不能同时删除两者，因为当你发现 B 与 A->BC 无关时，你已经删除了 B，结果是在 A->C 中，现在您有了一个新的函数依赖集：F1 = {A->C, B->AC, C->AB}F1 = {A->C, B->AC, C->AB} code> 其中 C 与集合 F1 下的 A->C 不无关。每删除一步都会获得一组新的 FD，在其下您可以查找下一个选定的属性是否无关。

上面的例子非常有趣，因为你可以从中得到 4 个规范封面，如下所示。

                                         A->BC
                                         B->AC
                                         C->AB
                                           |
                         +-----------------+-----------------+
                         |                                   |
                       A->C                                A->B
                       B->AC                               B->AC
                       C->AB                               C->AB
                         |                                   |
                +--------+--------+                 +--------+--------+
                |                 |                 |                 |
              A->C            +---+---+         +---+---+           A->B
              B->A            | A->C  |         | A->B  |           B->AC
              C->AB           | B->C  |         | B->AC |           C->A
                |             | C->AB |         | C->B  |             |
                +             +-------+         +-------+         +---+---+
                |             |  Fc2  |         |  Fc3  |         | A->B  |
            +---+---+         +-------+         +-------+         | B->C  |
            | A->C  |                                             | C->A  |
            | B->A  |                                             +-------+
            | C->B  |                                             |  Fc4  |
            +-------+                                             +-------+
            |  Fc1  |
            +-------+

注意树是如何形成的，通过不同的删除可能性，以及相对于它所在的最新 FD 的无关属性的计算。我的意思是你不能删除 FD A->BC因为 B 和 C 与 F 下的 A->BC 无关，因为删除 B 会生成另一个 FD与A->C（一个分支）并从A->BC中删除C形成另一组FD，其具有A->B（另一个分支）。