On the first-order expressibility of recursive queries

ABSTRACT

A Datalog program is bounded iff it is equivalent to a recursion-free Datalog program. We show that, for some classes of Datalog programs, expressibility in first-order query languages coincides with boundedness. Our results imply that testing first-order expressibility is undecidable for binary programs, decidable for monadic programs, and complete for &Sgr;02.

REFERENCES

• 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
• 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]
• BH79: Blass, A., Harary, F." Properties of almost all graphs and complexes, jr. Graph Theory 3(1979), pp. 225-240.
• 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 Sysiems Sciences 21(1980), pp. 156-178.
• CH82: Chandra, A.K., Harel, D." Structure and Complexity of Relational Queries. J. Computer and Systems Sciences 25(1982), pp. 99-128.
• CH85: Chandra, A.K., liarel, D." Hornclause queries and generalizations. J. Logic Programming 1(1985), pp. 1-15.
• 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]
• ChK73: Chang, C.C., Keisler, H.J." Model Theory. North-Holland, 1973.
• 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]
• 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]
• Fa75: Fagin, R." Monadic generalized spectra, geitschr, f. math. Logik nnd Grunlagen d. Math. 21(1975), pp. 89-96.
• 54: Fraiss~, R. Sur les classifications des systemes de relations. Publications So. Universitd Alger 1, No.I(1954).
• Ga81: Gaifman, H." On local and nonlocal properties. Proc. Logic Colloquium (J. Sterne, ed.), North-Holland, 1981, pp. 105-132.
• GMSV87: Gaifman, H., Mairson, H., Sagiv, Y., Vardi M.Y." Undecidable optimization problems for database logic programs. Proc. ~nd IEEE Syrup. on Logic in Computer Science, Ithaca, 1987, pp. 106-115.
• GV85: Gaifman, H., Va.rdi, M.Y.: A simple proof that connectivity of graphs is not first-order definable. Bull. EATCS 26(1985), pp. 43-45.
• GM78: Herve Gallaire , Jack Minker, Logic and Data Bases, Perseus Publishing, 1978
• 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]
• Im81: immerman, N." Number of quantifiers is better than number of tape cells. J. Computer and System Sciences 22(1981), pp. 384-406.
• 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: ioannidis, Y.E." A time bound on the materializa.tion of some recursively defined views. Proc. 1lib Int 'l Conf. on VerTI Large Data Bases, Stockhohn, 1985, pp. 219-226.
• Ka86: P. C. Kanellakis, Logic programming and parallel complexity, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• Ko87: Kola,itis, P.- Personal communication, 1987.
• 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
• Mo74: Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
• 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]
• 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]
• 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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
          Nouns: Datalog

General Terms:
Design, Languages, Performance