1
Top-k Approximate Functional Dependency Discovery
arXiv:2605.24925v1 [cs.DB] 24 May 2026
Xiaolong Wan, Xixian Han
Abstract—Approximate functional dependencies (AFDs) relax exact functional dependencies by tolerating a bounded degree of violation, making them suited for data quality auditing. Threshold-based discovery returns all dependencies above a userspecified cutoff, but output size is uncontrollable, the right threshold varies across datasets, and widely used measures are sensitive to LHS dimensionality. We study global top-k AFD discovery, where neither the LHS nor the RHS is fixed and the k strongest dependencies under µ+ are returned directly. The crossattribute comparability of µ+ makes such a global ranking welldefined. We prove a Triangle Incompatibility Theorem showing that minimality, global top-k ranking, and exact-k output cannot simultaneously hold under any non-monotonic scoring function, justifying the removal of the minimality requirement. We present two algorithms: TALE-Base, which returns the exact global top-k result by exhaustive level-wise evaluation, and TALE-Opt, which reduces computation through Apriori-style candidate generation, LHS computation reuse, and two complementary pruning rules exploiting exact FD monotonicity and an optimistic upper bound on µ+ . Experiments on 41 real-world datasets show that TALEOpt achieves pruning ratios up to 99.81% and speedups over TALE-Base up to 78.81×. Index Terms—Approximate functional dependency, top-k discovery, pruning strategy, data profiling.
I. I NTRODUCTION UNCTIONAL dependencies (FDs) are among the most studied integrity constraints in relational databases [1]. An FD X → A states that the values of X uniquely determine A, and discovering FDs from data has long served as a basis for schema design [2], data cleaning [3], and consistency checking [4]. In practice, strict FDs seldom hold over realworld datasets: dirty values, recording errors, and legitimate exceptions all introduce violations. Approximate functional dependencies (AFDs) [5] address this by tolerating a bounded degree of violation. For data quality auditing, an AFD that is almost satisfied is often more useful than an exact FD, since it points directly to the tuples responsible for the violation and supports targeted error detection and repair [6]. Existing approaches to AFD discovery predominantly follow a threshold-based paradigm: a user specifies a cutoff θ and all dependencies whose measure exceeds θ are returned [7]. Three difficulties undermine this paradigm in practice. • Uncontrollable output size. The number of returned dependencies depends entirely on θ. A high cutoff risks missing genuine but imperfect dependencies, while a low one floods the output with spurious results [8]. There is no principled way to choose between these extremes.
F
The authors are with School of Computer Science and Technology, Harbin Institute of Technology, China. (e-mail: [email protected], [email protected])
(a) Threshold-based
θ=0.90 1 score
0.5 Output size depends on θ: θ=0.80 ⇒ 7; θ=0.95 ⇒ 1; θ=0.90 ⇒ 3.
(b) Fixed-RHS top-k (RHS = D) 1 score
0.5 Only searches X→D. Misses {B, C}→E (score=0.97).
(c) Global top-k (this paper)
top-3 1 score
0.5 Searches all X→A. No θ, no fixed RHS. Returns the 3 globally strongest AFDs. RHS:
E
D
C
A
B
ignored
Fig. 1. Comparison of three AFD discovery paradigms on a relation with attributes {A, B, C, D, E}. Each dot represents a candidate AFD; colors indicate different RHS attributes (see legend). (a) The threshold-based approach returns all AFDs above θ, but output size is sensitive to θ. (b) The fixed-RHS approach restricts the search to a single target, missing high-scoring AFDs with other RHS. (c) The global top-k approach returns the k strongest AFDs across all attributes without any pre-specification.
Data-dependent threshold selection. No single θ works universally. The appropriate value depends on the data distribution, attribute cardinalities, and noise level, and it varies not only across datasets but across different attribute combinations within the same dataset. • Measure sensitivity to LHS dimensionality. Widely used measures such as g3 are sensitive to the number of distinct values on the left-hand side (LHS-uniqueness) [9]. As the LHS grows, even random attribute combinations tend to score high simply because fine-grained partitioning leaves few tuples per group. The same numerical threshold therefore carries different meanings at different LHS sizes, and this dimensionality bias compounds the first two difficulties. Figure 1 illustrates these problems and previews how the global top-k approach proposed in this paper addresses them. The top-k approach avoids threshold selection by returning the k highest-scoring dependencies directly. We extend this idea to a global setting where neither the LHS nor the RHS is fixed. Mandros et al. [8] study the fixed-RHS case, searching over subsets of the remaining attributes to find those that best determine a given target A. Their scoring function is a corrected fraction of information based on Shannon •
2
entropy, normalized by H(A). Since the normalization by H(A) depends on the marginal entropy of each RHS attribute, scores for dependencies with different right-hand sides reflect different reference points and are not directly comparable, so running their method separately for each possible target and merging the results does not yield a meaningful global ranking. A cross-RHS comparable scoring function is therefore a prerequisite for global top-k discovery, a requirement that Shannon entropy-based measures cannot satisfy. We address the problem of global top-k AFD discovery and adopt the µ+ measure as the scoring function. µ+ is grounded in logical entropy and quantifies the probability that two randomly chosen tuples agreeing on X also agree on A; its correction factor has a closed-form expression, keeping computation practical for the larger candidate space of global discovery. A recent comparative study [9] shows that µ+ is robust to both LHS-uniqueness and RHS-skew. Robustness to RHS-skew is especially important here, since a measure sensitive to it would systematically favor skewed attributes and flood the top-k list with artifacts rather than genuine dependencies. Our formulation imposes no minimality constraint on the LHS, not as a simplification, but because minimality is theoretically incompatible with global top-k ranking and exact-k output under any non-monotonic scoring function, as we prove in Theorem III.1. The global top-k AFD problem requires searching over all X → A combinations up to a bounded LHS size, a space that grows rapidly with the number of attributes. In the fixed-RHS setting of Mandros et al. [8], branch-and-bound exploits a single optimistic estimator over all LHS subsets. The global setting has no such structure, since no single bounding function can guide pruning across different RHS attributes. We propose two algorithms under the name TALE (Top-k AFD discovery via Logical Entropy). TALE-Base adopts a level-wise enumeration organized by LHS size, maintaining a min-heap of the current top-k results, and guarantees the exact global top-k result by exhaustive evaluation. TALE-Opt reduces computation through techniques at three levels. At the search level, an Apriori-style candidate generation scheme propagates pruning decisions to descendant LHS candidates. At the computation level, LHS hash values and NULL flags are cached and reused across all RHS evaluations sharing the same LHS. At the pruning level, exact FD pruning eliminates attributes whose supersets are guaranteed exact. The central challenge is that µ+ is not monotone under LHS enlargement, which rules out classical anti-monotonic pruning for the remaining candidates. We address this by deriving an optimistic upper bound on µ+ that decreases monotonically with LHS size, recovering safe pruning despite the non-monotonicity of the measure. This paper makes the following contributions. • The problem of global top-k AFD discovery is formalized, where neither the LHS nor the RHS is fixed. Adopting the µ+ measure makes dependencies with different RHS attributes directly comparable, giving a global ranking a well-defined meaning. To our knowledge, this problem has not been previously studied.
A Triangle Incompatibility Theorem shows that minimality, global top-k ranking, and exact-k output cannot simultaneously hold when the scoring function is not monotone under LHS enlargement, providing theoretical justification for dropping the minimality requirement. • A baseline algorithm TALE-Base and an optimized algorithm TALE-Opt are presented. TALE-Opt reduces computation through Apriori-style candidate generation, LHS computation reuse, exact FD pruning, and an optimistic upper bound on µ+ that recovers safe pruning under nonmonotonic scoring. • Experiments on 41 real-world datasets show that TALEOpt achieves pruning ratios up to 99.81% and speedups over TALE-Base up to 78.81×. The rest of this paper is organized as follows. Section II introduces preliminaries. Section III proves the Triangle Incompatibility Theorem. Section IV presents the baseline algorithm, which is optimized in Section V. Section VI reports experimental results. Section VII discusses related work, and Section VIII concludes the paper. •
II. P RELIMINARIES A. Basic Notions Let R = {A1 , A2 , . . . , Am } be a relation schema of m attributes, and let r be a relation instance over R containing n tuples. For a tuple t ∈ r and an attribute A ∈ R, t[A] denotes the value of A in t. For a subset X ⊆ R, t[X] denotes the projection of t onto X. We denote by πX the projection of r onto X, and by dX = |πX | the number of distinct X-values in r. Definition 1 (Functional Dependency). Given X ⊆ R and A ∈ R \ X, a functional dependency (FD) X → A holds in r if and only if for all t1 , t2 ∈ r, t1 [X] = t2 [X] implies t1 [A] = t2 [A]. An FD X → A is minimal if no proper subset X ′ ⊂ X also satisfies X ′ → A in r. When an FD does not hold exactly, a scoring function quantifies how close it is to holding. A dependency scored in this way is called an approximate functional dependency (AFD). Definition 2 (Approximate Functional Dependency). An approximate functional dependency (AFD) over a schema R is a pair (X → A, σ), where X ⊆ R, A ∈ R \ X, and σ is a scoring function that maps each dependency and relation instance to a value in [0, 1]. For a given instance r, the value σ(X → A, r) quantifies the strength of the dependency, with σ = 1 if and only if X → A is an exact FD in r. Many scoring functions have been proposed for AFDs, each with different trade-offs in reliability and sensitivity [9]. The measure adopted in this paper, µ+ , is defined in Section II-B. B. The µ+ Measure We adopt the µ+ measure [9] as the scoring function σ in Definition 2. It is based on logical entropy and built on probabilistic dependence (pdep), which measures the probability
3
that two tuples drawn uniformly at random with the same Xvalue also agree on A. Definition 3 (Probabilistic Dependence). Given X ⊆ R, A ∈ R \ X, and a relation instance r of size n, group the tuples by their X-values. For each group g, let |g| be its size and let fg,a be the number of tuples in g with value a on attribute A. The probabilistic dependence of A on X is X |g| X fg,a 2 . pdep(X → A, r) = n a |g| g P 2 The inner sum a (fg,a /|g|) is the probability that two tuples chosen uniformly at random from group g agree on A. The outer sum averages this over all groups, weighted by relative size. When X → A is an exact FD, each group is homogeneous in A and pdep = 1. When provides no P X 2 p , where pa is information about A, pdep reduces to a a the marginal frequency of value a. The unconditional variant removes the conditioning on X: X |{t ∈ r : t[A] = a}| 2 pdep(A, r) = n a which is simply the probability that two tuples chosen at random from r agree on A. The ratio pdep(X → A)/pdep(A) then measures how much conditioning on X increases agreement on A beyond what the marginal distribution already provides. Definition 4 (The µ+ Measure). Given X ⊆ R, A ∈ R \ X, and a relation instance r of size n with dX < n and pdep(A, r) < 1, the µ+ measure is defined as µ+ (X → A, r) = max 0, 1 − ρ(X → A, r) where
1 − pdep(X → A, r) n − 1 . · 1 − pdep(A, r) n − dX When dX = n or pdep(A, r) = 1, X → A is an exact FD and µ+ (X → A, r) := 1. ρ(X → A, r) =
The ratio (1−pdep(X → A))/(1−pdep(A)) is the fraction of disagreement on A that remains after conditioning on X. A value of zero means X fully determines A, while a value of one means X provides no benefit over the marginal. The factor (n − 1)/(n − dX ) corrects for a bias that arises when dX is large relative to n: with many small groups, even independent attributes show high pdep, and this factor penalizes that effect. Together, ρ close to zero yields µ+ close to one, while ρ ≥ 1 is truncated to µ+ = 0. Two properties of µ+ are relevant here. First, pdep(A, r) normalizes away the marginal distribution of A, so µ+ scores are directly comparable across dependencies with different right-hand sides, a prerequisite for global top-k discovery. Second, µ+ ranks among the top two performers across 14 measures in the comparative study of Parciak et al. [9], with strong robustness to both LHS-uniqueness and RHS-skew. The other top performer, RFI′+ , achieves comparable ranking quality but requires permutation-based estimation and is orders of magnitude slower. Therefore, Parciak et al. recommend µ+ for practical use.
C. Problem Definition We now define the problem studied in this paper, in which neither side of the dependency is fixed. Definition 5 (Global Top-k AFD Discovery). Given a relation instance r over schema R and a positive integer k, let F denote the set of all AFDs over r that are not exact FDs: F = {X → A | X ⊆ R, A ∈ R \ X, µ+ (X → A, r) < 1}. The global top-k AFD discovery problem is to find a subset Fk ⊆ F with |Fk | = min(k, |F |) such that for all f ∈ Fk and f ′ ∈ F \ Fk , µ+ (f, r) ≥ µ+ (f ′ , r). When multiple AFDs share the same µ+ score at the boundary, any selection among them is acceptable. In principle, F includes AFDs with LHS of any size up to m − 1. In practice, we restrict the search to LHS of size at most L, a user-specified parameter. While some largeLHS dependencies may still be meaningful, they are typically harder to inspect and validate. Therefore, L is used as a practical upper bound on the LHS size to control the search space and reduce the burden of human validation. Mandros et al. [8] observed that the average optimal LHS size across 42 datasets is 4.0. As |X| grows, dX approaches n, and the correction factor (n − 1)/(n − dX ) in µ+ heavily penalizes such candidates, making them unlikely to enter the top-k. For any choice of L, the algorithm returns the exact top-k among all AFDs with |X| ≤ L. Increasing L enlarges the search space and may change the result, but the algorithm remains exact within the chosen search depth. The candidate set F excludes exact FDs (µ+ = 1), since including them would fill the top-k list with dependencies that carry no information about data quality issues, leaving genuinely approximate dependencies with no chance to appear in the result. Exact FDs are in any case efficiently handled by existing algorithms [10], [11]. Our problem definition imposes no minimality constraint on the LHS. In classical FD discovery, minimality is natural because an exact FD X → A logically implies X ′ → A for any X ′ ⊃ X. For AFDs this implication does not hold: enlarging the LHS may increase or decrease µ+ , so a nonminimal dependency can score genuinely differently from any of its subsets. Section III shows that dropping minimality is not merely convenient but theoretically necessary. III. I NCOMPATIBILITY OF T OP -k AND M INIMALITY We prove that minimality, global top-k ranking, and exactk output are mutually incompatible under any non-monotonic scoring function. A. Three Properties Consider a relation instance r over schema R, the scoring function µ+ , and a positive integer k, with F as in Definition 5. A result set S ⊆ F should ideally satisfy three properties:
4
(P1) Minimality. Every dependency in S has a minimal LHS: for all X → A ∈ S, there is no X ′ ⊂ X such that X′ → A ∈ F. (P2) Global top-k. The dependencies in S have the k highest µ+ scores among all candidates: for all f ∈ S and f ′ ∈ F \ S, µ+ (f, r) ≥ µ+ (f ′ , r). (P3) Exact-k output. The result contains exactly k dependencies: |S| = k. Each property is individually reasonable, but the following theorem shows they cannot hold simultaneously.
¬(P3)
(P2) Global top-k
¬(P2)
¬(P1)
(P3) Exact-k output
Fig. 2. The Triangle Incompatibility (Theorem III.1). Each edge indicates that enforcing the two connected properties implies the violation of the third.
B. The Incompatibility Theorem Theorem III.1 (Triangle Incompatibility). Let σ be a scoring function such that there exist a relation instance r, a minimal AFD X → A, and a strict superset X ′ ⊃ X with σ(X → A, r) < σ(X ′ → A, r). Then there exist a relation instance and a value of k such that no subset S ⊆ F simultaneously satisfies (P1), (P2), and (P3). Proof. By assumption, there exist a relation instance r, a minimal AFD f1 = X → A with score s1 = σ(f1 , r), and a strict superset X ′ ⊃ X such that f2 = X ′ → A has score s2 = σ(f2 , r) > s1 . Since X ⊂ X ′ and f1 is minimal, f2 is non-minimal. We construct a counterexample with k = 2. Let r be extended with attributes Y and B distinct from those in X ′ ∪ {A}, and let f3 = Y → B,
(P1) Minimality
σ(f3 , r) = s3
be a minimal AFD independent of f1 and f2 , with 0 < s3 < s1 . This is realizable because Y and B are disjoint from X ′ ∪ {A}, so their distributions can be chosen independently without affecting s1 or s2 . We show that no subset S ⊆ {f1 , f2 , f3 } of size 2 satisfies all three properties. (P2) + (P3) ⇒ ¬(P1). The two highest-scoring AFDs are f2 (σ = s2 ) and f1 (σ = s1 ), so the global top-2 is {f2 , f1 }. But f2 is non-minimal since X ⊂ X ′ , violating (P1). (P1) + (P3) ⇒ ¬(P2). The minimal AFDs are f1 and f3 , so the only subset satisfying (P1) with |S| = 2 is {f1 , f3 }. But σ(f3 ) = s3 < s2 = σ(f2 ) and f2 ∈ / S, so S is not the global top-2, violating (P2). (P1) + (P2) ⇒ ¬(P3). To satisfy (P1), S must exclude the non-minimal f2 , so S ⊆ {f1 , f3 }. The only subset of size k = 2 is {f1 , f3 }, which is not the global top-2 since f2 has a higher score than f3 . No subset of size k can therefore satisfy both (P1) and (P2). In all three cases, at least one property is violated, completing the proof.
C. Discussion Figure 2 illustrates the structure of this incompatibility. The incompatibility is inherent in the problem definition, not a limitation of any particular algorithm: regardless of whether minimal AFDs are filtered before, after, or during ranking, the three properties cannot hold simultaneously.
The underlying reason is the absence of monotonicity. For exact FDs, X → A implies X ′ → A for any X ′ ⊃ X, so the larger dependency is redundant and minimality loses no information. For AFDs under µ+ , no such implication exists: a non-minimal dependency X ′ → A can score strictly higher than any of its minimal subsets, so enforcing minimality may discard the globally highest-scoring dependency. On the Adult dataset, {fnlwgt} → sex has µ+ = 0.898, while its strict superset {age, fnlwgt} → sex achieves µ+ = 0.986, and {age, fnlwgt, relationship} → sex reaches µ+ = 0.999 (Section VI). The score increases strictly with LHS size, so µ+ is not monotone under LHS enlargement and the premise of Theorem III.1 holds for this measure. We therefore enforce (P2) and (P3), returning the k highestscoring dependencies with exact output size, and drop (P1), prioritizing the strongest dependencies as measured by µ+ and aligning with the goal of identifying the most significant data quality issues. IV. BASELINE A LGORITHM A. Overview We refer to our approach as TALE (Top-k AFD discovery via Logical Entropy). TALE-Base, the baseline variant presented in this section, evaluates all candidate AFDs exhaustively and is guaranteed to return the exact global top-k result. TALE-Opt, introduced in Section V, builds on this foundation with pruning and computation reuse. TALE-Base enumerates candidates level by level, iterating over LHS sizes ℓ = 1, 2, . . . , L. At each level, it generates all m attribute combinations of size ℓ, pairs each with every ℓ attribute outside the LHS, and computes µ+ for each resulting candidate. A size-k min-heap H maintains the current top-k AFDs throughout. Each candidate requires a full scan of the relation, since the valid tuple set varies depending on which attributes contain NULL values. At the end of the enumeration, H contains the exact global top-k result. The following subsections describe candidate enumeration (Section IV-B), top-k heap maintenance (Section IV-C), and complexity analysis (Section IV-D). Pseudocode of TALEBase is given in Algorithm 1. B. Candidate Enumeration TALE-Base enumerates all dependencies X → A with X ⊆ R, A ∈ R \ X, and |X| ≤ L, filtering out exact FDs (µ+ = 1)
5
Algorithm 1: TALE-Base Input: Relation r over schema R = {A1 , . . . , Am }, integer k, max LHS size L Output: Top-k AFDs ranked by µ+ in descending order 1 H ← empty min-heap of capacity k, keyed on µ+ ; 2 for ℓ = 1 to L do 3 for each X ⊆ R with |X| = ℓ do 4 for each A ∈ R \ X do 5 r ′ ← {t ∈ r | t[B] 6= NULL for all B ∈ X ∪ {A}}; 6 if |r ′ | ≤ 1 then 7 continue; 8 s ← µ+ (X → A, r ′ ); // by Definition 4 9 if s = 1 then 10 continue; // exact FD 11 if |H| < k or s > H.root.score then 12 if |H| = k then 13 remove root of H; 14 insert (X → A, s) into H; 15 return entries of H sorted by µ+ descending;
complexity. The total number of candidates is C = PTime L m + ℓ=1 ℓ ·(m−ℓ). Computing µ for each candidate requires a single scan over the relation to filter NULL values and collect frequency statistics, costing O(n). Each candidate also incurs an O(log k) heap operation. The overall time complexity is O(C · (n + log k)), which simplifies to O(C · n) in typical settings where n ≫ log k. Space complexity. Beyond the input relation, TALE-Base uses O(n) working space for the per-candidate frequency maps (allocated and discarded per candidate, so only one set exists at any time), O(k) for the min-heap, and O(L) for the current LHS combination. The additional space complexity is therefore O(n + k). V. O PTIMIZED A LGORITHM A. Overview
after scoring. At level ℓ, it generates all m ℓ attribute subsets of size ℓ as candidate LHSs, pairing each with every attribute in R \ X to yield m ℓ × (m − ℓ) candidates at that level. The total number of candidates across all levels is L X m · (m − ℓ). ℓ ℓ=1
LHS combinations are generated in lexicographic order. Each X is processed immediately: all (m − ℓ) candidates sharing that LHS are evaluated and passed to H, after which X is discarded. Only the current combination and H are kept in memory at any time. For each candidate X → A, TALE-Base makes a single pass over the relation, filtering tuples with NULL values in X ∪ {A}, building the LHS-to-RHS frequency distribution, and computing pdep and µ+ . Any candidate with µ+ = 1 is an exact FD and is excluded. C. Top-k Heap Maintenance TALE-Base maintains a min-heap H of capacity k, keyed on µ+ , whose root holds the current minimum score among the top-k candidates. Two operations are performed on H. Insertion. When a new candidate X → A is evaluated, it is inserted directly if H has fewer than k entries. If H is full and the candidate’s µ+ exceeds the root score, the root is replaced. Otherwise the candidate is discarded. Each insertion takes O(log k) time. Threshold query. The root score serves as a dynamic threshold τ : any candidate with µ+ ≤ τ cannot enter the topk. In TALE-Base every candidate is evaluated before this comparison, so τ only saves the heap insertion cost. Its more important role is in TALE-Opt (Section V), where it enables pruning entire branches without computing µ+ . At the end of the enumeration, H contains min(k, |F |) AFDs. These are extracted in descending order of µ+ to produce the final result. D. Complexity Analysis Let m denote the number of attributes, n the number of tuples, L the maximum LHS size, and k the desired output size.
TALE-Opt reduces the exhaustive computation of TALEBase through techniques at three levels. The search level. The independent combinatorial enumeration is replaced by an Apriori-style candidate generation scheme [12]. Candidates at level ℓ + 1 are produced by joining pairs from level ℓ that share a common prefix, so pruning decisions made at level ℓ reduce the candidates evaluated at deeper levels. The computation level. For a fixed X, the LHS hash values and NULL flags are identical across all candidates X → A and are computed once, eliminating (m − ℓ − 1) redundant passes over the LHS. The pruning level. Two complementary rules remove RHS attributes from consideration. Exact FD pruning exploits monotonicity: if X → A is exact (µ+ = 1), then X ′ → A is also exact for any X ′ ⊃ X, so all such descendants can be removed for RHS A. Upper bound pruning targets nonexact descendants via an optimistic upper bound on µ+ that decreases monotonically as dX grows. When the bound falls below the current heap threshold τ , entire branches are pruned. The bound is strict under the no-NULL assumption; a heuristic extension for datasets with missing values is discussed in Section V-E. Algorithm 2 gives the pseudocode for the complete optimized algorithm TALE-Opt. The following subsections describe each technique in detail. B. Apriori-style Candidate Generation In TALE-Base, each level ℓ generates candidates independently by enumerating all m subsets of R of size ℓ, so a ℓ pruned candidate at level ℓ still has its supersets generated at level ℓ + 1. TALE-Opt replaces this with an Apriori-style scheme: candidates at level ℓ + 1 are derived from level ℓ by a join, so a candidate pruned at level ℓ produces no descendants. Concretely, let Lℓ denote the surviving LHS candidates at level ℓ. To generate Lℓ+1 , candidates in Lℓ are grouped by their first ℓ − 1 attributes (the prefix); within each group, every pair whose last attributes differ is joined to produce a candidate of size ℓ + 1. For example, {A1 , A3 } and {A1 , A5 } in L2 join to produce {A1 , A3 , A5 } ∈ L3 .
6
Algorithm 2: TALE-Opt Input: Relation r over schema R = {A1 , . . . , Am }, integer k, max LHS size L Output: Top-k AFDs ranked by µ+ in descending order + 1 H ← empty min-heap of capacity k, keyed on µ ; 2 τ ← 0; 3 L1 ← {Ai } : Ai ∈ R ; 4 for each X ∈ L1 do 5 S(X) ← R \ X; 6 for ℓ = 1 to L do 7 for each X ∈ Lℓ do 8 compute and cache lhsHash[i], lhsValid[i] for all tuples; 9 for each A ∈ S(X) do 10 compute s ← µ+ (X → A, r) using cached LHS arrays; 11 if s = 1 then 12 remove A from S(X); // FD pruning 13 else 14 if s > τ then 15 insert or update H with (X → A, s); 16 τ ← H.root.score; + 17 if µopt (X → A, r) ≤ τ then 18 remove A from S(X); // UB pruning 19 if ℓ < L then 20 Lℓ+1 ← ∅; 21 for each ordered pair X1 , X2 ∈ Lℓ sharing (ℓ−1)-prefix do 22 X ′ ← X1 ∪ X2 ; 23 S(X ′ ) ← S(X1 ) ∩ S(X2 ); 24 if S(X ′ ) 6= ∅ then 25 add X ′ to Lℓ+1 ; 26 return entries of H sorted by µ+ descending;
Apriori-style generation alone does not reduce the candidate space. It provides the structure through which pruning decisions propagate to descendants. The benefit appears when pruning rules remove candidates from Lℓ , causing a cascading reduction in Lℓ+1 and beyond. C. LHS Computation Reuse For a given LHS X of size ℓ, TALE-Base evaluates m − ℓ candidates X → A, each requiring an independent scan to compute the LHS hash and check for NULL values in X. Since X is fixed across all these evaluations, the per-tuple LHS work is repeated unnecessarily. TALE-Opt maintains two global arrays of size n: lhsHash[i], which stores the hash of the i-th tuple on the LHS attributes, and lhsValid[i], which records whether all LHS attributes of the i-th tuple are non-NULL. Both are computed once when a new X is first processed and reused for all m − ℓ RHS evaluations. RHS-specific frequency counts are maintained separately for each A, but the tuple-side preprocessing on X is shared. When processing a subsequent RHS attribute A, the scan checks only whether t[A] is NULL; the LHS hash and NULL status are read from the cached arrays, reducing the per-tuple LHS preprocessing cost from O(ℓ) to O(1) for all but the first RHS. The asymptotic saving in LHS-side preprocessing is O((m−ℓ−1)·n·ℓ) per LHS candidate. The factor ℓ reflects the per-tuple cost saved by caching, while (m − ℓ − 1) counts the number of RHS evaluations that benefit from reuse. D. Pruning Framework and Exact FD Pruning Each LHS candidate X is associated with an RHS candidate set S(X) ⊆ R \ X, tracking which RHS attributes still need
evaluation for X and its descendants. S(X) is implemented as a bit vector of m bits, where bit i is set if and only if Ai is still a candidate RHS. When a pruning rule determines that A is unnecessary, it removes A from S(X). Initialization. At level 1, each single-attribute candidate X = {Ai } is initialized with S(X) = R \ {Ai }. Exact FD pruning. After evaluating all RHS attributes in S(X) for a given LHS X, every attribute A for which X → A is exact (µ+ = 1) is removed from S(X). Exact FD satisfaction is closed under LHS enlargement: if X → A holds exactly, then X ′ → A holds exactly for any X ′ ⊃ X. Since exact FDs are excluded from the top-k result, every descendant X ′ ⊃ X with RHS A would also be exact and thus excluded. Removing A from S(X) is therefore safe. Propagation through Apriori join. When X1 , X2 ∈ Lℓ are joined to produce X ′ = X1 ∪ X2 ∈ Lℓ+1 , the RHS candidate set of X ′ is initialized as S(X ′ ) = S(X1 ) ∩ S(X2 ). If A has been removed from S(X1 ) by exact FD pruning or by the upper-bound rule of Section V-E, then X ′ → A need not be evaluated: since X ′ ⊃ X1 , if X1 → A is exact then X ′ → A is also exact, and if the upper bound for X1 falls below τ then so does the upper bound for X ′ . The same applies to S(X2 ). If S(X ′ ) = ∅, X ′ is discarded without being added to Lℓ+1 . Intersection and emptiness testing both cost O(⌈m/w⌉) where w is the word size, and the cost can be reduced to O(1) for schemas where the bit vector fits in one machine word. E. Optimistic Upper Bound Pruning Exact FD pruning targets attributes with µ+ = 1. A second rule targets attributes for which no descendant can score high enough to enter the top-k. It also operates by removing attributes from S(X), and the propagation mechanism of Section V-D applies without modification. We first derive a strict upper bound under the no-NULL assumption, then discuss a heuristic extension for datasets with missing values. Derivation under no-NULL assumption. When there are no NULL values, every candidate operates on the full relation of n tuples, and pdep(A, r) is a constant for each RHS attribute A. From Definition 4, µ+ (X → A, r) = 1 − ρ(X → A, r), 1 − pdep(X → A, r) n − 1 . · ρ(X → A, r) = 1 − pdep(A, r) n − dX To derive an upper bound on µ+ , we seek a lower bound on ρ. Consider any descendant X ′ ⊃ X such that X ′ → A is not an exact FD. Since X ⊂ X ′ , each distinct X ′ -value determines a unique X-value, so dX ′ ≥ dX . It follows that (n − 1)/(n − dX ′ ) ≥ (n − 1)/(n − dX ), so the second factor of ρ does not decrease. For the first factor, X ′ → A being non-exact means that there exist at least two tuples t1 , t2 ∈ r with t1 [X ′ ] = t2 [X ′ ] but t1 [A] 6= t2 [A]. The scenario that minimizes ρ (and thus
7
maximizes µ+ ) is when the dependency is as close to exact as possible. This occurs when X ′ → A is violated by exactly one pair of tuples that share the same X ′ -value but disagree on A, while all other X ′ -values have a unique corresponding A-value. By Definition 3, the contribution of this exception to pdep(X ′ → A, r) drops by exactly 1/n compared to the fully exact case, giving pdep(X ′ → A, r) = 1 − 1/n and 1 − pdep(X ′ → A, r) = 1/n. Substituting into ρ gives the minimum value of ρ over all non-exact descendants with dX ′ distinct LHS values, n−1 1 · n · (1 − pdep(A, r)) n − dX ′ n−1 = . n · (1 − pdep(A, r)) · (n − dX ′ )
ρmin (dX ′ ) =
Since dX ′ ≥ dX , we have ρmin (dX ′ ) ≥ ρmin (dX ). This leads to the following bound. Theorem V.1 (Optimistic Upper Bound). Assume the relation contains no NULL values, dX < n, and pdep(A, r) < 1. For any X ′ ⊃ X such that X ′ → A is not an exact FD, µ+ (X ′ → A, r) ≤ µ+ opt (X → A, r) =1−
n−1 . n · (1 − pdep(A, r)) · (n − dX )
Moreover, µ+ opt is monotonically decreasing in dX . Proof. For any non-exact descendant X ′ ⊃ X with dX ′ ≥ dX , 1 − pdep(X ′ → A, r) n−1 · 1 − pdep(A, r) n − dX ′ n−1 1 · ≥ n · (1 − pdep(A, r)) n − dX ′ n−1 ≥ n · (1 − pdep(A, r)) · (n − dX )
ρ(X ′ → A, r) =
where the first inequality uses pdep(X ′ → A, r) ≤ 1 − 1/n (the tightest bound for a non-exact FD) and the second uses dX ′ ≥ dX . Therefore µ+ (X ′ → A, r) = 1 − ρ(X ′ → A, r) ≤ 1 − ρmin (dX ) = µ+ opt (X → A, r). Monotonicity follows because increasing dX decreases (n − dX ), increasing ρmin and decreasing µ+ opt . Pruning rule. This rule applies to non-exact candidates, complementing the exact FD pruning of Section V-D. When µ+ = 1, the candidate is handled by exact FD pruning and µ+ opt is not evaluated. This also avoids the degenerate cases dX = n and pdep(A, r) = 1 where the denominator of µ+ opt is zero. For candidates with µ+ < 1, if µ+ opt (X → A, r) ≤ τ , no non-exact descendant of X with RHS A can enter the topk, and A is removed from S(X). Computing µ+ opt requires only dX and pdep(A, r), both available from the evaluation of X → A, so the additional cost is O(1) per candidate. Since µ+ opt decreases monotonically in dX , upper bound pruning is compatible with the propagation mechanism of Section V-D: if A is removed from S(X1 ) because µ+ opt (X1 → A, r) ≤ τ , then for any X ′ ⊃ X1 , dX ′ ≥ dX1 implies ′ ′ µ+ opt (X → A, r) ≤ τ , so S(X ) = S(X1 ) ∩ S(X2 ) correctly excludes A.
Effectiveness across levels. The upper bound depends on the ratio (n−1)/[n·(1−pdep(A, r))·(n−dX )]. When dX is small relative to n, µ+ opt stays close to 1 and pruning has little effect. Pruning becomes increasingly aggressive at deeper levels as dX grows. Extension to datasets with NULL values. When NULL values are present, different candidates may operate on different valid tuple sets, so both n and pdep(A, r) vary across candidates and the bound of Theorem V.1 is no longer guaranteed to hold strictly. We apply it heuristically, using the n and pdep(A, r) values of the current candidate. On all tested datasets, the top-k results with and without this heuristic are identical, suggesting the approximation is reliable in practice. For applications requiring absolute correctness guarantees, this pruning rule can be disabled without affecting the remainder of the algorithm. VI. E XPERIMENTAL E VALUATION We evaluate TALE-Base and TALE-Opt on 41 real-world datasets spanning a wide range of sizes and dimensionalities, with the goal of assessing pruning effectiveness, scalability, and the semantic quality of the discovered dependencies. A. Experimental Setup All algorithms are implemented in Java (JDK 21) and executed on a workstation with an Intel Core i9-13900 CPU (2.00 GHz, 24 cores) and 64 GB of main memory, running Windows 11. All reported times are wall-clock times of singlethreaded execution. A time limit of 48 hours is imposed. The executions that do not complete within this limit are marked with >48h. We compare two variants: TALE-Base (Algorithm 1), which exhaustively evaluates all candidates, and TALE-Opt (Algorithm 2), which adds Apriori-style candidate generation, LHS computation reuse, exact FD pruning, and optimistic upper bound pruning. To our knowledge, no prior algorithm addresses the global top-k AFD discovery problem as formulated in Definition 5. We do not compare against Mandros et al. [8] because the two methods address different problems: their method fixes the RHS and returns top-k LHS subsets for a single target, whereas TALE returns a global top-k across all attribute combinations. Moreover, their branch-and-bound strategy relies on an optimistic estimator specific to a fixed RHS; under µ+ and the global formulation, no analogous single bounding function exists across different RHS attributes, and the upper bound µ+ opt in Section V-E was derived specifically for the level-wise global search. Unless otherwise stated, k = 20 and L = 5. We use 41 publicly available datasets from the UCI Machine Learning Repository1 and Kaggle2 , covering a wide range of sizes (|r| from 155 to 2,075,259), dimensionalities (|R| from 7 to 109), and application domains. Dataset details and experimental results are given in Table I. Handling of NULL values. NULL values arise naturally during data collection, integration, and maintenance. We adopt 1 https://archive.ics.uci.edu/ 2 https://www.kaggle.com/
8
TABLE I OVERALL PERFORMANCE OF TALE-BASE AND TALE-O PT ON 41 REAL - WORLD DATASETS (k = 20, L = 5, TIME LIMIT 48 HOURS ). #ECN: NUMBER OF EVALUATED CANDIDATES . PR ATIO : FRACTION OF CANDIDATES PRUNED BY TALE-O PT RELATIVE TO TALE-B ASE . Dataset
|r|
|R|
Abalone Adult AI4I 2020 Air Quality Bank Marketing Appliances Energy Bike Sharing Clickstream Coupon Recommendation Credit Card Dry Bean Flight Gas Turbine Hepatitis Household Power Image Segmentation Incident Management Iranian Churn Letter Recognition Magic Gamma telescope MathE Metro Traffic MetroPT-3 Mushroom Mushroom (secondary) NHANES Nursery Obesity Occupancy OpenFDA Drug Parkinsons Plista Poker Hand Product Classification Rice Spambase South German Credit Steel Industry Steel Plates Superconductivity WDBC Wine Quality
4177 32561 10000 9357 45211 19735 17379 165474 12684 30000 13611 1000 36733 155 2075259 2100 141712 3150 20000 19020 9546 48204 1516948 8124 61069 2278 12960 2111 10129 1000 5875 1001 1000000 35311 3810 4601 1000 35040 1941 21263 569 4898
9 15 14 15 17 29 17 14 26 25 17 109 11 20 9 20 36 14 17 11 8 9 17 23 21 10 9 17 19 39 22 63 11 7 8 58 21 11 34 82 32 12
TALE-Base Time[s] #ECN 1.06 1962 130.28 52080 33.35 33306 63.42 52080 504.03 117028 11818.69 3550673 246.19 117028 533.57 33306 428.63 1778530 8261.13 1386350 279.78 117028 52135.27 12757176117 54.97 7007 2.47 333260 843.02 1962 71.11 333260 122223.16 13830012 7.38 33306 133.14 117028 23.90 7007 0.55 952 10.57 1962 37956.08 117028 118.07 815166 748.97 455679 0.99 3810 0.42 1962 18.84 117028 175.24 239685 339.04 22812426 442.49 613690 2591.75 445323060 349.72 7007 3.21 434 0.66 952 63696.08 267555682 22.53 455679 34.99 7007 1734.17 9665282 >48h 2244666114 334.61 6603744 5.95 12276
ignore-NULL semantics for all experiments. An AFD X → A is evaluated only on tuples with non-NULL values on all attributes in X ∪ {A}, consistent with recent work on AFD discovery [9]. B. Overall Performance Table I reports running times and evaluated candidate counts (#ECN) for both variants, together with the speedup and pruning ratio (PRatio) of TALE-Opt, on all 41 datasets (k = 20, L = 5). TALE-Base completes on 40 of 41 datasets within the 48-hour limit. Only Superconductivity (|R| = 82) exceeds it; TALE-Opt completes on all 41 datasets, finishing Superconductivity in under two hours (6,492 seconds). The per-level speedup on Superconductivity grows from 1.25× at level 1 to 3.51× at level 2 and 25.43× at level 3, consistent with the theoretical behavior of the upper bound: as ℓ increases, dX grows toward n, µ+ opt decreases rapidly, and pruning triggers on a rapidly growing fraction of the candidate space. PRatio ranges from 0% to 99.81% across the 41 datasets, driven primarily by data structure rather than dataset size.
TALE-Opt Time[s] #ECN 1.03 1763 91.91 48200 17.02 29645 15.03 15262 383.53 112971 7539.76 3375632 151.54 104791 197.12 19883 262.77 1502951 6059.55 1386350 3.55 1374 1468.64 51878348 16.66 1976 1.55 214449 694.19 1962 12.25 64256 23706.01 2197947 3.43 17616 107.71 117028 4.42 1605 0.34 655 7.50 1347 23150.57 110242 79.50 759018 393.97 265863 0.83 3456 0.48 1962 16.08 114624 108.71 223768 38.10 1699083 28.39 64312 179.45 5413737 293.28 7007 1.42 312 0.47 882 42423.48 235494705 14.21 386063 19.19 6406 63.07 551157 6492.27 4366203 174.71 6112655 3.55 9181
Speedup
PRatio
1.03 1.42 1.96 4.22 1.31 1.57 1.62 2.71 1.63 1.36 78.81 35.50 3.30 1.59 1.21 5.81 5.16 2.15 1.24 5.41 1.62 1.41 1.64 1.49 1.90 1.19 0.88 1.17 1.61 8.90 15.58 14.44 1.19 2.26 1.40 1.50 1.59 1.82 27.50 >17.7 1.92 1.68
10.14% 7.45% 10.99% 70.70% 3.47% 4.93% 10.46% 40.30% 15.49% 0.00% 98.83% 99.59% 71.80% 35.65% 0.00% 80.72% 84.11% 47.11% 0.00% 77.10% 31.20% 31.35% 5.80% 6.89% 41.66% 9.29% 0.00% 2.05% 6.64% 92.55% 89.52% 98.78% 0.00% 28.11% 7.35% 11.98% 15.28% 8.58% 94.30% 99.81% 7.43% 25.21%
At one extreme, Dry Bean (98.83%), Flight (99.59%), Plista (98.78%), Superconductivity (99.81%), Steel Plates (94.30%), and Incident Management (84.11%) all exceed 84% pruning. In these datasets, many LHS combinations produce dX values large relative to n, driving µ+ opt below τ at shallow levels. High dimensionality relative to |r| amplifies this effect: for Flight (|R| = 109, |r| = 1,000), Plista (|R| = 63, |r| = 1,001), and OpenFDA Drug (|R| = 39, |r| = 1,000), dX approaches n after adding even a single attribute to the LHS. Five datasets (Credit Card, Household Power, Letter Recognition, Nursery, and Poker Hand) show zero pruning. These datasets contain no exact FDs among evaluated candidates, so exact FD pruning has no effect. The top-k heap fills with lowscoring entries early, keeping τ near zero throughout the search and preventing the upper bound from triggering. Household Power and Poker Hand have narrow schemas (|R| = 9 and 11), further limiting the candidate space. Most datasets fall between these extremes, with PRatio between 10% and 85% and speedups between 1.2× and 6×. Nursery is the only dataset where TALE-Opt is marginally
1 0.1 0.01 3
4
5
6
Search depth L
1
2
3
10000
4
5
6
T OP -k LIST OVERLAP BETWEEN CONSECUTIVE VALUES OF L (k = 20). Dry Bean 5% 80% 95% 100% 100%
Air Quality 0% 0% 100% 100% 100%
Flight 0% 0% 0% 100% 100%
slower than TALE-Base (0.48s vs. 0.42s): the Apriori generation overhead outweighs any pruning benefit on this small dataset with no prunable candidates. On all other datasets TALE-Opt matches or outperforms TALE-Base. Summary. TALE-Opt achieves a positive speedup on 40 of 41 datasets. Pruning is most effective where exhaustive evaluation is most expensive: high-dimensional schemas where dX grows rapidly with LHS size, causing upper bound pruning to activate aggressively at deeper levels and reducing the evaluated candidate count by one to three orders of magnitude. C. Effect of Search Depth The parameter L bounds the LHS size of discovered AFDs; a larger L enlarges the search space and may improve result quality at the cost of longer running time. We evaluate TALEOpt on four representative datasets with L from 1 to 6, keeping k = 20 fixed. Figure 3 reports execution time and heap threshold τ ; Table II reports the overlap between consecutive top-k lists. Result quality converges well before L = 5 on all four datasets. On Dry Bean, τ stabilizes at L = 2 and the top-k list reaches 100% overlap at L = 4, with no further change through L = 6. On Air Quality, both τ and the top-k list stabilize at L = 3, with 100% overlap from L = 3 onward. On Flight, convergence occurs at L = 4, with 100% overlap between L = 4 and L = 5. On Adult, τ continues to increase at every level but the increments diminish rapidly: +0.773 at L = 2, +0.088 at L = 3, +0.013 at L = 4, +0.002 at L = 5, and +0.0005 at L = 6; the overlap between L = 5 and L = 6 is 70% and τ differs by less than 0.001, indicating near-convergence. Running time grows with L but at different rates across datasets. On Dry Bean, cumulative time at L = 5 is only 3.43 seconds and remains unchanged at L = 6, reflecting near-complete pruning at deeper levels. On Air Quality, time grows from 1.74 seconds at L = 2 to 15.26 seconds at L = 5. On Adult, time grows from 2.05 seconds at L = 2 to 96.13 seconds at L = 5 and 180.49 seconds at L = 6. Flight
40
0 10 20
40
60
80
100
10 20
Percentage of tuples (%)
70000
60
80
100
(b) PRatio vs. n (MetroPT-3) 100
TALE-Base TALE-Opt
60000
40
Percentage of tuples (%)
(a) Time vs. n (MetroPT-3)
(b) Heap threshold
TABLE II
60
20
0
Fig. 3. Effect of search depth L on running time and heap threshold (k = 20).
Adult 5% 5% 15% 30% 70%
20000
Search depth L
(a) Execution time
L → L+1 1→2 2→3 3→4 4→5 5→6
30000
TALE-Opt
80
50000
PRatio (%)
2
TALE-Opt
80
40000 30000 20000
60 40 20
10000 0
0 10
20 30 40 50 Number of attributes
58
10
(c) Time vs. m (Spambase)
20 30 40 50 Number of attributes
58
(d) PRatio vs. m (Spambase)
160
100
TALE-Opt
80
120
PRatio (%)
1
Adult Dry Bean Air Quality Flight
100
TALE-Base TALE-Opt
40000
PRatio (%)
10
Running time (seconds)
100
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
Running time (seconds)
Adult Dry Bean Air Quality Flight
1000
Running time (seconds)
10000
Heap threshold τ
Running time (seconds)
9
80 40
5
10 20 50 Number of results k
(e) Time vs. k (Adult)
40 20
TALE-Base TALE-Opt
0
60
0 100
5
10 20 50 Number of results k
100
(f) PRatio vs. k (Adult)
Fig. 4. Scalability of TALE-Base and TALE-Opt with respect to n, m, and k (k = 20 for n and m experiments, L = 5 throughout).
is the most expensive dataset due to its 109 attributes, with cumulative time reaching 1,469 seconds at L = 5 and 7,653 seconds at L = 6; the top-k result does not change between these two levels, so the additional 6,184 seconds yield no benefit. We adopt L = 5 as the default, since across all four datasets it either achieves the fully converged result or is within 0.001 of it in τ , consistent with the finding of Mandros et al. [8] that the average optimal LHS size across 42 datasets is 4.0. Users may reduce L for faster execution on wide schemas, or increase it when deeper completeness is needed. D. Scalability We evaluate scalability with respect to n, m, and k. For n, we use MetroPT-3 (|r| = 1,516,948, |R| = 17), sampled at six fractions from 10% to 100%. For m, we use Spambase (|r| = 4,601, |R| = 58), selected for its high dimensionality. For k, we use Adult (|r| = 32,561, |R| = 15), where the effect of k on pruning is clearly observable. Figure 4 reports running time and PRatio for each experiment; k = 20 and L = 5 unless otherwise stated. Varying n (MetroPT-3). TALE-Base grows from 2,869 seconds at 10% to 37,956 seconds at 100%, and TALE-Opt from 1,229 to 23,151 seconds. Both curves grow approximately linearly with n (Figure 4(a)), as the candidate count depends only on m and L, so total running time scales proportionally with n. PRatio decreases monotonically from 24.82% to 5.80% (Figure 4(b)): as n grows, dX grows more slowly, keeping (n − dX ) large and µ+ opt high, making the pruning condition
10
TABLE III E FFECT OF INDIVIDUAL OPTIMIZATION COMPONENTS (k = 20, L = 5). T IME IS IN SECONDS . PR ATIO IS COMPUTED RELATIVE TO THE THEORETICAL CANDIDATE COUNT. Variant TALE-Base TALE-A TALE-A+R TALE-A+R+E TALE-Opt
Time(s) 442.49 435.93 225.07 69.72 28.39
Parkinsons #ECN PRatio 613,690 — 613,690 0.00% 613,690 0.00% 194,127 68.37% 64,312 89.52%
Air Quality Time(s) #ECN PRatio 63.42 52,080 — 66.41 52,080 0.00% 57.40 52,080 0.00% 44.54 42,124 19.12% 15.03 15,262 70.70%
harder to satisfy. The number of exact FDs also decreases with n (from 8,129 at 10% to 637 at 100%), further reducing exact FD pruning. Varying m (Spambase). Running time grows super-linearly with m as the candidate space expands combinatorially. TALEBase increases from 0.88 seconds at m = 10 to 63,696 seconds at m = 58, roughly 72,000× (Figure 4(c)). TALE-Opt follows a similar trend but the gap widens from m = 40 onward, reaching approximately 21,000 seconds at m = 58. PRatio is zero for m ≤ 30 (Figure 4(d)): Spambase contains no exact FDs at small schema sizes and the upper bound remains above τ . Exact FDs appear at m = 40 (1,747 FDs), and PRatio rises to 11.98% at m = 58 as both pruning rules become effective. Varying k (Adult). TALE-Base is insensitive to k: running time stays between 125 and 131 seconds and #ECN is fixed at 52,080 across all tested values (Figure 4(e)), as exhaustive evaluation covers all candidates regardless of k. TALE-Opt shows a mild increase from 85.39 seconds at k = 5 to 100.59 seconds at k = 100, with PRatio falling from 11.44% to 4.90% (Figure 4(f)): a larger k requires a lower τ , weakening the upper bound pruning condition. TALE-Opt remains faster than TALE-Base at every tested k, with speedups from 1.47× at k = 5 to 1.28× at k = 100. E. Effect of Individual Optimization Components Table III reports running time, #ECN, and PRatio for five variants on four datasets with distinct pruning characteristics: Parkinsons (PRatio 89.52%), Air Quality (70.70%), Adult (7.45%), and Letter Recognition (0.00%). Starting from TALE-Base, each variant adds one component: TALE-A adds Apriori-style candidate generation, TALE-A+R adds LHS computation reuse, TALE-A+R+E adds exact FD pruning, and TALE-Opt adds optimistic upper bound pruning. Apriori-style generation. TALE-A and TALE-Base evaluate the same number of candidates on all four datasets: Aprioristyle generation alone does not reduce the candidate space but provides the propagation structure through which pruning decisions reach descendant LHS candidates. The running time difference is negligible. LHS computation reuse. TALE-A+R reduces running time substantially without changing #ECN: on Parkinsons from 435.93 to 225.07 seconds (48.4%); on Air Quality from 66.41 to 57.40 seconds (13.6%); on Adult from 130.65 to 104.71 seconds (19.9%); on Letter Recognition from 130.28 to 104.77 seconds (19.6%). The larger saving on Parkinsons reflects its higher dimensionality (|R| = 22), where reusing LHS hash values across more RHS attributes yields greater benefit.
Time(s) 130.28 130.65 104.71 104.30 91.91
Adult #ECN PRatio 52,080 — 52,080 0.00% 52,080 0.00% 49,717 4.54% 48,200 7.45%
Letter Recognition Time(s) #ECN PRatio 133.14 117,028 — 130.28 117,028 0.00% 104.77 117,028 0.00% 106.53 117,028 0.00% 107.71 117,028 0.00%
Exact FD pruning. The effect of TALE-A+R+E depends on the number of exact FDs in each dataset. On Parkinsons (3,353 exact FDs), #ECN drops from 613,690 to 194,127 (PRatio 68.37%) and time from 225.07 to 69.72 seconds. On Air Quality, 18,406 exact FDs exist but their supersets cover fewer candidates, giving PRatio 19.12% and time reduction from 57.40 to 44.54 seconds. On Adult (2,431 exact FDs), PRatio reaches only 4.54% and time changes minimally. On Letter Recognition, no exact FDs exist and #ECN is unchanged; the slight time increase (104.77 to 106.53 seconds) comes from BitSet maintenance overhead. Optimistic upper bound pruning. TALE-Opt provides the largest reduction where exact FD pruning alone leaves substantial candidates. On Parkinsons, #ECN falls from 194,127 to 64,312, pushing PRatio to 89.52% and time to 28.39 seconds. On Air Quality, upper bound pruning dominates: PRatio rises from 19.12% to 70.70% and time drops from 44.54 to 15.03 seconds (66.3%). On Adult, PRatio reaches 7.45% and time decreases from 104.30 to 91.91 seconds. On Letter Recognition, neither pruning rule triggers; TALEOpt finishes in 107.71 seconds, close to TALE-A+R (104.77 seconds), where LHS reuse is the sole source of speedup. All variants return identical top-k results to TALE-Base on all four datasets, confirming that the pruning rules are safe. Summary. The four components target different sources of inefficiency. LHS reuse reduces per-candidate computation cost universally. Exact FD pruning is most effective when the data contains many exact FDs whose supersets can be eliminated without evaluation. Upper bound pruning dominates on datasets with strong approximate dependencies, activating when τ is high enough to cut off entire subtrees. Where neither pruning condition triggers, LHS reuse remains the primary source of speedup. F. Case Study We examine the top-k results on three datasets: Dry Bean (agricultural morphology), WDBC (medical diagnosis), and AI4I 2020 (industrial predictive maintenance). For each dataset, we select representative AFDs from the top-20 to illustrate patterns visible only through global discovery. Table IV lists the selected AFDs and their semantic significance. Dry Bean. The top-20 results fall into two groups. Ranks 1–11 predict bean variety (Class) from morphological shape features, all at µ+ = 0.983. Rank 4, (roundness) → Class, is the most informative: a single shape descriptor nearly determines the variety, so a record whose roundness is inconsistent with its declared variety is a strong candidate for a labeling
11
TABLE IV R EPRESENTATIVE TOP -k AFD S AND THEIR SEMANTIC SIGNIFICANCE ACROSS THREE DOMAINS (k = 20, L = 5). I N WDBC, CP 1 AND CV 3 ABBREVIATE concave points1 AND concavity3; IN AI4I 2020, T WEAR , M FAIL , P TEMP, AND R SPEED ABBREVIATE Tool wear, Machine failure, Process temperature, AND Rotational speed. Dataset
|r|
Rank 4 3 Dry Bean 13,611 12 14 1 4 WDBC 569 15 16 1 2 AI4I 2020 10,000 4 14
AFD (roundness) → Class (ConvexArea, Solidity ) → Class (Extent, Class) → Area (Area, Extent) → Compactness (cp1 ) → Diagnosis (perimeter1 ) → Diagnosis (Diagnosis, cv3 ) → cp1 (Diagnosis, cp1 ) → cv3 (T wear , M fail, TWF , HDF , PWF ) → OSF (Type, R speed, M fail, PWF , OSF ) → HDF (Torque, M fail, HDF , PWF , OSF ) → TWF (P temp, T wear , M fail, PWF ) → HDF
error. Rank 3 shows that ConvexArea and Solidity jointly achieve the same strength, characterizing how shape compactness varies across bean types. Ranks 12–20 show geometric consistency constraints, such as (Extent , Class) → Area and (Area, Extent) → Compactness; violations here indicate measurement inconsistencies rather than labeling errors. WDBC. The Wisconsin Diagnostic Breast Cancer dataset contains 30 numerical features computed from cell nucleus images. Ranks 1–14 all predict Diagnosis (benign or malignant) from individual or combined morphological features. The top dependency, concave points1 → Diagnosis, achieves µ+ = 0.763, identifying the worst concave points of the nucleus as the strongest single predictor. Rank 4 shows perimeter1 reaching µ+ = 0.667 independently, so tumor boundary length carries nearly comparable diagnostic signal. Ranks 15– 20 shift direction: Diagnosis now appears on the left-hand side, predicting morphological features such as concave points1 and concavity3. A fixed-RHS method targeting Diagnosis as the dependent attribute would suppress these entirely. Their appearance in the top-20 shows that diagnosis, combined with one morphological feature, strongly constrains others, relevant to consistency checking in clinical records. AI4I 2020. The AI4I 2020 dataset records sensor readings and failure modes for an industrial milling machine, with five binary failure indicators: TWF (tool wear failure), HDF (heat dissipation failure), PWF (power failure), OSF (overstrain failure), and RNF (random failure). The top-20 results span multiple right-hand sides: OSF appears in ranks 1 and 5–9, HDF in ranks 2–3 and 11–19, TWF in ranks 4, 10, and 13. Rank 1, (Tool wear , Machine failure, TWF , HDF , PWF ) → OSF (µ+ = 0.995), shows that the co-occurrence of multiple concurrent failure conditions is a near-deterministic predictor of overstrain failure. Rank 2 shows that machine type, rotational speed, and concurrent failures jointly predict heat dissipation failure. Rank 14, (Process temp, Tool wear , Machine failure, PWF ) → HDF (µ+ = 0.985), shows that process temperature combined with tool wear indicates heat dissipation risk without requiring knowledge of other failure states. Across all three datasets, dependencies where the analyst’s target attribute appears on the left-hand side, or where the most informative predictor is not the obvious candidate, appear con-
µ+ 0.983 0.983 0.972 0.971 0.763 0.667 0.500 0.500 0.995 0.994 0.988 0.985
Semantic Significance Single shape feature predicts bean variety Shape compactness jointly determines variety Variety and fill ratio constrain bean size Geometric consistency among morphological measurements Worst concave points strongly predict malignancy Tumor perimeter independently predicts diagnosis Diagnosis and concavity jointly constrain concave points Reverse dependency invisible to fixed-RHS methods Concurrent failures predict overstrain failure Machine type and speed predict heat dissipation failure Torque with concurrent failures predicts tool wear failure Temperature and tool wear indicate heat dissipation risk
sistently in the top-k results. A fixed-RHS approach requires the analyst to commit to a target attribute before discovery begins; the global formulation removes this requirement and returns a unified ranking that can be inspected directly. VII. R ELATED WORK A. Data Profiling Dependency discovery is a core task within data profiling [13], [14], which extracts metadata and structural properties from datasets, including single-column statistics, unique column combinations, functional dependencies, and inclusion dependencies, with downstream applications in data quality assessment, schema understanding, and data integration. Traditional profiling algorithms return complete result sets; when the number of attributes is large, the output can contain thousands of dependencies. A global top-k ranking reduces this to a fixed-size result ordered by dependency strength. B. Functional Dependency Discovery Discovering the complete set of minimal non-trivial FDs from a relation instance has been studied extensively, and the algorithms can be grouped into three families. Attribute-oriented algorithms traverse the attribute lattice to enumerate and validate candidates. TANE [15] performs a level-wise traversal using stripped partitions and applies inference rules for pruning; FUN [16] and FD Mine [17] follow a similar enumeration with additional pruning conditions. DFD [18] handles each RHS attribute independently through a depth-first walk. Tuple-oriented algorithms derive dependencies from pairwise tuple comparisons. FDEP [19] and Dep-Miner [20] compute agree sets or difference sets and extract FDs from these structures. FastFDs [21] reduces cost by searching difference sets in a heuristic depth-first order. FSC [10] addresses largescale FD discovery by precomputing comparable pairs to avoid redundant tuple comparisons. Hybrid algorithms combine elements of both families. HyFD [22] uses sampled tuple pairs to generate candidates and validates them through partition-based checks. FDHITS [11] formulates FD discovery as hitting-set enumeration and interleaves parallel exploration with efficient validation.
12
All of the above target exact FDs and produce complete result sets. Pyro [5] extends discovery to approximate FDs and UCCs under a user-specified error threshold, combining a separate-and-conquer strategy with sampling-based candidate detection, but still returns all dependencies below the threshold rather than ranking them. Our setting scores dependencies by µ+ , does not fix the RHS, and returns only the top-k results. C. AFD Measures Kivinen and Mannila [23] defined several error measures for approximate FDs and studied their sample complexity. Among these, g3 quantifies error through a partition-based formulation and was later adopted in TANE [15], becoming widely used. Giannella and Robertson [24] proposed the τ measure based on probabilistic dependence (pdep), which captures how well the LHS determines the RHS but is sensitive to LHS-uniqueness. Mandros et al. [8] adopted a Shannon entropy-based measure with a bias correction derived from the permutation model. Parciak et al. [9] evaluated 14 AFD measures across reliability, sensitivity to LHS-uniqueness and RHS-skew, and computational cost, finding that µ+ and RFI′+ are the two best-performing measures. The authors recommend µ+ for practical use because RFI′+ is orders of magnitude more expensive to compute. We adopt µ+ based on the findings of Parciak et al. The property that makes this choice non-trivial is that µ+ scores are comparable across different RHS attributes, unlike Shannon entropy-based measures whose normalization depends on the marginal entropy of each RHS. D. Top-k AFD Discovery Mandros et al. [8] introduced the idea of returning the k strongest approximate dependencies rather than all dependencies above a threshold, fixing a target attribute A and searching for the k subsets X maximizing a corrected fraction of information F̂ ′ (X; A) via branch-and-bound with an optimistic estimator. Follow-up work proved that maximizing the reliable fraction of information is NP-hard and derived a tighter bound [25], [26]. Our formulation differs in that the RHS is not fixed: Mandros et al. search over 2d LHS subsets for a single target, whereas we search all X → A combinations simultaneously. This requires a scoring function comparable across RHS attributes, which rules out the fraction of information whose normalization depends on H(A), and invalidates their branchand-bound strategy since the optimistic estimator assumes a fixed RHS. The question of whether minimality should be enforced arises naturally in the global setting; we resolve it negatively via the Triangle Incompatibility Theorem. Wan et al. [27] rank exact FDs by redundancy count and develop pruning based on an upper bound on partition size; their scoring function is monotonic, so classical antimonotonic pruning applies directly. Wei and Link [28] propose redundancy as a ranking criterion for meaningful FD discovery but do not integrate it into the search process for top-k results. Fan et al. [29], [30] investigate top-k discovery of general
data quality rules incorporating relevance and diversity. None of these addresses the non-monotonicity of µ+ , which is the central pruning challenge in our setting. No existing method combines a global RHS-free formulation, a scoring function comparable across RHS attributes, and safe pruning under non-monotonic scoring. TALE addresses all three. VIII. C ONCLUSION This paper studies global top-k AFD discovery, where neither the LHS nor the RHS is fixed and the k highest-scoring dependencies under µ+ are returned directly. The thresholdbased paradigm that dominates existing work produces output of uncontrollable size, requires data-dependent threshold selection, and is sensitive to LHS dimensionality. The top-k formulation avoids all three. The Triangle Incompatibility Theorem shows that minimality, global top-k ranking, and exact-k output cannot simultaneously hold under any non-monotonic scoring function. This is an inherent property of the problem, not a limitation of any particular algorithm, and it provides a principled justification for dropping the minimality requirement. TALE-Base guarantees the exact global top-k result by evaluating all candidates level by level. TALE-Opt addresses the central challenge that µ+ is not monotone under LHS enlargement, which rules out classical anti-monotonic pruning. We derive an optimistic upper bound on µ+ that decreases monotonically with LHS size, recovering safe pruning; this bound is tracked per RHS attribute through bit-vectors and propagated across levels via Apriori-style candidate generation, complemented by LHS computation reuse and exact FD pruning. Experiments on 41 real-world datasets show pruning ratios reaching 99.81% on high-dimensional datasets and speedups of TALE-Opt over TALE-Base up to 78.81×. Case studies on three datasets confirm that the discovered dependencies are semantically interpretable and support practical data quality auditing. R EFERENCES [1] A. Silberschatz, H. F. Korth, and S. Sudarshan, Database System Concepts, Seventh Edition. McGraw-Hill Book Company, 2020. [2] H. Köhler and S. Link, “SQL schema design: foundations, normal forms, and normalization,” Inf. Syst., vol. 76, pp. 88–113, 2018. [3] T. Boeckling and A. Bronselaer, “Cleaning data with swipe,” ACM J. Data Inf. Qual., vol. 17, no. 1, pp. 1–29, 2025. [4] Y. Zhang, Z. Guo, and T. Rekatsinas, “A statistical perspective on discovering functional dependencies in noisy data,” in Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020. ACM, 2020, pp. 861–876. [5] S. Kruse and F. Naumann, “Efficient discovery of approximate dependencies,” Proc. VLDB Endow., vol. 11, no. 7, pp. 759–772, 2018. [6] I. F. Ilyas and X. Chu, Data Cleaning, ser. ACM Books. ACM, 2019, vol. 28. [7] L. Caruccio, V. Deufemia, and G. Polese, “Relaxed functional dependencies - A survey of approaches,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 1, pp. 147–165, 2016. [8] P. Mandros, M. Boley, and J. Vreeken, “Discovering reliable approximate functional dependencies,” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2017, pp. 355–363. [9] M. Parciak, S. Weytjens, N. Hens, F. Neven, L. M. Peeters, and S. Vansummeren, “Measuring approximate functional dependencies: a comparative study,” VLDB J., vol. 34, no. 4, p. 56, 2025.
13
[10] X. Wan, X. Han, J. Wang, and J. Li, “Efficient discovery of functional dependencies on massive data,” IEEE Trans. Knowl. Data Eng., vol. 36, no. 1, pp. 107–121, 2024. [11] T. Bleifuß, T. Papenbrock, T. Bläsius, M. Schirneck, and F. Naumann, “Discovering functional dependencies through hitting set enumeration,” Proc. ACM Manag. Data, vol. 2, no. 1, pp. 43:1–43:24, 2024. [12] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules in large databases,” in VLDB’94, Proceedings of 20th International Conference on Very Large Data Bases. Morgan Kaufmann, 1994, pp. 487–499. [13] Z. Abedjan, L. Golab, and F. Naumann, “Profiling relational data: a survey,” VLDB J., vol. 24, no. 4, pp. 557–581, 2015. [14] Z. Abedjan, L. Golab, F. Naumann, and T. Papenbrock, Data Profiling, ser. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2018. [15] Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen, “TANE: an efficient algorithm for discovering functional and approximate dependencies,” Comput. J., vol. 42, no. 2, pp. 100–111, 1999. [16] N. Novelli and R. Cicchetti, “Functional and embedded dependency inference: a data mining point of view,” Inf. Syst., vol. 26, no. 7, pp. 477–506, 2001. [17] H. Yao and H. J. Hamilton, “Mining functional dependencies from data,” Data Min. Knowl. Discov., vol. 16, no. 2, pp. 197–219, 2008. [18] Z. Abedjan, P. Schulze, and F. Naumann, “DFD: efficient functional dependency discovery,” in CIKM. ACM, 2014, pp. 949–958. [19] P. A. Flach and I. Savnik, “Database dependency discovery: A machine learning approach,” AI Commun., vol. 12, no. 3, pp. 139–160, 1999. [20] S. Lopes, J. Petit, and L. Lakhal, “Efficient discovery of functional dependencies and armstrong relations,” in EDBT, vol. 1777. Springer, 2000, pp. 350–364. [21] C. M. Wyss, C. Giannella, and E. L. Robertson, “Fastfds: A heuristicdriven, depth-first algorithm for mining functional dependencies from relation instances - extended abstract,” in DaWaK, vol. 2114. Springer, 2001, pp. 101–110. [22] T. Papenbrock and F. Naumann, “A hybrid approach to functional dependency discovery,” in Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016. ACM, 2016, pp. 821–833. [23] J. Kivinen and H. Mannila, “Approximate inference of functional dependencies from relations,” Theor. Comput. Sci., vol. 149, no. 1, pp. 129–149, 1995. [24] C. Giannella and E. L. Robertson, “On approximation measures for functional dependencies,” Inf. Syst., vol. 29, no. 6, pp. 483–507, 2004. [25] P. Mandros, M. Boley, and J. Vreeken, “Discovering reliable dependencies from data: Hardness and improved algorithms,” in IEEE International Conference on Data Mining, ICDM 2018. IEEE Computer Society, 2018, pp. 317–326. [26] ——, “Discovering dependencies with reliable mutual information,” Knowl. Inf. Syst., vol. 62, no. 11, pp. 4223–4253, 2020. [27] X. Wan and X. Han, “Redundancy-driven top-k functional dependency discovery,” CoRR, vol. abs/2601.10130, 2026. [28] Z. Wei and S. Link, “Towards the efficient discovery of meaningful functional dependencies,” Inf. Syst., vol. 116, p. 102224, 2023. [29] W. Fan, Z. Han, Y. Wang, and M. Xie, “Discovering top-k rules using subjective and objective criteria,” Proc. ACM Manag. Data, vol. 1, no. 1, pp. 70:1–70:29, 2023. [30] W. Fan, Z. Han, M. Xie, and G. Zhang, “Discovering top-k relevant and diversified rules,” Proc. ACM Manag. Data, vol. 2, no. 4, pp. 195:1– 195:28, 2024.