Wprowadzenie do zależności funkcjonalnych

W tym artykule porozmawiamy o zależnościach funkcjonalnych w bazach danych – czym są, gdzie są używane i jakie istnieją algorytmy, aby je znaleźć.

Zależności funkcjonalne rozważymy w kontekście relacyjnych baz danych. Mówiąc najprościej, w takich bazach informacje przechowywane są w formie tabel. Następnie używamy pojęć przybliżonych, które w ścisłej teorii relacji nie są wymienne: samą tabelę nazwiemy relacją, kolumny – atrybutami (ich zbiór – schematem relacji), a zbiór wartości wierszy na podzbiorze atrybutów - krotka.

Na przykład w powyższej tabeli (Benson, M, M, organy) jest krotką atrybutów (Pacjent, Paweł, Doktor).
Bardziej formalnie, jest to napisane w następujący sposób: [Pacjent, płeć, lekarz] = (Benson, M, M, organy).
Teraz możemy wprowadzić koncepcję zależności funkcjonalnej (FD):

Definicja 1. Relacja R spełnia prawo federalne X → Y (gdzie X, Y ⊆ R) wtedy i tylko wtedy, gdy dla dowolnych krotek , ∈ R zachodzi: jeśli [X] = [X], zatem [Y] = [Y]. W tym przypadku mówimy, że X (wyznacznik, czyli zbiór definiujący atrybutów) funkcjonalnie determinuje Y (zbiór zależny).

Innymi słowy, obecność prawa federalnego X → Y oznacza, że ​​jeśli mamy dwie krotki R i pasują do siebie pod względem atrybutów X, to będą one zbieżne pod względem atrybutów Y.
A teraz po kolei. Spójrzmy na atrybuty Pacjent и Płeć dla którego chcemy dowiedzieć się, czy istnieją między nimi zależności, czy nie. Dla takiego zestawu atrybutów mogą istnieć następujące zależności:

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

Jak zdefiniowano powyżej, aby utrzymać pierwszą zależność, każda unikalna wartość kolumny Pacjent musi pasować tylko jedna wartość kolumny Płeć. I w przypadku przykładowej tabeli rzeczywiście tak jest. Nie działa to jednak w drugą stronę, czyli nie jest spełniona druga zależność i atrybut Płeć nie jest wyznacznikiem Pacjent. Podobnie, jeśli weźmiemy zależność Lekarz → Pacjent, widać, że zostało to naruszone, ponieważ wartość Rudzik ten atrybut ma kilka różnych znaczeń - Ellisa i Grahama.

Zależności funkcjonalne pozwalają zatem określić istniejące zależności pomiędzy zbiorami atrybutów tabeli. Od tego momentu będziemy rozważać najciekawsze połączenia, a raczej takie X → Yczym oni są:

• nietrywialne, to znaczy prawa strona zależności nie jest podzbiorem lewej (Y ̸⊆ X);
• minimalne, to znaczy nie ma takiej zależności Z → YŻe Z ⊂X.

Zależności rozważane do tego momentu były ścisłe, to znaczy nie przewidywały żadnych naruszeń na stole, ale oprócz nich są też takie, które dopuszczają pewną niespójność między wartościami krotek. Zależności takie umieszczane są w osobnej klasie zwanej przybliżonymi i mogą być naruszane przez określoną liczbę krotek. Kwota ta jest regulowana przez maksymalny wskaźnik błędu emax. Na przykład poziom błędów = 0.01 może oznaczać, że zależność może zostać naruszona przez 1% dostępnych krotek na rozpatrywanym zbiorze atrybutów. Oznacza to, że w przypadku 1000 rekordów maksymalnie 10 krotek może naruszać prawo federalne. Rozważymy nieco inną metrykę, opartą na parami różnych wartości porównywanych krotek. Na uzależnienie X → Y na nastawienie r uważa się to za:

Obliczmy błąd dla Lekarz → Pacjent z powyższego przykładu. Mamy dwie krotki, których wartości różnią się w zależności od atrybutu Pacjent, ale zbiegają się Lekarz: [Lekarz, pacjent] = (Robin, Ellis) I [Lekarz, pacjent] = (Robin, Graham). Idąc za definicją błędu, musimy wziąć pod uwagę wszystkie pary sprzeczne, czyli będą ich dwie: (, ) i jego inwersja (, ). Podstawiamy to do wzoru i otrzymujemy:

Spróbujmy teraz odpowiedzieć na pytanie: „Po co to wszystko?” W rzeczywistości przepisy federalne są inne. Pierwszy typ to te zależności, które ustala administrator na etapie projektowania bazy danych. Zwykle jest ich niewiele, są rygorystyczne, a głównym zastosowaniem jest normalizacja danych i projektowanie schematów relacyjnych.

Drugi typ to zależności, które reprezentują „ukryte” dane i nieznane wcześniej relacje pomiędzy atrybutami. Oznacza to, że takie zależności nie były brane pod uwagę w momencie projektowania i zostały znalezione dla istniejącego zbioru danych, dzięki czemu później, w oparciu o wiele zidentyfikowanych przepisów federalnych, można było wyciągnąć jakiekolwiek wnioski na temat przechowywanych informacji. Właśnie z tymi zależnościami pracujemy. Zajmuje się nimi cała dziedzina eksploracji danych z różnymi technikami wyszukiwania i zbudowanymi na ich podstawie algorytmami. Zastanówmy się, w jaki sposób znalezione zależności funkcjonalne (dokładne lub przybliżone) w dowolnych danych mogą być przydatne.

Obecnie jednym z głównych zastosowań zależności jest czyszczenie danych. Polega na opracowaniu procesów identyfikacji „brudnych danych”, a następnie ich poprawienia. Wybitnymi przykładami „brudnych danych” są duplikaty, błędy lub literówki w danych, brakujące wartości, nieaktualne dane, dodatkowe spacje i tym podobne.

Przykład błędu danych:

Przykład duplikatów w danych:

Mamy na przykład tabelę i zbiór przepisów federalnych, które należy wykonać. Czyszczenie danych w tym przypadku wiąże się ze zmianą danych, tak aby przepisy federalne stały się prawidłowe. W takim przypadku liczba modyfikacji powinna być minimalna (ta procedura ma swoje własne algorytmy, na których nie będziemy się skupiać w tym artykule). Poniżej przykład takiej transformacji danych. Po lewej stronie pierwotna relacja, w której oczywiście nie są spełnione niezbędne FL (na czerwono zaznaczono przykład naruszenia jednego z FL). Po prawej stronie znajduje się zaktualizowana relacja, w której zielone komórki pokazują zmienione wartości. Po tej procedurze zaczęto utrzymywać niezbędne zależności.

Innym popularnym zastosowaniem jest projektowanie baz danych. W tym miejscu warto przypomnieć formy normalne i normalizację. Normalizacja to proces doprowadzenia relacji do zgodności z pewnym zestawem wymagań, z których każdy jest na swój sposób zdefiniowany przez formę normalną. Nie będziemy opisywać wymagań różnych form normalnych (robi się to w dowolnej książce na kursie baz danych dla początkujących), ale zauważymy jedynie, że każda z nich na swój sposób wykorzystuje koncepcję zależności funkcjonalnych. W końcu klucze FL są z natury ograniczeniami integralności, które są brane pod uwagę podczas projektowania bazy danych (w kontekście tego zadania klucze FL są czasami nazywane superkluczami).

Rozważmy ich zastosowanie dla czterech postaci normalnych na poniższym obrazku. Przypomnijmy, że postać normalna Boyce’a-Codda jest bardziej rygorystyczna niż trzecia forma, ale mniej rygorystyczna niż czwarta. Tego drugiego na razie nie rozważamy, gdyż jego sformułowanie wymaga zrozumienia zależności wielowartościowych, które w tym artykule nie są dla nas interesujące.

Kolejnym obszarem, w którym zależności znalazły swoje zastosowanie, jest redukcja wymiarowości przestrzeni cech w zadaniach takich jak budowa naiwnego klasyfikatora Bayesa, identyfikacja istotnych cech czy reparametryzowanie modelu regresji. W oryginalnych artykułach zadanie to nosi nazwę wyznaczania relewantności i trafności cech [5, 6] i jest rozwiązywane przy aktywnym wykorzystaniu koncepcji baz danych. Wraz z pojawieniem się takich prac można powiedzieć, że dziś istnieje zapotrzebowanie na rozwiązania, które pozwalają połączyć bazę danych, analitykę i realizację powyższych problemów optymalizacyjnych w jedno narzędzie [7, 8, 9].

