Luis Galárraga
email: luis.galarraga@inria.fr

Kim Ahlstrøm

Katja Hose

Torben Bach Pedersen

Answering Provenance-Aware Queries on RDF Data Cubes under Memory Budgets

The steadily-growing popularity of semantic data on the Web and the support for aggregation queries in SPARQL 1.1 have propelled the interest in Online Analytical Processing (OLAP) and data cubes in RDF. Query processing in such settings is challenging because SPARQL OLAP queries usually contain many triple patterns with grouping and aggregation. Moreover, one important factor of query answering on Web data is its provenance, i.e., metadata about its origin. Some applications in data analytics and access control require to augment the data with provenance metadata and run queries that impose constraints on this provenance. This task is called provenance-aware query answering. In this paper, we investigate the benefit of caching some parts of an RDF cube augmented with provenance information when answering provenance-aware SPARQL queries. We propose provenance-aware caching (PAC), a caching approach based on a provenance-aware partitioning of RDF graphs, and a benefit model for RDF cubes and SPARQL queries with aggregation. Our results on real and synthetic data show that PAC outperforms significantly the LRU strategy (least recently used) and the Jena TDB native caching in terms of hit-rate and response time.

Introduction

In the last years we have seen a steady increase of the amount of Linked Data available on the Web. This data spans over a wide variety of topics ranging from common-sense information to specialized domains such as governmental information, media, life sciences, etc. The data is usually published in RDF [START_REF] Raimond | RDF 1.1 primer. W3C recommendation[END_REF] and queried with SPARQL [START_REF] Seaborne | SPARQL 1.1 query language[END_REF]. The extended capabilities of SPARQL 1.1 -notably the support for aggregation queries-have motivated the publication of multidimensional data, i.e., data cubes, in RDF [START_REF] Colazzo | WaRG: Warehousing RDF Graphs[END_REF][START_REF] Galárraga | QBOAirbase: The European Air Quality Database as an RDF Cube[END_REF][START_REF] Benedikt Kämpgen | Interacting with Statistical Linked Data Via OLAP Operations[END_REF][START_REF] Varga | Dimensional Enrichment of Statistical Linked Open Data[END_REF] . Analysis on multidimensional data warehouses and is known as OLAP (On-Line Analytical Processing). The publication of the QB vocabulary [START_REF] Cyganiak | The RDF Data Cube Vocabulary[END_REF] has served as a bridge between the Semantic Web and OLAP communities.

Imposing constraints on the provenance of query results, a task known as provenance-aware query processing, is crucial in a setting with data coming from multiple independent sources. The provenance of a piece of data is a set of assertions about its origin. If a query must be evaluated over multiple independent data cubes [START_REF] Kämpgen | Querying the Global Cube: Integration of Multidimensional Datasets from the Web[END_REF], provenance metadata can help restrict OLAP queries to data or sources meeting certain quality constraints [START_REF] Mendes | Sieve: Linked Data Quality Assessment and Fusion[END_REF]. Moreover, provenance metadata allows for the implementation of access control policies on data [START_REF] Cadenhead | A Language for Provenance Access Control[END_REF] .

The importance of provenance data management motivated the creation of the PROV ontology [START_REF] Mcguinness | PROV-O: The PROV Ontology[END_REF] (PROV-O), the W3C standard to represent provenance information for RDF data. PROV-O provides the data model to describe a set of provenance entities, i.e., RDF resources, which are assigned to the triples in an RDF dataset. There exist multiple representations for provenance-augmented RDF data, such as named graphs and reification. These representations are, though, not exempt from performance issues for very complex queries [START_REF] Nguyen | Don't Like RDF Reification?: Making Statements About Statements Using Singleton Property[END_REF] due to the additional complexity added by the provenance metadata. In this paper we use the named graph representation [START_REF] Carroll | Named Graphs, Provenance and Trust[END_REF].

A recent formulation for provenance-aware query answering divides the query in two parts: a provenance query and an analytical query [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF][START_REF] Wylot | Executing Provenance-Enabled Queries over Web Data[END_REF]. The provenance query imposes constraints on the provenance entities of the triples that should be considered to answer the analytical query on the actual data. In a representation of provenance entities using named graphs, this is equivalent to adding a FROM clause to the analytical query for each provenance entity reported by the provenance query. As shown in [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF], query response time is seriously affected in frameworks, such as Jena, as the number of FROM clauses increases. This happens because the query engine has to fetch a large number of intermediate results from disk in order to answer the analytical query.

In this paper we propose to alleviate the aforementioned phenomenon by caching some fragments of the RDF graph in memory, so that the analytical queries benefit from fast access to the data. Our strategy, called provenance-aware caching (PAC), selects the most beneficial fragments that fit within a memory budget. Since we are interested in RDF cubes, we assume our queries are OLAP queries, i.e., SPARQL queries with aggregation, grouping and filtering. This assumption reduces the space of possible queries we optimize for, without the need of an explicit query-load. We show that for OLAP analytical queries, it suffices to cache a small percentage of the dataset in order to achieve up to 2x speed-up in query response time. This is particularly convenient for memoryconstrained settings. In summary our contributions are:

