This paper presents the first in-depth discussion of rerootability in hypertree decompositions, and defines a relaxed notion of normal form which leads to a truly rerootable and tractable class.
Abstract
Hypertree decompositions are a cornerstone in the theory of answering conjunctive queries efficiently. However, they are not yet widely adopted in practice. Problems related to, e.g., the uniqueness of decompositions and succinct representations of all decompositions have so far mostly been neglected by the theory literature. In this paper, we present the first in-depth discussion of rerootability in hypertree decompositions---a property which we argue is essential for such problems. Rerootability leads us to projection-freeness, and we have to discuss normal form to recover tractability. Normal form, however, again obstructs rerootability, and for this reason, we define a relaxed notion of normal form which leads to a truly rerootable and tractable class. Experimental evidence suggests that the price we pay in terms of width increase for transitioning to this class of decompositions is moderate in practice.
This paper combines Qdags with a Generalized Hypertree Decomposition of the query, into subqueries with fewer variables, and implements algorithms that find the optimal GHD according to the AGM bounds of the subqueries and the specificities of the Qdag cost model.
Diego Arroyuelo, Gabriel Carmona, Gonzalo Navarro et al.· 0 citations
We present Guanaco, an algorithm for performing conjunctive query evaluation where, for each Boolean conjunctive query, and positive epsilon, the algorithm achieves polynomial time with exponent equal to the submodular width plus epsilon. The algorithm and its running time generalize smoothly to general conjunctive que...
Over the past several years, numerous authors have explored model theoretically motivated combinatorial conditions that ensure that a graph has an efficient regular decomposition in the sense of Szemerédi. In this paper we set out a research program that explores a corresponding set of questions for 3-uniform hypergrap...
C. Terry, J. Wolf· Memoirs of the American Math...· 0 citations
In this paper, the parameterized complexity of the multiplicative $\alpha$-spanner problem with independent weights and lengths on undirected graphs is considered for the first time. All prior FPT results (except one on DAGs) assume basic instances (i.e., with unit weights and lengths) and are parameterized in the stre...
Marius Bächler, Markus Chimani, Henning Jasper· 0 citations
In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameters d1≤d2, there exists a coupling of G(n,d1) and G(n,d2) satisfying that G(n,d1)⊆G(n,d2) with high probability, confirming a conjecture of Ga...
Lawrence Hollom, Lyuben Lichev, Adva Mond et al.· The Annals of Applied Probab...· 0 citations
We prove that, whenever $ p \ge n^{-1/2 + o(1)} $, with high probability $ G(n, p) $ admits a fractional triangle decomposition, that is, a non-negative weight function on its triangles for which the total weight of all triangles containing each edge is equal to 1. This bound on $ p $ is optimal up to the asymptotic er...
Felix Joos, Zak Smith· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
