What is the correct approach when decomposing dependencies

Question

Hello I am currently studying for an exam that will take place in 11 days time from now. I am struggling with Carnonical Cover, Dependency Preservation and Lossless Decomposition. I am also a bit foggy on normal forms and the above mentioned subjects in the sense, that whenever I do exercises I seem to mess up. My question is whether the approach and thoughts here are correct:

R(ABCDEFG) Provided is the following set of dependencies after a canonical cover has been made. I did not do the canonical cover myself but the assignment said I had to assume it had been done.

Fc:
  A -> C
  E -> A
  C -> ABF
  F -> CDG

A+ = ABCDFG
E+ = ABCDEFG
C+ = ABCDFG
F+ = ABCDFG

E = Candidate Key.

This list of functional dependencies are in 2NF since there are no partial dependencies. It is however not in 3NF since there are transistive dependencies.

However decomposing into the following 4 relations will result in it being not only in 3NF but also BCNF

R1 = {E,A}
  E -> A

R2 = {A, C}
  A -> C

R3 = {CABF} 
  C -> ABF

R4 = {FCDG}
  F -> CDG

I use A in R1 as a foreign key to R2 and C in R2 as a foreign key to R3 etc.

Now there are no transistive dependencies and since all left hand sides in their respective relation are candidate keys it is in BCNF.

Is it not also lossless and dependency preserving?

1st, schemas are in NFs. Not sets of FDs. You need to know all the attributes. 2nd, when the FDs in a set hold, other ones do. The set of all FDs that hold when those do is its closure. So is this set a cover (ie the only FDs in this one's closure hold) or just some FDs that hold (so others in addition to the closure's could)? 2nd, are you saying that you are given that E is a CK, or are you saying you figured that out? Are you saying it's the only CK? (There can be more than one.) 3rd, your justifications for 2NF & 3NF are unsound. I'm going to stop there. Ask one question at a time. — philipxy, Aug 06 '17 at 18:50
@philipxy There has been made a carnonical cover over the FDs (Hence Fc if that was your question) and I figured out myself that E is the CK. — Paludan, Aug 07 '17 at 09:15
@philipxy Also thanks for the link. So just to try: The original schemas before decomposing it. was in 2NF because all attributes are fully functionally dependent on the CK and there are no cases of partial dependencies (For example AB -> C , A -> C here C is partially dependent on AB). It is not in 3NF because we have transistive dependencies (such as A->C C->B right?). — Paludan, Aug 07 '17 at 09:39
Armstrong's axioms give a closure. There are partial FDs, eg EA -> A. Just not partial FDs of non-primes on CKs. A->C is not a transitive dependency; there's no X such that A->X->C where NOT X->A. A->B is transitive, but not through C. You are not getting definitions & justifications correct. Also if you are going to justify things, give the definition & show all the parts are satisfied. Eg your 3NF reasoning lacks that the relation is in 2NF. If you leave out reasoning, how do we know you got to a right answer correctly? Do you see why I say one question please, with a reference? — philipxy, Aug 07 '17 at 10:26
@philipxy Yes I'm sorry there has been made a canonical cover and Fc is the result of that. This was taken directly from an assignment where it said that we should assume a canonical cover had been made. The whole A->C transistive dependency was just an out of context example and has no relation to the assignment, I only stated it to show what I meant a transistive dependency was. Sorry for being unclear I'm kind of new to the whole subject. Also by confirming attributes do you mean using Armstrongs axioms? Also I think I'm gonna read again because I can't follow much of what you're saying. — Paludan, Aug 07 '17 at 11:03
"Confirm attributes" reiterated "You need to know all the attributes." We need *all FDs that hold* to determine CKs etc *for a given schema/relation*. But a cover might not mention the trivial FDs & a canonical cover *won't*. Eg for schema/relation R(A,B,C,D,E,F,G,H) the set of CKs is {{E,H}}. (I wondered whether your example ABCs should have been XYZs, ie not from your question. *Mine were.*) PS Re future clarifications, please don't edit a question to invalidate any (good) answers. — philipxy, Aug 07 '17 at 16:47

score 2 · Answer 1 · answered Aug 06 '17 at 20:22

What is decomposed

In the title you say:

What is the correct approach when decomposing dependencies

but one does not decompose dependencies, but relation schemas. So, in this case, here there is a relation schema R(ABCDEFG) with a set of functional dependencies and one must decompose that schema.

What is a decomposition

A decomposition produces a set of relation schemas with the following properties: a) every attribute of the original schema is present in some (possibly more than one) subschema; b) no other attributes are present. Moreover, a decomposition is redundant when a relation subschema is contained in another. In your case, this is true for R2, which is contained in R3: there is no need to have both relations, since it would imply unuseful data redundancy.

What is a good decomposition

To be really useful, a decomposition should satisfy two important properties: preserve functional dependencies and preserve data (lossless decomposition). But another property characterizes a good decomposition: it should be as small as possible: there is no point in decomposing a schema in too many subschemas, since this would produce a non natural and complex database.

Actually your decomposition is lossless and preserves the dependencies.

How to decompose

The final objective of all this stuff is to produce a decomposisition (lossless and dependency preserving) in which the subschemas are in BCNF or 3NF. The simple solution of decomposing by using the attributes of the functional dependencies is not, however, a good solution. For this, there are algorithms, described in textbooks, that produces decompositions either for BCNF or for 3NF (the so-called “analysis” algorithm for BCNF, and “synthesis” algorithm for 3NF), trying to produce not too many subschemas. For instance, the “analysis” algorithm in this case produce the following decomposition in BCNF, with only two subschemas:

R1 < (A B C D F G) ,
    { F → C
      F → D
      F → G
      C → A
      C → B
      C → F
      A → C } >

R2 < (A E) ,
    { E → A } >

This decomposition is lossless and preserves the dependencies (which is not always true for the analysis algorithm).

thanks for the reply and thanks for the comments on what you decompose. I have a question regarding sub schema R1: Is the reason E is not mentioned in R1 because there are no uses of E there (right hand side)? — Paludan, Aug 07 '17 at 09:21
@Paludan, this is a particular example: if you remove E (which is the only candidate key in the original relation), then the resulting relation has three candidate keys, A, C and F, and it is already in BCNF. The analysis algorithm for decomposing in BCNF requires to find a dependency that violates this form, then manipulate it according to certain rules. In this case, the algorithm will always extract E from the original relation, and will produce three different possibile alternative correct results, with tables EA, EC, or EF (that is, E together with one candidate key of R1). — Renzo, Aug 08 '17 at 06:42

What is the correct approach when decomposing dependencies

1 Answers1