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

An Amateur's Introduction to Recursive Query Processing Strategies.

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52
@inproceedings{DBLP:conf/sigmod/BancilhonR86,
  author    = {Fran\c{c}ois Bancilhon and
               Raghu Ramakrishnan},
  editor    = {Carlo Zaniolo},
  title     = {An Amateur's Introduction to Recursive Query Processing Strategies},
  booktitle = {Proceedings of the 1986 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 28-30, 1986},
  publisher = {ACM Press},
  year      = {1986},
  pages     = {16-52},
  ee        = {http://doi.acm.org/10.1145/16894.16859, db/conf/sigmod/BancilhonR86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper surveys and compares various strategies for processing logic queries in relational databases. The survey and comparison is limited to the case of Horn Clauses with evaluable predicates but without function symbols. The paper is organized in three parts. In the first part, we introduce the main concepts and definitions. In the second, we describe the various strategies. For each strategy, we give its main characteristics, its application range and a detailed description. We also give an example of a query evaluation. The third part of the paper compares the strategies on performance grounds. We first present a set of sample rules and queries which are used for the performance comparisons, and then we characterize the data. Finally, we give an analytical solution for each query/rule system. Cost curves are plotted for specific configurations of the data.

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


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Carlo Zaniolo (Ed.): Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. ACM Press 1986 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 15(2)
Contents

Online Edition: ACM Digital Library


References

[Afrati et al. 86]
Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman: Convergence of Sideways Query Evaluation. PODS 1986: 24-30 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Aho and Ullman 79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Apt and Van Emden 82]
Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bancilhon 85]
...
[Bancilhon 85a]
...
[Bancilhon et al. 86]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bancilhon et al. 86a]
...
[Bancilhon and Ramakrishnan 86]
...
[Bayer 85]
...
[Chang 81]
Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dayal et al. 85]
...
[Delobel 86]
...
[Dietrich and Warren 85]
...
[Gallaire et al. 84]
...
[Gardarin and Maindreville 85]
Georges Gardarin, Christophe de Maindreville: Evaluation of Database Recursive Logic Programs as Recurrent Function Series. SIGMOD Conference 1986: 177-186 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Han and Lu 86]
Jiawei Han, Hongjun Lu: Some Performance Results on Recursive Query Processing in Relational Database Systems. ICDE 1986: 533-541 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Henschen and Naqvi 84]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kifer and Lozinskii 85]
...
[Laskowski 84]
...
[Lozinskii 83]
...
[Lozinskii 85]
...
[Lozinskii 85a]
...
[Marque-Pucheu 83]
...
[Marque-Pucheu et al. 84]
...
[McKay and Shapiro 81]
...
[Morris et al. 86]
Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Naqvi and Fishman 81]
...
[Naqvi and Henschen 83]
...
[Reiter 78]
...
[Rohmer and Lescoeur 85]
...
[Rosenthal et al. 85]
...
[Sacca and Zaniolo 86a]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sacca and Zaniolo 86b]
...
[Sagiv and Ullman 84]
...
[Shapiro and McKay 80]
Stuart C. Shapiro, Donald P. McKay: Inference with Recursive Rules. AAAI 1980: 151-153 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shapiro at al. 82]
...
[Tarski 55]
...
[Ullman 85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ullman and Van Gelder 85]
...
[Van Emden and Kowalski 76]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Valduriez and Boral 86]
Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Vieille 85]
...
[Vieille 86]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Zaniolo 85]
Carlo Zaniolo: The Representation and Deductive Retrieval of Complex Objects. VLDB 1985: 458-469 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Zaniolo 86]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Reda Alhajj: A Model that Simplifies the Coding of a Group of Object-Oriented Complex Queries. ADBIS (Short Papers) 1999: 178-184
  2. Mary F. Fernandez, Dan Suciu: Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998: 14-23
  3. Chien-Le Goh, Masahiko Tsukamoto, Shojiro Nishio: Fast Methods with Magic Sampling for Knowledge Discovery in Deductive Databases with Large Deduction Results. ER Workshops 1998: 14-28
  4. Hajime Kitakami, Yasuma Mori, Masatoshi Arikawa, Akira Sato: An Integration Methodology for Autonomous Taxonomy Databases Using Priorities. DASFAA 1997: 243-252
  5. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Mixed Integer Programming. ACM Trans. Database Syst. 21(2): 238-269(1996)
  6. Ismail H. Toroslu, Ghassan Z. Qadah: The Strong Partial Transitive-Closure Problem: Algorithms and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 8(4): 617-629(1996)
  7. Jukka Teuhola: Path Signatures: A Way to Speed Up Recursion in Relational Databases. IEEE Trans. Knowl. Data Eng. 8(3): 446-454(1996)
  8. Sakti Pramanik, Sungwon Jung: Description and Identification of Distributed Fragments of Recursive Relations. IEEE Trans. Knowl. Data Eng. 8(6): 1002-1016(1996)
  9. Chien-Le Goh, Masahiko Tsukamoto, Shojiro Nishio: Knowledge Discovery in Deductive Databases with Large Deduction Results: the First Step. IEEE Trans. Knowl. Data Eng. 8(6): 952-956(1996)
  10. Laks V. S. Lakshmanan, Fereidoon Sadri, Iyer N. Subramanian: SchemaSQL - A Language for Interoperability in Relational Multi-Database Systems. VLDB 1996: 239-250
  11. Holger Riedel, Andreas Heuer: Evaluation and Optimization of the LIVING IN A LATTICE Rule Language. ICDE 1996: 318-325
  12. Hendrik Decker, Ernest Teniente, Toni Urpí: How to Tackle Schema Validation by View Updating. EDBT 1996: 535-549
  13. Stefan Brass: SLDMagic - An Improved Magic Set Technique. ADBIS 1996: 75-83
  14. Ernest Teniente, Antoni Olivé: Updating Knowledge Bases While Maintaining Their Consistency. VLDB J. 4(2): 193-241(1995)
  15. Weining Zhang, Ke Wang, Siu-Cheung Chau: Data Partition and Parallel Evaluation of Datalog Programs. IEEE Trans. Knowl. Data Eng. 7(1): 163-176(1995)
  16. Linda Sirounian, William I. Grosky: A Knowledge Model For Unifying Deductive and Non-Deductive Heterogeneous Databases. IEEE Trans. Knowl. Data Eng. 7(1): 82-105(1995)
  17. Sang Ho Lee, Lawrence J. Henschen: Evaluation of Recursive Queries with Extended Rules in Deductive Databases. IEEE Trans. Knowl. Data Eng. 7(2): 328-331(1995)
  18. Jiawei Han: Chain-Split Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 7(2): 261-273(1995)
  19. Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: Mapping Datalog Program Execution to Networks of Procesors. IEEE Trans. Knowl. Data Eng. 7(3): 351-361(1995)
  20. Georges Gardarin, Fernando Machuca, Philippe Pucheral: OFL: A Functional Execution Model for Object Query Languages. SIGMOD Conference 1995: 59-70
  21. Laks V. S. Lakshmanan, Rokia Missaoui: Pushing Semantics Inside Recursion: A General Framework for Semantic Optimization of Recursive Queries. ICDE 1995: 211-220
  22. Giansalvatore Mecca, Anthony J. Bonner: Finite Query Languages for Sequence Databases. DBPL 1995: 12
  23. Sungwon Jung, Sakti Pramanik: An Efficient Representation of Distributed Fragments of Recursive Relations. DASFAA 1995: 397-404
  24. Johann Eder: View Definitions with Parameters. ADBIS 1995: 170-184
  25. Stefan Brass: Magic Sets vs. SLD-Resolution. ADBIS 1995: 185-203
  26. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  27. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs. IEEE Trans. Knowl. Data Eng. 6(4): 501-517(1994)
  28. 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)
  29. Jiawei Han: Constraint-Based Query Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 6(1): 96-107(1994)
  30. 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)
  31. Peter J. Stuckey, S. Sudarshan: Compiling Query Constraints. PODS 1994: 56-67
  32. Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116
  33. Foto N. Afrati: Bounded Arity Datalog (!=) Queries on Graphs. PODS 1994: 97-106
  34. Qi Yang, Clement T. Yu, Chengwen Liu, Son Dao, Gaoming Wang, Tracy Pham: A Hybrid Transitive Closure Algorithm for Sequential and Parallel Processing. ICDE 1994: 498-505
  35. Jukka Teuhola: An Efficient Relational Implementation of Recursive Relationships using Path Signatures. ICDE 1994: 348-355
  36. Tok Wang Ling, Pit Koon Teo: A Normal Form Object-Oriented Entity Relationship Diagram. ER 1994: 241-258
  37. Gabriel M. Kuper, Moshe Y. Vardi: The Logical Data Model. ACM Trans. Database Syst. 18(3): 379-413(1993)
  38. Jan Chomicki, Tomasz Imielinski: Finite Representation of Infinite Query Answers. ACM Trans. Database Syst. 18(2): 181-223(1993)
  39. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
  40. Francesco Bergadano: Inductive Database Relations. IEEE Trans. Knowl. Data Eng. 5(6): 969-972(1993)
  41. Rafiul Ahad, Bing Yao: RQL: A Recursive Query Language. IEEE Trans. Knowl. Data Eng. 5(3): 451-461(1993)
  42. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  43. Ismail H. Toroslu, Ghassan Z. Qadah: The Efficient Computation of Strong Partial Transitive-Closures. ICDE 1993: 530-537
  44. Philippe De Smedt, Stefano Ceri, Marie-Anne Neimat, Ming-Chien Shan, Rafi Ahmed: Recursive Functions in Iris. ICDE 1993: 145-154
  45. Shashi Shekhar, Ashim Kohli, Mark Coyle: Path Computation Algorithms for Advanced Traveller Information System (ATIS). ICDE 1993: 31-39
  46. Kien A. Hua, Jeffrey X. W. Su, Chau M. Hua: Efficient Evaluation of Traversal Recursive Queries Using Connectivity Index. ICDE 1993: 549-558
  47. Jiawei Han, Kangsheng Zeng, Tong Lu: Normalization of Linear Recursions in Deductive Databases. ICDE 1993: 559-567
  48. Cheong Youn, Hyoung-Joo Kim, Lawrence J. Henschen, Jiawei Han: Classification and Compilation of Linear Recursive Queries in Deductive Databases. IEEE Trans. Knowl. Data Eng. 4(1): 52-67(1992)
  49. Michael Stonebraker: The Integration of Rule Systems and Database Systems. IEEE Trans. Knowl. Data Eng. 4(5): 415-423(1992)
  50. 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)
  51. Elisa Bertino, Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Object-Oriented Query Languages: The Notion and the Issues. IEEE Trans. Knowl. Data Eng. 4(3): 223-237(1992)
  52. Toni Urpí, Antoni Olivé: A Method for Change Computation in Deductive Databases. VLDB 1992: 225-237
  53. Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies. SIGMOD Conference 1992: 256-265
  54. Russell Greiner: Learning Efficient Query Processing Strategies. PODS 1992: 33-46
  55. Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66
  56. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Linear Programming. PODS 1992: 283-292
  57. Serge Abiteboul, Allen Van Gelder: Optimizing Active Databases using the Split Technique. ICDT 1992: 171-187
  58. Laks V. S. Lakshmanan, Rokia Missaoui: On Semantic Query Optimization in Deductive Databases. ICDE 1992: 368-375
  59. Jiawei Han: Chain-Split Evaluation in Deductive Databases. ICDE 1992: 376-384
  60. Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
  61. Jean-Pierre Cheiney, Rosana S. G. Lanzelotte: A Model for Optimizing Deductive and Object-Oriented DB Requests. ICDE 1992: 385-392
  62. Ernest Teniente, Antoni Olivé: The Events Method for View Updating in Deductive Databases. EDBT 1992: 245-260
  63. Jiawei Han: Compilation-Based List Processing in Deductive Databases. EDBT 1992: 104-119
  64. Stefan Brass, Udo W. Lipeck: Generalized Bottom-Up Query Evaluation. EDBT 1992: 88-103
  65. Antoni Olivé: Integrity Constraints Checking In Deductive Databases. VLDB 1991: 513-523
  66. Jürgen Seib, Georg Lausen: Parallelizing Datalog Programs by Generalized Pivoting. PODS 1991: 241-251
  67. Wenceslas Fernandez de la Vega, Vangelis Th. Paschos, A. N. Staylopatis: On the Mean Execution Time of Recursive Definitions on Relational Databases. MFDBS 1991: 119-133
  68. Steve Taylor, Nabil I. Hachem: A Direct Algorithm for Computing the Transitive Closure of a Two-Dimensionally Structured File. MFDBS 1991: 146-159
  69. Yan-Nong Huang, Jean-Pierre Cheiney: Parallel Computation of Direct Transitive Closures. ICDE 1991: 192-199
  70. Jiawei Han: Constraint-Based Reasoning in Deductive Databases. ICDE 1991: 257-265
  71. Keh-Chang Guh, Chengyu Sun, Clement T. Yu: Real Time Retrieval and Update of Materialized Transitive Closure. ICDE 1991: 690-697
  72. Sumit Ganguly, Ravi Krishnamurthy, Abraham Silberschatz: An Analysis Technique for Transitive Closure Algorithms: A Statistical Approach. ICDE 1991: 728-735
  73. Lois M. L. Delcambre, Billy B. L. Lim, Susan Darling Urban: Object-Centered Constraints. ICDE 1991: 368-377
  74. Carol Small, Alexandra Poulovassilis: An Overview of PFL. DBPL 1991: 96-110
  75. Sang Ho Lee, Lawrence J. Henschen: Evaluation of Extended Recursive Queries in Deductive Databases. DASFAA 1991: 209-215
  76. Burkhard Freitag, Heribert Schütz, Günther Specht: LOLA - A Logic Language for Deductive Databases and its Implementation. DASFAA 1991: 216-225
  77. Yves Caseau: The LAURE Model for Object-Oriented Logic Databases. DASFAA 1991: 411-420
  78. Jorge B. Bocca: MegaLog - A platform for developing Knowledge Base Management Systems. DASFAA 1991: 374-380
  79. 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)
  80. 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)
  81. H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990)
  82. Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990)
  83. Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990)
  84. Michael Stonebraker, Lawrence A. Rowe, Michael Hirohama: The Implementation of Postgres. IEEE Trans. Knowl. Data Eng. 2(1): 125-142(1990)
  85. Michael V. Mannino, Leonard D. Shapiro: Extensions to Query Languages for Graph Traversal Problems. IEEE Trans. Knowl. Data Eng. 2(3): 353-363(1990)
  86. Johann Eder: Extending SQL with General Transitive Closure and Extreme Value Selections. IEEE Trans. Knowl. Data Eng. 2(4): 381-390(1990)
  87. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo: The LDL System Prototype. IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)
  88. Philippe Pucheral, Jean-Marc Thévenin, Patrick Valduriez: Efficient Main Memory Data Management Using the DBGraph Storage Model. VLDB 1990: 683-695
  89. Juhani Kuittinen, Otto Nurmi, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries. VLDB 1990: 372-379
  90. Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358
  91. Yeh-Heng Sheng: IDLOG: Extending the Expressive Power of Deductive Database Languages. SIGMOD Conference 1990: 54-63
  92. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
  93. Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152
  94. Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242
  95. Kenneth A. Ross: Modular Stratification and Magic Sets for DATALOG Programs with Negation. PODS 1990: 161-171
  96. Won Kim: Research Directions in Object-Oriented Database Systems. PODS 1990: 1-15
  97. Seppo Sippu, Eljas Soisalon-Soininen: Multiple SIP Strategies and Bottom-Up Adorning in Logic Query Optimization. ICDT 1990: 485-498
  98. Nicole Bidoit, P. Legay: WELL!: An Evaluation Procedure for All Logic Programs. ICDT 1990: 335-348
  99. Jaideep Srivastava, Kuo-Wei Hwang, Jack S. Eddy Tan: Parallelism in Database Production Systems. ICDE 1990: 121-128
  100. Thomas Ludwig: A Brief Overview of LILOG-DB. ICDE 1990: 420-427
  101. Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
  102. Anant Jhingran, Michael Stonebraker: Alternatives in Complex Object Representation: A Performance Perspective. ICDE 1990: 94-102
  103. Jorge B. Bocca: Compilation of Logic Programs to Implement Very Large Knowledge Base Systems - A Case Study: Educe*. ICDE 1990: 361-369
  104. Yuki Kusumi, Shojiro Nishio, Toshiharu Hasegawa: File Access Level Optimization Using Page Access Graph on Recursive Query Evaluation. EDBT 1990: 136-152
  105. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Abstract Machine for LDL. EDBT 1990: 153-168
  106. Michael Stonebraker: Future Trends in Database Systems. IEEE Trans. Knowl. Data Eng. 1(1): 33-44(1989)
  107. Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. IEEE Trans. Knowl. Data Eng. 1(2): 185-195(1989)
  108. 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)
  109. Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. IEEE Trans. Knowl. Data Eng. 1(4): 424-432(1989)
  110. Per-Åke Larson, Vinay Deshpande: A File Structure Supporting Traversal Recursion. SIGMOD Conference 1989: 243-252
  111. Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35
  112. Alexander Borgida, Ronald J. Brachman, Deborah L. McGuinness, Lori Alperin Resnick: CLASSIC: A Structural Data Model for Objects. SIGMOD Conference 1989: 58-67
  113. Rakesh Agrawal, Narain H. Gehani: ODE (Object Database and Environment): The Language and the Data Model. SIGMOD Conference 1989: 36-45
  114. Hirohisa Seki: On the Power of Alexander Templates. PODS 1989: 150-159
  115. Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
  116. Y. C. Tay: Attribute Agreement. PODS 1989: 110-119
  117. Yatin P. Saraiya: Linearizing Nonlinear Recursions in Polynomial Time. PODS 1989: 182-189
  118. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
  119. Stavros S. Cosmadakis: On the First-Order Expressibility of Recursive Queries. PODS 1989: 311-323
  120. Anthony J. Bonner: Hypothetical Datalog: Negation and Linear Recursion. PODS 1989: 286-300
  121. W. Yan, Nelson Mendonça Mattos: Transitive Closure and the LOGA+-Strategy for its Efficient Evaluation. MFDBS 1989: 415-428
  122. 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
  123. Kyung-Chang Kim, Won Kim, Alfred G. Dale: Cyclic Query Processing in Object-Oriented Databases. ICDE 1989: 564-571
  124. Isabel F. Cruz, Theodore S. Norvell: Aggregative Closure: An Extension of Transitive Closure. ICDE 1989: 384-391
  125. Jean-Pierre Cheiney, Christophe de Maindreville: Relational Storage and Efficient Retrieval of Rules in a Deductive DBMS. ICDE 1989: 644-651
  126. Hussien Aly, Z. Meral Özsoyoglu: Synchronized Counting Method. ICDE 1989: 366-373
  127. Jianhua Zhu, David Maier: Computational Objects in Object-Oriented Data Models. DBPL 1989: 139-160
  128. Rakesh Agrawal, Narain H. Gehani: Rationale for the Design of Persistence and Query Processing Facilities in the Database Programming Language O++. DBPL 1989: 25-40
  129. Serge Abiteboul, Stéphane Grumbach, Agnès Voisard, Emmanuel Waller: An Extensible Rule-Based Language with Complex Objects and data-Functions. DBPL 1989: 298-314
  130. Jai Hyoung Rhee, Seog Park: An Extension of Counting Method for Efficient Processing of the Cyclic Data. DASFAA 1989: 320-326
  131. Runping Qi, Wolfgang Bibel: A Framework for the Parallel Evaluation of Recursive Queries in Deductive Databases. DASFAA 1989: 301-309
  132. Shojiro Nishio, Masatsugu Nakahata, Eric G. Manning: A New Recursive Query Evaluation Strategy Using Search History Information. DASFAA 1989: 310-319
  133. Wo-Shun Luk, Simon Mok: A Comparison of I/O Performance of Some Linear Recursive Query Processing Methods. DASFAA 1989: 293-300
  134. Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. DASFAA 1989: 285-292
  135. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  136. Michel de Rougemont: Fixed-point semantics and the representation of algorithms on large data. VLDB 1988: 264-272
  137. Christophe de Maindreville, Eric Simon: Modelling Non Deterministic Queries and Updates in Deductive Databases. VLDB 1988: 395-406
  138. Cheong Youn, Lawrence J. Henschen, Jiawei Han: Classification of Recursive Formulas in Deductive Databases. SIGMOD Conference 1988: 320-328
  139. Ouri Wolfson, Abraham Silberschatz: Distributed Processing of Logic Programs. SIGMOD Conference 1988: 329-336
  140. Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms. SIGMOD Conference 1988: 404-412
  141. Raja Ramnarayan, Hongjun Lu: A Data/Knowledge Base Management Testbed and Experimental Results on Data/Knowledge Base Query and Update Processing. SIGMOD Conference 1988: 387-395
  142. Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163
  143. Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351
  144. Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332
  145. Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102
  146. Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60
  147. Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
  148. Peter T. Wood, Alberto O. Mendelzon, Paolo Atzeni: Idempotent Single-Predicate Horn Clauses. ICDT 1988: 129-143
  149. Guozhu Dong: On the Composition and Decomposition of Datalog Program Mappings. ICDT 1988: 87-101
  150. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
  151. Kyu-Young Whang, Stephen Brady: A Framework for Optimization in Expert System - DBMS Interface. ICDE 1988: 126-133
  152. Michael Stonebraker: Future Trends in Data Base Systems. ICDE 1988: 222-231
  153. Seppo Sippu, Eljas Soisalon-Soininen: An Optimization Strategy for Recursive Queries in Logic Databases. ICDE 1988: 470-477
  154. Christophe de Maindreville, Eric Simon: A Production Rule-Based Approach to Deductive Databases. ICDE 1988: 234-241
  155. Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. ICDE 1988: 452-461
  156. Ravi Krishnamurthy, Carlo Zaniolo: Optimization in a Logic Based Language for Knowledge and Data Intensive Applications. EDBT 1988: 16-33
  157. Jiawei Han, Ghassan Z. Qadah, Chinying Chaou: The Processing and Evaluation of Transitive Closure Queries. EDBT 1988: 49-75
  158. Stefano Ceri, Stefano Crespi-Reghizzi, Georg Gottlob, F. Lamperti, Luigi Lavazza, Letizia Tanca, Roberto Zicari: The Algres Project. EDBT 1988: 551-555
  159. Serge Abiteboul, Stéphane Grumbach: COL: A Logic-Based Language for Complex Objects. EDBT 1988: 271-293
  160. Malcolm P. Atkinson, Peter Buneman: Types and Persistence in Database Programming Languages. ACM Comput. Surv. 19(2): 105-190(1987)
  161. 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
  162. Wolfgang Nejdl: Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy. VLDB 1987: 43-50
  163. Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274
  164. Georges Gardarin: Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs. VLDB 1987: 21-30
  165. Stefano Ceri, Letizia Tanca: Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries. VLDB 1987: 31-41
  166. 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
  167. Timos K. Sellis: Efficiently Supporting Procedures in Relational Database Systems. SIGMOD Conference 1987: 278-291
  168. Domenico Saccà, Carlo Zaniolo: Magic Counting Methods. SIGMOD Conference 1987: 49-59
  169. H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344
  170. Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22
  171. Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81
  172. Margaret H. Butler: Storage Reclamation in Object Oriented Database Systems. SIGMOD Conference 1987: 410-425
  173. Hussien Aly, Z. Meral Özsoyoglu: Non-deterministic Modelling of Logical Queries in Deductive Databases. SIGMOD Conference 1987: 60-72
  174. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10
  175. Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362
  176. Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348
  177. Alberto Marchetti-Spaccamela, Antonella Pelaggi, Domenico Saccà: Worst-case Complexity Analysis of Methods for Logic Query Implementation. PODS 1987: 294-301
  178. Gösta Grahne, Seppo Sippu, Eljas Soisalon-Soininen: Efficient Evaluation for a Subset of Recursive Queries. PODS 1987: 284-293
  179. Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
  180. Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226
  181. Clement T. Yu, Weining Zhang: Efficient Recursive Query Processing using Wavefront Methods. ICDE 1987: 652-657
  182. Volker Linnemann: Non First Normal Form Relations and Recursive Queries: An SQL-Based Approach. ICDE 1987: 591-598
  183. Michael Kifer, Eliezer L. Lozinskii: Implementing Logic Programs as a Database System. ICDE 1987: 375-385
  184. Dina Bitton, Maria Hanrahan, Carolyn Turbyfill: Performance of Complex Queries in Main Memory Database Systems. ICDE 1987: 72-81
  185. Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590
  186. Ravi Krishnamurthy, Carlo Zaniolo: Control and Optimization Strategies in the Implementation of LDL. DBPL 1987: 329-345
  187. Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53
  188. Michael Kifer, Eliezer L. Lozinskii: Filtering Data Flow in Deductive Databases. ICDT 1986: 186-202
  189. Paris C. Kanellakis: Logic Programming and Parallel Complexity. ICDT 1986: 1-30

Copyright © Mon Nov 2 21:11:20 2009 by Michael Ley (ley@uni-trier.de)