From Hypertree Width to Submodular Width and Data-dependent Structural Decompositions

Abstract

Identifying the frontier of tractability for conjunctive queries is a longstanding question in database theory. Recent advances in structural decomposition methods provide an important answer regarding the fixed-parameter tractability of conjunctive queries, and efficient algorithms based on decomposition methods have been implemented in database management systems. The paper shows that these techniques are useful not only for long and complex queries, but even for short and simple ones. Moreover, it sheds some light on some subtle issues that are not completely understood yet, and discuss open problems, such as the gap remaining between the theoretical fixed-parameter polynomial-time upperbound and the running times required by actual algorithms used in practice.

Introduction

Conjunctive queries are defined through conjunctions of atoms (without negation), and are known to be equivalent to Select-Project-Join queries. The problem of evaluating such queries is NP-hard in general, but it is feasible in polynomial time on the class of acyclic queries (we omit “conjunctive,” hereafter), which was the subject of many seminal research works since the early ages of database theory This class contains all queries Q whose associated query hypergraph HQ is acyclic, where HQ is a hypergraph having the variables of Q as its nodes, and the (sets of variables occurring in the) atoms of Q as its hyperedges.

In fact, queries arising from real applications are hardly precisely acyclic. Yet, they are often not very intricate and, in fact, tend to exhibit some limited degree of cyclicity, which suffices to retain most of the nice properties of acyclic ones. Therefore, several efforts have been spent to investigate invariants that are best suited to identify nearlyacyclic hypergraphs, leading to the definition of a number of so-called (purely) structural decomposition-methods [ 12,9 ], such as the tree decompositions [ 20 ] and, after some years, the (generalized) hypertree [ 7,8 ], fractional hypertree [ 15 ], component hypertree [ 11 ], and greedy hypertree [ 14,13 ] decompositions. These methods aim at transforming a given cyclic hypergraph into an acyclic one, by organising its edges (or its nodes) into a polynomial number of clusters, and by suitably arranging these clusters as a tree, called decomposition tree. The original problem instance can then be evaluated over such a tree of subproblems (in our case, subqueries), with a cost that is exponential with respect to a measure of the complexity of the subproblems, also called width of the decomposition, and polynomial if this width is bounded by some constant. For instance, according to the treewidth notion, the width of a decomposition is given by the maximum cardinality (minus one) of the set of variables occurring in the subqueries associated with the vertices of the decomposition tree. The (generalized) hypertree width considers instead the number of atoms occurring in each subproblem, in other terms, the number of hyperedges needed to cover the relevant variables in each vertex of the decomposition tree. The fractional hypertree width [ 15 ] is similar, but it is based on a fractional cover of such variables, instead of an integral one, as in the case of (plain) hypertree decompositions.

Besides the theoretical guarantees on the cost of evaluating class of queries having bounded (fractional) hypertree width, experimental evidence of the benefits gained from these structural decomposition methods in query optimization (and in the equivalent Constraint Satisfaction Problem) has been provided in the literature by a number of different authors and in different application domains, see, e.g., [ 5,6,1 ].

A yet more general width-concept is the submodular width [ 19 ], where the cost of a decomposition is determined by the worst possible submodular function of sets of variables of the given hypergraph. Recall that a set function f is submodular if, for every element x and any pair of sets S and T with S ⊆ T and x ∈/ T , f (S ∪ {x}) − f (S) ≥ f (T ∪ {x}) − f (T ) holds. That is, the marginal contribution of any element decreases when sets become larger. This powerful notion is strictly more general than all previous techniques, as there are classes of hypergraphs having bounded submodular width, but unbounded fractional hypertree width. However, having bounded submodular width (smw) does not guarantee a polynomial-time combined complexity as for hypertree decompositions, but just fixed-parameter tractability where the query hypergraph is used as a parameter. This means that we have a polynomial-time data complexity of the form O(f1(HQ) · |DB|f2(smw)), where f1 is an exponential function of the query size. Marx also proved that having bounded smw is in fact a necessary condition for the fixedparameter tractability of conjunctive queries (unless the Exponential Time Hypothesis fails) [ 19 ]. Unfortunately, it is not clear how to recognise queries of bounded submodular width. It is worthwhile noting that, unlike the previous methods, the decompositions used to answer the query depend not only on the hypergraph HQ, but on the actual database DB, too. Nevertheless, the submodular width of HQ depends only on HQ, which makes it an actual structural measure.

