Base di Dati IV · Appunti Universitari

26 Oct 2004

Riassunto gerarchico delle nozioni del corso 2004-2005 di BASI DI DATI della Prof. Nicoletta Dessì - Università degli Studi di Cagliari, Facoltà di Scienze Matematiche Fisiche Naturali, Dipartimento di Matematica ed Informatica, Corso di Laurea in Informatica

Riferimenti: Raghu Ramakrishnan, Johannes Gehrke - Sistemi di basi di dati, McGraw-Hill

progettazione di basi di dati
- la progettazione delle basi di dati è una delle attività del processo di sviluppo dei sistemi informativi, va quindi inquadrata nel contesto più generale:
- ciclo di vita dei sistemi informativi
  - insieme e sequenzializzazione delle attività svolte da analisti, progettisti, utenti, nello sviluppo e nell'uso dei sistemi informativi
    - studio di fattibilità
    - raccolta ed analisi dei requisiti
    - progettazione
    - implementazione
    - validazione e collaudo
    - funzionamento
- metodologia di progettazione
  - si basa sul principio della separazione netta tra le decisioni relative a:
    - che cosa rappresentare
      - progettazione concettuale
        
        schema concettuale
    - come rappresentare
      - progettazione logica
        
        schema logico
      - progettazione fisica
        
        schema fisico
  - modelli
    - modelli logici
      - indipendenti dalle strutture fisiche ma disponibili nei DBMS
    - modelli fisici
      - indipendenti dalle modalità di realizzazione
