PaperlayerView exact revision on arXiv

Source-linked AI summary

S2RDF: RDF Querying with SPARQL on Spark

Alexander Schätzle, Martin Przyjaciel-Zablocki, Simon Skilevic, Georg Lausen

arXiv:1512.07021v3cs.DBcs.DC

TL;DR

Large, diverse RDF collections require distributed querying, but existing Hadoop-based systems can favor particular query shapes. S2RDF uses Spark and the semi-join-based ExtVP schema to reduce query input across patterns, outperforming prior systems on WatDiv while achieving sub-second runtimes for most billion-triple queries.

  • Problem

    Growing RDF collections require distributed storage and processing, while existing Hadoop-based approaches often favor particular query shapes.

  • Method

    S2RDF compiles SPARQL to Spark SQL and uses ExtVP, a semi-join-based relational schema that precomputes reductions for possible join correlations.

  • Results

    S2RDF outperforms centralized and distributed SPARQL processors by an order of magnitude on average across query shapes and achieves sub-second runtimes for most billion-triple benchmark queries.

  • Takeaways & Limitations

    ExtVP’s performance does not depend on query diameter, and a selectivity threshold of 0.25 retains 95% of best runtime improvements using 25% of table tuples and storage size.

  • Takeaways & Limitations

    ExtVP requires significantly more time to load because of its many semi-join operations, although loading is a one-time task.

Abstract

from arXiv · show

RDF has become very popular for semantic data publishing due to its flexible and universal graph-like data model. Yet, the ever-increasing size of RDF data collections makes it more and more infeasible to store and process them on a single machine, raising the need for distributed approaches. Instead of building a standalone but closed distributed RDF store, we endorse the usage of existing infrastructures for Big Data processing, e.g. Hadoop. However, SPARQL query performance is a major challenge as these platforms are not designed for RDF processing from ground. Thus, existing Hadoop-based approaches often favor certain query pattern shape while performance drops significantly for other shapes. In this paper, we describe a novel relational partitioning schema for RDF data called ExtVP that uses a semi-join based preprocessing, akin to the concept of Join Indices in relational databases, to efficiently minimize query input size regardless of its pattern shape and diameter. Our prototype system S2RDF is built on top of Spark and uses its relational interface to execute SPARQL queries over ExtVP. We demonstrate its superior performance in comparison to state of the art SPARQL-on-Hadoop approaches using the recent WatDiv test suite. S2RDF achieves sub-second runtimes for majority of queries on a billion triples RDF graph.

1. INTRODUCTION

RDF’s massive growth creates a need for distributed processing, but existing approaches face interoperability or query-shape limitations. S2RDF addresses this with Spark-based execution and ExtVP, a relational partitioning schema designed to reduce query input across diverse patterns.

  • Billions of RDF triples make single-machine storage and processing increasingly infeasible, while diverse graph structures complicate distributed querying.
  • Shared Big Data infrastructures such as Hadoop offer common storage for querying, data mining, and machine learning, unlike closed standalone RDF stores.
  • S2RDF combines Spark’s in-memory cluster computing with a relational interface for executing SPARQL queries.
  • ExtVP uses semi-join reductions to account for join correlations, exclude unnecessary data, and support query shapes regardless of diameter.
  • The system compiles SPARQL into Spark SQL, uses table statistics for table selection, and is evaluated against diverse WatDiv workloads.

2. FOUNDATIONS

This section introduces RDF triples and SPARQL basic graph patterns, whose structural diversity affects query performance. It also presents Spark’s distributed, in-memory execution model and relational DataFrame interface.

  • 2.1 RDF & SPARQL: RDF represents statements as triples that form a directed labeled graph, while SPARQL matches graph patterns against RDF data.
  • 2.1 RDF & SPARQL: A BGP returns a bag of solution mappings produced by merging compatible mappings from its triple patterns.
  • 2.1 RDF & SPARQL: SPARQL BGPs vary in shape and diameter, with star patterns common and query structure strongly affecting performance.
  • 2.2 Spark: Spark distributes fault-tolerant datasets across cluster machines and executes data-parallel workloads on Hadoop data sources.
  • 2.2 Spark: Spark SQL provides a relational interface whose DataFrames are distributed rows with a common schema, analogous to database tables.

3. RELATED WORK

Related systems span centralized RDF stores, federations, and cloud-based Big Data platforms. Their differing partitioning and execution strategies expose trade-offs involving locality, duplication, scalability, and workload specialization.

  • RDF systems include centralized and distributed designs backed by relational, NoSQL, or RDF-specific storage subsystems.
  • 3.1 Centralized Systems: Centralized RDF systems use relational mappings, exhaustive indexes, bit matrices, or compact triple structures to accelerate query processing.
  • 3.2 Distributed Systems: Standalone distributed stores dedicate their own infrastructure to RDF processing, whereas federation approaches distribute data and subqueries across centralized stores.
  • 3.2 Distributed Systems: Graph-based federation can improve query locality through overlapping partition borders, but centralized partitioners such as METIS have limited scalability.
  • 3.3 Cloud Infrastructures: Cloud-infrastructure approaches reuse shared Hadoop storage and processing, including systems based on subject grouping, vertical partitioning, or clustered indexes.

4. RELATIONAL MAPPINGS FOR RDF

Relational RDF mappings trade representation simplicity, input reduction, and join savings. Triples tables are flexible but scan-heavy, while vertical partitioning narrows access to predicate-specific tables.

  • 4.1 Triples Table: A triples table stores every RDF statement as one row with subject, predicate, and object columns.
  • 4.1 Triples Table: Mapping Q1 over a triples table references the table four times and can require scans over the whole dataset.
  • 4.1 Triples Table: Distributed triples-table processing is hindered because Hadoop frameworks provide limited support for maintaining rich indexes.
  • 4.2 Vertical Partitioning: Vertical partitioning creates a two-column table for each predicate, allowing predicate-bound triple patterns to access smaller candidate sets.

Triples Table

Vertical partitioning organizes RDF data into predicate-specific tables, allowing query mappings to select relevant partitions. Property tables reduce joins for star-shaped patterns but can be ineffective for linear-shaped patterns and introduce duplication for multi-valued predicates.

  • Vertical Partitioning: Vertical partitioning uses separate two-column tables for predicates, such as follows and likes.The corresponding SPARQL-to-SQL mapping selects the predicate-specific tables directly.
  • Vertical Partitioning: Predicate-specific partitions mimic an index and are manageable in distributed Hadoop environments.However, some partitions can represent a large share of the graph and cause substantial I/O.
  • Vertical Partitioning: Selective queries may still shuffle unnecessary data that is discarded afterward.This limitation arises when large partitions contain many irrelevant triples.
  • Property Tables: Multi-valued predicates in property tables require auxiliary tables or row duplication.The follows and likes example uses row duplication to represent multiple values.
  • Property Tables: Property tables group predicates into one table and reduce subject-subject self-joins for star-shaped query patterns.For Q1, the property-table mapping requires two joins instead of three under triples-table and VP representations.
  • Property Tables: For linear-shaped patterns, property tables provide no real benefit over triples tables and may perform worse.Their advantage is therefore concentrated in star-shaped query workloads.

5. EXTENDED VERTICAL PARTITIONING

ExtVP extends vertical partitioning with semi-join reductions that remove dangling tuples and reduce query input across diverse SPARQL query shapes. It selectively materializes useful correlation tables to balance performance benefits against storage overhead.

  • Design Goals: ExtVP is designed to improve query processing for star, linear, large-diameter, and mixed query shapes rather than favoring one structure.This addresses the shape sensitivity of many existing RDF layouts.
  • ExtVP in a Nutshell: In the running example, ExtVP reduces join comparisons from 12 in VP to one by accessing only tuples guaranteed to find a join partner.The reduced subsets avoid reading and shuffling tuples that would later be discarded.
  • ExtVP Definition: ExtVP extends VP by precomputing semi-join reductions between predicate partitions for relevant subject-subject, object-subject, and subject-object correlations.The schema does not precompute object-object correlations because they often yield little reduction, especially for self-joins.
  • ExtVP in a Nutshell: ExtVP excludes dangling tuples from join inputs, reducing I/O, comparisons, and memory consumption during distributed query execution.The approach targets Spark’s in-memory execution setting, where memory is more limited than HDFS disk space.
  • Storage Optimization: Only nonempty correlation tables that reduce their corresponding VP tables are stored, with a selectivity threshold available to limit storage overhead.Tables equal to VP, empty tables, or tables outside the threshold are not materialized.
  • Storage Optimization: More than 90% of ExtVP tables were empty or equal to VP in experiments, while physical storage including VP was approximately 1.3 times the original N-triples dataset size.For a dataset with approximately 10^9 triples and 86 predicates, the actual logical ExtVP size was approximately 11n.

