2017-02-05

Publishing temporal RDF data as create/delete event streams

Today I wondered about publishing temporal data as create/delete event streams. The events can be replayed by a database to produce state valid at a desired time. Use cases for this functionality can be found everywhere. For example, I've been recently working with open data from company registers. When companies relocate, their registered addresses change. It is thus useful to be able to trace back in history to find out what a company's address was at a particular date. When a company register provides only the current state of its data, tracing back to previous addresses is not possible.

Event streams are not a new idea. It corresponds with the well-known event sourcing pattern. This pattern was used in RDF too (for example, in shodan by Michael Hausenblas), although it is definitely not widespread. In 2013, I wrote an article about capturing temporal dimension of linked data. I think most of it holds true to date. In particular, there is still no established way of capturing temporal data in RDF. Event streams might be an option to consider.

Many answers to questions about temporal data in RDF are present in RDF 1.1 Concepts, one of the fundamental documents on RDF. For start, "the RDF data model is atemporal: RDF graphs are static snapshots of information." Nevertheless, "a snapshot of the state can be expressed as an RDF graph," which lends itself as a crude way of representing temporal data through time-indexed snapshots encoded as RDF graphs. There is also the option of reifying everything into observations, which is what statisticians and the Data Cube Vocabulary do. Alternatively, we can reify everything that happens into events.

Events

Events describe actions on data in a dataset. You can also think about them as database transactions, along with the associated properties. RDF triples are immutable, since "an RDF statement cannot be changed – it can only be added and removed" (source). This is why we need only two types of events:

  1. :Create (addition)
  2. :Delete (retraction)

Events can be represented as named graphs. Each event contains its type, which can be either :Create or :Delete, and timestamps, in particular valid time. Valid time tells us when the event's data is valid in the modelled world. The dcterms:valid property seems good enough to specify the valid time. Events may additionally describe other metadata, such as provenance. For example, dcterms:creator may link the person who created the event data. Encapsulating event's metadata in its named graph makes it self-contained, but it mixes operational data with data about the described domain, so an alternative to worth considering is to store the metadata in a separate graph.

The following example event stream describes that Alice was a member of ACME since 2000, while in 2001 she left to work for the Umbrella Corp, and then returned to ACME in 2003. The example is serialized in TriG, which allows to describe quads with named graphs instead of mere triples. You can use this example to test the queries discussed further on.

@prefix :         <http://example.com/> .
@prefix dcterms:  <http://purl.org/dc/terms/> .
@prefix org:      <http://www.w3.org/ns/org#> .
@prefix schema:   <http://schema.org/> .
@prefix xsd:      <http://www.w3.org/2001/XMLSchema#> .

:event-1 {
  :event-1 a :Create ;
    dcterms:valid "2000-01-01T09:00:00Z"^^xsd:dateTime .

  :Alice org:memberOf :ACME ;
    schema:name "Alice" .
}

:event-2 {
  :event-2 a :Delete ;
    dcterms:valid "2001-01-01T09:00:00Z"^^xsd:dateTime .

  :Alice org:memberOf :ACME .
}

:event-3 {
  :event-3 a :Create ;
    dcterms:valid "2001-01-01T09:00:00Z"^^xsd:dateTime .

  :Alice org:memberOf :UmbrellaCorp .
}

:event-4 {
  :event-4 a :Delete ;
    dcterms:valid "2003-01-01T09:00:00Z"^^xsd:dateTime .

  :Alice org:memberOf :UmbrellaCorp .
}

:event-5 {
  :event-5 a :Create ;
    dcterms:valid "2003-01-01T09:00:00Z"^^xsd:dateTime .

  :Alice org:memberOf :ACME .
}

Limitations

Describing event streams in the afore-mentioned way has some limitations. One of the apparent issues is the volume of data that is needed to encode seemingly simple facts. There are several ways how we can deal with this. Under the hood, RDF stores may implement structural sharing as in persistent data structures to avoid duplicating substructures present across multiple events. We can also make several assumptions that save space. :Create can be made the default event type, so that it doesn't need to be provided explicitly. In some limited cases, we can assume that valid time is the same as the transaction time. For example, in some countries, public contracts become valid only after they are published.

Another limitation of this approach is that it doesn't support blank nodes. You have to know the IRIs of the resources your want to describe.

Since named graphs are claimed for events, they cannot be used to distinguish datasets, as they typically are. Datasets need to be distinguished as RDF datasets. Having multiple datasets may hence mean having multiple SPARQL endpoints. Cross-dataset queries then have to be federated, or alternatively, current snapshots of the queried datasets can be loaded into a single RDF store as named graphs.

Integrity constraints

To illustrate properties of the proposed event representation, we can define integrity constraints that the event data must satisfy.

Union of delete graphs must be a subset of the union of create graphs. You cannot delete non-existent data. The following ASK query must return false:

PREFIX : <http://example.com/>

ASK WHERE {
  GRAPH ?delete {
    ?delete a :Delete .
    ?s ?p ?o .
  }
  FILTER NOT EXISTS {
    GRAPH ?create {
      ?create a :Create .
      ?s ?p ?o .
    }
  }
}

Each event graph must contain its type. The following ASK query must return true for each event:

ASK WHERE {
  GRAPH ?g {
    ?g a [] .
  }
}

The event type can be either :Create or :Delete. The following ASK query must return true for each event:

PREFIX : <http://example.com/>

ASK WHERE {
  VALUES ?type {
    :Create
    :Delete
  }
  GRAPH ?g {
    ?g a ?type .
  }
}

Events cannot have multiple types. The following ASK query must return false:

ASK WHERE {
  {
    SELECT ?g
    WHERE {
      GRAPH ?g {
        ?g a ?type .
      }
    }
    GROUP BY ?g
    HAVING (COUNT(?type) > 1)
  }
}

