The complexity of relational query languages (Extended Abstract)

ABSTRACT

Two complexity measures for query languages are proposed. Data complexity is the complexity of evaluating a query in the language as a function of the size of the database, and expression complexity is the complexity of evaluating a query in the language as a function of the size of the expression defining the query. We study the data and expression complexity of logical languages - relational calculus and its extensions by transitive closure, fixpoint and second order existential quantification - and algebraic languages - relational algebra and its extensions by bounded and unbounded looping. The pattern which will be shown is that the expression complexity of the investigated languages is one exponential higher then their data complexity, and for both types of complexity we show completeness in some complexity class.

REFERENCES

• 1: 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]
• 2: Bancilhon, F.: On the completeness of query languages for relational databases. Proc. 7th Symp. on MFCS, 1978.
• 3: Chandra, A.K., Harel, D.: Computable queries for relational databases. JCSS 21(1980), pp. 156-177.
• 4: Chandra, A.K., Harel, D.: Structure and complexity of relational queries. Proc. 21st IEEE Symp. on FOCS, 1980, pp. 333-347. Also, to appear in JCSS.
• 5: Ashok K. Chandra , David Harel, Horn clauses and the fixpoint query hierarchy, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588137]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: Codd, E.F.: Relational completeness of database sublanguage. In Data Base Systems (Rustin, Ed.), Prentice Hall, 1972, pp. 65-98.
• 10: Cooper, E.C.: On the expressive power of query languages for relational databases. Proc. ACM Symp. on PODS, Los Angeles, March 1982.
• 11: Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation (R. Karp, ed), SIAM-AMS Proc. 7(1974). pp. 43-73.
• 12: Hartmanis, J.: On non-determinacy in simple computing devices. Acta Info. 1(1972), pp. 28-36.
• 13: Hartmanis, J., Steams, R.E.: On the computational complexity of algorithms. Trans. AMS 117(1965), pp. 285-306.
• 14: Ibarra, O.H.: On two-way multihead automata. JCSS 7(1973), pp. 28-36.
• 15: Immerman, N.: Number of quantifier is better than number of tape cells. JCSS 22(1981), pp. 384-406.
• 16: Immerman, N.: Relational queries computable in polynomial time. This volume.
• 17: Jones, N.D.: Space bounded reducibility among combinatorial problems. JCSS 11(1975), pp. 68-85.
• 18: Jones, N.D.: Laaser, W.T.: Complete problems in deterministic polynomial time. TCS 3(1977), pp. 105-117.
• 19: Jones, N.D., Selman, A.L.: Turing machines and the spectra of first-order sentences. J. of Symbolic Logic 39(1974), pp. 139-150.
• 20: Karp, R.M.: Reducibility among combinatorial problems. In Complexity of Computer Computation (R.E. Miller and J.W. Thatcher, eds.), Plenum Press, 1972, pp. 85-103.
• 21: Richard E. Ladner, The circuit value problem is log space complete for P, ACM SIGACT News, v.7 n.1, p.18-20, January 1975 [doi>10.1145/990518.990519]
• 22: Nancy Lynch, Log Space Recognition and Translation of Parenthesis Languages, Journal of the ACM (JACM), v.24 n.4, p.583-590, Oct. 1977 [doi>10.1145/322033.322037]
• 23: Paredaens, J.: On the expressive power of the relational algebra. IPL 7(1978).
• 24: Stockmeyer, L.J.: The polynomial time hierarchy. TCS 3(1977), p. 1-22.
• 25: Zloof, M.: Query-by Example: Operations on the transitive closure. IBM Research Report RC5526, 1976.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Languages