tcb@breakable

# Functional Dependencies with Predicates:
What Makes the $g_{3}$-error Easy to Compute?111Part of this work was done
while the first author was doing a postdoc at LIRIS.

Simon Vilmin  Université de Lorraine, CNRS, LORIA, F-54000, France  Pierre
Faure–Giovagnoli  Univ Lyon, INSA Lyon, CNRS, UCBL, LIRIS, UMR5205, France
Compagnie Nationale du Rhône, Lyon, France  Jean-Marc Petit  Univ Lyon, INSA
Lyon, CNRS, UCBL, LIRIS, UMR5205, France  Vasile-Marian Scuturici  Univ Lyon,
INSA Lyon, CNRS, UCBL, LIRIS, UMR5205, France

###### Abstract

The notion of functional dependencies (FDs) can be used by data scientists and
domain experts to confront background knowledge against data. To overcome the
classical, too restrictive, satisfaction of FDs, it is possible to replace
equality with more meaningful binary predicates, and use a coverage measure
such as the $g_{3}$-error to estimate the degree to which a FD matches the
data. It is known that the $g_{3}$-error can be computed in polynomial time if
equality is used, but unfortunately, the problem becomes NP-complete when
relying on more general predicates instead. However, there has been no
analysis of which class of predicates or which properties alter the complexity
of the problem, especially when going from equality to more general
predicates.

In this work, we provide such an analysis. We focus on the properties of
commonly used predicates such as equality, similarity relations, and partial
orders. These properties are: reflexivity, transitivity, symmetry, and
antisymmetry. We show that symmetry and transitivity together are sufficient
to guarantee that the $g_{3}$-error can be computed in polynomial time.
However, dropping either of them makes the problem NP-complete.

Keywords: functional dependencies, $g_{3}$-error, predicates

##  1 Introduction

Functional dependencies (FDs) are database constraints initially devoted to
database design [MR92]. Since then, they have been used for numerous tasks
ranging from data cleaning [BFG+07] to data mining [NC01]. However, when
dealing with real world data, FDs are also a simple yet powerful way to
syntactically express background knowledge coming from domain experts
[FGPS22]. More precisely, a FD $X\rightarrow A$ between a set of attributes
(or features) $X$ and another attribute $A$ depicts a _function_ of the form
$f(X)=A$. In this context, asserting the existence of a function which
determines $A$ from $X$ in a dataset amounts to testing the validity of
$X\rightarrow A$ in a relation, _i.e._ to checking that _every pair_ of tuples
that are _equal_ on $X$ are also _equal_ on $A$. Unfortunately, this semantics
of satisfaction suffers from two major drawbacks which makes it inadequate to
capture the complexity of real world data: (i) it must be checked on the whole
dataset, and (ii) it uses equality.

Drawback (i) does not take into account data quality issues such as outliers,
mismeasurements or mistakes, which should not impact the relevance of a FD in
the data. To tackle this problem, it is customary to estimate the partial
validity of a given FD with a _coverage_ measure, rather than its total
satisfaction. The most common of these measures is the $g_{3}$-error [CGF+09,
GKK+08, HKPT99, SCP13], introduced by Kivinen and Mannila [KM95]. It is the
minimum proportion of tuples to remove from a relation in order to satisfy a
given FD. As shown for instance by Huhtala et al. [HKPT99], the $g_{3}$-error
can be computed in polynomial time for a single (classical) FD.

As for drawback (ii), equality does not always witness efficiently the
closeness of two real-world values. It screens imprecisions and uncertainties
that are inherent to every observation. In order to handle closeness (or
difference) in a more appropriate way, numerous researches have replaced
equality by _binary predicates_ , as witnessed by recent surveys on relaxed
FDs [CDP15, SGHW20].

However, if predicates extend FDs in a powerful and meaningful way with
respect to real-world applications, they also make computations harder. In
fact, contrary to strict equality, computing the $g_{3}$-error with binary
predicates becomes NP-complete [FGPS22, SCP13]. In particular, it has been
proven for differential [Son10], matching [Fan08], metric [KSSV09],
neighborhood [BW01], and comparable dependencies [SCP13]. Still, there is no
detailed analysis of what makes the $g_{3}$-error hard to compute when
dropping equality for more flexible predicates. As a consequence, domain
experts are left without any insights on which predicates they can use in
order to estimate the validity of their background knowledge in their data
quickly and efficiently.

This last problem constitutes the motivation for our contribution. In this
work, we study the following question: _which properties of predicates make
the $g_{3}$-error easy to compute?_ To do so, we introduce binary predicates
on each attribute of a relation scheme. Binary predicates take two values as
input and return true or false depending on whether the values match a given
comparison criteria. Predicates are a convenient framework to study the impact
of common properties such as reflexivity, transitivity, symmetry, and
antisymmetry (the properties of equality) on the hardness of computing the
$g_{3}$-error. In this setting, we make the following contributions. First, we
show that dropping reflexivity and antisymmetry does not make the
$g_{3}$-error hard to compute. When removing transitivity, the problem becomes
NP-complete. This result is intuitive as transitivity plays a crucial role in
the computation of the $g_{3}$-error for dependencies based on
similarity/distance relations [CDP15, SGHW20]. Second, we focus on symmetry.
Symmetry has attracted less attention, despite its importance in partial
orders and order FDs [DH82, GH83, Ng01]. Even though symmetry seems to have
less impact than transitivity in the computation of the $g_{3}$-error, we show
that when it is removed the problem also becomes NP-complete. This result
holds in particular for ordered dependencies.

Paper Organization. In Section 2, we recall some preliminary definitions.
Section 3 is devoted to the usual $g_{3}$-error. In Section 4, we introduce
predicates, along with definitions for the relaxed satisfaction of a
functional dependency. Section 5 investigates the problem of computing the
$g_{3}$-error when equality is replaced by predicates on each attribute. In
Section 6 we relate our results with existing extensions of FDs. We conclude
in Section 7 with some remarks and open questions for further research.

##  2 Preliminaries

All the objects we consider are finite. We begin with some definitions on
graphs [Ber73] and ordered sets [DP02]. A _graph_ $G$ is a pair $(V,E)$ where
$V$ is a set of _vertices_ and $E$ is a collection of pairs of vertices called
_edges_. An edge of the form $(u,u)$ is called a _loop_. The graph $G$ is
_directed_ if edges are ordered pairs of elements. Unless otherwise stated, we
consider _loopless undirected_ graphs. Let $G=(V,E)$ be an undirected graph,
and let $V^{\prime}\subseteq V$. The graph
$G[V^{\prime}]=(V^{\prime},E^{\prime})$ with $E^{\prime}=\\{(u,v)\in
E\mid\\{u,v\\}\subseteq V^{\prime}\\}$ is the graph _induced_ by $V^{\prime}$
with respect to $G$. A _path_ in $G$ is a sequence $e_{1},\dots,e_{m}$ of
pairwise distinct edges such that $e_{i}$ and $e_{i+1}$ share a common vertex
for each $1\leq i<m$. The _length_ of a path is its number of edges. An
_independent set_ of $G$ is a subset $I$ of $V$ such that no two vertices in
$I$ are connected by an edge of $G$. An independent set is _maximal_ if it is
inclusion-wise maximal among all independent sets. It is _maximum_ if it is an
independent set of maximal cardinality. Dually, a _clique_ of $G$ is a subset
$K$ of $V$ such that every pair of distinct vertices in $K$ are connected by
an edge of $G$. A graph $G$ is a _co-graph_ if it has no induced subgraph
corresponding to a path of length 3 (called $P_{4}$). A _partially ordered
set_ or _poset_ is a pair $P=(V,\leq)$ where $V$ is a set and $\leq$ a
reflexive, transitive, and antisymmetric binary relation. The relation $\leq$
is called a _partial order_. If for every $x,y\in V$, $x\leq y$ or $y\leq x$
holds, $\leq$ is a _total order_. A poset $P$ is associated to a directed
graph $G(P)=(V,E)$ where $(u_{i},u_{j})\in E$ exactly when $u_{i}\neq u_{j}$
and $u_{i}\leq u_{j}$. An undirected graph $G=(V,E)$ is a _comparability
graph_ if its edges can be directed so that the resulting directed graph
corresponds to a poset.

