Increasing availability of RDF data covering different domains is enabling ad-hoc integration of different kinds of data to suit varying needs. This usually results in large collections of data such as the Billion Triple Challenge datasets or SNOMED CT, that are not just “big” in the sense of volume but also “big” in variety of property and class types. However, techniques used by most RDF data processing systems fail to scale adequately in these scenarios. One major reason is that the storage models adopted by most of these systems, e.g., vertical partitioning, do not align well with the semantic units in the data and queries. While Big Data distributed processing platforms such as the Hadoopbased platforms offer the promise of “unlimited scale-out processing”, there are still open questions as to how best to physically partition and distribute RDF data for optimized distributed processing. In this poster, we present the idea of a semantics-oriented RDF storage model that partitions data into logical units that map to subqueries in graph patterns. These logical units can be seen as equivalence classes of star subgraphs in an RDF graph. This logical partitioning strategy enables more aggressive pruning of irrelevant query results by pruning irrelevant partitions. It also enables the possibility of semantic-query optimization for some queries such as eliminating joins under appropriate conditions. These benefits in addition to appropriate techniques for physically partitioning the logical partitions, translate to improved performance as shown by some preliminary results.
The Resource Description Framework (RDF) has been widely adopted and used to
represent various datasets in many different communities such as government, life
science, and finance, etc. One challenge that arises from this phenomenon is that most
RDF datasets now contain a significant number of various properties and classes, e.g.,
105 distinct properties and classes in DBPedia [
S O :prs1 “a” :prs2 “b” :prs3 “c” :prs4 “e” … … :homepage (:h) S O :prs1 “a.com” :prs4 “e.com” … …
EQ Example Instances of Equivalence Classes [ nmhp ] { (:prs4, [ {“e”}, {e@g.com}, {“e.com”}, {xxx-xxx-xxxx} ] ) } [ nma ] { (:prs2, [ {“b”}, {b@n.edu}, {:u4} ] ),
(:prs3, [ {“c”}, {c@g.com}, {:u1, :u3} ] ) } [ nmha ] { (:prs1, [ {“a”}, {a@g.com, a@n.edu}, {“a.com”}, …] ) } … … (b) types of properties and classes in a dataset. Given a query, matching vertical partitions are selected based on the properties in the graph pattern and then join operations are performed using the partitions. In a sense, this approach allows all vertical partitions corresponding to properties that are not in the query to be pruned out. However, despite this degree of prunability, the joins between “relevant” vertical partitions still incurs some overhead of processing irrelevant data since not all entries the vertical partitions form joined results. For example, consider the star pattern query with properties :name, :mbox, and :homepage. Fig. 1(a) shows the example of the execution plan and partitioned data using the VP-based approach, which results in two join operations. The violet-colored cells denote triples that are not relevant to query, but are processed and discarded during expensive join operations. Furthermore, the vertical partitioning process itself can be challenging for large heterogeneous datasets for multiple reasons. First, it may require the management of a large number file descriptors/buffers (> 105 for DBPedia) in memory during the partitioning process which can be impractical depending on hardware architecture being used. Second, a scalability is a key design objective on Hadoop-based frameworks, but the distributed file system used in Hadoop (or HDFS) does not scale well when there are numerous small files2. Given these challenges, there is a clear need for investigating novel storage and distribution schemes for RDF on scale-out platforms such as Hadoop. 2
Semantics-Oriented Storage Model : SemStorm
In this poster, we build on our previous works (e.g.,[
A Semantics-Oriented Storage Model for Big Heterogeneous RDF Data physically partitioning triplegroups in a semantics-oriented way. By semantics-oriented we mean, partitioning triplegroups into equivalence classes such that all members in an equivalence class are equivalent with respect to queries. This approach enables more aggressive pruning of logical partitions, i.e. equivalence classes than other approaches like the vertical partitioningW. For example, Fig. 2 shows that we select matching equivalence class sets (mecs): [nmha] and [nmhp], which contain all the properties in the example query, i.e. :n,:m, and :h (ignore a type property for now such as tA). All other remaining equivalence classes are pruned out, e.g., [nma] is not selected due to the absence of :h. The mecs sometimes contain extra values, e.g., objects for property :a and :p in [nmha] and [nmhp]. We later filter such values for exact matching results. Another unique advantage of SemStorm is that it enables additional optimizations that are not possible with other approaches, e.g., it may be possible to avoid explicitly materializing rdf:type triples if such triples can be inferred by the label of an equivalence class (the label of an equivalence class can be considered to be the set of properties in that equivalence class). For example, triplegroups under an equivalence class [pubAuthor, rdf:type with Publication] can skip materializations of Publication type triples if a schema file contains a triple “pubAuthor rdfs:domain Publication”. Fig. 2 shows that type triples are not materialized in triplegroup instances such as tg1 and tg2, which are denoted as (tA) for the class A. This optimization can add significant advantages because rdf:type triples tend to be disproportionately larger than other properties for many datasets, e.g., approx. 20% in LUBM datasets. Thus, avoiding their explicit representation reduces the amount of I/Os needed when rdf:type triples need to be processed and may in some cases eliminate the need to perform a join with such properties since it is implicitly captured in the equivalence class representation.
Implementation Issues. Triplegroups can be generated easily using a group-by
operation on a subject field of triples using a single MR job; they are then categorized based
equivalence class and stored in HDFS. Each equivalence class could be mapped into
a physical file, but it is likely that such 1:1 mappings could cause the many file issue
in case that many distinct equivalence classes are generated. To relieve the issue, we
need a heuristic that clusters equivalence classes into a smaller number of files, e.g.,
group equivalence classes that share a specific set of properties and store them together.
We also need to consider building indexes to locate matching equivalence classes from
physical files, e.g., mappings between equivalence class and their offsets in files.
Preliminary Evaluation. We evaluated three types of queries using the LUBM datasets
(450GB, Univ. 20k) on a 80-node Hadoop cluster in VCL3, where each node was
equipped with 2.33 GHz dual core CPUs, 4GB RAM, and 40GB HDD. Hive 0.124 was
selected for the VP approach. Query Q1 retrieves a list of publication authors with
Publication type triples, and Q2 additionally retrieves name (or title) of the publications.
We evaluated two variations of queries, with object field of some non-type triple pattern
bounded (high selectivity, denoted with postfix h), and same query with unbounded
object (low selectivity marked with l). Fig. 3 shows that SemStorm was 3 times faster than
Hive for Q1 because SemStorm can process queries using a Map-only job and save the
disk I/O for all the type triples. The execution time of Hive increased from Q1 to Q2
due to reading additional property relation :name but the execution time of SemStorm
was almost constant because both queries read the same equivalence classes. Finally,
Q3 was a negative query, which produces no answers. While SemStorm determined that
there are no answers (due to no matching equivalence classes) even before launching
the job, Hive executed join operations, producing 0 answer. The details are available in
the project website.5
Related Work. Our approach might be similar with Property Table [
Acknowledgment The work presented in this paper is partially funded by NSF grant IIS-1218277.