Kesetaraan matematika dari dua pernyataan SQL

9

Apakah ada cara untuk memeriksa kesetaraan matematis dari dua pernyataan SQL?

Saya punya dua pernyataan SQL:

  • SQL_STATEMENT_1
  • SQL_STATEMENT_2

Menjalankan kedua pernyataan pada data dan membandingkan output tidak membantu sama sekali.

Himpunan matematika di balik pernyataan perlu dievaluasi, seperti yang dilakukan oleh pemecah persamaan.

Di luar ruang lingkup pertanyaan saya adalah hal-hal seperti:

  • perbandingan selain kesetaraan (lebih besar dari, kurang dari, SEPERTI, ...)
  • prosedur tersimpan, atau pemicu
  • Ekspresi Common Table (WITH)

Dalam lingkup:

  • Subseleksi: WHERE other_id IN (PILIH id DARI WHERE lainnya ...)
  • BERGABUNG
database-theory guettli
sumber
Solusi parsial akan membandingkan rencana pelaksanaan 2 pertanyaan. Jika rencana eksekusi sama, maka mereka sama. Namun hubungan keduanya tidak berjalan baik. Ada 2 kueri yang setara secara logis yang memiliki rencana eksekusi yang berbeda.
BuahahaXD
1
@BuahahaXD: itu tidak benar. select * from foo where id = 4pasti akan memiliki rencana eksekusi yang sama denganselect * from foo where id = 2
a_horse_with_no_name
@a_horse_with_no_name Saya mengujinya di SQL Server dan mendapat 2 file XML yang berbeda. Parameter dimasukkan sebagai simpul <ParameterList> dalam file XML. Secara visual, rencana ini identik (scan tabel + pilih). Tapi saya percaya Anda mungkin benar tentang membandingkan rencana eksekusi.
BuahahaXD
1
@a_horse_with_no_name benar ketika datang ke kunci unik. Untuk semua yang lain, Adalah mungkin untuk select * from foo where id = 4dan select * from foo where id = 2memiliki dua rencana eksekusi yang berbeda jika 1) statistik indeks tidak mutakhir dan 2) bahkan jika statistik indeks mutakhir, distribusi utama id adalah miring. (ID yang disediakan bukan kunci unik).
RolandoMySQLDBA

Jawaban:

6

Apa persamaan matematis dari dua pernyataan SQL? Bagi saya, dua pertanyaan setara jika, ketika diberi kedua dataset yang sama, keduanya mengembalikan hasil yang sama.

Seperti yang Anda tunjukkan, SQL queries, superset dari aljabar relasional , bisa sangat kompleks. Kami dapat mencampur subqueries, menggunakan prosedur dan fungsi yang tersimpan ( deterministik atau tidak) yang akan membuat Anda lebih mirip kode nyata . Jika Anda berbicara tentang pertanyaan seperti ini maka itu akan sangat sulit. Sebenarnya itu mungkin tidak berbeda dari masalah "adalah dua algoritma yang setara".

Dalam kondisi itu mungkin tidak mungkin.

Namun...

... mungkin layak jika dua pertanyaan yang ingin Anda bandingkan adalah operasi yang ketat. Jika demikian, Anda bisa mengonversi kueri ke aljabar relasional dan kemudian menyelesaikannya dengan mengikuti aturan kesetaraan . Jika Anda memiliki pilihan / batasan dengan kondisi boolean nontrivial maka Anda mungkin perlu membuktikan daripada kondisi mereka juga setara. Anda kemudian harus mengandalkan aljabar boolean dan Anda mungkin akan berakhir dengan melakukan tabel kebenaran .

Seperti yang Anda lihat ini akan menjadi banyak pekerjaan dan, sejauh yang saya tahu, tidak ada yang bisa menghitung semua itu secara otomatis. Meskipun demikian, saya menemukan beberapa alat yang menurut Anda berguna jika Anda ingin menangani tugas:

LupaR
sumber
Pertanyaan saya hanya tentang mengatur operasi. Saya memperbarui pertanyaan. Hal ini terkait dengan masalah "dua algoritma yang setara". Tetapi konteksnya adalah batas, hanya operasi dasar dari set, join, subselect yang ada dalam ruang lingkup saya.
guettli
3

Tidak mungkin untuk memeriksa kesetaraan semantik dalam waktu yang terbatas menurut definisi, lihat teorema Rice :

untuk properti non-sepele dari fungsi parsial, tidak ada metode umum dan efektif untuk memutuskan apakah suatu algoritma menghitung fungsi parsial dengan properti itu.

pengguna63455
sumber
2
Ini hanya bukan komentar. Bisakah Anda memperluas penerapan Rice untuk konteks ini?
Michael Green
Sekalipun secara teori dimungkinkan, sintaks standar SQL saat ini sangat barok, dalam praktiknya tidak mungkin
James Anderson
1
Dengan penjelasan OP, sepertinya pertanyaannya lebih tentang kesetaraan logis daripada kesetaraan semantik. Pertanyaan sebenarnya adalah: dapatkah kita mengonversi pernyataan SQL ke ekspresi matematis dan kemudian mengevaluasi kesetaraan logis?
ForguesR
2

pengguna dba Lennart menunjuk saya ke proyek ini:

http://cosette.cs.washington.edu/

Cosette adalah prover otomatis untuk memeriksa ekivalensi dari query SQL. Ini memformalkan sebuah fragmen substansial dari SQL di Coq Proof Assistant dan mesin virtual simbolis Rosette. Ini mengembalikan bukti formal kesetaraan atau sampel tandingan untuk sepasang kueri yang diberikan.

guettli
sumber
1

Salah satu cara untuk melakukannya adalah dengan membangun parser, atau lebih baik, gunakan yang sudah ada. Saya percaya C # memiliki kelas TSQLParser dan memiliki metode Parse (). Parser akan memecah kueri Anda ke sub-kelas yang kemudian dapat Anda bandingkan.

Matan Yungman
sumber
1

Jika Anda mencari tes kesetaraan berbasis Teori Set, taruhan terbaik Anda adalah mengonversi WHEREkondisi apa pun yang dapat dikonversi menjadi jenis JOIN(dalam atau luar) dan minta pernyataan itu di-refactored. Ini termasuk IN subselectdan EXISTS subselectdan semua ketentuan lain dalam WHEREklausa yang berisi kata SELECT. Jika Anda melakukan ini pada kedua pernyataan SQL, Anda akan memiliki FROMklausa baru yang mewakili logika / matematika berbasis set yang Anda minati. Kemudian Anda bisa membandingkan dua pernyataan secara visual. Jika Anda mencari cara otomatis untuk melakukan semua ini, saya tidak tahu alat yang bisa melakukan ini.

Antrian Mann
sumber