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

Querying Logical Databases.

Moshe Y. Vardi: Querying Logical Databases. PODS 1985: 57-65
@inproceedings{DBLP:conf/pods/Vardi85,
  author    = {Moshe Y. Vardi},
  title     = {Querying Logical Databases},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {57-65},
  ee        = {http://doi.acm.org/10.1145/325405.325413, db/conf/pods/Vardi85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We study here the complexity of evaluating queries in logical databases. We focus on Reiter's model of closed-world databases with unknown values. We show that in this setting query evaluation is harder than query evaluation for physical databases. For example, while 1st-order queries over physical databases can be evaluated in logarithmic space, evaluation of 1st-order queries in the studied model is co-NP-complete. We describe an approximation algorithm for query evaluation that enables one to implement a logical databases on the top of a standard database management system.

Copyright © 1985 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 Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 25-27, 1985, Portland, Oregon. ACM 1985, ISBN 0-89791-153-9
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Moshe Y. Vardi: Querying Logical Databases. J. Comput. Syst. Sci. 33(2): 142-160(1986) BibTeX

References

[Bi81]
...
[CH80]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[CM77]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[Co70]
...
[Fa82]
...
[FUV83]
Ronald Fagin, Jeffrey D. Ullman, Moshe Y. Vardi: On the Semantics of Updates in Databases. PODS 1983: 352-365 BibTeX
[GK79]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[GM78]
...
[Gr77]
John Grant: Null Values in a Relational Data Base. Inf. Process. Lett. 6(5): 156-157(1977) BibTeX
[Im84]
...
[Ko81]
...
[Ku67]
...
[Ku70]
...
[NG78]
...
[Re80]
Raymond Reiter: A Logic for Default Reasoning. Artif. Intell. 13(1-2): 81-132(1980) BibTeX
[Re83]
...
[Re84]
...
[St77]
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
[Tr50]
...
[Va82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[Za82]
Carlo Zaniolo: Database Relations with Null Values. PODS 1982: 27-33 BibTeX

Referenced by

  1. Laks V. S. Lakshmanan, Nicola Leone, Robert B. Ross, V. S. Subrahmanian: ProbView: A Flexible Probabilistic Database System. ACM Trans. Database Syst. 22(3): 419-469(1997)
  2. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  3. Li-Yan Yuan, Ding-An Chiang: A Sound and Complete Query Evaluation Algorithm for Relational Databases with Disjunctive Information. PODS 1989: 66-74
  4. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  5. Li-Yan Yuan, Ding-An Chiang: A Sound and Complete Query Evaluation Algorithm for Relational Databases with Null Values. SIGMOD Conference 1988: 74-81
  6. Serge Abiteboul: Updates, A New Frontier. ICDT 1988: 1-18
  7. Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. SIGMOD Conference 1987: 34-48
  8. Marianne Winslett: A Model-Theoretic Approach to Updating Logical Databases. PODS 1986: 224-234
  9. Moshe Y. Vardi: On the Integrity of Databases with Incomplete Information. PODS 1986: 252-266
  10. Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12
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:46 2009