SPARQL Query Language Implementation Report

This document reflects the tests reported at the time of the transition from SPARQL CR to SPARQL PR, 12 November 2007. For a more recent implementation report, see the periodically updated implementation report.

Summary of Results

This implementation report summarizes results from 14 implementations of the SPARQL Query Language for RDF against the RDF Data Access Working Group's query language test suite. Test results were received in EARL. Each test in the test suite was assigned to one or more facets, representing low-level details of the query language. These facets were matched into eleven high-level features of the query language for the purposes of determining interoperability. The working group examined the coverage of the test suite vis a vis these facets in order to assure that no elements of the SPARQL language were omitted in the test suite.

Note that many facets represent elements common to many queries, such as projecting variables, use of prefixed names, or matching triple patterns. This implementation report takes a conservative view of test failures: a failure of a test that covers five facets of the query language is counted against all five facets, even if it is likely that the implementation correctly implements the more basic of the five facets. Future work may slim down the mapping of tests to facets in order to highlight the particular facets that more complex test cases are intended to test.

The following table shows results from 14 implementations that submitted EARL results. An implementation's score for a particular feature represents the fraction of tests of that feature that the implementation passed. A test is considered associated with a feature is at least one of the test's facets maps into the feature.

The "best 2" column of the table represents the fraction of facets for each feature that are passed by at least two implementations. The presence of 1.00 in every cell in that column indicates that every identified feature of the query language has at least two implementations that successfully pass all tests that contain facets that map onto that feature.

The Working Group identified one feature, the REDUCED query modifier, that is not tested in the test suite. This report contains information on implementations' use of and support for REDUCED.

The REDUCED feature

SPARQL includes the REDUCED keyword, which allows a query processor to return any number of duplicate solutions from one (zero duplicates, as if DISTINCT were given) up to the number of duplicate results that the equivalent query without DISTINCT would produce. Because of this flexibility, the Working Group could not include interoperability tests for REDUCED in the test suite. Instead, the Working Group solicited information on implementations' use of and support for the REDUCED feature:

• From Steve Harris, JXT implementor:

  I use it in two main ways:

  There are ways I can answer certain queries by consulting indexes that get the complete set of values, but not the cardinality. Eg. the top level graph index lets me directly answer SELECT REDUCED ?g WHERE { GRAPH ?g { ?x ?y ?x } }.

  Another way is just to reduce the size of result sets, but maintaining parallelism. When combining results from multiple backend servers the backend machines can all run DISTINCT/REDUCED operations and the results can be concatenated, without having to centrally process the results in order to guarantee DISTINCTness.

• Richard Newman. AllegroGraph implementor:

  I implement ordering and duplicate elimination by collecting results into an in-memory data structure. Ordering requires all results to be collected before beginning output; DISTINCT merely requires collection during streaming.

  Any time you use a query operation that would cause this behavior to be triggered -- for instance, specifying ORDER BY -- it suddenly becomes slightly more expensive to maintain duplicates, just for the sake of correctness.

  REDUCED allows me to avoid tracking those duplicates. I can certainly imagine other areas where it could make life easier for implementations.

  REDUCED also places almost no burden on implementations (as you say, they can just ignore it!), so I wouldn't like it to disappear.

• Benjamin Nowack, ARC:

  • ARC's SPARQL parser allows and parses REDUCED.
  • The query processor treats REDUCED identically to DISTINCT, queries with REDUCED return the same results as if DISTINCT was used instead.

Detailed Results

The following results represent, for each implementation, the fraction of tests passed per facet.

Algae2

AllegroGraph

Anzo - Glitter

ARC

ARQ

cwm

JXT

OpenRDF Sesame

Pellet

Pyrrho DBMS

Rasqal

RDF API for PHP

RDF::Query

RDFLib