Geospatial Compliance Metadata Automation Hub

Querying a Provenance Graph with SPARQL

Write the backward query first — given a published output, what produced it — because three quarters of real provenance questions run in that direction, and a graph indexed for forward traversal answers them slowly or not at all.

A provenance graph is only worth building if it can be interrogated, and interrogation means SPARQL for anything beyond a single hop. The queries themselves are short; what makes them useful is knowing which four questions to write and how to keep them from running away across a graph that grows without bound. This guide sits under spatial data lineage and provenance tracking, within Spatial Data Audit Reporting & Compliance Governance.

The four questions a provenance graph is actually askedBackward, forward, reproducibility and accountability queries compared by direction, cost and how often they are asked.DirectionCostShare of queriesWhat produced this?backwardbounded by depthabout three in fiveWhat used this source?forwardcan fan out widelyabout one in fiveWhat is affected if this iswrong?forward, transitiveexpensiveabout one in sixWho and what version ran it?single hoptrivialthe remainder
The first row is most of the traffic and the one to design the graph around.

Automated Python Implementation

#!/usr/bin/env python3
"""Query a PROV-O provenance graph for the questions that actually get asked."""
from rdflib import Graph, Namespace, URIRef

PROV = Namespace("http://www.w3.org/ns/prov#")

BACKWARD = """
PREFIX prov: <http://www.w3.org/ns/prov#>
SELECT ?activity ?label ?started ?agent ?source
WHERE {
  ?output prov:wasGeneratedBy ?activity .
  OPTIONAL { ?activity <http://www.w3.org/2000/01/rdf-schema#label> ?label }
  OPTIONAL { ?activity prov:startedAtTime ?started }
  OPTIONAL { ?activity prov:wasAssociatedWith ?agent }
  OPTIONAL { ?activity prov:used ?source }
}
ORDER BY ?started
"""

FORWARD = """
PREFIX prov: <http://www.w3.org/ns/prov#>
SELECT DISTINCT ?consumer ?activity
WHERE {
  ?activity prov:used ?source .
  ?consumer prov:wasGeneratedBy ?activity .
}
"""

# Transitive closure, bounded: an unbounded path over a growing graph is how a
# provenance store acquires a reputation for being slow.
AFFECTED = """
PREFIX prov: <http://www.w3.org/ns/prov#>
SELECT DISTINCT ?affected
WHERE {
  ?affected prov:wasDerivedFrom{1,%(depth)d} ?source .
}
"""

ACCOUNTABILITY = """
PREFIX prov: <http://www.w3.org/ns/prov#>
SELECT ?agent ?version
WHERE {
  ?output prov:wasGeneratedBy ?activity .
  ?activity prov:wasAssociatedWith ?agent .
  OPTIONAL { ?agent <http://www.w3.org/ns/prov#softwareVersion> ?version }
}
"""


def what_produced(graph, output_uri):
    """Backward: the activity, its inputs, its agent and when it ran."""
    return [dict(row.asdict()) for row in graph.query(
        BACKWARD, initBindings={"output": URIRef(output_uri)})]


def what_used(graph, source_uri):
    """Forward, one hop: the direct consumers of a source."""
    return [dict(row.asdict()) for row in graph.query(
        FORWARD, initBindings={"source": URIRef(source_uri)})]


def what_is_affected(graph, source_uri, depth=6):
    """Forward, transitive, bounded. Report the bound with the result."""
    query = AFFECTED % {"depth": depth}
    rows = [str(row.affected) for row in graph.query(
        query, initBindings={"source": URIRef(source_uri)})]
    return {"affected": sorted(rows), "depth_searched": depth,
            "may_be_incomplete": len(rows) > 0 and depth < 12}

Three choices here are what separate a query set that gets used from one that gets abandoned.

Every transitive query is depth-bounded and says so. An unbounded property path over a graph that grows with every pipeline run is the single most reliable way to make a provenance store feel unusable. Bounding it makes the query fast and the result honest, provided the bound is reported alongside the answer.

