Algebra Relazionale

(1)

Universit` a degli Studi di Trieste

Corso di Laurea in Informatica

Algebra Relazionale

D. Gubiani

marzo 2008

D. Gubiani Algebra Relazionale 1

Linguaggi per Basi di Dati - 1

Distinguiamo due classi di linguaggi per basi di dati : - linguaggi di definizione, o definition data language (DDL),

utilizzati per definire gli schemi logici e le autorizzazioni per l’accesso

- linguaggi di manipolazione dei dati, o data manipulation language (DML), utilizzati per l’interrogazione e l’aggiornamento delle istanze di basi di dati

Introduzione Algebra Relazionale Ottimizzazione Algebrica

Linguaggi per Basi di Dati - 2

Inoltre, distinguiamo tra

- linguaggi dichiarativi, che specificano unicamente le propriet`a del risultato (SQL, QBE)

- linguaggi procedurali, che specificano le modalit`a di generazione del risultato (algebra relazionale)

Operatori Insiemistici Operatori Unari Operatori Derivati Operazioni Addizionali

Algebra Relazionale

E un linguaggio di interrogazione dei dati di tipo procedurale ` basato su concetti di tipo algebrico

L’algebra relazionale mette a disposizione un insieme di operatori che agiscono su relazioni producendo relazioni (propriet`a di chiusura dell’algebra relazionale, che garantisce la composizionalit`a degli operatori)

Dato uno schema di base di dati R, un’interrogazione pu` o essere vista come una funzione che, per ogni istanza r∈R, produce una relazione su un dato insieme di attributi

Operatori

Binarie (o insiemistiche): unione, intersezione (operazione derivata), differenza, prodotto cartesiano

Unarie: selezione, proiezione, rinomina Derivate: join (join naturale, theta-join)

Operatori Insiemistici

Le relazioni sono insiemi: l’algebra relazionale mette a disposizione gli operatori insiemistici (binari) di base (unione, differenza prodotto cartesiano e intersezione)

Ogni operatore riceve in input due relazioni e restituisce in output una relazione (eventualmente vuota)

E possibile applicare le operazioni di unione, intersezione e `

differenza solo a relazioni definite sugli stessi attributi

E possibile applicare l’operazione di prodotto cartesiano solo a `

(2)

Ottimizzazione Algebrica

Operazioni Addizionali

Unione

r 1 ∪ r 2 = {t|t ∈ r 1 ∨ t ∈ r 2 } Esempio. Unione laureati e quadri

Intersezione

r 1 ∩ r 2 = {t|t ∈ r 1 ∧ t ∈ r 2 }

Esempio. Determinare i laureati che sono anche quadri

Differenza

r 1 − r 2 = {t|t ∈ r 1 ∧ t¬ ∈ r 2 }

Esempio. Determinare i laureati che non sono quadri

Intersezione: A ∩ B = A - (A - B)

Prodotto Cartesiano - 1

Operazione insiemistica

Prende in ingresso due relazioni e restituisce in uscita una relazione che contiene tutte le possibili combinazioni di tuple

Prodotto Cartesiano - 2

Prodotto Cartesiano - 3

Cardinalit`a del risultato del prodotto cartesiano:

card(risultato) = card(tabella1) × card(tabella2)

Possono sorgere conflitti fra i nomi: in tali casi occorre la

rinomina degli attributi

(3)

Operatori Unari

Sono operatori che prendono in input una relazione (e restituiscono in output una relazione)

Due operatori pi` u uno:

- selezione - proiezione - rinomina

Selezione - 1

Prende in ingresso una relazione e seleziona il sottoinsieme delle istanze che soddisfano una data condizione

Sintassi: σ hcondizionei (r ) CONDIZIONI ELEMENTARI:

hnome attributoihoperatore confrontoihnome attributoi hnome attributoihoperatore confrontoihvalore costantei CONDIZIONI COMPLESSE:

si ottengono dalle condizioni elementari utilizzando i connettivi logici

Selezione - 2

Esempio. Selezionare tutti gli impiegati che afferiscono al dipartimento 4

σ DNO=4 (Impiegato)

Selezione - 3

Grado del risultato della selezione:

grado(risultato) = grado(operando) Cardinalit`a del risultato della selezione:

