As junções podem ser paralelizadas?

9

Suponha que desejemos unir duas relações em um predicado. Isso está no NC?

Percebo que uma prova de que não está na NC equivaleria a uma prova de que , então aceitaria a evidência de que é um problema em aberto como resposta.PNC

Estou interessado no caso geral e também nos casos específicos (por exemplo, talvez com alguma estrutura de dados específica, ela possa ser paralelizada).

EDIT: para trazer alguns esclarecimentos dos comentários para este post:

  • Poderíamos considerar um equijoin . Em um único processador, um algoritmo baseado em hash é executado em e é o melhor que podemos fazer, pois precisamos ler cada conjuntoO ( | A | + | B | )A.x=B.yO(|A|+|B|)
  • Se o predicado é uma "caixa preta" onde temos que verificar cada par, existempares, e cada um poderia estar dentro ou não, então possibilidades. Verificar cada par divide as possibilidades pela metade, então o melhor que podemos fazer é .2 a b O ( a b )|A||B|2abO(ab)

Um desses (ou algum terceiro tipo de junção) poderia ser aprimorado para em vários processadores?logkn

Xodarap
fonte
Se essa questão for motivada por um problema prático, lembre-se de que NC pode não ser a noção mais adequada de "paralelizável".
Raphael
@ Rafael: não é, mas você poderia ligar para algo sobre o porquê? Posso fazer isso como uma pergunta separada, se for mais apropriado.
Xodarap
Não está claro para mim o que você está perguntando. Qual é a linguagem base de consulta do banco de dados relacional que você está adicionando ao operador de junção? Ou você está perguntando a complexidade das consultas que contêm apenas operadores de junção? Ou sua verdadeira pergunta é se é possível executar operadores de junção "em paralelo" para obter uma melhor complexidade de tempo? (semelhante à maneira como dizer AND pode ser feito em paralelo) Observe também que as consultas SQL (seguras) correspondem a FOL (Count).
Kaveh
Ou você está perguntando quais são as classes superior e superior (classes de complexidade) mais conhecidas sobre a complexidade que calcula a junção, dados como entrada dois bancos de dados relacionais.
Kaveh
2
@Xodarap: Você pode encontrar as respostas e comentários sobre esta pergunta minha instrutivos; Eu sei que sim. Kruskal et al. (1990) também é uma boa leitura.
Raphael

Respostas:

1

n2 processadores podem comparar todas as possibilidades de em profundidade constante; portanto, sim, está em NC.(n2)

Xodarap
fonte
Se você for fazer OR, a profundidade será logarítmica.
Sdcvvc 07/07
@sdcvvc: justo o suficiente. No extremo, você pode codificar 3SAT no cálculo relacional; portanto, esse resultado só será válido se suas seleções forem simples (ou seja, tempo constante).
Xodarap 07/07