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

Efficient decision-making over continuously changing data is essential for
many application domains such as cyber-physical systems, industry
digitalization, etc. Modern stream reasoning frameworks allow one to model and
solve various real-world problems using incremental and continuous evaluation
of programs as new data arrives in the stream. Applied techniques use, e.g.,
Datalog-like materialization or truth maintenance algorithms to avoid costly
re-computations, thus ensuring low latency and high throughput of a stream
reasoner. However, the expressiveness of existing approaches is quite limited
and, e.g., they cannot be used to encode problems with constraints, which often
appear in practice. In this paper, we suggest a novel approach that uses the
Conflict-Driven Constraint Learning (CDCL) to efficiently update legacy
solutions by using intelligent management of learned constraints. In
particular, we study the applicability of reinforcement learning to
continuously assess the utility of learned constraints computed in previous
invocations of the solving algorithm for the current one. Evaluations conducted
on real-world reconfiguration problems show that providing a CDCL algorithm
with relevant learned constraints from previous iterations results in
significant performance improvements of the algorithm in stream reasoning
scenarios.
Under consideration for acceptance in TPLP.

本文提出了一种基于冲突驱动约束学习（CDCL）的方法，通过智能管理学习到的约束条件来有效地更新流推理算法的遗留解决方案，研究了强化学习在连续评估先前计算的约束条件的实用性，并在真实世界的重构问题上取得了显着的性能提升，为流推理场景提供了新的解决思路。