- modello ER (Entity-Relationship, Entità-Relazione)
  - sviluppato da P.P. Chen nel 1976
  - è basato su rappresentazioni grafiche corredate da descrizioni
  - si è affermato nelle metodologie di progetto e nei sistemi software di ausilio alla progettazione (CASE)
  - costrutti di base
    - entità
      - classe di oggetti (fatti, persone, cose) dell'applicazione di interesse con proprietà comuni e con esistenza autonoma
      - esempi: impiegato, conto corrente, fattura, ordine, città, studente
      - si rappresenta con un rettangolo con al centro un nome univoco che la identifica nello schema
      - occorrenza (o istanza) di entità
        
        oggetto della classe che l'entità rappresenta (non è un valore che identifica l'oggetto ma l'oggetto stesso)
        
        nello schema concettuale si rappresentano solo le entità e non le singole istanze
      - entità deboli
        
        sono entità che non hanno propri attributi chiave e necessitano per essere identificate di un'altra entità detta entità forte
        
        in generale ha una chiave parziale
        
        può essere modellata con un attributo complesso dell'entità forte se non partecipa per suo conto ad altre relazioni
        
        esempio: [banca](0,N)<filiale>(1,1)[[filiale di banca]]
        
        la filiale di banca è l'entità debole
    - relazione
      - legame logico, significativo per l'applicazione di interesse, fra due o più entità
      - si rappresenta con un rombo con al centro un nome univoco che la identifica nello schema
      - in una occorrenza di relazione non ci possono essere ripetizioni (doppio arco con gli stessi estremi)
      - due entità possono essere coinvolte in più relazioni
      - le relazioni possono coinvolgere più di due entità
      - relazione ricorsiva
        
        una relazione può coinvolgere due volte la stessa entità
        
        in alcuni casi vanno specificati i ruoli:
        
        esempio
        
        entità: persona
        
        relazione ricorsiva matrimonio
        
        ruoli: marito, moglie
      - esempi
        
        residenza (fra persona e città)
        
        afferenza (tra impiegato e dipartimento)
    - attributo
      - proprietà elementare di un'entità o di una relazione, di interesse ai fini dell'applicazione
      - un attributo associa ad ogni occorrenza di entità o relazione un valore appartenente ad un insieme detto dominio dell'attributo
      - graficamente si rappresenta come un segmento che parte dall'entità o dalla relazione e termina con un piccolo cerchio affiancato dal nome dell'attributo (identificatore)
      - tipi di attributo
        
        semplici (atomici) o composti
        
        gli attributi composti si ottengono raggruppando attributi di una medesima entità o relazione che rappresentano affinità nel loro significato o uso
        
        esempio: [via, numero civico, CAP] rappresentano un indirizzo
        
        a valore singolo o multivalore
        
        esempio: età, colori
        
        memorizzati o derivati
        
        esempio: data di nascita, età
        
        valori nulli
        
        complessi (composti + multivalore)
        
        chiave
        
        indentifica univocamente un'entità
    - cardinalità
      - di relazione
        
        coppia di valori che si associa ad ogni entità che partecipa ad una relazione
        
        specificano il numero minimo e massimo di occorrenze della relazione cui ciascuna occorrenza di una entità può partecipare
        
        si indica con la notazione (min,max) prossima al segmento di unione dell'entità con la relazione
        
        casi notevoli:
        
        (1,1) : obbligatoria, una sola volta
        
        (1,N) : obbligatoria, n volte
        
        (0,1) : opzionale, una sola volta
        
        (0,N) : opzionale, N volte
        
        classificazione di relazioni
        
        con riferimento alle cardinalità massime, abbiamo le relazioni:
        
        uno a uno
        
        [ordine](0,1)<vendita>(1,1)[fattura]
        
        uno a molti
        
        [persona](1,1)<nascita>(1,N)[città]
        
        molti a molti
        
        [studente](0,N)<esame>(0,N)[corso]
      - di attributo
        
        si indica con la notazione (min, max) prossima al segmento di attributo
        
        hanno due scopi:
        
        indicare l'opzionalità (0,1)
        
        indicare gli attributi multivalore (0,N)
    - identificatore
      - identifica univocamente le occorrenze di un'entità
      - si rappresenta graficamente come una linea che termina con un piccolo cerchio
      - può essere:
        
        interno
        
        costituito da attributi dell'entità
        
        esterno
        
        costituito da attributi dell'entità più delle entità esterne attraverso le relazioni
      - ogni entità deve possedere almeno un identificatore
      - una identificazione esterna è possibile solo attraverso una relazione a cui l'entità da identificare partecipa con cardinalità (1,1)
    - generalizzazione
      - mette in relazione una o più entità E1, E2, ..., En (figlie) con una terza entità E (padre) che le comprende come caso particolare
        
        E è la generalizzazione di E1, E2, ..., En
        
        E1, E2, ..., En sono specializzazioni (o sottotipi) di E
      - graficamente si rappresenta con una freccia che punta verso E ed è collegata ai sottotipi con dei segmenti
      - proprietà:
        
        ogni proprietà di E è significativa per E1, E2, ..., En
        
        ogni occorrenza di E1, E2, ..., En è anche occorrenza di E
        
        ogni ocorrenza di E è al più occorrenza di una entità tra E1, E2, ..., En
      - ereditarietà
        
        tutte le proprietà (attributi, relazioni, altre generalizzazioni) dell'entità padre vengono ereditate dalle entità figlie e non rappresentate esplicitamente
      - classificazione
        
        generalizzazione totale
        
        lo è se ogni occorrenza dell'entità padre è un'occorrenza di almeno una delle entità figlie, altrimenti è parziale
        
        si rappresenta con una freccia piena
        
        generalizzazione parziale
        
        si rappresenta con una freccia vuota
      - proprietà di copertura
        
        totale ed esclusiva
        
        (persona → maschio, femmina)
        
        parziale ed esclusiva
        
        (impiegato → tecnico, segretario) ci sono impiegati che non sono ne tecnici ne segretari, un tecnico non è segretario e viceversa
        
        parziale e sovrapposta
        
        (impiegato → tecnico, segretario) ci sono impiegati che non sono ne tecnici ne segretari, un tecnico è anche segretario e viceversa
        
        totale e sovrapposta
        
        (impiegato → tecnico, segretario) gli impiegati sono solo tecnici e segretari e svolgono entrambi i ruoli
      - altre proprietà
        
        possono esistere gerarchie a più livelli e gerarchie multiple allo stesso livello
        
        un'entità può essere inclusa in più gerarchie, come genitore e/o come figlia
        
        se una generalizzazione ha solo un'entità figlia, si parla di sottoinsieme
