Optimizing datalog programs

ABSTRACT

Datalog programs, i.e., Prolog programs without function symbols, are considered It is assumed that a variable appearing in the head of a rule must also appear in the body of the rule. The input of a program is a set of ground atoms (which are given in addition to the program's rules) and, therefore, can be viewed as an assignment of relations to some of the program's predicates. Two programs are equivalent if they produce the same result for all possible assignments of relations to the extensional predicates (i.e., the predicates that do not appear as heads of rules). Two programs are uniformly equivalent if they produce the same result for all possible assignments of initial relations to all the predicates (i.e., both extensional and intentional). The equivalence problem for Datalog programs is known to be undecidable. It is shown that uniform equivalence is decidable, and an algorithm is given for minimizing a Datalog program under uniform equivalence. A technique for removing parts of a program that are redundant under equivalence (but not under uniform equivalence) is developed. A procedure for testing uniform equivalence is also developed for the case in which the database satisfies some constraints.

REFERENCES

• 1: A V Aho, Y Saglv, and J D Ullman {1979} "Eqmvalences among relational (,xprcsslons," SIAM J Computing, 8:2, pp 218-246
• 2: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 3: 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]
• 4: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 5: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 6: U S Chakravarthy, J Mlnker, and J Grant {1986} "Semantic Query Optlmlzatmn Addltmnal Constraants and Control Strategies," Proc First Int Conf on Expert Database Systems, April 1-4, Charleston, S C, pp 259-269
• 7: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 8: S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
• 9: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 10: J. J. Finger, Exploiting constraints in design synthesis, Stanford University, Stanford, CA, 1987
• 11: H Gaffman {1986} Private commumcatmn
• 12: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• 13: 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]
• 14: Michael Kifer , Eliezer L Lozinskii, Filtering data flow in deductive databases, Proceedings on International conference on database theory, p.186-202, December 1986, Rome, Italy
• 15: Jonathan Jay King, Query optimization by semantic reasoning, 1981
• 16: Anthony Klug , Rod Price, Determining View dependencies using tableaux, ACM Transactions on Database Systems (TODS), v.7 n.3, p.361-380, Sept. 1982 [doi>10.1145/319732.319738]
• 17: Eliezer L. Lozinskii, A problem-oriented inferential database system, ACM Transactions on Database Systems (TODS), v.11 n.3, p.323-356, Sept. 1986 [doi>10.1145/6314.6419]
• 18: Michael J Maher, Equivalences of logic programs, Proceedings on Third international conference on logic programming, p.410-424, September 1986, London, United Kingdom
• 19: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 20: D McKay and S Shapiro {1981} "Using active connection graphs for reasoning wlth recurmve rules," Proc 7th IJCAL pp 368- 374
• 21: S A Naqvl {1986} "A logic for negation m database systems," Preprmts of Workshop on Founda~lons of Deduc~lve Databases and Logic Programming, (:I Mmker, ed ), August 18--22, Washington, D C, pp 378- 387
• 22: J F Naughton {1986} "Redundancy m functmn-free recurmve rules," Proc 1986 Syrup on Logic Progrm'nmmg, September 22-25, Salt Lake C~ty, pp 236-245
• 23: Rohmer and R Lescoeur {1985} "The Alexander Method A Technique fol the Processing of Recurmve Axioms an Deductive Databases," Bull Internal Repol t
• 24: 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]
• 25: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 26: O Shmueh {1986} "Decldablhty and expressiveness aspects of logic querms," unpublished manuscript, Computer Scmnce Dept, Techmon - Israel Institute of Tcchllolog, b, Haafa 32000, Israel
• 27: Jeffrey D. Ullman, Implementation of logical query languages for databases, ACM Transactions on Database Systems (TODS), v.10 n.3, p.289-321, Sept. 1985 [doi>10.1145/3979.3980]
• 28: 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]
• 29: Allen Van Gelder, A message passing framework for logical query evaluation, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.155-165, May 28-30, 1986, Washington, D.C., United States
• 30: A Van Gelder {1986b} "Ncgatmn ,l~ failure using tlght derlvatmns fol gener.i1 logic programs," Proc 1986 Syrup cm Logl~ Programming, September 22-25, Salt L,~k~' CaW, pp 127-138
• 31: M Yannakak~s and C H Pap~d~m~t~ou
• 1982: "Algebrmc dependencies," J Cornput Syst Sc~ , 25, pp 2-41

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing

          Nouns: DATALOG

General Terms:
Algorithms, Languages, Management, Theory, Verification