prov-lineage · git:20260716.0e3f1b5 · 2026-07-16 · sha256 1c8fc5c93c43e70b
prov-lineage git:20260716.0e3f1b5A
Immutable. This exact content is served forever at /api/v1/blob/1c8fc5c93c43e70b.
---
name: prov-lineage
description: "Capture W3C PROV-O data lineage for DERIVED RDF, or explain a missing BGP target binding: record CONSTRUCT/DESCRIBE, SPARQL UPDATE, and reasoner-materialization lineage; under the opt-in `why-not` feature, report exactly which grounded BGP triple patterns are absent. Off by default; does not touch sparq-core/sparq-engine's lean build."
---
# sparq-prov — W3C PROV-O lineage for derived data
[W3C PROV-O](https://www.w3.org/TR/prov-o/) is the standard RDF vocabulary for
provenance: a `prov:Entity` was generated by a `prov:Activity` that `prov:used`
some inputs, so the entity `prov:wasDerivedFrom` them. `sparq-prov` records that
lineage for data sparq **derives** — today, the result of a `CONSTRUCT`/`DESCRIBE`
query (a new RDF graph produced from the queried data).
`sparq-prov` is the **opt-in public surface** for this. Add it explicitly; it is
**not** in sparq's default build (`sparq-core`/`sparq-engine` stay lean, the wasm
artifact is unchanged unless you pull it in). The capability is therefore **off by
default at the dependency level** — the leanest gating, with zero core overhead.
## Add the dependency
```toml
[dependencies]
sparq-prov = { path = "crates/sparq-prov" } # or your workspace path
oxrdf = { version = "0.3", features = ["rdf-12"] }
```
## Derive a graph + capture its lineage
`derive_construct` runs the query, times it, and returns a `Derivation` holding
both the derived triples and a PROV-O lineage graph. Name the input source(s) so
`prov:used` / `prov:wasDerivedFrom` are recorded.
```rust
use sparq_core::Graph;
use sparq_prov::{derive_construct, ProvConfig};
use oxrdf::NamedNode;
let g = Graph::load_str("@prefix ex: <http://ex/> . ex:alice ex:age 30 .", "turtle").unwrap();
let config = ProvConfig::with_inputs([NamedNode::new_unchecked("http://ex/src")]);
let d = derive_construct(
&g,
"PREFIX ex: <http://ex/> CONSTRUCT { ?s ex:years ?a } WHERE { ?s ex:age ?a }",
config,
).unwrap();
let derived = d.triples(); // the derived data (Vec<Triple>)
let inputs = d.used_inputs(); // configured input IRIs, in order (&[NamedNode])
let lineage = d.prov_graph(); // its PROV-O record (Vec<Triple>)
let turtle = d.prov_turtle(); // …prefix-compacted Turtle
let nt = d.prov_ntriples(); // …or canonical N-Triples
```
## The emitted PROV-O shape
For result entity `E`, activity `A`, inputs `Iᵢ`:
```turtle
A a prov:Activity .
A prov:startedAtTime "…Z"^^xsd:dateTime .
A prov:endedAtTime "…Z"^^xsd:dateTime .
A rdfs:label "CONSTRUCT" .
A prov:value "<the SPARQL text>" .
A prov:used Iᵢ . # one per input
E a prov:Entity .
E prov:wasGeneratedBy A .
E prov:wasDerivedFrom Iᵢ . # one per input
A prov:wasAssociatedWith <agent> . # if ProvConfig.agent is set
```
All IRIs are absolute, so the output is valid PROV-O that round-trips through any
RDF parser (tested against both `Graph::load_str` and `oxttl::NTriplesParser`).
## Capture lineage for a SPARQL UPDATE
A SPARQL UPDATE mutates a store. `derive_update` applies it **in place** and reads the
engine's *resolved* effect log, so the lineage reflects the triples actually committed
(exact even for non-deterministic update text — `NOW()`/`RAND()`/`UUID()`/fresh
`BNODE()`). The PROV reading is two-sided: **inserts** are *generated/derived*, **deletes**
are *invalidated*.
```rust
use sparq_core::Graph;
use sparq_prov::{derive_update, ProvConfig};
use oxrdf::NamedNode;
let mut g = Graph::load_str("@prefix ex: <http://ex/> . ex:a ex:age 30 .", "turtle").unwrap();
let cfg = ProvConfig::with_inputs([NamedNode::new_unchecked("http://ex/src")]);
let d = derive_update(
&mut g,
"PREFIX ex: <http://ex/> \
DELETE { ?s ex:age ?a } INSERT { ?s ex:years ?a } WHERE { ?s ex:age ?a }",
cfg,
).unwrap();
let inserted = d.inserted(); // the generated (derived) triples
let deleted = d.deleted(); // the retracted (invalidated) triples
let inputs = d.used_inputs(); // configured input IRIs, in order
let lineage = d.prov_graph(); // its PROV-O record (Vec<Triple>)
let turtle = d.prov_turtle(); // prefix-compacted Turtle for that same graph
```
Emitted shape — for update activity `A`, generated entity `E` (the inserts), inputs `Iᵢ`:
```turtle
A a prov:Activity .
A rdfs:label "DELETE/INSERT WHERE" . # / "INSERT DATA" / "LOAD" / "SPARQL UPDATE"
A prov:value "<the SPARQL text>" .
A prov:startedAtTime "…Z"^^xsd:dateTime .
A prov:endedAtTime "…Z"^^xsd:dateTime .
A prov:used Iᵢ . # one per input
E a prov:Entity . # only if the update INSERTED
E prov:wasGeneratedBy A . # "
E prov:wasDerivedFrom Iᵢ . # " (one per input)
_:d a prov:Entity ; # one fresh blank node per DELETED triple
prov:wasInvalidatedBy A .
```
Honesty boundaries:
- **Deletes are invalidations, not derivations** — a deleted triple is never
`wasGeneratedBy`/`wasDerivedFrom`. A pure-delete update generates **no** result entity.
- **Ground DATA ops record the declared operand batch, not a store-diff** — `INSERT DATA`
lineage attributes the operand triples as generated even if they were already asserted,
and `DELETE DATA` records the operand triples as invalidated even if absent. The
operation *declares* that data added / removed; the resolved effect log carries the
operand. (`DELETE … WHERE` that matches nothing is, by contrast, a true no-op — no
delta, no invalidation entity.)
- **Structural ops** (`CLEAR` / `DROP` / `CREATE`) change a graph's existence/emptiness,
not its triples-as-data — they are reflected only in the activity kind label, with **no**
per-triple entity (no sound per-triple derivation to assert).
## Identity & determinism
- IRIs default to stable, content-addressed `urn:sparq:prov:{role}:…` nodes — the
**same derivation mints the same activity/entity IRIs** across runs (no global
counter). Set `ProvConfig.activity` / `.entity` to integrate with an external
provenance store or a named-graph scheme.
- `ProvConfig.clock` is injectable (`fn() -> SystemTime`), so timing — and thus
the minted IRIs — are deterministic in tests. Defaults to `SystemTime::now`.
- `ProvConfig.used` lists the input-source IRIs (typically the dataset / named
graph the CONSTRUCT ran against); `ProvConfig.agent` names the running service.
## Reasoner-materialization lineage (`reason` feature)
Inference *is* derivation: when a reasoner materializes a triple, that triple is
`wasDerivedFrom` the premises the rule fired on. The `reason` feature turns a
`sparq-reason` `why()` proof tree (the `explain` feature there) straight into
PROV-O — a *finer-grained* provenance than a single CONSTRUCT activity, because
it names the rule and exact premises for **each** inferred fact.
```toml
[dependencies]
sparq-prov = { path = "crates/sparq-prov", features = ["reason"] }
sparq-reason = { path = "crates/sparq-reason", features = ["explain"] }
```
```rust
use sparq_prov::{prov_from_proof, prov_ntriples, ProvProofConfig};
// g: a sparq_reason::MaterializedGraph / MaterializedOwlGraph / MaterializedN3Graph.
let proof = g.why(&dict, inferred_fact).expect("fact is in the closure");
let lineage = prov_from_proof(&proof, &ProvProofConfig::default()); // Vec<Triple>
let ntriples = prov_ntriples(&proof, &ProvProofConfig::default()); // String
```
`prov_ntriples` is the one-call serializer for the same ordered lineage triples.
With the default clock-free configuration, both the triples and their
content-addressed IRIs are deterministic. <!-- [GPT-5.6] sq-8jn86 -->
Emitted shape — for each proof node (fact) `F` and the rule firing `R` that
generated a non-leaf `F` from premises `Pᵢ`:
```turtle
F a prov:Entity .
R a prov:Activity .
R rdfs:label "cax-sco" . # rdfs9 / prp-trp / n3-rule-0 / …
F prov:wasGeneratedBy R .
R prov:used Pᵢ . # one per premise
F prov:wasDerivedFrom Pᵢ .
R prov:generatedAtTime "…Z"^^xsd:dateTime . # iff ProvProofConfig.clock is set
R prov:wasAssociatedWith <agent> . # iff ProvProofConfig.agent is set
```
Asserted leaves and `axiom-*` tautologies are entities with **no** generating
activity — they are the boundary the derivation rests on. Entity/activity IRIs
are content-addressed (`urn:sparq:prov:fact:…` / `:rule:…`) from the proof's
canonical term strings, so lineage from overlapping proofs **stitches** into one
DAG (the same shared fact names the same entity).
## Scope — covered vs deferred
| Derivation path | Status |
|---|---|
| `CONSTRUCT` / `DESCRIBE` | ✅ covered (`derive_construct`) |
| Reasoner materialization (RDFS / OWL-RL / N3) | ✅ covered (`reason` feature → `prov_from_proof` / `prov_ntriples`) |
| SPARQL UPDATE data ops (`INSERT … WHERE`, `INSERT DATA`, `DELETE …`, `LOAD`) | ✅ covered (`derive_update`) — inserts ⇒ generated/derived, deletes ⇒ `wasInvalidatedBy` |
| SPARQL UPDATE structural ops (`CLEAR` / `DROP` / `CREATE`) | ⛔ no per-triple entity (deliberate boundary — recorded only as the activity kind) |
For the reasoner's per-fact proof itself (the input to `prov_from_proof`), see the
[`inference`](../inference/SKILL.md) skill's `explain` feature (`why()` produces
a proof tree — derivation provenance at the rule/premise level).
## Missing-answer explanation (`why-not` feature)
<!-- [GPT-5.6] sq-lsp7k.17 -->
The non-default `why-not` feature handles one bounded case: a fully-ground target
binding that did not appear in the answers to a single basic graph pattern (BGP).
`why_not(&Graph, &GraphPattern, &HashMap<Variable, Term>)` substitutes the target
through each BGP triple pattern and returns a `Vec<MissingPattern>` containing
exactly the absent concrete triples, in BGP order. If every triple is present,
the vector is empty because that target would satisfy the BGP.
```toml
[dependencies]
sparq-prov = { path = "crates/sparq-prov", features = ["why-not"] }
spargebra = { version = "0.4", features = ["sparql-12", "sep-0006"] }
```
The accepted algebra node is exactly `GraphPattern::Bgp`. `OPTIONAL`, `UNION`,
`FILTER`, property paths, named graphs, and every other algebra variant return
`WhyNotError::UnsupportedAlgebra`. A target missing a referenced variable, a
literal bound in subject position, or a non-IRI predicate binding also returns
an error. The explainer never treats an invalid substitution as evidence of an
absent RDF triple.
```rust
use std::collections::HashMap;
use oxrdf::{NamedNode, Term, Variable};
use spargebra::algebra::GraphPattern;
use spargebra::term::{NamedNodePattern, TermPattern, TriplePattern};
use sparq_core::Graph;
use sparq_prov::{why_not, why_not_report_ntriples, why_not_report_turtle};
let ex = |local: &str| NamedNode::new_unchecked(format!("http://example.com/{local}"));
let var = |name: &str| Variable::new_unchecked(name);
let triple_pattern = |predicate: &str, object_variable: &str| TriplePattern {
subject: TermPattern::Variable(var("x")),
predicate: NamedNodePattern::NamedNode(ex(predicate)),
object: TermPattern::Variable(var(object_variable)),
};
let graph = Graph::load_str("@prefix : <http://example.com/> . :a :p :b .", "turtle")?;
let bgp = GraphPattern::Bgp {
patterns: vec![triple_pattern("p", "y"), triple_pattern("q", "z")],
};
let target = HashMap::from([
(var("x"), Term::NamedNode(ex("a"))),
(var("y"), Term::NamedNode(ex("b"))),
(var("z"), Term::NamedNode(ex("c"))),
]);
let missing = why_not(&graph, &bgp, &target)?;
assert_eq!(missing.len(), 1);
assert_eq!(missing[0].grounded().predicate, ex("q"));
let ntriples = why_not_report_ntriples(&target, &missing)?;
let turtle = why_not_report_turtle(&target, &missing)?;
assert!(ntriples.contains("urn:sparq:prov:absent"));
assert!(turtle.contains("spqprov:absent"));
# Ok::<(), Box<dyn std::error::Error>>(())
```
<!-- [GPT-5.6] sq-lsp7k -->
Both report functions validate that `target` still grounds every retained
pattern to its recorded `MissingPattern::grounded()` triple; a different or
incomplete target fails closed. The emitted graph has one deterministic report
node per missing conjunct, in BGP order:
```turtle
<urn:sparq:prov:missing:0:…> a prov:Entity ;
rdf:reifies <<( <http://example.com/a> <http://example.com/q> <http://example.com/c> )>> ;
spqprov:absent true ;
spqprov:position 0 ;
spqprov:targetBinding "?x=<http://example.com/a>; …" .
```
`rdf:reifies` carries an RDF 1.2 triple term: the missing triple is quoted exactly and
is not asserted into the report graph. N-Triples and Turtle serialize the same
five metadata triples per missing conjunct with stable bytes/triple order.
## See also
- W3C PROV-O: <https://www.w3.org/TR/prov-o/>
- CDMC CD-1 (first-class data lineage): `compliance/cdmc/gap-register.md`
- Hartig provenance research §6: `research/feature-research-hartig.md`
- Crate README: `crates/sparq-prov/README.md`