card(risultato) ≤ card(operando) Indice di selettivit`a della operazione:

indice di selettivit`a = card(risultato) card(operando)

Proiezione - 1

Prende in ingresso una relazione e restituisce la porzione di tale relazione relativa al sottoinsieme di attributi specificati in input

Sintassi: π <listaAttributi > (r)

Proiezione - 2

Esempio. Determinare matricola, cognome e stipendio di ogni impiegato

π Matricola,Cognome,Stipendio (Impiegato)

(4)

Proiezione - 3

Grado del risultato della proiezione:

grado(risultato) ≤ grado(operando) - il caso = non `e, per` o, significativo Cardinalit`a del risultato della proiezione:

card(risultato) ≤ card(operando)

Selezione e Proiezione

Selezione e proiezione

- sono operazioni complementari (ortogonali) - possono essere eseguite in sequenza

Esempio. π Matricola,Cognome (σ Stipendio>50 (Impiegati))

Osservazione

Pu` o essere utile assegnare un nome alle relazioni intermedie Esempio. (vedi testo in precedenza)

- r 1 ← σ Stipendio>50 (Impiegato) - r 2 ← π Matricola,Cognome (r 1 )

Rinomina

E spesso utile (alle volte necessario) rinominare gli attributi ` Sintassi:

ρ B

₁

...B

n

←A

1

...A

n

(r ) Esempio.

r 2 ←

ρ Matr50 Cognome50←Matricola Cognome (π Matricola,Cognome (r 1 ))

Operatori derivati

Componendo le operazioni di base, si possono ottenere nuove operazioni (operazioni derivate):

- Join - Divisione - Semi-join

Join

L’operatore di join permette di collegare dati contenuti in relazioni diverse, confrontando i loro valori

Esistono due tipi fondamentali di join:

- θ-Join

- Natural-Join

(5)

θ -Join - 1

L’operazione di θ-Join:

combinazione fra prodotto cartesiano e selezione σ _hcondi (r X s) = r ./ hcondi s

dove ogni condizione elementare in hcondi coinvolge un attributo di R ed un attributo di S

θ -Join - 2

θ -Join ed Equi-Join

Sintassi:

r ./ hcondizione joini s

Assumendo che r ∈ R(A 1 ...A n ) e s ∈ S(B 1 ...B m ), la condizione di join hcondizione joini ha la forma:

hcondizione joini ≡ hcond 1 i and . . . and hcond k i dove hcond i i = hattr . di Rihop. confrontoihattr . di Si;

Se cond 1 . . . cond k sono tutte condizioni di uguaglianza, il join

`e detto Equi-Join

Natural-Join

Versione dell’operazione di Join in cui si confrontano tutti e soli gli attributi con lo stesso nome

Sintassi:

R ./ S

o, equivalentemente, R ∗ S

Osservazioni

In genere, nella condizione di join non viene utilizzato il connettivo OR che pu` o essere sostituito dall’operazione UNION

L’operazione di natural-Join `e ovviamente possibile solo nel caso in cui gli attributi abbiano un nome

