Relational Algebra - Study Notes (UFPel)

Model Relational

  • Relational model concepts from the slides: a relational database schema is composed of relations (tables).

  • A relation is a table; a tuple is a row; an attribute is a column; a domain is the set of values that may appear in each column.

  • Source cited: Elmasri & Navathe (2003).

Relational Schema

  • Example relational schema (Relational schema for a company):

    • Empregado (pnome, minicial, unome, ssn, datanasc, endereco, sexo, salario, superssn, dno)

    • superssn references Empregado

    • dno references Departamento

    • Departamento (dnome, dnumero, gerssn, gerdatainicio)

    • gerssn references Empregado

    • Depto_Localizacoes (dnumero, dlocalizacao)

    • Projeto (pjnome, pnumero, plocalizacao, dnum)

    • dnum references Departamento

    • Trabalha_Em (essn, pno, horas)

    • essn references Empregado

    • pno references Projeto

    • Dependente (essn, nome_dependente, sexo, datanasc, parentesco)

    • essn references Empregado

  • This shows foreign-key style references between relations (RI - referential integrity).

RI Referential Integrity in the Schema

  • Referential Integrity (RI) constraints are shown in the schema via foreign-key like references (e.g., superssn → Empregado, dno → Departamento, es ssn in Dependente referencing Empregado).

  • RI ensures the existence of referenced tuples for each foreign key value, maintaining consistency across relations.

Instance of a Relational DB

  • An instance of a relational database is a specific population of the schema with actual tuples.

  • The slides show that an instance is a snapshot of data conforming to the schema.

Languages for Querying

  • Query languages manipulate and retrieve data from a database instance.

  • Two formal bases for practical DB querying:

    • Relational Algebra (operational): provides procedures to compute queries.

    • Relational Calculus (declarative): specifies what to retrieve.

  • Practical languages (e.g., SQL) are based on these foundations.

Relational Algebra

  • Relational Algebra defines a set of operations on the relational model.

  • Purpose: to select/combine tuples from multiple relations to specify a query.

  • Result of an operation is a new relation.

  • Divided into two groups:

    • Set-theory operations: Union, Intersection, Difference, Cartesian Product

    • Database-specific operations: Selection, Projection, Join, etc.

Set-theory operations

  • Union (R ∪ S): combines tuples from two compatible relations; duplicates eliminated.

  • Intersection (R ∩ S): common tuples between two compatible relations.

  • Difference (R − S): tuples in R that are not in S.

Compatibility of relations for set operations

  • Two relations R(A1, A2, …, An) and S(B1, B2, …, Bn) are union-compatible if:

    • they have the same arity n, and

    • dom(Ai) = dom(Bi) for all i = 1..n.

  • This ensures the operations are well-defined.

Examples of set operations

  • Example: retrieve the social security numbers (NSS) of all employees who either work in department 5 OR supervise an employee who works in department 5.

    • DEP5_EMPS ← σNDEP=5 (EMPREGADO)

    • RESULT1 ← π NSS (DEP5_EMPS)

    • RESULT2 ← π NSSSUPER (DEP5_EMPS)

    • RESULT ← RESULT1 ∪ RESULT2

Properties of Union and Intersection

  • Commutativity: R ∪ S = S ∪ R and R ∩ S = S ∩ R.

  • Associativity: R ∪ (S ∪ T) = (R ∪ S) ∪ T and R ∩ (S ∩ T) = (R ∩ S) ∩ T.

Cartesian Product

  • Also a binary set operation; not limited to union-compatible relations.

  • R × S produces a relation Q with attributes of R followed by attributes of S: Q(A1, A2, …, An, B1, B2, …, Bm).

  • If |R| = nR tuples and |S| = nS tuples, then |Q| = nR × nS tuples.

  • Use case: combine tuples from two relations to prepare for a subsequent selection (e.g., to pair employees with dependents).

Example of Cartesian Product usage

  • To list dependents of female employees: EMP_FEM ← σSEXO='F' (EMPREGADO)

  • EMPNOMES ← πPNOME, SNOME, NSS (EMPFEM)

  • EMPDEP ← EMPNOMES χ DEPENDENTE

  • DEPATUAL ← σNSS = NSSEMP (EMPDEP)

  • RESULT ← πPNOME, SNOME, NOMEDEPENDENTE(DEP_ATUAL)

Join (Junção)

  • The join operation combines related tuples from two relations into a single tuple.

  • Notation: R ⋈_{condition} S or R S

  • Result: a relation with attributes from both R and S, where each pair of tuples satisfies the join condition.

  • General form: R S

  • Join condition typically of the form: θ where Ai is from R, Bj from S, and θ ∈ {=, <, ≤, >, ≥, ≠} with same domain for Ai and Bj.

Equi-join and Natural Join

  • Equi-join: a join where the condition uses only equality (=).

  • Result of an equi-join often contains one or more attributes with identical values; a natural join is an equi-join where the second attribute of each equality condition is eliminated from the result (usually on attributes with the same name).

  • Note: Natural join is a type of equi-join on common attributes.

Natural Join Example

  • For a natural join between DEPARTAMENTO and LOCAISDEPTO, one can write: DEPTLOCS ← DEPARTAMENTO ⋈ LOCAIS_DEPTO