OPTIONAL is used deliberately, not defensively. Wrapping every clause in OPTIONAL produces a query that always returns rows and never tells you anything is missing. The clauses that are genuinely optional — a label, an agent version — are marked; the ones that must be present are not, so a missing wasGeneratedBy shows up as an empty result rather than a row full of nulls.

Bindings are passed as parameters. Interpolating a URI into a query string is both a correctness problem, when the URI contains characters the parser treats specially, and a caching one, since every call produces a distinct query text.

How a backward query walks the graphFrom an output entity to the activity that generated it, then to the inputs that activity used and the agent it was associated with.Output entitythe thing being asked aboutwasGeneratedByActivitywith parameters and timeusedInput entitiescontent-addressedrepeatTheir activitiesbounded by depth
Two hops answer the common question; the third is only needed when the chain has to be followed further back.

Validation and Pipeline Integration

def test_backward_query_returns_the_generating_activity():
    graph = load_fixture("clip_run.ttl")
    rows = what_produced(graph, "urn:entity:clipped-roads")
    assert rows and any(row["activity"] for row in rows)


def test_missing_generation_edge_yields_no_rows():
    """An orphan output must not return a row full of nulls."""
    graph = load_fixture("orphan_output.ttl")
    assert what_produced(graph, "urn:entity:orphan") == []


def test_transitive_query_reports_its_bound():
    graph = load_fixture("deep_chain.ttl")
    result = what_is_affected(graph, "urn:entity:source", depth=3)
    assert result["depth_searched"] == 3

The second test encodes the property that makes the query set trustworthy. A graph with a missing derivation edge should produce an empty result, which is a visible finding, rather than a partially populated row that reads like a partial answer.

Expose these four queries as named functions rather than letting callers write SPARQL. The queries are the interface; ad-hoc SPARQL written by each consumer produces a set of subtly different questions whose answers cannot be compared, and it makes any future change to the graph shape a breaking change for everybody at once.

Which query answers the question being askedWhether a provenance question is backward, forward, transitive or accountability.Does the question start from anoutput?Backward querybounded, cheapyesnoDoes it need only directconsumers?Forward, one hopno property pathyesnoDoes it need everythingdownstream?Transitive, boundedreport the depthyesnoAccountability querya single hop to the agent
Establishing the direction first avoids the expensive query being run for a cheap question.

Keeping Queries Fast as the Graph Grows

A provenance graph accumulates monotonically — every pipeline run adds nodes and nothing is ever deleted — so a query set that performs well in the first month will not in the second year unless three things are true.

The store indexes what the queries traverse. Most triple stores index by subject and by predicate-object, and backward queries starting from a known output use both well. Forward transitive queries do not, and they are the ones that degrade. Where forward queries matter, materialising a derived-from closure table alongside the graph is a pragmatic answer: it duplicates information the graph already holds and turns a property path into a lookup.

Old provenance is partitioned rather than pruned. Deleting old lineage defeats the purpose, but a graph split by year — with queries defaulting to the current partition and reaching further only when asked — keeps the working set small. This matters more than it sounds: most questions are about recent outputs.

Representation events stay out. The single largest contributor to graph size is recording steps that change form rather than content, as discussed in spatial data lineage and provenance tracking. A graph carrying every format conversion and file copy is several times larger than one carrying only meaning-changing operations, and no query benefits from the difference.

The measure to watch is not graph size but the ninety-fifth percentile latency of the backward query. It is the one users notice, and when it starts to move the cause is almost always a forward query somewhere sharing the same store.

Long-Term Compliance Best Practices

  • Bound every property path and report the bound. An incomplete answer that says so is useful; one that does not is misleading.
  • Expose named queries, not raw SPARQL. Consumers writing their own produce incomparable answers and pin the graph shape.
  • Return an empty result for a missing edge. A partially populated row hides the gap the query should reveal.
  • Pass URIs as bindings. Interpolation breaks on unusual URIs and defeats query caching.
  • Watch the backward query’s latency, not the graph’s size. It is the number that reflects what users experience.