Stiptheidsaspecten van gedistribueerde database stream processing. (R-5472)

Een database stream is een voortdurend groeiende sequentie van data items. Bijvoorbeeld, als de input stream bestaat uit metingen van verkeersdrukte op bepaalde wegen, dan kan een controlesysteem een output stream opbouwen waarin de maximumsnelheid dynamisch wordt ingesteld afhankelijk van de huidige drukte. Het is uitdagend om zulke streams te verwerken, omdat binnenkomende data door haar hoge snelheid en grote volume vaak niet kan opgeslagen worden. In de plaats daarvan gebruikt men zogenaamde "on the fly" verwerking, waarbij data items enkel met elkaar in verband worden gebracht als ze in eenzelfde tijdsvenster voorkomen, bijvoorbeeld als hun tijdstippen ten hoogste tien seconden uit elkaar liggen. Bovendien, zijn de bovenstaande systemen vaak geïmplementeerd over een netwerk, om de berekening te verdelen over meerdere computers. Er bestaan veel programmeertalen en gedistribueerde uitvoeringsmechanismen voor het verwerken van database streams. Maar de programmeur verwacht vaak een maximale vertraging op de items in de output stream. We zullen dit de gewenste output timing noemen. Helaas zijn veel uitvoeringsmechanismen gevoelig voor vertragingen ten gevolge van hardware, scheduling policies, en asynchrone berichten in netwerken. Zulke vertragingen kunnen er voor zorgen dat de feitelijke output timing vaak te laat is in vergelijking met de gewenste output timing. De output items kunnen in principe zelfs steeds sterker vertraagd worden naarmate de tijd verstrijkt. Omdat zulke timing problemen nog niet goed begrepen zijn, willen we een natuurlijke theorie bekomen om te kunnen redeneren over hoe goed of hoe slecht de feitelijke output timing van een systeem is in vergelijking met de gewenste output timing. Via benaderingen van de gewenste output timing, zoeken we concreet naar praktische inzichten over het verband tussen de snelheid van een systeem en de nauwkeurigheid van de output timing.

Trefwoorden:DATABASE THEORIE

Disciplines:Toegepaste wiskunde, Artificiële intelligentie, Cognitieve wetenschappen en intelligente systemen