∎

11institutetext: Dominique Laurent 22institutetext: ETIS Laboratory - ENSEA,
CY Cergy Paris University, CNRS
F-95000 Cergy-Pontoise, France
<EMAIL_ADDRESS>Nicolas Spyratos 44institutetext:
LISN Laboratory - University Paris-Saclay, CNRS
F-91405 Orsay, France
<EMAIL_ADDRESS>

Acknowledgment: Work conducted while the second author was visiting at FORTH
Institute of Computer Science, Crete, Greece (https://www.ics.forth.gr/)

# Handling Inconsistencies in Tables with Nulls and Functional Dependencies

Dominique Laurent  Nicolas Spyratos

###### Abstract

In this paper we address the problem of handling inconsistencies in tables
with missing values (also called nulls) and functional dependencies. Although
the traditional view is that table instances must respect all functional
dependencies imposed on them, it is nevertheless relevant to develop theories
about how to handle instances that violate some dependencies. Regarding
missing values, we make no assumptions on their existence: a missing value
exists only if it is inferred from the functional dependencies of the table.

We propose a formal framework in which each tuple of a table is associated
with a truth value among the following: true, false, inconsistent or unknown;
and we show that our framework can be used to study important problems such as
consistent query answering, table merging, and data quality measures - to
mention just a few. In this paper, however, we focus mainly on consistent
query answering, a problem that has received considerable attention during the
last decades.

The main contributions of the paper are the following: (a) we introduce a new
approach to handle inconsistencies in a table with nulls and functional
dependencies, (b) we give algorithms for computing all true, inconsistent and
false tuples, (c) we investigate the relationship between our approach and
Four-valued logic in the context of data merging, and (d) we give a novel
solution to the consistent query answering problem and compare our solution to
that of table repairs.

###### Keywords:

Inconsistent database . Functional dependency . Null value . Data merging .
Consistent query answering

##  1 Introduction

In several applications today we encounter tables with missing values and
functional dependencies. Such a table is often the result of merging two or
more other tables coming from different sources. Typical examples include
recording the results of collaborative work, merging of tables during data
staging in data warehouses or checking the consistency of a relational
database.

As an example of collaborative work consider two groups of researchers each
studying three objects found in an archaeological site. The researchers of
each group record in a table data regarding the following attributes of each
object:

  * •

Identifier (here of the form $i_{n}$ where $n$ is an integer, distinct objects
being associated with distinct identifiers)

  * •

Kind (such as statue, weapon, …)

  * •

Material from which the object is made (such as iron, bronze, marble, …)

  * •

Century in which the object is believed to have been made.

At the end of their work each group submits their findings to the site
coordinator in the form of a table as shown in Figure 1 (tables $D_{1}$ and
$D_{2}$). Each row of a table contains data recorded for a single object. For
example, the row $(i_{1},statue,marble,1.BC)$ means that object $i_{1}$ is a
statue made of marble and believed to have been made in the first century
before Christ. Similarly the row $(i_{2},statue,,2.BC)$ means that object
$i_{2}$ is a statue of unknown material, believed to have been made during the
second century before Christ. Note that, in this tuple, there is a missing
value, meaning that the material from which object $i_{2}$ is made could not
be determined.

$D_{1}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ |  | $m^{\prime}$ |
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ |
| $i_{3}$ |  | $m$ |

$D_{2}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ |  | $c$
| $i_{2}$ | $k^{\prime}$ |  | $c^{\prime}$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ |
| $i_{3}$ | $k^{\prime}$ |  |

$D$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ |  | $m^{\prime}$ |
| $i_{1}$ | $k$ |  | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ |
| $i_{2}$ | $k^{\prime}$ |  | $c^{\prime}$
| $i_{3}$ |  | $m$ |
| $i_{3}$ | $k^{\prime}$ |  |

Figure 1: The tables prepared by the two groups and the merged table

Now, the data contained in the two tables can be merged into a single table
$D$ containing all tuples from the two tables, without duplicates, as shown in
Figure 1 (table $D$). In doing this merging, we may have discrepancies between
tuples of $D$. For example, object $i_{1}$ appears in $D$ as being made from
two different materials; and object $i_{2}$ appears as made from two different
materials and in two different centuries. This kind of discrepancies may lead
to ‘inconsistencies’ that should be identified by the site coordinator and
resolved in cooperation with the researchers of the two groups.

It should be obvious from this example that the merging of two or more tables
into a single table more often than not results in inconsistencies even if the
individual tables are each consistent. For example, although each of the
tables $D_{1}$ and $D_{2}$ shown in Figure 1 satisfies the functional
dependencies $Id\to K$ and $Id\to C$, the merged table $D$ does not satisfy
$Id\to C$.

A similar situation arises in data warehouses where one tries to merge views
of the underlying sources into a single materialized view to be stored in the
data warehouse.

As a last example, in a relational database, although each table may satisfy
its functional dependencies, the database as a whole may violate some
dependencies. To determine whether the database is consistent with its
dependencies, one proceeds as follows: all tables are merged by placing their
tuples into a single universal table $D$ possibly with missing values (under
certain assumptions discussed in Vardi88 ); then all functional dependencies
are applied on $D$ through the well known chase algorithm FaginMU82 ; Ullman .
If the algorithm terminates successfully (i.e., no inconsistency is detected)
then the database is consistent; otherwise the algorithm stops when a first
inconsistency is detected and the database is declared inconsistent.

So in general the question is: what should we do when a table is inconsistent?
There are roughly three approaches: $(a)$ reject the table, $(b)$ try to
correct or ‘repair’ it so that to make it consistent (and therefore be able to
work with the repaired table) and $(c)$ keep the table as is but make sure you
know which part is consistent and which is not.

The first approach is followed by database theorists when checking database
consistency, as explained above. This approach is clearly not acceptable in
practice as the universal table might contain a consistent set of tuples that
can be useful to users (e.g., users can still query the consistent part of the
table).

The second approach tries to alleviate the impact of inconsistent data on the
answers to a query by introducing the notion of repair: a repair is a
minimally different consistent instance of the table and an answer is
consistent if it is present in every repair. This approach, referred to as
‘consistent query answering’, has motivated important research efforts during
the past two decades and is still the subject of current research. The reader
is referred to Section 6 for a brief overview of the related literature.
However, this approach is always difficult to implement due to important
issues related to computational complexity and/or to semantics (there is still
no consensus regarding the definition of ‘consistent answer’).

In our work we follow the third approach that is, we keep inconsistencies in
the table but we determine which part of the table is consistent and which is
not. More specifically, we use set theoretic semantics for tuples and
functional dependencies that allow us to associate each tuple of the table
with one truth value among the following: true, false, inconsistent or
unknown. By doing so we can study a number of important problems including in
particular the problem of consistent query answering, and the definition of
data quality measures.

Regarding consistent query answering, our model offers a fundamentally
different and direct solution to the problem: the consistent answer is
obtained by simply retrieving true tuples that fit the query requirements.

Moreover our approach offers the possibility of defining meaningful data
quality measures. For example if a table contains a hundred tuples of which
only five are true while the remaining ones are inconsistent, then the quality
of data contained in the table is five percent. Since we have polynomial
algorithms for computing all true, false and inconsistent tuples, we can
define several quality measures of the data contained in a table, inspired by
the work in Parisi19 . We can then use such measures to accompany query
answers so that users are informed of the quality of the answer they receive
(e.g., getting an answer from a table with ninety five per cent of true tuples
is more reliable than if the table contained only five per cent of true
tuples). However, defining and studying such measures lies outside the goals
of the present paper. In this paper we focus on one important application of
our approach, namely consistent query answering. A complete account of data
quality measures will be reported in a future paper.

The main contributions of the present paper can be summarized as follows:

  1. 1.

We introduce a new approach to handle inconsistencies in a table with nulls
and functional dependencies; we do so by adapting the set theoretic semantics
of Spyratos87  to our context and by extending the chase algorithm so that all
inconsistencies are accounted for in the table.

  2. 2.

We give polynomial algorithms in the size of the table for computing all true
and all inconsistent tuples in the table.

  3. 3.

We investigate the relationship of our approach with Four-valued logic in the
context of data merging.

  4. 4.

We propose a novel approach for consistent query answering and we investigate
how our approach relates to existing approaches.

The paper is organized as follows: In Section 2 we recall basic definitions
and notations regarding tables and we introduce the set theoretic semantics
that we use in our work. In Section 3 we give definitions and properties
regarding the truth values that we associate with tuples. In Section 4 we
study computational issues and give algorithms for computing the truth values
of tuples. In Section 5, we show how our approach relates to Four-value logic
when merging two or more tables. In Section 6 we present a novel solution to
the problem of consistent query answering and compare it to existing
approaches. Section 7 contains concluding remarks and suggestions for further
research.

##  2 The Model

In this section we present the basic definitions regarding tuples and tables
as well as the set theoretic semantics that we use for tuples and functional
dependencies. Our approach builds upon earlier work on the partition model
Spyratos87 .

###  2.1 The Partition Model Revisited

Following Spyratos87 , we consider a universe $U=\\{A_{1},\ldots,A_{n}\\}$ in
which every attribute $A_{i}$ is associated with a set of atomic values called
the domain of $A_{i}$ and denoted by $dom(A_{i})$. An element of
$\bigcup_{A\in U}dom(A)$ is called a domain constant or a constant. We call
relation schema (or simply schema) any nonempty subset of $U$ and we denote it
by the concatenation of its elements; for example $\\{A_{1},A_{2}\\}$ is
simply denoted by $A_{1}A_{2}$. Similarly, the union of schemas $S_{1}$ and
$S_{2}$ is denoted as $S_{1}S_{2}$ instead of $S_{1}\cup S_{2}$.

We define a tuple $t$ to be a partial function from $U$ to $\bigcup_{A\in
U}dom(A)$ such that, for every $A$ in $U$, if $t$ is defined over $A$ then
$t(A)$ belongs to $dom(A)$. The domain of definition of $t$ is called the
schema of $t$, denoted by $sch(t)$. We note that tuples in our approach
satisfy the First Normal Form Ullman  in the sense that each tuple component
is an atomic value from an attribute domain.

Regarding notation, we follow the usual convention that, whenever possible,
lower-case characters denote domain constants and upper-case characters denote
the corresponding attributes. Following this convention the schema of a tuple
$t=ab$ is $AB$ and more generally, we denote the schema of $t$ as $T$.

Assuming that the schema of a tuple $t$ is understood, $t$ is denoted by the
concatenation of its values, that is: $t=a_{i_{1}}\ldots a_{i_{k}}$ means that
for every $j=1,\ldots,k$, $t(A_{i_{j}})=a_{i_{j}}$, $a_{i_{j}}$ is in
$dom(A_{i_{j}})$, and $sch(t)=A_{i_{1}}\ldots A_{i_{k}}$.

We assume that for any distinct attributes $A$ and $B$, we have either
$dom(A)=dom(B)$ or $dom(A)\cap dom(B)=\emptyset$. However, this may lead to
ambiguity when two attributes have the same domain. Ambiguity can be avoided
by prefixing each value of an attribute domain with the attribute name. For
example, if $dom(A)=dom(B)$ we can say ‘an $A$-value $a$’ to mean that $a$
belongs to $dom(A)$, and ‘a $B$-value $a$’ to mean that $a$ belongs to
$dom(B)$. In order to keep the notation simple we shall omit prefixes whenever
no ambiguity is possible.

Denoting by ${\cal T}$ the set of all tuples that can be built up given a
universe $U$ and the corresponding attribute domains, a table $D$ is a finite
sub-set of ${\cal T}$ where duplicates are not allowed.

Given a tuple $t$, for every $A$ in $sch(t)$, $t(A)$ is also denoted by $t.A$
and more generally, for every subset $S$ of $sch(t)$ the restriction of $t$ to
$S$, also called sub-tuple of $t$, is denoted by $t.S$. In other words, if
$S\subseteq sch(t)$, $t.S$ is the tuple such that $sch(t.S)=S$ and for every
$A$ in $S$, $(t.S).A=t.A$.

Moreover, $\sqsubseteq$ denotes the ‘sub-tuple’ relation, defined over ${\cal
T}$ as follows: for any tuples $t_{1}$ and $t_{2}$, $t_{1}\sqsubseteq t_{2}$
holds if $t_{1}$ is a sub-tuple of $t_{2}$. It is thus important to keep in
mind that whenever $t_{1}\sqsubseteq t_{2}$ holds, it is understood that
$sch(t_{1})\subseteq sch(t_{2})$ also holds.

The relation $\sqsubseteq$ is clearly a partial order over ${\cal T}$. Given a
table $D$, the set of all sub-tuples of the tuples in $D$ is called the lower
closure of $D$ and it is defined by: ${\sf LoCl}(D)=\\{q\in{\cal
T}~{}|~{}(\exists t\in D)(q\sqsubseteq t)\\}$. We shall call a table reduced
if it contains only maximal tuples (i.e., if no tuple in the set is sub-tuple
of some other tuple in the set).

The notion of ${\cal T}$-mapping, as defined below, generalizes that of
interpretation defined in Spyratos87 .

###### Definition 1

Let $U$ be a universe. A ${\cal T}$-mapping is a mapping $\mu$ defined from
$\bigcup_{A\in U}dom(A)$ to $2^{\mathbb{N}}$. A ${\cal T}$-mapping $\mu$ can
be extended to the set ${\cal T}$ as follows: for every $t=a_{i_{1}}\ldots
a_{i_{k}}$ in ${\cal T}$, $\mu(t)=\mu(a_{i_{1}})\cap\ldots\cap\mu(a_{i_{k}})$.

A ${\cal T}$-mapping $\mu$ is an interpretation if $\mu$ satisfies the
partition constraint stating that for every $A$ in $U$, and for all distinct
$a$ and $a^{\prime}$ in $dom(A)$, $\mu(a)\cap\mu(a^{\prime})=\emptyset$.

We emphasize that in Spyratos87  interpretations provide the basic tool for
defining true tuples: a tuple $t$ is said to be true in an interpretation
$\mu$ if $\mu(t)$ is nonempty.

To see the intuition behind this definition consider a relational table $D$
over $U$ and suppose that each tuple is associated with a unique identifier,
say an integer. Now, for every $A$ in $U$ and every $a$ in $dom(A)$, define
$\mu(a)$ to be the set of all identifiers of the tuples in $D$ containing $a$.
Then $\mu$ is an interpretation as it satisfies the partition constraint.
Indeed, due to the fact that, for every attribute $A$ in $U$, a tuple $t$ can
not have more than one $A$-value, it is then impossible that
$\mu(a)\cap\mu(a^{\prime})$ be nonempty for any distinct values $a$,
$a^{\prime}$ in $dom(A)$.

Incidentally, if for every $A$ in $U$ we denote by $dom^{*}(A)$ the set of all
$A$-values such that $\mu(a)\neq\emptyset$, then the set $\\{\mu(a)~{}|~{}a\in
dom^{*}(A)\\}$ is a partition of $\bigcup_{a\in dom^{*}(A)}\mu(a)$ (whence the
name “partition model”). The following example illustrates this important
feature.

###### Example 1

Considering $U=\\{A,B,C\\}$ and
$D=\\{ab,bc,ac,a^{\prime}b^{\prime},b^{\prime}c^{\prime},abc\\}$, the tuples
in $D$ can be respectively assigned the identifiers $1$, $2$, $3$, $4$, $5$
and $6$. In that case, we have $\mu(a)=\\{1,3,6\\}$,
$\mu(a^{\prime})=\\{4\\}$, $\mu(b)=\\{1,2,6\\}$, $\mu(b^{\prime})=\\{4,5\\}$,
$\mu(c)=\\{2,3,6\\}$, $\mu(c^{\prime})=\\{5\\}$, and $\mu(\alpha)=\emptyset$
for any constant $\alpha$ different than $a$, $a^{\prime}$, $b$, $b^{\prime}$,
$c$ and $c^{\prime}$.

It is clear that the ${\cal T}$-mapping $\mu$ is an interpretation and, since
$dom^{*}(A)$, $dom^{*}(B)$ and $dom^{*}(C)$ are respectively equal to
$\\{a,a^{\prime}\\}$, $\\{b,b^{\prime}\\}$ and $\\{c,c^{\prime}\\}$, it is
easy to see that $\\{\mu(\alpha)~{}|~{}\alpha\in dom^{*}(A)\\}$ is a partition
of $\\{1,3,4,6\\}$, $\\{\mu(\beta)~{}|~{}\beta\in dom^{*}(B)\\}$ is a
partition of $\\{1,2,4,5,6\\}$, and $\\{\mu(\gamma)~{}|~{}\gamma\in
dom^{*}(C)\\}$ is a partition of $\\{2,3,5,6\\}$.

Moreover, extending $\mu$ to non unary tuples yields the following regarding
the tuples in $D$: $\mu(ab)=\\{1,6\\}$, $\mu(bc)=\\{2,6\\}$,
$\mu(ac)=\\{3,6\\}$, $\mu(a^{\prime}b^{\prime})=\\{4\\}$,
$\mu(b^{\prime}c^{\prime})=\\{5\\}$, and $\mu(abc)=\\{6\\}$. $\Box$

Summarizing our discussion, when dealing with consistent tables in Spyratos87
, only interpretations are relevant. In the present work, we follow the same
idea, but we also extend the work of Spyratos87  so that we can deal with
inconsistencies. As we shall see, non satisfaction of the partition constraint
in Definition 1 is the key criterion to characterize inconsistent tuples.

###  2.2 Functional Dependencies

The notion of functional dependency in our approach is defined as in
Spyratos87 .

###### Definition 2

Let $U$ be a universe. A functional dependency is an expression of the form
$X\to Y$ where $X$ and $Y$ are nonempty sub-sets of $U$.

A ${\cal T}$-mapping $\mu$ satisfies $X\to Y$, denoted by $\mu\models X\to Y$,
if for all tuples $x$ and $y$, respectively over $X$ and $Y$, the following
holds: if $\mu(x)\cap\mu(y)\neq\emptyset$ then $\mu(x)\subseteq\mu(y)$.

Based on Definition 2, for all $X$ and $Y$ such that $X\cap Y=\emptyset$, and
for every ${\cal T}$-mapping $\mu$, the following holds:

$\mu\models X\to Y$ if and only if $\mu\models X\to A$ for every $A$ in $Y$.

This is so because, for every $x$ and $y$ such that
$\mu(x)\cap\mu(y)\neq\emptyset$, $\mu(x)\subseteq\mu(y)$ holds if and only if
$\mu(x)\subseteq\mu(a)$ holds for every constant $a$ in $y$.

Therefore without loss of generality we can assume that all functional
dependencies are of the form $X\to A$ where $A$ is an attribute not in $X$.
Under this assumption, we consider pairs $\Delta=(D,{\cal FD})$ where $D$ is a
table over $U$ and ${\cal FD}$ a set of functional dependencies over $U$, and
we say that a ${\cal T}$-mapping $\mu$ satisfies $\Delta$, denoted by
$\mu\models\Delta$, if $(i)$ for every $t$ in $D$, $\mu(t)\neq\emptyset$, and
$(ii)$ $\mu$ satisfies every $X\to A$ in ${\cal FD}$.

To see how our notion of functional dependency relates to the standard one in
relational databases Ullman , recall first that a relation $r$ over universe
$U$ satisfies $X\to A$ if for all tuples $t$ and $t^{\prime}$ in $r$ such that
$t.X=t^{\prime}.X$, we have $t.A=t^{\prime}.A$.

In our approach, let $\Delta=(D,{\cal FD})$ and consider two tuples $t$ and
$t^{\prime}$ in $D$ such that $XA$ is a subset of $sch(t)$ and of
$sch(t^{\prime})$ and let $t.X=t^{\prime}.X=x$. Then for every ${\cal
T}$-mapping $\mu$ such that $\mu\models\Delta$, $\mu(t)$ and $\mu(t^{\prime})$
are nonempty, implying that $\mu(x)\cap\mu(t.A)$ and
$\mu(x)\cap\mu(t^{\prime}.A)$ are also nonempty. By Definition 2, this implies
that $\mu(x)$ is a sub-set of $\mu(t.A)$ and of $\mu(t^{\prime}.A)$. As a
consequence, assuming that $t.A\neq t^{\prime}.A$ (i.e., that $X\to A$ is not
satisfied in the sense of the relational model), means that
$\mu(t.A)\cap\mu(t^{\prime}.A)$ is nonempty, and therefore $\mu$ can not be an
interpretation.

Therefore if we restrict ${\cal T}$-mappings to be interpretations then the
notion of functional dependency satisfaction in our approach is the same as
that of relational databases. As we shall see, this observation supports the
notion of consistency for $\Delta$, to be given later (in Definition 4).

Given $\Delta=(D,{\cal FD})$ and tuples $t$, $t^{\prime}$, $t^{\prime\prime}$,
the following notations are extensively used in the remainder of the paper.

$-$ $\Delta\vdash t$, denotes that if $\mu\models\Delta$ then
$\mu(t)\neq\emptyset$.
$-$ $\Delta\vdash(t\sqcap t^{\prime})$, denotes that if $\mu\models\Delta$
then $\mu(t)\cap\mu(t^{\prime})\neq\emptyset$.
$-$ $\Delta\vdash(t\preceq t^{\prime})$ denotes that if $\mu\models\Delta$
then $\mu(t)\subseteq\mu(t^{\prime})$.
$-$ $\Delta\vdash(t\preceq t^{\prime}\sqcap t^{\prime\prime})$ denotes that if
$\mu\models\Delta$ then
$\mu(t)\subseteq\mu(t^{\prime})\cap\mu(t^{\prime\prime})$.

Given $\Delta=(D,{\cal FD})$, we now build a particular ${\cal T}$-mapping
$\mu$ such that $\mu\models\Delta$ as follows: Let
$\left(\mu_{i}\right)_{i\geq 0}$ be the sequence defined by the steps below:

  1. 1.

Associate each tuple $t$ with an identifier, $id(t)$, called the tuple
identifier of $t$ (this can be an integer that identifies $t$ uniquely).

  2. 2.

Let $\mu_{0}$ be the mapping defined for every domain constant $a$ by:
$\mu_{0}(a)=\\{id(t)~{}|~{}t\in D\mbox{ and }a\sqsubseteq t\\}$.

  3. 3.

While there exists $X\to A$ in ${\cal FD}$, $x$ over $X$ and $a$ in $dom(A)$
such that $\mu_{i}(xa)\neq\emptyset$ and $\mu_{i}(x)\not\subseteq\mu_{i}(a)$,
define $\mu_{i+1}$ by: $\mu_{i+1}(a)=\mu_{i}(a)\cup\mu_{i}(x)$ and
$\mu_{i+1}(\alpha)=\mu_{i}(\alpha)$ for any other constant $\alpha$.

###### Lemma 1

For every $\Delta=(D,{\cal FD})$, the sequence $\left(\mu_{i}\right)_{i\geq
0}$ has a unique limit $\mu^{*}$ such that $\mu^{*}\models\Delta$. Moreover:

  1. 1.

For all $a_{1}$ and $a_{2}$ in the same attribute domain $dom(A)$, if
$\mu^{*}(a_{1})\cap\mu^{*}(a_{2})\neq\emptyset$ then there exist $X\to A$ in
${\cal FD}$ and $x$ over $X$ such that $\mu^{*}(x)\neq\emptyset$ and
$\mu^{*}(x)\subseteq\mu^{*}(a_{1})\cap\mu^{*}(a_{2})$.

  2. 2.

For all $\alpha$ and $\beta$, $\Delta\vdash(\alpha\sqcap\beta)$ holds if and
only if $\mu^{*}(\alpha)\cap\mu^{*}(\beta)\neq\emptyset$ holds.

###### Proof

See Appendix A. $\Box$

Given $\Delta=(D,{\cal FD})$, Lemma 1 shows the following:

  1. 1.

There always exists a ${\cal T}$-mapping $\mu$ such that $\mu\models\Delta$.

  2. 2.

When two constants from the same domain have common identifiers with respect
to $\mu^{*}$ then this is due to a functional dependency.

  3. 3.

For every tuple $t$, $\Delta\vdash t$ if and only if
$\mu^{*}(t)\neq\emptyset$.

It is important to note that the ${\cal T}$-mapping $\mu^{*}$ as defined in
Lemma 1 is not necessarily an interpretation as the following example shows.

###### Example 2

Let $U=\\{A,B,C\\}$ and $\Delta=(D,{\cal FD})$ where
$D=\\{ab,bc,abc^{\prime}\\}$ and ${\cal FD}=\\{B\to C\\}$. Associating $ab$,
$bc$ and $abc^{\prime}$ respectively with 1, 2 and 3, $\mu^{*}$ is obtained as
follows:
$\bullet$ First, we have $\mu_{0}(a)=\\{1,3\\}$, $\mu_{0}(b)=\\{1,2,3\\}$,
$\mu_{0}(c)=\\{2\\}$ and $\mu_{0}(c^{\prime})=\\{3\\}$ and
$\mu_{0}(\alpha)=\emptyset$ for any other domain constant $\alpha$.
$\bullet$ Then, considering $B\to C$, we have $\mu_{1}(a)=\\{1,3\\}$,
$\mu_{1}(b)=\mu_{1}(c)=\mu_{1}(c^{\prime})=\\{1,2,3\\}$ and
$\mu_{1}(\alpha)=\emptyset$ for any other domain constant $\alpha$.

Hence, $\mu^{*}=\mu_{1}$ and we remark that
$\mu^{*}(c)\cap\mu^{*}(c^{\prime})\neq\emptyset$, thus that $\mu^{*}$ is not
an interpretation. Nevertheless, as stated by Lemma 1, it is easy to see that
$\mu^{*}\models\Delta$. $\Box$

We note here that the authors of SpyratosL87  use a construction similar to
that of Lemma 1 to define a minimal model of $\Delta$, called ‘query model’,
assuming that $D$ is consistent with ${\cal FD}$.

Now, in order to characterize when $\Delta\vdash(t\preceq a)$ holds, we
introduce the notion of closure of a tuple $t$ in $\Delta$ inspired by the
well known relational notion of closure of a relation scheme with respect to a
set of functional dependencies Ullman .

###### Definition 3

Given a database $\Delta=(D,{\cal FD})$ and a tuple $t$, the closure of $t$ in
$\Delta$ (or closure of $t$ for short, when $\Delta$ is understood), denoted
by $t^{+}$, is the set of all domain constants $a$ such that
$\Delta\vdash(t\preceq a)$ holds.

We notice that, based on Definition 3, for every constant $a$ occurring in a
tuple $t$ (i.e., if $a\sqsubseteq t$ holds) then $a$ is in $t^{+}$, because,
in this case, $\mu(t)\subseteq\mu(a)$ holds for every ${\cal T}$-mapping
$\mu$. However constants not occurring in $t$ may also appear in $t^{+}$ due
to functional dependencies, as shown in the following example.

###### Example 3

Continuing Example 2 where $U=\\{A,B,C\\}$ and $\Delta=(D,{\cal FD})$ with
$D=\\{ab,bc,abc^{\prime}\\}$ and ${\cal FD}=\\{B\to C\\}$, we show that $c$
belongs to $(ab)^{+}$.

Indeed, for every $\mu$ such that $\mu\models\Delta$, we have
$\mu(ab)\subseteq\mu(b)$ (since $b\sqsubseteq ab$) and $\mu(b)\subseteq\mu(c)$
(due to $B\to C$ and the fact that $\mu(b)\cap\mu(c)\neq\emptyset$ must hold).
Hence, by transitivity, $\mu(ab)\subseteq\mu(c)$ holds, implying that
$\Delta\vdash(ab\preceq c)$ holds, which by Definition 3, means that $c$
belongs to $(ab)^{+}$. It should also be noticed that a similar argument shows
that $c^{\prime}$ also belongs to $(ab)^{+}$. $\Box$

Clearly computing the closure directly from its definition is inefficient.
Algorithm 1 gives a method for computing the closure, since the following
lemma states that this algorithm correctly computes the closure.

Algorithm 1 Closure of $t$

0: $\Delta=(D,{\cal FD})$ and a tuple $t$.

0: The closure $t^{+}$ of $t$

1: $\Delta_{t}:=(D_{t},{\cal FD})$ where $D_{t}=D\cup\\{t\\}$

2: $t^{+}:=\\{a~{}|~{}a\sqsubseteq t\\}$

3: while $t^{+}$ changes do

4: for all $X\to A\in{\cal FD}$ do

5: for all $x$ such that for every $b$ in $x$, $b\in t^{+}$ and
$\Delta_{t}\vdash xa$ do

6: $t^{+}:=t^{+}\cup\\{a\\}$

7: return $t^{+}$

###### Lemma 2

Let $\Delta=(D,{\cal FD})$ and $t$ a tuple. Then Algorithm 1 computes
correctly the closure $t^{+}$ of $t$.

###### Proof

See Appendix B. $\Box$

We draw attention on the fact that the database involved in Algorithm 1 is not
$\Delta$ but the database $\Delta_{t}$ that can be seen as $\Delta$ in which
the tuple $t$ has been added.

It should however be noticed that in case $\Delta\vdash t$, this distinction
is not necessary because in this case, for every tuple $q$, $\Delta\vdash q$
holds if and only if $\Delta_{t}\vdash q$ holds. This is a consequence of the
fact that, as seen in Appendix B, if $\Delta\vdash t$ then for every ${\cal
T}$-mapping $\mu$, $\mu\models\Delta$ holds if and only if
$\mu\models\Delta_{t}$.

On the other hand, the following example shows that when $\Delta\not\vdash t$,
the introduction of $\Delta_{t}$ instead of $\Delta$ is necessary for
correctly computing $t^{+}$.

###### Example 4

Let $U=\\{A,B,C\\}$ and $\Delta=(D,{\cal FD})$ where $D=\\{ac,b\\}$ and ${\cal
FD}=\\{A\to B,B\to C\\}$.

It is easy to see that when numbering the tuples in $D$ by $1$ for $ac$ and
$2$ for $b$, the ${\cal T}$-mapping $\mu^{*}$ for $\Delta$ is defined by:
$\mu^{*}(a)=\mu^{*}(c)=\\{1\\}$, $\mu^{*}(b)=\\{2\\}$ and
$\mu^{*}(\alpha)=\emptyset$ for any other constant $\alpha$.

For $t=ab$, we argue that $c$ is in $t^{+}$, that is, for every $\mu$ such
that $\mu\models\Delta$, $\mu(ab)\subseteq\mu(c)$ holds. Indeed, this
trivially holds if $\mu(ab)=\emptyset$ (as is the case with $\mu^{*}$), and
otherwise the following proof can be done:
$\bullet$ As $\mu(ab)\neq\emptyset$, $A\to B$ implies that
$\mu(a)\subseteq\mu(b)$.
$\bullet$ As $\mu(ac)\neq\emptyset$, $\mu(a)\subseteq\mu(b)$ implies
$\mu(bc)\neq\emptyset$. Thus, $\mu(b)\subseteq\mu(c)$, due to $B\to C$.
$\bullet$ Therefore, $\mu(a)\subseteq\mu(c)$, and since
$\mu(ab)\subseteq\mu(a)$, we have $\mu(ab)\subseteq\mu(c)$.

On the other hand, computing $(ab)^{+}$ using a modified version of Algorithm
1 where $\Delta_{t}$ is replaced by $\Delta$ would output $a$ and $b$ in the
closure. It should also be noticed that computing $(ab)^{+}$ using Algorithm 1
is as follows: by the statement on line 2, $a$ and $b$ are inserted into the
closure, and then, since for $t=ab$, $\Delta_{t}\vdash ab$ the above reasoning
shows that $\Delta_{t}\vdash bc$ as well. Therefore, $c$ is inserted into the
closure because the test line 5 succeeds. $\Box$

The following example shows a case where the tuple $t$ of which the closure is
computed is such that $\Delta\vdash t$.

###### Example 5

As seen in Example 2, if $U=\\{A,B,C\\}$ and $\Delta=(D,{\cal FD})$ where
$D=\\{ab,bc,abc^{\prime}\\}$ and ${\cal FD}=\\{B\to C\\}$, $\mu^{*}$ is
defined by: $\mu^{*}(a)=\\{1,3\\}$,
$\mu^{*}(b)=\mu^{*}(c)=\mu^{*}(c^{\prime})=\\{1,2,3\\}$ and
$\mu^{*}(\alpha)=\emptyset$ for any other domain constant $\alpha$.

In this case, the computation of $(ab)^{+}$ according to Algorithm 1 is as
follows:
$\bullet$ As $ab$ is in $D$, $\Delta_{t}=\Delta$. We thus run Algorithm 1 with
$\Delta$ instead of $\Delta_{t}$.
$\bullet$ $(ab)^{+}$ is first set to $\\{a,b\\}$.
$\bullet$ Considering $B\to C$, since $b$ is in $(ab)^{+}$, and since
$\Delta\vdash bc$ and $\Delta\vdash bc^{\prime}$ (this holds because
$\mu^{*}(c)$ and $\mu^{*}(c^{\prime})$ are nonempty), $c$ and $c^{\prime}$ are
inserted in $(ab)^{+}$.

As no further step is processed, $(ab)^{+}=\\{a,b,c,c^{\prime}\\}$, as seen in
Example 3. Thus $\Delta\vdash(ab\preceq c)$ and $\Delta\vdash(ab\preceq
c^{\prime})$ hold, implying $\Delta\vdash(ab\preceq c\sqcap c^{\prime})$.
$\Box$

##  3 Semantics

In this section we provide basic definitions and properties regarding the
truth value associated with a tuple. The following definition is borrowed from
Spyratos87 .

###### Definition 4

$\Delta$ is said to be consistent if there exists an interpretation $\mu$ such
that $\mu\models\Delta$.

Since in our approach, inconsistent tables are not discarded, it is crucial to
be able to provide semantics to any $\Delta=(D,{\cal FD})$, being it
consistent or not. To this end, inspired by Belnap’s Four-valued logic Belnap
, we consider four possible truth values for a given tuple $t$ in $\Delta$.
The notations of truth values for tuples in our approach and their intuitive
meaning are as follows, for a given tuple $t$:

  * •

Truth value ${\tt true}$: $t$ is true in $\Delta$.

  * •

Truth value ${\tt false}$: $t$ is false in $\Delta$. This means that we do not
follow the Closed World Assumption (CWA), according to which any non true
tuple is false Reiter77 .

  * •

Truth value ${\tt inc}$ (i.e., inconsistent): $t$ is true and false in
$\Delta$. This truth value is necessary for ‘safely’ dealing with inconsistent
tuples.

  * •

Truth value ${\tt unkn}$ (i.e., unknown): $t$ is not true, not false and not
inconsistent in $\Delta$. This truth value is necessary for dealing with
tuples not falling in one of the previous three categories.

In order to formalize the exact meaning of these truth values in our approach,
we introduce the following terminology and notation for a given tuple $t$:

  * •

If $\Delta\vdash t$ holds, $t$ is said to be potentially true in $\Delta$.
Notice here that by Lemma 1, $t$ is potentially true if and only if
$\mu^{*}(t)\neq\emptyset$.

  * •

If $\Delta\vdash(t\preceq a\sqcap a^{\prime})$ holds for some distinct $a$ and
$a^{\prime}$ in the same attribute domain, then we use the notation
$\Delta\mid\sim t$, and in this case, $t$ is said to be potentially false to
reflect that $\mu(a)\cap\mu(a^{\prime})$ must be empty for $\mu$ to be an
interpretation. By Definition 3, $\Delta\mid\sim t$ holds if and only if there
exist $a$ and $a^{\prime}$ in the same attribute domain such that $a$ and
$a^{\prime}$ are in $t^{+}$.

Consequently, if a tuple $t$ is such that $\Delta\vdash t$ and $\Delta\mid\sim
t$, then for $\mu$ to be an interpretation, $\mu$ must associate $t$ with a
set expected to be empty and nonempty, which is of course a case of
inconsistency! This explains why, in our approach, ‘potentially true’ and
‘potentially false’, should respectively be understood as ‘true or
inconsistent’ and ‘false or inconsistent’.

Based on this intuition, each tuple is assigned one of the four truth values
according to the following definition.

###### Definition 5

Given $\Delta=(D,{\cal FD})$ and a tuple $t$, the truth value of $t$ in
$\Delta$, denoted by $v_{\Delta}(t)$, is defined as follows:

$-$ $v_{\Delta}(t)={\tt true}$ | if $\Delta\vdash t$ and $\Delta\not\mid\sim t$; $t$ is said to be true in $\Delta$.
---|---
$-$ $v_{\Delta}(t)={\tt false}$ | if $\Delta\not\vdash t$ and $\Delta\mid\sim t$; $t$ is said to be false in $\Delta$.
$-$ $v_{\Delta}(t)={\tt inc}$ | if $\Delta\vdash t$ and $\Delta\mid\sim t$; $t$ is said to be inconsistent in $\Delta$.
$-$ $v_{\Delta}(t)={\tt unkn}$ | if $\Delta\not\vdash t$ and $\Delta\not\mid\sim t$; $t$ is said to be unknown in $\Delta$.

We point out that the four truth values as defined above correspond exactly to
the four truth values defined in the Four-valued logic Belnap . The reader is
referred to Section 5 for more details on this point. We illustrate Definition
5 through the following example.

###### Example 6

As in Example 2, let $U=\\{A,B,C\\}$ and $\Delta=(D,{\cal FD})$ where
$D=\\{ab,bc,abc^{\prime}\\}$ and ${\cal FD}=\\{B\to C\\}$.

It has been seen in Example 5 that $(ab)^{+}=\\{a,b,c,c^{\prime}\\}$. Thus
$\Delta\mid\sim ab$ holds. Moreover, it is easy to see from Example 2 that
$\mu^{*}(ab)\neq\emptyset$, implying that $\Delta\vdash ab$ holds as well. As
a consequence, by Definition 5, $v_{\Delta}(ab)={\tt inc}$, meaning that $ab$
is inconsistent in $\Delta$. We notice that similar arguments hold for $abc$,
$abc^{\prime}$, $bc$, $bc^{\prime}$ and $b$, showing that these tuples are
also inconsistent in $\Delta$.

Moreover, based on Definition 4, we also argue that $\Delta$ is not
consistent, because every $\mu$ such that $\mu\models\Delta$ cannot be an
interpretation. This is so because
$\mu^{*}(c)\cap\mu^{*}(c^{\prime})\neq\emptyset$ and Lemma 1 imply that for
$\mu$ such that $\mu\models\Delta$, $\mu(c)\cap\mu(c^{\prime})\neq\emptyset$.

Now, consider the tuple $bc^{\prime\prime}$ where $c^{\prime\prime}$ is a
constant in $dom(C)$ distinct from $c$ and $c^{\prime}$. To compute
$(bc^{\prime\prime})^{+}$ using Algorithm 1, the database
$\Delta_{t}=(D_{t},{\cal FD})$ where
$D_{t}=\\{ab,bc,abc^{\prime},bc^{\prime\prime}\\}$ is first defined and then,
the closure is first set to $\\{b,c^{\prime\prime}\\}$. The subsequent
computation steps rely on $B\to C$ and on that $\Delta_{t}\vdash bc$ and
$\Delta_{t}\vdash bc^{\prime}$ to insert $c$ and $c^{\prime}$ in the closure.

It therefore follows that
$(bc^{\prime\prime})^{+}=\\{b,c^{\prime\prime},c,c^{\prime}\\}$, thus that
$\Delta\mid\sim bc^{\prime\prime}$ holds. Since $\Delta\not\vdash
bc^{\prime\prime}$ (because $\mu^{*}(bc^{\prime\prime})=\emptyset$ and
$\mu^{*}\models\Delta$), it follows that $v_{\Delta}(bc^{\prime\prime})={\tt
false}$. Hence $bc^{\prime\prime}$ and all its super-tuples are false in
$\Delta$.

As an example of unknown tuple in $\Delta$, let $a^{\prime}$ be in $dom(A)$
such $a^{\prime}\neq a$, and consider $a^{\prime}c$. Since
$\mu^{*}(a^{\prime}c)=\emptyset$, $\Delta\not\vdash a^{\prime}c$. On the other
hand, it can be seen that $(a^{\prime}c)^{+}=\\{a^{\prime},c\\}$, because
$D\cup\\{a^{\prime}c\\}$ does not allow any specific tuple derivation using
$B\to C$. Hence, $\Delta\not\mid\sim a^{\prime}c$, which shows that
$v_{\Delta}(a^{\prime}c)={\tt unkn}$. $\Box$

The following example shows that computing all inconsistent tuples in $\Delta$
is not an easy task.

###### Example 7

Let $\Delta=(D,{\cal FD})$ be defined over $U=\\{A,B,C\\}$ by
$D=\\{abc,ac^{\prime}\\}$ and ${\cal FD}=\\{A\to B,B\to C\\}$.

Here again, the tuples in $D$ along with the functional dependencies in ${\cal
FD}$ show no explicit inconsistency. However computing $\mu^{*}$ yields the
following:
$\bullet$ To define $\mu_{0}$, we associate the tuples $abc$ and $ac^{\prime}$
with the integers 1 and 2, respectively. It follows that
$\mu_{0}(a)=\\{1,2\\}$, $\mu_{0}(b)=\\{1\\}$, $\mu_{0}(c)=\\{1\\}$,
$\mu_{0}(c^{\prime})=\\{2\\}$ and $\mu_{0}(\alpha)=\emptyset$ for any other
domain constant $\alpha$.
$\bullet$ The next steps modify $\mu_{0}$ so as to satisfy $A\to B$ and $B\to
C$ as follows:

  1. 1.

Due to $A\to B$, $\mu_{1}$ is defined by: $\mu_{1}(a)=\\{1,2\\}$,
$\mu_{1}(b)=\\{1,2\\}$, $\mu_{1}(c)=\\{1\\}$ and
$\mu_{1}(c^{\prime})=\\{2\\}$;

  2. 2.

Due to $B\to C$, $\mu_{2}$ is defined by: $\mu_{2}(a)=\\{1,2\\}$,
$\mu_{2}(b)=\\{1,2\\}$, $\mu_{2}(c)=\\{1,2\\}$ and
$\mu_{2}(c^{\prime})=\\{1,2\\}$.

As $\mu_{2}\models{\cal FD}$, $\mu^{*}=\mu_{2}$. Moreover, we have
$a^{+}=\\{a,b,c,c^{\prime}\\}$ and $b^{+}=\\{b,c,c^{\prime}\\}$ showing that,
by Lemma 2, $\Delta\vdash a\preceq(c\sqcap c^{\prime})$ and
$\Delta\vdash(b\preceq c\sqcap c^{\prime})$, thus that $a$ and $b$ are
inconsistent in $\Delta$. It can then be seen that, for example, $abc$,
$bc^{\prime}$ and $ac$ are also inconsistent in $\Delta$.

Now, let $\Delta_{1}=(D_{1},{\cal FD})$ such that
$D_{1}=\\{ac,ac^{\prime}\\}$. In this case, $\mu^{*}$ is defined by
$\mu^{*}(a)=\\{1,2\\}$, $\mu^{*}(c)=\\{1\\}$, $\mu^{*}(c^{\prime})=\\{2\\}$
and $\mu^{*}(\alpha)=\emptyset$ for any other domain constant $\alpha$.
Therefore, $a^{+}=\\{a\\}$, showing that $a$ is not inconsistent in
$\Delta_{1}$. As a consequence, $ac$, $ac^{\prime}$ along with all their sub-
tuples are true in $\Delta_{1}$ and all other tuples are unknown in
$\Delta_{1}$. $\Box$

The following proposition shows that our notion of inconsistent tuple complies
with Definition 4.

###### Proposition 1

$\Delta=(D,{\cal FD})$ is consistent if and only if there exists no tuple $t$
such that $v_{\Delta}(t)={\tt inc}$.

###### Proof

We first note that if there exists a tuple $t$ such that $v_{\Delta}(t)={\tt
inc}$, then $\Delta\vdash t$ and $\Delta\mid\sim t$. Hence there exist $a$ and
$a^{\prime}$ in the same attribute domain $dom(A)$ such that
$\Delta\vdash(t\preceq a\sqcap a^{\prime})$. Thus every ${\cal T}$-mapping
$\mu$ such that $\mu\models\Delta$ satisfies that $\mu(t)\neq\emptyset$ and
$\mu(t)\subseteq\mu(a)\cap\mu(a^{\prime})$, implying that
$\mu(a)\cap\mu(a^{\prime})\neq\emptyset$. Hence, $\mu$ is not an
interpretation, showing that, by Definition 4, $\Delta$ is not consistent.

Conversely, assuming that there is no tuple $t$ such that $v_{\Delta}(t)={\tt
inc}$, that is such that $\Delta\vdash t$ and $\Delta\mid\sim t$, we prove
that $\mu^{*}$ is an interpretation of $\Delta$. Indeed, if $a_{1}$ and
$a_{2}$ are two constants in the same attribute domain $A$ such that
$\mu^{*}(a_{1})\cap\mu^{*}(a_{2})\neq\emptyset$, then by Lemma 1(1), there
exist $X\to A$ in ${\cal FD}$ and $x$ over $X$ such that
$\mu^{*}(x)\neq\emptyset$ and
$\mu^{*}(x)\subseteq\mu^{*}(a_{1})\cap\mu^{*}(a_{2})$. Thus by Lemma 1(2), for
every $\mu$ such that $\mu\models\Delta$,
$\mu(x)\subseteq\mu(a_{1})\cap\mu(a_{2})$ and $\mu(x)\neq\emptyset$. We
therefore obtain that $\Delta\mid\sim x$ and $\Delta\vdash x$, thus that
$v_{\Delta}(x)={\tt inc}$, which is a contradiction. Therefore $\mu^{*}$ is an
interpretation, and the proof is complete. $\Box$

Based on Definition 5, we stress the following important remarks about
potentially true and potentially false tuples in a given $\Delta=(D,{\cal
FD})$:

  * •

Let $t$ be a potentially true tuple. Since $\Delta\vdash t$ holds, as a
consequence of Lemma 1, we have that $\mu^{*}(t)\neq\emptyset$. Therefore true
or inconsistent tuples are those tuples that are associated with a nonempty
set by every ${\cal T}$-mapping $\mu$ such that $\mu\models\Delta$. This
implies that potentially true tuples in $\Delta$ are built up with constants
occurring in $D$, and thus are in finite number. We provide in this paper
effective algorithms for computing the sets of true tuples and inconsistent
tuples.

  * •

As potentially false tuples $t$ are such that $\Delta\mid\sim t$, they may not
satisfy $\Delta\vdash t$. Hence, Lemma 1 cannot be used to characterize them.
Moreover, if $\Delta\mid\sim t$, then every tuple $t^{\prime}$ such that
$t\sqsubseteq t^{\prime}$ also satisfies $\Delta\mid\sim t^{\prime}$. This is
so because in this case, if $\Delta\vdash(t\preceq a\sqcap a^{\prime})$, then
$\Delta\vdash(t^{\prime}\preceq a\sqcap a^{\prime})$ holds as well. Thus, the
number of potentially false tuples may be infinite in case some of the
attribute domains are infinite.

  * •

Moreover, since every false tuple $t$ is potentially false and does not
satisfy $\Delta\vdash t$, it also follows as above that every tuple
$t^{\prime}$ such that $t\sqsubseteq t^{\prime}$ is also false. Thus, the
number of false tuples may be infinite in case some of the attribute domains
are infinite. However, the following proposition allows to characterize when a
given tuple $t$ is false.

###### Proposition 2

Given $\Delta=(D,{\cal FD})$ and a tuple $t$, $v_{\Delta}(t)={\tt false}$ if
and only if $\Delta\not\vdash t$ and $v_{\Delta_{t}}(t)={\tt inc}$, where
$\Delta_{t}=(D_{t},{\cal FD})$ and $D_{t}=D\cup\\{t\\}$.

###### Proof

Assuming that $v_{\Delta}(t)={\tt false}$ indeed entails that
$\Delta\not\vdash t$ by Definition 5. Moreover, as $\Delta\mid\sim t$, there
exist $A$ in $U$ and $a$ and $a^{\prime}$ in $dom(A)$ such that
$\Delta\vdash(t\preceq a\sqcap a^{\prime})$. Now, given $\mu$ such that
$\mu\models\Delta_{t}$, it has been shown that $\mu$ also satisfies that
$\mu\models\Delta$ (see Appendix B). Hence,
$\mu(t)\subseteq\mu(a)\cap\mu(a^{\prime})$ holds, which implies that
$\Delta_{t}\vdash(t\preceq a\sqcap a^{\prime})$, that is $\Delta_{t}\mid\sim
t$. Since it holds that $\Delta_{t}\vdash t$, we obtain that
$v_{\Delta_{t}}(t)={\tt inc}$.

Conversely, if $v_{\Delta_{t}}(t)={\tt inc}$ then, by Definition 5,
$\Delta_{t}\vdash t$ and $\Delta_{t}\mid\sim t$ hold. Therefore, there exist
$A$ in $U$ and $a$ and $a^{\prime}$ in $dom(A)$ such that
$\Delta_{t}\vdash(t\preceq a\sqcap a^{\prime})$, which by Algorithm 1 and
Lemma 2, implies that $a$ and $a^{\prime}$ are in $t^{+}$. We thus obtain that
$\Delta\mid\sim t$, which combined with our hypothesis that $\Delta\not\vdash
t$, implies that $v_{\Delta}(t)={\tt false}$. The proof is therefore complete.
$\Box$

##  4 Computing the Semantics

Similarly to standard two valued logic, where computing the semantics of
$\Delta$ means computing the set of all tuples true in $\Delta$, in our
approach, computing the semantics amounts to compute all true, inconsistent or
false tuples, knowing that unknown tuples are the remaining ones.

However, as mentioned above, the set of false tuples may be infinite, making
it impossible to compute them all. In this work, the case of false tuples is
only partially addressed, and we rather concentrate on potentially true
tuples, with the goal of investigating consistent query answering in our
approach (see Section 6).

###  4.1 The Chase Procedure in our Approach

We first propose an effective algorithm for the computation of all potentially
true tuples in a given $\Delta$. This algorithm is in fact inspired by the
standard chase algorithm Spyratos87 ; Ullman , with the main difference that
when a functional dependency cannot be satisfied, our algorithm does not stop.

Algorithm 2 Chasing a table

0: $\Delta=(D,{\cal FD})$

0: The chased table $\Delta^{*}=(D^{*},{\cal FD})$ and a set $inc({\cal FD})$
containing sets of tuples associated with each $X\to A$ in ${\cal FD}$

1: $D^{*}:=D$

2: for all $X\to A$ in ${\cal FD}$ do

3: $inc(X\to A):=\emptyset$

4: while $D^{*}$ changes do

5: for all $X\to A\in{\cal FD}$ do

6: for all $t_{1}$ in $D^{*}$ such that $XA\subseteq sch(t_{1})$ do

7: for all $t_{2}$ in $D^{*}$ such that $X\subseteq sch(t_{2})$ and
$t_{1}.X=t_{2}.X$ do

8: if $A\not\in sch(t_{2})$ then

9: $D^{*}:=D^{*}\cup\\{t_{2}a_{1}\\}$ where $a_{1}=t_{1}.A$

10: if $A\in sch(t_{2})$ and $t_{1}.A\neq t_{2}.A$ then

11: Let $y_{i}=t_{i}.(sch(t_{i})\setminus A)$ and $a_{i}=t_{i}.A$, for $i=1,2$

12: $D^{*}:=D^{*}\cup\\{y_{2}a_{1}\\}$// $y_{1}a_{2}$ is inserted into $D^{*}$
when processing $t_{2}$ in place of $t_{1}$// and $t_{1}$ in place of $t_{2}$

13: $inc(X\to A):=inc(X\to A)\cup\\{x\\}$ where $x=t_{1}.X=t_{2}.X$ //
Reduction: keep in $D^{*}$ only maximal tuples

14: for all $t_{1}$ in $D^{*}$ do

15: for all $t_{2}$ in $D^{*}$ do

16: if $t_{2}\sqsubseteq t_{1}$ and $t_{1}\neq t_{2}$ then

17: $D^{*}:=D^{*}\setminus\\{t_{2}\\}$

18: $inc({\cal FD}):=\\{inc(X\to A)~{}|~{}inc(X\to A)\neq\emptyset\\}$

19: return $\Delta^{*}=(D^{*},{\cal FD})$ and $inc({\cal FD})$

Instead, our chasing algorithm carries on the computation, returning a
database $\Delta^{*}=(D^{*},{\cal FD})$ and a set $inc({\cal FD})$ based on
which inconsistent and true tuples are shown to be efficiently computed.
Before doing so, we illustrate Algorithm 2 in the context of our introductory
example.

$D$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ |  | $m^{\prime}$ |
| $i_{1}$ | $k$ |  | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ |
| $i_{2}$ | $k^{\prime}$ |  | $c^{\prime}$
| $i_{3}$ |  | $m$ |
| $i_{3}$ | $k^{\prime}$ |  |

$D^{*}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ | $k$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c^{\prime}$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ | $c^{\prime}$
| $i_{3}$ | $k^{\prime}$ | $m$ |

Figure 2: The table $D$ and its chased version $D^{*}$

###### Example 8

Running Algorithm 2 with the table $D$ shown in Figure 1, and recalled in
Figure 2, produces the table $D^{*}$ shown in the right of Figure 2 and the
set $inc({\cal FD})=\\{inc(Id\to M),inc(Id\to C)\\}$ where $inc(Id\to
M)=\emptyset$ and $inc(Id\to C)=\\{i_{2}\\}$. The main steps of the algorithm
work as follows:
$\bullet$ First, $D^{*}$ is assigned $D$, and $inc(Id\to M)$ and $inc(Id\to
C)$ are assigned $\emptyset$.
$\bullet$ Due to the statement on line 9, the first two rows in $D$ (thus in
$D^{*}$) generate the new tuples $(i_{1},k,m^{\prime})$ and
$(i_{1},m^{\prime},c)$. Similarly, applying $Id\to K$ to the last two rows in
$D$ generates the new tuple $(i_{3},k^{\prime},m)$.
The rows 4 and 5 in $D$ generate $(i_{2},k^{\prime},m^{\prime\prime},c)$ and
the rows 5 and 6 generate $(i_{2},k^{\prime},m^{\prime\prime},c^{\prime})$.
Moreover, due to the statement on line 12, the rows 4 and 6 generate
$(i_{2},k^{\prime},m^{\prime},c^{\prime})$ and $(i_{2},k^{\prime},c)$ and
$i_{2}$ is inserted in $inc(Id\to C)$.
$\bullet$ With these new tuples at hand, the loop on line 4 proceeds further,
generating $(i_{1},k,m^{\prime},c)$ by the statement on line 9. No new tuple
is generated at this stage.
$\bullet$ The loop on line 4 is processed once again, producing no new tuple.
When running the reduction step against the current state of $D^{*}$, the
following tuples are removed: $(i_{1},m^{\prime})$, $(i_{1},k,m^{\prime})$,
$(i_{1},m^{\prime},c)$, $(i_{1},k,c)$, $(i_{2},k^{\prime},m^{\prime\prime})$,
$(i_{2},k^{\prime},c^{\prime})$, $(i_{2},k^{\prime},c)$, $(i_{3},m)$ and
$(i_{3},k^{\prime})$.

Thus, the output of Algorithm 2 is indeed as expected. It is important to
notice that, although tuples have been added in $D^{*}$ during the processing,
the final number of tuples in $D^{*}$ is less than that in $D$. Although this
particular result cannot be proven in general, it will be shown that in the
worst case, the size of $D^{*}$ remains polynomial in the size of $D$.

We emphasize that some nulls present in $D$ have been replaced by actual
values in $D^{*}$, thanks to the functional dependencies in ${\cal FD}$. For
example the second tuple in $D$ with two nulls has been ‘completed’ into a
total tuple in $D^{*}$. However, such a completion has not been possible for
every tuple in $D^{*}$. Namely, the $C$-value in the last tuple of $D^{*}$ is
left as null.

Keeping in line with our statement that ‘a missing value exists only if it is
inferred from the functional dependencies’, this indicates that the $C$-value
of this tuple could not be determined based on the content of $D$ and ${\cal
FD}$, and no other conclusion can be drawn regarding this null.

To see why the two insertions mentioned in the statement on line 12 are
needed, we first recall from Ullman  that, in the traditional case, the chased
table characterizes the semantics of the input table, in case no inconsistency
has been detected111In traditional chase, the semantics of a table $D$
containing nulls is the set of all tuples true in every instance of $D$, i.e.,
in every relation $R$ over $U$ with no nulls, that satisfies the functional
dependencies and such that for every $t$ in $D$, there exists $r$ in $R$ such
that $r.T=t$.. In this work our goal is similar, but has to be adapted to our
context. Namely, we expect that the chased table $D^{*}$ can provide a
syntactical characterization of all possibly true tuples in $\Delta$, that is
of all tuples $t$ such that $\Delta\vdash t$ holds.

In the context of our example, if we assume that
$(i_{2},k^{\prime},m^{\prime},c^{\prime})$ is not inserted during the
processing then Algorithm 2 would not fit our semantics. Indeed, for every
${\cal T}$-mapping $\mu$ such that $\mu\models\Delta$,
$\mu(i_{2})\subseteq\mu(c^{\prime})$ holds because of $Id\to C$ applied to the
seventh row in $D$. Thus,
$\mu(i_{2},k^{\prime},m^{\prime},c^{\prime})=\mu(k^{\prime},m^{\prime},c^{\prime})$,
and since $\mu(k^{\prime},m^{\prime},c^{\prime})$ is nonempty (due to the
fifth row in $D$), $\Delta\vdash(i_{2},k^{\prime},m^{\prime},c^{\prime})$.
Hence $(i_{2},k^{\prime},m^{\prime},c^{\prime})$ must appear in $D^{*}$ to
fulfill our expectation.

Adding such ‘new’ tuples when chasing a table is one of the main features of
our approach, as compared with traditional chase. This step should be seen as
a ‘by-product’ of carrying on the computation even after encountering a
violation of a functional dependency. $\Box$

The following lemma shows that Algorithm 2 provides an operational means to
characterize the tuples $t$ such that $\mu^{*}(t)\neq\emptyset$.

###### Lemma 3

Algorithm 2 applied to $\Delta=(D,{\cal FD})$ always terminates. Moreover, for
every tuple $t$, $\mu^{*}(t)\neq\emptyset$ holds if and only if $t$ is in
${\sf LoCl}(D^{*})$.

###### Proof

See Appendix C. $\Box$

Recalling that ${\sf LoCl}(D^{*})$ denotes the Lower Closure of $D^{*}$, that
is the set of all sub-tuples of tuples in $D^{*}$, Lemma 3 shows that $D^{*}$
is a ‘tabular’ version of the set of all tuples $t$ such that
$\mu^{*}(t)\neq\emptyset$, that is, by Lemma 1, a ‘tabular’ version of the set
of all tuples $t$ such that $\Delta\vdash t$. Therefore, $D^{*}$ provides a
syntactical characterization of the set of all tuples $t$ such that
$\Delta\vdash t$, as expected in the previous example.

###  4.2 Computing True Tuples and Inconsistent Tuples

As mentioned just above, Lemma 1 and Lemma 3 show that, given $\Delta=(D,{\cal
FD})$, a tuple $t$ is in ${\sf LoCl}(D^{*})$ if and only if $\Delta\vdash t$
holds, that is, if and only if $t$ is potentially true in $\Delta$, that is if
and only if $t$ is either true or inconsistent in $\Delta$.

To see how to compute the set of all inconsistent tuples, we first recall the
notion of closure of a relation scheme as defined in relational database
theory Ullman .

Given a set ${\cal FD}$ of functional dependencies and a relation scheme $X$,
the closure of $X$ with respect to ${\cal FD}$, or more simply the closure of
$X$, denoted by $X^{+}$, is the set of all attributes $A$ in $U$ such that
every table $D$ satisfying ${\cal FD}$ in the sense of relational tables, also
satisfies $X\to A$.

It is well-known that $X^{+}$ is computed through the following two steps that
are quite similar to the steps of Algorithm 1:

  * $X^{+}:=X$

  * while $X^{+}$ changes do

for all $Y\to B$ in ${\cal FD}$ such that $Y\subseteq X^{+}$ do

$X^{+}:=X^{+}\cup\\{B\\}$

return $X^{+}$

The following proposition shows a strong relationship between the closure of a
relation scheme as recalled above and the closure of a tuple as stated in
Definition 3.

###### Proposition 3

Let $\Delta=(D,{\cal FD})$ and $t$ be such that $\Delta\vdash t$. For every
tuple $q$ and every $a$ in $dom(A)$ such that $q\sqsubseteq t$ and
$a\sqsubseteq t$, we have: $a$ belongs to $q^{+}$ if and only if $A$ belongs
to $Q^{+}$.

###### Proof

See Appendix D. $\Box$

Algorithm 3 Inconsistent tuples in $\Delta=(D,{\cal FD})$

0: The output of Algorithm 2, that is $\Delta^{*}=(D^{*},{\cal FD})$ and
$inc({\cal FD})$.

0: The set ${\sf Inc}(\Delta)$

1: ${\sf Inc}(\Delta):=\emptyset$

2: for all $t$ in $D^{*}$ do

3: for all $X\to A$ in ${\cal FD}$ such that $XA\subseteq T$ do

4: if $x=t.X$ is in $inc(X\to A)$ then

5: for all $q$ such that $q\sqsubseteq t$ do

6: if $X\subseteq Q^{+}$ then

7: ${\sf Inc}(\Delta):={\sf Inc}(\Delta)\cup\\{t.Q\\}$

8: return ${\sf Inc}(\Delta)$

Using the notion of relation scheme closure, we introduce Algorithm 3 which
computes the set of inconsistent tuples in $\Delta$. The correctness of this
algorithm is shown in Lemma 4.

###### Lemma 4

Given $\Delta=(D,{\cal FD})$, a tuple $t$ is inconsistent in $\Delta$ if and
only if $t\in{\sf Inc}(\Delta)$.

###### Proof

See Appendix E. $\Box$

The following proposition characterizes inconsistent and true tuples in
$\Delta$ based on Algorithm 2 and Algorithm 3.

###### Proposition 4

Given $\Delta=(D,{\cal FD})$ and a tuple $t$:
1\. $t$ is inconsistent in $\Delta$ if and only if $t\in{\sf Inc}(\Delta)$.
2\. $t$ is true in $\Delta$ if and only if $t\in{\sf LoCl}(D^{*})\setminus{\sf
Inc}(\Delta)$.

###### Proof

Immediate consequence of Definition 5, Lemma 3 and Lemma 4. $\Box$

The following examples illustrate Algorithm 3 and Proposition 4.

###### Example 9

As in Example 7, let $\Delta=(D,{\cal FD})$ over $U=\\{A,B,C\\}$ where
$D=\\{abc,ac^{\prime}\\}$ and ${\cal FD}=\\{A\to B,B\to C\\}$. The tabular
version of $D$ is shown on the left below, whereas $D^{*}$ is shown on the
right.

$D$ | $A$ | $B$ | $C$
---|---|---|---
| $a$ | $b$ | $c$
| $a$ |  | $c^{\prime}$
$D^{*}$ | $A$ | $B$ | $C$
---|---|---|---
| $a$ | $b$ | $c$
| $a$ | $b$ | $c^{\prime}$

Running Algorithm 2, $D^{*}$ is first set to $D$ and $abc^{\prime}$ is
inserted in $D^{*}$ by the statement line 9 due to $A\to B$. Then, $b$ is
inserted in $inc(B\to C)$ by the statement line 13, due to the tuples $abc$
and $abc^{\prime}$. Thus, the table $D^{*}$ output by Algorithm 2 is as shown
above and $inc({\cal FD})=\\{inc(A\to B),inc(B\to C)\\}$ where $inc(A\to
B)=\emptyset$ and $inc(B\to C)=\\{b\\}$.

When running Algorithm 3 for $abc$ in $D^{*}$, since $b$ is in $inc(B\to C)$,
$b$, $ab$, $bc$ and $abc$ are inserted into ${\sf Inc}(\Delta)$, due to the
statement on line 7. This is so because the schema $Q$ of each of these tuples
contains $B$, and so, satisfies $B\subseteq Q^{+}$.

Moreover, for $q=a$, due to $A\to B$, we have $A^{+}=ABC$ and thus,
$B\subseteq A^{+}$ holds, showing that $a$ is inserted in ${\sf Inc}(\Delta)$
on line 7. A similar reasoning holds for $q=ac$ because $B\in(AC)^{+}$. Thus,
$ac$ is also inserted in ${\sf Inc}(\Delta)$ on line 7. The only remaining
possibility is $q=c$, and does not modify ${\sf Inc}(\Delta)$ because
$B\not\subseteq C^{+}$. A similar computation is performed with $abc^{\prime}$
in $D^{*}$, adding $bc^{\prime}$, $abc^{\prime}$ and $ac^{\prime}$ in ${\sf
Inc}(\Delta)$. As no other tuple can be inserted in ${\sf Inc}(\Delta)$,
Algorithm 3 returns

${\sf Inc}(\Delta)=\\{abc,$ $abc^{\prime},$ $ab$, $ac,$ $ac^{\prime},$ $bc,$
$bc^{\prime},$ $a,$ $b\\}$,

which, by Proposition 4(1), is the set of all inconsistent tuples in $\Delta$.
As a consequence, by Proposition 4(2), $c$ and $c^{\prime}$ are the only true
tuples in $\Delta$.

Now, as in Example 7, referring to $\Delta_{1}=(D_{1},{\cal FD})$ with
$D_{1}=\\{ac,ac^{\prime}\\}$, it is easy to see that $D_{1}^{*}=D_{1}$. This
implies that $\Delta_{1}$ is consistent, and that $ac$, $ac^{\prime}$, $a$,
$c$ and $c^{\prime}$ are true in $\Delta_{1}$. $\Box$

###  4.3 The Case of False Tuples

As already noticed, computing all tuples false in a given $\Delta=(D,{\cal
FD})$ is not feasible in case of infinite attribute domains. However, given a
tuple $t$ and assuming that $\Delta^{*}$ and ${\sf Inc}(\Delta)$ have been
computed, Algorithm 4 allows to compute $v_{\Delta}(t)$. In this way, instead
of being systematically identified, false tuples are identified on demand.

Algorithm 4 Tuple truth value in $\Delta=(D,{\cal FD})$

0: A tuple $t$, $\Delta^{*}=(D^{*},{\cal FD})$ and ${\sf Inc}(\Delta)$

0: The truth value of $t$ as one of the truth values true, false, inc or unkn

1: $v:={\tt unkn}$

2: if $t\in{\sf LoCl}(\Delta^{*})$ then

3: if $t\in{\sf Inc}(\Delta)$ then

4: $v:={\tt inc}$

5: else

6: $v:={\tt true}$

7: else

8: Compute $D^{*}_{t}$ using Algorithm 2 applied to $D^{*}\cup\\{t\\}$ and
${\cal FD}$

9: Compute ${\sf Inc}(\Delta_{t})$ using Algorithm 3 applied to
$\Delta_{t}=(D^{*}\cup\\{t\\},{\cal FD})$

10: if $t\in{\sf Inc}(\Delta_{t})$ then

11: $v:={\tt false}$

12: return $v$

###### Proposition 5

Given $\Delta=(D,{\cal FD})$, and a tuple $t$ and assuming that
$\Delta^{*}=(D^{*},{\cal FD})$ and ${\sf Inc}(\Delta)$ have been computed, the
truth value returned by Algorithm 4 is equal to $v_{\Delta}(t)$.

###### Proof

Immediate consequence of Definition 5 and Proposition 2. $\Box$

The following example illustrates the algorithm.

###### Example 10

It has been seen in Example 8 that in the context of our introductory example,
Algorithm 2 returns the table $D^{*}$ as shown in Figure 2, and
$inc(\Delta)=\\{inc(Id\to K),inc(Id\to C)\\}$ where $inc(Id\to K)=\emptyset$
and $inc(Id\to C)=\\{i_{2}\\}$. Thus, by Algorithm 3, the set ${\sf
Inc}(\Delta)$ is defined by:

${\sf Inc}(\Delta)=$ | $\\{t~{}|~{}i_{2}\sqsubseteq t\sqsubseteq(i_{2},k^{\prime},m^{\prime},c)\\}\cup\\{t~{}|~{}i_{2}\sqsubseteq t\sqsubseteq(i_{2},k^{\prime},m^{\prime},c^{\prime})\\}\,\cup$
---|---
| $\\{t~{}|~{}i_{2}\sqsubseteq
t\sqsubseteq(i_{2},k^{\prime},m^{\prime\prime},c)\\}\cup\\{t~{}|~{}i_{2}\sqsubseteq
t\sqsubseteq(i_{2},k^{\prime},m^{\prime\prime},c^{\prime})\\}$

Applying now Algorithm 4, we have the following:

  * •

$v_{\Delta}(i_{1},a,m,c)=v_{\Delta}(i_{1},k,m^{\prime},c)={\tt true}$, because
line 6 changes the value of $v$, since these tuples are in $D^{*}$ but not in
${\sf Inc}(\Delta)$.

  * •

$v_{\Delta}(i_{2})=v_{\Delta}(i_{2},c)=v_{\Delta}(i_{2},c^{\prime})={\tt
inc}$, because line 4 changes the value of $v$, since these tuples are in
${\sf Inc}(\Delta)$.

  * •

$v_{\Delta}(i_{1},k^{\prime})=v_{\Delta}(i_{1},c^{\prime})={\tt false}$.
Indeed, none of these tuples is in ${\sf LoCl}(D^{*})$, thus implying that
neither line 4 nor line 6 applies. Moreover, when running Algorithm 4 with
$(i_{1},k^{\prime})$ as input, $(i_{1},k,m,c)$ and $(i_{1},k^{\prime})$ are in
$D^{*}\cup\\{(i_{1},k^{\prime})\\}$. Hence $(i_{1},k^{\prime})$ is in ${\sf
Inc}(\Delta_{t})$, because of $Id\to K$, and by line 11,
$v_{\Delta}(k^{\prime}m)$ is set to ${\tt false}$. A similar reasoning holds
for $(i_{1},c^{\prime})$, but using $Id\to C$.

  * •

$v_{\Delta}(k^{\prime},m)={\tt unkn}$. Indeed, as above, when running
Algorithm 4 with $(k^{\prime},m)$ as input, lines 4 and 6 do not change the
value of $v$ (as $(k^{\prime},m)$ does not occur in ${\sf LoCl}(D^{*})$).
Moreover, as $D^{*}\cup\\{(k^{\prime},m)\\}$ is consistent, the value of $v$
is not changed by the statement line 11. Consequently, ${\tt unkn}$ is
returned. $\Box$

###  4.4 Complexity Issues

We argue that the computation of inconsistent and true tuples in
$\Delta=(D,{\cal FD})$ is polynomial in the size of the table $D$ and in the
order of the ‘number of conflicts with respect to functional dependencies’ (to
be defined shortly). To see this, denoting by $|E|$ the cardinality of a set
$E$, we investigate the complexities of Algorithm 2 and of Algorithm 3.

Regarding Algorithm 2, we first notice that, contrary to the standard chase
algorithm Ullman , rows are added in the table during the computation, and
some others are then removed by the reduction statement of line 14. To assess
the size of the table $D^{*}$ during the processing, we point out the
following:

  * •

If no inconsistency is found during the processing of the while-loop on line
4, at most one tuple is added in $D^{*}$ as the ‘join’ of two tuples in $D$ by
statement line 9. Therefore, the cardinality of $D^{*}$ remains in the same
order as that of $D$. Notice in this respect that, upon reduction, one ‘join’
tuple replaces two tuples in $D$, which reduces the size of the table $D^{*}$
output by the algorithm.

  * •

However, when inconsistent tuples occur, the statement line 9 adds more than
one tuple and statement line 12 inserts tuples resulting from a cross-product.

To find an upper bound of the size of $D^{*}$, for every $X\to A$ in ${\cal
FD}$, let $N(x)$ be the number of different $A$-values $a$ such that
$\Delta\vdash xa$ and $x$ belongs to $inc(X\to A)$. We denote by $\delta$ the
maximal value of all $N(x)$ for all $x$ in $inc({\cal FD})$; in other words
$\delta=\max(\\{N(x)~{}|~{}x\in inc({\cal FD})\\})$. $\delta$ is precisely
what was earlier referred to as the ‘number of conflicts with respect to
functional dependencies’.

Given a tuple in $D$ and a functional dependency $X\to A$ in ${\cal FD}$, each
of the statements line 9 and line 12 generates at most $\delta$ tuples. Since
several functional dependencies may apply to $t$, at most $\delta^{|{\cal
FD}|}$ tuples are generated for the given tuple $t$. Hence, the number of
tuples generated by the statements lines 9 and 12 is in ${\cal
O}\left(|D|.\delta^{|{\cal FD}|}\right)$. We therefore obtain that the size of
the table $D^{*}$ when running Algorithm 2 is in ${\cal
O}\left(|D|.\left(1+\delta^{|{\cal FD}|}\right)\right)$, that is in ${\cal
O}\left(|D|.\delta^{|{\cal FD}|}\right)$.

Since the number of runs of the while-loop on line 4 is at most equal to the
number of tuples added into $D^{*}$, this number is in ${\cal
O}\left(|D|.\delta^{|{\cal FD}|}\right)$. Since moreover one run of the while-
loop is quadratic in the size of $D^{*}$, the computational complexity of this
while-loop is in ${\cal O}\left(|D|^{3}.\delta^{3.|{\cal FD}|}\right)$.

The last point to be mentioned here is that the reduction processing on line
14 is performed through a scan $D^{*}$ whereby for every $t$ in $D^{*}$ every
sub-tuple of $t$ is removed. Such a processing being quadratic in the size of
$D^{*}$, the overall computational complexity of Algorithm 2 is in ${\cal
O}\left(|D|^{3}.\delta^{3.|{\cal FD}|}\right)$.

As the computational complexity of Algorithm 3 is clearly linear in the size
of $D^{*}$, the global complexity of the computation of inconsistent and true
tuples in $\Delta$ is as stated just above, and therefore polynomial in the
size of $D$.

Regarding Algorithm 4, we notice that its complexity is in ${\cal
O}\left(|D|^{3}.\delta^{3.|{\cal FD}|}\right)$ as well, because it requires a
scan of $D^{*}$ and then, in case the test line 2 fails, Algorithm 2 is
applied to a table whose cardinality is that of $D^{*}$ plus 1. It should
however be kept in mind that, in this case, the algorithm has to be run once
for each tuple, which shows that computing false tuples is not feasible even
if all attribute domains are finite. Indeed, in this case, denoting by $DOM$
the maximal cardinality of attribute domains, the cardinality of ${\cal T}$ is
in ${\cal O}\left(|U|^{DOM}\right)$, thus yielding a computation in ${\cal
O}\left(|U|^{DOM}.|D|^{3}.\delta^{3.|{\cal FD}|}\right)$.

We draw attention on the following important points regarding these complexity
results:

  1. 1.

Regarding the computation of false tuples, the above result has to be further
investigated in the following two directions: first the computation of
$D^{*}_{t}$ processed in Algorithm 4 is likely to be optimized using an
incremental algorithm instead of Algorithm 2, and second, it is expected that
there exist interesting and relevant cases whereby the computation of
$D^{*}_{t}$ is not necessary. We indeed suspect that this holds in the case of
a star schema. This is an important issue that lies out of the scope of the
present paper, but that will be investigated in the next future.

  2. 2.

When the database is consistent, $\delta$ is equal to $1$, thus yielding a
complexity in ${\cal O}(|D|^{3})$. This result can be shown independently from
the above computations as follows: In the case of traditional chase the
maximum of nulls in $D$ being bounded by $|U|.|D]$, the number or iterations
when running the algorithm is also bounded by $|U|.|D|$. Since the run of one
iteration is in $|D|^{2}$, the overall complexity is in ${\cal
O}(|U|.|D|^{3})$, or in ${\cal O}(|D|^{3})$, as $|U|$ is independent from
$|D|$.

  3. 3.

