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
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
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Marc Gyssens:
Embedded Join Dependencies as a Tool for Decomposing Full Join Dependencies.
PODS 1985: 205-214
- 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