Relational Algebra: Fundamental, Additional, and Extended Operations

Introduction to Relational Algebra

Relational Algebra is a formal, procedural query language associated with the Relational Data Model. It takes one or more relations as input and produces a new relation as output.

A query in relational algebra specifies the operational steps needed to compute the desired result. The language adheres to the closure property: since the operands are relations and the output is always a relation, operations can be nested and composed into complex algebraic expressions.

+--------------------+
|  Input Relation(s) |
+--------------------+
          |
          v
+--------------------+
| Relational Algebra |  ---> [Evaluates using selection, projection, joins, etc.]
|     Operation      |
+--------------------+
          |
          v
+--------------------+
|  Output Relation   |  ---> [Satisfies closure property: can be input to next op]
+--------------------+

---

Fundamental Operations of Relational Algebra

There are six fundamental operators from which all other algebraic operations can be derived:

1. Selection ($\sigma$) — Unary
2. Projection ($\pi$) — Unary
3. Rename ($\rho$) — Unary
4. Union ($\cup$) — Binary
5. Set Difference ($-$) — Binary
6. Cartesian Product ($\times$) — Binary

1. Select Operation ($\sigma$)

The Select operation chooses horizontal subsets of tuples from a relation that satisfy a specified selection condition (predicate).

• Notation: $${\sigma }_{<\text{selection condition}>}(R)$$
• Condition Syntax: Boolean expression combining comparison operators ($=,\ne ,<,\le ,>,\ge$) and logical connectors ($\wedge ,\vee ,\neg$).
• Degree and Cardinality:
  • Degree of $\sigma (R)$ = Degree of $R$ (attribute count remains unchanged).
  • Cardinality $\le |R|$.

Example: Given relation Student(SID, SName, Dept, Year): $${\sigma }_{\text{Dept}=\text{’CSIT’}\wedge \text{Year}=4}(\text{Student})$$ This extracts all fourth-year CSIT students with all their attributes.

2. Project Operation ($\pi$)

The Project operation chooses vertical subsets of attributes from a relation, discarding all other columns. Because relations are formal mathematical sets, duplicate tuples are automatically eliminated from the resulting projection.

• Notation: $${\pi }_{<\text{attribute list}>}(R)$$
• Degree and Cardinality:
  • Degree = Number of attributes in the attribute list.
  • Cardinality $\le |R|$ (strictly less if duplicates are removed).

Example: To get only student names and departments: $${\pi }_{\text{SName, Dept}}(\text{Student})$$

3. Rename Operation ($\rho$)

The Rename operation provides an identifier to intermediate relations resulting from sub-expressions and allows renaming of attributes.

• Notation:
  • ${\rho }_S(R)$: Renames relation $R$ to $S$.
  • ${\rho }_{S(B_1,B_2,\dots ,B_n)}(R)$: Renames relation $R$ to $S$ and its attributes to $B_1,B_2,\dots ,B_n$.
  • ${\rho }_{(B_1,B_2,\dots ,B_n)}(R)$: Renames only the attributes of relation $R$.

4. Union Operation ($\cup$)

The Union of two relations $R$ and $S$ produces a relation containing all tuples that appear in $R$, in $S$, or in both. Duplicates are eliminated.

• Precondition (Union Compatibility / Type Compatibility):
  1. $R$ and $S$ must have the exact same degree (number of attributes).
  2. The domain of the $i$-th attribute of $R$ must match the domain of the $i$-th attribute of $S$ for all $1\le i\le n$.
• Notation: $$R\cup S=\{t\mid t\in R\vee t\in S\}$$

5. Set Difference Operation ($-$)

The Set Difference of $R$ and $S$ returns tuples that are present in relation $R$ but absent in relation $S$.

• Precondition: $R$ and $S$ must be union-compatible.
• Notation: $$R-S=\{t\mid t\in R\wedge t\notin S\}$$
• Note: $R-S\ne S-R$ (non-commutative).

6. Cartesian Product (Cross Product) ($\times$)

The Cartesian Product combines every tuple of relation $R$ with every tuple of relation $S$.

