A
Survey Report on RDF Data Query Processing
Introduction
The third generation of the World
Wide Web (Web 3.0) for semantic affiliation or knowledge content uses Resource
Description Framework (RDF) for conceptual foundation and model for the
information in Web resources. RDF model that can represent data in a format of
machine-readable form has been popularly used in many Web 3.0 applications of
knowledge management. The structure of RDF expression is a set of triples or a
directed labeled RDF graph. Each triple consists of (1) subject, (2) predicate,
and (3) object. Querying RDF triplets is similar to perform large join
operations that traditional relational computing is unable to query a large
number of star join operations properly. Uniform Resource Identifier (URI) is
usually used in RDF to identify a unique Web resource (Brickley & Guha,
2014). SPARQL (Simple Protocol and RDF Query Language) is an RDF query language
or semantic query language that can retrieve and manipulate RDF data (W3C,
2004). However, querying large-scale RDF data sets encounters some difficult
problem. For instance, the computation of SPARQL queries on large-scale Web
data sets requires several joins between subsets of data that cause challenges
in code programming. Also, the traditional approaches of the single-place
machine cannot scale up or scale out due to increasing available RDF data.
In 2004, Google’s MapReduce
framework with a parallel and distributed algorithm as part of the solutions
opened up different ways to improve RDF query performance’s efficiency. For
example, Amazon’s EC2 (Elastic Compute Cloud), YARS2, 4store are a few
solutions. In this survey report, two promising solutions (1) PigSPARQL and (2)
MAPSIN to improve RDF query performance will be compared and evaluated based on
four criteria: main focus, key technical changes, rationale, and analysis of
pros and cons of each solution.
Main focus of the solutions
1. PigSPARQL
SPARQL recommended by the W3C is standard query language for a large number
of RDF datasets. It uses RDF triples whose subject, predicate and object are
variables in a sequence of MapReduce iterations of mapping, shuffling, sorting,
and reducing tasks. The challenge is joining data sets properly in either
map-side or reduce-side in SPARQL query or RDF graph. For reduce-side, join
computation is inefficient in selective joins and requires a great deal of
network bandwidth. On the map-side, the merge joins are difficult to cascade,
and some advantage such as avoiding shuffle is lost (Ghemawat, Gobioff & Leung,
2003). Pig Latin developed by Yahoo! Research is an Apache Hadoop-based
language for vast scale data set analysis. For Hadoop, Pig is a
high-prioritized project for automatic translation a Pig Latin program into
MapReduce jobs. A translation of SPARQL to Pig Latin ensures the main focus that SPARQL query processing
on a cluster of MapReduce framework with the advantage of performance
enhancement and newer Hadoop versions support from further developing Apache
Pig with minimum programming code changes (Blanas, Patel, Ercegovac, Rao,
Shekita & Tian, 2010). PigSPARQL is RDF query translation technique to translate
complex SPARQL queries to Pig Latin
on a MapReduce cluster. Fig 1 illustrates a high-level modular translation
process.
Fig 1: A modular translation
process
Source: Adapted from
Schatzle et al., 2011.
2. MAPSIN
Based on HBase’s indexing capabilities, MAPSIN
(Map-Side Index Nested Loop Join) improves selective query performance by
maintaining the reduce-side joins’ flexibility while using the map-side join’s
effectiveness without the change in the framework. Its main focus is to arrange MAPSIN joins with NoSQL HBase’s indexing
capabilities for scalable joins on Hadoop MapReduce framework in multiway joins
and one-pattern queries. HBase, that is a NoSQL column family or
column-oriented database integrated well into Hadoop, can store arbitrary RDF
graphs. RDF storage schema defines data modeling’s literature for RDF data in
semantic expressions. HBase becomes an extra storage layer on top of HDFS for
access data randomly almost at the real time where HDFS does not have this
ability. MAPSIN computes the join between two triple patterns in merging
compatible mappings in a single map phase only on transferring the needed data.
Fig 2 illustrates a typical RDF graph and SPARQL query.
Fig 2: RDF graph and
SPARQL query
Source: Adapted from
Schatzle et al., 2012.
Main technical changes
The key technical changes in PigSPARQL and MAPSIN are discussed as follows:
1. PigSPARQL
With RDF format data, SPARQL query language, MapReduce model, and Pig Latin
implementation, PiqSPARQL translate complex SPARQL queries through algebraic
presentations such as syntax tree, algebra tree, Pig Latin program to MapReduce
jobs. Notice that an SPARQL query is addressed on the algebra level and SPAQRL
algebra’s expression is interpreted as a tree that is bottom-up evaluated.
Query processing time in regarding the size of the RDF data, a feature of
MapReduce framework, is linear scalability (Schatzle, Przyjaciel-Zablocki &
Lausen, 2011).
2. MAPSIN
With HBase's indexing capabilities, MAPSIN join uses join technique by
computing the join between two triple patterns for output in a single map phase
with minimum transferred data. Triple patterns are cascaded in chains for
computations of mapping in the iteration of the MAPSIN join. MAPSIN joins’
performance and the HBase's number of index lookups are tightly correlated. It
is crucial to minimize the number of index lookups for optimization (Schatzle,
Przyjaciel-Zablocki, Dorner, Hornung, & Lausen, 2012).
Rationale for the technical changes
The rationale for the
technical changes in
PigSPARQL and MAPSIN is explained below:
1. PigSPARQL
Querying RDF datasets at web-scale is difficult due to the requirement of several
joins between data subsets in SPARQL computing and the single-place machine
technique cannot scale to meet large RDF data. MapReduce framework with its
well scalable properties becomes attractive for SPARQL in the Apache Hadoop
platform.
By extracting
information from a large RDF dataset then transforming and loading the
extracted data into a different format, it appears that cluster-based
parallelism outperforms parallel databases. PigSPARQL offers not only RDF data
query transformation but also a scalable implementation of the entire
ETL-process on a MapReduce cluster. PiqSPARQL provides good performance and
excellent scalability for complex analytical queries, but it suffers from poor
performance for selective queries because PiqSPAQRL does not have adequately
built-in index structures and redundant data shuffling in join computation in
the reduce phase (Schatzle et al., 2011).
2. MAPSIN
According to Schatzle et al. (2012), MAPSIN join takes advantage of the
distributed NoSQL HBase’s indexing capabilities to increase selective queries’
performance. HBase as top layer storage on HDFS can process data for MAPSIN
joins in the map phase to avoid costly data shuffling. MAPSIN join algorithm
can do joins cascade in MapReduce iteration. For consecutive joins, there is no
need an additional shuffle and reduce phase to pre-process the data.
Especially, MAPSIN joins require no changes in the underlying MapReduce
frameworks. Schatzle’s evaluation indicated that significant improvement of
selective queries over the common reduce-side join.
Analysis of pros and cons
Performance between PigSPARQL (with
SPARQL and Pig Latin) and MAPSIN (with HBase) is analyzed. Their pros and cons
are discussed as follows:
1. PigSPARQL
a. Pros
PigSPARQL is a translation framework
of RDF data queries from SPARQL to Pig Latin on MapReduce cluster without code
changes or overhead management. It takes advantage of parallel processing of
the large-scale datasets. PigSPARQL provides transformation part in scalable
implementation in ETL-based applications. PigSPARQL approach is easier to
achieve and handle than direct mapping into MapReduce framework (Afrati & Ullman, 2011). PigSPARQL’s translation uses several
optimization strategies effectively. PigSPARQL’s performance and its scaling
properties are competitive for complex analytical queries.
b. Cons
PigSPARQL performs poorly on
selective queries. It does not have built-in index structures. In the reduce
phase, it does data shuffling unnecessarily in join computation.
2. MAPSIN
a. Pros
MAPSIN join takes advantage of the
distributed NoSQL database HBase’s indexing capabilities to improve selective
queries. It eliminates the costly data shuffling and increases selective
queries over the common reduce-side join. HBase can store a space-efficient RDF
data schema with favorable access characteristics. With HBase, there are no shuffling
join partitions across the network. Users can access the relevant join partners
in each iteration. The reduce phase is not used in MAPSIN join. Also, there is
no change in the MapReduce framework or Hadoop platform. Map-side joins are
much more efficient than reduce-side joins. HBase and MapReduce’s combination
allows cascading a sequence of MAPSIN joins without sorting and repartitioning
the intermediate output for next iteration (Dean & Ghemawat, 2008). The number of MapReduce iterations and HBase
requests are reduced in the multiway optimization. Overall, the MAPSIN join
approach outperforms the reduce-side join for selective queries with an improvement
of the total query execution times significantly.
b. Cons
MAPSIN joins require some strict
precondition that makes them difficult to utilize in the sequence of joins.
Conclusion
In summary, the survey report provided two wide-used approaches, i.e.,
PigSPAQRL and MAPSIN, based on MapReduce framework and Hadoop platform to
process RDF data queries in large-scale data sets. The survey report identified
the primary focus and described each high-level approach with associated
SPAQRL, Pig Latin, HBase, MapReduce framework, and Hadoop HDFS. The rationale of these technical changes in
each solution was provided. The survey report also offered the analysis of pros
and cons of PigSPAQRL and MAPSIN. A question that was brought up is how to
incorporate MAPSIN joins into PigSPAQRL in a complimentarily hybrid solution
for dynamic join method on pattern selectivity and statistics at data loading
time.
REFERENCES
Afrati, F. &
Ullman, J. (2011). Optimizing multiway joins in a map-reduce environment. IEEE
Trans. Knowl. Data Eng. 23(9), 1282–1298.
Blanas, S.,
Patel, J.M., Ercegovac, V., Rao, J., Shekita, E.J. & Tian, Y. (2010). A
comparison of join algorithms for log processing in mapreduce. In: SIGMOD.
Brickley, D.,
& Guha, R. V. (eds). (2014, February 25). RDF Schema 1.1. W3C.
Retrieved from http://www.w3.org/TR/2014/REC-rdf-schema-20140225/
Dean, J. &
Ghemawat, S. (2008). Mapreduce: simplified data processing on large clusters.
Communications of the ACM 51(1), 107–113.
Ghemawat, S.,
Gobioff, H. & Leung, S.T. (2003). The google file system. in: proc. sosp,
pp. 29–43.
Sakr, S., &
Gaber, M. (Eds.). (2014). Large scale and big data: processing and
management. Boca Raton, FL: CRC Press.
W3C (The World
Wide Web Consortium). (2004). Resource description framework:
concepts and abstract syntax, W3C recommendation.
Schatzle, A.,
Przyjaciel-Zablocki, M., Dorner, C., Hornung, T. & Lausen, G. (2012).
Cascading map-side joins over HBase for scalable join processing. Retrieved
January 29, 2017 from http://ceur-ws.org/Vol-943/SSWS_HPCSW2012_paper5.pdf
Schatzle, A.,
Przyjaciel-Zablocki, M. & Lausen, G. (2011). Pigsparql: mapping sparql to
pig latin. Retrieved January 31, 2017 from
http://www.csd.uoc.gr/~hy561/papers/storageaccess/largescale/PigSPARQL-%20Mapping%20SPARQL%20to%20Pig%20Latin.pdf
