Tentang algoritma reduksi Codd

Algoritma Codd mengubah ekspresi dalam kalkulus relasional tuple menjadi Aljabar Relasional.

1. Apakah ada implementasi standar dari algoritma?
2. Apakah algoritma ini digunakan di mana saja? (Tampaknya industri ini hanya membutuhkan SQL dan varian, saya tidak yakin tentang teori database di akademisi.)
3. Apa kerumitan reduksi?

_{Ini diposting di SO lebih dari setahun yang lalu, tetapi tidak menerima jawaban yang baik.}

Pengurangan ini adalah teknik bukti konstruktif untuk menunjukkan bahwa subset (bernama aman) Tuple Relational Calculus (TRC) kurang ekspresif daripada Relational Algebra (RA). Cara lain menjadi benar juga, Safe-TRC dan RA memiliki kekuatan ekspresif yang setara. Lihat Teorema 5.3.10 sebagai contoh. Pembatasan "keamanan" sintaksis memastikan properti independen domain dari kalkulus dan diperlukan.

Dalam R-DBMS, SQL dapat dilihat sebagai bahasa konkret (deklaratif) untuk TRC. Mitra RA adalah rencana prosedural (urutan operasi) di mana ekspresi SQL dikompilasi. Jadi, konversi sebenarnya adalah deskripsi formal dari proses kompilasi. Perhatikan bahwa SQL memperkenalkan ekstensi seperti DISTINCT, ORDER BY, GROUP BY yang jelas di luar ruang lingkup teori TRC dan RA.

Saya tidak tahu kompleksitas teoretis yang tepat dari konversi, tetapi jelas itu harus "murah". Foton Kolaitis menyatakan bahwa itu linear.

Saya tidak mengetahui implementasi konsep bukti dari algoritma ini.