Back to Articles|Published on October 27, 2026|30 min read

Reliable Context Article

Query Provenance: Which Source Rows Justify a Derived Value?

A 2026 worked test of query provenance: witness sets for a join, projection and SUM, where, why and how provenance, PROV-O mapping, and an acceptance protocol for derived values.

By Reliable Context Research

Query Provenance: Which Source Rows Justify a Derived Value?

Summary

  1. 01A dataset-level lineage arrow cannot justify a displayed value. Reviewers need the source rows, relevant cells and transformation that produced it.
  2. 02Why-provenance explains which rows witness an output, where-provenance identifies copy locations, and how-provenance records how inputs combine.
  3. 03EMEA has two alternative witnesses for its existence, but its SUM of 200 needs both pairs together. Tuple-only annotation does not explain the number.
  4. 04Removal and cell perturbation tests check the witnesses against a frozen query and snapshot. Source quotations and observation dates support review of the inputs themselves.
  5. 05PROV-O preserves the run record but does not compute witnesses. Query provenance exposes source conflicts without resolving them and proves dependence rather than accuracy.
Inside this article
  1. 01Executive Summary
  2. 02Introduction and Background
  3. 03Key Distinctions in Query Provenance
  4. 04The Reference Asset: A Toy Join, Projection and SUM
  5. 05Aggregates: Why Tuple-Only Annotation Does Not Explain the Number
  6. 06Mapping the Example to PROV-O
  7. 07Implementation Considerations and Process Changes
  8. 08Limits: Unsupported Operators, Redactions and Unresolved Source Conflicts
  9. 09Data Analysis and Evidence
  10. 10Implications and Future Directions
  11. 11Frequently Asked Questions (FAQs)
  12. 12Conclusion

Executive Summary

A derived value in a canonical record is defensible only if a reviewer can name the input rows, and ideally the input cells, that produced it. A dataset-level lineage arrow does not meet that bar. Data lineage tools describe how data flows through systems [1], and the OpenLineage specification models Jobs, Runs and Datasets rather than rows [2]. Row-level query provenance answers a different question: which source tuples witnessed an output tuple [3]. This report turns that distinction into a black-box acceptance test that a context engineer can run without access to any vendor internals.

The vocabulary comes from the database literature. Why-provenance identifies the source data that influenced the existence of an output [4]. Where-provenance identifies the location a value was copied from [3]. How-provenance describes how the source tuples witness the output tuple [3]. Green, Karvounarakis and Tannen (2007) unified these for positive relational algebra using commutative semirings [5], and, in the same paper, extended the approach toward recursive Datalog [5]. For aggregates, Amsterdamer, Deutch and Tannen (2011) showed that tuple-only annotation is inapplicable and that individual values inside tuples must carry provenance too [6].

The reusable asset is a fully specified toy example: four private order rows joined to four public registry rows, with a DISTINCT projection, a row-level projection and a SUM. The EMEA region has two alternative witnesses, {o1, r1} and {o2, r2}; the EMEA total of 200 needs both (120 + 80). A decoy order worth 999 (79.98% of the 1,249 total order amount) has no join partner and contributes nothing, yet a dataset-level arrow would include it. The witness sets were derived by hand, by SQLite, by an independent Python evaluator and by exhaustive enumeration of all 255 non-empty input subsets; all four agree. To reproduce the enumeration, rerun the query on each of the 255 non-empty subsets of the eight input rows and compare each result with the full-input result. The evaluator code itself is not published here.

Standards help with record-keeping but do not compute witnesses. W3C PROV-O, a Recommendation dated 30 April 2013 [7], defines Entity, Activity, usage and derivation, but the data model states that PROV does not specify the conditions under which derivations exist [8]. Tool support is bounded: ProvSQL, the PostgreSQL extension, labels where-provenance an experimental feature [9] and states that an aggregate value has no source location because it is computed rather than copied [9]. The acceptance test therefore combines removal, perturbation, a three-way evidence check (where, why, how) and a preserved run record, and it names unsupported operators, redactions and unresolved source conflicts as explicit limits.

200EMEA total requiring both contributing order-registry pairs
50%Share of input rows on which the EMEA SUM cell depends
79.98%Share of total order amount held by the decoy order, which contributes nothing
255Non-empty input subsets exhaustively checked for the toy example

Introduction and Background

Context engineers who maintain canonical records face a recurring acceptance decision: a field displays a number or label that was calculated from several inputs, some private and some public, and a reviewer asks what justifies it. The usual answer is a citation to a dataset or a pipeline step. That answer is a lineage arrow. It states that table A and table B fed table C. It does not state which rows of A and B the displayed cell depends on, and it cannot distinguish a row that mattered from a row that sat in the same table.

The terminology is contested in practice. One vendor explainer published in June 2026 defines data lineage as tracking how data flows through systems [1] and data provenance as the historical record of data [1], and frames the two as differing in purpose, one operational and the other about governance [1]. The glossary of the National Network of Libraries of Medicine notes that data provenance is sometimes called data lineage [10]. The research literature draws sharper lines. Cui and Widom's lineage definition identified the exact set of base data items that produced a view data item [11], while Cheney, Chiticariu and Tan (2009) showed that a lineage set is not as precise as one may like [3]. Query provenance is the family of techniques that resolve this ambiguity at the level of individual input tuples and cells.

This report treats the problem as one of evidence rather than tooling: given a displayed value, a query and a source snapshot, what must be shown for the value to count as justified? The method is black-box. It requires only the ability to run the query on modified copies of the inputs and to inspect the query text.

Disclosure: the publisher, Reliable Context, builds a system of record, a tool that works at the level of individual values. It is complementary to query-level witness analysis, and this report does not claim that a system of record computes SQL witness sets. The test below is how a reader can check any system, including that one, against the input-level standard.

Scope and sources. The formal claims rest on primary papers, the W3C PROV family and tool documentation retrieved in October 2026. Search-volume figures for the topic are advertising estimates and are not used as evidence. All worked numbers were recomputed locally.

Key Distinctions in Query Provenance

Defining the objects: output value, source cell, contributing row, witness set, transformation

Five terms recur in the acceptance test, and each is used here in a fixed sense.

  • Output value: one cell of a query result, addressed by result row and column, for example the SUM cell of the EMEA row.
  • Source cell: one cell of one input row, addressed by relation, row identifier and column, for example orders.amount of row o1.
  • Contributing row: an input row that appears in at least one witness of the output.
  • Witness set: a subset of the input records sufficient for an output record to appear [3]. A minimal witness has no removable member. One output can have several alternative witnesses [3].
  • Transformation: the query text and version that maps inputs to the output, because provenance is sensitive to how the query is written. Where-provenance in particular is not invariant under equivalent queries [3].

Where-provenance versus why-provenance

Buneman, Khanna and Tan (2001) distinguished two questions. Why-provenance concerns the source data that had some influence on the existence of the data [4]. Where-provenance concerns where a piece of data is copied from [3]. The survey by Cheney and colleagues adds the unit of analysis: why-provenance relates source and output tuples, whereas where-provenance relates source and output locations, meaning cells [3]. In the toy example below, the label EMEA in the output has two candidate copy locations (the region cells of r1 and r2), while the existence of that output row is explained by two alternative witnesses.

Müller and colleagues (2018) generalise where-provenance for SQL: it includes cells copied verbatim but also cells used to compute a value [12]. A reviewer who asks for "the source cells" of a computed number is therefore asking for more than a copy pointer.

How-provenance and provenance semirings explained

Why-provenance reports which tuples contribute but not how. Green, Karvounarakis and Tannen observed that one needs to know not just which input tuples contribute but also how they contribute [5], and said the resulting annotation could justifiably be called how-provenance [5]. Their construction annotates each tuple with an element of a commutative semiring and defines a generalised positive algebra on those annotated relations [5]. The rules are compact: for projection and union the annotations of the same tuple are added, and for join they are multiplied [5]. The most general annotation is a polynomial with integer coefficients over input tuple identifiers [5], and any other annotation semantics follows from it through a semiring homomorphism [5]. The lineage of a tuple is the set of all contributing input tuples [5], which is why lineage is strictly less informative than the polynomial: Cheney and colleagues note that why-provenance cannot show that one source tuple contributes twice, while the polynomial can [3], and that one can derive the why-provenance of an output tuple from the polynomial [3].

For the toy example the polynomial of the EMEA row is o1·r1 + o2·r2. Addition marks alternative derivations; multiplication marks inputs that must co-occur. The set of minimal witnesses is read off the monomials: {o1, r1} and {o2, r2}.

Row-level and cell-level granularity

Herschel, Diestelkaemper and Ben Lahmar (2017) place data provenance at the finest level of a type hierarchy, one that can track the processing of individual data items [13], and describe a spectrum whose two ends are coarse-grained and fine-grained provenance [13]. Row granularity is what the majority of existing work provides [12]. The acceptance test uses rows first and cells second.

Data lineage versus data provenance, restated for acceptance

The practical difference is the unit of evidence. Lineage systems document datasets, jobs and, increasingly, columns. OpenLineage describes itself as an open framework for data lineage collection and analysis [14] and defines a Dataset as an abstract representation of data [2]. Its column-level facet gives fine grained information on datasets' dependencies [15], but it operates on columns, not on the rows that held the values on a particular run. A catalog-level fact such as "column region depends on column registry.region" is true of every output row, including rows with no support. The remainder of this report shows why that is insufficient for a single displayed cell.

The Reference Asset: A Toy Join, Projection and SUM

Inputs and queries

The relations below are fully specified. Each row carries an identifier (o1 to o4, r1 to r4) so that witness sets can be written down. The orders relation stands in for a private source and the registry relation for a public one; the logic does not depend on that split.

CREATE TABLE orders  (rid TEXT, order_id INT, org_id TEXT, amount INT);
INSERT INTO orders  VALUES ('o1',1,'A',120), ('o2',2,'B',80),
                           ('o3',3,'C',50),  ('o4',4,'Z',999);
CREATE TABLE registry (rid TEXT, org_id TEXT, name TEXT, region TEXT);
INSERT INTO registry VALUES ('r1','A','Acme','EMEA'), ('r2','B','Bolt','EMEA'),
                            ('r3','C','Cirrus','APAC'), ('r4','D','Delta','EMEA');

Q1: SELECT DISTINCT r.region
    FROM orders o JOIN registry r ON o.org_id = r.org_id;
Q2: SELECT r.region, SUM(o.amount)
    FROM orders o JOIN registry r ON o.org_id = r.org_id GROUP BY r.region;
Q3: SELECT r.name, r.region
    FROM orders o JOIN registry r ON o.org_id = r.org_id;

The join keeps three order-registry pairs: (o1, r1), (o2, r2) and (o3, r3). Order o4 carries org_id Z, which has no registry row, and registry row r4 (org D) has no order. Inner join semantics mean that the joined table has a row for each pair satisfying the condition [16], so o4 and r4 never enter the join result. The outputs are Q1 = {APAC, EMEA}; Q2 = {(APAC, 50), (EMEA, 200)}; Q3 = {(Acme, EMEA), (Bolt, EMEA), (Cirrus, APAC)}.

The witness matrix

Table 1 below lists, for each output, the minimal witnesses, the how-polynomial, and the source cells at three roles: value cells (their numbers enter the output), key cells (join and group conditions that were inspected) and label cells (the origin of copied text). The sets were derived by hand from the join pairs and then checked by exhaustive enumeration of all 255 non-empty subsets of the eight input rows.

OutputMinimal witnesses (why)How-polynomialSource cells
Q1 (EMEA){o1, r1}, {o2, r2}o1·r1 + o2·r2Label: registry.region of r1 and r2 (two candidate copy locations). Key: org_id of o1, r1, o2, r2.
Q1 (APAC){o3, r3}o3·r3Label: registry.region of r3. Key: org_id of o3, r3.
Q2 (EMEA, 200)Both rows of each witness are needed together: {o1, r1, o2, r2}(o1·r1)⊗120 + (o2·r2)⊗80Value: orders.amount of o1 (120) and o2 (80). Key: org_id of o1, r1, o2, r2. Group label: registry.region of r1, r2.
Q2 (APAC, 50){o3, r3}(o3·r3)⊗50Value: orders.amount of o3 (50). Key: org_id of o3, r3. Group label: registry.region of r3.
Q3 (Acme, EMEA){o1, r1}o1·r1Label: registry.name and registry.region of r1. Key: org_id of o1, r1.
Q3 (Bolt, EMEA){o2, r2}o2·r2Label: registry.name and registry.region of r2. Key: org_id of o2, r2.
Q3 (Cirrus, APAC){o3, r3}o3·r3Label: registry.name and registry.region of r3. Key: org_id of o3, r3.

