Progettazione database relazionali - · PDF file2.7.4 Modelli basati sulla logica 26 ......

Progettazione database relazionali

I&T Informatica e Telecomunicazioni S.p.AVia dei Castelli Romani, 900040 Pomezia (Roma) – ItalyTel. +39-6-911611Fax +39-6-91601162http://www.iet.it

I&T Informatica e Telecomunicazioni SpA

Divisione Innovazione TecnologicaArea Data Warehouse

Relatore: Nino [email protected]

Maggio 1998


2I&T Informatica e Telecomunicazioni SpA

Indice

Prefazione 5

1 Database e DBMS 6

1.1 Cos’è un database 61.2 DataBase Management System (DBMS) 61.3 Caratteristiche di un DBMS 7

1.3.1 Dati non volatili 81.3.2 Accesso efficiente a grandi quantità di dati 81.3.3 Modello dati 81.3.4 Linguaggi ad alto livello 81.3.5 Gestione delle transazioni 81.3.6 Accesso controllato 91.3.7 Capacità di recupero 91.3.8 Aspetti negativi 9

2 Progettazione concettuale 10

2.1 Ciclo di vita dei sistemi informativi 102.2 Modello dei dati e fasi di progettazione 11

2.2.1 Progetto concettuale del database 122.2.1.1 Livello vista 132.2.1.2 Schemi ed Istanze 13

2.2.2 Progetto logico del database 132.2.3 Progetto fisico del database 132.2.4 Indipendenza dei dati 14

2.3 Modello Entità-Relazione 142.3.1 Entità 142.3.2 Set di entità 142.3.3 Attributi e chiavi 152.3.4 Relazioni 152.3.5 Relazioni uno-a-uno 152.3.6 Relazione uno-a-molti 162.3.7 Relazione molti-a-molti 162.3.8 Gerarchia ISA 172.3.9 Attributi delle relazioni 17

2.4 Esempio di schema concettuale 182.5 Linee guida per tracciare uno schema entità-relazione 212.6 Utilità del diagramma Entità-Relazione 212.7 Altri modelli dati 22

2.7.1 Modello dati reticolare 222.7.2 Modello dati gerarchico 232.7.3 Modelli orientati agli oggetti 242.7.4 Modelli basati sulla logica 26

3 Progettazione logica 29

3.1 Modello dati logico 29



3.2 Modello dati relazionale 293.3 Rappresentazione dei diagrammi entità-relazione nel modello relazionale 31

3.3.1 Eliminazione delle gerarchie 313.4 Schema logico del database di esempio 343.5 Vincoli di integrità 38

3.5.1 Vincoli di chiave 383.5.2 Vincoli di integrità referenziale 38

3.6 Vantaggi del modello relazionale 403.7 Algebra relazionale 42

3.7.1 Operatori di base 423.7.1.1 Proiezione 423.7.1.2 Selezione o restrizione 423.7.1.3 Prodotto (cartesiano) o congiunzione 423.7.1.4 Ridenominazione 423.7.1.5 Unione 423.7.1.6 Differenza 42

3.7.2 Operatori derivati 443.7.2.1 Intersezione 443.7.2.2 Natural join (giunzione naturale) 443.7.2.3 Join (giunzione) 443.7.2.4 Semijoin 44

3.8 Normalizzazione dei dati 463.8.1 Ridondanza e anomalie 463.8.2 Dipendenze 47

3.8.2.1 Dipendenze funzionali 473.8.2.2 Dipendenze a molti valori 483.8.2.3 Individuazione delle dipendenze 49

3.8.3 Scomposizioni 493.8.3.1 Scomposizione lossless join (senza perdita) 493.8.3.2 Scomposizioni che conservano le dipendenze 51

3.8.4 Prima forma normale 533.8.5 Seconda forma normale 543.8.6 Terza forma normale 553.8.7 Linee guida sulla normalizzazione 573.8.8 Forma normale di Boyce-Codd 58

3.8.8.1 Osservazioni sulla 3NF e BCNF 593.8.8.2 Analisi non accurata 59

3.8.9 Quarta forma normale 613.9 Implementazione dello schema logico 61

4 Progettazione fisica 62

4.1 Strutture fisiche di accesso 624.1.1 Strutture sequenziali 62

4.1.1.1 Struttura sequenziale entry-sequenced (file sequenziale) 624.1.1.2 Struttura sequenziale ISAM (file indicizzato) 62

4.1.1.2.1 Ricerca in un indice 644.1.2 Strutture con accesso calcolato (file hashed) 64

4.1.2.1 Funzioni hash 654.1.3 Strutture ad albero (B-tree) 65

4.2 Progettazione fisica di una base di dati 66

Appendice A - Data Flow Diagram 69



Appendice B - Evoluzione dei modelli di elaborazione 72

B.1 Mainframe e mini 72B.2 Modello a personal computer isolati 72B.3 Modello rete/file server 74B.4 Modello client/server 76B.5 Pregi e difetti del modello client/server 80

Bibliografia 82



Prefazione

Nello svolgimento di ogni attività, sia a livello individuale sia in organizzazioni di ogni dimensione,sono essenziali la disponibilità di informazioni e la capacità di gestirle in modo efficace; ogniorganizzazione è dotata di un sistema informativo, che organizza e gestisce le informazioninecessarie per perseguire gli scopi dell’organizzazione stessa.

Progettare una base di dati significa definire struttura, caratteristiche e contenuto: si tratta, come èfacile immaginare, di un processo nel quale bisogna prendere molte decisioni strategiche e l’uso diopportune metodologie è fondamentale per la realizzazione di un prodotto di alta qualità.

In questo documento viene illustrato ed esemplificato il processo di progettazione concettuale,logica e fisica dei database relazionali (e una visione generale di altri modelli), che permette,partendo dai requisiti dell’utente, di arrivare a produrre strutture di database di buona qualità.



1 Database e DBMS

Chiunque si sia avvicinato al mondo dell’informatica ha sentito parlare di database e DBMS,vediamo che cosa sono.

1.1 Cos’è un database

Un database (o base di dati) è un insieme di informazioni permanenti organizzate secondo unastruttura definita da un modello dati che rappresenta una situazione reale che si vuole automatizzare(gestione magazzino, fatturazione, personale, ecc.).Nei file tradizionali le informazioni sono organizzate in modo sequenziale, mentre in un database,in accordo con il modello dati, vengono stabilite relazioni tra le varie porzioni di informazioni.

Ad esempio, un numero assume significato diverso se è contenuto in file o se è contenuto in undatabase. Nel primo caso è semplicemente un numero che si trova in una certa posizione del file.Invece in un database ad esso è assegnato un ruolo dal modello dati. Può essere il prezzo di unprodotto che è stato venduto come articolo di un ordine avanzato da un cliente. Ognuno di questielementi, prezzo, prodotto, articolo, ordine e cliente, è una entità specificata e correlata alle altre dalmodello dati.

Un database deve soddisfare i seguenti requisiti:

• i dati devono essere organizzati con ridondanza minima, ossia non devono essere inutilmenteduplicati per evitare spreco di risorse di memorizzazione e, soprattutto, per evitare l’oneredella gestione di copie multiple che possono mettere a rischio la consistenza e l’affidabilitàdei dati;

• i dati devono essere utilizzabili contemporaneamente da più utenti, evitando che ognuno creiuna copia propria degli stessi; deve esistere un’unica versione dei dati a cui gli utentiaccedono secondo specifici diritti. Inoltre sono necessarie delle tecniche che consentano dievitare che l’attività dei vari utenti generi conflitti per l’uso contemporaneo degli stessi dati.

1.2 DataBase Management System (DBMS)

I DBMS sono strumenti software che gestiscono in maniera efficace ed efficiente le informazionicontenute in un database.Prima dello sviluppo dei DBMS l’approccio che veniva applicato al problema dell’archiviazioneprevedeva l’uso diretto delle strutture del file system (vedi fig. 1.1).

Appl. 2

Appl. 3

Fig. 1.1 Approccio file system

Appl. 1



Nella soluzione file system, le applicazioni accedono direttamente agli archivi, quindi ognuna deveconoscere la struttura interna degli archivi e le relazioni tra i dati e deve evitare la duplicazionedegli stessi. Inoltre la non volatilità dei dati e la gestione degli accessi contemporanei di piùapplicazioni agli archivi viene relegata a strati software non specializzati per tali compiti, quali ilsistema operativo.

La caratteristica saliente che differenzia un sistema per la gestione di database (DB) è la presenza diun componente specializzato a tale ruolo (vedi fig. 1.2).

La figura 1.2 mostra come le applicazioni rivolgono al DBMS le proprie richieste di accesso allabase di dati, il quale gestisce i dati svincolando le applicazioni da tale onere. Quindi il DBMS è unmodulo, specializzato nella gestione del DB; a cui tutte le applicazioni si rivolgono per accedere aidati. Si ottiene così un triplice scopo: da una parte le funzionalità di gestione del database sonoraggruppate in un unico insieme, dall’altra le applicazioni risultano alleggerite e quindi più velocida realizzare e, soprattutto, nessuna potrà effettuare operazioni scorrette sul database.

1.3 Caratteristiche di un DBMS

Le proprietà fondamentali di un DBMS sono:

• Capacità di gestire dati non volatili;• Capacità di accedere in modo efficiente a grandi quantità di dati.

Sono richieste, inoltre, le seguenti caratteristiche:

• Mantenimento di un modello dati, o astrazione matematica tramite la quale l’utente puòosservare i dati;

• Mantenimento di linguaggi di alto livello che permettono all’utente di definire la struttura deidati, accedere ad essi ed elaborarli;

• Gestione delle transazioni, cioè capacità di fornire un accesso corretto e concorrente al DB daparte di molti utenti contemporaneamente;

• Accesso controllato, cioè capacità di limitare l’accesso ai dati agli utenti non autorizzati e dicontrollare la validità dei dati;

• Capacità di recupero, cioè la possibilità di ripristino a seguito di guasti del sistema senzaperdere dati.

Appl. 1

Appl. 2

Fig. 1.2 Approccio DBMS

DB

D

B

M

SAppl. 3



1.3.1 Dati non volatiliUn DBMS deve trattare dati non volatili, nello specifico deve trattare un database che contiene idati che si vogliono gestire e le informazioni che servono per gestirli. Ovviamente i dati per esserenon volatili devono essere memorizzati su memorie di massa.

1.3.2 Accesso efficiente a grandi quantità di datiUn DBMS deve permettere, a differenza di un file system, di accedere in maniera rapida a porzioniarbitrarie di dati contenuti nel DB. Questa capacità diventa necessaria soprattutto quando la moledei dati è molto grande, mentre per quantità piccole di solito bastano anche tecniche di accessosemplice, come quella della scansione lineare.

1.3.3 Modello datiOgni DBMS fornisce almeno un modello astratto di dati, che consente all’utente di considerare leinformazioni non come sequenza di bit, ma in termini a lui più comprensibili. Per operare sulleinformazioni contenute in un database è possibile, quindi, ignorare i dettagli della struttura fisica delDB e considerare i dati in termini di ciò che rappresentano nel mondo reale o, comunque, inrelazione al livello di astrazione del modello dei dati del database.

1.3.4 Linguaggi ad alto livelloUn DBMS supporta tradizionalmente tre tipi di linguaggi, distinti in base alle funzioni eseguite suidati. Tale distinzione è dovuta alla separazione delle funzioni dichiarative da quelle di elaborazionee di controllo, a differenza di quanto avviene in un comune linguaggio di programmazione.Il motivo è che, mentre in un normale programma i dati esistono solo mentre esso è in esecuzione,in un DB i dati sono permanenti e possono essere dichiarati una volta per tutte.Per la definizione dello schema logico del database viene usato il DDL (Data Definition Language).Esso non è un linguaggio procedurale, piuttosto è una notazione per definire le informazioni e lerelazioni intercorrenti fra esse, secondo un particolare modello dati.Per le operazione di interrogazione ed aggiornamento dei dati quali inserimento, modifica,cancellazione, e così via, viene usato il DML (Data Manipulation Language). Esso può esseredisponibile come linguaggio a se stante o come un insieme di istruzioni richiamabili da unlinguaggio di programmazione che svolge il ruolo di linguaggio host.Per le operazioni di controllo dei dati, la gestione degli utenti, l’assegnazione dei diritti di accesso,l’ottimizzazione del funzionamento del DBMS viene usato il DCL (Data Control Language).Solitamente il DML è utilizzato dai programmatori che realizzano i programmi applicativi destinatiagli utenti finali, mentre il DCL e il DDL sono usati dal DBA (Data Base Administrator), la personao il gruppo di persone che partecipa alla progettazione e al mantenimento del database.Un’altra figura che partecipa alla progettazione del DB è il DA (Data Administrator), figura di piùalto livello rispetto al DBA, che si occupa dei dati come patrimonio del sistema informativoaziendale, indipendentemente dalla loro localizzazione all’interno di un DB.

1.3.5 Gestione delle transazioniUn’altra caratteristica importante di un DBMS è la sua capacità di gestire simultaneamente grandiquantità di transazioni, cioè di procedure operanti sul DB. Alcuni DB sono così grandi che possonoessere utili solo se su di essi operano simultaneamente diverse applicazioni. I sistemi usati dallebanche, a cui accedono quasi istantaneamente centinaia o migliaia di macchine per interrogazioni ealmeno altrettanti impiegati delle filiali, costituiscono un tipico esempio di questi DB. A volte dueaccessi non interferiscono tra loro; ad esempio il saldo di un conto bancario può essere letto nellostesso tempo, senza problemi di inconsistenza, da qualunque numero di transazioni. Altre volte,come nel caso di un prelievo che avviene contemporaneamente ad un versamento, il risultato di duetransazioni simultanee e senza coordinazione può essere imprevedibile.



Quindi, le transazioni che modificano un campo, devono bloccare altre transazioni che cercano dileggere o scrivere lo stesso campo nel medesimo istante. Perciò un DBMS deve fornire controlli diconcorrenza per evitare che più di una transazione acceda allo stesso dato in modo non coordinato.

1.3.6 Accesso controllatoLe funzionalità di un DBMS di gestione degli utenti consente all’amministratore del sistema didefinire dei vincoli di accesso ai dati, ovvero di stabilire per ciascun utente i diritti di accesso(lettura, modifica e così via) alle singole unità di informazione del database.Inoltre un DBMS fornisce spesso una funzione di view (vista) che consente di creare oggetti astrattia partire da oggetti reali permettendo visione logiche diverse dello stesso insieme di dati; ciòcomporta la possibilità di rendere disponibile a determinate categorie di utenza l’intero database, adaltri solo una parte.

1.3.7 Capacità di recuperoUn DBMS, oltre a trattare dati non volatili, deve implementare delle tecniche che permettano ilripristino dei dati persi o danneggiati a seguito di un malfunzionamento di una qualsiasicomponente del sistema.La maggior parte dei DBMS esistenti gestisce un file detto log delle transazioni nel quale si tienetraccia di tutti i cambiamenti che avvengono nel database. Ogni volta che un utente avvia unatransazione che modifica il DB, il DBMS registra la modifica nel log delle transazioni. Quando latransazione è conclusa nel log viene segnalato che le modifiche della transazione sono definitive.Se, ad esempio, si verifica un crash del sistema dovuto ad una caduta di tensione, ci saranno dei datimodificati che non sono stati ancora scritti nel database, ma grazie al log delle transazioni, si potràricostruire la transazione persa.Per il recovery di problemi più seri come il crash del disco rigido non sono più sufficienti i log delletransazioni ma è necessario avere un backup (copia su dispositivi di memorizzazione esterni) delDB o di una parte di esso. Il DBMS deve fornire gli strumenti adatti ad assolvere a questo compito.

1.3.8 Aspetti negativi

I DBMS hanno anche degli aspetti negativi:

• I DBMS sono prodotti costosi, complessi e abbastanza diversi da molti altri strumentiinformatici. La loro introduzione comporta quindi notevoli investimenti, diretti (acquisto delprodotto) e indiretti (acquisizione delle risorse hardware e software necessarie, conversionedelle applicazioni, formazione del personale).

• I DBMS forniscono, in forma integrata, una serie di servizi, che sono necessariamente associatiad un costo. Nei casi in cui questi servizi non sono tutti necessari, è difficile scorporare i servizieffettivamente richiesti dagli altri, e ciò può comportare una riduzione di prestazioni.



2 Progettazione concettuale

La progettazione concettuale è la prima fase che viene eseguita nella costruzione di una base di dati,e in essa si produce, uno schema concettuale che rappresenta la realtà di interesse.Nel seguente capitolo illustreremo questo processo e i modelli dati che permettono di realizzare loschema concettuale suddetto, in particolare, il modello entità-relazione che è al momento il piùdiffuso. Prima di ciò, però, vediamo la metodologia di progettazione.

2.1 Ciclo di vita dei sistemi informativi

La progettazione di una base dati costituisce solo una componente del processo di sviluppo,all’interno di una organizzazione, di un sistema informativo complesso e va quindi inquadrata in uncontesto più ampio, quello del ciclo di vita dei sistemi informativi.Come illustrato in figura 2.1, il ciclo di vita di un sistema informativo comprende, generalmente, leseguenti attività.

• Studio di fattibilità. Serve a definire, in maniera per quanto possibile precisa, i costi delle variealternative possibili e a stabilire le priorità di realizzazione delle varie componenti del sistema.

• Raccolta e analisi dei requisiti. Consiste nella individuazione e nello studio delle proprietà edelle funzionalità che il sistema informativo dovrà avere. Questa fase richiede una interazionecon gli utenti del sistema e produce una descrizione completa, ma generalmente informale, dei

Studio difattibilità

Raccolta e analisidei requisiti

Progettazione

Implementazione

Validazione ecollaudo

Funzionamento

Fig. 2.1 Ciclo di vita di un sistema informativo



dati coinvolti (anche in termini di previsione sulla loro frequenza). Vengono inoltre stabiliti irequisiti software e hardware del sistema informativo.

• Progettazione. Si divide generalmente in progettazione dei dati e progettazione delleapplicazioni. Nella prima si individua la struttura e l’organizzazione che i dati dovranno avere,nell’altra si definiscono le caratteristiche dei programmi applicativi. Le due attività sonocomplementari e possono procedere in parallelo o in cascata. Le descrizioni dei dati e deiprogrammi prodotte in questa fase sono formali e fanno riferimento a specifici modelli.

• Implementazione. Consiste nella realizzazione del sistema informativo secondo la struttura e lecaratteristiche definite nella fase di progettazione. Viene costruita e popolata la base di dati eviene sviluppato il codice dei programmi.

• Validazione e collaudo. Serve a verificare il corretto funzionamento e la qualità del sistemainformativo. La sperimentazione deve prevedere, per quanto possibile, tutte le condizionioperative.

• Funzionamento. In questa fase il sistema informativo diventa operativo e richiede, a meno dimalfunzionamenti o revisioni delle funzionalità del sistema, solo operazioni di gestione emanutenzione.

Va detto che accanto alle attività citate, viene oggi spesso effettuata anche una attività detta diprototipizzazione, che consiste nell’uso di specifici strumenti software per la realizzazione rapida diuna versione semplificata del sistema informativo, con la quale sperimentare le sue funzionalità. Laverifica del prototipo può portare a una modifica dei requisiti e una eventuale revisione del progetto.Poiché i dati hanno un ruolo centrale nei sistemi informativi si giustifica uno studio autonomorelativo alla progettazione delle basi di dati che si individua nella terza fase del ciclo di vitariportato in figura 2.1.

2.2 Modello dei dati e fasi di progettazione

Nel corso degli anni, nell’ambito delle basi di dati, si è consolidata una metodologia di progettoarticolate in tre fasi principali da effettuare in cascata. Essa si fonda su un principio molto semplicema efficace: quello di separare in maniera netta le decisioni relative a “cosa” rappresentare in unabase dati (prima fase), da quelle relative a “come” farlo (fasi successive).Ogni fase si riferisce a un livello di astrazione nella rappresentazione dei dati e delle relazioni traessi, e ha lo scopo di separare le attività di risoluzione dei problemi e di garantire la possibilità dimodificare delle soluzioni adottate ai livelli inferiori senza dover riprogettare quanto definito neilivelli superiori.A ciascuna fase di progettazione corrispondono diversi modelli per la rappresentazione dei dati,ovvero tecniche per la rappresentazione degli aspetti rilevanti della realtà da modellare, definite dastrumenti e vincoli specifici. La rappresentazione generata seguendo le regole del modello vienedefinita schema (vedi fig. 2.2).

realtà di interesse

schema

modello (regole di rappresentazione)

Fig. 2.2 Realtà/modello/schema



Le fasi riconosciute fondamentali nella progettazione di un database sono le seguenti: progettoconcettuale, progetto logico e progetto fisico (vedi figura 2.3).

2.2.1 Progetto concettuale del database

Obiettivo della fase di progettazione concettuale è la rappresentazione completa (formale) dellarealtà di interesse (informale) ai fini informativi, in maniera indipendente da qualsiasi specificoDBMS e quindi senza tenere conto degli aspetti implementativi. Tale rappresentazione, dettaschema concettuale (che fa riferimento a un modello concettuale dei dati), è la rappresentazione piùastratta, ovvero più vicina alla logica umana, nella definizione di dati e relazioni.I modelli dei dati usati nella progettazione concettuale vengono definiti modelli semantici. Nelcorso degli anni sono stati definiti diversi modelli dei dati ad iniziare da quelli reticolari egerarchici seguiti da quello entità-relazione e infine quelli orientati agli oggetti e alla logica.

Fig. 2.3 Fasi della progettazione di una base di dati

Progetto fisico

Modello concettuale

Modello logico

Modello fisico

Progetto concettuale

Progetto logico

Schema concettuale

Schema logico

Schema fisico

Progettazione dibase di dati

Prodotti della progettazione

Requisitidella base di

dati



2.2.1.1 Livello vistaUna vista, sottoschema, o subschema, è una parte del database concettuale o un’astrazione di partedel database concettuale. In un certo senso, la costruzione delle viste è l’inverso del processo diintegrazione di un database: per ogni collezione dei dati che hanno contribuito alla costruzione deldatabase concettuale globale, possiamo costruire una vista che contenga proprio quei dati. Le vistesono importanti anche per far valere la sicurezza in un sistema di database, permettendo solo agliutenti che ne hanno l’autorizzazione di osservare i sottoinsiemi dei dati.Spesso una vista è proprio come un piccolo database concettuale ed ha lo stesso livello diastrazione. Però, in un certo senso, una vista può essere “più astratta” di un data base concettuale, inquanto i dati in essa coinvolti possono essere costruiti a partire dal database concettuale, senza peròessere effettivamente presenti in quel database.

2.2.1.2 Schemi ed IstanzeQuando si progetta un database si è interessati al suo schema, quando invece si usa si è interessati aidati effettivamente presenti in esso. Si noti che i dati nel database cambiano frequentemente, mentregli schemi rimangono gli stessi per lungo tempo.Il contenuto corrente del database si chiama istanza del database (o estensione del database o statodel database).Come visto, il termine schema è usato nelle varie fasi della progettazione di un database, cosìavremo schema concettuale per riferirsi al livello di progettazione concettuale del database, schemalogico per il progetto logico, schema fisico per il progetto fisico e semplicemente sottoschema per illivello delle viste.

2.2.2 Progetto logico del database

La fase di progettazione logica del database ha lo scopo di tradurre lo schema concettuale espressomediante un modello semantico in una rappresentazione mediate un modello logico dei dati. Larappresentazione che si ottiene viene definita schema logico del database.A differenza dello schema concettuale, lo schema logico dipende strettamente dal tipo di DBMSutilizzato e in particolare del suo modello logico dei dati. Un modello logico dei dati è quindi latecnica di organizzazione e di accesso ai dati utilizzata da specifiche categorie di DBMS. Inparticolare, in riferimento al modello logico dei dati su cui si basano, vengono distinti DBMSgerarchici, reticolari, relazionali, ad oggetti e basati sulla logica.

Un ulteriore compito della progettazione logica è quello di dichiarare le viste, tramite il DDL o glispecifici linguaggi di definizione dei dati del sottoschema. Successivamente per presentareinterrogazioni ed operazioni su tali viste, può essere previsto un linguaggio di manipolazione delsottoschema altrimenti viene usato il DML generico.

2.2.3 Progetto fisico del database

Nel progetto fisico viene stabilito come le strutture a livello logico debbano essere organizzate negliarchivi e nelle strutture del file system: esso dipende quindi non solo dal tipo di DBMS utilizzato,ma anche dal sistema operativo e in ultima istanza dalla piattaforma hardware del sistema che ospitail DBMS.E’ pertanto il livello di progettazione in cui si può far uso del minor livello di astrazione, dovendorispettare i vincoli tecnici imposti dal sistema ospite.



2.2.4 Indipendenza dei dati

La catena di astrazione della figura 2.3, dal database concettuale, a quello logico e a quello fisico,fornisce due livelli di “indipendenza dei dati”. E’ ovvio che in un database ben progettato, loschema fisico possa essere modificato senza alterare quello logico e senza richiedere unaridefinizione dei sottoschemi. Questa indipendenza è nota come indipendenza fisica dei dati. Ciòimplica che le modifiche all’organizzazione del database fisico possono alterare l’efficienza deiprogrammi applicativi, ma non sarà mai chiesto di riscrivere tali programmi solo perché lo schemafisico ha modificato l’implementazione dello schema logico.Anche la relazione tra vista e il database concettuale, fornisce un tipo di indipendenza chiamataindipendenza logica dei dati. L’uso del database può rendere necessario modificare lo schemaconcettuale, per esempio aggiungendo informazioni su diversi tipi di entità o altre informazioni suentità già esistenti. Lo schema concettuale può subire molte modifiche, senza coinvolgere isottoschemi esistenti, mentre altri tipi di variazione allo schema concettuale possono essere fattesolo ridefinendo la corrispondenza tra sottoschema e schema concettuale. Ancora una volta nonsono necessari variazioni ai programmi applicativi. L’unico tipo di variazione dello schemaconcettuale che non si riflette in una semplice ridefinizione della corrispondenza col sottoschema, siverifica quando vengono cancellate alcune informazioni del sottoschema. Naturalmente talivariazioni richiederanno la riscrittura o l’eliminazione di alcuni programmi applicativi.

2.3 Modello Entità-Relazione

Lo scopo del modello Entity-Relationship (Entità-Relazione E-R) è quello di permettere ladescrizione dello schema concettuale di una situazione reale senza preoccuparsi dell’efficienza odella progettazione del database fisico, che ci si aspetta invece nella maggior parte dei modellifisici. Di solito si pensa che lo schema entità-relazione così costruito sia poi tradotto in uno schemalogico di un modello logico dei dati, ad esempio quello relazionale, che al momento è il più diffuso.

2.3.1 EntitàIl modello entità-relazione, prevede come prima attività della progettazione concettuale, laindividuazione delle entità.Una entità è qualcosa che esiste ed è distinguibile: possiamo cioè riconoscere un’entità tra le altre.Ad esempio ogni persona è un’entità, così come ogni automobile.

2.3.2 Set di entitàUn gruppo composto da entità tutte “simili” forma un set di entità. Esempi di set di possono essere:

1) tutte le persone2) tutte le persone coi capelli rossi3) tutte le automobili

Negli esempi 1) e 2), osserviamo persone e persone coi capelli rossi: il termine “entità simili” non èdefinito in modo preciso e si possono stabilire infinite proprietà diverse con cui definire set dientità.Nella progettazione del modello concettuale di un database, la scelta dei set di entità, è unaoperazione fondamentale così come è importante individuare tutte le proprietà caratteristiche di unset di entità che vengono descritte mediante gli attributi. Dalla “somiglianza”, quindi, nasce lanecessità dell’individuazione di un insieme di caratteristiche comuni a tutti gli elementi del set dientità.Il set di entità è un concetto a livello di schema, mentre il corrispondente concetto a livello diistanza è il relativo sottoinsieme corrente di tutti gli elementi del dato set di entità nel database.



Ad esempio il Pubblico Registro Automobilistico può progettare il suo schema di database avente ilset di entità Automobili. L’istanza corrente di questo set di entità riguarderà tutte le automobiliimmatricolate sino ad ora in Italia, ma non tutte le automobili del mondo o tutte le automobili maiesistite.

Lo schema entità-relazione ha una rappresentazione grafica che permette di avere immediatamentela visione globale dello schema concettuale del database. La rappresentazione grafica che si ottiene,a volte, invece di schema, viene chiamata diagramma entità-relazione (Entity-RelationshipDiagram – ERD). In questa rappresentazione grafica si usa una convenzione per rappresentare i varioggetti. I set di entità vengono rappresentate con dei rettangoli con il nome del set di entitàall’interno.

2.3.3 Attributi e chiaviCome già detto, i set di entità possiedono delle proprietà, chiamate attributi, le quali associano adogni entità del set un valore appartenente al dominio dei possibili valori per quell’attributo. Di solitoil dominio sarà un insieme di interi, numeri reali, stringhe di caratteri, valori booleani ma ancheimmagini, audio e video come nei più recenti database multimediali.La scelta degli attributi caratteristici per i set di entità è un punto abbastanza critico nell’ideare loschema concettuale di un database. Tra tutti gli attributi di un particolare set di entità ne va sceltouno o un insieme, i cui valori identificano in modo univoco ogni entità del set. Questo attributo oinsieme di attributi è chiamato chiave per quel dato set. In linea di principio ogni set di entitàpossiede una chiave soddisfacendo la richiesta che ogni entità sia distinguibile da ogni altra. Ma seper un set di entità scegliamo un insieme di attributi tra i quali non si possa individuare una chiave,non saremo in grado di distinguere una entità dall’altra. Però è possibile fornire un codiceidentificativo arbitrario da usare come chiave.

La rappresentazione grafica degli attributi è un’ellisse con il nome dell’attributo scritto all’interno esi collega con il rispettivo set di entità con dei segmenti (non orientati). Agli attributi che fannoparte della chiave per il rispettivo set, viene aggiunta una sottolineatura al nome. Nel caso specialedi set di entità con un singolo attributo, a volte si identifica il set con l’attributo stesso, chiamando ilset col il nome dell’attributo. In tal caso, invece che con un rettangolo, il set di entità èrappresentato con un’ellisse collegata a qualunque relazione con cui sia coinvolto il set di entità.

2.3.4 RelazioniLe dipendenze o associazioni di interesse informativo tra i dati da rappresentare vengono espressenel modello entity-relationship mediante relazioni tra le corrispondenti entità. Le relazioni dellostesso tipo compongono l’insieme di relazioni (relation set) tra i due insiemi di entità.Per ottenere un modello adeguato del mondo reale, spesso è necessario classificare le relazioni aseconda del numero di entità associabili tra un set di entità e l’altro.

2.3.5 Relazioni uno-a-unoLa relazione più semplice, e più rara, fra le relazioni che collegano due set è quella uno-a-uno, cioèche ogni entità di un set è legata con al più un elemento dell’altro set.Le relazioni vengono rappresentate graficamente con dei rombi e vengono collegati ai propri set dientità con dei segmenti orientati o non a seconda del tipo di relazione. Nel caso di relazione uno-a-uno il segmento è orientato in entrambi i versi. Un’alternativa all’utilizzo dei segmenti orientati èquella di mettere sui segmenti che collegano la relazione ai set dei numeri che indicano lacardinalità della relazione.Un esempio di relazione 1:1 è la relazione tra nazioni e capitali. Ogni nazione ha un’unica capitale,ad una capitale corrisponde un’unica nazione (fig. 2.4).



2.3.6 Relazione uno-a-moltiDue set E1 ed E2 sono in relazione uno-a-molti da E1 ad E2 se una entità nel set E1 è associata conzero o più entità nel set E2, ma ogni entità in E2 è associata con al più una entità in E1.Un esempio di relazione 1:N è la relazione tra madri e figli. Una madre può avere più figli, mentread un figlio corrisponde un’unica madre (fig. 2.5).La rappresentazione grafica della relazione 1:N è un rombo con segmenti che uniscono i set dientità coinvolti e orientati soltanto nella direzione del set di entità con cardinalità uno.

2.3.7 Relazione molti-a-moltiDue set E1 ed E2 sono in relazione molti-a-molti se ad ogni elemento di E1 possono corrisponderepiù elementi di E2 e viceversa.Sulle relazioni molti-a-molti è da notare il fatto che non esistono efficienti strutture dati per la loroimplementazione, spesso è richiesto di scomporre tali relazioni con varie relazioni molti-a-uno.Un esempio di relazione N:M è la relazione tra corsi e studenti. Un corso è seguito da più studenti, elo stesso studente segue più corsi.Un altro esempio di relazione N:M è quella tra libri e autori. Un libro può essere scritto da piùautori, un autore può aver scritto più libri (fig. 2.6).La rappresentazione grafica della relazione N:M è un rombo con segmenti non orientati cheuniscono i set di entità coinvolti.

Nazioni CapitaliCapitale

Fig. 2.4 Diagramma E-R della relazione1:1 tra nazioni e capitali. Nazioni ha tre attributi: Nome Naz.(chiave), Estensione e Popolazione. Capitali ha due attributi: Nome Cap. (chiave), Abitanti.

Nome Naz. Nome Cap.

Estensione

Popolazione

Abitanti

Madri FigliFiglio

Fig. 2.5 Relazione 1:N tra il set Madri e il set Figli. Da notare il verso della freccia(nella figura non sono stati indicati gli attributi dei set di entità)



2.3.8 Gerarchia ISAUn tipo particolare di relazione è quella chiamata ISA o sottotipo/supertipo. Diciamo che A isa B,cioè “A è un B” (A è il sottotipo e B è il supertipo), se il set di entità B è una generalizzazione dientità del set A, o in modo equivalente se A è un tipo particolare di B. Lo scopo principale perdichiarare le relazioni isa tra i set di entità A e B è che in tal modo A eredita gli attributi di B, maavrà anche attributi che non avrebbero necessariamente significato per gli elementi di B che nonsiano anche elementi di A.La rappresentazione grafica della gerarchia isa è un rombo con etichetta isa con segmenti orientatinella direzione del set supertipo.

Un esempio di relazione isa è quello di una società che può avere un set di entità Dipendenti conattributi Matricola, Nome e Stipendio. Se la società fosse una squadra di calcio, alcuni deidipendenti, i Giocatori, avrebbero altri importanti attributi come Ruolo (portiere, difensore,attaccante), che non riguarderebbero gli altri dipendenti. Il modo migliore per progettare questoschema, è quello di avere un altro set di entità, Giocatori, legato con la relazione isa al setDipendenti. Gli attributi (anche le chiavi) che appartengono a Dipendenti (Matricola, Nome,Stipendio), verrebbero ereditati da Giocatori, ma solo Giocatori avrebbe un attributo come Ruolo(fig. 2.7).

2.3.9 Attributi delle relazioniIl modello entità-relazione prevede che anche gli insiemi delle relazioni abbiano degli attributi chene specificano le caratteristiche. Tali attributi vengono rappresentati graficamente con una ellisse,cioè come per gli attributi di un set di entità, con un segmento orientato nel verso che va dal romboall’ellisse (fig. 2.8).

Autori LibriScritto

Fig. 2.6 Relazione N:M tra il set Autori e il set Libri

Dipendenti Giocatori

Fig. 2.7 Gerarchia Giocatori isa Dipendenti. Giocatori e’ il sottotipo (A delladefinizione) e Dipendenti è il supertipo (B della definizione).

Matricola

Nome

Stipendio

Ruolo Isa

NomeAttributoRelazione

E1 E2R1

Fig. 2.8 Rappresentazione attributi relazione



2.4 Esempio di schema concettuale

Adesso viene proposto un esempio di schema concettuale che sarà usato anche nel successivocapitolo per vedere come uno schema concettuale si traduce in uno schema logico.L’esempio che si introduce è quello del database Mobili Componibili, che fa parte del sistemainformativo di un mobilificio e che rappresenta la seguente situazione:• gli articoli, di cui interessa archiviare la descrizione, il prezzo, l’aliquota IVA e le spese di

trasporto, sono suddivisi in categorie:• ciascun articolo è costituito da una serie di componenti, di cui vengono archiviati la descrizione

e il costo;• i componenti vengono prodotti da singoli laboratori; di ogni laboratorio viene memorizzato

l’indirizzo, la città e il telefono;• gli articoli possono comparire negli ordini; di ogni ordine viene archiviata la data;• infine gli ordini sono effettuati dai negozi di cui viene archiviato il nome, l’indirizzo, la città, e il

telefono.

Nel progetto concettuale vengono individuate i seguenti set di entità con rispettivi attributi e chiavi.

Set di Entità Attributi Chiave

Categoria Cat_Cod XCat_Descrizione

Articolo Art_Cod XArt_DescrizioneArt_PrezzoArt_IVAArt_Spese_Trasporto

Componente Com_Cod XCom_DescrizioneCom_Costo

Laboratorio Lab_Cod XLab_IndirizzoLab_CittàLab_Telefono

Negozio Neg_Cod XNeg_NomeNeg_IndirizzoNeg_CittàNeg_Telefono

Ordine Ord_Cod XOrd_Data

Fig. 2.9 Set di entità, attributi e chiavi delloschema concettuale di esempio



Tra tali set di entità sussistono le seguenti relazioni:

• Categoria e Articolo hanno una relazione di tipo 1:N, in quanto ciascuna categoria puòcontenere più articoli, mentre un articolo può appartenere ad una solo categoria. Chiamiamoquesta relazione Appartiene;

• Articolo e Componente sono in relazione N:M, in quanto ciascun articolo è composto da piùcomponenti e ciascun tipo di componente può entrare nella composizione di pù articoli; può poiessere necessario utilizzare più pezzi di un certo componente per comporre un determinatoarticolo, per cui un attributo della relazione è la quantità. Chiamiamo questa relazioneComposto;

• Laboratorio e Componente sono in relazione 1:N in quanto un laboratorio può costruire piùcomponenti, mentre un determinato componente viene prodotto da un solo laboratorio.Chiamiamo questa relazione Prodotta;

• Negozio e Ordine sono in relazione 1:N, in quanto un negozio può effettuare più ordini, mentreciascun ordine è relativo a un unico negozio. Chiamiamo questa relazione Effettuato;

• Ordine e Articolo sono in relazione N:M, in quanto in un ordine possono essere richiesti piùarticoli e un articolo può comparire in più ordini; la relazione ha come attributo la quantità nellaquale un certo articolo viene richiesto nell’ordine. Chiamiamo questa relazione Richiesto.

La figura 2.10 mostra la rappresentazione dello schema concettuale del database MobiliComponibili mediante il modello entità-relazione.



Negozio Ordine

Fig. 2.10 Schema Concettuale del DB Mobili Componibili secondo il modello entità-relazione.(Schema o Diagramma Entità-Relazione ERD)

Neg_CodNeg_Nome

Neg_Indirizzo

Ord_Cod

Effettuato

Neg_CittàOrd_Data

Neg_Telefono

Art_Cod

Art_Descriz.

Art_IVA

Art_Prezzo

Richiesto

Art_Spese_Trasp

Com_Desciz.

Com_Cod

Com_Costo

Composto

Articolo

Componente

Cat_Cod

Cat_Descriz.

AppartieneCategoria

Lab_Cod

Lab_Città

Prodotta

Lab_Telefono

Laboratorio

Lab_Indiriz.

OrdArt_Qta

ComArt_Qta



2.5 Linee guida per tracciare uno schema entità-relazione

1) Perfetta comprensione della realtà che si vuole rappresentare.

2) Individuazione dei set di entità.• Studiare la descrizione del Contesto a cui ci si riferisce e la definizione degli Obiettivi del

Progetto.• Individuare i Nomi degli Obiettivi/Concetti che è indispensabile citare per descrivere

Contesto e Obiettivi.• Valutare se si tratta di Nomi di Entità che dovranno essere gestite (o referenziate) dal

sistema in esame.

3) Individuazione degli attributi che caratterizzano i set di entità trovati al passo precedente, e scelta(o definizione) della chiave per ogni set di entità.

4) Individuazione delle relazioni tra i vari set di entità e definizione della loro cardinalità.• Studiare la descrizione del Contesto a cui ci si riferisce e la definizione degli Obiettivi del

Progetto.• Individuare le frasi che legano fra loro due set di entità con un verbo (Entità soggetto +

verbo + Entità oggetto).• Valutare se il verbo rappresenta un fatto che fa nascere una relazione fra due set di entità.• Verificare che non esistano relazioni duplicate o ingannevoli.• Definire la cardinalità delle relazioni.• Individuare eventuali attributi delle relazioni.

5) Disegno del diagramma entità-relazione.

Ai set di entità, agli attributi e alle relazioni devono essere assegnati dei nomi rappresentativi dellarealtà che esprimono e non devono essere ambigui.

2.6 Utilità del diagramma Entità-Relazione

Perché dovremmo essere interessati al modello dati di un sistema? In primo luogo perché lestrutture di dati e le relazioni possono essere così complesse che vogliamo evidenziarle edesaminarle indipendentemente dall’elaborazione che avrà luogo. In effetti, ciò è particolarmentevero quando il modello del sistema viene mostrato agli utenti esecutivi di livello superiore inun’organizzazione (ad esempio, i vicepresidenti o direttori di reparto). Tali utenti sono spessointeressati ai dati: quali dati servono per condurre gli affari? In che modo i dati sono correlati adaltri dati? Chi possiede i dati? A chi è consentito l’accesso ai dati?La risposta ad alcune di queste domande – ad esempio, l’accesso ai dati e l’identificazione deiproprietari – è fornita dai DA. Ogni volta che si inizia a costruire un nuovo sistema informativo, siha bisogno di parlare con queste persone in modo da poter coordinare le proprie informazioni sulsistema col loro modello di informazioni globale a livello aziendale.Il diagramma entità-relazione è un utile strumento per svolgere tale conversazione.Si dovrà altresì conversare con il gruppo dei DBA, situato solitamente nel reparto di elaborazionedati (mentre i DA non vi appartengono necessariamente), il cui compito è quello di garantire che idatabase computerizzati siano organizzati, gestiti e controllati efficacemente. Quindi essicostituiscono spesso la squadra di implementazione che ha la responsabilità di prendere un modello



essenziale (cioè, un modello indipendente dalla tecnologia specifica) e convertirlo in un progetto didatabase fisico efficace ed efficiente per Oracle, Informix, DB2 o qualche altro sistema di gestionedi database.Il diagramma di entità-relazione è un efficace strumento di modellamento per comunicare colgruppo di DBA.In base alle informazioni presentate dal diagramma E-R, il gruppo di amministrazione del databasepuò iniziare a determinare i tipi di chiave o di indici o di puntatori che servono per accedereefficientemente ai record del database.Quindi il modello dei dati fornisce, oltre alla rappresentazione dei dati del sistema che si vuolegestire, un utile strumento di conversazione con gli altri gruppi di lavoro che interagiscono in unprogetto. Ma esso riguarda esclusivamente dati e relazioni tra i dati, senza fornire alcunainformazione sulle funzioni che creano e utilizzano i dati. Queste informazioni sono fornite da unaltro tipo di diagramma, chiamati Data Flow Diagram (DFD), che modellano le funzioni svolte daun sistema (vedi appendice A).

2.7 Altri modelli dati

Prima dell’arrivo dei sistemi relazionali i DBMS si basavano su modelli reticolari o gerarchici chenon sono altro che dei casi particolari del modello relazionale.Successivamente al modello relazionale sono arrivati i sistemi orientati agli oggetti e alla logicache costituiscono l’ultima tendenza nell’ambito dei modelli dati e ancora oggi non è disponibile unostandard che ne regoli la definizione.Anche se il modello entità-relazione è attualmente il più diffuso, in alcuni contesti, si possonoadattare meglio i sistemi gerarchici e reticolari, però scegliere lo schema concettuale che offra lamigliore efficienza può essere piuttosto difficile e richiede una profonda comprensione del progettodel modello desiderato.E’ da tenere comunque presente che esistono degli algoritmi che permettono di passare da unoschema di database di un modello dati ad un altro in modo più o meno semplice.Vediamo adesso brevemente gli altri suddetti modelli dati.

2.7.1 Modello dati reticolare

A grandi linee il modello dati reticolare è un modello entità-relazione in cui le relazioni sonovincolate ad essere binarie e del tipo uno-a-molti. Tale vincolo consente di usare, per i dati, ilmodello di grafo orientato.Al posto di set di entità, il modello reticolare parla di tipo record logico. Un tipo record logico è ilnome di un insieme di record, chiamati record logici. I record logici sono composti da campi con iquali vengono rappresentati gli equivalenti degli “attributi” del modello entità-relazione.Le “relazioni binarie uno-a-molti”, vengono chiamati collegamenti o link.Per rappresentare i tipi record e i loro collegamenti si disegna un grafo orientato, chiamato rete, chein realtà è un diagramma semplificato entità-relazione. I nodi corrispondono ai tipi di record logici,e gli archi rappresentano i collegamenti. I nodi e gli archi sono battezzati rispettivamente coi nomidei loro tipo record logico e dei link. Gli archi sono orientati nella direzione uno-a-molti e sonopercorribili in entrambe le direzioni.Il record logico che si trova nella direzione “uno” della relazione uno-a-molti si chiama ownermentre l’altro si chiama member (vedi fig. 2.11).



L’esempio precedente è un caso molto semplice di rete, uno schema più generico è mostrato nellafigura 2.12.

2.7.2 Modello dati gerarchico

Nel modello dati gerarchico (sottoinsieme del modello reticolare) lo schema del database èvincolato ad essere costituito da una struttura ad albero (uno o più, foresta) nelle quali sonorappresentate bene le relazioni uno-a-molti ma non quelle molti-a-molti, quindi si adatta bene acerte realtà ma non a tutti i possibili contesti.Nel modello dati gerarchico vale ancora la terminologia del modello reticolare come ad esempio“tipo record logico” ma alcuni termini della teoria degli alberi si adattano meglio al caso, come adesempio, l’owner è chiamato più comunemente padre e il member figlio. La restrizionefondamentale rispetto alle reti è che un tipo di record può essere figlio solo su un collegamentomentre un tipo di record può essere padre su più collegamenti (gerarchia). La figura 2.13 mostra unesempio di struttura gerarchica.

LEGA CALCIO

SQUADRE

GIOCATORI

Squadre_calcio

Giocatori_squadra

LEGA CALCIO è owner del linkSquadre_calcio

SQUADRA è member del linkSquadre_calcio e contemporaneamenteowner del link Giocatori_squadra

GIOCATORI è member del linkGiocaori_squadra

Fig. 2.11 Esempio di schema reticolare

A

C

D E

B

Fig 2.12 Esempio di una struttura di rete



Al contrario del modello reticolare, nel modello gerarchico i collegamenti sono percorribili solo inun verso, da padre a figlio, ma questa limitazione può essere superata con delle tecniche particolariche portano all’introduzione di due nuovi oggetti “tipo record virtuali” e “tipo record combinati”.Essi, nel primo caso sono semplicemente dei puntatori, nel secondo, sono dei puntatori più dei dati,che permettono di arrivare direttamente al nodo di interesse senza passare dai nodi intermedi ecreare dei cammini arbitrari tra alberi differenti. Queste tecniche permettono anche di gestire lerelazioni molti-a-molti (fig. 2.14).

2.7.3 Modelli orientati agli oggetti

Nell’ambito dei DBMS successivi al modello relazionale un accenno particolare va fatto ai modelliobject oriented (OO-DBMS). Essi hanno la capacità di un DBMS e insieme alla combinazioneDML/Linguaggio host hanno le seguenti caratteristiche:

• Oggetti complessi: avere la capacità di definire tipi di dati con strutture nidificate,• Incapsulamento dell’informazione: cioè la capactà di definire procedure che si applicano solo a

oggetti di un determinato tipo e la possibilità di richiedere che tutti gli accessi a questi oggettiavvengano attraverso l’applicazione di una di queste procedure (viene occultata la strutturainterna degli oggetti),

A

C

D E

B

Fig 2.13 Esempio di struttura gerarchica

Studenti (Nome, Indirizzo) Corsi (Istituto, Numero)

Iscrizione (*Corso, Voto) *Studenti

Fig. 2.14 Relazione molti a molti con record combinati (* indica i record virtuali)



• Identità degli oggetti: capacità del sistema di distinguere due oggetti che sembrano gli stessi(componenti primitive uguali, ma indirizzo diverso),

• Gerarchia di tipi: permettere ai tipi di avere dei sottotipi con caratteristiche proprie.

Nella teoria dei sistemi object oriented un oggetto è un insieme di dati, più le procedure per operaresu questi dati. In termini rigorosamente informatici, un oggetto è un tipo di dato astratto (AbstractData Type – ADT) composto per l’appunto dai dati e dalle procedure per operare su di essi, e taleche l’unico accesso possibile avviene tramite queste procedure. Queste procedure vengono chiamatemetodi e vengono attivati dai messaggi che corrispondono a chiamate di funzioni dei linguaggi diprogrammazione tradizionali. L’insieme di tutti i metodi forniti per un oggetto è detta la suainterfaccia o il protocollo di accesso. Una classe invece è l’implementazione di un tipo di datoastratto basata sui concetti di ereditarietà, incapsulazione e polimorfismo. Per ereditarietà si intendeil meccanismo di derivazione delle caratteristiche tra le classi di oggetti. Mentre polimorfismo è lapossibilità di definire con lo stesso nome procedure su oggetti diversi e gestire quindi variabili nontipizzate.

Introduciamo adesso una notazione per definire la struttura degli oggetti, cioè il formato per i tipi.Notiamo prima di tutto che l’insieme di strutture ad oggetto definibili nel modello ad oggetti èmolto simile all’insieme dei possibili schemi per i database record del modello gerarchico, èpossibile definire il modo ricorsivo l’insieme dei tipi oggetti permessi.

• Un ente di tipo elementare, ad esempio un intero, un reale, o stringa di caratteri, è di tipooggetto. Un tale tipo corrisponde al tipo di dato per un “campo” nelle reti o nelle gerarchie.

• Se T è un tipo oggetto, allora SETOF(T) è un tipo oggetto.• Se T1, … , Tk sono tipi oggetto allora RECORDOF(T1, … , Tk) è un tipo oggetto.

Facciamo un esempio. Supponiamo per semplicità che i soli tipi elementari siano string e integer.Allora un tipo di un prodotto può essere rappresento dal record:

TipoProd = RECORDOF(nome:string, NumProd:integer)

dove i campi del record sono stati rappresentati dalla coppia (<nomecampo>:<tipo>).Se vogliamo gestire gli ordini, dobbiamo rappresentare le coppie prodotto/quantità, alloranecessitiamo creare il seguente tipo di oggetto:

PQTipo = RECORDOF(prodotto:TipoProd, quant:integer)

In questo caso il primo campo è un oggetto di tipo non elementare, e va pensato come un puntatorea un prodotto.Adesso possiamo definire il tipo di un ordine come:

TipoOrd = RECORDOF(NumOrd:integer, comprende:SETOF(PQTipo))

Da notare all’interno della definizione di TipoOrd vi è quella di un altro tipo di oggetto, comprende.SETOF(PQTipo) è equivalente alla due dichiarazioni:

SPTipo = SETOF(PQTipo)TipoOrd = RECORDOF(NumOrd:integer, comprende:SPQTipo)

Uno schema di database per un ipotetico DB per un negozio è rappresentato nella figura 2.15.



2.7.4 Modelli basati sulla logica

Alcuni sistemi chiamati Knowledge Base Management Systems (KBMS) si basano su regole logicheo conoscenza.Un sistema KBMS è il risultato dell’integrazione di un DBMS e della tecnologia dell’intelligenzaartificiale (AI). I modelli e la tecnologia dei DB attuali, in particolare quella relazionale, non sonoappropriate per questa integrazione.Si è quindi studiata una nuova tecnologia e nuovi modelli di cui necessita introdurre alcunedefinizioni.

Una base di conoscenza è un insieme strutturato di:

• Dati rappresentanti i fatti circa gli aspetti del dominio del discorso che si vuole modellare(alcune volte chiamato extensional database o fact base), e

• Conoscenza che rappresenta un alto livello di interpretazione e comprensione del dominio deldiscorso (alcune volte chiamato intensional database o rule base).

Un knowledge base management system è uno strumento il quale fornisce:

• Funzionalità per operare sia sull’intensional che sull’extensional database,• Un linguaggio che permetta di accedere alla base di conoscenza, e• Meccanismi per l’applicazione della conoscenza ai dati per ottenere risposte a delle richieste di

ragionamento circa i fatti.

Nei modelli dati basati sulla logica uno schema di database (o semplicemente schema) è definitocome la coppia (IDB, IC) dove IDB è l’intensional database e IC è un insieme finito di regolechiamate vincoli di integrità (o semplicemente integrità). I vincoli usualmente esprimonoinformazioni in forma negativa che restringono l’ammissibilità delle informazioni del database.Per uno schema (IDC, IC), uno stato del database e una tripla (IDB, IC, EDB) dove EDB èl’extensional database.

Vediamo adesso alcune necessarie definizioni sulle regole logiche.

TipoProd = RECORDOF(nome:string, NumProd:integer)

PQTipo = RECORDOF(prodotto:TipoProd, quant:integer)

TipoOrd = RECORDOF(NumOrd:integer, comprende:SETOF(PQTipo))

TipoCli RECORDOF(nome:string, indir:string, saldo:integer, ordini:SETOF(TipoOrd))

TipoRep = RECORDOF(nome:string, nemrep=integer, dipendenti:SETOF(TipoDip), capo:TipoDip, prodotti:SETOF(TipoProd))

TipoDip = RECORDOF(nome:string, stipendio:integer, reparto:TipoRep)

PrezzoProd = RECORDOF(prodotto:TipoProd, prezzo:integer)

TipoForn = RECORDOF(nome:string, indir:string, fornisce:SETOF(PrezzoProd))

Fig. 2.15 Esempio di schema di DB di un modello orientato agli oggetti



Un predicato è una funzione booleana (risultato vero o falso) costituito da un nome e da un insiemedi argomenti. Gli argomenti possono essere costituiti da costanti, variabili e simboli di funzioni. Lefunzioni forniscono come risultato valori del tipo da noi scelto.Le regole logiche sono delle istruzioni logiche del tipo: “se A1 e A2 e … An sono vere, allora B èvera” e si scrive:

B :- A1 & A2 & … & An.

il simbolo “:-“ si legge “se”.

Le regole logiche forniscono informazioni sui dati del database ed è utile notare l’analogia tranozione logica di predicato coi sui argomenti e il nome di relazione con i suoi attributi. Cioèpossiamo pensare che un predicato sia vero in corrispondenza dei suoi argomenti, se e solo se taliargomenti formano una tupla della relazione corrispondente.

Vista la brevità della trattazione invece di continuare con il formalismo introduciamo qualcheesempio.Supponiamo di avere uno schema di relazione Impiegati con attributi Nome, Ufficio, Stipendio eIndirizzo. Possiamo definire una vista pertutti attraverso la regola logica:

pertutti(N, U, I) :- impiegati(N, U, S, I).

La regola afferma che per tutti i nomi degli impiegati N, uffici U e indirizzo I, (N, U, I) è unaproprietà del predicato pertutti se esiste uno stipendio S tale che (N, U, S, I) sia un’istanza delpredicato impiegati. Notare che in generale una variabile come S, che compare alla destra delsimbolo” :-“, ma non alla sua sinistra, è trattata come esistenzialmente quantificata, quindi la regolasi legge “esiste qualche S”, dopo aver detto il “se” che corrisponde al simbolo “:-“.

Vediamo un altro esempio di come sia possibile esprimere in termini logici le informazioni sui dati:supponiamo di avere la relazione Impiegati con i soli attributi Nome e Uff. e la relazione Uffici congli attributi Uff. e Capo. Possiamo allora definire il predicato capo_di(I, C) col significato intuitivoche il capo C comanda l’impiegato I, espresso da:

capo_di(I, C) :- impiegati(I, U) & uffici(U, C). (2.1)

Cioè (I, C) è una istanza di capo_di tale per cui esiste un ufficio U tale che (I, U) sia un’istanza diimpiegati e (U, C) una di uffici. In sostanza abbiamo usato la precedente regola logica per creare lavista capo_di che è analoga a una relazione con gli attributi nome e capo.La ricercare del capo dell’impiegato Rossi Mario si esprimere in termini del predicato capo_disemplicemente come:

capo_di(‘Rossi Mario’, X) (2.2)

La ricerca dei valori di X che rendono vera la 2.2 si trovano con un algoritmo sostanzialmenteidentico a quello indicato in 2.3, ma la regola logica 2.1 ha un ruolo importante nel permettere alsistema di interpretare il significato dell’interrogazione. In senso generico possiamo dire che la 2.1rappresenta la “conoscenza” a proposito della relazione capo_di.

select capofrom impiegati, uffici (2.3)where impiegati.nome = ‘Rossi Mario’

and impiegati.uff = uffici.uff;



Un esempio di schema di database è:

Dove abbiamo un unico predicato, capo_di, ed una unica regola di integrità, icl. Essa afferma chetutti gli impiegati devono appartenere ad un ufficio esistente.

EDB

IDB

IC

impiegati(nome, uff)uffici(uff)capo(impieg, uff)

capo_di(I, C) :- impiegati (I, U) & capo(U, C)

icl :- impiegati(I, U) & NOT uffici(U)



3 Progettazione logica

Nel secondo capitolo abbiamo visto i vari modelli dati che rappresentano il progetto di un databasea livello concettuale. Per ogni modello a livello concettuale corrisponde un modello dati a livellologico della progettazione. In questo caso i modelli dati devono fornire oltre alla notazione perdescrivere i dati anche un insieme di operazioni per manipolare i dati stessi.In questo capitolo vedremo il modello dati relazionale, nel quale solitamente viene tradotto il“diagramma entità-relazione” progettato in precedenza, e l’algebra relazionale, un formalismo checi permette di accedere ai dati. Inoltre, illustreremo uno strumento di analisi della qualità di unprogetto, la teoria della normalizzazione.

3.1 Modello dati logico

Un modello dati a livello logico di progettazione è definito come un formalismo matematicocomposto da due parti:

• una notazione per descrivere i dati,• un insieme di operazioni per manipolare i dati.

Un modello matematico dei dati consente l’utilizzo di linguaggi e metodologie formali per l’accessoai dati. In particolare le due metodologie su cui si basano i linguaggi di accesso ai dati di undatabase relazionale sono l’algebra relazionale e il calcolo relazionale. In seguito verrà introdottala prima metodologia, in quanto costituisce la base del linguaggio SQL (Structured QueryLanguage), ormai affermato come standard nell’accesso ai database relazionali.

3.2 Modello dati relazionale

La rappresentazione dei dati nel modello logico relazionale è basata su un unico concettofondamentale, ovvero la relazione: questa va intesa in termini algebrici, e non va confusa con lerelazioni tra i dati del modello concettuale.Il concetto di relazione algebrica è quello secondo la teoria degli insiemi, cioè un sottoinsieme delprodotto cartesiano di una lista di domini.

Formalmente un dominio è semplicemente una lista di valori, non diverso da un tipo di dato.

Il prodotto cartesiano dei domini D1, D2, … , Dk che si scrive D1xD2x … xDk è l’insieme di tutte lek-tuple (v1, v2, … , vk) tali che v1 sia in D1, v2 in D2 e così via.Ad esempio se k=2, D1={0,1} e D2={a, b, c}, allora:

D1xD2={(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)}

Una relazione R è un qualunque sottoinsieme del prodotto cartesiano di uno o più domini.Ad esempio, considerando il prodotto cartesiano precedente, {(0, a), (0, c), (1, b)} è una relazionecosì come l’insieme vuoto.

Gli elementi di una relazione si chiamano tuple o record. Ogni relazione che sia un sottoinsieme diqualche prodotto D1xD2x … xDk di k domini si dice che k è il grado (o arità) della relazione R. Una



tupla (v1, v2, … , vk) ha k componenti e con vi indichiamo la i-esima componente. Una tupla con kcomponenti è anche chiamata k-tupla.

Vediamo un esempio più esemplificativo di relazione. Consideriamo i domini:Codice_Articolo = {T100, T200}Descriz_Articolo = {Tavolo quadrato, Tavolo tondo}

una possibile relazione tra essi è:Tavoli = {(T100, Tavolo tondo), (T200, Tavolo quadrato)}

Per comodità di rappresentazione è più conveniente descrivere una relazione algebrica come unatabella come fatto in figura 3.1.

Nella tabella che rappresenta la relazione algebrica, ogni riga è una tupla (o record) e a ognicolonna corrisponde una componente (o campo). Alle colonne si danno spesso dei nomi e sono gliattributi.L’insieme dei nomi di attributi (delle colonne) di una relazione si chiama schema di relazione. Sedenotiamo con REL una relazione e il suo schema di relazione ha gli attributi A1, A2, … , Ak siscrive spesso lo schema di relazione come:

REL(A1, A2, … , Ak)

per l’esempio precedente scriveremo:

Tavoli(Art_Cod, Art_Descriz)

L’insieme degli schemi di relazione usati per rappresentare informazioni viene chiamato schema didatabase (relazionale), e i valori correnti delle corrispondenti relazioni formano un’istanza deldatabase o semplicemente il database (relazionale).

Nella definizione di relazione come insieme seguono due osservazioni fondamentali:• in una tabella non possono esistere due righe uguali• l’ordine tra le righe di una tabella non è significativo.

Art_Cod Art_Descriz

T100 Tavolo tondo

T200 Tavolo quadrato

Schema direlazione

Tuplao

record

Tabella/Relazione Tavoli

Attributi

Fig. 3.1 Rappresentazione tabellare di una relazione

Componente della tuplao campo del record



Da tali osservazioni deriva che è possibile, e necessario, individuare in ciascuna tabella un insiemedi attributi (colonne) in base alle quali identificare le singole righe, che rappresentano quindi unachiave di accesso univoca alle informazioni contenute nella tabella stessa. Questo insieme dicolonne, che va definito in fase di creazione dello schema logico, è detto chiave primaria(Primary Key - PK) della tabella.

3.3 Rappresentazione dei diagrammi entità-relazione nel modello relazionale

Per la creazione di uno schema logico relazionale è necessario, partendo da uno schema concettualedefinito in precedenza, in base al modello entità-relazione, applicare le seguenti regole.

1) Le entità dello schema concettuale diventano tabelle nello schema logico.2) Le relazioni tra entità dello schema concettuale, vengono rappresentate nello schema logico,

facendo uso delle cosiddette chiavi esterne. Una chiave esterna (Foreign Key - FK) di unatabella è un insieme di attributi che corrispondono a quelli che costituiscono la chiave primariadi un’altra tabella, e stabiliscono quindi, un riferimento tra le righe delle due tabelle (vincoli diintegrità referenziale, vedi par. 3.5).In particolare per rappresentare una relazione tra le tabelle T1 e T2 bisogna distinguere tra lerelazioni 1:1, 1:N, N:N.2.1) Relazione 1:1

