Evaluation of database recursive logic programs as recurrent function series

ABSTRACT

The authors introduce a new method to compile queries referencing recursively defined predicates. This method is based on an interpretation of the query and the relations as functions which map one column of a relation to another column. It is shown that a large class of queries with associated recursive rules, including mutually recursive rules, can be computed as the limit of a series of functions. Typical cases of series of functions are given and solved. The solutions lend themselves towards either extended relational algebra or SQL optimized programs to compute the recursive query answers. Examples of applications are given.

REFERENCES

• AHO 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]
• BANC 85a: BANCILHON F "Evaluation des clauses de Horn dans les bases de donn6es relatlonnelles", A parattre dans PRC BD3, Eyrolles 1986
• BANC 85b: BANCILHON F "Nawe evaluation of recurs#vely defined predicates" MCC internal report, 1985
• BANC 85c: BANCILHON F, MAIER D, SAGIV Y, ULLMAN J D "Magic sets and other strange ways to implement logic programs", MCC internal report, 1985
• BERN 79: BERNSTEIN P A, CHRJ D W "Using semi-joins to solve relational quertes", Techmcal report CCA 01-79, Jan 1979
• CHAN 82: Ashok K. Chandra , David Harel, Horn clauses and the fixpoint query hierarchy, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588137]
• CHAN 81: CHANG C "On evaluation of queries containing derived relation #n a relational database", m {GALL 81}
• GALL 81: Herve Gallaire , Jack Minker , Jean M. Nicholas, Advances in Data Base Theory, Perseus Publishing, 1981
• GALL 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]
• HENS 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]
• LOZI85: LOZINSKII E L "Evaluatton queries m deductive databases by generating subquenes", IJCAI Proc, pp 173-177, Los Angeles, August 1985
• MARQ83: MARQUE-PUCHEU G "Algebraic structure of answers m a recurs#ve logic database", Rapport Ecole Normale Sup6neure, 1983
• ROHM85: ROHMER J, LESCOEUR R "La m6thode d'Alexandre une solution pour tralter les ax#omes r#.curslfs dans les bases de donn6es d6ductlves", Rapport de recherche, Bull, DRAL/IA/45 01 1985
• TARS 55: TARSKI A "A lattace theoretical fixpomt theorem and #ts appheat#ons", Pactfie journal of mathematics, N" 5, pp 285-309, 1955
• ULLM 85: Jeffrey D. Ullman, Implementation of logiclal query languages for databases (abstract only), ACM SIGMOD Record, v.14 n.4, p.444, May 1985
• VIEI85: VIEILLE L"Recurslve axioms m deductive databases the query sub-query approach", ECRC internal report 1985

INDEX TERMS

Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Algorithms, Theory