  Multi-column dependencies in relational databases come associated with two
different computational tasks. The detection problem is to decide whether a
dependency of a certain type and size holds in a given database, the discovery
problem asks to enumerate all valid dependencies of that type. We settle the
complexity of both of these problems for unique column combinations (UCCs),
functional dependencies (FDs), and inclusion dependencies (INDs). We show that
the detection of UCCs and FDs is W[2]-complete when parameterized by the
solution size. The discovery of inclusion-wise minimal UCCs is proven to be
equivalent under parsimonious reductions to the transversal hypergraph problem
of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs
is equivalent to the simultaneous enumeration of the hitting sets of multiple
input hypergraphs. We further identify the detection of INDs as one of the
first natural W[3]-complete problems. The discovery of maximal INDs is shown to
be equivalent to enumerating the maximal satisfying assignments of
antimonotone, 3-normalized Boolean formulas.
