Nicht blockierende Datenbankoperatoren für große Datensätze

- Diplomarbeit -


Beschreibung:
Das Semantic Web erweitert das World Wide Web von einem menschen-lesbaren Web zu einem maschinen-verständlichen Web und stellt damit Einsatzmöglichkeiten zum Suchen, Finden, Sortieren und der Klassifikation von Web-Informationen für den Menschen zur Verfügung.

Zu diesem Zweck hat das W3C RDFS und OWL als Ontologiesprachen und RIF als Semantic Web Regelsprache standardisiert. Mit Hilfe von Ontologien kann man implizites Wissen darstellen. Um aus den impliziten Wissen explizite Fakten zu ermitteln, können Inferenzregeln verwendet werden, die zum Beispiel in der RIF Regelsprache ausgedrückt sind.

Im LUPOSDATE-Projekt haben wir eine hocheffiziente Semantic Web Datenbank entwickelt, die die Regelsprache RIF unterstützt.

Da Regeln im Allgemeinen und im Gegensatz zu Anfragen rekursiv sein können, führt dieses zu Zyklen in den dazugehörigen Ausführungsplänen, in denen die Knoten Basisoperatoren zur Berechnung der Regeln darstellen und die Kanten die Ein- und Ausgabebeziehungen zwischen den Operatoren. Bei der Auswertung von Anfragen kommen häufig Operatoren zur Anwendung, die zunächst alle Zwischenergebnisse ihrer Operanden aufsammeln und anschließend diese auf einmal verarbeiten. Diese Operatoren werden auch blockierende Operatoren oder Pipelinebreaker genannt. Zyklen in den Ausführungsplänen, wie sie bei rekursiven Regeln vorkommen, verbieten jedoch den Einsatz von blockierenden Operatoren.

In dieser Bachelor-/Masterarbeit sollen typische Operatoren wie etwa den DISTINCT Operator zur Duplikatelimination und der Join-Operator in einer nicht blockierenden Variante entwickelt werden, die ebenfalls für große Datensätze geeignet ist und daher die effiziente Verwendung von externen Datenspeichern wie etwa Festplatten bedingen. Eine mögliche Vorgehensweise ist die Enwicklung einer externen Hashtabelle, die dann als Basisdatenstruktur für die Duplikateliminierung und für den Joinalgorithmus dienen kann. Ein Fokus ist ebenfalls der Einsatz von hybriden Algorithmen, die für kleine Datenmengen hauptspeicherbasierende Verfahren einsetzen und für größere Datenmengen externe Datenspeicher hinzuziehen. Anschließend soll die Performance der Algorithmen mit ihren blockierenden Verwandten sowie den vorhandenen hauptspeicherbasierenden Varianten durch Meßreihen verglichen werden.

Anforderungen/Kenntnisse:
Java

Bearbeitung:
Katja Knof

Ergebnis:
Die Ausarbeitung kann im Institut für Informationssysteme angefordert werden.

Betreuung:
Privatdozent Dr. rer.nat. habil. Sven Groppe

Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 500 5706