Entwicklung eines Kostenmodells für den Optimierer einer nativen ortsbasierten RDF-Datenbank

Abstract

Technologien des Semantic Web, wie insbesondere RDF, eignen sich hervorragend zur Darstellung und Verarbeitung semistrukturierter Daten. Dies gilt ebenso, falls die Daten Ortsinformationen beinhalten. Systeme zur Verarbeitung derartiger, ortsbasierter Daten auf Basis von RDF stellen somit erstrebenswerte Werkzeuge dar. Im Rahmen der Entwicklung eines solchen Systems, sieht man sich jedoch mit der Aufgabe konfrontiert, geeignete Ausführungspläne zu optimieren. Diese Arbeit befasst sich daher mit der Bereitstellung adäquater Entscheidungshilfen für den Optimierer eines nativen, ortsbasierten RDF-Datenbankverwaltungssystems. Aufgrund möglicher Korrelationen zwischen ortsbasierten und gewöhnlichen Attributen von Entitäten ist hierbei insbesondere ein Mechanismus zur Kardinalitätsabschätzung entsprechender Anfragen notwendig, denn die Werte einer solchen Abschätzung bestimmen maßgeblich die Anordnung der Joins in einem geeigneten Ausführungsplan, der wiederum ausschlaggebend für die Performanz der Anfragebearbeitung ist. Da bislang keine geeigneten Ansätze zur Lösung dieser Aufgabe zu finden sind, werden im Rahmen dieser Arbeit hierfür eigene Konzepte entwickelt. Das erste dieser Konzepte unterteilt den betrachteten, geographischen Bereich in disjunkte Kacheln, um damit eine Kardinalitätsabschätzung für die in einem Anfragefenster enthaltenen Objekte zu ermöglichen. Auf dieser Grundlage wird anschließend ein Ansatz entwickelt, der die Kardinalität einer Menge von Teilgraphen - und damit potentiellen Anfrageergebnissen - anhand einer Kombination ihrer enthaltenen Pfade abschätzt. Auf Basis dieser Abschätzungen ist es in der Folge möglich, ein Kriterium zu konzipieren, mit dessen Hilfe geeignete Operatoren zur Realisierung eines ortsbasierten Filters ausgewählt werden können. Die Evaluation einer Implementierung dieser Konzepte zeigt, dass anhand der Unterteilung in Kacheln lediglich moderate Verbesserungen der Abschätzungsgenauigkeit sowie der daraus resultierenden Ausführungszeiten möglich sind. Durch Hinzunahme der Kardinalitätsabschätzung mittels Pfaden können jedoch deutlich bessere Resultate erzielt werden. Auf deren Basis ist es dem erwähnten Entscheidungskriterium möglich, in gewinnbringender Art und Weise die jeweils optimalen Operatoren zur Realisierung eines ortsbasierten Filters auszuwählen.