FormularioBasi di Dati e Tecnologie Web: definizioni, teoremi e formule delle note, in ordine di capitolo

1. Basi di dati e progettazione

Basi di dati e DBMS - architettura ANSI-SPARC e indipendenza dei dati

Definizione (base di dati). Una base di dati (database, DB) è una collezione permanente, coerente e integrata di dati correlati, tenuta per lungo tempo (anche decenni), progettata per uno scopo preciso e per utenti ben identificati. Rappresenta alcuni aspetti del mondo reale, detto mini-mondo o universe of discourse. I dati sono fatti noti che si possono registrare e hanno un significato intrinseco.

Definizione (DBMS). Un sistema di gestione di basi di dati (database management system) è un software generico che permette di creare, gestire e aggiornare un DB. Tre attività:

• definizione: lo schema (tipi di dato, struttura, vincoli) è scritto nel catalogo di sistema come metadati;
• costruzione: memorizzazione dei dati veri e propri;
• manipolazione: interrogazioni (query) e aggiornamenti.

Definizione (livelli).

• Schema esterno (livello esterno): uno per ogni applicazione o gruppo di utenti, descrive solo i dati rilevanti per quella applicazione (una vista).
• Schema logico (livello logico): rappresentazione integrata dei dati, indipendente dalla loro rappresentazione fisica. È quello che si disegna con il modello relazionale.
• Schema interno (livello fisico): rappresentazione in strutture dati e unità di memorizzazione (file, pagine, indici).

Definizione (indipendenza fisica). Gli schemi logico ed esterno non dipendono dallo schema interno, che può cambiare senza modificarli.

Definizione (indipendenza logica). Lo schema esterno non dipende dallo schema logico: aggiunte e modifiche alle viste non richiedono cambiamenti al livello logico (e, viceversa, modifiche logiche si assorbono ridefinendo le viste).

Ciclo di vita di un sistema informativo e analisi dei requisiti

Definizione (requisiti). I requisiti sono l'insieme delle caratteristiche che un sistema deve avere per rispettare il suo scopo. Si distinguono in:

• funzionali: che cosa il sistema deve fare (esempio: stampare la fattura);
• non funzionali: il modo in cui deve farlo (esempio: stampare in meno di un minuto);
• altri vincoli: requisiti generali posti dagli stakeholder, spesso decisi in anticipo (esempio: usare Linux).

Definizione (progettazione di una base di dati). Obiettivo: definire lo schema logico e lo schema fisico (si pensi all'architettura ANSI/SPARC, Basi di dati e DBMS - architettura ANSI-SPARC e indipendenza dei datiUna base di dati (database, DB) è una collezione integrata e persistente di dati correlati che rappresenta un frammento di mondo reale (mini-mondo); un DBMS è il software generico che permette di definirla (schema, nel catalogo come metadati), costruirla e manipolarla (interrogazioni e aggiornamenti). Rispetto a una raccolta di file il DBMS riduce ridondanza e incoerenza, condivide i dati tra applicazioni con controllo della concorrenza (isolamento, atomicità), garantisce durabilità, sicurezza (autenticazione e autorizzazione) ed efficienza. L'architettura ANSI/SPARC ha tre livelli: schema esterno (una vista per applicazione), logico (rappresentazione integrata, indipendente dalla memorizzazione), interno (strutture fisiche); da qui l'indipendenza fisica (cambia l'interno senza toccare logico ed esterno) e logica (cambia il logico senza toccare le applicazioni). Attori: sviluppatori del DBMS, DBA, progettisti di basi di dati e di applicazioni, utenti parametrici e occasionali.Basi di dati e DBMS - architettura ANSI-SPARC e indipendenza dei dati →) di un DB secondo i risultati dell'analisi dei requisiti.

Definizione (modello dei dati). Un modello (di dati) è un insieme di strutture simboliche con regole di rappresentazione per descrivere un mini-mondo. La rappresentazione prodotta è lo schema.

2. Progettazione concettuale: il modello entità-relazione

Modello entità-relazione - entità, relazioni e attributi

Definizione (entità). Un'entità è una classe di oggetti del mondo reale (fatti, persone, cose) che esistono autonomamente e hanno proprietà comuni. Ha un nome univoco nello schema. Esempi: Studente, Veicolo, Corso, Dipartimento. Si costruisce con l'astrazione di classificazione.

Definizione (relazione). Una relazione (o associazione) rappresenta un legame tra due o più entità; il numero di entità coinvolte è il grado. Ha un nome univoco nello schema. Si costruisce con l'astrazione di associazione. Esempi: Esame tra Studente e Corso (grado 2, binaria); Ordine tra Fornitore, Prodotto e Reparto (grado 3, ternaria, in generale n-aria se il grado è maggiore di 2).

Definizione (attributo di entità). Un attributo di un'entità è una proprietà locale dell'entità, rilevante per l'applicazione: associa ad ogni istanza un valore di un insieme detto dominio. Si costruisce con l'astrazione di aggregazione. Nello schema il dominio è di norma omesso e riportato nel dizionario dei dati.

Definizione (attributo di relazione). Un attributo di una relazione $r$ modella una proprietà non di una sola entità, ma dell'associazione tra le entità; è una funzione totale dalle istanze di $r$ ai valori di un dominio.

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

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).

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à.

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

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.

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.

Generalizzazioni e identificatori nel modello ER

Definizione (IS-A). La relazione IS-A (di sottoinsieme) è definita tra due entità, superclasse e sottoclasse, e significa che ogni istanza della sottoclasse è anche istanza della superclasse. Esempio: Studente IS-A Persona.

Definizione (generalizzazione). Una generalizzazione è una superclasse estesa da più sottoclassi (più IS-A) secondo un unico criterio di classificazione. Esempio: Persona ⊃ {Femmina, Maschio} (criterio: sesso). La specializzazione è l'operazione inversa (dalla superclasse alle sottoclassi).

Definizione (identificatore). Un vincolo di identificazione per un'entità $e$ definisce un identificatore: un insieme di proprietà (attributi o relazioni) che identifica univocamente tutte le istanze di $e$. Non esistono due istanze diverse con gli stessi valori su tutte le proprietà dell'identificatore. Un'entità può avere più identificatori, ma almeno uno.

Definizione (entità debole). Un'entità debole non ha attributi chiave propri: è identificata dalla relazione con un'altra entità, in combinazione con un attributo (identificazione esterna). Ha sempre partecipazione totale (1,1) alla relazione che la identifica.

3. Progettazione logica e modello relazionale

Modello relazionale - relazioni, chiavi e vincoli

Definizione (tupla e relazione). Sia $X=\{A_1,\dots,A_n\}$ un insieme di attributi e $\mathrm{dom}$ la funzione che associa a ogni attributo il suo dominio. Una tupla su $X$ è una funzione $t$ che associa a ogni $A_i\in X$ un valore $t[A_i]\in\mathrm{dom}(A_i)$ (Funzioni - definizione, dominio e graficoUna funzione associa a ogni elemento del dominio un solo valore: dominio naturale, grafico, immagine, antimmagine e metodo grafico.Funzioni - definizione, dominio e grafico →). Una relazione su $X$ è un insieme di tuple su $X$.

Definizione (schema di relazione). Uno schema di relazione è un nome $R$ con un insieme di attributi, $R(A_1,\dots,A_n)$; due schemi coincidono se hanno lo stesso insieme di attributi con gli stessi domini. Un'istanza $r$ di $R$ è un insieme di tuple su $R$; la cardinalità $|r|$ è il numero di tuple. Un schema di base di dati è un insieme di schemi di relazione insieme ai vincoli di integrità (ne fanno parte integrante); un'istanza di base di dati è un insieme di istanze, una per schema, che rispetta tutti i vincoli. Si dicono corrette solo le istanze che rispettano tutti i vincoli.

Definizione (superchiave). Un insieme $K$ di attributi di $R$ è una superchiave se in ogni istanza $r$ non esistono due tuple diverse con gli stessi valori su $K$: $\forall t_1,t_2\in r,\ t_1\ne t_2\Rightarrow t_1[K]\ne t_2[K]$.

Definizione (chiave). Una chiave è una superchiave minimale: togliendo un attributo, non è più superchiave.

Definizione (integrità referenziale). Un vincolo di integrità referenziale tra un insieme di attributi $X$ di una relazione $R_1$ e una relazione $R_2$ richiede che i valori di $X$ in $R_1$ compaiano come valori della chiave primaria di $R_2$. $X$ è una chiave esterna (foreign key) di $R_1$ verso $R_2$.

Dipendenze funzionali e normalizzazione - BCNF e terza forma normale

Definizione (dipendenza funzionale, FD). Siano $X,Y$ insiemi di attributi di $R$. La dipendenza funzionale $X\to Y$ è un vincolo sulle istanze $r$ di $R$: $\forall t_1,t_2\in r:\ t_1[X]=t_2[X]\Rightarrow t_1[Y]=t_2[Y]$. Si dice che $X$ determina funzionalmente $Y$.

Definizione (1NF). Il dominio di ogni attributo contiene solo valori atomici (semplici, indivisibili) e il valore di ogni attributo di una tupla è un solo valore.

Definizione (2NF). $R$ è in 2NF se è in 1NF e ogni attributo non primo è in dipendenza completa da ogni chiave di $R$. Equivalente: nessun attributo non primo dipende da una parte di una chiave. Se ogni chiave ha un solo attributo, la 2NF è garantita.

Definizione (3NF). $R$ è in 3NF se è in 2NF e nessun attributo non primo è in dipendenza transitiva da una chiave. Intuitivamente: ogni FD con parte sinistra parte di una chiave o non chiave è un problema.

Definizione (BCNF). $R$ è in BCNF se per ogni FD non banale $X\to A$ di $R$, $X$ è una superchiave.

4. Algebra relazionale

Algebra relazionale - operatori di base e join

