Bisakah gabungan diparalelkan?

9

Misalkan kita ingin menggabungkan dua relasi dengan predikat. Apakah ini di NC?

Saya menyadari bahwa buktinya tidak berada di NC akan menjadi bukti bahwa , jadi saya akan menerima bukti itu menjadi masalah terbuka sebagai jawaban.PNC

Saya tertarik pada kasus umum serta kasus-kasus tertentu (misalnya mungkin dengan beberapa struktur data tertentu dapat diparalelkan).

EDIT: untuk membawa beberapa klarifikasi dari komentar ke dalam posting ini:

  • Kita dapat mempertimbangkan equijoin . Pada satu prosesor, algoritma berbasis hash berjalan di dan ini adalah yang terbaik yang bisa kita lakukan karena kita harus membaca setiap setA.x=B.yO(|A|+|B|)
  • Jika predikatnya adalah "kotak hitam" di mana kita harus memeriksa setiap pasangan, adaberpasangan, dan masing-masing bisa dalam atau tidak, jadi kemungkinan. Memeriksa setiap pasangan membagi kemungkinan menjadi dua, sehingga yang terbaik yang bisa kita lakukan adalah .|A||B|2abO(ab)

Bisakah salah satu dari ini (atau tipe gabungan ketiga) ditingkatkan ke di banyak prosesor?logkn

Xodarap
sumber
Jika pertanyaan ini dilatarbelakangi oleh masalah praktis, ingatlah bahwa NC mungkin bukan gagasan yang paling cocok tentang "yang bisa disejajarkan".
Raphael
@ Raphael: tidak, tapi bisakah Anda menautkan ke sesuatu tentang mengapa? Saya dapat mengajukan ini sebagai pertanyaan terpisah jika itu lebih tepat.
Xodarap
Tidak jelas bagi saya apa yang Anda minta. Apa bahasa query basis data relasional dasar yang Anda tambahkan ke operator gabung? Atau apakah Anda menanyakan kompleksitas kueri yang hanya berisi operator gabungan? Atau apakah pertanyaan Anda sebenarnya adalah apakah mungkin untuk menjalankan operator yang bergabung secara paralel untuk mencapai kompleksitas waktu yang lebih baik? (Mirip dengan cara yang mengatakan AND dapat dilakukan secara paralel) Juga perhatikan bahwa (aman) kueri SQL sesuai dengan FOL (Hitungan).
Kaveh
Atau apakah Anda bertanya apa yang paling dikenal sebagai batas atas dan batas bawah (kompleksitas kelas) pada kompleksitas komputasi gabungan yang diberikan dua database relasional sebagai input.
Kaveh
2
@Xodarap: Anda mungkin menemukan jawaban dan komentar tentang pertanyaan ini tentang instruktif saya ; Saya tahu saya melakukannya. Kruskal et al. (1990) juga merupakan bacaan yang bagus.
Raphael

Jawaban:

1

n2(n2)

Xodarap
sumber
Jika Anda akan mengambil OR, kedalaman akan menjadi logaritmik.
sdcvvc
@ sdcvvc: Cukup adil. Pada ekstrem Anda bisa menyandikan 3SAT dalam kalkulus relasional, sehingga hasil ini benar-benar hanya berlaku jika pilihan Anda sederhana (yaitu waktu yang konstan).
Xodarap