Algebra relazionale

Da Wikipedia, l'enciclopedia libera.

L'algebra relazionale e il collegato calcolo relazionale fanno parte dell'insieme di linguaggi che permettono di esaminare le query (interrogazioni) da effettuare nell'ambito della gestione di un database. L'algebra relazione è un linguaggio procedurale cioè una descrizione della procedura da attuare per ottenere il risultato. Il calcolo relazionale invece è un linguaggio dichiarativo, che permette di descrivere le proprietà del risultato invece che il modo per ottenerlo. Il risultato può essere calcolato sia sulle tuple (i singoli record che compongono la tabella) che sui domini (campo di applicazione della tabella).

[modifica] Algebra Relazionale

L'algebra relazionale è un linguaggio di interrogazione procedurale ed è definita da operatori di base. L’applicazione di ognuno di questi operatori algebrici alle relazioni produce sempre come risultato una relazione. La combinazione degli stessi permette di formulare interrogazioni complesse. Nella definizione dell’algebra relazionale il nome degli attributi e l’ordinamento delle tuple non è rilevante, inoltre si assume che tutte le relazioni in gioco siano insiemi finiti, per cui per esempio non è consentita l’operazione algebrica di complemento dato che -R può denotare un insieme infinito (cioè l’insieme delle tuple che non sono in R).

[modifica] Operatori dell'algebra relazionale

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

Operatori fondamentali (di base):

operatori unari di Selezione
operatori unari di Proiezione
operatori unari di Ridenominazione
operatori binari di Prodotto Cartesiano
operatori binari di Unione
operatori binari di Differenza

Operatori derivati (da quelli di base):

operatore insiemistico binario di Intersezione
operatore di join in varie forme (theta-join, natural-join, etc.)
operatore di divisione

Indichiamo con r (R), la relazione r definita sullo schema R. R è un insieme di attributi.

[modifica] Unione, Intersezione, Differenza

Dato che le relazioni sono degli insiemi ha senso definire su di esse gli operatori insiemistici tradizionali come unione, differenza e intersezione.L'unico vincolo è quello di avere delle tuple omogenee cioè definite sugli stessi attributi.