- progettazione concettuale
  - strategie di progetto
    - top-down
      - si parte dallo schema finale e si raffina con varie tecniche
    - bottom-up
      - si parte dai singoli schemi che si combinano per formare lo schema finale
    - inside-out
  - strategia pratica (ibrida o mista)
    - 1. si individuano i concetti principali e si realizza uno schema scheletro (semplice schema concettuale)
    - 2. si decompone sulla base dello schema scheletro
    - 3. si raffina si espande e si integra
  - qualità di uno schema concettuale
    - correttezza
    - completezza
      - leggibilità
      - minimalità
  - metodologia generale
    - 1. analisi dei requisiti
      - costruire un glossario dei termini
      - analizzare i requisiti ed eliminare le ambiguità presenti
      - raggruppare i requisiti in insiemi omogenei
    - 2. passo base
      - individuare i concetti più rilevanti per rappresentarli in uno schema scheletro
    - 3. passo di decomposizione
      - effettuare una decomposizione con riferimento ai concetti dello schema scheletro
    - 4. passo iterativo (da ripetere per affinamenti succesivi)
      - raffinare i concetti presenti sulla base delle loro specifiche
      - aggiungere concetti per descrivere specifiche non ancora descritte
    - 5. passo di integrazione
      - integrare i vari sotto-schemi con riferimento allo schema scheletro
    - 6. analisi di qualità (ripetuta e distribuita)
      - verificare le qualità dello schema ed eventualmente ristrutturarlo
- progettazione logica
  - ha l'obiettivo di tradurre lo schema concettuale in uno schema logico che rappresenti gli stessi dati in maniera corretta ed efficiente
    - non si tratta di una pura e semplice traduzione per due motivi:
      - alcuni aspetti non sono direttamente rapresentabili
      - è necessario prestare attenzione alle prestazioni
  - dati
    - ingresso
      - schema concettuale
      - informazioni sul carico applicativo
      - modello logico
    - uscita
      - schema logico
      - documentazione associata
- articolazione in fasi
  - ristrutturazione schema ER
    - descrizione
      - uno schema ER ristrutturato non è più uno schema concettuale nel senso stretto del termine
      - motivazioni
        
        semplificare la traduzione
        
        ottimizzare il progetto
      - per ottimizzare il risultato occorre analizzare le prestazioni, consideriamo quindi degli indici:
        
        spazio: numero di occorrenze previste
        
        tempo: numero di occorrenze (di entità e relazioni) visitate durante un'operazione
    - si divide in
      - analisi delle ridondanze
        
        una ridondanza in uno schema ER è un'informazione significativa ma derivabile da altre
        
        in questa fase si decide se eliminare le ridondanze eventualmente presenti o mantenerle
        
        vantaggi
        
        semplificazione delle interrogazioni
        
        svantaggi
        
        appesantimento degli aggiornamenti
        
        maggiore occupazione di spazio
        
        forme di ridondanza in uno schema ER
        
        attributi derivabili
        
        da attributi della stessa entità (o relazione)
        
        da attributi di altre entità (o relazioni)
        
        relazioni derivabili dalla composizione di altre relazioni in presenza di cicli
      - eliminazione delle generalizzazioni
        
        il modello relazionale non può rappresentare direttamente le generalizzazioni
        
        si eliminano le gerarchie sostituendole con entità e relazioni
        
        si hanno tre possibilità:
        
        1. accorpamento delle figlie nella generalizzazione nel padre
        
        conviene se gli accessi al padre ed alle figlie sono contestuali
        
        2. accorpamento del padre nella generalizzazione delle figlie
        
        conviene se gli accessi alle figlie sono distinti
        
        3. sostituzione della generalizzazione con relazioni
        
        conviene se gli accessi alle entità figlie sono separati dagli accessi al padre
        
        4. sono anche possibili soluzioni ibride
      - partizionamento/accorpamento di entità e relazioni
        
        ristrutturazioni effettuate per rendere più efficienti le operazioni in base al principio secondo cui gli accessi si riducono:
        
        separando gli attibuti di un concetto che vengono acceduti separatamente
        
        raggruppando attributi di concetti diversi acceduti insieme
        
        tipologie
        
        partizionamento verticale di entità
        
        partizionamento orizzontale di relazioni
        
        eliminazione di attributi multivalore
        
        accorpamento di entità/relazioni
      - scelta degli identificatori primari
        
        operazione indispensabile per la traduzione nel modello relazionale
        
        criteri
        
        assenza di valori nulli
        
        semplicità
        
        preferenza per gli indicatori interni
        
        utilizzo nelle operazioni più frequenti o importanti
        
        se nessun identificatore soddisfa i criteri, si introducono nuovi attributi (codici) contenenti valori speciali generati appositamente per questo scopo
  - traduzione verso il modello relazionale
    - idea di base
      - le entità diventano relazioni sugli stessi attributi
      - le associazioni (ovvero le relazioni ER) diventano relazioni sugli identificatori delle entità coinvolte (più degli attributi propri)
    - talvolta può essere utile ridenominare gli attributi della chiave della relazione che rappresenta l'associazione
