This is a repeatability page for functional dependency (FD) and order dependency (OD) discovery algorithms. You can find more repeatability pages (for other types of dependencies) here.

The algorithms are provided in the state their results have been published, but they may not represent the most recent version of their implementations. To get the more up-to-date version of the algorithms, use the binaries provided here.

The efficient discovery of functional dependencies in tables is a well-known challenge in database research and has seen several approaches.

An experimental evaluation of seven algorithms

The following seven FD algorithms have been evaluated as part of an experimental evaluation published in PVLDB Vol. 8.

All seven FD algorithms can be executed with the data profiling tool Metanome. A Metanome build in version 0.0.2 can be downloaded here.

Pyro is a discovery algorithm for approximate (or partial) functional dependencies. A paper on this algorithm has been published at PVLDB Vol. 11.

Note that Pyro is also capable of discovering partial unique column combinations and that the Pyro repository additionally contains versions of Tane, Ducc/Dfd, and fdep for partial FD/UCC discovery.

The exact discovery of all functional dependencies in relational tables is a complex task and, due to this complexity, state-of-the-art algorithms are often not able to process datasets of real-world size. When relaxing the discovery requirements, i.e., completeness, minimality, and correctness of the discovered FDs, we can build much more efficient, approximate algorithms. One such algorithm is the following, which has been published at CIKM'16:

The efficient discovery of order dependencies in tables is related to that of functional dependency discovery. An order dependency states that ordering a table by one set of attributes also orders the table by another set of attributes.

We also published a distributed discovery algorithm for bidirectional order dependencies DISTOD that you can find here.

You can find unlinked datasets here.

All FD algorithms have been exhaustively tested on the following datasets (null = null semantics):

Pyro has been evaluated with the datasets below.