Anfragen in Offenen und Geschlossenen Welten: Testen, Aufzählen und Zählen (QTEC).

• Antragsteller: Professor Dr. Carsten Lutz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 444619301

Für Datenbanken sind Constraints auf vielerlei Weise nützlich. Unter einer Closed-World Semantik schränken sie die Klasse der erlaubten Datenbanken ein, was zum Gebiet des Anfragens unter Constraints führt. Eine Open-World Semantik führt zu ontologievermitteltenAnfragen, bei denen eine Datenbankanfrage um eine Ontologie erweitert wird, die Domänenwissen zur Verfügung stellt und das Finden vollständigerer Antworten unterstützt. Ontologien sind meist in Beschreibungslogik formuliert oder als Mengen von (geeignet eingeschränkten) tupel- und gleichheitserzeugenden Dependenzen (TGDs und EGDs). Letztere generalisieren auch viele Constraintsprachen, die für Anfragen unter Constraints eine zentrale Rolle spielen.Ontologvermitteltes Anfragen ist im Allgemeinen nicht effizient machbar, sowohl gemessen in kombinierter Komplexität als auch (oft) in Datenkomplexität. Es wurden daher substantielle Anstrengungen unternommen, um die Komplexitätslandschaft zu verstehen und insbesondere die effizienten Fälle von den nicht effizienten zu trennen. Dasselbe gilt auch für Anfragen unter Constraints. Dieses hat zwar eine geringere Komplexität, aber dafür kann die Gegenwart von Constraints dazu führen, dass Anfragen effizient beantwortbar werden, die dies im Allgemeinen nicht sind.In diesen Bemühungen lag der Fokus meist darauf, einzelne Antworten zu testen, d.h. ein konkreter Antwortkandidat ist als Teil der Eingabe gegeben und das Problem besteht darin, zu entscheiden, ob der Kandidat wirklich eine Antwort ist. Aus praktischer Sicht ist dasunbefriedigend, weil Antwortkandidaten meist nicht zur Verfügung stehen oder es zu viele von Ihnen gibt. Stattdessen ist es oft das Ziel, Antworten ohne explizit gegebene Kandidaten zu finden oder zunächst ihre Zahl zu bestimmen, letzteres z.B. für statistischeAnfragen und zur Anfrageoptimierung. Das Ziel von QTEC ist es, das Aufzählen und das Zählen von Antworten zu studieren, sowohl für ontologievermitteltes Anfragen als auch für Anfragen unter Constraints, sowohl mit als auch ohne Datenbankupdates. Ein besondererFokus wird darauf liegen, die effizienten von den nicht effizienten Fällen zu trennen.Diese Arten der Anfrageauswertung wurden im Kontext von ontologievermittelten Anfragen beisher nicht studiert und nur recht selten für Anfragen unter Constraints. Wir betrachten beide Gebiete zusammen, da vorbereitende Arbeiten zeigen, dass sie eng verbunden sind und dass dadurcherheblich Synergien zu erwarten sind. Das QTEC Projekt zielt darauf ab, eine möglichst feingranulare Analyse von Klassen von Anfragen durchzuführen, die effizientes Aufzählen und Zählen erlauben. Dies soll schlussendlich effiziente Anfragebeantwortung in Anwendungen ermöglichen, in denen die tatsächlich verwendeten Anfragen effiziente Ansätze erlauben währen die verwendeten Anfragesprachen dies im allgemeinen nicht tun.

• DFG-Verfahren: Sachbeihilfen