< Terug naar vorige pagina

Project

Optimale join algoritmen voor moderne gedistribueerde data systemen (FWOAL1008)

In dit onderzoeksvoorstel zijn we geïnteresseerd in gedistribueerde
algoritmen voor query evaluatie met formele optimaliteitsgaranties.
Met de opkomst van big data en de groeiende populariteit van
clusters van machines voor big data-analyse, is er een grote
interesse in het begrijpen van de complexiteit van query operatoren
in deze setting. Query optimalisatie is een klassiek database
probleem, maar de nieuwe systemen hebben architecturen die
radicaal verschillen met traditionele databasesystemen en vereisen
daarom algoritmen die geoptimaliseerd zijn voor andere dan de
klassieke kostmodellen. In deze nieuwe systemen is data meestal
gepartitioneerd over machines die de gehele partitie in hun
geheugen bewaren. De dominerende kost in deze systemen is de
communicatie kost: de hoeveelheid data verplaatsing over het
netwerk en het aantal synchronisatie rondes tussen machines. Dit
staat in sterk contrast met de externe geheugen architectuur van
traditionele databasesystemen die worden uitgevoerd op een enkele
machine met het aantal disk interacties als dominerende kost. Een
bijzonder uitdagende operatie in de nieuwe cluster omgevingen is de
relationele join, waarvan de uitvoering meestal een grote
verplaatsing van data over het netwerk vereist. In dit
onderzoeksvoorstel zullen we de precieze complexiteit van join
query’s voor clusters van machines bestuderen en algoritmen
ontwikkelen voor het berekenen van query’s met formele garanties
op de communicatiekost.
Datum:1 jan 2021 →  Heden
Trefwoorden:Database management, Algoritmen voor optimale verwerking van zoekopdrachten
Disciplines:Analyse van algoritmen en complexiteit, Databasesystemen en -architecturen, Databasetheorie, Gedistribueerde systemen, Workflow-, proces- en databasemanagement