We move to terminology from database theory [LL12]. We use capital first
letters of the alphabet ($A$, $B$, $C$, …) to denote attributes and capital
last letters (…, $X$, $Y$, $Z$) for attribute sets. Let $U$ be a universe of
attributes, and $R\subseteq U$ a relation scheme. Each attribute $A$ in $R$
takes value in a domain $\textsf{dom}(A)$. The domain of $R$ is
$\textsf{dom}(R)=\bigcup_{A\in R}\textsf{dom}(A)$. Sometimes, especially in
examples, we write a set as a concatenation of its elements (e.g. $AB$
corresponds to $\\{A,B\\}$). A _tuple_ over $R$ is a mapping $t\colon
R\to\textsf{dom}(R)$ such that $t(A)\in\textsf{dom}(A)$ for every $A\in R$.
The _projection_ of a tuple $t$ on a subset $X$ of $R$ is the restriction of
$t$ to $X$, written $t[X]$. We write $t[A]$ as a shortcut for $t[\\{A\\}]$. A
_relation_ $r$ over $R$ is a finite set of tuples over $R$. A _functional
dependency_ (FD) over $R$ is an expression $X\rightarrow A$ where
$X\cup\\{A\\}\subseteq R$. Given a relation $r$ over $R$, we say that $r$
_satisfies_ $X\rightarrow A$, denoted by $r\models X\rightarrow A$, if for
every pair of tuples $(t_{1},t_{2})$ of $r$, $t_{1}[X]=t_{2}[X]$ implies
$t_{1}[A]=t_{2}[A]$. In case when $r$ does not satisfy $X\rightarrow A$, we
write $r\not\models X\rightarrow A$.

##  3 The $g_{3}$-error

This section introduces the $g_{3}$-error, along with its connection with
independent sets in graphs through counterexamples and conflict-graphs
[Ber11].

Let $r$ be a relation over $R$ and $X\rightarrow A$ a functional dependency.
The _$g_{3}$ -error_ quantifies the degree to which $X\rightarrow A$ holds in
$r$. We write it as $g_{3}(r,X\rightarrow A)$. It was introduced by Kivinen
and Mannila [KM95], and it is frequently used to estimate the partial validity
of a FD in a dataset [CDP15, CGF+09, FGPS22, HKPT99]. It is the minimum
proportion of tuples to remove from $r$ to satisfy $X\rightarrow A$, or more
formally:

######  Definition 1.

Let $R$ be a relation scheme, $r$ a relation over $R$ and $X\rightarrow A$ a
functional dependency over $R$. The _$g_{3}$ -error_ of $X\rightarrow A$ with
respect to $r$, denoted by $g_{3}(r,X\rightarrow A)$ is defined as:

$g_{3}(r,X\rightarrow A)=1-\frac{{\textsf{max}}(\\{|s|\mid s\subseteq
r,s\models X\rightarrow A\\})}{|r|}$

In particular, if $r\models X\rightarrow A$, we have $g_{3}(r,X\rightarrow
A)=0$. We refer to the problem of computing $g_{3}(r,X\rightarrow A)$ as the
_error validation problem_ [CDP15, SCP13]. Its decision version reads as
follows:

Error Validation Problem (EVP) Input: |  A relation $r$ over a relation scheme $R$, a FD $X\rightarrow A$, $k\in\mathbb{R}$.
---|---
Output: |  yes if $g_{3}(r,X\rightarrow A)\leq k$, no otherwise.

It is known [CDP15, FGPS22] that there is a strong relationship between this
problem and the task of computing the size of a maximum independent set in a
graph:

Maximum Independent Set (MIS) Input: |  A graph $G=(V,E)$, $k\in\mathbb{N}$.
---|---
Output: |  yes if $G$ has a maximal independent set $I$ such that $|I|\geq k$, no otherwise.

To see the relationship between EVP and MIS, we need the notions of
_counterexample_ and _conflict-graph_ [Ber11, FGPS22]. A _counterexample_ to
$X\rightarrow A$ in $r$ is a pair of tuples $(t_{1},t_{2})$ such that
$t_{1}[X]=t_{2}[X]$ but $t_{1}[A]\neq t_{2}[A]$. The _conflict-graph_ of
$X\rightarrow A$ with respect to $r$ is the graph $\textsf{CG}(r,X\rightarrow
A)=(r,E)$ where a (possibly ordered) pair of tuples $(t_{1},t_{2})$ in $r$
belongs to $E$ when it is a counterexample to $X\rightarrow A$ in $r$. An
independent set of $\textsf{CG}(r,X\rightarrow A)$ is precisely a subrelation
of $r$ which satisfies $X\rightarrow A$. Therefore, computing
$g_{3}(r,X\rightarrow A)$ reduces to finding the size of a maximum independent
set in $\textsf{CG}(r,X\rightarrow A)$. More precisely, $g_{3}(r,X\rightarrow
A)=1-\frac{|I|}{|r|}$ where $I$ is a maximum independent set of
$\textsf{CG}(r,X\rightarrow A)$.

######  Example 1.

Consider the relation scheme $R=\\{A,B,C,D\\}$ with
$\textsf{dom}(R)=\mathbb{N}$. Let $r$ be the relation over $R$ on the left of
Figure 1. It satisfies $BC\rightarrow A$ but not $D\rightarrow A$. Indeed,
$(t_{1},t_{3})$ is a counterexample to $D\rightarrow A$. The conflict-graph
$\textsf{CG}(r,D\rightarrow A)$ is given on the right of Figure 1. For
example, $\\{t_{1},t_{2},t_{6}\\}$ is a maximum independent set of
$\textsf{CG}(r,D\rightarrow A)$ of maximal size. We obtain:

$g_{3}(r,D\rightarrow A)=1-\frac{|\\{t_{1},t_{2},t_{6}\\}|}{|r|}=0.5$

In other words, we must remove half of the tuples of $r$ in order to satisfy
$D\rightarrow A$.

Figure 1: The relation $r$ and the conflict-graph $\textsf{CG}(r,D\rightarrow
A)$ of Example 1.

However, MIS is an NP-complete problem [GJ79] while computing
$g_{3}(r,X\rightarrow A)$ takes polynomial time in the size of $r$ and
$X\rightarrow A$ [HKPT99]. This difference is due to the properties of
equality, namely reflexivity, transitivity, symmetry and antisymmetry. They
make $\textsf{CG}(r,X\rightarrow A)$ a disjoint union of complete $k$-partite
graphs, and hence a co-graph [FGPS22]. In this class of graphs, solving MIS is
polynomial [GRT97]. This observation suggests to study in greater detail the
impact of such properties on the structure of conflict-graphs. First, we need
to introduce predicates to relax equality, and to define a more general
version of the error validation problem accordingly.

##  4 Predicates to relax equality

In this section, in line with previous researches on extensions of functional
dependencies [SGHW20, CDP15], we equip each attribute of a relation scheme
with a binary predicate. We define the new $g_{3}$-error and the corresponding
error validation problem.

Let $R$ be a relation scheme. For each $A\in R$, let
$\phi_{A}\colon\textsf{dom}(A)\times\textsf{dom}(A)\to\\{\texttt{\small{true}},\texttt{\small{false}}\\}$
be a predicate. For instance, the predicate $\phi_{A}$ can be equality, a
distance, or a similarity relation. We assume that predicates are black-box
oracles that can be computed in polynomial time in the size of their input.

Let $\Phi$ be a set of predicates, one for each attribute in $R$. The pair
$(R,\Phi)$ is a _relation scheme with predicates_. In a relation scheme with
predicates, relations and FDs are unchanged. However, the way a relation
satisfies (or not) a FD can easily be adapted to $\Phi$.

######  Definition 2 (Satisfaction with predicates).

Let $(R,\Phi)$ be a relation scheme with predicates, $r$ a relation and
$X\rightarrow A$ a functional dependency both over $(R,\Phi)$. The relation
$r$ _satisfies_ $X\rightarrow A$ with respect to $\Phi$, denoted by
$r\models_{\Phi}X\rightarrow A$, if for every pair of tuples $(t_{1},t_{2})$
of $r$, the following formula holds:

$\left(\bigwedge_{B\in
X}\phi_{B}(t_{1}[B],t_{2}[B])\right)\implies\phi_{A}(t_{1}[A],t_{2}[A])$

An new version of the $g_{3}$-error adapted to $\Phi$ is presented in the
following definition.

######  Definition 3.

Let $(R,\Phi)$ be a relation scheme with predicates, $r$ be a relation over
$(R,\Phi)$ and $X\rightarrow A$ a functional dependency over $(R,\Phi)$. The
_$g_{3}$ -error with predicates_ of $X\rightarrow A$ with respect to $r$,
denoted by $g_{3}^{\Phi}(r,X\rightarrow A)$ is defined as:

$g_{3}^{\Phi}(r,X\rightarrow A)=1-\frac{{\textsf{max}}(\\{|s|\mid s\subseteq
r,s\models_{\Phi}X\rightarrow A\\})}{|r|}$

From the definition of $g_{3}^{\Phi}(r,X\rightarrow A)$, we derive the
extension of the error validation problem from equality to predicates:

Error Validation Problem with Predicates (EVPP) Input: |  A relation $r$ over a relation scheme with predicates $(R,\Phi)$, a FD $X\rightarrow A$ over $(R,\Phi)$, $k\in\mathbb{R}$.
---|---
Output: |  yes if $g_{3}^{\Phi}(r,X\rightarrow A)\leq k$, no otherwise.

Observe that according to the definition of satisfaction with predicates
(Definition 2), counterexamples and conflict-graphs remain well-defined.
However, for a given predicate $\phi_{A}$, $\phi_{A}(x,y)=\phi_{A}(y,x)$ needs
not be true in general, meaning that we have to consider ordered pairs of
tuples. That is, an ordered pair of tuples $(t_{1},t_{2})$ in $r$ is a
counterexample to $X\rightarrow A$ if $\bigwedge_{B\in
X}\phi_{B}(t_{1}[B],\allowbreak t_{2}[B])=\texttt{\small{true}}$ but
$\phi_{A}(t_{1}[A],\allowbreak t_{2}[A])\neq\texttt{\small{true}}$.

We call $\textsf{CG}_{\Phi}(r,X\rightarrow A)$ the conflict-graph of
$X\rightarrow A$ in $r$. In general, $\textsf{CG}_{\Phi}(r,X\rightarrow A)$ is
directed. It is undirected if the predicates of $\Phi$ are symmetric (see
Section 5). In particular, computing $g_{3}^{\Phi}(r,X\rightarrow A)$ still
amounts to finding the size of a maximum independent set in
$\textsf{CG}_{\Phi}(r,X\rightarrow A)$.

######  Example 2.

We use the relation of Figure 1. Let
$\Phi=\\{\phi_{A},\phi_{B},\phi_{C},\phi_{D}\\}$ be the collection of
predicates defined as follows, for every $x,y\in\mathbb{N}$:

  * •

$\phi_{A}(x,y)=\phi_{B}(x,y)=\phi_{C}(x,y)=\texttt{\small{true}}$ if and only
if $|x-y|\leq 1$. Thus, $\phi_{A}$ is reflexive and symmetric but not
transitive (see Section 5),

  * •

$\phi_{D}$ is the equality.

The pair $(R,\Phi)$ is a relation scheme with predicates. We have
$r\models_{\Phi}AB\rightarrow D$ but $r\not\models_{\Phi}C\rightarrow A$. In
Figure 2, we depict $\textsf{CG}_{\Phi}(r,C\rightarrow A)$. A maximum
independent set of this graph is $\\{t_{1},t_{2},t_{3},t_{5}\\}$. We deduce

$g_{3}^{\Phi}(r,C\rightarrow
A)=1-\frac{|\\{t_{1},t_{2},t_{3},t_{5}\\}|}{|r|}=\frac{1}{3}$

Figure 2: The conflict-graph $\textsf{CG}_{\Phi}(r,C\rightarrow A)$ of Example
2.

Thus, there is also a strong relationship between EVPP and MIS, similar to the
one between EVP and MIS. Nonetheless, unlike EVP, the problem EVPP is NP-
complete [SCP13]. In the next section, we study this gap of complexity between
EVP and EVPP via different properties of predicates.

##  5 Predicates properties in the $g_{3}$-error

In this section, we study properties of binary predicates that are commonly
used to replace equality. We show how each of them affects the error
validation problem.

First, we define the properties of interest in this paper. Let $(R,\Phi)$ be a
relation scheme with predicates. Let $A\in R$ and $\phi_{A}$ be the
corresponding predicate. We consider the following properties:

  * (ref)

$\phi_{A}(x,x)=\texttt{\small{true}}$ for all $x\in\textsf{dom}(A)$
(reflexivity)

  * (tra)

for all $x,y,z\in\textsf{dom}(A)$,
$\phi_{A}(x,y)=\phi_{A}(y,z)=\texttt{\small{true}}$ implies
$\phi_{A}(x,z)=\texttt{\small{true}}$ (transitivity)

  * (sym)

for all $x,y\in\textsf{dom}(A)$, $\phi_{A}(x,y)=\phi_{A}(y,x)$ (symmetry)

  * (asym)

for all $x,y\in\textsf{dom}(A)$,
$\phi_{A}(x,y)=\phi_{A}(y,x)=\texttt{\small{true}}$ implies $x=y$
(antisymmetry).

Note that symmetry and antisymmetry together imply transitivity as
$\phi_{A}(x,y)=\texttt{\small{true}}$ entails $x=y$.

As a first step, we show that symmetry and transitivity are sufficient to make
EVPP solvable in polynomial time. In fact, we prove that the resulting
conflict-graph is a co-graph, as with equality.

######  Theorem 1.

The problem EVPP can be solved in polynomial time if the predicates used on
each attribute are transitive (tra) and symmetric (sym).

###### Proof.

Let $(R,\Phi)$ be a relation scheme with predicates. Let $r$ be relation over
$(R,\Phi)$ and $X\rightarrow A$ be a functional dependency, also over
$(R,\Phi)$. We assume that each predicate in $\Phi$ is transitive and
symmetric. We show how to compute the size of a maximum independent set of
$\textsf{CG}_{\Phi}(r,X\rightarrow A)$ in polynomial time.

As $\phi_{A}$ is not necessarily reflexive, a tuple $t$ in $r$ can produce a
counter-example $(t,t)$ to $X\rightarrow A$. Indeed, it may happen that
$\phi_{B}(t[B],t[B])=\texttt{true}$ for each $B\in X$, but
$\phi_{A}(t[A],t[A])=\texttt{false}$. However, it follows that $t$ never
belongs to a subrelation $s$ of $r$ satisfying $s\models_{\Phi}X\rightarrow
A$. Thus, let $r^{\prime}=r\setminus\\{t\in
r\mid\\{t\\}\not\models_{\Phi}X\rightarrow A\\}$. Then, a subrelation of $r$
satisfies $X\rightarrow A$ if and only if it is an independent set of
$\textsf{CG}_{\Phi}(r,X\rightarrow A)$ if and only if it is an independent set
of $\textsf{CG}_{\Phi}(r^{\prime},X\rightarrow A)$. Consequently, computing
$g_{3}^{\Phi}(r,X\rightarrow A)$ is solving MIS in
$\textsf{CG}_{\Phi}(r^{\prime},X\rightarrow A)$.

We prove now that $\textsf{CG}_{\Phi}(r^{\prime},X\rightarrow A)$ is a co-
graph. Assume for contradiction that
$\textsf{CG}_{\Phi}(r^{\prime},X\rightarrow A)$ has an induced path $P$ with
$4$ elements, say $t_{1},t_{2},t_{3},t_{4}$ with edges $(t_{1},t_{2})$,
$(t_{2},t_{3})$ and $(t_{3},t_{4})$. Remind that edges of
$\textsf{CG}_{\Phi}(r^{\prime},X\rightarrow A)$ are counterexamples to
$X\rightarrow A$ in $r^{\prime}$. Hence, by symmetry and transitivity of the
predicates of $\Phi$, we deduce that for each pair $(i,j)$ in $\\{1,2,3,4\\}$,
$\bigwedge_{B\in X}\phi_{B}(t_{i}[B],t_{j}[B])=\texttt{\small{true}}$. Thus,
we have $\bigwedge_{B\in X}\phi_{B}(t_{3}[B],t_{1}[B])=\bigwedge_{B\in
X}\allowbreak\phi_{B}(t_{1}[B],\allowbreak t_{4}[B])=\texttt{\small{true}}$.
However, neither $(t_{1},t_{3})$ nor $(t_{1},t_{4})$ belong to
$\textsf{CG}_{\Phi}(r^{\prime},\allowbreak X\rightarrow A)$ since $P$ is an
induced path by assumption. Thus,
$\phi_{A}(t_{3}[A],t_{1}[A])=\phi_{A}(t_{1}[A],t_{4}[A])=\texttt{\small{true}}$
must hold. Nonetheless, the transitivity of $\phi_{A}$ implies
$\phi_{A}(t_{3}[A],t_{4}[A])=\texttt{\small{true}}$, a contradiction with
$(t_{3},t_{4})$ being an edge of $\textsf{CG}_{\Phi}(r^{\prime},\allowbreak
X\rightarrow A)$. We deduce that $\textsf{CG}_{\Phi}(r^{\prime},X\rightarrow
A)$ cannot contain an induced $P_{4}$, and that it is indeed a co-graph. As
MIS can be solved in polynomial time for co-graphs [GRT97], the theorem
follows. ∎

One may encounter non-reflexive predicates when dealing with strict orders or
with binary predicates derived from SQL equality. In the $3$-valued logic of
SQL, comparing the null value with itself evaluates to false rather than true.
With this regard, it could be natural for domain experts to use a predicate
which is transitive, symmetric and reflexive almost everywhere but on the null
value. This would allow to deal with missing information without altering the
data.

The previous proof heavily makes use of transitivity, which has a strong
impact on the edges belonging to the conflict-graph. Intuitively, conflict-
graphs can become much more complex when transitivity is dropped. Indeed, we
prove an intuitive case: when predicates are not required to be transitive,
EVPP becomes intractable.

######  Theorem 2.

The problem EVPP is NP-complete even when the predicates used on each
attribute are symmetric (sym) and reflexive (ref).

The proof is given in Appendix A. It is a reduction from the problem (dual to
MIS) of finding the size of a maximum clique in general graphs. It uses
arguments similar to the proof of Song et al. [SCP13] showing the NP-
completeness of EVPP for comparable dependencies.

We turn our attention to the case where symmetry is dropped from the
predicates. In this context, conflict-graphs are directed. Indeed, an ordered
pair of tuples $(t_{1},t_{2})$ may be a counterexample to a functional
dependency, but not $(t_{2},t_{1})$. Yet, transitivity still contributes to
constraining the structure of conflict-graphs, as suggested by the following
example.

######  Example 3.

We consider the relation of Example 1. We equip $A,B,C,D$ with the following
predicates:

  * •

$\phi_{C}(x,y)=\texttt{\small{true}}$ if and only if $x\leq y$

  * •

$\phi_{A}(x,y)$ is defined by

$\phi_{A}(x,y)=\begin{cases}\texttt{\small{true}}&\text{if }x=y\\\
\texttt{\small{true}}&\text{if }x=1\text{ and }y\in\\{2,4\\}\\\
\texttt{\small{true}}&\text{if }x=3\text{ and }y=4\\\
\texttt{\small{false}}&\text{otherwise.}\end{cases}$

  * •

$\phi_{B}$ and $\phi_{D}$ are the equality.

Let $\Phi=\\{\phi_{A},\phi_{B},\phi_{C},\phi_{D}\\}$. The conflict-graph
$\textsf{CG}_{\Phi}(C\rightarrow A)$ is represented in Figure 3. Since
$\phi_{C}$ is transitive, we have
$\phi_{C}(t_{3}[C],t_{j}[C])=\texttt{\small{true}}$ for each tuple $t_{j}$ of
$r$. Moreover, $\phi_{A}(t_{3}[A],t_{6}[A])=\texttt{\small{false}}$ since
$(t_{3},t_{6})$ is a counterexample to $C\rightarrow A$. Therefore, the
transitivity of $\phi_{A}$ implies either
$\phi_{A}(t_{3}[A],t_{4}[A])=\texttt{\small{false}}$ or
$\phi_{A}(t_{4}[A],t_{6}[A])=\texttt{\small{false}}$. Hence, at least one of
$(t_{3},t_{4})$ and $(t_{4},t_{6})$ must be a counterexample to $C\rightarrow
A$ too. In the example, this is $(t_{3},t_{4})$.

Figure 3: The conflict-graph $\textsf{CG}_{\Phi}(r,C\rightarrow A)$ of Example
3.

Nevertheless, if transitivity constrains the complexity of the graph, dropping
symmetry still allows new kinds of graph structures. Indeed, in the presence
of symmetry, a conflict-graph cannot contain induced paths with more than $3$
elements because of transitivity. However, such paths may exist when symmetry
is removed.

######  Example 4.

In the previous example, the tuples $t_{2},t_{4},t_{5},t_{6}$ form an induced
$P_{4}$ of the underlying undirected graph of
$\textsf{CG}_{\Phi}(r,C\rightarrow A)$, even though $\phi_{A}$ and $\phi_{C}$
enjoy transitivity.

Therefore, we are left with the following intriguing question: can the loss of
symmetry be used to break transitivity, and offer conflict-graphs a structure
sufficiently complex to make EVPP intractable? The next theorem answers this
question affirmatively.

######  Theorem 3.

The problem EVPP is NP-complete even when the predicates used on each
attribute are transitive (tra), reflexive (ref), and antisymmetric (asym).

The proof is given in Appendix B. It is a reduction from MIS in
$2$-subdivision graphs [Pol74].

Theorem 1, Theorem 2 and Theorem 3 characterize the complexity of EVPP for
each combination of predicates properties. In the next section, we discuss the
granularity of these, and we use them as a framework to compare the complexity
of EVPP for some known extensions of functional dependencies.

##  6 Discussions

Replacing equality with various predicates to extend the semantics of
classical functional dependencies is frequent [CDP15, SGHW20]. Our approach
offers to compare these extensions on EVPP within a unifying framework based
on the properties of the predicates they use. We can summarize our results
with the hierarchy of classes of predicates given in Figure 4.

Figure 4: Complexity of EVPP with respect to the properties of predicates.

Regarding the computation of the $g_{3}$-error, most existing works have
focused on similarity/distance predicates. First, the $g_{3}$-error can be
computed in polynomial time for classical functional dependencies [HKPT98].
Then, Song et al. [SCP13] show that EVPP is NP-complete for a broad range of
extensions of FDs which happen to be reflexive (ref) and symmetric (sym)
predicates, which coincides with Theorem 2. However, they do not study
predicate properties as we do in this paper. More precisely, they identify the
hardness of EVPP for differential [Son10], matching [Fan08], metric [KSSV09],
neighborhood [BW01], and comparable dependencies [SCP13]. For some of these
dependencies, predicates may be defined over sets of attributes. Using one
predicate per attribute and taking their conjunction is a particular case of
predicate on attribute sets.

Some extensions of FDs use partial orders as predicates. This is the case of
ordered dependencies [DH82, GH83], ordered FDs [Ng01], and also of some
sequential dependencies [GKK+09] and denial constraints [BBFL05] for instance.
To our knowledge, the role of symmetry in EVPP has received little attention.
For sequential dependencies [GKK+09], a measure different than the
$g_{3}$-error have been used. The predicates of Theorem 3 are reflexive,
transitive and antisymmetric. Hence they are partial orders. Consequently, the
FDs in this context are _ordered functional dependencies_ as defined by Ng
[Ng01]. We obtain the following corollary:

######  Corollary 1.

EVPP is NP-complete for ordered functional dependencies.

Ordered functional dependencies are a restricted case of ordered dependencies
[GH83], sequential dependencies [GKK+09], and denial constraints [BBFL05] (see
[SGHW20]). The hardness of computing the $g_{3}$-error for these dependencies
follows from Corollary 1.

