Apakah operasi 'perbedaan' menambah ekspresif ke bahasa permintaan yang sudah termasuk 'bergabung'?

19

Operator perbedaan set (misalnya, EXCEPTdalam beberapa varian SQL) adalah salah satu dari banyak operator dasar aljabar relasional. Namun, ada beberapa database yang tidak mendukung operator perbedaan set secara langsung, tetapi yang mendukung LEFT JOIN(semacam gabungan luar), dan dalam praktiknya ini dapat digunakan sebagai pengganti operasi perbedaan set untuk mencapai efek yang sama.

Apakah ini berarti bahwa kekuatan ekspresif dari bahasa query adalah sama, bahkan tanpa operator perbedaan, selama LEFT JOINoperator dipertahankan? Bagaimana seseorang membuktikan fakta ini?

Ken Li
sumber
1
Untuk menunjukkan bahwa mereka memiliki kekuatan ekspresif yang sama menunjukkan bahwa operasi perbedaan dapat dibangun dengan operasi join kiri (dan mungkin operasi lain dalam RA).
sxd

Jawaban:

14

Dalam aljabar relasional, pertama-tama kita akan memberikan definisi informal tentang bergabung (luar) kiri, dan melanjutkan untuk membuktikan bahwa itu, penggantian nama, seleksi, bergabung dan proyeksi dapat membangun perbedaan, serta perbedaan itu, seleksi dan persatuan dapat digunakan untuk membangun kiri (luar) bergabung. Sebenarnya, kita akan berakhir melakukannya dengan urutan terbalik: kita akan menunjukkan bagaimana membangun gabungan kiri menggunakan perbedaan, dan kemudian kita akan menunjukkan cara membangun perbedaan menggunakan gabungan kiri.

Biarkan dan memiliki skema dan , di mana dan adalah himpunan atribut dalam satu skema tetapi tidak yang lain, dan adalah himpunan atribut yang sama.S ( R , T ) ( T , S ) R S TRS(R,T)(T,S)RST

Biarkan menjadi tuple nol untuk skema . Yaitu, itu adalah tuple yang terdiri dari semua nilai nol untuk setiap atribut . Kemudian, kita mendefinisikan gabungan luar kiri sebagai berikut: adalah himpunan semua tupel milik skema mana ...S ' S ' ( r , t , s ) ( R ' , T , S ' )w=(ϵ,ϵ,...,ϵ)SSR LEFT JOIN S(r,t,s)(R,T,S)

  1. R(r,t) adalah sebuah tupel dalam ;R
  2. (a) adalah tupel atau (b) ;S s = w(t,s)Ss=w
  3. Jika ada di set untuk , maka tidak ada di set.s w ( r , t , w )(r,t,s)sw(r,t,w)

Contoh: Skema adalah , skema adalah , dan kami memiliki itu dan . Dengan (1) dan (2) kita mendapatkan hasil antara . Dengan (3) kita harus menghapus , karena kita memiliki (misalnya) dan . Dengan demikian, kita dibiarkan dengan , hasil yang diharapkan untuk gabungan kiri.( A 1 , A 2 , A 3 ) S ( A 2 , A 3 , A 4 ) R = { ( 1 , 2 , 3 ) , ( 4 , 5 , 6 ) } S = { ( 2 , 3 , 4 ) , ( 2 , 3 , 6 ) } {R(A1,A2,A3)S(A2,A3,A4)R={(1,2,3),(4,5,6)}S={(2,3,4),(2,3,6)}( 1 , 2 , 3 , ϵ ) ( 1 , 2 , 3 , 4 ) s = 4{(1,2,3,4),(1,2,3,6),(1,2,3,ϵ),(4,5,6,ϵ)}(1,2,3,ϵ)(1,2,3,4){ ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 4 , 5 , 6 , ϵ ) }s=4ϵ=w{(1,2,3,4),(1,2,3,6),(4,5,6,ϵ)}

Teorema: R LEFT JOIN Ssetara dengan (R EQUIJOIN S) UNION ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w).

Bukti: (R EQUIJOIN S)memberi kita segala yang dibutuhkan oleh (1) dan (2a). Kami mengklaim yang ((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)memberi kami segala bentuk yang (r, t, w)diperlukan oleh (2b) dan (3).

Untuk melihat, pemberitahuan ini pertama bahwa (((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R)adalah himpunan semua tupel di yang tidak ada tuple sesuai pada . Untuk melihat itu, cukup untuk dicatat bahwa dengan memproyeksikan atribut umum dari dan (set atribut ) dan mengambil perbedaan, satu dibiarkan dengan semua dan hanya tupel (dengan skema ) yang diwakili dalam tetapi tidak . Dengan dengan , kami memulihkan semua dan hanya tupel di yang memiliki nilai untuk atribut di yang ada di tetapi tidak diS R S T T R S R R T R SRSRSTTRSEQUIJOINRRTRS; yaitu, set himpunan tuple yang telah kita klaim sejauh ini.

Selanjutnya, perhatikan bahwa skema adalah (((PROJECT_T R) DIFFERENCE (PROJECT_T S))sama dengan (yaitu, ), sedangkan skema adalah . The karena operasi adalah produk Cartesian, kita kita mendapatkan semua tupel dari bentuk di mana tidak ada di sesuai dengan di .( R , T ) w S ( r , t , w ) ( t , s ) S ( r , t ) RR(R,T)wSJOIN(r,t,w)(t,s)S(r,t)R

Untuk melihat bahwa ini adalah set tupel yang perlu kita tambahkan untuk R EQUIJOIN Smembangun R LEFT JOIN S, pertimbangkan hal berikut: dengan konstruksi, (3) puas, karena R EQUIJOIN Stidak dapat mengandung jika mengandung (jika ya, maka bagian kedua yang berisi akan menjadi kontradiksi); jika kita menambahkan yang lain tidak dalam , maka akan ada dalam sesuai dengan dalam , dan dengan definisi , juga akan menjadi , kontradiksi (3). Ini melengkapi buktinya.( r , t , w ) ( r , t , w ) ( r , t , w ) ( t , s ) S ( r , t ) R ( r , t , s )(r,t,s)((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)(r,t,w)(r,t,w)(r,t,w)((((PROJECT_T R) DIFFERENCE (PROJECT_T S)) EQUIJOIN R) JOIN w)(t,s)S(r,t)REQUIJOIN(r,t,s)R LEFT JOIN S

Sekarang kami menunjukkan bahwa join kiri dapat digunakan untuk membangun perbedaan:

Teorema: R DIFFERENCE Ssetara denganPROJECT_T(SELECT_{t'=w}(R LEFT JOIN (SELECT_{s=s'}(((S JOIN RENAME_{T->T'}(S)))))))

Bukti: Perhatikan bahwa di sini, dan kosong, karena semua atribut dibagikan agar masuk akal. Pertama, kita membuat relasi baru dari dengan menduplikasi set atribut dalam (ditangani oleh dan ) sehingga terdiri dari tupel pada set atribut mana (ditangani oleh itu ). Gabung kiri meninggalkan kita dengan tupel dalam bentuk mana atau . Sekarang, untuk menghilangkan entri yang juga muncul di , kita harus menyimpan hanya tupel formulirS S S ( t , t ) ( T , T ) t = t ( t , t ) t = t t = w S ( t , w ) T RSDIFFERENCESSRENAMEJOIN(t,t)(T,T)t=tSELECT(t,t)t=tt=wS(t,w), yang ditangani oleh pihak terluar SELECT. Yang terakhir PROJECTmenghilangkan atribut sementara set dan meninggalkan kita dengan perbedaan dalam hal skema asli.T

Contoh: Misalkan dan . Kami pertama kali mendapatkan dengan set atribut d : . The Operasi memberi kita produk Cartesian dengan semua sembilan pasangan mungkin; set ini tidak ditulis di sini karena alasan format. The kemudian pares bawah ini untuk . The dengan memberikan . The memberikan . The memberikanS = { ( 3 , 4 ) , ( 5 , 6 ) , ( 7 , 8 ) } S T { ( 3 , 4 ) , ( 5 , 6 ) , ( 7 ,R={(1,2),(3,4),(5,6)}S={(3,4),(5,6),(7,8)}SRENAMET{ ( 3 , 4 , 3 , 4 ) , ( 5 , 6 , 5 , 6 ) , ( 7 , 8 , 7 , 8 ) } R { ( 1 , 2 , ϵ , ϵ ) , ( 3 , 4 , 3 , 4 ) , ( 5 , 6 ,{(3,4),(5,6),(7,8)}JOINSELECT{(3,4,3,4),(5,6,5,6),(7,8,7,8)}LEFT JOINR{ ( 1 , 2 , ϵ , ϵ ) } { ( 1 , 2 ) }{(1,2,ϵ,ϵ),(3,4,3,4),(5,6,5,6)}SELECT{(1,2,ϵ,ϵ)}PROJECT{(1,2)}, jawaban yang diinginkan.

Patrick87
sumber
Harap edit posting Anda untuk menggunakan sintaks LaTeX. Mulailah dengan melampirkan semua rumus Anda di $ simbol (misalnya, $ (1,2) $ menjadi ). Kata kunci seperti select harus diletakkan di `(misalnya,` SELECT` menjadi ). (1,2)SELECT
Raphael
@ Raphael Terima kasih telah menunjukkan bahwa saya harus menggunakan LaTeX untuk ini. Saya telah melakukan upaya dengan niat baik di LaTeX'ing matematika dan backtick'ing kode ... tolong beri tahu saya jika ada hal lain yang harus saya lakukan. Terima kasih lagi!
Patrick87
Terima kasih banyak! Anda mungkin ingin mempertimbangkan $ $ ... $ $ untuk membuat potongan matematika yang indentasi (bukan inline). Ini sering dapat meningkatkan keterbacaan jika digunakan dengan benar. MathJax juga mendukung persamaan bernomor tetapi saya tidak yakin bagaimana melakukan ini.
Raphael
Saya pikir logika Anda salah di sini. Anda menggunakan DIFFERENCEuntuk mendefinisikan LEFT JOIN, dan kemudian Anda gunakan LEFT JOINuntuk mengekspresikan DIFFERENCE, menyimpulkan bahwa SQL dapat melakukannya tanpa itu. Agar ini valid, Anda harus menyatakan LEFT JOINdalam hal operator selainDIFFERENCE , dan kemudian membuktikan bahwa DIFFERENCEitu setara dengan itu.
Janoma
@ Janoma Saya tidak berpikir itu diperlukan ... kami mencoba untuk menunjukkan bahwa perbedaan dapat dinyatakan dalam gabungan kiri, jadi fungsi gabungan kiri diasumsikan. Pikirkan tentang hal ini: jika apa yang Anda katakan pantas, saya dapat mengklaim bahwa KIRI BERGABUNG adalah operasi "mendasar" atau "perlu", dan menuntut agar Anda mendefinisikan PERBEDAAN dalam hal operator lain, tetapi bukan KIRI BERGABUNG. Saya telah menunjukkan bahwa masing-masing dapat mensimulasikan yang lain, sehingga tidak ada yang lebih atau kurang "mendasar" daripada yang lain ... apa yang membuat PERBEDAAN istimewa? Di prop. logika, BUKAN dan DAN lengkap, seperti ATAU dan BUKAN; Anda tidak membutuhkan ketiganya.
Patrick87
-1

LEFT JOIN seperti yang diimplementasikan oleh SQL, tidak menghasilkan hubungan sebagai hasilnya (karena beberapa atribut dari hasilnya tidak akan memiliki nilai).

Ergo, KIRI BERGABUNG seperti yang diterapkan oleh SQL, bukan merupakan mitra langsung dari operator aljabar relasional apa pun.

Ergo, Operator perbedaan relasional tidak dapat dinyatakan dalam LEFT JOIN (karena LEFT JOIN tidak mungkin menjadi bagian dari aljabar relasional, ini karena LEFT JOIN menghasilkan sesuatu yang bukan suatu hubungan, sehingga melanggar penutupan aljabar).

Setiap set operator primitif dari relasional aljabar yang memenuhi penutupan yang saya tahu, selalu mencakup perbedaan baik relasional atau semidifference relasional lain.

Erwin Smout
sumber