Redundancy Overload Is Optional: Finding the FDs That Actually Matter

Tables have a talent for pretending to be tidy.

A customer table may have fifty columns. A transaction table may have a hundred. A log table may contain derived fields, timestamps, status codes, copied identifiers, normalized labels, and a few columns that nobody remembers creating but everybody is afraid to delete. Then a data profiling tool arrives, dutifully discovers functional dependencies, and returns several hundred thousand “valid” relationships.

Technically impressive. Operationally exhausting. The machine has discovered truth, and the human has inherited a landfill.

The paper Redundancy-Driven Top-k Functional Dependency Discovery by Xiaolong Wan and Xixian Han takes aim at this specific failure mode.¹ Its argument is not that functional dependency discovery is useless. Quite the opposite. Functional dependencies still matter for normalization, data cleaning, integrity checking, and schema understanding. The problem is that classical discovery asks the wrong first question.

It asks: “Which dependencies are valid?”

The better operational question is: “Which valid dependencies explain enough repeated structure to be worth looking at first?”

That difference sounds small. It is not. It changes FD discovery from exhaustive enumeration followed by ranking into an exact selective retrieval problem. The paper’s proposed algorithm, SDP — Selective-Discovery-and-Prune — does not merely find all FDs faster and sort them afterward. It uses redundancy itself to avoid searching large regions of the dependency lattice that cannot possibly contain a top-ranked result.

This is the useful part. Not another “we optimized the database thing” paper, though yes, the database thing is optimized. The deeper contribution is a mechanism for turning relevance into safe search control.

The mistake is treating “valid” as “important”

A functional dependency, written as $X \to A$, says that if two tuples agree on the attributes in $X$, they must also agree on attribute $A$. If FlightNo determines Origin, then every row with the same flight number should have the same origin. That is a meaningful dependency. It tells us something about the structure of the data.

But not every valid FD is equally useful.

A dependency based on a unique identifier may be perfectly valid and still not tell us much. If every ID is unique, then ID determines almost everything. The database did not reveal a hidden business rule. It merely reminded us that unique identifiers are unique. Thank you, table. Very profound.

The paper’s motivating distinction is between dependencies that are valid because they describe repeated structure and dependencies that are valid because the left-hand side is too specific. The former can expose redundancy, normalization opportunities, duplicate columns, derived fields, or business rules. The latter often add noise to an already crowded result set.

Redundancy count gives this distinction a measurable form. For a valid FD $X \to A$, the redundancy count can be understood through the partition induced by $X$. Group the table rows by the values of $X$. Within each group, the FD forces $A$ to be the same. Repeated occurrences inside those groups are the redundancy explained by the dependency.

In compact form:

Here, $r$ is the relation instance, and $\pi_X$ is the partition of tuples by $X$. Fewer equivalence classes under $X$ means larger repeated groups, and therefore more redundancy. A unique key creates almost as many groups as there are rows, so its redundancy is near zero. A meaningful repeated business rule creates larger groups, so its redundancy rises.

This is the first useful correction: the paper is not saying “all FDs are equally valuable but some are faster to find.” It says utility can be ranked, and redundancy is a concrete ranking signal.

That signal is not perfect. Redundancy is not the same as business value. A highly redundant dependency may reflect a useful business rule, a duplicate column, a derived field, or merely boring data-entry convention. But it is a much better triage signal than dumping all minimal FDs into a spreadsheet and calling it insight.

The baseline still pays for the garbage pile

The obvious baseline is Full-Discovery-and-Rank, or FDR in the paper.

FDR works in two phases. First, use an exhaustive FD discovery method — the paper uses FDHITS as the strong baseline — to discover all valid minimal non-trivial FDs. Second, compute redundancy for the discovered FDs, sort them, and return the top $k$.

This is correct. It is also wasteful by construction.

