# The Complexity of Dependency Detection and Discovery in Relational
Databases111An extended abstract of this work was presented at the 11th
International Symposium on Parameterized and Exact Computation (IPEC 2016)
[7].

Thomas Bläsius222This work originated while all authors were affiliated with
the Hasso Plattner Institute at the University of Potsdam.
<EMAIL_ADDRESS>Tobias Friedrich333This work originated while all
authors were affiliated with the Hasso Plattner Institute at the University of
Potsdam<EMAIL_ADDRESS>Martin Schirneck444This work originated while
all authors were affiliated with the Hasso Plattner Institute at the
University of Potsdam<EMAIL_ADDRESS>
###### Abstract

Multi-column dependencies in relational databases come associated with two
different computational tasks. The detection problem is to decide whether a
dependency of a certain type and size holds in a given database, the discovery
problem asks to enumerate all valid dependencies of that type. We settle the
complexity of both of these problems for unique column combinations (UCCs),
functional dependencies (FDs), and inclusion dependencies (INDs).

We show that the detection of UCCs and FDs is W[2]-complete when parameterized
by the solution size. The discovery of inclusion-wise minimal UCCs is proven
to be equivalent under parsimonious reductions to the transversal hypergraph
problem of enumerating the minimal hitting sets of a hypergraph. The discovery
of FDs is equivalent to the simultaneous enumeration of the hitting sets of
multiple input hypergraphs.

We further identify the detection of INDs as one of the first natural
W[3]-complete problems. The discovery of maximal INDs is shown to be
equivalent to enumerating the maximal satisfying assignments of antimonotone,
3-normalized Boolean formulas.

###### keywords:

data profiling , enumeration complexity , functional dependency , inclusion
dependency , parameterized complexity , parsimonious reduction , transversal
hypergraph , unique column combination , W[3]-completeness

††journal: ArXiv.

[1]organization=Karlsruhe Institute of Technology, city=Karlsruhe,
country=Germany

[2]organization=Hasso Plattner Institute, University of Potsdam, city=Potsdam,
country=Germany

##  1 Introduction

Data profiling is the extraction of metadata from databases. An important
class of metadata in the relational model are multi-column dependencies. They
describe interconnections between the values stored for different attributes
or even across multiple instances. Arguably the most prominent type of such
dependencies are the unique column combinations (UCCs), also known as
candidate keys. These are collections of attributes such that the value
combinations appearing in those attributes identify all rows of the database.
In Figure 1, the Name and Area Code provide a unique fingerprint of the first
database as, for example, there is only one Doe, John living in UK-W1K. Note
that none of the two columns can be left out due to duplicate values. Small
UCCs are natural candidates for primary keys, avoiding the need to introduce
surrogate identification. More importantly though, knowledge of the inclusion-
wise minimal unique column combinations enable various data cleaning tasks as
well as query optimization. For example, value combinations of UCCs are by
definition distinct and form groups of size $1$, thus SQL queries working on
UCCs can skip the grouping phase and the DISTINCT operation, even if requested
by the user [12, 42]. Also, the presence of UCCs allows for early returns of
SELECT and ORDER BY operations.

Unfortunately, a dataset only rarely comes annotated with its dependencies.
Much more often they need to be computed from raw data. This leads to two
different computational tasks. The _detection problem_ , is to decide whether
for a given database whether it admits a UCC with only a few columns. The
_discovery problem_ instead asks for a complete list of all minimal UCCs,
regardless of their size and number. An equivalent term for the latter, which
is probably more common in the algorithms community, is the _enumeration_ of
minimal solutions.

Figure 1: Illustration of multi-column dependencies. Name and Area Code
together are a minimal unique column combination in the first database. The
functional dependency
$\texttt{Name},\texttt{Area\,Code}\,{\to}\,\texttt{City}$ holds, but its left-
hand side is not minimal since $\texttt{Area\,Code}\,{\to}\,\texttt{City}$ is
also valid. There are two maximal inclusion dependencies of size 1 between the
first and the second database, Age is included in ID and Name in Author. They
cannot be combined to an inclusion dependency of size 2.

Functional dependencies (FDs), another dependency type, model the case in
which one is only interested in identifying the values of a specific column,
instead of all columns. In the example in Figure 1, it is enough to know the
Area Code to also infer the City since the value in the former determines the
latter. Finally, inclusion dependencies (INDs) reveal connections between
different databases as they describe the fact that all value combinations in
certain columns of one database also appear for the attributes of another. In
contrast to UCCs and FDs, where we want solutions to be small, here we ought
to find large or maximal inclusion dependencies. Those are much more likely to
be caused by the inherent structure of the data than by mere coincidence.
Functional dependencies and inclusion dependencies can be used for example for
cardinality estimation in query plan optimizers, query rewriting, and joins
[10, 31, 33].

The detection (decision) problems for all three types of dependencies are NP-
complete.111See Sections 3.1 and 4.1 for specific statements and references.
Notwithstanding, detection algorithms often perform well on practical datasets
[1]. One approach to bridge this apparent gap is to analyze whether properties
that are usually observed in realistic data benevolently influence the
hardness of the problem. Exploiting those properties may even lead to
algorithms that guarantee a polynomial running time in case these features are
present in the problem instance. This is formalized in the concept of
parameterized algorithms [16, 23, 40]. There, one tries to ascribe the
exponential complexity entirely to an parameter of the input, other than its
mere size. If the parameter is bounded for a given class of instances, we
obtain a polynomial running time whose order of growth is independent of the
parameter. This, of course, requires one to identify parameters that are both
algorithmically exploitable and small in practice.

Consider, for instance, the histograms in Figure 2, showing the size
distribution of minimal unique column combinations and functional
dependencies, as well as maximal inclusion dependencies in the MusicBrainz
database [46]. The majority of functional dependencies are rather small, same
for unique column combinations and inclusion dependencies. Beside surrogate
keys, giving rise to multiple functional dependencies of size 1, causalities
in the data can also lead to small FDs. For example, the name of an event
together with the year in which it started determines the year in which it
ends, implying an FD of size 2. Note that the starting year alone is usually
not enough to infer this information. The name of the action, however, seems
to indicate whether the event ends in the same year or the next. The size of
the dependency is thus a natural candidate for an algorithmic parameter.
Notwithstanding, we show that it is unlikely to be the sole explanation for
the good practical performance. We prove that the detection of unique column
combinations and functional dependencies is $\textsf{W}[2]$-complete with
respect to the size of the sought solution, detecting inclusion dependencies
is even $\textsf{W}[3]$-complete. For all we know, this excludes any algorithm
parameterized by the size.

Figure 2: The number of minimal unique column combinations, minimal functional
dependencies, and maximal inclusion dependencies for varying solution sizes in
the MusicBrainz database.

The hardness of detecting INDs is surprising also from a complexity-theoretic
standpoint. Currently, there are only a handful of natural problems known to
be complete for the class $\textsf{W}[3]$. The first one was given by Chen and
Zhang [13] in the context of supply chain management. We show here that the
detection of inclusion dependencies has this property, making it the second
such problem. Since this result was first announced, Bläsius et al. [6] have
also proven the extension problem for minimal hitting sets to be
$\textsf{W}[3]$-complete using different techniques. The latter has
subsequently been improved by Casel et al. [11], they have shown that already
the special case of extension to minimal dominating sets in bipartite graphs
is hard for $\textsf{W}[3]$. Finally, building on the work presented here,
Hannula, Song, and Link [32] have very recently identified independence
detection in relational databases as another representative of this class.

For enumeration problems, the border of tractability does not run between
polynomial and super-polynomial time, at least not when measured in the input
only. The number of solutions one wishes to be computed may be exponential in
the input size, ruling out any polynomial algorithm. Instead, one could ask
for an algorithm that scales polynomially both in the input and the number of
solutions. The most important yardstick in enumeration complexity is the
_transversal hypergraph_ problem, where one is tasked to compute all minimal
hitting sets of a given hypergraph. Currently, the fastest known algorithm
runs in time $N^{\operatorname{O}(\nicefrac{{\log N}}{{\log\log N}})}$, where
$N$ is the combined input and output size [28]. It is the major open question
in the field of enumeration algorithms whether the transversal hypergraph
problem can be solved in output-polynomial time. Besides from data profiling,
the problem emerges in many applications in artificial intelligence, machine
learning, distributed systems, monotone logic, and bioinformatics see [26,
44]. There are many algorithms known that work well on practical instances
[30].

We use the insights gained on the detection of multi-column dependencies in
databases to also investigate their discovery (enumeration) problems. It is
known that minimal unique column combinations and functional dependencies can
be discovered in output-polynomial time if and only if the transversal
hypergraph problem has an output-polynomial solution [24]. However, this was
proven via a Turing-style reduction that continuously calls a decision
subroutine to check whether the enumeration part has already found all
solutions. This construction inherently uses space proportional to the output
and is therefore hardly useful in practice. We are able to radically simplify
this equivalence and connect unique column combinations, functional
dependencies, and hitting sets directly at the enumeration level using so-
called _parsimonious reductions_ , running in polynomial time and space. We
give similar results also for the discovery of maximal inclusion dependencies.

Parsimonious reductions are the most restrictive form of reduction between
enumeration problems, but–therefore–also the most useful in practice. The
close connection to the transversal hypergraph problem that we prove in this
work explains in parts why dependency discovery works quite well on real-world
databases. Moreover, it allows us to transfer ideas from the design of hitting
set enumeration algorithms to data profiling, thereby connecting the two
research areas. For example, there are very space-efficient algorithms known
for the transversal hypergraph problem, while memory consumption still seems
to be a major obstacle in dependency discovery [41, 47]. We hope that our
results here inspire better data profiling algorithms in the future.

Our Contribution. We settle the parameterized complexity of the cardinality-
constrained decision problems for unique column combinations, functional
dependencies, and inclusion dependencies in relational databases, with the
solution size as parameter. We prove the following theorems.

######  Theorem 1.

Detecting a unique column combination of size $k$ in a relational database is
$\emph{{W}}[2]$-complete when parameterized by $k$. The same is true for the
detection of a valid, non-trivial functional dependency with a left-hand side
of size at most $k$, even if the desired right-hand side is given in the
input.

######  Theorem 2.

Detecting an inclusion dependency of size $k$ in a pair of relational
databases is $\emph{{W}}[3]$-complete when parameterized by $k$. The result
remains true even if both databases are over the same relational schema with
the identity mapping between their columns.

We also characterize the complexity of enumerating all multi-column
dependencies of a certain type in a given database. We do so by proving
parsimonious equivalences with well-known enumeration problems as well as
generalizations thereof.

######  Theorem 3.

The following enumeration problems are equivalent under parsimonious
reductions:

  1. 1.

listing all minimal unique column combinations of a relational database;

  2. 2.

listing all minimal, valid, and non-trivial functional dependencies with a
fixed right-hand side;

  3. 3.

the transversal hypergraph problem.

The enumeration of functional dependencies with arbitrary right-hand sides is
equivalent to listing the hitting sets of multiple input hypergraphs. The
latter two problems are at least as hard as the transversal hypergraph
problem.

######  Theorem 4.

The following enumeration problems are equivalent under parsimonious
reductions:

  1. 1.

listing all maximal inclusion dependencies of a pair of relational
databases;

  2. 2.

listing all maximal satisfying assignments of an antimonotone,
3-normalized Boolean formula.

This remains true even if the two databases are over the same schema and only
inclusions between the same columns are allowed. All those enumeration
problems are at least as hard as the transversal hypergraph problem.

Finally, we also briefly discuss the consequences of our findings to the
approximability of minimum dependencies.

Outline. In the next section, we fix some notation and review basic concepts
needed for the later proofs. Section 3 treats unique column combinations and
functional dependencies, Section 4 then considers inclusion dependencies. Both
of these sections start with a segment that formally defines all decision and
enumeration problems discussed in the respective section. The paper is
concluded in Section 5.

##  2 Preliminaries

###  2.1 Hypergraphs and Hitting Sets

A _hypergraph_ is a non-empty, finite _vertex set_ $V\neq\emptyset$ together
with a set of subsets $\mathcal{H}\subseteq\mathcal{P}(V)$, the
_(hyper-)edges_. We identify a hypergraph with its edge set $\mathcal{H}$ if
this does not create any ambiguities. We do not exclude special cases of this
definition like the empty graph ($\mathcal{H}=\emptyset$), an empty edge
($\emptyset\in\mathcal{H}$), or isolated vertices
($V\supsetneq\bigcup_{E\in\mathcal{H}}E$). A hypergraph is _Sperner_ if none
of its edges is contained in another. The _minimization_ of $\mathcal{H}$ is
the subset of all inclusion-wise minimal edges,
$\min(\mathcal{H})=\\{E\in\mathcal{H}\mid\forall
E^{\prime}\in\mathcal{H}\colon E^{\prime}\subseteq E\Rightarrow
E^{\prime}=E\\}$. This should not be confused with the notation for a minimum
element of a set. The minimization of a hypergraph is always Sperner.

