Appunti completi corso Basi di dati

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 consueto) vengono eliminati

Sono atomi:

∈

t R

– t [A ] comp t [A ]

– 1 1 2 2

t[A] comp k

– comp è un comparatore =, !=, >, >=, <, <=

– k è una costante

– t[A] è una restrizione sull’attributo A della tupla t

–

Regole di costruzione delle formule:

Se p è una formula, lo sono anche ¬p e (p)

– ∧ ∨

Se p e p sono formule, lo sono anche p p , p p e p → p

– 1 2 1 2 1 2 1 2

∀ ∈ ∃ ∈

Se p è una formula con variabile s, lo sono anche s R (p(s)) e s R (p(s))

–

Dalle regolette qua sopra capisci subito che il TRC funziona in modo molto simile alla

logica del prim'ordine. Alla fine TRC e AR hanno lo stesso identico potere espressivo e si

può passare facilmente da uno all'altro. Ogni operatore dell'AR ha infatti una corrispettiva

traduzione in TRC, come spiegato qui sotto:

∃ ∈

SELEZIONE { t | t R (t[A]=1) }

∃ ∈

PROIEZIONE { t | t R (t[A,B]=t [A,B]) }

1 1

∃ ∈ ∃ ∈ ∨

UNIONE { t | t R, t S (t = t t = t ) }

1 2 1 2

∃ ∈ ∉

DIFFERENZA { t | t R (t S) }

∃ ∈ ∃ ∈ ∧ ∧

JOIN { t | t R, t S (t[A,C] = t [A,C] t[B,D] = t [B,D] t[A] = t[B] ) }

1 2 1 2

C'è una cosa che nessuno dei due linguaggi sa fare: CONTARE! Se vuoi sapere quante

sono le tuple che rispettano una certa caratteristica, non puoi farlo con l'algebra o il calcolo

relazionale. Non puoi dire qual è la squadra di F1 che ha vinto più gran premi consecutivi,

ma in SQL sì. Quindi AR e TRC non sono computazionalmente completi. Tuttavia puoi fare

il "next", cioè puoi dire quali tuple sono consecutive tra loro, imponendo che presa la prima

e presa la seconda, non ce ne sta nessun'altra in mezzo. Altre operazioni come la

negazione o trovare il massimo sono molto più semplici, perché basta usare il

quantificatore “non esiste”, come se fosse logica.

Il DATALOG è un linguaggio che fonde il modello di programmazione logica basato su

regole del Prolog col mondo delle basi di dati. Si compone di REGOLE, che sono formate

da un lato sinistro (HEAD) e da un lato destro (BODY) nella forma P ← P , P … P

1 2 n

Ogni P è un PREDICATO che soddisfa certe condizioni e tutti i predicati del corpo sono

implicitamente collegati in AND. Sono composti da un nome, da costanti, variabili e simboli

di “don't care”, per esempio Persona(X, _, “M”). Se nella testa ci sono delle variabili, esse

devono comparire nel corpo altrimenti non è possibile effettuare il binding, per cui si può

dire Padre(X, Y) ← Persona(X, _, "M"), Genitore(X, Y). Ogni tupla corrisponde ad un

vero o falso e in Datalog viene chiamata FATTO. Le regole sulla sinistra possono avere

qualsiasi nome vogliamo e lo stesso per le variabili, mentre i predicati sulla destra hanno

un nome corrispondente a quello di una relazione.

Per fare una query il fatto viene introdotto dal simbolo ?- per cui ?- Padre(“Carlo”, X)

chiede di cercare tutte le tuple che hanno come padre Carlo. Ciò che il Datalog ritorna è

un INSIEME delle tuple che rispettano il fatto. Le query qui si chiamano GOAL e se non

hanno variabili ritornano solamente vero o falso.

Se ho fatto una regola, posso definire nuove regole a partire da quelle che ho già creato.

Nelle slide c'è l'esempio per identificare nonni e zii usando la regola Padre e alcune

variabili intermedie.

La corrispondenza tra Datalog e algebra relazionale si coglie facilmente: le costanti (tra

virgolette nel caso di stringhe) sono selezioni, le variabili a sinistra sono proiezioni, le

variabili interne (cioè che compaiono solo a destra) sono join.

Le basi di dati vanno divise tra la categoria ESTENSIONALE, cioè l'insieme delle tabelle,

e la categoria INTENSIONALE, cioè l'insieme dei predicati sulla sinistra delle regole, che

rappresenta la conoscenza che si può ottenere a partire dai fatti. Di solito si assume e si

obbliga che non vi sia intersezione tra il mondo estensionale e quello intensionale. Il

perché non l'ho capito (e anzi manco ho capito a cosa serve sto intensionale).

Anche il Datalog ha la negazione NOT che si pone prima del predicato. Senza la

negazione possiamo già fare selezione, intersezione, prodotto cartesiano, proiezione e

unione (l'unione si ottiene scrivendo più regole con la stessa testa). La negazione è

necessaria per fare la differenza (viene tradotta praticamente con AND NOT). Occhio che

la negazione deve essere SAFE affinché l'interprete non finisca in un loop infinito: se

compare una variabile in un predicato negato, la stessa variabile deve comparire in

un altro predicato non negato. Così abbiamo dimostrato che il Datalog è espressivo

almeno quanto l'algebra relazionale. Ma in realtà è più potente perché permette la

RICORSIONE! Una query diventa ricorsiva se la sua testa appare nel corpo! Come nella

programmazione, per fare una buona ricorsione ci serve l'unione di due regole: un caso

base e un caso ricorsivo in cui la testa compare nel corpo.

Lessico del Datalog

Relazione → PREDICATO

Attributo → ARGOMENTO

Tupla → FATTO

Query → REGOLA

Interrogazione → GOAL

L'algebra relazionale è un linguaggio procedurale, perché ci dice come valutare le

interrogazioni e come tale permette di essere ottimizzata. Il calcolo relazionale invece è

dichiarativo, cioè dichiara cosa ci interessa trovare senza specificare il come. Il Datalog è

anch'esso dichiarativo, ma va a costruire dipendenze fra regole in maniera procedurale.

Il linguaggio SQL assomiglia molto al TRC, mentre l'AR assomiglia a quello che succede

all'interno del DBMS quando le query in SQL vengono processate. Il Datalog è un ponte

fra le basi di dati e il mondo dell'intelligenza artificiale, dei linguaggi, dei sistemi deduttivi e

della logica.

L'SQL (STRUCTURED QUERY LANGUAGE) è un linguaggio di query che fa tante belle

cose ed è stato soggetto a numerose standardizzazioni. La maggior parte dei sistemi

attuali segue lo standard SQL-89 con l'aggiunta di alcune estensioni proprietarie per

arricchire il linguaggio (cioè comandi extra non riconosciuti da tutti i DBMS). Molto simile è

il livello Entry SQL appartenente allo standard successivo SQL-92.

Nell'SQL abbiamo dei DOMINI che definiscono l'insieme di valori ammissibili per una

variabile (perciò corrispondono ai tipi della programmazione). I domini si distinguono tra

quelli elementari e quelli definiti dall'utente.

CHARACTER

Rappresentano le stringhe di caratteri di lunghezza fissa o variabile.

[ ] [ ] [ FamigliaCaratteri ]

character varying (Lunghezza) character set

Si possono usare le abbreviazioni e e fare dichiarazioni come

char varchar char(10)

o varchar(40).

BIT

Rappresentano sequenze fisse o variabili di singoli bit che possono vale vero o falso.

[ ] [ ]

bit varying (Lunghezza)

DOMINI NUMERICI ESATTI

Per rappresentare interi e numeri razionali. Ci sono varie sintassi equivalenti:

[ Precisione [, Scala ] ]

numeric ( )

[ Precisione [, Scala ] ]

decimal ( )

bigint

integer

smallint

DOMINI NUMERICI APPROSSIMATI

Per rappresentare numeri reali in virgola mobile.

[ ]

float (Precisione)

real

double precision

ISTANTI TEMPORALI

MySQL

date(sintassi 'YYYY-MM-DD')

[ ] [ ] :

time (Precisione) with time zone (campi hour, minute, second)

[ ] [ ]

timestamp (Precisione) with time zone

Con timezone si hanno i due ulteriori campi e

timezone_hour timezone_minute

INTERVALLI TEMPORALI

PrimaUnitàDiTempo [ UltimaUnitàDiTempo ]

interval to

Le unità di tempo sono divise in 2 gruppi:

year, month

– day, hour, minute, second

–

Esempi:

interval year to month

– interval second

–

Possiamo definire noi dei tipi personalizzati specificando il nome, gli elementi che

compongono il tipo, il valore di default e dei vincoli.

NomeDominio DominioElementare

create domain as

[ ValoreDefault ] [ Constraints ]

Esempio: create domain Voto as smallint default null

Il valore di default si inserisce con questa sintassi < ValoreGenerico | |

default user

> dove il valore generico è un valore compatibile con il dominio elementare del tipo

null

personalizzato e è la login dell'utente attivo. Invece è un valore comune a tutti

user null

i domini e sta ad indicare che il valore non è noto o potrebbe non esistere.

I vincoli possono essere di vari tipi:

= il dominio