Foundations of Declarative Data Analysis Using Limit Datalog Programs

2017/05/19 by Kaminski, Mark, Grau, Bernardo Cuenca, Kostylev, Egor V. +2 · 1 citation
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1705.06927

Abstract

Motivated by applications in declarative data analysis, we study Datalog_ℤ---an extension of positive Datalog with arithmetic functions over integers. This language is known to be undecidable, so we propose two fragments. In limit~Datalog_ℤ predicates are axiomatised to keep minimal/maximal numeric values, allowing us to show that fact entailment is coNExpTime-complete in combined, and coNP-complete in data complexity. Moreover, an additional stability requirement causes the complexity to drop to ExpTime and PTime, respectively. Finally, we show that stable Datalog_ℤ can express many useful data analysis tasks, and so our results provide a sound foundation for the development of advanced information systems.

Cited by

• Are Language Models Efficient Reasoners? A Perspective from Logic Programming

Related

• Stratified Negation in Limit Datalog Programs
• Initial Limit Datalog: a New Extensible Class of Decidable Constrained Horn Clauses
• Complexity of Arithmetic in Warded Datalog+-
• Datalog with First-Class Facts
• Synthesizing Datalog Programs Using Numerical Relaxation