Closure of a Set of Functional Dependencies Given a set F set of functional dependencies,there are certain other functional dependencies that are logically implied by F. ·lfA>B and B→C,then we can infer that A>C ·etc. The set of all functional dependencies logically implied by Fis the closure of F. We denote the closure of Fby F*. Database System Concepts-7th Edition 7.14 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.14 ©Silberschatz, Korth and Sudarshan th Edition Closure of a Set of Functional Dependencies ▪ Given a set F set of functional dependencies, there are certain other functional dependencies that are logically implied by F. • If A → B and B → C, then we can infer that A → C • etc. ▪ The set of all functional dependencies logically implied by F is the closure of F. ▪ We denote the closure of F by F +
Keys and Functional Dependencies 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 ac K,→R Functional dependencies allow us to express constraints that cannot be expressed using superkeys.Consider the schema: in_dep (ID.name,salary,dept name,building,budget) We expect these functional dependencies to hold: dept name→building lD→building but would not expect the following to hold: dept name→salary Database System Concepts-7th Edition 7.15 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.15 ©Silberschatz, Korth and Sudarshan th Edition Keys and Functional Dependencies ▪ 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: in_dep (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
Use of Functional Dependencies We use functional dependencies to: 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. To 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 instructormay,by chance,satisfy name→lD. Database System Concepts-7th Edition 7.16 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.16 ©Silberschatz, Korth and Sudarshan th Edition Use of Functional Dependencies ▪ We use functional dependencies to: • 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. • To 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
Trivial Functional Dependencies 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 Ba Database System Concepts-7th Edition 7.17 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.17 ©Silberschatz, Korth and Sudarshan th Edition Trivial Functional Dependencies ▪ 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
Lossless Decomposition We can use functional dependencies to show when certain decomposition are lossless. For the case of R=(R1,R2),we require that for all possible relations r on schema R r=ΠR1(r)凶ΠR2(r) A decomposition of R into R and R2 is lossless decomposition if at least one of the following dependencies is in F+: ·R1∩R2→R1 ·R1∩R2→R2 The above functional dependencies are a sufficient condition for lossless join decomposition;the dependencies are a necessary condition only if all constraints are functional dependencies Database System Concepts-7th Edition 7.18 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 7.18 ©Silberschatz, Korth and Sudarshan th Edition Lossless Decomposition ▪ We can use functional dependencies to show when certain decomposition are lossless. ▪ For the case of R = (R1 , R2 ), we require that for all possible relations r on schema R r = R1 (r ) R2 (r ) ▪ A decomposition of R into R1 and R2 is lossless decomposition if at least one of the following dependencies is in F+ : • R1 R2 → R1 • R1 R2 → R2 ▪ The above functional dependencies are a sufficient condition for lossless join decomposition; the dependencies are a necessary condition only if all constraints are functional dependencies