🤖 AI

Efficient Temporal Datalog Materialisation for Composite Event Recognition

Dieser Beitrag adressiert die Herausforderung des Vergleichs unterschiedlicher Ereignisspezifikationssprachen durch ihre Abbildung auf ein einheitliches Temporal-Datalog-Framework und die Einführung von Streaming-Trigger-Graphen, um eine effiziente und generalisierbare Erkennung zusammengesetzter Ereignisse über Hochgeschwindigkeits-Datenströme zu ermöglichen.

Ursprüngliche Autoren: Periklis Mantenoglou

Veröffentlicht 2026-05-06

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Periklis Mantenoglou

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der Dirigent eines riesigen, hochgeschwindigkeitsfähigen Orchesters, in dem jeder Musiker ein anderes Instrument spielt und sich die Musik jede einzelne Sekunde ändert. Ihre Aufgabe besteht darin, spezifische, komplexe Muster in der Musik zu erkennen – wie etwa „eine Geige spielt einen hohen Ton, während eine Trommel drei Mal hintereinander einen langsamen Rhythmus schlägt" – und sofort eine rote Flagge zu hissen, falls ein solches Muster auftritt.

Dies ist die Herausforderung der Erkennung zusammengesetzter Ereignisse (Composite Event Recognition, CER). In der realen Welt geht es dabei nicht nur um Musik, sondern darum, Sicherheitsbedrohungen in einer Smart City zu identifizieren, Betrug in einer Bank aufzudecken oder eine Flotte von Lieferwagen zu überwachen. Das Problem besteht darin, dass verschiedene Teams unterschiedliche „Partituren" (Sprachen) verwenden, um diese Muster zu beschreiben, und ihre „Dirigenten" (Reasoner) nicht miteinander kommunizieren können.

Hier ist, wie dieses Papier dieses Problem löst, unter Verwendung einfacher Analogien:

1. Das Problem: Zu viele Dialekte

Stellen Sie sich eine Gruppe von Detektiven vor, die versuchen, ein Verbrechen aufzuklären. Ein Detektiv spricht „Event Calculus", ein anderer „LARS" und ein dritter „Temporal Datalog". Sie alle beschreiben dieselbe Tatortszene, verwenden jedoch unterschiedliche Wörter und Satzstrukturen.

Das Problem: Wenn Detektiv A einen Hinweis findet, versteht Detektiv B diesen möglicherweise nicht. Sie können ihre Notizen nicht leicht vergleichen und können nicht den besten Detektiv für die spezifische Aufgabe einsetzen, da die Sprachen nicht übereinstimmen.
Das Ziel des Papiers: Schaffung eines „Universalübersetzers", der die spezifischen Dialekte von Event Calculus und LARS in eine einzige, gemeinsame Sprache namens Temporal Datalog→⊖ umwandelt.

2. Der Universalübersetzer: Temporal Datalog→⊖

Die Autoren haben eine spezielle Version einer Logiksprache (eine Menge von Regeln für Computer) erstellt, die als dieser gemeinsame Boden dient.

Keine Zeitreise: Diese Sprache hat eine strikte Regel: Sie können nur in die Vergangenheit oder die Gegenwart blicken. Sie können nicht in die Zukunft blicken. Dies ist so, als würde man sagen: „Ich kann nur Entscheidungen treffen, die auf dem basieren, was bereits geschehen ist oder gerade jetzt passiert." Dies verhindert, dass das System verwirrt wird oder feststeckt, weil es auf Daten wartet, die noch nicht eingetroffen sind.
Stratifizierte Negation: Dies ist eine ausgefallene Art zu sagen, dass die Regeln in Schichten organisiert sind, um Widersprüche zu vermeiden. Stellen Sie sich ein Gebäude mit Etagen vor. Sie können nur von einer höheren Etage nach unten blicken, um zu prüfen, was sich in einer niedrigeren Etage befindet, niemals umgekehrt. Dies hält die Logik sauber und verhindert, dass das System in eine Schleife gerät: „Ist es wahr? Nein, ist es wahr? Nein..."

3. Der Motor: Streaming Trigger Graphs (STGs)

Sobald die Regeln in diese gemeinsame Sprache übersetzt sind, benötigt der Computer eine Möglichkeit, sie sofort zu verarbeiten, während die Daten hereinkommen. Die Autoren haben einen neuen Motor namens Streaming Trigger Graphs (STGs) entwickelt.

Stellen Sie sich einen STG als eine intelligente Fließbandanlage in einer Fabrik vor:

Die Fabrikhalle: Der „Stream" von Daten (Ereignisse) fließt auf einem Förderband.
Die Arbeiter (Knoten): Jeder Arbeiter an der Linie prüft eine bestimmte Bedingung.
Die „Vergessen"-Taste: In einer normalen Fabrik würden Sie möglicherweise jeden einzelnen Teil aufbewahren, das Sie je hergestellt haben. Aber in dieser Hochgeschwindigkeitsfabrik wirft der Arbeiter ein Teil sofort weg, wenn es zu alt ist, um für das aktuelle Produkt nützlich zu sein. Das Papier nennt dies „Vergessen". Es spart enorme Mengen an Speicherplatz, indem es nur die Fakten behält, die für den aktuellen Moment noch relevant sind.
Das Sicherheitsnetz (Negation): Manchmal muss ein Arbeiter wissen: „Ist ein bestimmtes Ereignis nicht passiert?" Der STG verfügt über einen speziellen Mechanismus (wie ein Sicherheitsbeamter mit einer „Betreten verboten"-Liste), der ein Produkt sofort daran hindert, weiterzuwandern, wenn ein verbotenes Ereignis eingetreten ist.

4. Wie es in der Praxis funktioniert

Das Papier zeigt, wie komplexe Regeln aus den beiden Hauptdialekten (Event Calculus und LARS) genommen und in diese gemeinsame Sprache übersetzt werden können.

