5

I'm looking for an easy to understand algorithm to compute (by hand) a closure of a set of functional dependencies. Some sources, including my instructor says I should just play with Armstrong's axioms and see what I can get at. To me, that's not a systematic way about doing it (i.e. easy to miss something).

Our course textbook (DB systems - the complete book, 2nd ed) doesn't give an algorithm for this either.

4

3 回答 3

1

在 FD 集合 F 下由 α 函数确定的所有属性的集合。

例如。假设我们有这些起始 FD，并且我们想使用下面的方法计算所有的闭包。

A -> BC 
AC -> D
D -> B
AB -> D

以上计算的更多FDs存在一次

A+ -> (A,B,C,D)
B+ -> (B)

同样我们可以计算C+、D+、(AC)+、(AB)+等等...

有一个非常简单的算法。计算所有的FDs

RESULT <- α
MODIFIED <- TRUE

WHILE(MODIFIED) {
   MODIFIED <- FALSE
   ∀ FD A->B IN F DO{
       IF A ⊂ RESULT {
           RESULT <- (RESULT) ∪ (B)
              MODIFIED <- TRUE IF RESULT CHANGES
       }
   }
}
于 2015-04-22T01:14:00.503 回答
1

用更“系统”的方式说，这可能是您正在寻找的算法。使用前三个阿姆斯壮公理：

  • 闭包 = S
  • 环形
    • 对于 S 中的每个 F，应用反身性和扩充性规则
    • 将新的 FD 添加到闭包中
    • 对于 S 中的每一对 FD，应用传递性规则
    • 将新的 Fd 添加到 Closure
  • 直到关闭不再改变`

我从这个演示笔记中得到的。但是，我发现以下方法更容易实现：

  • /*F 是一组 FD */
  • F⁺ = 空集
  • 对于每个属性集 X
    • 计算 X 在 F 上的闭包 X⁺
    • 对于 X⁺ 中的每个属性 A
      • 将 FD 添加到 F⁺：X -> A
  • 返回 F⁺</li>

取自这里

于 2014-02-07T20:23:39.653 回答
0

如果他所说的“玩”是指详尽的搜索，那么这绝不是不系统的；）而且一个简单的解决方案可能看起来像逐条规则基础上的一组依赖项的迭代扩展*）似乎只是要重新访问的项目队列和几个（两个？）循环..你试过吗？

顺便提一句。谷歌搜索我立即发现http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter6/node12.html - 但我无法验证这是否合理，因为我的笔记本电脑电池实际上正在下降！

*) 简单地说：只要在上一次迭代中发生任何变化，就迭代地应用它们。当应用所有它们时，它们不会改变当前状态的任何东西（即 (A -> ABCDEF) += (ADEF) ==> (A -> ABCDEF) 所以没有新符号被添加到集合中），那么这意味着，好吧，没有进一步的扩展进一步扩展它，所以我认为这是假设不再增长的集合是完整的。

于 2013-06-11T19:43:06.233 回答