LOSSLESS DECOMPOSITIONPowerPoint PresentationSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Definition of DecompositionExample of DecompositionSlide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Definition of Lossless DecompotionExampleSlide 51Slide 52Slide 53Slide 54Slide 55Slide 56LOSSLESS DECOMPOSITIONProf. Sin-Min LeeDepartment of Computer ScienceSan Jose State UniversityDefinition of DecompositionA decomposition of a relation R is a set of relations { R1, R2,…, Rn } such that each Ri is a subset of R and the union of all of the Ri is RExample of DecompositionFrom R( A B C ) we can have two subsets as:R1( A C ) and R2( B C )if we union R1 and R2 we will get RR = R1 U R2Definition of Lossless DecompotionA 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.ExampleR( A1, A2, A3, A4, A5 )R1( A1, A2, A3, A5 ); R2( A1, A3, A4 ); R3( A4, A5 ) are subsets of R.We have FD1: A1 --> A3 A5 FD2: A2 A3 --> A2 FD3: A5 --> A1 A4 FD4: A3 A4 --> A2A1 A2 A3 A4 A5a(1) a(2) a(3) b(1,4) a(5)a(1) b(2,2) a(3) a(4) b(2,5)b(3,1) b(3,2) b(3,3) a(4) a(5)By FD1: A1 --> A3 A5we have a new result tableA1 A2 A3 A4 A5a(1) a(2) a(3) b(1,4) a(5)a(1) b(2,2) a(3) a(4) a(5)b(3,1) b(3,2) b(3,3) a(4) a(5)By FD2: A2 A3 --> A4we don’t have a new result table because we don’t have any equally elements. Therefore, the result doesn’t change.By FD3: A5 --> A1 A4we have a new result tableA1 A2 A3 A4 A5a(1) a(2) a(3) a(4) a(5)a(1) b(2,2) a(3) a(4) a(5)b(3,1) b(3,2) b(3,3) a(4) a(5)By FD4: A3 A4 --> A2we get a new result tableA1 A2 A3 A4 A5a(1) a(2) a(3) a(4) a(5)a(1) a(2) a(3) a(4) a(5)b(3,1) b(3,2) b(3,3) a(4) a(5) tuple1 and tuple2 are lossless because they have all
View Full Document
Unlocking...