Appunti completi corso Basi di dati

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.

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.

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

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

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

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 σ Studente

Nome='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 Π Studente

Nome,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.

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

1 2

delle proiezioni spezzate, dobbiamo ricordarci che L = L ed L è un superset di L (ovvero

1 2

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

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