La ricerca delle dipendenze funzionali nei dati viene utilizzata in varie aree dell'analisi dei dati: gestione del database, pulizia dei dati, reverse engineering del database ed esplorazione dei dati. Abbiamo già pubblicato informazioni sulle dipendenze stesse Anastasia Birillo e Nikita Bobrov. Questa volta, Anastasia, laureata quest'anno al Computer Science Center, condivide lo sviluppo di questo lavoro come parte del lavoro di ricerca che ha difeso al centro.
Selezione del compito
Mentre studiavo al centro CS, ho iniziato a studiare in modo approfondito i database, ovvero la ricerca delle dipendenze funzionali e differenziali. Questo argomento era correlato all'argomento dei miei corsi all'università, quindi mentre lavoravo ai corsi ho iniziato a leggere articoli su varie dipendenze nei database. Ho scritto una recensione su quest'area, una delle mie prime in inglese e lo ha presentato alla conferenza SEIM-2017. Sono stato molto felice quando ho scoperto che dopotutto era stata accettata e ho deciso di approfondire l'argomento. Il concetto in sé non è nuovo: ha iniziato ad essere utilizzato negli anni '90, ma anche adesso viene utilizzato in molte aree.
Durante il mio secondo semestre al centro, ho avviato un progetto di ricerca per migliorare gli algoritmi per la ricerca delle dipendenze funzionali. Ci ha lavorato insieme allo studente laureato dell'Università statale di San Pietroburgo, Nikita Bobrov, presso JetBrains Research.
Complessità computazionale della ricerca di dipendenze funzionali
Il problema principale è la complessità computazionale. Il numero di possibili dipendenze minime e non banali è limitato sopra dal valore Dove — numero di attributi della tabella. Il tempo di funzionamento degli algoritmi dipende non solo dal numero di attributi, ma anche dal numero di righe. Negli anni '90, gli algoritmi di ricerca delle leggi federali su un normale PC desktop potevano elaborare set di dati contenenti fino a 20 attributi e decine di migliaia di righe in diverse ore. I moderni algoritmi eseguiti su processori multi-core rilevano le dipendenze per set di dati costituiti da centinaia di attributi (fino a 200) e centinaia di migliaia di righe all'incirca nello stesso tempo. Tuttavia, ciò non basta: un tempo del genere è inaccettabile per la maggior parte delle applicazioni del mondo reale. Pertanto, abbiamo sviluppato approcci per accelerare gli algoritmi esistenti.
Schemi di memorizzazione nella cache per intersezioni di partizioni
Nella prima parte del lavoro abbiamo sviluppato schemi di caching per una classe di algoritmi che utilizzano il metodo dell'intersezione delle partizioni. Una partizione per un attributo è un insieme di elenchi, in cui ciascun elenco contiene numeri di riga con gli stessi valori per un determinato attributo. Ciascuno di questi elenchi è chiamato cluster. Molti algoritmi moderni utilizzano le partizioni per determinare se viene mantenuta o meno una dipendenza, ovvero aderiscono al lemma: Dipendenza tenuto se . Ecco viene designata una partizione e viene utilizzato il concetto di dimensione della partizione: il numero di cluster al suo interno. Gli algoritmi che utilizzano le partizioni, quando la dipendenza viene violata, aggiungono ulteriori attributi al lato sinistro della dipendenza, quindi la ricalcolano, eseguendo l'operazione di intersezione delle partizioni. Questa operazione si chiama specializzazione negli articoli. Ma abbiamo notato che le partizioni per le dipendenze che verrebbero mantenute solo dopo alcuni cicli 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 Ginny, nonché sulla nostra metrica, che abbiamo chiamato entropia inversa. Si tratta di una leggera modifica dell'entropia di Shannon e aumenta con l'aumentare dell'unicità del set di dati. L’euristica proposta è la seguente:
Qui — grado di unicità della partizione recentemente calcolata E è la mediana dei gradi di unicità per i singoli attributi. Tutti e tre i parametri descritti sopra sono stati testati come parametri di unicità. Puoi anche notare che ci sono due modificatori nell'euristica. Il primo indica quanto la partizione corrente è vicina alla chiave primaria e consente di memorizzare nella cache in misura maggiore quelle partizioni lontane dalla chiave potenziale. Il secondo modificatore consente di monitorare l'occupazione della cache e quindi incoraggia l'aggiunta di più partizioni alla cache se è disponibile spazio libero. La riuscita soluzione di questo problema ci ha permesso di accelerare l'algoritmo PYRO del 10-40%, a seconda del set di dati. Vale la pena notare che l'algoritmo PYRO è quello di maggior successo in quest'area.
Nella figura seguente è possibile vedere i risultati dell'applicazione dell'euristica proposta rispetto a un approccio di caching di base con lancio di monete. L'asse X è logaritmico.
Un modo alternativo per archiviare le partizioni
Abbiamo quindi proposto un modo alternativo per archiviare le partizioni. Le partizioni sono un insieme di cluster, ognuno dei quali memorizza numeri di tuple con valori identici per determinati attributi. Questi cluster possono contenere lunghe sequenze di numeri di tupla, ad esempio se i dati in una tabella sono ordinati. Pertanto, abbiamo proposto uno schema di compressione per l'archiviazione delle partizioni, ovvero l'archiviazione a intervalli di valori in cluster di partizioni:
$$display$$pi(X) = {{parentesi graffa{1, 2, 3, 4, 5}_{Primo intervallo}, parentesi graffa{7, 8}_{Secondo intervallo}, 10}}\ downarrow{ Compressione} \ pi(X) = {{parentesi graffa{$, 1, 5}_{Primo~intervallo}, parentesi graffe{7, 8}_{Secondo~intervallo}, 10}}$$visualizzazione$$
Questo metodo è stato in grado di ridurre il consumo di memoria durante il funzionamento dell'algoritmo TANE dall'1 al 25%. L'algoritmo TANE è un classico algoritmo per la ricerca di leggi federali; utilizza le partizioni durante il suo lavoro. Come parte della pratica, è stato scelto l'algoritmo TANE, poiché era molto più semplice implementare la memorizzazione a intervalli in esso rispetto, ad esempio, a PYRO per valutare se l'approccio proposto funziona. I risultati ottenuti sono presentati nella figura seguente. L'asse X è logaritmico.
Conferenza ADBIS-2019
Sulla base dei risultati della ricerca, a settembre 2019 ho pubblicato un articolo alla 23a Conferenza europea sui progressi nei database e nei sistemi informativi (ADBIS-2019). Durante la presentazione il lavoro è stato notato da Bernhard Thalheim, una persona significativa nel campo delle banche dati. I risultati della ricerca hanno costituito la base della mia tesi di laurea magistrale in matematica e meccanica presso l'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. Inoltre, i risultati hanno mostrato che gli approcci proposti sono universali, poiché su entrambi gli algoritmi, con entrambi gli approcci, è stata osservata una significativa riduzione del consumo di memoria, nonché una significativa riduzione del tempo operativo degli algoritmi.
Fonte: habr.com