Approximate functional dependencies: a comparison of measures and a relevance focused tool for discovery

Abstract

Many companies nowadays make use of data to optimize their processes. However, the collected data can contain various inconsistencies due to typing errors, for example. This forces the company to clean the data before deducing insights. One possible solution to discover erroneous information is finding columns that determine other columns, also called Functional Dependencies (FDs). For example, two people that live in the same city have to live in the same country. However, as FDs do not allow errors, we have to find a method to find dependencies that approximately hold in the relation, referred to as Approximate Functional Dependencies (AFDs). This thesis aims to design a relevance-focused tool for domain experts to discover AFDs. We review the existing measures to determine the degree of approximation of an AFD by testing them on various theoretical examples. Based on the findings of these tests, we decide on a combination of measures that focuses on discovering relevant AFDs. Then, we integrate those measures and other AFD metadata into c-metric, a score representing the confidence in a particular AFD. Our extensive experimental evaluation of the c-metric shows that the metric is significantly more suitable for relevant AFD discovery than the existing approximation measures. Finally, to assist domain experts in discovering relevant AFDs, we implement a tool that visualizes our c-metric and other AFD metadata, such as probability distributions.