Database Reference
In-Depth Information
The output of the query is the set of those valuations of free variables that make the
query hold true
Q
(
T
)=
a
T
(
a
,
y
)
.
|
∃
=
y
π
This class of queries is denoted by CTQ (conjunctive tree queries).
Note that conjunctive queries from CTQ are indeed closed under conjunctions. This is
because patterns are closed under conjunction, as we have seen in
Section 11.1
.
We also consider unions of such queries: UCTQ denotes the class of queries of the form
∪···∪
Q
m
(
x
)
,
Q
1
(
x
)
where each
Q
i
is a query from CTQ. Like for schema mappings, we write CTQ(
σ
) and
+
,
+
,
=
,
σ
⊆{↓
,
↓
→
,
→
=
,
}
UCTQ(
σ
) for
to denote the subclass of queries using only the
+
,
),
+
,
),
symbols from
σ
. Recall that we are using abbreviations
⇓
for (
↓
,
↓
⇒
for (
→
,
→
and
∼
for (=
,
=).
Example 13.1 Recall the mapping defined in
Example 11.12
on page
154
. Suppose we
want to find out which rulers succeeded more than one other ruler. This can be expressed
over the target schema by the following conjunctive query with inequalities
MultiSucc
:
∃
x
∃
y
rulers
[
ruler
(
x
)
/
successor
(
z
)
,
ruler
(
y
)
/
successor
(
z
)]
∧
x
=
y
.
Just like in the relational case, the query might return different answers on different solu-
tions to a given source tree. For instance, for the source tree
T
1
shown in
Figure 10.1
,two
possible solutions are
T
2
and
T
3
shown in
Figure 11.4
.On
T
2
the query
MultiSucc
returns
{
James VI & I
}
, and on
T
3
the answer is
{
James VI & I
,
Charles I
}
.
What is the right answer to a query then? Since the queries return tuples of values, we can
simply adapt the
certain answers semantics
from the relational case. For a mapping
,
a query
Q
, and a source tree
S
conforming to
D
s
, we return the tuples which would be
returned for every possible solution:
certain
M
(
Q
,
S
)=
Q
(
T
)
M
.
T
is a solution for
S
under
M
The subscript
is omitted when it is clear from the context.
This is precisely why for now we restrict to queries that return tuples of data values: for
them, it is clear how to define certain answers. For queries that can return XML documents,
the definition is not so clear; we revisit the problem in the next chapter.
In our running example,
M
certain
M
(
MultiSucc
,
T
1
)=
{
James VI & I
}
.
Note that when
Q
is a Boolean query,
certain
M
(
Q
,
S
) is
true
if and only if
Q
is true for
all the solutions.
To understand the computational resources needed to find certain answers, we focus on
the following decision problem, for fixed
M
and
Q
:
