Esercizio - Traduzione da ER a relazionale - dodici casi (esercizi di traduzione del corso)

Testo (esercizi di traduzione ER → relazionale, corso di Basi di Dati, Ing. Informatica UniPD). Per ognuno di dodici piccoli schemi ER si chiede lo schema relazionale con le chiavi primarie e le chiavi esterne. Regole di partenza (note Ristrutturazione dello schema ER e traduzione nel modello relazionaleLa progettazione logica ha due passi. 1) Ristrutturazione dello schema ER, per togliere i costrutti che il modello relazionale non esprime: analisi delle ridondanze (attributi derivati e cicli di relazioni, decisa con volume dei dati e carico, tabelle di frequenza e accessi), eliminazione degli attributi multivalore (nuova entità), composti (appiattiti o nuova entità), delle IS-A (relazione con partecipazione (1,1) dalla sottoclasse) e delle generalizzazioni (opzione 1 relazioni, 2 accorpamento nel padre con attributo discriminante, 3 accorpamento nei figli, solo se completa e disgiunta), scelta degli identificatori principali (niente cicli di identificazione esterna), riscrittura dei vincoli esterni, partizionamento e accorpamento di entità. 2) Traduzione quasi automatica nel modello relazionale: ogni entità diventa una relazione con la chiave primaria data dall'identificatore principale (anche esterno); una relazione molti-a-molti diventa una relazione con le chiavi delle entità; una uno-a-molti con partecipazione obbligatoria si fonde con l'entità dal lato max 1 con una chiave esterna; con partecipazione opzionale si fonde (NULL) o si crea una relazione a parte; le uno-a-uno si fondono sul lato con partecipazione obbligatoria; le ternarie seguono la stessa logica con le chiavi di tutte le entità.Ristrutturazione dello schema ER e traduzione nel modello relazionale →): ogni entità diventa una relazione con l'identificatore principale come chiave; ogni relazione molti-a-molti diventa una relazione con le chiavi delle entità; nelle relazioni uno-a-molti e uno-a-uno la chiave dell'altra entità si porta, come chiave esterna, dal lato con massimo 1; si tiene una tabella a parte quando i NULL della fusione sarebbero sistematici.

Notazione: chiave primaria con *, chiave esterna con FK. Gli esempi sono stati controllati con SQLite (script con dati di esempio).

Caso 1: uno-a-molti con partecipazione obbligatoria o opzionale

ER: Giocatore (Badge, Nome) $(1,1)$ — Gioca (Stipendio) — $(0,N)$ Squadra (NomeSquadra, B).

Il lato con massimo 1 è Giocatore: la relazione si fonde in Giocatore.

Giocatore(*badge, nome, nome_squadra, stipendio)    FK nome_squadra -> Squadra(nome_squadra)
Squadra(*nome_squadra, b)

Con la partecipazione obbligatoria (1,1) si può imporre nome_squadra NOT NULL.

Variante (0,1). Se un giocatore può non giocare in nessuna squadra, la fusione produce NULL sistematici in nome_squadra e stipendio per chi non gioca, e un vincolo esterno complicato ("stipendio è NULL se e solo se nome_squadra è NULL"). Meglio una tabella a parte:

Giocatore(*badge, nome)
Gioca(*badge, nome_squadra, stipendio)    FK badge -> Giocatore(badge); FK nome_squadra -> Squadra(nome_squadra)
Squadra(*nome_squadra, b)

La chiave di Gioca è il solo badge, perché ogni giocatore gioca in al più una squadra. È la scelta migliore quando la maggior parte dei giocatori non gioca, perché la relazione non occupa righe per chi non gioca.

Caso 2: uno-a-uno con partecipazione obbligatoria da entrambi i lati

ER: Direttore (Badge, B) $(1,1)$ — Dirige (DataInizio) — $(1,1)$ Dipartimento (Dip, C).

Due traduzioni equivalenti, entrambe valide:

Direttore(*badge, b, dip, data_inizio)  FK dip -> Dipartimento(dip)   -- chiave candidata: dip (UNIQUE)
Dipartimento(*dip, c)

oppure il simmetrico, con il badge del direttore dentro Dipartimento. Una terza variante tiene la relazione a parte, Dirige(*badge, dip, data_inizio) con dip chiave candidata UNIQUE: utile se si vuole tenere fuori dalle entità la data di inizio. In ogni caso la colonna che porta la chiave esterna ha anche un vincolo UNIQUE, altrimenti due direttori avrebbero lo stesso dipartimento.

Caso 3: entità con identificatore esterno

ER: Utente (ID, Nome) $(0,1)$ — Ha — $(1,1)$ Profilo (Immagine), con Profilo identificato esternamente dal ruolo verso Utente.

Utente(*id, nome)
Profilo(*id, immagine)      FK id -> Utente(id)

Qui id di Profilo è sia chiave primaria sia chiave esterna. Si tiene Profilo separato per evitare NULL sistematici: tanti utenti non hanno un profilo.

Caso 4: ternaria con un lato (1,1)

