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

for example, marking the bits corresponding to the property vendor and price in
Figure 6.10c. After processing all triples in a group, if the local BitSet ( locBitSet )
does not match the global BitSet ( ECBitSet ), the structure is incomplete and
the group of triples is eliminated (line 4). Figure 6.10d shows that locBitSet of
triplegroup tg 3 is not matched with any global bit patterns representing the two
star patterns; therefore, tg 3 is discarded.

Algorithm 6.2: POTGJoinAnnotator

Map ( key:null, val : RDFMap rMap ) ;
1if join on Sub then
2 joinKey rMap.Sub ;
else if join on Obj then
3 joinKey extract joinKey from rMap.propM ap ;
4 emit joinKey , rMap ;

6.6.3.4 Implementation of TG_Join
The physical operators POTGJoinAnnotator and POTGJoinPackage are mapped
into the operator TG _ Join in NTGA. Both operators take as input a single relation
containing RDFMaps, and computes the join operation between star patterns. In the
map phase, the physical operator POTGJoinAnnotator annotates the RDFMaps
based on the join key corresponding to their equivalence class (lines 1-4 of Algorithm
6.2). In the reduce phase, the physical operator POTGJoinPackage is executed. The
operator separates the RDFMaps based on their equivalence class EC (lines 1-4 of
Algorithm 6.3) and packages the joined RDFMaps into a new RDFMap (lines 5-11),
which corresponds to a nested triplegroup. The equivalence class EC of the new joined
RDFMap is a function of the EC of the individual RDFMaps (line 8). In our implemen-
tation, the Sub field is a concatenation of the Sub fields of the joining RDFMaps.

Algorithm 6.3: POTGJoinPackage

Reduce ( key:joinKey, val:List of RDFMaps R ) ;
1 foreach rMap

R do

2if rMap.EC == EC 1 then

3 add rMap to leftList ;

else if rMap.EC == EC 2 then

4 add rMap to rightList ;

5 foreach left leftList do

6 foreach right rightList do

7 propM ap joinProp( left.propMap , right.propM ap ) ;

8 EC joinEC( left.EC , right.EC ) ;

9 Sub joinSub( left.Sub , right.Sub ) ;

10 rMap RDFMap( Sub , EC , propM ap ) ;

11 emit rMap ;