The inference problem for template dependencies
Yuri G. Gurevich, Harry R. Lewis · 1982
A template dependency is a formalized integrity constraint on a relational database, stating that whenever tuples exist in the database that agree on certain attributes, an additional tuple must also be present that agrees with the others in a specified way. It is shown that the inference problem for template dependencies is undecidable, that is, there can be no algorithm for determining whether a given dependency is a logical consequence of a given finite set of dependencies. The undecidability result holds whether or not databases are considered to be necessarily finite. INTROD UCTION The goal of dependency theory is to formalize constraints on the data comprising a relational database. In general, a dependency is a statement to the effect that when certain tuples are present in the database, so are certain others. Such statements can be used, for example, to capture the idea that attributes are functionally related or independent in some way. Many varieties of dependencies have been proposed in the literature; see the discussions in Fagin (1980) and Yannakakis and Papadimitriou (1980), for example. The proliferation of varieties is due in part to the desire to balance two opposing forces: on the one hand, dependencies should be of a form general enough to express interesting properties, but on the other hand, the form should not be so general that natural questions about dependencies become undecidable or computationally intractable. A significant question about any class of dependencies is its inference problem: Given a finite set D of dependencies and a single dependency D 0, to determine whether D O is true in every database in which each member of D is true. A solution to the inference problem carries with it the ability to determine whether two sets of