Sesame 2.4.0 with SPARQL 1.1 Query support

I am very proud to announce the release of Sesame 2.4.0. This is a major new release featuring support for SPARQL 1.1 Query.

Sesame 2.4.0 implements all features of SPARQL 1.1 Query as outlined in the October 14 W3C Working Draft, with the exception of basic federated query. SPARQL 1.1 for Sesame is developed by Ontotext in cooperation with Aduna.

The list of new SPARQL query features includes:

• Use of expressions in the SELECT clause
• Aggregates (COUNT, MIN, MAX, AVG, SUM, GROUP_CONCAT), HAVING and GROUP BY
• Property paths
• Subqueries
• Negation: (NOT) EXISTS and MINUS
• Set membership: (NOT) IN
• Conditionals: IF
• Various new builtin functions: COALESCE, BNODE, IRI, isNumeric, strLang, strDt

Apart from this impressive array of new query language features, Sesame 2.4.0 also implements a number of bug fixes and improvements, including scalability and performance improvement in the Native store. For a full overview, see the release notes.

SPARQL 1.1 Query: negated property sets and the algebra

I've just finished the implementation of SPARQL 1.1 property paths in Sesame. The major thing still missing was the implementation of negated property sets.

Negated property sets enable you to formulate a query like, for example: "give me back two resources x and y which are related in any direction via some property, but not via foaf:knows". In SPARQL 1.1, this would look like:

   SELECT ?x ?y
   WHERE { 
           ?x !(foaf:knows|^foaf:knows) ?y .
   }

The current SPARQL 1.1 draft defines a new abstract symbol for supporting negated property sets, called NegatedPropertySet. The SPARQL algebra, in turn, maps this abstract symbol directly to a new algebraic operator, so the algebra is extended with an additional operator in order to support negated property sets, and it also gives a specific evaluation semantics for this new operator.

However, although perhaps useful in terms of brevity, it is in fact not necessary to thus extend the algebra. Negated property sets do not actually introduce additional expressivity to the language (in contrast to, for example, arbitrary-length property paths): the above query could have been formulated in SPARQL 1.0:

   SELECT ?x ?y
   WHERE { 
       { ?x ?p1 ?y . FILTER (?p1 != foaf:knows) }
       UNION
       { ?y ?p2 ?x . FILTER (?p2 != foaf:knows) }
   }

This simple fact makes it possible to implement negated property sets without having to extend Sesame's query model with an additional algebra operator. The advantage of this is that all of Sesame's existing query optimizing/rewriting/evaluation strategies can immediately handle negated property sets, without having to be 'recalibrated' or indeed extended to take a complex additional operator into account.

So, the SPARQL parser processes a negated property set and translates it to the necessary collection of Joins, Filter comparisons and Unions. The algorithm is roughly as follows:

 let NPS be a negated property set with elements e_1...e_n.
 let s be the subject variable of the NPS.
 let ap be the (anonymous) predicate variable of the NPS.
 let O be the set of object variables of the NPS. 
 let F and F_i be two sets of filter conditions.
 let p(e) be the predicate IRI of e.

 for each e in NPS :
    create a filter condition f: p(e) != ap .
    if e is inverted: add f to F_i, otherwise add f to F .
 
 let J be a Join on basic graph patterns. 
 if F is not empty:
    for each o in O :
       add BGP(s, ap, o) to J .

 let I be a Join on basic graph patterns. 
 if F_i is not empty:
    for each o in O :
       add BGP(o, ap, s) to I .
 
 if I and J are both not empty:
    return Union(Filter(J, F), Filter(I, F_i)) .
 else if I is not empty :
    return Filter(I, F_i).
 else if J is not empty :
    return Filter(J, F).

The end result of applying this algorithm to the example SPARQL 1.1 query we saw above would be the following (slightly adapted for readability) Sesame query algebra expression:

Projection({x, y}, 
   Union(
      Filter(StatementPattern(y, ap, x), Compare(!=, ap, foaf:knows)),
      Filter(StatementPattern(x, ap, y), Compare(!=, ap, foaf:knows))
   )
)

Short and sweet. Of course, it gets less short and sweet when using more complex property sets, or property sets in combination with other property path features, but the algorithm caters to that. Such more complex expression just result in a larger set of unions and joins.

Notes on evaluating arbitrary-length property paths

I have more or less finished implementing parsing and basic evaluation for SPARQL 1.1 property paths in Sesame. The only thing still missing is negated property sets. Negated sets of properties... Who the heck wants that? Honestly.

