Conjunctive Query Containment with Safe Negation and TGD One-Boundedness

Query containment stands as one of the most fundamental problems in databases. Given two queries, $q_1$ and $q_2$, the query containment problem seeks to determine whether all the tuples retrieved by $q_1$ are also retrieved by $q_2$, irrespective of the underlying data. This question finds applications across various domains, from information integration and query optimisation to materialised view maintenance and constraint checking [3]. Thus, extensive study has been devoted to this problem, particularly for conjunctive queries (CQ) under set semantics, which corresponds to the select-project-join subset of relational algebra. Indeed, in today’s database (DB) usage, CQs are the most prevalent kind of queries [17].

Given its significance, substantial algorithmic and theoretical research has tackled CQ containment. The most famous results, possibly, are that the problem is NP-complete and that it can be solved through a homomorphism test (aka Homomorphism Theorem) [5]. I.e., given two CQs $q_1$ and $q_2$, we can check whether $q_1$ is contained in $q_2$, noted as $q_1⊑q_2$, by creating the canonical DB of $q_1$ (i.e. creating a DB by replacing every variable from $q_1$ with a new fresh constant), and querying $q_2$ over this canonical DB. From here, several refinements are possible. E.g., the problem becomes PTIME when the queries do not contain more than two atoms with the same predicate [19], or when we can bound its hypertree-width [10].

Yet, these results lose applicability when dealing with CQ extended with safe base negation (from now on $C{Q}^{\neg }$), i.e., queries containing negated atoms whose variables appear in positive atoms.

Clearly, $q_a⊑q_b$ since there is a homomorphism from $q_b$ to $q_a$ (i.e., $\{t\to Train\}$). Indeed, the homomorphism test is always sound to check containment, even in $C{Q}^{\neg }$ [16]. From now on, we will write $q_2\rightsquigarrow q_1$ to indicate that there is a homomorphism from $q_2$ to $q_1$.

However, the lack of homomorphism from $q_a$ to $q_b$ is not sufficient to assess that $q_b⋢q_a$. Indeed, the homomorphism test is sound, but incomplete, in $C{Q}^{\neg }$. Hence, a far more sophisticated technique is required. Indeed, under the presence of negated atoms, the problem is known to be ${\mathrm{\Pi }}_2^P$-hard [7, 20]. Consequently, such techniques encompass generating and analysing an exponential number of different canonical versions of $q_a$ [8, 20].

To address this situation, in this paper we study the conjunctive queries extended with at most one negation ($C{Q}^{1\neg }$), and those extended with several negated atoms ($C{Q}^{\neg }$), and characterise the classes $C{Q}_{HT}^{1\neg }$ and $C{Q}_{HT}^{\neg }$, i.e., their respective subclasses that satisfy the Homomorphism Theorem. That is, those boolean conjunctive queries with negation $q_2$ s.t., in essence, given any other boolean conjunctive query with negation $q_1$, $q_1⊑q_2$ iff $q_2\rightsquigarrow q_1$. This not only permits reducing the complexity to NP, but also exploiting the techniques given for checking homomorphisms faster [19, 10]. E.g., as we will see, both queries presented previously belong to $C{Q}_{HT}^{1\neg }$. Thus, we can check containment via the homomorphism test, and, furthermore, since no predicate appears more than twice, we can do it in PTIME [19].

To identify whether a query belongs to $C{Q}_{HT}^{1\neg }$ or $C{Q}_{HT}^{\neg }$, we realise that it is equivalent to answering whether a full-dependency (a full-tgd in the $C{Q}^{1\neg }$ case, and full-ded in the $C{Q}^{\neg }$), is uniformly one-bounded, or not, which is a property already studied in the context of logic programming [18, 13] and the chase algorithm [2]. A full-dependency is a rule of the form $\forall \overline{x}.\varphi (\overline{x})\to {\vee }_{i=1..n}{P}_i(\overline{x_i})$, where $\varphi$ is a conjunction of atoms and $P_i(\overline{x_i})$ is an atom s.t. $\overline{x_i}\subseteq x$. A full-dependency is a full-tgd when $n=1$, and a full-ded when $n>1$. Given a full-dependency $t$, and a database $D$, chasing $D$ with $t$ means, roughly speaking, creating the minimal necessary atoms $P_i(\overline{x_i})$ to satisfy $t$ in $D$. Do note that, if the predicate $P_i$ appears in $\varphi$, we might need to recursively chase $D$. In essence, a full-dependency is said to be uniformly one-bounded if and only if, for any database $D$, any fact $P(\overline{x})$ obtained by the chase can be obtained in a single chase step (i.e., without recursion). Bounded (full-)tgds have been well-studied since they permit avoiding recursion, and allowing first-order rewritings [1]. In this paper, we naturally extend this notion to full-deds.

Our main result is that a CQ with safe base negation satisfies the Homomorphism Theorem iff its dependency-version is uniformly one-bounded, where the dependency-version of a query is the dependency obtained by placing the negated atoms of the query in the right-hand side of the dependency (resulting in a tgd, in the $C{Q}^{1\neg }$ case, and in a ded, in the $C{Q}^{\neg }$ case).

We show this tight connection between the Homomorphism Theorem and dependency uniform one-boundedness by reducing containment over $C{Q}^{\neg }$ into an Ontology-Based Data Access (OBDA) consistency problem. In essence, given two boolean queries $q_1$ and $q_2$, we build an ontology, using dependencies, that captures the DB counterexamples of $q_1⊑q_2$; thus, its unsatisfiability proves containment. It is worth mentioning that this idea of reducing query-containment into ontology consistency has already been explored in [4, 8] to deal with query containment under constraints.

In summary, our contributions are:

• $\mathrm{■}$

  We define the classes $C{Q}_{HT}^{1\neg }$ and $C{Q}_{HT}^{\neg }$ of boolean conjunctive queries extended with one or several negated atoms, that satisfy the Homomorphism Theorem.

• $\mathrm{■}$

  We show that identifying whether a query $q\in C{Q}^{1\neg }$ belongs to $C{Q}_{HT}^{1\neg }$ is, in essence, the very same problem as identifying whether a full-tgd is uniformly one-bounded.

• $\mathrm{■}$

  We extend the notion of uniform one-boundedness to full-deds, and show that identifying whether a query $q\in C{Q}^{\neg }$ belongs to $C{Q}_{HT}^{\neg }$ is, in essence, the very same problem as identifying whether a full-ded is uniformly one-bounded.

• $\mathrm{■}$

  We demonstrate that deciding whether a query $q\in C{Q}^{\neg }$ belongs to $C{Q}_{HT}^{\neg }$ is EXPTIME-hard, but, in the $C{Q}_{HT}^{1\neg }$ case, its complexity lies between NP and ${\mathrm{\Pi }}_2^P$, mirroring the currently observed complexity for the chase-firing problem [12], and it is in NP when bounding the number of positive atoms that can unify with the negated atom.

As subsidiary contributions, we also show how to build a datalog (disjunctive-datalog) program that checks whether there is a containment between two conjunctive queries with one (several) negated safe atoms.

In the following, we introduce the basic logic notions we will use throughout the paper:

A term is either a variable, a constant, or a labelled null. We denote variables with lower case alphabetic characters (e.g., $x$, $y$, $z$), labelled nulls with strings starting with “#” (e.g., $\mathrm{\#}x$, $\mathrm{\#}y$, $\mathrm{\#}z$), and constants with strings starting with upper case characters (e.g., Train, John). A vector of terms is denoted by $\overline{t}$.

