Il modello Relazionale è un modello logico di dati la cui architettura è suddivisa in tre livelli nel modo seguente:
Livello concettuale:
è denominato database logico ed è costituito dalla rappresentazione astratta del database, in quanto indipendente dalla implementazione fisica. Questo livello si pone tra il livello interno e quello esterno.
Livello interno:
viene detto database fisico ed è costituito dalla implementazione del database logico e considera i tipi di dato, i formati, le strutture di memorizzazione ed i metodi di accesso, esso rappresenta la forma in cui il database viene memorizzato e richiamato.
Livello esterno:
concerne le viste, intese come porzioni del Database logico, che gli utenti hanno sul database.
Dati n insiemi D1,D2,...,Dn chiamati domini della relazione, il prodotto cartesiano di D1,D2,...,Dn indicato con D1 x D2 x...x Dn è costituito dall'insieme di n-uple (a1,a2,...,an), tali che, per ogni 1<=i<=n ai appartiene a Di. Una relazione matematica sui domini D1,D2,..,Dn è un sottoinsieme del prodotto cartesiano D1 x D2 x...x Dn dove n è il grado della relazione.
Ad una relazione può essere associata una rappresentazione tabellare.
Ogni relazione (tabella) ha tante righe quanti sono i suoi elementi. Poiché una relazione matematica è un insieme, in una relazione non ci sono mai due n-uple uguali. Ciascuna n-upla contiene dati logicamente collegati tra loro o stabilisce un legame logico fra essi. All'interno di ciascuna relazione non è definito alcun ordinamento fra n-uple, due relazioni con le stesse n-uple in ordine diverso rappresentano la stessa relazione. Ogni relazione ha un numero di domini pari al grado della relazione stessa ed è significativo il loro ordine, in quanto rappresenta l’identificazione del dominio stesso. I valori appartenenti a ciascun dominio sono omogenei tra loro.
A differenza delle relazioni matematiche, nel Modello Relazionale, data una relazione sui domini D1,D2,...,Dn si associa in maniera univoca a ciascun Di un identificatore, chiamato attributo. Quindi, nel modello relazionale, l'ordinamento dei domini non risulta essere significativo in quanto la loro identificazione può avvenire per mezzo degli attributi.
Il concetto di restrizione di t-upla è così definito: Sia data una n-upla t, definita sull'insieme di attributi X, e sia Y sottoinsieme di X, la restrizione di t sull'insieme di attributi Y denotata da t.Y, e` la n-upla ottenuta da t eliminando i valori degli attributi non in Y.
Ricordiamo che, dalla teoria degli insiemi, ogni insieme è allo stesso tempo soprainsieme e sottoinsieme di se stesso, questo implica una sostanziale identità tra la n-upla e la t-upla.
La caratteristica delle relazioni utilizzate per strutturare i dati nelle applicazioni informatiche è quella di poter variare nel tempo. Alcune t-uple vengono aggiunte, eliminate o modificate. Gli insiemi degli attributi definiti nelle relazioni è invece invariante nel tempo. L'insieme degli attributi di una relazione è chiamato schema di relazione.
Il nome della relazione ed i nomi degli attributi sono costrutti che descrivono la struttura per mezzo della quale sono organizzati logicamente i dati e vengono definiti schema di relazione o intenzione, mentre l’insieme delle t-uple costituisce l'istanza o la sua estensione.
Uno schema di basi di dati relazionale è quindi un insieme di schemi di relazione ed una base di dati relazionale è l'insieme delle t-uple di ciascuna relazione.
I concetti di base e le relative notazioni utilizzate per la definizione del modello logico di un database, sono essenzialmente quelli di: dominio, t-upla, relazione e database come di seguito definiti (da Yang).
Dominio:
L'universo di un database relazionale è denotato da U ed è costituito da un insieme finito non vuoto di A1...An definiti attributi, si ha quindi U={A1,...,An}. Il dominio di un attributo Aj per j=1,...,n è l'insieme finito dei valori di Aj.
Tupla:
Sia X un sottoinsieme non vuoto dell'universo U, sia DOM(X) il dominio di X, sia f:X->DOM(X) una funzione tale che f = {(Ai1, a1),...,(Aik,ak)}. Ciascun Aij per 1<=j<=k è un attributo in X ed un argomento di f. Ciascun aj per 1<=j<=k è un valore in DOM(Aij), ed il valore di f per Aij, o l'immagine di Aij secondo f come (Aij) = aj. Questa funzione 1-pla f viene definita t-upla su X. Considerando f come un elemento del prodotto complesso di DOM(Ai1),...,DOM(Aik), questo prodotto complesso è costituito da tutte le t-uple possibili su X ed è definito TUP(X).
Relazione:
Sia Uj un sottoinsieme non vuoto dell'universo U. Una relazione Rj su Uj, indicata Rj(Uj), di un database relazionale viene definita su TUP(Uj) se è un insieme di t-uple aventi schema Uj. L'insieme Uj è definito schema per la relazione Rj.
Database:
Un database relazionale è un insieme di relazioni R1,...,Rm tale che Rj è una relazione su Uj per 1<=j<=m. L'insieme degli schemi U1,...,Um per le relazioni R1,...,Rm rispettivamente tali che l'unione di U1,...,Um sia uguale a U è lo schema del database.
Le dipendenze fra dati sono delle limitazioni imposte ai dati di un database.
Come l'insieme degli attributi, l'insieme delle dipendenze fra dati costituisce una parte essenziale di uno schema di relazione o di uno schema di database. Una classe importante di dipendenze fra dati è quella delle dipendenze funzionali.
Viene così definita:
Siano U l'insieme universale degli attributi e Uj un sottoinsieme di U. Una dipendenza funzionale (FD) è una limitazione su Uj ed è della forma X->Y, dove X ed Y sono sottoinsiemi di Uj. Si dice che la relazione r(Uj) soddisfa la FD X->Y, o che X->Y vale in r(Uj) se per ciascuna coppia di t-uple di r(Uj) si ha che ogni volta che i loro X-valori sono uguali lo sono anche i loro Y-valori. Quando X->Y vale in r(Uj), diciamo che X determina funzionalmente Y in r(Uj), oppure che Y è funzionalmente dipendente da X in r(Uj).
La chiave è un caso particolare di dipendenza funzionale che permette di identificare univocamente le t-uple delle relazioni.
Tutte le relazioni hanno almeno una chiave la cui esistenza garantisce la possibilità di accedere a tutti i dati del database, in quanto, nel modello relazionale, è possibile accedere ai dati solo attraverso i loro valori, l'esistenza delle chiavi permette di individuare ciascun dato attraverso i seguenti elementi:
1. nome della relazione;
2. nome dell'attributo;
3. valore della chiave.
La chiave è cosi formalmente definita:
Sia U l'universo degli attributi, sia Uj un sottoinsieme non vuoto di U ed uno schema di relazione, sia K un sottoinsieme non vuoto di Uj. L`insieme K degli attributi è una chiave candidata per lo schema di relazione Uj se gode delle seguenti proprietà invarianti nel tempo:
1. Una relazione avente schema Uj non ha lo stesso K-valore per qualsiasi coppia di t-uple distinte nella relazione.
2. Se da K viene cancellato un qualsiasi attributo viene a mancare la precedente proprietà.
Ad ogni relazione è associato un insieme di chiavi candidate, fra le quali viene scelta una chiave, detta chiave primaria, per la relazione Uj, il rapporto fra K ed Uj e` una funzione da TUP(K) a TUP(Uj) che costituisce una dipendenza importante, detta dipendenza di chiave.
Una chiave primaria di una relazione viene detta semplice se costituita da un solo attributo e viene detta composta negli altri casi. Per un dato database, un dominio su cui sia definita una chiave primaria semplice viene detto dominio primario di tale database. Si noti che non tutti gli attributi di una chiave primaria composta debbono essere definiti su domini primari, anche se una chiave primaria semplice deve essere definita su un dominio primario. Tutti gli inserimenti, gli aggiornamenti e le cancellazioni riguardanti le relazioni di base sono limitate dalle seguenti regole, note come insert-update-delete-rules (Codd):
1. Una chiave primaria per una relazione di base non può avere un componente nullo.
2. Se un attributo A di una chiave composta per una relazione Rj viene definito su di un dominio primario, allora deve sempre esistere una relazione di base Rk avente una chiave primaria semplice B tale che ciascun A-valore in Rj sia presente come B-valore in Rk.
Poiché chiavi e soprachiavi comprendono dipendenze funzionali, uno schema di relazione non è determinato soltanto da un insieme U di attributi, ma anche da un insieme S di dipendenze funzionali su U. Pertanto uno schema di relazione si rappresenta mediante la coppia ordinata di U e S, ossia R=(U,S).
La soprachiave è così formalmente definita:
Sia R=(U,S) uno schema di relazione. Un sottoinsieme X di U si dice soprachiave per uno schema di relazione R se X->U è in S. Se X è una chiave per R, allora è anche chiave per una relazione avente schema R. Una chiave per uno schema di relazione R ed una chiave per una relazione r(R) possono essere utilizzate scambievolmente, ed una soprachiave deve contenere una chiave.
Se una relazione r avente come schema R=(U,S) è denotata da un ampio insieme U ed ha U come sua unica chiave, nota come chiave globale per r(R), allora il recupero di una t-upla in r(R) non è efficiente, poiché tale recupero necessita della massima quantità possibile di informazioni che possono essere fornite da un valore di chiave globale. In tal caso è utile aggiungere un attributo addizionale ad U ed utilizzare questo singolo attributo come chiave.
Il problema di trovare la chiave di dimensione minima per uno schema di relazione è NP-completo (Lucchesi-Osborn) pertanto trovare tutte le chiavi di uno schema di relazione è in genere un problema che presenta una notevole difficoltà di soluzione.
Ricordiamo che, nella teoria della complessità computazionale, un problema si definisce NP-completo quando può essere risolto da un algoritmo non deterministico di complessità polinomiale (classe NP) e quando, dato un qualsiasi problema B in NP, esiste una riduzione polinomiale da A a B.
Una riduzione polinomiale da un problema A ad uno B è una funzione da A a B tale che: f e` calcolabile da un algoritmo deterministico in tempo polinomiale ed un elemento x appartiene ad A solo e soltanto se f(x) appartiene a B.
Poiché si può sempre ridurre un problema in NP ad uno NP-completo, questi ultimi sono considerati computazionalmente i più difficili all'interno della classe NP ed è ad oggi aperto il problema della loro solubilità, attualmente costituiscono il confine tra la trattabilità e la non trattabilità computazionale.
La scomposizione di una relazione in più sotto-relazioni viene detta normalizzazione. Tale normalizzazione si rende necessaria quando, analizzando la relazione si riscontrano anomalie o ridondanze cosi definite:
1. Ridondanza: quando un Y-valore funzionalmente dipende da un X-valore viene ripetuto in tutte le t-uple relative all'X-valore.
2. Anomalia di aggiornamento: variando un Y-valore in presenza di una ridondanza è necessario variare tutte le t-uple corrispondenti all'X-valore per mantenere la X->Y.
3. Anomalia di cancellazione: quando la cancellazione di una t-upla relativa ad una particolare categoria di dati comporta la indesiderata cancellazione di dati relativi ad altre categorie.
4. Anomalia di inserimento: quando un dato non può essere inserito per le sole categorie di interesse.
Tali anomalie e ridondanze, che possono comportare l'inconsistenza o dispersività del database, non si presentano per quegli schemi di database che rispettano la 1st Normal Form (1NF) e la Boyce-Codd Normal Form (BCNF), (Codd "Recent Investigation in Relational Database Systems" 1974) come di seguito definite:
Uno schema di relazione R=Ai1...Aik è in 1NF se il dominio di ogni attributo Aij tale che 1<=j<=k è semplice. Uno schema di database è in 1NF se ogni suo schema di relazione è in 1NF.
Sia U l'universo di un database relazionale costituito da un insieme finito non vuoto di attributi A1...An e dato un insieme S di Functional Dependency (FD), uno schema di relazioni in 1NF R=(U,S) e` in BCNF se, per ogni FD non banale avente la forma X->A, X e` una soprachiave per R. Uno schema di database è in BCNF se ogni suo schema di relazione è in BCNF.
La BCNF inoltre comporta come interessante conseguenza la separazione in diverse relazioni di categorie di dati concettualmente omogenei.
Riassumiamo quanto presentato stabilendo una definizione formale del modello relazionale di database, (da Codd):
Sia Uj un sottoinsieme dell'universo U degli attributi, e sia Si un insieme di dipendenze fra dati su Uj per ciascun j, con 1<=J<=m ed U=U1...Um. Il modello relazionale di database è costituito da:
1. Un insieme di relazioni tabellari variabili nel tempo r1,...,rm aventi schemi invarianti nel tempo R1,...,Rm dove ciascun Rj=(Uj,Sj) con 1>=j>=m.
2. Un insieme di regole di inserimento e cancellazione.
3. Un sotto-linguaggio per la manipolazione di dati potente almeno quanto l'algebra relazionale.