Agli attributi di T1 vanno aggiunti, come chiave esterna, gli attributi che costituiscono lachiave primaria di T2, o alternativamente a T2 vanno aggiunti, come chiave esterna, gliattributi che costituiscono la chiave primaria di T1. Le due soluzioni sono del tuttoequivalenti.

2.2) Relazione 1:NSupponiamo che la relazione sia 1:N tra T1-T2. Agli attributi di T2 vanno aggiunti, comechiave esterna, gli attributi che costituiscono la chiave primaria di T1 (ma non ilviceversa!).

2.3) Relazione N:NIn questo caso va definita una nuova tabella T3, che contiene, come chiavi esterne, lechiavi primarie sia di T1 che di T2; è da notare come in questo caso la chiave primariadella tabella T3 possa essere costituita dalla totalità dei suoi attributi.

Gli eventuali attributi della relazione vengono inclusi come attributi della tabella in cui èrappresentata la relazione (T3), quella che contiene le chiavi esterne.

3.3.1 Eliminazione delle gerarchie

Il modello relazionale non permette di rappresentare direttamente le gerarchie Isa del modello E-Rquindi vanno eliminate ristrutturando entità e relazioni con tre alternative possibili che vediamorispettivamente nella figura 3.2 b), c), d) in relazione alla generica gerarchia Isa della figura 3.2 a).

1) Accorpamento delle figlie della generalizzazione nel padre. Le entità E1 ed E2 vengonoeliminate e le loro proprietà (attributi e partecipazione a relazioni e generalizzazioni) vengonoaggiunte all’entità padre E0. A tale entità viene aggiunto un ulteriore attributo che serve adistinguere il “tipo” di una occorrenza di E0, cioè se tale occorrenza apparteneva a E1 o a E2(fig. 3.2 b).



a) Generica gerarchia Isa

E0

A01

R1

A02

A11 A21

E3

E1

Isa

E2

Isa

R2 E4

c) Accorpamento padre nelle figlie

A01

R12

A02

A11A21

E3

E1 E2 R E4

A01

A02

R11

b) Accorpamento figlie al padre

E0

A01

R1

A02

A11

A21 E3

R2 E4

Tipo

d) Sostituzione gerarchia Isa con relazioni 1:1

E0

A01

R1

A02

A11 A21

E3

E1

RG1

E2

RG2

R2 E4

Fig. 3.2 Ristrutturazione gerarchia Isa



2) Accorpamento del padre della generalizzazione nelle figlie. L’entità padre E0 viene eliminatae, per la proprietà dell’ereditarietà, i suoi attributi, il suo identificatore e le relazione a cui taleentità partecipava, vengono aggiunti alle entità figlie E1 ed E2. Le relazioni R11 e R12rappresentano rispettivamente la restrizione della relazione R1 sulle occorrenze delle entità E1ed E2 (fig. 3.2 c)).

3) Sostituzione della generalizzazione con relazioni 1:1. La generalizzazione si trasforma in dueassociazioni uno a uno che legano rispettivamente l’entità padre con le entità figlie E1 ed E2.Non ci sono trasferimenti di attributi o associazioni e le entità E1 ed E2 sono identificateesternamente dall’entità E0 (fig 3.2 d)). Nello schema ottenuto bisogna verificare, dopo ognioperazione di aggiornamento delle entità coinvolte nella generalizzazione, che per ognioccorrenza di E1 e di E2 esista una occorrenza di E0 collegata (e per le generalizzazioni totali,che per ogni occorrenza di E0 c’è una occorrenza collegata in E1 o E2).



3.4 Schema logico del database di esempio

Trasformiamo adesso lo schema concettuale del database Mobili Componibili, sviluppato nelcapitolo precedente, nel corrispondente schema logico secondo il modello relazionale seguendo leregole sopra descritte.I passi per tradurre lo schema concettuale nello schema logico corrispondente sono i seguenti.

1) Per ciascun insieme di entità dello schema concettuale, viene definita una tabella nello schemalogico: Categorie, Articoli, Componenti, Laboratori, Negozi e Ordini (vedi figura 3.3).I nomi delle entità nello schema concettuale sono espressi al singolare (Categoria, Articolo,… );nello schema logico sono stati resi al plurale, seguendo una convenzione spesso adottata(Categorie, Articoli,… ). Si sarebbe potuto comunque cambiare completamente i nomi o lasciaregli stessi; ciò che importa è avere come obiettivo la comprensibilità dello schema.

Categorie

Cat_Cod Cat_Descrizione

Articoli

Art_Cod Art_Descrizione Art_Prezzo Art_Iva Art_Spese_Trasporto

Componenti

Com_Cod Com_Descrizione Com_Costo

Laboratori

Lab_Cod Lab_Indirizzo Lab_Città Lab_Telefono

Negozi

Neg_Cod Neg_Nome Neg_Indirizzo Neg_Città Neg_Telefono

Ordini

Ord_Cod Ord_Data

Fig. 3.3 Le tabelle corrispondenti ai set di entità del database Mobili Componibili



2) Per ciascuna tabella viene definita una chiave primaria che ne identifica univocamente le righe(figura 3.4).

3) Vengono definite le chiavi esterne per la rappresentazione delle relazioni 1:N tra Categorie eArticoli, tra Negozi e Ordini e tra Laboratori e Componenti, figura 3.5. Alla tabella Articoli èstato aggiunto Cat_Cod, la chiave primaria della tabella Categorie; a Ordini è stata aggiuntoNeg_Cod, la chiave primaria di Negozi; analogamente a Componenti è stato aggiunto Lab_Cod,la chiave primaria di Laboratori.

4) Vengono definite le nuove tabelle CompArt e OrdArt per la rappresentazione delle relazioniN:N tra Componenti e Articoli e tra Ordini e Articoli (figura 3.6). La tabella CompArt contienele chiavi primarie di Componenti e Articoli, la tabella OrdArt contiene le chiavi primarie diOrdini e Articoli.Si è poi aggiunto in CompArt l’attributo CompArt_Qta che specifica la quantità necessaria di uncomponente nella costruzione di un articolo. Per esempio, se l’articolo è una libreria e il

Tabella Chiave primaria

CategorieArticoli

ComponentiLaboratori

NegoziOrdini

Cat_CodArt_Cod

Com_CodFor_CodNeg_CodOrd_Cod

Fig. 3.4 Tabelle con relative chiavi primarie

Articoli

Art_Cod Cat_Cod Art_Descrizione Art_Presso Art_Iva Art_Spese_Trasporto

Ordini

Ord_Cod Neg_Cod Ord_Data

Componenti

Com_Cod Lab_Cod Com_Descrizione Com_Costo

Fig. 3.5 Tabelle del database Mobili Componibili con le chiavi esterne per le relazioni 1:N



componente è uno scaffale, CompArt_Qta rappresenta il numero di scaffali necessari percostruire la libreria. Analogamente si procede per OrdArt.

In figura 3.7 viene mostrata una rappresentazione dello schema logico relazionale del database diesempio Mobili Componibili.

CompArt

Art_Cod Com_Cod CompArt_Qta

OrdArt

Ord_Cod Art_Cod OrdArt_Qta

Fig 3.6 Rappresentazione delle relazioni N:N nel database Mobili Componibili



N

1

Fig. 3.7 Rappresentazione dello schema logico relazionale del database Mobili Componibili

NegoziNeg_CodNeg_NomeNeg_IndirizzoNeg_CittàNeg_Telefono

OrdiniOrd_CodNeg_CodOrd_Data

OrdArtOrd_CodArt_CodOrdArt_Qta

ArticoliArt_CodCat_CodArt_DescrizioneArt_PrezzoArt_IVAArt_Spese_Trasporto

CompArtArt_CodCom_CodCompArt_Qta

ComponentiCom_CodLab_CodCom_DescrizioneCom_Costo

LaboratoriLab_CodLab_IndizzoLab_CittàLab_Telefono

CategorieCat_CodCat_Descrizione

1N

1N

1N

1

N

1

N

N

1

N

1



3.5 Vincoli di integrità

Le strutture del modello relazionale ci permettono di organizzare le informazioni di interesse per lenostre applicazioni. In molti casi, però, non è vero che qualsiasi insieme di tuple sullo schemarappresenti informazioni corrette per l’applicazione.A tale scopo è stato introdotto il concetto di vincolo di integrità, come proprietà che deve esseresoddisfatta dalle istanze che rappresentano informazioni corrette per l’applicazione.E’ possibile classificare i vincoli a seconda degli elementi di una base di dati che ne sono coinvolti.Distinguiamo due categorie, la prima delle quali ha alcuni casi particolari:

• Un vincolo è intrarelazionale se il suo soddisfacimento è definito rispetto a singole relazionidella base di dati:• Un vincolo di tupla è un vincolo che può essere valutato su ciascuna tupla

indipendentemente dalle altre.• Come caso più specifico, un vincolo definito con riferimento a singoli valori viene detto

vincolo su valori o vincolo di dominio, in quanto impone una restrizione sul dominio degliattributi. Ad esempio, se una componente di una tupla rappresenta il voto di un esameuniversitario in esso sono ammessi valori compresi tra 18 e 30.

• Un vincolo è interrelazionale se coinvolge più relazioni.Ad esempio se abbiamo una tabella Esami e una Studenti possiamo richiedere che un numero dimatricola compaia nella relazione Esami solo se compare nella relazione Studenti.

3.5.1 Vincoli di chiaveI vincoli di chiave sono i più importanti vincoli intrarelazionali. Nel modello relazionale ognirelazione deve possedere una chiave e tale chiave deve identificare univocamente tutte le tuple dellarelazione a cui afferisce. Anche se è permesso che delle tuple possano contenere valori nulli(NULL) che indicano l’assenza (o la non conoscenza) dell’informazione per il corrispondentecomponente, sulle chiavi delle relazioni è vietata la presenza dei valori nulli pena l’identificazionestessa delle tuple.

3.5.2 Vincoli di integrità referenzialeI vincoli di integrità referenziale sono la più importante classe di vincoli interrelazionali.Vediamo alcune caratteristiche con un esempio: consideriamo la base di dati della figura 3.8.In essa la prima relazione contiene informazioni relative ad un insieme di infrazioni al codice dellastrada, la seconda agli agenti di polizia che le hanno rilevato e la terza ad un insieme di autoveicoli.Le informazioni della relazione INFRAZIONI sono rese significative e complete attraverso ilriferimento alle altre due relazioni: alla relazione AGENTI, per il tramite dell’attributo Agente, checontiene i numeri di matricola di agenti corrispondenti alla chiave primaria della relazioneAGENTI, e alla relazione AUTO per mezzo degli attributi Prov e Targa, che contengono gliomonimi attributi che formano la chiave primaria della relazione AUTO.I riferimenti sono significativi in quanto i valori nella relazione INFRAZIONI sono uguali a valorieffettivamente presenti nelle altre due: se un valore di Agente in INFRAZIONI non compare comevalore della chiave di AGENTI, allora il riferimento non è efficace. Nell’esempio, tutti i riferimentisono in effetti utilizzabili.

Un vincolo di integrità referenziale (foreign key o referential integrity constraint) fra un insieme diattributi X di una relazione R1 e un’altra relazione R2 è soddisfatto se i valori di X di ciascuna tupladell’istanza di R1 compaiono come valori della chiave (primaria) dell’istanza R2.



Una istanza del database precedente che non rispetta i vincoli di integrità referenziale è mostrato infigura 3.9.

La relazione AGENTI non contiene nessuna tupla con valore Matricola uguale a 456, poi AUTOnon contiene nessuna tupla con valore “RM” su Prov e 2F7643 su Numero.

INFRAZIONICodice Data Agente Art Prov Numero

987554 26/10/92 456 34 RM 2F7643630876 15/10/92 456 53 FI 4E5432

AGENTIMatricola CF Cognome Nome567 RSSM … Rossi Mario638 NREP … Neri Piero

AUTOProv Numero Proprietario Indirizzo

RM 1A2346 Verdi Piero Via TigliFI 4E5432 Bini Luca Via AceriMI 2F7643 Luci Gino Via Noci

Fig. 3.9 Una base di dati che viola i vincoli di integritàreferenziale

PKFK

FK

PK

INFRAZIONICodice Data Agente Art Prov Numero

143256 25/10/92 567 44 RM 4E5432987554 26/10/92 456 34 RM 4E5432987554 26/10/92 456 34 RM 2F7643630876 15/10/92 456 53 MI 2F7643539856 12/10/92 567 44 MI 2F7643

AGENTIMatricola CF Cognome Nome567 RSSM … Rossi Mario456 NREL … Neri Luigi638 NREP … Neri Piero

AUTOProv Numero Proprietario Indirizzo

RM 2F7643 Verdi Piero Via TigliRM 1A2346 Verdi Piero Via TigliRM 4E5432 Bini Luca Via AceriMI 2F7643 Luci Gino Via Aceri

Fig. 3.8 Una base di dati con vincoli di integrità referenziale

PKFK

FK

PK

Tabellasecondaria(correlata)

Tabellaprimaria

Tabellaprimaria



Quindi i vincoli di integrità referenziale stabiliscono delle regole da seguire per salvare le relazionidefinite tra tabelle durante l’immissione o l’eliminazione di record. Quando si applica l’integritàreferenziale non è possibile aggiungere un record ad una tabella correlata se nella tabella primarianon esistono record associati, modificare valori contenuti nella tabella primaria che genererebberorecord isolati in una tabella correlata ed infine eliminare record della tabella primaria se in unatabella correlata sono inclusi dei record correlati corrispondenti.

Non possiamo ad esempio cancellare un Agente dalla tabella AGENTI quando esistono ancora delletuple corrispondenti nella tabella INFRAZIONI, e viceversa non possiamo inserire delle Infrazioninon correlati ad alcun record nella tabella AGENTI e AUTO.

3.6 Vantaggi del modello relazionale

Nel modello relazionale, come visto nei paragrafi precedenti, i riferimenti tra le varie relazioni(tabelle) vengono realizzate mediante l’utilizzo di campi con domini comuni, questo si indicadicendo che il modello relazionale è “basato su valori”. Altri modelli logici, come il reticolare e ilgerarchico, realizzano le corrispondenze in modo esplicito attraverso puntatori e vengono pertantodetti modelli “basati su record e puntatori”. La figura 3.10 mostra un database relazionale, mentrenella figura 3.11 è rappresentato lo stesso database in un modello ideale basato su record epuntatori, dove sono stati utilizzati puntatori al posto dei riferimenti realizzati tramite valori (inumeri di matricola degli studenti e i codici dei corsi).

STUDENTIMatricola Cognome Nome Data di nascita

276545 Rossi Maria 25/11/1971485745 Neri Anna 13/04/1972200768 Verdi Fabio 12/02/1972587614 Rossi Luca 10/10/1971937653 Bruni Mario 01/12/1971

ESAMIStudente Voto Corso

276545 28 01276545 27 04937653 25 01200768 24 04

CORSICodice Titolo Docente

01 Analisi Giani03 Chimica Melli04 Chimica Belli

Fig. 3.10 Un database relazionale



Rispetto ad un modello basato su record e puntatori, il modello relazionale, basato su valori,presenta diversi vantaggi:• Esso richiede di rappresentare solo ciò che è rilevante dal punto di vista dell’applicazione

(dell’utente); i puntatori sono qualcosa di aggiuntivi, legato ad aspetti realizzativi; nei modellicon puntatori, il programmatore delle applicazioni fa riferimento a dati che non sonosignificativi per l’applicazione;

• Essendo tutta l’informazione contenuta nei valori, è relativamente semplice trasferire i dati daun contesto ad un altro (per esempio se si deve trasferire una base di dati da un calcolatore ad unaltro); in presenza di puntatori l’operazione è più complessa, perché i puntatori hanno unsignificato locale al sistema, che non sempre è immediato esportare;

• La rappresentazione logica dei dati (costituita dai soli valori) non fa alcun riferimento a quellafisica, che può anche cambiare nel tempo: il modello relazionale permette quindi di ottenerel’indipendenza fisica dei dati.

A titolo di inciso, vale la pena notare che anche in una base di dati relazionale, a livello fisico, i datipossono essere rappresentati secondo modalità che prevedono l’uso di puntatori. La differenza,rispetto ai modelli su puntatori è nel fato che qui i puntatori non sono visibili a livello logico.Inoltre, da notare anche database moderni, come quelli orientati agli oggetti, vengono introdotti gliidentificatori (di oggetti), che, pur ad un livello di astrazione più alto, presentano alcune dellecaratteristiche dei puntatori.

STUDENTIMatricola Cognome Nome Data di nascita

276545 Rossi Maria 25/11/1971485745 Neri Anna 13/04/1972200768 Verdi Fabio 12/02/1972587614 Rossi Luca 10/10/1971937653 Bruni Mario 01/12/1971

ESAMIStudente Voto Corso

28272524

CORSICodice Titolo Docente

01 Analisi Giani03 Chimica Melli04 Chimica Belli

Fig. 3.11 Database della fig. 3.10 con puntatori



3.7 Algebra relazionale

Gli operatori dell’algebra relazionale permettono di eseguire le operazioni sui dati di un databaserelazionale. Essi definiscono le operazioni rilevanti nella gestione delle tabelle (relazionialgebriche) e possono essere classificati in operatori di base e operatori derivati.I primi costituiscono un insieme funzionalmente completo, ovvero permettono di realizzare tutte leoperazioni di dati all’interno di uno di schema relazionale. I secondi sono derivabili dai primimediante opportune operazioni algebriche a volte complesse.Gli operatori di base sono proiezione, selezione, prodotto, ridenominazione, unione e differenza. Glioperatori derivati sono intersezione, giunzione naturale e giunzione.Tutti gli operatori relazionali hanno la caratteristica comune di avere come argomento dellerelazioni (tabelle) e fornire come risultato altre relazioni (ancora tabelle). Nel seguito saranno usaticome sinonimi i termini relazione e tabella.

3.7.1 Operatori di base

3.7.1.1 ProiezioneData una tabella e un insieme di attributi, la proiezione restituisce una tabella con tutte le righe diquella di partenza ma con alcune colonne (attributi) eliminati e/o risistemati nell’ordine desiderato(fig.3.12 c) e 3.13).

3.7.1.2 Selezione o restrizioneData una tabella e una condizione logica sui suoi attributi, la selezione restituisce una tabella con glistessi attributi di quella di partenza ma con le sole righe che soddisfano la condizione (fig. 3.12 d) e3.13).

3.7.1.3 Prodotto (cartesiano) o congiunzioneDate due tabelle, il loro prodotto restituisce una tabella le cui righe sono ottenute concatenando ogniriga della prima con tutte le righe della seconda (fig. 3.12 e)).

3.7.1.4 RidenominazioneData una tabella e una sequenza di attributi, la ridenominazione restituisce una tabella ottenuta dallatabella di partenza cambiandone tutti gli attributi ordinatamente in quelli della sequenza data comeargomento. Espressa in altri termini, la ridenominazione di una tabella in base a un insieme di nomiconsente di ridenominarne le colonne assegnando loro tali nomi.

3.7.1.5 UnioneDate due tabelle con gli stessi attributi restituisce come risultato una tabella contenente tutte le righedelle due tabelle considerate (fig. 3.12 f)).

3.7.1.6 DifferenzaAnche in questo caso le tabelle devono avere la stessa struttura; il risultato è una tabella checontiene tutte le righe della prima escluse quelle contenute nella seconda. In altre parole la tabellarestituita è uguale alla prima tabella epurata dalle righe uguali, cioè contenente gli stessi valori, arighe presenti nella seconda tabella (fig. 3.12 g)).

X Y Z X YProiezione

X Y Z X Y ZSelezione



A B Ca b cd a fc b d

a) Relazione R

D E Fb g ad a f

b) Relazione S

A Ca cd fc d

c) Proiezione di Rsugli attributi A e C

A B Ca b cc b d

d) Selezione su R concondizione logica B=b

A B C D E Fa b c b g aa b c d a fd a f b g ad a f d a fc b d b g ac b d d a f

e) Prodotto cartesiano R x S

a b cd a fc b db g a

f) Unione delle relazioniR e S, R ∪ S.

a b cc b d

g) Differenza delle relazioniR e S, R – S.

Fig. 3.12 Alcune operazioni dell’algebra relazionale

SELECT nomeFROM clientiWHERE saldo < 0;

Fig 3.13 Implementazione delle operazioni di PROIEZIONE e SELEZIONE in SQL. La parola chiaveSELECT in SQL corrisponde alla proiezione (e non alla selezione, fare attenzione all’infelice conflittodi notazione). Mentre la selezione viene implementata in SQL con la clausola WHERE.



3.7.2 Operatori derivati

3.7.2.1 IntersezioneDate due tabelle con gli stessi attributi, restituisce come risultato una tabella contenente tutte lerighe comuni alle due tabelle considerate. L’intersezione può essere espressa con due operazioni didifferenza:

R ∩ S = R – (R – S)

3.7.2.2 Natural join (giunzione naturale)Date due tabelle con un dominio in comune, restituisce una tabella ottenuta mediante il seguenteprocedimento:

1) viene effettuato il prodotto cartesiano tra le due tabelle;2) sulla tabella così risultante viene eseguita la selezione delle righe in cui gli attributi

appartenenti al dominio comune sono uguali;3) vengono infine ridenominati gli attributi comuni con uno stesso nome, in modo che

compaiono una sola volta.

E’ possibile definire il natural join anche tra tabelle aventi più domini in comune. Se le tabelle nonhanno domini in comune il natural join si riduce al prodotto cartesiano.

3.7.2.3 Join (giunzione)Date due tabelle con un dominio in comune, ed una condizione nella forma

A1 op A2

Dove A1 e A2 sono gli attributi delle due tabelle corrispondenti al dominio in comune e op è unoperatore di confronto (>, <, ≤, ecc.), la join restituisce una tabella ottenuta mediante il seguenteprocedimento:

1) viene effettuato il prodotto cartesiano tra le due tabelle:2) sulla tabella così risultante viene eseguita la selezione delle righe in cui gli attributi

appartenenti al dominio comune soddisfano la condizione:3) vengono infine ridenominati gli attributi comuni con lo stesso nome, in modo che

compaiono una volta sola.

Se op è l’operazione di = la join viene chiamata equijoin.

3.7.2.4 SemijoinIl semijoin della relazione R con la relazione S è la proiezione sugli attributi di R del natural join diR e S (fig. 3.14 h)).



A B Ca b cd b cb b fc a d

a) Relazione R

B C Db c db c ea d b

b) Relazione S

A B C Da b c da b c ed b c dd b c ec a d b

d) Natural join tra R e S (attributi incomune B e C)

A B C1 2 34 5 67 8 9

e) Relazione T

D E3 16 2

f) Relazione U

A B C D E1 2 3 3 11 2 3 6 24 5 6 6 2

g) Join B<D tra le relazioni T e U

A B Ca b cd b cc a d

h) Semijoin di R e S (proiezione su A,B, C del natural join in fig. d))

Fig. 3.14 Natural join, join, semijoin



3.8 Normalizzazione dei dati

Una volta impostato uno schema logico relazionale è necessario effettuare una serie di verifichesulla correttezza del procedimento svolto. Queste potranno portare a modificare la struttura delloschema stesso, al fine di renderlo corretto ed evitare il verificarsi, nella gestione dei dati, di erroridifficilmente ovviabili a posteriori.Tale processo è detto normalizzazione dello schema relazionale ed è effettuabile medianteprocedimenti di tipo algebrico, basati sui concetti di dipendenza e di scomposizione.Esistono cinque forme normali di cui le prime due sono molto semplici mentre quelle piùsignificative sono la terza e quella di Boyce-Codd che hanno certe proprietà desiderabili:• assenza o quasi di ridondanza nelle relazioni• eliminazione delle anomalie• conservazione delle dipendenze• ricostruzione della relazione di partenza a partire da quelle scomposte• mantenimento dei vincoli di integrità del progetto originale.

3.8.1 Ridondanza e anomalie

Vediamo dei comportamenti poco desiderabili di uno schema di relazione tramite un esempio.Supponiamo di avere la relazione:

INFO_FORN(NOME_FORN, INDIR_FORN, NOME_PROD, PREZZO)

che comprende tutte le informazioni di un fornitore di un particolare prodotto.In questo schema si possono riscontrare diversi problemi.

• Ridondanza. L’indirizzo del fornitore è ripetuto una volta per ogni prodotto venduto.• Inconsistenza potenziale (anomalie di aggiornamento). Come conseguenza della ridondanza

potremmo aggiornare l’indirizzo del fornitore in una tupla, lasciandolo inalterato in un’altra.Non avremmo allora un unico indirizzo per ogni fornitore, come invece ci si aspetterebbe.

• Anomalie di inserimento. Non possiamo registrare un indirizzo di un fornitore, se questoattualmente non fornisce almeno un prodotto. In una tupla potremmo porre dei valori nulli nellecomponenti NOME_PROD e PREZZO per quel fornitore, ma allora, quando per esso siintroducesse un prodotto, ci ricorderemmo di cancellare la tupla dei valori nulli? E ancorapeggio, NOME_PROD e NOME_FORN insieme formano una chiave per la relazione, e non èammissibile che si inseriscono dei valori nulli in una chiave.

• Anomalie in cancellazione. L’inverso del problema precedente è che se cancellassimo tutti iprodotti di un fornitore, involontariamente perderemmo traccia del suo indirizzo.

Nell’esempio mostrato tutti i problemi precedenti svaniscono se sostituiamo la relazioneINFO_FORN con i due schemi di relazione seguenti:

FORNITORI(NOME_FORN, INDIR_FORN)FORNISCE(NOME_FORN, NOME_PROD, PREZZO)

In tal caso FORNITORI contiene l’indirizzo di ogni fornitore esattamente una volta, quindi non vi èridondanza. Inoltre possiamo introdurre l’indirizzo di un fornitore anche se attualmente non fornisceprodotti.



Adesso però abbiamo lo svantaggio di dover eseguire una join tra le due relazione per ottenere gliindirizzi dei fornitori di un certo prodotto.Quello che abbiamo appena eseguito non è altro che una normalizzazione della relazioneINFO_FORN scomponendo tale relazione in altre due relazioni che conservano tutti i dati e ledipendenze di partenza.Vediamo adesso brevemente i concetti dipendenze e di scomposizione che sono alla base delleforme normali.

3.8.2 Dipendenze

La prima cosa da notare è che le dipendenze e la ridondanza sono strettamente legate tra di loro. Nelcaso in cui le dipendenze siano funzionali, la forma della ridondanza è ovvia. Se nella precedenterelazione INFO_FORN vedessimo le due tuple della figura 3.15:

potremmo fare l’ipotesi che Nome_Forn determini funzionalmente Indir_Forn per dedurre che ???sta per Via “Roma 16”. Quindi la dipendenza funzionale fa si che per un fornitore, tutti i campiIndir_Forn, escluso il primo, siano ridondanti. Se però non sono valide le nostre ipotesi sulladipendenza funzionale sopraddetta quest’ultimo campo non sarebbe ridondante.Quando abbiamo dei tipi di dipendenza più generali di quelle funzionali, la forma assunta dallaridondanza diventa meno chiara. In tutti i casi però sembra che la causa e la cura della ridondanzavadano mano nella mano. Cioè la dipendenza, come quella tra Indir_Forn e Nome_Forn, non solodà origine alla ridondanza, ma permette anche, la scomposizione della relazione Info_Forn inFornitori e Fornisce, in modo tale che la relazione originale Info_Forn possa essere recuperata dalledue relazioni.

Come evidenziato un tipo di dipendenza è quella funzionale, un’altra importante che analizzeremo èquella a molti valori.

3.8.2.1 Dipendenze funzionaliLe dipendenze funzionali descrivono legami di tipo funzionale tra gli attributi di una relazione.Se ad esempio un attributo ne determina un altro in modo unico, come potrebbe essere cheNome_Fornitore determina Indirizzo_Fornitore diciamo che vi è una dipendenza funzionale diIndirizzo_Fornitore da Nome_Fornitore, o anche che Nome_Fornitore determina funzionalmenteIndirizzo_Fornitore, e si indica come segue:

{Nome_Fornitore} à {Indirizzo_Fornitore}

Il significato delle dipendenze funzionali è che se abbiamo una relazione dove un certo insieme diattributi formano una chiave per tale relazione, possiamo dire che, gli altri attributi (anche unsottoinsieme della chiave) sono determinati funzionalmente dalla chiave. La chiave quindidetermina funzionalmente una relazione.

Un’ altra dipendenza funzionale dello schema di relazione Info_Forn è:{Nome_Forn, Nome_Prod} à {Prezzo}

Nome_Forn Indir_Forn Nome_Prod Prezzo

Acme Via Roma 16 Brie 3490Acme ??? Spumante 1190

Fig 3.15 Relazione con ridondanza



che ritroviamo nella seconda tabella della scomposizione.

3.8.2.2 Dipendenze a molti valoriIntroduciamo il concetto di dipendenza a molti valori con un esempio.Supponiamo di avere il seguente schema di relazione INFO_CORSO(CORSO, INSEGNANTE,ORA, AULA, STUDENTE, VOTO). In figura 3.16 abbiamo una possibile relazione per taleschema.

Corso Insegnante Ora Aula Studente Voto

Cs101 Chiarissimo 9-11 222 Rossi 30Cs101 Chiarissimo 11-13 333 Rossi 30Cs101 Chiarissimo 14-16 222 Rossi 30Cs101 Chiarissimo 9-11 222 Verdi 28Cs101 Chiarissimo 11-13 333 Verdi 28Cs101 Chiarissimo 14-16 222 Verdi 28

Fig. 3.16 Esempio relazione INFO_CORSO

In questo semplice esempio vi è un solo corso con due studenti, ma vediamo parecchi fattiimportanti che ci aspetteremmo fossero validi in qualunque relazione di questo schema. Un corsopuò avere luogo ogni volta a ore diverse in aule diverse. Ogni studente ha una tupla per ogni corsoseguito e per ogni sessione di quel corso. Il voto per il corso è ripetuto per ogni tupla.Perciò ci aspettiamo che valga in generale la dipendenza a molti valori di Ora e Aula da Corso e siindica

{Corso} àà {Ora, Aula}

cioè che esista un insieme di coppie ore-aula associate ad ogni corso e non associate agli altriattributi.Adesso se consideriamo le tuple:

u1 = Cs101 Chiarissimo 9-11 222 Rossi 30u2 = Cs101 Chiarissimo 11-13 333 Verdi 28

ossia la prima e la quinta tupla della relazione in fig 3.16. Adesso, vista la dipendenza precedente,possiamo pensare di scambiare la coppia ore-aula delle tuple precedenti ed ottenere le tupleseguenti:

u3 = Cs101 Chiarissimo 11-13 333 Rossi 30u4 = Cs101 Chiarissimo 9-11 222 Verdi 28

Se controlliamo la relazione in figura 3.16 vediamo che queste tuple sono effettivamente nellarelazione: rispettivamente la seconda e la quarta.La dipendenza molti valori sopra detta non vale perché le tuple si trovano nella relazione, ma essavale perché qualunque corso c se si tiene alle ore h1 nell’aula r1 con insegnante t1 e studente s1 cheha voto g1 e se si tiene anche alle ore h2 nell’aula r2 con insegnante t2 e studente s2 che ha voto g2,allora si terrà alle ore h1 nell’aula r1 con insegnante t2 e studente s2 che ha voto g2.

Esiste un algoritmo per controllare se sussistono dipendenze a molti valori tra due insiemi diattributi di una relazione, ma non ci dice come trovarle, per potere applicare regole discomposizione (algoritmo 7.6 pag. 476 Ullman).



3.8.2.3 Individuazione delle dipendenzePer individuare tutte le dipendenze di uno schema di relazione non è plausibile andare a vedere letuple della relazione per dedurre le dipendenze valide.Il solo modo per determinare le dipendenze funzionali che valgono per uno schema di relazione èquello di considerare con attenzione il significato degli attributi.

3.8.3 Scomposizioni

La scomposizione di uno schema di relazione R={A1, A2, … , An} consiste, nella sua sostituzione,con un insieme S={R1, R2, … , Rk} di sottoinsiemi di R tali che:

R = R1 ∪ R2 ∪ … ∪ Rk

Non è richiesto che i diversi Ri siano disgiunti.

Il motivo per eseguire una scomposizione è che essa permette di eliminare alcuni problemi visti nelparagrafo 3.8.1. Abbiamo anche visto in tale paragrafo che gli schemi di relazioni FORNITORI eFORNISCE sono una scomposizione per lo schema di relazione INFO_FORN, e risolvono iproblemi riscontrati.Ma adesso sorge un dubbio, noi ci aspettiamo che le relazioni correnti degli schemi scomposti sianola proiezione sui rispettivi attributi della relazione dello schema di partenza. Un modo percontrollarlo è quello di prendere il natural join delle relazioni scomposte e vedere se riotteniamo larelazione dello schema di partenza. Se però il natural join non permette di ricostruire la relazioneoriginale, non vi è alcun modo di ripristinarla in modo univoco.

3.8.3.1 Scomposizione lossless join (senza perdita)Se R è uno schema relazionale scomposto negli schemi R1, R2, … , Rk e D è un insieme didipendenze, diciamo che la scomposizione possiede un lossless join (rispetto a D) o è unascomposizione lossless join (rispetto a D), se per ogni relazione r (istanza attuale) di R che soddisfaD, r è il natural join delle sue proiezioni sugli Ri.

La proprietà di lossless join è necessaria se la relazione scomposta deve essere ricostruita a partiredai suoi costituenti (si esegue tra questi ultimi un natural join), di conseguenza interrogando lerelazioni scomposte otteniamo gli stessi risultati della relazione originale.

Facciamo un esempio di scomposizione che non è lossless join.Supponiamo di avere la relazione della figura 3.17.

tale relazione soddisfa le dipendenze funzionali:

Impiegato à SedeProgetto à Sede

Impiegato Progetto SedeRossi Marte RomaVerdi Giove MilanoVerdi Venere MilanoNeri Saturno MilanoNeri Venere Milano

Fig. 3.17 Relazione per la discussione sulla scomposizione lossless join



che sostanzialmente specificano il fatto che ciascun impiegato opera presso un’unica sede e checiascun progetto è sviluppato presso un’unica sede. Si osservi che impiegato può partecipare a piùprogetti anche se, sulla base delle dipendenze funzionali, debbono essere tutti progetti assegnati allasede a cui afferisce.L’idea generale delle scomposizioni è quella di scomporre la relazione di partenza sulla base delledipendenze. Allora saremmo portati a decomporre la relazione in due parti:• Una relazione sugli attributi Impiegati e Sede, in corrispondenza alla dipendenza Impiegato à

Sede.• L’altra sugli attributi Progetto e Sede, in corrispondenza alla dipendenza funzionale Progettoà

Sede.

L’istanza in figura 3.17 verrebbe decomposta, per mezzo di proiezioni sugli attributi coinvolti, nelledue relazioni in figura 3.18.

Adesso eseguiamo un natural join di queste ultime due tabelle con l’unico attributo comune, cioèSede, ed otteniamo la relazione della figura 3.19.

Osservando la relazione ottenuta notiamo che non abbiamo ricostruito tutte e sole le informazionidella relazione originaria: ad esempio l’impiegato Verdi lavora a Milano così come il progettoSaturno viene svolto presso la sede di Milano, ma in effetti Verdi non lavora a tale progetto.Abbiamo ottenuto una relazione che contiene due tuple in più, dette spurie, rispetto a quella dipartenza, quindi, la scomposizione non è lossless.

La definizione iniziale di scomposizione lossless join si adatta a qualunque numero di schemirelazionali. Però, per le scomposizioni in due schemi si può fornire un controllo molto più semplicedato dalla seguente definizione:

Impiegato SedeRossi RomaVerdi MilanoNeri Milano

Progetto SedeMarte RomaGiove MilanoSaturno MilanoVenere Milano

Fig. 3.18 Relazioni ottenute per proiezione della relazione in figura 3.17

Impiegato Progetto Sede

Rossi Marte RomaVerdi Giove Milano

Verdi Saturno Milano

Verdi Venere Milano

Neri Giove Milano

Neri Saturno MilanoNeri Venere Milano

Fig. 3.19 Risultato del natural join tra le relazioni della fig 3.18

Tuple spurie



Sia r una relazione su X e siano X1 e X2 sottoinsiemi di X tali che X1 ∪ X2 = X. Inoltre, sia X0 =X1 ∩ X2. Se r soddisfa la dipendenza funzionale X0àX1 oppure la dipendenza funzionaleX0àX2, allora r ha una scomposizione lossless join su X1 e X2.

In modo intuitivo possiamo dire che una relazione si decompone senza perdita su due relazioni sel’insieme degli attributi comuni alle due relazioni è chiave per almeno una delle due relazioniscomposte.

Nell’esempio precedente, possiamo vedere che l’intersezione degli insiemi degli attributi su cuiabbiamo effettuato le due proiezioni è costituita dall’attributo Sede, che non è primo membro dialcuna dipendenza funzionale.

Esiste un algoritmo che dato uno schema relazionale, un insieme di dipendenze funzionali e unascomposizione permette di dire se la scomposizione è lossless join (algoritmo 7.2 pag 448 Ullman).

3.8.3.2 Scomposizioni che conservano le dipendenzeUn’altra proprietà importante di una scomposizione di uno schema di relazione è che essa mantengale dipendenze.Diciamo che una scomposizione di uno schema di relazione conserva l’insieme delle dipendenze sel’unione di tutte le dipendenze nello schema scomposto implica logicamente tutte le dipendenzeiniziali.Il motivo per cui è desiderabile che una scomposizione mantenga le dipendenze è che le dipendenzesi possono considerare come vincoli di integrità (correttezza dei valori che si trovano nellecomponenti delle tuple) per lo schema di relazione.

Facciamo un esempio partendo dalla relazione della figura 3.17. Volendo rimuovere le anomalie,potremmo pensare, per ottenere una decomposizione lossless join, di sfruttare la dipendenza:

Impiegato à Sede(potremmo procedere anche utilizzando l’altra dipendenza, Progetto à Sede) ottenendo duerelazioni, una sugli attributi Impiegato e Sede e l’altra sugli attributi Impiegato e Progetto. L’istanzain figura 3.17 verrebbe così decomposta nelle relazioni in figura 3.20.

Il natural join delle due relazioni in figura 3.20 produce effettivamente la relazione in figura 3.17,per cui possiamo dire che la relazione in figura 3.17 ha una decomposizione lossless join suImpiegato, Sede e Impiegato, Progetto. In effetti Impiegato è chiave per la prima relazione, per cuila proprietà sopra discussa garantisce la decomposizione senza perdita. Però la decomposizione nonmantiene le dipendenze funzionali. Infatti, supponiamo di voler realizzare un inserimentocorrispondente all’inserimento di una tupla che specifica la partecipazione dell’impiegato Neri, cheopera a Milano, al progetto Marte (svolto a Roma). Sulla relazione originaria, cioè quella in figura

Impiegato SedeRossi RomaVerdi MilanoNeri Milano

Impiegato ProgettoRossi MarteVerdi GioveVerdi VenereNeri SaturnoNeri Venere

Fig. 3.20 Un’altra decomposizione per la relazione in figura 3.17



3.17, un tale aggiornamento verrebbe immediatamente individuato come illecito, perché porterebbead una violazione della dipendenza Progetto à Sede. Sulle relazioni decomposte, non è possibilerilevare alcune violazione di dipendenza (a meno di considerare le due relazionicontemporaneamente, ma in tal caso si verrebbero a perdere molti dei benefici delladecomposizione stessa): sulle relazione avente per attributi Impiegato e Progetto non è infattipossibile definire alcuna dipendenza funzionale e quindi non ci possono essere violazioni darilevare, mentre la tupla con i valori Neri e Milano già appartiene alla relazione su Impiegato eSede.Possiamo quindi notare come non sia possibile effettuare alcuna verifica sulla dipendenzaProgettoà Sede, perché i due attributi Progetto e Sede sono stati separati: uno in una relazione el’altro nell’altra.

In modo intuitivo possiamo dire che una decomposizione conserva le dipendenze se in ognidecomposizione, ciascuna delle dipendenze funzionali dello schema originario coinvolga attributiche compaiono tutti insieme in uno degli schemi decomposti.

In questo modo, è possibile garantire, sullo schema decomposto, il soddisfacimento degli stessivincoli il cui soddisfacimento è garantito dallo schema originario.

E’ opportuno osservare che una scomposizione può possedere un lossless join rispetto ad uninsieme di dipendenze F, pur non conservando F. L’esempio precedente in figura 3.20 è un esempiodi tale possibilità. Inoltre una scomposizione potrebbe conservare F, pur non possedendo un losslessjoin.

Esiste un algoritmo che dato uno schema di relazione, una scomposizione e un insieme didipendenze funzionali permette di dire se la scomposizione conserva le dipendenze (algoritmo 7.3pag. 454 Ullman).

Una nota a sfavore delle scomposizioni è quella che aumentano i tempi di risposta delleinterrogazioni sul database quindi è apprezzabile nel momento in cui sia necessario risolvereproblemi come quello della ridondanza, ma non in altri casi.



3.8.4 Prima forma normale

La prima forma normale (First Normal Form – 1NF) stabilisce che in una tabella (relazione) nonpossono esistere colonne (attributi) definite per contenere una molteplicità di valori. Una tabellaquindi non può contenere una struttura vettoriale o array, al contrario di quanto consentito inlinguaggi di programmazione tradizionali.Le tabelle che contengono una colonna non rispondente a questa condizione vanno trasformate,creando per ciascuna riga della tabella di partenza tante righe quanti sono i valori multipli presentinelle colonne della riga considerata, figura 3.21 a), oppure scomponendo in due tabelle come infigura 3.21 b).

