Wyszukiwanie zależności funkcyjnych w danych znajduje zastosowanie w różnych obszarach analizy danych: zarządzanie bazami danych, czyszczenie danych, inżynieria wsteczna baz danych oraz eksploracja danych. O samych zależnościach już publikowaliśmy Anastasii Birillo i Nikity Bobrowa. Tym razem Anastasia — absolwentka Computer Science Center tego roku — dzieli się rozwojem tej pracy w ramach Badań Naukowych, które obroniła w centrum.
Wybór zadania
Podczas nauki w CS Center zaczęłam zgłębiać temat baz danych, a dokładniej, wyszukiwania zależności funkcyjnych i różnicowych. Temat ten był związany z tematyką mojej pracy dyplomowej na uniwersytecie, więc w trakcie pracy nad nią zaczęłam czytać artykuły dotyczące różnych zależności w bazach danych. Napisałam przegląd tej dziedziny — jeden z moich pierwszych w języku angielskim i złożyłam go na konferencję SEIM-2017. Byłam bardzo zadowolona, kiedy dowiedziałam się, że został przyjęty, i postanowiłam jeszcze bardziej zagłębić się w temat. Sama koncepcja nie jest nowa — zaczęto ją stosować już w latach 90., ale nadal znajduje zastosowanie w wielu dziedzinach.
W drugim semestrze nauki w centrum rozpoczęłam projekt badawczy mający na celu poprawę algorytmów wyszukiwania zależności funkcyjnych. Pracowałam nad nim razem z doktorantem z SPbGU Nikitą Bobrowem w JetBrains Research.
Obliczeniowa złożoność wyszukiwania zależności funkcyjnych
Głównym problemem jest obliczeniowa złożoność. Liczba możliwych minimalnych i nietrywialnych zależności jest ograniczona z góry wartością 
, gdzie 
— liczba atrybutów tabeli. Czas pracy algorytmów zależy nie tylko od liczby atrybutów, ale również od liczby wierszy. W latach 90. algorytmy do wyszukiwania zależności funkcyjnych na zwykłym komputerze stacjonarnym mogły przetwarzać zbiory danych zawierające do 20 atrybutów i dziesiątki tysięcy wierszy, przez kilka godzin. Nowoczesne algorytmy, działające na wielordzeniowych procesorach, odkrywają zależności dla zbiorów danych składających się ze setek atrybutów (do 200) i setek tysięcy wierszy, w zbliżonym czasie. Niemniej jednak to nie wystarcza: czas ten jest nieakceptowalny dla większości rzeczywistych aplikacji. Dlatego opracowywaliśmy podejścia do przyspieszenia istniejących algorytmów.
Schematy pamięci podręcznej dla przecięcia partycji
W pierwszej części pracy opracowaliśmy schematy buforowania dla klasy algorytmów wykorzystujących metodę przecięcia partycji. Partycja dla atrybutu reprezentuje zestaw list, gdzie każda lista zawiera numery wierszy o identycznych wartościach dla danego atrybutu. Każda taka lista nazywana jest klastrem. Wiele nowoczesnych algorytmów używa partycji do określenia, czy zależność jest utrzymywana, kierując się zasadą: Zależność 
jest utrzymywana, jeśli 
. Tutaj 
oznaczana jest partycja i używa się pojęcia wielkości partycji — liczby klastrów w niej. Algorytmy, które wykorzystują partycje, w przypadku naruszenia zależności dodają dodatkowe atrybuty do lewej strony zależności, po czym przeliczają ją, wykonując operację przecięcia partycji. Taka operacja w artykułach nazywana jest specjalizacją. Zauważyliśmy jednak, że partycje dla zależności, które będą utrzymywane tylko po kilku rundach specjalizacji, mogą być aktywnie ponownie wykorzystywane, 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 Jina, a także naszą metrykę, którą nazwaliśmy Odwrotna Entropia. Jest to nieznaczna modyfikacja entropii Shannona i rośnie w miarę wzrostu unikalności zbioru danych. Proponowana heurystyka wygląda następująco:
Tutaj 
— stopień unikalności niedawno obliczonej partycji 
, a 
jest miarą unikalności median dla poszczególnych atrybutów. Wszystkie trzy metryki opisane powyżej zostały przetestowane jako miary unikalności. Warto również zauważyć, że w heurystyce obecne są dwa modyfikatory. Pierwszy wskazuje, jak bardzo bieżąca partycja jest zbliżona do klucza podstawowego i pozwala w większym stopniu buforować te partycje, które są dalekie od potencjalnego klucza. Drugi modyfikator pozwala śledzić zajętość pamięci podręcznej, co z kolei stymuluje dodawanie większej liczby partycji do pamięci podręcznej w przypadku dostępnego miejsca. Sukces w rozwiązaniu tego problemu pozwolił przyspieszyć algorytm PYRO o 10-40% w zależności od zestawu danych. Warto zauważyć, że algorytm PYRO jest najbardziej skuteczny w tej dziedzinie.
Na poniższym rysunku można zobaczyć wyniki zastosowania proponowanej heurystyki w porównaniu z podstawowym podejściem do buforowania opartym na rzutowaniu monety. Oś X jest logarithmiczna.
Alternatywny sposób przechowywania partycji
Następnie zaproponowaliśmy alternatywny sposób przechowywania partycji. Partycje stanowią zestaw klastrów, w których przechowywane są numery krotek o tych samych wartościach dla określonych atrybutów. Te klastry mogą zawierać długie sekwencje numerów krotek, na przykład, jeśli w tabeli dane są uporządkowane. Dlatego zaproponowaliśmy schemat kompresji do przechowywania partycji, a mianowicie przechowywanie przedziałów wartości w klastrach partycji:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Pierwszy~przedział}, underbrace{7, 8}_{Drugi~przedział}, 10}}\ downarrow{Kompresja}\ pi(X) = {{underbrace{$, 1, 5}_{Pierwszy~przedział}, underbrace{7, 8}_{Drugi~przedział}, 10}}$$display$$
Ta metoda pozwoliła na zmniejszenie zużycia pamięci podczas działania algorytmu TANE od 1 do 25%. Algorytm TANE to klasyczny algorytm do wyszukiwania FZ, który korzysta z partycji w trakcie swojej pracy. W ramach praktyki wybrano właśnie algorytm TANE, ponieważ wprowadzenie przechowywania przedziałów było znacznie prostsze niż na przykład w PYRO, aby ocenić, czy proponowane podejście działa. Uzyskane wyniki przedstawiono na poniższym rysunku. Oś X jest logarithmiczna.
Konferencja ADBIS-2019
Na podstawie badań w wrześniu 2019 roku wystąpiłam ze swoją pracą na konferencji 23. Europejskiej Konferencji na temat Postępów w Bazach Danych i Systemach Informacyjnych (ADBIS-2019). W trakcie wystąpienia swoją pracę podkreślił Bernhard Thalheim, znacząca postać w dziedzinie baz danych. Wyniki badań stały się fundamentem mojej pracy magisterskiej na Wydziale Matematyczno-Fizycznym Uniwersytetu Petersburskiego, podczas której oba zaproponowane podejścia (cache'owanie i kompresja) zostały wdrożone w obu algorytmach: TANE i PYRO. Wyniki pokazały, że zaproponowane podejścia są uniwersalne, ponieważ w obu algorytmach przy obu metodach zaobserwowano znaczne zmniejszenie zużycia pamięci oraz znaczące skrócenie czasu działania algorytmów.
Źródło: habr.com
