Query Repairs

When querying a database, it may happen that the query result includes some undesired tuples and/or that some desired tuples are missing. In such cases, it is often necessary to adjust the query to ensure that the result aligns with expectations, i.e., it includes the desired tuples and omits the undesired ones.

We propose a formalization of the above problem through the notion of query repairs, as follows. We assume that we are given a query $q$ and a set of labeled examples, by which we mean pairs $(I,\text{a})$ with $I$ a database instance and a a tuple of values from the active domain of $I$, labeled as positive or negative to indicate whether a is desired or undesired as an answer on input $I$. In the above example, for instance, the input query is $q$ and there is a positively labeled example $(I,\text{Nosferatu})$ that $q$ fails to fit. A query repair, then, is a query $q^{\prime }$ that fits the given labeled examples and “differs from $q$ in a minimal way”. Different notions of query repair arise by using different means to formalize what it means for two queries to differ in a minimal way. Besides requiring that $q^{\prime }$ fits the labeled examples and differs minimally from $q$, depending on the context, it may be natural to additionally require that $q\subseteq q^{\prime }$ or that $q^{\prime }\subseteq q$. This leads to further refinements of the notion of a query repair, namely query generalization and query specialization, respectively, which we also investigate.

We propose a broad framework for defining what it means for two queries to differ in a minimal way, based on a proximity pre-order $⪯$, i.e., a family of pre-orders ${⪯}_q$ (one for each query $q$), where $q^{\prime }{⪯}_q{q}^{\prime \prime }$ asserts that query $q^{\prime }$ is at least as close to $q$ as $q^{\prime \prime }$. A query $q^{\prime }$ is then a $⪯$-repair of a query $q$ if $q^{\prime }$ fits the given labeled examples and there is no query $q^{\prime \prime }$ with the same property such that $q^{\prime \prime }{\prec }_q{q}^{\prime }$. We instantiate this framework for conjunctive queries (CQs), focussing mainly on two kinds of proximity pre-orders: the containment-of-difference proximity pre-order ${⪯}^{\text{cod}}$, based on query containment, and the edit-distance proximity pre-order ${⪯}^{\text{edit-dist}}$, based on a distance metric between queries defined in terms of a suitably adapted version of edit distance. To be more precise, $q_1{⪯}_q^{\text{cod}}{q}_2$ if for every instance $I$, the symmetric difference of $q_1(I)$ and $q(I)$ is contained in the symmetric difference of $q_2(I)$ and $q(I)$. Moreover, $q_1{⪯}_q^{\text{edit-dist}}{q}_2$ if the edit distance between the homomorphism core of $q_1$ and the homomorphism core of $q$ is no larger than the edit distance between the homomorphism core of $q_2$ and the homomorphism core of $q$, modulo variable renaming.

The problem of constructing a query that fits a given set of labeled data examples has been studied extensively and is known under different names such as reverse engineering, query learning, or fitting; see for instance [25] which offers a comparison of several fitting algorithms for CQs. Recently, in [9], extremal variants of the fitting problem for CQs were studied, including (weakly/strongly) most-general fitting and most-specific fitting. There, the input consists of a set of positive and negative examples and the task is to find a most specific CQ, or a most general CQ, that fits them. We can think of such extremal fitting problems as constrained versions of the fitting problem for CQs where an additional requirement is put on the output query. In the same spirit, the query repair problem can also be viewed as a constrained version of fitting where the input now includes, in addition, a CQ $q$, and the output is required to be a fitting CQ that differs minimally from $q$.¹¹1For the trivial proximity pre-order ${⪯}_q$ relating every CQ to every CQ, the query repair problem coincides with the fitting problem. As a part of our contributions, we will establish close relationships between query repair problems and extremal fitting problems.

As usual, a schema $𝒮$ is a set of relation symbols, each with associated arity. A database instance over $𝒮$ is a finite set $I$ of facts of the form $R(a_1,\mathrm{\dots },a_n)$ where $R\in 𝒮$ is a relation symbol of arity $n$ and $a_1,\mathrm{\dots },a_n$ are values. We use $\mathrm{𝑎𝑑𝑜𝑚}(I)$ to denote the set of all values used in $I$. We can then view a query over a schema $𝒮$, semantically, as a function $q$ that maps each database instance $I$ over $𝒮$ to a set of $k$-tuples $q(I)\subseteq \mathrm{𝑎𝑑𝑜𝑚}{(I)}^k$, where $k\ge 0$ is the arity of the query. A query of arity zero is called a Boolean query. We write $q_1\subseteq q_2$ and say that $q_1$ is contained in $q_2$ if $q_1(I)\subseteq q_2(I)$ for all database instances $I$. Two queries $q_1$ and $q_2$ are equivalent, written $q_1\equiv q_2$, if $q_1\subseteq q_2$ and $q_2\subseteq q_1$.

A data example for a $k$-ary query $q$ consists of a database instance $I$ together with a $k$-tuple of values. We denote by $[[q]]$ the set of all data examples $(I,\text{a})$ for which it holds that $\text{a}\in q(I)$. A labeled example is a data example that is labeled as positive or as negative. By a collection of labeled examples we mean a pair $E=(E^{+},E^{-})$, where $E^{+}$ and $E^{-}$ are sets of examples. Here, the data examples in $E^{+}$ are considered as positive examples, and the data examples in $E^{-}$ are considered as negative examples. A query $q$ fits $E=(E^{+},E^{-})$ if $\text{a}\in q(I)$ for each $(I,\text{a})\in E^{+}$ and $\text{a}\notin q(I)$ for each $(I,\text{a})\in E^{-}$. In other words, $q$ fits $E=(E^{+},E^{-})$ if $E^{+}\subseteq [[q]]$ and $E^{-}\cap [[q]]=\mathrm{\varnothing }$. Here, we assume that $q$ has the same arity as the data examples in $E^{+}$ and $E^{-}$. We will often abuse notation and write that $q$ fits $E^{+}$ (or that $q$ fits $E^{-}$), meaning that $q$ fits $(E^{+},\mathrm{\varnothing })$ (respectively, $q$ fits $(\mathrm{\varnothing },E^{-})$).

We will be focusing specifically on conjunctive queries. By a $k$-ary conjunctive query (CQ) over a schema $𝒮$, we mean an expression of the form $q(\text{x})\text{ :- }{\alpha }_1,\mathrm{\dots },{\alpha }_n$ where $\text{x}=x_1,\mathrm{\dots },x_k$ is a sequence of variables and each ${\alpha }_i$ is a relational atom that uses a relation symbol from $𝒮$ and no constants. Note: the restriction to queries without constants is not essential for our results (cf. [25, Remark 2.3]) but simplifies the presentation.

The variables in x are called answer variables and the other variables used in the atoms ${\alpha }_i$ are the existential variables. Each answer variable is required to occur in at least one atom ${\alpha }_i$, a requirement known as the safety condition. For CQs $q,q^{\prime }$ of the same arity, we denote their conjunction by $q\wedge q^{\prime }$ (where, for instance, the conjunction of $q_1(x,y)\text{ :- }R(x,y,z)$ and $q_2(x,x)\text{ :- }S(x,z)$ is $q(x,x)\text{ :- }R(x,x,z),S(x,z^{\prime })$). With the size of a CQ, denoted $|q|$, we mean the number of atoms in it. The query output $q(I)$ is defined as usual, cf. any standard database textbook.

Every CQ $q(x_1,\mathrm{\dots },x_k)$ has a canonical example $e_q$, namely the data example $(I_q,⟨x_1,\mathrm{\dots },x_k⟩)$, where $I_q$ is the database instance (over the same schema as $q$) whose active domain consists of the variables in $q$ and whose facts are the atomic formulas in $q$.

Given data examples $e=(I,\text{a})$ and $e^{\prime }=(J,\text{b})$ over the same schema and with the same number of distinguished elements, a homomorphism $h:e\to e^{\prime }$ is a map from $\text{adom}(I)$ to $\text{adom}(J)$ that preserves all facts and such that $h(\text{a})=\text{b}$. When such a homomorphism exists, we say that $e$ “homomorphically maps to” $e^{\prime }$ and write $e\to e^{\prime }$. We say that $e$ and $e^{\prime }$ are homomorphically equivalent if $e\to e^{\prime }$ and $e^{\prime }\to e$. It then holds that $e\in [[q]]$ iff $e_q\to e$. Furthermore, the well-known Chandra-Merlin theorem states that $q\subseteq q^{\prime }$ holds iff $e_{q^{\prime }}\to e_q$.

A data example $e$ is said to be a core if every homomorphism $h:e\to e$ is surjective. It is well known that for every data example $e=(I,\text{a})$ there is a subinstance $I^{\prime }\subseteq I$ such that $(I^{\prime },\text{a})$ is a core and such that $(I,\text{a})$ and $(I^{\prime },\text{a})$ are homomorphically equivalent. Moreover, such $(I^{\prime },\text{a})$ is unique up to isomorphism, and may be referred to as the core of $e$, denoted $\text{core}(e)$. We say that a CQ $q$ is a core if its canonical example $e_q$ is a core.

The direct product of two database instances, denoted $I\times J$, is the database instance containing all facts $R(⟨a_1,b_1⟩,\mathrm{\dots },⟨a_n,b_n⟩)$ over the domain $adom(I)\times adom(J)$ such that $R(a_1,\mathrm{\dots },a_n)$ is a fact of $I$ and $R(b_1,\mathrm{\dots },b_n)$ is a fact of $J$. This naturally extends to data examples: $(I,⟨a_1,\mathrm{\dots },a_k⟩)\times (J,⟨b_1,\mathrm{\dots },b_k⟩)=(I\times J,⟨⟨a_1,b_1⟩,\mathrm{\dots },⟨a_k,b_k⟩⟩)$.

Fix a query language $ℒ$. A proximity pre-order $⪯$ for $ℒ$ is a family of pre-orders ${⪯}_q$, one for every $q\in ℒ$, satisfying the following conditions:

Conservativeness

For all $q,q^{\prime }\in ℒ$, $q{⪯}_q{q}^{\prime }$.

Syntax independence

Whenever $q_1^{\prime }\equiv q_1$, $q_2^{\prime }\equiv q_2$ and $q_3^{\prime }\equiv q_3$, then $q_1{⪯}_{q_2}{q}_3$ iff $q_1^{\prime }{⪯}_{q_2^{\prime }}{q}_3^{\prime }$.

Let $q\in ℒ$, and let $E$ a collection of labeled examples (of the same arity as $q$). We call the pair $(q,E)$ an annotated $ℒ$-query. The following are the 3 main notions studied in this paper.

• $\mathrm{■}$

  A $⪯$-repair for $(q,E)$ is a query $q^{\prime }\in ℒ$ such that (i) $q^{\prime }$ fits $E$, and (ii) there is no $q^{\prime \prime }\in ℒ$ with $q^{\prime \prime }{\prec }_q{q}^{\prime }$ that satisfies (i).

• $\mathrm{■}$

  A $⪯$-generalization for $(q,E)$ is a query $q^{\prime }\in ℒ$ such that (i) $q^{\prime }$ fits $E$ and $q\subseteq q^{\prime }$ and (ii) there is no $q^{\prime \prime }\in ℒ$ with $q^{\prime \prime }{\prec }_q{q}^{\prime }$ that satisfies (i).

• $\mathrm{■}$

  A $⪯$-specialization for $(q,E)$ is a query $q^{\prime }\in ℒ$ such that (i) $q^{\prime }$ fits $E$ and $q^{\prime }\subseteq q$, and (ii) there is no $q^{\prime \prime }\in ℒ$ with $q^{\prime \prime }{\prec }_q{q}^{\prime }$ that satisfies (i).

(where $q_1{\prec }_q{q}_2$ is short for $q_1{⪯}_q{q}_2$ and $q_2{⋠}_q{q}_1$).

Note: under this definition, $⪯$-specializations and $⪯$-generalizations need not be $⪯$-repairs.

Conservativeness and syntax-independence are minimal conditions on $⪯$ needed to yield intuitive behavior for query repairs: conservativeness ensures that if the input query $q$ already fits the given examples, then $q$ is its own $⪯$-repair, while syntax independence ensures that equivalent queries have equivalent $⪯$-repairs.

