Teoria Informatica

1 Introduzione Database

Esempio concreto: il valore 100, da solo, è un dato. Se gli si associa un contesto (voto in decimi, euro, centimetri, …) diventa un’informazione.

2 I Database

1. Consistenza/coerenza (non esistono dati che si contraddicono).
2. Riservatezza/autenticazione (accesso ai dati consentito solo alle persone autorizzate).
3. Permanenza dei dati (operazioni di backup e ripristino che garantiscono la conservazione dei dati da fattori distruttivi che possono essere interni ed esterni).
4. Efficienza (utilizzo ottimale delle risorse e ottimizzazione delle tempistiche di uso del database).

Le 4 fasi di creazione di un database

La creazione di un database prevede 4 fasi in cui l’output finale di ogni fase è input della fase successiva:

1. Analisi dei requisiti: in questa fase il progettista analizza le richieste del committente.
2. Progettazione concettuale: in questa fase il progettista compie un lavoro di astrazione e generalizzazione dei concetti che formano la realtà in esame (la realtà in esame viene chiamata minimondo) e ha come risultato finale la creazione di uno schema grafico che rappresenta la realtà di cui si vogliono memorizzare i dati. Questo schema grafico si chiama modello concettuale. Generalmente alla fine di questa fase il progettista illustra il modello concettuale al committente. Il modello concettuale è indipendente dal tipo di database utilizzato.
3. Traduzione dal modello concettuale in modello logico: in questa fase il progettista traduce il modello concettuale in uno schema che adotta le strutture previste dal tipo di database utilizzato. Tale schema prende il nome di modello logico ed è il risultato finale di questa fase. Il modello logico è indipendente dall’implementazione fisica del database, ovvero dalle modalità con cui intendiamo memorizzare fisicamente i dati nei dispositivi di elaborazione.
4. Creazione del modello fisico: in questa fase il progettista si occupa della memorizzazione nelle memorie di massa dei dati. Si parla di implementazione fisica del database e ha come risultato la creazione dello schema fisico.

3 E-R — Modello Concettuale

Il modello concettuale che noi useremo è il modello E-R (Entity-Relationship). Entity sta per entità, relationship sta per relazione ma in realtà si parla spesso di associazione e di modello entità-associazione. Il modello E-R si basa su 4 costrutti:

1. Entità: l’entità è un’astrazione che rappresenta una categoria di oggetti della realtà che hanno caratteristiche comuni (attributi). Essa ha un nome (inizia con la lettera maiuscola ed è un nome singolare) e ha un’esistenza autonoma.
2. Attributo: caratteristica dell’entità. Un attributo è caratterizzato da:
   2a) nome
   2b) tipo (numerico, stringa, data/ora)
   2c) dimensione (numero di caratteri o cifre)
   2d) opzionalità (ovvero se è necessario o meno che l’attributo abbia un valore).
3. Associazione: il legame logico tra entità. L’associazione ha un nome e può avere attributi.
4. Identificatore: l’attributo (o l’insieme degli attributi) che identifica univocamente un’istanza dell’entità.

Esempi di entità: studente, classe, docente, auto, libro…

Convenzioni grafiche

• L’entità si indica con un rettangolo al cui interno vi è il nome dell’entità.
• L’associazione tra due entità si indica con un rombo al cui interno vi è il nome dell’associazione, collegato alle entità che lega tramite segmenti.
• Un attributo di un’entità si indica mediante un segmento che ha inizio dal rettangolo che rappresenta l’entità e che termina con un pallino e con il nome dell’attributo.
• L’attributo (o l’insieme degli attributi) che identifica univocamente un’istanza dell’entità si chiama identificatore e graficamente viene identificato con un pallino pieno.
• Se l’identificatore è formato da più attributi (identificatore composto), i componenti hanno pallino vuoto, sono collegati da una barra orizzontale e all’estremità della barra si trova un unico pallino pieno (es. Presidente: Nome + Cognome).
• Per le entità deboli, l’identificatore è rappresentato con un pallino pieno collegato all’associazione identificante mediante un segmento: esso è composto dall’identificatore dell’entità forte collegata e da uno o più attributi dell’entità debole (la chiave parziale).

Entità deboli

Generalizzazione e specializzazione

Quando un’entità presenta uno o più attributi che sono valorizzabili solo in un sottoinsieme proprio delle istanze dell’entità, è preferibile considerare una sottoentità che contenga solo le istanze valorizzabili. In questo caso si parla di generalizzazione (o entità padre) e specializzazione (o entità figlia).

Le entità figlie ereditano tutti gli attributi dell’entità padre (compreso l’identificatore) e le relative associazioni, ma hanno attributi propri e possono avere associazioni proprie.

Altro esempio di generalizzazione:

Associazione ricorsiva

L’associazione ricorsiva è un’associazione tra istanze della stessa entità e si usa generalmente quando c’è una gerarchia.

Associazioni binarie, ternarie e n-arie

Un’associazione si dice binaria se collega logicamente due entità. Un’associazione si dice ternaria se lega logicamente tre entità. In generale un’associazione si dice n-aria se collega n entità. Per semplicità didattica, nei diagrammi ternari di questo manuale omettiamo le cardinalità: la traduzione nel modello logico avviene comunque con una nuova tabella come per le n:n.

Esempio di associazione binaria:

Cardinalità delle associazioni binarie

Le cardinalità di un’associazione binaria sono due coppie, ognuna delle quali legata a un’entità (la prima coppia indica il numero minimo ed il numero massimo di istanze della seconda entità legate a un’istanza della prima entità ed è posta accanto alla prima entità; la seconda coppia indica il numero minimo ed il numero massimo di istanze della prima entità legate a un’istanza della seconda entità ed è posta accanto alla seconda entità).

In riferimento alle cardinalità le associazioni possono essere:

1) Uno a uno (si scrive 1:1)

In questo tipo di associazione ogni istanza della prima entità è legata al più a un’istanza della seconda entità.

Altro esempio:

2) Uno a molti (si scrive 1:n)

In questo tipo di associazione ogni istanza della prima entità è collegata al più a un’istanza della seconda entità ed esiste almeno un’istanza della seconda entità che è collegata a più istanze della prima entità.

3) Molti a molti (si scrive n:n)

Un’associazione molti a molti è un’associazione in cui esiste almeno un’istanza della prima entità collegata a più istanze della seconda entità e viceversa.

Attributi composti e multivalore

In generale la cardinalità di un attributo è la coppia di numeri che indicano il numero minimo e massimo di valori che l’attributo può avere. Nel caso di un attributo non multivalore (un attributo che non è multivalore si chiama attributo singolo) la cardinalità è sottintesa e può essere non indicata.

Il dominio

4 Il Modello Logico

Il modello logico è uno schema, non grafico, che rappresenta un database utilizzando le strutture previste dal tipo di database utilizzato. Noi utilizziamo il database relazionale, ideato dal signore E. F. Codd (ricercatore IBM) nel 1970 (54 anni fa) e basato sul concetto matematico di relazione. Parliamo in questo caso di modello logico relazionale.

Le relazioni spesso vengono scritte in forma tabellare.

Un attributo di una relazione scritta in forma tabellare è l’intestazione di una colonna. In una tabella che rappresenta una relazione l’ordine delle colonne e delle righe non ha importanza; i valori all’interno di una colonna sono tutti dello stesso tipo e non ci sono due righe della tabella uguali.

Chiave esterna

Nell’esempio sotto, nomeClasse nella tabella Studente è una chiave esterna perché fa riferimento alla chiave primaria nomeClasse della tabella Classe.

Osserviamo che i valori della chiave primaria non possono ripetersi all’interno di una tabella. I valori della chiave esterna possono ripetersi ma, a differenza dell’esempio (la classe 3T non è presente nella tabella Classe), non dovrebbero esserci valori della chiave esterna che non sono presenti tra i valori della chiave primaria della tabella collegata.

Per evitare questo problema si pone un vincolo per cui non è possibile inserire una riga che presenta un valore della chiave esterna che non è presente tra i valori della chiave primaria della tabella collegata. Questo vincolo si chiama vincolo di integrità referenziale.

La tabella che contiene la chiave esterna viene chiamata tabella referenziante (detta anche tabella referenziale o slave): è quella che «punta» verso l’altra. La tabella la cui chiave primaria è usata dalla FK viene chiamata tabella referenziata (o master).

Vincoli

Esistono due tipi di vincolo:

• Vincolo interrelazionale (vincolo che riguarda più tabelle; esempio: vincolo di integrità referenziale);
• Vincolo intrarelazionale (vincolo che riguarda solo una tabella). Il vincolo intrarelazionale può essere di due tipi:
  • Vincolo di dominio (vincolo che riguarda un solo attributo);
  • Vincolo di tupla (vincolo che riguarda 2 o più attributi).

Osserviamo che la tabella presenta:

Il vincolo di dominio NumeroEsame>0 AND NumeroEsame<31 eviterebbe l’errore sul NumeroEsame (il vincolo di dominio riguarda un attributo: NUMEROESAME).

Il vincolo di dominio Voto>=18 AND Voto<=30 eviterebbe l’Errore 2 (Voto: 32). Il vincolo di tupla Lode="No" OR Voto=30 (cioè: se Lode è “Sì” allora Voto deve essere 30) eviterebbe l’Errore 3 (il vincolo di tupla riguarda gli attributi VOTO e LODE).

Notazione del modello logico relazionale

Nel modello logico relazionale le tabelle vengono scritte nella forma:

Esame (IdEsame(PK), data, voto, lode, numeroEsame, Matricola(FK))

dove si indica con PK la chiave primaria (anche composta, es. PK(Matricola, IdEsame)) e con FK la chiave esterna. Questa notazione è usata in tutto il manuale, nella teoria e negli esercizi.

Procedimento di traduzione dal modello E-R al modello logico

La traduzione dal modello E-R al modello logico avviene in 3 passi ordinati. L’ordine è importante: prima si ristruttura (applicando la Regola 1), poi si traducono entità e associazioni (applicando la Regola 2).

1. Passo 1 — Ristrutturazione (Regola 1): si eliminano i costrutti che il modello logico non rappresenta: attributo composto, attributo multivalore, generalizzazione. Si ottiene il modello E-R ristrutturato.
2. Passo 2 — Traduzione delle entità: ogni entità del modello ristrutturato diventa una tabella con i propri attributi e il proprio identificatore come chiave primaria (PK). L’entità debole usa come PK la coppia PK dell’entità forte + chiave parziale (la chiave parziale è l’attributo dell’entità debole che, unito alla chiave primaria dell’entità forte, forma la chiave primaria dell’entità debole).
3. Passo 3 — Traduzione delle associazioni (Regola 2): nel modello logico non esiste il rombo: ogni associazione va tradotta in tabelle e chiavi.
   • 1:n: nel modello logico l’associazione viene rappresentata con una FK aggiunta nella tabella referenziante, cioè quella dal lato con massimo 1 (es. Studente (1,1) → FK nomeClasse in Studente). Gli eventuali attributi dell’associazione vengono rappresentati nella stessa tabella, accanto alla FK.
   • n:n: nel modello logico l’associazione viene rappresentata con una nuova tabella col nome dell’associazione, con PK formata dalla coppia delle PK delle due entità (che sono anche due FK) più gli eventuali attributi dell’associazione.
   • Ternaria: nel modello logico l’associazione viene rappresentata con una nuova tabella la cui PK è la terna delle PK delle tre entità, più gli attributi dell’associazione.
   • 1:1: nel modello logico l’associazione viene rappresentata con fusione in un’unica tabella (solo se non crea molti valori nulli) oppure con una FK nella tabella con meno valori nulli (spesso con vincolo UNIQUE).
   • Ricorsiva: nel modello logico l’associazione viene rappresentata sdoppiando logicamente l’entità nei due ruoli e applicando il caso 1:n (con FK) o n:n (con nuova tabella) a seconda delle cardinalità.
   • Debole + identificante: nel modello logico l’associazione identificante viene rappresentata con la FK già contenuta nella PK composta della debole; non serve una tabella in più per l’associazione.

Regola 1 — Eliminazione dei costrutti del modello E-R non presenti nel modello logico