Anyway. Apart from the fact that the property path syntax is not quite simple to parse, there are some concepts involved which make evaluation of property-paths tricky - especially if arbitrary-length paths are involved.

Arbitrary-length paths are paths specified with a '+' or '*' modifier. For example, the path ?x foaf:knows+/foaf:name ?name specifies a match where either ?x knows someone with name ?name, or knows someone who knows someone with name ?name, or ... you get the point. The trouble with such queries in 'traditional' evaluation is that there is no a-priori length: you can not simply use the SPARQL parser to build a set of joins.

A path of fixed length n will usually be translated by the parser to n-1 joins on individual statement patterns. In order to allow evaluation of non-fixed length paths, we need something that amounts to graph traversal. Fortunately, Sesame's default evaluation strategy (essentially lazy iteration over bindings) is well suited for this task. What I have done is the following:

1. the SPARQL parser translates an arbitrary-length property path to a new algebra operator, called (rather appropriately I thought) ArbitraryLengthPath.
2. the default EvaluationStrategy for such an operator is based on a dynamically expanding iterator, which creates new joins while being evaluted.

Effectively, this new iterator (called PathIteration, currently located as an inner class in the EvaluationStrategyImpl) implements a depth-first graph traversal strategy. It reports back results iteratively and expands the path sequence length (using an ever-increasing iterative creation of nested joins) until it reaches a length at which the nested join no longer produces any matches. Cycle-detection is implemented by the simple expedient of adding an boolean comparison operator (NEQ) on top of our join: if the start node of the path has the same value as the end node, we have a cycle.

Sesame 2.4.0-alpha1 released, with SPARQL 1.1 Query support

I'm very pleased to announce a first test release of Sesame with SPARQL 1.1 support: Sesame 2.4.0-alpha1. This first alpha-release of Sesame 2.4 contains support for various SPARQL 1.1 Query features as specified in the current SPARQL 1.1 Query Working Draft. The implementation of SPARQL 1.1 in Sesame is led by Ontotext.

The list of features includes:

• Use of expressions in the SELECT clause.
• Use of aggregates (COUNT, MIN, MAX, AVG, SUM)
• Use of HAVING and GROUP BY
• Use of Subqueries
• Negation: (NOT) EXISTS and MINUS
• Set membership: (NOT) IN
• Various new builtin functions: COALESCE, BNODE, IRI, isNumeric, strLang, strDt
• Partial support for property paths. Current support includes path sequences (/), path alternatives (|), zero or one matches (?), specific numbers of occurrences ({n, m}), and inverted properties (^). Not yet supported are arbitrary-length paths (+ and * wildcards) and negated properties (!).

As this is an alpha release we advise you to use it for testing and evaluation purposes only. We are actively looking for your feedback in terms of bug reports and other problems you may encounter. We'd love to hear your comments! Please send your feedback to the sesame-general mailinglist.

In other news, the OpenRDF.org website has been given a fresh coat of paint and a good update. I'm sure Arjohn will be pleased to hear your feedback. Take a look, and fill in the survey.

Implementing SPARQL 1.1 Query - first findings