6. S2RDF QUERY PROCESSING

S2RDF compiles SPARQL algebra into Spark SQL by selecting ExtVP or VP tables for each triple pattern and joining the resulting subqueries. It also optimizes execution order using query structure and table statistics, while some SPARQL optimization remains incomplete.

  • Query Compilation: S2RDF parses SPARQL with Jena ARQ, applies basic algebraic optimizations such as filter pushing, and generates Spark SQL from the algebra tree.The remaining SPARQL 1.0 operators are mapped to corresponding Spark SQL constructs.
  • Table Selection: For each triple pattern, the compiler starts with its VP table and checks SS, SO, and OS correlations to select the candidate table with the smallest SF value.Patterns with variable predicates use the base triples table instead.
  • Query Compilation: The compiler maps bound values to SQL WHERE conditions and variable names to renamed columns, allowing subqueries to be joined using natural joins.Each triple pattern becomes a subquery, and their joins produce the BGP result.
  • Query Execution: If a selected ExtVP table is empty, S2RDF can return an empty result using statistics without executing the full query.This applies when a query contains a correlation between predicates that does not exist in the dataset.
  • Join Order Optimization: Join order is optimized by executing more selective patterns first, avoiding cross joins, and using actual selected-table sizes to join the smallest tables first.The method uses query structure for bound-value ordering and table statistics to refine ordering among similarly bound patterns.
  • Join Order Optimization: In the running example, statistics replace an order that first joins the two largest tables with one that joins the two smallest tables, avoiding a discarded intermediate result.The original mapping can ignore triple-pattern order and produce suboptimal query plans.

7. EVALUATION

The evaluation shows that S2RDF combines strong performance with broad robustness across query shapes and dataset scales, while ExtVP reduces input sizes and supports selective execution. Its main operational trade-off is higher one-time loading cost and additional storage, which thresholding can substantially reduce.

  • Query Patterns: For high-selectivity linear and star queries, ExtVP is approximately four times faster than VP and achieves sub-second runtimes on a billion triples.The reported condition is SF < 0.01 on small inputs.
  • Basic Testing: S2RDF outperforms PigSPARQL and SHARD by several orders of magnitude across all query categories.The comparison attributes this difference to the batch-oriented MapReduce execution used by those systems.
  • Basic Testing: S2RDF is an order of magnitude faster than Sempala on average across all four query categories.For star-shaped queries, ExtVP reduces scan input while Sempala scans its unified property table.
  • Basic Testing: S2RDF outperforms H2RDF+ by at least one order of magnitude on average across all four query categories.H2RDF+ can remain comparable on smaller datasets through centralized merge joins, but larger datasets often force MapReduce execution.
  • Basic Testing: S2RDF answers most benchmark queries in less than a second on a billion-triples RDF graph, regardless of query pattern shape.The evaluation reports superior performance across distributed and centralized RDF stores and consistent performance across query shapes.
  • Incremental Linear Testing: ExtVP can improve performance as query length increases by reducing intermediate results before additional joins are performed.In IL-2, a selected ExtVP table reduces one input from 0.4 ∗|G| to 0.1 ∗|G|, so a longer query can run better despite requiring more joins.

8. CONCLUSION

