Riassunto Base Dati II PDF

Preview

Summary

Sommario Sommario Lezione - Dipendenze Funzionali Forme Normali Lezione Algoritmo per la copertura minimale Dipendenze multivalore (MVD) Decomposizione LJ in relazioni 4NF............................................................................................... Lezione Il Sistema Informativo Il...

Description

BASI DI DATI 2

Sommario Sommario ............................................................................................................................................. 1 Lezione 1 .............................................................................................................................................. 3 Dipendenze Funzionali ................................................................................................................ 3 Forme Normali ................................................................................................................................. 3 Lezione 2 .............................................................................................................................................. 5 Algoritmo per la copertura minimale ............................................................................................... 5 Dipendenze multivalore (MVD) ...................................................................................................... 6 Decomposizione LJ in relazioni 4NF............................................................................................... 6 Lezione 3 .............................................................................................................................................. 7 Il Sistema Informativo ..................................................................................................................... 7 Il ciclo di vita ................................................................................................................................... 7 Fasi del Macro Ciclo di vita ............................................................................................................. 7 Fasi del Micro Ciclo di vita.............................................................................................................. 7 Il processo di progettazione di un database ..................................................................................... 8 La progettazione fisica nei database relazionali .............................................................................. 9 Denormalizzare uno schema .......................................................................................................... 10 Lezione 4 ............................................................................................................................................ 11 Memorizzazione di record ed organizzazione dei file ................................................................... 11 Tecnologia RAID ........................................................................................................................... 12 Lezione 5 ............................................................................................................................................ 13 Indici .............................................................................................................................................. 13 Alberi di ricerca ............................................................................................................................. 15 Definizione formale B-Tree ........................................................................................................... 15 I B+-Tree ......................................................................................................................................... 16 Lezione 6 ............................................................................................................................................ 18 Gestione delle transazioni .............................................................................................................. 18 Algoritmo per la serializzabilità ................................................................................................. 21 Lezione 7 ............................................................................................................................................ 22 Tecniche per il controllo della concorrenza ............................................................................... 22 Tecniche di Locking ................................................................................................................... 22 Regole per lock shared/esclusivi ................................................................................................ 24 Il protocollo Two-Phase Locking ............................................................................................... 24 Lezione 8 ............................................................................................................................................ 26 Tecniche di Recovery ................................................................................................................. 26 Protocollo WAL (Write-Ahead Logging) ................................................................................... 27 Tecniche di recovery basate su aggiornamento differito............................................................ 27 1

BASI DI DATI 2 Recovery con deferred update in ambiente multiutente............................................................. 27 Tecniche di Recovery basate su Immediate Update................................................................... 28 Backup-Restore del DB ............................................................................................................. 28 Lezione 9 ............................................................................................................................................ 29 Concetti sui database Object-Oriented ....................................................................................... 29 Gli Oggetti.................................................................................................................................. 29 Incapsulamento di Operazioni, Metodi e Persistenza ................................................................ 30 Gerarchie ed Ereditarietà nei DBMS O-O ................................................................................. 31 Oggetti Complessi ...................................................................................................................... 31 Lezione 10 .......................................................................................................................................... 32 Standard, linguaggi e progettazione di database ad oggetti ....................................................... 32 L’Object Definition Language ................................................................................................... 33 L’Object Query Language .......................................................................................................... 33 Progettazione concettuale di database ad oggetti ....................................................................... 35 Lezione 11 – Basi di Dati Distribuite ed Architetture Client-Server ................................................. 36 La tecnologia per i DDB ............................................................................................................ 36 Tipi di architetture multiprocessore ........................................................................................... 36 Architettura di un DDB .............................................................................................................. 36 Tipi di trasparenza ...................................................................................................................... 36 Funzionalità addizionali caratteristiche dei DDBMS ................................................................ 37 Frammentazione dei Dati ........................................................................................................... 38 Replicazione ed Allocazione di dati ........................................................................................... 39 Esempi di frammentazione, allocazione e replicazione ............................................................. 40 Esempio: Conti correnti bancari ........................................................................................................ 42 Livelli di trasparenza .................................................................................................................. 43 Efficienza ................................................................................................................................... 43 Tipi di DDB................................................................................................................................ 43 Sistemi per la gestione dei DB Federati ..................................................................................... 44 Architettura Client-Server .......................................................................................................... 45 Lezione 12 – XML e basi di dati in Internet ...................................................................................... 47 Approcci alla memorizzazione di documenti XML ....................................................................... 48 XPath.............................................................................................................................................. 49 XQuery ........................................................................................................................................... 50 Esempi............................................................................................................................................ 50

2

BASI DI DATI 2

Lezione 1 Nella bisogna utilizzare una s , ovvero l'utente deve capire, in modo facile, il contenuto degli attributi in modo da y. Esistono delle di per disegni di schemi di relazioni:  degli attributi;  riduzioni dei dalle tuple;  riduzione dei delle tuple;  non consentire . La

consente di che si dividono in: 





. Inoltre si devono evitare

