12-Gli archivi di dati

  • Home » 12-Gli archivi di dati
Corso Informatica

12-Gli archivi di dati

{gspeech style=2}

Introduzione
La necessità di ricordare è una delle più pressanti della nostra vita: ci sono le scadenze dei pagamenti, gli impegni di lavoro, le ricorrenze familiari, i numeri di telefono di amici e colleghi, gli appuntamenti dal dentista, ecc. Le necessità personali sono, comunque, abbastanza circoscritte e può essere sufficiente tenere aggiornata e consultare frequentemente la propria agenda. Se, però, si pensa a situazioni più complesse, come la gestione dell’anagrafe in un Comune o duella degli ordini in un’azienda, ci si rende corto che la mole dei dati da ricordare è imponente, tanto che la loro archiviazione può costituire un problema.
II computer offre la possibilità di registrare e poi di reperire o aggiornare, in tempi brevi, grandi quantità di informazioni e questa sua caratteristica è diventata, nel tempo, addirittura più importante della capacità di calcolo. Naturalmente i dati non devono essere memorizzali alla rinfusa, ma secondo una logica rigorosa, che permetta di consultarli in modo efficiente. Consideriamo, per esempio, i libri della nostra biblioteca. Se sono molti, può convenire utilizzare il computer per organizzare un semplice catalogo.


Le informazioni che registriamo devono aiutarci quando cerchiamo qualcosa e quindi devono essere sufficienti a rispondere a domande del tipo:

Abbiamo libri di Svevo?
Ci sono libri di medicina?
Abbiamo Il fu Mattia Pascal?
Qual è l’elenco di tutti i nostri libri?

Se i nostri libri sono veramente moltissimi, può aver senso anche registrare la posizione che ognuno occupa. Avremo quindi bisogno di memorizzare, per ogni libro, il titolo, l’autore, l’editore, l’argomento, la posizione. Se gli autori sono più di uno (per esempio, Fruttero e Lucentini), li registriamo insieme. Per la posizione, possiamo assegnare un numero alle stanze (1 per il salotto, 2 per Io studio ecc.) e poi all’interno di una stanza numerare i ripiani che vengono utilizzati per i libri. In una biblioteca pubblica, dove sono richieste possibilità di consultazione molto più articolate, queste informazioni non sarebbero affatto sufficienti e dovrebbero essere organizzate diversamente, ma nel nostro raso possono bastare a rispondere alle domande ipotizzate. I dati che abbiamo deciso di memorizzare (titolo, autore, editore, argomento) non esauriscono tutte le notizie riguardanti il libro e rappresentano, rispetto all’oggetto vero e proprio, un’astrazione: non dicono nulla, infatti, della sua grandezza, del disegno sulla copertina, dei numero di pagine, dell’anno di edizione ecc.: servono, però, al nostro scopo.

SCEGLIERE I DATI
Quando si risolve un problema, è molto importante saper scegliere i dati veramente utili e sono stati fatti molti studi sulle tecniche per individuarli e organizzarli opportunamente. Per “ricordare” i dati si utilizzano delle memorie ausiliarie, o memorie di massa, come il disco rigido o il dischetto o il nastro magnetico. Si tratta di dispositivi periferici sui quali i dati vengono registrati in modo permanente (cioè non si cancellano quando si spegne il computer). I dati possono essere trasferiti dall’elaboratore alla memoria di massa (operazione di scrittura) oppure dalla memoria di massa all’elaboratore (operazione di lettura). Anche il video, la tastiera e la stampante sono dispositivi periferici: non servono a registrazioni permanenti, ma permettono all’elaboratore di comunicare con l’esterno. Come si è detto, i dati non vengono registrati alla rinfusa, ma vengono raggruppati in file: un file occupa una certa quantità di memoria ausiliaria. Su uno stesso disco o dischetto o nastro possono essere memorizzati più file e ognuno di essi è identificato da un nome. Il contenuto di un file può essere di diversi tipi. Quando si scrive un testo, utilizzando un word processor e lo si “salva”, non si fa altro che creare un file, identificato da un nome ben preciso, per esempio “lettera.doc”. Si può immaginare questo file come la successione di tutti i caratteri che compongono il testo. In realtà, dal punto di vista fisico, non è così, ma questo aspetto del problema è gestito dal word processor e non da chi lo utilizza. Un testo si può poi rileggere, modificare o anche cancellare. Anche i programmi si possono considerare come particolari tipi di testo. Anch’essi vengono “salvati”, cioè memorizzati su un file identificato da un nome (per esempio, un programma in Cobol si potrebbe chiamare “stampa.cob”) e poi possono essere modificati o cancellati. Se un file contiene dei dati organizzati secondo un certo schema, lo si può immaginare, invece, come una tabella.

