Utente:FulvioBambusi/Sandbox

Nell'ambito della gestione di un database esistono tre tipi di linguaggi formali con i quali si possono esprimere query:

• L'Algebra Relazionale, che è un linguaggio procedurale (ovvero si esplicita la procedura per costruire l'informazione richiesta). Esso si basa su cinque operazioni fondamentali (selezione, proiezione, unione, differenza e prodotto cartesiano) e tre derivate (intersezione, join e semi-join) che danno l'intero potere espressivo del linguaggio.

• Il Calcolo Relazionale, che invece è dichiarativo (ovvero viene esplicitata qual è l'informazione da estrarre, ma non come). Questo linguaggio si basa sulla logica del primo ordine e, a parte le formule unsafe, ha un potere espressivo equivalente a quello dell'algebra relazionale. Si divide in due tipologie principali: il calcolo delle tuple (TRC, Tuple Relational Calculus) e il calcolo dei domini (DRC, Domain Relational Calculus).

• Il Datalog, che possiede un potere espressivo maggiore rispetto all'algebra relazionale e del trc in quanto può esprimere query ricorsive. Anch'esso si basa sulla programmazione logica, come derivato del Prolog.

Esempio di query in Algebra Relazionale e in TRC:
Mostrare il nome degli studenti 
che abbiano preso 28 all'esame di Basi di Dati.
Database: 
STUDENTE (Matricola, Nome, DatadiNascita, Indirizzo);
ESAME (Matricola, CodiceCorso, Data, Voto);
CORSO (CodiceCorso, Titolo, Docente);

Algebra Relazionale:
Π Nome σ Voto=28 ∧ Titolo='BasidiDati'
(STUDENTE ▷◁ ESAME ▷◁ CORSO)

TRC:
{ t | ∃ t1 ∈ STUDENTE,
∃ t2 ∈ ESAME,
∃ t3 ∈ CORSO
( t[Nome]=t1[Nome] ∧
t1[Matricola]=t2[Matricola] ∧
t2[CodiceCorso]=t3[CodiceCorso] ∧
t2[Voto]=28 ∧ t3[Titolo]='BasidiDati') }

Datalog:
VOTO (Nome) :-Studente(M, Nome, _ _),
Esame(M, CCorso, _, V),
Corso(CCorso, T, _),
V=28, T='Basi di Dati'

Espressioni algebriche in TRC

Essendo le query dell'algebra relazionale esprimibili tramite cinque funzioni fondamentali, per dimostrare che il suo potere espressivo è compreso in quello del calcolo (ovvero che non esistono query esprimibili in algebra relazionale ma non in trc) è sufficiente mostrare come queste cinque primitive siano esprimibili in trc.

Selezione

$\sigma _{condizione}R\leftrightarrow \{t|\exists t_{1}\in R(condizione\land t=t_{1})\}$

Proiezione

$\Pi _{attributo_{1},attributo_{2},...attributo_{n}}R\leftrightarrow \{t|\exists t_{1}\in Rt[attributo_{1}]=t_{1}[attributo_{1}]\land t[attributo_{2}]=t_{1}[attributo_{2}]\land ...t[attributo_{n}]=t_{1}[attributo_{n}])\}$

Prodotto cartesiano

Se TABELLA₁ è composta dagli attributi a,b,c e TABELLA è composta da d,e

$TABELLA_{1}\times TABELLA_{2}\leftrightarrow \{q|\exists t\in TABELLA_{1},s\in TABELLA_{2}(q[a]=t[a]\land q[b]=t[b]\land q[c]=t[c]\land q[d]=s[d]\land q[e]=s[e])\}$

Differenza

$TABELLA_{1}-TABELLA_{2}\leftrightarrow \{q|\exists t\in TABELLA_{1}(q=t\land (\not \exists s\in TABELLA_{2}(s=q)))\}$

Unione

$TABELLA_{1}\cup TABELLA_{2}\leftrightarrow \{q|\exists t\in TABELLA_{1},s\in TABELLA_{2}(q=t\lor q=s)\}$

Espressioni TRC in Algebra Relazionale

Se, come visto precedentemente, tutte le operazioni dell'algebra relazionale possono essere tradotte con espressioni più o meno complesse in TRC, non è detto che questo possa avvenire anche al contrario. Infatti è importante sottolineare che il potere espressivo dell'Algebra Relazionale e del TRC può dirsi equivalente solo quando quest'ultimo linguaggio viene limitato alle espressioni definite safe.

Una formula safe in Calcolo, è una formula indipendente dal dominio, ovvero che non deve dipendere dalla possibilità di variare di questo.

Query unsafe

Una formula unsafe è una formula che dipende dal dominio.

• Esempio di query unsafe:

 { t | t ∉ R }

Questa espressione ha per risultato infinite tuple (o per meglio dire tutte le tuple costruibili a partire dal dominio su cu t è definita, e quindi non è “indipendente dal dominio”. Questa query dunque non può essere valutata in algebra.

Superiorità del Datalog

Le interrogazioni ricorsive non possono essere espresse nè in algebra relazionale nè in trc (un'interrogazione è ricorsiva se è espressa in termini di sè stessa). Forniamo di seguito un esempio di interrogazione non esprimibile in algebra senza fornire una dimostrazione di questo fatto.

La tabella Gerarchia rappresenta un organigramma aziendale in cui ogni impiegato ha al più un superiore.

matricolaImpiegato	matricolaSuperiore

In questo contesto l'interrogazione "estrarre la matricola di tutti i dipendenti diretti o indiretti di in superiore" non è esprimibile in algebra. Essa andrebbe infatti realizzata tramite un numero di join dipendente dall'istanza della tabella, e sarebbe pertanto impossibile garantirne sempre la correttezza (data una query costituita da n join è sufficiente che un impiegato abbia n+1 superiori indiretti per rendere il risultato della query non completo). L’espressione corretta della query richiede l’uso della ricorsione.

Ricorsione in Datalog

Le interrogazioni ricorsive sono invece esprimibili in Datalog: la testa di una regola può comparire nel suo corpo. La regola di cui sopra potrebbe ad esempio essere risolta così:

Supervisore(IMP,MAN) :-Gerarchia(IMP,MAN)
Supervisore(IMP,MAN) :-Gerarchia(IMP,MED),Supervisore(MED,MAN)
?-Supervisore('Antonio',_)

Note

• Lucidi del corso di basi di dati 1 POLIMI (PDF), su home.deib.polimi.it. URL consultato il 29 novembre 2016.
• Database system concepts - 6 edition, su codex.cs.yale.edu. URL consultato il 12 dicembre 2016.