[Back]

J. De Bruijn, S. 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 (LPNMR 2009)", Springer, 2009, ISBN: 978-3-642-04237-9, 101 - 114.

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.

http://dx.doi.org/10.1007/978-3-642-04238-6_11

http://publik.tuwien.ac.at/files/PubDat_180900.pdf

Project Head Thomas Eiter:
ONOTRULE - ONTOlogies meet business RULEs