1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

27
1 Record, tabelle, Record, tabelle, relazioni relazioni F. Bombi 1 novembre 2001

Transcript of 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

Page 1: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

1

Record, tabelle, relazioniRecord, tabelle, relazioni

F. Bombi

1 novembre 2001

Page 2: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

2

Record, tabelle, relazioniRecord, 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

Page 3: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

3

RecordRecord Il concetto di record nasce con riferimento alla registrazione

su supporti fisici, quali nastri o dischi magnetici, di filefile contenenti insiemi di dati

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

Ogni record è a sua volta composto da campicampi 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 recordtracciato record

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

Page 4: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

4

EsempioEsempio 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.

Page 5: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

5

TabelleTabelle

Possiamo organizzare la stessa informazione in una tabellatabella composta da righerighe e colonnecolonne.

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

Cognome Nome CDF Data nasc. Sesso Comune Stato civ.

Page 6: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

6

RelazioniRelazioni In termini più matematici possiamo pensare ogni

record (o riga della tabella) come una ennuplaennupla (in inglese n-tuplen-tuple o semplicemente tupletuple) di valori ciascuno appartenente ad un differente insieme (gli insiemi dei cognomi possibili, dei codici fiscali, ecc.)

Gli n n elementi di una ennupla vengono detti attributiattributi

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

Page 7: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

7

Esempio

Supponiamo di avere due insiemiA = {a, b, c, d}A = {a, b, c, d}B = {1, 2, 3}B = {1, 2, 3}

Il prodotto cartesiano C = A x BC = 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)}C={(a,1),(a,2),(a,3),(b,1),…,(d,2),(d,3)}

L’insieme D = {(a,2),(b,1),(c,1),(c,3)}D = {(a,2),(b,1),(c,1),(c,3)}

costituisce una relazionerelazione (binaria) su AA e BB

Page 8: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

8

In prima approssimazione…In prima approssimazione…

filefile tabellatabella relazionerelazione

recordrecord rigariga tuplatupla

campocampo colonnacolonna attributoattributo

Page 9: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

9

Chiavi e attributiChiavi 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 chiavechiave (o chiave primaria)

Dato quindi il valore di una chiave 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

Page 10: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

10

In JavaIn 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 class Record { public String cognome;{ public String cognome; public String nome;public String nome; public String codice fiscale;public String codice fiscale; ecc., ecc.ecc., ecc.}}

Un file potrà essere rappresentato come una lista o un array di record

Page 11: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

11

Un po’ di generalità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 CoppiaCoppia):– Il primo campo è la chiavechiave che dovrà essere un oggetto che

realizza l’interfaccia ComparableComparable– Il secondo sarà ancora un oggetto che costituisce l’unico attributoattributo

presente Un file (tabella, relazione), sarà rappresentata di un arrayarray (quando sappiamo il numero di record presenti) oppure da una ListaLista (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 attributoattributo composto a sua volta da un recordrecord oppure sostituendo la classe CoppiaCoppia con una classe EnnuplaEnnupla con il numero di campi necessari

Page 12: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

12

Ricerca di un recordRicerca di un record A questo punto disponiamo di quasi tutti gli strumenti

necessari per gestire un filefile 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 CoppiaCoppia). 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 successo o con insuccessoinsuccesso

Page 13: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

13

La classe La classe CoppiaCoppiapublic class Coppia implements Comparablepublic class Coppia implements Comparable{ public Comparable chiave;{ public Comparable chiave; public Object attributo;public Object attributo; public Coppia (Comparable c, Object a) public Coppia (Comparable c, Object a) { chiave = c; attributo = a; }{ chiave = c; attributo = a; } public int compareTo (Object x) public int compareTo (Object x) { return chiave.compareTo(((Coppia)x).chiave); }{ return chiave.compareTo(((Coppia)x).chiave); } public String toString () public String toString () { return chiave.toString() + ":" + attributo.toString();}{ return chiave.toString() + ":" + attributo.toString();}}}

Anche se non è necessario (dato che tutti i campi sono publicpublic) è comodo chela classe realizzi l’inerfaccia ComparableComparable (questo obbliga ad inserire unmetodo compareTo() compareTo() ad accesso pubblico che confronta le chiavi.Il costruttore rende più immediato assegnare i valori ai campi al momentodella costruzione di un nuovo oggetto.Ogni classe deve avere un metodo toString()toString() per poter stampare gliesemplari della classe

Page 14: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

14

Ricerca in un arrayRicerca 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 ifif e whilewhile.

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 breakbreak per uscire da un ciclo prima che sia terminato. In modo analogo possiamo uscire da un ciclo usando l’istruzione return return (che termina anche il metodo)

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

Page 15: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

15

Uso di Uso di breakbreak o di uno switch o di uno switch

int i;int i;for (i = 0; i < n; i++)for (i = 0; i < n; i++) if (x.compareTo(v[i]) == 0)if (x.compareTo(v[i]) == 0) break;break;if (i == n)if (i == n) // non trovato// non trovatoelseelse // trovato// trovato int i;int i;

boolean trovato = false;boolean trovato = false;for (i = 0; !trovato && i < n; i++)for (i = 0; !trovato && i < n; i++) if (x.compareTo(v[i]) == 0)if (x.compareTo(v[i]) == 0) trovato = true;trovato = true;if (trovato)if (trovato) // trovato// trovatoelseelse // non trovato// non trovato

breakbreak

switchswitch

Si vuole cercareSi vuole cercarex fra i primi nx fra i primi nelementi delelementi delvettore v[]vettore v[]

Page 16: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

16

Quanto tempo occorre per Quanto tempo occorre per trovare un dato fra n?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:– 11 nel caso migliore (l’elemento cercato è il primo)– nn nel caso peggiore (l’elemento cercato è l’ultimo o non

è presente)– (n+1)/2(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

Page 17: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

17

L’uso di una L’uso di una sentinellasentinella È possibile ridurre a metà il numero di confronti

utilizzando una sentinellasentinella (utile anche in altre circostanze)

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

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 nn la ricerca è fallita

Page 18: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

18

int i;int i;v[n] = x;v[n] = x;for (i = 0; x.compareTo(v[i]) == 0; i++);for (i = 0; x.compareTo(v[i]) == 0; i++);if (i == n)if (i == n) // non trovato// non trovatoelseelse // trovato// trovato

tempotempo

tagliataglia

Due confrontiDue confronti

SentinellaSentinella

Anche usando la sentinellaAnche usando la sentinellail comportamento asintoticoil comportamento asintoticorimane rimane O(n)O(n)Cambia la costante di proporzionalità che legail tempo effettivo a n n

Page 19: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

19

Possiamo fare meglio?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 divide et impera impera che sfrutta il risultato di ogni confronto per ridurre le dimensioni del problema da risolvere

Page 20: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

20

Ricerca per Ricerca per bisezionebisezioneVogliamo cerca xx nel vettore v[]v[] fra gli elementi di indice

compreso fra ii e ssSe i > si > s l’elemento cercato non è presente insuccesso!

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

base)(Passo ricorsivo)Se x < v[m]x < v[m] cerchiamo fra ii e m-1m-1Se x > v[m]x > v[m] cerchiamo fra m+1m+1 e ss 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

Page 21: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

21

public static Comparable public static Comparable binaria (Comparable x, Comparable[] v, int n)binaria (Comparable x, Comparable[] v, int n) { int inf = 0;{ int inf = 0; int sup = n - 1;int sup = n - 1; int meta;int meta; while (inf <= sup)while (inf <= sup) { meta = (inf + sup)/2;{ meta = (inf + sup)/2; int confronto = x.compareTo(v[meta]);int confronto = x.compareTo(v[meta]); if ( confronto == 0)if ( confronto == 0) return v[meta];return v[meta]; else if (confronto < 0)else if (confronto < 0) sup = meta - 1;sup = meta - 1; elseelse inf = meta + 1;inf = meta + 1; }} return null;return null; }}

Questa realizzazioneQuesta realizzazionedell’algoritmo di ricercadell’algoritmo di ricercaper bisezione o binariaper bisezione o binariamostra come eliminare lamostra come eliminare laricorsione con un ciclo ricorsione con un ciclo while()while() e gestire i e gestire i due casi base con due due casi base con due salti (i due salti (i due returnreturn))

Page 22: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

22

Quanti confronti si fanno?Quanti confronti si fanno? Per semplificare l’analisi supponiamo che

n = 2n = 2kk-1-1 e quindi k = lnk = ln22(n+1)(n+1) Consideriamo solo il caso peggiore e analizziamo il

problema in funzione di kkT(1) = 1T(1) = 1

T(k) = 1 + T(k-1)T(k) = 1 + T(k-1) È immediato dimostrare per induzione che la ricorrenza ha

come soluzioneT(k) = kT(k) = k

e quindi

T(n) = lnT(n) = ln22(n+1)(n+1) Il comportamento asintotico è dunque O(log n)O(log n)

Page 23: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

23

Ricerca in una listaRicerca 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

Page 24: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

24

public static Comparable scansione (Comparable x, Catena l)public static Comparable scansione (Comparable x, Catena l) { for (IteraCatena q = new IteraCatena(l); { for (IteraCatena q = new IteraCatena(l); !q.allaFine(); q.prossimo())!q.allaFine(); q.prossimo()) if (x.compareTo(q.valore()) == 0)if (x.compareTo(q.valore()) == 0) return (Comparable)q.valore();return (Comparable)q.valore(); return null;return null; }}

public static Comparable sentinella (Comparable x, Catena l)public static Comparable sentinella (Comparable x, Catena l) { IteraCatena q = new IteraCatena(l);{ IteraCatena q = new IteraCatena(l); q.vaiAllaFine();q.vaiAllaFine(); IteraCatena p = new IteraCatena(q);IteraCatena p = new IteraCatena(q); q.inserisci(x);q.inserisci(x); q.vaiAllInizio();q.vaiAllInizio(); while (x.compareTo(q.valore()) != 0)while (x.compareTo(q.valore()) != 0) q.prossimo();q.prossimo(); Comparable tmp = (Comparable)q.valore();Comparable tmp = (Comparable)q.valore(); q.prossimo();q.prossimo(); if (q.allaFine())if (q.allaFine()) tmp = null;tmp = null; p.togli();p.togli(); return tmp;return tmp; }}

Con una lista il vantaggioCon una lista il vantaggioderivante dall’uso di unaderivante dall’uso di unasentinella è dubbiosentinella è dubbio

Page 25: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

25

Esempio di utilizzoEsempio 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

Page 26: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

26

public class CercaStudentepublic class CercaStudente{ public static void main (String[] arg) throws IOException{ public static void main (String[] arg) throws IOException { BufferedReader fileDati=new BufferedReader(new FileReader(arg[0]));{ BufferedReader fileDati=new BufferedReader(new FileReader(arg[0])); String str;String str; Coppia[] dati = new Coppia[100];Coppia[] dati = new Coppia[100]; int n = 0;int n = 0; while((str = fileDati.readLine()) != null)while((str = fileDati.readLine()) != null) { StringTokenizer t = new StringTokenizer(str, ":");{ StringTokenizer t = new StringTokenizer(str, ":"); String matricola = t.nextToken();String matricola = t.nextToken(); String nome = t.nextToken();String nome = t.nextToken(); dati[n++] = new Coppia(nome, matricola);dati[n++] = new Coppia(nome, matricola); }} Ordina.mergesort(dati, n);Ordina.mergesort(dati, n); for (int j = 0; j < n; j++) System.out.println(j + ": " + dati[j]);for (int j = 0; j < n; j++) System.out.println(j + ": " + dati[j]); BufferedReader in = BufferedReader in = new BufferedReader(new InputStreamReader(System.in));new BufferedReader(new InputStreamReader(System.in)); str = in.readLine();str = in.readLine(); while (str.length() != 0)while (str.length() != 0) { Coppia x = new Coppia(str, null);{ Coppia x = new Coppia(str, null); System.out.println(Cerca.scansione(x, dati, n));System.out.println(Cerca.scansione(x, dati, n)); System.out.println(Cerca.sentinella(x, dati, n));System.out.println(Cerca.sentinella(x, dati, n)); System.out.println(Cerca.binaria(x, dati, n));System.out.println(Cerca.binaria(x, dati, n)); str = in.readLine();str = in.readLine(); }} }}}}

Page 27: 1 Record, tabelle, relazioni F. Bombi 1 novembre 2001.

27

AttenzioneAttenzione

Gli oggetti di tipo CoppiaCoppia sono confrontabili e il confronto avviene considerando solo il campo chiavechiave

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 nullnull o un riferimento all’elemento che contiene la chiave cercata