Graph-based Algorithms for Pareto Preference Query Evaluation

Searching a database is one of the most common procedures in everyday life. Usually, the results of such a search match the query parameters perfectly. But if no perfect match is found, the user usually has to find out by himself how to change search parameters in order to get results. To overcome this problem, Kießling has introduced a model of preferences in databases. This model is based on simple strict partial orders as given in expressions like "red is better than blue". For every query, the best-matching objects are returned, whether these are perfect matches or not. A best match is a tuple that matches the preference not worse than any other tuple – or as we say – that is not dominated by any other tuple. The specific problem we address is finding best matches for Pareto preferences, the combination of preferences with all of them being equally important. This problem is closely related to skyline queries. Based on the better-than graph, a visualization of the strict partial orders constructed by Pareto preferences, we have found a novel type of optimization called pruning that can be applied to all existing generic algorithms. While common generic algorithms rely on tuple-to-tuple comparisons to identify dominated tuples, our optimization technique uses the structure of the better-than graph to identify elements in the order that are definitively dominated by some given tuple. This enables us to omit many comparisons. By further analysis of the better-than graph, we were able to find a new kind of algorithm. This generic algorithm, Hexagon, is capable of finding the best matches in some previously unknown set of tuples in linear time with respect to the size of the better-than graph. Apart from the standard algorithm, we present a number of optimizations for it regarding its memory requirements. But Hexagon is not limited to standard preference queries. We also address top-k queries with a variant of Hexagon. These queries return the best k tuples of an input relation with respect to some rating function. The performance benchmarks we have made show the superiority of algorithms using pruning and especially of Hexagon, although the latter cannot be used in all cases due to memory requirements. Moreover, Hexagon can be combined with existing algorithms that have been optimized by pruning to enable the cost-based algorithm selection for Pareto preference evaluation.Das Durchsuchen von Datenbanken ist bei der Benutzung eines Computers mittlerweile eine völlig alltägliche Angelegenheit, auch wenn der Zugriff für den Benutzer unsichtbar erfolgt. Im Normalfall erfüllen die Ergebnisse alle Anforderungen der Suchanfrage, man spricht von "perfekten Treffern". Wenn allerdings kein einziger solch perfekter Treffer gefunden werden kann, muss der Benutzer im Allgemeinen selbst herausfinden, wie er die Such-Parameter verändern muss, um doch noch Ergebnisse zu bekommen. Um dieses Problem zu lösen, wurde von Kießling ein Präferenz-Modell für Datenbanken eingeführt. Das Modell basiert auf strikten partiellen Ordnungen, wie sie in Redewendungen wie "rot ist besser als blau" vorkommen. Bei einer Anfrage an eine Datenbank werden stets die am besten passenden Objekte zurückgegeben, auch wenn es sich dabei nicht um perfekte Treffer handelt. Ein "am besten passendes Objekt" ist - im Hinblick auf die Präferenz des Nutzers - nicht schlechter als irgendein anderes Objekt in der Datenbank. Besitzt ein Benutzer mehrere gleichberechtigte Präferenzen spricht man von einer Pareto-Präferenz. Die Auswertung solcher Pareto-Präferenzen, die eng verwandt sind mit Skyline-Queries, ist Inhalt dieser Dissertation. In dieser Doktorarbeit wird, basierend auf dem sogenannten Better-Than-Graph zur Visualisierung von strikten partiellen Ordnungen, eine neue Optimierungsmethode namens "Pruning" für Algorithmen zur Auswertung von Pareto-Präferenzen vorgestellt. Diese Methode erlaubt es, die sonst üblichen tupelweisen Vergleiche teilweise zu übergehen und dadurch die Auswertungsgeschwindigkeit zu verbessern. Weitergehende Analysen des Better-Than-Graphs führen danach zu einer neuen Art von Algorithmus auf generischen Daten. Dieser neue Algorithmus mit Namen Hexagon ermöglicht es, die besten Elemente einer beliebigen Eingabemenge in linearer Zeit (in Bezug auf Eingabegröße und Größe des Better-Than-Graphs) zu finden. Darüberhinaus können mit Hexagon auch verwandte Probleme, wie z. B. Top-K-Anfragen, elegant und schnell gelöst werden. Speziell bei Pareto-Präferenz-Anfragen ist Hexagon bei der Geschwindigkeit anderen Algorithmen stark überlegen, wie einige Tests zeigen. Dabei ist aber anzumerken, dass Hexagon nicht in allen Problemfällen angewendet werden kann, da nicht immer genug Hauptspeicher für die Verarbeitung des Better-Than-Graphs vorhanden ist. Abschließend wird in dieser Arbeit jedoch noch dargelegt, wie Hexagon und andere Algorithmen im Rahmen eines kostenbasierten Optimierers bestmöglich kombiniert werden können