Algebraic Optimization of RDF Graph Pattern Queries on MapReduce - Large Scale and Big Data: Processing and Management - page 219

Pr1_rMap—PF1, PF2, PF3, PF4, PF5
Property
pLabel
pProp
Producer
prodFeature

Object
o1
o2
o3
{PF1, PF2, PF3,
PF4, PF5}

Indirect Hashing
(PF1, PF3, PF5)
(PF2, PF4)

unnest

partial-unnest

k1*
k2*

→

→

Mapper

Mapper

<PF1, Pr1_rMap-PF1>
<PF2, Pr1_rMap-PF2>
<PF3, Pr1_rMap-PF3>
<PF4, Pr1_rMap-PF4>
<PF5, Pr1_rMap-PF5>

Map output of
MR J1

Optimized map
output of MR J1

< K1*, Pr1_rMap-PF1, PF3, PF5>
< K2*, Pr1_rMap-PF2, PF4>

Rep = 5 Rep = 2

PF2,<PFList ,PrLi..
PF3,<PFList ,PrLi..

K1*,<PFList ,PrList>

Reducer_bkt 1 Reducer_bkt 2 Reducer_bkt 1

K2*,<PFList ,PrList>

Rf_bkt
1:PF1

Rf_bkt
1:K1*

Rf_bkt
2:PF2

PF1_rMap-PF1 PF2_rMap-PF2

Pr1_rMap-PF1
Pr3_rMap-PF1

PF1_rMap-PF1
PF3_rMap-PF3
PF5_rMap-PF5

Pr1_rMap-PF1, PF3, PF5
Pr1_rMap-PF3
Pr3_rMap-PF1, PF5

Pr1_rMap-PF2
Pr2_rMap-PF2
Pr3_rMap-PF2

Rf_bkt
1:PF3

PF3_rMap-PF3

Reducer_bkt 2

Pr1_rMap-PF3
Pr2_rMap-PF3

Rf_bkt
2:PF4

PF4_rMap-PF4

Pr1_rMap-PF4
Pr2_rMap-PF4
Pr3_rMap-PF4

Rf_bkt
1:K2*

PF2_rMap-PF2
PF4_rMap-PF4

Pr1_rMap-PF2, PF4
Pr2_rMap-PF2, PF4
Pr3_rMap-PF2, PF4

Rf_bkt
1:PF5

PF5_rMap-PF5

Pr1_rMap-PF5
Pr3_rMap-PF5

Product

ProductFeature

(a) (b)

FIGURE 6.19 Lazy map-side unnest strategies: (a) complete unnesting ( Rep = 5) and (b) partial unnesting ( Rep = 2).