-A fragmentation scheme tailored for provenance-augmented RDF graphs.

-The formulation of the budgeted provenance-enabled fragment selection problem:

The problem of selecting a set of fragments for caching so that as many OLAP queries as possible benefit from fast access to cached data. -A query rewriting algorithm to answer analytical queries from a set of named graphs and cached fragments. -A study of the impact of caching on the performance of Jena TDB for provenanceaware SPARQL aggregation queries. The remainder of this paper is structured as follows. Section 2 introduces the basic concepts of RDF cubes, SPARQL aggregation queries and provenance in RDF. In Section 3, we introduce the fragment selection problem with a memory budget for RDF cubes with provenance information. This is followed by an experimental evaluation in Section 4 and a discussion of related work in Section 5. Section 6 concludes the paper.

Preliminaries

RDF Cubes

In compliance with the official RDF specification [START_REF] Raimond | RDF 1.1 primer. W3C recommendation[END_REF], we define an RDF triple t (or simply a triple) as t = s, p, o ∈ (U ∪ B) × P × (U ∪ B ∪ L), where s is the subject, p is the predicate, and o is the object. In this definition, U, B, and L are countably infinite sets of IRIs, blank nodes, and literals. In addition, we define the set of predicates P ⊆ U

SPARQL queries

Due to space constraints, we do not provide a rigorous definition of SPARQL aggregation queries; instead we resort to the formulation used in [START_REF] Ibragimov | Optimizing Aggregate SPARQL Queries Using Materialized RDF Views[END_REF]. SPARQL aggregation queries are the most common types of OLAP queries. We define a triple pattern as a triple

t = s, p, o ∈ (U ∪ B ∪ V) × (P ∪ V) × (U ∪ B ∪ L ∪ V). The set V is a set of variables with (U ∪ B ∪ L) ∩ V = ∅. A basic graph pattern G p is a set of triple patterns. A SPARQL select query Q is an expression of the form "SELECT V F WHERE Ĝp GROUP BY V HAVING c" with V ∪ F = ∅.
In this definition V ⊆ V is the set of projection variables and F is a set of aggregation expressions of the form f (g( V )) where f ∈ {COUNT, SUM, AVG, MIN, MAX} and g( V ) is a numerical expression on the set of aggregated variables V ⊆ V. Ĝp is an extended basic graph pattern, potentially containing OPTIONAL and FILTER clauses. The set of grouping variables is a superset of the projection variables (V ⊇ V ) whereas c is a Boolean expression on V ∪ F . The GROUP BY and HAVING clauses are optional.

Example 2. The following SPARQL query computes the maximal concentration of PM 10 per city in Denmark in 2012 according to the schema in Figure 1.

SELECT ?city (MAX(?ms) as ?max) WHERE { ?obs air:pm10 ?ms. ?obs air:year y:2012. ?obs air:station ?st. ?st air:inCity ?city. ?city air:locatedIn Denmark.

} GROUP BY ?city

Provenance

There exist multiple provenance models for RDF in the literature [START_REF] Cheney | Provenance in Databases: Why, How, and Where[END_REF]; in this paper, we focus on workflow provenance [START_REF] Theoharis | On Provenance of Queries on Semantic Web Data[END_REF]: the history of a unit of information from its sources to its current state. This provenance is modeled using RDF by assigning each triple an RDF resource, which we call its provenance entity. The set of statements describing the provenance entities of an RDF graph defines a provenance graph. The PROV Ontology [START_REF] Mcguinness | PROV-O: The PROV Ontology[END_REF] is the W3C specification to model provenance graphs. In this model a provenance entity can represent a data resource such as a file, a web page or the intermediate result of a data transformation process. Any operation on data is modeled as an activity in PROV-O. Those activities can be directly or indirectly carried out by agents: people, organizations, or even computer programs. If I is a set of provenance entities and f : K → I is a provenance function on the triples of an RDF graph K, a provenance-augmented RDF graph K I is a set of pairs t, f (t) , which can also be seen as a set of quadruples s, p, o, i , where i = f (t) ∈ I.

We can also model a provenance-augmented RDF graph as a set of RDF sub-graphs, each containing the triples associated to the same provenance entity. In this view K I = {K i1 , . . . , K in } (i 1 , . . . , i n ∈ I) and each RDF sub-graph is a named graph with label

i k (1 ≤ k ≤ n).
We define a provenance-augmented cube as an RDF cube whose triples have been augmented with provenance entities.

Provenance-Aware Query Answering

Given a provenance-augmented RDF graph K I = {K i1 , . . . , K in } and a provenance graph G I describing the set of provenance entities i 1 , . . . , i n ∈ I, a provenance-aware query is a pair of SPARQL queries q p , q a [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF][START_REF] Wylot | Executing Provenance-Enabled Queries over Web Data[END_REF]. q p is known as the provenance query and is defined on G I . The provenance query is designed so that it returns a set of provenance entities I ⊆ I. Those provenance entities are used to restrict the scope of the analytical query q a on the RDF graph K I to those subgraphs with labels in I.

