UNIVERSITA’ DEGLI STUDI DI MILANO BICOCCA
FACOLTA’ DI SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di Laurea in Informatica
Analisi di Metriche e Algoritmi
per la Qualità dei Dati.
Progettazione e Realizzazione di
un Framework per
l’Assessment della Qualità.
Supervisori:
Chiar.mo Prof. Carlo BATINI
Dott. Daniele BARONE
Relazione della prova finale di:
Carmine Carella
Matricola: 055465
Anno Accademico 2005/2006
1
Overview









La Qualità dei Dati e la sua Importanza
Aree di Ricerca nell’Ambito della Qualità dei Dati
Dimensioni dei Valori dei Dati
Data Quality Framework
Caso di Studio
GUI e Funzioni
Accuratezza Sintattica
Metadati
Appendice
2
La Qualità dei Dati e la sua Importanza
 I dati sono elementi chiave nei processi aziendali
 Decisionali: guidano le decisioni di planning
 Operazionali: sono utilizzati nelle decisioni a livello operativo
 La scarsa qualità dei dati:
 Aumenta con il tempo
 È pervasiva (si diffonde)
 È costosa (mancati ricavi, extra costi)
 Nel processo di creazione e utilizzo dei dati si rendono
necessarie attività appositamente dedicate alla gestione
della qualità:
 Valutazione (assessment)
 Miglioramento (improvement)
3
Aree di Ricerca nell’Ambito della Qualità dei Dati
 Dimensioni: le dimensioni sono
proprietà che caratterizzano uno
specifico aspetto della qualità.
Possono essere associate a livello:
 dello schema
 della rappresentazione dei dati
 dei valori dei dati
 Metriche: associate alle dimensioni di
 Tecniche: algoritmi, euristiche,
qualità ne misurano il livello
conoscenze per lo specifico problema
 qualitative o quantitative
di DQ
 su diversi tipi di dati (strutturati,
 Le tecniche necessitano del
semistrutturati e non strutturati)
supporto di tools: procedure
automatizzate
 per i dati strutturati ai diversi
livelli di granularità
 Un insieme di tools prende il
nome di framework
4
Aree di Ricerca nell’Ambito della Qualità dei Dati
 Dimensioni: le dimensioni sono
proprietà che caratterizzano uno
specifico aspetto della qualità.
Possono essere associate a livello:
 dello schema
 della rappresentazione dei dati
 dei valori
dei dati
 Metriche: associate alle dimensioni di
 Tecniche: algoritmi, euristiche,
qualità ne misurano il livello
conoscenze per lo specifico problema
di DQ
 qualitative o quantitative
 su diversi tipi di dati
(strutturati, semistrutturati e
non strutturati)
 per i dati strutturati ai diversi
livelli di granularità
 Le tecniche necessitano del
supporto di tools: procedure
automatizzate
 Un insieme di tools prende il
nome di framework
5
Dimensioni dei Valori dei Dati
 Accuratezza: vicinanza tra un valore v e un valore v’ considerato la
corretta rappresentazione del mondo reale che v vuole rappresentare.
Si distingue in accuratezza semantica e accuratezza sintattica.
 Accuratezza Sintattica: vicinanza di un valore v agli elementi
del corrispondente dominio di definizione D.
Descritta
durante il
caso di
studio
 Completezza: il grado con il quale la relazione rappresenta la
corrispondente parte del mondo reale. Definita in base a:
 Modello con valori nulli (significato valore nullo: generale, di
valore mancante).
 Assunzione CWA (closed world assumption): i valori presenti in
una tabella relazionale e nessun altro valore rappresentano i
fatti veri del mondo reale.
Presentate
nell’
appendice
 Currency: quanto tempestivamente i dati sono aggiornati.
(accuratezza temporale).
 Consistenza: rileva le violazioni di regole semantiche definite su un
insieme di dati. Vincoli di integrità, istanza regole semantiche, nel
modello relazionale.
6
Data Quality Framework
Descrizione
Attività
Assessment delle principali dimensioni di qualità dei dati e Localizzazione e
Correzione degli errori
Dimensioni

Accuratezza Sintattica
 Completezza
 Currency

Consistenza
Metriche
Algoritmi quantitativi
Tipi di Dati
Strutturati (Modello Relazionale)
Livelli di Granularità
Database, Relazione,Tupla, Attributo, Singolo valore
Funzioni Principali
Assessment
Misurazione delle quattro dimensioni
Gestione Metadati
“Metadati misurazione” utilizzati dagli algoritmi durante l’esecuzione e “Metadati
dimensione” danno informazioni relative alle valutazioni effettuate
Gestione Report Parziale
Report parziale con le misurazioni effettuate durante l’utilizzo del framework
Gestione Reports Completi
Report completi di misurazione per ogni dimensione
Strumenti Utilizzati
Java con IDE Eclipse
Realizzazione
MySQL
DBMS Relazionale d’appoggio
XML
Organizzazione e Strutturazione logica dei metadati
Widget toolkit SWT
Creazione GUI
7
Caso di Studio

Utilizzato per testare il framework
Il test è stato effettuato per

Verificare la correttezza dei risultati

Funzionamento degli algoritmi
Database MySQL


Recuperato dal sito del progetto Eclipse-BIRT relativo ad una compagnia
ClassicModels Inc. per la vendita di modelli in scala di automobili, treni,
navi, autobus, aerei, ect.
Contiene 8 relazioni, 60 attributi, 3864 tuple

Relazioni contenenti tipici dati di business: offices, employees, customers,
orders, order details, payments, products, product lines

Prima di eseguire il test con tale database, i dati sono stati “sporcati” per
poi poter rilevare provlemi di qualità
8
Framework : GUI e Funzioni
Connessione e
Disconnesione
database
Funzioni per
l’assessment
Gestione
Reports
Completi
Struttura
Database
connesso
Gestione
Metadati
Misurazione
Visualizzazione
Report Parziale e
Metadati Misurazione
Area
Risultati
Visualizzazione
grafica risultati
Informazioni sul
percorso
metadati
misurazione
Informazioni sul
database connesso
Informazioni sulla
singola relazione
Informazioni sul
percorso
metadati
dimensione
9
Accuratezza Sintattica
 Lookup table: informazioni che vengono consultate durante la misurazione
dell’accuratezza
 Funzioni di distanza: Jaro
 Simple Ratio:
 risultati desiderati / numero totale risultati
 1 – ( risultati non desiderati / numero totale risultati)
Accuratezza Sintattica Attributo: due metriche
 Metrica basata sulla presenza della lookup table
 Lookup table
 Jaro
 Simple Ratio
 Metrica basata sulla frequenza dei valori dell’attributo
 Jaro
 Soundex
Accuratezza Sintattica Tupla e Relazione: una metrica
 Metrica basata sulla tecnica del Record Linkage
 Lookup table
10
Accuratezza Sintattica Attributo
Prima metrica basata sulla presenza della lookup table
 Lookup table: rappresenta il dominio di definizione dell’attributo
Algoritmo
Accuratezza sintattica del singolo valore dell’attributo
1. Per ogni valore v dell’attributo, controlla che v sia uno dei valori nel dominio
2. Determinazione insieme valori accurati e dell’ insieme non accurati
3. Per ogni valore dell’insieme non accurati, si effettua il confronto con ogni
valore del dominio tramite Jaro, per trovare il valore massimo di similarità e il
valore più vicino
Accuratezza sintattica dell’attributo
4. Determinazione accuratezza attributo tramite simple ratio
11
Inserimento lookup table Accuratezza Sintattica Attributo city della relazione offices
Relazione
d’appartenenza
dell’attributo
Nome attributo a
cui associare la
lookup table
Coordinate
MySQL della
lookup table
12
Accuratezza Sintattica Attributo city della relazione offices con metrica lookup table
Valore accuratezza
dell’attributo
Correzione
suggerita
Accuratezza
singolo valore
13
Accuratezza Sintattica Tuple e Relazioni
Metrica ispirata alla metodologia ISTAT per la qualità dei dati toponomastici e a
tecniche di Record Linkage
Lookup table: relazione contenete le istanze corrette della relazione da valutare,
rappresentanti la parte del mondo reale che si vuole modellare
In base all’ algoritmo di record matching utilizzato (confronto tra sottostringhe), la
relazione da valutare e la lookup table dovrebbero avere la stessa struttura: ugual
numero di attributi e stesso ordine
Fase di configurazione della misurazione: in cui adattare le strutture e scegliere tutti
o un sottoinsieme degli attributi e in quale ordine. (normalizzazione formati)
Fase di misurazione: algoritmo di record matching che restituisce per ogni tupla “non
accurata” il valore di accuratezza e la tupla più vicina della lookup table
Accuratezza Relazione: simple ratio, rapporto tra numero di tuple non accurate
(match < 100%) e numero totale di tuple della relazione, sottratto ad uno






