Esercizi di Algebra Relazionale

Algebra relazionale: riepilogo

Proiezione

(notazione π) Operatore unario per estrarre colonne da una relazione: π(lista_attributi)(R). Lo schema del risultato contiene i soli attributi contenuti in lista_attributi. La relazione risultato contiene le tuple ristrette agli attributi nella lista.

Selezione

(notazione σ) Operatore unario per selezionare righe da una relazione: σ_condizione(R). La condizione di selezione è un'espressione booleana del tipo: attributo OP costante oppure attributo1 OP attributo2, dove OP = {<, <=, >, >=, =, ≠}. È espandibile con i connettivi logici (AND, OR). Lo schema del risultato è identico allo schema di R. La relazione risultato contiene le tuple che soddisfano la condizione specificata.

Unione

(notazione ∪) L'unione di due relazioni R1 e R2 contiene tutte le tuple (prese una sola volta) presenti in R1, in R2 oppure in entrambe. Lo schema del risultato è identico allo schema di R1.

Intersezione

(notazione ∩) L'intersezione di due relazioni R1 e R2 contiene tutte le tuple (prese una sola volta) presenti contemporaneamente sia in R1 che in R2. Lo schema del risultato è identico allo schema di R1.

Differenza

(notazione -) La differenza tra due relazioni R1 e R2 contiene tutte le tuple presenti in R1 ma non in R2. Lo schema del risultato è identico allo schema di R1.

Ridenominazione

(notazione ρ) ρ(y←x)(R) oppure ρ(R(F),E). Dove: E è un'espressione arbitraria di algebra relazionale, R è un'istanza di relazione che rappresenta il risultato della esecuzione di E (contiene le stesse tuple di E, ma con alcuni campi rinominati) detta "ridenominazione", F è una lista nella forma: Nuovo nome Vecchio nome, Nuovo nome Posizione.

Prodotto cartesiano

(notazione ×) Un'istanza di relazione il cui schema contiene tutti i campi di R1 seguiti da tutti i campi di R2. Restituisce (nell'ordine originale) i campi di R1 seguiti da tutti i campi di R2 (nell'ordine originale). ATTENZIONE: Se due relazioni hanno degli attributi con nomi in comune, i campi corrispondenti nel prodotto cartesiano non hanno nome (per convenzione) e ci si può riferire a loro solo attraverso la posizione che occupano nello schema. Si può generare un conflitto di nomi che si risolve con la ridenominazione.

Join condizionale o Theta-join

(notazione ⋈_c) Il JOIN condizionale tra R1 e R2 è una SELECT applicata sul prodotto cartesiano tra R1 e R2, ovvero ⋈_c ≡ σ_c(R1 × R2).

Equi-join

(notazione ⋈_c) L'EQUI JOIN tra R1 e R2 è un JOIN in cui la condizione di JOIN c è composta solo da uguaglianze (eventualmente connesse da AND). Lo schema del risultato di un EQUI-JOIN contiene tutti gli attributi di R1 e gli attributi di R2 che non compaiono nella condizione di JOIN. NOTA: Nel risultato gli attributi della condizione compaiono una sola volta.

Natural join

(notazione ⋈) È un EQUI-JOIN in cui le uguaglianze sono specificate su tutti gli attributi aventi lo stesso nome in R1 e R2. Le tuple del risultato sono ottenute combinando le tuple degli operandi con valori uguali sugli attributi comuni.

Proprietà del NATURAL JOIN: Il join è commutativo e associativo. Se le due relazioni non hanno attributi in comune, il NATURAL JOIN si riduce ad essere un semplice prodotto cartesiano. Una buona tecnica per ricavare le espressioni dell'algebra relazionale è quella di procedere per passi, ricordando che i risultati di interrogazioni intermedie sono sempre relazioni.

Viste

In algebra relazionale è possibile definire delle viste, che altro non sono che espressioni a cui viene assegnato un nome. È quindi possibile utilizzare le viste all'interno di altre espressioni, il che semplifica la scrittura di espressioni complesse. La sintassi è: V = E, dove V è il nome della vista. NOTA: L'utilizzo di viste non influisce sull'efficienza delle interrogazioni.

Minimo e massimo

Minimo/massimo assoluto

Dato lo schema relazionale R(A,B) trovare il minimo/massimo B in R. Supponiamo di determinare il minimo: ρ(A1,B1←A,B)(R) - (R ⋈ (R _B>B1)). Nella seconda parte vengono trovati tutti quei valori che non sono il minimo. Per far questo viene fatto un join tra la relazione R e se stessa, con però tutti gli attributi rinominati. La condizione di join dice che ogni attributo B deve essere maggiore degli stessi attributi rinominati. In questo modo vengono tenute tutte le tuple tranne quella in cui l'attributo B assume il valore minore. Quindi per il principio di complementarietà sottraendo dall'insieme iniziale, l'insieme delle tuple dove B non è il minimo, otteniamo proprio il valore minimo che cercavamo.

Minimo/massimo relativo

Dato lo schema relazionale R(A,B) trovare per ogni A il minimo/massimo B in R. Supponiamo di determinare il massimo: ρ(A1,B1←A,B)(R) - (R ⋈ _{A=A1 AND B). È molto simile al massimo assoluto. Il predicato di join in questo caso seleziona tutti i valori minimi di B per ogni attributo A.}

Ottimizzazione algebrica

L'ottimizzazione algebrica ha lo scopo di trovare un'espressione equivalente all'espressione data che possa essere eseguita in modo più efficiente. Il costo dell'esecuzione di un'interrogazione può essere valutato in termini delle dimensioni dei risultati intermedi. In presenza di alternative equivalenti viene scelta l'espressione con costo minore. Le trasformazioni di equivalenza sono operazioni che sostituiscono un'espressione con un'altra a essa equivalente, interessanti se riducono il costo.