The hierarchy depicts quite accurately the current knowledge about EVPP and
the delimitation between tractable and intractable cases. However, this
analysis may require further refinements. Indeed, there may be particular
types of FDs with predicates where EVPP is tractable in polynomial time, even
though their predicates belong to a class for which the problem is NP-
complete. For instance, assume that each attribute $A$ in $R$ is equipped with
a _total_ order $\phi_{A}$. We show in Proposition 1 and Corollary 2 that in
this case, EVPP can be solved in polynomial time, even though the predicates
are reflexive, transitive and antisymmetric.

######  Proposition 1.

Let $(R,\Phi)$ be a relation scheme with predicates. Then, EVPP can be solved
in polynomial time for a given FD $X\rightarrow A$ if $\phi_{B}$ is transitive
for each $B\in X$ and $\phi_{A}$ is a total order.

###### Proof.

Let $(R,\Phi)$ be a relation scheme with predicates and $X\rightarrow A$ a
functional dependency. Assume that $\phi_{B}$ is transitive for each $B\in X$
and that $\phi_{A}$ is a total order. Let $r$ be a relation over $(R,\Phi)$.
Let $G=(r,E)$ be the undirected graph underlying
$\textsf{CG}_{\Phi}(r,X\rightarrow A)$, that is, $(t_{i},t_{j})\in E$ if and
only if $(t_{i},t_{j})$ or $(t_{j},t_{i})$ is an edge of
$\textsf{CG}_{\Phi}(r,X\rightarrow A)$.

We show that $G$ is a comparability graph. To do so, we associate the
following predicate $\leq$ to $\textsf{CG}_{\Phi}(r,X\rightarrow A)$: for each
pair $t_{i},t_{j}$ of tuples of $r$, $t_{i}\leq t_{i}$ and $t_{i}\leq t_{j}$
if $(t_{i},t_{j})$ is a counterexample to $X\rightarrow A$. We show that
$\leq$ is a partial order:

  * •

_reflexivity_. It follows by definition.

  * •

_antisymmetry_. We use contrapositive. Let $t_{i},t_{j}$ be two distinct
tuples of $r$ and assume that $(t_{i},t_{j})$ belongs to
$\textsf{CG}_{\Phi}(r,X\rightarrow A)$. We need to prove that $(t_{j},t_{i})$
does not belong to $\textsf{CG}_{\Phi}(r,X\rightarrow A)$, _i.e._ it is not a
counterexample to $X\rightarrow A$. First,
$(t_{i},t_{j})\in\textsf{CG}_{\Phi}(r,X\rightarrow A)$ implies that
$\phi_{A}(t_{i}[A],t_{j}[A])=\texttt{\small{false}}$. Then, since $\phi_{A}$
is a total order, $\phi_{A}(t_{j}[A],t_{i}[A])=\texttt{\small{true}}$.
Consequently, $(t_{j},t_{i})$ cannot belong to
$\textsf{CG}_{\Phi}(r,X\rightarrow A)$ and $\leq$ is antisymmetric.

  * •

_transitivity_. Let $t_{i},t_{j},t_{k}$ be tuples of $r$ such that
$(t_{i},t_{j})$ and $(t_{j},t_{k})$ are in $\textsf{CG}_{\Phi}(r,X\rightarrow
A)$. Applying transitivity, we have that $\bigwedge_{B\in
X}\phi_{B}(t_{i}[B],t_{k}[B])=\texttt{\small{true}}$. We show that
$\phi_{A}(t_{i}[A],\allowbreak t_{k}[A])=\texttt{\small{false}}$. Since
$(t_{i},t_{j})$ is a counterexample to $X\rightarrow A$, we have
$\phi_{A}(t_{i}[A],t_{j}[A])=\texttt{\small{false}}$. As $\phi_{A}$ is a total
order, we deduce that $\phi_{A}(t_{j}[A],t_{i}[A])=\texttt{\small{true}}$.
Similarly, we obtain $\phi_{A}(t_{k}[A],\allowbreak
t_{j}[A])=\texttt{\small{true}}$. As $\phi_{A}$ is transitive, we derive
$\phi_{A}(t_{k}[A],\allowbreak t_{i}[A])=\texttt{\small{true}}$. Now assume
for contradiction that $\phi_{A}(t_{i}[A],t_{k}[A])=\texttt{\small{true}}$.
Since, $\phi_{A}(t_{k}[A],t_{j}[A])=\texttt{\small{true}}$, we derive
$\phi_{A}(t_{i}[A],t_{j}[A])=\texttt{\small{true}}$ by transitivity of
$\phi_{A}$, a contradiction. Therefore, $\phi_{A}(t_{i}[A],\allowbreak
t_{k}[A])=\texttt{\small{false}}$. Using the fact that $\bigwedge_{B\in
X}\allowbreak\phi_{B}(t_{i}[B],t_{k}[B])=\texttt{\small{true}}$, we conclude
that $(t_{i},t_{k})$ is also a counterexample to $X\rightarrow A$. The
transitivity of $\leq$ follows.

Consequently, $\leq$ is a partial order and $G$ is indeed a comparability
graph. Since MIS can be solved in polynomial time for comparability graphs
[Gol04], the result follows. ∎

We can deduce the following corollary on total orders, that can be used for
ordered dependencies.

######  Corollary 2.

Let $(R,\Phi)$ be a relation scheme with predicates. Then, EVPP can be solved
in polymomial time if each predicate in $\Phi$ is a total order.

In particular, Golab et al. [GKK+09] proposed a polynomial-time algorithm for
a variant of $g_{3}$ applied to a restricted type of sequential dependencies
using total orders on each attribute.

##  7 Conclusion and future work

In this work, we have studied the complexity of computing the $g_{3}$-error
when equality is replaced by more general predicates. We studied four common
properties of binary predicates: reflexivity, symmetry, transitivity, and
antisymmetry. We have shown that when symmetry and transitivity are taken
together, the $g_{3}$-error can be computed in polynomial time. Transitivity
strongly impacts the structure of the conflict-graph of the counterexamples to
a functional dependency in a relation. Thus, it comes as no surprise that
dropping transitivity makes the $g_{3}$-error hard to compute. More
surprisingly, removing symmetry instead of transitivity leads to the same
conclusion. This is because deleting symmetry makes the conflict-graph
directed. In this case, the orientation of the edges weakens the impact of
transitivity, thus allowing the conflict-graph to be complex enough to make
the $g_{3}$-error computation problem intractable.

We believe our approach sheds new light on the problem of computing the
$g_{3}$-error, and that it is suitable for estimating the complexity of this
problem when defining new types of FDs, by looking at the properties of
predicates used to compare values.

We highlight now some research directions for future works. In a recent paper
[LKR20], Livshits et al. study the problem of computing optimal repairs in a
relation with respect to a set of functional dependencies. A repair is a
collection of tuples which does not violate a prescribed set of FDs. It is
optimal if it is of maximal size among all possible repairs. Henceforth, there
is a strong connection between the problem of computing repairs and computing
the $g_{3}$-error with respect to a collection of FDs. In their work, the
authors give a dichotomy between tractable and intractable cases based on the
structure of FDs. In particular, they use previous results from Gribkoff et
al. [GVdBS14] to show that the problem is already NP-complete for $2$ FDs in
general. In the case where computing an optimal repair can be done in
polynomial time, it would be interesting to use our approach and relax
equality with predicates in order to study the tractability of computing the
$g_{3}$-error on a collection of FDs with relaxed equality.

From a practical point of view, the exact computation of the $g_{3}$-error is
extremely expensive in large datasets. Recent works [CDP16, FGPS22] have
proposed to use approximation algorithms to compute the $g_{3}$-error both for
equality and predicates. It could be of interest to identify properties or
classes of predicates where more efficient algorithms can be adopted. It is
also possible to extend the existing algorithms calculating the classical
$g_{3}$-error (see _e.g._ [HKPT99]). They use the projection to identify
equivalence classes among values of $A$ and $X$. However, when dropping
transitivity (for instance in similarity predicates), separating the values of
a relation into “similar classes” requires to devise a new projection
operation, a seemingly tough but fascinating problem to investigate.

### Acknowledgment.

We thank the reviewers for their valuable feedback.. We also thank the
Datavalor initiative of Insavalor (subsidiary of INSA Lyon) for funding part
of this work.

