LOSSY OR LOSSLESS DECOMPOSITION (second method)

Algorithm: Testing for lossless (nonadditive) join property.

Input: A universal relation R, a decomposition D = { R1, R2, R3, ….. Rm } of R, and a set F of functional dependencies.

1. Create an initial matrix S with one row i for each relation in Ri in D, and one column j for each attribute Aj in R.

2. Set S(i, j) := bij for all matrix entries. (* each bij is a distinct symbol associated with indices (i, j) * )

  {for each column j representing attribute Aj                                 {if (relation Ri includes attribute Aj ) then set S(I, j):=aj;};};            (* each aj is a distinct symbol associated with index (j) *)  

3. For each row i representing relation schema Ri

  {for each functional dependency X  → Y in F           {for all rows in S which 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 have an “a” symbol for the                                   the column set the other rows to that same “a” symbol                                         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 ;};};};  

4. Repeat the following loop until a complete loop execution results in no changes to S

5. If a row is made up entirely of “a” symbols, then the decomposition has the lossless join property; otherwise, it does

Question 1. Given a relational schema R = { SSN, ENAME, PNUMBER, PNAME, PLOCATION, HOURS } and the decomposed table R1 = { ENAME, PLOCATION } and R2 = { SSN, PNUMBER, HOURS, PNAME, PLOCATION } and FD = { SSN → ENAME, PNUMBER → { PNAME, PLOCATION}, { SSN, PNUMBER } → HOURS }. Identify whether the given decomposition of R, R1 and R2 is lossless or lossy decomposition ?

Solution: Using the above algorithm let’s solve the above question.

1. Let’s construct a table of the above relation R, R1, and R2 and insert value in form of bij or aj using ALGO STEP1 (Create an initial matrix S with one row i for each relation in Ri in D, and one column j for each attribute aj in R).

	SSNENAME	PNUMBERPNAME	PLOCATION	HOURS
R1	b11	b12	b13	b14	b15	b16
R2	b21	b22	b23	b24	b25	b26

Created a table using R = { SSN, ENAME, PNUMBER, PNAME, PLOCATION, HOURS } where every attribute of R is represented in each column. And the initial value of each decomposed table R1 R2 and R3 in the format of bij, where i is the row and j is the column using ALGO STEP2 ( Set S(i, j) := bij for all matrix entries. (* each bij is a distinct symbol associated with indices (i, j) * ) )

	SSNENAME	PNUMBERPNAME	PLOCATION	HOURS
R1	b11	b12	b13	b14	b15	b16
R2	b21	b22	b23	b24	b25	b26

Now insert value in row R1 and R2 as “aj” using R1 = { ENAME, PLOCATION } and R2 = { SSN, PNUMBER, HOURS, PNAME, PLOCATION }

	SSNENAME	PNUMBERPNAME	PLOCATION	HOURS
R1	a1	b12	b13	b14	a5	b16
R2	a1	b22	a3	a4	a5	a6

Given Functional Dependencies are FD = {SSN → ENAME, PNUMBER → {PNAME, PLOCATION}, {SSN, PNUMBER } → HOURS }

Using step 4 of the above algorithm, if there exist a functional dependency X → Y, and for two tuples t1, and t2 if

t1 [ X ] = t2 [ X ] then we must have

t1 [ Y ] = t2 [ Y ]

	SSNENAME	PNUMBERPNAME	PLOCATION	HOURS
R1	a1	b12	b13	b14	a5	b16
R2	a1	b22	a3	a4	a5	a6

Find in the above table that is there any X → Y whose X are equal then make Y also equal.Since by using the above FD we did not found any row either of R1 or R2 having all a, hence we can say that above R which is decomposed in R1 and R2 are lossy decomposition, i.e. information is not preserved during decomposition.

Question 2 . Given a relational schema R = { SSN, ENAME, PNUMBER, PNAME, PLOCATION, HOURS } and the decomposed table

R1 = { SSN, ENAME }

R2 = { PNUMBER, PNAME, PLOCATION }

R3 = { SSN, PNUMBER, HOURS }

FD = { SSN → ENAME, PNUMBER → { PNAME, PLOCATION}, { SSN, PNUMBER } → HOURS }.