Querying

Querying over event streams is naturally more difficult than querying reconciled dataset snapshots. Nevertheless, the complexity of the queries may be hidden behind a proxy offering a more convenient syntax that extends SPARQL. An easy way to try the following queries is to use Apache Jena's Fuseki with an in-memory dataset loaded from the example event stream above: ./fuseki-server --file data.trig --update /ds.

Queries over the default graph, defined as the union of all graphs, query what has been true at some point in time:

CONSTRUCT {
  ?s ?p ?o .
}
WHERE {
  # Fuseki uses <urn:x-arq:UnionGraph> to denote the union graph,
  # unless tdb:unionDefaultGraph is set to true.
  # (https://jena.apache.org/documentation/tdb/assembler.html#union-default-graph)
  GRAPH <urn:x-arq:UnionGraph> {
    ?s ?p ?o .
  }
}

Current valid data is a subset of the :Create graphs without the triples in the subsequent :Delete graphs:

PREFIX :        <http://example.com/>
PREFIX dcterms: <http://purl.org/dc/terms/>

CONSTRUCT {
  ?s ?p ?o .
}
WHERE {
  GRAPH ?create {
    ?create a :Create ;
            dcterms:valid ?createValid .
    ?s ?p ?o .
  }
  FILTER NOT EXISTS {
    GRAPH ?delete {
      ?delete a :Delete ;
              dcterms:valid ?deleteValid .
      FILTER (?deleteValid > ?createValid)
      ?s ?p ?o .
    }
  }
}

We can also roll back and query data at a particular moment in time. This functionality is what Datomic provides as the asOf filter. For instance, the data valid at January 1, 2001 at 9:00 is union of the :Create events preceding this instant without the :Delete events that followed them until the chosen time:

PREFIX :        <http://example.com/>
PREFIX dcterms: <http://purl.org/dc/terms/>
PREFIX xsd:     <http://www.w3.org/2001/XMLSchema#>

CONSTRUCT {
  ?s ?p ?o .
}
WHERE {
  GRAPH ?create {
    ?create a :Create ;
      dcterms:valid ?validCreate .
    FILTER (?validCreate < "2001-01-01T09:00:00Z"^^xsd:dateTime)
    ?s ?p ?o .
  }
  MINUS {
    GRAPH ?delete {
      ?delete a :Delete ;
        dcterms:valid ?validDelete .
      FILTER (?validDelete < "2001-01-01T09:00:00Z"^^xsd:dateTime)
      ?s ?p ?o .
    }
  }
}

Event resolution proxy

Manipulation with event streams following the proposed representation can be simplied by an event resolution proxy. This proxy may be based on the SPARQL 1.1 Graph Store HTTP Protocol, which provides a standard way to work with named graphs. However, the Graph Store Protocol doesn't support quad-based RDF formats, so the proxy thus needs to partition multi-graph payloads into several transactions.

The proxy can provide several conveniences. It can prune event payloads by removing retractions of non-existent triples or additions of existing triples, or by dropping complete events if found redundant. It can automatically add transaction time; for example by using BIND (now() AS ?transactionTime) in SPARQL. Simplifying even further, the proxy can automatically mint event identifiers as URNs produced by the uuid() function in SPARQL. No event metadata can be provided explicitly in such case, although some metadata may be created automatically. Event type can be inferred from the HTTP method the proxy receives. HTTP PUT may correspond with the :Create type, while HTTP DELETE should indicate the :Delete type. Additionally, the proxy can assume that valid time is the same as transaction time.

Publishing

Create/delete event streams can be effectively split to batches by time intervals, suggesting several ways of publishing such data. An event stream should be published as an updated append-only quad dump. Additionally, there may be quads dumps of events from shorter periods of time, such as a day or month, to enable more responsive data syndication. Currently valid dataset may be materialized and published as a periodically updated dump. Instead of updating the current dataset in place, it may be published in snapshots. A snapshot from a given date can be used as a basis when replaying events, so that you don't have to replay the whole history of events, but only those that came after the snapshot. Any quad-based RDF serialization, such as TriG or N-Quads, will do for the dumps. Finally, in the absence of structural sharing, the dumps should be compressed to avoid size bloat caused by duplication of shared data structures.

The next challenge is to refine and test this idea. We can also wrap the event streams in a convenient abstraction that reduces the cognitive effort that comes with their manipulation. I think this is something developers of RDF store can consider to include in their products.

2016-10-06

Basic fusion of RDF data in SPARQL

A need to fuse data often arises when you combine multiple datasets. The combined datasets may contain descriptions of the same things that are given different identifiers. If possible, the descriptions of the same thing should be fused into one to simplify querying over the combined data. However, the problem with different co-referent identifiers also appears frequently in a single dataset. If a thing does not have an identifier, then it must be referred to by its description. Likewise, if the dataset's format does not support using identifiers as links, then things must also be referred to by their descriptions. For example, a company referenced from several public contracts as their supplier may have a registered legal entity number, yet its description is duplicated in each awarded contract instead of linking the company by its identifier due to the limitations of the format storing the data, such as CSV.

Fusing descriptions of things is a recurrent task both in intergration of multiple RDF datasets and in transformations of non-RDF data to RDF. Since fusion of RDF data can be complex, there are dedicated data fusion tools, such as Sieve or LD-FusionTool, that can help formulate and execute intricate fusion policies. However, in this post I will deal with basic fusion of RDF data using the humble SPARQL 1.1 Update, which is readily available in most RDF stores and many ETL tools for processing RDF data, such as LinkedPipes-ETL. Moreover, a basic data fusion is widely applicable in many scenarios, which is why I wanted to share several simple ways for approaching it.

Content-based addressing