Beispiel: Wenn eine Regel besagt: „Wenn ein Gerät in den letzten 2 Stunden repariert wurde, markieren Sie es als 'Verifiziert'", wandelt der Übersetzer dies in eine einfache Regel um, die die aktuelle Zeit minus 2 Stunden überprüft.
Das Ergebnis: Der STG-Motor führt dann diese übersetzten Regeln aus. Wenn neue Daten eintreffen (z. B. eine Reparatur stattfindet), aktualisiert der Motor sofort sein Wissen, prüft die Regeln und gibt das Ergebnis aus (z. B. „Gerät ist verifiziert"), ohne jemals langsamer zu werden oder festzustecken.

5. Warum dies wichtig ist

Das Papier behauptet, dass durch diese Übersetzung und die Verwendung dieses neuen Motors:

Einheitlichkeit: Sie können verschiedene Ereignissprachen nun fair vergleichen, da sie alle auf demselben Motor laufen.
Effizienz: Der „Vergessen"-Mechanismus und die intelligente Organisation des Graphen bedeuten, dass das System große Datenmengen sehr schnell verarbeiten kann, ohne den Speicher zu erschöpfen.
Korrektheit: Die Autoren haben mathematisch bewiesen, dass diese Übersetzung die Bedeutung der Regeln nicht verändert. Wenn die ursprüngliche Regel sagte „X ist wahr", wird die übersetzte Version ebenfalls sagen „X ist wahr".

Zusammenfassung

Kurz gesagt haben die Autoren einen Universalübersetzer für Ereigniserkennungssprachen und eine super-effiziente, speichersparende Fließbandanlage (Streaming Trigger Graphs) zum Verarbeiten dieser Sprachen entwickelt. Dies ermöglicht es Computern, komplexe, zeitkritische Muster in Hochgeschwindigkeitsdatenströmen zuverlässig zu erkennen, ohne durch unterschiedliche Sprachen verwirrt zu werden oder den Speicherplatz zu verlieren.

Technische Zusammenfassung: Effiziente Materialisierung temporaler Datalog-Programme für die Erkennung zusammengesetzter Ereignisse

Problemstellung

Frameworks zur Erkennung zusammengesetzter Ereignisse (Composite Event Recognition, CER) sind unverzichtbar, um kritische Situationen (z. B. Sicherheitsbedrohungen) über hochratige Ströme symbolischer Ereignisse zu detektieren. Diese Frameworks bestehen typischerweise aus einer Ereignisspezifikationssprache (Event Specification Language, ESL) zur Definition von Mustern und einem Stream-Reasoner zu deren Auswertung. Die bestehenden ESLs werden jedoch häufig isoliert untersucht, was Vergleiche hinsichtlich ihrer Ausdruckskraft erschwert und den Anwendungsbereich ihrer zugehörigen Reasoner verschleiert. Darüber hinaus lassen sich Muster, die in einer ESL formuliert sind, häufig nicht getreu oder optimal in eine andere übersetzen, was die Nutzung des für ein spezifisches Problem am besten geeigneten Reasoners verhindert. Es fehlt an einem vereinheitlichenden Formalismus, der prominente ESLs einbetten kann und gleichzeitig eine effiziente, latenzarme Inferenz über unendliche Ströme unterstützt.

Methodik

Die Autoren schlagen einen vereinheitlichten Ansatz vor, der auf Temporal Datalog $^{\rightarrow}_{\ominus}$ basiert, einer Variante von Temporal Datalog mit stratifizierter Negation und ohne Zukunftsabhängigkeiten (vorwärtspropagierend). Die Methodik umfasst zwei Hauptkomponenten:

1. Einbettung von ESLs in Temporal Datalog $^{\rightarrow}_{\ominus}$

Der Artikel stellt Abbildungen von zwei prominenten logikbasierten ESLs in Temporal Datalog $^{\rightarrow}_{\ominus}$ vor und beweist, dass diese Übersetzungen in Bezug auf die Beantwortung von Anfragen Äquivalenz erhaltend sind:

Plain LARS: Ein Fragment der LARS-Sprache (basierend auf Answer Set Programming mit Fensteroperatoren). Die Übersetzung (Algorithmus 2) behandelt temporale Modalitäten ( $\diamond$ , $\square$ ) und Fensteroperatoren ( $\boxplus$ ) durch die Einführung von Hilfsprädikaten und das Grounding von Zeitvariablen. Sie stellt sicher, dass das resultierende Programm vorwärtspropagierend und temporal stratifiziert ist.
Event Calculus with Delayed Effects (ECDE): Eine Variante des Event Calculus, die in großskaligen CER-Systemen eingesetzt wird. Die Übersetzung (Algorithmus 3) eliminiert Funktoren (Ereignis-/Fluent-Typen) durch die Einführung spezifischer Prädikate für jeden Typ und jeden Wert. Sie kodiert das Trägheitsgesetz, verzögerte Effekte und statische Fluent-Definitionen in vorwärtspropagierende Regeln und gewährleistet dabei die temporale Stratifikation.

2. Streaming Trigger Graphs (STGs)

Um eine effiziente Materialisierung von Temporal Datalog $^{\rightarrow}_{\ominus}$ zu unterstützen, schlagen die Autoren Streaming Trigger Graphs (STGs) vor, eine Erweiterung von Trigger Graphs (TGs). Standard-TGs sind unzureichend, da sie keine native Unterstützung für Negation oder das unendliche Grounding von Zeitvariablen bieten, wie es für Streaming erforderlich ist.

Streaming Execution Graphs (SEGs): STGs basieren auf SEGs, die Execution Graphs erweitern um:
- Negation: Wird über $n$ -Kanten (Hyperkanten) dargestellt, die als Filter fungieren und die Herleitung von Fakten verhindern, wenn bestimmte negative Bedingungen erfüllt sind.
- Zeit: Knoten sind mit spezifischen Zeitpunkten assoziiert, und Kanten erzwingen zeitliche Verschiebungen, die mit den Regeln konsistent sind.
Inkrementelle Stratifikation: Um inkrementelle Updates zu ermöglichen, ohne den gesamten Graphen neu zu berechnen, definieren die Autoren eine inkrementelle Stratifikation. Dies ermöglicht es dem System, Regeln für einen bestimmten Zeitpunkt $t$ in Schichten zu verarbeiten, wobei sichergestellt wird, dass Fakten für Zeit $t$ unter Verwendung von Fakten aus $t$ oder früheren Zeitpunkten abgeleitet werden, niemals jedoch aus der Zukunft.
Konsistenz vs. $k$ -Kompatibilität: Die Autoren führen ein „Konsistenz"-Kriterium für die Knotenkonstruktion ein. Im Gegensatz zur Standard- $k$ -Kompatibilität (die erfordert, dass mindestens ein Eingangsknoten aus der aktuellen Iteration $k-1$ stammt), erlaubt Konsistenz die Konstruktion von Knoten, wenn diese in einer beliebigen vorherigen Iteration erstellt wurden, sofern ihre Zeitlabels den Anforderungen der Regel entsprechen. Dies verhindert, dass der Materialisierungsprozess ins Stocken gerät, wenn Abhängigkeiten über mehrere Zeitschritte hinweg bestehen.
Optimierungen: Der Ansatz integriert Standard-Optimierungen für TGs (Entfernung von Subsumtionen, delta-basierte Updates) und führt einen „Vergessens"-Mechanismus ein. Knoten und Fakten werden aus dem Graphen entfernt, sobald ihre Zeitstempel den maximalen temporalen Versatz überschreiten, der von irgendeiner Regel erforderlich ist, was einen begrenzten Speicherverbrauch gewährleistet.

Hauptbeiträge

Formale Abbildungen: Der Artikel liefert und beweist die Korrektheit von Abbildungen von praktischen Fragmenten von Plain LARS und ECDE nach Temporal Datalog $^{\rightarrow}_{\ominus}$ . Dies etabliert Temporal Datalog $^{\rightarrow}_{\ominus}$ als natürlichen Formalismus zum Einbetten und Vergleichen dieser Sprachen.
Streaming Trigger Graphs (STGs): Ein neuartiger Inferenzalgorithmus und ein Rechenmodell, die speziell für Temporal Datalog $^{\rightarrow}_{\ominus}$ entwickelt wurden. STGs unterstützen stratifizierte Negation und bewältigen die Unendlichkeit von Zeitvariablen durch inkrementelle Stratifikation und Konsistenzprüfungen.
Uniformer CER-Mechanismus: Durch die Vereinheitlichung von ESLs unter einem einzigen Formalismus und Inferenzmotor erleichtert die Arbeit die formale Analyse und den Vergleich verschiedener Ereignisspezifikationssprachen und weicht damit von ad-hoc, isolierten Lösungen ab.

Ergebnisse und Korrektheit

Der Artikel liefert theoretische Beweise anstelle empirischer experimenteller Ergebnisse.

Korrektheit der Übersetzung: Satz 1 und Satz 2 beweisen, dass die Übersetzungen von Plain LARS und ECDE nach Temporal Datalog $^{\rightarrow}_{\ominus}$ die perfekten Modell-Semantiken der ursprünglichen Programme erhalten.
Korrektheit von STGmat: Satz 3 beweist, dass Algorithmus 4 (STGmat) korrekt einen Streaming Trigger Graph konstruiert, der dieselben Fakten liefert wie die standardmäßige modelltheoretische Auswertung des Programms über einen Strom.
Terminierung und Effizienz: Die Verwendung der inkrementellen Stratifikation und des „Vergessens"-Mechanismus (Proposition 1) stellt sicher, dass der Materialisierungsprozess nicht in unendlichen Ableitungen gefangen wird und dass der Speicherverbrauch durch das Verwerfen von Fakten, die zukünftige Ableitungen nicht mehr beeinflussen können, gesteuert wird.

Bedeutung und Behauptungen

Die Autoren behaupten, dass diese Arbeit die Fragmentierung im CER-Bereich durch die Bereitstellung eines uniformen Mechanismus zur Erkennung zusammengesetzter Ereignisse adressiert.

Generalisierung: Der Ansatz ist so konzipiert, dass er sich auf eine breite Palette praktischer Ereignisspezifikationssprachen verallgemeinern lässt, die die Eigenschaften stratifizierter Negation und fehlender Zukunftsabhängigkeiten teilen, welche gemeinsame Anforderungen im Stream-Reasoning darstellen.
Effizienz: Durch die Erweiterung modernster Datalog-Materialisierungstechniken (Trigger Graphs) auf die Handhabung temporaler Ströme mit Negation bieten die vorgeschlagenen STGs einen Weg zu effizienter, latenzarmer Inferenz, ohne dass ad-hoc-Optimierungen für jede einzelne Sprache erforderlich sind.
Fundamentale Konsolidierung: Die Arbeit trägt zur Konsolidierung der theoretischen Grundlagen von CER bei und ermöglicht prinzipielle Trade-off-Studien zwischen Ausdruckskraft und Inferenz-Traktabilität.

Der Artikel schließt mit der Feststellung, dass zwar geordnete Eingabeströme angenommen werden, die Handhabung von nicht-geordneten Strömen und probabilistische Erweiterungen jedoch zukünftiger Arbeit vorbehalten bleiben. Die Beiträge werden als ein Schritt zur Weiterentwicklung des Standes der Technik in der Erkennung zusammengesetzter Ereignisse durch Vereinheitlichung und effiziente Materialisierung dargestellt.