lev@eng.umd.edu (Lev Novik) (03/12/91)
Hi! I have a problem: ----- Suppose we have a set of elements, and a set of inferences of the type "If we know _these_ elements, we can find _that_ one." Problem: find the smallest set from which we can derive all elements of te original set. ----- Can anybody refer me to any algorithm on this (preferably not NP).? Thanks. ------------------------------------ Lev Novik Dept. of Mathematics University of Maryland, College Park.
libkin@saul.cis.upenn.edu (Leonid Libkin) (03/12/91)
In article <1991Mar11.193909.10853@eng.umd.edu> lev@eng.umd.edu (Lev Novik) writes: >Hi! >I have a problem: >----- > Suppose we have a set of elements, and a set of inferences of >the type "If we know _these_ elements, we can find _that_ one." Problem: find >the smallest set from which we can derive all elements of te original set. >----- >Can anybody refer me to any algorithm on this (preferably not NP).? >Thanks. > >------------------------------------ >Lev Novik >Dept. of Mathematics >University of Maryland, College Park. This is the problem of finding minimal keys in relational schemes with functional dependencies. If you need to know all keys, their number may be exponential in the number of dependencies (inferences). Actually, you asked about _the_ smallest set, but such a set may not be unique. To find _a_ key takes polynomial time in the number of dependencies/inferences. ----------------------------------------------------------------------------- ! Leonid Libkin ! E-mail: libkin@saul.cis.upenn.edu ! ! Dept. of Comp. & Info. Sci. ! Voice: (215) 898 - 9510 or ! ! University of Pennsylvania ! (215) 222 - 8758 ! ! Philadelphia, PA 19104-6389 ! Fax: (215) 898 - 0587 ! -----------------------------------------------------------------------------