Algebra relazionale - profgiagnotti.it

// obiettivi di apprendimento

✓Comprendere l’algebra relazionale come fondamento teorico del linguaggio SQL

✓Applicare le operazioni unarie (proiezione π e selezione σ) su insiemi di tuple

✓Applicare le operazioni binarie: prodotto cartesiano, join naturale, theta-join, equi-join

✓Tradurre espressioni di algebra relazionale in query SQL e viceversa

📄

Slides

Simboli, operatori, tavole di corrispondenza SQL

Scarica →

1. Cos’è l’Algebra Relazionale

L’algebra relazionale è il linguaggio formale che sta alla base di SQL. È stata inventata da Edgar F. Codd nel 1970 nel suo paper fondamentale “A Relational Model of Data for Large Shared Data Banks”. Prima che esistesse SQL, si descrivevano le interrogazioni ai database usando questo sistema matematico.

Studiare l’algebra relazionale è utile perché ti aiuta a ragionare su cosa fa una query prima di scriverla: capire i dati che escono, prevedere problemi di performance, e comprendere come l’ottimizzatore SQL interpreta le tue istruzioni.

// definizione formale

L’algebra relazionale è un’algebra procedurale che opera su relazioni (insiemi di tuple) e produce come risultato nuove relazioni. Ogni operazione prende una o due relazioni come input e ne restituisce una come output.

Dati di esempio

Useremo due tabelle semplificate del nostro database scuola per illustrare ogni operazione.

R — STUDENTE

id	nome	cognome	anno
1	Marco	Rossi	4
2	Laura	Bianchi	4
3	Ahmed	Karim	5
4	Sofia	Ferrari	5

S — ESAME

id_esame	id_studente	materia	voto
10	1	Programmazione	28
11	1	Matematica	25
12	2	Programmazione	30
13	3	Inglese	22

2. Operazioni Unarie

Le operazioni unarie agiscono su una sola relazione. Le principali sono la proiezione e la selezione.

PROIEZIONE

Seleziona colonne — riduce gli attributi (verticale)

// espressione algebrica

πnome, cognome(STUDENTE)

Prendi solo gli attributi nome e cognome dalla relazione STUDENTE. Tutti gli altri attributi (id, anno) vengono scartati.

// SQL equivalente

SELECT nome, cognome
FROM STUDENTE;

// risultato

RISULTATO

nome	cognome
Marco	Rossi
Laura	Bianchi
Ahmed	Karim
Sofia	Ferrari

id e anno sono stati eliminati

SELEZIONE

Filtra righe — riduce le tuple (orizzontale)

// espressione algebrica

σvoto > 27(ESAME)

Prendi solo le tuple di ESAME dove il voto è maggiore di 27. Le colonne rimangono invariate, cambiano le righe.

// SQL equivalente

SELECT *
FROM ESAME
WHERE voto > 27;

// risultato

RISULTATO

id_esame	id_st.	materia	voto
10	1	Programmazione	28
12	2	Programmazione	30

solo le tuple con voto > 27

// composizione delle operazioni

Le operazioni si possono comporre: il risultato di una diventa input della successiva. Per trovare nome e cognome degli studenti del quinto anno:

πnome, cognome( σanno = 5(STUDENTE) )

Prima si applica σ (seleziona anno=5), poi π sui risultati (solo nome e cognome). SQL: SELECT nome, cognome FROM STUDENTE WHERE anno = 5

3. Prodotto Cartesiano e Join

Le operazioni binarie agiscono su due relazioni. Il prodotto cartesiano è la base teorica, ma il join è l’operazione concreta che usi ogni giorno in SQL.

PRODOTTO CARTESIANO

Combina ogni tupla di R con ogni tupla di S

STUDENTE × ESAME

STUDENTE

4 tuple

×

ESAME

4 tuple

= 4 × 4 = 16 tuple

⚠️ Il prodotto cartesiano da solo non ha senso semantico: combina ogni studente con ogni esame, indipendentemente da chi lo ha sostenuto. Non si usa quasi mai direttamente — serve come base teorica del join.

⋈

JOIN NATURALE

Prodotto cartesiano + selezione sugli attributi comuni con stesso nome

// espressione algebrica

STUDENTE ⋈ ESAME

Unisce le tuple dove gli attributi con lo stesso nome (qui: id/id_studente — dipende dalla denominazione) hanno lo stesso valore. Equivale a: × seguito da σ su colonne comuni.

// SQL equivalente (con alias id)

SELECT *
FROM STUDENTE
NATURAL JOIN ESAME;
-- oppure, più esplicito:
SELECT *
FROM STUDENTE s
JOIN ESAME e
  ON s.id = e.id_studente;

// risultato

RISULTATO

id	nome	cognome	materia	voto
1	Marco	Rossi	Programmazione	28
1	Marco	Rossi	Matematica	25
2	Laura	Bianchi	Programmazione	30
3	Ahmed	Karim	Inglese	22

Sofia (id=4) non appare: nessun esame

Theta-join e Equi-join

⋈θ

THETA-JOIN

Join con una condizione generica θ (theta) — può essere qualsiasi predicato: =, ≠, <, >, ≤, ≥.

