Database — Dispensa Completa

1.1 Mini-Mondo e Definizione di Dato

Il concetto di mini-mondo (o universo del discorso) e alla base di ogni sistema informativo. Si tratta di una porzione specifica della realta che si intende rappresentare all'interno di un database: per esempio, per un sistema universitario il mini-mondo comprende studenti, docenti, corsi di laurea, esami e carriere. I dati grezzi sono fatti elementari e non interpretati (ad esempio la stringa "1985-03-12"), mentre le informazioni sono i dati interpretati e contestualizzati che assumono significato per l'utente (ad esempio "Mario Rossi e nato il 12 marzo 1985"). Il processo di interpretazione trasforma dati in conoscenza utilizzabile.

Un database e una collezione di dati correlati logicamente, progettata per soddisfare le esigenze informative di una o piu organizzazioni. Non e una collezione casuale di dati: esiste una struttura che riflette le relazioni del mini-mondo, e ogni inserimento, modifica o cancellazione deve preservare la consistenza rispetto alla realta modellata. Il Database Management System (DBMS) e il software che gestisce questa collezione, offrendo strumenti per definire, costruire, manipolare e condividere i dati in modo controllato.

1.2 Gestione Centralizzata vs Distribuita

Un DBMS puo operare secondo due paradigmi fondamentali. Nella gestione centralizzata, tutti i dati risiedono su un singolo server e tutti gli utenti vi accedono attraverso lo stesso sistema. Questo garantisce un controllo unitario su sicurezza, integrita e consistenza, ma introduce un potenziale collo di bottiglia e un singolo punto di guasto. Nella gestione distribuita, i dati sono frammentati e replicati su piu nodi interconnessi. Il sistema distribuito deve nascondere all'utente la frammentazione fisica, presentando una visione logica unificata. Questo migliora la disponibilita e le prestazioni in contesti geograficamente distribuiti, ma introduce complessita nella gestione della consistenza e nella sincronizzazione delle repliche.

1.3 Ridondanza Controllata e Inconsistenza

Uno dei maggiori vantaggi offerti da un DBMS e la riduzione della ridondanza dei dati rispetto ai sistemi di file tradizionali. Nei file system, la stessa informazione viene spesso replicata in piu file di applicazioni diverse, portando a spreco di spazio e, piu gravemente, a inconsistenze quando una copia viene aggiornata e le altre no. Il DBMS consente di centralizzare la definizione dei dati e di controllare la ridondanza attraverso la condivisione controllata e i vincoli di integrita. Tuttavia, una certa ridondanza puo essere intenzionalmente mantenuta per motivi prestazionali (data denormalization), ma viene gestita consapevolmente dal DBA.

1.4 Caratteristiche dell'Approccio Database

L'approccio database introduce diverse caratteristiche distintive rispetto ai sistemi di file. La proprieta di auto-descrittivita implica che il sistema contiene non solo i dati ma anche una descrizione completa della loro struttura (il catalogo di sistema o data dictionary). Questo rende il sistema flessibile e adattabile ai cambiamenti. L'isolamento tra programmi e dati (data abstraction) permette di modificare la struttura fisica di memorizzazione senza intervenire sui programmi applicativi, un principio che approfondiremo con l'indipendenza dei dati. Il supporto per viste multiple consente a diversi utenti di vedere diverse rappresentazioni dello stesso dato sottostante. La condivisione dei dati multi-utente e regolata da sofisticati meccanismi di controllo della concorrenza che garantiscono la consistenza in presenza di accessi simultanei.

1.5 Vantaggi e Svantaggi dei DBMS

I vantaggi offerti da un DBMS sono molteplici. Il controllo centralizzato riduce la ridondanza e previene le inconsistenze. L'integrita dei dati e garantita attraverso vincoli dichiarativi (chiavi primarie, chiavi esterne, vincoli di dominio, CHECK) e vincoli procedurali (trigger, stored procedure). La sicurezza e gestita tramite autenticazione, autorizzazione granulare a livello di tabelle, viste e operazioni, e crittografia. I meccanismi di recovery garantiscono la durabilita dei dati anche in caso di guasti hardware o software. I linguaggi di query di alto livello (SQL) riducono drasticamente i tempi di sviluppo.