I am currently in the middle of implementing SPARQL 1.1 Query Language into Sesame 2 (code can be found in Sesame's subversion repository, branch 2.4). The current working draft specifies a number of new features for SPARQL, and I will briefly make some points about the features I have implemented thus far, noting problems I encountered or where the current working draft was unclear to me.

1. Expressions in SELECT

This new feature was fairly straightforward to implement, mainly as Sesame already had support for it in its query algebra. I only needed to adapt the parser.

2. Negation

In section 8 two additional operators are introduced, both of which can be used to express negation. They are (NOT) EXISTS, and MINUS. Implementation of the EXISTS function again was quite straightforward, Sesame already having algebraic support for it.

The definition of MINUS in SPARQL gave me some headaches, however. In Sesame's native query language SeRQL, the MINUS operator is a set operator operating on collections of triples - that is, the result of {A} MINUS {B} is the set of all triples matching A, minus all triples matching B. In SPARQL, however, MINUS is defined in terms of  compatible solutions. This means that Sesame's own algebra operator for MINUS can not simply be reused for SPARQL. However, it also seems that SPARQL's definition of MINUS makes it, for all practical purposes, exactly equivalent to using a NOT EXISTS filter. To see why this is, we have to take a look at the definitions of both operators.

In section 8.3 , the difference between NOT EXISTS and MINUS is explained, with a number of examples. This explanation shows that when the right-hand side pattern shares no variables with the left-hand pattern, the outcome is different. However, what is also apparent from this explanation that when a MINUS operator is used and no shared variables exist between the two patterns, the MINUS operator effectively does nothing.

This also follows if we look at  the definition of MINUS in the SPARQL algebra and the definition of compatible solutions in section 17.3: by definition any two solutions µ and µ' which share no variables v are compatible. So the outcome of any such query would be exactly the same as if the MINUS were not there. This leaves us with two scenarios:

1. the two patterns share a variable, in this case the MINUS can be replaced with a NOT EXISTS;
2. the two patterns do not share a variable, in this case the MINUS can be ignored.

All in all it seems to me that MINUS as currently defined does not add additional expressivity to the language and is only a syntactic variant. If that is intended, that might be useful to clarify in the working draft.

3. Subqueries

Sesame already having basic support for this in the algebra, again this was rather simple to add, as it only required me to tweak the SPARQL parser. I will probably need to test it further though.

4. Aggregates

Fortunately for me, it turns out that basic support for aggregate functions had been added to Sesame's algebra earlier, courtesy of David Huynh. It required a bit of tweaking to be compatible with SPARQL's definitions, but the framework was already there, ready for me to extend.

There are a number of things unclear in the working draft however, regarding the expected behaviour of aggregate functions.

The first problem has to do with datatypes. Most examples take it as given that all input to, say, a SUM operator will be numeric values. It is not clearly stated what the expected behaviour is if a particular variable binding turns out to be non-numeric value. As a case in point, SUM is formally defined in terms of the XPath function op:numeric-add. This function explicitly states that it operates only on specific numeric types. No mention is made however, of expected behaviour when one operand is not a numeric type (section 16.3 of the SPARQL WD does mention that a type error results for incompatible operands, but it is not clear if this also applies to aggregate functions). Moreover, it is not clearly stated how a type error in an aggregate function should influence the result. I can see a number of possible scenarios, when a type error occurs during evaluation of an aggregate function:

1. the entire query fails with an error;
2. the incompatible operand value is ignored and evaluation continues;
3. the aggregate operator fails silently, returning 0.

From a usability perspective, I would probably have a preference for option 2, although I note that in other mathematical operators (+, -, *, etc.) Sesame's interpretation currently is that an incompatible operand results in a failed query.

Another problem with the definition of aggregates, or more in general with aggregates in combination with several other features, is that it is not always clearly defined how they should interact (disclaimer: perhaps it is properly defined in section 10.2, but I'm having a hard time following the definitions there). For example, what happens when we apply an ORDER BY on a graph pattern that already has a GROUP BY and an aggregate function? For example, take the following data set:

:org1 :affiliates :auth1, :auth2 .
:auth1 :name "John" .
:auth2 :name "Paul" .
:org2 :affiliates :auth3 .
:auth3 :name "Ringo" .

And the following query:

SELECT (GROUP_CONCAT(?name) AS ?names)
WHERE {
  ?org :affiliates ?auth .
  ?auth :name ?name.
}
GROUP BY ?org
ORDER BY ASC(str(?name))

My intuitive understanding would be that the result of this query would be:

?names     

"Ringo"
"John Paul"

That is: the ordering is applied to the intermediate result of the grouping, thus supplying the aggregate operator (in this case, GROUP_CONCAT) with an ordered sequence (which makes sure that we get a concatenated string "John Paul" rather than "Paul John"). But it is not completely clear to me from the working draft if the ORDER BY clause should be applied to a grouping in this fashion.

These are my findings thus far. I have not yet started on property paths or federated query. In the mean time, I would welcome any feedback on my notes, including feedback that tells me I should have read section so-and-so and it's all clear as glass if I had just taken the time to study it properly :)

Also, this: in the course of this work I have written several DAWG-Manifest style unit tests to check conformance as I saw it. They can be found in Sesame's SVN repository, and I'd be happy to let them be reused.

Back to working on Sesame

Ontotext, the Bulgarian Semantic Web company of OWLIM fame, have given me the opportunity to return to working on Sesame as a developer. Specifically, I have been contracted to help implement SPARQL 1.1 Query and Update into the Sesame framework.

Work has already started and I'm happy to report that various features have already been implemented and tested - the fact that Sesame's query algebra is based on the SeRQL language helps a lot here, as various SPARQL 1.1 features were already available in SeRQL. This includes the use of expressions in the SELECT, as well as negation features and subqueries. More challenging will be the inclusion of aggregates and property paths. More soon.

SWC 0.10 - OWL Reasoning support

Anton and I have just released version 0.10 of SWC, the Sesame Windows Client. The main new feature of this release is support for OWL reasoning.

The Sesame Windows Client now includes the latest version of Ontotext's SwiftOWLIM store, a high-performance in-memory store and OWL reasoner. SWC allows you to create a local SwiftOWLIM store like any other Sesame repository, with the added advantage that it supports OWL semantics. OWL reasoning made easy!

Also, we have made a number of improvements in the performance of data upload and data export, as well as several minor changes in the UI.

Next steps in the development of SWC are: adding support for other triplestores that have a Sesame API bridge (including Virtuoso and AllegroGraph), as well as improving the SPARQL endpoint support (by allowing additional parameters to be set). And oh yeah, we're still looking for a good new name for the SWC...

Semantic Mediawiki Conference (SMWCon) Fall 2010

I just came back from an exhausting but highly inspirational 2 days of talks and demos about Semantic Mediawiki and various extensions and use cases: SMWCon Fall 2010 (hosted at the Open University in Amsterdam).

Some of my personal highlights (in no particular order):

• Semantic Maps as presented by Jeroen de Dauw. This was a bit of an eye-opener, as I had previously briefly thought about using something like this, but decided it wouldn't be worth the bother if it involved having to type in a lot of coordinates.
  Well guess what, you don't have to: it provides full geocoding functionality, effectively allowing you just to type in a street address. It ties in with Google maps as well as Open StreetMaps, Yahoo maps and OpenLayers. Overall it looks just massively useful.
• WikiTags by Jesse Wang: a very impressive demo on how to link the world of (semantic) wikis to the world of MS Office. Automated annotation of terms in MS Word, live links between Outlook and the wiki, quick and easy adding of e-mail messages to the wiki, etc. etc. The thought behind this effort appeals to me: don't rage against the machine but accept that MS Office tools are the daily working environment for many people and organisations, and cater to that.
• The Suite of Halo extensions presented by Daniel Hansch: although I was already aware of the Halo extensions I had not yet completely grokked the full range of features and improvements it encompasses. In particular its support for fine-grained access control is something that captured my attention. On the ToDo list to take for a test drive.
• SparqlExtension by Alfredas Chmieliauskas and Chris Davis: particularly impressive about this demo was the way in which this extension enables integration of (RDF) data from many different sources and creating all sorts of reportings on that data. Can't wait to tweak this one to talk to a Sesame server and start testing it on our internal group wiki.
• Rudi van Bavel and Michael Cariaso both showed very interesting stuff involving the creation, maintenance and use of SNPedia, a wiki containing huge amounts of human genetic data.

To be honest, though, I found all presentations and demos, not just the ones mentioned above, interesting and engaging. The atmosphere throughout the two days was positive and pragmatic, with lots of interesting group discussion going on. It was great to see people from so many different background coming together to share experiences and show new and innovative ways in which the SMW platform can be used and extended.

SWC 0.9 released: out-of-the box triplestore and SPARQL query library

Hot on the heels of the previous SWC release comes another major update of the Sesame Windows Client. Version 0.9 has a whole range of useful new features and improvements: 

• You can now create and use local repositories (many thanks to the IKVM developers and Enrico Minack for making this possible);
• "My Query Book" allows you to save and reuse your favorite SPARQL queries;
• You can now open the result of a SPARQL SELECT query in a new (paged) window;
• You can now directly save the result of a SPARQL SELECT query as comma-separated values, XML, or JSON;
• Your most recently used server URLs are now remembered;
• Autocompletion when typing in a server URL.

The use of local repositories means that you can use the SWC as a quick and easy RDF triplestore. Create a new store, add your RDF data, and start querying. No need to install a separate triplestore server.

Query Book screenshot (click to enlarge)

The Query Book allows you to not only save your queries, but also to document them. This way, you can quickly create a library of useful SPARQL queries and document not only what they do, but also on which repository or SPARQL endpoint the query is most likely to give a useful result. The Query Book's search feature makes sure that even in a large library you can still easily find back any query.

Another new feature is the opening of a SPARQL SELECT query result in a new (paged) window. What is especially useful about this is that you can now execute one query, keep the result in a separate window, and then execute another query and compare its result with the previous one.

If you want to save the result of a SPARQL query, you can now do so, in a choice of three formats: comma-separated values (CSV), which is useful for import in e.g. Excel, is the default choice, but the official SPARQL Query Results XML format and the SPARQL JSON format are also suppported.

Both Anton and I are quite happy with this new release, and hope you find it useful as well. As always, the new release can be found on the  project homepage on Sourceforge.

Sesame 2 Windows Client - or is that SPARQL Windows/Linux Client?

I've just released a new version of the Sesame 2 Windows Client. Thanks to a new co-developer, Anton Andreev (of OntoText), the SWC tool is now a full-fledged SPARQL client: it can connect to any SPARQL endpoint, not just Sesame servers.

Apart from this new feature, the tool also has a couple of other improvements:

• context information fetching can now be disabled when connecting to large repositories;
• namespace clauses can now be automatically generated, based on the prefixes used in the query.

The only problem with this new release is that the name of the tool is now even more of a mismatch. Not only is the Sesame 2 Windows Client not just for Windows (it also runs on Linux under Mono), but now it is also not just for Sesame. A free drink to whoever suggests a good new name!

As always, the new release can be found on the  project homepage on Sourceforge. The source code can from now on be found in the Sourceforge SVN repository.

Accessing DBpedia's SPARQL endpoint with Sesame

I'd like to share a tip on using Sesame as a client for SPARQL endpoints. This may be rather trivial to some but perhaps new to others.

We are developing a tool called ROC (Rapid Ontology Construction) (see our paper@ASWC'08), which is a tool that allows domain experts to quickly build a basic vocabulary for their domain, re-using existing terminology whenever possible. How this works is that the ROC tool asks the domain expert for a set of keywords that are 'core' terms of the domain, and then queries remote sources for concepts matching those terms. These are then presented to the user, who can select terms from the list, find relations to other terms, and expand the set of terms and relations, iteratively. The resulting vocabulary (or 'proto-ontology', basically a SKOS-like thesaurus) can be used as is, or can be used as input for a knowledge engineer to base a more comprehensive domain ontology on.

ROC is developed on top of Sesame, and up until now we simply supplied the tool with 'remote sources' by adding data to a locally running Sesame repository. In order to act with the LOD cloud, we obviously needed something a bit less awkward, so I started looking into ways to extend the functionality to be able to query linked open data.

Fortunately, I didn't have to look far, because Sesame actually already supports this: Sesame's client server protocol is a superset the SPARQL protocol. This I already knew, but what I hadn't yet tried was to see if that meant you could use Sesame's client libraries to query any SPARQL endpoint (instead of just connect to a remote Sesame server, which is what it is primarily designed for, after all). And guess what, it turns out that you can!

Here's a bit of code that connects to DBPedia's SPARQL endpoint and fires a query. The idea is simply to reuse Sesame HTTPRepository class, supply the endpoint URL as the server, and specify no repository:

String endpointURL = "http://dbpedia.org/sparql";
HTTPRepository dbpediaEndpoint = 
         new HTTPRepository(endpointURL, "");
dbpediaEndpoint.initialize();

RepositoryConnection conn = 
         dbpediaEndpoint.getConnection();
try {
  String sparqlQuery = 
         " SELECT * WHERE {?X ?P ?Y} LIMIT 10 ";
  TupleQuery query = conn.prepareTupleQuery(SPARQL, query);
  TupleQueryResult result = query.evaluate();

  while (result.hasNext()) {
      ... // do something linked and open
  }
}
finally {
  conn.close();
}

Now, I'm perhaps easily impressed, but to me this was beautifully easy. This makes integrating arbitrary linked open data in most of our Sesame-based tooling (including ROC) completely painless.

Sesame 2 progress

Hofstadter's Law states that anything takes longer than you expect, even if you take Hofstadter's Law into account. I guess the development path of Sesame 2 is a textbook example of this principle in action.

On the bright side though, we are making good progress. The last alpha release was already shown to be quite mature. The next release will definitively freeze the APIs (and be called beta1). Real Soon Now. Honest.

The query algebra in Sesame 2 is IMHO an interesting piece of work: it allows us to map both SPARQL and SeRQL to an algebraic representation of a query. Query evaluation strategies can then ignore the specifics of the query syntax and just concentrate on manipulating the algebraic expression. Thanks to David Huynh, the object model has now been extended with operators for aggregate operations as well. This has not been fed back into the actual query languages yet, so that remains a ToDo.

I'm also quite pleased with they way in which the APIs have developed. It has taken several thinks and rethinks but the current way in which a user communicates with Sesame is both powerful and easy to use. The web client app is finally taking shape as well (I hope to show that in action soon).

We've also learned a lot about managing an (open source) project in the past few months. Our development environment has undergone some drastic changes: we switched from sourceforge CVS to our own SVN server, and we have started using maven to handle project management. Sesame is no longer a monolothic project but instead consists of about 33 modules, each of which can be checked out and edited separately. Sounds convoluted but it has a number of advantages, including the fact that we can very easily manage dependencies between different versions of parts of the code, and have made a very clear distinction between apis and implementations. This makes the whole framework a lot more extensible, flexible, and reusable. Which is sort of the point of a framework of course :)