This describes translation algorithms from Relational Algebra to Conjunctive Queries and vise-versa
We can translate a Relational Algebra expression that is in Select-Project-Join form into CQ. Note that it is not possible to translate any other form to it
Suppose we have the following logical query plan:
$ \pi_{
\begin{subarray}{l} R_1.A, \\ S_1.B \\ \end{subarray}
} \sigma_{
\begin{subarray}{l} {\color{grey}{(1)}} \ R_1.A = R_2.A \ \land \\ {\color{grey}{(2)}} \ R_2.B = 4 \ \land \\ {\color{grey}{(3)}} \ R_2.A = R_3.A \ \land \\ {\color{grey}{(4)}} \ R_3.B = S_1.B \ \land \\ {\color{grey}{(5)}} \ S_1.C = S_2.C \ \land \\ {\color{grey}{(6)}} \ S_2.B = 4 \end{subarray}
} \big( \rho_{R_1}(R) \times \rho_{R_2}(R) \times \rho_{R_3}(R) \times \rho_{S_1}(S) \times \rho_{S_2}(S) \big)$
We proceed as follows
in this case
\begin{array}{l l} Q(x_{R_1.A}, y_{S_1.B}) \leftarrow &
R(x_{R_1.A}, y_{R_1.B}), \\
& R(x_{R_2.A}, y_{R_1.B}), \\ & R(x_{R_3.A}, y_{R_3.B}), \\ & R(y_{S_1.B}, z_{S_1.C}), \\ & R(y_{S_2.B}, z_{S_2.C}) \\ \end{array} $
\begin{array}{l l} Q(x_{R_1.A}, y_{S_1.B}) \leftarrow &
R(x_{R_1.A} {\color{grey}{|^{(1)}}}, y_{R_1.B}), \\
& R(x_{R_1.A} {\color{grey}{|^{(1,3)}}}, 4 {\color{grey}{|^{(2)}}}), \\ & R(x_{R_1.A} {\color{grey}{|^{(3)}}}, y_{R_3.B} {\color{grey}{|^{(4)}}}), \\ & R(y_{R_3.B} {\color{grey}{|^{(4)}}}, z_{S_1.C} {\color{grey}{|^{(5)}}}), \\ & R(4 {\color{grey}{|^{(6)}}}, z_{S_1.C} {\color{grey}{|^{(5)}}}) \\ \end{array} $
Translation from CQ back to Relational Algebra is straightforward
Given: $Q(t) \leftarrow \text{MovieStar}({\color{red}{n}}, a, g, {\color{blue}{1940}}), \text{StarsIn}(t, y, {\color{red}{n}})$
We translate it as
\sigma_{
\begin{subarray}{l} \text{M.name = S.starName } \land \\ \text{M.birthDate = 1940} \\ \end{subarray}
} \big( \rho_M(\text{MovieStar}) \times \rho_S(\text{StarsIn}) \big)$