Tornando all’esempio della nostra biblioteca, le informazioni registrate sono organizzale come in tabella:

Titolo

Autore

Editore

Argomento

Posizione

A che punto è la notte

 Fruttero e Lucentini

Mondadori

 Giallo

14

 La struttura degli algoritmi

Fabrizio Luccio

 Boringhieri

informatica

23

 …

…

 …

…

 …

Ogni riga della tabella si dice record e rappresenta un solo oggetto, in questo caso un libro. Titolo, autore, editore, argomento e posizione sono i campi del record e costituiscono le informazioni relative all’oggetto libro.

Si può pensare il file come una successione di record registrati in modo permanente uno dietro l’altro su una memoria di massa.
Anche in questo caso, dal punto di vista fisico, le cose non stanno proprio così, ma se si lavora con un linguaggio di programmazione, specialmente se si tratta di un linguaggio dell’ultima generazione, non è necessario conoscere il modo in cui fisicamente avviene la registrazione dei record.
È indispensabile, invece, sapere molto bene come si opera con un file. Prima di tutto un file deve essere creato.
Se, per esempio, decidiamo di registrare le informazioni sulla nostra biblioteca, nel momento in cui, per la prima volta, inseriamo dei dati, essi vengono salvati in un file, al quale viene assegnato un nome; potrebbe essere “libri.doc”. AI file si possono poi apportate delle modifiche: più precisamente, è possibile:

  • inserire nuovi record, che verranno aggiunti a quelli già esistenti;
  • cancellare dei record: una volta cancellati, non risultano più presenti nel file;
  • modificare il contenuto dei record.

MODIFICARE E RICERCARE
È importante osservare che, per cancellare o modificare un record, occorre prima ricercarlo. Inoltre, non bisogna confondere l’operazione di cancellazione dell’intero file, con la cancellazione di alcuni record al suo interno.
Dopo la prima, infatti, il file non è più reperibile: dopo la seconda, invece, esiste ancora, anche se con qualche record in meno. Se rappresentiamo il file come una tabella, possiamo pensare l’operazione di inserimento come un’aggiunta di nuove righe, mentre, per quanto riguarda la cancellazione e la modifica, si tratta di posizionarsi su una particolare riga per poi cancellarla o modificarla.
Ci sono file che sono soggetti a modifiche molto frequenti: basti pensare, per esempio, al file che contiene le prenotazioni dei voli di una compagnia aerea: avvengono continuamente inserimenti di nuove prenotazioni e anche variazioni o cancellazioni riguardanti prenotazioni già fatte. I dati, mantenuti opportunamente aggiornati per mezzo di queste operazioni, possono essere consultati.
Si può effettuare la ricerca di un particolare record (facendo riferimento ancora al nostro esempio, si potrebbe cercare se, fra i libri della nostra biblioteca, c’è quello dal titolo Il fu Mattia Pascal): tale operazione può avere esito positivo o no. Si possono ricercare tutti i record con certe caratteristiche (tutti i libri di Svevo o tutti i libri di medicina): anche in questo caso, si potrebbe non trovare alcun record con i requisiti richiesti. Si può, infine, consultare l’elenco di tutti i record del file (la lista di tutti i nostri libri).
Perché sia possibile gestire un file ed effettuare operazioni su di esso, occorre che siano predisposti opportuni programmi. Ci sono, però, particolari servizi, riguardanti i file, che vengono messi a disposizione dal sistema operativo. Utilizzando i comandi appositi, gli si può chiedere,infatti, di copiare un file, di cambiargli nome, di cancellarlo ecc. Si può anche ottenere la lista dei nomi di tutti i file che sono stati memorizzati su un disco.