- progettazione fisica
  - si divide in
    - organizzazione dei files
    - metodi di accesso
    - organizzazione indici
  - file
    - insieme di record
      - lunghezza fissa (R)
      - lunghezza variabile
    - blocco
      - unità di trasferimento dati da disco a memoria (buffer)
      - fattore di blocco
        
        bfr = B / R
        
        dove: B = dimensione del blocco, R = dimensione del record
    - allocazioni a blocchi di un file
      - contigua
      - collegata
      - a cluster
  - organizzazione dei file rispetto ai record
    - non ordinati (heap)
      - record memorizzati secondo l'ordine di inserimento
      - caratteristiche
        
        inserimento efficiente
        
        aggiornamento e ricerca sequenziale
        
        complessità lineare
        
        cancellazione
        
        ricerca e scrittura dei record
    - sequenziali (ordinati)
      - record ordinati rispetto ad un campo chiave
      - caratteristiche
        
        aggiornamento e ricerca dicotomica
        
        complessità logaritmica
        
        inserimento e cancellazione
        
        riscrittura all'interno del file
    - hash
      - posizione record calcolata
      - caratteristiche
        
        allocazione random del record
        
        basata su un'algoritmo di hashing
        
        applicato ad un campo chiave
        
        accesso direto al record
      - collisione
        
        avviene quando l'algoritmo di hashing calcola la stessa posizione per due record diversi
        
        soluzioni
        
        ricerca posizione libera e collegamento con puntatori
        
        dispendiosa e non sempre praticabile
        
        aree di overflow
        
        richiedono una riorganizzazione periodica
        
        hash ripetuto iterativamente
        
        è dispendioso
  - indici
    - ad un solo livello
      - sono basati su file sequenziali ordinati
    - a più livelli
      - sono basati su organizzazioni al albero B+
    - alberi di ricerca
      - i nodi del sottoalbero SX hanno chiave minore del nodo padre
      - i nodi del sottoalbero DX hanno chiave maggiore del nodo padre
      - presentano il problema del bilanciamento
      - inserimenti e cancellazioni possono sbilanciare l'albero
      - il B albero soddisfa vincoli che assicurano il bilanciamento dell'albero a seguito di inserimenti e cancellazioni
      - B tree di ordine m
        
        la radice o è una foglia oppure ha almeno due figli
        
        ogni nodo interno ha un numero di figli k tale che m/2 ≤ k ≤ m
        
        ad ogni nodo interno con k figli sono associate k-1 chiavi ordinate
        
        bilanciamento
        
        tutti i cammini della radice ad una qualsiasi delle foglie hanno la stessa lunghezza
        
        occorre ristrutturare l'albero a seguito di:
        
        inserimento di una chiave
        
        modifica
        
        cancellazione
        
        operazioni
        
        inserimento di una nuova chiave
        
        ricerca del nodo in cui effettuare l'inserimento
        
        inserimento della nuova chiave nel nodo
        
        splitting
        
        quando un nodo trabocca (overflow) il suo contenuto di m+1 chiavi è diviso in due parti:
        
        le (m/2) chiavi minori restano in un nodo
        
        le m-(m/2) chiavi più grandi in un'altro nodo
        
        la chiave mediana è memorizzata nel nodo padre dove funge da separatore
        
        se anche il nodo padre è completo, l'albero aumenta di livello (splitting del padre)
        
        cancellazione di una chiave
        
        ricerca del nodo in cui effettuare l'inserimento
        
        cancellazione della chiave
        
        ridistribuzione
        
        si adotta quando si cancella un nodo e l'albero si sbilancia
      - B+ tree di ordine m
        
        ha le stesse proprietà del B tree ma:
        
        i puntatori ai dati (blocco/record) sono memorizzati solo nei nodi foglia
        
        i nodi foglia sono collegati tra loro per fornire un accesso ordinato al campo di ricerca ed al record
        
        i nodi foglia sono simili al primo livello di un indice, i nodi interni corrispondono agli altri livelli di un indice multilivello
