Database Reference
In-Depth Information
Figure 4. Reformulation of a query (m
T(
z
)T(
z
)
, φ(
z
)) into a query (m
S(
x
)T(
x'
,
y
)
, φ'(
x
)) using the mapping
∧
x
(S(
x
)
∧
∧
y
T(
x'
,
y
))
Definition 16.
(
answer to a query
) Let
q
= (
m
ST
, φ) be a query from
S
(
x
) to
T
(
x'
,
y
) and
I
= (
S
, Ω) be an
instance of
S
. The answer to
q
(
I
) is such the instance
J
= (
T
, Ω') that
Ω' = {ω.
restrict
(
x'
)
∧
null
(
y
) | ω
∧
Ω
∧
φ(ω(
x
)) =
true
},
where ω.
restrict
(
x'
) is the restriction of the valuation ω to the variables in
x'
, and
null
(
y
) is a valuation
assigning nulls to all variables in
y
.
Example 8.
The query
q
12
= (
m
S
1(
x
1,
x
2,
x
3,
x
4)
S
2(
x
1,
x
3,
x
4)
,
x
3
= “
John
”
∧
x
2
= “2005”), filters an instance of the
source schema
S
1
according to the qualifier and produces an instance of the schema
S
2
.
A query is issued by the user against an arbitrarily chosen peer schema (the target schema). The user
perceives a target schema
T
(
z
), and defines a qualifier φ(
z
), so initially the query is from
T
to
T
, and is
of the form
q
= (
m
T
(
z
)
T
(
z
)
, φ(
z
)). When the query is propagated to a source peer with the schema
S
(
x
), it
must be reformulated into a query from
S
to
T
, i.e. to
q'
= (
m
S
(
x
)
T
(
x'
,
y
)
, φ'(
x
)). The
query reformulation
concerns the left-hand side of the query, and consists in the appropriate renaming of variables.
The reformulation is performed as follows (Figure 4):
1. We want to determine the qualifier φ'(
x
) over the source schema
S
(
x
). To do this we use the map-
ping
m
S
(
x
)
T
(
x'
,
y
)
.
The qualifier φ'(
x
) is obtained as the result of the following rewriting of the qualifier φ(
z
)
φ'(
x
):= φ(
z
).
rewrite
(
T
(
z
),
T
(
x'
,
y
)),
The rewriting consists in appropriate replacement of variable names. A variable
z
∧
z
occurring in
φ(
z
) is replaced by such a variable
x
∧
x'
that the type of
z
in
T
(
z
) is equal to the type of
x
in
T
(
x'
,
y
).
If such
x
∧
x'
does not exist, the query is not rewritable.
Example 9.
For the query
q
11
= (
m
S
1(
x
1,
x
2,
x
3,
x
4)
S
1(
x
1,
x
2,
x
3,
x
4)
,
x
3
= “
John
”),
we have the following reformulation for its propagation to
S
2
