La ricerca di dipendenze funzionali nei dati è applicata in diverse aree dell'analisi dei dati: gestione di database, pulizia dei dati, reverse engineering di database ed esplorazione dei dati. Abbiamo già pubblicato informazioni sulle dipendenze stesse. di Anastasia Birillo e Nikita Bobrov. Questa volta Anastasia, laureata al Computer Science Center di quest'anno, condivide lo sviluppo di quest'opera nell'ambito della ricerca scientifica, che ha difeso nel centro.
Scelta del compito
Durante il mio percorso di studi al CS Center ho approfondito lo studio dei database, in particolare la ricerca di dipendenze funzionali e differenziali. Questo argomento era legato alla mia tesi universitaria, quindi durante la scrittura ho cominciato a leggere articoli sulle varie dipendenze nei database. Ho scritto una panoramica su quest'area, uno dei miei primi lavori in inglese e l'ho presentata alla conferenza SEIM-2017. Ero molto contenta quando ho scoperto che era stata accettata e ho deciso di approfondire l'argomento. Il concetto stesso non è nuovo: è stato applicato per la prima volta negli anni '90, ma continua a trovare applicazione in molti settori.
Nel secondo semestre di studio al centro, ho avviato un progetto di ricerca per migliorare gli algoritmi di ricerca delle dipendenze funzionali. Ho lavorato a questo progetto insieme al dottorando Nikita Bobrov dell'SPBGU presso JetBrains Research.
La complessità computazionale della ricerca di dipendenze funzionali
Il problema principale è la complessità computazionale. Il numero di dipendenze minime e non banali possibili è limitato superiormente dal valore 
, dove 
cioè il numero di attributi della 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 comune PC desktop potevano elaborare set di dati contenenti fino a 20 attributi e decine di migliaia di righe in diverse ore. Gli algoritmi moderni, che lavorano su processori multi-core, scoprono dipendenze per set di dati composti da centinaia di attributi (fino a 200) e centinaia di migliaia di righe, in tempi simili. Tuttavia, questo non è sufficiente: tale tempo è inaccettabile per la maggior parte delle applicazioni reali. Pertanto, abbiamo sviluppato approcci per accelerare 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 quel dato attributo. Ogni lista è chiamata cluster. Molti algoritmi moderni utilizzano le partizioni per determinare se una dipendenza è mantenuta o meno, seguendo precisamente il lemma: Una dipendenza 
è mantenuta se 
. Qui 
denota una partizione e viene utilizzato il concetto di dimensione della partizione - il numero di cluster in essa. Gli algoritmi che utilizzano le partizioni, quando una dipendenza viene violata, aggiungono ulteriori attributi al lato sinistro della dipendenza, dopo di che la ricalcolano, eseguendo l'operazione di intersezione delle partizioni. Tale operazione è chiamata specializzazione in articoli. Ma abbiamo notato che le partizioni per dipendenze che saranno mantenute solo dopo diversi turni di specializzazione possono essere riutilizzate attivamente, il che può ridurre significativamente 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. Questa è una leggera modifica dell'entropia di Shannon e cresce man mano che cresce l'unicità del set di dati. L'euristica proposta è la seguente:
Qui 
il grado di unicità della recente partizione calcolata 
, e 
è la mediana dei gradi di unicità per i singoli attributi. Sono state testate come metriche di unicità tutte e tre le metriche descritte sopra. Inoltre, si può notare che nell'euristica ci sono due modificatori. Il primo indica quanto sia vicina la partizione corrente alla chiave primaria e consente di memorizzare in cache maggiormente quelle partizioni che sono lontane dalla chiave potenziale. Il secondo modificatore consente di monitorare l'occupazione della cache e stimola quindi l'aggiunta di un numero maggiore di partizioni nella cache quando c'è spazio libero. Risolvere con successo questo problema ha permesso di accelerare l'algoritmo PYRO dal 10% al 40% a seconda del set di dati. È importante notare che l'algoritmo PYRO è il più efficace in questo campo.
Nella figura sottostante è possibile osservare i risultati dell'applicazione dell'euristica proposta rispetto all'approccio di base del caching, basato sul lancio di una moneta. L'asse X è logaritmico.
Metodo alternativo per la memorizzazione delle partizioni
Successivamente, abbiamo proposto un metodo alternativo per la memorizzazione delle partizioni. Le partizioni rappresentano un insieme di cluster, ciascuno 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 intervallare dei 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 tra l'1 e il 25%. L'algoritmo TANE è un algoritmo classico per la scoperta delle dipendenze funzionali, che utilizza le partizioni nel suo funzionamento. Nell'ambito della pratica è stato scelto proprio l'algoritmo TANE, poiché integrare la memorizzazione intervallare in esso era significativamente più semplice che, ad esempio, in PYRO, per valutare se l'approccio proposto funziona. I risultati ottenuti sono presentati nella figura sottostante. L'asse X è logaritmico.
Conferenza ADBIS-2019
A seguito della ricerca, nel settembre 2019 ho presentato un articolo alla 23ª Conferenza Europea su Avanzamenti nei Database e nei Sistemi Informativi (ADBIS-2019). Durante la presentazione, il lavoro è stato riconosciuto da Bernhard Thalheim, una figura importante nel campo dei database. I risultati della ricerca sono stati la base della mia tesi di laurea in Matematica e Meccanica all'Università Statale di San Pietroburgo, durante la quale entrambi gli approcci proposti (caching e compressione) sono stati implementati in entrambi gli algoritmi: TANE e PYRO. I risultati hanno dimostrato che gli approcci proposti sono universali, poiché in entrambi gli algoritmi con entrambi gli approcci si è osservata una significativa riduzione della memoria utilizzata, così come una significativa riduzione dei tempi di esecuzione degli algoritmi.
Fonte: habr.com