## References

  * [BBFL05] Leopoldo Bertossi, Loreto Bravo, Enrico Franconi, and Andrei Lopatenko.  Complexity and approximation of fixing numerical attributes in databases under integrity constraints.  In International Workshop on Database Programming Languages, pages 262–278. Springer, 2005.
  * [Ber73] Claude Berge.  Graphs and hypergraphs.  North-Holland Pub. Co., 1973.
  * [Ber11] Leopoldo Bertossi.  Database repairing and consistent query answering.  Synthesis Lectures on Data Management, 3(5):1–121, 2011.
  * [BFG+07] Philip Bohannon, Wenfei Fan, Floris Geerts, Xibei Jia, and Anastasios Kementsietsidis.  Conditional functional dependencies for data cleaning.  In 2007 IEEE 23rd international conference on data engineering, pages 746–755. IEEE, 2007.
  * [BW01] Renaud Bassée and Jef Wijsen.  Neighborhood dependencies for prediction.  In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 562–567. Springer, 2001.
  * [CDP15] Loredana Caruccio, Vincenzo Deufemia, and Giuseppe Polese.  Relaxed functional dependencies—a survey of approaches.  IEEE Transactions on Knowledge and Data Engineering, 28(1):147–165, 2015.
  * [CDP16] Loredana Caruccio, Vincenzo Deufemia, and Giuseppe Polese.  On the discovery of relaxed functional dependencies.  In Proceedings of the 20th International Database Engineering & Applications Symposium, pages 53–61, 2016.
  * [CGF+09] Graham Cormode, Lukasz Golab, Korn Flip, Andrew McGregor, Divesh Srivastava, and Xi Zhang.  Estimating the confidence of conditional functional dependencies.  In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD ’09, page 469–482, New York, NY, USA, 2009. Association for Computing Machinery.
  * [DH82] Jirun Dong and Richard Hull.  Applying approximate order dependency to reduce indexing space.  In Proceedings of the 1982 ACM SIGMOD international conference on Management of data, pages 119–127, 1982.
  * [DP02] Brian A Davey and Hilary A Priestley.  Introduction to lattices and order.  Cambridge university press, 2002.
  * [Fan08] Wenfei Fan.  Dependencies revisited for improving data quality.  In Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 159–170, 2008.
  * [FGPS22] Pierre Faure–Giovagnoli, Jean-Marc Petit, and Vasile-Marian Scuturici.  Assessing the existence of a function in a dataset with the g3 indicator.  In IEEE International Conference on Data Engineering, 2022.
  * [GH83] Seymour Ginsburg and Richard Hull.  Order dependency in the relational model.  Theoretical computer science, 26(1-2):149–195, 1983.
  * [GJ79] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [GKK+08] Lukasz Golab, Howard Karloff, Flip Korn, Divesh Srivastava, and Bei Yu.  On generating near-optimal tableaux for conditional functional dependencies.  Proceedings of the VLDB Endowment, 1(1):376–390, 2008.
  * [GKK+09] Lukasz Golab, Howard Karloff, Flip Korn, Avishek Saha, and Divesh Srivastava.  Sequential dependencies.  Proceedings of the VLDB Endowment, 2(1):574–585, 2009.
  * [Gol04] Martin Charles Golumbic.  Algorithmic graph theory and perfect graphs.  Elsevier, 2004.
  * [GRT97] Vassilis Giakoumakis, Florian Roussel, and Henri Thuillier.  On p_4-tidy graphs.  Discrete Mathematics and Theoretical Computer Science, 1:17–41, 1997.
  * [GVdBS14] Eric Gribkoff, Guy Van den Broeck, and Dan Suciu.  The most probable database problem.  In Proceedings of the First international workshop on Big Uncertain Data (BUDA), pages 1–7, 2014.
  * [HKPT98] Ykä Huhtala, Juha Karkkainen, Pasi Porkka, and Hannu Toivonen.  Efficient discovery of functional and approximate dependencies using partitions.  In Proceedings 14th International Conference on Data Engineering, pages 392–401. IEEE, 1998.
  * [HKPT99] Yka Huhtala, Juha Kärkkäinen, Pasi Porkka, and Hannu Toivonen.  Tane: An efficient algorithm for discovering functional and approximate dependencies.  The computer journal, 42(2):100–111, 1999.
  * [KM95] Jyrki Kivinen and Heikki Mannila.  Approximate inference of functional dependencies from relations.  Theoretical Computer Science, 149(1):129–149, 1995.
  * [KSSV09] Nick Koudas, Avishek Saha, Divesh Srivastava, and Suresh Venkatasubramanian.  Metric functional dependencies.  In 2009 IEEE 25th International Conference on Data Engineering, pages 1275–1278. IEEE, 2009.
  * [LKR20] Ester Livshits, Benny Kimelfeld, and Sudeepa Roy.  Computing optimal repairs for functional dependencies.  ACM Transactions on Database Systems (TODS), 45(1):1–46, 2020.
  * [LL12] Mark Levene and George Loizou.  A guided tour of relational databases and beyond.  Springer Science & Business Media, 2012.
  * [MR92] Heikki Mannila and Kari-Jouko Räihä.  The design of relational databases.  Addison-Wesley Longman Publishing Co., Inc., 1992.
  * [NC01] Noel Novelli and Rosine Cicchetti.  Functional and embedded dependency inference: a data mining point of view.  Information Systems, 26(7):477–506, 2001.
  * [Ng01] Wilfred Ng.  An extension of the relational data model to incorporate ordered domains.  ACM Transactions on Database Systems (TODS), 26(3):344–383, 2001\.
  * [Pol74] Svatopluk Poljak.  A note on stable sets and colorings of graphs.  Commentationes Mathematicae Universitatis Carolinae, 15(2):307–309, 1974.
  * [SCP13] Shaoxu Song, Lei Chen, and S Yu Philip.  Comparable dependencies over heterogeneous data.  The VLDB journal, 22(2):253–274, 2013.
  * [SGHW20] Shaoxu Song, Fei Gao, Ruihong Huang, and Chaokun Wang.  Data dependencies extended for variety and veracity: A family tree.  IEEE Transactions on Knowledge and Data Engineering, 12 2020.
  * [Son10] Shaoxu Song.  Data dependencies in the presence of difference.  PhD thesis, Hong Kong University of Science and Technology, 2010.

##  Appendix A Proof of Theorem 2

######  Theorem (2).

The problem EVPP is NP-complete even when the predicates used on each
attributes are symmetric (sym) and reflexive (ref).

###### Proof.

We first show that EVPP belongs to NP. Let $(R,\Phi)$ be a relation scheme
with predicates, $r$ a relation over $(R,\Phi)$, $X\rightarrow A$ a functional
dependency over $(R,\Phi)$ and $k\in\mathbb{R}$. We have that
$g_{3}^{\Phi}(X\rightarrow A,r)\leq k$ if and only if there exists a
subrelation $s$ in $r$ satisfying $s\models_{\Phi}X\rightarrow A$ and
$1-\frac{|s|}{|r|}\leq k$, or $|s|\geq(1-k)\times|r|$ equivalently. Therefore,
a certificate for EVPP is a subrelation $s$ containing at least
$(1-k)\times|r|$ tuples and satisfying $X\rightarrow A$ (with respect to
$\Phi$). Since predicates can be computed in polynomial time by assumption, it
takes polynomial time to check that $s\models_{\Phi}X\rightarrow A$. Thus,
EVPP belongs to NP.

To show NP-completeness, it is convenient to use a reduction from Maximum
Clique (MC) rather than MIS, even though the problems are polynomially
equivalent:

Maximum Clique (MC) Input: |  A graph $G=(V,E)$, $k\in\mathbb{N}$.
---|---
Output: |  yes if $G$ has a clique with at least $k$ vertices.

Let $G=(V,E)$ be a graph with $V=\\{u_{1},\dots,u_{n}\\}$ for some
$n\in\mathbb{N}$, and $E=\\{e_{1},\dots,e_{m}\\}$ for some $m\in\mathbb{N}$.
Let $k$ be an integer such that $k\leq|V|$. We construct an instance of EVPP.
We begin with a relation scheme with predicates $(R,\Phi)$ where
$R=\\{B_{1},\dots,B_{m},A\\}$, $\Phi=\\{\phi_{1},\dots,\phi_{m},\phi_{A}\\}$ ,
and:

  * •

