Safety of datalog queries over infinite databases

ABSTRACT

A query is safe with respect to a set of constraints if for every database that satisfies the constraints the query is guaranteed to yield a finite set of answers. We study here the safety problem for Datalog programs with respect to finiteness constraints. We show that safety can be viewed as a combination of two properties: weak safety, which guarantees the finiteness of intermediate answers, and termination, which guarantees the finiteness of the evaluation. We prove that while weak safety is decidable, termination is not. We then consider monadic programs, i.e., programs in which all intensional predicates are monadic, and show that safety is decidable in polynomial time for monadic programs. While we do not settle the safety problem, we show that a closely related problem, the decision problem for safety with respect to functional dependencies, is undecidable even for monadic programs.

REFERENCES

• AH88: Serge Abiteboul , Richard Hull, Data functions, datalog and negation, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.143-153, June 01-03, 1988, Chicago, Illinois, United States
• 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
• CGKV88: 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]
• CH85: Chandra, A.K., Hard, D.: Hornclause queries and generalizations. J. Looic Proorammino 1(1985), pp. 1-15.
• GM78: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• GMSV87: Gaifman, H., Mairson, H., Sagiv, Y., Vardi M.Y.: Undecidable optimization problems for database logic programs. Proe. ~nd IEEE St/rap. on Logic in Computer Science, Ithaca, 1987, pp. 106-115.
• 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]
• HU79: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Io85: Ioannidis, Y.E.: A time bound on the materialization of some recursively defined views. Proc. I I th Int 'l Conf. on Very Large Data Bases, Stockholm, 1985, pp. 219-226.
• Ki88: Kifer, M.: On safety, domain independence, and capturability of database queries. Proc. Int'l Conf. on Data and Knowledge Bases, Jerusalem, 1988.
• KiL88: Micheal Kifer , Eliezer L. Lozinskii, SYGRAF: Implementing Logic Programs in a Database Style, IEEE Transactions on Software Engineering, v.14 n.7, p.922-935, July 1988 [doi>10.1109/32.42735 ]
• KiRS88: Michael Kifer , Raghu Ramakrishnan , Avi Silberschatz, An axiomatic approach to deciding query safety in deductive databases, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.52-60, March 1988, Austin, Texas, United States [doi>10.1145/308386.308412]
• KrRS88: Ravi Krishnamurthy , Raghu Ramakrishnan , Oded Shmueli, A framework for testing safety and effective computability of extended datalog, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.154-163, June 01-03, 1988, Chicago, Illinois, United States
• 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]
• 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]
• Ra70: Rabin, M.O.: Weakly definable relations and special automata. Proc. SCrap. on Mathematical Logic and Foundations of Set Theory (Y. Bar- Hilel, ed.), North-Holland, 1970, pp. 1-23.
• Ra88: Ramakrishnan, R.: Private communication, 1988.
• RBS87: R. Ramakrishnan , F. Bancilhon , A. Silberschatz, Safety of recursive Horn clauses with infinite relations, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.328-339, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28694]
• RS59: Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Research and Development, 3(1959), pp. 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]
• 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]
• TW68: Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical System Theory 2(1968), pp. 57-81.
• 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]
• Ul88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Decision problems

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

          Nouns: Datalog

General Terms:
Algorithms, Design, Languages, Theory