Wprowadzenie do zależności funkcyjnych

W tym artykule omówimy zależności funkcyjne w bazach danych — czym one są, gdzie są stosowane i jakie algorytmy istnieją do ich wykrywania.

Zależności funkcyjne rozważymy w kontekście relacyjnych baz danych. Mówiąc w dużym uproszczeniu, w takich bazach danych informacje są przechowywane w postaci tabel. Następnie użyjemy pojęć przybliżonych, które w rygorystycznej teorii relacyjnej nie są wzajemnie zamienne: samą tabelę nazywamy relacją, kolumny — atrybutami (ich zbiór to schemat relacji), a zestaw wartości wiersza w podzbiorze atrybutów — krotką.

Na przykład, w powyższej tabeli, (Benson, M, M organ) jest krotką dla atrybutów (Pacjent, Płeć, Doktor).
Bardziej formalnie zapisywane jest to w następujący sposób: [Pacjent, Płeć, Doktor] = (Benson, M, M organ).
Teraz możemy wprowadzić pojęcie zależności funkcyjnej (ZF):

Definicja 1. Relacja R spełnia ZF X → Y (gdzie X, Y ⊆ R) wtedy i tylko wtedy, gdy dla dowolnych krotek , ∈ R zachodzi: jeśli [X] = [X], to [Y ] = [Y ]. W takim przypadku mówimy, że X (determinant, czyli określający zbiór atrybutów) funkcyjnie określa Y (zbiór zależny).

Innymi słowy, obecność ZF X → Y oznacza, że jeśli mamy dwie krotki w R i są one zgodne pod względem atrybutów X, to będą one także zgodne pod względem atrybutów Y.
A teraz po kolei. Rozważmy atrybuty Pacjent i Płeć dla których chcemy sprawdzić, czy istnieją między nimi zależności, czy nie. Dla takiego zbioru atrybutów mogą istnieć następujące zależności:

1. Pacjent → Płeć
2. Płeć → Pacjent

Zgodnie z powyższą definicją, aby pierwsza zależność była utrzymana, każdemu unikalnemu wartości kolumny Pacjent musi odpowiadać tylko jedna wartość kolumny Płeć. I dla przykładowej tabeli rzeczywiście tak jest. Jednak w odwrotną stronę to nie działa, to znaczy druga zależność nie jest spełniona, a atrybut Płeć nie jest determinantem dla Pacjenta.Podobnie, biorąc zależność Doktor → Pacjent, można zauważyć, że jest ona naruszona, ponieważ wartość Robin dla tego atrybutu ma kilka różnych wartości — Ellis i Graham.

W ten sposób funkcjonalne zależności pozwalają określić istniejące powiązania między zbiorami atrybutów tabeli. Od teraz będziemy rozważać najbardziej interesujące powiązania, a konkretnie takie X → Y, które są:

• nietrywialne, tzn. prawa strona zależności nie jest podzbiorem lewej (Y ̸⊆ X);
• minimalne, tzn. nie istnieje taka zależność Z → Y, nawet bez optymalizacji pod takie zadania, wygrywa i na obcym terenie: Z ⊂ X.

Rozważane do tej pory zależności były restrykcyjne, tzn. nie przewidywały żadnych naruszeń w tabeli, ale oprócz nich istnieją również takie, które dopuszczają pewną niespójność między wartościami krotek. Takie zależności się wydziela do osobnej klasy, nazywa przybliżonymi i pozwala się im na naruszanie w określonej liczbie krotek. Liczba ta jest regulowana wskaźnikiem maksymalnego błędu emax. Na przykład, udział błędu = 0.01 może oznaczać, że zależność może być naruszona w 1% istniejących krotek w rozważanym zbiorze atrybutów. To znaczy, dla 1000 rekordów maksymalnie 10 krotek może naruszać FZ. My natomiast będziemy rozważać nieco inną metrykę, opartą na parze różnych wartościach porównywanych krotek. Dla zależności X → Y na relacji r jest to liczone w ten sposób:

Obliczmy błąd dla Doktor → Pacjent z powyższego przykładu. Mamy dwie krotki, których wartości różnią się w atrybucie Pacjent, ale zgadzają się na Lekarz: [Lekarz, Pacjent] = (Robin, Ellis) i [Lekarz, Pacjent] = (Robin, Graham). Zgodnie z definicją błędu, musimy uwzględnić wszystkie konfliktujące pary, więc będzie ich dwie: (, ) oraz jej inwersję (, ). Podstawmy do wzoru i otrzymamy:

A teraz spróbujmy odpowiedzieć na pytanie: „Po co to wszystko?”. W rzeczywistości istnieją różne rodzaje FZ. Pierwszy typ to takie zależności, które są definiowane przez administratora na etapie projektowania bazy danych. Zazwyczaj jest ich niewiele, są restrykcyjne, a ich głównym zastosowaniem jest normalizacja danych i projektowanie schematów relacji.

Drugi typ to zależności reprezentujące „ukryte” dane i wcześniej nieznane powiązania między atrybutami. Oznacza to, że o takich zależnościach nie myślano w momencie projektowania i znajdują je dopiero w istniejącym zbiorze danych, aby następnie na podstawie wielu ujawnionych wzorców wyciągnąć jakieś wnioski o przechowywanych informacjach. To dokładnie z takimi zależnościami pracujemy. Zajmuje się nimi cała dziedzina eksploracji danych z różnymi technikami wyszukiwania i zbudowanymi na ich podstawie algorytmami. Przyjrzyjmy się, jak mogą być przydatne znalezione funkcjonalne zależności (dokładne lub przybliżone) w danych.

Dziś wśród podstawowych obszarów zastosowania zależności wyróżnia się czyszczenie danych. Polega ono na opracowaniu procesów identyfikacji „brudnych danych” z następową ich korekcją. Jaskrawymi przykładami „brudnych danych” są duplikaty, błędy w danych lub literówki, brakujące wartości, przestarzałe dane, zbędne spacje i tym podobne.

Przykład błędu w danych:

Przykład duplikatów w danych:

Na przykład mamy tabelę i zestaw reguł, które powinny być spełnione. Czystość danych w tym przypadku zakłada zmianę danych w taki sposób, aby reguły były poprawne. Przy tym liczba modyfikacji powinna być minimalna (dla tej procedury istnieją własne algorytmy, na których nie będziemy się koncentrować w tym artykule). Poniżej przedstawiono przykład takiej transformacji danych. Po lewej stronie odniesienie początkowe, w którym wyraźnie nie spełniają się niezbędne reguły (na czerwono wyróżniono przykład naruszenia jednej z reguł). Po prawej stronie przedstawiono zaktualizowane odniesienie, w którym zielone komórki pokazują zmienione wartości. Po przeprowadzeniu takiej procedury niezbędne zależności zaczęły być spełniane.

Inną popularną dziedziną zastosowania jest projektowanie baz danych. Warto przypomnieć o normalnych formach i normalizacji. Normalizacja to proces dostosowywania relacji do pewnego zestawu wymagań, z których każde jest definiowane przez normalną formę na swój sposób. Nie będziemy szczegółowo omawiać wymagań różnych normalnych form (to można znaleźć w każdej książce na temat baz danych dla początkujących), a jedynie zauważamy, że każda z nich w swój sposób wykorzystuje koncepcję zależności funkcyjnych. Zależności funkcyjne są w istocie ograniczeniami integralności, które uwzględnia się podczas projektowania bazy danych (w kontekście tego zadania zależności funkcyjne czasami nazywane są superkluczami).

Rozważmy ich zastosowanie dla czterech normalnych form na obrazku poniżej. Przypomnijmy, że normalna forma Boyce'a-Codda jest bardziej rygorystyczna niż trzecia forma, ale jednocześnie mniej rygorystyczna niż czwarta. Na razie nie rozważamy czwartej formy, ponieważ jej zrozumienie wymaga znajomości wielowartościowych zależności, które nie są przedmiotem tego artykułu.

Inną dziedziną, w której zależności znalazły swoje zastosowanie, jest redukcja wymiarowości przestrzeni cech w takich zadaniach jak budowanie naiwnego klasyfikatora bayesowskiego, wybieranie istotnych cech oraz reparametryzacja modelu regresji. W oryginalnych artykułach problem ten nazywa się określaniem zbędnych cech (feature redundancy) i istotnych cech (feature relevancy) [5, 6], a rozwiązywany jest z aktywnym wykorzystaniem koncepcji baz danych. Pojawienie się takich prac pozwala nam mówić o rosnącym zapotrzebowaniu na rozwiązania, które łączą bazę danych, analitykę i realizację wymienionych powyżej problemów optymalizacji w jedno narzędzie [7, 8, 9].

