dbTalk Databases Forums  

functional dependencies and view equations

comp.databases.theory comp.databases.theory


Discuss functional dependencies and view equations in the comp.databases.theory forum.



Reply
 
Thread Tools Display Modes
  #1  
Old   
Mikito Harakiri
 
Posts: n/a

Default functional dependencies and view equations - 10-06-2003 , 06:50 PM






When solving example in Banchilhon&Spyratos paper I found that view
equations technique is applicable for proving lemmas about functional
dependencies as well.

Suppose we have functional dependency

A.x->A.y

By "->" definition

for any tuples a1,a2 from A ( a1.x = a2.x implies a1.y != a2.y )

which can be equivalently rewritten as

not exists a1,a2 ( a1.x = a2.x & a1.y != a2.y )

which gives immediately view equation

(select from A a1, A a2
where a1.x = a2.x and a1.y != a2.y) = DUM

/* Equation #1 */

Note, that SQL pseudo syntax above has empty column expression list in
the select clause in order to match void column list in the DUM table.

We'll prove Armstrong transitivity lemma. In addition to the Equation
#1 we demand

A.y->A.z

or equivalently

(select from A a1, A a2
where a1.y = a2.y and a1.z != a2.z) = DUM

/* Equation #2 */

We are asked to evaluate

select from A a1, A a2
where a1.x = a2.x and a1.z != a2.z

If it equals to DUM, then A.x->A.z follows. In the first step we add a
tautological predicate

select from A a1, A a2
where a1.x = a2.x and a1.z != a2.z
and (a1.y = a2.y or a1.y != a2.y)

and rewrite it as a union

select from A a1, A a2
where a1.x = a2.x and a1.z != a2.z
and a1.y = a2.y
union
select from A a1, A a2
where a1.x = a2.x and a1.z != a2.z
and a1.y != a2.y

and reshuffle the predicates conveniently

select from A a1, A a2
where a1.y = a2.y and a1.z != a2.z
and a1.x = a2.x
union
select from A a1, A a2
where a1.x = a2.x and a1.y != a2.y
and a1.z != a2.z

Finally, we notice that the left side of the union is a stricter
version than the left side of Equation #1. In other words, it
evaluates to DUM. Likewise, the right side of the union evaluates to
DUM too. This gives DUM as a result. QED

Reply With Quote
Reply




Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off



Powered by vBulletin Version 3.5.3
Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.