Ristrutturazione dello schema ER e traduzione nel modello relazionale

Lo schema ER (Modello entità-relazione - entità, relazioni e attributiIl modello entità-relazione (ER, Chen 1976) descrive il mini-mondo con entità (classi di oggetti autonomi), relazioni (associazioni tra due o più entità, di grado 2 o più) e attributi (proprietà locali di entità o relazioni su un dominio; NULL per l'informazione mancante, con tre significati; attributi composti). Ogni costrutto ha una semantica estensionale: un'entità è un insieme di oggetti (senza ripetizioni né ordine), una relazione è un sottoinsieme del prodotto cartesiano delle entità coinvolte (quindi la stessa coppia non può comparire due volte: per gli eventi ripetuti si introduce una nuova entità, come Sessione o Fattura), un attributo è una funzione totale dalle istanze a un dominio. Si sceglie un'entità invece di un attributo quando il concetto ha istanze con proprietà proprie o collegamenti; mai trasformare un'entità in relazione. Lo schema ER è documentato dal dizionario dei dati (entità, relazioni, attributi, vincoli esterni).Modello entità-relazione - entità, relazioni e attributi →, Relazioni ricorsive, cardinalità e vincoli di integrità nel modello ERI vincoli di integrità di uno schema ER sono di quattro tipi: di cardinalità sulle relazioni, di cardinalità sugli attributi, di identificazione sulle entità e vincoli esterni. La cardinalità (min,max) di un'entità e con ruolo u in una relazione r dice a quante istanze di r partecipa ogni istanza di e: min 0 = partecipazione opzionale, min 1 = obbligatoria, max 1 = al più una volta, max N = molte; le relazioni binarie si classificano per i massimi in uno-a-uno, uno-a-molti, molti-a-molti. I vincoli di cardinalità non permettono di violare la semantica estensionale (una coppia compare una volta sola). Una relazione ricorsiva collega un'entità con se stessa e richiede i ruoli (Predecessore e Successore, Sorgente e Destinazione): con le cardinalità si ottengono catene, alberi e grafi diretti; grafi non diretti, assenza di cicli e di cappi richiedono vincoli esterni; i multigrafi si modellano con una terza entità (etichetta, colore). Gli attributi hanno cardinalità (1,1) di default, (0,1) se opzionali, (x,N) se multivalore.Relazioni ricorsive, cardinalità e vincoli di integrità nel modello ER →, Generalizzazioni e identificatori nel modello ERUna relazione IS-A tra superclasse e sottoclasse significa che ogni istanza della sottoclasse è anche istanza della superclasse (inclusione tra estensioni: riflessiva e transitiva, non simmetrica); vale il principio di ereditarietà: attributi, relazioni e vincoli della superclasse sono propri anche delle sottoclassi e non si ridisegnano. Una generalizzazione è una superclasse con più sottoclassi secondo un solo criterio, con due vincoli: completezza (ogni istanza della superclasse è in almeno una sottoclasse) e disgiunzione (in al più una); si hanno quattro combinazioni, e partizione se completa e disgiunta. Su una stessa entità possono esserci più generalizzazioni indipendenti con criteri diversi. L'identificatore di un'entità è un insieme di proprietà che identifica ogni istanza: interno se formato da soli attributi (1,1) dell'entità, esterno se contiene ruoli di relazioni (1,1) con altre entità (con eventuali attributi), come per l'entità debole; ogni entità ne ha almeno uno.Generalizzazioni e identificatori nel modello ER →) non si traduce direttamente in tabelle: tra i due modelli c'è un disadattamento (impedance mismatch).

Per questo la progettazione logica ha due passi:

1. Ristrutturazione dello schema ER: si tolgono i costrutti non esprimibili e si scelgono gli identificatori principali (qui servono decisioni del progettista, in base al carico);
2. Traduzione nello schema relazionale: quasi automatica, perché non richiede (quasi) scelte. Lo schema prodotto non contiene ridondanze, se non quelle aggiunte e motivate.

I concetti del modello di arrivo (chiave, chiave esterna) sono in Modello relazionale - relazioni, chiavi e vincoliIl modello relazionale (Codd, IBM, 1970) rappresenta i dati con relazioni, cioè tabelle, ed è basato su valori: i legami tra relazioni sono confronti di valori, non puntatori, il che garantisce indipendenza dalle strutture fisiche, portabilità e bidirezionalità. Una relazione matematica è un sottoinsieme del prodotto cartesiano di n domini (insieme di n-uple ordinate, senza duplicati né ordine tra le righe); una relazione del modello è un insieme di tuple, funzioni dagli attributi ai valori del dominio, quindi non posizionale. Si distinguono schema di relazione e istanza, schema di base di dati (relazioni più vincoli) e istanza. NULL è un valore speciale fuori da ogni dominio. I vincoli di integrità sono intra-relazionali (di dominio, di tupla, di chiave) e inter-relazionali (integrità referenziale, con la chiave esterna). Superchiave: insieme di attributi che non ripete mai i valori; chiave: superchiave minimale; ogni relazione ne ha almeno una (tutti gli attributi); la chiave primaria è una chiave scelta, senza NULL.Modello relazionale - relazioni, chiavi e vincoli →; qui si usa la notazione $R(\underline{K},\,A,\,B)$ con la chiave primaria sottolineata (nei blocchi di codice: * indica la chiave primaria e FK le chiavi esterne).

Passo 1: ristrutturazione

I passi, in ordine: (1) analisi delle ridondanze; (2) eliminazione degli attributi multivalore; (3) degli attributi composti; (4) delle IS-A e delle generalizzazioni; (5) scelta degli identificatori principali; (6) specifica dei vincoli esterni; (7) partizionamento e accorpamento di entità.

1. Analisi delle ridondanze

Per la minimalità non si deve rappresentare la stessa proprietà due volte. La ridondanza intensionale (nello schema) si elimina con trasformazioni che conservano l'informazione; quella estensionale (nelle istanze) si tiene solo se motivata da prestazioni.

a) Attributi comuni a una generalizzazione. Un attributo $D$ comune alle sottoclassi $E_1,E_2$ di $E$ si sposta in $E$.

