On the Undecidability of Implications between Embedded Multivalued Database Dependencies

The implication and finite implication problems for embedded multivalued database dependencies are both shown to be algorithmically undecidable. The proof is by an interpretation of semigroup word problems via systems of permuting equivalence relations into database dependencies. In contrast, it is shown that for each fixed premise H one has a decision procedure for implications H F.