Database Reference
In-Depth Information
Definition 3.2 (
MINIMAL REPAIR CHECKING
(
MRC
)).
Let
D
be a fixed database
AC
D
scheme and
a fixed set of aggregate constraints on
. Given an instance D of
D
ρ
D
AC
, and a repair
for D w.r.t.
and
,
MRC
S
(with
S ∈{
card
,
set
}
) is the
(
, ρ)
problem of deciding whether
D
belongs to the set
D
, ρ
) |
D
is an instance of
ρ
is an
-minimal repair for D
{(
D
and
S
w.r.t.
D
and
AC}
The following theorem characterizes the complexity of the
MRC
problem.
MRC
S
Δ ∈{Z,Q}
S ∈{
,
}
Theorem 3.2.
with
and
card
set
in coNP-complete.
Hence the computational complexity of the problem of deciding whether a given
repair is minimal does not depend neither on the domain of measure attributes, nor
on the semantics adopted. Interesting enough, we will see in Section 2.4 that the
MRC
set
problem becomes tractable in the presence of steady aggregate constraints.
3.3 Consistent Query Answer Problem (
CQA
)
We now define consistent query answer problem and characterize its complexity.
We recall that q
D,AC
(
D
)
denotes the consistent answer of the query q posed on the
database D, instance of
D
, in the presence of the set of aggregate constraints
AC
(see Definition 2.8)
Definition 3.3 (
CONSISTENT QUERY ANSWER PROBLEM
(
CQA
)).
Let
D
be a
fixed database scheme,
AC
a fixed set of aggregate constraints on
D
, and q afixed
query over
D
.
CQA
S
, with
S ∈{
set, card
}
, is the problem of deciding whether a
given instance of
D
belongs to the set
and q
D,AC
(
{
D
|
D is an instance of
D
D
)
is true
}.
Before providing the complexity characterization of the
CQA
problem, we in-
troduce a new lemma extending the result of Lemma 3.1. Basically, the following
lemma states that, if a database D admits a repair
ρ
such that a given query q is true
ρ
for D such that q is
ρ(
)
(resp., false) on
D
, then there is a polynomial-size repair
ρ
(
true (resp., false) on
D
)
.
Lemma 3.2.
Let
D
be a database scheme,
AC
a set of aggregate constraints on
D
,
D an instance of
D
and q
=
R
(
a
1
,...,
a
n
)
a query over
D
. If there is a repair
ρ
for
ρ
D w.r.t.
D
and
AC
such that q
∈ ρ(
D
)
(resp. q
∈ ρ(
D
)
), then there is a repair
for D w.r.t.
D
and
AC
such that:
λ(ρ
) ⊆ λ(ρ)
(i)
,
∈ ρ
(
∈ ρ
(
(ii) q
D
)
(resp. q
D
)
), and
ρ
has polynomial size w.r.t. D and q.
(iii)
Search WWH ::
Custom Search