La Struttura degli archivi di dati
La progettazione di un archivio di dati comprende un’attenta analisi dello scopo che tale archivio dovrà avere. La dimensione dell’archivio va scelta accuratamente tenendo conto principalmente della dimensione massima che esso potrà assumere e scegliendo di conseguenza il supporto fisico più adeguato.
La struttura del singolo record deve essere creata in modo tale da contenere tutte le informazioni di cui si avrà bisogno una volta che l’archivio sarà utilizzato.
Infine la disposizione dei dati dovrà essere tale da minimizzare i tempi di ricerca e le operazioni di inserimento e cancellazione di record nell’archivio.
Se si volesse creare un archivio contenente le informazioni su nome, cognome, data di nascita e classe di tutti gli allievi di una scuola superiore bisognerebbe iniziare considerando:

  • la dimensione massima dell’archivio: il numero di studenti attuali (probabilmente un valore più elevato nell’ipotesi che il numero di studenti cresca con gli anni);
  • la struttura del singolo record: dal momento che interessano nome, cognome, data di nascita e classe, il record avrà una struttura del tipo: Nome, Cognome, Data di Nascita, Classe.
    Nel caso in cui sia specificata la funzione che dovrà avere l’archivio potrebbe essere utile aggiungere campi che serviranno in futuro.
    Se, per esempio, si volesse mantenere le informazioni sulle assenze totali di ogni alunno si potrebbe aggiungere un campo assenze.
    La scelta di come ogni singolo campo debba essere rappresentato è competenza del progettista dell’archivio.
    In questo caso, per esempio, vi sono infiniti modi per rappresentare una data: gg/mm/aaaa oppure gg/mm/aa oppure ancora gg/mese(in lettere)/aaaa, ecc.
    Tra queste varie sintassi si sceglierà la più comoda per le operazioni che si dovranno effettuare sull’archivio. Infatti, supponendo di volere calcolare l’età di ogni singolo alunno, sarebbe più comodo avere la data nella notazione gg/mm/aaaa per effettuare la sottrazione rispetto alla data attuale;
  • la disposizione dei record nell’archivio: in questo caso supponendo di lavorare sulle singole classi, una disposizione adatta sarebbe in ordine alfabetico classe per classe. Si immagini infatti di dovere effettuare operazioni sugli alunni di una stessa classe: i tempi sono minimizzati nel caso in cui tutti i record relativi agli alunni siano vicini.

La registrazione dei dati negli archivi e il loro prelievo
La necessità di recuperare informazioni da un archivio rende indispensabile utilizzare delle memorie di massa per la loro registrazione e che queste memorie devono risultare le più veloci possibile per non appesantire le operazioni di ricerca o inserimento.
Diventa quindi importantissimo utilizzare delle tecniche in grado di ottimizzare la disposizione delle informazioni nelle memorie, al momento dell’inserimento dei dati. Si mira quindi a ridurre lo spazio utilizzato, i tempi di accesso alle memorie e i tempi di delle informazioni già memorizzate.
In base a tutto ciò, analizzeremo ora le tecniche di registrazione delle informazioni per ottimizzare questi aspetti.

Registrazione sequenziale
Questa tecnica consiste nella registrazione in successione delle informazioni. Questo permette di generare un ordine di registrazione che sarà conservato anche in fase di lettura.
Questo tipo di struttura permette di scrivere i record in successione uno dopo l’altro e di recuperarli scorrendo nuovamente l’archivio dall’inizio fino al raggiungimento del record richiesto, come in figura.

Per comprendere meglio il funzionamento, indichiamo in un generico linguaggio di programmazione, detto pseudocodice, le varie operazioni. Lo pseudocodice per l’inserimento di elementi con registrazione sequenziale, potrebbe essere il seguente:

Indice=0
Do while (Not(Archivio[Indice]=EOF))
  Indice=Indice+1
Loop
Archivio[Indice]Indice=Recorwordef_da_inserire Archivio[Indice]Indice=Indice+1
Archivio[Indice]=EOF

Prelievo dei dati in modo sequenziale
Bisogna pensare ad un metodo che segnali la fine delle informazioni registrate e che permetta di terminare una ricerca in caso di mancato ritrovamento del record richiesto.
Tutto ciò si ottiene introducendo un EOF che rappresenta l’ultima posizione valida dell’archivio. Uno pseudocodice per la ricerca delle informazioni registrate potrebbe essere il seguente:

Flag_Trovato=False
Do while (Not(Archivio[Indice)=EOF))
  If Archivio[Indice]=Recorwordef_cercato Then           Flag_Trovato=True
 Exit Do End If
 Indice=Indice+1
 Loop
If Flag_Trovato=True Then
 Return Indice
End If

I principali problemi di questa organizzazione consistono nei tempi di accesso.
Si pensi ad un archivio contenente un elevato numero di informazioni e di voler recuperare un record che sfortunatamente è stato registrato in ultima posizione.
Bisognerebbe scorrere tutti i record fino a quando non si preleva quello corretto che equivale a fare N accessi dove N è la lunghezza della memoria ovvero il numero di record inseriti.
In media (supponendo che si trovi a metà) è proporzionale a M/2 con M il numero totale degli elementi del file.
Sicuramente non si tratta di una tecnica molto efficiente.
Si è comunque osservato che, per archivi moderatamente numerosi, questa tecnica rappresenta un buon compromesso tra la velocità di accesso e la semplicità di gestione.
Infatti pensando alla realizzazione di un’organizzazione di questo tipo appare evidente che il principale vantaggio è la semplicità di implementazione.

