Soft and Constrained Hypertree Width

Hypertree decompositions provide a way of making Conjunctive Queries (CQs) and Constraint Satisfaction Problems (CSPs) efficiently solvable, by identifying ways to decompose them into small subproblems that can be combined efficiently. In practical settings, these small subproblems might still be problematic to solve, even when the width of the decomposition is low. For example, if the cover of some part of the decomposition for a CQ is not connected, this induces the computation of full Cartesian products over database relations when evaluating the query using the decomposition. It is therefore of interest to impose constraints on decompositions. We utilise the framework of candidate tree decompositions, introduced by Gottlob, et al. (J.ACM, 2021), to introduce soft hypertree width. This novel measure is a tractable relaxation of hypertree width that provides more algorithmic flexibility as well as lower width over hypertree width. We show that this improvement over hypertree width is arbitrarily high and that soft hypertree width admits a natural game characterisation. Moreover, an iterated version of soft hypertree width induces a hierarchy of width measures whose transfinite closure equals generalised hypertree width. On the basis of soft hypertree decompositions we initiate the study of computing hypergraph decompositions under constraints. We show for large general classes of constraints that the problem of computing a constraint soft hypertree decomposition is still tractable.