Database Reference
In-Depth Information
Rational-variant of Consistent Query Answer
The following theorem show that the complexity of
CQA
under the
card
-minimal
semantics is not lowered by the introduction of steady aggregate constraints, dif-
ferently from the
set
-minimal semantics, as
STEADY
-
CQA
set
is shown to be
coNP
-
complete.
Theorem 3.7.
STEADY
-
CQA
card
p
2
[
-complete, whereas
STEADY
-
CQA
set
is
is
Δ
logn
]
coNP-complete.
Basically, the membership in coNP of
STEADY
-
CQA
set
derives from the fact that
STEADY
-
MRC
set
is in
P
.
3.5 Summary of the complexity results
A summary of the complexity results obtained so far is shown in
Table 3.1
, where
all the problems are shown to be complete for the classes reported in the cells of the
table.
RE
Δ
M
RC
card
CQA
card
M
RC
set
CQA
set
Constraints
AC
Domain
Δ
p
2
p
2
General
Z
NP
coNP
Δ
[
logn
]
coNP
Π
p
2
p
2
Q
NP
coNP
Δ
[
logn
]
coNP
Π
p
2
p
2
Z
NP
coNP
Δ
[
logn
]
coNP
Π
Steady
p
2
Q
P
coNP
Δ
[
logn
]
P
coNP
Table 3.1 Summary of complexity results
The results in the above-reported table show that the choice of the semantics
(
card
-or
set
- minimality), the class of aggregate constraints (general or steady),
as well as the domain of the numerical data involved in the constraints, introduce
different sources of complexity. Specifically, in the presence of general aggregate
constraints, the complexity of the analyzed problems does not depend on the do-
main of the numerical data, but only on the semantics. This does not hold in the
presence of steady aggregate constraints. In fact, in this case,
RE
is
NP
-complete
if the domain of the numerical data is
Z
, whereas it is
P
-complete if the domain
is
Q
. Analogously, under the
set
-minimal semantics,
MRC
and
CQA
are
coNP
- and
p
2
- complete, respectively, if the numerical data domain is
Π
, and their complexity
becomes
P
- and
coNP
- complete, respectively, if the numerical data domain is
Z
Q
.
Search WWH ::
Custom Search