In the absence of an external identifier, a thing can be identified with a blank node in RDF. Since blank nodes are local identifiers and no two blank nodes are the same, using them can eventually lead to proliferation of aliases for equivalent things. One practice that ameliorates this issue is content-based addressing. Instead of identifying a thing with an arbitrary name, such as a blank node, its name is derived from its description; usually by applying a hash function. This turns the “Web of Names” into the Web of Hashes. Using hash-based IRIs for naming things in RDF completely sidesteps having to fuse aliases with the same description. This is how you can rewrite blank nodes to hash-based IRIs in SPARQL Update and thus merge duplicate data:

In practice, you may want to restrict the renamed resources to those that feature some minimal description that makes them distinguishable. Instead of selecting all blank nodes, you can select those that match a specific graph pattern. This way, you can avoid merging underspecified resources. For example, the following two addresses, for which we only know that they are located in the Czech Republic, are unlikely the same:


@prefix : <http://schema.org/> .

[ a :PostalAddress ;
  :addressCountry "CZ" ] .

[ a :PostalAddress ;
  :addressCountry "CZ" ] .

More restrictive graph patterns also work to your advantage in case of larger datasets. By lowering the complexity of your SPARQL updates, they reduce the chance of you running into out of memory errors or timeouts.

Hash-based fusion

Hashes can be used as keys not only for blank nodes. Using SPARQL, we can select resources satisfying a given graph pattern and fuse them based on their hashed descriptions. Let's have a tiny sample dataset that features duplicate resources:

If you want to merge equivalent resources instantiating class :C (i.e. :r1, :r2, and :r5), you can do it using the following SPARQL update:

The downside of this method is that the order of bindings in GROUP_CONCAT cannot be set explicitly, nor it is guaranteed to be deterministic. In theory, you may get different concatenations for the same set of bindings. In practice, RDF stores typically concatenate bindings in the same order, which makes this method work.

Fusing subset descriptions

If we fuse resources by hashes of their descriptions, only those with the exact same descriptions are fused. Resources that differ in a value or are described with different properties will not get fused together, because they will have distinct hashes. Nevertheless, we may want to fuse resources with a resource that is described by a superset of their descriptions. For example, we may want to merge the following blank nodes, since the description of the first one is a subset of the second one's description:


@prefix : <http://schema.org/> .

[ a :Organization ;
  :name "ACME Inc." ] .

[ a :Organization ;
  :name "ACME Inc." ;
  :description "The best company in the world."@en ] .

Resources with subset descriptions can be fused in SPARQL Update using double negation:

The above-mentioned caveats apply in this case too, so you can use a more specific graph pattern to avoid merging underspecified resources. The update may execute several rewrites until reaching the largest superset, which makes it inefficient and slow.

Key-based fusion

If you want to fuse resources with unequal descriptions that are not all subsets of one resource's description, a key to identify the resources to fuse must be defined. Keys can be simple, represented by a single inverse functional property, or compound, represented by a combination of properties. For instance, it may be reasonable to fuse the following resources on the basis of shared values for the properties rdf:type and :name:


@prefix :    <http://schema.org/> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .

[ a :Organization ;
  :name "ACME Inc." ;
  :foundingDate "1960-01-01"^^xsd:date ;
  :email "contact@acme.com" ;
  :description "The worst company in the world."@en ] .

[ a :Organization ;
  :name "ACME Inc." ;
  :foundingDate "1963-01-01"^^xsd:date ;
  :description "The best company in the world."@en ] .

To fuse resources by key, we group them by the key properties, select one of them, and rewrite the others to the selected one:

If we fuse the resources in the example above, we can get the following:


@prefix :    <http://schema.org/> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .

[ a :Organization ;
  :name "ACME Inc." ;
  :foundingDate "1960-01-01"^^xsd:date, "1963-01-01"^^xsd:date ;
  :email "contact@acme.com" ;
  :description "The best company in the world."@en, "The worst company in the world."@en ] .

This example illustrates how fusion highlights problems in data, including conflicting values of functional properties, such as the :foundingDate, or contradicting values of other properties, such as the :description. However, resolving these conflicts is a complex task that is beyond the scope of this post.

Conclusion

While I found the presented methods for data fusion to be applicable for a variety of datasets, they may fare worse for complex or large datasets. Besides the concern of correctness, one has to weigh the concern of performance. Based on my experience so far, the hash-based and key-based methods are usually remarkably performant, while the methods featuring double negation are not. Nonetheless, the SPARQL updates from this post can be oftentimes simply copied and pasted and work out of the box (having tweaked the graph patterns selecting the fused resources).

2016-06-28

On generating SPARQL

The question how to generate SPARQL comes so often in my work that I figured I attempt a summary of the different approaches that answer this question, none of which is established enough to be considered a best practice. The lack of a well-established method for generating SPARQL may have arisen from the fact that SPARQL is serialized to strings. While its string-based format may be convenient to write by hand, it is less convenient to generate through code. To make SPARQL more amenable to programmatic manipulation, several approaches have been devised, some of which I will cover in this post.

Opting for strings or structured data to represent a data manipulation language is a fundamental design decision. Dumbing the decision down, there is a usability trade-off to be made: either adopt a string representation to ease manual authoring or go for a representation using data to ease programmatic manipulation. Can we nevertheless have the best of both options?

SPARQL continues in the string-based tradition of SQL; possibly leveraging a superficial familiarity between the syntaxes. In fact, SPARQL was recently assessed as “a string-based query language, as opposed to a composable data API.” This assessment implicitly reveals that there is a demand for languages represented as structured data, such as the Elasticsearch query DSL serialized in JSON or the Datomic query syntax, which is serialized in EDN.

