LINEAGEX: A Column Lineage Extraction System for SQL

Jiannan Wang; Shi Heng Zhang; Zhengjie Miao

REVIEW 4 major objections 6 minor 13 references

LINEAGEX: A Column Lineage Extraction System for SQL

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read LINEAGEX extracts column-level lineage from SQL query logs alone, without executing queries or accessing a database, by intelligently traversing parse trees and resolving ambiguities such as SELECT * and set operations.

desk verdict Useful demo with a genuinely new reordering trick, but the accuracy claim is untested and the set-operation rule looks like a silent over-approximation. read the letter →

arxiv 2505.23133 v1 pith:NGY5AJFK submitted 2025-05-29 cs.DB

Shi Heng Zhang , Zhengjie Miao , Jiannan Wang This is my paper

classification cs.DB

keywords datalineagecolumnSQLstaticanalysisqueryparsinggovernanceimpactgraph

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's claim is that column-level data lineage can be recovered from a batch of SQL query definitions without executing the queries or instrumenting the database. LINEAGEX does this by parsing each statement with a SQL parser into an abstract syntax tree, traversing the tree with a compact set of keyword rules that classify each column as a direct contributor, a referenced column, or both, and using a stack to defer ambiguous lookups until the defining query has been resolved. According to the paper, this resolves the two recurring difficulties that break existing static tools: SELECT * projections and columns without table prefixes, as well as CTEs, subqueries, and set operations whose intermediate results obscure the true source columns. If the approach is right, it offers a lightweight alternative for impact analysis and data governance teams who only have access to query logs.

What carries the argument

The carrying mechanism is a post-order depth-first traversal of the abstract syntax tree, guided by a table of keyword rules that update three sets: C_con (columns that directly produce an output column), C_ref (columns that appear anywhere in the query, such as in join or filter predicates), and C_pos (column candidates for the current FROM clause). A stack-based auto-inference step reorders the traversal of interdependent queries so that when a table or view is referenced before its definition is known, the system first processes the definition and then resumes, which is what allows SELECT * and unqualified columns to be expanded to concrete columns.

What would settle it

Run LINEAGEX on the MIMIC dataset's 70 view definitions used in the demonstration, execute the same views in a real database, and compare the static lineage graph edge-by-edge against the lineage computed by a DBMS-integrated provenance system; any output column whose dependency set differs, such as a predicate column placed in the contribution set instead of the reference set or a misaligned set operation, would falsify the high-accuracy claim.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is a traversal discipline: process each query's AST in post-order, maintain three accumulating sets — C_con for columns that directly produce an output column, C_ref for columns referenced anywhere in the query such as join predicates or WHERE clauses, and C_pos as the pool of columns reachable from the current FROM — and apply the keyword rules at each node. The design treats lineage as intentionally broad: for an output column c_out, C(c_out) includes any input column whose change could affect c_out, including columns that appear only in predicates. A stack-based auto-inference step reorders interdependent queries so that when a view is referenced before its definition, or a SELECT * cannot be expanded without metadata, the system processes the defining query first and then resumes the deferred traversal. The paper argues this lets LINEAGEX handle views built on SELECT * and set operations that trip up existing static tools, yielding a column-level graph that distinguishes contributing from referenced columns and is also visualized interactively.

Load-bearing premise

The system's correctness rests on the assumption that the SQL parser's parse tree and the keyword rules in Table I faithfully encode the paper's lineage definition for every SQL construct the user feeds it, so any misparse or misclassification of a column silently produces a wrong lineage graph.

Editorial extensions

If this is right

For impact analysis, every output column that references a changed input column — not just those that directly project it — is flagged as potentially affected, which is what the C_ref classification provides.
A data engineer with access only to query logs can construct a column-level lineage graph for the entire warehouse, including views defined through SELECT * and set operations, without asking the DBMS for metadata.
The same static extraction can be augmented with database execution plans when a connection is available, so the tool degrades gracefully from fully static to plan-assisted mode.
The JSON lineage output and interactive HTML graph give data-governance teams a lightweight, visual way to audit sensitive data flow for compliance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's broad 'any column referred in the query' semantics means the graph is deliberately conservative: edges represent potential influence rather than minimal causal dependency, so users should not read absence of an edge as proof of independence.
The demonstration shows a single running example plus the MIMIC dataset, but reports no numeric precision or recall; a labeled benchmark over a large query log is the natural next step to substantiate the claim of high coverage and accuracy.
The design is extensible: because the traversal rules are keyword-based and the parser is pluggable, adding dialect-specific rules or a standard lineage interchange format would let the same core serve governance platforms.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things before reading. First, LINEAGEX is a plausible, lightweight column-lineage library that does something the cited tools don't: it reorders query processing to resolve SELECT * and unqualified column references across view definitions. That's a real engineering contribution, and the open-source release makes it checkable. Second, the paper's headline claim — high coverage and accuracy — has zero quantitative support, and the one rule that matters for set operations looks sloppy.

