Database Reference
In-Depth Information
1
which has polynomial size
and such that it updates a subset of the pairs
tuple,
ρ
attribute
updated by
.
D
AC
D
Lemma 3.1. Let
be a database scheme,
a set of aggregate constraints on
,
and D an instance of
D
such that D is not consistent w.r.t.
D
and
AC
. If there is a
ρ for D w.r.t.
repair
ρ
for D w.r.t.
D
and
AC
, then there is a repair
D
and
AC
such that
• λ ( ρ ) ⊆ λ ( ρ )
, and
• ρ has polynomial size w.r.t. D.
Intuitively, the result of the lemma follows from the fact that we can define a
system of linear inequality In
( ρ ,
D
, D , AC )
such that given a repair
ρ
for D w.r.t.
D
and
AC
,
ρ
corresponds to a solution x
( ρ )
of In
( ρ ,
D
, D , AC )
. Basically, each
variable of In
( ρ ,
D
, D , AC )
corresponds to a pair
tuple, attribute
changed by
ρ
,
and the inequalities appropriately encode all the constraints of
AC
violated by D
and the domain constraints. It is worth noting that In
( ρ ,
D
, D , AC )
must be defined
so that any other solution x of In
ρ .
This is not trivial since it must be the case that assigning the values of x to the cor-
responding pairs
( ρ ,
D
, D , AC )
still corresponds to a repair
tuple, attribute
of D the following hold: (i) D is consistent w.r.t.
the set of aggregate constraints
AC
originally violated by D , and (ii) no violations
of constraints in
AC
possibly not encoded in In
( ρ ,
D
, D , AC )
are triggered. As the
size of In
is polynomial w.r.t. the size of D and since every feasible
system of linear inequalities admits a polynomial bounded solution, the result of the
lemma follow. The detailed proof of Lemma 3.1, as well as those of the theorems
stated in this chapter, can be found in [26].
The result Lemma 3.1 entails that the repair existence problem is in NP , since
when deciding the existence of a repair for an inconsistent we can limit the search
space to polynomial size sets of updates. The following theorem provides a tight
characterization of the complexity of RE .
( ρ ,
D
, D , AC )
Theorem 3.1. RE Δ with
Δ ∈{ Z , Q }
is NP-complete.
We will see in Section 2.4 that the repair existence problem become tractable in
the case that the aggregate constraints are steady and measure attributes range over
the domain of rationals.
3.2 Minimal Repair Checking Problem ( MRC )
We now address the characterization of the problem of deciding whether a given
repair is minimal, under either the card -orthe set - minimal semantics.
The minimal repair checking is defined as follows.
1 The size of an atomic update u = t , A , v is determined by the size of the representation of the
(integer or rational) number v . In turn, the size of a set U of atomic updates is given by sum of the
sizes of the atomic updates in U .
Search WWH ::




Custom Search