Salta el contingut

Àlgebra relacional

L'àlgebra relacional és el llenguatge formal que Codd va definir el 1970 com a fonament teòric del model relacional. Consisteix en un conjunt d'operadors que prenen una o dues relacions com a entrada i produeixen una nova relació com a sortida. Cada consulta SQL que escrivim es pot expressar —i de fet el motor de BD la compila internament— com una expressió d'àlgebra relacional.

Entendre l'àlgebra relacional ajuda a:

  • Comprendre com el SGBD optimitza les consultes (el pla d'execució és un arbre d'operadors).
  • Raonar formalment sobre la correcció d'una consulta.
  • Entendre per què certes consultes SQL es comporten com es comporten.

Notació

Símbol Operador Entrada
σ (sigma) Selecció Unària
π (pi) Projecció Unària
ρ (rho) Reanomenament Unària
∪ Unió Binària
− Diferència Binària
× Producte cartesià Binària
∩ Intersecció Binària (derivada)
⋈ Join natural Binària (derivada)
⋈_θ Theta-join Binària (derivada)
÷ Divisió Binària (derivada)

Els operadors fonamentals (σ, π, ρ, ∪, −, ×) són suficients per expressar qualsevol consulta. Els derivats (∩, ⋈, ÷) es defineixen a partir dels fonamentals i s'usen per comoditat.

Esquema d'exemple

Al llarg d'aquest document usarem el següent esquema de botiga en línia:

CLIENT(id_client, nom, ciutat, edat)
PRODUCTE(id_producte, descripcio, categoria, preu)
COMANDA(id_comanda, id_client, id_producte, data, quantitat)

Instàncies d'exemple:

CLIENT

id_client nom ciutat edat
1 Anna Barcelona 28
2 Bernat Girona 35
3 Carla Barcelona 22
4 David Lleida 41

PRODUCTE

id_producte descripcio categoria preu
P1 Teclat mecànic Informàtica 89.90
P2 Ratolí ergonòmic Informàtica 45.00
P3 Cadira oficina Mobiliari 320.00
P4 Monitor 27" Informàtica 249.00

COMANDA

id_comanda id_client id_producte data quantitat
C1 1 P1 2024-01-10 1
C2 1 P3 2024-01-15 2
C3 2 P2 2024-02-01 1
C4 3 P1 2024-02-10 3

Operadors fonamentals

Selecció (σ)

Filtra les tuples d'una relació que compleixen una condició. El resultat té el mateix esquema que la relació original però potencialment menys tuples.

Sintaxi: σ_condició(R)

Exemple: Clients de Barcelona:

σ_ciutat='Barcelona'(CLIENT)

Resultat:

id_client nom ciutat edat
1 Anna Barcelona 28
3 Carla Barcelona 22

SQL equivalent: 

SELECT * FROM CLIENT WHERE ciutat = 'Barcelona';

La condició pot combinar predicats amb els operadors lògics ∧ (AND), ∨ (OR) i ¬ (NOT), i comparadors =, ≠, <, >, ≤, ≥.

Exemple: Clients de Barcelona menors de 30 anys:

σ_ciutat='Barcelona' ∧ edat<30(CLIENT)

Projecció (π)

Selecciona un subconjunt de columnes d'una relació. El resultat té el mateix nombre de tuples però menys atributs. Si al projectar apareixen tuples duplicades, s'eliminen (perquè el resultat és un conjunt).

Sintaxi: π_atributs(R)

Exemple: Noms i ciutats dels clients:

π_nom,ciutat(CLIENT)

Resultat:

nom ciutat
Anna Barcelona
Bernat Girona
Carla Barcelona
David Lleida

SQL equivalent: 

SELECT DISTINCT nom, ciutat FROM CLIENT;

Composició de selecció i projecció: Els operadors es poden combinar. Per obtenir els noms dels clients de Barcelona:

π_nom(σ_ciutat='Barcelona'(CLIENT))

SQL equivalent: 

SELECT nom FROM CLIENT WHERE ciutat = 'Barcelona';

Reanomenament (ρ)