A predicate is composed of a name and some arity (e.g. Connects is a $3$-ary predicate). An atom is an $n$-ary predicate with $n$ terms (e.g. Connects(x,y,Train)). A ground atom is an atom whose terms are labelled nulls or constants (e.g., Connects(#x,#y,Train)).

A substitution $\sigma$ is a mapping from variables and labelled nulls to terms. Variables can be mapped to any term, whereas labelled nulls can only be mapped to other labelled nulls or constants. Applying a substitution $\sigma$ to an atom (or conjunction of atoms) $a$, denoted by $a_{[\sigma ]}$, consists in simultaneously replacing each variable (labelled null) $v$ with $\sigma (v)$ in $a$ (in case $\sigma (v)$ is defined). We denote a substitution with $\{v_1\to t_1,v_2\to t_2,\mathrm{\dots }\}$ where $v_i$ are different variables and labelled-nulls and $t_i$ are terms. If all the variables are mapped to labelled nulls or constants, we call the substitution ground.

A database $D$ is a finite set of ground atoms. Given a ground atom $a$, $a$ is true in $D$, denoted by $D\vDash a$, iff $a\in D$.

Next, we review the notions of conjunctive queries and query containment.

A boolean CQ is a formula composed of a 0-ary atom, called the head, and a conjunction of atoms, called the body. E.g., $q()\text{ :- }A(x)\wedge B(x,y)$ is a CQ, where $q()$ is the head and $A(x)\wedge B(x,y)$ is the body. Given a boolean CQ $q$, and a database $D$, we say that the query is true in $D$, denoted by $D\vDash q$, iff there exists a ground substitution $\sigma$ that makes all the atoms of the body of $q$ true w.r.t. $D$. A boolean CQ $q_1$ is contained in another boolean CQ $q_2$, denoted by $q_1⊑q_2$, iff, for any database $D$ s.t. $D\vDash q_1$, we have $D\vDash q_2$.

Given two boolean queries $q_1$ and $q_2$, a homomorphism from $q_2$ to $q_1$, denoted by $q_2\rightsquigarrow q_1$, is a substitution $\sigma$ that makes the body of $q_2$ contained in the body of $q_1$. Similarly, given a conjunction of positive atoms $a$, a database $D$, and a substitution $\sigma$ s.t. $D\vDash a_{[\sigma ]}$, we say that $\sigma$ is a homomorphism from $a$ to $D$ (shortly, $D$ satisfies $a$) and write, abusing notation, $D\vDash a$. We naturally extend the notion of homomorphism to databases as follows. Given two databases $D_1$ and $D_2$, a homomorphism from $D_1$ to $D_2$ is a substitution $\sigma$ s.t. $D_{1[\sigma ]}\subseteq D_2$.

Given a set of (possibly non-ground) atoms, its freeze is the DB obtained after applying a substitution that replaces each variable with a fresh labelled null. Given a boolean CQ $q$, we define freeze(q) as the freeze of its body. E.g., the freeze of $q()\text{ :- }A(y)\wedge B(y,\mathrm{\#}z,John)$ is the DB $\{A(\mathrm{\#}y),B(\mathrm{\#}y,\mathrm{\#}z,John)\}$. Given two boolean CQ $q_1$ and $q_2$, we can check whether $q_2\rightsquigarrow q_1$ by querying $q_2$ over freeze($q_1$).

Next, we summarise the notions of tgds, deds, and OBDA techniques we require:

A (full-)dependency is a formula $\forall \overline{x}.\varphi (\overline{x})\to {\vee }_{i=1..n}{P}_i(\overline{x_i})$, where $\varphi$ is a conjunction of atoms, called the left-hand side (LHS), and ${\vee }_{i=1..n}{P}_i(\overline{x_i})$ is a disjunction of atoms, called the right-hand side (RHS), with $\overline{x_i}\subseteq \overline{x}$. We denote the LHS and RHS of a dependency $t$ by $LHS(t)$ and $RHS(t)$, respectively. Do note that we do not consider existential variables (i.e. all the variables appearing in the RHS also appear in the LHS). Given a dependency $t$ and a database $D$, we say that $D$ satisfies $t$, noted as $D\vDash t$, iff for any homomorphism $\sigma$ from $LHS(t)$ to $D$, we have $D\vDash P_i{(\overline{x_i})}_{[\sigma ]}$ for some $P_i(\overline{x_i})\in RHS(t)$. Otherwise, we say that $D$ violates $t$. When the dependency only contains one atom in its RHS, we call it a tgd (tuple-generating dependency); when it contains several, we call it a ded (disjunctive-embedded dependency); and when it has none, we call it a denial. For brevity, we use the terms tgd/ded to refer to full-tgd/ded, and we omit the logic quantifiers.

An ontology $O$ is a pair $⟨T,D⟩$, where $T$ is a set of dependencies, and $D$ is a database. A model of an ontology $O$ is a set of ground atoms $M$ s.t. 1) there is a homomorphism from $D$ to $M$, and 2) every dependency $t\in T$ is satisfied by $M$. We might use $\text{<em class="ltx\_emph ltx\_font\_italic">models</em>}(O)$ to refer to all the models of an ontology $O$. Given a boolean conjunctive query $q$, we use the certain answer semantics. That is, querying $q$ over $O$ consists in answering whether $q$ is true in every possible model of $O$, which we note as $⟨T,D⟩\vDash q$. Since we only work with full-dependencies, all models are finite.

Given an ontology $O=⟨T,D⟩$, where $T$ is only composed of full-tgds, its universal model is a finite model $M\in models(O)$ s.t., for any other model $M^{\prime }\in models(O)$, $M\rightsquigarrow M^{\prime }$. Given an ontology $O$ and a (union of) conjunctive query(ies) $q$, we can obtain the certain-answers of $q$ over $O$ by querying $q$ over its universal model $M$ [6]. More in general, if the ontology is composed of full-tgds, full-deds, and denials, its universal model set is a finite set of models $M_1$, …, $M_n\in models(O)$, s.t., 1) for any possible model $M^{\prime }$, there is some $M_i$ s.t. $M_i\rightsquigarrow M^{\prime }$, and 2) the set is minimal, i.e., there are no two models in the universal model set $M_i,M_j$ s.t. $M_i\rightsquigarrow M_j$ [6]. In this case, we can check $O\vDash q$ by querying $q$ over all the models $M_i$ of the universal model set.

