# Re: satisfies algorithm

Date: Fri, 25 Jul 2008 08:54:05 -0400

Message-ID: <92kik.14667$cW3.1512@nlpi064.nbdc.sbc.com>

<aarklon_at_gmail.com> wrote in message

news:94535fa5-c35a-4eb7-a975-294496da668d_at_z11g2000prl.googlegroups.com...

*> Hi all,*

*>*

*>*

*> the following is the algorithm which i saw in schaum series*

*> book(fundamentals of relational databases)*

*>*

*> satisfies algorithm*

*>*

*> this algorithm shown below can be used to determine if a relation r*

*> satisfies or does not satisfies a given functional dependency A -> B.*

*> the input to the algorithm is a given relation r and a functional*

*> dependency A -> B. the output of the algorithm is true if r satisfies*

*> A -> B; otherwise the output is false.*

*>*

*> 1) sort the tuples of the relation r on the A attribute(s) so that*

*> tuples with equal values under A are next to each other*

*>*

*> 2) check that tuples with equal values under attribute(s) A also have*

*> equal values under attribute(s) B*

*>*

*> 3) if any tuples of r meet condition 1 but fail to meet condition 2*

*> the output of the algorithm is false. otherwise, the relation*

*> satisfies the functional dependency and the o/p of the algorithm is*

*> true.*

*>*

*> now my question is there any other better method (other than inference*

*> axioms) ?*

Yes. Normalize. A schema that is in BCNF does not have any nontrivial functional dependencies where the determinant is not also a key. Where there is a key, there should also be a unique index of some sort, making it impossible for there to be two tuples with the same determinant. Received on Fri Jul 25 2008 - 07:54:05 CDT