Functional Dependencies (Cont.) Let R be a relation schema acR and BCR The functional dependency a→B holds on R if and only if for any legal relations r(R),whenever any two tuples f and t2 of r agree on the attributes a,they also agree on the attributes B.That is, t[o侧=t2[o→t[B]=t2[β] Example:Consider r(A,B with the following instance of r. 5 3 7 On this instance,A->B does NOT hold,but B->A does hold. Database System Concepts-6th Edition 8.12 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 8.12 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies (Cont.) 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, A → B does NOT hold, but B → A does hold. 1 4 1 5 3 7
Functional Dependencies(Cont.) K is a superkey 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 acK,→R Functional dependencies allow us to express constraints that cannot be expressed using superkeys.Consider the schema: inst dept (ID.name,salary.dept name,building,budget ) We expect these functional dependencies to hold: dept name->building and lD→building but would not expect the following to hold: dept name→salary Database System Concepts-6th Edition 8.13 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.13 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies (Cont.) K is a superkey 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. Consider the schema: inst_dept (ID, name, salary, dept_name, building, budget ). We expect these functional dependencies to hold: dept_name→ building and ID → building but would not expect the following to hold: dept_name → salary
Use of Functional Dependencies We use functional dependencies to: test relations to see if they are legal under a given set of functional dependencies. If a relation r is legal under a set F of functional dependencies,we say that rsatisfies F. specify constraints on the set of legal relations We say that F holds on R if all legal relations on R satisfy the set of functional dependencies F. Note:A specific instance of a relation schema may satisfy a functional dependency even if the functional dependency does not hold on all legal instances. For example,a specific instance of instructor may,by chance,satisfy name->ID. Database System Concepts-6th Edition 8.14 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.14 ©Silberschatz, Korth and Sudarshan th Edition Use of Functional Dependencies We use functional dependencies to: test relations to see if they are legal under a given set of functional dependencies. If a relation r is legal under a set F of functional dependencies, we say that r satisfies F. specify constraints on the set of legal relations We say that F holds on R if all legal relations on R satisfy the set of functional dependencies F. Note: A specific instance of a relation schema may satisfy a functional dependency even if the functional dependency does not hold on all legal instances. For example, a specific instance of instructor may, by chance, satisfy name → ID
Functional Dependencies (Cont.) A functional dependency is trivial if it is satisfied by all instances of a relation Example: ,lD,name→lD name>name In general,a>B is trivial if Bca Database System Concepts-6th Edition 8.15 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.15 ©Silberschatz, Korth and Sudarshan th Edition Functional Dependencies (Cont.) 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
Closure of a Set of Functional Dependencies Given a set F of functional dependencies,there are certain other functional dependencies that are logically implied by F. For example:If A->B and B->C,then we can infer that A> C The set of all functional dependencies logically implied by F is the closure of F. We denote the closure of F by F+. F+is a superset of F. Database System Concepts-6th Edition 8.16 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 8.16 ©Silberschatz, Korth and Sudarshan th Edition Closure of a Set of Functional Dependencies Given a set F of functional dependencies, there are certain other functional dependencies that are logically implied by F. For example: If A → B and B → C, then we can infer that A → C The set of all functional dependencies logically implied by F is the closure of F. We denote the closure of F by F+. F+ is a superset of F