Connected Schema Linking: Letting Join Structure Recover the Columns a Question Never Names

When a language model turns a business question into SQL over a large company database, it first has to pick which tables and columns matter. This step is called schema linking, and it fails in a particular way. The question often never mentions the column that holds the answer, or the intermediate table needed to join two mentioned tables. A schema linker that scores each column by how well its name matches the question will drop exactly those elements. Once a column is missing from the prompt, no amount of downstream reasoning can recover it.

This proposal treats the database schema as the graph it already is. Tables and columns are nodes, and foreign keys and co-usage in past queries are edges. Relevance flows from the columns the question does match to the columns it does not. The final selection must then be a connected, joinable subgraph that fits a token budget. The bet is that structure is a cheap and reliable bridge across the vocabulary gap: a cryptic column like cst_seg_cd shares no words with "customer tier," but it sits one hop from a table that does.

Core Claim

Current schema linkers make independent keep-or-drop decisions per item, even when they are budget-aware. RESDSQL ranks items with a cross-encoder and keeps the top $k$. KaSLA solves a 0-1 knapsack over tables and columns. Extractive Schema Linking (ExSL) reads per-column relevance from marker-token hidden states. None of these guarantees that the chosen elements can be joined, and none lets evidence at one node inform another. KaSLA itself reports that roughly 9.52% of cases still miss relevant elements.

We claim that two changes, applied on top of any of these linkers, recover a specific and measurable class of misses: gold columns and bridge tables with near-zero word overlap with the question. The first change is propagating base relevance scores over a typed schema graph. The second is selecting a connected subgraph under a budget rather than an independent set. The gain should grow with schema size. It should therefore be largest on Spider 2.0, whose databases average 812 columns and where schema linking causes 27.6% of errors.

The claim is falsifiable in a sharp way. If a trivial post-hoc repair matches our gains, the idea is not worth having. That repair adds every table on the shortest foreign-key path between the tables the base linker selected.

Mechanism

Let $s_i \in [0,1]$ be the relevance score any base linker assigns to schema element $i$. Let $W$ be a column-normalized adjacency matrix over the schema graph. The graph has three edge types: table–column membership, foreign-key links, and co-occurrence of two elements in training SQL. The edge types carry separate weights, fitted on a development split. Propagated relevance is the fixed point of a personalized random walk that restarts at the base scores:

$$r = (1-\alpha)\, s + \alpha\, W r,$$

where $\alpha \in [0,1)$ controls how far relevance spreads.

This borrows directly from PositionRank. PositionRank biases PageRank's restart distribution with a positional prior to rank keyphrases in scholarly papers, reporting a 29.09% relative MRR gain on the Nguyen dataset. We replace its word co-occurrence graph with a relational schema graph, and its positional prior with a learned lexical-semantic prior.

Selection then solves a prize-collecting Steiner tree problem: choose a connected subgraph $T$ that maximizes collected relevance minus cost, subject to a token budget $B$:

$$\max_{T \text{ connected}} \sum_{i \in T} r_i - \lambda \sum_{i \in T} c_i \quad \text{s.t.} \quad \sum_{i \in T} c_i \le B.$$

Here $c_i$ is the number of prompt tokens element $i$ costs, and $\lambda$ trades relevance against length. We use a standard greedy or primal-dual approximation, because schemas of a few thousand nodes make exact solvers unnecessary.

We borrow the budget from KaSLA's dynamic redundancy estimate so the comparison with it is clean. The only change is the connectivity constraint and the propagated prizes. The budget is also our answer to a constraint from ECLASS-Augmented Product Search: there, adding the full "advanced" attribute set hurt retrieval compared with the "basic" set. Exposing more structure is not free, so the budget must keep propagation from dumping whole neighborhoods into the prompt.

Relation to Enterprise Graph Systems

The enterprise graph literature supplies the motivating premise rather than the method. RelGo shows that relational query plans improve dramatically when the optimizer sees graph topology instead of flat per-column statistics. GalaxyWeaver rewrites schemas using workload query patterns. We carry both ideas to the natural-language front end. Topology should shape which schema elements the model sees, and workload co-usage is a legitimate edge signal.

Unlike GalaxyWeaver, we do not change the physical schema, and we do not rely on a non-deterministic LLM to redesign anything. The graph is derived deterministically from catalog metadata and query logs.

A real risk in cloud warehouses is that foreign keys are often undeclared. We therefore also build an inferred-key variant, with edges from column-name and type matching plus log co-usage. We report results separately for declared-key and inferred-key graphs.

Research Program

We will build the propagation-plus-selection module as a drop-in stage after three base linkers: ExSL marker probabilities, KaSLA's combined scores, and RSL-SQL's forward-linking selections converted to scores. The SQL generator is held fixed per comparison.

