Testing Losless Join Algorithm

Testing algorithm
input: A relation R, a decomposition D = {R1, R2,..., Rm} of R, and
a set F of function dependencies.

1. Create an initial matrix S with one row i for each relation Ri in
D, and one column j for each attribute Aj in R.
2. Set S(i, j) := bij for all matrix entries.
3. For each row i representing relation schema Ri Do
{for each column j representing Aj do
{if relation Ri includes attribute Aj then
set S(i, j) := aj;}
4. Repeat the following loop until a complete loop execution results
in no changes to S.

{for each function dependency X  Y in F do
for all rows in S which have the same symbols in the
columns corresponding to attributes in X do
{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 the 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 appear 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 decompo-
sition has the lossless join property; otherwise it does not.