First page Back Continue Last page Graphics
Redundancy of Inference Rules
An inference rule r in a set of inference rules R for a type of constraints C is redundant if for all sets F of constraints of type C: F+{R-{r}} = F+
- Prove that none of the Armstrong rules are redundant in the set of (3) Armstrong rules.
- Prove that adding the union rule, the decomposition rule or the pseudotransitivity rule would make the set of rules redundant.
Notes:
Redundancy means that all the (logical) consequences we can deduce from a given set of constraints can be deduced using just a subset of the given inference rules. Note that it is important that we only consider constraints of a certain type. There may be logical consequences that cannot be deduced using the rules because they are of a different type.
Proving that a set of rules is not redundant is done by giving a small counterexample. We take a set of constraints and calculate all the consequences through the subset of rules. We then show that there is another consequence that is generated using the extra rule.
Example: to show that the reflexivity rule is not redundant we take the empty set of functional dependencies over a table with zero (or more) attributes. With augmentation and transitivity we cannot generate any fds because there are no fds to start from. With reflexivity however we can create the fd Ø Ø.
For augmentation it is easiest to start from two attributes A and B and show that augmentation is needed to generate A AB from A B.
For transitivity it is easiest to start from three attributes.
Using the smallest possible number of attributes keeps the size of F+ down!
Proving the redundancy of the union and other rules is done by proving these rules using the other rules. This has been done in the homework already. It is just important to note that this is the way to prove redundancy.