Basi di dati - appunti

Selezione e proiezione commutano (se F si riferisce esclusivamente ad attributi in Y): π (σ (E)) σ (π (E)) ≡ Y F F Y

“Push-down” della selezione rispetto al join (se F è sullo schema di E1): σ (E1 E2) σ (E1 ) E2 ≡ ⨝ ⨝F F

Usualmente un RDBMS cerca di eliminare quanto prima gli attributi che non servono per produrre il risultato di una query. Un attributo A è utile se è richiesto in output o è necessario per un operatore che non è stato ancora eseguito.

Esempio: nome, cognome e stipendio degli impiegati che lavorano nelle sedi di Bologna:

PROGETTAZIONE LOGICA

Obiettivo della fase di progettazione logica è pervenire, a partire dallo schema concettuale, a uno schema logico che rappresenti in modo fedele i concetti e i requisiti analizzati e che sia, al tempo stesso, “efficiente”.

L’efficienza è legata alle prestazioni, ma poiché queste non sono valutabili precisamente,

nello schema relazionale. In altre parole, il mapping M definisce come ogni entità, relazione e attributo nello schema concettuale viene rappresentato come una tabella, una chiave primaria e attributi nella tabella relazionale. Quando si dice che uno schema relazionale rappresenta "fedelmente" uno schema concettuale, significa che il mapping M è tale che ogni stato legale del database nello schema concettuale può essere rappresentato esattamente nello schema relazionale. Ciò significa che tutte le informazioni documentate nello schema concettuale possono essere memorizzate e recuperate nello schema relazionale. Inoltre, la fedeltà implica che il mapping M preserva le relazioni tra le entità e gli attributi nello schema concettuale. Ad esempio, se due entità sono collegate da una relazione nel diagramma E/R, il mapping M garantirà che le tabelle corrispondenti nello schema relazionale abbiano le chiavi esterne corrette per rappresentare questa relazione. In sintesi, la fedeltà tra uno schema concettuale e uno schema relazionale significa che il mapping M consente di rappresentare esattamente le informazioni nello schema concettuale nel database relazionale, preservando le relazioni tra le entità e gli attributi.stato db di DB .conc conc rel La progettazione preserva l'informazione se M è totale e iniettiva: - (totale) per ogni stato db di DB esiste uno stato db di DB tale che M(db) = db; conc rel conc rel - (iniettiva) non esistono due stati db1conc e db2conc tali che M(db1conc) = M(db2conc). Preservare l'informazione -> la definizione intuitivamente asserisce che lo schema relazionale può contenere i dati dello schema E/R(totalità) e che si può "ritornare indietro" (iniettività). La progettazione garantisce l'equivalenza se preserva l'informazione e per ogni stato legale db di DB esiste uno stato legale db direl tale che M(db) = db. La definizione intuitivamente asserisce che esiste una biiezione tra gli insiemi di stati legali.conc rel In pratica la traduzione da schema E/R a schema relazionale avviene operando una sequenza di trasformazioni/traduzioni semplici, per ognuna delle quali.è altrettanto semplice rispettare regole che garantiscono l'equivalenza. Per quanto visto, possiamo dividere queste regole in: - regole che preservano l'informazione (regole sulla "struttura"); - regole aggiuntive che garantiscono l'equivalenza (regole sui vincoli). L'equivalenza può comunque essere solo in parte garantita dal DDL di SQL, infatti alcuni vincoli non possono essere direttamente espressi in SQL. La progettazione logica può essere articolata in due fasi principali: 1. Ristrutturazione: - eliminazione dallo schema E/R dei costrutti che non possono essere direttamente rappresentati nel modello logico relazionale, ovvero attributi multivalore e gerarchie di generalizzazione; - partizionamento/accorpamento di entità e associazioni; - scelta degli identificatori principali. 2. Traduzione: si mappano i costrutti residui in elementi del modello relazionale. La ristrutturazione si pone l'obiettivo di semplificare la traduzione e

“ottimizzare" le prestazioni.

Per confrontare tra loro diverse alternative bisogna conoscere, almeno in maniera approssimativa, il “carico di lavoro”, ovvero le principali operazioni che la base dati dovrà supportare e i “volumi” dei dati in gioco.

Regola 80-20: il 20% delle operazioni produce l’80% del carico.

Gli indicatori che deriviamo considerano due aspetti:

• spazio: numero di istanze (di entità e associazioni) previste;
• tempo: numero di istanze visitate durante un’operazione.

Tavola dei volumi

Specifica il numero stimato di istanze per ogni entità (E) e associazione (R) dello schema.

I valori sono necessariamente approssimati, ma indicativi.

Descrizione delle operazioni

L’analisi delle operazioni principali richiede la codifica di:

• tipo dell’operazione: Interattiva (I) o Batch (B);
• frequenza: numero medio di esecuzioni in un certo periodo di tempo;
• schema di navigazione: frammento dello schema

E/R interessato dall'operazione sul quale viene evidenziato (con frecce) il "cammino logico" da percorrere per accedere alle informazioni di interesse. Per ogni operazione si costruisce una tavola degli accessi basata sullo schema di navigazione:

• Il campo costrutto specifica il tipo di concetto (entità o associazione);
• Nel campo accessi si conta il numero degli accessi;
• Il campo tipo è riferito al tipo di operazione: le operazioni di scrittura (S) sono più onerose di quelle di lettura (L). Il costo degli accessi in scrittura è in genere considerato doppio rispetto a quello delle letture.

Per ogni entità e per ogni associazione interessate dall'operazione, la tavola degli accessi riporta il numero di istanze interessate e il tipo di accesso (L: lettura; S: scrittura). Il numero delle istanze si ricava dalla tavola dei volumi mediante semplici operazioni (assumendo uniformità nella distribuzione dei valori): ad esempio in

media ogni impiegato partecipa a 6000/2000 = 3 progetti.

Analisi delle ridondanze

Una ridondanza in uno schema E-R è un'informazione significativa ma derivabile da altre. In questa fase si decide se eliminare o meno le ridondanze eventualmente presenti; è quindi comunque importante averle individuate in fase di progettazione concettuale.

Le possibili ridondanze riguardano attributi derivabili da altri attributi e associazioni derivabili dalla composizione di altre associazioni (cicli).

Mantenendo una ridondanza si semplificano alcune interrogazioni, ma si appesantiscono gli aggiornamenti e si occupa maggior spazio.

Esempio: L'attributo NumeroResidenti è derivabile da un'operazione di conteggio delle istanze di persona residenti in una città.

Si considerano innanzitutto le operazioni influenzate dalla ridondanza, considerando anche le loro frequenze di esecuzione:

operazione 1: inserisci una nuova persona con la relativa città di

residenza•(500 volte al giorno);

operazione 2: visualizza tutti i dati di una città (incluso il numero di residenti)•(2 volte al giorno);

E si costruiscono le tavole degli accessi. È importante considerare la frequenza delle operazioni:

con ridondanza:

op 1: 1500 accessi in scrittura e 500 accessi in lettura al giorno;

op 2: 2 accessi in lettura al giorno;

totale: 3502 accessi al giorno;

senza ridondanza:

op 1: 1000 accessi in scrittura al giorno;

op 2: 10002 accessi in lettura al giorno;

totale: 12002 accessi al giorno.

Si decide pertanto di mantenere la ridondanza, privilegiando l’efficienza.

In generale si devono fare anche considerazioni sullo spazio in più richiesto per mantenere la ridondanza.

Eliminazione delle gerarchie

Il modello relazionale non può rappresentare direttamente le gerarchie di generalizzazione.

Entità e associazioni sono invece direttamente rappresentabili. Si eliminano perciò le gerarchie, sostituendole con entità.

E relazioni. Vi sono 3 possibilità (più altre soluzioni intermedie).

Collasso verso l'alto: Accorpare le entità figlie nel genitore. "Tipo" è un attributo selettore che specifica se una singola istanza di E appartiene a una delle N sotto-entità.

Copertura totale esclusiva: Tipo assume N valori, quante sono le sotto-entità;

Parziale esclusiva: Tipo assume N+1 valori; il valore in più serve per le istanze che non appartengono a nessuna sotto-entità;

Sovrapposta: occorrono tanti selettori quante sono le sotto-entità, ciascuno a valore booleano Tipo_i, che è vero per ogni istanza di E che appartiene a E_i; se la copertura è parziale i selettori possono essere tutti falsi, oppure si può aggiungere un selettore.

Le eventuali associazioni connesse alle sotto-entità si trasportano su E, le eventuali cardinalità minime diventano 0.

Collasso verso il basso: Accorpare il genitore

nelle entità figlie. Se la copertura non è completa il collasso verso il basso non si può applicare: non si saprebbe infatti dove collocare le istanze di E che non sono né in E1, né in E2. Se la copertura non è esclusiva introduce ridondanza: una certa istanza può essere sia in E1 sia in E2, e quindi si rappresentano due volte gli attributi che provengono da E. Sostituire con associazioni. Tutte le entità vengono mantenute: le entità figlie sono in associazione binaria con l'entità padre e sono identificate esternamente. La sostituzione con associazioni è sempre possibile indipendentemente dalla copertura della gerarchia. La scelta fra le alternative illustrate si può fare adottando un metodo simile a quello visto per l'analisi delle ridondanze, considerando sia il numero degli accessi sia l'occupazione di spazio. È possibile seguire alcune semplici regole generali (ovvero: mantieni)insieme ciò che viene usato insieme): - conviene se gli accessi all'entità padre e alle entità figlie sono contestuali; - conviene se gli accessi alle entità figlie sono distinti, ma d'altra parte è possibile solo con generalizzazioni totali; - conviene se gli accessi alle entità figlie sono separati dagli accessi al padre. Sono anche possibili soluzioni "ibride", soprattutto in presenza di gerarchie a più livelli -> Partizionamenti e accorpamenti È possibile ristrutturare lo schema accorpando o partizionando entità e associazioni. Queste ristrutturazioni sono effettuate per rendere più efficienti le operazioni in base al principio già visto, ovvero: gli accessi si riducono separando attributi di un concetto che vengono acceduti separatamente e raggruppando attributi di concetti diversi a cui si accede insieme. I casi principali sono: - partizionamento verticale di entità