b) Identificatori non minimali. Un identificatore formato da un sovrainsieme di un altro identificatore si sostituisce con quello minimale.

c) Cicli di relazioni. Può esserci ridondanza quando una relazione $R_1$ tra due entità ha lo stesso contenuto informativo di una catena $R_2,\dots,R_n$ che collega le stesse coppie. Non ogni ciclo è ridondante: dipende dal significato. Controlli sintattici: un ciclo di uno-a-uno dà un uno-a-uno, un ciclo di uno-a-molti dà uno-a-molti; uno-a-molti seguito da molti-a-uno può dare qualunque tipo (la cardinalità non si conosce a priori).

Esempio 1 (ridondante). Vincolo esterno: ogni Persona proviene dalla Regione a cui appartiene la Città di nascita. Relazioni: Nasce (Persona (1,1), Città (0,N)), Appartiene (Città (1,1), Regione (1,N)), ProvieneDa (Persona (1,1), Regione (0,N)). ProvieneDa è derivabile: Persona → Città → Regione. Si elimina ProvieneDa (rispetta il vincolo, anzi lo rimuove, e lo schema si spiega da solo). Eliminare invece Appartiene sarebbe sbagliato: da Persona-Regione non si saprebbe più in quale città nasce.

Esempio 2 (ridondante, ma solo una relazione si può togliere). Vincolo: ogni Impiegato collabora con il Direttore che dirige il Dipartimento dove lavora. Relazioni: Collabora (Impiegato (1,1), Direttore (1,N)), Dirige (Direttore (1,N), Dipartimento (1,1)), Lavora (Impiegato (1,1), Dipartimento (1,N)): un impiegato ha un dipartimento, un dipartimento ha un direttore, quindi il direttore dell'impiegato è determinato. Si può eliminare Collabora (rispetta il vincolo, conserva l'informazione, si spiega da solo). Eliminare Dirige o Lavora conserva il vincolo ma non l'informazione (non si sa più in quale dipartimento lavora l'impiegato, o quale dipartimento dirige il direttore).

