Foundations of Declarative Data Analysis Using Limit Datalog Programs
Abstract
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.
Cite
Text
Kaminski et al. "Foundations of Declarative Data Analysis Using Limit Datalog Programs." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/156Markdown
[Kaminski et al. "Foundations of Declarative Data Analysis Using Limit Datalog Programs." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/kaminski2017ijcai-foundations/) doi:10.24963/IJCAI.2017/156BibTeX
@inproceedings{kaminski2017ijcai-foundations,
title = {{Foundations of Declarative Data Analysis Using Limit Datalog Programs}},
author = {Kaminski, Mark and Grau, Bernardo Cuenca and Kostylev, Egor V. and Motik, Boris and Horrocks, Ian},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {1123-1130},
doi = {10.24963/IJCAI.2017/156},
url = {https://mlanthology.org/ijcai/2017/kaminski2017ijcai-foundations/}
}