Transformation rules for relational algebra

The transformation rules are used to formulate a relational algebra expression into different ways and query optimizer choose the most efficient equivalent expression to execute. Two expressions are considered to be equivalent if they have same set of attributes in different order but  representing  the  same information.

Let us  consider relations R,  S, and  T  with set  of  attributes

respectively, where X, Y, and Z represent predicates and L,L1, L2, M, M1, M2, and N denote sets of attributes.

Rule 1. Cascading of selection (σ)

It means that conjunctive selection operations can be transformed into individual selection operations and vice versa.

Ex.                           

Rule 2. Commutativity of selection (σ)

Rule 3.  Cascading of  projection (π)

Rule 4.  Commutativity  of selection  (σ)  and  projection (π)

Rule 5. Commutativity of join () and Cartesian Product (X)

Rule 6. Commutavity of selection (σ) and join () or Cartesian product (X)

Rule 7. Commutavity of projection (π) and join () or Cartesian product (X).

Rule 8. Commutativity of Union () and Intersection ()

R S = S R

R S = S R

Rule 9. Commutativity of Selection (σ) and Union () or Intersection () or Differerence (–).

Rule 10.  Comutativity of  projection  (π) and  Union  ()

Rule 11. Associativity of Join () and Cartesian product (X)

Rule 12. Associativity of Union () and Intersection ()

(R S ) T = S (R T)

(R S) T = S (R T)

Rule 13. Converting a selection (σ) and Cartesian product (X) sequence into Join ()

Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)

Leave a Reply

Your email address will not be published. Required fields are marked *