Home » LOSSY OR LOSSLESS DECOMPOSITION (second method)

LOSSY OR LOSSLESS DECOMPOSITION (second method)

by Online Tutorials Library

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) * )

3. For each row i representing relation schema Ri

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.


You may also like