Reasoning about Record Matching Rules

Wenfei Fan, Xibei Jia, Jianzhong Li, Shuai Ma

TL;DR

This paper introduces "matching dependencies" (MDs) and "relative candidate keys" (RCKs) to address the challenge of accurately matching records in real-world, "dirty" datasets. They propose novel reasoning techniques and algorithms to automatically infer these rules, significantly improving the quality and efficiency of record matching, blocking, and windowing processes.

What Problem Does This Paper Address?

Accurately identifying records that refer to the same real-world entity (e.g., a person, a product) is crucial for data integration, cleaning, and master data management. However, real-world data is often "dirty," meaning it contains errors, inconsistencies, and different representations of the same information across various sources. Traditional methods for inferring relationships between data, like functional dependencies (FDs), assume clean data and are ill-equipped to handle these imperfections. This paper tackles the problem of how to define and reason about rules for matching records when the data itself is unreliable and may not perfectly align.

Methods

The core of this paper lies in its novel formalisms and reasoning mechanisms:

  • Matching Dependencies (MDs): This new class of dependencies extends traditional FDs to handle unreliable data. MDs are defined using similarity metrics (e.g., edit distance, q-grams) and a "dynamic semantics." This means an MD states that if certain attributes are similar across records, then other attributes should be identified (made equal), even if they are currently different in the source data.
  • Relative Candidate Keys (RCKs): A special case of MDs, RCKs are minimal sets of attribute comparisons that can reliably identify matching records across different, potentially unreliable, relations. They differ from traditional candidate keys by allowing similarity metrics and operating across schemas.
  • Reasoning Mechanism: The authors propose a generic reasoning mechanism for inferring MDs from a given set of MDs. This mechanism accounts for the dynamic semantics of MDs and the interactions between similarity and equality operators.
  • Algorithms:
    • MDClosure: An O(n²) algorithm for determining if one MD can be deduced from a set of MDs, comparable to FD implication analysis.
  • findRCKs: An efficient algorithm to deduce a set of "quality" RCKs based on a cost model that considers attribute similarity, value length, and accuracy.

Datasets

The paper uses real-life data scraped from the web for experiments, specifically addresses and sale items (books, DVDs). They also generated datasets by introducing duplicates and noise into these real-world data sources. The datasets were controlled by varying the number of records (from 10k to 80k) and the percentage of duplicates and errors. No new benchmarks were introduced; existing real-world data was adapted.

Key Insights and Ideas

  • Dynamic Semantics is Key: The most crucial insight is that for dirty data, "identification" (making attributes equal) is more appropriate than strict equality. MDs capture this by allowing similarity on the left-hand side (LHS) to enforce equality on the right-hand side (RHS), even if the RHS attributes are initially different.
  • RCKs as "Smart" Matching Keys: RCKs provide a principled way to determine what attributes to compare and how to compare them for matching. They go beyond simple equality, incorporating domain-specific similarity measures.
  • Automated Rule Discovery: The ability to automatically infer MDs and RCKs from a set of initial rules or data significantly reduces the manual effort typically required in record matching.
  • Interactions Matter: The paper highlights non-trivial interactions between similarity operators and the "identification" operator, which are not present in traditional FD theory and require specialized reasoning.
  • RCKs Enhance Existing Methods: RCKs are not a replacement for existing record matching algorithms but a powerful complement, improving their accuracy and efficiency.

Key Results

  • Improved Match Quality: Using RCKs with the Fellegi-Sunter (statistical) method improved precision by up to 20% and recall by up to 30% compared to methods without RCKs. The Sorted Neighborhood (rule-based) method saw similar improvements in precision and recall (around 20%).
  • Increased Efficiency: RCKs helped reduce the number of attribute comparisons, leading to efficiency gains in matching, blocking, and windowing.
  • Robustness to Noise: Methods using RCKs became less sensitive to data noise and errors.
  • Scalability: The algorithms for inferring MDs (MDClosure) and RCKs (findRCKs) demonstrated good scalability with respect to the number of MDs, the number of RCKs, and the length of attribute lists. For instance, it took less than 100 seconds to deduce 50 quality RCKs from 2000 MDs.
  • Blocking/Windowing Effectiveness: Using RCKs as blocking or windowing keys consistently improved match quality (pairs completeness) by over 10%.

Limitations and Future Work

  • Negation Support: The authors suggest extending MDs to support "negation" to specify when records cannot be matched.
  • Domain-Specific Synonyms: Incorporating constants to capture domain-specific synonym rules (e.g., "USA" = "United States") is a future direction.
  • Complex Correspondences: The current work focuses on 1-1 attribute correspondences. Future work will address more complex matches involving multiple attributes from one schema to multiple attributes in another.
  • Similarity Metric Impact: Investigating the impact of different similarity metrics and quality models on RCK deduction is planned.
  • MD Discovery: Developing algorithms to automatically discover MDs from sample data is a key area for future research.

Summary updated

BibTeX
@article{fan2009reasoning,
  author = {Wenfei Fan and Xibei Jia and Jianzhong Li and Shuai Ma},
  title = {{Reasoning about Record Matching Rules}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687674},
}
Figure