Databases Reference
In-Depth Information
set of complex objects, including both aggregation and inheritance hierarchies
2)
.
A third approach is a combination of the above two approaches.
By dividing a large index into sub-indexes and placing each sub-index on a
separate machine, we can improve the efficiency of index operations through
parallelism. In
1)
, a parallel retrieval algorithm was proposed for an index structure
mapped on the hyper-cube parallel machine architecture. In
6)
, an optimizing method
using the horizontal and vertical splitting index was proposed.
In these studies, each processor transfers its own retrieval results asynchronously
and independently of the other processors. No communications among processors
are required for controlling transfer. In such a case, detection of the overall
termination of the parallel retrieval is important.
In the following, we propose termination detection schemes of extremely low
time and space cost, based on the notion of
branch history
. In our schemes, the
multi-indexing scheme is used, which allows us to take advantage of pipeline
parallelism.
Index Splitting and Parallel Retrieval
Let a
path expression
of a complex object be denoted as . Here,
A
1
is an attribute of the class
C
1
. is an attribute of the class
C
j
,
and the
domain of the attribute
A
j-
1
of
C
j-
1
is the class
C
j
. Let the value of
P
be
o
1
o
2
…o
n
+1
.
Here
o
1
is an instance of
C
1
, and
o
j
(
j
> 1) is the value of the attribute
A
j-
1
of object
o
j-
1
.
o
j
is assumed to be not a set.
o
n
+1
is an object identifier or a simple value such
as an integer or a string.
Let the set of values of
P
be denoted as
O
p
. When the value of the attribute
A
j
in
the object
o
j
is
o
j
+1
, the pair <
o
j
, o
j
+1
> is called an
index element
of
P
. Here
o
j
+1
is a
key value
and
o
j
is the corresponding
data value
. The index
I
p
of the path expression
P
is the set of all index elements specified as:
The
extension
of an object
o
is defined as the set of index elements that includes
objects referring to
o
directly or indirectly. Consider the following retrieval query:
“Retrieve the set of objects in the class
C
1
for which the value of the attribute
A
n
is
s
n
”
The
multi-indexing scheme
traverses the extension of
s
n
using
I
p
in the order <
o
n
,
s
n
>, <
o
n-
1
,
o
n
>…<
o
1
,
o
2
>, and finally returns the set of
o
1
as the retrieval result.
Index splitting
Let
I
p
be divided into the sub-indexes where
. The set of sub-indexes {
V
1
,
V
2
, …,
V
n
} is called a
V-partition
of
I
p
. Let each
V
j
be further divided into
m
j
sub-indexes horizontally,
each of which is denoted as
, and maintained in the processor
element
(See Fig.1).
