数据库细化 - F的最小覆盖（无关属性） [英] database refinement - minimal cover of F (extraneous attributes)
问题描述
FD F = {ABC - > D，CD - > B，BCF - > D，CDF - > BE，BCDF - > E}
查找Fc，F的最小封面（也称为规范封面）。
这是我的书中使用的方法：
示例：abc - > xyz
a是多余的（无关）if（bc）+⊇a; （abc）+⊇x。
注意：这里，使用F计算闭包，其中a或x被删除从abc - > xyz。
我不明白最后一个粗体句。
一个解决方案是：
考虑CDF - > BE
B 是多余的：（CDF）+ =（CDFBE）⊇（ B ）
F成为{ABC - > D，CD - > B，BCF - > D， CDF - > E }
但我不明白。
根据这个逻辑：
E也可以是冗余的，
coz：
考虑CDF - > BE
E 是多余的：（CDF）+ =（CDFBE）⊇（ E ）
F成为{ABC - > D，CD - > B ，BCF - > D， CDF - > B }
我知道我必须忽略一些重要的标准。有谁能告诉我这是什么？
如果r（R）是定义了一组功能依赖关系F的关系模式， R与功能依赖关系x-> Y
如果A属于X，而A是无关的，那么
F - {X> Y}）U {（XA）→& Y}等价于F
如果A属于Y，而A是无关的，则
F等同于（F - {X> Y}）U {X - > （YA）}
计算A是否与X无关
1。在F
下找到（XA）+ 2.如果Y是F下的（XA）+的子集，则A是无关的
这个想法是检查我们是否可以获取该功能依赖关系左侧的已删除属性，并且仍然可以使用F内的其他功能依赖来导出它。如果是，则A是冗余的，因为它可以从其他FD推断。
计算A是否与Y无关
1。找到F'=（F - {X> Y}）U {X - > （Y-A）}
2.在F'
下找到X + 3。如果F'下的X +包含A，则A与Y无关
这里，从左侧删除A，并检查是否可以从从这一个中删除了一组FD。如果我们具有FD {X - >（Y-A）}并且与集合F中的其他FS并且在该模拟FD下找到X的关闭，那么可以进行仿真。如果我们看到X +包含原始的属性，那么在原始集合中它是多余的，因此我们将A声明为与Y无关，并将集合删除A（称为F'），因为F'具有与F相同的关闭。
请注意，我们不会像秒钟一样使用删除的A来计算F'。这是因为（X-A）是X的子集，因此，在属性关闭计算的某个步骤中，F下的（X-A）+将总是使（X-A）U Y。这就好像我们构造了F'=（F - {X - Y}）U {（XA）→Y}，并计算出这个F'下的（XA）的闭包，因为（XA）是一个子集并且F'中的修改的FD也将计算为（XA）U Y。这是如果A属于X的原因，则不计算F'。虽然我们可以，但是在闭包计算中并不会有所不同。
另一方面，当A属于Y时，我们必须计算出从Y开始，这是因为当我们在F'下找到X +时，我们在一个步骤中得到XU（YA），如果我们在F下找到X的关闭，我们得到XUY，这是没有意义的，因为它只是计算X的关闭在其原始集合下，我们无法确定某些属性是否是无关紧要的。
只需检查是否可以从集合中的其他FD推断删除的属性。从原始集中删除目标FD，并检查是否可以从其他属性逻辑地推断删除的FD的已删除属性。请注意，如果两个属性与左侧或右侧的FD无关，那么您不能同时删除这两个属性，因此可以使用阿姆斯壮的公理。
在这种情况下，生成两个FD，每个FD都被删除了一个无关属性。在你的例子中
F = {ABC - > D，CD - > B，BCF - > D，CDF - > BE，BCDF - >因为 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}
如果还有更多问题，请告诉我们。
EDIT1：
考虑
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} 其中 C 不是外来的到 A-> C 在集合 F1 之下。删除的每个步骤都可以获得一组新的FD，在这种情况下，您会发现下一个选定的属性是否是无关的。
上面的例子非常有趣，因为你可以从中获得4个规范的封面，如下所示。
A-> BC
B-&AC AC b $ b 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 与 A-> BC 无关F，因为删除 B 生成另一个FD，具有 A-> C （一个分支）和删除 C 从 A-> BC 形成另一组FD，其具有 A-> B （另一个分支）。
Schema R = (A, B, C, D, E, F)
FD F = {ABC -> D, CD -> B, BCF -> D, CDF -> BE, BCDF -> E}
Find Fc, the minimal cover (aka. canonical cover) of F.
This is the method using in my book:
Example: abc -> xyz
a is redundant (extraneous) if (bc)+ ⊇ a; x is redundant if (abc)+ ⊇ x.
NOTE: Here, the closures are computed using F, with a or x being deleted from abc -> xyz respectively.
I don't understand the last bold sentence.
one solution is:
Consider CDF -> BE
B is redundant: (CDF)+ = (CDFBE) ⊇ (B)
F becomes { ABC -> D, CD -> B, BCF -> D, CDF -> E}
but I don't understand.
according to this logic:
E can be redundant too,
coz:
Consider CDF -> BE
E is redundant: (CDF)+ = (CDFBE) ⊇ (E)
F becomes { ABC -> D, CD -> B, BCF -> D, CDF -> B}
I know I must overlook some important criteria. Can anyone tell me what is that?
If r(R) is a relational schema on which the set of functional dependencies F is defined, then an attribute A in R is extraneous to the functional dependency 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)}
To compute if A is extraneous to X
1. Find (X-A)+ under F
2. If Y is a subset of (X-A)+ under F then A is extraneous
The idea is to check if we can acquire the removed attribute on the left hand side of this functional dependency and still be able to derive it with the other functional dependencies inside F. If yes then A is redundant, as it can be inferred from other FDs.
To compute if A is extraneous to Y
1. Find F' = (F - {X->Y}) U {X -> (Y-A)}
2. Find X+ under F'
3. If X+ under F' contains A then A is extraneous to Y
Here, we remove A from the left hand side, and check if the removed attribute can be inferred from the set of FDs which has A removed from this one. Kind of simulation that if we have the FD {X -> (Y-A)} and with the other FSs in the set F and finding the closure of X under this simulated FD. If we see that X+ contains the removed attribute from the original one then it was redundant in the original set, and thus we declare A as extraneous to Y and keep the set with removed A, which we call F', because F' has the same closure as F.
Note that we do not compute F' with the removed A as in the seconds case. This is because (X-A) is a subset of X and thus, (X-A)+ under F will always make (X-A) U Y in some step of attribute closure computation. This is the same as if we constructed F' = (F - {X->Y}) U {(X-A) -> Y} and computed the closure of (X-A) under this F', as (X-A) is a subset to itself, and the modified FD in F' will also compute into (X-A) U Y. This is the cause if A belongs to X , we do not compute F'. Although we could, but it does not make difference in the closure computation.
On the other hand when A belongs to Y, we have to compute the F' with A removed from Y, this is because when we find X+ under F' we get X U (Y-A) in a step, and if we find closure of X under F we get X U Y, that does not make sense, as it simply computes the closure of X under its original set from which we cannot tell if some attribute is extraneous.
Simply, check that if a removed attribute can be inferred from other FDs in the set. Remove the target FD from the original set, and check if you can logically infer the removed attribute of the removed FD from other attribute. Armstrong's Axioms could also be applied.
Note that if two attributes are extraneous to an FD on the left hand side or the right hand side, then you cannot remove both. In this case two FDs are generated, each one with, one of the extraneous attribute removed. As in your example
F = {ABC -> D, CD -> B, BCF -> D, CDF -> BE, BCDF -> E}
because of CDF->BE, B is extraneous and also E is extraneous. So this generates two possibilities:
F1 = {ABC -> D, CD -> B, BCF -> D, CDF -> B, BCDF -> E}
F2 = {ABC -> D, CD -> B, BCF -> D, CDF -> E, BCDF -> E} (here you can remove CDF->E also as BCDF->E implies CDF->E)
You can find more than one Canonical Cover/Minimal Cover of a set of functional dependencies. So it is not unique. You do not need to keep track to all the possibilities that is generated like this. Just pick one.
AS per a quick calculation here is what i found as he canonical cover/minimal cover:
Fc = {AC->D, CD->B, CF->DE}
Let us know if there is some more problem.
EDIT1:
Consider
r(A, B, C)
and the set of FDs is
F = {A->BC, B->AC, C->AB}
Here you see that under F, B is extraneous to A->BC. Also 'C' is extraneous to A->BC under F. But you cannot remove both, because when you find B is extraneous to A->BC , you have already remove B, and which results in A->C, and you now have a new functional dependency set: F1 = {A->C, B->AC, C->AB} where C in not extraneous to A->C under the set F1. Each step of removal gets you a new set of FD, under which you find if the next selected attribute is extraneous or not.
The above example is very interesting, as you can get 4 canonical cover from it as shown below.
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 |
+-------+
Note how the tree is formed, by the different possibilities of removal, and the calculation of extraneous attributes with respect to the latest FD which it is in. I mean you cannot remove the FD A->BC because B and C is extraneous to A->BC under F, because removal of B generates another FD with A->C (one branch) and removal of C from A->BC forms another set of FD which has A->B (another branch).
这篇关于数据库细化 - F的最小覆盖（无关属性）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