A hitting set, or transversal, of a hypergraph $(V,\mathcal{H})$ is a set
$T\subseteq V$ of vertices such that $T$ has a non-empty intersection with
every edge $E\in\mathcal{H}$. A hitting set is (inclusion-wise) minimal if it
does not properly contain another hitting set. The minimal hitting sets of
$\mathcal{H}$ form a Sperner hypergraph on the same vertex set $V$, the
transversal hypergraph $\operatorname{Tr}(\mathcal{H})$. Regarding
transversals, it does not make a difference whether the full hypergraph
$\mathcal{H}$ is considered or its minimization, it holds that
$\operatorname{Tr}(\min(\mathcal{H}))=\operatorname{Tr}(\mathcal{H})$.

###  2.2 Relational Databases and Dependencies

A _(relational) schema_ $R$ is a non-empty, finite set of _attributes_ or
_columns_. Each attribute comes implicitly associated with a set of admissible
values. A _row_ , or _record_ , over schema $R$ is a tuple $r$ whose entries
are indexed by $R$ such that, for any attribute $a\in R$, the value $r[a]$ is
admissible for $a$. A _(relational) database_ $\mathfrak{r}$ over $R$ is a
finite set of records. For any row $r$ and subset $X\subseteq R$ of columns,
$r[X]$ is the subtuple of $r$ projected onto $S$. We let $\mathfrak{r}[X]$
denote the family of all such subtuples of rows in $\mathfrak{r}$. Note that
$\mathfrak{r}[X]$ is a multiset as the same combination of values may appear
in different rows.

We are interested in multi-column dependencies in relational databases,
namely, unique column combinations, functional dependencies, and inclusion
dependencies. For their definition, we need the notion of difference sets. For
any two distinct rows $r_{1},r_{2}$, $r_{1}\neq r_{2}$, over the same schema
$R$, their _difference set_ $\\{a\in R\mid r_{1}[a]\neq r_{2}[a]\\}$ is the
set of attributes in which the rows disagree. A difference set is _(inclusion-
wise) minimal_ if it does not properly contain a difference set for another
pair of rows in the database. We denote the hypergraph of minimal difference
sets by $\mathcal{D}$. The vertex set is $R$.

A _unique column combination_ (UCC), or simply unique, for some database
$\mathfrak{r}$ over schema $R$, is a subset $U\subseteq R$ of attributes such
that for any two records $r,s\in\mathfrak{r}$, $r\neq s$, there is an
attribute $a\in U$ such that $r[a]\neq s[a]$. Equivalently, $U$ is a UCC for
$\mathfrak{r}$ iff the collection $\mathfrak{r}[U]$ of projections onto $U$ is
mere set. A UCC is (inclusion-wise) minimal if it does not properly contain
another UCC. There is an intimate connection between UCCs and transversals in
hypergraphs. It is well-known in the literature, see [1, 17], probably the
first explicit mention was by Mannila and Räihä [38].

######  Observation 5 (Folklore).

The unique column combinations are the hitting sets of difference sets. In
particular, let $\mathfrak{r}$ be a database and $\mathcal{D}$ the hypergraph
of its minimal difference sets. Then, any minimal transversal in
$\operatorname{Tr}(\mathcal{D})$ is a minimal unique of $\mathfrak{r}$ and
there are no other minimal uniques in $\mathfrak{r}$.

_Functional dependencies_ (FDs) over a schema $R$ are expressions of the form
$X\,{\to}\,a$ for some set $X\subseteq R$ of columns and a single attribute
$a\in R$. The set $X$ is the _left-hand side_ (LHS) of the dependency and $a$
the _right-hand side_ (RHS). We say that the FD has _size_ $|X|$. A functional
dependency $X\,{\to}\,a$ is said to _hold_ , or be _valid_ , in an database
$\mathfrak{r}$ (over $R$) if any pair of records that agree on $X$ also agree
on $a$, that is, if $r[X]=s[X]$ implies $r[a]=s[a]$ for any
$r,s\in\mathfrak{r}$. Otherwise, $X\,{\to}\,a$ is said to _fail_ in
$\mathfrak{r}$, or be _invalid_. The FD $\emptyset\,{\to}\,a$ holds iff all
rows agree on $a$. An FD $X\,{\to}\,a$ is _(inclusion-wise) minimal_ if it
holds in $\mathfrak{r}$ and $X^{\prime\prime}\,{\to}\,a$ fails for any proper
subset $X^{\prime\prime}\subsetneq X$. A functional dependency is _non-
trivial_ if $a\notin X$. Note that trivial functional dependencies hold in any
database.

Finally, we turn to multi-column dependencies among multiple databases. Let
$R$ and $S$ be two relational schemas and $\mathfrak{r}$ and $\mathfrak{s}$
databases over $R$ and $S$, respectively. For some $X\subseteq R$, let
$\sigma\colon X\to S$ be an injective map. The pair $(X,\sigma)$ is an
_inclusion dependency_ (IND) if, for each row $r\in\mathfrak{r}$, there exists
some $s\in\mathfrak{s}$ such that $r[a]=s[\sigma(a)]$ for every $a\in X$, that
is, iff the inclusion $\mathfrak{r}[X]\subseteq\mathfrak{s}[\sigma(X)]$ holds.
If the map $\sigma$ is given in the input, we say that $X$ is the dependency.
Such an inclusion dependency then is _maximal_ if the set $X$ is maximal among
all INDs for $\mathfrak{r}$ and $\mathfrak{s}$. For the general case, we
define a partial order on the pairs $(X,\sigma)$. We say that
$(X,\sigma)\preccurlyeq(X^{\prime},\sigma^{\prime})$ holds if $X\subseteq
X^{\prime}$ and $\sigma$ is the restriction of $\sigma^{\prime}$ to $X$. An
inclusion dependency then is _maximal_ if it is an $\preccurlyeq$-maximal
element among the inclusion dependencies between $\mathfrak{r}$ and
$\mathfrak{s}$. Observe that the inclusion dependencies are indeed downward
closed with respect to $\preccurlyeq$. However, it may happen that
$(X,\sigma)$ and $(X^{\prime},\sigma^{\prime})$ are both maximal although
$X^{\prime}\subsetneq X$ is a strict subset.

###  2.3 Parameterized Complexity

The central idea of the _parameterized complexity_ of a decision problem is to
identify a quantity of the input, other than its mere size, that captures the
hardness of the problem. The decision problem associated with a language
$\mathrm{\Pi}\subseteq\\{0,1\\}^{*}$ is to determine whether some instance
$I\in\\{0,1\\}^{*}$ is in $\mathrm{\Pi}$. A decision problem is
_parameterized_ if any instance $I$ is additionally augmented with a
_parameter_ $k=k(I)\in\mathbb{N}^{+}$, we thus have
$\mathrm{\Pi}\subseteq\\{0,1\\}^{*}\,{\times}\,\mathbb{N}^{+}$. A
parameterized decision problem $\mathrm{\Pi}$ is _fixed-parameter tractable_
(FPT), if there exists a computable function
$f\colon\mathbb{N}^{+}\to\mathbb{N}^{+}$ and an algorithm that decides any
instance $(I,k)$ in time $f(k)\,{\cdot}\,\textsf{poly}(|I|)$. The complexity
class FPT is the collection of all fixed-parameter tractable problems.

Let $\mathrm{\Pi}$ and $\mathrm{\Pi}^{\prime}$ be two parameterized problems.
A _parameterized reduction_ , or _FPT-reduction_ , from $\mathrm{\Pi}$ to
$\mathrm{\Pi}^{\prime}$ is an algorithm running in time
$f(k)\cdot\textsf{poly}(|I|)$ on instances $(I,k)$, which outputs some
instance $(I^{\prime},k^{\prime})$ such that $k^{\prime}\leq g(k)$ for some
computable function $g\colon\mathbb{N}^{+}\to\mathbb{N}^{+}$, and
$(I,k)\in\mathrm{\Pi}$ holds if and only if
$(I^{\prime},k^{\prime})\in\mathrm{\Pi}^{\prime}$ does. Due to the time bound,
we have $|I^{\prime}|\leq f(k)\,\textsf{poly}(|I|)$. If there is also an FPT-
reduction from $\mathrm{\Pi}^{\prime}$ to $\mathrm{\Pi}$, we say that the
problems are _FPT-equivalent_. A notable special case of FPT-reductions are
polynomial many-one reductions that preserve the parameter, meaning
$k^{\prime}=k$.

Parameterized reductions give rise to the so-called W-_hierarchy_ of
complexity classes. We use one of several equivalent definitions involving
(mainly) Boolean formulas. However, first consider the Independent Set problem
on graphs parameterized by the size of the sought solution. The class
$\textsf{W}[1]$ is the collection of all parameterized problems that admit a
parameterized reduction to Independent Set. For some positive integer $t$, a
Boolean formula is _$t$ -normalized_ if it is a conjunction of disjunctions of
conjunctions of disjunctions (and so on) of literals with $t\hskip
1.00006pt{-}\hskip 1.00006pt{1}$ alternations or, equivalently, $t$ levels in
total. The Weighted $t$-normalized Satisfiability problem is to decide, for a
$t$-normalized formula $\varphi$ and a positive integer $k$, whether $\varphi$
admits a satisfying assignment of Hamming weight $k$, that is, with (exactly)
$k$ variables set to true. Here, $k$ is the parameter. For every $t\geq 2$,
$\textsf{W}[t]$ is the class of all problems reducible to Weighted
$t$-normalized Satisfiability.222The definition via normalized formulas comes
with an inconsistency at $t=1$. A $1$-normalized formula is a single
conjunctive clause, the associated weighted satisfiability problem is
trivially seen to be in P and thus in FPT.  The classes
$\textsf{FPT}\subseteq\textsf{W}[1]\subseteq\textsf{W}[2]\subseteq\dots$ form
an ascending hierarchy. All inclusion are conjectured to be strict, which is
however still unproven.

###  2.4 Enumeration Complexity

_Enumeration_ is the task of compiling and outputting a list of all solutions
to a computational problem without repetitions. Note that this is different
from a counting problem, which asks for the mere number of solutions. More
formally, an _enumeration problem_ is a function
$\mathrm{\Pi}\colon\\{0,1\\}^{*}\to\mathcal{P}(\\{0,1\\}^{*})$ such that, for
all instances $I\in\\{0,1\\}^{*}$, the set of _solutions_ $\mathrm{\Pi}(I)$ is
finite. An algorithm solving this problem needs to output, on input $I$, all
elements of $\mathrm{\Pi}(I)$ exactly once. We do not impose any order on the
output. We focus on the enumeration of minimal hitting sets, that is,
$\mathrm{\Pi}\colon(V,\mathcal{H})\mapsto\operatorname{Tr}(\mathcal{H})$.

An _output-polynomial_ algorithm runs in time polynomial in the combined input
and output size $N=|V|+|\mathcal{H}|+|\operatorname{Tr}(\mathcal{H})|$. A
(seemingly) stronger requirement is an _incremental polynomial_ algorithm,
generating the solutions in such a way that the $i$-th _delay_ , the time
between the $(i\hskip 1.00006pt{-}\hskip 1.00006pt{1})$-st and $i$-th output,
is bounded by $\textsf{poly}(|V|,|\mathcal{H}|,i)$. This includes the
_preprocessing time_ until the first solution arrives ($i=1$) as well as the
_postprocessing time_ between the last solution and termination
($i=|\operatorname{Tr}(\mathcal{H})|\,{+}\,1$). The strongest form of output-
efficiency is that of _polynomial delay_ , where the delay is universally
bounded by $\textsf{poly}(|V|,|\mathcal{H}|)$. There is currently no output-
polynomial algorithm known for the transversal hypergraph problem, but its
existence would immediately imply also an incremental polynomial algorithm
[4].

