🤖 AI

Efficient Temporal Datalog Materialisation for Composite Event Recognition

Dit artikel adresseert de uitdaging van het vergelijken van uiteenlopende specificatietalen voor gebeurtenissen door ze af te beelden op een unifyd Temporal Datalog-raamwerk en het introduceren van Streaming Trigger-graafstructuren om efficiënte, generaliseerbare herkenning van samengestelde gebeurtenissen over datastromen met hoge snelheid mogelijk te maken.

Oorspronkelijke auteurs: Periklis Mantenoglou

Gepubliceerd 2026-05-06

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Periklis Mantenoglou

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de dirigent bent van een massaal, hoogtempo orkest, waarbij elke muzikant een ander instrument bespeelt en de muziek elke seconde verandert. Jouw taak is om specifieke, complexe patronen in de muziek te herkennen – zoals "een viool die een hoge noot speelt terwijl een trommel drie keer op rij een langzaam ritme slaat" – en onmiddellijk een rode vlag te heffen zodra zo'n patroon optreedt.

Dit is de uitdaging van Composite Event Recognition (CER). In de echte wereld gaat het hier niet alleen om muziek; het gaat om het opsporen van veiligheidsbedreigingen in een slimme stad, het detecteren van fraude in een bank, of het monitoren van een vloot bezorgvrachtwagens. Het probleem is dat verschillende teams verschillende "partituren" (talen) gebruiken om deze patronen te beschrijven, en dat hun "dirigenten" (redeneerders) niet met elkaar kunnen communiceren.

Hieronder wordt uiteengezet hoe dit artikel dat probleem oplost, met behulp van eenvoudige analogieën:

1. Het Probleem: Te Veel Dialecten

Stel je een groep detectives voor die een misdaad proberen op te lossen. Eén detective spreekt "Event Calculus", een andere spreekt "LARS" en een derde spreekt "Temporal Datalog". Ze beschrijven allemaal hetzelfde misdaadtoneel, maar gebruiken verschillende woorden en zinsstructuren.

Het Probleem: Als Detective A een aanwijzing vindt, begrijpt Detective B die misschien niet. Ze kunnen hun notities niet eenvoudig vergelijken en ze kunnen de beste detective voor de specifieke klus niet inzetten, omdat de talen niet overeenkomen.
Het Doel van het Artikel: Creëer een "Universele Vertaler" die de specifieke dialecten van Event Calculus en LARS omzet in één gemeenschappelijke taal, genaamd Temporal Datalog→⊖.

2. De Universele Vertaler: Temporal Datalog→⊖

De auteurs hebben een speciale versie van een logische taal (een reeks regels voor computers) ontwikkeld die fungeert als dit gemeenschappelijke platform.

Geen Tijdreizen: Deze taal heeft een strikte regel: je kunt alleen naar het verleden of het heden kijken. Je kunt niet naar de toekomst kijken. Dit is alsof je zegt: "Ik kan alleen beslissingen nemen op basis van wat al is gebeurd of wat nu gebeurt." Dit voorkomt dat het systeem in de war raakt of blijft hangen in het wachten op gegevens die nog niet zijn aangekomen.
Gelaagde Negatie: Dit is een ingewikkelde manier van zeggen dat de regels in lagen zijn georganiseerd om tegenstrijdigheden te voorkomen. Stel je een gebouw met verdiepingen voor. Je kunt alleen van een hogere verdieping naar beneden kijken om te controleren wat er op een lagere verdieping gebeurt, nooit andersom. Dit houdt de logica schoon en voorkomt dat het systeem in een lus terechtkomt van "Is het waar? Nee, is het waar? Nee..."