In the rest of this paper, we will restrict attention to CQs. That is, $ℒ$ is the class of CQs.

Several algorithmic problems arise, all parameterized with a proximity pre-order $⪯$.

We will also study the analogous algorithmic problems for $⪯$-generalization and $⪯$-specialization, defined in the expected way.

In all of the above problems, the input queries and examples are assumed to be compatible in terms of their arity. Moreover, in our complexity analyses, we will assume a fixed (constant) query arity $k\ge 0$. This is in fact only necessary for some of the upper bounds in Sect. 4.2.

In this section, we study notions of query generalization, query specialization and query repair defined based on query containment. For generalization and specialization, it seems intuitively clear what the definition should be. Let $(q,E)$ be an annotated CQ. Then

• $\mathrm{■}$

  a containment-based generalization for $(q,E)$ is a CQ $q^{\prime }$ that fits $E$ and such that $q\subseteq q^{\prime }$ and there is no CQ $q^{\prime \prime }$ that fits $E$ with $q\subseteq q^{\prime \prime }⊊q^{\prime }$.

• $\mathrm{■}$

  a containment-based specialization for $(q,E)$ is a CQ $q^{\prime }$ that fits $E$ and such that $q^{\prime }\subseteq q$ and there is no CQ $q^{\prime \prime }$ that fits $E$ with $q^{\prime }⊊q^{\prime \prime }\subseteq q$.

It is less immediately clear what the right query containment-based definition of query repairs should be. As it turns out, the above notions of query generalization and query specialization can be viewed as query generalizations and query specializations with respect to the following natural proximity pre-order (cf. also [24, 29, 4]).

Recall that $[[q]]$ denotes the set of all positive examples of a query $q$. Therefore, $[[q]]\oplus [[q_i]]$ denotes the set of all examples on which $q_i$ disagrees with $q$. Thus, $q_1{⪯}_q^{\text{cod}}{q}_2$ means that the set of examples on which $q$ and $q_1$ disagree is a subset of the set of examples on which $q$ and $q_2$ disagree (cod stands for “containment of difference”). It is easy to see that ${⪯}^{\text{cod}}$ is indeed a proximity pre-order. Moreover, it gives rise to the intended containment-based notions of query generalization and specialization:

It also follows that ${⪯}^{\text{cod}}$-generalizations and ${⪯}^{\text{cod}}$-specializations are ${⪯}^{\text{cod}}$-repairs. This furthermore suggests ${⪯}^{\text{cod}}$-repairs as a (seemingly) natural containment-based notion of query repair. Next, we will study ${⪯}^{\text{cod}}$-generalizations, ${⪯}^{\text{cod}}$-specializations, and ${⪯}^{\text{cod}}$-repairs. Our main findings can be summarized as follows: ${⪯}^{\text{<em class="ltx\_emph ltx\_font\_upright" style="font-size:70\%;">cod</em>}}$-generalizations and ${⪯}^{\text{<em class="ltx\_emph ltx\_font\_upright" style="font-size:70\%;">cod</em>}}$-specializations are well-behaved notions, although the latter do not always exist (Example 1.3) and can be too plentiful (Example 4.14). The associated existence, verification, and construction problems admit effective algorithms, although often of super-polynomial complexity. The more general ${⪯}^{\text{<em class="ltx\_emph ltx\_font\_upright" style="font-size:70\%;">cod</em>}}$-repairs exhibits counter-intuitive behavior.

In this section, we study proximity pre-orders based on distance metrics. In particular, we propose and study a variant of edit distance for CQs. We also study proximity pre-orders based on several other natural distance metrics. Our main findings can be summarized as follows: edit distance, suitably defined, yields a proximity pre-order that avoids some of the problems of ${⪯}^{\text{cod}}$. We also show that other natural distance metrics induce proximity pre-orders that are less well behaved.

One can think of a semantic distance metric for CQs as a distance metric (in the standard sense) on the equivalence classes of CQs. Every semantic distance metric, and in fact every weak semantic distance metric, induces a pre-order.

We study ${⪯}^{dist}$-repairs for several distance metrics. Besides the algorithmic problems of repair existence, verification and construction, we also consider the following natural fitting problem that is closely related to query repairs based on distance metrics: