Corrigendum to ``On the undecidability of implications between embedded multivalued database dependencies''
type: Item
instance of: scholarly article
title: Corrigendum to ``On the undecidability of implications between embedded multivalued database dependencies''
zbMATH Open document ID: 1171.68449
published in: Information and Computation
publication date: 2007-01-22T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 5117649
author: Christian Herrmann
MaRDI profile type: Publication
full work available at URL: j.ic.2006.09.002
OpenAlex ID: W2084831953
cites work: Q3912018
cites work: A Proof Procedure for Data Dependencies
cites work: On the undecidability of implications between embedded multivalued database dependencies
DOI: 10.1016/J.IC.2006.09.002
description: scientific article; zbMATH DE number 5117649