The paper "Approximate Discovery of Functional Dependencies for Large Datasets" has been selected for presentation at the CIKM 2016. It pursues the idea of approximating the set of functional dependencies in a relational dataset instead of exactly calculating it, thereby trading little inaccuracies for great efficiency improvements. This paper is a result of the research of the Master's project "Approximate Data Profiling" and the extracurricular work of the participating students.

Abstract

Functional dependencies (FDs) are an important prerequisite for various data management tasks, such as schema normalization, query optimization, and data cleansing. However, automatic FD discovery entails an exponentially growing search and solution space, so that even today’s fastest FD discovery algorithms are limited to small datasets only, due to long runtimes and high memory consumptions.

To overcome this situation, we propose an approximate discovery strategy that sacrifices possibly little result correctness in return for large performance improvements. In particular, we introduce AID-FD, an algorithm that approximately discovers FDs within runtimes up to orders of magnitude faster than state-of-the-art FD discovery algorithms. We evaluate and compare our performance results with a focus on scalability in runtime and memory, and with measures for completeness, correctness, and minimality.