  The tractability of certain CSPs for dense or sparse instances is known from
the 90s. Recently, the densification and the sparsification of CSPs were
formulated as computational tasks and the systematical study of their
computational complexity was initiated.
  We approach this problem by introducing the densification operator, i.e. the
closure operator that, given an instance of a CSP, outputs all constraints that
are satisfied by all of its solutions. According to the Galois theory of
closure operators, any such operator is related to a certain implicational
system (or, a functional dependency) $\Sigma$. We are specifically interested
in those classes of fixed-template CSPs, parameterized by constraint languages
$\Gamma$, for which there is an implicational system $\Sigma$ whose size is a
polynomial in the number of variables $n$. We show that in the Boolean case,
such implicational systems exist if and only if $\Gamma$ is of bounded width.
For such languages, $\Sigma$ can be computed in log-space or in a logarithmic
time with a polynomial number of processors. Given an implicational system
$\Sigma$, the densification task is equivalent to the computation of the
closure of input constraints. The sparsification task is equivalent to the
computation of the minimal key.