Identify whether the given decomposition of R, R1 [email protected], and R3 is lossless or lossy decomposition?

Solution: Using above algorithm let’s solve the above question.

Let’s construct a table of the above relation R, R1 R2 and R3 and insert value in form of bij or aj using ALGO STEP1 (Create an initial matrix S with one row i for each relation in Ri in D, and one column j for each attribute aj in R).

	SSN	ENAME	PNUMBER	PNAME	PLOCATION	HOURS
R1
R2
R3

Created a table using R = { SSN, ENAME, PNUMBER, PNAME, PLOCATION, HOURS } where every attribute of R is represented in each column. And initial value of each decomposed table R1 R2 and R3 in the format of bij, where i is the row and j is the column using ALGO STEP2 ( Set S(i, j) := bij for all matrix entries. (* each bij is a distinct symbol associated with indices (i, j) * ) )

	SSN	ENAME	PNUMBER	PNAME	PLOCATION	HOURS
R1	b11	b12	b13	b14	b15	b16
R2	b21	b22	b23	b24	b25	b26
R3	b31	b32	b33	b34	b35	b36

Now insert value in row R1 R2 and R3 as “aj” using R1 = { SSN, ENAME } R2 = { PNUMBER, PNAME, PLOCATION } and R3 = { SSN, PNUMBER, HOURS } using ALGO STEP3 For each row i representing relation schema Ri{for each column j representing attribute Aj {if (relation Ri includes attribute Aj ) then set S(i, j):=aj;};}; (* each aj is a distinct symbol associated with index (j) *)

	SSN	ENAME	PNUMBER	PNAME	PLOCATION	HOURS
R1	a1	a2	b13	b14	b15	b16
R2	b11	b22	a3	a4	a5	b26
R3	a1	b32	a3	b34	b35	a6

Given Functional Dependencies are FD = { SSN → ENAME, PNUMBER → { PNAME, PLOCATION}, { SSN, PNUMBER } → HOURS }

Using step 4 of above algorithm, if there exist a functional dependency X → Y, and for two tuples t1, and t2 if

t1 [ X ] = t2 [ X ] then we must have

t1 [ Y ] = t2 [ Y ]

	SSN	ENAME	PNUMBER	PNAME	PLOCATION	HOURS
R1	a1	a2	b13	b14	b15	b16
R2	b11	b22	a3	a4	a5	b26
R3	a1	b32	a3	b34	b35	a6

Find in the above table that is there any FD X → Y whose X are equal then make Y also equal.

Step A: By using the above FD SSN → ENAME, we found that SSN of R1 and R3 are equal, hence ENAME of R1 and R3 will also be equal. The Table will look like:

	SSN	ENAME	PNUMBER	PNAME	PLOCATION	HOURS
R1	a1	a2	b13	b14	b15	b16
R2	b11	b22	a3	a4	a5	b26
R3	a1	a2	a3	b34	b35	a6

Step B: By using FD PNUMBER → {PNAME, PLOCATION} on the above table we found that PNUMBER of R2 and R3 are equal, hence PNAME, PLOCATION of R2 and R3 will also be equal. The Table will look like:

	SSN	ENAME	PNUMBER	PNAME	PLOCATION	HOURS
R1	a1	a2	b13	b14	b15	b16
R2	b11	b22	a3	a4	a5	b26
R3	a1	a2	a3	a4	a5	a6

Step C: Since by using above FD: {SSN, PNUMBER} → HOURS we did not find any row either of R1 R2 or R3 whose SSN, PNUMBER are equal hence there will be no change in above table. Finally, our table looks like:

	SSN	ENAME	PNUMBER	PNAME	PLOCATION	HOURS
R1	a1	a2	b13	b14	b15	b16
R2	b11	b22	a3	a4	a5	b26
R3	a1	a2	a3	a4	a5	a6

If we see the row R3, we found that all the values in that row has value aj, from above algo we can say that our decomposition of R in R1, R2, and R3 are lossless.

Next TopicQUESTIONS TO IDENTIFY NORMAL FORM

LOSSY OR LOSSLESS DECOMPOSITION (second method)

LOSSY OR LOSSLESS DECOMPOSITION (second method)

Alternate Key in DBMS

AWS DevOps

You may also like