Czy istnieje związek między relacyjną algebrą / rachunkiem a teorią kategorii?

Mam świadomość co najmniej dwóch różnych teoretycznych podejść do zrozumienia relacyjnych baz danych: relacyjnej algebry / rachunku Codda i teorii kategorii.

Czy istnieje związek między tymi dwoma podejściami? Czy są w pewnym sensie równoważne? Czy są jakieś prace wprowadzające wyjaśniające, w jaki sposób oba te środowiska wyjaśniają relacyjne bazy danych?

Tło: Jakiś czas temu przeczytałem Teorię kategorii Davida Spivaka dla naukowców, która poświęciła sporo czasu na dyskusje, w jaki sposób można zastosować teorię kategorii do zrozumienia teorii relacyjnych baz danych. Mając jednak niewielkie osobiste doświadczenie na temat tego, jakie są relacyjne bazy danych lub dlaczego są one przydatne, w tym czasie nie doceniałem w pełni głębi wglądu zawartej w książce.

Jednak ostatnio uczyłem się o zapytaniach SQL i dwóch pakietach R do manipulacji danymi: dplyr i data.table . SQL może najwyraźniej wyrażać wiele pomysłów algebry relacyjnej / rachunku / modelu Codda, ale nie wszystkie . Co więcej, autor dplyr, Hadley Wickham, wyraźnie stwierdził, że jego filozofia leżąca u podstaw pakietu opiera się na pracy Codda nad relacyjną algebrą oraz podstawowych komendach data.table dość dobrze odwzorowujących polecenia w SQL i dplyr.

Wiem też, że teoria kategorii wpływa na wielu programistów używających funkcjonalnych języków programowania, takich jak Haskell. Jednak tak naprawdę nie jestem świadom, że istnieje jakiekolwiek zastosowanie programowania funkcjonalnego do manipulacji danymi lub nauki danych, oprócz mruczącego pakietu Hadleya Wickhama dla R, faktu, że Apache Spark jest napisany w Scali oraz technologii związanych z MapReduce .

Wszystkie tego rodzaju sugestie sugerują mi, że powinien istnieć jakiś związek między teorią kategorii a relacyjną algebrą / rachunkiem Codda, ale nigdy nie słyszałem o tym, aby ktoś wyraźnie określał takie powiązanie lub wyjaśniał, w jaki sposób leży u podstaw decyzji projektowych w popularnych manipulacjach danymi i technologie relacyjnych baz danych. Podejrzewam więc, że mogłem się całkowicie mylić.

EDYCJA: Najwyraźniej David Spivak pracował nad „ funkcjonalnym językiem zapytań (FQL) ”. To brzmi jak zastosowanie takiego teoretycznego połączenia, pod warunkiem, że istnieje.

Uwaga: Nie jestem pewien, czy „struktury relacyjne” są odpowiednim znacznikiem do dyskusji na temat relacyjnych baz danych lub relacyjnej algebry / rachunku różniczkowego. Ten artykuł w Wikipedii sugeruje, że mogą być ze sobą powiązane, ale ostatecznie nie wiem, co oznacza wyrażenie „struktura relacyjna”. Ponownie otaguj.

Kategoryczne podejście do zapytań o języki jest trochę niszowe, ale myślę, że to bardzo interesująca nisza!

Dwoma kluczowymi postaciami w tej dziedzinie są Peter Buneman i Torsten Grust . Oczywiście nie wykonali całej pracy, ale jeśli zaczniesz od ich dokumentów i prześledzisz wykres cytowań, uzyskasz całkiem dobre pokrycie tego obszaru.

Główną obserwacją, na której pracują, jest to, że ponieważ relację można postrzegać jako zbiór krotek, funktor zestawu sił można interpretować jako przyjmowanie typu krotki do rodzaju relacji nad tą krotką. Zatem fakt, że funktor powerset tworzy monadę, oznacza, że ​​możesz używać pomysłów inspirowanych składnią rozumienia monad Philipa Wadlera, aby uzyskać kategorycznie inspirowany rachunek dla zapytań o bogatej teorii równań.

Rzeczywiście, system zapytań Bunemana i in Kleisli otrzymał swoją nazwę od tego, że monady są czasem nazywane „potrójnymi Kleisli”.

Rozprawa doktorska Grust, Comprehending Queries , szczegółowo omawia te idee, w tym wykorzystanie morfizmów monad do modelowania operatorów agregacji (takich jak sumi count). Grust i jego grupa również zbudowali system, Ferry , który badał, jak zintegrować bazy danych z językami programowania.

Jednym z głównych problemów w tej pracy (a także w Kleisli, jeśli pamięć służy), jest to, że monadyczne języki zapytań wydają się być nieco bardziej ekspresyjne niż algebra relacyjna - pozwalają zapytaniom obsługiwać zestawy zbiorów. Kompilacja tego w SQL lub algebrze relacyjnej wymaga pewnej uwagi (na przykład zobacz praktyczną teorię kwerendy zintegrowanej z językiem ) Cheneya i in. , Ale podstawowa kwestia ma bardzo ładne kategoryczne sformułowanie. Algebra relacyjna wykorzystuje jedynie monoidalną strukturę funktora powerset, tj. Istnienie naturalnej transformacji iloczynu kartezjańskiego$(\bullet) : \mathcal{P}(X) \times \mathcal{P}(Y) \to \mathcal{P}(X \times Y)$; i monadyczne języki zapytań również wymagają połączenia,$\mu : \mathcal{P}(\mathcal{P}(X)) \to \mathcal{P}(X)$.

To prawdopodobnie główny strumień pracy nad kategorycznymi podejściami do języków zapytań.

Nowym pomysłem (który niestety nie zyskał tak dużej przyczepności, jak myślę, że na to zasługuje) jest praca Davida Spivaka nad wykorzystaniem prostych zestawów do modelowania baz danych - patrz Simplicial Databases . Główną innowacją jest to, że prosta struktura pozwala na jawne modelowanie całego schematu bazy danych, w tym relacji między tabelami (np. Systemem kluczy obcych), a to umożliwia nadanie semantyki operacjom aktualizacji schematu.

Kolejnym odstępstwem od standardowych języków zapytań są ograniczone logiczne języki programowania, takie jak Datalog, które można rozumieć jako algebrę relacyjną plus operator punktu stałego. Punkty stałe pozwalają wyrażać takie rzeczy, jak przechodnie zapytania o zamknięcie, a więc nowe bazy danych, takie jak języki zapytań funkcji Datomic oparte na Datalog. Mój doktorant, Michael Arntzenius , i ja studiowaliśmy semantykę Datalogu, i opracowaliśmy funkcjonalny analog, który nazywamy Datafun , który ma dość kategoryczną interpretację w kategoriach zestawów i semilattices.