Towards fully-fledged archiving for RDF datasets

We define an RDF graph G as a set of triples t = ⟨ s , p , o ⟩ , where s ∈ I ∪ B , p ∈ I , and o ∈ I ∪ L ∪ B are the subject, predicate, and object of t, respectively. Here, I , L , and B are sets of IRIs (entity identifiers), literal values (e.g., strings, integers, dates), and blank nodes (anonymous entities) [66]. The notion of a graph is based on the fact that G can be modeled as a directed labeled graph where the predicate p of a triple denotes a directed labeled edge from node s to node o. The RDF W3C standard [66] defines a named graph as an RDF graph that has been associated to a label l ( G ) = g ∈ I ∪ B . The function l ( · ) returns the associated label of an RDF graph, if any. Table 1 provides the relevant notation related to RDF graphs.

2.2. RDF graph archives

Intuitively, an RDF graph archive is a temporally-ordered collection of all the states an RDF graph has gone through since its creation. More formally, a graph archive A = { G s , G s + i , … , G s + n − 1 } is an ordered set of RDF graphs, where each G i is a revision or version with revision number i ∈ N , and G s ( s ⩾ 0 ) is the graph archive’s initial revision. A non-initial revision G i ( i > s ) is obtained by applying an update or changeset u i = ⟨ u i + , u i − ⟩ to revision G i − 1 . The sets u i + , u i − consist of triples that should be added and deleted respectively to and from revision G i − 1 such that u i + ∩ u i − = ∅ . In other words, G i = u i ( G i − 1 ) = ( G i − 1 ∪ u i + ) ∖ u i − . Figure 1 provides a toy RDF graph archive A that models the evolution of the information about the country members of the United Nations (UN) and their diplomatic relationships (:dr). The archive stores triples such as ⟨ :USA, a, :Country ⟩ or ⟨ :USA, :dr, :Cuba ⟩, and consists of two revisions { G 0 , G 1 } . G 1 is obtained by applying update u 1 to the initial revision G 0 . We extend the notion of changesets to arbitrary pairs of revisions i, j with i < j , and denote by u i , j = ⟨ u i , j + , u i , j − ⟩ the changeset such that G j = u i , j ( G i ) .

OPEN IN VIEWER

Fig. 1.

Two revisions G 0 , G 1 and a changeset u 1 of an RDF graph archive A.

We remark that a graph archive can also be modeled as a collection of 4-tuples ⟨ s , p , o , ρ ⟩ , where ρ ∈ I is the RDF identifier of revision i = rv ( ρ ) and rv ⊂ I × N is a function that maps revision identifiers to natural numbers. We also define the function ts ⊂ I × N that associates a revision identifier ρ to its commit time, i.e., the timestamp of application of changeset u i . Some solutions for RDF archiving [8,31,33,54,75,79] implement this logical model in different ways and to different extents. For example, R43ples [33], R&WBase [79] and Quit Store [8] store changesets and/or their associated metadata in additional named graphs using PROV-O [78]. In contrast, x-RDF-3X [54] stores the temporal metadata in special indexes that optimize for concurrent updates at the expense of temporal consistency, i.e., revision numbers may not always be in concordance with the timestamps.

In contrast to an RDF graph archive, an RDF dataset is a set D = { G 0 , G 1 , … , G m } of named graphs. Differently from revisions in a graph archive, we use the notation G k for the k-th graph in a dataset, whereas G i k denotes the i-th revision of G k . The notation related to RDF datasets is detailed in Table 2. Each graph G k ∈ D has a label l ( G k ) = g k ∈ I ∪ B . The exception to this rule is G 0 , known as the default graph [66], which is unlabeled.

Most of the existing solutions for RDF archiving can handle the history of a single graph. However, scenarios such as data warehousing [20,21,30,35,36,43–45,47] may require to keep track of the common evolution of an RDF dataset, for example, by storing the addition and removal timestamps of the different RDF graphs in the dataset. Analogously to the definition of graph archives, we define a dataset archive A = { D 0 , D 1 , … , D l − 1 } as a temporally ordered collection of RDF datasets. The j-th revision of A ( j > 1 ) can be obtained by applying a dataset update U j = { u ˆ j , u j 0 , u j 1 , … u j m } to revision D j − 1 = { G j − 1 0 , G j − 1 1 , … G j − 1 m } . U j consists of an update per graph plus a special changeset u ˆ j = ⟨ u ˆ j + , u ˆ j − ⟩ that we call the graph changeset ( u ˆ j + ∩ u ˆ j − = ∅ ). The sets u ˆ j + , u ˆ j − store the labels of the graphs that should be added and deleted in revision j respectively. If a graph G k is in u ˆ j − (i.e., it is scheduled for removal), then G k as well as its corresponding changeset u j k ∈ U j must be empty. It follows that we can obtain revision D j by (i) applying the individual changesets u j k ( G j − 1 k ) for each 0 ⩽ k ⩽ m , (ii) removing the graphs in u ˆ j − , and (iii) adding the graphs in u ˆ j + .

