Popular SPARQL query endpoints hosted by open knowledge graphs such as Wikidata and DBpedia process hundreds of thousands or even millions of queries per day. Making sense of queries at this scale is challenging. We propose a taxonomy of basic graph patterns (BGPs) in order to induce a hierarchical structure from such patterns found in a large query log. The leaves of this taxonomy are the raw basic graph patterns extracted from each query of the log. Each layer thereafter applies a generalisation step followed by a canonicalisation step, with each layer representing an increasingly coarse partition based on an increasingly more general motif. Generalisations are applied for constant subjects/objects (nodes), constant predicates (edge labels), direction, constant/variable distinction, and homomorphic equivalence. We discuss use-cases, define these generalisation steps, and apply them to induce a taxonomy of BGPs from a subset of the Wikidata query log.
There are now hundreds of public SPARQL endpoints available on the Web [
Thus, given a large SPARQL query log such as that published for Wikidata [
The design of such a taxonomy is challenging, and indeed there are potentially many ways
in which such a taxonomy can be defined. But we think the idea is worth exploring in order
to help bring order to large SPARQL query logs. In this work, we take some initial steps
in this direction by focusing on the case of basic graph patterns [
Caching [12, 13]: The taxonomy can identify frequent motifs that, if cached, could increase cache hit rates and improve query evaluation performance.
Optimisation [14]: The taxonomy could be used to decide on specialised indexes and optimisations to reduce the costs for frequent motifs.
Benchmarking [15, 16]: The taxonomy can be used to classify diferent types of graph
patterns for benchmarking, enabling the comparison of diferent engines for diferent motifs.
Log exploration [
Paper outline In Section 2, we discuss related works that classify or generalise queries from SPARQL logs. Section 3 presents the taxonomy we propose, while Section 4 presents the results of applying our taxonomy to a sample of the Wikidata query logs. Section 5 concludes.
The use of SPARQL query logs for understanding user demands has become a rich topic of interest, leading to a wide body of research. For space reasons, we focus on those works that specifically look at generalising and/or classifying real-world queries in such logs.
The first category of related works extract high-level query patterns for the purpose of
analysing logs. Bonifati et al. [
The second category of works process log queries for the purposes of benchmarking. Saleem et al. [15] propose a framework, called FEASIBLE, that extracts diferent features from queries, such as join vertex degree and shape, number of triple pattern and their selectivity, etc.; these features are used to select a small number of representative queries for a benchmark. Angles et al. [16] propose high-level categories of subqueries (BGPs, property paths, etc.) for the Wikidata query log that are then used to compare the performance of diferent engines.
In terms of novelty, rather than pre-defining shapes/motifs, we instead pre-define a set of generalisation steps that can produce arbitrary motifs. We are also not aware of works that propose a hierarchical way to structure such motifs.
In this section, we present our proposed taxonomy of BGPs based on increasingly high-level motifs induced by a sequence of generalisation steps. We first present definitions, then an example, and finally summarise how we implemented software to compute the taxonomy. Preliminaries. Let I, L and V denote the set of all IRI, literal and variable terms, respectively. A triple pattern = (, , ) ∈ (I ∪ L ∪ V) × (I ∪ V) × (I ∪ L ∪ V) is an RDF triple allowing variables in any position. We use C = I ∪ L to denote constants where the distinction between IRIs and literals does not matter. A set of triple patterns is called a basic graph pattern (BGP).1 Letting denote a BGP, we denote by vars() the set of variables appearing in , by cons() the set of constants appearing in , by nodes() the set of subject/object terms (i.e., nodes) in , and by labs() the set of predicate terms (i.e., edge labels) in .
Given a BGP , we will define a sequence of generalisation steps that form increasingly high-level equivalence classes of BGPs induced by patterns that we call motifs. Specifically, a generalisation step is a transformation of a BGP that yields an equivalence relation ∼ on BGPs such that, given two BGPs and , we say that ∼ if and only if () = (). We then call () (or equivalently ()) an -motif. To define specific generalisation steps, we introduce a partial term mapping : C∪V → C∪V whose domain is denoted by dom( ). Given a BGP , we denote by () the image of under , i.e., () = {( ′(), ′(), ′()) | (, , ) ∈ } where ′() = () for all ∈ dom( ), and ′() = for all ∈/ dom( ); i.e., rewrites some of the terms in , leaving terms for which it is not defined as they are. Letting s, p and o denote the subject, predicate and object positions, we may also use selective images to rewrite terms only in selected positions; for example, s,o() = {( ′(), , ′()) | (, , ) ∈ } only rewrites subject and object terms with .
Proposed Taxonomy. There are innumerable distinct generalisation steps that one could consider, and indeed the “best” choice may depend on external factors such as the particular use-cases, logs, etc., involved. The order in which the generalisation steps are applied can also afect the resulting taxonomy. In the following, we propose a concrete set of generalisation steps inspired by the idea of incrementally generalising the graph structure of BGPs. As a zeroth step, we abstract away variable names from the input BGPs (modulo isomorphism). In subsequent steps we abstract away the values of particular constants in order to yield an increasingly abstract graph structure. We then abstract away edge labels and direction in order to yield a directed and then undirected graph, respectively. Thereafter we abstract away the 1We assume that blank nodes appearing in a BGP are mapped to fresh variables [11]. distinction between constants and variables, and finally we compute the core of the graph. As aforementioned, this is one way in which generalisation steps can be applied. Exploring other possible steps, and the motifs and taxonomies they yield, is an interesting topic for future work. Definition 3.1.
We define the following generalisation steps, where and are BGPs: 0. The zeroth step generalises variable names, capturing isomorphism modulo variables. We say that ∼ 0 if and only if there exists a one-to-one term mapping : vars() → vars() such that () = . 1. The first step further generalises constant nodes in a BGP, capturing isomorphism modulo variables and constant nodes. We say that ∼ 1 if and only if there exists a one-to-one term mapping : nodes() ∩ cons() → nodes() ∩ cons() such that s,o() ∼ 0 . 2. The second step further generalises constant edge labels (predicates) in a BGP, capturing isomorphism modulo variables and constants. We say that ∼ 2 if and only if there exists a one-to-one term mapping : labs() ∩ cons() → labs() ∩ cons() such that p() ∼ 1 . 3. The third step generalises edge labels, capturing isomorphism of the directed graph of the BGP while still distinguishing constants and variables. Let c ∈ C and v ∈ V denote a reserved constant and variable, respectively. Let : C ∪ V → {c, v} denote a term mapping such that () = c for all ∈ C and () = v for all ∈ V. We say that ∼ 3 if and only if p() ∼ 2 p(). 4. The fourth step generalises edge direction, capturing isomorphism of the undirected graph of the BGP while still distinguishing constants and variables. Let ± = {(, , ) | (, , ) ∈ or (, , ) ∈ } denote the completion of . We say that ∼ 4 if and only if ± ∼ 3 ± . 5. The fifth step generalises constant and variable distinction, capturing isomorphism of the undirected graph of the BGP without distinguishing constants and variables. Here we choose to map constants to variables. We say that ∼ 5 if and only if there exists a one-to-one term mapping : cons() ∪ cons() → V ∖ (vars() ∪ vars()) such that () ∼ 4 (). 6. The sixth step generalises non-core edges and nodes, capturing homomorphic equivalence of the undirected graph of the BGPs. We say that there is a homomorphism from to , denoted → , if and only if there exists a term mapping : vars() → vars() ∪ cons() such that () ⊆ . We then say that and are homomorphically equivalent modulo variables, denoted ≃0 , if and only if → and → . Let us overload the previous definitions, where we denote by ≃0,...,5 the steps ∼ 0,...,5 replacing the zeroth step ∼ 0 with ≃0. We say that ∼ 6 if and only if ≃5 .
Each generalisation step induces a partition of a set of BGPs ℬ via the quotient set ℬ/∼ . Example. Take the following SPARQL query, which intuitively asks for information about papers published in AMW that cite other AMW papers:
SELECT ?x ?p ?o WHERE { ?x :venue :AMW . ?y :venue :AMW . ?x :cites ?y . ?x ?p ?o . } :venue :cites :AMW :cites :venue (a) Zeroth step (b) First step (c) Second step (d) Third step (e) Fourth step (f) Fifth step (g) Sixth step Implementation. We implemented the extraction of the aforementioned taxonomy using the QCan package [11], which ofers methods for canonicalising SPARQL queries. Specifically, QCan represents SPARQL BGPs as RDF graphs in a reified form using r-graphs. The package can then invoke the blabel package [17], which canonically labels existential values, and can also perform RDF leaning, which is used to calculate the core of the graph required for step 6.
In this section, we extract the taxonomy from the BGPs of a large sample of queries from the
Wikidata SPARQL logs [
Robotic queries We first present the results for robotic queries. We took a random sample of 1,000,000 queries from the set of robotic queries in the interval. We then extracted all the BGPs contained in these queries, giving us a total of 1,781,337 BGPs. Table 1a presents some high-level statistics, showing the number of motifs generated at each step, along with the motif (equivalence class) with the largest number of BGPs. The results clearly show that each successive level of the taxonomy finds less unique motifs, while finding larger equivalence classes for these queries. This is of interest for exploring the logs: a user starting at step 6 (the highest level) can expand to a reasonable number (55) of child motifs at step 5, ordered by size; expanding these motifs from step 5, they can expect, on average, 2–3 child motifs, and so forth.
In Table 2, we present the top 5 motifs at each step for these robotic queries, starting from step 1. As before, dashed lines indicate variables while solid lines indicate constants. At step 1, the motifs represent parameterised queries, where nodes (subjects/objects), specifically, are generalised. The Wikidata properties P300 and P214 seen in this step indicate an ISO 3166-2 code for countries, and a VIAF ID used by libraries, respectively. The results show that the most common BGPs are composed of single triple patterns. The top motif is unusual in that it has no variable: it stems from a syntactic shortcut used in Wikidata for selecting the languages of labels returned by a custom service. We also see that the third, fourth and fifth motifs contain two variables; such BGPs may form part of a larger query, and be contained, for example, in an OPTIONAL clause. Steps 2 and 3 are quite similar to each other. We see that the most common motif in both steps refers to a singleton BGP with a constant predicate and variable nodes, but in the second and fifth positions, we see popular join shapes. Step 4 generalises edge direction, where we see a similar set of results to the previous two steps; the motif with a single edge having a constant and variable node is more prominent here as it merges two cases from step 3: one where the subject is the variable, and the other where the object is the variable. Removing the constant/variable distinction in step 5, we see many of the simpler motifs merged into the ifrst two motifs, but thereafter, we see diferent types of joins, including disconnected patterns Step 1 2 3 4 5 6 1 c in the fourth and fifth positions; these disconnected patterns are due to geographic queries that apply a join between two variables based on geographic distance, rather than a natural equi-join. At step 6, which looks at the cores of the step 5 graphs, we find three motifs: 1,780,647 BGPs collapse to a core with a single edge between two nodes (this includes acyclic queries and queries with even-length cycles, for example), 649 BGPs collapse to a self-loop on one node (this includes all and only queries with a self-loop, i.e., a triple pattern with the same subject and object), while 41 BGPs collapse to a triangle (as per the example shown in Figure 1). Organic queries Next we extract our taxonomy from the set of all 872,555 organic queries in the chosen interval, which contain 2,198,557 BGPs. Table 1b presents the overall statistics regarding the number of motifs and the largest equivalence class size at each step. Of interest is 5 wdt:P214 83,229 (4.67%) c2
c1 71,524 (4.02%) 71,664 (4.02%) 76,558 (4.30%) 26,998 (1.52%) wdt:P300 88,199 (4.95%)
c 268,915 (15.10%) 270,846 (15.20%) 296,520 (16.65%) 53,511 (3.00%) — — that the number of motifs is generally much higher than in the robotic case, indicating more diverse query shapes. This is to not surprising as one would expect robotic trafic to account for more regular (e.g., parameterised) queries when compared with queries created by users.
As before, Table 3 presents the top 5 motifs at each step – starting from step 1 – in the organic
case. The Wikidata properties P31, P625 and P238 seen in step 1 refer to instance of, coordinate
location and IATA airport code, respectively. We see the same top motif as in the case of robotic
queries relating to Wikidata’s label service. However, we also see a number of more complex
motifs, including the fourth and fifth motif, which we suspect may be misclassified bot trafic
(the logs classify organic and robotic trafic using a number of heuristics, such as user-agent,
the volume of similar queries originating from a single source, etc. [
We believe that better tools are needed in order to summarise, structure, explore and understand the contents of large SPARQL logs. In this work, we have proposed a taxonomy for understanding the structure (specifically) of BGPs found in such a log. We proposed a sequence of generalisation steps that, when applied to BGPs, yield increasingly high-level motifs by incrementally abstracting away details from the BGP, generating a hierarchical taxonomy over those BGPs. Extracting the taxonomy for a sample of Wikidata queries, we gain some interesting insights into the most common motifs occurring in BGPs relating to frequently accessed predicates, frequent join types, the rarity of acyclic queries, the presence of disconnected graph patterns, and some potentially misclassified organic queries.
For future work, we would like to develop a user interface that allows for exploring the
taxonomy of a given SPARQL query log: starting from step 6 (the highest level), the user is
presented the motifs and the number of associated BGPs in descending order; upon clicking a
motif, the sub-motifs at the lower level are presented in the same order. This would allow the
user to start from a high-level view of the BGPs of the log, and “drill-down” on specific motifs
for more details. We are also interested in exploring diferent sequences of generalisation steps
that might yield more interesting insights. Another direction would be to study how diferent
generalisation steps preserve diferent graph metrics; a key metric along these lines would be
(hyper-)treewidth, which captures how “tree-like” a query is and predicts the complexity of
evaluating the query [
This work was supported by Fondecyt No. 1221926 and by ANID – Millennium Science Initiative Program – Code ICN17_002. can collapse cycles of even length to a single edge, cycles of odd length or even cliques to a self-loop, etc. [11] J. Salas, A. Hogan, Semantics and canonicalisation of SPARQL 1.1, Semantic Web 13 (2022) 829–893. doi:10.3233/SW-212871. [12] G. T. Williams, J. Weaver, Enabling fine-grained HTTP caching of SPARQL query results, in: The Semantic Web - ISWC 2011 - 10th International Semantic Web Conference, Bonn, Germany, October 23-27, 2011, Proceedings, Part I, 2011, pp. 762–777. doi:10.1007/978-3-642-25073-6\_48. [13] N. Papailiou, D. Tsoumakos, P. Karras, N. Koziris, Graph-aware, workload-adaptive SPARQL query caching, in: ACM SIGMOD International Conference on Management of Data, ACM, 2015, pp. 1777–1792. doi:10.1145/2723372.2723714. [14] W. Ali, M. Saleem, B. Yao, A. Hogan, A. N. Ngomo, A survey of RDF stores & SPARQL engines for querying knowledge graphs, VLDB J. 31 (2022) 1–26. doi:10.1007/ s00778-021-00711-3. [15] M. Saleem, Q. Mehmood, A. N. Ngomo, FEASIBLE: A feature-based SPARQL benchmark generation framework, in: The Semantic Web - ISWC 2015 - 14th International Semantic Web Conference, Bethlehem, PA, USA, October 11-15, 2015, Proceedings, Part I, volume 9366 of Lecture Notes in Computer Science, Springer, 2015, pp. 52–69. doi:10.1007/978-3-319-25007-6\_4. [16] R. Angles, C. B. Aranda, A. Hogan, C. Rojas, D. Vrgoc, WDBench: A Wikidata Graph Query Benchmark, in: The Semantic Web - ISWC 2022 - 21st International Semantic Web Conference, Virtual Event, October 23-27, 2022, Proceedings, volume 13489 of Lecture Notes in Computer Science, Springer, 2022, pp. 714–731. doi:10.1007/978-3-031-19433-7\_41. [17] A. Hogan, Canonical forms for isomorphic and equivalent RDF graphs: Algorithms for leaning and labelling blank nodes, ACM TOW 11 (2017) 22:1–22:62. doi:10.1145/3068333.