Basi di dati e sistemi informativi

Basi di dati

Definizioni

Per basi di dati si intende un sistema in grado di gestire dati in modo integrato e flessibile, limitando i rischi di ridondanza e incoerenza. Per DBMS (DB Management System) si intende un sistema software in grado di gestire collezioni di dati (DB) in modo affidabile e persistente. Per modello dei dati si intende un insieme di elementi utilizzati per organizzare e strutturare di dati di interesse.

Metodologia di progetto

Nell’ambito delle basi di dati, si è consolidata una metodologia di progetto, articolata in tre fasi principali:

• Progettazione concettuale: in cui si vuole rappresentare le specifiche informali in termini di una descrizione formale e completa. Il prodotto che ne viene fuori viene chiamato schema concettuale.
• Progettazione logica: questa fase consiste nella traduzione dello schema concettuale in termini del modello di rappresentazione dei dati. Il prodotto di questa fase viene detto schema logico e consente di descrivere i dati secondo una rappresentazione indipendente dai dettagli fisici.
• Progettazione fisica: in questa fase lo schema logico viene completato con la specifica dei parametri fisici di memorizzazione dei dati. Il prodotto di questa fase viene detto schema fisico e fa riferimento a modello fisico dei dati.

Progettazione concettuale

Lo schema concettuale

Lo schema concettuale è una rappresentazione di alto livello dei requisiti sui dati raccolti. Esso contiene una descrizione dettagliata dei dati, delle relazioni e dei vincoli, ma non contiene dettagli implementativi. Per poterlo definire, si usa il modello Entità-Relazioni (Entity-Relationship), composto da entità, attributi e relazioni.

Entità

Per Entità si intende una classe di oggetti della realtà di interesse distinguibili dagli altri. Una occorrenza è un oggetto dell’entità e viene rappresentata tramite un rettangolo. Per poter distinguere due o più occorrenze di una stessa entità, bisogna assumere l’esistenza di un vincolo di unicità sugli attributi. La chiave è un sottoinsieme di attributi di un’entità la cui combinazione di valori è univoca. La proprietà di unicità è un vincolo sullo schema dell’entità, pertanto vale sempre.

Attributi

Gli attributi descrivono le particolari proprietà dell’entità. Essi associano a ciascuna occorrenza un valore appartenente a un insieme, detto dominio. Quando per un attributo non è possibile determinare un valore, si usa il valore NULL. Gli attributi possono essere:

• Attributo Composto: è suddivisibile in parti più piccole. Ad esempio, l’attributo Indirizzo si può dividere in Via, Civico, CAP, Città, Stato.
• Attributo Multi-valore: può assumere più di un valore per ciascuna occorrenza. Es: Telefoni, titoli_di_studio, sedi.
• Attributo derivato: attributo che è possibile determinare a partire da altri attributi. Ad esempio, Età è derivabile da data di nascita.

Relazioni

Una relazione è un’associazione o legame logico esistente tra due o più entità. Si indica con un rombo. Per grado di una relazione si intende il numero di entità partecipanti. Un'entità può essere in relazione con sé stessa. In tal caso si utilizzano esplicitamente nomi di ruolo per chiarire la partecipazione.

Le relazioni possono avere dei vincoli e possono essere di due tipi:

• Cardinalità: specifica il numero di relazioni minime e massime a cui una occorrenza può partecipare. Si dividono in: 1:1 (uno a uno), 1:N (uno a molti) o M:N (molti a molti);
• Partecipazione: specifica se l’esistenza di una occorrenza dipende dal suo essere in relazione con un’altra. Ne esistono di due tipi:
  • Totale, in cui ogni occorrenza di entità partecipa alla relazione. La partecipazione totale viene indicata con una linea spessa.
  • Parziale, in cui una occorrenza di entità può anche non partecipare alla relazione.

Gerarchie ISA

La gerarchia ISA permette di indicare cosa rappresenti un’entità rispetto ad un'altra. Ad esempio, un liceale è uno studente. Questa gerarchia serve per avere una generalizzazione:

• Totale, in cui ogni occorrenza della classe padre è una occorrenza di almeno una delle figlie. In caso contrario si dice parziale;
• Esclusiva, in cui ogni occorrenza della classe padre è al più una sola occorrenza di una classe figlia. In caso contrario si dice sovrapposta.

Progettazione logica

La progettazione logica di basi di dati è una fase in cui si definiscono in dettaglio la struttura e il layout delle tabelle del DB, nonché le relazioni tra le tabelle.

