Database Reference
In-Depth Information
Figure 5. Three execution strategies for query q
11
a
a
a
Ans
=
merge Ans Ans Ans
({
,
,
}),
a
11
21
31
Ans
a
11
=
q I
( )
=
{(
x
:
⊥
,
x
:
⊥
,
x
:
⊥
,
x
: )},
⊥
11
1
1
2
3
4
a
21
(
)
{(
:
,
:
,
:
)},
Ans
=
q
I
=
x XML x
John x NY
21
2
1
3
4
a
31
Ans
=
q
(
I
)
=
{(
x
:
⊥
,
x
:
⊥
,
x
: )},
⊥
31
3
3
1
2
Ans
a
=
{(
x XML x
:
,
:
⊥
,
x
:
John x NY
,
:
)}.
1
2
3
4
Strategy
(
b
).
It differs from strategy (
a
) in that
P
2
after receiving the query propagates it to
P
3
and
waits for the answer
q
32
(
I
3
). It is obvious that the result
Ans
b
is equal to
Ans
a
:
b
b
b
Ans
=
=
merge Ans Ans Ans
x XML x
({
,
,
})
b
11
21
31
{(
:
,
:
⊥
,
x
:
John x
,
4
:
NY
)}.
1
2
3
Strategy
(
c
).
In contrast to the strategy (
b
), the peer
P
3
propagates the query to
P
2
and waits for the
answer. Next, the peer
P
3
decides to merge the obtained answer
q
23
(
I
2
). with the whole its instance
I
3
. The
decision follows from the fact that the functional dependency /
authors
/
author
/
paper
[
title
=
x
1
]/
year
is
defined over the local schema of
P
2
, and satisfies the necessary condition for discovering missing values
of variable
x
2
of the type /
authors
/
author
/
paper
/
year
(Theorem 1). So we have:
Ans
=
merge Ans Ans Ans
({
c
,
c
,
c
}),
c
11
23
31
c
23
{(
:
,
:
,
:
)},
Ans
=
x XML x
⊥
x
John
1
2
3
c
c
Ans
=
=
q merge I Ans
x XML x
(
({ ,
})
31
31
3
23
)},
{(
:
,
:
2005
,
x
:
John
1
2
3
Ans
c
=
{(
x XML x
:
,
:
2005
,
x
:
John x NY
,
:
)}.
1
2
3
4
While computing
merge
({
I
3
,
Ans
c
23
}) a missing value of
x
2
is discovered. Thus, the answer
Ans
c
provides more information than those in strategies (
a
) and (
b
).