Registrazione ad accesso casuale
Questa tecnica consiste nel creare una corrispondenza tra un valore numerico ed una posizione all’interno della memoria di massa. Ad esempio, se dobbiamo scrivere il record numero 17 automaticamente siamo subito al corrente della posizione in cui si trova.
La prima ipotesi è che la dimensione dei singoli record sia uguale per tutti. Questa è un’ipotesi che trova riscontro nella realtà, in quanto per la memorizzazione dei record si fa sempre riferimento a strutture dati dimensionate in modo costante.
Per esempio, se si dovessero memorizzare i dati relativi alle matricole di un’università risulterebbe comodo creare un record mediante una struttura come la seguente:

campo Nome rappresentato da un massimo di 20 caratteri;
 campo Cognome costituito da un massimo di 20 caratteri;
 campo Matricola rappresentato da un intero corto di 16 bit;
campo Indirizzo di 20 caratteri.

In questo caso si avrebbe una dimensione per ogni record di:
(20 + 20 + 20) x 1 byte + 2 byte= 62 byte

A questo punto per scrivere nella quarta posizione basterebbe spostarsi di 3 x 62 = 186 byte.

Il prelievo dei dati con accesso casuale
Come per la scrittura, si osserva facilmente che questa organizzazione permette di accedere ad un qualsiasi record senza obbligatoriamente scorrere tutti i precedenti.
Il tempo di accesso è stato notevolmente ridotto a scapito di una più complicata gestione delle operazioni di lettura e scrittura.

Registrazione ad indice
In questo caso è possibile accedere direttamente all’elemento desiderato tramite il valore di un campo chiave. Ora sono necessari più file: uno che contiene i dati veri e propri e dei file aggiuntivi che mettono in corrispondenza la chiave con la posizione che tale record occupa all’interno del file dei dati. Si immagini, per esempio, un archivio di alunni una scuola. In questo caso si potrebbe pensare di avere delle tabelle con degli indici di vario tipo: indice sul Nome, oppure sul Cognome o ancora sulla Matricola.


Per esempio, un indice sul Nome prevedrebbe un’ulteriore tabella, in grado di legare il nome alla posizione in cui si trova tale record nella tabella originale.
Il campo Nome viene chiamato, dopo questa operazione, chiave di ricerca in quanto è legato direttamente alla posizione in cui si trova quel record all’interno del file di dati.
II vantaggio di questo tipo di organizzazione sta nella fase di ricerca dei dati.

Prelievo dei dati negli archivi con registrazione ad indice
II metodo degli indici è particolarmente vantaggioso in quanto permette di lavorare con tabelle di dimensioni minori, le tabelle degli indici, anziché le tabelle originali.
Una tecnica utilizzata molto spesso è quella di lasciare le tabelle originali nelle memorie di massa, portando le tabelle degli indici nelle memorie più veloci del sistema, quelle ad
accesso casuale e volatili, le RAM (Random Access Memory).
In questo modo, essendo queste seconde memorie molto più veloci di quelle di massa, risultano più veloci le operazioni di ricerca, ricorrendo alla memoria di massa solo dopo aver scoperto l’effettiva posizione del record.
Quindi appare chiaro che per le operazioni di ricerca, cancellazione, ma anche inserimento è obbligatorio fornire la chiave, cioè il Campo, secondo cui si è creato l’indice, in quanto è l’unica in grado di distinguere tra loro i record.
Questa condizione si verifica soltanto nel caso in cui non esistano due copie identiche della stessa chiave. Nell’esempio appena visto non avrebbe molto senso prendere come chiave il Nome, in quanto potrebbero esistere due persone con Io stesso nome e di conseguenza non si capirebbe a quale ci si sta riferendo.
Questo significa che la chiave deve essere primaria, ovvero diversa per ogni elemento all’interno della tabella, condizione sicuramente verificata dal campo Matricola.

Registrazione e prelievo dei dati con organizzazione ad accesso calcolato
Si tratta di archivi nei quali la ricerca di un determinato record avviene in base ad una chiave primaria che, sottoposta ad una particolare procedura che adesso analizzeremo, indica la posizione del record.
Conoscendo la chiave, che potrebbe essere un campo come Matricola del caso precedente, si può quindi risalire al record ricercato attraverso una funzione, detta funzione di hash, che data la chiave restituisce un numero indicante la posizione del record in questione. Naturalmente se la chiave di ricerca è un campo numerico la funzione di hash dovrà opportunamente trasformare questo insieme valore di caratteri alfanumerici. Ipotizziamo di avere l’archivio degli incassi giornalieri di un negozio.
Una classica funzione di hash potrebbe essere la seguente:

Y= giorno*mese Mod 365

(Ricordiamo che Mod indica il resto della divisione.)
Quindi, in base alla coppia giorno, mese, con la funzione di hash è possibile risalire alla posizione del record.

Bisogna osservare come la coppia Giorno/Mese sia una chiave primaria, in quanto, trattandosi di incassi giornalieri, è impossibile che esista un’altra coppia uguale di giorno e mese.
Si immagini di cercare l’incasso dell’11 Maggio. La funzione sarà:

