Base di Dati III

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

• DF (dipendenza funzionale)
  • esprime un vincolo di integrità del modello relazionale
  • mette in correlazione alcuni attributi
  • è una proprietà della semantica della Base di Dati che vale per l'ambiente specifico di modellazione (non è detto che una particolare dipendenza funzionale valga in altri database che si riferiscono ad altri contesti)
    • esempi
      • Stato, Numero patente → SSN
      • CAP → Prefisso telefonico
  • definizione
    • data una relazione r(X) e due sottoinsiemi di attributi non vuoti Y, Z di X:
    • esiste su r(X) una dipendenza funzionale DF tra Y e Z se, per ogni coppia di tuple t1 e t2 di r risulta:
    • t1(Y) = t2(Y) → t1(Z) = t2(Z)
    • NOTA
      • la notazione X → Y significa X determina Y, ovvero Y dipende funzionalmente da X
    • esempio
      • Impiegato → Stipendio
  • DF non banale
    • Y → Z è non banale se nessun attributo di Z compare tra gli attributi di Y
    • esempio di DF banale
      • Progetto → Progetto
  • implicazione
    • dato un insieme F di dipendenze funzionali per uno schema R, e una dipendenza funzionale X → Y si dice che F IMPLICA LOGICAMENTE X → Yse ogni relazione r di schema R che verifica le dipendenze funzionali in F verifica anche X → Y
    • esempio
      • F = {A → B, B → C} ⇒ A → C
      • F implica logicamente A → C e si scrive: F |= A → C
  • chiusura
    • la chiusura F+ di un insieme F di dipendenze funzionali è l'insieme di tutte le dipendenze funzionali implicate da F
    • F+ = {X → Y | F |= X → Y}
    • esempio
      • R(A,B,C) e F = {A → B, B → C}
      • F+ contiene tutte le dipendenze X → Y che verificano una delle tre condizioni:
        • 1. X contiene A
        • 2. X contiene B ma non A, Y non contiene A
        • 3. X → Y è la dipendenza C → C
      • F+ contiene ad esempio: ABC → BC, AB → BC, A → C, BC → B
  • assiomi di Armstrong (1974)
    • insieme di regole che consentono di calcolare (inferire) tutte le dipendenze in F+
    • gli assiomi possono essere
      • corretti (sound)
        • se applicati ad F generano solo dipendenza in F+
      • completi
        • se consentono di generare tutte le dipendenze di F+
    • assiomi
      • rifflesività
        • se Y ⊆ X allora F |= X → Y
        • NB: genera dipendenze banali, cioè dipendenze in cui la parte destra è contenuta nella parte sinistra
      • addittività
        • se X → Y allora F |= XZ → YZ
      • transitività
        • se X → Y e Y → Z allora F |= X → Z
    • regole derivate
      • unione
        • {X → Y, X → Z} |= X → YZ
      • pseudotransitività
        • {X → Y, WY → Z} |= XW → Z
      • decomposizione
        • se Z ⊆ Y, X → Y |= X → Z
    • concetto di chiave
      • dato uno schema R(A₁, A₂, ..., A_N) ed un insieme di dipendenze funzionali F, un sottoinsieme X di attributi di R è una chiave se
        • X → A₁, A₂, ..., A_Nè in F+
        • per nessun Y sottoinsieme proprio di X si verifica che
          • Y → A₁, A₂, ..., A_Nè in F+ (condizione di minimalità)
    • chiusura di un insieme di attributi
      • dati un insieme di dipendenze funzionali F ed un insieme di attributi X, la chiusura X+ di X rispetto ad F è l'insieme di attributi A tali che:
        • F |= X → A, ossia A tali che X → A
    • calcolare X+ (chiusura degli attributi) è meno costoso che calcolare F+ (chiusura DF), spesso non ci interessa tutto F+ ma solo verificare se contiene una certa dipendenza
    • algoritmo per calcolare X+
      • X+ si calcola incrementalmente
        • a partire da X si uniscono ad X tutti gli attributi in F da esso implicati
          • X += X;
          • do {
            • if ((A → B) AND (A ⊆ X+)) {
              • X += (X+) ∪ B
            • }
          • } while (X+ non si modifica più);
    • esempio di calcolo di X+
      • AB → C, C → A, BC → D, ACD → B, D → EG, BE → C, CG → BD, CE → AG
      • X = BD
      • X+ = BD
      • considero D ed uso D → EG : X+ = BDEG
      • considero BE ed uso BE → C : X+ = BCDEG
      • considero C ed uso C → A : X+ = ABCDEG
      • anche considerando altre dipendenze, X+ non si modifica
    • DF equivalenti
      • due insiemi di dipendenze funzionali F e G si dicono equivalenti se hanno la stessa chiusura
    • copertura minima per un insieme F (G = insieme di dipendenze minimali)
      • dato un insieme di dipendenze funzionali F, la sua copertura minima è un insieme G di DF tali che:
        • la parte destra di ogni dipendenza in G è un singolo attributo (in G non c'è nessun lato destro ridondante)
        • per nessuna X → A in G si ha che (XA)+ = G+ (in G non ci sono dipendenze ridondanti)
        • per nessuna X → A in G e nessun sottoinsieme Z di X si ha che (XAZ)+ = G+ (sul lato sinistro di G non ci sono dipendenze ridondanti)
      • calcolo di G:
        • 1. si sostituisce ad ogni dipendenza del tipo X → A₁, A₂, ..., A_n con X → A₁, X → A₂, ..., X → A_n
        • 2. si sostituiscono le dipendenze con più attributi sul lato sinistro con dipendenze che hanno un solo attributo (l'ordine con cui si esaminano le componenti può influire sul risultato)
        • 3. si eliminano le dipendenze banali o ridondanti
• normalizzazione
  • serve a progettare bene gli schemi definendo più relazioni con meno attributi per evitare inefficienze nelle prestazioni
  • è un processo di analisi degli schemi basato sul rilevamento delle DF (dipendenze funzionali) e le chiavi primarie
  • finalità
    • minimizzare lo spazio di memoria occupato dalle relazioni
    • eliminare le ridondanze
    • evitare le anomalie in:
      • inserimento
      • modifica
      • cancellazione
  • le tabelle vengono decomposte in altre tabelle ciascuna delle quali è riferita ad un singolo oggetto
  • è un processo top-down che sottopone le relazioni a test per stabilirne il livello di forma normale (NF - Normal Form) che garantisce la qualità di una relazione
  • forme normali
    • 1NF - prima forma normale
      • fa parte integrante della definizione del modello relazionale di base (una relazione è sempre in 1NF)
        • tutte le righe hanno lo stesso numero di colonne
        • i valori sono atomici
          • il valore che un qualsiasi attributo assume nella relazione è un valore singolo del dominio dell'attributo
        • non esistono due righe uguali
        • l'ordine delle righe è irrilevante
      • definita per impedire il nesting (annidamento) delle relazioni, ovvero l'inserimento di una relazione nella relazione
      • vieta di esprimere un attributo come struttura
    • 2NF - seconda forma normale
      • effetua test di DF sugli attributi che fanno parte della chiave primaria
      • una relazione la cui chiave è singola (costituita da un solo attributo) è sicuramente in 2NF
      • premesse
        • 1. un attributo si dice PRIMO se fa parte di una chiave candidata, altrimenti si dice NON PRIMO
        • 2. un attributo X si dice che dipende funzionalmente in modo completo da una chiave (non singola) se eliminando uno degli attributi della chiave non è più possibile identificarlo
      • una relazione R è in 2NF se ogni attributo non primo dipende funzionalmente in modo completo dalla chiave primaria di R
      • possono esistere delle dipendenze funzionali in cui degli attributi non primi dipendono da altri attributi non primi
      • esclude la dipendenza di un attributo non primo da una parte della chiave
    • 3NF - terza forma normale
      • elimina le dipendenze transitive di uno o più attributi ottenute attraverso un attributo non chiave
      • dipendenza transitiva
        • si ha quando dati X → Z e Z → Y, Z non è ne chiave candidata, ne sottoinsieme di chiave candidata (attributo primo)
      • una relazione r è in terza forma normale (3NF) se, per ogni DF X → Y definita su di essa, è verificata almeno una delle seguenti condizioni:
        • a) X contiene una chiave K di r (X è una superchiave)
        • b) ogni attributo in Y è contenuto in almeno una chiave di r (Y è primo)
      • in 3NF si ammettono DF che non hanno una chiave a sinistra purchè a destra ci sia un attributo primo
    • BCNF - Boyce Codd Normal Form
      • ha come obiettivo di riportare l'orgine di ogni DF alla chiave della relazione
      • ogni attributo deve dipendere esclusivamente dalla chiave eliminando tutte le altre dipendenze
      • una relazione r è in BCNF se, per ogni DF X → Y definita su di essa, X contiene una chiave K di r (X deve essere una superchiave)
      • una relazione in BCNF è anche 3NF, il contrario non è sempre vero
      • se una relazione ha una sola chiave, le forme normali 3NF e BCNF coincidono
    • 4NF - quarta forma normale
    • 5NF - quinta forma normale
  • decomposizione (scomposizione di schemi)
    • si utilizza per migliorare il livello di forma normale delle relazioni
    • uno schema non normalizzato viene scomposto in schemi normalizzati
    • la scomposizione di una relazione R = {A₁, A₂, ..., A_n} è la sua sostituzione con una collezione C = {R₁, R₂, ..., R_n} tale che R = R₁∪ R₂, ...,∪ R_n(il join di R_i riproduce R)
      • i vari schemi R_i non sono in genere disgiunti
    • proprietà di una decomposizione in R(X)
      • preservazione dell'informazione contenuta in R(X)
        • garantisce la ricostruzione delle informazioni originarie
      • preservazione delle dipendenze funzionali contenute in R(X)
        • garantisce il mantenimento dei vincoli di integrità originari
        • una decomposizione conserva le dipendenze se ciascuna delle dipendenze funzionali dello schema originario coinvolge attributi che compaiono tutti insieme in uno degli schemi decomposti
    • procedura
      • si crea una relazione per ogni gruppo di attributi coinvolti in una dipendenza funzionale
      • si verifica che alla fine una relazione contenga una chiave della relazione originaria
    • decomposizione senza perdita di informazione (lossless join)
      • una relazione r si decompone senza perdita su X1 e X2 se il join delle due proiezioni è uguale ad r stessa (cioè non contiene tuple spurie)
      • dato uno schema R, una sua scomposizione R₁, R₂, ..., R_k ed un insieme F di dipendenze funzionali, si dice che la scomposizione è lossless join (senza perdita) se R è ottenibile come join naturale delle relazioni che la scompongono
    • la verifica che una decomposizione di R(X) in n-relazioni sia lossless è un problema complesso
    • teorema
      • data una relazione R ed un insieme F di DF che valgono su R, una decomposizione di R in due relazioni è lossless se e solo se F+ contiene:
        • R₁∩ R₂→ R₁ oppure
        • R₁∩ R₂→ R₂
        • cioè il join naturale per riottenere R è eseguito su una superchiave di una delle due relazioni in cui R(X) è stata decomposta
    • esistono decomposizioni che preservano i dati ma non le dipendenze funzionali e viceversa
    • qualsiasi schema di relazione ha una decomposizione 3NF lossless che preserva le dipendenze funzionali
    • qualsiasi schema di relazione ha una decomposizione BCNF lossless ma non è garantita la preservazione delle dipendenze funzionali