If a table contains hundreds of thousands of valid dependencies, and the user only wants the top 10 by redundancy, FDR still pays the cost of discovering the dependencies that will be discarded. The ranking happens too late. It is like reading every document in a warehouse before deciding which ten are relevant. A noble lifestyle, if your servers enjoy martyrdom.

SDP’s central move is to pull the ranking signal inside the search process.

The algorithm still needs exactness. It cannot simply skip candidates because they “look uninteresting.” That would make the result approximate. The paper’s contribution is finding a safe upper bound on redundancy, so the algorithm can prove that certain branches cannot contain a top-$k$ FD before spending expensive validation work on them.

The mechanism: redundancy falls as the left-hand side becomes more specific

The key mechanism is partition refinement.

When we add attributes to the left-hand side of a candidate FD, the tuple partition becomes finer. Rows that previously belonged to the same group may split into smaller groups because they no longer agree on the added attribute. The number of equivalence classes cannot decrease.

Since redundancy is $|r| - |\pi_X|$, finer partitions mean redundancy cannot increase. More specific left-hand sides usually explain less repetition.

This gives SDP a monotone upper bound. For a candidate left-hand side $X$ and right-hand side $A$, any descendant of $X$ in the search lattice — any candidate that adds more attributes to $X$ — can only have redundancy up to a computable ceiling. If that ceiling is below the current top-$k$ threshold, then neither the current node nor its descendants can enter the final top-$k$ set.

The paper also uses the fact that a valid FD $X \to A$ imposes a relationship between the partition induced by $X$ and the partition induced by $A$. If $X$ determines $A$, then rows grouped together by $X$ must also share $A$. This constrains how small the partition cardinality can be.

In simplified terms, SDP uses an upper bound shaped by the tuple count, the right-hand-side partition, and the partition sizes of attributes already included in the candidate left-hand side. The intuition is enough for business readers:

if a branch has already become too specific to explain much redundancy, no amount of further specialization can make it more important.

That is the paper’s real engine. Redundancy is not merely a score. It becomes a pruning certificate.

SDP is not “FDHITS, but sorted earlier”

The paper builds SDP on top of the hypergraph-style enumeration framework used by FDHITS. That matters because SDP is not starting from a toy algorithm. It adapts a strong modern discovery approach.

FDHITS treats FD discovery through difference sets and minimal hitting set enumeration. Roughly, tuple pairs that disagree on certain attributes provide evidence against possible dependencies. Candidate left-hand sides are generated as hitting sets over these difference constraints and then validated against the full data.

SDP keeps this general framework but changes the search discipline.

It maintains a min-heap of the current top-$k$ FDs. The smallest redundancy value in this heap becomes the dynamic threshold $\tau$. At the beginning, $\tau$ is low because the heap is empty or incomplete. As SDP finds high-redundancy valid FDs, $\tau$ rises. A higher $\tau$ makes pruning stronger.

The algorithm applies pruning in two important places:

This is the difference between passive ranking and active retrieval. FDR ranks after the search has paid its bill. SDP lets the ranking objective negotiate the bill in advance.

Three accelerators make the pruning practical

The base pruning idea is correct, but correctness alone does not guarantee speed. SDP becomes practical through three optimization strategies.

Attribute ordering finds useful dependencies before the threshold gets lazy

Pruning is only powerful after $\tau$ becomes meaningful. If the algorithm first wanders through low-redundancy branches, the threshold rises slowly and little gets pruned.

The paper’s first optimization orders attributes by partition cardinality. Attributes with fewer equivalence classes tend to preserve larger groups and therefore higher potential redundancy. SDP uses this ordering both for selecting right-hand-side attributes and for extending left-hand-side candidates.

This is heuristic, not part of the correctness proof. The result remains exact even if the ordering is not perfect. But the ordering helps SDP discover high-redundancy FDs early, which raises $\tau$ quickly and makes the safe pruning rule useful sooner.

The practical lesson is familiar: in search problems, finding one good answer early can be more valuable than marginally improving every later check. Early good answers become filters.

Pairwise bounds prevent the algorithm from trusting misleading single columns