d) Attributi derivati. Un attributo è derivato se si calcola da altri attributi della stessa entità (Età da DataNascita; StipendioNetto = Lordo - Tasse) o di altre entità (Abitanti di Città = conteggio delle Vive). Per Età, oltre all'aggiornamento è sempre potenzialmente incoerente perché cambia nel tempo: meglio tenere DataNascita. Per ogni derivato si decide se tenerlo, con il carico della base di dati. Pro: non serve calcolarlo, meno accessi in lettura. Contro: serve un vincolo esterno per la coerenza, elaborazione per mantenerlo allineato, più spazio. Se si tiene, va documentato.

Il carico di una base di dati

Il carico è dato da due informazioni: il volume dei dati (numero medio di istanze di ogni entità e relazione, cardinalità media di partecipazione) e le operazioni, ciascuna con il proprio schema di operazione (la parte di schema coinvolta) e uno schema di navigazione, con le lettere I, U, D, R (insert, update, delete, read). Le operazioni sono online (interattive, più importanti) o batch (in background, per esempio di notte). Si compilano due tabelle:

• tabella delle frequenze: operazione, descrizione, frequenza, tipo (online/batch);
• tabella degli accessi/volume: costrutti coinvolti, tipo (entità o relazione), numero di accessi, tipo di accesso (lettura R o scrittura W), accessi medi totali, con peso 1 per le letture e 2 per le scritture.

Esempio: Abitanti in Città. Persona(CF, nome), Città(nome, indirizzo, Abitanti), Vive (Persona (1,1), Città (0,N)). Volumi: Persona 1 000 000, Città 200, Vive 1 000 000 (cioè in media 5 000 abitanti per città). Operazioni: O1 inserire una persona con la sua città (500 al giorno, online); O2 stampare i dati di una città, abitanti compresi (2 al giorno, online); O3 riassumere tutte le città (1 all'anno, batch, qui trascurata).

Totale al giorno: 3502 con la ridondanza contro 12002 senza. Considerando solo O1 conviene toglierla, ma con O2 (o con entrambe) conviene tenerla, aggiungendo un vincolo esterno: all'inserimento o cancellazione di Persona e Vive si aggiorna Abitanti.

2. Eliminazione degli attributi multivalore

Il modello relazionale non ammette attributi multivalore. Per un'entità $E$ con attributo multivalore $A$ di cardinalità $(x,y)$: si crea una nuova entità $F$ (con l'attributo $A$ come identificatore) e una relazione binaria tra $E$ e $F$ con $E$ $(x,y)$ ed $F$ $(1,N)$. La cardinalità (1,N) di $F$ dice che interessano solo i valori di $A$ effettivamente usati.

Esempio: Impiegato con Telefono (0,N) → Impiegato, Telefono(numero), relazione Possiede (Impiegato (0,N), Telefono (1,N)). Se l'attributo è condiviso da più entità $E_1$, $E_2$, si usa la stessa $F$ e un vincolo esterno per la cardinalità (1,N) di $F$ sull'unione delle due relazioni.

Per un attributo multivalore di una relazione, la relazione si trasforma prima in entità (con relazioni (1,1) verso le entità originali), poi si procede come sopra.

3. Eliminazione degli attributi composti

Se cardinalità (1,1): si sostituiscono con i componenti. Esempio: Indirizzo(Via, Numero, CAP) → tre attributi di Persona. Se (0,1): oppure si appiattiscono con vincolo esterno ("le tre componenti di Matrimonio sono definite tutte o nessuna"), oppure si crea una nuova entità con i componenti e una relazione (0,1) verso l'originale. Per un composto di una relazione si trasforma prima la relazione in entità.

4. Eliminazione di IS-A e generalizzazioni

