Complexity of the Stable Model Semantics for Queries on Incomplete Databases

Abstract. We study the complexity of consistency checking and query answer-ing on incomplete databases for languages ranging from non-recursive Datalog to disjunctive Datalog with negation under the stable model semantics. We consider both possible and certain answers and both closed- and open-world interpreta-tion of C-databases with and without conditions. By reduction to stable models of logic programs we find that, under closed-world interpretation, adding nega-tion to (disjunctive) Datalog does not increase the complexity of the considered problems for C-databases, but certain answers for databases without conditions are easier for Datalog without than with negation. Under open-world interpreta-tion, adding negation to non-recursive Datalog already leads to undecidability, but the complexity of certain answers for negation-free queries is the same as under closed-world interpretation.