The primary aim of the paper is to shed light on the recent achievement in structural decomposition methods, in particular – to make clear why the powerful notion of fractional hypertree width is not able to catch the precise complexity of a given query; – to show, by using the case study of queries whose hypergraphs are simple cycles, that using data-dependent decompositions, as in the case of submodular width, provides better upper bounds on the cost of queries, and effective algorithms; – to make evident that the benefits of such sophisticated notions occur not only in long and complex queries, but even in short and simple ones, occurring in most real-world applications; – to give a hint of what is the submodular width of a query, and a hint of the problems that are still open in this area of research.

Hypertree decompositions and the AGM bound

Let H a hypergraph, and denote the set of its nodes by nodes (H) and the set of its hyperedges by edges (H). Formally, a tree decomposition [ 20 ] of H is a pair hT , χi, where T = (V, F ) is a tree, and χ is a labelling function assigning to each vertex p ∈ V a set of vertices χ(p) ⊆ nodes (H), such that the following three conditions are satisfied: (1) for each node b of H, there exists p ∈ V such that b ∈ χ(p); (2) for each hyperedge h ∈ edges (H), there exists p ∈ V such that h ⊆ χ(p); and (3) for each node b in nodes (H), the set {p ∈ V | b ∈ χ(p)} induces a connected subtree of T . The width of hT , χi is the number maxp∈V (|χ(p)| − 1). The treewidth of H, denoted by tw(H), is the minimum width over all its tree decompositions.

Hypertree Decompositions A generalized hypertree decomposition of a hypergraph H is a triple HD = hT , χ, λi, called a hypertree for H, where hT , χi is a tree decomposition of H, and λ is a function labelling the vertices of T by sets of hyperedges of H such that, for each vertex p of T , χ(p) ⊆ Sh∈λ(v) h. That is, all nodes in the χ labelling are covered by hyperedges in the λ labelling.

Consider a generalized hypertree decomposition HD =hT , χ, λi. The cyclicity measure used in standard generalized hypertree decompositions, called generalized hypertree width and denoted by ghw(H), is based on the cardinality of the set λ(p) in charge of covering χ(p), for each vertex p of the decomposition tree. Contrasted with the treewidth, which is based on the cardinality of χ(p), it is clear that ghw(H) ≤ tw(H) always holds. It has been observed that more general notions can be obtained by allowing the use of more general functions fHD(·), to measure the weight fHD(p) of any vertex of T , and hence to define the width of a hypertree decomposition.

A fractional hypertree decomposition [ 15 ] of a hypergraph H is a pair FHD = hHD , γi, where HD = hT , χ, λi is a generalized hypertree decomposition of H, and γ is a mapping associating each vertex p of T with a function γp : λ(p) 7→ R mapping hyperedges to non-negative real numbers. For each vertex p in T , γp encodes a fractional cover of the nodes in χ(p): for each v ∈ χ(p), Ph∈λ(p),v∈h γp(h) ≥ 1. Define ρ(p) = Ph∈λ(p) γp(h). The width of FHD is the maximum of ρ(p) over all vertices p in T . The fractional hypertree width of H, denoted by f hw(H), is the minimum width over all its fractional hypertree decompositions.2

Generalized hypertree width is obtained if in the definition of fractional hypertree decomposition we restrict the codomain of each γp to be integral. It is thus not surprising that there are hypergraphs where the fractional hypertree width is smaller than the (generalized) hypertree width.

The additional power of fractional covers in the decomposition vertices makes the problem intractable, in general. Indeed, for a given hypergraph H and for any fixed w ≥ 2, computing a hypertree decomposition of width at most w (if any) is feasible in polynomial-time, while checking whether H has fractional hypertree width at most w is NP-hard [ 4 ]. However, there is a polynomial-time algorithm for deciding whether the fractional hypertree width is f (w) for a function f in O(w3) [ 18 ]. 2 The equivalent (original) definition in [ 15 ] does not use the λ-labeling, so that γp weighs all hyperedges. Our definition is used, e.g., in [ 1 ].

