Large-Scale RDF Processing with MapReduce - Large Scale and Big Data: Processing and Management - page 171

5.6.2 C asCaDing J oins
Chains of concatenated triple patterns require some slight modifications to the pre-
viously described base case. To compute a query of at least three triple patterns we
have to process several joins successively, for example, p 1 ⋈ p 2 ⋈ p 3 . The processing
of the first two patterns p 1 ⋈ p 2 correspond to the base case and the results are stored
in HDFS. The additional triple pattern p 3 is then joined with the mappings for p 1 ⋈
p 2 . To this end, an additional map-phase (without any intermediate shuffle or reduce
phase) is initialized with the previously computed mappings as input. Since these
mappings reside in HDFS, they are retrieved locally in parallel such that the map
function gets invoked for each mapping μ 2 for p 1 ⋈ p 2 . The compatible mappings
for p 3 are retrieved using the same strategy as for the base case, that is, μ 2 is used to
substitute the shared variables in p 3 , p

sub
3

=µ 2 ( , and compatible mappings are
retrieved following the triple pattern mapping outlined in Table 5.4. Algorithm 5.1
outlines one iteration of the MAPSIN join. The input for the map function contains
either a mapping for the first triple pattern (via distributed table scan) or a mapping
for previously joined triple patterns (loaded from HDFS).

p

3

Algorithm 5.1: MAPSIN Join: map(inKey, inValue)

input : inKey, inValue: value contains input mapping, key can be ignored
output : multiset of mappings
1 p n +1 Cong.getNextPattern()
2 μ n inValue .getInputMapping()
3 Ω n +1 ∅
4 if dom ( μ n ) dom ( p n +1 ) = ∅ then
5

/ / substitute shared vars in p n +1

sub

6 p n +1 μ n ( p n +1 )

sub

7 results HBase.GET( p n +1 ) / / table index lookup using substituted pattern

8 else
9 results HBase.GET( p n +1 ) / / table index lookup using unsubstituted pattern
10 end
11 if results ≠ ∅ then
12 / / merge μ n with compatible mappings for p n +1
13 foreach mapping μ in results do
14 μ n +1 μ n μ
15 Ω n +1 Ω n +1 μ n +1
16 end
17 emit( null, Ω n +1 ) / / key is not used since there is no reduce phase
18 end