Queries are easier than you thought (probably)

ABSTRACT

The optimization of a large class of queries is explored, using a powerful normal form recently proven. The queries include the fixpoint and while queries, and an extension of while with arithmetic. The optimization method is evaluated using a probabilistic analysis. In particular, the average complexity of fixpoint and while is considered and some surprising results are obtained. They suggest that the worst-case complexity is sometimes overly pessimistic for such queries, whose average complexity is often much more reasonable than the provably rare worst case. Some computational properties of queries are also investigated. A probabilistic notion of boundedness is defined, and it is shown that all programs in the class considered are bounded almost everywhere. An effective way of using this fact is provided.

REFERENCES

• AG92: S. Abiteboul and A. Van Gelder. Optimizing active databases using the split technique. Technical report, INRIA, 1992.
• AS91: Serge Abiteboul , Eric Simon, Fundamental properties of deterministic and nondeterministic extensions of Datalog, Theoretical Computer Science, v.78 n.1, p.137-158, Jan. 21, 1991
• AV91a: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• AV91b: Serge Abiteboul , Victor Vianu, Generic Computation and its complexity, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.209-219, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103444]
• AVV91: $. Abiteboul, M. Vardi, and V. Vianu. Fixpoint logics, relational machines, and computational complexity. Technical report, in preparation, 1991.
• AVV92: S. Abiteboul, M. Vardi, and V. Vianu. Computing with infinitary logic. Technical report, in preparation, 1992.
• Bol85: B61a Bollob~s. Random Graphs. Academic Press, London, 1985.
• CH80: A.K. Chandra and D. Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156- 178, 1980.
• CH82: A.K. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25(I):99-128, 1982.
• Cha81: 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]
• Dah87: Elias Dahlhaus, Skolem normal forms concerning the least fixpoint, Computation theory and logic, Springer-Verlag, London, 1987
• Fag90: Ronald Fogin, Finite-model theory—a personal perspective, Proceedings of the third international conference on database theory on Database theory, p.3-24, November 1990, Paris, France
• Gel89: A. Van Gelder, The alternating fixpoint of logic programs with negation, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73722]
• GJ79: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Gra83: E. Grandjean. Complexity of the first-order theory of almost all finite structures. Inform. and Control, 57:180-204, 1983.
• GS86: Y. Gurevich and S. Shelah. Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic, 32:265-280, 1986.
• Gur91: Yuri Gurevich, Average case completeness, Journal of Computer and System Sciences, v.42 n.3, p.346-398, June 1991 [doi>10.1016/0022-0000(91)90007-R]
• Imm86: 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]
• Imm87: N. Immerman. Expressibility as a complexity measure: Results and directions. Technical Report DCS-TR-538, Yale Univ., 1987.
• KA89: P. Kanellakis , S. Abiteboul, Database theory column, ACM SIGACT News, v.20 n.4, p.17-23, Nov. 1989 [doi>10.1145/74074.74077]
• Kan91: Paris C. Kanellakis, Elements of relational database theory, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• Kol91: Phokion G. Kolaitis, The expressive power of stratified logic programs, Information and Computation, v.90 n.1, p.50-66, Jan. 1991 [doi>10.1016/0890-5401(91)90059-B]
• KP88: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.231-239, March 1988, Austin, Texas, United States [doi>10.1145/308386.308446]
• KV87: P. Kolaitis , M. Vardi, The decision problem for the probabilities of higher-order properties, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.425-435, January 1987, New York, New York, United States [doi>10.1145/28395.28441]
• KV90a: P. Kolaitis and M. Vardi. 0-1 laws for infinitary logics. In 5th IEEE Syrup. on Logic in Computer Science, pages 156-167, t990.
• KV90b: Phokion G. Kolaitis and Moshe Y. Vardi. 0-1 laws for infinitary logics. In Proc. 5th IEEE Conf. on Logic in Computer Science, pages 156-167, Los Angeles, 1990. IEEE Computer Society Press.
• KV92: Phokion G. Kolaitis , Moshe Y. Vardi, Infinitary logics and 0–1 laws, Information and Computation, v.98 n.2, p.258-294, June 1992 [doi>10.1016/0890-5401(92)90021-7]
• Lev86: Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
• SN91: S. Seshadri , Jeffrey F. Naughton, On the expected size of recursive Datalog queries, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.268-279, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113438]
• SS88: Saharon Shelah and Joel Spencer. Zero-one laws for sparse random graphs. Amer. J. Math., 1:97-115, 1988.
• Ull88: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• Var82: 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]
• Var92: M. Vardi, 1992. email communication.
• Wil84: H.S. Will. Backtrack: an o(1)expected time algorithm for the graph coloring problem. Information Processing Letters, 18:3:119-121, 1984.

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.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

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

General Terms:
Languages, Performance