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:
- 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.
- Extensional Query Processing: They applied a recursive algorithm that attempts to decompose complex queries into simpler sub-queries whose probabilities can be calculated independently.
- 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.
- Implementation: The researchers leveraged components of the Ontop OBDA system to translate SPARQL queries into a format suitable for their safeness-checker.
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).
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