不同的最小覆盖可能的数量是多少?

huangapple go评论67阅读模式
英文:

The number of different minimal cover possible are?

问题

Sure, here are the translated portions:

"Consider R(A,B,C,D,E,F,G) be a relational schema with the following functional dependencies:
AC->G, D->EG, BC->D, CG->BD, ACD->B, CE->AG. The number of different minimal cover possible are___________?"

"Actually in this question we were supposed to find all the possible minimal covers. I used this video
So using that theory i tried doing this question but end up getting only 2 minimal covers and then answer given in my text book is 4 .
The minimal covers I got are:

D->E,D->G,BC->D,CG->D,AC->B(#),CE->A
2)
AC->G,D->E,D->G,BC->D,CG->D,CD->B(#),
CE->A

Actually the video gives only standard procedure to FIND a minimal cover. but the problem is a bit tricky as it asks about how MANY minimal covers we can find. I am applying the algorithm right...the only issue is that I am unable to find how many more minimal covers can be possible for the given set of FD's."

英文:

>Consider R(A,B,C,D,E,F,G) be a relational schema with the following functional dependencies:
AC->G, D->EG, BC->D, CG->BD, ACD->B, CE->AG. The number of different minimal cover possible are___________?
Actually in this question we were supposed to find all the possible minimal covers. I used this video
So using that theory i tried doing this question but end up getting only 2 minimal covers and then answer given in my text book is 4 .
The minimal covers I got are:
> 1)
D->E,D->G,BC->D,CG->D,AC->B(#),CE->A
> 2)
AC->G,D->E,D->G,BC->D,CG->D,CD->B(#),
CE->A
Actually the video gives only standard procedure to FIND a minimal cover. but the problem is a bit tricky as it asks about how MANY minimal covers we can find. I am applying the algorithm right...the only issue is that I am unable to find how many more minimal covers can be possible for the given set of FD's

答案1

得分: 1

常见的生成最小覆盖的算法包括三个步骤:

  1. 拆分右侧部分,生成只包含一个属性在右侧部分的函数依赖。

  2. 对于每个左侧部分包含多个属性的情况,尝试逐个删除每个属性,看剩余部分是否仍然能够确定右侧部分。如果可以,就从左侧部分中删除该属性。

  3. 对于每个剩余的依赖关系,尝试看是否可以被消除。

在您的情况下,第一步产生了以下结果:

F = { A C → G
A C D → B
B C → D
C G → B
C G → D
C E → A
C E → G
D → E
D → G }

在第二步中,我们必须检查前面七个依赖关系。对于每个依赖关系A1A2...An -> B,我们逐个尝试消除每个Ai,并查看剩余属性的闭包是否仍包含B(闭包是相对于F的)。在这种情况下,我们有两种可能性:从ACD -> B,我们可以消除AD。因此,现在我们有两组不同的依赖关系:

F1 = { A C → G
C D → B
B C → D
C G → B
C G → D
C E → A
C E → G
D → E
D → G }

F2 = { A C → G
A C → B
B C → D
C G → B
C G → D
C E → A
C E → G
D → E
D → G }

现在我们可以应用最后一步:对于每个依赖关系X -> A,我们可以看看A是否包含在X+中,X+是相对于所有其他依赖关系的闭包。在这种情况下,我们可以消除该依赖关系。

结果通常取决于我们应用这些检查的顺序。

在这里,有四种不同的规范覆盖:

G1 = { A C → G
B C → D
C G → B
C E → A
D → E
D → G }

G2 = { A C → G
B C → D
C G → D
C E → A
C D → B
D → E
D → G }

G3 = { A C → B
B C → D
C G → B
C E → A
D → E
D → G }

G4 = { A C → B
B C → D
C G → D
C E → A
D → E
D → G }

注意:我不确定是否还有其他规范覆盖。

英文:

A common algorithm to produce a minimal cover consists of three steps:

  1. Split the right part, producing FDs with only one attribute on the right part.

  2. For each left part with more than one attribute, try to remove each attribute in turn and see if the remaining can still determine the right part. In this case, eliminate the attribute from the left part.

  3. For each remaining dependency, try to see if it can be eliminated.

In your case the first step produces:

F = { A C → G
      A C D → B
      B C → D
      C G → B
      C G → D
      C E → A
      C E → G
      D → E
      D → G }

In the second step, we must check the first seven dependencies. For each dependency A1A2...An -> B we try to eliminate in turn each Ai and see
if B is included in the closure of the remaining attributes (the closure taken with respect to F). In this case we have two possibilities: from ACD -> B we can eliminate either A or D. So we have now two different set of dependencies:

F1 = { A C → G
       C D → B
       B C → D
       C G → B
       C G → D
       C E → A
       C E → G
       D → E
       D → G }

and

F2 = { A C → G
       A C → B
       B C → D
       C G → B
       C G → D
       C E → A
       C E → G
       D → E
       D → G }

Now we can apply the last step: for each dependency X -> A we can see if A is included in the closure of X, X+ with respect to all the other dependencies. In this case, we can eliminate that dependency.

The result will depend, in general, from the order in which we apply those checks.

Here there are four different canonical covers:

G1 = { A C → G
       B C → D
       C G → B
       C E → A
       D → E
       D → G }

G2 = { A C → G
       B C → D
       C G → D
       C E → A
       C D → B
       D → E
       D → G }

G3 = { A C → B
       B C → D
       C G → B
       C E → A
       D → E
       D → G }

G4 = { A C → B
       B C → D
       C G → D
       C E → A
       D → E
       D → G }

Note: it is not clear to me if there are other canonical covers.

huangapple
  • 本文由 发表于 2020年1月6日 23:28:16
  • 转载请务必保留本文链接:https://go.coder-hub.com/59614734.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定