Query evaluation Queries whose (fractional) hypertree width is bounded by some constant k can be answered in polynomial time. Given a query Q and a hypertree decomposition HD for the query hypergraph HQ, the query can be transformed into an acyclic query, based on the decomposition HD . Each vertex of the decomposition tree can be viewed as a subproblem to be solved: in our database context, such a vertex p is associated with a subquery Qp whose atoms are the atoms in λ(p), and whose set of output variables is χ(p). By computing the answers of these subqueries, we obtain an acyclic query equivalent to Q that can be evaluated easily, by standard techniques. Equivalently, we can see this transformation as a query plan for Q (where some atoms can appear multiple times with different projections, if necessary). The crucial observation here is that the maximum number of answers of the subquery Qp associated with each vertex p is at most |rp|ρ(p), where rp is the largest database relation associated with the hyperedges in λ(p) [ 15,3 ]. Moreover, such answers can be efficiently computed within this upper bound [ 1 ].

Tight Bounds The so-called AGM bound [ 3 ] states that, in fact, the upper bound on the number of solutions at each subproblem Qp provided by the best fractional cover ρ∗ is tight: there exists some database DB such that the number of answers of Qp over this database meets the fractional cover upper bound. This result has been refined in [ 10 ], where a bound based on the so-called coloring number C(Qp) of such a query is defined, in order to take into account the output variables, as well as certain kinds of functional dependencies.

It follows that, whenever the fractional hypertree width of a query Q is w, and we have any fractional hypertree decomposition of width w, there always exists a database DB such that evaluating the subproblem Qp at some vertex p of the decomposition tree requires Ω(N w) time, where N is the size of the largest relation occurring in Qp. Yet, from the results based on the submodular width, it turns out that we could do much better. How is that possible? 3

When worst cases are unachievable

In this section, we show that fractional hypertree decompositions do not provide a tight bound on the cost of evaluating conjunctive queries. This is not very clear, at a first sight, because of the results mentioned in the previous section. However, we see that even in very simple queries the worst cases predicted by fractional hypertree width are impossible to achieve.

Let us start with a hint of what happens. Consider a conjunctive query q with an associated hypergraph Hq having fhw (Hq) = k, and let HD be a width-k fractional hypertree decomposition for q. Let v be a vertex of HD whose associated subproblem has a fractional cover of weight k. Then, there exists a database DB such that solving this subproblem takes at least O(nk) time. However, it is possible that there exists another decomposition HD ′ with no subproblem having such an evaluation cost over this specific database DB. In its turn, HD ′ will have a critical database DB′ for which some of its subproblems require O(nk) time. But DB′ is not necessarily a bad case for the previous decomposition HD . Therefore, it is possible that, for the given query q, for every database DB there is a fractional hypertree decomposition where any subproblem occurring in its vertices can be evaluated in less than O(nk) time.

As a case study of this phenomenon, we investigate the class of conjunctive queries whose associated hypergraphs are (simple) cycles. These queries have (fractional) hypertree width 2, but they can be actually evaluated in subquadratic time on any given database.

A simple example: the cycles First, consider the following simple cyclic query q4, whose (hyper)graph G4 is shown in Figure 1:

ans(X¯ ) ← r1(X1, X2) ∧ r2(X2, X3) ∧ r3(X3, X4) ∧ r4(X4, X1).

Consider the decomposition of this graph in the center of Figure 1, which involves subproblems such as r1(X1, X2) ∧ r2(X2, X3) and r3(X3, X4) ∧ r4(X4, X1) having a fractional cover of weight 2. It follows that there exists a database DB4 such that, e.g., the subquery ans(X1, X2, X3) ← r1(X1, X2) ∧ r2(X2, X3) has O(N 2) answers, where for the sake of simplicity we assume that the relations are the same and that they have N tuples each.