N. Protocollo Uffici interessati

N. Protocollo Uffici interessati

Fig. 3.21 Prima forma normale

PersoneRec_Num Nome Cognome Data_Nascita Figlio_1 Figlio_2 Figlio_3

PersoneRec_Num Nome Cognome Data_Nascita

FigliRec_Num Nome_Figlio

a) Trasformazione senza scomposizione

b) Trasformazione con scomposizione

PK

FK(colonna di join)

Colonne ripetute



Nelle tabelle non normalizzate viene assegnato comunque spazio di memorizzazione ai “campiripetuti” anche se in essi non sono specificati valori. Inoltre il numero dei “campi ripetuti”, è fisso,ad esempio nella prima tabella della figura 3.21 b) per ogni persona sono ammessi al più tre figli,ma ci sono persone con quattro o più figli. In ultimo, ma non per importanza, se vogliamo ricercareun figlio nella tabella suddetta lo dobbiamo fare per tutte e tre le colonne di ogni riga.Tutti questi problemi sono stati risolti scomponendo la tabella di partenza in due tabelle in cui inuna (tabella Figli) sono stati spostati le colonne ripetute. L’associazione tra le due tabelle è stabilitacon la combinazione della primary key e foreign key (fig. 3.21 b)).

3.8.5 Seconda forma normale

La seconda forma normale (Second Normal Form – 2NF) riguarda le tabelle in cui la chiaveprimaria sia composta da più attributi e stabilisce che, in questo caso, tutte le colonne corrispondentiagli attributi dipendano dall’intera chiave primaria e non da una parte di essa. Naturalmente èrichiesto che la tabella sia già in 1NF. Se la tabella è dotata di chiave primaria mono attributo è giàin 2NF.Nella prima parte della figura 3.22 è mostrata una tabella che non risponde a questo requisito; infattila chiave primaria è composta da Codice_città e Codice_via; la colonna Città dipende solo daCodice_città; la colonna Via dipende invece da Codice_città e Codice_via: la colonna Città quindinon dipende da tutta la chiave, ma solo da una sua parte.Per ricondurre una tabella con questa caratteristica alla seconda forma normale è necessarioscomporla in due tabelle. Nella seconda parte della figura 3.22 entrambe le tabelle, cherappresentano globalmente la stessa realtà della precedente, rispettano la seconda forma normale.

Convertendo il progetto di un database in 2NF si eliminano buona parte dei problemi visti nelparagrafo 3.8.1.

Codice_città Codice_via Via

01 01 Verdi01 02 Bianchi01 03 Rossi02 01 Gialli

Codice_città Città

01 Roma02 Milano03 Torino04 Genova

Fig. 3.22 Seconda forma normale

Codice_città Codice_via Città Via

01 01 Roma Verdi01 02 Roma Bianchi01 03 Roma Rossi02 01 Milano Gialli

Dipendenze funzionali:

{Codice città} à {Città}{Codice città, Codice via} à {Via}



3.8.6 Terza forma normale

Delle successive forme normali diamo anche una definizione formale e per fare questo ci servonoalcune definizioni.

Una relazione può avere più attributi o insieme di attributi che possono formare una chiave. Con iltermine chiave candidata si indica un qualsiasi insieme minimale di attributi che funzionalmente lidetermina tutti, mentre il termine chiave (primaria) è riservato per una particolare chiave candidata(la “principale”). Con il termine superchiave si indica un qualunque superinsieme (è una chiave ocontiene una chiave) di una chiave.Si definisce primario un attributo A in una relazione R se A è membro di una qualunque chiave diR. Se A non e membro di alcuna chiave, allora A è non primario.

Uno schema di relazione R è in terza forma normale (Third Normal Form - 3NF) se ogni volta chein R vale X à A e A non è in X, allora X è una superchiave per R, oppure A è primario,

cioè la 3NF stabilisce che non esistono dipendenze tra colonne di una tabella se non basate sullachiave primaria, o se esistono, l’attributo determinato è primario. Naturalmente è richiesto che latabella sia già in 2NF.

Nella prima parte della figura 3.23 sono mostrate due tabelle che non rispondono a questo requisito:le dipendenze funzionali individuate per la prima tabella sono:

{N_Protocollo} à {Mittente, Tipo}{Tipo} à {Urgenza}

per la seconda:

{Tipo} à {Descrizione}

la violazione è data dal fatto che nella prima tabella la chiave primaria è N_Protocollo; la colonnaUrgenza non dipende da N_Protocollo, bensì, dalla chiave primaria della seconda tabella, ovveroTipo. Quindi la dipendenza funzionale:

{Tipo} à {Urgenza}

viola la 3NF in quanto Tipo non è superchiave per la prima tabella e Urgenza non è primario.Anche in questo caso la dipendenza va ricondotta alla tabella opportuna, creandone eventualmenteuna ad hoc. Nel nostro esempio le modifiche da apportare allo schema logico rappresentato sono leseguenti:

1) eliminare la colonna urgenza dalla prima tabella,2) aggiungere la colonna Urgenza alla seconda tabella, ottenere così la terza tabella della

figura 3.23.



Si scompone in modo che a ciascuna dipendenza corrisponde una diversa relazione la cui chiave èproprio il primo membro della dipendenza stessa. In tale modo, il soddisfacimento della 3NF ègarantito, per la definizione stessa della 3NF.Nell’esempio precedente, la separazione delle dipendenze (e quindi dei concetti da essarappresentati) è stata facilitata dalla struttura delle dipendenze stesse, “naturalmente” separate eindipendenti l’una dall’altra. In effetti in molti casi pratici, la decomposizione può essere effettuataproducendo tante relazioni quante sono le dipendenze funzionali definite (o meglio, le dipendenzefunzionali con diverso primo membro).

In generale, purtroppo, le dipendenze possono avere una struttura complessa: può non esserenecessario (possibile) basare la decomposizione su tutte le dipendenze e può essere difficileindividuare quelle su cui si deve basare la decomposizione.Vediamo un esempio semplicissimo, esaminando il quale capiamo subito quale sarebbe la naturadella decomposizione, ma che, al tempo stesso, ci permette di individuare il problema.Consideriamo la relazione della figura 3.24.

N_Protocollo Mittente Tipo Urgenza

1 001 1 Si2 002 2 No3 003 1 Si4 002 2 No5 003 3 Si

Tipo Descrizione

1 Lettera2 Memo3 Telegramma

Tipo Descrizione Urgenza

1 Lettera Si2 Memo No3 Telegramma Si

Fig. 3.23 Terza forma normale (anche BCNF)

Impiegato Categoria StipendioNeri 3 30Verdi 3 30Rossi 4 50Mori 4 50Bianchi 5 72

Fig. 3.24 Una relazione con varie dipendenze funzionali



Notiamo che soddisfa la dipendenza:{Impiegato, Categoria} à {Stipendio}

ma anche le dipendenze:{Impiegato} à {Categoria}{Categoria} à {Stipendio}

Procedendo come in precedenza, potremmo facilmente ottenere una base di dati con due relazionientrambe in 3NF.D’altra parte, per la stessa relazione, avremmo potuto individuare, insieme alla dipendenzafunzionale:

{Categoria} à {Stipendio}anche la dipendenza:

{Impiegato} à {Categoria, Stipendio}anziché {Impiegato} à {Categoria}, che avrebbe descritto il frammento di realtà con la stessaaccuratezza (o quasi). In questo secondo caso, non avremmo avuto strumenti per generare unanaturale decomposizione in 3NF, perché ovviamente la dipendenza {Impiegato} à {Categoria,Stipendio} ricopre tutti attributi e quindi non suggerisce alcuna relazione decomposta.Da notare come in un esempio così semplice l’individuazione delle dipendenze possa produrredifficoltà nella decomposizione; si può immaginare che cosa possa succedere quando la relazione ècomplessa e su di essa sono definite diverse dipendenze funzionali, fra loro interconnesse.In tal caso non si può fare a meno di trattare la normalizzazione in modo formale che però esuladagli scopi di questo documento.

3.8.7 Linee guida sulla normalizzazione

1) Partire dalle tabelle non normalizzate

2) Individuare le chiavi primarie, ed eventuali altre dipendenze funzionali.

3) Individuare e risolvere le violazioni della 1NF rimuovendo tutti gli attributi ripetuti.• Se esistono attributi ripetuti trasformare la tabella in questione creando per ciascuna riga

della tabella di partenza tante righe quanti sono i valori multipli presenti nelle colonnedella riga considerata oppure spostando le colonne ripetute in un’altra tabella dove lachiave primaria della prima tabella diventa chiave esterna in quest’ultima (fig 3.21 a) eb)).

4) Individuare e risolvere le violazioni della 2NF assicurando che ciascun attributo dipendadall’intera chiave.

• Se alcuni attributi non dipendono dall’intera chiave (dipendenze funzionali in cui iltermine a sinistra non è l’intera chiave) creare una nuova tabella con gli altri attributi chedipendono da parte di questa.

• Definire in questa nuova tabella la chiave primaria coincidente con la parte determinantedella chiave originale.

• Eliminare dalla tabella originale gli attributi (non chiave) spostati nella nuova tabella(fig. 3.22).

5) Individuare e risolvere le violazioni della 3NF assicurando che non esistano attributi non chiaveche dipendano da altri attributi non chiave.

• Se esiste un tale attributo, rimuoverlo dalla tabella originale insieme da tutti gli altri chedipendono dallo stesso determinante (dipendenze funzionali tra attributi non chiave), ecreare una nuova tabella che li contenga.



• Gli attributi determinanti diventano chiave primaria nella nuova tabella e permangononella precedente tabella in qualità di chiavi esterne.

• (Eliminare gli attributi che sono dipendenti dai determinanti dalla tabella di partenza(fig. 3.23)).

Il processo precedente permette di verificare la qualità delle relazioni, a volte non occorre farenessuna trasformazione, perché lo schema del database si trova gia in 3NF, in questo contesto, lateoria della normalizzazione costituisce un utile strumento di analisi della qualità di un progetto.Il motivo per cui a volte non necessita fare alcuna trasformazione sullo schema del database èperché la metodologia di progettazione (concettuale, logica) porta a schemi di database già in 3NF,tramite l’individuazione e la separazione dei concetti fondamentali della realtà da modellarecreando entità e/o associazioni distinte.

Per la maggior parte delle situazioni quando un progetto di schema di database si trova in terzaforma normale è più che ottimo.Nei successivi paragrafi, per completezza, illustreremo la forma normale di Boyce-Codd ebrevemente, la quarta forma normale (nella pratica poco usata).

3.8.8 Forma normale di Boyce-Codd

La forma normale di Boyce-Codd è una condizione molto forte, nel senso che non è semprepossibile portare in questa forma uno schema relazionale tramite scomposizione, senza perdere lacapacità di mantenere le dipendenze. Mentre la terza forma normale fornisce la maggior parte deivantaggi della forma normale di Boyce-Codd, per quanto riguarda l’eliminazione delle anomalie,però è una condizione che possiamo raggiungere per uno schema arbitrario di database, senzaperdere la conservazione delle dipendenze o la proprietà di lossless-join.

Uno schema di relazione R con dipendenze F, si dice essere in forma normale Boyce-Codd (Boyce-Codd Normal Form – BCNF) se ogni volta in R vale XàA, e A non è in X, allora X è unasuperchiave di R, cioè X è una chiave o contiene una chiave.

Ovvero, la BCNF stabilisce che non esistono dipendenze tra attributi di una relazione se non basatesulla chiave primaria.

Si consideri lo schema relazionale (CITTA’, VIA, CAP), abbreviato con CSZ, con le dipendenzeCSàZ e ZàC. Si può dimostrare che le chiavi di questo schema relazionale sono CS e SZ. Loschema CSZ con queste dipendenze non si trova in BCNF, dato che in CSZ vale ZàC, però Z nonè una chiave di CSZ e neppure contiene una chiave. La scomposizione però in 3NF poiché C èprimario e CS è chiave.L’esempio della figura 3.23 è in BCNF.

La ragione che sta alla base della BCNF è quella di eliminare le ridondanze che possono essereintrodotte dalle dipendenze funzionali e non eliminate dalle precedenti forme normali. In tale formanormale, facendo uso solo delle dipendenze funzionali, non è possibile prevedere nessun valore datigli altri.



3.8.8.1 Osservazioni sulla 3NF e BCNFNaturalmente dato che la 3NF è più debole della BCNF, non può eliminare tutte le ridondanze.L’esempio canonico è quello CSZ precedente, che è in 3NF e si possono avere coppie di tuple comein figura 3.25:

in cui dalla dipendenza ZàC possiamo dedurre che il valore incognito è c. Si osservi che questetuple non possono violare l’altra dipendenza CSàZ perché altrimenti sarebbero la stessa tupla.

Le due più importanti proprietà per schemi di database sono il lossless join e la conservazione delledipendenze e sono viste come un tutt’uno.I risultati a cui si è giunti sono che per qualunque schema relazionale vi è una scomposizionelossless join in forma normale Boyce-Codd e una in terza forma normale che ha un lossless join econserva anche le dipendenze. Tuttavia può non esserci una scomposizione di uno schemarelazionale in forma normale Boyce-Codd che conservi le dipendenze.Si può quindi affermare che, talvolta, la forma normale di Boyce-Codd non è raggiungibile.

Esiste un algoritmo che dato uno schema relazionale e un insieme di dipendenze funzionali trovauna scomposizione lossless join per la BCNF (algoritmo 7.4 pag. 461 Ullman).

Esiste un algoritmo che dato uno schema relazionale e un insieme di dipendenze funzionali trovauna scomposizione lossless join che conserva le dipendenze per la 3NF (algoritmo 7.5 e teorema 7.8pagg. 465-466 Ullman).

3.8.8.2 Analisi non accurataSpesso la non raggiungibilità della BCNF di uno schema di database può essere dovuta ad unaanalisi non sufficientemente accurata dell’applicazione.Facciamo un esempio. Consideriamo la relazione in figura 3.26.

Su tale relazione possiamo supporre che siano definite le seguenti dipendenze:

• {Funzionario} à {Sede}: ogni funzionario opera presso una sede;• {Progetto, Sede} à {Funzionario}: ogni progetto ha più responsabili, ma in sedi diverse, e ogni

funzionario può essere responsabile di più progetti, però, per ogni sede, un progetto ha un soloresponsabile.

Città (C) Via (S) CAP (Z)c s1 z? s2 z

Fig. 3.25 Ridondanza in 3NF

Funzionario Progetto SedeRossi Marte RomaVerdi Giove MilanoVerdi Marte MilanoNeri Saturno MilanoNeri Venere Milano

Fig. 3.26 Una relazione con decomposizione problematica



La relazione non è in BCNF, perché il primo membro della dipendenza {Funzionario}à{Sede}non è superchiave. Al tempo stesso, possiamo notare come non sia possibile alcuna buonadecomposizione di questa relazione; infatti, la dipendenza {Progetto, Sede} à {Funzionario}coinvolge tutti gli attributi e quindi nessuna decomposizione è in grado di conservarla.Se però esaminiamo meglio le specifiche, possiamo arrivare alla conclusione che avremmo potutodescrivere il frammento di realtà di interesse in maniera più appropriata introducendo un ulterioreattributo Reparto, che partiziona (sulla base dei responsabili) le singole sedi, vedi figura 3.27.

Le dipendenze possono, in questo caso, essere così definite:

• {Funzionario}à{Sede, Reparto}: ogni funzionario opera presso una sede e dirige un reparto;• {Sede, Reparto}à{Funzionario}: per ogni sede e reparto c’è un solo funzionario;• {Progetto, Sede}à{Reparto}: per ogni sede, un progetto è assegnato ad un solo reparto (e, di

conseguenza, ha un solo responsabile); la dipendenza funzionale {Progetto,Sede}à{Funzionario} è quindi ricostruibile.

Per questo schema, esiste una buona decomposizione, come mostrato dall’istanza in figura 3.28.

• la decomposizione è senza perdita, perché gli attributi comuni Sede e Reparto formano unachiave per la prima relazione;

• le dipendenze sono conservate, perché per ciascuna dipendenza esiste una relazione decompostache ne contiene tutti gli attributi;

• entrambe le relazioni sono in BCNF, perché tutte le dipendenze hanno il primo membrocostituito da una chiave.

Funzionario Progetto Sede RepartoRossi Marte Roma 1Verdi Giove Milano 1Verdi Marte Milano 1Neri Saturno Milano 2Neri Venere Milano 2

Fig. 3.27 Modifica della relazione in figura 3.26

Funzionario Sede RepartoRossi Roma 1Neri Milano 2Verdi Milano 1

Progetto Sede RepartoMarte Roma 1Giove Milano 2Marte Milano 2Saturno Milano 1Venere Milano 1

Fig. 3.28 Una buona decomposizione della relazione in figura 3.27



3.8.9 Quarta forma normale

Esiste una generalizzazione della forma normale di Boyce-Codd, che si applica a schemi direlazione con dipendenze a molti valori, e che permette di eliminare le ridondanze provocate daqueste dipendenze e non eliminate dalle precedenti forme normali.

La definizione formale è data di seguito.

Sia R uno schema di relazione e D l’insieme di dipendenze applicabili a R. Diciamo che R è inquarta forma normale (Fourth Normal Form – 4NF) se ogni volta che nella chiusura di D esiste unadipendenza a molti valori XààY, dove Y non è sottoinsieme di X e X∪ Y non contiene tutti gliattributi di R, si verifica che X sia superchiave di R.

Notiamo che il significato di una superchiave (chiave) è quello di un insieme di attributi chedetermina funzionalmente R.Mentre la chiusura di un insieme di dipendenze F, è l’insieme delle dipendenze funzionalilogicamente implicato da F.

Si osservi che se R è in quarta forma normale, allora è anche in forma normale di Boyce-Codd, cioèla condizione di quarta forma normale è più forte della forma normale di Boyce–Codd.

La 4NF possiede una scomposizione lossless join rispetto ad un insieme di dipendenze D (pag. 478Ullman).

3.9 Implementazione dello schema logico

Ricapitolando, il corretto progetto di una base di dati relazionale dovrebbe partire dalla definizionedello schema derivato dall’esame della realtà di interesse, per arrivare alla definizione di unoschema logico relazionale normalizzato.Esistono strumenti informatici detti CASE (Computer Aided Software Engineering) che aiutanol’analista in questo processo; esempio di questa classe di strumenti è Bachman della CayenneSoftware Inc.Lo schema relazionale deve essere tradotto utilizzando un RDBMS (Relational DatabaseManagement System); tra i più diffusi troviamo Oracle, Informix, DB2 e Microsoft Access.Un RDBMS, tramite il suo DDL, permette di implementare lo schema logico attraverso la creazionedi tabelle, chiavi primarie e esterne, indici, viste e così via, fa rispettare i vincoli di tupla, didominio, di unicità, di Not Null, di integrità referenziale, ecc.

Nella pratica, nella progettazione dello schema logico, per ragioni di efficienza si deve compierespesso un ulteriore passo detto di denormalizzazione in cui, in parziale contrasto con la teoriarelazionale, si ammette una certa ridondanza dei dati in cambio di migliori prestazioni del sistema intermini di tempi di risposta.



4 Progettazione fisica

La progettazione fisica permette la rappresentazione dello schema logico per mezzo di strutturefisiche di memorizzazione. Ad, esempio una relazione può essere realizzata fisicamente per mezzodi un file sequenziale, o di un file hashed o di file sequenziale con uno o più indici.Ogni tupla della relazione viene memorizzata come un record fisico nella struttura dati scelta, e ognicomponente della tupla è memorizzata in un campo del record fisico.In questo capitolo vediamo le più comuni (e semplici) strutture fisiche di memorizzazione, e alcunesemplici strategie di progettazione fisica.

4.1 Strutture fisiche di accesso

Le strutture fisiche di accesso descrivono il modo in cui vengono organizzati i dati per garantireoperazioni di ricerca e di modifica efficienti da parte dei programmi applicativi. In genere, ciascunDBMS ha a disposizione un numero abbastanza limitato di tipi di strutture di accesso; ad esempio,nei sistemi relazionali sono disponibili semplici indici, che vengono definiti dal progettista tramiteistruzioni DDL. In questo paragrafo considereremo strutture sequenziali, ad accesso calcolato e adalbero (B-tree).

4.1.1 Strutture sequenziali

Le strutture sequenziali sono caratterizzate da una disposizione sequenziale delle tuple in memoriadi massa; il file è costituito da vari blocchi di memoria consecutivi, e le tuple vengono inserite neiblocchi rispettando una sequenza. Tale sequenza può essere di vari tipi:• In una organizzazione entry-sequenced, la sequenza delle tuple è indotta dal loro ordine di

immissione.• In una organizzazione ISAM, la sequenza delle tuple dipende dal valore assunto in ciascuna

tupla da un campo di ordinamento.

