What you Always Wanted to Know About Datalog (And Never Dared to Ask).

@article{DBLP:journals/tkde/CeriGT89,
  author    = {Stefano Ceri and
               Georg Gottlob and
               Letizia Tanca},
  title     = {What you Always Wanted to Know About Datalog (And Never Dared
               to Ask)},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {1},
  number    = {1},
  year      = {1989},
  pages     = {146-166},
  ee        = {db/journals/tkde/CeriGT89.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1989 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-2 or /cdrom

• 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

...

[2]

...

[3]

Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153 BibTeX

[4]

Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX

[5]

Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX

[6]

...

[7]

Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 BibTeX

[8]

Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590 BibTeX

[9]

Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. IEEE Data Eng. Bull. 12(1): 30-36(1989) BibTeX

[10]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[11]

Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX

[12]

Krzysztof R. Apt, Howard A. Blair, Adrian Walker: Towards a Theory of Declarative Knowledge. Foundations of Deductive Databases and Logic Programming. 1988: 89-148 BibTeX

[13]

François Bancilhon: Naive Evaluation of Recursively Defined Relations. On Knowledge Base Management Systems (Islamorada) 1985: 165-178 BibTeX

[14]

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

[15]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX

[16]

François Bancilhon, Raghu Ramakrishnan: Performance Evaluation of Data Intensive Logic Programs. Foundations of Deductive Databases and Logic Programming. 1988: 439-517 BibTeX

[17]

...

[18]

François Bancilhon, Setrag Khoshafian: A Calculus for Complex Objects. PODS 1986: 53-60 BibTeX

[19]

François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105 BibTeX

[20]

...

[21]

Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur: Sets and Negation in a Logic Database Language (LDL1). PODS 1987: 21-37 BibTeX

[22]

Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX

[23]

Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40 BibTeX

[24]

...

[25]

Jorge B. Bocca: On the Evaluation Strategy of EDUCE. SIGMOD Conference 1986: 368-378 BibTeX

[26]

Michael L. Brodie: Future Intelligent Information Systems: AI and Database Technologies Working Together. AAAI 1988: 844-845 BibTeX

[27]

François Bry: Logic Programming as Constructivism: A Formalization and its Application to Databases. PODS 1989: 34-50 BibTeX

[28]

Stefano Ceri, Georg Gottlob, Luigi Lavazza: Translation and Optimization of Logic Queries: The Algebraic Approach. VLDB 1986: 395-402 BibTeX

[29]

Stefano Ceri, Letizia Tanca: Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries. VLDB 1987: 31-41 BibTeX

[30]

Stefano Ceri, Stefano Crespi-Reghizzi, Georg Gottlob, F. Lamperti, Luigi Lavazza, Letizia Tanca, Roberto Zicari: The Algres Project. EDBT 1988: 551-555 BibTeX

[31]

...

[32]

Stefano Ceri, Stefano Crespi-Reghizzi, Roberto Zicari, Gianfranco Lamperti, Luigi Lavazza: Algres: An Advanced System for Complex Applications. IEEE Software 7(4): 68-78(1990) BibTeX

[33]

Stefano Ceri, Georg Gottlob, Gio Wiederhold: Efficient Database Access from Prolog. IEEE Trans. Software Eng. 15(2): 153-164(1989) BibTeX

[34]

Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6
BibTeX

[35]

Upen S. Chakravarthy, Jack Minker, John Grant: Semantic Query Optimization: Additional Constraints and Control Strategies. Expert Database Conf. 1986: 345-379 BibTeX

[36]

Upen S. Chakravarthy, John Grant, Jack Minker: Foundations of Semantic Query Optimization for Deductive Databases. Foundations of Deductive Databases and Logic Programming. 1988: 243-273 BibTeX

[37]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[38]

Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 BibTeX

[39]

...

[40]

...

[41]

Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 BibTeX

[42]

Chin-Liang Chang, Adrian Walker: PROSQL: A Prolog Programming Interface with SQL/DS. Expert Database Workshop 1984: 233-246 BibTeX

[43]

Danette Chimenti, Anthony B. O'Hare, Ravi Krishnamurthy, Shalom Tsur, Carolyn West, Carlo Zaniolo: An Overview of the LDL System. IEEE Data Eng. Bull. 10(4): 52-62(1987) BibTeX

[44]

Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322 BibTeX

[45]

W. F. Clocksin, Chris Mellish: Programming in Prolog. Springer 1981
BibTeX

[46]

Frédéric Cuppens, Robert Demolombe: A Prolog-Relational DBMS Interface Using Delayed Evaluation. JCDKB 1988: 135-148 BibTeX

[47]

Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. ICDE 1988: 452-461 BibTeX

[48]

...

[49]

Melvin Fitting: A Kripke-Kleene Semantics for Logic Programs. J. Log. Program. 2(4): 295-312(1985) BibTeX

[50]

Kazuhiro Fuchi: Revisiting Original Philosophy of Fifth Generation Computer Systems Project. FGCS 1984: 1-2 BibTeX

[51]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX

[52]

Georges Gardarin, Christophe de Maindreville: Evaluation of Database Recursive Logic Programs as Recurrent Function Series. SIGMOD Conference 1986: 177-186 BibTeX

[53]

...

[54]

Georges Gardarin: Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs. VLDB 1987: 21-30 BibTeX

[55]

...

[56]

...

[57]

...

[58]

Antonin Guttman: New Features for Relational Database Systems to Support CAD Applications. Ph.D. thesis, University of California, Berkeley 1984
BibTeX

[59]

Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX

[60]

...

[61]

Yannis E. Ioannidis, Eugene Wong: An Algebraic Approach to Recursive Inference. Expert Database Conf. 1986: 295-309 BibTeX

[62]

Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 BibTeX

[63]

...

[64]

Yannis E. Ioannidis, Joanna Chen, Mark A. Friedman, Manolis M. Tsangaris: Bermuda - An Architectural Perspective on Interfacing Prolog to a Database Machine. Expert Database Conf. 1988: 229-255 BibTeX

[65]

Hidenori Itoh: Research and Development on Knowledge Bases Systems at ICOT. VLDB 1986: 437-445 BibTeX

[66]

Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX

[67]

...

[68]

Michael Kifer, Eliezer L. Lozinskii: Filtering Data Flow in Deductive Databases. ICDT 1986: 186-202 BibTeX

[69]

Won Kim, David S. Reiner, Don S. Batory (Eds.): Query Processing in Database Systems. Springer 1985, ISBN 3-540-13831-5
Contents BibTeX

[70]

Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 BibTeX

[71]

Phokion G. Kolaitis: The Expressive Power of Stratified Programs. Inf. Comput. 90(1): 50-66(1991) BibTeX

[72]

Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX

[73]

Ravi Krishnamurthy, Carlo Zaniolo: Optimization in a Logic Based Language for Knowledge and Data Intensive Applications. EDBT 1988: 16-33 BibTeX

[74]

Kenneth Kunen: Negation in Logic Programming. J. Log. Program. 4(4): 289-308(1987) BibTeX

[75]

Gabriel M. Kuper: Logic Programming With Sets. PODS 1987: 11-20 BibTeX

[76]

...

[77]

Erik Lambrichts, Peter Nees, Jan Paredaens, Peter Peelman, Letizia Tanca: Integration of Functions in the Fixpoint Semantics of Rule-Based Systems. MFDBS 1989: 301-316 BibTeX

[78]

John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX

[79]

...

[80]

...

[81]

Eliezer L. Lozinskii: Evaluating Queries in Deductive Databases by Generating. IJCAI 1985: 173-177 BibTeX

[82]

David Maier, David Scott Warren: Computing with Logic: Logic Programming with Prolog. Benjamin/Cummings 1988, ISBN 0-8053-6681-4
BibTeX

[83]

...

[84]

Michael V. Mannino, Paicheng Chu, Thomas Sager: Statistical Profile Estimation in Database Systems. ACM Comput. Surv. 20(3): 191-221(1988) BibTeX

[85]

...

[86]

G. Marque-Pucheu: Rational Set of Trees and the Algebraic Semantics of Logic Programming. Acta Inf. 20: 249-260(1983) BibTeX

[87]

G. Marque-Pucheu, J. Martin-Gallausiaux, Geneviève Jomier: Interfacing Prolog and Relational Data Base Management Systems. ICOD-2 Workshop on New Applications of Data Bases 1983: 225-244 BibTeX

[88]

Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 BibTeX

[89]

Katherine A. Morris, Jeffrey F. Naughton, Yatin P. Saraiya, Jeffrey D. Ullman, Allen Van Gelder: YAWN! (Yet Another Window on NAIL!). IEEE Data Eng. Bull. 10(4): 28-43(1987) BibTeX

[90]

Katherine A. Morris: An Algorithm for Ordering Subgoals in NAIL! PODS 1988: 82-88 BibTeX

[91]

...

[92]

Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX

[93]

Wolfgang Nejdl: Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy. VLDB 1987: 43-50 BibTeX

[94]

Philip A. Bernstein, Umeshwar Dayal, David J. DeWitt, Dieter Gawlick, Jim Gray, Matthias Jarke, Bruce G. Lindsay, Peter C. Lockemann, David Maier, Erich J. Neuhold, Andreas Reuter, Lawrence A. Rowe, Hans-Jörg Schek, Joachim W. Schmidt, Michael Schrefl, Michael Stonebraker: Future Directions in DBMS Research - The Laguna Beach Participants. SIGMOD Record 18(1): 17-26(1989) BibTeX

[95]

...

[96]

Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 BibTeX

[97]

...

[98]

Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102 BibTeX

[99]

Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159 BibTeX

[100]

...

[101]

J. Rohmer, R. Lescoeur, Jean-Marc Kerisit: The Alexander Method - A Technique for The Processing of Recursive Axioms in Deductive Databases. New Generation Comput. 4(3): 273-285(1986) BibTeX

[102]

Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX

[103]

Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33 BibTeX

[104]

Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 BibTeX

[105]

...

[106]

Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59 BibTeX

[106a]

Domenico Saccà, M. Dispinzeri, A. Mecchia, Clara Pizzuti, C. Del Gracco, Paolo Naggar: The Advanced Database Environment of the KIWI System. IEEE Data Eng. Bull. 10(4): 20-27(1987) BibTeX

[107]

Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX

[108]

Lothar Schmitz: An Improved Transitive Closure Algorithm. Computing 30: 359-371(1983) BibTeX

[109]

Claus-Peter Schnorr: An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comput. 7(2): 127-133(1978) BibTeX

[110]

John C. Shepherdson: Negation as Failure II. J. Log. Program. 2(3): 185-202(1985) BibTeX

[111]

John C. Shepherdson: Negation in Logic Programming. Foundations of Deductive Databases and Logic Programming. 1988: 19-88 BibTeX

[112]

Oded Shmueli, Shamim A. Naqvi: Set Grouping and Layering in Horn Clause Programs. ICLP 1987: 152-177 BibTeX

[113]

...

[114]

David E. Smith, Michael R. Genesereth, Matthew L. Ginsberg: Controlling Recursive Inference. Artif. Intell. 30(3): 343-389(1986) BibTeX

[115]

Leon Sterling, Ehud Y. Shapiro: The Art of Prolog - Advanced Programming Techniques. MIT Press 1986, ISBN 0-262-19250-0
BibTeX

[116]

Mark E. Stickel: A Unification Algorithm for Associative-Commutative Functions. J. ACM 28(3): 423-434(1981) BibTeX

[117]

...

[118]

...

[119]

Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41 BibTeX

[120]

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

[121]

...

[122]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[123]

Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX

[124]

Patrick Valduriez, Setrag Khoshafian: Parallel Evaluation of the Transitive Closure of a Database Relation. International Journal of Parallel Programming 17(1): 19-37(1988) BibTeX

[125]

Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX

[126]

Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: Unfounded Sets and Well-Founded Semantics for General Logic Programs. PODS 1988: 221-230 BibTeX

[127]

Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX

[128]

Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX

[129]

Laurent Vieille: A Database-Complete Proof Procedure Based on SLD-Resolution. ICLP 1987: 74-103 BibTeX

[130]

Laurent Vieille: From QSQ towards QoSaQ: Global Optimization of Recursive Queries. Expert Database Conf. 1988: 743-778 BibTeX

[131]

Henry S. Warren Jr.: A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations. Commun. ACM 18(4): 218-220(1975) BibTeX

[132]

Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) BibTeX

[133]

Carlo Zaniolo: The Representation and Deductive Retrieval of Complex Objects. VLDB 1985: 458-469 BibTeX

[134]

...

[135]

Carlo Zaniolo, Domenico Saccà: Rule Rewriting Methods in the Implementation of the Logic Language LDL. DS-3 1988: 457-483 BibTeX

[136]

...

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. Johann Eder: View Definitions with Parameters. ADBIS 1995: 170-184
4. Yannis E. Ioannidis, Manolis M. Tsangaris: The Design, Implementation, and Performance Evaluation of BERMUDA. IEEE Trans. Knowl. Data Eng. 6(1): 38-56(1994)
5. Martin F. van Bommel, Grant E. Weddell: Reasoning About Equations and Functional Dependencies on Complex Objects. IEEE Trans. Knowl. Data Eng. 6(3): 455-469(1994)
6. Rainer Manthey: Active and Passive Rules in Database Systems: How Do They Relate? (Invited Paper). ADBIS 1994: 104-115
7. Francesco Bergadano: Inductive Database Relations. IEEE Trans. Knowl. Data Eng. 5(6): 969-972(1993)
8. James B. Behm, Toby J. Teorey: Relative Constraints in ER Data Models. ER 1993: 46-59
9. Laks V. S. Lakshmanan, Rokia Missaoui: On Semantic Query Optimization in Deductive Databases. ICDE 1992: 368-375
10. Steve Taylor, Nabil I. Hachem: A Direct Algorithm for Computing the Transitive Closure of a Two-Dimensionally Structured File. MFDBS 1991: 146-159