Relational Algebra and SQL Fundamentals

Understanding Relational Algebra Basics

Relational algebra is the theoretical foundation of SQL and relational databases. It provides a set of operators that manipulate relations (tables) to produce new relations. Mastering these operators helps you write efficient queries and understand how databases process your commands.

Selection (σ) – Filtering Rows

The selection operator, denoted by σ, extracts rows that satisfy a given predicate. For example, given a relation R(A, B, C) and the condition B = 3 ∧ C > 1, the correct relational algebra expression is:

• σ_{B=3 ∧ C>1}(R)

This expression returns only those tuples where B equals 3 and C is greater than 1. Other options such as a Cartesian product (R × σ_B=3(R)) or a simple projection (π_B,C(R)) do not apply the full predicate and therefore produce incorrect results.

Projection (π) – Selecting Columns

Projection creates a new relation containing only the specified attributes. However, after projecting, duplicate rows may appear. To eliminate duplicates, relational algebra provides the duplicate elimination operator, denoted by δ.

• δ(π_attributes(R)) – removes duplicate tuples after projection.

Without δ, the result of a projection could contain repeated rows, which is often undesirable in query results.

Rename (ρ) – Giving New Names

The rename operator, ρ, changes the name of a relation or its attributes. This is useful when you need to differentiate between two relations that have identical attribute names, especially before performing joins.

• ρ_S(σ_C>1(R)) – renames the result of a selection to S.

Join Operators – Combining Relations

Joins are among the most powerful relational algebra operators. They combine tuples from two relations based on a common attribute set.

Natural Join (⋈) and Empty Attribute Sets

If the common attribute set X between two relations is empty, the natural join behaves like a Cartesian product. In other words, every tuple from the first relation pairs with every tuple from the second relation.

• R ⋈ S (with X = ∅) ≡ R × S

Outer Joins – Preserving Unmatched Rows

Outer joins keep rows that do not find a matching partner in the other relation. A left outer join returns all rows from the left relation and matching rows from the right relation, filling with NULLs when there is no match.

• R ⟕ S – left outer join (often written as R ▷◁ S in relational algebra textbooks).

Note that the symbol “⋉” typically denotes a left outer join, while “⋊⋉” is not a standard operator for this purpose.

SQL Fundamentals Aligned with Relational Algebra

SQL implements the concepts of relational algebra in a declarative language. Understanding the correspondence between the two helps you translate logical queries into efficient SQL statements.

WHERE vs. HAVING – Filtering Rows vs. Groups

The WHERE clause filters rows before any grouping occurs, while the HAVING clause filters groups after the GROUP BY operation.

• Use WHERE to apply predicates on individual rows.
• Use HAVING to restrict groups based on aggregate conditions (e.g., HAVING COUNT(*) > 5).

Aggregation and NULL Handling

Aggregate functions such as SUM, AVG, MAX, and MIN ignore NULL values. This means that rows with NULL in the aggregated column do not affect the result, except when the entire set is NULL, in which case the aggregate returns NULL.

The NOT NULL constraint ensures that a column never contains NULL, simplifying aggregation because every row contributes a valid value.

Indexing – When to Use and When to Avoid

Indexes speed up data retrieval but come with maintenance overhead. Follow these guidelines:

• Avoid indexes on small tables – full table scans are cheap, and the index adds unnecessary write cost.
• Prefer indexes on columns with high cardinality (many distinct values) and that appear frequently in WHERE clauses.
• Be cautious with columns that are frequently updated; each update must also modify the index.

Therefore, the correct scenario to avoid an index is when the table is small and columns are frequently updated.

Putting It All Together – Sample Queries

Below are practical examples that illustrate the concepts discussed.

Example 1: Filtering with Selection

SELECT *
FROM R
WHERE B = 3 AND C > 1;

This SQL query mirrors the relational algebra expression σ_{B=3 ∧ C>1}(R).

Example 2: Removing Duplicates After Projection

SELECT DISTINCT B, C
FROM R;

Here, DISTINCT implements the δ (duplicate elimination) operator after projecting columns B and C.

Example 3: Left Outer Join

SELECT R.A, R.B, S.C
FROM R
LEFT JOIN S ON R.B = S.B;

This query corresponds to the relational algebra expression R ⟕ S (left outer join).

Example 4: Using HAVING to Filter Groups

SELECT B, COUNT(*) AS cnt
FROM R
GROUP BY B
HAVING COUNT(*) > 10;

The HAVING clause filters groups after aggregation, just as relational algebra would apply a selection on the grouped result.

Example 5: Index Considerations

Suppose you have a table Orders with columns order_id (primary key) and status. If Orders contains only a few rows and status changes frequently, creating an index on status is not advisable.

Key Takeaways

• Selection (σ) filters rows based on predicates.
• Projection (π) selects columns; use duplicate elimination (δ) to remove repeats.
• Rename (ρ) changes relation or attribute names, facilitating joins.
• Natural joins become Cartesian products when there are no common attributes.
• Left outer joins preserve all rows from the left relation.
• SQL’s WHERE filters rows, while HAVING filters groups.
• Aggregate functions ignore NULLs; NOT NULL constraints guarantee non‑NULL values.
• Indexes boost read performance but should be avoided on small, frequently‑updated tables.