  The task of computing homomorphisms between two finite relational structures
$\mathcal{A}$ and $\mathcal{B}$ is a well-studied question with numerous
applications. Since the set $\operatorname{Hom}(\mathcal{A},\mathcal{B})$ of
all homomorphisms may be very large having a method of representing it in a
succinct way, especially one which enables us to perform efficient enumeration
and counting, could be extremely useful.
  One simple yet powerful way of doing so is to decompose
$\operatorname{Hom}(\mathcal{A},\mathcal{B})$ using union and Cartesian
product. Such data structures, called d-representations, have been introduced
by Olteanu and Zavodny in the context of database theory. Their results also
imply that if the treewidth of the left-hand side structure $\mathcal{A}$ is
bounded, then a d-representation of polynomial size can be found in polynomial
time. We show that for structures of bounded arity this is optimal: if the
treewidth is unbounded then there are instances where the size of any
d-representation is superpolynomial. Along the way we develop tools for proving
lower bounds on the size of d-representations, in particular we define a notion
of reduction suitable for this context and prove an almost tight lower bound on
the size of d-representations of all $k$-cliques in a graph.
