Given a relation $R$, let $R_A$ denote the set of all first coordinates of $R$. That is, $x\in R_A$ iff $xRy$ for some $y\in B$. Likewise, $R_B$ denotes the set of all second coordinates.
Then the smallest cardinal of $D$ is bounded above by $\min\{|R_A|,|R_B|\}$.
To see this is an upper bound, assume wlog $|R_A|\leq|R_B|$ and let $D=R_A$ with $S = \{(x,x)|x\in R_A\} \subseteq A\times D$ and $K = R|_{D\times B}$.
However, without more information on $R$, nothing more can be said. Here are 2 examples to justify that statement.
${}$
I claim that sometimes this bound is optimal. For let $A = B$ and $R =\{(x,x)\in A\times A\}$ and suppose $R = S\cdot K$. Then we must have $R_A = S_A$. We may assume wlog that $K_D = D$ for other wise we can replace $D$ with $K_D$. Since $R_A = S_A$, every $a\in A$ must be paired with a corresponding $d_a \in D$. Since $|D|<|A|$, there must be some $d\in D$ with at least 2 different $a$s paired with it, that is $(a_1,d)$ and $(a_2,d)$ must both be in $S$ for $a_1\neq a_2$.
Since $K_D = D$, we know we have an ordered pair of the form $(d, a_3)$. But then $R=S\cdot K$ so $(a_1,a_3)$ and $(a_2,a_3)$ are both in $R$, showing that $a_1 = a_2$, a contradiction.
${}$
I also claim that sometimes this bound is not optimal. For, let $R = A\times A$. Let $D$ be any one point set. Let $S = A\times D$ and $K = D\times A$. Then $R = S\cdot K$ while $|D| = 1$.