Appunti completi corso Basi di dati

Sistemi aziendali e gestione delle informazioni

Un'azienda è composta da un sistema informatico, un sistema informativo e un sistema organizzativo. Il sistema informativo è l'insieme di risorse, strumenti e procedure per la gestione delle informazioni aziendali, mentre il sistema informatico è l'insieme degli strumenti hardware e software di un'azienda. Il sistema informatico è integrato in quello informativo che è all'interno di quello organizzativo.

Il dato è l'unica elementare grezza di informazione, mentre l'informazione è l'elaborazione dei dati per rispondere a esigenze specifiche. I processi sono invece le procedure aziendali per rispondere ad una necessità. La tecnologia dell'informazione può essere incentrata sui dati o sui processi. Nel nostro caso ovviamente saremo incentrati sui dati e la loro elaborazione.

Architettura del DBMS

L'architettura che ne consegue è che gli utenti si interfacciano ai processi che fanno uso dei dati, ma tra i processi e il database c'è un mediatore, il DBMS, cioè il Database Management System. Consiste in un software che gestisce l'organizzazione dei dati in modo più astratto e ad alto livello.

Senza DBMS abbiamo un sistema operativo che si interfaccia con i singoli file attraverso il file system, mentre con il DBMS il database è un file unico gestito in modo più astratto. Il problema principale del file system è che deve fornire una descrizione del file ad ogni processo che ne fa richiesta, generando possibili problemi di coerenza. Il DBMS invece ha una descrizione (Catalog o Data Dictionary) che vale per tutti e fornisce vari servizi in maniera più astratta.

Caratteristiche del DBMS

• Condivisione dei dati: le stesse informazioni sono accessibili da parte di più utenti, senza dover fare la copia per ogni singolo utente.
• Concorrenza (accesso contemporaneo di più utenti): gestisce l'accesso esclusivo alle informazioni serializzando le richieste. Il prof fa l'esempio stupendo di due persone che accedono al Bancomat allo stesso istante. Se le richieste non vengono serializzate, si regalano soldi :D
• Vincoli di integrità: il dato inserito deve essere coerente con i vincoli, per esempio se inserisci il voto di un esame non puoi mettere 47.
• Efficienza per caricamento, query, sort.
• Privacy e controllo dell'accesso.
• Robustezza contro crash e possibili incidenti: un metodo utilizzato in risposta al problema di hard disk failure è il RAID, cioè l'uso di un array di hard disk che contengono esattamente gli stessi dati e sono usati in parallelo nel centro di calcolo. Ma anche i centri di calcolo sono replicati in più posti fisici differenti nel caso in cui succedano disastri naturali. Il DBMS garantirà la coerenza di tutte le copie ridondanti.

Nel DBMS i dati sono memorizzati una sola volta senza ridondanza nel database. In questo modo non solo si usa molta meno memoria (conseguenza ovvia), ma ci si assicura anche che il dato abbia un solo valore. Se ci fossero più copie il dato potrebbe avere più valori e quindi verrebbe meno l'integrità. Ci sarebbe anche un peggioramento dell'efficienza, perché per modificare un dato bisognerebbe cercare tutte le sue occorrenze e aggiornarle.

Per usare un DBMS bisogna definire la struttura dei dati e poi le operazioni che possiamo compiere su di essi. Un esempio è la tabella di nome Studente che contiene colonne per memorizzare matricola, nome, città e corso di studi. Nota che i nomi delle tabelle sono sempre al singolare, anche se contengono più elementi.

Linguaggi e utenti del database

I linguaggi per la programmazione di database si dividono in due categorie: linguaggi di definizione dei dati (DDL) e linguaggi di manipolazione dei dati (DML). Quello che studieremo noi è SQL, un linguaggio di manipolazione.

Gli utenti possono usare diversi linguaggi: gli amministratori usano DDL, i programmatori usano DML, gli utenti occasionali usano versioni user friendly del DML (tipo con interfacce grafiche), mentre gli utenti finali usano le applicazioni e non si interessano di queste diavolerie.

Esistono numerosi DBMS per soddisfare diverse esigenze. Essi differiscono più o meno come differiscono i compilatori del C: i comandi standard sono uguali, ma sono diversi nelle funzionalità più avanzate.

