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

19

Tampaknya diketahui bahwa untuk menemukan jawaban atas kueri atas database relasional , kita perlu waktu , dan seseorang tidak dapat menyingkirkan eksponen . $Q$ $D$ $|D|^{|Q|}$ $|Q|$

Karena bisa menjadi sangat besar, kami bertanya-tanya mengapa database bekerja sama sekali dalam praktiknya. $D$

Apakah ini hanya masalah permintaan biasa yang tidak besar sama sekali dalam aplikasi dunia nyata? (Maka itu menarik untuk mengetahui apa ukuran pertanyaan yang biasa diajukan untuk sistem database relasional, dan apa ukuran "maksimal" dari pertanyaan yang diharapkan dapat dijawab secara efektif oleh sistem DB dalam praktiknya .)

Catatan tentang eksponen tidak `dilepas ' $|Q|$

Untuk menunjukkan bahwa eksponen tidak dapat dilepas, seseorang dapat menggunakan kueri yang menanyakan apakah ada klik ukuran dalam grafik yang diberikan oleh database. Untuk memeriksa apakah grafik memiliki -clique adalah masalah NP-complete. Selain itu, ini tidak bisa diperbaiki dengan parameter tetap, dengan parameter . Detail dapat ditemukan di, misalnya, Libkin, L .: Elements Of Finite Model Theory. Springer (2004) atau Papadimitriou, CH, Yannakakis, M .: Tentang kompleksitas kueri basis data. J. Comput. Syst. Sci. 58 (3), 407–427 (1999) $|Q|$ $n$ $n$ $n$

cc.complexity-theory time-complexity descriptive-complexity db.databases imz - Ivan Zakharyaschev
sumber

7

Kueri biasa (seperti SELECT * FROM users WHERE username="abc" AND passwrod="xyz") adalah pencarian sederhana, yang menjalankan O (| D |) untuk dijalankan. Jika ada indeks pada bidang basis data yang relevan, itu akan mengambil O (log | D |). Saya tidak ke dalam basis data, tapi saya tidak berpikir pertanyaan yang lebih rumit akan memakan waktu eksponensial.

MS Dousti

7

@ imz: Dalam contoh Anda, kompleksitasnya adalah

, yang masih polinomial. Tampaknya, jika ada k bergabung dalam kueri, kompleksitasnya adalah

. Ini adalah polinomial untuk k tetap, tapi saya pikir untuk k besar, menjalankan kueri akan sangat lambat dalam praktiknya. Oleh karena itu seseorang harus menghindari terlalu banyak bergabung di semua biaya.

O (| D |^{2})

$O(|D|^2)$

O (| D |^{k + 1})

$O(|D|^{k+1})$

MS Dousti

7

Kompleksitas waktu adalah eksponensial dalam panjang kueri dalam kasus terburuk . Ini tidak bertentangan dengan beberapa permintaan panjang yang cepat. Praktisi basis data tahu kueri mana yang berjalan cepat di mesin basis data biasa, dan mereka tidak bergantung pada kasus terburuk yang terikat dalam hal panjangnya permintaan.

Tsuyoshi Ito

2

@Kaveh: "Buku Kompleksitas Deskriptif Immerman melakukan diskusi kecil di bab terakhir": Saran yang sangat bagus. Nitpicking: Ini dibahas dalam bab kedua dari belakang. @ imz: Anda mungkin menemukan kertas Daya Ekspresif dari SQL juga bermanfaat.

MS Dousti

5

@imz: "Apakah grafik ini memiliki n-klik" bukan pertanyaan umum dalam praktiknya. Sebagian besar pertanyaan lebih seperti yang disarankan @Sadeq, dan memiliki struktur seperti pohon. Selain itu, untuk database yang sangat besar, bahkan permintaan linear sepenuhnya terlalu mahal, dan kita harus bekerja dengan sketsa database.

András Salamon

16

Ada kelas besar pertanyaan yang "mudah", bahkan dalam kasus terburuk. Secara khusus, jika kelas kueri hanya berisi kueri konjungtif dan setiap kueri memiliki lebar terikat (misalnya treewidth, treewidth grafik insidensinya, lebar hiperree fraksional, atau lebar submodular) maka kueri dapat dijawab dengan menggunakan sesuatu seperti gabungan pohon , bersama dengan enumerasi brute force untuk bagian lokal dari kueri yang menyimpang dari pohon. Ini membutuhkan waktu polinomial, dengan derajat polinom ditentukan oleh parameter lebar.

Tampaknya banyak pertanyaan yang ditemui dalam praktik bersifat konjungtif dan memiliki lebar kecil. Jadi runtime polinomial memiliki tingkat rendah dalam hal ini.

Dániel Marx mempresentasikan makalah di STOC 2010 tentang lebar submodular baru-baru ini, versi lengkapnya mencakup ringkasan yang bagus tentang berbagai pengertian lebar dan bagaimana perumusan CSP berhubungan dengan formalisme basis data (versi konferensi tidak memiliki ini).

Dániel Marx, properti hypergraph yang dapat dilacak untuk kepuasan kendala dan pertanyaan konjungtif , 2010. arxiv: 0911.0801

Ini bukan jawaban yang lengkap, karena tidak berurusan dengan kompleksitas "khas" dari query database, tetapi bahkan dengan analisis kasus terburuk ada pertanyaan mudah.

András Salamon
sumber

6

Orang dapat menggunakan kueri Q_n untuk memeriksa apakah grafik, direpresentasikan sebagai basis data, berisi klik dengan n elemen. Untuk memeriksa apakah grafik memiliki klik adalah masalah NP-complete. Selain itu, ini tidak bisa diperbaiki dengan parameter tetap, dengan parameter n (yang berarti D ^ n).

mishaz
sumber

Silakan kirim penjelasan tambahan mengenai latar belakang pertanyaan baik sebagai "komentar" (bukan "jawaban") - dengan tombol "Tambahkan Komentar" di bawah pertanyaan, atau sebagai saran sunting - dengan tautan "sunting" di bawah pertanyaan. "Jawaban" bukan untuk diskusi dan penambahan pertanyaan. (Berpartisipasi di sini harus lebih nyaman jika Anda mendaftar sebagai pengguna non-anonim; maka lebih mudah untuk melacak siapa yang mengatakan apa dalam diskusi.)

imz - Ivan Zakharyaschev

@imz: Dia meletakkannya sebagai jawaban karena dia tidak memiliki hak istimewa untuk berkomentar. Seseorang harus memiliki setidaknya 50 rep. untuk dapat berkomentar di mana-mana.

Tomek Tarczynski

@ Tomek, @imz, yah, sedang dibahas tentang meta saat ini jika kita harus mengizinkan komentar menggunakan jawaban atau tidak.

Kaveh

5

Cara lain untuk menjawab pertanyaan ini adalah, "mereka tidak!"

Jika Anda memberikan implementasi DBMS khas kueri berisi jumlah yang sangat besar bergabung, itu bahkan tidak akan membuatnya melewati fase perencanaan / optimasi (apalagi evaluasi), bahkan jika kueri asiklik atau memiliki struktur yang sangat sederhana seperti Andrá menyinggung hal di atas.

Tapi, untuk beban kerja DBMS "khas", pertanyaan seperti itu tampaknya tidak muncul.

tjgreen
sumber

1

Untuk pertanyaan kompleks, hasil fase optimasi adalah rencana yang dipilih secara acak. Ini tidak seburuk kedengarannya, karena jalur eksekusi mungkin masih "cukup baik", dan ada banyak alasan mengapa optimasi sulit di luar kombinatorik dari jumlah gabungan.

Tegiri Nenashi

4

Berikut adalah versi yang lebih memperhatikan realitas dari jawaban tigreen dari sudut pandang orang yang benar-benar menggunakan basis data (relasional) secara intensif: Inti dan kompleksitas aplikasi mereka adalah untuk menyusunnya dengan cara yang mereka perlukan dalam jumlah yang sedikit. bergabung untuk setiap permintaan yang pernah dibutuhkan sebanyak mungkin dan itulah sebabnya mereka benar-benar Berfungsi . Dengan kata lain, jangan berharap basis data untuk menyelesaikan masalah rumit bagi Anda sendiri - mereka tidak akan, tetapi jika digunakan dengan bijak mereka adalah instrumen yang sangat berguna dan dapat diterapkan.

siapapun
sumber

0

Bergabung hanya kuadratik dari hubungan banyak ke banyak. Ini relatif jarang: dalam praktiknya, sebagian besar hubungan dan gabungan adalah 1-ke-banyak, sehingga mereka akan membutuhkan waktu linier jika indeks / kunci didefinisikan. Pertanyaan dengan beberapa banyak-ke-banyak bergabung adalah masalah serius.

reinierpost
sumber

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

Catatan tentang eksponen tidak `dilepas '| Q ||Q||Q|

Jawaban:

Catatan tentang eksponen tidak `dilepas ' $|Q|$