Re: satisfies algorithm

From: Brian Selzer <>
Date: Fri, 25 Jul 2008 08:54:05 -0400
Message-ID: <92kik.14667$>

<> wrote in message
> 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