dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

On the Complexity and Axiomatizability of Consistent Database States.

Marc H. Graham, Moshe Y. Vardi: On the Complexity and Axiomatizability of Consistent Database States. PODS 1984: 281-289
@inproceedings{DBLP:conf/pods/GrahamV84,
  author    = {Marc H. Graham and
               Moshe Y. Vardi},
  editor    = {Daniel J. Rosenkrantz and
               Ronald Fagin},
  title     = {On the Complexity and Axiomatizability of Consistent Database
               States},
  booktitle = {Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada},
  publisher = {ACM},
  year      = {1984},
  isbn      = {0-89791-128-8},
  pages     = {281-289},
  ee        = {http://doi.acm.org/10.1145/588011.588052, db/conf/pods/GrahamV84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A database is consistent with respect to a set Sigma of dependencies if it has a weak instance. A weak instance is a universal relation that satisfies Sigma, and whose projections on the relation schemes are supersets of the relations in the database. In this paper we investigate the complexity of testing consistency and the logics that can axiomatize consistency, relative to a fixed set Sigma of dependencies. If Sigma is allowed to include embedded dependencies, then consistency can be non-recursive. If Sigma consists only of total dependencies, then consistency can be tested in polynomial time. The degree of the polynomial can, however, be arbitrarily high. Consistency can be axiomatized but not finitely axiomatized by equality generating dependencies. If embedded dependencies are allowed then consistency cannot be finitely axiomatized by any effective logic. If, on the other hand, only total dependencies are allowed then consistency can be finitely axiomatized by fixpoint logic.

Copyright © 1984 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 ...

Printed Edition

Daniel J. Rosenkrantz, Ronald Fagin (Eds.): Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada. ACM 1984, ISBN 0-89791-128-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

References

[AN]
...
[AU]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BV1]
...
[BV2]
...
[C1]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[C2]
...
[C3]
...
[CH]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cha]
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CK]
...
[DST]
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fa1]
...
[Fa2]
Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fe]
...
[Gu]
...
[GMV]
...
[Ha]
...
[Ho]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Im]
Neil Immerman: Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982: 147-152 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JL]
Neil D. Jones, William T. Laaser: Complete Problems for Deterministic Polynomial Time. Theor. Comput. Sci. 3(1): 105-117(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[McKi]
...
[MSY]
David Maier, Yehoshua Sagiv, Mihalis Yannakakis: On the Complexity of Testing Implications of Functional and Join Dependencies. J. ACM 28(4): 680-695(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MZ]
...
[MUV]
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: The Revenge of the JD. PODS 1983: 279-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sa]
Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Var1]
Moshe Y. Vardi: Global Decision Problems for Relational Databases. FOCS 1981: 198-202 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Var2]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Y]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Free | Complete | Author
Last update Fri Sep 14 17:28:24 2012 CET by the DBLP Team — This material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page