=Paper=
{{Paper
|id=Vol-2369/short01
|storemode=property
|title=Semantic Width Revisited (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-2369/short01.pdf
|volume=Vol-2369
|authors=Georg Gottlob,Matthias Lanzinger,Reinhard Pichler
|dblpUrl=https://dblp.org/rec/conf/amw/GottlobLP19
}}
==Semantic Width Revisited (Extended Abstract)==
https://ceur-ws.org/Vol-2369/short01.pdf
Semantic Width Revisited (Extended Abstract)
Georg Gottlob1,2 , Matthias Lanzinger1 , and Reinhard Pichler1
1
TU Wien, Austria,
2
University of Oxford, UK
{gottlob, mlanzing, pichler}@dbai.tuwien.ac.at
1 Introduction
Answering conjunctive queries (CQ) and, equivalently, solving constraint sat-
isfaction problems (CSP), are among the most fundamental tasks in computer
science. While these problems are NP-complete, there has been much success in
identifying “islands of tractability”. In this work, we want to further sharpen the
image of this complexity landscape. In particular, we are interested in extend-
ing the pioneering work by Barceló, Pieris, Romero, and Vardi [1, 2], Dalmau,
Kolaitis, and Vardi [4], and Grohe [6] on the deep connections between query
minimization and structural decompositions. To this end, the following notion
of semantic widths will be the central theme of our work. Note that from now
on, we only concentrate on CQs. Clearly, all results hold for CSPs as well.
Definition 1. Let Q be the class of all conjunctive queries and w : Q → R+ be
some property of the query. We define semantic w as sem-w(q) := inf{w(q 0 ) |
q 0 ' q}, where ' denotes homomorphic equivalence.
Such semantic widths can be interpreted as measures of the inherent structural
complexity of the underlying question posed by the query, whereas classical
notions of width express the complexity of a specific way to pose the question.
So far, semantic notions of acyclicity [2], treewidth (tw ) [4], and (generalized)
hypertree width (hw and ghw , resp.) [1] have been investigated, while more pow-
erful notions of width such as fractional hypertree width (fhw ) [7], submodular
width (subw ) [9], and adaptive width (adw ) [8] have been left unexplored. The
goal of this work is to study semantic notions also of fhw , adw , and subw . Re-
call that the semantic notions of acyclicity, tw , and ghw can be characterized in
terms of the core of the CQ. This naturally raises the question if such a char-
acterization is also possible for fhw , subw , and adw . We will give an affirmative
answer which, structurally, looks very similar to the previous results. However,
some additional machinery will be needed to prove our new results.
In [9], subw was introduced to provide an in some sense “complete” char-
acterization of the fixed-parameter tractability (FPT) of CQ Evaluation. Our
investigation of the semantic version of subw will provide new input for such an
FPT-characterization. More specifically, our new notion of sem-subw will allow
us to identify an FPT-fragment of CQ Evaluation which is strictly bigger than
the fragment defined via subw in [9].
2 G. Gottlob, M. Lanzinger, R. Pichler
Strongly related to the search for (fixed-parameter) tractable fragments of
CQ Evaluation is the complexity of the Check problem which, for given integer
k ≥ 1, is about deciding if a given CQ has width ≤ k. Among the width notions
mentioned above, this problem is tractable for tw and hw and NP-complete for
ghw and fhw . For subw and adw , the complexity is expected to be even higher.
When moving to semantic notions, the computation of the core introduces a
further source of intractability. In case of ghw and fhw , several structural prop-
erties of the hypergraph underlying a CQ have been identified recently [5] to
make the Check problem tractable. We will show that these properties may
also be helpful for the computation of the semantic variants of ghw and fhw .
2 Preliminaries
We assume the reader to be familiar with basic concepts such as conjunctive
queries (CQs) and their associated hypergraphs. We implicitly extend proper-
ties of hypergraphs to CQs through their associated hypergraphs. Due to space
limitations, we refer to [9] for definitions of the fractional cover number (ρ∗ ),
generalized hypertree width (ghw), fractional hypertree width (f hw), adaptive
width (adw), and submodular width (subw).
We are mainly interested in two computational problems here. The first one
is the usual query evaluation problem for a class of CQs Q, which we denote as
Eval(Q). The decision problem of checking, whether a query has width ≤ k for
width notion w, will be referred to as Check(w, k).
The problem Check(w, k) with w ∈ {ghw , fhw } has been shown NP-complete
even for k = 2 [5]. On the positive side, also tractable fragments of this problem
have been identified in [5] via the following hypergraph properties: for a hyper-
graph H, the c-multi-intersection width of H refers to the maximum cardinality
of an intersection of any c distinct edges. For the special case c = 2, we simply
use the term intersection width. The degree of H is the maximum number of
edges a vertex of H occurs in. The rank of H is the maximum edge size in H.
3 Results
The following theorem is the basis of all our further considerations:
Theorem 1. For every conjunctive query q:
1. sem-ρ∗ (q) = ρ∗ (Core(q))
2. sem-f hw(q) = f hw(Core(q))
3. sem-adw(q) = adw(Core(q))
4. sem-subw(q) = subw(Core(q))
An interesting consequence of Theorem 1 is that bounded semantic width
of a class Q of CQs, for the notions of width enumerated in the theorem, im-
plies FPT of the Eval(Q) problem when parameterized by the query. This
is due to the fact that core computation only depends on the query (not the
Semantic Width Revisited 3
data). This is of particular interest in the case of bounded sem-subw, because
it properly generalizes bounded submodular width, and as such “escapes” the
FPT-characterization theorem of Marx [9]. To see that the generalization is in
fact proper, consider the class of “grid queries” QGn , such that QGn asks if
a given undirected graph contains a grid of size ≥ n. The core of query QGn
simply asks for the existence of a single (undirected) edge. However, the asso-
ciated hypergraphs of the family (QGn )n≥1 include grids of every dimension.
Hence, (QGn )n≥1 has unbounded treewidth. By considering the fractional in-
dependent set where every vertex has weight 1/rank (H), we get the inequality
subw(H) ≥ adw(H) ≥ (tw (H) + 1)/rank (H). It is then clear that QGn has
unbounded subw , which is in sharp contrast to sem-subw(QGn ) = 1.
Corollary 1. Let Q be a class of CQs. Then bounded sem-f hw, sem-subw, and
sem-adw are sufficient conditions for the fixed-parameter tractability of Eval(Q)
(parameterized by the query). Furthermore, they properly subsume bounded fhw ,
subw , and adw , respectively.
In [5], it was shown that the Check problem of ghw and fhw becomes
tractable if the underlying hypergraphs satisfy certain properties such as bounded
(multi-)intersection width, bounded degree, and/or bounded rank. Note that all
these properties are hereditary in the sense that deletion of vertices and/or edges
from a hypergraph does not destroy these properties. Thus, using Theorem 1, we
can directly identify tractable fragments of Check for sem-ghw and sem-f hw.
We present Corollary 2 as an illustrative example for various similar results.
Corollary 2. For a constant k > 0, let Q be a class of conjunctive queries with
bounded fractional hypertree width and bounded degree, then Check(sem-f hw, k)
is tractable in Q.
There exist classes with bounded fhw but unbounded ghw [7]. However, little
is known about the conditions under which this can occur. We show that for
classes with either bounded degree or bounded intersection width, the properties
of bounded fhw and bounded ghw (and, therefore, also bounded hw ) in fact
coincide. Furthermore, since sem-f hw and sem-ghw(cf. [1]) are characterized by
the width of the core, it is easy to generalize the result to the semantic case. As a
direct consequence, the promise algorithm presented by Chen and Dalmau in [3]
can be adapted to classes with bounded sem-f hw and either bounded degree or
bounded intersection width, making evaluation of these classes tractable.
Theorem 2. Let q be a conjunctive query and let its associated hypergraph have
degree d and intersection width i. The following statements hold:
– f hw(q) ≤ ghw(q) ≤ d f hw(q) (Implicit in [5])
– sem-f hw(q) ≤ sem-ghw(q) ≤ d sem-f hw(q)
– f hw(q) ≤ ghw(q) ≤ 2i f hw(q)2 + 2 f hw(q)
– sem-f hw(q) ≤ sem-ghw(q) ≤ 2i sem-f hw(q)2 + 2 sem-f hw(q)
4 G. Gottlob, M. Lanzinger, R. Pichler
4 Conclusion
So far, we have given a characterization of the semantic variants of ρ∗ , f hw, adw,
and subw. From this we are able to derive new insights into the complexity of
CQs. Figure 1 illustrates our current view of the complexity landscape of CQs.
Many consequences of Theorem 1 are yet to be explored. Of particular in-
terest is the role of sem-subw. Marx has shown that bounded subw characterizes
those hypergraphs for which evaluation of the associated CQs is fixed-parameter
tractable [9]. The natural next step is to characterize precisely those CQs for
which the evaluation is fixed-parameter tractable. Semantic submodular width
is a natural candidate step in this direction but the question whether it provides
a necessary condition for fixed-parameter tractable CQ evaluation remains an
important open problem for future work.
sem-subw
sem-adw
sem-f hw
subw
adw
sem-ghw Check & Eval tractable
sem-f hwBIP f hw
sem-f hwBDP Check hard
ghw Eval tractable
tw, hw
ghwLogBMIP
Eval FPT
f hwBDP
Fig. 1. CQ Complexity Landscape. Contributions presented in this paper are under-
lined. We write wP to denote a width notion w on classes constrained to a property P
where P is one of bounded degree (BDP), bounded intersection (BIP), or logarithmi-
cally bounded multi-intersection (LogBMIP).
Acknowledgements This work was supported by the Austrian Science Fund
(FWF):P30930-N35.
References
1. Barceló, P., Pieris, A., Romero, M.: Semantic optimization in tractable classes of
conjunctive queries. SIGMOD Rec. 46(2), 5–17 (Sep 2017)
2. Barceló, P., Romero, M., Vardi, M.Y.: Semantic acyclicity on graph databases. SIAM
Journal on Computing 45(4), 1339–1376 (2016)
3. Chen, H., Dalmau, V.: Beyond hypertree width: Decomposition methods without
decompositions. In: Proc. CP 2005. pp. 167–181. Springer (2005)
Semantic Width Revisited 5
4. Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth,
and finite-variable logics. In: Proc. CP 2002. pp. 310–326. Springer (2002)
5. Fischl, W., Gottlob, G., Pichler, R.: General and fractional hypertree decomposi-
tions: Hard and easy cases. In: Proc. PODS 2018. pp. 17–32. ACM (2018)
6. Grohe, M.: The complexity of homomorphism and constraint satisfaction problems
seen from the other side. Journal of the ACM (JACM) 54(1), 1 (2007)
7. Grohe, M., Marx, D.: Constraint solving via fractional edge covers. ACM Trans.
Algorithms 11(1), 4:1–4:20 (2014)
8. Marx, D.: Tractable structures for constraint satisfaction with truth tables. Theory
of Computing Systems 48(3), 444–464 (2011)
9. Marx, D.: Tractable hypergraph properties for constraint satisfaction and conjunc-
tive queries. Journal of the ACM 60(6), 42 (2013)