Czy sprzężenia mogą być równoległe?

Załóżmy, że chcemy połączyć dwie relacje w predykacie. Czy to jest w NC?

Zdaję sobie sprawę, że dowód, że nie ma go w NC, będzie równoznaczny z dowodem, że , więc przyjmuję dowód, że jest to otwarty problem jako odpowiedź. $P\not=NC$

Interesuje mnie zarówno ogólny przypadek, jak i konkretne przypadki (np. Może z pewną określoną strukturą danych można je zrównoleglić).

EDYCJA: aby wprowadzić wyjaśnienia do komentarzy w tym poście:

Możemy rozważyć ekwiwalent . Na pojedynczym procesorze algorytm oparty na haszowaniu działa w i jest to najlepsze, co możemy zrobić, ponieważ musimy czytać każdy zestaw $A.x = B.y$ $O(|A|+|B|)$
Jeśli predykatem jest „czarna skrzynka”, w której musimy sprawdzić każdą parę, sąpary, a każda z nich może być lub nie, więc możliwości. Sprawdzanie każdej pary dzieli możliwości na pół, więc najlepiej, co możemy zrobić, to . $|A|\cdot|B|$ $2^{ab}$ $O(ab)$

Czy któryś z tych (lub jakiś trzeci typ łączenia) mógłby zostać ulepszony do na wielu procesorach? $\log^k n$

— Xodarap
źródło

Jeśli pytanie jest uzasadnione problemem praktycznym, należy pamiętać, że NC może nie być najbardziej odpowiednim pojęciem „równoległego”.

— Raphael

@Raphael: tak nie jest, ale czy możesz link do czegoś o tym, dlaczego? Mogę zadać to jako osobne pytanie, jeśli jest to bardziej odpowiednie.

— Xodarap

Nie jest dla mnie jasne, o co pytasz. Jaki jest podstawowy język zapytań relacyjnej bazy danych, do którego dodajesz operator łączenia? A może pytasz o złożoność zapytań zawierających tylko operatory łączenia? A może Twoim prawdziwym pytaniem jest to, czy możliwe jest uruchomienie operatorów łączenia „równolegle”, aby uzyskać większą złożoność czasu? (podobny do tego, że powiedzenie AND można wykonać równolegle) Należy również pamiętać, że (bezpieczne) zapytania SQL odpowiadają FOL (Count).

— Kaveh

A może pytasz, jakie są najbardziej znane górne i dolne granice (klasy złożoności) w złożoności obliczającej połączenie, biorąc pod uwagę dwie relacyjne bazy danych jako dane wejściowe.

— Kaveh

@Xodarap: Odpowiedzi i komentarze na to pytanie mogą być dla mnie pouczające; Wiem, że tak. Kruskal i in. (1990) to także dobra lektura.

— Raphael

$n^2$ procesory mogą porównywać wszystkie możliwości na stałej głębokości, więc tak, jest w NC. ${n \choose 2}$

— Xodarap
źródło

Jeśli zamierzasz wziąć OR, głębokość będzie logarytmiczna.

— sdcvvc,

@sdcvvc: Wystarczająco uczciwy. W skrajności możesz zakodować 3SAT w rachunku relacyjnym, więc ten wynik naprawdę działa tylko wtedy, gdy twoje wybory są proste (tj. Stały czas).

— Xodarap,