11institutetext:  Free University of Bozen-Bolzano, Italy

# Complete Approximations of Incomplete Queries

Julien Corman  Werner Nutt  Ognjen Savković

###### Abstract

This paper studies the completeness of conjunctive queries over a partially
complete database and the approximation of incomplete queries. Given a query
and a set of completeness rules (a special kind of tuple generating
dependencies) that specify which parts of the database are complete, we
investigate whether the query can be fully answered, as if all data were
available. If not, we explore reformulating the query into either Maximal
Complete Specializations (MCSs) or the (unique up to equivalence) Minimal
Complete Generalization (MCG) that can be fully answered, that is, the best
complete approximations of the query from below or above in the sense of query
containment. We show that the MSG can be characterized as the least fixed-
point of a monotonic operator in a preorder. Then, we show that an MCS can be
computed by recursive backward application of completeness rules. We study the
complexity of both problems and discuss implementation techniques that rely on
an ASP and Prolog engines, respectively.

##  1 Introduction

Completeness is one of the classical dimensions of data quality, well studied
both in the context of relational data [4, 5, 7, 1] and more recently in the
context of knowledge graphs [12, 6]. An information system may be incomplete
because some data has not yet been inserted, or simply because some
information is unavailable for certain records. As a consequence, a query $Q$
that retrieves data may itself be incomplete, in the sense that when $Q$ is
evaluated over the actual (incomplete) database, some answers to $Q$ over the
ideal (complete) database are missing. Similarly, if $Q$ produces statistics
(e.g., count answers), then these statistics may be incorrect.

On the other hand, part of the data is often _known_ to be complete. This
information may be sufficient to confirm that $Q$ is complete, or, if this is
not the case, to produce a query that is complete and _approximates_ $Q$. The
latter task is the one investigated in this paper. More precisely, we consider
two natural strategies to approximate $Q$. The first strategy consists in
producing a complete query $Q^{\prime}$ that is more _general_ than $Q$, in
the sense that the answers to $Q$ over the ideal (complete) database are a
subset of the answers to $Q^{\prime}$. In a scenario where one is searching
for a specific piece of information, this strategy ensures that it will be
retrieved. Instead, the second strategy consists in producing a complete query
that is more _specific_ than $Q$. This can be useful for statistics: the
answers to $Q$ may not be complete yet (e.g., for a whole country), but one
may already publish partial statistics (e.g., for a given region) that are
guaranteed to be correct.

As a (toy) running example, we will consider a database instance $D$ of a
hypothetical school information system in the Italian province of Bolzano.
Following the approach of [8, 13, 10], one can express which (parts of which)
tables in $D$ are known to be complete, using so-called _table-completeness
statements_ (TCSs). For example, one may write three TCSs that say that $D$
contains _(i)_ “all primary schools,” _(ii)_ “all pupils attending a school in
the district of Merano,” and _(iii)_ “all English learners that are pupils at
a primary school,” respectively. Conceptually, the TCS _(ii)_ for instance
asserts that for every pupil enrolled in a school in the district of Merano,
there exists a corresponding record in $D$’s “pupils” table.

Now consider the query $Q$ that retrieves all language learners enrolled in a
primary school in the district of Merano. The three TCSs above are not
sufficient to infer that $Q$ is complete. However, one can approximate $Q$ by
either generalizing or specializing it. For instance, the query $Q^{+}$ that
retrieves all pupils enrolled in a primary school in the district of Merano
generalizes $Q$, and is complete, from TCSs _(i)_ and _(ii)_. If the purpose
of $Q$ was to retrieve a specific pupil (among the ideal answers to $Q$), then
the answers to $Q^{\prime}$ are guaranteed to contain this pupil. Conversely,
the query $Q^{-}$ that retrieves all English learners enrolled in a primary
school in the district of Merano specializes $Q$, and is also complete, from
TCSs _(i)_ , _(ii)_ and _(iii)_. If the purpose of $Q$ was to publish
statistics (e.g., its number of answers), then partial statistics (e.g., the
number of answers to $Q$ restricted to English learners, a.k.a. $Q^{-}$) can
already be published.

Previous work studied the problem of checking whether a conjunctive query (CQ)
is complete wrt to a set of TCSs. In particular, it was shown in [13] that
this problem can be reduced to the classical problem of query containment [2].
Then in [10], this same problem was reduced to reasoning in Datalog programs
under answer-set semantics, extending the setting by considering the presence
of keys, foreign keys, and finite domain constraints. We pursue this work by
studying the two types of complete approximations (generalization and
specialization) sketched above, still focusing on CQs.

#### Contributions

Among the complete CQs that generalize a CQ $Q$, we identify the most specific
ones, which we call _Minimal Complete Generalizations_ (MCGs). And we define
the _Maximal Complete Specializations_ (MCSs) of $Q$ analogously. Our main
contributions can be summarized as follows:

  * •

We show that if $Q$ admits an MCG, then it is unique up to query equivalence.
To this end, we introduce a generalization operator that maps incomplete
queries to “less” incomplete ones, and show that a fixed-point of this
operator (modulo query equivalence) is a complete generalization. This yields
an algorithm to compute an MCG. We also study the computational complexity of
the corresponding decision problem.

  * •

We show that there can be multiple MCSs, or (infinitely many) complete
specializations but no maximal one. As a consequence, we restrict our search
space for an MCS to queries of a given bounded size. For this latter problem,
we first propose an algorithm that finds MCSs (if any) that can be obtained
without adding any atom to $Q$, leveraging unification between the query under
construction and atoms in TCSs. We then extend this idea to identify MCSs that
may contain more atoms.

  * •

We discuss implementation techniques for finding MSG and MCSs using forward
rule application in Datalog and backward rule application in Prolog,
respectively.

#### Organization

In Section 2, we recall basic definitions from database theory and formally
introduce the problem of query completeness and relevant characterization
theorems. In Sections 3 and 4, we discuss the generalization and
specialization problems, respectively. Section 5 discusses corresponding
implementation techniques.

##  2 Query Completeness

#### Preliminaries

We adopt standard notation from databases. We assume an infinite set each of
relation symbols, constants, and variables. The constants make up the set
${\sf dom\/}$ (the _domain_). Terms are constants or variables. For variables,
we use upper-case, for constants lower-case letters, tuples are indicated by
an overline, like $\bar{c}$. For a relation symbol $R$ with arity $n$, an
_atom_ is an expression $R(t_{1},\ldots,t_{n})$, where $t_{1},\ldots,t_{n}$
are terms. A database _instance_ $D$ is a finite set of ground atoms (facts),
that is, atoms that contain only constants. A _conjunctive query_ (CQ) is
written as $Q(\bar{u})\leftarrow B$, where $Q(\bar{u})$ is an atom and $B$ a
conjunction of atoms. We call $B$ the _body_ of $Q$ and $\bar{u}$ the _head
terms._ A CQ is _safe_ if all variables of $\bar{u}$ occur in $B$. Given a CQ
$Q(\bar{u})\leftarrow B$ and an instance $D$, a tuple $\alpha\bar{u}$ is an
_answer_ of $Q$ over $D$, written $Q(D)$, if $\alpha$ is an assignment of
variables from $Q$ to ${\sf dom\/}$ such that $\alpha B\subseteq D$. A query
$Q$ is _contained_ in a query $Q^{\prime}$, written $Q\sqsubseteq Q^{\prime}$,
if for every database instance $D$ it holds that $Q(D)\subseteq
Q^{\prime}(D)$. We say that $Q$ and $Q^{\prime}$ are _equivalent_ if
$Q\sqsubseteq Q^{\prime}$ and $Q^{\prime}\sqsubseteq Q$. The query $Q$ is
_strictly contained_ in $Q^{\prime}$ if $Q$ is contained in $Q^{\prime}$ and
$Q^{\prime}$ is not equivalent to $Q$. If $Q$ is contained in $Q^{\prime}$,
then $Q^{\prime}$ is _more general_ than $Q$, and $Q$ is _more special_ than
$Q^{\prime}$.

#### Completeness Theory

When stating that data is potentially incomplete, one must have a conceptual
complete reference. We model an _incomplete database_ in the style of [9] as a
pair of database instances $\mathcal{D}=({D}^{i},{D}^{a})$, where
${D}^{a}\subseteq{D}^{i}$. Here, ${D}^{i}$ is called the _ideal_ state and
${D}^{a}$ the _available_ state. In an application, the state stored in a DBMS
is the available state, which often represents only a part of the facts that
hold in reality. The facts holding in reality constitute the ideal state,
which however is unknown.

Given a query $Q$ and an incomplete database $\mathcal{D}=({D}^{i},{D}^{a})$,
we say that $Q$ is _complete over $D$_ if $Q({D}^{i})=Q({D}^{a})$ and we write
$\mathcal{D}\models\textsl{Compl}(Q)$.

To specify that parts of a relation instance are complete, we introduce a kind
of metadata, which we call _table completeness_ (TC) statements (or TCS for
short). A TCS, written $\textsl{Compl}(R(\bar{s});\,G)$, has two components, a
relational atom $R(\bar{s})$, where $\bar{s}$ is a tuple of terms, and (a
possibly empty) conjunction of atoms $G$, called _condition._ Intuitively, a
TC statement $\textsl{Compl}(R(\bar{s});\,G)$ asserts that table $R$ is
complete for all tuples that match $\bar{s}$ and can be joined with $G$. We
denote a TC statement generically as $C$.

To define the semantics of a TCS $C$, we associate to it a query
$Q_{C}(\bar{s})\leftarrow R(\bar{s}),G$. Then $C$ is satisfied by
$\mathcal{D}=({D}^{i},{D}^{a})$, written
$\mathcal{D}\models\textsl{Compl}(R(\bar{s});\,G)$, if
$Q_{C}({D}^{i})\subseteq R({D}^{a})$. This means that the ideal instance
${D}^{i}$ is used to determine the tuples in the ideal instance $R({D}^{i})$
of $R$ that match $\bar{s}$ and satisfy $G$, and that the statement $C$ is
satisfied if these tuples are present in the available version $R({D}^{a})$.
If no TC statement is associated with a relation then we do not know anything
about the completeness of that relation.

Let $\mathbf{C}$ be a set of TC statements. We say that $\mathbf{C}$ entails
the completeness of $Q$, written $\mathbf{C}\models\textsl{Compl}(Q)$, if for
every $\mathcal{D}$ it holds that $\mathcal{D}\models\mathbf{C}$ implies
$\mathcal{D}\models\textsl{Compl}(Q)$.

######  Example 2.1.

We consider a simplified database “schoolBolzano”, modeling schools in the
province of Bolzano. It consists of the three tables below:

$\displaystyle\textit{pupil\/}({\mathit{pname\/}},\mathit{code\/},\mathit{sname\/}),$
$\displaystyle\textit{school\/}({\mathit{sname\/}},\mathit{type\/},\mathit{district\/}),$
$\displaystyle\textit{learns\/}({\mathit{pname\/}},{\mathit{lang\/}}).$

The table pupil contains for each pupil the name, the class and the school the
pupil attends. The table school records for each school the name, the type
(e.g., primary or middle school), and its school district. Finally, the table
learns records which pupil learns which language. Next, we assume the
following completeness statements:

$\displaystyle C_{\textit{sp}}$ $\displaystyle\colon$
$\displaystyle\textsl{Compl}(\textit{school\/}(S,\mathit{primary\/},D);\,\textit{true}),$
$\displaystyle C_{\textit{pb}}$ $\displaystyle\colon$
$\displaystyle\textsl{Compl}(\textit{pupil\/}(N,C,S);\,\textit{school\/}(S,T,\mathit{merano\/})),$
$\displaystyle C_{\textit{enp}}$ $\displaystyle\colon$
$\displaystyle\textsl{Compl}(\textit{learns\/}(N,\mathit{english\/});\,\textit{pupil\/}(N,C,S),\textit{school\/}(S,\mathit{primary\/},D)).$

The statements say that the database contains all primary schools
($C_{\textit{sp}}$), all pupils attending a school in the district of Merano
($C_{\textit{pb}}$), and all English learners that are pupils attending a
primary school ($C_{\textit{enp}}$).

For instance, let
$D^{a}=\\{\textit{school\/}(\mathit{goethe\/},\mathit{primary\/},\mathit{merano\/}\\})$
and
$D^{i}=D^{a}\cup\\{\textit{pupil\/}(\mathit{john},1,\mathit{goethe\/})\\}$.
Then, $(D^{i},D^{a})\models C_{\textit{sp}}$, but $(D^{i},D^{a})\not\models
C_{\textit{pb}}$.

Now consider the query for the “names of all pupils that attend a primary
school in the district of Merano”:

$\displaystyle Q_{\textit{ppb}}(N)\leftarrow{}\
\textit{pupil\/}(N,C,S),\textit{school\/}(S,\mathit{primary\/},\mathit{merano\/}).$

Intuitively, the query is complete because our database contains all records
of pupils from primary schools in the district of Merano ($C_{\textit{pb}}$)
and it contains all such schools ($C_{\textit{sp}}$).

Alternatively, let us consider the query for “the names of all pupils that
attend a primary school in the district of Merano and that learn some
language”:

$\displaystyle Q_{\textit{pbl}}(N)\leftarrow{}\
\textit{pupil\/}(N,C,S),\textit{school\/}(S,\mathit{primary\/},\mathit{merano\/}),\textit{learns\/}(N,L)$

This query is not complete since some language learners (of a language other
than English) may be missing from the database. ∎

#### Reasoning about Query Completeness

To reason about completeness, we define for every set $\mathbf{C}$ of TC
statements the operator $T_{\mathbf{C}}$ that maps database instances to
database instances. If $C$ is a TC statement about $R$, then we define

$T_{C}(D):=\\{R(\bar{t})\mid\bar{t}\in Q_{C}(D)\\}$ and
$T_{\mathbf{C}}(D):=\bigcup_{C\in\mathbf{C}}T_{C}(D).$ (1)

Since all queries $Q_{C}$ are monotonic, the operator $T_{\mathbf{C}}$ is
monotonic in that for any $D\subseteq D^{\prime}$ it holds that
$T_{\mathbf{C}}(D)\subseteq T_{\mathbf{C}}(D^{\prime})$. Moreover, for every
instance $D$, the pair $(D,T_{\mathbf{C}}(D))$ is an incomplete database that
satisfies $\mathbf{C}$, and $T_{\mathbf{C}}(D)$ is the smallest set (wrt set
inclusion) for which this holds. Below we cite a proposition that summarizes
the connection between the $T_{\mathbf{C}}$ operator and the satisfaction of
the set $\mathbf{C}$ by a in incomplete database:

######  Proposition 2.2 (${T_{\mathbf{C}}}$ Operator [10, Proposition 1]).

Let $\mathbf{C}$ be a set of TC statements. Then

  * •

$T_{\mathbf{C}}(D)\subseteq D$, for all database instances $D$;

  * •

$(D^{i},D^{a})\models\mathbf{C}$ iff $T_{\mathbf{C}}(D^{i})\subseteq D^{a}$,
for all $D^{a}\subseteq D^{i}$.

In [10] it has been shown that, similar to containment checking [2],
completeness checking can be reduced to the question whether a test query
returns a specific result over a test database. Below, we summarize that
approach.

In what follows, we always consider a set of TC statements $\mathbf{C}$ and a
conjunctive query $Q$ defined by the rule
${Q(\bar{u})}\leftarrow{R_{1}(\bar{t}_{1}),\ldots,R_{n}(\bar{t}_{n})}$. We
define the set of facts $\mathit{D}_{Q}$, which we call the _canonical
database_ of $Q$, obtained by freezing the atoms in the body of
$Q$.111“Freezing” variables is a well-known concept in logic programming and
database theory, which allows one to treat a variable like a constant. Thus,

$\mathit{D}_{Q}=\\{R_{1}(\theta\bar{t}_{1}),\ldots,R_{n}(\theta\bar{t}_{n})\\},$

where $\theta$ is the substitution that maps each variable $X$ to the “frozen
version” $\theta X$ of $X$.

To check whether $Q$ is complete one applies $T_{\mathbf{C}}$ to
$\mathit{D}_{Q}$ and verifies whether $Q$ can retrieve the frozen tuple of
distinguished variables.

######  Theorem 2.3 (Characterization of Completeness [10, Theorem 2]).

Let $\mathbf{C}$ be a set of TC statements, and $Q(\bar{u})\leftarrow B$ be a
conjunctive query. Then

$\mathbf{C}\models\textsl{Compl}(Q)\quad\Longleftrightarrow\quad\theta\bar{u}\in
Q(T_{\mathbf{C}}(\mathit{D}_{Q})).$

######  Example 2.4.

We illustrate this theorem with our running example. Suppose
$\mathcal{D}=({D}^{i},{D}^{a})$ satisfies
$\\{C_{\textit{sp}},C_{\textit{pb}}\\}$. Consider an answer, say $n^{\prime}$,
returned by $Q_{\textit{ppb}}$ over the ideal instance ${D}^{i}$. Then
${D}^{i}$ contains two atoms of the form
$\textit{pupil\/}(n^{\prime},c^{\prime},s^{\prime})$ and
$\textit{school\/}(s^{\prime},\mathit{primary\/},\mathit{merano\/})$. Now, due
to $C_{\textit{sp}}$, also ${D}^{a}$ contains
$\textit{school\/}(s^{\prime},\mathit{primary\/},\mathit{merano\/})$, and due
to $C_{\textit{pb}}$, the atom
$\textit{pupil\/}(s^{\prime},c^{\prime},\mathit{\mathit{goethe\/}\/})$ is in
${D}^{a}$, too. Consequently, $Q_{\textit{ppb}}$ returns $n^{\prime}$ also
over ${D}^{a}$. Since ${D}^{i}$ and ${D}^{a}$ were arbitrary, this shows that
$\\{C_{\textit{sp}},C_{\textit{pb}}\\}\models\textsl{Compl}(Q_{\textit{ppb}})$.
∎

######  Example 2.5 (Complete Generalizations and Specializations).

We recall query $Q_{\textit{pbl}}(N)$ that was incomplete given the
assumptions. One way to obtain more general queries is by dropping some of the
query atoms (that is, relaxing query conditions). Hence, if we drop the learns
atom we obtain a complete generalization of $Q$:

$Q_{\textit{pbl}}^{\textit{gen}}(N)\leftarrow{}\textit{pupil\/}(N,C,S),\textit{school\/}(S,\mathit{primary\/},\mathit{merano\/})$

which is the same as query $Q_{\textit{ppb}}$ and is complete.

To obtain query specializations one can turn variables into constants or add
new atoms to the body (or both). For instance, we observe if in
$Q_{\textit{pbl}}(N)$ we replace $\textit{learns\/}(N,L)$ with
$\textit{learns\/}(N,\mathit{english\/})$ we obtain a query:

$\displaystyle Q_{\textit{pbl}}^{\textit{spec}}(N)\leftarrow{}$
$\displaystyle\
\textit{pupil\/}(N,C,S),\textit{school\/}(S,\mathit{primary\/},\mathit{merano\/}),\textit{learns\/}(N,\mathit{english\/})$

which is complete, since $C_{\textit{enp}}$ guarantees completeness of the
learns-atom. ∎

##  3 Query Generalization

In this section, we study the problem of finding a complete generalization of
a (possibly incomplete) query. We restrict our scope to the case where all
queries (input query and generalizations) are CQs.

First, we rephrase the well-known characterization of containment among
conjunctive queries due to Chandra and Merlin [2] in our formalism.

######  Proposition 3.1 (Characterization of Containment).

Let $Q(\bar{u})\leftarrow B$ and $Q^{\prime}({\bar{u}}^{\prime})\leftarrow
B^{\prime}$ be conjunctive queries. Then

$Q\sqsubseteq Q^{\prime}\quad\Longleftrightarrow\quad\theta\bar{u}\in
Q^{\prime}(\mathit{D}_{Q}).$

The proposition holds because $Q$ is contained in $Q^{\prime}$ iff there
exists a homomorphism $\delta$ from $Q^{\prime}$ to $Q$. Such a $\delta$ can
be seen as an assignment of constants and variables in $D_{Q}$ to the
variables in $Q^{\prime}$ that satisfies $Q^{\prime}$ and returns the tuple of
head terms $\theta\bar{u}$ of $Q$.

We say that a query $Q^{\prime}$ is a _complete generalization_ of $Q$ wrt a
set of TC statements $\mathbf{C}$ if $Q^{\prime}$ is more general than $Q$ and
$Q^{\prime}$ is complete wrt $\mathbf{C}$.

######  Definition 3.2 (Minimal Complete Generalization).

A query $Q^{\prime}$ is a _minimal complete generalization_ (MCG) of $Q$ wrt a
set of TC statements $\mathbf{C}$ if:

  * •

$Q^{\prime}$ is a complete generalization of $Q$ wrt $\mathbf{C}$, and

  * •

it is a minimal one, that is, there exists no query $Q^{\prime\prime}$ such
that $Q^{\prime\prime}$ is a complete generalization of $Q$ and
$Q^{\prime\prime}$ is strictly contained in $Q^{\prime}$.

#### Computing Minimal Complete Generalizations

In the following we investigate properties of MCGs. We first show that in our
search for MCGs of $Q$ it is sufficient to concentrate on _subqueries_ of $Q$,
that is, (safe) queries obtained by dropping some atoms from the body of $Q$.
Note that if $Q_{0}$ is a subquery of $Q$, then $Q$ is contained in $Q_{0}$.
More specifically, we will show the following proposition.

######  Proposition 3.3 (MCGs are Subqueries).

Let $\mathbf{C}$ be a set of TC statements, $Q$ a conjunctive query, and
$Q^{\prime}$ a complete generalization of $Q$ wrt $\mathbf{C}$. Then there
exists a subquery $Q_{0}$ of $Q$ such that $Q_{0}\sqsubseteq Q^{\prime}$ and
$Q_{0}$ is a complete generalization of $Q$.

For our proof we rely on the properties of minimal conjunctive queries. We
remind the reader that $Q$ is _minimal_ if all its subqueries are strictly
more general that $Q$, or, in other words, if $Q$ does not have redundant
atoms. This means that for any subquery $Q_{0}$ obtained from $Q$ by dropping
some of the atoms in $Q$ it holds that $Q_{0}\not\sqsubseteq Q$. Every
conjunctive query is equivalent to a minimal query [2].

If $Q(\bar{u})\leftarrow B$ is a query, and $\alpha$ a substitution, then with
$\alpha Q$ we denote the query $\tilde{Q}(\alpha\bar{u})\leftarrow\alpha B$.
We call $\alpha Q$ an _instantiation_ of $Q$.

Next we identify properties of minimal queries that we use later in the
proofs. In particular, we show that a minimal query $Q$ is complete iff the
image of the frozen query $D_{Q}$ under $T_{\mathbf{C}}$ comprises all of
$D_{Q}$. Moreover we show that any instantiation of a complete minimal query
is again complete.

######  Lemma 3.4 (Completeness of Minimal Queries).

Let $\mathbf{C}$ be a set of TC statements, $Q(\bar{u})\leftarrow B$ a minimal
conjunctive query, and $\alpha$ a substitution. Then

  1. 1.

$\mathbf{C}\models\textsl{Compl}(Q)\quad\Longleftrightarrow\quad\mathit{D}_{Q}\subseteq
T_{\mathbf{C}}(\mathit{D}_{Q});$

  2. 2.

$\mathbf{C}\models\textsl{Compl}(Q)\quad\Longrightarrow\quad\mathbf{C}\models\textsl{Compl}(\alpha
Q)$.

###### Proof.

Claim 1. $(\Leftarrow)$ This direction holds for all conjunctive queries: if
$D_{Q}\subseteq T_{\mathbf{C}}(D_{Q})$, then the freezing mapping $\theta$
trivially satisfies $\theta B\subseteq D_{Q}$, hence, $\theta$ is an
assignment that satisfies $B$ over $D_{Q}$ and returns $\theta\bar{u}$ as an
answer. Thus, $\theta\bar{u}\in Q(D_{Q})\subseteq Q(T_{\mathbf{C}}(D_{Q}))$,
so that $Q$ is complete wrt $\mathbf{C}$ according to Theorem 2.3.

$(\Rightarrow)$ Let $\tilde{B}$ be the set of atoms obtained by unfreezing
$T_{\mathbf{C}}(D_{Q})$, that is,
$\tilde{B}=\theta^{-1}T_{\mathbf{C}}(D_{Q})$, and define $\tilde{Q}$ by the
rule $\tilde{Q}(\bar{u})\leftarrow\tilde{B}$. Note that $\tilde{Q}$ is a
subquery of $Q$. Since $Q$ is complete, Theorem 2.3 implies that
$\theta\bar{u}\in Q(T_{\mathbf{C}}(D_{Q}))$. It follows that all variables in
$\bar{u}$ occur in $\tilde{B}$ so that the query
$\tilde{Q}(\bar{u})\leftarrow\tilde{B}$ is safe. It also follows that
$\theta\bar{u}\in Q(\theta\tilde{B})=Q(D_{\tilde{Q}})$, which by Proposition
3.1 entails that $\tilde{Q}\sqsubseteq Q$. However, as $Q$ is minimal, this is
only possible if $B=\tilde{B}$, so that $D_{Q}=\theta
B=\theta\tilde{B}=T_{\mathbf{C}}(D_{Q})$.

Claim 2. Since the “$\Leftarrow$” direction of Claim 1 holds for all CQs, it
suffices to show that $D_{\alpha Q}\subseteq T_{\mathbf{C}}(D_{\alpha Q})$,
which amounts to showing $\theta\alpha B\subseteq T_{\mathbf{C}}(\theta\alpha
B)$. To this end, let $R(\bar{t})$ be an atom of $B$. Then
$R(\theta\bar{t})=\theta R(\bar{t})\in T_{\mathbf{C}}(\theta B)$ by Claim 1.
This is only possible if there exists a TC statement
$C=\textsl{Compl}(R(\bar{s});\,G)$ that is applicable to $\theta R(\bar{t})$.
Applicability implies there is an assignment $\beta$ such that
$R(\beta\bar{s})=R(\theta\bar{t})$ and $\beta G\subseteq\theta B$.

We can use $C$ also to map $\theta\alpha R(\bar{t})=R(\theta\alpha\bar{t})$
from $\theta\alpha B$, using instead of $\beta$ the assignment
$\theta\alpha\theta^{-1}\beta$. This new assignment essentially instantiates
$\beta$ by $\alpha$, but also unfreezes the frozen variables introduced by
$\beta$ and finally freezes again all variables.

With this assignment we have
$R(\theta\alpha\theta^{-1}\beta\bar{s})=R(\theta\alpha\theta^{-1}\theta\bar{t})=R(\theta\alpha\bar{t})\in\theta\alpha
B$. Moreover, since $\beta G\subseteq\theta B$, we also have
$\theta\alpha\theta^{-1}\beta G\subseteq\theta\alpha\theta^{-1}\theta
B=\theta\alpha B$. Consequentely, $C$ is applicable to $\theta\alpha
R(\bar{t})$ in $\theta\alpha B$ and $\theta\alpha R(\bar{t})\in\theta\alpha
B=D_{\alpha Q}$. ∎

Note that Claim 2 does not hold for non-minimal queries. For example, for the
non-minimal query $Q(X)\leftarrow{}R(X,a),R(X,Y)$, the TCS
$C=\textsl{Compl}(R(X,a);\textit{true})$, and the substitution
$\alpha=\\{Y\mapsto c\\}$ we have that $\\{C\\}\models\textsl{Compl}(Q)$, but
$\\{C\\}\not\models\textsl{Compl}(\alpha Q)$.

Now, we are ready to prove that it suffices to concentrate on subqueries when
looking for MCGs.

###### Proof of Proposition 3.3.

Consider a conjunctive query $Q(\bar{u})\leftarrow B$ and a complete
generalisation $Q^{\prime}(\bar{u}^{\prime})\leftarrow B^{\prime}$ of $Q$.
Since every conjunctive query is equivalent to a minimal one and a query
equivalent to a complete one is also complete, we assume without loss of
generality that $Q^{\prime}$ is minimal.

Since $Q\sqsubseteq Q^{\prime}$, there exists a query homomorphism $\delta$
from $Q^{\prime}$ to $Q$. Let $B_{0}=\delta B$ and define $Q_{0}$ as
$Q_{0}(\bar{X})\leftarrow B_{0}$. Then $Q_{0}=\delta Q^{\prime}$ and using
Claim 2 of Lemma 3.4 we conclude that $Q_{0}$ is complete.

Since $Q_{0}$ is a subquery of $Q$, we have $Q\sqsubseteq Q_{0}$. Moreover,
since $Q^{\prime}$ is minimal and $\delta$ is a substitution with
$Q_{0}=\delta Q^{\prime}$, we have $Q_{0}\sqsubseteq Q^{\prime}$. ∎

While Proposition 3.3 leaves us with all subqueries of $Q$ as candidates for
MCGs, we can still do better. We will modify the monotonic $T_{C}$ operator on
database instances to a monotonic operator $G_{\mathbf{C}}$ on queries. This
will allow us to characterize completeness in terms of fixed points. We will
then conclude that MCGs are least fixed points, are unique up to equivalence,
and can be computed by fixed point iteration.

First we define the _generalization operator_ $G_{\mathbf{C}}$. To make the
mathematics in this section work, we consider _generalized conjunctive
queries_ $Q(\bar{u})\leftarrow{}B$, where we give up the safety condition that
every head variable (that is, every variable occurring in $\bar{u}$) also
occurs in $B$. As for conjunctive queries, the set of answers of a generalized
conjunctive query $Q$ over an instance $D$ is defined as
$Q(D)=\\{\alpha\bar{u}\mid\alpha B\subseteq D\\}$, where $\alpha$ ranges over
all assignments of domain values to variables of $Q$. Note that if $Q$ is
unsafe, that is, $Q$ has a head variable not occurring in $B$, $D$ is an
instance, and $\alpha$ satisfies $Q$ over $D$, then for every domain value $c$
the modified assignment $\alpha[x/c]$ also satisfies $Q$ over $D$.
Consequently, an unsafe query can have an infinite answer set. Clearly, unsafe
queries are not of practical interest, but are needed for the mathematical
development.

For a set of TC statements $\mathbf{C}$ we define the operator
$G_{\mathbf{C}}$ as follows. If $Q(\bar{u})\leftarrow{}B$ is a generalized
conjunctive query, then the query $G_{\mathbf{C}}(Q)$ is computed in four
steps:

  1. 1.

freeze $B$ to obtain the database instance $D_{Q}$,

  2. 2.

compute $D_{Q}^{\prime}:=T_{\mathbf{C}}(D_{Q})$,

  3. 3.

unfreeze $D_{Q}^{\prime}$ to obtain a set of atoms $B^{\prime}\subseteq B$,

  4. 4.

finally, set $G_{\mathbf{C}}(Q):=Q^{\prime}$ where
$Q^{\prime}(\bar{u})\leftarrow B^{\prime}$.

Since $D_{Q}^{\prime}=T_{\mathbf{C}}(D_{Q})\subseteq D_{Q}$, it follows that
$B^{\prime}\subseteq B$. Thus, $G_{\mathbf{C}}(Q)$ is a subquery of $Q$.
Intuitively, $G_{\mathbf{C}}$ keeps only those atoms of a query body that are
“complete” wrt $\mathbf{C}$. Note that even if $Q$ is safe,
$G_{\mathbf{C}}(Q)$ may be unsafe.

Now we point out properties of the $G_{\mathbf{C}}$ operator that will help us
answer the questions about MCGs posed above. We first observe that the
completeness characterization in Theorem 2.3 can be reformulated in terms of
fixed points (modulo query equivalence) of $G_{\mathbf{C}}$.

######  Proposition 3.5.

Let $\mathbf{C}$ be a set of TC statements and $Q$, $Q^{\prime}$ be
generalized conjunctive queries. Then,

  1. 1.

$Q\sqsubseteq Q^{\prime}\quad\Longrightarrow\quad G_{\mathbf{C}}(Q)\sqsubseteq
G_{\mathbf{C}}(Q^{\prime})$;

  2. 2.

$\mathbf{C}\models\textsl{Compl}(Q)\quad\Longleftrightarrow\quad Q\equiv
G_{\mathbf{C}}(Q)$.

###### Proof Idea.

Claim 1 can be shown using the fact that the containment “$Q\sqsubseteq
Q^{\prime}$” implies the existence of a homomorphism $\delta$ from
$Q^{\prime}$ to $Q$ such that $\delta Q^{\prime}\subseteq Q$ [2]. For each
atom $A\in Q^{\prime}$, if $A\in T_{\mathbf{C}}(D_{Q^{\prime}})$ then
$\theta\delta A\in T_{\mathbf{C}}(D_{Q})$. Thus, $\delta$ is also a
homomorphism from $G_{\mathbf{C}}(Q^{\prime})$ to $G_{\mathbf{C}}(Q)$.

To see Claim 2, note that the characterizing condition for completeness in
Theorem 2.3, “$\theta\bar{u}\in Q(T_{\mathbf{C}}(\mathit{D}_{Q}))$,” is
equivalent to the existence of a query homomorphism from $Q$ to
$G_{\mathbf{C}}(Q)$ and thus to the containment $G_{\mathbf{C}}(Q)\sqsubseteq
Q$. Since, according to Claim 1, the converse containment $Q\sqsubseteq
G_{\mathbf{C}}(Q)$ holds anyway, this yields Claim 2. ∎

We are now in a position to prove that there is at most one MCG. As the proof
solely applies simple principles of order theory, we first fix a suitable
vocabulary. We remind the reader that a _preorder_ is a reflexive and
transitive binary relation $\preceq$ on some set $S$. A _least element_ of $S$
is an $l\in S$ such that $l\preceq s$ for all $s\in S$ (note that $S$ may
admit several least elements). The _equivalence relation_ $\approx$ _induced
by_ $\preceq$ is defined over $S$ by $s\approx s^{\prime}$ iff $s\preceq
s^{\prime}$ and $s^{\prime}\preceq s$. A function $f\colon S\to S$ is
_monotonic_ if $f(s)\preceq f(s^{\prime})$ whenever $s\preceq s^{\prime}$. An
element $s\in S$ is a _fixed point of_ $f$ _modulo_ $\approx$ if $f(s)\approx
s$. With $f^{0}$ we denote the identity function on $S$ while $f^{i}$, where
$i\geq 0$, denotes the $(i-1)$-fold composition of $f$ with itself. The
following lemma is folklore, but is usually expressed for orders (i.e.
antisymmetric preorders), so we write it explicitly for the sake of self-
containment:

######  Lemma 3.6.

Let $S$ be a finite set with preorder $\preceq$ and a least element $\bot$,
and let $f\colon S\to S$ be a monotonic function. Then

  1. 1.

$f$ has a least fixed point $p_{0}$ modulo $\approx$, and

  2. 2.

$p_{0}=f^{k}(\bot)$, where $k=\min\\{i\mid f^{i+1}(\bot)\preceq
f^{i}(\bot)\\}$.

###### Proof.

Since $\bot$ is a least element, $\bot\preceq f(\bot)$. Because $f$ is
monotonic, this implies $f(\bot)\preceq f(f(\bot))$. Inductively, we conclude
that $f^{i}(\bot)\preceq f^{i+1}(\bot)$ for all $i\geq 0$. Next, because $S$
is finite, the sequence $f^{i}(\bot)$ must enter a loop. So there exists a
least $k\geq 0$ such that $f^{k+1}(\bot)\preceq f^{k}(\bot)$. Together with
the fact that $f^{k}(\bot)\preceq f^{k+1}(\bot)$, this implies that
$f^{k}(\bot)\approx f^{k+1}(\bot)$, therefore $p_{0}=f^{k}(\bot)$ is a fixed
point modulo $\approx$.

Let $p$ be another fixed point modulo $\approx$. Then $\bot\preceq p$, and
consequently (since $f$ is monotonic), $p_{0}=f^{k}(\bot)\preceq
f^{k}(p)\approx p$. So $p_{0}$ is a least fixed point modulo $\approx$. ∎

We can use Lemma 3.6 to rephrase Proposition 3.5, using the operator
$G_{\mathbf{C}}$ as the function $f$, and leveraging the fact that containment
is a preorder on CQs. Precisely, for a given $Q$, we denote the set of
subqueries of $Q$, including those that are not safe, as $\textsl{Sub}_{Q}$.
Clearly, $\textsl{Sub}_{Q}$ is finite, containment is a preorder on
$\textsl{Sub}_{Q}$ (whose induced equivalence relation is query equivalence),
$Q$ is a least element of $\textsl{Sub}_{Q}$, and $G_{\mathbf{C}}$ is a
monotonic function on $\textsl{Sub}_{Q}$. Thus, all prerequisites of Lemma 3.6
are satisfied and we conclude the following proposition.

######  Proposition 3.7.

Let $Q$ be a conjunctive query and $\mathbf{C}$ be a set of TC statements.
Then

  1. (a)

$G_{\mathbf{C}}$ has a least fixed point (modulo $\equiv$) $\tilde{Q}$ in
$\textsl{Sub}_{Q}$ ;

  2. (b)

$\tilde{Q}$ is complete;

  3. (c)

$\tilde{Q}={G_{\mathbf{C}}}^{n}(Q)$ where $n$ is less or equal than the number
of atoms in $Q$;

  4. (d)

if $Q^{\prime}$ is any complete generalization of $Q$, then
$\tilde{Q}\sqsubseteq Q^{\prime}$;

  5. (e)

if $\tilde{Q}$ is safe, then $\tilde{Q}$ is the MCG of $Q$ wrt $\mathbf{C}$,
otherwise no complete generalisation of $Q$ wrt $\mathbf{C}$ exists.

###### Proof.

Claim (a) immediately follows from Lemma 3.6, while Claim (b) holds because
fixed points of $G_{\mathbf{C}}$ are complete (by Proposition 3.5). Claim (c)
holds because the application of $G_{\mathbf{C}}$ to an incomplete query
causes the removal of at least one atom. Claim (d) holds, since by Proposition
3.3, every complete generalization of $Q$ has some complete query
$Q_{0}\in\textsl{Sub}_{Q}$ as a subquery, and by Proposition 3.5, $\tilde{Q}$
is contained in every complete query $Q_{0}\in\textsl{Sub}_{Q}$. Finally, if
$\tilde{Q}$ is not safe, then there is no safe subquery of $Q$ that is
complete and therefore no complete generalisation of $Q$. Hence, Claim (e)
holds. ∎

A possible algorithm suggested by Proposition 3.7 would repeatedly apply the
$G_{\mathbf{C}}$ operator to $Q$, producing a sequence of subqueries
$Q_{i}={G_{\mathbf{C}}}^{i}(Q)$, and stop when $Q_{i+1}\sqsubseteq Q_{i}$.
Alternatively, the termination condition could be a check that $Q_{i}$ is
complete. A third possibility (which we use below in Algorithm 1) is to stop
when $Q_{i+1}=Q_{i}$, that is, when $G_{\mathbf{C}}$ does not remove any atom
from $Q_{i}$. The following result shows that this is correct:

######  Proposition 3.8.

Let $Q$ be a CQ, $\mathbf{C}$ be a set of TC statements, and
$Q_{i}={G_{\mathbf{C}}}^{i}(Q)$ for $i\geq 0$. If $Q_{i+1}=Q_{i}$, then
$Q_{i}$ is a least fixed point of $G_{\mathbf{C}}$ modulo $\equiv$ in
$\textsl{Sub}_{Q}$.

###### Proof.

By Proposition 3.7, repeatedly applying $G_{\mathbf{C}}$ to $Q$ leads to a
first $Q_{k}$ that is a fixed point modulo $\equiv$, this query $Q_{k}$ is a
least fixed point modulo $\equiv$, and $Q_{j}\equiv Q_{k}$ for each $j\geq k$.
If $Q_{i}=Q_{i+1}$, then $i\geq k$, so $Q_{i}\equiv Q_{k}$, therefore $Q_{i}$
is also a least fixed point modulo $\equiv$. ∎

#### Generalization Algorithm

Following Proposition 3.7, we construct Algorithm 1, which computes an MCG for
a query $Q$ and TCSs $C$.

Input : query $Q(\bar{u})\leftarrow B$, set of TCSs $\mathbf{C}$

Output : MCG of $Q$ if one exists; otherwise $\mathtt{null}$

$Q_{\mathit{old}}:=Q$, $Q_{\mathit{new}}=G_{\mathbf{C}}(Q)$;

while  _$Q_{\mathit{new}}$ is safe and $Q_{\mathit{new}}\neq
Q_{\mathit{old}}$_ do

$Q_{\mathit{old}}:=Q_{\mathit{new}}$

$Q_{\mathit{new}}:=G_{\mathbf{C}}(Q_{\mathit{old}})$

if  _$Q_{\mathit{new}}$ is not safe_ then

return _$\mathtt{null}$_

else

return _$Q_{\mathit{new}}$_

Algorithm 1 Computes an MCG if one exists

#### Computational Complexity

We study two decision problems related to generalizing a (possibly) incomplete
CQ. The first problem estimates the cost of the $G_{\mathbf{C}}$ operator. We
show that this problem is complete for the complexity class DP, which
intuitively consists of all problems that can be decided by an algorithm that
performs two calls to an NP-oracle: the algorithm responds “yes” if the first
oracle call returns “yes” and the second one returns “no”.

######  Proposition 3.9.

For a set $\mathbf{C}$ of TC statements and two CQs $Q$ and $Q^{\prime}$,
deciding whether $Q^{\prime}=G_{\mathbf{C}}(Q)$ is DP-complete.

Our second decision problem estimates the cost of computing an MCG. We show
that this problem is in $\textrm{P}^{\textrm{NP}}$, which is the class of
problems that can be decided in polynomial time by a Turing machine that uses
an NP-oracle.222An example of a complete problem problem for
$\textrm{P}^{\textrm{NP}}$, provided by Krentel (1988), is the
lexicographically last satisfying assignment of a Boolean formula: given a
Boolean formula $\phi(X_{1},\dots,X_{n})$, decide whether variable $X_{n}$
takes value $1$ in the lexicographically largest satisfying assignment for
$\phi$. We do not know whether the problem is also
$\textrm{P}^{\textrm{NP}}$-hard.

######  Proposition 3.10.

For a set $\mathbf{C}$ of TC statements and two CQs $Q$ and $Q^{\prime}$,
deciding whether $Q^{\prime}$ is an MCG of $Q$ wrt $\mathbf{C}$ is in
$\textrm{P}^{\textrm{NP}}$.

###### Proof sketch.

In order to decide whether $Q^{\prime}$ is an MCG of $Q$, it is sufficient to
execute Algorithm 1, verify whether the output query $Q_{\mathit{new}}$ is
null, and if it is not, determine whether $Q_{\mathit{new}}\equiv Q^{\prime}$.
The latter can be done with a call to an NP oracle, since equivalence of CQs
is known to be in NP (and the size of $Q_{\mathit{new}}$ is bounded by the
size of $Q$).

Next, we observe that Algorithm 1 performs a number of iterations that is
linear in the size of $Q$ (because the $G_{\mathbf{C}}$ operator intuitively
discards atoms from the body of its input query). So to complete the proof, it
is sufficient to observe that each of these iteration can be executed in
linear time, assuming an NP oracle. More precisely, for any query
$Q_{\mathit{old}}$, the query $G_{\mathbf{C}}(Q_{\mathit{old}})$ can be
computed by retaining certain atoms in the body $B$ of $Q_{\mathit{old}}$:
retain an atom $A$ iff there is a TCS $\textsl{Compl}(A;G)$ in $\mathbf{C}$
and a substitution $\alpha$ such that $\alpha G\subseteq B$. Deciding the
existence of such a substitution is in NP, because _(i)_ the size of $\alpha$
is bounded by the size of $G$ (so it can be encoded as a certificate with
polynomial length), and _(ii)_ $\alpha G\subseteq B$ can be trivially verified
in polynomial time.

∎

##  4 Query Specialization

As discussed in the introduction, another common way to approximate a query is
to make it more specific. Analogously to the previous section, we study the
existence and computation of CQs that specialize $Q$ and are complete wrt a
set of TCSs. As in the preceding section, all queries mentioned are assumed to
be conjunctive queries.

We say, that $Q^{\prime}$ is a _complete specialization_ (CS) of $Q$ wrt a set
$\mathbf{C}$ of TCSs if $Q^{\prime}\sqsubseteq Q$ and
$\mathbf{C}\models\textsl{Compl}(Q^{\prime})$. Among those queries, the
preferred ones are the _maximal_ ones:

######  Definition 4.1 (Maximal Complete Specialization).

A query $Q^{\prime}$ is a _maximal complete specialization_ (MCS) of $Q$ wrt a
set $\mathbf{C}$ of TCSs if:

  * •

$Q^{\prime}$ is a CS of $Q$ wrt $\mathbf{C}$, and

  * •

it is a maximal one, that is, there exists no query $Q^{\prime\prime}$ such
that $Q^{\prime\prime}$ is a CS of $Q$ and $Q^{\prime}$ is strictly contained
in $Q^{\prime\prime}$.

Even though the definition of an MCS is symmetric to the one of an MCG, it
will turn out that there are important differences between these two settings
that require different approaches. First, a query may have several non-
equivalent MCSs (whereas it admits at most one MCG up to equivalence). Second,
a query may admit CSs but no MCS:

######  Theorem 4.2.

There is a query $Q$ and set $\mathbf{C}$ of TCSs such that $Q$ admits CSs wrt
$\mathbf{C}$, none of which is maximal.

###### Proof.

Consider a schema with a binary relation conn that specifies whether two
cities are connected via a direct flight, and let $C$ be the TCS
$\textsl{Compl}(\textit{conn\/}(X,Y);\textit{conn\/}(Y,Z))$, which states that
the data is complete for all (direct) connections that can be extended. The
query $Q(X)\leftarrow\textit{conn\/}(X,Y)$, which retrieves all cities with an
outgoing flight, is not complete wrt $\\{C\\}$. As an illustration, consider
the incomplete database $\mathcal{D}=({D}^{i},{D}^{a})$ where
${D}^{i}=\\{\textit{conn\/}(a,b),\textit{conn\/}(b,c),\textit{conn\/}(d,e)\\}$
and ${D}^{a}=\\{\textit{conn\/}(a,b),\textit{conn\/}(b,c)\\}$. The database
$\mathcal{D}$ satisfies $C$, but $Q(D^{i})\not\subseteq Q(D^{a})$.

Now let $Q^{\prime}$ be any complete specialization of $Q$ wrt $\mathbf{C}$.
Because $Q^{\prime}$ is complete, its body must contain a set
$\mathcal{A}_{k}$ of atoms that identifies a round trip of length $k$ for some
$k\geq 1$, having the form
$\mathcal{A}_{k}=\\{\textit{conn\/}(X_{0},X_{1}),\textit{conn\/}(X_{1},X_{2}),\ldots,\textit{conn\/}(X_{k-1},X_{0})\\}$,
and $Q^{\prime}$ must project exactly one of these variables.

Let $k^{\prime}$ be the largest $k$ for which this holds, and consider the
query $Q_{2k^{\prime}}(X_{0})\leftarrow{}\mathcal{A}_{2k^{\prime}}$. This
query is also a complete specialization of $Q$. Moreover, the function
$\delta_{k}$ that maps each $X_{i}$ to $X_{i\bmod k}$ is a homomorphism from
$Q_{2k^{\prime}}$ to $Q^{\prime}$, which implies $Q^{\prime}\sqsubseteq
Q_{2k^{\prime}}$. However, $\mathcal{A}_{k}$ cannot be mapped to
$\mathcal{A}_{2k^{\prime}}$ (i.e., the body of $Q$), therefore there is no
homomorphism from $Q^{\prime}$ to $Q_{2k^{\prime}}$, which implies
$Q_{2k^{\prime}}\not\sqsubseteq Q^{\prime}$. So $Q^{\prime}$ is not an MCS. ∎

These observations lead us to investigate restrictions on a set $\mathbf{C}$
of TCSs that guarantee the set of CSs (thus also of MCSs) of a query wrt
$\mathbf{C}$ to be finite. We define the _dependency graph_ of $\mathbf{C}$ as
the graph whose nodes are the relation names appearing in $\mathbf{C}$, and
with an edge from $R$ to $R^{\prime}$ iff $R^{\prime}$ appears in $G$ for some
statement of the form $\textsl{Compl}(A;G)$, where the atom $A$ is over $R$.
We say that $\mathbf{C}$ is _acyclic_ if its dependency graph is acyclic. The
following result provides an upper bound on the size of an MCS for such a
$\mathbf{C}$.

######  Theorem 4.3.

Let $Q$ be a CQ, $\mathbf{C}$ an acyclic set of TCSs and $s$ the number of
relation names that appear in $\mathbf{C}$. Then the number of atoms in a MCS
of $Q$ wrt $\mathbf{C}$ is in $\mathcal{O}(|Q|\times|C|^{s+1})$.333This
acyclicity requirement on $\mathbf{C}$ can be relaxed, while guaranteeing a
bound on the size of an MCS. In particular, it is sufficient to require that
$\mathbf{C}$ is _weakly acyclic_ , as defined in [3].

In the rest of this section, we show how to compute the CSs of $Q$ that are
maximal (wrt $\sqsubseteq$) within the space of queries with at most $|Q|+k$
atoms, for some $k\in\mathbb{N}$. We call such a query a $k$-MCS. Theorem 4.3
implies that, if $\mathbf{C}$ is acyclic, then MCSs and $k$-MCSs coincide for
a large enough $k$. We also restrict our investigations to the case where $Q$
is a minimal query in the sense of Lemma 3.4, that is $Q$ has no redundant
atoms.

We first analyze how to compute MCSs without adding atoms to the body of $Q$
(we call such MCSs maximal complete instantiations, defined below), and we
then extend this approach to find $k$-MCSs.

###  4.1 Maximal Complete Instantiations

######  Definition 4.4 (Maximal Complete Instantiation).

If $\mathbf{C}$ is a set of TCSs, then a _maximal complete instantiation
(MCI)_ of $Q$ wrt $\mathbf{C}$ is an instantiation of $Q$ that is complete wrt
$\mathbf{C}$ and maximal wrt containent among these.

As an illustration, in the proof sketch of Theorem 4.2, the query
$Q^{\prime}(X)\leftarrow{}\textit{conn\/}(X,X)$ is the only MCI for $Q$ wrt
$\mathbf{C}$.

Our approach to compute MCIs revolves around a specific type of substitution
that we call a _complete unifier_ , defined as follows:

######  Definition 4.5 (Complete Unifier).

Let $Q$ be a CQ and $\mathbf{C}$ a set of TCSs. A _complete unifier_ for $Q$
and $\mathbf{C}$ is a substitution $\gamma$ such that, for each atom $A$ in
the body of $Q$, there is a TCS $C=\textsl{Compl}(A^{\prime};G)\in\mathbf{C}$
that satisfies

$\gamma A=\gamma A^{\prime}\qquad\text{~{}and~{}}\qquad\gamma G\subseteq\gamma
B.$

Applying a complete unifier to $Q$ yields a complete query:

######  Proposition 4.6.

If $\gamma$ is a complete unifier for $Q$ and a set $\mathbf{C}$ of TCSs, then
$\mathbf{C}\models\textsl{Compl}(\gamma Q)$.

######  Example 4.7.

In Ex. 2.1, the substitution $\gamma=\\{L\mapsto\mathit{english\/}\\}$ is a
complete unifier for $Q_{\textit{pbl}}$ and the set of TCSs, and $\gamma
Q_{\textit{pbl}}=Q_{\textit{pbl}}^{\textit{spec}}$ is indeed complete. ∎

######  Theorem 4.8.

Let $\mathbf{C}$ be a set of TCSs, let $Q$ be a query, and $Q^{\prime}$ be a
complete instantiation of $Q$ wrt $\mathbf{C}$. Then there is a complete
unifier $\gamma$ for $Q$ and $\mathbf{C}$ such that
$Q^{\prime}\sqsubseteq\gamma Q$.

######  Example 4.9 (continued).

Consider $Q^{\prime}(N)\leftarrow{}\
\textit{pupil\/}(N,1,S),\textit{school\/}(S,\mathit{primary\/},\mathit{merano\/}),\textit{learns\/}(N,\mathit{english\/})$.
Then $Q^{\prime}$ is a complete instantiation of $Q_{\textit{pbl}}$ and
$Q^{\prime}\sqsubseteq\gamma Q_{\textit{pbl}}$. ∎

Observe that if $\gamma$ is a complete unifier for $Q$ and $\mathbf{C}$, then
there must be a subset $\mathbf{C}^{\prime}$ of $\mathbf{C}$ such that
$\gamma$ is a complete unifier for $Q$ and every atom $A$ in $Q$ is unified
with the head of exactly one TCS from $\mathbf{C}^{\prime}$. We call such a
$\mathbf{C}^{\prime}$ a _matching subset_ of $\mathbf{C}$ for $Q$. Since $Q$
and $\mathbf{C}^{\prime}$ admit a complete unifier, they admit a (unique) most
general one. Let $\text{mgu}(Q,\mathbf{C}^{\prime})$ denote this unifier, and
let
$\text{mgu}(Q,2^{\mathbf{C}})=\\{\text{mgu}(Q,\mathbf{C}^{\prime})\mid\mathbf{C}^{\prime}\text{~{}is
a matching subset
of~{}}\mathbf{C}\text{~{}for~{}}Q,Q\text{~{}and~{}}\mathbf{C}^{\prime}\text{
admit a complete unifier}\\}$. Since $\mathbf{C}$ is finite,
$\text{mgu}(Q,2^{\mathbf{C}})$ is finite, too. More, as an immediate
consequence of Theorem 4.8 and Proposition 4.6, each MCI of $Q$ wrt
$\mathbf{C}$ is equivalent to $\gamma Q$ for some
$\gamma\in\text{mgu}(Q,2^{\mathbf{C}})$. This is the rationale behind our
procedure to compute all MCIs of $Q$ wrt $\mathbf{C}$ described with Algorithm
2. The first loop computes $\\{\gamma
Q\mid\gamma\in\text{mgu}(Q,2^{\mathbf{C}})\\}$, relying on a function MGU that
returns $\text{mgu}(Q,\mathbf{C}^{\prime})$ if it exists, and null otherwise.
The second loop discards non-maximal instantiations within these.

Input : a query $Q(\bar{u})\leftarrow{}A_{1},\dots,A_{n}$, a set $\mathbf{C}$
of TCSs

Output : the set $\mathcal{S}$ of all MCIs of $Q$ wrt $\mathbf{C}$

1 $\mathcal{S}:=\emptyset$, $\gamma:=\mathtt{null}$

2 foreach  _matching subset $\mathbf{C}^{\prime}$ of $\mathbf{C}$ for $Q$_ do

3 $\gamma:=\mathtt{MGU}(Q,\mathbf{C}^{\prime})$

4 if  _ $\gamma\not=\mathtt{null}$ _ then

5 $\mathcal{S}:=\mathcal{S}\cup\\{\gamma Q\\}$

6

7foreach  _$Q^{\prime}$ in $\mathcal{S}$_ do

8 if  _there exists $Q^{\prime\prime}\in\mathcal{S}$ such that
$Q^{\prime}\sqsubseteq\\{Q\\}^{\prime\prime}$_ then
$\mathcal{S}:=\mathcal{S}\setminus\\{Q^{\prime}\\}$

9

return _$\mathcal{S}$_

Algorithm 2 Computes Maximal Complete Instantiations

#### Computational Complexity of the MCI Decision Problem

We study the problem that consists in deciding whether a query is an MCI.

######  Theorem 4.10.

Given a query $Q$, a candidate query $Q^{\prime}$ and a set $\mathbf{C}$ of
TCSs, deciding whether $Q^{\prime}$ is an MCI of $Q$ wrt $\mathbf{C}$ is in
$\Pi^{\text{P}}_{2}$.

###### Proof sketch.

We show that a non-deterministic Turing machine can verify in polynomial time
that $Q^{\prime}$ is _not_ an MCI, assuming an oracle for NP, as follows:

  1. (I)

determine whether $Q^{\prime}$ is complete,

  2. (II)

if it is, then determine whether it is also an instantiation of $Q$,

  3. (III)

if it is, then verify that there is a more general complete instantiation of
$Q$.

For Step (I), it was show in [13] that deciding whether a CQ is complete wrt
to a set of TCSs is NP-complete. Therefore one can determine whether
$Q^{\prime}$ is complete with one call to an NP oracle.

For Step (II), similarly, we show that deciding whether $Q^{\prime}$ is an
instantiation of $Q$ is in NP. Observe that $Q^{\prime}$ is an instantiation
of $Q$ iff there is a substitution $\alpha$ such that $Q^{\prime}=\alpha Q$.
If such a substitution exists, then it is a function from the variables that
appear in $Q$ to the variables and constants that appear in $Q^{\prime}$. So
$\alpha$ can be encoded as a certificate with length polynomial in the size of
$Q$ and $Q^{\prime}$. And given $\alpha$, one can (trivially) verify in
polynomial time that $Q^{\prime}=\alpha Q$.

For Step (III), it is sufficient to verify that there exists a substitution
$\beta$ such that _(i)_ $\beta Q$ is complete, _(ii)_
$Q^{\prime}\sqsubseteq\beta Q$ and _(iii)_ $\beta Q\not\sqsubseteq
Q^{\prime}$. Again, such a substitution can be encoded as a certificate with
polynomial length. Next, as we explained above for Step (I), whether _(i)_
holds can be determined (therefore also verified) with one call to an NP
oracle. And it is well-known that containment of CQs is in NP, therefore
_(ii)_ and _(iii)_ can also be verified by calling such an oracle (note that a
quantifier alternation is only needed here for _(iii)_ , which is in co-NP,
whereas (i) and (ii) are in NP). ∎

It is not hard to show (using a similar technique as for Proposition 3.9) that
deciding the MCI problem is DP-hard. Whether it is
$\Pi^{\text{P}}_{2}$-complete is an open question.

###  4.2 Adding Atoms

We can now extend our approach to computing all $k$-MCSs of a query $Q$ of
size $n$ wrt a set $\mathbf{C}$ of TCSs. Let $\Sigma_{\mathbf{C}}$ be the set
of all relation names appearing in $\mathbf{C}$. An _extension_ of $Q$ is a
query obtained by adding atoms to the body of $Q$. We call an extension
_fresh_ if the variables of the added atoms do not appear in $Q$. A first
observation is that a fresh extension $Q^{\prime}$ of $Q$ is a specialization
of $Q$, therefore the MCIs of $Q^{\prime}$ are CSs of $Q$.

Next, a key observation is that the $k$-MCSs of $Q$ coincide with the MCIs of
all fresh extensions of $Q$ with $n+k-1$ fresh atoms, restricted to MCIs of
size $\leq n+k$. The intuition is the following. Let $Q^{\prime}$ be a CS of
$Q$ of size $\leq n+k$. Then there is a homomorphism $\delta$ from $Q$ to
$Q^{\prime}$. Let also $B^{\prime}$ be the set atoms in $Q^{\prime}$ that have
no preimage via $\delta$. Then the size of $B^{\prime}$ is $\leq n+k-1$. We
construct a new query $Q^{\prime\prime}$ of size $2n+k-1$ whose body consists
of the body $B$ of $Q$, and a fresh version of $B^{\prime}$. Then
$Q^{\prime}\sqsubseteq Q^{\prime\prime}$. Moreover, since $Q^{\prime}$ is
complete, $Q^{\prime\prime}$ must have an MCI at least as general as
$Q^{\prime}$.

The first loop of Algorithm 3 implements this idea: the function
$\texttt{MCI}_{\leq n+k}(Q^{\prime\prime},\mathbf{C})$ returns the MCIs of
$Q^{\prime\prime}$ wrt $\mathbf{C}^{\prime}$ of size $\leq n+k$. Then the
second loop discards non-maximal instantiations within these.

Input : a query $Q(\bar{u})\leftarrow{}B$, a set $\mathbf{C}$ of TCSs ,
$k\in\mathbb{N}_{0}$

Output : the set $\mathcal{S}$ of all $k$-MCSs of $Q$ wrt $\mathbf{C}$

1 $\mathcal{S}:=\emptyset$

2foreach  _set $B^{\prime}$ of fresh atoms of size $n+k-1$ over
$\Sigma_{\mathbf{C}}$ _ do

3 construct $Q^{\prime\prime}(\bar{u})\leftarrow{}B,B^{\prime}$

4 $\mathcal{S}:=\mathcal{S}\cup\mathtt{MCI}_{\leq
n+k}(Q^{\prime\prime},\mathbf{C})$

5 foreach  _$Q^{\prime\prime}$ in $\mathcal{S}$_ do

6 if  _exists $Q^{\prime\prime\prime}\in\mathcal{S}$ such that
$Q^{\prime\prime}\sqsubseteq Q^{\prime\prime\prime}$_ then
$\mathcal{S}:=\mathcal{S}\setminus\\{Q^{\prime\prime}\\}$

7

return _$\mathcal{S}$_

Algorithm 3 Computes k-MCSs

##  5 Implementation

We now briefly discuss how we chose platforms to implement our algorithms in
the demo tool MAGIK [14].

#### Implementing Generalization

At its core the generalization algorithm repeatedly applies the
$G_{\mathbf{C}}$ operator to the database instance $D_{Q}$ until it has
reached a fixed point. In each round, starting from an instance of the size of
the query, a new instance is produced by applying TC statements in a forward
fashion, until original and new instance are identical. We implemented this
via a datalog engine, namely the ASP solver dlv. The instance $D_{Q}$ is
represented by facts, initially obtained by freezing the query, and the TC
statements are translated into TC rules.

For example, the query $Q_{\textit{ppb}}(N)$ would be translated into the
facts $\textit{pupil\/}^{i}(n^{\prime},c^{\prime},s^{\prime}),$ and
$\textit{school\/}^{i}(s^{\prime},\mathit{primary\/},\mathit{merano\/})$,
while the statement $C_{\textit{pb}}$ would be translated into the rule
$\textit{pupil\/}^{a}(N,C,S)\leftarrow\textit{pupil\/}^{i}(N,C,S),\,\textit{school\/}^{i}(S,T,\mathit{merano\/}))$.
To distinguish original and new atoms, the relation symbols are either labeled
with the superscript i, standing for “ideal”, or a, standing for “available”.
A fixed point is reached if each “ideal” fact is translated into an
“available” fact.

While the ASP functionality is not used here, it becomes beneficial when
taking account of disjunctive constraints such as finite domain constraints.

#### Implementing Specialization

The core operation of the specialization algorithm in Section 4 is
unification, which makes ASP systems unsuitable as a platform while it is
offered as a functionality by Prolog. We implemented it in SWI-Prolog. The
problem is inherently hard, due to the doubly exponential search space.

For instance, let us consider the query
$Q_{\textit{l}}\leftarrow{}\textit{learns\/}(N,L)$, and the set of TCSs from
our running example, minus the TCS $C_{\textit{pb}}$, and extended with
$\textsl{Compl}(\textit{pupil\/}(N,C,S);\textit{class\/}(C,S,L,\mathit{halfDay\/}))$
and
$\textsl{Compl}(\textit{pupil\/}(N,C,S);\textit{class\/}(C,S,L,\mathit{fullDay\/})).$
The search for all $3$-MCSs would run out of memory.444Using an Intel Core i7
with 8GB of RAM, and 2GB allocated to SWI-Prolog.

To avoid this we implemented several optimizations.555The code is available
at: https://github.com/osavkovic/QuerySpecProlog/ Briefly, to compute
$k$-MCSs, we consider extensions of size 0, then $1,2,\ldots,k$. For $j>i$,
the $i$-MCSs are likely to be identical to the $j$-MCSs. By keeping in memory
the list of maximal specializations collected so far, we can compare them for
containment with the currently analyzed extensions. This step reduces the
search space at line 2 of Alg. 3. This way, we reduce the number of
specializations that we store, and this reduces memory consumption. Further
optimizations can be implemented in the presence of integrity constraints
(e.g., foreign keys) which we do not present in this paper.

We performed preliminary tests of our optimized code, and reached size
$|Q_{\textit{l}}|+7$ after around more than 2 hours. The average running times
(over multiple runs) are reported in Table 1. We observe that the running time
grows exponentially with the number of atom added to the query.

k-MCS | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---|---
CPU time (sec) | 0 | 0 | 0 | 0 | 0 | 8 | 725 | 9083
Table 1: Time required for the specialization algorithm to compute k-MCS of
query $Q_{\textit{l}}$.

This small experiment shows that the optimizations improve the initially
proposed specialization algorithm (especially, concerning memory), and that
such optimizations may still not be sufficient for large queries.

##  6 Conclusion

In this work, we studied the completeness of conjunctive queries over
partially complete databases where completeness is determined via so-called
completeness statements. For queries that cannot be answered completely, we
study ways to approximate such queries with more general or more special
queries that are complete. In particular, we established characterizations and
algorithms for finding maximal complete specializations (MCSs) or the (unique)
minimal complete generalization (MCG). The MCG can be characterized as the
least fixed-point of a monotonic operator in a preorder. An MCS can be
computed through unification between the query and completeness statements.
The complexity of both problems is studied, and implementation techniques
using ASP and Prolog engines are discussed.

We plan to extend our theory by considering integrity constraints like primary
and foreign keys, and finite domain constraints, and to enhance our
implementation techniques.

## References

  * [1] Marcelo Arenas, Leopoldo Bertossi, Jan Chomicki, Xin He, Vijay Raghavan, and Jeremy Spinrad.  Scalar aggregation in inconsistent databases.  Theor. Comput. Sci., 296(3), 2003.
  * [2] Ashok K. Chandra and Philip M. Merlin.  Optimal implementation of conjunctive queries in relational data bases.  STOC ’77, page 77–90. Association for Computing Machinery, 1977.
  * [3] Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa.  Data exchange: Semantics and query answering.  In Proc. ICDT, pages 207–224, 2002.
  * [4] W. Fan and F. Geerts.  Relative information completeness.  In PODS, 2009.
  * [5] W. Fan and F. Geerts.  Capturing missing tuples and missing values.  In PODS, 2010.
  * [6] Dieter Fensel, Umutcan Simsek, Kevin Angele, Elwin Huaman, Elias Kärle, Oleksandra Panasiuk, Ioan Toma, Jürgen Umbrich, and Alexander Wahler.  Knowledge graphs: Methodology, Tools and Selected Use Cases.  Springer, 2020.
  * [7] Paolo Guagliardo and Leonid Libkin.  Making sql queries correct on incomplete databases: A feasibility study.  PODS ’16, 2016.
  * [8] A.Y. Levy.  Obtaining complete answers from incomplete databases.  In Proc. VLDB, pages 402–412, 1996.
  * [9] A. Motro.  Integrity = Validity + Completeness.  ACM TODS, 14(4):480–502, 1989.
  * [10] Werner Nutt, Sergey Paramonov, and Ognjen Savkovic.  Implementing query completeness reasoning.  In CIKM, pages 733–742, 2015.
  * [11] Christos M. Papadimitriou.  Computational complexity.  Addison-Wesley, 1994.
  * [12] Simon Razniewski, Hiba Arnaout, Shrestha Ghosh, and Fabian Suchanek.  Completeness, recall, and negation in open-world knowledge bases: A survey.  ACM Comput. Surv., 56(6), 2024.
  * [13] Simon Razniewski and Werner Nutt.  Completeness of queries over incomplete databases.  PVLDB, 4(11):749–760, 2011.
  * [14] Ognjen Savković, Paramita Mirza, Alex Tomasi, and Werner Nutt.  Complete approximations of incomplete queries.  In VLDB Endowment 6 (12) (VLDB) (2013), pages 1378–1381, 2013.

## Appendix

[chapter] [chapter]l0

##  Appendix 0.A The Complexity of Identifying MCGs

Recall that DP consists of problems that can be decided by an algorithm that
simultaneously performs two calls to an NP-oracle. The algorithm responds
“yes” if the first oracle call returns “yes” and the second one returns “no”.
Our proof is based on a reduction of a DP-complete graph problem, known as
_Critical 3-colorability_ [11]:

> Given a graph, is it true that the graph is not 3-colorable but any subgraph
> obtained by removing one of the edges is 3-colorable?

######  Proposition 0.A.1.

For a set $\mathbf{C}$ of TC statements and two CQs $Q$ and $Q^{\prime}$,
deciding whether $Q^{\prime}=G_{\mathbf{C}}(Q)$ is DP-complete.

###### Proof.

_(Membership)_ That the problem is in DP follows because one can verify that
$Q^{\prime}\equiv G_{\mathbf{C}}(Q)$ in two steps. For every atom in
$A^{\prime}\in D_{Q^{\prime}}$ one has to find a statement $C\in\mathbf{C}$
such that $A^{\prime}=T_{C}(D_{Q})$. This can be done with one NP-oracle call.
Similarly, one has to show for every $A\in D_{Q}\setminus D_{Q^{\prime}}$ that
such a rule does not exist. This can be done again with one call to an co-NP
oracle.

_(Hardness)_ We show hardness by reducing the Critical 3-colorability problem.
Assume we are given a graph $G=\langle V,E\rangle$ with vertices $V$ and edges
$E$. It is known that starting from $G$ one can construct a Boolean query
$Q_{G}\leftarrow{}B_{G}$ where:

$B_{G}=\bigwedge_{(v_{i},v_{j})\in E}\textit{Eg}(X_{i},X_{j})$

such that $G$ is 3-colorable iff $Q_{G}$ evaluates to true over the database
$D$ that contains six correct colorings for the relation Eg:
$\\{\textit{Eg}(red,blue),\textit{Eg}(blue,red),\dots\\}$. Similarly, for each
edge $(v_{i},v_{j})\in E$ we construct a query
$Q_{G}^{(i,j)}\leftarrow{}B_{G}^{(i,j)}$ where

$B_{G}^{(i,j)}=\bigwedge_{(v_{l},v_{k})\in
E\setminus(v_{i},v_{j})}\textit{Eg}(X_{l},X_{k}),$

such that $Q_{G}^{(i,j)}(D)=\textit{true}$ iff the subgraph $G^{(i,j)}=\langle
V,E\setminus(v_{i},v_{j})\rangle$ is 3-colorable. We use this idea to
construct a set of TCSs $\mathbf{C}$:

$\displaystyle\mathbf{C}\quad=\quad$
$\displaystyle\Big{(}\bigcup_{(v_{i},v_{j})\in
E}\textsl{Compl}(\mathit{test}_{(i,j)};B_{G}^{(i,j)})\Big{)}\cup\textsl{Compl}(\mathit{test}_{G};B_{G})$
$\displaystyle\cup\textsl{Compl}(\textit{Eg}(X,Y);\textit{true}),$

where $\mathit{test}_{(i,j)}$ are propositions. Then we construct two Boolean
queries:

$\displaystyle Q\leftarrow{}\Big{(}\bigwedge_{(v_{i},v_{j})\in
E}\mathit{test}_{(i,j)}\Big{)}\land\mathit{test}\land D\text{\quad and
\quad}Q^{\prime}\leftarrow{}\Big{(}\bigwedge_{(v_{i},v_{j})\in
E}\mathit{test}_{(i,j)}\Big{)}\land D.$

From the characterizing condition for completeness “$\theta\bar{X}\in
Q(T_{\mathbf{C}}(\mathit{D}_{Q}))$,” we observe that each proposition
$\mathit{test}_{(i,j)}$ is complete iff $G^{(i,j)}$ subgraph is 3-colorable,
and similarly the proposition $\mathit{test}$ is complete iff $G$ is
3-colorable. Next, query $Q^{\prime}$ is the same as $Q$ except it does not
contain the $\mathit{test}$ proposition. Thus, $Q^{\prime}=G_{\mathbf{C}}(Q)$
iff each $G^{(i,j)}$ is 3-colorable but $G$ is not. ∎

The fixpoint iteration algorithm computes a MCG (if it exists) in a number of
steps linear in the size of a given query, using a DP-oracle. A call to a DP-
oracle can be realized by two calls to an NP-oracle. Thus, the MCG decision
problem belongs to the class of problems $\textrm{P}^{\textrm{NP}}$. This is a
class of problems that can be decided in polynomial time by a Turing machine
that uses an NP-oracle.666An example of a complete problem for class
$\textrm{P}^{\textrm{NP}}$ provided by Krentel (1988) is the lexicographically
last satisfying assignment of a Boolean formula: Given a Boolean formula
$\phi(X_{1},\dots,X_{n})$ the question whether in the in the lexicographically
largest satisfying assignment of $\phi$ variable $X_{n}$ takes value $1$.

Hence we have the following proposition.

######  Proposition 0.A.2.

Given queries $Q$ and $Q^{\prime}$, and set of TC statements $\mathbf{C}$, the
problem of checking whether $Q^{\prime}$ is the MCG of $Q$ wrt $\mathbf{C}$ is
in $\textrm{P}^{\textrm{NP}}$.

It is unknown if the problem is also $\textrm{P}^{\textrm{NP}}$-hard.

##  Appendix 0.B The Number of MCSs for Acyclic Sets of TC Statements

######  Theorem 0.B.1.

et $Q$ be a query and $\mathbf{C}$ an acyclic set of TCSs such that exactly
$s$ relations names appear in $\mathbf{C}$. Then the number of atoms in a MCS
of $Q$ wrt $\mathbf{C}$ is in $\mathcal{O}(|Q|\times|C|^{s+1})$.

###### Proof.

We analyze the number of atoms that one needs to add to $Q$ (in the worst
case) in order to make it complete. We observe that some atoms in $Q$ may need
to be also instantiated but that does not affect the maximal number of atoms
that one may need to consider. We also observe that adding more atoms may only
create queries that are more special thus they wont be maximal any more.

Since the set of TCSs is acyclic we can create a total order on the relation
names $R_{1},\ldots,R_{n}$ in $\mathbf{C}$ such that if $i<j$ then there is no
TC statement with $R_{j}$ in the head and an $R_{i}$-atom in the condition.
Further, for any relation that occurs in the condition of some TC statement
with $R_{j}$ as a head does not have and $R_{i}$-atom in the condition, and so
on recursively. In other words, completeness of $R_{j}$-atoms does not depend
on the completeness of $R_{i}$-atoms.

Now we can reason in the following way analyzing the atoms in $Q$. We start
with some $R_{1}$-atom in $Q$ (or the smallest $i$ for which $R_{i}$-atom
exists in $Q$), and we observe that to make each such atom complete (that is
to match it with some TCS) we may need (in the worst case) to introduce an
additional $|\mathbf{C}|$ atoms in $Q$. This is because each TC statement
$\mathbf{C}$ is of size at most $|\mathbf{C}|$. These introduced atoms may be
already complete or not, but again, in the worst case we may need for each of
them to introduce again $|\mathbf{C}|$ new atoms from the conditions of TC
statements. However, those new atoms are now $R_{i}$-atoms where $i\geq 2$.
Hence, repeating the same logic, for $R_{2}$ we may need to introduce at most
$|\mathbf{C}|$ many $R_{i}$-atoms, where $i\geq 3$, and so on. For
$R_{n}$-atoms in $Q$ we cannot introduce any new atom since their TCSs have an
empty condition (otherwise there would be a loop in the dependency graph).

Hence, the total number of such steps in bounded by the number of relations in
$|\mathbf{C}|$ which is $s$. Since we may need to perform this procedure for
every atom in $Q$, in the worst case the resulting query can have
$|Q|\times(|\mathbf{C}|+|\mathbf{C}|^{2}+\dots+|\mathbf{C}|^{s})$ of total
atoms, and so
$|Q|\times(|\mathbf{C}|+|\mathbf{C}|^{2}+\dots+|\mathbf{C}|^{s})\in\mathcal{O}(|Q|\times|\mathbf{C}|^{s+1})$.

∎

##  Appendix 0.C Complete Unifiers Make Queries Complete

Applying a complete unifier to $Q$ yields a complete query:

######  Proposition 0.C.1.

If $\gamma$ is a complete unifier for a CQ $Q$ and set $\mathbf{C}$ of TCSs,
then $\mathbf{C}\models\textsl{Compl}(\gamma Q)$.

###### Proof.

First let us recall the completeness characterization for minimal queries. Let
$\mathbf{C}$ be a set of TCSs and $Q(\bar{u})\leftarrow{}B$ be a minimal query
then it holds that $\mathbf{C}\models\textsl{Compl}(Q)$ iff $\theta B\subseteq
T_{\mathbf{C}}(\theta B)$. In other words,
$\mathbf{C}\models\textsl{Compl}(Q)$ iff for each $A\in B$ there exists a TCS
$C=\textsl{Compl}(A^{\prime};G)\in\mathbf{C}$ such that

$\displaystyle\theta A\in T_{C}(\theta B)=\\{\beta
A^{\prime}\mid\beta\text{~{} is a substitution ~{}and~{}~{}}{\beta
G}\subseteq\theta B\\}.$ (2)

Now we return to our queries $Q$ and $\gamma Q$ from the theorem. Wlog we
assume that $\gamma Q$ is minimal as well. From the definition of the unifier
$\gamma$ over $\gamma Q$ and $\mathbf{C}$, we have that for each atom $A_{i}$
of the query there exists a TC statement
$C_{i}=\textsl{Compl}(A_{i}^{\prime};G_{i})$ and there are atoms
$B_{i}\subseteq B$ such that $\gamma A_{i}=\gamma A_{i}^{\prime}$ and $\gamma
G_{i}=\gamma B_{i}^{\prime}$. On the other hand, if in equation (2) we set
$\beta=\theta\gamma$ we have that

$\displaystyle\theta\gamma A\in T_{C}(\theta\gamma B)=\\{\theta\gamma
A^{\prime}\mid\theta\gamma\text{~{} is a substitution
~{}and~{}~{}}{\theta\gamma G}\subseteq\theta\gamma B\\}.$

That is, equation (2) holds for $\gamma Q$, so $\gamma Q$ is complete. ∎

##  Appendix 0.D Maximal Instantiations are Produced by Complete Unifiers

######  Theorem 0.D.1.

Let $\mathbf{C}$ be a set of TCSs, $Q$ a query, and $Q^{\prime}$ a complete
instantiation of $Q$ wrt $\mathbf{C}$. Then there is a complete unifier
$\gamma$ for $Q$ and $\mathbf{C}$ such that $Q^{\prime}\sqsubseteq\gamma Q$.

###### Proof.

We restate again characterization (2) that we established in the preceding
proof. Let $\mathbf{C}$ be a set of TCSs and $Q(\bar{u})\leftarrow{}B$ be a
minimal query then it holds that $\mathbf{C}\models\textsl{Compl}(Q)$ iff
$\theta B\subseteq T_{\mathbf{C}}(\theta B)$. For a minimal query $Q$, it
holds that $\mathbf{C}\models\textsl{Compl}(Q)$ iff for each $A\in B$ there
exists a TC statement $C=\textsl{Compl}(A^{\prime};G)\in\mathbf{C}$ such that

$\displaystyle\theta A\in T_{C}(\theta B)=\\{\beta
A^{\prime}\mid\beta\text{~{} is a substitution ~{}and~{}~{}}{\beta
G}\subseteq\theta B\\}.$ (3)

Let $Q^{\prime\prime}$ be a complete specialization of $Q(\hbox to0.0pt{\hskip
2.0347pt\leavevmode\hbox{\set@color$\overline{\hbox{}}$}\hss}{\leavevmode\hbox{\set@color$X$}})\leftarrow{}A_{1},\dots,A_{n}$
and let $\alpha^{\prime}$ be a specializing substitution such that
$\alpha^{\prime}Q\equiv Q^{\prime\prime}$. In the following we construct a
complete specialization of $Q$ that is at least as general as $Q$ and that is
obtained by applying some unifier $\gamma$ on $Q$.

Wlog we assume that $\alpha^{\prime}Q$ is a minimal query. According to
characterization criteria for each atom $\alpha^{\prime}A_{i}$ in
$\alpha^{\prime}Q$ there exists a TC statement
$C_{i}=\textsl{Compl}(A_{i}^{\prime};G_{i})\in\mathbf{C}$ such that

$\theta\alpha^{\prime}A_{i}\in T_{C_{i}}(\theta\alpha^{\prime}B)=\\{\beta
A_{i}^{\prime}\mid\beta\text{~{} is a substitution ~{}and~{}~{}}{\beta
G_{i}}\subseteq\theta\alpha^{\prime}B\\}.$

From there it follows that $A_{i}$ and $A_{i}^{\prime}$ are unifiable and that
$G_{i}$ unifies with some set of atoms from $B$, say $B_{i}\subseteq B$. In
fact, assuming that TCSs and query have different variables there exist
substitutions $\beta_{i}$ such that
$\theta\alpha^{\prime}A_{i}=\beta_{i}A_{i}^{\prime}$ and
$\beta_{i}G_{i}=\theta\alpha^{\prime}B_{i}$, and thus
$\theta\alpha^{\prime}\beta_{1}\cdots\beta_{n}$ is a unifier for all pairs.

We set that $\gamma^{\prime}=\theta\alpha^{\prime}\beta_{1}\cdots\beta_{n}$
Since, pairs of are unifiable, there exists a mgu $\gamma$ that unifies all
pairs (and that is more general than $\gamma^{\prime}$, that is,
$\gamma^{\prime}\preceq\gamma$). Since $\gamma^{\prime}\preceq\gamma$ then
$Q^{\prime}=\gamma^{\prime}Q\sqsubseteq\gamma Q$. It is also not hard to see
that $\gamma Q$ is complete. Since we have that $\gamma A_{i}=\gamma
A_{i}^{\prime}$ and $\gamma G_{i}=\gamma B_{i}^{\prime}$, if in equation (3)
we set $\beta=\theta\gamma$ we have that

$\theta\gamma A_{i}\in T_{C_{i}}(\theta\gamma B)\\{\theta\gamma
A_{i}^{\prime}\mid\theta\gamma\text{~{} is a substitution
~{}and~{}~{}}{\theta\gamma G_{i}}\subseteq\theta\gamma B\\}.$

That is (3) holds for $\gamma Q$, that is, $\gamma Q$ is complete.

∎

##  Appendix 0.E The k-MCS Algorithm is Correct

First we recall the algorithm (in this document listed as Algorithm 3) that
returns all k-MCSs for a given query $Q$ and set of TCSs $\mathbf{C}$.

Input : a query $Q(\bar{u})\leftarrow{}B$, a set $\mathbf{C}$ of TCSs ,
$k\in\mathbb{N}_{0}$

Output : the set $\mathcal{S}$ of all $k$-MCSs of $Q$ wrt $\mathbf{C}$

1 $\mathcal{S}:=\emptyset$

2foreach  _set $B^{\prime}$ of fresh atoms of size $n+k-1$ over
$\Sigma_{\mathbf{C}}$ _ do

3 construct $Q^{\prime\prime}(\bar{u})\leftarrow{}B,B^{\prime}$

4 $\mathcal{S}:=\mathcal{S}\cup\mathtt{MCI}_{\leq
n+k}(Q^{\prime\prime},\mathbf{C})$

5 foreach  _$Q^{\prime\prime}$ in $\mathcal{S}$_ do

6 if  _exists $Q^{\prime\prime\prime}\in\mathcal{S}$ such that
$Q^{\prime\prime}\sqsubseteq Q^{\prime\prime\prime}$_ then
$\mathcal{S}:=\mathcal{S}\setminus\\{Q^{\prime\prime}\\}$

7

return _$\mathcal{S}$_

Algorithm 4 Computes k-MCSs

######  Theorem 0.E.1 (k-MCS Algorithm).

Let $Q$ be a CQ, $\mathbf{C}$ a set of TCSs, $k$ a nonnegative integer and
$\textsl{k-}\textsl{MCS}(Q,\mathbf{C})$ be the set of queries returned by
Algorithm 3. Then for every query $Q^{\prime}$:

$Q^{\prime}\in\textsl{k-}\textsl{MCS}(Q,\mathbf{C})\quad\text{iff}\quad
Q^{\prime}\text{~{}is a k-MCS of~{}}Q\text{~{}wrt~{}~{}}\mathbf{C}.$

###### Proof.

Let $b$ be the size of $Q$, i.e. the number of atoms in $Q$.

_(Soundness)._ We show that the algorithm only returns complete
specializations of $Q$ of size $\leq n+k$.

An extension of $Q$ is a specialization of $Q$. So each constructed query
$Q^{\prime\prime}$ (Line 3) is a specialization of $Q$. Next, the call
$\mathtt{MCI}_{len+k}(Q^{\prime\prime},\mathbf{C})$ returns complete
specializations of $Q^{\prime\prime}$ (therefore also of $Q$) of size $\leq
n+k$. Thus $\mathcal{S}$ can only contain such queries, and since the
algorithm returns a subset of $\mathcal{S}$, it can only return such queries.

_(Completeness)._ Let us assume that our input query $Q$ is of the form
$Q(\bar{u})\leftarrow{}B$, where $B$ is a set of $n$ atoms. And let
$Q^{\prime}(\bar{u}^{\prime})\leftarrow{}B^{\prime}$ be a complete
specialization of $Q$ of size $\leq n+k$. We show that our algorithm returns a
complete specialization of $Q$ of size $\leq n+k$ that is more general than
$Q^{\prime}$.

To do so, we construct a query $Q^{\prime\prime}$ that is one of the candidate
queries generated by our algorithm (Line 2) for $Q$ as input, in such a way
that $Q^{\prime\prime}$ is more general than $Q^{\prime}$ (i.e.
$Q^{\prime}\sqsubseteq Q^{\prime\prime}$). In other words, $Q^{\prime}$ is a
complete instantiation of $Q^{\prime\prime}$. Therefore, after the algorithm
(Line 4) calls $\texttt{MCI}_{\leq n+k}(Q^{\prime\prime},\mathbf{C})$, the set
$\mathcal{S}$ will contain either $Q^{\prime}$ itself or a query that is more
general than $Q^{\prime}$. Together with the fact that the algorithm returns
the maximal elements of $\mathcal{S}$ (Lines 5 to 7), this proves our claim.

The query $Q^{\prime\prime}$ is of the form
$Q^{\prime\prime}(\bar{u})\leftarrow{}B,B^{\prime\prime\prime},B^{\prime\prime\prime\prime}$,
where the sets of atoms $B^{\prime\prime\prime}$ and
$B^{\prime\prime\prime\prime}$ are defined as follows. Since $Q^{\prime}$ is a
specialization of $Q$, there exists a homomorphism $\delta\colon Q\to
Q^{\prime}$ such that $\delta B\subseteq B^{\prime}$. Let
$B^{\prime\prime}=B^{\prime}\setminus\delta B$. We observe that
$|B^{\prime\prime}|<n+k-1$, since $\delta$ has to map $B$ to at least one atom
in $B^{\prime}$. We define $B^{\prime\prime\prime}$ as a fresh version of
$B^{\prime\prime}$, that is, a set of atoms identical to $B^{\prime\prime}$,
but where each variable is replaced with a fresh one (note that
$B^{\prime\prime\prime}$ also has size $<n+k-1$). To define
$B^{\prime\prime\prime\prime}$, we select an arbitrary atom $A$ in $B$, and
construct $B^{\prime\prime\prime\prime}$ with enough repeated fresh version of
$A$ so that
$|B|+|B^{\prime\prime\prime}|+|B^{\prime\prime\prime\prime}|=n+n+k-1$.

To conclude the proof, we show that $Q^{\prime}\sqsubseteq Q^{\prime\prime}$.
First, we observe that $B^{\prime\prime\prime\prime}$ is “redundant” in
$Q^{\prime\prime}$, meaning that dropping $B^{\prime\prime\prime\prime}$
yields an equivalent query. So in order to show that $Q^{\prime}\sqsubseteq
Q^{\prime\prime}$, it is sufficient to show that there is a homomorphism from
$(B,B^{\prime\prime\prime})$ to $B^{\prime}$. Such a homomorphism can be
constructed by extending $\delta$ (which, as a reminder, maps $B$ to
$B^{\prime}$) with a substitution $\delta^{\prime}$ that maps
$B^{\prime\prime\prime}$ to $B^{\prime}$ and is compatible with $\delta$.
Trivially, from the construction of $B^{\prime\prime\prime}$, such a
substitution exists: since $B^{\prime\prime\prime}$ is constructed out of
$B^{\prime\prime}\subseteq B^{\prime}$ by renaming variables with fresh ones,
$\delta^{\prime}$ can be defined as the inverse of this renaming.

∎