Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Effizientes Aufzählen der Ergebnisse von Pfadanfragen bei Graphdatenbanken

Antragsteller Dr. Markus Schmid
Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2019 bis 2023
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 416776735
 
Erstellungsjahr 2023

Zusammenfassung der Projektergebnisse

Hauptzielsetzung des Projekts war die Entwicklung und theoretische Untersuchung von effizienten Algorithmen (inklusive Aufzählalgorithmen) zur Auswertung von Pfadanfragen auf Graphdatenbanken. Des Weiteren waren wir auch an anderen Datenmodellen und entsprechenden Anfragesprachen interessiert. Die Resultate des Projekts können in drei Teilgebiete unterteilt werden. Graphdatenbanken und Pfadanfragen: Bezüglich der Graphdatenbanken lag unser Hauptaugenmerk auf Anfragesprachen, die reguläre Ausdrücke (und Varianten davon) als Hauptelement verwenden. Diesbezüglich haben wir im Detail analysiert, wie sich das bekannte Konzept der "capture groups" (auch Rückreferenzen genannt), wie man es in praktischen Implementierungen von regulären Ausdrücken findet, auf praktisch relevante Klassen von Pfadanfragen übertragen lässt. Außerdem haben wir die klassischen "regular path queries" (die eine Kernfunktionalität sowohl von akademischen als auch kommerziellen Datenbanksystemen beschreiben) im Rahmen der "fine-grained complexity" untersucht. Informationsextraktion und Document Spanners: Document spanners - ein momentanes "hot­ topic" in der Datenbanktheorie extrahieren Tupel von Intervallen (die als "spans" bezeichnet werden) aus Textdokumenten. Wir haben eine Klasse von document spanners formuliert, die bezüglich ihrer Ausdrucksstärke einen großen Teil der zwar sehr mächtigen, aber algorithmisch schwer zu handhabenden "core spanners" abdecken, aber gleichzeitig bezüglich der Komplexität ihrer Auswerteprobleme viel eher der gutartigen Klasse der regulären spanners gleichen. Außerdem haben wir Algorithmen entworfen, die document spanners direkt auf Dokumenten auswerten (insbesondere aufzählen) können, welche durch "straight-line programs" (SLPs) komprimiert sind - ein grammatikbasiertes Kompressionsschema, das in der theoretischen Literatur äußerst beliebt ist, aber auch viele praktische Anwendungen hat. Die Laufzeit unserer Algorithmen hängt nur linear von der Größe der komprimierten Dokumente ab, die, im besten Fall, exponentiell kleiner sind als die unkomprimierten Daten. Aufgrund der hohen Komprimierbarkeit von textuellen Daten in praktischen Szenarios und aufgrund der Tatsache, dass viele Algorithmen für SLP-Kompression existieren, ist unser Ansatz von praktischer Relevanz. Wir waren außerdem in der Lage unsere Algorithmen auf den dynamischen Fall zu erweitern, wo wir die komprimierten Daten updaten können, ohne sie dafür dekomprimieren zu müssen. Complex Event Processing und Teilsequenz-Anfragen: Die Analyse von Eventströmen, welche zur Laufzeit großer Softwaresysteme generiert werden, ist ein noch junger Bereich der sowohl praktischen als auch theoretischen Forschung im Bereich Datenbanken. Basierend auf klassischen Resultaten der induktiven Inferenz von Patternsprachen nach Angluin haben wir eine Klasse von Teilsequenzanfragen für Eventströme entworfen. Außerdem haben wir einen Algorithmus entwickelt, welcher die gemeinsame Struktur einer endlichen Menge an Eventströmen lernen kann. Diese Arbeit hat zu einer Reihe neuer algorithmischer Herausforderungen im allgemeinen Bereich der Stringalgorithmik geführt, welche wir bereits teilweise lösen konnten.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2025 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung