On motivation towards study of width parameters beyond treewidth

Question

Many width parameters are invented to capture the tractability of CSP (and its equivalent problem, conjunctive queries (CQ) evaluation): treewidth, hypertree width, generalized hypertree width, fractional hypertree width, submodular width. Every width parameter besides treewidth seems to be motivated by the $V(H)$ can be unbounded given $H = (V(H),E(H))$ being a hypergraph representation of a problem instance, i.e., treewidth of $H$ can become unbounded but the problem instance with $H$ can be evaluated in polynomial-time. In other words, a class of hypergraphs with bounded treewidth fails to capture all the tractable problem instances. I can imagine this works for CSP where an arity of constraint can be unbounded but it's hard for me to imagine this assumption holds for conjunctive queries, which essentially suggests that an arity of a relation can be unbounded, which contradicts with the general assumption [1].

My question is

When does bounded treewidth fail to capture all tractable CQs? Is there any example? Such example (query) needs to have bounded arity of each relation appearing in the query and at the same time, the treewidth is unbounded.

One example, described in CSP, is given in [2] at the end of section 2. Translated into query context, effectively, it says that for a query with one relation, $R$, if arity of $R$ goes to $\infty$, associated $H$ has unbounded treewidth but it can be evaluated polynomial-time: we just simply return $R$ as the query result (Please correct me if I understand wrong). Thus, this specific example does not address my question. Gottlob et al. [3] mention the following in the paper "Each query having treewidth $k$ or degree of cyclicity $k$ has also query width $\le k$, but for some queries the converse does not hold [9, 18]. There are even classes of queries with bounded query width but unbounded treewidth." However, I haven't been able to find such query with unbounded treewidth but bounded hypertree width (or a closely-related query width) in the cited references of the sentence.

[1] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases, volume 8. Addison-Wesley Reading, 1995.

[2] Martin Grohe and Dániel Marx. Constraint Solving via Fractional Edge Covers. ACM Transactions on Algorithms (TALG), 11(1):1–20, 2014.

[3] Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree Decompositions and Tractable Queries. Journal of Computer and System Sciences, 64(3):579–627, 2002.

[9] Ch. Chekuri and A. Rajaraman. Conjunctive Query Containment Revisited. In Proc. International Conference on Database Theory 1997 (ICDT’97), Delphi, Greece, Jan. 1997, Springer LNCS, Vol. 1186, pp.56-70, 1997.

[18] G. Gottlob, N. Leone, and F. Scarcello. The Complexity of Acyclic Conjunctive Queries. Technical Report DBAI-TR-98/17, available on the web as: http://www.dbai.tuwien.ac.at/staff/gottlob/acyclic.ps, or by email from the authors. An extended abstract concerning part of this work has been published in Proc. of the IEEE Symposium on Foundations of Computer Science (FOCS’98), pp.706-715, Palo Alto, CA, 1998.

Answer 1

It is not hard to see that if a class of queries has arity bounded by $a$ and hypertree width bouded by $k$, then it will also have treewidth bounded by $a\cdot k$. Indeed, any bag in a hypertree decomposition of a query of width $k$ is covered by at most $k$ atoms of the query, each of them having arity at most $k$. Thus any bag of the decomposition contains less than $a \cdot k$ vertices.

The case for unbounded arity is different. The example you cite roughly boils down to the following: consider a query $Q_n := R_n(x_1, \dots, x_n)$ having exactly one atom of arity $n$. It is not hard to see that $Q_n$ has treewidth $n$ since you need a bag to cover $R_n$. But clearly, answering $Q_n$ is completely trivial. Hence the class $\mathcal{C} := \{Q_n \mid n \in \mathbb{N}\}$ has unbounded treewidth but is tractable.

As a matter of fact $Q_n$ is acyclic and, in other words, it has hypertree width $1$, which answers your questions concerning finding a class of queries having unbounded treewidth but bounded hypertree width.

Now you argue that the hypothesis of bounded arity does not hold. I do not understand what you mean by this. I agree that if you fix a query, its arity is bounded but the reasoning here is that we consider classes of queries, which may have unbounded arity (as $\mathcal{C}$).

Now if you mean that bounded arity is not a realistic real life scenario, let me point out two things. First of all, one goal of these measures is to understand and pinpoint the theoretical complexity of the problem of answering CQ. In this case, one does not really care about whether it is a pratical assumption or not.

However, I would argue that these classes of queries have practical use. Arity is a lower bound on the treewidth and one can easily find practical data schemas with arity bigger than 20. Having an exponential dependency on the arity in the constants is far from optimal.

On the other hand, it is known from Yannakakis [Yannakakis, 81] that acyclic queries can be answered in linear time in the size of the database, the constants involved being independent from the arity of the query, something that is not captured by results working on the treewidth of the query directly. Hypertree width related measures hence have a much more realistic approach of databases. A join tree can be seen as way of performing the joins to ensure that intermediate steps remain bounded.

Rererences

[Yannakakis, 81] Yannakakis, M. (1981, September). Algorithms for acyclic database schemes. In VLDB (Vol. 81, pp. 82-94).