- transazione
  - unità elementare di lavoro svolta da un modulo che accede alla base di dati
  - lavoro:
    - lettura
    - inserimento
    - modifica
    - cancellazione
  - proprietà ACID
    - atomicità
      - la transazione è un'unità indivisibile di esecuzione
      - gli aggiornamenti che essa effettua vengono eseguiti tutti o nessuno
      - in caso di errore o non completamento delle operazioni sui dati la transazione deve:
        
        essere disfatta (undo) se non è stato eseguito il commit
        
        essere rifatta (redo) se è stato eseguito il commit
    - consistenza
      - le operazioni effettuate da una transazione devono rispettare i vincoli di integrità sui dati
      - i vincoli sono controllati:
        
        all'atto dell'operazione
        
        dopo il commit
        
        il non rispetto comporta un undo
    - isolamento
      - l'effetto di più transazioni eseguite in concorrenza deve essere uguale a quello che si otterrebbe eseguendo singolarmente ciascuna transazione
      - evita l'effetto domino: disfacimento in cascata di tutte le transazioni nel caso in cui una di esse non vada a buon fine
    - durabilità
      - l'effetto di una transazione portata a termine correttamente non deve venir perso (persistenza)
  - anamalie delle transazioni
    - sono causate dall'esecuzione concorrente delle transazioni:
      - perdita di aggiornamento
      - letture sporche
      - letture inconsistenti
      - aggiornamento fantasma
  - conflitto
    - due transazioni in esecuzione sono in conflitto se
      - accedono alla stessa pagina
      - almeno una di esse effettua una scrittura
  - scheduler
    - modulo di sistema che gestisce le operazioni di lettura e scrittura
    - determina se le richieste fatte da una transazione possono essere soddisfatte o no
    - accetta o rifiuta esecuzioni concorrenti durante l'evoluzione delle transazioni in modo da evitare anomalie
    - accetta o rifiuta uno schedule durante l'evoluzione delle transazioni in modo da evitare anomalie
  - definizioni formali
    - transazione
      - t₁: r(x)₁ r(y)₁ w(y)₁ r(z)₁
    - schedule
      - S₁: r(x)₁ r(y)₂ r(y)₃ w(y)₁ r(z)₃
      - t₁ t₂ t₃...
  - schedule seriale
    - le azioni di tutte le transazioni compaiono in sequenza senza essere inframezzate da azioni di altre transazioni
      - [r(x)₁ r(y)₁ w(y)₁] [r(x)₂ r(z)₂] [r(x)₃ r(y)₃ w(y)₃]
  - controllo della concorrenza
    - utilizzo di meccanismi di controllo della concorrenza che assicurano schedule seriali o equivalenti
    - LOCKING
      - principale meccanismo adottato da quasi tutti i DBMS commerciali
      - è basato sull'utilizzo di tre primitive che accompagnano ogni operazione di lettura e scrittura, rispettando un insieme di regole
        
        r_lock
        
        w_lock
        
        unlock
      - protocollo di LOCKING
        
        ogni operazione di lettura deve essere
        
        preceduta da un r_lock
        
        seguita da un unlock
        
        (lock condiviso o shared)
        
        ogni operazione di scrittura deve essere
        
        preceduta da un w_lock
        
        seguita da un unlock
        
        (lock esclusivo o exclusive)
      - transazione BENFORMATA
        
        transazione che segue il protocollo di locking
      - tabella dei conflitti
        
        il gestore della concorrenza riceve le richieste identificate dalla transazione e dal dato a cui la stessa richiede di accedere
      - locking a 2 fasi (2PL)
        
        ulteriore restrizioni al locking per garantire uno schedule seriale
        
        una transazione dopo aver rilasciato un lock non può acquisirne altri:
        
        1P) richiesta di tutti i LOCK (fase crescente)
        
        2P) rilascio di tutti i LOCK (fase calante)
        
        questo è valido se l'esito della transazione non è un ABORT
      - locking a 2 fasi stretto (2PL strict)
        
        i lock di una transazione possono essere rilasciati solo dopo aver correttamente effettuato le operazioni di commit/abort
        
        uno schedule 2PL è equivalente ad uno schedule seriale che riporti i conflitti nello stesso ordine
      - timestamp
        
        identificatore associato alla transazione considerata come evento temporale
        
        determina un ordinamento temporale delle transazioni
        
        è poco utilizzato perchè comporta:
        
        uccisione di troppe transazioni
        
        eccessiva bufferizzazione delle scritture
        
        politica dello scheduler
        
        ogni transazione non può leggere o scrivere un dato scritto da una transazione con timestamp superiore al suo
        
        ogni transazione non può scrivere un dato che è già stato letto da una transazione con timestamp superiore al suo
      - deadlock
        
        blocco dell'esecuzione dovuta al raggiungimento di una posizione di stallo tra i lock
        
        rimedi
        
        timeout
        
        ogni transazione viene abortita se ancora attiva dopo un intervallo di tempo prefissato (più utilizzato)
        
        prevenzione
        
        una transazione richiede di seguito tutte le sue risorse (difficoltoso)
        
        timestamp e rispetto precedenze
        
        (50% uccisa 50% attende)