The above complexity study should be further investigated in order to provide
more accurate results regarding the estimation of the number of actual tests
necessary to the computation of $D^{*}$. The results in CKS86  are likely to
be useful for such a more thorough study of this complexity.

##  5 Four-Valued Logic and Table Merging

In this section, we first give a brief overview of Belnap’s Four-valued logic
and then we show that our approach has a strong relationship with this
formalism in the context of merging two or more tables.

###  5.1 Basics of Four-Valued Logic

Four-valued logic was introduced by Belnap in Belnap , who argued that his
formalism is of interest when integrating data from various data sources. To
this end, he introduced four truth values denoted by t, b, n and f and read as
true, both true and false, neither true nor false and false, respectively. An
important feature of this Four-valued logic is that its truth values can be
compared according to two partial orderings, known as truth ordering and
knowledge ordering, respectively denoted by $\preceq_{t}$ and $\preceq_{k}$
and defined as follows:

$\varphi$ |  $\neg\varphi$
---|---
${\tt t}$ | ${\tt f}$
${\tt b}$ | ${\tt b}$
${\tt n}$ | ${\tt n}$
${\tt f}$ | ${\tt t}$

$\vee$ | t | b | n | f
---|---|---|---|---
t | t | t | t | t
b | t | b | t | b
n | t | t | n | n
f | t | b | n | f

$\wedge$ | t | b | n | f
---|---|---|---|---
t | t | b | n | f
b | b | b | f | f
n | n | f | n | f
f | f | f | f | f

$\oplus$ | t | b | n | f
---|---|---|---|---
t | t | b | t | b
b | b | b | b | b
n | t | b | n | f
f | b | b | f | f

$\otimes$ | t | b | n | f
---|---|---|---|---
t | t | t | n | n
b | t | b | n | f
n | n | n | n | n
f | n | f | n | f

Figure 3: Truth tables of basic connectors

${\tt n}\preceq_{k}{\tt t}\preceq_{k}{\tt b}$ ; ${\tt n}\preceq_{k}{\tt
f}\preceq_{k}{\tt b}$ and ${\tt f}\preceq_{t}{\tt n}\preceq_{t}{\tt t}$ ;
${\tt f}\preceq_{t}{\tt b}\preceq_{t}{\tt t}$.

As a consequence, two new connectors were introduced, denoted by $\oplus$ and
$\otimes$, in addition to the standard connectors $\vee$ (disjunction) and
$\wedge$ (conjunction). The corresponding truth tables, along with that for
negation, are displayed in Figure 3 and show that $\vee$ and $\oplus$
correspond to the least upper bound (lub) with respect to $\preceq_{t}$ and
$\preceq_{k}$, respectively; whereas $\wedge$ and $\otimes$, correspond to the
geatest lower bound (glb) with respect to $\preceq_{t}$ and $\preceq_{k}$,
respectively . It is also shown in Belnap ; Fitting91  that the set $\\{{\tt
t},{\tt b},{\tt n},{\tt f}\\}$ equipped with the two orderings $\preceq_{t}$
and $\preceq_{k}$ has a distributive bi-lattice structure.

Not surprisingly, some basic properties holding in standard logic do not hold
in this setting. For example, Figure 3 shows that formulas of the form
$\Phi\vee\neg\Phi$ are not always true, independently of the truth value of
$\Phi$. The reader is referred to the literature ArieliA98 ; Belnap ;
Fitting91 ; Laurent19 ; Tsoukias  for more details on the properties of Four-
valued logic.

Based on the truth tables shown in Figure 3, it turns out that the connector
$\oplus$ plays a key role in the context of data integration. Indeed,
considering $n$ data sources $S_{1},\ldots,S_{n}$ and a fact $\varphi$, for
every $i=1,\ldots,n$, $\varphi$ is assigned one truth value $v_{i}$, among
${\tt t}$, ${\tt b}$, ${\tt n}$, or ${\tt f}$ in each $S_{i}$. The
‘integrated’ truth value of $\varphi$, denoted by $v$ is then obtained as the
expression $v=v_{1}\oplus\ldots\oplus v_{n}$, due to the following intuition:

  * •

The third row (or third column) of the truth table of $\oplus$ shows that
every $v_{i}$ such that $v_{i}={\tt n}$ plays no role in the resulting truth
value $v$, provided that one of them be distinct from ${\tt n}$ (otherwise the
‘integrated’ truth value of $\varphi$ is obviously ${\tt n}$). This fits our
intuition that a source in which the truth value of $\varphi$ is unknown does
not provide any piece of information regarding the ‘integrated’ truth value of
$\varphi$. We thus assume hereafter that for every $i=1,\ldots,n$,
$v_{i}\neq{\tt n}$.

  * •

For every ${\tt v}$ among t, b, n or f, if $v_{1}=\ldots=v_{n}={\tt v}$, then
$v={\tt v}$. The intuition here is that, since all sources agree on truth
value ${\tt v}$, it is obvious to expect $v$ to be this common value ${\tt
v}$. For example, if for every $i=1,\ldots,n$, $v_{i}={\tt t}$, then it should
be obvious that $v$ must be ${\tt t}$ as well!

  * •

Now, if there exists $i_{0}$ such that $v_{i_{0}}={\tt b}$, then $v={\tt b}$.
This fits the intuition that if $\varphi$ is inconsistent in at least one data
source, then $\varphi$ remains inconsistent in the integrated source.

  * •

The last case is when there exist distinct $i$ and $j$ in $\\{1,\ldots,n\\}$
such that $v_{i}\neq v_{j}$, and no $v_{i}$ is equal to ${\tt b}$. In this
case we have $v_{i}={\tt t}$ and $v_{j}={\tt f}$ (or equivalently $v_{i}={\tt
f}$ and $v_{j}={\tt t}$), which is the standard case of conflicting data
sources in practice. In this case, it holds that $v={\tt b}$ (since ${\tt
t}\oplus{\tt f}={\tt b}$). This result again fits our intuition that in case
of conflicting data sources, the ‘integrated’ truth value in inconsistent.

In the next sub-section, we show that, in our approach, the four truth values
as defined in Definition 5 also follow this intuition when it comes to merging
two or more tables over the same universe $U$.

###  5.2 Merging two or more Tables

Data merging consists in collecting data from multiple, possibly heterogeneous
sources and putting them in a single destination. The data from each source
usually comes in the form of a CSV file, along with some hints on the data,
referred to as metadata MEDES ; RavatZ19 . During this process, different data
sources are put together, or merged, into a single data store. Data merging is
also related to data consolidation and to data integration.

When data comes from a broad range of sources, consolidation allows
organizations to more easily present data, while also facilitating effective
data analysis. Data consolidation techniques reduce inefficiencies, like data
duplication, costs related to reliance on multiple databases and multiple data
management points.

In this section, we consider a simplified, relational scenario of $n$ sources
$\Delta_{1}=(D_{1},{\cal FD}_{1}),\ldots,\Delta_{n}=(D_{n},{\cal FD}_{n})$,
where each source $\Delta_{i}=(D_{i},{\cal FD}_{i})$ consists of a table
$D_{i}$ over a fixed universe $U$, possibly with nulls, and functional
dependencies ${\cal FD}_{i}$. We then explain how to merge these sources in
our approach under the following assumptions:

  1. 1.

All source tables are over the same universe $U$.

  2. 2.

Merging is done in the simplest possible way, namely $(a)$ the merged table is
the union (in the set theoretic sense) of the source tables and $(b)$ the set
of functional dependencies of the merged table is the union of the sets of
functional dependencies of the source tables. That is, the sources are merged
through the pair: $\Delta=(D,{\cal FD})$, where $D=\bigcup_{i=1}^{i=n}D_{i}$
and ${\cal FD}=\bigcup_{i=1}^{i=n}{\cal FD}_{i}$.

Relying on Belnap’s Four-valued logic, we investigate the relationship between
the truth values a tuple $t$ has in the source tables and the truth value the
tuple $t$ has in the merged table.

First, notice that a ‘natural’ one-to-one mapping $h$ from our set ${\sf
Four}=\\{{\tt true},$ ${\tt inc},$ ${\tt unkn},$ ${\tt false}\\}$ to Belnap’s
set ${\cal FOUR}=\\{{\tt t},$ ${\tt b},$ ${\tt n},$ ${\tt f}\\}$, can be
defined by: $h({\tt true})={\tt t}$, $h({\tt inc})={\tt b}$, $h({\tt
unkn})={\tt n}$ and $h({\tt false})={\tt f}$. Then, the connector $\oplus$
defined on ${\cal FOUR}$ induces a connector $\overline{\oplus}$ over ${\sf
Four}$ defined by: ${\tt v}_{1}\overline{\oplus}{\tt v}_{2}=h^{-1}(h({\tt
v}_{1})\oplus h({\tt v}_{2}))$ for all ${\tt v}_{1}$ and ${\tt v}_{2}$ in
${\sf Four}$.

Moreover, we can define a partial ordering on ${\sf Four}$ isomorphic to the
knowledge ordering of ${\cal FOUR}$ that allows us to compare truth values in
${\sf Four}$. Denoting this partial ordering by $\triangleleft$, we have:

${\tt unkn}\,\triangleleft\,{\tt false}\,\triangleleft\,{\tt inc}$ and ${\tt
unkn}\,\triangleleft\,{\tt true}\,\triangleleft\,{\tt inc}$

The following proposition shows that the truth value of a tuple $t$ in the
merged table is always greater (with respect to $\triangleleft$) than any of
the truth values that $t$ has in the source tables in which it appears. In
other words, when merging tables, the knowledge about tuples always increases,
compared to the knowledge we have about tuples in the source tables.

###### Proposition 6

Let $\Delta_{i}=(D_{i},{\cal FD}_{i})$ ($i=1,\ldots,n$) be $n$ data sources
over the same universe, and let $\Delta=(D,{\cal FD})$ be defined by
$D=\bigcup_{i=1}^{i=n}D_{i}$ and ${\cal FD}=\bigcup_{i=1}^{i=n}{\cal FD}_{i}$.
For every tuple $t$ the following holds:

$\overline{\bigoplus}\,_{i=1}^{i=n}\,v_{\Delta_{i}}(t)~{}\triangleleft~{}v_{\Delta}(t)$.

###### Proof

For every $i=1,\ldots,n$, let $\Delta^{\prime}_{i}=(D_{i},{\cal FD})$. We
first prove that for every tuple $t$,
$v_{\Delta_{i}}(t)~{}\triangleleft~{}v_{\Delta^{\prime}_{i}}(t)$ holds.
Indeed, for every $i=1,\ldots,n$, let $D_{i}^{*}$, respectively
$(D_{i}^{\prime})^{*}$, the chased table of $D_{i}$ with respect to ${\cal
FD}_{i}$, respectively ${\cal FD}$. Since ${\cal FD}_{i}\subseteq{\cal FD}$
holds, it is easy to see that for every $q_{i}$ in $(D_{i}^{\prime})^{*}$
there exists $q$ in $D_{i}^{*}$ such that $q_{i}\sqsubseteq q$. Hence, for
every $q$ in ${\cal T}$, $[q^{+}]_{i}\subseteq[q^{+}]^{\prime}_{i}$, where
$[q^{+}]_{i}$, respectively $[q^{+}]^{\prime}_{i}$, denotes the closure of $q$
in $\Delta_{i}$, respectively $\Delta^{\prime}_{i}$. Therefore, if
$\Delta_{i}\vdash t$, respectively $\Delta_{i}\mid\sim t$, then
$\Delta^{\prime}_{i}\vdash t$, respectively $\Delta^{\prime}_{i}\mid\sim t$,
and so, for every $i=1,\ldots,n$, $v_{\Delta_{i}}(t)\triangleleft
v_{\Delta^{\prime}_{i}}(t)$.

Considering $\Delta^{\prime}_{i}$ ($i=1,\ldots,n$) and $\Delta$, it can be
seen that for every $i=1,\ldots,n$ and every $q_{i}$ in $D_{i}^{\prime*}$
there exists $q$ in $D^{*}$ such that $q_{i}\sqsubseteq q$. Consequently, for
every $i=1,\ldots,n$, and every $q$ in ${\cal T}$,
$[q^{+}]^{\prime}_{i}\subseteq q^{+}$, where $q^{+}$ denotes the closure of
$q$ in $\Delta$. Therefore, if for some $i$, $\Delta^{\prime}_{i}\vdash t$,
respectively $\Delta^{\prime}_{i}\mid\sim t$, then $\Delta\vdash t$,
respectively $\Delta\mid\sim t$, and so, for every $i=1,\ldots,n$,
$v_{\Delta^{\prime}_{i}}(t)\triangleleft v_{\Delta}(t)$. The proposition
follows from the transitivity of $\triangleleft$ and from the fact that
$\overline{\oplus}$ defines the least upper bound (lub) with respect to
$\triangleleft$, in the same way as $\oplus$ defines the lub with respect to
$\preceq_{k}$. $\Box$

In what follows, we identify cases where the equality
$\overline{\bigoplus}\,_{i=1}^{i=n}\,v_{\Delta_{i}}(t)=v_{\Delta}(t)$ holds
and cases where it does not. To simplify, we assume that $n=2$.

First, if for $i=1$ or $i=2$, $v_{\Delta_{i}}(t)={\tt inc}$, then the
proposition implies that $v_{\Delta}(t)={\tt inc}$, because ${\tt inc}$ is
maximal with respect to $\triangleleft$. In this case, the equality always
holds. Another case where the equality holds is if $v_{\Delta_{1}}(t)={\tt
true}$ and $v_{\Delta_{2}}(t)={\tt false}$. Indeed, in this case we have
$\Delta\vdash t$ and $\Delta\mid\sim t$, showing that $v_{\Delta}(t)={\tt
inc}$. Therefore,
$v_{\Delta}(t)=v_{\Delta_{1}}(t)\,\overline{\oplus}\,v_{\Delta_{2}}(t)$.

To see cases where the equality
$v_{\Delta_{1}}(t)\,\overline{\oplus}\,v_{\Delta_{2}}(t)=v_{\Delta}(t)$ does
not hold, let $U=\\{A,B,C\\}$, $\Delta_{1}=(\\{abc\\},\emptyset)$ and
$\Delta_{2}=(\\{bc^{\prime}\\},\\{B\to C\\})$.

In this case, $\Delta=(D,{\cal FD})$ where $D=\\{abc,bc^{\prime}\\}$ and
${\cal FD}=\\{B\to C\\}$. Hence, $D^{*}=\\{abc,abc^{\prime}\\}$ and ${\sf
Inc}(\Delta)=\\{b,bc,bc^{\prime},abc,abc^{\prime}\\}$, and so:

  * •

$v_{\Delta_{1}}(b)=v_{\Delta_{2}}(b)={\tt true}$, whereas $v_{\Delta}(b)={\tt
inc}$.

  * •

$v_{\Delta_{1}}(bc^{\prime})={\tt unkn}$, $v_{\Delta_{2}}(bc^{\prime})={\tt
true}$, thus implying that $v_{1}\oplus v_{2}={\tt true}$, whereas
$v_{\Delta}(bc^{\prime})={\tt inc}$.

We further illustrate Proposition 6 in the the context of our introductory
example.

###### Example 11

We recall that in our introductory example, we have two data sources
$\Delta_{1}=(D_{1},{\cal FD})$ and $\Delta_{2}=(D_{2},{\cal FD})$, where
${\cal FD}=\\{ID\to K,ID\to C\\}$.

Based on $D_{1}$ and $D_{2}$ as shown in Figure 1 and displayed in Figure 4,
applying Algorithm 2 produces $D_{1}^{*}$ and $D_{2}^{*}$ also shown in Figure
4, and returns ${\sf Inc}(\Delta_{1})={\sf Inc}(\Delta_{2})=\emptyset$.

$D_{1}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ |  | $m^{\prime}$ |
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ |
| $i_{3}$ |  | $m$ |

$D_{2}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ |  | $c$
| $i_{2}$ | $k^{\prime}$ |  | $c^{\prime}$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ |
| $i_{3}$ | $k^{\prime}$ |  |

$D_{1}^{*}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ | $k$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ | $c$
| $i_{3}$ |  | $m$ |

$D_{2}^{*}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ |  | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ | $c^{\prime}$
| $i_{3}$ | $k^{\prime}$ |  |

Figure 4: The source tables of our introductory example and their chased
versions

Hence, as already mentioned, $\Delta_{1}$ and $\Delta_{2}$ are consistent.
Referring to Example 10 and Figure 2, applying Proposition 6 entails the
following:

  * •

$v_{\Delta_{1}}(i_{1},k,m,c)={\tt true}$, $v_{\Delta_{2}}(i_{1},k,m,c)={\tt
unkn}$ and $v_{\Delta}(i_{1},k,m,c)={\tt true}$.
$v_{\Delta_{1}}(i_{1},k,m^{\prime},c)={\tt true}$,
$v_{\Delta_{2}}(i_{1},k,m^{\prime},c)={\tt unkn}$ and
$v_{\Delta}(i_{1},k,m^{\prime},c)={\tt true}$.
These are cases of equality because ${\tt true}\,\overline{\oplus}\,{\tt
unkn}={\tt true}$.

  * •

$v_{\Delta_{1}}(i_{2},c)={\tt true}$, $v_{\Delta_{2}}(i_{2},c)={\tt false}$
and $v_{\Delta}(i_{2},c)={\tt inc}$.
This is another case of equality because ${\tt true}\,\overline{\oplus}\,{\tt
false}={\tt inc}$.

  * •

$v_{\Delta_{1}}(i_{2})={\tt true}$, $v_{\Delta_{2}}(i_{2})={\tt true}$ and
$v_{\Delta}(i_{2})={\tt inc}$.
This is a case where equality does not hold because ${\tt
true}\,\overline{\oplus}\,{\tt true}\neq{\tt inc}$. Notice however that ${\tt
true}\,\triangleleft\,{\tt inc}$ holds. $\Box$

##  6 Consistent Query Answering

In this section, considering true tuples and false tuples only (i.e.,
forgetting about false tuples), we address the important problem of consistent
query answering. We first provide a brief review of the abundant related
literature, and then, we show that our approach provides new insights in the
problem of consistent query answering. Moreover, we also argue that in our
approach, the ‘quality’ of such consistent answers can be assessed, based on
the notion of tuple truth value. However, this issue lies out of the scope of
the present paper, and will be the subject of further research in the next
future.

###  6.1 Related Work

The problem of query answering in presence of inconsistencies has motivated
important research efforts during the past two decades and is still the
subject of current research. As mentioned in the introductory section, the
most popular approaches in the literature are based on the notion of ‘repair’,
a repair of ${\cal D}$ being intuitively a consistent database ${\cal R}$ ‘as
close as possible’ to ${\cal D}$; and an answer to a query $Q$ is consistent
if it is present in every repair ${\cal R}$ of ${\cal D}$.

However, it has been recognized that generating all repairs is difficult to
implement - if not unfeasible. This is a well known problem in practice which
explains, for instance, why data cleansing is a very important but tedious
task in the management of databases and data warehouses RahmD00 . This issue
has been thoroughly investigated in LivshitsKR20 , where it has been shown
that computing repairs of a given relational table in the presence of
functional dependencies is either polynomial or APX-complete222Roughly, APX is
the set of NP optimization problems that allow polynomial-time approximation
algorithms (source: Wikipedia)., depending on the form of the functional
dependencies. The reader is referred to AfratiK09  for theoretical results on
the complexity of testing whether ${\cal R}$ is a repair of ${\cal D}$, when
considering a more generic context than we do in this work (more than one
table and constraints other than functional dependencies). A Prolog based
approach for the generation of repairs can be found in ArieliDNB06 .

Dealing with repairs without generating them is thus an important issue, also
known as Consistent Query Answering in Inconsistent Databases. One of the
first works in this area is Bry97  and the problem has since been addressed in
the context of various database models (mainly the relational model or
deductive database models) and under various types of constraints (first order
constraints, key constraints, key foreign-key constraints). Seminal papers in
this area are ArenasBC99  and Wijsen09 , while an overview of works in this
area can be found in Bertossi2011 .

The problem considered in all these works can be stated as follows: Given a
database ${\cal D}$ with integrity constraints ${\cal IC}$, assume that ${\cal
D}$ is inconsistent with respect to ${\cal IC}$. Under this assumption, given
a query $Q$ against ${\cal D}$, what is the consistent answer to $Q$? The
usual approach to alleviate the impact of inconsistent data on the answers to
a query is to consider that an answer to $Q$ is consistent if it is present in
every repair ${\cal R}$ of ${\cal D}$.

Complexity results regarding the computation of the consistent answer have
been widely studied in CaliLR03 . For example one important case is when
${\cal IC}$ consists in having one key constraint per database relation and
$Q$ is a conjunctive query containing no self-join (i.e., no join of a
relation with itself). In this case computing the consistent answer is
polynomial whereas if self-joins occur then the problem is co-NP-complete.

Another important problem in considering repairs is that there are many ways
of defining the notion of repair. This is so because there are many ways of
defining a distance between two database instances, and there is no consensus
as to the ‘best’ definition of distance. Although the distance based on
symmetric difference seems to be the most popular, other distances exist as
well based for example on sub-sets, on cardinality, on updates or on
homomorphism Wijsen05 . Notice in this respect that the results in
LivshitsKR20  are set for two distances: one based on sub-sets and one based
on updates.

###  6.2 Consistent Query Answering in our Approach

In our work we do not use any notion of repair, thus we avoid the above
problem of choosing among all possible ways of defining repairs. Instead, we
use set theoretic semantics for tuples and functional dependencies that allow
us to associate each tuple with one truth value among true, false,
inconsistent or unknown.

In what follows, we outline the process of consistent query answering in our
approach, and then compare it to the approaches based on repairs. In doing so
we follow the intuition of the repairs-approach where an answer to a query is
consistent if it is present in every repair; and we transpose it in our
approach by considering that a tuple is in the consistent answer to the query
if its truth value is true in the sense of our model.

As usual when dealing with a single table with nulls, a query $Q$ is an SQL-
like expression of one of the following two forms:

$Q:$ SELECT $X$ or $Q:$ SELECT $X$ WHERE $\Gamma$

In either of these forms, $X$ is an attribute list seen as a relation schema,
and in the second form, the WHERE clause specifies a selection condition
$\Gamma$. It should thus be clear that, as in SQL, the where clause in a query
is optional. The generic form of a query $Q$ is denoted by $Q:{\sf
SELECT}~{}X~{}{\sf[WHERE~{}}\Gamma{\sf]}$.

A selection condition $\Gamma$ is a well formed formula involving the usual
connectors $\neg$, $\vee$ and $\wedge$ and built up from atomic boolean
comparisons of one of the forms $A\,\theta\,a$ or $A\,\theta\,A^{\prime}$,
where $\theta$ is a comparison predicate, $A$ and $A^{\prime}$ are attributes
in $U$ whose domain elements are comparable through $\theta$, and $a$ is in
$dom(A)$.

Moreover, a tuple $t$ satisfies $A\,\theta\,a$ if $A$ is in $sch(t)$ and if
$t.A\,\theta\,a$ holds, and $t$ satisfies $A\,\theta\,A^{\prime}$ if $A$ and
$A^{\prime}$ are in $sch(t)$ and if $t.A\,\theta\,t.A^{\prime}$ holds. Based
on this, determining whether $t$ satisfies $\Gamma$ follows the rules usual in
First Order Logic regarding connectors. For instance, referring to our
introductory example, the tuple $t=(k,m)$ such that $sch(t)=KM$ satisfies the
conditions $(K=k)$ and $(M=m\vee C=c^{\prime})$ but does not satisfy the
condition $(M=K)$, assuming that $m$ and $k$ are comparable but distinct
constants.

Given $\Delta=(D,{\cal FD})$, the answer to $Q$ in $\Delta$ is the set of the
restrictions to $X$ of all tuples $t$ in $D^{*}$ such that $X\subseteq sch(t)$
and such that $t$ satisfies $\Gamma$, when present in $Q$. It follows that
answers to queries contain only tuples without nulls.

Now, roughly speaking, the consistent answer to $Q$ is the set of all true
tuples defined over $X$ that satisfy the condition in $Q$. However, as the
following example shows, this rough definition should be carefully stated in
particular with regard to the functional dependencies to be taken into account
for tuple truth value.

###### Example 12

In the context of our introductory example, let $\Delta=(D,{\cal FD})$ where
${\cal FD}=\\{Id\to K,Id\to C\\}$ and where $D$ is displayed in Figure 1. As
seen in Example 8, Algorithm 2 returns $D^{*}$ as shown below and $inc({\cal
FD})=\\{inc(Id\to K),inc(Id\to C)\\}$ where $inc(Id\to K)=\emptyset$ and
$inc(Id\to C)=\\{i_{2}\\}$.

$D^{*}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ | $k$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c^{\prime}$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ | $c^{\prime}$
| $i_{3}$ | $k^{\prime}$ | $m$ |

We also recall from Example 10 that ${\sf Inc}(\Delta)$ is defined by:

${\sf Inc}(\Delta)=$ | $\\{t~{}|~{}i_{2}\sqsubseteq t\sqsubseteq(i_{2},k^{\prime},m^{\prime},c)\\}\cup\\{t~{}|~{}i_{2}\sqsubseteq t\sqsubseteq(i_{2},k^{\prime},m^{\prime\prime},c)\\}\,\cup$
---|---
| $\\{t~{}|~{}i_{2}\sqsubseteq
t\sqsubseteq(i_{2},k^{\prime},m^{\prime},c^{\prime})\\}\cup\\{t~{}|~{}i_{2}\sqsubseteq
t\sqsubseteq(i_{2},k^{\prime},m^{\prime\prime},c^{\prime})\\}$

Let $Q_{1}$ and $Q_{2}$ be two queries (without conditions) as defined below:

$Q_{1}:{\sf SELECT}$ $Id,K,C$ and $Q_{2}:{\sf SELECT}$ $Id,K,M$

Projecting the tuples in $D^{*}$ over the attributes $Id$, $K$, $C$ for
$Q_{1}$ and over $Id$, $K$, $M$ for $Q_{2}$ produces the tables $\Pi_{1}$ and
$\Pi_{2}$ shown below.

$\Pi_{1}$ | $Id$ | $K$ | $C$
---|---|---|---
| $i_{1}$ | $k$ | $c$
| $i_{2}$ | $k^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $c^{\prime}$
$\Pi_{2}$ | $Id$ | $K$ | $M$
---|---|---|---
| $i_{1}$ | $k$ | $m$
| $i_{1}$ | $k$ | $m^{\prime}$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$
| $i_{3}$ | $k^{\prime}$ | $m$

Since in these two tables, the tuples whose $Id$-value is $i_{2}$, are
inconsistent in $\Delta$, it seems justified to exclude them from any
consistent answer. In other words, according to this intuition, the expected
consistent answers to $Q_{1}$ and $Q_{2}$ are respectively $\\{(i_{1},k,c)\\}$
and $\\{(i_{1},k,m),(i_{1},k,m^{\prime}),(i_{3},k^{\prime},m)\\}$.

We explain below why it makes sense to exclude the two tuples in the case of
$Q_{1}$, whereas the removal in the case of $Q_{2}$ is debatable.

  1. 1.

Regarding $Q_{1}$, the tuples $(i_{2},k^{\prime},c)$ and
$(i_{2},k^{\prime},c^{\prime})$ in $\Pi_{1}$ clearly violate $Id\to C$ from
${\cal FD}$, and thus can not occur in the consistent answer to $Q_{1}$.

  2. 2.

Regarding $Q_{2}$ however, no functional dependency is violated by the tuples
in $\Pi_{2}$, and thus, there is no reason for removing any of them when
producing the consistent answer to $Q_{2}$.

Another way of explaining this situation is to notice that, in $D^{*}$, the
only non satisfied functional dependency is $Id\to C$ and that

  1. 1.

attributes $Id$ and $C$ occur in the SELECT clause of $Q_{1}$, making it
necessary to check functional dependency satisfaction;

  2. 2.

attribute $C$ does not occur in the SELECT clause of $Q_{2}$, implying that
checking functional dependency satisfaction makes no sense.

Another important point to take into account is the impact of selection
conditions on tuple truth value in the answer to a query. To illustrate this
point, first notice that, when considering the query $Q_{1}$ the only
functional dependency to be checked is $Id\to C$, with respect to which the
table $\Pi_{1}$ shows inconsistencies regarding $i_{2}$. However, let now
$Q^{\prime}_{1}$ be the query defined by:

$Q^{\prime}_{1}:{\sf SELECT}$ $Id,K,C$ WHERE $C=c^{\prime}$

Only the fifth and sixth tuples in $D^{*}$ satisfy the selection condition and
thus, the only possible tuple in the consistent answer to $Q^{\prime}_{1}$ is
$(i_{2},k^{\prime},c^{\prime})$, which alone, trivially satisfies the
functional dependency $Id\to C$.

However, the consistency of the answer to $Q^{\prime}_{1}$ may seem counter-
intuitive, since the tuple $(i_{2},k^{\prime},c^{\prime})$ is seen as
inconsistent in the answer to $Q_{1}$, where the same attributes are involved.
To cope with this counter-intuitive situation, we rather consider that the
consistent answer of $Q^{\prime}_{1}$ is empty, i.e., that consistency has to
be checked independently from selection conditions, based only on the
functional dependencies involving only attributes from the SELECT clause in
the query.

In what follows, we provide the formalism and the definitions to account for
these remarks. $\Box$

Given a table $D$ over $U$, a subset $X$ of $U$ and a selection condition
$\Gamma$, we denote by $\sigma_{\Gamma}(D)$, $\pi_{X}(D)$ and $\pi_{X}({\cal
FD})$ the following sets:

  * •

$\sigma_{\Gamma}(D)$ is the set of all tuples $t$ in $D$ such that $t$
satisfies $\Gamma$.

  * •

$\pi_{X}(D)$ is the set of the restrictions to $X$ of all tuples in $D$ whose
schema contains $X$; that is $\pi_{X}(D)=\\{t~{}|~{}(\exists q\in
D)(X\subseteq sch(q),~{}t=q.X)\\}$.

  * •

$\pi_{X}({\cal FD})$ is the set of all functional dependencies that involve
attributes in $X$ only; that is $\pi_{X}({\cal FD})=\\{(Y\to B)\in{\cal
FD}~{}|~{}YB\subseteq X\\}$.

These notation are used in the following definition where the notion of
consistent answer to a query is introduced.

###### Definition 6

Given $\Delta=(D,{\cal FD})$ and $Q:{\sf SELECT}$ $X$ [WHERE $\Gamma$], let
$\Delta_{X}$ be defined by $\Delta_{X}=(\pi_{X}(D^{*}),\pi_{X}({\cal FD}))$.

The answer to $Q$ in $\Delta$, denoted by $ans_{\Delta}(Q)$, is the set
$\pi_{X}(\sigma_{\Gamma}(D^{*}))$. Moreover, for every tuple $x$ in
$ans_{\Delta}(Q)$, the truth value of $x$ in $ans_{\Delta}(Q)$ is defined by
$v_{\Delta_{X}}(x)$.

The consistent answer to $Q$ in $\Delta$, denoted by $ans^{+}_{\Delta}(Q)$, is
the set of all tuples $x$ in $ans_{\Delta}(Q)$ such that
$v_{\Delta_{X}}(x)={\tt true}$.

It is important to notice that, according to Definition 6, given $\Delta$ and
$Q$, two distinct truth values may be given to a tuple $t$, namely, its truth
value in $\Delta$, i.e., $v_{\Delta}(t)$, and its truth value in $\Delta_{X}$,
i.e., $v_{\Delta_{X}}(t)$. Since these truth values are not determined using
the same set of functional dependencies, they might be distinct.

Referring to Example 12, based on the notation introduced in Definition 6, for
$X_{1}=Id\,K\,C$, $\pi_{X_{1}}({\cal FD})={\cal FD}$, and so,
$\Delta_{X_{1}}=(\Pi_{1},{\cal FD})$. In this case, for every tuple $x$ over
$X_{1}$, $v_{\Delta_{X_{1}}}(x)=v_{\Delta}(x)$. On the other hand, for
$X_{2}=Id\,K\,M$, $\pi_{X_{2}}({\cal FD})=\\{Id\to K\\}$, and so,
$\Delta_{X_{2}}=(\Pi_{2},\\{Id\to K\\})$. Since $\Pi_{2}$ satisfies $Id\to K$,
for $x=(i_{2},k^{\prime},m^{\prime})$, $v_{\Delta_{X_{2}}}(x)={\tt true}$.
However, as $x$ is a super-tuple of $i_{2}$, we have $v_{\Delta}(x)={\tt
inc}$, showing that $v_{\Delta_{X_{2}}}(x)\neq v_{\Delta}(x)$.

Algorithm 5 Consistent answer $ans^{+}_{\Delta}(Q)$

0: A query $Q:{\sf SELECT}$ $X$ [WHERE $\Gamma$], $\Delta^{*}=(D^{*},{\cal
FD})$ and $inc({\cal FD})$

0: The set $ans^{+}_{\Delta}(Q)$

1: $ans^{+}_{\Delta}(Q):=\emptyset$

2: for all $t$ in $D^{*}$ do

3: if $sch(t)$ contains all attributes in $X$ then

4: if for every $Y\to B$ in $\pi_{X}({\cal FD})$, $t.Y$ is not in $inc(Y\to
B)$ then

5: if $t$ satisfies $\Gamma$ then

6: // This test always succeeds if $Q$ involves no selection condition

7: $ans^{+}_{\Delta}(Q):=ans^{+}_{\Delta}(Q)\cup\\{t.X\\}$

8: return $ans^{+}_{\Delta}(Q)$

The following proposition shows that $ans^{+}_{\Delta}(Q)$ is computed from
$D^{*}$ and $inc({\cal FD})$, using Algorithm 5.

###### Proposition 7

Given $\Delta=(D,{\cal FD})$ and $Q:{\sf SELECT}$ $X$ [WHERE $\Gamma$],
Algorithm 5 correctly computes $ans^{+}_{\Delta}(Q)$.

###### Proof

In this proof, denoting by $ans$ the output of Algorithm 5, we prove that
$ans=ans^{+}_{\Delta}(Q)$. To prove that $ans\subseteq ans^{+}_{\Delta}(Q)$,
we notice that, by Algorithm 5, every tuple $x$ in $ans$ $x$ is the projection
over $X$ of a tuple $t$ in $D^{*}$ satisfying $\Gamma$. Thus, $x$ belongs to
$\pi_{X}(\sigma_{\Gamma}(D^{*}))$, that is to $ans_{\Delta}(Q)$. Moreover,
since for every $t$ in $D^{*}$ such that $t.X$ is in $ans$ and every $Y\to B$
in $\pi_{X}({\cal FD})$, $t.Y$ is not in $inc(Y\to B)$, it holds that
$v_{\Delta_{X}}(x)={\tt true}$. It thus follows that $x$ is in
$ans^{+}_{\Delta}(Q)$.

Conversely, assuming that $x$ is in $ans^{+}_{\Delta}(Q)$ implies that $x$ is
in $ans_{\Delta}(Q)$. Hence, $D^{*}$ contains a tuple $t$ that satisfies
$\Gamma$ and $t.X=x$, meaning that $sch(t)$ contains $X$ and that $t$
satisfies the if-condition on line 5 in Algorithm 5. Moreover, since we also
have $v_{\Delta_{X}}(x)={\tt true}$, for every $Y\to B$ in $\pi_{X}({\cal
FD})$, $t.Y$ cannot be in $inc(Y\to B)$. This shows that the if-condition on
line 4 in Algorithm 5 is satisfied, and thus that $x$ belongs to $ans$, which
completes the proof. $\Box$

Regarding complexity, Proposition 7 shows that, assuming that $D^{*}$ has been
computed, the computation of the consistent answer is linear in the size of
$D^{*}$.

If we assume moreover that ${\sf Inc}(\Delta)$ has also been computed,
labelling each tuple in $ans^{+}_{\Delta}(Q)$ by its truth value in $\Delta$
is an option to investigate, because it has been seen from Definition 6 that
the truth value of a tuple $t$ in $\Delta$, i.e., $v_{\Delta}(t)$, may be
different than the truth value of $t$ in $ans_{\Delta}(Q)$, i.e.,
$v_{\Delta_{X}}(t)$.

Knowing that a tuple in the consistent answer, thus having truth value true in
this answer, has truth value inc in the database it comes from, may indeed be
relevant in case the user is interested in data quality, as is the case when
dealing with data lakes MEDES . Investigating further issues related to query
answering in our approach, including issues related to data quality is the
subject of future work.

###### Example 13

Running Algorithm 5 with the queries $Q_{1}$, $Q^{\prime}_{1}$ and $Q_{2}$ as
in Example 12, returns $ans^{+}_{\Delta}(Q_{1})=\\{(i_{1},k,c)\\}$,
$ans^{+}_{\Delta}(Q^{\prime}_{1})=\emptyset$ and
$ans^{+}_{\Delta}(Q_{2})=\\{(i_{1},k,m),$ $(i_{1},k,m^{\prime}),$
$(i_{2},k^{\prime},m^{\prime}),$ $(i_{2},k^{\prime},m^{\prime\prime}),$
$(i_{3},k^{\prime},m)\\}$, as expected.

As earlier noticed regarding $ans^{+}_{\Delta}(Q_{2})$, for
$x=(i_{2},k^{\prime},m^{\prime})$ or $x=(i_{2},k^{\prime},m^{\prime\prime})$,
we have $v_{\Delta}(x)\neq v_{\Delta_{X_{2}}}(x)$. In this case, smart users
could find it relevant to be informed of this situation, which can be done by
labelling the two tuples $(i_{2},k^{\prime},m^{\prime})$ and
$(i_{2},k^{\prime},m^{\prime\prime})$ by ${\tt inc}$, that is, their truth
value in $\Delta$. We notice that this piece of information cannot be provided
by any of the existing approaches.

Considering now the query $Q_{3}:{\sf SELECT}$ $M,C$ WHERE $K=k^{\prime}$,
Algorithm 5 discards the first two tuples of $D^{*}$ (because their $K$-value
is not equal to $k^{\prime}$), and also the last tuple of $D^{*}$ (as this
tuple has no $C$-value). When processing the remaining four tuples in $D^{*}$,
no functional dependency has to be taken care of, and so, we obtain
$ans^{+}_{\Delta}(Q_{3})=\\{(m^{\prime},c),$ $(m^{\prime},c^{\prime}),$
$(m^{\prime\prime},c),$ $(m^{\prime\prime},c^{\prime})\\}$. $\Box$

###  6.3 Comparison with Repair-Based Approaches

Comparing our approach with approaches to consistent query answering from the
literature, we point out that when constraints are functional dependencies
only, as in our approach, repairs are defined using set-theoretic inclusion as
follows.

###### Definition 7

Given $\Delta=(D,{\cal FD})$, denoting by $D^{*}$ the chased table associated
with $D$, a repair of $\Delta$ is a table $R$ over $U$ such that: (1)
$R\subseteq D^{*}$, (2) $R$ satisfies ${\cal FD}$, and (3) $R$ is maximal
among the sets satisfying $(1)$ and $(2)$.

We notice that in the above definition, inclusion is understood in its strict
set-theoretic meaning, disregarding the presence of nulls in the tuples. For
example $\\{ab,a^{\prime}bc\\}\subseteq\\{abc,a^{\prime}bc\\}$ does not hold
whereas $\\{ab,a^{\prime}bc\\}\subseteq\\{ab,abc,a^{\prime}bc\\}$ does.

Repairs of $\Delta$ can be generated based on the tuples stored in $inc({\cal
FD})$ according to the following algorithm:

$R:=D^{*}$

for all $X\to A$ in ${\cal FD}$ do

for all $x$ in $inc(X\to A)$ do

choose an $A$-value $a$ among all $\alpha$ such that $x\alpha$ occurs in
$D^{*}$

$R:=R\setminus\\{q~{}|~{}XA\subseteq sch(q),q.X=x,q.A\neq a\\}$

return $R$

Indeed, based on Definition 7, $R$ as computed above is a repair because: (1)
$R\subseteq D^{*}$ clearly holds, (2) $R$ satisfies ${\cal FD}$ holds since
for every $X\to A$ in ${\cal FD}$, there exist $q$ and $q^{\prime}$ in $R$
such that $q.X=q^{\prime}.X$ and $q.A\neq q^{\prime}.A$, and (3) $R$ is
maximal because inserting any of the removed tuples leads to violation of a
functional dependency.

Given a query $Q:{\sf SELECT}$ $X$ [WHERE $\Gamma$], denoting by $Rep(\Delta)$
the set of all repairs of $\Delta$, the consistent answer to $Q$ based on
repairs can be formally defined in the following two ways:

  1. 1.

$ans^{\downarrow}_{\Delta}(Q)=\pi_{X}\left(\bigcap_{R\in
Rep(\Delta)}\sigma_{\Gamma}(R)\right)$.

  2. 2.

$ans^{\uparrow}_{\Delta}(Q)=\bigcap_{R\in
Rep(\Delta)}\pi_{X}(\sigma_{\Gamma}(R))$.

Intuitively, $ans^{\downarrow}_{\Delta}(Q)$ is obtained by evaluating the
query against the intersection of all repairs, whereas
$ans^{\uparrow}_{\Delta}(Q)$ is obtained by evaluating the query against each
repair and by taking the intersection of all these answers.

###### Example 14

Computing the repairs of $D^{*}$ as shown in Example 12 produces the tables
$R_{1}$ and $R_{2}$ shown below.

$R_{1}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ | $k$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ | $c$
| $i_{3}$ | $k^{\prime}$ | $m$ |
$R_{2}$ | $Id$ | $K$ | $M$ | $C$
---|---|---|---|---
| $i_{1}$ | $k$ | $m$ | $c$
| $i_{1}$ | $k$ | $m^{\prime}$ | $c$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime}$ | $c^{\prime}$
| $i_{2}$ | $k^{\prime}$ | $m^{\prime\prime}$ | $c^{\prime}$
| $i_{3}$ | $k^{\prime}$ | $m$ |

Thus, regarding the queries $Q_{1}$, $Q^{\prime}_{1}$, $Q_{2}$ and $Q_{3}$ of
Example 12, we have:

  * •

$ans^{\downarrow}_{\Delta}(Q_{1})=\\{(i_{1},k,c)\\}$ ;
$ans^{\uparrow}_{\Delta}(Q_{1})=\\{(i_{1},k,c)\\}$

  * •

$ans^{\downarrow}_{\Delta}(Q^{\prime}_{1})=\emptyset$ ;
$ans^{\uparrow}_{\Delta}(Q^{\prime}_{1})=\emptyset$

  * •

$ans^{\downarrow}_{\Delta}(Q_{2})=\\{(i_{1},k,m),(i_{1},k,m^{\prime}),(i_{3},k^{\prime},m)\\}$
;
$ans^{\uparrow}_{\Delta}(Q_{2})=\\{(i_{1},k,m),(i_{1},k,m^{\prime}),(i_{2},k^{\prime},m^{\prime}),(i_{2},k^{\prime},m^{\prime\prime}),(i_{3},k^{\prime},m)\\}$

  * •

$ans^{\downarrow}_{\Delta}(Q_{3})=\emptyset$ ;
$ans^{\uparrow}_{\Delta}(Q_{3})=\emptyset$

It should be noticed that computing all repairs before computing the answers
is not realistic in practice. In what follows, we provide an efficient
algorithm to compute these answers and we prove that they are always ‘smaller’
with respect to set theoretic inclusion than the answers as defined in
Definition 6. $\Box$

Algorithm 6 Repair-based consistent answers $ans^{\downarrow}_{\Delta}(Q)$,
$ans^{\uparrow}_{\Delta}(Q)$

0: A query $Q:{\sf SELECT}$ $X$ [WHERE $\Gamma$], $\Delta^{*}=(D^{*},{\cal
FD})$ and $inc({\cal FD})$

0: The sets $ans^{\downarrow}(Q)$ and $ans^{\uparrow}(Q)$

1: $ans^{\downarrow}(Q):=\emptyset$ ; $ans^{\uparrow}(Q):=\emptyset$

2: for all $t$ in $D^{*}$ do

3: if $sch(t)$ contains all attributes in $X$ then

4: if $t$ satisfies $\Gamma$ then

5: // This test always succeeds if $Q$ involves no selection condition

6: if for every $Y\to B$ in ${\cal FD}$ such that $YB\subseteq sch(t)$, $t.Y$
is not in $inc(Y\to B)$ then

7: $ans^{\downarrow}(Q):=ans^{\downarrow}(Q)\cup\\{t.X\\}$

8: if for every $Y\to B$ in ${\cal FD}$ such that $YB\subseteq sch(t)$ and
$B\in X$, $t.Y$ is not in $inc(Y\to B)$ then

9: $ans^{\uparrow}(Q):=ans^{\uparrow}(Q)\cup\\{t.X\\}$

10: return $ans^{\downarrow}(Q)$, $ans^{\uparrow}(Q)$

The following proposition deals with the computation of
$ans^{\downarrow}_{\Delta}(Q)$ and of $ans^{\uparrow}_{\Delta}(Q)$, and
compares these answers with $ans^{+}_{\Delta}(Q)$.

###### Proposition 8

Given $\Delta=(D,{\cal FD})$ and a query $Q:{\sf SELECT}$ $X$ [WHERE
$\Gamma$], Algorithm 6 correctly computes $ans^{\downarrow}_{\Delta}(Q)$ and
$ans^{\uparrow}_{\Delta}(Q)$. Moreover, the following holds:
$ans^{\downarrow}_{\Delta}(Q)\subseteq ans^{\uparrow}_{\Delta}(Q)\subseteq
ans^{+}_{\Delta}(Q)$.

###### Proof

See Appendix F. $\Box$

To illustrate the inclusions in Proposition 8, it can be seen from Example 13
and Example 14 that:

$-$
$ans^{\downarrow}_{\Delta}(Q_{1})=ans^{\uparrow}_{\Delta}(Q_{1})=ans^{+}_{\Delta}(Q_{1})$;
$-$
$ans^{\downarrow}_{\Delta}(Q^{\prime}_{1})=ans^{\uparrow}_{\Delta}(Q^{\prime}_{1})=ans^{+}_{\Delta}(Q^{\prime}_{1})$;
$-$ $ans^{\downarrow}_{\Delta}(Q_{2})\subset ans^{\uparrow}_{\Delta}(Q_{2})$
and $ans^{\uparrow}_{\Delta}(Q_{2})=ans^{+}_{\Delta}(Q_{2})$;
$-$ $ans^{\downarrow}_{\Delta}(Q_{3})=ans^{\uparrow}_{\Delta}(Q_{3})$ and
$ans^{\uparrow}_{\Delta}(Q_{3})\subset ans^{+}_{\Delta}(Q_{3})$.

Regarding complexity, is important to note that, if the chased table $D^{*}$
is available then any of the three ways to compute consistent query answers is
linear in the size of $D^{*}$. Moreover, when providing any of these
consistent answers, our approach allows for pointing to the user possible
problematic tuples, namely those tuples that are inconsistent in $\Delta$,
although not inconsistent in the answer.

##  7 Concluding Remarks

In this paper we have introduced a novel approach to handle inconsistencies in
a table with nulls and functional dependencies. Our approach uses set
theoretic semantics and relies on an extended version of the well known chase
procedure to associate every possible tuple with one of the four truth values
true, false, inconsistent and unknown. Moreover, we have seen that true and
inconsistent tuples can be computed in time polynomial in the size of the
input table. We have also seen that our approach applies to consistent query
answering and we have shown that it provides larger answers than the repair-
based approaches.

Building upon these results, we currently pursue four lines of research: $(1)$
applying our approach to the particular but important case of key-foreign key
constraints in the context of a star schema or a snow-flake schema; $(2)$
designing incremental algorithms to improve performance in case of updates,
$(3)$ extending our approach to constraints other than functional
dependencies, such as inclusion dependencies as done in BravoB06 , (4)
investigating the issue of data quality in the framework of our approach, and
$(5)$ extending our approach to account for the presence of tuples declared as
false.

## Declarations

Author contributions: The two authors contributed to the study, conception and
design. Both read and approved the submitted manuscript.

Funding: No funds, grants, or other support was received for conducting this
study.

Financial interests: N/A.

Non-financial interests: N/A.

Data availability: Data sharing is not applicable to this article as no
datasets were generated or analyzed during the current study.

## References

  * (1) Foto N. Afrati and Phokion G. Kolaitis.  Repair checking in inconsistent databases: algorithms and complexity.  In Ronald Fagin, editor, Database Theory - ICDT 2009, 12th International Conference,Proceedings, volume 361 of ACM International Conference Proceeding Series, pages 31–41. ACM, 2009.
  * (2) Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki.  Consistent query answers in inconsistent databases.  In Victor Vianu and Christos H. Papadimitriou, editors, Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Pennsylvania, USA, pages 68–79. ACM Press, 1999.
  * (3) Ofer Arieli and Arnon Avron.  The value of the four values.  Artif. Intell., 102(1):97–141, 1998.
  * (4) Ofer Arieli, Marc Denecker, Bert Van Nuffelen, and Maurice Bruynooghe.  Computational methods for database repair by signed formulae.  Ann. Math. Artif. Intell., 46(1-2):4–37, 2006.
  * (5) Nuel D. Belnap.  A useful four-valued logic.  In J. Michael Dunn and George Epstein, editors, Modern Uses of Multiple-Valued Logic, pages 5–37”, isbn=”978–94–010–1161–7, Dordrecht, 1977\. Springer Netherlands.
  * (6) Leopoldo E. Bertossi.  Database Repairing and Consistent Query Answering.  Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.
  * (7) Loreto Bravo and Leopoldo E. Bertossi.  Semantically correct query answers in the presence of null values.  In Torsten Grust, Hagen Höpfner, Arantza Illarramendi, Stefan Jablonski, Marco Mesiti, Sascha Müller, Paula-Lavinia Patranjan, Kai-Uwe Sattler, Myra Spiliopoulou, and Jef Wijsen, editors, Current Trends in Database Technology - EDBT 2006, EDBT 2006 Workshops PhD, DataX, IIDB, IIHA, ICSNW, QLQP, PIM, PaRMA, and Reactivity on the Web, Munich, Germany, March 26-31, 2006, Revised Selected Papers, volume 4254 of Lecture Notes in Computer Science, pages 336–357. Springer, 2006.
  * (8) François Bry.  Query answering in information systems with integrity constraints.  In Sushil Jajodia, William List, Graeme W. McGregor, and Leon Strous, editors, Integrity and Internal Control in Information Systems, volume 109 of IFIP Conference Proceedings, pages 113–130. Chapman Hall, 1997\.
  * (9) Andrea Calì, Domenico Lembo, and Riccardo Rosati.  On the decidability and complexity of query answering over inconsistent and incomplete databases.  In Frank Neven, Catriel Beeri, and Tova Milo, editors, Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 260–271. ACM, 2003.
  * (10) S. Ceri, G. Gottlob, and L. Tanca.  Logic Programming and Databases.  Surveys in Computer Science, Springer Verlag, 1990.
  * (11) Stavros S. Cosmadakis, Paris C. Kanellakis, and Nicolas Spyratos.  Partition semantics for relations.  J. Comput. Syst. Sci., 33(2):203–233, 1986.
  * (12) Ronald Fagin, Alberto O. Mendelzon, and Jeffrey D. Ullman.  A simplified universal relation assumption and its properties.  ACM Trans. Database Syst., 7(3):343–360, 1982.
  * (13) Melvin Fitting.  Bilattices and the semantics of logic programming.  J. Log. Program., 11(1&2):91–116, 1991.
  * (14) Dominique Laurent.  4-valued semantics under the OWA: A deductive database approach.  In Giorgos Flouris, Dominique Laurent, Dimitris Plexousakis, Nicolas Spyratos, and Yuzuru Tanaka, editors, Information Search, Integration, and Personalization - 13th International Workshop, ISIP, Revised Selected Papers, volume 1197 of Communications in Computer and Information Science, pages 101–116. Springer, 2019.
  * (15) Ester Livshits, Benny Kimelfeld, and Sudeepa Roy.  Computing optimal repairs for functional dependencies.  ACM Trans. Database Syst., 45(1):4:1–4:46, 2020.
  * (16) Cedrine Madera and Anne Laurent.  The next information architecture evolution: The data lake wave.  In Proceedings of the 8th International Conference on Management of Digital EcoSystems, MEDES, pages 174–180, New York, NY, USA, 2016. ACM.
  * (17) Francesco Parisi and John Grant.  Inconsistency measures for relational databases.  CoRR, abs/1904.03403, 2019.
  * (18) Erhard Rahm and Hong Hai Do.  Data cleaning: Problems and current approaches.  IEEE Data Eng. Bull., 23(4):3–13, 2000.
  * (19) Franck Ravat and Yan Zhao.  Data lakes: Trends and perspectives.  In Sven Hartmann, Josef Küng, Sharma Chakravarthy, Gabriele Anderst-Kotsis, A Min Tjoa, and Ismail Khalil, editors, Database and Expert Systems Applications - 30th International Conference, DEXA, Proceedings, Part I, volume 11706 of Lecture Notes in Computer Science, pages 304–313. Springer, 2019.
  * (20) Raymond Reiter.  On closed world data bases.  In Hervé Gallaire and Jack Minker, editors, Logic and Data Bases, Symposium on Logic and Data Bases, Centre d’études et de recherches de Toulouse, France, 1977, Advances in Data Base Theory, pages 55–76, New York, 1977. Plemum Press.
  * (21) Nicolas Spyratos.  The partition model: A deductive database model.  ACM Trans. Database Syst., 12(1):1–37, 1987.
  * (22) Nicolas Spyratos and Christophe Lécluse.  Incorporating functional dependencies in deductive query answering.  In Proceedings of the Third International Conference on Data Engineering, February 3-5, 1987, Los Angeles, California, USA, pages 658–664. IEEE Computer Society, 1987.
  * (23) Alexis Tsoukiàs.  A first order, four-valued, weakly paraconsistent logic and its relation with rough sets semantics.  Foundations of Computing and Decision Sciences, 27(2):77–96, 2002\.
  * (24) Jeffrey D. Ullman.  Principles of Databases and Knowledge-Base Systems, volume 1-2.  Computer Science Press, 1988.
  * (25) Moshe Y. Vardi.  The universal-relation data model for logical independence.  IEEE Softw., 5(2):80–85, 1988.
  * (26) Jef Wijsen.  Database repairing using updates.  ACM Trans. Database Syst., 30(3):722–768, 2005.
  * (27) Jef Wijsen.  On the consistent rewriting of conjunctive queries under primary key constraints.  Inf. Syst., 34(7):578–601, 2009.

##  Appendix A Proof of Lemma 1

Lemma 1. For every $\Delta=(D,{\cal FD})$, the sequence
$\left(\mu_{i}\right)_{i\geq 0}$ has a unique limit $\mu^{*}$ that satisfies
that $\mu^{*}\models\Delta$. Moreover:

  1. 1.

For all $a_{1}$ and $a_{2}$ in the same attribute domain $dom(A)$, if
$\mu^{*}(a_{1})\cap\mu^{*}(a_{2})\neq\emptyset$ then there exist $X\to A$ in
${\cal FD}$ and $x$ over $X$ such that $\mu^{*}(x)\neq\emptyset$ and
$\mu^{*}(x)\subseteq\mu^{*}(a_{1})\cap\mu^{*}(a_{2})$.

  2. 2.

For all $\alpha$ and $\beta$, $\Delta\vdash(\alpha\sqcap\beta)$ holds if and
only if $\mu^{*}(\alpha)\cap\mu^{*}(\beta)\neq\emptyset$ holds.

###### Proof

We recall that the sequence $\left(\mu_{i}\right)_{i\geq 0}$ is defined by the
following steps:

  1. 1.

For every $t$ in $D$, assign a ‘fresh’ integer $id(t)$ to $t$;

  2. 2.

Let $\mu_{0}$ be the mapping defined for every domain constant $a$ by:
$\mu_{0}(a)=\\{id(t)~{}|~{}t\in D\mbox{ and }a\sqsubseteq t\\}$;

  3. 3.

While there exists $X\to A$ in ${\cal FD}$, $x$ over $X$ and $a$ in $dom(A)$
such that $\mu(xa)\neq\emptyset$ and $\mu(x)\not\subseteq\mu(a)$, define
$\mu_{i+1}$ by: $\mu_{i+1}(a)=\mu_{i}(a)\cup\mu_{i}(x)$ and
$\mu_{i+1}(\alpha)=\mu_{i}(\alpha)$ for any other constant $\alpha$.

The sequence $\left(\mu_{i}\right)_{i\geq 0}$ is increasing in the sense that
for every $\alpha$, $\mu_{i}(\alpha)\subseteq\mu_{i+1}(\alpha)$, and bounded
in the sense that for every $\alpha$,
$\mu_{i}(\alpha)\subseteq\\{id(t)~{}|~{}t\in\Delta\\}$. Hence the sequence has
a unique limit. Moreover, for every $t$ in $D$, $\mu^{*}(t)\neq\emptyset$
holds because $id(t)$ always belongs to $\mu^{*}(t)$, and $\mu^{*}\models{\cal
FD}$, because otherwise $\mu^{*}$ would not be the limit of the sequence.
Therefore $\mu^{*}\models\Delta$, which shows the first part of the lemma.

$(1)$ Regarding the first item in the second part of the lemma, we first
notice that by definition of $\mu_{0}$, we have
$\mu_{0}(a_{1})\cap\mu_{0}(a_{2})=\emptyset$, because it is not possible that
a tuple in $D$ has two distinct values over an attribute.

Since we assume that $\mu^{*}(a_{1})\cap\mu^{*}(a_{2})\neq\emptyset$, there
exists $i_{0}\geq 0$ such that
$\mu_{i_{0}}(a_{1})\cap\mu_{i_{0}}(a_{2})=\emptyset$ and
$\mu_{i_{0}+1}(a_{1})\cap\mu_{i_{0}+1}(a_{2})\neq\emptyset$. By definition of
the sequence $\left(\mu_{i}\right)_{i\geq 0}$, for $j=1,2$,
$\mu_{i_{0}+1}(a_{j})=\mu_{i_{0}}(a_{j})\cup M(a_{j})$ where $M(a_{j})$ is the
union of all $\mu_{i_{0}}(x_{j})$ such that $X_{j}\to A$ is in ${\cal FD}$,
$\mu_{i_{0}}(x_{j})\cap\mu_{i_{0}}(a_{j})\neq\emptyset$ and
$\mu_{i_{0}}(x_{j})\not\subseteq\mu_{i_{0}}(a_{j})$. Hence,

$\mu_{i_{0}+1}(a_{1})\cap\mu_{i_{0}+1}(a_{2})$ | $=(\mu_{i_{0}}(a_{1})\cup M(a_{1}))\cap(\mu_{i_{0}}(a_{2})\cup M(a_{2}))$
---|---
| $=(\mu_{i_{0}}(a_{1})\cap\mu_{i_{0}}(a_{2}))\cup(\mu_{i_{0}}(a_{1})\cap
M(a_{2}))~{}\cup~{}\qquad$
| $(M(a_{1})\cap\mu_{i_{0}}(a_{2}))\cup(M(a_{1})\cap M(a_{2}))$

Since $\mu_{i_{0}+1}(a_{1})\cap\mu_{i_{0}+1}(a_{2})\neq\emptyset$, at least
one of the four terms of the above union is not empty. But since
$\mu_{i_{0}}(a_{1})\cap\mu_{i_{0}}(a_{2})=\emptyset$, only the last three
cases are investigated below.

$(i)$ If $\mu_{i_{0}}(a_{1})\cap M(a_{2})\neq\emptyset$, $M(a_{2})$ contains
$x_{2}$ such that $\mu_{i_{0}}(a_{1})\cap\mu_{i_{0}}(x_{2})\neq\emptyset$.
Thus, there exists $X_{2}\to A$ is in ${\cal FD}$ such that
$X_{2}=sch(x_{2})$, $\mu_{i_{0}}(a_{1})\cap\mu_{i_{0}}(x_{2})\neq\emptyset$
and $\mu_{i_{0}}(a_{2})\cap\mu_{i_{0}}(x_{2})\neq\emptyset$. Since both
$a_{1}$ and $a_{2}$ are in $dom(A)$, we have
$\mu_{i_{0}+1}(x_{2})\subseteq\mu_{i_{0}+1}(a_{1})$ and
$\mu_{i_{0}+1}(x_{2})\subseteq\mu_{i_{0}+1}(a_{2})$. Thus
$\mu^{*}(x_{2})\subseteq\mu^{*}(a_{1})\cap\mu^{*}(a_{2})$.

$(ii)$ If $\mu_{i_{0}}(a_{2})\cap M(a_{1})\neq\emptyset$, it can be shown in a
similar way that there exist $X_{1}\to A$ is in ${\cal FD}$ and $x_{1}$ over
$X_{1}$ such that $\mu^{*}(x_{1})\subseteq\mu^{*}(a_{1})\cap\mu^{*}(a_{2})$.
The proof is omitted.

$(iii)$ If $M(a_{1})\cap M(a_{2})\neq\emptyset$, for $j=1,2$, $M(a_{j})$
contains $x_{j}$ such that
$\mu_{i_{0}}(x_{1})\cap\mu_{i_{0}}(x_{2})\neq\emptyset$. Thus, for $j=1,2$,
there exist $X_{j}\to A$ in ${\cal FD}$ such that $X_{j}=sch(x_{j})$,
$\mu_{i_{0}}(x_{j})\cap\mu_{i_{0}}(a_{j})\neq\emptyset$ and
$\mu_{i_{0}}(x_{1})\cap\mu_{i_{0}}(x_{2})\neq\emptyset$. Hence,
$\mu_{i_{0}+1}(x_{j})\subseteq\mu_{i_{0}+1}(a_{j})$, for $j=1,2$ and
$\mu_{i_{0}+1}(x_{1})\cap\mu_{i_{0}+1}(x_{2})\neq\emptyset$. It follows that,
when computing $\mu_{i_{0}+2}$, we obtain the additional inclusions
$\mu_{i_{0}+2}(x_{1})\subseteq\mu_{i_{0}+2}(a_{2})$ and
$\mu_{i_{0}+2}(x_{2})\subseteq\mu_{i_{0}+2}(a_{1})$, which implies that for
$j=1,2$, $\mu^{*}(x_{j})\subseteq\mu^{*}(a_{1})\cap\mu^{*}(a_{2})$ holds. This
part of the proof is thus complete.

$(2)$ Regarding the second item in the second part of the lemma, assume first
that $\Delta\vdash(\alpha\sqcap\beta)$. Since $\mu^{*}\models\Delta$, we
obviously have that $\mu^{*}(\alpha)\cap\mu^{*}(\beta)\neq\emptyset$.

Conversely, assuming that $\mu^{*}(\alpha)\cap\mu^{*}(\beta)\neq\emptyset$, we
show that $\Delta\vdash(\alpha\sqcap\beta)$, that is, for every $\mu$ such
that $\mu\models\Delta$, $\mu(\alpha)\cap\mu(\beta)\neq\emptyset$. The proof
is by induction on the steps of the construction of $\mu^{*}$, assuming
$\alpha$ in $dom(A)$ and $\beta$ in $dom(B)$.
$\bullet$ The result holds for $i=0$. Indeed, if
$\mu_{0}(\alpha)\cap\mu_{0}(\beta)\neq\emptyset$ then there exists $u$ in $D$
such that $\alpha\sqsubseteq u$ and $\beta\sqsubseteq u$. Hence for every
$\mu$ such that $\mu\models\Delta$, we have $\mu(u)\neq\emptyset$ and
$\mu(u)\subseteq\mu(\alpha)\cap\mu(\beta)$, implying that
$\mu(\alpha)\cap\mu(\beta)\neq\emptyset$ holds.
$\bullet$ For $i_{0}>0$, assuming that $\mu_{i_{0}}$ satisfies that for all
$\zeta$ and $\eta$ such that
$\mu_{i_{0}}(\zeta)\cap\mu_{i_{0}}(\eta)\neq\emptyset$, we have
$\mu(\zeta)\cap\mu(\eta)\neq\emptyset$ for every $\mu$ such that
$\mu\models\Delta$, we show that the result holds for $\mu_{i_{0}+1}$.

Indeed, let $i_{0}$ such that
$\mu_{i_{0}}(\alpha)\cap\mu_{i_{0}}(\beta)=\emptyset$ and
$\mu_{i_{0}+1}(\alpha)\cap\mu_{i_{0}+1}(\beta)\neq\emptyset$. By definition of
the sequence $(\mu_{i})_{i\geq 0}$, and as in $(1)$ just above,
$\mu_{i_{0}+1}(\alpha)=\mu_{i_{0}}(\alpha)\cup M(\alpha)$ where $M(\alpha)$ is
the union of all $\mu_{i_{0}}(x)$ such that $X\to A$ is in ${\cal FD}$,
$\mu_{i_{0}}(x)\cap\mu_{i_{0}}(\alpha)\neq\emptyset$ and
$\mu_{i_{0}}(x)\not\subseteq\mu_{i_{0}}(\alpha)$. Similarly,
$\mu_{i_{0}+1}(\beta)=\mu_{i_{0}}(\beta)\cup M(\beta)$ where $M(\beta)$ is the
union of all $\mu_{i_{0}}(y)$ such that $Y\to B$ is in ${\cal FD}$,
$\mu_{i_{0}}(y)\cap\mu_{i_{0}}(\beta)\neq\emptyset$ and
$\mu_{i_{0}}(y)\not\subseteq\mu_{i_{0}}(\beta)$. Thus:

$\mu_{i_{0}+1}(\alpha)\cap\mu_{i_{0}+1}(\beta)$ | $=(\mu_{i_{0}}(\alpha)\cup M(\alpha))\cap(\mu_{i_{0}}(\beta)\cup M(\beta))$
---|---
| $=(\mu_{i_{0}}(\alpha)\cap\mu_{i_{0}}(\beta))\cup(\mu_{i_{0}}(\alpha)\cap
M(\beta))~{}\cup~{}\qquad$
| $(M(\alpha)\cap\mu_{i_{0}}(\beta))\cup(M(\alpha)\cap M(\beta))$

Since $\mu_{i_{0}+1}(\alpha)\cap\mu_{i_{0}+1}(\beta)\neq\emptyset$, at least
one of the four terms of the above union is non empty. But since
$\mu_{i_{0}}(\alpha)\cap\mu_{i_{0}}(\beta)=\emptyset$, only the last three
cases are investigated below.

$(i)$ If $\mu_{i_{0}}(\alpha)\cap M(\beta)\neq\emptyset$, there exist $Y\to B$
in ${\cal FD}$ and $y$ over $Y$ such that
$\mu_{i_{0}}(\alpha)\cap\mu_{i_{0}}(y)\neq\emptyset$ and
$\mu_{i_{0}}(\beta)\cap\mu_{i_{0}}(y)\neq\emptyset$. By our induction
hypothesis, for every $\mu$ such that $\mu\models\Delta$, we have
$\mu(\alpha)\cap\mu(y)\neq\emptyset$ and $\mu(y)\subseteq\mu(\beta)$, which
implies that $\mu(\alpha)\cap\mu(\beta)\neq\emptyset$.

$(ii)$ If $\mu_{i_{0}}(\beta)\cap M(\alpha)\neq\emptyset$, the case is similar
to $(i)$ above. The proof is omitted.

$(iii)$ If $M(\alpha)\cap M(\beta)\neq\emptyset$, there exist $X\to A$ and
$Y\to B$ in ${\cal FD}$, $x$ over $X$ and $y$ over $Y$, such that
$\mu_{i_{0}}(x)\cap\mu_{i_{0}}(y)\neq\emptyset$,
$\mu_{i_{0}}(\alpha)\cap\mu_{i_{0}}(x)\neq\emptyset$ and
$\mu_{i_{0}}(\beta)\cap\mu_{i_{0}}(y)\neq\emptyset$. By our induction
hypothesis, for every $\mu$ such that $\mu\models\Delta$, we have
$\mu(x)\cap\mu(y)\neq\emptyset$, $\mu(x)\subseteq\mu(\alpha)$ and
$\mu(y)\subseteq\mu(\beta)$. Hence, $\mu(\alpha)\cap\mu(\beta)\neq\emptyset$
also holds in this case, and the proof is complete. $\Box$

##  Appendix B Proof of Lemma 2

Lemma 2. Let $\Delta=(D,{\cal FD})$ and $t$ a tuple. Then Algorithm 1 computes
correctly the closure $t^{+}$ of $t$.

###### Proof

In this proof, we denote by $cl(t)$ the output of Algorithm 1, and we show
that $cl(t)=t^{+}$, that is that $cl(t)\subseteq t^{+}$ and $t^{+}\subseteq
cl(t)$ both hold. Before proceeding to these proofs, we draw attention on that
for every ${\cal T}$-mapping $\mu$ such that $\mu(t)\neq\emptyset$,
$\mu\models\Delta$ if and only if $\mu\models\Delta_{t}$, where $\Delta_{t}$
is defined by the statement line 1 in Algorithm 1. Indeed:
$\bullet$ If $\mu\models\Delta_{t}$ then for every $q\in D_{t}$
$\mu(q)\neq\emptyset$ and $\mu\models{\cal FD}$. Since $D\subset D_{t}$,
$\mu(q)\neq\emptyset$ for every $q\in D$, implying that $\mu\models\Delta$
holds.
$\bullet$ Conversely, if $\mu\models\Delta$ then as $\mu(t)$ is supposed to be
nonempty, $\mu(q)\neq\emptyset$ for every $q$ in $D_{t}$. Since
$\mu\models{\cal FD}$ holds, $\mu\models\Delta_{t}$ also holds.

To first prove that $cl(t)\subseteq t^{+}$, we consider a ${\cal T}$-mapping
$\mu$ such that $\mu\models\Delta$, and we prove that $\mu(t)\subseteq\mu(a)$
for every $a$ in $cl(t)$. We first observe that if $\mu(t)=\emptyset$ then
$\mu(t)\subseteq\mu(\alpha)$ holds for every constant $\alpha$. Therefore,
$\mu(t)\subseteq\mu(a)$ holds.

Now, if $\mu(t)\neq\emptyset$ then $\mu\models\Delta_{t}$, as shown above. The
proof that $\mu(t)\subseteq\mu(a)$ is done by induction on the steps of the
execution of Algorithm 1. Denoting by $cl^{0}$, $cl^{1}$, $\ldots$ the
sequence of the assignments of $cl(t)$ during execution, the following holds
for every $a$ in $cl(t)$.
$\bullet$ If $a$ is in $cl^{0}$ as computed on line 2, $a$ occurs in $t$. It
is thus clear that $\mu(t)\subseteq\mu(a)$.
$\bullet$ We now assume that, for $j\geq 0$, every $\alpha$ in $cl^{j}$ is
such that $\mu(t)\subseteq\mu(\alpha)$ and we show that this holds for $a$ in
$cl^{j+1}$ but not in $cl^{j}$. In this case, according to the condition in
line 5 of Algorithm 1, there exist $X\to A$ in ${\cal FD}$ and $x$ over $X$
such that $\Delta_{t}\vdash xa$ and for every $b$ in $x$, $b\in cl^{j}$. Thus
$\mu(x)\cap\mu(a)\neq\emptyset$ (because $\mu\models\Delta_{t}$) and
$\mu(t)\subseteq\mu(b)$ for every $b$ in $x$ (by our induction hypothesis,
because $b$ is in $cl^{j}$). Hence $\mu(t)\subseteq\mu(x)$ and
$\mu(x)\subseteq\mu(a)$ hold, thus implying that $\mu(t)\subseteq\mu(a)$.

As a consequence, we have shown that for every $\mu$ such that
$\mu\models\Delta$, for every $a$ in $cl(t)$, $\mu(t)\subseteq\mu(a)$.
Therefore, by Definition 3, $cl(t)\subseteq t^{+}$ holds.

Conversely, $t^{+}\subseteq cl(t)$ is shown by contraposition: assuming that
$a\not\in cl(t)$, we prove that $a\not\in t^{+}$. To this end, we exhibit a
${\cal T}$-mapping $\mu_{t}$ such that $\mu_{t}\models\Delta$ and
$\mu_{t}(t)\not\subseteq\mu_{t}(a)$.

We denote by $\mu_{t}^{*}$ the ${\cal T}$-mapping built up as $\mu^{*}$, but
starting from $\Delta_{t}$ as defined line 1 in Algorithm 1. Thus,
$\mu_{t}^{*}\models\Delta_{t}$, and since $\mu^{*}_{t}(t)\neq\emptyset$, it
has been seen above that $\mu^{*}_{t}\models\Delta$.

Thus, if $\mu^{*}_{t}(t)\not\subseteq\mu^{*}_{t}(a)$ then $\mu_{t}^{*}$ is the
${\cal T}$-mapping we are looking for, and thus, we set $\mu_{t}=\mu^{*}_{t}$.
Assuming that $\mu^{*}(t)\subseteq\mu^{*}(a)$, let $k$ be an integer not in
$\mu^{*}_{t}(\alpha)$ for any $\alpha$ occurring in $\Delta_{t}$, and let
$\mu_{t}$ be the ${\cal T}$-mapping defined for every constant $\alpha$ by:
$-$ $\mu_{t}(\alpha)=\mu^{*}_{t}(\alpha)\cup\\{k\\}$, if $\alpha\in cl(t)$
$-$ $\mu_{t}(\alpha)=\mu^{*}_{t}(\alpha)$, otherwise.
We show that $\mu_{t}$ satisfies that: $(1)$
$\mu_{t}(t)\not\subseteq\mu_{t}(a)$ and $(2)$ $\mu_{t}\models\Delta$.

$(1)$ Since every $\alpha$ in $t$ is in $cl(t)$, $k$ is in $\mu_{t}(t)$ and
since $a$ is not in $cl(t)$, $k$ is not in $cl(a)$. It thus follows that
$\mu_{t}(t)\not\subseteq\mu_{t}(a)$.

$(2)$ Since for every constant $\alpha$,
$\mu^{*}_{t}(\alpha)\subseteq\mu_{t}(\alpha)$ holds, for every $q$ in $D$, it
holds that $\mu^{*}_{t}(q)\subseteq\mu_{t}(q)$, which implies
$\mu_{t}(q)\neq\emptyset$, because $\mu^{*}_{t}(q)\neq\emptyset$ holds as a
consequence of $\mu^{*}_{t}\models\Delta$.

To prove that $\mu_{t}\models Y\to B$ for every $Y\to B$ in ${\cal FD}$, let
$y$ over $Y$ and $b$ in $dom(B)$ such $\mu_{t}(y)\cap\mu_{t}(b)\neq\emptyset$.
To show that $\mu_{t}(y)\subseteq\mu_{t}(b)$, we consider the two cases
according to which $\mu^{*}_{t}(y)\cap\mu^{*}_{t}(b)$ is or not empty.
$\bullet$ If $\mu^{*}_{t}(y)\cap\mu^{*}_{t}(b)=\emptyset$, then by definition