Figure 2 illustrates an example of a dataset archive with two revisions D 0 and D 1 . D 0 is a dataset with graphs { G 0 0 , G 0 1 } both at local revision 0. The dataset update U 1 generates a new global dataset revision D 1 . U 1 consists of three changesets: u 1 0 that modifies the default graph G 0 , u 1 1 that leaves G 1 untouched, and the graph update u ˆ 2 that adds graph G 2 to the dataset and initializes it at revision s = 1 (denoted by G 1 2 ).

As proposed by some RDF engines [57,77], we define the master graph G M ∈ D (with label M) as the RDF graph that stores the metadata about all the graphs in an RDF dataset D. If we associate the creation of a graph G k with label g k to a triple of the form ⟨ g k , rdf:type , η :Graph ⟩ in G M for some namespace η, then we can model a dataset archive as a set of 5-tuples ⟨ s , p , o , ρ , ζ ⟩ . Here, ρ ∈ I is the RDF identifier of the local revision of the triple in an RDF graph with label g = l ( ρ ) (Table 2). Conversely, ζ ∈ I identifies a (global) dataset revision j = rv ( ζ ) . Likewise, we overload the function ts ( ζ ) (defined originally in Table 1) so that it returns the timestamp associated to the dataset revision identifier ζ. Last, we notice that the addition of a non-empty graph to a dataset archive generates two revisions: one for creating the graph, and one for populating it. A similar logic applies to graph deletion.

OPEN IN VIEWER

Fig. 2.

A dataset archive A with two revisions D 0 , D 1 . The first revision contains two graphs, the default graph G 0 and G 1 . The dataset update U ˆ 1 (i) modifies G 0 , (ii) leaves G 1 untouched, and (iii) and creates a new graph G 2 , all with local revision 1.

SPARQL 1.1 is the W3C standard language to query RDF data [71]. For the sake of brevity, we do not provide a rigorous definition of the syntax and semantics of SPARQL queries; instead we briefly introduce the syntax of a subset of SELECT queries and refer the reader to the official specification [71]. SPARQL is a graph-based language whose building blocks are triple patterns. A triple pattern t ˆ is a triple ⟨ s ˆ , p ˆ , o ˆ ⟩ ∈ ( I ∪ B ∪ V ) × ( I ∪ V ) × ( I ∪ B ∪ L ∪ V ) , where V is a set of variables such that ( I ∪ B ∪ L ) ∩ V = ∅ (variables are always prefixed with ? or $). A basic graph pattern (abbreviated BGP) G ˆ is the conjunction of a set of triple patterns { t ˆ 1 . t ˆ 2 … . t ˆ m }, e.g., { ?s a :Person . ?s :nationality :France }

When no named graph is specified, the SPARQL standard assumes that the BGP is matched against the default graph in the RDF dataset. Otherwise, for matches against specific graphs, SPARQL supports the syntax GRAPH g ¯ { G ˆ } , where g ¯ ∈ I ∪ B ∪ V . In this paper we call this, a named BGP denoted by G ˆ g ¯ . A SPARQL select query Q on an RDF dataset has the basic form “SELECT V (FROM NAMED g ¯ 1 FROM NAMED g ¯ 2 … ) WHERE { G ˆ ′ G ˆ ″ … G ˆ g ¯ 1 G ˆ g ¯ 2 … } , with projection variables V ⊂ V . SPARQL supports named BGPs G ˆ g ¯ with variables g ¯ ∈ V . In some implementations [57,77] the bindings for those variables originate from the master graph G M . The BGPs in the expression can contain FILTER conditions, be surrounded by OPTIONAL clauses, and be combined by means of UNION clauses.

2.5. Queries on archives

Queries on graph/dataset archives may combine results coming from different revisions in the history of the data collection in order to answer an information need. The literature defines five types of queries on RDF archives [27,75]. We illustrate them by means of our example graph archive from Fig. 1.

Version Materialization. VM queries are standard queries run against a single revision, such as what was the list of countries according to the UN at revision j?

Low-level changes are changes at the triple level. Indicators for low-level changes focus on additions and deletions of triples and vocabulary elements. The vocabulary Υ ( D ) ⊂ I ∪ L ∪ B of an RDF dataset D is the set of all the terms occurring in triples of the dataset. Tracking changes in the number of triples rather than in the raw size of the RDF dumps is more informative for data analytics, as the latter option is sensitive to the serialization format. Moreover an increase in the vocabulary of a dataset can provide hints about the nature of the changes and the novelty of the data incorporated in a new revision. All metrics are defined by Fernández et al. [27] for pairs of revisions i, j with j > i .

Change ratio The authors of BEAR [27] define the change ratio between two revisions i and j of an RDF graph G as (1) δ i , j ( G ) = | u i , j + | + | u i , j − | | G i ∪ G j | . δ i , j compares the size of the changes between two revisions w.r.t. the revisions’ joint size. Large values for δ i , j denote important changes in between the revisions. For a more fine-grained analysis, Fernández et al. [27] also proposes the insertion and deletion ratios: (2) δ i , j + = | u i , j + | | G i | (3) δ i , j − = | u i , j − | | G i | .