IS-A. Una relazione $E$ IS-A $F$ diventa una nuova relazione binaria ISA-E-F con $E$ $(1,1)$ ed $F$ $(0,1)$, e $E$ riceve un identificatore esterno dalla relazione.

Implicazione estensionale: prima $s_3$ era lo stesso oggetto in Persona e in Studente; dopo, Persona e Studente sono entità distinte, con istanze diverse collegate dalla relazione: $(s_3,p_3)\in I(\text{ISA-S-P})$.

Generalizzazione. Tre opzioni (le prime due vanno bene per ogni tipo di generalizzazione, la terza solo per quelle complete e disgiunte).

Esempi (Persona ⊃ {Femmina, Maschio}, completa e disgiunta, Femmina ha Gravidanza, Maschio ha ServizioMilitare):

• Opzione 2: Persona(Cognome, Età, Gravidanza (0,1), ServizioMilitare (0,1), Sesso (1,1)), con vincolo esterno: Gravidanza solo se Sesso=F, ServizioMilitare solo se Sesso=M. Per Persona ⊃ {Studente, Docente} non completa e disgiunta: attributo Ruolo (0,1), con vincoli per DataIscrizione e DataAssunzione. Per non disgiunta il massimo di Ruolo è N.
• Opzione 3: Femmina(Cognome, Età, Gravidanza), Maschio(Cognome, Età, ServizioMilitare).

