計算一組FD的閉包算法

我正在尋找一個易於理解的算法來計算（手動）一組函數依賴關係的閉包。包括我的教練在內的一些消息來源說，我應該和阿姆斯特朗的公理一起玩，看看我能得到什麼。對我而言，這不是一個系統的方法（即容易錯過某些東西）。計算一組FD的閉包算法

我們的課程教科書（數據庫系統 - 完整的書，第二版）也沒有給出這個算法。

2013-06-11 dbmonster

這實際上似乎是一個相當有趣的問題，這可能是動態規劃可以利用的。 – RBarryYoung

如果通過「遊戲」，他的意思是徹底搜索，那麼決不是這種系統性的;）一個簡單的解決方案可能看起來像是逐個規則地依賴於一組依賴的迭代擴展只是要重新審視的項目隊列和幾個（兩個？）循環..你試過了嗎？

Btw。 google搜索我立即發現http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter6/node12.html - 但我無法驗證它是否合理，因爲我的筆記本電腦電池真的要壞了！

來源

2013-06-11 19:43:06 quetzalcoatl

+1：這是一個很好的參考頁面，但它沒有解釋如何枚舉閉包。 – RBarryYoung

不，玩意味着試驗和錯誤:)你的鏈接再次涉及阿姆斯壯公理。我如何知道何時停止應用它們？ – dbmonster

簡單地說：只要在前一次迭代中發生了任何變化，就可以迭代應用它們。當應用它們時，它們在當前狀態下不會改變任何東西（即'（A - > ABCDEF）+ =（ADEF）==>（A - > ABCDEF）'，所以沒有新的符號被添加到該集合中），那麼它也就是說，沒有進一步的擴張將其擴大，所以我認爲這是假設沒有更多增長的組合完成的一點。 – quetzalcoatl

爲了使它更加「系統化」，這可能是您正在尋找的算法。使用前三個阿姆斯特朗的公理：

閉幕= S
環
- 按照每個F在S，適用反思和擴充規則
- 添加新的文件描述符的封閉
- 對於每個S中的一對FD應用傳遞規則
- 將新的Fd添加到關閉
直到關閉不再改變任何'

我從this presentation notes採取。然而，我發現下面的方法比較容易的方式來實現：

/* F是設置X
- 計算每個屬性組FDS */
- F⁺的=空集
- 對於F
- X的閉合X⁺用於X⁺每個屬性A
  - 的添加到F⁺的FD：X - >甲
返回F⁺

其從here

來源

2014-02-07 20:23:39

。：第二個註釋http://www.cse.cuhk.edu.hk/~taoyf/course/bmeg3120/notes/fd2.pdf有一個顯示FD +計算的例子。你能否告訴我爲什麼'ACD-> A'類FD沒有關閉。 – coderredoc

的集合中的所有的屬性取功能由α一組的FD F的下測定。

例如。假設我們有這些起始FD，並且我們想要使用下面的一次計算所有閉包。

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

更多的FD通過上述本一次

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

同樣+，d +，（AC）+，（AB）+ ...等

有我們可以計算進行計算：C一個非常簡單的alg。來計算所有的FD集雖然

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-22 01:14:00 AbhimanyuAryan

計算一組FD的閉包算法

回答

相關問題