Database Reference
In-Depth Information
a
A
B
C
D
AB
AB
AC
AC
AD
AD
BC
BC
BD
BD
CD
CD
b
A
B
C
D
AB
AB
AC
AC
AD
AD
BC
BC
BD
BD
CD
CD
Fig. 7.7
Computation of the minimum bipartite matching between two levels in the
cube lattice
that is,
k
+ 1 outgoing edges. All original edges have cost
A
(
e
ij
)andall
replicated edges have cost
S
(
e
ij
). Therefore, this transformed graph induces
a bipartite graph (because there are edges between nodes in different levels
but not between nodes in the same level). Finally, we compute the minimum
cost matching in this bipartite graph such that each node
j
in level
k
will be
matched to some node
i
in level
k
+1.If
j
is connected to
i
by an
A
() edge,
then
j
determines the attribute order in which
i
will be sorted during its
computation. If, instead,
j
is connected to
i
by an
S
() edge,
i
will be sorted
in order to compute
j
.
As an example, consider in Fig.
7.7
the graph constructed as indicated
above, for levels 1 and 2 of the lattice in Fig.
7.6
.Edgesoftype
A
(
e
ij
)are
represented with solid lines, while edges of type
S
(
e
ij
) with dashed lines. Note
that in Fig.
7.7
a we have added a copy of each node at level 2. In Fig.
7.7
b,
we can see that all the views will be computed at a cost
A
(
e
ij
). For example,
A
will be computed from
AC
,
B
from
BA
,andsoon.
The matching above is performed
N
times, where
N
is the number of
grouping attributes, generating an evaluation plan. The heuristics is that if
for every pair of levels the cost is minimum, the same occurs for the whole
plan. The output lattice gives a sorting order to compute each node. As a
result, the PipeSort algorithm induces the following evaluation strategy: in
every chain such that a node in level
k
is a prefix of node in level
k
+1(in
the output graph), all aggregations can be computed in a pipeline.
The general scheme of the PipeSort algorithm is given next:
PipeSort Algorithm
INPUT: A search lattice with the
A
()
and
S
()
edges costs
OUTPUT: An evaluation plan to compute all nodes in the search lattice
For level
k
=0
to level
N −
1
Generate-Plan(
k
+1
→ k
);
For each node
i
in level
k
+1
Search WWH ::
Custom Search