for each $1\leq i\leq m$, $\textsf{dom}(B_{i})=\\{0,1,2\\}$ and $\phi_{i}$ is
defined as follows:

$\phi_{i}(x,y)=\begin{cases}\texttt{\small{true}}&\text{if }x=y\text{ or
}x+y<3\\\ \texttt{\small{false}}&\text{otherwise.}\end{cases}$

Observe that $\phi_{i}$ is reflexive and symmetric.

  * •

$\textsf{dom}(A)=\\{1,\dots,n\\}$, and the predicate $\phi_{A}$ for $A$ is
defined by $\phi_{A}(x,y)=\texttt{\small{true}}$ if and only if $x=y$. Thus,
$\phi_{A}$ is reflexive and symmetric.

Observe that the predicates can be computed in polynomial time in the size of
their input. Now, we build a relation $r=\\{t_{1},\dots,t_{n}\\}$ (one tuple
per vertex in $G$) over $(R,\Phi)$. For each $1\leq i\leq n$, we put
$t_{i}[A]=i$ and for each $1\leq j\leq m$:

$t_{i}[B_{j}]=\begin{cases}0&\text{if }u_{i}\notin e_{j}\\\ 1&\text{if
}e_{j}=(u_{i},u_{\ell})\text{ and }i<\ell\\\ 2&\text{if
}e_{j}=(u_{\ell},u_{i})\text{ and }\ell<i\\\ \end{cases}$

Finally, let $k^{\prime}=1-\frac{k}{n}$, and consider the functional
dependency $X\rightarrow A$ where $X=\\{B_{1},\dots,B_{m}\\}$. We obtain an
instance of EVPP which can be constructed in polynomial time in the size of
$G$. The reduction is illustrated on an example in Figure 5.

Figure 5: Reduction of Theorem 2. In grey, a clique and its associated
subrelation satisfying $X\rightarrow A$.

To conclude the proof, we have to prove that $G$ contains a clique $K$ such
that $|K|\geq k$ if and only if $g_{3}^{\Phi}(X\rightarrow A,r)\leq
k^{\prime}$. To do so, we show that for every distinct tuples $t_{i},t_{j}$ of
$r$, $\bigwedge_{1\leq\ell\leq m}\phi_{\ell}(t_{i}[B_{\ell}],\allowbreak
t_{j}[B_{\ell}])=\texttt{\small{true}}$ if and only if $(u_{i},u_{j})$ is not
an edge of $G$.

We begin with the only if part. Hence, assume that for each $1\leq\ell\leq m$,
we have $\phi_{\ell}(t_{i}[B_{\ell}],t_{j}[B_{\ell}])=\texttt{\small{true}}$.
By definition of $\phi_{\ell}$, we have two cases:

  * •

$t_{i}[B_{\ell}]=t_{j}[B_{\ell}]$. By construction of $r$, it follows that
$t_{i}[B_{\ell}]=0$. Hence, neither $u_{i}$ nor $u_{j}$ belongs to $e_{\ell}$.

  * •

$t_{i}[B_{\ell}]+t_{j}[B_{\ell}]<3$. It follows that either
$t_{i}[B_{\ell}]=0$ or $t_{j}[B_{\ell}]=0$. Without loss of generality, assume
that $t_{i}[B_{\ell}]=0$. Then, again by construction of $r$, we deduce that
$u_{i}\notin e_{\ell}$.

Thus, $(u_{i},u_{j})$ is not an edge of $G$.

We move to the if part. We use contrapositive. Hence, assume there exists some
$B_{\ell}$, $1\leq\ell\leq m$, such that
$\phi_{\ell}(t_{i}[B_{\ell}],t_{j}[B_{\ell}])=\texttt{\small{false}}$. By
definition of $\phi_{\ell}$, we deduce that $t_{i}[B_{\ell}]\neq
t_{j}[B_{\ell}]$ and $t_{i}[B_{\ell}]+t_{j}[B_{\ell}]\geq 3$. Without loss of
generality, we obtain $t_{i}[B_{\ell}]=1$ and $t_{j}[B_{\ell}]=2$. Therefore,
by construction of $r$, $u_{i}\in e_{\ell}$ and $u_{j}\in e_{\ell}$ must hold.
As $t_{i}[B_{\ell}]\neq t_{j}[B_{\ell}]$, we deduce that
$(u_{i},u_{j})=e_{\ell}$, concluding this part of the proof.

Consequently, a subset $K$ of $V$ is a clique in $G$ if and only if the
corresponding set of tuples $s(K)$ is a subrelation of $r$ which satisfies
$X\rightarrow A$. Therefore, $G$ contains a clique $K$ such that $|K|\geq k$
if and only if $g_{3}^{\Phi}(X\rightarrow A,r)\leq k^{\prime}$ holds, which
concludes the proof. ∎

##  Appendix B Proof of Theorem 3

######  Theorem (3).

The problem EVPP is NP-complete even when the predicates used on each
attribute are transitive (tra), reflexive (ref), and antisymmetric (asym).

###### Proof.

The fact that EVPP belongs to NP has been shown in Theorem 2.

To show NP-completeness, we use a reduction from MIS in $2$-subdivision
graphs, in which MIS remains NP-complete [Pol74]. Let $G=(V,E)$ be an
(undirected) graph where $V=\\{u_{1},\dots,u_{n}\\}$ and
$E=\\{e_{1},\dots,e_{m}\\}$. Without loss of generality, we assume that $G$ is
loopless and that each vertex belongs to at least one edge. Let
$V_{2}=V\cup\\{v_{k}^{i}\mid 1\leq k\leq m,1\leq i\leq n\text{ and }u_{i}\in
e_{k}\\}$ be a new set of vertices. We construct a set $E_{2}$ of edges. It is
obtained from $E$ by replacing each edge $e_{k}=(u_{i},u_{j})$ by a path made
of three edges
$\\{(u_{i},v_{k}^{i}),(v_{k}^{i},v_{k}^{j}),(v_{k}^{j},u_{j})\\}$. The graph
$G_{2}=(V_{2},E_{2})$ is the $2$-subdivision of $G$. Every $2$-subdivision
graph is the $2$-subdivision of some graph. The graph $G_{2}$ can be built in
polynomial time in the size of $G$.

Now we construct an instance of EVPP. Let $\\{a_{1},\dots,a_{n}\\}$ be a set
of characters. We build a relation scheme with predicates $(R,\Phi)$ where
$R=\\{B,A\\}$, $\Phi=\\{\phi_{B},\phi_{A}\\}$, and:

  * •

$\textsf{dom}(B)$ is the set of pairs of symbols associated to
$\\{a_{1},\dots,a_{n}\\}\times\\{a_{1},\dots,a_{n}\\}$. We add a predicate
$\phi_{B}$ as follows:

$\phi_{B}(x,y)=\begin{cases}\texttt{\small{true}}&\text{if }x=y\\\
\texttt{\small{true}}&\text{if }x\neq y\text{ and }x[1]=x[2]\text{ and
}x[1]\in\\{y[1],y[2]\\}\\\
\texttt{\small{false}}&\text{otherwise.}\end{cases}$

The predicate is _reflexive_ by definition. We prove that it is _transitive_.
Let $x,y,z\in\textsf{dom}(B)$ and assume that
$\phi_{B}(x,y)=\phi_{B}(y,z)=\texttt{\small{true}}$. If $x=y=z$, we readily
have $\phi_{B}(x,z)=\texttt{\small{true}}$. Since $x\neq z$ implies $x\neq y$
or $y\neq z$, it is sufficient to show that $\phi(x,z)=\texttt{\small{true}}$
in these two cases. Assume first that $x\neq y$. Then
$\phi_{B}(x,y)=\texttt{\small{true}}$ if and only if $x=a_{i}a_{i}$ and
$y\in\\{a_{i}a_{j},a_{j}a_{i}\\}$ for $1\leq i,j\leq n$, $i\neq j$. It follows
that $\phi_{B}(y,z)$ holds if and only if $z=y$. Thus,
$\phi_{B}(x,z)=\phi_{B}(x,y)=\texttt{\small{true}}$ is valid. Let us assume
now that $y\neq z$. Then, $\phi_{B}(y,z)=\texttt{\small{true}}$ implies that
$y=a_{i}a_{i}$ for some $1\leq i\leq n$, by definition of $\phi_{B}$.
Therefore, $\phi_{B}(x,y)=\texttt{\small{true}}$ entails $x=y$. We deduce
$\phi_{B}(x,z)=\texttt{\small{true}}$. Consequently, $\phi_{B}$ is transitive.
At last, assume that $\phi_{B}(x,y)=\texttt{\small{true}}$ with $x\neq y$.
Hence, $y[1]\neq y[2]$ and $\phi_{B}(y,x)$ cannot be true. Therefore,
$\phi_{B}(x,y)=\phi_{B}(y,x)=\texttt{\small{true}}$ entails $x=y$. Thus,
$\phi_{B}$ is also _antisymmetric_.

  * •