Istnieje wiele algorytmów (zarówno nowoczesnych, jak i mniej nowoczesnych) wyszukiwania przepisów federalnych w zbiorze danych.Algorytmy takie można podzielić na trzy grupy:

• Algorytmy wykorzystujące przechodzenie przez kraty algebraiczne (algorytmy przechodzenia przez kraty)
• Algorytmy oparte na poszukiwaniu uzgodnionych wartości (algorytmy różnicowe i uzgodnione)
• Algorytmy oparte na porównaniach parami (algorytmy indukcji zależności)

Krótki opis każdego typu algorytmu przedstawiono w poniższej tabeli:


Więcej na temat tej klasyfikacji można przeczytać w [4]. Poniżej znajdują się przykłady algorytmów dla każdego typu:

Obecnie pojawiają się nowe algorytmy, które łączą kilka podejść do znajdowania zależności funkcjonalnych. Przykładami takich algorytmów są Pyro [2] i HyFD [3]. Analizę ich prac można spodziewać się w kolejnych artykułach z tej serii. W tym artykule przeanalizujemy jedynie podstawowe pojęcia i lematy niezbędne do zrozumienia technik wykrywania zależności.

Zacznijmy od prostego zbioru różnic i zgodności, stosowanego w algorytmach drugiego typu. Zbiór różnicowy to zbiór krotek, które nie mają tych samych wartości, podczas gdy zbiór zgodny, przeciwnie, to krotki, które mają te same wartości. Warto zauważyć, że w tym przypadku rozważamy tylko lewą stronę zależności.

Inną ważną koncepcją, z którą spotkaliśmy się powyżej, jest sieć algebraiczna. Ponieważ wiele nowoczesnych algorytmów działa w oparciu o tę koncepcję, musimy mieć pojęcie, co to jest.

Aby wprowadzić pojęcie sieci, należy zdefiniować zbiór częściowo uporządkowany (lub zbiór częściowo uporządkowany, w skrócie poset).

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

1. Zwrotność, czyli a ⩽ a
2. Antysymetria, czyli jeśli a ⩽ b i b ⩽ a, to a = b
3. Przechodniość, czyli dla a ⩽ b i b ⩽ c wynika, że ​​a ⩽ c

Relację taką nazywamy (luźną) relacją porządku częściowego, a sam zbiór nazywamy zbiorem częściowo uporządkowanym. Notacja formalna: ⟨S, ⩽⟩.

Jako najprostszy przykład zbioru częściowo uporządkowanego możemy wziąć zbiór wszystkich liczb naturalnych N ze zwykłą relacją porządku ⩽. Łatwo sprawdzić, że wszystkie niezbędne aksjomaty są spełnione.

Bardziej wymowny przykład. Rozważmy zbiór wszystkich podzbiorów {1, 2, 3} uporządkowany według relacji włączenia ⊆. Rzeczywiście, relacja ta spełnia wszystkie warunki porządku częściowego, więc ⟨P ({1, 2, 3}), ⊆⟩ jest zbiorem częściowo uporządkowanym. Poniższy rysunek przedstawia strukturę tego zbioru: jeśli strzałkami można dojść do jednego elementu z innym elementem, to są one w relacji porządkowej.

Przydałyby nam się jeszcze dwie proste definicje z dziedziny matematyki – supremum i infimum.

Definicja 3. Niech ⟨S, ⩽⟩ będzie zbiorem częściowo uporządkowanym, A ⊆ S. Górną granicą A jest element u ∈ S taki, że ∀x ∈ S: x ⩽ u. Niech U będzie zbiorem wszystkich górnych granic S. Jeśli w U jest najmniejszy element, to nazywamy go supremum i oznaczamy sup A.

W podobny sposób wprowadzono koncepcję dokładnej dolnej granicy.

Definicja 4. Niech ⟨S, ⩽⟩ będzie zbiorem częściowo uporządkowanym, A ⊆ S. Dolna część A jest elementem l ∈ S takim, że ∀x ∈ S: l ⩽ x. Niech L będzie zbiorem wszystkich dolnych granic S. Jeżeli w L znajduje się największy element, to nazywamy go infimum i oznaczamy inf A.

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

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

Definicja 5. Niech ⟨P,⩽⟩ będzie zbiorem częściowo uporządkowanym, takim, że każdy dwuelementowy podzbiór ma górną i dolną granicę. Wtedy P nazywa się siecią algebraiczną. W tym przypadku sup{x, y} zapisuje się jako x ∨ y, a inf {x, y} jako x ∧ y.

Sprawdźmy, czy nasz przykład roboczy ⟨P ({1, 2, 3}), ⊆⟩ jest siecią. Rzeczywiście, dla dowolnego a, b ∈ P ({1, 2, 3}), a∨b = a∪b i a∧b = a∩b. Rozważmy na przykład zbiory {1, 2} i {1, 3} i znajdź ich dolną i górną część. Jeśli je przetniemy, otrzymamy zbiór {1}, który będzie końcem. Supremum otrzymujemy łącząc je - {1, 2, 3}.

W algorytmach identyfikacji problemów fizycznych przestrzeń poszukiwań jest często reprezentowana w postaci siatki, gdzie zbiory jednego elementu (czytaj pierwszy poziom siatki poszukiwań, gdzie lewa strona zależności składa się z jednego atrybutu) reprezentują każdy atrybut pierwotnej relacji.
Najpierw rozważamy zależności postaci ∅ → Pojedynczy atrybut. Ten krok pozwala określić, które atrybuty są kluczami podstawowymi (dla takich atrybutów nie ma wyznaczników, dlatego lewa strona jest pusta). Ponadto takie algorytmy poruszają się w górę wzdłuż sieci. Warto zaznaczyć, że nie można przejść całej sieci, czyli jeśli na wejście zostanie przekazany żądany maksymalny rozmiar lewej strony, to algorytm nie przejdzie dalej niż poziom o tym rozmiarze.

Poniższy rysunek pokazuje, jak można wykorzystać kratę algebraiczną w problemie znalezienia FZ. Tutaj każda krawędź (X, XY) reprezentuje zależność X → Y. Przykładowo, przeszliśmy pierwszy poziom i wiemy, że uzależnienie trwa A → B (wyświetlimy to jako zielone połączenie między wierzchołkami A и B). Oznacza to, że dalej, przesuwając się w górę siatki, możemy nie sprawdzić zależności A, C → B, bo nie będzie już minimalna. Podobnie nie sprawdzalibyśmy tego, gdyby zależność była zachowana C → B.

Ponadto z reguły wszystkie nowoczesne algorytmy wyszukiwania przepisów federalnych wykorzystują strukturę danych taką jak partycja (w oryginalnym źródle - partycja pozbawiona [1]). Formalna definicja partycji jest następująca:

Definicja 6. Niech X ⊆ R będzie zbiorem atrybutów relacji r. Klaster to zbiór indeksów krotek w r, które mają tę samą wartość dla X, to znaczy c(t) = {i|ti[X] = t[X]}. Partycja to zbiór skupień, z wyłączeniem skupień o jednostkowej długości:

Krótko mówiąc, partycja dla atrybutu X to zbiór list, gdzie każda lista zawiera numery linii z tymi samymi wartościami X. We współczesnej literaturze struktura reprezentująca partycje nazywana jest indeksem listy pozycji (PLI). Klastry o długości jednostkowej są wykluczane na potrzeby kompresji PLI, ponieważ są to klastry zawierające tylko numer rekordu z unikalną wartością, która zawsze będzie łatwa do zidentyfikowania.

Spójrzmy na przykład. Wróćmy do tej samej tabeli z pacjentami i zbudujmy przegrody dla kolumn Pacjent и Płeć (po lewej stronie pojawiła się nowa kolumna, w której zaznaczono numery wierszy tabeli):

Ponadto zgodnie z definicją przegroda dla kolumny Pacjent będzie w rzeczywistości pusty, ponieważ pojedyncze klastry są wykluczone z partycji.

Partycje można uzyskać według kilku atrybutów. Można to zrobić na dwa sposoby: przeglądając tabelę, zbuduj partycję, używając jednocześnie wszystkich niezbędnych atrybutów, lub zbuduj ją, korzystając z operacji przecięcia partycji, używając podzbioru atrybutów. Algorytmy wyszukiwania prawa federalnego korzystają z drugiej opcji.

