Database Systems 6th Edition by Ramez Elmasri, Shamkant B. Navathe

Exercise 2

Algorithm 15.3. Testing for Nonadditive Join Property
Input: A universal relation R, a decomposition D = {R₁, R₂, ..., R_m} of R, and a set F of functional dependencies.
Note: Explanatory comments are given at the end of some of the steps. They follow the format: (* comment *).
1. Create an initial matrix S with one row i for each relation R_i in D, and one column j for each attribute A_j in R.
2. Set S(i, j):= b_ijfor all matrix entries. (* each b_ij is a distinct symbol associated with indices (i, j) *).
3. For each row i representing relation schema R_i {for each column j representing attribute A_j {if (relation R_i includes attribute A_j ) then set S(i, j):= aj;};}; (* each a_j is a distinct symbol associated with index (j) *).
4. Repeat the following loop until a complete loop execution results in no changes to S
{for each functional dependency X → Y in F
{for all rows in S that have the same symbols in the columns corresponding to attributes in X
{make the symbols in each column that correspond to an attribute in Y be the same in all these rows as follows: If any of the rows has an a symbol for the column, set the other rows to that same a symbol in the column. If no a symbol exists for the attribute in any of the rows, choose one of the b symbols that appears in one of the rows for the attribute and set the other rows to that same b symbol in the column ;} ; } ;};
5. If a row is made up entirely of a symbols, then the decomposition has the nonadditive join property; otherwise, it does not.
-Show that, if the matrix S resulting from Algorithm 15.3 does not have a row that is all "a" symbols, then projecting S on the decomposition and joining it back will always produce at least one spurious tuple.