On the Complexity of Testing Implications of Functional and Join Dependencies
David Maier, Yehoshua Sagiv, Mihalis Yannakakis · Journal of the ACM · 1981
It iS shown that testing whether a dependency o is unpiled by a set ~ of functional and join dependencies is NP-hard if o is a join dependency, but it reqmres only O(l u Ill ~ II) time ff o Is either a funcuonal or a multivalued dependency ( j U [ is the number of elements in the set of all the attributes U, and II ~ II as the space required to write down ~).The fact that inferring join dependencies is NP-hard follows from the followmg stronger result.It is proved that if ~ is a set of one jom dependency and several funcuonal dependencies, then testing whether Z implies a join dependency o is NP-complete By combming this result with a recent result of Beeri and Var& ~t can be proved that if 2 is a set of one join dependency and several multivalued dependencies, then testing whether ~ unphes a join dependency o Is NP-hard It is also shown that the problem of deciding whether a JD-rule can be applied to a tableau T and the problem of testing whether a relation r does not obey a join dependency are NP-complete.The first problem is NP-complete even if T can be obtamed from a tableau corresponding to a join dependency by applying some FD-rules.As a result, It follows that deciding whether the join of several relations obtained by projecUon from a umversal instance is not equal to the universal instance is NP-complete.Finally, it is proved that there is no umversal constant n such that for every set of multlvalued dependencies ~ and a join dependency o that is not unpiled by ~, there is a relation with no more than n tuples in which holds but o fails.