Bahasa query database untuk kueri yang efisien

9

Tampaknya dalam bahasa kueri populer untuk basis data relasional, dimungkinkan untuk membuat kueri yang akan membutuhkan banyak sumber daya untuk menjawab. Dalam praktiknya, admin basis data mengelola ini dengan membatasi jumlah memori per kueri , dan memeriksa kueri yang telah berjalan lama jika ada perlambatan dalam database. Ini sepertinya agak ad-hoc, apakah ada solusi TCS untuk ini?

Apakah ada bahasa permintaan yang hanya dapat mengimplementasikan permintaan efisien?

Jika tidak ada bahasa seperti itu, apakah ada alasan teoretis untuk ini?

Beberapa alasan mengapa saya mengharapkan hal-hal semacam ini ada atau setidaknya masuk akal:

  • kami memiliki bahasa pemrograman yang secara khusus dirancang untuk hanya menerapkan perhitungan efisien (biasanya dengan memiliki beberapa logika restriktif dalam sistem tipenya)
  • bahasa query populer (seperti SQL) sudah terinspirasi oleh logika, sehingga tidak tampak sebagai peregangan bagi pengguna database untuk mempertimbangkan logika yang lebih ketat.
  • pengguna basis data yang tidak jahat sudah mencoba menyiapkan kueri yang dieksekusi dengan cepat, jadi kita harus berharap bahasa query yang lebih ketat ini hanya menghambat pengguna jahat.

Pertanyaan ini terinspirasi oleh persimpangan dua pertanyaan sebelumnya:

Bahasa pemrograman untuk komputasi yang efisien

Mengapa database relasional bekerja sama sekali, mengingat kompleksitas eksponensial teoretis dari penemuan jawaban (dalam ukuran kueri)?

cc.complexity-theory pl.programming-languages db.databases finite-model-theory Artem Kaznatcheev
sumber
1
Bukankah ini tepatnya topik Kompleksitas Deskriptif? mereka memiliki karakterisasi bahasa query untuk berbagai kelas kompleksitas.
Kaveh
Kompleksitas deskriptif jelas merupakan bagian besar dan panduan untuk bahasa pemrograman untuk perhitungan yang efisien. Tapi saya tidak berpikir itu sesederhana mengatakan "kompleksitas deskriptif menggunakan logika" dan "query ke database menggunakan logika". Secara khusus, untuk DC tampaknya ukuran kueri sudah diperbaiki dan 'n' berasal dari ukuran struktur hingga yang diterima kueri. Dalam database, sebenarnya ukuran kueri yang variabel dan database juga variabel atau mungkin parameter tetap.
Artem Kaznatcheev
3
ada juga hasil untuk permintaan variabel, mereka hanya tidak begitu mencengangkan seperti kecocokan antara kelas memeriksa model dan kelas kompleksitas terkenal. Juga bidang yang lebih luas dari teori model hingga, di mana kompleksitas deskriptif merupakan bagian, memiliki sejumlah hasil ekspresibilitas yang berhubungan langsung dengan database. Basis data pada akhirnya adalah struktur teori-model yang hampir persis terbatas.
Marc Hamann
1
Saya tidak memikirkan korespondensi ini. Saya menambahkan tag teori-model hingga. Jika Anda atau @Kaveh ingin menguraikan komentar Anda dan mengetahui cara mengadopsi hasil spesifik dari kompleksitas deskriptif model-teori terbatas pada umumnya untuk menghasilkan bahasa query seperti itu, maka saya benar-benar ingin melihat jawaban itu!
Artem Kaznatcheev

Jawaban:

7

Salah satu cara melihat bahasa query database adalah melalui lensa database deduktif , di mana query direpresentasikan sebagai program logika. Dalam pengaturan ini, pekerjaan paling relevan yang terkait dengan pertanyaan Anda adalah McAllester Pada analisis kompleksitas analisis statis , yang mengamati bahwa Anda dapat mempertimbangkan tentang waktu menjalankan kueri dengan alasan tentang jumlah "pemecatan awalan" dalam aturan Anda program. Apa "awalan menembak" itu tidak terlalu rumit, tapi saya akan merujuk Anda ke kertas untuk itu.

Dalam dunia pemrograman fungsional, hal semacam ini disebut semantik biaya : itu tidak berarti Anda hanya dapat mengimplementasikan kueri (program) yang efisien, tetapi itu berarti bahwa Anda dapat mempertimbangkan kompleksitas asimtotik dari program deklaratif Anda dengan cara yang masuk akal .

Beberapa kemudian bekerja pada implementasi ide-ide McAllester termasuk Dari aturan datalog ke program yang efisien dengan jaminan waktu dan ruang (Liu dan Stoller) dan Dedalus: Datalog dalam Waktu dan Ruang (Alvaro, Marczak, Conway, Hellerstein, Maier, dan Sears). Saya akui saya belum membaca yang terakhir dari kedua makalah itu.

Rob Simmons
sumber