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

[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.

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ᵢ:

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.

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ᵢ:

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.

[dependencies]
sparq-prov   = { path = "crates/sparq-prov", features = ["reason"] }
sparq-reason = { path = "crates/sparq-reason", features = ["explain"] }

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.

Emitted shape — for each proof node (fact) F and the rule firing R that generated a non-leaf F from premises Pᵢ:

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 skill's explain feature (why() produces a proof tree — derivation provenance at the rule/premise level).

Missing-answer explanation (why-not feature)

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.

[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.

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>>(())

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:

<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