Decomposition using Functional Dependency

Dependency preservation

1. Prepared by: RAJ NAIK SY CE-1 150410107053 Decomposition using FD- dependency preservation

2. Fuctional dependencies play a key role in differentiating good database designs from bad database designs. Let R be a relation schema, α  R and β  R The functional dependency α  β holds on R if and only if for any legal relations r(R), whenever any two tuples t1 and t2 of R agree on the attributes α , they also agree on the attributes β . That is, t1 [ α ] = t2 [ α ]  t1 [ β ] = t2 [ β ] Functional Dependencies

3. Example: Consider r(A,B) with the following instance of r. On this instance, A  B does NOT hold, but B  A does hold. A functional dependency is a generalization of the notion of a key Functional Dependencies 1 4 1 7 4 6

4. K is a superkey or for relation schema R if and only if K  R K is a candidate key for R if and only if K  R, and for no α  K, α  R Functional dependencies allow us to express constraints that cannot be expressed using superkeys . Functional Dependencies

5. Consider the schema: inst_dept (ID, name, salary, dept_name , building, budget ) We expect these functional dependencies to hold: dept_name  building ID  building but would not expect the following to hold: dept_name  salary Functional Dependencies

6. A functional dependency is trivial if it is satisfied by all instances of a relation Example: ID, name  ID name  name In general, α  β is trivial if β  α Functional Dependencies

7. The most important properties are Armstrong's axioms, which are used in database normalization: Subset Property If Y is a subset of X , then X → Y Augmentation If X → Y , then XZ → YZ Transitivity If X → Y and Y → Z , then X → Z Properties of functional dependencies

8. From these rules, we can derive these secondary rules: Union : If X → Y and X → Z , then X → YZ Decomposition : If X → YZ , then X → Y and X → Z Pseudotransitivity : f X → Y and WY → Z , then XW → Z Properties of functional dependencies

9. We can avoid update anomalies by decomposition of the original relation. The relation scema R is decomposed into relation schemas: {R1,R2,R3,……., Rn } in such a way that R 1  R2  …  R n = R Introduction to Decomposition

10. Lending_schema = ( Branch_name , Branch_city , Assets, Cusomer_name , Loan_number , Amount) The Lending schema is decomposed into following two relations: 1) Branch_customer_schema = ( Branch_name , Branch_city , Assets, Cusomer_name ) 2) Customer_loan_schema = ( Cusomer_name , Loan_number , Amount ) Example

11. Branch_Name Branch_City Assets Customer_Name Downtown Brooklyn 90000 Jones Redwood Palo Alto 21000 Smith Perryridge Horseneck 90000 Jackson Mianus Horseneck 80000 Jones Northtown Rye 37000 Hayes Customer_Name Loan_No Amount Jones L-17 10000 Smith L-23 2000 Jackson L-14 1500 Jones L-11 900 Hayes L-16 1300 The Branch_customer Relation The Customer_loan Relation

12. Branch_Name Branch_City Assets Customer_Name Loan_No Amount Downtown Brooklyn 90000 Jones L-17 10000 Downtown Brooklyn 90000 Jones L-11 9000 Redwood Palo Alto 21000 Smith L-23 2000 Perryridge Horseneck 90000 Jackson L-14 1500 Mianus Horseneck 80000 Jones L-11 900 Mianus Horseneck 80000 Jones L-17 1000 Northtown Rye 37000 Hayes L-16 1300 The result of this join is shown below: The relation Branch_customer Customer_loan

13. If the relation Branch_customer and Customer_loan is compared with the original lending relation, we observe that: Every tuple in lending relation is in Branch_customer and Customer_loan relation. The relation Branch_customer and Customer_loan contain following additional tuples: (Downtown,Brooklyn,90000,Jones,L-11,9000) (Mianus,Horseneck,80000,Jones,L-17,1000)

14. 2. Consider the query: “Find all the branches that have made a loan in an amount less than Rs . 1000.” The result of this query using the lending relation is : Mianus . The result of the same query using the relation Branch_customer and Customer_loan is: Downtown and Mianus .

15. From the above two cases we can say that the decomposition of lending relation into Branch_customer and Customer_loan results in bad database design. It results in loss of information and repetition of information. Because of loss of i nformation, we call the decomposition of lending relation into Branch_customer and Customer_loan a lossy decomposition or a lossy -join decomposition.

16. Decomposition help us eliminate redundancy, root of data anomalies. There are two important properties associated with decomposition: 1. Lossless join 2. Dependency Preservation Desirable Properties of Decomposition

17. This property ensures that any instance of the original relation can be identifies from the corresponding instances in the smaller relation. Let R be a relational schema, and let F be a s et of functional dependencies on R. Let R1 and R2 form a decomposition of R. This decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies is in F + R1  R2  R1 R1  R2  R2 In other word, if R1  R2 forms a superkey of either R1 or R2, the decomposition of R is a lossless-join decomposition. Lossless join

18. Question: Let R(A,B,C) and F=(A B ).Check the decomposition of R into R1(A,B) and R2(A,C) . R1  R2 is A which is comman attribute. A B is the FD in F. (augmentation rule) A AB which is relation R1. Thus, R1  R2 is satisfie s. Hence, above decomposition is lossless-join decomposition. Example of Lossless-join

19. Question : Let R(A,B,C) and F=(A B ).Check the decomposition of R into R1(A,B) and R2(B,C) . R1  R2 is B which is comman attribute. But B is not a superkey of either R1 or R2. Hence this decomposition is not a lossless-join decomposition. Example of Lossless-join

20. This property ensures that a constraint on the original relation can be maintained by simply enforcing some constraint on each of the smaller relation. Given a relational schema R and set of fuctional dependencies associated with it is F. R is decomposed into the relation schema R1,R2,… Rn with functional dependencies F1,F2,…Fn. Dependency Preservation

21. Then the decomposition is dependency preserving if the closure of F’ (where F’=F1,F2,…. Fn ) is identical to F +. F’ + =F + Getting lossless decomposition is necessary. Dependency Preservation

22. Question : R=(A, B, C), F={A  B, B  C} Decomposition of R: R1=(A, C) R2=(B, C) Does this decomposition preserve the given dependencies? In R1 the following dependencies hold: F1’={A  A, C  C, A  C, AC  AC} In R2 the following dependencies hold: F2’= {B  B, C  C, B  C, BC  BC} The set of nontrivial dependencies hold on R1 and R2: F‘ = {B  C, A  C} A  B can not be derived from F’, so this decomposition is NOT dependency preserving. Example of Dependency Preservation

23. Question : R=(A, B, C), F={A  B, B  C} Decomposition of R: R1=(A, B) R2=(B, C) Does this decomposition preserve the given dependencies? In R1 the following dependencies hold: F1={A  B, A  A, B  B, AB  AB} In R2 the following dependencies hold: F2= {B  B, C  C, B  C, BC  BC} F’= F1’ U F2’ = {A  B, B  C, trivial dependencies} In F’ all the original dependencies occur, so this decomposition preserves dependencies. Example of Dependency Preservation