Database Reference
In-Depth Information
set
set
ρ
D,AC
(
D
)
for our running example contains
ρ
1
,
ρ
3
,
ρ
5
and further
set
-minimal
repairs, such as
ρ
3
\{
t
2
,
Value
,
1150
}∪{
t
3
,
Value
,
350
}
.
2.7 Consistent Answers
We address the problem of extracting reliable information from data violating a
given set of aggregate constraints. Specifically, we consider boolean queries check-
ing whether a given tuple belongs to a database, and adopt the widely-used notion
of consistent query answer introduced in [4]. More complex forms of queries will
be considered in Chapter 5, and further extensions to different forms of queries will
be discussed in Chapter 6.
Definition 2.7 (Query). A
query
over a database scheme
D
is a ground atom of the
form
R
(
v
1
,...,
v
n
)
, where
R
(
A
1
,...,
A
n
)
is a relation scheme in
D
.
Given a query
q
issued on a database
D
, we write
q
∈
D
(resp.,
q
∈
D
)if
q
evaluates to
true
(resp.,
false
)on
D
.
Definition 2.8 (Consistent query answer). Let
D
be a database scheme,
D
an in-
D
AC
D
D
stance of
,
a set of aggregate constraints on
and
q
a query over
. The
S
consistent query answer
of
q
on
D
under the
-minimal semantics (denoted as
q
D,AC
(
ρ ∈ ρ
D,AC
(
)
S ∈{
}
)
D
, with
set, card
) is true iff for each
D
it holds that
∈ ρ
(
)
q
.
Observe that, according to the above-reported definition, in the case that a
database
D
does not admit any repair, the consistent answer of any query on
D
is true (under both the
set
- and
card
- minimal semantics).
Example 2.13.
Consider the query
q
=
BalanceSheet(2009, Disbursements, total dis-
bursements, aggr, 1190)
. It is easy to see that the consistent answer of
q
under the
card
-minimal semantics is
true
, as this ground tuple belongs to every database re-
paired by a
card
-minimal repair in
D
card
. However, the consistent
answer of
q
under the
set
-minimal semantics is
false
, since
q
ρ
D,AC
(
D
)=
{ρ
, ρ
5
}
1
∈ ρ
1
(
D
)
but
q
∈ ρ
3
(
D
)
,
where
ρ
1
and
ρ
3
are the
set
-minimal repairs introduced in Examples 2.9 and 2.11,
respectively.
2.8 Complexity Classes
In the following chapters, we study the computational complexity of several prob-
lems related to evaluation of repairs and consistent answers. Our complexity re-
sults refer to the
data complexity
assumption [1], which measures the complexity
of a problem as a function of the size of the database instance, while the database
scheme, the query and integrity constraints are assumed to be fixed.
We will consider the following complexity classes [39, 45]:
Search WWH ::
Custom Search