Foundations of knowledge graphs: Complexity of arithmetic in vadalog

Abstract

Vadalog is a powerful state-of-the-art Knowledge Graph (KG) system with strong theoretical underpinnings for its core logical reasoning component. Vadalog's reasoning and knowledge representation language is an extension of Datalog. The Datalog language is widely used in the context of knowledge-based systems and Big Data analytics because of its declarative nature, scalability, and its ability to express full recursion. The theoretical guarantees of the Vadalog language, however, do not cover extensions heavily needed in data analytics, such as arithmetic. In fact, there are no complexity results for the combination of a (decidable) Datalog language extended with arithmetic and existentials in rule heads, the latter of which is needed e.g., for ontological reasoning. In this work we investigate potential candidates for arithmetic in Vadalog and show that extending KG reasoning languages with arithmetic is a non-trivial problem. We define a new language as extension of Vadalog’s core language with a well-behaving and efficient form of arithmetic. We prove P-completeness of our language, which we call Warded Bound DatalogZ. Moreover, we show the first expressivity results for a decidable language supporting arithmetic. In particular, we prove capture results for Limit DatalogZ, a language that was recently introduced in a remarkable line of work by Kaminski et al. Our contributions prove that our language is a suitable candidate for reasoning in AI systems. Thereby, we lay the theoretical foundation for highly expressive logical languages that combine the power of complex recursive reasoning and arithmetic, while maintaining efficient reasoning algorithms for applications in modern AI systems, such as KGs.