Visualizing How-Provenance Explanations for SPARQL Queries

Luis Galárraga, Daniel Hernández, Anas Katim, Katja Hose

Visualizing How-Provenance Explanations for SPARQL Queries

Introduction

Knowledge Graphs (KGs) such as Wikidata and DBpedia have become indispensable for data-driven applications. However, they often function as "black boxes." When a user executes a SPARQL query, they receive a result set without a clear understanding of which specific triples in the database were responsible for those answers or how they were logically combined. This lack of transparency complicates query debugging and makes it difficult to assess the trustworthiness of data sources.

To address this, researchers have developed SPARQLprov, an engine-agnostic tool designed to provide "how-provenance" explanations. Unlike traditional provenance solutions that require specialized database engines, SPARQLprov works as a middleware layer on top of standard SPARQL endpoints.

The SPARQLprov Framework

The core innovation of SPARQLprov lies in its ability to generate explanations without modifying the underlying database architecture. It achieves this through a four-stage process:

  1. Reification: Since standard RDF triples lack unique identifiers, the system assigns IDs to statements.
  2. Query Rewriting: The user's standard SPARQL query is automatically transformed into a more complex version that requests both the original data and the metadata required for provenance.
  3. Evaluation: The rewritten query is executed on a standard endpoint (e.g., Wikidata).
  4. Decoding: The raw metadata is translated back into human-readable polynomials and visual subgraphs.
The SPARQLprov workflow: query rewriting and provenance decoding.

Reification and How-Provenance

At the heart of the explanation is "how-provenance," which structures the origin of data into mathematical polynomials. For instance, if a result is derived from the conjunction of two facts or the alternative of a third, the provenance might be expressed as $(a \otimes b) \oplus c$.

To make these polynomials meaningful, the system relies on reification. By treating edges in the graph as entities with their own IDs, the tool can pinpoint exactly which triples contributed to a result. This allows for a "Neighborhood" view, where the relevant subgraph is highlighted for the user, showing the specific facts (e.g., gender, occupation, nationality) that led to the query match.

An example RDF graph with reified edges (e1 to e7) representing specific facts about political figures.

Handling Complex Queries and Negation

One of the most significant technical hurdles in provenance is handling non-monotonic queries—those involving negation or set differences (the MINUS operator). SPARQLprov utilizes "spm-semirings," a mathematical framework that allows for a "subtraction" equivalent in provenance. This enables the tool to explain not just why a result exists, but also why it was not filtered out by an exclusion criterion, or conversely, to show "non-solutions" that were excluded.

Real-world Application: Wikidata

The primary testbed for SPARQLprov is Wikidata. As a massive, public general knowledge graph that already utilizes a form of reification for its statements, Wikidata is ideal for demonstrating live provenance explanations. Users can write queries against the live Wikidata endpoint and receive annotated results that show the specific source triples involved, facilitating source verification and data auditing.

Limitations and Future Directions

The main challenge for this middleware approach is query complexity. Rewriting a query to include provenance metadata significantly increases its execution time. On public endpoints with strict timeouts, this can lead to failures. Current mitigations include the use of LIMIT clauses to keep query execution manageable.

Future work aims to apply these visual explanations to high-stakes tasks like source verification and to develop more intuitive visual metaphors for representing complex provenance polynomials to non-expert users.

Summary updated

Abstract

Knowledge graphs (KGs) are vast collections of machine-readable information, usually modeled in RDF and queried with SPARQL. KGs have opened the door to a plethora of applications such as Web search or smart assistants that query and process the knowledge contained in those KGs. An important, but often disregarded, aspect of querying KGs is query provenance: explanations of the data sources and transformations that made a query result possible. In this article we demonstrate, through a Web application, the capabilities of SPARQLprov, an engine-agnostic method that annotates query results with how-provenance annotations. To this end, SPARQLprov resorts to query rewriting techniques, which make it applicable to already deployed SPARQL endpoints. We describe the principles behind SPARQLprov and discuss perspectives on visualizing how-provenance explanations for SPARQL queries.
BibTeX
@inproceedings{galarraga2023visualizing,
  author = {Luis Galárraga and Daniel Hernández and Anas Katim and Katja Hose},
  title = {{Visualizing How-Provenance Explanations for SPARQL Queries}},
  booktitle = {The Web Conference},
  year = {2023},
  doi = {10.1145/3543873.3587350},
}
Figure