Base di Dati IV · Appunti Universitari

Your support helps keep this website running. Please consider supporting this project. SPONSOR DONATE

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