Detailseite
Projekt
Teamlogiken: Neue Brücken zu Datenbank-Reparaturen
Antragsteller
Privatdozent Dr. Arne Meier
Fachliche Zuordnung
Theoretische Informatik
Förderung
Förderung seit 2023
Projektkennung
Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 511769688
Viele Bereiche des Lebens in der modernen Gesellschaft sind mit großen Datenmengen verbunden oder hängen von ihnen ab: Wettervorhersagen, Internet-Suchanfragen oder medizinische Datenbanken, um nur einige zu nennen. Es ist keine Übertreibung zu sagen, dass das Gebiet der Datenbanktheorie mit vielen Aspekten unseres Lebens verwoben ist. Ein grundlegendes Anliegen bei der Datenverarbeitung ist die Datenkonsistenz. In Datenbanksystemen wird die Konsistenz durch mehrere Bedingungen sichergestellt, die die Datenbank zu jedem Zeitpunkt erfüllen muss. Vor allem bei großen Datenbanken fehlt diese Eigenschaft oft oder sie kann in einer Vielzahl von Szenarien und aus verschiedenen Gründen inkonsistent werden. Inkonsistenz kann z. B. auftreten, wenn mehrere Datensätze kombiniert werden, während jeder einzelne Datensatz konsistent ist. Seit etwas mehr als einem Jahrzehnt gibt es ein modernes Konzept der Abhängigkeit und Unabhängigkeit in der Logik. Im Jahr 2007 schlug Jouko Väänänen mit seiner Dependenzlogik (DL) eine Logik vor, in der man Abhängigkeiten zwischen Variablen als Bestandteil von Formeln in dieser Logik ausdrücken kann. Ein Team ist eine Menge von Belegungen und die Team-Semantik ist das zugrundeliegende Konzept in dieser Logik. DL kann eindeutig als eine Logik betrachtet werden, die den Formalismen von Datenbanken sehr nahekommt. Wir werden Repair Checking (RC) und Conjunctive Query Answering (CQA) aus der Perspektive der DL betrachten. Dabei werden wir uns auf Update-Repairs konzentrieren und eine passende Verbindung zu DL anstreben. Insbesondere wollen wir uns mit Denail und Equality generierenden Abhängigkeiten befassen, indem wir entsprechende Semantiken und Begriffe in DL finden. Außerdem werden wir das Konzept der eingebetteten mehrwertigen Abhängigkeiten (Fagin, 1977) im Rahmen von DL untersuchen. Diese Abhängigkeiten spielen in der Datenbanktheorie eine wichtige Rolle. Angetrieben von der Motivation, die Komplexität solcher datenbankbezogenen Probleme besser zu verstehen (das Inferenzproblem für funktionale und Inklusionsabhängigkeiten zusammen ist unentscheidbar), werden wir solche Konzepte in der neuen Umgebung der Teamlogik untersuchen. Eine weitere Ursache für Inkonsistenzen in DBs kann der Austausch von Daten sein. Hier bieten sich Verbindungen zum Bereich der Belief Revision sowie der Argumentation an. In diesem Projekt werden wir die untersuchten Probleme auch mit dem Framework der parametrisierten Komplexität angehen. Hier werden über die klassische Komplexität (in der man Probleme bezüglich der reinen Eingabelänge analysiert) hinausgehend die Komplexität von Problemen bezüglich sogenannter Parameter untersucht.
DFG-Verfahren
Sachbeihilfen
Internationaler Bezug
Finnland, Neuseeland, Österreich, Schweden, USA
