Algebra relazionale Presentazione 12.1 Informatica Generale (Prof. Luca A. Ludovico)
-
Upload
angelica-di-giacomo -
Category
Documents
-
view
228 -
download
2
Transcript of Algebra relazionale Presentazione 12.1 Informatica Generale (Prof. Luca A. Ludovico)
Algebra relazionale
Presentazione 12.1
Informatica Generale (Prof. Luca A. Ludovico)
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Linguaggi di interrogazione per db relazionali
• Tipologia:– Dichiarativi: specificano le proprietà del
risultato ("che cosa")– Procedurali: specificano le modalità di
generazione del risultato ("come")
• Rappresentanti più significativi:– Algebra relazionale: procedurale– SQL (Structured Query Language): dichiarativo
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Algebra relazionale
• Si basa su un insieme di operatori– definiti su relazioni– che producono relazioni– che possono essere composti
• Le relazioni sono insiemi.
• I risultati dell’applicazione di operatori su relazioni (insiemi) debbono essere relazioni (insiemi).
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Operatori dell’algebra relazionale
• L'algebra relazionale ha 6 operatori di base e diversi operatori derivati, che possono cioè essere definiti come combinazione di operatori primitivi.
• Operatori fondamentali (di base):1. operatori binari di Unione
2. operatori binari di Differenza
3. operatori binari di Prodotto cartesiano
4. operatori unari di Selezione
5. operatori unari di Proiezione
6. operatori unari di Ridenominazione
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Operatori dell’algebra relazionale
• I sei operatori precedenti sono fondamentali, perché nessuno di essi può essere omesso senza perdere in espressività.
• Operatori derivati (da quelli di base):1. operatore insiemistico binario di Intersezione2. operatore di Join in varie forme (Theta-Join, Natural-Join, etc.)3. operatore di Divisione
• Nel seguito indichiamo con r(X) la relazione r definita sullo schema X. X è un insieme di attributi.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Unione (teoria degli insiemi)
• Nella teoria degli insiemi, l'unione di due insiemi A e B è data dall'insieme formato da tutti gli elementi che appartengono all'insieme A o all'insieme B o a entrambi.
• L'unione è una operazione binaria. Nell'algebra booleana corrisponde all'operatore OR; in logica, corrisponde alla disgiunzione.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Unione (relazioni)
• Vincolo: avere tuple omogenee cioè definite sugli stessi attributi.
• L'unione di due relazioni r1(X) e r2(X) definite sullo stesso insieme di attributi X è indicata con r1(X) r2(X).
• Il risultato è una relazione ancora su X contenente le tuple che appartengono a r1 oppure a r2 oppure a entrambe, senza ripetizioni delle eventuali tuple ripetute.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Unione
Nome Cognome
Uto Ughi
Severino Gazzelloni
Salvatore Accardo
Solisti Direttori
Nome Cognome
Riccardo Muti
Riccardo Chailly
Giuseppe Sinopoli
Daniele Gatti
Nome Cognome
Riccardo Muti
Riccardo Chailly
Giuseppe Sinopoli
Daniele Gatti
Uto Ughi
Severino Gazzelloni
Salvatore Accardo
Artisti = Solisti Direttori
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Intersezione (teoria degli insiemi)
• Nella teoria degli insiemi, l'intersezione di due insiemi A e B è data dall'insieme formato da tutti gli elementi che appartengono sia all'insieme A che all'insieme B contemporaneamente.
• L'intersezione è una operazione binaria. Nell'Algebra Booleana corrisponde all'operatore AND e, in logica, alla congiunzione.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Intersezione (relazioni)
• Vincolo: avere tuple omogenee cioè definite sugli stessi attributi.
• L’intersezione di due relazioni r1(X) e r2(X) definite sullo stesso insieme di attributi X è indicata con r1(X) r2(X).
• Il risultato è una relazione ancora su X contenente solo le tuple che appartengono sia a r1(X) sia a r2(X).
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Intersezione
Nome Cognome
Luciano Pavarotti
Josè Carreras
Placido Domingo
Cantanti Direttori
Nome Cognome
Riccardo Muti
Placido Domingo
Daniel Harding
Daniele Gatti
Nome Cognome
Placido Domingo
Cantanti Direttori
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Differenza (teoria degli insiemi)
• Nella teoria degli insiemi, dati due insiemi A e B, il complemento di A rispetto a B (o l'insieme differenza B – A), è formato dai soli elementi di B che non appartengono ad A. Formalmente:
B – A = B / A = {x B x A}• Si noti che l'insieme differenza B - A è un
sottoinsieme dell'insieme B.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Differenza (relazioni)
• Vincolo: avere tuple omogenee cioè definite sugli stessi attributi.
• Il complemento di r1(X) e r2(X) è indicato come r2(X) − r1(X).
• Il risultato è una relazione su X contenente tutte le tuple che appartengono a r2(X) e non appartengono a r1(X).
• Si osservi che il secondo operando, r1(X), non è necessariamente un sottoinsieme di r2(X).
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Differenza
Direttori in attività Direttori italiani
Nome Cognome
Daniel Harding
Daniel Barenboim
Simon Rattle
James Levine
Direttori in attività Direttori italiani
Nome Cognome
Riccardo Muti
Daniel Harding
Claudio Abbado
Daniel Barenboim
Simon Rattle
James Levine
Daniele Gatti
Nome Cognome
Antonino Votto
Arturo Toscanini
Giuseppe Sinopoli
Claudio Abbado
Daniele Gatti
Riccardo Muti
Problema sugli insiemi
• Alle volte, alcune operazioni insiemistiche sarebbero sensate ma sono rese impossibili dal fatto che gli attributi presentano nomi differenti.– Esempio: dati di locandina di Carmen
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Autori Interpreti
Cognome Qualifica
Bizet compositore
Meilhac librettista
Halévy librettista
Cognome Ruolo
Barenboim direttore
Rachvelishvili
Carmen, mezzosoprano
Kaufmann Don José, tenore
Autori Interpreti ?
Ridenominazione
• L'operatore unario di ridenominazione modifica lo schema di una relazione, cambiando i nomi di uno o più attributi.
• Utile per ottenere delle tuple omogenee quando non lo sono (pur se il campo semantico della query lo è).
• Ciò che cambia sono i nomi degli attributi, mentre i valori rimangono inalterati e vengono associati ai nuovi attributi.
• Sintassi: REN nuovo attrib. vecchio attrib. (operando)
nuovo attrib. vecchio attrib. (operando)
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Ridenominazione
• Si “modifica lo schema” lasciando inalterata l'istanza
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Autori Interpreti
Cognome Qualifica
Bizet compositore
Meilhac librettista
Halévy librettista
Cognome Ruolo
Barenboim direttore
Rachvelishvili
Carmen, mezzosoprano
Kaufmann Don José, tenore
Ora è possibile calcolare Autori REN Qualifica Ruolo (Interpreti)
REN Qualifica Ruolo (Interpreti)
Cognome Qualifica
Barenboim direttore
Rachvelishvili
Carmen, mezzosoprano
Kaufmann Don José, tenore
Schemi omogenei
Selezione
• È un operatore unario che restituisce come risultato una relazione.
• Sintassi:SEL condizione (operando)
condizione (operando) ove condizione è un’espressione booleana
• Semantica: produce un risultato che– ha lo stesso schema dell'operando– contiene un sottoinsieme delle ennuple dell'operando– contiene solo le ennuple che soddisfano una data condizione,
complessa a piacere
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Esempi di selezione
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Selezionare tutti gli studenti di nome “Paola”:
NOME = “Paola” (studente)
Esempi di selezione
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Selezionare tutti gli studenti in cui l’istanza dell’attributo CITTA’ è “Torino” o “Roma” e l’istanza dell’attributo C-DIP è diversa da “Log”
SEL ((CITTA= “Torino” OR CITTA= “Roma”) AND (NOT(C-DIP=“Log”))) (studente)
((CITTA= “Torino” CITTA= “Roma”)C-DIP=“Log”))) (studente)
Proiezione
• È un operatore unario che restituisce come risultato una relazione.
• Sintassi:PROJ lista attributi (operando)
lista attributi (operando)ove lista attributi è un sottoinsieme dello schema X.
• Semantica: produce un risultato che– ha parte degli attributi dell'operando, ossia tutti quelli elencati in
lista attributi– contiene ennuple cui contribuiscono tutte le ennuple
dell'operando
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Esempi di proiezione
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Restituire una tabella avente come schema gli attributi NOME e C-DIP e come istanza la restrizione delle tuple sugli attributi NOME e C-DIP
NOME, C-DIP (studente)
Esempi di proiezione
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Restituire una tabella avente come schema l’attributo C-DIP e come istanza la restrizione delle tuple sull’attributo C-DIP
C-DIP (studente)
Supponendo di fare un’operazione di proiezione solo sull’attributo C-DIP della relazione studente, si verrebbero a creare dei duplicati, delle tuple ripetute (ci sono infatti due studenti nel corso d’informatica). Nei linguaggi formali la proiezione elimina automaticamente i duplicati.
Cardinalità delle proiezioni
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
• Una proiezione:– contiene al più tante ennuple quante
l'operando– può contenerne di meno, a causa di
eliminazione di duplicati
• Se X, insieme degli attributi su cui si effettua la proiezione, è una superchiave di R, allora PROJX(R) contiene esattamente tante ennuple quante R.
Selezione e proiezione
• Sono due operatori "ortogonali“– selezione: decomposizione orizzontale– proiezione: decomposizione verticale
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Selezione
Proiezione
Esercizi
• Quali studenti (identificati dal solo nome) sono iscritti al diploma di informatica?
• Quali studenti di Logistica (identificati dalla matricola) non sono di Milano?
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Soluzioni
• Quali studenti (identificati dal solo nome) sono iscritti al diploma di informatica?
Nome C-DIP=“Inf” (STUDENTE)
• Quali studenti di Logistica non sono di Milano?
Matr C-DIP=“Log” ((Città=“Milano”))(STUDENTE)
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Nome
Carlo
Paola
Matr
702
Esercizio
• Estrarre la matricola degli studenti che hanno preso almeno un voto superiore a 28 e non sono mai scesi sotto il 25.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Soluzione
• Vengono sottratti a tutti gli studenti (identificati dalla sola matricola) che hanno preso un voto maggiore o uguale a 28 tutti quelli che hanno preso un voto inferiore a 25.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Matr Voto>=28 (ESAME) - Matr Voto<25 (ESAME)
Estrazione di informazioni dalle relazioni
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
• Combinando selezione e proiezione, è possibile estrarre interessanti informazioni da una relazione.
• Non è ancora possibile però correlare informazioni presenti in relazioni diverse.
• Il join è l'operatore dell'algebra relazionale che permette di correlare dati in relazioni diverse.
Prodotto cartesiano
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
• Il prodotto cartesiano di due relazioni R e S, indicato con R x S, è una tabella (priva di nome) avente come schema gli attributi di R e S e come istanza tutte le possibili coppie di tuple di R e S.
Nome Cognome
Luciano Pavarotti
Josè Carreras
Cantanti Rappresentazioni Opera Teatro
Tosca Scala
Aida Metropolitan
Cantanti X RappresentazioniNome Cognome Opera Teatro
Luciano Pavarotti Tosca Scala
Luciano Pavarotti Aida Metropolitan
Josè Carreras Tosca Scala
Josè Carreras Aida Metropolitan
Join
• Join è un operatore derivato dell’algebra relazionale, e più precisamente si tratta di una particolare selezione fatta sulla relazione ottenuta da un prodotto cartesiano.
• Più formalmente ciò che produce il join è una tabella (priva di nome) avente per schema la concatenazione degli schemi di origine e per istanza le tuple ottenute concatenando quelle tuple dei due schemi che soddisfano un predicato.
• Sintassi: A JOIN predicato B oppure A predicato B
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Join
• La sintassi del predicato di join è un’espressione congiuntiva (ossia un AND) di predicati semplici:
ATTR1 op ATTR2
ove ATTR1 appartiene a TAB1, ATTR2 appartiene a TAB2 e op è un operatore di confronto.
• Il join può essere classificato in due diversi tipi: – equi-join: consente soli confronti di uguaglianza. Il predicato
va specificato.– join naturale: equi-join di tutti gli attributi omonimi. Si omette
il predicato e si elimina la colonna ripetuta.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Esempio di join
• Equi-join: STUDENTE STUDENTE.Matr = ESAME.Matr ESAMEè equivalente alla seguente espressione
STUDENTE.Matr = ESAME.Matr (STUDENTE X ESAME)
• Join naturale: STUDENTE ESAME
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Esempio di join naturale
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Join completo, incompleto e vuoto
• Se tutte le tuple delle relazioni chiamate in causa partecipano al join, si parla di join completo.
• Se alcune tuple dell’una o dell’altra relazione non vi partecipano, si parla di join incompleto.
• Se il join non riesce a relazionare alcuna tupla della prima relazione con alcun’altra della seconda relazione, si parla di join vuoto.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Join esterno
• Nel caso di join incompleto o vuoto, alcune ennuple possono non contribuire al risultato in quanto la colonna su cui opera il join non ha una controparte nell’altra relazione.
• Il join esterno estende, con valori nulli, le ennuple che verrebbero tagliate fuori da un join (interno). Esiste in tre versioni:– sinistro (JOINleft): mantiene tutte le ennuple del primo
operando, estendendole con valori nulli, se necessario– destro (JOINright): ... del secondo operando ...– completo (JOINfull): ... di entrambi gli operandi ...
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Osservazioni sulla cardinalità del join
• Siano R1(A,B), R2(B,C) due relazioni con alcuni attributi in comune, identificati come insieme B.
• In generale, il join di R1 e R2 contiene un numero di ennuple compreso fra zero ed il prodotto di |R1| e |R2|: 0 ≤ |R1 JOIN R2| ≤ |R1| × |R2|
• Se il join coinvolge una chiave di R2 (ovvero, B è chiave in R2), allora il numero di ennuple è compreso fra zero e |R1|: 0 ≤ |R1 JOIN R2| ≤ |R1|
• Se il join coinvolge una chiave di R2 (ovvero, B è chiave in R2) ed esiste un vincolo di integrità referenziale fra B (in R1) e R2, allora il numero di ennuple è pari a |R1|: |R1 JOIN R2| = |R1|
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Esercizio
• Estrarre il nome degli studenti che non hanno mai preso meno di 28.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Soluzione
• Nell’ultima parte della soluzione vengono trovate tutte le matricole degli studenti che hanno preso un voto minore di 28.
• Queste matricole vengono sottratte alle matricole di tutti gli studenti che hanno sostenuto esami. Rimangono quindi le matricole degli studenti che non hanno mai preso un voto minore di 28.
• Per trovare il nome di queste matricole viene fatto un join con la tabella STUDENTE.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Esercizio
• Estrarre il nome degli studenti che hanno sostenuto “informatica” e “matematica” lo stesso giorno.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1
Soluzione
• Viene inizialmente fatto un join (seconda riga) tra la tabella ESAME e le tuple della tabella CORSO che hanno come istanza dell’attributo Titolo la parola “informatica”. Facendo cosi si ottiene una tabella che contiene tutti gli studenti che hanno fatto l’esame di informatica (oltre a tutti gli attributi di ESAME e CORSO).
• Nell’ultima riga viene creata analogamente una tabella che contiene gli studenti che hanno fatto matematica. Ne vengono proiettati gli attributi Matr e Data e vengono ridenominati in MatrMat e DataMat. La relazione così ottenuta (formata dai due attributi MatrMat, DataMat) viene posta in join con la tabella degli studenti di informatica.
• Viene posta la condizione di join: Matr = MatrMat e Data = DataMat in modo da ottenere solo quegli studenti che hanno dato entrambi gli esami e nella stessa data.
• Il nome di questi studenti è però contenuto nella tabella STUDENTI, e quindi viene fatto un ulteriore join (la prima riga) proprio con la tabella STUDENTI, per ottenere i nomi degli studenti in questione.
Informatica Generale (Prof. Luca A. Ludovico)Presentazione 12.1