0

Here's the decomposing algorithm I have:

R is a relation. F is the set of FD's

1.If an FD X ->Y in F violates BCNF
2. Compute X +.
3. Replace R by two relations with schemas:
4. R1 = X +
5. R2 = R – (X + – X )
6. Project the FD’s F onto R1 and R2
7. Recursively decompose R1 and R2 into BCNF

I'm having trouble performing the algorithm, so I'm asking for help. I searched through SO, but the algorithm that I found did not contain the projection part. I think there's some misunderstanding about the algorithm.

Suppose I Have A Relation R(LMNOPQRS), and my functional dependencies are D = {L->NQ, MNR->O, O->M, NQ->LS, S->OPR} and I'm trying to perform the algorithm to get this relation into BCNF.

Here is what I tried:

I found that MNR->O is one of the FD's that violates BCNF since it's not a superkey to the relation. So I decomposed them into two relations:

R1 = MNRO R2 = NQLSPRM

now the projection is my hardest part: I tried to find the closure set of MNRO to project the FD's, and the FDs that satisfies the relation R1 is O->M and MNR->O. MNR is the key to the relation R1, but O is not. So do I just omit the O-M relation? or should I decompose further? Did I do my projection right?

Thank you in advance for the help.

Ioce
  • 19
  • 4
  • Please tell us where you this algorithm--textbook name & edition. The reference will explain what the projection of FD closure F on a component is: the FDs from F+ whose attributes are in that component. The algorithm is applied recursively to each component. – philipxy Dec 04 '19 at 07:47
  • The Algorithm came from my professor, but it is based on the book "A First Course in Database Systems 3ed". – Ioce Dec 04 '19 at 07:53
  • What research have you done to find out what projecting a set of FDs on a component or attribute set is? Have you googled the book & seen slides at http://infolab.stanford.edu/~ullman/fcdb.html? – philipxy Dec 04 '19 at 07:55
  • yes, about projection, it is at section 3.2.8, where projecting the set of FD's from R on R1 will output the set of FD's that hold in R1. – Ioce Dec 04 '19 at 07:59
  • And that doesn't say what I said in my first comment about which FDs those are? How are you stuck calculating those projected FDs? (There is a theorem you have been given relating FDs in a projection/component & those in a original/join.) – philipxy Dec 04 '19 at 08:04
  • I'm very sorry but I still do not quite understand how that helps on my question. Can you elaborate a little bit more? – Ioce Dec 04 '19 at 08:07
  • I told you in my first comment what the FDs that hold in a projection/component are in terms of those that hold in an original. – philipxy Dec 04 '19 at 08:08
  • So does that mean I should not have ```O->M``` in my projected sets of FD's? – Ioce Dec 04 '19 at 08:13
  • Is it or is it not in the set I & your textbook (differently) defined? What exacty part of what exact step are you stuck on? PS I just googled 'projecting a set of FDs on a component' & got a bunch of hits including many at SO. That's the question you are asking in your post. Why didn't you? – philipxy Dec 04 '19 at 08:13
  • I think it's the part on finding new FDs from projection. Follow from the definition then the two FDs I found were correct since all their components are in the new relation. Then R1 is still not BCNF since O is not a superkey on the relation. Further decomposing the relation will give me ```R1 = OM R2 = MNR```. But no FD from the two would satisfy the relation? – Ioce Dec 04 '19 at 08:27
  • What does "I have these FDs" mean? "These are all the FDs that hold"?--Not possible. "These are all the non-trivial FDs that hold"?--Not possible. "These are some FDs that hold"?--Question can't be answered. Find out what a *cover* is & what the exact conditions are to apply a particular definition/rule/algorithm. To determine CKs & NFs we must be given FDs that form a cover. Sometimes a minimal/irreducible cover. And the set of all attributes must given. [See this answer.](https://stackoverflow.com/a/53386492/3404097) 2. What *exactly* does F need to be? Then F is what in terms of D? – philipxy Dec 05 '19 at 10:23

0 Answers0