Algebra relazionale per l'ottimizzazione delle query

Quando viene inserita una query, viene inizialmente scansionata, analizzata e convalidata. Viene quindi creata una rappresentazione interna della query, ad esempio un albero della query o un grafico della query. Quindi vengono ideate strategie di esecuzione alternative per recuperare i risultati dalle tabelle del database. Il processo di scelta della strategia di esecuzione più appropriata per l'elaborazione delle query è chiamato ottimizzazione delle query.

Problemi di ottimizzazione delle query in DDBMS

In DDBMS, l'ottimizzazione delle query è un'attività cruciale. La complessità è elevata poiché il numero di strategie alternative può aumentare in modo esponenziale a causa dei seguenti fattori:

La presenza di una serie di frammenti.
Distribuzione dei frammenti o delle tabelle su vari siti.
La velocità dei collegamenti di comunicazione.
Disparità nelle capacità di elaborazione locale.

Quindi, in un sistema distribuito, l'obiettivo è spesso trovare una buona strategia di esecuzione per l'elaborazione delle query piuttosto che la migliore. Il tempo per eseguire una query è la somma di quanto segue:

È ora di comunicare le query ai database.
È ora di eseguire frammenti di query locali.
È ora di raccogliere dati da diversi siti.
È ora di visualizzare i risultati nell'applicazione.

Elaborazione query

L'elaborazione della query è un insieme di tutte le attività a partire dal posizionamento della query fino alla visualizzazione dei risultati della query. I passaggi sono come mostrato nel diagramma seguente:

Algebra relazionale

L'algebra relazionale definisce l'insieme di base delle operazioni del modello di database relazionale. Una sequenza di operazioni di algebra relazionale forma un'espressione di algebra relazionale. Il risultato di questa espressione rappresenta il risultato di una query sul database.

Le operazioni di base sono:

Projection
Selection
Union
Intersection
Minus
Join

Proiezione

L'operazione di proiezione visualizza un sottoinsieme di campi di una tabella. Questo dà una partizione verticale della tabella.

Syntax in Relational Algebra

$$ \ pi _ {<{AttributeList}>} {(<{Nome tabella}>)} $$

Ad esempio, consideriamo il seguente database degli studenti:

STUDENT
Roll_No	Name	Course	Semester	Gender
2	Amit Prasad	BCA	1	Maschio
4	Varsha Tiwari	BCA	1	Femmina
5	Asif Ali	MCA	2	Maschio
6	Joe Wallace	MCA	1	Maschio
8	Shivani Iyengar	BCA	1	Femmina

Se vogliamo visualizzare i nomi e i corsi di tutti gli studenti, useremo la seguente espressione di algebra relazionale:

$$ \ pi_ {Name, Course} {(STUDENT)} $$

Selezione

L'operazione di selezione mostra un sottoinsieme di tuple di una tabella che soddisfa determinate condizioni. Questo dà una partizione orizzontale della tabella.

Syntax in Relational Algebra

$$ \ sigma _ {<{Condizioni}>} {(<{Nome tabella}>)} $$

Ad esempio, nella tabella Studenti, se vogliamo visualizzare i dettagli di tutti gli studenti che hanno optato per il corso MCA, utilizzeremo la seguente espressione di algebra relazionale:

$$ \ sigma_ {Course} = {\ small "BCA"} ^ {(STUDENT)} $$

Combinazione di operazioni di proiezione e selezione

Per la maggior parte delle query, abbiamo bisogno di una combinazione di operazioni di proiezione e selezione. Ci sono due modi per scrivere queste espressioni:

Utilizzo della sequenza di operazioni di proiezione e selezione.
Utilizzo dell'operazione di rinomina per generare risultati intermedi.

Ad esempio, per visualizzare i nomi di tutte le studentesse del corso BCA -

Espressione di algebra relazionale utilizzando sequenze di operazioni di proiezione e selezione

$$ \ pi_ {Name} (\ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)}) $$

Espressione di algebra relazionale che utilizza l'operazione di rinomina per generare risultati intermedi

$$ FemaleBCAStudent \ leftarrow \ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)} $$

$$ Risultato \ leftarrow \ pi_ {Name} {(FemaleBCAStudent)} $$

Unione

Se P è il risultato di un'operazione e Q è il risultato di un'altra operazione, l'unione di P e Q ($ p \ cup Q $) è l'insieme di tutte le tuple che è in P o in Q o in entrambe senza duplicati .

Ad esempio, per visualizzare tutti gli studenti che sono nel semestre 1 o nel corso BCA -