We now adapt these metrics for RDF datasets. For this purpose, we define the size of a dataset D as sz ( D ) = ∑ G ∈ D | G | and the size of a dataset changeset U as sz ( U ) = sz ( U + ) + sz ( U − ) with sz ( U + ) = ∑ u ∈ U | u + | and sz − ( U ) = ∑ u ∈ U | u − | . With these definitions, the previous formulas can be ported to RDF datasets as follows: (4) δ i , j ( D ) = sz ( U ) ∑ G ∈ D i ∩ D j | G i ∪ G j | + ∑ G ∈ D i △ D j | G | (5) δ i , j + ( D ) = sz ( U + ) sz ( D i ) (6) δ i , j − ( D ) = sz ( U − ) sz ( D i )

Here, D i △ D j denotes the symmetric difference between the sets of RDF graphs in revisions i and j.

Vocabulary dynamicity The vocabulary dynamicity for two revisions i and j of an RDF graph is defined as [27]: (7) vdyn i , j ( G ) = | Υ ( u i , j ) | | Υ ( G i ) ∪ Υ ( G j ) | Υ ( u i , j ) is the set of vocabulary terms – IRIs, literals, or blank nodes – in the changeset u i , j (Table 1). The literature also defines the vocabulary dynamicity for insertions ( vdyn+ i , j ) and deletions ( vdyn- i , j ): (8) vdyn+ i , j ( G ) = | Υ ( u i , j + ) | | Υ ( G i ) ∪ Υ ( G j ) | (9) vdyn- i , j ( G ) = | Υ ( u i , j − ) | | Υ ( G i ) ∪ Υ ( G j ) | . The formulas are analogous for RDF datasets if we replace G by D and u i , j by U i , j .

Growth ratio The grow ratio is the ratio between the number of triples in two revisions i, j. It is calculated as follows for graphs and datasets: (10) Γ i , j ( G ) = | G j | | G i | (11) Γ i , j ( D ) = sz ( D j ) sz ( D i ) .

3.2. High-level changes

A high-level change confers semantics to a changeset. For example, if an update consists of the addition of triples about an unseen subject, we can interpret the triples as the addition of an entity to the dataset. High-level changes provide deeper insights about the development of an RDF dataset than low-level changes. In addition, they can be domain-dependent. Some approaches [59,69] have proposed vocabularies to describe changesets in RDF data as high-level changes. Since our approach is oblivious to the domain of the data, we propose a set of metrics on domain-agnostic high-level changes.

Entity changes RDF datasets describe real-world entities s by means of triples ⟨ s , p , o ⟩ . Hence, an entity is a subject for the sake of this analysis. We define the metric entity changes between revisions i , j in an RDF graph as: (12) ec i , j ( G ) = | σ i , j ( G ) | = | σ i , j + ( G ) ∪ σ i , j − ( G ) | In the formula, σ i , j + is the set of added entities, i.e., the subjects present in Υ ( G j ) but not in Υ ( G i ) (analogously the set of deleted entities σ i , j − is defined by swapping the roles of i and j). This metric can easily be adapted to an RDF dataset D if we define ec ( G ) (with no subscripts) as the number of different subjects in a graph G. It follows that, ec i , j ( D ) = ∑ G ∈ D i ∩ D j ec i , j ( G ) (13) + ∑ G ∈ D i △ D j ec ( G ) .

We also propose the triple-to-entity-change score, that is, the average number of triples that constitute a single entity change. It can be calculated as follows for RDF graphs: (14) ect i , j ( G ) = | ⟨ s , p , o ⟩ ∈ u i , j + ∪ u i , j − : s ∈ σ i , j ( G ) | ec i , j ( G ) We port this metric to RDF datasets by first defining U + = ⋃ u ∈ U + u and U − = ⋃ u ∈ U − u and plugging them into the formula for ect i , j : (15) ect i , j ( D ) = | ⟨ s , p , o ⟩ ∈ U i , j + ∪ U i , j − : s ∈ σ i , j ( D ) | ec i , j ( D )

Object updates and orphan object additions/deletions An object update in a changeset u i , j is defined by the deletion of a triple ⟨ s , p , o ⟩ and the addition of a triple ⟨ s , p , o ′ ⟩ with o ≠ o ′ . Once a triple in a changeset has been assigned to a high-level change, the triple is consumed and cannot be assigned to any other high-level change. We define orphan object additions and deletions respectively as those triples ⟨ s + , p + , o + ⟩ ∈ u i , j + and ⟨ s − , p − , o − ⟩ ∈ u i , j − that have not been consumed by any of the previous high-level changes. The dataset counterparts of these metrics for two revisions i, j can be calculated by summing the values for each of the graphs in D i ∩ D j .

Table 3 summarizes all the metrics defined by RDFev.

