Le basi di dati contengono informazioni sulle quali le applicazioni eseguono delle operazioni di interrogazione e aggiornamento dei dati. Per questo motivo assumono importanza i linguaggi che definiscono le funzioni di interrogazione e di selezione dei dati. L'algebra relazionale e' un linguaggio procedurale che, pur non essendo diverso dalle quello implementato dalle basi di dati, permette di esprimere operazioni complesse sui dati come una sequenza passi piu' semplici.
L'algebra relazionale e' costituita da un insieme di operatori. Gli operatori sono definiti su relazioni e restituiscono ancora relazioni. E' possibile combinare piu' operatori per costruire interrogazioni complesse.
Gli operatori si suddividono in:
- operatori insiemistici: Unione, Intersezione, Differenza.
- operatori che estraggono righe o colonne di una tabella: Selezione, Proiezione
- operatori che combinano righe di differenti tabelle: Prodotto Cartesiano, Join
Due relazioni R e S sono compatibili se: 1) hanno lo stesso numero di attributi, cioe’ lo stesso grado, 2) gli attributi nella stessa posizione sono dello stesso tipo.
1. Unione di relazioni
Date due relazioni compatibili R ed S, l’unione di R con S è la relazione ottenuta dall’unione insiemistica delle due relazioni (unione di tuple di R ed S)
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 |
| C003 | Luigi | Verdi | Via Moro, 4 |
| C004 | Guido | Galli | Via Po, 23 |
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 |
| C002 | Paolo | Bianchi | Via Roma, 12 |
| C003 | Luigi | Verdi | Via Moro, 4 |
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 |
| C002 | Paolo | Bianchi | Via Roma, 12 |
| C003 | Luigi | Verdi | Via Moro, 4 |
| C004 | Guido | Galli | Via Po, 23 |
Ad esempio, nella gestione dell'anagrafe tributaria, i contribuenti si dividono in persone fisiche e persone giuridiche, cioe' le persone e le imprese. Supponiamo che la relazione PersoneFisiche abbia schema PersoneFisiche(CodiceFiscale, Nominativo) ove il nominativo contiene la stringa nome e cognome. E che la relazione PersoneGiudiridiche abbia lo schema PersoneGiuridiche(CodiceFiscale, Denominazione). Quindi, si puo' dire che le due relazioni sono compatibili. Facendo l'unione delle due relazioni si ottiene l'elenco unico dei Contribuenti.
Notare che i valori duplicati, nell'algebra relazionale, vengono automaticamente eliminati dal risultato dell’operazione. (Questo non e’ vero nel linguaggio SQL).
2. Intersezione di due relazioni
Date due relazioni compatibili R ed S, l’intersezione di R e S costituisce tutte le tuple presenti sia in R che in S.
Grado(S) = Grado(R); T = intersect(R, S)
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 |
| C003 | Luigi | Verdi | Via Moro, 4 |
| C004 | Guido | Galli | Via Po, 23 |
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 |
| C002 | Paolo | Bianchi | Via Roma, 12 |
| C003 | Luigi | Verdi | Via Moro, 4 |
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 |
| C003 | Luigi | Verdi | Via Moro, 4 |
3. Differenza di relazioni
Date due relazioni compatibili R ed S, la differenza di R con S è la relazione ottenuta dalla differenza insiemistica delle due relazioni. In altre parole, R-S rappresenta la relazione delle tuple di R che non sono in S.
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 |
| C003 | Luigi | Verdi | Via Moro, 4 |
| C004 | Guido | Galli | Via Po, 23 |
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 |
| C002 | Paolo | Bianchi | Via Roma, 12 |
| C003 | Luigi | Verdi | Via Moro, 4 |
| CODICE | NOME | COGNOME | INDIRIZZO |
|---|---|---|---|
| C004 | Guido | Galli | Via Po, 23 |
Attenzione: R-S è diverso da S-R.
4. Proiezione di relazioni
Data una relazione R ed un sottoinsieme A = (A1, A2,..., Ak) dei suoi attributi, si definisce proiezione di R su A la relazione di grado K che si ottiene da R ignorando le colonne relative agli attributi non contenuti in A ed eliminando le eventuali tuple duplicate.
S = project R on A1, A2,..., Ak; Card(S) = Card(R); Grado(S) <= Grado(R)
Esempio:
| CODICE | NOME | COGNOME | INDIRIZZO | PROVINCIA |
|---|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 | MI |
| C002 | Paolo | Bianchi | Via Roma, 12 | MI |
| C003 | Luigi | Verdi | Via Moro, 4 | TO |
| NOME | COGNOME |
|---|---|
| Mario | Rossi |
| Paolo | Bianchi |
| Luigi | Verdi |
5. Selezione (o Restrizione) di una relazione
Data una relazione R ed un predicato P (semplice o composto) sui suoi attributi, l’operazione di selezione o restrizione di R a P è la relazione costituita della tuple di R che soddisfano P. (Se la proiezione seleziona le colonne, le restrizione seleziona le righe.)
S = restrict R where P(t); Card(S) <= Card(R); Grado(S) = Grado(R)
Esempio: i clienti della provincia di Milano
| CODICE | NOME | COGNOME | INDIRIZZO | PROVINCIA |
|---|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 | MI |
| C002 | Paolo | Bianchi | Via Roma, 12 | MI |
| C003 | Luigi | Verdi | Via Moro, 4 | TO |
| C004 | Guido | Galli | Via Po, 23 | PD |
| CODICE | NOME | COGNOME | INDIRIZZO | PROVINCIA |
|---|---|---|---|---|
| C001 | Mario | Rossi | Via Adige, 30 | MI |
| C002 | Paolo | Bianchi | Via Roma, 12 | MI |
I predicati semplici contengono gli operatori relazionali, i predicati composti contengono gli operatori logici che servono per connettere piu' predicati semplici. Ad esempio, tutti i clienti in provincia di Milano e Roma (where Provincia = "MI" OR Provincia = "RM"), tutti i clienti in provincia di Milano che si chiamano Bianchi (where Provincia = "MI" AND Cognome = "Bianchi")
6. Prodotto di relazioni
Date due relazioni qualsiasi R ed S, rispettivamente di grado g1 e g2 e cardinalità c1 e c2, il prodotto di R ed S è la relazione di grado g1+g2 e cardinalità c1*c2, le cui tuple si ottengono concatenando ogni tupla di R con ogni tupla di S.
Nel prodotto cartesiano ogni tupla di R viene replicata tante volte quante sono le tuple di S.
Il prodotto cartesiano di due relazioni restituisce tutte le possibili coppie di tuple, ma un prodotto di relazioni con migliaia di righe implica una espolsione di dati in memoria. Il prodotto cartesiano e' una relazione che, come contenuto informativo, non ha senso, ma e' il punto di partenza dell'operatore join.
| COD_ORD | DATA | COD_CLI |
|---|---|---|
| 001 | 20/10/2015 | 1000 |
| 002 | 23/10/2015 | 2000 |
| COD_ART | PREZZO | QTA |
|---|---|---|
| A001 | 10 | 500 |
| A002 | 20 | 400 |
| A003 | 30 | 300 |
| COD_ORD | DATA | COD_CLI | COD_ART | PREZZO | QTA |
|---|---|---|---|---|---|
| 001 | 20/10/2015 | 1000 | A001 | 10 | 500 |
| 001 | 20/10/2015 | 1000 | A002 | 20 | 400 |
| 001 | 20/10/2015 | 1000 | A003 | 30 | 300 |
| 002 | 23/10/2015 | 2000 | A001 | 10 | 500 |
| 002 | 23/10/2015 | 2000 | A002 | 20 | 400 |
| 002 | 23/10/2015 | 2000 | A003 | 30 | 300 |
Quando si fa una operazione di join tra due relazioni, il motore SQL, dietro le quinte, fa un prodotto cartesiano delle due relazioni. Ad esempio, supponiamo di avere una anagrafica di 100 clienti e una tabella di 1000 ordini, supponiamo che c'e' una relazione 1:N tra Clienti e Ordini. Se si incrociano i dati delle due tabelle con una join, la prima operazione eseguita dal motore SQL e' un prodotto cartesiano che possiede centomila tuple.
7. Join di due relazioni
Join operator pairs two tuples from different relations, if and only if a given join condition is satisfied.
Date due relazioni R e S, ha senso fare l'operazione di join se le due relazioni hanno in comune almeno un attributo dello stesso tipo. L'attributo in comune e', quasi sempre, una chiave primaria della relazione R e la chiave esterna della relazione S. Ad esempio, nell'associazione Giocatore-Penalita', ho la chiave primaria Giocatore.IdGiocatore e la chiave esterna Penalita.IdGiocatore: l'attributo IdGiocatore della relazione Giocatore e' univoco perche' e' chiave primaria, l'attributo IdGiocatore della relazione Penalita e' ripetuto perche' un giocatore puo' avere piu' penalita'. L'associazione Giocatore-Penalita' e' opzionale perche' non tutti i giocatori hanno una penalita'.
___________ /\ ___________
| | / \ | |
| Giocatore |________ Assegnazione ________| Penalita' |
|___________| (0,N) \ / (1,1) |___________|
\/
7.1 Join Naturale
Natural join (⋈) is a binary operator that is written as (R ⋈ S) where R and S are relations. The result of the natural join is the set of all combinations of tuples in R and S that are equal on their common attribute names.
Se voglio conoscere le penalita' del giocatore Mario Rossi, devo associare con una join i dati delle tabelle Giocatore e Penalita'. E ha senso fare la join tra le tabelle Giocatore e Penalita' perche' hanno in comune l'attributo IdGiocatore. Per cui eseguo la operazione di join naturale Giocatore ⋈ Penalita. In questo caso la join naturale diventa una operazione di join tra Giocatore.IdGiocatore e Penalita.IdGiocatore.
Una operazione di join viene eseguita attraverso piu' passi. Il primo passo e' un prodotto cartesiano. Il prodotto cartesiano possiede come colonne la somma delle colonne delle due tabelle e come righe la combinazione di tutte le righe della prima tabella con tutte le righe della seconda tabella. Il secondo passo consiste in una restrizione cioe' una selezione delle tuple aventi valori uguali sugli attributi in comune delle due relazioni, in questo caso IdGiocatore. Il terzo passo consiste nell'eliminare una delle due colonne uguali.
Esempio di Join Naturale
| IdGiocatore | Nome | Cognome |
|---|---|---|
| 1 | Mario | Rossi |
| 2 | Luca | Bianchi |
| 3 | Paolo | Verdi |
| IdPenalita | Data | Importo | IdGiocatore |
|---|---|---|---|
| 001 | 10/10/2015 | 100 | 1 |
| 002 | 11/10/2015 | 500 | 2 |
| Nome | Cognome | IdGiocatore | IdPenalita | Data | Importo |
|---|---|---|---|---|---|
| Mario | Rossi | 1 | 001 | 10/10/2015 | 100 |
| Luca | Bianchi | 2 | 002 | 11/10/2015 | 500 |
Se non ci fossero state penalita', la join sarebbe stata una relazione vuota, che non contiene tuple. In linguaggio naturale avremmo detto che nessun giocatore ha squalifiche.
7.2 Thetajoin e equijoin
The thetajoin operator is a general form of join operator which combines tuples from two relations where the combination condition does not simply consider shared attributes. The thetajoin uses a θ binary relational operator in the set {<, ≤, =, >, ≥}. In case the operator θ is the equality operator then this join is said to be an equijoin.
Gli EquiJoin sono la quasi totalità dei join effettuate. Il Join Naturale è un EquiJoin su tutti gli attributi comuni di R ed S, con eliminazione delle colonne duplicate.
___________ / \ ___________
| | / \ | |
| Agente |________ CLIENTELA ________| Cliente |
|___________| (0,N) \ / (1,1) |___________|
\ /
Supponiamo di avere una relazione Clienti e una relazione Agenti. Un Cliente si riferisce ad un solo agente e un agente puo' avere piu' clienti, cioe' Agenti-Clienti e' una associazione 1:N.
Esempio di Equijoin
| CodCli | NomeCli | Indirizzo | CodAgente |
|---|---|---|---|
| C001 | Bianchi Mario | Via Po, 23 | A0052 |
| C002 | Neri Paolo | Via Roma, 12 | A0016 |
| C006 | Verdi Luigi | Via Moro, 4 | A0052 |
| CodAg | NomeAg | Telefono |
|---|---|---|
| A0016 | Franchi Luca | 346 1736449 |
| A0044 | Livi Claudio | 339 1837447 |
| A0052 | Bini Sergio | 333 1234935 |
| CodCli | NomeCli | Indirizzo | CodAgente | NomeAg | Telefono |
|---|---|---|---|---|---|
| C001 | Bianchi Mario | Via Po, 23 | A0052 | Bini Sergio | 333 1234935 |
| C002 | Neri Paolo | Via Roma, 12 | A0016 | Franchi Luca | 346 1736449 |
| C006 | Verdi Luigi | Via Moro, 4 | A0052 | Bini Sergio | 333 1234935 |
La relazione finale, ottenuta tramite equijoin, mostra gli attributi di entrambe le tabelle. Il primo passo di questa join consiste in un prodotto cartesiano che incrocia le righe delle due tabelle generando 3*3=9 tuple, di cui solo 3 sono quelle che sodisfano la condizione di equijoin.
7.3 Outer Join
Natural Join, Thetajoin and Equijoin are called inner joins. Whereas the result of an inner join consists only of those tuples with matching attributes in the two operands, an outer join contains those tuples and additionally some unmatched tuples in one of the operands. There are different types of outer joins: left outer join, right outer join and full outer joins.
Consideriamo di nuovo la associazione Calciatori-Penalita. Con una equijoin sul campo IdGiocatore, la relazione finale mostra solo i giocatori con penalita. Supponiamo di volere visualizzare non solo i giocatori che hanno una penalita, ma tutti i giocatori e accanto ad ogni giocatore le sue eventuali penalita. L'operatore inner join restituise solo i giocatori con penalita, l'operatore outer join o join esterno restituisce un numero maggiore di tuple.
Consideriamo due relazioni L e R. Ci sono due tipi di outer join: il left outer join e il right outer join.
7.3.1 Left outer join
L'operatore left outer join restituisce tutte le tuple della relaziona a sinistra e solo le tuple della relazione a destra hanno un valore corrispondente per l’attributo comune.
Ad esempio L'operazione Giocatore left outer join Penalita restituisce tutte le tuple della inner join e in piu anche la riga
con i giocatori senza penalita, con il campo penalita non valorizzato, cioe NULL.
| IdGiocatore | Nome | Cognome | IdPenalita | Data | Importo |
|---|---|---|---|---|---|
| 1 | Mario | Rossi | 001 | 10/10/2015 | 100 |
| 2 | Luca | Bianchi | 002 | 11/10/2015 | 500 |
| 3 | Paolo | Verdi | NULL | NULL | NULL |
7.3.2 Right outer join
L'operatore right outer join visualizza tutte le tuple della relazione a destra e solo quelle della relazione a sinistra che hanno un valore corrispondente per l’attributo comune.
Ad esempio, nel caso delle relazioni Clienti e Agenti, tutti i clienti hanno un agente, ma ci sono anche agenti a cui non e' stato assegnato
nessun cliente. Per cui Clienti right join Agenti mostra tutti gli agenti anche l'agente "Livi Claudio" che non ha clienti associati.
| CodCli | NomeCli | Indirizzo | CodAgente | NomeAg | Telefono |
|---|---|---|---|---|---|
| C001 | Bianchi Mario | Via Po, 23 | A0052 | Bini Sergio | 333 1234935 |
| C002 | Neri Paolo | Via Roma, 12 | A0016 | Franchi Luca | 346 1736449 |
| C006 | Verdi Luigi | Via Moro, 4 | A0052 | Bini Sergio | 333 1234935 |
| NULL | NULL | NULL | A0044 | Livi Claudio | 339 1837447 |
Se facessi Giocatori right join Penalita avrei lo stesso risultato della equijoin.
Esempio: applicazione di outer join
Per lavoro, il professore faceva delle ricerche su tabelle con i versamenti ICI contenenti degli errori. La prima tabella era l'anagrafe dei contribuenti,
avente codice fiscale come chiave primaria, la seconda tabella era i versamenti avente codice fiscale come chiave esterna, perche' un contribuente fa
piu' versamenti nel tempo. Siccome l'operatore aveva commesso errori nell'inserimento dei dati, venivano fuori delle anomalie.
Infatti il database conteneva contribuenti senza versamenti e versamenti con codice fiscale che non erano attribuibili a un contribuente.
Per mettere in luce queste anomalie si utilizzano dei join esterni.
Ritorniamo agli esempi visti precedentemente. Consideriamo l'associazione cliente-agente, per visualizzare tutti gli agenti che non hanno clienti si fa
un join destro e la restrizione con la condizione che la chiave esterna CodAgente nella tabella Clienti non sia valorizzata (CodAgente = NULL),
infatti, se un agente non ha clienti, il suo valore non compare nella tabella Clienti.
Consideriamo l'associazione giocatore-penalita, per visualizzare l'elenco dei giocatori che non hanno penalita, si fa un join sinistro e la restrizione
con la condizione che, nella tabella Penalita, IdGiocatore sia NULL.
8. Esempi di applicazione degli operatori dell'algebra relazionale
Consideriamo il seguente frammento di schema di database di una filiale di una banca, con le tabella Cliente, ContoCorrente e Movimento. Un cliente puo' avere piu' conti correnti (non e' possibile cointestare un conto) e su un conto corrente si possono fare piu' movimenti. Se c'e' un conto corrente, sicuramente c'e' una persona che lo possiede, se c'e' un movimento, sicuramente e' legato ad un conto corrente e contemporameamente ad una persona.
Clienti(IdCliente, Cognome, Nome, Via, CAP, Citta, Provincia) ContoCorrenti(CodConto, IdCliente(FK), DataApertura, DataChiusura, Saldo) Movimenti(IdMovimento, CodConto(FK), Data, Importo, Causale)
Nella relazione ContoCorrenti, IdCliente e' chiave esterna. Nella relazione Movimenti, CodConto e' chiave esterna.
Vediamo alcuni esempi di interrogazioni sulla base di dati dei conti correnti. Questi esempi utilizzano un pseudolinguaggio relazionale. Gli operatori sono applicati in modo annidato e vengono eseguiti a partire da quelli piu' interni. Gli operatori si applicano a relazioni e generano nuove relazioni, la quale diventa l'operando dell'operatore successivo.
Esempio: Causale e importo dei movimenti aventi importo maggiore di 5000 euro
project (restrict Movimenti where Importo>5000) on Causale, Importo
Esempio: Codice conto e importo dei movimenti di Bianchi Mario
R = Clienti.IdCliente join ContoCorrenti.IdCliente project (restrict (R.CodConto join Movimenti.CodConto) where Cognome=‘Bianchi’ AND Nome=‘Mario’) on CodConto, Importo
Esempio: Elenco dei clienti (Cognome, Nome) che hanno effettuato movimenti con causale “Vers” nel mese di settembre 2006
R = Clienti.IdCliente join ContoCorrenti.IdCliente S = R.CodConto join Movimenti.CodConto project (restrict S where Causale=‘Vers’ AND Data>=’01/09/2006’ AND Data<=’30/09/2006’) on Cognome, Nome
Sull'algebra relazionale sono stati costruiti i linguaggi SQL, che implementano gli operatori definiti dall'algebra relazionale. Restrizione, proiezione e join rappresentano tutto quello che ci serve per fare le interrogazioni sulle basi di dati. Quando un motore SQL esegue una interrogazione, la prima cosa che il motore fa sono le join per collegare i dati di piu' tabelle, poi esegue la selezione delle righe e infine la selezione delle colonne.
Esempio: Data e importo delle penalita di Mario Rossi
project (restict (Giocatori.IdGiocatore join Penalita.IdGiocatore) where Cognome = 'Rossi' AND Nome ='Mario') on Data, Importo
Questo si traduce in SQL, in una delle due espressioni equivalenti:
SELECT Data, Importo FROM Giocatori INNER JOIN Penalita ON Giocatori.IdGiocatore = Penalita.IdGiocatore WHERE Cognome = 'Rossi' AND Nome = 'Mario' SELECT Data, Importo FROM Giocatori, Penalita WHERE Giocatori.IdGiocatore = Penalita.IdGiocatore AND Cognome = 'Rossi' AND Nome = 'Mario'
La condizione di equijoin si trova nella causola JOIN, per la prima versione, nella clausola WHERE, per la seconda. Se si usa un outer join va bene solo la prima versione, la seconda versione non va piu' bene.
No comments:
Post a Comment