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

- for SQL, first translate SQL to TA
- then find the minimal possible SPJ Expression
- translate it as suggested below

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

- step 1:

- for each relation we create an atom in body with distinct variables

- step 2:

- for all the conditions of the selection part we replace the variables that participate in equations by the same symbol

in this case

- step 1:
- $

\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} $

- in the head we put what we want to see in the output, i.e. the variables specified in the projection
- variable names like $x_{R_1.A}$ are helpful to keep track of the original names, however it could be anything
- this query now computes $\rho_{R_1}(R) \times \rho_{R_2}(R) \times \rho_{R_3}(R) \times \rho_{S_1}(S) \times \rho_{S_2}(S)$

- step 2
- we restrict the query so it outputs only the tuples that match the selection condition
- for that for every equality we replace all the occurrence of variables in that inequality to the same variable

- the name does not matter
- for constants we put the value of a constant
- $

\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} $

- here ${\color{grey}{|^{(i)}}}$ shows what part of the condition was used to do the replacement

- now this is equivalent to the RA expression

Translation from CQ back to Relational Algebra is straightforward

- the number of elements being joined is equal to the number of atoms
- i.e. the number of joins is (# of atoms) - 1

- we then add the selection
- with an equality condition for each variable name (if repeated 2 or more times)
- and for each constant

- finally, only the variables in the head get projected
- of course, we need to know the relational schema to be able to do that
- note that in CQ we use positions to denote attributes

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

- $\pi_\text{S.movieTitle}

\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)$

- Database Systems Architecture (ULB)
- Database Systems Architecture lecture notes #2 by S. Vansummeren [1]