Here
- Proof of the completeness
Armstrong’s Axioms
- Additional rules derived from axioms
- Union
- if A B and A C, then A BC
- Decomposition
- if A BC, then A B and A C
Completeness of the
Armstrong’s Axioms
- Proving that Armstrong’s axioms are a complete set of inference rules
- Armstrong’s rules generate all FDs in F*
Completeness of the
Armstrong’s Axioms
- First define X+, the closure of X with respect to F:
- X+ is the set of attributes A such that X A can be deduced from Armstrong’s axioms
- Note that we can deduce that X Y for some set Y by consulting Armstrong’s axioms if and only if Y X+
Completeness of the
Armstrong’s Axioms
- Note that we can deduce that X Y for some set Y by consulting Armstrong’s axioms if and only if Y X+
- X Y F+ Y X+
- Y X+ and suppose that A Y then X A F+ (definition of X+)
- A Y: X A F+
- X Y F+ (union rule)
- X Y F+ Y X+
- X Y F+ and suppose that A Y then X A F+ (decomposition rule)
- A X+ (definition of X+)
- A Y: A X+
- Y X+
Completeness of the
Armstrong’s Axioms
- Idea
- To establish completeness, it is sufficient to show:
- if X Y cannot be deduced from Armstrong’s axioms
(so X Y not in F+)
then there is a relational instance r for R in which all the dependencies in F are true, but X Y does not hold
(so X Y not in F*)
Completeness of the
Armstrong’s Axioms
- Idea
- If X Y cannot be deduced from Armstrong’s axioms then there is a relational instance r for R in which all the dependencies in F are true, but X Y does not hold
Completeness of the
Armstrong’s Axioms
- Suppose one can not deduce X Y from Armstrong’s axioms
- Consider the instances r for R with 2 tuples
- (make the two tuples agree on X+ but disagree elsewhere)
Completeness of the
Armstrong’s Axioms
- Check that all the dependencies in F are true:
- Suppose that V W is a dependency in F
- If V is not a subset of X+, the dependency holds in r
- If V is a subset of X+, then both X V, and X W can be deduced by Armstrong’s axioms. This means that W is a subset of X+, and thus V W holds in r
Completeness of the
Armstrong’s Axioms
- Check that all the dependencies in F are true
- Illustration
- O N is a dependency in F but O is not a subset of X+, the dependency holds in r
- M N is a dependency in F and M is a subset of X+, then both L M, and L N can be deduced by Armstrong’s axioms. This means that N is a subset of X+, and thus M N holds in r
Completeness of the
Armstrong’s Axioms
- Confirm that X Y does not hold in r:
- Recall that we can deduce that X Y for some set Y by consulting Armstrong’s axioms if and only if Y X+
- By assumption, we can’t deduce that X Y holds in r
- Hence Y contains an attribute not in the subset X+, confirming that X Y does not hold in r
Completeness of the
Armstrong’s Axioms
- We have proved the correctness (last colstructie) and the completeness of Armstrong’s Axioms:
- How to prove the soundness of another set of rules?
- From the definition
- Deduce from the Armstrong’s Axioms
- How to disprove their soundness
Completeness of the
Armstrong’s Axioms
- How to prove completeness of another set of rules?
- Repeat the given proof
- Deduce Armstrong’s Axioms from them
- How to disprove completeness
- By showing (via a counterexample)
that some consequence of Armstrong's rules
cannot be deduced from them
Completeness of the
Armstrong’s Axioms
- Exercise
- Are the following set of rules a sound and complete set of inference rules?
- S1: X X
- S2: if X Y then XZ Y
- S3: if X Y, Y Z then XW ZW
Solution (soundness)
Solution (completeness)
Completeness of the
Armstrong’s Axioms
- Exercises
- Are the following set of rules a complete set of inference rules?