ER: E1 (A, B) $(0,N)$, E2 (C, D) $(0,N)$, E3 (E, F) $(1,1)$, relazione ternaria R con attributo X.

Il pattern uno-a-molti si ripete anche per le ternarie: il lato con massimo 1 è E3, che porta le chiavi degli altri due e l'attributo:

E1(*a, b)
E2(*c, d)
E3(*e, f, a, c, x)        FK a -> E1(a); FK c -> E2(c)

Ogni istanza di E3 compare in esattamente una tripla (1,1), quindi i valori a, c, x esistono sempre (NOT NULL).

Caso 5: ternaria con un lato (0,1) o con due lati a massimo 1

ER: lo schema del caso 4, ma con partecipazione di E1 pari a $(0,1)$ e E3 con $(1,1)$ (nel disegno del corso le cardinalità sono ritoccate a mano e la lettura è incerta; il principio è comunque il seguente).

• Quando il lato a massimo 1 ha partecipazione obbligatoria, la fusione è l'identica del caso 4 e non crea NULL: nell'esempio E3 con chiavi a, c e x, con a UNIQUE perché anche E1 ha massimo 1.
• Se invece la fusione va nell'entità con partecipazione opzionale (E1, $(0,1)$), le colonne e, c, x sono NULL per le istanze che non partecipano: il corso mostra comunque questa tabella E1(a, b, e, c, x) con FK verso E3 e E2. Va bene se non ci sono più partecipazioni obbligatorie che la rendano problematica; altrimenti è preferibile una tabella a parte R(a, e, c, x).

Caso 6: molti-a-molti con identificatore composto

ER: E1 (A, B, C) $(0,N)$ — R (X) — $(0,N)$ E2 (D, F). L'identificatore di E1 è formato da due attributi.

E1(*a, *b, c)
E2(*d, f)
R(*a, *b, *d, x)      FK (a, b) -> E1(a, b); FK d -> E2(d)

La coppia (a, b) è una sola chiave esterna composta, non due. Osservazione del corso: si può sempre tenere in una tabella a parte anche una relazione uno-a-uno o uno-a-molti, ma serve una buona motivazione (per esempio NULL sistematici), altrimenti è eccessivo.

Caso 7: relazione ricorsiva (albero o grafo)

ER: Nodo (ID, A), relazione ricorsiva Arco con ruoli Sorgente $(0,N)$ e Destinazione $(0,1)$ e attributo B.

La cardinalità massima 1 sulla Destinazione dice che ogni nodo ha al più un arco entrante, cioè al più un padre: albero. La chiave esterna va nella riga del nodo che partecipa con max 1 (il figlio) e contiene l'altro estremo (il padre):

Nodo(*id, a, b, sorgente)        FK sorgente -> Nodo(id)     -- NULL per la radice

Una soluzione equivalente tiene l'arco a parte: Arco(sorgente, *destinazione, b) con la sola destinazione come chiave (solo la destinazione ha massimo 1), con due chiavi esterne verso Nodo.

Errore da evitare: Nodo(id, a, destinazione, b) dice l'opposto: ogni nodo ha un solo arco uscente (la Sorgente andrebbe verso la Destinazione con massimo 1). Esempio di istanza corretta: Nodo(n1, x1, NULL, y1), (n2, x2, n1, y2), (n3, x3, n1, y3), (n4, x4, n3, y1), (n5, x5, n3, y3) è l'albero con radice n1, figli n2, n3, e n4, n5 sotto n3. Se Sorgente e Destinazione fossero entrambi $(0,N)$ (grafo diretto) servirebbe Arco(*sorgente, *destinazione, b) con due FK. Vedi AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).Alberi → e Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →.

Caso 8: ternaria con E3 opzionale $(0,1)$

ER: ternaria R (X) tra E1 (A, B), E2 (C, D), E3 (E, F), con E3 $(0,1)$ (E3 massimo 1).

La chiave di R è e (ogni istanza di E3 compare in una sola tripla). Due traduzioni corrette:

E1(*a, b)   E2(*c, d)   E3(*e, f)
R(*e, a, c, x)          FK e -> E3(e); FK a -> E1(a); FK c -> E2(c)         -- tabella a parte, niente NULL

oppure con fusione in E3: E3(*e, f, a, c, x), con a, c, x NULL per le istanze di E3 che non partecipano. Il corso mostra entrambe; la prima non ha NULL, la seconda è più compatta e va bene se quasi tutte le istanze di E3 partecipano.

Caso 9: relazione molti-a-molti con attributo, e l'errore degli eventi ripetuti

ER: E1 (A) $(0,N)$ — R (C) — $(0,N)$ E2 (B).

E1(*a)   E2(*b)   R(*a, *b, c)     FK a -> E1(a); FK b -> E2(b)

Errore (segnalato dal corso): voler inserire in R due righe con la stessa coppia $(a_1,b_1)$ e valori diversi di C ($x$ e poi $z$) viola la chiave primaria. Aggiungere un ID, R(*id, a, b, c), "funziona" ma R non è più una relazione: è un'entità, e quindi lo schema concettuale era sbagliato. Se i legami si ripetono davvero, va rivisto l'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 →: eventi ripetuti).

Caso 10: catena di relazioni con attributo

ER: Insegnante (CF, Età) $(0,N)$ — Lavora (Data) — $(0,N)$ Laurea (Codice, Nome), con Laurea $(1,1)$ — Appartiene — $(0,N)$ Università (Nome).

Insegnante(*cf, eta)
Universita(*nome)
Laurea(*codice, nome, universita)       FK universita -> Universita(nome)       -- Appartiene (1,1) fusa
Lavora(*cf, *laurea, data)              FK cf -> Insegnante(cf); FK laurea -> Laurea(codice)

Lavora è molti-a-molti con attributo Data: chiave (cf, laurea). Appartiene è uno-a-molti obbligatoria, fusa in Laurea.

Caso 11: relazione ricorsiva ternaria (grafo diretto con archi tipizzati)

ER: Insegnante (CF, Età), Corso (Codice, Nome, CFU); relazione Confronta tra Insegnante con ruolo Migliore, Insegnante con ruolo Peggiore e Corso, tutti $(0,N)$.

Insegnante(*cf, eta)
Corso(*codice, nome, cfu)
Confronta(*migliore, *peggiore, *corso)
          FK migliore -> Insegnante(cf); FK peggiore -> Insegnante(cf); FK corso -> Corso(codice)

Le due chiavi esterne verso Insegnante sono diverse (ruoli diversi). La chiave comprende tutte e tre le colonne: è un multigrafo orientato (tra due insegnanti ci possono essere più archi, uno per corso); un'istanza $(m_3,m_4,x)$ senza il corso sarebbe sbagliata, perché non si possono saltare le etichette. Vedi 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 →.

Caso 12: schema con più relazioni (impiegati, dipartimenti, progetti, città)

ER (in sintesi): Impiegato (CF, Nome, Cognome); Dipartimento (Nome, Telefono); Progetto (Nome, Budget); Città (Nome, Regione). Relazioni: Dirige tra Impiegato $(0,1)$ e Dipartimento $(1,1)$; Appartiene tra Impiegato $(0,1)$ e Dipartimento $(0,N)$, con attributo Data; Sede tra Dipartimento $(1,1)$ e Città $(0,N)$; Partecipa tra Impiegato $(0,N)$ e Progetto $(0,N)$; Svolto tra Progetto $(1,1)$ e Città $(0,N)$; PartDi, ricorsiva su Progetto con ruoli Sub $(0,1)$ e Sup $(0,N)$.

Schema relazionale del corso (con le domande a margine):

Impiegato(*cf, nome, cognome, dirige?, appartiene?, data?)    FK dirige, appartiene -> Dipartimento(nome)
Dipartimento(*nome, telefono, citta)                          FK citta -> Citta(nome)
Citta(*nome, regione)
Partecipa(*cf, *progetto)                                     FK cf -> Impiegato(cf); FK progetto -> Progetto(nome)
Progetto(*nome, budget, sup?, citta)                          FK sup -> Progetto(nome); FK citta -> Citta(nome)

Punti di attenzione:

• Dirige e Appartiene portano due chiavi esterne separate verso Dipartimento (due ruoli diversi). Il corso chiede: quale delle due colonne ha più NULL sistematici? Dirige: solo pochi impiegati dirigono un dipartimento, quindi dirige è quasi sempre NULL. Poiché Dipartimento partecipa a Dirige con $(1,1)$, la traduzione alternativa e senza NULL è mettere la chiave dell'impiegato nel dipartimento (direttore), il lato obbligatorio.
• Partecipa: molti-a-molti, relazione a parte con le due chiavi.
• Sede e Svolto (lato (1,1)): fuse in Dipartimento e Progetto con citta NOT NULL.
• PartDi: ricorsiva con Sub $(0,1)$ → struttura ad albero: chiave esterna sup in Progetto (NULL per i progetti di primo livello).

Verifica con SQLite

Provati con SQLite i casi 1 (variante a parte: un secondo inserimento dello stesso badge in Gioca è rifiutato dalla chiave), 3 (un profilo di un utente inesistente è rifiutato), 7 (albero a cinque nodi: i figli di n3 sono n4 e n5), 9 (la seconda riga con la stessa coppia è rifiutata) e 11 (due archi tra gli stessi insegnanti, per corsi diversi, sono accettati). Gli altri casi sono applicazioni della stessa regola.

Domande d'esame

Una relazione uno-a-molti con partecipazione opzionale del lato uno: fusione o tabella a parte? Traccia. La fusione dà NULL nelle colonne chiave esterna e negli attributi della relazione per le istanze non partecipanti. Se i NULL sarebbero sistematici (pochi partecipano), tabella a parte con chiave la sola chiave del lato con massimo 1.

Come si traduce una relazione ricorsiva Arco con Sorgente (0,N) e Destinazione (0,1)? Traccia. Albero: chiave esterna sul nodo con massimo 1 (il figlio), che contiene il padre: Nodo(id, ..., sorgente). Scrivere la colonna destinazione direbbe il contrario.