4.1.1.1 Struttura sequenziale entry-sequenced (file sequenziale)Una struttura sequenziale entry-sequenced è ottimale per svolgere operazioni di lettura e scritturasequenziali. Dato che le tuple non sono disposte con un ordine prestabilito, il modo tipico diaccedere al loro contenuto è tramite scansione (scan) sequenziale. D’altra parte questaorganizzazione usa tutti i blocchi a disposizione del file e tutti gli spazi all’interno dei blocchi e,quindi, la scansione risulta particolarmente efficiente. E’ anche possibile accedere ad una tuplaspecifica, nel caso di tuple a lunghezza fissa, pur di conoscere in che ordine essa è stata inserita.Per quanto riguarda le operazioni di caricamento iniziale dei dati e di inserimento, esse avvengonoalla fine del file ed in modo sequenziale; è sufficiente gestire un puntatore all’ultima tupla per potereseguire l’operazione. Il principale problema è posto dalle operazioni di modifica e cancellazione:poiché le tuple vengono disposte in sequenza, ogni modifica che comporti un aumento delledimensioni della tupla non può essere facilmente gestita “in loco”, ed ogni cancellazione causa unpotenziale spreco di memoria, in quanto viene implementata spesso lasciando inutilizzato dellospazio.

4.1.1.2 Struttura sequenziale ISAM (file indicizzato)L’organizzazione ISAM dei file (Indexed Sequential Access Method, metodo di accesso sequenzialecon indici) assegna a ciascuna tupla una posizione in base al valore del campo chiave. Questaorganizzazione è basata sull’idea di dare alle tuple un ordinamento fisico che rifletta l’ordinamento



lessicografico dei valori presenti in un campo chiave. In realtà non è necessario che il campo sceltoper definire l’ordinamento delle tuple sia un campo chiave, anche se in questo paragrafosupporremo di ordinare i record in base al valore delle loro chiavi che, inoltre, individueranno inmaniera univoca un record. Per quanto riguarda i criteri di ordinamento, gli usuali domini di valori,come le stringhe di caratteri, gli interi o i reali, seguono un ordinamento convenzionale: per inumeri interi o reali si considera quello numerico, mentre per le stringhe di caratteri abbiamol’ordine lessicografico (o dictionary).Per aumentare la velocità di accesso al file ordinato (che chiamiamo file principale), si definisce unsecondo file (chiamato sparse index, indice rado), che consiste nelle coppie:

(<valore chiave>,<indirizzo del blocco>)

Per ogni blocco del file principale, nel file indice esiste un record (µ,b): µ è un valore non superiore(≤) a quello di tutte le chiavi contenute nel blocco b e maggiore (>) dei valori delle chiavi di ogniblocco che precede b.Il primo campo di (µ, b) è una chiave e il file indice è ordinato rispetto ad essa.

Se vogliamo trovare il blocco b del file principale che contiene un record con chiave µ dobbiamoricercare nel file indice il record:

(µj, b) tale che µj ≤ µ (µ ≥ µj)

dove il record successivo:

(µk, bk) è tale che µ < µk

in questa situazione si dice che µk copre µ.

File principale

b

µi1 … altri campi …

µi2 … …

… …

µin … …

µj1 … …

µj2 … …

… …

µ …

… …

µjn … …

µk1 … …

µk2 … …

… …µkn … …

File indice

(µi,bi)

(µj,b)

(µk,bk)

bi

bk

µj≤µjp p=1,… ,nµj>µip p=1,… ,n(angolo superiore sinistro blocco)

Fig. 4.1 File indice e file principale



4.1.1.2.1 Ricerca in un indice

La strategia più semplice consiste sicuramente nell’usare una tecnica di ricerca lineare (cioèscandire l’indice dall’inizio controllando ogni record fino a trovare l’indice che copre µ).Questo metodo non è conveniente se non per gli indici più piccoli, dato che in tal caso si puòrichiamare in memoria principale l’intero indice e, in media per eseguire una ricerca con successo,si accederà a metà dei blocchi. Comunque fare una ricerca lineare sull’indice è meglio che farla sulfile principale; se questo possiede R record per blocco, allora i record dell’indice sono 1/R rispetto aquelli del file principale. Inoltre di solito i record indice sono più corti e possono così essereraggruppati in un numero maggiore per blocco.

Un metodo migliore è rappresentato dall’effettuare una ricerca binaria sulle chiavi del file indice.Si supponga che B1,… ,Bn siano i blocchi che contengono il file indice (non il file principale) e sianorispettivamente µ1,… µn le prime chiavi di ognuno di tali blocchi.Per trovare il blocco che contiene il record del file principale con chiave µ, dovremo primaanalizzare il blocco indice B[n/2] e confrontare µ con µn/2. Se µ<µn/2, dovremo iterare il processo suiblocchi B1,… ,B[n/2]-1, altrimenti considerare i blocchi Bn/2,… ,Bn. Alla fine rimarrà un solo blocco, incui potremo effettuare una ricerca lineare per trovare nell’indice il valore chiave che copre µ.

Un metodo ancora più efficiente è noto come ricerca per interpolazione o per calcolo degliindirizzi. Esso si basa sulla nostra conoscenza della statistica della distribuzione attesa per i valoridella chiave e sull’affidabilità di tale distribuzione.Se ad esempio ci si chiede di cercare Giuseppe Rossi sulla guida telefonica, non la apriamo a metà,ma a circa il 75%, “sapendo” che è pressappoco il punto in cui si trova la R. Se ci trovassimo alla S,torniamo circa il 5%, e non a metà dall’inizio, come faremmo invece col secondo passo in unaricerca binaria.In generale, si supponga di avere un algoritmo che, dato il valore chiave µ1, fornisca il valore dellafrazione tra altre due chiavi µ2, µ3 in cui ci aspettiamo che si trovi µ1. Chiamiamo questa funzionef(µ1,µ2,µ3). Siano B1,… ,Bn i blocchi in cui si trova l’indice (o parte di esso) ed indichiamo µ2 laprima chiave di B1 e µ3 l’ultima di Bn. Sia i un indice tale che i = [nf(µ1,µ2,µ3)], allora analizzeremoil blocco Bi per definire quale rapporto vi sia tra la prima chiave di tale blocco e µ1. Come in unaricerca binaria, tale processo verrà iterato su B1,… Bi-1 o su Bi,… Bn (sull’insieme di blocchi checontiene la chiave che copre µ1) fino a che non rimarrà un solo blocco.

4.1.2 Strutture con accesso calcolato (file hashed)

Una struttura con accesso calcolato garantisce, al pari dell’organizzazione ISAM, un accessoassociativo ai dati, in cui, cioè, la locazione fisica dei dati dipende dal valore assunto da un campoparticolare ma è preferibile ad essa perché le tuple non devono essere disposte in ordine in memoriadi massa.L’idea che sta alla base dell’organizzazione hashed dei file è quella della suddivisione del file inbuckets, a seconda del valore della chiave. Per ogni file memorizzato in tal modo, esiste unafunzione hash h che prende come argomento un valore della chiave e fornisce un intero tra 0 e B-1,dove B è il numero dei bucket usati per tale file. L’intero h(v) è il numero di bucket incorrispondenza del valore chiave v.Ogni baucket è composto da un numero (possibilmente piccolo) di blocchi e questi sono organizzaticome raggruppamento. Vi è un array di puntatori, con indice tra 0 e B-1, che chiamiamo indice delbucket. In esso l’elemento i è un puntatore al primo blocco: tale puntatore viene detto testata delbucket. Nel bucket i tutti i blocchi sono collegati in una lista tramite puntatori e, nell’ultimo dellalista (o nella testata del bucket, se questo è attualmente vuoto) vi è un puntatore nullo. È normale



che B sia abbastanza piccolo da permettere che l’intero indice del bucket risieda in memoriaprincipale, mentre se così non fosse, l’indice si estenderebbe su tutti i blocchi necessari ed ognunodi questi verrebbe richiamato in memoria quando necessario.

4.1.2.1 Funzioni hashEsistono molti tipi di funzioni utilizzabili come funzioni hash h. È fondamentale che l’intervallo sia0,… ,B-1 ed è opportuno che h ripartisca le chiavi: ossia che al variare di v su tutti i possibili valoridella chiave, h(v) assuma in modo quasi equiprobabile tutti i possibili valori.Un semplice esempio di funzione hash è quello che trasforma ogni chiave in un intero e poi neprende il resto modulo B. Se iniziamo con valori interi per la chiave, calcoliamo semplicementeh(v) = v mod B.

Un esempio di file hashed che usa la funzione hash precedente con B=4 è mostrato in figura 4.2.

4.1.3 Strutture ad albero (B-tree)

Le strutture ad albero, denominate B-tree o B+-tree, sono le più frequentemente usate nei DBMS ditipo relazionale. Esse consentono accessi associativi, cioè in base ad un valore di un attributo chiave(key), senza essere necessariamente vincolare la collocazione fisica delle tuple in posizionispecifiche del file. In genere, quando un utente specifica a livello di DDL la definizione di un indicerelativo ad un attributo o una lista di attributi di una tabella, ciò corrisponde a definire opportunestrutture ad albero.Come sempre, ogni albero è caratterizzato da un nodo radice, vari nodi intermedi e vari nodi foglia;ogni nodo corrisponde ad un blocco. I legami tra nodi vengono stabiliti da puntatori; in genere, ogninodo ha un numero di discendenti abbastanza grande (non è raro il caso in cui ogni nodo ha decineo centinaia di successori); questo consente di costruire alberi con un numero limitato di livelli. Unaltro requisito importante è che la lunghezza di un cammino che collega il nodo radice da unqualunque nodo foglia sia costante (B-tree, alberi bilanciati). In tal caso, i tempi di accesso alleinformazioni contenute nell’albero sono praticamente costanti.L’organizzazione fisica avviene tramite indici (file), e siccome gli indici non sono altro che file conrecord non puntati, non vi è motivo per cui non si possa avere un indice di un indice, un indice diquest’ultimo e così via, fino a quando si arriva a un livello di indice che sia contenuto in un soloblocco, come suggerito dalla figura 4.3.

Directory deiBucket (indice)

o

17 13 5 29 o

31 o

2 o

23 7 35 19 11

0

1

2

3

Fig. 4.2 Organizzazione di un file hashed

1° Rec 5° Rec

Bucket

Blocchi



Di fatto una tale struttura potrebbe essere molto più efficiente rispetto a un file con un unico livellodi indice. Nella struttura della figura 4.3 il file principale è ordinato per valore di chiave. Il primolivello di indice consiste delle coppie (v, b) in cui b è un puntatore al blocco B del file principale e vè la prima chiave nel blocco B. Naturalmente anche l’indice è ordinato per valore di chiave. Ilsecondo livello di indice possiede coppie (v, b), in cui b punta al blocco indice di primo livello e vne è la prima chiave e così via.

La differenza tra un B-tree e un B+-tree è che negli alberi B+, i nodi foglia sono collegati da unacatena in base all’ordine imposto dalla chiave. Tale catena consente di svolgere in modo efficienteanche interrogazioni il cui predicato di selezione definisce un intervallo di valori ammissibili. Inparticolare questa struttura dati consente anche una scansione ordinata in base ai valori di chiavedell’intero file, che risulta abbastanza efficiente.Negli altri alberi (B-tree) non viene previsto di collegare sequenzialmente i nodi foglia.

4.2 Progettazione fisica di una base di dati

Nell’ambito del progetto di una base di dati, la fase finale è costituita dalla progettazione fisica, che,ricevendo in ingresso lo schema logico del DB e le caratteristiche del sistema scelto, produce inuscita lo schema fisico del database, costituito dalle effettive definizioni delle relazioni e soprattuttodelle strutture fisiche utilizzate, con i relativi parametri.L’attività di progettazione fisica di una base di dati relazionale può essere molto complessa, perchéoltre alle scelte relative alle strutture fisiche può essere necessario definire molti parametri, chevanno dalle dimensioni iniziali dei file alle possibilità di espansione, dalla contiguità di allocazionealla quantità e alle dimensioni delle aree di transito per scambio di informazioni tra memoriaprincipale e secondaria.La maggior parte delle scelte da effettuare nel corso della progettazione fisica dipende in effettidallo specifico sistema di gestione utilizzato, e quindi risulta difficile fornire una panoramicacompleta. Indicheremo solo le linee principali, che possono però essere considerate sufficienti inpresenza di basi di dati di dimensioni non enormi o con carichi di lavoro non particolarmentecomplessi.

Indice di 2° livello

File principale



Nodo (blocco) radice

Blocchi del file principale

Fig. 4.3 Un indice a molti livelli e interpretazione a struttura di albero



Assumiamo che il DBMS a nostra disposizione preveda solo file non ordinati, con possibilità didefinizione di indici. In questo contesto, ignorando gli altri parametri, la progettazione fisica puòessere ricondotta ad una attività di individuazione degli indici da definire su ciascuna relazione (aparte l’attività semplice di specifica degli schemi delle relazioni nello specifico DDL del sistemausato, con i tipi di dati ammessi per i vari attributi).Per orientarci nella scelta degli indici, è opportuno ricordare che le operazioni più delicate in un DBrelazionale sono quelle di selezione (che corrisponde all’accesso ad uno o più record sulla base deivalori di uno o più attributi) e di join (che richiede di combinare ennuple di relazioni diverse sullabase dei valori di uno o più attributi di ciascuna di tali relazioni). Ciascuna delle due operazioni puòessere eseguita in maniera più efficiente se sui campi interessati è definito un indice, che permetteun accesso diretto.Consideriamo, ad esempio, un DB su due relazioni, la prima, IMPIEGATI, sugli attributi Matricola(che costituisce la chiave), Cognome, Nome e Dipartimento (che indica il codice del dipartimento diafferenza) e la seconda, DIPARTIMENTI, sugli attributi Codice (che costituisce la chiave), Nome eDirettore.Volendo effettuare sulla relazione IMPIEGATI una selezione sull’attributo Matricola (ricerca di unimpiegato dato il numero di matricola), se sulla relazione è presente un indice su tale attributo sipuò procedere con un accesso diretto, molto efficiente, altrimenti si deve effettuare un accessosequenziale, con un costo proporzionale alla dimensione del file. Lo stesso vale per una ricercabasata sul cognome dell’impiegato; vale la pena notare che se è definito un indice su un attributo,solo le ricerche basate su tale attributo possono trarne beneficio: se la relazione ha un indice suMatricola e non ha un indice su Cognome, le selezioni su Matricola potranno essere eseguite inmodo efficiente mentre quelle su Cognome rimarranno inefficienti.Un equi-join fra le due relazioni volto a collegare ciascun impiegato con il corrispondentedipartimento, in presenza di un indice sulla chiave Codice della relazione Dipartimenti, può essereeffettuato in modo molto efficiente tramite il metodo dei nested-loop; si scandisce sequenzialmentela relazione IMPIEGATI (e questo non è un problema, perché tutte le sue ennuple contribuiscono alrisultato) e, per ciascuna di esse, si effettua un accesso diretto alla relazione DIPARTIMENTI sullabase dell’indice. Se l’indice non è definito, l’accesso alla relazione DIPARTIMENTI risultainefficiente, e tutto il join risulta più costoso.E’ importante ricordare come molti dei join che si presentano nelle applicazioni sono equi-join e peralmeno una delle due relazioni i campi coinvolti formano una chiave, come nell’esempio appenamostrato. Al tempo stesso possiamo notare come quasi sempre la chiave di una relazione siacoinvolta in operazioni di selezione o di join (o entrambe). Pertanto possiamo dire che è ragionevoledefinire, su ciascuna relazione, un indice in corrispondenza della relativa chiave (indice primario).Tali indici solitamente vengono creati in automatico dal DBMS. Inoltre possono essere definitiindici (indici secondari) su altri campi su cui vengono effettuate operazioni di selezione oppure sucui è richiesto un ordinamento in uscita (perché un indice ordina logicamente i record di un file,rendendo nullo il costo di un ordinamento). Queste osservazioni costituiscono la base di unasemplice strategia di progettazione fisica.Definiti in questo modo gli indici, si può sperimentare sul campo il comportamento della nostraapplicazione: se le prestazioni risultano insoddisfacenti, si possono aggiungere altri indici,procedendo però con grande attenzione, in quanto l’aggiunta di un indice comporta un aggravio delcarico per far fronte alle operazioni di modifica. Talvolta, inoltre, il comportamento del sistema èimprevedibile, e l’aggiunta di indici non altera la strategia di ottimizzazione delle interrogazioniprincipali, risultando del tutto inefficace. É buona norma, dopo l’aggiunta di un indice, verificareche le interrogazioni ne facciano effettivamente uso. Per questo motivo, l’attività di scelta degliindici nell’ambito del progetto fisico delle basi di dati relazionali è svolta spesso in modo empirico,con un approccio per tentativi; più in generale, l’attività di regolazione (tuning) del progetto fisicoconsente spesso di migliorare le prestazioni della base di dati.



Appendici



Appendice A - Data Flow Diagram

I data flow diagram (Diagrammi di Flusso Dati - DFD) modellano (specificano) le funzioni svolteda un sistema informativo. Hanno una attraente notazione grafica che li rende facili da usare:

L’idea alla base della costruzione di un DFD che modella una particolare realtà è quella di vedere larealtà da modellare come un macroprocesso, e a livelli successivi esplodere questo macroprocessoin sottoprocessi che rappresentano situazioni sempre più in dettaglio. I processi si scompongonofintanto che non si arriva a un processo che non è più scomponibile in altri processi (processoelementare) che viene a questo punto descritto in uno pseudolinguaggio o in linguaggio naturale.

Supponiamo per esempio di voler rappresentare il frammento di realtà che esprime la gestione di unordine nel nostro sistema informativo del mobilificio.L’esempio che segue è molto semplificato ma rende l’idea di come si costruisce un DFD.Si parte sempre da un DFD di livello 0 nel quale sono rappresentate le entità esterne chepartecipano al processo (fig A.1).

Simbolo di funzione (processo)

Simbolo di dispositivo di input

Simbolo di dispositivo di output

Simbolo di flusso dati

Simbolo di memorizzazione dati (file, database, ecc.)

NEGOZIO

NEGOZIO

GESTIONEORDINE

0

Fig. A.1 DFD-0 Entità esterne che partecipano al processo GESTIONE ORDINI

Ordine

Spedizione



Le entità esterne sono i NEGOZI, il processo che vogliamo gestire è GESTIONE ORDINI.Esplodiamo quest’ultimo processo nei sottoprocessi della figura A.2.

Esplodiamo adesso il processo Convalida Ordine come in figura A.3.

CONVALIDAORDINE

1

Fig. A.2 DFD-1 Gestione ordine

Ordine

Ordine convalidato

EVASIONEORDINE

2

Spedizione

DB Mobili (tbl Ordine)

Ordine

Negozio

ControlloCodice articoli

1

Fig. A.3 DFD-1.1 Convalida Ordine

Ordine

Chk Codice

DB

MOBILI

ControlloQuantità

2

Chk Quantità

MemorizzaOrdine

4

Ordine

RispedisciNegozio

3

Ordine rifiutato

Qta non disponibile

Articolo nonesistente

Prodottoesistente

Qta disponibile(ordine convalidato)



I processi ottenuti sono elementari, la loro funzione va espressa in pseudolinguaggio o linguagginaturale. Ci rimane da esplodere il processo Evasione Ordine così come fatto in figura A.4.

I processi ottenuti sono elementari.

L’insieme di tutti i DFD ricavati (più la descrizione dei processi elementari) descrive come avvienela gestione di un ordine nel sistema informativo del mobilificio.

Un altro formalismo usato per definire le specifiche di un sistema (asincrono) sono le Reti di Petri ese siamo interessati a modellare il comportamento di un sistema in funzione del tempo possiamofare uso dei diagrammi di transizione di stato (State Transition Diagram - STD).

Negozio

Fig. A.4 DFD-1.2 Evasione Ordine

-Dati ordine-Dati articoli

DB

MOBILI

ComposizioneOrdine

1

DocumentazSpedizione

2

ArticoliRichiesti

Spedizione

Datinegozio



Appendice B - Evoluzione dei modelli di elaborazione

Oggi si parla di database su architettura client/server e su Web, ma prima di arrivare a questesoluzioni quali erano i modelli di sistema informativo utilizzati?L’evoluzione storica di tali sistemi ha visto infatti per molti anni concentrare la maggior parte dellerisorse di calcolo intorno a diverse architetture di base. La prima, sia dal punto di vista temporaleche da quello della rilevanza assunta, è l’architettura basata sui sistemi di calcolo centralizzati(architettura HOST).

B.1 Mainframe e mini