W prostych słowach, aby na przykład uzyskać partycję według kolumn ABC, możesz wziąć partycje AC и B (lub dowolny inny zbiór rozłącznych podzbiorów) i przecinają je ze sobą. Operacja przecięcia dwóch przegród wybiera skupienia o największej długości, które są wspólne dla obu przegród.

Spójrzmy na przykład:

W pierwszym przypadku otrzymaliśmy pustą partycję. Jeśli przyjrzysz się uważnie tabeli, rzeczywiście nie ma identycznych wartości dla tych dwóch atrybutów. Jeśli lekko zmodyfikujemy tabelę (przypadek po prawej), otrzymamy już niepuste przecięcie. Co więcej, linie 1 i 2 faktycznie zawierają te same wartości atrybutów Płeć и Lekarz.

Następnie będziemy potrzebować takiej koncepcji, jak rozmiar partycji. Formalnie:

Mówiąc najprościej, rozmiar partycji to liczba klastrów znajdujących się w partycji (pamiętaj, że pojedyncze klastry nie są uwzględnione w partycji!):

Teraz możemy zdefiniować jeden z kluczowych lematów, który dla danych partycji pozwala określić, czy zachodzi zależność, czy nie:

Lemat 1. Zależność A, B → C zachodzi wtedy i tylko wtedy, gdy

Zgodnie z lematem, aby ustalić, czy zależność zachodzi, należy wykonać cztery kroki:

1. Oblicz partycję dla lewej strony zależności
2. Oblicz partycję dla prawej strony zależności
3. Oblicz iloczyn pierwszego i drugiego etapu
4. Porównaj rozmiary przegród uzyskanych w pierwszym i trzecim kroku

Poniżej znajduje się przykład sprawdzenia, czy zależność zachodzi zgodnie z tym lematem:

W tym artykule zbadaliśmy pojęcia takie jak zależność funkcjonalna, przybliżona zależność funkcjonalna, sprawdziliśmy, gdzie są stosowane, a także jakie istnieją algorytmy wyszukiwania funkcji fizycznych. Przeanalizowaliśmy również szczegółowo podstawowe, ale ważne pojęcia, które są aktywnie wykorzystywane w nowoczesnych algorytmach wyszukiwania przepisów federalnych.

Bibliografia:

1. Huhtala Y. i in. TANE: Wydajny algorytm odkrywania zależności funkcjonalnych i przybliżonych //Dziennik komputerowy. – 1999. – T. 42. – Nr. 2. – s. 100-111.
2. Kruse S., Naumann F. Skuteczne odkrywanie przybliżonych zależności // Postępowanie fundacji VLDB. – 2018 r. – T. 11. – Nr. 7. – s. 759-772.
3. Papenbrock T., Naumann F. Hybrydowe podejście do odkrywania zależności funkcjonalnych //Materiały z Międzynarodowej Konferencji na temat Zarządzania Danymi 2016. – ACM, 2016. – s. 821-833.
4. Papenbrock T. i in. Odkrycie 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. Przyłączyć się czy nie dołączyć?: Dwa razy zastanowić się nad łączeniem przed wyborem funkcji //Materiały z Międzynarodowej Konferencji na temat Zarządzania Danymi 2016. – ACM, 2016. – s. 19-34.
6. Abo Khamis M. i in. Uczenie się w bazie danych za pomocą rzadkich tensorów //Materiały z 37. sympozjum ACM SIGMOD-SIGACT-SIGAI na temat zasad systemów baz danych. – ACM, 2018. – s. 325-340.
7. Hellerstein J. M. i in. Biblioteka analityczna MADlib: lub umiejętności MAD, SQL //Proceedings of the VLDB Endowment. – 2012. – T. 5. – Nr. 12. – s. 1700-1711.
8. Qin C., Rusu F. Przybliżenia spekulatywne dla optymalizacji teraskalowego rozproszonego gradientu opadania //Proceedings of the Fourth Workshop on Data Analytics in the Cloud. – ACM, 2015. – s. 1.
9. Meng X. i in. Mllib: Uczenie maszynowe w Apache Spark //The Journal of Machine Learning Research. – 2016 r. – T. 17. – Nr. 1. – s. 1235-1241.

Autorzy artykułu: Anastazja Birillo, badacz ds Badania JetBrains, Student centrum CS и Nikita Bobrow, badacz ds Badania JetBrains

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