Могут ли объединения быть распараллелены?

9

Предположим, мы хотим объединить два отношения в предикате. Это в NC?

Я понимаю, что доказательство того, что он не находится в NC, будет равносильно доказательству того, что пNС , поэтому я бы принял доказательство того, что это открытая проблема, в качестве ответа.

Меня интересует как общий случай, так и конкретные случаи (например, возможно, с какой-то конкретной структурой данных ее можно распараллелить).

РЕДАКТИРОВАТЬ: внести некоторые пояснения из комментариев в этот пост:

  • Мы могли бы рассмотреть эквисоединение A,Иксзнак равноВ,Y . На одном процессоре алгоритм на основе хеша работает в О(|A|+|В|) и это лучшее, что мы можем сделать, так как мы должны читать каждый набор
  • Если предикат является «черным ящиком», где мы должны проверять каждую пару, естьпары, и каждая из них может быть или нет, так что возможностей. Проверка каждой пары делит возможности пополам, поэтому лучшее, что мы можем сделать, это .|A||В|2aбО(aб)

Может ли какой-либо из них (или какой-либо третий тип объединения) быть улучшен до на нескольких процессорах?журналКN

Xodarap
источник
Если этот вопрос мотивирован практической проблемой, имейте в виду, что NC может быть не самым подходящим понятием «параллелизуемость».
Рафаэль
@ Рафаэль: это не так, но не могли бы вы дать ссылку на вопрос, почему? Я могу задать это как отдельный вопрос, если это более уместно.
Xodarap
Мне не понятно, о чем вы спрашиваете. На каком базовом языке запросов реляционной базы данных вы добавляете оператор соединения? Или вы задаете сложность запросов, которые содержат только операторы соединения? Или же ваш реальный вопрос заключается в том, можно ли запускать операторы соединения "параллельно", чтобы добиться большей сложности во времени? (аналогично тому, как сказать, что AND может выполняться параллельно). Также обратите внимание, что (безопасные) SQL-запросы соответствуют FOL (Count).
Каве
Или вы спрашиваете, каковы наиболее известные верхняя и нижняя границы (классы сложности) для сложности, вычисляющей объединение с учетом двух реляционных баз данных в качестве входных данных.
Каве
2
@Xodarap: Вы можете найти ответы и комментарии на этот мой поучительный вопрос; Я знаю, что сделал. Крускал и соавт. (1990) также хорошо читается.
Рафаэль

Ответы:

1

N2(N2)

Xodarap
источник
Если вы собираетесь взять ИЛИ, глубина будет логарифмической.
sdcvvc
@sdcvvc: Достаточно справедливо. В крайнем случае вы можете закодировать 3SAT в реляционном исчислении, так что этот результат действительно верен, только если ваш выбор прост (то есть постоянное время).
Xodarap