Understanding Lossless Decomposition in Database Systems

Understanding Lossless Decomposition in Database Systems
paly

This article explains the concept of lossless decomposition in database systems using an example and definitions from the field of computer science.

  • Uploaded on | 0 Views
  • yankoepp yankoepp

About Understanding Lossless Decomposition in Database Systems

PowerPoint presentation about 'Understanding Lossless Decomposition in Database Systems'. This presentation describes the topic on This article explains the concept of lossless decomposition in database systems using an example and definitions from the field of computer science.. The key topics included in this slideshow are lossless decomposition, relation schema, subset, database systems, computer science,. Download this presentation absolutely free.

Presentation Transcript


1. Lossless Decomposition Anannya Sengupta CS 157A Prof. Sin-Min Lee

2. Definition of Decomposition Let R be a relation schema A set of relation schemas { R1, R2, , Rn } is a decomposition of R if R = R1 U R2 U ..U Rn each Ri is a subset of R ( for i = 1,2 ,n)

3. Example of Decomposition For relation R(x,y,z) there can be 2 subsets: R1(x,z) and R2(y,z) If we union R1 and R2, we get R R = R1 U R2

4. Goal of Decomposition Eliminate redundancy by decomposing a relation into several relations in a higher normal form. It is important to check that a decomposition does not lead to bad design

5. Problem with Decomposition Given instances of the decomposed relations, we may not be able to reconstruct the corresponding instance of the original relation information loss

6. Example : Problem with Decomposition Model Name Price Category a11 100 Canon s20 200 Nikon a70 150 Canon R Model Name Category a11 Canon s20 Nikon a70 Canon Price Category 100 Canon 200 Nikon 150 Canon R1 R2

7. Example : Problem with Decomposition R1 U R2 Model Name Price Category a11 100 Canon a11 150 Canon s20 200 Nikon a70 100 Canon a70 150 Canon Model Name Price Category a11 100 Canon s20 200 Nikon a70 150 Canon R

8. Lossy decomposition In previous example, additional tuples are obtained along with original tuples Although there are more tuples, this leads to less information Due to the loss of information, decomposition for previous example is called lossy decomposition or lossy-join decomposition

9. Lossy decomposition (more example) Employee Project Branch Brown Mars L.A. Green Jupiter San Jose Green Venus San Jose Hoskins Saturn San Jose Hoskins Venus San Jose T Functional dependencies: Employee Branch, Project Branch

10. Lossy decomposition Decomposition of the previous relation Employee Branch Brown L.A Green San Jose Hoskins San Jose Project Branch Mars L.A. Jupiter San Jose Saturn San Jose Venus San Jose T1 T2

11. Lossy decomposition Employee Project Branch Brown Mars L.A. Green Jupiter San Jose Green Venus San Jose Hoskins Saturn San Jose Hoskins Venus San Jose Green Saturn San Jose Hoskins Jupiter San Jose Employee Project Branch Brown Mars L.A. Green Jupiter San Jose Green Venus San Jose Hoskins Saturn San Jose Hoskins Venus San Jose After Natural Join Original Relation After Natural Join, we get two extra tuples. Thus, there is loss of information.

12. Lossless Decomposition A decomposition {R1, R2, , Rn} of a relation R is called a lossless decomposition for R if the natural join of R1, R2, , Rn produces exactly the relation R.

13. Lossless Decomposition A decomposition is lossless if we can recover: R(A, B, C) Decompose R1(A, B) R2(A, C) Recover R(A, B, C) Thus, R = R

14. Lossless Decomposition Property R : relation F : set of functional dependencies on R X,Y : decomposition of R Decomposition is lossles if : X Y X, that is: all attributes common to both X and Y functionally determine ALL the attributes in X OR X Y Y, that is: all attributes common to both X and Y functionally determine ALL the attributes in Y

15. Lossless Decomposition Property In other words, if X Y forms a superkey of either X or Y, the decomposition of R is a lossless decomposition

16. Armstrong s Axioms X, Y, Z are sets of attributes 1. Reflexivity: If X Y, then X Y 2. Augmentation: If X Y, then XZ YZ for any Z 3. Transitivity: If X Y and Y Z, then X Z 4. Union: If X Y and X Z, then X YZ 5. Decomposition: If X YZ, then X Y and X Z

17. Example : Lossless Decomposition Given: Lending-schema = ( branch-name, branch-city, assets, customer-name, loan-number, amount ) Required FDs: branch-name branch-city assets loan-number amount branch-name Decompose Lending-schema into two schemas: Branch-schema = ( branch-name, branch-city, assets ) Loan-info-schema = ( branch-name, customer-name, loan-number, amount )

18. Example : Lossless Decomposition Show that decomposition is Lossless Decomposition Since branch-name branch-city assets, the augmentation rule for FD implies that: branch-name branch-name branch-city assets Since Branch-schema Loan-info-schema = { branch- name } Thus, this decomposition is Lossless decomposition

20. Example R1 (A1, A2, A3, A5) R2 (A1, A3, A4) R3 (A4, A5) FD1: A1 A3 A5 FD2: A5 A1 A4 FD3: A3 A4 A2

21. Example (cont) A1 A2 A3 A4 A5 R1 a(1) a(2) a(3) b(1,4) a(5) R2 a(1) b(2,2) a(3) a(4) b(2,5) R3 b(3,1) b(3,2) b(3,3) a(4) a(5)

22. Example (cont) By FD1: A1 A3 A5 A1 A2 A3 A4 A5 R1 a(1) a(2) a(3) b(1,4) a(5) R2 a(1) b(2,2) a(3) a(4) b(2,5) R3 b(3,1) b(3,2) b(3,3) a(4) a(5)

23. Example (cont) By FD1: A1 A3 A5 we have a new result table A1 A2 A3 A4 A5 R1 a(1) a(2) a(3) b(1,4) a(5) R2 a(1) b(2,2) a(3) a(4) a(5) R3 b(3,1) b(3,2) b(3,3) a(4) a(5)

24. Example (cont) By FD2: A5 A1 A4 A1 A2 A3 A4 A5 R1 a(1) a(2) a(3) b(1,4) a(5) R2 a(1) b(2,2) a(3) a(4) a(5) R3 b(3,1) b(3,2) b(3,3) a(4) a(5)

25. Example (cont) FD2: A5 A1 A4 we have a new result table A1 A2 A3 A4 A5 R1 a(1) a(2) a(3) a(4) a(5) R2 a(1) b(2,2) a(3) a(4) a(5) R3 a(1) b(3,2) b(3,3) a(4) a(5)

26. Conclusions Decompositions should always be lossless Lossless decomposition ensure that the information in the original relation can be accurately reconstructed based on the information represented in the decomposed relations.

27. References Fundamentals of Database Systems Fourth Edition Elmasri, Navathe Database System Concepts Fourth Edition Silberschatz, Korth, Sudarshan