Database Reference
In-Depth Information
we show that this problem belongs to the class of the problems that can be decided
in polynomial time w.r.t. the size of the database by a Turing machine with an
NP
oracle.
In general, if a database can be repaired, different repairs can be performed on
D
yielding a new database consistent w.r.t.
, although some of them
may not be considered “reasonable”. For instance, if a repair exists for
D
chang-
ing only one value in one tuple of
D
, any repair updating all values in all tuples
of
D
can be reasonably disregarded. To evaluate whether a repair should be con-
sidered “relevant” or not, we introduce two different ordering criteria on repairs,
corresponding to the comparison operators '
D
and
AC
<
card
'. The former compares
two repairs by evaluating whether one of the two performs a subset of the updates of
the other. That is, given two repairs
<
set
' and '
ρ
a
,
ρ
b
, we say that
ρ
a
precedes
ρ
b
(
ρ
a
<
set
ρ
b
)
iff
λ
(
ρ
a
)
⊂ λ
(
ρ
b
)
. The latter ordering criterion states that a repair
ρ
a
is preferred
w.r.t. a repair
ρ
b
(
ρ
a
<
card
ρ
b
)iff
|λ
(
ρ
a
)
| < |λ
(
ρ
b
)
|
, that is if the number of changes
issued by
ρ
a
is less than
ρ
b
.
Observe that
ρ
a
<
set
ρ
b
implies
ρ
a
<
card
ρ
b
, but the vice versa does not hold, as it
can be the case that repair
ρ
a
changes a set of values
λ
(
ρ
a
)
which is not a subset of
λ
(
ρ
b
)
, but whose cardinality is less than that of
λ
(
ρ
b
)
.
ρ
Example 2.10.
Consider the repair
1
for “Balance Sheet” example introduced in
Example 2.9, and the repair
ρ
=
{
t
2
,
Value
,
1000
,
t
3
,
Value
,
250
,
t
18
,
Value
,
1190
}
.
2
It is easy to see that
ρ
1
<
card
ρ
2
and
ρ
<
set
ρ
2
.
1
Definition 2.6 (Set- and card-minimal repairs). Let
D
be a database scheme,
AC
a set of aggregate constraints on
D
, and
D
an instance of
D
. A repair
ρ
for
D
w.r.t.
D
is a
set
-minimal repair [resp.,
card
-minimal repair] iff there is no repair
ρ
for
D
w.r.t.
and
AC
ρ
<
set
ρ
ρ
<
card
ρ
D
and
AC
such that
[resp.
].
Example 2.11.
The repair
ρ
1
of Example 2.9 is minimal under both the
set
-minimal
and the
card
-minimal semantics.
Consider the repair
ρ
3
=
{
t
2
,
Value
,
1150
,
t
15
,
Value
,
1060
,
t
19
,
Value
,
80
,
t
20
,
Value
ρ
3
is minimal only under the
set
-minimal semantics. It is
not
card
-minimal since, for instance,
,
160
}
. The repair
ρ
1
consists of fewer atomic updates.
Now, consider the repair
ρ
4
=
{
t
2
,
Value
,
1150
,
t
15
,
Value
,
1000
,
t
18
,
Value
,
1060
,
t
19
,
Value
,
140
,
t
20
,
Value
,
260
,}
. The strategy represented by
ρ
4
can be reason-
ably disregarded, since the atomic updates of repair
ρ
3
or those of repair
ρ
1
suffice
to make
BalanceSheets
consistent. In fact,
ρ
4
is not minimal both under the
set
-
minimal semantics (as
ρ
3
<
set
ρ
4
) and under the
card
-minimal one (as
ρ
1
<
card
ρ
4
).
D
D
Given a database scheme
and a database instance
D
of
which is not con-
AC
sistent w.r.t. a set of aggregate constraints
, different
set
-minimal repairs (resp.,
card
-minimal repairs) may exist for
D
. The sets of
set
- and
card
-minimal repairs of
D
w.r.t.
D
and
AC
will be denoted as
ρ
D,AC
(
set
D
)
and
ρ
D,AC
(
card
D
)
, respectively.
card
Example 2.12.
In the “Balance Sheet” example,
ρ
D,AC
(
D
)=
{ρ
1
, ρ
5
}
where
ρ
1
is
the repair defined in Example 2.9 and
ρ
5
=
{
t
3
,
Value
,
350
,
t
18
,
Value
,
1190
}
. The
Search WWH ::
Custom Search