Arguably the most restrictive way to relate enumeration problems are
parsimonious reductions. The concept is closely related but should not be
confused with the homonymous class of reductions for counting problems [9]. A
_parsimonious reduction_ from enumeration problem $\mathrm{\Pi}$ to
$\mathrm{\Pi}^{\prime}$ is a pair of polynomial time computable functions
$f\colon\\{0,1\\}^{*}\to\\{0,1\\}^{*}$ and
$g\colon(\\{0,1\\}^{*})^{2}\to\\{0,1\\}^{*}$ such that, for any instance
$I\in\\{0,1\\}^{*}$, $g(I,\cdot)$ is a bijection from
$\mathrm{\Pi}^{\prime}(f(I))$ to $\mathrm{\Pi}(I)$. The behavior of
$g(I,\cdot)$ on $\\{0,1\\}^{*}{\setminus}\mathrm{\Pi}^{\prime}(f(I))$ is
irrelevant. Intuitively, any enumeration algorithm for $\mathrm{\Pi}^{\prime}$
can then be turned into one for $\mathrm{\Pi}$ by first mapping the input $I$
to $f(I)$ and translating the solutions back via $g$. 5 establishes a
parsimonious reduction from the enumeration of minimal UCCs to the transversal
hypergraph problem with $f\colon(R,\mathfrak{r})\mapsto(R,\mathcal{D})$ and
$g((R,\mathfrak{r}),\cdot)$ being the identity over subsets of $R$.

##  3 Unique Column Combinations and Functional Dependencies

Theoreticians as well as practitioners in data profiling and database design
are frequently confronted with the task of finding a small collection of items
that has a non-empty intersection with each member of a prescribed family of
sets, see [1, 17, 18, 34, 37]. They thus aim to solve instances of the hitting
set problem. In this section, we show that this encounter is inevitable in the
sense that detecting a small unique column combination or functional
dependency in a relational database is the same as finding a hitting set in a
hypergraph. Even more so, this equivalence extends to enumeration. We show
that the associated discovery problems of finding all UCCs or FDs is indeed
the same as enumerating all hitting sets.

We first formally define the respective decision and enumeration problems. The
decision versions are always parameterized by the solution size. We then order
them in a (seemingly) ascending chain via parameterized reductions. However,
the start and end points of this chain will turn out to be FPT-equivalent,
settling the complexity of the problems involved as complete for the
parameterized complexity class $\textsf{W}[2]$. We then also show the
equivalence of the corresponding enumeration problems under parsimonious
reductions.

###  3.1 Problem Definitions

Recall the definitions of hitting sets as well as unique column combinations
and functional dependencies from Sections 2.1 and 2.2. We are interested in
the parameterized complexity of the associated cardinality-constrained
decision problems. The constraint always serves as the parameter.

Hitting Set

Instance:

A hypergraph $(V,\mathcal{H})$ and a non-negative integer $k$.

Parameter:

The non-negative integer $k$.

Decision:

Is there a set $T\subseteq V$ of vertices with cardinality $|T|=k$

such that $T$ is a hitting set for $\mathcal{H}$?

Note that if $k>|V|$, then the answer to the decision problem is trivially
false; otherwise, there is no difference between deciding the existence of a
transversal with _at most_ or _exactly_ $k$ elements since every superset of a
hitting set is again a hitting set. We ignore the special case of a too large
$k$ since parameterized complexity is primarily concerned with the situation
that the parameter is much smaller than the input size. The unparameterized
Hitting Set problem is one of Karp’s initial 21 NP-complete problems [35]. In
fact, its minimization variant–to compute the minimum size of any hitting
set–is even NP-hard to approximate within a factor of $(1-\varepsilon)\ln|V|$
for any $\varepsilon>0$ [19]. The parameterized variant defined above is the
prototypical $\textsf{W}[2]$-complete problem [23].

The corresponding enumeration problem broadens the notion of a “small”
solution, namely, the task is now to list all _inclusion-wise minimal_ hitting
sets, that is, the edges of the transversal hypergraph
$\operatorname{Tr}(\mathcal{H})$. All other hitting sets can be trivially
obtained from the minimal ones by arbitrarily adding more vertices.

Transversal Hypergraph

Instance:

A hypergraph $(V,\mathcal{H})$.

Enumeration:

List all edges of $\operatorname{Tr}(\mathcal{H})$.

Let $N=|\mathcal{H}|+|\operatorname{Tr}(\mathcal{H})|+|V|$ denote the combined
input and output size, Fredman and Kachiyan’s algorithm solves Transversal
Hypergraph in time $N^{\operatorname{O}(\nicefrac{{\log N}}{{\log\log N}})}$
[28].

We generalize the problem to the enumeration of minimal hitting sets for
multiple input hypergraphs simultaneously. We do not prescribe any order in
which the hypergraphs are processed. However, we want to be able to quickly
tell to which input a solution belongs. For this, let
$\operatorname{Tr}(\mathcal{H})\hskip 1.00006pt\dot{\cup}\hskip
1.00006pt\operatorname{Tr}(\mathcal{G})$ denote the disjoint union of the
transversal hypergraphs of $(V,\mathcal{H})$ and $(W,\mathcal{G})$ with the
additional requirement that the union is encoded in such a way that, for any
$T\in\operatorname{Tr}(\mathcal{H})\hskip 1.00006pt\dot{\cup}\hskip
1.00006pt\operatorname{Tr}(\mathcal{G})$, the containment
$T\in\operatorname{Tr}(\mathcal{H})$ is decidable in time
$\textsf{poly}(|V|,|W|,|\mathcal{H}|,|\mathcal{G}|)$, independently of the
sizes $|\operatorname{Tr}(\mathcal{H})|$ and
$|\operatorname{Tr}(\mathcal{G})|$.

Transversal Hypergraph Union

Instance:

A $d$-tuple of hypergraphs
$(\mathcal{H}_{1},\mathcal{H}_{2},\dots,\mathcal{H}_{d})$.

Enumeration:

List all edges of
$\operatorname{Tr}(\mathcal{H}_{1})\,\dot{\cup}\,\operatorname{Tr}(\mathcal{H}_{2})\,\dot{\cup}\,\dots\,\dot{\cup}\,\operatorname{Tr}(\mathcal{H}_{d})$.

We now define the detection and discovery problems of multi-column
dependencies in relational databases, again starting with the cardinality-
constraint decision problems.

Unique Column Combination

Instance:

A relational database $\mathfrak{r}$ over schema $R$

and a non-negative integer $k$.

Parameter:

The non-negative integer $k$.

Decision:

Is there a set $U\subseteq R$ of attributes with cardinality $|U|=k$

such that $U$ is a unique column combination in $\mathfrak{r}$?

The minimization variant of Unique Column Combination is NP-hard [45].

Enumerate Minimal UCCs

Instance:

A relational database $\mathfrak{r}$.

Enumeration:

List all minimal unique column combinations of $\mathfrak{r}$.

For functional dependencies, we define two variants of the decision problem
that slightly differ in the given input. The first one fixes the right-hand
side of the desired dependency, while the second one asks for an FD with
arbitrary RHS holding in the database. While their parameterized complexity
will turn out to be the same, there are some differences in their discovery.

Functional Dependencyfixed RHS

Instance:

A relational database $\mathfrak{r}$ over schema $R$, an attribute $a\in R$,

and a non-negative integer $k$.

Parameter:

The non-negative integer $k$.

Decision:

Is there a set $X\subseteq R{\setminus}\\{a\\}$ with $|X|=k$ such that

the functional dependency $X\,{\to}\,a$ holds in $\mathfrak{r}$?

Functional Dependency

Instance:

A relational database $\mathfrak{r}$ over schema $R$

and a non-negative integer $k$.

Parameter:

The non-negative integer $k$.

Decision:

Is there a set $X\subseteq R$ with $|X|=k$ and an attribute $a\in
R{\setminus}X$

such that the functional dependency $X\,{\to}\,a$ holds in $\mathfrak{r}$?

The unparameterized variant of Functional Dependencyfixed RHS is NP-complete
even if the number of admissible values for each attribute is at most $2$
[18]. It is the same to ask for a functional dependency whose left-hand side
is of size at most $k$; unless of course $k\geq|R|$ since then no non-trivial
FD adheres to the (exact) size constraint. Again, we ignore this issue.

Recall that we say that a functional dependency $X\,{\to}\,a$ is minimal if
its LHS $X$ is inclusion-wise minimal among all $X^{\prime}\subseteq R$ such
that $X^{\prime}\,{\to}\,a$ is valid.

Enumerate Minimal FDsfixed RHS

Instance:

A relational database $\mathfrak{r}$ over schema $R$ and an attribute $a\in
R$.

Enumeration:

List all minimal, valid, non-trivial functional dependencies of $\mathfrak{r}$

with right-hand side $a$.

Enumerate Minimal FDs

Instance:

A relational database $\mathfrak{r}$.

Enumeration:

List all minimal, valid, non-trivial functional dependencies of
$\mathfrak{r}$.

Enumerate Minimal UCCs and Enumerate Minimal FDs can be solved in output-
polynomial time (in incremental polynomial time or with polynomial delay,
respectively) if and only if this is possible for the Transversal Hypergraph
problem [24].

###  3.2 Detection

Next, we prove the parameterized complexity of the detection problems for
unique column combinations and functional dependencies. We start by showing
the $\textsf{W}[2]$-hardness of Unique Column Combination. The following lemma
was obtained independently by Froese et al. [29].

(a)

(b)

Figure 3: Illustration of the reductions in Lemmas 6 and 7. (a) An instance of
Hitting Set and the equivalent instance of Unique Column Combination. (b) An
instance $\mathfrak{r}$ of Functional Dependencyfixed RHS with fixed right-
hand side $a$ and the equivalent instance $\mathfrak{r}^{\prime}$ of
Functional Dependency. The functional dependencies $ab\,{\to}\,d$ holds in
$\mathfrak{r}$, but not in $\mathfrak{r}^{\prime}$.

######  Lemma 6.

There is a parameterized reduction from _Hitting Set_ to the _Unique Column
Combination_ problem.

###### Proof.

Let $(V,\mathcal{H})$ be the hypergraph given in the input to the Hitting Set
problem. Without loss of generality, we can assume it to be Sperner;
otherwise, we replace it by its minimization $\min(\mathcal{H})$ (in quadratic
time). Observe that $\min(\mathcal{H})$ has a hitting set of size at most $k$
iff $\mathcal{H}$ has one. We construct from $\mathcal{H}$ in polynomial time
a database $\mathfrak{r}$ over schema $V$ such that the minimal difference
sets of $\mathfrak{r}$ are the edges of $\mathcal{H}$. The lemma then follows
immediately from 5. In particular, since 5 transfers solutions, the parameter
$k$ is preserved by the reduction.

Let $E_{1},E_{2},\dots,E_{m}$ be the edges of $\mathcal{H}$. We take the
integers $0,1,\dots,m$ as the admissible values for all attributes in $V$. As
rows, we first add the all-zero tuple $r_{0}=(0)_{a\in V}$ to $\mathfrak{r}$.
For each $i\in[m]$, we also add the record $r_{i}$ defined as

$r_{i}[a]=\begin{cases}i,&\text{if }a\in E_{i};\\\
0,&\text{otherwise.}\end{cases}$

See Figure 3(a) for an illustration. Clearly, $\mathfrak{r}$ can be computed
in linear time.

Any edge $E_{i}$ is a difference set in $\mathfrak{r}$, namely, that of the
pair $(r_{0},r_{i})$. Any other difference set must come from a pair
$(r_{i},r_{j})$ with $1\leq i<j\leq m$. It is easy to see that those rows
disagree in $E_{i}\cup E_{j}$, which is not minimal. Since $\mathcal{H}$ is
Sperner, it contains exactly the minimal difference sets of $\mathfrak{r}$. ∎

The next two reductions are straightforward due to the similar structures of
uniques and functional dependencies. While a UCC separates any pair of rows,
an FD $X\,{\to}\,a$ needs to distinguish only those with $r[a]\neq s[a]$.

######  Lemma 7.

There are parameterized reductions

  1. 1.

from _Unique Column Combination_

to _Functional Dependency fixed RHS_;

  2. 2.

from _Functional Dependency fixed RHS_

to _Functional Dependency_.

###### Proof.

To prove Item 1, we add a single unique column to the database and fix it as
the right-hand side of the sought functional dependency. Let
$\mathfrak{r}=\\{r_{1},r_{2},\dots,r_{|\mathfrak{r}|}\\}$ be a database over
schema $R$, and $a$ an attribute not previously in $R$. We construct
$\mathfrak{r}^{\prime}$ over $R\cup\\{a\\}$ by adding, for each $r_{i}$, the
row $r^{\prime}_{i}$ defined by $r^{\prime}_{i}[R]=r_{i}[R]$ and
$r^{\prime}_{i}[a]=i$. The reduction maps an instance $(\mathfrak{r},R,k)$ of
Unique Column Combination to the instance
$(\mathfrak{r}^{\prime},R\cup\\{a\\},a,k)$ of Functional Dependencyfixed RHS.
Since, for any two distinct rows
$r^{\prime}_{i},r^{\prime}_{j}\in\mathfrak{r}^{\prime}$, $i\neq j$, we have
$r^{\prime}_{i}[a]\neq r^{\prime}_{j}[a]$, the left-hand sides of the non-
trivial, valid FDs $X\,{\to}\,a$ in $\mathfrak{r}^{\prime}$ are in one-to-one
correspondence to the UCCs in $\mathfrak{r}$.

To reduce Functional Dependencyfixed RHS to Functional Dependency, we need to
mask all “unwanted” FDs with RHS different from the fixed attribute $a$. See
Figure 3(b) for an example. Let again $\mathfrak{r}$ be the input database
over $R$. To construct the resulting database $\mathfrak{r}^{\prime}$ over the
same schema $R$, we take all rows from $\mathfrak{r}$ and add $|R|-1$ new
ones. Fix an arbitrary record $r^{*}\in\mathfrak{r}$ and let ${\times}$ be a
new symbol that does not previously appear as a value. For each attribute
$b\in R{\setminus}\\{a\\}$, we add the row $r_{b}$ satisfying
$r_{b}[R{\setminus}\\{b\\}]=r^{*}[R{\setminus}\\{b\\}]$ and
$r_{b}[b]={\times}$. The rows $r^{*}$ and $r_{b}$ now witness that any non-
trivial FD $X\,{\to}\,b$ fails in $\mathfrak{r}^{\prime}$.

It is left to prove that $X\,{\to}\,a$ holds in $\mathfrak{r}$ if and only if
it holds in $\mathfrak{r}^{\prime}$. Evidently, any valid FD in
$\mathfrak{r}^{\prime}$ is also valid in the subset $\mathfrak{r}$. Suppose
$X\,{\to}\,a$ holds in $\mathfrak{r}$ and let rows
$r,s\in\mathfrak{r}^{\prime}$ be such that $r[a]\neq s[a]$. The only case
where the conclusion $r[X]\neq s[X]$ may possibly be in doubt is if
$r\in\mathfrak{r}^{\prime}{\setminus}\mathfrak{r}$ and $s\in\mathfrak{r}$ (all
new rows in $\mathfrak{r}^{\prime}{\setminus}\mathfrak{r}$ agree on $a$).
Hence, $r=r_{b}$ for some $b\neq a$. If $b\in X$, the new value ${\times}$
appears in the projection $r[X]$ but not in $s[X]$; otherwise, we have
$r[X]=r^{*}[X]$. Since $X\,{\to}\,a$ holds for the pair
$r^{*},s\in\mathfrak{r}$, the relation $r[X]=r^{*}[X]\neq s[X]$ follows. ∎

The next lemma proves that every instance of the unrestricted Functional
Dependency problem can be expressed as an equivalent Boolean formula in
conjunctive normal form. Since CNF formulas are exactly the $2$-normalized
ones, we obtain a reduction to Weighted $2$-normalized Satisfiability. This is
the main result of this section.

######  Lemma 8.

There is a parameterized reduction from _Functional Dependency_ to the
_Weighted $2$-normalized Satisfiability_ problem.

###### Proof.

Given a database $\mathfrak{r}$ over $R$, we derive a CNF formula that has a
satisfying assignment of Hamming weight $k\hskip 1.00006pt{+}\hskip
1.00006pt{1}$ if and only if there is a non-trivial FD with left-hand side of
size $k$ that holds in $\mathfrak{r}$. We use two types of variables
distinguished by their semantic purpose, $\texttt{Var}_{LHS}=\\{x_{a}\mid a\in
R\\}$ and $\texttt{Var}_{RHS}=\\{y_{a}\mid a\in R\\}$. Some variable $x_{a}$
from $\texttt{Var}_{LHS}$ being set to true corresponds to the attribute $a$
appearing on the left-hand side of the sought functional dependency; for
$y_{a}$ from $\texttt{Var}_{RHS}$, this means the attribute is the right-hand
side.

We start with the RHS. It might be tempting to enforce that any satisfying
assignment chooses exactly one variable from $\texttt{Var}_{RHS}$. We prove
below that this is not necessary and forgoing the $\operatorname{O}(|R|^{2})$
clauses representing this constraint allows for a (slightly) leaner
construction. However, we do have to ensure that at least one variable from
$\texttt{Var}_{RHS}$ is set to true and the corresponding one in
$\texttt{Var}_{LHS}$ is false. This is done by the clauses
$C_{RHS}=\bigvee_{y_{a}\in\texttt{Var}_{RHS}}y_{a}$ and $C_{a}=\neg
y_{a}\vee\neg x_{a}$ for each $a\in R$. The subformula $\varphi_{RHS}$ is
their conjunction.

We now model the LHS. For any attribute $a\in R$ and rows
$r,s\in\mathfrak{r}$, let

$C_{a,r,s}=\neg y_{a}\vee\bigvee_{\begin{subarray}{c}b\in
R{\setminus}\\{a\\}\\\\[0.875pt] r[b]\neq s[b]\end{subarray}}x_{b}.$

Intuitively, the clause $C_{a,r,s}$ represents the fact that if $X\,{\to}\,a$
is a valid, non-trivial FD, then $X$ has to contain at least one attribute
$b$, different from $a$, such that $r[b]\neq s[b]$. From these clauses, we
assemble the subformula

$\varphi_{a}=\bigwedge_{\begin{subarray}{c}r,s\in\mathfrak{r}\\\\[0.875pt]
r[a]\neq s[a]\end{subarray}}C_{a,r,s}.$

The output of our reduction is the formula
$\varphi=\varphi_{RHS}\wedge\bigwedge_{a\in R}\varphi_{a}$. Indeed, $\varphi$
is in conjunctive normal form and has $\operatorname{O}(|R|\hskip
1.00006pt|\mathfrak{r}|^{2})$ clauses with at most $|R|$ literals each. An
encoding of $\varphi$ is computable in time linear in its size.

Regarding the correctness of the reduction, recall that we claimed $\varphi$
to have a weight $k\hskip 1.00006pt{+}\hskip 1.00006pt{1}$ satisfying
assignment iff a non-trivial functional dependency $X\,{\to}\,a$ of size $k$
holds in $\mathfrak{r}$. Suppose that the latter is true. We show that setting
the variable $y_{a}$ as well as all $x_{b}$ with $b\in X$ to true (and all
others to false) satisfies $\varphi$. Note that the assignment automatically
satisfies $C_{RHS}$ and all $C_{b,r,s}$ with $b\neq a$. We are left with the
subformula $\varphi_{a}$ containing the clauses $C_{a,r,s}$ for row pairs with
$r[a]\neq s[a]$. To distinguish these pairs, the LHS $X$ includes, for each of
them, some attribute $b\in R{\setminus}\\{a\\}$ such that $r[b]\neq s[b]$.
Clause $C_{a,r,s}$ is then satisfied by the corresponding literal $x_{b}$.

For the other direction, we identify assignments with the variables they set
to true. Let $A\subseteq\texttt{Var}_{LHS}\cup\texttt{Var}_{RHS}$ be an
assignment of Hamming weight $|A|=k\hskip 1.00006pt{+}\hskip 1.00006pt{1}$
that satisfies $\varphi$. The assignment induces two subsets of the schema
$R$, namely, $X=\\{a\in R\mid x_{a}\in A\cap\texttt{Var}_{LHS}\\}$ and
$Y=\\{a\in R\mid y_{a}\in A\cap\texttt{Var}_{RHS}\\}$. Due to the clause
$C_{RHS}$, $Y$ is non-empty and $X$ contains at most $k$ elements. Moreover,
$X$ and $Y$ are disjoint as the $C_{a}$ are all satisfied. We say that the
generalized functional dependency $X\,{\to}\,Y$ holds in a database if
$X\,{\to}\,a$ holds for every $a\in Y$. It is clearly enough to show that
$X\,{\to}\,Y$ indeed holds in $\mathfrak{r}$.

Assume $X\,{\to}\,a$ fails for some $a\in Y$. This is witnessed by a pair of
rows $r,s\in\mathfrak{r}$ with $r[X]=s[X]$ but $r[a]\neq s[a]$, whence the
clause $C_{a,r,s}$ is present in $\varphi$. Since $y_{a}\in A$ is in the
assignment, the literal $\neg y_{a}$ evaluates to false. Also, as $X$ is
disjoint from the difference set $\\{b\in R{\setminus}\\{a\\}\mid r[b]\neq
s[b]\\}$, no other literal satisfies $C_{a,r,s}$, which is a contradiction. ∎

We have established a chain of parameterized reductions between the dependency
detection problems of unique column combinations and functional dependencies.
The fact that the endpoints Hitting Set and Weighted $2$-normalized
Satisfiability are both $\textsf{W}[2]$-complete shows that all of the
problems are, this completes the proof of 1.

###  3.3 Approximation and Discovery

Our reductions have implications beyond the scope of parameterized complexity.
Observe that the transformations in Lemmas 6 and 7 can be computed in
polynomial time and preserve approximations with respect to the solution size
$k$ or $|X|$, respectively. Also, recall that the minimization version of
Hitting Set is NP-hard to approximate within a factor of
$(1-\varepsilon)\ln|V|$ for every $\varepsilon>0$ [19]. As a consequence, the
minimization versions of Unique Column Combination, Functional Dependencyfixed
RHS, and Functional Dependency all inherit the same hardness of approximation.
Previously, an approximation-preserving reduction was known only for the
Unique Column Combination problem, starting from Set Cover [2].

Rather than approximating minimum solutions, we are mainly interested in the
discovery of minimal dependencies in databases. Traditionally, enumeration has
been studied via embedded decision problems that are different from those
defined in Section 3.1. Instead, the Transversal Hypergraph problem
(enumerating minimal hitting sets) has been associated with the problem of
deciding for two hypergraphs $\mathcal{H}$ and $\mathcal{G}$ whether
$\mathcal{G}=\operatorname{Tr}(\mathcal{H})$ or, equivalently,
$\mathcal{H}=\operatorname{Tr}(\mathcal{G})$, called the Dual problem.
Enumerate Minimal UCCs analogously corresponds to decide for a database
$\mathfrak{r}$ and hypergraph $\mathcal{H}$, whether $\mathcal{H}$ consists of
all minimal uniques of $\mathfrak{r}$. Intuitively, this formalizes the
decision whether an enumeration algorithm has found all solutions.

Both decision problems are in coNP and it was proven by Eiter and Gottlob [24]
that they are many-one equivalent. Using a lifting result by Bioch and Ibaraki
[4], this shows that minimal hitting sets can be enumerated in output-
polynomial time if and only if minimal UCCs can, which is the case if and only
if Dual is in P. Such an equivalence is theoretically appealing and has lead
to the quasi-output-polynomial upper bound on the running time of hitting
set/UCC enumeration that is currently the best known [28]. The connection to
enumeration has also inspired the intriguing result that Dual is likely not
coNP-hard as it can be solved in polynomial time when given access to
$\operatorname{O}(\nicefrac{{\log^{2}N}}{{\log\log N}})$ suitably guessed
nondeterministic bits [3, 25], where $N$ denotes the total input size of the
pair $(\mathcal{H},\mathcal{G})$. There are classes of hypergraphs for which
Dual is indeed in P, see for example [8, 20, 25, 43], or at least in FPT with
respect to certain structural parameters [27]. For a much more thorough
overview of decision problems associated with enumeration, see the recent work
by Creignou et al. [15].

Unfortunately, the approach described above holds only limited value when it
comes to designing practical algorithms. Imagine an implementation of the
discovery of minimal UCCs of a database $\mathfrak{r}$ via repeated checks
whether the hypergraph $\mathcal{H}$ of previously found solutions is already
complete. Such an algorithm is bound to use an amount of memory that is
exponential in the size of $\mathfrak{r}$. This is due to the fact that some
databases have exponentially many minimal solutions and the decision
subroutine at least has to read all of $\mathcal{H}$. Note that such a large
memory consumption is not at all necessary as there are algorithms known for
Transversal Hypergraph whose space complexity is only linear in the input size
[27, 39]. In fact, enumeration algorithms are often analyzed not only with
respect to their running time, but also in terms of space consumption, see [9,
14]. For data profiling problems like Enumerate Minimal UCCs on the other
hand, space-efficient algorithms have only recently started to received some
attention [5, 6, 36].

In the following, we simplify and at the same time extend the above
equivalences making them usable in practice, namely, we prove 3. It states the
existence of parsimonious reductions, in both directions, that relate the
input instances directly on the level of the enumeration problems, without
decision problems as intermediaries. This way, we characterize the enumeration
complexity of unique column combinations as well as functional dependencies,
both with fixed and arbitrary right-hand side. Curiously, our insights on
enumeration also stem from the study of decision problems, however, the
results are entirely lifted.

