Queries with guarded negation (full version

A well-established and fundamental insight in database the-ory 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 prac-tical algorithms in the case of unions of conjunctive queries, but become difficult or even undecidable when queries are allowed to contain negation. Inspired by recent results in fi-nite model theory, we consider a restricted form of negation, guarded negation. We 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 nega-tion, and we show that these query languages are compu-tationally well behaved, in terms of testing query contain-ment, query evaluation, open-world query answering, and boundedness. GN-SQL and GN-Datalog subsume a num-ber of well known query languages and constraint languages, such as unions of conjunctive queries, monadic Datalog, and frontier-guarded tgds. In addition, an analysis of standard benchmark workloads shows that most usage of negation in SQL in practice is guarded negation. 1