On the undecidability of implications between embedded multivalued database dependencies

摘要

By an implication for database dependencies we mean an expression H => F, where H is a conjunction of dependencies and F a single dependency. Fixing a class of such implications, a solution of the (finite) implication problem consists in an algorithmic procedure deciding for every implication in the class whether or not it holds in all (finite) databases (in which it is to be interpreted). In [3] this problem was studied for dependencies which are functional (fd) or embedded multivalued (emvd). As pointed out by Luc Segoufin, what was really shown is the following.