Three features stand out. First, the DISTINCT projection in Q1 is where two witnesses compete: either {o1, r1} or {o2, r2} makes EMEA appear. Second, in Q2 the same pairs are not alternatives for the number: the SUM cell depends on both together. Third, the cells that matter inside a contributing row are a minority. The Acme row r1 contributes its org_id and region to the SUM, but its name cell is irrelevant to Q2 and relevant to Q3. Row-level witnesses therefore over-approximate cell-level ones, which is the reason the acceptance test treats cells as a second pass.

The perturbation results

Table 2 below records what happens when inputs are removed or changed. Each row was computed in SQLite and recomputed with a separate Python evaluator that implements the join and grouping directly; the two agreed on every row.

Perturbation of the inputsQ1 resultQ2 resultReading
None (baseline)APAC, EMEAAPAC 50, EMEA 200Reference.
Delete o1APAC, EMEAAPAC 50, EMEA 80EMEA survives in Q1 through {o2, r2}. The SUM drops by 120.
Delete o2APAC, EMEAAPAC 50, EMEA 120The SUM drops by 80.
Delete r1APAC, EMEAAPAC 50, EMEA 80The registry row is as necessary to the SUM as the order row.
Delete o1 and o2 (one member of each witness)APACAPAC 50EMEA disappears: the deleted set hits every witness.
Delete o1 and r2APACAPAC 50Same.
Delete o4 or r4APAC, EMEAAPAC 50, EMEA 200No change: neither row is in any witness.
Set o1.amount from 120 to 130APAC, EMEAAPAC 50, EMEA 210The value cell passes through with weight 1.
Set o4.amount from 999 to 1APAC, EMEAAPAC 50, EMEA 200No change: an unwitnessed cell cannot move the output.
Set r1.region from EMEA to APACAPAC, EMEAAPAC 170, EMEA 80The group label cell controls which group receives 120.
Set o1.org_id from A to ZAPAC, EMEAAPAC 50, EMEA 80The join-key cell is inspected: breaking it removes the pair.
Set r1.name from Acme to Acme2APAC, EMEAAPAC 50, EMEA 200Q3 changes to (Acme2, EMEA); Q2 does not.

Two lessons follow. A single-row removal test cannot certify a contributing row when an alternative witness exists; it must be applied to sets that hit every minimal witness. And a perturbation test certifies a cell only for the change tested, which is why the protocol pairs it with a structural witness.

A dataset-level lineage arrow documents that data moved; it does not show that a displayed cell is supported.

Aggregates: Why Tuple-Only Annotation Does Not Explain the Number

Figure 01
EMEA existence versus the EMEA total
Why EMEA appearsDISTINCT projection
  • Either {o1, r1} or {o2, r2} makes EMEA appear.
  • No single deletion removes EMEA; two deletions, one per witness, remove it.
What produces the totalSUM
  • Both order-registry pairs are needed together for the total of 200.
  • Deleting o1 changes the total from 200 to 80; the tuple polynomial cannot predict that.

The semiring polynomial is the same for both EMEA rows. The computed number also needs the numerical contributions.

The semiring polynomial of the EMEA row in Q2 is the same as that of EMEA in Q1: o1·r1 + o2·r2. Read alone, it says that EMEA exists if either pair exists. That is true of the group, but it is silent on the number. Deleting o1 changes the total from 200 to 80, and the polynomial gives no way to predict that.

Amsterdamer, Deutch and Tannen (2011) address this gap. They state that aggregate queries pose novel challenges, rendering the semiring approach inapplicable [6], and propose annotating not just tuples but also the individual values within tuples [6]. Their device is the tensor product [17]. For the toy SUM, the EMEA cell is the formal expression (o1·r1)⊗120 + (o2·r2)⊗80, which is the form shown in Table 1. Setting the token o1 to zero removes the first term and leaves 80, which matches the deletion row in Table 2. The authors relate this algebraic treatment of deletions to the counting algorithm for view maintenance [17].

Two limits from the same paper bear on acceptance:

  • Size. The construction keeps the representation size polynomial in the size of the input database [17], and the authors argue that tuple-level annotation alone cannot represent aggregation with a feasible amount of annotation.
  • Negation. Relational difference is encoded through nested aggregation, and the authors caution that the resulting semantics is probably not the last word on difference of annotated relations [17].

PostgreSQL's documentation adds a practical detail for any audit of a SUM: it computes the sum of the non-null input values [18], and the sum of no rows returns null, not zero [18]. A NULL amount therefore contributes no numerical weight yet can still be a witnessed row, and a group with no contributing rows yields NULL rather than 0. A reviewer should confirm which of those two cases a displayed zero or blank represents.

How tools handle this varies. Perm, an early SQL rewriting system, defines the provenance of a query computing the sum of an attribute for all tuples of an input relation as every input tuple [19], and rewrites aggregation by joining its results with the rewritten input [19]. ProvSQL, by contrast, documents that aggregation is treated as a scalar multiplication of provenance values [20], in line with the semimodule construction.

Mapping the Example to PROV-O

W3C PROV-O is a Recommendation dated 30 April 2013 [7]. It is a vocabulary for recording the history of a record, and an OWL2 ontology that maps the PROV data model to RDF [21]. For the toy example, four of its terms carry the weight.

  • Entity: a physical, digital, conceptual, or other kind of thing [7]. Each input row, each result cell and the source snapshot can be entities.
  • Activity: something that occurs over a period of time [7]. The execution of Q2 against a snapshot is an activity.
  • used: usage is the beginning of utilizing an entity by an activity [7]. The query run used the snapshot and the rows read.
  • wasDerivedFrom: a derivation is a transformation of an entity into another [7]. The EMEA total derives from o1 and o2, with the join keys and group label cells recorded as additional inputs where the reviewer needs them.

A responsible agent is also recordable. An agent is something that bears some form of responsibility [7], and an activity association is an assignment of responsibility to an agent for an activity [7]. Generation, the completion of production of a new entity by an activity [7], links the result to the run. A minimal Turtle sketch of the Q2 EMEA cell follows.

ex:emea_total  a prov:Entity ;
    prov:wasGeneratedBy ex:run_q2_2026_10_20 ;
    prov:wasDerivedFrom ex:o1, ex:o2, ex:r1, ex:r2 .
ex:run_q2_2026_10_20  a prov:Activity ;
    prov:used ex:orders_snapshot, ex:registry_snapshot ;
    prov:wasAssociatedWith ex:analyst_agent .

What PROV-O does not do is equally important. The data model defines provenance as information about entities, activities and people involved in producing a piece of data [8], that can be used to form assessments about its quality, reliability or trustworthiness [8]. It records; it does not rule on truth. It also does not compute the derivation edges: PROV does not attempt to specify the conditions under which derivations exist [8], so a derivation is considered to have been determined by unspecified means [8]. Whether ex:o4 is absent from the derivation list is a fact about the query, to be established by a witness computation or the perturbation tests, not by the vocabulary. A cloud-database article mentions PROV-O only in a bullet about a separate metadata dataset describing such things as where the data came from, who created it, or when it was created [22], which is the coarse end of the spectrum.

Implementation Considerations and Process Changes

The acceptance protocol

The protocol below accepts or rejects one displayed derived value. Its output is the audit trail for a derived data value: a record that another reviewer can replay. It needs the query text, a frozen copy of the inputs and the ability to run the query again.

  • Step 1, freeze. Preserve the query text and version, the source snapshot identifiers, the execution time and the responsible agent. These four items are what PROV-O's activity, used and association terms exist to hold.
  • Step 2, enumerate candidates. List the input rows that the join and filter conditions admit. For the toy query this is three of four orders and three of four registry rows.
  • Step 3, state witnesses. For each output, write the minimal witness sets. Two outputs with the same set of rows but different roles, such as Q1 and Q2 EMEA, must be reported separately, since the number needs a conjunction of witnesses.
  • Step 4, removal test. Delete a set of rows that hits every minimal witness and confirm that the output disappears or changes as predicted. Delete a row outside the witness sets and confirm that nothing changes.
  • Step 5, perturbation test. Change one input cell and confirm the output moves by the predicted amount. For SUM, record each input's numerical contribution and confirm that the contributions add to the total.
  • Step 6, evidence kind. Record which of where, why and how evidence supports the cell: a copy location for labels, a witness set for existence, a formal expression for computed numbers.
  • Step 7, source quotation. For each contributing source cell, attach the verbatim source text and observation date. Query provenance stops at the input row; whether that row is correct is a separate question.

