You will write a program that computes the BCNF decomposition of a pair (relatio

Question

You will write a program that computes the BCNF decomposition of a pair (relation, functional dependencies. You might find it useful to implement the classes described below 1. S A stack of relations. Methods include: (a) S.push (R) push a relation into the stack. (b) S. pop pop a relation from the stack. (c) S.isempty() returns true if the stack is empty. 2. R A relation is a set of attributes and can be implemented easily using an array A of integers with values of 0 or 1. If A Lil 1 means that the attribute with ASCII i is in the relation 3. F- A functional dependency is an object containing two relations (sets. One on the left hand side and one on the right hand side. Methods include: F.1hs(); and F.rhs 4. L A ist of functional dependencies. Methods include (a) L. insert F) inserts a new functional dependency into the list (b) L.get Next C); returns the next functional dependency in the list (c) L. reset resets the list so that the next call to getNext C) returns the first functional dependency 5. DB a list of relations. Methods include the same as a list of functional dependencies.

Explanation / Answer

Although the question is old, the other questions/answers don't seem to provide a very clear step-by-step general answer on determining and decomposing relations to BCNF.

1. Determine BCNF:
For relation R to be in BCNF, all the functional dependencies (FDs) that hold in R need to satisfy property that the determinants X are all superkeys of R. i.e. if X->Y holds in R, then X must be a superkey of R to be in BCNF.

In your case, it can be shown that the only candidate key (minimal superkey) is ACE. Thus both FDs: A->B and C->D are violating BCNF as both A and C are not superkeys or R.

2. Decompose R into BCNF form:
If R is not in BCNF, we decompose R into a set of relations S that are in BCNF.
This can be accomplished with a very simple algorithm:

In your case the iterative steps are as follows:

Thus R(A,B,C,D,E) is decomposed into a set of relations: R1(A,C,E), R2(A,B) and R3(C,D) that satisfies BCNF.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.