Databases Architettura di un DBMS

(1)

Databases

Architettura di un DBMS

(2)

2

Architettura di un dbms

• Un DBMS e’ un software per la gestione di basi di dati, e piu’ in generale e’ uno strumento potente per creare e gestire in

maniera efficiente una grande quantita’ di dati e per permettere la loro persistenza nel tempo.

• Come funziona e si usa un DBMS?

Cognome Stipendio

Rossi 1700

Rossi 1550

Bianchi 1500 Select Cognome, Stipendio

From Impiegati

Where Stipendio>1300

Nome Cognome Sesso Stipendio

Maria Rossi F 1700

Piero Neri M 1200

Luca Rossi M 1550

Elena Bianchi F 1500

?

(3)

3

Esercitazione di gruppo

• Vogliamo implementare un DBMS relazionale!

• Il sistema deve essere in grado di:

• Memorizzare relazioni come R(A,B,C), S(A,B) e T(A,B).

• Eseguire interrogazioni come:

select A, B From R

Where B = 2000

select R.A, T.B From R, S, T

Where R.B = S.A And S.B = T.A

(4)

4

Verifica del sistema

Come si comporta il sistema nei confronti di:

• Ricerca di tuple?

• Ordine delle operazioni?

• Aggiornamenti di tuple?

• Accesso ripetuto alle stesse locazioni su disco?

• Modifiche concorrenti?

• Controllo degli accessi?

• Interfacce di programmazione?

(5)

5

Architettura di un DBMS relazionale (1)

Query compiler

Buffer

Lock Table Execution

Engine Index/File/

Record Manager Buffer Manager Storage Manager

Transaction Manager

Logging/

Recovery

Concurrency Control DDL Compiler

Dati e comandi Dati

(6)

6

Architettura di un DBMS relazionale (2)

• L’architettura presentata nel lucido precedente è composta da tre sottosistemi principali:

• Per la gestione dei dati su disco.

• Per l’esecuzione delle interrogazioni.

• Per la gestione delle transazioni.

(7)

7

Sottosistema per le interrogazioni

Query compiler

Buffer Execution

Engine Index/File/

RecordManager Buffer Manager

Storage Manager

Select A, B From R1, R2 Where C = D And C = ‘c’

(8)

8

Query compiler (1)

• Il Query Compiler fa il parsing e ottimizza le interrogazioni.

• L’interrogazione viene prima riconosciuta e controllata sintatticamente.

• Il risultato del parsing viene tradotto in una espressione in una versione estesa dell’algebra relazionale.

• L’espressione viene trasformata in un’espressione equivalente ma considerata più efficiente.

• Il risultato del query compiler è un query plan, cioè un elenco cronologico delle operazioni da compiere per eseguire

l’interrogazione.

(9)

“Ottimizzazione” algebrica

• Il termine ottimizzazione è improprio (anche se efficace) perché la vera ottimizzazione avviene a livello algoritmico

• Possono essere impiegate delle euristiche.

• Si basa sulla nozione di equivalenza di espressioni algebriche:

• Due espressioni sono equivalenti se producono lo stesso risultato qualunque sia l'istanza attuale della base di dati

• I DBMS cercano di eseguire espressioni equivalenti a quelle date, ma meno "costose"

• Proprietà fondamentali (“euristiche”):

• σezioni e proiezioni il più presto possibile (per ridurre le dimensioni dei risultati intermedi):

• "push σections down"

• "push projections down"

(10)

"Push σections"

• Assumiamo A attributo di R₂

σ A=10 (R₁ × R₂) = R₁ × σ

A=10 ( R₂)

• Riduce in modo significativo la dimensione del risultato intermedio (e quindi il costo dell'operazione)

(11)

Una procedura euristica di ottimizzazione

• Decomporre le σezioni congiuntive in successive σezioni atomiche

• Anticipare il più possibile le σezioni

• In una sequenza di σezioni, anticipare le più σettive

• Anticipare il più possibile le proiezioni (anche introducendone di nuove)

(12)

Esempio

R1(ABC), R2(DEF), R3(GHI)

SELECT A , E FROM R1, R2, R3

WHERE C=D AND B>100 AND F=G AND H=7 AND I>2

• prodotto cartesiano (FROM)

• σezione (WHERE)

• proiezione (SELECT)

π _AE (σ C=D AND B>100 AND F=G AND H=7 AND I>2 ((R1 × R2) × R3))

(13)

Esempio, continua

π _AE (σ C=D AND B>100 AND F=G AND H=7 AND I>2 ((R1 × R2) × R3))

• Può essere interpretato come

π _AE(σ _B>100(R1) ×_C=D R2) ×_F=G σ_I>2(σ_H=7(R3)))

