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

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?

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 ′$R$$S$$(R', T)$$(T, S')$$R'$$S'$$T$

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 = (\epsilon, \epsilon, ..., \epsilon)$$S'$$S'$R LEFT JOIN S$(r, t, s)$$(R', T, S')$

1. $(r, t)$ adalah sebuah tupel dalam ;$R$
2. (a) adalah tupel atau (b) ;S s = $(t, s)$$S$$s = w$
3. Jika ada di set untuk , maka tidak ada di set.s ≠ w ( r , t , w $(r, t, s)$$s \neq w$$(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$$(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)\}$( 1 , 2 , 3 , ϵ ) ( 1 , 2 , 3 , 4 ) s = $\{(1, 2, 3, 4),(1, 2, 3, 6), (1, 2, 3, \epsilon),(4, 5, 6, \epsilon)\}$$(1, 2, 3, \epsilon)$$(1, 2, 3, 4)${ ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 3 , 6 ) , ( 4 , 5 , 6 , ϵ ) $s = 4 \neq \epsilon = w$$\{(1, 2, 3, 4), (1, 2, 3, 6), (4, 5, 6, \epsilon)\}$

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 $R$$S$$R$$S$$T$$T$$R$$S$EQUIJOIN$R$$R$$T$$R$$S$; 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 ) $R$$(R', T)$$w$$S'$JOIN$(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)$$R$EQUIJOIN$(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 $R'$$S'$DIFFERENCE$S$$S$RENAMEJOIN$(t, t')$$(T, T')$$t = t'$SELECT$(t, t')$$t=t'$$t'=w$$S$$(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)\}$$S$RENAME$T'${ ( 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 JOIN$R${ ( 1 , 2 , ϵ , ϵ ) } { ( 1 , 2 ) $\{(1, 2, \epsilon, \epsilon), (3, 4, 3, 4), (5, 6, 5, 6)\}$SELECT$\{(1, 2, \epsilon, \epsilon)\}$PROJECT$\{(1, 2)\}$, jawaban yang diinginkan.

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.