To illustrate the approaches for generating SPARQL I decided to show how they fare on an example task. The chosen example should be simple enough, yet realistic, and such that it demonstrates the common problems in encountered when generating SPARQL.

Example

Let's say you want to know all the people (i.e. instances of foaf:Person) known to DBpedia. There are 1.8 million such persons, which is way too many to fetch in a single SPARQL query. In order to avoid overload, DBpedia's SPARQL endpoint is configured to provide at most 10 thousand results. Since we want to get all the results, we need to use paging via LIMIT and OFFSET to partition the complete results into smaller parts, such that one part can be retrieved within a single query.

Paging requires a stable sort order over the complete collection of results. However, sorting a large collection of RDF resources is an expensive operation. If a collection's size exceeds a pre-configured limit, Virtuoso requires the queries paging over this collection to use scrollable cursors (see the section “Example: Prevent Limits of Sorted LIMIT/OFFSET query”), which basically wrap an ordered query into a subquery in order to better leverage the temporary storage of the sorted collection. Because of the number of persons in DBpedia we need to apply this technique to our query.

Let's say that for each person we want to get values of several required properties and some optional properties. For example, we may want to get names (foaf:name) and birth dates (dbo:birthDate) and, optionally, dates of death (dbo:deathDate). Since persons can have multiple names and we want only one name per person, we need to use SAMPLE with the names to retrieve a single random name associated with each person. We could assume that a person has no more than one birth date and death date, but in fact in DBpedia there are 31 thousand persons with multiple birth dates and 12 thousand persons with multiple death dates, so we also need to use SAMPLE for these properties. Considering all these requirements, our SPARQL query may look like the following.

We need the LIMIT and OFFSET in this query to be generated dynamically, as well as the listing of the required and the optional properties. In the following, I will cover and compare several approaches for generating SPARQL queries using these parameters. All the approaches are illustrated by examples in Clojure to make them better comparable.

String concatenation

The approach that is readily at hand of most developers is string concatenation. While it is simple to start, it intertwines SPARQL with code, which makes it brittle and error prone. Convoluted manual escaping may be needed and the result is particularly messy in programming languages that lack support of multi-line strings, such as JavaScript. Here is an example implementation using string concatenation to generate the above-mentioned query.

Parameterized queries

If queries to be generated differ only in few variables, they can be generated from a parameterized query, which represents a generic template that can be filled with specific parameter values at runtime. Parameterized queries enable to split static and dynamic parts of the generated queries. While the static query template is represented in SPARQL and can be stored in a separate file, the dynamic parts can be represented using a programming language's data types and passed to the template at runtime. The separation provides both the readability of SPARQL and the expressiveness of programming languages. For example, template parameters can be statically typed in order to improve error reporting during development or avoid some SPARQL injection attacks in production.

Although parameterized queries improve on string concatenation and are highlighted among the linked data patterns, they are limited. In particular, I will discuss the limitations of parameterized queries as implemented in Apache Jena by ParameterizedSparqlString. While the main drawbacks of parameterized queries are true for other implementations as well, the details may differ. In Jena's parameterized queries only variables can be dynamic. Moreover, each variable can be bound only to a single value. For example, for the pattern ?s a ?class . we cannot bind ?class to schema:Organization and schema:Place to produce ?s a schema:Organization, schema:Place .. If we provide multiple bindings for a variable, only the last one is used. Queries that cannot restrict their dynamic parts to variables can escape to using string buffers to append arbitrary strings to the queries, but doing so gives you the same problems string concatenation has. Due to these restrictions we cannot generate the example query using this approach. Here is a partial implementation that generates only the limit and offset.

Jena also provides a similar approach closer to prepared statements in SQL. When executing a query (via QueryExecutionFactory) you can provide it with pre-bound variables (via QuerySolutionMap). Similar restrictions to those discussed above apply. Moreover, your template must be a syntactically valid SPARQL query or update. In turn, this prohibits generating LIMIT numbers, because LIMIT ?limit is not a valid SPARQL syntax. The following implementation thus does not work.

Templating

If we need higher expressivity for generating SPARQL, we can use a templating language. Templating is not restricted to the syntax of SPARQL, because it treats SPARQL as arbitrary text, so that any manipulation is allowed. As is the case with parameterized queries, templating enables to separate the static template from the dynamic parts of SPARQL. Unlike parameterized queries, a template is not represented in pure SPARQL, but in a mix of SPARQL and a templating language. This recalls some of the shortcomings of interposing SPARQL with code in string concatenation. Moreover, templates generally do not constrain their input, for example by declaring types, so that any data can be passed into the templates without it being checked in advance. Notable exceptions allowing to declare types of template data are available in Scala; for example Scalate or Twirl.

In order to show how to generate SPARQL via templating I adopted Mustache, which is a minimalistic and widely known templating language implemented in many programming languages. The following is a Mustache template that can generate the example query.

Rendering this template requires little code that provides the template with input data.

Domain-specific languages

As the string concatenation approach shows, SPARQL can be built using programming language construct. Whereas string concatenation operates on the low level of text manipulation, programming languages can be used to create constructs operating on a higher level closer to SPARQL. In this way, programming languages can be built up to domain-specific languages (DSLs) that compile to SPARQL. DSLs retain the expressivity of the programming languages they are defined in, while providing a syntax closer to SPARQL, thus reducing the cognitive overhead when translating SPARQL into code. However, when using or designing DSLs, we need to be careful about the potential clashes between names in the modelled language and the programming language the DSL is implemented in. For example, concat is used both in SPARQL and Clojure. Conversely, if a DSL lacks a part of the modelled language, escape hatches may be needed, regressing back to string concatenation.

Lisps, Clojure included, are uniquely positioned to serve as languages for defining DSLs. Since Lisp code is represented using data structures, it is easier to manipulate than languages represented as strings, such as SPARQL.