$$ Sem1Student \ leftarrow \ sigma_ {Semester = 1} {(STUDENT)} $$

$$ BCAStudent \ leftarrow \ sigma_ {Course = \ small "BCA"} {(STUDENT)} $$

$$ Risultato \ leftarrow Sem1Student \ cup BCAStudent $$

Intersezione

Se P è il risultato di un'operazione e Q è il risultato di un'altra operazione, l'intersezione di P e Q ($ p \ cap Q $) è l'insieme di tutte le tuple che sono in P e Q entrambi.

Ad esempio, dati i seguenti due schemi:

EMPLOYEE

EmpID	Nome	Città	Dipartimento	Stipendio

PROJECT

PId	Città	Dipartimento	Stato

Per visualizzare i nomi di tutte le città in cui si trova un progetto e anche un dipendente risiede:

$$ CityEmp \ leftarrow \ pi_ {City} {(EMPLOYEE)} $$

$$ CityProject \ leftarrow \ pi_ {City} {(PROJECT)} $$

$$ Risultato \ leftarrow CityEmp \ cap CityProject $$

Meno

Se P è il risultato di un'operazione e Q è il risultato di un'altra operazione, P - Q è l'insieme di tutte le tuple che sono in P e non in Q.

Ad esempio, per elencare tutti i reparti che non hanno un progetto in corso (progetti con stato = in corso) -

$$ AllDept \ leftarrow \ pi_ {Department} {(EMPLOYEE)} $$

$$ ProjectDept \ leftarrow \ pi_ {Department} (\ sigma_ {Status = \ small "going"} {(PROJECT)}) $$

$$ Risultato \ leftarrow AllDept - ProjectDept $$

Aderire

L'operazione di join combina le tuple correlate di due diverse tabelle (risultati di query) in una singola tabella.

Ad esempio, considera due schemi, Cliente e Filiale in un database bancario come segue:

CUSTOMER

CustID	AccNo	TypeOfAc	BranchID	DateOfOpening

BRANCH

BranchID	BranchName	IFSCcode	Indirizzo

Per elencare i dettagli del dipendente insieme ai dettagli della filiale:

$$ Risultato \ leftarrow CUSTOMER \ bowtie_ {Customer.BranchID = Branch.BranchID} {BRANCH} $$

Traduzione di query SQL in algebra relazionale

Le query SQL vengono tradotte in espressioni di algebra relazionale equivalenti prima dell'ottimizzazione. Una query viene inizialmente scomposta in blocchi di query più piccoli. Questi blocchi vengono tradotti in espressioni di algebra relazionale equivalenti. L'ottimizzazione include l'ottimizzazione di ogni blocco e quindi l'ottimizzazione dell'intera query.

Esempi

Consideriamo i seguenti schemi:

DIPENDENTE

EmpID	Nome	Città	Dipartimento	Stipendio

PROGETTO

PId	Città	Dipartimento	Stato

LAVORI

EmpID	PID	Ore

Esempio 1

Per visualizzare i dettagli di tutti i dipendenti che guadagnano uno stipendio INFERIORE allo stipendio medio, scriviamo la query SQL:

SELECT * FROM EMPLOYEE 
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;

Questa query contiene una sottoquery nidificata. Quindi, questo può essere suddiviso in due blocchi.

Il blocco interno è -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

Se il risultato di questa query è AvgSal, il blocco esterno è -

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

Espressione di algebra relazionale per blocco interno -

$$ AvgSal \ leftarrow \ Im_ {AVERAGE (Salary)} {EMPLOYEE} $$

Espressione di algebra relazionale per blocco esterno -

$$ \ sigma_ {Salary <{AvgSal}>} {EMPLOYEE} $$

Esempio 2

Per visualizzare l'ID del progetto e lo stato di tutti i progetti del dipendente 'Arun Kumar', scriviamo la query SQL:

SELECT PID, STATUS FROM PROJECT 
WHERE PID = ( SELECT FROM WORKS  WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE 
            WHERE NAME = 'ARUN KUMAR'));

Questa query contiene due sottoquery nidificate. Pertanto, può essere suddiviso in tre blocchi, come segue:

SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR'; 
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID; 
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;

(Qui ArunEmpID e ArunPID sono i risultati di query interne)

Le espressioni di algebra relazionale per i tre blocchi sono:

$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Name = \ small "Arun Kumar"} {(EMPLOYEE)}) $$

