The Evaluation and the Computational Complexity of Datalog Queries of Boolean Constraint Databases
Peter Zsolt Revesz · International Journal of Algebra and Computation · 1998
In the database framework of Kanellakis et al. it was argued that constraint query languages should meet the closed-form requirement, that is, queries 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.