Matsu is a Clojure library that provides a DSL for constructing SPARQL via macros. Macros are expanded at compile time, so when they generate SPARQL they generally cannot access data that becomes available only at runtime. To a limited degree it is possible to work around this limitation by invoking the Clojure reader at runtime. Moreover, since Matsu is built using macros, we need to use macros to extend it. An example of such approach is its in-built the defquery macro that allows to pass parameters into a query template. Nevertheless, mixing macros with runtime data quickly becomes convoluted, especially if larger parts of SPARQL need to be generated dynamically.

If we consider using Matsu for generating the example query, we discover several problems that prevent us from accomplishing the desired outcome, apart from the already mentioned generic issues of macros. For instance, Matsu does not support subqueries. Defining subqueries separately and composing them as subqueries via raw input is also not possible, because Matsu queries contain prefix declarations, which are syntactically invalid in subqueries. Ultimately, the farthest I was able to get with Matsu for the example query was merely to the inner-most subquery.

Query DSLs in object-oriented langauges are often called query builders. For example, Jena provides a query builder that allows to build SPARQL by manipulating Java objects. The query builder is deeply vested in the Jena object model, which provides some type checking at the expense of a more verbose syntax. Since Clojure allows to call Java directly, implementing the example query using the query builder is straightforward.

While Matsu represents queries via macros and Jena's query builder does so via code, there is another option: representing queries via data. Using a programming language's native data structures for representing SPARQL provides arguably the best facility for programmatic manipulation. Data is transparent at runtime and as such it can be easily composed and inspected. In fact, a widespread Clojure design rule is to prefer functions over macros and data over functions. An example of using data to represent a SPARQL-like query language in Clojure is the Fabric DSL. While this DSL is not exactly SPARQL, it is “highly inspired by the W3C SPARQL language, albeit expressed in a more Clojuresque way and not limited to RDF semantics” (source).

SPIN RDF

An approach that uses data in RDF for representing SPARQL is SPIN RDF. It offers an RDF syntax for SPARQL and an API for manipulating it. While the translation of SPARQL to RDF is for the most part straightforward, one of its more intricate parts is using RDF collections for maintaining order in triple patterns or projected bindings, because the collections are difficult to manipulate in SPARQL.

Nonetheless, SPIN RDF seems to have a fundamental problem with passing dynamic parameters from code. For what I can tell, the membrane between SPIN RDF and code is impermeable. It would seem natural to manipulate SPIN RDF via SPARQL Update. However, how can you pass data to the SPARQL Update from your code? If you adopt SPIN RDF wholesale, your SPARQL Update operation is represented in RDF, so you have the same problem. Passing data from code to SPIN RDF thus results in a recursive paradox. Although I tried hard, I have not found a solution to this conundrum in the SPIN RDF documentation, nor in the source code of SPIN API.

This is how the example query can be represented using SPIN RDF; albeit using fixed values in place of the dynamic parts due to the limitations discussed above.

Rendering SPIN RDF to SPARQL can be implemented using the following code.

I have found a way to generate dynamic SPARQL queries in SPIN RDF using JSON-LD. JSON-LD can be represented by data structures, such as hash maps or arrays, that are available in most programming languages. This representation can be serialized to JSON that can be interpreted as RDF using the JSON-LD syntax. SPIN RDF can be in turn translated as SPARQL, obtaining our desired outcome. As may be apparent from this workflow, crossing that many syntaxes (Clojure, JSON-LD, RDF, SPIN, and SPARQL) requires large cognitive effort due to the mappings between the syntaxes one has to be aware of when authoring SPARQL in this way. Here is an implementation of this approach for the example query.

SPARQL algebra

As previously mentioned, a problematic part of SPIN RDF is its use of RDF collections for representing order. The documentation of Apache Jena recognizes this, saying that “RDF itself is often the most appropriate way to do this, but sometimes it isn't so convenient. An algebra expression is a tree, and order matters.” (source). The documentation talks about SPARQL algebra, which formalizes the low-level algebraic operators into which SPARQL is compiled. Instead of using RDF, Jena represents SPARQL algebra in s-expressions (SSE), which are commonly used in programming languages based on Lisp, such as Scheme. In fact, the “SSE syntax is almost valid Scheme” (source), but the SSE's documention acknowledges that Lisps “lacks convenient syntax for the RDF terms themselves” (source).

In order to see how our example query looks in SSE we can use Jena's command-line tools and invoke qparse --print=op --file query.rq to convert the query into SSE. The following is the result we get.

If SSEs were valid Clojure data structures, we could manipulate them as data and then serialize them to SPARQL. Nevertheless, there are minor differences between SSE and the syntax of Clojure. For example, while ?name and _:a are valid symbols in Clojure, absolute IRIs enclosed in angle brackets, such as <http://dbpedia.org/ontology/>, are not. Possibly, these differences can be remedied by using tagged literals for RDF terms.

Conclusions

I hope this post gave you a flavour of the various approaches for generating SPARQL. There is an apparent impedance mismatch between the current programming languages and SPARQL. While the programming languages operate with data structures and objects, SPARQL must be eventually produced as a string. This mismatch motivates the development of approaches for generating SPARQL, which is presented with many challenges, some of which I described in the post.

I assessed these approaches on the basis of how they fare on generating an example query using the data from DBpedia. The complete implementations of these approaches are available in this repository. Out of the approaches I reviewed, I found four in which it is feasible to generate the example SPARQL query without undue effort, which include:

  • String concatenation
  • Templating
  • Jena's query builder DSL
  • SPIN RDF using JSON-LD

My personal favourite that I use for generating SPARQL is templating with Mustache, which appears to mesh best with my brain and the tasks I do with SPARQL. Nonetheless, I am aware of the limitations of this approach and I am on a constant lookout for better solutions, possibly involving rendering SPARQL from data.