We chose the YAGO [74], DBpedia [9], and Wikidata [23] knowledge bases for our analysis, because of their large size, dynamicity, and central role in the Linked Open Data initiative. We build an RDF graph archive by considering each release of the knowledge base as a revision. None of the datasets is provided as a monolithic file, instead they are divided into themes. These are subsets of triples of the same nature, e.g., triples with literal objects extracted with certain extraction methods. We thus focus on the most popular themes. For DBpedia we use the mapping-based objects and mapping-based literals themes, which are available from version 3.5 (2015) onwards. Additionally, we include the instance-types theme as well as the ontology. For YAGO, we use the knowledge base’s core, namely, the themes facts, meta facts, literal facts, date facts, and labels available from version 2 (v.1.0 was not published in RDF). As for Wikidata, we use the simple-statements of the RDF Exports [68] in the period from 2014-05 to 2016-08. These dumps provide a clean subset of the dataset useful for applications that rely mainly on Wikidata’s encyclopedic knowledge. All datasets are available for download in the RDFev’s website https://relweb.cs.aau.dk/rdfev. Table 4 maps revision numbers to releases for the sake of conciseness in the evolution analysis.

Change ratio Figures 3(a), 3(d) and 3(g) depict the evolution of the change, insertion, and deletion ratios for our experimental datasets. Up to the release 3.9 (rev. 5), DBpedia exhibits a steady growth with significantly more insertions than deletions. Minor releases such as 3.5.1 (rev. 1) are indeed minor in terms of low-level changes. Release 2015-04 (rev. 6) is an inflexion point not only in terms of naming scheme (see Table 4): the deletion rate exceeds the insertion rate and subsequent revisions exhibit a tight difference between the rates. This suggests a major design shift in the construction of DBpedia from revision 6.

As for YAGO, the evolution reflects a different release cycle. There is a clear distinction between major releases (3.0.0 and 3.1, i.e., rev. 1 and 4) and minor releases (3.0.1 and 3.0.2, i.e., rev. 2 and 3). The magnitude of the changes in major releases is significantly higher for YAGO than for any DBpedia release. Minor versions seem to be mostly focused on corrections, with a low number of changes.

Contrary to the other datasets, Wikidata shows a slowly decreasing change ratio that fluctuates between 5% (rev. 10) and 33% (rev. 3) within the studied period of 2 years.

Vocabulary dynamicity As shown in Figs 3(b), 3(e), and 3(h), the vocabulary dynamicity is, not surprisingly, correlated with the change ratio. Nevertheless, the vocabulary dynamicity between releases 3.9 and 2015-14 (rev. 5 and 6) in DBpedia did not decrease. This suggests that DBpedia 2015-04 contained more entities, but fewer – presumably noisy – triples about those entities. The major releases of YAGO (rev. 1 and 4) show a notably higher vocabulary dynamicity than the minor releases. As for Wikidata, slight spikes in dynamicity can be observed at revisions 4 and 9, however this metric remains relatively low in Wikidata compared to the others bases.

Growth ratio Figures 3(c), 3(f), and 3(i) depict the growth ratio of our experimental datasets. In all cases, this metric is mainly positive with low values for minor revisions. As pointed out by the change ratio, the 2015-04 release in DBpedia is remarkable as the dataset shrank and was succeeded by more conservative growth ratios. This may suggest that recent DBpedia releases are more curated. We observe that YAGO’s growth ratio is significantly larger for major versions. This is especially true for the 3.0.0 (rev. 1) release that doubled the size of the knowledge base.

4.3. High-level evolution analysis

OPEN IN VIEWER

Fig. 4.

Entity changes and object updates.

4.3.2. Object updates and orphan object additions/deletions

OPEN IN VIEWER

Fig. 5.

Orphan object additions and deletions.

We present the evolution of the number of object updates for our experimental datasets in Figs 4(c), 4(f), and 4(i). For DBpedia, the curve is consistent with the change ratio (Fig. 3(a)). In addition to a drop in size, the 2015-04 release also shows the highest number of object updates, which corroborates the presence of a drastic redesign of the dataset.

The results for YAGO are depicted in Fig. 4(f), where we see larger numbers of object updates compared to major releases in DBpedia. This is consistent with the previous results that show that YAGO goes through bigger changes between releases. The same trends are observed for the number of orphan object additions and deletions in Figs 5(a) and 5(b). Compared to the other two datasets, Wikidata’s number of object updates, shown in Fig. 4(i), is much lower and constant throughout the stream of revisions.

Finally, we remark that in YAGO and DBpedia, object updates are 4.8 and 1.8 times more frequent than orphan additions and deletions. This entails that the bulk of editions in these knowledge bases aims at updating existing object values. This behavior contrasts with Wikidata, where orphan object updates are 3.7 times more common than proper object updates. As depicted in Fig. 5(c), Wikidata exhibits many more orphan object updates than the other knowledge bases. Moreover, orphan object additions are 19 times more common than orphan object deletions.

