Question 7 of 8

Question 7 (3+3+(10+4)=20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Part (a) — functional dependency. For a relation schema R and attribute sets X, Y ⊆ R, X functionally determines Y (written X → Y) if, in every legal instance of R, any two tuples that agree on all of X's attributes are guaranteed to also agree on all of Y's attributes. Equivalently, the value of X uniquely determines the value of Y — there cannot be two tuples with the same X-value but different Y-values.

Part (b) — trivial functional dependencies. X → Y is called trivial when Y ⊆ X (e.g. AB → A, or AB → AB). Such a dependency holds automatically in EVERY possible instance, for every relation, purely from the definition of a tuple (two tuples that agree on all of X necessarily agree on the subset of X that is Y) — it carries no real integrity constraint and reflects nothing about the application's data, unlike a non-trivial FD (Y ⊄ X), which does restrict which instances are legal.

Given (c). Attribute set ABCDFG (6 attributes; note there is no E) with FDs: AB→CD, BC→FG, A→G, G→B, C→G.

Find. (i) A minimal cover; (ii) whether decomposing into R1=ABCD and R2=CFG is lossless.

Approach. Minimal-cover algorithm: (1) split every FD's right-hand side into single attributes; (2) remove any extraneous LEFT-hand attribute, i.e. one whose removal still lets the reduced LHS's closure (under the WHOLE current FD set) derive the RHS; (3) remove any FD that is itself entirely redundant, i.e. implied by the rest. The lossless-join test for a decomposition {R1,R2} checks whether the common attributes R1∩R2 functionally determine (the closure of) either R1 or R2 in full.

1. Step 1 — singleton right-hand sides. AB→CD splits into AB→C, AB→D; BC→FG splits into BC→F, BC→G. Working set: {AB→C, AB→D, BC→F, BC→G, A→G, G→B, C→G}.
2. Step 2 — drop extraneous LHS attributes. Testing AB→C: is B extraneous? Compute A⁺ using the whole set — A→G gives G, G→B gives B, and now that both A and B are in the closure, AB→C fires too, so A⁺ already contains C without needing B. B is extraneous → AB→C reduces to A→C. The identical argument (A⁺ already contains D once C is in it, via the still-present AB→D) reduces AB→D to A→D. Testing BC→F: is B extraneous? C⁺ alone (via C→G, then G→B) already reaches {B,C,G}, and now BC→F fires since B and C are both present — B is extraneous → BC→F reduces to C→F. Testing BC→G: C⁺ alone already contains G directly (C→G is already a separate FD) — B is extraneous, and the reduced form C→G is an exact duplicate of an FD already in the set, so BC→G is simply dropped.
3. Step 3 — drop entirely redundant FDs. Working set is now {A→C, A→D, C→F, C→G, A→G, G→B}. Testing A→G against the rest: A⁺ (via A→C, C→G) already reaches G without using A→G directly — A→G is redundant and is dropped. Testing each of the remaining five FDs the same way (compute the LHS's closure using only the OTHER four) shows none of A→C, A→D, C→F, C→G, G→B can be derived from the rest — all five are necessary.

Part (c)(ii) — lossless-join test. R1=ABCD, R2=CFG; the common attribute set is R1∩R2={C}. Computing C⁺ using the ORIGINAL FD set: C→G gives {C,G}; G→B gives {C,G,B}; now B and C are both present, so BC→FG fires, adding F (G is already present): C⁺ = {B,C,F,G}. Checking against the two pieces: is R2=CFG ⊆ C⁺? {C,F,G} ⊆ {B,C,F,G} — yes. Since the common attribute set C already functionally determines the entirety of R2, the lossless-join condition for a binary decomposition (R1∩R2 → R2, or alternatively R1∩R2 → R1, must hold in F⁺) is satisfied: the decomposition IS lossless. (R1=ABCD is NOT fully contained in C⁺, since A and D are missing — but only ONE side needs to hold, and R2 does.)