text:
\section{Introduction}
\label{sec:intro}

\noindent
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 \Cref{fig:example_table}, the \texttt{Name} and \texttt{Area Code}
provide a unique fingerprint of the first database as, for example,
there is only one \texttt{Doe,$\,$John} living in \texttt{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 \texttt{DISTINCT} operation, even if requested by the user~\cite{Chaudhuri94GroupByQueryOptimization,Paulley94ExploitingUniquenessinQueryOptimization}.
Also, the presence of UCCs allows for early returns of \texttt{SELECT}
and \texttt{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 \emph{detection problem}, is to decide whether for a given database
whether it admits a UCC with only a few columns.
The \emph{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 \emph{enumeration} of minimal solutions.

\begin{figure}
\centering
	\includegraphics[scale=0.85]{tabelle_2}
	\caption{Illustration of multi-column dependencies.
		\texttt{Name} and \texttt{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,
		\texttt{Age} is included in \texttt{ID} and \texttt{Name} in \texttt{Author}.
		They cannot be combined to an inclusion dependency of size 2.}
\label{fig:example_table}
\end{figure}

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 \Cref{fig:example_table},
it is enough to know the \texttt{Area Code} to also infer the \texttt{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~\cite{Casanova82INDsandFDs,Giannella02QueryEvalApproximateFDs,Ilyas04CORDS_SIGMOD}.

The detection (decision) problems for all three types of dependencies are \textsf{NP}\xspace-complete.\footnote{%
	See \Cref{subsec:UCC_problem_definitions,subsec:IND_problem_definitions}
	for specific statements and references.
}
Notwithstanding, detection algorithms often perform well on practical datasets~\citep{Abedjan18DataProfiling}.
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~\cite{Cygan15ParamertizedAlgorithms,DowneyFellows13Parameterized,Niedermeier06Invitation}.
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 \Cref{fig:histogram}, showing the
size distribution of minimal unique column combinations and
functional dependencies, as well as maximal inclusion dependencies in the
MusicBrainz
database~\cite{Swartz02MusicBrainz}.
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}\xspace[2]$-complete
with respect to the size of the sought solution, detecting
inclusion dependencies is even $\textsf{W}\xspace[3]$-complete.
For all we know, this excludes any algorithm parameterized by the size.

\begin{figure}
  \centering
  \includegraphics{histogram}
  \caption{The number of minimal unique column combinations, minimal
    functional dependencies, and maximal inclusion dependencies
    for varying solution sizes in the MusicBrainz database.}
  \label{fig:histogram}
\end{figure}

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}\xspace[3]$.
The first one was given by Chen and Zhang~\cite{Chen06W3W4} 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.~\cite{Blaesius19EfficientlyALENEX}
have also proven the extension problem for minimal hitting sets to be $\textsf{W}\xspace[3]$-complete
using different techniques.
The latter has subsequently been improved by Casel et al.~\cite{Casel18ComplexitySolutionExtensionArxiv},
they have shown that already the special case of extension to minimal dominating sets
in bipartite graphs is hard for $\textsf{W}\xspace[3]$.
Finally, building on the work presented here,
Hannula, Song, and Link~\cite{Hannula21IndependenceFromDataArXiv}
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 \emph{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^{\Or(\sfrac{\log N}{\log\log N})}$,
where $N$ is the combined input and output size~\cite{FredmanKhachiyan96Dualization}.
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~\cite{EiterMakinoGottlob08Survey,Pusa20MOOMIN}.
There are many algorithms known that work well on practical instances~\cite{Gainer17AlgorithmsAndComputation}.

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-poly\-no\-mial solution~\cite{EiterGottlob95RelatedProblems}.
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 \emph{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~\cite{Papenbrock16HyFD,Wei19DiscoveryEmbeddedUnique}.
We hope that our results here inspire better data profiling algorithms in the future.\\

\noindent
\textbf{Our Contribution.}
We settle the parameterized complexity of the car\-di\-na\-lity-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.

\begin{thm}
\label{thm:unique_fd_W[2]}
	Detecting a unique column combination of size $k$ in a relational database
	is $\emph{\textsf{W}\xspace}[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.
\end{thm}

\begin{thm}
\label{thm:ind_W[3]}
	Detecting an inclusion dependency of size $k$ in a pair of relational databases
	is $\emph{\textsf{W}\xspace}[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.
\end{thm}

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.

\begin{thm}
\label{thm:equiv_transHyp}
	The following enumeration problems are equivalent under parsimonious reductions:
	\begin{enumerate}
		\item listing all minimal unique column combinations of a relational database;
		\item listing all minimal, valid, and non-trivial functional dependencies
			with a fixed right-hand side;
		\item the transversal hypergraph problem.
	\end{enumerate}
	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.
\end{thm}

\begin{thm}
\label{thm:enum_ind}
	The following enumeration problems are equivalent under parsimonious reductions:
	\begin{enumerate}
		\item listing all maximal inclusion dependencies of a pair of relational\\
				databases;
		\item listing all maximal satisfying assignments of an antimonotone,\\
				3-normalized Boolean formula.
	\end{enumerate}
	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.
\end{thm}

Finally, we also briefly discuss the consequences of our findings
to the approximability of minimum dependencies.\vspace*{.5em}

\noindent
\textbf{Outline.}
In the next section, we fix some notation and review basic concepts needed for the later proofs.
\Cref{sec:UCCs_and_FDs} treats unique column combinations and functional dependencies,
\Cref{sec:INDs} 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 \Cref{sec:conclusion}.

\section{Preliminaries}
\label{sec:prelims}

\subsection{Hypergraphs and Hitting Sets}
\label{subsec:prelims_hypergraphs}

\noindent
A \emph{hypergraph} is a non-empty, finite \emph{vertex set} $V \neq \emptyset$ together
with a set of subsets $\mathcal{H} \subseteq \mathcal{P}(V)$, the \emph{(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 \emph{Sperner} if none of its edges is contained in another.
The \emph{minimization} of $\mathcal{H}$ is the subset of all
inclusion-wise minimal edges,
$\min(\mathcal{H}) = \{ E \in \mathcal{H} \mid \forall E' \in \mathcal{H} \colon E' \subseteq E \Rightarrow E' = 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 \textit{hitting set}, or \textit{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 \textit{(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 \textit{transversal hypergraph} $\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 $\Tr(\min(\mathcal{H})) = \Tr(\mathcal{H})$.

\subsection{Relational Databases and Dependencies}
\label{subsec:prelims_databases}

\noindent
A \emph{(relational) schema} $R$ is a non-empty, finite set of \emph{attributes} or \emph{columns}.
Each attribute comes implicitly associated with a set of admissible values.
A \emph{row}, or \emph{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 \emph{(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 \emph{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 \emph{(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 \emph{unique column combination} (UCC), or simply \textit{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 \textit{(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 \cite{Abedjan18DataProfiling,Date03DatabaseSystems},
probably the first explicit mention was by Mannila and Räihä~\cite{Mannila87Dependency}.

\begin{obs}[Folklore]
\label{obs:UCCs_and_transversals}
	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 $\Tr(\mathcal{D})$ is a minimal unique of $\mathfrak{r}$
	and there are no other minimal uniques in $\mathfrak{r}$.
\end{obs}

\emph{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 \emph{left-hand side} (LHS) of the dependency
and $a$ the \emph{right-hand side} (RHS).
We say that the FD has \emph{size} $|X|$.
A functional dependency $X \,{\to}\, a$ is said to \emph{hold},
or be \emph{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 \emph{fail} in $\mathfrak{r}$, or be \emph{invalid}.
The FD $\emptyset \,{\to}\, a$ holds iff all rows agree on $a$.
An FD $X \,{\to}\, a$ is \emph{(inclusion-wise) minimal} if it holds in $\mathfrak{r}$ and
$X'' \,{\to}\, a$ fails for any proper subset $X'' \subsetneq X$.
A functional dependency is \emph{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 \emph{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 \emph{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',\sigma')$ holds
if $X \subseteq X'$ and $\sigma$ is the restriction of $\sigma'$ to $X$.
An inclusion dependency then is \emph{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',\sigma')$ are both maximal
although $X' \subsetneq X$ is a strict subset.

\subsection{Parameterized Complexity}
\label{subsec:prelims_parameterized}

\noindent
The central idea of the \emph{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 \emph{parameterized} if any instance $I$ is
additionally augmented with a \emph{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 \emph{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}\xspace(|I|)$.
The complexity class \textsf{FPT}\xspace
is the collection of all fixed-parameter tractable problems.

Let $\mathrm{\Pi}$ and $\mathrm{\Pi}'$ be two parameterized problems.
A \emph{parameterized reduction}, or \emph{FPT-reduction},
from $\mathrm{\Pi}$ to $\mathrm{\Pi}'$ is an algorithm
running in time $f(k)\cdot \textsf{poly}\xspace(|I|)$ on instances $(I, k)$,
which outputs some instance $(I', k')$
such that $k' \le 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',k') \in \mathrm{\Pi}'$ does.
Due to the time bound, we have $|I'| \le f(k) \, \textsf{poly}\xspace(|I|)$.
If there is also an FPT-reduction from $\mathrm{\Pi}'$ to $\mathrm{\Pi}$,
we say that the problems are \emph{FPT-equivalent}.
A notable special case of FPT-reductions are
polynomial many-one reductions that preserve the parameter,
meaning $k' = k$.

Parameterized reductions give rise to the so-called \textsf{W}\xspace-\emph{hierarchy} of complexity classes.
We use one of several equivalent definitions involving (mainly) Boolean formulas.
However, first consider the \textsc{Independent Set} problem on graphs
parameterized by the size of the sought solution.
The class $\textsf{W}\xspace[1]$ is the collection of all parameterized problems that admit
a parameterized reduction to \textsc{Independent Set}.
For some positive integer $t$, a Boolean formula is \emph{$t$-normalized}
if it is a conjunction of disjunctions of conjunctions of disjunctions (and so on) of literals
with $t\hspace*{.1em}{-}\hspace*{.1em}{1}$ alternations or, equivalently,
$t$ levels in total.
The \WS{t} 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 \ge 2$, $\textsf{W}\xspace[t]$ is the class of all problems reducible to \WS{t}.\footnote{%
	The definition via normalized formulas comes with an inconsistency at $t=1$.
	A \mbox{$1$-normalized} formula is a single conjunctive clause,
	the associated weighted satisfiability problem is trivially seen to be in $\P$
	and thus in $\textsf{FPT}\xspace$.
}
The classes
$\textsf{FPT}\xspace \subseteq \textsf{W}\xspace[1] \subseteq \textsf{W}\xspace[2] \subseteq \dots$
form an ascending hierarchy.
All inclusion are conjectured to be strict,
which is however still unproven.

\subsection{Enumeration Complexity}
\label{subsec:prelims_enumeration}

\noindent
\emph{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 \emph{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 \emph{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 \Tr(\mathcal{H})$.

An \emph{output-polynomial} algorithm runs in time polynomial
in the combined input and output size $N = |V| + |\mathcal{H}| + |\Tr(\mathcal{H})|$.
A (seemingly) stronger requirement is an \emph{incremental polynomial}
  algorithm, generating the solutions in such a way that the $i$-th
\emph{delay}, the time between the $(i\hspace*{.1em}{-}\hspace*{.1em}{1})$-st and $i$-th output, is
bounded by $\textsf{poly}\xspace(|V|,|\mathcal{H}|,i)$.
This includes the \emph{preprocessing time} until the first solution arrives ($i = 1$)
as well as the \emph{postprocessing time} between the last solution and termination
($i = |\Tr(\mathcal{H})|\,{+}\,1$).
The strongest form of
output-efficiency is that of \emph{polynomial delay}, where the
delay is universally bounded by $\textsf{poly}\xspace(|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~\cite{Bioch95Identification}.

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~\cite{CapelliStrozecki19Incremental}.
A \emph{parsimonious reduction} from enumeration problem $\mathrm{\Pi}$ to $\mathrm{\Pi}'$
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}'(f(I))$ to $\mathrm{\Pi}(I)$.
The behavior of $g(I, \cdot)$ on $\{0,1\}^*{\setminus}\mathrm{\Pi}'(f(I))$ is irrelevant.
Intuitively, any enumeration algorithm for $\mathrm{\Pi}'$ 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$.
\Cref{obs:UCCs_and_transversals} 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$.

\section{Unique Column Combinations and Functional Dependencies}
\label{sec:UCCs_and_FDs}

\noindent
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~\cite{Abedjan18DataProfiling,Date03DatabaseSystems,Davies94SmallestFeatureSets,
Kantola92FDsAndINDs,Maier83TheoryRelationalDatabases}.
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}\xspace[2]$.
We then also show the equivalence of the corresponding enumeration problems under parsimonious reductions.

\subsection{Problem Definitions}
\label{subsec:UCC_problem_definitions}

\noindent
Recall the definitions of hitting sets as well as
unique column combinations and functional dependencies from \Cref{subsec:prelims_hypergraphs,subsec:prelims_databases}.
We are interested in the parameterized complexity
of the associated cardinality-constrained decision problems.
The constraint always serves as the parameter.

\vspace*{.6em}
\noindent\textsc{Hitting Set}\xspace
\begin{description}
	\item [Instance:] A hypergraph $(V,\mathcal{H})$ and a non-negative integer $k$.
	\item [Parameter:] The non-negative integer $k$.
	\item [Decision:] Is there a set $T \subseteq V$ of vertices with cardinality $|T| = k$

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

\noindent
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 \emph{at most} or \emph{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 \textsc{Hitting Set}\xspace problem is one of Karp's initial 21 \mbox{\textsf{NP}\xspace-complete} problems~\cite{Karp72Reducibility}.
In fact, its minimization variant--to compute the minimum size of any hitting set--is
even \textsf{NP}\xspace-hard to approximate within a factor of $(1 - \varepsilon) \ln |V|$
for any \mbox{$\varepsilon > 0$}~\cite{Dinur14ParallelRepetition}.
The parameterized variant defined above is the prototypical \mbox{$\textsf{W}\xspace[2]$-complete} problem~\cite{DowneyFellows13Parameterized}.

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

\vspace*{.6em}
\noindent\textsc{Transversal Hypergraph}\xspace
\begin{description}[labelwidth = 2.45cm]
	\item [Instance:] A hypergraph $(V,\mathcal{H})$.
	\item [Enumeration:] List all edges of $\Tr(\mathcal{H})$.
\end{description}

\noindent
Let $N = |\mathcal{H}| + |\Tr(\mathcal{H})| + |V|$ denote the combined input and output size,
Fredman and Kachiyan's algorithm solves \textsc{Transversal Hypergraph}\xspace in time
$N^{\Or(\sfrac{\log N}{\log\log N})}$~\cite{FredmanKhachiyan96Dualization}.

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 $\Tr(\mathcal{H}) \hspace*{.1em}\dot\cup\hspace*{.1em} \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 \Tr(\mathcal{H}) \hspace*{.1em}\dot\cup\hspace*{.1em} \Tr(\mathcal{G})$,
the containment $T \in \Tr(\mathcal{H})$
is decidable in time $\textsf{poly}\xspace(|V|,|W|,|\mathcal{H}|, |\mathcal{G}|)$,
independently of the sizes $|\Tr(\mathcal{H})|$ and $|\Tr(\mathcal{G})|$.

\vspace*{.6em}
\noindent\textsc{Transversal Hypergraph Union}\xspace
\begin{description}[labelwidth = 2.45cm]
	\item [Instance:] A $d$-tuple of hypergraphs $(\mathcal{H}_1, \mathcal{H}_2, \dots, \mathcal{H}_d)$.
	\item [Enumeration:] List all edges of
		$\Tr(\mathcal{H}_1) \,\dot\cup\, \Tr(\mathcal{H}_2) \,\dot\cup\, \dots \,\dot\cup\, \Tr(\mathcal{H}_d)$.
\end{description}

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

\vspace*{.6em}
\noindent\textsc{Unique Column Combination}\xspace
\begin{description}
	\item [Instance:] A relational database $\mathfrak{r}$ over schema $R$

		and a non-negative integer $k$.
	\item [Parameter:] The non-negative integer $k$.
	\item [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}$?
\end{description}

\noindent
The minimization variant of \textsc{Unique Column Combination}\xspace is \textsf{NP}\xspace-hard~\cite{Skowron92DiscernibilityMatrices}.

\vspace*{.6em}
\noindent\textsc{Enumerate Minimal UCCs}\xspace
\begin{description}[labelwidth = 2.45cm]
	\item [Instance:] A relational database $\mathfrak{r}$.
	\item [Enumeration:] List all minimal unique column combinations of $\mathfrak{r}$.
\end{description}

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.

\pagebreak

\noindent\textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace
\begin{description}
	\item [Instance:] A relational database $\mathfrak{r}$ over schema $R$, an attribute $a \in R$,

			and a non-negative integer $k$.
	\item [Parameter:] The non-negative integer $k$.
	\item [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}$?
\end{description}

\vspace*{.6em}
\noindent\textsc{Functional Dependency}\xspace
\begin{description}
	\item [Instance:] A relational database $\mathfrak{r}$ over schema $R$

		and a non-negative integer $k$.
	\item [Parameter:] The non-negative integer $k$.
	\item [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}$?
\end{description}

\noindent
The unparameterized variant of \textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace is \textsf{NP}\xspace-complete
even if the number of admissible values for each attribute is at most~$2$~\cite{Davies94SmallestFeatureSets}.
It is the same to ask for a functional dependency whose left-hand side
is of size at most $k$;
unless of course $k \ge |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' \subseteq R$ such that $X' \,{\to}\, a$ is valid.

\vspace*{.6em}
\noindent\textsc{Enumerate Minimal FDs}\textsubscript{\textit{fixed RHS}}\xspace
\begin{description}[labelwidth = 2.45cm]
	\item [Instance:] A relational database $\mathfrak{r}$ over schema $R$
		and an attribute $a \in R$.
	\item [Enumeration:] List all minimal, valid, non-trivial functional dependencies of~$\mathfrak{r}$

		\hspace*{0.3cm} with right-hand side $a$.
\end{description}

\vspace*{.6em}
\noindent\textsc{Enumerate Minimal FDs}\xspace
\begin{description}[labelwidth = 2.45cm]
	\item [Instance:] A relational database $\mathfrak{r}$.
	\item [Enumeration:] List all minimal, valid, non-trivial functional dependencies~of~$\mathfrak{r}$.
\end{description}

\noindent
\textsc{Enumerate Minimal UCCs}\xspace and \textsc{Enumerate Minimal FDs}\xspace 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 \textsc{Transversal Hypergraph}\xspace problem~\cite{EiterGottlob95RelatedProblems}.

\subsection{Detection}
\label{subsec:UCC_detection}

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

\begin{figure}
    \centering
    \begin{subfigure}{0.5\textwidth}
        \centering
        \includegraphics[page=1,scale=1.1]{unique-fd-reductions}
        \captionsetup{justification=centering}
		\caption{}
	\label{subfig:unique-reduction}
    \end{subfigure}%
    \begin{subfigure}{0.5\textwidth}
        \centering
	    \includegraphics[page=2,scale=1.1]{unique-fd-reductions}
	    \captionsetup{justification=centering}
		\caption{}
	\label{subfig:fd-reduction}
    \end{subfigure}
    \caption{Illustration of the reductions in \Cref{lem:hs_to_unique,lem:unique_to_fd}.
		(a)~An instance of \textsc{Hitting Set}\xspace and the equivalent instance of \textsc{Unique Column Combination}\xspace.
		(b)~An instance $\mathfrak{r}$ of \textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace with fixed right-hand side $a$
		and the equivalent instance $\mathfrak{r}'$ of \textsc{Functional Dependency}\xspace.
		The functional dependencies $ab \,{\to}\, d$ holds in $\mathfrak{r}$, but not in $\mathfrak{r}'$.}
  \label{fig:unique-fd-reductions}
\label{fig:oracle_run_times}
\end{figure}

\begin{lem}
\label[lem]{lem:hs_to_unique}
	There is a parameterized reduction from \emph{\textsc{Hitting Set}\xspace}	to the \emph{\textsc{Unique Column Combination}\xspace} problem.
\end{lem}

\begin{proof}
	Let $(V,\mathcal{H})$ be the hypergraph given in the input to the \textsc{Hitting Set}\xspace 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 \Cref{obs:UCCs_and_transversals}.
	In particular, since \Cref{obs:UCCs_and_transversals}
	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
	\begin{equation*}
		r_i[a] =
			\begin{cases}
				i, & \text{if } a \in E_i;\\
				0, & \text{otherwise.}
			\end{cases}
	\end{equation*}

	\noindent
	See \Cref{subfig:unique-reduction} 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 \le i < j \le 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}$.
\end{proof}

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]$.

\begin{lem}
\label[lem]{lem:unique_to_fd}
	There are parameterized reductions
	\begin{enumerate}
		\item\label[stat]{case:unique_to_fdfixed} from \emph{\textsc{Unique Column Combination}\xspace}

			to \emph{\textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace};
		\item\label[stat]{case:fdfixed_to_fd} from \emph{\textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace}

			to \emph{\textsc{Functional Dependency}\xspace}.
	\end{enumerate}
\end{lem}

\begin{proof}
	To prove \Cref{case:unique_to_fdfixed}, 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}'$ over $R \cup \{a\}$ by adding,
	for each $r_i$, the row $r'_i$ defined by $r'_i[R] = r_i[R]$ and $r'_i[a] = i$.
	The reduction maps an instance $(\mathfrak{r},R,k)$ of \textsc{Unique Column Combination}\xspace
	to the instance $(\mathfrak{r}',R \cup \{a\}, a, k)$ of \textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace.
	Since, for any two distinct rows $r'_i,r'_j \in \mathfrak{r}'$, $i \neq j$,	we have $r'_i[a] \neq r'_j[a]$,
	the left-hand sides of the non-trivial, valid FDs $X \,{\to}\, a$ in $\mathfrak{r}'$ are
	in one-to-one correspondence to the UCCs in $\mathfrak{r}$.

	To reduce \textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace to \textsc{Functional Dependency}\xspace, we need to mask all ``unwanted'' FDs
	with RHS different from the fixed attribute $a$.
	See \Cref{subfig:fd-reduction} for an example.
	Let again $\mathfrak{r}$ be the input database over $R$.
	To construct the resulting database $\mathfrak{r}'$ 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}'$.

 	It is left to prove that $X \,{\to}\, a$ holds in $\mathfrak{r}$ if and only if it holds in $\mathfrak{r}'$.
 	Evidently, any valid FD in $\mathfrak{r}'$ is also valid in the subset $\mathfrak{r}$.
 	Suppose $X \,{\to}\, a$ holds in $\mathfrak{r}$ and let rows $r,s \in \mathfrak{r}'$
 	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}'{\setminus}\mathfrak{r}$ and $s \in \mathfrak{r}$
 	(all new rows in $\mathfrak{r}'{\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.
\end{proof}

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

\begin{lem}
  \label[lem]{lem:fd_to_ws2}
  There is a parameterized reduction from \emph{\textsc{Functional Dependency}\xspace} to the \emph{\WS{2}} problem.
\end{lem}

\begin{proof}
	Given a database $\mathfrak{r}$ over $R$, we derive a CNF formula
	that has a satisfying assignment of Hamming weight $k\hspace*{.1em}{+}\hspace*{.1em}{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,
	$\var{LHS} = \{x_a \mid a \in R \}$ and
	$\var{RHS} = \{y_a \mid a \in R \}$.
	Some variable $x_a$ from $\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 $\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 $\var{RHS}$.
	We prove below that this is not necessary and forgoing the $\Or(|R|^2)$ clauses
	representing this constraint allows for a (slightly) leaner construction.
	However, we do have to ensure that at least one variable from $\var{RHS}$ is set to \true
	and the corresponding one in $\var{LHS}$ is \false.
	This is done by the clauses $C_{RHS} = \bigvee_{y_a \in \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
 	\begin{equation*}
		C_{a,r,s} = \neg y_a \vee \bigvee_{\substack{b \in R{\setminus}\{a\}\\[.125em] r[b] \neq s[b]}} x_b.
	\end{equation*}

	\noindent
	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
	\begin{equation*}
    	\varphi_a = \bigwedge_{\substack{r,s \in \mathfrak{r}\\[.125em] r[a] \neq s[a]}} C_{a,r,s}.
	\end{equation*}
	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 $\Or(|R| \hspace*{.1em} |\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\hspace*{.1em}{+}\hspace*{.1em}{1}$ satisfying assignment iff
	a \mbox{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 \var{LHS} \cup \var{RHS}$ be an assignment
	of Hamming weight $|A| = k\hspace*{.1em}{+}\hspace*{.1em}{1}$ that satisfies $\varphi$.
	The assignment induces two subsets of the schema $R$,
	namely, $X = \{a \in R \mid x_a \in A \cap \var{LHS}\}$ and
	$Y = \{a \in R \mid y_a \in A \cap \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.
\end{proof}

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 \textsc{Hitting Set}\xspace and \WS{2} are both $\textsf{W}\xspace[2]$-complete
shows that all of the problems are, this completes the proof of \Cref{thm:unique_fd_W[2]}.

\subsection{Approximation and Discovery}
\label{subsec:UCC_discovery}

\noindent
Our reductions have implications beyond the scope of parameterized complexity.
Observe that the transformations in \Cref{lem:hs_to_unique,lem:unique_to_fd}
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 \textsc{Hitting Set}\xspace is \textsf{NP}\xspace-hard to approximate
within a factor of $(1-\varepsilon) \ln |V|$
for every $\varepsilon > 0$~\cite{Dinur14ParallelRepetition}.
As a consequence, the minimization versions of \textsc{Unique Column Combination}\xspace, \textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace,
and \textsc{Functional Dependency}\xspace all inherit the same hardness of approximation.
Previously, an approximation-preserving reduction was known
only for the \textsc{Unique Column Combination}\xspace problem, starting from \textsc{Set Cover}~\cite{Akutsu96ApproxMinKey}.

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 \Cref{subsec:UCC_problem_definitions}.
Instead, the \textsc{Transversal Hypergraph}\xspace problem (enumerating minimal hitting sets)
has been associated with the problem of deciding for two hypergraphs $\mathcal{H}$ and $\mathcal{G}$
whether $\mathcal{G}  = \Tr(\mathcal{H})$ or, equivalently, $\mathcal{H} = \Tr(\mathcal{G})$, called the \textsc{Dual} problem.
\textsc{Enumerate Minimal UCCs}\xspace 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 \textsf{co}\textsf{NP}\xspace and it was proven
by Eiter and Gottlob~\cite{EiterGottlob95RelatedProblems} that they are many-one equivalent.
Using a lifting result by Bioch and Ibaraki~\cite{Bioch95Identification},
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 \textsc{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~\cite{FredmanKhachiyan96Dualization}.
The connection to enumeration has also inspired the intriguing result that \textsc{Dual} is likely not \textsf{co}\textsf{NP}\xspace-hard as it can be solved
in polynomial time when given access to $\Or(\sfrac{\log^2 N}{\log\log N})$ suitably guessed
non\-deterministic bits~\cite{Beigel99BoundedNondeterminism,EiterGottlobMakino03NewResults},
where $N$ denotes the total input size of the pair $(\mathcal{H}, \mathcal{G})$.
There are classes of hypergraphs for which \textsc{Dual} is indeed in \P, see for
example~\cite{Boros98Subimplicants,DomingoMishraPitt99DualizationLearningMembershipQueries,
EiterGottlobMakino03NewResults,Peled94DualRegularBooleanFunction},
or at least in \textsf{FPT}\xspace with respect to certain structural parameters~\cite{ElbassioniHagenRauf08FPTHypergraphDuality}.
For a much more thorough overview of decision problems associated with enumeration,
see the recent work by Creignou et al.~\cite{Creignou19ComplexityTheoryHardEnumerationProblems}.

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 \textsc{Transversal Hypergraph}\xspace
whose space complexity is only linear in the input size~\cite{ElbassioniHagenRauf08FPTHypergraphDuality,Murakami14Dualization}.
In fact, enumeration algorithms are often analyzed
not only with respect to their running time, but also in terms of space consumption,
see~\cite{CapelliStrozecki19Incremental,Conte20SublinearSpaceMaximalCliqueEnumeration}.
For data profiling problems like \textsc{Enumerate Minimal UCCs}\xspace on the other hand,
space-efficient algorithms
have only recently started to received some attention~\cite{Birnick20HPIValid,Blaesius19EfficientlyALENEX,Koehler16Possible}.

In the following, we simplify and at the same time extend the above equivalences
making them usable in practice,
namely, we prove \Cref{thm:equiv_transHyp}.
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
\textsc{Hitting Set}\xspace, \textsc{Unique Column Combination}\xspace, \textsc{Functional Dependency}\textsubscript{\textit{fixed RHS}}\xspace, and \textsc{Functional Dependency}\xspace (in that order) for \emph{minimum} dependencies
described in \Cref{lem:hs_to_unique,lem:unique_to_fd}
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 \emph{minimal} dependencies
are in fact parsimonious reductions from \textsc{Transversal Hypergraph}\xspace to \textsc{Enumerate Minimal UCCs}\xspace and
further to \textsc{Enumerate Minimal FDs/FDs}\textsubscript{\textit{fixed RHS}}.
Regarding the inverse direction, \Cref{obs:UCCs_and_transversals}
shows that the enumeration of UCCs is at most as hard as that of hitting sets,
that is, \textsc{Enumerate Minimal UCCs}\xspace and \textsc{Transversal Hypergraph}\xspace 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) \emph{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 \Cref{thm:equiv_transHyp},
we still need the following lemma that characterizes the
complexity of functional dependency discovery
in terms of the \textsc{Transversal Hypergraph Union}\xspace problem.

\begin{lem}
\label[lem]{lem:parsimonious_transHyp_union}
	The problems \emph{\textsc{Enumerate Minimal FDs}\xspace} and \emph{\textsc{Transversal Hypergraph Union}\xspace} are equivalent under parsimonious reductions.
	Moreover, there is a parsimonious reduction from \emph{\textsc{Enumerate Minimal FDs}\textsubscript{\textit{fixed RHS}}\xspace} to \emph{\textsc{Transversal Hypergraph}\xspace}.
\end{lem}

\begin{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 \emph{punctured difference set} to be $D(r,s){\setminus}\{a\}$.
	It is implicit in the proof of \Cref{lem:fd_to_ws2}\hspace*{.25pt}--\hspace*{.25pt}{}and
	easy to verify from the definition of functional dependencies\hspace*{.25pt}--\hspace*{.25pt}{}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 \textsc{Enumerate Minimal FDs}\xspace problem to \textsc{Transversal Hypergraph Union}\xspace.
	In the same fashion, fixing the desired right-hand side in the input reduces
	\textsc{Enumerate Minimal FDs}\textsubscript{\textit{fixed RHS}}\xspace to \textsc{Transversal Hypergraph}\xspace.

	\begin{figure}
\centering
	\includegraphics[page=1,scale=.93]{transHyp_union-fd-reduction}
	\caption{Illustration of \Cref{lem:parsimonious_transHyp_union}.
		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
		$\Tr(\mathcal{H}_1) = \{ \{a,c\}, \{b\}\}$,
		$\Tr(\mathcal{H}_2) = \{ \{b\}, \{c,b\}, \{c,e\}\}$,
		and $\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$.}
\label{fig:transHyp_union}
\end{figure}

	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 \Cref{fig:transHyp_union}.
	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 \Cref{lem:hs_to_unique}.
	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$,
	\begin{equation*}
		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}
	\end{equation*}
	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 \Cref{lem:unique_to_fd}~\ref{case:fdfixed_to_fd}.
	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}\xspace(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 \Tr(\mathcal{H}_i)$.
	The existence of a parsimonious reduction from \textsc{Transversal Hypergraph Union}\xspace to \textsc{Enumerate Minimal FDs}\xspace easily follows from that.
	Let $X \subseteq R$ and \mbox{$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 \le i \le 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 \le j \le m$.
	The rows $r$ and $s$ share only the value $0$, if any.
	Therefore,
	\begin{equation*}
		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\,{\le}\,k\,{\le}\,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}
	\end{equation*}
	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 $\Tr(\mathcal{D}_{x_i}) = \Tr(\mathcal{H}_i)$
	are the same.
\end{proof}

It is known that \textsc{Enumerate Minimal FDs}\xspace can be solved in output-polynomial time
if and only if \textsc{Transversal Hypergraph}\xspace can~\cite{EiterGottlob95RelatedProblems},
this has been established along the same lines as discussed in the remarks
preceding~\Cref{lem:parsimonious_transHyp_union}.
Notably, Eiter and Gottlob additionally presented an alternative construction
in the extended version of~\cite{EiterGottlob95RelatedProblems}
that is \emph{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 $\Or(|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.

\section{Inclusion Dependencies}
\label{sec:INDs}

\noindent
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}\xspace[3]$.
We do so by proving its FPT-equivalence
with the weighted satisfiability problem for a certain fragment of propositional logic.
Later in \Cref{subsec:IND_discovery}, we transfer our results
to the discovery of maximal inclusion dependencies.

\subsection{Problem Definitions}
\label{subsec:IND_problem_definitions}

\noindent
A Boolean formula is \emph{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 \mbox{$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
\begin{equation*}
	((\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)).
\end{equation*}
This formula admits satisfying assignments of Hamming weight~$0$, $1$, and $2$, but none of larger weight.

The \textsc{Weighted Antimonotone $3$-normalized Satisfiability}\xspace problem is the special case of \WS{3}
restricted to antimonotone formulas.

\vspace*{.6em}
\noindent\textsc{Weighted Antimonotone $3$-normalized Satisfiability}\xspace (\textsc{WA$3$NS}\xspace)
\begin{description}
	\item [Instance:] An antimonotone, $3$-normalized Boolean formula $\varphi$

		and a non-negative integer $k$.
	\item [Parameter:] The non-negative integer $k$.
	\item [Decision:] Does $\varphi$ admit a satisfying assignment of Hamming weight $k$?
\end{description}

\noindent
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~\cite{DowneyFellows95FPTCompletenessI,DowneyFellows95FPTCompletenessII}
implies that the \textsc{WA$3$NS}\xspace special case is \mbox{$\textsf{W}\xspace[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.

\vspace*{.6em}
\noindent\textsc{Enumerate Maximal Satisfying \textsc{WA$3$NS}\xspace Assignments}\xspace
\begin{description}[labelwidth = 2.45cm]
	\item [Instance:] An antimonotone, $3$-normalized Boolean formula $\varphi$.
	\item [Enumeration:] List all maximal satisfying assignments of $\varphi$.
\end{description}

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.

\vspace*{.6em}
\noindent\textsc{Inclusion Dependency}\textsubscript{\textit{Identity}}\xspace
\begin{description}
	\item [Instance:] Two relational databases $\mathfrak{r}$, $\mathfrak{s}$ over schema $R$

		and a non-negative integer $k$.
	\item [Parameter:] The non-negative integer $k$.
	\item [Decision:] Is there a set $X \subseteq R$ with $|X| = k$ such that

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

\vspace*{.6em}
\noindent\textsc{Inclusion Dependency}\xspace
\begin{description}
	\item [Instance:] Two relational databases, $\mathfrak{r}$ over schema $R$ and $\mathfrak{s}$ over $S$,

			and a non-negative integer $k$.
	\item [Parameter:] The non-negative integer $k$.
	\item [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?
\end{description}

\noindent
The unparameterized variant of the general \textsc{Inclusion Dependency}\xspace problem is \textsf{NP}\xspace-complete
already for pairs of binary databases~\cite{Kantola92FDsAndINDs}.

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

\vspace*{.6em}
\noindent\textsc{Enumerate Maximal INDs}\textsubscript{\textit{Identity}}\xspace
\begin{description}[labelwidth = 2.45cm]
	\item [Instance:] Two relational databases $\mathfrak{r}$, $\mathfrak{s}$ over the same schema.
	\item [Enumeration:] List all maximal valid inclusion dependencies between $\mathfrak{r}$ and $\mathfrak{s}$

		\hspace*{0.3cm} with the identity mapping between the columns.
\end{description}

\vspace*{.6em}
\noindent\textsc{Enumerate Maximal INDs}\xspace
\begin{description}[labelwidth = 2.45cm]
	\item [Instance:] Two relational databases $\mathfrak{r}$ and $\mathfrak{s}$.
	\item [Enumeration:] List all maximal valid inclusion dependencies between $\mathfrak{r}$ and~$\mathfrak{s}$.
\end{description}

\subsection{Membership in $W[3]$}
\label{subsec:ind-is-in-w3}

\noindent
We show that both variants of the \textsc{Inclusion Dependency}\xspace decision problem are contained in the class $\textsf{W}\xspace[3]$.
Recall that the \textsc{Inclusion Dependency}\textsubscript{\textit{Identity}}\xspace 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.

\begin{lem}
\label[lem]{lem:ind-with-or-without-mapping}
	There is a parameterized reduction from \emph{\textsc{Inclusion}}
	\emph{\textsc{Depen\-dency}\textsubscript{\textit{Identity}}} to \emph{\textsc{Inclusion Dependency}\xspace}.
\end{lem}

\begin{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.
\end{proof}

To demonstrate the membership of the general problem in $\textsf{W}\xspace[3]$, we reduce is to \textsc{WA$3$NS}\xspace.
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 \emph{pairs} of attributes and Boolean variables.

\begin{lem}
\label[lem]{lem:ind-to-wans-without-mapping}
 	There is a parameterized reduction from \emph{\textsc{Inclusion Dependency}\xspace} to \emph{\textsc{Weighted Antimonotone $3$-normalized Satisfiability}\xspace}.
\end{lem}

\begin{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 $\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 $\var{R \times S}$
	and the truth assignments obtained this way.
	Moreover, these assignments all satisfy the following antimonotone Boolean formula $\varphi_{map}$.
	\begin{align*}
		\varphi_{map} =
			\left(\bigwedge_{i = 1}^{|R|} \bigwedge_{j = 1}^{|S| - 1} \bigwedge_{j' = j+1}^{|S|}
				(\neg x_{i, j} \vee \neg x_{i, j'})\right)
			\  \wedge \
			\left(\bigwedge_{j = 1}^{|S|} \bigwedge_{i = 1}^{|R| - 1} \bigwedge_{i' = i+1}^{|R|}
				(\neg x_{i, j} \vee \neg x_{i', j})\right).
  \end{align*}

	\noindent
	The first half of $\varphi_{map}$ expresses that,
	for every pair of variables $x_{i, j}$ and $x_{i, j'}$ with $j \neq j'$,
	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', j}$
	with $i \neq i'$.
	Conversely, a satisfying assignment $A$ (a subset of $\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 \le j \le |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 \emph{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 \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
    \begin{align*}
    	\varphi = \bigwedge_{r_{\ell} \in \mathfrak{r}} \bigvee_{s_m \in \mathfrak{s}} M_{\ell, m}
	\end{align*}
	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 $\Or(|R|^2 |S| + |R||S|^2)$
	and all sets $F_{\ell,m}$ together are computable in time $\Or(|\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.
\end{proof}

\subsection{Hardness for $W[3]$}
\label{subsec:ind-w3-hard}

\noindent
We now show that detecting inclusion dependencies is also hard for $\textsf{W}\xspace[3]$.
We argue that the existence of weighted satisfying assignments
for \mbox{3-normalized}, antimonotone formulas can be decided by solving instances of
the more restricted \textsc{Inclusion Dependency}\textsubscript{\textit{Identity}}\xspace 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 \emph{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 \textsc{WA$3$NS}\xspace to the \textsc{Inclusion Dependency}\textsubscript{\textit{Identity}}\xspace problem.
The remainder of this section is dedicated to proving this claim.
Recall that the top level connective of a \mbox{3-normalized} formula is a conjunction.
We start by demonstrating how to model this using databases.

\begin{lem}
\label[lem]{lem:ind-hardness_conjunction}
	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)}$.
\end{lem}

\begin{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 \emph{every} record $s \in \mathfrak{s}$.
\end{proof}

One could hope that there is a similar method treating disjunctions.
However, we believe that there is none that is both computable in \mbox{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 \mbox{FPT-time} procedures of constructing conjunctions as well as disjunctions,
one could encode antimonotone Boolean formulas of arbitrary logical depth.
The Antimonotone Collaps Theorem~\cite{DowneyFellows13Parameterized},
states that the \textsc{Weighted Antimonotone $t$-normalized Satisfiability} problem
is $\textsf{W}\xspace[t]$-complete for every odd $t \ge 3$.
This would then render \textsc{Inclusion Dependency}\textsubscript{\textit{Identity}}\xspace to be hard for all classes $\textsf{W}\xspace[t]$ and,
as a consequence of \Cref{lem:ind-to-wans-without-mapping,lem:ind-with-or-without-mapping},
the $\textsf{W}\xspace$-hierarchy would collapse to its third level.
That being said, there is a method specifically tailored to antimonotone DNF formulas.

\begin{lem}
\label[lem]{lem:ind-hardness_DNF}
	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})}$.
\end{lem}

\begin{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 \Cref{lem:hs_to_unique}, as
	\begin{equation*}
		r_j[a_i] =
			\begin{cases}
				j, & \text{if variable } x_i \text{ occurs in } M_j;\\
				0, & \text{otherwise.}
			\end{cases}
	\end{equation*}
	See \Cref{fig:ind-hardness} for an example.

	\begin{figure}
	\centering
	\includegraphics[page=1,scale=1.1]{ind-hardness}
	\caption{Illustration of \Cref{lem:ind-hardness_DNF}.
		The antimonotone DNF formula $\varphi$ on the left
		has the three conjunctive clauses $M_1, M_2, M_3$.
		The equivalent instance of \textsc{Inclusion Dependency}\textsubscript{\textit{Identity}}\xspace 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.
	}
\label{fig:ind-hardness}
\end{figure}

	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 \mbox{$j$-th} copy of $\mathfrak{r}$, we set the value for attribute $a_i$ to $\times$
	whenever $x_i$ occurs in $M_j$.
	(See \Cref{fig:ind-hardness} 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 \mbox{$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$.
\end{proof}

\Cref{lem:ind-hardness_conjunction,lem:ind-hardness_DNF} imply that,
given an antimonotone, \mbox{3-normalized} formula $\varphi$,
we can build an instance $(\mathfrak{r}, \mathfrak{s})$ of \textsc{Inclusion Dependency}\textsubscript{\textit{Identity}}\xspace in \mbox{FPT-time} (even polynomial)
such that $f_\varphi = f_{(\mathfrak{r}, \mathfrak{s})}$.
Together with the findings of \Cref{subsec:ind-is-in-w3},
this finishes the proof of \Cref{thm:ind_W[3]}.

\subsection{Discovery}
\label{subsec:IND_discovery}

\noindent
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, \mbox{3-normalized} formulas, as detailed in \Cref{thm:enum_ind}.
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.

\Cref{lem:ind-hardness_conjunction,lem:ind-hardness_DNF}
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 $\var{\varphi}$,
such that the inclusion dependencies $X \subseteq R$ are in canonical
correspondence with the satisfying assignments $A \subseteq \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, \Cref{lem:ind-hardness_conjunction,lem:ind-hardness_DNF}
induce a parsimonious reduction from \textsc{Enumerate Maximal Satisfying \textsc{WA$3$NS}\xspace Assignments}\xspace to \textsc{Enumerate Maximal INDs}\textsubscript{\textit{Identity}}\xspace.
It is also easy to see that \Cref{lem:ind-with-or-without-mapping}
implies a parsimonious reduction from the enumeration
of such restricted inclusion dependencies to the general \textsc{Enumerate Maximal INDs}\xspace problem.
The lemma does nothing else but invalidating all non-identity
mappings between the columns.
Finally, \Cref{lem:ind-to-wans-without-mapping} 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 \Cref{subsec:prelims_databases,subsec:IND_problem_definitions} 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 \Cref{thm:enum_ind} by showing that the problems
are at least as hard as \textsc{Transversal Hypergraph}\xspace.
This is an easy exercise using the structure of antimonotone CNFs.

\begin{lem}
\label[lem]{lem:enum_ind_transversal_hard}
	The enumeration of maximal satisfying assignments of antimonotone Boolean formulas
	in conjunctive normal form
	is equivalent to \emph{\textsc{Transversal Hypergraph}\xspace} under parsimonious reductions.
	In particular, \emph{\textsc{Enumerate Maximal Satisfying \textsc{WA$3$NS}\xspace Assignments}\xspace} is at least as hard as the \emph{\textsc{Transversal Hypergraph}\xspace} problem.
\end{lem}

\begin{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 $\var{\varphi}$ be the set of all variables of $\varphi$
 	and $C_1, \dots, C_m \subseteq \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 \var{\varphi}$ (the set of \true variables)
	is satisfying iff its complement $\overline{A} = \var{\varphi}{\setminus}\hspace*{.1em}{A}$
	is a hitting set of the hypergraph $\{C_i\}_{i \in [m]}$.
	Assignment $A$ is maximal in that regard iff $\overline{A} \in \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.
\end{proof}

\section{Conclusion}
\label{sec:conclusion}

\noindent
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 $\textsf{W}\xspace$-hierarchy at least partially collapses.
In fact, the detection of inclusion dependencies turned out to be surprisingly hard
in that it is $\textsf{W}\xspace[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 \emph{other} parameters.
As an example, \textsc{Unique Column Combination}\xspace on databases over schema $R$
are trivially in \textsf{FPT}\xspace 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~\cite{Abedjan18DataProfiling,Papenbrock16HyFD,Wei19DiscoveryEmbeddedUnique}.
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.

\section*{Ackowledgements}

\noindent
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.

\bibliographystyle{plainurl}

redpajama_set_name: RedPajamaArXiv


'Old tight Astley, 'ee's got a pumpee.
This entry was written by NeiloMac, posted on November 21, 2017 at 7:41 pm, filed under Video and tagged video, youtube. Bookmark the permalink. Follow any comments here with the RSS feed for this post.


Jakob Brøchner Madsen (born in Randers, Denmark) is an economist, professor and former financial analyst and deputy chief economist (Bank of Jutland). He was one of few economist who predicted the IT bubble in 2001 and the housing bubble in 2006 and the global financial crisis.
He received his PhD in 1991. Since completing his PhD he has held lecturing positions at the University of Southampton, University of Western Australia and Flinders University and professorial positions at Brunel University, London, and University of Copenhagen. Since joining Monash University in 2006 he has been the coordinator of the Caulfield Campus.
He has published more than 60 papers in international refereed journals including Journal of Economic Growth, Journal of Monetary Economics, Review of Economics and Statistics, Economic Journal, Journal of Development Economics, Journal of International Economics, Economica, Journal of Economic History, Scandinavian Journal of Economics, Economics Letters, Journal of International Money and Finance, Southern Economic Journal and Explorations in Economic History. The research areas are in macroeconomics, economic growth, macrofinance, applied econometrics, and the macroeconomics of the Great Depression.
He was ranked as number 949 in the world of the 55000+ economists who published at least one JEL classified article over the period from 1994 to 1998, according to a recent study funded by the European Economic Association.
^ Bezemer, Dirk J (25 Jun 2009). ""No One Saw This Coming": Understanding Financial Crisis Through Accounting Models". Munich Personal RePEc Archive. Retrieved September 20, 2011.


A trail blazing relationship podcast for growth-development oriented people who want a deeply fulfilling long-term relationship. Here we re-write the outdated nonsense of marriage and monogamy and offer you practical, easy to apply tools so you can get the kind of relationship you deserve and then strengthen it over time. Your host Jayson Gaddis once again shares his own traumas and triumphs on the way to "winning*" in marriage (*winning means he can get his connection needs met without compromising his values or integrity). Join him, his wife, and many other relationship geeks as they explore the next chapter of modern monogamy.
In this episode I explain how society and culture play an massive role in the indoctrination of men from a young age, which keeps their hearts behind a giant wall. From a young age, boys learn to repress and hide their emotions and their sensitive side in order to belong to the peer group, their family, and avoid rejection and abandonment.


Swimming Pool Designs And Prices Pools Modern Inground Ideas Awesome is part of great design ideas. Swimming Pool Designs And Prices Pools Modern Inground Ideas Awesome was created by combining fantastic ideas, interesting arrangements, and follow the current trends in the field of that make you more inspired and give artistic touches. We'd be honored if you can apply some or all of these design in your wedding. believe me, brilliant ideas would be perfect if it can be applied in real and make the people around you amazed!
Swimming Pool Designs And Prices Pools Modern Inground Ideas Awesome was posted in March 18, 2019 at 12:42 pm. Swimming Pool Designs And Prices Pools Modern Inground Ideas Awesome has viewed by 5 users. Click it and download the Swimming Pool Designs And Prices Pools Modern Inground Ideas Awesome.
Pool, Public Swimming Pool Design was posted December 17, 2018 at 8:46 pm by soulpower.info . More over Public Swimming Pool Design has viewed by 409 visitor.
Pool, Indoor Swimming Pool Design was posted February 27, 2019 at 6:19 pm by soulpower.info . More over Indoor Swimming Pool Design has viewed by 801 visitor.
Backyard, Swimming Pool Ideas For Backyard was posted November 18, 2018 at 3:02 am by soulpower.info . More over Swimming Pool Ideas For Backyard has viewed by 871 visitor.
Pool, Swimming Pool Fountain Ideas was posted February 9, 2019 at 3:05 am by soulpower.info . More over Swimming Pool Fountain Ideas has viewed by 373 visitor.
Pool, Free Swimming Pool Design Software was posted October 29, 2018 at 8:50 pm by soulpower.info . More over Free Swimming Pool Design Software has viewed by 496 visitor.
Pool, Swimming Pool Design Pdf was posted December 14, 2018 at 1:39 am by soulpower.info . More over Swimming Pool Design Pdf has viewed by 400 visitor.
Pool, Small Swimming Pool Ideas was posted November 17, 2018 at 1:56 am by soulpower.info . More over Small Swimming Pool Ideas has viewed by 646 visitor.
Pool, Swimming Pools Designs was posted October 10, 2018 at 5:57 am by soulpower.info . More over Swimming Pools Designs has viewed by 675 visitor.
Backyard, Backyard Swimming Pool Ideas was posted November 4, 2018 at 8:22 pm by soulpower.info . More over Backyard Swimming Pool Ideas has viewed by 875 visitor.
Pool, Swimming Pool Ideas For Backyard was posted March 1, 2019 at 3:11 am by soulpower.info . More over Swimming Pool Ideas For Backyard has viewed by 843 visitor.