Foundations of Declarative Data Analysis Using Limit Datalog Programs - Kaminski, M; Cuenca Grau, B; Kostylev, E; Motik, B; Horrocks, I (AAAI Press / International Joint Conferences on Artificial Intelligence, 2017)
Motivated by applications in declarative data analysis, we study $Datalog$Z—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$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 $stability$ requirement causes the complexity to drop to EXPTIME and PTIME, respectively. Finally, we show that stable $Datalog$Z can express many useful data analysis tasks, and so our results provide a sound foundation for the development of advanced information systems.