Database Reference
In-Depth Information
2.5 Repairs
The concept of repair is fundamental to define a strategy for extracting reliable infor-
mation from inconsistent databases. In this section, we introduce repairs consisting
of sets of updates at attribute-level that will be used for fixing inconsistent numerical
databases.
=
(
Definition 2.3 (Atomic update). Let
t
R
v
1
,...,
v
n
)
be a tuple over the relation
v
i
>
(
Δ
,...,
Δ
)
<
,
,
scheme
R
A
1
:
A
n
:
.An
atomic update
on
t
is a triplet
t
A
i
, where
1
n
R
and
v
i
is a value in
i
and
v
i
=
A
i
∈M
Δ
v
i
.
v
i
>
with
v
i
, thus yielding the tuple
u
Update
u
=
<
t
,
A
i
,
replaces
t
[
A
i
]
(
t
)=
v
i
,
(
R
v
1
,...,
v
i
−
1
,
v
i
+
1
,...,
v
n
)
. We denote the pair
<
tuple
,
attribute
>
updated by
λ
(
)
λ
(
)=
<
,
u
as
u
, that is
u
t
A
i
>
. Observe that we consider atomic updates work-
M
ing on the set
R
of measure attributes only, since, as explained in Section 2.1,
non-measure attributes are
a priori
assumed to be correct.
Definition 2.4 (Consistent database update). Let
D
be a database instance and
U
be a set of atomic updates on tuples of
D
. The set
U
is said to be a
consistent database update
iff
=
{
u
1
,...,
u
n
}
∀
,
∈
[
..
]
=
λ
(
)
=
λ
(
u
k
)
j
k
1
n
if
j
k
then
u
j
.
Informally, a set of atomic updates
U
is a consistent database update iff, for each
pair of updates
u
1
,
U
, either
u
1
and
u
2
work on distinct tuples, or they change
different attributes of the same tuple.
The set of pairs
u
2
∈
<
tuple
,
attribute
>
updated by a consistent database update
U
{λ
(
)
}
will be denoted as
.
Given a database instance
D
, a tuple
t
in
D
, and a consistent database update
U
, we denote the tuple obtained by applying the atomic updates in
U
of the form
<
λ
(
U
)=
∪
u
i
u
i
∈
U
. Moreover, we denote the database instance resulting from
applying all the atomic updates in
U
on the tuples of
D
as
U
t
,
A
,
v
>
on
t
as
U
(
t
)
.
We now introduce the notion of repair for a database w.r.t. a set of constraints.
(
D
)
Definition 2.5 (Repair). Let
D
be a database scheme,
AC
a set of aggregate con-
straints on
D
, and
D
an instance of
D
.A
repair
ρ
for
D
w.r.t.
D
and
AC
is a
consistent database update such that
ρ
(
D
)
|
=
D
and
ρ
(
D
)
|
=
AC
.
Example 2.9.
The database instance in the “Balance Sheet” example can be made
consistent w.r.t. the set of integrity constraints defined in Examples 2.2 and 2.3 by
increasing the values of attribute
Value
of both
t
2
and
t
18
up to 1150 and 1190,
respectively. That is,
ρ
=
{
t
2
,
Value
,
1150
,
t
18
,
Value
,
1190
}
is a repair.
1
2.6 Card- and Set-minimal Repairs
We will show in Chapter 3 that the problem of deciding whether there is repair for
a database violating a given set of aggregate constraints is decidable. In particular,
Search WWH ::
Custom Search