In this section we have conducted a study of the evolution of three large RDF knowledge bases using our proposed framework RDFev, which resorts to a domain-agnostic analysis from two perspectives: At the low-level it studies the dynamics of triples and vocabulary terms across different versions of an RDF dataset, whereas at the high-level it measures how those low-level changes translate into updates to the entities described in the experimental datasets. All in all, we have identified different patterns of evolution. On the one hand, Wikidata exhibits a stable release cycle in the studied period, as our metrics did not exhibit big fluctuations from release to release. On the other hand, YAGO and DBpedia have a release cycle that distinguishes between minor and major releases. Major releases are characterized by a large number of updates in the knowledge base and may not necessarily increase its size. Conversely, minor releases incur in at least one order of magnitude fewer changes than major releases and seem to focus on improving the quality of the knowledge base, for instance, by being more conservative in the number of triple and entity additions. Unlike YAGO, DBpedia has shown decreases in size across releases. We argue that an effective solution for large-scale RDF archiving should be able to adapt to different patterns of evolution.

5.1. RDF archiving systems

There are plenty of systems to store and query the history of an RDF dataset. Except for a few approaches [7,8,33,81], most available systems support archiving of a single RDF graph. Ostrich [75], for instance, manages quads of the form ⟨ s , p , o , rv ( ρ ) ⟩ . Other solutions do not support revision numbers and use the ρ-component ρ ∈ I to model temporal metadata such as insertion, deletion, and validity timestamps for triples [31]. In this paper we make a distinction between insertion/deletion timestamps for triples and validity intervals. While the former are unlikely to change, the latter are subject to modifications because they constitute domain information, e.g., the validity of a marriage statement. This is why the general data model introduced in Section 2 only associates revision numbers and commit timestamps to the fourth component ρ, whereas other types of metadata are still attached to the graph label g = l ( ρ ) . We summarize the architectural spectrum of RDF archiving systems in Table 5 where we characterize the state-of-the-art approaches according to the following criteria:

In the following, we discuss further details of the state-of-the-art systems, grouped by their storage paradigms.

Multiple research endeavors have proposed alternatives to succinctly formulate queries on RDF archives. The BEAR benchmark [27] uses AnQL to express the query types described in Section 2.5. AnQL [82] is a SPARQL extension based on quad patterns ⟨ s ˆ , p ˆ , o ˆ , g ˆ ⟩ . AnQL is more general than SPARQL-T (proposed by RDF-TX [31]) because the g ˆ -component can be bound to any term u ∈ I ∪ L (not only time objects). For instance, a DM query asking for the countries added at revision 1 to our example RDF dataset from Fig. 1 could be written as follows:

T-SPARQL [32] is a SPARQL extension inspired by the query language TSQL2 [72]. T-SPARQL allows for the annotation of groups of triple patterns with constraints on temporal validity and commit time, i.e., it supports both time-intervals and timestamps as time objects. T-SPARQL defines several comparison operators between time objects, namely equality, precedes, overlaps, meets, and contains. Similar extensions [12,62] also offer support for geo-spatial data.

SPARQ-LTL [28] is a SPARQL extension that makes two assumptions, namely that (i) triples are annotated with revision numbers, and (ii) revisions are accessible as named graphs. When no revision is specified, BGPs are iteratively matched against every revision. A set of clauses on BGPs can instruct the SPARQL engine to match a BGP against other revisions at each iteration. For instance the clause PAST in the expression PAST{ q } MINUS { q } with q = ⟨ ?x a :Country⟩ will bind variable ?x to all the countries that were ever deleted from the RDF dataset, even if they were later added.

5.3. Benchmarks and tools for RDF archives

BEAR [27] is the state-of-the-art benchmark for RDF archive solutions. The benchmark provides three real-world RDF graphs (called BEAR-A, BEAR-B, and BEAR-C) with their corresponding history, as well as a set of VM, DM, and V queries on those histories. In addition, BEAR allows system designers to compare their solutions with baseline systems based on different storage strategies (IC, CB, TB, and hybrids TB/CB, IC/CB) and platforms (Jena TDB and HDT). Despite its multiple functionalities and its dominant position in the domain, BEAR has some limitations: (i) It assumes single-graph RDF datasets; (ii) it does not support CV and CD queries, moreover VM, DM, and V queries are defined on single triple patterns; and (iii) it cannot simulate datasets of arbitrary size and query workloads.

EvoGen [48] tackles the latter limitation by extending the Lehigh University Benchmark (LUBM) [34] to a setting where both the schema and the data evolve. Users cannot only control the size and frequency of that evolution, but can also define customized query workloads. EvoGen supports all the types of queries on archives presented in Section 2.5 on multiple triple patterns.

A recent approach [76] proposes to use FCA (Formal Concept Analysis) and several data fusion techniques to produce summaries of the evolution of entities across different revisions of an RDF archive. A summary can, for instance, describe groups of subjects with common properties that change over time. Such summaries are of great interest for data maintainers as they convey edition patterns in RDF data through time.

6.1. Functionality analysis

