DataBase System Functional Dependencies G In the emp info table, we get emp_into id emp name skill_id skill_name skill_ date skill_Iv1 09112 Jones librarian 03-15-99 12 09112 Jones 26 PC-admin 06-30-98 10 09112 Jones 89 word-proc 01-15-00 12 12231 Smith 26 PC-admin 0415-99 12231 Smith 39 bookkeeping 07-30-97 13597 Brown 27 statistic 09-15-99 14131 Blake 事非非 26 PC-admin 05-30-98 14131 Blake 89 word-proc 09-3099 10 emp id ->emp name emp id→ emp phone? emp id ->dep name and emp phonet emp id Haichang Gao, Software School, Xidian University 18
DataBase System Haichang Gao , Software School , Xidian University 18 In the emp_info table, we get Functional Dependencies emp_id → emp_name emp_id → emp_phone? emp_id → dep_name ?, and emp_phone emp_id
DataBase System Functional Dependencies Analyze the following tables(suppose they are valid) T2 row#A B A B AB y X x1 y1 y y x3 x1 4 X 3|y2 5 x5 y2 x2 y4 X6 y x4 y3 x4|y4 T1:A→B T2:A→B T3:A→B B+A B→A B+A Haichang Gao, Software School, Xidian University 19
DataBase System Haichang Gao , Software School , Xidian University 19 Analyze the following tables (suppose they are valid) Functional Dependencies T2: A → B B → A T1: A → B B A T3: A → B B A
DataBase System CE Logical implications among functional dependencies G Inclusion rule(包含规则) H Given a table t with a specified heading Head(T). IfX and Y are sets of attributes contained in Head(D), andRx, then XY. Proof. By def, need only demonstrate that if two rows u and v agree on X they must agree on Y. But Y is a subset of X, so seems obvious Trivial Dependency(平凡的函数依赖) H A Trivial Dependency is a FD of the form X-Y, in a table t wherexuy C Head(t). That will hold for any possible content of the table T. 矿(更确切地说明什么是 trivial dependency) A Given a trivial dependency x y in T, it must be the case that Ysx. eg.A→A,AB→A Haichang Gao, Software School, Xidian University 20
DataBase System Haichang Gao , Software School , Xidian University 20 Inclusion Rule (包含规则) Given a table T with a specified heading Head(T). If X and Y are sets of attributes contained in Head(T), and Y X, then X→Y. Proof. By def, need only demonstrate that if two rows u and v agree on X they must agree on Y. But Y is a subset of X, so seems obvious. Trivial Dependency (平凡的函数依赖) A Trivial Dependency is a FD of the form X →Y, in a table T where X ∪ Y Head(T). That will hold for any possible content of the table T. (更确切地说明什么是trivial dependency) Given a trivial dependency X →Y in T, it must be the case that Y X. e.g. A →A, AB →A Logical implications among functional dependencies
DataBase System 多 Armstrongs Axioms ρ Armstrong' s Axiom(阿姆斯特朗公理1974) Al: Inclusion rule(包含规则): ifEx, then X→Y 证明:对于关系模式R<UF>的任一关系中的任意两个元组 t和s,若Ⅺ]=SⅪ],由于YX,则tY]=SY],故X→Y。 E Example. customer name loan number -> customer name customer name ->customer name Haichang Gao, Software School, Xidian University 21
DataBase System Haichang Gao , Software School , Xidian University 21 Armstrong’s Axiom (阿姆斯特朗公理 1974) A1: Inclusion rule(包含规则): if Y X, then X→Y 证明：对于关系模式R<U,F>的任一关系r中的任意两个元组 t和s，若t[X]=s[X]，由于Y X，则t[Y]=s[Y]，故X→Y。 Example: ➢ customer_name, loan_number → customer_name ➢ customer_name → customer_name Armstrong’s Axioms
DataBase System 多 Armstrongs Axioms Armstrong' S Axion(阿姆斯特朗公理1974) A2: Transitivity rule(传递规则):iX→ Y and y→Z, then x→Z 证明:对于关系模式R<U,F>的任一关系r中的任意 两个元组t和,若Ⅺ=S[Ⅺ,由于X→Y,有Y=s; 再由Y→Z,有幻团,所以FFX→z A Example For relation: S( sno, sname, sdept, dept manager sH0→> sdept, sdept→ dept manager THEN: sno -> dept manager Haichang Gao, Software School, Xidian University 22
DataBase System Haichang Gao , Software School , Xidian University 22 Armstrong’s Axiom (阿姆斯特朗公理 1974) A2: Transitivity rule(传递规则): if X → Y and Y → Z , then X → Z 证明：对于关系模式R<U，F> 的任一关系 r中的任意 两个元组 t和s，若t[X]=s[X]，由于X→Y，有 t[Y]=s[Y]； 再由Y→Z，有t[Z]=s[Z]，所以F ╞ X→Z。 Example: For relation: S( sno, sname, sdept, dept_manager ) ➢ sno → sdept, sdept → dept_manager ➢ THEN: sno → dept_manager Armstrong’s Axioms