Costrutti da eliminare: attributo composto; attributo multivalore; generalizzazione.

Nell’applicare questa regola si ristruttura il modello E-R in modo tale da eliminare i costrutti non presenti nel modello logico (in questa fase generalmente si ottimizza pure il modello E-R per renderlo più efficiente in relazione allo spazio occupato dai dati, alla ridondanza dei dati e al tempo di accesso ai dati).

Eliminazione dell’attributo composto

Si elimina l’attributo composto sostituendolo con gli attributi atomici che lo compongono.

Eliminazione dell’attributo multivalore

Si sostituisce l’attributo multivalore con un’entità che è collegata all’entità che lo conteneva con un’associazione 1:n o n:n.

Eliminazione delle generalizzazioni

Per eliminare le generalizzazioni durante la creazione del modello E-R si possono seguire tre metodi alternativi. Non si sceglie a caso: prima leggi la copertura (t/p, e/s), poi guarda se le figlie hanno attributi o associazioni proprie, poi decidi cosa sei disposto ad accettare (valori nulli, tabelle in più, associazioni duplicate). In fondo a questa sezione c’è la tavola di scelta.

Metodo 1 — Eliminazione dell’entità padre: è possibile solo quando la copertura è totale (ogni istanza del padre sta in almeno una figlia: altrimenti quelle «solo padre» andrebbero perse). È preferibile quando la copertura è anche esclusiva (nessuna istanza in due figlie: altrimenti la ripeteresti) e quando le figlie hanno molti attributi propri. Le associazioni dell’entità padre vanno ripetute per ogni entità figlia. Svantaggio: schema più complesso; le interrogazioni «su tutti i padri» diventano un’unione delle tabelle figlie.

Metodo 2 — Eliminazione delle entità figlie: è sempre possibile. Sceglilo quando la copertura è parziale (esistono istanze solo-padre) e/o sovrapposta, oppure quando le figlie sono «povere»: pochi attributi specifici e nessuna associazione propria. Ha lo svantaggio di aumentare i dati nulli (gli attributi di una figlia restano vuoti sulle istanze delle altre) e il vantaggio di uno schema con una sola tabella; la consultazione però spesso si complica, perché le query devono distinguere i tipi e gestire i nulli. Aggiungi un attributo di controllo (es. razza, ruolo) che dica a quale figlia appartiene l’istanza.

Metodo 3 — Sostituire la generalizzazione con un’associazione 1:1 che lega entità padre ed entità figlia, per ogni entità figlia. È sempre possibile. Sceglilo quando le figlie hanno associazioni proprie che non vuoi mescolare sul padre (es. solo i medici seguono i ricoveri), oppure quando vuoi evitare sia i nulli del Metodo 2 sia la duplicazione delle associazioni del padre del Metodo 1. Funziona bene con copertura parziale (chi non è figlia resta solo nel padre) e con copertura sovrapposta (la stessa istanza può avere due 1:1). Svantaggio: più tabelle e più join per ricostruire una figlia completa.

Stesso metodo, con un’associazione che resta sul padre: Iscrizione verso CircoloSportivo non si sposta sulle figlie; dopo la ristrutturazione la generalizzazione è sostituita solo da Is_T e Is_C.

Regola 2 — Rappresentazione delle associazioni nel modello logico

Con questa regola stabiliamo i principi che ci permetteranno di rappresentare le associazioni nel modello logico. Ci sono tre casi:

Caso 1: Associazione 1:n

In un’associazione 1:n tra due entità si creano due tabelle (una per entità). L’associazione è rappresentata da una chiave esterna inserita nella tabella referenziante, cioè nella tabella corrispondente all’entità la cui cardinalità, posta accanto a tale entità, ha il massimo uguale a 1 verso l’altra entità. In pratica: la FK va nella tabella dal lato “molti” (quella con (1,1) o (0,1) accanto a sé).

Esempio (Studente (1,1) — Iscrizione — (1,n) Classe): accanto a Studente c’è (1,1), quindi ogni studente è collegato ad al massimo una classe → la FK nomeClasse va in Studente (tabella referenziante). Accanto a Classe c’è (1,n), quindi una classe può avere molti studenti → Classe è la tabella referenziata (contiene la PK nomeClasse). Se l’associazione ha attributi propri, vanno nella stessa tabella referenziante, accanto alla chiave esterna.