As depicted in Table 5, existing RDF archiving solutions differ greatly in design and functionality. The first works [18,54,81] offered mostly storage of old revisions and support for basic VM queries. Consequently, subsequent efforts focused on extending the query capabilities and allowing for concurrent updates as in standard version control systems [8,33,46,79]. Such solutions are attractive for data maintainers in collaborative projects, however they still lack scalability, e.g., they cannot handle large datasets and changesets, besides conflict management is still delegated to users. More recent works [19,75] have therefore focused on improving storage and querying performance, alas, at the expense of features. For example, Ostrich [75] is limited to a single snapshot and delta chain. In addition to the limitations in functionality, Table 5 shows that most of the existing systems are not available because their source code is not published. While this still leaves us with Ostrich [75], Quit Store [8], R&WBase [79], R43ples [33] and x-RDF-3X as testable solutions, only [75] was able to run on our experimental datasets. To carry out a fair comparison with the other systems, we tried Quit Store in the persistence mode, which ingests the data graphs into main memory at startup – allowing us to measure ingestion times. Unfortunately, the system crashes for all our experimental datasets.7

We evaluate the performance of Ostrich on our experimental datasets in terms of storage space, ingestion time – the time to generate a new revision from an input changeset – and query response time. The changesets were computed with RDFev from the different versions of DBpedia, YAGO, and Wikidata (Table 4). All the experiments were run on a server with a 4-core CPU (Intel Xeon E5-2680 v3@2.50 GHz) and 64 GB of RAM.

OPEN IN VIEWER

Fig. 6.

Ostrich’s performance on multiple revisions of DBpedia and YAGO.

Storage space Figure 6(a) shows the amount of storage space (in GB) used by Ostrich for the selected revisions of our experimental datasets. We provide the raw sizes of the RDF dumps of each revision for reference. Storing each version of YAGO separately requires 36 GB, while Ostrich uses only 4.84 GB. For DBpedia compression goes from 39 GB to 5.96 GB. As for Wikidata, it takes 131 GB to stores the raw files, but only 7.88 GB with Ostrich. This yields a compression rate of 87% for YAGO, 84% for DBpedia and 94% for Wikidata. This space efficiency is the result of using HDT [25] for snapshot storage, as well as compression for the delta chains.

Ingestion time Figure 6(b) shows Ostrich’s ingestion times. We also provide the number of triples of each revision as reference. The results suggest that this measure depends both on the changeset size, and the length of the delta chain. However, the latter factor becomes more prominent as the length of the delta chain increases. For example, we can observe that Ostrich requires ∼22 hours to ingest revision 9 of DBpedia (2.43M added and 2.46M deleted triples) while it takes only ∼14 hours to ingest revision 5 (12.85M added and 5.95M deleted triples). This confirms the trends observed in [75] where ingestion time increases linearly with the number of revisions. This is explained by the fact that Ostrich stores the i-th revision of an archive as a changeset of the form u 0 , i . In consequence, Ostrich’s changesets are constructed from the triples in all previous revisions, and can only grow in size. This fact makes it unsuitable for very long histories.

Query runtime We run Ostrich on 100 randomly generated VM, V, and DM queries on our experimental datasets. Ostrich does not support queries on full BGPs natively, thus the queries consisted of single triple patterns of the most common forms, namely ⟨ ?, p, ? ⟩, ⟨ s, p, ? ⟩, and ⟨ ?, p, o ⟩ in equal numbers. We also considered queries ⟨ ?, <top p>, o ⟩, where <top p> corresponds to the top 5 most common predicates in the dataset. Revision numbers for all queries were also randomly generated. Table 6 shows Ostrich’s average runtime in seconds for the different types of queries. We set a timeout of 1 hour for each query, and show the number of timeouts in parentheses next to the runtime, which excludes queries that timed out. We observe that Ostrich is roughly one order of magnitude faster on YAGO than on DBpedia and Wikidata. To further understand the factors that impact Ostrich’s runtime, we computed the Spearman correlation score between Ostrich’s query runtime and a set of features relevant to query execution. These features include the length of the delta chain, the average size of the relevant changesets, the size of the initial revision, the average number of deleted and added triples in the changesets, and the number of query results. The results show that the most correlated features are the length of the delta chain, the standard deviation of the changeset size, and the average number of deleted triples. This suggests that Ostrich’s runtime performance will degrade as the history of the archive grows and that massive deletions actually aggravate that phenomenon. Finally, we observe some timeouts in YAGO in contrast to DBpedia and Wikidata. We believe this is mainly caused by the sizes of the changesets, which are on average of 3.72GB for YAGO, versus 2.09GB for DBpedia and 1.86GB for Wikidata. YAGO’s changesets at revisions 1 and 4 are very large as shown in Section 4.

7.1. Functionalities

