We study the tractability of conjunctive query answering for queries with unbounded arity. It is well known that tractability of the problem can be characterised in terms of the queries treewidth under the assumption of bounded arity. We extend this result to cases with unbounded arity but degree 2. To do so, we introduce hypergraph dilutions as an alternative method to primal graph minors for studying substructures of hypergraphs. Using dilutions we observe an analogue to the Excluded Grid Theorem for degree 2 hypergraphs. In consequence, we show that that the tractability of conjunctive query answering can be characterised in terms of generalised hypertree width. A similar characterisation is also shown for the corresponding counting problem. We also generalise our main structural result to arbitrary bounded degree and discuss possible paths towards a characterisation of the bounded degree case.
翻译:我们研究对非约束性查询的共质查询的可辨别性。众所周知,问题的可辨别性可以以结合性假设下的 " 边际 " 查询为特征。我们将这一结果推广到无约束性对等性但第2级的案件。为此,我们采用高光分解作为原始图未成年人研究高光分结构的替代方法。我们使用分解来观察2级高光谱中被排除的网格理论的类比。因此,我们表明共质查询的可辨识性可以以普遍化超大树宽度为特征。相应的计数问题也显示出类似的特征。我们还将我们的主要结构结果概括为任意约束性程度,并讨论接近约束性案例特征的可能途径。