Given an ontology $⟨T,D⟩$, s.t., there is a full-tgd $t\in T$ that is violated in $D$ for some substitution $\sigma$, applying a chase step means adding $RHS{(t)}_{[\sigma ]}$ into $D$. In case $t$ is a ded violated in $D$ for some substitution $\sigma$, applying a chase step means adding some $P{(\overline{x})}_{[\sigma ]}$ into $D$, where $P\in RHS(t)$. In case $t$ is a denial, the chase is considered to fail, and no solution exists. The chase algorithm consists in iteratively applying any possible chase step until reaching a new database $D^{\prime }$ where all dependencies are satisfied. If the ontology is composed solely of full-tgds, the result is unique and is the universal model of $O$. If the ontology contains full-dependencies, and we use the chase to explore every possible solution, we can obtain its universal model set.

Given a tgd $t$, we say that it is uniformly one-bounded (or one-bounded, for short) iff, given any database $D$ and ground atom $A(\overline{c})$, if $⟨t,D⟩\vDash A(\overline{c})$ we can obtain $A(\overline{c})$ in, at most, one single chase step. That is, either $A(\overline{c})\in D$, or there exists a substitution $\sigma$ s.t. $D\vDash LHS{(t)}_{[\sigma ]}$, and $A(\overline{c})=RHS{(t)}_{[\sigma ]}$.

In this paper, we refer to the boolean CQ extended with base negated atoms as $C{Q}^{\neg }$. As expected, a CQ with negation $q$ is true in a database $D$, denoted as $D\vDash q$, iff there exists a ground substitution $\sigma$ such that, for every positive atom $a$ in the body of $q$, $a_{[\sigma ]}\in D$, and for every negated atom $\neg b$ in the body of $q$, $b_{[\sigma ]}\notin D$. We only consider safe negation, i.e., queries where all variables appearing in a negated atom also appear in at least one positive atom of the same query.

We extend also the notion of homomorphism $q_2\rightsquigarrow q_1$ to queries with negation by requiring that the substitution $\sigma$ maps every positive atom $a$ of $q_2$ to a positive atom $a_{[\sigma ]}$ in the body of $q_1$, and every negated atom $\neg b$ of $q_2$ to a negated atom $\neg b_{[\sigma ]}$ in the body of $q_1$.

To study which queries from $C{Q}^{\neg }$ satisfy the Homomorphism Theorem, we must first formalise this notion. In particular, to bring a meaningful definition, we must be careful with those queries containing a contradiction. E.g., $q()\text{ :- }A(\overline{x})\wedge P(\overline{x})\wedge \neg P(\overline{x})$ is trivially contained in any other query, independently of having/not-having any homomorphism. Do note that such contradictions can be found by checking another homomorphism. I.e., we can find a contradiction by checking the existence of a homomorphism from $P(\overline{x})\wedge \neg P(\overline{x})$ (for every predicate $P$) to the body of our query.

Thus, we consider that a query $q_2$ satisfies the Homomorphism Theorem, in essence, if the containment w.r.t. another query $q_1$ can be determined by checking a homomorphism from $q_2$ to $q_1$, and checking whether $q_1$ contains or not a contradiction:

The main purpose of this paper is to characterise the set $C{Q}_{HT}^{\neg }$. That is, bringing a way to identify whether a query $q\in C{Q}^{\neg }$ belongs to $C{Q}_{HT}^{\neg }$. For our purposes, we will also study a slightly simplified case. That is, we will study the boolean conjunctive queries with at most one negated atom (from now on $C{Q}^{1\neg }$), and study when they satisfy the Homomorphism Theorem. Formally:

In this section, we bring the intuitions about how to check whether a query from $C{Q}^{\neg }$ satisfies the Homomorphism Theorem, and thus, belongs to $C{Q}_{HT}^{\neg }$. As we are going to see, such a query belongs to $C{Q}_{HT}^{\neg }$ iff its dependency-version is one-bounded. The formal theorems are left for the next section.

In particular, we reach such intuitions by reducing the problem of query containment of $C{Q}^{\neg }$ boolean queries to an OBDA consistency problem. That is, we build an ontology whose models represent the databases that witness the non-containment of the queries. As a result, if the ontology admits one (finite) model, there is a database counterexample for such containment. This reduction is already present in some other works, such as [4, 8].

In the following, we first discuss the reduction to an ontology finite satisfiability problem, then, we discuss why the queries whose dependency-version is one-bounded satisfy the Homomorphism Theorem, and finally, we discuss why the queries that satisfy the Homomorphism Theorem have one-bounded dependency-versions. From now on, abusing the language, we will call a query whose dependency-version is one-bounded a one-bounded query. In addition, we will only work with boolean queries with at most one negation (i.e., $C{Q}^{1\neg }$) to explain the intuitions with the easiest case.

Now we formalise the previous intuitions and generalise them to deal with boolean queries with several negated atoms.

In the following, we first define the notions relative to our ontology construction. In essence, we define the notions of dependency-version of a query, and its freeze, and formally prove that the ontology we build models the database counterexamples of the containment.

Then, we define, for our purposes, the notion of uniform one-boundedness for deds. Indeed, the notion of uniform one-boundedness is well defined for tgds, but, as far as we know, it has never been extended to deds. In our proposal, we define a ded as uniformly one-bounded if any atom from its universal model set can be obtained in at most one chase step, regardless of the original database.

Finally, we show that a query from $C{Q}^{\neg }$ belongs to $C{Q}_{HT}^{\neg }$ iff its dependency-version is uniformly one-bounded using the previous reduction to ontology finite satisfiability.