R ⋈R.id < S.id S

SELECT *
FROM R JOIN S
  ON R.id < S.id;

⋈=

EQUI-JOIN

Caso speciale del theta-join dove la condizione è sempre di uguaglianza. È il tipo di join più comune nelle basi di dati relazionali.

STUDENTE ⋈S.id = E.id_studente ESAME

SELECT *
FROM STUDENTE S
JOIN ESAME E
  ON S.id = E.id_studente;

4. Operazioni Insiemistiche

Le operazioni insiemistiche lavorano su due relazioni compatibili — cioè con lo stesso numero di attributi e tipi corrispondenti. Corrispondono agli operatori sugli insiemi della matematica.

UNION — ∪

Unisce tutte le tuple di R e S, eliminando i duplicati.

SELECT nome FROM R
UNION
SELECT nome FROM S;

UNION ALL mantiene i duplicati

INTERSEZIONE — ∩

Solo le tuple presenti in entrambe R e S.

SELECT nome FROM R
INTERSECT
SELECT nome FROM S;
-- MySQL: simula con JOIN

DIFFERENZA — −

Le tuple in R ma non in S.

SELECT nome FROM R
EXCEPT
SELECT nome FROM S;
-- MySQL: NOT IN / NOT EXISTS

// compatibilità degli schemi

Le operazioni insiemistiche richiedono che le due relazioni siano union-compatible: stesso numero di attributi e tipi corrispondenti. Due tabelle con struttura diversa non possono essere unite con UNION, INTERSECT o EXCEPT — usa il JOIN invece.

5. Corrispondenza Algebra Relazionale ↔ SQL

Questa è la tabella di riferimento fondamentale per tradurre espressioni algebriche in SQL e viceversa. Tienila sempre a portata di mano durante gli esercizi.

// ALGEBRA RELAZIONALE → SQL

Simbolo	Operazione	Espressione Algebrica	Equivalente SQL
π	Proiezione	π_nome,voto(ESAME)	`SELECT nome, voto FROM ESAME`
σ	Selezione	σ_voto>27(ESAME)	`SELECT * FROM ESAME WHERE voto > 27`
×	Prodotto cartesiano	STUDENTE × ESAME	`SELECT * FROM STUDENTE, ESAME`
⋈	Join naturale	R ⋈ S	`SELECT * FROM R NATURAL JOIN S`
⋈_θ	Theta/Equi-join	R ⋈_R.id=S.id S	`SELECT * FROM R JOIN S ON R.id = S.id`
∪	Unione	R ∪ S	`SELECT … FROM R UNION SELECT … FROM S`
∩	Intersezione	R ∩ S	`SELECT … FROM R INTERSECT SELECT … FROM S`
−	Differenza	R − S	`SELECT … FROM R EXCEPT SELECT … FROM S`

Esempio completo: espressione composta

Traduzione di una query complessa dalla forma algebrica a SQL. Trova nome e materia degli studenti del 4° anno con voto superiore a 26.

// passo per passo

PASSO 1

Seleziona gli studenti del 4° anno

S₁ = σanno=4(STUDENTE)

PASSO 2

Seleziona gli esami con voto > 26

E₁ = σvoto>26(ESAME)

PASSO 3

Fai il join sui due risultati

J = S₁ ⋈S₁.id=E₁.id_studente E₁

PASSO 4

Proietta solo nome e materia

Risultato = πnome, materia(J)

↓

SQL equivalente

SELECT  s.nome, e.materia
FROM    STUDENTE s
JOIN    ESAME    e  ON s.id = e.id_studente
WHERE   s.anno = 4
  AND   e.voto > 26;

📌 Riepilogo — Punti chiave

L'algebra relazionale è la base teorica di SQL: ogni query SQL corrisponde a un'espressione algebrica.
π (proiezione) seleziona le colonne — corrisponde alla lista dopo SELECT. σ (selezione) filtra le righe — corrisponde a WHERE.
Il prodotto cartesiano (×) combina tutto con tutto: senza una condizione di join diventa inutile e molto costoso (N×M righe).
Il join naturale (⋈) è il prodotto cartesiano filtrato sugli attributi comuni. Il theta-join usa una condizione generica, l'equi-join usa l'uguaglianza.
Le operazioni insiemistiche (∪ ∩ −) richiedono relazioni union-compatible. In MySQL: UNION, INTERSECT (simulata), EXCEPT (simulata con NOT IN).

// link utili

🧮

Relational Algebra Land — Simulatore Online

relational.algebra.land · Inserisci le tue tabelle e prova le operazioni interattivamente

↗ 📜

E.F. Codd — A Relational Model of Data (1970)

acm.org · Il paper originale che ha inventato i database relazionali (Turing Award)

↗ 🎓

Princeton CS322 — Relational Algebra Lecture Notes

cs.princeton.edu · Materiale universitario con esempi formali

↗

1. Cos’è l’Algebra Relazionale

Dati di esempio

2. Operazioni Unarie

3. Prodotto Cartesiano e Join

Theta-join e Equi-join

4. Operazioni Insiemistiche

5. Corrispondenza Algebra Relazionale ↔ SQL

Esempio completo: espressione composta

Lascia un commento Annulla risposta