Decision table: audit question to minimum evidence

Table 3 below maps the question a reviewer asks to the least evidence that answers it. The mapping is the author's synthesis of the definitions above, not a standard.

Audit questionMinimum evidenceWhy a weaker artifact fails
Which pipelines or datasets touched this value?Dataset lineageSufficient only when the reviewer accepts every row of every upstream dataset as potentially relevant.
Which input rows does the displayed value depend on?Input rows: the minimal witness sets from the query runA dataset arrow cannot exclude row o4, which carries 999 of the 1,249 total order amount.
Which input cells does it depend on?Source cells at three roles: value, key and labelRow-level evidence over-approximates: r1.name is in a contributing row but irrelevant to the SUM.
How were the inputs combined?Transformation: query text, version and a how-polynomial or tensor expressionA witness set cannot show that two pairs must co-occur for the SUM.
Is the input itself right?Source quotation with observation date and the source's own identifierProvenance proves dependence, not accuracy.
Can the value be reproduced later?Query version, snapshot, time, agentWithout a frozen snapshot, a re-run may diverge from the displayed value.

Dataset lineage is cheapest and weakest; only the source quotation speaks to correctness.

Figure 02
Accept or reject a displayed derived value
  1. 01Freeze the run

    Preserve the query text and version, source snapshot identifiers, execution time and responsible agent.

  2. 02Enumerate candidates and witnesses

    List rows admitted by joins and filters, then state minimal witnesses for each output. Report existence and aggregate outputs separately.

  3. 03Test removal

    Delete rows that hit every minimal witness and check the predicted change. Delete a row outside the witnesses and check that nothing changes.

  4. 04Perturb a cell

    Change one input cell and check the predicted movement. For SUM, record each numerical contribution and check that they add to the total.

  5. 05Record the evidence kind

    Identify copy locations for labels, witness sets for existence and formal expressions for computed numbers.

  6. 06Attach source quotations

    Attach verbatim source text and the observation date for every contributing source cell. Input correctness remains a separate question.

Limits: Unsupported Operators, Redactions and Unresolved Source Conflicts

What the formal results do and do not cover

The semiring result applies to positive relational algebra, extended to recursive Datalog queries [5], but Green and colleagues left negation open, noting that it seems to require axiomatizing an additional operation [5]. The toy example uses only inner join, projection, DISTINCT, GROUP BY and SUM, so it sits partly inside that fragment and partly in the aggregate extension. Constructs such as EXCEPT, NOT EXISTS, outer joins, window functions, correlated subqueries and user-defined functions are outside the positive-algebra result, and a claim that all SQL shares the result would be unsupported. The Perm authors list queries with multiple set-difference operations and subqueries in negated or disjunctive expressions as an open problem [19].

Tool documentation as of October 2026

ProvSQL describes itself as a PostgreSQL extension that transparently tracks the provenance of query results [23] and represents provenance as a circuit of gates [23]. PGXN lists release 1.13.0, dated 17 October 2026 [24], and its release notes call it a hardening and performance release [25]. Where-provenance in ProvSQL tracks, for each value in a query result, the specific cell [9], is disabled by default [9] and is labelled an experimental feature [9]. That label is the documented basis for the statement that not every SQL construct is supported under where-provenance. The same page says an aggregate value is computed rather than copied, so it has no location [9]. Outside where-provenance mode, the evaluation function sr_why returns the set of witnesses that support the result [26]. A HAVING condition is not exploded because it is already the provenance of the group [20]. The documentation also states that EXCEPT ALL and INTERSECT ALL over tracked relations are refused [27]. A 2018 demonstration paper cites the earlier result that where-provenance cannot be captured by semiring provenance [28], which is why tools expose both modes rather than one.

The Tübingen group's demonstration targets a feature-rich SQL dialect with correlated subqueries and a focus on bag semantics [29]. A reviewer should ask which contract a tool implements, since reporting the particular set of input cells used differs from the minimal-witness definition in Table 1.

Redactions and unresolved conflicts

Two non-algebraic limits remain.

  • Redactions: if a contributing source cell is withheld from the reviewer, the witness can be named but the source quotation cannot be shown, and the evidence must be recorded as blocked with a reason rather than silently omitted.
  • Unresolved source conflicts: if two registry rows disagreed about org A's region, the query would join both and Q2 would produce a number that mixes two claims.

