Extending stratified datalog to capture complexity classes ranging from P to QH

This paper presents a unified solution to the problem of extending stratifi ed DATALOG to express database complexity classes ranging from P to QH; QW is the query hierarchy containing the decision problems that can be solved in polynomial time by a deterministic Turing machine using, a constant numb er of calls to an NP-oracle. The solution is based on (i) stratified negati on as the core of a simple, declarative semantics for negation, (ii) the us e 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 com plexity level that includes the problem at hand, and (iv) a general algorit hm that adapts its behavior to the desired level of complexity required by the query so that exponential time computation is only required for hard pr oblems.