Il modello relazionale: chiavi, vincoli e algebra relazionale

Nel 1970 Edgar Codd, ricercatore dell’IBM, propose di rappresentare i dati come semplici tabelle e di interrogarli con operazioni matematiche, invece di navigare tra puntatori come nei sistemi dell’epoca. Il modello relazionale è ancora la base di quasi tutti i sistemi informativi. In questa lezione vediamo le relazioni e le chiavi con la dimostrazione che ogni relazione ne ha almeno una, i vincoli d’integrità, l’algebra relazionale con selezione, proiezione e giunzione, la dimostrazione dei limiti sulla dimensione di una giunzione, e il legame con SQL.

Relazioni, tuple e attributi

Una relazione è una tabella con un nome, colonne con nome (gli attributi) e righe (le tuple). Matematicamente è un insieme di tuple: l’ordine delle righe non conta e non ci sono due righe uguali. Ogni attributo prende valori in un dominio (interi, date, stringhe), e ogni cella contiene un solo valore atomico. Lo schema della relazione è il nome con gli attributi, Studente(matricola, nome, cognome, nascita); l’istanza è il contenuto in un certo momento.

Le chiavi

Una superchiave è un insieme di attributi che non assume mai lo stesso valore in due tuple diverse. Una chiave è una superchiave minimale: togliendo un qualsiasi attributo non è più superchiave.

Teorema. Ogni relazione ha almeno una chiave.

Dimostrazione. L’insieme di tutti gli attributi è una superchiave: due tuple con tutti i valori uguali sarebbero la stessa tupla, e una relazione è un insieme, quindi non ha duplicati. Se questa superchiave non è minimale, si toglie un attributo che la lascia superchiave, e si ripete. Gli attributi sono in numero finito, quindi il procedimento termina, e l’insieme a cui si arriva è una superchiave da cui non si può togliere nulla: una chiave. ∎

Tra le chiavi se ne sceglie una come chiave primaria, su cui non si ammettono valori nulli. Spesso si usa un codice artificiale (un numero progressivo) anche quando esiste una chiave naturale, perché è più stabile e più compatto.

I vincoli d’integrità

Il modello non accetta qualsiasi dato: i vincoli esprimono le regole del mondo reale e il DBMS li fa rispettare.

• Vincoli di dominio e di tupla: il voto è tra 18 e 30, la data di fine non precede quella d’inizio.
• Vincolo di chiave: nessun duplicato sulla chiave primaria, nessun valore nullo.
• Integrità referenziale: una chiave esterna deve riferire una tupla esistente. Ogni esame si riferisce a uno studente presente nella tabella Studente. Quando si cancella lo studente, il DBMS può rifiutare la cancellazione, cancellare anche i suoi esami (a cascata) o mettere a nullo il riferimento, secondo come è stato dichiarato il vincolo.

L’algebra relazionale

Le interrogazioni si costruiscono con operatori che prendono relazioni e restituiscono relazioni, e quindi si possono comporre:

• selezione : le tuple che soddisfano una condizione, cioè un sottoinsieme delle righe;
• proiezione : solo alcune colonne, eliminando i duplicati che ne risultano;
• unione, differenza, intersezione di relazioni con lo stesso schema;
• ridenominazione degli attributi;
• giunzione naturale : combina le tuple delle due relazioni che hanno valori uguali sugli attributi comuni.

Teorema. La giunzione naturale di e ha un numero di tuple compreso tra 0 e . Se gli attributi comuni contengono una chiave di , il risultato ha al massimo tuple; se in più c’è un vincolo di integrità referenziale da verso su quegli attributi, ne ha esattamente .

Dimostrazione. Ogni tupla del risultato nasce da una coppia di tuple, una di e una di , e le coppie possibili sono : è il massimo, raggiunto quando tutte hanno lo stesso valore sugli attributi comuni. Il minimo 0 si ha quando nessun valore coincide. Se gli attributi comuni contengono una chiave di , per ogni tupla di esiste al più una tupla di con quei valori, quindi ogni tupla di contribuisce al più una tupla al risultato. Con il vincolo referenziale quella tupla di esiste sempre, e il contributo è esattamente uno. ∎

È il caso più comune: unire gli esami (con la chiave esterna) agli studenti (con la chiave) dà una riga per esame, arricchita con i dati dello studente. Saperlo aiuta a capire quando una query restituisce “troppe righe”: di solito si è unito su attributi che non sono chiave.

Dall’algebra a SQL

SQL, il linguaggio di tutti i DBMS relazionali (lezione su SQL), è un linguaggio dichiarativo costruito su queste operazioni: si dice che cosa si vuole, non come ottenerlo.

SELECT s.cognome, e.voto
FROM Studente s JOIN Esame e ON s.matricola = e.matricola
WHERE e.voto >= 28;

corrisponde a . Il DBMS traduce la richiesta in un’espressione dell’algebra e la ottimizza con equivalenze algebriche: per esempio esegue la selezione prima della giunzione, così si uniscono meno tuple. Questa indipendenza tra la domanda e il modo di rispondere, possibile grazie alla base matematica del modello, è la ragione principale del suo successo.