ABSTRACT
In a previous paper [10], the authors introduced the notion of hypertree decomposition and the corresponding concept of hypertree width and showed that the conjunctive queries whose hypergraphs have bounded hypertree-width can be evaluated in polynomial time. Bounded hypertree-width generalizes the notions of acyclicity and bounded treewidth and corresponds to larger classes of tractable queries. In the present paper, we provide natural characterizations of hypergraphs and queries having bounded hypertree-width in terms of game-theory and logic.
First we define the Robber and Marshals game, and prove that a hypergraph H has hypertree-width at most k iff k marshals have a winning strategy on H, allowing them to trap a robber who moves along the hyperedges. This game is akin the well-known Robber and Cops game (which characterizes bounded treewidth), except that marshals are more powerful than cops: They can control entire hyperedges instead of just vertices.
Kolaitis and Vardi [17] recently gave an elegant characterization of the conjunctive queries having treewidth < k in terms of the k-variable fragment of a certain logic L ( = existential-conjunctive fragment of positive FO). We use the Robber and Marshals game to derive a surprisingly simple and equally elegant characterization of the class HW[k] of queries of hypertree-width at most k in terms of guarded logic. In particular, we show that HW[k] = GFk (L), where GFk(L) denotes the k-guarded fragment of L. In this fragment, conjunctions of k atoms rather than just single atoms are allowed to act as guards. Note that, for the particular case k = 1, our results provide new characterizations of the class of acyclic queries.
We extend the notion of bounded hypertreewidth to nonrecursive stratified datalog and show that the k-guarded fragment GFk(FO) of first order logic has the same expressive power as nonrecursive stratified datalog of hypertreewidth ⪇ k.
- 1.S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases, Addison-Wesley Publishing Company, 1995.]] Google ScholarDigital Library
- 2.S. Abiteboul and O.M. Duschka. Complexity of Answering Queries Using Materialized Views. In Proc. of PODS'98, Seattle, Washington, pp. 254-263, 1998.]] Google ScholarDigital Library
- 3.J. Van Benthem. Dynamic Bits and Pieces. ILLC Research Report, University of Amsterdam, 1997.]]Google Scholar
- 4.A.K. Chandra and P.M. Merlin. Optimal Implementation of Conjunctive Queries in relational Databases. In ACM Symp. on Theory of Computing (STOC'77), pp.77-90, 1977.]] Google ScholarDigital Library
- 5.Ch. Chekuri and A. Rajaraman. Conjunctive Query Containment Revisited. Theoretical Computer Science, 239(2):211-229, 2000. A preliminary version appeared in Proe. of ICDT:97, Springer LNCS, Vol. 1186, pp.56-70, 1997.]] Google ScholarDigital Library
- 6.B.Courcelle: Monadic second-order logic of graphs VII: Graphs as relational structures, in Theoretical Computer Science, Vol 101, pp. 3-33 (1992).]] Google ScholarDigital Library
- 7.R. Dechter and J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, pp. 38:353-366, 1989.]] Google ScholarDigital Library
- 8.J. Flum, M. Frick: and M. Grohe. Query Evaluation via Tree-Decomposition. In Proe. of ICDT:01, Springer LNCS, Vol. 1973: pp.22-38, 2001.]] Google ScholarDigital Library
- 9.G. Gottlob, N. Leone, and F. Scarcello. The Complexity of Acyclic Conjunctive Queries. To appear in Journal of the ACM. An extended abstract concerning part of this work has been published in Proe. of the IEEE Symposium on Foundations of Computer Science (FOCS'98), pp.706-715, Palo Alto, CA, 1998.]] Google ScholarDigital Library
- 10.G. Gottlob, N. Leone, and F. Scarcello. Hypertree Decompositions and Tractable Queries. To appear in Journal of Computer and System Sciences. An extended abstract concerning part of this work has been published in Proceedings of the Eighteenth ACM Symposium on Principles of Database Systems (PODS'99), pp. 21-32, Philadelphia, Pennsylvania, May 1999.]] Google ScholarDigital Library
- 11.G. Gottlob, N. Leone, and F. Scarcello. A Comparison of Structural CSP Decomposition Methods. Artificial Intelligence, 124(2):243-282, 2000. A preliminary version appeared in Proe. of IJCAF99, Vol.1, pp. 394-399, 1999.]] Google ScholarDigital Library
- 12.G. Gottlob, E. Gradel, H. Veith. Datalog LITE: A Deductive Query Language with Linear Time Model Checking. To appear in ACM Transactions on Computational Logic.]] Google ScholarDigital Library
- 13.G. Gottlob and R. Pichler. Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width. Maunuscript, submitted for publication. 2001.]]Google Scholar
- 14.E. Gradel. On the Restraining Power of Guards. Journal of Symbolic Logic, Vol. 64,pp. 1719-1742, 1999.]]Google ScholarCross Ref
- 15.M. Grohe, T. Schwentick, and L. Segoufin. When is the Evaluation of Conjunctive Queries Tractable? To appear in Proc. ACM STOCk01, 2001.]] Google ScholarDigital Library
- 16.M. Gyssens, P.G. Jeavons, and D.A. Cohen. Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence, 66:57-89, 1994.]] Google ScholarDigital Library
- 17.Ph. G. Kolaitis and M. Y. Vardi. Conjunctive-Query Containment and Constraint Satisfaction. Journal of Computer and System Sciences, 61:302-332, 2000.]] Google ScholarDigital Library
- 18.A. Lustig and O. Shmueli. Acyclic Hypergraph Projections. J. of Algorithms, 30:400-422, 1999.]] Google ScholarDigital Library
- 19.N. Robertson and P.D. Seymour. Graph Minors II. Algorithmic Aspects of Tree-Width. J. Algorithms, 7:309-322, 1986.]]Google Scholar
- 20.P.D. Seymour and R. Thomas. Graph Searching and a Min-Max Theorem for Tree-Width. J. of Combinatorial Theory, Series B, 58:22-33, 1993.]] Google ScholarDigital Library
- 21.J.D. Ullman. Principles of Database and Knowledge Base Systems, Vol II, Computer Science Press, Rockville, MD, 1989.]] Google ScholarDigital Library
- 22.J.D. Ullman. Information integration using logical views. Theoretical Computer Science, 239(2):189-210, 2000.]] Google ScholarDigital Library
- 23.M. Vardi. Complexity of Relational Query Languages. In Proe. of 14th ACM STOC, pp. 137-146, 1982.]] Google ScholarDigital Library
- 24.M. Vardi. Constraint Satisfaction and Database Theory. Tutorial at PODS'00. Currently available at: www.cs.rice.edu/~vardi/papers/pods00t, ps. gz.]] Google ScholarDigital Library
- 25.E. Wanke. Bounded Tree-Width and LOGCFL. Journal of Algorithms, 16:470-491, 1994.]] Google ScholarDigital Library
- 26.M. Yannakakis. Algorithms for Acyclic Database Schemes. In Proe. of Int. Conf. on Very Large Data Bases (VLDB'81), pp. 82-94, C. Zaniolo and C. Delobel Eds., Cannes, France, 1981.]]Google Scholar
Index Terms
- Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width
Recommendations
Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width
Special issu on PODS 2001In a previous paper (J. Comput. System Sci. 64 (2002) 519), the authors introduced the notion of hypertree decomposition and the corresponding concept of hypertree width and showed that the conjunctive queries whose hypergraphs have bounded hypertree ...
Marshals, monotone marshals, and hypertree-width
The tree-width of a hypergraph H equals one less than the number of cops necessary to catch the robber in the Monotone Robber and Cops Game played on H. Analogously, the hypertree-width of a hypergraph is characterised by the Monotone Robber and ...
Guards, Bounds, and Generalized Semantics
Some initial motivations for the Guarded Fragment still seem of interest in carrying its program further. First, we stress the equivalence between two perspectives: (a) satisfiability on standard models for guarded first-order formulas, and (b) ...
Comments