Come si sceglie. Si dividono le operazioni in due insiemi. Insieme A: operazioni che usano gli attributi del padre $p$ (vanno bene opzioni 1 e 2). Insieme B: operazioni che usano gli attributi del padre insieme a quelli di una sottoclasse (vanno bene l'opzione 3). Se B prevale, opzione 3 (se la generalizzazione è completa e disgiunta). Se prevale A: opzione 2 se gli attributi del padre e del figlio si usano insieme, opzione 1 se si usano separatamente.

5. Scelta degli identificatori principali

Per ogni entità si sceglie un identificatore principale tra i possibili. Criteri: minimalità (meno attributi), preferire gli identificatori interni, usare quello più impiegato nelle operazioni importanti. Gli identificatori principali esterni creano un grafo di identificazione (un nodo per entità, un arco da $E$ a $F$ se $E$ partecipa alla relazione che identifica $F$): un ciclo nel grafo (entità che si identificano a vicenda) è un errore e si elimina scegliendo un altro identificatore o introducendo un codice ad hoc.

6. Vincoli esterni

Si riformulano tutti i vincoli esterni sullo schema trasformato e si aggiungono quelli nati dalla trasformazione: vincoli per attributi multivalore, per i composti opzionali, di disgiunzione e completezza, per gli identificatori non principali (ora rimossi).

7. Partizionamento e accorpamento

• Partizionamento orizzontale: $E$ si divide in $E_1,\dots,E_n$ con gli stessi attributi ma istanze diverse, scelte con un predicato (per esempio ordini aperti e ordini chiusi). Verticale: $E$ si divide in entità con gli stessi oggetti ma gruppi di attributi diversi, ciascuna con il proprio identificatore, collegate da relazioni uno-a-uno (1,1)-(1,1) (per mettere insieme gli attributi usati insieme). Servono per le prestazioni.
• Accorpamento: più entità si fondono in una, con tutti gli attributi e le relazioni (è l'opposto della trasformazione che toglie gli attributi opzionali). Esempio: Ordine e NotaDiConsegna con relazione (0,1)-(1,1): si fonde, con gli attributi di consegna opzionali. Ha l'effetto collaterale di perdere la de-duplicazione.

Passo 2: traduzione nel modello relazionale

Si parte dallo schema ER ristrutturato e dai vincoli, e si ottiene uno schema relazionale con i suoi vincoli. Passi: (1) entità → relazioni con i loro vincoli; (2) relazioni → relazioni (o fuse in un'entità); (3) vincoli esterni. Lo schema ottenuto di solito è già di buona qualità (Dipendenze funzionali e normalizzazione - BCNF e terza forma normaleLa qualità di uno schema relazionale si misura con quattro linee guida informali: semantica chiara degli attributi (una relazione per un'entità o associazione), niente ridondanza che causi anomalie di inserimento, cancellazione e modifica, pochi NULL sistematici, nessuna tupla spuria dopo un join (si unisce solo su chiavi primarie ed esterne). La normalizzazione verifica queste proprietà con le dipendenze funzionali X -> Y (se due tuple coincidono su X coincidono su Y), usando le regole di Armstrong (riflessiva, aumento, transitiva) e la chiusura X+ per trovare chiavi. 1NF: attributi atomici (si tolgono multivalore e relazioni annidate). 2NF: ogni attributo non primo dipende completamente da ogni chiave (niente dipendenze parziali). 3NF: nessun attributo non primo dipende transitivamente da una chiave; equivalentemente per ogni X -> A, X è superchiave oppure A è primo. BCNF: per ogni X -> A non banale X è superchiave. Si ottiene scomponendo senza perdere informazione (join senza perdita se l'intersezione determina una delle parti); la 3NF si ottiene sempre mantenendo le dipendenze, la BCNF a volte le perde. Un buon schema ER tradotto è già normalizzato.Dipendenze funzionali e normalizzazione - BCNF e terza forma normale →), si può controllare la normalizzazione.

Entità

Ogni entità $E$ diventa una relazione $R_E$:

• attributi: tutti quelli di $E$, più quelli che derivano dalla fusione di relazioni (per ogni relazione $Q$ fusa: gli attributi di $Q$ e gli identificatori delle altre entità di $Q$);
• chiave primaria: l'identificatore principale di $E$ (anche esterno);
• identificatore esterno: la chiave primaria include gli attributi che vengono dalla chiave dell'entità collegata, che sono anche chiave esterna.

Esempio (Studente identificato da Badge e da Università): Studente(Badge, Università, Nome, Cognome) con FK Università → Università(Nome, Città). Per l'entità debole Copia: Copia(Libro, Inventario) con FK Libro → Libro(ISBN).

Relazioni

Una relazione $Q$ non fusa diventa una relazione con gli attributi di $Q$ più le chiavi primarie delle entità coinvolte (che sono chiavi esterne). Chiave primaria: se nessuna entità partecipa con massimo 1, è l'insieme di tutte le chiavi delle entità; altrimenti ogni entità con massimo 1 ha una chiave e si sceglie una delle candidate.

Regola breve: nelle uno-a-molti la chiave esterna (il riferimento) va nella relazione del lato con massimo 1 (quello che ha al più un partner) e punta all'altro; nelle uno-a-uno, dove entrambi i lati hanno massimo 1, si sceglie il lato con partecipazione obbligatoria. Si fonde (cioè non si crea una tabella) quando la partecipazione di quel lato è obbligatoria; con partecipazione opzionale si valuta se i NULL sono sistematici.

Ternarie con un lato (1,1). Si ripete il pattern uno-a-molti: la relazione che ha il lato $E_3$ con massimo 1 riceve le chiavi di $E_1$ e $E_2$ e gli attributi della relazione ($E_3(\underline{E},F,A,C,X)$). Se la partecipazione di $E_3$ è (0,1) la fusione è comunque corretta (i NULL non sono sistematici se non c'è più partecipazione obbligatoria).

Relazioni ricorsive. Vale la stessa regola con ruoli distinti come nomi di colonna diversi. Esempio albero: Nodo(ID, A), relazione Arco con Sorgente (0,N), Destinazione (0,1) e attributo B. Il lato con massimo 1 è la Destinazione: ogni nodo ha al più un arco entrante, quindi la sua riga contiene il nodo di origine: Nodo(ID, A, B, sorgente) con FK sorgente → Nodo(ID). La chiave esterna sta nella colonna dell'entità che partecipa con max 1 e il valore è l'altro partecipante: scrivere Nodo(ID, A, destinazione, B) direbbe il contrario, cioè che ogni nodo ha un solo arco uscente. Per un grafo con (0,N) su entrambi i ruoli: Arco(sorgente, destinazione, B) con due FK verso Nodo; con un'etichetta (multigrafo) la chiave include anche l'etichetta.

Attributi di relazione e eventi ripetuti. Una relazione molti-a-molti $R(\underline{A,B},C)$ non può contenere due istanze con la stessa coppia $(A,B)$: violerebbe la chiave primaria. Se serve ripetere, la relazione diventa un'entità con un proprio ID, $R(\underline{ID},A,B,C)$, e non è più una relazione concettualmente: se si vuole davvero, si modella così già nell'ER.

Esempio completo: la biblioteca

Dallo schema della nota ER (Libro, Autore, Copia, Iscritto, Prestito; Scrive N:N, Possiede 1:N con Copia identificata dal libro, Riguarda e Effettua uno-a-molti da Prestito):

Libro(*ISBN, titolo)
Autore(*id, nome)
Scrive(*autore, *libro)             FK autore -> Autore(id); FK libro -> Libro(ISBN)
Copia(*libro, *inventario)          FK libro -> Libro(ISBN)
Iscritto(*codice, nome, indirizzo)
Prestito(*id, data_inizio, libro, inventario, iscritto)
   FK (libro, inventario) -> Copia(libro, inventario);  FK iscritto -> Iscritto(codice)

Il prestito ha (1,1) verso Copia e verso Iscritto: fusione con due chiavi esterne, una composta perché Copia ha chiave composta. In SQL:

CREATE TABLE Libro   (ISBN TEXT PRIMARY KEY, titolo TEXT NOT NULL);
CREATE TABLE Autore  (id INTEGER PRIMARY KEY, nome TEXT NOT NULL);
CREATE TABLE Scrive  (autore INT REFERENCES Autore(id), libro TEXT REFERENCES Libro(ISBN),
                      PRIMARY KEY (autore, libro));
CREATE TABLE Copia   (libro TEXT REFERENCES Libro(ISBN), inventario INT,
                      PRIMARY KEY (libro, inventario));
CREATE TABLE Iscritto(codice INTEGER PRIMARY KEY, nome TEXT NOT NULL, indirizzo TEXT);
CREATE TABLE Prestito(id INTEGER PRIMARY KEY, data_inizio DATE NOT NULL,
                      libro TEXT NOT NULL, inventario INT NOT NULL,
                      iscritto INT NOT NULL REFERENCES Iscritto(codice),
                      FOREIGN KEY (libro, inventario) REFERENCES Copia(libro, inventario));

(Gli attributi NOT NULL rendono operativa la cardinalità minima 1; la massima 1 è la fusione.)

Mappare i vincoli

• Cardinalità minime: NOT NULL sulle chiavi esterne dei lati (1,1); le relazioni N:N non le esprimono, servono vincoli esterni.
• Vincoli esterni, di disgiunzione e completezza: espressi con tuple constraint, CHECK, trigger o a livello applicativo, e documentati.
• Domini e identificatori non principali: chiavi candidate con UNIQUE.

Domande d'esame

1. Come si traduce una relazione uno-a-molti con partecipazione opzionale del lato uno? Traccia. Due modi: fusione nella relazione del lato con massimo 1 con chiave esterna ammessa NULL, oppure relazione a parte con le due chiavi. La seconda evita NULL sistematici (utile se pochi hanno un partner).

2. Come si elimina una generalizzazione e come si sceglie l'opzione? Traccia. Tre opzioni: relazioni IS-A con vincoli esterni, accorpamento nel padre con attributo discriminante (NULL sistematici), accorpamento nei figli (solo completa e disgiunta). Si guarda quali operazioni usano gli attributi del padre insieme a quelli dei figli.

3. Un attributo derivato conviene sempre eliminarlo? Traccia. No: si confrontano gli accessi totali delle operazioni con e senza (peso 2 alle scritture). Nell'esempio Abitanti 3502 contro 12002 al giorno: si tiene, documentato, con vincolo esterno per l'aggiornamento.