# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1337436733 -7200
# Node ID 5df1620cfa5027b651c86cd0ac8ed14d0c823e0a
# Parent  05bd6cb31abc68dfe87a7d498175efe67eb562e2
Really final ex3.

diff -r 05bd6cb31abc -r 5df1620cfa50 exercises/solutions/sol03.pdf
Binary file exercises/solutions/sol03.pdf has changed
diff -r 05bd6cb31abc -r 5df1620cfa50 exercises/solutions/sol03.tex
--- a/exercises/solutions/sol03.tex	Sat May 19 04:25:58 2012 +0200
+++ b/exercises/solutions/sol03.tex	Sat May 19 16:12:13 2012 +0200
@@ -82,20 +82,21 @@
 \end{figure}
 
 \section*{Exercise 3.3}
+There are more trivial examples with the required properties and it would be easier to prove the properties on them in a formal way. However, we tried to find an example, which works for all three parts of this exercise with minimal modifications. We traded off formal proofs for intuitive understanding of the underlying differences between these relations.\\\\
 (a) Let $R_S$ be the relation with $S=(x_1,...,x_n)$ for the constraint $x_1 > \sum_{i=2}^{n}x_i$ over the domains $D_i = \{0,1,2\}$, i.e., $R_S = \{(1,0,...,0)\} \cup \{(2,(x_i)_{1<i\leq n}) \mid \sum_{i=2}^{n}x_i < 2\}$ or more graphically $R_S = \{(1,0,...,0),$ $(2,0,...,0,1,0,...,0),(2,1,0,...,0), (2,0,...,0,1)\}$.
 
 The projection network of $R_S$ is by definition $Proj(R_S) = \langle S, D_i = \pi_{x_i}(R_S), R_{x_i,x_j}' = \pi_{x_i,x_j}(R_S)\rangle$ with $R'_{x_1,x_j} = \{(1,0),(2,0),(2,1)\}$ and for $i \neq 1$ holds $R'_{x_i,x_j}=\{(0,0),(0,1),(1,0)\}$.
 
-The limited domains impose transitive relations $x_1 > x_i$ for all $1 < i \leq n$ and $x_i = x_j = 0 \lor x_i \neq x_j$ for $i \neq 1$. Since this imposed relations essentially reduce the contraint to the mentioned binary relations it follows that all solutions of the projection network are also in the relation, i.e., $Sol(Proj(R_S)) = R_S$.
+The limited domains impose transitive relations $x_1 > x_i$ for all $1 < i \leq n$ and $x_i = x_j = 0 \lor x_i \neq x_j$ for $i \neq 1$. Since this imposed relations essentially reduce the contraint to the mentioned binary relations $R'$ it follows that all solutions of the projection network are also in the relation, i.e., $Sol(Proj(R_S)) = R_S$.
 
 All projections of $R_S$ to a subset of $S$, so that $x_1$ is contained, basically reduces the network to the projection size, all properties remain unchanged, therefore the projection network of the projection of $R_S$ has only solutions which are in the projected relation (and vice versa).
 
-All projections of $R_S$ to a subset of $S$ without $x_1$ mean a reduction to the constraint $2 > \sum_{i=1}^{m}x_i$ where m is the projections size. This has obviously also a binary representation with $R'_{x_i,x_j} = \{(0,0),(1,0),(0,1)\}$. Again it follows that the projection network of this projection has only solutions which are in the projected relation (and vice versa).
+All projections of $R_S$ to a subset of $S$ without $x_1$ mean a reduction to the constraint $2 > \sum_{i=1}^{m}x_i$ where m is the projection size. This has obviously also a binary representation with $R'_{x_i,x_j} = \{(0,0),(1,0),(0,1)\}$. Again it follows that the projection network of this projection has only solutions which are in the projected relation (and vice versa).
 
 Given that the relation $R_S$ itself and all its possible projections have binary representations, it holds that $R_S$ is binary decomposable. \qed\\\\
 (c) We will do part (c) before (b) because here we use the same constraint as in part (a). However, we will expand the domains with $D_i = \{0,1,2,3\}$. This gives us the relation $R_S = \{(x_1,(x_i)_{1<i\leq n}) \mid \sum_{i=2}^{n}x_i < x_1\}$.
 
-This relation has no binary representation, because no set of binary relations can enforce the constraint for $x_1 = 3$. E.g. $(3,1,1,1,0,...,0)$ is a solution of $Proj(R_S)$, because it is consistent with the constraints $R'_{x_1,x_j}=\{(1,0),(2,0),(2,1),(3,0),(3,1),(3,2)\}$ and for $i\neq 1$ $R'_{x_i,x_j}=\{(0,0),(1,0),(0,1),(1,1),(2,0)\}$ while it is not contained in $R_S$. It follows that $R_S \neq Sol(Proj(R_S))$.
+This relation has no binary representation, because no set of binary relations can enforce the constraint for $x_1 = 3$. E.g. $(3,1,1,1,0,...,0)$ is a solution of $Proj(R_S)$, because it is consistent with the constraints $R'_{x_1,x_j}=\{(1,0),(2,0),(2,1),(3,0),(3,1),(3,2)\}$ and for $i\neq 1$ $R'_{x_i,x_j}=\{(0,0),(1,0),(0,1),(1,1),(2,0)\}$ while it is not contained in $R_S$. It follows that $R_S \subseteq Sol(Proj(R_S))$ and $R_S \neq Sol(Proj(R_S))$.
 
 We could have shown the same effect by leaving the domains untouched, but changing the constraint to $x_1 \geq \sum_{i=2}^nx_i$ instead, which has the same effect, it requires a systematic (here ternary) view over all variables. \qed\\\\
 (b) This time we modify the relation like this
@@ -104,5 +105,5 @@
 
 This modification does not change the property of the relation to have a binary representation, because solutions to the binary constraints are exactly the variable assignments from the relation (again due to the transitive relations over $x_1$).
 
-However, if we use a projection without $x_1$, we lose our pivot variable for the otherwise separted sets of variables. Solutions to such a projection network induced by the projected relation without $x_1$ will again lack the systematic view over the separated sets of variables and their sums, which yields possible solutions which are inconsistent with the projected relation. From this follows that our modified $R_S$ has a binary representation but is not binary decomposable. \qed
+However, if we use a projection without $x_1$, we lose our pivot variable for the otherwise separted sets of variables. Solutions to such a projection network induced by the projected relation without $x_1$ will again lack the systematic view over the separated sets of variables and their sums, which yields possible solutions which are inconsistent with the projected relation. From this follows that our modified $R_S$ has a binary representation but is not binary decomposable. \qed\\\\
 \end{document}