S2RDF combines Spark-based SPARQL processing with ExtVP, a relational RDF schema that reduces join input for varied query shapes. The evaluation reports strong performance, while future work targets ExtVP’s storage overhead and table count.

  • System and contribution: S2RDF compiles SPARQL to Spark SQL and uses ExtVP to avoid dangling join tuples, reducing query input size across query-pattern shapes.ExtVP precomputes reductions for possible correlations between VP tables using semi-join reductions.
  • System and contribution: ExtVP can use a selectivity threshold to reduce storage overhead while preserving most of its performance benefit.A threshold of 0.25 retains 95% of the best possible runtime improvements while using 25% of table tuples and storage size.
  • Future work: Future work proposes compact bit-vector representations and a strategy to unify ExtVP tables while considering intersections among correlations.These directions are intended to reduce table-size overhead and potentially improve input selectivity.

A.2 Star Queries

The Star Queries workload contains predefined WatDiv cases spanning SPARQL BGP shapes and includes tests designed to examine ExtVP selectivity effects. The supplied cases vary in query size, predicates, joins, and bindings.

  • Query cases: Star-query cases include subject-centered patterns with predicates such as age, familyName, artist, type, description, keywords, and genre.Examples range from four-triple patterns to larger patterns involving homepage, review, purchase, and product relations.
  • Selectivity testing: The workload was defined to test how varying ExtVP selectivity factors affect query performance.The supplied cases include linear examples with different selectivity factors for correlated predicate pairs.

B.1 Varying OS Selectivity

The OS-selectivity cases vary the selectivity of ExtVP tables for subject-object correlations across predicate paths. The examples span reviewer, friendOf, email, age, and jobTitle joins.

  • Predicate-pair cases: The cases vary OS selectivity factors for predicate pairs such as friendOf–email, friendOf–age, and friendOf–jobTitle.The corresponding ExtVP_OS factors are 0.90, 0.50, and 0.05, respectively.
  • Reviewer cases: Reviewer-centered cases use ExtVP_OS selectivities of 0.90 for email and 0.05 for jobTitle.The reviewer VP partition is reported as 0.01 * |G| in both examples.

B.2 Varying SO Selectivity

The SO-selectivity cases vary correlations in the opposite subject-object direction and include two-edge and three-edge paths. The supplied examples range from highly selective relations to factors near one.

  • Two-edge paths: SO selectivity varies across two-edge paths such as reviewer–friendOf, author–friendOf, follows–likes, and reviewer–likes.The listed ExtVP_SO factors include 0.31, 0.04, 0.90, and 0.31, respectively.
  • Highly selective cases: The workload also includes highly selective cases where ExtVP_OS is below 0.01 and ExtVP_SO is 0.96 or 0.80.These cases use likes–trailer and email–faxNumber predicate pairs.
  • Three-edge paths: Three-edge paths test SO correlations such as follows–friendOf–homepage and artist–friendOf–follows.Their listed factors include 1 and 0.05 for the first path, and 0.01 and 0.77 for the second.

B.6 Empty Result Queries

The WatDiv workload includes empty-result linear queries designed to examine S2RDF’s performance as query paths grow. Examples use two- and three-edge paths with semi-join filter factors of zero.

  • Query 8-1 forms a friendOf-to-language path with both reported ExtVP filter factors equal to 0.
  • Query 8-2 extends the path to friendOf, follows, and language, again with both reported ExtVP filter factors equal to 0.
  • The workload tests S2RDF with linear queries whose sizes increase by incrementally adding triple patterns.The queries start at 5 triple patterns and extend to 10.
  • The workload contains user, retailer, and unbound query types.

C.1 Incremental User Queries (Type 1)

The incremental workload evaluates linear user, retailer, and unbound queries by expanding paths from 5 to 10 triple patterns. Query instances progressively add one triple pattern, producing increasingly long path-shaped SPARQL queries.

  • Unbound queries: Unbound queries use fixed path patterns beginning with offers, includes, review, reviewer, and friendOf, then add likes, authorship, follows, homepage, and language.Examples 3-5 through 3-10 show the path growing one triple pattern at a time.
Loading 1512.07021v3…