y(chiave) = 11 * 5 Mod 365 = 55

quindi la posizione sarà la 55.
Il valore 365 è stato utilizzato in quanto si è supposto che in un anno non esistono più di 365 giorni!
Si presenta ora un problema: si pensi di cercare l’incasso dell’11 Maggio e successivamente del 5 Novembre.
Si ottiene rispettivamente la posizione 11 * 5 = 55 e la posizione 5 * 11 = 55. Praticamente la stessa posizione dovrebbe contenere due record diversi: si è verificata una collisione.
Questo fenomeno si può ottenere sia nelle fasi di registrazione che nelle fasi di ricerca delle informazioni.

La gestione del fenomeno delle collisioni
Per gestire questo strano fenomeno della collisione sono state studiate e messe a punto diverse tecniche. Le principali sono:

  • la scansione lineare;
  • la scansione di tipo quadratico;
  • utilizzo di area separata (detta di overflow).

La scansione lineare rappresenta la tecnica più semplice e, come dice la parola, si preoccupa di cercare il record per il quale è stata generata una collisione, di seguito al record che l’ha generata. Si prosegue quindi in successione fino a che non si trova il record.
Nel caso invece di inserimento di un nuovo record e di collisione, l’inserimento viene tentato in posizioni successive finché non si trova una cella libera. Se si immagina di applicare questo metodo e di ottenere una successione più o meno lunga di fenomeni di collisione ci si rende subito conto che si vengono a creare grandi raggruppamenti di record in sequenza tra loro.
Per risolvere questo problema di raggruppamenti di record si è pensato di fare in modo che la ricerca di posizioni libere non avvenga in maniera sequenziale ma, per esempio, in maniera quadratica.

Quindi anziché aumentare di uno la posizione cella in cui provare ad inserire l’elemento si prosegue in maniera quadratica provando subito la cella successiva, se non libera saltando due celle, se non ancora libera saltando quattro celle, e così via…
Con questa tecnica si evita di creare imponenti blocchi di dati generati dalle collisioni, ma si cerca di distribuirli lungo tutto il file.
L’ultimo metodo utilizza invece delle aree apposite per la memorizzazione dei record che hanno generato delle collisioni. Queste aree dette di overflow vengono riempite mano a mano che si generano collisioni e sono proprio utilizzate come aree di riserva.
Questo permette di continuare a lavorare unicamente sul file finché non si genera una collisione e, solo in quel momento, analizzare l’area di overflow alla ricerca del record.
Ad ogni record corrisponde quindi un’area di overflow. Se non si trova il record nella prima posizione cercata si continua a cercarlo in maniera lineare nell’area di overflow dedicata a quel particolare record, come indicato in figura.
Infatti in questa figura appare chiaro come nel caso in cui si stia cercando il record relativo all’11 Maggio non ci sia nessun problema, in quanto si trova nella posizione in cui ci aspettavamo di trovarlo. Ma se si cerca il 5 Novembre allora devo cercare nell’area di overflow relativa all’ 11 Maggio e sicuramente lo troverò.

Alcuni particolari metodi di ricerca
In questo contesto di ricerca dei dati negli archivi abbiamo ritenuto opportuno approfondire l’argomento dei metodi di ricerca e della loro efficienza.
In particolare, escludendo il caso dell’accesso casuale e delle collisioni, il modo più istintivo per cercare un elemento all’interno di un elenco è quello di scorrere tutti gli elementi finché non si trova quello desiderato.
Esistono alcuni algoritmi in grado di dimostrare che non è il metodo più efficiente ma che è possibile dimezzare i tempi di ricerca utilizzando dei piccoli accorgimenti. Questi piccoli accorgimenti sono dei veri e propri algoritmi di ricerca:

  • ricerca sequenziale (scorrimento di tutti gli elementi fino a quello desiderato);
  • ricerca sequenziale a blocchi;
    ricerca dicotomica.

La ricerca sequenziale a blocchi
La ricerca sequenziale a blocchi è nata nel tentativo di rendere più veloce la semplice ricerca sequenziale. L’ipotesi di lavoro è che il file su cui effettuare la ricerca sia stato precedentemente ordinato secondo la sua chiave di ricerca. In questo caso è possibile suddividere il file originario in un certo numero di blocchi di uguale lunghezza.
La ricerca verrà effettuata confrontando il record cercato solamente con il primo record di ogni blocco e:

  • se la chiave è maggiore della chiave del primo record del blocco allora si passa al blocco successivo;
  • se la chiave è minore della chiave del primo record del blocco allora si ritorna al record precedente e se non si trova significa che il record non è presente.

