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 F be a set of functional dependencies on schema R.
• Let {R1,R2, . . .,Rn} be a decomposition of R.
• The restriction of F to Ri is the set of all functional dependencies in F+ that include only attributes
  of Ri.
• Functional dependencies in a restriction can be tested in one relation, as they involve attributes in one
  relation schema.
• The set of restrictions F1, F2, . . ., Fn is the set of dependencies that can be checked eciently.
• We need to know whether testing only the restrictions is suffcient.
• Let F0 = F1, F2, . . ., Fn.
• F0 is a set of functional dependencies on schema R, but in general, F0
  6= F.
• However, it may be that F'+ = F+.
• If this is so, then every functional dependency in F is implied by F0, and if F0 is satis ed, then F must
  also be satisfied.
• A decomposition having the property that F0+ = F+ is a dependency-preserving decomposition.

2. The algorithm for testing dependency preservation follows this method.

compute F+
for each schema Ri in D do
begin
Fi .= the restriction of F+ to Ri,
end
F' = Ф ,
for each restriction Fi do
begin
F' = F ∪Fi
end
compute F'+,
if (F'+ = F+) then return (true)
else return (false),

3. We can now show that our decomposition of Lending-schema is dependency preserving.

• The functional dependency
  bname → assets bcity
  can be tested in one relation on Branch-schema.
• The functional dependency
  loan# → amount bname
  can be tested in Loan-schema.

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

5. An Easier Way To Test For Dependency Preservation

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

In other words, are the functional dependencies not easily checkable logically implied by those that are?
Rather than compute F+ and F'+, and see whether they are equal, we can do this.

• Find F - F', the functional dependencies not checkable in one relation.
• See whether this set is obtainable from F' 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).

Repetition of Information

1. Our decomposition does not su er from the repetition of information problem.

• Branch and loan data are separated into distinct relations.
• Thus we do not have to repeat branch data for each loan.
• If a single loan is made to several customers, we do not have to repeat the loan amount for each customer.
• This lack of redundancy is obviously desirable.
• We will see how this may be achieved through the use of normal forms.