next up previous contents
Next: Model Evaluation: Up: Reconstructability Analysis (RA) Previous: Formal Definition:

Join-procedure:

Let fjoin(i) be the prior distribution from (i-1) previous joins, Vjoin(i) the variables set fjoin(i) is defined on (letting $f_{join}^{(1)} := \pi_{V_1}, \; V_{join}^{(1)}:= V_1 $). Denote the projection (subrelation, subsystem) whose information is to be added to the join as $f_{proj}^{(i+1)}:= \pi_{V_{(i+1)}}$, with Vproj(i):=Vi as its variable set. The new resulting distribution from this join is fjoin(i+1) and defined on the variable set $V_{join}^{(i+1)}=V_{proj}^{(i+1)} \cup V_{join}^{(i)}$. We define three sets of variables:

\begin{displaymath}A^{(i)}:= \{ x \in V \vert\; x \in V_{proj}^{(i+1)} \wedge x \notin V_{join}^{(i)} \} \end{displaymath}


\begin{displaymath}B^{(i)}:= \{ x \in V \vert\; x \in V_{proj}^{(i+1)} \wedge x \in V_{join}^{(i)} \} \end{displaymath}


\begin{displaymath}C^{(i)}:= \{ x \in V \vert\; x \notin V_{proj}^{(i+1)} \wedge x \in V_{join}^{(i)} \} \end{displaymath}

For the join we need to combine the two distributions fproj(i+1) and fjoin(i)over their common variable-set B(i). If $B^{(i)}= \emptyset$, then the distributions are assumed to be independent (by the model) and we obtain fjoin(i+1) by multiplying $f_{proj}^{(i+1)} \cdot f_{join}^{(i)}$. Let $ \vec{a} \in dom(A^{(i)}), \vec{b} \in dom(B^{(i)}), \vec{c} \in dom(C^{(i)})$ :

\begin{displaymath}f_{join}^{(i+1)}(\vec{a},\vec{c}) = f_{proj}^{(i+1)}(\vec{a})
\cdot f_{join}^{(i)}(\vec{c})
\end{displaymath}

Otherwise we transform fjoin(i) into a conditional distribution $\hat{f}_{join}^{(i)}(C^{(i)}\vert B^{(i)})$. For each value $\vec{b} \in dom(B^{(i)})$ we obtain a conditional distribution on dom(C(i)) (as described in section 2.3.2) by dividing:

\begin{displaymath}\hat{f}_{join}^{(i)}(\vec{c} \vert\, \vec{b} ) :=
\frac{f_{join}^{(i)}(\vec{c},\vec{b})}
{f_{join}^{(i)}( \vec{b} ) }
\end{displaymath}

Then we obtain fjoin(i+1) by:

\begin{displaymath}f_{join}^{(i+1)}(\vec{a},\vec{b},\vec{c}) = f_{proj}^{(i+1)}(...
...\vec{b})
\cdot \hat{f}_{join}^{(i)}(\vec{c} \vert \vec{b})
\end{displaymath}

By the way, $C \ne \emptyset$ because of the irredundancy condition, $A= \emptyset$ can be the case in some joins but this does not influence the described procedure.

Performing relational joins for $i=1,\ldots,m-1$ we combine the information of all projections together and in most cases end up with the maximum entropy restruction $J(\pi_M(f))= f_{join}^{(m)}$ of our simplified structure-system $\pi_M(f)$.

In some cases, when we have a so called ``loop-structure'' which means loop-dependencies in our model-structure, then fjoin(m) is only an approximation of $J(\pi_M(f))$. As $\pi_M(\:J(\pi_M(f)\:)= \pi_M(f)$, we can recognize such a situation by simply projecting fjoin(m) into our model. If there are loop-dependencies we need to continue joining the projections $f_{proj}^{(i+1)}:= \pi_{V_{((i+1)modulo\: m)}},\;
i=m,\ldots\;$ to our already obtained join-distribution fjoin(m) until we reach a close enough approximation of $J(\pi_M(f))$. This can be done following the above discussed procedures. Note that $A^{(i)}=\emptyset,\; i=m,\ldots\;$.

\begin{displaymath}\Delta_i :=\max_{j=(i-m+1),\ldots,i}\vert f_{join}^{(j)} - f_{join}^{(j-m)}\vert\:,\quad
i \ge 2\cdot m \:
\end{displaymath}

is a measure for the closeness of the approximation [26, pp. 225-227]:

\begin{displaymath}f_{join}^{(i)} - \Delta_i \le J(\pi_M(f)) \le f_{join}^{(i)} + \Delta_i \end{displaymath}

For examples on the described join procedures see also [26, pp. 223-227].


next up previous contents
Next: Model Evaluation: Up: Reconstructability Analysis (RA) Previous: Formal Definition:
Thomas Prang
1998-06-07