Algebra relazionale

Note

L'algebra relazionale è un linguaggio formale di interrogazione delle basi dei dati. In questo linguaggio esiste un insieme minimo di 5 operazioni che danno l'intero potere espressivo del linguaggio, dove gli operandi sono le tabelle. Le espressioni algebriche esprimono interrogazioni in modo formale, e consentono di estrarre informazioni dai dati.

L'operazione di selezione , e ci restituisce una tabella con lo stesso schema di , e con istanze le -uple di che soddisfano il predicato di selezione. Il predicato di selezione permette di usare operazioni booleane (), comparatori (), e termini (costanti e attributi).

L'operazione di proiezione , che restituisce una tabella con schema gli attributi selezionati, e con istanza la restrizione delle -uple sugli attributi selezionati. L'operatore restituisce tutte le colonne. Formalmente la proiezione elimina i duplicati, tuttavia informalmente l'eliminazione va richiesta esplicitamente.

Gli operatori di unione e intersezione restituiscono rispettivamente l'unione e intersezione delle -uple delle tabelle specificate. È possibile solo se i domini delle tabelle sono ordinatamente dello stesso tipo. Formalmente l'intersezione è ricavabile con la formula: L'operatore di differenza restituisce la differenza delle -uple delle tabelle specificate, rimuove quindi le righe della prima tabella in comune con la seconda.

Il prodotto cartesiano restituisce una tabella priva di nome con schema gli attributi delle due tabelle, e con istanza tutte le possibili coppie di -uple delle due tabelle.

L'operazione di join è equivalente all'espressione: Produce quindi una tabella con schema concatenazione degli schemi di e , e con istanze le -uple ottenute concatenando le tuple di e che soddisfano il predicato. Dentro l'operazione di join si possono utilizzare tutti i predicati booleani.

Si parla di equi-join quando si fanno solo confronti di uguaglianza, e di join naturale quando un equi-join si fa di tutti gli attributi omonimi, in questo caso si omette il predicato e si elimina la colonna ripetuta.

Nell'operazione di semi-join è equivalente alla seguente espressione: Anche in questo caso esiste il semi-join naturale.

Assegnamento e ridenominazione

L'assegnamento è un operazione utilizzata per dare un nome al risultato di un'espressione algebrica, non fa parte delle operazioni algebriche: La ridenominazione permette di generare una tabella in cui un attributo ha nomi diversi, anche questa non fa parte delle operazioni algebriche:

Rappresentazione delle espressioni tramite alberi

Ogni espressione dell'algebra relazionale può essere rappresentata in modo grafico da un albero. Rappresenta l'ordine di valutazione degli operandi, dove ogni operatore corrisponde a un nodo.

Ottimizzazione di query

Esistono delle equivalenze tra query, tra cui:

  • Eliminazione dei prodotti cartesiani. Se è una congiunzione di predicati del tipo , allora:
  • Push della selezione rispetto al join. Se è un predicato che si applica ai soli attributi di , allora:
  • Push della proiezione rispetto al join. Definendo e come gli attributi di e necessari a valutare , e definendo e , allora:
  • Idempotenza della selezione. Si ha che per :
  • Idempotenza della proiezione. Si ha che per e :
  • Push della selezione rispetto all'unione. Si ha che:
  • Push della selezione rispetto alla differenza. Si ha che:
  • Push della proiezione rispetto all'unione. Si ha che:
  • Commutazione di join e unione. Si ha che:

Oltre a queste esistono delle formule come: Informalmente per ottimizzare algebricamente si minimizza la dimensione dei risultati intermedi utilizzando dove possibile le trasformazioni di push, e utilizzando le trasformazioni di idempotenza per generare nuove selezioni e proiezioni.