Measuring Approximate Functional Dependencies:
a Comparative Study

We thank Dan Suciu for helpful discussions. S. Vansummeren was supported by the Bijzonder Onderzoeksfonds (BOF) of Hasselt University under Grant No. BOF20ZAP02. This research received funding from the Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programme. This work was supported by Research Foundation—Flanders (FWO) for ELIXIR Belgium (I002819N). The resources and services used in this work were provided by the VSC (Flemish Supercomputer Center), funded by the Research Foundation – Flanders (FWO) and the Flemish Government.

Marcel Parciak12,
Sebastiaan Weytjens2,
Niel Hens2,
Frank Neven2,
Liesbet M. Peeters12 and
Stijn Vansummeren2
1UHasselt, BIOMED, Agoralaan, 3590 Diepenbeek, Belgium
2UHasselt, Data Science Institute, Agoralaan, 3590 Diepenbeek, Belgium

Approximate functional dependencies (AFDs) are functional dependencies (FDs)
that “almost” hold in a relation. While various measures have been proposed
to quantify the level to which an holds approximately, they are difficult
to compare and it is unclear which measure is preferable when one needs to
discover in real-world data, i.e., data that only approximately satisfies
the . In response, this paper formally and qualitatively compares AFD
measures. We obtain a formal comparison through a novel presentation of
measures in terms of Shannon and logical entropy.

Qualitatively, we perform a sensitivity analysis w.r.t. structural properties
of input relations and quantitatively study the effectiveness of AFD measures
for ranking on real world data.  Based on this analysis, we give clear
recommendations for the AFD measures to use in practice.

functional dependencies, data cleaning, data profiling

§ INTRODUCTION

There are many benefits to knowing the set of functional dependencies (for
short) that are expected to hold in the instances of a database schema: aid
in ensuring data consistency and help in data
cleaning [1, 2];
facilitate data integration [3]; and can be
exploited for query
optimization [4, 5],
among other tasks.  In many data science scenarios, however, the set of design
is unknown or incomplete [6]. As such, a
variety of techniques have been proposed to reverse engineer this set of design
from a given relation instance
[7, 8, 9, 10, 6].

Reverse engineering is particularly challenging in the practical setting
where the relation instance itself does not satisfy the target set of design
.  This may happen, e.g.,
due to errors during data entry, resulting in a corrupt instance.  To recover
the set of design in such a setting, it clearly does not suffice to simply
enumerate the that are satisfied in the relation instance. Instead, one must also consider approximate functional dependencies
(), that is, that “almost hold” in the relation.
A key decision to then make is when an “almost” holds. This decision is
reflected in the adoption of an measure, which formally quantifies
the extent to which an holds approximately in a given relation by
attributing a score in the interval $[0,1]$. Higher values indicate a higher
degree of satisfaction. As such, an measure provides a way of
ranking the search space of all possible where higher-scoring are ranked before lower-scoring ones. A good measure, then, is one that
ranks in the relation's target set of design higher than those that
are not in the target set, and does this consistently for relation instances
that occur in practice. Given a good AFD measure one may discover the set of design FDs by ranking the search space, and returning all FDs smaller than a given threshold.

Many measures have been proposed
in the literature over the past decades [11, 12, 13, 14, 15, 16, 3, 17, 18].

Unfortunately, these measures vary widely in nature and there has been
little study so far in comparing them. As such there is no clear guideline for
deciding which measure(s) to adopt.  In response, we aim to address the following two central questions in this

(a) How do the different measures compare?

(b) Which measure(s) perform best and most consistently when discovering in real-world data?

We adopt the following methodology to answer (a): In
Section <ref> we present a survey of known measures in a uniform formal framework.
Specifically, we observe that there are three classes of measures: (i) measures that quantify the fraction of violations (we refer to them as ); (ii) measures based on Shannon entropy () [19]; and (iii) measures based on logical entropy () [20]. We then proceed to evaluate the measures' sensitivity
to structural properties of the input relation, in
Section <ref>.  Specifically, we study whether a measure can distinguish
between an $\X\to\Y$ in relation instances that were generated to approximately satisfy
the  versus relation instances where
$\X$ and $\Y$ were randomly generated. We evaluate this on synthetic data,
controlling the following parameters: (1) the error level; (2)
: the normalized number of unique values occurring in
; and  (3) :
the skewness of the distribution of values occurring in $\pi_{\Y}(R)$.[We refer to Table <ref> for an overview of the notation used in this paper.]
This evaluation
sheds light on the measure's distinguishing power as well as on their biases w.r.t. error level, and .
In general, measures are more robust  if they are inversely proportional to the error level and are insensitive to and , as we discuss in Section <ref>.

We adopt the following methodology to answer (b):
We compare the effectiveness of measures on real-world data.  Because existing benchmarks for exact discovery are designed to gauge algorithmic efficiency and  do not contain the “ground truth” set of design to compare against, we  propose a new discovery benchmark. This benchmark, denoted , is obtained by manually creating design for existing benchmarks.
Our analysis in Section <ref>
on shows that well-ranking measures exist within each class of measures
(, and ). Importantly, these measures are only effective
when they are correctly normalized—which is not always done in the
literature. Furthermore, the best-ranking measure for (measure $g'_3$,
which we formally introduce in Section <ref>) is sensitive to
and therefore performs worse than the best-ranking measures for
(measure $\RFInorm$) and (a little-known measure called
$\muplus$), which have comparable performance as well as equal structural
sensitivity properties. However, $\RFInorm$ is slow to compute, whereas $\muplus$
is very efficient. Therefore, we recommend $\muplus$ for practical discovery. More in-depth discussion and recommendations are given in
Section <ref>, where Table <ref> summarizes our

In summary, our contributions are as follows. (1) A survey of measures, using a new and uniform presentation.
(2) Sensitivity analysis of measure performance w.r.t. structural properties of the input relations. (3) Creation of a real-world benchmark for discovery. (4) Analysis of measure ranking power on this benchmark. (5) Clear recommendations for measure adoption in discovery.

The general organisation of the paper has already been outlined. In addition, we discuss related work and motivate the paper's scope in Section <ref>.
We introduce the necessary background in Section <ref>.
An extended paper version, containing extra experimental material that is omitted here due to lack of space, is available online [44].

§ RELATED WORK AND PAPER SCOPE

Relaxing .
In the literature there are two distinct
ways to relax the notion of an  [21]: relax
the constraint that an $\X \to \Y$ needs to be fully satisfied; or replace
the way in which tuples are compared on their $\X$-values by a similarity
function rather than strict equality. We focus on the former.

measures versus discovery algorithms. We focus on understanding measures and how they allow us to rank the search space
of possible for AFD discovery. A related but orthogonal issue, that we do not consider in this paper, is the study
of discovery algorithms. discovery algorithms usually fix a way
to quantify the approximateness of an —typically through the choice of an
measure that fixes a ranking of the search space—but then combine a
multitude of techniques to do the actual discovery. This includes pruning the
ranked search space for efficiency reasons (e.g.,
[22, 13, 14, 15])
or complementing the measures' ranking with heuristics for application-specific
purposes (e.g., [17, 23]).

Of course, improved knowledge of measures may aid in improving discovery
algorithms in the future. For this reason, when we introduce measures in
Section <ref> we also indicate in which discovery algorithms they
are used.  Because discovery algorithms do not directly expose the way in which
they rank the search space of , we do not experimentally compare against
discovery algorithms.

When an holds in
a relation, there is clearly a statistical correlation among the 's
attributes. Conversely, correlated attributes may (but need not) indicate the
presence of an . The techniques that are typically used to test statistical
correlation, such as the $\chi^2$ test or mean-square
contingency [17], however, only measure the
strength of correlation (e.g., $\X$ and $\Y$ are correlated) but do not indicate
the direction in which functional dependence ($\X \to \Y$ or $\Y \to \X$) is likely
to hold. As such, these techniques do not form appropriate measures [16] and are not further considered here.

Exact FD discovery. In the context of exact discovery, some works
consider the problem of ranking exact FDs according to relevance, where the
challenge lies in quantifying relevance [24]. We are not concerned with exact FD discovery, but with
measures for quantifying the extent to which hold approximately.
Discovery of should also not be confused with the approximate discovery of
exact as e.g., done in [10]. There,
only a subset of all that are satisfied are computed in return for
performance improvements.

Existing comparisons of measures.
Giannella and Robertson [12] compare a limited
number of measures on theoretical examples as
well as on 4 real world datasets. In their experiments, they report on average
differences between pairs of measures and do not compare with a ground truth set
of . They therefore do not empirically compare the effectiveness of the
measures as done here. In their survey concerning relaxations, Caruccio
et al. [21] also survey some of the measures that are considered here, but do not provide a qualitative comparison.

Discovery of Conditional FDs. Conditional (CFDs for short)
generalize FDs: they are FDs that only hold on a subset of the
data [25]. CFDs are widely used in data
cleaning [26, 27].
Discovery of (approximate) CFDs amounts to (i) selecting suitable subsets of the
data and (ii) discovering (A)FDs in these
subsets [28]. In particular, Geerts and
Rammelaere [28] propose a generic (A)CFD
discovery algorithm in which any (A)FD discovery algorithm can be plugged.
Insights into AFD measures, as is our focus here, can improve AFD discovery which in turn can be useful for the discovery of (A)CFDs.

Applications of . Data management tasks may use to
different extents. For example, only semantically meaningful (i.e., FDs
that a human database administrator would include in a database schema design)
are useful for data cleaning tasks [22] while
for query optimisation one could try to exploit all AFDs present in a
relation, even if they are not semantically meaningful. Our real-world
benchmark focuses on the former kind of .
Thus, we present a study of
measures applicable to discover semantically meaningful .

§ PRELIMINARIES

We summarize the notation used in this paper in Table <ref>.
We assume given a fixed set of attributes, where each attribute $X$ has a domain
$\dom(X)$ of possible data values.
We use uppercase letters $X,Y,Z$ to denote attributes and
boldface type like $\seq{X}, \seq{Y}, \seq{Z}$ to denote sets of attributes.
Lowercase $\seq{x}$, $\seq{y}$, $\seq{z}$ denote tuples over these sets.
Formally, as usual, a tuple over $\seq{X}$ is a mapping $\seq{x}$ that assigns
each attribute $X \in \seq{X}$ to a value $\seq{x}(X) \in \dom(X)$.
We write $\seq{x}\colon \seq{X}$ to indicate that $\seq{x}$ is a tuple over $\seq{X}$, and  $\restr{\seq{x}}{\seq Y}$ for the restriction of $\seq x$ to $\seq{Y} \subseteq \seq X$. We use juxtaposition like $\X\Y$ to denote the union $\X \cup \Y$ of two sets of attributes, and also apply this notation to tuples: if $\x \colon \X$ and $\y\colon \Y$ with $\X$ and $\Y$ disjoint, then $\x\y$ is the tuple that equals $\x$ on all attributes in $\X$ and $\y$ on all attributes in $\Y$, i.e. $\restr{\x\y}{\X} = \x$ and $\restr{\x\y}{\Y} = \y$.

We will work with bag-based relations. Formally, a relation over $\seq{X}$ (also
called $\seq{X}$-relation) is a mapping $R$ that assigns a natural number
$R(\seq{x}) \in \nats$ to each tuple $\seq{x}\colon \seq{X}$.

We require relations to be finite in the sense that $R(\seq{x})$ can be non-zero
for at most a finite number of $\seq{x}$.  We write $\seq x \in R$ to denote
that $R(\seq x) > 0$ and stress that $R$ is an $\seq X$-relation by means of the
notation $R(\seq X)$.  $\size{R}$ denotes the total number of tuples in $R$,
$\pi_{\Y}(R)$ denotes bag-based projection on $\Y$, and $\sigma_{\X = \x}(R)$
denotes bag-based selection. If $\Y \subseteq \X$ then we denote by $\dom_R(\Y)$
the set $\{ \restr{\x}{Y} \mid  \x \in R\}$.

