Relational Algebra & Calculus

Relational Algebra & Calculus in DBMS

Relational Algebra and Relational Calculus are formal query languages associated with the relational database model. They form the mathematical foundation for SQL (Structured Query Language).

1. Relational Algebra (Procedural Language)

1.1 Basic (Fundamental) Operators

1. Select Operation (σ - Sigma)

• Purpose: Selects tuples (rows) that satisfy a given predicate (condition).
• Notation: σ_p(R) where p is the propositional logic formula and R is the relation.
• Degree: The degree (number of columns) of the resulting relation is the same as the original relation.
• Cardinality: The cardinality (number of rows) of the resulting relation is less than or equal to the original relation.
• Example: σ_salary > 50000(Employee) selects all employees earning more than 50,000.

2. Project Operation (π - Pi)

• Purpose: Selects specified attributes (columns) from a relation and discards the rest. It automatically eliminates duplicate tuples in the output.
• Notation: π_A1, A2, ..., An(R) where A represents the attributes.
• Example: π_Name, Salary(Employee) extracts only the Name and Salary columns.

3. Union Operation (∪)

• Purpose: Combines the tuples of two relations. To perform a union, the two relations must be Union Compatible.
• Union Compatibility Rules:
  1. They must have the same degree (number of attributes).
  2. The domains (data types) of the corresponding attributes must be identical or compatible.
• Notation: R ∪ S
• Duplicate tuples are automatically eliminated.

4. Set Difference Operation (-)

• Purpose: Finds tuples that are in one relation but not in another.
• Notation: R - S (Tuples present in R but absent in S).
• Requires both relations to be union compatible.

5. Cartesian Product Operation (× - Cross Product)

• Purpose: Combines information from any two relations. It pairs every tuple of the first relation with every tuple of the second relation.
• Notation: R × S
• Degree: Degree of R + Degree of S.
• Cardinality: Cardinality of R * Cardinality of S.

6. Rename Operation (ρ - Rho)

• Purpose: Renames an output relation or its attributes to resolve naming conflicts, especially useful in self-joins.
• Notation: ρ_x(R) (renames relation R to x) or ρ_x(A1, A2)(R) (renames relation and attributes).

1.2 Extended (Derived) Operators

1. Set Intersection (∩)

• Purpose: Finds tuples that are present in both relations.
• Notation: R ∩ S
• Can be derived as: R - (R - S).
• Requires union compatibility.

2. Joins (⋈)

• Combines tuples from different relations provided they satisfy a specified condition (θ).
• Notation: R ⋈_θ S
• The condition θ can be any comparison operator (<, >, =, ≤, ≥, ≠). B. Equi Join:
• A special case of Theta Join where the condition θ contains only the equality (=) operator. C. Natural Join (⋈):
• An Equi Join over all common attributes. It automatically drops one copy of the duplicate column.
• If there are no common attributes, a Natural Join behaves exactly like a Cartesian Product. D. Outer Joins: Used to retain tuples that do not have matching values in the joined relation.
• Left Outer Join (⟕): Retains all tuples from the left relation. Unmatched left tuples get NULL values for right attributes.
• Right Outer Join (⟖): Retains all tuples from the right relation.
• Full Outer Join (⟗): Retains all tuples from both relations.

3. Division Operator (÷)

• Purpose: Used for queries that involve the word "every" or "all".
• Example Scenario: Find students who have taken all courses offered by the CS department.
• Notation: R ÷ S
• It returns the attributes of R that are not in S, but only for those tuples in R that match every tuple in S.

2. Relational Calculus (Non-Procedural Language)

2.1 Tuple Relational Calculus (TRC)

• Variables in TRC represent tuples (rows) of a relation.
• Notation: { t | P(t) }
• Meaning: The set of all tuples t such that predicate P is true for t.
• Example: { t | t ∈ Employee ∧ t.Salary > 50000 } (Finds all employee tuples with salary > 50000).
• Uses quantifiers: Universal (∀ - For all) and Existential (∃ - There exists).

2.2 Domain Relational Calculus (DRC)

• Variables in DRC represent domains (attributes/columns) instead of whole tuples.
• Notation: { <x1, x2, ..., xn> | P(x1, x2, ..., xn) }
• QBE (Query-By-Example) is a visual database manipulation language based closely on DRC.

3. Expressive Power

• A query language is called Relationally Complete if it can express any query that can be expressed in basic Relational Algebra.
• Relational Algebra, Tuple Relational Calculus (safe expressions), and Domain Relational Calculus (safe expressions) have the exact same expressive power.
• SQL is considered relationally complete because it implements all relational algebra operators.