Relazioni ricorsive, cardinalità e vincoli di integrità nel modello ER

Entità, relazioni e attributi (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 →) descrivono la struttura dello schema. Questa nota aggiunge le regole che le istanze devono rispettare: i vincoli di integrità, di cui le cardinalità sono il tipo principale, e il caso speciale delle relazioni ricorsive.

Definizione (vincolo di integrità). Un vincolo di integrità è una regola espressa sullo schema (livello intensionale) che specifica una condizione da rispettare in ogni istanza (livello estensionale). In ER si hanno:

1. vincoli di cardinalità sulle relazioni;
2. vincoli di cardinalità sugli attributi;
3. vincoli di identificazione sulle entità (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 →);
4. altri vincoli, detti esterni (al diagramma).

Cardinalità delle relazioni

Definizione (cardinalità). Una cardinalità si riferisce a un ruolo $u$ di un'entità $e$ in una relazione $r$ ed esprime un estremo inferiore e un estremo superiore al numero di istanze di $r$ a cui ogni istanza di $e$ può partecipare con il ruolo $u$. Si scrive $(\min,\max)$ accanto all'entità.

Formalmente, per ogni istanza $e_i$ di $e$: $\min \le |\{\,r_k\in I(r)\;:\; r_k[u]=e_i\,\}| \le \max$.

I valori utili sono 0, 1, N:

• minimo 0: partecipazione opzionale; minimo 1: obbligatoria;
• massimo 1: l'istanza partecipa al più una volta; massimo N: molte volte (nessun limite).

I vincoli di cardinalità non permettono di violare la semantica estensionale: anche con Esame(Studente (0,N), Corso (0,N)) la coppia $(s_1,c_1)$ compare una volta sola. La cardinalità può solo restringere il numero di coppie distinte: con Studente (0,1) lo studente sostiene un solo esame in tutto, non uno per sessione.

Classificazione delle relazioni binarie

Dai massimi si ottiene il tipo (i minimi dicono solo se la partecipazione è obbligatoria):

Un errore classico è scambiare le cardinalità: "una persona lavora per una sola azienda, ma in un'azienda lavorano molte persone" si scrive Persona (0,1) o (1,1) lato lavora, Azienda (0,N) lato impiegati; scrivere Persona (0,N) e Azienda (0,1) dice il contrario (un'azienda ha al più una persona).

Come scegliere (procedura). Per ciascun lato della relazione chiedersi: (1) ogni istanza deve partecipare? → min 1 altrimenti 0; (2) può partecipare più di una volta? → max N altrimenti 1. Esempio: "Ogni ordine ha esattamente un cliente; un cliente può non aver ordinato nulla" → Ordine (1,1), Cliente (0,N).

Relazioni ternarie

La cardinalità di un'entità in una relazione ternaria conta le triple, non le coppie. Caveat: la partecipazione opzionale (0,N) in una ternaria non permette una tripla "incompleta" (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 →). Esempio: Ordine(Fornitore (1,N), Prodotto (1,N), Reparto (0,N)): ogni fornitore e ogni prodotto compaiono in almeno un ordine, un reparto può non aver mai ordinato.

Cardinalità degli attributi

Definizione (cardinalità di un attributo). Estremo inferiore e superiore al numero di valori associati a ogni istanza dell'entità (o della relazione).

• (0,1): attributo opzionale (può essere NULL).
• (1,N) o (0,N): attributo multivalore.
• Se non è indicata, la cardinalità è (1,1): obbligatorio e monovalore.

Esempio (Impiegato): Cognome (1,1); PatenteDiGuida (0,1); Laurea (1,N); Telefono (0,N). Estensionalmente un attributo semplice è $a: I(e)\to D$, un multivalore è $a: I(e)\to\mathcal P(D)$ (insieme delle parti, Insiemi e insieme delle partiCome si descrive un insieme, sottoinsiemi, uguaglianza, insieme delle parti e insiemi finiti e infiniti.Insiemi e insieme delle parti →), un opzionale è $a: I(e)\to D\cup\{\text{NULL}\}$. Gli attributi multivalore e composti si eliminano in fase di ristrutturazione (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 →).

Relazioni ricorsive

Definizione (relazione ricorsiva). Una relazione è ricorsiva quando la stessa entità partecipa più di una volta. In questo caso il ruolo di ogni partecipazione va indicato esplicitamente.

Esempio: Re e la relazione Successione, con ruoli Predecessore e Successore. Estensionalmente le istanze sono coppie etichettate $(\text{Predecessore}: k_1,\ \text{Successore}: k_2)$ ($(k_1,k_2)$ è diversa da $(k_2,k_1)$). Quando l'entità partecipa una volta sola, il ruolo coincide implicitamente con il nome dell'entità.

Quali strutture si ottengono con le cardinalità

Sia Nodo un'entità e Arco una relazione ricorsiva con ruoli Sorgente e Destinazione:

Con (1,1) su un ruolo un nodo deve partecipare: la catena $(k_4,\ ?)$ non si chiude, perché $k_4$ non avrebbe successore.

Quello che le cardinalità non dicono

• Cappi (un nodo collegato a se stesso, $(k_1,k_1)$) e cicli (nell'albero): servono vincoli esterni.
• Grafo non diretto: l'istanza $(k_1,k_2)$ e $(k_2,k_1)$ è lo stesso arco; per gestirlo serve un vincolo esterno (per esempio $k_1<k_2$ nell'ordine degli identificatori).
• Multigrafo (due archi diversi tra gli stessi nodi): la relazione binaria non lo rappresenta, perché la coppia è unica. Si usa una terza entità, l'etichetta, e una ternaria Arco(Sorgente: Nodo, Destinazione: Nodo, Etichetta): le istanze $(m_1,m_2,\text{verde})$ e $(m_1,m_2,\text{viola})$ sono distinte. Le etichette non si possono saltare, perché con cardinalità (0,N) servono per distinguere.
• Sostituire i due ruoli con due entità (RePredecessore e ReSuccessore collegate da Succ) non è equivalente: nella catena $k_1\to k_2\to k_3\to k_4$ i predecessori sono $\{k_1,k_2,k_3\}$ e i successori $\{k_2,k_3,k_4\}$, insiemi che si sovrappongono. Un'entità distinta per ruolo li considererebbe oggetti diversi, mentre $k_2$ è un solo re che ha il ruolo di successore di $k_1$ e di predecessore di $k_3$.

Per la struttura dati su cui poggia, vedi 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à → e 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 →.

Esempi tipici

• Social network: Utente segue Utente (Follower (0,N), Followed (0,N)); Commento risponde a Commento (Commento_Origine (0,N), Commento_Risposta (0,1)): è un albero di risposte, ogni commento risponde al più a un altro (Esercizio - Progettazione ER e schema relazionale del social network (esercizio social e laboratorio)).
• Tassonomia di prodotti: Categoria ha Supercategoria (0,1) e Sottocategorie (0,N).
• Percorsi: Città collegata a Città con Distanza come attributo di relazione.

Vincoli esterni

Definizione (vincolo esterno). Un vincolo che non si disegna con i costrutti del modello. Si scrive nella documentazione in notazione matematica o in linguaggio naturale non ambiguo.

Esempi: "un tavolo è servito da un solo cameriere" (vedi Esercizio - Progettazione ER e schema relazionale della pizzeria (tema d'esame 30 giugno 2025)); "se il tipo del conto è fattura, almeno uno tra codice fiscale e partita IVA è presente"; "ogni persona proviene dalla regione della città in cui è nata" (un ciclo di relazioni, 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 →).

Domande d'esame

1. Un'azienda ha molti impiegati e un impiegato lavora per una sola azienda. Scrivere le cardinalità. Traccia. Impiegato (1,1) o (0,1), Azienda (0,N) o (1,N): uno-a-molti. Il minimo dell'impiegato dipende dal fatto che esistano impiegati senza azienda; scambiare i lati significherebbe che l'azienda ha al più un impiegato.

2. Come si modella un grafo diretto di nodi con archi colorati, anche più archi tra gli stessi nodi? Traccia. Relazione ricorsiva Arco con ruoli Sorgente e Destinazione, tutti (0,N); per distinguere archi paralleli un'entità Colore e una ternaria Arco(Sorgente, Destinazione, Colore). Cappi e simmetria si vietano con vincoli esterni.

3. Che cosa implica la cardinalità (1,1) su entrambi i ruoli di una relazione ricorsiva Successione tra re? Traccia. Ogni re ha un predecessore e un successore: nessun primo né ultimo, quindi solo cicli o infinite istanze. Per una catena finita servono (0,1) su entrambi i ruoli.