PaperlayerView exact revision on arXiv

Source-linked AI summary

An Analytical Study of Large SPARQL Query Logs

Angela Bonifati, Wim Martens, Thomas Timm

arXiv:1708.00363v1cs.DB

TL;DR

Real SPARQL query logs are difficult to access, limiting evidence about how users query heterogeneous RDF endpoints. The paper analyzes a much larger multi-source corpus through syntactic, graph/hypergraph, complexity, and temporal analyses. It finds mostly simple acyclic queries, while cyclic queries are generally flower-shaped and have width two, with few width-three exceptions.

  • Problem

    Query logs are often inaccessible, limiting direct understanding of how end-users formulate queries across SPARQL endpoints.

  • Method

    The authors conduct a large-scale study combining syntactic analysis, graph and hypergraph shape and width analysis, synthetic engine experiments, and streak analysis over time.

  • Results

    The overwhelming majority of queries is acyclic; cyclic queries mostly form flowers and have tree- and hypertreewidth two, with few width-three exceptions.

  • Takeaways & Limitations

    The findings provide insights relevant to SPARQL query evaluation, optimization, tuning, and benchmarking.

  • Takeaways & Limitations

    The logs are dominated by small, simple queries, while Wikidata examples have different characteristics from SPARQL endpoint logs.

Abstract

from arXiv · show

With the adoption of RDF as the data model for Linked Data and the Semantic Web, query specification from end- users has become more and more common in SPARQL end- points. In this paper, we conduct an in-depth analytical study of the queries formulated by end-users and harvested from large and up-to-date query logs from a wide variety of RDF data sources. As opposed to previous studies, ours is the first assessment on a voluminous query corpus, span- ning over several years and covering many representative SPARQL endpoints. Apart from the syntactical structure of the queries, that exhibits already interesting results on this generalized corpus, we drill deeper in the structural char- acteristics related to the graph- and hypergraph represen- tation of queries. We outline the most common shapes of queries when visually displayed as pseudographs, and char- acterize their (hyper-)tree width. Moreover, we analyze the evolution of queries over time, by introducing the novel con- cept of a streak, i.e., a sequence of queries that appear as subsequent modifications of a seed query. Our study offers several fresh insights on the already rich query features of real SPARQL queries formulated by real users, and brings us to draw a number of conclusions and pinpoint future di- rections for SPARQL query evaluation, query optimization, tuning, and benchmarking.

1. INTRODUCTION

The paper analyzes a large, multi-source corpus of real SPARQL query logs, extending beyond syntactic statistics to query structure, complexity, evolution, and practical engine behavior. It reports predominantly simple, acyclic queries, with cyclic queries usually having flower-like structure and low width, while noting important scope boundaries.

  • Motivation: The study uses query logs spanning 2009–2017 from multiple SPARQL endpoints to examine how end-users formulate queries.The corpus addresses the limited accessibility and scale of prior real-query studies.
  • Novelty: The corpus is two orders of magnitude larger than those in previous studies, enabling a comprehensive shape analysis of diverse SPARQL queries.Earlier work examined smaller or narrower corpora and often did not characterize almost-star-shaped patterns.
  • Contributions: The analysis combines syntactic measures with projection and subquery usage, graph and hypergraph topology, shape analysis, treewidth, hypertreewidth, and query streaks.Streaks are sequences of similar queries interpreted as gradual modifications of a seed query.
  • Findings: The overwhelming majority of queries is acyclic, while most cyclic queries are flowers consisting of a central node with simple, small attachments.Cyclic queries generally have tree- and hypertreewidth two, with a few exceptions of width three.
  • Interpretation: The interpretation is constrained because more than 55% of logged queries use only one triple, and Wikidata example queries differ markedly from endpoint logs.The authors caution that these characteristics should not be taken to show larger-treewidth queries are unimportant in practice.
  • Practical evaluation: Synthetic chain-and-cycle experiments reveal different engine behaviors in Blazegraph and PostgreSQL, with the difference more pronounced for PostgreSQL.The authors interpret this as motivating specific optimization techniques for cyclic queries.

2. DATA SETS

The authors assemble a heterogeneous corpus of 180,653,910 queries from seven RDF data sources and multiple domains, then clean, parse, deduplicate, and analyze the resulting unique queries.

  • Corpus construction: The corpus contains 180,653,910 queries collected from USEWOD, DBpedia, British Museum, and Wikidata sources.The data spans DBpedia, SWDF, LGD, BioPortal, BioMed, British Museum, and Wikidata.
  • Corpus construction: The seven data sources cover diverse domains, including semantic web, geological, biological, bibliographic, museum, and Wikidata data.Most logs are from DBpedia, while Wikidata contributes user-submitted example queries.
  • Cleaning: The authors delete duplicate log files before analysis when files differ only in anonymization hash values.This prevents duplicated source files from affecting the corpus overview and subsequent analysis.
  • Cleaning: They remove non-query entries, retain actual SPARQL queries, parse them with Apache Jena 3.0.1, and deduplicate the valid queries.The analysis focuses on the resulting unique parsed queries.

3. PRELIMINARIES

The preliminaries define RDF data, SPARQL query components and pattern operators, then introduce conjunctive queries as the central restricted class used later in the study.

  • RDF and SPARQL: RDF data consists of triples ⟨s, p, o⟩, with subjects, predicates, and objects drawn from IRIs, blank nodes, and literals.For this paper, the distinctions among these RDF term categories are not important.
  • RDF and SPARQL: A SPARQL query is represented as (query-type, pattern P, solution-modifier).The pattern matches RDF data, while the solution modifier processes the resulting multiset of mappings.
  • RDF and SPARQL: SPARQL query types are Select, Ask, Construct, and Describe, which respectively return projected mappings, a Boolean answer, constructed triples, or descriptions of resources.Describe-query output is implementation-dependent.
  • SPARQL patterns: SPARQL patterns include triple and property-path patterns combined with And, Filter, Union, Opt, Graph, and nested subqueries.Property paths and subqueries are identified as SPARQL 1.1 features, and filters express built-in predicates, equalities, inequalities, and Boolean combinations.
  • SPARQL patterns: The paper illustrates these constructs with a Wikidata query using a property path, a triple pattern, and an English-language filter.The And operator is represented by a dot and may be implicit in concise syntax.
  • Conjunctive queries: A conjunctive query is a SPARQL pattern that uses only triple patterns and the And operator.This class is central to the subsequent analysis.

4. SHALLOW ANALYSIS

The shallow analysis characterizes query types, operators, sizes, and selected SPARQL features across a heterogeneous corpus. Most Select/Ask queries are small, commonly use conjunctive patterns with filters, and show substantial variation across datasets.

  • Query types: 87.97% of queries are Select, 4.97% Ask, 4.59% Describe, and 2.47% Construct, with substantial dataset-level variation.BioMed13 has almost 85% Describe queries, while LGD13 has 71% Construct queries.
  • Solution modifiers: Distinct usage varies sharply, reaching 97% in BritM14, 82% in BioP13, and 69% in BioP14.Across DBpedia12–16, the corresponding percentages are 18%, 8%, 11%, 38%, and 8%.
  • Operators: Filter, And, Union, and Opt are common body operators, while Graph is concentrated in BioPortal logs and Filter ranges from 61% in LGD14 to 3% or less in BioMed13 and BioP13.95% of queries using Graph originate from BioP13 and BioP14.
  • Aggregation: Aggregation operators occur in 3% or fewer of queries in nearly all datasets, except Count in LGD14 at 31% and Group By in WikiData17 at 30%.The authors associate WikiData17’s higher aggregation use with its cherry-picked example-query collection rather than an endpoint log.
  • Query size: 56.45% of Select/Ask queries use at most one triple, 90.76% at most six, and 99.32% at most twelve.The largest queries contain 209 and 211 triples in DBpedia15 and 221 and 229 in BioMed13.
  • Patterns and subqueries: 66.27% of queries are conjunctive patterns with filters, rising to 74.83% when Optional is added.Only 0.54% of queries use subqueries, although usage reaches 9.74% in WikiData.

5. STRUCTURAL ANALYSIS

The paper represents SPARQL queries as graphs or hypergraphs to expose structural complexity, then analyzes query fragments and compares chain and cycle workloads across engines.

  • Query Classes: 39.061.206 AOF patterns comprise 74.83% of Select and Ask queries in the corpus.
  • Graph and Hypergraph Representations: Canonical graphs represent variables and constants as nodes connected by triple-pattern edges, while hypergraphs represent variable and blank-node co-occurrence in triples.
  • Graph and Hypergraph Representations: Predicate variables can make canonical graphs misleading because they omit join conditions that the canonical hypergraph captures.
  • Comparative Evaluation: Synthetic chain and cycle workloads vary query length from 3 to 8 and compare Blazegraph with PostgreSQL, with cycles representing hypertreewidth two.
  • Query Classes: 54.58% of AOF patterns are conjunctive queries, while 84.08% belong to the CQF fragment with simple filters.
  • Query Classes: 98.53% of AOF patterns are well-designed, but well-designedness alone does not guarantee constant hypertreewidth or tractable evaluation.

6. SHAPE ANALYSIS

The shape analysis finds that logged CQ-like queries are overwhelmingly small and acyclic, while most cyclic queries have flower-like structure and low tree or hypertree width.

  • Query Size and Classical Shapes: 82% of CQs, 83.45% of CQF queries, and 75.52% of CQOF queries contain only one triple.
  • Query Size and Classical Shapes: The analysis classifies CQ, CQF, and CQOF queries using cumulative graph shapes including chains, stars, trees, forests, flowers, and flower sets.
  • Cyclic Shapes: Plain cycles are uncommon; many remaining cyclic queries consist of a central node with simple attachments, termed flowers.
  • Cyclic Shapes: Flower sets improve coverage beyond plain forests by roughly 0.05% across CQ, CQF, and CQOF fragments, approaching complete coverage more closely.
  • Constants and Cycles: 9.66 million single-edge CQs, or 78.70% of single-edge CQs, use constants.
  • Constants and Cycles: 39,471 queries have shortest cycles of length three, while only 26 have shortest cycles longer than five and two reach length 14.
  • Tree- and Hypertreewidth: Forests and subclasses have treewidth one; cycles, flowers, and flower sets have treewidth two, with one remaining query at treewidth three.
  • Tree- and Hypertreewidth: Among the 6,959,510 CQOF queries requiring hypergraphs, all but 86 width-two and eight width-three queries have hypertree width one.

7. PROPERTY PATHS

Property paths are uncommon overall, often express simple edge tests, and mostly remain within a tractable expression class under the cited simple path semantics.

  • Prevalence and Forms: 247,404 property paths occur in the corpus, although 92 WikiData17 queries, or 29.87%, use property paths.
  • Prevalence and Forms: 63,039 property paths are simple !a expressions and 306 are reverse-edge ˆa expressions; the analysis focuses on 184,059 more complex paths.
  • Prevalence and Forms: 66,262 complex property paths, representing 36%, use reverse navigation with the ˆ operator.
  • Complexity: Only one corpus expression, (a/b)∗, falls outside the Ctract class associated with polynomial-time evaluation under simple path semantics.

8. EVOLUTION OF QUERIES OVER TIME

The study examines whether users refine queries through sequences of similar log entries, introducing streaks to capture these patterns. In three DBpedia day logs, the longest observed streak contained 169 queries under a window size of 30.

  • Implications: The authors describe the observed results as preliminary and suggest that similar-query sequences may warrant specialized optimization techniques.This behavior is framed as occurring in certain contexts rather than universally.
  • Streaks: A streak is a sequence of nearby queries in which each successive query matches its predecessor under a similarity test.Queries must be within a chosen window and have no intervening query similar to the preceding query.
  • Similarity test: The similarity test used normalized Levenshtein distance after removing namespace prefixes, requiring queries to be at least 75% identical from their first query keyword.The distance was normalized by the length of the longer query string.
  • Results: 169 queries formed the longest streak found with window size 30, and larger windows produced still longer streaks.The authors identify window tuning and more complex within-streak similarity metrics as future research directions.

9. CONCLUSIONS AND DISCUSSION

The paper analyzes 180,653,910 queries across heterogeneous RDF sources, combining syntactic, structural, and temporal analyses. It finds mostly simple query workloads while showing that shape analysis and synthetic comparisons can inform evaluation, optimization, tuning, benchmarking, and graph-query-language design.

  • Conclusions: The corpus contains 180,653,910 queries from seven RDF data sources spanning DBpedia, biological, geological, bibliographic, museum, and Wikidata datasets.Most datasets show similar simplicity, while British Museum and Wikidata have distinct characteristics because of templates and example-query curation.
  • Conclusions: Most queries contain one or two triples, but DBpedia also includes substantial numbers of queries with 11 or more triples.The paper reports occurrences of up to 21% for queries with at least 11 triples in DBpedia datasets.
  • Conclusions: The study combines syntactic statistics, projection and subquery analysis, graph and hypergraph shape analysis, streak mining, and synthetic chain-cycle workload experiments.The synthetic experiments compare average runtimes in Blazegraph and PostgreSQL.
  • Conclusions: Shape analysis is presented as relevant to designing graph query languages and to understanding structural effects on query evaluation.The paper connects query shapes with canonical graphs and hypergraph tree-likeness.

APPENDIX

The appendix extends the analysis to a larger corpus containing duplicates and reports its syntactic, fragment, shape, and property-path characteristics. Compared with the unique-query dataset, larger and more complex queries appear more often when duplicates are retained.

  • Appendix: The duplicate-containing appendix corpus contains 173,798,237 valid queries.Its characteristics are summarized in Table 1, with additional analyses reported in the appendix.
  • Syntactic analysis: The appendix repeats keyword-count and operator-distribution analyses and reports triple-count percentages for the complete corpus.These results are presented in Tables 7 and 8 and Figure 8.
  • Query fragments and shapes: The appendix reports relative sizes for CQ, CQF, and CQOF conjunctive-query fragments and cumulative shape results across all logs.The fragment sizes appear in Figure 9 and the cumulative shape analysis in Table 9.
  • Corpus comparison: Larger and more complex queries occur more often in the duplicate-containing corpus than in the unique-query corpus.This is the appendix's explicit comparison between the two corpus variants.
  • Property paths: The complete corpus analysis also reports the structure of navigational property paths.The property-path results are presented in Figure 10.
Loading 1708.00363v1…