Dynamische Ausdrucksstärke von Logiken

• Antragsteller: Professor Dr. Thomas Schwentick
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 228818952

Riesige und starken Änderungen unterliegende Datenbestände sind eine aktuelle Herausforderung an Datenmanagementsysteme. So erneuert sich beispielsweise der Datenbestand einer Suchmaschine durch Hinzukommen von Nachrichten fortwährend. In sozialen Netzwerken ändern sich Beziehungen zwischen Nutzern, wodurch sich vielfältige Konsequenzen für die Sichtbarkeit von Daten für andere Nutzer, ergeben.In solchen dynamischen Szenarien ist es aus Effizienzgründen häufig nicht möglich, nach jeder Änderung der Daten alle benötigten Informationen von Grund auf neu zu berechnen. Stattdessen können diese Informationen oft mithilfe sogenannter 'dynamischer Algorithmen' auf der Basis der Änderungsdaten und vorsorglich berechneter Hilfsinformationen inkrementell gewonnen werden.In vielen Anwendungen der Informatik werden heutzutage Anfragen jedoch nicht durch Angabe eines Algorithmus formuliert, sondern mittels deklarativer Spezifikationssprachen. Statt zu beschreiben wie das Anfrageergebnis berechnet werden kann, geben Benutzer hierbei nur die gewünschten Eigenschaften des Anfrageergebnisses an. In der Regel liegen solchen deklarativen Spezifikationssprachen Logiken zugrunde, z.B. Temporallogiken bei Spezifikationssprachen für die automatische Verifikation, die Prädikatenlogik bei Anfragesprachen für Datenbanken oder Beschreibungslogiken bei Ontologien.In Mittelpunkt dieses Projektes steht die Ausdrucksstärke von Logiken als Spezifikationssprachen in dynamischen Szenarien, also die Fähigkeit solcher Logiken, Anfragen inkrementell zu beschreiben.Die letzte größere, systematische Untersuchung in diesem Forschungsgebiet wurde in dem 2003 beendeten Dissertationsprojekt von Hesse unternommen. Seither wird der Forschungsstand durch Einzelresultate, auch durch den Antragsteller, dominiert. Eine aktuelle, umfassende Untersuchung unter Berücksichtigung der in den letzten Jahren eröffneten Forschungsperspektiven steht aus.Im Rahmen des beantragten Projektes sollen systematisch neue Techniken erarbeitet werden, um für einfache Logiken die Klasse der inkrementell ausdrückbaren Anfragen zu vergrößern. Flankierend sollen Methoden entwickelt werden, mit denen sich die Grenzen der dynamischen Ausdrucksfähigkeit solcher Logiken erkunden lassen. Schließlich sollen Verbindungen zwischen der dynamischen Ausdrucksfähigkeit logischer Spezifikationssprachen und der algorithmischen dynamischen Komplexität untersucht werden, wie sie im klassischen, "nicht-dynamischen" Fall bereits bekannt sind.Insgesamt soll damit das Verständnis der inkrementellen Berechnungen zugrunde liegenden Mechanismen verbessert werden, auch über den Bereich der dynamischen Ausdrucksstärke von Logiken hinaus.

• DFG-Verfahren: Sachbeihilfen