ESEMPIO
Un file tiene traccia degli articoli di un supermercato indicando il loro codice con la relativa descrizione.
Il file non è ordinato, quindi per poter utilizzare la ricerca sequenziale a blocchi è necessario prima effettuare un ordinamento e, supponendo come chiave di ricerca il Codice Articolo, si otterrà il file in figura.

A questo punto si supponga di suddividere il file in blocchi di tre record ciascuno di record più un blocco finale di un record solo. Si immagini ora di ricercare l’articolo di codice 0005:

 

  1. partendo dal primo blocco con primo elemento 0001 si vede che 0005 > 0001 quindi:
  2. si passa al blocco successivo e si ottiene 0005 > 0004 quindi:
  3. si passa al blocco successivo 0005 < 0007 quindi:
  4. si torna al blocco precedente e si esegue una ricerca sequenziale al suo interno parte dal secondo record:
  5. 0005 = 0005 TROVATO.

Con questa tecnica si è così ottenuto un miglioramento della velocità di ricerca dei record passando da tempi proporzionali al numero di elementi del file a tempi proporzionali alla radice quadrata.

La ricerca dicotomica
La ricerca dicotomica è la più efficiente tra quelle presentate. Il principio di funzionamento si basa nell’effettuare la ricerca del record solo nella metà del file che lo contiene, ripetendo questi passi fino al suo recupero.
Si immagini, per esempio, di avere il file trattato nell’esempio precedente.
Si divide il file in due blocchi: il primo contenente i record da 1 a 5, il secondo conte i record da 6 a 10.
Supponendo di dovere cercare il record di chiave 0005 si valuta se 0005 >0001 se 0005 > 0006.

Essendo 0005 > 0001, ma non 0006 il record si troverà nel primo blocco.
A questo punto si divide il primo blocco in altri due sottoblocchi (dei quali uno di tre record in quanto contenente un numero dispari di elementi).
Ragionando come per il Passo 1 si ottiene che il record cercato si troverà nel secondo blocco in cui è stata suddivisa la prima metà del file. Questo secondo blocco contiene i record di chiave 0004 e 0005 (quella cercata).
Suddividendolo ancora si ottengono gli ultimi due blocchi di un solo elemento: il primo con il record 0004 ed il secondo con il record 0005, quindi l’elemento è stato trovato.
La ricerca dicotomica permette di ottenere un tempo di ricerca proporzionale al logaritmo in base 2 del numero dei record presenti nel file.

Gestione degli indici nei file
Nei paragrafi precedenti abbiamo introdotto il concetto di indici, descrivendoli come elementi aggiuntivi inseriti in apposite tabelle, in grado di legare la chiave primaria alla posizione del record nella tabella.
Il vantaggio di questa operazione consisteva nel poter effettuare le ricerche in base alla chiave primaria, ma solo nella tabella degli indici, ed una volta scoperta la posizione del record nella tabella vera e propria, accedervi per recuperare tutti i campi.
In realtà gli indici non sono contenuti in una semplice tabella ma in strutture più complesse chiamate alberi bilanciati, che sono casi particolari degli alberi sui quali esistono tecniche di ricerca estremamente veloci ed efficienti.
Questo significa che grazie a queste nuove strutture, la ricerca della chiave primaria (che ricordiamo è utile per ricavare l’indice che indica la posizione del record) diventa estremamente veloce.

La figura mostra un esempio di albero binario. La caratteristica che appare chiara è che partendo dalla chiave di valore 32 a sinistra si va verso chiavi di valore minore, a destra verso chiavi di valore maggiore. Questo vale per qualsiasi nodo dell’albero, ovvero che abbia delle altre chiavi sotto di sé. Per semplicità abbiamo omesso l’indice relativo alla chiave, che in realtà viene scoperto non appena si trova la chiave in questione. Quindi gli alberi binari hanno una caratteristica ben precisa che si scorrendoli a partire dalla radice, cioè dal nodo più alto.
Infatti a sinistra di ogni nodo si trovano sempre nodi di valore minore, mentre a destra si trovano sempre nodi di maggior valore.
Considerando per esempio il nodo 45 si osserva che alla sinistra si incontra il nodo 43 ed alla destra il nodo 54.

Si potrebbe, però, notare come la ricerca di un record che si trova più in profondità (ad un livello più basso) rispetto ad un altro nodo impieghi tempi più lunghi in quanto aumentano i nodi da attraversare. Infatti nel caso di figura, cercare il nodo 17 è differente dal cercare il nodo 2, in quanto si attraversa un numero diverso di nodi nei due casi. Per rendere efficiente la ricerca nasce quindi l’esigenza di creare particolari alberi in cui la profondità si mantenga praticamente costante per tutti i nodi. Sono gli alberi bilanciati detti anche B-tree.
La figura mostra la versione bilanciata del precedente albero binario.
Ora, per prelevare il nodo 17 si effettuano tre accessi al file, contro i quattro accessi della versione precedente. Indubbiamente aumenta la complessità delle operazioni di gestione degli alberi, nel caso in cui questi siano bilanciati, ma si ottengono ricerche più veloci.
Con l’aggiunta di nuovi nodi, la struttura dell’albero binario aumenta sempre più di dimensioni.