Dla wyszukiwania zależności funkcyjnych w zbiorze danych istnieje wiele algorytmów (zarówno nowoczesnych, jak i nieco starszych). Takie algorytmy można podzielić na trzy grupy:

• Algorytmy wykorzystujące przeszukiwanie sieci algebraicznych (Lattice traversal algorithms)
• Algorytmy oparte na wyszukiwaniu zgodnych wartości (Difference- and agree-set algorithms)
• Algorytmy oparte na porównaniach parowych (Dependency induction algorithms)

Krótki opis każdego typu algorytmu przedstawiony jest w tabeli poniżej:


Więcej informacji na temat tej klasyfikacji można znaleźć [4]. Poniżej przedstawiono przykłady algorytmów dla każdego z typów:

Obecnie pojawiają się nowe algorytmy, które łączą w sobie kilka podejść do poszukiwania funkcjonalnych zależności. Przykładami takich algorytmów są Pyro [2] i HyFD [3]. Analiza ich działania jest przewidziana w kolejnych artykułach tego cyklu. W tym artykule omówimy jedynie podstawowe pojęcia i lemę, które są niezbędne do zrozumienia technik wykrywania zależności.

Zacznijmy od prostych pojęć — difference- i agree-set, stosowanych w drugim typie algorytmów. Difference-set to zbiór krotek, które różnią się wartościami, natomiast agree-set to krotki, które mają wartości zgodne. Należy zaznaczyć, że w tym przypadku rozważamy tylko lewą część zależności.

Kolejnym ważnym pojęciem, które było wspomniane powyżej, jest algebraiczna kratka. Ponieważ wiele współczesnych algorytmów operuje na tym pojęciu, musimy mieć pojęcie o tym, czym ono jest.

Aby wprowadzić pojęcie kratki, potrzebne jest określenie zbioru częściowo uporządkowanego (lub partially ordered set, w skrócie — poset).

Definicja 2. Mówi się, że zbiór S jest częściowo uporządkowany w relacji binarnej ⩽, jeśli dla wszystkich a, b, c ∈ S spełnione są następujące właściwości:

1. Refleksyjność, czyli a ⩽ a
2. Antysymetryczność, czyli jeśli a ⩽ b i b ⩽ a, to a = b
3. Transytywność, czyli dla a ⩽ b i b ⩽ c zachodzi a ⩽ c

Taka relacja nazywana jest relacją (niestrictznego) porządku częściowego, a sam zbiór — zbiorem częściowo uporządkowanym. Formalne oznaczenie: ⟨S, ⩽⟩.

Jako najprostszy przykład częściowo uporządkowanego zbioru można przyjąć zbiór wszystkich liczb naturalnych N z tradycyjną relacją porządku ⩽. Niezbyt trudno sprawdzić, że wszystkie niezbędne aksjomaty są spełnione.

Bardziej złożony przykład. Rozważmy zbiór wszystkich podzbiorów {1, 2, 3}, uporządkowany relacją zawierania ⊆. Rzeczywiście, ta relacja spełnia wszystkie warunki porządku częściowego, dlatego ⟨P ({1, 2, 3}), ⊆⟩ — to zbiór częściowo uporządkowany. Na poniższym rysunku przedstawiona jest struktura tego zbioru: jeśli z jednego elementu można dotrzeć do drugiego elementu za pomocą strzałek, to znajdują się one w relacji porządku.

Potrzebujemy jeszcze dwóch prostych definicji z zakresu matematyki — supremum i infimum.

Definicja 3. Niech ⟨S, ⩽⟩ — częściowo uporządkowany zbiór, A ⊆ S. Górna granica A to taki element u ∈ S, że ∀x ∈ S: x ⩽ u. Niech U — zbiór wszystkich górnych granic S. Jeśli w U istnieje najmniejszy element, wtedy nazywa się on supremum i oznacza się jako sup A.

Analogicznie wprowadza się pojęcie dokładnej dolnej granicy.

Definicja 4. Niech ⟨S, ⩽⟩ — częściowo uporządkowany zbiór, A ⊆ S. Dolna granica A to taki element l ∈ S, że ∀x ∈ S: l ⩽ x. Niech L — zbiór wszystkich dolnych granic S. Jeśli w L istnieje największy element, wtedy nazywa się on infimum i oznacza się jako inf A.

Rozważmy jako przykład powyższy częściowo uporządkowany zbiór ⟨P ({1, 2, 3}), ⊆⟩ i znajdźmy w nim supremum oraz infimum:

Teraz możemy sformułować definicję struktury algebraicznej.

Definicja 5. Niech ⟨P, ⩽⟩ — częściowo uporządkowany zbiór, taki że każde dwuelementowe podzbiór ma dokładne górne i dolne granice. Wtedy P nazywa się strukturą algebraiczną. Przy czym sup{x, y} zapisuje się jako x ∨ y, a inf {x, y} — jako x ∧ y.

Sprawdźmy, że nasz przykład roboczy ⟨P ({1, 2, 3}), ⊆⟩ jest strukturą. Rzeczywiście, dla każdego a, b ∈ P ({1, 2, 3}), a∨b = a∪b, a a∧b = a∩b. Na przykład, rozważmy zbiory {1, 2} i {1, 3} i znajdźmy ich infimum oraz supremum. Gdy je przetniemy, otrzymamy zbiór {1}, który będzie infimum. Supremum otrzymamy ich połączeniem — {1, 2, 3}.

W algorytmach wykrywania FZ przestrzeń przeszukiwania często przedstawia się w formie struktury, gdzie zbiory z jednolitym elementem (czytaj pierwszy poziom struktury, gdzie lewa część zależności składa się z jednego atrybutu) stanowią każdy atrybut pierwotnej relacji.
Na początku rozważane są zależności typu ∅ → Pojedynczy atrybut. Ten krok pozwala określić, które atrybuty są kluczami podstawowymi (dla takich atrybutów nie ma wyznaczników, a zatem lewa część jest pusta). Następnie takie algorytmy poruszają się w górę struktury. Należy przy tym zauważyć, że struktury można przeszukiwać nie całość, co oznacza, że jeśli na wejściu przekażemy pożądany maksymalny rozmiar lewej części, to algorytm nie będzie szedł dalej poza poziom o takim rozmiarze.

Na poniższym rysunku pokazano, jak można wykorzystać algebraiczną siatkę w problemie wyszukiwania FZ. Tutaj każda krawędź (X, XY) reprezentuje zależność X → Y. Na przykład przeszliśmy pierwszy poziom i wiemy, że utrzymywana jest zależność A → B (przedstawmy to zieloną linią między wierzchołkami A i B). Oznacza to, że dalej, gdy będziemy poruszać się w górę siatki, nie musimy sprawdzać zależności A, C → B, ponieważ nie będzie ona już minimalna. Podobnie nie sprawdzalibyśmy jej, gdyby utrzymywana była zależność C → B.

Ponadto, jak zwykle, wszystkie nowoczesne algorytmy wyszukiwania FZ korzystają z takiej struktury danych, jak partycja (w oryginale — stripped partition [1]). Formalna definicja partycji wygląda następująco:

Definicja 6. Niech X ⊆ R — zbiór atrybutów dla relacji r. Klaster jest zbiorem indeksów krotek z r, które mają tę samą wartość dla X, to znaczy c(t) = {i|ti[X] = t[X]}. Particja jest zbiorem klastrów, wykluczając klastry jednostkowej długości:

Mówiąc prosto, partycja dla atrybutu X jest zbiorem list, gdzie każda lista zawiera numery wierszy o tych samych wartościach dla X. W nowoczesnej literaturze struktura przedstawiająca partycje nazywa się position list index (PLI). Klastry jednostkowej długości są wykluczane w celu kompresji PLI, ponieważ są to klastry zawierające tylko numer wpisu o unikalnej wartości, którą zawsze będzie łatwo ustalić.

Rozważmy przykład. Wróćmy do tej samej tabeli pacjentów i stwórzmy partycje dla kolumn Pacjent i Płeć (po lewej stronie pojawiła się nowa kolumna, w której zaznaczone są numery wierszy tabeli):

Przy tym, zgodnie z definicją, partycja dla kolumny Pacjent w rzeczywistości będzie pusta, ponieważ klastry jednostkowej długości są wykluczane z partycji.

Partycje można uzyskiwać według kilku atrybutów. I w tym celu istnieją dwie drogi: przechodząc przez tabelę, zbudować partycję od razu dla wszystkich niezbędnych atrybutów, lub zbudować ją za pomocą operacji przecięcia partycji według podzbioru atrybutów. Algorytmy wyszukiwania FZ korzystają z drugiej opcji.

Mówiąc prosto, aby na przykład uzyskać partycję dla kolumn ABC, można wziąć partycje dla AC i B (lub dowolny inny zestaw niepokrywających się podzbiorów) i ich przecięcie. Operacja przecięcia dwóch partycji wyodrębnia klastry o największej długości, wspólne dla obu partycji.

Rozważmy przykład:

W pierwszym przypadku otrzymaliśmy pustą partycję. Jeśli przyjrzymy się tabeli, to rzeczywiście nie ma tam identycznych wartości dla dwóch atrybutów. Jeśli jednak nieco zmodyfikujemy tabelę (przypadek po prawej stronie), otrzymamy już niepustą przecięcie. Przy tym wiersze 1 i 2 rzeczywiście zawierają identyczne wartości dla atrybutów. Płeć i Doktor.

Następnie będziemy potrzebować takiego pojęcia, jak rozmiar partycji. Formalnie:

Mówiąc prościej, rozmiar partycji to liczba klastrów wchodzących w skład partycji (pamiętamy, że pojedyncze klastry nie wchodzą do partycji!):

Teraz możemy określić jedną z kluczowych lem, która dla zadanych partycji pozwala ustalić, czy zależność jest utrzymywana, czy nie:

Lema 1. Zależność A, B → C jest utrzymywana, jeśli i tylko jeśli

Zgodnie z lemą, aby ustalić, czy zależność jest utrzymywana, należy wykonać cztery kroki:

1. Obliczyć partycję dla lewej strony zależności
2. Obliczyć partycję dla prawej strony zależności
3. Obliczyć iloczyn pierwszego i drugiego kroku
4. Porównać rozmiary partycji uzyskanych w pierwszym i trzecim kroku

Poniżej znajduje się przykład sprawdzania, czy zależność jest utrzymywana według danej lem:

W tym artykule omówiliśmy takie pojęcia, jak zależność funkcjonalna, przybliżona zależność funkcjonalna, a także gdzie są one stosowane i jakie algorytmy wyszukiwania FZ istnieją. Przyjrzeliśmy się również podstawowym, ale ważnym pojęciom, które są aktywnie wykorzystywane w nowoczesnych algorytmach wyszukiwania FZ.

Odnośniki do literatury:

1. Huhtala Y. i in. TANE: Efektywny algorytm odkrywania zależności funkcjonalnych i przybliżonych // The computer journal. – 1999. – T. 42. – nr 2. – s. 100-111.
2. Kruse S., Naumann F. Efektywne odkrywanie przybliżonych zależności // Proceedings of the VLDB Endowment. – 2018. – T. 11. – nr 7. – s. 759-772.
3. Papenbrock T., Naumann F. Hybrydowe podejście do odkrywania zależności funkcjonalnych // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 821-833.
4. Papenbrock T. i in. Odkrywanie zależności funkcjonalnych: Eksperymentalna ocena siedmiu algorytmów // Proceedings of the VLDB Endowment. – 2015. – T. 8. – nr 10. – s. 1082-1093.
5. Kumar A. i in. Dołączyć czy nie dołączyć?: Przemyślenia na temat dołączeń przed wyborem cech // Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – s. 19-34.
6. Abo Khamis M. et al. Uczenie w bazie danych z wykorzystaniem rzadkich tensorów // Materiały 37. Sympozjum ACM SIGMOD-SIGACT-SIGAI dotyczącego zasad systemów baz danych. – ACM, 2018. – S. 325-340.
7. Hellerstein J. M. et al. Biblioteka analityczna MADlib: czyli umiejętności MAD, SQL // Materiały Fundacji VLDB. – 2012. – T. 5. – nr 12. – S. 1700-1711.
8. Qin C., Rusu F. Spekulacyjne przybliżenia dla optymalizacji gradientu w teraskali rozproszonym // Materiały Czwartej Warsztatu na temat analityki danych w chmurze. – ACM, 2015. – S. 1.
9. Meng X. et al. Mllib: uczenie maszynowe w apache spark // Czasopismo Badań nad Uczeniem Maszynowym. – 2016. – T. 17. – nr 1. – S. 1235-1241.

Autorzy artykułu: Anastazja Birillo, badacz w JetBrains Research, studentka centrum CS i Nikita Bobrow, badacz w JetBrains Research

Źródło: habr.com