The reductions between the decision problems Hitting Set, Unique Column
Combination, Functional Dependencyfixed RHS, and Functional Dependency (in
that order) for _minimum_ dependencies described in Lemmas 6 and 7 are all
built on bijective correspondences between the solutions. The running times of
the reductions are polynomial and independent of the given budget $k$.
Finally, the mappings of the solution spaces also preserve set inclusions.
This means, the same input transformations applied to the discovery of
_minimal_ dependencies are in fact parsimonious reductions from Transversal
Hypergraph to Enumerate Minimal UCCs and further to Enumerate Minimal
FDs/FDsfixed RHS. Regarding the inverse direction, 5 shows that the
enumeration of UCCs is at most as hard as that of hitting sets, that is,
Enumerate Minimal UCCs and Transversal Hypergraph are equivalent. It is worth
noting that the parsimonious reductions increase the size of the instances at
most by a polynomial factor (in most case a constant one) _in the input size
only_ and therefore transfer the space complexity of any enumeration algorithm
from one side to the other.

To complete the proof of 3, we still need the following lemma that
characterizes the complexity of functional dependency discovery in terms of
the Transversal Hypergraph Union problem.

######  Lemma 9.

The problems _Enumerate Minimal FDs_ and _Transversal Hypergraph Union_ are
equivalent under parsimonious reductions. Moreover, there is a parsimonious
reduction from _Enumerate Minimal FDs fixed RHS_ to _Transversal Hypergraph_.

###### Proof.

This proof uses techniques that already helped to establish the previous
lemmas of this section. Let $\mathfrak{r}$ be a database over schema $R$,
$a\in R$ some attribute, $r,s\in\mathfrak{r}$ two rows with $r[a]\neq s[a]$.
Recall that their difference set is $D(r,s)=\\{b\in R\mid r[b]\neq s[b]\\}$.
We define their _punctured difference set_ to be $D(r,s){\setminus}\\{a\\}$.
It is implicit in the proof of Lemma 8 – and easy to verify from the
definition of functional dependencies – that a set $X\subseteq
R{\setminus}\\{a\\}$ is the left-hand side of a valid, minimal, non-trivial FD
$X\,{\to}\,a$ if and only if it is a minimal hitting set for the hypergraph
$\mathcal{D}_{a}=\\{D(r,s){\setminus}\\{a\\}\mid
r,s\in\mathfrak{r};r[a]\,{\neq}\,s[a]\\}$ of punctured difference sets.

Transforming the input database $\mathfrak{r}$ over schema
$R=\\{a_{1},\dots,a_{|R|}\\}$ into the $|R|$ hypergraphs
$\mathcal{D}_{a_{1}},\dots,\mathcal{D}_{a_{|R|}}$ is a parsimonious reduction
from the Enumerate Minimal FDs problem to Transversal Hypergraph Union. In the
same fashion, fixing the desired right-hand side in the input reduces
Enumerate Minimal FDsfixed RHS to Transversal Hypergraph.

Figure 4: Illustration of Lemma 9. The three hypergraphs
$\mathcal{H}_{1},\mathcal{H}_{2},\mathcal{H}_{3}$ on the vertex set $V$ are on
the left and the equivalent database $\mathfrak{r}$ is on the right. The
hypergraphs $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ share the edge
$\\{b,c\\}$, but this results in two rows $r_{2}$ and $r_{3}$. The
corresponding transversal hypergraphs are
$\operatorname{Tr}(\mathcal{H}_{1})=\\{\\{a,c\\},\\{b\\}\\}$,
$\operatorname{Tr}(\mathcal{H}_{2})=\\{\\{b\\},\\{c,b\\},\\{c,e\\}\\}$, and
$\operatorname{Tr}(\mathcal{H}_{3})=\\{\\{a,b\\},\\{b,c,d\\},\\{b,c,e\\}\\}$.
The functional dependencies $b\,{\to}\,x_{1}$ and $b\,{\to}\,x_{2}$ indeed
hold in $\mathfrak{r}$, and adding the attribute $a$ gives $ab\,{\to}\,x_{3}$.
The rows in the last block eliminate all non-trivial functional dependencies
$X\,{\to}\,v$ with $v\in V$.

The opposite reduction is the main part of the lemma. We are given hypergraphs
$\mathcal{H}_{1},\dots,\mathcal{H}_{d}$, without loss of generality all on the
same vertex set $V\\!$, and we need to compute some database $\mathfrak{r}$
such that its valid, non-trivial functional dependencies are in one-to-one
correspondence with the hitting sets of the $\mathcal{H}_{i}$. An example can
be seen in Figure 4. As the relational schema, we take the set
$R=V\cup\\{x_{1},\dots,x_{d}\\}$, where the $x_{i}$ are attributes not
previously appearing in $V\\!$. The construction of $\mathfrak{r}$ starts
similarly to Lemma 6. We first add the all-zeros row $r_{0}$ (with
$r_{0}[a]=0$ for every $a\in R$). Let $m=\sum_{i=1}^{d}|\mathcal{H}_{i}|$ be
the total number of edges and $E_{1},E_{2},\dots,E_{m}$ an arbitrary numbering
of them. Note that if the same set of vertices is an edge of multiple
hypergraphs, it appears in the list with that multiplicity. For every edge
$E_{j}$, we add the following row $r_{j}$,

$r_{j}[a]=\begin{cases}j,&\text{if }a\in E_{j};\\\ 0,&\text{if }a\in
V{\setminus}E_{j};\\\ 1,&\text{if }a=x_{i}\text{ such that
}E_{j}\in\mathcal{H}_{i};\\\ 0,&\text{otherwise.}\end{cases}$

In other words, the subtuple $r_{j}[V]$ is the characteristic vector of
$E_{j}$ only that its non-zero entries are $j$ instead of $1$; the subtuple
$r_{j}[\\{x_{1},\dots,x_{d}\\}]$ has exactly one $1$ at the position
corresponding to the hypergraph containing $E_{j}$. The remaining construction
of database $\mathfrak{r}$ uses an idea of Lemma 7 2. Let $\times$ be a new
symbol. For every vertex $v\in V$, we add the row $r_{v}$ with
$r_{v}[v]=\times$ and $r_{v}[a]=0$ for all other attributes $a\in
R{\setminus}\\{v\\}$. The database $\mathfrak{r}$ can be obtained in time
$\textsf{poly}(m,|V|)$.

We claim that the minimal, valid, non-trivial functional dependencies of
$\mathfrak{r}$ are exactly those having the form $T\,{\to}\,x_{i}$ with
$T\in\operatorname{Tr}(\mathcal{H}_{i})$. The existence of a parsimonious
reduction from Transversal Hypergraph Union to Enumerate Minimal FDs easily
follows from that. Let $X\subseteq R$ and $a\in R{\setminus}X$ be such that
the FD $X\,{\to}\,a$ holds in $\mathfrak{r}$ and is minimal. For any $v\in V$,
the rows $r_{0}$ and $r_{v}$ differ only in attribute $v$, therefore $v$ is
not the right-hand side of any non-trivial FD, whence $a=x_{i}$ for some
$1\leq i\leq d$. As seen above, the set $X$ must be a minimal transversal of
the hypergraph $\mathcal{D}_{x_{i}}=\\{D(r,s){\setminus}\\{a\\}\mid
r,s\in\mathfrak{r};r[x_{i}]\,{\neq}\,s[x_{i}]\\}$. We are left to prove that
$\mathcal{D}_{x_{i}}$ has the same minimal transversals as $\mathcal{H}_{i}$.
Let $r,s\in\mathfrak{r}$ be rows that differ in attribute $x_{i}$, say,
$r[x_{i}]=1$ and $s[x_{i}]=0$. We thus have $r=r_{j}$ for some $1\leq j\leq
m$. The rows $r$ and $s$ share only the value $0$, if any. Therefore,

$D(r,s)=\begin{cases}E_{j}\cup\\{x_{i}\\},&\text{ if }s=r_{0};\\\ E_{j}\cup
E_{k}\cup\\{x_{i},x_{\ell}\\},&\text{ if }s=r_{k}\text{ for
}1\,{\leq}\,k\,{\leq}\,m\text{ such that }E_{k}\in\mathcal{H}_{\ell};\\\
E_{j}\cup\\{x_{i},v\\},&\text{ if }s=r_{v}\text{ for }v\in V\\!.\end{cases}$

In the second case, note that $\ell\neq i$ since $s[x_{i}]=0$. The above
implies that $\mathcal{H}_{i}\subseteq\mathcal{D}_{x_{i}}$; moreover, all
edges in $\mathcal{D}_{x_{i}}{\setminus}\mathcal{H}_{i}$ are supersets of ones
in $\mathcal{H}_{i}$. The respective minimizations
$\min(\mathcal{D}_{x_{i}})=\min(\mathcal{H}_{i})$ are thus equal and, by
duality, also their transversal hypergraphs
$\operatorname{Tr}(\mathcal{D}_{x_{i}})=\operatorname{Tr}(\mathcal{H}_{i})$
are the same. ∎

It is known that Enumerate Minimal FDs can be solved in output-polynomial time
if and only if Transversal Hypergraph can [24], this has been established
along the same lines as discussed in the remarks preceding Lemma 9. Notably,
Eiter and Gottlob additionally presented an alternative construction in the
extended version of [24] that is _almost_ parsimonious. The only condition
they needed to relax is the bijection between the solution spaces. They
transform a database over schema $R$ into some hypergraph
$(R^{2},\mathcal{F})$ such that the majority of its minimal hitting sets
indeed correspond to the functional dependencies with arbitrary right-hand
side. However, $\mathcal{F}$ has some $\operatorname{O}(|R|^{4})$ excess
solutions (that is, polynomially many in the input size only), which do not
have an FD counterpart, but are easily recognizable. We leave it as an open
problem to give a fully parsimonious reduction between the problems. We have
shown above that this is equivalent to encoding the hitting set information of
$|R|$ different hypergraphs into a single one.

##  4 Inclusion Dependencies

We now discuss inclusion dependencies in relational databases. We show that
their detection problem, when parameterized by the solution size, is one of
the first natural problems to be complete for the class $\textsf{W}[3]$. We do
so by proving its FPT-equivalence with the weighted satisfiability problem for
a certain fragment of propositional logic. Later in Section 4.4, we transfer
our results to the discovery of maximal inclusion dependencies.

###  4.1 Problem Definitions

A Boolean formula is _antimonotone_ if it only contains negative literals. We
identify a variable assignment with those variables that are set to true. In
the case of antimonotone formulas, this means that the satisfying assignments
are closed under arbitrarily turning variables to false, that is, taking
subsets. The empty assignment that assigns false to all variables is always
satisfying. Recall that a formula is $3$-normalized if it is a conjunction of
disjunctions of conjunctions of literals or, equivalently, if it is a
conjunctions of subformulas in disjunctive normal form (DNF). An example of an
antimonotone, $3$-normalized formula is

$((\neg x_{1}\wedge\neg x_{2}\wedge\neg x_{4})\vee(\neg x_{3}\wedge\neg
x_{4}))\wedge((\neg x_{1}\wedge\neg x_{3})\vee(\neg x_{2}\wedge\neg
x_{5})\vee(\neg x_{1}\wedge\neg x_{4}\wedge\neg x_{5})).$

This formula admits satisfying assignments of Hamming weight $0$, $1$, and
$2$, but none of larger weight.

The Weighted Antimonotone $3$-normalized Satisfiability problem is the special
case of Weighted $3$-normalized Satisfiability restricted to antimonotone
formulas.

Weighted Antimonotone $3$-normalized Satisfiability (WA$3$NS)

Instance:

An antimonotone, $3$-normalized Boolean formula $\varphi$

and a non-negative integer $k$.

Parameter:

The non-negative integer $k$.

Decision:

Does $\varphi$ admit a satisfying assignment of Hamming weight $k$?

By the above remark, this is the same as asking for an assignment of weight at
least $k$. The Antimonotone Collapse Theorem of Downey and Fellows [21, 22]
implies that the WA$3$NS special case is $\textsf{W}[3]$-complete on its own.

The inclusion-wise maximal satisfying assignments carry the full information
about the collection of all satisfying assignments. It is therefore natural to
define the corresponding enumeration problem as follows.

Enumerate Maximal Satisfying WA$3$NS Assignments

Instance:

An antimonotone, $3$-normalized Boolean formula $\varphi$.

Enumeration:

List all maximal satisfying assignments of $\varphi$.

For inclusion dependencies, the situation is similar. Every subset of a valid
IND is also valid. Asking for a dependency of size exactly $k$ is thus the
same as asking for one of size at least $k$. We define two variants of the
decision problem, similar as we did with functional dependencies. The more
restricted variant requires the two databases to have the same schema with the
identity mapping between columns.