Definizione (compatibilità all'unione). Due relazioni sono compatibili all'unione se hanno lo stesso numero di attributi e ogni coppia di attributi ha stesso nome e stesso dominio.

Definizione (prodotto). Date $R_1(X_1,\dots,X_n)$ e $R_2(Y_1,\dots,Y_m)$, il prodotto $R_1\times R_2$ ha schema $(X_1,\dots,X_n,Y_1,\dots,Y_m)$, grado $n+m$ e cardinalità $|R_1|\cdot|R_2|$: ogni tupla del primo operando è concatenata a ogni tupla del secondo.

Definizione (rinomina). $\rho_{A_1,\dots,A_k\leftarrow B_1,\dots,B_k}(R)$ cambia i nomi degli attributi $B_i$ in $A_i$. Si modifica lo schema, non l'istanza: domini e valori restano.

Definizione (selezione). $\sigma_\varphi(R)$ ha lo stesso schema di $R$ e contiene il sottoinsieme delle tuple di $R$ che soddisfano la proposizione $\varphi$. La proposizione è:

• $A_i\ \theta\ A_j$, con $A_i,A_j$ attributi di $R$ sullo stesso dominio;
• $A_i\ \theta\ c$, con $c$ costante;
• dove $\theta\in\{<,>,=,\neq,\leq,\geq\}$;
• combinazione di proposizioni con $\wedge$, $\vee$, $\neg$.

Definizione (proiezione). $\pi_{A_1,\dots,A_k}(R)$ ha come schema un sottoinsieme degli attributi di $R$ e contiene le tuple di $R$ ristrette a quegli attributi. Il grado è $k$; la cardinalità è $\le|R|$: è minore se, dopo aver tolto colonne, alcune tuple diventano uguali e (essendo $R$ un insieme) i duplicati spariscono; è uguale a $|R|$ se gli attributi proiettati contengono una superchiave.

Definizione (theta-join). Date $R_1(X)$ e $R_2(Y)$ senza attributi omonimi e una proposizione $\varphi$ che confronta attributi di $R_1$ con attributi di $R_2$ (e costanti), $$R_1\bowtie_\varphi R_2=\sigma_\varphi(R_1\times R_2).$$ Grado $n+m$; cardinalità $0\le|R_1\bowtie_\varphi R_2|\le|R_1|\cdot|R_2|$ (detta anche selettività).

Definizione (join naturale). Siano $R_1(X,W)$ e $R_2(Y,Z)$ con $W=(W_1,\dots,W_m)$ e $Z=(Z_1,\dots,Z_m)$ gli attributi con lo stesso nome. Allora $$R_1\bowtie R_2=\pi_{X,W_1,\dots,W_m,Y}\big(R_1\bowtie_{W_1=Z_1\wedge\dots\wedge W_m=Z_m}R_2\big).$$

Algebra relazionale estesa - divisione, aggregazione e outer join

Definizione. Data $R(X)$ e funzioni $F_1,\dots,F_n$ sugli attributi di $R$ (attributi, costanti, espressioni aritmetiche), $$\pi_{F_1,\dots,F_n}(R)=\{(F_1(t),\dots,F_n(t))\mid t\in R\}.$$

Definizione (aggregazione). Data $R(X)$ e funzioni di aggregazione $f_1(A_i),\dots,f_n(A_j)$ con $A_i,A_j\in X$, $$\mathcal{F}_{f_1(A_i),\dots,f_n(A_j)}(R).$$ Il risultato è una relazione con $n$ attributi (uno per funzione) e esattamente una tupla: grado $n$, cardinalità 1.

Definizione (raggruppamento). Data $R(X)$, funzioni $f_1(A_i),\dots,f_n(A_j)$ e $m$ attributi di raggruppamento $A_1,\dots,A_m$, $$_{A_1,\dots,A_m}\mathcal{F}_{f_1(A_i),\dots,f_n(A_j)}(R).$$ Gli attributi prima di $\mathcal{F}$ sono quelli di raggruppamento. Il risultato ha grado $n+m$ e una tupla per ogni gruppo (cardinalità = numero di gruppi).

Definizione. Date $R(X,Y)$ e $S(Y)$, la divisione $R\div S$ ha schema $X$ e contiene le tuple $x$ tali che per ogni $y\in S$ la tupla $(x,y)$ appartiene a $R$: $$R\div S=\{x\mid\forall y\in S:\ (x,y)\in R\}=\pi_X(R)-\pi_X\big((\pi_X(R)\times S)-R\big).$$

5. SQL: definizione dei dati e interrogazioni

SQL - query nidificate, operatori insiemistici e viste

Definizione. Una vista è una tabella derivata da altre tabelle (di base o altre viste) per mezzo di una query. È una tabella virtuale: a differenza delle tabelle di base, le sue righe non sono memorizzate (nella forma classica); la query che la definisce viene eseguita ogni volta che la si usa.

6. SQL avanzato

SQL avanzato - indici, transazioni e trigger

Definizione. Un indice è una struttura dati ausiliaria che offre un metodo alternativo di accesso ai dati senza cambiare il loro layout fisico. È un file di record, ciascuno una coppia $(K,P)$: $K$ è la chiave dell'indice (il valore del campo indicizzato) e $P$ un puntatore al blocco o al record del file dei dati.

Definizione. Una transazione è una sequenza di operazioni da considerare atomica, corretta anche in presenza di concorrenza, e con effetti permanenti.