Datalog reasoning based on the semina\"ive evaluation strategy evaluates
rules using traditional join plans, which often leads to redundancy and
inefficiency in practice, especially when the rules are complex. Hypertree
decompositions help identify efficient query plans and reduce similar
redundancy in query answering. However, it is unclear how this can be applied
to materialisation and incremental reasoning with recursive Datalog programs.
Moreover, hypertree decompositions require additional data structures and thus
introduce nonnegligible overhead in both runtime and memory consumption. In
this paper, we provide algorithms that exploit hypertree decompositions for the
materialisation and incremental evaluation of Datalog programs. Furthermore, we
combine this approach with standard Datalog reasoning algorithms in a modular
fashion so that the overhead caused by the decompositions is reduced. Our
empirical evaluation shows that, when the program contains complex rules, the
combined approach is usually significantly faster than the baseline approach,
sometimes by orders of magnitude.

本文提供了应用超树分解来优化和简化 Datalog 程序的算法，并与标准 Datalog 和增量规则评估方法相结合。经过实验证明，当程序包含复杂规则时，这种方法通常比基线方法快得多。

使用超树分解增强 Datalog 推理

Enhancing Datalog Reasoning with Hypertree Decompositions

Hypertree decompositions, as well as the more powerful generalized hypertree
decompositions (GHDs), and the yet more general fractional hypertree
decompositions (FHD) are hypergraph decomposition methods successfully used for
answering conjunctive queries and for the solution of constraint satisfaction
problems. Every hypergraph H has a width relative to each of these
decomposition methods: its hypertree width hw(H), its generalized hypertree
width ghw(H), and its fractional hypertree width fhw(H), respectively.
It is known that hw(H) <= k can be checked in polynomial time for fixed k,
while checking ghw(H) <= k is NP-complete for any k greater than or equal to 3.
The complexity of checking fhw(H) <= k for a fixed k has been open for more
than a decade.
We settle this open problem by showing that checking fhw(H) <= k is
NP-complete, even for k=2. The same construction allows us to prove also the
NP-completeness of checking ghw(H) <= k for k=2. After proving these hardness
results, we identify meaningful restrictions, for which checking for bounded
ghw or fhw becomes tractable.

证明了检查分数超树宽度是否小于等于 k 的复杂度为 NP 完全问题，即使 k 为 2，同时证明了检查广义超树宽度是否小于等于 k 的复杂度同样为 NP 完全问题。