Think now of how this worst-case bound can be achieved. First assume that ri is a cartesian product of the domain of its variables: we have N = |d(X1)| · |d(X2)| so that |d(X1)| = N 1/2. Because ans(X1, X2, X3) cannot be larger than the cartesian products of the domain of its variables, it follows that, in this case, |ans(X1, X2, X3)| ≤ N 3/2. In order to reach the worst-case bound of N 2, in DB4 the attributes should have quite different domain sizes. In particular, we must have many values on the extremal variables of the chain X1, X2, X3, that is, almost N values for X1 and X3, and a few values for X2. For instance, X2 may have just one skew value that is connected to all values for X1 and X3, so that ans(X1, X2, X3) = d(X1) × 1 × d(X3) and |ans(X1, X2, X3)| = N 2. For completeness, note that if X2 has many values, say almost N , than it should behave like a key, and the size of ans(X1, X2, X3) will be almost linear in N . Summing-up, to achieve the O(N 2) worst-case bound on ans(X1, X2, X3), we should have |d(X2)| = Δ, with Δ much smaller than N . However, in this case we can use the decomposition shown on the right in Figure 1: note that the subproblems in the vertices of this decomposition have at most N Δ answers, achieved in the vertices in the middle where we have a cartesian product of the form ri × d(X2). The cost of evaluating q4 over DB4 using this decomposition is thus O(N Δ), which is smaller than the O(N 2) cost predicted by fractional hypertree width.

We next show that the above reasoning can be generalized to any database, showing that the quadratic fractional hypertree-width worst-case is not tight, in particular such a query can be evaluated in O(N 3/2), that is, within the same bound as the triangle query. A general bound for evaluating cycles Following the intuition described in the previous section, we next show that actually we can guarantee a subquadratic evaluation time for every conjunctive query having a cycle as its hypergraph and on any given database. A further ingredient to obtain a precise upper bound is to consider horizontal fragments of the relations, and possibly use different decompositions for evaluating the given query on different fragments. Therefore, not only we look for the best decomposition with regard to specific database, but also the best ones for different fragments of the database.

This bound is a slight improvement of the upper bound described in [ 16 ] and it is quite similar to the upper bound given in [ 2 ] for the special case of queries asking for length-k simple cycles in graphs, whose techniques are indeed used both in [ 16 ] and X1 X4

X2 X3 r1(X1, X2) ∧ r2(X2, X3)

r4(X4, X1) ∧ r2(X2, ) r3(X3, X4) ∧ r4(X4, X1) r3(X3, X4) ∧ r2(X2, ) r2(X2, X3) in the present paper. Contrasted with this latter upper bound, our result is more general because it works with queries involving any combination of arbitrary binary relations, while the results on graphs assume only one relation (the edge relationship of the input graph).

Theorem 1. Let C be any class of conjunctive queries whose associated hypergraphs are (simple) cycles. Then, the answers of1any query i1n C having k atoms on a database of size N can be computed in O((2/k) ⌈k/2⌉ · N 2− ⌈k/2⌉ + OUT), where OUT is the size of the output.

Proof. Consider the following query qk ∈ C over a database DBk of size N¯ : ans(X¯ ) ← r1(X1, X2) ∧ r2(X2, X3) ∧ · · · ∧ rk(Xk, X1), where r1, . . . , rk are binary relation symbols, not necessarily distinct, and for each i ∈ [k], ri has Ni tuples. Its associated hypergraph Gk is a simple cycle having k vertices and k edges, and both hw(Gk) = 2 and f hw(Gk) = 2 holds.

Let δ > 0 be a number that will be determined later. For each i ∈ [k], let ri′ ⊆ ri be the (horizontal) fragment of ri consisting of the tuples {hv, v′i ∈ ri | v occurs in more than δ tuples in ri}. Let qi′ be the variant of query qk where the atom ri(Xi, Xi+1) is replaced by ri′(Xi, Xi+1), and consider a hypertree decomposition for qi′ of the form shown on the right in Figure 1, with Xi playing the role of X2. Note that the number of tuples in the projection ri′(Xi, ) occurring in the decomposition vertices is at most Ni/δ, so that qi can be evaluated in O(N¯ Ni/δ + OUTi). The OUTi answers of this modified query are all those answers of qk such that Xi is instantiated with any value of its domain having degree at least δ (if any). After the evaluation of all such modified queries, we get all the OUTδ answers of qk over DBk where some variable takes a value having degree at least δ. The total time used for such computations is O(N¯ N¯ /δ + OUTδ). Note that, having these answers, each domain value having degree at least δ is no longer needed in any relation.

