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

Algorithm 6.5: Extended POTGJoinAnnotator ( TG _ OptMVJoin )

Map ( key:null, val: RDFMap rMap ) ;
1if join on Sub then
2 emit func*( rMap.Sub ), rMap ;

else if join on Obj then
//Partially unnest MVP's ObjList in rMap based on
k* = func* ( Obj )

3 pList partial-unnest ( rMap , func* );

4 foreach partialM ap pList do

5 key extract k * for partialMap ;

6 emit key , partialM ap ;

partial-unnest ( RDFMap rMap , func* )
//RDFMap( Sub , EC , propM ap )

;

7 objList extract MV prop's listofobjects from propM ap ;
8 foreach obj objList do
9 groupKey func* ( obj );
10 add( prop , obj )to partialList [ groupKey ] ;
11 emit partialList ;

Algorithm 6.6 shows the extensions to POTGJoinPackage operator, where all
RDFMaps corresponding to the same group key k * but different join keys are pro-
cessed in the same reduce(). For example, RDFMaps in Reducer_ bkt 1 correspond
to group key k 1* but different original keys PF 1, PF 3, and PF 5. This requires selec-
tively joining RDFMaps based on the original join key. RDFMaps corresponding
to the left relation ( leftEC ) are extracted into a list (line 1). RDFMaps from the
right relation ( rightEC ) are unnested and hashed based on the join key (line 2). The
algorithm iterates through each RDFMap in the left relation (line 3), and probes
the hashed relation for each distinct object value (join key) for each property (lines
4-6). When a match is found the RDFMaps are joined (line 7) as per the definition
of TG _ Join . Additional details about the partitioning scheme and a discussion on
the implementation issues can be found here [37].

Algorithm 6.6: Extended POTGJoinPackage ( TG _ OptMVJoin )

Reduce ( key:k* , val:List of RDFMaps R ) ;
1 lef tList extract leftEC RDFMaps from R //MV
2 rightHash extract rightECRDFMaps from R //non-MV
3 foreach leftR leftList do
//Handle multivalued property

4 MVList extract prop's objList from leftR ;

5 foreach joinKey MVList do

6 rightR rightHash. get( joinKey );

7 emit joinRDFMaps( leftR , rightR ) ;