Vi studerar problemet med att beräkna en konjunktiv fråga q parallellt, med hjälp av p servrar, på en stor databas. Vi överväger algoritmer med en omgång kommunikation, och studera komplexiteten i kommunikationen. Vi är särskilt intresserade av det fall där datan är skev, vilket är en stor utmaning för skalbar parallell frågebehandling. Vi etablerar ett tätt samband mellan den fraktionerade kanten packning av frågan och mängden kommunikation i två fall. För det första, när den enda statistiken över databasen är kardinaliteterna i indatarelationerna, och datan är skev-fri, tillhandahåller vi matchande övre och nedre gränser (upp till en polylogaritmisk faktor av p) uttryckta i bråkiga kanter förpackningar av frågan q. För det andra, i fallet när relationerna är skeva och de tunga hitters och deras frekvenser är kända, vi ger övre och nedre gränser uttryckta i form av packningar av kvarvarande frågor som erhålls genom att specialisera frågan till en tung hitter. Alla våra nedre gränser uttrycks i den starkaste formen, eftersom antalet bitar som behövs för att kommuniceras mellan processorer med obegränsad beräkningskraft. Våra resultat generaliserar tidigare resultat på enhetliga databaser (där varje relation är en matchning) [4], och lägre gränser för MapReduce modellen [1].
Beame, Koutris och Suciu REF visade sig vara en matchande övre och nedre gräns för den mängd kommunikation som behövs för att beräkna en fullständig konjunktiv fråga utan självkontakter i en kommunikationsrunda.
Skew in parallel query processing
{'venue': "PODS '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}