Conditional Functional Dependencies for Data Cleaning

22 concepts10 papers1 proposal

Traditional database theory treats integrity constraints as global truths. When we define a Functional Dependency (FD) like $\text{ZipCode} \rightarrow \text{State}$, we assert that for every pair of records in the database, if the zip codes match, the states must match.

While this rigidity works well for database design, it falls short for data cleaning. Real-world data is messy, heterogeneous, and deeply context-dependent. A rule might be perfectly valid for records in one country but completely incorrect for another. To bridge this gap, a modern paradigm treats integrity constraints not as global invariants, but as localized rules bound to specific data patterns.

The Limitation of Global Constraints

To understand why traditional constraints fail at data cleaning, consider a global relation containing international addresses. If we attempt to enforce a standard functional dependency like $\text{ZipCode} \rightarrow \text{Street}$, we run into an immediate problem: this relationship does not hold globally across all countries. In some postal systems, a zip code narrows down the location to a specific street; in others, it only identifies a broad region or city.

As noted by Geerts et al., traditional integrity constraints are too rigid because they force an all-or-nothing schema design. If a dependency fails to hold for a small subset of data or represents a localized business rule, it must be discarded entirely from the global schema. This creates a significant vulnerability in data quality systems: without a way to formalize context-specific rules, automated systems cannot distinguish between a genuine data error and a valid exception to a global rule.

The Intuition of the Pattern Tableau

To solve this, Bohannon et al. introduced Conditional Functional Dependencies (CFDs). The core insight behind a CFD is to pair a standard functional dependency with a pattern tableau—a secondary table that defines exactly when and how the constraint should be applied.

A pattern tableau extends the standard dependency $X \rightarrow Y$ by mapping attributes to either constants or wildcards (_). This mechanism enables two distinct types of localized constraints:

  1. Context-Dependent Rules: The dependency only triggers if the data matches a specific context. For example, we can specify that the dependency $\text{ZipCode} \rightarrow \text{Street}$ is only enforced if the $\text{Country}$ attribute equals 'UK'.
  2. Constant-Value Enforcements: The tableau can dictate that a specific value in attribute $X$ must always result in a specific constant value in attribute $Y$. For instance, if $\text{Country} = 'US'$, then $\text{Currency}$ must be 'USD'.
Traditional FD:  [Country, ZipCode] -> [Street]  (Must hold globally for all pairs)

CFD Pattern Tableau:
Country  |  ZipCode  ||  Street
===============================
'UK'     |    _      ||    _       (Enforce ZipCode -> Street ONLY for UK records)
'US'     |    _      ||  'USD'     (Enforce that US records must use USD currency)

This architectural shift fundamentally changes how systems detect errors. In classical dependency theory, detecting a violation requires a pair of records to show a contradiction ($t_1[X] = t_2[X]$ but $t_1[Y] \neq t_2[Y]$).

By contrast, because CFDs embed constants directly into the constraint logic, they enable single-tuple error detection. As Bohannon et al. demonstrate, if a single record contains Country = 'US' and Currency = 'EUR', the system can flag it as an error immediately in isolation, without needing to compare it to any other row in the database.

Expanding Expressiveness

Once constraints are freed from global rigidity, the pattern language can be extended to capture increasingly complex semantics.

Set Conditions and Inequalities

Real-world business logic rarely stops at simple equality matches. To capture more nuanced data anomalies, Geerts et al. introduced extended CFDs (eCFDs). Instead of limiting the pattern tableau to exact constants or open wildcards, eCFDs allow attributes to be constrained by sets of values, intervals, and inequalities (e.g., $\text{Age} > 65$). Crucially, the authors proved that this added expressiveness does not increase the computational complexity of validating or cleaning the data, providing a much more powerful toolkit for identifying heterogeneous inconsistencies for free.

Regular Expressions and Partial Matches

Sometimes, an inconsistency occurs within the structure of the value itself rather than between distinct columns. Tang et al. pushed the paradigm further by introducing Pattern Functional Dependencies (PFDs). PFDs integrate regular expressions directly into the dependency theory. Instead of checking if two values are exactly identical, a PFD can enforce that if a partial string matches a specific format (like an area code pattern in a phone number), another part of the record must conform to a corresponding pattern. To support this, the authors developed a dedicated set of inference axioms—extending classical Armstrong's axioms—to handle properties unique to pattern matching, such as handling logical contradictions (Inconsistency-EFQ) and generalizing left-hand-side patterns.

Fuzzy and Relational Extensions

The concept of conditional constraints extends beyond functional dependencies. Chen et al. generalized the concept into Matching Dependencies (MDs), which replace exact equality matches with similarity thresholds to accommodate typos and formatting variations. Meanwhile, Ma et al. extended the conditional paradigm to cross-table relationships with Conditional Inclusion Dependencies (CINDs), ensuring that referential integrity constraints are only triggered under specific data patterns.

Putting CFDs to Work: Detection and Repair

The ultimate goal of formalizing these conditional rules is to automate data quality pipelines. Systems like SEMANDAQ, developed by Fan et al., use CFDs as an operational engine to automatically discover inconsistencies and guide users through data cleaning workflows.

When a data quality system detects a violation, it faces a choice: how should it repair the data? Cong et al. addressed this by developing heuristic algorithms that do more than just make the data "consistent" with the rules; they use statistical sampling and incremental repair mechanisms to ensure that the modifications maximize the actual semantic accuracy of the underlying data.

[ Dirty Data ] ---> [ CFD Engine (Tableau Rules) ] ---> [ Violation Detection ]
                                                                |
[ Clean Data ] <--- [ Heuristic Repair (Accuracy Focus) ] <-----+

However, managing conditional dependencies introduces unique downstream challenges when data is transformed. When users query data through database views, the underlying constraints change. Fan et al. investigated this dependency propagation problem, mapping out how CFDs behave across different relational algebra operations. They demonstrated that while standard FDs are frequently lost entirely during view transformations, CFDs can successfully preserve critical semantic constraints across views because their conditional nature allows them to adapt to the specific subsets of data being exposed.

Ultimately, by grounding abstract dependency theory in localized data patterns, conditional constraints provide the mathematical foundation needed to turn rigid database schemas into flexible, automated data cleaning engines.

Key Foundational Work

Conditional Functional Dependencies for Data Cleaning (2007) — contributed 4 concept elements to this direction.
Extending Dependencies with Conditions (2007) — contributed 3 concept elements to this direction.
Improving Data Quality: Consistency and Accuracy (2007) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 9 papers
  2. Version 1 · 2026-10-04 · 16 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_conditional_functional_dependencies_4c05517d,
  title = {conditional functional dependencies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conditional-functional-dependencies/rdr_4c05517d3bfa4f45b08fa90977c309ad},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_conditional_functional_dependencies_4c05517d_v2,
  title = {conditional functional dependencies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conditional-functional-dependencies/rdr_4c05517d3bfa4f45b08fa90977c309ad/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake