An amateur's introduction to recursive query processing strategies

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.

REFERENCES

• Afrati et al 86: Foto Afrati , Christos Papadimitriou , George Papageorgiou , Athena Roussou , Yehoshua Sagiv , Jeffrey D Ullman, Convergence of sideways query evaluation, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.24-30, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15400]
• Aho and Ullman 79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• Apt and Van Emden 82: Krzysztof R. Apt , M. H. van Emden, Contributions to the Theory of Logic Programming, Journal of the ACM (JACM), v.29 n.3, p.841-862, July 1982 [doi>10.1145/322326.322339]
• Bancilhon 85: "Nmve Evaluation of Recurslvely Defined Relations," F Bancllhon, m On Knowledge Base Management Systems - Integrating Database and AI Systems, Bro&e and Mylopoulo,, Eds , Sprsnger-Verlag
• Bancilhon 85a: "A Note on the Performance of Rule Based Systems," F Banellhon, MCC Techmcal Report DB-022-85, 1985
• Bancilhon et al 86: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• Bancilhon et al 86a: "Magic Sets Algorithms and Examples," F Bancflhon, D Miner, Y Saglv and J Ullman, Unpubhshed Manuscr,pt, 1986
• Bancilhon and Ramakrishnan 86: "Performance Evaluatmn of Data Intensive Logxc Programs," F Bancllhon and R Ramakrrshnan,Unpubhshed Manuscrtlat, March 1986
• Bayer 85: "Query Evaluatmn and Reeursmn m Deductive Database Systems," R Bayer, Unpttbhshed Manuserspt, 1985
• Chang 81: '#On the Eva|uatlon of Queries Contalmng Derived Relations m Relational Databases," C Chang, In Advances m Data Base Theory, Vol l, H GaUa#r~, J Mmker and J M Nicolas, Plenum Pre#6, New York, 1981, pp 235-260
• Dayal et al 85: "PROBE- a Research Project m Knowledge-Oriented Database Systems Prehmmary Analysis," U Dayal, A Buchmann, D Goldhlrsch, S Hefler, F Manola, J Orenstem and A Rosenthal, Teehmcal Report, CCA-85-03, July 1985
• Delobel 86: "Bases de Donnees et Bases de Connmssauces Une Approche Systemxque a l'Atde d'une Algebre Matnclelle des Relations," C Delobel Jonrnees Francophones, Grenoble, January 1986
• Dietrich and Warren 85: "Dynamic Programming Strategms for the Evaluatmn of Recursive Queries," S W Dietrich and DS Warren, Unpubhshed Report, 1985
• Gallaire et al 84: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• Gardarin and Maindreville 85: Georges Gardarin , Christophe de Maindreville, Evaluation of database recursive logic programs as recurrent function series, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.177-186, May 28-30, 1986, Washington, D.C., United States
• Han and Lu 86: Jiawei Han , Hongjun Lu, Some Performance Results on Recursive Query Processing in Relational Database Systems, Proceedings of the Second International Conference on Data Engineering, p.533-541, February 05-07, 1986
• Henschen and Naqvi 84: Lawrence J. Henschen , Shamim A. Naqvi, On compiling queries in recursive first-order databases, Journal of the ACM (JACM), v.31 n.1, p.47-85, Jan. 1984 [doi>10.1145/2422.2423]
• Kifer and Lozinskii 85: "Query Opttmlzatmn m Logxc Databases," M Kffer and E Lozmskn, T#ehmcal R#port, SUNY at Stonybrook, June 1985
• Laskowski 84: "Compdmg Recurmve Axtoms m First Order Databases," K Laskowskl, Masters Thesss, Northwestern Unwers,ty, 198#
• Lozinskii 83: "A Problem-Oriented Inferentml Database System," E Lozlnskn, Tech Report 83-17, The Hebrew Unwersdy of Jerusalem, May 1983
• Lozinskii 85: "Evaluating Quertes m Deductive Databases by Generating," E Lozmskn, Proc 11th Internatwnal Joint Conference on Artsfiesal Intelhgenee, 1985
• Lozinskii 85a: "Inference by Generating and Structuring of Deduetwe Databases," E Lozmskn, Unpnbhshed Manuscr:pt, 1985
• Marque-Pucheu 83: "Algebraic Structure of Answers m a Recurslve Logic Database," G Marque-Pueheu, To appear m Acta Informahea
• Marque-Pucheu et al 84: "Interfacing Prolog and Relatmnal Database Management Systems," G Marque-Pueheu, J Martm-Gallausaux and G Jomter, tn New Apphcattons of Databases, Gardarm and Gelenbe Eds, Aeadem,e Press, London, 1984
• McKay and Shapiro 81: "Using Active Connectmn Graphs for Reasomng wtth Reeurslve Rules," D McKay and S Shapiro, Proc 7th Internat, onal Josnt Conference on Artsfictal Intelhgenee, 1981
• Morris et al 86: Katherine Morris , Jeffrey D Ullman , Allen Van Gelder, Design overview of the NAIL] system, Proceedings on Third international conference on logic programming, p.554-568, September 1986, London, United Kingdom
• Naqvi and Fishman 81: "An Improved Compdmg Techmque for First Order Databases," Sham#m A Naqvx and Darnel H Ftshman, Proe Formal Bases for Databases, Toulouse, October 1981
• Naqvi and Henschen 83: "Synthesmng Least F#xed Point Queues into Non-reeurs#ve Iterat#ve Programs," S Naqw and L Hensehen, Proe 9th International Joint Conference on Art#fic,al Intelhgence, Karlsruhe, 1983
• Reiter 78: "Deductive Questxon Answenng on Relatmnal Data Base," R Re#ter, In Logic and Data Bases, H Galla#re and J Mmker Piehum Press, New York, 1978, pp 1#9-177
• Rohmer and Lescoeur 85: "La Methode Alexandre une solution pour tralter les axlomes recurmfs dons les bases de donnees deductives ," Colloque Reeonnass- 8anee de Forme8 et Intelhoenee Art,ficselle, Grenoble, November 1985
• Rosenthal et al 85: "Traversal Recurslon A Practical Approach to Supporting Recurmve Apphcat,ons," A Rosenthal, S Heller, U Dayal, F Manola, Unpubhshed Report, CCA, December 1985
• Sacca and Zaniolo 86a: Domenico Saccà , Carlo Zaniolo, On the implementation of a simple class of logic queries for databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.16-23, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6013]
• Sacca and Zaniolo 86b: "Implementing Recurslve Logic Quenes with Function Symbols,"Unpublished Manuaer,pt, Aprd 1986
• Sagiv and Ullman 84: Yehoshua Sagiv , Jeffrey D. Ullman, Complexity of a top-down capture rule, Stanford University, Stanford, CA, 1984
• Shapiro and McKay 80: "Inference wath Recurslve Rules," S Shapiro and D McKay, Proc 1st Annual Nat, onal Conference on Art,fie,at Intelhgence, August, 1980
• Shapiro et al 82: "Bi-Dlrectmnal Inference," S Shapiro, J Martins and D McKay, Proe #th Annual Conference of the Cogs,tire Science Society, Ann Arbor, Mtehtgan, 1982
• Tarski 55: "A LatUce Theoret,cal FL#pomt Theorem and its Apphcatmns" A Tarskb Paesfie Journal of Mathematscs 5, 1955, pp 285-309
• Ullman 85: "implementatmn of Logical Query Languages for Databases," J Ullman, TOLD, Vol 10, No 8, pp #89-821, 1985
• Ullman and Van Gelder 85: "Testing Apphcabfllty of Top-Down Capture Rules," J Ullman and A Van Gelder, Teehmcal Report, Stanford Unwerstty, STAN- CS-85-10# 6, 1985
• Van Emden and Kowalski 76: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• Valduriez and Boral 86: "Evaluatmn of Recurslve Quenes Using Join In&ces," P Valdunez and H Boral, Proe Fsrst Intl Conference on Ezpert Database Systems, Charleston, 1986
• Vieille 85: "On Handhng Recurslvely Defined Virtual Relatmns m Deductive Databases," L Vlellle, Unpubhshed Report, ECRC, Mumeh
• Vieille 86: "Recursive axmms in Deductive Databases The Query/Subquery Approach," L Vleflle, Proc First Intl Conference on Ezpert Database Systems, Charleston, 1986
• Zaniolo 85: "The Representation and Deductive Retrieval of Complex Objects," C Zamolo, Proe 11th Int Conference on Very Large Data Bases, Stockholm, September 1985
• Zaniolo 86: "Safety and Compllatmn of Non-Reeurmve Horn Clauses," C Zamolo Proe F, rst Intl Conference on Ezpert Database Systems, Charleston, 1986

INDEX TERMS

Classification:
  A. General Literature
  A.1 INTRODUCTORY AND SURVEY

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Prolog

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Languages, Performance