Corrigendum to ``On the undecidability of implications between embedded multivalued database dependencies'' (Q859834): Difference between revisions

By an implication for database dependencies we mean an expression \(H\Rightarrow F\), where \(H\) is a conjunction of dependencies and \(F\) is 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 our original paper [Inf. Comput. 122, No. 2, 221--235 (1995; Zbl 1096.68608)] 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. Theorem 1. The implication problem and the finite implication problem for implications \(H\Rightarrow F\), where \(F\) is an emvd and \(H\) is a conjunction of emvds and fds, are unsolvable. The claimed extension to emvds, alone, relied on an elimination of fds from the problem which was attributed to \textit{C. Beeri} and \textit{M. Y. Vardi} [Automata, languages and programming, 8th Colloq., Acre (Akko)/Isr. 1981, Lect. Notes Comput. Sci. 115, 73--85 (1981; Zbl 0462.68022)] However, this reference does not supply the elimination claimed in Theorem 16 of our original paper. On the other hand, the arguments given in our original paper do not provide a proof -- those for Lemma 18 are vacuous. Both facts have been observed by Luc Segoufin. The purpose of this corrigendum is to provide a proof for this elimination and so for the result stated in our paper.