3. De Motor: Streaming Trigger Graphs (STG's)

Zodra de regels zijn vertaald naar deze gemeenschappelijke taal, moet de computer een manier hebben om ze direct te verwerken terwijl de gegevens binnenstromen. De auteurs hebben een nieuwe motor uitgevonden die Streaming Trigger Graphs (STG's) heet.

Beschouw een STG als een slimme assemblagelijn in een fabriek:

De Fabrieksvloer: De "stroom" van gegevens (gebeurtenissen) stroomt over een lopende band.
De Werkers (Knopen): Elke werker op de lijn controleert op een specifieke voorwaarde.
De "Vergeten"-knop: In een normale fabriek houd je misschien elk onderdeel dat je ooit hebt gemaakt. Maar in deze hoogtempo-fabriek gooit een werker een onderdeel onmiddellijk weg als het te oud is om nuttig te zijn voor het huidige product. Het artikel noemt dit "Vergeten". Dit bespaart enorme hoeveelheden geheugen door alleen de feiten bij te houden die op dat moment nog relevant zijn.
Het Veiligheidsnet (Negatie): Soms moet een werker weten: "Is een specifieke gebeurtenis niet gebeurd?" De STG heeft een speciaal mechanisme (zoals een beveiliger met een "Toegang Verboden"-lijst) dat een product onmiddellijk blokkeert om verder te gaan als een verboden gebeurtenis heeft plaatsgevonden.

4. Hoe Dit in de Praktijk Werkt

Het artikel laat zien hoe complexe regels uit de twee belangrijkste "dialecten" (Event Calculus en LARS) worden vertaald naar deze gemeenschappelijke taal.

Voorbeeld: Als een regel zegt: "Als een apparaat in de laatste 2 uur is gerepareerd, markeer het als 'Geverifieerd'", dan zet de vertaler dit om in een eenvoudige regel die de huidige tijd min 2 uur controleert.
Het Resultaat: De STG-motor voert vervolgens deze vertaalde regels uit. Zodra nieuwe gegevens binnenkomen (bijvoorbeeld een reparatie), werkt de motor zijn kennis direct bij, controleert hij de regels en geeft hij het resultaat (bijvoorbeeld "Apparaat is Geverifieerd") zonder ooit te vertragen of vast te lopen.

5. Waarom Dit Belangrijk Is

Het artikel beweert dat door deze vertaling en het gebruik van deze nieuwe motor:

Uniformiteit: Je nu verschillende gebeurtenistalen eerlijk kunt vergelijken, omdat ze allemaal op dezelfde motor draaien.
Efficiëntie: Het "Vergeten"-mechanisme en de slimme organisatie van de grafiek betekenen dat het systeem enorme hoeveelheden gegevens zeer snel kan verwerken zonder het geheugen te raken.
Correctheid: De auteurs hebben wiskundig bewezen dat deze vertaling de betekenis van de regels niet verandert. Als de oorspronkelijke regel zei "X is waar", zal de vertaalde versie ook zeggen "X is waar".

Samenvatting

Kortom, de auteurs hebben een universele vertaler voor taal voor gebeurtenisdetectie gebouwd en een super-efficiënte, geheugensparende assemblagelijn (Streaming Trigger Graphs) om deze te verwerken. Hierdoor kunnen computers betrouwbaar complexe, tijdgevoelige patronen in hoogtempo-gegevensstromen opsporen, zonder in de war te raken door verschillende talen of zonder op te raken in ruimte.

Technische Samenvatting: Efficiënte Temporele Datalog-Materialisatie voor Samengestelde Eventherkenning

Probleemstelling

Kaders voor Samengestelde Eventherkenning (CER) zijn essentieel voor het detecteren van kritieke situaties (bijvoorbeeld veiligheidsbedreigingen) in hoge-snelheidsstromen van symbolische gebeurtenissen. Deze kaders bestaan doorgaans uit een Event Specificatie Taal (ESL) om patronen te definiëren en een stream-redeneraar om deze te evalueren. Echter, bestaande ESL's worden vaak geïsoleerd bestudeerd, wat vergelijkingen betreffende expressiviteit bemoeilijkt en het toepassingsgebied van hun bijbehorende redenaars vertroebelt. Bovendien kunnen patronen die in de ene ESL zijn uitgedrukt, vaak niet getrouw of optimaal worden vertaald naar een andere, waardoor het gebruik van de meest geschikte redenaar voor een specifiek probleem wordt verhinderd. Er ontbreekt een verenigende formalisme dat prominente ESL's kan embedden, terwijl het efficiënt, laag-latentie redeneren over onbegrensde stromen ondersteunt.

Methodologie

De auteurs stellen een verenigde aanpak voor die centraal staat rond Temporele Datalog $^{\rightarrow}_{\ominus}$ , een variant van Temporele Datalog met gestratificeerde negatie en zonder toekomstafhankelijkheden (voorwaarts-propagerend). De methodologie omvat twee hoofdcomponenten:

1. Embedden van ESL's in Temporele Datalog $^{\rightarrow}_{\ominus}$

Het artikel presenteert mappings van twee prominente logische ESL's naar Temporele Datalog $^{\rightarrow}_{\ominus}$ , en bewijst dat deze vertalingen equivalentiebehoudend zijn met betrekking tot het beantwoorden van queries:

Plain LARS: Een fragment van de LARS-taal (gebaseerd op Answer Set Programming met vensteroperatoren). De vertaling (Algoritme 2) behandelt temporele modaliteiten ( $\diamond$ , $\square$ ) en vensteroperatoren ( $\boxplus$ ) door het introduceren van auxiliaire predicaten en het grondig maken van tijdsvariabelen. Het zorgt ervoor dat het resulterende programma voorwaarts-propagerend en temporeel gestratificeerd is.
Event Calculus met vertraagde effecten (ECDE): Een variant van de Event Calculus die wordt gebruikt in grootschalige CER. De vertaling (Algoritme 3) elimineert functors (event/fluent-types) door specifieke predicaten voor elk type en elke waarde in te voeren. Het codeert de wet van traagheid, vertraagde effecten en statische fluent-definities in voorwaarts-propagerende regels, waarbij temporele stratificatie wordt gewaarborgd.

2. Streaming Trigger Graphs (STG's)

Om efficiënte materialisatie van Temporele Datalog $^{\rightarrow}_{\ominus}$ te ondersteunen, stellen de auteurs Streaming Trigger Graphs (STG's) voor, een extensie van Trigger Graphs (TG's). Standaard TG's zijn onvoldoende omdat ze geen native ondersteuning bieden voor negatie of de oneindige gronding van tijdsvariabelen die vereist is voor streaming.

Streaming Execution Graphs (SEG's): STG's zijn gebaseerd op SEG's, die Execution Graphs uitbreiden met:
- Negatie: Weergegeven via $n$ -randen (hyperranden) die fungeren als filters, waardoor het afleiden van feiten wordt voorkomen als specifieke negatieve voorwaarden worden voldaan.
- Tijd: Knopen zijn geassocieerd met specifieke tijdstippen, en randen handhaven temporele offsets die consistent zijn met de regels.
Incrementele Stratificatie: Om incrementele updates mogelijk te maken zonder de volledige graaf opnieuw te berekenen, definiëren de auteurs een incrementele stratificatie. Dit stelt het systeem in staat regels in strata te verwerken voor een specifiek tijdstip $t$ , waarbij wordt gegarandeerd dat feiten voor tijd $t$ worden afgeleid met feiten van $t$ of eerder, maar nooit uit de toekomst.
Consistentie versus $k$ -compatibiliteit: De auteurs introduceren een "consistentie"-criterium voor knopconstructie. In tegenstelling tot standaard $k$ -compatibiliteit (waarbij ten minste één invoerknop uit de huidige iteratie $k-1$ moet komen), staat consistentie toe dat knopen worden geconstrueerd als ze in eerdere iteraties zijn gebouwd, mits hun tijdslabels voldoen aan de eisen van de regel. Dit voorkomt dat het materialisatieproces vastloopt wanneer afhankelijkheden zich over meerdere tijdstappen uitstrekken.
Optimalisaties: De aanpak integreert standaard TG-optimalisaties (verwijdering van subsumptie, delta-gebaseerde updates) en introduceert een "vergeten"-mechanisme. Knopen en feiten worden uit de graaf verwijderd zodra hun tijdstempel de maximale temporele offset overschrijdt die door een regel wordt vereist, waardoor een gebonden geheugengebruik wordt gewaarborgd.

Belangrijkste Bijdragen

Formele Mappings: Het artikel biedt de correctheid van mappings van praktische fragmenten van Plain LARS en ECDE naar Temporele Datalog $^{\rightarrow}_{\ominus}$ en bewijst deze. Dit vestigt Temporele Datalog $^{\rightarrow}_{\ominus}$ als een natuurlijk formalisme voor het embedden en vergelijken van deze talen.
Streaming Trigger Graphs (STG's): Een nieuw redeneeralgoritme en computationeel model dat specifiek is ontworpen voor Temporele Datalog $^{\rightarrow}_{\ominus}$ . STG's ondersteunen gestratificeerde negatie en behandelen de oneindige aard van tijdsvariabelen via incrementele stratificatie en consistentiecontroles.
Uniform CER-mechanisme: Door ESL's te verenigen onder één formalisme en redeneermotor, faciliteert dit werk de formele analyse en vergelijking van verschillende event-specificatietalen, en beweegt het weg van ad-hoc, geïsoleerde oplossingen.

Resultaten en Correctheid

Het artikel levert theoretische bewijzen in plaats van empirische experimentele resultaten.

Correctheid van Vertaling: Stelling 1 en Stelling 2 bewijzen dat de vertalingen van Plain LARS en ECDE naar Temporele Datalog $^{\rightarrow}_{\ominus}$ de perfecte modelsemantiek van de oorspronkelijke programma's behouden.
Correctheid van STGmat: Stelling 3 bewijst dat Algoritme 4 (STGmat) correct een Streaming Trigger Graph construeert die dezelfde feiten oplevert als de standaard model-theoretische evaluatie van het programma over een stroom.
Terminatie en Efficiëntie: Het gebruik van incrementele stratificatie en het "vergeten"-mechanisme (Propositie 1) zorgt ervoor dat het materialisatieproces niet vastloopt in oneindige afleidingen en dat het geheugengebruik wordt beheerd door feiten te verwijderen die geen invloed meer kunnen hebben op toekomstige afleidingen.

Betekenis en Claims

De auteurs claimen dat dit werk de fragmentatie in het CER-veld aanpakt door een uniform mechanisme voor samengestelde eventherkenning te bieden.

Generalisatie: De aanpak is ontworpen om te generaliseren over een breed scala aan praktische event-specificatietalen die de eigenschappen van gestratificeerde negatie en geen toekomstafhankelijkheden delen, wat veelvoorkomende vereisten zijn in stream-redenering.
Efficiëntie: Door state-of-the-art Datalog-materialisatietechnieken (Trigger Graphs) uit te breiden om temporele stromen met negatie te verwerken, bieden de voorgestelde STG's een weg naar efficiënt, laag-latentie redeneren zonder de noodzaak van ad-hoc optimalisaties voor elke specifieke taal.
Fundamentele Consolidatie: Het werk helpt de theoretische fundamenten van CER te consolideren, waardoor principiële trade-off-studies tussen expressiviteit en redeneerbaarheid mogelijk worden.

Het artikel concludeert met de opmerking dat, hoewel het uitgaat van geordende invoerstromen, het behandelen van niet-geordende stromen en probabilistische extensies worden overgelaten voor toekomstig werk. De bijdragen worden gepresenteerd als een stap in de richting van het bevorderen van de state of the art in samengestelde eventherkenning door middel van unificatie en efficiënte materialisatie.