Dydra is an RDF graph storage service. It stores and retrieves the contents of RDF datasets through SPARQL, LDF and LDP interfaces. In addition to these basic capabilities, it retains previous store states, in addition to the current state, as active addressable aspects of a dataset analogous to named graphs in a quad store. It incorporates arbitrary revisions into target datasets according to query arguments for HTTP requests and an additional REVISION clause in SPARQL. This document describes a taxonomy of archival RDF queries and illustrates it with examples drawn from three popular ontologies: gist, schema.org and STW, which demonstrate how the Dydra TB storage architecture combines with simple interface extensions to support the principal tasks and address the primary concerns when working with RDF data over time.
Dydra is an RDF graph storage service. It operates as a cloud service, a local
service or an embedded library. It stores and retrieves the contents of RDF
datasets through SPARQL, LDF and LDP interfaces. In addition to these basic
capabilities, Dydra retains previous store states, in addition to the current state,
as active addressable aspects of a dataset analogous to named graphs in a quad
store. It addresses these states in its REST interfaces through the values supplied
for a revision argument, which acts in a manner analogous to the graph argument
for a quad store request, or through the Accept-Datetime header defined by
Memento. Its SPARQL dialect includes a REVISION clause which plays a role
for revisions analogous to that which the GRAPH clause plays with respect to
named graphs. These facilities sufice to manage and analyze evolving datasets
over time. In order to demonstrate this, we present a taxonomy of archival RDF
analytics, describe its relation to the BEAR framework[
The next section introduces a taxonomy with which to comprehend the possible query forms, Section 3 aligns this taxonomy with that from the BEAR proposal and illustrates each case with a simple query. Section 4 provides extended examples. Section 5 discusses implementation considerations.
A Taxonomy for Archival RDF Analysis
We characterize queries, for the purpose of this discussion, according to two
principle dimensions: dataset constitution and algebra combination. Constitution
concerns which revisions to include in the target dataset and how to address them.
Combination concerns how the query algebra combines those constituent elements.
An a-temporal query specifies a target RDF dataset with respect to named graphs
by indicating which graphs are to be merged into the target dataset default graph
and/or which are to be made available as named graphs. When a variable is
specified in a GRAPH clause, it ranges over the specified set or, when none
was specified, over a default set. In order to perform inter-graph comparisons,
a query includes multiple GRAPH clauses and combines the respective results
through arbitrary SPARQL[
In a transaction-time query, revisions play a role analogous to graphs. The query can specify one or more revisions to indicate the transaction state(s) which constitute(s) the target dataset. If none is specified, as a default, the dataset reflects the latest revision. Any revision variable ranges over known revisions. A revision variable extends solutions within their scope with a binding for its value, which contributes to algebra operations in the same manner as any other binding. In contrast to graphs, however, in addition to specifying an individual revision, a revision designator can compose revisions, for example, to incorporate all states over a temporal interval, or to indicate the diference between the states which correspond to transactions. The query algebra then matches graph patterns against the composed revision datasets and combines them to produce the results.
In terms of dataset constitution and algebra combination, descriptions of transaction-time queries supports the following characterisations:1 – dataset revision constitution : none (∅), single (@), multiple (n), ranges (· · · ), or diferences ( ∆ ) – algebraic combination : default (∅), constant (Vi)2, or abstract (?v) .
The revision designators provide means to constitute datasets corresponding to various temporal entities: – A single revision is identified directly by it UUID, for example
58bd5f 7-7d46-48f8-b64a-43f257c48817, or by a timestamp in the interval in 1 This exposition concerns neither streaming data nor graph store operations. Any use cases related to streaming data will still require an individual query reduction to occur on a static dataset, but may require additional means to refer to transaction when constituting the dataset. Use cases related to graph store operations are always identity projections of a composed dataset. 2 A constant corresponds to a date, a revision name, or the revision associated with some user label. ``````C`om`b`ina`tio`n Constitution default (∅) constant (Vi) abstract (?v) none (∅) → single
V er(Q) M at(Q,HEAD)
M at(Q, Vi) J oin(Q1, Vi, Q2, Vj)
Dif f (Q, vi, vj)
Change(Q) multiple range diference (n) (· · · ) (∆ ) which the revision was current for its repository, in that case 2016-03-15T01:11:38Z. – A relative revision is designated by inflection, for example 58bd5f 7-7d46-48f8-b64a-43f257c48817 The compositon of two revision is designated by their sequence, for example 58bd5f 7-7d46-48f8-b64a-43f257c48817,f47ac10b-58cc-4372-a567-0e02b2c3d479. – The additions and deletions between two revision is designated by connecting identifiers for the bound with " ..", for example 58bd5f 7-7d46-48f8-b64a-43f257c48817..f47ac10b-58cc-4372-a567-0e02b2c3d479.
The combined characterisations yield the taxonomy shown in Table 1. In these terms, all query variations present in the BEAR framework are accommodated in four of the twelve combinations, as indicated in the none and single columns. In particular, a mechanism which provides just a request revision specification analogous to the SPARQL graph clause is suficient. For more complex use cases, the constitution forms multiple, range, and diference compose a basic graph match target a dataset which comprises distinct revisions, but is processed as a single entity. This supports diachronic use cases, such as – Retrieve those concepts changed during a given calendar interval. – Compute those ontology items which contradict the state recorded in the previous revision. – Retrieve those concepts which are universally valid across the entire repository lifetime.
Once the distinction has been made between dataset constitution and algebraic
composition, in order to extend SPARQL to query revisioned datasets, is it
necessary only to provide means establish the scope of a given revision and,
where the value is not constant, to bind it to a variable. This is accomplished
with a REVISION clause, analogous to a GRAPH or SERVICE clause. Where
the latter limit the application of contained patterns to composed local graphs and
or to a graph at a remote location, the REVISION clause limits the application
to composed versions. Where alternative approaches, suggest to conflate revision
metamodel with the domain model either by reifying the domain data in order
to store it in the revision model[
OptionalGraphPattern | GroupOrUnionGraphPattern | MinusGraphPattern | GraphGraphPattern |
RevisionGraphPattern | ServiceGraphPattern
[ [ 6 0 a ] ] RevisionGraphPattern : :=
’REVISION ’ ( VarOrIRIref | S t r i n g ) GroupGraphPattern
transaction information with domain data[
The implementation extends one grammar production, as indicated in figure 13, to establish the scope of a revision designator and permit its binding. If the value is constant, the target is that revision. If the value is a bound variable, the query applies to all revision values apparent for that variable in the respective solutions. If the variable is free, the revision ranges over all repository revisions, in reverse chronological order. 3
Each element from the BEAR blueprint for temporal RDF analytics is realized
as in Table 3. In Dydra, the semantics diverge from that proposed by [
In order to illustrate how the facility applies to concrete cases, we present examples for archival analysis of ontology datasets. One is drawn from each of three popular, evolving ontologies: gist schema.org, Standard Thesaurus for Economics, and Each alternative is illustrated below with a case related to ontology curation. 4.1
gist Use the provenance records to determine the revisions current at given dates and analyse the ontology state for each. 3 See http://www.w3.org/TR/2013/REC-sparql11-query-20130321/ as available on 2016-04-25 . SELECT ? concept ( count (? subConcept ) as ? f r e q u e n c y ) ( sample (? r e l e a s e D a t e ) as ? date ) ( sample (? l a b e l ) as ? r e l e a s e ) WHERE { { SERVICE < http : / / l o c a l h o s t /schema/ g i s t - provenance > { { SELECT ? r e l e a s e D a t e (max (? r e v i s i o n D a t e ) as ? r e l e a s e R e v i s i o n D a t e ) WHERE {
VALUES ? r e l e a s e D a t e { ’2009 -02 -28T12 : 0 0 : 0 0Z’^^ < http : / /www. w3 . org /2001/XMLSchema#dateTime > ’2009 -07 -31 T12 : 0 0 : 0 0Z’^^ < http : / /www. w3 . org /2001/XMLSchema#dateTime > } GRAPH ? r e v i s i o n { ? r e v i s i o n < http : / /www. w3 . org / ns / prov#generatedAtTime > ? r e v i s i o n D a t e . } } GROUP BY ? concept ? r e v i s i o n ORDER BY DESC (? f r e q u e n c y ) LIMIT 10 4.2
STW Indicate the prevalence of descriptors across thesaurus revisions. p r e f i x sk o s : < http : / /www. w3 . org /2004/02/ s k os / c o r e#> p r e f i x zbwext : < http : / / zbw . eu / namespaces /zbw - e x t e n s i o n s /> # # Show the number o f v e r s i o n s i n which a d e s c r i p t o r i s p r e s e n t # s e l e c t ? p r e v a l e n c e ( count (? p r e v a l e n c e ) as ? f r e q u e n c y ) where { s e l e c t ? s ( count (? r ) as ? p r e v a l e n c e ) where {
r e v i s i o n ? r { ? s a zbwext : D e s c r i p t o r . } } group by ? s } group by ? p r e v a l e n c e o r d e r by desc (? f r e q u e n c y ) 4.3 schema.org Indicate the prevalence of classes which have been marked as deprecated. s e l e c t ? concept ? r e v i s i o n D e p r e c a t e d ? r e v i s i o n U s e d where { { s e l e c t ? concept ? rDeprecated where { r e v i s i o n ? rDeprecated { ? concept < http : / /www. w3 . org /2000/01/ rdf - schema#comment> ?comment . f i l t e r ( regex (? comment , ’ . * d e p r e c a t e d . * ’ ) ) } } } { r e v i s i o n ? rUsed {
? concept a ? type . } } { s e r v i c e < http : / / l o c a l h o s t /schema - org - t e s t / provenance > {
graph ? rUsed { ? rUsed r d f s : l a b e l ? r e v i s i o n U s e d } } } { s e r v i c e < http : / / l o c a l h o s t /schema - org - t e s t / provenance > {
graph ? rDeprecated { ? rDeprecated r d f s : l a b e l ? r e v i s i o n D e p r e c a t e d } } } } o r d e r by ? concept 5
The store implementation has been designed for eficient mutation at scale balanced with the requirement to access historical revisions of data. It combines graph-partitioned triple tables with clustered, persistent B+tree indexes, based on a memory-mapped MVCC design with full ACID semantics. By default, repository data is comprehensively indexed six ways: GSPO, GPOS, GOSP, SPOG, POSG, OSPG, enabling any quad-pattern match to be answered from indices. RDF terms are interned on an installation-wide basis into integer ordinals. In the storage for a repository, B+tree keys consist of four integers representing the graph, subject, predicate, and object terms. B+tree values store a revision visibility map indicating which revisions a particular quad is visible in.
The revisioning can be disabled in a per-repository basis in which case B+tree values are of zero length; further, the trade-of between mutation performance versus query performance can be tuned by configuring the revision visibility map to be used only on the GSPO index, which speeds up mutation about six-fold at the constant cost of a factor two increase in B+tree lookups during query processing of non-GSPO patterns.
There are various encodings of revision visibility maps as succinct data structures that optimize for eficient revision lookup and compact space utilization. The base storage requirements for an un-versioned repository involve sixteen or thirty-two bytes per statement, depending on intended capacity, times the index count plus storage for term strings. With revisions, the space should increase in a sublinear relation to mutation count, where those statements not modified since first insertion require no additional space, while mutated quads require a visibility map, the size of which depends on the mutation pattern.
Table 2 compares the space for RDF document and indexed representations
of the example datasets. In addition to the gist, schema.org and STW datasets,
the table includes statistics from the revision history of the "Experimental Factor
Ontology" [
As illustrated by the green components in figure 2 4, the implementation efort to support REVISION clause was limited. The service depends on a 4 See http://arxiv.org/pdf/1504.01891v2, as available on 2016-04-25. strict separation between the SPARQL processor and the RDF store. This limits the query processor to operations which manage transactions for specific repository revisions and to perform count, match and scan operations with respect to statement patterns. As a consequence of this interface, the changes to the SPARQL processor are limited to 293 sloc for the algebra operator and the two productions in the grammar in figure 1.
This compares well, for example, to the SERVICE operator, which requires 453 sloc and to the 13,151 sloc for the entire algebra implementation. The store implementation is more substantial. In this case, 1,921 / 101,416 sloc implement the revisioned index, which is still a relatively small amount, considering the capabilities. Dydra SPARQL forms corresponding to BEAR Abstract Notation
Mat(Q,vi)
SELECT * WHERE { Q :[vi] } SELECT * WHERE {
REVISION <urn : uuid :12345678 -· · · -123456789012 > {
? s ?p ?o SELECT * WHERE { { { {Q : [ v i ] } MINUS {Q : [ v j ] } } BIND( v i AS?V) } UNION { { {Q : [ v j ] } MINUS {Q : [ v i ] } } BIND( v i AS?V) } SELECT * WHERE {
REVISION ?v { { {? s ?p ?o} MINUS {REVISION " ~ " {? s ?p ?o }}} UNION { { REVISION " ~ " {? s ?p ?o }} MINUS {? s ?p ?o }} }
} } } SELECT * WHERE { {REVISION <urn : uuid :12345678 -· · · -123456789012 > {
{? s ?p ?o} } {REVISION <urn : uuid :87654321 -· · · -098765432109 > {
{? s ?p ?o} } SELECT ?V1 ?V2 WHERE { {{P : ? V1 } MINUS {P : ? V2}}
FILTER( abs (? V1 - ?V2) = 1 ) SELECT ?v WHERE {
REVISION ?v { {? s ?p ?o} MINUS { REVISION ’ ~ ’ {? s ?p ?o} } Version materialisation
Change(Q) Dif(Q,vi,vj) SELECT * WHERE {
REVISION ?v {
? s ?p ?o Cross-version join(Q1,vi,Q2,vj) SELECT * WHERE { {Q : [ v i ] } {Q : [ v j ] } } join