Limit Datalog: A Declarative Query Language for Data Analysis

摘要

Motivated by applications in declarative data analysis, we study Datalog_Z-an extension of Datalog with stratified negation and arithmetics over integers. Reasoning in this language is undecidable, so we present a fragment, called limit Datalog_Z, that is powerful enough to naturally capture many important data analysis tasks. In limit Datalog_Z, all intensional predicates with a numeric argument are limit predicates that keep only the maximal or minimal bounds on numeric values. Reasoning in limit Datalog_Z is decidable if multiplication is used in a way that satisfies our linearity condition. Moreover, fact entailment in limit-linear Datalog_Z is △_2~(EXP)-complete in combined and △_2~P-complete in data complexity, and it drops to coNEXP and coNP, respectively, if only (semi-)positive programs are considered. We also propose an additional stability requirement, for which the complexity drops to EXP and P, matching the bounds for usual Datalog. Limit Datalog_Z thus provides us with a unified logical framework for declarative data analysis and can be used as a basis for understanding the expressive power of the key data analysis constructs.