Per grado di un albero si intende il massimo numero di rami che dipartono da uno qualsiasi dei suoi nodi.
Per altezza di un albero si intende la lunghezza del cammino più lungo dal nodo iniziale fino ad uno qualsiasi dei più bassi.
In generale per un albero binario bilanciato valgono le seguenti regole:

  • la lunghezza del cammino tra il nodo iniziale ed uno qualsiasi dei nodi finali può differire al massimo di 1;
  • ogni nodo ha al massimo due rami che partono da lui;
  • ogni nodo contiene al massimo un elemento.

ESEMPIO
Un archivio contiene dei record. Le chiavi primarie di questi record sono 2, 12, 39, 50, 55, 60, 88. L’albero bilanciato è in figura.
La ricerca è molto semplice: andiamo sinistra se l’elemento è minore di quello su cui siamo fermi, a destra se è maggiore. Se arriviamo in un nodo terminale (fra quelli posti più in basso) senza averlo trovato la chiave che stiamo cercando non esiste.

La sicurezza
la sicurezza è un argomento che verrà trattato in questo paragrafo in maniera da rendere note le scelte progettuali che permettono le realizzazioni di archivi sicuri.
La sicurezza ai giorni nostri è uno degli aspetti più importanti di un database insieme all’efficienza di elaborazione.
Gli archivi di dati possono essere distrutti da eventi naturali (un fenomeno meteorologico), fenomeni elettrici o da manomissioni causate da persone che cercano di venire a conoscenza del contenuto di un archivio.
Un classico esempio di guasto di un archivio consiste nella caduta della testina su disco.
Infatti, le testine sui dischi magnetici sono posizionate ad una distanza ravvicinata facendo però sempre in modo che non vi sia contatto fisico.
Se la testina tocca il disco magnetico, lo rovina e il contenuto dei dati in quella parte di disco non è più consultabile.
Questo è il primo caso che evidenzia la necessità di processi di backup che permettano salvataggi continui dei dati contenuti negli archivi in modo da consentirne un semplice recupero in caso di guasti permanenti.
Questi tipi di danni sono relativamente risolvibili, in quanto bisogna solo ricordarsi di mantenere il più possibile aggiornata una copia di backup dell’archivio.
Si pensi, invece, alla situazione in cui una caduta di tensione interrompa un’operazione su un archivio. Si immagini ancora che questa operazione fosse una scrittura. Questo guasto causa uno stato inconsistente dell’archivio perché ciò che si osserverà successivamente nella lettura di un dato sarà un valore vecchio (in quanto la scrittura non ha avuto successo).
Lo stesso problema si ha nel caso in cui una transazione non venga eseguita in maniera atomica (completamente da inizio a fine) e quindi debba essere ripristinato lo stato dell’archivio.
I metodi per risolvere questi tipi di problemi sono diversi:
• utilizzo del file di log;
• write Ahead Log Protocol;
• copie di dischi.
Infine è possibile che il sistema venga volontariamente violato da qualcuno interessato a conoscerne i contenuti. Senza entrare nei dettagli, i metodi più semplici, ma non sempre più efficaci, consistono nel fare in modo che ogni utente possegga un identificativo ed una password per accedere in maniera univoca all’archivio.

File di Log
Il sistema mantiene un file di Log su disco contenente tutte le informazioni su ogni modifica dei dati. In particolare contiene le informazioni riguardo al valore che questi valori avevano prima e dopo la modifica.
Per semplicità viene solitamente suddiviso in due parti:

una parte attiva che viene lasciata su disco;
una parte meno recente memorizzata su nastro.

Nel caso in cui si verifichi un guasto che interrompe un’operazione di modifica dell’archivio, il sistema legge il file di Log e ripristina lo stato.

Write Ahead Log Protocol
Tutto dovrebbe andare bene finché non intercorre un errore tra il momento in cui il sistema inizia ad effettuare delle modifiche e il momento in cui le scrive nel file di Log. In questo caso le modifiche verrebbero perse.
La soluzione al problema consiste nel fare in modo che il file di Log sia sempre scritto prima che le modifiche abbiano inizio in modo che in caso di errore siano comunque registrate.

