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

mapper1 (( Q i , G j ), (GjData, subqueryInfo))
//( Q i , G j ): Q i / G j is the ID of a subquery/data segment
// GjData: the content of the data graph segment G j
// SubqueryInfo: prototypes/branching & non-branching nodes/triples of Q
begin
- compute E = {e|e is a useful partial embedding of Q i in GjData }
- for each e ∈ E do emit ([ Q i ,e ])
end.

Example 7. (Continued from Example 6). Some embeddings of Q 1 , Q 2 and Q 3
in the segments G 1 , G 2 and G 3 computed by the corresponding mappers and
emitted with key the subquery ID, appear below. More specifically, a total em-
bedding evaluated and emitted by the mapper working on ( Q 1 ,G 1 ), is 2 :
(1) key = Q1, value = ( < Person4,Article1,* > , < *,”Title1” > , < +, , , ,+ > )
The Mapper working on ( Q 2 ,G 1 ) computes and emits the partial embedding:
(2) key = Q2, value = ( < *,Article1,Person4 > , < *,* > , < , ,+, , > )
Between the embeddings obtained and emitted by the Mapper working on
( Q 1 ,G 2 ) is the (partial) embedding:
(3) key = Q1, value = ( < Person2,Article2,* > , < *,* > , < +, , , , > )
Between the embeddings obtained and emitted by the Mapper working on
( Q 2 ,G 2 ) are the (partial) embeddings:
(4) key = Q2, value = ( < *,Article1,Person1 > , < *,* > , < , ,+, , > )
(5) key = Q2, value = ( < *,Article2,Person3 > , < *,* > , < , ,+, , > )
The Mapper working on ( Q 3 ,G 2 ) computes and emits the total embeddings:
(6) key = Q3, value = ( < Person4,*,Person1 > , < *,* > , < ,+, , , > )
(7) key = Q3, value = ( < Person2,*,Person3 > , < *,* > , < ,+, , , > )
The Mapper working on ( Q 1 ,G 3 ) emits the partial embedding:
(8) key = Q1, value = ( < *,Article2,* > , < *,”Title2” > , < , , , ,+ > )
The Mapper working on ( Q 2 ,G 3 ) emits the partial embeddings:
(9) key = Q2, value = ( < *,Article1,* > , < Journal1,* > , < , , ,+, > )

(10) )

The mappers working on ( Q 3 ,G 3 )and( Q 3 ,G 1 ) return no embeddings.

key = Q2, value = ( < *,Article2,* > , < Journal1,* > , < , , ,+, >

Reducer of Phase 1. A reducer receives all useful embeddings of a subquery
Q i in all graph segments G 1 ,...,G m of G , computes all total embeddings of Q i ,
in G and emits them to the mappers of phase 2 with key the subquery ID. It also
emits (with proper subquery IDs as keys) the branching node values from the
total embeddings of Q i to be used in the total embeddings of other subqueries:

reducer1 ( Q i ,values )
// Q i : a subquery ID. values: contains a list of embeddings for Q i and the NBL list
begin
- collect in a list F i the total embeddings of Q i appearing in values or
obtained by joining partial embeddings in values
- for each embedding e =( bn, nbn, tl ) in F i do

2 Notice that we can check if an embedding is total or partial by comparing it with
the corresponding subquery prototype (see Example 6).