ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

The Inference Problem for Template Dependencies.

Yuri Gurevich, Harry R. Lewis: The Inference Problem for Template Dependencies. PODS 1982: 221-229
@inproceedings{DBLP:conf/pods/GurevichL82,
  author    = {Yuri Gurevich and
               Harry R. Lewis},
  title     = {The Inference Problem for Template Dependencies},
  booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
               March 29-31, 1982, Los Angeles, California},
  publisher = {ACM},
  year      = {1982},
  pages     = {221-229},
  ee        = {http://doi.acm.org/10.1145/588111.588148, db/conf/pods/GurevichL82.html},
  crossref  = {DBLP:conf/pods/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

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 here 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.

Copyright © 1982 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California. ACM 1982
Contents BibTeX

Online Edition: ACM Digital Library


References

[CLM]
Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. STOC 1981: 342-354 BibTeX
[G]
...
[GL]
...
[F]
Ronald Fagin: Horn Clauses and Database Dependencies (Extended Abstract). STOC 1980: 123-134 BibTeX
[FMUY]
Ronald Fagin, David Maier, Jeffrey D. Ullman, Mihalis Yannakakis: Tools for Template Dependencies. SIAM J. Comput. 12(1): 36-59(1983) BibTeX
[P]
...
[SU]
Fereidoon Sadri, Jeffrey D. Ullman: A Complete Axiomatization for a Large Class of Dependencies in Relational Databases. STOC 1980: 117-122 BibTeX
[T]
...
[V]
Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. PODS 1982: 230-238 BibTeX
[YP]
Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies (Extended Abstract). FOCS 1980: 328-332 BibTeX

Referenced by

  1. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  2. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  3. Marc Gyssens: Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies. PODS 1985: 205-214
  4. Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. PODS 1982: 230-238
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:40 2009