The paper is a demonstration, so I don't expect a full benchmark, but the abstract claims 'high coverage and accuracy' and that claim is not established. The only walk-through is the same motivating example the system was designed to fix. That is one coherent demo, not evidence of coverage. The MIMIC dataset is mentioned but no numbers are given.

The more specific concern is the set-operation rule in Table I. As written, it adds every projection column and every C_pos column to C_ref for every output column, with no position or name correspondence. For 'SELECT a,b FROM t1 UNION SELECT c,d FROM t2', that gives each output column the union of all four columns, and it classifies them all as referenced rather than contributed. Maybe that over-approximation is deliberate — the paper's definition includes 'any column referred in the query' — but the demo text says 'all of webact's columns will reference the pagecolumn' as if that is correct semantics, and the UI shows some as 'both referenced and contributed.' The rule as printed only updates C_ref, so the C_con classification is unclear. Either way, the paper should say outright that set-operation lineage is conservative by design, or fix the rule and show a non-aligned example.

The citation pattern is fine: SQLLineage and SQLGlot are the obvious baselines, and the provenance literature is cited properly. Self-citation is not an issue.

Who should read this: someone building static SQL analysis tools or using lineage for governance. The dynamic reordering idea is worth a look. But don't take the accuracy claim at face value. For a demo, I'd accept conditional on the authors adding a small benchmark against SQLLineage on a few real workloads and clarifying the set-operation semantics. It deserves referee time, but the final version needs to tone down the claim or back it up.

Referee Report

4 major / 6 minor

Summary. The paper presents LINEAGEX, an open-source Python library that infers column-level data lineage statically from SQL query logs without executing queries or integrating with a DBMS. The system parses queries with SQLGlot, builds a query dictionary, traverses each query's AST in post-order while applying keyword rules (Table I) that populate contribution (C_con), referenced (C_ref), and both-type (C_both) column sets, and uses a stack-based reordering to resolve forward references, SELECT *, and unqualified column ambiguities by deferring traversal of views defined later in the log. An optional mode uses PostgreSQL's EXPLAIN when a database connection is available. The demonstration paper walks through an impact-analysis scenario on three views and three base tables, compares LINEAGEX's output with SQLLineage and GPT-4o, and showcases an interactive lineage-graph UI. The central claim is that LINEAGEX achieves 'high coverage and accuracy' for column-lineage extraction.

Significance. The tool addresses a real pain point: extracting column-level lineage from query logs without heavyweight DBMS integration, and the open-source release plus video demonstration are concrete artifacts that support reproducibility. The stack-based auto-inference of view definitions is a plausible and useful mechanism for resolving SELECT * and unqualified column references across multiple queries, and the running example nicely illustrates the cross-query dependency problem. If the accuracy claim were substantiated, LINEAGEX would be a welcome lightweight alternative in the lineage-tool landscape. However, the evidence in the paper is far too thin for the claim: there is no benchmark, no labeled test set, no error analysis, and the only demonstrated example is the same hand-constructed scenario used to motivate the design (Example 1), so the evidence is partly self-confirming. In addition, the traversal-rule specification in Table I is ambiguous and, read literally, contradicts the paper's own walkthrough, and the set-operation rule does not preserve positional correspondence between columns.

major comments (4)