Relazione da valutare
ID
1
Tipo
Corso
Nome
Vittorio Emanuele
Città
Milano
Provincia
Lookup table con fase configurazione
Mi
Città
Chiave
primaria dello
stesso tipo
Key
1
Dug
Corso
Milano
Stesso numero e ordine attributi
Nome
Vittorio Emanuele
Comune
Milano
Lookup table senza fase configurazione
Provincia
Mi
ID
3
Tipo_Nome
Corso Vittorio
Emanuele
Provincia
Mi
Indirizzo
Corso Vittorio Emanuele Milano Mi
14
Fase di configurazione accuratezza sintattica tuple della relazione employees
Struttura
relazione da
valutare
Struttura
lookup table
15
Accuratezza Sintattica Tuple della relazione employees
Tupla corretta della
lookup table
Valore accuratezza
tupla
Tupla non accurata
della relazione valutata
16
Metadati (informazioni circa un dato)
 Organizzati e strutturati tramite un
modello di metadati, metamodello
 Modello concettuale: schema ER
 Modello Logico: documento XML
1. Metadati misurazione: contengono le
informazioni aggiuntive necessarie alle
misurazioni come lookup table per
l’accuratezza sintattica dell’attributo, della
relazione e delle tuple, frequenza media
di aggiornamento per la currency,
coordinate relazione per la consistenza
2. Metadati dimensione: per ogni
dimensione valutata danno informazioni
circa la data, la metrica utilizzata, il livello
di granularità, il valore della misurazione
e eventuali metadati misurazione
utilizzati. Viene creato il report
parziale/totale con formattazione XSL
17
Report delle valutazioni delle dimensioni
18
Conclusioni e Sviluppi Futuri
Il framework potrà essere ancora migliorato:
 L’attivita di assessment
 Creazione
metriche per la valutazione di
nuove dimensioni di qualità
 migliorando

gli algoritmi esistenti
Un’attività di miglioramento (improvement)
della qualità
19
Appendice
20
Seconda metrica basata sulla frequenza dei valori dell’attributo
Confronto tra valori attualmente presenti nell’attributo
1. Analisi dei valori, alla ricerca dei valori con una bassa frequenza (numero di occorrenze uguale
ad uno), possibili candidati ad avere errori di accuratezza
2. Valori con frequenza alta costituiscono il dominio di confronto
3. Primo confronto tramite funzione Jaro per determinare i valori a bassa frequenza accurati e
valori da analizzare nuovamente con il secondo confronto
4. Secondo confronto, tra valore bassa frequenza con valore più vicino, con la funzione soundex
per determinare se i due valori rappresentano o meno lo stesso concetto del mondo reale
5. Determinazione accuratezza attributo tramite simple ratio
NomiImpiegati
….
Paolo
Valori frequenza bassa
Valori accurati
Marco
Luca
Palo
Mal
Luca
Paolo
Palo
Jaro
Luca
Nuova Analisi
Marco
Giacomo
Max
Giacomo
Paolo
Marco
Giacomo
Max
Mal
Dominio confronto
Max
Valori più vicini
Soundex
Palo
Mal
Palo = Paolo
Mal ≠ Max
Soundex
Paolo
Max
Errore
Accuratezza
Sintattica
21
Accuratezza Sintattica Attributo contactFirstName della relazione customers con metrica
frequenza valori
Valore accuratezza
dell’attributo
Correzione
suggerita
22
Completezza
 Livelli di granularità: Relazione, Attributo, Tupla
 Metrica basata sul modello a valori nulli, sull’assunzione CWA. Utilizza la forma
funzionale simple ratio.
 Simple ratio:
 risultati desiderati / numero totale risultati
 1 – ( risultati non desiderati / numero totale risultati)
Algoritmo
1. Ricerca e conteggio valori nulli (Nvn)
2. Determinazione numero attributi (Na) e numero tuple (Nt) e numero massimo di
valori che la relazione può contenere (N)
3. La completezza è determinata tramite
•
Per l’attributo: CA=1 – ( Nvn / Nt)
•
Per la relazione: CR= ( Nvnn / N) dove Nvnn numero valori non nulli
•
Per la tupla: CT=1 – ( Nvn / Na) determinata per ogni tupla della relazione
23
Currency: tempestività di aggiornamento dei dati.
Livello granularità: Attributo.
Scala risultati: <current, not current>
Tre Metriche basate sul metadato “last update”, implementato con il campo Timestamp di MySQL.
 Prima metrica si basa sul recupero della data di ultimo aggiornamento (massimo valore
timestamp).
 Due metriche basate anche sul metadato “frequenza media di aggiorn.” (espressa in giorni).
 Seconda metrica con “frequenza media” inserita dall’utente
1. Differenza tra istante misurazione e last update = delta (es. 14 giorni fa)
2. Recupero frequenza media (es. 13 giorni)
3. Se delta > frequenza media → not current altrimenti se delta ≤ frequenza media → current
 Terza metrica con “frequenza media” ricavata dai valori del timestamp

…
uguale alla precedente metrica nei passi (1) e (3) con l’eccezione (passo 2) che la
frequenza viene calcolata a runtime: con una differenza tra aggiornamenti successivi.
e-mail
timestamp
Differenze
[email protected]
31/12/2005
(08/01/2006) − (31/12/2005) = 8 giorni
[email protected]
08/01/2006
(20/01/2006) − (08/01/2006) = 12 giorni
[email protected]
20/01/2006
Somma 8 + 12 = 20 giorni
Ordinamento valori
timestamp
Rapporto 20 / 3 = 6 giorni
Frequenza media
di aggiornamento
24
Consistenza




Ricerca delle violazioni ai vincoli di integrità in particolare ai vincoli interrelazionali
quindi vincoli di integrità referenziale.
Livello di granularità: attributo ma anche tupla (se si considerano più attributi)
Metrica basata sul record matching con una fase di configurazione
Consideriamo il livello dell’attributo, l’idea è quella di confrontare i valori di un
attributo A di una relazione R1 con i valori di un altro attributo B di una relazione R2
che si suppone contenga gli stessi valori di A, in quanto B rappresenta lo stesso
concetto del mondo reale di A (caso vincoli interrelazionali). Se A è chiave primaria di
R1 e B chiave esterna di R2 allora caso integrità referenziale. Durante il confronto si
determinano i valori inconsistenti.
Algoritmo
Controllo consistenza dei valori di un attributo chiave esterna
1.
2.
3.
4.
5.
Scelta di due relazioni sul quale è definito un vincolo di integrità referenziale
Collegamento relazioni con inserimento coordinate connessione della relazione con
chiave esterna nei metadati
Fase di configurazione per la scelta degli attributi, sui cui valori deve essere
controllata la consistenza
Misurazione con record matching
Per ogni valore non consistente: percentuale di consistenza e valore più vicino
(ricavato dalla relazione con chiave primaria)
25
Consistenza attributo productCode chiave primaria di product e chiave esterna di orderdetails
Valore chiave primaria più
vicino
Valore di consistenza
Valore chiave esterna
inconsistente
26