Decomposition.pdf
Document Details
Uploaded by Deleted User
Full Transcript
Decomposition in DBMS Decomposition of a Relation- Definition: The process of breaking up or dividing a single relation into two or more sub relations is called as decomposition of a relation. Properties of Decomposition- The following two properties must be followed when decomp...
Decomposition in DBMS Decomposition of a Relation- Definition: The process of breaking up or dividing a single relation into two or more sub relations is called as decomposition of a relation. Properties of Decomposition- The following two properties must be followed when decomposing a given relation- 1. Lossless decomposition- Lossless decomposition ensures- No information is lost from the original relation during decomposition. When the sub relations are joined back, the same relation is obtained that was decomposed. Every decomposition must always be lossless. Types of Decomposition- Decomposition of a relation can be completed in the following two ways- 1. Lossless Join Decomposition- Consider there is a relation R which is decomposed into sub relations R1 , R2 , …. , Rn. This decomposition is called lossless join decomposition when the join of the sub relations results in the same relation R that was decomposed. For lossless join decomposition, we always have- R1 ⋈ R2 ⋈ R3 ……. ⋈ Rn = R where ⋈ is a natural join operator Example- Consider the following relation R( A , B , C )- A B C 1 2 1 2 5 3 3 3 3 Consider this relation is decomposed into two sub relations R 1( A , B ) and R2( B , C )- The two sub relations are- A B B C 1 2 2 1 2 5 5 3 3 3 3 3 R1 ( A , B ) R 2( B , C ) Now, let us check whether this decomposition is lossless or not. For lossless decomposition, we must have- R1 ⋈ R2 = R Now, if we perform the natural join ( ⋈ ) of the sub relations R1 and R2 , we get- A B C 1 2 1 2 5 3 3 3 3 This relation is same as the original relation R. Thus, we conclude that the above decomposition is lossless join decomposition. NOTE- Lossless join decomposition is also known as non-additive join decomposition. This is because the resultant relation after joining the sub relations is same as the decomposed relation. No extraneous tuples appear after joining of the sub-relations. 2. Lossy Join Decomposition- Consider there is a relation R which is decomposed into sub relations R 1 , R2 , …. , Rn. This decomposition is called lossy join decomposition when the join of the sub relations does not result in the same relation R that was decomposed. The natural join of the sub relations is always found to have some extraneous tuples. For lossy join decomposition, we always have- R1 ⋈ R2 ⋈ R3 ……. ⋈ Rn ⊃ R where ⋈ is a natural join operator Example- Consider the above relation R( A , B , C )- Consider this relation is decomposed into two sub relations as R 1( A , C ) and R2( B , C )- The two sub relations are- B C A C 2 1 1 1 5 3 2 3 3 3 3 3 R1 ( A , B ) R 2( B , C ) Now, let us check whether this decomposition is lossy or not. For lossy decomposition, we must have- R1 ⋈ R2 ⊃ R Now, if we perform the natural join ( ⋈ ) of the sub relations R1 and R2 we get- A B C 1 2 1 2 5 3 2 3 3 3 5 3 3 3 3 This relation is not same as the original relation R and contains some extraneous tuples. Clearly, R1 ⋈ R2 ⊃ R. Thus, we conclude that the above decomposition is lossy join decomposition. NOTE- Lossy join decomposition is also known as careless decomposition. This is because extraneous tuples get introduced in the natural join of the sub-relations. Extraneous tuples make the identification of the original tuples difficult. Determining Whether Decomposition Is Lossless Or Lossy- Consider a relation R is decomposed into two sub relations R 1 and R2. Then, If all the following conditions satisfy, then the decomposition is lossless. If any of these conditions fail, then the decomposition is lossy. Condition-01: Union of both the sub relations must contain all the attributes that are present in the original relation R. Thus, R1 ∪ R2 = R Condition-02: Intersection of both the sub relations must not be null. In other words, there must be some common attribute which is present in both the sub relations. Thus, R1 ∩ R2 ≠ ∅ Condition-03: Intersection of both the sub relations must be a super key of either R 1 or R2 or both. Thus, R1 ∩ R2 = Super key of R1 or R2 Solved Examples to know whether a decomposition is lossy or losseless Problem-01: Consider a relation schema R ( A , B , C , D ) with the functional dependencies A → B and C → D. Determine whether the decomposition of R into R1 ( A , B ) and R2 ( C , D ) is lossless or lossy. Solution- Condition-01: According to condition-01, union of both the sub relations must contain all the attributes of relation R. So, we have- R1 ( A , B ) ∪ R 2 ( C , D ) =R(A,B,C,D) Clearly, union of the sub relations contain all the attributes of relation R. Thus, condition-01 satisfies. Condition-02: According to condition-02, intersection of both the sub relations must not be null. So, we have- R 1 ( A , B ) ∩ R2 ( C , D ) =Φ Clearly, intersection of the sub relations is null. So, condition-02 fails. Thus, we conclude that the decomposition is lossy. Problem-02: Consider a relation schema R ( A , B , C , D ) with the following functional dependencies- A→B B→C C→D D→B Determine whether the decomposition of R into R1 ( A , B ) , R2 ( B , C ) and R3 ( B , D ) is lossless or lossy. Solution- Strategy to Solve When a given relation is decomposed into more than two sub relations, then- Consider any one possible ways in which the relation might have been decomposed into those sub relations. First, divide the given relation into two sub relations. Then, divide the sub relations according to the sub relations given in the question. As a thumb rule, remember- Any relation can be decomposed only into two sub relations at a time. Consider the original relation R was decomposed into the given sub relations as shown- Decomposition of R(A, B, C, D) into R'(A, B, C) and R3(B, D)- Condition-01: According to condition-01, union of both the sub relations must contain all the attributes of relation R. So, we have- R‘ ( A , B , C ) ∪ R3 ( B , D ) =R(A,B,C,D) Clearly, union of the sub relations contain all the attributes of relation R. Thus, condition-01 satisfies. Condition-02: According to condition-02, intersection of both the sub relations must not be null. So, we have- R‘ ( A , B , C ) ∩ R3 ( B , D ) =B Clearly, intersection of the sub relations is not null. Thus, condition-02 satisfies. Condition-03: According to condition-03, intersection of both the sub relations must be the super key of one of the two sub relations or both. So, we have- R‘ ( A , B , C ) ∩ R3 ( B , D ) =B Now, the closure of attribute B is- B+ = { B , C , D } Now, we see- Attribute ‘B’ can not determine attribute ‘A’ of sub relation R’. Thus, it is not a super key of the sub relation R’. Attribute ‘B’ can determine all the attributes of sub relation R 3. Thus, it is a super key of the sub relation R3. Clearly, intersection of the sub relations is a super key of one of the sub relations. So, condition-03 satisfies. Thus, we conclude that the decomposition is lossless. Decomposition of R'(A, B, C) into R1(A, B) and R2(B, C)- Condition-01: According to condition-01, union of both the sub relations must contain all the attributes of relation R’. So, we have- R1 ( A , B ) ∪ R2 ( B , C ) = R’ ( A , B , C ) Clearly, union of the sub relations contain all the attributes of relation R’. Thus, condition-01 satisfies. Condition-02: According to condition-02, intersection of both the sub relations must not be null. So, we have- R1 ( A , B ) ∩ R 2 ( B , C ) =B Clearly, intersection of the sub relations is not null. Thus, condition-02 satisfies. Condition-03: According to condition-03, intersection of both the sub relations must be the super key of one of the two sub relations or both. So, we have- R1 ( A , B ) ∩ R 2 ( B , C ) =B Now, the closure of attribute B is- B+ = { B , C , D } Now, we see- Attribute ‘B’ can not determine attribute ‘A’ of sub relation R 1. Thus, it is not a super key of the sub relation R1. Attribute ‘B’ can determine all the attributes of sub relation R 2. Thus, it is a super key of the sub relation R2. Clearly, intersection of the sub relations is a super key of one of the sub relations. So, condition-03 satisfies. Thus, we conclude that the decomposition is lossless. Conclusion- Overall decomposition of relation R into sub relations R 1, R2 and R3 is lossless.