Query evaluation via tree-decompositions

ABSTRACT

A number of efficient methods for evaluating first-order and monadic-second order queries on finite relational structures are based on tree-decompositions of structures or queries. We systematically study these methods.In the first part of the article, we consider arbitrary formulas on tree-like structures. We generalize a theorem of Courcelle [1990] by showing that on structures of bounded tree-width a monadic second-order formula (with free first- and second-order variables) can be evaluated in time linear in the structure size plus the size of the output.In the second part, we study tree-like formulas on arbitrary structures. We generalize the notions of acyclicity and bounded tree-width from conjunctive queries to arbitrary first-order formulas in a straightforward way and analyze the complexity of evaluating formulas of these fragments. Moreover, we show that the acyclic and bounded tree-width fragments have the same expressive power as the well-known guarded fragment and the finite-variable fragments of first-order logic, respectively.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Andréka, H., van Benthem, J., and Németi, I. 1996. Modal languages and bounded fragments of first-order logic. ILLC Research Report ML-96-03, University of Amsterdam.
• 4: Stefan Arnborg , Derek G. Corneil , Andrzej Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.277-284, April 1, 1987 [doi>10.1137/0608024]
• 5: Stefan Arnborg , Jens Lagergren , Detlef Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, v.12 n.2, p.308-340, June 1991 [doi>10.1016/0196-6774(91)90006-K]
• 6: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 7: Chandra Chekuri , Anand Rajaraman, Conjunctive Query Containment Revisited, Proceedings of the 6th International Conference on Database Theory, p.56-70, January 08-10, 1997
• 8: Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 9: Bruno Courcelle, The monadic second order logic of graphs VI: on several representations of graphs by relational structures, Discrete Applied Mathematics, v.54 n.2-3, p.117-149, Oct. 17, 1994 [doi>10.1016/0166-218X(94)90019-1]
• 10: B. Courcelle , M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs, Theoretical Computer Science, v.109 n.1-2, p.49-82, March 1, 1993 [doi>10.1016/0304-3975(93)90064-Z]
• 11: Downey, R. G., and Fellows, M. R. 1999. Parameterized Complexity. Springer-Verlag, New York.
• 12: Ebbinghaus, H.-D., and Flum, J. 1999. Finite Model Theory. 2nd ed. Springer-Verlag, New York.
• 13: Tomás Feder , Moshe Y. Vardi, Monotone monadic SNP and constraint satisfaction, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.612-622, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167245]
• 14: Frick, M. 2001. Easy Instances for Model Checking. Ph.D. dissertation. Albert-Ludwigs-Universität Freiburg.
• 15: Markus Frick , Martin Grohe, The Complexity of First-Order and Monadic Second-Order Logic Revisited, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.215-224, July 22-25, 2002
• 16: Georg Gottlob , Erich Grädel , Helmut Veith, Datalog LITE: a deductive query language with linear time model checking, ACM Transactions on Computational Logic (TOCL), v.3 n.1, p.42-79, January 2002 [doi>10.1145/504077.504079]
• 17: Georg Gottlob , Nicola Leone , Francesco Scarcello, The Complexity of Acyclic Conjunctive Queries, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.706, November 08-11, 1998
• 18: Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303979]
• 19: Georg Gottlob , Nicola Leone , Francesco Scarcello, Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.195-206, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375579]
• 20: Martin Groher , Thomas Schwentick , Luc Segoufin, When is the evaluation of conjunctive queries tractable?, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.657-666, July 2001, Hersonissos, Greece [doi>10.1145/380752.380867]
• 21: Immerman, N. 1999. Descriptive Complexity. Springer-Verlag, New York.
• 22: Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-213, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275511]
• 23: J. A. Makowsky, Model theory and computer science: an appetizer, Handbook of logic in computer science (vol. 1): background: mathematical structures, Oxford University Press, Inc., New York, NY, 1993
• 24: Moret, B., and Shapiro, H. 1990. Algorithms from P to NP. Benjamin/Cummings.
• 25: Stockmeyer, L. J. 1974. The Complexity of Decision Problems in Automata Theory. Ph.D. dissertation, Dept. Electrical Engineering, MIT, Cambridge, Mass.
• 26: Robert E. Tarjan , Mihalis Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Journal on Computing, v.13 n.3, p.566-579, August 1984 [doi>10.1137/0213035]
• 27: Thatcher, J. W., and Wright, J. B. 1968. Generalised finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2, 57--81.
• 28: Peter van Emde Boas, Machine models and simulations, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 29: 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]
• 30: Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212474]
• 31: Yannakakis, M. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases. pp. 82--94.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

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

General Terms:
Algorithms, Languages, Theory, Verification

Keywords:
Acyclic conjunctive queries, combined complexity, hypergraphs, monadic second-order logic, tree-width