Decidable optimization problems for database logic programs

ABSTRACT

Datalog is the language of logic programs without function symbols. It is used as a database query language. If it is possible to eliminate recursion from a Datalog program &Pgr;, then &Pgr; is said to be bounded. It is known that the problem of deciding whether a given Datalog program is bounded is undecidable, even for binary programs. We show here that boundedness is decidable for monadic programs, i.e., programs where the recursive predicates are monadic (the non-recursive predicates can have arbitrary arity). Underlying our results are new tools for the optimization of Datalog programs based on automata theory and logic. In particular, one of the tools we develop is a theory of two-way alternating tree automata. We also use our techniques to show that containment for monadic programs is decidable.

REFERENCES

• AP87: F. Afrati , C. Papadimitriou, The parallel complexity of simple chain queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.210-213, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28682]
• ASU79: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• AU79: 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]
• BKBR87: C. Beeri , P. Kanellakis , F. Bancilhon , R. Ramakrishnan, Bounds on the propagation of selection into logic programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-226, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28683]
• BL80: Brzozowski, J.A., Leiss, E.: On equations for regular languages, finite automata, and sequential networks. Theoretical Computer Science 10(1980), pp. 19-35.
• BR86: 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
• Ch81: Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
• CH80: Chandra, A.K., Harel, D.: Computable queries for rclati(,nal databases. J. Computer and Systems Sciences21(1980), pp. 156 178.
• CH82: Chandra, A.K., llarel, I).: Structure and Complexity of Relational Queries. J. Computer and Systems Sciences 25(1982), pp. 99- 128.
• CH85: Chandra, A.K., Hard, D.: ltorn-clause queries and generalizations. J. Logic Programmint? 1(1985), pp. 1-15.
• CK86: 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]
• CKS81: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 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]
• Co74: Cook, S.A.: An observation on timestorage trade off. J. Computer and System Sciences 9(1974), pp. 308-316.
• Fa75: Fagin, R.: Monadlc generalized spectra. Zeitschr. J. math. Logik und Grunlagen d. Math. 21(1975), pp. 89-96.
• Ga82: Gaifman, H.: On local and non-local properties. Proc. Logic Colloquium (J. Sterne, ed.), North-llolland, 1981, pp. 105--132.
• GM78: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• GMSV87: Gaifman, II., Mairson, II., Sagiv, Y., Vardl M.Y.: Undecidable optimization problems for database logic programs. Proc. ~nd IEEE Syrup. on LotTic in Computer Science, Ithaca, 1987, pp. 106-115.
• GR82: Yuri Gurevich , Leo Harrington, Trees, automata, and games, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.60-65, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802177]
• HN84: 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]
• Im86: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• Io85: loannidis, Y.E.: A time bound on the materialization of some recursively defined views. Proc. l ! th lnt 'i Conf. on Very Large Data Bases, Stockholm, 1985, i)i). 219226.
• Ka86: P. C. Kanellakis, Logic programming and parallel complexity, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• Mo74: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• MS87: David, E. Muller , Paul, E. Schupp, Alternating automata on infinite trees, Theoretical Computer Science, v.54 n.2-3, p.267-276, Oct. 1987 [doi>10.1016/0304-3975(87)90133-2]
• MUV84: David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, On the foundations of the universal relation model, ACM Transactions on Database Systems (TODS), v.9 n.2, p.283-308, June 1984 [doi>10.1145/329.318580]
• MW88: David Maier , David S. Warren, Computing with logic: logic programming with Prolog, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1988
• Na86: Jeff Naughton, Data independent recursion in deductive databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.267-279, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15420]
• NS87: J. F. Naughton , Y. Sagiv, A decidable class of bounded recursions, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-236, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28684]
• RS59: R~bin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Research and Development, 3(1959), Pl:'. 114-125.
• Sa85: Yehoshua Sagiv, On computing restricted projections of representative instances, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.171-180, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325427]
• Sh59: Shepherdson, J.C.: The reduction o{ twoway automata to one-way automata. IBM d. Research and Development, 3(1959), pp. 199- 201.
• Sh87: 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]
• St82: Streett, R.S.: Propositional dynamic logic of looping and converse is elementarily decidable. Information and Contro~ 54(1982), pp. 121-141.
• Ul85: 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]
• UV86: Ullman, J.D., Van GeldLer, A.: Parallel complexity of logical query programs. Proc. ~7th IEEE Syrup. on Foundations of Computer Science, ~}'oronto, 1986, pp. 438 454.
• Va82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• Va88: Moshe Y. Vardi, Decidability and undecidability results for boundedness of linear recursive queries, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.341-351, March 1988, Austin, Texas, United States [doi>10.1145/308386.308470]
• Zl76: Zloof, M.: Query-by-Example: Operations on the Transitive Closure. IBM Research Report RC5526, 1976.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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

General Terms:
Algorithms, Theory