Vediamo un po’ di definizioni:

• Schema o componente intensionale di una relazione R: rappresenta la struttura logica di base della relazione. Essa definisce i nomi degli attributi, i domini degli attributi e i vincoli di integrità che si applicano alla relazione nel suo insieme.
• Istanza o componente estensionale di R: rappresenta l'insieme effettivo di tuple (righe) presenti nella relazione in un dato momento.

Le tuple sono definite come un insieme, quindi non c’è un particolare ordinamento su di esse. Per questo motivo, i valori all’interno di una tupla devono essere definiti come “lista ordinata”.

Vincoli del modello

Nel modello esistono alcuni vincoli:

• Di dominio: i valori di ciascun attributo sono valori appartenenti al corrispondente dominio.
• Di chiave, in cui:
  • Per ogni relazione esiste un sottoinsieme, detto superchiave, di uno o più attributi di una tabella che può identificare in modo univoco ogni riga all'interno della tabella.
  • Esiste un insieme più restrittivo del precedente, detto chiave, che gode della proprietà di essere minimo (senza ridondanze).
  • Le chiavi che soddisfano entrambe le proprietà, si dicono chiavi candidate. Quella designata si dice chiave primaria.
• Integrità di entità: nessuna chiave primaria può assumere valore null.
• Integrità referenziale: viene espresso come vincolo di chiave esterna, e stabilisce una relazione tra due tabelle, in cui uno o più attributi di una tabella fa riferimento alla chiave primaria di un'altra tabella. Esso assicura che i valori nella colonna di riferimento esistano nella tabella di riferimento.

Mapping E-R relazionale

Il mapping E-R relazionale è la creazione di una relazione, per ogni entità, con attributi semplici della stessa entità, scegliendo come chiave primaria una delle chiavi dell’entità. In base all’entità abbiamo:

• Per le entità deboli, cioè quelle entità che hanno una chiave che dipende da una di un’altra relazione, bisogna:
  • Creare una relazione con gli attributi dell’entità e includere, come chiave esterna, la chiave primaria dell’entità “proprietaria”.
  • La chiave primaria della nuova relazione sarà la combinazione della chiave esterna più la chiave parziale.
• Per ogni associazione binaria 1:1, bisogna:
  • Identificare le entità partecipanti S e D;
  • Scegliere una entità S con partecipazione totale ed includere in essa, come chiave esterna, la PK di D. In S bisogna includere anche eventuali attributi dell’associazione.
• Per ogni associazione binaria 1:N, bisogna:
  • Identificare le entità partecipanti;
  • Scegliere l’entità S dal lato N ed includere in essa, come chiave esterna, la PK dell’altra. In S bisogna includere anche eventuali attributi dell’associazione.
• Per ogni associazione R di tipo M:N, bisogna:
  • Creare una nuova relazione R;
  • Includere le chiavi esterne delle entità partecipanti;
  • La loro combinazione formerà la PK di R;
  • Includere eventuali attributi di R.
• Per ogni attributo multivalore A, bisogna:
  • Creare una nuova relazione che include A e la chiave primaria della entità di partenza come chiave esterna.
  • La PK sarà la combinazione della chiave esterna e di A.
• Per ogni associazione con grado > 2, bisogna:
  • Creare una nuova relazione;
  • Includere come chiavi esterne le PK delle entità partecipanti nonché eventuali attributi dell’associazione.
  • La PK sarà la combinazione delle chiavi esterne.

Algebra relazionale

L’algebra relazionale è:

1. Un linguaggio procedurale: le operazioni vengono specificate descrivendo il procedimento da seguire.
2. Chiusa, cioè è possibile scrivere espressioni come sequenza di operazioni;
3. Costituita da un insieme di operatori definiti su relazioni che producono relazioni.

I principali operatori sono: selezione, proiezione, ridenominazione (unari) e join (binario). Esistono le operazioni tipiche dell’insiemistica: unione, intersezione, differenza e prodotto cartesiano.

Unione, intersezione, differenza

Si tratta di operazioni binarie dell’insiemistica e hanno senso su relazioni con tuple omogenee, ovvero attributi identici o almeno appartenenti al medesimo dominio. Le operazioni binarie sono:

• Unione: produce una relazione che include tutte le tuple presenti in R o in S o in entrambe.
• Intersezione: produce una relazione che include tutte le tuple presenti sia in R che in S.
• Differenza: produce una relazione che include tutte le tuple presenti in R, ma non in S.

