Lehrgebiet Informationssysteme

FB Informatik

LG IS

AG DBIS

(C) AG DBIS

Ambiguity for Referential Integrity is Undecidable

Joachim Reinert

Department of Computer Science
University of Kaiserslautern
P.O.Box 3049, 67653 Kaiserslautern, Germany
e-mail: haerder@informatik.uni-kl.de

Full paper (postscript version, compressed by gzip)

Abstract

SQL has grown to the language for relational database systems. One vital element of the relational model is referential integrity. This type of integrity constraints is now included in the new SQL2 standard with capabilities to react on violations of specified integrity constraints. These reactions may lead to indeterminism with respect to the outcome of a user operation which is also known from the usage of rules or triggers. In the database context, however, such ambiguities are undesirable. Hence, for each submitted operation one must check whether or not ambiguity occurs, and in the former case rollback the operation. Since much checks are time consuming, one might consider performing them only for schemas which bear the risk of an indeterminism. This paper shows that it is undecidable whether or not a schema may have an instance leading to ambiguities. Therefore, unnecessary checks can not be avoided in general.

Published in: Proc. 7th Int. Working Conference on Scientific and Statistical Database Management, Charlottesville, VA, Sep. 1994, IEEE Computer Society Press, pp. 207-216.