Global and local history Our survey in Section 5.1 shows that R43ples [33] and Quit Store [8] are the only available solutions that support both archiving of the local and joint (global) history of multiple RDF graphs. We argue that such a feature is vital for proper RDF archiving: It is not only of great value for distributed version control in collaborative projects, but can also be useful for the users and maintainers of data warehouses. Conversely, existing solutions are strictly focused on distributed version control and their Git-based architectures make them unsuitable to archive the releases of large datasets such as YAGO, DBpedia, or Wikidata as explained in Section 6. From an engineering and algorithmic perspective, this implies to redesign RDF solutions to work with 5-tuples instead of triples. We discuss the technical challenges of such requirement in Section 7.2.

OPEN IN VIEWER

Fig. 7.

Two logical models to handle metadata in RDF archives. The namespace prov: corresponds to the PROV-O namespace.

Temporal domain-specific vs. revision metadata Systems and language extensions for queries with time constraints [31,32], treat both domain-specific metadata (e.g., triple validity intervals) and revision-related annotations (e.g., revision numbers) in the same way. We highlight, however, that revision metadata is immutable and should therefore be logically placed at a different level. In this line of thought we propose to associate revision metadata for graphs and datasets, e.g., commit time, revision numbers, or branching & tagging information, to the local and global revision identifiers ρ and ζ, whereas depending on the application, domain-specific time objects could be modeled either as statements about the revisions or as statements about the graph labels g = l ( ρ ) . The former alternative enforces the same temporal domain-specific metadata to all the triples added in a changeset, whereas the latter option makes sense if all the triples with the same graph label are supposed to share the same domain-specific information – which can still be edited by another changeset on the master graph. We depict both alternatives in Fig. 7. We remark that such associations are only defined at the logical level.

Provenance Revision metadata is part of the history of a triple within a dataset. Instead, its complete history is given by its workflow provenance. The W3C offers the PROV-O ontology [78] to model the history of a triple from its sources to its current state in an RDF dataset. Pretty much like temporal domain-specific metadata, provenance metadata can be logically linked to either the (local or global) revision identifiers or to the graph labels (Fig. 7). This depends on whether we want to define provenance for changesets because the triples added to an RDF graph may have different provenance workflows. A hybrid approach could associate a default provenance history to a graph and use the revision identifiers to override or extend that default history for new triples. Moreover, the global revision identifier ζ provides an additional level of metadata that allow us to model the provenance of a dataset changeset.

Concurrent updates & modularity We can group the existing state-of-the-art solutions in three categories regarding their support for concurrent updates, namely (i) solutions with limited or no support for concurrent updates [7,19,31,64,75], (ii) solutions inspired by version control systems such as Git [8,33,46,79,81], and (iii) approaches with full support for highly concurrent updates [54]. Git-like solutions are particularly interesting for collaborative efforts such as DBpedia, because it is feasible to delegate users the task of conflict management. Conversely, fully automatically constructed KBs such as NELL [17] or data-intensive (e.g., streaming) applications may need the features of solutions such as x-RDF-3X [54]. Consequently, we propose a modular design that separates the concurrency layer from the storage backend. Such a middleware could take care of enforcing a consistency model for concurrent commits either automatically or via user-based conflict management. The layer could also manage the additional metadata for features such as branching and tagging. In that light, collaborative version control systems for RDF [8,33,79] become an application of fully-fledged RDF archiving.

Formats for publication and querying A fully functional archiving solution should support the most popular RDF serialization formats for data ingestion and dumping. For metadata enhanced RDF, this should include support for N-quads, singleton properties, and RDF-star. Among those, RDF-star [37] is the only one that can natively support multiple levels of metadata (still in a very verbose fashion). For example RDF-star could serialize the tuple ⟨:USA, :dr, :Cuba, ρ , ζ ⟩ with graph label (:gl) l ( ρ ) = :UN and global timestamp (:ts) ts ( ζ ) = 2020-07-09 as follows:

<<<:USA :dr :Cuba> :gl :UN> :ts “2020-07-09”ˆˆxsd:date>

The authors of [37] propose this serialization as part of the Turtle-star format. Moreover, they propose SPARQL-star that allows for nested triple patterns. While SPARQL-star enables the definition of metadata constraints at different levels, a fully archive-compliant language could offer further syntactic sugar such as the clauses REVISION [7,33] or DELTA to bind the variables of a BGP to the data in particular revisions or deltas. We propose to build such an archive-compliant language upon SPARQL-star.

Support for different types of archive queries Most of the studied archiving systems can answer all the query types defined in the literature of RDF archives [27,75]. That said, more complex queries such as CD and CV queries, or queries on full BGPs are sometimes supported via query middlewares and external libraries [8,75]. We endorse this design philosophy because it eases modularity. Existing applications in mining archives [42,60,61] already benefit from support for V, VM, and DM queries on single triple patterns. By guaranteeing scalable runtime for such queries, we can indirectly improve the runtime of more complex queries. Further optimizations can be achieved by proper query planning.