Functional Dependencies. A functional dependency (for short) is an expression $\varphi$ of the form $\seq{X} \to \seq{Y}$. An is linear if $|\X| = |\Y| = 1$ and non-linear otherwise.
A relation $R(\W)$ with $\seq{X},\seq{Y} \subseteq \W$ satisfies $\varphi$  if for all tuples $\w, \seq{w'} \in R$ we have that $\restr{\w}{\Y} = \restr{\seq{w'}}{\Y}$ whenever $\restr{\seq{w}}{\X} = \restr{\seq{w'}}{\X}$.

In what follows, we always implicitly assume that $\X$ and $\Y$ are disjoint when considering .

Dependency Discovery. A schema is a finite set of
. In the exact discovery problem we are given a relation $R$ that
satisfies all in some fixed design schema $\schema(R)$, but have no knowledge
of $\schema(R)$ itself. We are then asked to recover $\schema(R)$ by  deriving the largest set $\Lambda \supseteq \schema(R)$ of
that are satisfied by $R$. In the approximate discovery problem, we are given a relation $R$ that does not satisfy $\schema(R)$ and again we are asked to recover $\schema(R)$. Here, we assume that $R$ is obtained by means of a noisy channel process as follows. From a clean relation $R'$ that satisfies $\schema(R)$, $R$ is obtained by modifying certain values in tuples in $R'$. We consider an error each cell for which $R$ differs from the clean version $R'$. Note that by running exact discovery algorithms on $R$, we will still be able to recover satisfied in $\schema(R)$. Our interest in this paper is in approximate discovery, i.e., deriving the in $\schema(R)$ that, because of errors introduced, are violated in $R$ and therefore cannot be discovered by exact discovery.

In Section <ref> we survey various measures that have been
proposed to quantify the level to which an holds approximately. As we will
see, many of these measures are based on exploiting notions of
Shannon or logical entropy.

We introduce these notions next.

Both notions of entropy are defined w.r.t. a given joint probability
distribution. In our setting, this probability distribution is defined by the
relation under consideration. Let $R(\W)$ be a relation. The
joint probability distribution $\prob_R(\seq{W})$ over $\W$ induced by $R$ is
defined by $\prob_R(\W = \w) = \frac{ R(\!\w) }{|R|}$. As such, $\prob_R(\W = \w)$ is the probability of observing $\w$ when
randomly drawing a tuple from $R$. We note that this probability distribution is
only well-defined when $R$ is non-empty. Because the empty relation vacuously satisfies all ,  we will implicitly assume without loss of generality
in the rest of this paper that relations are non-empty.

To simplify notation in what follows, we simply write $\prob_R(\w)$,
$\prob_R(\y)$ and $\prob_R(\y \mid \x)$ instead of $\prob_R(\W = \w)$,
$\prob_R(\Y = \y)$ and $\prob_R(\Y = \y \mid \X = \x)$, respectively.
The notions of marginal and conditional distributions derived from $\prob_R(\w)$
are defined as follows:

$\prob_R(\y)$ denotes the marginal probability
distribution on $\seq Y$-tuples in $R$, while
$\prob_R(\y \mid \x)$ is the conditional distribution on $\seq{Y}$ given $\seq{X}=\x$. Thus,

\begin{align*}
\prob_R(\seq y) = \sum_{\w: \W \text{ s.t. }
\restr{\seq w}{\seq Y} = \seq y} \prob_R(\seq w), \;\;\;\;\;\;
\prob_R(\seq y \mid \x) = \frac{\prob_R(\seq x\seq y)}{\prob_R(\seq x)}.
\end{align*}

It is readily verified that $\prob_R(\Y)$ equals the distribution induced by $\pi_Y(R)$, while $\prob_R(\Y \mid \X = \x)$ equals the distribution induced by $\pi_Y\sigma_{\X = \x}(R)$.

Shannon Entropy.
We write $\entrop_R(\seq{X})$ for the Shannon entropy of $\X$ in $R$,
defined as usual [19] by[Here and in the
sequel we use the common convention that $0 \log 0 = 0$ and
$\frac{0}{0} = 0$.]

\[ \entrop_R(\seq X) = - \sum_{\seq x\colon \seq X} \prob_R(\seq x) \log \prob_R(\seq x). \]

$\entrop_R(\seq X)$ reflects the average level of uncertainty inherent in the possible tuples over $\seq X$ in $\pi_X(R)$.
The conditional entropy $\entrop_R(\seq Y \mid \seq X)$ is the uncertainty in $\seq Y$ given $\seq X$, defined as

\begin{align*}
\entrop_R(\seq Y \mid \seq X) & = - \sum_{\seq x\colon \seq X, \seq y\colon \seq Y} \prob_R(\seq x \seq y) \log \frac{\prob_R(\seq x \seq y)}{\prob_R(\seq x)}.
\end{align*}

Equivalently, denoting by $\entrop_R(\Y \mid \x)$ the Shannon entropy of $\Y$ in the conditional distribution $\prob_R(\Y \mid \X = \x)$,  we see that $\entrop_R(\Y \mid \X)$ is the expected value of $\entrop_R(\Y \mid \x)$, taken over all $\x$, i.e., $\entrop_R(\Y \mid \X) = \expect_{\x}\left[\entrop_R(\Y \mid \x)\right]$.

Logical Entropy.
The logical entropy of $\X$ in $R$ is the probability that two tuples
$\seq{w}$ and $\seq{w'}$, drawn randomly with replacement from $R$ according to $\prob_R$, differ in some attribute in $\seq X$ [20]. That is,

\[ \logentrop_R(\seq{X}) := 1 - \sum_{\seq{x}\colon \seq X} p_R(\seq x)^2. \]

Here, $p_R(\seq x)^2$ is the probability that two random tuples are exactly equal to $\seq x$ on $X$.

We denote by $\logentrop_R(\Y \mid \x)$ the logical entropy of $\Y$ in the conditional distribution $\prob_R(\Y \mid \X = \x)$, i.e.,

\[ \logentrop_R(\Y \mid \x) = 1 - \sum_{\y \colon \Y} \prob_R(\y \mid \x)^2.\]

The logical conditional entropy of $\seq Y$ given $\seq X$ in $R$, denoted $h_R(\seq Y \mid \seq X)$, is the probability that two tuples, drawn at random with replacement from $R$ according to $p_R$, are equal in all attributes of $\seq X$, but differ in some attribute of $\seq Y$,

\begin{equation*}
\logentrop_R(\seq{Y} \mid \seq{X}) := \sum_{\x, \y} \prob_R(\x\y)[\prob_R(\x)-\prob_R(\x\y)].
\end{equation*}

Here, the factor $\prob_R(\x\y)$ expresses the probability of observing $\x\y$
in the first tuple and the factor $\prob_R(\x)-\prob_R(\x,\y)$ is the
probability that the second tuple has the same value for $\x$ but differs in

Note that, in contrast to the case of Shannon entropy where $\entrop_R(\Y \mid \X) = \expect_{\x}[ \entrop_R(\Y \mid \x)]$, in logical entropy $\logentrop_R(\Y \mid \X) \not = \expect_{\x}[ \logentrop_R(\Y \mid \x)]$.
We discuss the relationship between logical and Shannon entropy further in Appendix <ref>
We discuss the relationship between logical and Shannon entropy further in [44].

§ AFD MEASURES

In this section, we survey the literature on measures.

measures. Formally, an measure, short for
approximate measure, is a function that maps pairs $(\varphi, R)$,
with $\varphi$ an and $R$ a relation, to a number in the interval $[0,1]$
that indicates the level to which $\varphi$ holds in $R$. Higher values are
intended to indicate that $R$ makes fewer violations to $\varphi$, and we
require that $f(\varphi, R) = 1$ if $R$ perfectly satisfies $\varphi$.

It is important to note that instead of defining measures, some papers in
the literature define error measures where a high value indicates
a high number of errors against the . In what follows, we routinely re-define
such error measures $e$ into an measure $f_e$ by setting
$f_e(\varphi, R) := 1 - e(\varphi, R)$.

Every measure $f$ naturally gives rise to an associated discovery
algorithm as follows. From an abstract viewpoint, an discovery algorithm
simply consists of a fixed measure $f$ and a threshold
$\epsilon \in [0,1]$. Given a relation $R(\W)$ the algorithm returns all over $\W$ whose $f$-value lies in the range $[\epsilon,1[$. (In particular, this excludes the satisfied by $R$.)

Interpretation and baselines.
As with all threshold-based algorithms, a key difficulty for discovery
algorithms lies in determining the correct threshold $\epsilon$ to use. At its
core, this question boils down to how we should interpret the significance of
the values returned by $f$. It is tempting to see the values of $f$ as a
percentage with $f(\varphi, R) = 1$ indicating that $R$ perfectly satisfies
$\varphi$ and $f(\varphi, R) = 0$ indicating that $R$ completely fails to
satisfy $\varphi$.  This interpretation, however, is only valid if the measure
has a notion of $R$ “completely failing to satisfy” $\varphi$. In particular,
this is only possible when there are relations for which $f(\varphi,R) = 0$.
In what follows, we call a
relation $R$ with $f(\varphi, R) = 0$ a baseline of $f$ for $\varphi$. If
$f$ has a baseline for every $\varphi$ then we say that $f$ has
baselines, otherwise we call $f$ without baselines. Having baselines
is a necessary condition for interpreting measure scores as

Conventions. Throughout this section, assume that
$R$ is a $\W$-relation, let $\X,\Y$ be disjoint subsets of $\W$ and let
$\varphi = \X \to \Y$. We convene that for all measures $f$ that we describe, we
trivially set $f(\varphi, R) := 1$ if $R \models \varphi$. So, the definitions
that follow only apply when $R \not \models \varphi$. In that case, observe that
$R$ must be non-empty, that $\size{\!\dom_R(\X)} \not = \size{R}$ and that
$\size{\!\dom_R(\Y)} > 1$ since otherwise $R$ trivially satisfies $\X \to
\Y$. As a consequence, $\entrop_R(\Y) > 0$ and $\logentrop_R(\Y) > 0$. This ensures that the denominator of fractions in the formulas that follow are never zero.

§.§ Co-occurrence ratio

Ilyas et al. [17] consider the derivation of
(called soft in their paper) as well as general correlations
between attributes. To derive , they consider the
ratio between the number of distinct $\X$-tuples and the number of distinct
$\X\Y$-tuples occurring in $R$. We denote this measure by $\rho$, formally
defined as:

\[ \rho(\X \to \Y, R)  := \frac{|\dom_{\X}(R)|}{|\dom_{\X\Y}(R)|}. \]

This is $1$ if $R$ satisfies $\X \to \Y$ and decreases when more $\y$-tuples
occur with the same $\x$-tuple. Note that $\rho$ is a set-based measure, as it
ignores the multiplicities of the tuples in $R$. It is also
without baselines, as $\size{\!\dom_{\X}(R)}>0$ for any non-empty relation $R$
and as, by convention, $\rho(\varphi,R) = 1$ when $R$ is empty.

§.§ g-measures

Kivinen and Mannila [11] introduced three  error measures on set-based relations. Generalized to bag-based relations, and converted to measures, these are the following.

The measure $g_1$. The measure $g_1$ is based on logical
entropy. Specifically, Kivinen and Manila defined $g_1$ to reflect the
(normalized) number of violating pairs in $R$.  Here, a pair $(\w,\w')$ of
$R$-tuples is a violating pair if they are equal on $\X$ but differ on
$\Y$. Formally, if we denote the bag of violating pairs in $R \times R$ by
$G_1(\X \to \Y, R)$ then, converted to an measure instead of an error measure

\begin{align*}
g_1(\X \to \Y,R) & := \frac{|R|^2  - |G_1(\X \to \Y,R)|}{|R|^2} \\
& = 1 - \frac{|G_1(\X \to \Y,R)|}{|R|^2} =  1 - h_R(\Y \mid \X).
\end{align*}

In other words, $g_1$ is maximized when the logical conditional entropy is minimized.

The measure $g_1$ is without baselines.
Because pairs of the form $(\w,\w)$ are never violating, it is straightforward to see that the total number of violating pairs is bounded from above by $\size{R}^2 - \sum_{\w} R(\w)^2$. We denote by $g'_1$ the normalized version of $g_1$,

\begin{align*}
g'_1(\X \to \Y,R) & := 1 -  \frac{|G_1(\X \to \Y,R)|}{\size{R}^2-\sum_{\w} R(\w)^2}.
\end{align*}

The baselines of $g'_1$ are hence those relations for which the set $G_1(\X \to \Y, R)$ consists of all possible violating pairs.

Both $g_1$ and $g'_1$ have been used as the basis of discovery
algorithms. In particular, $g_1$ is the basis of
Fdx [23] while $g'_1$ is the basis of
Pyro [22].  Adaptations of $g'_1$ are also used in the context of denial constraints  [29]
and roll-up dependencies [30].

The measure $g_2$. Kivinen and Manila defined $g_2$ to reflect the probability that a random tuple participates in a violating pair. We define $G_{2}(\X \to \Y, R)$ to be the set of all tuples in $R$ that participate in a violating pair,

\begin{align*}
G_{2}(\X {\tiny\to} \Y, R):=\left\{ \w\in R\mid \exists \w' \in R, (\w,\w') \in G_1(\X {\tiny\to} \Y, R) \right\}.
\end{align*}

Then, $g_2$, converted to an measure instead of
an error measure as originally proposed,
computes the probability that a tuple, drawn randomly from $R$ according to $\prob_R$, is not part of a violating pair,

\[ g_2(\X \to \Y, R) := 1 - \sum_{\w \in G_2(\X \to \Y, R)} \prob_R(\w) . \]

The FD-compliance-ratio, that is used as one of the building blocks in UNI-DETECT  [31], is based on $g_2$.

The measure $g_3$. The measure $g_3$ computes the relative size of a maximal subrelation of $R$ for which $\X \to \Y$ holds. Specifically, define $R'(\W)$ to be a subrelation of $R(\W)$, denoted $R'\subseteq R$, if $R'(\w) \leq R(\w)$
for all $\w\colon \W$. Let $G_3(\X\to \Y, R)$ denote the set of all subrelations of $R$ that satisfy $\X \to \Y$,

\[ G_3(\X\to\Y, R) := \left\{R' \mid R'\subseteq R, R'\models \X\to \Y \right\}.\]
$g_3$ is defined as the maximum relative size of a subrelation satisfying $\X \to \Y$:

\begin{align*}
g_3(\X \to \Y, R) & := \max_{R' \in G_3(\X \to \Y, R)} \frac{|R'|}{|R|}.
\end{align*}

Note that $1-g_3(\X \to \Y, R)$ can naturally be interpreted as the minimum fraction of tuples that need to be removed for $\X \to \Y$ to hold in $R$.

The measure $g_3$ is without baselines. For any non-empty $R$ we can
always obtain a subrelation $R' \in G_3(\varphi, R)$ of size
$\size{\!\dom_{\X}(R)}$ by arbitrarily fixing one $\y$-value for each
$\x$-value. As such, $g_3$ is bounded from below by
$\frac{|\dom_{\X}(R)|}{\size{R}} > 0$. Gianella and
Robertson [12] proposed a normalized variant
$g'_3$ of $g_3$, defined as follows:

\begin{align*}
g'_3(\X \to \Y, R) & := \max_{R' \in G_3(\X \to \Y, R)} \frac{\size{R'} - \size{\dom_{R}(\X)}}{\size{R} - \size{\dom_{R}(\X)}}.
\end{align*}

This variant has baselines, namely all relations $R$ for which no
subrelation $R' \in G_3(\varphi,R)$ is larger than $\size{\dom_R(\X)}$.

The unnormalized measure $g_3$ is used in multiple discovery algorithms [11, 9, 32, 33]. Furthermore, the `per-tuple' probability of an , as defined in [3], is precisely  $g_3$.

Berzal et al. [18] use it as the basis for relational decomposition based on instead of .
Exact and approximate solutions for the computation of $g_3$ in the context of non-crisp are proposed in [34].
We note that $g_3$ has been generalized to other dependencies as well: e.g.,
conditional  [35, 36],  inclusion dependencies [37], and conditional matching dependencies [38].
By contrast, the normalized version $g'_3$ only appears in  [12].

§.§ Fraction of information

Fraction of Information. Cavallo and Pittarelli [39] introduced
fraction of information ()  as a way to generalize from
deterministic to probabilistic databases.  Usage of as an measure was later studied by Giannelli and Robertson [12]
is based on Shannon entropy and is formally defined as

\[ \FI(\X \to \Y, R) :=
% \begin{cases}
%   1                                                           & \text{ if } |\dom_R(\Y)| = 1, \\
\frac{\entrop_R(\Y) - \entrop_R(\Y \mid \X)}{\entrop_R(\Y)}. % & \text{otherwise.}
% \end{cases}
\]

The numerator $\entrop_R(\Y) - \entrop_R(\Y \mid \X)$ is known as mutual information [19], which we further denote by $\mut_R(\X; \Y)$.

We can understand as follows.  $\entrop_R(\Y)$ measures the uncertainty of
observing $\Y$, while $\entrop_R(\Y \mid \X)$ measures the uncertainty of
observing $\Y$ after observing $\X$. hence represents the proportional
reduction of uncertainty about $\Y$ that is achieved by knowing $\X$. When $R$
satisfies $\X \to \Y$, there is no uncertainty about $\Y$ after observing $\X$
and hence $\entrop_R(\Y \mid \X) = 0$ and so is $1$. Conversely, when $\X$
and $\Y$ are independent random variables in $\prob_R$, there is no
reduction in uncertainty, and hence $\entrop_R(\Y\mid \X)=\entrop_R(\Y)$ and so
$\FI$ is $0$.  Thus, the baselines of $\FI$ for $\X \to \Y$ are
those relations $R$ for which $\X$ and $\Y$ are independent in $\prob_R$.

Mandros et al. [13, 14]
and Pennerath et al. [15] proposed two refinements
to specifically for discovery, called reliable  () and
smoothed  (), respectively. They are motivated in proposing these
refinements by the following observation. Consider a relation $S(\W)$ and assume
that we are given relation $R(\W)$ of size $n$ that is obtained by sampling $n$
tuples from $S$ according to distribution $\prob_S$. Further assume that we do
not have access to $S$ and wish to determine $\FI(\X \to \Y, S)$ based on
$R$. Then a result by Roulston [40] states that the expected
value of $\mut_R(\X; \Y)$, taken over all $R$ obtained in this manner, equals

\begin{equation*}
\mut_S(\X; \Y) + \frac{\size{\dom_S(\X\Y)} - \size{\dom_S(\X)} - \size{\dom_S(\Y)} + 1}{2n}.
\end{equation*}

In other words, we may expect  $\mut_R(\X; \Y)$ to overestimate
$\mut_S(\X; \Y)$ and the magnitude of overestimation depends on the size of the
active domains of $\X\Y$, $\X$, and $\Y$ in $S$, as well as on $n$.  Additionally, because $\entrop_R(\Y)$ underestimates $\entrop_S(\Y)$ [40],
we may conclude that  $\FI(\X \to \Y, R)$ is expected to overestimate
$\FI(\X \to \Y, S)$ and the magnitude of overestimation depends on the active
domain sizes and the size of $S$. This overestimation is problematic since $\FI(\X \to \Y, R)$ will be quite large, even if $\X$ and $\Y$ are independent in $\prob_S$, resulting in $\FI(\X \to \Y, S)$ being $0$.

*Reliable .
Reliable corrects for this bias by subtracting the mutual information value
that is expected under random $(\X;\Y)$-permutations.

Relation $R'$ is an $(\X;\Y)$-permutation of $R$, denoted
$R \sim_{\X;\Y} R'$
if (i) $\size{R} = \size{R'}$; (ii)
$\pi_{\X}(R) = \pi_{\X}(R')$; (iii) $\pi_{\Y}(R) = \pi_{\Y}(R')$; and (iv) $\pi_{\Z}(R) = \pi_{\Z}(R')$ where $\Z = \W \setminus \X\Y$.

In particular, $R'$ and $R$ have the same marginal distributions on $\X$ and on $\Y$, $\prob_{R'}(\X) = \prob_R(\X)$ and $\prob_{R'}(\Y) = \prob_R(\Y)$. In what follows, for a measure $f$, we denote by $\expect_{R}[f(\X \to \Y, R))]$ the expected value of $f(\X \to \Y,R)$ where the expectation is taken over all  $(\X;\Y)$-permutations of $R$.

Reliable fraction of information is then defined as

\begin{align*}
\RFI(\X \to \Y, R) & := \FI(\X \to \Y, R) - \expect_{R}[ \FI(\X \to \Y, R)].
\end{align*}

Because the number of permutations of $R$ is finite, we may compute $\expect_R[\FI(\X \to \Y, R)]$, and hence also $\RFI(\X \to \Y, R)$, by simply computing $\FI(\X \to \Y, R')$ for every permutation $R'$ of $R$ and taking the average. More efficient algorithms are proposed in [14, 13]. Even with these improved algorithms, computing $\RFI$ remains inefficient, as we show in Section <ref>.

Strictly speaking, $\RFI$ is not an measure since it can become negative when $\FI(\varphi, R) < \expect_{R}[\FI(\varphi, R)]$. Because such negative $\RFI$ values indicate that there is weak evidence to conclude that $\varphi$ is an , we turn $\RFI$ into an actual AFD measure $\RFIplus$ by setting

\[
\RFIplus(\X \to \Y, R) := \max(\RFI(\X \to \Y, R), 0).
\]

The baselines of $\RFIplus$ for $\X \to \Y$ are hence all relations whose value is smaller or equal than the expected value under random permutations.

*Smoothed .
Smoothed uses laplace smoothing to reduce bias. Laplace smoothing is
a well-known statistical technique to reduce estimator variance. It is
parameterized by a value $\alpha > 0$. Specifically, for a relation $S(\X\Y)$, let $S^{(\alpha)}$
denote the $\alpha$-smoothed version of $S$, defined by
$S^{(\alpha)}(\x\y) := S(\x\y) + \alpha$ for every $\x \in \dom_{S}(\X)$ and $\y \in \dom_S(\Y)$. Note in particular, that it is possible that  $S(\x\y) = 0$, in which case $S^{(\alpha)}(\x\y) = \alpha$. Then the smoothed of $R$ is simply the normal of the $\alpha$-smoothed version of $\pi_{\X\Y}(R)$:

\begin{align*}
\SFI_{\alpha}(\X \to \Y, R) & := \FI(\X \to \Y, \pi_{\X\Y}^{(\alpha)}(R)).
\end{align*}

We note that, because $\pi_{\X\Y}^{(\alpha)}(R)$ contains a tuple $\x\y$ for every possible combination of $\x \in \dom_{\X}(R)$ and $\y \in \dom_{\Y}(R)$, it can be many times larger than $R$. is therefore also relatively inefficient to compute, as we show in Section <ref>.

discovery algorithms based on and are presented in [13, 14]
and [15], respectively.

§.§ Probabilistic dependency, $\tau$ and $\mu$

Piatetsky-Shapiro and Matheus [16] proposed probabilistic
dependency as another probabilistic generalization of a functional
dependency. They also introduced a normalized version of probabilistic
dependency, which is equivalent to the Goodman and Kruskal $\tau$ measure of
association [41]. Finally, they also propose a rescaled
version of $\tau$. All three notions are defined as follows. It is worth noting,
that, apart from [16], we are not aware of any work that
considers these measures for discovery in the database context, let alone
designs discovery algorithms for them.

*Probabilistic dependency.
The probabilistic dependency of $\Y$ on $\X$ in $R$, denoted by
$\pdep(\X \to \Y, R)$, represents the conditional probability that two tuples
drawn randomly with replacement from $R$ are equal on $\Y$, given that they are
equal on $\X$. Formally,

\begin{align*}
\pdep(\X \to \Y, R) & := \sum_{\x} \prob_R(\x) \pdep(\Y \mid \x, R),
\end{align*}

where $\pdep(\Y \mid \x, R)$ is the probability that two random $\Y$-tuples
drawn with replacement from the conditional distribution $\prob_R(\Y \mid \x)$
are equal:

\[ \pdep(\Y \mid \x, R) := \sum_{\y} \prob_R(\y \mid \x)^2 = 1 - \logentrop_R(\Y \mid \x). \]

Probabilistic dependency is hence a measure based on logical entropy.
It can be understood as follows. Suppose that we are given two tuples that equal
$\x$ on $\X$. Then $\pdep(\Y\mid \x, R)$ is the probability that these tuples are
also equal on $\Y$, and $\pdep(\X \to \Y, R)$ is the expected value of
$\pdep(\Y\mid \x, R)$ over all $\x$.

We note that probabilistic dependency can also be seen as a generalization of the measure $g_2$. Whereas $g_2$ computes the probability that a random tuple cannot be extended to a violating pair, probabilistic dependency computes the average conditional probability that a given $\X$-tuple $\x$ cannot be extended to a violating pair, where the average is taken over all values of $\X$.

*The measure $\tau$. It is straightforward to see that $\pdep(\X \to \Y, R) > 0$, always. As such, $\pdep$ is a measure without baselines. In fact, Piatetsky-Shapiro and Matheus [16] show that we always have

\[ \pdep(\X \to \Y, R) \geq \pdep(\Y, R) \]

where $\pdep(\Y, R)$, called probabilistic self-dependency,  is defined
as the probability that two random tuples in $R$ have equal $\Y$ attributes,

\[ \pdep(\Y, R) := \sum_{\y} \prob_R(\y)^2 = 1 - \logentrop_R(\Y). \]

To account for the relationship between $\pdep(\X \to \Y, R)$ and $\pdep(\Y,R)$,
Piatetsky-Shapiro and Matheus propose to normalize $\pdep(\X\to\Y,R)$ w.r.t. $\pdep(\Y,R)$. The
resulting measure is equivalent to the Goodman and Kruskal $\tau$ (tau) measure
of association [41], which is defined as

\begin{align*}
\tau(\X\to \Y, R) :=
\frac{\pdep(\X \to \Y, R)-\pdep(\Y, R)}{1-\pdep(\Y, R)}.
\end{align*}

Piatetsky-Shapiro and Matheus
explain $\tau$  in the following way [16]. Suppose we
are given a tuple drawn randomly from $R$ according to $\prob_R$, and we need to
guess its $\Y$ value. One strategy is to make guesses randomly according to the
marginal distribution of $\Y$, i.e. guess value $\Y=\y$ with probability
$\prob_R(\y)$. Then the probability for a correct guess is $ \pdep(\Y,R)$. If we
also know that item has $\X=\x$, we can improve our guess using conditional
probabilities of $\Y$, given that $\X=\x$. Then our probability for success,
averaged over all values of $\X$, is $\pdep(\X \to \Y,R)$, and
$\tau(\X \to \Y, R)$ is the relative increase in our probability of successfully
guessing $\Y$, given $\X$. The baselines of $\tau$ for $\X \to \Y$ are hence those relations where this relative increase is zero.

The measure $\mu$. Piatetsky-Shapiro and
Matheus [16] note that $\pdep$ and $\tau$ have the following undesirable property.

Given a random relation $R$ of size $N\geq 2$ containing attributes $\X$ and $\Y$, where $\X$ has $K = \size{\dom_R(\X)}$ distinct values in its active domain, the expected values of $\pdep$ and $\tau$ under random permutations of $R$ are

\begin{align*}
\expect_R[\pdep(\X {\tiny\to} \Y, R)] & = \pdep(\Y, R) + \frac{K-1}{N-1}(1-\pdep(\Y, R)), \\
\expect_R[\tau(\X {\tiny\to} \Y, R)] & = \frac{\size{\dom_R(\X)}-1}{\size{R}-1}.
\end{align*}

Thus, for a fixed distribution of $\Y$ values, $\expect_R[\pdep(\X \to \Y,R)]$
depends only on the number of distinct $\X$ values and not on their relative
frequency. Moreover, the formula for $\expect_R[\tau(\X\to\Y, R)]$ tells us that
if we have two candidate with the same right hand side, $\X \to \Y$ and
$\Z \to \Y$, then if $\size{\dom_R(\Z)} > \size{\dom_R(\X)}$, we may expect
$\tau$ to score $\Z \to \Y$ better than $\X \to \Y$, regardless of any intrinsic
better relationship between $\Z$ and $\Y$ over $\X$ and $\Y$ in $R$. In
response, Piatetsky-Shapiro and Matheus compensate for this effect by
introducing the measure $\mu$ which normalizes $\pdep(\X\to \Y, R)$ with respect
to $\expect_R[\pdep(\X\to \Y, R)]$ instead of
$\pdep(\Y, R)$:[This fraction is ill-defined
if the denominator $1 - \expect_R[\pdep(\varphi,R)] = 0$. This only happens,
however, when $R \models \varphi$, which we have assumed not to be the case
throughout this section, since we have already convened to set
$\mu(\varphi,R) = 1$ whenever $R \models \varphi$. See the
full paper [44] for a proof.See the Appendix for a

\begin{align*}
\mu(\X{\tiny\to}\Y, R) & := \frac{\pdep(\X {\tiny\to} \Y, R)-\expect_R[\pdep(\X {\tiny\to} \Y, R)]}{1-\expect_R[\pdep(\X {\tiny\to} \Y, R)]} \\
& = 1-\frac{1-\pdep(\X {\tiny\to} \Y, R)}{1-\pdep(\Y, R)} \frac{|R|-1}{|R|-|\dom_R(\X)|}
\end{align*}

Strictly speaking, $\mu$ is not a measure since it returns negative values when $\pdep(\X \to \Y, R) > \expect_R[\pdep(\X \to \Y, R)]$.  Because such negative $\mu$ values indicate that there is weak evidence to conclude that $\varphi$ is an , we turn $\mu$ into an actual AFD measure $\muplus$ by setting

\[ \muplus(\X \to \Y, R) := \max(\mu(\X \to \Y, R), 0). \]

The baselines of $\muplus$ for $\X \to \Y$ are hence all relations where the $\pdep(\X \to \Y)$ value is smaller or equal to the expected value under random permuations.

§.§ Classes of AFD measures.

Looking at the previous definitions, we observe three different notions that are used to formally define a measure. Consequently, we discern the following three classes (see also the second row in Table <ref>):

* The class of measures that have a notion of “violation” and quantify the number of violations, consisting of $\rho, g_2, g_3$, and $g'_3$. We denote this class by $\simple$ ().

* The class of measures based on Shannon entropy, consisting of $\FI, \RFIplus$, and $\SFI$. We denote this class by $\shannon$ ().

* The class of measures based on logical entropy, consisting of $g_1,g'_1, \pdep, \tau$, and $\muplus$ and denoted by $\logical$ ().

In the full paper version [44]In appendix <ref> we observe that there are
striking similarities between measures in each of these classes, allowing
us to relate and link measures across classes. For example, we can
show that $\FI$ is the $\shannon$-based version of $\tau$, while $\pdep$
is a $\logical$-based version of $g_2$. This gives a first insight into
how measures compare formally. By means of this comparison, we have
identified the following two new measures, which do not appear in the
literature but which are $\shannon$ versions of existing measures. For
completeness, we include both of these measures in our study.

The new measure . The measure $g_1$ is based on logical entropy. We may hence view $1 - \entrop_R(\Y \mid \X)$ as the
Shannon equivalent of $g_1$, where logical entropy is replaced by Shannon entropy.
Giannella and Robertson [12] observed that
$1 - \entrop_R(\Y \mid \X)$ has the range $[-\infty, 1]$ instead of $[0,1]$
and therefore disregard it as an measure.
Nevertheless, we propose the following Shannon variant
for our comparison, obtained by limiting $1  - \entrop_R(\Y\mid\X)$ to be positive:

\[ \SHANNONGONE(\X \to \Y, R) := \max(1 - \entrop_R(\Y \mid \X), 0). \]

The new measure .
We also observe a conceptual similarity between $\mu$ and $\RFI$: $\mu$ corrects for the  bias of $\tau$ under random permutations while $\RFI$ corrects for the bias of $\FI$ under random permutations. Despite this conceptual similarity, note that the corrections are done differently: $\mu$ corrects by taking the normalized difference between $\pdep$ and $\expect_R[\pdep]$ while $\RFI$ corrects by taking the absolute difference between $\FI$ and $\expect_R[\FI]$. As such, $\RFI$ is not a normalized measure. Since it is natural to ask what the normalized variant of $\RFI$ is and how it behaves, we define

\[ \RFInorm(\varphi, R) := \max\left(\frac{\FI(\varphi,R) - \expect_R[\FI(\varphi,R)]}{1 -\expect_R[\FI(\varphi,R)]}, 0\right). \]

§ SENSITIVITY ANALYSIS

§ EVALUATION ON REAL-WORLD DATA

§ CONCLUSIONS

An overview of our results is given in Table <ref>. We find that well-ranking measures exist within each class: $g'_3$ in , in , and $\muplus$ in .
We further observe that measures are only effective when correctly normalized—which is not always done in the literature.

$g_3$ is widely known and cited [11, 9, 32, 12, 33, 34, 18]
but to the best of our knowledge only [12] considers the correctly normalized version $g'_3$. The sensitivity of $g'_3$ to remains a structural weakness,  hampering its effectiveness
as illustrated by its lower performance in practice on (Fig <ref>).

is the defining measure of and suffers from sensitivity to as illustrated by its behavior on . Its corrections
[15] and  [13, 14] were aimed at removing bias from , but our experiments on reveal that their distinguishing power is greatly diminished; they especially overcompensate their correction of w.r.t. . This is reflected by their behavior on , where they are  among the worst performing measures. Our novel correction of is the best performing measure on and is insensitive to both and . Its main drawback is the slow computation by current algorithms rendering it essentially useless in practice.

Our recommendation for most suitable measure is therefore the little-known measure $\mu$. It has comparable performance to as well as equal structural sensitivity properties, but can be efficiently computed.

When the number of attributes in the LHS increases, LHS-uniqueness is expected to increase naturally to $1$. Since $g'_3$, , and are the only measures among the considered ones that are insensitive to , they are the most promising  measures for discovering non-linear .

Another finding worth noting is that we illustrated on , perhaps contrary to popular belief, that by only inspecting a small number of top-ranked candidate (according to $g'_3$, $\RFInorm$, $\mu$), one already succeeds in finding a large number of true design FDs that were obscured by errors. This means in particular, that a domain expert does not need to wade through hundreds of high-ranked candidate but can restrict attention to a handful.

Inspired by Arocena et al. [45],
we study in Appendix <ref> the measures' sensitivity to
different kinds and different levels of errors by passing the relations in $\rwd$
through a controlled error channel. We again find that $\RFInorm$ and $\muplus$
perform best, closely followed by $g'_3$. We also find that the effectiveness
of all measures quickly deteriorates for increasing error levels making them
essentially useless for error levels above $5\%$.

[1]
X. Chu, I. F. Ilyas, and P. Papotti, “Holistic data cleaning: Putting violations into context,” in 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013 (C. S. Jensen, C. M. Jermaine, and X. Zhou, eds.), pp. 458–469, IEEE Computer Society, 2013.

[2]
T. Rekatsinas, X. Chu, I. F. Ilyas, and C. Ré, “Holoclean: Holistic data repairs with probabilistic inference,” Proc. VLDB Endow., vol. 10, no. 11, pp. 1190–1201, 2017.

[3]
D. Z. Wang, X. L. Dong, A. D. Sarma, M. J. Franklin, and A. Y. Halevy, “Functional dependency generation and applications in pay-as-you-go data integration systems,” in 12th International Workshop on the Web and Databases, WebDB 2009, Providence, Rhode Island, USA, June 28, 2009, 2009.

[4]
H. Liu, D. Xiao, P. Didwania, and M. Y. Eltabakh, “Exploiting soft and hard correlations in big data query optimization,” Proc. VLDB Endow., vol. 9, no. 12, pp. 1005–1016, 2016.

[5]
J. Kossmann, T. Papenbrock, and F. Naumann, “Data dependencies for query optimization: a survey,” VLDB J., vol. 31, no. 1, pp. 1–22, 2022.

[6]
T. Papenbrock and F. Naumann, “A hybrid approach to functional dependency discovery,” in Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016 (F. Özcan, G. Koutrika, and S. Madden, eds.), pp. 821–833, ACM, 2016.

[7]
T. Papenbrock, J. Ehrlich, J. Marten, T. Neubert, J. Rudolph, M. Schönberg, J. Zwiener, and F. Naumann, “Functional dependency discovery: An experimental evaluation of seven algorithms,” Proc. VLDB Endow., vol. 8, no. 10, pp. 1082–1093, 2015.

[8]
P. Schirmer, T. Papenbrock, S. Kruse, F. Naumann, D. Hempfing, T. Mayer, and D. Neuschäfer-Rube, “Dynfd: Functional dependency discovery in dynamic datasets,” in Advances in Database Technology - 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, March 26-29, 2019 (M. Herschel, H. Galhardas, B. Reinwald, I. Fundulaki, C. Binnig, and Z. Kaoudi, eds.), pp. 253–264, OpenProceedings.org, 2019.

[9]
L. Berti-Équille, H. Harmouch, F. Naumann, N. Novelli, and S. Thirumuruganathan, “Discovery of genuine functional dependencies from relational data with missing values,” Proc. VLDB Endow., vol. 11, no. 8, pp. 880–892, 2018.

[10]
T. Bleifuß, S. Bülow, J. Frohnhofen, J. Risch, G. Wiese, S. Kruse, T. Papenbrock, and F. Naumann, “Approximate discovery of functional dependencies for large datasets,” in Proceedings of the 25th ACM International Conference on Information and Knowledge Management, CIKM 2016, Indianapolis, IN, USA, October 24-28, 2016 (S. Mukhopadhyay, C. Zhai, E. Bertino, F. Crestani, J. Mostafa, J. Tang, L. Si, X. Zhou, Y. Chang, Y. Li, and P. Sondhi, eds.), pp. 1803–1812, ACM, 2016.

[11]
J. Kivinen and H. Mannila, “Approximate inference of functional dependencies from relations,” Theor. Comput. Sci., vol. 149, no. 1, pp. 129–149, 1995.

[12]
C. Giannella and E. L. Robertson, “On approximation measures for functional dependencies,” Inf. Syst., vol. 29, no. 6, pp. 483–507, 2004.

[13]
P. Mandros, M. Boley, and J. Vreeken, “Discovering reliable approximate functional dependencies,” in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13 - 17, 2017, pp. 355–363, ACM, 2017.

[14]
P. Mandros, M. Boley, and J. Vreeken, “Discovering dependencies with reliable mutual information,” Knowl. Inf. Syst., vol. 62, no. 11, pp. 4223–4253, 2020.

[15]
F. Pennerath, P. Mandros, and J. Vreeken, “Discovering approximate functional dependencies using smoothed mutual information,” in KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020 (R. Gupta, Y. Liu, J. Tang, and B. A. Prakash, eds.), pp. 1254–1264, ACM, 2020.

[16]
G. Piatetsky-Shapiro and C. J. Matheus, “Measuring data dependencies in large databases,” in Proceedings of the 2nd International Conference on Knowledge Discovery in Databases, pp. 162––173, AAAI Press, 1993.

[17]
I. F. Ilyas, V. Markl, P. J. Haas, P. Brown, and A. Aboulnaga, “CORDS: automatic discovery of correlations and soft functional dependencies,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13-18, 2004 (G. Weikum, A. C. König, and S. Deßloch, eds.), pp. 647–658, ACM, 2004.

[18]
F. Berzal, J. Cubero, F. Cuenca, and J. Medina, “Relational decomposition through partial functional dependencies,” Data and Knowledge Engineering, vol. 43, no. 2, pp. 207–234, 2002.

[19]
S. Edwards, “Thomas m. cover and joy a. thomas, elements of information theory (2nd ed.), john wiley & sons, inc. (2006),” Inf. Process. Manag., vol. 44, no. 1, pp. 400–401, 2008.

[20]
D. Ellerman, New Foundations for Information Theory - Logical Entropy and Shannon Entropy.
SpringerBriefs in Philosophy, Springer, 2021.

[21]
L. Caruccio, V. Deufemia, and G. Polese, “Relaxed functional dependencies - A survey of approaches,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 1, pp. 147–165, 2016.

[22]
S. Kruse and F. Naumann, “Efficient discovery of approximate dependencies,” Proc. VLDB Endow., vol. 11, no. 7, pp. 759–772, 2018.

[23]
Y. Zhang, Z. Guo, and T. Rekatsinas, “A statistical perspective on discovering functional dependencies in noisy data,” in Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020 (D. Maier, R. Pottinger, A. Doan, W. Tan, A. Alawini, and H. Q. Ngo, eds.), pp. 861–876, ACM, 2020.

[24]
Z. Wei and S. Link, “Discovery and ranking of functional dependencies,” in 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019, pp. 1526–1537, IEEE, 2019.

[25]
P. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis, “Conditional functional dependencies for data cleaning,” in Proceedings of the 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey, April 15-20, 2007 (R. Chirkova, A. Dogac, M. T. Özsu, and T. K. Sellis, eds.), pp. 746–755, IEEE Computer Society, 2007.

[26]
W. Fan, F. Geerts, and X. Jia, “A revival of integrity constraints for data cleaning,” Proc. VLDB Endow., vol. 1, no. 2, pp. 1522–1523, 2008.

[27]
W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis, “Conditional functional dependencies for capturing data inconsistencies,” ACM Trans. Database Syst., vol. 33, no. 2, pp. 6:1–6:48, 2008.

[28]
J. Rammelaere and F. Geerts, “Revisiting conditional functional dependency discovery: Splitting the "c" from the "fd",” in Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2018, Dublin, Ireland, September 10-14, 2018, Proceedings, Part II, vol. 11052 of Lecture Notes in Computer Science, pp. 552–568, Springer, 2018.

[29]
E. H. M. Pena, E. C. de Almeida, and F. Naumann, “Discovery of approximate (and exact) denial constraints,” Proc. VLDB Endow., vol. 13, no. 3, pp. 266–278, 2019.

[30]
T. Calders, R. T. Ng, and J. Wijsen, “Searching for dependencies at multiple abstraction levels,” ACM Trans. Database Syst., vol. 27, no. 3, pp. 229–260, 2002.

[31]
P. Wang and Y. He, “Uni-detect: A unified approach to automated error detection in tables,” in SIGMOD, pp. 811–828, ACM, 2019.

[32]
Y. Huhtala, J. Kärkkäinen, P. Porkka, and H. Toivonen, “TANE: an efficient algorithm for discovering functional and approximate dependencies,” Comput. J., vol. 42, no. 2, pp. 100–111, 1999.

[33]
R. S. King and J. J. Legendre, “Discovery of functional and approximate functional dependencies in relational databases,” Adv. Decis. Sci., vol. 7, no. 1, pp. 49–59, 2003.

[34]
P. Faure-Giovagnoli, J. Petit, and V. Scuturici, “Assessing the existence of a function in a dataset with the g3 indicator,” in 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022, pp. 607–620, IEEE, 2022.

[35]
G. Cormode, L. Golab, F. Korn, A. McGregor, D. Srivastava, and X. Zhang, “Estimating the confidence of conditional functional dependencies,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, Providence, Rhode Island, USA, June 29 - July 2, 2009 (U. Çetintemel, S. B. Zdonik, D. Kossmann, and N. Tatbul, eds.), pp. 469–482, ACM, 2009.

[36]
J. Rammelaere and F. Geerts, “Explaining repaired data with cfds,” Proc. VLDB Endow., vol. 11, no. 11, pp. 1387–1399, 2018.

[37]
F. D. Marchi, S. Lopes, and J. Petit, “Unary and n-ary inclusion dependency discovery in relational databases,” J. Intell. Inf. Syst., vol. 32, no. 1, pp. 53–73, 2009.

[38]
Y. Wang, S. Song, L. Chen, J. X. Yu, and H. Cheng, “Discovering conditional matching rules,” ACM Trans. Knowl. Discov. Data, vol. 11, no. 4, pp. 46:1–46:38, 2017.

[39]
R. Cavallo and M. Pittarelli, “The theory of probabilistic databases,” in VLDB'87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England (P. M. Stocker, W. Kent, and P. Hammersley, eds.), pp. 71–81, Morgan Kaufmann, 1987.

[40]
M. S. Roulston, “Estimating the errors on measured entropy and mutual information,” Physica D: Nonlinear Phenomena, vol. 125, no. 3, pp. 285–294, 1999.

[41]
L. A. Goodman and W. H. Kruskal, “Measures of association for cross classifications,” Journal of the American Statistical Association, vol. 49, no. 268, pp. 732–764, 1954.

[42]
J. Birnick, T. Bläsius, T. Friedrich, F. Naumann, T. Papenbrock, and M. Schirneck, “Hitting set enumeration with partial information for unique column combination discovery,” Proc. VLDB Endow., vol. 13, no. 11, pp. 2270–2283, 2020.

[43]
F. Chiang and R. J. Miller, “Discovering data quality rules,” Proc. VLDB Endow., vol. 1, no. 1, pp. 1166–1177, 2008.

[44]
M. Parciak, S. Weytjens, N. Hens, F. Neven, L. Peeters, and S. Vansummeren, “Artifacts related to "approximately measuring functional dependencies: a comparitive study".” Available at <https://github.com/MarcelPa/AFD_comparative_study>, 2022.

[45]
P. C. Arocena, B. Glavic, G. Mecca, R. J. Miller, P. Papotti, and D. Santoro, “Messing up with BART: error generation for evaluating data-cleaning algorithms,” Proc. VLDB Endow., vol. 9, no. 2, pp. 36–47, 2015.

§ DISCUSSION ON LOGICAL VS SHANNON ENTROPY

The notion of logical entropy arises in mathematical philosophy [20], where it is observed to provide a theory of information based on logic. Importantly, formulas and equalities concerning logical entropy can be converted into corresponding formulas and equalities concerning Shannon entropy by the so-called dit-bit transform (see  [20]).
Logical and Shannon entropy are hence highly similar, but measure different things: logical entropy measures the probability of two random tuples to be distinguished, while Shannon entropy measures average  uncertainty.

§ PROOF OF WELL-DEFINEDNESS OF $\MU$

In this section we prove the following result mentioned in Footnote footnote:muwelldef.

If $\expect_R[\pdep(\varphi,R)] = 1$ then $R \models \varphi$.

Assume that $\expect_R[\pdep(\varphi,R)] = 1$. Let $R_1, \dots, R_n$ be an enumeration of all permuations of $R$. Then

\begin{align*}
\expect_R[\pdep(\varphi,R)]  = \frac{\sum_{i=1}^N \pdep(\varphi,R_i)}{N}
\end{align*}

Hence, $\expect_R[\pdep(\varphi,R)] = 1$ iff $\sum_{i=1}^N \pdep(\varphi,R_i) = N$. Because the range of $\pdep$ is the interval $[0,1]$ this sum can equal $N$ if, and only if, $\pdep(\varphi,R_i) = 1$ for every $R_i$, including $R$ itself. Suppose, for the purpose of contradiction, that $R \not \models \varphi$. Then, the value of $\pdep$ is given by the formula in Section <ref>, i.e.

\begin{align*}
\pdep(\X \to \Y, R) & = \sum_{\x} \prob_R(\x) [1 - \pdep(\Y \mid \x, R) \\
& = 1 - \expect_{\x}[\logentrop_R(\Y \mid \x)]
\end{align*}

where the second equality is due to Lemma <ref>. Since $\pdep(\X \to \Y, R) = 1$, this means in particular that $\expect_{\x}[\logentrop_R(\Y \mid \x)] = 0$, which by reasoning similar as above can only happen if $\logentrop_R(\Y \mid \x) = 0$ for every $\x \in \pi_{\X}(R)$. This means, that for every  $\x \in \pi_{\X}(R)$, the probability to draw two distinct $\Y$-tuples in $\pi_{\Y}(\sigma_{\X=\x}(R))$ is zero. But that can only happen if there is only one $\Y$-value $\pi_{\Y}(\sigma_{\X=\x}(R))$, in which case $R \models \varphi$ and we obtain our desired contradiction.

§ FORMAL COMPARISON OF THE AFD MEASURES

Overview of similarities between measures and measures in / .

$g_1$                                                                                $= 1 - \logentrop_R(\Y \mid \X)$
$ 1 - \entrop_R(\Y\mid \X)$

$\pdep$                                                                                $= \sum_{\x} \prob_R(\x) \left(1 - \logentrop_R(\Y \mid \x)\right)$
$g_3$                                                                                = $\sum_{\x} \prob_R(\x) \max_{\y} \prob_R(\y \mid \x)$

$= 1 - \sum_{\x} \prob_R(\x) \logentrop_R(\Y \mid \x)$
$g_2$                                                                                $= 1 - \sum_{\w \in G_2(\X \to \Y, R)} \prob_R(\w)$

$\tau$                                                                                $= 1 - \frac{\expect_{\x}[\logentrop_R(\Y \mid \x)]}{\logentrop_R(\Y)}$
$\FI$                                                                                $= 1 - \frac{\entrop_R(\Y \mid \X)}{\entrop_R(\Y)}$

$= 1 - \frac{\expect_{\x}[\entrop_R(\Y \mid \x)]}{\entrop_R(\Y)}$

$ = \frac{\pdep(\varphi, R)-\expect_R[\pdep(\varphi, R)]}{1-\expect_R[\pdep(\varphi, R)]}$
$\RFI$                                                                                $= \FI(\varphi, R) - \expect_R[\FI(\varphi,R)]$

This section presents a formal comparison of the measures introduced in Section <ref>,
which motivates the definition of the new measures and .

Among the measures introduced in Section <ref>, we discern the following three classes (see also the second row in Table <ref>):

* The class of measures that have a notion of “violation” and quantify the number of violations, consisting of $\rho, g_2, g_3$, and $g'_3$. We denote this class by $\simple$.

* The class of measures based on Shannon entropy, consisting of $\FI, \RFIplus$, and $\SFI$. We denote this class by $\shannon$.

* The class of measures based on logical entropy, consisting of $g_1,g'_1, \pdep, \tau$, and $\muplus$ and denoted by $\logical$.

We discuss the similarities in the design of measures and those in the and class
by means of Table <ref>, which clusters
measures into groups that we find similar and where we rewrite measures
into equivalent form when this is necessary to stress the similarities.
We prove in the full version of this paper [44]:

The alternate formulas given in
Table <ref> are equivalent to their definition given in
Sections <ref>–<ref>.

The proof may be found in the Appendix <ref>.

c1 We have already observed that $g_1$ is a measure based on
logical entropy, $g_1(\X \to \Y,R) = 1 - \logentrop_R(\Y \mid \X)$.
We find it interesting to observe that Giannella and
Robertson [12] considered an axiomatisation of
error measures, and showed that Shannon entropy $\entrop_R(\Y \mid \X)$ is,
up to a multiplicative constant, the unique unnormalized error measure that
satisfies their axioms. As such, we may view $1 - \entrop_R(\Y \mid \X)$ as the
Shannon equivalent of $g_1$. Unfortunately, however, $1 - \entrop_R(\Y \mid \X)$
is not an measure: the value of $\entrop_R(\Y \mid \X)$ is unbounded and
$1 - \entrop_R(\Y \mid \X)$ hence has range $[-\infty, 1]$ instead of $[0,1]$.
Giannella and Robertson [12] therefore turn
$1 - \entrop_R(\Y \mid \X)$ into an measure by moving to $\FI$, which
normalizes $\entrop_R(\Y \mid \X)$ w.r.t. $\entrop_R(\Y)$. This is no longer the
conceptual Shannon counterpart of $g_1$. However, as further discussed below, it is nevertheless natural to ask what the conceptual Shannon counterpart of $g_1$ is and how it behaves. We thus propose the following Shannon variant $\SHANNONGONE$ of $g_1$, obtained by limiting $1  - \entrop_R(\Y\mid\X)$ to be positive:

\[ \SHANNONGONE(\X \to \Y, R) := \max(1 - \entrop_R(\Y \mid \X), 0). \]

c2 We have already observed in Section <ref> that we may view $\pdep$ as a generalisation of $g_2$. We may also view it as an alternate to $g_3$. Indeed, $\pdep$ equals the expected value of $1 - \logentrop_R(\Y \mid \x)$—expressing the probability of $\x$ not participating in a violating pair—while $g_3$ equals the expected value of $\max_{\y} \prob_R(\y \mid \x)$—expressing the largest subgroup of non-violating tuples in $\pi_{\Y}\sigma_{\X=\x}(R)$, where in both cases expectation is taken over all $\x$.

c3 As shown by the rewritten formulas in line 3 of Table <ref>, $\FI$ is simply the Shannon entropy-based version of $\tau$.

The similarity between $\tau$ and $\FI$ extends to a conceptual similarity between $\mu$ and $\RFI$: $\mu$ corrects for the  bias of $\tau$ under random permutations while $\RFI$ corrects for the bias of $\FI$ under random permutations. Despite this conceptual similarity, note that the corrections are done differently: $\mu$ corrects by taking the normalized difference between $\pdep$ and $\expect_R[\pdep]$ while $\RFI$ corrects by taking the absolute difference between $\FI$ and $\expect_R[\FI]$.  As such $\RFI$ is not a normalized measure. Since it is natural to ask what the normalized variant of $\RFI$ is and how it behaves, we define

\[ \RFInorm(\varphi, R) := \max\left(\frac{\FI(\varphi,R) - \expect_R[\FI(\varphi,R)]}{1 -\expect_R[\FI(\varphi,R)]}, 0\right). \]

We attribute both new measures $\SHANNONGONE$ and $\RFInorm$ to $\shannon$,
and compare their behavior to that of the other measures in the following sections.

§ PROOFS OF EQUIVALENCE

In this section we prove that the alternate measure formulations shown in
Table <ref> are correct, hence proving
Theorem <ref>. The theorem is proved as a sequence of lemmas. Throughout this section, assume that $R \not \models \X \to \Y$.

$g_3(\X \to \Y, R) = \sum_{\x} \prob_R(\x) \max_{\y} \prob_R(\y \mid \x)$.

We reason as follows.

\begin{align*}
g_3(\X \to \Y, R)
& = \max_{R' \in G_3(\X \to \Y, R)} \frac{|R'|}{|R|}          \\
& = \max_{R' \in G_3(\X \to \Y,R)} \sum_{\w \in R'} \prob_R(\w) \\
& = \sum_{\x} \max_{\y} \prob_R(\x\y)                        \\
& = \sum_{\x} \prob_R(\x) \max_{\y} \prob_R(\y \mid \x).
\end{align*}

Here, the first equality is the definition of $g_3$.  The second equality follows by definition of $\prob_R$. The third equality follows from the following observation: a relation $R'\subseteq R$ can only be maximal if $R'(\w)=R(\w)$ whenever $R'(\w)>0$ for all $\w\in R$. That is, either we keep all occurrences of $\w$ or we remove all of them.  So, maximizing $\sum_{\w \in R'} \prob_R(\w)$ corresponds to, for every $\x$, keeping that $\y$ that maximizes $\prob_R(\x\y)$. Thereby, effectively removing all other tuples $\x\y'$ with $\y\neq\y'$. The last equality then follows from the definition of conditional probability.

$\pdep(\Y \mid \x, R) = 1 - \logentrop_R(\Y \mid \x)$ and therefore

\begin{align*}
\pdep(\X \to \Y, R) & = \sum_{\x} \prob_R(\x) (1 - \logentrop_R(\Y \mid x)) \\
& = 1 - \sum_{\x} \prob_R(\x) \logentrop_R(\Y \mid \x)\\
& = 1 - \expect_{\x}[\logentrop_R(\Y \mid \x)]
\end{align*}

We first observe

\begin{align*}
\pdep(\Y \mid \x, R)
& = \sum_{\y} \prob_R(\y \mid \x)^2           \\
& = 1 - (1 - \sum_{\y} \prob_R(\y \mid \x)^2) \\
& = 1 - \logentrop_R(Y \mid \x).
\end{align*}

\begin{align*}
\pdep(\X \to \Y, R) & = \sum_{\x} \prob_R(\x) \pdep(\Y \mid \x, R)                            \\
& = \sum_{\x} \prob_R(\x) (1 - \logentrop_R(\Y \mid x))                   \\
& = \sum_{\x} \prob_R(\x) - \sum_{\x} \prob_R(\x)\logentrop_R(\Y \mid \x) \\
& = 1 - \sum_{\x} \prob_R(\x)\logentrop_R(\Y \mid \x). \qedhere
\end{align*}

$\tau(X \to Y, R) = 1 - \frac{\expect_{\x}[\logentrop_R(\Y \mid \x)]}{\logentrop_R(\Y)}$

We reason as follows.

\begin{align*}
\tau(X\to Y , R) & = \frac{\pdep(\X \to \Y, R)-\pdep(\Y, R)}{1-\pdep(\Y, R)}                                                 \\
& = \frac{(1 - \expect_{\x}[\logentrop_R(\Y \mid \x)]) - (1 - \logentrop_R(\Y))}{1 - (1 - \logentrop_R(\Y))} \\
& = \frac{\logentrop_R(\Y) - \expect_{\x}[\logentrop_R(\Y \mid \x)]}{\logentrop_R(\Y)}                      \\
& = 1 - \frac{\expect_{\x}[\logentrop_R(\Y \mid \x)]}{\logentrop_R(\Y)} \qedhere
\end{align*}

Here, the second equality is by Lemma <ref> and the fact that $\pdep(\Y, R) = 1 - \logentrop_R(\Y)$ by definition.

Relating this to logical entropy we observe

$ \mu(\X \to \Y,R) = 1 - \frac{\expect_{\x}[\logentrop_R(\Y\mid\x)]}{\logentrop_R(\Y)} \frac{|R|-1}{|R|-|\dom(\X,R)|}$

We reason as follows.

\begin{align*}
\mu(&\X \to \Y, R) \\
& :=\frac{\pdep(\X \to \Y, R)-\expect_R[\pdep(\X \to \Y, R)]}{1-\expect_R[\pdep(\X \to \Y, R)]} \\
& =1-\frac{1-\pdep(\X \to \Y, R)}{1-\pdep(\Y, R)} \frac{|R|-1}{|R|-|\dom(\X,R)|} \\
& = 1 - \frac{1- (1 - \expect_{\x}[\logentrop_R(\Y \mid \x)])}{1-(1-\logentrop_R(\Y))} \frac{|R|-1}{|R|-|\dom(\X,R)|} \\
& = 1 - \frac{\expect_{\x}[\logentrop_R(\Y \mid \x)]}{\logentrop_R(\Y)} \frac{|R|-1}{|R|-|\dom(\X,R)|}.\qedhere
\end{align*}

\[ \FI(\X \to \Y, R) = 1 - \frac{\entrop_R(\Y \mid \X)}{\entrop_R(\Y)}.\]

To show the claimed equality, we reason as follows. Recall that we implicitly
assume throughout the paper that $R$ is non-empty. By definition

\[ \FI(\X \to \Y, R) :=
\begin{cases}
1                                                           & \text{ if } |\dom_R(\Y)| = 1, \\
\frac{\entrop_R(\Y) - \entrop_R(\Y \mid \X)}{\entrop_R(\Y)} & \text{otherwise.}
\end{cases}
\]

We now make a case analysis.

* If $|\dom_R(\Y)| = 1$ then $\entrop_R(\Y) = 0$. Moreover, if
$\entrop_R(\Y) = 0$, also $\entrop_R(\Y \mid \X) = 0$. As such,

\[ 1 - \frac{\entrop_R(\Y \mid \X)}{\entrop_R(\X)} = 1- \frac{0}{0} = 1 - 0 = 1 = \FI(\X \to \Y, R),\]

as desired.

* If $|\dom_R(\Y)| > 1$ then

\begin{align*}
\FI(\X \to \Y, R)
& = \frac{\entrop_R(Y) - \entrop_R(\Y \mid \X)}{\entrop_R(\Y)} \\
& = 1 - \frac{\entrop_R(\Y\mid \X)}{\entrop(\Y)} \qedhere
\end{align*}

§ ADDITIONAL INFORMATION ON THE SENSITIVITY ANALYSIS

every axis plot/.append style=thick,
every axis y label/.style=
at=(ticklabel cs:0.5),rotate=90,anchor=near ticklabel,
every axis x label/.style=
at=(ticklabel cs:0.5),anchor=near ticklabel,
ymin=-0.05, ymax=1.05,
legend columns=-1,
legend style=draw=none,

legend to name=appendix_syn_noise_simple_legend,
xlabel=Error rate,
ylabel=Measure value,
xmin=-0.0, xmax=0.09,
[plotColor1] table [x=error,y=fd] plotdata/syn_error_copy_rho.dat;
[plotColor2] table [x=error,y=fd] plotdata/syn_error_copy_g2.dat;
[plotColor3] table [x=error,y=fd] plotdata/syn_error_copy_g3.dat;
[plotColor4] table [x=error,y=fd] plotdata/syn_error_copy_g3_prime.dat;
[plotColor1,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_rho.dat;
[plotColor2,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_g2.dat;
[plotColor3,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_g3.dat;
[plotColor4,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_g3_prime.dat;

legend to name=appendix_syn_keylike_simple_legend,
xlabel=LHS Uniqueness,
ylabel=Measure value,
xmin=0.1, xmax=0.9,
[plotColor1] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_rho.dat;
[plotColor2] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_g2.dat;
[plotColor3] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_g3.dat;
[plotColor4] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_g3_prime.dat;
[plotColor1,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_rho.dat;
[plotColor2,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_g2.dat;
[plotColor3,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_g3.dat;
[plotColor4,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_g3_prime.dat;

legend to name=appendix_syn_rhsskew_simple_legend,
xlabel=RHS Skew,
ylabel=Measure value,
xmin=0.0, xmax=9.0,
[plotColor1] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_rho.dat;
[plotColor2] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_g2.dat;
[plotColor3] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_g3.dat;
[plotColor4] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_g3_prime.dat;
[plotColor1,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_rho.dat;
[plotColor2,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_g2.dat;
[plotColor3,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_g3.dat;
[plotColor4,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_g3_prime.dat;

legend to name=appendix_syn_noise_shannon_legend,
xlabel=Error rate,
xmin=-0.0, xmax=0.09,
[plotColor1] table [x=error,y=fd] plotdata/syn_error_copy_shannon_g1_prime.dat;
[plotColor2] table [x=error,y=fd] plotdata/syn_error_copy_fraction_of_information.dat;
[plotColor3] table [x=error,y=fd] plotdata/syn_error_copy_reliable_fraction_of_information_prime.dat;
[plotColor4] table [x=error,y=fd] plotdata/syn_error_copy_fraction_of_information_prime.dat;
[plotColor5] table [x=error,y=fd] plotdata/syn_error_copy_smoothed_fraction_of_information.dat;
[plotColor1,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_shannon_g1_prime.dat;
[plotColor2,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_fraction_of_information.dat;
[plotColor3,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_reliable_fraction_of_information_prime.dat;
[plotColor4,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_fraction_of_information_prime.dat;
[plotColor5,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_smoothed_fraction_of_information.dat;

legend to name=appendix_syn_keylike_shannon_legend,
xlabel=LHS Uniqueness,
xmin=0.1, xmax=0.9,
[plotColor1] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_shannon_g1_prime.dat;
[plotColor2] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_fraction_of_information.dat;
[plotColor3] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_reliable_fraction_of_information_prime.dat;
[plotColor4] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_fraction_of_information_prime.dat;
[plotColor5] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_smoothed_fraction_of_information.dat;
[plotColor1,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_shannon_g1_prime.dat;
[plotColor2,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_fraction_of_information.dat;
[plotColor3,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_reliable_fraction_of_information_prime.dat;
[plotColor4,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_fraction_of_information_prime.dat;
[plotColor5,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_smoothed_fraction_of_information.dat;

legend to name=appendix_syn_rhsskew_shannon_legend,
xlabel=RHS Skew,
xmin=0.0, xmax=9.0,
[plotColor1] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_shannon_g1_prime.dat;
[plotColor2] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_fraction_of_information.dat;
[plotColor3] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_reliable_fraction_of_information_prime.dat;
[plotColor4] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_fraction_of_information_prime.dat;
[plotColor5] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_smoothed_fraction_of_information.dat;
[plotColor1,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_shannon_g1_prime.dat;
[plotColor2,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_fraction_of_information.dat;
[plotColor3,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_reliable_fraction_of_information_prime.dat;
[plotColor4,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_fraction_of_information_prime.dat;
[plotColor5,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_smoothed_fraction_of_information.dat;

legend to name=appendix_syn_noise_logical_legend,
xlabel=Error rate,
xmin=-0.0, xmax=0.09,

[plotColor1] table [x=error,y=fd] plotdata/syn_error_copy_g1_prime.dat;
[plotColor2] table [x=error,y=fd] plotdata/syn_error_copy_pdep.dat;
[plotColor3] table [x=error,y=fd] plotdata/syn_error_copy_tau.dat;
[plotColor4] table [x=error,y=fd] plotdata/syn_error_copy_mu_prime.dat;

[plotColor1,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_g1_prime.dat;
[plotColor2,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_pdep.dat;
[plotColor3,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_tau.dat;
[plotColor4,style=dashed] table [x=error,y=random] plotdata/syn_error_copy_mu_prime.dat;

legend to name=appendix_syn_keylike_logical_legend,
xlabel=LHS Uniqueness,
xmin=0.1, xmax=0.9,

[plotColor1] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_g1_prime.dat;
[plotColor2] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_pdep.dat;
[plotColor3] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_tau.dat;
[plotColor4] table [x=lhs_uniq,y=fd] plotdata/syn_keylike_mu_prime.dat;

[plotColor1,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_g1_prime.dat;
[plotColor2,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_pdep.dat;
[plotColor3,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_tau.dat;
[plotColor4,style=dashed] table [x=lhs_uniq,y=random] plotdata/syn_keylike_mu_prime.dat;

legend to name=appendix_syn_rhsskew_logical_legend,
xlabel=RHS Skew,
xmin=0.0, xmax=9.0,

[plotColor1] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_g1_prime.dat;
[plotColor2] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_pdep.dat;
[plotColor3] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_tau.dat;
[plotColor4] table [x=rhs_skew,y=fd] plotdata/syn_rhsskew_mu_prime.dat;

[plotColor1,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_g1_prime.dat;
[plotColor2,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_pdep.dat;
[plotColor3,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_tau.dat;
[plotColor4,style=dashed] table [x=rhs_skew,y=random] plotdata/syn_rhsskew_mu_prime.dat;

Average measures values of the three experiments on data. The top row shows $\synnoisefd$ (solid lines) and $\synnoisenonfd$ (dashed lines) for different error levels. Middle row shows $\synuniquefd$ (solid lines) and $\synuniquenonfd$ (dashed lines) for different levels. Bottom row shows $\synskewfd$ (solid lines) and $\synskewnonfd$ (dashed lines) for different levels. Some of the lines are hidden behind each other. The $\synnoisenonfd$ lines of $\SHANNONGONE$ and $\RFIplus$ are behind $\RFInorm$. The $\synnoisefd$ line of $\pdep$ is behind $\tau$. The $\synnoisenonfd$ line of $g_1,g'_1$ is behind its own $\synnoisefd$ line. The $\synuniquenonfd$ line of $\RFIplus$ is behind $\RFInorm$. The $\synuniquefd$ line of $\pdep$ is behind $\tau$. The $\synskewnonfd$ lines of $\RFIplus$ and $\RFInorm$ are behind $\SFI$. The $\synskewnonfd$ line of $g_1,g'_1$ is behind the $\synskewfd$ line of itself.

We provide more detail on the material presented in Section <ref>. Specifically, for each synthetic benchmark $\benchmark$ Figure <ref> shows separate plots of the average measure values on $\benchmarkfd$ (in solid lines) and $\benchmarknonfd$ (in dashed lines).
Values for $g_1$ and $g'_1$
are grouped together as their average measure values are the same on both
$\benchmarkfd$ and $\benchmarknonfd$.  From Figure <ref> we make the following additional observations w.r.t. and .

For $\rho$, $g_2$, $\SHANNONGONE$, $g_3$, $\FI$, $\pdep$, and $\tau$ the average measure values on $\synuniquenonfd$ increase,
eventually approaching the measure values on $\synuniquefd$. For $\RFIplus$ and $\SFI$, by contrast, the average measure values over $\synuniquefd$ decrease towards zero for increasing , eventually reaching the value on $\synuniquenonfd$. Note that this decrease is already observable for  small values.

This means that all mentioned measures
are biased w.r.t. (either by inflating the scores of non-FDs or deflating the scores of FDs).

The distinguishing power of all measures, as well as $\SHANNONGONE$, and
$\pdep$ drops when increases. Indeed, over $\synskewfd$ the average
measure values remains relatively constant as increases, while the
average measure values increases and approaches the values over $\synskewfd$.
These measures are thus biased w.r.t. : their score for $\X\to\Y$
increases solely on the basis of $\Y$ and independent of $\X$ even if relations
are generated by a process that sampled $\X$ and $\Y$ independently at random.
We observe that the measures (save $\SHANNONGONE$), $\tau$, and
$\muplus$ correct for this behavior. Furthermore, $\FI$ and $\tau$ slightly
decrease at higher levels of .

§ ADDITIONAL INFORMATION ON THE EVALUATION ON REAL-WORLD DATA

We provide more detail on the material presented in Section <ref>.

*Precision-Recall Curves.

The precision-recall curves shown in Figure <ref> supplement our statements based on the area under the curve values. They constitute the graphical counterpart for Table <ref>. It is clear that for each class one of the measures stands out; $g'_3$ for , $\RFInorm$ for and $\muplus$ for .

every axis plot/.append style=thick,
every axis y label/.style=
at=(ticklabel cs:0.5),rotate=90,anchor=near ticklabel,
every axis x label/.style=
at=(ticklabel cs:0.5),anchor=near ticklabel,
xmin=-0.05, xmax=1.05,
ymin=-0.05, ymax=1.05,
legend columns=-1,
legend style=draw=none,

legend to name=rwd_prcurves_simple_legend,
[plotColor1] table [x=recall,y=precision] plotdata/rwd_rho.dat;
[plotColor2] table [x=recall,y=precision] plotdata/rwd_g2.dat;
[plotColor3] table [x=recall,y=precision] plotdata/rwd_g3.dat;
[plotColor4] table [x=recall,y=precision] plotdata/rwd_g3_prime.dat;

legend to name=rwd_prcurves_shannon_legend,
[plotColor1] table [x=recall,y=precision] plotdata/rwd_shannon_g1_prime.dat;
[plotColor2] table [x=recall,y=precision] plotdata/rwd_fraction_of_information.dat;
[plotColor3] table [x=recall,y=precision] plotdata/rwd_reliable_fraction_of_information_prime.dat;
[plotColor4] table [x=recall,y=precision] plotdata/rwd_fraction_of_information_prime.dat;
[plotColor5] table [x=recall,y=precision] plotdata/rwd_smoothed_fraction_of_information.dat;

legend to name=rwd_prcurves_logical_legend,
[plotColor1] table [x=recall,y=precision] plotdata/rwd_g1.dat;
[plotColor2] table [x=recall,y=precision] plotdata/rwd_g1_prime.dat;
[plotColor3] table [x=recall,y=precision] plotdata/rwd_pdep.dat;
[plotColor4] table [x=recall,y=precision] plotdata/rwd_tau.dat;
[plotColor5] table [x=recall,y=precision] plotdata/rwd_mu_prime.dat;

Precision-Recall curves over grouped per measure class: , , and .

*Measure Runtimes. Table <ref> shows the runtimes of each measure in more detail. We observe that $\rho$ is the fastest measure with $110$ seconds to calculate a value for all candidate . In general, the measures of the class are faster compared to the others. Measures of the class take on average roughly $21$ seconds longer to compute values for all candidate . In the class, the differences are much larger. While $\SHANNONGONE$ and $\FI$ achive runtimes comparable to the measures from the class, $\RFIplus$, $\RFInorm$ and $\SFI$ were not able to calculate values for all candidates. In that, $\SFI$ is able to calculate a value for $1430$ (roughly $90\%$) candidates while $\RFIplus$ and $\RFInorm$ finish only $250$ (roughly $15\%$) candidates.

$\RFIplus$, $\RFInorm$ and $\SFI$ are significantly slower than the other measures. The table shows the runtimes, capped at 24 hours, and the number of measures candidates within the runtime.

Next we consider the whole of and disregard the measures $\RFIplus$ and $\RFInorm$ for which the scores of not all candidate could be computed.
A comparison between the AUC values of and in Table <ref> show only minor differences. $\SFI$ shows the largest differences ($-0.036$), followed by $g_1$ and $g'_1$ ($-0.026$ and $-0.027$ respectively) and $\FI$ with a difference of $-0.019$. All other measures show differences below $-0.01$. We also note that all differences are negative, which means that each measure achieved better results when the  values of $\RFIplus$ and $\RFInorm$ are left out. We do not observe any notable changes for any of the tables of .

The differences between and without $\RFIplus$ and $\RFInorm$ are minimal. The table shows the same overview as Table <ref> for . $\RFIplus$ and $\RFInorm$ show the same values, as the candidates do not change compared to .

best (pct)

[head to column names,late after line=

*RWD without .
To get more insight into the candidate that could not be calculated by $\RFIplus$ and $\RFInorm$, we investigated the measure results for this exact subset: $\rwd \setminus \rwdminus$. This subset contains $405$ candidates that are exclusively non-. For this reason, we cannot assess precision, recall or other metrics. However, we can derive some intuition about how difficult those candidates are by investigating the measure values of the other measures. The upper part of Table <ref> shows an overview of summary statistics of $\rwd \setminus \rwdminus$.

We observe that both average and median of most measure values are low. Still, it is noteworthy that judging by very high max values there seems to be a small subset of candidate that could lead to changes the AUCs of $\RFIplus$ and $\RFInorm$. Ultimately, the only way to confirm that suspicion would be to use $\RFIplus$ and $\RFInorm$ to calculate values for all candidates of $\rwd \setminus \rwdminus$.

In addition, we investigated the properties of $\rwd \setminus \rwdminus$, especially with regard to the properties we used in Section <ref>. The lower part of Table <ref> shows an overview of summary statistics of the number of tuples, and . Both and do not show unexpected values. is rather low, is around $1.0$, both of which match properties of in general. The number of tuples is rather large, indicating that having a lot of values increases the runtimes of $\RFIplus$ and $\RFInorm$.

The candidate that $\RFIplus$ and $\RFInorm$ could not calculate have the potential to decrease their performance. The upper part shows summary statistics of all measures for $\rwd \setminus \rwdminus$. The lower part shows summary statistics of properties of the candidates, indicating that a high tuple count increases the runtime of $\RFIplus$ and $\RFInorm$.

mean     std     min     median     max

[head to column names,late after line=
[head to column names,late after line=

§ EVALUATION ON WITH EXTRA ERRORS

To study the measures' sensitivity to different kinds and different levels of
errors on real world data, we created the benchmark . We obtain
by passing the relations $R \in \rwd$ through a controlled error channel such that, denoting by $R'$ the obtained relation, some in
$\perfectFD(R)$ do not hold anymore in $R'$ and hence become part of
$\designAFD(R')$. Existing AFDs are always maintained, i.e.,
$\designAFD(R) \subseteq \designAFD(R')$.

We actually have multiple error channels, which are parameterized by an error
level $\eta\in [0,1]$ and an error type. When passing $R$ through the channel we
consider all $\X \to \Y \in \perfectFD(R)$ and modify $k=\lfloor \eta|R|\rfloor$
$\Y$-values. To avoid interference, we select at most one $\X\to \Y$ for
every unique $\Y$ per relation, ensuring that $\Y$ does not appear in $\designAFD(R)$, and that no $\Y\to \Z$ has previously been selected.

The procedure to modify the $\Y$ values
is determined by the chosen type of data error for which we consider three categories inspired by Arocena et al. [45]: error, and value.

For a chosen tuple $\w \in R$, only $\restr{\w}{\Y}$ is changed, where the change depends on the data error type:

* : Randomly pick any $\tilde{\w} \in R$ with $\tilde{\w}|_{\Y} \neq \w|_{\Y}$ and
make $\tilde{\w}|_{\Y}$ the new value for $\w|_{\Y}$.

* : To every $\y\in\dom_R(\Y)$, we associate three new values representing three common typos. From these, one is chosen each time at random as the new value for ${\w}|_{\Y}$.

* : ${\w}|_{\y}$ is assigned a unique newly generated value.

We point out that does not introduce any new values and keeps $\dom_{R}(\Y)$ stable, while (resp., ) introduces a number of new values independent of (resp., dependent on) the error level. $\X$ is not modified, and therefore $\prob_{R'}(\X) = \prob_{R}(\X)$.

To ensure that increasing error levels do not accidentally reduce errors, we
ensure that, for each $\x\colon \X$ we pick at most $\lfloor N_{\x}/2\rfloor$
tuples $\w$ with $\w|_{\X}=\x$ to modify, where $N_{\X}$ is the number of times
that $\x$ occurs in $\pi_{\X}(R)$. $\perfectFD$s for which this cannot be
guaranteed are omitted. The number of new that can be constructed
therefore depends on the error level.

We consider four error levels: 1%, 2%, 5% and 10%. For each type of data error $t$ and each error level $\eta$, we obtain a new benchmark $\nrwd[t,\eta]$. Consequently, we generate 12 tables per table $R$ for which $|\perfectFD(R)|>0$ (so, tables  and  are excluded). Overall the number of increases from
in to in
$\nrwd[\copykind, 1\%]$. That number is the same for the other error types but can drop a little for higher noise levels as explained above. Similar to $\rwdminus$, we retain only candidates where each measure calculates a value in a reasonable amount of time.
A complete overview of the number of additional per relation and per error level is given in [44].
Per combination of parameters, the ground truth then consists of the thus constructed together with the from $R$.

$\muplus$ and $\RFInorm$ score best $\nrwd$ with one exception. The table shows the AUCs for each noise type and noise level of , the dataset derived from by introducing errors. in the table header, the sizes $n$ of each of the datasets is shown. For comparison, the first column repeats the AUCs for .

$\copykind,1$     $\copykind,2$     $\copykind,5$     $\copykind,10$     $\boguskind,1$     $\boguskind,2$     $\boguskind,5$     $\boguskind,10$     $\typokind,1$     $\typokind,2$     $\typokind,5$     $\typokind,10$

$n$     1229          1204              1206              1218              1143               1130               1127               1111               992                 1188              1194              1189              915

[late after line=

On average, $\muplus$ and $\RFInorm$ score most reliably over . The table shows the percentages per error type where a measure has the lowest rank to reach a recall of $1.0$.

[late after line=

Table <ref> lists AUC scores over per error type and for different error levels.

We observe that $\mu'$ has the highest AUC score in 6 out of 12 cases, followed by $\RFInorm$ that scores highest in 4 our of 12 cases. Both $\muplus$ and $\RFInorm$ are the top-two scoring measures consistently. The only exception is $\nrwd[\typokind,10\%]$ where $\RFIplus$ is the highest scoring measure. We also observe that $\muplus$ scores highest on all $\nrwd$ datasets with $\eta=2\%,5\%$ while $\RFInorm$ scores highest on all $\nrwd$ with $\eta=1\%$. There is no clear observation for $\eta=10\%$. Regarding the error types, we observe that in general the AUCs of are higher on the same error levels. For $\nrwd[\boguskind,10\%]$ $g_3$,$\SHANNONGONE$ and $\FI$ are exceptions. We observe a similar, yet less pronounced, trend for compared to , which does not hold for $\eta=10\%$.
We remark that for some measures the AUC score on $\nrwd$ is larger at the 1% error level than for . This is not completely unexpected as the ground truth for both is different. A suprising result is presented for $\SHANNONGONE$, where the AUC of each $\nrwd$ dataset is higher than for .

We do see that, as expected, the AUC score for each of the measures deteriorates at increasing error levels to an absolute low at error level 10%. The exception is $\RFI'$ whose performance increases at higher error levels for error types but not for the other error types. When error types and error levels are unknown but expected to be small, $\mu'$ therefore remains the best choice of -measure. Furthermore, it is evident from Table <ref> that -measures are not very effective when error levels are greater than 5%.

Within $g'_3$ remains the best measure.
Within we see $\RFInorm$ scoring best while $\SFI$ performs worst for most datasets. The measures $\SHANNONGONE$, $\FI$ and $\RFIplus$ show very similar scores.
Within we observe that $\tau$ is usually an improvement over $\pdep$, and  $\muplus$ is an improvement over $\tau$. Further, $g_1$ and $g'_1$ perform consistently worse than any other measure in .

*Rank at max recall.
We show in
Table <ref> a qualitative comparison between measures by listing, for each measure $f$ and error type $t$, its winning number, which is defined as follows. Consider a particular $(\text{relation}, t, \eta)$ combination in $\nrwd$. A measure  $f$ wins this triple if its $\rankAtMaxRecall$ is minimal among all measures on this triple. The winning number of $f$ for error type $t$  is then the number of times $f$ wins, taken over all triples of type $t$.
Here, we see again that both $\RFInorm$ and $\muplus$ score very well. Across all error types, $\muplus$ is the only measure that is in included in the top two values. It scores best on , where its rank at max recall is minimal for $75\%$ of all relations. $\tau$ is the runner-up with $53.1\%$ of the relations. In , $\RFInorm$ achives a minimal rank at max recall for $50.0\%$ of the relations. $g_3$, $g'_3$ and $\muplus$ follow with $42.3\%$. For , $\RFInorm$ ranks candidates best on $58.1\%$ relations. $\muplus$ is behind that with $54.8\%$.