Jos de Bruijn and Stijn Heymans. Complexity of the stable model semantics for queries on incomplete databases. In Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR2009), Potsdam, Germany, September 14-18 2009.

We study the complexity of consistency checking and query answering 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 interpretation of C-databases with and without conditions. By reduction to stable models of logic programs we find that, under closed-world interpretation, adding negation 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 interpretation, 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.

[ bib | .pdf ] Back