The central analysis is stratified. For each gold column and table, we compute its word and subword overlap with the question, and we split gold elements into overlap bins. We then report recall per bin. The hypothesis predicts gains concentrated in the zero-overlap bin and on bridge tables. It predicts little change where names match. Spider-DK gives a curated version of this split: its omitted-column category drives accuracy down to 7.9% and implicit conditions to 9.1%.

A second analysis measures connectivity directly: the fraction of selected sets in which every selected table is reachable from every other through selected join edges. We report it alongside the Recall+ and Precision+ measures that KaSLA introduced.

Baselines

The naive reference points are full-schema prompting and BM25 column retrieval. Full-schema prompting is feasible on BIRD but truncates on Spider 2.0. BM25 scored 31.4% Hit_Rate@5 against 94.3% for dense retrieval with hierarchical metadata in the ECLASS study, so we expect it to be weak. We include it to anchor the overlap-stratified curves.

The strongest existing competitors are RSL-SQL and KaSLA-on-RSL-SQL. RSL-SQL reports 67.21% execution accuracy on the BIRD development set with GPT-4o and 63.56% with DeepSeek. It also reports 94% strict recall while cutting input columns by 83%. KaSLA reports that plugging its knapsack linker into RSL-SQL with DeepSeek-v3 raises BIRD execution accuracy from 63.17% to 64.73%. ExSL reports 63.23% on BIRD dev against 59.71% for generative baselines.

On Spider 2.0-lite, the file reports 5.68% for DAIL-SQL and 8.78% for DeepSeek-V3. No reported result was found on Lacuna for KaSLA, ExSL, or RSL-SQL on Spider 2.0. We will run all three ourselves.

Fairness means the same base scores, the same SQL generator and decoding settings, and the same token budget $B$ for every selector. Hyperparameters ($\alpha$, the edge-type weights, and $\lambda$) are tuned on a held-out split with a trial budget equal to what we give KaSLA's budget parameters.

The critical ablation is foreign-key closure. It takes the base linker's selection and adds all tables and key columns on shortest foreign-key paths between selected tables. We also run propagation without the connectivity constraint, and the connectivity constraint without propagation.

Beating the strongest baseline means three things. First, higher execution accuracy than KaSLA-on-RSL-SQL at the same DeepSeek-v3 generator, meaning above 64.73% on BIRD dev. Second, a statistically significant recall gain in the zero-overlap bin at equal or smaller prompt size. Third, a clear margin over foreign-key closure on Spider 2.0-lite.

Why not just…?

Why not just add foreign-key closure after an existing linker? This is the serious threat. On BIRD, with about 7.3 tables per database, closure may capture most of the bridge-table benefit, and we expect it to be competitive there. It has two limits. It cannot promote an unmentioned column inside a selected table, which is the Spider-DK omitted-column case. And on 812-column warehouses, shortest-path closure can add many tables with no budget control. The closure ablation settles this directly. If closure matches us on Spider 2.0-lite and on zero-overlap recall, we will report that the contribution reduces to closure.

Why not just put the whole schema in a long-context model? RSL-SQL attributes its gains partly to removing schema noise. ExSL notes that full-schema prompting is costly even when the schema fits. On Spider 2.0, frontier agents reach only 21.3% (o1-preview) and 12.3% (GPT-4o). Our full-schema baseline measures this at matched generators, and the overlap-stratified curves show whether long context recovers zero-overlap columns on its own.

Why not just have an LLM rewrite the question into schema vocabulary? The ECLASS study found that LLM rewriting sometimes hurt retrieval by stripping technical constraints. On Robustness of Neural Semantic Parsers shows parsers dropping from about 85% to about 40% under rephrasing, so injecting paraphrases is itself risky. Rewriting is also complementary: it changes $s$, whereas we change how $s$ is used. We will run a rewrite-then-link baseline and a rewrite-plus-propagation combination to see whether structure adds anything beyond better base scores.

Why not just let an agent execute queries and self-correct? KaSLA's failure analysis shows that execution feedback cannot repair a query whose required column never entered the prompt. RSL-SQL notes that live execution is often not allowed in secured settings. We treat self-correction as an orthogonal stage and hold it fixed, on or off, across all selectors.

Proposed Experiments

Experiments run on Spider, Spider-DK, Spider-Syn, Spider-Realistic, BIRD, and Spider 2.0-lite. For each, we report execution accuracy, Recall+, Precision+, prompt tokens, connectivity rate, and overlap-stratified recall.

Three checks are decisive. First, on Spider 2.0-lite, propagation plus connected selection must beat foreign-key closure on execution accuracy at equal token budget. Second, the recall gain must be concentrated in the zero-overlap bin and the Spider-DK omitted-column category, not spread evenly; an even spread would suggest we are merely admitting more elements. Third, the inferred-key graph must retain most of the gain of the declared-key graph, which determines whether the method transfers to warehouses without declared constraints.

A cost check completes the picture. The module should add latency comparable to KaSLA's reported increase from 5.15 s to 5.48 s per instance, not the multi-second LLM loops it replaces.