Hard problems for simple logic programs

ABSTRACT

A number of optimizations have been proposed for Datalog programs involving a single intensional predicate (“single-IDB programs”). Examples include the detection of commutativity and separability ([Naug88],[RSUV89], [Ioan89a]) in linear logic programs, and the detection of ZYT-linearizability ([ZYT88], [RSUV89], [Sara89], [Sara90]) in nonlinear programs. We show that the natural generalizations of the commutativity and ZYT-linearizability problems (respectively, the sequencability and base-case linearizability problems) are undecidable. Our constructions involve the simulation of context-free grammars using single-IDB programs that have a bounded number of initialisation rules. The constructions may be used to show that containment (or equivalence) is undecidable for such programs, even if the programs are linear, or if each program contains a single recursive rule. These results tighten those of [Shmu87] and [Abit89].

REFERENCES

• Abit89: Serge Abiteboul, Boundedness is undecidable for datalog programs with a single recursive rule, Information Processing Letters, v.32 n.6, p.281-287, Oct. 3, 1989 [doi>10.1016/0020-0190(89)90019-7]
• BMSU86: 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]
• BR87: C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
• CM77: 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]
• HU79: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Ioan89a: Ioanmd,s, Y E {1989} "Commutahv,ty and its role m the processing of hnear recursmn," Tech Report 804, Umverslty of Wisconsin- Madison
• Ioan89b: Ioanmdls, Y E {1989} "Towards an algebrazc theory of recursmn," Tech Report 801, Umverslty of Wisconsin-Madison
• Naug88: Jeffrey F. Naughton, Compiling separable recursions, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.312-319, June 01-03, 1988, Chicago, Illinois, United States
• RSUV89: R. Ramakrishnan , Y. Sagiv , J. D. Ullman , M. Y Vardi, Proof-tree transformation theorems and their applications, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.172-181, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73739]
• SY81: 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]
• Sagi87: Y. Sagiv, Optimizing datalog programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.349-362, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28696]
• Sara89: Y. P. Saraiya, Linearising nonlinear recursions in polynomial time, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.182-189, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73740]
• Sara90: Yatin P. Saraiya, Polynomial-time program transformations in deductive databases, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.132-144, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298551]
• Shmu87: O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.237-249, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28685]
• Ullm89: Unman, ~ D {1989} Prmczples o/Da~.abase and Knowledge.base Systems, Vol II, Computer Scmnce Press, Rockwlle, Md
• ZYT88: Zhang, W, C T Yu and D Troy, "A necessary and sufficmnt cond~tmn to hneax~ze doubly recurs~ve programs m logic databases," unpubhshed manuscript, Dept of EECS, Umvers~ty of Ilhnms at Chicago

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

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

          Nouns: Datalog

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Languages