Apakah ada hubungan antara aljabar / kalkulus relasional dan teori kategori?

Saya menyadari setidaknya dua pendekatan teoretis yang berbeda untuk memahami basis data relasional: aljabar / kalkulus relasional Codd, dan teori kategori.

Apakah ada hubungan antara kedua pendekatan ini? Apakah mereka dalam beberapa hal setara? Apakah ada pekerjaan pendahuluan yang menjelaskan bagaimana kedua kerangka kerja ini menjelaskan basis data relasional?

Latar belakang: Beberapa waktu yang lalu saya membaca Teori Kategori untuk Ilmuwan David Spivak yang menghabiskan cukup banyak waktu membahas bagaimana teori kategori dapat diterapkan untuk memahami teori database relasional. Namun, memiliki sedikit pengalaman pribadi tentang apa itu database relasional atau mengapa mereka berguna, pada saat itu saya tidak sepenuhnya menghargai kedalaman wawasan yang ditemukan dalam buku ini.

Namun, baru-baru ini saya telah belajar tentang query SQL dan dua paket R untuk manipulasi data: dplyr dan data.table . SQL ternyata dapat mengekspresikan banyak ide aljabar / kalkulus / model relasional Codd, tetapi tidak semua . Selain itu, penulis dplyr, Hadley Wickham, telah menyatakan secara eksplisit bahwa filosofinya yang mendasari paket didasarkan pada karya Codd pada aljabar relasional, dan perintah-perintah dasar data.tabel peta cukup baik untuk perintah dalam SQL dan dplyr.

Saya juga tahu bahwa teori kategori memengaruhi banyak programmer menggunakan bahasa pemrograman fungsional seperti Haskell. Namun, saya tidak benar-benar menyadari adanya penggunaan pemrograman fungsional untuk manipulasi data atau ilmu data, selain paket purrr Hadley Wickham untuk R, fakta bahwa Apache Spark ditulis dalam Scala , dan teknologi yang terkait dengan MapReduce .

Semua jenis ini menunjukkan kepada saya bahwa harus ada semacam hubungan antara teori kategori dan aljabar / kalkulus relasional Codd, tetapi saya belum pernah mendengar ada orang yang membuat koneksi semacam itu secara eksplisit atau menjelaskan bagaimana hal itu mendasari keputusan desain dalam manipulasi data populer dan teknologi basis data relasional. Jadi saya juga curiga saya bisa sepenuhnya salah.

EDIT: Rupanya David Spivak telah bekerja pada " bahasa query functorial (FQL) ". Ini kedengarannya seperti aplikasi dari koneksi teoretis, asalkan ada.

Catatan: Saya tidak yakin apakah "struktur-relasional" adalah tag yang tepat untuk diskusi tentang basis data relasional atau aljabar / kalkulus relasional. Artikel Wikipedia ini menunjukkan mereka mungkin terhubung, tetapi pada akhirnya saya tidak tahu apa arti frasa "struktur relasional". Jangan ragu untuk memberi tag ulang.

Pendekatan kategorikal pada bahasa query sedikit menarik, tapi saya pikir ini niche yang sangat menarik!

Dua tokoh kunci di bidang ini adalah Peter Buneman dan Torsten Grust . Jelas, mereka tidak melakukan semua pekerjaan, tetapi jika Anda mulai dengan kertas mereka dan menelusuri grafik kutipan, Anda akan mendapatkan cakupan area yang cukup bagus.

Pengamatan sentral dari mana mereka bekerja adalah bahwa karena suatu relasi dapat dipandang sebagai satu set tupel, fungsi powerset dapat diartikan sebagai mengambil tipe tuple ke tipe relasi dari tupel itu. Kemudian, fakta bahwa funcet functor membentuk sebuah monad berarti bahwa Anda dapat menggunakan ide-ide yang diilhami oleh sintaks pemahaman monad Philip Wadler untuk memberikan kalkulus yang diilhami secara kategoris untuk pertanyaan dengan teori ekuasional yang kaya.

Memang, sistem permintaan Buneman et al, Kleisli mendapatkan namanya dari fakta bahwa monad kadang-kadang disebut "tiga kali lipat Kleisli".

Tesis PhD Grust, Comprehending Queries , menyelesaikan ide-ide ini secara rinci, termasuk penggunaan morfisme monad untuk memodelkan operator agregasi (seperti sumdan count). Grust dan kelompoknya juga membangun sistem, Ferry , yang mempelajari cara mengintegrasikan basis data ke dalam bahasa pemrograman.

Salah satu masalah utama dalam pekerjaan ini (dan juga di Kleisli, jika ingatanku), adalah bahwa bahasa query monadik cenderung sedikit lebih ekspresif daripada aljabar relasional - mereka mengizinkan permintaan untuk menangani set set. Mengkompilasi ini ke SQL atau aljabar relasional membutuhkan perhatian (misalnya, lihat Cheney et al. Sebuah teori praktis dari query yang terintegrasi dengan bahasa ), tetapi masalah dasarnya memiliki formulasi kategorikal yang sangat bagus. Aljabar relasional hanya menggunakan struktur monoidal dari funcet functor, yaitu, keberadaan transformasi alami produk kartesius$(\bullet) : \mathcal{P}(X) \times \mathcal{P}(Y) \to \mathcal{P}(X \times Y)$; dan bahasa permintaan monadik juga menuntut bergabung,$\mu : \mathcal{P}(\mathcal{P}(X)) \to \mathcal{P}(X)$.

Itu mungkin aliran utama pekerjaan pada pendekatan kategoris ke bahasa query.

Gagasan baru (yang sayangnya belum mendapatkan daya tarik sebanyak yang saya pikir pantas) adalah karya David Spivak tentang penggunaan set simplisial untuk memodelkan basis data - lihat Simplicial Databases . Inovasi sentral adalah bahwa struktur sederhana memungkinkan secara eksplisit memodelkan seluruh skema database termasuk hubungan antara tabel (misalnya, sistem kunci asing), dan ini memungkinkan memberikan semantik untuk operasi pembaruan skema.

Penyimpangan lain dari bahasa kueri standar adalah bahasa pemrograman logika terbatas seperti Datalog, yang dapat dipahami sebagai aljabar relasional plus operator titik tetap. Poin tetap memungkinkan mengekspresikan hal-hal seperti kueri penutupan transitif, dan database baru seperti bahasa kueri fitur Datomic berdasarkan Datalog. Mahasiswa PhD saya, Michael Arntzenius , dan saya telah mempelajari semantik Datalog, dan menghasilkan analog fungsional yang kami sebut Datafun , yang memiliki interpretasi yang cukup kategorikal dalam hal kategori poset dan semilattice.