Dependency Preservation

1. Another desirable property in database design is dependency preservation.
   • We would like to check easily that updates to the database do not result in illegal relations being created.
   • It would be nice if our design allowed us to check updates without having to compute natural joins.
   • To know whether joins must be computed, we need to determine what functional dependencies may be tested by checking each relation individually.
   • Let be a set of functional dependencies on scheme .
   • Let be a decomposition of .
   • The restriction of to is the set of all functional dependencies in that include only attributes of .
   • Functional dependencies in a restriction can be tested in one relation, as they involve attributes in one relation scheme.
   • The set of restrictions is the set of dependencies that can be checked efficiently.
   • We need to know whether testing only the restrictions is sufficient.
   • Let .
   • is a set of functional dependencies on scheme , but in general, .
   • However, it may be that .
   • If this is so, then every functional dependency in is implied by , and if is satisfied, then must also be satisfied.
   • A decomposition having the property that is a dependency-preserving decomposition.
2. The algorithm for testing dependency preservation follows this method:

   

3. We can now show that our decomposition of Lending-scheme is dependency preserving.
   • The functional dependency

     

     can be tested in one relation on Branch-scheme.

   • The functional dependency

     

     can be tested in Loan-info scheme.

4. As the above example shows, it is often easier not to apply the algorithm shown to test dependency preservation, as computing takes exponential time.

5. An Easier Way To Test For Dependency Preservation

   Really we only need to know whether the functional dependencies in and not in are implied by those in .

   In other words, are the functional dependencies not easily checkable logically implied by those that are?

   Rather than compute and , and see whether they are equal, we can do this:

   • Find , the functional dependencies not checkable in one relation.
   • See whether this set is obtainable from by using Armstrong's Axioms.
   • This should take a great deal less work, as we have (usually) just a few functional dependencies to work on.
   Use this simpler method on exams and assignments (unless you have exponential time available to you).