The Evaluation and the Computational Complexity of Datalog Queries of Boolean Constraint Databases

In the database framework of Kanellakis et al. it was argued that constraint query languages should meet the closed-form requirement, that is, they should take as input constraint databases and give as output constraint databases that use the same type of constraints. This paper shows that the closed-form requirement can be met for Datalog queries with Boolean equality constraints with double exponential time-complete data complexity, for Datalog queries with precedence and monotone inequality constraints in triple exponential-time data complexity. A closed-form evaluation is also shown for (Stratified) Datalog queries with equality and inequality constraints in atomless Boolean algebras in triple exponential-time data complexity. 1 Introduction Constraint databases describe extensional database relations as quantifier-free first-order formulas. Constraint databases in the form of non-ground facts have been used in constraint logic programming [9, 10, 19] for almost ten years. Constra..