CSE 350, Fall 2003
Dina Q Goldin

Prove the following identity:

s_F (p_A (R)) = p_A (s_F (R)), provided that F only mentions attributes in the set A.

• Let t be a tuple in s_F (p_A(R))

• By definition of selection, this is the same as saying that t is in (p_A (R)) and F(t) is true.

• By definition of projection, this is the same as saying that for some t’ in R, t = t’[A], and F(t) is true.

• Since F only mentions attributes from A this is the same as saying that for some t’ in R, t = t’[A], and F(t’) is true.

• By definition of selection, this is the same as saying that for some t’ in R, t = t’[A], and t’ in s_F(R).
• By definition of projection, this is the same as saying that t is in p_A (s_F(R)).