Single-attribute partition counts can be loose. Two attributes may each have low cardinality individually, while their combination almost uniquely identifies rows. If SDP only looks at single attributes, it may overestimate the redundancy potential of branches containing that pair.

The paper addresses this using a Partition Cardinality Matrix, or PCM. The PCM stores selected pairwise partition cardinalities. It is built partly through selective pre-computation and partly through opportunistic caching: when the algorithm validates a two-attribute candidate and obtains the pairwise partition as a byproduct, it stores the result for later pruning.

This is a sensible engineering compromise. Computing all pairwise partitions would be expensive. Computing none would leave the upper bound too loose. PCM makes the bound tighter where it is likely to matter, without turning pruning into its own expensive monster. We have enough of those already.

Global best-first scheduling lets one RHS help prune another

A sequential algorithm may process one right-hand-side attribute at a time. That creates a timing problem. Suppose the best high-redundancy FDs sit under the last RHS processed. Then the algorithm spends too much time exploring earlier RHS trees with a weak threshold.

SDP’s third optimization uses a global best-first scheduler across right-hand-side search trees. Instead of exhausting one RHS tree before moving to the next, the algorithm maintains a global priority queue and advances the most promising branch across all RHS attributes.

This changes traversal order, not correctness. The paper proves that any traversal strategy visiting all unpruned candidates under a safe upper bound returns the same exact top-$k$ result. The global scheduler simply helps find high-redundancy FDs earlier, so $\tau$ becomes useful across all trees.

In business language: discoveries in one part of the schema immediately tighten the budget for the rest of the schema. Search becomes organizational learning, not isolated departmental paperwork.

What the experiments are actually testing

The paper’s evaluation is broad enough to separate the main evidence from the supporting tests. The authors implement the algorithms in Java, run them under a 56 GB memory limit, and evaluate on more than 40 datasets from UCI and Kaggle. The datasets range from 8 to 109 attributes and from hundreds of rows to tens of millions of tuples. The default setting is $k = 10$.

Here is the clean interpretation of the experimental design:

This distinction matters. The paper is not one big scoreboard. It is a mechanism paper with experiments arranged around the mechanism: prune more search, validate fewer candidates, materialize fewer partitions, and still return exact top-$k$ results.

The main result: SDP wins when exhaustive discovery becomes silly

The headline result is that SDP is much faster than FDR on large-scale and high-dimensional datasets, with reported speedups reaching 10–1000× in the settings where exhaustive discovery struggles.

The Flight dataset is the dramatic example. It has 1,000 tuples and 109 attributes. FDR discovers 982,631 FDs, of which 734,583 have positive redundancy. FDR takes 195.179 seconds and uses 2.5 GB of memory. SDP returns the top-$k$ result in 0.166 seconds and uses 0.093 GB, for a reported speedup of 1175.8×. The search pruning ratio is 0.9999 and the candidate pruning ratio is 0.99999.

Translated: SDP avoids almost the entire search and validation burden while preserving the exact top-$k$ answer.

ReactionNetwork shows another strong case. FDR takes 137.882 seconds and 44.888 GB of memory. SDP takes 1.669 seconds and 0.764 GB in the overall comparison, a reported 82.614× speedup. Here, the story is not only time. It is memory survivability.

FDR runs out of memory on five datasets: census, covtype, homec, rideshare_kaggle, and superconductivity. SDP completes on them. The paper attributes this to the fact that FDR materializes partitions for many candidates, while SDP prunes candidates before paying that memory cost.

This is important for operational data profiling. Runtime is annoying. Out-of-memory failure is a workflow killer. A profiler that finishes in ten minutes is slower than ideal; a profiler that dies after consuming the machine is not a profiler. It is an expensive confession.

The scalability tests show where the mechanism bends and where it holds

The tuple scalability test uses ftda, the largest dataset in the paper, with over 13 million tuples and 11 attributes. The authors construct prefix subsets from 20% to 100% of the data.

FDR scales roughly linearly with tuple count. SDP grows more slowly and reaches a 7.87× speedup at 13.1 million tuples. The paper also observes that SDP validates a stable number of candidates — around 50–60 — as the dataset grows. The interpretation is that the top high-redundancy FDs remain stable enough for the pruning logic to keep working, even though validating any single candidate becomes more expensive with more tuples.

The attribute scalability test is more severe. It uses the superconductivity dataset with up to 82 attributes. This is where FD discovery traditionally becomes painful because each additional attribute expands the search lattice.

FDR’s node count grows from 419 at 16 attributes to 2.65 million at 65 attributes, then it runs out of memory at 82 attributes. SDP stays below 0.38 GB of memory and, even at 82 attributes, generates 1,518 nodes and validates only 246 candidates.

That is the mechanism in its preferred habitat: wide schemas, many possible dependencies, small $k$, and many low-redundancy branches that can be safely discarded.

The $k$ sensitivity test is the quiet boundary condition

The most important limitation is not hidden. It is in the $k$ sensitivity experiment.

On ReactionNetwork, FDR is almost insensitive to $k$. Its runtime stays around 145–155 seconds and memory use stays around 42.6–44.9 GB. This is expected because FDR discovers everything first. Whether the user asks for top 1 or top 500 barely matters after the exhaustive work is already done.

SDP behaves differently. As $k$ increases from 1 to 500, runtime grows from 0.43 seconds to 72.45 seconds, generated nodes increase from 442 to 24,000, and memory rises from 0.14 GB to 28.49 GB.

This is not a flaw. It is the price of relevance-aware search. When $k$ is small, the threshold $\tau$ becomes high quickly, so pruning is aggressive. When $k$ grows, the $k$-th best redundancy threshold falls, more candidates remain plausible, and SDP must explore more of the lattice.

For business use, this is actually helpful. It says SDP is best aligned with human review capacity. If a data steward wants the top 10 or top 50 dependencies worth investigating, SDP fits the task. If someone asks for the top 50,000, they may secretly be asking for exhaustive discovery again, just with a nicer hat.

The ablation study shows the algorithm is not carried by one trick

The ablation study compares four variants:

The results show different components doing different jobs.

On ReactionNetwork, SDP-core takes 81.792 seconds and uses 32.4 GB. Adding ordering reduces runtime to 8.239 seconds and memory to 4.6 GB. Adding PCM gives similar runtime but slightly lower memory. Full SDP drops runtime further to 2.849 seconds and memory to 1.3 GB.

On census, SDP-core runs out of memory. Ordering makes the run feasible at 315.055 seconds and 30.9 GB. PCM alone after ordering slightly increases runtime to 355.054 seconds but reduces memory to 29.8 GB. Full global scheduling then cuts runtime to 21.213 seconds and memory to 6.4 GB.

The interpretation is not “every optimization always improves everything.” That would be too tidy, and therefore suspicious. Ordering is critical for raising the threshold early. PCM mainly tightens bounds and saves memory, sometimes with overhead. Global scheduling produces the strongest convergence effect because it lets early high-redundancy discoveries prune across RHS trees.

This is a useful engineering lesson: pruning systems are often threshold economies. The value does not come from one perfect bound. It comes from finding good candidates early enough that the bound can become ruthless.

The case studies turn redundancy into recognizable data problems

The paper’s qualitative examples are useful because they show what high-redundancy FDs look like in real tables.

In the movies dataset, ReleaseDate -> ReleaseYear has very high redundancy. That is a natural temporal hierarchy. If both columns are stored, one is derivable from the other. Whether to remove it depends on query performance and data model choices, but the dependency is plainly interpretable.

In the weather dataset, precipitation -> rain and rain -> precipitation appear as mutual dependencies with redundancy almost equal to the dataset size. That suggests synonymy or duplicated representation. In a production data catalog, this is exactly the sort of relationship worth surfacing.