[Abstract, Section IV] The central claim that LINEAGEX 'achieves high coverage and accuracy' is not supported by any reported measurement. Section IV describes a demonstration of a single hand-picked three-query scenario—the same Example 1 used to motivate the system in Section I—and mentions the MIMIC dataset without reporting any results on it. There is no labeled benchmark, no comparison table, no error counts, and no discussion of failure cases. Because the demonstrated example is also the motivating example, the evidence is partly self-confirming and cannot establish a general accuracy claim. The revision should either add a small evaluation (e.g., a labeled set of queries with ground-truth lineage) or replace the abstract's unconditional accuracy claim with a scoped one.
[Table I (Set Operation row), Section IV Step 4] The set-operation rule is position-insensitive and, as stated, cannot produce correct lineage for multi-column set operations whose leaves are not aligned. For 'CREATE VIEW v AS SELECT a, b FROM t1 UNION SELECT c, d FROM t2', standard SQL semantics assigns v.a lineage {t1.a, t2.c} and v.b lineage {t1.b, t2.d} (positional ordering), but the rule 'C_ref ← C_ref ∪ p ∪ C_pos ∀ p ∈ P' attaches the union of all columns of both leaves to every output column, and labels them only as C_ref even though the branch values are copied into the output (a contribution, not merely a reference). The demo's INTERSECT query Q2 has columns that line up one-to-one, so it cannot expose the flaw; worse, Step 4 presents the rule's all-to-all outcome ('all of the webact's columns will reference the page column') as the correct answer, which is exactly what needs to be justified. Please either make the rule preserve positional/name correspondence (and classify branch columns as C_con), or give a labeled benchmark that validates the all-to-all behavior under the paper's notion of 'potential change'.
[Table I (SELECT and Other Keywords rows), Section III Figure 4 walkthrough] There is an inconsistency between the written rule table and the walkthrough. Literally read, 'C_con ← p ∪ C_pos ∀ p ∈ P' (SELECT rule) and 'C_ref ← C_ref ∪ p ∪ C_pos ∀ p ∈ tempcols' (Other Keywords rule) attach the full candidate set C_pos—all columns of all tables scanned so far in the FROM—to every output column. For Q3, that would make wcid's C_con include every column of customers and web, contradicting Step 5 of the walkthrough ('Each output column's C_con only has one column, e.g., wcid has C_con of customers.cid'). Since Table I is the core algorithm specification, it must be rewritten with explicit per-output-column semantics, stating exactly when C_pos is used (e.g., only to resolve * or an unqualified column) and when only the projection expression p is attached.
[Section III, Table/View Auto-Inference] The mechanism for handling missing metadata is under-specified. The paper names 'absence of metadata' as a key challenge and says the stack mechanism resolves SELECT * and unqualified columns by deferring to view definitions, but it never explains how the columns of a base table are discovered when the log contains no CREATE TABLE for that table (as with customers, orders, and web in Example 1) and no DBMS connection is available. This matters because SELECT * expansion and the FROM rule's 'C_pos ← C_pos ∪ {its columns}' both require a known column list for every referenced table. The revision should specify the schema-inference step (e.g., collecting columns from all query references) and state its limitations, since otherwise the claimed coverage cannot be assessed.

minor comments (6)

[Section III, Table I] The notation is inconsistent: the text uses C_con, C_ref, C_both, and M_CTE while Table I uses Ccon, Cref, and MCTE; please unify the notation so the rules are unambiguous.
[Section II, References] The inline citation [3] for Apache Atlas points to Tang et al., 'SAC: A System for Big Data Lineage Tracking', which is a different system; the bibliography entry and the inline text do not match and should be corrected.
[Table I, Other Keywords row] The 'Other Keywords' row collapses JOIN, WHERE, GROUP BY, HAVING, and ORDER BY into a single rule, but these constructs have different lineage semantics (e.g., join predicates introduce references, while projections introduce contributions); a brief statement of which SQL constructs are supported and how would help evaluate the coverage claim.
[Section III] The traversal collects lineage for output columns, but the paper never explains how the names of the output columns of a query are determined for the lineage graph, especially for SELECT *, AS aliases, and set operations; a short description of the per-output-column bookkeeping would make the rules in Table I interpretable.
[Section IV] The MIMIC dataset is invoked ('more than 300 columns in 26 base tables and 700 columns in 70 view definitions'), but the paper reports no result, measurement, or described demo step on MIMIC; a sentence on what the audience will see on MIMIC would support the coverage claim.
[Section IV, Comparison with existing methods] The GPT-4o comparison is a single interaction and should be labeled as illustrative; as written, it reads as a capability claim about LLM lineage reasoning rather than as a systematic comparison.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: LINEAGEX's lineage rules are an implementation, not a self-derived prediction; the demo is anecdotal but not circular.

full rationale