Inclusion DependencyIdentity

Instance:

Two relational databases $\mathfrak{r}$, $\mathfrak{s}$ over schema $R$

and a non-negative integer $k$.

Parameter:

The non-negative integer $k$.

Decision:

Is there a set $X\subseteq R$ with $|X|=k$ such that

$\mathfrak{r}[X]\subseteq\mathfrak{s}[X]$ is an inclusion dependency?

Inclusion Dependency

Instance:

Two relational databases, $\mathfrak{r}$ over schema $R$ and $\mathfrak{s}$
over $S$,

and a non-negative integer $k$.

Parameter:

The non-negative integer $k$.

Decision:

Is there a set $X\subseteq R$ with $|X|=k$ and an injective mapping

$\sigma\colon X\to S$ such that
$\mathfrak{r}[X]\subseteq\mathfrak{s}[\sigma(X)]$ is an inclusion dependency?

The unparameterized variant of the general Inclusion Dependency problem is NP-
complete already for pairs of binary databases [34].

The solutions of Inclusion DependencyIdentity are mere subsets of the
underlying schema, therefore it is clear what we mean by a maximal solution.
The case of the general Inclusion Dependency problem is slightly more
intricate. Recall from Section 2.2 that we say a general inclusion dependency
$(X,\sigma)$ is maximal if there is no other IND
$(X^{\prime},\sigma^{\prime})$ such that $X\subsetneq X^{\prime}$ is a proper
subset and $\sigma$ is the restriction of $\sigma^{\prime}$ to $X$. Note that
the pair $(X^{\prime},\tau)$ with an alternative mapping $\tau$ might still be
a valid inclusion dependency. This leads to the following enumeration
problems.

Enumerate Maximal INDsIdentity

Instance:

Two relational databases $\mathfrak{r}$, $\mathfrak{s}$ over the same schema.

Enumeration:

List all maximal valid inclusion dependencies between $\mathfrak{r}$ and
$\mathfrak{s}$

with the identity mapping between the columns.

Enumerate Maximal INDs

Instance:

Two relational databases $\mathfrak{r}$ and $\mathfrak{s}$.

Enumeration:

List all maximal valid inclusion dependencies between $\mathfrak{r}$ and
$\mathfrak{s}$.

###  4.2 Membership in $W[3]$

We show that both variants of the Inclusion Dependency decision problem are
contained in the class $\textsf{W}[3]$. Recall that the Inclusion
DependencyIdentity problem restricts the input to pairs
$(\mathfrak{r},\mathfrak{s})$ of databases over the same schema and forbids
solutions in which the set of values $\mathfrak{r}[a]$ of one column are
contained in $\mathfrak{s}[b]$ for some other column $b\neq a$. As a first
step, we show (not entirely surprisingly) that this variant is at most as hard
as the general problem.

######  Lemma 10.

There is a parameterized reduction from _Inclusion_ _Dependency Identity_ to
_Inclusion Dependency_.

###### Proof.

Let $\mathfrak{r}$ and $\mathfrak{s}$ be two databases over the schema $R$ and
let $t^{\times}=(\times_{a})_{a\in R}$ be a new row, where the $\times_{a}$
are $|R|$ different symbols none of which are previously used anywhere in
$\mathfrak{r}$ or $\mathfrak{s}$. In the restricted setting, an inclusion
dependency is a set $X\subseteq R$ of columns such that
$\mathfrak{r}[X]\subseteq\mathfrak{s}[X]$. It is easy to see that
$(\mathfrak{r},\mathfrak{s})$ has such an inclusion dependency of size $k$,
for any $k$, if and only if
$(\mathfrak{r}\cup\\{t^{\times}\\},\mathfrak{s}\cup\\{t^{\times}\\})$ has an
inclusion dependency of the same size with an arbitrary mapping between the
columns since $\times_{a}\in\mathfrak{s}[b]$ holds iff $a=b$. The lemma
follows from here. ∎

To demonstrate the membership of the general problem in $\textsf{W}[3]$, we
reduce is to WA$3$NS. Namely, we compute from the two databases an
antimonotone, $3$-normalized formula which has a weight $k$ satisfying
assignment if and only if the databases admit an inclusion dependency of that
cardinality. For this, we use a correspondence between _pairs_ of attributes
and Boolean variables.

######  Lemma 11.

There is a parameterized reduction from _Inclusion Dependency_ to _Weighted
Antimonotone $3$-normalized Satisfiability_.

###### Proof.

Let $R=\\{a_{1},\dots,a_{|R|}\\}$ and $S=\\{b_{1},\dots,b_{|S|}\\}$ be two
schemas. We introduce a Boolean variable $x_{i,j}$ for each pair of attributes
$a_{i}\in R$ and $b_{j}\in S$. We let $\texttt{Var}_{P}$ denote the set of
variables corresponding to a collection $P\subseteq R\times S$ of such pairs.
Consider a subset $X\subseteq R$ together with an injection $\sigma\colon X\to
S$. From this, we construct a truth assignment including the variable
$x_{i,j}$ (setting it to true) iff $a_{i}\in X$ and $\sigma(a_{i})=b_{j}$. The
resulting assignment has weight $|X|$ and the collection of all possible
configurations $(X,\sigma)$ is uniquely described by $\texttt{Var}_{R\times
S}$ and the truth assignments obtained this way. Moreover, these assignments
all satisfy the following antimonotone Boolean formula $\varphi_{map}$.

$\displaystyle\varphi_{map}=\left(\bigwedge_{i=1}^{|R|}\bigwedge_{j=1}^{|S|-1}\bigwedge_{j^{\prime}=j+1}^{|S|}(\neg
x_{i,j}\vee\neg x_{i,j^{\prime}})\right)\ \wedge\
\left(\bigwedge_{j=1}^{|S|}\bigwedge_{i=1}^{|R|-1}\bigwedge_{i^{\prime}=i+1}^{|R|}(\neg
x_{i,j}\vee\neg x_{i^{\prime},j})\right).$

The first half of $\varphi_{map}$ expresses that, for every pair of variables
$x_{i,j}$ and $x_{i,j^{\prime}}$ with $j\neq j^{\prime}$, at most one of them
shall be true; the second half is satisfied if the same holds for all pairs
$x_{i,j}$ and $x_{i^{\prime},j}$ with $i\neq i^{\prime}$. Conversely, a
satisfying assignment $A$ (a subset of $\texttt{Var}_{R\times S}$) for
$\varphi_{map}$ defines a relation $\sigma\subseteq R\times S$ and a set
$X\subseteq R$ by setting $\sigma=\\{(a_{i},b_{j})\mid x_{i,j}\in A\\}$ and
$X=\\{a_{i}\in R\mid\exists\,1\leq j\leq|S|\colon x_{i,j}\in A\\}$. By
construction, the relation $\sigma$ is not only a function $\sigma\colon X\to
S$, but an injection. In summary, $\varphi_{map}$ is fulfilled exactly by the
assignments described above. Observe that $\varphi_{map}$ is in conjunctive
normal form and therefore also $3$-normalized as each literal is a conjunctive
clause of length 1.

We now formalize the requirement that a configuration $(X,\sigma)$ is an
inclusion dependency in a given pair of databases $\mathfrak{r}$ and
$\mathfrak{s}$ over the respective schemas $R$ and $S$, that is, that
$\mathfrak{r}[X]\subseteq\mathfrak{s}[\sigma(X)]$ holds. First, assume that
each database consists only of a single row $r_{\ell}$ and $s_{m}$,
respectively. We say a pair of attributes $(a_{i},b_{j})\in R\times S$ is
_forbidden_ for $r_{\ell}$ and $s_{m}$ if $r_{\ell}[a_{i}]\neq s_{m}[b_{j}]$.
Let $F_{\ell,m}$ be the set of all forbidden pairs. For an configuration
$(X,\sigma)$ to be an IND, the variables $x_{i,j}$ need to be set to false for
all $(a_{i},b_{j})\in F_{\ell,m}$. In terms of Boolean formulas, this is
represented by the conjunctive clause
$M_{\ell,m}=\bigwedge_{x\in\texttt{Var}_{F_{\ell,m}}}\\!\neg x$. It follows
that $(X,\sigma)$ is an inclusion dependency if and only if the corresponding
variable assignment satisfies both $\varphi_{map}$ and $M_{\ell,m}$.

Now suppose $\mathfrak{s}$ has multiple rows, while $\mathfrak{r}$ is still
considered to have only one. The configuration $(X,\sigma)$ is an IND for
$(\mathfrak{r},\mathfrak{s})$ iff it is one for at least one instance
$(\mathfrak{r},\\{s_{m}\\})$ with $s_{m}\in\mathfrak{s}$. If also
$\mathfrak{r}$ has more records, then $(X,\sigma)$ is an IND for
$(\mathfrak{r},\mathfrak{s})$ iff it is one in each instance
$(\\{r_{\ell}\\},\mathfrak{s})$ with $r_{\ell}\in\mathfrak{r}$. Therefore, we
obtain an inclusion dependency if and only if $\varphi_{map}$ and the formula

$\displaystyle\varphi=\bigwedge_{r_{\ell}\in\mathfrak{r}}\bigvee_{s_{m}\in\mathfrak{s}}M_{\ell,m}$

are simultaneously satisfied by the assignment corresponding to $(X,\sigma)$.

The formula $\varphi\wedge\varphi_{map}$ is antimonotone and 3-normalized. The
(disjunctive) clauses of $\varphi_{map}$ can be constructed in total time
$\operatorname{O}(|R|^{2}|S|+|R||S|^{2})$ and all sets $F_{\ell,m}$ together
are computable in time $\operatorname{O}(|\mathfrak{r}||\mathfrak{s}||R||S|)$.
An encoding of $\varphi\wedge\varphi_{map}$ can thus be obtained from the
input databases $\mathfrak{r}$ and $\mathfrak{s}$ in polynomial time. Finally,
by the above observation that any solution for the sub-formula $\varphi_{map}$
that corresponds to $(X,\sigma)$ has weight $|X|$, the reduction preserves the
parameter. ∎

###  4.3 Hardness for $W[3]$

We now show that detecting inclusion dependencies is also hard for
$\textsf{W}[3]$. We argue that the existence of weighted satisfying
assignments for 3-normalized, antimonotone formulas can be decided by solving
instances of the more restricted Inclusion DependencyIdentity variant. For the
reduction, we make use of indicator functions. On the one hand, we interpret
propositional formulas $\varphi$ over $n$ variables as Boolean functions
$f_{\varphi}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ in the obvious way. On the other
hand, for a pair of databases $\mathfrak{r}$ and $\mathfrak{s}$ over the the
same schema $R$, we represent any subset $X\subseteq R$ by its characteristic
vector of length $|R|$. We then define the _indicator function_
$f_{(\mathfrak{r},\mathfrak{s})}\colon\\{0,1\\}^{|R|}\to\\{0,1\\}$ by
requiring that $f_{(\mathfrak{r},\mathfrak{s})}(X)=1$ holds if and only if $X$
is an inclusion dependency (with the identity mapping between the columns).

We claim that for any formula $\varphi$ that is antimonotone and 3-normalized,
there is a pair $(\mathfrak{r},\mathfrak{s})$ of databases computable in
polynomial time such that $f_{\varphi}=f_{(\mathfrak{r},\mathfrak{s})}$.
Clearly, this gives a parameterized reduction from WA$3$NS to the Inclusion
DependencyIdentity problem. The remainder of this section is dedicated to
proving this claim. Recall that the top level connective of a 3-normalized
formula is a conjunction. We start by demonstrating how to model this using
databases.

######  Lemma 12.

Let $(\mathfrak{r}^{(1)},\mathfrak{s}^{(1)})$ and
$(\mathfrak{r}^{(2)},\mathfrak{s}^{(2)})$ be two pairs of databases, all over
the same schema $R$, with indicator functions $f^{(1)}$ and $f^{(2)}$,
respectively. There exists a polynomial time computable pair
$(\mathfrak{r},\mathfrak{s})$ over $R$ of size
$|\mathfrak{r}|=|\mathfrak{r}^{(1)}|+|\mathfrak{r}^{(2)}|$ and
$|\mathfrak{s}|=|\mathfrak{s}^{(1)}|+|\mathfrak{s}^{(2)}|$, having indicator
function $f_{(\mathfrak{r},\mathfrak{s})}=f^{(1)}\wedge f^{(2)}$.

###### Proof.