• Notation: $$R\times S=\{t\cdot q\mid t\in R\wedge q\in S\}$$
• Characteristics:
  • If $R$ has degree $n_1$ and cardinality $m_1$, and $S$ has degree $n_2$ and cardinality $m_2$:
  • Degree of $R\times S=n_1+n_2$.
  • Cardinality of $R\times S=m_1\times m_2$.

---

Additional (Derived) Relational Operations

These operations simplify queries and can be rewritten using the fundamental operations.

1. Set Intersection ($\cap$)

Finds tuples that belong to both relations $R$ and $S$.

• Precondition: $R$ and $S$ must be union-compatible.
• Derivation: $$R\cap S=R-(R-S)$$ $$R\cap S=(R\cup S)-(R-S)-(S-R)$$

2. Theta Join (${\bowtie }_{\theta }$)

Theta join applies a selection condition $\theta$ on the Cartesian product of two relations: $$R{\bowtie }_{\theta }S={\sigma }_{\theta }(R\times S)$$ The condition $\theta$ is of the form $R.A\text{ op }S.B$, where $\text{op}\in \{=,<,\le ,>,\ge ,\ne \}$.

3. Equijoin

A Theta join where the comparison operator across all joining attributes is strictly equality ($=$). $$R{\bowtie }_{R.A=S.B}S={\sigma }_{R.A=S.B}(R\times S)$$ The resulting relation contains duplicate attribute columns holding identical values from both relations.

4. Natural Join ($\bowtie$ or $\ast$)

Natural Join is an equijoin performed over all common attributes of relations $R$ and $S$, where duplicate join columns are projected out automatically.

• Derivation: Let $R(A_1,A_2,\dots ,A_n,C_1,C_2,\dots ,C_k)$ and $S(C_1,C_2,\dots ,C_k,B_1,B_2,\dots ,B_m)$, where $C_i$ are the common attributes. $$R\bowtie S={\pi }_{A_1,\dots ,A_n,R.C_1,\dots ,R.C_k,B_1,\dots ,B_m}({\sigma }_{R.C_1=S.C_1\wedge \cdots \wedge R.C_k=S.C_k}(R\times S))$$

Trace Example: Natural Join

Given Relations $R$ and $S$:

Table R

Table S

Result of $R\bowtie S$:

Tuple with ID = 102 is dropped because 102 does not exist in $S$. Tuple with ID = 103 is dropped because 103 does not exist in $R$.

5. Outer Joins

Outer joins preserve tuples that do not satisfy the join condition by filling missing attribute values with NULL.

• Left Outer Join ($\text{leftouterjoin}$): Retains all tuples from the left relation $R$. Tuples without a match in $S$ have NULL values for all attributes of $S$.
• Right Outer Join ($\text{rightouterjoin}$): Retains all tuples from the right relation $S$. Missing attributes from $R$ are populated with NULL.
• Full Outer Join ($\text{fullouterjoin}$): Retains all tuples from both $R$ and $S$, padding mismatches with NULL.

Left Outer Join (R =< S):
+--------------------+--------------------+
| Matches from R & S | Dangling from R    |  (S columns = NULL)
+--------------------+--------------------+

Right Outer Join (R >= S):
+--------------------+--------------------+
| Matches from R & S | Dangling from S    |  (R columns = NULL)
+--------------------+--------------------+

Full Outer Join (R =<= S):
+--------------------+--------------------+--------------------+
| Matches from R & S | Dangling from R    | Dangling from S    |
+--------------------+--------------------+--------------------+

6. Division Operation ($÷$)

The division operator applies when answering queries containing phrases like "for all" or "for every".

• Let $R(A,B)$ and $S(B)$. The relation $R÷S$ is the set of all tuples $t[A]$ such that for every tuple $u\in S$, the tuple $⟨t[A],u[B]⟩$ exists in $R$.
• Derivation using fundamental operations: $$R÷S={\pi }_A(R)-{\pi }_A(({\pi }_A(R)\times S)-R)$$

Trace Example: Division

Table Takes(StudentID, CourseID)

Table Compulsory(CourseID)

Evaluating $\text{Takes}÷\text{Compulsory}$:

