Determine the smallest cardinal of $D$ satisfying certain requirement. Define the composition of two relation $R\subset A\times B$, and $S\subset B\times C$, as $(a,c)\in R\cdot S$ iff $\exists b ((a,b)\in R\land(b,c)\in S)$. My question is  given  a relation $R$, what is the smallest cardinal of a set $D$ for the  relation $R\subset A\times B$, such that there exists two relation $S\subset A\times D,K\subset D\times B$ such that $R=S\cdot K$?
Is there any construction of the set $D$?
 A: At most the cardinality of $R$, since you can define the relation $S$ in $A\times R$, for $(a,(b,c))\in S\iff a=b$ and the relation $K$ in $R\times B$, $((a,b),c)\in K,\iff b=c$, then, $R=S\cdot K$.
My guess is the smallest cardinal of $I$, where $I$ is any indexing set such that $\{A_i\}_{i\in I}$ and $\{B_i\}_{i\in I}$ are a family of subset of $A$ and $B$, respectively, and $R=\bigcup\limits_{i\in I}A_i\times B_i$. Then you can define the relations $S\subset A\times I,K\subset I\times B$, such that $(a,i)\in S\iff a\in A_{i}$ and $(i,b)\in K\iff b\in B_i$ (so, you have $R=S\cdot K$). (of course, this cardinality isn't so easy to compute...)
A: 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$.
