## 5 Related Work
### MapReduce Algorithms for RDF Databases  
The relevance of RDF query processing via MapReduce has been highlighted by several studies (e.g., [57; 58; 59]). Basically, these works focus the attention on RDF data management architectures and systems designed for Cloud environments, with a special focus to large-scale RDF processing. Approaches investigated here mainly consider several special tasks that can be performed on the Web via RDF, such as _Web data publishing_ and _Web data exchanging_. Paper [60] focuses the attention on _querying linked data based on MapReduce_. Linked data can easily be modeled via RDF databases. In particular, authors consider linked data that are arbitrarily partitioned and distributed over a set of Cloud nodes, such that input queries are decomposed into a set of suitable _sub-queries_, each one involving data stored in a specific node. The proposed method is two-step in nature. In the first step, sub-queries are executed on the respective node in an isolated manner. In the second step, intermediate results are combined in order to obtain the final answer to the input query. The innovation introduced by this research effort consists in the fact that the proposedquery algorithm is independent of all the parameters of the model, _i.e._, linked data partitioning, local data storage, query decomposition mechanism, local query algorithm. SPARQL query processing over RDF data has attracted a lot of attention from the research community as well. In this context, several approaches have been proposed recently. [61] addresses the problem of _supporting SPARQL queries over very large RDF datasets_ via mapping SPARQL statements over _PigLatin_[62] programs. These programs are finally executed in terms of a series of MapReduce jobs on top of a Hadoop cluster. The study also provides an interesting experimental trade-off analysis on top of a popular benchmark dataset. [63] also investigates _scalability issues of processing SPARQL queries over Web-scale RDF knowledge bases_. To this end, authors propose an innovative partitioning method particularly suitable to RDF data that introduces the nice amenity of providing _effective indexing schemes_ for supporting efficient SPARQL query processing over MapReduce. Still in this area, [64; 65] provide anatomy and main functionalities of _a semantic data analytical engine_ and _a Cloud-enabled RDF triple store_, respectively. Both embed several points of research innovation over state-of-the-art proposals. Contribution [66] studies how to apply _compression paradigms_ to obtain _scalable RDF processing with MapReduce_. Authors point the specific case of Semantic Web, where _many billions of statements_, which are released using the RDF data model, exist. Therefore, they propose to apply a novel data compression technique in order to tame the severity of data size, and thus design _a set of distributed MapReduce algorithms_ to efficiently compress and decompress a large amount of RDF data. In particular, they apply a _dictionary encoding technique_ that maintains the structure of the (Web) data. The solution is implemented as a prototype using the Hadoop framework, and its performance is evaluated over a large amount of data and scales linearly on both input size and number of nodes. Still in the context of optimization issues, [67] proposes _a novel nested data model for representing intermediate data_ of RDF processing concisely using _nesting-aware dataflow operators_ that allow for lazy and partial un-nesting strategies. Indeed, authors correctly recognize that, during RDF data processing, intermediate results of joins with multi-valued attributes or relationships contain redundant sub-tuples due to repetition of single-valued attributes. As a consequence, the amount of redundant content is high for real-world multi-valued relationships in typical data-intensive instances such as social networks or biological datasets.