Tuttavia, i DBMS presentano anche svantaggi significativi. I costi iniziali di acquisto, installazione e configurazione possono essere elevati. La complessita del software richiede personale specializzato (DBA) per la gestione e l'ottimizzazione. L'overhead prestazionale del livello DBMS puo essere significativo per applicazioni semplici che non necessitano di tutte le funzionalita offerte. Esistono scenari in cui un DBMS non e la scelta migliore: per applicazioni con requisiti di latenza estremamente bassi (sistemi embedded, trading ad alta frequenza), per dati transienti che non richiedono persistenza, o per semplici archivi monoutente dove un file system e sufficiente.

1.6 Utenti del Database

Le figure che interagiscono con un database si dividono in diverse categorie. Il Database Administrator (DBA) e responsabile della gestione complessiva del sistema: installazione, configurazione, monitoraggio delle prestazioni, backup e recovery, assegnazione dei permessi. I progettisti (designer) si occupano della fase di analisi e progettazione: il progettista concettuale definisce lo schema ER, il progettista logico lo traduce in uno schema relazionale. I programmatori (application developer) scrivono il codice che interroga e modifica il database tramite DML incorporato in linguaggi ospite (Java, Python, C#). Gli utenti finali sono coloro che interagiscono con il database attraverso applicazioni predefinite o strumenti di query interattivi, senza conoscere i dettagli implementativi.

1.7 Cenni Storici

L'evoluzione dei database ha attraversato diverse generazioni. Negli anni Sessanta nacquero i primi sistemi basati su modelli gerarchici (IMS di IBM) e reticolari (CODASYL/IDMS), pensati per applicazioni gestionali su mainframe. Nel 1970 Edgar F. Codd pubblico il fondamentale articolo "A Relational Model of Data for Large Shared Data Banks" che getto le basi del modello relazionale. Gli anni Settanta videro la nascita dei prototipi System R (IBM) e Ingres (Berkeley), che dimostrarono la fattibilita pratica del modello. Negli anni Ottanta i DBMS relazionali commerciali (DB2, Oracle, SQL Server) divennero lo standard del mercato e SQL fu standardizzato dall'ANSI e dall'ISO. Gli anni Novanta portarono i database object-oriented e object-relational, il data warehousing e l'OLAP. Negli anni Duemila emersero i database XML e, con la crescita del Web, i database NoSQL (key-value, document, column-family, graph). Dal 2010 in poi si assiste alla diffusione dei database cloud (Amazon RDS, Azure SQL, Google Cloud Spanner, Snowflake) e dei sistemi NewSQL che cercano di coniugare la scalabilita orizzontale dei NoSQL con le garanzie ACID dei sistemi relazionali tradizionali.

2.1 Modello Concettuale, Logico e Fisico

Un modello di dati e un insieme di concetti, regole e convenzioni utilizzati per descrivere la struttura, le operazioni e i vincoli di un database. I modelli si classificano in tre livelli di astrazione. Il modello concettuale (di alto livello) fornisce strumenti vicini al modo in cui gli esseri umani percepiscono la realta: entita, attributi, relazioni, cardinalita. Il modello Entity-Relationship (ER) e il piu diffuso modello concettuale e viene utilizzato nella fase di progettazione concettuale per catturare i requisiti informativi indipendentemente dai dettagli implementativi.

Il modello logico (o implementativo) traduce lo schema concettuale in un formalismo che puo essere direttamente implementato da un DBMS. Il modello relazionale e il piu diffuso: rappresenta i dati come relazioni (tabelle), con tuple (righe) e attributi (colonne). Altri modelli logici includono il modello reticolare (grafi di record e link), il modello gerarchico (strutture ad albero padre-figlio), il modello a oggetti (oggetti con identita, attributi e metodi) e il modello XML (documenti con struttura ad albero etichettata).

Il modello fisico descrive nel dettaglio come i dati sono effettivamente memorizzati su supporti fisici: organizzazione dei file (heap, sorted, hashed), strutture di accesso (indici B+ tree, bitmap index, hash index), compressione, crittografia, partizionamento. E di competenza del DBA e degli amministratori di sistema.

2.2 Schema vs Istanza vs Stato

Lo schema (o intensione) e la descrizione della struttura del database: definisce le tabelle, gli attributi, i tipi, i vincoli, le viste. Lo schema cambia raramente e rappresenta l'aspetto invariante del database. L'istanza (o estensione) e l'insieme dei dati effettivamente memorizzati in un dato momento. Lo stato del database e un sinonimo di istanza: la sequenza degli stati nel tempo rappresenta l'evoluzione del contenuto del database.

Lo stato iniziale e lo stato del database al momento della prima popolazione, subito dopo la creazione dello schema. Uno stato valido e uno stato che soddisfa tutti i vincoli definiti nello schema: vincoli di chiave (UNIQUE, PRIMARY KEY), vincoli di integrita referenziale (FOREIGN KEY), vincoli di dominio (CHECK, NOT NULL), vincoli di tupla (CHECK su una riga). Ogni operazione DML (INSERT, UPDATE, DELETE) deve portare il database da uno stato valido a un altro stato valido. Se un'operazione viola un vincolo, il DBMS la rifiuta e il database rimane nello stato precedente. Questo principio e fondamentale per garantire la consistenza dei dati nel tempo.

3.1 Il modello a tre livelli

L'architettura ANSI/SPARC (American National Standards Institute / Standards Planning and Requirements Committee) e un modello di riferimento che definisce tre livelli di astrazione per i database, con l'obiettivo di separare la visione degli utenti dai dettagli fisici di memorizzazione. Il livello esterno (o di vista) rappresenta il modo in cui i singoli utenti o gruppi di utenti percepiscono i dati. Ogni utente ha la propria vista parziale del database, che espone solo i dati di suo interesse. Le viste vengono definite attraverso il VDL (View Definition Language) e, nei sistemi moderni, tramite il comando SQL CREATE VIEW.

Il livello concettuale (o logico) fornisce una descrizione globale, integrata e indipendente della struttura dell'intero database. Non contiene dettagli fisici: descrive entita, attributi, relazioni, vincoli di integrita e informazioni di sicurezza. Questo livello rappresenta la "fotografia" completa del mini-mondo cosi come deve essere rappresentato nel database. Il livello interno (o fisico) descrive come i dati sono materialmente archiviati: l'organizzazione dei file, gli indici, i percorsi di accesso, la compressione, il partizionamento.

3.2 Mappatura tra i Livelli

La mappatura esterno-concettuale traduce le richieste dell'utente (espresse in termini dello schema esterno) in richieste sullo schema concettuale. Quando un utente interroga una vista, il DBMS deve tradurre la query sulla vista nella corrispondente query sulle tabelle concettuali sottostanti. La mappatura concettuale-interno traduce le operazioni sul livello concettuale in operazioni sulle strutture fisiche: dato un comando SELECT su una tabella, il sistema decide se utilizzare un indice B+ tree, un full table scan o un hash lookup, in base alle statistiche e alle strutture fisiche disponibili.

3.3 Indipendenza Logica dei Dati

L'indipendenza logica dei dati e la capacita di modificare lo schema concettuale senza dover alterare gli schemi esterni. Ad esempio, se si aggiunge un nuovo attributo "telefono" alla tabella "Studenti", le viste esistenti che non includono "telefono" continuano a funzionare inalterate. Se si scompone una tabella in due tabelle normalizzate (ad esempio si porta una relazione da 1NF a 2NF), le viste esterne possono essere ridefinite tramite JOIN per preservare la stessa visione dei dati. L'indipendenza logica e piu difficile da raggiungere di quella fisica, perche i cambiamenti logici hanno un impatto strutturale piu profondo: la mappatura vista-schema concettuale diventa piu complessa.

3.4 Indipendenza Fisica dei Dati

L'indipendenza fisica dei dati e la capacita di modificare lo schema interno senza alterare lo schema concettuale. Esempi concreti: la creazione di un nuovo indice per velocizzare una query non richiede modifiche a livello logico; il passaggio da un organizzazione heap a un organizzazione hash per una tabella non altera la definizione della tabella stessa; la compressione delle pagine su disco e trasparente all'utente. L'indipendenza fisica e generalmente facile da ottenere perche il livello logico e completamente astratto dalle strutture fisiche sottostanti. Questo principio e alla base della cosiddetta "data abstraction" che caratterizza l'approccio database.

4.1 DDL — Data Definition Language

Il Data Definition Language (DDL) e utilizzato per definire, modificare e rimuovere la struttura del database. Opera esclusivamente sullo schema, non sui dati. Le istruzioni DDL sono generalmente eseguite dal DBA o dai progettisti durante la fase di creazione e manutenzione del database.

CREATE TABLE definisce una nuova relazione specificandone gli attributi, i tipi e i vincoli.

ALTER TABLE modifica la struttura di una tabella esistente. Puo aggiungere, eliminare o modificare colonne, attivare o disattivare vincoli, rinominare la tabella.

DROP TABLE rimuove completamente una tabella e tutti i suoi dati. DROP INDEX rimuove un indice senza alterare i dati. DROP VIEW elimina una vista.

4.2 SDL, VDL e DDL Integrato

Lo Storage Definition Language (SDL) e un sottoinsieme del DDL utilizzato per specificare lo schema interno. I comandi SDL definiscono come i dati sono memorizzati: organizzazione fisica, indici, parametri di storage. Nei DBMS moderni, la gestione dello storage e spesso automatica e non richiede istruzioni esplicite, ma alcuni sistemi permettono di specificare il tablespace, l'allocazione delle pagine, il fattore di riempimento degli indici.

Il View Definition Language (VDL) definisce le viste, ovvero gli schemi esterni. In SQL le viste sono definite tramite CREATE VIEW. Una vista e una tabella virtuale basata sul risultato di una query. Le viste possono essere utilizzate per semplificare query complesse, per nascondere colonne sensibili, e per fornire interfacce personalizzate a diversi gruppi di utenti.

4.3 DML — Data Manipulation Language

Il Data Manipulation Language (DML) fornisce le operazioni per inserire, modificare, cancellare e recuperare i dati. Si distingue in DML procedurale (record-at-a-time) e DML non procedurale (set-oriented o dichiarativo).

DML Procedurale

Nel DML procedurale, l'utente specifica sia quali dati ottenere sia come ottenerli. L'algebra relazionale e l'esempio classico: le operazioni di selezione (sigma), proiezione (pi), prodotto cartesiano (x), unione, intersezione, differenza, e i vari tipi di join (theta-join, equi-join, natural join, semi-join) vengono composte per costruire il risultato. L'utente deve specificare l'ordine delle operazioni, creando di fatto un piano di esecuzione.

DML Non Procedurale / Dichiarativo

Nel DML non procedurale, l'utente specifica quali dati vuole ottenere ma non come ottenerli. Il DBMS e responsabile di determinare il piano di esecuzione ottimale. SQL e il linguaggio dichiarativo piu diffuso. Le operazioni DML di base sono INSERT, UPDATE, DELETE e SELECT.

4.4 DCL — Data Control Language

Il Data Control Language (DCL) gestisce permessi e sicurezza. GRANT assegna privilegi, REVOKE li rimuove. I privilegi possono essere di tipo DDL (CREATE, ALTER, DROP), DML (SELECT, INSERT, UPDATE, DELETE) o amministrativi (WITH GRANT OPTION).

5.1 Architettura a Singolo Tier

Nell'architettura monolitica (single-tier), il DBMS, l'applicazione e l'interfaccia utente risiedono sulla stessa macchina. Tutte le componenti condividono le risorse di calcolo e memoria. E adatta a contesti monoutente o sistemi embedded dove la complessita di rete e ingiustificata. Il limite principale e la mancanza di scalabilita: ogni utente aggiuntivo richiede una copia completa del sistema.

5.2 Architettura a Due Tier (Client/Server)

L'architettura two-tier separa il client (interfaccia utente + logica applicativa) dal server (database). Il client invia query SQL al server attraverso un connettore (ODBC, JDBC, driver nativo) e il server restituisce i risultati. Il server puo servire molti client simultaneamente, centralizzando la gestione dei dati. Lo svantaggio principale e che la logica applicativa risiede sul client, rendendo gli aggiornamenti distributivamente costosi: ogni client deve essere aggiornato individualmente. Inoltre, la connessione diretta al database espone potenziali vulnerabilita di sicurezza.

5.3 Architettura a Tre Tier

Nell'architettura three-tier si introduce un livello intermedio (application server o middle-tier) tra client e database. Il client gestisce solo la presentazione (interfaccia utente HTML/CSS/JS), il server applicativo contiene la logica di business, e il database server gestisce i dati. Il flusso di una richiesta e: il client invia una richiesta HTTP al server applicativo, che elabora la logica, interroga il database (se necessario), e restituisce una risposta formattata. Questo modello offre numerosi vantaggi: la logica di business e centralizzata e facilmente aggiornabile, la sicurezza e migliorata perche il client non accede mai direttamente al database, la scalabilita orizzontale e possibile replicando il server applicativo, e la separazione dei compiti facilita lo sviluppo in team specializzati.

5.4 Architettura N-Tier

L'architettura N-tier generalizza il modello three-tier introducendo ulteriori strati specializzati. In un sistema web moderno si possono avere: un web server (Nginx, Apache) per la terminazione SSL e il routing, un reverse proxy/cache (Varnish, CloudFront), un application server per la logica di business (Node.js, Spring Boot, Django), un layer di caching distribuito (Redis, Memcached), un message broker (Kafka, RabbitMQ) per la comunicazione asincrona, un layer di autenticazione e autorizzazione (OAuth, LDAP), un database OLTP e uno o piu database OLAP separati. Ogni livello puo essere sviluppato, distribuito e scalato indipendentemente, offrendo la massima flessibilita. La complessita di gestione e debugging aumenta proporzionalmente al numero di livelli, ed e necessaria una strategia di monitoring e tracing distribuito (OpenTelemetry, Jaeger).

6.1 Definizione di Transazione

Una transazione e una sequenza di operazioni di lettura e scrittura sul database che costituisce una singola unita logica di lavoro. Le transazioni sono delimitate da istruzioni BEGIN TRANSACTION e COMMIT (o ROLLBACK in caso di fallimento). Il concetto di transazione e fondamentale per garantire l'affidabilita del sistema in presenza di guasti, concorrenza e accessi simultanei.

6.2 Proprieta ACID

Atomicita

L'atomicita garantisce che una transazione sia eseguita integralmente o per nulla. Se una transazione viene interrotta da un guasto (crash di sistema, errore hardware, violazione di vincolo), tutte le operazioni gia eseguite devono essere annullate (rollback) e lo stato del database deve tornare a quello precedente l'inizio della transazione. Il DBMS implementa l'atomicita attraverso il transaction log (write-ahead log o WAL): prima di scrivere i dati effettivi, vengono registrate le modifiche nel log. In caso di crash, il log viene utilizzato per annullare (undo) le transazioni non completate e per riapplicare (redo) quelle gia committate.

Consistenza

La consistenza richiede che una transazione trasformi il database da uno stato valido a un altro stato valido, preservando tutti i vincoli di integrita definiti sullo schema. La consistenza e responsabilita condivisa tra il programmatore (che deve scrivere transazioni semanticamente corrette) e il DBMS (che applica automaticamente i vincoli dichiarativi). Se una transazione viola un vincolo, il DBMS la rifiuta con un rollback.

Isolamento

L'isolamento garantisce che l'esecuzione concorrente di piu transazioni produca un risultato equivalente a quello che si otterrebbe eseguendo le stesse transazioni in un ordine seriale (uno dopo l'altro). In pratica, il DBMS utilizza tecniche di controllo della concorrenza (locking, timestamp ordering, multiversion concurrency control - MVCC) per garantire la serializzabilita. Il grado di isolamento effettivo e regolato dai livelli di isolamento.

Durabilita

La durabilita (o persistenza) garantisce che gli effetti di una transazione committata siano permanenti e sopravvivano a qualsiasi guasto successivo. Il DBMS assicura la durabilita scrivendo nel transaction log prima di confermare il COMMIT (Write-Ahead Logging): una volta che il log e stato scritto su disco, la transazione e considerata committata anche se il sistema si arresta immediatamente dopo. Al riavvio, il recovery manager utilizza il log per ripristinare lo stato consistente.

6.3 Anomalie di Concorrenza

Quando piu transazioni vengono eseguite concorrentemente senza adeguati controlli, si verificano fenomeni anomali che compromettono l'isolamento. Il Lost Update si verifica quando due transazioni leggono lo stesso dato, lo modificano concorrentemente, e l'ultima scrittura sovrascrive la prima senza incorporarla. La Dirty Read si verifica quando una transazione legge dati scritti da un'altra transazione non ancora committata: se la seconda transazione esegue rollback, la prima ha letto dati mai esistiti. L'Unrepeatable Read si verifica quando, all'interno della stessa transazione, due letture dello stesso dato restituiscono valori diversi perche un'altra transazione ha modificato il dato nel frattempo. Il Phantom Read si verifica quando una transazione esegue due volte la stessa query con un predicato di selezione e ottiene un insieme diverso di righe perche un'altra transazione ha inserito o cancellato righe che soddisfano il predicato.

6.4 Livelli di Isolamento

Lo standard SQL definisce quattro livelli di isolamento. READ UNCOMMITTED e il livello piu basso: permette dirty read, unrepeatable read e phantom read. READ COMMITTED garantisce che ogni lettura veda solo dati committati, eliminando le dirty read ma non le unrepeatable. REPEATABLE READ garantisce che letture ripetute dello stesso dato diano lo stesso risultato, eliminando unrepeatable read ma non i phantom. SERIALIZABLE e il livello massimo: garantisce l'assenza di tutte le anomalie, producendo un'esecuzione equivalente a una seriale. Livelli piu elevati offrono maggiore consistenza ma riducono la concorrenza e quindi le prestazioni. La scelta del livello di isolamento e un compromesso tra correttezza e throughput.

7.1 Gerarchia delle Memorie

La gerarchia delle memorie e organizzata per livelli con costi e prestazioni decrescenti. Al vertice ci sono i registri della CPU (accesso in 0.3-1 ns, capacita di pochi KB), seguiti dalla cache L1/L2/L3 (1-10 ns, qualche MB), dalla RAM (50-100 ns, GB), dal disco SSD (0.05-0.2 ms, TB), dal disco HDD (5-15 ms, TB), e infine dal nastro (secondi, PB). La differenza di velocita tra RAM e disco e di diversi ordini di grandezza: per questo motivo i DBMS utilizzano sofisticate tecniche di buffer management per minimizzare il numero di accessi a disco.

7.2 Struttura della Memoria Secondaria

I dischi sono organizzati in tracce concentriche, settori (tipicamente 512 byte), e blocchi multipli di settori. La pagine di database e l'unita logica di trasferimento tra disco e memoria, con dimensione tipica di 4 KB, 8 KB o 16 KB. Una pagina contiene uno o piu record di una o piu tabelle. L'operazione di lettura di una pagina richiede tre componenti: il seek time (posizionamento della testina sulla traccia corretta, 5-15 ms per HDD), la latenza rotazionale (attesa che il settore passi sotto la testina, meta giro), e il transfer time (lettura effettiva dei dati, trascurabile per pagine singole).

7.3 Buffer Pool

Il buffer pool e un'area della RAM gestita dal DBMS in cui vengono caricate le pagine del database. E organizzato come un array di frame, ognuno in grado di contenere una pagina. Ogni frame e associato a meta-informazioni: il page_id per identificare quale pagina del disco e caricata, il pin count (numero di operazioni correnti che stanno usando la pagina), il dirty bit (true se la pagina e stata modificata e deve essere riscritta su disco), e altri flag per la politica di rimpiazzo.

Quando una transazione richiede una pagina, il buffer manager verifica se la pagina e gia presente nel pool (cache hit). In caso affermativo, incrementa il pin count e restituisce il puntatore. In caso di miss, deve: (1) selezionare un frame libero o vittima secondo la politica di rimpiazzo, (2) se la pagina vittima e dirty, scriverla su disco (write-back), (3) caricare la pagina richiesta dal disco, (4) aggiornare le meta-informazioni, (5) incrementare il pin count e restituire il puntatore. Quando la transazione rilascia la pagina, decrementa il pin count. Una pagina con pin count = 0 e candidata alla sostituzione.

La politica di scrittura puo essere write-through (la modifica viene scritta immediatamente su disco prima che la transazione prosegua) o write-back (la pagina viene marcata dirty e scritta su disco solo quando deve essere rimossa dal buffer o al momento del checkpoint). La write-through e piu sicura ma molto piu lenta; la write-back e lo standard nei DBMS moderni, abbinata al Write-Ahead Logging per garantire la durabilita.

7.4 Algoritmi di Rimpiazzo Pagina

LRU (Least Recently Used)

LRU sostituisce la pagina che non viene usata da piu tempo. Mantiene una lista ordinata per timestamp di ultimo accesso: quando una pagina viene acceduta, viene spostata in testa; la pagina da sostituire e sempre in coda. LRU e efficace per carichi di lavoro con localita temporale (pattern di accesso ripetuto), ma soffre nei sequential scan: una scansione sequenziale puo flusare ("floodare") il buffer pool, sostituendo pagine che sarebbero state riaccedute. Questo fenomeno e noto come sequential flooding.

Clock (Second Chance)

L'algoritmo Clock e una approssimazione di LRU che evita di mantenere una lista ordinata esplicita. Le pagine sono disposte in un buffer circolare e ogni frame ha un reference bit. Quando una pagina viene acceduta, il reference bit viene impostato a 1. Quando si cerca una vittima, la mano dell'orologio scorre in avanti: se il reference bit e 1, viene azzerato e la pagina ottiene una seconda possibilita; se e 0, la pagina viene sostituita. Clock e computazionalmente piu leggero di LRU e resiste meglio ai sequential scan perche il reference bit offre una protezione limitata.

MRU (Most Recently Used)

MRU sostituisce la pagina usata piu recentemente. Contrariamente a LRU, e ottimale quando il pattern di accesso e tale che le pagine accedute di recente non verranno riutilizzate presto. E particolarmente efficace per large table scans e per carichi di lavoro in cui una transazione accede a molte pagine diverse in sequenza senza ripeterle.

LRU-K

LRU-K generalizza LRU tenendo traccia non solo dell'ultimo accesso ma degli ultimi K accessi a ogni pagina. Quando una pagina viene acceduta, si registra il timestamp. Al momento della sostituzione, la pagina con il K-esimo accesso piu remoto viene scelta come vittima. Per K=1 coincide con LRU. K=2 e la scelta piu comune in pratica. LRU-K discrimina meglio tra pagine con accesso frequente e pagine con accesso sporadico: una pagina acceduta due volte di recente ha probabilita molto piu alta di essere riacceduta. E l'algoritmo usato in molti DBMS commerciali moderni.

7.5 Organizzazione delle Pagine su Disco

I file di database si organizzano in tre modalita principali. Heap File: le pagine vengono allocate in ordine di inserimento senza alcun ordinamento; le nuove pagine sono aggiunte alla fine del file. L'inserimento e veloce (O(1)), ma la ricerca senza indice richiede una scansione completa (O(N)). Sorted File: le pagine sono mantenute ordinate secondo un attributo chiave, tipicamente la primary key. La ricerca binaria e possibile (O(log N)), ma l'inserimento richiede riscrittura parziale del file (O(N)). Hashing Statico: le pagine sono organizzate in bucket, ciascuno corrispondente a un valore o un intervallo di valori della funzione hash. La ricerca diretta e O(1) media. L'hashing dinamico (estendibile o lineare) risolve il problema del ridimensionamento, permettendo di far crescere la tabella hash senza riorganizzare l'intero file. L'estendibile hashing usa una directory di puntatori che raddoppia quando un bucket trabocca; il lineare hashing usa un rehashing progressivo round-robin.

7.6 RAID — Redundant Array of Independent Disks

RAID e una tecnologia che combina piu dischi fisici in un'unica unita logica per migliorare le prestazioni, l'affidabilita, o entrambe. Esistono diversi livelli standard:

RAID 0 — Striping

I dati sono suddivisi in blocchi (stripes) e distribuiti uniformemente tra tutti i dischi del gruppo. La lettura e scrittura concorrenti su piu dischi moltiplicano le prestazioni (banda aggregata = banda di un disco * numero dischi). Non offre alcuna tolleranza ai guasti: il guasto di un singolo disco rende il gruppo inutilizzabile. Adatto per dati temporanei o facilmente rigenerabili dove la velocita e prioritaria (cache di rendering, scratch disk).

RAID 1 — Mirroring

Ogni dato viene scritto identicamente su due o piu dischi (set mirror). La lettura puo essere servita da qualsiasi disco, migliorando le prestazioni in lettura. La scrittura deve essere eseguita su tutti i mirror, con un costo leggermente superiore a un singolo disco. La tolleranza ai guasti e massima: il set sopravvive al guasto di N-1 dischi su N. Lo spazio utile e pari al 50% della capacita totale (o 1/N per N mirror). Adatto per dati critici (sistema operativo, log di transazioni, database ad alta criticita).

RAID 5 — Striping con Parita Distribuita

RAID 5 combina lo striping con la parita: per ogni striscia (stripe) di N blocchi di dati, viene calcolato un blocco di parita tramite XOR, distribuito su un disco diverso per ogni striscia. La tolleranza ai guasti e di un solo disco: se un disco si guasta, i suoi dati possono essere ricostruiti calcolando lo XOR dei restanti dischi. La capacita utile e (N-1)/N del totale. La scrittura casuale e costosa perche richiede quattro accessi (leggere il dato vecchio e la parita vecchia, scrivere il dato nuovo e la parita nuova). Le letture sequenziali sono veloci perche tutti i dischi lavorano in parallelo. Adatto per storage di file e database OLAP.

RAID 6 — Doppia Parita

RAID 6 estende RAID 5 con due blocchi di parita per striscia, calcolati con codici di erasure (Reed-Solomon o XOR su due dimensioni). Puo tollerare il guasto simultaneo di due dischi. La penalita di scrittura e ancora maggiore: sei accessi per una scrittura casuale. La capacita utile e (N-2)/N. Adatto per archivi di grandi dimensioni dove i tempi di ricostruzione di RAID 5 (ore o giorni) espongono a un secondo guasto.

RAID 10 — Striping di Mirror

RAID 10 (o 1+0) combina mirroring e striping: crea prima dei mirror (RAID 1) e poi li stripa (RAID 0). Combina la tolleranza ai guasti del mirroring con le prestazioni dello striping. La capacita utile e il 50% del totale. La tolleranza ai guasti dipende da quali dischi si guastano: il sistema sopravvive al guasto di un disco per mirror. Le prestazioni in scrittura sono simili a un singolo disco. E lo schema preferito per database OLTP ad alta criticita dove sia prestazioni che affidabilita sono essenziali.