Measuring Approximate Functional Dependencies

M Parciak, S Weytjens, F Neven, L Peeters, N Hens, S Vansummeren

09/06/2023 - Knowledge Graphs for Data Integration Workshop, UHasselt

Introduction: Functional Dependencies (FDs)

Introduction: Approximate FDs (AFDs)

Introduction: Approximate FDs (AFDs)

Our Aim

Compare AFD measures proposed in the literature.

AFD measures: literature review

Literature review

Since 1954, 12 AFD measures were described.

​

We identify three groups

• Violation: quantify a number of FD violations
• Shannon: measures based on shannon entropy
• Logical: measures based on logical entropy

AFD measures: formal comparison

Identifying two new measures

Evaluation on Real-World Data

Approach

Test AFD measures on a real-world benchmark, which we manually annotate, and compare the measures on precision, recall and rankings.

Evaluation on Real-World Data

​

• three measures outperform the rest

Evaluating the ranking power

Evaluation on Real-World Data

​

• three measures outperform the rest
• largely attributed to R₃ & R₆

Evaluating the ranking power

Evaluation on Real-World Data

​

• three measures outperform the rest
• largely attributed to R₃ & R₆
• two structural properties confuse the measures:
• LHS-uniqueness
• RHS-skewness

Evaluating the ranking power

Sensitivity Analysis

Structural properties and AFD measures

​

​

​

Based on synthetic datasets, we find that

RFI’⁺ & 𝜇⁺ (both orange) separate FDs from non- FDs best.

Contributions

• uniform AFD measures definitions�(including an open-source implementation)
• formal comparison of AFD measures
• manually annotated real-world benchmark
• measure evaluation on the new benchmark
• sensitivity analysis of the measures
• AFD measure recommendations

Conclusions

1

2

3

𝜇⁺

• accurate (2nd on RWD^-)
• insensitive
• fast

RFI’⁺

• accurate (1st on RWD^-)
• insensitive
• slow

g’₃

• accurate (3rd on RWD^-)
• sensitive to skew
• fast