Re: satisfies algorithm


<aarklon@xxxxxxxxx> wrote in message
news:94535fa5-c35a-4eb7-a975-294496da668d@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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.


.

Relevant Pages

  • satisfies algorithm
    ... the following is the algorithm which i saw in schaum series ... book(fundamentals of relational databases) ... satisfies or does not satisfies a given functional dependency A -> B. ...
    (comp.databases.theory)
  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... I would tailor which algorithm to start with by how the student thinks ... If you only learn the beautiful side of programming, ...
    (comp.programming)
  • Re: puzzle
    ... >> Christopher Barber wrote: ... >> or understanding among programming professionals. ... > algorithm "close to" O. ... bubble sort, it is almost always acceptable to use an interchange sort: ...
    (comp.programming)
  • Re: The ultimate luxury ?
    ... >>My definition in terms of imposing a linear order on a set is abstract ... >>and corresponds not to the algorithm of sorting, ... > that the CS dudes of today would not know what sort means. ... Jesse Hughes ...
    (sci.physics)
  • Re: Help me with references
    ... I can't think of any situation in which bubble sort is ... > best choice for a sorting algorithm in a real machine. ... Quicksort is optimized for large Ns. ... I picked Bubblesort because your original post implied something along ...
    (comp.lang.java.help)