Analyzing real-world SPARQL queries in the light of probabilistic data

Jörg Schönfisch, Heiner Stuckenschmidt

Abstract

Handling uncertain knowledge – like information extracted from unstructured text, with some probability of being correct – is crucial for modeling many real-world domains. Ontologies and ontology-based data access (OBDA) have proven to be versatile methods to capture this knowledge. While theoretical work exists for probabilistic OBDA, identifying efficiently processable (safe) queries, there has been little analysis on the safeness of probabilistic queries in real-world applications. In this paper, we investigate queries collected from several public SPARQL endpoints and determine the distribution of safe and unsafe queries. Our analysis shows that 99.68% of queries in practice are safe, making probabilistic OBDA feasible and practical to fulfill real-world users’ information needs.

Introduction: The Challenge of Uncertain Data

In the Semantic Web, Ontology-Based Data Access (OBDA) allows users to query databases through high-level conceptual models. However, real-world data is frequently uncertain, arising from noisy extraction processes or the integration of conflicting sources. Probabilistic databases address this by assigning a probability to each fact.

The primary hurdle is computational: calculating the probability of a query answer follows a strict "dichotomy." A query is either safe (solvable in polynomial time) or unsafe (technically #P-hard). Until this research, it was unknown if the queries actually written by users were safe or unsafe. If most real-world queries were unsafe, probabilistic OBDA would remain a theoretical curiosity rather than a useful tool.

Methodology

The authors developed a framework to evaluate query safeness by combining several techniques:

  1. Query Rewriting: Using the DL-Lite description logic (the foundation of OWL 2 QL), high-level ontology queries are rewritten into standard database queries, specifically Unions of Conjunctive Queries. Figure 1 illustrates the specific rewriting rules applied to atoms and inclusions.
  2. Extensional Query Processing: They applied a recursive algorithm that attempts to decompose complex queries into simpler sub-queries whose probabilities can be calculated independently.
  3. Safeness Check: If the algorithm can completely decompose the query using specific rules, such as finding "separator variables," the query is deemed safe. If it cannot, it is classified as unsafe.
  4. Implementation: The researchers leveraged components of the Ontop OBDA system to translate SPARQL queries into a format suitable for their safeness-checker.
Rewriting rules for atoms and inclusions in DL-Lite.

Datasets and Query Distribution

The study utilized the Linked SPARQL Queries (LSQ) dataset, which contains logs from four major public SPARQL endpoints: DBpedia (Wikipedia data), Linked Geo Data (LGD) (OpenStreetMap data), Semantic Web Dog Food (SWDF) (academic conference metadata), and the British Museum (BM) (cultural heritage data).

Distribution of SPARQL query types across the four analyzed datasets.

Out of approximately 1.2 million queries collected, the analysis focused on a subset of roughly 507,000 SELECT and ASK queries that could be translated into conjunctive queries for analysis. As shown in Figure 2, SELECT queries represent the vast majority of the workload across all datasets.

Key Insights and Results

The analysis yielded several significant findings regarding the practicality of probabilistic data access:

  • 99.68% Safeness: Of the queries analyzed, nearly all were safe. This is a massive green light for developers building probabilistic systems, proving that the structural complexity of typical user queries does not hit theoretical computational limits.
  • Structural Simplicity: Most human-written queries are structurally simple, often following "star-shaped" patterns (multiple properties describing a single subject). These patterns are inherently easier for probabilistic engines to handle.
  • The "Machine" Factor: Unsafe queries were rare and often appeared to be generated by automated tools rather than humans. For example, the SWDF dataset showed a higher rate of unsafe queries (2.07%) compared to DBpedia (0.28%), likely due to bot-generated patterns.
  • Efficiency: Determining whether a query was safe took an average of only 86ms, meaning the overhead for checking safeness is negligible in a production environment.

Conclusion and Future Directions

This research demonstrates that the "average case" for the Semantic Web is remarkably well-behaved. Probabilistic OBDA is not just a theoretical framework but a highly practical one for real-world applications.

However, limitations remain. Current safeness algorithms do not yet fully account for SPARQL features like OPTIONAL, GROUP BY, or DISTINCT. Future work will focus on extending these algorithms and investigating approximation methods for the 0.32% of queries that are unsafe, ensuring that probabilistic systems can handle even the most complex user needs.

Summary updated

Abstract

Handling uncertain knowledge – like information extracted from unstructured text, with some probability of being correct – is crucial for modeling many real world domains. Ontologies and ontology-based data access (OBDA) have proven to be versatile methods to capture this knowledge. Multiple systems for OBDA have been developed and there is theoretical work towards probabilistic OBDA, namely identifying efficiently processable (safe) queries. However, there is no analysis on the safeness of probabilistic queries in real-world applications, or in other words the feasibility of fulfilling users’ information needs over probabilistic data. In this paper we investigate queries collected from several public SPARQL endpoints and determine the distribution of safe and unsafe queries. This analysis shows that many queries in practice are safe, making probabilistic OBDA feasible and practical to fulfill real-world users’ information needs.
BibTeX
@inproceedings{schonfisch2016analyzing,
  author = {Jörg Schönfisch and Heiner Stuckenschmidt},
  title = {{Analyzing real-world SPARQL queries in the light of probabilistic data}},
  booktitle = {MADOC},
  year = {2016},
}
Figure