Then, we take care of the remaining fragment: consider the query qk′′: ans′′(X¯ ) ← ′′ r′′(X1, X2) ∧ r′′(X2, X3) ∧ · · · ∧ r′′(Xk, X1) over the database DBk with the relations ri1′′ = ri \ ri′, fo2r each i ∈ [k]. Wekevaluate this query by using a tree decomposition of the form shown in the center of Figure 1 with two big vertices, each one covering half of the query. The width w of this decomposition is ⌈k/2⌉. Let rs and rt be the smallest relations in the database DB′k′, having number of tuples Nr and Nt, respectively. We can always choose the decomposition in such a way that rs and rt occur in different vertices. Consider now the evaluation of the subproblem comprising the relation rs: because every value has degree at most δ, every tuple of rs can have at most δ extensions to tuples in the subsequent relation in the subproblem, say rz ; the same happens for every tuple in rz , and so on for all the atoms in this subproblem. The evaluation of these atoms takes O(Nsδw−1) time and, similarly, we need O(Ntδw−1) to evaluate the subproblem occurring in the other vertex of the decomposition, for a total cost of O((Ns + Nt)δw−1). Because rs and rt are the smallest relations, it can be seen easily that (Ns + Nt) ≤ 2N¯ /k, so that the total cost for evaluating qk′′ over DB′k′ using such a decomposition is O(2δw−1N¯ /k + OUT′′), where OUT′′ is the size of the output relation ans′′(X¯ ). By equating the cost of using the two kinds of decompositions, we can compute the value δ = (k/2N¯ )1/w that guarantees that we obtain the same evaluation cost for either kind of fragment and for every possible input database. With this value, the total cost for evaluating qk on any given database DBk of size N¯ is O((2/k)1/wN 2−1/w + OUT), where OUT is the size of the output relation ans(X¯ ). ⊔⊓ 4

Discussion and Open problems

Recent advances have shown that powerful structural decompositions such as the (fractional) hypertree width or the submodular width may lead to effective algorithms even for very simple queries, and not just for long and complex ones (possibly involving atoms with large arities), which have been the typical targets for these sophisticated techniques. Moreover, we have seen that the worst case upper bounds of the so-called purely structural decomposition methods, where the choice of the decomposition depends only on the query hypergraph, are not tight.

Contrasted with such methods, the notion of submodular width, which is based on data-dependent decompositions, is more powerful and in fact characterises the frontier of fixed-parameter tractability for conjunctive queries. The algorithm used in [ 19 ] is based on the computation of almost uniform horizontal fragments of all possible subproblems that can be evaluated in polynomial-time. Very roughly, uniform means here that, in each fragment and for any subset of variables of a subproblem, partial solutions over these variables extend to full solutions of the subproblem in a similar way. Whenever a subproblem does not meet this condition, it can be split in more subproblems leading to new fragments. The subproblems of each new instance associated with a fragment are kept locally consistent. That is, tuples that are not useful in that fragment are filtered out, and the procedure continues looking for new small, consistent and uniform subproblems to deal with. This procedure works in fixed-parameter polynomial time, where the parameter is the size of the query. Eventually, under the promise that the submodular width is below some fixed threshold w (which is used to define precisely the above process), there should exist some tree decomposition whose subproblems are among those that we have computed. Furthermore, whenever for an instance associated with some fragment its subproblems are not empty, because they are pairwise consistent we can conclude that the given query has some answer on the input database; otherwise, we conclude that there are no answers (see also [ 14 ] for such consistency properties).

Marx’s algorithm is quite involved and its actual cost is quite high even for queries with a few variables. The PANDA algorithm described in [ 17 ] aims at obtaining a similar worst case bound, but is more suitable to effective implementations. However, because of its different uniformization procedure, its cost involves a (log n)h factor, where h is the number of atoms in the query, which is not allowed in fixed-parameter polynomial time algorithms (the parameter cannot occur as the exponent of a number that depends on the input size). In fact, it is still open whether or not such a bad factor can be avoided, so that an effective fixed-parameter polynomial time algorithm can be implemented. An algorithm for computing the submodular width of a given hypergraph is also missing, as well as a possible approximation of this notion. Furthermore, the frontier of polynomial-time tractability for conjunctive queries involving atoms of arbitrary arities is still unknown, and it is even unknown whether it can actually be charted or not.