LINEAGEX does not claim a formal derivation from first principles. Section II defines column lineage operationally: C(c_out) includes directly contributing input columns plus any column referred in the query. Section III and Table I specify traversal rules that realize that definition. The system's output is therefore, by construction, whatever the rules compute; the paper's 'high coverage and accuracy' is an empirical claim about whether the rules match intended lineage, supported only by the running example and a MIMIC demo. That is weak evidence, but not circularity: there is no fitted parameter renamed as a prediction, no uniqueness theorem imported from the authors' prior work, and no equation reduces to its own input. References [5] and [6] are external tools, and the authors' contributions are not justified by self-citation. The set-operation rule's position-insensitivity is a potential correctness limitation, not a circularity, because the rule is not derived from the output it is meant to produce. The only mild self-confirmation is that Example 1 is the same scenario used to motivate the rules; but there is no derivation-level equivalence. Score 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The system introduces no new physical or formal entities and no fitted numeric parameters. Its assumptions are about parser fidelity, the lineage semantics, the correctness of hand-written traversal rules, and completeness of the input query log.

assumptions (4)

domain assumption SQLGlot's AST is a faithful representation of the input SQL for the supported dialects and constructs.
Invoked in Section III, Transformation Module: 'we used SQLGlot' to generate the AST that all lineage rules operate on.
ad hoc to paper Column-level lineage should include every column referenced in the query, not only columns that directly determine output values.
Section II defines C(c_out) to include 'any column referred in the query'; this modeling choice determines C_ref and affects impact-analysis conclusions, but is not compared with alternative semantics.
ad hoc to paper The keyword traversal rules in Table I correctly implement the lineage definition across joins, set operations, CTEs, and subqueries.
Section III presents the rules with no formal proof or benchmark; correctness is assumed by construction.
domain assumption The query log contains the full set of definitions needed to resolve every referenced view or table.
Section III states missing dependencies cause errors when running EXPLAIN, and the stack mechanism can only defer queries whose definitions exist in the input.

how reviews work

0 comments

Cite this review

Pith. "Pith review of LINEAGEX: A Column Lineage Extraction System for SQL." pith.science (2026). https://pith.science/paper/NGY5AJFK

@misc{pith2026250523133,
  author       = {Pith},
  title        = {Pith review of: LINEAGEX: A Column Lineage Extraction System for SQL},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NGY5AJFK}},
  note         = {Machine review of arXiv:2505.23133}
}

read the original abstract

As enterprise data grows in size and complexity, column-level data lineage, which records the creation, transformation, and reference of each column in the warehouse, has been the key to effective data governance that assists tasks like data quality monitoring, storage refactoring, and workflow migration. Unfortunately, existing systems introduce overheads by integration with query execution or fail to achieve satisfying accuracy for column lineage. In this paper, we demonstrate LINEAGEX, a lightweight Python library that infers column level lineage from SQL queries and visualizes it through an interactive interface. LINEAGEX achieves high coverage and accuracy for column lineage extraction by intelligently traversing query parse trees and handling ambiguities. The demonstration walks through use cases of building lineage graphs and troubleshooting data quality issues. LINEAGEX is open sourced at https://github.com/sfu-db/lineagex and our video demonstration is at https://youtu.be/5LaBBDDitlw

Figures

Figures reproduced from arXiv: 2505.23133 by the authors.

**Figure 3.** An illustration of LINEAGEX. LINEAGEX with the popular Python data science ecosystem by providing a simple API that directly takes the SQL statements and outputs the lineage graph. Besides the API, we provide a UI that visualizes the column lineage for users to examine. In this demonstration, we will showcase the impact analysis scenario and illustrate how LINEAGEX provides accurate column-level lineage to further h… view at source ↗

**Figure 4.** Sample AST and traverse order SQL Lineage Information Extraction Module. The final module takes each query AST as input and builds the mappings from the result view/table to its lineage T and the mapping from output columns C output to input columns C source . We consider three types of columns in the lineage: 1)C con: columns that directly contribute to C output; 2) C ref : columns referenced in the query, e.g., co… view at source ↗

Figures from the paper (1 more)

**Figure 5.** Figure 5: The User Interface of LINEAGEX. EAGEX can also incorporate the extraction with a database connection. We extended LINEAGEX using PostgreSQL’s EXPLAIN command to obtain the physical query plan instead of the AST from the parser, which provides accurate metadata to deal …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

ProvSQL: Provenance and Probability Management in PostgreSQL,

P. Senellartet al., “ProvSQL: Provenance and Probability Management in PostgreSQL,”PVLDB, vol. 11, no. 12, pp. 2034–2037, 2018

work page 2018
[2]

Perm: Processing Provenance and Data on the Same Data Model through Query Rewriting,

B. Glavic and G. Alonso, “Perm: Processing Provenance and Data on the Same Data Model through Query Rewriting,” inProc. ICDE, Shanghai, China, Mar. 29 - Apr. 2, 2009, pp. 174–185

