Dependency Preservation

Dependency Preservation:--

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

for each restriction do
begin

end

compute ;
if ( ) then return (true)
else return (false);

3. We can now show that our decomposition of Lending-schema is dependency preserving.
o The functional dependency
o bname assets bcity
o can be tested in one relation on Branch-schema.

o The functional dependency
o loan# amount bname
o 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 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 F' 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 and , and see whether they are equal, we can do this:
o Find F - F', the functional dependencies not checkable in one relation.
o See whether this set is obtainable from F' by using Armstrong's Axioms.
o 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 suffer from the repetition of information problem.
o Branch and loan data are separated into distinct relations.
o Thus we do not have to repeat branch data for each loan.
o If a single loan is made to several customers, we do not have to repeat the loan amount for each customer.
o This lack of redundancy is obviously desirable.
o We will see how this may be achieved through the use of normal forms.
BCNF
1. Now we can give a general method to generate a collection of BCNF schemas.
result := ;

done := false;

compute ;

while (not done) do
if (there is a schema in result that is not in BCNF)
then begin
let be a nontrivial
functional dependency that holds on

such that is not in ,and ;
result = (result ;
end
else done = true;

2. This algorithm generates a lossless-join BCNF decomposition. Why?
o We replace a schema with and .
o The dependency holds on .
o .
o So we have , and thus a lossless join.

3. Let's apply this algorithm to our earlier example of poor database design:
Lending-schema = (bname, assets, bcity, loan#, cname, amount)

The set of functional dependencies we require to hold on this schema are
bname assets bcity
loan# amount bname
A candidate key for this schema is {loan#, cname}.
We will now proceed to decompose:
The functional dependency
bname assets bcity
holds on Lending-schema, but bname is not a superkey.
We replace Lending-schema with
Branch-schema = (bname, assets, bcity)

Loan-info-schema = (bname, loan#, cname, amount)

Branch-schema is now in BCNF.
The functional dependency
loan# amount bname

holds on Loan-info-schema, but loan# is not a superkey.
We replace Loan-info-schema with
Loan-schema = (bname, loan#, amount)

Borrow-schema = (cname, loan#)

These are both now in BCNF.
We saw earlier that this decomposition is both lossless-join and dependency-preserving.
4. Not every decomposition is dependency-preserving.
o Consider the relation schema
o Banker-schema = (bname, cname, banker-name)
o
o The set F of functional dependencies is
o banker-name bname
o
o cname bname banker-name
o
o The schema is not in BCNF as banker-name is not a superkey.
o If we apply our algorithm, we may obtain the decomposition
o Banker-branch-schema = (bname, banker-name)
o
o Cust-banker-schema = (cname, banker-name)
o
o The decomposed schemas preserve only the first (and trivial) functional dependencies.
o The closure of this dependency does not include the second one.
o Thus a violation of cname bname banker-name cannot be detected unless a join is computed.
This shows us that not every BCNF decomposition is dependency-preserving.
5. It is not always possible to satisfy all three design goals:
o BCNF.
o Lossless join.
o Dependency preservation.
6. We can see that any BCNF decomposition of Banker-schema must fail to preserve
cname bname banker-name