Record, tabelle, relazioni F. Bombi 1 novembre 2001



Scaricare 445 b.
02.01.2018
Dimensione del file445 b.


Record, tabelle, relazioni

  • F. Bombi

  • 1 novembre 2001


Record, tabelle, relazioni

  • Sino ad ora abbiamo studiato strutture di dati, quali array e liste che ci consentono di gestire collezioni di dati dello stesso tipo

  • È frequente la necessità di gestire dati di natura diversa in un unico oggetto. A secondo del contesto in cui ci si muove si parla di:

    • File di Record
    • Tabelle
    • Relazioni
  • L’impiego di array di liste, di array di array o di liste di array non risolve il problema



Record

  • Il concetto di record nasce con riferimento alla registrazione su supporti fisici, quali nastri o dischi magnetici, di file contenenti insiemi di dati

  • La struttura più semplice che si può adottare, detta file piatto, si compone di una sequenze di record di uguale struttura

  • Ogni record è a sua volta composto da campi secondo una struttura predeterminata

  • Ogni campo contiene un‘informazione elementare (un dato numerico, una stringa di caratteri, una data, ecc.) in un formato noto (binario, ASCII)

  • L’organizzazione dei record di un file è descritta in un documento detto tracciato record

  • Per semplicità assumiamo che ciascun campo occupi un numero di byte fisso e noto a priori



Esempio

  • All’anagrafe di un comune vogliamo conservare i dati anagrafici dei cittadini

  • Utilizziamo un file composto da record

  • Per ogni cittadino prevediamo un record composto dai seguenti campi:

    • Cognome stringa 20 caratteri
    • Nome stringa 20 caratteri
    • Codice fiscale stringa 16 caratteri
    • Data di nascita stringa 6 caratteri
    • Comune di nascita intero 4 byte
    • Sesso carattere 1 carattere
    • Stato civile carattere 1 carattere
    • Ecc. ecc.


Tabelle

  • Possiamo organizzare la stessa informazione in una tabella composta da righe e colonne.

  • Utilizziamo una riga per ogni record e una colonna per ogni campo



Relazioni

  • In termini più matematici possiamo pensare ogni record (o riga della tabella) come una ennupla (in inglese n-tuple o semplicemente tuple) di valori ciascuno appartenente ad un differente insieme (gli insiemi dei cognomi possibili, dei codici fiscali, ecc.)

  • Gli n elementi di una ennupla vengono detti attributi

  • L’intero insieme di dati è allora una relazione definita come un sottoinsieme del prodotto cartesiano degli insiemi di tutti i possibili valori di ciascun campo



Esempio

  • Supponiamo di avere due insiemi

      • A = {a, b, c, d}
      • B = {1, 2, 3}
  • Il prodotto cartesiano C = A x B dei due insiemi è l’insieme di tutte le possibili coppie di elementi del primo e del secondo insieme

  • C={(a,1),(a,2),(a,3),(b,1),…,(d,2),(d,3)}

  • L’insieme

  • D = {(a,2),(b,1),(c,1),(c,3)}

  • costituisce una relazione (binaria) su A e B



In prima approssimazione…



Chiavi e attributi

  • Per definizione, in una relazione (essendo un insieme) non ci possono essere due n-uple uguali. Per coerenza assumiamo che in un file (o in una tabella) non ci siano due record (due righe uguali)

  • In questa trattazione molto semplificata immaginiamo in fine che ciascun record sia univocamente individuato dal valore di uno dei campi detto chiave (o chiave primaria)

  • Dato quindi il valore di una chiave possiamo cercare se esiste (o non esiste) un record individuato da quel valore della chiave

  • L’operazione di ricerca fornisce il valore dei restanti attributi, la ricerca corrisponde quindi alla valutazione di una funzione pensando alla chiave come variabile indipendente e ai restanti attributi variabili dipendenti



In Java

  • È facile pensare di utilizzare una classe per rappresentare un record, la classe avrà tanti membri quanti sono i campi del record

  • In prima battuta la classe non richiede metodi e può essere costruita in modo che i membri siano tutti pubblici

  • Tornando per un momento all’esempio dell’anagrafe potremmo usare la classe

      • public class Record
      • { public String cognome;
      • public String nome;
      • public String codice fiscale;
      • ecc., ecc.
      • }
  • Un file potrà essere rappresentato come una lista o un array di record



Un po’ di generalità

  • Nei prossimi esempi, per trattare il problema in modo un po’ più astratto, assumiamo di voler gestire record composti da soli due campi (che chiameremo Coppia):

    • Il primo campo è la chiave che dovrà essere un oggetto che realizza l’interfaccia Comparable
    • Il secondo sarà ancora un oggetto che costituisce l’unico attributo presente
  • Un file (tabella, relazione), sarà rappresentata di un array (quando sappiamo il numero di record presenti) oppure da una Lista (quando vogliamo poter aggiungere e togliere gli elementi a piacimento)

  • È pressoché immediato generalizzare questo schema quando si debbano trattare record con molti campi pensando all’oggetto attributo composto a sua volta da un record oppure sostituendo la classe Coppia con una classe Ennupla con il numero di campi necessari