Outer Join (Junção Externa)

  • Outer joins return not only the matching tuples but also non-matching ones, filling missing attributes with NULLs for the non-matching side.

  • Types:

    • LEFT OUTER JOIN

    • RIGHT OUTER JOIN

    • FULL OUTER JOIN

Precedence of Operations

  • Operator precedence (order of evaluation):
    1) σ, π, ρ (selection, projection, rename) – highest
    2) χ (join) and ⋈
    3) ∩ (intersection)
    4) ∪ and − (union and difference) – lower

Additional Operations

  • Some queries cannot be expressed with classical relational algebra operators alone and require additional operators (used in commercial DB languages).

Aggregation Functions

  • Aggregation functions operate on numeric attributes and produce a relation as a result (not a scalar).

  • Common functions: SUM, AVERAGE, MAXIMUM, MINIMUM, COUNT.

  • General form: Operator FUNCTION ℑ ()

  • Details:

    • is a list of attributes by which the result is grouped.

    • is a list of pairs (, ).

    • The resulting relation has the grouping attributes plus the results of the functions.

  • Example: For each department, compute the number of employees and their average salary:

    • R(DNO, NRO ext{_}EMPS, ext{MÉDIA}) \leftarrow NDEP \, \mathcal{I} \, COUNT(NSS), \, AVERAGE(SALÁRIO) (EMPREGADO)

    • Note: If the names of the resulting attributes are not specified, the system may assign defaults.

Examples (Exemplos)

  • Example 1: Find the name and address of all employees who work for the department named 'Pesquisa'.

    • PESQUISA_DEPTO ← σ DNOME = 'Pesquisa' (DEPARTAMENTO)

    • PESQUISADEPTOEMPS ← (PESQUISA_DEPTO DNÚMERO = NDEP EMPREGADO)

    • RESULT ← π PNOME, SNOME, ENDEREÇO (PESQUISADEPTOEMPS)

  • Example 2: For every project located in 'Stafford', list the project number, department number, and the manager's surname, address, and date of birth.

    • STAFFORD_PROJS ← σ PLOCALIZAÇÃO = 'Stafford' (PROJETO)

    • CONTRDEPT ← (STAFFORDPROJS DNUM = DNÚMERO_DEPARTAMENTO)

    • PROJDEPTMGR ← (CONTR_DEPT SSNGER = NSS EMPREGADO)

    • RESULT ← π PNÚMERO, DNUM, SNOME, ENDEREÇO, DATANASC (PROJDEPTMGR)

  • Example 3: List the names of all employees who have two or more dependents.

  • Example 4: List the names of employees who have no dependents.

  • Example 5: List the names of managers who have at least one dependent.

Exercises (Navathe, 4th edition or similar references)

  • A set of exercises includes various JOIN types, and queries about the Company database used in the slides.

  • Example exercises include: retrieving employee names by department, employees with dependents sharing the same name, managers supervising particular employees, and aggregate queries by department.

References

  • Main reference: Elmasri, R.; Navathe, S. B. Systems of Database (6th and 4th editions cited).

  • Additional参考: Takai, O.K.; Italiano, I. C.; Ferreira, J. E. Introdução a Banco de Dados. Appendix available at USP site.

Notes on notation and conventions in this course

  • Notation used in slides:

    • σ for Selection with condition inside parentheses: σ(R)\sigma_{} (R)

    • π for Projection with a list of attributes: π(R)\pi_{}(R)

    • × for Cartesian product: R×SR \times S

    • ⋈ or a join symbol for Join with a condition: R⋈SR \bowtie_{} S

    • ∪ for Union; ∩ for Intersection; − for Difference

    • ρ for Rename operator (typical in relational algebra, used in precedence discussion)

    • ℑ for Aggregation operator in the forms shown

Quick reference cheat sheet (condensed)

  • Selection: σ(R)\sigma_{}(R)

    • Condition formats: or

    • Relational operators: { =, <, ≤, ≥, ≠ }

    • Logical operators: { AND, OR, NOT }

  • Projection: π(R)\pi_{}(R)

    • Preserves the order of attributes as listed; de-dup automatically; not commutative

  • Cartesian product: R×SR \times S with attributes from R followed by those from S; ∣R×S∣=∣R∣⋅∣S∣|R \times S| = |R| \cdot |S|

  • Join: R⋈SR \bowtie_{} S; common operator forms include Equijoin (using =) and Natural Join

  • Equijoin: join with equality condition only; Natural Join removes duplicate attribute on the second relation when the names match

  • Outer Join: Left, Right, Full Outer Join to preserve non-matching tuples by padding NULLs

  • Aggregation: R(groupingattributes,,)R( {grouping attributes}, {, } ) with functions like SUM,AVERAGE,MAX,MIN,COUNT\text{SUM}, \text{AVERAGE}, \text{MAX}, \text{MIN}, \text{COUNT}

  • Precedence: σ, π, ρ > χ, ⋈ > ∩ > ∪, −

If you would like, I can tailor these notes further for a specific section (e.g., more examples for Selection/Projection, or convert all examples to SQL-like expressions for practice).