DBMS: il modello gerarchico dei dati
Questo mese parleremo dei sistemi gerarchici di gestione basi di dati. Dopo aver visto nel numero scorso il modello semantico dei dati, tuttora oggetto di studio e ricerca in tutto il mondo, faremo di fatto un passo indietro. Fra i Data Base, i sistemi gerarchici sono stati i primi ad apparire sul mercato nel "lontano 1969" ad opera della onnipresente IBM. 15 anni di vita, un'eternita' nel mondo dell'informatica.
I sistemi gerarchici
Soffermeremo maggiormente la nostra attenzione sulle differenze col modello dei dati visto lo scorso mese, mostrando come sia possibile adattare uno schema semantico a uno schema gerarchico.
La struttura dei dati memorizzabili in una base di tipo gerarchico e' ad albero, per intenderci pensate un attimo ad un albero genealogico. Avremo una radice, alcuni nodi e i relativi archi tra questi, per descrivere delle associazioni.
Nel caso dell'albero genealogico, la radice sara' il capostipite, ai nodi saranno presenti i discendenti, gli archi rappresenteranno l'associazione padre-figlio. In fig.1 un esempio di albero genealogico che per ragioni piu' o meno storiche dovrebbe essere abbastanza importante.
La struttura di una base di dati gerarchica e' anch'essa ad albero: ogni nodo sara' un insieme di dati, in relazione di tipo gerarchico con altri insiemi della base.
Una base di questo tipo e', per definizione, un insieme di esemplari gerarchici. Un esemplare gerarchico e' un albero con radice un elemento dell'insieme radice e come nodi discendenti tutti gli elementi (dei nodi seguenti) in relazione diretta o indiretta con l'elemento della radice.
Un albero genealogico come quello di fig.1 e' un esemplare gerarchico della base mostrata in figura 2, dove il primo nodo e' l'insieme di tutti i bisnonni, il secondo l'insieme di tutti i nonni, e cosi' via.
Adamo e' la radice ed e' un elemento di Bisnonni; Caino, Abele e Set (sempre per definizione) sono la famiglia di Adamo nell'insieme Nonni. Enoch e Enos sono elementi di Padri e rispettivamente appartengono alla famiglia di Caino e di Set in Padri. A loro volta Irad e Kenan, appartenenti alle famiglie di Enoch e Enos in Figli, sono elementi dell'insieme Figli. Sembra un discorso un po' contorto, ma e' esattamente come nella ralta', come si "manipolano" le discendenze.
Si e' usato questo tema in quanto maggiormente adeguato ad essere rappresentato con strutture ad albero. Di fatto pero' le basi di dati gerarchiche servono per manipolare qualsiasi insieme di dati fra loro correlati.
Assumeremo che un insieme sia precedente ad un altro se lo precede nell'ordinamento gerarchico; discorso analogo per insiemi seguenti. In fig.2 l'insieme dei Nonni e' il precedente dell'insieme dei Padri e il seguente dell'insieme dei Bisnonni. Quest'ultimo e' precedente a tutti gli insiemi: e' detto insieme radice. Analogamente l'insieme Figli e' seguente a tutti gli altri: e' detto insieme terminale.
Esistono vincoli propri del tipo di organizzazione, che non possono essere violati.
le associazioni tra i dati hanno tutti diretta multipla e inversa univoca
l'inversa e' sempre totale
diretta multipla vuol dire che ogni elemento in un insieme puo' essere associato con piu' elementi dell'insieme seguente. Inversa univoca vuol dire che ogni elemento di ogni insieme diverso dall'insieme radice e' in associazione con un unico elemento dell'insieme precedente (deve appartenere a qualche famiglia). Totale vuol dire che questo elemento esiste sempre.
Sempre in merito alla genealogia, e' facile verificare che ogni elemento di ogni insieme puo' avere uno o piu' figli (elementi nell'insieme seguente) e deve avere un padre (elemento nell'insieme precedente). Eccezion fatta per la radice e per l'ultimo insieme: assumiamo che al momento dell'istallazione della base di dati nulla si sappia in merito ai padri dei bisnonni e ai figli dei figli.
In figura 3 e' mostrato un caso piu' generale: l'organizzazione di una universita'. Come si puo' notare, ogni insieme non terminale e' in relazione con due insiemi seguenti.
Nell'insieme radice abbiamo le varie facolta' (Medicina, Ingengneria, Farmacia, Scienze ecc.). Ogni facolta' ha uno o piu' corsi di laurea e una o piu' biblioteche. A loro volta ogni Corso di Laurea ha dei docenti e degli studenti; ogni biblioteca ha un certo numero di Libri e del personale addetto.
Lo studente Tizio, ad esempio, potrebbe essere iscritto al Corso di Laurea in Matematica, facolta' di Scienze. Tizio sara' un elemento di Studenti, appartenente alla famiglia di Scienze Matematiche in Studenti. Scienze Matematiche sara' un elemento dell'insieme Corsi di Laurea, facente parte della famiglia di Scienze; quest'ultima e' un elemento di Facolta'.
Gli operatori
Vedremo ora come e' possibile costruire una base di dati gerarchica e come si opera su essa per prelevare o inserire elementi. Nella defnizione di ogni insieme, come gia' visto per le classi del modello semantico dei dati, si dovranno elencare gli attributi di ogni ennupla: es. nome, cognome, indirizzo ecc.
Bisognera', inoltre, dichiarare quali sono gli insiemi (nodi seguenti) in relazione con l'insieme che si sta definendo. Nessun riferimento ai nodi precedenti: il sistema e' in grado di riconoscerli automaticamente.
Prima di parlare di inserimento e ricerca, chiariremo un punto molto importane: l'ordinamento di un albero. Un esemplare gerarchico, come visto, e' in generale una struttura ad albero. Anche in strutture di questo tipo, e' possibile definire una relazione di ordinamento: un meccanismo per sapere se un elemento viene prima o dopo di un altro. Basta mettersi daccordo una volta per tutte. Nei sistemi gerarchici, il tipo di ordinamento adottato per gli elementi di un albero e' quello anticipato: il nodo prima della sua famiglia, ricorsivamente. Ordiniamo l'esemplare gerarchico di fig.1: il primo elemento e' Adamo, poi viene la sua famiglia. Questa e' composta da Caino, Abele e Set. Si comincia da Caino e si passa alla sua famiglia: Enoch. A sua volta la sua famiglia e' Irad. Abbiamo finito con Caino, si sale su e il successore e' Abele: non ha famiglia, si passa a Set che ha come famiglia Enos che ha come famiglia Kenan.
La visita dell'albero e' completa: ricapitolando, l'ordinamento sequenziale gerarchico in quest'albero e': Adamo, Caino, Enoch, Irad, Abele, Set, Enos, Kenan.
La semantica degli operatori dei sistemi gerarchici si basa, per l'appunto, sull'ordinamento degli esemplari. Per l'esattezza gli operatori hanno una semantica espressa in termini di un elemento detto di riferimento corrente.
L'elemento corrente e' sempre l'ultimo elemento inserito o l'ultimo elemento ripescato nella base di dati. A partire da un elemento corrente e' possibile richiedere il successivo (nell'ordinamento), specificando l'insieme in cui effettuare la ricerca e eventualmente una condizione.
La prima operazione da compiere e' l'inizializzazione dell'elemento corrente. Supponiamo di avere lo schema di figura 2, con inserito l'esemplare gerarchico mostrato in fig.1.
Inizializiamo come elemento di riferimento Adamo. Scriveremo qualcosa del tipo:
get Bisnonni with Nome="Adamo"
Bisnonni e' l'insieme in cui effettuare la ricerca; Nome="Adamo" la condizione da verificare. Per muoverci sull'esemplare esiste l'operatore next, seguito da insieme e, facoltivamente, condizione. Esempio:
next Nonni
restituisce Caino (e' il successore di Adamo, nell'insieme dei nonni, secondo l'ordinamento anticipato visto sopra). Caino diventa il nuovo elemento corrente. Possiamo spostarci specificando una condizione:
next Nonni with Nome="Set"
l'elemento di riferimento diventa ora Set: e' lui il prossimo in Nonni, secondo l'ordinamento, con Nome="Set".
Facciamo un altro esperimento: inizializziamo nuovamente l'elemento di riferimento corrente, nel seguente modo:
get Figli
ci posizioniamo su Irad. Con:
next Figli
otteniamo Kenan. Irad, nell'esemplare gerarchico e' il primo nell'insieme figli che si incontra. Il suo successore, nello stesso insieme e' Kenan. Fin qui tutto regolare. Esiste un altro operatore, nextd, che fa lo stesso lavoro, senza pero' allontanarsi dalla famiglia dell'elemento di riferimento. Se dopo esserci posizionati su Irad eseguiamo un:
nextd Figli
il sistema generera' errore non esistendo altri elementi in Figli, della stessa famiglia di Irad (=altri elementi figli di Enoch).
Per inserire un elemento nella base di dati esiste l'operatore make. La sua sintassi e':
make Insieme Elemento
Elemento e' l'elemento da inserire; Insieme e' l'insieme in cui vogliamo inserirlo. L'operatore make costruisce un elemento in Insieme e lo pone come successivo dell'elemento corrente, nell'ordinamento sequenziale gerarchico. L'elemento inserito diventa il nuovo riferimento corrente. Facciamo qualche esempio. E' data la base di dati di figura 3. Immaginiamo che siano gia' stati inseriti alcuni dati, tra cui l'esemplare gerarchico di fig. 4a : facolta' di Scienze con i due figli (o la famiglia) in CorsiDiLaurea, Matematica e Fisica.
Vogliamo inserire lo studente Tizio, appartenente alla famiglia del corso di laurea in Matematica, in Studenti. Come sempre, la prima operazione da compiere e' inizializzare l'elemento di riferimento corrente. Dovendo modificare i figli di Matematica eseguiremo:
getfirst CorsiDiLaurea with Nome="Matematica"
in parole cerchiamo nell'insieme CorsiDiLaurea l'elemento (in generale il primo elemento) che ha per nome "Matematica". Con:
make Studenti (Tizio)
avremo la situzione di figura 4b. Come promesso, Tizio e' posto dopo Matematica, nell'ordinamento sequenziale gerarchico. Tizio diventa il nuovo riferimento corrente. Supponiamo a questo punto di voler inserire il corso di laurea in Informatica (il nome vero e' Scienze dell'Informazione, ndr). Non c'e' bisogno di spostare l'elemento corrente, dato che a noi va bene che (Informatica) sia posto come successore (in CorsiDiLaurea) di Tizio. Bastera' un:
make CorsiDiLaurea (Informatica)
per avere la situazione di figura 4c
Da schema semantico a schema gerarchico
I meccanismi di astrazione del modello semantico dei dati visti nel numero scorso, permettono di modellare molto facilmente i vari aspetti della conoscenza, prima dell'istallazione di una base di dati. Col modello gerarchico, piu' precisamente a causa dei suoi vincoli impliciti, modellare determinate situazioni diventa piu' difficile, a meno che non si ricorra a particolari trucchetti, discussi in seguito.
Un esempio classico e' mostrato in figura 5a. Si vuole rappresentare l'associazione multipla Esami-Studenti. Multipla vuol dire che ogni Studente e' in relazione con piu' esami (tutti quelli che ha sostenuto) e ogni esame di una particolare facolta' e' stato (ovviamente) superato da piu' studenti.
Col modello gerarchico, tale situazione non e' direttamente realizzabile, essendo l'inversa di ogni associazione unica. In parole povere, uno studente puo' puntare piu' esami (associazione diretta multipla) ma ogni esame (associazione inversa) puo' puntare un solo studente (unica). Come si puo' notare non torna affatto. Finche' si parla di genitori e figli tutto ok (un padre ha piu' figli, ma ogni figlio ha un solo padre), allontanandoci un pochino da schemi per natura gerarchici, il modello dei dati discusso questo mese, mostra subito i suoi limiti, a causa anche della sua considerevole eta'.
In fig. 5b e' mostrata una delle possibili soluzioni: si puo' simulare l'associazione multipla solo a costo di pagare una non indifferente ridondanza (duplicazione di alcuni dati). Si costruiscono due alberi gerarchici, formati da due insiemi l'uno. Il primo albero gerarchico e' formato dall'insieme Studenti e da un particolare insieme di servizio che contiene codici di esami (un numero che l'identifica univocamente). Ogni studente che ha sostenuto esami, ha nell'insieme Codici Esami una sua propria famiglia: i codici degli esami da lui superati.
Nel secondo albero gerarchico sono presenti altri due insiemi, uno Esami, l'altro di servizio, contiene matricole di studenti. Stesso meccanismo: ogni esame di Esami ha una sua famiglia in Matricole Studenti, rappresentante le matricole di tutti gli studenti che hanno superato l'esame in considerazione.
L'associazione multipla, a questo punto funziona cosi': partendo da Studenti, possiamo conoscere la famiglia in Codici Esami di un particolare studente. Per ogni codice pescato accediamo all'insieme Esami, per conoscere effettivamente gli esami sostenuti. Viceversa, per sapere da quali studenti e' stato sostenuto un esame, si accede a Esami, si ci sposta in Matricole Studenti e prese le varie matricole (appartenenti alla famiglia dell'esame in considerazione) si accede in Studenti per conoscere gli altri attributi (nome, cognome, eta' ecc.).
In fig. 6a e' mostrato un altro caso non esprimibile direttamente col modello dei dati gerararchico. C'e' una classe, Libri, puntata da due altre classi: in termini piu' specifici, si dice codominio di due associazioni. La classe Utenti conterra' gli utenti che accedeno alla blblioteca per prendere in prestito libri; la classe Reparti contiene i vari reparti (suddivisi per materia) della biblioteca. Un libro si trova in un solo reparto e puo' (ovviamente) essere in prestito a un solo utente. Viceversa, in ogni reparto ci sono piu' libri e ogni utente puo' averne in prestito piu' d'uno.
Anche questa situazione non e' gerarchica, in fig. 6b e' mostrata una possibile soluzione.
Come prima, due alberi gerarchici. Il primo non fa altro che realizzare la prima delle due associazioni: Reparti-Libri. Il secondo albero, col solito trucchetto dell'insieme di servizio, completa l'associazione. Codici Libri contiene per l'appunto codici di libri, ognuno identifica univocamente un libro della biblioteca. Se si vuol conoscere quali libri ha in prestito un particolare utente, si accede a Utenti, si scende in Codici Libri. Conoscendo la famiglia in Codici Libri dell'utente in considerazione, grazie ai codici prelevati, si prelevano dall'insieme "Libri", Autore, Titolo e posizione dei materiali ricercati.
