Functional dependencies are important metadata used for schema normalization, data cleansing and many other tasks. The efficient discovery of functional dependencies in tables is a well-known challenge in database research and has seen several approaches. Because no comprehensive comparison between these algorithms exist at the time, it is hard to choose the best algorithm for a given dataset. In this experimental paper, we describe, evaluate, and compare the seven most cited and most important algorithms, all solving this same problem. First, we classify the algorithms into three different categories, explaining their commonalities. We then describe all algorithms with their main ideas. The descriptions provide additional details where the original papers were ambiguous or incomplete. Our evaluation of careful re-implementations of all algorithms spans a broad test space including synthetic and real-world data. We show that all functional dependency algorithms optimize for certain data characteristics and provide hints on when to choose which algorithm. In summary, however, all current approaches scale surprisingly poorly, showing potential for future research. Functional dependencies (FDs) express relationships between attributes of a database relation. An FD X → A states that the values of attribute set X uniquely determine the values of attribute A. For instance, the zipcode attribute in an address relation usually determines the city attribute: zipcode → city. Due to this property, functional dependencies serve a wide range of data analysis, data integration, and data cleansing tasks. In particular, they are frequently used for schema normalization and database (re-)design. Liu et al. provide an excellent survey of the literature, analyzing many algorithms for functional dependency discovery . While all algorithms have the same goal, namely the discovery of all minimal, non-trivial functional dependencies in a given dataset, they differ in their approach. Existing evaluations and comparisons of subsets of the algorithms do not show well how the approaches differ in their runtime and memory behavior, and there has been no comparative study of this comprehensive set of algorithms in the past. Therefore, it is almost impossible for developers to find the right algorithm for their needs. In this paper, we analyze and compare the FD algorithms in detail. We measure their execution time and memory consumption on synthetic and real-world datasets and explain the algorithms' behavior in different scenarios. Furthermore, we provide hints on which algorithm should be used for which datasets. Overall, we could confirm original experimental results, where available. Contributions. We classify seven FD algorithms by their main concepts giving an overview on state-of-the-art developments. We revisit all algorithms and provide additional descriptions for their practical implementation where their original publications are sparse. We compare the algorithms on different datasets and evaluate both runtime and memory usage. From our experimental results, we derive concrete suggestions on when to use which algorithm. We also make all implementations, data, and the evaluation framework available online 1 . Structure. Section 2 gives an overview of FD discovery in general, discussing common concepts, alternative approaches, and our classification of discovery algorithms. Section 3 describes the implementation of the algorithms. Section 4 presents our evaluation results and Section 5 concludes the advantages and disadvantages of each discovery algorithm. We first formally define functional dependencies following the notation of [7] and then classify the seven FD algorithms by their technical and logical commonalities to give an overview on state-of-the-art FD discovery approaches.
The efficient discovery of exact FDs has gained particular interest REF .
Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms
PVLDB
PVLDB
Computer Science