Add Thesis

Optimierung einer Statistikdatenbank für Big Data

Written by Lars Bengel

Paper category

Bachelor Thesis

Subject

Computer Science

Year

2018

Abstract

Bachelorarbeit: Der KoralRDF-Graph wird in einer speziellen Datenbank gespeichert. Dies ist der sogenannte RDF-Speicher. Koral2 ist ein verteilter RDF-Speicher, der nach einer Master-Slave-Architektur aufgebaut ist.Diese Architektur umfasst einen Host, einen Master und einige andere Computer und Slaves. Der Master-Knoten übernimmt die Koordination von Anfragen auf dem Graphen, und die Slave-Knoten speichern die ihnen zugewiesenen Graphenpartitionen und führen Anfragen darauf aus. Alle Computer verfügen über einen Netzwerkmanager zur Kommunikation untereinander. Beim Laden von Grafiken wird zunächst ein Wörterbuch generiert und Textressourcen werden digitale IDs zugewiesen. In der Abbildung werden Ressourcen durch diese IDs ersetzt, um den Speicherbedarf zu reduzieren. Erstellen Sie dann Grafikpartitionen. Das bedeutet, dass der Graph ohne Informationsverlust in viele kleinere Graphpartitionen zerlegt wird. Erstellen Sie nach der Partitionierung des Graphen eine statistische Datenbank und bestimmen Sie die Verbindungszuständigkeiten. Jeder Ressource ist ein Untergeordneter zugeordnet, der von der Häufigkeit des Auftretens als Subjekt abhängt. Während der Ausführung der Anfrage ist dieser Slave dafür verantwortlich, alle Daten mit den ihm zugewiesenen Ressourcen zu kombinieren. Die Graphpartitionen werden dann an jede Slave-Station gesendet, die sie verwendet, um einen lokalen Triplett-Index zu erstellen. Die Anforderung für den Graphen wird vom Anforderungskoordinator verarbeitet und dann an jede Slave-Station verteilt. Jeder Slave führt eine Abfrage des lokalen Triplet-Index durch. Das Ergebnis wird an den Koordinator zurückgesendet, der mithilfe des Wörterbuchs die ID entschlüsselt und das Ergebnis zurückgibt. 1.1.2 Statistische Datenbank Durch die Partitionierung werden die Tripel des Graphen auf verschiedene Partitionen verteilt. Um alle Daten wiederfinden zu können, ohne alle Slaves abzufragen, wird eine Statistikdatenbank benötigt. Es speichert alle Ressourcen des Datensatzes als Subjekt-, Prädikats- oder Objektauftrittshäufigkeit in jeder Partition. Es besteht aus immer gleich langen Datenblöcken, aufgeteilt in 3 Teile. Diese Teile repräsentieren 3 mögliche Subjekte, Prädikate oder Objekte. Jeder Teil besteht aus n Feldern, und jedes Feld repräsentiert die Partition des in der Slave-Station gespeicherten Graphen für die Häufigkeit, mit der die Ressource in der Ressource erscheint. Die Größe jedes Feldes beträgt 8 Byte. In der aktuellen Implementierung ist die Größe jedes Datenblocks fest, und alle Blöcke werden fortlaufend in einer Datei gespeichert.Die Position eines Datenblocks in dieser Datei wird um die Ressourcen-ID und die feste Größe des Datenblocks erhöht. 2.2 Statistische Datenbank als Matrix Die statistische Datenbank kann auch als 3n-Matrix verstanden werden. Formel (2) stellt die Struktur dieser Matrix dar, die die Anzahl der Ressourcen ist, die in der Datenbank erscheinen, und nis ist die Anzahl der Partitionen, auf die die Tripel verteilt werden. Jede Zeile der Matrix besteht aus drei Teilen, die die drei Positionen Subjectsrc, Predicateprc und Objectorc darstellen. Es ist der Index der Zeile in der Statistikdatenbank und stellt die ID der Partition dar, die sich im Intervall [0, n) befindet. Daher enthält der Eintrag prc die Häufigkeit der Ressource am dreifachen Positionsprädikat in Partition c. Daher kann die statistische Datenbank als eine Abbildung basierend auf den Mengen von N [0; m) und [0; 3n) ausgedrückt werden. Die Signatur der Figur ist in Formel (3) dargestellt. Formel (4) gibt an, dass die Funktion statDB(r, j) .rist der Zeilenindex ist, der zwischen 0 und m liegt. Der Parameter j ist der Spaltenindex. Daraus lässt sich ableiten, ob es sich um ein Subjekt, ein Prädikat oder einen Objektwert handelt. Es wird auch verwendet, um den Index k zu berechnen, der angibt, in welcher Partition sich der Wert befindet. Existiert der angeforderte Wert nicht, wird 0 zurückgegeben. 2.3 Es gibt zwei Operationen, die verwendet werden können, um auf die statistische Datenbank zuzugreifen: Lesen (r) und Inkrementieren (r; j). Die Funktion read (r) ist in Formel (10) definiert. Es gibt die entsprechende Zeile in der Ressourcenstatistikdatenbank zurück. Die in Formel (11) definierte Funktion Inkrement (r; j) liest den Wert an der Position (r; j) in der Statistikdatenbank und schreibt den Inkrementwert an dieselbe Position zurück. Beispiel 7 Die Funktion read(r) in Formel (10) ist eine Leseoperation in der Statistikdatenbank. Es gibt ein Array zurück, das die Häufigkeit des Auftretens der Ressource enthält. Für das aktuelle Beispiel in Abbildung 4 gibt der Aufruf von read (11) das Array [0; 0; 2; 1; 0; 0] zurück. Die Funktion inkrement(r;j) in Formel (11) wird verwendet, um einen einzelnen Wert in der Statistikdatenbank zu erhöhen. Der Aufruf von Inkrement (1; 1) erhöht den Wert 11 von 3 auf 4, und Inkrement (3; 2) erhöht den Wert p32 von 0 auf 1. 3. Datenbankanalyse In diesem Abschnitt wird die Analyse der statistischen Datenbank durchgeführt. Dabei können die gesammelten Informationen zur Gestaltung von Optimierungsstrategien verwendet werden. Die Analyse bezieht sich auf eine Testdatenbank mit 100 Millionen Tripeln, die in 4 Partitionen aufgeteilt ist. Insgesamt enthält die Datenbank etwa 37,4 Millionen verschiedene Ressourcen. Ressourcen erhalten anhand ihres Aussehens eine ID, die inkrementell vergeben wird. Abschnitt 3.1 analysiert schreibende Zugriffe auf die Datenbank, während Abschnitt 3.2 sich mit statistischen Daten und deren Verteilung in der Datenbank beschäftigt. Read Less