Database & Information

Retrieval

GRUPPO 3

Corso di Didactics of Computer Science

6 Maggio 2011

Strutture dati

• Per dato si intende un valore che può essere trasformato da un elaboratore elettronico.

• Una struttura dati è un'entità usata per organizzare un insieme di dati all'interno della memoria del computer o per memorizzarli in una memoria di massa.

Tipi di strutture dati

• Le strutture dati sono strumenti astratti che evitano agli utenti di dover conoscere i dettagli che riguardano la memorizzazione effettiva dei dati e consentono di accedervi come se fossero memorizzati nel formato più appropriato.

• La memoria del computer non è organizzata in pile, code, alberi..., bensì in una sequenza di celle di memoria a cui si può fare riferimento.

I databaseA fine Ottocento, negli Stati Uniti, ci fu un incremento dell’immigrazione e si pose il problema di come organizzare il prossimo censimento.• Herman Hollerith, progettò e costruì macchine di elaborazione in grado di leggere, conteggiare ed ordinare i dati immessi su schede perforate.• La prima banca dati moderna fu quella progettata per il censimento del 1950, usando il primo modello di elaboratore messo in vendita, l'UNIVAC-1 che memorizzava i dati su nastro magnetico.• L'utilizzo delle banche dati crebbe negli anni Sessanta, grazie all'introduzione dei primi dischi magnetici.

Informazione strutturataQuando si considerano insiemi organizzati di dati si parla di basi di dati o database.

Una base di dati è un sistema che converte un insieme esteso di dati in uno strumento astratto consentendo agli utenti di cercare ed estrarre informazioni.

Tipi di database1. Database gerarchico• I file sono correlati come in un albero genealogico. • Esiste un unico punto d'ingresso (radice) ed ogni figlio può avere un solo genitore. • Si tratta di un tipo di database rigido.

Tipi di database2. Database reticolare• E' simile ad un database gerarchico, ma ciascun figlio può avere più genitori.• E’ più flessibile rispetto ad un database gerarchico.

Tipi di database3. Database relazionale• Negli anni Settanta Edgard F. Codd, si pose il problema di come superare i limiti dei modelli gerarchico e reticolare. • Questo nuovo modello si basa sui concetti di tabella e di relazione.• Consente di connettere i dati di più file tramite l'uso di un campo chiave.

Tipi di database4. Database ad oggetti

• Negli anni Ottanta la nascita di nuove esigenze ed applicazioni in ambito scientifico-tecnologico, portano alla necessità di modellare dati complessi legati da relazioni articolate.• Un oggetto può essere costituito da vari tipi di dati (anche di tipo grafico, audio o video) e dalle istruzioni che possono essere eseguite su tali dati. • L'approccio orientato agli oggetti è il più compatibile con la creazione di basi di dati multimediali.

Astrazione dei dati

Si distinguono tre livelli di astrazione:1. Livello fisico: descrive la base di dati

come un insieme di record nella memoria di massa.

2. Livello logico: descrive i collegamenti tra i diversi dati.

3. Livello esterno: presenta i dati come vengono visti dall’utente.

Gestione dei dati

Il DBMS (DataBase Management System) è un sistema di gestione di una base di dati.

Esempio: Access

• Access è un software prodotto da Microsoft che rientra nel pacchetto Office.• E’ un modello di database relazionale.• Fornisce le funzionalità di un DBMS.• Supporta due linguaggi di interrogazione:

QBE (Query By Example)SQL (Structured Query Language)

Questi permettono di interrogare i database al fine di recuperare le informazioni richieste.

Data Mining

• Le origini del data mining sono da ricondurre all'esigenza di eseguire analisi statistiche su insiemi di dati vasti ed eterogenei. • Il data mining consiste in una serie di tecniche volte a scoprire schemi ricorrenti nelle basi di dati. In particolare si cercano schemi fino a quel momento ignoti invece di chiedere semplicemente il recupero dei dati memorizzati.

Motori di ricerca

Si basano su database ospitati su potenti computer, grazie ai quali si possono reperire informazioni utilizzando una o più parole-chiave.

• Il motore di ricerca manda sul Web un programma chiamato spider che invia i documenti trovati al programma di indicizzazione. Esso provvede a estrapolarne le parole, che vengono poi memorizzate in un grande database insieme agli indirizzi dei documenti stessi.• Quando si digita la parola chiave, il motore di ricerca individua tutti i documenti indicizzati che contengono quel termine, e ne elenca i titoli e gli indirizzi, accompagnati da una breve descrizione dei contenuti.

Information Retrieval

• Il termine IR fu coniato nel 1952 da Calvin Mooers che formulò le “legge di Mooers”:

“Un sistema di reperimento delle informazioni tenderà a non essere

usato quando trovare le informazioni è più noioso e doloroso che non

trovarle.”• L’Information Retrieval è la ricerca di informazione di natura non strutturata in un insieme di documenti che soddisfa a un bisogno informativo.

Information retrieval intelligente• Nelle query rendere sensibile il sistema al significato delle parole, es: imposta/tassa, imposta/finestra.• Considerare l’ordinamento delle parole nell’interrogazione.• Ricerca booleana.Un documento è rilevante quando• Risponde precisamente alle esigenze dell’utente.• Suggerisce una fonte di informazione: nuove informazioni possono portare a nuove idee e direzioni di ricerca.• Richiama alla memoria dell’utente altre conoscenze.

Secondo Shannon il contenuto informativo di un messaggio è rappresentato dalla sua probabilità di presentarsi in un insieme di messaggi possibili: maggiore è la probabilità di realizzarsi minore è il contenuto informativo. • RECALL: percentuale di documenti rilevanti recuperati sul totale dei documenti rilevanti presenti nell’insieme.• PRECISIONE: percentuale dei documenti rilevanti sul totale dei documenti recuperati.• SILENZIO: percentuale di documenti rilevanti non recuperati sul totale dei documenti rilevanti presenti nell’insieme.• RUMORE: percentuale dei documenti non rilevanti sul totale dei documenti recuperati.