Presentandosi per primo sugli scenari dell’elaborazione dei dati, l’HOST computer (mainframe omini) ha per lunghi anni rappresentato l’unica soluzione possibile alle richieste di elaborazioneautomatica di dati. L’architettura HOST è basata sul concetto di mettere a disposizione un unicosistema di elaborazione ad un numero più o meno elevato di utenti i quali possono usare ogniapplicazione presente sul computer centrale richiedendola da un terminale dumb (stupido), privo dicapacità di calcolo ma in grado di inviare informazioni al computer e di visualizzare quelle ricevute.Nella figura B.1 sono illustrati due modelli host-based. Si noti che l’applicazione sul mainframe e’responsabile sia dell’interazione con l’utente che della gestione dei dati in ambiente multi-utente.Ben presto è risultato evidente che questa strategia di sviluppo di un’applicazione era inefficiente,in quanto per ogni applicazione occorreva reinventare la stessa componente di gestione dei dati. Cifu dunque un’evoluzione che portò a dividere l’applicazione in due parti: un front end, responsabiledell’interazione con l’utente, ed un back end, responsabile della gestione dei dati. Il back end è unDBMS che può essere usato con ogni nuovo front end, con una crescita della flessibilità delsistema, in quanto più front end diversi possono accedere allo stesso DBMS.Come ogni cosa il modello host-based aveva vantaggi e svantaggi. Da una parte, poiché il sistema ècentralizzato, l’amministrazione è fatta da persone affidabili che garantiscono la disponibilità deidati agli utenti ed i backup di sicurezza; inoltre periferiche costose come unità a dischi, stampanti emodem, sono condivise tra diversi utenti.D’altra parte, al crescere del numero di utenti del sistema, deve aumentare la potenza di calcolo delcomputer centralizzato; i sistemi operativi proprietary, le applicazioni, la memoria e i dischicostano, e più ce ne vogliono più si paga.

B.2 Modello a personal computer isolati

Il modello precedente cambiò definitivamente negli anni ’80, con l’introduzione dei personal e delleworkstation. Il PC IBM con il DOS, il Macintosh di Apple e, più tardi, le workstation UNIX di HPe Sun cambiarono l’informatica aziendale distribuendola in più centri di elaborazione indipendenti emettendo fine al controllo centralizzato del mainframe su tutti i dati dell’azienda.I vantaggi introdotti da questo modello sono:

• le workstation ed i personal sono molto economici e facili da usare;• possono essere personalizzati sulle esigenze dell’utente con un particolare sistema operativo e

con le applicazioni più adatte;• gli applicativi per PC (word processor, spreadsheet, DBMS e pacchetti di grafica) sono tanti e

poco costosi; se non soddisfano i requisiti necessari possono essere personalizzati con semplicistrumenti di sviluppo;



Fig. B.1 Il modello basato su un host consente a più utenti di condividere applicazioni, database e periferiche

dumb

dumb

DB DB DB

DBMS&

Applic

DBMS&

Applic

DBMS&

Applic

Mainframe o minicomputer

Stampante

Periferiche condivise

Modem

dumb

dumb

dumb

Terminali stupidi

dumb

dumb

DBStampante

Periferiche condivise

Modem

dumb

dumb

dumb

Terminali stupidi

ApplicDBMS

Applic Applic

Mainframe o minicomputer



• i dati di una workstation sono personali e l’utente è responsabile della loro gestione e della loroprotezione; non è più necessario un esperto e ben retribuito system manager.

D’altra parte, le informazioni aziendali, che una volta erano centralizzate, sono ora sparse in tuttal’azienda; i dati su un PC non sono immediatamente disponibili a chiunque, e questo puòcompromettere il guadagno nel rapporto costi/prestazioni con una caduta di produttività di gruppi dilavoro; inoltre gli utenti non possono più condividere risorse costose. La figura B.2 illustra questiproblemi.

B.3 Modello rete/file server

I problemi citati nei paragrafi precedenti hanno condotto al modello rete/file server.Oggi chi usa un personal computer è probabilmente collegato ad una rete LAN (Local AreaNetwork) con cui è possibile coniugare i vantaggi di un PC con la condivisione di dati e periferiche.La figura B.3 illustra questo modello.I dati sono conservati su un file server, cioè un nodo centrale accessibile a tutti gli utenti. In genereil file server è anche il punto centrale di condivisione di periferiche, code di stampa e modem.

Fig. B.2 Il modello a personal computer isolati distribuisce le sorgenti di dati in tutta l’azienda

Stampante

Periferiche isolatedai PC

Modem

DB Host computer

DB DB1 s t Q t r 2 n d Q t r

0

20

40

60

80

1 s t Q t r 2 n d Q t r 1 s t Q t r 2 n d Q t r0

20

40

60

80

1 s t Q t r 2 n d Q t r

Databaseisolato

Databaseisolato



Poiché il file server è un computer indipendente della rete, è opportuno che sia attrezzato di unagrande quantità di memoria a disco.Un’applicazione che gira su una workstation legge e scrive sul file server; in molti casi interi fileviaggiano sulla rete per servire le operazioni dei vari PC. Ad esempio, l’utente può avere un DBMSsul suo PC e, dopo averlo lanciato, può chiedere le informazioni che si trovano in un file sul fileserver, il quale invia tutto o in parte il file che le contiene e poi si disinteressa dell’applicazione chegira sul PC dell’utente. Alla fine l’utente salva il file sul file server.Purtroppo il modello rete/file server è congenitamente incapace di servire adeguatamenteapplicazioni multi-utente a dati condivisi, come invece avviene su mainframe. Prima di tutto nonconsente la concorrenza (accesso simultaneo ad un singolo insieme di dati da più utenti) richiestadalle applicazioni multi-user; questo perché il file server gestisce file, grossi insiemi di dati, e nonpermette ad un utente di usare un file che sia stato locked (bloccato) da un altro utente.In altre parole, utenti che operano sullo stesso insieme di dati si scontrano e sono costretti adattendere in linea. Inoltre, se molte workstation richiedono ed inviano file, la rete si saturarapidamente e la performance del sistema subisce un notevole peggioramento.

Modem

Database

Fig. B.3 Il modello rete/file server collega diversi PC in modo che possano condividere dati e periferiche

Rete locale (LAN)

Stampante

File serverPeriferiche condivise Disco del

file server

Grandi quantità didati si riversanosulla rete

File X

1 s t Q t r 2 n d Q t r0

20

40

60

80



20

40

60

80



20

40

60

80


Utente A(usa File X)

Utente B(in attesa)

Utente C(in attesa)

File XFile X

Solo un utente alla voltapuò aggiornare il file X



B.4 Modello client/server

I problemi delle LAN hanno inoltre portato all’introduzione del modello client/server, chiamatoanche elaborazione distribuita o elaborazione cooperativa, che coniuga i vantaggi della rete con lecaratteristiche di accesso condiviso e alte performance tipiche del modello host-based (vedi figuraB.4).Il modello client/server è costituito da tre parti, ognuna con un compito specifico: un server backend che si occupa di gestire in modo efficiente un database tra più utenti che richiedono l’accessoconcorrente, una parte client front end usata dall’utente per interagire con i dati, una rete e unsoftware di comunicazione che costituiscono i veicoli che trasmettono i dati tra client e server.Un sistema client/server si basa su una corretta suddivisione di una applicazione in componenticlient e componenti server. Il paradigma applicativo che ha costituito un riferimento in questocontesto è illustrato nella figura B.5.

Modem

Client

Database condiviso

Fig. B.4 I database client/server condividono i dati in piccoli insiemi (righe) checonsentono un alto grado di concorrenza e di performance

Rete locale (LAN)

Stampante

Server di databasePeriferiche condivise

Riga Z

Piccole quantità didati consentonoche la LAN lavoriin modo efficiente

Riga Y

Riga X

Molti utenti possono aggiornare la stessa tabella contemporaneamente


20

40

60

80



20

40

60

80



20

40

60

80


Utente A(usa riga X)

Utente B(usa riga Y)

Utente C(usa riga Z)



E’ ovvio che suddividere logicamente un’applicazione in componenti funzionali rappresenta sempreun’operazione arbitraria, ma considerare l’applicazione come composta dai quattro moduli sopraevidenziati ha consentito un approccio molto più corretto alle problematiche client/server.Analizziamo in dettaglio ogni singolo modulo per poter cogliere meglio le implicazioni connesse.

Interfaccia utenteIn questo modulo rientrano tutti i componenti applicativi che consentono all’utilizzatore delprogramma di interagire con esso per ottenere determinati risultati. La più semplice interfacciapensabile per un modulo software è quella che consiste semplicemente nella possibilità del suorichiamo, tramite un idoneo meccanismo fornito dal sistema operativo, e nell’utilizzo dei risultatidella sua esecuzione, come una stampa, una videata, un file archiviato su qualche supporto.Ci aspettiamo ovviamente che un’applicazione moderna sia realizzata in ambiente grafico, inconformità a determinati standard e sia progettata per facilitare realmente il suo utilizzo da partedell’utente finale. Una buona interfaccia deve addirittura essere in grado di far cogliere all’utentetutte le potenzialità del sistema che sta utilizzando al di là di quelle che sono le sue immediatenecessità.

Logica applicativaLe componenti applicative che fanno sì che l’esecuzione di un programma porti a determinatirisultati rientrano in questa categoria. Può essere costituita da componenti di calcolo, di stampa, dielaborazione di un testo o di quanto altro realizza la funzione per la quale l’utente ha richiamato inesecuzione un determinato componente software.

Logica di accesso ai datiL’identificazione di questa componente ha contribuito alla corretta definizione di una applicazionerealizzata secondo il paradigma client/server. Si tratta di fatto di tutti quegli elementi che gestisconoin maniera corretta i dati forniti dall’utente al sistema o viceversa reperiti per la loro consultazionedai rapporti di archiviazione.Fanno parte della logica di accesso ai dati tutte le procedure di controllo sui dati stessi, da unasemplice validazione, come può essere quella su un valore minimo o massimo, a procedure dicontrollo della validità dei riferimenti tra i dati. Possono in certi casi esistere procedure complesseche producono operazioni in cascata a seguito di particolari eventi, come il calcolo di valori derivatidall’inserimento di una specifica tabella o la registrazione di valori di controllo quali l’identitàdell’utente, la data e l’ora dell’operazione relativamente all’esecuzione di operazioni ritenutecritiche.

Accesso ai datiIn questo gruppo rientrano tutte le componenti che si occupano di archiviare e reperire i dati suisupporti di archiviazione del sistema. Queste operazioni sono normalmente svolte da un DBMSdovendo essere fornite garanzie di integrità fisica dei dati, possibilità di accesso concorrente,ottimizzazione dei tempi di lettura e scrittura e indipendenza nei confronti del sistema hardwareutilizzato.

Alla luce di quanto detto risulta che la suddivisione ottimale dei componenti di un sistemaclient/server può risultare quella illustrata in figura B.6.

Interfacciautente

Logicaapplicativa

Logica diaccesso ai dati

Accesso aidati

Fig. B.5 Struttura di una applicazione client/server



L’intersezione tra componenti client e componenti server indica la forte difficoltà esistente in unsistema reale a definire una netta distinzione tra le due classi di componenti. Risulta infattiestremamente complesso suddividere la logica di accesso ai dati dalla logica applicativa per moltedelle applicazioni di un sistema reale. Normalmente è necessario che alcuni di questi componentivengano replicati sia sul lato client che su quello server per poter garantire al tempo stesso integritànei dati ed interfacce utenti efficaci.Un caso significativo è quello tipico sui controlli di validità del singolo dato: sebbene debba esseresicuramente implementato un meccanismo che protegga il database dall’accettare valoriincongruenti, è altrettanto vero che una buona interfaccia utente dovrà intercettare possibili errori diinserimento dati se non guidare l’utente verso l’inserimento di dati corretti. A questo scopo la logicadi controllo dovrà essere parzialmente duplicata su vari componenti dell’applicazione. Ad evitareinconsistenze, i controlli sull’integrità del dato dovranno sempre essere implementati sul lato server;tuttavia una buona logica applicativa dovrà comprendere dei meccanismi per acquisire in manieraautomatica e dinamica dal server le informazioni relative ai vincoli di integrità del dato stesso perpoterli riprodurre in locale, possibilmente passando tali informazioni ai componenti di interfacciaprogettati per guidare l’utente nella fase di immissione dei dati. Sebbene l’ultima parola in fatto dicontrolli spetti al server, sarebbe di fatto assurdo che nessun controllo fosse fatto a livellodell’applicazione client. Avremmo in questo caso un’elevata quantità di dati rifiutati durante le fasidi inserimento e modifica e di fatto caricheremmo l'utente dell'onere di conoscere tutti i vincolidefiniti all’interno dello schema del database.

La suddivisione in componenti client e server illustrata si collega anche alla necessità di unmoderno database di poter gestire vincoli di integrità logica sui dati oltre a quelli di integrità fisica.I DBMS appositamente progettati, o comunque profondamente rivisti nel contesto di architettureclient/server, vengono in certi casi definiti estesi proprio per sottolineare la presenza di meccanismiidonei a definire vincoli di integrità dei dati in essi archiviati.Parte di questi meccanismi sono in realtà implementati anche nei database commerciali per sistemicentralizzati. In particolare la struttura stessa del sistema relazionale aveva portato i progettisti diquesti prodotti, già nei primi anni del loro utilizzo, alla ricerca di meccanismi per mantenere integrii vincoli di riferimento tra le varie tabelle del database. Tuttavia non era apparso chiaro, operlomeno rilevante che i vincoli di integrità referenziale sono solo una parte, seppure significativa,della classe più ampia dei vincoli di integrità logica dei dati. Tale visione era certamentecondizionata da un approccio nello sviluppo dei sistemi informativi orientato più ai programmi chenon ai dati, tipico del periodo antecedente all’uso dei DBMS. Questo modo di pensare è nato dallamancata percezione della necessità di indipendenza tra il dato e l’applicazione e ha portato aconsiderare i vincoli di integrità sui dati come parte della logica applicativa, da implementare quindicome controlli da inserire in un programma. Le caratteristiche di distribuzione e maggioreflessibilità del sistema client/server fanno sì che un dato venga normalmente visto come patrimonio

Interfacciautente

Logicaapplicativa


Accesso aidati

Componenti serverComponenti client

Fig. B.6 Suddivisione di una applicazione client/server



comune di molte applicazioni, rendendo di fatto impossibile un approccio di controllo sulla validitàdel dato stesso implementata su ogni singolo componente software. Si rendono quindi necessarimeccanismi a livello di DBMS per la definizione a livello centralizzato, come parte integrante deldato, dei necessari vincoli di integrità logica.Facendo riferimento alla definizione classica che definisce un’informazione come un dato integratodalle conoscenze necessarie per interpretarlo, potremmo dire che i DBMS stessi sono più dei gestoridi informazioni che gestori di dati.Secondo lo schema già visto potremmo affermare che in un DBMS esteso esistono dei meccanismiche implementano l’approccio della figura B.7.

La logica di accesso ai dati, definita come componente chiave di un sistema client/server, coincideinfatti con i meccanismi definiti per garantire l’integrità dei dati sui DBMS.A questo livello, quindi, viene gestita l’integrità referenziale, cioè viene gestito l’insieme di regoleutilizzate per assicurare che le relazioni tra i record delle tabelle correlate siano valide e nonvengano eliminati o modificati per errore dati correlati; viene inoltre garantita l’integrità didominio, cioè si controlla che i dati che si vogliono inserire nel database appartengano al lorodominio di definizione (cioè se appartengono ad un insieme specifico di valori, definito al momentodella creazione delle tabelle del DB in cui devono essere inseriti). Infine vengono effettuati anche icontrolli per garantire l’integrità di comportamento, argomento considerato di particolare interesseper i sistemi informativi moderni, connesso alla visione del dato come correlato a particolari regoledi comportamento (ad esempio, nell’inserimento di un ordine è opportuno assicurarsi che la suadata non sia antecedente ad ordini precedentemente emessi).L’implementazione di questi vincoli può avvenire sia sfruttando la sintassi standard SQL, che haperò il forte limite nella necessità di basarsi su definizioni espresse al momento della creazionedelle strutture dati direttamente sulle colonne o nelle tabelle del database, sia con un approccio ditipo procedurale, che consente di realizzare moduli software direttamente all’interno del DBMS pereffettuare operazioni di controllo su determinati eventi del sistema. Il meccanismo principale digestione dell’integrità logica dei dati tramite la tecnica procedurale è quello del trigger, un insiemedi istruzioni che vengono eseguite non ad una richiesta specifica dell’utente ma al determinarsi diparticolari eventi.

Interfacciautente

Logicaapplicativa


Accesso aidati

Componenti serverComponenti client

Fig. B.7 Logica di accesso dati e integrità semantica

Integrità di comportamento

Integrità di dominio

Integrità referenziale



Un sistema client/server può raggiungere prestazioni migliori di un sistema file server, perché sial’applicazione client che il server di database collaborano a sostenere il carico di elaborazione diun’applicazione (da cui il termine “elaborazione distribuita”).Il server gestisce il database tra diversi client, mentre i client inviano, richiedono e analizzano i datiche ricevono dal server.L’applicazione client lavora con piccoli insiemi specifici di dati, come ad esempio le righe di unatabella, e non con file, come avviene invece nel sistema file server.Un server di database è intelligente, blocca e restituisce solo le righe che un client richiede, il chegarantisce la concorrenza, minimizza il traffico di rete e migliora la performance.

B.5 Pregi e difetti del modello client/server

Flessibilità dell’elaborazione distribuitaI vantaggi maggiori derivano dal fatto che il client e il server girano su diversi computer e quindi icomputer possono essere scelti con requisiti particolari per soddisfare al meglio le esigenze delledue componenti. Per esempio, è consigliabile usare processori potenti e grandi quantità di memoria,centrale o su disco, per il server, che così può conservare grandi quantità di dati e servire moltiutenti. Invece si può usare un computer meno costoso, con poca memoria ed una CPU non tantopotente, ma un mouse ed eccellenti capacità grafiche, per applicazioni client.Inoltre il sistema può rispondere con flessibilità agli inevitabili cambiamenti del software edell’hardware. Infine le dimensioni del sistema possono essere modificate in corrispondenza acambiamenti dei gruppi di lavoro, ad esempio aggiungendo nuove workstation per i nuovi assunti.

Client/server per concentrarsi su un’area dello sviluppo del sistemaOgni componente può essere specializzata per fare qualcosa nel modo migliore. Per esempio, nellosviluppo di un’applicazione client il programmatore può concentrarsi sulla presentazione esull’analisi dei dati, mentre il server si occupa della loro gestione; in altre parole il programmatorenon deve costruire un nuovo DBMS ogni volta che crea una nuova applicazione.

Client/server per risparmiareNel passato l’unico modo per eseguire un’applicazione su un database multi-utente era quello diusare mainframe o mini costosi e potenti. Questo comportava terminali a carattere, un team diprogrammatori ben pagati per la messa a punto dell’applicazione ed un team di amministratori,anche loro ben pagati, per la manutenzione. Le spese iniziali e di manutenzione per questo sistemapotevano essere astronomiche. In molti casi, un sistema client/server supporta un’applicazione damainframe con costi molto ridotti, distribuendo la potenza di calcolo su molti computer economicicollegati in rete. Anche lo sviluppo dell’applicazione è più semplice, grazie alle interfacce GUI(Graphical User Interface) e ai tool di sviluppo orientati agli oggetti.

Alcuni svantaggiPer quanto riguarda gli svantaggi, è da considerare che la riduzione di costi potrebbe non esseresignificativa nella realtà. Quando si preventivano i costi per un sistema bisogna tenere conto dimolti fattori, e non solo delle spese per l’hardware: per esempio la produttività degli utenti, siaquelli che usano gli applicativi, sia quelli che sviluppano software, sia quelli che amministrano ilsistema. Chi sviluppa software aumenterà la sua produttività grazie alle interfacce GUI ed ai toolCASE (Computer Aided Software Engineering) disponibili nel modello client/server, mentre gliutenti di applicativi e gli amministratori possono vedere diminuire la loro produttività. Infatti,l’affidabilità di un sistema client/server, fatto da un mix di componenti hardware e softwaresviluppate e gestite in modo indipendente, è intrinsecamente minore di quella di un mainframe o di



un mini centralizzato. E poi, chi chiamare in caso di guasto? Il tempo di down dovuto alla “scarsaaffidabilità” si traduce in una diminuzione di produttività degli utenti finali e degli amministratori.Il segreto per realizzare davvero un risparmio sta nella scelta del tipo corretto di applicazioni chepossono girare con successo su un sistema client server.



Bibliografia

Ullman J. D. - Basi di dati e basi di conoscenza – Jackson, 1991.

Atzeni P., Ceri S., Paraboschi S., Torlone R. – Basi di dati. Concetti, Linguaggi e architetture. –McGraw-Hill, 1996.

Guidi A., Dordolò D. – SQL – McGraw-Hill, 1996.

Yourdon E. – Analisi strutturata dei sistemi. Concetti e metodi. – Jackson, 1990.

Bobrowski S. – La granda guida a Oracle 7 – Jackson, 1995.

Ozsu M. T. – Query Processing Issues in OO KBS, 1994.http://www.cs.usask.ca/homepages/grads/moa135/826/DD-sum.html

Decker H., Teniente E., Urpì T. – How to Tackle Schema Validation by View Updating

Costal D., Teniente E., Urpì T., Farrè C. – Handling Conceptual Model Validation by Planning

Progettazione database relazionali - · PDF file2.7.4 Modelli basati sulla logica 26 ......

Documents

Transcript of Progettazione database relazionali - · PDF file2.7.4 Modelli basati sulla logica 26 ......