Databases Reference
In-Depth Information
Note that the above-sketched scheme works in parallel with the group of PEs
concerned in the retrieval.
•
Packet level detection
Packet-level detection suffers from the following defects.
(1) Transferring overhead
Since a branch history is associated with an object (i.e., OID), the extra
overhead of transferring the branch history through the communication
line increases to a large degree. If the complex objects are deeply nested,
this overhead would become very large.
(2) Termination detection overhead
While the index retrieval is performed in parallel by more than one PE, the
termination detection is performed only in RCPE (See Fig.1). For every
arrival of an object, the RCPE has to check the possibility of merging branch
histories. This would be a great burden for the PE.
In order to reduce the above-described overhead, instead of attaching a branch
history to every object, we attach the branch to every packet that stores more than
one object for transfer. If a PE receives a packet
P
from one of the upstream neighbor
PEs, for every object in
P
it searches the corresponding data values and packs
them into an output packet, which is transferred to the related downstream neighbor
PE. First, we modify the definition of branch history.
(i)
Let the branch history attached to the packet including the object in the
retrieval condition be
“
ε
”
.
(ii) Let <
b
i-
1
, …,
b
1
> be the branch history of a packet
P
transferred from the
upstream neighbor PE. The output packets would be produced one after
another to store the retrieval results. Since the number
'p'
packets produced
is not known until all of the retrieval results are known, all packets except
the final packet have the branch history <
unknown, b
i-
1
, …,
b
1
>. Only
when the last packet is fixed,
p
is known. Therefore, only the last packet
has the branch history <
p, b
i-
1
, …,
b
1
>.
For example, assume that the input packet
P
with the branch history < 3,
unknown
> is received and that three packets are produced by retrieving each OID in
P
as a
key value. The first two packets have the branch history <
unknown,
3,
unknown
> and the last packet has the branch history < 3, 3,
unknown
>. An example of the
branch histories of packets is shown on the left-hand side of Fig.3.
Merging branch histories is not performed if all of their first terms are
unknown
.
If these branch histories include a branch history in which the first term is fixed
(known), the possibility of merging would be checked. For example, if there exist
two <
unknown,
2,
unknown
>s in
T,
merging these branch histories into < 2,
unknown
> will occur when < 3, 2,
unknown
> is received. If there exist <
unknown,