We now study the complexity of deciding whether $q\in C{Q}^{\neg }$ belongs to $C{Q}_{HT}^{\neg }$. As we are going to see, the problem is EXPTIME-hard due to a reduction from full-tgd fact entailment [11]. To lower this result, we study the complexity of $C{Q}_{HT}^{1\neg }$, and see that its complexity lies between NP and ${\mathrm{\Pi }}_2^P$, which virtually mirrors the known complexity of the chase triggering problem [12], whose similarity with our problem is also discussed.

Conjunctive query containment was shown to be NP-complete in [5], who also proposed the homomorphism test as a solution. To reduce the complexity, some researchers found some cases where the problem was in PTIME. For instance, Sarayian [19] showed that, if the queries do not contain more than two atoms with the same predicate, containment can be checked in PTIME. Gottlob et al [10] defined the notion of bounded hypertree width, which made conjunctive query containment checking in PTIME too.

Considering that we can reduce a homomorphism test from queries including negated atoms to a homomorphism test between queries with only positive atoms (e.g., replace any not(p) atom by a fresh predicate notP), this paper enlarges the application of the previous work to the $C{Q}_{HT}^{\neg }$ case.

To check containment in $C{Q}^{\neg }$, Levy and Sagiv [15] proposed building an exponential number of canonical databases and applying a homomorphism test for each one of them. Later on, while reviewing this method, Ullman stated that the query containment problem in $C{Q}^{\neg }$ was ${\mathrm{\Pi }}_2^P$-complete [20]. It turns out, however, that the upper-bound seems only valid when the arity of the predicates is bounded since Geck et al. [9] showed that it is coNEXPTIME-complete when arities are unbounded.

The work of Wei and Lausen [22, 21] is an optimised version of the work of [15, 20]. In essence, it uses the different homomorphisms between the queries to create several simpler containment tests. However, in the worst case, their approach might create the same exponential number of canonical databases. Similarly, the work of Farré et al [8] is based on building such canonical databases at runtime. Hence, they also face the problem of searching for a counterexample over an exponential search space.

The most similar result to our work is one from Mugnier et al [14], where a sufficient condition to assess that a query belongs to $C{Q}_{HT}^{\neg }$ is given. Basically, Mugnier et al state that if a query $q_2$ does not contain two unifiable atoms with opposite polarity, $q_2\in C{Q}_{HT}^{\neg }$. Indeed, this is a case in which $q_2\in C{Q}_{HT}^{\neg }$ since, roughly speaking, the RHS of the $ded(q_2)$ cannot unify with the LHS of $ded(q_2)$, which makes $ded(q_2)$ trivially uniformly one-bounded. Do note that this property is sufficient, but not necessary, as the queries provided in Example 1 can show. It is also worth mentioning that, in a different paper, Mugnier et al studied conditions that, when satisfied by $q_1,q_2\in C{Q}^{\neg }$, the query-containment complexity of $q_1⊑q_2$ can drop down to NP-complete [16]. Do note, however, that such conditions refer to both queries, whereas we have studied conditions over $q_2$ alone.

We have defined the classes $C{Q}_{HT}^{1\neg }$ and $C{Q}_{HT}^{\neg }$ of CQs that satisfy the Homomorphism Theorem, having one or several safe negated atoms. We have seen that deciding $C{Q}_{HT}^{1\neg }$ ($C{Q}_{HT}^{\neg }$) membership is, in essence, the same problem as deciding whether a full-tgd (full-ded) is uniformly one-bounded. We have also seen that the problem is EXPTIME-hard for the $C{Q}_{HT}^{\neg }$ case, but ${\mathrm{\Pi }}_2^P$ in the $C{Q}_{HT}^{1\neg }$ case, and can be lowered down to NP when bounding the number of positive atoms that can unify with the negated atom. We have also shown how to solve query containment using datalog queries, when the query $q\in C{Q}^{1\neg }$, and disjunctive datalog queries, when $q\in C{Q}^{\neg }$. Numerous interesting further work problems can be addressed, such as: