# Consistent data fusion with Parker

Antoon Bronselaer<EMAIL_ADDRESS>DDCM Lab, Department of
Telecommunication and Information Science, Ghent University, Sint-
Pietersnieuwstraat 41, B-9000 Ghent, Belgium  Maribel Acosta
<EMAIL_ADDRESS>Faculty of Computer Science, Ruhr University Bochum,
Universitätsstraße 150, D-44801 Bochum, Germany

###### Abstract

When combining data from multiple sources, inconsistent data complicates the
production of a coherent result. In this paper, we introduce a new type of
constraints called edit rules under a partial key (EPKs). These constraints
can model inconsistencies both within and between sources, but in a loosely-
coupled matter. We show that we can adapt the well-known set cover methodology
to the setting of EPKs and this yields an efficient algorithm to find minimal
cost repairs of sources. This algorithm is implemented in a repair engine
called Parker. Empirical results show that Parker is several orders of
magnitude faster than state-of-the-art repair tools. At the same time, the
quality of the repairs in terms of $F_{1}$-score ranges from comparable to
better compared to these tools.

###### keywords:

Data Fusion , Data Quality , Edit rules , Key constraints , Functional
Dependencies

††journal: Information Fusion

##  1 Introduction

We study the data fusion problem where data from different sources must be
under certain consistency constraints. This problem is modelled by assuming
that each data source has the same schema and provides information on some
entity in terms of single tuples. Consistency is validated by means of two
types of integrity constraints. On one hand, tuples are subject to tuple-level
constraints that are expressed as _edit rules_. These edit rules model the
internal consistency for each individual source. On the other hand, tuples
coming from different sources must agree on certain attributes and this is
modelled as a (partial) key constraint. This partial key constraint models the
level agreement that sources must reach in order to be mutual consistent.

#### Running example

Figure 1 shows data taken from the European Clinical Trials Register (EudraCT)
database. In Figure 1 (a), the design parameters of a single clinical trial
are shown for different sites in the European Union where this trial was
executed. Figure 1 (b) shows six simple edit rules (ERs) to which the design
parameters of a study must adhere. The first four rules together enforce that
a study has exactly one masking strategy. The last two rules enforce that if a
trial uses a placebo or an active comparator, then that trial is controlled.
Violations of these rules are shown in bold red font in panel (a).

Figure 1: Data on the design parameters of a clinical trial executed in
different sites (a). Edit rules that need to hold are shown in (b) and
violations are marked in bold red font. Required agreement between sites is
modelled by a partial key (c), with violations marked in grey. A minimal
repair is shown in (d), with changes marked in bold green font.

Figure 1 (c) shows a set of functional dependencies (FDs) that indicate
‘#study’ is a partial key as ‘#study’ and ‘country code’ are a candidate key.
The partial key implies that four design parameters need to be the same for
the same study, regardless of the site where it was executed. Violations of
this partial key constraints are marked as grey shaded columns in Figure 1
(a). Finally, Figure 1 (d) shows a _repair_ of the data from Figure 1 (a) that
violates no ERs and no FDs. This repair is _minimal_ in the sense that there
is no relation with the same attributes that (i) satisfies all constraints and
(ii) differs from Figure 1 in less attribute values.

#### Motivation

An immediate question might be why constraints are modelled as a mixture of
FDs and ERs. All constraints in Figure 1 can be represented in the 9 framework
of conditional functional dependencies (CFDs) [1, 2] or denial constraints
(DCs) [3], so why not use them? The main problem with these formalisms, is
that finding (minimal) repairs is a computationally intensive task [4, 5, 6,
7]. When using edit rules, however, the problem of finding (minimal) repairs
boils down to finding (minimal) set covers of failing rules if the given rules
satisfy a closure property [8, 9, 10]. In a similar manner, finding (minimal)
repairs for violations of a partial key constraint is easy if no backward
repairing (i.e., modification of the key values) is allowed. The main argument
of this paper is that when combining both partial key constraints and edit
rules, we can exploit the properties of both constraint types to efficiently
prune the search space and still ensure minimal repairs. Moreover, the
combination of partial keys and edit rules alleviates the expressiveness of
edit rules in such a way we can cover many constraints we observe in real life
scenarios. As such, an appealing balance between computational efficiency and
expressiveness is obtained.

#### Contributions

We propose an efficient algorithm to find all minimal repairs when constraints
are a mixture of a partial key and a set of edit rules. The algorithm is
implemented as the Parker (Partial Key and Edit Rule) repair engine and is
available as a part of an open source
framework111https://gitlab.com/ledc/ledc-sigma. Empirical results show that
Parker is superior on all tested datasets in terms of performance when
compared to two state-of-the-art cleaning tools (HoloClean and Raha-Baran). In
terms of precision and recall, Parker is competitive with these tools and in
some cases better.

The remainder of the paper is structured as follows. Section 2 explains
preliminary concepts. Section 3 introduces the foundations of edit rules under
partial key constraints (EPKs). Section 4 describes our approach to compute
minimal repairs for EPKs based on the cost models presented in Section 5.
Related Work is discussed in Section 6, while Section 7 presents an
experimental study against the state of the art. Lastly, Section 8 presents
the conclusion and an outlook to future work.

##  2 Preliminaries

###  2.1 The relational model

We consider $\mathcal{A}$ to be a countable set of attributes where for each
$a\in\mathcal{A}$, $A$ denotes the _domain_ of $a$ and is assumed to be
countable. A _schema_ $\mathcal{R}=\\{a_{1},\ldots,a_{k}\\}$ is a non-empty
and finite subset of $\mathcal{A}$. A _relation_ $R$ with schema $\mathcal{R}$
is defined by a finite set $R\subseteq A_{1}\times\ldots\times A_{k}$.
Elements of $R$ with schema $\mathcal{R}$ are called _tuples_ with schema
$\mathcal{R}$. For a relation $R$ with schema $\mathcal{R}$, a set of
attributes $X\subseteq\mathcal{R}$ and a predicate $P$, we denote the
_projection_ of $R$ over $X$ by $R[X]$ and _selection_ over $P$ by $R_{P}$.
For two relations $R^{\prime}$ and $R^{\prime\prime}$ with respective schemas
$\mathcal{R}^{\prime}$ and $\mathcal{R}^{\prime\prime}$, $R^{\prime}\bowtie
R^{\prime\prime}$ denotes the _natural join_ of $R^{\prime}$ and
$R^{\prime\prime}$.

###  2.2 Functional dependencies and partial keys

A _functional dependency_ (FD) [11] $\phi$ defined over a schema $\mathcal{R}$
is an expression of the form $X\rightarrow Y$ such that
$X\subseteq\mathcal{R}$ and $Y\subseteq\mathcal{R}$. A relation $R$ with
schema $\mathcal{R}$ _satisfies_ $\phi$ (denoted by $R\models\phi$) if
$\forall r_{1},r_{2}\in R:r_{1}[X]=r_{2}[X]\Rightarrow r_{1}[Y]=r_{2}[Y]$. An
FD $X\rightarrow Y$ is _minimal_ is there is no $X^{\prime}\subset X$ such
that $X^{\prime}\rightarrow Y$ holds. A set of attributes
$\mathcal{K}\subseteq\mathcal{R}$ is called a _candidate key_ if the FD
$\mathcal{K}\rightarrow\mathcal{R}$ holds and is minimal. For a candidate key
$\mathcal{K}$, a partial key is a subset of that candidate key that determines
at least one attribute other than the key.

###  2.3 Edit rules

An _edit rule_ [8] is a tuple-level constraint that specifies which
combinations of attribute values are not permitted to occur together. There
are different types of edit rules such as _linear_ edit rules [8, 10], _ratio_
edits [10] and _constant_ edits [9]. For simplicity, we will restrict
ourselves to constant edit rules, even though the methodology is applicable to
a broader category of constraints222The implementation in ledc-sigma allows
rules equivalent to relational selection $\sigma$ with variables..

A (constant) _edit rule_ (ER) $E$ on $\mathcal{R}=\\{a_{1},...,a_{k}\\}$ is an
expression of the form $E_{1}\times...\times E_{k}$ where $E_{i}\subseteq
A_{i}$. A tuple $r$ _satisfies_ $E$ (denoted by $r\models E$) if $r\notin E$.
If some $E_{i}$ is empty for $E$, then $E$ never fails and we call such rules
_tautologies_. Conversely, if all $E_{i}$ equal $A_{i}$ for rule $E$, then $E$
is never satisfied and we call such rules _contradictions_. In what follows,
we assume that rules are neither a tautology nor a contradiction. An attribute
$a_{i}\in\mathcal{R}$ is said to _enter_ an edit rule $E$ if and only if
$E_{i}\subset A_{i}$. Alternatively, we say that $E$ _involves_ $a_{i}$. The
set of attributes involved in $E$ is denoted by $\mathcal{I}\left(E\right)$.

##  3 Edit Rules under Partial Key Constraints

###  3.1 Basic definition and problem statement

Suppose we have a set of data sources that all provide information on some
entity. They do so by each emitting one tuple that obeys a common schema
$\mathcal{R}$. This means that we can model the whole of these different
sources as a single relation $R$ with schema $\mathcal{R}$. In our earlier
example (Figure 1, (a)), the sources correspond to member states of the EU and
they each present information about one clinical trial identified by its study
number. Suppose now we want to fuse information coming from these sources in a
consistent manner by enforcing two requirements.

  1. 1.

Each source is internally consistent according to a set of tuple-level
constraints (Figure 1, (b)).

  2. 2.

Sources agree on certain parts of the data and we formalize this by stating
that some identifier of the entity we are describing, functionally determines
some (not necessarily all) attributes (Figure 1, (c)).

The combination of these two requirements can be formalized via the notion of
an edit rule under a partial key (EPK) constraint and is defined as follows.

###### Definition 1

Let $\mathcal{R}$ be a schema that can be partitioned into $\mathcal{K}$,
$\mathcal{R}_{1}$ and $\mathcal{R}_{2}$. An edit rule under a partial key
constraint (EPK constraint) is an edit rule $E$ on
$\mathcal{R}_{1}\cup\mathcal{R}_{2}$ such that the FD
$\phi:\mathcal{K}\rightarrow\mathcal{R}_{1}$ needs to hold.

Definition 1 implies that any EPK is determined by a pair $(\phi,E)$. It thus
follows naturally that a relation $R$ fails an EPK whenever either
$R\not\models\phi$ or there is some $r\in R$ for which $r\not\models E$. For a
single schema $\mathcal{R}$, multiple edit rules can be defined, but we
restrict ourselves to a single partial key. A set of EPKs can then always be
denoted by a couple $\left(\phi,\mathcal{E}\right)$, where $\phi$ provides the
partial key constraint and $\mathcal{E}$ is a set of edit rules.

The fusion model we introduced above can now be represented by a set of EPKs
where consolidation is done by repairing inconsistencies in an optimal way. In
more formal terms, if $R$ fails some EPK, then we want to _modify_ $R$ into a
new relation $R^{*}$ such that (i) $R^{*}$ fails no EPKs and (ii) the
differences between $R$ and $R^{*}$ are minimized. A relation $R^{*}$ is
called a _repair_ if is satisfies (i) and is called a _minimal repair_ if it
satisfies (i) and (ii).

In the scope of this paper, we focus on repairs achieved by updates only.
Moreover, we make the explicit assumption that $\mathcal{K}$ does not contain
errors, modelling the fact that sources make judgements on the right entities.
The minimization criterion of repairs is defined here in terms of a _cost
function_ for attribute changes.

###### Definition 2

A _cost function_ for $a\in\mathcal{R}$ is a positive-definite function
$\Delta_{a}:A^{2}\rightarrow\mathbb{N}$.

If $\mathcal{R}$ is entirely equipped with cost functions, then the cost for
modifying some tuple $r$ into a tuple $r^{*}$ is simple computed by the sum of
costs:

$\Delta(r,r^{*})=\sum_{a\in\mathcal{R}}\Delta_{a}\left(r[a],r^{*}[a]\right).$
(1)

A repair $R^{*}$ is now called $\Delta$-minimal if rows $r\in R$ are modified
into rows $r^{*}$ such that the sum of all $\Delta\left(r,r^{*}\right)$ is
minimal. One obvious cost function is the one that simply verifies whether
$r[a]=r^{*}[a]$ (cost $0$), or not (cost $1$). Using this cost function,
$\Delta(r,r^{*})$ equals the number of attributes that were modified. Figure 1
(d) shows a repair of Figure 1 (a) that is $\Delta$-minimal under this
counting function.

In general, cost functions need not to be symmetric and we can assign a
different cost function to each individual tuple. It is usually a desirable
feature that cost functions are at least constant with respect to changing a
null value, meaning that $\Delta_{a}(\bot,v)$ is independent of $v$. We now
formulate the main problem studied in this paper as follows.

Figure 2: High-level architecture of the Parker repair engine.

#### Problem statement

Given a relation $R$ with schema $\mathcal{R}$ and a set of EPKs, find all
$\Delta$-minimal repairs $R^{*}$ for some predefined cost function $\Delta$.
Solving this problem in a naive way, requires testing all possible repairs,
which has a time complexity of
$\mathcal{O}\left(|R|\cdot\prod_{a_{i}\in\mathcal{R}}\left|A_{i}\right|\right)$.
By exploiting the properties of EPKs, we are able to construct a repair engine
(Parker) that explores the search space in a very efficient manner. The main
architecture of Parker is shown in Figure 2. Besides the constraints, Parker
is equipped with a cost model $\Delta$ and a selection strategy to choose,
from all $\Delta$-minimal repairs, a single repair. We provide more details on
both cost models and selection strategies in Section 5.

###  3.2 Properties of EPKs

For constant ERs, an efficient method exists to find minimal repairs [8]. If
some tuple $r\in R$ fails some $E\in\mathcal{E}$, a _solution_ is a set of
attributes $\mathcal{S}\subseteq\mathcal{R}$ such that there exists a valid
tuple $r^{*}$ that _only_ differs from $r$ in $\mathcal{S}$. In other words, a
solution $\mathcal{S}$ must satisfy:

$\exists r^{*}:r^{*}\models\mathcal{E}\wedge
r\left[\overline{\mathcal{S}}\right]=r^{*}\left[\overline{\mathcal{S}}\right].$
(2)

We say that a repair $r^{*}$ for $r$ has solution $\mathcal{S}$ if this above
condition is satisfied. For constant edit rules, solutions satisfy a
particular property in the sense that constant edit rules are _interaction-
free_ in the sense that if we consider a single constant rule $E$ and $r$ is
changed in two different attributes $a_{1}$ and $a_{2}$ to satisfy $E$, then
one of both changes can be undone and $E$ is still satisfied.

To find solutions efficiently, $\mathcal{E}$ can be transformed into a
_sufficient set_ , denoted by $\underline{\Omega}\left(\mathcal{E}\right)$.
This sufficient set has the property that any solution $\mathcal{S}$ for a
tuple $r$ is always a set-cover of the _failing_ rules from
$\underline{\Omega}\left(\mathcal{E}\right)$. Set covers are hereby defined as
follows:

###### Definition 3

A set cover for edit rules $\mathcal{E}$ on $\mathcal{R}$ is a set of
attributes $\mathcal{C}\subseteq\mathcal{R}$ such that $\forall
E\in\mathcal{E}:\mathcal{I}\left(E\right)\cap\mathcal{C}\neq\emptyset$.

In Figure 1 (c), the set of rules is sufficient, meaning that solutions to
errors can be found by composing set covers to failing rules. For example, the
second tuple in Figure 1 (a) fails two rules and as the attribute ‘control’
covers both of these rules, we are certain there exists repair for the second
tuple where we only change attribute ‘control’.

The construction of $\underline{\Omega}\left(\mathcal{E}\right)$ is key in our
approach for several reasons. First,
$\underline{\Omega}\left(\mathcal{E}\right)$ can be constructed efficiently
for small to medium-sized $\mathcal{E}$ by using the FCF algorithm [9].
Moreover, continuous research is devoted to making this construction step more
efficient. Second, construction of
$\underline{\Omega}\left(\mathcal{E}\right)$ allows to check if there a priori
_exists_ a tuple that satisfies $\mathcal{E}$ or not. If there exists one,
$\mathcal{E}$ is called _satisfiable_ and it can be shown that $\mathcal{E}$
is _satisfiable_ if and only if $\underline{\Omega}\left(\mathcal{E}\right)$
does not contain a contradiction. This translates immediately to EPKs.

###### Proposition 1

A set of EPKs $\left(\phi,\mathcal{E}\right)$ is _satisfiable_ if
$\mathcal{E}$ is satisfiable.

Third, $\underline{\Omega}\left(\mathcal{E}\right)$ allows to find minimal
repairs for EPKs, although not in a straightforward manner. The main problem
is that solutions and set covers of failing rules deal with _sets of
attributes_. However, the cost functions $\Delta_{a}$ we use here, calculate
cost in terms of _values_ that attributes take. We will show later that in the
setting of EPKs, we _must_ use such cost functions. The consequence is that we
can not simply look for minimal solutions in terms of attributes anymore,
because the cost repairing those attributes depends on the values that these
attributes take. We therefore need to rely on a weaker connection between
repairs and covers in terms of $\subset$-minimal covers.

###### Definition 4

For edit rules $\mathcal{E}$ on $\mathcal{R}$, a set-cover
$\mathcal{C}\subseteq\mathcal{R}$ is $\subset$-minimal if no real subset of
$\mathcal{C}$ is a set-cover of $\mathcal{E}$.

Intuitively, $\subset$-minimal covers inform us about the different ways in
how we can change tuples to satisfy failing rules. In the example on Figure 1
(a), the second tuple fails two rules and we can either solve this by changing
‘control’ or by changing ‘placebo’ and ‘active compare’. This intuition leads
to the following proposition.

###### Proposition 2

Let $\mathcal{E}$ be a set of edit rules on $\mathcal{R}$. If $r^{*}$ is a
repair for $r$ with solution $\mathcal{S}$ then $\mathcal{S}$ contains at
least one $\subset$-minimal cover of the rules failed by $r$.

The main question is now whether or not a $\Delta$-minimal repair always has a
solution $\mathcal{S}$ that is _equal_ to a $\subset$-minimal cover of failing
rules of $\underline{\Omega}\left(\mathcal{E}\right)$. Unfortunately, the
answer to this question is negative because, in general, changing more
attributes can lead to a lower overall cost. This means we can not restrict
ourselves to $\subset$-minimal covers when searching for $\Delta$-minimal
repairs. Fortunately, some properties exist to keep searching efficiently. For
a tuple $r$, a repair $r^{*}$ is said to be _$\mathcal{S}$ -minimal_ if it has
changes only in $\mathcal{S}$ and does so in a cost-minimal way. This latter
means there is no repair $r^{\prime}$ with solution $\mathcal{S}$ such that
$\Delta(r,r^{\prime})<\Delta(r,r^{*})$. Two important properties now relate
such $\mathcal{S}$-minimal repairs to $\Delta$-minimal repairs and help in
finding the latter efficiently.

###### Theorem 1

If $r^{*}$ is a $\Delta$-minimal repair for $r$ with solution $\mathcal{S}$
and there exists a $\subset$-minimal cover $\mathcal{C}$ such that
$\mathcal{C}\subset\mathcal{S}$ then for the tuple $r^{\prime}$ satisfying
$r^{\prime}[\mathcal{C}]=r^{*}[\mathcal{C}]\wedge
r^{\prime}[\overline{\mathcal{C}}]=r[\overline{\mathcal{C}}]$ we have that (1)
$r^{\prime}$ is not a repair for $r$ and (2) $\Delta\left(r,r^{\prime}\right)$
is strictly smaller than the cost for any $\mathcal{C}$-minimal repair for
$r$.

The crux of Theorem 1 is that it gives us a strategy for finding
$\Delta$-minimal repairs. More precisely, we can use all $\subset$-minimal
cover of failing rules as a starting point. For any such $\mathcal{C}$, we can
iterate over possible values in order of _lowest cost first_. We continue this
iteration until we find a repair and due to the nature of iteration, this
repair is then $\mathcal{C}$-minimal. Theorem 1 now says that any potential
$\Delta$-minimal repair $r^{*}$ that changes _more_ attributes than
$\mathcal{C}$, _must_ take values for $\mathcal{C}$ that have lower cost than
the repair we just found. As such, if we find repairs that are
$\mathcal{C}$-minimal, we only need to inspect those values for $\mathcal{C}$
that have a strictly lower cost than the $\mathcal{C}$-minimal solutions and
those are values we already iterated over. A stronger result is that not each
combination of values for $\mathcal{C}$ with cost strictly lower than the
$\mathcal{C}$-minimal solutions needs to be inspected.

###### Proposition 3

If $r$ is a tuple that has a $\Delta$-minimal repair $r^{*}$ using solution
$\mathcal{S}$ then we must have:

$\forall a_{i}\in\mathcal{S}:r[a_{i}]\neq r^{*}[a_{i}]\wedge\exists
E\in\underline{\Omega}\left(\mathcal{E}\right):r^{*}[a_{i}]\notin E_{i}$

Proposition 3 basically states we should only make changes to $r$ that are
necessary to satisfy some rule. Because constant edit rules are interaction-
free, Proposition 3 can be verified by observing _only_ the values for
$\mathcal{C}$. This is particularly useful because Theorem 1 tells us that if
some solution $\mathcal{S}$ strictly contains a $\subset$-minimal cover
$\mathcal{C}$, then the values taken for $\mathcal{C}$ by some
$\Delta$-minimal repair will themselves not resolve all failing rules. For
constant edit rules, we can now also verify whether the values for
$\mathcal{C}$ satisfy Proposition 3. We emphasize here that this latter
observation holds _only_ for constant edit rules. It one wishes to use edit
rules involving variables (e.g. a rule of the type $a_{1}\leq a_{2}$), then
because such rules are not interaction-free, we can not apply this property if
we want to find $\Delta$-minimal repairs.

##  4 Finding Minimal Repairs for EPKs

In this section, we exploit the properties of edit rules and EPKs introduced
in the previous to compose an efficient algorithm for finding all
$\Delta$-minimal repairs for a relation $R$ constrained under a set of EPKs
$(\phi,\mathcal{E})$. To gradually introduce our approach, we will first study
the case where $\phi$ is a _full_ key constraint. In that scenario, we have
$\phi:\mathcal{K}\rightarrow\mathcal{R}_{1}\cup\mathcal{R}_{2}$ and
$\mathcal{E}$ contains edit rules defined over
$\mathcal{R}_{1}\cup\mathcal{R}_{2}$. We will introduce our algorithm in that
case step by step. Finally, we will generalize that algorithm to the case of
partial keys.

###  4.1 Finding $\equiv_{\mathcal{K}}$ tuples

To begin with, $\mathcal{K}$ imposes an equivalence relation
$\equiv_{\mathcal{K}}$ on $R$ where
$r\equiv_{\mathcal{K}}r^{\prime}\Leftrightarrow
r[\mathcal{K}]=r^{\prime}[\mathcal{K}]$. It is easy to see that (i) finding
$\Delta$-minimal repairs requires treating all equivalent tuples at the same
time and (ii) tuples that are not equivalent can be treated independently from
each other. For that reason, we focus here on the treatment of a single
equivalence class $R_{\mathcal{K}=\mathbf{k}}$ with $\mathbf{k}$ some key
value. Semantically speaking, each class forms a group of information about a
single entity provided by different sources.

###  4.2 Minimal cost iteration

If we have some class $R_{\mathcal{K}=\mathbf{k}}$ then our main interest lies
in the attributes $\mathcal{R}_{1}\cup\mathcal{R}_{2}$ which we can write as a
set $\\{a_{1},\ldots,a_{m}\\}$. Any $\Delta$-minimal repair must take values
for $\mathcal{R}_{1}\cup\mathcal{R}_{2}$ in the set $A_{1}\times\ldots\times
A_{m}$. Iterating over all these values this requires testing
$\prod_{i=1}^{m}|A_{i}|$ combinations which rapidly becomes intractable. To
make this more feasible, we can compose a ranking over the set
$A_{1}\times\ldots\times A_{m}$ such that lower ranked tuples imply a lower
cost when using them as a repair. In other words, this ranking allows us to
iterate over possible repairs in order of _lowest cost first_ (LCF).

In order to construct such an LCF ranking, we first consider weak orders
$\leq_{i}$ over the different attribute domains $A_{i}$. For each attribute
$a\in\mathcal{R}_{1}\cup\mathcal{R}_{2}$ and for any value $v\in A$, we can
see that if $r^{*}$ would be a repair for the class
$R_{\mathcal{K}=\mathbf{k}}$ with $r^{*}[a]=v$, then the cost contributed by
$a$ is equal to:

$c\left(v\right)=\sum_{r^{\prime}\in
R_{\mathcal{K}=\mathbf{k}}}\Delta_{a}(r^{\prime}[a],v)$ (3)

We hereby simply sum the costs required to change the value of $a$, for each
member of the class $R_{\mathcal{K}=\mathbf{k}}$ into $v$. The total cost for
repairing class $R_{\mathcal{K}=\mathbf{k}}$ with tuple $r^{*}$ is then equal
to the sum of all $c(r^{*}[a])$ over $\mathcal{R}_{1}\cup\mathcal{R}_{2}$. In
other words, we have that:

$\beta(\mathbf{k},r^{*})=\sum_{r\in
R_{\mathcal{K}=\mathbf{k}}}\Delta(r,r^{*})=\sum_{a\in\mathcal{R}_{1}\cup\mathcal{R}_{2}}c\left(r^{*}[a]\right)$
(4)

We use the notation $\beta\left(\mathbf{k},.\right)$ here to indicate the
local objective we want to minimize for each class
$R_{\mathcal{K}=\mathbf{k}}$. In the example of Figure 1 (a), suppose we
consider a constant cost model $\Delta_{a}$ for each attribute $a$ where
$\Delta_{a}(v,v^{\prime})$ is $0$ if $v=v^{\prime}$ and $1$ if $v\neq
v^{\prime}$. In that case, for attribute ‘open’ we find
$c(\text{`No'})=c(\text{`Yes'})=2$. Similarly, for attribute ‘control’, we
find $c(\text{`No'})=1$ and $c(\text{`Yes'})=3$. Note here that, although the
cost model $\Delta_{a}$ is constant for individual rows, the _induced_ cost
for changing some value for _an entire class_ , is not.

Consider now a weak order $\leq_{a}$ over $A$ such that $v\leq_{a}v^{\prime}$
if and only if $c\left(v\right)\leq c\left(v^{\prime}\right)$. Next, we choose
a _total_ order that is _consistent_ with $\leq_{a}$ by _indexing_ values from
$A$ in such a way that lower indices imply lower cost. In other words, we
consider an index scheme such that $\forall v_{(i)}\in A:\forall v_{(j)}\in
A:i\leq j\Leftrightarrow v_{(i)}\leq_{a}v_{(j)}$, where both $i$ and $j$ are
values in $\\{1,\ldots,|A|\\}$. With these notations at hand, Algorithm 1
provides an algorithm for LCF-iteration over values from
$A_{1}\times\ldots\times A_{m}$.

Algorithm 1 LCF-tuple iteration

1:$\left\\{(A_{1},\leq_{1}),\ldots(A_{m},\leq_{m})\right\\}$

2:$\mathbb{S}\leftarrow\emptyset$

3:push$\left(\mathbb{S},\left[v^{1}_{(1)},\ldots,v^{k}_{(1)}\right]\right)$

4:while $\mathbb{S}\neq\emptyset$ do

5: $r_{\text{pop}}\leftarrow$pop$\left(\mathbb{S}\right)$

6: for $i\in\\{1,\ldots,k\\}$ do

7: if $r_{\text{pop}}[a_{i}]\neq v^{i}_{(|A_{i}|)}$ then

8: push$\left(\mathbb{S},\textbf{next}\left(r_{\text{pop}},i\right)\right)$

9: end if

10: end for

11:end while

The algorithm takes a set of $m$ weakly-ordered sets $(A_{i},\leq_{i})$, for
which we can generate indexed values consistent with $\leq_{i}$. The main idea
of the iteration is to keep a _sorted set_ $\mathbb{S}$ that keeps tuples
$r^{\prime}$ sorted by their value $\beta(\mathbf{k},r^{\prime})$. Initially,
we push the value with indices one and we sequentially pop the first element
from $\mathbb{S}$. For each popped tuple $r_{\text{pop}}$ we check, for each
attribute $a_{i}$, if $r_{\text{pop}}$ currently has the last value according
to index scheme (line 7). If it does not, we push a copy of $r_{\text{pop}}$,
but increase the index of the value for $a_{i}$ with one step (line 8).

Algorithm 1 can be attributed the following properties. First, sorted sets
like $\mathbb{S}$ can be implemented with a Red-Black tree, meaning that
inserting new tuples $r^{\prime}$ is done in $\mathcal{O}(\log|\mathbb{S}|)$
time. Second, after each pop, $\mathbb{S}$ grows with _at most_ $m$ tuples,
where $m$ equals the amount of attributes. Third, each tuple we push to
$\mathbb{S}$ has a value for $\beta$ that is greater than or equal to the
value for $\beta$ of the tuple that was popped. Because we maintain order in
$\mathbb{S}$, it follows that we pop values from $\mathbb{S}$ in such a way
that $\beta$ is never decreasing. Lastly, by construction, each value from
$A_{1}\times\ldots\times A_{m}$ must be pushed once to $\mathbb{S}$, which
means the sequence of popped values is indeed an iteration over
$A_{1}\times\ldots\times A_{m}$. Note that it is possible that the same tuple
is popped multiple times from $\mathbb{S}$ but this can be solved by either
popping all tuples with an equal value for $\beta(.,.)$ in one go or by
keeping track of those tuples we already observed.

The properties we mentioned imply that finding minimal repairs of class
$R_{\mathcal{K}=\mathbf{k}}$ can be done by simply running Algorithm 1 and
check, for each popped $r^{\prime}$ whether $r^{\prime}\models\mathcal{E}$. If
so, we found one minimal solution and it suffices to verify only solutions
with an equal cost. As soon as we observe solutions with higher cost, we can
stop the algorithm and return all tuples that satisfy $\mathcal{E}$. Clearly,
this search still has a worst case complexity of
$\mathcal{O}\left(\prod_{i=1}^{m}|A_{i}|\right)$, but if _consistent_ tuples
(i.e., tuples that satisfy $\mathcal{E}$) are observed early, we do much
better than this worst case. Still, in this naive strategy, we will in general
observe tuples for which we know they will not be consistent and skipping
those tuples can further improve the efficiency of the search.

###  4.3 Exploiting independence of rules

One way of improving the complexity of LCF iteration is to treat groups of
attributes independently. Suppose we can partition $\mathcal{E}$ in two sets
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ such that attributes involved in rules
from $\mathcal{E}_{1}$ are not involved in rules from $\mathcal{E}_{2}$ and
vice versa. Formally:

$\left(\bigcup_{E\in\mathcal{E}_{1}}\mathcal{I}\left(E\right)\right)\cap\left(\bigcup_{E\in\mathcal{E}_{2}}\mathcal{I}\left(E\right)\right)=\emptyset.$
(5)

When this condition is satisfied, we say that $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ are _independent_. For a partition into independent sets,
there are two essential properties that hold. First, Barcaroli and Venturi
[12] showed that if $\mathcal{E}$ partitions into independent sets
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$, then
$\underline{\Omega}\left(\mathcal{E}\right)=\underline{\Omega}\left(\mathcal{E}_{1}\right)\cup\underline{\Omega}\left(\mathcal{E}_{2}\right)$.
Second, the following proposition holds.

###### Proposition 4

Let $\left(\phi,\mathcal{E}\right)$ be a set of EPKs on $\mathcal{R}$ and $R$
a relation with schema $\mathcal{R}$. If $\mathcal{E}$ partitions into two
independent sets $\mathcal{E}^{\prime}$ and $\mathcal{E}^{\prime\prime}$ such
that $\mathcal{E}^{\prime}$ are edit rules on
$\mathcal{R}^{\prime}\subseteq\mathcal{R}$ and $\mathcal{E}^{\prime\prime}$
are edit rules on $\mathcal{R}^{\prime\prime}\subseteq\mathcal{R}$ with
$\mathcal{R}^{\prime}\cup\mathcal{R}^{\prime\prime}=\mathcal{R}\setminus\mathcal{K}$
then $R^{*}$ is a $\Delta$-minimal repair if and only if
$R^{*}[\mathcal{K}\cup\mathcal{R}^{\prime}]$ is a $\Delta$-minimal repair for
$R[\mathcal{K}\cup\mathcal{R}^{\prime}]$ against
$\left(\phi,\mathcal{E}^{\prime}\right)$ and
$R^{*}[\mathcal{K}\cup\mathcal{R}^{\prime\prime}]$ is a $\Delta$-minimal
repair for $R[\mathcal{K}\cup\mathcal{R}^{\prime\prime}]$ against
$\left(\phi,\mathcal{E}^{\prime\prime}\right)$.

These results show for any $(\phi,\mathcal{E})$ that if $\mathcal{E}$ is
composed of independent sets, then repairing inconsistencies can be done for
$(\phi,\mathcal{E}_{1})$ and $(\phi,\mathcal{E}_{2})$ separately. Note that
recursive application of both propositions allows to generalize the results to
a partition into $K$ independent sets. In Figure 1 (b), we have two
independent sets: the first four rules and last two rules.

###  4.4 Finding minimal repairs under full key constraints

We now combine all the results from the previous into an algorithm. The main
idea is that, when we perform an LCF iteration over some set
$A_{1}\times\ldots\times A_{m}$, we try to keep $m$ small by focusing on
$\subset$-minimal covers.

Consider some class $R_{\mathcal{K}=\mathbf{k}}$ and let us now index tuples
consistent with the LCF order, just as we did for individual attributes. That
is, the first tuple under LCF order is $r_{(1)}$, the second tuple $r_{(2)}$
and so on. There are now two cases.

$\boxed{Case\ 1}$. Suppose $r_{(1)}\models\mathcal{E}$, then this tuple is one
of the minimal repairs for $R_{\mathcal{K}=\mathbf{k}}$. That means, if we
replace the attributes $\mathcal{R}_{1}\cup\mathcal{R}_{2}$ of each tuple in
$R_{\mathcal{K}=\mathbf{k}}$ with $r_{(1)}$, then the class is repaired with
minimal cost. Of course, $r_{(1)}$ is not guaranteed to be the only minimal
cost repair. Therefore, consider the set of tuples:

$M_{\mathbf{k}}=\\{r\mid r\in A_{1}\times\ldots\times
A_{k}\wedge\beta(\mathbf{k},r)=\beta(\mathbf{k},r_{(1)})\\}$ (6)

This set contains the first $|M_{\mathbf{k}}|$ tuples under LCF order that all
have equal cost. Clearly, if $\exists r^{\prime}\in
M_{\mathbf{k}}:r^{\prime}\models\mathcal{E}$, then the set of minimal cost
repairs for $R_{\mathcal{K}=\mathbf{k}}$ is a subset of $M_{\mathbf{k}}$ and
it suffices to inspect $M_{\mathbf{k}}$.

$\boxed{Case\ 2}$. If the first case does not apply, we have $\forall
r^{\prime}\in M_{\mathbf{k}}:r^{\prime}\not\models\mathcal{E}$. We then want
to change $r^{\prime}$ into some $r^{\prime\prime}\notin M_{\mathbf{k}}$. If
we do that by modifying its value for $a$, then:

$\beta\left(\mathbf{k},r^{\prime\prime}\right)=\beta\left(\mathbf{k},r^{\prime}\right)+c\left(r^{\prime\prime}[a]\right)-c\left(r^{\prime}[a]\right)$
(7)

for which we know that
$c\left(r^{\prime\prime}[a]\right)-c\left(r^{\prime}[a]\right)>0$ because
$r^{\prime\prime}\notin M_{\mathbf{k}}$. This can be generalized to:

$\beta\left(\mathbf{k},r^{\prime\prime}\right)=\beta\left(\mathbf{k},r^{\prime}\right)+\sum_{a\in\mathcal{R}_{1}\cup\mathcal{R}_{2}}c\left(r^{\prime\prime}[a]\right)-c\left(r^{\prime}[a]\right).$
(8)

where we require that
$c\left(r^{\prime\prime}[a]\right)>c\left(r^{\prime}[a]\right)$ to ensure
$r^{\prime\prime}\notin M_{\mathbf{k}}$. The above expression shows that the
cost for repairing $R_{\mathcal{K}=\mathbf{k}}$ by $r^{\prime\prime}$ can be
written as the cost for $r^{\prime}$ and the functions $c\left(.\right)$. But
since $r^{\prime}\in M_{\mathbf{k}}$, we know that
$\beta\left(\mathbf{k},r^{\prime}\right)$ is already minimal. Hence, in order
to minimize $\beta\left(\mathbf{k},r^{\prime\prime}\right)$ we must minimize
the second term of the right hand side, conditioned on
$r^{\prime\prime}\models\mathcal{E}$. To do so, we consider for each attribute
$a\in\mathcal{R}$ an _induced_ cost function $\Delta_{a}^{\bullet}$ on the set
$A^{\bullet}=\\{v\mid v\in A\wedge c(v)>r^{\prime}[a]\\}$ that satisfies
$\forall v\in
A^{\bullet}:\Delta_{a}^{\bullet}\left(r^{\prime}[a],v\right)=c\left(v\right)-c\left(r^{\prime}[a]\right)$.
This induced cost function gives the cost to change attribute $a$ of tuple
$r^{\prime}$ accounting for all tuples in $R_{\mathcal{K}=\mathbf{k}}$. By
construction, $\Delta_{a}^{\bullet}$ is positive definite on $A^{\bullet}$ and
we can now write:

$\beta\left(\mathbf{k},r^{\prime\prime}\right)=\beta\left(\mathbf{k},r^{\prime}\right)+\Delta^{\bullet}(r,r^{\prime\prime}).$
(9)

It follows that if we find a $\Delta^{\bullet}$-minimal repair $r^{*}$ for
$r^{\prime}$, then clearly, we minimize
$\beta\left(\mathbf{k},r^{\prime\prime}\right)$ under the condition
$r^{\prime\prime}\models\mathcal{E}$. This now leads us the main theorem of
this paper.

###### Theorem 2

For any class $R_{\mathcal{K}=\mathbf{k}}\subseteq R$ with schema
$\mathcal{R}$, some cost model $\Delta$ and a set of EPKs
$\left(\phi,\mathcal{E}\right)$, any $\Delta$-minimal repair $r^{*}$ is the
$\Delta^{\bullet}$-minimal repair of some tuple $r^{\prime}\in
M_{\mathbf{k}}$.

The importance of Theorem 2 is that it reduces finding minimal repairs for
EPKs $\left(\phi,\mathcal{E}\right)$ to finding minimal repairs for
$\mathcal{E}$, but with a modified cost model $\Delta^{\bullet}$. In the
previous section, we already pointed out that this can be done by inspection
of $\subset$-minimal covers. Now, as a final step, we connect this inspection
to the notion of LCF iteration. More precisely, suppose we have some
$r^{\prime}\in M_{\mathbf{k}}$ for which we have the induced cost model
$\Delta^{\bullet}$. If $r^{\prime}\not\models\mathcal{E}$, we compose the
failing rules as $\\{E\mid
E\in\underline{\Omega}\left(\mathcal{E}\right)\wedge r^{\prime}\not\models
E\\}$. Next, we find all $\subset$-minimal covers $\mathcal{C}$ of this set of
failing rules. For each such cover $\mathcal{C}$, we can find a minimal
$\mathcal{C}$-repair by using Algorithm 1 where $m=|\mathcal{C}|$. In other
words, we do an LCF-tuple iteration, but consider only attributes in
$\mathcal{C}$. In general, we can expect $|\mathcal{C}|$ to be significantly
smaller than $|\mathcal{R}|$. In a final step, we need to account for the fact
that the solution attributes of a $\Delta$-minimal repair are not necessarily
equal to a $\subset$-minimal cover, but can also be a superset of such a
cover. To account for this, we can use Theorem 1 and inspect only those value
combinations for $\mathcal{C}$ that occur in LCF order before any
$\mathcal{C}$-minimal repair. In addition, if we consider constant edit rules,
we can use Proposition 3 to discard any value combinations for $\mathcal{C}$
where some value changes to attributes in $\mathcal{C}$ are unnecessary. All
the ideas and properties we have presented can now be summarized in the pseudo
code of Algorithm 2.

Algorithm 2 Full Key Repair

1:Relation $R$ with schema $\mathcal{K}\cup\mathcal{R}^{\prime}$ and EPKs
$\left(\mathcal{K}\rightarrow\mathcal{R}^{\prime},\mathcal{E}\right)$

2:Relation $R^{*}$ that is a $\Delta$-minimal repair of $R$

3:$\underline{\Omega}\left(\mathcal{E}\right)\leftarrow$ FCF$(\mathcal{E})$

4:for $\mathbf{k}\in R[\mathcal{K}]$ do

5: $\varphi\leftarrow\emptyset$

6: $M_{\mathbf{k}}\leftarrow$ LCF($\mathbf{k},\Delta$)

7: if $\exists r^{\prime}\in M_{\mathbf{k}}:r^{\prime}\models\mathcal{E}$ then

8: $\varphi\leftarrow\\{r^{\prime}\mid r^{\prime}\in
M_{\mathbf{k}}:r^{\prime}\models\mathcal{E}\\}$

9: else

10: for $r^{\prime}\in M_{\mathbf{k}}$ do

11: for $\mathcal{C}\in$
covers($r^{\prime},\underline{\Omega}\left(\mathcal{E}\right)$) do

12: $\varphi_{\mathcal{C}}\leftarrow$
findRepairs($r^{\prime},\underline{\Omega}\left(\mathcal{E}\right),\Delta^{\bullet},\mathcal{C}$)

13: $\varphi\leftarrow$ merge($\varphi,\varphi_{\mathcal{C}}$)

14: end for

15: end for

16: end if

17: $r^{*}\leftarrow$ select($\varphi$)

18: apply($r^{*}$, $R_{\mathcal{K}=\mathbf{k}}$)

19:end for

In Algorithm 2, we assume that $\mathcal{E}$ cannot be partitioned into
independent sets. If it can, then Algorithm 2 should applied for each
independent set separately. The algorithm starts with composing a sufficient
set $\underline{\Omega}\left(\mathcal{E}\right)$ for the rules $\mathcal{E}$
(line 3). It is assumed here that $\underline{\Omega}\left(\mathcal{E}\right)$
does not contain a contradiction. If is does, then the EPKs are not
satisfiable (Proposition 1) and the algorithm should return an error. Next, we
iterate over each key value $\mathbf{k}$ and compose the set $M_{\mathbf{k}}$
of minimal changes according to $\Delta$ (line 6). If this set contains tuples
that satisfy $\mathcal{E}$, these tuples have minimal cost and we assign all
such tuples in $M_{\mathbf{k}}$ to the set $\varphi$ (line 8). Else, we
iterate over each $r^{\prime}\in M_{\mathbf{k}}$ and compose the
$\subset$-minimal covers $\mathcal{C}$ for $r^{\prime}$ in terms of
$\underline{\Omega}\left(\mathcal{E}\right)$ (line 11). For each cover
$\mathcal{C}$, we search for possible minimal repairs of $r^{\prime}$ using
$\mathcal{C}$ as the attributes we change and where we reason in terms of the
induced cost model $\Delta^{\bullet}$ (line 12). To do so, we iterate over
possible values for $\mathcal{C}$ in LCF order, where cost is now determined
by $\Delta^{\bullet}$. This LCF iteration can be done by using a modification
of Algorithm 1, where we stop as soon as we have observed all minimal repairs.
In the same step, we also inspect possible supersets of $\mathcal{C}$, where
we can apply Theorem 1. That means, when we iterate over values for
$\mathcal{C}$ in LCF order, each value combination that does not lead to a
$\mathcal{C}$-minimal repair is fixed and we search for
$\Delta^{\bullet}$-minimal repairs, but now under the condition that the
values for $\mathcal{C}$ are fixed. If we deal with constant edit rules, we
can also use Proposition 3 to restrict this search. The possible minimal
repairs using $\mathcal{C}$ (or a superset) are stored in the set
$\varphi_{\mathcal{C}}$ and this set is merged with the repairs $\varphi$.
That means, if the newly found repairs have an equal cost, then we take the
union of both sets. If $\varphi_{\mathcal{C}}$ has a lower cost, then
$\varphi$ is replaced with $\varphi_{\mathcal{C}}$. Else, we just keep
$\varphi$. Because of the latter, we can keep at all times an upper bound for
the cost of repairing. As we always iterate in terms of LCF order, we can
always abort searching whenever we exceed this upper bound. This upper bound
_must_ monotonically decrease during the loop over covers (line 11) _and_
during the loop over tuples $r^{\prime}\in M_{\mathbf{k}}$ (line 10). When we
have inspected all $\subset$-minimal covers $\mathcal{C}$ and their supersets,
variable $\varphi$ will contain all $\Delta$-minimal repairs for
$R_{\mathcal{K}=\mathbf{k}}$ (Theorem 2). We then select one of the minimal
repairs (line 17) and apply it to each of the tuples in
$R_{\mathcal{K}=\mathbf{k}}$ (line 18).

###  4.5 The case of partial key constraints

Consider now the general case of a partial key constraint
$\phi:\mathcal{K}\rightarrow\mathcal{R}_{1}$ and where $\mathcal{E}$ contains
edit rules defined over $\mathcal{R}_{1}\cup\mathcal{R}_{2}$. The main problem
is now that a $\Delta$-minimal repair for $R[\mathcal{K}\cup\mathcal{R}_{1}]$
and constraints $(\phi,\mathcal{E}_{1})$ will not necessarily lead us to a
$\Delta$-minimal repair for $R$. In Figure 1 (c), attributes ‘placebo’ and
‘active compare’ are not determined by ‘#study’, which means these design
parameters depend on the country where the study was executed.

In order to solve the more generic problem of partial keys, we can again
assume that each set of tuples $R_{\mathcal{K}=\mathbf{k}}$ is treated
separately and that there are no independent sets in $\mathcal{E}$ (if there
are, we can use a divide-and-conquer strategy). In the example of Figure 1, we
have already noted that the set of rules shown in (b) contains two independent
sets. In the first independent set, rules involve only attributes determined
by ‘#study’, so that problem can be treated entirely by Algorithm 2. In the
second independent set, rules involve both attributes determined by ‘#study’
(i.e., ‘control’) and attributes not determined by ‘#study’ (i.e., ‘placebo’
and ‘active compare’). Let us now consider a slightly modified example as
shown in Figure 3.

Figure 3: A modification of the data in Figure 1

In order to find minimal repairs, we first use Algorithm 2 to find a
$\Delta$-minimal repair for
$R_{\mathcal{K}=\mathbf{k}}[\mathcal{K}\cup\mathcal{R}_{1}]$ under the same
cost model but for EPKs $\left(\phi,\mathcal{E}_{1}\right)$. Hereby,
$\mathcal{E}_{1}$ contains all rules that involve _only_ attributes from
$\mathcal{R}_{1}$. In the example of Figure 3, this means we need to find a
minimal repair for attribute ‘control’ where $\mathcal{E}_{1}=\emptyset$.
Assuming a constant cost model, this leads to a single repair where ‘control’
is assigned the value ‘No’ and cost equals $1$. If we then consider attributes
‘placebo’ and ‘active compare’, all values ‘Yes’ needs to be changed into ‘No’
to satisfy the edit rules, implying a total cost of $6$. However, if we would
choose ‘control’ equal to ‘Yes’, the total cost would be $3$.

In order to account for this, we can modify our algorithm in a simple manner.
When we search for repairs with induced cost models (Algorithm 2, line 12), we
do this by LCF iteration on a space determined by a cover $\mathcal{C}$.
However, if we find a repair for
$R_{\mathcal{K}=\mathbf{k}}[\mathcal{K}\cup\mathcal{R}_{1}]$, we must then
verify if that repair would cause any violations of edit rules for
$R_{\mathcal{K}=\mathbf{k}}$. If it does, we can compute the _additional cost_
for fixing those violations for each tuple in $R_{\mathcal{K}=\mathbf{k}}$. We
then keep on progressing the LCF iteration until we are sure we have found all
minimal repairs, just like before. Note that this approach will work best if
$|\mathcal{R}_{2}|<<|\mathcal{R}_{1}|$, which means that most attributes are
determined by $\mathcal{K}$. This is a reasonable assumption in the setting of
data fusion.

##  5 Cost Models and Repair Selection

After introducing the main methodology for finding repairs, it should be clear
that cost functions are of crucial importance in our methodology. Moreover, as
minimal repairs are not unique, we require repair selection methods to select
a single repair from the minimal alternatives. In this section, we discuss
some practical methods to build cost functions and repair selection methods.

###  5.1 Cost functions

In the most simple case, a cost function is _constant_ and we have:

$\Delta_{a}(v,v^{\prime})=\left\\{\begin{array}[]{cc}0&v=v^{\prime}\\\
\alpha&v\neq v^{\prime}\end{array}\right.$

Here, $\alpha$ is some constant integer cost that can be used to reflect the
reliability of attribute $a$. That is, a more reliable attribute $a$ can be
assigned a higher cost $\alpha$. Using constant cost functions for edit rules
has the advantage that all minimal repairs must have a solution equal to a
$\subset$-minimal cover, which makes it much more easy to find repairs. When
using constant cost functions in the setting of EPKs, then $\alpha=1$ leads to
an induced cost function $\Delta_{a}^{\bullet}$ that uses _majority voting_
for values.

It has been established in the past that majority voting is not always the
best choice as a fusion model [13, 14]. A better approach is to account for
reliability of sources [14], which in our case correspond to tuples in $R$.
Usually, reliability is estimated based on some training data. We propose to
deal with reliability in a different, non-supervised manner by assigning each
row in $R$ it’s own cost function. The constant $\alpha$ we use in a constant
cost model is then multiplied with a factor that is inverse proportionate to
the ‘badness’ of the row. This multiplier is computed, for each row $r\in R$
as follows:

$\left(|\mathcal{R}|-\left|\\{a\mid
r[a]=\bot\vee\left(a\in\mathcal{I}\left(E\right)\wedge r\not\models
E\right)\\}\right|\right)^{\omega}$ (10)

Hereby, we make a very course and pessimistic estimate of the number of
attributes that are ‘in error’ by looking at those attributes that either
occur in a failing rule or have a null value. We then subtract that number
from the total number of attributes (i.e. $|\mathcal{R}|$) and raise it to the
power $\omega$, which when greater then $1$ acts an amplifier of the effect.
We can then compute the cost for changing the value of attribute $a$ for row
$r$ from $v$ to $v^{\prime}$ as:

$\Delta_{a}(v,v^{\prime})\cdot\left(|\mathcal{R}|-\left|\\{a\mid
r[a]=\bot\vee\left(a\in\mathcal{I}\left(E\right)\wedge r\not\models
E\right)\\}\right|\right)^{\omega}$ (11)

By doing so, we basically model that making a change to a row that contains
many attributes that might be in error has a relatively low cost. We will show
in Section 7 that this heuristic can provide a significant boost in the
quality of repairs.

Besides these two basic cost functions, a plenitude of other cost functions
can be considered. For example, when data are additive, the cost for changing
$v$ into $v^{\prime}$ can account for the _magnitude_ $|v-v^{\prime}|$ of the
change. Another way of dealing with cost, is to account for specific error
mechanisms. For example, when $v$ and $v^{\prime}$ are string data, one could
assign a lower cost to a change where the Levenshtein distance between $v$ and
$v^{\prime}$ is very small, indicating that the change from $v$ to
$v^{\prime}$ can be explained by a typographical error. In the same spirit,
edits of dates could be equipped with error-aware cost functions. As a final
example, a cost function could also account for a priori preferences among
values. Consider for example a case with allergen information. Assume there
are different sources that provide conflicting information on the allergens of
a single product. One source could say that product A contains gluten and
another source could say product A does not contain gluten. In such a
scenario, one is inclined to prefer the value of the source that induces the
least _risk_ and therefore model that the cost of changing ‘gluten’ into ‘no
gluten’ is much greater than the cost of the opposite change. We will
demonstrate the impact of such a cost model in Section 7.

###  5.2 Repair selection

When multiple repairs are found to have a minimal cost, it can be desirable to
provide a further selection strategy to choose a ‘best’ repair from the
minimal ones. One obvious method to do so, is simply to pick a minimal repair
at random. In this line of thought, we consider each minimal repair to be
equally good and make no further distinction between minimal repairs.

A second method would be to aim at respecting the (marginal and joint)
distributions of the observed data as much as possible. To that end, one often
uses the clean data (i.e., the data in $R$ that contains no violations of
rules) to estimate the distributions of the data. When such distributions are
available, one can select a repair among all minimal repairs with a
probability that is proportionate to the observed frequency of that repair.
There are several ways to implement such a strategy. We will resort in our
experiments to a simple method where make an estimate of the probability of
observing a repaired object, meaning we measure the frequency of the entire
object after repairing. Alternatives could be to observe the frequency of only
the part of the attributes that are changed or make a selection of the
attributes for which frequencies are measured.

As a final note, we emphasize the distinction between cost functions and
repair selection. One could argue that repair selection becomes largely
disposable if we would include for example information about frequency in the
computation of cost. We do however reject this idea. In our methodology,
_cost_ is something that can be used to make _local_ distinctions between
repairs for a given entity. It accounts for information about that entity and
not other entities. Whenever there are multiple repairs that are minimal in
terms of cost, _global_ information about the data, such as distributions, can
be used to make a further distinction. In general, we think this difference is
important to avoid an all too large influence of the distributions in for
example extremely skewed datasets.

##  6 Related Work

Data fusion covers a broad category of problems where information from
different sources needs to be consolidated. In this paper, we study the
specific scenario where (i) each source is modelled by a single tuple of a
relation and (ii) consolidation means merging into a single tuple for those
attributes under the partial key constraint. This seemingly simple problem,
and slight variants of it, has been studied surprisingly often in the vast
body of literature dealing with data fusion. The very first approaches kept a
close connection to the relational setting. They used relational operators
like union and (match) join [15, 16, 17, 18]. Continuing on this idea, the SQL
language has been extended with a fuse by operator, yielding a declarative
approach towards data fusion [19, 20]. An interesting observation is that
these relational approaches usually use operators like subsumption and
complement to ‘clean’ a relation and minimize the amount of null values [21].
In that extent, it can be said that the even earliest approaches used some
notion of consistency to optimize the result.

One particular problem with fusion by means of relational operators, is that
it does not deal well with errors in data. To that extent, attribute-level
fusion functions can be used to deal with linear conversions [22, 23],
specificity of information [24] and multi-valued data [25, 26]. A good
overview of possible attribute-level fusion functions can be found in [27].
Another approach to resolve inconsistencies is to add sufficiently many
sources. A particular problem hereby is that sources can copy from one another
and knowing these dependencies turns out to be important in source selection
[13]. Moreover, it has been established that estimating the reliability of the
different sources significantly influences the quality of the fusion operator
[14, 28]. In the current paper, we have adopted this idea, but rather than
using a training set to estimate reliability, we use an unsupervised estimate
of the reliability based on failing rules and missing values.

The attribute-level fusion functions that are mentioned here aim to resolve
inter-source inconsistencies. The approach we develop here is more general in
the sense it allows to deal with both intra-source and inter-source
inconsistencies. To that extent, some approaches from the field of constraint-
based consistency verification follow the same strategy. For example, Llunatic
allows to model extended equality-generating dependencies (EGDs) and uses a
generalization of the Chase algorithm to construct a Chase tree that can be
used to search repairs of dirty data [4, 5]. In practical applications, the
branching factor of a Chase tree is so high, that pruning strategies are
required to keep the computational effort feasible. A consequence thereof is
that solutions are not guaranteed to be minimal, although there are good
heuristics to approximate minimal solutions. Another way to find repairs, is
by learning a probabilistic model of the data [6]. Such a methodology is used
in HoloClean, that allows to model a set of denial constraints (DCs) that need
to be satisfied on the data [6]. HoloClean uses the available constraints in
combination with other information like correlation analysis, outlier
detection techniques, reference data… to learn a model for the data. From that
model, it then generates repairs for the given data. Finally, Raha [29] and
Baran [7] are two semi-supervised systems for “configuration-free” error
detection (Raha) and repair (Baran). The main idea here is that no constraints
need to be given. Instead, error patterns are learned from a small dirty
dataset for which either users provide correct labels or a clean version is
available. Parker differs from these approaches by using a specific type of
constraints (EPKs) that are less expressive than extended EGDs and DCs, but
can use the set-cover approach to search for minimal repairs efficiently.
Hereby, a wide variety of cost functions can be used to model a broad range of
error mechanisms.

##  7 Experimental Study

###  7.1 Experimental Setup

In the following, we describe the configurations of our experiments. To allow
for reproducibility, the datasets, source code, raw results and analyses of
the results are available online
333https://gitlab.com/antoonbronselaer/parker-reproducibility.

Table 1: Dataset descriptions. The dataset size indicates the number of rows and attributes. Errors is the number of incorrect cells according to the Gold Standard (GS). The GS size includes the number (and percentage) of rows covered from the dataset. Dataset | Size | Errors | GS Size | Constraints
---|---|---|---|---
Allergen | $1160\times 22$ | $358$ |  $206$ $(17.8\%)$ |  key = $code$ $E_{1}=\neg(t_{x}.nuts<t_{x}.brazil\\_nuts$) $E_{2}=\neg(t_{x}.nuts<t_{x}.macadamia\\_nuts)$ $E_{3}=\neg(t_{x}.nuts<t_{x}.hazelnut)$ $E_{4}=\neg(t_{x}.nuts<t_{x}.pistachio)$ $E_{5}=\neg(t_{x}.nuts<t_{x}.walnut)$
EudraCT | $86670\times 9$ | $2962$ |  $3133$ $(3.6\%)$ |  key = $eudract\\_number$ $E_{1}=\neg(t_{x}.double\\_blind=yes\wedge t_{x}.open=yes$) $E_{2}=\neg(t_{x}.single\\_blind=yes\wedge t_{x}.open=yes$) $E_{3}=\neg(t_{x}.double\\_blind=no\wedge t_{x}.single\\_blind=no\wedge t_{x}.open=no$) $E_{4}=\neg(t_{x}.controlled=no\wedge t_{x}.placebo=yes$) $E_{5}=\neg(t_{x}.crossover=yes\wedge t_{x}.parallel\\_group=yes$) $E_{6}=\neg(t_{x}.double\\_blind=yes\wedge t_{x}.single\\_blind=yes$) $E_{7}=\neg(t_{x}.active\\_comparator=yes\wedge t_{x}.controlled=no$) $E_{8}=\neg(t_{x}.arms\leq 1\wedge t_{x}.placebo=yes$) $E_{9}=\neg(t_{x}.arms\leq 1\wedge t_{x}.active\\_comparator=yes$)
Flight | $776067\times 5$ | $134778$ |  $70951$ $(9\%)$ |  key = $\\{date\\_collected,flight\\_number\\}$ $E_{1}=\neg(t_{x}.actual\\_departure\geq t_{x}.actual\\_arrival$) $E_{2}=\neg(t_{x}.scheduled\\_departure\geq t_{x}.scheduled\\_arrival$)

(a) Allergen

(b) EudraCT

(c) Flight

Figure 4: Frequency of errors in the different attributes across the datasets.

#### Datasets

We evaluate our approach using three real-world datasets, which differ in
size, number of errors, and number of considered constraints. Each dataset is
accompanied by a gold standard that contains a sample of correct tuples. Table
1 provides a summary of the dataset descriptions, including the the size of
the gold standard and constraints considered in our experiments.

  * 1.

Allergen. This dataset is composed of data about products and their allergens,
which were crawled444Access date: 24 November, 2020. from the German version
of the Alnatura555https://www.alnatura.de/de-de/ and Open Food
Facts666https://world.openfoodfacts.org/ websites. The attributes of this
dataset indicate the presence (‘2’), traces (‘1’), or absence (‘0’) of
allergens in a product. The constraints model the correspondence between
allergens related to nuts in general and specific nuts. The gold standard was
consolidated by the authors by looking at actual pictures of the products’
labels provided by independent web sources. For the initial annotations, the
inter-rater agreement computed with the Fleiss’ kappa measure was $0.844$.
Discrepancies were resolved via mutual agreement. The repair of this dataset
is particularly challenging due to the high number of attributes and error
distribution across them.

  * 2.

EudraCT. This dataset contains data about clinical trials conducted in Europe.
This dataset was obtained from the European Union Drug Regulating Authorities
Clinical Trials Database (EudraCT) register777https://eudract.ema.europa.eu/
and the gold standard was created from external
registries888https://clinicaltrials.gov/999https://www.drks.de/drks_web/. The
gold standard of this dataset does not contain the correct values for the
attributes placebo and active_comparator, hence, they do not appear in Figure
4(b); yet, the edit rules $E_{4}$, $E_{7}$, $E_{8}$ and $E_{9}$ are kept as
they contribute to the repairs of other attributes. The repair of this dataset
is particularly challenging due to the number of constraints to consider.

  * 3.

Flight. This dataset describes flights annotated with the departing and
arrival airports as well as their expected and actual time of departure and
arrival. The dataset and gold standard used in this work are a modification of
the Flight Dataset101010http://lunadong.com/fusionDataSets.htm. We
consolidated all the temporal information into the same timezone (UTC-0) and
format. In this way, we can specify edit rules such as $E_{1}$ and $E_{2}$
(cf. Table 1). The repair of this dataset is challenging due to the high
number of tuples.

#### Approaches

We compare our proposed solution Parker with recent state-of-the-art
approaches for error correction using the following configurations.

  * 1.

Parker. We evaluate different configurations of Parker (denoted
$\cdot/\cdot/\cdot$) with variations in the key constraint $\phi$, the cost
model $\Delta$ and the repair selection strategy, respectively. For the _key
constraint_ , we either consider a full key constraint (F) or no key
constraint (N). We did not test a partial key scenario due to lack of golden
standards for that configuration. The case with no key constraint allows to
study an edit-rules-only case versus EPKs. For the _cost model_ , our baseline
scenarios are constant cost functions (C) and cost functions that adopt an
estimate of reliability based on observed errors (E) as introduced in Section
5.1. In the latter case, $\omega=4$ provided the best results. For the
‘Allergen’ dataset, we additionally consider a preference cost function (P).
This cost function models combines a reliability estimate ($\omega=4$) with a
risk-aversion strategy, where we are reluctant to changes that remove an
indication of an allergen (high cost) and are more inclined to accept repairs
that add indications of allergens (low cost). For the _repair selection_ , we
evaluate the frequency-based (F) and random (R) strategies. Frequency-based
selection means here we sample repairs with a probability equal to their
observed frequency in the clean data. In both cases, a frequent pattern tree
was constructed from the clean data. As a final note, we also tested scenarios
where we removed the edit rules and used only the key constraint. Those
scenarios are marked with a $*$ and in that case, we do not consider cost
functions with a reliability estimate as there are no edit rules to detect
tuple-level errors.

  * 2.

HoloClean [6]. We evaluate the performance of
HoloClean111111https://github.com/HoloClean/holoclean v1.0.0 using different
error detector strategies: null detector (HoloClean-N), violation detector
(HoloClean-V), and both detectors (HoloClean). The other parameters were used
as provided by default.

  * 3.

Raha+Baran [29, 7]. Raha and Baran121212https://github.com/BigDaMa/raha v.1.25
are semi-supervised approaches that learn from correct labels. Therefore, Raha
and Baran were provided with the subset of each dataset for which the gold
standard is available. To detect errors, Raha relies on a labelling budget
$\theta_{Label}$ to acquire correct labels for erroneous cells. We set up the
labelling budget to $\theta_{labels}=20$, as specified by the authors [29].
The errors detected by Raha are then fed into Baran for correction. We run
Raha+Baran 10 times, and report on the average performance.

#### Evaluation Metrics

We report on precision, recall, and the $F_{1}$ metrics. A true positive
corresponds to a cell that is correctly repaired with respect to the gold
standard. Precision ($P$) is the number of correct repairs divided by the
number of total repairs performed by the approach. Recall ($R$) is the number
of correct repairs divided by the number of errors measured by comparing the
input data with the gold standard. $F_{1}$ is the harmonic mean of precision
and recall. We also measure the effectiveness of the approaches per attribute;
we compute precision, recall, and $F_{1}$ scores of the repairs in each
attribute and average them by the number of attributes in the dataset to
obtain the macro-precision ($P_{M}$), macro-recall ($R_{M}$) and macro-$F_{1}$
($F_{1M}$). The efficiency of the approaches is measured as the runtime in
seconds ($s$).

#### Implementation

Parker is implemented in Java 8 and is available as a part of the ledc-
sigma131313https://gitlab.com/ledc/ledc-sigma package. The implementation
adopts also variables edit rules such as those appearing in Flight (Table 1).
HoloClean, Raha, and Baran are executed with Python 3.6. Parker and HoloClean
use PostgreSQL 10.17 as backend. We execute the experiments on an Ubuntu
18.04.5 machine, with an i9-10940X CPU (3.30GHz, 14 cores with hyper-
threading) and 256 GB RAM. Execution times are measured with the Linux command
time.

###  7.2 Overall Effectiveness of the Approaches

Table 2: Effectiveness of the repairs of the evaluated approaches. n/a indicates that the approach configuration is not applicable to that dataset. – indicates that the approach could not be executed in that dataset. Best results per dataset are highlighted in bold. | Allergen | EudraCT | Flight
---|---|---|---
Approach | $F_{1}$ | $P$ | $R$ | $F_{1}$ | $P$ | $R$ | $F_{1}$ | $P$ | $R$
HoloClean | 0.01 | 0.06 | 0.01 | 0.49 | 0.91 | 0.33 | 0.56 | 0.81 | 0.43
HoloClean-N | n/a | n/a | n/a | 0.47 | 0.87 | 0.32 | 0.57 | 0.81 | 0.43
HoloClean-V | 0.01 | 0.06 | 0.01 | 0.49 | 0.91 | 0.33 | 0.56 | 0.81 | 0.43
Raha+Baran | 0.46 | 0.51 | 0.42 | 0.77 | 0.87 | 0.70 | – | – | –
Parker F/E/F | 0.13 | 0.20 | 0.09 | 0.76 | 0.93 | 0.65 | n/a | n/a | n/a
Parker F/C/F | 0.15 | 0.24 | 0.11 | 0.74 | 0.90 | 0.62 | n/a | n/a | n/a
Parker F/E/R | 0.29 | 0.45 | 0.21 | 0.65 | 0.80 | 0.55 | 0.81 | 0.82 | 0.81
Parker F/C/R | 0.28 | 0.44 | 0.20 | 0.64 | 0.79 | 0.54 | 0.68 | 0.69 | 0.67
Parker N/C/F | 0.01 | 0.50 | 0.01 | 0.50 | 0.63 | 0.41 | n/a | n/a | n/a
Parker N/C/R | 0.01 | 0.50 | 0.01 | 0.48 | 0.60 | 0.40 | 0.46 | 0.44 | 0.49
Parker F/C/F* | 0.14 | 0.22 | 0.10 | 0.69 | 0.88 | 0.57 | n/a | n/a | n/a
Parker F/C/R* | 0.26 | 0.40 | 0.19 | 0.57 | 0.73 | 0.47 | 0.68 | 0.70 | 0.67
Parker F/P/F | 0.42 | 0.65 | 0.31 | n/a | n/a | n/a | n/a | n/a | n/a

We compare the effectiveness of the repairs obtained with Parker and with the
state-of-the-art approaches. Table 2 presents a summary of the precision,
recall, and $F_{1}$ scores of repairs for each dataset. Overall, we observe
that none of the studied approaches completely overcomes the other baselines.
This is due to the different repair strategies implemented by the approaches
and the distribution of errors and coverage of edit rules in the datasets.

The effectiveness of Parker depends on the cost model, the repair selection
strategy, and the leverage of the constraints. In the Allergen dataset, the
preferential cost model of Parker that implements a risk-aversion strategy
clearly outperforms the other Parker configurations, since this type of model
captures the intrinsic properties of this dataset. Yet, Parker can only handle
repairs when the input sources disagree on the attribute values of an entity.
For example, Parker could not compute correct repairs for the attribute
cashew, as both web sources indicated the absence of an allergen for the same
product. This results in Parker achieving higher precision than recall. A
similar behaviour is observed in Parker over the EudracCT dataset. In EudraCT,
the error-based cost model (E) and frequency-based repair strategies (F)
slightly outperform their corresponding counterparts with constant-based cost
model (C) and random repairs (R), respectively. In addition, when edit rules
are disabled in Parker (N), we observe a major drop in both precision and
recall. This is due to the relatively high number of rows ($\sim 10\%$) that
are incorrect due to violations of edit rules; this aspect is further
discussed in Section 7.3.

In the Flight dataset, we tested only the configuration of Parker that selects
repairs randomly (R). Here, the error-based cost model (E) outperforms the
other configurations of Parker. The reason for this is that E encodes the fact
that sources with null values or violations of edit rules are considered less
trustworthy, thus, increasing the cost of the repairs. To verify that this
behaviour is not due to the effects of the edit rules, we also tested the
additional configuration Parker F/E/R* (not reported in the table), which
achieves close performance to F/E/R, i.e., 0.79 in F1-score, precision, and
recall. This confirms that the gain in performance is mostly due to the error-
based cost model (E) implemented by Parker, while the consideration of edit
rules allow to correctly detect additional repairs.

Comparing the best configurations of Parker across the different datasets, we
observe that Parker performs better on EudraCT and Flight than on the Allergen
dataset. The reason for this is the number of different sources describing the
entities in each dataset. The Allergen dataset only includes two sources and,
as explained earlier, Parker cannot detect repairs where the input sources
agree on incorrect values. In contrast, the EudraCT and Flight datasets
include several sources141414Up to 44 sources in EudraCT and up to 51 in
Flight.. For these cases, the chances that all the sources carry the same
errors are very small; this is leveraged by Parker to identify the repairs.
Also, the configurations Parker F/C/F* and F/C/R* that ignore the edit rules
do not outperform the other Parker configurations. This shows the advantage of
exploiting the edit rules when computing dataset repairs. The impact of edit
rules is further analyzed in Section 7.3.

In comparison to the other approaches, Parker exhibits high precision values,
and competitive $F_{1}$ scores. The main reason for the lower recall values
can be attributed to the cases where entities are described by a few sources
with the same errors. In these cases, HoloClean and Raha+Baran can effectively
learn repairs by taking into account the data distributions across the entire
dataset, while Parker focuses on computing repairs at the entity level. Table
2 also reports major differences between the performance of the state-of-the-
art approaches. The results indicate that the learning techniques of HoloClean
are able to learn repairs from larger datasets, as observed in the high
precision values of HoloClean in the EudraCT and Flight datasets. Yet,
HoloClean is not able to cover all possible errors in the data, which is
reflected in the relatively low recall values in all datasets. In contrast,
Raha+Baran can effectively learn repairs from smaller datasets but it still
does not outperform Parker in terms of precision. From this, we can conclude
that the learning techniques of Raha+Baran are recall-oriented allowing for
identifying more types of repairs, while the cost model and the repair
strategies of Parker are rather precision-oriented.

###  7.3 Violations of Edit Rules

Table 3: Violations of edit rules. For each edit rule $E_{i}$, number of rows (with non-null values in the involved attributes) in the dataset and after the repairs that violate $E_{i}$. The right part of the table focuses on the subset of the dataset for which exists an entry in the Gold Standard (GS). Parker (All) indicates all configurations. For Raha+Baran, the table reports the average number of violations obtained in the $10$ runs. Edit Rule | Dataset | HoloClean | Parker | Subset | HoloClean | Raha+ | Parker
---|---|---|---|---|---|---|---
|  |  | (All) | in GS |  | Baran | (All)
Allergen $E_{1}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0
Allergen $E_{2}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0
Allergen $E_{3}$ | 10 | 1 | 0 | 3 | 0 | 2.4 | 0
Allergen $E_{4}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0
Allergen $E_{5}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0
Total Violations | 10 | 1 | 0 | 3 | 0 | 2.4 | 0
EudraCT $E_{1}$ | 881 | 895 | 0 | 12 | 12 | 12.6 | 0
EudraCT $E_{2}$ | 164 | 167 | 0 | 0 | 0 | 0 | 0
EudraCT $E_{3}$ | 7034 | 7953 | 0 | 151 | 192 | 180.9 | 0
EudraCT $E_{4}$ | 57 | 65 | 0 | 0 | 0 | 4.5 | 0
EudraCT $E_{5}$ | 890 | 896 | 0 | 47 | 47 | 28.8 | 0
EudraCT $E_{6}$ | 211 | 217 | 0 | 5 | 5 | 0 | 0
EudraCT $E_{7}$ | 165 | 190 | 0 | 5 | 7 | 16.7 | 0
EudraCT $E_{8}$ | 230 | 230 | 0 | 2 | 2 | 2.5 | 0
EudraCT $E_{9}$ | 146 | 146 | 0 | 7 | 7 | 8.9 | 0
Total Violations | 9778 | 10759 | 0 | 229 | 272 | 254.9 | 0
Flight $E_{1}$ | 9327 | 21375 | 0 | 799 | 1861 | – | 0
Flight $E_{2}$ | 10055 | 10640 | 0 | 1273 | 1367 | – | 0
Total Violations | 19382 | 32015 | 0 | 2072 | 3228 | – | 0

To further understand the effectiveness of the approaches, next we look into
the violations to edit results defined for each dataset (cf. Table 1). Table 3
shows the number of rows that violate the edit rules $E_{i}$ before and after
computing repairs with the baseline approaches. This table distinguishes
between the violations in the full dataset (left) and in the subset of the
data for which the correct rows are available in the gold standard (right). In
comparison to the size of the datasets (cf. Table 1), we observe that the
number of rows that violate edit rules is relatively low, i.e., $<1\%$ in
Allergen, $11\%$ in EudraCT, and $22\%$ in Flight. This indicates that the
high precision values achieved by Parker are not exclusively due to leveraging
the edit rules, but also to its cost model and strategy to decide on the
repairs.

The results in Table 3 empirically confirm that Parker produces repairs that
do not violate any of the edit rules in the datasets. Contrary, HoloClean and
Raha+Baran are not able to ensure violation-free repairs and, in several
cases, produce repairs that introduce more violations to edit rules. In the
case of HoloClean, despite that it takes into account edit rules for
correcting the datasets, the computed repairs introduce new violations in the
larger datasets EudraCT and Flight. For the EudraCT dataset, HoloClean
introduces new violations for all rules except for $E_{8}$ and $E_{9}$.
Regarding the violations of $E_{8}$ and $E_{9}$, HoloClean did not produce
repairs for this cells, i.e., the violations that occur in the original
dataset were still present after the repairs. In the Flight dataset, the edit
rules $E_{1}$ and $E_{2}$ cover all the the attributes of the dataset.
Therefore, we expect Parker and HoloClean to be able to detect the erroneous
rows in the dataset that violate these rules. However, HoloClean introduces
more violations, especially for the edit rule $E_{1}$, which involves the
attributes $actual\\_departure$ and $actual\\_arrival$ with the highest number
of errors according to Figure 4(c). This result indicates that HoloClean might
learn incorrect repairs in the cases where the number of errors in some
attributes is high. Raha+Baran only introduces new violations for the EudraCT
dataset for the edit rules $E_{1}$, $E_{4}$, $E_{7}$, $E_{8}$, and $E_{9}$. In
particular, the rules $E_{4}$, $E_{7}$, $E_{8}$, and $E_{9}$ involve the
attributes $active\\_comparator$ and $placebo$ which are not present in the
gold standard as shown in Figure 4(b). As expected, Raha+Baran is not able to
produce repairs that do not violate rules for which the correct version is not
available. In the other edit rules, Raha+Baran reduces the number of
violations, yet, its effectiveness highly depends on the sampled tuples. For
example, we observe that in $4$ out of the $10$ runs, Raha+Baran actually
introduced new violations to edit rule EudraCT $E_{5}$, yet, it reduces the
number of violations on average.

Comparing the results of Tables 2 and 3, we confirm that the approaches that
consider edit rules, i.e., Parker and HoloClean, achieve a higher precision in
the rows where incorrect values are due to violations of edit rules.

###  7.4 Effectiveness of the Approaches per Attribute

Figure 4 shows that the distribution of errors varies considerably among
attributes within the datasets. Moreover, devising correct repairs for some
attributes might be particularly challenging due to (i) the characteristics of
some attributes, (ii) the skewness of error distributions, and (iii) the lack
of edit rules covering the attributes. To provide further insights into these
aspects of the repairs, in this section, we look into the effectiveness of the
approaches in the different attributes. For each dataset, we first report on
Table 4 on the macro scores for precision, recall, and $F_{1}$, where each
metric is computed per attribute and then averaged by the number of
attributes. Afterwards, we look into the precision and recall values for each
attribute in Figure 5.

Table 4: Macro scores of the repairs of the evaluated approaches. – indicates that the approach could not be executed in that dataset. Parker (Best) indicates the best configuration per dataset as of Table 2, i.e., F/P/F for Allergen and F/CE/F for EudraCT and Flight. Best results per dataset are highlighted. | Allergen | EudraCT | Flight
---|---|---|---
Approach | $F_{1M}$ | $P_{M}$ | $R_{M}$ | $F_{1M}$ | $P_{M}$ | $R_{M}$ | $F_{1M}$ | $P_{M}$ | $R_{M}$
HoloClean | 0.01 | 0.05 | 0.01 | 0.58 | 0.91 | 0.42 | 0.61 | 0.73 | 0.52
Raha+Baran | 0.51 | 0.69 | 0.40 | 0.77 | 0.89 | 0.68 | – | – | –
Parker (Best) | 0.42 | 0.65 | 0.31 | 0.79 | 0.92 | 0.69 | 0.85 | 0.85 | 0.85

#### Allergen Dataset

The macro scores in this dataset reveal that Raha+Baran outperforms the other
approaches at the individual attributes. In comparison to the performance
reported in Table 2, now Parker does not exhibit the highest precision. The
reason for this is that Parker is able to identify correct repairs mainly for
one of the attributes with the highest number of errors, i.e., $nuts$. Since
all the edit rules $E_{i}$ cover this attribute (cf. Table 1), Parker
effectively repairs a large portion of the cells for the $nuts$ attribute. For
most of the attributes, however, Parker does not have enough information to
compute correct repairs as (i) there are no edit rules covering those
attributes, and (ii) each entity is described by only two sources with
potentially the same errors. This is similar for HoloClean, although it is not
able to leverage effectively the edit rules for the attribute $nuts$. In the
case of Raha+Baran, the size of the dataset for which it is applied (206 rows)
and the labelling budget $(\theta_{labels}=20)$ allows it to learn correct
repairs for many more attributes that results in the best $P_{M}$ and $R_{M}$
performance. Concretely, Raha+Baran outperforms Parker in $7$ out of $12$
attributes (cf. Figure 5(a)).

(a) Allergen

(b) EudraCT

(c) Flight

Figure 5: Precision and recall per attribute of repairs of the studied
approaches. Attributes are ordered by the frequency of errors as of Figure 4.

#### EudraCT Dataset

In contrast to the overall results, Parker outperforms the state of the art in
all the macro scores in this dataset. Table 4 shows that Raha+Baran performs
slightly worse than Parker, indicating that the learning techniques of
Raha+Baran in combination with the labelling budget are not sufficient to
capture all possible repairs in this dataset. In terms of $P_{M}$, most of the
approaches achieve a relatively high precision in all attributes. Parker is
only outperformed in the $crossover$ and $controlled$ attributes. Still,
Parker is competitive with the other approaches in $crossover$, as this
attribute presents errors that can be captured with edit rules ($E_{5}$ covers
$17\%$ of the cases) or by cost model and repair strategies due to the high
number of null values ($59\%$). The types of errors in the $controlled$
attribute are more challenging to detect and correct with Parker due to the
low coverage with the edit rules and the lack of $null$ values. In these
cases, using information about the data distributions as implemented by
HoloClean allows for capturing more errors. In terms of $R_{M}$, Parker
outperforms the state of the art in the majority of the attributes, expect for
$single\\_blind$, $controlled$, and $parallel\\_group$. The attribute
$single\\_blind$ is covered by the edit rules $E_{2}$, $E_{3}$, and $E_{4}$
which are violated by $92\%$ of the rows. An inspection into the results for
$single\\_blind$ reveals that Parker correctly repaired all the rows that
violate the edit rules, but it fails in correcting cells with other error
types. For the attributes $controlled$ and $parallel\\_group$, the edit rules
$E_{4}$, $E_{7}$, and $E_{5}$ only cover $3\%$ and $5\%$ of the rows,
respectively. This explains the low recall of Parker in these attributes.
Interestingly, the recall of Parker is very different for $arms$ and
$parallel\\_group$, which are the attributes with the highest number of errors
(cf. Figure 4(b)) and only a few rows ($<3\%$) violate the edit rules covering
these attributes. There is however a big difference in the amount of $null$
values: $91\%$ of the cells are $null$ for $arms$ vs. $16\%$ for
$parallel\\_group$. At the same time, rules $E_{8}$ and $E_{9}$ allow for
deductively repairing those studies that include either a placebo or an active
comparator. This shows how the presence of edit rules can lead to quite
deterministic repairing in some cases.

#### Flight Dataset

Similar to the overall effectiveness of the approaches, Parker outperforms
HoloClean in all the metrics (cf. Table 4). Figure 5(c) shows that the
attributes $actual\\_departure$ and $actual\\_arrival$ are more challenging to
repair for both approaches. The reason for this is two-fold: the edit rule
$E_{1}$ that considers these attributes covers less rows than the other rule,
and the number of $null$ values in these attributes is $40\%$ less than in the
other attributes. In addition, the distribution of the errors shown in Figure
4(c) suggests that it is challenging for HoloClean to learn correct repairs
when a large portion of the rows contain errors; this is the case for
$actual\\_departure$ where $64\%$ of the cells are incorrect and
$actual\\_arrival$ where $51\%$ of the cells are incorrect. All these aspects
make Parker, in general, more effective in both $P_{M}$ and $R_{M}$ in
comparison to HoloClean.

###  7.5 Efficiency of the Approaches

Table 5: Runtime of the approaches (in seconds). For the learning-based approaches, the runtimes for error detection and repair computation are reported. For Parker, average runtimes of the configurations that implement a frequency-based (F) or a random-based (R) repair strategy. * indicates that edit rules are ignored. Approach | Allergen | EudraCT | Flight
---|---|---|---
HoloClean Error Detection | 0.87 | 22.47 | 462.03
HoloClean Repairs | 115.61 | 6099.57 | 6841.80
HoloClean Total | 116.48 | 6122.04 | 7303.83
Raha Error Detection | 8.31 | 33.80 | –
Baran Repairs | 326.95 | 5493.22 | –
Raha+Baran Total | 335.25 | 5527.02 | –
Parker $\cdot$/$\cdot$/F | 0.005 | 8.95 | n/a
Parker $\cdot$/$\cdot$/R | 0.005 | 6.00 | 2.02
Parker $\cdot$/$\cdot$/F* | 0.003 | 31.31 | n/a
Parker $\cdot$/$\cdot$/R* | 0.003 | 1.93 | 1.87

Lastly, we report the efficiency of the studied approaches in Table 5 in terms
of runtime. Comparing all the approaches, Parker outperforms HoloClean and
Raha+Baran by several orders of magnitude in all datasets. This confirms that
Parker produces high-quality repairs which are competitive or more accurate
than the state-of-the-art while requiring less computation time. In the
following, we analyze the aspects that impact on the runtime of the studied
approaches.

For the learning-based approaches, i.e. HoloClean and Raha+Baran, we
distinguish between the time spent during the error detection phase and the
repair computation. For HoloClean and Parker, we exclude from this analysis
the time required for loading the datasets into the database. Note that the
results reported for Raha+Baran cannot be directly compared to the other
approaches: HoloClean and Parker were executed over the entire datasets, while
Raha+Baran was executed only on the subset of the datasets for which the rows
exist in the gold standard.

In the case of HoloClean, the error detection phase is directly impacted by
the size of the datasets, but this effect is not observed for the computation
of the repairs. For the latter stage, the performance is affected by the
number of attributes and edit rules as HoloClean computes the distribution and
correlations between attributes to learn the repairs.

The performance of Raha+Baran follows a similar behavior to HoloClean. The
error detection phase implemented by Raha is orders of magnitude faster than
the repair of the cells with Baran. In particular, Raha+Baran is notably
slower than HoloClean, as it is running only on a small percentage of the
datasets ($3.6\%-17.8\%$). The reason for this is the application of a large
number of learning strategies and the computation of features to obtain the
repairs. This affects the scalability of Raha+Baran to large datasets.

Similar to HoloClean, the runtime of Parker is affected by the number of
attributes and edit rules in the dataset. This is observed when comparing the
runtimes for the configurations $\cdot$/$\cdot$/R for the datasets EudraCT and
Flight: here, Parker takes 3 times longer for EudraCT with a large number of
attributes and edit rules than for the Flight dataset with a large number of
rows. In the case of Parker, Table 5 shows, as expected, that the frequency-
based repair strategy is slower than the random strategy. Moreover, when the
edit rules are not considered, the frequency-based strategy (configurations
$\cdot$/$\cdot$/F*) requires more time than the random strategy
($\cdot$/$\cdot$/R*). This indicates that the edit rules allow for pruning the
space of repairs, which improves both the accuracy of the approach and the
efficiency. Overall, the runtimes of Parker indicate that it can scale up to
even larger datasets.

##  8 Conclusion and Future Work

In this work, we presented a novel type of constraints called edit rules under
a partial key (EPKs) to repair inconsistencies in data fusion. Based on EPKs,
we then proposed an approach to compute minimal cost repairs which allow to
efficiently and effectively explore the space of repairs. We demonstrated the
theoretical properties regarding minimality of our approach. Our proposed
techniques were implemented in our Parker engine. Our experimental study over
three real-world datasets show that, on average, Parker computes more accurate
repairs than the state-of-the-art approaches. In particular, Parker
outperforms the state of the art in the cases where every entity is described
by several sources and the correct repairs can be devised using the edit
rules. In terms of efficiency, Parker showed to be orders of magnitude faster
than the learning-based approaches. Our results indicate that Parker is able
to scale up to very large datasets.

Future work may focus on extending the computation of repairs by taking into
consideration data distributions of the attributes. This will allow Parker to
capture other repairs that are not covered by EPKs; yet, this would require
further investigations on the tradeoff between accuracy and scalability of the
computation of the repairs. Another line of work can investigate the
application of our techniques to semantic data fusion, where additional
ontological knowledge can be exploited to enhance the consistency constraints.

##  9 Appendix A: Proofs

######  Proof 1 (Proposition 1)

If $\mathcal{E}$ is satisfiable, there exists a tuple $r^{*}$ that fails no
rules. A relation $R$ for which
$R[\mathcal{R}_{1}\cup\mathcal{R}_{2}]=r^{*}[\mathcal{R}_{1}\cup\mathcal{R}_{2}]$
is a non-empty relation that fails no EPKs.∎

######  Proof 2 (Proposition 2)

If a solution would not contain a $\subset$-minimal cover it would not cover
failing rules and can thus never lead to a repair. ∎

######  Proof 3 (Theorem 1)

$None$ By contradiction. On one hand, by construction and because any
$\Delta_{a}$ is positive definite, it follows that
$\Delta(r,r^{\prime})=\Delta(r[\mathcal{C}],r^{*}[\mathcal{C}])$. On the other
hand, we have that
$\Delta(r,r^{*})=\Delta(r[\mathcal{C}],r^{*}[\mathcal{C}])+\Delta(r[\mathcal{S}\setminus\mathcal{C}],r^{*}[\mathcal{S}\setminus\mathcal{C}])$.
Because $r^{*}$ is a repair with solution $\mathcal{S}$, the second term of
the sum is greater than zero and it follows that
$\Delta(r,r^{\prime})<\Delta(r,r^{*})$. So, if $r^{\prime}$ is repair, then
$r^{*}$ is not $\Delta$-minimal.

$None$ If there exists a $\mathcal{C}$-minimal repair, say $r^{**}$ with a
cost smaller than or equal to $\Delta\left(r,r^{\prime}\right)$ then we have
$\Delta\left(r,r^{**}\right)\leq\Delta\left(r,r^{\prime}\right)<\Delta\left(r,r^{*}\right)$
from which it follows that $r^{*}$ is not $\Delta$-minimal.∎

######  Proof 4 (Proposition 3)

Suppose the proposition would not hold, then there exists an
$a_{i}\in\mathcal{S}$ for which either $r[a_{i}]=r^{*}[a_{i}]$ or $\forall
E\in\underline{\Omega}\left(\mathcal{E}\right):r^{*}[a_{i}]\in E_{i}$. In the
first case, then the solution is not $\mathcal{S}$ but
$\mathcal{S}\setminus\\{a_{i}\\}$. In the second case, consider the tuple
$r^{\prime}$ that satisfies
$r^{\prime}[\mathcal{R}\setminus\\{a_{i}\\}]=r^{*}[\mathcal{R}\setminus\\{a_{i}\\}]$
and $r^{\prime}[a_{i}]=r[a_{i}]$. We now have $r^{\prime}\models\mathcal{E}$
and because cost functions are positive definite, we also have
$\Delta(r,r^{\prime})<\Delta(r,r^{*})$ which means $r^{*}$ is not a
$\Delta$-minimal repair. ∎

######  Proof 5 (Proposition 4)

For any $r\in R$, $r$ is modified into $r^{*}$ with cost $\Delta(r,r^{*})$.
Because $\mathcal{E}^{\prime}$ and $\mathcal{E}^{\prime\prime}$ are
independent sets, we have
$\mathcal{R}^{\prime}\cup\mathcal{R}^{\prime\prime}=\emptyset$, so we have:

$\Delta(r,r^{*})=\Delta(r[\mathcal{K}\cup\mathcal{R}^{\prime}],r^{*}[\mathcal{K}\cup\mathcal{R}^{\prime}])+\Delta(r[\mathcal{K}\cup\mathcal{R}^{\prime\prime}],r^{*}[\mathcal{K}\cup\mathcal{R}^{\prime\prime}]).$
(12)

Moreover, if $r^{\prime}$ is a tuple with schema
$\mathcal{K}\cup\mathcal{R}^{\prime}$ and $t$ is a tuple with schema
$\mathcal{R}$ then we have $r^{\prime}\models\mathcal{E}^{\prime}\wedge
t[\mathcal{R}^{\prime}]=r^{\prime}\Rightarrow t\models\mathcal{E}^{\prime}$. A
similar property holds for tuples $r^{\prime\prime}$ with schema
$\mathcal{K}\cup\mathcal{R}^{\prime\prime}$. It then follows that if
$r^{\prime}$ is a tuple with schema $\mathcal{K}\cup\mathcal{R}^{\prime}$ and
$r^{\prime\prime}$ is a tuple with schema
$\mathcal{K}\cup\mathcal{R}^{\prime\prime}$ we have:

$r^{\prime}\models\mathcal{E}^{\prime}\wedge
r^{\prime}\models\mathcal{E}^{\prime\prime}\Rightarrow r^{\prime}\bowtie
r^{\prime\prime}\models\mathcal{E}^{\prime}\cup\mathcal{E}^{\prime\prime}=\mathcal{E}.$
(13)

Any tuple $r^{\prime}$ (with schema $\mathcal{K}\cup\mathcal{R}^{\prime}$)
that satisfies $\mathcal{E}^{\prime}$ can thus be naturally joined with any
tuple $r^{\prime\prime}$ (with schema
$\mathcal{K}\cup\mathcal{R}^{\prime\prime}$) that satisfies
$\mathcal{E}^{\prime\prime}$ and the result will satisfy $\mathcal{E}$. If in
addition $r^{\prime}$ minimizes
$\Delta(r[\mathcal{K}\cup\mathcal{R}^{\prime}],r^{*}[\mathcal{K}\cup\mathcal{R}^{\prime}])$
and $r^{\prime\prime}$ minimizes
$\Delta(r[\mathcal{K}\cup\mathcal{R}^{\prime\prime}],r^{*}[\mathcal{K}\cup\mathcal{R}^{\prime\prime}])$,
then $r^{\prime}\bowtie r^{\prime\prime}$ minimizes $\Delta(r,r^{*})$. ∎

######  Proof 6 (Theorem 2)

$None$ If some tuple $r^{\prime}\in M_{\mathbf{k}}$ is consistent, then that
tuple is a $\Delta$-minimal repair for $R_{\mathcal{K}=\mathbf{k}}\subseteq R$
and also a trivial $\Delta^{\bullet}$-minimal repair for itself.

$None$ If $\forall r^{\prime}\in
M_{\mathbf{k}}:r^{\prime}\not\models\mathcal{E}$ then $r^{*}\notin
M_{\mathbf{k}}$. Now, for any $r^{\prime\prime}\notin M_{\mathbf{k}}$ there
always exists some tuple $t$ such that
$\beta(\mathbf{k},t)<\beta(\mathbf{k},r^{\prime\prime})$ and in addition,
$r^{\prime\prime}$ and $t$ only differ for one attribute $a$. We then have
$\beta(\mathbf{k},r^{\prime\prime})=\beta(\mathbf{k},t)+c(r^{\prime\prime}[a])-c(t[a])$.
Now if $t\in M_{\mathbf{k}}$, then we can write
$\beta(\mathbf{k},r^{\prime\prime})=\beta(\mathbf{k},t)+\Delta^{\bullet}(t,r^{\prime\prime})$.
If $t\notin M_{\mathbf{k}}$, then $t$ itself can be written in terms of some
$t^{\prime}$ where $t$ and $t^{\prime}$ differ in only one attribute $b$ such
that
$\beta(\mathbf{k},r^{\prime\prime})=\beta(\mathbf{k},t^{\prime})+c(t[b])-c(t^{\prime}[b])+c(r^{\prime\prime}[a])-c(t[a])$.
Clearly, in each step $\beta(\mathbf{k},.)$ is strictly decreasing and lower
bounded, so eventually, for every $r^{\prime\prime}\notin M_{\mathbf{k}}$, we
must find some $r^{\prime}\in M_{\mathbf{k}}$ such that
$\beta(\mathbf{k},r^{\prime\prime})=\beta(\mathbf{k},r^{\prime})+\Delta^{\bullet}(r^{\prime},r^{\prime\prime})$.
It is now straightforward to see that any $r^{*}\notin M_{\mathbf{k}}$ can be
written in the same way and minimizing $\beta(\mathbf{k},r^{*})$ is equivalent
to minimizing $\Delta^{\bullet}(r^{\prime},r^{*})$ for any $r^{\prime}\in
M_{\mathbf{k}}$.∎

## References

  * Bohannon et al. [2007] P. Bohannon, W. Fan, F. Geerts, X. Jia, A. Kementsietsidis,  Conditional functional dependencies for data cleaning,  in: Proceedings of the IEEE International Conference on Data Engineering, 2007, pp. 746–755.
  * Fan et al. [2008] W. Fan, F. Geerts, X. Jia, A. Kementsietsidis,  Conditional functional dependencies for capturing data inconsistencies,  ACM Transactions on Database Systems 33 (2008) 1–48.
  * Chu et al. [2013] X. Chu, I. Ilyas, P. Papotti,  Discovering denial constraints,  in: Proceedings of the VLDB Endowment, 2013, pp. 1498–1509.
  * Geerts et al. [2013] F. Geerts, G. Mecca, P. Papotti, D. Santoro,  The LLUNATIC data-cleaning framework,  Proc. VLDB Endow. 6 (2013) 625–636.
  * Geerts et al. [2019] F. Geerts, G. Mecca, P. Papotti, D. Santoro,  Cleaning data with Llunatic,  The VLDB Journal (2019). doi:10.1007/s00778-019-00586-5.
  * Rekatsinas et al. [2017] T. Rekatsinas, X. Chu, I. Ilyas, C. Ré,  Holoclean: Holistic data repairs with probabilistic inference,  in: Proceedings of the VLDB Endowment, 2017, pp. 1190–1201.
  * Mahdavi and Abedjan [2020] M. Mahdavi, Z. Abedjan,  Baran: Effective error correction via a unified context representation and transfer learning,  Proc. VLDB Endowment 13 (2020) 1948–1961.
  * Fellegi and Holt [1976] I. Fellegi, D. Holt,  A systematic approach to automatic edit and imputation,  Journal of the American Statistical Association 71 (1976) 17–35.
  * Boskovitz [2008] A. Boskovitz, Data Editing and Logic: The covering set method from the perspective of logic, Ph.D. thesis, The Australian National University, 2008.
  * De Waal et al. [2001] T. De Waal, J. Pannekoek, S. Scholtus, Handbook of statistical Data Editing and Imputation, Wiley, 2001.
  * Abiteboul et al. [1995] S. Abiteboul, R. Hull, V. Vianu (Eds.), Foundations of Databases: The Logical Level, 1st ed., Addison-Wesley Longman Publishing Co., Inc., 1995\.
  * Barcaroli and Venturi [1997] G. Barcaroli, M. Venturi,  An integrated system for edit and imputation of data: An application to the italian labour forces survey.,  in: Contributed papers of the 49th session of the international statistical institute., 1997, pp. 81–82.
  * Dong et al. [2009] X. L. Dong, L. Berti-Equille, D. Srivastava,  Integrating conflicting data: the role of source dependence,  in: Proceedings of the VLDB conference, 2009, pp. 550–561.
  * Dong et al. [2012] X. L. Dong, B. Saha, D. Srivastava,  Less is more: Selecting sources wisely for integration,  in: Proceedings of the VLDB conference, 2012, pp. 37–48.
  * Galindo-Legaria [1994] C. Galindo-Legaria,  Outerjoins as disjunctions,  in: Proceedings of SIGMOD, 1994, pp. 348–358.
  * Galindo-Legaria and Rosenthal [1997] C. Galindo-Legaria, A. Rosenthal,  Outerjoin simplification and reordering for query optimization,  Transactions on Database Systems 22 (1997) 43–74.
  * Yan and Özsu [1999] L. L. Yan, T. Özsu,  Conflict tolerant queries in aurora,  in: Proceedings of the Fourth IECIS International Conference on Cooperative Information Systems, 1999, pp. 279–290.
  * Greco et al. [2001] S. Greco, L. Pontieri, E. Zumpano,  Integrating and managing conflicting data,  in: The 4th International Andrei Ershov Memorial Conference on Perspectives of System Informatics, 2001, pp. 187–192.
  * Bleiholder and Naumann [2005] J. Bleiholder, F. Naumann,  Declarative data fusion: Syntax, semantics, and implementation,  in: Proceedings of the East European Conference on Advances in Databases and Information Systems (ADBIS), 2005, pp. 58–73.
  * Bleiholder et al. [2010] J. Bleiholder, S. Szott, M. Herschel, F. Kaufer, F. Naumann,  Subsumption and complementation as data fusion operators,  in: EDBT, 2010, pp. 513–524.
  * Bleiholder et al. [2011] J. Bleiholder, M. Herschel, F. Naumann,  Eliminating nulls with subsumption and complementation,  IEEE Data Engineering Bulletin 34 (2011) 18–25.
  * Lu et al. [1997] H. Lu, W. Fan, C. Hian Goh, S. Madnick, D. Cheung,  Discovering and reconciling semantic conflicts: a data mining prospective,  in: IFIP Working Conference on Data Semantics (DS-7), 1997.
  * Fan et al. [2001] W. Fan, H. Lu, S. Madnick, D. Cheung,  Discovering and reconciling value conflicts for numerical data integration,  Information Systems 26 (2001) 635–656.
  * Bronselaer et al. [2016] A. Bronselaer, M. Szymczak, S. Zadrozny, G. De Tré,  Dynamical order construction in data fusion,  Information Fusion 27 (2016) 1–18.
  * Bronselaer et al. [2012] A. Bronselaer, D. Van Britsom, G. De Tré,  A framework for multiset merging,  Fuzzy Sets and Systems 191 (2012) 1–20.
  * Bronselaer et al. [2015] A. Bronselaer, D. Van Britsom, G. De Tré,  Propagation of data fusion,  IEEE Transactions on Knowledge and Data Engineering 27 (2015) 1330–1342.
  * Bleiholder and Naumann [2008] J. Bleiholder, F. Naumann,  Data fusion,  ACM Computing Surveys 41 (2008).
  * Li et al. [2013] X. Li, X. L. Dong, K. Lyons, W. Meng, D. Srivastava,  Truth finding on the deep web: Is the problem solved?,  in: Proceedings of the VLDB conference, 2013, pp. 97–108.
  * Mahdavi et al. [2019] M. Mahdavi, Z. Abedjan, R. Castro Fernandez, S. Madden, M. Ouzzani, M. Stonebraker, N. Tang,  Raha: A configuration-free error detection system,  in: Proceedings of the 2019 International Conference on Management of Data, SIGMOD ’19, Association for Computing Machinery, 2019, p. 865–882.