Perpanjangan SQL capturing

Menurut Immerman , kelas kompleksitas yang terkait dengan kueri SQL adalah kelas kueri aman di (kueri urutan pertama ditambah operator penghitungan): SQL menangkap kueri aman. (Dengan kata lain, semua kueri SQL memiliki kompleksitas dalam , dan semua masalah di dapat diekspresikan sebagai kueri SQL.) $\mathsf{Q(FO(COUNT))}$ $\mathsf{Q(FO(COUNT))}$ $\mathsf{Q(FO(COUNT))}$

Berdasarkan hasil ini, dari sudut pandang teoretis, ada banyak masalah menarik yang dapat diselesaikan secara efisien tetapi tidak dapat diekspresikan dalam SQL. Oleh karena itu perpanjangan SQL yang masih efisien tampaknya menarik. Jadi inilah pertanyaan saya:

Apakah ada ekstensi SQL (diimplementasikan dan digunakan dalam industri ) yang menangkap $\mathsf{P}$ (yaitu dapat mengekspresikan semua kueri yang dihitung waktu polinomial dan tidak ada yang lain)?

Saya ingin bahasa query database yang memenuhi ketiga kondisi. Sangat mudah untuk mendefinisikan ekstensi yang akan memperluas SQL dan akan menangkap . Tetapi pertanyaan saya adalah apakah bahasa seperti itu masuk akal dari perspektif praktis, jadi saya ingin bahasa yang digunakan dalam praktik. Jika ini bukan masalahnya dan tidak ada bahasa seperti itu, maka saya ingin tahu apakah ada alasan yang membuat bahasa seperti itu tidak menarik dari sudut pandang praktis? Misalnya, apakah pertanyaan yang muncul dalam praktik biasanya cukup sederhana sehingga tidak perlu bahasa seperti itu? $\mathsf{P}$

database-theory complexity-theory finite-model-theory descriptive-complexity Kaveh
sumber

@ JD, maaf, tapi berdasarkan komentar Anda, saya pikir Anda tidak mengerti pertanyaannya. Pertanyaannya jelas. Menangkap kelas kompleksitas dengan bahasa adalah terminologi standar. (Apa yang tidak terdefinisi dengan baik adalah preferensi saya bahwa bahasa tersebut harus menjadi bahasa query, tetapi itu hanya preferensi dan saya sudah memberi tahu Anda bahwa saya akan baik-baik saja dengan yang tidak jika tidak ada satu dengan preferensi itu.)

Kaveh

@ Shog9, saya sudah menjawabnya. JD tidak mengerti pertanyaan itu, ia bahkan tidak tahu apa arti menangkap dan tidak menyadari bahwa bahasa yang menangkap P tidak bisa Turing lengkap dengan definisi. Dia berharap itu akan dinyatakan dalam cara dia suka, saya telah menyatakannya dalam terminologi kompleksitas deskriptif biasa dan kompleksitas bahasa query, dan bahkan telah menjelaskan ini kepadanya. Apa yang tidak jelas di sini?

Kaveh

@ Shog9, motivasi datang dari Kompleksitas Deskriptif . Saya mencoba untuk melihat apakah ada bahasa yang memperluas SQL yang digunakan dalam industri yang menangkap P. Bahasa SQL asli agak lemah seperti yang ditunjukkan hasil Immermann, dari sudut pandang teoritis banyak perhitungan efisien tidak mungkin untuk dinyatakan di dalamnya. Di sisi lain kami ingin menjaga bahasa tetap efisien (yaitu

). Apakah ada bahasa seperti itu? (Saya pikir ini mungkin jelas bagi orang yang akrab dengan kompleksitas deskriptif).

P

$\mathsf{P}$

Kaveh

@ Shog9: Saya gagal melihat mengapa pertanyaan ini membutuhkan intervensi moderator dan ditutup. Saya cukup nyaman dengan Kompleksitas Deskriptif untuk mengatakan bahwa ini adalah pertanyaan nyata (walaupun mungkin lebih cocok untuk TCS - ini sedikit pertanyaan yang sulit).

Alex ten Brink

Ketika saya melihat pertanyaan lain juga ditutup (yang juga memiliki suara dekat), saya mengajukan pertanyaan tentang meta tentang itu: meta.cs.stackexchange.com/questions/97/…

Alex ten Brink

Jawaban:

Adapun pertanyaan utama Anda, saya sarankan survei singkat ini oleh Martin Grohe.

Apakah pertanyaan yang diperlukan dalam praktik biasanya cukup sederhana sehingga tidak perlu bahasa yang lebih kuat?

Saya akan mengatakan ini memegang sebagian besar waktu, mengingat jumlah ekstensi yang adil ditambahkan ke bahasa permintaan umum (penutupan transitif, operator aritmatika, penghitungan, dll.). Ini berasal dari sudut pandang seseorang yang telah melakukan beberapa pekerjaan sebagai pengembang lepas situs web yang relatif sederhana dan aplikasi lain, jadi saya tidak yakin tentang penggunaan nyata SQL dalam industri yang lebih besar / database yang lebih besar.

Dalam kasus yang jarang terjadi, bahasa yang lebih kuat mungkin diperlukan, saya duga bahwa pengembang perangkat lunak menanganinya dengan menggunakan bahasa tempat mereka menulis aplikasi, bukan kueri (seperti C ++ atau java).

Janoma
sumber

Pertama, kekuatan ekspresif SQL kurang jelas dari yang terlihat. Fitur agregat, pengelompokan, dan aritmatika dari SQL ternyata memiliki efek yang cukup halus. A priori, tampaknya layak bahwa dengan beberapa pengkodean operator aljabar menggunakan fitur-fitur ini, orang benar-benar dapat mengekspresikan jangkauan dalam SQL. Ternyata ini sebenarnya bukan kasus untuk SQL-92 , yang merupakan "lokal".

Leonid Libkin. Kekuatan ekspresif dari SQL , TCS 296 (3), 379-404. doi: 10.1016 / S0304-3975 (02) 00736-3 ( pracetak )

Ini berarti bahwa ekstensi diperlukan untuk SQL-92 untuk menangkap PTIME, dan yang memungkinkan bahasa yang dihasilkan menjadi "non-lokal".

Namun, memungkinkan struktur yang dipesan dan dengan aritmatika yang terbatas secara realistis, membuktikan bahwa SQL-92 tidak dapat mengungkapkan jangkauan akan menyiratkan bahwa seragam dan karenanya cenderung cukup sulit. (Dapat dikatakan bahwa pemesanan linear alami selalu ada pada tipe data dalam SQL-92, dan oleh karena itu orang dapat mengasumsikan bahwa struktur yang mendasarinya dipesan.) $\text{TC}^0 \subsetneq \text{NLOGSPACE}$

Kemudian lansekap berubah lagi, karena SQL: 1999 (SQL3) termasuk rekursi. Jadi SQL: 1999 tampaknya setidaknya sama ekspresifnya dengan logika titik tetap dengan penghitungan (meskipun saya pikir detailnya mungkin agak rumit, termasuk masalah pesanan). Apakah konstruksi baru membuat logika lebih ekspresif daripada yang diperlukan untuk menangkap PTIME, saya tidak tahu, dan beberapa studi akan diperlukan untuk membangun ini. Sementara itu, revisi lebih lanjut dilakukan pada tahun 2003 , 2006 , 2008 dan 2011(menjadi dokumen ISO, hanya konsep yang tersedia secara gratis). Revisi ini menambahkan banyak sekali fitur baru, termasuk memungkinkan XQuery sebagai "bagian" dari pertanyaan SQL. Dugaan saya adalah bahwa "SQL" sekarang lebih ekspresif daripada yang diperlukan untuk menangkap PTIME, tetapi pengkodean yang diperlukan untuk melakukannya mungkin memerlukan kueri yang besar dan agak tidak wajar yang mungkin tidak didukung dalam sistem nyata.

Jadi saya pikir ada bukti bahwa tidak ada ekstensi industri SQL yang secara tepat menangkap PTIME , menjawab pertanyaan Anda dengan cara yang kabur. Singkatnya, ekstensi industri agak kuat dan mungkin sudah melampaui PTIME. Jika memang benar bahwa SQL: 1999 sudah cukup kuat untuk menangkap setidaknya PTIME, maka itu juga tidak jelas apa arti "SQL" dalam pertanyaan Anda, karena orang harus mendefinisikan "SQL" berarti versi yang mendahului SQL: 1999.

Akhirnya, survei Grohe tentang pencarian logika yang menangkap PTIME (juga disebutkan oleh Janoma) menunjukkan tidak hanya bahwa menangkap PTIME itu rumit kecuali jika kita memiliki urutan linier sebagai bagian dari bahasa, tetapi juga bukti bahwa tidak ada logika seperti itu juga akan menyiratkan . $\text{P} \ne \text{NP}$

Martin Grohe, Pencarian logika menangkap PTIME , LICS 2008, 267–271. doi: 10.1109 / LICS.2008.11 ( pracetak )

András Salamon
sumber

Terima kasih András, terutama untuk menyebutkan bahwa SQL3 mendukung "rekursi", saya harus memeriksa dan melihat apa yang diketahui tentang itu. :)

Kaveh

ps: Saya menduga bahwa Anda memasukkan diskusi tentang hubungan dengan teori kompleksitas dan logika menangkap P untuk pembaca, namun izinkan saya menambahkan sebagai catatan dan klarifikasi: Saya menggunakan SQL dalam arti bahwa Immerman telah menggunakannya dalam hasil dan bahwa hasilnya menggunakan definisi SQL yang tepat. Saya tahu tentang hubungan dengan pemisahan kelas kompleksitas dan pertanyaan tentang logika yang menangkap P, namun saya tidak berpikir mereka mempengaruhi jawaban atas pertanyaan saya,

Kaveh

jawaban atas pertanyaan saya bisa positif (atau negatif) dan mereka akan konsisten dengan semua jawaban yang mungkin untuk P vs NP dan keberadaan logika invarian-urutan untuk P.

Kaveh

Kaveh, jika Anda mendefinisikan SQL seperti yang dilakukan oleh Immerman, maka saya pikir jawabannya adalah "mungkin tidak", karena ekstensi industri yang ada tampaknya terlalu lemah, atau terlalu kuat. Tapi (AFAIK) kami tidak punya bukti kuat untuk ini. Mungkin sebagian subset dari ekstensi tepat menangkap PTIME, tapi saya tidak yakin saya ingin menjelajah melalui spesifikasi yang mencoba mengisolasinya ...

András Salamon

-1

$P$ $P$ $P$ $P$ $P$

$P = NP$ $P = NP$ $P$ $P$ $NPC$

$P \ne NP$

$P = NP$

Meskipun mungkin tidak ada untuk tujuan nyata, itu pasti ada dan dapat dibangun dan diimplementasikan. Anda bisa mendefinisikan bahasa itu dengan sesuatu yang mampu mensimulasikan mesin Turing hingga sejumlah langkah yang belum dilakukan. IE, mampu menyelesaikan masalah P-complete . Namun, jika Anda membangun hal seperti itu, itu hampir Turing-lengkap kecuali untuk pembatasan "diberi sejumlah langkah", yang dalam bahasa seperti SQL akan menjadi cara yang sangat aneh untuk membatasi hanya untuk permintaan yang aman. Anda bisa melakukan ini jika langkah-langkahnya adalah catatan dari beberapa tabel, tetapi ini masih tidak terlihat berharga untuk tujuan praktis.

Victor Stafusa
sumber

F O

$\mathsf{FO}$

A C^{0}

$\mathsf{AC^0}$

N P

$\mathsf{NP}$

P

$\mathsf{P}$

P

$\mathsf{P}$

F O (L F P)

$\mathsf{FO(LFP)}$ $\mathsf{P}$