计算一组FD的闭合的算法 [英] algorithm for computing closure of a set of FDs

问题描述

我正在寻找一种易于理解的算法来（手动）计算一组功能依赖项的闭包。
包括我的老师在内的一些消息来源说，我应该只玩阿姆斯特朗的公理，看看能得到什么。对我来说，这不是系统的方法（即容易遗漏）。

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.

推荐答案

如果用播放表示穷举搜索，那么这绝对不是not-systematic;）并且一个简单的解决方案看起来像是在逐条规则的基础上迭代依赖集的迭代扩展*）似乎只是一堆要重新讨论的项目和一些（两个？）循环。您尝试过吗？

If by "play" he meant an exhaustive search, then in no way this is not-systematic ;) And a simple solution could look like iterative expansion*) of the set of dependencies on the rule-by-rule basis seems to be just a queue of items to be revisited and a few (two?) loops.. Have you tried it?

顺便说一句。我在Google上四处搜寻，立即发现 http：// www .cs.sfu.ca / CourseCentral / 354 / zaiane / material / notes / Chapter6 / node12.html -但我无法验证是否合理，因为笔记本电脑中的电池实际上已经没电了！

Btw. googling around I immediatelly found http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter6/node12.html - but I cannot verify if it is reasonable because my battery in laptop is literally going down!

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

*) Simply: apply them iteratively as long as anything has changed in the previous iteration. When applying ALL of them does not change anything in the current state (i.e. (A -> ABCDEF) += (ADEF) ==> (A -> ABCDEF) so no new symbol was added to the set), then it means, well, that no further expansions expand it furhter, so I think that's the point to assume the no-more-growing set to be complete.

这篇关于计算一组FD的闭合的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！