Näherungsweise Auswertung von Konjunktiven Anfragen

Probleme welche von klassischen Computern nicht in akzeptabler Zeit gelöst werden können treten in vielen Forschungsgebieten auf. Die Auswertung von konjunktiven Anfragen über relationale Datenbanken gehört im Generellen zu diesen Problemen. Konjunktive Anfragen formen die Basis der Abfragesprache SQL (Structured Query Language) welche zum de-facto Standard für die Abfrage und Wartung relationaler Datenbanken wurde. Diese Arbeit behandelt die Entwicklung neuer Annäherungsverfahren für konjunktive Anfragen welche nicht in akzeptabler Zeit ausgewertet werden können. Unsere neuen Annäherungsverfahren sollten zu signifikanten Verbesserungen bei der datenbasierten Entscheidungsfindung führen, z.B., für Frühwarnsysteme welche auf die Analyse von Big-Data basieren oder um geschäftskritische Entscheidungen anhand der Analyse von Big-Data zu treffen. In den letzten Jahrzehnten wurde ein sehr gutes Verständnis für jene Klassen von konjunktiven Anfragen welche in akzeptabler Zeit ausgewertet werden können aufgebaut und es wurde bewiesen, dass eine untere Annäherung von einer Anfrage immer existiert, und zwar innerhalb jeder dieser Klassen. Nichtsdestotrotz ist dieser Ansatz relativ starr und manche unteren Annäherungen können ziemlich uninformativ sein, d.h., die untere Annäherung könnte, im Gegensatz zur originalen Anfrage, eine leere Antwortmenge zurückgeben. Obere Annäherungen könnten hilfreich sein wenn das passiert, da diese alle Antworten zu eine Anfrage zurückgeben. Eines unserer Ziele ist es, die grundlegenden Aspekte oberer Annäherungen zu studieren, einschließlich des Existenzproblems und des Problems der Berechnung einer Annäherung. Unglücklicherweise existieren obere Annäherungen (innerhalb einer Klasse von Anfragen welche in akzeptabler Zeit ausgewertet werden können) nicht immer, und auch das Entscheidungsproblem ob eine konjunktive Anfrage eine obere Annäherung besitzt ist ungelöst. Daher ist ein weiteres Ziel dieser Arbeit die Entwicklung von liberaleren Annäherungsverfahren welche eine Art von mengenmäßiger Garantie geben. Das bedeutet, dass diese garantieren sollen, dass das Ergebnis der Annäherung nicht zu weit von dem Ergebnis der originalen Anfrage (für jene Datenbanken welche von Interesse sind) entfernt ist. Dazu müssen wir ein Maß für die Differenz zwischen Anfragen und/oder Antworten definieren. Für konjunktive Anfragen existiert derzeit noch kein solches Maß. Basierend auf diesem Maß studieren wir Annäherungen deren Unterschied zum Ergebnis der zu approximierenden Anfrage kleiner ist als eine vorgegebene Schranke. Des Weiteren untersuchen wir, in welcher Weise uns die vorhandenen Daten einer Datenbank helfen können um bessere Annäherungen zu finden. Es wurde gezeigt, dass es enge Beziehungen zwischen der Annäherung von konjunktiven Anfragen über relationale Datenbanken und einigen Klassen von semantischen Web-Anfragen über semi-strukturierte Daten gibt. Wir studieren auch mögliche Verbindungen zwischen unseren Annäherungsverfahren und Annäherungen von semantischen Web-Anfragen.

Überwachtes Lernen ist eine maschinelle Lernmethode die darauf abzielt ein allgemeines Modell aus Eingabe-Ausgabe-Beispielen zu lernen. Das erlernte Modell kann dann verwendet wer- den um (in Situationen welche noch nie zuvor aufgetreten sind) Entscheidungen aufgrund der Eingabedaten zu treffen. Ein Klassifizierer ist eine Funktion welche die Eingabedaten partitioniert, d. h., die Entscheidungen trifft. Wir studieren den Fall der Klassifizierung von Konstanten, genannt Entitäten, einer relationalen Datenbank, in positive und negative Fälle. Der erlernte Klassifizierer basiert auf einer Menge von automatisch generierten Datenbankabfragen, genannt Features. Eine Trainingsdatenbank ist eine Datenbank mit einer Partition der Entitäten in positive und negative Beispiele. Durch die Verwendung von Datenbankabfragen können wir das gesamte Wissen über die Rohdaten in der Trainingsdatenbank nutzen (d. H. all die Beziehungen). Dieses Wissen ist entscheidend um die Features automatisch zu generieren. Wir betrachten verschiedene Abfragesprachen, untersuchen die Komplexität der Klassifizierung der Eingabebeispiele und der Generierung der Features, und geben explizite Algorithmen für die Klassifizierung und Feature-Generierung an. Darüber hinaus behandeln wir den Fall einer ungefähren Klassifizierung, bei der die Trainingsdatenbank eine geringe Menge an Rauschen enthält welches eine genaue Klassifizierung unmöglich macht. Wir identifizieren praktikable Fälle für welche die Klassifizierung und die Feature-Generierung effizient durchführbar ist. Wir zeigen dass, obwohl die Feature-Generierung für manche Abfrage- sprachen nicht praktikabel ist, das Klassifizierungsproblem praktikabel sein kann, und wir geben einen expliziten Algorithmus für diesen Fall. Dies ist möglich, weil wir die Abfragen nicht materialisieren müssen um sie auszuwerten. Für alle identifizierten praktikablen Fälle zeigen wir, dass eine ungefähre Klassifizierung auch praktikablen ist und geben explizite Algorithmen dafür an.