Prov Lineage

---
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`