Sprawnie znajduj zależności funkcjonalne w bazach danych

Znajdowanie zależności funkcjonalnych w danych znajduje zastosowanie w różnych obszarach analizy danych: zarządzaniu bazami danych, czyszczeniu danych, inżynierii wstecznej baz danych i eksploracji danych. O samych zależnościach już pisaliśmy статью Anastasia Birillo i Nikita Bobrov. Tym razem Anastazja, tegoroczna absolwentka Centrum Informatyki, dzieli się rozwojem tej pracy w ramach pracy badawczej, którą obroniła w ośrodku.

Wybór zadań

Studiując w centrum CS, zacząłem dogłębnie studiować bazy danych, a mianowicie szukać zależności funkcjonalnych i różnicowych. Temat ten był powiązany z tematem moich zajęć na uniwersytecie, dlatego pracując nad zajęciami zacząłem czytać artykuły na temat różnych zależności w bazach danych. Napisałem recenzję tego obszaru - jedną z moich pierwszych artykuły w języku angielskim i zgłosiła go na konferencję SEIM-2017. Bardzo się ucieszyłam, gdy dowiedziałam się, że mimo wszystko została przyjęta, i postanowiłam zgłębić temat. Sama koncepcja nie jest nowa – zaczęto ją stosować już w latach 90., ale już teraz znajduje zastosowanie w wielu obszarach.

Podczas drugiego semestru studiów w ośrodku rozpocząłem projekt badawczy mający na celu udoskonalenie algorytmów wyszukiwania zależności funkcjonalnych. Pracowała nad nim wspólnie ze studentką Uniwersytetu Państwowego w Petersburgu Nikitą Bobrową w JetBrains Research.

Złożoność obliczeniowa poszukiwania zależności funkcjonalnych

Głównym problemem jest złożoność obliczeniowa. Liczba możliwych minimalnych i nietrywialnych zależności jest ograniczona powyżej wartością Gdzie — liczba atrybutów tabeli. Czas działania algorytmów zależy nie tylko od liczby atrybutów, ale także od liczby wierszy. W latach 90. algorytmy wyszukiwania prawa federalnego na zwykłym komputerze stacjonarnym mogły przetwarzać zestawy danych zawierające do 20 atrybutów i dziesiątki tysięcy wierszy w ciągu nawet kilku godzin. Nowoczesne algorytmy działające na procesorach wielordzeniowych wykrywają zależności dla zbiorów danych składających się z setek atrybutów (aż do 200) i setek tysięcy wierszy mniej więcej w tym samym czasie. To jednak nie wystarczy: taki czas jest nie do przyjęcia dla większości rzeczywistych zastosowań. Dlatego opracowaliśmy podejścia mające na celu przyspieszenie istniejących algorytmów.

Schematy buforowania dla przecięć partycji

W pierwszej części pracy opracowaliśmy schematy buforowania dla klasy algorytmów wykorzystujących metodę przecięcia partycji. Partycja dla atrybutu to zbiór list, gdzie każda lista zawiera numery wierszy z tymi samymi wartościami dla danego atrybutu. Każda taka lista nazywana jest klastrem. Wiele nowoczesnych algorytmów wykorzystuje partycje do określenia, czy zależność jest utrzymywana, czy nie, a mianowicie stosują się do lematu: Zależność odbyło się, jeśli , tutaj wyznacza się partycję i stosuje się koncepcję rozmiaru partycji - liczby znajdujących się w niej klastrów. Algorytmy wykorzystujące partycje, w przypadku naruszenia zależności, dodają dodatkowe atrybuty po lewej stronie zależności, a następnie przeliczają je, wykonując operację przecięcia partycji. Operację tę nazywa się specjalizacją w artykułach. Zauważyliśmy jednak, że partycje dla zależności, które zostaną zachowane dopiero po kilku rundach specjalizacji, można aktywnie ponownie wykorzystać, co może znacznie skrócić czas działania algorytmów, ponieważ operacja przecięcia jest kosztowna.

Dlatego zaproponowaliśmy heurystykę opartą na Entropii Shannona i Niepewności Ginny, a także naszą metrykę, którą nazwaliśmy Odwróconą Entropią. Jest to niewielka modyfikacja Shannon Entropy i zwiększa się wraz ze wzrostem niepowtarzalności zbioru danych. Proponowana heurystyka jest następująca:

Tutaj — stopień niepowtarzalności ostatnio obliczonego podziału I jest medianą stopni niepowtarzalności poszczególnych atrybutów. Wszystkie trzy metryki opisane powyżej zostały przetestowane jako metryki niepowtarzalności. Można również zauważyć, że w heurystyce występują dwa modyfikatory. Pierwsza wskazuje, jak blisko klucza podstawowego znajduje się bieżąca partycja i pozwala w większym stopniu buforować te partycje, które są daleko od potencjalnego klucza. Drugi modyfikator pozwala monitorować zajętość pamięci podręcznej i tym samym zachęca do dodawania kolejnych partycji do pamięci podręcznej, jeśli jest dostępna wolna przestrzeń. Pomyślne rozwiązanie tego problemu pozwoliło przyspieszyć algorytm PYRO o 10-40%, w zależności od zbioru danych. Warto dodać, że algorytm PYRO odnosi największe sukcesy w tym obszarze.

Na poniższym rysunku możesz zobaczyć wyniki zastosowania proponowanej heurystyki w porównaniu z podstawowym podejściem do buforowania monetą. Oś X jest logarytmiczna.

Alternatywny sposób przechowywania partycji

Następnie zaproponowaliśmy alternatywny sposób przechowywania partycji. Partycje to zbiór klastrów, z których każdy przechowuje liczbę krotek o identycznych wartościach dla niektórych atrybutów. Te klastry mogą zawierać długie sekwencje liczb krotek, na przykład jeśli dane w tabeli są uporządkowane. Dlatego zaproponowaliśmy schemat kompresji do przechowywania partycji, a mianowicie interwałowe przechowywanie wartości w klastrach partycji:

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Pierwszy interwał}, underbrace{7, 8}_{Drugi interwał}, 10}}\ downarrow{ Kompresja} \ pi(X) = {{podkreślenie{$, 1, 5}_{pierwszy~interwał}, podkreślenie{7, 8}_{drugi~interwał}, 10}}$$display$$

Dzięki tej metodzie udało się zmniejszyć zużycie pamięci podczas działania algorytmu TANE od 1 do 25%. Algorytm TANE jest klasycznym algorytmem wyszukiwania przepisów federalnych, w swojej pracy wykorzystuje partycje. W ramach praktyki wybrano algorytm TANE, gdyż znacznie łatwiej było w nim zaimplementować przechowywanie interwałowe niż np. w PYRO, aby ocenić, czy zaproponowane podejście działa. Uzyskane wyniki przedstawiono na poniższym rysunku. Oś X jest logarytmiczna.

Konferencja ADBIS-2019

Na podstawie wyników badania we wrześniu 2019 roku opublikowałem artykuł Inteligentne buforowanie dla wydajnego wykrywania zależności funkcjonalnych na 23. Europejskiej Konferencji na temat Postępów w Bazach Danych i Systemach Informacyjnych (ADBIS-2019). Podczas prezentacji prace zostały docenione przez Bernharda Thalheima, znaczącą osobę w dziedzinie baz danych. Wyniki badań stały się podstawą mojej pracy magisterskiej z matematyki i mechaniki na Uniwersytecie Państwowym w Petersburgu, podczas której oba zaproponowane podejścia (buforowanie i kompresja) zostały zaimplementowane w obu algorytmach: TANE i PYRO. Ponadto wyniki wykazały, że zaproponowane podejścia są uniwersalne, gdyż w obu algorytmach, przy obu podejściach, zaobserwowano znaczne zmniejszenie zużycia pamięci, a także znaczne skrócenie czasu działania algorytmów.

Źródło: www.habr.com