Queries with Guarded Negation
A well-established and fundamental insight in database theory is that negation (also known as complementation) tends to make queries difficult to process and difficult to reason about. Many basic problems are decidable and admit practical algorithms in the case of unions of conjunctive queries, but become difficult or even un-decidable when queries are allowed to contain negation. Inspired by recent results in finite model theory, the authors consider a restricted form of negation, guarded negation. They introduce a fragment of SQL, called GN-SQL, as well as a fragment of Datalog with stratified negation, called GN-Datalog, that allow only guarded negation, and they show that these query languages are computationally well behaved, in terms of testing query containment, query evaluation, open-world query answering, and boundedness.