1. All distinct students: ${\pi }_{\text{StudentID}}(\text{Takes})=\{S1,S2,S3\}$.
2. All combinations of students with compulsory courses: $${\pi }_{\text{StudentID}}(\text{Takes})\times \text{Compulsory}=\{(S1,C1),(S1,C2),(S2,C1),(S2,C2),(S3,C1),(S3,C2)\}$$
3. Courses not taken: $$({\pi }_{\text{StudentID}}(\text{Takes})\times \text{Compulsory})-\text{Takes}=\{(S2,C2)\}$$
4. Students missing at least one compulsory course: $${\pi }_{\text{StudentID}}(\dots )=\{S2\}$$
5. Difference gives qualified students: $$\{S1,S2,S3\}-\{S2\}=\{S1,S3\}$$

---

Extended Relational Operations

Standard relational algebra cannot compute aggregate properties (averages, counts, maximums) or retain duplicates when necessary. Extended operations address these limitations.

1. Generalized Projection

Allows arithmetic functions and expressions in the projection list: $${\pi }_{F_1,F_2,\dots ,F_n}(R)$$ Example: On relation Employee(ID, Salary, Bonus): $${\pi }_{\text{ID},(\text{Salary}+\text{Bonus})\to \text{TotalCompensation}}(\text{Employee})$$

2. Aggregate Functions and Grouping

Aggregates apply functions over collections of values from a column (e.g., COUNT, SUM, AVG, MIN, MAX).

• Notation: $${}_{<\text{grouping attributes}>}{\Im }_{<\text{aggregate function list}>}(R)$$
• If no grouping attribute is specified, the aggregate evaluates across the entire relation.

Example: Find total salary and number of instructors per department: $${}_{\text{DeptName}}{\Im }_{\text{COUNT}(\text{InstructorID})\to \text{StaffCount},\text{AVG}(\text{Salary})\to \text{AvgSal}}(\text{Instructor})$$

---

Relational Operations Comparison

---

Comprehensive Worked Exam Problems

Problem 1: School and Teacher Database

Given Relational Schema:

• TEACHER(TID, TName, TAddress, TQualification)
• SCHOOL(SID, SName, SAddress, SPhone)
• SCHOOL_TEACHER(SID, TID, No_of_Period)

Query: Retrieve the TName and No_of_Period of teachers who teach in "ABC" school.

Step-by-Step Algebraic Formulation:

1. Filter the school record for "ABC": $$R_1\leftarrow {\sigma }_{\text{SName}=\text{’ABC’}}(\text{SCHOOL})$$
2. Join with the association relation SCHOOL_TEACHER: $$R_2\leftarrow R_1\bowtie \text{SCHOOL\_TEACHER}$$
3. Join the result with TEACHER to obtain instructor details: $$R_3\leftarrow R_2\bowtie \text{TEACHER}$$
4. Project the required columns: $$\text{Result}\leftarrow {\pi }_{\text{TName, No\_of\_Period}}(R_3)$$

Single Line Expression: $${\pi }_{\text{TName, No\_of\_Period}}({\sigma }_{\text{SName}=\text{’ABC’}}(\text{SCHOOL})\bowtie \text{SCHOOL\_TEACHER}\bowtie \text{TEACHER})$$

---

Problem 2: University Student Database

Given Relational Schema:

• Student(SID, SName, Dept, Year)
• Course(CID, CName, Credit)
• Enroll(SID, CID, Grade)

Query A: Find names of all students enrolled in the course named "DBMS".

1. Select course tuple where CName = 'DBMS': $$T_1\leftarrow {\sigma }_{\text{CName}=\text{’DBMS’}}(\text{Course})$$
2. Join with Enroll: $$T_2\leftarrow T_1\bowtie \text{Enroll}$$
3. Join with Student: $$T_3\leftarrow T_2\bowtie \text{Student}$$
4. Project SName: $$\text{Result}\leftarrow {\pi }_{\text{SName}}(T_3)$$

Query B: Find SID of students who have enrolled in both 'C101' and 'C102'.

