Complexity of Arithmetic in Warded Datalog+-
This work addresses the problem of enabling efficient arithmetic reasoning in logic-based languages for applications like knowledge graphs, representing a foundational advance rather than an incremental step.
The paper tackles the lack of decidable fragments in Datalog+- languages extended with arithmetic by defining a new language that extends Warded Datalog+- with arithmetic and proves its P-completeness, providing an efficient reasoning algorithm and closing an open question.
Warded Datalog+- extends the logic-based language Datalog with existential quantifiers in rule heads. Existential rules are needed for advanced reasoning tasks, e.g., ontological reasoning. The theoretical efficiency guarantees of Warded Datalog+- do not cover extensions crucial for data analytics, such as arithmetic. Moreover, despite the significance of arithmetic for common data analytic scenarios, no decidable fragment of any Datalog+- language extended with arithmetic has been identified. We close this gap by defining a new language that extends Warded Datalog+- with arithmetic and prove its P-completeness. Furthermore, we present an efficient reasoning algorithm for our newly defined language and prove descriptive complexity results for a recently introduced Datalog fragment with integer arithmetic, thereby closing an open question. We lay the theoretical foundation for highly expressive Datalog+- languages that combine the power of advanced recursive rules and arithmetic while guaranteeing efficient reasoning algorithms for applications in modern AI systems, such as Knowledge Graphs.