- affidabilità transazioni
  - astrazione della memoria stabile
  - unità disco MIRRORED
  - file di LOG
    - file sequenziale che registra
      - in ordine temporale
      - le azioni sui dati compiute dalle transazioni
    - bufferizzazione delle operazioni
    - record di transizione
      - begin, commit, abort
        
        in ordine temporale
      - Update (U), Insert (I), Delete (D)
        
        Before Image (BI) → U,D
        
        After Image (AI) → U,I
    - checkpoint
      - punti di "controllo" che vengono memorizzati periodicamente
      - flush in memoria di transazioni con record di commit o abort
    - dump
      - backup di
        
        tutta la base di dati
        
        aree aggiornate
        
        aree danneggiate
      - viene effettuato in background a transazioni ferme
  - protocolli di affidabilità
    - WAL (Write Ahead Log)
      - scrittura della BI prima dell'update
      - consente UNDO
    - Commit Precedenza
      - scrittura della AI prima del commit
      - consente REDO
  - gestione dei guasti
    - ripresa a caldo
      - basata sui file di log:
        
        a) ripercorre indietro il log fino ad individuare l'ultimo checkpoint valido
        
        b) ripercorre indietro il log: UNDO delle transizioni attive al checkpoint ma che non hanno effettuato commit/abort; si arriva alla più vecchia transazione che non ha effettuato commit/abort
        
        le transazioni sono disfatte copiando nel record del file oggetto della transazione la Before Image (BI)
        
        c) ripercorre in avanti il log con REDO di transazioni che hanno effettuato commit o abort
        
        le transazioni sono rifatte copiando nel record del file oggetto della transazione la After Image (AI)
    - ripresa a freddo
      - basata su dump + ripresa a caldo
      - a) si ricopia dal dump la parte deteriorata
      - b) si ripercorre in avanti il log con REDO riproducendo la situazione precedente al guasto
      - c) si esegue la ripresa a caldo