2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ RE: "the hypothesis of bounded arity does not hold", I would think the motivation is more justified from query perspective (I don't have problem with CSP part) by stating we are trying to understand the impact of arity on the query evaluation complexity (as one of your points). $\endgroup$
    – xxks-kkk
    Mar 28 at 22:32
  • $\begingroup$ In terms of arity, there are two levels of meanings. If one states unbounded arity of a relation leads to unbounded treewidth, I would argue that's false because relation, by definition, is a finite structure,i.e., sort associated with relation is finite [1]. On the other hand, if one states that a query can have unbounded arity (number of variables in a query), that's true because number of relations in a query can be unbounded. Thus, $\mathcal{C}$ is not a good example in my view. $\endgroup$
    – xxks-kkk
    Mar 28 at 22:34
  • $\begingroup$ Thus, I would think finding a query class with unbounded treewidth is not possible due to the definition of relation. The construction $\mathcal{C}$ contradicts to my understanding on relation. However, is it possible to find a query class with arity of each relation is bounded and at the same time, the treewidth is unbounded (such query class can have unbounded number of relations and thus, number of variables)? $\endgroup$
    – xxks-kkk
    Mar 28 at 23:03
  • $\begingroup$ There seems to be a huge misunderstanding of the objects. If you fix the instance, everything is bounded. Unboundedness is only possible when looking at families of objects; unbounded arity for a (infinite) family of relations means that the maximal arity of relations in the family is unbounded. Same with treewidth of a family of queries. We have: unbounded arity of a family => unbounded treewidth. The other way around is false: $Q_n := \bigwedge_{i<j\leq n} E(x_i,x_j)$ has bounded arity (2) and $Q_n$ has treewidth $n$ (it is a clique!) thus the family $(Q_n)_n$ has unbounded treewidth. $\endgroup$
    – holf
    Mar 29 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.