Ensuring the Completeness and Soundness of SPARQL Queries Using Completeness Statements about RDF Data Sources

Tracking #: 1765-2977

This paper is currently under review
Fariz Darari
Werner Nutt
Simon Razniewski
Sebastian Rudolph

Responsible editor: 
Aidan Hogan

Submission type: 
Full Paper
RDF generally follows the open-world assumption: information is incomplete by default. Consequently, SPARQL queries cannot retrieve with certainty complete answers, and even worse, when they involve negation, it is unclear whether they produce sound answers. Nevertheless, there is hope to lift this limitation. On many specific topics (e.g., children of Trump, Apollo 11 crew, EU founders), RDF data sources contain complete information, a fact that can be made explicit through completeness statements. In this work, we leverage completeness statements to bridge the gap between RDF and SPARQL. We first develop a technique to check query completeness based on RDF data with completeness information. For queries with negation, we approach the problem of query soundness checking. We provide a formalization and characterize the soundness problem via a reduction to the completeness problem. We further develop efficient methods for completeness checking, and conduct experimental evaluations based on Wikidata to demonstrate the feasibility of our approach.
Full PDF Version: 
Under Review