An Algorithm for Querying Linked Data Using Map-Reduce - Data Management in Cloud, Grid and P2P Systems - page 59

begin
- emit([ Q i , (bn, nbn)]); // emits total embedding with key the subquery Q i
- for i=0to |bn| -1 do
if (bn[i] != '*') then
for each ( i, Q j ) in NBL do emit ([ Q j , ( i, bn [ i ])]) ;

end

end.

Example 8. (Continued from Example 7). Between the total embeddings of Q 1
that constructs and emits reducer with key Q 1 are:
(1) = > key = Q1, value = ( < Person4,Article1,* > , < *,”Title1” > )
(3)+(8) = > key = Q1, value = ( < Person2,Article2,* > , < *,”Title2” > )
It also emits the following missing branching node values:
key = Q2, value = (1,Person2) key = Q2, value = (1,Person4)
key = Q3, value = (2,Article1) key = Q3, value = (2,Article2), ...
The Reducer for key Q2 constructs and emits the total embeddings for Q 2 :
(4)+(9) = > key = Q2, value = ( < *,Article1,Person1 > , < Journal1,* > )
(5)+(10) = > key = Q2, value = ( < *,Article2,Person3 > , < Journal1,* > )
and the following values for missing branching nodes:
key = Q3, value = (2,Article1) key = Q3, value = (2,Article2)

key = Q1, value = (3,Person1) key = Q1, value = (3,Person3), ...

Reducer for key Q3 emits:
(6) = > key = Q3, value = ( < Person4,*,Person1 > , < *,* > )
(7) = > key = Q3, value = ( < Person2,*,Person3 > , < *,* > )
key = Q2, value = (1,Person2) key = Q2, value = (1,Person4)

key = Q1, value = (3,Person1) key = Q1, value = (3,Person3)

5.4 Phase 2 of the Algorithm

Mapper of Phase 2. Each mapper manipulates the embeddings of a specific
subquery. It fills in their missing branching node values using values from the em-
beddings of other subqueries and emits the resulted embeddings to the reducers
of Phase 2 (the key is the tuple of the branching node values):

mapper2 ( Q i ,values)
// Q i : the ID of a subquery
// values: a set E of the parts (bn, nbn) of the total embeddings of Q i and
//aset V of pairs ( i, v ) ,where v is a candidate value for bn [ i ]
begin
- for each embedding e =( bn, nbn ) in E do
- for each instance bn of bn using the values in V do emit ([ bn , ( Q i ,nbn )])

end.

Example 9. (Continued from Example 8). Mapper with key Q1 receives:

E= { ( < Person4,Article1,* > , < *,”Title1” > ), ( < Person2,Article2,* > , < *,”Title2” > ),... }
V= { (3,Person1), (3,Person3),... }