DATALOG Queries with Stratified Negation and Choice: from P to DP

This paper introduces a unified solution to the problem of extending stratified DATALOG to express DB-complexity classes ranging from P to DP. The solution is based on (i) stratified negation as the core of a simple, declarative semantics for negation, (ii) the use of a “choice” construct to capture non-determinism of stable models (iii) the ability to bind a query execution to the complexity class that includes the problem at hand, and (iv) a general algorithm that ensures efficient execution for the different complexity classes. We thus obtain a class of DATALOG programs that preserves computational tractability, while achieving completeness for a wide range of complexity classes.