Decidability and undecidability results for boundedness of linear recursive queries

ABSTRACT

If it is possible to eliminate recursion from a Datalog program P, then P is said to be bounded. It was shown by Gaifman et al that the problem of deciding whether a given Datalog program is bounded is undecidable, even for linear programs that has one 4-ary intensional predicate. We sharpen that result by showing that the problem of deciding whether a given Datalog program is bounded is undecidable, even for linear programs that has one binary intensional predicate. We then consider linear programs with a single recursive rule. We show that if the intensional predicate is binary, then the boundedness problem for such program is decidable, in fact, it is NP-complete.

REFERENCES

• 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]
• 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, Hard, D Computable queries for relational databases J Computer and Systems Sciences 21(1980), pp 156-178
• CH82: Chandra, A K, Ilarel, D Structure and Complexity of Relational Queues J Computer and S11stems Scsences 25(1982), pp 99-128
• CH85: Chandra, A K, Harel, D Item-clause queries and generahzahons J Logsc Programming 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]
• CGKV87: Stavros Cosmadakis , Haim Gaifman , Paris Kanellakis , Moshe Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.477-490, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62259]
• 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]
• CMG86: Chakravarthy, U S, Mmker, J, Grant, J- Semantic query optimmatlon- additional constraints and control strategies Prec. ~nd lnt'l Conf on Expert Database ,qllstems, Charleston, 1986, pp 259-169
• GM78: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• GMSV87: Galfman, 11, Malrson, II, C;agl~, Y, Vard~ M Y Undecldable op|,mj~,ation problem~ for database log,c program~ Proc ~nd IEEE SI/mp on Log,e sn Computer Scsence, Ithaca, 1987, pp 1013-I 15
• 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: Ioannld~s, Y E A time bound on the matermhzatlon of some recursively defined views Proc 11th lnt'i Conf on I er~/ Large Data Bases, Stockholm, 1985, pp 219-226
• JCV84: Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 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: Moscho~ak,s, Y N Elementary lnductson on Abstract Structures North llolland, 1974
• 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]
• Na86a: 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]
• Na86b: Naughton, J F Redundancy m Function-free |Iorn clauses Proc IEEE Syrup on Loglc Programmzng, Salt Lake Clty~ 1986, pp 236-245
• Na86c: Jeffrey F. Naughton, Optimizing function-free recursive inference rules, Stanford University, Stanford, CA, 1986
• 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]
• 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]
• 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]
• 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]
• Va87: Vard,, M Y fl~'~ults on ~-lVay Automata, forthcoming
• Zl76: Zloof, M, Query-by-E~'ample Operatzons on the Transst;ve Closure IBM Research Report RC5526, 1976.