Prodotto cartesiano

Il prodotto cartesiano è un’operazione binaria su insiemi, ma non richiede la compatibilità delle relazioni partecipanti. Osserviamo che:

• Il grado della relazione risultante è pari alla somma dei gradi delle due relazioni partecipanti;
• La cardinalità è pari al prodotto di quelle delle due relazioni partecipanti.

Il prodotto cartesiano combina tutte le tuple di R con quelle di S, per questo potrebbero essere unite tuple che non ha senso unire.

Join

L’operatore di join è utilizzato per combinare coppie di tuple, provenienti da relazioni collegate, in singole tuple. L’operazione è espressa come <> = (R × S) <>. In altre parole, viene applicata la selezione sul risultato del prodotto cartesiano. L’operatore join si dice:

• Theta join in caso di condizione generica.
• Equi join quando la condizione è un'uguaglianza.
• Completo se ciascuna tupla di ciascuna delle relazioni contribuisce ad almeno una tupla del risultato.
• Natural join se si limita a riportare una volta l’attributo di comparazione nella tabella risultante.
• Outer join se inserisce nella relazione risultante le tuple che contribuiscono al risultato, estesi con valori nulli nel caso in cui non ci siano controparti opportune. Si può distinguere in:
  • Left Outer Join: Include tutti i record della prima (sinistra) di due tabelle, anche se non sono presenti valori corrispondenti per i record della seconda tabella (destra).
  • Right Outer Join: Include tutti i record della seconda (destra) di due tabelle, anche se non sono presenti valori corrispondenti per i record della prima tabella (sinistra).
  • Full Outer Join.

Raffinamento dello schema e normalizzazione nei DB relazionali

Esistono metodi formali per assicurare la scelta di “buoni” schemi relazionali. Linee guida informali:

• Progettare lo schema in modo che:
  • Sia semplice descrivere il suo significato.
  • Non ci siano attributi di entità diverse del mondo reale in un solo schema di relazione.
• Ridurre la ridondanza per diminuire la “storage area” (la memoria) ed evitare le anomalie da aggiornamento:
• Ridurre il numero di valori null nelle tuple;
• Evitare le tuple spurie, cioè con informazioni non corrette (generate a seguito di un natural join).

Dipendenze funzionali

Una dipendenza funzionale è un vincolo tra due insiemi di attributi di una base di dati e dipende dalla semantica dello schema. Data uno schema relazionale R e due sottoinsiemi non vuoti di attributi X e Y → esiste una dipendenza funzionale (Y dipende da X) se per ogni istanza r di R, abbiamo che: se i valori su X coincidono, anche i valori su Y coincidono. È importante osservare che non vale la proprietà: →.

Sia F l’insieme delle FD su uno schema R. Esso è minimo se:

• Ogni FD ha un solo attributo alla sua destra;
• Non è possibile rimuovere alcuna FD da F ed avere ancora un insieme equivalente ad F;
• La parte sinistra di ogni FD è minima.

Chiamiamo F⁺, chiusura di F, l’insieme delle FD implicate da F. Esistono delle regole per determinare le FD, detti assiomi di Armstrong:

• Riflessività
• Incremento
• Transitività
• Unione
• Decomposizione

Seguendo queste regole otterremmo sicuramente schemi privi di ridondanza. Purtroppo, il calcolo della chiusura è pesante e in genere va accettata una certa quantità di ridondanza per motivi di efficienza.

Forme normali

Le forme normali sono un metodo formale per analizzare le relazioni. Essa consente una decomposizione di relazioni in schemi che godono di migliori proprietà. Esistono 4 forme normali:

Decomposizione senza perdite

In una decomposizione dovremmo avere:

• La decomposizione senza perdita, che garantisce la ricostruzione delle informazioni originarie.
• La conservazione delle dipendenze, in cui:
  • Bisogna garantire il mantenimento dei vincoli di integrità originari.
  • Ciascuna delle dipendenze funzionali dello schema originario coinvolge attributi che compaiono tutti insieme in uno degli schemi decomposti.
  • Le relazioni decomposte hanno le stesse capacità di R di rappresentare i vincoli di integrità e rilevare aggiornamenti non consentiti.
  • Esiste un algoritmo che garantisce il lossless join e la conservazione delle dipendenze con decomposizione in 3NF (non in BCNF).

SQL come DDL

SQL DDL (Data Definition Language) consente di definire lo schema: tabelle, vincoli, domini, viste, ecc.

Domini elementari