La ricerca delle dipendenze funzionali nei dati viene applicata in vari campi dell'analisi dei dati: gestione dei database, pulizia dei dati, reverse engineering dei database ed esplorazione dei dati. Di queste dipendenze abbiamo già pubblicato di Anastasia Birillo e Nikita Bobrov. Questa volta Anastasia, laureata del Computer Science Center di quest'anno, condivide lo sviluppo di questo lavoro nell'ambito del NIR, che ha presentato al centro.
Scelta del compito
Durante l'apprendimento al CS Center, ho iniziato a studiare in profondità i database, in particolare la ricerca di dipendenze funzionali e differenziali. Questo argomento era collegato al tema della mia tesi universitaria, quindi durante il lavoro sulla tesi ho iniziato a leggere articoli sulle varie dipendenze nei database. Ho scritto una panoramica di quest'area — uno dei miei primi in inglese e l'ho presentato alla conferenza SEIM-2017. Ero molto felice quando ho scoperto che era stato accettato e ho deciso di approfondire il tema. Il concetto stesso non è nuovo: è stato applicato fin dagli anni '90, ma anche adesso trova applicazione in molti campi.
Nel secondo semestre di studio al centro, ho iniziato un progetto di ricerca volto a migliorare gli algoritmi di ricerca delle dipendenze funzionali. Ho lavorato a questo progetto insieme al dottorando di SPbGU Nikita Bobrov presso JetBrains Research.
Complesso computazionale della ricerca delle dipendenze funzionali
Il problema principale è la complessità computazionale. Il numero possibile di dipendenze minime e non banali è limitato superiormente dal valore 
, dove 
è il numero di attributi nella tabella. Il tempo di esecuzione degli algoritmi dipende non solo dal numero di attributi, ma anche dal numero di righe. Negli anni '90, gli algoritmi per la ricerca delle dipendenze funzionali su un normale PC desktop potevano elaborare set di dati contenenti fino a 20 attributi e decine di migliaia di righe, richiedendo anche diverse ore. Gli algoritmi moderni, che operano su processori multicore, trovano dipendenze per set di dati composti da centinaia di attributi (fino a 200) e centinaia di migliaia di righe, in un tempo simile. Tuttavia, ciò non è sufficiente: tale tempo è inaccettabile per la maggior parte delle applicazioni reali. Pertanto, abbiamo sviluppato approcci per velocizzare gli algoritmi esistenti.
Schemi di caching per l'intersezione delle partizioni
Nella prima parte del lavoro abbiamo sviluppato schemi di caching per una classe di algoritmi che utilizzano il metodo di intersezione delle partizioni. Una partizione per un attributo rappresenta un insieme di liste, dove ogni lista contiene i numeri di riga con valori identici per questo attributo. Ogni lista di questo tipo è chiamata cluster. Molti algoritmi moderni usano partizioni per determinare se una dipendenza è mantenuta o meno, seguendo il lemma: La dipendenza 
è mantenuta, se 
. Qui 
è designata la partizione e si usa il concetto di dimensione della partizione — il numero di cluster in essa. Gli algoritmi che usano partizioni, quando la dipendenza è violata, aggiungono attributi aggiuntivi al lato sinistro della dipendenza, dopo di che la ricalcolano eseguendo l'operazione di intersezione delle partizioni. Questa operazione è chiamata specializzazione negli articoli. Ma abbiamo notato che le partizioni per le dipendenze, che saranno mantenute solo dopo diversi turni di specializzazione, possono essere riutilizzate attivamente, il che può notevolmente ridurre il tempo di esecuzione degli algoritmi, poiché l'operazione di intersezione è costosa.
Pertanto, abbiamo proposto un'euristica basata sull'Entropia di Shannon e sull'incertezza di Gini, oltre alla nostra metrica, che abbiamo chiamato Entropia Inversa. Essa è una lieve modifica dell'Entropia di Shannon e cresce man mano che aumenta l'unicità del set di dati. L'euristica proposta appare come segue:
Qui 
è il grado di unicità della partizione appena calcolata 
, ma 
è una mediana dei livelli di unicità per singoli attributi. Come metrica di unicità sono state testate tutte e tre le metriche descritte sopra. Si può anche notare che nell'euristica sono presenti due modificatori. Il primo indica quanto sia vicina la partizione attuale alla chiave primaria e consente di memorizzare nella cache in modo più efficace quelle partizioni che sono lontane dalla chiave potenziale. Il secondo modificatore consente di monitorare l'occupazione della cache e stimola così l'aggiunta di un numero maggiore di partizioni nella cache in presenza di spazio libero. La risoluzione riuscita di questo compito ha permesso di accelerare l'algoritmo PYRO del 10-40% a seconda del dataset. Vale la pena notare che l'algoritmo PYRO è il più efficace in questo ambito.
Nell'immagine sottostante si possono vedere i risultati dell'applicazione dell'euristica proposta rispetto all'approccio di caching di base basato sul lancio della moneta. L'asse X è logaritmico.
Metodo alternativo di memorizzazione delle partizioni
Poi abbiamo proposto un metodo alternativo di memorizzazione delle partizioni. Le partizioni rappresentano un insieme di cluster, ognuno dei quali contiene i numeri delle tuple con valori identici per determinati attributi. Questi cluster possono contenere lunghe sequenze di numeri di tuple, ad esempio, se i dati nella tabella sono ordinati. Pertanto, abbiamo proposto uno schema di compressione per la memorizzazione delle partizioni, ossia la memorizzazione degli intervalli di valori nei cluster delle partizioni:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Primo~intervallo}, underbrace{7, 8}_{Secondo~intervallo}, 10}}\ downarrow{Compressione}\ pi(X) = {{underbrace{$, 1, 5}_{Primo~intervallo}, underbrace{7, 8}_{Secondo~intervallo}, 10}}$$display$$
Questo metodo è riuscito a ridurre il consumo di memoria durante l'esecuzione dell'algoritmo TANE dal 1 al 25%. L'algoritmo TANE è un algoritmo classico per la ricerca di FD, utilizza le partizioni nel suo funzionamento. Nell'ambito della pratica è stato scelto proprio l'algoritmo TANE, in quanto implementare la memorizzazione per intervallo è stato significativamente più semplice rispetto a, ad esempio, PYRO, per valutare se l'approccio proposto funziona. I risultati ottenuti sono presentati nell'immagine sottostante. L'asse X è logaritmico.
Conferenza ADBIS-2019
In base ai risultati della ricerca di settembre 2019, ho presentato un articolo alla conferenza 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Durante l'intervento, il lavoro è stato sottolineato da Bernhard Thalheim, una figura di rilievo nel campo dei database. I risultati delle ricerche hanno costituito la base della mia tesi di laurea nel programma di matematica e meccanica della SPbGU, durante la quale entrambi gli approcci proposti (caching e compressione) sono stati implementati negli algoritmi: TANE e PYRO. I risultati hanno dimostrato che gli approcci proposti sono universali, poiché su entrambi gli algoritmi con entrambi gli approcci si è osservata una significativa riduzione della memoria utilizzata, nonché una significativa riduzione del tempo di esecuzione degli algoritmi.
Fonte: habr.com
