Relational Algebra

• Trakteer! 🍩

<aside> 🔺 RA — the basic set of operations for relational model

</aside>

Important for:

• providing a formal foundation for relational model operations
• being used as a basis for implementing and optimizing queries by RDBMS
• being incorporated into the SQL for RDBMS

RDBMS Architecture

• SQL query — declarative query from user
• RA plan — translated into relational algebra expression
• Optimized RA plan — find logically equivalent—but more efficient—RA expression
• Execution — execute each operator of the optimized plan

RA Operations

<aside> 🔺 Binary operation — two relations $R_1(A_1,...,A_n)$ and $R_2(B_1,...,B_n)$ are said to be union compatible if they have the same degree n and if $dom(A_i)=dom(B_i)$ for $1\le i\le n$.

</aside>

Union compatibility are required for union, intersection, and set difference operators. Operators like cartesian product and join doesn't need union compatibility.

• Set operations

  • Union — $\cup$ (binary operation)
    • includes all tuples that are either in $R_1$ or $R_2$ or both without duplicate tuples
    • $R_1\cup R_2$
    • is commutative and is associative
  • Intersection — $\cap$ (binary operation)
    • includes all tuples that are in both $R_1$ and $R_2$
    • $R_1 \cap R_2$ = $R_1 - (R_1 - R_2)$
    • is commutative and associative
  • Set difference — $-$(binary operation)
    • otherwise known as difference, minus, except operation
    • includes all tuples that are in R but not in S
    • $R-S=((R \cup S)-(R-S)-(S-R))$
  • Cartesian/cross product — $\times$(binary operation)

    • combining each tuple in $R_1$ with each tuple in $R_2$

    • $R_1 \times R_2$

      👀 $Employee \times Dependents$

      👀 $People \times Students$

    • mainly used to express joins

    • useful when followed by a selection condition

• Operations for specific relational DB

  • Select — $\sigma$ (unary operation)

    • returns all tuples which satisfy a condition

    • $\sigma_{<condition>}R$

      👀 $\sigma_{salary>40000}(Employee)$

      👀 $\sigma_{name="smith"}(Employee)$

    select * 
    from students
    where gpa > 3.5;
    

    $$ \sigma_{gpa>3.5}(students) $$

    • clauses can be connected by the standard boolean operatiors and, or, not, to form a general selection condition

      👀 $\sigma_{(Dno=4 \text{ and } salary>25000) \text{ or } (Dno=5 \text{ and } salary>30000)} (Employee)$

    • a sequence of selects can be applied in any order and any cascade of select operations can then be combined into a single select operations with conjunctive AND condition.

    • select operation is commutative

  • Project — $\pi$ (unary operation)

    • select certain columns and eliminates the other columns, then removes duplicates

    • $\pi_{<attribute \ list>}(R)$

      👀 $\pi_{sname,gpa}(Students)$

      👀 $\pi_{name,salary}(Employee)$

    select distinct sname, gpa
    from students;
    

    $$ \pi_{sname, gpa}(students) $$

  • Rename — $\rho$ (unary operation)

    • changes the schema, not the instance
    • $\rho_{S(B_1,...,B_n)}(R)$ or $\rho_S(R)$ or $\rho_{(B_1,...,B_n)}(R)$
      • S: the new relation name
      • B1,...,Bn: the new attribute names
    • we care about this operator because we are working in a named perspective

    select sid as studId, sname as name, gpa as gradePtAvg
    from students;
    

    $$ \rho_{(studId, name, gradePtAvg)}(Students) $$

    • we can also break down a compositional RA by specifying intermediate result relations and renaming the relation and its attributes
    • generalized project operation also allows functions of attributes to be included in the projection list

  • Join — (binary operation)

    • (Theta) Join

      • to combine related tuples from two relations into single tuples

      • allows us to process relationship among relations

      • $R_1 ⋈_{<join \ condition>}R_2$

        👀 $Result = (People)⋈_{<Pname=Sname>}(Students)$

        this join example is called equijoin — a join operation that uses only equality comparison operator

    • (Natural) Join

      • a theta join + project operation
      • joins two relations, then use projection to select desired columns
      • $R_1*R_2$ or $R_1⋈R_2$ without join condition
      • the attributes joined must have the same name in both relations, otherwise we have to rename one of them first.

    • (Semi) Join ⋉

      • $R⋉_{<join \ condition>}S$ or $\pi_{A_1,...,A_n}(R⋈S)$

        👀 $People ⋉_{pname=sname}(Students)$

      select distinct ssn, pname, address
      from people, students
      where pname = sname;
      

      $$ People⋉_{pname,sname}Students $$

• Other

  • Division — $\div$ (binary operation)
    • $R \div S$
    • when we wish to express queries with 'all'

Things to note: