Databases Reference
In-Depth Information
(i) Let the branch history attached to the object in the retrieval condition be
“”
(null string).
(ii) Let <
b
i-
1
, …,
b
1
> be the branch history of an object
o
transferred from the
upstream neighbor PE, and let be the retrieval result in
the PE with
o
as the key value. Each OID in
R
is transferred to one of the
downstream neighbor PEs with the attached branch history <
k, b
i-
1
, …,
b
1
>.
The termination detection scheme uses a
table T
of branch histories to detect the
acceptance of all the final retrieval results.
T
is held in RCPE (see Fig. 1) and all
termination detection activities are performed in RCPE. Consider the example
illustrated in Fig. 2, where the resultant OIDs and their
branch histories
are reported
in the order
. Changes to
T
are shown in the right-hand side of
Fig. 2.
Figure 2: Object-level retrieval termination detection
For example, if the object
a
is received by RCPE,
a
's history, namely < 2, 3 >, is
entered in
T
. When the object
b
is received, the associated history, < 1, 3 >, is
merged alone into < 3 >, and is entered in
T
. When < 2, 3 > is accepted by receiving
c,
a < 2, 3 > can be found by searching
T,
and these two < 2, 3 >s are merged into
a single < 3 >. Thus,
T
holds two < 3 >s. Next, the two < 2, 3 >s are accepted by
receiving
d
and
e
they are merged into a single < 3 >. At this point, three < 3 >s
remain in
T,
and these are merged into . Eventually,
T
becomes empty, and all
portions of the final retrieval result can be concluded to have arrived at RCPE.
In this example, although the object that can be
logically
merged with
a
is
d
and
not
c, a
can be merged with
c,
which arrives earlier than
d,
as is shown in Fig. 2.
Moreover,
d
can be merged later with
e,
which has the same branch history. In
addition however, in this case, the object that can be logically merged with
d
is
a
and not
e
. We can observe that since
a, b, c,
and
e
have the same branch history,
two arbitrary histories can be merged according to the arrival order, which is
independent of the logical references among the histories.
