ACM SIGMOD Anthology TODS dblp.uni-trier.de

Implementation of Logical Query Languages for Databases.

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985)
@article{DBLP:journals/tods/Ullman85,
  author    = {Jeffrey D. Ullman},
  title     = {Implementation of Logical Query Languages for Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {3},
  year      = {1985},
  pages     = {289-321},
  ee        = {http://doi.acm.org/10.1145/3979.3980, db/journals/tods/Ullman85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We examine methods of implementing queries about relational databases in the case where these queries are expressed in first-order logic as a collection of Horn clauses. Because queries may be defined recursively, straightforward methods of query evaluation do not always work, and a variety of strategies have been proposed to handle subsets of recursive queries. We express such query evaluation techniques as "capture rules" on a graph representing clauses and predicates. One essential property of capture rules is that they can be applied independently, thus providing a clean interface for query-evaluation systems that use several different strategies in different situations. Another is that there be an efficient test for the applicability of a given rule. We define basic capture rules corresponding to application of operators from relational algebra, a top-down capture rule corresponding to "backward chaining," that is, repeated resolution of goals, a bottom-up rule, corresponding to "forward chaining," where we attempt to deduce all true facts in a given class, and a "sideways" rule that allows us to pass results from one goal to another.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Conference Abstract

Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases (Abstract). SIGMOD Conference 1985: 444 BibTeX

References

[1]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[2]
Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163 BibTeX
[3]
Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 BibTeX
[4]
Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322 BibTeX
[5]
...
[6]
...
[7]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[8]
Robert A. Kowalski: A Proof Procedure Using Connection Graphs. J. ACM 22(4): 572-595(1975) BibTeX
[9]
...
[10]
...
[11]
...
[12]
...
[13]
Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76 BibTeX
[14]
Raymond Reiter: Deductive Question-Answering on Relational Data Bases. Logic and Data Bases 1977: 149-177 BibTeX
[15]
...
[16]
...
[17]
...
[18]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX
[19]
Stephen Taylor, Andy Lowry, Gerald Q. Maguire Jr., Salvatore J. Stolfo: Logic Programming Using Parallel Associative Operations. SLP 1984: 58-68 BibTeX
[20]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[21]
...
[22]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX

Referenced by

  1. David B. Kemp, Thomas Conway, Evan P. Harris, Fergus Henderson, Kotagiri Ramamohanarao, Zoltan Somogyi: Database Transactions in a Purely Declarative Logic Programming Language. DASFAA 1997: 283-292
  2. Louiqa Raschid, Jorge Lobo: Semantics for Update Rule Programs and Implementations in a Relational Database Management System. ACM Trans. Database Syst. 21(4): 526-571(1996)
  3. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. ACM Trans. Database Syst. 21(1): 107-155(1996)
  4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  5. Jayen Vaghani, Kotagiri Ramamohanarao, David B. Kemp, Zoltan Somogyi, Peter J. Stuckey, Tim S. Leask, James Harland: The Aditi Deductive Database System. VLDB J. 3(2): 245-288(1994)
  6. Werner Kießling, Helmut Schmidt, Werner Strauß, Gerhard Dünzinger: DECLARE and SDS: Early Efforts to Commercialize Deductive Database Technology. VLDB J. 3(2): 211-243(1994)
  7. Wenyu Lu, Dik Lun Lee, Jiawei Han: A Study on the Structure of Linear Recursion. IEEE Trans. Knowl. Data Eng. 6(5): 723-737(1994)
  8. 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)
  9. Konstantinos F. Sagonas, Terrance Swift, David Scott Warren: XSB as an Efficient Deductive Database Engine. SIGMOD Conference 1994: 442-453
  10. Kirack Sohn: Constraints among Argument Sizes in Logic Programs. PODS 1994: 68-74
  11. Gabriel M. Kuper, Moshe Y. Vardi: The Logical Data Model. ACM Trans. Database Syst. 18(3): 379-413(1993)
  12. Rafiul Ahad, Bing Yao: RQL: A Recursive Query Language. IEEE Trans. Knowl. Data Eng. 5(3): 451-461(1993)
  13. Michael Stonebraker: The Integration of Rule Systems and Database Systems. IEEE Trans. Knowl. Data Eng. 4(5): 415-423(1992)
  14. 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)
  15. Stefano Ceri: A Declarative Approach to Active Databases. ICDE 1992: 452-456
  16. Guido Moerkotte, Peter C. Lockemann: Reactive Consistency Control In Deductive Databases. ACM Trans. Database Syst. 16(4): 670-702(1991)
  17. Alberto O. Mendelzon, Peter T. Wood: Functional Dependencies in Horn Clause Queries. ACM Trans. Database Syst. 16(1): 31-55(1991)
  18. Guy M. Lohman, Bruce G. Lindsay, Hamid Pirahesh, K. Bernhard Schiefer: Extensions to Starburst: Objects, Types, Functions, and Rules. Commun. ACM 34(10): 94-109(1991)
  19. Kirack Sohn, Allen Van Gelder: Termination Detection in Logic Programs using Argument Sizes. PODS 1991: 216-226
  20. Jayen Vaghani, Kotagiri Ramamohanarao, David B. Kemp, Zoltan Somogyi, Peter J. Stuckey: Design Overview of the Aditi Deductive Database System. ICDE 1991: 240-247
  21. Ken-Chih Liu, Lu Zhang: Natural Joins in Relational Databases with Indefinite and Maybe Information. ICDE 1991: 132-139
  22. Sang-goo Lee, Lawrence J. Henschen, Ghassan Z. Qadah: Semantic Query Reformulation in Deductive Databases. ICDE 1991: 232-239
  23. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  24. Kotagiri Ramamohanarao: The Aditi Deductive Database System (Extented Abstract). DASFAA 1991: 201-208
  25. Sang Ho Lee, Lawrence J. Henschen: Evaluation of Extended Recursive Queries in Deductive Databases. DASFAA 1991: 209-215
  26. 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)
  27. 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)
  28. Michael Stonebraker, Lawrence A. Rowe, Michael Hirohama: The Implementation of Postgres. IEEE Trans. Knowl. Data Eng. 2(1): 125-142(1990)
  29. Michael V. Mannino, Leonard D. Shapiro: Extensions to Query Languages for Graph Traversal Problems. IEEE Trans. Knowl. Data Eng. 2(3): 353-363(1990)
  30. Peter T. Wood: Factoring Augmented Regular Chain Programs. VLDB 1990: 255-263
  31. Juhani Kuittinen, Otto Nurmi, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries. VLDB 1990: 372-379
  32. Thane E. Plambeck: Semigroup Techniques in Recursive Query Optimization. PODS 1990: 145-153
  33. Allen Van Gelder: Deriving Constraints Among Argument Sizes in Logic Programs. PODS 1990: 47-60
  34. Seppo Sippu, Eljas Soisalon-Soininen: Multiple SIP Strategies and Bottom-Up Adorning in Logic Query Optimization. ICDT 1990: 485-498
  35. A. M. Alashqur, Stanley Y. W. Su, Herman Lam: A Rule-based Language for Deductive Object-Oriented Databases. ICDE 1990: 58-67
  36. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Abstract Machine for LDL. EDBT 1990: 153-168
  37. 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)
  38. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Towards on Open Architecture for LDL. VLDB 1989: 195-203
  39. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
  40. Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
  41. Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149
  42. Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189
  43. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
  44. Stavros S. Cosmadakis: On the First-Order Expressibility of Recursive Queries. PODS 1989: 311-323
  45. Alexander Tuzhilin, Zvi M. Kedem: Querying and Controlling the Future Behaviour of Complex Objects. ICDE 1989: 434-442
  46. Kyung-Chang Kim, Won Kim, Alfred G. Dale: Cyclic Query Processing in Object-Oriented Databases. ICDE 1989: 564-571
  47. Jean-Pierre Cheiney, Christophe de Maindreville: Relational Storage and Efficient Retrieval of Rules in a Deductive DBMS. ICDE 1989: 644-651
  48. Runping Qi, Wolfgang Bibel: A Framework for the Parallel Evaluation of Recursive Queries in Deductive Databases. DASFAA 1989: 301-309
  49. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  50. Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988)
  51. Christophe de Maindreville, Eric Simon: Modelling Non Deterministic Queries and Updates in Deductive Databases. VLDB 1988: 395-406
  52. Eliezer L. Lozinskii: Computing Facts in Non-Horn Deductive Systems. VLDB 1988: 273-279
  53. Cheong Youn, Lawrence J. Henschen, Jiawei Han: Classification of Recursive Formulas in Deductive Databases. SIGMOD Conference 1988: 320-328
  54. Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
  55. Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163
  56. Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351
  57. Jeffrey D. Ullman, Moshe Y. Vardi: The Complexity of Ordering Subgoals. PODS 1988: 74-81
  58. Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332
  59. Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102
  60. Shamim A. Naqvi, Ravi Krishnamurthy: Database Updates in Logic Programming. PODS 1988: 251-262
  61. Katherine A. Morris: An Algorithm for Ordering Subgoals in NAIL! PODS 1988: 82-88
  62. Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60
  63. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
  64. Kyu-Young Whang, Stephen Brady: A Framework for Optimization in Expert System - DBMS Interface. ICDE 1988: 126-133
  65. Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477
  66. Ravi Krishnamurthy, Carlo Zaniolo: Optimization in a Logic Based Language for Knowledge and Data Intensive Applications. EDBT 1988: 16-33
  67. Jiawei Han, Ghassan Z. Qadah, Chinying Chaou: The Processing and Evaluation of Transitive Closure Queries. EDBT 1988: 49-75
  68. Stefano Ceri, Stefano Crespi-Reghizzi, Georg Gottlob, F. Lamperti, Luigi Lavazza, Letizia Tanca, Roberto Zicari: The Algres Project. EDBT 1988: 551-555
  69. Kyu-Young Whang, Shamkant B. Navathe: An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments. VLDB 1987: 275-287
  70. Wolfgang Nejdl: Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy. VLDB 1987: 43-50
  71. Georges Gardarin: Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs. VLDB 1987: 21-30
  72. Stefano Ceri, Letizia Tanca: Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries. VLDB 1987: 31-41
  73. Weining Zhang, Clement T. Yu: A Necessary Condition for a Doubly Recursive Rule to be Equivalent to a Linear Recursive Rule. SIGMOD Conference 1987: 345-356
  74. Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59
  75. Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81
  76. Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987: 323-330
  77. Hussien Aly, Z. Meral Özsoyoglu: Non-deterministic Modelling of Logical Queries in Deductive Databases. SIGMOD Conference 1987: 60-72
  78. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10
  79. Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249
  80. Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362
  81. Alberto Marchetti-Spaccamela, Antonella Pelaggi, Domenico Saccà: Worst-case Complexity Analysis of Methods for Logic Query Implementation. PODS 1987: 294-301
  82. Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
  83. Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur: Sets and Negation in a Logic Database Language (LDL1). PODS 1987: 21-37
  84. Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226
  85. Clement T. Yu, Weining Zhang: Efficient Recursive Query Processing using Wavefront Methods. ICDE 1987: 652-657
  86. Michael Stonebraker, Eric N. Hanson, Chin-Heng Hong: The Design of the Postgres Rules System. ICDE 1987: 365-374
  87. Volker Linnemann: Non First Normal Form Relations and Recursive Queries: An SQL-Based Approach. ICDE 1987: 591-598
  88. Michael Kifer, Eliezer L. Lozinskii: Implementing Logic Programs as a Database System. ICDE 1987: 375-385
  89. Ulrich Güntzer, Werner Kießling, Rudolf Bayer: On the Evaluation of Recursion in (Deductive) Database Systems by Efficient Differential Fixpoint Iteration. ICDE 1987: 120-129
  90. Shamim A. Naqvi, Ravi Krishnamurthy: Semantics of Updates in Logic Programming. DBPL 1987: 313-327
  91. Ravi Krishnamurthy, Carlo Zaniolo: Control and Optimization Strategies in the Implementation of LDL. DBPL 1987: 329-345
  92. Eliezer L. Lozinskii: A Problem-Oriented Inferential Database System. ACM Trans. Database Syst. 11(3): 323-356(1986)
  93. Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41
  94. Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137
  95. Charles Kellogg, Anthony B. O'Hare, Larry Travis: Optimizing the Rule-Data Interface in a KMS. VLDB 1986: 42-51
  96. Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411
  97. Stefano Ceri, Georg Gottlob, Luigi Lavazza: Translation and Optimization of Logic Queries: The Algebraic Approach. VLDB 1986: 395-402
  98. Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176
  99. François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52
  100. Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23
  101. Jeffrey F. Naughton: Data Independent Recursion in Deductive Databases. PODS 1986: 267-279
  102. François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15
  103. Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53
  104. Paris C. Kanellakis: Logic Programming and Parallel Complexity. ICDT 1986: 1-30
  105. Haruo Yokota, Sko Sakai, Hidenori Itoh: Deductive Database System based on Unit Resolution. ICDE 1986: 228-235
  106. Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:57 2008