ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA...

56
ALGEBRA E CALCOLO ALGEBRA E CALCOLO RELAZIONALE RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE RIDENOMINAZIONE LOGICA PROPOSIZIONALE LOGICA PROPOSIZIONALE SELEZIONE SELEZIONE PROIEZIONE PROIEZIONE 1 2 3 4 5 6 INTRODUZIONE INTRODUZIONE I

Transcript of ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA...

Page 1: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

ALGEBRA E CALCOLO ALGEBRA E CALCOLO RELAZIONALERELAZIONALE

OPERATORI DELL’ALGEBRA RELAZIONALEOPERATORI DELL’ALGEBRA RELAZIONALE

UNIONE, INTERSEZIONE, DIFFERENZAUNIONE, INTERSEZIONE, DIFFERENZA

RIDENOMINAZIONERIDENOMINAZIONE

LOGICA PROPOSIZIONALELOGICA PROPOSIZIONALE

SELEZIONESELEZIONE

PROIEZIONEPROIEZIONE

11

22

33

44

55

66

INTRODUZIONEINTRODUZIONEINTRODUZIONEINTRODUZIONEII

Page 2: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

ESERCIZIESERCIZIESERCIZIESERCIZI

DIVISIONEDIVISIONEDIVISIONEDIVISIONEJOINJOINJOINJOIN

1010

1111

1212

1313

1414

1515

99

88

77

1616

ALGEBRA E CALCOLO RELAZIONALE INDICE

INTERROGAZIONI IN ALGEBRA RELAZIONALEINTERROGAZIONI IN ALGEBRA RELAZIONALEINTERROGAZIONI IN ALGEBRA RELAZIONALEINTERROGAZIONI IN ALGEBRA RELAZIONALE

EQUIVALENZA DI ESPRESSIONI ALGEBRICHEEQUIVALENZA DI ESPRESSIONI ALGEBRICHEEQUIVALENZA DI ESPRESSIONI ALGEBRICHEEQUIVALENZA DI ESPRESSIONI ALGEBRICHE

CALCOLO RELAZIONALE SUI DOMINICALCOLO RELAZIONALE SUI DOMINICALCOLO RELAZIONALE SUI DOMINICALCOLO RELAZIONALE SUI DOMINI

PREGI E DIFETTI DEL CALCOLO SU DOMINIPREGI E DIFETTI DEL CALCOLO SU DOMINIPREGI E DIFETTI DEL CALCOLO SU DOMINIPREGI E DIFETTI DEL CALCOLO SU DOMINI

CALCOLO SU TUPLE CON DICHIARAZIONI DI RANGECALCOLO SU TUPLE CON DICHIARAZIONI DI RANGECALCOLO SU TUPLE CON DICHIARAZIONI DI RANGECALCOLO SU TUPLE CON DICHIARAZIONI DI RANGE

ALGEBRA E CALCOLO CON VALORI NULLIALGEBRA E CALCOLO CON VALORI NULLI ALGEBRA E CALCOLO CON VALORI NULLIALGEBRA E CALCOLO CON VALORI NULLI

VISTEVISTEVISTEVISTE

Page 3: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

INTRODUZIONEINTRODUZIONE

linguaggio di interrogazione o Query Languagelinguaggio di interrogazione o Query Language: linguaggio tramite il : linguaggio tramite il quale un utente richiede delle informazioni da una base dati (bd);quale un utente richiede delle informazioni da una base dati (bd);sono una componente essenziale delle bd.sono una componente essenziale delle bd.

È importante studiare i fondamenti dei linguaggi di interrogazione, È importante studiare i fondamenti dei linguaggi di interrogazione, per vedere come i concetti sono realizzati in pratica nei sistemi per vedere come i concetti sono realizzati in pratica nei sistemi relazionali.relazionali.

I linguaggi di query procedurali oppure non procedurali:I linguaggi di query procedurali oppure non procedurali:– proceduraleprocedurale quando è necessario specificare la sequenza di operazioni quando è necessario specificare la sequenza di operazioni

(complesse), sul db, per ottenere il risultato desiderato; l’utente deve (complesse), sul db, per ottenere il risultato desiderato; l’utente deve specificare la procedura per ottenere il risultatospecificare la procedura per ottenere il risultato

– non proceduralenon procedurale l’utente descrive l’informazione desiderata senza l’utente descrive l’informazione desiderata senza specificare la procedura per ottenere il risultato, descrive solo le specificare la procedura per ottenere il risultato, descrive solo le proprietà del risultato.proprietà del risultato.

ALGEBRA E CALCOLO RELAZIONALE

Page 4: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

I linguaggi di query sono classificati in due classi:I linguaggi di query sono classificati in due classi:

•linguaggi algebrici (procedurali): ad esempio l’algebra relazionale; (procedurali): ad esempio l’algebra relazionale;

•linguaggi basati su calcolo dei predicati (non procedurali).: linguaggi di (non procedurali).: linguaggi di questa seconda classe possono esistere in due versioni, versione a questa seconda classe possono esistere in due versioni, versione a calcolo relazionale sulle tuple e versione a e versione a calcolo relazionale sui domini.

L’algebra relazionale è un linguaggio di interrogazione procedurale basato su L’algebra relazionale è un linguaggio di interrogazione procedurale basato su concetti di tipo algebrico, ed è costituito da un insieme di operatori; concetti di tipo algebrico, ed è costituito da un insieme di operatori; l’applicazione di ognuno di questi operatori algebrici alle relazioni produce l’applicazione di ognuno di questi operatori algebrici alle relazioni produce sempre come risultato una relazione.sempre come risultato una relazione.

ALGEBRA E CALCOLO RELAZIONALE INTRODUZIONE

Page 5: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Questa proprietà detta di Questa proprietà detta di chiusura significa che le operazioni almeno in significa che le operazioni almeno in linea di principio possono essere annidate “cioè il risultato di una certa linea di principio possono essere annidate “cioè il risultato di una certa operazione dell’algebra, essendo una relazione può essere a sua volta fornito operazione dell’algebra, essendo una relazione può essere a sua volta fornito come input alla stessa operazione”.come input alla stessa operazione”.

Nella definizione dell’algebra relazionale il nome degli attributi e Nella definizione dell’algebra relazionale il nome degli attributi e l’ordinamento delle tuple non è rilevante, inoltre si assume che tutte le l’ordinamento delle tuple non è rilevante, inoltre si assume che tutte le relazioni in gioco siano insiemi finiti, per cui per esempio non è consentita relazioni in gioco siano insiemi finiti, per cui per esempio non è consentita l’operazione algebrica di complemento dato che -R può denotare un insieme l’operazione algebrica di complemento dato che -R può denotare un insieme infinito (cioè l’insieme delle tuple che non sono in R).infinito (cioè l’insieme delle tuple che non sono in R).

La proprietà di chiusura non è posseduta dagli altri due modelli classici La proprietà di chiusura non è posseduta dagli altri due modelli classici (cioè gerarchico e reticolare).(cioè gerarchico e reticolare).

ALGEBRA E CALCOLO RELAZIONALE INTRODUZIONE

Page 6: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

OPERATORI OPERATORI DELL’ALGEBRA RELAZIONALEDELL’ALGEBRA RELAZIONALE

L’algebra relazionale propone 6 operatori di base e 3 derivati.L’algebra relazionale propone 6 operatori di base e 3 derivati.

Operatori Operatori fondamentali (di base): (di base):

•operatori unari dioperatori unari di Selezione, , Proiezione, , Ridenominazione..

•operatori binari di operatori binari di Prodotto Cartesiano, , Unione e e Differenza..

Operatori Operatori derivati (da quelli di base):(da quelli di base):

•operatore insiemistico binario di operatore insiemistico binario di Intersezione..

•operatore di operatore di join, in varie forme, , in varie forme, theta-join, , natural-join..

•operatore di operatore di divisione ( )

•Indichiamo conIndichiamo con r r (R), la relazione(R), la relazione r r definita sullo schema R.definita sullo schema R.

R è un insieme di attributi.R è un insieme di attributi.

ALGEBRA E CALCOLO RELAZIONALE

Page 7: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Unione, Differenza, IntersezioneUnione, Differenza, Intersezione

Le operazioni binarie di unione, differenza ed intersezione sulle relazioni di un data Le operazioni binarie di unione, differenza ed intersezione sulle relazioni di un data base richiedono che le loro relazioni-operando siano compatibili nei loro schemi.base richiedono che le loro relazioni-operando siano compatibili nei loro schemi.

Due relazioni Due relazioni rr (R) ed (R) ed s s (S) sono compatibili nei loro schemi se gli attributi di R (S) sono compatibili nei loro schemi se gli attributi di R coincidono con gli attributi di S:coincidono con gli attributi di S:

Def: se ADef: se A11... A... Ak k R ed B R ed B11...B...Bh h S, allora r(R) ed s(S) sono due relazioni S, allora r(R) ed s(S) sono due relazioni

compatibili se anche i due schemi R ed S lo sono, cioè deve esistere una funzione uno-compatibili se anche i due schemi R ed S lo sono, cioè deve esistere una funzione uno-uno fra R ed S tale che si abbia Dom(Auno fra R ed S tale che si abbia Dom(Aii)=Dom(B)=Dom(Bjj) per 1) per 1 i, j i, j k . k .

•l’unione di due relazionidi due relazioni r r ed ed ss definite sullo stesso insieme di attributi X è indicata definite sullo stesso insieme di attributi X è indicata con con rr ss ed è una relazione ancora su X contenente le tuple che appartengono ad ed è una relazione ancora su X contenente le tuple che appartengono ad r r oppure ad oppure ad ss, oppure ad entrambi;, oppure ad entrambi;

•la differenza didi r r (X) ed (X) ed ss (X) è indicata con (X) è indicata con r-sr-s ed è una relazione su X contenente ed è una relazione su X contenente le tuple che appartengono adle tuple che appartengono ad r r e non ad e non ad ss;;

•l’intersezione di rdi r(X)(X) eded s s(X) è indicata con (X) è indicata con rr ss ed è una relazione su X ed è una relazione su X contenente le tuple che appartengono sia ad contenente le tuple che appartengono sia ad r r sia ad sia ad s s..

ALGEBRA E CALCOLO RELAZIONALE

Page 8: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

LaureatiMatricola Cognome Età

7274 Rossi 377432 Neri 399824 Verdi 38

DirigentiMatricola Cognome Età

9297 Neri 567432 Neri 399824 Verdi 38

Esempio: operazioni di unione, intersezione e differenza

Matricola Cognome Età7274 Rossi 377432 Neri 399824 Verdi 389297 Neri 56

Matricola Cognome Età7432 Neri 399824 Verdi 38

Matricola Cognome Età7274 Rossi 37

Laureati Dirigenti Laureati Dirigenti

Laureati - Dirigenti

ALGEBRA E CALCOLO RELAZIONALE UNIONE, DIFFERENZA, INTERSEZIONE

Page 9: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Riguardo la definizione di compatibilità.

Supponiamo di avere una porzione di data base per grandi magazzini:Supponiamo di avere una porzione di data base per grandi magazzini:

Vendite (reparto, articolo)Vendite (reparto, articolo)

Fornitura (articolo, fornitore)Fornitura (articolo, fornitore)

Tipo ( articolo, colore, dimensione)Tipo ( articolo, colore, dimensione)

Dipendenti (nome, funzione, reparto, salario)Dipendenti (nome, funzione, reparto, salario)

Le relazioni Vendite e Tipo sono evidentemente non compatibili per unione.Le relazioni Vendite e Tipo sono evidentemente non compatibili per unione.

Le tuple sono disomogenee, mentre le tuple devono essere omogenee cioè Le tuple sono disomogenee, mentre le tuple devono essere omogenee cioè definite sugli stessi attributi.definite sugli stessi attributi.

Le relazioni Vendite e Fornitura, possono essere considerate compatibili Le relazioni Vendite e Fornitura, possono essere considerate compatibili per unione se reparto e fornitore sono entrambe definite nello stesso dominio per unione se reparto e fornitore sono entrambe definite nello stesso dominio (ossia se i loro valori appartengono allo stesso tipo-dati; ad esempio sono (ossia se i loro valori appartengono allo stesso tipo-dati; ad esempio sono entrambe stringhe di caratteri di uguale lunghezza massima).entrambe stringhe di caratteri di uguale lunghezza massima).

ALGEBRA E CALCOLO RELAZIONALE UNIONE, DIFFERENZA, INTERSEZIONE

Page 10: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

RIDENOMINAZIONERIDENOMINAZIONE

Consideriamo le due relazioni in figura:Consideriamo le due relazioni in figura:

Sarebbe sensato eseguire su di esse una sorta di unione, al fine di ottenere Sarebbe sensato eseguire su di esse una sorta di unione, al fine di ottenere tutte le coppie “genitore-figlio” note alla base di dati, ma ciò non è possibile, tutte le coppie “genitore-figlio” note alla base di dati, ma ciò non è possibile, perché l’attributo che intuitivamente abbiamo indicato con Genitore, si chiama perché l’attributo che intuitivamente abbiamo indicato con Genitore, si chiama in effetti Padre in una relazione e Madre nell’altra.in effetti Padre in una relazione e Madre nell’altra.

Per risolvere il problema si introduce un operatore diPer risolvere il problema si introduce un operatore di ridenominazione il il quale ha il compito di adeguare i nomi degli attributi, a seconda delle necessità, quale ha il compito di adeguare i nomi degli attributi, a seconda delle necessità, al fine di facilitare le operazioni insiemistiche. L’operatore è detto di al fine di facilitare le operazioni insiemistiche. L’operatore è detto di ridenominazioneridenominazione, perché cambia il nome degli attributi lasciando inalterato il , perché cambia il nome degli attributi lasciando inalterato il contenuto delle relazioni.contenuto delle relazioni.

PATERNITA' Padre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

MATERNITA' Madre FiglioEva CainoEva SetSara IsaccoAgar Ismaele

ALGEBRA E CALCOLO RELAZIONALE

Page 11: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Definizione:

Sia r una relazione definita sull’insieme di attributi X e sia Y un (altro) insieme Sia r una relazione definita sull’insieme di attributi X e sia Y un (altro) insieme di attributi con la stessa cardinalità. Inoltre, siano Adi attributi con la stessa cardinalità. Inoltre, siano A11AA22 … A … Akk e B e B11 … B … Bkk

rispettivamente un ordinamento per gli attributi in X e un ordinamento per quelli rispettivamente un ordinamento per gli attributi in X e un ordinamento per quelli in Y. Allora la ridenominazionein Y. Allora la ridenominazione

contiene una tupla contiene una tupla t’t’ per ciascuna tupla per ciascuna tupla tt in in rr, definita come segue:, definita come segue: t’ t’ è una tupla è una tupla su Y e su Y e t’t’[B[Bii] =] = t t[A[Aii], per i = 1,…, n.], per i = 1,…, n.

La definizione conferma che ciò che cambia sono i nomi degli attributi, mentre i La definizione conferma che ciò che cambia sono i nomi degli attributi, mentre i valori rimangono inalterati e vengono associati ai nuovi attributi. In pratica, nelle valori rimangono inalterati e vengono associati ai nuovi attributi. In pratica, nelle due liste Adue liste A11AA22 … A … Akk e B e B11 … B … Bkk indicheremo solo gli attributi che vengono indicheremo solo gli attributi che vengono

ridenominati (cioè quelli per cui Aridenominati (cioè quelli per cui Aii B Bii ). ).

)(...... 2121r

kk AAABBB

ALGEBRA E CALCOLO RELAZIONALE RIDENOMINAZIONE

Page 12: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Esempio (genitori-figli):

PATERNITA' Padre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

MATERNITA' Madre FiglioEva CainoEva SetSara IsaccoAgar Ismaele

PATERNITA' Padre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Unione sensata ma scorretta PATERNITA’Unione sensata ma scorretta PATERNITA’ MATERNITA’ ??? MATERNITA’ ???

Ridenominiamo le relazioni:Ridenominiamo le relazioni:

PATERNITA' Genitore FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

)'(PATERNITAPadreGenitore