While I invested a fair amount of effort into this post, it is entirely possible I might have overlooked something or implemented any of the reviewed approaches in a sub-optimal way, so I would be glad to hear any suggestions on how to improve. In the meantime, while we search for the ideal solution for generating SPARQL, I think the membrane between code and SPARQL will remain only semipermeable.

2016-03-22

Academia-driven development

In this post I present an opinionated (and mostly-wrong) account on programming in academia. It's based in part on my experience as a developer working in academia and in part on conversations I had with fellow developers working in the private sector.

In academia, you rarely program even if you are in computer science. Instead, you read papers, write papers, write deliverables for ongoing projects, or write project proposals. You aren't paid to program, you are paid to publish. You do only as much programming as is needed to have something to write a paper about. “Scientists use programming the way software engineers use public transport – just as a means to get to what they have to do,” observes Bozhidar Bozhanov. While programming purists may be dissatisfied with that, Jason Baldridge is content with this state of affairs and writes: “For academics, there is basically little to no incentive to produce high quality software, and that is how it should be.”

Albert Einstein allegedly said this: “If we knew what it was we were doing, it would not be called research, would it?” While the attribution of this quote is dubious at best, there's a grain of truth in what the quote says. It's natural in research that you often don't know what you work on. I think this is the reason why test-driven development (TDD) is not truly applicable in research. Programming in research is used to explore new ideas. TDD, on the contrary, requires upfront specification of what you are building. German has the verb ‘basteln’ that stands for DIY fiddling. The word was adopted into the Czech spoken language with a negative connotation of not knowing what you're doing, which I think captures nicely what often happens in academic programming.

The low quality of academic software hinders its maintenance and extensibility in long-term development. For one-off experiments these concerns aren't an issue, but most experiments needs to be reproducible. Academic software must allow to reproduce and verify the results that are reported in the publication associated with it. Anyone must be able to re-run the software. It must be open-source, allowing others to scrutinize its inner workings. Unfortunately, it's often the case that academic software isn't released or, when it's made available, it's nigh impossible to run it without asking its creators for assistance.

What's more is that usability of software is hardly ever a concern in academia, in spite of the fact that usable software may attract more citations, thereby increasing the academic prestige of its author. An often-mentioned example of this effect in practice is Word2vec, the paper of which boasts with 1305 citations according to Google Scholar. Indeed, it would be a felicitous turn if we reconsidered the usability of academic software as a valuable proxy that increases citation numbers.

A great benefit that comes with reproducible and usable software is extensibility. Ted Pedersen argues that there's “a very happy side-effect that comes from creating releasable code—you will be more efficient in producing new work of your own since you can easily reproduce and extend your own results.” Nonetheless, even though software may be both reproducible and usable, extending a code base without tests may be like building on quicksand. This is usually an opportunity for refactoring. For example, the feature to be extended can be first covered with tests that document its expected behaviour, as Nell Shamrell-Harrington suggests in surgical refactoring. The subsequent feature extension must not break these tests, unless the expected behaviour should change. I think adopting this approach can do a great good to the continuity of academic development.

Finally, there's also an economic argument to make for ‘poor-quality’ academic software. If software developed in the academia achieved production quality, it would constitute a competition to software produced in the private sector. Since academia is a part of the public sector, academic endeavours are financed mostly from the public funds. Hence such competition with commercial software can be considered unfair. Dennis Polhill argues that “unfair competition exists when a government or quasi-government entity takes advantage of its tax exemption and other privileges to supply private goods to the market in competition with private suppliers.” Following this line of thought, the public sector should not subsidize the development of software that is commercially viable and can be built by private companies. Instead of developing working solutions, academia can try and test new prototypes. If released openly, this proof-of-concept work can be then adopted in the private sector and grown into commercial products.

Eventually, when exploring my thoughts on academia-driven development, I realized that I'm torn between settling for the current status quo and pushing for emancipating software with publications. While I'm stuck figuring this out, there are laudable initiatives, such as Semantic Web Developers, which organizes regular conference workshops that showcase semantic web software and incite conversations about the status of software in academia. Let's see how these conversations pan out.

2016-03-21

In science, form follows funding

Recently, brief Twitter exchanges I had with @csarven on the subject of #LinkedResearch made me want to articulate a longer-form opinion on scientific publishing that no longer fitted a tweet. Be wary though, although this opinion is longer, it's still oversimplifying a rather complex matter for the sake of conveying the few key points I have.

There's a pervasive belief that “if you can't measure it, you can't manage it”. Not only is this quote often misattributed to Peter Drucker, its author William Edwards Deming actually wrote that “it is wrong to suppose that if you can't measure it, you can't manage it — a costly myth” (The New Economics, 2000, p. 35). Contradicting the misquoted statement, Deming instead suggested that it's possible to manage without measuring. With that being said, he acknowledges that metrics remain an essential input to management.

Since funding is a key instrument of management, metrics influence funding decisions too. Viewed from this perspective, science is difficult to fund because its quality is hard to measure. The difficulty of measuring science is widely recognized, so that scientometrics was devised with the purpose of studying how to measure science. Since measuring science directly is difficult, scientometrics found ways to measure scientific publishing, such as citation indices. Though using publishing as a proxy to science comes with an implicit assumption that the quality of scientific publications correlates positively with the quality of science, many are willing to take on this assumption simply because of the lack of a better way for evaluating science. The key issue of this approach is that the emphasis on measurability constrains the preferred form of scientific publishing to make measuring it simpler. A large share of scientific publishing is centralized in the hands of few large publishers who establish a constrained environment that can be measured with less effort. The form of publishing imposes a systemic influence on science. As Marshall McLuhan wrote, the medium is the message. While in architecture form follows function, in science, form follows funding.

