SPARQL Bottom Up Semantics

From Blazegraph
Jump to: navigation, search

Understanding SPARQL’s Bottom-up Semantics

Preface: In the 1.5.2 release we’ve implemented a couple of fixes regarding issues related to SPARQL’s bottom-up evaluation approach and associated variable scoping problems. If you encounter regressions with some of your queries after upgrading to 1.5.2, this Wiki page may help you identify ill-designed queries that are not in line with the official SPARQL 1.1 semantics .

While the wiki page SPARQL_Order_Matters discusses implications of SPARQL's "as written" ordered evaluation semantics, another tricky aspect in SPARQL is it's bottom-up evaluation semantics. Informally speaking, bottom-up evaluation means that subqueries and nested groups are (logically) evaluated first. As a consequence, actual evaluation order chosen by SPARQL engines must yield the same results as bottom-up evaluation order in order to be valid.

Blazegraph does not actually use bottom-up evaluation normally. Instead, Blazegraph prefers to reorder joins and join groups in order to reduce the amount of data read and the size of the intermediate solutions flowing through the query using what is known as left-deep evaluation. However, some queries can only be evaluated by bottom-up plans. Bottom-up plans are often much less efficient. However, bottom-up evaluation can be required if some variables are not visible in some intermediate scopes such that more efficient left-deep plans can not be used.

This guide will help you understand why, how to recognize when bottom-up evaluation semantics are being used and what you can do to avoid the problem and get more performance out of the your SPARQL queries. It also sketches Blazegraph's built-in optimization techniques for efficiently dealing with issues induced by SPARQL's bottom-up semantics.

A Simple Example - the Basic Idea of SPARQL Evaluation

Let’s start out with a very simple dataset that we will use throughout the upcoming examples:

 <http://example.com/Alice>   a <http://example.com/Person> .
 <http://example.com/Flipper> a <http://example.com/Animal> .

