Question 7 of 8

Question 7 (6+7+7=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.

Given. CarSale(CarID, OptionType, OptionListPrice, SaleDate, OptionDiscountedPrice) with F = { CarID→SaleDate, OptionType→OptionListPrice, CarID,OptionType→OptionDiscountedPrice }, decomposed into R1=CarSale(CarID,SaleDate), R2=Options(OptionType,OptionListPrice), R3=CarOptions(CarID,OptionType,OptionDiscountedPrice).

Find. (a) the definition of a functional dependency; (b) whether {R1,R2,R3} is a lossless-join decomposition; (c) whether it is dependency-preserving.

Approach. (b) uses the general CHASE (tableau) test, which handles a decomposition into any number of pieces (the textbook's common-attribute shortcut only covers exactly two pieces): build one tableau row per relation with distinguished symbols for its own attributes and unique symbols elsewhere, then repeatedly equate cells forced equal by each FD until nothing changes — the decomposition is lossless exactly when some row ends up entirely distinguished. (c) checks each ORIGINAL FD's full attribute set against the three pieces directly.

1. 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 agreeing on all of X's attributes are guaranteed to also agree on all of Y's attributes. Equivalently: knowing the X-value of a tuple is enough to know its Y-value uniquely — two tuples can never share an X-value while differing on Y.
2. Part (b) — lossless-join via chase. Tableau, using CarID, OptionType, OptionListPrice, SaleDate, OptionDiscountedPrice as the attribute order (a_i = distinguished, b_i,j = unique to row i):

   Row	CarID	OptionType	OptionListPrice	SaleDate	OptionDiscountedPrice
   R1 (CarID,SaleDate)	a1	b1,2	b1,3	a4	b1,5
   R2 (OptionType,OptionListPrice)	b2,1	a2	a3	b2,4	b2,5
   R3 (CarID,OptionType,OptionDiscountedPrice)	a1	a2	b3,3	b3,4	a5

   Apply CarID→SaleDate: rows R1 and R3 agree on CarID (both a₁), so their SaleDate cells must be equated — R1 already carries the distinguished a₄, so R3's b_3,4 is overwritten to a₄. Apply OptionType→OptionListPrice: rows R2 and R3 agree on OptionType (both a₂), so their OptionListPrice cells equate — R2 carries the distinguished a₃, so R3's b_3,3 is overwritten to a₃. After these two substitutions, row R3 reads (a₁, a₂, a₃, a₄, a₅) — entirely distinguished symbols. (The third FD, CarID,OptionType→OptionDiscountedPrice, needs no further action: no OTHER row shares both a₁ AND a₂ simultaneously with R3, so it never triggers, but it is not needed once R3 is already fully distinguished.)

A row of all-distinguished symbols is exactly the chase's termination condition for a LOSSLESS-JOIN decomposition (that row certifies the original relation is always recoverable by natural-joining R1, R2, R3 back together): the decomposition IS lossless. This matches the intuitive reason too — R3 already contains BOTH halves of the whole relation's only candidate key {CarID, OptionType} (since {CarID,OptionType}⁺ = all 5 attributes, using all three given FDs, and no proper subset of it determines everything), so joining R1 and R2 back onto R3 can only ever re-attach exactly the SaleDate and OptionListPrice values that belong to each row, never spurious combinations.

Part (c) — dependency preservation. A decomposition preserves F if the UNION of each Fi (F projected onto relation Ri) still implies every original dependency, i.e. F ⊆ (F1∪F2∪F3)⁺. Here the check is immediate without computing any closure at all: each of the three given FDs has BOTH its left- and right-hand attributes wholly contained within a SINGLE decomposed relation — CarID→SaleDate sits entirely inside R1={CarID,SaleDate}; OptionType→OptionListPrice sits entirely inside R2={OptionType,OptionListPrice}; CarID,OptionType→OptionDiscountedPrice sits entirely inside R3={CarID,OptionType,OptionDiscountedPrice}. Since every original FD already appears, verbatim, as a dependency projected onto one of the three pieces, F1∪F2∪F3 literally CONTAINS F (not merely implies it). Yes, the decomposition is dependency-preserving — and it is the strongest possible case, since no cross-relation reasoning (join, then re-derive) is ever needed to recover any of the three original rules.