$$ ArunPID \ leftarrow \ pi_ {PID} (\ sigma_ {EmpID = \ small "ArunEmpID"} {(WORKS)}) $$

$$ Risultato \ leftarrow \ pi_ {PID, Status} (\ sigma_ {PID = \ small "ArunPID"} {(PROJECT)}) $$

Calcolo degli operatori di algebra relazionale

Il calcolo degli operatori di algebra relazionale può essere eseguito in molti modi diversi e ogni alternativa è chiamata file access path.

L'alternativa di calcolo dipende da tre fattori principali:

Tipo di operatore
Memoria disponibile
Strutture del disco

Il tempo per eseguire un'operazione di algebra relazionale è la somma di:

È ora di elaborare le tuple.
È ora di recuperare le tuple della tabella dal disco alla memoria.

Poiché il tempo per elaborare una tupla è molto inferiore al tempo per recuperare la tupla dalla memoria, in particolare in un sistema distribuito, l'accesso al disco è molto spesso considerato come la metrica per calcolare il costo dell'espressione relazionale.

Calcolo della selezione

Il calcolo dell'operazione di selezione dipende dalla complessità della condizione di selezione e dalla disponibilità di indici sugli attributi della tabella.

Di seguito sono riportate le alternative di calcolo a seconda degli indici:

No Index- Se la tabella non è ordinata e non ha indici, il processo di selezione prevede la scansione di tutti i blocchi del disco della tabella. Ogni blocco viene portato in memoria e ogni tupla nel blocco viene esaminata per vedere se soddisfa la condizione di selezione. Se la condizione è soddisfatta, viene visualizzata come output. Questo è l'approccio più costoso poiché ogni tupla viene portata in memoria e ogni tupla viene elaborata.
B+ Tree Index- La maggior parte dei sistemi di database si basa sull'indice B + Tree. Se la condizione di selezione è basata sul campo, che è la chiave di questo indice B + Tree, questo indice viene utilizzato per recuperare i risultati. Tuttavia, l'elaborazione delle istruzioni di selezione con condizioni complesse può comportare un numero maggiore di accessi al blocco del disco e in alcuni casi la scansione completa della tabella.
Hash Index- Se vengono utilizzati indici hash e il relativo campo chiave viene utilizzato nella condizione di selezione, il recupero delle tuple utilizzando l'indice hash diventa un processo semplice. Un indice hash utilizza una funzione hash per trovare l'indirizzo di un bucket in cui è memorizzato il valore della chiave corrispondente al valore hash. Per trovare un valore chiave nell'indice, viene eseguita la funzione hash e viene trovato l'indirizzo del bucket. Vengono cercati i valori chiave nel bucket. Se viene trovata una corrispondenza, la tupla effettiva viene recuperata dal blocco del disco nella memoria.

Calcolo dei join

Quando vogliamo unire due tabelle, diciamo P e Q, ogni tupla in P deve essere confrontata con ogni tupla in Q per verificare se la condizione di join è soddisfatta. Se la condizione è soddisfatta, le tuple corrispondenti vengono concatenate, eliminando i campi duplicati e aggiunte alla relazione del risultato. Di conseguenza, questa è l'operazione più costosa.

Gli approcci comuni per l'elaborazione dei join sono:

Approccio ad anello annidato

Questo è l'approccio di join convenzionale. Può essere illustrato attraverso il seguente pseudocodice (tabelle P e Q, con tuple tuple_p e tuple_q e attributo di unione a) -

For each tuple_p in P 
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then 
   Concatenate tuple_p and tuple_q and append to Result 
End If 
Next tuple_q 
Next tuple-p

Approccio sort-merge

In questo approccio, le due tabelle vengono ordinate individualmente in base all'attributo di unione e quindi le tabelle ordinate vengono unite. Vengono adottate tecniche di ordinamento esterno poiché il numero di record è molto elevato e non può essere contenuto nella memoria. Una volta ordinate le singole tabelle, una pagina ciascuna delle tabelle ordinate viene portata in memoria, unita in base all'attributo di unione e le tuple unite vengono scritte.

Approccio hash join

Questo approccio comprende due fasi: fase di partizionamento e fase di sondaggio. Nella fase di partizionamento, le tabelle P e Q sono suddivise in due serie di partizioni disgiunte. Viene decisa una funzione hash comune. Questa funzione hash viene utilizzata per assegnare tuple alle partizioni. Nella fase di sondaggio, le tuple in una partizione di P vengono confrontate con le tuple della corrispondente partizione di Q. Se corrispondono, vengono scritte.

↰ Previous page Next page ↱