Apakah ada isomorfisme antara (subset dari) teori kategori dan aljabar relasional?

Itu datang dari perspektif big data. Pada dasarnya, banyak kerangka kerja (seperti Apache Spark) "mengimbangi" kurangnya operasi relasional dengan menyediakan antarmuka seperti Functor / Monad dan ada gerakan serupa menuju konversi kucing ke SQL (Slick in Scala). Misalnya, kita perlu penggabungan alami (dengan asumsi tidak ada pengulangan pada indeks) untuk perkalian elemen-bijaksana vektor dari perspektif SQL, yang dapat dianggap sebagai zip + map(multiply) (Spark's MLib, bagaimanapun, sudah memiliki ElementwiseProduct) dalam aplikasi Kategori Teori.

Cukup dengan mengatakan (contoh-contoh berikut ada di Scala):

• subkumpulan referens yang direferensikan dapat dianggap sebagai functor aplikatif (koleksi berlebihan), yang pada gilirannya memberi kita zip: List(1,2,3).ap(List(2,4,8).map(a => (b: Int) => a * b))-> (List(1,2,3) zip List(2,4,8)).map(x => x._1 * x._2). Selain itu, kami dapat mendorongnya ke beberapa bergabung lain, dengan asumsi beberapa preprocessing ( groupByoperator atau hanya surjection, atau umumnya - sebuah epimorfisme).

• bergabung dan seleksi lainnya dapat dianggap sebagai monad. Misalnya WHEREsaja: List(1,2,2,4).flatMap(x => if (x < 3) List(x) else List.empty)->List(1,2,2,4).filter(_ < 3)

• data itu sendiri hanya ADT (GADT juga?), yang pada gilirannya terlihat seperti Set-kategori sederhana (atau lebih umum - Cartesian-closed), jadi harus (saya kira) mencakup operasi berbasis Set (karena Curry- Howard-Lambek sendiri) dan juga operasi suka RENAME(setidaknya dalam praktek).

• agregasi sesuai dengan fold/reduce(catamorphism)

Jadi, yang saya tanyakan adalah dapatkah kita membangun isomorfisme antara (mungkin subset dari) teori kategori dan aljabar relasional (keseluruhan) atau apakah ada sesuatu yang terbuka? Jika berhasil, "subset" kategori apa yang isomorfis terhadap relalgebra?

Anda dapat melihat bahwa asumsi saya sendiri cukup luas sementara solusi formal seperti korespondensi Curry-Howard-Lambek untuk logika-kucing-lambda lebih tepat - jadi sebenarnya, saya meminta referensi untuk penelitian yang dilakukan (yang menunjukkan hubungan langsung ) dengan lebih banyak contoh di Scala / Haskell.

Sunting : jawaban yang diterima membuat saya berpikir bahwa saya terlalu jauh mewakili gabungan dan kondisi sebagai monad (terutama menggunakan nilai kosong yang secara efektif instantiates FALSE), saya pikir pullback harus cukup setidaknya untuk subset relalgebra dari SQL. Monads lebih baik untuk barang-barang tingkat tinggi (bersarang) seperti GROUP BY, yang bukan bagian dari relalgebra.

Biarkan saya mengartikulasikan korespondensi Curry-Howard-Lambek dengan sedikit jargon yang akan saya jelaskan. Lambek menunjukkan bahwa kalkulus lambda yang diketik sederhana dengan produk adalah bahasa internal dari kategori tertutup kartesius. Saya tidak akan menjelaskan apa kategori tertutup kartesian, meskipun tidak sulit, melainkan apa yang dikatakan pernyataan di atas adalah Anda tidak perlu tahu! (Atau Anda sudah tahu, jika Anda tahu apa itu kalkulus lambda yang diketik sederhana dengan produk). Untuk beberapa jenis teori / logika menjadi bahasa internal / logika kategori berarti 1) bahwa kita dapat menafsirkan bahasa ke dalam struktur pada kategori dengan cara yang mempertahankan struktur bahasa (pada dasarnya kondisi kesehatan), dan2) dan "pada dasarnya" semua struktur yang timbul dari penutupan kartesius dapat dibicarakan dalam hal bahasa ini (kondisi kelengkapan).

$\{ x\mid x = x\}$. Setiap ekspresi aljabar relasional secara logis setara dengan kueri independen domain dalam kalkulus relasional.

Mengesampingkan hal itu, kategori yang logika internalnya (yang pada dasarnya merupakan bentuk bahasa internal yang tidak terkategorifikasi atau tidak relevan) adalah kategori Heyting untuk FOL intuitionistic dan kategori Boolean untuk FOL klasik. (Versi yang relevan yang dikategorikan / terbukti dijelaskan oleh hyperdoctrine . Juga sangat relevan adalah berbagai macam pretoposis .) Perhatikan, bahwa FOL, kalkulus relasional, dan aljabar relasional tidak mendukung agregasi. (Mereka juga tidak mendukung rekursi yang diperlukan untuk mewakili permintaan Datalog .) Satu pendekatan untukGROUP BYdan agregasi adalah untuk memungkinkan kolom bernilai hubungan yang mengarah ke logika tingkat tinggi (HOL) dan kalkulus bersarang bersarang (NRC). Setelah kami memiliki kolom bernilai relasi, agregasi dapat diformalkan hanya sebagai operator "skalar" lainnya.

Contoh Anda menunjukkan fakta bahwa meta-bahasa monadik adalah bahasa yang layak untuk kueri. Makalah Monad Comprehensions: A Versatile Representation of Queries ( PDF ) merinci hal ini dengan baik. Tampilan yang lebih komprehensif dan modern adalah tesis PhD Ryan Wisnesky, A Functional Query Language with Categorical Types ( PDF ), yang terkait dengan karya David Spivak yang dengan sendirinya agak relevan dengan interpretasi pertanyaan Anda. (Jika Anda ingin lebih historis, ada Kleisli, A Functional Query System .) Faktanya, meta-bahasa monadik adalah bahasa yang layak untuk kueri di dalam sarang.kalkulus relasional. Wisnesky merumuskan NRC dalam hal topos dasar yang bahasa internalnya adalah bahasa Mitchell-Bénabou yang pada dasarnya terlihat seperti teori himpunan intuitionistic dengan pembatas yang dibatasi. Untuk tujuan Wisnesky, ia menggunakan topos Boolean yang sebaliknya akan memiliki logika klasik. Bahasa ini jauh lebih kuat daripada (inti) SQL atau Datalog. Perlu dicatat bahwa kategori set hingga membentuk topos (Boolean) .