Without loosing generality, the values appearing in $\mathfrak{r}^{(1)}$ and
$\mathfrak{s}^{(1)}$ are disjoint from those in $\mathfrak{r}^{(2)}$ and
$\mathfrak{s}^{(2)}$. We straightforwardly construct
$(\mathfrak{r},\mathfrak{s})$ as
$\mathfrak{r}=\mathfrak{r}^{(1)}\cup\mathfrak{r}^{(2)}$ and
$\mathfrak{s}=\mathfrak{s}^{(1)}\cup\mathfrak{s}^{(2)}$, which matches the
requirements on both the computability and size. We still need to show
$f_{(\mathfrak{r},\mathfrak{s})}=f^{(1)}\wedge f^{(2)}$.

Equivalently, we prove that a set $X\subseteq R$ is an inclusion dependency in
$(\mathfrak{r},\mathfrak{s})$ if and only if it is one in both pairs
$(\mathfrak{r}^{(1)},\mathfrak{s}^{(1)})$ and
$(\mathfrak{r}^{(2)},\mathfrak{s}^{(2)})$. Let $X$ be an IND in
$(\mathfrak{r}^{(1)},\mathfrak{s}^{(1)})$ as well as
$(\mathfrak{r}^{(2)},\mathfrak{s}^{(2)})$. That means, for every row
$r\in\mathfrak{r}^{(1)}$, there exists some $s\in\mathfrak{s}^{(1)}$ with
$r[X]=s[X]$; same for $\mathfrak{r}^{(2)}$ and $\mathfrak{s}^{(2)}$. As all
those rows are also present in $(\mathfrak{r},\mathfrak{s})$, $X$ is an IND
there as well. Conversely, suppose $X$ is not an inclusion dependency in, say,
$(\mathfrak{r}^{(1)},\mathfrak{s}^{(1)})$. Then, $\mathfrak{r}^{(1)}$ has a
row $r$ that disagrees with every $s\in\mathfrak{s}^{(1)}$ on some attribute
in $X$. The record $r$ is also in present in $\mathfrak{r}$ and all rows in
$\mathfrak{s}$ belong either to $\mathfrak{s}^{(1)}$ or have completely
disjoint values. This results in $r[X]\not=s[X]$ for _every_ record
$s\in\mathfrak{s}$. ∎

One could hope that there is a similar method treating disjunctions. However,
we believe that there is none that is both computable in FPT-time and
compatible with a complementing method representing conjunctions (for example,
the one above). The reason is as follows. Negative literals are easily
expressible by pairs of single-row databases. Together with FPT-time
procedures of constructing conjunctions as well as disjunctions, one could
encode antimonotone Boolean formulas of arbitrary logical depth. The
Antimonotone Collaps Theorem [23], states that the Weighted Antimonotone
$t$-normalized Satisfiability problem is $\textsf{W}[t]$-complete for every
odd $t\geq 3$. This would then render Inclusion DependencyIdentity to be hard
for all classes $\textsf{W}[t]$ and, as a consequence of Lemmas 11 and 10, the
W-hierarchy would collapse to its third level. That being said, there is a
method specifically tailored to antimonotone DNF formulas.

######  Lemma 13.

Let $\varphi$ be an antimonotone formula in disjunctive normal form. There are
relational databases $\mathfrak{r}$ and $\mathfrak{s}$ over the same schema
computable in time polynomial in the size of $\varphi$ such that
$f_{\varphi}=f_{(\mathfrak{r},\mathfrak{s})}$.

###### Proof.

Let $x_{1},\dots,x_{n}$ be the variables of $\varphi$. Define schema
$R=\\{a_{1},\dots,a_{n}\\}$ by identifying variable $x_{i}$ with attribute
$a_{i}$. We first describe how to obtain $\mathfrak{r}$ and subsequently
construct a matching database $\mathfrak{s}$. Let $M_{1},\dots,M_{m}$ denote
the $m$ constituting conjunctive clauses of the DNF formula $\varphi$. For
each $M_{j}$, we define the row $r_{j}$, similarly as in the proof of Lemma 6,
as

$r_{j}[a_{i}]=\begin{cases}j,&\text{if variable }x_{i}\text{ occurs in
}M_{j};\\\ 0,&\text{otherwise.}\end{cases}$

See Figure 5 for an example.

Figure 5: Illustration of Lemma 13. The antimonotone DNF formula $\varphi$ on
the left has the three conjunctive clauses $M_{1},M_{2},M_{3}$. The equivalent
instance of Inclusion DependencyIdentity consists of database $\mathfrak{r}$
in the center and $\mathfrak{s}$ on the right. There are three maximal
inclusion dependencies $\\{a_{4},a_{5},a_{6}\\}$, $\\{a_{1},a_{3},a_{6}\\}$,
and $\\{a_{3},a_{5}\\}$. Adding any more attributes to either of them would
create a hitting set for the conjunctive clauses, corresponding to an
unsatisfying assignment.

The second database $\mathfrak{s}$ is constructed by first creating $m$ copies
of $\mathfrak{r}$. Let $\times$ be a new symbol not appearing anywhere in
$\mathfrak{r}$. In the $j$-th copy of $\mathfrak{r}$, we set the value for
attribute $a_{i}$ to $\times$ whenever $x_{i}$ occurs in $M_{j}$. (See Figure
5 again.) Note that $|R|=n$ equals the number of variables of $\varphi$ and
$|\mathfrak{r}|$ is linear in the number $m$ of conjunctive clauses, while
$|\mathfrak{s}|$ is quadratic. The time to compute the pair
$(\mathfrak{r},\mathfrak{s})$ is linear in their combined size and polynomial
in the size of $\varphi$. It is left to show that the indicator function
satisfies $f_{\varphi}=f_{(\mathfrak{r},\mathfrak{s})}$.

First, suppose $f_{\varphi}(X)=1$ for some length-$n$ binary vector $X$ or,
equivalently, for some subset $X\subseteq R$. We show that
$f_{(\mathfrak{r},\mathfrak{s})}(X)=1$, meaning that $X$ is an inclusion
dependency in $(\mathfrak{r},\mathfrak{s})$. Necessarily, we have
$f_{M_{j}}(X)=1$ for at least one conjunctive clause $M_{j}$. Since $M_{j}$
contains only negative literals, all of its variables evaluate to false. This
is equivalent to $X$ not containing any attribute that corresponds to a
variable in $M_{j}$. In the $j$-th copy of $\mathfrak{r}$ in the database
$\mathfrak{s}$, the values were changed to $\times$ for exactly those
attributes. Thus, the projection $\mathfrak{s}[X]$ contains an exact copy of
$\mathfrak{r}[X]$ and $X$ is indeed an IND, resulting in
$f_{(\mathfrak{r},\mathfrak{s})}(X)=1$.

For the opposite direction, suppose $f_{\varphi}(X)=0$. Each conjunctive
clause thus contains a variable corresponding to some attribute in $X$.
Consequently, in each row of $\mathfrak{s}$, there is an attribute in $X$
whose value was replaced by $\times$. As $\mathfrak{r}$ does not contain the
symbol $\times$ at all, $X$ is not an IND and
$f_{(\mathfrak{r},\mathfrak{s})}(X)=0$. ∎

Lemmas 12 and 13 imply that, given an antimonotone, 3-normalized formula
$\varphi$, we can build an instance $(\mathfrak{r},\mathfrak{s})$ of Inclusion
DependencyIdentity in FPT-time (even polynomial) such that
$f_{\varphi}=f_{(\mathfrak{r},\mathfrak{s})}$. Together with the findings of
Section 4.2, this finishes the proof of 2.

###  4.4 Discovery

As we did with minimal unique column combinations and functional dependencies,
we can lift our results from detecting a single inclusion dependency to
discovering all of them. It turns out that there is a parsimonious equivalence
with the enumeration of assignments to antimonotone, 3-normalized formulas, as
detailed in 4. The key observations to prove this are once again that the
reductions above are polynomial time computable, independently of the
parameter, and that they preserve inclusions.

Lemmas 12 and 13 describe how to turn the formula $\varphi$ in polynomial time
into a pair of databases over the common schema $R$, which is effectively the
same as $\texttt{Var}_{\varphi}$, such that the inclusion dependencies
$X\subseteq R$ are in canonical correspondence with the satisfying assignments
$A\subseteq\texttt{Var}_{\varphi}$. Moreover, the parameterized reduction
preserves inclusion relations between the solutions such that the maximal
dependencies also correspond to the maximal assignments. In other words,
Lemmas 12 and 13 induce a parsimonious reduction from Enumerate Maximal
Satisfying WA$3$NS Assignments to Enumerate Maximal INDsIdentity. It is also
easy to see that Lemma 10 implies a parsimonious reduction from the
enumeration of such restricted inclusion dependencies to the general Enumerate
Maximal INDs problem. The lemma does nothing else but invalidating all non-
identity mappings between the columns. Finally, Lemma 11 shows how to
translate general inclusion dependencies back to antimonotone, 3-normalized
formula $\varphi$. Observe that the (inclusion-wise) maximal satisfying
assignments of the resulting formula correspond exactly to the notion of
maximality for general INDs (see Sections 2.2 and 4.1 for details). This shows
the equivalence of all the enumeration problems involved. Again, the space
complexity is preserved up to polynomial factors by the parsimonious
reductions.

We complete the proof of 4 by showing that the problems are at least as hard
as Transversal Hypergraph. This is an easy exercise using the structure of
antimonotone CNFs.

######  Lemma 14.

The enumeration of maximal satisfying assignments of antimonotone Boolean
formulas in conjunctive normal form is equivalent to _Transversal Hypergraph_
under parsimonious reductions. In particular, _Enumerate Maximal Satisfying WA
$3$NS Assignments_ is at least as hard as the _Transversal Hypergraph_
problem.

###### Proof.

For the reductions, in both directions, we identify the (disjunctive) clauses
of an antimonotone CNF formula $\varphi$ with the sets of variables they
contain. To spell it out, let $\texttt{Var}_{\varphi}$ be the set of all
variables of $\varphi$ and $C_{1},\dots,C_{m}\subseteq\texttt{Var}_{\varphi}$
the clauses. Since the the formula is antimonotone, any $C_{i}$ is satisfied
iff there is a variable $x\in C_{i}$ that is assigned false. In other words,
an assignment $A\subseteq\texttt{Var}_{\varphi}$ (the set of true variables)
is satisfying iff its complement
$\overline{A}=\texttt{Var}_{\varphi}{\setminus}\hskip 1.00006pt{A}$ is a
hitting set of the hypergraph $\\{C_{i}\\}_{i\in[m]}$. Assignment $A$ is
maximal in that regard iff $\overline{A}\in\operatorname{Tr}(\\{C_{i}\\}_{i})$
is a minimal transversal. In the very same fashion, we can construct from any
hypergraph $(\mathcal{H},V)$ an antimonotone CNF formula on the variable set
$\\{x_{v}\mid v\in V\\}$ by setting
$\varphi=\bigwedge_{E\in\mathcal{H}}\bigvee_{v\in E}\neg x_{v}$. Complementing
the maximal satisfying assignments of $\varphi$ recovers the minimal hitting
sets of $\mathcal{H}$.

The second part of the lemma follows from any CNF formula being also
3-normalized by viewing literals as conjunctive clauses of length 1. ∎

##  5 Conclusion

We have determined the complexity of the detection problems for various types
of multi-column dependencies, parameterized by the solution size. Our results
imply that these problems do not admit FPT-algorithms unless the W-hierarchy
at least partially collapses. In fact, the detection of inclusion dependencies
turned out to be surprisingly hard in that it is $\textsf{W}[3]$-complete.
Therefore, a small solution size alone is not enough to explain the good
performance in practice. This is unfortunate as the choice of parameter
appears to be very natural in the sense that the requirement of a small
solution size is regularly met in practice. Of course, our results do not
preclude FPT-algorithms for _other_ parameters. As an example, Unique Column
Combination on databases over schema $R$ are trivially in FPT with respect to
the parameter $|R|$ by checking all subsets. This is of course not very
satisfying since assuming the schema to be small is much stronger than
assuming the solutions to be small. Similarly, one could consider the maximum
number $d$ of attributes on which two rows in the data disagree as parameter.
Using the standard bounded search tree of height $k$ with nodes of degree at
most $d$ gives an FPT-algorithm with respect to the parameter $d+k$. Again,
the assumption that any two rows in a relation differ only on a few columns
seems to be fairly unrealistic for most practical data sets. More structural
research into relational databases is needed to bridge the gap between the
worst-case hardness and empirical tractability of dependency detection
problems. This will involve identifying properties of realistic instances that
can explain and hopefully even improve the running times of practical methods.
For example, by designing multivariate algorithms with more than one
parameter.