The problem of answering provenance-aware queries on RDF data has been studied in the last years [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF][START_REF] Chebotko | Storing, Indexing and Querying Large Provenance Data Sets as RDF Graphs in Apache HBase[END_REF][START_REF] Wylot | TripleProv: Efficient Processing of Lineage Queries in a Native RDF Store[END_REF][START_REF] Wylot | Executing Provenance-Enabled Queries over Web Data[END_REF]. If provenance information is modeled using named graphs (where the labels are provenance entities), the naive strategy is to augment the analytical query with a FROM clause for every provenance entity reported by the provenance query. In [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF] it is shown that this strategy performs poorly in frameworks such as Jena for non-selective provenance queries. To alleviate this problem, [START_REF] Wylot | Executing Provenance-Enabled Queries over Web Data[END_REF] proposes to first fetch all the triples from the named graphs, and then run the analytical query on the merge of those graphs. While this strategy generally outperforms the naive approach, it is not free from performance issues for non-selective analytical queries. Nonetheless, we observe that both strategies require the retrieval of a large number of triples from disk. Therefore, we study the impact of keeping some parts or fragments of the dataset in main memory so that queries can benefit from fast access to the data.

The Budgeted Provenance-Enabled Fragment Selection Problem

In this section, we define the budgeted provenance-enabled fragment selection problem. This is the problem of selecting a set of provenance-enabled RDF data fragments for caching so that we reduce the response time of the analytical query when answering a provenance-enabled query. This is achieved by maximizing the amount of data that is retrieved from the cache. In the following, we describe the three components of our approach, namely the fragmentation strategy, the cost-benefit model, and the query rewriting algorithm. We highlight that our method is query-load agnostic, thus it aims at optimizing for as many queries as possible in the space of analytical queries.

Fragmentation strategy

A fragmentation strategy defines how to split a dataset into smaller parts, i.e., fragments.

Once the dataset is fragmented, we can decide which parts to put in the cache. We start by defining a fragment for provenance-augmented RDF graphs.

Definition 1. A fragment signature s φ is a quadruple s, p, o, i such that each component can be a constant or a variable. We say a quadruple q in a provenance-augmented RDF graph K I matches a fragment signature if there exists an instantiation ρ for the variables in the signature such that ρ(s φ ) = q. The set φ of quadruples that match s φ in a provenance-augmented RDF graph K I is a fragment.

Definition 2. A provenance-aware fragment tree Φ consists of a set of fragments and a partial order f on those fragments. A fragment φ subsumes a fragment φ , denoted by

φ f φ , iff s φ ⇒ s φ . If φ f φ then φ ⊇ φ .
Figure 2 shows a provenance-aware fragment tree describing some fragments from the cube introduced in Example 1 with two provenance entities pr:e1 and pr:e2. The root fragment contains the trivial signature, i.e., the signature that matches all quadruples in the dataset. In the second level, we have signatures with restrictions on the provenance entities of the quadruples. The fragments in the third level have restrictions on both the predicate and the provenance entity. Fragments always subsume their children.

Algorithm 1 describes the method to construct a provenance-aware fragment tree given a provenance-augmented RDF graph. The algorithm first initializes the tree with the trivial signature (line 1). Then for each quadruple in the dataset, the method constructs signatures with (a) bound provenance entity, (b) bound provenance entity and Fig. 2: A provenance-aware fragment tree. The size of each fragment is noted below. predicate (line 3), and (c) bound provenance entity, predicate and object for the rdf:type predicate (lines 4-5). The latter step accounts for the typically large size of the rdf:type predicate. If the tree does not contain a signature, the signature is initialized (by setting its size to 1 in line 8) and added to the tree (line 9). Otherwise, the size of the signature is incremented to account for the current quadruple (line 11).

Algorithm 1: BuildProvenanceAwareFragmentTree

Input: a provenance-augmented RDF graph: KI Output: a provenance-aware fragment tree: When clear from the context, we drop the distinction between a fragment and its signature and refer to both as φ. Finally, we highlight that Algorithm 1 produces fragmentation schemes with redundancy. Whether we allow redundancy or not in the set of selected fragments depends on the benefit model. We elaborate on this in the following.

Φ 1 Φ := { * , * , * , * } 2 foreach q := s, p, o, i ∈ KI do 3 Φ := { * , * , * , i , * , p, * , i } 4 if p = "rdf:type" then 5 Φ := Φ ∪ { * , p, o, i } 6 foreach s φ ∈ Φ do 7 if s φ ∈ Φ then

Cost-Benefit Model