Canvia el nom d'una relació o dels seus atributs. És útil per evitar ambigüitats quan treballem amb dues còpies de la mateixa relació.

Sintaxi: ρ_nouNom(R) o ρ_nouNom(a1→b1, a2→b2)(R)

Exemple: Reanomenar CLIENT com C:

ρ_C(CLIENT)

SQL equivalent: 

SELECT * FROM CLIENT AS C;

Unió (∪)

Combina les tuples de dues relacions compatibles (mateix nombre d'atributs i dominis compatibles). Elimina duplicats.

Sintaxi: R ∪ S

Exemple: Noms de clients i de ciutats (si volgués una llista unificada de noms):

π_nom(σ_ciutat='Barcelona'(CLIENT)) ∪ π_nom(σ_ciutat='Girona'(CLIENT))

SQL equivalent: 

SELECT nom FROM CLIENT WHERE ciutat = 'Barcelona'
UNION
SELECT nom FROM CLIENT WHERE ciutat = 'Girona';

Compatibilitat de la unió

Dues relacions sóncompatibles per a la unió si tenen el mateix nombre d'atributs i els atributs corresponents tenen dominis compatibles. Els noms dels atributs no cal que coincideixin, però convé reanomenar-los per claredat.

Diferència (−)

Retorna les tuples que estan a la primera relació però no a la segona. Les dues relacions han de ser compatibles per a la unió.

Sintaxi: R − S

Exemple: Clients que no han fet cap comanda:

π_id_client(CLIENT) − π_id_client(COMANDA)

Resultat: {4} (David no té cap comanda)

SQL equivalent:

SELECT id_client FROM CLIENT
EXCEPT
SELECT id_client FROM COMANDA;

Producte cartesià (×)

Combina cada tupla de R amb cada tupla de S. Si R té m tuples i n atributs, i S té p tuples i q atributs, el resultat té m×p tuples i n+q atributs.

Sintaxi: R × S

Exemple:

CLIENT × PRODUCTE

Produeix totes les combinacions possibles de clients i productes (4 × 4 = 16 tuples). Per si sol no és gaire útil; s'usa combinat amb la selecció per implementar el join.

SQL equivalent:

SELECT * FROM CLIENT CROSS JOIN PRODUCTE;

Operadors derivats

Intersecció (∩)

Retorna les tuples que estan en totes dues relacions. Es pot expressar amb la diferència:

R ∩ S = R − (R − S)

Exemple: Clients que han comprat tant el producte P1 com el P2:

π_id_client(σ_id_producte='P1'(COMANDA)) ∩ π_id_client(σ_id_producte='P2'(COMANDA))

SQL equivalent:

SELECT id_client FROM COMANDA WHERE id_producte = 'P1'
INTERSECT
SELECT id_client FROM COMANDA WHERE id_producte = 'P2';

Theta-join (⋈_θ)

Combina dues relacions seleccionant les parelles de tuples que compleixen una condició θ. Es defineix com:

R ⋈_θ S = σ_θ(R × S)

Exemple: Clients amb les seves comandes (condició d'igualtat):

CLIENT ⋈_(CLIENT.id_client = COMANDA.id_client) COMANDA

SQL equivalent:

SELECT * FROM CLIENT JOIN COMANDA ON CLIENT.id_client = COMANDA.id_client;

Equijoin

Theta-join on la condició θ és una igualtat (=). El resultat conté les dues columnes de la condició (la de R i la de S).

Join natural (⋈)

Un equijoin que fa la igualtat automàticament sobre tots els atributs amb el mateix nom, i elimina les columnes duplicades del resultat.

CLIENT ⋈ COMANDA

El join es fa sobre id_client (l'únic atribut comú) i el resultat té id_client una sola vegada.

SQL equivalent:

SELECT * FROM CLIENT NATURAL JOIN COMANDA;

Precaució amb el join natural

El join natural pot donar resultats inesperats si dues taules comparteixen per coincidència un nom d'atribut que no és una FK/PK. A la pràctica s'usa l'equijoin explícit o la sintaxi USING.

Divisió (÷)

L'operador de divisió és el menys intuïtiu però és molt útil per a consultes del tipus "quins X han fet tots els Y". Si R(A, B) i S(B), llavors R ÷ S retorna els valors de A que apareixen a R associats a tots els valors de B que hi ha a S.

Sintaxi: R ÷ S

Exemple: Quin clients han comprat tots els productes d'Informàtica?

Comprades = π_id_client, id_producte(COMANDA)
Informatica = π_id_producte(σ_categoria='Informàtica'(PRODUCTE))

Comprades ÷ Informatica

SQL equivalent (usant doble negació):

SELECT DISTINCT id_client FROM COMANDA c1
WHERE NOT EXISTS (
    SELECT id_producte FROM PRODUCTE
    WHERE categoria = 'Informàtica'
    AND id_producte NOT IN (
        SELECT id_producte FROM COMANDA c2
        WHERE c2.id_client = c1.id_client
    )
);

La divisió es pot expressar amb els operadors fonamentals:

R ÷ S = π_A(R) − π_A((π_A(R) × S) − R)

Equivalències àlgebra relacional ↔ SQL

Àlgebra relacional SQL
σ_condició(R) WHERE condició
π_a1,a2(R) SELECT DISTINCT a1, a2
R ∪ S UNION
R − S EXCEPT / MINUS
R ∩ S INTERSECT
R × S CROSS JOIN
R ⋈_θ S JOIN ... ON θ
R ⋈ S NATURAL JOIN
ρ_nou(R) AS nou

Propietats dels operadors

Conèixer les propietats permet l'optimització algebraica: el SGBD reescriu la consulta en una forma equivalent però més eficient.

Commutativitat

  • R ∪ S = S ∪ R
  • R ∩ S = S ∩ R
  • R ⋈ S = S ⋈ R
  • R × S ≠ S × R (el resultat és equivalent però l'ordre de les columnes canvia)

Associativitat

  • (R ∪ S) ∪ T = R ∪ (S ∪ T)
  • (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

Regla de cascada de seleccions

Una selecció conjuntiva es pot descompondre:

σ_c1 ∧ c2(R) = σ_c1(σ_c2(R))

Això permet baixar les seleccions a prop de les fulles de l'arbre per reduir el nombre de tuples el més aviat possible.

Conmutació selecció-producte cartesià

Si la condició c només afecta atributs de R:

σ_c(R × S) = σ_c(R) × S

Aquesta és la transformació que converteix un producte cartesià + selecció en un join: el SGBD aplica primer el filtre i redueix R abans de fer el producte.

Arbres d'operadors

Les expressions d'àlgebra relacional es representen com a arbres, on:

  • Les fulles són les relacions base.
  • Els nodes interns són els operadors.
  • L'arrel és el resultat final.

Exemple: Noms dels clients de Barcelona que han fet almenys una comanda:

π_nom
  |
σ_ciutat='Barcelona'
  |
CLIENT ⋈_(CLIENT.id_client=COMANDA.id_client) COMANDA

El SGBD pot reordenar l'arbre per optimitzar:

π_nom
  |
σ_ciutat='Barcelona'(CLIENT) ⋈ COMANDA

Aplicant primer la selecció a CLIENT reduïm el nombre de tuples que participen al join.

Exercicis

Usa l'esquema d'exemple (CLIENT, PRODUCTE, COMANDA) per expressar les consultes següents en àlgebra relacional i, després, en SQL:

  1. Llista els noms dels clients majors de 30 anys.
  2. Quins productes costen menys de 100 EUR?
  3. Obté les comandes realitzades per la client Anna.
  4. Llista les categories de productes que han estat comprats (sense repeticions).
  5. Quins clients han fet almenys una comanda de més de 2 unitats?
  6. Llista els noms dels clients que no han fet cap comanda.
  7. Quins clients han comprat productes de totes les categories?

Ordre recomanat

Per resoldre una consulta en àlgebra relacional, convé seguir aquest ordre: (1) identifica les taules que necessites, (2) aplica les seleccions per filtrar files, (3) fes els joins necessaris, (4) projecta les columnes que vols al resultat.