Laboratorio di informatica III: Basi di dati
20 Marzo 1998

La Base di Dati (BD) dovrebbe raccogliere e mantenere informazioni riguardanti la topografia e i trasporti pubblici di una città. Tali informazioni saranno usate dall'applicazione che gestisce la BD per effettuare alcune significative elaborazioni.

1 DESCRIZIONE DEI DATI

1.1 Informazioni topografiche

Si assume che sia disponibile una pianta della città molto precisa e dettagliata. In particolare, si suppone che tale pianta sia suddivisa, tramite una griglia regolare, in regioni quadrate dette settori. Ogni punto all'interno dell'area della città che si vuole rappresentare appartiene ad uno di questi settori. Tali settori verranno numerati o identificati nel modo che sembrerà più conveniente (relativamente all'uso che si farà nella BD di tali settori). Ogni coppia composta da una via/piazza e da un numero civico (di tale via/piazza) verrà chiamata sito. Per ogni sito che ha interesse rappresentare si manterrà il settore a cui il sito appartiene. Inoltre, se due settori sono adiacenti (cioè se condividono un lato o uno spigolo) e vi è una via/piazza che li collega, allora tale informazione deve essere mantenuta nella BD (ad esempio i settori S e T sono collegati da via Salaria). Si suppone che i settori siano così piccoli che due di essi possano essere collegati da al più una sola via/piazza.

1.2 Dati relativi ai trasporti pubblici

La BD raccoglierà i dati relativi alle linee autobus, tranviarie e metropolitane.

1.2.1 Linee autobus e tranviarie

Per ogni linea ha interesse mantenere le seguenti informazioni: numero della linea, se è una linea autobus o tranviaria, i siti dei due capolinea, se è una linea diurna o notturna, orari della prima e ultima partenza dai capolinea nei giorni feriali e festivi,   il tempo medio tra due passaggi successivi nei feriali e nei festivi, se la linea è in servizio tutti i giorni, solo i feriali o solo i festivi. Inoltre, si vogliono mantenere informazioni molto dettagliate sui percorsi. Per ogni percorso (solitamente, ci sono due percorsi, a volte leggermente differenti, tra i due capolinea) si registrano le seguenti informazioni: per ogni fermata il numero d'ordine (la prima, la seconda, ecc.dopo il capolinea), il sito più vicino e il settore a cui appartiene. Infine, ha interesse mantenere anche dati relativi alle vetture in servizio sulla linea: il numero totale di vetture adibite alla linea, per ogni vettura il numero (che la identifica), il numero dei posti in piedi, seduti e per carrozzelle, il modello (una sigla alfanumerica di al più 20 caratteri).

1.2.2 Linee metropolitane

Per ogni linea metropolitana: sigla della linea, i due capolinea, il tempo medio tra due passaggi successivi nei feriali e nei festivi. Inoltre, la sequenza delle fermate e per ognuna il sito più vicino e il settore a cui appartiene.

2 DESCRIZIONE DELLE OPERAZIONI

Tutte le operazioni che manipolano i dati devono rispettare i vincoli di integrità. Ad esempio, non deve essere possibile inserire il settore di appartenenza di un sito se il settore non esiste, oppure specificare il sito di una fermata se tale sito non è già presente nella DB.Nel caso di cancellazioni o modifica di un dato occorre verificare che tale dato non sia usato in altri contesti nella BD. Ad esempio, se le informazioni relative ad un sito vengono cancellate a tale sito non si può far riferimento.

Inserimento: Deve essere possibile inserire uno qualsiasi dei dati precedentemente menzionati.

Modifica: Deve essere possibile modificare uno qualsiasi dei dati nella BD, purché non si violino i vincoli di integrità.

Cancellazione: Deve essere possibile cancellare uno qualsiasi dei dati nella BD, purché non si violino i vincoli di integrità. Se la cancellazione di un dato viola qualche vincolo di integrità referenziale si dovrà decidere se proibire la cancellazione oppure permetterla e quindi cancellare in cascata tutti i dati che fanno riferimento al dato cancellato.

Inserimento da file: L'applicazione che gestisce la BD deve essere in grado di leggere tre tipi di file (di tipo testo) ed eseguire automaticamente i relativi inserimenti. In tutti e tre i tipi di file le informazioni sono contenute in linee (terminate con un return) e ogni linea è suddivisa in campi separati dal carattere ";":

Il primo tipo di file contiene informazioni topografiche relative ai siti ed ha il seguente contenuto: ogni linea del file contiene 4 campi, il primo contiene il nome di una via/piazza (ad es. via salaria oppure piazza dei cinquecento), il secondo un numero civico di tale via/piazza, il terzo e il quarto le coordinate di un settore (si suppone di aver fissato, in modo arbitrario, un sistema di riferimento per i settori in cui uno dei settori di spigolo della griglia è visto come se fosse l'angolo in basso a sinistra della griglia avente coordinate (0,0) e ogni altro settore avrà coordinate (h,v) dove h è la distanza orizzontale dal settore (0,0) e v quella verticale). Quindi, questo tipo di file serve per inserire nuovi siti specificando i relativi settori di appartenenza.

Il secondo tipo di file riguarda il collegamento tra settori ed ha il contenuto seguente: ogni linea è suddivisa in 5 campi, il primo e il secondo contengono le coordinate di un settore, il terzo e il quarto le coordinate di un altro settore adiacente al primo e il quinto il nome di una via/piazza che collega i due settori.

Il terzo tipo di file riguarda i percorsi delle linee di trasporto ed ha il seguente contenuto: ogni linea del file è suddivisa in 4 campi, il primo contiene il numero/sigla di una linea di trasporto, il secondo il numero d'ordine di una fermata (il numero d'ordine 0 rappresenta il capolinea di partenza), il terzo e il quarto il sito più vicino alla fermata.

Percorsi: Data una linea di trasporto si vuole ottenere il percorso (o i due percorsi) come sequenza ordinata dei siti delle fermate.

Incrocio: Dati due percorsi (ognuno dei quali specificato tramite il numero/sigla di una linea e il capolinea di partenza) si vuole sapere se si incrociano, ovvero se c'è una fermata del primo percorso e una dell'altro che si trovano nello stesso settore o in settori adiacenti.

Collegamento: Dati due percorsi si vuole determinare se sono collegati. Due percorsi sono collegati se o si incrociano oppure vi è un altro percorso che è collegato ad entrambi.

Distanza tra siti: Dati due siti si vuole determinare la loro distanza. Per distanza si intende il numero minimo di settori che è necessario attraversare per andare da un sito all'altro. Più precisamente, la distanza di due siti equivale alla distanza dei settori di appartenenza. Quest'ultima distanza è definita come segue. Si consideri il grafo G non orientato i cui nodi sono i settori e vi è un arco tra due nodi se e solo se i settori corrispondenti sono adiacenti e c'è una via/piazza che li collega. La distanza tra due settori è definita come la distanza tra i due nodi corrispondenti nel grafo G (la lunghezza del più corto cammino tra i due nodi). Si osservi che la distanza può anche essere infinita.

Percorso migliore: Dato un sito A e un sito B si vuole determinare il percorso migliore che va da A a B usando le linee di trasporto. Più precisamente, si vuole trovare, se esiste, il percorso da A a B che minimizza il numero di linee di trasporto diverse utilizzate (ad es. il percorso ideale sarebbe quello che usa una sola linea). Per dare una definizione precisa di ciò dobbiamo introdurre un grafo T orientato con archi multipli etichettati. I nodi di T sono i settori, vi è un arco orientato tra il nodo s e il nodo t se c'è un percorso p di una linea di trasporto che ha una fermata nel settore che corrisponde ad s e la fermata successiva nel settore corrispondente a t, in questo caso l'arco è etichettato con p. Il percorso migliore tra A e B è il cammino orientato tra i nodi corrispondenti ad A e B nel grafo T che usa il minor numero di etichette distinte. Si osservi che potrebbe anche non esserci alcun cammino.

E' possibile scaricare il software (4,254 Mb), la relazione in formato Word '97 (344 Kb) e sia i files di prova utilizzati da noi (7 Kb, già caricati nel database fornito con il software) che quelli utilizzati dal professore durante l'esame (34 Kb):

Software	Relazione	Files di prova del Prof.	Nostri files di prova

Il mio ringraziamento va ai colleghi Giovanni Buonomo, Massimo Delungo e Laura Orso con i quali ho collaborato per la realizzazione di questo software.

Indietro