7.12

Let \(R_1, R_2, ..., R_n\) be a decomposition of schema \(U\). Let \(u(U)\) be a relation, and let \(r_i = \Pi_{R_i}(u)\). Show that \[ u \subseteq r_1 \bowtie r_2 \bowtie ... \bowtie r_n \]

---

Consider some tuple \(t\) in \(u\).

Note that \(r_i = \Pi_{R_i}(u)\) implies that \(t[R_i] \in r_i, 1 \leq i \leq n\). Thus,

\[ t[R_1] \bowtie t[R_2] \bowtie ... \bowtie t[R_n] \in r_1 \bowtie r_2 \bowtie ... \bowtie r_n \]

By the definition of natural join,

\[ t[R_1] \bowtie t[R_2] \bowtie ... \bowtie t[R_n] = \Pi_\alpha(\sigma_\beta(t[R_1] \times t[R_2] \times ... \times t[R_n])) \]

where the condition \(\beta\) is satisfied if values of attributes with the same name in a tuple are equal and where \(\alpha = U\). The Cartesian product of single tuples generates one tuple. The selection process is satisfied because all attributes with the same name must have the same value since they are projections from the same tuple. Finally, the projection clause removes duplicate attribute names.

By the definition of decomposition, \(U = R_1 \cup R_2 \cup ... \cup R_n\), which means that all attributes of \(t\) are in \(t[R_1] \bowtie t[R_2] \bowtie ... \bowtie t[R_n]\). That is, \(t\) is equal to the result of this join.

Since \(t\) is any arbitrary tuple in \(u\),

\[ u \subseteq r_1 \bowtie r_2 \bowtie ... \bowtie r_n \]