In the YouTube recommendation dataset, dependencies among watch time, watch percentage, and video duration reveal calculated invariants. These are useful not because they save a few bytes, but because violations can indicate broken logging, transformation bugs, or inconsistent metric definitions.

In the HR dataset, dependencies such as Job_Title -> Department and Hire_Date -> Status suggest organizational policy rules. These could support role-based access audits or employee master-data checks. With HR data, of course, “dependency” should not be confused with fairness, legality, or managerial wisdom. The table can tell you that a rule exists. It cannot tell you that the rule deserves applause.

The case studies show the business pathway: high-redundancy FDs are candidates for investigation. They are not automatic instructions.

What Cognaptus would infer for business practice

The paper directly shows that exact redundancy-ranked top-$k$ FD discovery can be made much cheaper than exhaustive discovery on many large or wide datasets. It also shows that high-redundancy FDs often correspond to interpretable structural patterns.

From that, the business implications are fairly concrete.

The ROI is not “cheaper algorithm, therefore cheaper company.” Please. The real ROI path is narrower and more credible: lower profiling cost makes it feasible to run dependency discovery on datasets where exhaustive methods are too slow or memory-heavy; ranked output reduces human review burden; and the surfaced dependencies can become candidates for governance rules, cleaning checks, or schema refactoring.

That is enough. Not every paper needs to become a transformation journey with stock-photo executives pointing at dashboards.

Boundaries: exact does not mean universally useful

The paper is careful about exactness: SDP returns exact top-$k$ results under its redundancy objective. But exactness under a metric is not the same as universal practical relevance.

Several boundaries matter.

First, redundancy count is a proxy. It favors dependencies that explain repeated structure. That is often useful for normalization and cleaning, but business importance can also depend on regulatory risk, revenue impact, operational criticality, or user-facing semantics. A lower-redundancy dependency involving a sensitive field may matter more than a high-redundancy dependency involving harmless metadata.

Second, the method focuses on exact FDs. Real-world operational data is often noisy. Near-dependencies and approximate dependencies may be more useful in messy systems, especially when errors, delayed updates, or integration mismatches are common. The paper’s case study on gendergap notes a small number of violating tuples; that kind of situation is precisely where approximate or exception-aware profiling may be needed.

Third, the performance advantage is workload-dependent. SDP shines when $k$ is small and the search space is large enough for pruning to matter. On simpler low-dimensional datasets, the overhead of PCM pre-computation and global scheduling can make SDP comparable to or slightly slower than FDR. The paper explicitly notes cases such as ht_sensor, harth, and grocery_sales where overhead becomes visible.

Fourth, null semantics matter. The experiments use NULL-EQ semantics, treating nulls as equal to each other and distinct from non-null values. Different organizations may use different missing-value semantics, and that can change discovered dependencies.

Finally, implementation context matters. The experiments use Java on a specific workstation with a 56 GB memory allocation. The qualitative conclusion is robust enough to be meaningful, but deployment performance will still depend on engineering details, data distribution, and integration with existing profiling pipelines.

The real lesson is selective exactness

The most interesting part of the paper is not that SDP is faster. Speed is the symptom.

The real lesson is selective exactness: when the ranking objective has a safe monotone bound, an algorithm can remain exact while refusing to enumerate irrelevant truth.

That pattern is valuable beyond FD discovery. Many enterprise analytics systems still behave as if completeness is the default virtue. They generate every candidate rule, every possible alert, every metric slice, every compliance exception, and then ask humans to triage the wreckage. This is how dashboards become wallpaper and governance becomes theater.

SDP shows a better pattern for one technical domain. Define a relevance metric. Prove a safe bound. Search in an order that finds strong candidates early. Use those candidates to prune the rest. Return fewer things, but return the right fewer things.

For functional dependencies, that means treating redundancy overload as optional. The database may contain a million valid facts. The user probably needs ten good leads.

And if a unique ID determines every column, congratulations. The table has discovered the concept of identity. We can all move on.

Cognaptus: Automate the Present, Incubate the Future.