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} = Π_{R_{i}} (u)$ . Show that $u \subseteq r_{1} ⋈ r_{2} ⋈ . . . ⋈ r_{n}$

Consider some tuple $t$ in $u$ .

Note that $r_{i} = Π_{R_{i}} (u)$ implies that $t [R_{i}] \in r_{i}, 1 \leq i \leq n$ . Thus,

$t [R_{1}] ⋈ t [R_{2}] ⋈ . . . ⋈ t [R_{n}] \in r_{1} ⋈ r_{2} ⋈ . . . ⋈ r_{n}$

By the definition of natural join,

$t [R_{1}] ⋈ t [R_{2}] ⋈ . . . ⋈ t [R_{n}] = Π_{α} (σ_{β} (t [R_{1}] \times t [R_{2}] \times . . . \times t [R_{n}]))$

where the condition $β$ is satisfied if values of attributes with the same name in a tuple are equal and where $α = 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}] ⋈ t [R_{2}] ⋈ . . . ⋈ 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} ⋈ r_{2} ⋈ . . . ⋈ r_{n}$