Foundations of Declarative Data Analysis Using Limit Datalog Programs
This work provides a theoretical foundation for declarative data analysis systems, addressing undecidability issues in extensions of Datalog for applications in information systems.
The authors tackled the undecidability of Datalog with integer arithmetic by proposing two restricted fragments, limit Datalog_Z and stable Datalog_Z, proving that fact entailment is coNExpTime-complete in combined complexity and coNP-complete in data complexity for the former, with complexities dropping to ExpTime and PTime for the latter.
Motivated by applications in declarative data analysis, we study $\mathit{Datalog}_{\mathbb{Z}}$---an extension of positive Datalog with arithmetic functions over integers. This language is known to be undecidable, so we propose two fragments. In $\mathit{limit}~\mathit{Datalog}_{\mathbb{Z}}$ 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 $\mathit{stability}$ requirement causes the complexity to drop to ExpTime and PTime, respectively. Finally, we show that stable $\mathit{Datalog}_{\mathbb{Z}}$ can express many useful data analysis tasks, and so our results provide a sound foundation for the development of advanced information systems.