Abstract
Motivated by applications in declarative data analysis, we study DatalogZ---an extension of positive Datalog with arithmetic functions over integers. This language is known to be undecidable, so we propose two fragments. In limit DatalogZ 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 DatalogZ can express many useful data analysis tasks, and so our results provide a sound foundation for the development of advanced information systems.
Keywords
- Knowledge Representation, Reasoning, and Logic: Computational Complexity of Reasoning
- Knowledge Representation, Reasoning, and Logic: Knowledge Representation Languages
- Knowledge Representation, Reasoning, and Logic: Logics for Knowledge Representation
- Knowledge Representation, Reasoning, and Logic: Tractable languages and knowledge compilation