che non possono essere inseriti in questo modo (es. se un dipartimento ha un manager non posso inserire un dipartimento senza avere il manager). la , ad esempio se ho una tabella impiegato con un attributo dipartimento e non ho una tabella solo per dipartimento, cancellando l'ultimo impiegato di quel dipartimento eliminerei l'esistenza di quest’ultimo dall'intero DB. se cambio il valore di un devo tutte le altre che hanno quel valore, altrimenti l’attributo diventa inconsistente.

Un altro aspetto da considerare è l'eliminazione dei . Si p per eliminare gli attributi che causano la presenza di valori null. ed inoltre può dare nel fare il Bisogna considerare anche le , ad esempio una ed potrebbe portare ad un join completamente sbagliato che genera tuple che non rispecchiano la realtà. Se consideriamo una tabella impiegato con l'attributo progetto e una tabella dove si considera il progetto (in generale) con tutte le ore di lavoro che ha richiesto, se eseguiamo un join attribuiamo tutte quelle ore ad ogni impiegato.

Dipendenze Funzionali , sono denotate da X → Y (Y è funzionalmente dipendente da X). La cosa importante è che per vedere le inferenze di X, si effettua la chiusura denotata da X+, ovvero si vede a partire da X tutti gli attributi che si possono raggiungere. La notazione F ‡ X → Y denota che la FD X → Y è inferita da F.   

(IR 1) (IR 2) (IR 3)

Se 𝑋 ⊇ 𝑌allora X → Y X → Y ‡ XZ → YZ ,X → Y , Y → Z- ‡ X → Z

Inoltre: (IR 4) Decomposition o Projective ,X → YZ- ‡ X → Z (IR 5) Union ,X → Y , X → Z- ‡ X → YZ (IR 6) Pseudotransitive , X → Y , WY → Z- ‡ WX → Z È stato provato che le   

).

Forme Normali 3

BASI DI DATI 2 . Gli schemi devono superare il test altrimenti la relazione che viola il test deve essere decomposta in tante relazioni tali che singolarmente superino il test. (1NF) . La soluzione è quella di rimuovere gli attributi della relazione annidata, crearne una nuova e propagare la chiave primaria in essa. (2NF) (ovvero se la chiave primaria non è composta da un solo attributo , ma devono dipendere da tutta la chiave). Se uno schema di relazione non è in 2NF può essere ulteriormente normalizzato in un certo numero di relazioni in 2NF, in cui gli attributi non primi sono associati solo con la parte di chiave primaria da cui sono funzionalmente dipendenti pienamente. (3NF)

ovvero tutti gli attributi dell'entità e non da attributi che sono dipendenti dalla chiave primaria. Inoltre la

relazione deve essere 2NF.

→ A, allora X è una superchiave di R.

4

BASI DI DATI 2

