Database Reference
In-Depth Information
What about more general queries, say FO queries? We know that in the case of CWA,
we can always answer them (and the complexity is
CO
NP-complete). In the case of OWA,
finding certain answers is an undecidable problem. Annotated mappings give us some ad-
ditional cases, compared to OWA, when query answering is decidable.
The parameter that we use is the following:
•
#
op
(
) - the maximum number of open positions per atom in an st-tgd in the anno-
tated mapping.
M
,
α
In our example, the value of #
op
(
M
,
α
) is 1, as no st-tgd uses more than one open position.
Theorem 8.35
The data complexity of finding certain answers for
FO
queries under
annotated mappings is as follows:
1. in
CO
NP
if
#
op
(
)=0
(which is the
CWA
case);
2. decidable (in
CO
NEXPTIME
)if
#
op
(
M
,
α
M
,
α
)=1
.
3. undecidable for some mappings
(
M
,
α
)
with
#
op
(
M
,
α
)
>
1
.
Thus, if more than one position in a rule is marked
op
, query answering behaves like
in OWA. With no
op
positions, we have the CWA case. The new intermediate case is one
open annotation per rule, and there we retain decidability of query answering.