ALGEBRA E CALCOLO RELAZIONALE RIDENOMINAZIONE

Page 13: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

MATERNITA' Madre FiglioEva CainoEva SetSara IsaccoAgar Ismaele

Unione preceduta da due ridenominazioni:

()'( MATERNITA’) PATERNITA MadreGenitorePadreGenitore Genitore FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Eva CainoEva SetSara IsaccoAgar Ismaele

MATERNITA' Figlio

Eva CainoEva SetSara IsaccoAgar Ismaele

Genitore

)'(MATERNITAMadreGenitore

ALGEBRA E CALCOLO RELAZIONALE RIDENOMINAZIONE

Page 14: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Altro esempio di unione preceduta da ridenominazione.

In questo caso, in ciascuna relazione sono due gli attributi che vengono In questo caso, in ciascuna relazione sono due gli attributi che vengono ridenominati e quindi l’ordinamento delle coppie (Sede, Retribuzione e così ridenominati e quindi l’ordinamento delle coppie (Sede, Retribuzione e così via) è significativo.via) è significativo.

Cognome Agenzia StipendioRossi Roma 45Neri Milano 53

Cognome Fabbrica SalarioVerdi Latina 33Bruni Monza 32

)()( ,Re,,Re, OPERAIIMPIEGATI SalarioFabbricatribuzioneSedeStipendioAgenziatribuzioneSede Cognome Sede Retribuzione

Rossi Roma 45Neri Milano 53Verdi Latina 33Bruni Monza 32

Un’altra unione preceduta da ridenominazioneUn’altra unione preceduta da ridenominazione

ALGEBRA E CALCOLO RELAZIONALE RIDENOMINAZIONE

Page 15: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Premesse: (selezione, proiezione)

Prima di entrare nel dettaglio degli operatori di Selezione, Proiezione e Join, Prima di entrare nel dettaglio degli operatori di Selezione, Proiezione e Join, facciamo alcune considerazioni sui primi due operatori: selezioni e proiezione facciamo alcune considerazioni sui primi due operatori: selezioni e proiezione svolgono funzioni complementari ( o ortogonali ).svolgono funzioni complementari ( o ortogonali ).

•Entrambi sono operatoriEntrambi sono operatori unari e producono come risultato una porzione della e producono come risultato una porzione della relazione-operando.relazione-operando.

Denotiamo con r (X) una relazione definita sullo schema X di attributi.Denotiamo con r (X) una relazione definita sullo schema X di attributi.•La selezione produce un sottoinsieme delle tuple, mantenendo inalterato lo La selezione produce un sottoinsieme delle tuple, mantenendo inalterato lo

schema su cui è definita le relazione. Le tuple selezionate sono quelle che schema su cui è definita le relazione. Le tuple selezionate sono quelle che soddisfano una certa condizione di selezione chiamato “predicato di selezione”.soddisfano una certa condizione di selezione chiamato “predicato di selezione”.

• La proiezione dà come risultato tutte le tuple ma su un sottoinsieme degli La proiezione dà come risultato tutte le tuple ma su un sottoinsieme degli attributi di X, cioè le tuple sono definite su un sottoinsieme (X’attributi di X, cioè le tuple sono definite su un sottoinsieme (X’X) degli attributi X) degli attributi che compongono lo schema della relazione di partenza.che compongono lo schema della relazione di partenza.

Possiamo dire che la selezione produce “Possiamo dire che la selezione produce “decomposizioni orizzontali”, mentre la ”, mentre la proiezione produce “proiezione produce “decomposizioni verticali”, vedi figura.”, vedi figura.

ALGEBRA E CALCOLO RELAZIONALE

Torna a selezione Torna a proiezione

Page 16: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

A B C A B C

Selezione: decomposizione orizzontale

A B C

Proiezione: decomposizione verticale

)(, rBAA B

)(Pr rselezionediedicato

r (A,B,C) r (A,B,C)

r (A,B,C ) r’(A,B)

ALGEBRA E CALCOLO RELAZIONALE PREMESSE ( SELEZIONE E PROIEZIONE )

Page 17: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Le figure precedenti mostrano le caratteristiche fondamentali dei due Le figure precedenti mostrano le caratteristiche fondamentali dei due operatori.operatori.

•L’operatore di selezione è denotato dal simbolo L’operatore di selezione è denotato dal simbolo a pedice del quale si esprime a pedice del quale si esprime il predicato di selezione il predicato di selezione P P opportuno. Il risultato è una istanza diversa di opportuno. Il risultato è una istanza diversa di relazione che contiene le tuple che soddisfano il predicato di selezionerelazione che contiene le tuple che soddisfano il predicato di selezione

PP = predicato di selezione , = predicato di selezione , r r = relazione = relazione

•L’operatore di proiezione è denotato dal simbolo L’operatore di proiezione è denotato dal simbolo a pedice del quale si a pedice del quale si specificano gli attributi che si vogliono proiettare. Il risultato è una relazione con specificano gli attributi che si vogliono proiettare. Il risultato è una relazione con uno schema diverso.uno schema diverso.

)(rP

)'(')(' XrrX

ALGEBRA E CALCOLO RELAZIONALE PREMESSE ( SELEZIONE E PROIEZIONE )

Page 18: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

LOGICA PROPOSIZIONALELOGICA PROPOSIZIONALE

Atomi e formule

La logica proposizionale fa uso di 5 operatori logici o connettivi: La logica proposizionale fa uso di 5 operatori logici o connettivi: (not (not logico o negazione), logico o negazione), (and logico o congiunzione), (and logico o congiunzione), (or logico o disgiunzione), (or logico o disgiunzione), (equivalenza o “se o solo se”), (equivalenza o “se o solo se”), (implicazione o “se allora”). (implicazione o “se allora”).

Una frase dichiarativa che è o vera o falsa (e non può essere simultaneamente Una frase dichiarativa che è o vera o falsa (e non può essere simultaneamente vera e falsa) viene dettavera e falsa) viene detta proposizione. I simboli impiegati per denotare le I simboli impiegati per denotare le proposizioni vengono informalmente denominati proposizioni vengono informalmente denominati formule atomicheformule atomiche o, più o, più brevementebrevemente atomi. In termini informali, un’espressione che rappresenta una In termini informali, un’espressione che rappresenta una proposizione o una proposizione composta viene dettaproposizione o una proposizione composta viene detta formula.

Le formule vengono definite ricorsivamente nel modo seguente:Le formule vengono definite ricorsivamente nel modo seguente:•un atomo è una formulaun atomo è una formula•se F è una formula, allora se F è una formula, allora F è una formulaF è una formula•se F e G sono formule, allora (F se F e G sono formule, allora (F G), (F G), (F G), (F G), (F G) ed (F G) ed (F G) sono G) sono

formuleformule•nessun altro ente è una formulanessun altro ente è una formula

ALGEBRA E CALCOLO RELAZIONALE

Torna a sintassie semantica

Torna a sintassie semantica

Page 19: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Precedenza operatoriPrecedenza operatori

Agli operatori logici si assegna il seguente ordine di precedenza Agli operatori logici si assegna il seguente ordine di precedenza decrescente:decrescente:

oppure ¯ , oppure ¯ , oppure oppure , , oppure +, oppure +, , , ..

Naturalmente la parentizzazione ha la precedenza più alta.Naturalmente la parentizzazione ha la precedenza più alta.

La La tavola di verità degli operatori è la seguente:degli operatori è la seguente:

H G Not H And Or Implicazione EquivalenzaT T F T T T TT F F F T F FF T T F T T FF F T F F T T

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 20: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Interpretazione delle formule

Data una formula F, siano AData una formula F, siano A11, … , A, … , An-1n-1, A, Ann gli atomi presenti in F. Una gli atomi presenti in F. Una interpretazione di F è un’attribuzione di valori di verità ad Adi F è un’attribuzione di valori di verità ad A11, … , A, … , An-1n-1, A, Ann, in cui , in cui

ciascun Aciascun Ajj, per 1 , per 1 j j n, è vero o falso. Dal momento che vi sono 2 n, è vero o falso. Dal momento che vi sono 2nn modi modi

possibili di attribuire valori di verità ad n atomi, esistono 2possibili di attribuire valori di verità ad n atomi, esistono 2nn interpretazioni di F. interpretazioni di F.

Una formula F si dice vera sotto una interpretazione se F viene valutata vera in Una formula F si dice vera sotto una interpretazione se F viene valutata vera in quell’interpretazione, e si dice falsa in caso contrario.quell’interpretazione, e si dice falsa in caso contrario.

Si dice che una formula èSi dice che una formula è valida, o che è unao che è una tautologia, se è vera sotto tutte le se è vera sotto tutte le sue interpretazioni, e che èsue interpretazioni, e che è non valida in caso contrarioin caso contrario.

Si dice che una formula èSi dice che una formula è incoerente o che è unao che è una contraddizione se è falsa sotto se è falsa sotto tutte le sue interpretazioni e viene dettatutte le sue interpretazioni e viene detta coerente in caso contrarioin caso contrario.

Se una formula è valida, allora essa è coerente, ma non è vero l’inverso. Se una formula è valida, allora essa è coerente, ma non è vero l’inverso. Analogamente, se una formula è incoerente allora essa è non valida, ma non è Analogamente, se una formula è incoerente allora essa è non valida, ma non è vero l’inverso. Ad esempio, la formula F vero l’inverso. Ad esempio, la formula F F è non valida dal momento che non F è non valida dal momento che non è una tautologia, eppure è coerente dal momento che non è una contraddizione. è una tautologia, eppure è coerente dal momento che non è una contraddizione. Se una formula F è vera sotto un’interpretazione M, diciamo allora che MSe una formula F è vera sotto un’interpretazione M, diciamo allora che M soddisfa F, o che F F, o che F è soddisfatta da M. d’altro canto, se una formula F è falsa da M. d’altro canto, se una formula F è falsa sotto un’interpretazione M, allora diciamo che M sotto un’interpretazione M, allora diciamo che M falsifica F o che F F o che F è è falsificata da Mda M.

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 21: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Equivalenza tra formule

Le equivalenze sono molto utili nel semplificare le formuleLe equivalenze sono molto utili nel semplificare le formule

F F G G F F G G

(F (F G) G) ( (FFG) G) (F (FG)G)

(F (F G) G) F F G (legge di De Morgan)G (legge di De Morgan)

(F (F G) G) F F G (legge di De Morgan)G (legge di De Morgan)

G G G G F equivale a una “contraddizione”, formula sempre falsa per qualsiasi F equivale a una “contraddizione”, formula sempre falsa per qualsiasi valore di verità di F e G. valore di verità di F e G.

G G G G T equivale ad una “tautologia”, formula sempre vera per qualsiasi T equivale ad una “tautologia”, formula sempre vera per qualsiasi valore di verità di G.valore di verità di G.

GG ( (GG H) H) (G (G G) G) G GH H F F G GH H G GH H

GG ( (G G H) H) (G (G G) G) (G(G H) H) T T G G H H G G H H

(F (F G) G) (F (F H) H) F F (G (GH)H)

Quando due formule sono equivalenti, la formula più complessa può essere Quando due formule sono equivalenti, la formula più complessa può essere sostituita dalla sua controparte equivalente per ottenere una semplificazione o anche sostituita dalla sua controparte equivalente per ottenere una semplificazione o anche una minimizzazione.una minimizzazione.

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 22: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Logica del primo ordineLogica del primo ordine

Predicati

la logica del primo ordine comprende tre ulteriori nozioni logiche: termini, la logica del primo ordine comprende tre ulteriori nozioni logiche: termini, predicati e quantificatori.predicati e quantificatori.

I termini vengono definiti ricorsivamente nel modo seguente:I termini vengono definiti ricorsivamente nel modo seguente:•Una costante, come ad esempio una costante numerica o un simbolo non Una costante, come ad esempio una costante numerica o un simbolo non

numerico (ad esempio una stringa di caratteri) è un termine.numerico (ad esempio una stringa di caratteri) è un termine.•Una variabile è un termine.Una variabile è un termine.

•Se f è un simbolo di funzione ennupla, e tSe f è un simbolo di funzione ennupla, e t11, … , t, … , tnn sono termini, allora f (t sono termini, allora f (t11,…,t,…,tn n ) )

è un termine.è un termine.•Nessun altro ente è un termine.Nessun altro ente è un termine.

Un predicato ennuplo Un predicato ennuplo pp è una funzione ennupla da (D è una funzione ennupla da (D11*D*D22* … *D* … *Dnn ) in { vero o ) in { vero o

falso }, dove “vero” e “falso” sono valori di verità.falso }, dove “vero” e “falso” sono valori di verità.

P P : D: D11*D*D22* … * D* … * Dnn {Vero, Falso} {Vero, Falso}

Formalmente, un atomo in logica di primo ordine viene definito nel modo Formalmente, un atomo in logica di primo ordine viene definito nel modo seguente: se seguente: se pp è un simbolo di un predicato n-plo e t è un simbolo di un predicato n-plo e t11,…,t,…,tn n sono termini, allora sono termini, allora pp(t(t11,,

…t…tnn) è un atomo. Vi sono quattro tipi di simboli che possono essere usati per ) è un atomo. Vi sono quattro tipi di simboli che possono essere usati per

costruire un atomo: le costanti, le variabili, i simboli di funzione ed i simboli di costruire un atomo: le costanti, le variabili, i simboli di funzione ed i simboli di predicato.predicato.

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 23: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

QuantificazioneQuantificazione

In un linguaggio di programmazione, quando una procedura P contiene una In un linguaggio di programmazione, quando una procedura P contiene una procedura Q ed esiste un identificatore x presente in Q, x è una variabile locale procedura Q ed esiste un identificatore x presente in Q, x è una variabile locale in Q se x è dichiarato in Q, ed è una variabile globale in caso contrario.in Q se x è dichiarato in Q, ed è una variabile globale in caso contrario.

Se una variabile x presente in una formula F è libera o limitata in F allora Se una variabile x presente in una formula F è libera o limitata in F allora essa è rispettivamente analoga ad una variabile globale o locale in un essa è rispettivamente analoga ad una variabile globale o locale in un linguaggio di programmazione.linguaggio di programmazione.

La variabile quantificata universalmente è (La variabile quantificata universalmente è (x), che si legge “per tutti gli x”, x), che si legge “per tutti gli x”, “per ciascun x”, o “per ogni x”. La variabile quantificata esistenzialmente è “per ciascun x”, o “per ogni x”. La variabile quantificata esistenzialmente è ((x), che si legge “esiste un x”, “per un certo x”, o “per almeno un x”. I simboli x), che si legge “esiste un x”, “per un certo x”, o “per almeno un x”. I simboli ed ed vengono detti rispettivamente vengono detti rispettivamente quantificatore universale ee quantificatore esistenziale.

Sia G(x) una formula in cui x è una variabile libera (ossia x non è Sia G(x) una formula in cui x è una variabile libera (ossia x non è quantificata in G). L’ambiente (scope) di Q (dove Q coincide con quantificata in G). L’ambiente (scope) di Q (dove Q coincide con o o ) in ) in una formula F:una formula F:

F:= Qx (G(x)) è la sottoformula G(x) a cui Q viene applicato. Nella F, la F:= Qx (G(x)) è la sottoformula G(x) a cui Q viene applicato. Nella F, la prima occorrenza di x situata a destra di Q è limitata in F, ed ogni altra prima occorrenza di x situata a destra di Q è limitata in F, ed ogni altra occorrenza di x situata nell’ambito G(x) è libera in G, dal momento che x non è occorrenza di x situata nell’ambito G(x) è libera in G, dal momento che x non è quantificata in G ma diventa limitata in F.quantificata in G ma diventa limitata in F.

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 24: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Analogamente, se y per yAnalogamente, se y per yx è anch’essa una variabile libera in G, allora y è x è anch’essa una variabile libera in G, allora y è libera sia in G(x,y) che in F(y), dove F(y):=Qx (G(x,y)). libera sia in G(x,y) che in F(y), dove F(y):=Qx (G(x,y)).

Una variabile può essere allo stesso tempo libera o limitata in una Una variabile può essere allo stesso tempo libera o limitata in una formula; ad esempio, la variabile y nella formula formula; ad esempio, la variabile y nella formula x(G(x,y))x(G(x,y))y (H(y)) è y (H(y)) è libera in libera in x(G(x,y)) ma è limitata in x(G(x,y)) ma è limitata in y (H(y)).y (H(y)).

F:= F:= x(G(x,y))x(G(x,y)) y (H(y)),y (H(y)), il simbolo := significa “è definito come”. il simbolo := significa “è definito come”.

EsempioEsempio

Le variabili libere sono quelle non quantificate:Le variabili libere sono quelle non quantificate:

F(k):= F(k):= x(G(x,y,k)) x(G(x,y,k)) y (H(y,k))y (H(y,k)), k è una variabile libera. , k è una variabile libera.

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 25: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

FormuleFormule

Nella logica del primo ordine, le Nella logica del primo ordine, le formuleformule vengono definite ricorsivamente nel vengono definite ricorsivamente nel modo seguente:modo seguente:

•Un atomo è una formula.Un atomo è una formula.•Se F e G sono formule, allora Se F e G sono formule, allora F, (F F, (F G), (F G), (F G), (F G), (F G), (F G), (F G) sono G) sono

formule.formule.•Se F è una formula ed x è una variabile libera in F, allora Se F è una formula ed x è una variabile libera in F, allora x(F(x)) ed x(F(x)) ed x(F(x)) sono formule.x(F(x)) sono formule.

•Nessun altro ente è una formula.Nessun altro ente è una formula.

In una formula, le parentesi possono essere omesse seguendo lo stesso ordine In una formula, le parentesi possono essere omesse seguendo lo stesso ordine di precedenza adottato per la logica proposizionale. Inoltre entrambi i di precedenza adottato per la logica proposizionale. Inoltre entrambi i quantificatori hanno lo stesso ordine di precedenza, che è superiore a quello quantificatori hanno lo stesso ordine di precedenza, che è superiore a quello dell’operatore logico di negazione.dell’operatore logico di negazione.

Una formula si dice Una formula si dice chiusa se tutte le sue variabili sono quantificate e viene se tutte le sue variabili sono quantificate e viene detta aperta in caso contrario.detta aperta in caso contrario.

Una formula chiusa è facilmente interpretabile, mentre una formula aperta è Una formula chiusa è facilmente interpretabile, mentre una formula aperta è difficilmente interpretabile. difficilmente interpretabile.

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 26: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Interpretazioni di formuleInterpretazioni di formule

Una Una interpretazione di una formula F nella logica del primo ordine è di una formula F nella logica del primo ordine è costituita da un dominio non vuoto D di valori e da una attribuzione di valori costituita da un dominio non vuoto D di valori e da una attribuzione di valori a ciascuna costante, simbolo di funzione e simbolo di predicato presenti in F a ciascuna costante, simbolo di funzione e simbolo di predicato presenti in F nel modo seguente.nel modo seguente.

(1) Per ciascuna costante, la costante stessa è un elemento in D.(1) Per ciascuna costante, la costante stessa è un elemento in D.

(2) A ciascun simbolo di funzione n-pla attribuiamo un valore in D (2) A ciascun simbolo di funzione n-pla attribuiamo un valore in D applicato da applicato da

DDnn f : Df : Dn n D D(3) A ciascun simbolo di predicato n-plo attribuiamo un valore di verità (3) A ciascun simbolo di predicato n-plo attribuiamo un valore di verità

(vero o (vero o

falso) applicato da Dfalso) applicato da Dnn p p : D: Dn n {vero, falso} {vero, falso}

Per ciascuna interpretazione di una formula su di un dato dominio D, la Per ciascuna interpretazione di una formula su di un dato dominio D, la formula viene formula viene valutata vera o falsa secondo le seguenti regole. vera o falsa secondo le seguenti regole.

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 27: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

(1) Ciascuna delle formule (1) Ciascuna delle formule F, (F F, (F G), (F G), (F G), (F G), (F G) e (F G) e (F G) viene G) viene

valutata vera o falsa come descritto nella tavola di verità. valutata vera o falsa come descritto nella tavola di verità.

(2) (2) x(F(x)) viene valutata vera se F è vera per tutti gli elementi nel x(F(x)) viene valutata vera se F è vera per tutti gli elementi nel dominio dominio

sottostante, e viene valutata falsa in caso contrario.sottostante, e viene valutata falsa in caso contrario.

(3) (3) x(F(x)) viene valutata vera se F è vera per un certo elemento del x(F(x)) viene valutata vera se F è vera per un certo elemento del dominio sottostante, e viene valutata falsa in caso contrario.dominio sottostante, e viene valutata falsa in caso contrario.

Una formula chiusa è facilmente interpretabile, mentre una formula aperta Una formula chiusa è facilmente interpretabile, mentre una formula aperta non può essere interpretata se tutte le variabili libere presenti nella formula non può essere interpretata se tutte le variabili libere presenti nella formula non vengono rappresentate da valori nel dominio sottostante.non vengono rappresentate da valori nel dominio sottostante.

Equivalenze: Equivalenze:

((x(F(x)) x(F(x)) x(x(F(x) )F(x) )

((x(F(x)) x(F(x)) x(x(F(x))F(x))

ALGEBRA E CALCOLO RELAZIONALE LOGICA PROPOSIZIONALE

Page 28: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

SELEZIONESELEZIONE (vedi premessa) (vedi premessa)

Per selezionare delle tuple specifiche da una relazione dobbiamo specificare Per selezionare delle tuple specifiche da una relazione dobbiamo specificare una certa condizione come criterio di selezione detto “una certa condizione come criterio di selezione detto “predicato di selezione”. ”. Denotiamo il predicato di selezione con una Denotiamo il predicato di selezione con una formula F che viene definita F che viene definita ricorsivamente nel modo seguente:ricorsivamente nel modo seguente:

• AA B, A B, A c c e e c c A sono formule, dove A e B sono attributi A sono formule, dove A e B sono attributi

compatibili, compatibili, cc è una costante in DOM(A), e è una costante in DOM(A), e è un operatore di è un operatore di

confronto aritmetico in confronto aritmetico in , , , , , , , , , , . Queste formule sono tutte . Queste formule sono tutte

atomiche.atomiche.

• Se G e H sono formule, allora la congiunzione G · H, la disgiunzione Se G e H sono formule, allora la congiunzione G · H, la disgiunzione

G+H e le negazioni G+H e le negazioni G ed G ed H sono formule.H sono formule.

• Nessun altro ente è una formula.Nessun altro ente è una formula.

ALGEBRA E CALCOLO RELAZIONALE

Premessa

Page 29: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Date una formula F e una tupla Date una formula F e una tupla tt, è definito un valore di verità per F su , è definito un valore di verità per F su tt::

•A A B è vera su B è vera su t t se e solo se se e solo se t t[A] è in relazione [A] è in relazione con con tt[B] [B]

esempio: A=B, è vera se esempio: A=B, è vera se tt[A] = [A] = tt[B];[B];

•A A c è vera su c è vera su t t se e solo sese e solo se t t[A] è in relazione [A] è in relazione con c; con c;

•FF1 1 F F22 , F , F1 1 F F22 , , FF11 hanno l’usuale significato. hanno l’usuale significato.

Possiamo completare la definizione:Possiamo completare la definizione:

•la selezione produce una relazione sugli stessi attributi di r che la selezione produce una relazione sugli stessi attributi di r che contiene le tuplecontiene le tuple t t di r su cui F è vera.di r su cui F è vera.

)(rF

ALGEBRA E CALCOLO RELAZIONALE SELEZIONE

Page 30: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

IMPIEGATICognome Nome Età Stipendio

Rossi Mario 25 2000000Neri Luca 40 3000000Verdi Nico 36 4500000Rossi Marco 40 3900000

)(400000030 IMPIEGATIStipendioEtà

Cognome Nome Età Stipendio

Rossi Mario 25 2000000Verdi Nico 36 4500000

ALGEBRA E CALCOLO RELAZIONALE SELEZIONE

Page 31: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

CITTADINICognome Nome CittàDi Nascita Residenza

Rossi Mario Roma MilanoNeri Luca Roma RomaVerdi Nico Firenze FirenzeRossi Marco Napoli Napoli

Cognome Nome CittàDi Nascita Residenza

Neri Luca Roma RomaVerdi Nico Firenze Firenze

)(Re CITTADINIsidenzacitaCittàDiNas

ALGEBRA E CALCOLO RELAZIONALE SELEZIONE

Page 32: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

PROIEZIONE PROIEZIONE (Vedi premessa) (Vedi premessa)

Dati una relazione r(X) e un sottoinsieme Y di X, la proiezione di r su Y Dati una relazione r(X) e un sottoinsieme Y di X, la proiezione di r su Y (indicata con ) è l’insieme di tuple su Y ottenute dalle tuple di r (indicata con ) è l’insieme di tuple su Y ottenute dalle tuple di r considerando solo i valori su Y: considerando solo i valori su Y:

•la proiezione decompone verticalmente le relazioni: il risultato della la proiezione decompone verticalmente le relazioni: il risultato della proiezione contiene in questo caso tante tuple quante l’operando, definite proiezione contiene in questo caso tante tuple quante l’operando, definite però solo su parte degli attributi (vedi esempio 1)però solo su parte degli attributi (vedi esempio 1)

•il risultato della proiezione può contenere un numero di tuple inferiore il risultato della proiezione può contenere un numero di tuple inferiore rispetto a quelle dell’operando, perché più tuple, avendo uguali valori su tutti rispetto a quelle dell’operando, perché più tuple, avendo uguali valori su tutti gli attributi della proiezione, danno lo stesso contributo alla proiezione stessa gli attributi della proiezione, danno lo stesso contributo alla proiezione stessa (vedi esempio 2) Essendo le relazioni definite come insiemi, non possono in esse (vedi esempio 2) Essendo le relazioni definite come insiemi, non possono in esse comparire più tuple uguali fra loro: i contributi uguali “collassano” in una sola comparire più tuple uguali fra loro: i contributi uguali “collassano” in una sola tupla. tupla.

)(rY

}|][{)( rtYtrY

ALGEBRA E CALCOLO RELAZIONALE

Premessa

Page 33: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Se Y è superchiave allora contiene lo stesso numero di tuple di Se Y è superchiave allora contiene lo stesso numero di tuple di rr se e se e solo se Y è superchiave per solo se Y è superchiave per rr. Infatti. Infatti

•se Y è superchiave, allora se Y è superchiave, allora rr non contiene tuple uguali su Y, e quindi ogni non contiene tuple uguali su Y, e quindi ogni tupla dà un contributo diverso alla proiezione; tupla dà un contributo diverso alla proiezione;

•se la proiezione ha tante tuple quante l’operando, allora ciascuna tupla di se la proiezione ha tante tuple quante l’operando, allora ciascuna tupla di rr contribuisce alla proiezione con valori diversi, e quindi contribuisce alla proiezione con valori diversi, e quindi rr non contiene coppie non contiene coppie di tuple uguali su Y: questa è proprio la definizione di superchiave.di tuple uguali su Y: questa è proprio la definizione di superchiave.

Per la relazione Impiegati, gli attributi Cognome e Nome formano una Per la relazione Impiegati, gli attributi Cognome e Nome formano una chiave ( e quindi una superchiave ), mentre Reparto e capo non formano una chiave ( e quindi una superchiave ), mentre Reparto e capo non formano una superchiave: questo giustifica il comportamento riguardo al numero delle superchiave: questo giustifica il comportamento riguardo al numero delle tuple.tuple.

)(rY

ALGEBRA E CALCOLO RELAZIONALE PROIEZIONE

Page 34: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

IMPIEGATICognome Nome Reparto Capo

Rossi Mario Vendite De rossiNeri Luca Vendite De rossiVerdi Mario Personale LupiRossi Marco Personale Lupi

)(,Nome IMPIEGATICognome

Esempio 1

Cognome Nome

Rossi MarioNeri LucaVerdi MarioRossi Marco

ALGEBRA E CALCOLO RELAZIONALE PROIEZIONE

Page 35: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

IMPIEGATICognome Nome Reparto Capo

Rossi Mario Vendite De rossiNeri Luca Vendite De rossiVerdi Mario Personale LupiRossi Marco Personale Lupi

Esempio 2

Reparto Capo

Vendite De rossi Personale Lupi

)(,Reparto IMPIEGATICapo

ALGEBRA E CALCOLO RELAZIONALE PROIEZIONE

Page 36: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

JOINJOIN

L’operatore di join è il più caratteristico dell’algebra relazionale, in quanto L’operatore di join è il più caratteristico dell’algebra relazionale, in quanto permette di correlare dati contenuti in relazioni diverse, confrontando i valori permette di correlare dati contenuti in relazioni diverse, confrontando i valori contenuti in esse e quindi utilizzando la caratteristica fondamentale del contenuti in esse e quindi utilizzando la caratteristica fondamentale del modello, quella di essere basato su valori.modello, quella di essere basato su valori.

Esistono due versioni dell’operatore il Esistono due versioni dell’operatore il join naturale ( ) e il ( ) e il theta join theta join (().).

•Il Il join naturale (r(r1 1 rr2 2 ) di r) di r11(X(X11) e r) e r22(X(X22) è una relazione definita su X) è una relazione definita su X11XX22

(cioè sull’unione degli insiemi X(cioè sull’unione degli insiemi X1 1 e Xe X22), come segue:), come segue:

rr1 1 rr22= = t su Xt su X11XX2 2 | esistono t| esistono t11 r r11 e t e t2 2 r r2 2 con t[X con t[X11]] = t= t11 e t[X e t[X22]= t]= t22

Più sinteticamente:Più sinteticamente:

rr1 1 rr22= = t su Xt su X11XX2 2 | t[X| t[X11]] rr11 e t[X e t[X22] ] r r2 2

ALGEBRA E CALCOLO RELAZIONALE

Page 37: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Possiamo esprimere l’operatore di in termini di proiezione e selezione:Possiamo esprimere l’operatore di in termini di proiezione e selezione:

rr1 1 rr22==

Il join-naturale è la selezione con un predicato particolare, che è del tipoIl join-naturale è la selezione con un predicato particolare, che è del tipo:

(il predicato dell’operatore di selezione applicato al prodotto cartesiano di (il predicato dell’operatore di selezione applicato al prodotto cartesiano di rr11 e r e r22) il predicato è un) il predicato è un and dei predicati di uguaglianza tra gli attributi dei predicati di uguaglianza tra gli attributi

comuni Acomuni Aii presi in r presi in r11 e in r e in r22, {A, {A11 … A … A22}=X}=X11 X X22 . Il risultato della selezione . Il risultato della selezione

viene proiettato su Xviene proiettato su X11 X X22. .

Esempi alla pagina successiva.Esempi alla pagina successiva.

))(( 21)..( 21121rr

iini ArArXX

)..( 211 iini ArAr

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 38: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Impiegato Reparto

Rossi venditeNeri produzioneBianchi produzione

Reparto Capo

produzione Morivendite Bruni

))(( 21)..( 21121rr

iini ArArXX

r1 r2

r1 r2 =

r1 r2

Esempio 1

Impiegato Reparto Reparto Capo

Rossi vendite produzione MoriRossi vendite vendite BruniNeri produzione produzione MoriNeri produzione vendite BruniBianchi produzione produzione MoriBianchi produzione vendite Bruni

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 39: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Impiegato Reparto Reparto Capo

Rossi vendite vendite BruniNeri produzione produzione MoriBianchi produzione produzione Mori

))(( 21)Reparto.Reparto.( 21rrrr

Impiegato Reparto Capo

Rossi vendite BruniNeri produzione MoriBianchi produzione Mori

(...)),(Reparto)Reparto,(Impiegato21 Caporr

Tabella finale

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 40: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Nell’esempio 1, abbiamo visto che ciascuna tupla di ciascuno degli operandi Nell’esempio 1, abbiamo visto che ciascuna tupla di ciascuno degli operandi contribuisce ad almeno una tupla del risultato (il join si dice contribuisce ad almeno una tupla del risultato (il join si dice completo):):

per ogni tupla tper ogni tupla t11 di r di r11, esiste una tupla t in (r, esiste una tupla t in (r1 1 rr22)) tale che t[X tale che t[X11]=t]=t11

(analogamente per r(analogamente per r22).).

Questa proprietà non è sempre verificata, perché richiede una Questa proprietà non è sempre verificata, perché richiede una corrispondenza fra le tuple delle due relazioni.corrispondenza fra le tuple delle due relazioni.

Possiamo avere esempi di join in cui alcune tuple degli operandi non Possiamo avere esempi di join in cui alcune tuple degli operandi non contribuiscono al risultato, perché l’altra relazione non contiene tuple con gli contribuiscono al risultato, perché l’altra relazione non contiene tuple con gli stessi valori sull’attributo comune. Tali tuple vengono chiamate “stessi valori sull’attributo comune. Tali tuple vengono chiamate “dangling” ” (dondolanti), (vedi esempio 1)(dondolanti), (vedi esempio 1)

Come caso limite, possiamo avere join vuoti, è possibile che nessuna delle Come caso limite, possiamo avere join vuoti, è possibile che nessuna delle tuple degli operandi sia combinabile, e allora il risultato del join è la relazione tuple degli operandi sia combinabile, e allora il risultato del join è la relazione vuota (vedi esempio 2, di join vuoto)vuota (vedi esempio 2, di join vuoto)

All’estremo opposto, è possibile che ciascuna delle tuple di ciascuno degli All’estremo opposto, è possibile che ciascuna delle tuple di ciascuno degli operandi sia combinabile con tutte le tuple dell’altro (esempio 3).operandi sia combinabile con tutte le tuple dell’altro (esempio 3).

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 41: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Esempio di join con tuple “dangling”

Impiegato Reparto

Rossi venditeNeri produzioneBianchi produzione

Reparto Capo

produzione Mori acquisti Bruni

r1 r2

r1 join-naturale r2 Impiegato Reparto Capo

Neri produzione MoriBianchi produzione Mori

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 42: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Esempio di join vuoto:

Impiegato Reparto

Rossi venditeNeri produzioneBianchi produzione

Reparto Capo

concorsi Mori acquisti Bruni

r1r2

Impiegato Reparto Capo

r1 r2

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 43: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Esempio di join con |r1|×|r2| tuple:

Impiegato Progetto

Rossi ANeri A

Bianchi A

Progetto Capo

A MoriA Bruni

r1 r2

Impiegato Progetto Capo

Rossi A MoriRossi A BruniNeri A MoriNeri A Bruni

Bianchi A MoriBianchi A Bruni

r1 r2

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 44: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Esempio di join sulla base di valori della chiave di una delle relazioni coinvolte.Esempio di join sulla base di valori della chiave di una delle relazioni coinvolte.In questo caso è definito, fra gli attributi coinvolti, un vincolo di riferimento.In questo caso è definito, fra gli attributi coinvolti, un vincolo di riferimento.

Codice Data Agente Articolo Provincia Numero

143256 25/10/92 567 44 RM 4E5432987554 26/10/92 456 34 RM 4E5432987554 26/10/92 456 34 RM 2F76432630876 15/10/92 456 53 MI 2F7643539856 12/10/92 567 44 MI 2F7643

Provincia Numero Proprietario Indirizzo

RM 2F7643 Verdi Piero Via Tigli

RM 1A2396 Verdi Piero Via TigliRM 4E5432 Bini Luca Via AceriMI 2F7643 Luci Gino Via Aceri

INFRAZIONIINFRAZIONI

AUTOAUTO

INFRAZIONI INFRAZIONI JOIN-NATURALE JOIN-NATURALE AUTOAUTOCodice Data Agente Articolo Provincia Numero Proprietario Indirizzo

143256 25/10/92 567 44 RM 4E5432 Bini Luca Via Aceri987554 26/10/92 456 34 RM 4E5432 Bini Luca Via Aceri987554 26/10/92 456 34 RM 2F76432 Verdi Piero Via Tigli630876 15/10/92 456 53 MI 2F7643 Luci Gino Via Aceri539856 12/10/92 567 44 MI 2F7643 Luci Gino Via Aceri

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 45: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Ricapitolando possiamo dire anche sulla base degli esempi che il join di rRicapitolando possiamo dire anche sulla base degli esempi che il join di r1 1 e e

rr22 contiene un numero di tuple compreso fra 0 e |r contiene un numero di tuple compreso fra 0 e |r11|×|r|×|r22| . Inoltre:| . Inoltre:

•se il join di rse il join di r11 e r e r22 è completo, allora contiene almeno un numero di tuple è completo, allora contiene almeno un numero di tuple

pari al massimo fra |rpari al massimo fra |r11| e |r| e |r22|;|;

•se Xse X11XX22 contiene una chiave per r contiene una chiave per r22, allora il join di r, allora il join di r11(X(X11) e r) e r22(X(X22) contiene ) contiene

al più |ral più |r11| tuple;| tuple;

•se Xse X11XX22 contiene una chiave per r contiene una chiave per r22 sussiste il vincolo di riferimento fra sussiste il vincolo di riferimento fra

XX11XX22 (o un suo sottoinsieme) in r (o un suo sottoinsieme) in r11 e la chiave di r e la chiave di r22, allora il join di r, allora il join di r11(X(X11) e ) e

rr22(X(X22) contiene esattamente |r) contiene esattamente |r11| tuple.| tuple.

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 46: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Osservazioni sul join naturale

Consideriamo i casi estremi:quello in cui i due schemi coincidono e quello in cui Consideriamo i casi estremi:quello in cui i due schemi coincidono e quello in cui sono disgiunti.sono disgiunti.

•XX11=X=X22 , il join coincide con l’intersezione: , il join coincide con l’intersezione:

rr1 1 rr22= r= r11(X(X11) ) r r22(X(X22))

la definizione di join naturale richiede che il risultato sia definito sull’unione dei la definizione di join naturale richiede che il risultato sia definito sull’unione dei due insiemi di attributi, e che contenga le tuple t tali che t[Xdue insiemi di attributi, e che contenga le tuple t tali che t[X11]]rr11 e t[X e t[X22] ] rr22; ;

poiché l’unione di Xpoiché l’unione di X11 e X e X22 è ancora pari a X è ancora pari a X11 e quindi t è definita su X e quindi t è definita su X11: la : la

definizione richiede quindi che t definizione richiede quindi che t rr11 e t e t rr22 e coincide quindi con la definizione di e coincide quindi con la definizione di

intersezione.intersezione.

•XX11XX22==, i due insiemi sono disgiunti., i due insiemi sono disgiunti.

Il risultato è sempre definito sull’unione XIl risultato è sempre definito sull’unione X11XX22, e ciascuna tupla deriva sempre da , e ciascuna tupla deriva sempre da

due tuple, una per ciascuno degli operandi, poiché tali tuple non hanno attributi in due tuple, una per ciascuno degli operandi, poiché tali tuple non hanno attributi in comune, non viene richiesta ad esse nessuna condizione per partecipare insieme al comune, non viene richiesta ad esse nessuna condizione per partecipare insieme al join:la condizione informale, cioè che le due tuple debbono avere gli stessi join:la condizione informale, cioè che le due tuple debbono avere gli stessi

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 47: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

valori sugli attributi comuni, degenera in una condizione sempre verificata. valori sugli attributi comuni, degenera in una condizione sempre verificata. Il risultato del join contiene le tuple ottenute combinando, in tutti i modi Il risultato del join contiene le tuple ottenute combinando, in tutti i modi possibili, le tuple degli operandi. In questo caso particolare il join diventa un possibili, le tuple degli operandi. In questo caso particolare il join diventa un prodotto cartesiano. .

Potremmo dire che il prodotto cartesiano è un operatore definito (con la Potremmo dire che il prodotto cartesiano è un operatore definito (con la stessa definizione data per il join naturale) su relazioni che non hanno stessa definizione data per il join naturale) su relazioni che non hanno attributi in comune.attributi in comune.

Un prodotto cartesiano ha di solito ben poco utilità, in quanto concatena Un prodotto cartesiano ha di solito ben poco utilità, in quanto concatena tuple non necessariamente correlate dal punto di vista semantico.tuple non necessariamente correlate dal punto di vista semantico.

L’esempio successivo mostra un prodotto cartesiano, il cui risultato L’esempio successivo mostra un prodotto cartesiano, il cui risultato contiene un numero di tuple pari al prodotto delle cardinalità degli operandi.contiene un numero di tuple pari al prodotto delle cardinalità degli operandi.

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 48: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

ImpiegatiImpiegato Progetto

Rossi ANeri ANeri B

Progetticodice Nome

A VenereB Marte

Impiegato Progetto codice Nome

Rossi A A VenereNeri A A VenereNeri B A Venere

Rossi A B Marte

Impiegati Progetti

Il prodotto cartesiano viene spesso seguito da una selezione, che centra l’attenzione suIl prodotto cartesiano viene spesso seguito da una selezione, che centra l’attenzione sutuple correlate secondo le esigenze.tuple correlate secondo le esigenze.Per questa ragione viene spesso definito un operatore derivato, il Per questa ragione viene spesso definito un operatore derivato, il theta-jointheta-join, come , come prodotto cartesiano seguito da una selezione.prodotto cartesiano seguito da una selezione.

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 49: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

THETA JOINTHETA JOIN ( )

•L’operatore di theta-join è definito come segue:L’operatore di theta-join è definito come segue:

dove F è una formula proposizionale utilizzabile in una selezione e le dove F è una formula proposizionale utilizzabile in una selezione e le relazioni rrelazioni r11 e r e r22 non hanno attributi in comune. non hanno attributi in comune.

Nell’esempio precedente si può esprimere la seguente interrogazione:Nell’esempio precedente si può esprimere la seguente interrogazione:

)( 2121 rrrr FF

21 rrF

ALGEBRA E CALCOLO RELAZIONALE JOIN

ProgettiImpiegatiProgetto Codice

Page 50: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Impiegato Progetto codice Nome

Rossi A A VenereNeri A A VenereNeri B B Marte

Impiegato Progetto

Rossi ANeri A

Bianchi A

Progetto Capo

A MoriA Bruni

Impiegati Progetti

)Progetti(ImpiegatiProgettiImpiegati ProgettoProgetto

CodiceCodice

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 51: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Un theta join in cui la condizione di selezione F sia una congiunzione di Un theta join in cui la condizione di selezione F sia una congiunzione di atomi di uguaglianza, con un attributo della prima relazione e uno della atomi di uguaglianza, con un attributo della prima relazione e uno della seconda, viene chiamato seconda, viene chiamato equi-join. equi-join. La figura precedente è ottenuta per mezzo La figura precedente è ottenuta per mezzo di un equi join.di un equi join.

Dal punto di vista pratico il theta-join e ancor più l’equi-join hanno una Dal punto di vista pratico il theta-join e ancor più l’equi-join hanno una grande importanza, in quanto la maggior parte dei sistemi di basi di dati grande importanza, in quanto la maggior parte dei sistemi di basi di dati effettivamente esistenti non utilizzano i nomi di attributo per correlare le effettivamente esistenti non utilizzano i nomi di attributo per correlare le relazioni, e quindi non utilizzano il natural-join ma l’equi-join e il theta-join.relazioni, e quindi non utilizzano il natural-join ma l’equi-join e il theta-join.

Notiamo che il natural join può essere simulato per mezzo della Notiamo che il natural join può essere simulato per mezzo della ridenominazione, dell’equi-join e della proiezione.ridenominazione, dell’equi-join e della proiezione.

Esempio date due relazioni rEsempio date due relazioni r11(ABC) e r(ABC) e r22(BCD), il join naturale di r(BCD), il join naturale di r11 ed r ed r22

può essere espresso per mezzo degli altri operatori, in tre passi:può essere espresso per mezzo degli altri operatori, in tre passi:

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 52: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

• Ridenominando gli attributi in modo da ottenere relazioni su schemi Ridenominando gli attributi in modo da ottenere relazioni su schemi disgiunti:disgiunti:

• effettuando l’equi-join, con condizioni di uguaglianza sugli attributi effettuando l’equi-join, con condizioni di uguaglianza sugli attributi corrispondenti: corrispondenti:

• concludendo con una proiezione che elimina gli attributi “doppioni”, che concludendo con una proiezione che elimina gli attributi “doppioni”, che presentano valori identici a quelli di altri attributi:presentano valori identici a quelli di altri attributi:

)( 2'' rBCCB

)( 2''''

1 rr BCCBCCBB

)))((( 2''''

1 rr BCCBCCBB

ABCD

ALGEBRA E CALCOLO RELAZIONALE JOIN

Page 53: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

DIVISIONE ( )DIVISIONE ( )

L’operatore di divisione lo si può applicare sulle relazioni s ed r se e solo se L’operatore di divisione lo si può applicare sulle relazioni s ed r se e solo se lo schema di relazione su cui è definito s è contenuto nello schema di relazione lo schema di relazione su cui è definito s è contenuto nello schema di relazione su cui è definito r.su cui è definito r.

SianoSiano r r ed ed s s due relazioni definite su S ed R, e sia S due relazioni definite su S ed R, e sia SR, allora avremo che:R, allora avremo che:

]))([()()()( rsrrSsRr SRSRSR

RS

ALGEBRA E CALCOLO RELAZIONALE

Page 54: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

Impiegati

Impiegato Nome Progetto

Rossi ANeri ANeri BVerdi BVerdi ANeri CVerdi C

Progetti

Nome Progetto

ABC

ProgettiImpiegati Impiegato

NeriVerdi

Verificare tramite la definizione.Verificare tramite la definizione.

Esempio: vogliamo tutti gli impiegati che partecipano ai progetti A, B e C

ALGEBRA E CALCOLO RELAZIONALE DIVISIONE

Page 55: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

]Impiegati)Progetti)(Impiegati[()(Impiegati ImpiegatiImpiegatiImpiegati

Impiegato

RossiNeriVerdi

)(ImpiegatiImpiegato

)(ImpiegatoImpiegato × Progetti-Impiegati

Impiegato Nome Progetto

Rossi A

Impiegato Nome Progetto

Rossi ARossi BRossi CNeri ANeri BNeri CVerdi AVerdi BVerdi C

)(ImpiegatiImpiegato × Progetti

I

ALGEBRA E CALCOLO RELAZIONALE DIVISIONE

Page 56: ALGEBRA E CALCOLO RELAZIONALE OPERATORI DELL’ALGEBRA RELAZIONALE UNIONE, INTERSEZIONE, DIFFERENZA RIDENOMINAZIONE LOGICA PROPOSIZIONALE SELEZIONEPROIEZIONE.

]Impiegati)Progetti)(Impiegati[( ImpiegatoImpiegato

]Impiegati)Progetti)(Impiegati[()(Impiegati ImpiegatoImpiegatoImpiegato

Impiegato

Rossi

Impiegato

RossiNeriVerdi

Impiegato

Rossi__

Impiegato

NeriVerdi

ProgettiImpiegati

ALGEBRA E CALCOLO RELAZIONALE DIVISIONE