Ricerca di un record

  • A questo punto disponiamo di quasi tutti gli strumenti necessari per gestire un file di record ciascuno composto da una coppia chiave-attributo in un array o in una lista

  • Sappiamo:

    • Inserire o togliere un elemento
    • Ordinare il file
    • Eliminare i doppioni
  • Vediamo ora come cercare un elemento dato il valore della chiave

  • Pensiamo di organizzare la ricerca mediante un metodo statico che riceva quale parametro l’array o la lista e la chiave da cercare (inserita in un oggetto di tipo Coppia). Tutti gli algoritmi di ricerca hanno la peculiarità di avere due uscite (a stretto rigore non sarebbero strutturati) in quanto la ricerca può terminare con successo o con insuccesso



La classe Coppia



Ricerca in un array

  • Come già detto l’algoritmo base per cercare un elemento in un array pone un sottile problema di strutturazione in quanto richiede due uscite. Non può essere quindi pensato direttamente come composizione di if e while.

  • Occorre ricorrere ad un’istruzione di salto incondizionato oppure ad uno switch

  • Java, per risolvere situazione di questo tipo, mette a nostra disposizione l’istruzione break per uscire da un ciclo prima che sia terminato. In modo analogo possiamo uscire da un ciclo usando l’istruzione return (che termina anche il metodo)

  • Stilisticamente l’uso di switch è in genere sconsigliato da qualche purista



Uso di break o di uno switch



Quanto tempo occorre per trovare un dato fra n?

  • Abbiamo analizzato situazioni di questo tipo in altri casi per cui sappiamo subito dire che dobbiamo fare un numero di cicli pari a:

    • 1 nel caso migliore (l’elemento cercato è il primo)
    • n nel caso peggiore (l’elemento cercato è l’ultimo o non è presente)
    • (n+1)/2 in media (l’elemento cercato è presente e occupa con la stessa probabilità tutti le posizioni possibili)
  • Ad ogni ciclo dobbiamo fare due confronti, uno per verificare se l’elemento è presente e l’altro per verificare se abbiamo esaurito i dati



L’uso di una sentinella

  • È possibile ridurre a metà il numero di confronti utilizzando una sentinella (utile anche in altre circostanze)

  • Supponendo che il vettore v[]abbia almeno una posizione libera, inseriamo il valore da cercare al posto di indice n

  • A questo punto siamo sicuri che l’elemento cercato compaia nel vettore almeno una volta, possiamo interrompere il ciclo di ricerca quando si trova il dato senza controllare se si è esaurito il vettore

  • Al termine del ciclo se l’elemento trovato occupa la posizione n la ricerca è fallita





Possiamo fare meglio?

  • Se non abbiamo altre informazioni non c’è modo di migliorare le cose. Se sappiamo che il vettore è ordinato possiamo utilizzare una strategia ricorsiva di tipo divide et impera che sfrutta il risultato di ogni confronto per ridurre le dimensioni del problema da risolvere



Ricerca per bisezione

  • Vogliamo cerca x nel vettore v[] fra gli elementi di indice compreso fra i e s

  • Se i > s l’elemento cercato non è presente insuccesso! (uno dei casi base)

  • Sia m = (i+s)/2 se v[m] == x successo! (l’altro caso base)

  • (Passo ricorsivo)

  • Se x < v[m] cerchiamo fra i e m-1

  • Se x > v[m] cerchiamo fra m+1 e s

  • Anche se apparentemente ci sono due chiamate ricorsive ad ogni passo ne viene attivata una sola per cui è immediato utilizzare l’eliminazione della ricorsione in coda e realizzare l’algoritmo in forma iterativa





Quanti confronti si fanno?

  • Per semplificare l’analisi supponiamo che

  • n = 2k-1 e quindi k = ln2(n+1)

  • Consideriamo solo il caso peggiore e analizziamo il problema in funzione di k

  • T(1) = 1

  • T(k) = 1 + T(k-1)

  • È immediato dimostrare per induzione che la ricorrenza ha come soluzione

  • T(k) = k

    • e quindi
  • T(n) = ln2(n+1)

  • Il comportamento asintotico è dunque O(log n)



Ricerca in una lista

  • Gli algoritmi di ricerca per scansione con o senza sentinella possono essere facilmente riscritti per la ricerca di un elemento in una lista

  • Con una lista non è invece possibile utilizzare l’algoritmo di bisezione

  • Con una l’uso della sentinella è un po’ brigoso perché è necessario prima inserire l’elemento cercato nella lista e poi toglierlo, non disponendo di metodi di confronto fra iteratori (che per altro sarebbe facile costruire) non è poi immediato verificare se la ricerca termina alla fine della lista





Esempio di utilizzo

  • Costruiamo ora una semplice applicazione che legge da un file (il nome è passato come argomento dalla riga di comando) i dati relativi ad un insieme di studenti, ciascun record è costituito dal numero di matricola e dal nome separati dal carattere ‘:’

  • Si legge poi dall’ingresso standard il nome di uno studente per cercare il corrispondente numero di matricola

  • Notare che i dati vengono ordinati per poter utilizzare l’algoritmo di bisezione





Attenzione

  • Gli oggetti di tipo Coppia sono confrontabili e il confronto avviene considerando solo il campo chiave

  • Per effettuare la ricerca è necessario costruire un oggetto che contiene la chiave cercata (il valore dell’attributo è inessenziale)

  • I metodi di ricerca restituiscono o un riferimento null o un riferimento all’elemento che contiene la chiave cercata






©astratto.info 2017
invia messaggio

    Pagina principale