Generating diverse solutions to conjunctive queries and propositional formulae

Abstract

Die Anzahl der Lösungen für ein computationelles Problem kann enorm sein, weshalb die Ausgabe aller Möglichkeiten oft nicht ratsam ist. Daher sollte ein Solver nur eine kleine Anzahl aller Lösungen berechnen. Dies sollte jedoch keine willkürliche Auswahl an Lösungen sein, sondern eine Sammlung möglichst unterschiedlicher, damit der*die Nutzer*in den gesamten Lösungsraum besser erfassen kann. Ausgehend davon beschäftigt sich die vorliegende Arbeit mit dem Problem der Berechnung einer Sammlung möglichst unterschiedlicher Antworten auf Datenbankabfragen - mit besonderem Fokus auf konjunktive Abfragen - und der Berechnung einer Sammlung möglichst unterschiedlicher Modelle aussagenlogischer Formeln. Dabei handelt es such um zwei der grundlegendsten Probleme in der Datenbanktheorie und der künstlichen Intelligenz. Zur Analyse dieser Probleme werden Techniken aus der parametrisierten Komplexität verwenden, insbesondere wird die Komplexität der Probleme an Azyklizitätsmaße, i.e., Baumweite und Hyperbaumweite, geknüpft. Es werden sowohl theoretische Ergebnisse als auch konkrete Algorithmen angegeben, die so detailliert erklärt werden, dass eine Implementierung unkompliziert erfolgen kann. Konkret werden drei XP dynamische Programmieralgorithmen präsentiert, die jeweils für azyklische konjunktive Abfragen, konjunktive Abfragen mit Negation oder aussagenlogische Formeln entwickelt wurden. Für fixe Datenbankabfragen erster Ordnung wird darüber hinaus eine FPT-Kernelisierungsprozedur angegeben. Abschießend werden für die behandelten Probleme auch neue theoretische untere Schranken angeführt, welche außerdem zu den in der gegenwärtigen Arbeit etablierten oberen Schranken passen.

The number of solutions to a computational problem can be tremendous and thus, presenting them all to the user is often not advisable. Instead, a solver should only output a small number of all solutions. However, these should not be arbitrary solutions but a diverse collection such that the user obtains a better grasp on the whole solution space. Tackling this problem, in this thesis, we formally analyze the problem of computing a diverse collection of answers to database queries - in particular conjunctive queries (CQ) - and computing a diverse collection of models of propositional formulae (SAT). These are two of the most fundamental problems that arise in database theory and artificial intelligence. For our analysis, we apply techniques of parameterized complexity and to that end, we tie the complexity of the problems to acyclicity measures, i.e., treewidth and hypertreewidth. We give theoretical results as well as concrete algorithms that are explained in such detail that an implementation thereof is straightforward. Concretely, we present three XP dynamic programming algorithms. These are designed for acyclic conjunctive queries, conjunctive queries with negation, and propositional formulas, respectively. Furthermore, for fixed first order database queries, we give an FPT kernelization procedure. As for theoretical results, we provide novel lower bounds for the diversity problems which match the upper bounds provided by the algorithms.