Data ProfilingMatteo Senardi

ScopoFine dello studio è valutare le tecniche di Data Profiling nell’ambito della ricerca delle dipendenze funzionali.

I test effettuati sono basati su alcuni esperimenti di dependency discovery, riportati nell’articolo “Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms”.

Cosa c’è dentro i nostri dati?

Cosa c’è dentro i nostri dati?Modelli, Densità, Vincoli Riscontri attesi

Residuali, Outlier, Anomalie Riscontri disattesi

Che uso posso farne?

Che uso posso farne?1. Aiutare a fare una valutazione approfondità della

qualità dei dati comprendere contenuto, struttura e relazioni sul set di dati analizzato;

2. Scoprire anomalie nei dati;

3. Capire se i dati esistenti possono essere applicati ad altre aree o scopi.

Analisi del contestoDurante il processo di database administration si possono riscontrare varie situazioni, quali:

1. Diverse inconsistenze all’interno dei dati, quali record mancanti o valori NULL;

2. Colonna scelta come chiave primaria risulta non univoca all’interno della tabella;

Analisi del contesto3. Incoerenza tra design dello schema e esigenze

dell’utente finale;

4. Qualsiasi altro problema con i dati, non correttamente valutato.

Correggere questi problemi di data quality porta ad un grande lavoro di rielaborazione aumento dei costi in termini di tempo e spesa!

ApproccioPiuttosto che cercare una soluzione al problema, sarebbe meglio agire inzialmente in modo da evitare che si possa creare il problema stesso....

Dopo tutto “prevenire è meglio che curare”.

Proprio qui viene in aiuto il Data Profiling.

Definizione di Data Profiling“Processo di esaminazione e analisi statistica del contenuto di una sorgente di dati e successiva raccolta di informazioni.” Wikipedia

“Data Profiling si riferisce all’attività di creazione di un piccolo ma informativo sommario di database.” Ted Johnson

ScopoIl processo di Data Profiling produce statistiche che possono essere utilizzate per vari scopi di analisi:

• Analizzare la qualità dei dati;

• Cercare il numero di valori NULL di un attributo;

• Controllare se valori NULL o di stringhe vuote possono generare problemi ;

Scopo• Analisi statistica di lunghezza massima, minima e

media delle stringhe di una colonna;

• Determinare il formato dei dati appropriato;

• Trovare colonne univoche da scegliere come chiavi;

• Ricerca di dipendenze funzionali.

Come applicare Data Profiling?Generalmente Data Profiling si conduce in due modi:

1. Scrivendo query SQL ad hoc su sample di dati;

2. Utilizzando strumenti di Data Profiling quali:• IBM WebSphere Information Analyser;• Microsoft’s SQL Server Integration Services;• SAP BusinessObjects Information Steward;• Talend Open Studio for Data Quality;• Metanome; • etc…

MetanomeProgetto a capo di Felix Naumann presso Hasso-Plattner-Institute applicazione freeware con funzionalità di Data Profiling realizzata mediante lo sviluppo e l'integrazione di algoritmi efficienti in uno strumento comune web-based.

ArchitetturaApplicazione sviluppata seguendo lo standard MVC: 1. Model script e file di configurazione XML;

2. View http server;

3. Cotroller java.

Progetti di Data Profiling basati su MetanomeVengono forniti diversi algoritmi per svolgere compiti di Data Profiling utilizzando Metanome:

• Functional dependency discovery;•Unique column combination discovery;•Inclusion dependency discovery;•…..

Dependency DiscoveryData uno schema di relazione R(X), una dipendenza funzionale su R è un vincolo di integrità espresso nella forma YZ, dove Y e Z sono sottoinsiemi di X.

Il procedimento di scoperta delle FD presenta diverse problematiche:

1. Costo per tempo di ricerca accettabile;2. Dipendenze funzionali individuate devono sussistere.

Algoritmi esistentiTra gli algoritmi di dependency discovery compatibili con cui si cerca di ottimizzare i risultati, diminuendo il tempo di ricerca:

• Tane;

• FD-Mine.

Di seguito sarà descritto funzionamento e criticità.

TaneTane si basa su due principi:

1. Partizione degli attributi per ogni valore in attributo si creano degli insiemi che contengono il numero di righe che ne hanno un’occorrenza;

2. Ricerca bottom-up sulla struttura lattice si inizia testando XY a livello 1, poi con XXY a livello 2 ….

TaneDue casi di potatura (pruning) sull’albero delle ricerche:

• Ogni volta che viene trovata una chiave;

• Ogni volta che viene trovata una superchiave, se XY ed X è superchiave, allora si potrà escludere XUY nella ricerca, tagliando gli archi del lattice che vanno da X al nodo successivo.

Criticità: FD non individuateConsiderando R={A,B,C}, con A e BC chiavi:

• Livello 1, Tane trova A chiave BϵC+(B)e CϵC+(C), per cui AB e AC, e A viene eliminato dal lattice;

• Livello 2, Tane trova BC chiave ma C+(AB) e C+(AC) non sono disponibili essendo stata eliminata A;

In tale modo la FD BCA non verrebbe considerata!

SoluzioneModifica della regola di pruning invece di eliminare A dal lattice, viene marcata come non valida. I nodi non validi non sono più testati per la scoperta delle dipendenze funzionali, ma possono essere utilizzati per generare ulteriori nodi non validi fintanto che i loro set C+ non sono vuoti.

FD_-MineFD-Mine sfrutta le proprietà delle Dipendenze Funzionali per effettuare i tagli:

1. Simmetria: se XY e YX, allora XY: i due attributi sono equivalenti;

FD_-Mine2. Inferenze addizionali sugli assiomi di Armstrong:

• pseudotransitività: dato XY, se vale XWZ, allora vale YWZ• dato XY, se vale ZWX, allora vale ZWY

In tale modo si eliminano attributi nella ricerca del lattice per velocizzare il processo.

Criticità: FD non minimeSi dimostra FD-Mine possa condurre alla scoperta di dipendenze funzionali non minime:

• Assumendo: X equivalente a Y, XWZ (in rispetto dell’assioma YWZ);

• Dato un attributo A di Y dipendente da W’, subset di W;• YWZ, ma un subset di YW, chiamato YW-A, determina

già Z La dipendenza funzionale non è minima.

Misure osservateRiporto le misure osservate nella simulazione:

• Numero di dipendenze funzionali individuate;

• Tempi di profilazione dei due algoritmi;

• Rapporto tra i tempi di simulazione dei due algoritmi.

Risultati del Paper

Confronto dei risultati ottenuti• Tane ha individuato 4 FD in 362 secondi contro 1.1 secondi dei risultati del Paper;

• FD-Mine 16 FD in 85 secondi;

• I dati della ricerca confermano 4 FD non minime presenti nel dataset.

Confronto dei risultati ottenuti• Tane ha individuato 1 FD in 431 secondi;

• FD-Mine 1 FD in 150 secondi;

• I dati della ricerca confermano 1 FD non minima presente nel dataset.

Confronto dei risultati ottenuti• Tane ha individuato 1 FD in 1964 secondi;

• FD-Mine 1 FD in 4756 secondi;

• I dati della ricerca confermano 1 FD non minima presente nel dataset.

Confronto dei risultati ottenuti• Tane ha individuato 46 FD in 2441 secondi;

• FD-Mine 6508 FD in 3117 secondi;

• I dati della ricerca confermano 46 FD non minime presenti nel dataset.

Confronto dei risultati ottenuti• Tane ha individuato 1 FD in 4631 secondi;

• FD-Mine 1 FD in 8444 secondi contro 7.1 secondi dei risultati del Paper;

• I dati della ricerca confermano 1 FD non minima presente nel dataset.

Confronto dei risultati ottenuti• Tane ha individuato un numero di DF inferiore rispetto al risultato della ricerca 527 contro 538.

• FD-Mine invece ha superato la soglia di 4 ore di osservazione time limit

Video Metanome

Schermata Time Limit

Schermata #1 Memory Limit

Schermata #2 Memory Limit

Schermata Extended Results

Osservazioni• Tane implementa esclusivamente regole di potatura

affidabili algoritmo tipicamente più lento;

• FD-Mine individua diverse FD non-minime dimensione dei risultati può sovrastare velocemente la capacità di memoria;

• ricerca di FD non-minime può essere richiedente in tempo, annullando il vantaggio cronometrico di FD-Mine.

Osservazioni• Dai grafici si può notare un proggressivo

avvicinamento nelle proporzioni dei risultati, all’aumentare della dimensione del dataset tempo media le prestazioni

• La differenza mostrata nel diverso numero di DF per il dataset echocardiogram.csv è dovuta ad un errore di formattazione, risolto dopo la pubblicazione del Paper risultato ottenuto è da considerarsi attendibile.

ConclusioniA causa del limite prestazionale della macchine utilizzata, non è stato possibile raggiungere le performance originarie.

I risultati mostrano che nella maggior parte delle simulazioni le misure analizzate corrispondono ai dati presenti nella ricerca.

ConclusioniSi deve inoltre tenere conto dell’utilizzo di una versione dell’applicazione ancora in via di sviluppo e non esente da bug. Nuove ottimizzazioni e aggiornamenti degli algoritmi potrebbero favorire l’espansione dello strumento, che ricordo al momento è freeware.

Segnalo per ultimo la realizzazione di una pagina GitHub con funzione di guida per l’installazione di Metanome: https://github.com/pualien/Metanome-Installation-Guide

Bibliografia• Naumann Felix (2013). “Data Profiling Revisited”, Hasso Plattner Institut.

http://hpi.de/fileadmin/user_upload/fachgebiete/naumann/publications/2013/profiling_vision.pdf.

• Thorsten Papenbrock, T. Bergmann, M. Finke, J. Zwiener, F. Naumann (2015). “Data Profiling with Metanome”, Algorithms”, Hasso Plattner Institut. http://www.vldb.org/pvldb/vol8/p1860-papenbrock.pdf.

• Thorsten Papenbrock, J. Ehrlich, J. Marten, T. Neubert, J.P. Rudolph, M. Schonberg, J. Zwiener, F. Naumann (2015). ”Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms”, Hasso Plattner Institut. https://hpi.de/fileadmin/user_upload/fachgebiete/naumann/publications/2015/p1897-papenbrock.pdf

• Ykä Huhtala, Juha Kärkkäinen, Pasi Porkka, Hannu Toivonen (1999). “Tane: An Efficient Algorithm for Discovering Functional and Approximate Dependencies”, University of Helsinki. http://www.cs.helsinki.fi/u/htoivone/pubs/tane_99.pdf.

• Hong Yao, Howard J. Hamilton (2007). “Mining functional dependencies from data”, University of Regina. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.563.2429&rep=rep1&type=pdf.

Grazie per l’attenzione