For most use cases, the Semantic Web provides essential mechanisms to interlink data in a fast and e cient way. However, it is still not widely accepted in industry since some important features are not mature enough. Requirements include easier model transformation and access to dynamic data. One of the most missing important features is version control which would make it possible to record changes in a way that they can be rolled back at any time. Recent version control system are not very well integrated into the Semantic Web.
This paper shows a novel way of dealing with version control for Linked Data. It presents R43ples as an approach using named graphs to semantically store the di erences between revisions. Furthermore it allows direct access and manipulation of revisions with SPARQL. Thus, the access is almost transparent for the clients which can still use known SPARQL queries enhanced with some additional keywords. A prototypical implementation of the system shows a proof of concept and performance considerations. enablers to support new inter-organisational collaboration models for the creation of virtual enterprises. The ComVantage1 project explores the capabilities of Linked Data (LD) as a exible and rapidly unifying way to provide access to the data vaults of all stakeholders of a virtual enterprise by creating a product-centred collaboration space. However, the almost unlimited openness and exibility of Linked Data may also involve disadvantages. Industrial applications require reliability, security and stability. Thus, they need to keep control over the process of data manipulation. In fact, version control is an essential requirement for them to adapt this technology.
Section 2 of this paper states the need for version control systems in the Semantic Web and provides an overview of related work and our contributions. In section 3, the version control concept of R43ples is presented. Section 4 describes the prototypical implementation. Section 5 evaluates the concept and gives some metrics of the implementation. Section 6 discusses the concept further before the paper is concluded with an outlook of possible enhancements.
The major function of version control systems is to record changes in the information model in order to get back to a prior version when needed. Furthermore, version control makes it possible to merge changes of di erent authors into one common information base. Obviously, this functionality is not only needed for software engineering but for data in general. This includes Linked Data which has a special demand for version control because of its very open nature and the number of possible contributors to a data set. Current version control systems are usually either text-based (changes can be localised in lines) or completely binary (no localisation of changes possible). However, Linked Data is graph-based and thus in this case the existing systems don't meet the localisation mechanisms which is necessary for merging revisions. Additionally, one can di erentiate between distributed systems and central systems. In a central system like Subversion2 the whole repository is stored on a central server and the clients have local working copies. In distributed systems like Git3, every client holds the full repository and can re-synchronise with other clients.
There has been a lot of previous work on versioning of
models. For example, Watkins and Nicole [
Another interesting approach which allows tracking of
information over time in Linked Data is the use of temporal RDF
suggested by [
Most authors who handle version control systems for the
Semantic Web follow an operation based approach which relies
on speci c operations and are thus not well integrated in the
current Semantic Web environment. Auer and Herre [
Some Semantic Web applications support synchronising
between di erent users, e.g. OntoWiki Mobile [
R43ples o ers a completely semantic approach for
versioning RDF data sets in named graphs and accessing them via
SPARQL. The concept is based partly on the work of Vander
Sande et. al. [
We use a central repository since no local working copy in a traditional sense can be checked out in the Semantic Web and held on the client. The complete graph could be extremly large and every piece of information is potentially connected with other information spread over the global Linked Data cloud. This also excludes conventional LockModify-Unlock mechanisms. This would imply that the whole network has to be locked. Thus we use a CopyModify-Merge mechanism where clients get their information via SPARQL (copy), work with this in their local memory (modify) and commit their updates to the server via SPARQL again (merge). This makes it possible for users to keep on working with the well-known SPARQL interface while providing fast and exible revisions management. R43ples handles version control on a graph level and not the instance level. Thus, a speci c version of a whole named graph is the unit under version control. It is stored as a revision which can be queried and used as a base for further changes. Unlike in le-based systems (e.g. Subversion or Git) where a revision contains a set of les representing a speci c point in time, a revision in R43ples contains only one single named graph.
The whole approach uses semantics in order to avoid hidden
meanings which makes it hard for other clients to access the
information. Thus, revisions are modelled as Linked Data.
The data model uses PROV-O [
The named graph with the URI of the revisioned graph holds
the MASTER revision representing the terminal revision of
the default branch in the revision graph. The information
about other revisions and their connections and further
revisioned graphs is stored in an additional named graph for
each revisioned graph called <r43ples-revisions>. All
revision control systems have to provide information of all
revisions while handling the number of storage. Since \97,3%
of the entire data in each version remains unchanged" [
The R43ples approach supports tags as references to speci c revisions via the property rmo:references (as shown in gure 2). They are of type rmo:Tag and have a unique name (rmo:tagName) as well as a description (rdfs:description). Similarly, di erent branches are supported by allowing different successors of one revision via prov:isDerivedFrom. Each terminal revision of the generated branches is referenced by a rmo:Branch entity. The rmo:Master is a subclass pointing to the default graph. All these references point to copies of a full graph of this revision via rmo:fullGraph property. The centralised approach of R43ples can easily achieve the necessary uniqueness of the revision numbers. The revision numbers can follow di erent schemes, for example just ordinals or using a hash. We decided for a more complex naming scheme which indicates the position of a revision in the graph. For the system these are just strings for providing a human-friendly identi er without semantic meaning (although the revision number, not shown in gure 2, is also part of the URI, e.g. \3.1-22"). The users need to be able to retrieve the whole revision graph including the numbers of the revisions. With R43ples it is possible to receive this information like any other data via SPARQL queries directly on the revision graph <r43ples-revisions>. 3.3
Information from the MASTER revision is instantly available since the whole data set exists in the speci ed named graph. It is used when the client does not specify a revision. Therefore, it is likely that it will be accessed very often. However, other revisions must be generated dynamically as only the delta information is stored between two revisions. With respect to the revision to be generated, all triples of the add set must be added to the the previous revision and all triples of the delete set must be removed from the previous revision. R43ples accepts slightly enhanced SPARQL queries which allow to add the revision number for each speci ed graph in the SPARQL query. For each named graph g speci ed in a query, a temporary graph T Gg; r is generated for the speci ed revision r according to equation 1 (gx = full materialised revision x of graph g): nearestBranch
X revision i=r T Gg;r = gnearestBranch+ (deleteSetg;i addSetg;i) This simple formula can be mapped to a series of SPARQL queries as presented in the pseudo code below. It rsts creates a graph <graph -rev_g > merging all change sets. Afterwards it rewrites the query so it uses this new temporary graph instead of the speci ed one. The result of the SPARQL query on that graph is returned after cleaning up the temporary graph. def select_query(query): for (graph,rev_g) in query.graphs_and_revs(): sparql("COPY GRAPH <graph > \
TO GRAPH <graph -rev_g >") for rev in graph.path_to_revision(rev_g): sparql("REMOVE GRAPH <rev.add_set_graph >
FROM GRAPH <graph -rev_g >") sparql("ADD GRAPH <rev.delete_set_graph >
TO GRAPH <graph -rev_g >") query.replace(graph, "graph -rev_g ") result = sparql(query_string) for (graph,rev_g) in query.graphs_and_revs(): sparql("DROP GRAPH <graph -rev_g >") return result When considering the merging of revisions, it does not matter which previous revision is used to generate the merged revision due to the properties of SPARQL. An INSERT statement of an existing triple does not insert it a second time and a DELETE statement of a non-existing triple does not end in an error message. The add set A and delete set D of a revision with the set of triples Rm merged from revision with sets of triples R1 and R2 must comply with the rules from equations 2 and 3.
A = (RmnR1) [ (RmnR2) D = (R1nRm) [ (R2nRm) (1) (2)
Clients update revisions via the established SPARQL UPDATE command. This updates the revision graph with a new revision node which references the new change sets. The changes are both re ected in the new add and delete sets as well as in the updated full graph. However, updates can only be performed on the terminal sibling of a branch. If a client wants to update a revision which is not referenced by a branch, the commit is rejected. The client has to merge its local changes with the most recent information of the branch. Merging is the application of two di erent change sets to one entity. If the local merge is possible, the client can recommit these merged changes. The other option is to explicitly create a new branch for the local changes. The client cannot usually merge if it is unable to reconcile the changes. These con icts have to be resolved afterwards in order to get a common consolidated data model in the revision control system. Thus, the changes have to be combined or one change has to be selected in preference to the other. This is performed via an additional administrator interface on the server.
In a SPARQL query it has to be possible to determine the revision of the involved named graphs. Furthermore, update queries should contain information about the author and a commit message. Partly, this information could be embedded into the name of the graph. However, we strongly believe that loading identi ers with semantics would be a violation of the basic principles of Linked Data. Another option are new keywords or specifying this information as part of the WHERE clause as triple patterns like ?revision rmo:revisionOf <sampleGraph> ; rmo:revisionNumber "43". However, the latter one has the disadvantage that there is no clear distinction between the speci cation of revision information and SPARQL query pattern.
We decided to introduce the additional keyword REVISION SELECT ? s ?p ? o FROM <sampleGraph> REVISION "4 3 " WHERE f
? s ?p ? o . to SPARQL to add the necessary semantic. Furthermore, the update mechanisms need some meta information about the commit introduced by the keywords USER and MESSAGE. Finally, the creation of tags and branches is solved by the keywords BRANCH and TAG.
In a SELECT query the user can de ne the revision number by applying the FROM clause with the keyword REVISION. It can be a number representing a revision, a string representing a branch or tag (e.g. \master") or empty. When it is empty or the keyword REVISION is missing, the MASTER revision will be used as default. An exemplary query is shown in listing 1.
Updates (INSERT or DELETE queries) can only be executed on a branch speci ed by the branch name or the number of a revision referenced by a branch. In INSERT and DELETE queries the performing user must rst be de ned. Therefore the keyword USER is reserved. After the FROM respectively the INTO clause the keyword REVISION identi es the graph revision following the same approach as in a SELECT query. Furthermore, there could be attached a commit message following the keyword MESSAGE as shown in listing 2.
The REVISION parameter is necessary for the SPARQL endpoint to check to which branch revision a client wants to apply its changes. If the client wants to update a revision that is not directly referenced by a branch, the server will reject the commit. Then, the client needs to check if its data model is consistent with the new information from a branch revision. If so, it can resubmit its changes, or it can open a new branch if there is a con ict the client is not able to handle. If the branch revision of the server matches that of the client, the server will accept the change and create a new revision with the information provided. Then, the responding branch reference will be forwarded to this new revision.
Listing 3 depicts a SPARQL query for generating a new branch. In the example, a new branch is created with the information from revision 42. The same interface is available for creating a tag using the keyword TAG instead of BRANCH.
USER <mgraube> BRANCH <sampleGraph> REVISION "4 2 " TO "
F e a t u r e xyz " Listing 3: Query for branching from revision 42
graph-revision-number graph-revision-number-of-master
Revision of graph of last query Current MASTER revision number of graph The clients are kept aware of the recent MASTER revision in every SPARQL response. The HTTP response header is extended by additional elds which specify the current MASTER revision number and the revision number on which the query was executed for every named graph involved. Table 1 describes the construction of the parameter names. All underlined sub strings are replaced with the current named graph under version control. This information is not needed by the client for querying. Yet it provides the new revision number after a commit and is thus very useful for the client.
The concept was implemented as proof of concept and its source code is publicly available via GitHub5. The prototype is realised as a SPARQL proxy rather than a modi cation of an existing open-source SPARQL endpoint. The implementation works as a Java application. Jersey6 is used as RESTful (Representational State Transfer) Web service framework and grizzly7 as the web server while Virtuoso8 acts as triple store and SPARQL endpoint. A live demonstration system is running on http://eatld.et.tu-dresden.de:8890/ r43ples/sparql.
Figure 3 shows the system structure. If a client wants to use the revision control features of R43ples it has to send the SPARQL queries to R43ples' SPARQL endpoint instead of the triplestore's endpoint. Furthermore there is an administrator interface which acts as a test bed for functions that don't yet have a proper REST interface. These functions are controlled by a command line interface and perform complex management of the graphs under version control. R43ples stores no information about the revisions itself but 5https://github.com/plt-tud/r43ples 6https://jersey.java.net/ 7https://grizzly.java.net/ 8http://virtuoso.openlinksw.com/ CONSTRUCT f? s ?p ? o g WHERE f
GRAPH <NEW REV TEMP> f ? s ?p ? o g FILTER NOT EXISTS f GRAPH <LAST REV> f ? s ?p ? o g g uses a con gured triplestore which is accessed by the triple store interface. The communication is based on SPARQL queries. To ensure the integrity of the data, only the SPARQL proxy should have access to the di erent graphs which it creates. Access rights are de ned in the triple store. The clients need to know if the endpoint supports R43ples features in addition to standard SPARQL. Hence, R43ples copies the SPARQL 1.1 Service Description9 of the connected endpoint and adds sd:r43ples as further sd:Feature.
The implemented proxy SPARQL endpoint can also handle standard SPARQL queries. Of course, this raises the requirement that the revisioned graph shall be only edited by R43ples and its speci c queries. Otherwise inconsistencies would be generated. Virtuoso supports such access policies for the SPARQL endpoint, prohibiting write access to the <r43ples-revisions> graph and all graphs which are related to R43ples.
The generation and update of the version system information is completely implemented with the help of SPARQL queries. R43ples performs a SPARQL update on a temporary copy of the full graph of the speci ed branch. Afterwards, it retrieves all added triples with the SPARQL query from listing 4 which returns all triples which are in NEW-REV-TEMP but not in LAST-REV. After the same concept was used for the removed triples, the ADD and DELETE sets are constructed with the help of a SPARQL CONSTRUCT query. Then the new revision information is inserted in <r43ples-revisions> and the actual full graph is updated with the help of INSERT and DELETE queries. The administrator interface o ers an additional way for interacting with R43ples for those features which don't have a friendly REST interface yet. Those tasks are currently: Put an existing graph under revision management Import a new graph under version control Generate visualisation of the revision graph (yEd export) Set a new MASTER revision
Merge two revisions The admin interface currently supports turtle serialisation10 for the export and import of RDF data. The visualisation of the revisions, their connections and branches is done by creating a GraphML le which can be viewed with yEd11. 9http://www.w3.org/TR/sparql11-service-description/ 10http://www.w3.org/2007/02/turtle/primer/ 11http://www.yworks.com/de/products_yed_about.html The merging feature is still under construction while we are investigating di erent approaches for a user friendly interface.
An important metric for evaluating the usability of this concept is the response time of the service for R43ples queries in various con gurations. Therefore, we have measured the time between the request sent by the client and the response received using Apache jMeter12. We evaluated the operation time of R43ples in a complex setup on a 4 GB RAM system running a Virtuoso 7 as SPARQL endpoint connected to R43ples. We generated random data sets with sizes of 100, 1000, 10000 and 100000 triples. Then we created ten revisions for each data set with changes of 10 to 100 triples. Finally, we measured the response time for a simple SPARQL query (querying all triples and limiting them to ten results) dependent on all data sets, all revisions and all di erent change sizes. The measurement was repeated 20 times to capture random e ects such as computing load. Figure 4 presents some results showing the response time in comparison to variations of the three variables around a speci c setup (1000 triples in the data set, going back ve commits into the past with 50 triples changing in every commit). The left plot shows that the response time increases linearly with the number of commits plus a constant bias of some milliseconds. The size of the commit seems also to be almost linear to the response time as suggested by the middle plot. Even the size of the data set has linear in uence (note the logarithmic scale in the right plot).
A deeper analysis shows that the structure of the data set is not signi cant. The overhead for querying a revision that is available as full graph is about 10 ms in comparison to a direct SPARQL query and is thus almost negligible. However, if the revision has to be generated by R43ples, the dominant factors are the overall size of changes to be reversed and the size of the data set. Equation 4 lists a simple linear model which almost exactly re ects these ndings (R2 = 0:98) with the variables T as R43ples response time in milliseconds, SDS as data set size, SC as change size and P as path length to a full graph revision. Thus, in many application T would be of order O(SDS).
T = 100 + 0:06 SDS + 0:7 (P SC ) (4) The results makes sense since the algorithm has to duplicate the graph and then apply all changes. Both e orts are proportional to the size. As minor result R43ples can perform few revisions and big changes in each revision step better than lots of small changes assuming that the overall number of changed triples is the same. Furthermore, UPDATE query time increases linearly with the size of the committed change set.
The costs for a new revision S ;Revision (in additional triples) are almost proportional to the size of changes and independent from the complexity of previous revisions and the revision graph (S ;Revision = SC + 12). The additional xed 12http://jmeter.apache.org/ triples in <r43ples-revisions> (six for a revision; six for the commit) are negligible. The creation of a branch or a tag copies the full graph besides the addition of a xed number of triples (S ;Tag = SDS + 11; S ;Branch = SDS + 15).
Although the approach presented here solves most of the versioning problems, there are also some drawbacks. Named graphs are used extensively, mainly for storing di erences between revisions. This means that the use of named graphs for other purposes cannot be guaranteed. Those purposes could be structuring of information, access control or additional provenance information. One might ask if we need an additional context attribute as a fth element explicitly declared for revision control.
The concept is fully transparent for SPARQL clients which are not aware of the R43ples version control system. They can use the prototype as common SPARQL endpoint without additional features always working on the master revision. Clients can easily check if an endpoint supports R43ples query by evaluating the service description of the endpoint.
Clients will usually work on MASTER or other branches in order to get the most recent information. However, there could be situations when clients should continuously work on a speci c revision of a graph. Then, this revision of the graph should be tagged in order to store a full copy. A possible solution would be the automatic detection of such frequently used revisions and triggering of tag generation. Another drawback is the lack of support for blank nodes in the current implementation. You can't assume that blank nodes from di erent graphs with the same blank node identi ers are the same. For example, the blank nodes in the change sets are not equal to the ones in the full graph, prohibiting a correct application of the changes when generating an old revision. This can of course be solved by a prior Skolemization which should ideally be performed by the client or could also be achieved by an enhanced version of R43ples before executing a SPARQL query.
Currently, the generation of uncached revision follows a simple approach applying all changes from the rst successor until reaching the leaf of a branch. However, if there are many tags in the revision graph, it could be more e cient to use another revision path to generate this revision. Thus, one has to solve a shortest-path-problem.
Another point of discussion is the way of transferring the necessary additional information. Currently, the R43ples SPARQL server transports the MASTER revision as well as the relevant revisions of all involved graphs in the HTTP header. On the other hand, the R43ples clients transport information about the graph revisions in the HTTP body. An alternative would be to transfer both information in the HTTP body and thus on the same level. This would need an extension of the SPARQL result model.
The integration of version control into the existing Semantic Web tool environment is not easy. A basic requirement is that these tools don't work on a le basis but on a triplestore with SPARQL interface. Under these circumstances it would be no big problem to exchange the SPARQL interface with the slightly enhanced R43ples interface.
The performance of the prototype limits the application to
medium sized data sets. Queries on data sets with more
than a few thousand triples take longer than most users
are willing to wait. This can be solved by splitting large
data sets into smaller ones and by directly implementing the
concept into the SPARQL endpoint which should improve
performance considerably. Another promising approach we
are currently working on is the use of enhanced SPARQL
rewriting in order to perform the query taking into account
the full graph and all change sets in one request Hence, the
generation of the whole graph for the speci ed revision is
not necessary which really takes long time for big datasets.
Finally, security is a crucial point for all industrial
applications. We rely on the adaptable security mechanisms of
existing triple stores and SPARQL endpoints. These should
only provide information about the revision tree and the
revisioned data sets to authenticated and authorised users.
This could be achieved for example by the approach
suggested by [
We have presented a concept for a semantic revision control system for Linked Data which uses the capabilities of SPARQL. The implemented prototype works well for querying cached graphs. The generation of uncached graphs is sufcient for small to medium sized data sets. The advantage of our approach is that it is completely based on semantics and thus the information about revisions can be retrieved via SPARQL. Furthermore, SPARQL is used as access mechanism with only slight adaptations in order to ensure the semantic use of revision information while keeping the query compatible to standard SPARQL.
However, this concept still needs further research. Our next steps will involve investigating di erent merging approaches and an intensive consideration of how this concept can be integrated into existing tools.
This research was partly funded by the European Commission on the grant number 284928 (ComVantage).