DRedMTL: Schnelle inkrementelle Aktualisierung von DatalogMTL‑Materialisierungen

DatalogMTL erweitert die klassische Datalog‑Sprache um Metric Temporal Logic (MTL) und ermöglicht damit präzises, zeitbasiertes Schlussfolgern über Daten, die sich im Zeitverlauf verändern. Durch die Einbindung von MTL können komplexe zeitliche Abhängigkeiten modelliert und abgefragt werden, was in vielen Anwendungsbereichen – etwa in der Ereignisverarbeitung oder im Internet‑der‑Dinge – von entscheidender Bedeutung ist.

Aktuelle Verfahren zur Materialisierung von DatalogMTL‑Programmen, sei es auf Basis von Automata oder durch vollständige Neuberechnung, bieten zwar theoretische Korrektheit, bleiben jedoch bei dynamischen Datenupdates ineffizient. In der Praxis, wo Daten häufig hinzukommen oder geändert werden, ist eine schnelle, inkrementelle Aktualisierung unerlässlich, um Echtzeit‑Antworten zu gewährleisten.

Die neue Methode DRedMTL löst dieses Problem, indem sie den bewährten DRed‑Algorithmus für klassische Datalog‑Materialisierungen adaptiert und um spezielle Operatoren für periodische Intervalle erweitert. Während eine herkömmliche Datalog‑Materialisierung lediglich aus einer endlichen Menge von Fakten besteht, enthält eine DatalogMTL‑Materialisierung zusätzlich periodische Intervalle, die die vollständige Auswertung durch Unfolding beschreiben. DRedMTL verarbeitet diese Intervalle effizient und aktualisiert die Materialisierung ohne vollständige Neuberechnung.

In einer Implementierung, die auf öffentlich zugänglichen Datensätzen getestet wurde, zeigte DRedMTL in den meisten Fällen eine deutlich bessere Laufzeit als die klassische Neuberechnung. Die Performanceverbesserung reicht dabei häufig um ein Vielfaches und kann in einigen Fällen sogar um mehrere Größenordnungen liegen, was die Methode zu einer vielversprechenden Lösung für zeitkritische Anwendungen macht.