-- Il modello logico associato al modello E-R soprastante:
Studente (Matricola(PK), Nome, Cognome, nomeClasse(FK))
Classe   (nomeClasse(PK), numeroAula)

Caso 2: Associazioni n:n

In questo caso l’associazione è formata da una nuova tabella che ha per nome il nome dell’associazione, per chiave primaria l’attributo composto dalle 2 chiavi primarie delle 2 entità collegate e per attributi gli eventuali attributi dell’associazione.

Studente    (Matricola(PK), Nome, Cognome)
Esame       (IdEsame(PK), Nome)
Svolgimento (PK(Matricola, IdEsame), FK(Matricola), FK(IdEsame), voto, data)

Caso 3: Associazione 1:1

Nella traduzione da modello E-R a modello logico di un’associazione 1:1 si possono seguire diverse strategie:

Prima strategia: consiste nel considerare in luogo delle due entità un’unica entità che contiene gli attributi di entrambe (non è consigliabile quando questa scelta comporterebbe la presenza di attributi non valorizzabili).

-- usando la prima strategia (esempio con CodFiscale):
Persona (CodFiscale(PK), Nome, Cognome, Numero, DataScadenza)

Lo stesso schema, con identificatori diversi: Telefono per Persona e CF per Tessera Sanitaria.

-- prima strategia, identificatori Telefono e CF:
Persona (Telefono(PK), Nome, Cognome, CF, DataScadenza)

Seconda strategia: consiste nel rappresentare l’associazione con la chiave esterna. Si inserisce la chiave esterna nella tabella che presenta un numero minore di attributi non valorizzabili.

-- usando la strategia 2:
Stato      (Nome(PK), NumAbitanti)
Presidente (PK(Nome, Cognome), NomeStato(FK))

5 Esercizi — Dal modello E-R al modello logico

Regola 1 · Ristrutturazione del modello E-R  +  Regola 2 · Associazioni nel modello logico

Gli esercizi seguenti sono disposti in ordine di difficoltà crescente. Per ognuno sono forniti il testo, il modello E-R (disegnato seguendo le convenzioni grafiche del manuale: entità come rettangoli, associazioni come rombi, attributi con pallino, identificatore con pallino pieno, cardinalità come coppie), lo svolgimento commentato e la soluzione in notazione modello logico con PK per le chiavi primarie e FK per le chiavi esterne. Prova a risolvere l’esercizio prima di aprire la soluzione.

-- Passo 2: tabelle delle entità, senza FK da associazioni
Paziente (Codice(PK), Nome, Cognome)
Referto  (Numero(PK), Data)

-- Passo 1: nulla da ristrutturare; Passo 2: 2 tabelle; Passo 3: 1:n → FK in Referto
Paziente (Codice(PK), Nome, Cognome)
Referto  (Numero(PK), Data, codPaziente(FK))

-- Passo 2: senza FK da associazioni
Libro (ISBN(PK), Titolo)
Copia (Inventario(PK))

-- Passo 1: nulla da ristrutturare; Passo 3: 1:n → FK + attributo in Copia
Libro (ISBN(PK), Titolo)
Copia (Inventario(PK), Condizione, ISBN(FK))

-- Passo 2: senza tabella Guarda
Utente (IdUtente(PK), Username)
Film   (IdFilm(PK), Titolo)

-- Passo 3: n:n → nuova tabella con PK(IdUtente, IdFilm)
Utente (IdUtente(PK), Username)
Film   (IdFilm(PK), Titolo)
Guarda (PK(IdUtente, IdFilm), IdUtente(FK), IdFilm(FK), Data)

-- Passo 2: senza FK di Possiede
Dipendente (Matricola(PK), Nome, Cognome)
Telefono   (Numero(PK))

-- Passo 1: multivalore → entità Telefono + Possiede 1:n; Passo 3: 1:n → FK in Telefono
Dipendente (Matricola(PK), Nome, Cognome)
Telefono   (Numero(PK), matricola(FK))