La relazione vuota `e una relazione

L’operazione di θ-Join senza condizioni e l’operazione di Natural-Join senza attributi con lo stesso nome degenerano

Semi-Join

Proiezione del risultato di un Natural-Join sugli attributi di una relazione

Sintassi:

R n S ≡ π R (R ∗ S) R o S ≡ π S (R ∗ S)

Esempio. Determinare tutti gli impiegati che lavorano ad almeno un progetto

r ← IMPIEGATI n LAVORAINPROGETTO

(6)

Divisione - 1

Esempio. Determinare il cognome degli impiegati che lavorano a tutti i progetti cui lavora Rossi

Divisione - 2

Soluzione 1:

ROSSI ← σ cognome=Rossi (IMPIEGATI ) R PROG ← ROSSI ∗ LAVORAINPROGETTO R P ← π progetto (R PROG )

IMP ← LAVORAINPROGETTO ÷ R P R ← π cognome (IMP ∗ IMPIEGATI )

Divisione - 3

Soluzione 2:

CANDIDATI ← π matricola (IMPIEGATI ) CONDIZIONI ← CANDIDATI × R P

NO GOOD ← CONDIZIONI − LAVORAINPROGETTO CANDIDATI CATTIVI ← π matricola (NO GOOD) R MATR ← CANDIDATI − CANDIDATI CATTIVI R ← π cognome (R MATR ∗ IMPIEGATI )

Operazioni Addizionali

Esiste una serie di operazioni addizionali che non possono essere ricavate dalle operazioni di base:

- Funzioni aggregate - Join esterno - Unione esterna

Funzioni Aggregate - 1

Operano su un insieme di dati e restituiscono come risultato un dato aggregato (una relazione contenente un solo valore) Sintassi:

F OPERATORE Attributo (r )

Funzioni Aggregate - 2

Esempio. Determinare il numero di impiegati dell’azienda, il

loro stipendio medio, lo stipendio massimo e l’ammontare

complessivo degli stipendi

(7)

Funzioni Aggregate - 3

Si possono usare anche pi` u funzioni aggregate:

F SUM salario, AVERAGE salario (IMPIEGATI )

Il nome dell’attributo del risultato `e la combinazione operatore attributo (`e possibile la rinomina)

Esiste la possibilit`a di eseguire preliminarmente una partizione delle tuple in modo che la funzione venga eseguita

separatamente sugli elementi di ciascuna classe - Esempio. Determinare il numero di impiegati per ogni

dipartimento

R1 ← DNO F COUNT matricola (IMPIEGATI )

Join Esterno - 1

Consente di gestire dei casi non coperti dal Join tradizionale Esistono tre tipi di Join esterno:

- Destro - Sinistro - Completo

Join Esterno - 2

Esempio. Determinare il cognome dei dipendenti con eventualmente i progetti a cui lavorano

R ←

π Cognome,Progetto (IMPIEGATI left join LAVORAINPROGETTO)

Unione Esterna

Esempio. Determinare l’unione delle relazioni Facolt`a(Nome,SSN,Dipartimento,Rank) Studenti(Name,SSN,Dipartimento,Advisor) R ← Facolt`aUnione Esterna Studenti dove R(Nome,SSN,Dipartimento,Rank,Advisor) Realizza l’unione fra relazioni non compatibili rispetto all’unione

Gli attributi non comuni assumono il valore NULL nelle tuple per le quali non hanno un valore

Equivalenza di Espressioni Algebriche Trasformazioni di Equivalenza Esempio

Equivalenza di Espressioni Algebriche

L’algebra relazionale permette di formulare espressioni fra loro equivalenti

Diversi tipi di equivalenza:

- equivalenza dipendente dallo schema - equivalenza assoluta

Equivalenza Dipendente dallo Schema

E 1 ≡ R E 2 se E 1 (r ) = E 2 (r ) per ogni r ∈ R Esempio.

π A,B (R 1 ) ./ π A,C (R 2 ) ≡ R π A,B,C (R 1 ./ R 2 )

Se e solo se R 1 ed R 2 hanno in comune il solo attributo A

(8)

Equivalenza Assoluta

(Non Dipendente dallo Schema)

E 1 ≡ E 2 se E 1 ≡ R E 2 per ogni R

Esempio. Per qualsiasi schema R, `e facile vedere che π A,B (σ A>0 (R)) ≡ σ A>0 (π A,B (R))

Ottimizzazione Algebriche - 1

L’ottimizzazione algebrica ha lo scopo di trovare

un’espressione che sia equivalente all’espressione data e possa essere eseguita in modo pi` u efficiente

Ottimizzazione Algebriche - 2

Infatti, in fase di esecuzione delle interrogazioni (specificate in SQL) vengono tradotte in algebra relazionale e viene valutato il costo

- il costo dell’esecuzione di un’interrogazione pu` o essere valutato in termini delle dimensioni dei risultati intermedi

In presenza di alternative equivalenti viene scelta l’espressione con costo minore

Trasformazioni di Equivalenza

Le trasformazioni di equivalenza sono operazioni che sostituiscono un’espressione con un’altra a essa equivalente

- interessanti se riducono il costo Alcune trasformazioni:

- atomizzazione delle selezioni - idempotenza delle proiezioni

- anticipazione della selezione rispetto al join - anticipazione della proiezione rispetto al join

Atomizzazione delle Selezioni

Una congiunzione di selezioni pu` o essere sostituita da una sequenza di selezioni atomiche

σ F

₁

∧F

2

(E ) ≡ σ F

₁

(σ F

₁

(E ))

Successive applicazioni permettono di operare su condizioni atomiche

Nota. E`e una qualsiasi espressione.

Idempotenza delle Proiezioni

Una proiezione pu` o essere trasformata in una sequenza di proiezioni che eliminano i vari attributi in varie fasi π X (E ) ≡ π X (π X ,Y (E ))

Nota. E`e un’espressione definita su un insieme di attributi che contiene X e Y .

(9)

Anticipazione della Selezione Rispetto al Join

Anticipazione della selezione rispetto al join (pushing selections down)

σ F (E 1 ./ E 2 ) ≡ E 1 ./ σ F (E 2 )

Nota.Se la condizione F coinvolge solo attributi della sottoespressione E2.

Anticipazione della Proiezione Rispetto al Join

Anticipazione della proiezione rispetto al join (pushing projections down)

π X

₁

,Y

₂

(E 1 ./ E 2 ) ≡ E 1 ./ π Y

₂

(E 2 )

Nota.Con E1`e definita su X1, E2`e definita su X2,Y₂⊆X₂e (X1∩X₂) ⊆ Y2 (gli attributi di X₂Y₂non sono coinvolti nel join).

Combinata con l’idempotenza delle proiezioni, permette di eliminare subito da ciascuna relazione gli attributi che non compaiono nel risultato e non sono coinvolti nel join

Altre Trasformazioni di Equivalenza - 1

Inglobamento di una selezione in un prodotto cartesiano σ F (E 1 × E 2 ) ≡ E 1 ./ F E 2

Distributivit`a della selezione rispetto all’unione σ F (E 1 ∪ E 2 ) ≡ σ F (E 1 ) ∪ σ F (E 2 )

Distributivit`a della selezione rispetto alla differenza σ F (E 1 − E 2 ) ≡ σ F (E 1 ) − σ F (E 2 )

Distributivit`a della proiezione rispetto all’unione π X (E 1 ∪ E 2 ) ≡ π X (E 1 ) ∪ π X (E 2 )

Osservazione.La proiezione non `e distributiva rispetto alla differenza.

Altre Trasformazioni di Equivalenza - 2

Trasformazioni basate sulla corrispondenza tra operatori insiemistici e selezioni complesse:

σ F

₁

∨F

2

(R) ≡ σ F

₁

(R) ∪ σ F

₂

(R)

σ F

₁

∧F

2

(R) ≡ σ F

₁

(R) ∩ σ F

₂

(R) ≡ σ F

₁

(R) ./ σ F

₂

(R) σ F

₁

∧¬(F

2

) (R) ≡ σ F

1

(R) − σ F

2

(R)

Propriet`a distributiva del join rispetto all’unione E ./ (E 1 ∪ E 2 ) ≡ (E ./ E 1 ) ∪ (E ./ E 2 )

Esempio - 1

Esempio. Dato lo schema

{DIPARTIMENTO(dNumero, dNome, manager), IMPIEGATO(matricola, nome, cognome, dip, stipendio)}, trovare i nomi dei dipartimenti il cui manager guadagna pi` u di 80000 euro.

Esempio - 2

Soluzione non ottimizzata:

π dNome (σ matricola=manager ∧stipendio>80000 (IMPIEGATO ./

DIPARTIMENTO)) Si pu` o riscrivere come:

π dNome (σ matricola=manager (σ stipendio>80000 (IMPIEGATO ./

DIPARTIMENTO)))

(10)

Esempio - 3

Si pu`o riscrivere come:

π dNome (σ stipendio>80000 (IMPIEGATO) ./ matricola=manager

DIPARTIMENTO) Si pu`o riscrivere come:

π dNome (π matricola (σ stipendio>80000 (IMPIEGATO)) ./ matricola=manager

DIPARTIMENTO)