Using set intersection: $${\pi }_{\text{SID}}({\sigma }_{\text{CID}=\text{’C101’}}(\text{Enroll}))\cap {\pi }_{\text{SID}}({\sigma }_{\text{CID}=\text{’C102’}}(\text{Enroll}))$$

Query C: Find the names of students who have NOT enrolled in any course.

1. All students: ${\pi }_{\text{SID}}(\text{Student})$
2. Students who have enrolled in at least one course: ${\pi }_{\text{SID}}(\text{Enroll})$
3. Set difference: $$\text{UnenrolledSIDs}\leftarrow {\pi }_{\text{SID}}(\text{Student})-{\pi }_{\text{SID}}(\text{Enroll})$$
4. Retrieve names: $$\text{Result}\leftarrow {\pi }_{\text{SName}}(\text{UnenrolledSIDs}\bowtie \text{Student})$$

Query D: Find students who have enrolled in ALL courses offered.

This represents a standard universal quantification problem solved by Division ($÷$): $$\text{AllCourses}\leftarrow {\pi }_{\text{CID}}(\text{Course})$$ $$\text{StudentEnrolledPairs}\leftarrow {\pi }_{\text{SID, CID}}(\text{Enroll})$$ $$\text{Result}\leftarrow {\pi }_{\text{SName}}((\text{StudentEnrolledPairs}÷\text{AllCourses})\bowtie \text{Student})$$

---

Problem 3: Banking Database

Given Relational Schema:

• Customer(CustomerID, CustomerName, Address, Phone, Email)
• Borrows(CustomerID, LoanNumber)
• Loan(LoanNumber, LoanType, Amount)

Query: Find the names of customers who have a loan with an amount greater than 500,000.

$${\pi }_{\text{CustomerName}}({\sigma }_{\text{Amount}>500000}(\text{Loan})\bowtie \text{Borrows}\bowtie \text{Customer})$$

---

Applications and Importance in Query Optimization

Relational algebra is not merely an academic notation; it serves direct practical purposes in database engine architecture:

1. Internal Representation: Relational database management systems translate SQL queries into equivalent relational algebra expressions, represented internally as query trees.
2. Equivalence Rules and Optimization: The database query optimizer applies algebraic transformation rules to swap operations. For instance: $${\sigma }_C(R\bowtie S)\equiv ({\sigma }_C(R))\bowtie S$$ Pushing selections down past joins drastically cuts the size of intermediate relations, saving memory and CPU cycles during joins.
3. Execution Plans: Leaf nodes of an operator tree correspond to base relations stored on disk, internal nodes correspond to relational operators, and the root produces the query answer.

          Query Optimization via Selection Push-down

      Unoptimized Plan                      Optimized Plan
          pi(TName)                            pi(TName)
             |                                    |
          sigma(Dept='CSIT')                     join
             |                                  /    \
            join                     sigma(Dept='CSIT') Enroll
           /    \                         |
       Student  Enroll                 Student

---

Exam Tips

• Check Union Compatibility First: When writing $\cup$, $-$, or $\cap$, verify that both operands project the identical number of attributes with compatible types. Writing $\text{Student}\cup \text{Course}$ will receive zero marks; project common attributes first, such as ${\pi }_{\text{ID}}(\text{Student})\cup {\pi }_{\text{ID}}(\text{Faculty})$.
• Projection List Reductions: Never project attributes before applying selection conditions on those attributes unless you include the predicate attribute in the projection. Always apply selections as early as possible.
• Handling "ALL" Questions: Whenever an exam question uses phrases like "teachers who teach all subjects", "customers who have accounts in all branches", or "students enrolled in every course", identify it immediately as a Division operation ($R÷S$).
• Join Subscripts: When using Theta Join, specify the join condition explicitly in the subscript (e.g., $R{\bowtie }_{R.\text{ID}=S.\text{ID}}S$). If using Natural Join ($\bowtie$), ensure the schema has identical attribute names for the join key.
• Show Intermediate Relations: Break down complex relational algebra answers using assignment arrows ($\leftarrow$) and numbered steps ($R_1,R_2,R_3$). This clarifies your logic and secures partial credit even if a final projection has a syntax oversight.