Abstract
We study containment of conjunctive queries that are evaluated over databases that may contain tuples with null values. We assume the semantics of SQL for single block queries with a SELECT DISTINCT clause. This problem ("null containment" for short) is different from containment over databases without null values and sometimes more difficult.
We show that null-containment for boolean conjunctive queries is NP-complete while it is Pi(P)(2)-complete for queries with distinguished variables. However, if no relation symbol is allowed to appear more than twice, then null-containment is polynomial, as it is for databases without nulls. If we add a unary test predicate IS NULL, as it is available in SQL, then containment becomes Pi(P)(2)-hard for boolean queries, while it remains in Pi(P)(2) for arbitrary queries.