References

1. Aberger , C.R. , Lamb , A. , Tu , S. , No¨tzli, A. , Olukotun , K. , Re´, C. : Emptyheaded: A relational engine for graph processing . ACM TODS 42(4) , 20 : 1 - 20 : 44 ( 2017 ).

2. Alon , N. , Yuster , R. , Zwick , U. : Finding and counting given length cycles . Algorithmica 17 ( 3 ), 209 - 223 ( 1997 ).

3. Atserias , A. , Grohe , M. , Marx , D. : Size bounds and query plans for relational joins . SIAM J. on Comp . 42 ( 4 ), 1737 - 1767 ( 2013 )

4. Fischl , W. , Gottlob , G. , Pichler , R.: General and fractional hypertree decompositions: Hard and easy cases . In: Proc. of PODS'18 ( 2018 )

5. Ghionna , L. , Granata , L. , Greco , G. , Scarcello , F. : Hypertree decompositions for query optimization . In: Proc. of ICDE'07 . pp. 36 - 45 ( 2007 )

6. Ghionna , L. , Greco , G. , Scarcello , F.: H-DB : A Hybrid Quantitative-structural SQL Optimizer . In: Proc. of CIKM '11 . pp. 2573 - 2576 ( 2011 )

7. Gottlob , G. , Leone , N. , Scarcello , F. : Hypertree decompositions and tractable queries . JCSS 64 ( 3 ), 579 - 627 ( 2002 )

8. Gottlob , G. , Leone , N. , Scarcello , F. : Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width . JCSS 66 ( 4 ), 775 - 808 ( 2003 )

9. Gottlob , G. , Greco , G. , Scarcello , F. : Treewidth and hypertree width . In: Tractability: Practical Approaches to Hard Problems, pp. 3 - 38 . Cambridge University Press ( 2014 ).

10. Gottlob , G. , Lee , S.T. , Valiant , G. , Valiant , P. : Size and Treewidth Bounds for Conjunctive Queries . J.ACM 59 ( 3 ), 1 - 35 ( 2012 )

11. Gottlob , G. , Miklo´s, Z. , Schwentick , T. : Generalized hypertree decompositions: NP-hardness and tractable variants . J.ACM 56 ( 6 ), 30 : 1 - 30 : 32 ( 2009 )

12. Greco , G. , Leone , N. , Scarcello , F. , Terracina , G. : Structural decomposition methods: Key notions and database applications . In: A Comprehensive Guide Through the Italian Database Research Over the Last 25 Years ., Studies in Big Data , vol. 31 , pp. 253 - 267 . Springer

13. Greco , G. , Scarcello , F. : Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems . Inf. Comput . 252 , 201 - 220 ( 2017 ).

14. Greco , G. , Scarcello , F. : The power of local consistency in conjunctive queries and constraint satisfaction problems . SIAM J. Comput . 46 ( 3 ), 1111 - 1145 ( 2017 ).

15. Grohe , M. , Marx , D. : Constraint solving via fractional edge covers . ACM Trans. on Alg . 11 ( 1 ), 4: 1 - 4 : 20 ( 2014 )

16. Joglekar , M. , Re´, C. : It's all a matter of degree - using degree information to optimize multiway joins . Theory Comput. Syst . 62 ( 4 ), 810 - 853 ( 2018 ).

17. Khamis , M.A. , Ngo , H.Q. , Suciu , D. : What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In: Proc. of PODS 2017 , pp. 429 - 444 .

18. Marx , D. : Approximating fractional hypertree width . ACM T. on Alg . 6 ( 2 ), 29 : 1 - 17 ( 2010 )

19. Marx , D. : Tractable hypergraph properties for constraint satisfaction and conjunctive queries . J.ACM 60 ( 6 ), 42 : 1 - 42 : 51 ( 2013 )

20. Robertson , N. , Seymour , P. : Graph minors . II. Algorithmic aspects of tree-width . J. of Alg . 7 ( 3 ), 309 - 322 ( 1986 )