# Complexity of Arithmetic in Warded Datalog+-

arXiv: https://arxiv.org/abs/2202.05086 · HTML: https://mlsanity.com/paper/2202.05086/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 50 references that are in the map.
- First posted on arXiv 10 Feb 2022.

## Builds on (most cited first, 5 of 5)

- [The Vadalog System: Datalog-based Reasoning for Knowledge Graphs](https://mlsanity.com/paper/1807.08709/) (2018)
- [ASP(AC): Answer Set Programming with Algebraic Constraints](https://mlsanity.com/paper/2008.04008/) (2020)
- [Foundations of Declarative Data Analysis Using Limit Datalog Programs](https://mlsanity.com/paper/1705.06927/) (2017)
- [Here and There with Arithmetic](https://mlsanity.com/paper/2108.03187/) (2021)
- [Initial Limit Datalog: a New Extensible Class of Decidable Constrained Horn Clauses](https://mlsanity.com/paper/2104.14175/) (2021)

## Abstract (arXiv)

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.