Query containment is a fundamental database problem which has been extensively studied for conjunctive queries (CQs). The most famous result is arguably the Homomorphism Theorem: a CQ q₁ is contained in a CQ q₂ iff there is a homomorphism from q₂ to q₁. However, when extending conjunctive queries with safe base negation (CQ^¬), this test becomes incomplete, hence, requiring significantly more expensive procedures due to its inherently harder complexity (Π₂^P-hard). In this paper, we define and study the classes CQ^{1¬}_{HT} and CQ^{¬}_{HT}: the classes of conjunctive queries extended with one or several safe negated atoms that satisfy the Homomorphism Theorem, and hence, whose containment check is in NP. To characterise them, we define what we call the dependency-version of a query, which is a dependency that, intuitively, models the databases in which the query is false. It turns out that, when the query q contains one (several) negated atom(s), the query satisfies the Homomorphism Theorem iff its tgd(ded)-version is uniformly one-bounded. We also show that CQ^¬_{HT} membership is EXPTIME-hard, but its complexity reduces to Π₂^P in the CQ^{1¬}_{HT} case, and to NP when bounding the number of positive atoms that can unify with the negated one.

The notion of SQL assertion was introduced, in SQL-92 standard, to define general constraints over a relational database. They can be used, for instance, to specify cross-row constraints or multitable check constraints. However, up to now, none of the current relational database management systems (RDBMSs) support SQL assertions due to the difficulty of providing an efficient solution. To implement SQL assertions efficiently, the RDBMs require an incremental checking mechanism. I.e., given an assertion, the RDBMS should revalidate it only when a transaction changes data in a manner that could violate it, and only for the affected data. Some years ago, the deductive database community provided several incremental checking methods, however, their results could not get into practice in RDBMS. In this paper, we propose an approach to efficiently implement SQL assertions in an RDBMS through an incremental revalidation technique. Such an approach is compatible with any RDBMS since it is fully based on standard SQL concepts (tables, triggers, and procedures). Our proposal uses and extends the Event Rules , an existing proposal for incremental checking in deductive databases. This extension is required to handle distributive aggregates, which pushes the expressiveness of the handled SQL assertions beyond first-order constraints. Moreover, we exploit this extension to improve the treatment of constraints involving existential variables, which are a very common kind of constraints difficult and expensive to handle. Finally, we show the efficiency of our approach through some experiments, and we formally prove its soundness and completeness.

We present TINTIN, a tool to perform efficient integrity checking of SQL assertions in SQL Server. TINTIN rewrites each assertion into a set of standard SQL queries that, given a set of insertions and deletions of tuples, allow to incrementally compute whether this update violates the assertion or not. If one of such queries returns a non empty answer, then the assertion is violated. Efficiency is achieved by evaluating only those data and those assertions that can actually be violated according to the update. TINTIN is aimed at two different purposes. First, to show the feasibility of our approach by implementing it on a commercial relational DBMS. Second, to illustrate that the efficiency we achieve is good enough for making assertions to be used in practice.