This page was exported from EDUGRABS [ http://www.edugrabs.com ] Export date:Thu Apr 26 15:23:19 2018 / +0000 GMT ___________________________________________________ Title: Inference Rules For Functional Dependencies --------------------------------------------------- Inference Rules For Functional Dependencies - Let S be the set of functional dependencies that are specified on relation schema R. Numerous other dependencies can be inferred or deduced from the functional dependencies in S. Example : Let S = {A → B, B → C} We can infer the following functional dependency from S: A → C Armstrong's Inference Rules - Let A, B and C and D be arbitrary subsets of the set of attributes of the giver relation R, and let AB be the union of A and B. Then,⇒→ Reflexivity : If B is subset of A, then A → B Augmentation :  If A → B, then AC → BC Transitivity : If A → B and B → C, then A → C. Projectivity or Decomposition Rule :  If A → BC, Then A → B and A → C Proof : Step 1 : A → BC (GIVEN) Step 2 : BC → B (Using Rule 1, since B ⊆ BC) Step 3 : A → B (Using Rule 3, on step 1 and step 2) Union or Additive Rule :  If A→B, and A→C Then A→BC. Proof : Step 1 : A → B (GIVEN) Step 2 : A → C (given) Step 3 : A → AB (using Rule 2 on step 1, since AA=A) Step 4 : AB → BC (using rule 2 on step 2) Step 5 : A → BC (using rule 3 on step 3 and step 4) Pseudo Transitive Rule :  If A → B, DB → C, then DA → C Proof : Step 1 : A → B (Given) Step 2 : DB → C (Given) Step 3 : DA → DB (Rule 2 on step 1) Step 4 : DA → C (Rule 3 on step 3 and step 2) These are not commutative as well as associative. i.e. if X → Y then Y → X   x (not possible) Composition Rule : If A → B, and C → D, then AC → BD. Self Determination Rule : A → A is a self determination rule. Question 1: Prove or disprove the following inference rules for functional dependencies. Note: Read "⇒" as implies a. {X → Y, Z → W} ⇒ XZ → YW ?? b. {X → Y, XY → Z} ⇒ X → Z c. {XY → Z, Y → W} ⇒ XW → Z Solution : Method : Use Armstrong's Axioms or Attribute closure to prove or disprove. a. {X → Y, Z → W} ⇒ XZ → YW ?? XZ → XZ XZ → XW (Z -> W) XZ → W (decomposition rule) XZ → XZ XZ → YZ (X -> Y) XZ → Y (decomposition rule) ⇒ XZ → YW (union rule) Hence True. b. {X → Y, XY → Z} ⇒ X → Z ?? XY→Z XX → Z (pseudotransitivity rule as X → Y) ⇒ X → Z Hence True. c. {XY → Z, Y → W} ⇒ XW → Z ?? W → W X → X Y → YW Z → Z WX → WX WY → WY WZ → WZ XY → WXYZ XZ → XZ YZ → WYZ Therefore WX → Z is not true You can also find the attribute closure for WX and show that closure set does not contain Z. Question 2: Consider a relational scheme R with attributes A,B,C,D,F and the FDs A → BC B → E CD → EF Prove that functional dependency AD → F holds in R. Step 1 : A → BC (Given) Step 2 : A → C (Decomposition Rule applied on step 1) Step 3 : AD → CD (Augmentation Rule applied on step 2) Step 4 : CD → EF (Given) Step 5 : AD → EF (transivity Rule applied on step 3 and 4) Step 6 : AD → F (Decomposition Rule applied on step 5) Previous Home Next Trivial and Non Trivial FD examples Closure of a Set (X+) and Applications of Closure --------------------------------------------------- Images: --------------------------------------------------- --------------------------------------------------- Post date: 2015-06-26 06:41:31 Post date GMT: 2015-06-26 06:41:31 Post modified date: 2015-12-16 13:10:12 Post modified date GMT: 2015-12-16 13:10:12 ____________________________________________________________________________________________ Export of Post and Page as text file has been powered by [ Universal Post Manager ] plugin from www.gconverters.com