Can Datalog be Approximated?

Surajit Chaudhuri, Phokion G. Kolaitis: Can Datalog be Approximated? PODS 1994: 86-96

@inproceedings{DBLP:conf/pods/ChaudhuriK94,
  author    = {Surajit Chaudhuri and
               Phokion G. Kolaitis},
  title     = {Can Datalog be Approximated?},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {86-96},
  ee        = {http://doi.acm.org/10.1145/182591.182602, db/conf/pods/pods94-86.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we investigate whether recursive Datalog predicates can be approximated by finite unions of conjunctive queries. We introduce a quantitative notion of error and examine two types of approximation, namely, absolute approximation and relative approximation. We also stipulate that the approximations obey certain qualitative criteria, namely we require them to be upper envelopes or lower envelopes of the Datalog predicate they approximate. We establish that absolute approximation by finite unions of conjunctive queries is not possible, which means that no unbounded Datalog predicate can be approximated by a finite union of conjunctive queries in such a way that the error is bounded uniformly by the same constant on all finite databases. After this, we examine relative approximations, i.e., approximations that guarantee bounds for the error relative to the size of the Datalog predicate under consideration. Although such approximations exist in some cases, we show that for several large and well-studied classes of unbounded Datalog predicates it is not possible to find finite unions of conjunctive queries that satisfy the aforementioned qualitatitative criteria and have the property that the relative error of the approximation is bounded by a constant. Finally, we consider first-order approximations and obtain sharp negative results for the approximability of the transitive closure query and the cycle query by first-order queries.

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1244 KB]

Journal Edition

Surajit Chaudhuri, Phokion G. Kolaitis: Can Datalog Be Approximated? J. Comput. Syst. Sci. 55(2): 355-369(1997)

References

[AP87]: Foto N. Afrati, Christos H. Papadimitriou: The Parallel Complexity of Simple Chain Queries. PODS 1987: 210-213
[AG89]: Miklós Ajtai, Yuri Gurevich: Datalog vs. First-Order Logic. FOCS 1989: 142-147
[AU79]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
[Co74]: Stephen A. Cook: An Observation on Time-Storage Trade Off. J. Comput. Syst. Sci. 9(3): 308-316(1974)
[CGKV88]: Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi: Decidable Optimization Problems for Database Logic Programs (Preliminary Report). STOC 1988: 477-490
[CM77]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90
[C93]: Surajit Chaudhuri: Finding Nonrecursive Envelopes for Datalog Predicates. PODS 1993: 135-146
[Fa75]: ...
[FSV93]: ...
[GMSV87]: Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115
[GJ79]: 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
[Io86]: Yannis E. Ioannidis: A Time Bound on the Materialization of Some Recursively Defined Views. Algorithmica 1(3): 361-385(1986)
[KA89]: Paris C. Kanellakis, Serge Abiteboul: Database Theory Column: Deciding Bounded Recursion in Database Logic Programs. SIGACT News 20(4): 17-23(1989)
[KV90]: Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. PODS 1990: 61-71
[MUV84]: David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984)
[Na89]: Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. J. Comput. Syst. Sci. 38(2): 259-289(1989)
[PS82]: Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall 1982, ISBN 0-13-152462-3
[SY81]: Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980)
[U89]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
[Va82]: Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146