Vincenzo DEUFEMIA | Progetti

MINING DI DIPENDENZE FUNZIONALI APPROSSIMATE DA GRANDI DATABASE

Le dipendenze funzionali sono state spesso utilizzate per verificare la qualità degli schemi di database relazionali. Negli ultimi decenni la definizione canonica di dipendenza funzionale approssimata è stata spesso estesa allo scopo di esprimere vincoli in nuovi contesti applicativi. In letteratura tali dipendenze estese sono note come Relaxed Functional Dependencies (RFD), e ne esistono più di trenta diversi tipi, utilizzate in vari contesti applicativi, tra cui data cleaning, deduplicazione di record, individuazione di frodi, database multimediali, etc. Tuttavia, l’utilità delle RFD è legata alla capacità di inferirle in modo automatico dai dati, avendo oggi a disposizione quantità enormi di dati. Tuttavia, se in passato gli algoritmi di inferenza di dipendenze funzionali esatte si sono rivelati particolarmente complessi, richiedendo la definizione di opportune tecniche di pruning, tale complessità esplode in modo considerevole per le RFD. Mentre infatti per le dipendenze esatte è possibile sfruttare divere proprietà delle partizioni indotte dai valori degli attributi, nonché il fatto che le dipendenze debbano valere per tutte le tuple, tali proprietà non si applicano quando si devono esaminare similarità tra valori di attributi e porzioni del database su cui le rfd valgono. Il tutto è reso ulteriormente complesso se si vogliono inferire anche le soglie in modo automatico.Nonostante gli oltre trenta diversi tipi di RFD, solo per pochi di essi sono stati forniti algoritmi per poterle inferire in modo automatico ed efficiente dai dati. Di recente, abbiamo prodotto dei prototipi di algoritmi general purpose, in gado di inferire diversi tipi di dipendenze, includendo sia quelle che rilassano sul confronto tra attributi che quelle che rilassano sulla validità, richiedendo però all’utente di specificare manualmente le soglie. Oltre ad estendere e sperimentare ulteriormente gli algoritmi sin qui prodotti, in questo progetto di ricerca si intendono definire nuovi algoritmi per l’inferenza di rfd dai dati, sfuttando concetti come la dominanza statistica, ma anche algoritmi genetici, cercando di individuare opportune proprietà del processo di inferenza che portino alla definizione di opportune tecniche di pruning. Ulteriore obiettivo del progetto è quello di verificare la possibilità di utilizzare opportune tecniche di machine learning in grado di permettere di inferire in modo automatico non solo le rfd, ma anche le soglie ad esse associate. Gli algoritmi prodotti saranno sperimentati su database di grandi dimensioni, comunemente usati per esperimenti del settore. Allo scopo, si cercherà di evidenziare soprattutto criticità legate alla scalabilitàUna parte estremamente rilevante del progetto riguarderà la sperimentazione dei prototipi su data set di cospicue dimensioni, allo scopo di verificare le capacità di inferenza, ma soprattutto le performance e la scalabilità. Si prevedono pertanto cicli di sperimentazione e revisione che richiederanno la revisione degli algoritmi e dei prototipi in presenza di problemi di precisione nell’inferenza delle RFD e delle relative soglie, ma soprattutto, in presenza di prevedibili problemi di scalabilità. Infine, oltre ai domini applicativi menzionati in precedenza, si cercheranno di individuarne di nuovi sui quali sperimentare i migliori algoritmi individuati. Ad esempio, si cercheranno nuove applicazioni nell’ambito del data quality e del data profiling.