Database Systems - Relational Algebra Notes

Overview of Database Systems and Relational Algebra

Query Languages

  • Allow manipulation and retrieval of data from databases.
  • The relational model offers simple yet powerful query languages (QLs).
  • Key differences between query languages and programming languages:
  • QLs are not designed for complex calculations.
  • Provide easy access to large datasets.

Formal Relational Query Languages

  • Form the basis for commercial languages like SQL:
  1. Relational Algebra:
    • Uses operators to compose queries.
    • Describes a step-by-step procedure for computing results.
    • Useful for execution plans representation.
  2. Relational Calculus:
    • Based on first-order logic subsets.
    • Specifies desired results without detailing computation methods.
    • Non-procedural or declarative in nature.

Characteristics of an Algebra

  • Expressions:
  • Constructed with operators and operands.
  • Can be evaluated.
  • Equivalent Expressions:
  • Return the same results for all variable values.
  • Allow the replacement of sub-expressions without changing meaning.
  • Context Independence:
  • The value remains the same regardless of context (e.g., 5 + 3 is the same in any context).

Relational Algebra: Principles

  • Atoms are relations.
  • Operators apply to instances of a relation.
  • Each operator results in:
  1. Result schema (dependent on the argument relation schemas).
  2. Result instance (dependent on argument instances).
  • Concepts in relational algebra reappear in SQL and are used in database management systems (DBMS).

Classification of Relational Algebra Operators

  • Set theoretic operators:
  • Union (∪)
  • Intersection (∩)
  • Difference (`
  • Other operators include:
  • Renaming (ρ)
  • Projection (π)
  • Selection (σ)
  • Cartesian Product (×)
  • Joins
  • Division (÷)
  • Extended operators for:
  • Duplicate elimination, grouping, aggregation, sorting, outer joins.

Core Operators and Their Functions

1. Selection (σ)
  • Selects rows satisfying specified conditions.
  • Output schema mirrors the input schema.
2. Projection (π)
  • Removes unwanted attributes from relation output.
  • Eliminates duplicates unless specified otherwise.
3. Cartesian Product (×)
  • Combines every row from one relation with every row from another.
  • May require renaming to resolve conflicts with similar field names.
4. Set-Difference (R - S)
  • Returns tuples in R not present in S.
  • Must be union-compatible.
5. Union (R ∪ S)
  • Combines tuples from both R and S, retaining duplicates.
  • Requires union compatibility for both input relations.
6. Intersection (R ∩ S)
  • Returns tuples present in both R and S.
  • Must be union-compatible.
7. Joins
  • Joins can be theta joins (any condition), equi-joins (only equalities), or natural joins (on all common fields).
  • Result schema is derived from the combined schemas of the joined relations.
8. Division (A/B)
  • Finds tuples in A that are associated with every tuple in B through the division of fields.

Aggregation and Grouping

  • Retrieve aggregate values using functions like SUM, AVG, MIN, and COUNT.
  • Grouping Aggregation: Retrieves aggregate values within groups based on specified attributes.

Outer Joins

  • Extends inner join results by including tuples from one or both input relations, filling in nulls where there are no matches.
  • Types include:
  • Left Outer Join: Retains all rows from the left relation.
  • Right Outer Join: Retains all rows from the right relation.
  • Full Outer Join: Retains all rows from both relations.

Summary of Relational Algebra Operators

  • Selection (σ): Select rows based on conditions.
  • Projection (π): Filter out columns.
  • Cross-product (×): Combine two relations.
  • Set-difference (R - S): Find tuples in one relation not in another.
  • Union (R ∪ S): Combine tuples from both relations.
  • Intersection (R ∩ S): Find common tuples.
  • Joins: Combine relations based on specified criteria.
  • Division (A/B): Find tuples in A associated with all tuples in B.
  • Renaming (ρ): Change names of attributes in a resulting relation.

Practical Examples

Example Queries
  1. Find names of sailors who reserved a specific boat (e.g. boat #103).
  2. Identify sailors who’ve reserved a red boat.
  3. Determine sailors who’ve reserved either a red or green boat.
  4. Find sailors who’ve reserved both a red and a green boat.
  5. Identify sailors who’ve reserved all boats.
Query Optimization
  • Multiple ways to express a query.
  • Importance of query optimization in selecting the most efficient expression for execution.