Measuring distributed publishing on the Web is a harder task, though not an insurmountable one. For instance, Google's PageRank algorithm provides a fair approximation of the influence the documents distributed on the Web have. Linked research, which proposes to use the linked data principles for scientific publishing, may enable to measure science without the cost incurred by centralization of publishing. In fact, I think its proverbial “killer application” may be a measurable index like the Science Citation Index. Indeed, SCI was a great success, and it “did not stem from its primary function as a search engine, but from its use as an instrument for measuring scientific productivity” (Eugene Garfield: The evolution of the Science Citation Index, 2007). A question that naturally follows is: how off am I in thinking this?

2015-12-08

Coding dub techno in Ruby using Sonic Pi

Dub techno lends itself to code thanks to its formulaic nature. Indeed, A Bullshitter's Guide to Dub Techno says:

“Sadly, a lot of dub techno out there is unbelievably dull — greyscale, unadventurous, utterly and literally generic. It must seem easy to make because after all, all you need is the a submerged kickdrum, a few clanking chords stretched pointlessly out into arching waves of unmoving, unfeeling nothingness, and maybe the odd snatch of tired melodica, snaking around like a cobra that desperately needs to be put out of its misery.”

I decided to try to code dub techno in Ruby using Sonic Pi. Sonic Pi is an app for live coding sound. It started as a tool for teaching computer science using Raspberry Pi but it works damn well for making a lot of noise. Here's my attempt at coding dub techno in Sonic Pi:

The source code is available here.

My attempt exploits some of the dub techno stereotypes, such as the excessive repetition progressing as I slowly build the sound. As Joanna Demers writes on dub techno and related genres in Listening through the Noise: “Static music goes nowhere, achieves no goals, does no work, and sounds the same three hours into the work as it did when the work began.” In case of dub techno, it is an intentionally bare and stripped-down version of techno. It often focuses on the timbre of sound, using modulating synthesizers heavily drenched in reverb and echoes. Demers writes: “Static music is not only music that avoids conventional harmonic or melodic goals but also music that takes specific steps to obscure any sense of the passage of time.” Dub techno keeps melodic or harmonic progressions to a minimum, usually employing single minor chords oscillating through entire tracks. In my code, I use solely the D minor chord, which varies only in chord inversions and octave shifts.

I think that Sonic Pi offers a fluent live coding experience. For example, the nested with_* functions (such as with_fx) accepting Ruby blocks as arguments provide an intuitive way of representing bottom-up sound processing pipelines. Furthermore, live coding provides a fast feedback loop. Your ears are the tests of your code and you can hear the results of your code immediately.

Overall, I really enjoyed this attempt at dub techno. I would like to thank to Sam Aaron and co. for creating Sonic Pi and I would encourage you to give Sonic Pi a shot.

2015-05-02

Curling SPARQL HTTP Graph Store protocol

SPARQL HTTP Graph Store protocol provides a way of manipulating RDF graphs via HTTP. Unlike SPARQL Update it does not allow you to work with RDF on the level of individual assertions (triples). Instead, you handle your data on a higher level of named graphs. Named graph is a pair of a URI and a set of RDF triples. A set of triples can contain a single triple only, so it is technically possible to manipulate individual triples with the Graph Store protocol, but this way of storing data is not common. In line with the principles of REST, the protocol defines its operations using HTTP requests. It covers the familiar CRUD (Create, Read, Update, Delete) operations known from REST APIs. It is simple and useful, albeit lesser known part of the family of SPARQL specifications. I have seen software that would have benefited had its developers known this protocol. This is why I decided to cover it in a post.

Instead of showing the HTTP interactions via the Graph Store protocol in a particular programming language I decided to use cURL as the lingua franca of HTTP. I discuss how the Graph Store protocol works in 2 implementations: Virtuoso (version 7.2) and Apache Jena Fuseki (version 2). By default, you can find a Graph Store endpoint at http://localhost:8890/sparql-graph-crud-auth for Virtuoso and at http://localhost:3030/{dataset}/data for Fuseki ({dataset} is the name of the dataset you configure). Virtuoso also allows you to use http://localhost:8890/sparql-graph-crud for read-only operations that do not require authentication. The differences between these implementations are minor, since both implement the protocol's specification well.

If you want to follow along with the examples below, an easy option is to download the latest version of Fuseki and start it with a disposable in-memory dataset using the shell command fuseki-server --update --mem /ds (ds is the name of our dataset). You can use any RDF file as testing data. For example, you can download DBpedia's description of SPARQL in the Turtle syntax as the file data.ttl:

curl -L -H "Accept:text/turtle" \
     http://dbpedia.org/resource/SPARQL > data.ttl

Finally, if any of the arguments you provide to cURL (such as graph URI) contains characters with special meaning in your shell (such as &), you need to enclose them in double quotes. The backslash you see in the example commands is used to escape new lines so that the commands can be split for better readability.

I will now walk through the 4 main operations defined by the Graph Store protocol: creating graphs with the PUT method, reading them using the GET method, adding data to existing graphs using the POST method, and deleting graphs, which can be achieved, quite unsurprisingly, via the DELETE method.

Create: PUT

You can load data into an RDF graph using the PUT HTTP method (see the specification). This is how you load RDF data from file data.ttl to the graph named http://example.com/graph:

Virtuoso
curl -X PUT \
     --digest -u dba:dba \
     -H Content-Type:text/turtle \
     -T data.ttl \
     -G http://localhost:8890/sparql-graph-crud-auth \
     --data-urlencode graph=http://example.com/graph
Fuseki
curl -X PUT \
     -H Content-Type:text/turtle \
     -T data.ttl \
     -G http://localhost:3030/ds/data \
     --data-urlencode graph=http://example.com/graph

