Non-determinism and weak constraints in Datalog

This paper introduces a simple and powerful extension of stratified DATALOG which permits to express various DB-complexity classes. The new language, called DATALOG¬s,c,p, extends DATALOG with stratified negation, a non-deterministic construct, calledchoice, and a weak form of constraints, calledpreference rules, that is, constraints that should be respected but, if they cannot be eventually enforced, they only invalidate the portions of the program which they are concerned with. Although DATALOG with stratified negation is not able to express all polynomial time queries, the introduction of the non-deterministic constructchoice permits to express, exactly, the ‘deterministic fragment’ of the class of DB-queriesP, under the non-deterministic semantics, NP, under the possible semantics, and coNP, under the certain semantics. The introduction of preference rules, further increases the expressive power of the language, and permits to express the complexity classes Σ2p, under the possibility semantics, and Π2p, under the certainty semantics.