Internamente un DBMS possiede un processore DDL e un processore DML. Il primo agisce direttamente sul catalog (che sta su disco insieme al database naturalmente), mentre il secondo legge il database, ma non direttamente, bensì attraverso il piano di esecuzione query, che analizza le richieste di interrogazione e le ottimizza prima di eseguirle.

L'obiettivo del corso è saper progettare basi di dati, saperle interrogare e in generale sapere un po' di cosa stiamo parlando. Noi vedremo prima la teoria delle basi di dati, poi come interrogarle con SQL e solo alla fine le progetteremo (ha senso didatticamente).

Modelli di dati

I dati vanno strutturati in un certo modo ed esistono vari modelli per poterlo fare, alcuni di questi sono:

• Modello gerarchico (anni 60).
• Modello reticolare (anni 70).
• Modello relazionale (anni 80).
• Modello a oggetti (anni 90).
• Modello XML (anni 00).

Il modello gerarchico dice che i dati sono rappresentati come record e ci sono dei puntatori ai record strutturati ad albero. Quindi è un modello che conosciamo. Anche il modello reticolare lo conosciamo perché è come il precedente, ma al posto di una struttura ad albero abbiamo una struttura a grafo, che permette di muoversi più liberamente.

Il modello relazionale ha i dati rappresentati come tabelle e non come record, ed è il modello che studieremo noi. Le associazioni, cioè i collegamenti tra le informazioni che fanno riferimento allo stesso oggetto, vengono fatte non con i puntatori, ma con attributi in comune tra diverse tabelle. Il modello a oggetti lo conosciamo già dall'informatica mentre quello XML lo vedremo con Fraternali nel corso di tecnologie web.

Dicevamo che ci sono tanti DBMS: quello più diffuso è Oracle, di cui ne esistono tante versioni con prezzi molto diversi. Gratuito per piccoli database, ma ultramilionario man mano che aumentano le funzionalità richieste... È diventato tra i più diffusi perché è portabile e funziona su sistemi diversi.

Definizione informale del modello relazionale

Ma diamo ora una definizione informale del modello relazionale, cioè della tabella. È una tabella con un nome (mi raccomando, al singolare), che dispone di righe e colonne. Ogni colonna contiene un attributo e ogni riga è un'istanza di un dato.

Una definizione più formale e quindi comprensibile (dipende) è data da queste altre definizioni. Le righe contengono tuple e le colonne fanno riferimento ad attributi delle tuple. Abbiamo un dominio di valori accettati. Facendo il prodotto cartesiano di più domini otteniamo l'insieme di tutte le possibili tuple esistenti (ovviamente sono un botto).

La relazione è un qualunque sottoinsieme del prodotto cartesiano dei domini. Le notazioni sulle slide sono molto chiare al riguardo. Il grado della relazione è dato dal numero di domini (numero di colonne in pratica), mentre la cardinalità della relazione è il numero di tuple (aka di righe). Gli attributi devono avere nomi distinti all'interno della stessa relazione. La tabella risultante di fatto è la relazione.

Attenzione! Nelle slide ci sono alcuni esempi di tabelle e uno di quelli (precisamente quello sugli scontrini) mette in chiaro una cosa: nelle basi di dati non esiste un ordinamento delle tuple. Se vogliamo sapere l'ordine con cui si presentano le informazioni bisogna aggiungere un attributo in più che lo esplicita.

Vincoli di integrità

Nelle basi di dati bisogna rispettare alcuni vincoli di integrità:

• Escludere istanze che non rappresentano il mondo applicativo: per esempio se un attributo rappresenta il voto di un esame, bisogna escludere tutti i valori che non hanno senso.
• Vincoli sui valori nulli: alcuni dati possono avere valori nulli, mentre altri sono obbligatori.
• Integrità referenziale e vincoli generici.
• Chiavi: il concetto di chiave permette di identificare in modo univoco una tupla all'interno di una certa relazione. La chiave è un sottoinsieme di attributi che rispettano le caratteristiche di minimalità e unicità. Per unicità si intende che non possono esistere chiavi con attributi uguali, e minimalità significa che basta togliere un attributo dalla chiave per perdere l'unicità.

Algebra relazionale

L'algebra relazionale è un formalismo insieme ad altri come il calcolo relazionale e la programmazione logica per descrivere le relazioni e le query. Infatti il linguaggio SQL che studieremo ha un interprete associato nel DBMS che, come abbiamo visto, attua delle ottimizzazioni alle query prima di eseguirle. Queste ottimizzazioni sono facilmente realizzabili se la query è maneggiata in algebra relazionale.

