Auto-Relate: A Unified Approach to Discovering Reliable Functional Relationships Leveraging Statistical Tests Ziyan Han1 , Yeye He2∗ , Shuyuan Kang3 , Min Xie4 , Weiwei Cui2 , Song Ge2 , Haidong Zhang2 , Dongmei Zhang2 , Surajit Chaudhuri2 , Rui Mao1∗ , Jianbin Qin1∗ 1 Shenzhen University
2 Microsoft Research
3 Beijing Institute of Technology, Zhuhai
4 Shenzhen Institute of Computing Sciences
{hanzy,mao,qinjianbin}@szu.edu.cn,{yeyehe,weiweicu,songge,haizhang,dongmeiz,surajitc}@microsoft.com, [email protected],[email protected]
arXiv:2606.07060v1 [cs.DB] 5 Jun 2026
ABSTRACT Tables in spreadsheets, computational notebooks, and databases often contain rich inter-column relationships. Yet these relationships are typically implicit and are often lost when tables are exported to standard formats. Recovering them can benefit downstream tasks, including table understanding, data quality improvement, and provenance analysis. However, simply mining relationships that hold on an observed table is insufficient, as many are spurious due to coincidence, redundancy, or limited data diversity. In this paper, we introduce functional relationships (FRs) as a unified notion for inter-column relationships in tables, subsuming arithmetic relationships, string transformations, and functional dependencies. We characterize FR reliability through four complementary criteria: accuracy, atomicity, stability, and integrity. Guided by these criteria, we propose Auto-Relate, a mine-then-verify framework that first generates accurate candidate FRs and then verifies the remaining reliability criteria through a Minimality Test, a Perturbation Test, and an Independence Test, respectively. To further improve efficiency, we develop three optimization strategies, including a group-by lower bound for early rejection, a closed-form speedup for arithmetic FRs, and a binomial bound for statistically guided early termination. We construct a large-scale benchmark suite from 58,679 real-world spreadsheets and relational tables, containing 6,414 ground-truth FRs spanning all three FR types. Extensive experiments against 18 baselines show that Auto-Relate consistently achieves the best performance, with an average PR-AUC of 0.87, 59% higher than the best competing baseline across all settings. PVLDB Artifact Availability: The source code and data have been made available at https://github.com/ katekangKK/Auto-Relate.git.
1
INTRODUCTION
Tables are a fundamental data representation across spreadsheets (e.g., Excel or Google Sheets), computational notebooks (e.g., Jupyter), and relational databases. In these environments, users routinely create derived columns from existing ones by writing spreadsheet formulas, data-transformation programs, or SQL expressions [27, 29, 30, 68]. As a result, tables often contain rich inter-column relationships. For example, numeric columns are often related by arithmetic formulas, textual columns are commonly related by string transformations, and categorical columns may exhibit deterministic dependency patterns. Although ubiquitous in real-world tables, * Corresponding authors
such relationships are often implicit rather than explicitly represented, and are typically not preserved when tables are exported to standard formats such as CSV or Parquet. Recovering such relationships from raw tables is practically valuable, benefiting a range of downstream applications, including table understanding [41, 48], data quality improvement [16, 59], data consistency maintenance [4, 21, 37, 51], and data provenance analysis [10, 18]. For table understanding, recovered relationships can reveal the latent structure of complex tables and help users interpret how columns are composed. For data quality and consistency, they can serve as executable constraints for detecting, explaining, and repairing inconsistent values, and can support automatic propagation of updates to dependent cells or columns. Moreover, they can aid provenance analysis by helping users trace how derived values are produced within or across tables. However, discovering such relationships directly from table data is non-trivial. Simply finding relationships that hold on the observed table is insufficient. Existing methods typically rely on observed-table signals such as exact satisfaction [3, 31], low violation rate [25, 36, 53], association strength [33, 57], or informationtheoretic dependency scores [44, 53, 56], but these signals alone cannot distinguish genuine relationships from spurious ones. Because a table is only a finite sample of a larger underlying data space, many candidates may appear to hold on one table instance merely by coincidence, redundancy, or limited domain coverage, even though they are not meaningful or generalizable. We refer to such coincidental, redundant, or incomplete candidates as spurious FRs. This spuriousness problem becomes even more severe in dirty-data settings, where a candidate may satisfy an approximate criterion despite omitting essential attributes. Example 1: Figures 1–3 illustrate that genuine and spurious FRs can coexist in the same table. Although these tables contain genuine FRs, a naive search may also produce several types of spurious candidates. For example, Figure 1 contains coincidental candidates such as B × F = E, which hold on the observed rows but are unlikely to reflect genuine relationships, as well as redundant candidates such as I × J + E = K, where E is extraneous and the real relationship is simply I × J = K. Similar spurious cases arise among string transformations in Figure 2, and Figure 3 shows spurious FRs such as L → M, which hold only because of limited value diversity in the observed table. These examples show that satisfying the observed table alone is insufficient for reliable FR discovery. □ Beyond these concrete examples, the key observation is that they all share the same functional nature: input values determine
Figure 1: An example spreadsheet table with arithmetic relationships (ARs).
Figure 2: An example spreadsheet table with string transformations (STs). output values. We therefore use the term functional relationships (FRs) to refer to such inter-column relationships in tables. This unified notion highlights a common reliability challenge shared across different relationship types: how to distinguish meaningful relationships from spurious ones using only table data. Despite its practical importance, FR discovery remains understudied as a unified problem. Accordingly, we formulate the problem as reliable functional relationship discovery. Since spurious FRs can arise from different causes, reliability cannot be assessed from a single observed-table signal alone. We therefore characterize FR reliability through four complementary criteria: accuracy, atomicity, stability, and integrity. Together, these criteria capture whether a candidate FR is well supported by the observed table, free of redundant input columns, non-trivial under value recombination, and, in dirty-data settings, not systematically missing essential attributes. Building on these reliability criteria, we propose Auto-Relate, a unified mine-then-verify framework for discovering reliable FRs by leveraging statistical tests. Auto-Relate first generates candidate FRs that satisfy the accuracy requirement, and then verifies the remaining reliability criteria through dedicated tests. A Minimality Test removes non-atomic candidates with redundant input columns. A Perturbation Test evaluates stability by randomly recombining participative values across rows and measuring how likely the candidate is to survive; genuine, non-trivial relationships should usually be destroyed by such recombination, whereas spurious ones tend to survive. In dirty-data settings, an additional Independence Test examines whether the violation pattern of a candidate depends on columns outside its participative column set, thereby filtering incomplete candidates with omitted attributes. We further develop efficient algorithms that exploit candidate-level pruning, deterministic lower bounds, and statistically guided early termination, enabling reliable predictions within seconds for interactive use cases.
• We introduce functional relationships (FRs), a unified notion for describing inter-column relationships in tables that subsumes arithmetic relationships (ARs), string transformations (STs), and functional dependencies (FDs) (Section 2). • We characterize the reliability of FRs through four complementary properties, i.e., accuracy, atomicity, stability, and integrity, and use them to guide the design of Auto-Relate (Section 3.1). • We develop Auto-Relate, a unified mine-then-verify framework for reliable FR discovery (Section 3.2) that first generates accurate candidate FRs and then verifies atomicity, stability, and integrity through a Minimality Test, a Perturbation Test, and an Independence Test, respectively (Section 3.3–Section 3.5). • We enhance Auto-Relate with three optimization strategies, including a group-by lower bound for early rejection, a closed-form speed-up strategy for AR-type FRs, and a binomial bound for statistically guided early termination, substantially improving efficiency while providing theoretical guarantees (Section 4). • We built the first large-scale benchmark suite, collected from 58,679 real-world spreadsheets and relational tables, containing 6,414 real functional relationships that cover all three types of FR. This allows us to systematically evaluate the FR discovery problem, and can be a useful resource for future research. (Section 5.1). • We conduct extensive experiments against 18 baselines across all FR types and data settings. The results show that Auto-Relate consistently outperforms all baselines, achieving an average PRAUC of 0.87 and improving over the strongest competing baseline by 59.0% on average across all settings (Section 5.2).
Contributions & Organizations. The main contributions and structure of this paper are summarized as follows.
We use the Functional Relationship (FR) to refer to the mapping between different columns in tabular data, illustrating how input
In addition, we discuss the related work in Section 6, and conclude this paper in Section 7.
2
2
PROBLEM DEFINITION
Figure 3: An example spreadsheet table with functional dependencies (FDs). values (one or more columns in the data) are transformed into output values (other columns). Formally, we define FRs as follows.
provided by ARs and STs. We therefore reserve FDs for the singlecolumn categorical setting, where 𝑓𝑟 is implicitly induced by the dependency: identical input values imply identical output values.
Definition 1 (Functional Relationships): Given a table 𝑇 with a set of columns 𝐶, and column subsets 𝑋, 𝑌 ⊆ 𝐶. A Functional Relationship Ψ = (𝑋, 𝑌, 𝑓𝑟 ) is composed of input columns set 𝑋 , output columns set 𝑌 and a mapping function 𝑓𝑟 . Let 𝑉𝑇 (𝑋 ) and 𝑉𝑇 (𝑌 ) denote the domains of 𝑋 and 𝑌 induced by table 𝑇 , respectively. For all 𝑥 ∈ 𝑉𝑇 (𝑋 ) 𝑎𝑛𝑑 𝑦 ∈ 𝑉𝑇 (𝑌 ), it holds that ( 1, if 𝑦 = 𝑓𝑟 (𝑥) Pr(𝑌 = 𝑦 | 𝑋 = 𝑥) = 0, otherwise
Example 2: Figures 1–3 illustrate the three types of FRs in real spreadsheet tables. In each figure, true-positive (TP) relationships are genuine, whereas false-positive (FP) relationships are spurious. • ARs (Figure 1): Ψ1 = ({𝐹, 𝐺 }, 𝐻, 𝐹 ×𝐺) captures that 𝐻 (Revenue) equals 𝐹 (Days) × 𝐺 (Rate), and Ψ2 = ({𝐻, 𝐾, 𝑁 }, 𝑂, 𝐻 + 𝐾 + 𝑁 ) captures that column 𝑂 (Total Revenue) is obtained by summing the three partial revenues in 𝐻 , 𝐾, and 𝑁 . • STs (Figure 2): Ψ3 = ({𝐵, 𝐶, 𝐷}, 𝐸, concat(𝐵, 𝐶, 𝐷)) concatenates 𝐵 (CITY), 𝐶 (STATE), and 𝐷 (LZIP) into 𝐸 (CTSTZIP), while Ψ4 = ({𝑁 }, 𝑂, extract(𝑁 , space)) extracts the first name in 𝑂 (FIRSTNAME) from the full name in 𝑁 (EXEC). • FDs (Figure 3): Ψ5 = ({𝐴}, 𝐵, 𝐴 → 𝐵) captures that 𝐵 (Quarter & Year) is determined by 𝐴 (Date), and Ψ6 = ({𝐹 }, 𝐺, 𝐹 → 𝐺) captures that 𝐺 (Region) is determined by 𝐹 (Country). □
A FR Ψ = (𝑋, 𝑌 , 𝑓𝑟 ) is non-trivial if 𝑌 ⊈ 𝑋 , and normalized if 𝑌 contains a single column. We denote 𝐶 Ψ = 𝑋 ∪𝑌 as the participative column set of FR Ψ. For two FRs Ψ1 and Ψ2 , they are said to be isomerous if 𝐶 Ψ1 = 𝐶 Ψ2 . In this paper, we consider only non-trivial, normalized FRs, as they suffice to infer all other FRs that hold on table 𝑇 . Semantics. Given a tuple 𝑡 ∈ 𝑇 , we say that 𝑡 satisfies an FR Ψ = (𝑋, 𝑌 , 𝑓𝑟 ), written as 𝑡 |= Ψ, if 𝑓𝑟 (𝑡 [𝑋 ]) = 𝑡 [𝑌 ]; otherwise, 𝑡 is said to violate Ψ, written as 𝑡 ̸ |= Ψ. For a table 𝑇 , we say that 𝑇 satisfies Ψ, denoted as 𝑇 |= Ψ, if 𝑡 |= Ψ for all 𝑡 ∈ 𝑇 . The set of observed violating tuples of Ψ on 𝑇 is vio𝑇 (Ψ) = {𝑡 ∈ 𝑇 | 𝑡 ̸ |= Ψ}, and the satisfaction ratio of Ψ on 𝑇 is sat𝑇 (Ψ) =
Problem statement. Our task is to discover reliable functional relationships (FRs) from a table. • Input: A table 𝑇 . • Output: A set 𝑅 of reliable FRs discovered from 𝑇 .
|{𝑡 ∈ 𝑇 | 𝑡 |= Ψ}| . |𝑇 |
To this end, we design a unified framework that first generates candidate FRs from 𝑇 and then evaluates the reliability of each candidate FR, thereby filtering out spurious FRs and returning a set 𝑅 of reliable FRs. We will formally define the reliability criteria for FRs and present the framework in Section 3.
Equivalently, 𝑇 |= Ψ iff sat𝑇 (Ψ) = 1, or iff vio𝑇 (Ψ) = ∅. Definition 2 (Approximate FRs): Given a threshold 𝜏 ∈ (0, 1], an FR Ψ = (𝑋, 𝑌 , 𝑓𝑟 ) is said to be 𝜏-approximate on 𝑇 if sat𝑇 (Ψ) ≥ 𝜏, i.e., |vio𝑇 (Ψ)| ≤ (1−𝜏)|𝑇 |. When 𝜏 = 1, a 𝜏-approximate FR reduces to an exact FR, i.e., 𝑇 |= Ψ. We next introduce three common types of FRs as follows. Arithmetic Relationships (ARs). When input and output columns are numeric, we refer to the FR as an AR, where the mapping function 𝑓𝑟 corresponds to an arithmetic formula involving operations such as addition, subtraction, multiplication, and division. String Transformations (STs). When input and output columns are textual, we refer to the FR as an ST, where 𝑓𝑟 corresponds to a string operation such as concatenation, substring extraction, or splitting [8, 29, 30, 34, 35, 68]. Functional Dependencies (FDs). When both the input and output are single categorical columns, we refer to the FR as an FD, a wellstudied form of consistency constraint [6, 12]. Although FDs can express deterministic relationships over numeric or textual values, they capture value determinacy rather than the mapping function
3
THE AUTO-RELATE FRAMEWORK
In this section, we present Auto-Relate, a unified mine-then-verify framework for discovering reliable FRs. We first introduce four reliability criteria for characterizing meaningful FRs (Section 3.1). We then provide an overview of the framework (Section 3.2) and detail its three reliability tests: the Minimality Test, the Perturbation Test, and the Independence Test (Sections 3.3–3.5).
3.1
Reliability Criteria for FRs
Auto-Relate aims to identify reliable FRs that are non-spurious and generalizable beyond a single table instance, rather than merely enumerating candidates. We characterize FR reliability through four properties: accuracy, atomicity, stability, and integrity, which capture complementary aspects of FR reliability and motivate the statistical tests in Auto-Relate. 3
Definition 3 (Accuracy): An FR Ψ = (𝑋, 𝑌, 𝑓𝑟 ) is said to be accurate on a table 𝑇 if 𝑇 |= Ψ, i.e., sat𝑇 (Ψ) = 1. In dirty-data settings, exact satisfaction may be too restrictive; we therefore relax this requirement and say that Ψ is 𝜏-accurate on 𝑇 if it is a 𝜏-approximate FR on 𝑇 , i.e., sat𝑇 (Ψ) ≥ 𝜏.
Algorithm 1: Auto-Relate Input : A table 𝑇 , a data setting 𝛿 ∈ {clean, dirty}, an accuracy threshold 𝜏, a significance threshold 𝛼, a perturbation threshold 𝜂, a maximum number of input columns (i.e., the search level) ℓmax . Output : A set 𝑅 of reliable FRs discovered from 𝑇 . 1 𝑅 ← ∅; 2 𝑅prune ← ∅; 3 for 𝑖 ← 1 to ℓmax do 4 𝑅cand ← CandidateGeneration(𝑇 , 𝛿, 𝜏, 𝑖); 5 if 𝑅cand = ∅ then continue; 6 foreach Ψ ∈ 𝑅cand do 7 if not MinimalityTest(Ψ, 𝑅prune ) then 8 continue
Definition 4 (Atomicity): An FR Ψ = (𝑋, 𝑌, 𝑓𝑟 ) is said to be atomic on a table 𝑇 if there exists no other FR Ψ′ = (𝑋 ′, 𝑌, 𝑓𝑟′ ) such that 𝑋 ′ ⊆ 𝑋 and Ψ is accurate on 𝑇 . That is, no proper subset of the input columns 𝑋 of Ψ can determine the same output columns 𝑌 on 𝑇 . Definition 5 (Stability): An FR Ψ = (𝑋, 𝑌, 𝑓𝑟 ) is said to be stable on a table 𝑇 if there exists at least one violating combination in the induced domain, i.e., ∃𝑥 ∈ 𝑉𝑇 (𝑋 ), ∃𝑦 ∈ 𝑉𝑇 (𝑌 ) s.t. 𝑦 ≠ 𝑓𝑟 (𝑥). Equivalently, the valid mappings of 𝑓𝑟 are a strict subset of the Cartesian product 𝑉𝑇 (𝑋 ) × 𝑉𝑇 (𝑌 ).
10
𝑅prune ← 𝑅prune ∪ {Ψ}; 𝑝 pert ← PerturbationTest(𝑇 , Ψ, 𝜂); if 𝑝 pert ≤ 𝜂 then 𝑅 ← 𝑅 ∪ {Ψ};
11 12 13 14
Definition 7 (Reliability): An FR is said to be reliable if it satisfies accuracy, atomicity, stability, and integrity.
15
Example 3: Continuing with FRs in Example 2, we illustrate why observed-table accuracy alone is insufficient. The genuine FR Ψ1 = ({𝐹, 𝐺 }, 𝐻, 𝐹 × 𝐺) is accurate on the table in Figure 1 and is stable because random recombination of 𝐹 , 𝐺, and 𝐻 will usually destroy the equality 𝐻 = 𝐹 × 𝐺. By contrast, Ψ1+ = ({𝐵, 𝐹, 𝐺 }, 𝐻, 𝐹 × 𝐺 + 𝐵) is also accurate but violates atomicity, since the smaller FR Ψ1 already determines 𝐻 and 𝐵 is redundant. Another candidate, Ψcoin = ({𝐵, 𝐶}, 𝐸, 𝐵 ×𝐶), is unstable: 𝐵, 𝐶, and 𝐸 are sparse binary columns, so most tuples trivially satisfy 𝐵×𝐶 = 𝐸 = 0 and Ψcoin often survives perturbation. Finally, in a dirty-data variant of Figure 1, the incomplete candidate Ψ2− = ({𝐻, 𝐾 }, 𝑂, 𝐻 +𝐾) may still be 𝜏-accurate, but its violations occur on rows where the omitted term 𝑁 is nonzero. This dependence on 𝑁 indicates that Ψ2− violates integrity. □
return 𝑅;
candidates maintained across levels for atomicity-based pruning of subsequent candidates (lines 1–2). It then proceeds level by level from 𝑖 = 1 to ℓmax , interleaving candidate generation and reliability verification at each level (line 3–14). At each level 𝑖, Auto-Relate invokes CandidateGeneration to obtain the candidate FR set 𝑅cand (line 4); if no candidates are produced, the level is skipped (line 5). For each candidate Ψ ∈ 𝑅cand (line 6), it first applies MinimalityTest to check whether 𝑅prune already contains a candidate whose input column set is a proper subset of that of Ψ (line 7); if so, Ψ is non-atomic and discarded. In the dirty-data setting, the surviving candidate is further checked via IndependenceTest (lines 9–10) for integrity; a candidate that fails this test is rejected as incomplete. Each candidate that passes the above filters is added to 𝑅prune (line 11), so that it can prune supersets at subsequent levels. Finally, PerturbationTest is applied to compute the perturbation score 𝑝 pert (line 12); if 𝑝 pert ≤ 𝜂, the candidate is admitted into the reliable FR set 𝑅 (lines 13–14). After all levels have been processed, Auto-Relate returns 𝑅 as the set of reliable FRs discovered from 𝑇 (line 15). Complexity. Let 𝑅𝐶 be the set of all candidate FRs generated across all levels. For a candidate FR Ψ, let Tmt (Ψ), Tit (Ψ), and Tpt (Ψ) denote the time of MinimalityTest, IndependenceTest, and PerturbationTest, respectively. Then the total running time of Auto-Relate is the Í candidate-generation cost plus at most 𝑂 ( Ψ∈𝑅𝐶 (Tmt (Ψ) + 1[𝛿 = dirty] ·Tit (Ψ) +Tpt (Ψ))). Note that this is the worst-case complexity; in practice, our algorithm is much faster by effective pruning and optimization strategies introduced in Section 4.
Among these criteria, integrity is meaningful primarily in dirtydata settings, where an approximately accurate candidate may omit essential attributes. In clean-data settings, accurate candidates have no observed violations from which such omissions can be diagnosed. We next describe how Auto-Relate operationalizes these criteria.
3.2
if 𝛿 = dirty then if not IndependenceTest(𝑇 , Ψ, 𝛼) then continue;
9
Definition 6 (Integrity): Let 𝑍 = 𝐶 \ 𝐶 Ψ be the set of nonparticipative columns of an FR Ψ = (𝑋, 𝑌, 𝑓𝑟 ) in a table 𝑇 with a set of columns 𝐶. For a tuple 𝑡 sampled uniformly at random from 𝑇 , let 𝐼 Ψ (𝑡) = 1[𝑡 ̸ |= Ψ] denote the violation indicator of Ψ. We say that Ψ satisfies integrity if 𝐼 Ψ (𝑡) ⊥ ⊥ 𝑡 [𝑐] for every 𝑐 ∈ 𝑍 . That is, the violation pattern of Ψ is independent of every non-participative column.
Overview of Auto-Relate
Given an input table 𝑇 , Auto-Relate aims to discover a set of reliable FRs from 𝑇 . It mainly consists of two stages: candidate generation and reliability verification. The candidate-generation stage enumerates candidate FRs that satisfy the accuracy requirement, while the reliability-verification stage further examines these candidates through three tests: the MinimalityTest for atomicity (Section 3.3), the PerturbationTest for stability (Section 3.4), and the IndependenceTest for integrity in the dirty-data setting (Section 3.5).
3.3
Algorithm. As shown in Algorithm 1, Auto-Relate operates in a level-wise manner. It first initializes two sets: (i) 𝑅, the set of reliable FRs to be returned, and (ii) 𝑅prune , the set of previously retained
Minimality Test
The Minimality Test is the first verification step in Algorithm 1. It enforces the atomicity criterion by pruning redundant candidates. 4
Recall from Definition 4 that a candidate Ψ = (𝑋, 𝑌, 𝑓𝑟 ) is nonatomic if there exists another FR Ψ′ = (𝑋 ′, 𝑌, 𝑓𝑟′ ) with 𝑋 ′ ⊂ 𝑋 and sat𝑇 (Ψ′ ) ≥ 𝜏. In this case, 𝑌 can already be determined with sufficient accuracy by a strict subset of 𝑋 , and thus Ψ can be discarded. To operationalize this idea, Auto-Relate performs candidate enumeration in a level-wise manner, processing all candidates with |𝑋 | = 𝑖 before those with |𝑋 | = 𝑖 + 1. For each candidate Ψ = (𝑋, 𝑌 , 𝑓𝑟 ) at level 𝑖, the MinimalityTest checks whether the pruning set 𝑅prune already contains a previously retained candidate Ψ′ = (𝑋 ′, 𝑌 , 𝑓𝑟′ ) with the same output column 𝑌 and a strict subset of input columns, i.e., 𝑋 ′ ⊂ 𝑋 . If so, Ψ is immediately pruned and does not enter the remaining verification procedures. Since pruning decisions at earlier levels propagate to later levels, this test can eliminate many redundant supersets, especially on wide tables.
Algorithm 2: Perturbation Test Input : A table 𝑇 , a candidate FR Ψ, a perturbation threshold 𝜂, maximum iterations 𝑛 max , a confidence 𝑧-score, and checking interval 𝛽. Output : An estimated perturbation score 𝑝 pert . 1 𝐶 Ψ ← the participative column set of Ψ; 2 𝐵 group ← the group-by lower bound computed from table 𝑇 and FR Ψ; 3 if 𝐵 group > 𝜂 then 4 return 𝐵 group 5 𝑛𝑠 ← 0; 6 𝑛 ← 0;
for 𝑖 ← 1 to 𝑛 max do (𝑟 𝑎 , 𝑟𝑏 ) ← randomly sample two distinct rows from 𝑇 ; 9 𝐶 ′ ← a random non-empty subset of 𝐶 Ψ ; 10 (𝑟 𝑎′ , 𝑟𝑏′ ) ← perturb(𝑟 𝑎 , 𝑟𝑏 , 𝐶 ′ ); 11 if 𝑟 𝑎′ satisfies Ψ and 𝑟𝑏′ satisfies Ψ then 12 𝑛𝑠 ← 𝑛𝑠 + 1; 7
8
3.4
Perturbation Test
The perturbation test is designed to evaluate the stability of a candidate FR Ψ by measuring how likely it is to remain valid under random cross-row perturbations of its participative values. If Ψ captures a genuine, non-trivial relationship, then randomly recombining observed values across tuples should often destroy it. By contrast, spurious candidates caused by low domain diversity or coincidental patterns tend to survive such perturbations more easily. Let Ψ = (𝑋, 𝑌 , 𝑓𝑟 ) be a candidate FR on a table 𝑇 , and let 𝐶 Ψ = 𝑋 ∪ 𝑌 denote its participative column set. A single perturbation trial uniformly samples two distinct rows 𝑟 𝑎 , 𝑟𝑏 from 𝑇 without replacement, uniformly samples a non-empty subset 𝐶 ′ ⊆ 𝐶 Ψ , swaps the values of 𝐶 ′ between 𝑟 𝑎 and 𝑟𝑏 to produce perturbed rows 𝑟 𝑎′ and 𝑟𝑏′ , and checks whether both 𝑟 𝑎′ and 𝑟𝑏′ still satisfy Ψ. If so, we say that Ψ survives the trial. We define the perturbation score 𝑝 pert of Ψ, denoted by 𝑝 pert as the probability that Ψ survives a random perturbation trial:
𝑛 ← 𝑛 + 1; if mod(𝑛, 𝛽) = 0 then 𝐵 lower, 𝐵 upper ← wilson_interval(𝑛, 𝑛𝑠 , 𝑧); if 𝐵 lower > 𝜂 or 𝐵 upper < 𝜂 then break;
13 14 15 16 17
18 19
𝑝 pert ← 𝑛𝑠 /𝑛; return 𝑝 pert ;
cost of 𝑂 (|𝑇 | · 2 |𝐶 Ψ | ) per candidate, but when 𝐵 group > 𝜂, the sampling loop is bypassed entirely. For the remaining candidates, Wilson-interval early termination often stops sampling after only 𝑛 ∗ ≪ 𝑛 max iterations in practice, yielding an effective per-candidate cost of 𝑂 (|𝑇 | · 2 |𝐶 Ψ | + 𝑛 ∗ · |𝐶 Ψ |).
𝑝 pert = Pr[Ψ survives a random perturbation trial]. In practice, 𝑝 pert is estimated by the fraction of survivals over repeated trials. A low score indicates that Ψ is sensitive to random recombination and is therefore more likely to reflect a genuine relationship, whereas a high score suggests Ψ is spurious. We accept Ψ as stable only if 𝑝 pert ≤ 𝜂, where 𝜂 is a user-specified threshold.
Example 4: Consider the genuine FR Ψ1 = ({𝐹, 𝐺 }, 𝐻, 𝐹 × 𝐺) and the spurious candidate Ψcoin = ({𝐵, 𝐶}, 𝐸, 𝐵 × 𝐶) from Example 3. For Ψ1 , swapping the value of column 𝐺 between two sampled rows in Figure 1 typically violates the equality 𝐻 = 𝐹 × 𝐺, yielding a low perturbation score. By contrast, Ψcoin often survives perturbation because 𝐵, 𝐶, and 𝐸 are sparse binary columns and many tuples coincidentally satisfy 𝐵 × 𝐶 = 𝐸 = 0. □
Algorithm. An exact computation of 𝑝 pert requires enumerating all pairs of rows in 𝑇 together with all 2 |𝐶 Ψ | − 1 non-empty column subsets of 𝐶 Ψ , which is computationally prohibitive. We therefore adopt a sampling-based approximation to estimate 𝑝 pert , as shown in Algorithm 2. To further improve efficiency, Auto-Relate incorporates two optimization strategies: a group-by lower bound that enables exact early rejection before sampling (lines 2–4), and a binomial bound based on the Wilson confidence interval that enables statistically guided early termination during sampling (lines 14–17). Their details and theoretical guarantees are presented in Section 4.
3.5
Independence Test
In the dirty-data setting, a candidate FR Ψ may hold on most rows while violating a few due to noise. A natural approach is to discard the violation rows and apply the Perturbation Test on the remaining clean rows. However, this removes precisely the rows that carry diagnostic information; violations may be systematically caused by an omitted column, and removing them eliminates the evidence needed to detect such incompleteness. For example, removing the violation rows of Ψ2− in Example 3 would eliminate the rows where 𝑁 ≠ 0, causing it to incorrectly survive the subsequent Perturbation Test. To address this issue, we introduce the Independence Test, which verifies the integrity of a candidate FR before the Perturbation Test. Recall from Definition 6 that integrity requires the violation pattern
Complexity. An exact computation of the perturbation score 𝑝 pert requires enumerating all |𝑇2 | row pairs and all 2 |𝐶 Ψ | − 1 non-empty column subsets, yielding 𝑂 (|𝑇 | 2 · 2 |𝐶 Ψ | · |𝐶 Ψ |) per candidate, which is prohibitive even for moderately sized tables. The sampling-based Algorithm 2 performs at most 𝑛 max iterations in the worst case, each costing 𝑂 (|𝐶 Ψ |) for the perturbation and verification. Computing the group-by lower bound incurs an additional pre-computation 5
of Ψ to be independent of all non-participative columns 𝑍 = 𝐶 \ 𝐶 Ψ . Intuitively, if the violations of Ψ are systematically correlated with any column 𝑐 ′ ∈ 𝑍 , then Ψ violates integrity; the output column is not solely determined by the declared input columns 𝑋 , but is also influenced by 𝑐 ′ , which should have been included in 𝑋 . Such candidates are therefore regarded as unreliable and are discarded. Let Ψ = (𝑋, 𝑌 , 𝑓𝑟 ) be a candidate FR on table 𝑇 , with 𝐶 Ψ = 𝑋 ∪ 𝑌 . For each tuple 𝑡 ∈ 𝑇 , we define the violation indicator
Algorithm 3: Independence Test Input : A table 𝑇 , a candidate FR Ψ, and a significance threshold 𝛼. Output : A Boolean decision indicating whether Ψ passes the Independence Test. 1 IΨ ← the violation indicator vector of Ψ on 𝑇 ; 2 𝐶 Ψ ← the participative column set of Ψ; 3 𝐶 irr ← 𝐶 \ 𝐶 Ψ , where 𝐶 is the column set of 𝑇 ; ′ 4 foreach 𝑐 ∈ 𝐶 irr do 5 construct the contingency table between IΨ and 𝑐 ′ ; 6 𝑝 ← the 𝑝-value of the chi-square test of independence on the contingency table; 7 if 𝑝 ≤ 𝛼 then 8 return False
𝐼 Ψ (𝑡) = 1[𝑡 ̸ |= Ψ], which equals 1 if 𝑡 violates Ψ and 0 otherwise. Let IΨ = (𝐼 Ψ (𝑡))𝑡 ∈𝑇 denote the indicator vector over all tuples in 𝑇 . For every nonparticipative column 𝑐 ′ ∈ 𝐶 \ 𝐶 Ψ , the Independence Test examines whether the binary variable 𝐼 Ψ (𝑡) is statistically independent of the observed value 𝑡 [𝑐 ′ ]. Formally, for each such column 𝑐 ′ , we test ′
𝐻 0𝑐 : 𝐼 Ψ (𝑡) ⊥⊥ 𝑡 [𝑐 ′ ]
against
′
𝐻 1𝑐 : 𝐼 Ψ (𝑡) ̸⊥ ⊥ 𝑡 [𝑐 ′ ].
9
Empirically, this is implemented by constructing the contingency table between IΨ and 𝑐 ′ and computing the corresponding 𝑝-value via a chi-square test of independence [54]. If any 𝑝-value is no greater than the significance threshold 𝛼, we reject Ψ as violating integrity; otherwise, Ψ passes the Independence Test. Algorithm. Algorithm 3 summarizes the Independence Test procedure. It first computes the violation indicator vector IΨ , where 𝐼 Ψ (𝑡) = 1 if tuple 𝑡 violates Ψ and 0 otherwise (line 1). It then iterates over each non-participative column 𝑐 ′ ∈ 𝐶 irr (line 4): for each such column, it constructs the contingency table between 𝑐 ′ and IΨ (line 5) and computes the corresponding 𝑝-value via a chi-square test of independence [54] (line 6). If any 𝑝-value falls below the significance threshold 𝛼, the candidate FR Ψ is immediately rejected as violating integrity and the algorithm returns False (lines 7–8); if no such column is found, Ψ passes the Independence Test and the algorithm returns True (line 9). Complexity. Let 𝐶 irr = 𝐶 \ 𝐶 Ψ be the set of non-participative columns. Computing the violation indicator vector IΨ costs 𝑂 (|𝑇 | · |𝐶 Ψ |). For each 𝑐 ′ ∈ 𝐶 irr , constructing the contingency table requires a single pass over 𝑇 in 𝑂 (|𝑇 |), and the chi-square test costs 𝑂 (𝑑𝑐 ′ ) where 𝑑𝑐 ′ is the number of distinct values in 𝑐 ′ . The total cost is therefore 𝑂 (|𝑇 | · |𝐶 Ψ | + |𝐶 irr | · (|𝑇 | + max𝑐 ′ 𝑑𝑐 ′ )) = 𝑂 (|𝑇 | · |𝐶 |), since |𝐶 Ψ |, |𝐶 irr | ≤ |𝐶 | and 𝑑𝑐 ′ ≤ |𝑇 |. Note that the Independence Test is invoked only in the dirty-data setting; in the clean-data setting, IΨ is uniformly zero and the test is skipped.
4
return True
the sampling loop by exploiting their expression-tree structure (Section 4.2). Finally, we develop a binomial bound that enables statistically guided early termination during sampling once the perturbation score can be determined with statistical confidence (Section 4.3). Together, these strategies substantially reduce the practical cost of perturbation-based verification while preserving the correctness of deterministic pruning and providing approximate statistical error control for early termination.
4.1
Group-by Bound
We first introduce a deterministic group-by lower bound on the perturbation score of a candidate FR Ψ = (𝑋, 𝑌, 𝑓𝑟 ). This bound enables exact rejection before the sampling loop begins. The key observation is straightforward. In a perturbation trial, two rows 𝑟 𝑎 and 𝑟𝑏 are sampled uniformly at random from𝑇 without replacement, and the values of a randomly selected non-empty subset 𝐶 ′ ⊆ 𝐶 Ψ are swapped between them. If the swapped values are identical across 𝑟 𝑎 and 𝑟𝑏 for every column in 𝐶 ′ , i.e., 𝑟 𝑎 [𝑐] = 𝑟𝑏 [𝑐] for all 𝑐 ∈ 𝐶 ′ , then the perturbed rows 𝑟 𝑎′ and 𝑟𝑏′ remain unchanged, and the FR trivially survives the perturbation. Therefore, the perturbation score 𝑝 pert is at least as large as the probability of such an identity-swap event. For a non-empty subset 𝐶 ′ ⊆ 𝐶 Ψ , let v1, . . . , v𝑚 be the distinct joint values observed on 𝐶 ′ , and let 𝑛𝑖 be the number of rows sharing joint value v𝑖 . When two rows are sampled uniformly at random without replacement, the probability of an identity swap on 𝐶 ′ is
OPTIMIZATION STRATEGIES
The reliability verification stage of Auto-Relate can be computationally expensive. As analyzed in Sections 3.4 and 3.5, the Independence Test runs in 𝑂 (|𝑇 | · |𝐶 |) time per candidate, which is linear in the table size and inexpensive in practice. The Perturba tion Test, however, requires enumerating all |𝑇2 | row pairs and all 2 |𝐶 Ψ | − 1 non-empty column subsets in its exact form, yielding a per-candidate complexity of 𝑂 (|𝑇 | 2 · 2 |𝐶 Ψ | ), which is prohibitive even for moderately sized tables. To address these bottlenecks, we develop three complementary optimization strategies for the PerturbationTest. We first introduce a group-by bound that rejects candidate FRs before sampling begins (Section 4.1). We then propose a closed-form speed-up strategy for AR-type FRs that reduces the per-iteration verification cost within
𝑞𝐶 ′ =
𝑚 ∑︁ 𝑛𝑖
|𝑇 | 𝑖=1
·
𝑛𝑖 − 1 . |𝑇 | − 1
(1)
Recall that in Algorithm 2, each column in 𝐶 Ψ is independently included in 𝐶 ′ with probability 1/2, conditioned on 𝐶 ′ being nonempty. This is equivalent to sampling 𝐶 ′ uniformly at random from the 2 |𝐶 Ψ | − 1 non-empty subsets of 𝐶 Ψ . Accordingly, we define the group-by lower bound 𝐵 group as the expected identity-swap probability under this distribution: ∑︁ 1 𝐵 group = |𝐶 | 𝑞𝐶 ′ . (2) 2 Ψ − 1 ∅≠𝐶 ′ ⊆𝐶 Ψ
6
Lemma 4.1 (Group-by Lower Bound): In the clean-data setting, let 𝑝 pert denote the perturbation score of a candidate FR Ψ on a table 𝑇 , computed by Algorithm 2. Then 𝑝 pert ≥ 𝐵 group . □
core value, i.e., 𝐻𝑟𝑎 + 𝐾𝑟𝑎 = 𝐻𝑟𝑏 + 𝐾𝑟𝑏 , which is both necessary and sufficient for Ψ2 to remain satisfied after swapping 𝐻 and 𝐾 between 𝑟 𝑎 and 𝑟𝑏 . □
Proof: Fix any non-empty subset 𝐶 ′ ⊆ 𝐶 Ψ . Let 𝐼 denote the identityswap event that 𝑟 𝑎 [𝑐] = 𝑟𝑏 [𝑐] for every 𝑐 ∈ 𝐶 ′ , and let 𝑆 denote the event that Ψ survives the perturbation trial. Under event 𝐼 , swapping the values on 𝐶 ′ leaves both rows unchanged, i.e., 𝑟 𝑎′ = 𝑟 𝑎 and 𝑟𝑏′ = 𝑟𝑏 . In the clean-data setting, both 𝑟 𝑎 and 𝑟𝑏 satisfy Ψ before perturbation, and since they remain unchanged, Ψ is also satisfied after perturbation. Hence, 𝐼 ⊆ 𝑆, and therefore Pr[𝑆 |𝐶 ′ ] ≥ Pr[𝐼 |𝐶 ′ ] = 𝑞𝐶 ′ . Taking expectation over the uniform choice of 𝐶 ′ , we have ∑︁ 1 𝑝 pert = Pr[𝑆] = |𝐶 | Pr[𝑆 | 𝐶 ′ ] 2 Ψ − 1 ∅≠𝐶 ′ ⊆𝐶 Ψ ∑︁ 1 ≥ |𝐶 | 𝑞𝐶 ′ = 𝐵 group . □ 2 Ψ − 1 ∅≠𝐶 ′ ⊆𝐶
4.3
Ψ
Therefore, if 𝐵 group > 𝜂, the candidate FR can be safely rejected without entering the sampling loop (Lines 2–4 of Algorithm 2). Dirty-data extension. In the dirty-data setting, a candidate FR is allowed to have a small number of violations after passing the 𝜏-accuracy filter. To apply the group-by bound in this setting, we restrict attention to the subset of rows on which Ψ holds, i.e., 𝑇Ψ+ = {𝑡 ∈ 𝑇 : 𝑡 |= Ψ}. Since every identity swap on 𝑇Ψ+ leaves the sampled rows unchanged and those rows satisfy Ψ before perturbation, the same argument as in Lemma 4.1 yields a valid lower bound for the perturbation score over initially satisfied rows. Accordingly, in the + dirty-data setting, we use 𝐵 group = 𝐵 group (𝑇Ψ+ ).
4.2
Binomial Bound
When the group-by lower bound does not suffice to reject a candidate FR, Algorithm 2 enters the sampling loop. Each perturbation trial yields a Bernoulli outcome. If the number of trials were fixed in advance at 𝑛, then the cumulative number of survivals 𝑛𝑠 would follow a Binomial(𝑛, 𝑝 pert ) distribution, where 𝑝 pert denotes the true perturbation score. This motivates the use of the Wilson score interval as a practical confidence interval for 𝑝 pert . In Algorithm 2, at each checkpoint with 𝑛 completed trials and 𝑛𝑠 observed survivals, we compute the Wilson interval for 𝑝 pert and terminate sampling early once the interval lies entirely on one side of the threshold 𝜂. We emphasize, however, that because the interval is repeatedly monitored during sampling and the stopping time is data-dependent, the resulting error control should be interpreted as approximate rather than as an exact finite-sample sequential guarantee. Specifically, we adopt the Wilson score interval [66] rather than the Wald interval, because it is known to exhibit substantially better finite-sample performance, especially for small 𝑛 or extreme values of 𝑝 pert . At any fixed checkpoint after 𝑛 trials with 𝑛𝑠 successes, the nominal (1 − 𝛾) confidence interval [𝐵 lower, 𝐵 upper ] for 𝑝 pert is √︁ 𝑛𝑠 + 𝑧 2 /2 𝑧 𝑛𝑠 (𝑛 − 𝑛𝑠 )/𝑛 + 𝑧 2 /4 − , (3) 𝐵 lower = 𝑛 + 𝑧2 𝑛 + 𝑧2 √︁ 𝑛𝑠 + 𝑧 2 /2 𝑧 𝑛𝑠 (𝑛 − 𝑛𝑠 )/𝑛 + 𝑧 2 /4 𝐵 upper = + , (4) 𝑛 + 𝑧2 𝑛 + 𝑧2 where 𝑧 = Φ−1 (1 − 𝛾/2) is the standard normal critical value for a nominal two-sided confidence level of 1 − 𝛾. Based on this interval, the sampling loop in Algorithm 2 terminates early if 𝐵 lower > 𝜂 or 𝐵 upper < 𝜂 (lines 14–17). That is, early termination occurs once the entire Wilson interval lies on one side of the threshold 𝜂. To reduce the overhead of interval evaluation, the Wilson interval is computed once every 𝛽 iterations rather than after every perturbation trial.
Closed-form Speed-up
For AR-type FRs that enter the sampling loop, we additionally reduce the per-trial verification cost by exploiting the expressiontree representation of the arithmetic formula. Specifically, let Ψ = (𝑋, 𝑌, 𝑓𝑟 ) be an AR candidate whose formula 𝑓𝑟 is represented as a binary expression tree. When the sampled perturbation set 𝐶 ′ coincides with the set of leaf columns in the subtree rooted at some internal binary operator node 𝑢, we refer to the value of that sub-expression as the perturbation core. In this case, swapping all columns in 𝐶 ′ between two sampled rows only affects the perturbation core while leaving the rest of the expression unchanged. Therefore, for such perturbations, the trial outcome can be determined by checking whether the perturbation core remains unchanged, rather than re-evaluating the entire expression tree on the perturbed rows. This optimization is specific to AR-type FRs and is applied only when the sampled perturbation set matches the leaf set of some subtree in the expression tree.
Lemma 4.2 (Binomial Bound): Let 𝑝 pert denote the true perturbation score of a candidate FR Ψ. If Algorithm 2 terminates early because 𝐵 lower > 𝜂 or 𝐵 upper < 𝜂, then the resulting threshold-based decision can disagree with the exact decision based on 𝑝 pert only if 𝑝 pert ∉ [𝐵 lower, 𝐵 upper ]. □ Proof: The early termination is triggered only when the Wilson interval at the stopping checkpoint [𝐵 lower, 𝐵 upper ] lies strictly on one side of the threshold 𝜂, i.e., when 𝐵 lower > 𝜂 or 𝐵 upper < 𝜂. If 𝐵 upper < 𝜂 and 𝑝 pert ∈ [𝐵 lower, 𝐵 upper ], then 𝑝 pert < 𝜂, so the resulting threshold-based decision agrees with the exact decision based on 𝑝 pert . Similarly, if 𝐵 lower > 𝜂 and 𝑝 pert ∈ [𝐵 lower, 𝐵 upper ], then 𝑝 pert > 𝜂, so the two decisions also agree. Therefore, a disagreement can occur only if 𝑝 pert ∉ [𝐵 lower, 𝐵 upper ], that is,
Example 5: Consider the genuine AR Ψ2 = ({𝐻, 𝐾, 𝑁 }, 𝑂, 𝐻 + 𝐾 + 𝑁 ) in Example 2 and a perturbation trial in which the sampled column subset is 𝐶 ′ = {𝐻, 𝐾 }. In the expression tree of Ψ2 , the columns 𝐻 and 𝐾 form the sub-expression 𝐻 + 𝐾, which serves as the perturbation core. Since the remaining part of the expression, namely 𝑁 , is unchanged in this trial, the Closed-form Speed-up does not need to recompute the full expression 𝐻 + 𝐾 + 𝑁 on the perturbed tuples. Instead, provided both sampled tuples satisfy Ψ2 before perturbation, it only checks whether they share the same
{decision error} ⊆ {𝑝 pert ∉ [𝐵 lower, 𝐵 upper ]}. Taking probabilities on both sides gives Pr(decision error) ≤ Pr(𝑝 pert ∉ [𝐵 lower, 𝐵 upper ]). 7
□
Table 1: Statistics of the Real benchmark suite
Consequently, any early-termination decision can be erroneous only if the Wilson interval at the termination checkpoint fails to cover 𝑝 pert . Thus, the Binomial Bound reduces the practical cost of the Perturbation Test by terminating sampling once the decision relative to 𝜂 becomes clear from the monitored Wilson interval, while this early-termination criterion should be interpreted as a practical approximation rather than an exact sequential coverage guarantee under repeated monitoring.
5
Dataset Real-AR Real-ST Real-FD
#Rows (Min, Avg, Max) (28, 578, 16961) (5, 98, 23005) (107, 25688, 717321)
#Cols (Min, Avg, Max) (3, 12, 400) (32, 113, 500) (4, 22, 333)
#Pos. FRs 966 1938 3510
#Neg. FRs 8102 294253 5579
Baselines. We compared Auto-Relate against a comprehensive set of 18 baselines and ranking measures from 12 groups. (1) ExplainDa-V [63], which explains dataset-version changes using data transformations; we adapt its conciseness and concentration criteria to score candidate FRs. (2) GPT-5 [50], a large language model prompted with column names and sampled rows in a few-shot incontext learning setting to verify FRs. (3) Chi-Squared (CS) [33], a classical test of independence. (4) Mutual Information (MI) [14], an information-theoretic dependence measure. (5) Fraction of Information (FI) [13, 25], an information-theoretic measure that quantifies the relative reduction in uncertainty about the RHS given the LHS. (6) Reliable FI (RFI+ , RFI′+ ) [44, 53], two bias-corrected FI-based variants. (7) Smoothed MI (SMI) [56], an MI variant with Laplace smoothing. (8) Co-occurrence (𝜌) [33], the ratio of distinct LHS values to distinct (LHS, RHS) value pairs. (9) 𝑔1 -based measures (𝑔1 , 𝑔𝑠1 , 𝑔𝑠+ 1 ) [25, 36, 53], based on the fraction of violating tuple pairs and closely related variants. (10) Violating row ratio (𝑔2 ) [36, 53], the fraction of tuples involved in violations. (11) Row-removal ratio (𝑔3 , 𝑔3′ ) [25, 36, 53], the minimum fraction of rows whose removal eliminates all violations. (12) Probabilistic dependency (𝑝 dep ) and its normalized variants (𝜇 + , 𝜏) [26, 57], based on the conditional probability that two randomly sampled tuples agree on the LHS also agree on the RHS. For quality comparison, all methods were evaluated on the same candidate FR pool in each benchmark. Each benchmark provided a fixed set of positive and negative FR candidates, and each method scored, ranked, or filtered these candidates independently.
EXPERIMENTS
Using real-life data, we experimentally evaluated the (1) effectiveness and (2) efficiency of the proposed Auto-Relate of discovering reliable FRs for (a) different types of FRs and (b) clean and dirty data.
5.1
#Tables 2539 55766 374
Experimental Settings
Datasets. Since benchmark datasets for AR and ST discovery are scarce, and existing FD benchmarks are limited in both scale and diversity, we collaborated with Microsoft Research to construct a new benchmark suite, Real, based on a large collection of real-world Excel spreadsheets and tabular data from Auto-Pipeline [68]. The suite supports the evaluation of all three FR types considered in this paper, namely ARs, STs, and FDs. As shown in Table 1, we summarized the statistics of the datasets, including the number of tables, the row and column statistics per table, and the number of positive and negative FRs. • Real-AR contains 2,539 tables, with 28–16,961 rows and 3–400 columns per table, yielding 966 positive and 8,102 negative AR candidates. Positive samples correspond to ground-truth formulas recorded in original spreadsheets, while negative ones are spurious candidates with observed violations on the source tables. • Real-ST contains 55,766 tables, with 5–23,005 rows and 32–500 columns per table, yielding 1,938 positive and 294,253 negative ST candidates. Positive samples are verified string-transformation formulas, while negative ones are spurious candidates whose output column is a string column inserted from an unrelated table. • Real-FD contains 374 tables, with 107–717,321 rows and 4–333 columns per table, yielding 3,510 positive and 5,579 negative FD candidates. Positive samples include both reliable and approximate FDs extracted from the data, while negative samples comprise spurious candidates with substantial observed violations and manually added unreliable dependencies.
Metrics. We evaluated the quality of discovered FRs using precision, recall, and F1-score. Here, precision is the fraction of predicted positives that are correct, and recall is the fraction of true positives that are successfully identified. Formally, 𝑃=
TP , TP + FP
𝑅=
TP , TP + FN
𝐹1 =
2𝑃𝑅 . 𝑃 +𝑅
To summarize performance over all score thresholds, we further reported PR-AUC (Precision-Recall Area Under the Curve) [58], which measures the area under the precision–recall curve, where a larger value indicates better overall performance.
For evaluation, we derived both a clean-data setting and a dirtydata setting from the underlying source tables. In the clean-data setting, violating rows of negative candidate FRs were removed so that both positive and negative candidates hold exactly on the resulting tables, making the discrimination task more challenging. In the dirty-data setting, we injected 10% random noise into the source tables to simulate realistic data errors. In addition, we included RWD [53], which contains 10 tables and 126 manually labeled FD relationships, for further validating effectiveness. Unlike commonly used FD discovery benchmarks that are primarily designed for evaluating enumeration efficiency, RWD provides ground-truth design FDs and is therefore suitable for evaluating candidate-level reliability discrimination.
Configuration. All experiments were conducted on a server running Ubuntu 20.04 with an Intel(R) Xeon(R) Platinum 8370C CPU (2.80 GHz), 96 GB RAM, and a 1.8 TB SSD. For Auto-Relate, we set the perturbation threshold to 𝜂 = 0.5, the significance threshold in the Independence Test to 𝛼 = 0.05, the maximum discovery level ℓmax = 4, and the accuracy threshold to 𝜏 = 1.0 in the clean-data setting and 𝜏 = 0.8 in the dirty-data setting. To exploit the withinlevel independence of candidates, we set the degree of parallelism to the number of CPU cores. All baselines were run with the default configurations reported in their original papers. 8
Table 2: Quality comparison. Each cell reports PR-AUC (precision, recall, F1-score); the best PR-AUC per setting is in bold Methods Auto-Relate Explain-Da-V GPT-5 CS MI FI RFI+ RFI′+ SMI 𝑝𝑑𝑒𝑝 𝜇+ 𝜏 𝜌 𝑔1 𝑔𝑠1 𝑔𝑠+ 1 𝑔2 𝑔3 𝑔3′+
Arithmetic Relationships (Real-AR) Clean Dirty 0.82 (0.89, 0.85, 0.87) 0.92 (0.91, 0.87, 0.89) 0.53 (0.62, 0.49, 0.55) 0.52 (0.62, 0.49, 0.55) 0.54 (0.36, 0.62, 0.46) 0.59 (0.61, 0.92, 0.73) 0.53 (0.57, 0.90, 0.69) 0.15 (0.18, 0.92, 0.30) 0.43 (0.48, 0.97, 0.64) 0.57 (0.57, 0.89, 0.70) 0.52 (0.53, 0.93, 0.68) 0.18 (0.39, 0.90, 0.55) 0.34 (0.51, 0.45, 0.48) 0.08 (0.11, 1.0, 0.19) 0.50 (0.55, 0.78, 0.65) 0.49 (0.56, 0.57, 0.56) 0.26 (0.39, 0.23, 0.29) 0.06 (0.11, 1.0, 0.19) 0.10 (0.11, 1.0, 0.19) 0.47 (0.60, 0.53, 0.56) 0.43 (0.52, 0.58, 0.55) 0.32 (0.27, 0.48, 0.35) 0.53 (0.53, 0.93, 0.68) 0.61 (0.39, 0.87, 0.54) 0.11 (0.11, 1.0, 0.19) 0.52 (0.55, 0.69, 0.61) 0.11 (0.11, 1.0, 0.19) 0.57 (0.56, 0.82, 0.67) 0.11 (0.11, 1.0, 0.19) 0.51 (0.61, 0.57, 0.59) 0.11 (0.11, 1.0, 0.19) 0.51 (0.61, 0.57, 0.59) 0.11 (0.11, 1.0, 0.19) 0.56 (0.56, 0.85, 0.68) 0.11 (0.11, 1.0, 0.19) 0.44 (0.52, 0.53, 0.52) 0.08 (0.11, 1.0, 0.19) 0.07 (0.11, 1.0, 0.19)
String Transformations (Real-ST) Clean Dirty 0.84 (0.92, 0.90, 0.91) 0.81 (0.92, 0.86, 0.89) 0.01 (0.01, 1.0, 0.01) 0.0 (0.0, 1.0, 0.01) 0.81 (0.84, 0.77, 0.80) 0.25 (0.39, 0.92, 0.55) 0.66 (0.64, 0.89, 0.75) 0.01 (0.02, 0.21, 0.03) 0.01 (0.01, 1.0, 0.02) 0.03 (0.05, 0.86, 0.10) 0.58 (0.59, 0.99, 0.74) 0.02 (0.03, 0.92, 0.07) 0.21 (0.34, 0.28, 0.31) 0.03 (0.25, 0.04, 0.06) 0.39 (0.49, 0.60, 0.54) 0.01 (0.02, 0.39, 0.03) 0.23 (0.39, 0.45, 0.42) 0.02 (0.29, 0.04, 0.07) 0.01 (0.01, 1.0, 0.01) 0.0 (0.0, 0.78, 0.01) 0.26 (0.39, 0.36, 0.37) 0.01 (0.02, 0.33, 0.03) 0.58 (0.59, 0.99, 0.74) 0.02 (0.04, 0.92, 0.07) 0.01 (0.01, 1.0, 0.01) 0.0 (0.01, 0.89, 0.01) 0.01 (0.01, 1.0, 0.01) 0.0 (0.01, 0.88, 0.01) 0.01 (0.01, 1.0, 0.01) 0.0 (0.01, 0.86, 0.01) 0.01 (0.01, 1.0, 0.01) 0.0 (0.01, 0.86, 0.01) 0.01 (0.01, 1.0, 0.01) 0.0 (0.01, 0.87, 0.01) 0.01 (0.01, 1.0, 0.01) 0.0 (0.0, 1.0, 0.01) 0.01 (0.01, 1.0, 0.01) 0.0 (0.0, 1.0, 0.01)
Functional Dependencies (Real-FD) Clean Dirty 0.91 (0.73, 1.0, 0.85) 0.92 (0.74, 1.0, 0.85) 0.35 (0.39, 1.0, 0.56) 0.36 (0.38, 1.0, 0.55) 0.90 (0.82, 0.96, 0.88) 0.75 (0.72, 1.0, 0.84) 0.45 (0.46, 0.75, 0.57) 0.44 (0.43, 0.91, 0.59) 0.38 (0.38, 0.82, 0.52) 0.45 (0.47, 0.83, 0.60) 0.42 (0.43, 0.90, 0.59) 0.42 (0.47, 0.95, 0.63) 0.49 (0.46, 0.76, 0.57) 0.53 (0.56, 0.76, 0.64) 0.44 (0.45, 0.88, 0.59) 0.55 (0.58, 0.81, 0.68) 0.49 (0.39, 0.73, 0.51) 0.41 (0.38, 1.0, 0.55) 0.39 (0.39, 1.0, 0.56) 0.34 (0.43, 1.0, 0.61) 0.49 (0.52, 0.80, 0.63) 0.56 (0.60, 0.81, 0.69) 0.43 (0.44, 0.90, 0.59) 0.45 (0.52, 0.90, 0.66) 0.40 (0.40, 1.0, 0.57) 0.37 (0.39, 0.99, 0.55) 0.38 (0.38, 1.0, 0.55) 0.41 (0.44, 1.0, 0.61) 0.40 (0.40, 1.0, 0.57) 0.40 (0.41, 0.86, 0.55) 0.40 (0.40, 1.0, 0.57) 0.40 (0.38, 1.0, 0.55) 0.40 (0.40, 1.0, 0.57) 0.40 (0.38, 0.98, 0.55) 0.40 (0.40, 1.0, 0.57) 0.41 (0.44, 1.0, 0.61) 0.43 (0.45, 0.88, 0.59) 0.37 (0.48, 0.92, 0.63)
(a) Real-AR (Clean)
(b) Real-AR (Dirty)
(c) Real-ST (Clean)
(d) Real-ST (Dirty)
(e) Real-FD (Clean)
(f) Real-FD (Dirty)
(g) RWD (Clean)
(h) RWD (Dirty)
Figure 4: Quality comparisons on the Real and RWD benchmarks, between six best performing methods.
5.2
Experimental results
Auto-Relate delivers consistent gains across all three FR types. On Real-AR, it achieves PR-AUC scores of 0.82 and 0.92 under the clean and dirty settings, respectively, which are 51.9% and 50.8% higher than the strongest competing baselines. On Real-ST, AutoRelate obtains PR-AUC scores of 0.84 and 0.81, ranking first in both settings, with a particularly large margin under dirty data. On Real-FD, it ranks first in both settings, achieving PR-AUC scores of 0.91 (clean) and 0.92 (dirty). While the margin over the strongest baseline is narrow on clean data (0.91 vs. 0.90), Auto-Relate maintains a 22.7% improvement under dirty data, demonstrating stronger robustness to noise. These indicate that Auto-Relate generalizes effectively across ARs, STs, and classical FDs, providing strong reliability discrimination across both clean and dirty data.
Exp-1: Effectiveness of Auto-Relate. We first evaluated the effectiveness of Auto-Relate and all baselines under the default setting. Real benchmarks. Table 2 reports the overall quality comparison on the Real benchmarks, and Figure 4 shows the corresponding precision–recall curves of the top-six methods. As shown in Table 2, Auto-Relate consistently achieves the best PR-AUC across all settings. It achieves an average PR-AUC of 0.87, which is on average 59% higher than the strongest competing baseline across all settings, with the largest absolute gain of 0.56 on Real-ST in the dirty setting. Figure 4 further shows that Auto-Relate maintains a clear precision–recall advantage in most Real benchmark settings. 9
Table 3: Ablation of optimizations on Real-AR
RWD benchmark. We further compared Auto-Relate against the topsix best-performing baselines on the RWD benchmark. As shown in Figures 4(g) and 4(h), Auto-Relate consistently achieves the best performance under both clean and dirty settings, with PR-AUC scores of 0.90 and 0.80, respectively. It outperforms the strongest competing baselines by 41.6% and 19.3%, and maintains higher precision across a wide recall range. These results confirm its effectiveness on this manually labeled FD benchmark.
Method Auto-Relate No Group-by No Closed-form No Binomial No Optimization
Clean Time (ms) PR-AUC 20.3 0.82 21.6 0.82 31.3 0.83 25.4 0.82 35.9 0.83
Dirty Time (ms) PR-AUC 72.9 0.92 72.9 0.92 92.3 0.92 93.5 0.92 115.6 0.92
the sampling loop and is expected to be more beneficial on wider tables with higher-arity FRs.
Exp-2: Efficiency and Scalability of Auto-Relate. We evaluated the efficiency of Auto-Relate under the default setting, focusing on its per-candidate running time, scalability with respect to table size, and the practical impact of the proposed optimization strategies. Comparison vs. baselines. Figure 5 reports the per-candidate running time for the reliability-verification stage on each benchmark, excluding candidate generation, which is shared across all methods. Specifically, the 𝑥-axis shows the 50th, 90th, and 95th percentile running times, together with the average running time across all tables. On Real-AR and Real-ST, Auto-Relate processes each table within a fraction of a second across all reported percentiles. While it is slower than lightweight statistical measures such as CS and MI, all methods remain in the sub-second regime, keeping AutoRelate practical for interactive use. On Real-FD, some baselines (e.g., RFI′+ ) spend more than 300 seconds per table at the 95th percentile, whereas Auto-Relate remains substantially faster. Although AutoRelate is not always the fastest method, its reliability-verification procedure naturally incurs additional cost beyond purely statistical measures. Nevertheless, its per-candidate running time remains practical for interactive use while achieving substantially higher accuracy than competing baselines (Table 2). Varying table size. To evaluate the scalability of Auto-Relate, we selected tables with more than 1,000 rows and construct datasets of target sizes ranging from 2K to 10K rows via controlled downsampling or row-level up-sampling. As shown in Figure 6, the average per-candidate running time generally increases with the number of rows, as expected. Nevertheless, Auto-Relate exhibits strong scalability across all FR types, with consistently low per-candidate running time, while MI can exceed 10 seconds per candidate on larger inputs. Although Auto-Relate is slower than FI and RFI+ on Real-AR and Real-ST, it achieves substantially better quality (see Table 2). These verify that Auto-Relate scales well with table size while maintaining a practical efficiency-quality trade-off. Impact of optimization strategies. We evaluated the practical impact of the proposed optimization strategies on Real-AR. As shown in Table 3, the proposed optimizations reduce the per-candidate verification time by 43.5% in the clean setting (from 35.9 ms to 20.3 ms) and 36.9% in the dirty setting (from 115.6 ms to 72.9 ms). Among them, the closed-form speed-up and binomial bound contribute the most, reducing the per-candidate cost by up to 19.4 ms and 20.6 ms in the dirty setting, respectively. On Real-AR, the closed-form speed-up applies to 44.2% of sampled candidates, and the binomial bound triggers early termination on every sampled candidate, explaining why they reduce verification time substantially. The group-by bound has a smaller effect on average per-candidate runtime because candidates rejected by it are also quickly eliminated by subsequent tests; nonetheless, it rejects 85.4% of candidates before
Exp-3: Sensitivity Analysis. We evaluated the sensitivity of AutoRelate to the threshold 𝜂, noise rate, and the size |𝐶 Ψ | in FRs. Varying the perturbation threshold. We first varied the perturbation threshold 𝜂 from 0.1 to 0.9 on Real-AR and report the resulting F1scores. As shown in Figure 8(a), Auto-Relate consistently achieves the best F1-score across a broad range of threshold settings, peaking around the default choice 𝜂 = 0.5. In contrast, most baselines, with the exception of RFI+ , exhibit relatively stable but consistently lower F1-score curves across different thresholds. These demonstrate that Auto-Relate is robust to the perturbation threshold. Varying noise rates. We varied the noise rate in the dirty-data setting from 2% to 10% and plot the resulting precision–recall curves of Auto-Relate on Real-AR. As shown in Figure 8(b), Auto-Relate exhibits limited sensitivity to the noise rate. While higher noise rates lead to a slight precision drop in the high-recall region, the overall precision–recall trade-off remains stable, verifying the robustness of Auto-Relate across varying noise rates. Varying the number of participative columns. We evaluated how the number of participative columns |𝐶 Ψ | affects the FR discovery performance. Figure 7 reports the precision–recall curves on Real-AR and Real-ST under both clean and dirty settings. For AR discovery, we compare the 3-column and 4-column settings; for ST discovery, we compare the 2-column and 3-column settings. As expected, with |𝐶 Ψ | increasing, the task becomes more challenging and the performance of all methods generally decreases, especially on dirty data. Nevertheless, Auto-Relate consistently achieves the best PRAUC and maintains a clear precision–recall advantage across both datasets and settings. These show that Auto-Relate remains effective when FRs involve more participative columns. Exp-4: Ablation Study. We evaluated the impact of reliability tests and optimization strategies in Auto-Relate. No Minimality Test. To evaluate the effectiveness of the Minimality Test, we compared Auto-Relate and its variant without the minimality test, as shown in Figure 9(a). The two curves remain relatively close in the low-to-mid recall range, but diverge noticeably in the high-recall region, where the variant without the Minimality Test suffers a clearer precision drop. This indicates that atomicity-based filtering is effective in suppressing redundant FRs and improving the overall quality of the returned candidates. No Independence Test. To evaluate the effectiveness of the Independence Test, we compared Auto-Relate with a variant that omits the Independence Test, as shown in Figure 9(b). Removing the Independence Test leads to a clear precision loss, with the gap being especially evident between recall 0.6 and 0.9. This confirms that the Independence Test plays a critical role in filtering incomplete 10
(a) Real-AR dataset
(b) Real-ST dataset
(c) Real-FD dataset
Average Running Time (seconds)
Figure 5: Per-candidate verification time on the Real benchmarks. 101 100
Auto-Relate CS FI MI RFI+
100
Auto-Relate CS FI MI RFI+
101
Auto-Relate CS FI MI RFI+
100
10 1 10 1
10 2 2k
4k 6k 8k 10k (a) Arithmetic Relationship
2k
4k 6k 8k 10k (b) String Transformation Table Length (rows)
2k
4k 6k 8k 10k (c) Functional Dependency
Figure 6: Scalability with respect to table size on the Real benchmarks.
(a) Clean Real-AR: 3-column ARs
(b) Dirty Real-AR: 3-column ARs
(c) Clean Real-ST: 2-column STs
(d) Dirty Real-ST: 2-column STs
(e) Clean Real-AR: 4-column ARs
(f) Dirty Real-AR: 4-column ARs
(g) Clean Real-ST: 3-column STs
(h) Dirty Real-ST: 3-column STs
Figure 7: Sensitivity to the number of participative columns on Real-AR and Real-ST.
6
candidates, and is therefore particularly important for maintaining the reliability of Auto-Relate in the dirty-data setting. No Optimization Strategies. We examined whether the proposed optimization strategies affect the quality of FR discovery. As shown in Table 3, removing individual or all optimization strategies has little effect on PR-AUC across all settings. Together with the runtime analysis in Exp-2, this confirms that the proposed optimizations mainly affect efficiency, enabling Auto-Relate to reduce verification cost while preserving its discovery effectiveness.
RELATED WORK
Dependency and Relationship Discovery. Functional dependencies (FDs) and approximate functional dependencies (AFDs) have been extensively studied in data profiling and data management. Representative discovery algorithms (e.g., [3, 31, 49, 67]) focus on efficiently enumerating minimal FDs from relational data, with a comprehensive experimental comparison provided by [52]. More recent work continues to improve FD discovery, e.g., via hitting-set-based enumeration [7], mixed-type extensions [47], and meaningfulnessaware discovery [65], while relaxed and approximate variants have 11
(a) Varying threshold 𝜂
Table Transformation Discovery. Table transformation has been extensively studied in program synthesis, data wrangling, and spreadsheet analysis, largely under the programming-by-example (PBE) paradigm. Systems such as FlashFill [27] and its table-level extension [29] synthesize string transformations from input-output examples, while Foofah [34] and CLX [35] extend this idea to tablelevel operators and verifiable pattern-based transformations, respectively. Beyond a fixed operator set, DataXFormer [2] and TDE [30] mine transformations from external sources such as web tables and existing transformation logic, Auto-Pipeline [68] generalizes PBE to a by-target setting for multi-step pipelines, and AutoPandas [5] synthesizes Pandas programs with neural-backed generators. From a complementary perspective, Explain-Da-V [63] explains semantic changes between dataset versions as transformation programs, and we include its conciseness and concentration metrics in our evaluation. These methods differ from Auto-Relate in both interaction mode and technical objective. PBE-style settings rely on user-provided examples and keep users in the loop to inspect or select synthesized programs, which makes manual validation feasible. By contrast, Auto-Relate operates automatically on a single observed table and aims to discover latent functional relationships at scale, where distinguishing genuine relationships from coincidental, redundant, or incomplete ones becomes the core challenge. In particular, while Explain-Da-V uses ranking heuristics such as conciseness to prioritize candidate transformations, Auto-Relate explicitly verifies candidate reliability through dedicated tests of accuracy, atomicity, stability, and integrity.
(b) Varying noise rate
Figure 8: Sensitivity to threshold 𝜂 and noise rate on Real-AR.
(a) No Minimality Test
(b) No Independence Test
Figure 9: Ablation of reliability tests on Real-AR. been surveyed in [12] and recently advanced in [11, 40]. Beyond FDs, related dependency formalisms have been studied as well, including conditional functional dependencies (CFDs) [9, 21], denial constraints (DCs) [17, 55], matching dependencies (MDs) [38, 62], and entity enhancing rules (REEs) [22–24, 28]. These methods are complementary to Auto-Relate, as they mainly focus on enumerating or mining dependency candidates, whereas our focus is on reliability verification of discovered relationships. A related line of work studies measures for ranking approximate FD candidates, including violation-based measures [25, 36, 53], cooccurrence-based measures [33], information-theoretic measures such as Mutual Information (MI) [14] and Fraction of Information (FI) [13, 25], and probabilistic measures [26, 57]. A recent comparative study [53] systematically evaluates these measures. While useful for scoring and ranking candidates, these methods primarily assess candidates through observed-table signals such as violations, association strength, or uncertainty reduction, rather than explicitly verifying structural reliability. Most closely related to our work are methods for reliable dependency discovery. RFI [44–46] and SMI [56] improve the robustness of information-theoretic scores under finite or sparse data, while Zhang et al. [70] and DAFDiscover [20] target noisy or dirty settings, and the anytime framework [60] targets resource-constrained settings. Efficiency-oriented approaches such as [39] further improve the scalability of approximate dependency discovery. Auto-Relate differs from this line of work in two aspects. First, prior work ties reliability to score estimation, noise-robust modeling, or efficiency, whereas we characterize reliability through four properties, i.e., accuracy, atomicity, stability, and integrity, and verify them directly on the observed table through dedicated tests. Second, their scope is primarily FD/AFD-style dependency discovery, whereas Auto-Relate unifies ARs, STs, and FDs under a single framework. Berti-Équille et al. [6] study genuine FDs under missing values; by contrast, our Independence Test targets incomplete candidates whose violations correlate with non-participative attributes.
Spreadsheet Analysis, Table Understanding, and Data Cleaning. Spreadsheets are a common environment in which functional relationships arise, and prior work in spreadsheet analysis has studied the prevalence of spreadsheet errors [51], formula error detection [4], cell clustering and smell detection [15], and fault prediction via product metrics [37]. A parallel line of work on table understanding and data profiling aims to recover the semantics and latent structure of tables, ranging from classical column annotation [41] and table profiling [48] to learned column-type inference such as Sherlock [32] and Sato [69], and more recent table pre-training and language-model-based approaches [19, 64]. In data cleaning [1], dependencies and derived-value relationships have been used as constraints for error detection and repair, e.g., in HoloClean [61], Raha [43], and Baran [42], while related work on data quality [16] and provenance [10, 18] relies on similar inter-column relationships for consistency maintenance and lineage tracing. By contrast, AutoRelate treats reliable FR discovery as the primary problem, providing a unified framework for ARs, STs, and FDs from raw tables, with explicit reliability verification to filter spurious candidates.
7
CONCLUSION
We proposed Auto-Relate, a unified framework for discovering reliable functional relationships from tables. Its main contributions include: (1) a unified notion of functional relationships covering arithmetic relationships, string transformations, and functional dependencies; (2) four reliability criteria, including accuracy, atomicity, stability, and integrity, for distinguishing genuine relationships from spurious ones; (3) a mine-then-verify framework that first generates candidate relationships and then verifies their reliability 12
through a Minimality Test, a Perturbation Test, and an Independence Test; (4) three optimization strategies for efficient reliability verification; and (5) a large-scale benchmark suite constructed from 58,679 real-world spreadsheets and relational tables and containing 6,414 ground-truth instances across all three types. Extensive experiments against 18 baselines demonstrate the effectiveness and efficiency of Auto-Relate, which achieves an average PR-AUC of 0.87, 59% higher than the best competing baseline across all settings.
13
REFERENCES
[31] Yka Huhtala, Juha Kärkkäinen, Pasi Porkka, and Hannu Toivonen. 1999. TANE: An efficient algorithm for discovering functional and approximate dependencies. The computer journal 42, 2 (1999), 100–111. [32] Madelon Hulsebos, Kevin Hu, Michiel Bakker, Emanuel Zgraggen, Arvind Satyanarayan, Tim Kraska, Çagatay Demiralp, and César Hidalgo. 2019. Sherlock: A Deep Learning Approach to Semantic Data Type Detection. In SIGKDD. 1500–1508. [33] Ihab F Ilyas, Volker Markl, Peter Haas, Paul Brown, and Ashraf Aboulnaga. 2004. CORDS: Automatic discovery of correlations and soft functional dependencies. In SIGMOD. 647–658. [34] Zhongjun Jin, Michael R Anderson, Michael Cafarella, and HV Jagadish. 2017. Foofah: Transforming data by example. In SIGMOD. 683–698. [35] Zhongjun Jin, Michael Cafarella, HV Jagadish, Sean Kandel, Michael Minar, and Joseph M Hellerstein. 2019. CLX: Towards verifiable PBE data transformation. EDBT (2019), 265–276. [36] Jyrki Kivinen and Heikki Mannila. 1995. Approximate inference of functional dependencies from relations. Theoretical Computer Science 149, 1 (1995), 129–149. [37] Patrick Koch, Konstantin Schekotihin, Dietmar Jannach, Birgit Hofer, and Franz Wotawa. 2021. Metric-based fault prediction for spreadsheets. TSE 47, 10 (2021), 2195–2207. [38] Ioannis Koumarelas, Thorsten Papenbrock, and Felix Naumann. 2020. MDedup: Duplicate detection with matching dependencies. PVLDB 13, 5 (2020), 712–725. [39] Sebastian Kruse and Felix Naumann. 2018. Efficient discovery of approximate dependencies. PVLDB 11, 7 (2018), 759–772. [40] Mengran Li, Zijing Tan, Honghui Yang, and Shuai Ma. 2025. Efficient Discovery of Relaxed Functional Dependencies. PVLDB 18, 7 (2025), 2044–2056. [41] Girija Limaye, Sunita Sarawagi, and Soumen Chakrabarti. 2010. Annotating and searching web tables using entities, types and relationships. PVLDB 3, 1-2 (2010), 1338–1347. [42] Mohammad Mahdavi and Ziawasch Abedjan. 2020. Baran: Effective Error Correction via a Unified Context Representation and Transfer Learning. PVLDB 13, 11 (2020), 1948–1961. [43] Mohammad Mahdavi, Ziawasch Abedjan, Raul Castro Fernandez, Samuel Madden, Mourad Ouzzani, Michael Stonebraker, and Nan Tang. 2019. Raha: A Configuration-Free Error Detection System. In SIGMOD. 865–882. [44] Panagiotis Mandros, Mario Boley, and Jilles Vreeken. 2017. Discovering reliable approximate functional dependencies. In SIGKDD. 355–363. [45] Panagiotis Mandros, Mario Boley, and Jilles Vreeken. 2018. Discovering reliable dependencies from data: Hardness and improved algorithms. In ICDM. 317–326. [46] Panagiotis Mandros, Mario Boley, and Jilles Vreeken. 2020. Discovering dependencies with reliable mutual information. KAIS 62, 11 (2020), 4223–4253. [47] Panagiotis Mandros, David Kaltenpoth, Mario Boley, and Jilles Vreeken. 2020. Discovering functional dependencies from mixed-type data. In SIGKDD. 1404– 1414. [48] Felix Naumann. 2014. Data profiling revisited. SIGMOD Record 42, 4 (2014), 40–49. [49] Noel Novelli and Rosine Cicchetti. 2001. Fun: An efficient algorithm for mining functional and embedded dependencies. In ICDT. 189–203. [50] OpenAI. 2025. Introducing GPT-5. https://openai.com/index/introducing-gpt-5/. Accessed: 2026-04-29. [51] Raymond R Panko. 1998. What we know about spreadsheet errors. JOEUC 10, 2 (1998), 15–21. [52] Thorsten Papenbrock, Jens Ehrlich, Jannik Marten, Tommy Neubert, Jan-Peer Rudolph, Martin Schönberg, Jakob Zwiener, and Felix Naumann. 2015. Functional dependency discovery: An experimental evaluation of seven algorithms. PVLDB 8, 10 (2015), 1082–1093. [53] Marcel Parciak, Sebastiaan Weytjens, Niel Hens, Frank Neven, Liesbet M Peeters, and Stijn Vansummeren. 2024. Measuring Approximate Functional Dependencies: a Comparative Study. In ICDE. 3505–3518. [54] Karl Pearson. 1900. On the Criterion that a Given System of Deviations from the Probable in the Case of a Correlated System of Variables is Such that it Can be Reasonably Supposed to have Arisen from Random Sampling. Philos. Mag. 50, 302 (1900), 157–175. [55] Eduardo H. M. Pena, Eduardo Cunha de Almeida, and Felix Naumann. 2019. Discovery of Approximate (and Exact) Denial Constraints. PVLDB 13, 3 (2019), 266–278. [56] Frédéric Pennerath, Panagiotis Mandros, and Jilles Vreeken. 2020. Discovering approximate functional dependencies using smoothed mutual information. In SIGKDD. 1254–1264. [57] Gregory Piatetsky-Shapiro and C Matheus. 1993. Measuring data dependencies in large databases. In KDD. 162–173. [58] David Powers. 2011. Evaluation: From Precision, Recall and F-Measure to ROC, Informedness, Markedness & Correlation. JMLT 2, 1 (2011), 37–63. [59] Erhard Rahm, Hong Hai Do, et al. 2000. Data cleaning: Problems and current approaches. IEEE Data Eng. Bull. 23, 4 (2000), 3–13. [60] Sanjivni Rana, Junya Ogawa, Suraj Shetiya, Senjuti Basu Roy, and Gautam Das. 2025. Anytime Algorithms for Approximate Functional Dependencies. In SIGKDD. 2386–2397.
[1] Ziawasch Abedjan, Xu Chu, Dong Deng, Raul Castro Fernandez, Ihab F. Ilyas, Mourad Ouzzani, Paolo Papotti, Michael Stonebraker, and Nan Tang. 2016. Detecting data errors: where are we and what needs to be done? PVLDB 9, 12 (2016), 993–1004. [2] Ziawasch Abedjan, John Morcos, Ihab F Ilyas, Mourad Ouzzani, Paolo Papotti, and Michael Stonebraker. 2016. Dataxformer: A robust transformation discovery system. In ICDE. 1134–1145. [3] Ziawasch Abedjan, Patrick Schulze, and Felix Naumann. 2014. DFD: Efficient functional dependency discovery. In CIKM. 949–958. [4] Daniel W Barowy, Emery D Berger, and Benjamin Zorn. 2018. ExceLint: automatically finding spreadsheet formula errors. PACMPL 2, OOPSLA (2018), 1–26. [5] Rohan Bavishi, Caroline Lemieux, Roy Fox, Koushik Sen, and Ion Stoica. 2019. AutoPandas: neural-backed generators for program synthesis. PACMPL 3, OOPSLA (2019), 1–27. [6] Laure Berti-Équille, Hazar Harmouch, Felix Naumann, Noël Novelli, and Saravanan Thirumuruganathan. 2018. Discovery of genuine functional dependencies from relational data with missing values. PVLDB 11, 8 (2018), 880–892. [7] Tobias Bleifuß, Thorsten Papenbrock, Thomas Bläsius, Martin Schirneck, and Felix Naumann. 2024. Discovering functional dependencies through hitting set enumeration. PACMMOD 2, 1 (2024), 1–24. [8] Alex Bogatu, Norman W Paton, Alvaro AA Fernandes, and Martin Koehler. 2019. Towards automatic data format transformations: data wrangling at scale. Comput. J. 62, 7 (2019), 1044–1060. [9] Philip Bohannon, Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsietsidis. 2007. Conditional functional dependencies for data cleaning. In ICDE. 746–755. [10] Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew. 2001. Why and where: A characterization of data provenance. In ICDT. 316–330. [11] Loredana Caruccio, Vincenzo Deufemia, Felix Naumann, and Giuseppe Polese. 2021. Discovering Relaxed Functional Dependencies Based on Multi-Attribute Dominance. TKDE 33, 9 (2021), 3212–3228. [12] Loredana Caruccio, Vincenzo Deufemia, and Giuseppe Polese. 2016. Relaxed functional dependencies—a survey of approaches. TKDE 28, 1 (2016), 147–165. [13] Roger Cavallo and Michael Pittarelli. 1987. The theory of probabilistic databases.. In PVLDB. 71–81. [14] Jie Cheng, David A Bell, and Weiru Liu. 1997. Learning belief networks from data: An information theory based approach. In CIKM. 325–331. [15] Shing-Chi Cheung, Wanjun Chen, Yepang Liu, and Chang Xu. 2016. CUSTODES: automatic spreadsheet cell clustering and smell detection using strong and weak features. In ICSE. 464–475. [16] Xu Chu, Ihab F Ilyas, Sanjay Krishnan, and Jiannan Wang. 2016. Data cleaning: Overview and emerging challenges. In SIGMOD. 2201–2206. [17] Xu Chu, Ihab F Ilyas, and Paolo Papotti. 2013. Discovering denial constraints. PVLDB 6, 13 (2013), 1498–1509. [18] Yingwei Cui and Jennifer Widom. 2000. Practical lineage tracing in data warehouses. In ICDE. 367–378. [19] Xiang Deng, Huan Sun, Alyssa Lees, You Wu, and Cong Yu. 2020. TURL: table understanding through representation learning. PVLDB 14, 3 (2020), 307–319. [20] Xiaoou Ding, Yixing Lu, Hongzhi Wang, Chen Wang, Yida Liu, and Jianmin Wang. 2024. Dafdiscover: Robust mining algorithm for dynamic approximate functional dependencies on dirty data. PVLDB 17, 11 (2024), 3484–3496. [21] Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsietsidis. 2008. Conditional functional dependencies for capturing data inconsistencies. TODS 33, 2 (2008), 1–48. [22] Wenfei Fan, Ziyan Han, Yaoshu Wang, and Min Xie. 2022. Parallel Rule Discovery from Large Datasets by Sampling. In SIGMOD. 384–398. [23] Wenfei Fan, Ziyan Han, Yaoshu Wang, and Min Xie. 2023. Discovering top-k rules using subjective and objective criteria. PACMMOD 1, 1 (2023), 1–29. [24] Wenfei Fan, Ziyan Han, Min Xie, and Guangyi Zhang. 2024. Discovering top-k relevant and diversified rules. PACMMOD 2, 4 (2024), 1–28. [25] Chris Giannella and Edward Robertson. 2004. On approximation measures for functional dependencies. Information Systems 29, 6 (2004), 483–507. [26] Leo A Goodman and William H Kruskal. 1979. Measures of association for cross classifications. Springer. [27] Sumit Gulwani. 2011. Automating string processing in spreadsheets using inputoutput examples. ACM Sigplan Notices 46, 1 (2011), 317–330. [28] Ziyan Han, Wanjia Chen, Yunpeng Han, Rui Mao, and Jianbin Qin. 2026. Fast Diversified Top-k Rule Discovery via User-Guided Embeddings. TKDE 38, 3 (2026), 1739–1753. [29] William R Harris and Sumit Gulwani. 2011. Spreadsheet table transformations from examples. ACM SIGPLAN Notices 46, 6 (2011), 317–328. [30] Yeye He, Xu Chu, Kris Ganjam, Yudian Zheng, Vivek Narasayya, and Surajit Chaudhuri. 2018. Transform-data-by-example (TDE) an extensible search engine for data transformations. PVLDB 11, 10 (2018), 1165–1177.
14
[67] Catharine Wyss, Chris Giannella, and Edward Robertson. 2001. FastFDs: A heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances. In DaWaK. 101–110. [68] Junwen Yang, Yeye He, and Surajit Chaudhuri. 2021. Auto-pipeline: synthesizing complex data pipelines by-target using reinforcement learning and search. PVLDB 14, 11 (2021), 2563–2575. [69] Dan Zhang, Madelon Hulsebos, Yoshihiko Suhara, Çağatay Demiralp, Jinfeng Li, and Wang-Chiew Tan. 2020. Sato: contextual semantic type detection in tables. PVLDB 13, 12 (2020), 1835–1848. [70] Yunjia Zhang, Zhihan Guo, and Theodoros Rekatsinas. 2020. A Statistical Perspective on Discovering Functional Dependencies in Noisy Data. In SIGMOD. 861–876.
[61] Theodoros Rekatsinas, Xu Chu, Ihab F. Ilyas, and Christopher Ré. 2017. HoloClean: holistic data repairs with probabilistic inference. Proc. VLDB Endow. 10, 11 (Aug. 2017), 1190–1201. https://doi.org/10.14778/3137628.3137631 [62] Philipp Schirmer, Thorsten Papenbrock, Ioannis Koumarelas, and Felix Naumann. 2020. Efficient Discovery of Matching Dependencies. TODS 45, 3 (2020), 1–33. [63] Roee Shraga and Renée J Miller. 2023. Explaining dataset changes for semantic data versioning with Explain-Da-V. PVLDB 16, 6 (2023), 1587–1600. [64] Yoshihiko Suhara, Jinfeng Li, Yuliang Li, Dan Zhang, Çağatay Demiralp, Chen Chen, and Wang-Chiew Tan. 2022. Annotating Columns with Pre-trained Language Models. In SIGMOD. 1493–1503. [65] Ziheng Wei and Sebastian Link. 2023. Towards the efficient discovery of meaningful functional dependencies. Information Systems 116 (2023), 102224. [66] Edwin B Wilson. 1927. Probable inference, the law of succession, and statistical inference. J. Amer. Statist. Assoc. 22, 158 (1927), 209–212.
15