We address the problem of estimating when the results of an input SPARQL query over dynamic RDF datasets will change. We evaluate a framework that extracts features from the query and/or from past versions of the target dataset and inputs them into binary classi ers to predict whether or not the results for a query will change at a xed point in the near future. For this evaluation, we create a gold standard based on 23 versions of Wikidata and a curated collection of 221 SPARQL queries. Our results show that the quality of predictions possible using (only) features based on the query structure and lightweight statistics of the predicate dynamics { though capable of beating a random baseline { are not competitive with results obtained using (more costly to derive) knowledge of the complete historical changes in the query results.
Many applications that consume Linked Data (LD) face challenges related to remote changes in the underlying data. Client-side caches can reduce the network tra c between clients and servers, the load on servers, and the average latency of responses. However, since datasets change over time, for caches to be useful, they should be updated when the underlying data that they re ect change; predicting such remote changes, however, is a challenging problem, particularly when data are accessed as the results of queries to a SPARQL endpoint.
Since datasets change over time, long-running applications that cache and
repeatedly use query results obtained from an external SPARQL endpoint may
resubmit the queries regularly to ensure up-to-dateness. As a result, without
further information as to the dynamics of a particular SPARQL query, applications
face the choice of either performing frequent query executions that may be
redundant and repeatedly return the same results (aiming for stronger consistency
at the cost of more frequent querying), or performing infrequent query
executions that may lead to stale data being persisted in the application when the
underlying sources change (accepting weaker consistency to improve e
ciency/scalability). Given the costs for clients and servers of repetitive requests served
over the Web and the potential e ciency gains o ered by local caches, several
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
weak consistency approaches have been proposed that try to keep the local data
of the applications updated at lower cost by predicting changes [
Some works study data dynamics based on the historical evolution of
entities [
Given a SPARQL query and a dynamic RDF graph (consisting of multiple historical versions), in this work, we address the problem of predicting whether or not the query's results will change in the next version of the RDF graph.
To the best of our knowledge, this is the rst work to address this problem.
Along these lines, we evaluate a general architecture based on Machine Learning that extracts static features from a query, as well as features from the query and dynamic dataset. These features are fed into a binary classi er to predict whether or not the query results will change in a xed point in the future, or, more ambitiously, can be fed into a regression model to predict when the query results are likely to change. With respect to the features used, we show that there is a trade-o between those that are easy to compute but o er less accurate predictions (e.g., static query features) versus those that are more costly to compute but o er more accurate predictions (e.g., historical changes in query results). Per this trade-o , which features to use for predicting the dynamics of query results may then depend on the particular application.
In order to better understand this conceptual trade-o { and more generally,
to evaluate the quality of predictions made by our framework { we create a
novel gold standard based on 23 weekly versions of the Wikidata knowledge
graph [
Contributions: (1) We evaluate a general architecture for predicting when/if the results of a SPARQL query will change in a future version of a dynamic RDF dataset. (2) We evaluate a number of features to instantiate this architecture based on analysis of the query, analysis of the dynamics of predicates in the data, and analysis of historical changes in the query results. (3) We create a gold standard for these tasks based on 23 consecutive versions of Wikidata and a set of 221 real-world SPARQL queries. (4) We use this gold standard to compare the predictions obtained using di erent types of features and classi ers. 2
A variety of works have addressed the issue of modeling and consuming dynamic
Linked Data from a broad range of perspectives [
Some works have addressed the synchronization problem on the publisher
side, proposing noti cation mechanisms that keep registered consumers informed
about relevant changes to the data [
Conversely, a variety of works have looked at building models of remote data
that can help to predict which data are most dynamic, and which are most
static, indicating which subsets of the data may need be refreshed from the
remote source more often [
Speci cally regarding the dynamics of SPARQL query results, Passant and
Mendes [
Novelty: Given a query and a dynamic RDF dataset, we aim to predict whether
or not the query's results will have changed in a xed point in the near future.
Our work thus complements existing works aiming for weak consistency, but (i)
generalizes the problem, evaluating a framework that can incorporate statistics
on predicate dynamics [
RDF is a conceptual data model based on directed graphs that can be used to describe resources on the Web. RDF terms are elements of the set I [ B [ L composed of IRIs I, literals L, and blank nodes B. A tuple (s; p; o) 2 (I [ B) (I) (I [ B [ L) is called an RDF triple, where s is called subject, p is called predicate, and o is called object. An RDF graph is a set of RDF triples.
SPARQL is the recommended query language to retrieve and manipulate data
stored in the RDF format. In this work, we focus on SPARQL SELECT queries,
where we will rst de ne a SPARQL 1.0 query. Let V be a set of variables
disjoint from the set of RDF terms. A SPARQL expression is built recursively
as follows. (1) A triple pattern t 2 (I [ B [ L [ V) (I [ V) (I [ L [ B [ V) is an
expression. (2) If Q1 and Q2 are expressions and R is a lter condition, then Q1
FILTER R, Q1 UNION Q2, Q1 OPTIONAL Q2, Q1 AND Q2 are expressions. Finally,
if Q is an expression, V a list of variables and a boolean value, SELECTV Q is
a SPARQL SELECT query, where V denotes the projected variables, and the
DISTINCT option that when true, removes duplicate results. The semantics of
a SPARQL SELECT query Q is de ned in terms of its evaluation over an RDF
graph G, denoted Q(G), giving a set of partial mappings from projected variables
to the set I [ L [ B; we refer to Perez et al. [
Our method supports SPARQL 1.1 SELECT queries, which allow a variety of additional features. One key feature in this extension is that of property paths, which allows for matching arbitrary length paths in an RDF graph, potentially returning or matching the endpoints of the path. An IRI p is a path expression; if e, e1 and e2 are path expressions, then ^e (inverse of e), e1/e2 (e1 followed by e2), e1|e2 (e1 or e2), e* (zero or more e), e+ (one or more e), e? (zero or one e), and (e) (parentheses used for precedence) are also path expressions ; nally, if p, p1, : : : ; pn are IRIs, then !p, !(p1| : : : |pn) and !(p1| : : : |pk|^pk+1| : : : |^pn) for k +1 n (negated property sets) are path expressions. Thereafter, a path pattern (s; e; o) where e is a path expression is an expression. Other features supported in SPARQL 1.1 include sub-queries, negation, aggregation, value binding, and so forth; for brevity, we do not introduce de nitions for all such features.
One topic we do wish to highlight, however { as it relates to the behavior of
a query over a dynamic RDF graph { is that of the monotonicity of SPARQL
queries [
We consider a dynamic RDF graph to be a sequence of n discrete versions of an RDF graph denoted G := (G1; : : : ; Gn); in practice, we assume these versions to have regular intervals (e.g., hourly, daily, weekly, etc.). Further given a SPARQL (1.1) SELECT query Q, we would like to have knowledge of the dynamics of its results. The speci c problem we consider in this work { which we call One Shot Change (OSC) { accepts G, Q and a positive integer k as input and outputs a boolean value predicting whether or not the results will change from Gn to some future version Gn+k (i.e., Q(Gn) 6= Q(Gn+k)?). In the case of bag semantics, we de ne \6=" in terms of bag inequality, meaning that two bags of query results are di erent if the multiplicity of any result di ers. We thus currently focus on predicting if the results of a query will change, rather than predicting when, or to what extent, they will change; these latter problems are left for future work. Architecture: In Figure 1, we provide an overview of a general architecture for making predictions with respect to the OSC prediction task. A SPARQL query Q and a dynamic RDF graph G are given as input. The Query Feature Extractor extracts static features from the query, which include statistics about the number of elements in the query (e.g., number of triple patterns, variables, etc.) as well as the presence of particular query operators (e.g., UNION, FILTER, recursive path expressions, etc.). The Predicate Feature Extractor takes as input the predicates from the query and statistics about those predicates from the dynamic graph to produce a set of aggregated numerical features about the dynamicity of predicates used in the query. The Result Feature Extractor takes as input the results of the query over past versions of the dynamic graph from which it produces further features. All such features are passed to a (pre-trained) binary classi er to generate the nal OSC prediction. We will now describe in more detail the query, data and result features considered in this work.
Query Features: Our initial set of features is based on static analysis of the input SPARQL query. Figure 2 shows only a sample of evaluated features, as well as { for the purposes of illustration { their values for an example query.
Q
G Q(G)
The rst group of features captures statistics about the query, indicating loosely its size and complexity. One might consider that the higher these values are, in general, the more dynamic we can expect the query to be since there are more \opportunities" for the query results to be a ected by change. In some cases, however, the hypothesized correlation is not direct since, for example, adding more triple patterns may serve to narrow the query down and focus it on a static part of the graph (e.g., when looking for the movies of directors, adding a triple pattern to restrict the results to directors who have died may reduce the likelihood of changes in the results in a future version). Hence it will be of interest to see, experimentally, how these features a ect the predictions.
The second group indicates the query operators used; we capture the presence or absence of query operators and solution modi ers from SPARQL 1.1.
In the third group gathers related features into one dimension: in the case
of Recursive path, we group queries with path expressions of the form e* or e+.
On the other hand, in Negation, we group non-monotonic features that allow
for modeling di erence (MINUS, NOT EXISTS, !BOUND2. These features { though
course-grained { are straightforward to extract from a query, and o er
valuable insights into how the query may behave in a dynamic query; for example,
the Negation feature captures information about the (non-)monotonicity of the
query, while we suppose that Recursive paths, which may traverse an arbitrary
number of triples in the graph, might be more sensitive to change. Again, such
correlations are not without exception and will require empirical study.
Predicate Features: The next component extracts features that capture
information about the dynamics of predicates used in the query (without evaluating
the query on the dynamic graph). This component captures how often and how
many triples change for a predicate in a time interval, with the idea that { as
in previous works [
X f :instance of, ... g SELECT ?item WHERE f ?item :instance_of :human . ?item :gender :female .
f ?item :place_of_birth :Wales g UNION f ?item :place_of_birth ?pob .
?pob :located_in* :Wales g OPTIONAL f ?sitelink schema:about ?item .
?sitelink schema:inLanguage "cy" g
FILTER (!BOUND(?sitelink)) g LIMIT 100 of triple patterns of variables of projected variables of predicates FILTER LIMIT UNION GROUPBY Sub-query Recursive path Negation
Predicates low, such statistics can be easier to maintain. Formally, given two RDF graphs Gi and Gj , we denote by Gi Gj the set of triples (Gi [ Gj ) (Gi \ Gj ) where \ " denotes set di erence; in other words, Gi Gj denotes the triples in one graph or the other but not both (noting that Gi Gj = Gj Gi). Next, given an RDF graph G and an IRI p, let #(G; p) := jf(x; y; z) 2 G : y = pgj denote the number of triples in G with predicate p. Finally, given a dynamic RDF graph G := (G1; : : : ; Gn) and a predicate p, we denote by (G; p) := in=11 ##((GGii[GGii++11;;pp)) the normalized sum of the number of triples with the predicate p that changed between pairs of consecutive versions.
Example 1. Consider the example dynamic RDF graph G in Figure 3 (based on real data from Wikidata, with IRIs modi ed for the purposes of readability). In Figure 4 we show the pairwise changes between each version: G1 G2 and G2 G3. For a predicate p, the value (G; p) is then the sum of triples with predicate p in the graphs G1 G2 and G2 G3 divided by the number of triples with predicate p in the graphs G1 [ G2 and G2 [ G3. Looking at Figure 4, for example, :name does not appear ( (G; :name) = 0), :children appears twice in G1 G2 and G1 [ G2, as well as, twice in G2 G3 and G2 [ G3 ( (G; :children) = 4=4 = 1), and so forth.
Given a query Q with a set of predicates fpi; :::; png, we may then consider a variety of aggregate functions over (G; p1); :::; (G; pn), such as max, mean, etc., to compute a nal numeric feature for the query, representing a summary of the level of dynamicity of the predicates it contains.
Result features: The third type of feature we capture indicates how many times the query results Q have changed over the past versions of the dynamic graph. While this feature o ers rich information for prediction, given a query that has not previously been seen, it is costly to compute, since it requires the evaluation of the query over each past version within an interval, which in turn requires maintaining indexes over the full data for a variety of past versions. 5
In order to evaluate the e ectiveness for predicting changes in SPARQL query
results, we require a dynamic RDF graph, with access to various historical
versions; preferably this graph contains real-world, large-scale, diverse RDF data,
and with su cient changes between versions to provide both positive and
negative examples of queries whose results change. Furthermore, we require a set of
SPARQL queries that can be answered against this dynamic graph; preferably
these queries again should be diverse, representative of real-world user queries,
of a variety of shapes and sizes, using a variety of query operators, and with a
mix of both dynamic and static results over the dynamic graph. In particular,
we choose Wikidata [
Table 1 shows the ten most dynamic predicates according to the number of added and deleted statements involving that predicate (Total) and the ratio of added and deleted statements divided by the total number of statements for that predicate across all snapshots (Dyn); for the latter, we only include predicates 2 1:5 0:5 1 0 109 1 8 107 6 4 2
Added
Removed
23
that appear in all snapshots and appear in 1,000 statements overall. Though
the largest number of changes involves the predicate schema:description, its
dynamic value is low due to it being a common predicate. On the other hand, the
OWL properties have high dynamicity ratios due to taking blank node values;
we currently do not consider isomorphism of graphs due to blank nodes.
Queries: The corpus collected by Gonzalez and Hogan [
A total of 96 queries had to be removed from the original set of 389 because they asked for information external to Wikidata (using SERVICE) or asked for quali ers that are not present in the truthy version. We also eliminated 12 queries that returned bindings to blank nodes to facilitate comparison between 3 https://www.wikidata.org/wiki/Wikidata:SPARQL_query_service/queries/ examples the results. Furthermore, some queries featured non-deterministic elements { such as LIMIT/OFFSET without ordering, SAMPLE or temporal functions { such as TODAY() { that may lead to changes in results not related to changes in the data; we remove 23 queries with SAMPLE and temporal functions, and add an ORDER BY clause to all queries to ensure determinism with LIMIT/OFFSET and more generally to facilitate quick comparison of results. We also eliminated 37 queries with empty results for all snapshots. As a result of this process of ltering, we end up with a total of 221 non-empty deterministic queries.
In Table 2, we provide statistics on the distribution of di erent types of triple patterns in the 221 queries before the transformation; of key importance is that 86.20% of the triple patterns have a constant in the predicate position, meaning that they are compatible with a model based on the dynamics of predicates. We also see that 83 triple patterns (11.34%) feature a path expression, where Table 3 provides the distribution of these expressions (remarking that multiple patterns can be used in one expression); of note here is that recursion is commonly found (74.70% use e* while 9.64% use e+), and that we nd no negated property paths.
Finally, we look at how the results for these queries change over the 23 versions. Figure 6 shows how many queries had some results change between two consecutive versions, where we see that approximately half of the result sets change in each version. But are these always the same queries that change every time? Figure 6 shows the number of versions in which some result changed for each query; the queries are ordered by the number of changes in their results, where we can see that the results of 44 queries (19.90%) change each time, 17 queries (7.69%) never change, and more generally, we note a quite uniform distribution of queries in between. More generally speaking, we conclude that our query set has a good balance of queries whose results never change, queries whose results always change, and queries whose results sometimes change.
20 d e g n a h c son 10 i s r e V
0 23 0 100 Query 200 Feature extraction: To compute the query features, we use Apache Jena to parse the query and extract the necessary statistics and determine the presence of the relevant query operators. In order to extract statistics on the dynamics of individual predicates in the dynamic graph, a challenge here is scalability, since we work with a total of 32.3 billion triples; hence we (1) sort each version of Wikidata, (2) apply a merge-sort iterator over each pair of consecutive versions (Gi and Gi+1) to detect triples that changed (Gi Gj ), writing a separate le for triples that were deleted (Gi Gj ) and added (Gj Gi), (3) from these les, we can then compute and sum the number of triples changed for each predicate between each pair of versions. Finally, in order to create the ground truth in terms of which results change between which versions, we index each version in Virtuoso and compute the results for each query against each version and write them to disk; we then compare consecutive pairs of results with a merge-sort. 6
Our experiments evaluate the (relative) quality of One Shot Change (OSC) predictions that can be made based on query features, predicate features, result features, as well as combinations thereof, using a selection of binary classi ers. Setting: To build our nal datasets, we must de ne a past interval to consider. With 23 versions, we must hold out at least one version to predict, leaving a maximum interval of 22 past versions to use for computing our features. However, the more past versions we consider for a prediction, the fewer examples we can generate; for example, if we consider 22 versions, we will only have one ground truth label for each query. In the end, we opted to consider intervals of 3, 5, 9 and 17 previous versions, for example, in the case of an interval of three versions, we use (Gi 3; Gi 2; Gi 1) to predict changes in queries results for the subsequent version (Gi), which allows us to predict OSC from G4 to G23 inclusive, providing 20 labeled examples per query. We thus have 4,420 labeled examples for intervals of 3, ranging down to 1,326 examples for intervals of 17. No feature explicitly indicates the versions given or the version to be predicted.
In the case of predicate dynamics, as discussed in Section 4, there are potentially many predicates per query, each with its own value for (G; p), where to reduce (and x) dimensionality, we may apply an aggregate function to choose the min, max or mean value over all predicates. In preliminary experiments, we found the mean value to o er the best results, followed by the max value; hence in what follows we adopt the mean value in our experiments.
For OSC prediction, we test four binary classi ers: Decision Trees, Linear SVM, Naive Bayes, and Nearest Neighbors. We split the data to use 80% for training and 20% for tests. To avoid over tting, we use strati ed 5-fold crossvalidation. We consider three types of features, as previously described { query features (q), predicate features (p) and result features (r) { considering historical data (only) from the xed interval. We also consider combinations of these features: qp, qr, pr and qpr.
Results: Table 4 shows the F1-score for the predictions made considering the union of di erent combinations of the sets of features (q, p, r) and varying the window sizes (3, 5, 9, 17); for reference, we include a baseline that randomly guesses yes/no respecting the observed class distribution. Given the number of con gurations presented, we only include F1 scores for reasons of space; however, we remark that the Precision and Recall scores were in general quite balanced. The best results were obtained using the features from r, where, as can be expected, prediction performs best when knowledge of changes in the historical results of the input query is available. The features from sets q and p { which do not assume the availability of such information { obtain a signi cantly lower F1-score; the best result including r was with pr (F1 = 0:831) using Linear SVM and window size 17, while the best results without r was with q (F1 = 0:60) using Linear SVM and window size 5.
Furthermore, in Figure 8, we show that the size of the window in uences the quality of the results when considering r features (blue), being better as the window increases. However, there is no clear trend in the results for increasing window sizes when considering models without using r features (red). (As aforementioned, we can see that Precision and Recall results are comparable.) 7
In this paper we evaluate methods to predict whether or not (OSC) the results of an input query will change at a xed point in the near future. More specifically, we evaluate a framework based on binary classi ers that accept features extracted from the query, from past versions of the data, and/or from the combination of both. Considering this framework, we hypothesize that there is a conceptual trade-o between the cost of computing features and their value for prediction: features extracted from queries alone are the most e cient to extract, not requiring historical data, but are quite coarse-grained for prediction; on the Classi er
q
Decision Trees 0.497 Naive Bayes 0.432 Nearest Neighbors 0.505 Linear SVM 0.596
Decision Trees 0.485 Naive Bayes 0.431 Nearest Neighbors 0.517 Linear SVM 0.600
Decision Trees 0.456 Naive Bayes 0.434 Nearest Neighbors 0.514
Linear SVM 0.578 other hand, features based on changes in results over previous versions for an (unseen) input query are often the most costly to acquire, but o er ne-grained information for prediction; nally, features based on the dynamics of predicates o er a balance between the two, allowing to summarize historical data into succinct statistics, thus o ering more ne-grained information than static query features but more coarse-grained information than historical results.
We thus explore this trade-o experimentally using 23 versions and 221 usercontributed queries for Wikidata to form a gold standard dataset. We use this gold standard dataset to evaluate the trade-o identi ed between di erent types of features for OSC predictions. Our results show that the features based on historical changes to query results perform best (reaching F1 = 0:831 in the best con guration), whereas considering static query features and predicate dynamics alone is less competitive (reaching F1 = 0:600 in the best con guration) when historical results are not available or are prohibitively costly to compute. Com1 0:8 0:6 0:4 0:2 0 3 5 9 F1 17
9 Precision 17 9 Recall 17 paring query and predicate features, in fact, query features performed better, where predicate features alone only barely outperformed a random baseline.
In conclusion, our results show that having knowledge of the historical changes of the results of a query is important for improving the quality of OSC predictions using binary classi ers. However, in many scenarios, such knowledge is often not available or may not be practical to compute. Considering a real-world caching use-case, for example, historical changes in results may be maintained for queries that are frequently repeated with relatively low-cost, but for a previously unseen query, computing results for past versions at runtime would incur a prohibitive cost. Hence, we identify an open research question: is it possible to estimate the dynamics of query results without relying on (costly) knowledge about historical changes of query results while staying competitive with the quality of prediction possible when such knowledge is available?
Regarding future work, our gold standard based on Wikidata could be
extended to consider more versions spanning a longer period of time and/or more
queries; a very large query dataset for Wikidata was recently published [
Acknowledgements This work was supported by the Millennium Institute for Foundational Research on Data (IMFD), by Fondecyt Grant No. 1181896 and by CONICYT PFCHA/Doctorado Nacional/2017 - 21171070.