$\textsf{dom}(A)=\\{1,\dots,n\\}$ and $\phi_{A}(x,y)=\texttt{\small{true}}$ if
and only if $x=y$. In other words, $\phi_{A}$ is the usual equality. Hence, it
enjoys both reflexivity, transitivity and antisymmetry.

Observe that all predicates can be computed in polynomial time in the size of
their input. Now we construct a relation
$r=\\{t_{1},\dots,t_{n}\\}\cup\\{t_{k}^{i}\mid 1\leq k\leq m,1\leq i\leq
n,v_{k}^{i}\in V_{2}\\}$ (one tuple per vertex in $G_{2}$) over $(R,\Phi)$:

  * •

for each $1\leq i\leq n$, $t_{i}[B]=a_{i}a_{i}$ and $t_{i}[A]=i$,

  * •

for each $1\leq k\leq m$ and each $1\leq i\leq n$ such that $v_{k}^{i}\in
V_{2}$, let $e_{k}=(u_{i},u_{j})$, $1\leq j\leq n$, be the corresponding edge
of $G$. Then, we put $t_{k}^{i}[B]=a_{i}a_{j}$ if $i<j$ and $a_{j}a_{i}$
otherwise. As for $A$, we define $t_{k}^{i}[A]=j$.

Finally, we consider the functional dependency $B\rightarrow A$. The whole
reduction can be computed in polynomial time in the size of $G$. It is
illustrated on an example in Figure 6. Intuitively, $\phi_{B}$ guarantees that
two tuples representing adjacent vertices of $G_{2}$ will agree on $B$ in
$(R,\Phi)$. However, the transitivity of $\phi_{B}$ will produce pairs of
tuples which agree on $B$ even though they are not adjacent in $G_{2}$. More
precisely, $\phi_{B}$ returns true in two cases:

  * •

when it compares $t_{i}$ to $t_{k}^{i}$ and $t_{k}^{j}$ for each edge $e_{k}$
of $G$ to which $u_{i}$ belongs, and

  * •

when it compares $t_{k}^{i}$ to $t_{k}^{j}$ for each edge $e_{k}$ of $G$.

The role of $\Phi_{A}$ is then to assert that non-adjacent tuples cannot
produce counterexamples.

Figure 6: Reduction of Theorem 3. In grey, an independent set and its
associated subrelation satisfying $B\rightarrow A$.

We begin with the if part. Consider two (distinct) vertices of $V_{2}$ that
are connected in $G_{2}$. Because $G_{2}$ is the $2$-subdivision of $G$, we
have the following cases:

  * •

$u_{i},v_{k}^{i}$ for some $1\leq i\leq n$ and $1\leq k\leq m$. For $B$, we
have $t_{i}[B]=a_{i}a_{i}$ and $t_{k}^{i}[B]=a_{i}a_{j}$ (or $a_{j}a_{i}$) for
some $1\leq j\leq n$. Therefore,
$\phi_{B}(t_{i}[B],t_{k}^{i}[B])=\texttt{\small{true}}$ holds. However,
$t_{i}[A]\neq t_{k}^{i}[A]$ also by definition of $r$. Thus,
$\\{t_{i},t_{k}^{i}\\}\not\models_{\Phi}B\rightarrow A$.

  * •

$v_{k}^{i},v_{k}^{j}$ for some $1\leq i<j\leq n$ (without loss of generality)
and $1\leq k\leq m$. Then, $t_{k}^{i}[B]=t_{k}^{j}[B]$, $t_{k}^{i}[A]=j$, and
$t_{k}^{j}[A]=i$. It follows that
$\\{t_{k}^{j},t_{k}^{i}\\}\not\models_{\Phi}B\rightarrow A$, by definition of
$\phi_{B}$ and $\phi_{A}$.

Thus, if two vertices are connected in $G_{2}$, the corresponding tuples in
$r$ do not satisfy the functional dependency $B\rightarrow A$, concluding this
part of the proof.

We show the only if part using contrapositive. Consider two distinct vertices
of $V_{2}$ that are not connected in $G_{2}$. We have four cases:

  * •

$u_{i},u_{j}$ for some $1\leq i<j\leq n$. By definition of $r$, we have
$t_{i}[B]=a_{i}a_{i}$ and $t_{j}[B]=a_{j}a_{j}$. Thus,
$\phi_{B}(t_{i}[B],t_{j}[B])=\phi_{B}(t_{j}[B],t_{i}[B])\allowbreak=\texttt{\small{false}}$,
and $\\{t_{i},t_{j}\\}\models_{\Phi}B\rightarrow A$ holds.

  * •

$v_{k}^{i},v_{\ell}^{j}$ for some $1\leq k,\ell\leq m$ and $1\leq i,j\leq n$.
Then, $t_{k}^{i}[B][1]\neq t_{k}^{i}[B][2]$ and $t_{\ell}^{j}[B][1]\neq
t_{\ell}^{j}[B][2]$. According to $G_{2}$, $v_{k}^{i}$ and $v_{\ell}^{j}$ are
not connected if and only if $k\neq\ell$. Consequently, $t_{k}^{i}[B]\neq
t_{\ell}^{j}[B]$ by definition of $r$. Hence,
$\phi_{B}(t_{k}^{i}[B],t_{\ell}^{j}[B])=\phi_{B}(t_{\ell}^{j}[B],t_{k}^{i}[B])=\texttt{\small{false}}$.
We deduce that $\\{t_{k}^{i},t_{\ell}^{j}\\}\models_{\Phi}B\rightarrow A$.

  * •

$u_{i},v_{k}^{j}$ for some $1\leq i,j\leq n$, $1\leq k\leq m$ and $u_{i}\notin
e_{k}$ in $G$. Then, $t_{i}[B]=a_{i}a_{i}$ and since $u_{i}\notin e_{k}$, we
have $t_{k}^{j}[B]=a_{j}a_{\ell}$ (or $a_{\ell}a_{j}$) for some $1\leq\ell\leq
n$ and $i\neq j,\ell$. By definition of $\phi_{B}$, we deduce that
$\phi_{B}(t_{i}[B],t_{k}^{j}[B])=\phi_{B}(t_{k}^{j}[B],t_{i}[B])=\texttt{\small{false}}$
must hold. Therefore, $\\{t_{i},t_{j}^{k}\\}\models_{\Phi}B\rightarrow A$ is
true too.

  * •

$u_{i},v_{k}^{j}$ for some $1\leq i,j\leq n$, $1\leq k\leq m$ and $u_{i}\in
e_{k}$ in $G$. Then, necessarily $i\neq j$ by construction of $G_{2}$.
Consequently, we must have $t_{i}[A]=t_{j}^{k}[A]=i$ by definition of $r$.
Therefore, $\phi_{A}(t_{i}[A],t_{k}^{j}[A])=\texttt{\small{true}}$ and
$\\{t_{i},t_{k}^{j}\\}\models_{\Phi}B\rightarrow A$ holds.

Thus, whenever two vertices of $G_{2}$ are disconnected, the corresponding set
of tuples of $r$ satisfies $B\rightarrow A$. This concludes the proof of the
equivalence.

Consequently, $G_{2}$ has an independent set of size $k$ if and only if there
exists a subrelation $s$ of $r$ of size $k$ which satisfies $B\rightarrow A$,
concluding the proof. ∎