The cost-benefit model quantifies the price we have to pay for caching a fragment, as well as the amount of saved response time induced by using the cached fragment to answer queries. In line with approaches for view materialization [START_REF] Ibragimov | Optimizing Aggregate SPARQL Queries Using Materialized RDF Views[END_REF] we use the number of quadruples matched by the fragment's signature as its cost, i.e., cost(φ) = |φ|. We say a fragment φ is relevant to a provenance-aware query q = q p , q a if at least one of the quadruples in φ can be used to answer q-and none of them could lead to a wrong answer. For example, consider a provenance query q p with result pr:e1 and the analytical query q a from Example 2. In this case the analytical query is restricted by the provenance query to the quadruples with provenance pr:e1. We say that the fragments φ and φ with signatures s φ = *, air:pm10, *, pr:e1 and s φ = *, *, *, pr:e1 are relevant to q. In contrast, the fragment φ with signature s φ = *, p:unitPrice, *, pg:e2 is not relevant, because q p does not consider the provenance entity pg:e2.

Under the assumption that the cost of accessing a quadruple from main memory is insignificant compared to the cost of accessing it from disk, we define the benefit of a cached fragment φ as ben(φ) = qa∈Q |φ qa ∩ φ|. Here Q is the space of all possible queries and φ qa is the set of quadruples required by the query engine to answer q a . In other words, the benefit of a cached fragment is the absolute number of times one of its quadruples can be fetched to answer a query. It follows the total benefit of a set of cached fragments Φ ⊆ Φ from a tree Φ, is given by ben(Φ ) = qa∈Q |φ qa ∩ u(Φ )|, with u(Φ ) = φ∈Φ φ. Our goal is to find a Φ with maximal ben(Φ ).

We highlight that in real-world query engines, the benefit of a fragment w.r.t a query q a may not necessarily depend on the absolute number of cached relevant quadruples used to answer q a , but on the ratio w.r.t the query's relevant set, i.e.,

|φq a ∩u(Φ )| |φq a |
. For example, it may be more beneficial to retrieve 1000 cached quadruples for a query with |φ qa | = 1000 than for a query with |φ qa | = 10000. In the absence of an explicit query load, however, we can only expect to estimate the term |φ qa ∩u(Φ )| since the queries q a as well as φ qa and |φ qa | are unknown. In the following we show that the fixed structure of RDF cubes as well as our focus on OLAP queries, both provide hints to guarantee that ben(Φ ) is at least large.

Observation 1 Distance to observations. The closer to the observations a predicate lies in the schema, the larger the relevance set of its matching fragments is.

For example, all OLAP queries on data cubes involve aggregation of at least one measure. This means that |φ qa ∩ φ| > 0 for fragments φ that match measure quadruples. Furthermore and assuming connected SPARQL queries, filtering or grouping on attributes and dimensions in higher levels always requires to pass by the lower levels, hence it is more beneficial to cache quadruples with predicates in the lower levels.

Observation 2 Diversity. Fragments with larger diversity of predicates have larger relevance sets, i.e., they "touch" more queries. Observation 3 Duplicates. Given a selection of fragments Φ, duplicate quadruples lying in different fragments do not provide additional benefit, because they occupy extra memory without extending the set of relevant queries of Φ.

Based on these observations and the fragmentation defined by the provenance-aware fragment tree, we devise a selection strategy given a memory budget.

Fragment selection

Given a provenance-augmented RDF cube K c = {O, D, P M , P D , P A , ∆}, a maximum budget W in number of quadruples, and a provenance-aware fragment tree Φ, we formulate the budgeted provenance-enabled fragment selection problem as an integer linear program (ILP):

maximize φ∈Φ d o (φ) -1 × d v (φ) × x φ s.t. φ∈Φ |φ| × x φ ≤ W (budget) ∀p : φ root → • • • → φ k : φ∈p x φ ≤ 1 (no replication) ∀φ ∈ Φ : x φ ∈ {0, 1} (integrality constraints) (1)
Each fragment φ in the lattice is assigned a Boolean variable x φ . If x φ = 1 the fragment is chosen for caching. Hence, the solution to the ILP produces a set of fragments Φ cached ⊂ Φ that will be stored in main memory. Observations 1 and 2 are implemented in the objective function. This function decreases with the distance of the fragment's predicates to the observations (d o ) and increases with the fragment's diversity (d v ) 1 . We define the distance of a predicate to the observations as the number of hops from an observation to the predicate in the schema. In Figure 1, for example, the predicates air:pm10 and air:unit have distances 1 and 2 respectively. If a fragment φ contains quadruples with different predicates, d(φ) is the smallest distance among all predicates in φ. The diversity, on the other hand, is the number of different predicates in quadruples in φ. The cost model is encoded in the budget constraint. Since duplicate quadruples do not contribute with additional benefit (Observation 3), the no replication constraint guarantees that the resulting set Φ cached has no redundancy. Because of this constraint and the partial order encoded in the tree, the ILP solver can pick at most one fragment in a given path from the root to a leaf.

Query rewriting