Lezione 2 La progettazione di un DB relazionale può avvenire in modo Top-Down (si parte dall'ER e si effettua la normalizzazione) oppure Bottom-Up (si considera lo schema del DB solo in termini di dipendenze funzionali e poi si effettua la normalizzazione). Nell'applicare la normalizzazione bisogna conservare gli attributi (basta controllare se gli attributi di ogni entità sono presenti nel nuovo schema) e le dipendenze (bisogna “navigare” nel nuovo schema e per ogni relazione dobbiamo vedere se la parte destra della dipendenza è raggiungibile partendo da quella sinistra, percorrendo cammini dettati da una dipendenza).

Algoritmo per la copertura minimale Una copertura minimale di un insieme E di dipendenze funzionali è un insieme minimale F di dipendenze che è equivalente a E. Si parte dall'insieme di tutte le dipendenze funzionali possibili, poi si procede ad eliminare le entità che non comportano modifiche delle dipendenze funzionali. Algoritmo di sintesi relazionale Decomposizione dependency-preserving in schemi di relazione 3NF: 1. trovare una copertura minimale G di F; 2. per ogni parte sinistra X di una dipendenza funzionale che appare in G, creare uno schema di relazione {X U A1 U A2… U Am- in D dove X → A1, X → A2, … ,X → Am sono le sole dipendenze in G aventi X come parte sinistra. 3. mettere in uno schema di relazione singolo tutti gli attributi rimanenti, per garantire la proprietà di attribute-preservation. Algoritmo Lossless Join Questo algoritmo consente di verificare se lo schema rispetta la proprietà di join non additivo, ovvero se si possono effettuare join tra le tabelle che consentono di ricavare tutte le informazioni memorizzate nel database. Una decomposizione con lossless join garantisce che non vengano generate tuple spurie applicando una operazione di natural join alle relazioni nella decomposizione. La teoria delle decomposizioni lossless join si basa sull'assunzione che nessun valore null è ammesso per gli attributi di join. Si parte mettendo sulle righe le relazioni del nuovo schema e sulle colonne gli attributi e tutte le righe bij dove l'indice i indica la riga e j la colonna. Poi per ogni relazione si mette a j in corrispondenza degli attributi presenti nella relazione (sia parte destra che sinistra). Poi si procede iterativamente fino a quando o non si ha una riga con tutte a oppure non avvengono modifiche nel modo seguente: le dipendenze vengono valutate a coppia, per ogni 2 dipendenze che hanno la parte sinistra in comune (ovvero hanno aj nella tabella) si aggiornano le tabelle della parte sinistra copiando il valore aj dall'altra relazione. Se alla fine si ha una riga con tutti valori aj allora si rispetta il lossless join altrimenti no.

5

BASI DI DATI 2

Dipendenze multivalore (MVD) . In presenza di due o più attributi indipendenti multivalued nello stesso schema, siamo costretti a ripetere ogni valore di un attributo con un valore dell'altro.

Relazioni contenenti MVD non-trivial tendono ad essere relazioni “tutta chiave”, nel senso che la chiave è formata da tutti gli attributi.

ENAME ↠ PNAME è una MVD banale Esempio: ENAME ↠ PNAME, ENAME ↠ DNAME

ma ENAME non è una superchiave.

EMP non è in 4NF. Si scompone in:

Decomposizione LJ in relazioni 4NF Decomposizione di un schema in relazioni 4NF con la proprietà LJ: porre D = {R}; finché esiste uno schema di relazione Q in D che non è in 4NF { scegliere uno schema di relazione Q in D che non è in 4NF; trovare una MVD non banale X -» Y in Q che viola 4NF; rimpiazzare Q in D con due schemi (Q – Y) e (X U Y); } 6

BASI DI DATI 2

Lezione 3 Il Sistema Informativo Il sistema informativo è composto da:  Dati  DBMS  Hardware  Media di memorizzazione  Applicativi che interagiscono con i dati  Personale che gestisce o usa il sistema  Gli applicativi che gestiscono l'aggiornamento dei dati  I programmatori che sviluppano gli applicativi

Il ciclo di vita Il ciclo di vita di un sistema informativo (risorsa per la raccolta, gestione, uso e disseminazione) è detto macro ciclo di vita. Il ciclo di vita di un sistema di base di dati è detto micro ciclo di vita.

Fasi del Macro Ciclo di vita 1. Analisi di fattibilità: si analizzano le aree di applicazione, si effettuano gli studi dei costi/benefici e si determina la complessità del sistema. 2. Raccolta ed analisi dei requisiti: consiste nella raccolta dei requisiti e definizione delle funzionalità del sistema. 3. Progettazione: si divide in progettazione del database e progettazione degli applicativi. 4. Implementazione: si implementa il Sistema Informativo, si carica il database e si implementano e testano le transazioni. 5. Validazione e Testing: si verifica che il sistema soddisfi i requisiti e le performance richieste. 6. Rilascio e manutenzione: questa fase può essere preceduta da una di addestramento del personale. Se emergono nuove funzionalità da implementare si devono ripetere tutti i passi precedenti.

Fasi del Micro Ciclo di vita 1. Definizione del Sistema: si definisce l'ambito del sistema, i suoi utenti e le funzionalità. Si identificano le interfacce per gli utenti, i vincoli sui tempi di risposta ed i requisiti hardware. 2. Progettazione della Base di Dati: si realizza la progettazione logica e fisica per il DBMS scelto. 3. Implementazione della base di dati: si creano i file del database vuoti e si implementa dell'eventuale software applicativo di supporto. 4. Caricamento/Conversione dei dati: si popola il database, o si utilizzano file esistenti o si crea da capo. 5. Conversione delle applicazioni: si convertono le vecchie applicazioni software al nuovo sistema. 6. Test e Validazione: si testa il nuovo sistema. 7. Operation: il sistema di base di dati con le applicazioni diventa operativo. All'inizio si preferisce associare l'utilizzo del nuovo sistema in concomitanza con il vecchio. 8. Controllo e Manutenzione: il sistema è in continuo monitoraggio.

7

BASI DI DATI 2

Il processo di progettazione di un database Gli scopi della fase di progettazione sono: 1. soddisfare i requisiti sui dati che interessano gli utenti e a cui accedono le applicazioni; 2. fornire una strutturazione delle informazioni naturale e facile da comprendere; 3. soddisfare i requisiti di elaborazione e di prestazioni (tempo di risposta, spazio di memorizzazione). È difficile raggiungere tutti gli scopi perché alcuni sono in contrasto tra loro. La progettazione di un database è composta da: 1. Raccolta ed analisi dei requisiti:  Identificare le aree di applicazione, gli utenti che useranno il DB.  Analizzare la documentazione esistente.  Esaminare il contesto operativo e l'utilizzo pianificato delle informazioni, inclusa l'analisi delle transazioni e la specifica dei dati di input e output delle transazioni.  Intervistare gli utenti finali per determinare le priorità di importanza.  Design dello schema concettuale, che si divide in due attività: i. (Progettazione dello schema concettuale) Lo scopo dello schema concettuale è fornire una comprensione completa della struttura, semantica, relazioni e vincoli del database. È una descrizione stabile del contenuto. Un data model di alto livello deve godere di tali proprietà: o Espressività: deve permettere una facile distinzione tra tipi di dati, relazioni e vincoli. o Semplicità e comprensibilità: il modello deve essere semplice per facilitare la comprensione. o Minimalità: dovrebb...