This is, we have two triples, one stating the Alice is a person and the other one stating that Flipper is an Animal. To illustrate the basic idea of SPARQL evaluation, let’s start out with a simple query:

 SELECT ?s ?personType WHERE {
   BIND(<http://example.com/Person> AS ?personType)
   ?s a ?o
   FILTER(?o=?personType)
 }

The query binds the URI <http://example.com/Person> to variable ?personType and extracts all instances of this type. Naively following the W3C’s semantics, evaluation of this triple pattern proceeds as follows:

1. Evaluate the BIND expression, which gives us a single, so-called mapping:

 { ?personType -> <http://example.com/Person> }

2. Evaluate the triple pattern ?s a ?o against the data, which gives us two mappings, namely

 { ?s -> <http://example.com/Alice>,   ?o -> <http://example.com/Person> },
 { ?s -> <http://example.com/Flipper>, ?o -> <http://example.com/Animal> }

The interesting point here is that, when strictly following the semantics as defined by the W3C, this pattern is evaluated independently from the previous expression, the join is performed in a subsequent step (see 3. below). This is, of course, not a very efficient approach - and as discussed previously Blazegraph for this reason chooses to “inject” the binding obtained from 1. into the triple pattern, evaluating the pattern ?s a <http://example.com/Person> instead.

3. The two partial results are then “joined” together, combining those mappings that do not carry "contradicting" information in the form of conflicting variable bindings. In our case, the mapping from 1. joins with both mappings from 2., essentially computing the cross product. The join thus gives us the following two mappings:

 { ?s -> <http://example.com/Alice>,   ?o -> <http://example.com/Person>, ?personType -> <http://example.com/Person> },
 { ?s -> <http://example.com/Flipper>, ?o -> <http://example.com/Animal>, ?personType -> <http://example.com/Person> }

4. In the next step, we apply the FILTER expression, retaining those mappings for which variable ?o and ?personType coincide, namely

 { ?s -> <http://example.com/Alice>, ?o -> <http://example.com/Person>, ?personType ->  <http://example.com/Person> }

Note that, as defined in the SPARQL standard, FILTER expressions are applied after evaluating a join group, so we could safely move the FILTER expression right in the beginning without changing the evaluation process (and hence, without changing the result)

5. Finally, as per SELECT clause, we project on variables ?s and ?personType to get the final query result. Written in tabular form, here’s the outcome:

 ?s                         | ?personType
 --------------------------------------------------------
 <http://example.com/Alice> | <http://example.com/Person> 

A Problematic Case: FILTER expressions

Nested Subgroups

As you may know, SPARQL allows to nest expressions into subgroups. Let’s now modify our example and look at the following query:

 SELECT ?s ?personType WHERE {
   BIND(<http://example.com/Person> AS ?personType)
   {
     ?s a ?o
     FILTER(?o=?personType)
   }
 }

The only change here are the { } brackets - they put the triple pattern and the FILTER expression into a separate, nested group. Now the bottom-up evaluation of SPARQL becomes relevant, since the inner group is evaluated as a whole, as an isolated group - and this changes the outcome of the query, as discussed next:

1. Evaluate the BIND expression, which gives us the mapping (as before):

 { ?type -> <http://example.com/Person> }

2. We next turn towards an evaluation of the subgroup that is enclosed by the inner { } brackets - following a bottom-up paradigm, this evaluation is done independently from the result computed in 1. 2a. As before in step 2., we evaluate the triple pattern “?s a ?o” against the data, which gives us two mappings, namely

 { ?s -> <http://example.com/Alice>,   ?o -> <http://example.com/Person> },
 { ?s -> <http://example.com/Flipper>, ?o -> <http://example.com/Animal> }

2b. Now, the FILTER (?o=?type) is applied on the two mappings from 2a. And here’s the problem: these two mappings do not contain a binding for variable ?type (because it is not in scope). In such cases, the SPARQL semantic defines that the FILTER condition evaluates to an “error”, in which case the FILTER rejects all mappings. After step 2, we thus end up with no mapping.

3. Finally, the single mapping from 1. is joined with the empty result from 2., so we end up with the empty result.

SPARQL has a lot of great features, but this is not one of them. To help make people's lives easier we are extending Blazegraph's EXPLAIN feature to also report problems such as this in your queries (see Explain#Explain_Hints for details).

UNIONs

While the query from before may look unnecessarily complex and somewhat constructed, the following example is probably much closer to situations as they might show up in practical applications:

 SELECT ?person ?nonPerson ?type WHERE {
   BIND(<http://example.com/Person> AS ?type)
   {
     ?person a ?o
     FILTER(?o=?type)
   }
   UNION
   {
     ?nonPerson a ?o
     FILTER(?o!=?type)
   }
 }

In this UNION query, the BIND expression is used to introduce a variable binding that is intended to be reused in the two parts of the UNION: the idea is to extract all instances of type <http://example.com/Person> in the first part of the UNION, and all the others in the second part of the UNION.

You may be surprised that this query does not work as expected: the two blocks of the UNION open up new scopes, in which the ?type variable is not known. For the same reasons as in the example before, both FILTER expression evaluate to error and we end up with the empty result. One way to fix this is by (redundantly) pushing the BIND into the two parts of the UNION:

  SELECT ?person ?nonPerson ?type WHERE {
    {
      BIND(<http://example.com/Person> AS ?type)
      ?person a ?o
      FILTER(?o=?type)
    }
   UNION
   {
     BIND(<http://example.com/Person> AS ?type)
     ?nonPerson a ?o
     FILTER(?o!=?type)
   }
 }

This query will give us results as expected, namely:

 ?person                    | ?nonPerson                      | ?type
 ------------------------------------------------------------------------------------------
 <http://example.com/Alice> |                                 | <http://example.com/Person> 
                            |   <http://example.com/Flipper>  | <http://example.com/Animal> 

Other Problematic Cases: BIND and VALUES

The problem sketched above is not restricted to the usage of variables in FILTER expressions. Similar issues may pop up whenever using variables in nodes that “consume” variables without matching them against the dataset. In particular, using a triple pattern with a variable in an inner scope is not a problem: the variables are matched against the dataset independently from the outside, and will be joined with the outside part at a later point in time. But when using SPARQL 1.1 constructs such as BIND or VALUES clauses, you may run into the same problems as sketched before by means of the FILTER expression. Look at the following query, which aims at extracting all persons (first part of the UNION) and all instances that are not persons (second part of the UNION), including the respective types:

 SELECT ?s ?type WHERE {
   BIND("http://example.com/" AS ?typeBase)
   {
     BIND(URI(CONCAT(?typeBase,"Person")) AS ?type)
     ?s a ?o
     FILTER(?o=?type)
   }
   UNION
   {
     BIND(URI(CONCAT(?typeBase,"Animal")) AS ?type)
     ?s a ?o
     FILTER(?o=?type)
   }
 }

The problem is essentially the same: we bind variable ?typeBase outside. In the inner UNION blocks, we try to bind variable ?type based on ?typeBase - but the latter is not in scope here. Hence, the query returns the empty result.

The same can happen with VALUES clauses, as illustrated by the following variation:

 SELECT ?s ?type WHERE {
   {
     BIND(URI(CONCAT(?typeBase,"Person")) AS ?type)
     ?s a ?o
     FILTER(?o=?type)
   }
   UNION
   {
     BIND(URI(CONCAT(?typeBase,"Animal")) AS ?type)
     ?s a ?o
     FILTER(?o=?type)
   }
 } VALUES (?typeBase) { ("http://example.com/") }

Again, ?typeBase (which is bound in the outer VALUES clause) is not visible when computing the BINDs for variable ?type, and hence the query will fail to produce results.

Optimizations in Blazegraph

Strictly following bottom-up semantics when implementing a query engine is typically not a good choice when it comes to evaluation performance. Top-down evaluation, where we inject mappings from previous evaluation steps into subsequent subgroups, can lead to significant speedups. The good news is that, for a broad range of SPARQL queries, bottom-up and top-down evaluation coincide. This holds, for instance, for the complete class of SPARQL queries built only from triple patterns connected through “.” (so-called conjunctive queries).

When it comes to Blazegraph, the basic evaluation approach is a top-down approach. For queries where top-down and bottom-up evaluation make a difference, Blazegraph rewrites queries in such a way that their top-down evaluation result coincides with the bottom-up result, where possible (wherever this is not possible, it essentially switches to bottom-up evaluation for that part of the query). There are various techniques and tricks that are implemented in Blazegraph's optimizer for this purpose: in many cases, subgroups can just be flattened out without changing semantics, variables in subgroups that are known to be unbound can be renamed to avoid clashes, etc. With the fixes in 1.5.2 we’ve ruled out various inconsistencies between Blazegraph and the official W3C spec, so if migrate from previous versions to 1.5.2 or later, check your queries for issues similiar in style to those discussed above.

Summary

Although some of the examples above were somewhat artificially designed to illustrate the issues arising in the context of SPARQL’s bottom-up semantics by means of simplistic examples, we have observed ill-designed queries of this style in practice in both our own applications and in customer applications. We hope that the examples and guidelines in this post help our readers and users to avoid the common pitfalls and write better, standard-compliance SPARQL in the future.