Trade-offs on storage, query runtime, and ingestion time RDF archiving differs from standard RDF management in an even more imperative need for scalability, in particular storage efficiency. As shown by Taelman et al. [75], the existing storage paradigms shine at different types of queries. Hence, supporting arbitrary queries while being storage-efficient requires the best from the IC, CB, FB, and TB philosophies. A hybrid approach, however, will inevitably be more complex and introduce further parameters and trade-offs. The authors of Ostrich [75], for instance, chose to benefit faster version materialization via redundant deltas at the expense of larger ingestion times. Users requiring shorter ingestion times could, on the other hand, opt for non-redundant changesets, or lazy non-asynchronous ingestion (at the expense of data availability). We argue that the most crucial algorithmic challenge for a CB archiving solution is to decide when to store a revision as a snapshot or as a delta, which is tantamount to trading disk space for faster VM queries. This could be formulated as an (multi-objective) minimization problem whose objective might be a function of response time for triple patterns in VM, CV and V queries with constraints on available disk space and average ingestion time. When high concurrency is imperative, the objective function could also take query throughput into account. In the same vibe, a TB solution could trigger the construction of further indexes (e.g., new combinations of components, incremental indexes in the concurrent setting) based on a careful consideration of disk consumption and runtime gain. Such scenarios would not only require the conception of a novel cost model for query runtime in the archiving setting, but also the development of approximation algorithms for the underlying optimization problems, which are likely NP-Hard. Finally, since fresh data is likely to be queried more often than stale data, we believe that fetch time complexity9

Internal serialization Archiving multi-graph datasets requires the serialization of 5-tuples, which complexifies the trade-offs between space (i.e., disk and main memory consumption) and runtime efficiency (i.e., response time, ingestion time). For example, dealing with more columns increases the number of possible index combinations. Also, it leads to more data redundancy, since a triple can be associated to multiple values for the fourth and fifth component. Classical solutions for metadata in RDF include reification [67], singleton properties [55], and named graphs [66]. Reification assigns each RDF statement (triple or quad) an identifier t ∈ I that can be then used to link the triple to its ρ and ζ components in the 5-tuples data model introduced in Section 2.3. While simple and fully compatible with the existing RDF standards, reification is well-known to incur serious performance issues for storage and query efficiency, e.g., it would quintuple the number of triple patterns in SPARQL queries. On those grounds, Nguyen et al. [55] proposes singleton properties to piggyback the metadata in the predicate component. In this strategy, predicates take the form p # m ∈ I for some m ∈ N and every triple with p in the dataset. This scheme gives p # m the role of ρ in the aforementioned data model reducing the overhead of reification. However, singleton properties would still require an additional level of reification for the fifth component ζ. The same is true for a solution based on named graphs. A more recent solution is HDTQ [26], which extends HDT with support for quads. An additional extension could account for a fifth component. Systems such as Dydra [7] or v-RDFCSA [19] resort to bit vectors and visibility maps for triples and quads. We argue that vector and matrix representations may be suitable for scalable RDF archiving as they allow for good compression in the presence of high redundancy: If we assume a binary matrix from triples (rows) to graph revisions (columns) where a one denotes the presence of a triple in a revision, we would expect rows and columns to contain many contiguous ones – the logic is analogous for removed triples.

Accounting for evolution patterns As our study in Section 4 shows, the evolution patterns of RDF archives can change throughout time leading even, to decreases in dataset size. With that in mind, we envision an adaptive data-oriented system that adjusts its parameters according to the archive’s evolution for the sake of efficient resource comsumption. Parameter tuning could rely on the metrics proposed in Section 3. Nonetheless, these desiderata translate into some design and engineering considerations. For example, we saw in Section 6 that a large number of deletions can negatively impact Ostrich’s query runtime, hence, such an event could trigger the construction of a complete snapshot of the dataset in order to speed-up VM queries (assuming the existence of a cost model for query runtime). In the same spirit and assuming some sort of dictionary encoding, an increase in the vocabulary dynamicity could increase the number of bits used to encode the identifiers of RDF terms in the dictionary. Those changes could be automatically carried out by the archiving engine, but could also be manually set up by the system administrator after an analysis with RDFev. A design philosophy that we envision to explore divides the history of each graph in the dataset in intervals such that each interval is associated to a block file. This file contains a full snapshot plus all the changesets in the interval. It follows that the application of a new changeset may update the latest block file or create a new one (old blocks could be merged into snapshots to save disk space). This action could be automatically executed by the engine or triggered by the system administrator. For instance, if the archive is the backend of a version control system, new branches may always trigger the creation of snapshots. This base architecture should be enhanced with additional indexes to speed up V queries and adapted compression for the dictionary and the triples.

Finally as we expect long dataset histories, it is vital for solutions to improve their ingestion time complexity, which should depend on the size of the changesets rather than on history size—contrary to what we observed in Section 6 for Ostrich. This constraint could be taken into account by the storage policy for the creation of storage structures such as deltas, snapshots, or indexes (e.g., by reducing the length of delta chains for redundant changesets). Nevertheless, very large changesets may still be challenging, specially in the concurrent scenario. This may justify the creation of temporary incremental (in-memory) indexes and data structures optimized for asynchronous batch updates as proposed in x-RDF-3X [54].