## 6 BFS-Based Implementation of RDF Graph Traversals over MapReduce
```  
In more detail, for each row, stored metadata have the following semantics: (see the previous example--the description is field-based): (\(i\)) the first number is the node ID; (\(ii\)) the subsequent list of numbers represents the adjacent list for that node, and it is equal to NULL if empty; (\(iii\)) the subsequent color-code represents the state of the node; (\(iv\)) the last symbol states if the target node has been processed (_i.e._, then, it is equal to \"1\") or not (_i.e._, then, it is equal to \"7\"). The adoption of this metadata information exposes the clear advantage of supporting _portability_ and _interoperability_ within Cloud environments widely. Looking into code-wise details, the proposed algorithm consists of a series of iterations where each iteration represents a MapReduce job using the output from the previous MapReduce job until the convergence criterion is met. The _Mapper_ job (see Algorithm 2) allows us to expand the frontier of exploration by selecting the new nodes to explore (the ones that in the standard BFS algorithm are inserted into the queue) and the ones already explored (or still not explored), as to complete the output. ```
0:key -- ID of the current node; value -- node information Output:void -- a new node is emitted Begin \(u\leftarrow\) (Node)value; if(u.color == GREY)then for(each\(v\in L_{u}\))do//L\({}_{u}\)is the adjacency list of u \(v\leftarrow\)newNode();  v.color == GREY; // mark v as unexplored for(each\(c\in P_{u}\))do//P\({}_{u}\)is the path list of u  c.ID = u.ID;  c.tag = u.tag;  v.add(c); endfor; emit(v.ID,v); endfor; u.color = BLACK; // mark u as explored endif; emit(key,u); return; End;
```  
**Algorithm 2**Map(_key_, _value_)  
The _Reducer_ job (see Algorithm 3) allows us to (_i_) merge the data provided by the _Mapper_ and re-create an adjacency list that will be used at the next step and (_ii_) update the counter for the convergence test. More in detail, in order to merge nodes with the same ID, a color priority method was devised so that, in the case of the generation of a node with the same ID with different color, the darkest one will be saved. ```
Input:key -- ID of the current node; values -- node information list Output:void -- updates for the current node are emitted Begin \(newNode\leftarrow\)newNode(); for(each\(u\in values\))do  merge(newNode.edgeList(),u.edgeList()); // merge the newNode's edge list with u's edge list  merge(newNode.tagList(),u.tagList()); // merge the newNode's tag list with u's tag list  newNode.setToDarkest(newNode.color,u.color); // set color of newNode to the darkest color endfor; // between the newNode's color and the u's color update(WHITE,GREY,BLACK); // update the number of processed nodes having color WHITE, GREY, BLACK emit(key.newNode); // emit updates for the current node return; End;
```  
**Algorithm 3**Reduce(_key_, _values_)  
```
Input:key -- ID of the current node; values -- node information list Output:void -- updates for the current node are emitted begin \(newNode\leftarrow\)newNode(); for(each\(u\in values\))do  merge(newNode.edgeList(),u.edgeList()); // merge the newNode's edge list with u's edge list  merge(newNode.tagList(),u.tagList()); // merge the newNode's tag list with u's tag list  newNode.setToDarkest(newNode.color,u.color); // set color of newNode to the darkest color endfor; // between the newNode's color and the u's color update(WHITE,GREY,BLACK); // update the number of processed nodes having color WHITE, GREY, BLACK emit(key.newNode); // emit updates for the current node return; End;
```  
**Algorithm 4**Reduce(_key_, _value_)
By inspecting our proposed algorithm, it clearly turns that new nodes are generated via a series of MapReduce steps. This may increase _communication costs_, but our experimental analysis proves that they are limited in impact. Indeed, in Section 7, we show that our throughput performance analysis, which includes the impact of communication costs, exposes a good behavior.