Database Reference
In-Depth Information
Chapter 3
Repairing and Querying: the Fundamental
Decision Problems
Abstract In this chapter, we introduce some fundamental decision problems related
to repairing and querying inconsistent data. Specifically, we formalize the
repair
existence problem
, the
minimal repair checking problem
, and the
consistent query
answer problem
, and analyze their computational complexity in the presence of
databases inconsistent w.r.t. a given set of aggregate constraints. In this regard, we
provide a thorough characterization, as we investigate the sensitivity of the compu-
tational complexity of these problems to several aspects: the domain of numerical
attributes (integers or rationals), the form of the aggregate constraints considered
(steady or not), and the minimality semantics (
card
-or
set
-minimal).
3.1 Repair Existence Problem (
RE
)
The problem of deciding whether a database inconsistent w.r.t. a set of aggregate
constraints can be repaired is defined as follows:
Definition 3.1 (
REPAIR EXISTENCE
(
RE
)). Let
D
be a fixed database scheme, and
AC
a fixed set of aggregate constraints on
D
.
RE
is the problem of deciding whether
a given instance of
D
belongs to the set
{
D
|
D
is an instance of
D
and there exists a repair for
D
w.r.t.
D
and
AC}
In the following, we denote with
RE
Δ
the version of the
RE
problem where every
measure attribute in
. Hence,
RE
Z
(resp.,
RE
Q
)
is the version of the repair existence problem where all the measure attributes are
constrained to range over the domain
M
D
is associated with the domain
Δ
) . An analogous notation will be
used for the decision problems that will be defined later, i.e., the minimal repair
checking (
MRC
) and consistent query answer (
CQA
) defined in Sections 3.2 and 3.3,
respectively.
As a preliminary result, we have that, if at least one repair
Z
(resp.,
Q
ρ
exists for a database
ρ
for
D
w.r.t.
D
w.r.t. a set of aggregate constraints
AC
, then there is a repair
AC
Search WWH ::
Custom Search