In this section, we describe how to use a selection of cached fragments Φ cached to answer provenance-aware queries q = q p , q a . Recall from Section 2.4 that in a setting based on named graphs, a provenance-aware query can be answered by adding a FROM clause to the analytical query q a for each provenance entity i ∈ I reported by q p . Each provenance entity corresponds to a named graph that resides in disk. In our setting we count additionally on a set of cached fragments Φ cached that can be accessed from memory. We treat each fragment φ ∈ Φ cached as a memory named graph with label id (φ), where id (φ) returns the concatenation of the constant components of s φ (φ's signature). Exploiting those memory named graphs to answer the analytical query is the goal of Algorithm 2. The algorithm takes as input an analytical query q a , a provenanceaware tree Φ tree , the result of the provenance query I , and the set of cached fragments Φ cached reported by our selection strategy in Section 3.3. The algorithm returns the graph labels that will be added as FROM clauses to the analytical query.

Line 1 initializes some intermediate variables. Lines 2-5 compute the most specific fragments in the lattice that are relevant to the analytical query, i.e., fragments whose signatures combine the provenance entities in I with the triple patterns of the analytical query. Then for each relevant fragment φ, the algorithm verifies whether φ is in the cache (line 9). If so, the fragment is added as a candidate (line 8). Otherwise, the algorithm verifies whether one of φ's ancestors (line 9) has been cached. There can be at most of one of such ancestors due to the redundancy constraint discussed in Section 3.3. If an ancestor φ is found in the cache, the algorithm adds it to the set of candidates (line 10). Since this addition turns every (possibly) selected descendant of φ redundant, the algorithm removes those descendants from the list of candidates (line 10). If neither φ nor any of its ancestors is in the cache, the algorithm takes as candidate the named graph labeled with the provenance entity i in s φ (line 12). This step turns any fragment with signature of the form -, -, -, i superflous, and thus unnecessary (line 13). Once the final list of candidates have been computed, Alg. 2 generates the graph labels that will be used to rewrite the analytical query (line 14).

Experiments

Experimental setup

Data. We evaluated PAC on several datasets generated with the Star Schema Benchmark (SSB [START_REF] Pat | Star Schema Benchmark[END_REF]) and on the QBOAirbase dataset [START_REF] Galárraga | QBOAirbase: The European Air Quality Database as an RDF Cube[END_REF]. The SSB benchmark provides a data generator for a database of line orders processed by a wholesaler. The number of line orders is an argument for the data generator. We converted the SSB dataset into an RDF cube, where each line order corresponds to an observation defined by four dimensions: supplier, part, customer, and date. We generated four datasets with four different numbers of line orders: 80k, 160k, 320k, and 640k. This resulted in 2.3m, 4.4m, 7.8m, and 14.4m triples respectively. All SSB datasets contain 68 distinct predicates. The QBOAirbase dataset, on the other hand, models air pollution measurements from 36 European countries as an RDF cube augmented with workflow provenance. A measurement corresponds to an observation with coordinates in the time, station (location), and sensor dimensions. We tested our approach on the subset of measurements of Denmark (qboairbase-dk) and Great Britain (qboairbase-gb). These datasets account for 542k and 4.3m triples respectively, both with 81 distinct predicates. Provenance Data and Queries. Since the SSB benchmark does not provide provenance for the data, we augmented each RDF cube with 1000 distinct provenance entities and simulated a set of provenance queries. The provenance entities are assigned to observations in the cube according to two settings: balanced and unbalanced. In the balanced setting, each provenance entity is assigned the same number of observations in the cube, whereas in the unbalanced setting the i th provenance entity is assigned 2 i triples. We denote the resulting SSB datasets with the prefixes b-ufollowed by the number of line orders, e.g., b-ssb-80k contains 80k line orders with a balanced provenance assignment. We simulated our provenance queries by materializing sets of provenance entities covering from 10% to 90% of the provenance entities in the cube (at intervals of 10%). The datasets qboairbase-dk and qboairbase-gb contain 25.3k and 191.8k different provenance identifiers. For QBOAirbase we constructed a set of 5 provenance queries. These queries impose constraints (a) on whether the data has been quality checked or not (2 queries), (b) on whether we know the data provider or not (2 queries), and (c) on the observation's generation time. Analytical Queries. The SSB benchmark provides a set of 13 standard OLAP queries [START_REF] Pat | Star Schema Benchmark[END_REF]. For QBOAirbase [START_REF] Galárraga | QBOAirbase: The European Air Quality Database as an RDF Cube[END_REF], we used 8 of the analytical queries available at the project's website2 . These are the queries where Jena does not time out. For all datasets, we construct provenance-aware queries by combining each analytical query with each of our provenance queries. Each provenance-aware query is executed three non-consecutive times in random order. We averaged the runtimes. System Setup and Opponent. We used the Jena TDB physical database for the indisk named graphs, and the Jena TDB in-memory store for the cached fragments 3 . All experiments were run in a virtual server with an AMD Opteron 6376 with 8 cores, 128 GB of RAM and 1 TB of disk space running in RAID-5. We tested our queries under two general system settings: (1) after purging the operating system cache and disabling the Jena TDB cache -which we call cold-, and (2) with the default TDB cache (∼ 50MB) and a populated OS's cache after having run all the queries at least once. We call this setting warm. We compare our approach with the caching provided by Jena TDB and with the LRU caching strategy. The memory budgets are provided as percentages. For Jena TDB a budget of 20% means the engine counts on memory of size 20% the physical database. In contrast, for PAC and LRU the budgets indicate the percentage of triples in the dataset that will be cached. LRU populates the available cache space with the fragments used by the last executed query in a driven-by-size greedy fashion. Jena's standard execution plans timed out with most of the queries, thus we implemented an execution strategy on top of Jena, on which queries are executed on the merge of all relevant in-disk named graphs and cached fragments [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF][START_REF] Wylot | Executing Provenance-Enabled Queries over Web Data[END_REF].

Evaluation

Impact of graph filtering. We disabled caching and compare PAC's graph filtering and query rewriting with the approach proposed in [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF], and a naive query rewriting on the analytical queries. The naive approach rewrites the analytical query by adding a FROM clause for each of the results of the provenance query. In contrast, the approach in [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF] defines a context index that maps provenance entities to predicate paths, allowing for pruning of the graphs that do not co-occur with predicate paths in the query. In the same spirit, Alg. 2 filters irrelevant graphs by means of the provenance-aware fragment tree, which encodes the co-occurrences of predicates, object values, and provenance identifiers. Table 1 shows the average runtime and average index built time of the different strategies for four of our datasets. We observe that PAC's filtering outperforms the naive approach in query runtime, because it achieves reductions from 12% to 24% in the total number of materialized triples. While the context index and PAC achieve comparable reductions in the SSB datasets, [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF] performs worse for two reasons: (a) it merges all relevant graphs in disk, and (b) it does not handle unions natively. The latter limitation implies that subqueries must be executed independently and their results merged. It also explains why this method sometimes materializes more triples than the naive approach, leading to negative reduction rates. Finally, we highlight that the context index's build time is up to 3x slower than PAC's provenance-aware fragment tree because the context index runs an expensive select query for each predicate path in the index.

Caching vs. In-memory DB. Table 2 compares the average runtime of PAC, the LRU, and the Jena TDB caching strategies -the two latter with and without PAC's filteringat budget 20% against full PAC (budget 100%) and the Jena TDB in-memory database in a warm setting. PAC at budget 20% outperforms in total time all caching strategies and the Jena in-memory database. The bottom line is that with PAC's strategic caching, it is not necessary to store everything in main memory for speed-up. In addition, full PAC is 2x faster than the in-memory database thanks to PAC's graph filtering (Alg. 2). Impact of the memory budget. Figures 3 and4 show the impact of the memory budget on the average cache hit-rate and the average response time of PAC in a cold setting on four datasets from all our families of datasets. We define the hit-rate as the ratio of graph labels returned by Alg. 2 that correspond to cached fragments. We observe a monotonically increasing behavior in the hit-rate for all datasets. On the u-ssb-80k and qboairbase datasets, the hit-rate already approaches 80% at budget 10%, contrary to the h-ssb-80k dataset where the increase is more gradual. This phenomenon is mainly caused by the fine granularity of the fragments both in u-ssb-80k and qboairbase. Finegrained fragments give the selector more flexibility at utilizing the available budget in contrast to very large fragments as the ones found in h-ssb-80k. If a very large fragment does not fit into the remaining cache space, it will not be added, even though it may be relevant to many queries in the query space. The trends in the hit-rate are supported by the runtime behavior in Figure 4. PAC vs. LRU and TDB. We compare PAC, the LRU caching strategy, and the Jena TDB native caching for qboairbase-gb on a warm setting in Figure 5. The trend is independent of the system setting and is similar for qboairbase-dk. We first observe that PAC outperforms Jena TDB at all budgets. Only when PAC's filtering is enabled (TDB+PAC-F), TDB performs comparably to PAC. On the contrary, LRU seems inadequate for this dataset, even when PAC's filtering is enabled (LRU+PAC-F). Due to the high diversity of cached fragment signatures in the qboairbase datasets (approx. 192k), it is unlikely for two consecutive queries to require the same fragments. This hurts the performance of LRU, which delivers a hit-rate of 0 for less than 40% budget. LRU+PAC-F does slightly better, but its maximal hit-rate is no higher than 0.6. The situation is different for the u-ssb-80k dataset as shown in Figure 6. While PAC still delivers the best performance, TDB is outperformed by LRU. The trends are corroborated by the hit-rate, where PAC is between 0.26 and 0.57 ratio points better than LRU, and between 0.24 and 0.69 points better than LRU+PAC-F. Our findings in the h-ssb-80k dataset are alike: PAC is between 0.15 and 0.47 ratio points better than LRU as displayed in Figure 7 (between 0.08 and 0.28 points w.r.t. LRU+PAC-F). All in all, the synergy between graph filtering and a high hit-rate makes PAC faster than standard caching strategies.

Caching on bigger datasets. We also investigate the behavior of the different caching strategies as the number of triples increases in the u-ssb family of datasets on a warm system setting. We set a budget of 20% and show the results in Figure 8. PAC consis- Fig. 8: Runtime on u-ssb tently achieves better runtime than its competitors. In general, all trends observed in the h-ssb-80k and u-ssb-80k datasets remain constant as the number of triples increases. Impact of caching on queries. We also study the impact of the different caching strategies on the response time of the individual analytical queries. For this purpose we compute the area under the curve of response time vs. budget for each analytical query under the different strategies on the h-ssb-80k, u-ssb-80k, qboairbase-gb, and qboairbase-dk datasets. The runtimes were averaged across all provenance queries. Table 3 shows the number of queries where each strategy wins, that is, the strategy achieves the smallest area under the curve until budgets 20%, 50%, and 100%. We notice that TDB becomes insensitive to the budget argument after a value of 20%. By looking at the winning strategies in each query, we observe that PAC has an almost stable behavior: the set of benefited queries grows monotonically as the budget increases. Despite of being queryload oblivious, PAC with budget 20% wins in 50% of the analytical queries in the SSB datasets, and in 100% of the analytical queries in the QBOAirbase datasets.

State of the Art

This paper studies the impact of caching fragments of a provenance-augmented RDF cube for faster query processing. Therefore, we present the state of the art in terms of three axes: caching in SPARQL and OLAP, query answering on SPARQL aggregation queries, and provenance management. Caching in SPARQL and OLAP. Caching data to speed up query answering is a standard technique in databases and has also been applied to RDF/SPARQL and OLAP.

Caching can be implemented at different levels. For example, the Jena TDB engine relies on the file caching provided by the Java Virtual Machine to speed up subsequent access to recently used parts of the RDF store. When implemented at the application level, e.g., in a client-server setting, caching is often concerned with the reutilization of query results [START_REF] Lorey | Caching and Prefetching Strategies for SPARQL Queries[END_REF][START_REF] Martin | Improving the Performance of Semantic Web Applications with SPARQL Query Caching[END_REF][START_REF] Todd | Enabling Fine-Grained HTTP Caching of SPARQL Query Results[END_REF]. In contrast, we aim at caching fragments of the RDF dataset that are used by multiple queries and unlike [START_REF] Lorey | Caching and Prefetching Strategies for SPARQL Queries[END_REF], we do not count on an explicit query load. Caching has also been implemented for data fragments and intermediate query results. In the framework of Linked Data Fragments (LDF) [START_REF] Verborgh | Triple Pattern Fragments: A Low-cost Knowledge Graph Interface for the Web[END_REF], the server can return cached data fragments, leaving the query processing to the client. While PAC's notion of fragments is similar to that of LDF, [START_REF] Verborgh | Triple Pattern Fragments: A Low-cost Knowledge Graph Interface for the Web[END_REF] does not consider provenance and focuses on reducing the server's load for the sake of availability rather than on minimizing response time. Caching has also been applied to OLAP queries [START_REF] Deshpande | Caching Multidimensional Queries Using Chunks[END_REF][START_REF] Kalnis | An Adaptive Peer-to-peer Network for Distributed Caching of OLAP Results[END_REF]. The system PeerOLAP [START_REF] Kalnis | An Adaptive Peer-to-peer Network for Distributed Caching of OLAP Results[END_REF], for example, relies on a P2P network to answer OLAP queries. PeerOLAP reuses the results of queries executed by neighbor peers as data sources. As PeerOLAP, most systems focus on caching recently queried results [START_REF] Bishop | FactForge: A fast track to the Web of data[END_REF][START_REF] Erling | RDF Support in the Virtuoso DBMS[END_REF]. In [START_REF] Umbrich | Hybrid SPARQL Queries: Fresh vs. Fast Results[END_REF] a hybrid query engine is proposed; it combines live results with cached data as a trade-off between precision and speed. In our approach, we use heuristics to pre-cache strategically important parts of the data.

SPARQL Aggregation Queries. The interest on optimizing SPARQL queries with aggregation [START_REF] Castillo | RDFMatView: Indexing RDF Data for SPARQL Queries[END_REF][START_REF] Ibragimov | Optimizing Aggregate SPARQL Queries Using Materialized RDF Views[END_REF] started with the publication of SPARQL 1.1 [START_REF] Seaborne | SPARQL 1.1 query language[END_REF]. MARVEL [START_REF] Ibragimov | Optimizing Aggregate SPARQL Queries Using Materialized RDF Views[END_REF] proposes to answer SPARQL aggregation queries on RDF cubes by rewriting the query in terms of a set of views. These views are structured according to a partial order, and selected for query answering based on a cost model as in PAC. Unlike PAC, MAR-VEL is not a caching approach: it is based on precomputed aggregates -materialized as views-rather than on actual RDF fragments. Moreover, MARVEL does not support provenance. Conversely, [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF] supports provenance and proposes a context index for graph filtering to speed up the execution of the analytical queries. The index stores the co-occurence of provenance entities and predefined predicate paths. [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF] assumes also that some of the quadruples produced by the ETL process are all assigned a single hard-coded provenance entity. Albeit not equivalent, our provenance-aware fragment tree serves for graph filtering at a better performance without additional assumptions.

Besides, [START_REF] Ahlstrøm | Towards Answering Provenance-Enabled SPARQL Queries Over RDF Data Cubes[END_REF] does not implement caching.

Provenance management. The management of provenance is a crucial task for Linked Data and RDF given the decentralized nature of the Web. There are several approaches to encode provenance in RDF, such as reification [START_REF] Raimond | RDF 1.1 primer. W3C recommendation[END_REF], named graphs [START_REF] Carroll | Named Graphs, Provenance and Trust[END_REF], singleton properties [START_REF] Nguyen | Don't Like RDF Reification?: Making Statements About Statements Using Singleton Property[END_REF], and embedded triples [START_REF] Hartig | Foundations of RDF* and SPARQL* -An Alternative Approach to Statement-Level Metadata in RDF[END_REF]. In this work we focus on workflow provenance [START_REF] Theoharis | On Provenance of Queries on Semantic Web Data[END_REF]. Other approaches study provenance in terms of the lineage of the query results [START_REF] Green | Provenance Semirings[END_REF][START_REF] Wylot | TripleProv: Efficient Processing of Lineage Queries in a Native RDF Store[END_REF]: expressions (e.g., a polynomial) that encode the origin of a result w.r.t the triples in the dataset. The TripleProv engine [START_REF] Wylot | TripleProv: Efficient Processing of Lineage Queries in a Native RDF Store[END_REF] allows for native calculation of lineage for the results of SPARQL queries. Our setting is significantly different, because provenance is encoded as provenance entities described using RDF and the PROV-O ontology [START_REF] Mcguinness | PROV-O: The PROV Ontology[END_REF]. Compared to the notion of lineage for query results, a provenance entity can be seen as the identifier of a precomputed lineage.

Conclusions

In this paper, we have presented provenance-aware caching (PAC), an approach to cache fragments of a provenance-augmented RDF graph in order to speed up provenanceaware OLAP queries. Our techniques are query-load agnostic and our experimental evaluation shows that PAC outperforms the Jena TDB native cache and the standard LRU caching strategy in real and synthetic data. The PAC principle can be applied to scenarios where the query-load is unknown, e.g., to bootstrap the cache, or when the workload changes constantly. It is also applicable in settings characterized by locations of "fast" and "slow" access, such as a hybrid drives or remote storage servers. As future work, we envision to integrate explicit dynamic query workloads into our framework, and to extend the fragment definitions beyond equality constraints on the quadruples by, for example, using the provenance graph. All the data and experimental results are available at http://qweb.cs.aau.dk/pac/.

Fig. 1 :Example 1 .

 11 Fig. 1: Observation with 3 dimensions: Year, Station, and Sensor. Measure predicates P M are in solid line style, whereas attribute predicates P A use dotted lines. The dashed edges correspond to the dimension properties P D .

8 s 9 Φ

 89 φ .size := 1 := Φ ∪ s φ 10 else 11 s φ .size := s φ .size + 1 12 return Φ

Algorithm 2 : 3 foreach i ∈ I do 4 s

 234 rewriteAnalyticalQueryInput: Analytical query qa, provenance-aware tree Φtree , the provenance query result I , the set of cached fragments Φ cached Output: A set of graph labels1 candidates := relevant := disk := ∅ 2 foreach t = s, p, o ∈ qa do := { * , p, o, i , * , p, * , i } ∩ Φtree 5 relevant := relevant ∪ {most-specific-fragment-in(s)} 6 foreach φ ∈ relevant do 7 if φ ∈ Φ cached then 8 candidates := candidates ∪ {φ} 9 else if ∃ φ ∈ Φ cached : s φ f s φ then 10 candidates := candidates -{ φ : s φ f s φ} ∪ {φ }11 else 12 disk := disk ∪ {i : s φ = * , p, * , i } 13 candidates := candidates -{φ : s φ ≈ -, -, -, i } 14 return {id (φ) : φ ∈ candidates ∪ disk )}