L'algebra relazionale dispone di operatori fondamentali unari e binari e alcuni operatori derivati, tutti binari. Il risultato di ogni operazione è sempre una relazione. Vediamo quindi questi operatori quali sono e come funzionano.

Selezione

Sintassi σ [relazione][predicato di selezione]

Esempi σ StudenteNome='Paolo' σ Studente(Città='Torino') OR (Città='Roma')

Significato

Data una relazione, seleziona le tuple che rispettano il predicato di selezione. Questo predicato può contenere non solo operatori di uguaglianza ma tutti gli operatori di confronto e logici che si usano normalmente.

Proiezione

Sintassi Π [relazione][attributi]

Esempio Π StudenteNome,Dipartimento

Significato

Data una relazione seleziona il sottoinsieme con gli attributi dati, quindi in pratica seleziona delle colonne della tabella. Attenzione! Se selezionando gli attributi ci sono dei duplicati, essi vengono eliminati. La presenza dei duplicati deve essere richiesta esplicitamente.

Assegnamento

Non è un operatore algebrico, ma è l'equivalente dell'assegnamento nella programmazione. Possiamo assegnare una relazione ad una variabile per fare conti più complessi.

Unione

Sintassi Sintassi insiemistica dell'unione

Significato

Ritorna la relazione che è l'unione di due relazioni. Se una tupla si presenta su entrambe le tabelle viene inserita una volta sola come spiegato prima. Attenzione però! Affinché l'unione sia fattibile le due tabelle devono essere compatibili, ovvero devono avere lo stesso grado e gli attributi devono avere gli stessi nomi.

Differenza

Sintassi Sintassi insiemistica della differenza

Significato

Ritorna la relazione che è la differenza di due relazioni. Anche qui le due tabelle devono essere compatibili.

Prodotto cartesiano

Sintassi Sintassi insiemistica del prodotto cartesiano

Significato

Praticamente restituisce tutto. Il numero di colonne risultante è la somma delle colonne (quindi il grado è la somma dei gradi). Ogni tupla della prima tabella è associata a tutte le tuple della seconda tabella, per cui la cardinalità risultante è il prodotto delle cardinalità. Ritorna un tabellone gigante con tutte le combinazioni possibili tra tuple e attributi.

Intersezione

Sintassi Sintassi insiemistica dell'intersezione

Derivazione R - (R - S)

Significato

Sai cos'è l'intersezione quindi bona. Ma ricordati la compatibilità.

Join

Sintassi [tabella1] [simbolo di join] [tabella2][predicato di relazione]

Derivazione σ [tabella1] [prodotto cartesiano] [tabella2][predicato di relazione]

Significato

Quindi si selezionano le tuple che soddisfano il requisito partendo dal prodotto cartesiano delle due relazioni. Se l'operatore di confronto è l'uguaglianza, parliamo di equi-join. Un suo caso particolare è il join naturale in cui dal prodotto cartesiano si considerano le tuple con gli attributi omonimi, quindi è utile per unire tabelle che condividono degli attributi in un'unica tabella. In questo caso la sintassi non esplicita il predicato di relazione, ma mette solo il simbolo di join.

Il tabellone che rappresenta il join di tutte le tabelle del database prende il nome di prima forma normale.

Semijoin

Sintassi [tabella1] [simbolo di semi-join] [tabella2][predicato di relazione]

Derivazione Π [tabella1] [simbolo di join] [tabella2]Attr([tabella1]) [predicato di relazione]

Significato

Come il join, ma nella tabella finale tiene in considerazione solo gli attributi della prima tabella, per cui funziona un po' come un filtro.

Questi operatori vanno utilizzati per tradurre delle query scritte in linguaggio naturale. Alcuni casi sono intuitivi, ma per altri (quelli dati dai professori per capirci) bisogna avere degli accorgimenti furbi e un paio sono molto importanti. Per esempio se compare un “nessuno” nella query, sicuramente c'è di sotto una differenza da fare. Mentre se si chiede un valore massimo (minimo), la strategia usata è fare il join della relazione che contiene il valore con se stessa per trovare i valori non massimi (minimi), che poi vengono sottratti dalla tabella originale. Attenzione proprio alle differenze che devono essere fatte tra tabelle compatibili: a questo scopo spesso si fanno dei semijoin al posto di normali join.

Ottimizzazioni dell'algebra relazionale

Come detto nella lezione precedente, l'algebra relazionale è uno strumento utile per effettuare ottimizzazioni sulle query prima di eseguirle. Il nostro compito ora è proprio vedere quali sono queste ottimizzazioni. Per prima cosa dobbiamo considerare la struttura ad albero dell'espressione, ovvero l'albero che contiene gli operatori nei nodi interni e gli operandi sulle foglie. Esaminando l'albero è facile identificare le trasformazioni possibili. Qui elenchiamo tutte le ottimizzazioni, sulle slide invece c'è il disegno dell'albero e la simbologia corretta delle espressioni per ognuna.

1) Eliminazione dei prodotti cartesiani

La selezione su un prodotto cartesiano di due tabelle si può trasformare direttamente nel join delle due tabelle. Ciò si può fare se il predicato di selezione è nella forma ATTR comp ATTR.

2) Push della selezione rispetto al join

Anziché fare la selezione sul join di due tabelle, possiamo direttamente fare la selezione sulla prima tabella e poi fare il join sulla seconda (o viceversa, dipende da quale attributo coinvolge il join, se della prima o della seconda tabella). Questo perché il join richiede il calcolo del prodotto cartesiano, che ritorna un bordello di tuple. Lo scopo principale delle ottimizzazioni è proprio ridurre il numero delle tuple da processare prima di effettuare ogni tipo di join.

3) Push della proiezione rispetto al join

Anche qui, anziché fare il join di due tabelle e poi la proiezione, ha più senso prima fare la proiezione sulle tabelle e poi il join delle due. In questo caso bisogna modificare il predicato di selezione su ciascuna tabella, in modo che esse ritornino gli attributi necessari sia dalla proiezione di partenza che dal join da effettuare.

4) Idempotenza della selezione

Qua non capisco bene il senso: anziché fare un'unica selezione con due predicati collegati in AND possiamo fare due selezioni distinte. Ovviamente il risultato non cambia, ma non capisco in cosa consiste l'ottimizzazione. Forse è utile per applicare alcuni tipi di push.

5) Idempotenza della proiezione

Pure qui possiamo spezzare una proiezione in due proiezioni, ma bisogna fare attenzione! Se chiamiamo L l'insieme degli attributi da proiettare e L₁ ed L₂ gli insiemi degli attributi delle proiezioni spezzate, dobbiamo ricordarci che L = L₁ ed L₂ è un superset di L (ovvero è più grande o tuttalpiù uguale ad L). Altrimenti perdi i pezzi.

6) Push della selezione rispetto all'unione

Anziché fare l'unione di due tabelle e poi fare la selezione, puoi prima applicare la selezione su entrambe le tabelle e poi unirle.

7) Push della selezione rispetto alla differenza

Esattamente come prima, ma applicato sulla differenza.

8) Push della proiezione rispetto all'unione

Analogamente, anziché fare la proiezione sull'unione, fai prima la proiezione sulle tabelle e poi le unisci. Attenzione però che non vale il push della proiezione sulla differenza e l'intersezione, perché la proiezione ha proprietà diverse.

9) Commutazione di join e unione

Diabolico, lasciamolo perdere...

Calcolo relazionale

Dopo l'algebra relazionale, ci restano da fare il calcolo relazionale e poi il Datalog. Il calcolo relazionale è composto da un insieme di linguaggi formali che si classificano come TRC (Tuple Relational Calculus) oppure DRC (Domain Relational Calculus). Quello che studiamo noi è il TRC, che a sua volta si divide in tuple arbitrarie e tuple ristrette su range. Nel nostro caso trattiamo il TRC su tuple arbitrarie, perché ci servirà a capire perché l'SQL funziona in un certo modo.

Il TRC è un linguaggio dichiarativo, cioè permette all'utente di dichiarare che cosa si vuole ottenere senza dire come ottenerlo. Questo servizio invece è offerto dall'algebra relazionale, che è un linguaggio procedurale, ovvero descrive la procedura per ottenere un risultato. Essendo procedurale, proprio come il software, può essere ottimizzato.

Definizione formale del TRC

• Forma standard {t | p(t)}.
• T è una tupla.
• P(t) è una proprietà della tupla.
• P(t) è una formula composta da atomi.
• P è detto predicato e t sono i suoi termini.
• Ogni operazione del calcolo relazionale ritorna un insieme, di conseguenza i duplicati (come di