• oppure

π _AE(

π _AEF((π _AC(σ _B>100 (R1))) × _C=D R2)

×_F=G π _G (σ_I>2(σ_H=7(R3))) )

(14)

14

Query compiler (2)

Query compiler

Buffer Execution

Engine Index/File/

RecordManager Buffer Manager Storage Manager

π_A,B(σ_C=D(σ_C=c(R1)×R2))

(15)

15

Execution Engine (1)

• L’Execution Engine crea una sequenza di richieste di dati

(tipicamente record) e implementa le istruzioni ottenute dal query compiler.

(16)

16

Execution Engine (2)

Query compiler

Buffer Execution

Engine Index/File/

Storage Manager

π_A,B(σ_C=D(σ_C=c(R1) × R2))

σ_C=c(R1), ×R2, σ, π

(17)

17

Resource Manager (1)

• Il Resource Manager sa dove sono i dati (file e record) e come recuperarli velocemente (indici).

• Le richieste di dati vengono tradotte in richieste di blocchi su disco.

(18)

18

Resource Manager (2)

Query compiler

Buffer Execution

Engine Index/File/

π_A,B(σ_C=D(σ_C=c(R1) × R2))

σ_C=c(R1), ×R2, σ, π

R1

(19)

19

Gestione dati su disco (1)

• Il Buffer Manager ha il compito di trasportare in memoria centrale i blocchi richiesti.

• Per farlo, si affida allo Storage Manager, che gestisce i dispositivi di memoria secondaria.

• I Dischi sono i principali dispositivi utilizzati per memorizzare database.

• I dati gestiti dal buffer manager sono di vario tipo:

• Dati: il contenuto del database.

• Metadati: lo schema del database.

• Statistiche: informazioni sul contenuto del database.

• Indici: strutture di supporto per l’accesso rapido ai dati.

(20)

Memoria principale e secondaria

• I programmi accedono efficientemente solo a dati in memoria principale (heap, stack, buffer di SO).

• Le basi di dati debbono essere (sostanzialmente) in memoria secondaria per due motivi:

• dimensioni

• persistenza

• I dati in memoria secondaria possono essere utilizzati solo se prima trasferiti in memoria principale.

(21)

Memoria principale e secondaria, 2

• I dispositivi di memoria secondaria sono organizzati in blocchi di lunghezza (di solito) fissa (ordine di grandezza: alcuni KB)

• Le uniche operazioni sui dispositivi solo la lettura e la scrittura di di una pagina, cioè dei dati di un blocco (cioè di una stringa di byte);

• per comodità consideriamo blocco e pagina sinonimi

(22)

Memoria principale e secondaria, 3

• Accesso a memoria secondaria:

• tempo di posizionamento della testina (10-50ms)

• tempo di latenza (5-10ms)

• tempo di trasferimento (1-2ms)

in media non meno di 10 ms

• Il costo di un accesso a memoria secondaria è quattro o più ordini di grandezza maggiore di quello per operazioni in memoria

centrale

• Perciò, nelle applicazioni "I/O bound" (cioè con molti accessi a memoria secondaria e relativamente poche operazioni) il costo dipende esclusivamente dal numero di accessi a memoria

secondaria

• Inoltre, accessi a blocchi “vicini” costano meno (contiguità)

(23)

23

Query compiler

Buffer Execution

Engine Index/File/

Storage Manager

π_A,B(σ_C=D(σ_C=c(R1) × R2))

σ_C=c(R1), ×R2, σ, π

R1

σ (R1)

(24)

24

Query compiler

Buffer Execution

Engine Index/File/

π_A,B(σ_C=D(σ_C=c(R1) × R2))

σ_C=c(R1), ×R2, σ, π

R2

×R2

(25)

25

Query compiler

Buffer Execution

Engine Index/File/

π_A,B(σ_C=D(σ_C=c(R1) × R2))

σ_C=c(R1), ×R2, σ, π

σ, π