Project R-13653

Gedissocieerde Verwerking van Recursieve Queries onder Updates (Onderzoek)

Efficiënte ondervraging van steeds veranderende gegevens is een belangrijke vereiste in hedendaagse toepassingen. Recent onderzoek heeft aangetoond dat queries die niet efficient verwerkt worden onder updates door conventionele algoritmes, wel efficiënt verwerkt kunnen worden door de verwerking te "dissociëren" in twee fases. (1) Een update fase waarin enkel een beknopte "voorstelling" van het queryresultaat bijgehouden wordt onder updates. (2) Een ophaalfase waarin deze voorstelling gebruikt om het resultaat efficiënt op te sommen. De realisatie van gedissocieerde update verwerking in concrete systemen heeft verschillende grootordes efficiëntiewinsten aangetoond. Tot op heden is gedissocieerde update verwerking echter alleen onderzocht voor querytalen zonder recursie. Dit staat in schril contrast tot de stijgende aandacht voor talen met recursie zoals Datalog, welke analyses ondersteunt in diverse domeinen zoals graafanalyse en gedistribueerde ML. In dit project postuleren we dat door gedissocieerde updateverwerking ook voor recursieve talen te ontwikkelen we mogelijk de deur openen naar vergelijkbare prestatieverbeteringen in de recursieve context. Concreet stellen we voor om (1) de klasse van recursieve queries met ideale complexiteit in het gedissocieerde raamwerk te bestuderen; (2) gedissocieerde updateverwerking te integreren in de evaluatie van Datalog programma's; en (3) te bestuderen hoe structurele eigenschappen van update-streams uitgebuit kunnen worden.

01 januari 2023 - 31 december 2026