# A Framework for Combining Entity Resolution and
Query Answering in Knowledge Bases

Ronald Fagin1 Phokion G. Kolaitis1,2 Domenico Lembo3 Lucian Popa1 Federico
Scafoglieri3
1IBM Research, Almaden, USA
2UC Santa Cruz, USA
3Sapienza University of Rome, Italy
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We propose a new framework for combining entity resolution and query answering
in knowledge bases (KBs) with tuple-generating dependencies (tgds) and
equality-generating dependencies (egds) as rules. We define the semantics of
the KB in terms of special instances that involve equivalence classes of
entities and sets of values. Intuitively, the former collect all entities
denoting the same real-world object, while the latter collect all alternative
values for an attribute. This approach allows us to both resolve entities and
bypass possible inconsistencies in the data. We then design a chase procedure
that is tailored to this new framework and has the feature that it never
fails; moreover, when the chase procedure terminates, it produces a universal
solution, which in turn can be used to obtain the certain answers to
conjunctive queries. We finally discuss challenges arising when the chase does
not terminate.

##  1 Introduction

Entity resolution is the problem of determining whether different data records
refer to the same real-world object, such as the same individual or the same
organization, and so on (?; ?). In this paper, we study entity resolution in
combination with query answering in the context of knowledge bases (KBs)
consisting of ground atoms and rules specified as tuple-generating
dependencies (tgds) and equality-generating dependencies (egds). These rules
have been widely investigates in databases and knowledge representation, e.g.
in (?; ?; ?; ?; ?; ?); in particular, they allow expressing both data
transformations and classical axioms used in Description Logic (DL) (?; ?) and
Datalog +/- ontologies (?). In addition, egds are employed to express typical
entity resolution rules that one may write in practice, i.e., rules that
enforce equality between two entities, as in (?). The KBs considered here
separate out _entities_ and _values_ and involve $n$-ary predicates that
denote $n$-ary relations, $n\geq 1$, over entities and/or values from
predefined datatypes. As is customary for ontologies, the _TBox_ is the
intensional component (i.e., the rules) of a KB, while the _database_ of the
KB is its extensional component (i.e., the ground atoms).

$\textnormal{{Doe}}_{1}$358John DoeHPhoneName$\textnormal{{Doe}}_{2}$635J.
DoeHPhoneName

(a) Before entity resolution.

$\textnormal{{Doe}}_{1}$358John Doe$\textnormal{{Doe}}_{2}$635J. DoeHPhoneName

(b) After entity resolution.

Figure 1: Ground Atoms of the Knowledge Base

As an example, Fig. 1(a) depicts a set of ground atoms, where
$\textnormal{{Doe}}_{1}$ and $\textnormal{{Doe}}_{2}$ are entities while the
rest are values (indicating names and landline home phone numbers). Fig. 2
illustrates a small TBox (containing only egds, for simplicity).

$\displaystyle\begin{array}[]{ll}(s_{1})&\mathit{Name}(p_{1},n_{1})\wedge\mathit{Name}(p_{2},n_{2})\wedge\mathit{JaccSim}(n_{1},n_{2},0.6)\\\
&\rightarrow p_{1}=p_{2}\\\
(s_{2})&\mathit{Name}(p,n_{1})\wedge\mathit{Name}(p,n_{2})\rightarrow
n_{1}=n_{2}\\\
(s_{3})&\mathit{HPhone}(p,f_{1})\wedge\mathit{HPhone}(p,f_{2})\rightarrow
f_{1}=f_{2}\end{array}$
Figure 2: Entity-egds and value-egds.

To capture entity resolution rules, we allow egds to contain atoms involving
built-in predicates, such as $\mathit{JaccSim}$. In the example, rule $s_{1}$
states that two names (i.e., strings) with Jaccard similarity above $0.6$ must
belong to the same individual. Rules $s_{2}$ and $s_{3}$ stipulate that an
individual has at most one name and at most one landline home phone number,
respectively. We call _entity-egds_ rules that impose equality on two entities
(e.g., $s_{1}$), and we call _value-egds_ rules that impose equality on two
values (e.g., $s_{2}$ and $s_{3}$).

It is now easy to see that, according to the standard semantics, the database
in Fig. 1(a) does not satisfy the entity-egd $s_{1}$ (note that the Jaccard
similarity of John Doe and J. Doe is $0.625$). Thus, the main challenge one
has in practice is to come up with a consistent way to complete or modify the
original KB, while respecting all its rules.

In this paper, we develop a framework for entity resolution and query
answering in KBs, where the valid models, called _KB solutions_ , must satisfy
all entity resolution rules along with all other KB rules; furthermore, the
solutions must include all original data (i.e., no information is ever dropped
or altered). Our approach is guided by the intuitive principle that for each
real-world object there must be a single node in the solution that represents
all “equivalent” entities denoting the object. To achieve this, we use
equivalence classes of entities, which become first-class citizens in our
framework. In addition, we relax the standard way in which value-egds are
satisfied by allowing solutions to use sets of values, thus collecting
together all possible values for a given attribute (e.g., the second argument
of $\mathit{Name}$ or $\mathit{HPhone}$). Continuing with the above example,
Fig. 1(b) shows a new set of ground atoms that uses equivalence classes and
sets of values.

We remark that the use of equivalence classes of entities and sets of values
in KB solutions requires a drastic revision of the classical notion of
satisfaction for tgds and egds. Intuitively, we interpret egds as matching
dependencies (?; ?). That is, when the conditions expressed by (the body of)
an entity-egd or a value-egd hold in the data (and thus two entities or two
values must be made equal), we combine them through a merging function. We
adopt a general and common merging function that takes the union of the
entities or the union of the values. This function actually belongs to the
_Union class of match and merge functions_ analyzed in (?; ?). In this way, we
group all possible alternatives for denoting an object into a unique set of
entities. Similarly, when two values exist where only one value is instead
allowed according to the TBox, we explicitly form their union. Note that we
consider the union of entities a “global” feature for a solution, that is, an
entity $e$ may belong to exactly one equivalence class; in contrast, the union
of values is “local” to the context in which a value occurs, that is, a
particular value may belong to more than one set of values. For instance, let
us add $\mathit{HPhone}(\textnormal{{Doe}}_{3},\texttt{358})$ to the KB of our
example. Then, in a solution satisfying the KB, 358 belongs to two different
sets: the one shown in Fig. 1(b) (i.e., $\\{\texttt{358},\texttt{635}\\}$) and
the singleton $\\{\texttt{358}\\}$, which is the set of landline home phone
numbers of $\textnormal{{Doe}}_{3}$.

It is worth noting that the semantics we adopt for value-egds allows us to
always have a solution (that is, a model) for a KB, even when there are no
models according to the standard first-order semantics; for example, if a
value-egd enforces the equality of two different values, then first-order
logic concludes that the KB is inconsistent. We thus may say that our
semantics is inconsistency tolerant with respect to violations of value-egds.
Indeed, we collect together all possible alternative values for individual
attributes, whereas in data cleaning the task is to choose one of the
alternatives.

We also point out that value-egds may substantially affect entity resolution.
As an example, consider the database in Fig. 1(a) and on top of it the new set
of rules given below

$\displaystyle\begin{array}[]{ll}(s^{\prime}_{1})&\mathit{Name}(p_{1},n_{1})\wedge\mathit{HPhone}(p_{1},f)\wedge\mathit{Name}(p_{2},n_{2})\wedge\\\
&\mathit{HPhone}(p_{2},f)\wedge\mathit{JaccSim}(n_{1},n_{2},0.6)\rightarrow
p_{1}=p_{2}\\\
(s^{\prime}_{2})&\mathit{Name}(p_{1},n_{1})\wedge\mathit{Name}(p_{2},n_{2})\wedge\mathit{HPhone}(p_{1},f_{1})\wedge\\\
&\mathit{HPhone}(p_{2},f_{2})\wedge\mathit{JaccSim}(n_{1},n_{2},0.6)\rightarrow
f_{1}=f_{2}\\\\[8.53581pt] \end{array}$

Rule $s^{\prime}_{1}$ states that two entities having similar names and the
same landline home phone number denote the same real-world individual, while
rule $s^{\prime}_{2}$ says that two entities with similar names must have the
same phone number. It is easy to see that a TBox having only rule
$s^{\prime}_{1}$ would not lead to inferring that $\textnormal{{Doe}}_{1}$ and
$\textnormal{{Doe}}_{2}$ denote the same individual. However, by virtue of
rule $s^{\prime}_{2}$, a solution has to group together the two telephone
numbers into the same set, thus saying that $\textnormal{{Doe}}_{1}$ and
$\textnormal{{Doe}}_{2}$ have both the landline home phone numbers
$\\{\texttt{635},\texttt{358}\\}$. This union “fires” rule $s^{\prime}_{1}$,
and thus entities are resolved, i.e., are put together into the same
equivalence class of the solution.

We finally note that, in order to maximize entity resolution, our semantics
allows the body a rule to be satisfied by assignments in which different
occurrences of the same value-variable are replaced by different sets of
values, as long as these sets have a non-empty intersection (instead of
requiring that all occurrences are replaced by the same set of values).

For instance, if we add to the rules in Fig. 2 the tgd

$\begin{array}[]{l}\mathit{HPhone}(p_{1},f)\wedge\mathit{HPhone}(p_{2},f)\rightarrow\mathit{SameHouse}(p_{1},p_{2},f)\\\\[8.53581pt]
\end{array}$

stating that two entities with the same home phone number live in the same
house, and to the database in Fig. 1(a) the atom
$\mathit{HPhone}(\textnormal{{Doe}}_{3},\texttt{358})$, we can conclude that
the individual denoted by $\textnormal{{Doe}}_{3}$ and the individual denoted
by $\textnormal{{Doe}}_{1}$ and $\textnormal{{Doe}}_{2}$ live in the same
house (since they share one phone number).onsistently with this choice, we
also require tgds to “propagate” such intersections. Then, through the above
tgd, we also infer that the phone number of the house is
$\\{\texttt{358}\\}$,which we denote with a fact of the form
$\mathit{SameHouse}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],[\textnormal{{Doe}}_{3}],\\{\texttt{358}\\})$.
Note that the behaviour we described differs from the standard one only for
value-variables, since two equivalence classes of entities are always either
disjoint or the same class.

In this paper, we formalize the aforementioned ideas and investigate query
answering, with focus on conjunctive queries (CQs). The main contributions are
as follows.

  * •

We propose a new framework for entity resolution in KBs consisting of tgds and
egds, and give rigorous semantics.

  * •

We define _universal solutions_ and show that, as for standard tgd and egd
semantics, universal solutions can be used to obtain the certain answers of
CQs.

  * •

We propose a variant of the classical _chase_ procedure (?; ?) tailored to our
approach. An important feature of our chase procedure is that it never fails,
even in the presence of egds. At the same time, as in other frameworks, our
chase procedure might not terminate.

  * •

We show that, when the chase procedure terminates, it returns a universal
solution (and thus we have an algorithm for computing the certain answers to
conjunctive queries).

  * •

When the chase procedure does not terminate, defining the result of the chase
becomes a more intricate task. We point out that the strategy proposed in (?)
does not work in our framework. Thus a different notion of the result of the
chase is needed, which we leave for future study.

The rest of the paper is organized as follows. In Section 2 we give some
background notions useful for the following treatment. In Section 3 we propose
our framework and give the notions of instance, solution and universal
solution for a KB. In Section 4 we define query answering and show that for
CQs it can be solved through query evaluation over a universal solution. In
Section 5 we first define the chase procedure in our setting, and discuss the
case of terminating chase sequences, for which the chase procedure returns a
universal solution; then we attack the challenging case of non-terminating
chase sequences, for which we show that previously proposed approaches cannot
directly adapted to our setting. In Section 6 we discuss some related work,
and in Section 7 we conclude the paper.

##  2 Basic Notions

Equivalence relations. If $\mathcal{Z}$ is a set, then an _equivalence
relation on $\mathcal{Z}$_ is a binary relation
$\theta\subseteq\mathcal{Z}\times\mathcal{Z}$ that is reflexive (i.e.,
$x\>\theta\>x$, for every $x\in\mathcal{Z}$), symmetric (i.e., $x\>\theta\>y$
implies $y\>\theta\>x$, for every $x,y\in\mathcal{Z}$), and transitive (i.e.,
$x\>\theta\>y$ and $y\>\theta\>z$ imply $x\>\theta\>z$, for every
$x,y,z\in\mathcal{Z}$).

If $x\in\mathcal{Z}$, then the _equivalence class of $x$ w.r.t. $\theta$_ is
the set $[x]_{\theta}=\\{y\in\mathcal{Z}\>\mid\>y\>\theta\>x\>\\}$. Sometimes,
we will write $[x]$ instead of $[x]_{\theta}$, if $\theta$ is clear from the
context. Moreover, we may write, e.g., $[a,b,c]_{\theta}$ (or simply
$[a,b,c]$) to denote the equivalence class consisting of the elements $a$,
$b$, and $c$.

The equivalence classes of an equivalence relation $\theta$ have the following
well known properties: (i) each equivalence class is non-empty; (ii) for all
$x,y\in\mathcal{Z}$, we have that $x\theta y$ if and only if
$[x]_{\theta}=[y]_{\theta}$; (iii) two equivalence classes are either equal
sets or disjoint sets. Consequently, the equivalence classes of $\theta$ form
a partition of $\mathcal{Z}$. The _quotient set $\mathcal{Z}/\theta$ of
$\theta$ on $\mathcal{Z}$_ is the set of all equivalence classes over
$\mathcal{Z}$ w.r.t. $\theta$, i.e.,
$\mathcal{Z}/\theta=\\{[x]_{\theta}\>|\>x\in\mathcal{Z}\\}$. Obviously, given
a quotient set $\mathcal{Z}/\theta$, we have that
$\mathcal{Z}=\underset{[x]_{\theta}\in\mathcal{Z}/\theta}{\bigcup}[x]_{\theta}$.

Alphabets and conjunctions of atoms. We consider four pairwise disjoint
alphabets $\mathcal{S}_{P}$, $\mathcal{S}_{E}$, $\mathcal{S}_{V}$, and
$\mathcal{S}_{\mathcal{V}}$. The set $\mathcal{S}_{P}$ is a finite alphabet
for predicates; it is partitioned into the sets $\mathcal{S}_{O}$ and
$\mathcal{S}_{B}$, which are the alphabets for _KB_ predicates and _built-in_
predicates, respectively. The sets $\mathcal{S}_{E}$, $\mathcal{S}_{V}$, and
$\mathcal{S}_{\mathcal{V}}$ are countable infinite alphabets for _entities_ ,
_values_ , and _variables_ , respectively. For ease of exposition, we do not
distinguish between different data types, thus $\mathcal{S}_{V}$ is a single
set containing all possible values.

The number of arguments of a predicate $P\in\mathcal{S}_{P}$ is the _arity_ of
$P$, denoted with $\mathit{arity}(P)$. With each $n$-ary predicate $P$ we
associate a tuple $\mathit{type}(P)=\langle\rho_{1},\ldots\rho_{n}\rangle$,
such that, for each $1\leq i\leq n$, either $\rho_{i}=\mathsf{e}$ or
$\rho_{i}=\mathsf{v}$. This tuple specifies the _types of the arguments of
$P$_, i.e., whether each argument of $P$ ranges over entities ($\mathsf{e}$)
or values ($\mathsf{v}$). We also write $\mathit{type}(P,i)$ for the _type_
$\rho_{i}$ of the $i$-th argument of $P$.

Note that the built-in predicates from $\mathcal{S}_{B}$ are special, pre-
interpreted predicates, whose arguments range only over values, i.e., if $B$
is an $n$-ary built-in predicate, then $\mathit{type}(B)$ is the $n$-ary tuple
$\langle\mathsf{v},\ldots,\mathsf{v}\rangle$. The examples in Sec. 1 use the
Jaccard similarity $\mathit{JaccSim}$ as a built-in predicate.

An _atom_ is an expression $P(t_{1},\dots,t_{n})$, where
$P\in\mathcal{S}_{P}$, and each $t_{i}$ is either a variable from
$\mathcal{S}_{\mathcal{V}}$ or a constant, which in turn is either an entity
from $\mathcal{S}_{E}$, if $\mathit{type}(P,i)=\mathsf{e}$, or a value from
$\mathcal{S}_{V}$, if $\mathit{type}(P,i)=\mathsf{v}$. When
$t_{i}\in\mathcal{S}_{\mathcal{V}}$, we call it an _entity-variable_ if
$\mathit{type}(P,i)=\mathsf{e}$, or a _value-variable_ , if
$\mathit{type}(P,i)=\mathsf{v}$. A _ground_ atom is an atom with no variables.

A _conjunction $\phi(\mathbf{x})$ of atoms_ is an expression
$P_{1}(\mathbf{t}_{1})\land\ldots\land P_{m}(\mathbf{t}_{m})$, where each
$P_{j}(\mathbf{t}_{j})$ is an atom such that each variable in $\mathbf{t}_{j}$
is among those in $\mathbf{x}$. We also require that every variable $x$ in
$\mathbf{x}$ is either an entity-variable or a value-variable and that, if $x$
occurs in an atom whose predicate is built-in (note that thus $x$ is a value-
variable), then there exists some other atom $P_{j}(\mathbf{t}_{j})$ in
$\phi(\mathbf{x})$ such that $P_{j}\in\mathcal{S}_{O}$ and $x$ is in
$\mathbf{t}_{j}$. If a conjunction contains no built-in predicates, we say
that it is _built-in free_ ; if it contains no entities or values, we say that
it is _constant-free_.

Remark on notation. As done in this section, in the formulas appearing
throughout the paper, we use $e$ to denote an entity from $\mathcal{S}_{E}$,
we use $v$ to denote a value from $\mathcal{S}_{V}$, we use $c$ to denote a
constant (i.e., $c\in\mathcal{S}_{E}\cup\mathcal{S}_{V}$), we use $x$, $y$,
$w$, and $z$ to denote variables from $\mathcal{S}_{\mathcal{V}}$, and we use
$t$ to denote terms (i.e.,
$t\in\mathcal{S}_{\mathcal{V}}\cup\mathcal{S}_{E}\cup\mathcal{S}_{V}$).
Typically, we use $P$ to denote a predicate from $\mathcal{S}_{P}$. All the
above symbols may appear with subscripts. In the examples, we use self-
explanatory symbols, and we write entities in bold font and values in true
type font.

##  3 Framework

In this section, we present the syntax and the semantics of a framework for
entity resolution in knowledge bases.

Syntax. A _knowledge base_ (KB) $\mathcal{K}$ is a pair
$(\mathcal{T},\mathbf{D})$, consisting of a TBox $\mathcal{T}$ and a database
$\mathbf{D}$. The TBox is a finite set of _tuple-generating dependencies_
(tgds) and _equality-generating dependencies_ (egds). A _tgd_ is a formula

$\displaystyle\begin{array}[]{c}\forall\mathbf{x}(\phi(\mathbf{x})\rightarrow\exists\mathbf{y}\psi(\mathbf{x},\mathbf{y})),\end{array}$
(2)

where $\phi(\mathbf{x})$ and $\psi(\mathbf{x},\mathbf{y})$ are conjunctions of
atoms, such that $\mathbf{x}$ and $\mathbf{y}$ have no variables in common and
$\psi(\mathbf{x},\mathbf{y})$ is built-in free and, for simplicity, constant-
free. As in (?), we assume that all variables in $\mathbf{x}$ appear in
$\phi(\mathbf{x})$, but not necessarily in $\psi(\mathbf{x},\mathbf{y})$. We
call $\phi(\mathbf{x})$ the body of the tgd, and $\psi(\mathbf{x},\mathbf{y})$
the head of it.

An _egd_ is a formula

$\forall\mathbf{x}(\phi(\mathbf{x})\rightarrow y=z),$ (3)

where $\phi(\mathbf{x})$ is a conjunction of atoms and $y$ and $z$ are
distinct variables occurring in $\phi(\mathbf{x})$, such that either both $y$
and $z$ are entity-variables (in which case we have an _entity-egd_) or both
$y$ and $z$ are value-variables (in which case we have a _value-egd_). We call
$\phi(\mathbf{x})$ the body of the egd. For _value-egds_ , we require that
neither $y$ nor $z$ occur in atoms having a built-in as predicate. This
ensures that the meaning of built-ins remains fixed. We will write
$\mathsf{body}(r)$ to denote the body of a tgd or an egd $r$; furthermore, we
may write $r$ with no quantifiers.

######  Example 1.

Let $\mathcal{T}$ be the TBox consisting of the rules

$\displaystyle\begin{array}[]{ll}(r_{1})&\mathit{CI}(p_{1},\mathit{name}_{1},\mathit{phone}_{1})\wedge\mathit{CI}(p_{2},\mathit{name}_{2},\mathit{phone}_{2})\wedge\\\
&\mathit{JaccSim}(\mathit{name}_{1},\mathit{name}_{2},0.6)\rightarrow
p_{1}=p_{2}\\\
(r_{2})&\mathit{CI}(p,\mathit{name}_{1},\mathit{phone}_{1})\wedge\mathit{CI}(p,\mathit{name}_{2},\mathit{phone}_{2})\\\
&\rightarrow\mathit{name}_{1}=\mathit{name}_{2}\\\
(r_{3})&\mathit{CI}(p,\mathit{name}_{1},\mathit{phone}_{1})\wedge\mathit{CI}(p,\mathit{name}_{2},\mathit{phone}_{2})\\\
&\rightarrow\mathit{phone}_{1}=\mathit{phone}_{2}\\\
(r_{4})&\mathit{CI}(p,\mathit{name},\mathit{phone})\rightarrow\mathit{Emp}(p,\mathit{comp})\wedge\mathit{CEO}(\mathit{comp},\mathit{dir})\\\
(r_{5})&\mathit{Emp}(p,\mathit{comp}_{1})\wedge\mathit{Emp}(p,\mathit{comp}_{2})\rightarrow\mathit{comp}_{1}=\mathit{comp}_{2}\\\
(r_{6})&\mathit{CI}(p_{1},\mathit{name}_{1},\mathit{phone})\wedge\mathit{CI}(p_{2},\mathit{name}_{2},\mathit{phone})\\\
&\rightarrow\mathit{SameHouse}(p_{1},p_{2},\mathit{phone})\end{array}$

Here,
$\mathit{type}(\mathit{CI})=\langle\mathsf{e},\mathsf{v},\mathsf{v}\rangle$,
$\mathit{type}(\mathit{Emp})=\langle\mathsf{e},\mathsf{e}\rangle$,
$\mathit{type}(\mathit{CEO})=\langle\mathsf{e},\mathsf{e}\rangle$, and
$\mathit{type}(\mathit{SameHouse})=\langle\mathsf{e},\mathsf{e},\mathsf{v}\rangle$.
The predicates have the meaning suggested by their names. In particular, the
predicate $\mathit{CI}$ maintains contact information of individuals, whereas
$\mathit{Emp}$ associates employees to the companies they work for. Each of
the six rules makes an assertion about the predicates. In particular, rule
$r_{1}$ states that if the Jaccard similarity of two names is higher then
$0.6$, then these names are names of the same individual. The TBox also says
that everyone can have only one name ($r_{2}$) and only one the landline phone
number ($r_{3}$); everyone having contact information is also an employee in
some company which in turn has a CEO ($r_{4}$); everyone can work for only one
company ($r_{5}$); two individuals with the same landline phone number live in
the same house ($r_{6}$). ∎

The database $\mathbf{D}$ of a KB $\mathcal{K}$ is a finite set of ground
atoms of the form $P(c_{1},\ldots,c_{n})$ over the alphabets
$\mathcal{S}_{P}$, $\mathcal{S}_{E}$, and $\mathcal{S}_{V}$, where
$P\in\mathcal{S}_{P}$ and each $c_{i}$ is an entity from $\mathcal{S}_{E}$, if
$\mathit{type}(P,i)=\mathsf{e}$, or a value from $\mathcal{S}_{V}$, if
$\mathit{type}(P,i)=\mathsf{v}$.

######  Example 2.

Let $\mathbf{D}$ be the database consisting of the atoms

$\displaystyle\begin{array}[]{llll}(g_{1})&\mathit{CI}(\textnormal{{Doe}}_{1},\texttt{J.
Doe},\texttt{358})&~{}~{}~{}(g_{4})&\mathit{Emp}(\textnormal{{Doe}}_{2},\textnormal{{Yahoo}})\\\
(g_{2})&\mathit{CI}(\textnormal{{Doe}}_{2},\texttt{John
Doe},\texttt{635})&~{}~{}~{}(g_{5})&\mathit{Emp}(\textnormal{{Doe}}_{3},\textnormal{{IBM}})\\\
(g_{3})&\mathit{CI}(\textnormal{{Doe}}_{3},\texttt{Mary
Doe},\texttt{358})&~{}~{}~{}(g_{6})&\mathit{CEO}(\textnormal{{Yahoo}},\textnormal{{Doe}}_{1}).\end{array}$

In particular, the atom $g_{1}$ of $\mathbf{D}$ asserts that
$\textnormal{{Doe}}_{1}$ has name J.Doe and phone number 358. Moreover, the
database $\mathbf{D}$ also specifies that $\textnormal{{Doe}}_{1}$ has phone
number 358 ($g_{1}$), $\textnormal{{Doe}}_{2}$ has name John Doe and phone
number 635 ($g_{2}$), $\textnormal{{Doe}}_{3}$ has name Mary Doe and phone
number 358 ($g_{3}$), $\textnormal{{Doe}}_{2}$ is employee of Yahoo ($g_{4}$),
$\textnormal{{Doe}}_{3}$ is employee of IBM ($g_{5}$), and the CEO of Yahoo is
$\textnormal{{Doe}}_{1}$ ($g_{6}$). ∎

To ensure that built-in predicates have the same semantics in every KB, we
assume that we have a fixed (infinite and countable) set $GB$ of ground atoms
of the form $B(v_{1},..v_{n})$, where $B$ is in $\mathcal{S}_{B}$ and
$v_{1},..v_{n}$ are in $\mathcal{S}_{V}$. Intuitively, $GB$ contains all facts
about built-in predicates that hold overall. Given a KB
$\mathcal{K}=(\mathcal{T},\mathbf{D})$, we assume that
$\mathbf{D}=\mathbf{D}_{O}\cup\mathbf{D}_{B}$, where $\mathbf{D}_{O}$ contains
only ground atoms with predicate from $\mathcal{S}_{O}$ and $\mathbf{D}_{B}$
is the (finite) set of all atoms in $GB$ whose built-in predicates and values
are mentioned in $\mathcal{T}$ and in $\mathbf{D}_{O}$.

Semantics. Let $\mathcal{S}_{EN}$ and $\mathcal{S}_{VN}$ be two infinite,
countable, disjoint sets that are also disjoint from the alphabets introduced
in Sec. 2. We call $\mathcal{S}_{EN}$ the set of entity-nulls and
$\mathcal{S}_{VN}$ the set of value-nulls; their union is referred to as the
set of nulls. We use $\mathit{sig}(\mathcal{K})$ to denote the signature of a
KB $\mathcal{K}$, i.e., the set of symbols of $\mathcal{S}_{P}$,
$\mathcal{S}_{E}$ and $\mathcal{S}_{V}$ occurring in $\mathcal{K}$.

The semantics of a KB is given using special databases, called KB _instances_
, whose ground atoms have components that are either equivalence classes of
entities and entity-nulls or non-empty sets of values and value-nulls.

######  Definition 1.

Let $\mathcal{K}$ be a KB, $\mathcal{S}$ a subset of
$(\mathcal{S}_{E}\cap\mathit{sig}(\mathcal{K}))\cup\mathcal{S}_{EN}$, and
$\sim$ an equivalence relation on $\mathcal{S}$, called the equivalence
relation _associated_ with $\mathcal{K}$. An _instance $\mathcal{I}$ for
$\mathcal{K}$ w.r.t. $\sim$_ is a set of _facts_ $P(T_{1},\ldots,T_{n})$ such
that $P\in\mathcal{S}_{P}\cap\mathit{sig}(\mathcal{K})$,
$\mathit{arity}(P)=n$, and, for each $1\leq i\leq n$, we have that
$T_{i}\neq\emptyset$ and either $T_{i}\in{\mathcal{S}/\sim}$, if
$\mathit{type}(P,i)=\mathsf{e}$, or
$T_{i}\subseteq(\mathcal{S}_{V}\cap\mathit{sig}(\mathcal{K}))\cup\mathcal{S}_{VN}$,
if $\mathit{type}(P,i)=\mathsf{v}$.

To denote an equivalence class in $\mathcal{I}$, we may use the symbol $E$
(possibly with a subscript). Note that an equivalence class $E$ in
$\mathcal{I}$ may contain both entities and entity-nulls. In the sequel, we
may simply refer to $E$ as an equivalence class of entities. Similarly, a non-
empty subset of
$(\mathcal{S}_{V}\cap\mathit{sig}(\mathcal{K}))\cup\mathcal{S}_{VN}$ in
$\mathcal{I}$ can be simply referred to as a set of values, denoted with the
symbol $V$ (possibly with a subscript). We will use $T$ (possibly with a
subscript) to denote a set that can be either an equivalence class of entities
or a set of values.

######  Definition 2.

Let $\mathcal{K}$ be a KB and let $\mathcal{I}$ be an instance for
$\mathcal{K}$ w.r.t. to an equivalence relation $\sim$.

The _active domain of $\mathcal{I}$_, denoted by
$\mathit{active}(\mathcal{I})$, is the set

$\\{T\mid\mbox{there are $P(T_{1},\ldots,T_{n})\in\mathcal{I}$ and $i\leq n$
with $T=T_{i}$}\\}$.

We write $\mathit{active}_{E}(\mathcal{I})$ and
$\mathit{active}_{V}(\mathcal{I})$ to denote the set of all equivalence
classes of entities and the set of all sets of values contained in
$\mathit{active}(\mathcal{I})$, respectively. Obviously,
$\mathit{active}(\mathcal{I})=\mathit{active}_{E}(\mathcal{I})\cup\mathit{active}_{V}(\mathcal{I})$.

The _underlying domain of $\mathcal{I}$_, denoted by
$\mathit{under}(\mathcal{I})$, is the set
$\mathit{under}_{E}(\mathcal{I})\cup\mathit{under}_{V}(\mathcal{I})$, where

$\mathit{under}_{E}(\mathcal{I})=\\{e\mid\mbox{there is
$E\in\mathit{active}_{E}(\mathcal{I})$ and $e\in E$}\\}$

and

$\mathit{under}_{V}(\mathcal{I})=\\{v\mid\mbox{there is
$V\in\mathit{active}_{V}(\mathcal{I})$ and $v\in V$}\\}$.

If $\mathcal{I}$ is an instance of $\mathcal{K}$ w.r.t. $\sim$, then it is
easy to see that $\mathcal{I}$ is an instance of $\mathcal{K}$ w.r.t. the
equivalence relation $\sim^{\prime}$ induced on
$\mathit{under}_{E}(\mathcal{I})$ by $\sim$. In what follows, we will consider
only instances w.r.t. equivalence relations over
$\mathcal{S}=\mathit{under}_{E}(\mathcal{I})$. Furthermore, we may simply call
$\mathcal{I}$ an instance for $\mathcal{K}$ and leave the equivalence relation
associated with $\mathcal{I}$ implicit.

######  Example 3.

Let $\mathcal{K}=(\mathcal{T},\mathbf{D})$ be a KB such that $\mathcal{T}$ and
$\mathbf{D}$ are as in Ex. 1 and in Ex. 2, respectively. Then, consider the
following set $\mathcal{I}$ of facts:

$\begin{array}[]{ll}(d_{1})\mathit{CI}([\textnormal{{Doe}}_{1}],\\{\texttt{J.
Doe}\\},\\{\texttt{358}\\})&(d_{4})\mathit{Emp}([\textnormal{{Doe}}_{2}],[\textnormal{{Yahoo}}])\\\
(d_{2})\mathit{CI}([\textnormal{{Doe}}_{2}],\\{\texttt{John
Doe}\\},\\{\texttt{635}\\})&(d_{5})\mathit{Emp}([\textnormal{{Doe}}_{3}],[\textnormal{{IBM}}])\\\
(d_{3})\mathit{CI}([\textnormal{{Doe}}_{3}],\\{\texttt{Mary
Doe}\\},\\{\texttt{358}\\})&(d_{6})\mathit{CEO}([\textnormal{{Yahoo}}],[\textnormal{{Doe}}_{1}])\end{array}$

$\mathcal{I}$ is an instance for $\mathcal{K}$ w.r.t. the identity relation
over the set
$\mathcal{S}=\\{\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2},\textnormal{{Doe}}_{3},\textnormal{{Yahoo}},\textnormal{{IBM}}\\}$.
Further, let $\textnormal{{e}}_{1}^{\bot}$ and $\textnormal{{e}}_{2}^{\bot}$
be entity-nulls, and $\sim^{\prime}$ be an equivalence relation over
$\mathcal{S}\cup\\{\textnormal{{e}}_{1}^{\bot},\textnormal{{e}}_{2}^{\bot}\\}$,
such that $\textnormal{{Doe}}_{1}\sim^{\prime}\textnormal{{Doe}}_{2}$,
$\textnormal{{IBM}}\sim^{\prime}\textnormal{{e}}_{1}^{\bot}$ and their
symmetric versions are the only equivalences in $\sim^{\prime}$ different from
the identity. The following set $\mathcal{I}^{\prime}$ of facts is an instance
for $\mathcal{K}$ w.r.t. $\sim^{\prime}$.

$\begin{array}[]{l}\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{J.
Doe},\texttt{John Doe}\\},\\{\texttt{358},\texttt{635}\\}),\\\
\mathit{CI}([\textnormal{{Doe}}_{3}],\\{\texttt{Mary
Doe}\\},\\{\texttt{358}\\}),\\\
\mathit{Emp}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],[\textnormal{{Yahoo}}]),~{}~{}\mathit{Emp}([\textnormal{{Doe}}_{3}],[\textnormal{{IBM}},\textnormal{{e}}_{1}^{\bot}])\\\
\mathit{CEO}([\textnormal{{Yahoo}}],[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}]),~{}~{}\mathit{CEO}([\textnormal{{IBM}},\textnormal{{e}}_{1}^{\bot}],[\textnormal{{e}}_{2}^{\bot}])\\\
\mathit{SameHouse}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],[\textnormal{{Doe}}_{3}],\\{\texttt{358}\\}),\\\
\mathit{SameHouse}([\textnormal{{Doe}}_{3}],[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{358}\\}).\hfill\qed\end{array}$

To define the notions of satisfaction of tgds and egds by an instance, we
first introduce the notion of an _assignment_ from a conjunction
$\phi(\mathbf{x})$ of atoms to an instance $\mathcal{I}$ of a KB
$\mathcal{K}$. To formalize this notion, we need a preliminary transformation
of $\phi(\mathbf{x})$ that substitutes each occurrence of a value-variable in
$\phi(\mathbf{x})$ with a fresh variable. We call such fresh variables _set-
variables_ and denote the result of the transformation
$\tau(\phi(\mathbf{x}))$. If $x$ is a value-variable in $\mathbf{x}$, we write
$\mathit{SetVar}(x,\tau(\phi(\mathbf{x})))$ to denote the set of fresh
variables used in $\tau(\phi(\mathbf{x}))$ to replace the occurrences of $x$
in $\phi(\mathbf{x})$. For example, if $\phi(\mathbf{x})=P_{1}(x,y,z)\land
P_{2}(y,z)\land P_{3}(x,w)$, where
$\mathit{type}(P_{1})=\langle\mathsf{e},\mathsf{e},\mathsf{v}\rangle$,
$\mathit{type}(P_{2})=\langle\mathsf{e},\mathsf{v}\rangle$, and
$\mathit{type}(P_{3})=\langle\mathsf{e},\mathsf{v}\rangle$, then
$\tau(\phi(\mathbf{x}))=P_{1}(x,y,S_{1}^{z})\land P_{2}(y,S_{2}^{z})\land
P_{3}(x,S_{1}^{w})$, where $S_{1}^{z}$, $S_{2}^{z}$, $S_{1}^{w}$ are the fresh
set-variables introduced by $\tau$. Also,
$\mathit{SetVar}(z,\tau(\phi(\mathbf{x})))=\\{S_{1}^{z},S_{2}^{z}\\}$ and
$\mathit{SetVar}(w,\tau(\phi(\mathbf{x})))=\\{S_{1}^{w}\\}$. In what follows,
if $x$ is a value-variable, then each set-variable in
$\mathit{SetVar}(x,\tau(\phi(\mathbf{x})))$ will have $x$ as a superscript.

We are now ready to formally define assignments.

######  Definition 3.

Let $\phi(\mathbf{x})$ be a conjunction of atoms and let $\mathcal{I}$ be an
instance for a KB $\mathcal{K}$ w.r.t. $\sim$. An _assignment from
$\phi(\mathbf{x})$ to $\mathcal{I}$_ is a mapping $\mu$ from the variables and
values in $\tau(\phi(\mathbf{x}))$ to $\mathit{active}(\mathcal{I})$, defined
as follows:

  1. 1.

$\mu(x)$ is an equivalence class in $\mathit{active}_{E}(\mathcal{I})$, for
every entity-variable $x$;

  2. 2.

$\mu(v)=V$ such that $V\in\mathit{active}_{V}(\mathcal{I})$ and $v\in V$, for
every value $v$;

  3. 3.

$\mu(S)$ is a set of values in $\mathit{active}_{V}(\mathcal{I})$, for every
set-variable $S$;

  4. 4.

$\bigcap_{i=1}^{k}\mu(S_{i}^{x})\neq\emptyset$, for every value-variable $x$
such that
$\mathit{SetVar}(x,\tau(\phi(\mathbf{x})))=\\{S_{1}^{x},\ldots,S_{k}^{x}\\}$;

  5. 5.

$\mathcal{I}$ contains a fact of the form
$P(\mu(x),\mu(S),[e]_{\sim},\mu(v))$, for each atom $P(x,S,e,v)$ of
$\tau(\phi(\mathbf{x}))$, where $x$ is an entity-variable, $S$ is a set-
variable, $e$ is an entity in $\mathcal{S}_{E}$ and $v$ is a value in
$\mathcal{S}_{V}$ (the definition generalizes in the obvious way for atoms of
different form).

In words, the above definition says that an assignment maps every entity-
variable to an equivalence class of entities (Condition 1), every value to a
set of values containing it (Condition 2), and every occurrence of a value-
variable to a set of values (Condition 3), in such a way that multiple
occurrences of the same value-variable are mapped to sets with a non-empty
intersection (Condition 4). This captures the intuition that, since predicate
arguments ranging over values are interpreted through sets of values, a join
between such arguments holds when such sets have a non-empty intersection.
Finally, Condition 5 states that $\tau(\phi(\mathbf{x}))$ is “realized” in
$\mathcal{I}$. Note that an assignment also maps values to sets of values
(Condition 2). This allows an assignment to map atoms in $\phi(\mathbf{x})$ to
facts in $\mathcal{I}$, since predicate arguments ranging over values are
instantiated in $\mathcal{I}$ by sets of values.

If $P(\mathbf{t})$ is an atom of $\phi(\mathbf{x})$, we write
$\mu(P(\mathbf{t}))$ for the fact of $\mathcal{I}$ in Condition 5 and call it
the _$\mu$ -image (in $\mathcal{I}$) of $P(\mathbf{t})$_. We write
$\mu(\phi(\mathbf{x}))$ for the set
$\\{\mu(P(\mathbf{t}))~{}|~{}P(\mathbf{t})\textrm{ occurs in
}\phi(\mathbf{x})\\}$, and call it the _$\mu$ -image (in $\mathcal{I}$) of
$\phi(\mathbf{x})$_.

######  Example 4.

Consider the tgd $r_{6}$ of Ex. 1 and the instance $\mathcal{I}^{\prime}$
given in Ex. 3 and apply $\tau$ to the body of $r_{6}$ to obtain
$\mathit{CI}(p_{1},S^{\mathit{name}_{1}},S_{1}^{\mathit{phone}})\wedge
CI(p_{2},S^{\mathit{name}_{2}},S_{2}^{\mathit{phone}})$. Let $\mu$ be the
following mapping:

$\begin{array}[]{l}\mu(p_{1})=[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],~{}~{}\mu(S^{\mathit{name}_{1}})=\\{\texttt{J.
Doe},\texttt{John Doe}\\}\\\
\mu(S_{1}^{\mathit{phone}})=\\{\texttt{358},\texttt{635}\\},~{}~{}\mu(p_{2})=[\textnormal{{Doe}}_{3}]\\\
\mu(S^{\mathit{name}_{2}})=\\{\texttt{Mary
Doe}\\},~{}~{}\mu(S_{2}^{\mathit{phone}})=\\{\texttt{358}\\}.\end{array}$

It is easy to see that $\mu$ is an assignment from the body of $r_{6}$ to
$\mathcal{I}^{\prime}$ (note the non-empty intersection between
$\mu(S_{1}^{\mathit{phone}})$ and $\mu(S_{2}^{\mathit{phone}})$). Let us now
apply $\tau$ to the head of $r_{6}$ to obtain
$\mathit{SameHouse}(p_{1},p_{2},R^{\mathit{phone}})$. The following mapping
$\mu^{\prime}$ is an assignment from
$\mathit{SameHouse}(p_{1},p_{2},\mathit{phone})$ to $\mathcal{I}^{\prime}$:

$\begin{array}[]{c}\mu^{\prime}(p_{1})=[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\mu^{\prime}(p_{2})=[\textnormal{{Doe}}_{3}],\mu^{\prime}(R^{\mathit{phone}})=\\{\texttt{358}\\}.\end{array}$

We are now ready to define the semantics of tgds and egds.

######  Definition 4.

An instance $\mathcal{I}$ for a KB $\mathcal{K}$ satisfies:

  * •

a tgd of the form (2), if for each assignment $\mu$ from $\phi(\mathbf{x})$ to
$\mathcal{I}$ there is an assignment $\mu^{\prime}$ from
$\psi(\mathbf{x},\mathbf{y})$ to $\mathcal{I}$ such that, for each $x$ in
$\mathbf{x}$ occurring in both $\phi(\mathbf{x})$ and
$\psi(\mathbf{x},\mathbf{y})$:

    * –

$\mu(x)=\mu^{\prime}(x)$, if $x$ is an entity-variable;

    * –

$\bigcap_{i=1}^{k}\mu(S_{i}^{x})\subseteq\bigcap_{i=1}^{\ell}\mu^{\prime}(R_{i}^{x})$,
where
$\\{S_{1}^{x},\ldots,S_{k}^{x}\\}=\mathit{SetVar}(x,\tau(\phi(\mathbf{x})))$
and
$\\{R_{1}^{x},\ldots,R_{\ell}^{x}\\}=\mathit{SetVar}(x,\tau(\psi(\mathbf{x},\mathbf{y})))$,
if $x$ is a value-variable.

Each such assignment $\mu^{\prime}$ is called a _head-compatible tgd-
extension_ of $\mu$ to $\mathcal{I}$ (or simply a tgd-extension of $\mu$ to
$\mathcal{I}$).

  * •

an entity-egd of the form (3), if each assignment $\mu$ from
$\phi(\mathbf{x})$ to $\mathcal{I}$ is such that $\mu(y)=\mu(z)$;

  * •

a value-egd of the form (3), if each assignment $\mu$ from $\phi(\mathbf{x})$
to $\mathcal{I}$ is such that $\mu(S^{y})=\mu(S^{z})$ for all set-variables
$S^{y},S^{z}\in\mathit{SetVar}(y,\tau(\phi(\mathbf{x})))\cup\mathit{SetVar}(z,\tau(\phi(\mathbf{x})))$.

In words, Def. 4 expresses the following for each assignment $\mu$ from the
body of a rule $r$ to $\mathcal{I}$:

$(1)$ If $r$ is a tgd, the definition stipulates two different behaviours for
frontier variables (i.e., variables occurring in both the body and the head of
the tgd). Specifically, for the tgd to be satisfied, it should be possible to
extend $\mu$ so that (i) every frontier entity-variable is assigned to exactly
the same equivalence class both in the body and the head of the rule (this is
in line with the standard semantics for frontier variables in tgds); and (ii)
the intersection of the sets of values assigned in the body of the tgd to the
various occurrences of a frontier value-variable $x$ is contained in the
intersection of the sets of values assigned to the occurrences of $x$ in the
head of the tgd. Note that, while $\mu$ maps all the occurrences of an entity-
variable in $\phi(\mathbf{x})$ to the same equivalence class, it may map
multiple occurrences of a value-variable to different sets of values with non
empty-intersection; thus, it is natural that this intersection is “propagated”
to the head.

$(2)$ If $r$ is an entity-egd, the notion of satisfaction is standard, since
it requires that $\mu$ assigns $y$ and $z$ to the same equivalence class of
entities.

$(3)$ If $r$ is a value-egd, we have again to take into account that each
occurrence of $y$ in the rule body can be assigned by $\mu$ to a different set
of values (provided that all such sets have a non-empty intersection), and
analogously for each occurrence of $z$. The definition stipulates that, for
the value-egd to be satisfied, all such sets of values are equal.

######  Example 5.

$\mathcal{I}^{\prime}$ from Ex. 3 satisfies tgd $r_{6}$ of Ex. 1, since
$\mu^{\prime}$ is a head-compatible tgd extension of the only assignment $\mu$
from the body of $r_{6}$ to $\mathcal{I}^{\prime}$. Indeed,
$\mu^{\prime}(p_{1})=\mu(p_{1})$, $\mu^{\prime}(p_{2})=\mu(p_{2})$, and
$\mu^{\prime}(S^{\mathit{phone}})=\mu(S_{1}^{\mathit{phone}})\cap\mu(S_{2}^{\mathit{phone}})$
(cf. Ex. 4). It is also easy to see that $\mathcal{I}^{\prime}$ satisfies all
rules of Ex. 1. ∎

Finally, we define when an instance is a solution for a KB.

######  Definition 5.

Let $\mathcal{K}=(\mathcal{T},\mathbf{D})$ be a KB and $\mathcal{I}$ an
instance.

  * •

$\mathcal{I}$ _satisfies_ $\mathcal{T}$ if $\mathcal{I}$ satisfies every tgd
and egd in $\mathcal{T}$.

  * •

$\mathcal{I}$ satisfies a ground atom $P(c_{1},\ldots,c_{n})$ in $\mathbf{D}$
if there is a fact $P(T_{1},\ldots,T_{n})$ in $\mathcal{I}$ such that
$c_{i}\in T_{i}$, for $1\leq i\leq n$.

  * •

$\mathcal{I}$ satisfies $\mathbf{D}$ if $\mathcal{I}$ satisfies all ground
atoms in $\mathbf{D}$.

  * •

$\mathcal{I}$ is a _solution_ for $\mathcal{K}$, denoted by
$\mathcal{I}\models\mathcal{K}$, if $\mathcal{I}$ satisfies $\mathcal{T}$ and
$\mathbf{D}$. The set of all solutions of a KB $\mathcal{K}$ is denoted by
$\mathit{Sol}(\mathcal{K})$, i.e.,
$\mathit{Sol}(\mathcal{K})=\\{\mathcal{I}~{}|~{}\mathcal{I}\models\mathcal{K}\\}$.

######  Example 6.

Consider the instances $\mathcal{I}$ and $\mathcal{I}^{\prime}$ given in Ex. 3
for the $\mathcal{K}$ of Ex. 1 and Ex. 2. It is easy to see that $\mathcal{I}$
is not a solution for $\mathcal{K}$, whereas $\mathcal{I}^{\prime}$ is a
solution for $\mathcal{K}$. ∎

Universal solutions. It is well known that the _universal_ solutions exhibit
good properties that make them to be the preferred solutions (see, e.g., (?;
?; ?)). To introduce the notion of a universal solution in our framework, we
first need to adapt the notion of homomorphism. We begin with some auxiliary
definitions and notation.

######  Definition 6.

Let $\mathbf{T}=\langle T_{1},\ldots,T_{n}\rangle$ and
$\mathbf{T^{\prime}}=\langle T^{\prime}_{1},\ldots,T^{\prime}_{n}\rangle$ be
two tuples such that each $T_{i}$ and each $T^{\prime}_{i}$ is either a set of
entities and entity-nulls or a set of values and value-nulls.

  * •

$\mathbf{T^{\prime}}$ _dominates_ $\mathbf{T}$, denoted
$\mathbf{T}\leq\mathbf{T^{\prime}}$, if $T_{i}\subseteq T^{\prime}_{i}$, for
all $i$.

  * •

$\mathbf{T^{\prime}}$ _strictly dominates_ $\mathbf{T}$, denoted
$\mathbf{T}<\mathbf{T}^{\prime}$, if $\mathbf{T}\leq\mathbf{T^{\prime}}$ and
$\mathbf{T}\neq\mathbf{T^{\prime}}$.

  * •

Let $P(\mathbf{T})$ and $P(\mathbf{T^{\prime}})$ be facts.
$P(\mathbf{T^{\prime}})$ _dominates_ $P(\mathbf{T})$, denoted
$P(\mathbf{T})\leq P(\mathbf{T^{\prime}})$, if
$\mathbf{T}\leq\mathbf{T^{\prime}}$; $P(\mathbf{T^{\prime}})$ _strictly
dominates_ $P(\mathbf{T})$, denoted $P(\mathbf{T})<P(\mathbf{T^{\prime}})$, if
$\mathbf{T}<\mathbf{T^{\prime}}$.

######  Definition 7.

Let $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ be two instances of a KB
$\mathcal{K}$. A homomorphism $h:\mathcal{I}_{1}\rightarrow\mathcal{I}_{2}$ is
a mapping from the elements of $\mathit{under}(\mathcal{I}_{1})$ to elements
of $\mathit{under}(\mathcal{I}_{2})$ such that:

  1. 1.

$h(e)=e$, for every entity $e$ in
$\mathit{under}_{E}(\mathcal{I}_{1})\cap\mathcal{S}_{E}$;

  2. 2.

$h(e_{\bot})$ belongs to $\mathit{under}_{E}(\mathcal{I}_{2})$, for every
entity-null $e_{\bot}$ in
$\mathit{under}_{E}(\mathcal{I}_{1})\cap\mathcal{S}_{EN}$;

  3. 3.

$h(v)=v$, for every value $v$ in
$\mathit{under}_{V}(\mathcal{I}_{1})\cap\mathcal{S}_{V}$;

  4. 4.

$h(v_{\bot})$ belongs to $\mathit{under}_{V}(\mathcal{I}_{2})$, for every
value-null $v_{\bot}$ in
$\mathit{under}_{V}(\mathcal{I}_{1})\cap\mathcal{S}_{VN}$;

  5. 5.

for every $P(T_{1},\ldots,T_{n})$ in $\mathcal{I}_{1}$, there is a
$P(U_{1},\ldots,U_{n})$ in $\mathcal{I}_{2}$ such that
$P(h(T_{1}),\ldots,h(T_{n}))\leq P(U_{1},\ldots,U_{n})$, where
$h(T_{i})=\\{h(x)\mid x\in T_{i})\\}$, for $1\leq i\leq n$.

In the sequel, we may write $h(P(T_{1},\ldots,T_{n}))$ instead of
$P(h(T_{1}),\ldots,h(T_{n}))$, and may use $h(\langle
T_{1},\ldots,T_{n}\rangle)$ to denote the tuple $\langle
h(T_{1}),\ldots,h(T_{n})\rangle$.

We now define the key notion of a universal solution.

######  Definition 8.

A solution $\mathcal{U}$ for a KB $\mathcal{K}$ is _universal_ if, for every
$\mathcal{I}\in\mathit{Sol}(\mathcal{K})$, there is a homomorphism
$h:\mathcal{U}\rightarrow\mathcal{I}$.

The instance $\mathcal{I}^{\prime}$ in Ex. 3 is a universal solution for
$\mathcal{K}$, as is the instance obtained by eliminating
$\textnormal{{e}}_{1}^{\bot}$ from $\mathcal{I}^{\prime}$.

Two instances $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$ are _homomorphically
equivalent_ if there are homomorphisms
$h:\mathcal{I}_{1}\rightarrow\mathcal{I}_{2}$ and
$h^{\prime}:\mathcal{I}_{2}\rightarrow\mathcal{I}_{1}$. All universal
solutions are homomorphically equivalent.

##  4 Query answering

A conjunctive query (CQ) $q$ is a formula
$\exists\mathbf{y}\phi(\mathbf{x},\mathbf{y})$, where
$\phi(\mathbf{x},\mathbf{y})$ is a built-in free conjunction of atoms. The
_arity_ of $q$ is the number of its free variables in $\mathbf{x}$; we will
often write $q(\mathbf{x})$, instead of just $q$, to indicate the free
variables of $q$.

Let $q(\mathbf{x}):\exists\mathbf{x}\phi(\mathbf{x},\mathbf{y})$ be a CQ,
where $\mathbf{x}=x_{1},\ldots,x_{n}$. Given a KB $\mathcal{K}$ and an
instance $\mathcal{I}$ for $\mathcal{K}$, the _answer to $q$ on
$\mathcal{I}$_, denoted by $q^{\mathcal{I}}$, is the set of all tuples
$\langle T_{1},\ldots,T_{n}\rangle$ such that there is an assignment $\mu$
from $\phi(\mathbf{x},\mathbf{y})$ to $\mathcal{I}$ for which

  * •

$T_{i}=\mu(x_{i})$, if $x_{i}$ is an entity-variable;

  * •

$T_{i}=\bigcap_{j=1}^{k}\mu(S_{j}^{x_{i}})$, if $x_{i}$ is a value-variable,
where
$\\{S_{1}^{x_{i}},\ldots,S_{k}^{x_{i}}\\}=\mathit{SetVar}(x_{i},\tau(\phi(\mathbf{x},\mathbf{y})))$.

We will also say that $\mu$ is an assignment from $q(\mathbf{x})$ to
$\mathcal{I}$.

######  Example 7.

Let $q(x)$ be the CQ

$\exists p_{1},p_{2}~{}\mathit{CI}(p_{1},\texttt{J.
Doe},x)\wedge\mathit{CI}(p_{2},\texttt{Mary Doe},x)$

asking for the phone number in common between (the entities named) J. Doe and
Mary Doe. The answer to $q(x)$ on the instance $\mathcal{I}^{\prime}$ in Ex. 3
is $q^{\mathcal{I}^{\prime}}=\\{\langle\\{\texttt{358}\\}\rangle\\}$. This is
obtained through the assignment $\mu_{q}$

$\begin{array}[]{l}\mu_{q}(p_{1})=[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\mu_{q}(\texttt{J.
Doe})=\\{\texttt{J. Doe},\texttt{John Doe}\\}\\\
\mu_{q}(S^{x}_{1})=\\{\texttt{{358},{635}}\\},\mu_{q}(p_{2})=[\textnormal{{Doe}}_{3}]\\\
\mu_{q}(\texttt{Mary Doe})=\\{\texttt{Mary
Doe}\\},\mu_{q}(S_{2}^{x})=\\{\texttt{358}\\}\end{array}$

If $q_{1}(x):\exists z~{}\mathit{CEO}(z,x)$ is the query asking for the CEOs,
then
$q_{1}^{\mathcal{I}^{\prime}}=\\{\langle[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}]\rangle,\langle[\textnormal{{e}}_{2}^{\bot}]\rangle\\}$.
∎

The next result tells how conjunctive queries are preserved under
homomorphisms in our framework.

######  Proposition 1.

Let $q$ be a CQ and let $\mathcal{K}$ a KB. If $\mathcal{I}_{1}$,
$\mathcal{I}_{2}$ are two instances for $\mathcal{K}$ and
$h:\mathcal{I}_{1}\rightarrow\mathcal{I}_{2}$ is a homomorphism from
$\mathcal{I}_{1}$ to $\mathcal{I}_{2}$, then, for every $\mathbf{T}\in
q^{\mathcal{I}_{1}}$, there is $\mathbf{U}\in q^{\mathcal{I}_{2}}$ such that
$h(\mathbf{T})\leq\mathbf{U}$.

###### Proof.

Without loss of generality, let us consider the query $q(x,y)$ defined has
$\exists w\,P_{1}(x,y,e)\land P_{2}(x,y,w,v)$, where $x$ is an entity-
variable, $y$ and $w$ are value-variables, $e$ is an entity from
$\mathcal{S}_{E}$ and $v$ is a value from $\mathcal{S}_{V}$. By applying the
$\tau$ operator to (the conjunction of atoms in) $q(x,y)$ we get
$P_{1}(x,S_{1}^{y},e)\land P_{2}(x,S_{2}^{y},S^{w},v)$. Then, by the
definition of answer to a query over an instance it follows that for every
tuple $\langle E,V\rangle\in q^{\mathcal{I}_{1}}$ there is an assignment $\mu$
from $q(x,y)$ to $\mathcal{I}_{1}$ such that, $\mu(x)=E$,
$\mu(S_{1}^{y})=V_{1}$, $\mu(S_{2}^{y})=V_{2}$, $\mu(S^{w})=V_{3}$,
$\mu(v)=V_{4}$, $V=V_{1}\cap V_{2}=\emptyset$, $v\in V_{4}$, and
$\mathcal{I}_{1}$ contains the facts $P_{1}(E,V_{1},[e]_{\sim^{1}})$ and
$P_{2}(E,V_{2},V_{3},V_{4})$ (where $\sim^{1}$ is the equivalence relation
associated to $\mathcal{I}_{1}$). Since $h$ is homomorphism from
$\mathcal{I}_{1}$ to $\mathcal{I}_{2}$, the instance $\mathcal{I}_{2}$ has to
contain the facts $P_{1}(\hat{E},\hat{V}_{1},\hat{E}_{1})$ and
$P_{2}(\hat{E},\hat{V}_{2},\hat{V}_{3},\hat{V}_{4})$, such that
$P_{1}(h(E),h(V_{1}),h([e]_{\sim^{1}}))\leq
P_{1}(\hat{E},\hat{V}_{1},\hat{E}_{1})$ and
$P_{2}(h(E),h(V_{2}),h(V_{3}),h(V_{4}))\leq
P_{2}(\hat{E},\hat{V}_{2},\hat{V}_{3},\hat{V}_{4})$ We then construct a
mapping $\mu^{\prime}$ from the variables and values in
$P_{1}(x,S_{1}^{y},e)\land P_{2}(x,S_{2}^{y},S^{w},v)$ to
$\mathit{active}_{E}(\mathcal{I}_{2})$ as follows: $\mu^{\prime}(x)=\hat{E}$,
$\mu^{\prime}(S_{1}^{y})=\hat{V}_{1}$, $\mu^{\prime}(S_{2}^{y})=\hat{V}_{2}$,
$\mu^{\prime}(S^{w})=\hat{V}_{3}$, and $\mu^{\prime}(v)=\hat{V}_{4}$. It is
not difficult to see that $\mu^{\prime}$ is an assignment from $q(x,y)$ to
$\mathcal{I}_{2}$. In particular:

  * •

since $e\in[e]_{\sim^{1}}$ and $h(e)=e$, then $e\in h([e]_{\sim^{1}})$, and
since $h([e]_{\sim^{1}})\subseteq\hat{E}_{1}$, it follows that
$e\in\hat{E}_{1}$, which implies that $\hat{E}_{1}=[e]_{\sim^{2}}$ (where
$\sim^{2}$ is the equivalence relation associated to $\mathcal{I}_{2}$);

  * •

since $V_{1}\cap V_{2}\neq\emptyset$ and since $h(V_{1}\cap V_{2})\subseteq
h(V_{1})\cap h(V_{2})\subseteq\hat{V}_{1}\cap\hat{V}_{2}$, it follows that
that $\hat{V}_{1}\cap\hat{V}_{2}\neq\emptyset$;

  * •

since $v\in V_{4}$ and $h(v)=v$, then $v\in h(V_{4})$, and since
$h(V_{4})\subseteq\hat{V}_{4}$, it follows that $v\in\hat{V}_{4}$.

The above assignment $\mu^{\prime}$ testifies that
$\langle\hat{E},\hat{V}\rangle\in q^{\mathcal{I}_{2}}$, where
$\hat{V}=\hat{V}_{1}\cap\hat{V}_{2}$. This proves the thesis, since, as said,
$h(E)\subseteq\hat{E}$ and $h(V)\subseteq\hat{V}$. ∎

When querying a KB $\mathcal{K}$, we are interested in reasoning over all
solutions for $\mathcal{K}$. We adapt the classical notion of certain answers
to our framework. A tuple $\mathbf{T}=\langle T_{1},\ldots,T_{n}\rangle$ is
_null-free_ if each $T_{i}$ is non-empty and contains no nulls.

######  Definition 9.

Let $q$ be a CQ and let $\mathcal{K}$ be a KB. A null-free tuple $\mathbf{T}$
is a _certain answer_ to $q$ w.r.t. $\mathcal{K}$ if

  1. 1.

for every solution $\mathcal{I}$ for $\mathcal{K}$, there is a tuple
$\mathbf{T^{\prime}}\in q^{\mathcal{I}}$ such that
$\mathbf{T}\leq\mathbf{T^{\prime}}$;

  2. 2.

there is no null-free tuple $\mathbf{T^{\prime}}$ that satisfies $1.$ and
$\mathbf{T}<\mathbf{T^{\prime}}$.

We write $\mathit{cert}(q,\mathcal{K})$ for the set of certain answers to $q$.

Note that the second condition in the above definition asserts that a certain
answer has to be a maximal null-free tuple with respect to the tuple dominance
order $\leq$ given in Def. 6, among the tuples satisfying Condition $1.$ The
following example clarifies the importance of this condition.

######  Example 8.

In every solution for the KB $\mathcal{K}$ used in our ongoing example,
$\textnormal{{Doe}}_{1}$ and $\textnormal{{Doe}}_{2}$ are in the same
equivalence class denoting a CEO. Then, the null-free tuple
$\langle\\{\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}\\}\rangle$ is a
certain answer to the query $q_{1}(x):\exists z\mathit{CEO}(z,x)$. Observe
that the null-free tuple $\langle\\{\textnormal{{Doe}}_{1}\\}\rangle$
satisfies the first (but not the second) condition in Def. 9. However, we do
not want this tuple to be a certain answer since it is not an equivalence
class in any solution. ∎

The next results tell that if two sets of entities appear in a certain answer
or in different certain answers, then either they are the same set or they are
disjoint. In particular, the sets of entities that appear in certain answers
can be viewed as equivalence classes of some equivalence relation.

######  Proposition 2.

Let $q$ be a CQ of arity $n$, let $\mathcal{K}$ be a KB, and let
$\mathbf{T}=\langle T_{1},\dots,T_{n}\rangle$ and $\mathbf{T^{\prime}}=\langle
T^{\prime}_{1},\dots,T^{\prime}_{n}\rangle$ be two certain answers to $q$
w.r.t. $\mathcal{K}$. If $T_{i}$ and $T^{\prime}_{j}$ are sets of entities,
then either $T_{i}=T^{\prime}_{j}$ or $T_{i}\cap T^{\prime}_{j}=\emptyset$,
where $1\leq i,j\leq n$.

###### Proof.

Towards a contradiction, assume that $T_{i}$, $T^{\prime}_{j}$ are two non-
empty sets of entities such that $T_{i}\neq T^{\prime}_{j}$ and $T_{i}\cap
T^{\prime}_{j}\neq\emptyset$. Then $T_{i}\subsetneqq T_{i}\cup T^{\prime}_{j}$
or $T^{\prime}_{j}\subsetneqq T_{i}\cup T^{\prime}_{j}$. Let’s assume
$T_{i}\subsetneqq T_{i}\cup T^{\prime}_{j}$. Since $\langle
T_{1},\dots,T_{n}\rangle$ and $\langle
T^{\prime}_{1},\dots,T^{\prime}_{n}\rangle$ are certain answers of $q$, for
every solution $\mathcal{I}$, there are tuples $\langle
L_{1},\dots,L_{n}\rangle$, $\langle
L^{\prime}_{1},\dots,L^{\prime}_{n}\rangle$ in $q^{\mathcal{I}}$ such that for
every $k$ we have $T_{k}\subseteq L_{k}$ and $T^{\prime}_{k}\subseteq
L^{\prime}_{k}$. Thus we have that $T_{i}\subseteq L_{i}$ and
$T^{\prime}_{j}\subseteq L^{\prime}_{j}$. Since $T_{i}\cap
T^{\prime}_{j}\neq\emptyset$, it follows that $L_{i}\cap
L^{\prime}_{j}\neq\emptyset$. However, $L_{i}$, $L^{\prime}_{j}$ are
equivalence classes in the solution $\mathcal{I}$, hence they must coincide,
i.e. $L_{i}=L^{\prime}_{j}$. It follows that $T_{i}\cup
T^{\prime}_{j}\subseteq L_{i}=L^{\prime}_{j}$. Consider now the tuple $\langle
T_{1},\dots,T_{i-1},T_{i}\cup T_{j},T_{i+1},\dots,T_{n}\rangle$, which is
obtained from $\langle T_{1},\dots,T_{n}\rangle$ by replacing $T_{i}$ by
$T_{i}\cup T_{j}$. Note that $\langle
T_{1},\dots,T_{i-1},T_{i},T_{i+1},\dots,T_{n}\rangle<\langle
T_{1},\dots,T_{i-1},T_{i}\cup T_{j},T_{i+1},\dots,T_{n}\rangle$ because
$T_{i}\subsetneqq T_{i}\cup T^{\prime}_{j}$. However for every solution
$\mathcal{I}$ of $\mathcal{K}$, we have that $T_{i}\cup
T^{\prime}_{j}\subseteq L_{i}$, and for all $1\leq k\leq n$ such that $k\neq
i$, we have that $T_{k}\subseteq L_{k}$. This means that $\langle
T_{1},\dots,T_{i-1},T_{i}\cup T_{j},T_{i+1},\dots,T_{n}\rangle$ satisfies
Condition $(i)$ of Definition 9, and therefore $\langle
T_{1},\dots,T_{n}\rangle$ does not respect Condition $(ii)$ of Definition 9),
and thus it is not a certain answer, which is a contradiction. Note finally
that if we assume $T^{\prime}_{j}\subsetneqq T_{i}\cup T^{\prime}_{j}$ we
contradict that $\langle T^{\prime}_{1},\dots,T^{\prime}_{n}\rangle$ is a
certain answer by using an analogous argument. ∎

The following property easily follows from the above proposition.

######  Corollary 1.

Let $\mathcal{K}$ be a KB, $q$ be a CQ, and $\langle T_{1},\dots,T_{n}\rangle$
be a certain answer to $q$ with respect to $\mathcal{K}$. If $T_{i}$ and
$T_{j}$ are sets of entities such that $i\neq j$, then either $T_{i}=T_{j}$ or
$T_{i}\cap T_{j}=\emptyset$.

###### Proof.

It follows from Proposition 2 when $\mathbf{T}=\mathbf{T^{\prime}}$. ∎

In data exchange and related areas, the certain answers to CQs can be obtained
by evaluating the query on a universal solution and then applying an operator
$\downarrow$ that eliminates the tuples that contain nulls (see, e.g., (?;
?)). The operator $\downarrow$ can easily be adapted to our framework as
follows. If $E$ is a set of entities and entity-nulls, then
$E{\downarrow}=\\{e~{}|~{}e\in\mathcal{S}_{E}\cap E\\}$. Similarly, if $V$ is
a non-empty set of values and value-nulls, then
$V{\downarrow}=\\{v~{}|~{}v\in\mathcal{S}_{V}\cap V\\}$. In words,
$\downarrow$ removes all nulls from $E$ and from $V$. If $\langle
T_{1},\dots,T_{n}\rangle$ is a tuple such that each $T_{i}$ is either a set of
entities and entity-nulls or a set of values and value-nulls, then we set
$\langle T_{1},\dots,T_{n}\rangle{\downarrow}=\langle
T_{1}{\downarrow},\dots,T_{n}{\downarrow}\rangle$. Finally, given a set
$\Theta$ of tuples of the above form, $\Theta{\downarrow}$ is the set obtained
from $\Theta$ by removing all tuples in $\Theta$ containing a $T_{i}$ such
that $T_{i}{\downarrow}=\emptyset$, and replacing every other tuple $\langle
T_{1},\dots,T_{n}\rangle$ in $\Theta$ by the tuple $\langle
T_{1},\dots,T_{n}\rangle{\downarrow}$.

The next example shows that, in our framework, the certain answers to a CQ $q$
cannot always be obtained by evaluating $q$ on a universal solution and then
applying $\downarrow$.

######  Example 9.

Let $P_{1}$ and $P_{2}$ be such that
$\mathit{type}(P_{1})=\mathit{type}(P_{2})=\langle\mathsf{e},\mathsf{v}\rangle$,
$\mathcal{T}^{\prime}$ be the TBox consisting of the rules

$\begin{array}[]{l}P_{1}(x,y)\rightarrow P_{2}(x,y),~{}~{}P_{1}(x,y)\land
P_{1}(x,z)\rightarrow y=z\end{array}$

and
$\mathbf{D}^{\prime}=\\{P_{1}(\textnormal{{e}},1),P_{1}(\textnormal{{e}},2)\\}$.
Consider the following universal solutions for
$\mathcal{K}^{\prime}=(\mathcal{T}^{\prime},\mathbf{D}^{\prime})$

$\begin{array}[]{lcl}\mathcal{I}_{1}&=&\\{P_{1}([\textnormal{{e}}],\\{1,2\\}),P_{2}([\textnormal{{e}}],\\{1,2\\})\\}\\\
\mathcal{I}_{2}&=&\\{P_{1}([\textnormal{{e}}],\\{1,2\\}),P_{2}([\textnormal{{e}}],\\{1\\}),P_{2}([\textnormal{{e}}],\\{1,2\\})\\}\end{array}$

and the query $q(x,y):P_{2}(x,y)$. Then
$q^{\mathcal{I}_{1}}{\downarrow}=q^{\mathcal{I}_{1}}=\\{\langle[\textnormal{{e}}],\\{1,2\\}\rangle\\}$,
and
$q^{\mathcal{I}_{2}}{\downarrow}=q^{\mathcal{I}_{2}}=\\{\langle[\textnormal{{e}}],\\{1,2\\}\rangle,\langle[\textnormal{{e}}],\\{1\\}\rangle\\}$.
Thus, $q^{\mathcal{I}_{2}}{\downarrow}$ does not coincide with the set of
certain answers to $q$ w.r.t. $\mathcal{K}^{\prime}$, because the tuple
$\langle[\textnormal{{e}}],\\{1\\}\rangle$ does not satisfy the second
condition in Def. 9. ∎

Intuitively, in the above example the universal solution $\mathcal{I}_{2}$ is
not “minimal”, in the sense that the fact $P_{2}([\textnormal{{e}}],\\{1\\})$
in $\mathcal{I}_{2}$ is dominated by another fact of $\mathcal{I}_{2}$, namely
$P_{2}([\textnormal{{e}}],\\{1,2\\})$. This behaviour causes that the answer
to the query over $\mathcal{I}_{2}$ contains also tuples that are not maximal
with respect to tuple dominance (cf. Def. 9). Note also that the situation is
even more complicated in the presence of nulls. For example, we might have an
instance containing both facts $Q([\textnormal{{e}}],\\{1,2,n\\})$ and
$Q([\textnormal{{e}}],\\{1,n^{\prime}\\})$, where $n$ and $n^{\prime}$ are two
different value-nulls. In this case, no fact in the solution is dominated by
another fact, still “non-minimality” shows up if we eliminate the nulls.his
suggests that we need some additional processing besides elimination of nulls.
We modify the operator $\downarrow$ by performing a further _reduction_ step.

######  Definition 10.

Given a query $q$ and an instance $\mathcal{I}$ for a KB $\mathcal{K}$, we
write $q^{\mathcal{I}}{\downarrow^{\rho}}$ to denote the set of null-free
tuples obtained by removing from $q^{\mathcal{I}}{\downarrow}$ all tuples
strictly dominated by other tuples in the set, that is, if $\mathbf{T}$ and
$\mathbf{T^{\prime}}$ are two tuples in $q^{\mathcal{I}}{\downarrow}$ such
that $\mathbf{T}<\mathbf{T^{\prime}}$, then remove $\mathbf{T}$ from
$q^{\mathcal{I}}{\downarrow}$.

The following property is needed to prove the last theorem of this section. It
easily follows from Prop. 1 and Def. 7.

######  Corollary 2.

Let $\mathcal{K}$ be a KB, $q$ be a CQ, $\mathcal{U}$ be a universal solution
for $\mathcal{K}$, and $\mathbf{T}\in q^{\mathcal{U}}$. Then, for every
$\mathcal{I}\in\mathit{Sol}(\mathcal{K})$ there is a tuple
$\mathbf{T^{\prime}}\in q^{\mathcal{I}}$ such that
$\mathbf{T}\downarrow\leq\mathbf{T^{\prime}}$.

###### Proof.

Obviously, $\mathbf{T^{\prime}}\downarrow\leq\mathbf{T^{\prime}}$. Since
$\mathcal{U}$ is universal, there is a homomorphism $h$ from $\mathcal{U}$ to
$\mathcal{I}$. From Proposition 1 it follows that there is
$\mathbf{T^{\prime}}\in q^{\mathcal{I}}$ such that
$h(\mathbf{T})\leq\mathbf{T^{\prime}}$. From Definition 7 (homomorphism) it
follows that $\mathbf{T}\downarrow\leq h(\mathbf{T})$, and thus
$\mathbf{T}\downarrow\leq\mathbf{T^{\prime}}$. ∎

We are now able to present the main result of this section, which asserts that
universal solutions can be used to compute the certain answers to CQs in our
framework.

######  Theorem 1.

Let $q$ be a CQ, let $\mathcal{K}$ be a KB, and let $\mathcal{U}$ be a
universal solution for $\mathcal{K}$. Then
$\mathit{cert}(q,\mathcal{K})=q^{\mathcal{U}}{{\downarrow^{\rho}}}$.

###### Proof.

We first show that
$q^{\mathcal{U}}{\downarrow^{\rho}}\subseteq\mathit{cert}(q,\mathcal{K})$. Let
$\mathbf{T}\in{q^{\mathcal{U}}{\downarrow^{\rho}}}$, which of course implies
$\mathbf{T}\in q^{\mathcal{U}}$. By Corollary 2 we have that for every
$\mathcal{I}\in\mathit{Sol}(\mathcal{K})$ there is a tuple
$\mathbf{T^{\prime}}\in q^{\mathcal{I}}$ such that
$\mathbf{T}{\downarrow}\leq\mathbf{T^{\prime}}$. Since
$\mathbf{T}\in{q^{\mathcal{U}}{\downarrow^{\rho}}}$, it is null-free and thus
$\mathbf{T}{\downarrow}=\mathbf{T}$. Hence, Condition $(i)$ of Definition 9
(certain answers) is satisfied by $\mathbf{T}$. Let us now assume by
contradiction that $\mathbf{T}$ does not satisfy Condition $(ii)$ of
Definition 9. This means that there exists a null-free tuple
$\mathbf{T^{\prime}}$ satisfying Condition $(i)$ of Definition 9 such that
$\mathbf{T}<\mathbf{T^{\prime}}$. Since $\mathbf{T^{\prime}}$ satisfies
Condition $(i)$ of Definition 9, there must exist a tuple $\mathbf{U}\in
q^{\mathcal{U}}$ such that $\mathbf{T^{\prime}}\leq\mathbf{U}$, and thus
obviously $\mathbf{T}<\mathbf{U}$. We can apply the $\downarrow$ operator to
both $\mathbf{T}$ and $\mathbf{U}$ and get
$\mathbf{T}{\downarrow}<\mathbf{U}{\downarrow}$, and since, as said,
$\mathbf{T}=\mathbf{T}{\downarrow}$, we have that
$\mathbf{T}<\mathbf{U}{\downarrow}$, which is a contradiction. Indeed,
$\mathbf{T}\in q^{\mathcal{U}}{\downarrow^{\rho}}$ (by hypothesis) and
$\mathbf{U}\downarrow\in q^{\mathcal{U}}{\downarrow}$, and thus it is not
possible that $\mathbf{U}$ dominates $\mathbf{T}$ (cf. Step 3 of the
definition of the $\downarrow^{\rho}$ operator).

We now show that $\mathit{cert}(q,\mathcal{K})\subseteq
q^{\mathcal{U}}{\downarrow^{\rho}}$. Let
$\mathbf{T}\in\mathit{cert}(q,\mathcal{K})$. By Condition $(i)$ of Definition
9 there exists a tuple $\mathbf{U}\in q^{\mathcal{U}}$ such that
$\mathbf{T}\leq\mathbf{U}$, which implies
$\mathbf{T}\leq\mathbf{U}{\downarrow}$ (since $\mathbf{T}$ is null-free). By
Corollary 2, we have that for each $\mathcal{I}\in\mathit{Sol}(\mathcal{K})$
there is a tuple $\mathbf{T^{\prime}}\in q^{\mathcal{I}}$ such that
$\mathbf{U}{\downarrow}\leq\mathbf{T^{\prime}}$. This last fact implies that
$\mathbf{U}{\downarrow}$ is a null-free tuple satisfying Condition $(i)$ of
Definition 9. Thus, if $\mathbf{T}<\mathbf{U}{\downarrow}$ then $\mathbf{T}$
is not a certain answer, which contradicts the assumption. Therefore, it must
be $\mathbf{T}=\mathbf{U}{\downarrow}$. This shows that $\mathbf{T}\in
q^{\mathcal{U}}{\downarrow}$. Let us assume by contradiction that
$\mathbf{T}\not\in q^{\mathcal{U}}{\downarrow^{\rho}}$. By definition of the
$\downarrow^{\rho}$ operator, the above assumption implies that there exists a
tuple $\mathbf{X}\in q^{\mathcal{U}}{\downarrow^{\rho}}$ such that
$\mathbf{T}<\mathbf{X}$, and since
$q^{\mathcal{U}}{\downarrow^{\rho}}\subseteq\mathit{cert}(q,\mathcal{K})$, as
shown in the first part of this proof, $\mathbf{X}$ satisfies Condition $(i)$
of Definition 9, which in turn implies that
$\mathbf{T}\not\in\mathit{cert}(q,\mathcal{K})$, which is a contradiction. ∎

######  Example 10.

As seen earlier in Ex.6, $\mathcal{I}^{\prime}$ is a universal solution for
$\mathcal{K}$. Then, for the query $q_{1}(x):\exists zCEO(z,x)$, we have that
$\mathit{cert}(q_{1},\mathcal{K})=q_{1}^{\mathcal{I}^{\prime}}{\downarrow^{\rho}}=\\{\langle[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}]\rangle\\}$.
∎

##  5 Computing a universal model

In this section, we adapt the well-known notion of restricted chase (?; ?; ?;
?) to our framework. Interestingly, the chase procedure we define never
produces a failure, unlike, e.g., the restricted chase procedure in the case
of standard data exchange, where the application of egds may cause a failure
when two different constants have to be made equal. Instead, in our framework,
when an entity-egd forces two different equivalence classes of entities to be
equated, we combine the two equivalence classes into a bigger equivalence
class. Similarly, when a value-egd forces two different sets of values to be
equated, we take the union of the two sets and modify the instance
accordingly. However, it is possible that the chase procedure may have
infinitely many steps, each producing a new instance. As a consequence, some
care is required in defining the result of the application of this
(potentially infinite) procedure to a KB $\mathcal{K}$, so that we can obtain
an instance that can be used (at least in principle) for query answering. We
call such instance _the result of the chase of the KB $\mathcal{K}$_, and
distinguish the case in which the chase terminates from the case in which it
does not. In the former case, the result of the chase of $\mathcal{K}$ is
simply the instance produced in the last step of the chase procedure, and we
show that this instance is a universal solution for $\mathcal{K}$. In the
latter case, we point out that previous approaches from the literature for
infinite standard chase sequences under tgds and egds cannot be smoothly
adapted to our framework, and we leave it open for this case how to define the
result of the chase so that it is a universal solution.

We start with the notion of the _base instance_ for a KB. Given a KB
$\mathcal{K}=(\mathcal{T},\mathbf{D})$, we define the set

$\mathcal{I}^{\mathbf{D}}=\\{P(\\{c_{1}\\},\ldots,\\{c_{n}\\})~{}|~{}P(c_{1},\ldots,c_{n})\in\mathbf{D}\\}.$

$\mathcal{I}^{\mathbf{D}}$ is an instance for $\mathcal{K}$ w.r.t. the
identity relation $\mathsf{id}$ over the set
$\mathcal{S}=\mathcal{S}_{E}\cap\mathit{sig}(\mathcal{K})$. We call
$\mathcal{I}^{\mathbf{D}}$ the _base instance_ for $\mathcal{K}$. Note that
the base instance for $\mathcal{K}$ is also a base instance for every KB
having $\mathbf{D}$ as database, and is a solution for
$(\emptyset,\mathbf{D})$. As an example, note that the instance $\mathcal{I}$
of Ex. 3 is the base instance for the KB $\mathcal{K}$ defined in Ex. 1 and in
Ex. 2.

We next define three chase steps, one for tgds, one for entity-egds, and one
for value-egds.

######  Definition 11.

Let $\mathcal{K}=(\mathcal{T},\mathbf{D})$ be a KB and $\mathcal{I}_{1}$ an
instance for $\mathcal{K}$ w.r.t. an equivalence relation $\sim^{1}$ on
$\mathit{under}_{E}(\mathcal{I}_{1})$.

  * •

(tgd) Let $r$ be a tgd of the form (2). Without loss of generality, we assume
that all atoms in $\psi(\mathbf{x},\mathbf{y})$ are of the form
$P(x_{1},\ldots,x_{k},y_{1},\ldots,y_{\ell})$, where $x_{1},\ldots,x_{k}$
belong to $\mathbf{x}$ and $y_{1},\ldots,y_{\ell}$ belong to $\mathbf{y}$, and
we denote with $\mathbf{y_{e}}=y_{e}^{1},\ldots y_{e}^{h}$ and
$\mathbf{y_{v}}=y_{v}^{1},\ldots,y_{v}^{j}$ the entity-variables and value-
variables in $\mathbf{y}$, respectively. Let $\mu$ be an assignment from
$\phi(\mathbf{x})$ to $\mathcal{I}_{1}$ such that there is no
$\psi(\mathbf{x},\mathbf{y})$-compatible tgd-extension of $\mu$ to
$\mathcal{I}_{1}$. We say that $r$ is _applicable_ to $\mathcal{I}_{1}$ with
$\mu$ (or that $\mu$ _triggers_ $r$ in $\mathcal{I}_{1}$), and construct
$\mathcal{I}_{2}$ via the following procedure:
let $\\{f_{e}^{1},\ldots,f_{e}^{h}\\}\subseteq\mathcal{S}_{EN}$ and
$\\{f_{v}^{1},\ldots,f_{v}^{j}\\}\subseteq\mathcal{S}_{VN}$ be
two sets of fresh nulls (i.e., not occurring in $\mathcal{I}_{1}$),
which are distinct from each other
put $\mathcal{I}_{2}:=\mathcal{I}_{1}$
for each atom $P(x_{1},\ldots,x_{k},y_{1},\ldots,y_{\ell})$ in
$\psi(\mathbf{x},\mathbf{y})$ do
$\mathcal{I}_{2}:=\mathcal{I}_{2}\cup\\{P(T_{1},\ldots,T_{k},U_{1},\ldots,U_{\ell})\\}$
where,

    * –

for $1\leq i\leq k$, we have $T_{i}=\mu(x_{i})$, if $x_{i}$ is an entity-
variable, or $T_{i}=\bigcap_{p=1}^{m}\mu(S_{p}^{x_{i}})$, if $x_{i}$ is value-
variable and
$\\{S_{1}^{x_{i}},\ldots,S_{m}^{x_{i}}\\}=\mathit{SetVar}(x_{i},\tau(\phi(\mathbf{x})))$;

    * –

for $1\leq i\leq\ell$, we have $U_{i}=\\{f_{e}^{s}\\}$ if $y_{i}=y_{e}^{s}$,
with $1\leq s\leq h$, or $U_{i}=\\{f_{v}^{q}\\}$ if $y_{i}=y_{v}^{q}$, with
$1\leq q\leq j$. (Thus, each singleton $\\{f_{e}^{s}\\}$ is a new equivalence
class.)

  * •

(entity-egd) Let $r$ be an entity-egd of the form (3), and $\mu$ an assignment
from $\phi(\mathbf{x})$ to $\mathcal{I}_{1}$ such that $\mu(y)\neq\mu(z)$. We
say that $r$ is _applicable_ to $\mathcal{I}_{1}$ with $\mu$ (or that $\mu$
_triggers_ $r$ in $\mathcal{I}_{1}$), and we construct $\mathcal{I}_{2}$ from
$\mathcal{I}_{1}$ by replacing in $\mathcal{I}_{1}$ all occurrences of
$\mu(y)$ and $\mu(z)$ with $\mu(y)\cup\mu(z)$.
(Thus, we merge two equivalence classes into a new one.)

  * •

(value-egd) let $r$ be a value-egd of the form (3). Let
$\\{S_{1}^{y},\ldots,S_{m}^{y}\\}=\mathit{SetVar}(y,\tau(\phi(\mathbf{x})))$,
$\\{S_{1}^{z},\ldots,S_{k}^{z}\\}=\mathit{SetVar}(z,\tau(\phi(\mathbf{x})))$,
$1\leq i\leq m$, $1\leq j\leq k$, and $\mu$ be an assignment from
$\phi(\mathbf{x})$ to $\mathcal{I}_{1}$ such that
$\mu(S^{y}_{i})\neq\mu(S^{z}_{j})$. We say that $r$ is _applicable_ to
$\mathcal{I}_{1}$ with $\mu$ (or that $\mu$ _triggers_ $r$ in
$\mathcal{I}_{1}$), and we construct $\mathcal{I}_{2}$ from $\mathcal{I}_{1}$
by replacing in the image $\mu(\phi(\mathbf{x}))$ each set
$\mu(S_{1}^{y}),\ldots,\mu(S_{m}^{y}),\mu(S_{1}^{z}),\ldots$ and
$\mu(S_{k}^{z})$ with
$\mu(S_{1}^{y})\cup\ldots\cup\mu(S_{m}^{y})\cup\mu(S_{1}^{z})\cup\ldots\cup\mu(S_{k}^{z})$.

If $r$ is a tgd or egd that can be applied to $\mathcal{I}_{1}$ with $\mu$, we
say that $\mathcal{I}_{2}$ is the _result of applying_ $r$ to
$\mathcal{I}_{1}$ with $\mu$ and we write
$\mathcal{I}_{1}\xrightarrow[]{r,\mu}\mathcal{I}_{2}$. We call
$\mathcal{I}_{1}\xrightarrow[]{r,\mu}\mathcal{I}_{2}$ a _chase step_.

For both the entity-egd step and the value-egd step, the chase procedure
constructs $\mathcal{I}_{2}$ by replacing some facts of $\mathcal{I}_{1}$.
However, whereas for entity-egds the replacement is “global” (i.e., the two
equivalence classes merged in the step are substituted by their union
everywhere in $\mathcal{I}_{1}$), for value-egds the replacement is “local”,
in the sense that the two sets merged in the step are substituted by their
union _only_ in facts occurring in the image $\mu(\phi(\mathbf{x}))$, which is
a subset of $\mathcal{I}_{1}$.

######  Example 11.

Consider again the KB $\mathcal{K}=(\mathcal{T},\mathbf{D})$ of Ex. 1 and Ex.
2. The interpretation $\mathcal{I}$ of Ex. 3 is the base instance
$\mathcal{I}^{\mathbf{D}}$ for $\mathcal{K}$. We depict below the application
of the rules of Def. 11, starting from the instance
$\mathcal{I}=\mathcal{I}^{\mathbf{D}}$.

tgd application:
$\mathcal{I}^{\mathbf{D}}\xrightarrow[]{r_{4},\mu_{0}}\mathcal{I}_{1}$, where
$\mu_{0}$ is such that $\mu_{0}(\mathsf{body}(r_{4}))=\\{d_{3}\\}$. The
resulting instance $\mathcal{I}_{1}$ contains the facts $d_{1}$-$d_{6}$ (see.
Ex. 3), as well as the facts:

$\displaystyle\begin{array}[]{ll}(d_{7})\mathit{Emp}([\textnormal{{Doe}}_{3}],[\textnormal{{e}}_{1}^{\bot}]),&(d_{8})\mathit{CEO}([\textnormal{{e}}_{1}^{\bot}],[\textnormal{{e}}_{2}^{\bot}]).\end{array}$

entity-egd application:
$\mathcal{I}_{1}\xrightarrow[]{r_{1},\mu_{1}}\mathcal{I}_{2}$, where the
assignment $\mu_{1}$ is such that
$\mu_{1}(\mathsf{body}(r_{1}))=\\{d_{1},d_{2},\mathit{JaccSim}(\\{\texttt{J.
Doe}\\},\\{\texttt{John Doe}\\},\\{0.6\\})\\}$. The resulting instance
$\mathcal{I}_{2}$ contains the facts $d_{3}$, $d_{5}$, $d_{7}$, $d_{8}$, as
well as the facts:

$\displaystyle\begin{array}[]{ll}(d_{1})\rightarrow(d_{9})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{J.
Doe}\\},\\{\texttt{358}\\})\\\
(d_{2})\rightarrow(d_{10})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{John
Doe}\\},\\{\texttt{635}\\})\\\
(d_{4})\rightarrow(d_{11})&\mathit{Emp}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],[\textnormal{{Yahoo}}])\\\
(d_{6})\rightarrow(d_{12})&\mathit{CEO}([\textnormal{{Yahoo}}],[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}]).\\\
\end{array}$

value-egd application:
$\mathcal{I}_{2}\xrightarrow[]{r_{2},\mu_{2}}\mathcal{I}_{3}$, where $\mu_{2}$
is such that $\mu_{2}(\mathsf{body}(r_{2}))=\\{d_{9},d_{10}\\}$. The resulting
instance $\mathcal{I}_{3}$ contains the facts $d_{3}$, $d_{11}$, $d_{5}$,
$d_{12}$, $d_{7}$, $d_{8}$, as well as the facts:

$\displaystyle\begin{array}[]{ll}(d_{9})\rightarrow(d_{13})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{J.
Doe,John Doe}\\},\\{\texttt{358}\\})\\\
(d_{10})\rightarrow(d_{14})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{J.
Doe,John Doe}\\},\\{\texttt{635}\\}).\\\ \end{array}$

We now define the notion of a chase sequence.

######  Definition 12.

Let $\mathcal{K}=(\mathcal{T},\mathbf{D})$ be a KB. A _chase sequence for
$\mathcal{K}$_ is a (finite or infinite) sequence
$\sigma=\mathcal{I}_{0},\mathcal{I}_{1},\mathcal{I}_{2}\dots$, such that
$\mathcal{I}_{0}=\mathcal{I}^{\mathbf{D}}$ and
$\mathcal{I}_{i}\xrightarrow[]{r_{i},\mu_{i}}\mathcal{I}_{i+1}$ is a chase
step, for each consecutive pair ($\mathcal{I}_{i},\mathcal{I}_{i+1}$) in the
sequence $\sigma$.

In the Appendix, we provide an entire chase sequence for the KB $\mathcal{K}$
of our running example; the first three instances of this sequence have been
described in Ex. 11.

We now present some basic properties of the instances in a chase sequence.

######  Proposition 3.

Let $\mathcal{K}$ be a KB.

  * •

If $\mathcal{I}$ is an instance for $\mathcal{K}$ w.r.t. an equivalence
relation $\sim$ on $\mathit{under}_{E}(\mathcal{I})$ and if
$\mathcal{I}^{\prime}$ is such that
$\mathcal{I}\xrightarrow[]{r,\mu}\mathcal{I}^{\prime}$, then there is an
equivalence relation $\sim^{\prime}$ such that $\mathcal{I}^{\prime}$ is an
instance for $\mathcal{K}$ w.r.t. $\sim^{\prime}$ on
$\mathit{under}_{E}(\mathcal{I}^{\prime})$.

  * •

Every $\mathcal{I}_{i}$ occurring in a chase sequence for a KB
$\mathcal{K}=(\mathcal{T},\mathbf{D})$ is an instance for $\mathcal{K}$.

###### Proof.

We prove the thesis at the first bullet by considering the three possible
cases for the rule $r$ and the corresponding chase steps of Definition 11.

_Case of tgd chase step:_ Let $r$ be a tgd of the form (2). Let
$\mathcal{S}=\mathit{under}_{E}(\mathcal{I})\cup\textsf{N}^{f_{e}}$, where
$\textsf{N}^{f_{e}}=\\{f_{e}^{1},\ldots,f_{e}^{h}\\}$, i.e.,
$\textsf{N}^{f_{e}}$ is the set of the fresh null symbols used in Definition
11 for the tgd case. Let $\sim^{\prime}=\sim\cup\\{\langle
f,f\rangle~{}|~{}f\in\textsf{N}^{f_{e}}\\}$ (notice that $\textsf{N}^{f_{e}}$
could even be empty, which implies $\sim^{\prime}=\sim$). It is easy to see
that $\sim^{\prime}$ is an equivalence relation over $\mathcal{S}$, and that
$\mathit{under}_{E}(\mathcal{I})/{\sim}\subseteq\mathcal{S}/{\sim^{\prime}}$.
Then, according to Definition 11 and thus for each
$P(T_{1},\ldots,T_{n})\in\mathcal{I}^{\prime}$ and each $1\leq i\leq n$ such
that $\mathit{type}(P,i)=\mathsf{e}$, either
$T_{i}\in\mathit{under}_{E}(\mathcal{I})/{\sim}$, and thus
$T_{i}\in\mathcal{S}/{\sim^{\prime}}$, or $T_{i}=\\{f\\}$, where
$f\in\textsf{N}^{f_{e}}$, and from the definition of $\sim^{\prime}$ it
obviously holds that $\\{f\\}\in\mathcal{S}/{\sim^{\prime}}$. Notice also that
$\mathcal{S}=\mathit{under}_{E}(\mathcal{I}^{\prime})$. Moreover, for each
$1\leq i\leq n$ such that $\mathit{type}(P,i)=\mathsf{v}$, it holds either
$T_{i}\subseteq\mathit{under}_{V}(\mathcal{I})$ or $T_{i}=\\{f^{\prime}\\}$,
where
$f^{\prime}\in\\{f_{v}^{1},\ldots,f_{v}^{j}\\}\subseteq\mathcal{S}_{VN}$.
Thus, $T_{i}$ is a non-empty subset of
$(\mathcal{S}_{V}\cap\mathit{sig}(\mathcal{K}))\cup\mathcal{S}_{VN}$. The
above facts show that $\mathcal{I}^{\prime}$ is an instance for $\mathcal{K}$
w.r.t. $\sim^{\prime}$ over
$\mathcal{S}=\mathit{under}_{E}(\mathcal{I}^{\prime})$.

_Case of entity-egd chase step:_ Let $r$ be an entity-egd of the form (3). In
this case we have
$\mathit{under}_{E}(\mathcal{I}^{\prime})=\mathit{under}_{E}(\mathcal{I})$ and
$\sim^{\prime}=\sim\cup\sim^{e}$, where $\sim^{e}=\\{\langle f,g\rangle\mid
f,g\in\mu(y)\cup\mu(z)\\}$. Obviously, $\sim^{e}$ is an equivalence relation
over $\mu(y)\cup\mu(z)$. Thus $\sim^{\prime}$ is the union of an equivalence
relation over $\mathit{under}_{E}(\mathcal{I})$ and an equivalence relation
over $\mu(y)\cup\mu(z)$. As a consequence, $\sim^{\prime}$ is a reflexive and
symmetric relation over $\mathit{under}_{E}(\mathcal{I})\cup\mu(y)\cup\mu(z)$,
and since $\mu(y)\cup\mu(z)\subseteq\mathit{under}_{E}(\mathcal{I})$, then
$\sim^{\prime}$ is reflexive and symmetric over
$\mathit{under}_{E}(\mathcal{I})=\mathit{under}_{E}(\mathcal{I}^{\prime})$. We
have then to prove that $\sim^{\prime}$ is also transitive. To this aim we
consider all possible cases. Let $a,b,c$ be elements in $\mathcal{S}$. The
following situations are conceivable:

  * •

$(a,b)\in\sim$ and $(b,c)\in\sim$, but since $\sim$ is an equivalence relation
over $\mathit{under}_{E}(\mathcal{I})$, then $(a,c)\in\sim$, and since
$\sim\subseteq\sim^{\prime}$ then $(a,c)\in\sim^{\prime}$.

  * •

$(a,b)\in\sim^{e}$ and $(b,c)\in\sim^{e}$, but since $\sim^{e}$ is an
equivalence relation over $\mu(y)\cup\mu(z)$, then $(a,c)\in\sim^{e}$ and
since $\sim^{e}\subseteq\sim^{\prime}$ then $(a,c)\in\sim^{\prime}$.

  * •

$(a,b)\in\sim$ and $(b,c)\in\sim^{e}$. Since $(b,c)\in\sim^{e}$, by definition
of chase step, $b,c\in\mu(y)\cup\mu(z)$, and also
$[b]_{\sim}\subseteq\mu(y)\cup\mu(z)$. Since $(a,b)\in\sim$, it also holds
that $a\in[b]_{\sim}$, and thus $a\in\mu(y)\cup\mu(z)$. This means that
$(a,b)\in\sim^{e}$ as well, which coincides with the previous case (for which
we have already shown that transitivity holds).

We can then prove that each fact $P(T_{1},\ldots,T_{n})$ of
$\mathcal{I}^{\prime}$ satisfies the conditions of Definition 1 with an
argument similar to that used in the last part of the proof for the tgd case.
The only difference is that if some $T_{i}$ does not occur also in some fact
of $\mathcal{I}$, then it must be $T_{i}=\mu(z)\cup\mu(y)$, which is indeed an
equivalence class of $\mathit{under}_{E}(\mathcal{I}^{\prime})/\sim^{\prime}$.

_Case of value-egd chase step:_ Let $r$ be a value-egd of the form (3). In
this case
$\mathit{under}_{E}(\mathcal{I}^{\prime})=\mathit{under}_{E}(\mathcal{I})$ and
$\sim^{\prime}=\sim$. The rest of the proof proceeds as for the previous
cases. We however note that in this case each $T_{i}$ that does not occur in a
fact of $\mathcal{I}$ must be of the form
$\mu(S_{1}^{y})\cup\ldots\cup\mu(S_{m}^{y})\cup\mu(S_{1}^{z})\cup\ldots\cup\mu(S_{k}^{z})$,
which is clearly a non-empty subset of
$(\mathcal{S}_{V}\cap\mathit{sig}(\mathcal{K}))\cup\mathcal{S}_{VN}$.

The property at the second bullet easily follows from the property at the
first bullet and the fact that in every chase sequence
$\mathcal{I}_{0}=\mathcal{I}^{\mathbf{D}}$ and $\mathcal{I}^{\mathbf{D}}$ is
an instance for $\mathcal{K}$ by construction.

∎

######  Proposition 4.

Let $\mathcal{K}$ be a KB, let $\sigma$ be a chase sequence for $\mathcal{K}$,
and let $\mathcal{I}_{i}$ and $\mathcal{I}_{j}$, with $i\leq j$, be two
instances for $\mathcal{K}$ w.r.t. equivalence relations $\sim^{i}$ and
$\sim^{j}$, respectively, such that $\mathcal{I}_{i}$ and $\mathcal{I}_{j}$
belong to $\sigma$. Then the following holds:

  * •

$\sim^{i}\subseteq\sim^{j}$ and
$\mathit{under}(\mathcal{I}_{i})\subseteq\mathit{under}(\mathcal{I}_{j})$;

  * •

If $P(\mathbf{T})$ is a fact in ${\mathcal{I}_{i}}$, then there is a fact
$P(\mathbf{T^{\prime}})$ in $\mathcal{I}_{j}$ such that $P(\mathbf{T})\leq
P(\mathbf{T}^{\prime})$.

###### Proof.

We recall that $\mathcal{K}=(\mathcal{T},\mathbf{D})$, where $\mathcal{T}$ is
the TBox of $\mathcal{K}$ and $\mathbf{D}$ the database of $\mathcal{K}$. The
properties can be easily proved by induction. _Base case._ Let be $i=0$ and
$j=1$, that is, consider $\mathcal{I}_{0}$ and $\mathcal{I}_{1}$, where
$\mathcal{I}_{0}$ is the base instance $\mathcal{I}^{\mathbf{D}}$ of
$\mathcal{K}$ and $\mathcal{I}_{1}$ is the instance produced by the
application of a chase step to $\mathcal{I}^{\mathbf{D}}$. The inclusions
$\sim^{0}\subseteq\sim^{1}$ and
$\mathit{under}(\mathcal{I}_{0})\subseteq\mathit{under}(\mathcal{I}_{1})$ can
be proved by using the same construction adopted in the proof of Proposition
3, where $\mathcal{I}=\mathcal{I}_{0}$ and
$\mathcal{I}^{\prime}=\mathcal{I}_{1}$. In particular, for the case in which
$r$ is a tgd, by construction, we have that
$\sim_{0}=\sim\subseteq\sim^{\prime}=\sim_{1}$. Moreover,
$\mathit{under}_{V}(\mathcal{I}^{\prime})=\mathit{under}_{V}(\mathcal{I})\cup\\{f_{v}^{1},\ldots,f_{v}^{j}\\}$
and thus
$\mathit{under}(\mathcal{I})\subseteq\mathit{under}(\mathcal{I}^{\prime})$
(that is,
$\mathit{under}(\mathcal{I}_{0})\subseteq\mathit{under}(\mathcal{I}_{1})$. The
cases in which $r$ is a value-egd or an entity-egd are even more
straightforward.

It remains to prove that for each fact $P(\mathbf{T})\in\mathcal{I}_{0}$ there
exists $P(\mathbf{T^{\prime}})\in\mathcal{I}_{1}$ such that
$\mathbf{T}\leq\mathbf{T^{\prime}}$. Let us consider the three possible chase
steps. _(tgd)_ : this step does not modify facts in $\mathcal{I}_{0}$, thus
$\mathbf{T}=\mathbf{T^{\prime}}$. _(entity-egd)_ : every equivalence class $E$
in $\mathit{active}(\mathcal{I}_{0})$, i.e., the active domain of
$\mathcal{I}_{0}$, remains as is or it is substituted by a class $E^{\prime}$
such that $E\subseteq E^{\prime}$. Moreover,
$\mathit{active}_{V}(\mathcal{I}_{0})=\mathit{active}_{V}(\mathcal{I}_{1})$.
These facts easily show the thesis in this case. _(value-egd)_ : the argument
is similar as the previous case, that is, every set of values $V$ in
$\mathit{active}_{V}(\mathcal{I}_{0})$ remains as is or it is substituted by a
set of values $V^{\prime}$ such that $V\subseteq V^{\prime}$. Moreover,
$\mathit{active}_{E}(\mathcal{I}_{0})=\mathit{active}_{E}(\mathcal{I}_{1})$.

_Inductive case._ we assume that the thesis holds for a certain integer
$\ell$, i.e., that properties $(i)$, $(ii)$, and $(iii)$ hold for each
$i,j\leq\ell$ such that $i\leq j$, and prove that they hold also for each
$i,j\leq\ell+1$ such that $i\leq j$. The only cases that need to be shown are
those in which $j=\ell+1$, because the other cases already hold by the
inductive hypothesis. Of course, if $i=\ell+1$ the condition is trivially
satisfied. For $i=\ell$ the three properties can be proved exactly as done for
the base case. Then, all cases in which $i<\ell$ follow by the previous case
and the inductive hypothesis. ∎

Prop. 4 implies that for every $i\leq j$ and every equivalence class $E$ in
$\mathit{under}_{E}(\mathcal{I}_{i})/{\sim^{i}}$, there exists $E^{\prime}$ in
$\mathit{under}_{E}(\mathcal{I}_{j})/\sim^{j}$ such that $E\subseteq
E^{\prime}$; in particular, we have that
$[e]_{\sim^{i}}\subseteq[e]_{\sim^{j}}$, for each entity
$e\in\mathcal{S}_{E}\cap\mathit{sig}(\mathcal{K})$.

When a chase sequence for a KB is infinite, there might be rules applicable to
some instance $\mathcal{I}_{i}$ in the sequence that are never applied, even
though they remain applicable in subsequent chase steps. It is however always
possible to establish a suitable order in the application of the rules so that
the above situation never occurs. Chase sequences enjoying this property are
called _fair_. In what follows, we assume that all chase sequences considered
are fair.

We now investigate the possible outcomes of the chase for a KB $\mathcal{K}$.
We first give the definition of the result of the chase for a finite chase
sequence.

######  Definition 13.

Let $\mathcal{K}=(\mathcal{T},\mathbf{D})$ be a KB.

  * •

A _finite chase of $\mathcal{K}$_ is a finite chase sequence
$\sigma=\mathcal{I}_{0},\mathcal{I}_{1},\ldots,\mathcal{I}_{m}$, for which
there is no rule $r$ in $\mathcal{T}$ and no assignment $\mu$ such that $r$
can be applied to $\mathcal{I}_{m}$ with $\mu$.

  * •

We say that $\mathcal{I}_{m}$ is the _result of the finite chase $\sigma$ for
$\mathcal{K}$_, and denote it by $\mathit{chase}(\mathcal{K},\sigma)$.

Prop. 3 implies that $\mathit{chase}(\mathcal{K},\sigma)$ is an instance for
$\mathcal{K}$. Actually, it turns out to be a solution for $\mathcal{K}$.

######  Lemma 1.

Let $\mathcal{K}$ be a KB and let
$\sigma=\mathcal{I}_{0},\mathcal{I}_{1},\ldots,\mathcal{I}_{m}$ be a finite
chase for $\mathcal{K}$. Then $\mathit{chase}(\mathcal{K},\sigma)$ is a
solution for $\mathcal{K}$.

###### Proof.

We need to prove that $\mathit{chase}(\mathcal{K},\sigma)$ satisfies all facts
in $\mathbf{D}$, all tgds, entity-egds and value-egds in $\mathcal{T}$. We
show each point separately:

  * (i)

The property that $\mathit{chase}(\mathcal{K},\sigma)$ satisfies all facts in
$\mathbf{D}$ follows from $\mathcal{I}_{0}=\mathcal{I}^{\mathbf{D}}$ and from
Proposition 4. Indeed, $\mathcal{I}^{\mathbf{D}}$ satisfies all facts in
$\mathbf{D}$, by definition of base instance, which means that for each ground
atom $P(c_{1},\ldots,c_{n})$ in $\mathbf{D}$ there is a fact
$P(T_{1},\ldots,T_{n})$ in $\mathcal{I}_{0}$ such that $c_{i}\in T_{i}$ for
$1\leq i\leq n$. By Proposition 4 it follows that in $\mathcal{I}_{m}$ there
is a tuple $\langle T_{1}^{\prime},\ldots,T_{n}^{\prime}\rangle$ such that
$T_{1}\subseteq T_{1}^{\prime},\ldots,T_{n}\subseteq T_{n}^{\prime}$, and thus
$P(c_{1},\ldots,c_{n})$ is satisfied also in
$\mathcal{I}_{m}=\mathit{chase}(\mathcal{K},\sigma)$.

  * (ii)

To prove that $\mathit{chase}(\mathcal{K},\sigma)$ satisfies all tgds in
$\mathcal{T}$, let us assume by contradiction that there is a tgd
$d=\forall\mathbf{x}(\phi(\mathbf{x})\rightarrow\exists\mathbf{y}\psi(\mathbf{x},\mathbf{y}))$
that is not satisfied by $\mathit{chase}(\mathcal{K},\sigma)$. This means that
there is an assignment $\mu$ from $\phi(\mathbf{x})$ to
$\mathit{chase}(\mathcal{K},\sigma)$ such that there is no
$\psi(\mathbf{x},\mathbf{y})$-compatible tgd-extension $\mu^{\prime}$ of $\mu$
to $\mathit{chase}(\mathcal{K},\sigma)$. But thus $d$ would be applicable to
$\mathit{chase}(\mathcal{K},\sigma)$ with assignment $\mu$, which contradicts
the hypothesis that $\sigma$ is a finite chase.

  * (iii)

The fact that $\mathit{chase}(\mathcal{K},\sigma)$ satisfies all the entity-
egds and value-egds can be proved as done in (ii) for satisfaction of tgds in
$\mathcal{T}$.

∎

The following lemma is used to prove that if $\sigma$ is a finite chase, then
$\mathit{chase}(\mathcal{K},\sigma)$ is not just a solution for $\mathcal{K}$,
but also a universal solution for $\mathcal{K}$. A similar result, known as
the Triangle Lemma, was used in (?) in the context of data exchange.

######  Lemma 2.

Let $\mathcal{I}_{1}\xrightarrow[]{r,\mu}\mathcal{I}_{2}$ be a chase step. Let
$\mathcal{I}$ be an instance for $\mathcal{K}$ such that $\mathcal{I}$
satisfies $r$ and there exists a homomorphism
$h_{1}:\mathcal{I}_{1}\rightarrow\mathcal{I}$. Then there is a homomorphism
$h_{2}:\mathcal{I}_{2}\rightarrow\mathcal{I}$ such that $h_{2}$ extends
$h_{1}$.

###### Proof.

The proof follows the line of the proof of Lemma 3.4 in (?). However, since
our structures are based on equivalence classes and sets of values, the
various steps of the proof are more involved. In particular, differently from
(?), in our framework the composition of an assignment with an homomorphism
does not directly yield a new assignment. Nonetheless, an assignment can be
constructed on the basis of such composition.

We prove the thesis by considering the three possible cases for the rule $d$
and the corresponding chase steps of Definition 11.

_Case of tgd chase step:_ Let $r$ be a tgd of the form (2). For ease of
exposition, we assume $\phi(\mathbf{x})=P_{1}(x_{1},x_{2})\land
P_{2}(x_{1},x_{2})$ and
$\psi(\mathbf{x},\mathbf{y})=P_{3}(x_{1},x_{2},y_{1},y_{2})\land
P_{4}(x_{2},y_{1},y_{2})$, where $x_{1}$ and $y_{2}$ are entity variables and
$x_{2}$ and $y_{1}$ are value-variables. The case of generic tgds can be
managed in a similar way. If we apply the operator $\tau$ to both the body and
the head of the tgd, we obtain the following formulas:
$\tau(\phi(\mathbf{x}))=P_{1}(x_{1},S_{1}^{x_{2}})\land
P_{2}(x_{1},S_{2}^{x_{2}})$
$\tau(\psi(\mathbf{x},\mathbf{y}))=P_{3}(x_{1},R_{1}^{x_{2}},R_{1}^{y_{1}},y_{2})\land
P_{4}(R_{2}^{x_{2}},R_{2}^{y_{1}},y_{2})$
We first construct an assignment $\hat{\mu}$ from $\phi(\mathbf{x})$ to
$\mathcal{I}$. By the definition of chase step, $\mu$ is an assignment from
$\phi(\mathbf{x})$ to $\mathcal{I}_{1}$. Then, there exist an equivalence
class $E_{1}\in\mathit{active}_{E}(\mathcal{I}_{1})$ and two sets of values
$V_{1},V_{2}\in\mathit{active}_{V}(\mathcal{I}_{1})$ such that $V_{1}\cap
V_{2}\neq\emptyset$, $\mu(x_{1})=E_{1}$, $\mu(S_{1}^{x_{2}})=V_{1}$,
$\mu(S_{2}^{x_{2}})=V_{2}$, $P_{1}(E_{1},V_{1})$ and $P_{2}(E_{1},V_{2})$ are
facts in $\mathcal{I}_{1}$. Since $h_{1}$ is homomorphism from
$\mathcal{I}_{1}$ to $\mathcal{I}$, there exist facts
$P_{1}(E_{1}^{\prime},V_{1}^{\prime})$, $P_{2}(E_{2}^{\prime},V_{2}^{\prime})$
in $\mathcal{I}$, such that $h_{1}(P_{1}(E_{1},V_{1}))\leq
P_{1}(E_{1}^{\prime},V_{1}^{\prime})$ and $h_{1}(P_{2}(E_{1},V_{2}))\leq
P_{2}(E_{1}^{\prime},V_{2}^{\prime})$, that is, $h_{1}(E_{1})\subseteq
E_{1}^{\prime}$, $h_{1}(E_{1})\subseteq E_{2}^{\prime}$,
$h_{1}(V_{1})\subseteq V_{1}^{\prime}$, $h_{1}(V_{2})\subseteq
V_{2}^{\prime}$. Since $V_{1}\cap V_{2}\neq\emptyset$, then also
$V_{1}^{\prime}\cap V2^{\prime}\neq\emptyset$. Moreover, since
$E_{1}^{\prime}$ and $E_{2}^{\prime}$ are equivalence classes containing the
same non-empty subset, they must be the same equivalence class, i.e.,
$E_{1}^{\prime}=E_{2}^{\prime}$. We then define the mapping $\hat{\mu}$ as
follows: $\hat{\mu}(x_{1})=E_{1}^{\prime}$,
$\hat{\mu}(S_{1}^{x_{2}})=V_{1}^{\prime}$, and
$\hat{\mu}(S_{2}^{x_{2}})=V_{2}^{\prime}$. It is easy to see that $\hat{\mu}$
satisfies the conditions in Definition 3, and thus it is an assignment from
$\phi(\mathbf{x})$ to $\mathcal{I}$.

Since $\mathcal{I}$ satisfies $r$, there is an assignment $\mu^{\prime}$ that
is a $\psi(\mathbf{x},\mathbf{y})$-compatible extension of $\hat{\mu}$ to
$\mathcal{I}$. By definition we have that:

  * •

$\mu^{\prime}(x_{1})=\hat{\mu}(x_{1})=E_{1}^{\prime}$

  * •

$\mu^{\prime}(R_{1}^{x_{2}})=V_{3}^{\prime}$,
$\mu^{\prime}(R_{2}^{x_{2}})=V_{4}^{\prime}$, where
$V_{3}^{\prime},V_{4}^{\prime}\in\mathit{active}_{V}(\mathcal{I})$ are such
that $V_{1}^{\prime}\cap V_{2}^{\prime}\subseteq V_{3}^{\prime}\cap
V_{4}^{\prime}$,

  * •

$\mu^{\prime}(R_{1}^{y_{1}})=V_{5}^{\prime}$,
$\mu^{\prime}(R_{2}^{y_{1}})=V_{6}^{\prime}$, where
$V_{5}^{\prime},V_{6}^{\prime}\in\mathit{active}_{V}(\mathcal{I})$ are such
that $V_{5}^{\prime}\cap V_{6}^{\prime}\neq\emptyset$,

  * •

$\mu^{\prime}(y_{2})=E_{2}^{\prime}$, where
$E_{2}^{\prime}\in\mathit{active}_{E}(\mathcal{I})$,

  * •

$\mathcal{I}$ contains the facts
$P_{3}(E_{1}^{\prime},V_{3}^{\prime},V_{5}^{\prime},E_{2}^{\prime})$ and
$P_{4}(V_{4}^{\prime},V_{6}^{\prime},E_{2}^{\prime})$.

Then, by definition of tgd chase step it follows that there is also an
assignment $\mu_{2}$ from $\psi(\mathbf{x},\mathbf{y})$ to $\mathcal{I}_{2}$
defined as follows

  * •

$\mu_{2}(x_{1})=\mu(x_{1})=E_{1}$

  * •

$\mu_{2}(R_{1}^{x_{2}})=\mu_{2}(R_{2}^{x_{2}})=V_{1}\cap V_{2}$

  * •

$\mu_{2}(R_{1}^{y_{1}})=\mu_{2}(R_{2}^{y_{1}})=\\{f_{v}^{y_{1}}\\}$

  * •

$\mu_{2}(y_{2})=[f_{e}^{y_{2}}]$

where $f_{v}^{y_{1}}$ and $f_{e}^{y_{2}}$ are the fresh value-null and entity-
null, respectively, introduced by the chase step. We remark that $\mu_{2}$ is
a $\psi(\mathbf{x},\mathbf{y})$-compatible extension of $\mu$ to
$\mathcal{I}_{2}$, and that
$\mathit{under}(\mathcal{I}_{2})=\mathit{under}(\mathcal{I}_{1})\cup\\{f_{v}^{y_{1}},f_{e}^{y_{2}}\\}$.
Moreover, $\mathcal{I}_{2}=\mathcal{I}_{1}\cup\\{P_{3}(E_{1},V_{1}\cap
V_{2},\\{f_{v}^{y_{1}}\\},[f_{e}^{y_{2}}]),P_{4}(V_{1}\cap
V_{2},\\{f_{v}^{y_{1}}\\},[f_{e}^{y_{2}}])\\}$.

We now construct a mapping $h_{2}$ and show that it is an homomorphism from
$\mathcal{I}_{2}$ to $\mathcal{I}$. We define $h_{2}$ as follows:

  * •

$h_{2}(o)=h_{1}(o)$ for each $o\in\mathit{under}(\mathcal{I}_{1})$;

  * •

$h_{2}(f_{v}^{y_{1}})=v$, where $v$ is any element in $V_{5}^{\prime}\cap
V_{6}^{\prime}$;

  * •

$h_{2}(f_{e}^{y_{2}})=e$, where $e$ is any element in $E_{2}^{\prime}$.

Note that, as stated before, $V_{5}^{\prime}\cap V_{6}^{\prime}\neq\emptyset$.
Moreover, $E_{2}^{\prime}\neq\emptyset$, since $E_{2}^{\prime}$ is an
equivalence class in $\mathit{active}(\mathcal{I})$. Thus $v$ and $e$ above
always exist. Note also that $h_{2}$ extends $h_{1}$.

By construction, $h_{2}$ is a mapping from the elements of
$\mathit{under}(\mathcal{I}_{2})$ to the elements of
$\mathit{under}(\mathcal{I})$. Moreover, Conditions 1-4 of Definition 7
(homomorphism) are trivially satisfied. To prove that $h_{2}$ is homomorphism
from $\mathcal{I}_{2}$ to $\mathcal{I}$ it remains to prove that also
Condition 5 of Definition 7 holds. Such condition is obviously satisfied by
all facts in $\mathcal{I}_{1}$ (which is contained in $\mathcal{I}_{2}$),
since $h_{2}$ over such facts behaves as $h_{1}$, and $h_{1}$ is an
homomorphism to $\mathcal{I}$. Consider now the fact $P_{3}(E_{1},V_{1}\cap
V_{2},\\{f_{v}^{y_{1}}\\},[f_{e}^{y_{2}}])$, which is in
$\mathcal{I}_{2}\setminus\mathcal{I}_{1}$. We have to show that there exists a
fact in $\mathcal{I}$ of the form
$P_{3}(\hat{E_{1}},\hat{V_{1}},\hat{V_{2}},\hat{E_{2}})$, where
$\hat{E_{1}},\hat{E_{2}}\in\mathit{active}_{E}(\mathcal{I})$ and
$\hat{V_{1}},\hat{V_{2}}\in\mathit{active}_{V}(\mathcal{I})$, such that
$h_{2}(P_{3}(E_{1},V_{1}\cap V_{2},\\{f_{v}^{y_{1}}\\},[f_{e}^{y_{2}}]))\leq
P_{3}(\hat{E_{1}},\hat{V_{1}},\hat{V_{2}},\hat{E_{2}})$, i.e.,
$h_{2}(E_{1})\subseteq\hat{E_{1}}$, $h_{2}(V_{1}\cap
V_{2})\subseteq\hat{V_{1}}$, $h_{2}(\\{f_{v}^{y_{1}}\\})\subseteq\hat{V_{2}}$,
$h_{2}([f_{e}^{y_{2}}])\subseteq\hat{E_{2}}$. To this aim we set
$\hat{E_{1}}=E_{1}^{\prime}$, $\hat{V_{1}}=V_{3}^{\prime}$,
$\hat{V_{2}}=V_{5}^{\prime}$, $\hat{E_{2}}=E_{2}^{\prime}$, and show that the
above mentioned containments do indeed hold.

  * •

$h_{2}(E_{1})\subseteq E_{1}^{\prime}$ follows from
$h_{2}(E_{1})=h_{1}(E_{1})$ and $h_{1}(E_{1})\subseteq E_{1}^{\prime}$;

  * •

$h_{2}(V_{1}\cap V_{2})\subseteq V_{3}^{\prime}$ is a consequence of
$h_{2}(V_{1}\cap V_{2})=h_{1}(V_{1}\cap V_{2})\subseteq h_{1}(V_{1})\cap
h_{1}(V_{2})\subseteq V_{1}^{\prime}\cap V_{2}^{\prime}\subseteq
V_{3}^{\prime}\cap V_{4}^{\prime}\subseteq V_{3}^{\prime}$.

  * •

$h_{2}(\\{f_{v}^{y_{1}}\\})\subseteq V_{5}^{\prime}$ holds because
$h_{2}(f_{v}^{y_{1}})=v$ and $v\in V_{5}^{\prime}\cap V_{6}^{\prime}$, and
thus $h_{2}(\\{f_{v}^{y_{1}}\\})=\\{v\\}\subseteq V_{5}^{\prime}$.

  * •

$h_{2}([f_{e}^{y_{2}}])\subseteq E_{2}^{\prime}$ holds because
$h_{2}(f_{v}^{y_{1}})=e$ and $e\in E_{2}^{\prime}$, and thus
$h_{2}([f_{e}^{y_{2}}])=[e]\subseteq E_{2}^{\prime}$.

We can proceed in analogously to show that Condition 5 of Definition 7 is
satisfied also for the other fact, $P_{4}(V_{1}\cap
V_{2},\\{f_{v}^{y_{1}}\\},[f_{e}^{y_{2}}])$, which is contained in
$\mathcal{I}_{2}\setminus\mathcal{I}_{1}$.

_Case of entity-egd chase step:_ Let $r$ be an entity-egd of the form (3). By
the definition of the chase step, $\mu$ is an assignment from
$\phi(\mathbf{x})$ to $\mathcal{I}_{1}$, and in particular there exist
equivalence classes $E_{1},E_{2}\in\mathit{active}_{E}(\mathcal{I}_{1})$ such
that $\mu(y)=E_{1}$ and $\mu(z)=E_{2}$. It is then possible to construct an
assignment $\hat{\mu}$ from $\phi(\mathbf{x})$ to $\mathcal{I}$ such that
$\hat{\mu}(y)=E_{1}^{\prime}$, $\hat{\mu}(z)=E_{2}^{\prime}$,
$E_{1}^{\prime},E_{2}^{\prime}\in\mathit{active}_{E}(\mathcal{I}_{1})$,
$h_{1}(E_{1})\subseteq E_{1}^{\prime}$ and $h_{1}(E_{2})\subseteq
E_{2}^{\prime}$. The construction of $\hat{\mu}$ is similar to the analogous
construction described for the case of tgd chase step. For the sake of
completeness we describe this procedure also for the entity-egd chase step
(note that in this case we need to also deal with entities and values possibly
occurring in the rule body $\phi(\mathbf{x})$). For ease of exposition, and
without loss of generality, we assume that
$\phi(\mathbf{x})=P_{1}(x,y,e,v)\land P_{2}(x,y,z)$, where $x$ is a value-
variable, $y,z$ are entity-variables, $e\in\mathcal{S}_{E}$, and
$v\in\mathcal{S}_{V}$. By applying the operator $\tau$ to $\phi(\mathbf{x})$
we obtain $\tau(\phi(\mathbf{x}))=P_{1}(S_{1}^{x},y,e,v)\land
P_{2}(S_{2}^{x},y,z)$. Since $\mu$ is an assignment from $\phi(\mathbf{x})$ to
$\mathcal{I}_{1}$, there exist
$E,E_{1},E_{2}\in\mathit{active}_{E}(\mathcal{I}_{1})$ and
$V,V_{1},V_{2}\in\mathit{active}_{V}(\mathcal{I}_{1})$ such that $e\in E$,
$V_{1}\cap V_{2}\neq\emptyset$, $v\in V$, $P_{1}(V_{1},E_{1},E,V)$ and
$P_{2}(V_{2},E_{1},E_{2})$ are two facts in $\mathcal{I}_{1}$, and
$\mu(S_{1}^{x})=V_{1}$, $\mu(y)=E_{1}$, $\mu(v)=V$, $\mu(S_{2}^{x})=V_{2}$,
and $\mu(z)=E_{2}$. Since $h_{1}$ is homomorphism from $\mathcal{I}_{1}$ to
$\mathcal{I}$, there exist
$P_{1}(V_{1}^{\prime},E_{1}^{\prime},E^{\prime},V^{\prime})$ and
$P_{2}(V_{2}^{\prime},E_{1}^{\prime},E_{2}^{\prime})$ in $\mathcal{I}$ such
that $h_{1}(P_{1}(V_{1},E_{1},E,V))\leq
P_{1}(V_{1}^{\prime},E_{1}^{\prime},E^{\prime},V^{\prime})$ and
$h_{1}(P_{2}(V_{2},E_{1},E_{2}))\leq
P_{2}(V_{2}^{\prime},E_{1}^{\prime},E_{2}^{\prime})$, i.e.,
$h_{1}(E_{1})\subseteq E_{1}^{\prime}$, $h_{1}(V_{1})\subseteq
V_{1}^{\prime}$, $h_{1}(E)\subseteq E^{\prime}$, $h_{1}(V)\subseteq
V^{\prime}$, $h_{1}(V_{2})\subseteq V_{2}^{\prime}$, $h_{1}(E_{2})\subseteq
E_{2}^{\prime}$ and . We then define $\hat{\mu}$ as follows:
$\hat{\mu}(S_{1}^{x})=V_{1}^{\prime}$, $\hat{\mu}(y)=E_{1}^{\prime}$,
$\hat{\mu}(v)=V$, $\hat{\mu}(S_{2}^{x})=V_{2}^{\prime}$,
$\hat{\mu}(z)=E_{2}^{\prime}$. It is easy to see that $\hat{\mu}$ is an
assignment from $\phi(\mathbf{x})$ to $\mathcal{I}$. In particular, since
$e\in E$ and $h(e)=e$ it obviously holds $e\in h_{1}(E)\subseteq E^{\prime}$,
which implies $e\in E^{\prime}$. Similarly, since $v\in\mu(v)=V$ and
$v=h_{1}(v)$ we have that $v\in h_{1}(V)\subseteq V^{\prime}$, which implies
$v\in V^{\prime}$.

We then take $h_{2}$ to be $h_{1}$ and show that $h_{1}$ is still a
homomorphism when considered from $\mathcal{I}_{2}$ to $\mathcal{I}$. We soon
note that $\mathit{under}(\mathcal{I}_{1})=\mathit{under}(\mathcal{I}_{2})$,
and thus $h_{1}$ is a mapping from $\mathit{under}(\mathcal{I}_{2})$ as well.
Moreover, since $h_{1}$ is an homomorphism, then Conditions 1-4 of Definition
7 are obviously satisfied. It remains to prove that Condition 5 of Definition
7 is also satisfied, i.e., we have to prove that for each fact
$P(T_{1},\ldots,T_{n})$ in $\mathcal{I}_{2}$ there exists a fact
$P(U_{1},\ldots,U_{n})$ in $\mathcal{I}$ such that $h_{1}(T_{i})\subseteq
U_{i}$, for $1\leq i\leq n$. We recall that $\mathcal{I}_{2}$ is obtained by
replacing in $\mathcal{I}_{1}$ every occurrence of $E_{1}$ and every
occurrence of $E_{2}$ with $E_{1}\cup E_{2}$. Therefore, two cases are
possible. $(a)$ $T_{i}\neq E_{1}\cup E_{2}$ for $1\leq i\leq n$. In this case,
the thesis holds since $P(T_{1},\ldots,T_{n})$ is also in $\mathcal{I}_{1}$
and $h_{1}$ is an homomorphism from $\mathcal{I}_{1}$ to $\mathcal{I}$. $(b)$
there is $j$ such that $1\leq j\leq n$ and $T_{j}=E_{1}\cup E_{2}$. Without
loss of generality we can also assume that $T_{i}\neq E_{1}\cup E_{2}$ for
$1\leq i\leq n$ and $i\neq j$. Since two equivalence classes are either
disjoint or are the same class, we have that each $T_{i}$ such that $i\neq j$
is either a set of values or an equivalence class disjoint from $E_{1}\cup
E_{2}$. Then, there is a fact
$P(T_{1},\ldots,T_{j-1},T^{\prime}_{j},T_{j+1}\ldots,T_{n})$ in
$\mathcal{I}_{1}$ where it is either $T^{\prime}_{j}=E_{1}$ or
$T^{\prime}_{j}=E_{2}$, and, for every $i\neq j$, $T_{i}\neq E_{1}$ and
$T_{i}\neq E_{2}$ . Let us consider $T^{\prime}_{j}=E_{1}$ (the other choice
can be treated analogously). Then, there must exist a fact
$P(U_{1},\ldots,U_{j-1},U_{j},U_{j+1}\ldots,U_{n})$ in $\mathcal{I}$ such that
$h_{1}(T_{i})\subseteq U_{i}$ for $1\leq i\leq n$. In particular, this means
that $h_{1}(E_{1})\subseteq U_{j}$, with $U_{j}$ an equivalence class in
$\mathit{active}_{E}(\mathcal{I})$. Since $h_{1}(E_{1})\subseteq
E_{1}^{\prime}$, it must be $U_{j}=E_{1}^{\prime}$. Indeed, for the two
equivalence classes $U_{j}$ and $E_{1}^{\prime}$ it holds either
$U_{j}=E_{1}^{\prime}$ or $U_{j}\cap E_{1}^{\prime}=\emptyset$, but the second
option is impossible, since $h_{1}(E_{1})$ is a common non-empty subset of
$U_{j}$ and $E_{1}^{\prime}$. Then, since $\mathcal{I}$ satisfies the entity-
egd $d$, which in $d$ is triggered by $\hat{\mu}$, we have that
$E_{1}^{\prime}=E_{2}^{\prime}$ and thus from $h_{1}(E_{1})\subseteq
E_{1}^{\prime}$ and $h_{1}(E_{2})\subseteq E_{2}^{\prime}$ it follows
$h_{1}(E_{1})\cup h_{1}(E_{2})\subseteq E_{1}^{\prime}$ and thus
$h_{1}(E_{1}\cup E_{2})\subseteq E_{1}^{\prime}$, that is
$h_{1}(T_{j})\subseteq E_{1}^{\prime}=U_{j}$. This shows that
$P(U_{1},\ldots,U_{j-1},U_{j},U_{j+1}\ldots,U_{n})$ is the fact in
$\mathcal{I}$ we were looking for, thus proving Condition 5 of Definition 7.

_Case of value-egd chase step:_ The proof is similar to the one used for the
entity-egd chase step. Let $r$ be an entity-egd of the form (3), and, Without
loss of generality, assume that $\phi(\mathbf{x})=P_{1}(y,z)\land P_{2}(z)$,
where $y,z$ are value-variables (the possible presence of entity-variables,
entities and values can be dealt with as shown in the previous cases of this
proof). Then, $\tau(\phi(\mathbf{x}))=P_{1}(S_{1}^{y},S_{1}^{z})\land
P_{2}(S_{2}^{z})$. Since $\mu$ is assignment from $\phi(\mathbf{x})$ to
$\mathcal{I}_{1}$, then there exist
$V_{1},V_{2},V_{3}\in\mathit{active}_{V}(\mathcal{I}_{1})$ such that
$\mu(S_{1}^{y})=V_{1}$, $\mu(S_{1}^{z})=V_{2}$, $\mu(S_{2}^{z})=V_{3}$,
$V_{2}\cap V_{3}\neq\emptyset$, $P_{1}(V_{1},V_{2})$ and $P_{2}(V_{3})$ are
facts in $\mathcal{I}_{1}$. Since $h_{1}$ is homomorphism from
$\mathcal{I}_{1}$ to $\mathcal{I}$, then there are facts in
$P_{1}(V_{1}^{\prime},V_{2}^{\prime})$ and $P_{2}(V_{3}^{\prime})$ in
$\mathcal{I}$ such that $h_{1}(P_{1}(V_{1},V_{2}))\leq
P_{1}(V_{1}^{\prime},V_{2}^{\prime})$ and $h_{1}(P_{2}(V_{3}))\leq
P_{2}(V_{3}^{\prime})$, i.e., $h_{1}(V_{1})\subseteq V_{1}^{\prime}$,
$h_{1}(V_{2})\subseteq V_{2}^{\prime}$, $h_{1}(V_{3})\subseteq
V_{3}^{\prime}$. Since $V_{2}\cap V_{3}\neq\emptyset$, then
$V_{2}^{\prime}\cap V_{3}^{\prime}\neq\emptyset$. We define a mapping
$\hat{\mu}$ such that $\hat{\mu}(S_{1}^{y})=V_{1}^{\prime}$,
$\hat{\mu}(S_{1}^{z})=V_{2}^{\prime}$, $\hat{\mu}(S_{2}^{z})=V_{3}^{\prime}$.
It is easy to see that $\hat{\mu}$ is an assignment from $\phi(\mathbf{x})$ to
$\mathcal{I}$.

We then take $h_{2}$ to be $h_{1}$ and show that $h_{1}$ is still a
homomorphism when considered from $\mathcal{I}_{2}$ to $\mathcal{I}$. We soon
note that $\mathit{under}(\mathcal{I}_{1})=\mathit{under}(\mathcal{I}_{2})$,
and thus $h_{1}$ is a mapping from $\mathit{under}(\mathcal{I}_{2})$ as well.
Moreover, since $h_{1}$ is an homomorphism, then condition 1-4 of Definition 7
are obviously satisfied. Condition 5 of Definition 7 is also already satisfied
for all facts in $\mathcal{I}_{2}$ that are also in $\mathcal{I}_{1}$. It
remains to prove that such condition holds also for facts in
$\mathcal{I}_{2}\setminus\mathcal{I}_{1}$. The only two such facts are
$P_{1}(V_{1}\cup V_{2}\cup V_{3},V_{1}\cup V_{2}\cup V_{3})$ and
$P_{2}(V_{1}\cup V_{2}\cup V_{3})$ (see the value-egd chase step in Definition
11). We have to show that there are facts $P_{1}(\hat{V_{1}},\hat{V_{2}})$ and
$P_{2}(\hat{V_{3}})$ in $\mathcal{I}$ such that $h_{1}(P_{1}(V_{1}\cup
V_{2}\cup V_{3},V_{1}\cup V_{2}\cup V_{3}))\leq
P_{1}(\hat{V_{1}},\hat{V_{2}})$ and $h_{1}(P_{2}(V_{1}\cup V_{2}\cup
V_{3}))\leq P_{2}(\hat{V_{3}})$, i.e., $h_{1}(V_{1}\cup V_{2}\cup
V_{3})\subseteq\hat{V_{1}}$, $h_{1}(V_{1}\cup V_{2}\cup
V_{3})\subseteq\hat{V_{2}}$, and $h_{1}(V_{1}\cup V_{2}\cup
V_{3})\subseteq\hat{V_{3}}$. It is not difficult to see that such facts are
$P_{1}(V_{1}^{\prime},V_{2}^{\prime})$ and $P_{2}(V_{3}^{\prime})$. Indeed, we
know that $h_{1}(V_{1})\subseteq V_{1}^{\prime}$ , $h_{1}(V_{2})\subseteq
V_{2}^{\prime}$ and $h_{1}(V_{3})\subseteq V_{3}^{\prime}$. Then, since
$\mathcal{I}$ satisfies $d$, which is triggered in $\mathcal{I}$ by
$\hat{\mu}$, it must be $V_{1}^{\prime}=V_{2}^{\prime}=V_{3}^{\prime}$. Thus,
we have that $h_{1}(V_{1})\cup h_{1}(V_{2})\cup h_{1}(V_{3})\subseteq
V_{1}^{\prime}=V_{2}^{\prime}=V_{3}^{\prime}$, and thus $h_{1}(V_{1}\cup
V_{2}\cup V_{3})\subseteq V_{1}^{\prime}=V_{2}^{\prime}=V_{3}^{\prime}$, which
shows the thesis. ∎

The following theorem is the main result of this section.

######  Theorem 2.

If $\mathcal{K}$ is a KB and
$\sigma=\mathcal{I}_{0},\mathcal{I}_{1},\ldots,\mathcal{I}_{m}$ is a finite
chase for $\mathcal{K}$, then $\mathit{chase}(\mathcal{K},\sigma)$ is a
universal solution for $\mathcal{K}$.

###### Proof.

From Lemma 1 it follows that $\mathit{chase}(\mathcal{K},\sigma)$ is a model
for $\mathcal{K}$. It remains to prove that it is universal, i.e., that there
exists an homomorphism from
$\mathit{chase}(\mathcal{K},\sigma)=\mathcal{I}_{m}$ to every solution for
$\mathcal{K}$. The proof is based on Lemma 2 and on the observation that the
identity mapping $\mathsf{id}$ is a homomorphism from $\mathcal{I}_{0}$ to
every $\mathcal{I}\in\mathit{Sol}(\mathcal{K})$. The thesis can be thus proved
by applying Lemma 2 to each $\mathcal{I}_{i},\mathcal{I}_{i+1}$ in $\sigma$,
starting from $\mathcal{I}_{0},\mathcal{I}_{1}$, with $h_{1}=\mathsf{id}$ as
homomorphism from $\mathcal{I}_{0}$ to a solution $\mathcal{I}$ for
$\mathcal{K}$. ∎

Theorem 2 implies that if both $\sigma$ and $\sigma^{\prime}$ are finite
chases for $\mathcal{K}$, then $\mathit{chase}(\mathcal{K},\sigma)$ and
$\mathit{chase}(\mathcal{K},\sigma^{\prime})$ are homomorphically equivalent.
Thus, the result of a finite chase for $\mathcal{K}$ is unique up to
homomorphic equivalence.

It is easy to verify that if $\mathcal{K}=(\mathcal{T},\mathbf{D})$ is a KB in
which every tgd in $\mathcal{T}$ is full (i.e., there are no existential
quantifiers in the heads of the tgds in $\mathcal{T}$), then every chase
sequence for $\mathcal{K}$ is finite. In particular, this holds true if
$\mathcal{T}$ consists of egds only, which covers all entity resolution
settings.

For infinite chase sequences, the definition of the result of the chase
requires some care. The typical approach adopted when only tgds are present
(?; ?), or for settings involving _separable_ tgds and egds (?; ?; ?), is to
define the result of an infinite chase sequence as the union of all facts
generated in the various chase steps. This approach does not work for
arbitrary tgds and egds since the resulting instance needs not satisfy all the
rules and thus needs not be a solution in our terminology. Moreover, in our
framework the union of all instances in an infinite chase sequence is not even
an instance for the KB at hand, because the sets of entities in the result
does not correspond to equivalence classes with respect to an equivalence
relation.

An alternative approach, which might be better suited for a setting with
arbitrary tgds and egds, is to define the result of an infinite chase sequence
as the instance containing all _persistent_ facts, i.e., all facts that are
introduced in some step in the chase sequence and are never modified in
subsequent chase steps. This notion was introduced in (?). In our setting,
given a KB $\mathcal{K}$ and an infinite chase sequence
$\sigma=\mathcal{I}_{0},\mathcal{I}_{1},\ldots$, this means that we define the
result $\mathit{chase}(\mathcal{K},\sigma)$ of the infinite chase $\sigma$ of
$\mathcal{K}$ as follows:

$\mathit{chase}(\mathcal{K},\sigma)=\\{f\mid\textrm{there is some }i\geq
0\textrm{ such that }\\\ f\in\mathcal{I}_{j}\textrm{ for each }j\geq i\\}.$
(4)

The following example shows that this definition does not work in our
framework, because the above set might be empty (even if the database
$\mathbf{D}$ is non-empty).

######  Example 12.

Let $\mathcal{K}=\langle\mathcal{T},\mathbf{D}\rangle$, where
$\mathbf{D}=\\{P(1,2)\\}$ and $\mathcal{T}$ consists of the two rules

$(r_{1})~{}P(x,y)\rightarrow P(y,z);~{}~{}r_{2})~{}P(x,y)\land
P(y,z)\rightarrow y=z,$

with $\mathit{type}(P)=\langle\mathsf{v},\mathsf{v}\rangle$. We construct an
infinite chase sequence starting with
$\mathcal{I}_{0}=\\{P(\\{1\\},\\{2\\})\\}$ and by repeatedly applying the
above rules with suitable assignments in the following order:
$r_{1},r_{1},r_{2},r_{1},r_{2},r_{1},r_{2},r_{1}\ldots$.

We obtain the infinite chase sequence
$\sigma=\mathcal{I}_{0},\mathcal{I}_{1},\ldots$

$\begin{array}[]{lcl}\mathcal{I}_{0}&=&\\{P(\\{1\\},\\{2\\})\\}\\\
\mathcal{I}_{1}&=&\\{P(\\{1\\},\\{2\\}),P(\\{2\\},\\{v_{\bot}^{1}\\})\\}\\\
\mathcal{I}_{2}&=&\\{P(\\{1\\},\\{2\\}),P(\\{2\\},\\{v_{\bot}^{1}\\}),P(\\{v_{\bot}^{1}\\},\\{v_{\bot}^{2}\\})\\}\\\
\mathcal{I}_{3}&=&\\{P(\\{1\\},\\{2,v_{\bot}^{1}\\}),P(\\{2,v_{\bot}^{1}\\},\\{2,v_{\bot}^{1}\\}),\\\
&&P(\\{v_{\bot}^{1}\\},\\{v_{\bot}^{2}\\})\\}\\\ \ldots\\\
\mathcal{I}_{7}&=&\\{P(\\{1\\},\\{2,v_{\bot}^{1},v_{\bot}^{2}\\}),P(\\{2,v_{\bot}^{1}\\},\\{2,v_{\bot}^{1},v_{\bot}^{2}\\}),\\\
&&P(\\{2,v_{\bot}^{1},v_{\bot}^{2}\\},\\{2,v_{\bot}^{1},v_{\bot}^{2}\\}),P(\\{v_{\bot}^{2}\\},\\{v_{\bot}^{3}\\}),\\\
&&P(\\{v_{\bot}^{3}\\},\\{v_{\bot}^{4}\\})\\}\\\ \ldots\end{array}$

It is not difficult to see that the set $\mathit{chase}(\mathcal{K},\sigma)$
defined in (4) above is empty, i.e., _no_ persistent facts occur in $\sigma$.
∎

The infinite chase sequence $\sigma$ in Ex. 12 is fair. At the same time,
there are finite fair sequences for the KB $\mathcal{K}$ in this example.
Indeed, if we apply rule $r_{1}$ and then rule $r_{2}$, we get a finite chase
sequence
$\sigma^{\prime}=\mathcal{I}^{\prime}_{0},\mathcal{I}^{\prime}_{1},\mathcal{I}^{\prime}_{2}$,
where

$\begin{array}[]{lcl}\mathcal{I}^{\prime}_{0}&=&\\{P(\\{1\\},\\{2\\})\\}\\\
\mathcal{I}^{\prime}_{1}&=&\\{P(\\{1\\},\\{2\\}),P(\\{2\\},\\{v_{\bot}^{1}\\})\\}\\\
\mathcal{I}^{\prime}_{2}&=&\\{P(\\{1\\},\\{2,v_{\bot}\\}),P(\\{2,v_{\bot}\\},\\{2,v_{\bot}\\})\\}.\end{array}$

Consequently,
$\mathit{chase}(\mathcal{K},\sigma^{\prime})=\mathcal{I}^{\prime}_{2}$. Thus,
further investigation is needed when both finite and infinite chase sequences
exist for a KB. We leave this as a topic for future work.

##  6 Related Work

From the extensive literature on entity resolution, we comment briefly on only
a small subset of earlier work that is related to ours.

Swoosh (?) is a generic approach to entity resolution in which the functions
used to compare and merge records are “black boxes”. In our framework, the
match function is determined by entity-egds and value-egds, whereas the merge
function is implemented via the union operation - an important special case of
merge functions in the Swoosh approach. In this sense, our framework is less
general than Swoosh. In another sense, our framework is more general as it
supports tgds, differentiates between entities and values, and incorporates
query answering.

As in the work on matching dependencies (MDs) (?; ?), we consider variables in
the head of egds to be matched and merged rather than to be made equal. In
(?), generic functions obeying some natural properties are used to compute the
result of a match, while we use the union of the sets of values or sets of
entities involved in the match. In the MDs framework, a version of the chase
procedure is used to resolve dependency violations. This chase acts locally on
a pair of tuples at each step, whereas our chase procedure matches entities in
a global fashion and values in a local fashion. Furthermore, we support tgds,
which are not in the framework of MDs.

There is a body of work on declarative entity resolution and its variants that
is related to our framework; relevant references include the Dedupalog
framework (?), the declarative framework for entity linking in (?; ?), and the
more recent LACE framework (?). In both Dedupalog and LACE, there is a
distinction between hard and soft entity resolution rules. LACE supports
global merges and creates equivalence classes as we do, but it does not
support local merges; also, LACE combines entity resolution rules with denial
constraints, while our framework combines entity resolution rules with tgds.
The declarative framework for entity linking in (?; ?) uses key dependencies
and disjunctive constraints with “weighted” semantics that measure the
strength of the links. The key dependencies are interpreted as hard rules that
the solutions must satisfy in the standard sense. Consequently, two
conflicting links cannot co-exist in the same solution, hence that approach
uses repairs to define the notion of the certain links. In contrast, in our
framework we carry along via the chase all the alternatives as either sets of
values or equivalence classes of entities. Another feature of our framework is
the focus on the certain answers of queries. Finally, the aforementioned
declarative framework for entity linking uses more general link relations
without rules for an equivalence relation of entities; thus, it is less
focused on entity resolution.

##  7 Conclusions and Future Work

The main contribution of this paper is the development of a new declarative
framework that combines entity resolution and query answering in knowledge
bases. This is largely a conceptual contribution because the development of
the new declarative framework entailed rethinking from first principles the
definitions of such central notions as assignment, homomorphism, satisfaction
of tgds and egds in a model, and universal solution. At the technical level,
we designed a chase procedure that never fails, and showed that, when it
terminates, it produces a universal solution that, in turn, can be used in
query answering.

As regards future directions, perhaps the most pressing issue is to identify a
“good” notion of the result of the chase when the chase procedure does not
terminate. This may lead to extending the framework presented here to settings
where all universal solutions are infinite. While infinite universal solutions
cannot be materialized, such solutions have been used to obtain rewritability
results (?), occasionally combined with partial materialization of the result
of an infinite chase (?). In parallel, it is important to identify structural
conditions on the tgds and the egds of the TBox that guarantee termination of
the chase procedure in polynomial time and, thus, yield tractable conjunctive
query answering. It is also worthwhile exploring whether other variants of the
chase procedure, such as the semi-oblivious (a.k.a. Skolem) chase (?; ?) or
the core chase (?), can be suitably adapted to our framework so that their
desirable properties carry over.

Finally, we note that there are several different areas, including data
exchange (?), data integration (?; ?), ontology-mediated query answering (?),
and ontology-based data access (?), in which tgds and egds play a crucial
role. We believe that the framework presented here makes it possible to infuse
entity resolution into these areas in a principled way.

## References

  * Arasu, Ré, and Suciu 2009 Arasu, A.; Ré, C.; and Suciu, D.  2009\.  Large-scale deduplication with constraints using dedupalog.  In Proc. of the 25th IEEE Int. Conf. on Data Engineering (ICDE), 952–963.  IEEE Computer Society Press.
  * Artale et al. 2009 Artale, A.; Calvanese, D.; Kontchakov, R.; and Zakharyaschev, M.  2009\.  The DL-Lite family and relations.  J. of Artificial Intelligence Research 36:1–69.
  * Baader et al. 2007 Baader, F.; Calvanese, D.; McGuinness, D.; Nardi, D.; and Patel-Schneider, P. F., eds.  2007\.  The Description Logic Handbook: Theory, Implementation and Applications.  Cambridge University Press, 2nd edition.
  * Baget et al. 2011 Baget, J.; Leclère, M.; Mugnier, M.; and Salvat, E.  2011\.  On rules with existential variables: Walking the decidability line.  Artificial Intelligence 175(9-10):1620–1654.
  * Beeri and Vardi 1984 Beeri, C., and Vardi, M. Y.  1984\.  A proof procedure for data dependencies.  J. of the ACM 31(4):718–741.
  * Benjelloun et al. 2009 Benjelloun, O.; Garcia-Molina, H.; Menestrina, D.; Su, Q.; Whang, S. E.; and Widom, J.  2009\.  Swoosh: a generic approach to entity resolution.  Very Large Database J. 18(1):255–276.
  * Bertossi, Kolahi, and Lakshmanan 2013 Bertossi, L. E.; Kolahi, S.; and Lakshmanan, L. V. S.  2013\.  Data cleaning and query answering with matching dependencies and matching functions.  Theoretical Computer Science 52(3):441–482.
  * Bienvenu and Ortiz 2015 Bienvenu, M., and Ortiz, M.  2015\.  Ontology-mediated query answering with data-tractable description logics.  In Faber, W., and Paschke, A., eds., Reasoning Web. Semantic Technologies for Intelligent Data Access – 11th Int. Summer School Tutorial Lectures (RW), volume 9203, 218–307.  Springer.
  * Bienvenu, Cima, and Gutiérrez-Basulto 2022 Bienvenu, M.; Cima, G.; and Gutiérrez-Basulto, V.  2022\.  LACE: A logical approach to collective entity resolution.  In Proc. of the 41st ACM SIGACT SIGMOD SIGAI Symp. on Principles of Database Systems (PODS), 379–391.  ACM Press.
  * Burdick et al. 2016 Burdick, D.; Fagin, R.; Kolaitis, P. G.; Popa, L.; and Tan, W.  2016\.  A declarative framework for linking entities.  ACM Trans. Database Syst. 41(3):17:1–17:38.
  * Burdick et al. 2019 Burdick, D.; Fagin, R.; Kolaitis, P. G.; Popa, L.; and Tan, W.  2019\.  Expressive power of entity-linking frameworks.  J. Comput. Syst. Sci. 100:44–69.
  * Calautti and Pieris 2021 Calautti, M., and Pieris, A.  2021\.  Semi-oblivious chase termination: The sticky case.  Theoretical Computer Science 65(1):84–121.
  * Calì et al. 2004 Calì, A.; Calvanese, D.; De Giacomo, G.; and Lenzerini, M.  2004\.  Data integration under integrity constraints.  Information Systems 29:147–163.
  * Calì, Gottlob, and Kifer 2013 Calì, A.; Gottlob, G.; and Kifer, M.  2013\.  Taming the infinite chase: Query answering under expressive relational constraints.  J. of Artificial Intelligence Research 48:115–174.
  * Calì, Gottlob, and Lukasiewicz 2009 Calì, A.; Gottlob, G.; and Lukasiewicz, T.  2009\.  A general Datalog-based framework for tractable query answering over ontologies.  In Proc. of the 28th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 77–86.
  * Calvanese et al. 2007 Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R.  2007\.  Tractable reasoning and efficient query answering in description logics: The DL-Lite family.  J. of Automated Reasoning 39(3):385–429.
  * Calvanese et al. 2018 Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R.  2018\.  Ontology-based data access and integration.  In Liu, L., and Özsu, M. T., eds., Encyclopedia of Database Systems, Second Edition. Springer.
  * Cuenca Grau et al. 2013 Cuenca Grau, B.; Horrocks, I.; Krötzsch, M.; Kupke, C.; Magka, D.; Motik, B.; and Wang, Z.  2013\.  Acyclicity notions for existential rules and their application to query answering in ontologies.  J. of Artificial Intelligence Research 47:741–808.
  * Deutsch, Nash, and Remmel 2008 Deutsch, A.; Nash, A.; and Remmel, J. B.  2008\.  The chase revisited.  In Proc. of the 27th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 149–158.  ACM Press.
  * Doan, Halevy, and Ives 2012 Doan, A.; Halevy, A. Y.; and Ives, Z. G.  2012\.  Principles of Data Integration.  Morgan Kaufmann.
  * Fagin et al. 2005 Fagin, R.; Kolaitis, P. G.; Miller, R. J.; and Popa, L.  2005\.  Data exchange: Semantics and query answering.  Theoretical Computer Science 336(1):89–124.
  * Fan 2008 Fan, W.  2008\.  Dependencies revisited for improving data quality.  In Lenzerini, M., and Lembo, D., eds., Proc. of the 27th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 159–170.  ACM Press.
  * Grahne and Onet 2018 Grahne, G., and Onet, A.  2018\.  Anatomy of the chase.  Fundamenta Informaticae 157(3):221–270.
  * Johnson and Klug 1984 Johnson, D. S., and Klug, A. C.  1984\.  Testing containment of conjunctive queries under functional and inclusion dependencies.  J. of Computer and System Sciences 28(1):167–189.
  * Krötzsch, Marx, and Rudolph 2019 Krötzsch, M.; Marx, M.; and Rudolph, S.  2019\.  The power of the terminating chase (invited talk).  In Proc. of the 22nd Int. Conf. on Database Theory (ICDT), volume 127 of LIPIcs, 3:1–3:17.
  * Lenzerini 2002 Lenzerini, M.  2002\.  Data integration: A theoretical perspective.  In Proc. of the 21st ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 233–246.
  * Lutz, Toman, and Wolter 2009 Lutz, C.; Toman, D.; and Wolter, F.  2009\.  Conjunctive query answering in the description logic $\mathcal{EL}$ using a relational database system.  In Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI), 2070–2075.
  * Marnette 2009 Marnette, B.  2009\.  Generalized schema-mappings: from termination to tractability.  In Paredaens, J., and Su, J., eds., Proc. of the 28th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems (PODS), 13–22.  ACM Press.
  * Papadakis et al. 2021 Papadakis, G.; Ioannou, E.; Thanos, E.; and Palpanas, T.  2021\.  The Four Generations of Entity Resolution.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers.

## EXAMPLE OF A TERMINATING CHASE SEQUENCE

We now show a complete execution of the chase procedure in our ongoing
example.

######  Example 13.

Consider the KB $\mathcal{K}=(\mathcal{T},\mathbf{D})$ of Examples 1 and 2,
which we report below for the the sake of presentation:

$\displaystyle\begin{array}[]{ll}(r_{1})&\mathit{CI}(p_{1},\mathit{name}_{1},\mathit{phone}_{1})\wedge\mathit{CI}(p_{2},\mathit{name}_{2},\mathit{phone}_{2})\wedge\\\
&\mathit{JaccSim}(\mathit{name}_{1},\mathit{name}_{2},0.6)\rightarrow
p_{1}=p_{2}\\\
(r_{2})&\mathit{CI}(p,\mathit{name}_{1},\mathit{phone}_{1})\wedge\mathit{CI}(p,\mathit{name}_{2},\mathit{phone}_{2})\\\
&\rightarrow\mathit{name}_{1}=\mathit{name}_{2}\\\
(r_{3})&\mathit{CI}(p,\mathit{name}_{1},\mathit{phone}_{1})\wedge\mathit{CI}(p,\mathit{name}_{2},\mathit{phone}_{2})\\\
&\rightarrow\mathit{phone}_{1}=\mathit{phone}_{2}\\\
(r_{4})&\mathit{CI}(p,\mathit{name},\mathit{phone})\rightarrow\mathit{Emp}(p,\mathit{comp})\wedge\mathit{CEO}(\mathit{comp},\mathit{dir})\\\
(r_{5})&\mathit{Emp}(p,\mathit{comp}_{1})\wedge\mathit{Emp}(p,\mathit{comp}_{2})\rightarrow\mathit{comp}_{1}=\mathit{comp}_{2}\\\
(r_{6})&\mathit{CI}(p_{1},\mathit{name}_{1},\mathit{phone})\wedge\mathit{CI}(p_{2},\mathit{name}_{2},\mathit{phone})\\\
&\rightarrow\mathit{SameHouse}(p_{1},p_{2},\mathit{phone})\end{array}$
$\displaystyle\begin{array}[]{llll}(g_{1})&\mathit{CI}(\textnormal{{Doe}}_{1},\texttt{J.
Doe},\texttt{358})&~{}~{}~{}(g_{4})&\mathit{Emp}(\textnormal{{Doe}}_{2},\textnormal{{Yahoo}})\\\
(g_{2})&\mathit{CI}(\textnormal{{Doe}}_{2},\texttt{John
Doe},\texttt{635})&~{}~{}~{}(g_{5})&\mathit{Emp}(\textnormal{{Doe}}_{3},\textnormal{{IBM}})\\\
(g_{3})&\mathit{CI}(\textnormal{{Doe}}_{3},\texttt{Mary
Doe},\texttt{358})&~{}~{}~{}(g_{6})&\mathit{CEO}(\textnormal{{Yahoo}},\textnormal{{Doe}}_{1})\end{array}$

As said, interpretation $\mathcal{I}$ of Example 3 is the base instance
$\mathcal{I}^{\mathbf{D}}$ for $\mathcal{K}$. Again, we report it below for
convenience.

$\begin{array}[]{ll}(d_{1})\mathit{CI}([\textnormal{{Doe}}_{1}],\\{\texttt{J.
Doe}\\},\\{\texttt{358}\\})&(d_{4})\mathit{Emp}([\textnormal{{Doe}}_{2}],[\textnormal{{Yahoo}}])\\\
(d_{2})\mathit{CI}([\textnormal{{Doe}}_{2}],\\{\texttt{John
Doe}\\},\\{\texttt{635}\\})&(d_{5})\mathit{Emp}([\textnormal{{Doe}}_{3}],[\textnormal{{IBM}}])\\\
(d_{3})\mathit{CI}([\textnormal{{Doe}}_{3}],\\{\texttt{Mary
Doe}\\},\\{\texttt{358}\\})&(d_{6})\mathit{CEO}([\textnormal{{Yahoo}}],[\textnormal{{Doe}}_{1}])\end{array}$

A possible chase sequence is the one composed by the following chase steps:

Step 1:
$\mathcal{I}^{\mathbf{D}}\xrightarrow[]{r_{4},\mu_{0}}\mathcal{I}_{1}$, where
$\mu_{0}$ is such that $\mu_{0}(\mathsf{body}(r_{4}))=\\{d_{3}\\}$. The
resulting instance $\mathcal{I}_{1}$ contains the facts $d_{1}$-$d_{6}$, as
well as following facts:

$\displaystyle\begin{array}[]{ll}(d_{7})\mathit{Emp}([\textnormal{{Doe}}_{3}],[\textnormal{{e}}_{1}^{\bot}]),&(d_{8})\mathit{CEO}([\textnormal{{e}}_{1}^{\bot}],[\textnormal{{e}}_{2}^{\bot}]).\end{array}$

Step 2: $\mathcal{I}_{1}\xrightarrow[]{r_{1},\mu_{1}}\mathcal{I}_{2}$, where
$\mu_{1}$ is such that
$\mu_{1}(\mathsf{body}(r_{1}))=\\{d_{1},d_{2},\mathit{JaccSim}(\\{\texttt{J.
Doe}\\},\\{\texttt{John Doe}\\},\\{0.6\\})$. The resulting instance
$\mathcal{I}_{2}$ contains the facts $d_{3}$, $d_{5}$, $d_{7}$, and $d_{8}$,
as well as the following facts:

$\displaystyle\begin{array}[]{ll}(d_{1})\rightarrow(d_{9})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{J.
Doe}\\},\\{\texttt{358}\\})\\\
(d_{2})\rightarrow(d_{10})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{John
Doe}\\},\\{\texttt{635}\\})\\\
(d_{4})\rightarrow(d_{11})&\mathit{Emp}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],[\textnormal{{Yahoo}}])\\\
(d_{6})\rightarrow(d_{12})&\mathit{CEO}([\textnormal{{Yahoo}}],[\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}])\\\
\end{array}$

Step 3: $\mathcal{I}_{2}\xrightarrow[]{r_{2},\mu_{2}}\mathcal{I}_{3}$, where
$\mu_{2}$ is such that $\mu_{2}(\mathsf{body}(r_{2}))=\\{d_{9},d_{10}\\}$. The
resulting instance $\mathcal{I}_{3}$ contains the facts $d_{3}$, $d_{11}$,
$d_{5}$, $d_{12}$, $d_{7}$, $d_{8}$, as well as the following facts:

$\displaystyle\begin{array}[]{ll}(d_{9})\rightarrow(d_{13})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{J.
Doe,John Doe}\\},\\{\texttt{358}\\})\\\
(d_{10})\rightarrow(d_{14})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{J.
Doe,John Doe}\\},\\{\texttt{635}\\})\\\ \end{array}$

Step 4: $\mathcal{I}_{3}\xrightarrow[]{r_{3},\mu_{4}}\mathcal{I}_{4}$, where
$\mu_{3}$ is such that $\mu_{3}(\mathsf{body}(r_{3}))=\\{d_{13},d_{14}\\}$.
The resulting instance $\mathcal{I}_{4}$ contains the fact $d_{3}$, $d_{11}$,
$d_{5}$, $d_{12}$, $d_{7}$, $d_{8}$, as well as the following fact:

$\displaystyle\begin{array}[]{ll}(d_{13}),(d_{14})\rightarrow(d_{15})&\mathit{CI}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],\\{\texttt{J.
Doe,John Doe}\\},\\\ &~{}~{}\\{\texttt{358},\texttt{635}\\})\end{array}$

Note that $d_{15}$ replaces facts $d_{13}$ and $d_{14}$ of $\mathcal{I}_{3}$.

Step 5: $\mathcal{I}_{4}\xrightarrow[]{r_{5},\mu_{5}}\mathcal{I}_{5}$, where
$\mu_{5}$ is such that $\mu_{5}(\mathsf{body}(r_{5}))=\\{d_{5},d_{7}\\}$. The
resulting instance $\mathcal{I}_{5}$ contains facts $d_{14}$, $d_{3}$,
$d_{11}$, $d_{12}$ plus the facts:

$\displaystyle\begin{array}[]{ll}(d_{5}),(d_{7})\rightarrow(d_{16})&\mathit{Emp}([\textnormal{{Doe}}_{3}],[\textnormal{{IBM}},\textnormal{{e}}_{1}^{\bot}])\\\
(d_{8})\rightarrow(d_{17})&\mathit{CEO}([\textnormal{{IBM}},\textnormal{{e}}_{1}^{\bot}],[\textnormal{{e}}_{2}^{\bot}])\end{array}$

Note that $d_{16}$ replaces facts $d_{5}$ and $d_{7}$ of $\mathcal{I}_{4}$.

Step 6: $\mathcal{I}_{5}\xrightarrow[]{r_{6},\mu_{6}}\mathcal{I}_{6}$, where
$\mu_{6}$ is such that $\mu_{6}(\mathsf{body}(r_{6}))=\\{d_{14},d_{3}\\}$. The
resulting instance $\mathcal{I}_{6}$ contains the same facts as
$\mathcal{I}_{5}$ plus the following fact

$\displaystyle\begin{array}[]{ll}(d_{18})&\mathit{SameHouse}([\textnormal{{Doe}}_{1},\textnormal{{Doe}}_{2}],[\textnormal{{Doe}}_{3}],\\{\texttt{358}\\})\end{array}$

Step 7: $\mathcal{I}_{6}\xrightarrow[]{r_{6},\mu_{7}}\mathcal{I}_{7}$, where
$\mu_{7}$ is such that $\mu_{7}(\mathsf{body}(r_{6}))=\\{d_{14},d_{3}\\}$ (as
for step 6, but in this case $d_{14}$ is the image of the second fact in