Appunti di Basi di dati

Formattazione del testo

N P (R) + N T (R)+– con un indice B -tree sugli attributi di join sulla relazione S: C =N P (R) + (h + 1)N T (R)• hash join: viene creata una tabella hash in memoria centrale e viene riem-pita con l’attributo di join della relazione R. Successivamente si fa il joinattraverso questa tabella con gli attributi di S e si ripete il processo finchéN T (R) ⌉non si completa la relazione R: C = N P (R) + N P (S)⌈ N T (T )6.3 Ottimizzazione logicaOltre all’ottimizzazione fisica, che abbiamo visto prima e che dipende dallastruttura di come i dati sono fisicamente salvati nel database in memoria, es-iste l’ottimizzazione logica, che sfruttando l’equivalenza tra diversi metodi ditradurre query in algebra relazionale, modificando l’ordine delle operazioni, èpossibile ottimizzare le varie query, in modo da fare il minor numero di accessial database. Alcune delle principali regole di equivalenza sono:• anticipazione della selezione

rispetto al join• anticipazione della proiezione rispetto al join• distributività della selezione rispetto all’unione e alla differenza

Ogni query dell’algebra relazionale può essere vista come un albero, dove ai nodi diversi dalle foglie sono presenti operatori e ai nodi foglia sono presenti relazioni. La costruzione dell’albero tiene conto della presenza di indici e dell’ottimizzazione sia logica che fisica. Inoltre per esegure materialmente le query possono essere applicati due approcci:

• materializzazione: le tuple di relazioni intermedie calcolate vengono salvate e passate al livello superiore successivamente;
• pipeline: le tuple una volta calcolate vengono direttamente passate al livello superiore

Transazioni

Una transazione è una serie di operazioni di aggiornamento di una base di dati che vengono considerate in modo unitario. La particolarità delle transazioni è che se un’operazione viene interrotta o è impossibile eseguirla,

La trasazione attraverso un'operazione di rollback può resettare la base di dati allo stato immediatamente precedente a quello dell'inizio dell'esecuzione della transazione. Grazie a questa transazione è possibile avere la base di dati in uno stato inconsistente durante l'esecuzione di una transazione (ma deve essere consistente al termine della transazione). Le operazioni che non sono incluse in transazioni vengono considerate transazioni a sé stanti. Per semplicità rappresentiamo le transazioni come sequenze di operazioni read-write.

7.1 Esecuzione concorrente di transazioni

Una delle caratteristiche delle transazioni è che possono essere eseguite in modo concorrente. Questo permette di aumentare la velocità di esecuzione in modo sensibile. Di contro bisogna stare attenti a come queste vengono schedulate, perché alcuni modi di eseguire alcune transazioni in modo concorrente possono portare a errori, chiamati anomalie. Le anomalie più frequenti sono:

struttura a grafo, dove i nodi rappresentano le transazioni e gli archi rappresentano le dipendenze tra le operazioni delle transazioni.– è aciclico se non contiene cicli, ovvero se non esistono percorsi che ritornano al nodo di partenza. La serializzabilità di uno scheduling può essere valutata anche utilizzando il protocollo di locking. Questo protocollo prevede l'utilizzo di lock (bloccaggi) per garantire l'accesso esclusivo ai dati condivisi tra le transazioni. In particolare, si utilizzano due tipi di lock: il lock di lettura (shared lock) e il lock di scrittura (exclusive lock). Un'operazione di lettura può ottenere un lock di lettura solo se nessuna transazione ha ottenuto un lock di scrittura sullo stesso dato. Al contrario, un'operazione di scrittura può ottenere un lock di scrittura solo se nessuna transazione ha ottenuto un lock di lettura o di scrittura sullo stesso dato. Il protocollo di locking garantisce la correttezza dello scheduling, evitando problemi come il lost update (aggiornamento perso), le letture irripetibili e gli aggiornamenti fantasma. Il lost update si verifica quando due transazioni leggono e scrivono contemporaneamente sullo stesso dato, ma solo l'ultima scrittura viene mantenuta. Le letture irripetibili si verificano quando una transazione legge lo stesso dato più volte durante la sua esecuzione e ottiene risultati diversi. Gli aggiornamenti fantasma si verificano quando una transazione legge un insieme di dati, esegue un'operazione di scrittura su un sottoinsieme di questi dati e poi legge nuovamente l'insieme di dati, ottenendo risultati diversi. Per garantire la correttezza dello scheduling, è necessario seguire alcune regole nel protocollo di locking. Ad esempio, un'operazione di scrittura deve ottenere un lock di scrittura solo se nessuna transazione ha ottenuto un lock di lettura o di scrittura sullo stesso dato. Inoltre, un'operazione di lettura può ottenere un lock di lettura solo se nessuna transazione ha ottenuto un lock di scrittura sullo stesso dato. In conclusione, la serializzabilità di uno scheduling concorrente può essere valutata utilizzando le coppie di operazioni conflittuali o il protocollo di locking. Entrambi i metodi garantiscono la correttezza dello scheduling, evitando problemi come il lost update, le letture irripetibili e gli aggiornamenti fantasma.

transazione ad ogni nodo– un arco orientato per indicare l’ordine delle operazioni di una coppiadi operazioni conflittuali• per evitare la formazione di cicli in un grafico delle precedenze, al momentodella costruzione dello scheduling, i DBMS sfruttano un sistema di lock:– un lock in lettura per ogni variabile– un lock in scrittura per ogni variabile– si può prendere un lock in lettura se non è già presente un lock inscrittura– si può prendere un lock in scrittura se non è già presente un lockqualsiasi• per gestire i lock si usa il protocollo 2PL, che impone di non riprendere illock su una variabile dopo aver fatto l’unlock su quella stessa variabile• l’applicazione del protocollo 2PL genera scheduling c-serializzabili. Unproblema però è la possibilità di incappare in situazioni di deadlock. Perevitare queste situazioni, si può applicare delle convenzioni, a discapitodell’efficenza:–

prendere sempre il write lock– fare l’operazione di unlock dopo il commit (protocollo 2PL stretto)
7.2 gestione dell’affidabilità
Per garantire alcune delle proprietà principali delle transazioni bisogna prevedere
dei meccanismi che intervengano in caso di fallimento della transazione stessa
o del sistema che ospita il database. Per fare ciò una componente dedicata
del DBMS usa file di log e checkpoint per garantire l’affidabilità dei dati del
database.
7.2.1 File di log
I file di log sono file che vengono salvati in un posto molto sicuro, e noi consideri-
amo che siano sempre disponibili, anche in caso di fallimento del sistema. I file di
log contengono uno storico di tutte le operazioni di aggiornamento che vengono
effettuate sul database, insieme ai valori assunti prima dell’aggiornamento.
11
7.2.2 Checkpoint
Ogni volta che una transazione viene eseguita le operazioni di aggiornamento
vengono memorizzate nel buffer in memoria centrale che contiene le pagine

Il database contiene informazioni che devono essere memorizzate. Per rendere effettivi questi cambiamenti, periodicamente le pagine del buffer vengono salvate in memoria secondaria, perché la memoria centrale è più soggetta a fallimenti.

La transazione viene interrotta prima del commit. Se non si applicassero meccanismi di affidabilità si perderebbe l'atomicità della transazione, e inoltre il database potrebbe trovarsi in uno stato inconsistente. Quando avviene un transaction failure, si guarda nel file di log quali operazioni erano state svolte, e si fa un'operazione di UNDO.

Può succedere che avvenga un crash generale del sistema. In questo caso non solo le transazioni vengono interrotte, ma si perde anche il buffer in memoria centrale. In questo caso si applicano due operazioni:

• operazione di UNDO sulle transazioni che erano iniziate ma che non erano state completate;
• operazione di REDO per le operazioni che erano iniziate e finite.

ma le cui operazioni sono state effettuate dopo l'ultimo checkpoint. Si applica quindi, quando possibile, questo meccanismo, detto di ripresa a caldo, che senza l'intervento umano risolve tutti i problemi legati all'affidabilità dei dati.

8 Blockchain

La blockchain è un registro di transazioni distribuito in una rete di nodi, dove ogni nodo è paritario rispetto agli altri. Ha diverse caratteristiche fondamentali che la distinguono dalle altre tecnologie:

• Sfrutta tecnologie di hashing (SHA-256) per garantire la sicurezza.
• È formata da una catena di blocchi, ognuno formato da un header e da un insieme di transazioni.
• L'header è formato da:
• timestamp: momento in cui il blocco è stato generato
• n° di transazioni del blocco 12
• difficulty target: numero di zeri con cui l'hash del blocco deve iniziare (256 bit)
• nonce: numero da variare per trovare l'hash corretto del blocco
• hash del blocco precedente:

Per connettere i blocchi alla catena– merkle root del blocco delle transazioni: un merkle root è un albero di hash di transazioni in cui un nodo superiore è l’hash dei due nodi inferiori. Se cambia anche un solo hash, cambia anche l’hash della radice e quindi l’hash del blocco che diventa invalido.

La blockchain è replicata uguale in ogni nodo, di modo che non esiste un nodo centrale.

Una transazione contiene i dati del mittente, del destinatario, e dell’oggetto dello scambio.

La validazione di una transazione o di un blocco deve essere fatta da tutti i nodi, cosı̀ che se anche un nodo o un gruppo di nodi è fraudolento, è molto difficile che un’informazione incorretta passi.

Per evitare sybil attack ci sono nodi speciali detti miner che attraverso alcune tecniche (proof of work, proof of stake, ...) costruiscono in blocchi, ad esempio variando il nonce e calcolando hash crittografici, in cambio di una ricompenza. Poichè la

La potenza hardware (proof of work) o il numero di criptovalute (proof of stake) necessarie per validare un blocco è molto elevato, è impossibile che un nodo abbia una potenza da poter superare quella di tutti gli altri messi insieme. Ne consegue che la blockchain è molto sicura.

9 Sistemi NoSQL

Un sistema NoSQL (Not only SQL) appartiene a una classe di sistemi di basi di dati che gestiscono i dati non solo attraverso l'utilizzo di SQL. Nella pratica questo significa che le basi di dati non sono relazionali e SQL non viene mai usato. Nascono dall'esigenza nata negli ultimi anni dei big data, ovvero di basi di dati enormi e decentralizzate. Sono sistemi molto variegati, che non seguono uno standard, e di cui esistono diverse macrocategorie principali:

• sistemi a documenti
• sistemi a grafi
• sistemi a key value store
• sistemi a colonne ordinate

Mentre le basi di dati relazionali hanno le proprietà ACID, le basi di dati NoSQL hanno le proprietà base (per la

La maggior parte dei sistemi:

• Basically Avialable: disponibili sempre grazie all'architettura distribuita
• Soft State: lo stato della base di dati può cambiare senza l'intervento dell'utente
• Eventual Consistency: la consistenza dei dati è raggiunta alla fine, non in ogni momento dell'esecuzione

9.1 Sistemi a documenti

Sono insiemi di collezioni di documenti. Le associazioni tra documenti sono rappresentate o tramite referencing (tipo chiave secondaria) o, più spesso, tramite embedding, cioè integrando un documento in un altro. Si può avere così ridondanza dei dati, eliminando la normalizzazione delle basi di dati relazionali, ma si guadagna molto in efficenza in quanto, se strutturato bene, un sistema a documenti elimina o riduce di molto le operazioni di join.