Fig. 3 :Fig. 4 :

 34 Fig. 3: Budget vs. hit-rate for PAC

Fig. 7 :

 7 Fig. 5: Runtime on qboairbase-gb

Table 1 :

 1 Performance of different graph filtering strategies (warm setting).

			PAC			Context index		Naive
	Dataset	Runtime	Build time	Triples reduction	Runtime	Build time	Triples reduction	Runtime
	b-ssb-80k	24.52s	17.38s	24.11%	35.97s	24.45s	24.10%	33.36s
	u-ssb-80k	25.82s	17.65s	22.58%	37.48s	27.57s	22.56%	34.79s
	qboairbase-gb	20.04s	42.72s	12.00%	103.41s	134.10s	-37.51%	24.85s
	qboairbase-dk	1.98s	5.56s	13.72%	6.54s	19.94s	-35.31%	2.61s

Table 2 :

 2 Runtime of a full in-memory database vs. the caching strategies at budget=20%

Table 3 :

 3 Number of queries where each strategy wins (warm system setting)

We omitted the fragment size from the objective function because size benefits too much those fragments with general signatures, i.e., those of the form * , * , * , i

http://qweb.cs.aau.dk/qboairbase/

We used Jena v.3.2 available at https://jena.apache.org/

Acknowledgments

This research was partially funded by the Danish Council for Independent Research (DFF) under grant agreement no. DFF-4093-00301.