This page was exported from EDUGRABS [ http://www.edugrabs.com ]
Export date:Sat Mar 25 13:24:36 2017 / +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