Example of Lossless Decomposition Decomposition of R=(A,B,C) R1=(A,B) R2=(B,C) AB AB B C a 1 A 1 1 A 2 B B 2 2 B r Πa.B(r) Π8.c) AB C ΠA()凶ΠB(r) 1 2 B Database System Concepts-7th Edition 7.9 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 7.9 ©Silberschatz, Korth and Sudarshan th Edition Example of Lossless Decomposition ▪ Decomposition of R = (A, B, C) R1 = (A, B) R2 = (B, C)
Normalization Theory Decide whether a particular relation R is in "good"form. In the case that a relation R is not in "good"form,decompose it into set of relations {R1,R2,...R}such that Each relation is in good form The decomposition is a lossless decomposition Our theory is based on: Functional dependencies Multivalued dependencies Database System Concepts-7th Edition 7.10 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.10 ©Silberschatz, Korth and Sudarshan th Edition Normalization Theory ▪ Decide whether a particular relation R is in “good” form. ▪ In the case that a relation R is not in “good” form, decompose it into set of relations {R1 , R2 , ..., Rn } such that • Each relation is in good form • The decomposition is a lossless decomposition ▪ Our theory is based on: • Functional dependencies • Multivalued dependencies
Functional Dependencies There are usually a variety of constraints(rules)on the data in the real world. For example,some of the constraints that are expected to hold in a university database are: Students and instructors are uniquely identified by their ID. Each student and instructor has only one name. Each instructor and student is(primarily)associated with only one department. Each department has only one value for its budget,and only one associated building. Database System Concepts-7th Edition 7.11 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.11 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies ▪ There are usually a variety of constraints (rules) on the data in the real world. ▪ For example, some of the constraints that are expected to hold in a university database are: • Students and instructors are uniquely identified by their ID. • Each student and instructor has only one name. • Each instructor and student is (primarily) associated with only one department. • Each department has only one value for its budget, and only one associated building
Functional Dependencies (Cont.) An instance of a relation that satisfies all such real-world constraints is called a legal instance of the relation; A legal instance of a database is one where all the relation instances are legal instances Constraints on the set of legal relations. Require that the value for a certain set of attributes determines uniquely the value for another set of attributes. A functional dependency is a generalization of the notion of a key. Database System Concepts-7th Edition 7.12 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.12 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies (Cont.) ▪ An instance of a relation that satisfies all such real-world constraints is called a legal instance of the relation; ▪ A legal instance of a database is one where all the relation instances are legal instances ▪ Constraints on the set of legal relations. ▪ Require that the value for a certain set of attributes determines uniquely the value for another set of attributes. ▪ A functional dependency is a generalization of the notion of a key
Functional Dependencies Definition Let R be a relation schema aR and BCR The functional dependency 0→B holds on R if and only if for any legal relations r(R),whenever any two tuples f and t,of ragree on the attributes a,they also agree on the attributes B.That is, tila]=t2 [a]tlB]=t2[B] Example:Consider r(A,B)with the following instance of r. 4 1 5 37 ■On this instance,B>A hold;A→B does NOT hold, Database System Concepts-7th Edition 7.13 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.13 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies Definition ▪ 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 [ ] ▪ Example: Consider r(A,B ) with the following instance of r. ▪ On this instance, B → A hold; A → B does NOT hold, 1 4 1 5 3 7