work page 2009
[3]

SAC: A System for Big Data Lineage Tracking,

M. Tanget al., “SAC: A System for Big Data Lineage Tracking,” in Proc. ICDE, Macao, China, Apr. 8-11, 2019, pp. 1964–1967

work page 2019
[4]

Microsoft Purview: A System for Central Governance of Data,

S. Ahmadet al., “Microsoft Purview: A System for Central Governance of Data,”PVLDB, vol. 16, no. 12, pp. 3624–3635, 2023

work page 2023
[5]

sqlglot,

T. Mao, “sqlglot,” GitHub repository, 2024, [Online]. Available: https: //github.com/tobymao/sqlglot

work page 2024
[6]

sqllineage,

J. Hu, “sqllineage,” GitHub repository, 2024, [Online]. Available: https: //github.com/reata/sqllineage

work page 2024
[7]

An Approach to Evaluate Data Trustworthiness Based on Data Provenance,

C. Daiet al., “An Approach to Evaluate Data Trustworthiness Based on Data Provenance,” inSecure Data Management, Berlin, Heidelberg, 2008, pp. 82–98

work page 2008
[8]

DataHub: Collaborative Data Science & Dataset Version Management at Scale,

A. P. Bhardwajet al., “DataHub: Collaborative Data Science & Dataset Version Management at Scale,” inCIDR, 2015

work page 2015

Show all 13 references

[9]

Why and where: A characterization of data prove- nance,

P. Bunemanet al., “Why and where: A characterization of data prove- nance,” inICDT, London, UK, Jan. 4–6, 2001, pp. 316–330

2001
[10]

Lineage tracing for general data warehouse transformations,

Y . Cui and J. Widom, “Lineage tracing for general data warehouse transformations,”The VLDB Journal, vol. 12, no. 1, pp. 41–58, 2003

2003
[11]

GProM—a swiss army knife for your provenance needs,

B. S. Arabet al., “GProM—a swiss army knife for your provenance needs,”IEEE Data Eng. Bull., vol. 41, no. 1, 2018

2018
[12]

Computing how-provenance for SPARQL queries via query rewriting,

D. Hern ´andezet al., “Computing how-provenance for SPARQL queries via query rewriting,”PVLDB, vol. 14, no. 13, pp. 3389–3401, 2021

2021
[13]

Vamsa: Automated provenance tracking in data science scripts,

M. H. Namakiet al., “Vamsa: Automated provenance tracking in data science scripts,” inProc. KDD, 2020

2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

ProvSQL: Provenance and Probability Management in PostgreSQL,

P. Senellartet al., “ProvSQL: Provenance and Probability Management in PostgreSQL,”PVLDB, vol. 11, no. 12, pp. 2034–2037, 2018

work page 2018

[2] [2]

Perm: Processing Provenance and Data on the Same Data Model through Query Rewriting,

B. Glavic and G. Alonso, “Perm: Processing Provenance and Data on the Same Data Model through Query Rewriting,” inProc. ICDE, Shanghai, China, Mar. 29 - Apr. 2, 2009, pp. 174–185

work page 2009

[3] [3]

SAC: A System for Big Data Lineage Tracking,

M. Tanget al., “SAC: A System for Big Data Lineage Tracking,” in Proc. ICDE, Macao, China, Apr. 8-11, 2019, pp. 1964–1967

work page 2019

[4] [4]

Microsoft Purview: A System for Central Governance of Data,

S. Ahmadet al., “Microsoft Purview: A System for Central Governance of Data,”PVLDB, vol. 16, no. 12, pp. 3624–3635, 2023

work page 2023

[5] [5]

sqlglot,

T. Mao, “sqlglot,” GitHub repository, 2024, [Online]. Available: https: //github.com/tobymao/sqlglot

work page 2024

[6] [6]

sqllineage,

J. Hu, “sqllineage,” GitHub repository, 2024, [Online]. Available: https: //github.com/reata/sqllineage

work page 2024

[7] [7]

An Approach to Evaluate Data Trustworthiness Based on Data Provenance,

C. Daiet al., “An Approach to Evaluate Data Trustworthiness Based on Data Provenance,” inSecure Data Management, Berlin, Heidelberg, 2008, pp. 82–98

work page 2008

[8] [8]

DataHub: Collaborative Data Science & Dataset Version Management at Scale,

A. P. Bhardwajet al., “DataHub: Collaborative Data Science & Dataset Version Management at Scale,” inCIDR, 2015

work page 2015