From Conceptual Lineage to Executable Lineage

1. The many meanings of lineage

“Lineage” may refer to several artefacts. A high-level architecture map shows source systems, domains, and products. A pipeline graph shows jobs and datasets. A column map links source fields to target attributes. A provenance record identifies the exact inputs and transformations that produced a value. These are related but not interchangeable.

Let lineage maturity be layered:

where $L_0$ is conceptual relevance, $L_1$ dataset flow, $L_2$ process dependency, $L_3$ attribute derivation, and $L_4$ execution-instance provenance. Higher layers do not invalidate lower ones. They answer different questions.

A conceptual map may say that diagnostic reporting involves patient, encounter, order, sample, result, and report objects. It cannot by itself answer why one result value has a particular unit or why a row was excluded. Treating it as full lineage creates false confidence.

2. A typed provenance graph

Lineage can be represented as a directed property graph

where vertices include sources, fields, tasks, rules, reference sets, contracts, policies, outputs, and executions; edges are typed; and $\pi$ stores version and temporal properties.

Useful edge types include reads, derives, filters, joins, maps, validates, authorises, publishes, and supersedes. A generic edge “depends on” loses explanatory power because dependency kinds propagate differently.

For example, changing a source field should affect downstream derivations that read it. Changing a policy may affect publication without changing values. Changing a quality threshold may alter quarantine. A typed graph allows impact analysis to follow relevant edge classes.

3. From field to attribute

Field-level lineage should express transformation, not only adjacency. Let source field $c_s$ map to target attribute $a_d$ through tasks ${\tau }_1,\dots ,{\tau }_k$:

Each edge should reference a transformation expression or rule identifier. For a derived attribute

lineage includes every material input, reference version $r_v$, and parameter $\theta$. If a record is filtered by predicate $p$, the exclusion path is part of lineage even though no target value exists.

This suggests positive and negative provenance. Positive provenance explains why a value is present. Negative provenance explains why an expected value is absent. The latter is difficult but essential for questions such as “why was this case not counted?”

4. Provenance semirings and contribution

Database theory offers a formal language for provenance. In semiring provenance, annotations propagate through relational operations. Addition can represent alternative derivations; multiplication can represent joint contribution.

If output tuple $y$ derives from source tuples $x_1$ and $x_2$ through a join, its provenance polynomial may be

If either of two source paths can produce the same output,

This abstraction helps reason about which inputs contribute to outputs and how deletion or correction propagates. Real pipelines include arbitrary code, external services, and approximate transformations, so complete formal provenance may be impractical. Yet the principle remains valuable: lineage should express contribution structure, not merely execution sequence.

5. Lineage across semantic layers

A source-to-target path is incomplete if it omits semantic projection. Suppose a local code is mapped to a canonical concept. The output depends on the local value, mapping table, mapping version, confidence rule, and perhaps manual adjudication.

Semantic lineage can be represented as

If a mapping changes, historical canonical outputs may be restated. The graph should identify affected records and products. Similarly, a metric depends on a population definition and aggregation rule, not just on columns.

Lineage must therefore cross physical, logical, and semantic layers. Otherwise the platform can tell where bytes moved while remaining silent about where meaning changed.

6. Control and policy lineage

Some dependencies determine whether computation occurs rather than how values are derived. A task may run only after another task passes quality checks. A dataset may be published only if a policy permits the purpose and role.

Control lineage records such gates:

Policy lineage records the decision basis:

These paths are essential when an output is absent, delayed, or restricted. Without them, operational lineage can misdiagnose a policy denial as a pipeline failure.

Policy lineage also supports accountability. It shows not only who accessed data, but which rule allowed the access under which declared purpose.

7. Execution-instance provenance

Design-time lineage describes possible paths. Runtime provenance describes the path actually taken by a particular execution and output version.

Let execution e produce output y. Its provenance subgraph is

where vertices carry concrete versions, timestamps, hashes, partitions, parameters, and quality outcomes. Two outputs with the same logical lineage may have different runtime provenance because they used different source snapshots or reference versions.

Execution provenance enables replay and forensic analysis. It should be immutable or append-only, linked to publication manifests, and queryable at several granularities. Full cell-level provenance may be expensive; platforms can combine exact lineage for critical attributes with dataset-level lineage elsewhere.

The architecture should state its precision, rather than implying universal traceability.

8. Executable impact analysis

Lineage becomes executable when it drives operations. Suppose contract attribute a changes. The impacted set is a graph reachability query:

Typed edges allow selective propagation. A documentation-only relation may not trigger replay. A semantic dependency may trigger metric restatement. A policy dependency may trigger access review.

Executable lineage can generate test plans, identify owners, estimate affected partitions, block incompatible releases, and construct replay DAGs. It can also support data deletion by identifying derived copies, though deletion across aggregates and models remains complex.

The graph is no longer a passive diagram. It participates in deployment and incident control.

9. Explanation and the limits of lineage

Lineage can explain production without explaining the represented world. It answers “how was this value computed?” rather than “why did this event happen?” Confusing the two turns provenance into pseudo-causality.

Lineage also does not guarantee correctness. A perfectly traced computation can implement a wrong rule. Nor does it eliminate interpretation: users must understand which dependencies are material and what the transformation means.

The platform should expose explanation at appropriate levels. An executive may need metric definition and source domains; an analyst may need field derivation; an auditor may need execution hashes; an engineer may need code and partition details. One graph supports multiple projections.

10. Building lineage as infrastructure

Practical lineage combines static code analysis, orchestrator metadata, query logs, explicit mapping specifications, contract registries, reference versioning, and runtime manifests. Automatic extraction is valuable but cannot infer every semantic or policy relation. Human-authored edges remain necessary.

Quality of lineage can be measured through coverage and validity:

supplemented by freshness, version completeness, and tested reachability. Coverage estimates should be honest about unknown material edges.

A lineage programme succeeds when teams use the graph during change, incident response, and explanation— not when a catalogue displays attractive arrows.

Conclusion

Conceptual lineage identifies relevant objects and domains. Executable lineage identifies the typed, versioned, temporal path by which a particular output became publishable. The transition requires field-level derivation, semantic mappings, control gates, policy decisions, and runtime evidence.

Formal provenance models clarify contribution; property graphs make heterogeneous dependencies queryable; execution manifests connect design to history. The result supports impact analysis, replay, compatibility control, and layered explanation.

Lineage does not create truth, but it makes the manufacture of claims inspectable. Its mature form is not a picture of the platform. It is part of the platform’s control plane: a computational memory that can answer what depends on what, under which rule, in which version, and with what consequence.

Conceptual references

Buneman, P., Khanna, S., and Tan, W.-C. “Why and Where: A Characterization of Data Provenance” (2001). Green, T. J., Karvounarakis, G., and Tannen, V. “Provenance Semirings” (2007). Cheney, J., Chiticariu, L., and Tan, W.-C. “Provenance in Databases” (2009). Moreau, L. et al. “The Open Provenance Model” (2011). Latour, B. Science in Action (1987).