l'unione di due relazioni r1 e r2 definite sullo stesso insieme di attributi X è indicata con $r1 \cup r2$ ed è una relazione ancora su X contenente le tuple che appartengono a r1 oppure a r2.Unione (insiemistica)
la differenza di r1(x) e r2(x( è indicata come $r 1 - r 2$ ed è una relazion su X contenente le tuple che appartengono a r1 e non appartengono a r2.
l'intersezione di r1(X) e r2(X) è indicata con $r1 \cap r2$ ed è una relazione su X contenente le tuple che appartengono sia a r1 che r2.

[modifica] Ridenominazione

L’operatore di ridenominazione, r, modifica lo schema di una relazione, cambiando i nomi di uno o più attributi. Quest'operazione è molto utile per ottenere delle tuple omogenee quando non lo sono anche se il campo semantico di applicazione della query lo è. Sia r una relazione definita sull'insieme di attributi X e sia Y un (altro) insieme di attributi con ordinamento per gli attributi in X e un ordinamento per quelli in Y. Allora la ridenominazione $\rho_{B1,B2...Bk\leftarrow A1,A2...Ak} (r)$ contiene una tupla t' per ciascuna tupla t in r, definita come segue: t' è una tupla su Y e $t' [B i] = t [A i]$ , per i = 1,..., n. La definizione conferma che ciò che cambia sono i nomi degli attributi, mentre i valori rimangono inalterati e vengono associati ai nuovi attributi.

[modifica] Logica Proposizionale

[modifica] Selezione

È un operatore unario e restituisce come risultato una relazione.

Chiamiamo formula relazionale un'espressione che mette in relazione attributi per mezzo degli operatori =,!=,<,>,<=,>=. Sia r(X) una relazione sull'insieme di attributi X, e F una formula relazionale. La selezione di r rispetto a F, denotata da "S" F(r), é una relazione definita su X, contenente le n-tuple di r che rendono F vera, cioè la selezione da una tabella non è altro che l'insieme di righe che appartengono alla tabella e che soddisfano una serie di condizioni indicate nella selezione stessa.

[modifica] Proiezione

L'operatore di proiezione effettua una modifica al grado della relazione a cui si applica. Il simbolo è $Π$ a pedice del quale viene indicata la lista degli attributi che costituiscono la nuova relazione, tali attributi sono un sottoinsieme degli attributi della relazione originale. La proiezione $\Pi _{\left (A_1, A_2, ..., A_n\right )}(r)$ produce una relazione $r p$ il cui schema è l'insieme degli attributi $A n$ e la cui istanza è la restrizione delle tuple di $r$ sugli attributi $A n$ .

Formalmente la proiezione elimina le tuple che dovessero risultare duplicate nella relazione finale, infatti istanze con presenza di tuple duplicate non sono ammesse dal modello relazionale. Questo comportamento può però non essere rispettato nelle implementazioni reali. In SQL per esempio tale bisogna esplicitamente evidenziare la volontà di eliminare le tuple duplicate.

[modifica] Join

Il join è un' operazione binaria che si applica a due relazioni $R (A 1, A 2,..., A m)$ ed $S (B 1, B 2,..., B n)$ . La funzione del join è unire tuple logicamente collegate delle due relazioni in un'unica tupla. La relazione risultante $R j (A 1, A 2,..., A m, B 1, B 2,..., B n)$ ha come schema l'insieme degli attributi di R ed S, mentre l'estensione viene espressa come il prodotto cartesiano di R ed S seguito dalla selezione delle tuple che soddisfano la condizione di join. L'operatore di join non è un operatore elementare dell'algebra relazionale ed è definito nel seguente modo: $\bowtie_{F \left( R,S \right)} \left( R,S \right )= \sigma _{F \left(R,S \right)} \left( R \times S \right)$ . Per il significato e la sintassi della condizione di selezione $F (R, S)$ vedere l'operatore di selezione.

Nel caso che il criterio di selezione delle tuple sia determinato da un operatore di confronto (<,>,=,ecc.) si puo' parlare di theta-join. Un caso particolare del theta-join è l'equi-join, in cui si applica l'operatore di uguaglianza.

Nel caso si voglia eseguire un equi-join su attributi con lo stesso nome, si puo' ricorrere a un'operazione particolare chiamata natural-join. In presenza di due attributi uguali, viene rinominato l'attributo comune in una delle due relazioni, viene eseguito l'equi-join rispetto ai due attributi, e viene eliminata una delle colonne che risultano uguali. Nel natural-join, quindi, la condizione di join è implicita, e lo schema della relazione risultante è l'insieme degli attributi di R ed S meno uno degli attributi uguali.

[modifica] Interrogazioni

[modifica] Equivalenza di espressioni algebriche

[modifica] Algebra con valori nulli

Un concetto importante in algebra relazionale è quello dei valori nulli (NULL), utilizzati per rappresentare valori di attributi sconosciuti oppure non applicabili.

I valori nulli possono essere interpretati in tre modi:

Valore sconosciuto: non si conosce il valore per quell'attributo

Valore non disponibile: non si vuole che l'attributo venga registrato

Attributo non applicabile: l'attributo non puo' essere applicato all'entità

Spesso è difficile stabilire a quale categoria un valore nullo appartiene, puo' capitare che possa rappresentare anche tutti e tre i casi! Nelle basi di dati, quindi, ciascun valore NULL è considerato diverso. Quando in un'operazione di confronto viene coinvolto un valore NULL, il risultato viene considerato UNKNOWN (sconosciuto); per questo motivo, in algebra relazionale si utilizza una logica a tre valori (TRUE, FALSE, UNKNOWN) al posto della logica standard con TRUE e FALSE. Se si esegue un'interrogazione al database, la regola generale è che vengono prelevate solo le tuple in cui la condizione di selezione è TRUE, mentre vengono scartate quelle con valore FALSE o UNKNOWN.

In SQL, i valori nulli vengono trattati in modo particolare: per controllare se un dato valore è NULL, invece di usare il simbolo di uguaglianza (=) o disuguaglianza (<>), si utilizzano le keywords IS e IS NOT, perché l'operatore di uguaglianza coi valori nulli non ha senso.

Le tavole di verità corrispondenti alle tre principali operazioni sono

NOT
V	F
U	U
F	V

OR	V	U	F
V	V	V	V
U	V	U	U
F	V	U	F

AND	V	U	F
V	V	U	F
U	U	U	F
F	F	F	F

[modifica] Viste

[modifica] Datalog

Datalog è un linguaggio di interrogazioni per basi di dati che ha riscosso un notevole interesse dalla comunità scientifica dalla metà degli anni '80.

Esso discende direttamente da Prolog del quale è la semplificazione dedicata ai DB relazionali; infatti è basato anch'esso su regole di deduzione ma non permette l'utilizzo di simboli di funzione né un modello di valutazione non procedurale (SLD resolution).