Copie di dischi
Si tratta di un metodo che permette il ripristino dello stato senza utilizzare i dischi di backup. Consiste, infatti, nell’avere più copie dei record degli archivi, magari distribuiti in aree geografiche differenti, permettendo quindi di prelevare da un altro disco il contenuto danneggiato del proprio disco.
Naturalmente questo causa una più complessa gestione in quanto ogni modifica dovrà essere effettuata su tutte le copie del record presenti.

{/gspeech} 

Esercizi
1. Si vuole realizzare un archivio contenente i dati riguardanti una squadra di atletica leggera, specializzata nei 100 metri ostacoli. Per ogni tesserato si vuole registrare nome, cognome, anno di nascita, posizione ottenuta nell’ultima gara effettuata e numero di gare vinte dall’inizio dell’anno. Progettare la struttura del record indicando per ogni campo o sottocampo la dimensione massima.
2. Un supermercato possiede un archivio come quello in figura. Indicare la sequenza di accessi che si effettuano per prelevare l’articolo il cui codice è 0007. Supponendo di avere un tempo di accesso alla memoria di massa di durata T, indicare quanto tempo si impiega per la ricerca del record e proporre una soluzione adeguata.

3. Considerando la tabella precedente si supponga che ogni record sia costituito da 4 byte per il codice articolo e da 20 caratteri al massimo per la descrizione e che ogni carattere occupi un byte. Indicare in quale posizione (in termini di byte) si troverà il record di codice 0007 all’interno del file.
4. In base all’archivio di figura si realizzi la tabella degli indici in grado di legare la coppia nome, cognome degli atleti alla posizione occupata nel file. Spiegare inoltre il funzionamento della ricerca per mezzo della tabella degli indici. Nelle tre tabelle di figura, indicare quali sono le chiavi secondarie, le chiavi primarie e, nel caso in cui si renda necessario, le eventuali chiavi composte.

5. Si ha a disposizione un archivio di dati con la tabella di fig. 4. Si supponga di dovere effettuare delle ricerche all’interno di questa tabella utilizzando un accesso calcolato. La funzione di hash è la seguente:

Posizione = Matricola MOD 50

Si evidenzino gli accessi alla memoria nel caso in cui si ricerchi il record il cui campo matricola sia 42, successivamente 92 e successivamente 142. Spiegare dettagliatamente i singoli passi nel caso in cui si utilizzi la scansione lineare.

6. Si devono effettuare delle ricerche nella tabella di figura, rispettivamente con ricerche sequenziali, a blocchi e dicotomiche.
Descrivere i passi necessari per effettuarle sapendo che bisogna ricercare sempre il record di chiave 44. Indicare, tra i vari algoritmi utilizzati, quello che ha effettuato la ricerca più velocemente.

7. Effettuare le seguenti operazioni sull’albero bilanciato di figura.

  • ricercare l’elemento 57;
  • ricercare l’elemento 20;
  • ricercare l’elemento 88;
  • indicando per ogni operazione in dettaglio i criteri seguiti e la lunghezza del cammino attraversato.

8. Indicare in figura, quale immagine rappresenta un albero binario in base alle regole esposte nell’unità.

 Esercizi
1. Che cosa si intende per archivi di dati?
2. In quali contesti si utilizzano gli archivi di dati?
3. Quali sono i principali aspetti che caratterizzano un archivio di dati?
4. Come deve essere realizzato un archivio di dati per essere particolarmente efficiente?
5. Che cosa si intende per record e campi dei record in un archivio di dati?
6. Come bisogna procedere nella scelta della struttura dei record e della loro dimensione?
7. Qual è l’influenza del posizionamento dei record nel supporto fisico sulla velocità di ricerca?
8. Perché nasce l’esigenza di memorizzare i dati relativi agli archivi in memorie di massa?
9. Che cosa si intende per registrazione o accesso sequenziale a una memoria di massa?
10. Che cosa si intende per accesso casuale e quali sono gli svantaggi/vantaggi rispetto all’accesso sequenziale?
11. Qual è l’utilità dell’inserimento di indici per la memorizzazione/ricerca di record nelle memorie?
12. All’intero della tabella di un archivio di dati qual è la differenza tra chiave primaria e chiave secondaria?
13. Quali sono i vantaggi dell’uso dell’accesso calcolato rispetto a quello sequenziale o casuale?
14. Che cosa si intende per funzione di hash e qual è la sua funzione?
15. In che cosa consiste il fenomeno delle collisioni?
16. Quali tecniche conosci per la gestione delle collisioni?
17. Indica i tipi di ricerca che è possibile effettuare su di un archivio.
18. Indica la differenza tra albero binario e albero binario bilanciato (B-tree).
19. Qual è il vantaggio che si ottiene nel suddividere gli alberi in sottoalberi interamente caricabili in memoria (in pagine)?
20. Che cosa si intende per sicurezza di un archivio di dati?
21. Quali metodi conosci per garantirla?

Commento all'articolo