-- Passo 2: senza FK di Rilascio
Persona (CodFiscale(PK), Nome, Cognome)
Patente (Numero(PK), DataScadenza)

-- Passo 3: 1:1 seconda strategia → FK in Patente (meno nulli)
Persona (CodFiscale(PK), Nome, Cognome)
Patente (Numero(PK), DataScadenza, codFiscale(FK))
-- in 1:1 la FK è anche UNIQUE; in alternativa può essere PK: Patente (codFiscale(PK, FK), Numero, DataScadenza)

-- Passo 2: senza FK di RiceveC/RiceveG
Cane         (CodiceC(PK), Nome, Razza, pesoMedio)
Gatto        (CodiceG(PK), Nome, Razza, coloreOcchi)
Vaccinazione (CodVaccinazione(PK), Nome)

-- Passo 1: Metodo 1 padre eliminato; Passo 3: 2x1:n → 2 FK in Vaccinazione
Cane         (CodiceC(PK), Nome, Razza, pesoMedio)
Gatto        (CodiceG(PK), Nome, Razza, coloreOcchi)
Vaccinazione (CodVaccinazione(PK), Nome, Data, CodiceC(FK), CodiceG(FK))
-- vincolo di tupla: esattamente una delle due FK è valorizzata:
-- (CodiceC IS NOT NULL AND CodiceG IS NULL) OR (CodiceC IS NULL AND CodiceG IS NOT NULL)

-- Passo 2: Via senza FK di Contiene (PK incompleta)
Città (CAP(PK), nome)
Via   (nome, lunghezza)

-- Passo 2: debole → PK(CAP, nome); Passo 3: Contiene già nella FK
Città      (CAP(PK), nome)
Via        (PK(CAP, nome), CAP(FK), lunghezza)

-- Passo 2: senza FK, senza Fornitura
Dipartimento (NomeDip(PK), Piano)
Prodotto     (IdProdotto(PK), Descrizione)
Venditore    (PIVA(PK), RagioneSociale)
Telefono     (Numero(PK))

-- Passo 1: telefono → Telefono + Possiede; Passo 3: ternaria → nuova tabella terna
Dipartimento (NomeDip(PK), Piano)
Prodotto     (IdProdotto(PK), Descrizione)
Venditore    (PIVA(PK), RagioneSociale)
Fornitura    (PK(NomeDip, IdProdotto, PIVA), NomeDip(FK), IdProdotto(FK), PIVA(FK), Quantita)
Telefono     (Numero(PK), nomeDip(FK))

-- Passo 2: senza FK, senza Sostiene
Studente (Matricola(PK), Nome, Cognome, Via, NumeroCivico, Citta)
Telefono (Numero(PK))
Docente  (IdDocente(PK), Nome)
Corso    (IdCorso(PK), Titolo)

-- Passo 1: composto → colonne, multivalore → Telefono; Passo 3: 1:n → FK, n:n → nuova tabella
Studente   (Matricola(PK), Nome, Cognome, Via, NumeroCivico, Citta)
Telefono   (Numero(PK), matricola(FK))
Docente    (IdDocente(PK), Nome)
Corso      (IdCorso(PK), Titolo, idDocente(FK))
Sostiene   (PK(Matricola, IdCorso), Matricola(FK), IdCorso(FK), Voto, Data)

-- Passo 2: senza FK di Effettua/Segue
Paziente  (CodSanitario(PK), Nome, Cognome, Via, NumeroCivico, Citta)
Personale (CF(PK), Nome, Cognome, Telefono, Ruolo, Specializzazione, Piano)
Ricovero  (NumRicovero, DataIngresso, DataDimissione)

-- Passo 1: composto → colonne, Metodo 2 con Ruolo; Passo 3: Effettua in PK, Segue → FK
Paziente  (CodSanitario(PK), Nome, Cognome, Via, NumeroCivico, Citta)
Personale (CF(PK), Nome, Cognome, Telefono, Ruolo, Specializzazione, Piano)
Ricovero  (PK(CodPaziente, NumRicovero), CodPaziente(FK), DataIngresso, DataDimissione, CFMedico(FK))