Re: satisfies algorithm

From: Brian Selzer <brian_at_selzer-software.com>
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

Original text of this message