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

Optimizing Datalog Programs.

Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362
@inproceedings{DBLP:conf/pods/Sagiv87,
  author    = {Yehoshua Sagiv},
  title     = {Optimizing Datalog Programs},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {349-362},
  ee        = {http://doi.acm.org/10.1145/28659.28696, db/conf/pods/Sagiv87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Datalog programs, i e, Prolog programs without function symbols, are considered. It is assumed that a variable appearing in the head of a rule must also appear in the body of the rule. The input of a program is a set of ground atoms (which are given in addition to the program's rules) and, therefore, can be viewed as an assignment of relations to some of the program's predicates. Two programs are equivalent if they produce the same result for all possible assignments of relations to the extensional predicates (i e, the predicates that do not appear as heads of rules). Two programs are uniformly equivalent if they produce the same result for all possible assignments of initial relations to all the predicates (i e , both extensional and intentional). The equivalence problem for Datalog programs is known to be undecidable. It is shown that uniform equivalence is decidable, and an algorithm is given for minimizing a Datalog program under uniform equivalence. A technique for removing parts of a program that are redundant under equivalence (but not under uniform equivalence) is developed. A procedure for testing uniform equivalence is also developed for the case in which the database satisfies some constraints.

Copyright © 1987 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 Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

References

[Aho, Sagiv, Ullman 1979]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[Apt, Blair, Walker 1986]
...
[Bancilhon, Maier, Sagiv, Ullman 1986a]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[Bancilhan, Ramakrishnan 1986b]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[Beeri, Vardi 1984]
Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 31(4): 718-741(1984) BibTeX
[Chakravarthy, Minker, Grant 1986]
Upen S. Chakravarthy, Jack Minker, John Grant: Semantic Query Optimization: Additional Constraints and Control Strategies. Expert Database Conf. 1986: 345-379 BibTeX
[Chandra, Merlin 1976]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[Cosmadakis, Kanellakis 1986]
Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX
[Fagin 1982]
Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) BibTeX
[Finger 1986]
...
[Gaifman 1986]
...
[Gallaire, Minker 1978]
...
[Henschern, Naqvi 1984]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[Kifer, Lozinskii 1986]
Michael Kifer, Eliezer L. Lozinskii: Filtering Data Flow in Deductive Databases. ICDT 1986: 186-202 BibTeX
[King 1981]
...
[Klug, Price 1982]
Anthony C. Klug, Rod Price: Determining View Dependencies Using Tableaux. ACM Trans. Database Syst. 7(3): 361-380(1982) BibTeX
[Lozinskii 1986]
Eliezer L. Lozinskii: A Problem-Oriented Inferential Database System. ACM Trans. Database Syst. 11(3): 323-356(1986) BibTeX
[Maher 1986]
Michael J. Maher: Eqivalences of Logic Programs. ICLP 1986: 410-424 BibTeX
[Maier, Mendelzon, Sagiv 1979]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[McKay, Shapiro 1981]
...
[Naqvi 1986]
...
[Naughton 1986]
Jeffrey F. Naughton: Redundancy in Function-Free Recursive Rules. SLP 1986: 236-245 BibTeX
[Rohmer, Lescoeur 1985]
...
[Saccà, Zaniolo 1986]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX
[Sagiv, Yannakakis 1980]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX
[Shmueli 1986]
...
[Ullman 1985]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[Van Emden, Kowalski 1976]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX
[Van Gelder 1986a]
Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165 BibTeX
[Van Gelder 1986b]
Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX
[Yannakakis, Papadimitriou 1982]
Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41(1982) BibTeX

Referenced by

  1. Danilo Montesi, Elisa Bertino, Maurizio Martelli: Transactions and Updates in Deductive Databases. IEEE Trans. Knowl. Data Eng. 9(5): 784-797(1997)
  2. Laks V. S. Lakshmanan, Rokia Missaoui: Pushing Semantics Inside Recursion: A General Framework for Semantic Optimization of Recursive Queries. ICDE 1995: 211-220
  3. Keh-Chang Guh, Clement T. Yu: Efficient Query Processing for a Subset of Linear Recursive Binary Rules. IEEE Trans. Knowl. Data Eng. 6(5): 842-849(1994)
  4. Keh-Chang Guh, Clement T. Yu: Efficient Management of Materialized Generalized Transitive Closure in Centralized and Parallel Environments. IEEE Trans. Knowl. Data Eng. 4(4): 371-381(1992)
  5. Tomás Feder, Yatin P. Saraiya: Decidability and Undecidability of Equivalence for Linear Datalog with Applications to Normal-Form Optimizations. ICDT 1992: 297-311
  6. Laks V. S. Lakshmanan, Rokia Missaoui: On Semantic Query Optimization in Deductive Databases. ICDE 1992: 368-375
  7. Surajit Chaudhuri: Detecting Redundant Tuples During Query Evaluation. PODS 1991: 115-126
  8. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  9. Weining Zhang, Clement T. Yu, Daniel Troy: Necessary and Sufficient Conditions to Linearize Double Recursive Programs in Logic Databases. ACM Trans. Database Syst. 15(3): 459-482(1990)
  10. Michael Kifer, Eliezer L. Lozinskii: On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering. ACM Trans. Database Syst. 15(3): 385-426(1990)
  11. Yatin P. Saraiya: Hard Problems for Simple Logic Programs. SIGMOD Conference 1990: 64-73
  12. Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
  13. Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229
  14. Ron van der Meyden: Recursively Indefinite Databases. ICDT 1990: 364-378
  15. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  16. Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182
  17. Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35
  18. Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189
  19. Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989: 172-181
  20. Simona Rabinovici-Cohen, Ouri Wolfson: Why a Single Parallelization Strategy in not Enough in Knowledge Bases. PODS 1989: 200-216
  21. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  22. Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153
  23. Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
  24. Guozhu Dong: On the Composition and Decomposition of Datalog Program Mappings. ICDT 1988: 87-101
  25. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
  26. Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81
  27. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10
  28. Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249
  29. Jeffrey F. Naughton, Yehoshua Sagiv: A Decidable Class of Bounded Recursions. PODS 1987: 227-236
  30. Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348
  31. Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226
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:52 2009