The -T named argument uploads a given local file, -H specifies an HTTP header indicating the content type of the uploaded file, -G provides the Graph Store endpoint's URL, and --data-urlencode let's you pass in a URI naming of the created graph (via the graph query parameter). Since the Graph Store protocol's interface is uniform, most of the other operations use similar arguments.

Virtuoso uses HTTP Digest authentication for write and delete operations (i.e. create, update, and delete). The example above assumes the default Virtuoso user and password (i.e. dba:dba). If you fail to provide valid authentication credentials, you will be slapped over your hands with the HTTP 401 Unauthorized status code. Fuseki does not require authentication by default, but you can configure it using Apache Shiro.

When using Virtuoso, you can leave the Content-Type header out, because the data format will be automatically detected, but doing so is not a good idea. You need to provide it for Fuseki and if you fail to do so, you will face HTTP 400 Bad Request response. Try not to rely on the autodetection being correct and provide the Content-Type header explicitly.

If you want to put data into the default graph, you can use the default query parameter with no value:

Fuseki
curl -X PUT \
     -H Content-Type:text/turtle \
     -T data.ttl \
     -G http://localhost:3030/ds/data \
     -d default

If you use Fuseki, you can also omit the graph parameter completely to manipulate with the default graph. Nevertheless, this is not a standard behaviour, so you should not rely on it.

If you PUT data into an existing non-empty graph, its previous data is replaced.

Read: GET

To download data from a given graph, you just issue a GET request (see the specification). You can use the option -G to perform GET request via cURL:

Virtuoso
curl -G http://localhost:8890/sparql-graph-crud \
     --data-urlencode graph=http://example.com/graph
Fuseki
curl -G http://localhost:3030/ds/data \
     --data-urlencode graph=http://example.com/graph

Alternatively, you can simply use curl http://localhost:3030/ds/data?graph=http%3A%2F%2Fexample.com%2Fgraph, but -G allows you to provide the graph query parameter separately via --data-urlencode, which also takes care of the proper URL-encoding. You can specify the RDF serialization you want to get the data in via the Accept HTTP header. For example, if you want the data in N-Triples, you provide the Accept header with the MIME type application/n-triples:

Fuseki
curl -H Accept:application/n-triples \
     -G http://localhost:3030/ds/data \
     --data-urlencode graph=http://example.com/graph

Unfortunately, while Fuseki supports the application/n-triples MIME type, Virtuoso does not. Instead, you will have specify the deprecated MIME type text/ntriples (even text/plain will work) to get the data in N-Triples. Since N-Triples serializes each RDF triple on a separate line, you can use it as a naïve way of counting the triples in a graph by piping the data into wc -l (-s option used to hide the cURL progress bar):

Virtuoso
curl -s -H Accept:text/ntriples \
     -G http://localhost:8890/sparql-graph-crud \
     --data-urlencode graph=http://example.com/graph | \
     wc -l

If a graph named by the requested URI does not exist, you will get HTTP 404 Not Found response.

Update: POST

If you want to add data to an existing graph, use the POST method (see the specification). In case you POST data to a non-existent graph, it will be created just as if using the PUT method. The difference of POST and PUT is that when you send data to an existing graph, POST will merge it with the graph's current data, while PUT will replace it.

Virtuoso
curl -X POST \ 
     --digest -u dba:dba \
     -H Content-Type:text/turtle \
     -T data.ttl \
     -G http://localhost:8890/sparql-graph-crud-auth \
     --data-urlencode graph=http://example.com/graph
Fuseki
curl -X POST \ 
     -H Content-Type:text/turtle \
     -T data.ttl \
     -G http://localhost:3030/ds/data \
     --data-urlencode graph=http://example.com/graph

It is worth knowing how triples are merged during this operation. When you POST data to a non-empty graph, the current set of triples the graph is associated with will be merged with the set of triples from the uploaded data via set union. In most cases, if these two sets shared any triples, they will not be duplicated. However, if the shared triples contain blank nodes, they will be duplicated because, due to their local scope, blank nodes from different datasets are always treated as distinct. For example, if you repeatedly POST the same triples containing blank nodes to the same graph, the first time its size will increase by the number of posted triples, but on the second and subsequent POSTs the size of the graph will increase by the number of triples containing blank nodes. This can be one of the reasons why you may want to avoid using blank nodes.

Delete: DELETE

Unsurprisingly, deleting graphs is achieved using the DELETE method (see the specification). As you may expect by now, if you attempt to delete a non-existent graph, you will get HTTP 404 Not Found response.

Virtuoso
curl -X DELETE \
     --digest -u dba:dba \
     -G http://localhost:8890/sparql-graph-crud-auth \
     --data-urlencode graph=http://example.com/graph
Fuseki
curl -X DELETE \
     -G http://localhost:3030/ds/data \
     --data-urlencode graph=http://example.com/graph

Other methods

As in the HTTP specification, there are other methods defined in the Graph Store protocol. An example of such method is HEAD, which can be used to test whether a graph exists. cURL allows you to issue a HEAD request using the -I option:

Fuseki
curl -I \
     -G http://localhost:3030/ds/data \
     --data-urlencode graph=http://example.com/graph

If you the graph exists, you will receive HTTP 200 OK status code. Otherwise, you will once again see a saddening HTTP 404 Not Found response. In the current version of Virtuoso (7.2) using the HEAD method will trigger 501 Method Not Implemented, so you should use Fuseki if you want to play with this method.

As the Graph Store protocol's specification shows, you can replace any operation of the protocol by an equivalent SPARQL update or query. Graph Store protocol thus provides an uncomplicated interface for basic operations manipulating with RDF graphs. I think it is a simple tool worth knowing.