Extending Stratified Datalog to Capture Complexity Classes Ranging from P to QH

This paper presents a unified solution to the problem of extending stratified DATALOG to express database complexity classes ranging from to; is the query hierarchy containing the decision problems that can be solved in polynomial time by a deterministic Turing machine using a constant number of calls to an -oracle. 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 the nondeterminism of stable models in a disciplined fashion, (iii) the ability to bind a query to the lowest complexity level that includes the problem at hand, and (iv) a general algorithm that adapts its behavior to the desired level of complexity required by the query so that exponential time computation is only required for hard problems.