On the other hand, our results regarding the discovery of all dependencies of
a certain type in a database are indeed able to explain the good run times in
practice. We proved that the profiling of relational data at its core is
closely related to the transversal hypergraph problem. Although the exact
complexity of the latter is still open, there are many empirically efficient
algorithms known for it. Most importantly, modern algorithms for the
enumeration of hitting sets have the advantage that their space complexity is
only linear in the input size, this is a feature many data profiling
algorithms are still lacking today [1, 41, 47]. Even more than large run
times, prohibitive memory consumption still puts certain databases out of
reach for data profiling today. The relations shown here may therefore be a
way to improve the current state of the art algorithms in that direction.

## Ackowledgements

We thank Sebastian Kruse, Felix Naumann, and Thorsten Papenbrock for proposing
data profiling as a research topic to us, for their continued support, and for
providing the data presented in the introduction. We are also thankful for the
discussion with Jan Kossmann on query optimization and with Yann Strozecki on
enumeration complexity, both provided valuable insights and pointers to the
literature.

## References

  * [1] Ziawasch Abedjan, Lukasz Golab, Felix Naumann, and Thorsten Papenbrock.  Data Profiling, volume 10 of Synthesis Lectures on Data Management.  Morgan & Claypool Publishers, San Rafael, CA, USA, 2018.  doi:10.2200/S00878ED1V01Y201810DTM052.
  * [2] Tatsuya Akutsu and Feng Bao.  Approximating Minimum Keys and Optimal Substructure Screens.  In Proceedings of the 2nd International Conference on Computing and Combinatorics (COCOON), pages 290–299, 1996.  doi:10.1007/3-540-61332-3_163.
  * [3] Richard Beigel and Bin Fu.  Molecular Computing, Bounded Nondeterminism, and Efficient Recursion.  Algorithmica, 25:222–238, 1999.  doi:10.1007/PL00008275.
  * [4] Jan C. Bioch and Toshihide Ibaraki.  Complexity of Identification and Dualization of Positive Boolean Functions.  Information and Computation, 123:50–63, 1995.  doi:10.1006/inco.1995.1157.
  * [5] Johann Birnick, Thomas Bläsius, Tobias Friedrich, Felix Naumann, Thorsten Papenbrock, and Martin Schirneck.  Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery.  Proceedings of the VLDB Endowment, 13:2270–2283, 2020.  doi:10.14778/3407790.3407824.
  * [6] Thomas Bläsius, Tobias Friedrich, Julius Lischeid, Kitty Meeks, and Martin Schirneck.  Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling.  In Proceedings of the 21st Meeting on Algorithm Engineering and Experiments (ALENEX), pages 130–143, 2019.  doi:10.1137/1.9781611975499.11.
  * [7] Thomas Bläsius, Tobias Friedrich, and Martin Schirneck.  The Parameterized Complexity of Dependency Detection in Relational Databases.  In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC), pages 6:1–6:13, 2016.  doi:10.4230/LIPIcs.IPEC.2016.6.
  * [8] Endre Boros, Vladimir Gurvich, and Peter L. Hammer.  Dual Subimplicants of Positive Boolean Functions.  Optimization Methods and Software, 10:147–156, 1998.  doi:10.1080/10556789808805708.
  * [9] Florent Capelli and Yann Strozecki.  Incremental Delay Enumeration: Space and Time.  Discrete Applied Mathematics, 268:179–190, 2019.  doi:10.1016/j.dam.2018.06.038.
  * [10] Marco A. Casanova, Ronald Fagin, and Christos H. Papadimitriou.  Inclusion Dependencies and Their Interaction with Functional Dependencies.  In Proceedings of the 1st Symposium on Principles of Database Systems (PODS), pages 171–176, 1982.  doi:10.1145/588111.588141.
  * [11] Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, and Florian Sikora.  On the Complexity of Solution Extension of Optimization Problems.  CoRR, abs/1810.04553, 2018.  URL: http://arxiv.org/abs/1810.04553, arXiv:1810.04553.
  * [12] Surajit Chaudhuri and Kyuseok Shim.  Including Group-By in Query Optimization.  In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), pages 354–366, 1994.  URL: http://www.vldb.org/conf/1994/P354.PDF.
  * [13] Jianer Chen and Fenghui Zhang.  On Product Covering in 3-Tier Supply Chain Models: Natural Complete Problems for $W[3]$ and $W[4]$.  Theoretical Computer Science, 363:278–288, 2006.  doi:10.1016/j.tcs.2006.07.016.
  * [14] Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari.  Sublinear-Space and Bounded-Delay Algorithms for Maximal Clique Enumeration in Graphs.  Algorithmica, 82:1547–1573, 2020.  doi:10.1007/s00453-019-00656-8.
  * [15] Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer.  A Complexity Theory for Hard Enumeration Problems.  Discrete Applied Mathematics, 268:191–209, 2019.  doi:10.1016/j.dam.2019.02.025.
  * [16] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, Cham, Switzerland, 2015.  doi:10.1007/978-3-319-21275-3.
  * [17] Christopher J. Date.  An Introduction to Database Systems.  Addison-Wesley Longman Publishing, Boston, MA, USA, 8th edition edition, 2003.
  * [18] Scott Davies and Stuart Russell.  NP-Completeness of Searches for Smallest Possible Feature Sets.  In AAAI Symposium on Intelligent Relevance, 1994.  Technical Report.  URL: https://www.aaai.org/Papers/Symposia/Fall/1994/FS-94-02/FS94-02-011.pdf.
  * [19] Irit Dinur and David Steurer.  Analytical Approach to Parallel Repetition.  In Proceedings of the 46th Symposium on Theory of Computing (STOC), page 624–633, 2014.  doi:10.1145/2591796.2591884.
  * [20] Carlos Domingo, Nina Mishra, and Leonard Pitt.  Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries.  Machine Learning, 37:89–110, 1999.  doi:10.1023/A:1007627028578.
  * [21] Rodney G. Downey and Michael R. Fellows.  Fixed-Parameter Tractability and Completeness I: Basic Results.  SIAM Journal on Computing, 24:873–921, 1995.  doi:10.1137/S0097539792228228.
  * [22] Rodney G. Downey and Michael R. Fellows.  Fixed-Parameter Tractability and Completeness II: On Completeness for $W[1]$.  Theoretical Computer Science, 141:109–131, 1995.  doi:10.1016/0304-3975(94)00097-3.
  * [23] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, London, UK, 2013.  doi:10.1007/978-1-4471-5559-1.
  * [24] Thomas Eiter and Georg Gottlob.  Identifying the Minimal Transversals of a Hypergraph and Related Problems.  SIAM Journal on Computing, 24:1278–1304, 1995.  doi:10.1137/S0097539793250299.
  * [25] Thomas Eiter, Georg Gottlob, and Kazuhisa Makino.  New Results on Monotone Dualization and Generating Hypergraph Transversals.  SIAM Journal on Computing, 32:514–537, 2003.  doi:10.1137/S009753970240639X.
  * [26] Thomas Eiter, Kazuhisa Makino, and Georg Gottlob.  Computational Aspects of Monotone Dualization: A Brief Survey.  Discrete Applied Mathematics, 156:2035–2049, 2008.  doi:10.1016/j.dam.2007.04.017.
  * [27] Khaled M. Elbassioni, Matthias Hagen, and Imran Rauf.  Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems.  In Proceedings of the 3rd International Workshop on Parameterized and Exact Computation, (IWPEC), pages 91–102, 2008.  doi:10.1007/978-3-540-79723-4_10.
  * [28] Michael L. Fredman and Leonid G. Khachiyan.  On the Complexity of Dualization of Monotone Disjunctive Normal Forms.  Journal of Algorithms, 21:618–628, 1996.  doi:10.1006/jagm.1996.0062.
  * [29] Vincent Froese, René van Bevern, Rolf Niedermeier, and Manuel Sorge.  Exploiting Hidden Structure in Selecting Dimensions That Distinguish Vectors.  Journal of Computer and System Sciences, 82:521–535, 2016.  doi:10.1016/j.jcss.2015.11.011.
  * [30] Andrew Gainer-Dewar and Paola Vera-Licona.  The Minimal Hitting Set Generation Problem: Algorithms and Computation.  SIAM Journal on Discrete Mathematics, 31:63–100, 2017.  doi:10.1137/15M1055024.
  * [31] Chris Giannella, Mehmet M. Dalkilic, Dennis P. Groth, and Edward L. Robertson.  Improving Query Evaluation with Approximate Functional Dependency Based Decompositions.  In Proceedings of the 19th British National Conference on Databases, (BNCOD), volume 2405, pages 26–41, 2002.  doi:10.1007/3-540-45495-0_3.
  * [32] Miika Hannula, Bor-Kuan Song, and Sebastian Link.  An Algorithm for the Discovery of Independence from Data.  CoRR, abs/2101.02502, 2021.  ArXiv preprint.  URL: https://arxiv.org/abs/2101.02502, arXiv:2101.02502.
  * [33] Ihab F. Ilyas, Volker Markl, Peter J. Haas, Paul Brown, and Ashraf Aboulnaga.  CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies.  In Proceedings of the 2004 International Conference on Management of Data (SIGMOD), pages 647–658, 2004.  doi:10.1145/1007568.1007641.
  * [34] Martti Kantola, Heikki Mannila, Kari-Jouko Räihä, and Harri Siirtola.  Discovering Functional and Inclusion Dependencies in Relational Databases.  International Journal of Intelligent Systems, 7:591–607, 1992.  doi:10.1002/int.4550070703.
  * [35] Richard M. Karp.  Reducibility Among Combinatorial Problems.  In Proceedings of a Symposium on the Complexity of Computer Computations, pages 85–103, 1972.  URL: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf.
  * [36] Henning Köhler, Uwe Leck, Sebastian Link, and Xiaofang Zhou.  Possible and Certain Keys for SQL.  The VLDB Journal, 25:571–596, 2016.  doi:10.1007/s00778-016-0430-9.
  * [37] David Maier.  The Theory of Relational Databases.  Computer Science Press, Rockville, MD, USA, 1983.
  * [38] Heikki Mannila and Kari-Jouko Räihä.  Dependency Inference.  In Proceedings of the 13th International Conference on Very Large Data Bases (VLDB), pages 155–158, 1987.  URL: https://www.vldb.org/conf/1987/P155.PDF.
  * [39] Keisuke Murakami and Takeaki Uno.  Efficient Algorithms for Dualizing Large-scale Hypergraphs.  Discrete Applied Mathematics, 170:83–94, 2014.  doi:10.1016/j.dam.2014.01.012.
  * [40] Rolf Niedermeier.  Invitation to Fixed-Parameter Algorithms.  Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford, UK, 2006.  doi:10.1093/acprof:oso/9780198566076.001.0001.
  * [41] Thorsten Papenbrock and Felix Naumann.  A Hybrid Approach to Functional Dependency Discovery.  In Proceedings of the 2016 International Conference on Management of Data (SIGMOD), pages 821–833, 2016.  doi:10.1145/2882903.2915203.
  * [42] Glenn N. Paulley and Per-Åke Larson.  Exploiting Uniqueness in Query Optimization.  In Proceedings of the 10th International Conference on Data Engineering (ICDE), pages 68–79, 1994.  doi:10.1109/ICDE.1994.283003.
  * [43] Uri N. Peled and Bruno Simeone.  A $O(nm)$-Time Algorithm for Computing the Dual of a Regular Boolean Function.  Discrete Applied Mathematics, 49:309–323, 1994.  doi:10.1016/0166-218X(94)90215-1.
  * [44] Taneli Pusa, Mariana Galvao Ferrarini, Ricardo Andrade, Arnaud Mary, Alberto Marchetti-Spaccamela, Leen Stougie, and Marie-France Sagot.  MOOMIN - mathematical exploration of ’omics data on a metabolic network.  Bioinformatics, 36:514–523, 2020.  doi:10.1093/bioinformatics/btz584.
  * [45] Andrzej Skowron and Cecylia Rauszer.  volume 11 of Theory and Decision Library - Series D: System Theory, Knowledge Engineering and Problem Solving, chapter The Discernibility Matrices and Functions in Information Systems, pages 331–362.  Kluwer Academic Publishers, Dordrecht, Netherlands, 1992.  doi:10.1007/978-94-015-7975-9_21.
  * [46] Aaron Swartz.  MusicBrainz: A Semantic Web Service.  IEEE Intelligent Systems, 17:76–77, 2002.  See www.musicbrainz.org.  doi:10.1109/5254.988466.
  * [47] Ziheng Wei, Uwe Leck, and Sebastian Link.  Discovery and Ranking of Embedded Uniqueness Constraints.  Proceedings of the VLDB Endowment, 12:2339–2352, 2019.  doi:10.14778/3358701.3358703.