Expressiveness of restricted recursive queries

ABSTRACT

We study the effect of various syntactic restrictions on the expressive power of database logic programs. We find natural examples of programs which require recursively defined predicates of arbitrarily large width, require rules with arbitrarily many recursive calls, or require nonlinear rules, but can be evaluated in NC2.

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]
• 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]
• 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 relational databases. J. Computer and Systems 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., Harel, 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]
• 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]
• Co74: Cook, S.A.' An observation on time-storage trade off. J. Computer and System Sciences 9 (1974), pp. 308-316.
• GMSV87: Gaifman, H., Mairson, H., Sagiv, Y., Vardi M.Y.: Undecidable optimization problems for database logic programs. Proc. 2nd IEEE Symp. on Logic in Computer Science, Ithaca, 1987, pp. 106-115.
• 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]
• HU79: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Im81: hnmerman, N.' Number of quantifiers is better titan 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]
• Im87: hnmerman, N.' Expressibility as a complexity measure: results and directions. Pvoc. ~nd IEEE Conf. on Structure in Complexity Theory, Ithaca, 1987, pp. 194-202.
• Im87b: Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
• Io85: Ioannidis, Y.E.' A time bound on the materialization of some recursively defined views. Proc. 111h }nt 'l Conf. on Very Large Data Bases, Stockholm, 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
• 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]
• 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]
• UlVG86: Ullman, J.D., Van Gelder, A.' Parallel complexity of logical query programs. P~'oc. ~7th IEEE Syrup. on Foundaiions of Uomp. Sci., Toronto, 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

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

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Design, Languages, Performance, Theory