Relational Algebra Fundamentals

Introduction to Relational Algebra

Relational algebra is the theoretical foundation of SQL and relational database query processing. It provides a collection of operators that manipulate relations (tables) to produce new relations. Mastering these operators—SELECT, PROJECT, JOIN, UNION, MINUS, and RENAME—is essential for anyone studying algorithmics or designing efficient database queries.

Combining Sequential SELECT Operations

When two SELECT (σ) operations are applied one after the other on the same relation, they can be merged into a single SELECT with a conjunctive condition. This optimization reduces the number of passes over the data and improves query performance.

Why a Conjunctive Condition Works

Consider the expression σ_{C1}(σ_{C2}(EMPLOYEE)). The first selection filters tuples that satisfy condition C2, and the second filters the result for condition C1. Since both conditions must be true for a tuple to survive, they can be combined using logical AND:

σ_{C1 ∧ C2}(EMPLOYEE)

This single operation yields exactly the same set of tuples as the two-step process.

Common Pitfalls

• Attempting to replace the second SELECT with a PROJECT changes the attributes returned, which is not equivalent.
• Using UNION would produce a set of tuples that satisfy either condition, not both.
• Swapping the order of SELECT operations does not affect the result, but adding a RENAME is unnecessary unless attribute names clash.

PROJECT Operation and Duplicate Elimination

The PROJECT (π) operator extracts a subset of attributes from a relation. By definition, relational algebra works with sets of tuples, which means duplicate rows are automatically removed.

Effect on Non‑Key Attributes

When you project attributes that are not part of a primary key, any duplicate tuples that become identical after the projection are eliminated. The resulting relation contains only distinct tuples.

Example:

π_{Dept, Salary}(EMPLOYEE)

If two employees share the same department and salary, the projection will keep only one of those rows.

Key Takeaway

PROJECT never fails because of duplicates, never replaces them with NULL, and never preserves the original cardinality when duplicates exist. It always returns a set of unique tuples.

Understanding the CARTESIAN PRODUCT (×)

The Cartesian product combines every tuple of one relation with every tuple of another, producing a relation whose degree (number of attributes) is the sum of the degrees of the operands.

Degree Calculation Example

Given R(A, B) and S(C, D) with disjoint attribute names, the product R × S has attributes A, B, C, D—four in total.

This rule holds regardless of attribute names; the only requirement is that the schemas do not share attribute names, otherwise a RENAME may be needed to avoid ambiguity.

Set Difference (MINUS) and Its Non‑Commutative Nature

The MINUS (or set difference) operator returns tuples that appear in the first relation but not in the second. Because the operation is directional, swapping the operands generally yields a different result.

Why Order Matters

Consider relations R and S. R – S produces all tuples in R that are absent from S. Conversely, S – R returns tuples unique to S. Unless the two relations are identical, the results differ, demonstrating that MINUS is not commutative.

Common Misconceptions

• It does not always return an empty set; the result depends on the overlap of tuples.
• It does not rename attributes; attribute names must already be compatible.
• It does not require a preceding UNION; it works directly on compatible relations.

RENAME Operator (ρ) Syntax and Usage

The RENAME operator changes the name of a relation and/or its attributes, which is useful for avoiding name clashes in subsequent operations such as joins.

Correct Syntax Example

To rename the relation EMPLOYEE to NewEmp and its attributes to EmpID and EmpName, use:

ρNewEmp(EmpID, EmpName)(EMPLOYEE)

This form first specifies the new relation name, then lists the new attribute names in the same order as the original schema.

Incorrect Variants

• ρ(EmpID, EmpName)(EMPLOYEE) omits the new relation name.
• ρNewEmp(EMPLOYEE) renames only the relation, leaving attributes unchanged.
• ρNewEmp, EmpID, EmpName(EMPLOYEE) does not follow the proper parentheses placement.

Cardinality of the Cartesian Product

When computing R × S, the number of resulting tuples equals the product of the cardinalities of the two input relations.

Example Calculation

If R contains 5 tuples and S contains 3 tuples, then R × S yields 5 × 3 = 15 tuples.

This linear scaling is a key factor in query optimization; large Cartesian products can be expensive, so they are often replaced by more selective joins.

Natural Join Representation

A natural join combines two relations by automatically matching attributes with the same name, eliminating duplicate columns in the result.

Correct Expression for EMPLOYEE and DEPARTMENT

To join EMPLOYEE and DEPARTMENT on the common attribute Dno, the relational algebra expression is:

σ_{EMPLOYEE.Dno = DEPARTMENT.Dno}(EMPLOYEE × DEPARTMENT)

Although this uses a selection after a Cartesian product, it is equivalent to the natural join operator (⋈) because the condition equates the shared attribute.

Why Other Options Are Incorrect

• EMPLOYEE ÷ DEPARTMENT denotes division, a different operation.
• ρEMP_DEPT (EMPLOYEE) × DEPARTMENT only renames the relation without performing a join.
• π_{EMPLOYEE.*, DEPARTMENT.*}(EMPLOYEE ∪ DEPARTMENT) uses union and projection, which does not enforce the equality of Dno.

UNION Compatibility Requirements

The UNION operator merges two relations into a single relation containing all distinct tuples from both inputs. For this operation to be valid, the relations must be union compatible.

Definition of Union Compatibility

Two relations are union compatible when they have:

• The same number of attributes (degree).
• Corresponding attributes with identical data types.

Attribute names do not need to match, but the order and types must align. If the schemas differ, a RENAME can be applied to achieve compatibility.

Summary of Key Concepts

Understanding the fundamentals of relational algebra equips you to write more efficient SQL queries and to reason about query optimization. The main takeaways from this course are:

• Multiple SELECT operations can be merged using a conjunctive AND condition.
• PROJECT eliminates duplicate tuples, always returning a set of distinct rows.
• The degree of a Cartesian product is the sum of the degrees of its operands.
• MINUS is not commutative; order matters.
• Correct RENAME syntax includes both the new relation name and the new attribute list.
• Cardinality of R × S equals |R| × |S|.
• Natural joins can be expressed via selection on a Cartesian product.
• Union compatibility requires matching attribute counts and types.

By mastering these operators, you lay a solid foundation for advanced database topics such as query rewriting, optimization, and relational calculus.