Truth-discovery research notes that information about one object from different sources may conflict due to errors and missing records [30]. Query provenance names which rows were used; it does not adjudicate between them.

When a catalog or lineage product is the right tool

Table 4 below states the fit between needs and tool classes. It is a description of categories and documented behavior, not a ranking.

NeedTool classDocumented behavior or fit
Estate-wide map of datasets, jobs and columnsLineage and catalog productsOpenLineage defines metadata for running jobs and their corresponding events [14]. DataHub's guide describes column-level lineage that tracks changes and movements for each specific data column [31]. Google documents that lineage records metadata about data movement but doesn't capture the data itself [32].
Which input rows and cells justify one SQL resultQuery-provenance engines or the black-box protocol aboveProvSQL for PostgreSQL; research systems such as Perm and the Tübingen tools. Coverage is bounded as in the previous subsections.
A portable record of the run (snapshot, time, agent)PROV-O or an equivalent run recordRecords entities, activities and derivations; does not compute them [8].
One canonical record per real thing, with a verbatim cited source and observation date behind each value and its chain of custody exportableA system of record (the publisher's product category; see the disclosure above)Relevant to the source-quotation row of Table 3 only to the extent a given system implements it. It is deliberately not a data catalog. Whether a given derived field has input-level justification is checked with the protocol above.

A lineage or catalog product is the right choice when the question is "what depends on this table", for impact analysis or estate inventory. Microsoft Purview's classic catalog documentation, for example, says its lineage granularity can vary based on the data systems supported [33]; dbt notes that column-level lineage does not reflect other usage like joins and filters [34] and relies on SQL parsing [34]; Google documents that column-level lineage is not collected if a job creates more than 1,500 column-level links [32]. These scope statements explain why a column arrow cannot answer which orders produced a particular total.

Provenance shows dependence, not accuracy, so the verbatim source and observation date behind each witnessed input remain necessary.

Data Analysis and Evidence

Worked numbers from the toy example

The toy example yields the following quantities, each recomputed by two independent evaluators and an exhaustive subset search.

  • Rows involved. The eight input rows split into six that appear in some witness (o1, o2, o3, r1, r2, r3) and two that appear in none (o4, r4). The EMEA SUM cell depends on 4 of 8 rows (50%).
  • SUM decomposition. EMEA 200 = 120 (o1, 60%) + 80 (o2, 40%). APAC 50 = 50 (o3, 100%). The output total of 250 is 20.0% of the 1,249 total order amount.
  • Decoy weight. Order o4 holds 999 of 1,249, or 79.98% of the order amount, and contributes 0 to any output.
  • Deletion sensitivity. Deleting any single row that belongs to an EMEA witness changes the EMEA SUM (by minus 120 or minus 80). Deleting any one non-witness row changes nothing. For Q1 no single deletion changes EMEA, but two deletions (one per witness) remove it.

Published measurements on cost and scope

The burden of fine-grained capture is quantified in the literature, with methods that differ.

  • Perm (2009): overhead for provenance-computing TPC-H queries in a range of factor 3 to 30 [19] on test databases of 10MB, 100MB and 1GB [19]; for one query the number of result tuples increased by a factor of approximately 15000 [19].
  • Smoke (2018): at most 22% overhead across four TPC-H queries at scale factor 1 [35].
  • ProvSQL (2025): scale factors 1 to 10, with databases of size 1 to 10 GB [36], and a high overhead on two queries that nevertheless remains under a factor of 4 [36].

The systems differ in definition and workload, so the figures are not a ranking; capture is feasible but not free.

Computational complexity bounds what any checker can promise. Deletion propagation is in general NP-complete for conjunctive queries containing projections and joins [37], so no checker can promise a minimal repair for arbitrary queries.

Conflicts and missing provenance at scale

The scale of source disagreement motivates the "unresolved conflict" limit.

  • Stock and flight sources: for 70% of data items more than one value is provided [38], and only 70% of correct values are provided by the majority of the sources [38].
  • Web-scale extraction: extraction errors are far more prevalent than source errors [39], which implies a second provenance layer, the extractor, that a row-level witness over the extracted table does not itself record.
  • Wikidata referencing: Curotto and Hogan's August 2020 snapshot found 771 million statements (68.56%) referenced to external sources, 68 million (6.02%) referenced to Wikipedia, and 286 million (25.42%) without reference [40].

No cross-industry survey of the share of derived values lacking input-level provenance was found, and none is asserted here.

Figure 03
The contributions to the EMEA SUM of 200Order amount
Source: toy example

Implications and Future Directions

For context engineers, the main implication is a change of evidence standard. A derived field in a canonical record should not be accepted on the strength of a pipeline diagram. It should carry, or be able to regenerate on demand, the witness rows for each displayed cell, the query version and snapshot, and the source quotation behind each witnessed input. The cost literature suggests, though no study tests it directly, that generating witnesses on demand for a reviewed subset may be practical even where capture on every query is not, since overheads range from under a factor of 4 even on ProvSQL's two highest-overhead evaluated queries [36] to a factor of 3 to 30 for Perm's [19].

For tool buyers, the documented limits are the useful part of the documentation. Where-provenance in ProvSQL is described as experimental [9], and column-level lineage in the catalog products cited above is scoped by parsing and by supported systems [34] [33]. Procurement should ask for the output of the toy example, in particular the Q2 EMEA cell and the exclusion of o4, before accepting a claim of fine-grained provenance.

For researchers, three gaps are visible. First, no public benchmark pairs witness-set correctness with verbatim source quotations; the performance papers measure capture overhead rather than reviewer-facing evidence. Second, the aggregate and negation cases remain the least settled. Third, extraction pipelines add a layer that SQL provenance does not see. Combining row witnesses, extractor identity and source quotations in a single exportable chain is an open design problem.

Frequently Asked Questions (FAQs)

What is query provenance, in one sentence?

Query provenance is the record of which input data a query result depends on, at the level of tuples or cells, in the senses of why, where and how [29].

How do you trace a derived value to its source rows?

Write the query, freeze the snapshot, enumerate the join pairs, state the minimal witness sets, then confirm them by deleting a set that hits every witness and by changing one cell at a time, as in Table 2. The how-polynomial or tensor expression records the combination rule.

Why-provenance versus where-provenance: which one is needed?

Existence questions ("why is this row here?") need why-provenance, a witness set. Copy questions ("which cell did this label come from?") need where-provenance. A computed number needs both plus the combination rule, because an aggregate value is computed rather than copied [9].

What are provenance semirings, in plain terms?

They are annotations on tuples that combine by addition for alternatives and multiplication for joint use [5].

Is data provenance the same as data lineage?

Not in the sense used here. Provenance names the origin and history of data [41], lineage tools document flows between datasets and columns, and one vendor describes provenance as the trust layer underneath lineage [1]. For acceptance, the question is whether the artifact names rows.

Conclusion

A dataset-level lineage arrow documents that data moved; it does not show that a displayed cell is supported. The input-level standard is the witness: the set of rows, and where needed cells, that jointly produce the value, with a rule for combining them. The toy example makes the difference concrete. Two alternative witnesses explain why EMEA appears, both pairs are needed for the total of 200, and a decoy order holding 79.98% of the order amount contributes nothing. A reviewer who sees only the lineage arrow cannot tell these cases apart.

The formal basis is well established for positive relational queries and, with extra structure, for aggregates. It is not established for every SQL construct, and tool documentation reflects that, including the experimental status and stated gaps of current implementations. Standards such as PROV-O supply the vocabulary to preserve the query version, snapshot, time and agent, but they do not compute the derivations. The practical result is a short protocol: freeze, enumerate, state witnesses, remove, perturb, record the evidence kind and attach the source quotation.

Two things stay outside the method by design. Provenance shows dependence, not accuracy, so the verbatim source and observation date behind each witnessed input remain necessary. And where sources disagree, the method exposes the conflict instead of resolving it. Teams can adopt the toy example as a regression fixture for any system that claims fine-grained provenance.

External Sources (41)

Published by

Reliable Context Research

Reliable Context is a system of record for organizations that fuse private and public information and must defend every value they act on: one canonical record per real thing, ambiguity shown rather than hidden, and provenance behind every value.

Our product · Evidence and editorial standards · Contact

Request access

Editorial note

Researched and written by Reliable Context Research with AI-assisted research tools; sources are cited inline and checked before publication. Report an error: https://reliablecontext.com/corrections.