Datenbanken Online Lexikon TH Köln, Campus Gummersbach
Aktuelle Änderungen - Suchen:

InfiniteGraph

InfiniteGraph ist eine sehr junge NoSQL Graphendatenbank, welche auf der Infrastruktur der Objektdatenbank Objectivity/DB aufbaut. InfiniteGraph und Objectivity/DB werden von der Firma Objectivity Inc. gepflegt, welche die Object Management Group (OMG) und Object Data Management Group (ODMG) mitgegr�ndet hat. Folgende Mechanismen werden bereits von Objectivity/DB umgesetzt.

  1. Jedes Objekt in der Datenbank hat eine eindeutige Identit�t
  2. Objekte k�nnen durch Kanten verbunden werden. Hierbei sind auch mehrfach Kanten und bidirektionale Kanten erlaubt.
  3. Die Datenbank kann SQL Anfragen beantworten
  4. Die Datenbank kennt ein Iterator Konzept, welches im Gro�en und Ganzen einer Graph Traversierung entspricht
  5. Es wird ein synchrones und quorum-basiertes Verfahren zur Replikation genutzt, auf welches im Kapitel Replikation in InfiniteGraph n�her eingegangen wird.

InfiniteGraph nutzt diese Vorentwicklungen. Somit konnte sehr schnell eine graphenorientierte Programmierschnittstelle angeboten werden. Im nachfolgenden wird im allgemeinen das Produkt InfiniteGraph beschrieben. Da dieses jedoch nicht ohne den "Unterbau" Objectivity/DB auskommt, werden auch einige Konzepte dieser Datenbank, die f�r die Nutzung von InfiniteGraph relevant oder von Vorteil sind, beschrieben.


Inhalt

Steckbrief
Datenmodell
Architektur
Replikation
Transaktionen
Indizierung
Kommunikation
Bewertung
Quellen



Steckbrief

Webadressehttp://www.infinitegraph.com
KategorieVerteilte Graphdatenbank
DatenmodellProperty Graph
SchemaJava Klassen
Query-MethodeTraverser API, PQL
APIJava
PersistenzObjectivity/DB
TransaktionenACID, lokal und verteilt
Replikation/SkalierungObjectivity/DB, derzeit keine Graphpartitionierung
LizenenKommerziell, Demoversion mit bis zu 1000000 Knoten

Datenmodell

Das Datenmodell von InfiniteGraph entspricht einem Property-Graphen. Knoten und Kanten werden durch objektorientierte Klassen definiert. Diese erben von Basisklassen aus der API Schnittstelle. Die Basisklassen definieren ein statisches Grundschema welches z.B. eine eindeutige Identit�t implementiert. Durch Attribute der Klassen k�nnen weitere Properties erzeugt werden. Momentan gibt es keinen Schemamanager der die Verbindung zwischen Knoten und Kanten �berpr�ft. In InfiniteGraph besitzen Kanten eine Gewichtung. Dies sorgt f�r eine reduzierte Betrachtung von Kanten bei Analyseverfahren. Da bei vielen Analyseverfahren ein hoher Prozentsatz der betrachteten Kanten irrelevant ist, ist dies eine sinnvolle Technik. Zur Indizierung von Properties nutzt InfiniteGraph sowohl eigene Indextypen aber auch Alternativen wie die Indizies vom Open Source Projekt Lucene. Knoten k�nnen ebenfalls Namen gegeben werden, was einen schnelleren Zugriff erlaubt.

Architektur


Abbildung 1: Architektur von InfiniteGraph[1]

Die genaue Verbindung der Dateien, die im nachfolgenden einzeln beschrieben werden, kann Abbildung 1 entnommen werden.

  • Konfigurationsdatei

Beim Erstellen einer Datenbank wird eine vorher angelegte Konfigurationsdatei genutzt. Die Konfigurationsdatei ist eine Propertiedatei (.properties) welche Informationen zum Erstellen der Datenbank enth�lt. Dazu z�hlt die eindeutige ID der Datenbank sowie die Spezifikation der StorageUnits. Auch andere Konfigurationen, wie z.B. das Abschalten der MROW Funktionalit�t k�nnen hier definiert werden.

  • Bootdatei

Beim Erstellen einer Datenbank wird automatisch eine Bootdatei erzeugt (.boot). Diese wird unter dem Pfad erzeugt, der im 'BootFilePath' der Konfigurationsdatei angegeben wurde. Dabei handelt es sich um eine Textdatei, die Informationen zum �ffnen einer Datenbank enth�lt. Weitere Informationen aus der Konfigurationsdatei, wie der zu verwendende Lockserver oder der Name bzw. die Identifikation der Datenbank, werden ebenfalls in die Bootdatei kopiert.
Die Bootdatei enth�lt den Pfad zur Systemdatenbankdatei.

  • Systemdatenbankdatei

Die Systemdatenbankdatei (.fdb) wird ebenfalls automatisch erzeugt. Standardm��ig im selben Pfad wie die Bootdatei.
Die Systemdatenbankdatei enth�lt eine Liste aller individuellen Datenbankdateien und aller autonomen Partitionen falls mehr als eine existiert.
Wenn das erste Objekt eines definierten Typs in der Datenbank gespeichert wird, wird das zugeh�rige Schema erzeugt und in der Systemdatenbank gespeichert.

  • Individuelle Datenbankdateien

Es werden auch die individuellen Datenbankdateien erzeugt (.DB). Auf diese wird im Kapitel �ber StorageUnits n�her eingegangen. Kurz zusammengefasst, existieren f�r die verschiedenen Typen, Knoten, Kanten und Connectoren, einzelne Datenbankdateien. Beim Speichern eines Objekts eines bestimmten Typs wird dieses in der zugeh�rigen Datenbankdatei gespeichert bzw. in deren Containern.

  • Journaldateien

Wenn eine Applikation �nderungen an der Datenbank vornimmt werden Journal Dateien (.JNL) angelegt. Diese werden genutzt, um beim Abbruch bzw. Fehlschlag einer Transaktion, den letzten konsitenten Datenbankzustand wieder herzustellen.


  • Storage Unit

Abbildung 3: Eine StorageUnit[1]

Abbildung 2: Eine StorageUnit und ihre Container[1]

Wenn eine Applikation Knoten oder Kanten in die Datenbank einf�gt, werden diese in Datenbankdateien gespeichert. Eine StorageUnit ist eine Kombination aus Speicherort und Spezifikation, die Richtlinien �ber das Zuweisen von Daten enth�lt. Jede StorageUnit speichert Daten in drei verschiedenen Datenbankdateien (siehe Abbildung 3). Eine InfiniteGraph Datenbank kann auch mehrere StorageUnits nutzen. Ist dies der Fall werden die Datenbankdateien fortlaufend nummeriert. Jede Datenbankdatei besitzt eine Nummer an Containern. Container sind die technische Umsetzung der Speicherung von Daten (siehe Abbildung 2). Ihre initiale Gr��e, wird durch die StorageUnit Spezifikation bestimmt und ergibt sich aus dem minimal zul�ssigen Wert. Es werden auch maximal zul�ssige Werte angegeben. Ebenso kann die initiale Menge von Containern spezifiziert werden. Die Spezifikation einer StorageUnit wird dann immer f�r alle drei Datenbankdateien angewendet. Durch diese Spezifikation ist eine gezielte Auslagerung der Daten im Netzwerk m�glich.


  • Lockserver

Ein Lockserver ist daf�r zust�ndig, den Datenbankzugriff durch Locks auf Daten zu steuern um die Daten konsistent zu halten. Dadurch werden anfragenden Transaktionen Locks vergeben und entzogen. Daf�r wird immer der Container gelockt, der die angefragten Daten enth�lt. Wenn ein zweiter Lock auf einen bereits gelockten Container angefragt wird, kann dieser nur dann erteilt werden, wenn die beiden Locks kompatibel sind. Dies ist z.B. der Fall, wenn es sich beim ersten Lock um einen Lock mit Leserechten handelt, und beim zweiten Lock ebenfalls. Auch die Kombination Lesen und Schreiben ist erlaubt.
W�hrend einer Transaktion ist es m�glich 'stale data' ,also veraltete Daten, zu erhalten, da InfiniteGraph MROW erlaubt. MROW steht f�r Multiple Readers, One Writer. Diese Eigenschaft kann manuell deaktiviert werden. Dies f�hrt jedoch zu Performance Nachteilen.

Replikation


Abbildung 4: Der Aufbau einer autonomen Partition[4]

Datenreplikation wird in InfiniteGraph durch Objectivity/DRO (Data Replication Option) erreicht. Dieses Feature ist Teil der Grundlage von InfiniteGraph, Objectivity/DB. Objectivity/DRO nutzt mehrere Datenbankimages um synchrone Replikation zu gew�hrleisten.
Synchrone Replikation bedeutet, dass bei einem Update auf einem Datenbankimage alle anderen existierenden Images ebenfalls aktualisiert werden. Vorteil dieses Mechanismus ist die st�ndige Konsistenz der Daten. Nachteil dieses Mechanismus ist die Fehleranf�lligkeit durch Ausfall eines Servers der ein Datenbankimage enth�lt. In diesem Fall kann die synchrone Replikation nicht durchgef�hrt werden.
Objectivity/DRO modifiziert den beschriebenen Mechanismus um ein Verfahren, welches eine Mindestzahl an erreichbaren Datenbankimages ben�tigt, die zusammen einen konsistenten Datenbankzustand repr�sentieren k�nnen. Dazu werden die Datenbankimages in autonome Partitionen abgelegt. Autonome Partitionen sind unabh�ngig von Netzwerk- oder Systemfehlern anderer Partitionen und besitzen einen eigenen Lockserver. Jede autonome Partition besitzt eine komplette Architektur (siehe Abbildung 4). In der Systemdatenbankdatei sind Referenzen zu allen anderen autonomen Partitionen hinterlegt.
Stellt eine Transaktion eine Anfrage an einen Lockserver werden alle anderen Lockserver kontaktiert. Antwortet eine Mehrzahl, wird der Transaktion der Zugriff auf die Daten gew�hrt. Die Transaktion wird dann auf allen erreichbaren Datenbankimages synchron durchgef�hrt. In dieser Zeit k�nnen keinen anderen Transaktionen auf die Container zugreifen um Konsistenz der Daten zu gew�hrleisten. Eine Mehrzahl an Datenbankimages bwz. an autonomen Partitionen wird als Quorum bezeichnet.
Datenimages, die nach einiger Zeit wieder erreichbar sind, werden in Objectivity/DRO automatisch mit dem aktuellen Status synchronisiert. Dieser wird durch die Mehrzahl der Datenbankimages repr�sentiert. Standardm��ig ist dieses Verfahren f�r READ und WRITE Transaktionen aktiviert. F�r READ Transaktionen kann es aber vom Anwendungsentwickler deaktiviert werden.
Objectivity/FTO (Fault Tolerant Option), das hier nicht n�her beschrieben werden soll, bietet ein administratives Tool um autonome Partitionen zu erzeugen und ist bei jeder InfiniteGraph Installation verf�gbar.


Transaktionen

Um in InfiniteGraph mit der Datenbank zu kommunizieren, sind Transaktionen notwendig. Transaktionen sind bereits Teil von Objectivity/DB. Durch die Verwendung von Transaktionen werden ACID Eigenschaften erreicht. Beim Durchf�hren einer Transaktion, wird der Container, der die relevanten Daten enth�lt, vom Lockserver f�r andere unzul�ssige Transaktionen gesperrt. Erst nach dem Commit einer Transaktion werden die Daten bzw. der Container wieder frei gegeben. Der nachfolgende Code demonstriert die einfache Umsetzung von Transaktionen durch die InfiniteGraph Java API.
Transaction tx = myGraph.beginTransaction(AccessMode.READ_WRITE);
  //Mache etwas in der Transaktion
tx.commit()

Indizierung

InfiniteGraph unterst�tzt drei verschiedene Index-Implementierungen.

  • Graph Index
Dies ist der Basismechanismus zum indizieren von Objekten in InfiniteGraph. Hierbei werden alle Objekte eines angegebenen Typs automatisch in den Index eingepflegt. Daf�r m�ssen ein Name, eine Klasse sowie ein oder mehrere Attribute angegeben werden. Indizierbare Typen sind short, int, long, float, double und String von Knoten oder Kanten. Das nachfolgende Beispiel erzeugt einen Index mit dem Namen 'myGraphIndexName' f�r das Attribut bzw. die Property 'name' des Knoten 'Person'. Es wird ebenfalls dargestellt, wie ein solcher Index geladen werden kann.
IndexManager.<Person>createGraphIndex("myGraphIndexName", Person.class.getName(), "name");
personGraphIndex = IndexManager.getGraphIndex(Person.class.getName(), "name");
  • Generic Index

Beim Generic Index hat der Entwickler die volle Kontrolle dar�ber, welche Objekte in den Index aufgenommen werden sollen. Dazu muss er nach der Erzeugung des Index alle Objekte eines Typs explizit hinzuf�gen. Dabei lassen sich Logiken einbauen.

Das nachfolgende Beispiel zeigt, wie nur Knoten vom Typ Person und dem Namen "John" in den Index aufgenommen werden.
//Erzeugen eines generischen Index
IndexManager.<Person>createGenericIndex("myGenericIndex", Person.class.getName(), "name");

//Laden des generischen Index
GenericIndex<Person> myGenericIndex IndexManager.getGenericIndexByName("myGenericIndex");

//Iteration �ber alle Knoten vom Typ Person
Iterable<Vertex> vertexItr = myGraphDB.getVertices(Person.class.getName());
  try{
    for (Vertex vertex�: vertexItr){
      Person returnedVertex = (Person) vertex;

      //Wenn der Name der Person 'John' ist wird das Objekt dem Index hinzugef�gt
      if(returnedVertex.getName().equals("John"))
        myGenericIndex.put(returnedVertex);
    }
  }
  catch(IndexException ndxe){
   //Something TODO here
  }       
  • Lucine Index

InfiniteGraph unterst�tzt Apache Lucene� Volltext Indizierung und Suchunterst�tzung mit der LuceneIndex Klasse. Durch diese Implementierung eines Index, wird jedes indizierte Attribut in Text umgewandelt. Weiter wird hier auf diese Art der Indizierung nicht eingegangen, da ebenfalls eine genauere Erkl�rung des Apache Lucene� Projekts notwendig w�re.

Kommunikation

Die Kommunikation mit der Datenbank erfolgt immer �ber die Java API, die von InfinteGraph zur Verf�gung gestellt wird.

  • CRUD

CRUD steht f�r Create Read Update Delete und beschreibt die Basisoperationen zur Manipulation von Daten.
Nachdem eine Datenbank erstellt und ge�ffnet ist, k�nnen Knoten und Kanten hinzugef�gt werden. Dazu werden Instanzen von Klassen gebildet, die definierte Basistypen und damit auch Basisfunktionalit�ten erben.
Diese sind

  1. BaseVertex f�r Knoten und
  2. BaseEdge f�r Kanten
Ausgehend f�r die Beschreibung aller Operationen ist die Klasse Person, die einen Knoten abbildet und im folgenden Code Ausschnitt dargestellt ist. Das Objekt 'myGraph' steht f�r die bereits ge�ffnete Datenbank. Die Implementierung von Transaktionen wird hier nicht mit dargestellt.
public class Person extends BaseVertex
{
    private String name;

    public Employee(String name){
        setName(name);    
    }

    private void setName(String name){
        markModified();
        this.name = name;
    }

    public String getName(){
        fetch();
        return this.name;
    }
}
  • Create
Um einen Knoten vom Typ Person in der Datenbank zu speichern, muss dieser zuerst erzeugt werden.
Person person = new Person("markus");
Danach kann das Objekt 'person' innerhalb einer Transaktion der Datenbank hinzugef�gt werden.
myGraph.addVertex(person);
  • Read

Um einen Knoten wieder aus der Datenbank zu laden, verwendet man entweder dessen Index oder einen einfachen Graph Traverse. Beide M�glichkeiten werden in den nachfolgenden Kapiteln beschrieben.

  • Update

Zum �ndern eines Datensatzes, muss dieser zuerst aus der Datenbank geladen werden. Danach k�nnen seine Attribute wie bei normalen Java Objekten �ber die Getter und Setter Methoden ver�ndert werden. Wichtig hierbei ist, dass diese Methoden markModified() bzw. fetch() aufrufen, da der geladene Datensatz nur eine leere H�lle ist. markModified() signalisiert der Datenbank, dass �nderungen am Objekt vorgenommen wurden. fetch() signalisiert der Datenbank, dass die Daten des Attributes Lazy nachgeladen werden sollen.

  • Delete
Um einen Eintrag aus einer Datenbank zu l�schen, muss dieser entweder zuerst geladen worden sein oder seine ID muss bekannt sein. Daraufhin stehen folgende Methoden zur Verf�gung.
myGraph.removeVertex(person);
myGraph.removeVertexById(id);
  • Predicate Query Language

Abbildung 5: Beispiel einer 'Operator Expression' in PQL[2]

Die Predicate Query Language (PQL) ist Teil der Objectivity/DB und damit auch f�r InfiniteGraph verf�gbar. Da es sich um eine Query Language handelt, werden nur Abfragen von Daten unterst�tzt. Manipulation oder das Erzeugen von Daten ist nicht m�glich. PQL besitzt eine Menge von Operatoren die zusammen mit Operanden eine 'Operator Expression' bilden. 'Attribute Expressions' verweisen dabei auf Attribute bereits persistierter Objekte w�hrend 'Literal Expressions' Konstanten sind, die mit den Werten der Attribute verglichen werden (siehe Abbildung 5). Eine beispielhafte Abfrage in Java unter Verwendung eines Index kann folgenderma�en aussehen.
IndexIterable<Person> indexItr = personGraphIndex.query(new PredicateQuery("name='John' && age < 100")); Hierbei werden Personen aus der Datenbank geladen, deren Name �John� ist und die j�nger als 100 Jahre sind. Die Verwendung von 'Operator Expressions' �hnelt stark der Syntax von SQL. Die Verwendung von Regular Expressions ist ebenfalls m�glich.

  • Traversierung

Abbildung 6: Traversierung eines Graphen in InfinityGraph[3]

InfiniteGraph unterst�tzt sowohl eine Breitensuche als auch eine Tiefensuche. Diese Suche kann von jedem Knoten im Graphen gestartet werden. Die Tiefen- bzw. Breitensuche kann durch den Entwickler manipuliert werden. Dazu k�nnen sowohl 'Path-' als auch 'Result Qualifier' implementiert werden. Ein 'Path Qualifier' entscheidet bei jedem Knoten ob der Weg weiter verfolgt wird oder nicht. Der 'Result Qualifier' entscheidet ob Pfade relevant f�r das Ergebnis sind. Dazu k�nnen, wie beim 'Path Qualifier', benutzerdefinierte Regeln implementiert werden. Um Ergebnisse zu verwerten m�ssen 'Result Handler' implementiert werden, die Pfade verwerten die als qualifiziert gelten. Abbildung 6 illustriert den detaillierten Ablauf eine Traversierung in InfiniteGraph. Im nachfolgenden wird ein Code Beispiel dargestellt welches durch eine individuelle Implementierung eines 'Result Handlers' die Knoten der durchlaufenden Pfade ausgibt. 'root' ist dabei der Startknoten f�r die Traversierung durch eine Tiefensuche.



PrintPathResultsHandler resultPrinter = 
  new PrintPathResultsHandler();

//Es wird ein Navigator erzeugt, der eine Tiefensuche durchf�hrt
//und jeden Pfad bis zum Ende verfolgt.
//Dabei wird jeder Knoten dem ResultHandler �bergeben
Navigator myNavigator = root.navigate
  (Guide.SIMPLE_DEPTH_FIRST, Qualifier.FOREVER,
   Qualifier.Any, resultPrinter);

myNavigator.start();
myNavigator.stop();

class PrintPathResultsHandler implements 
  NavigationResultHandler{

  @Override
  public void handleNavigatorFinished(Navigator arg0) {}

  @Override
  public void handleResultPath(Path path, Navigator arg1) {
    for(Hop h :path){
      System.out.println(h.getVertex().toString());
    }
  }


Bewertung

Im nachfolgenden werden die Vor- und Nachteile von InfiniteGraph betrachtet.
Vorteile

  1. Durch Objectivity/DB besitzt InfiniteGraph einen Unterbau, der bereits Persistenz, Replikation und Transaktionen implementiert.
  2. Eine sehr gute Unterst�tzung f�r die objektorientierte Programmiersprache Java vorhanden.
  3. InfiniteGraph bzw. Objectivity/DB hat mit seinen StorageUnits ein gutes Konzept zur Auslagerung von Daten auf entfernte Systeme.

Nachteile

  1. Sehr junges Projekt. Dies f�hrt wahrscheinlich zu h�ufigen Ver�nderungen an der API.
  2. Keine uniqueness oder mandatory (not null) constraints f�r Properties an Knoten und Kanten. Dies kann allerdings durch Konzepte der objektorientierten Programmierung erreicht werden.
  3. Keine Netzwerkschnittstellen wie REST

Quellen

Allgemeine Quellen die im Text verwendet wurden

http://www.objectivity.com/pages/downloads/whitepaper/html/datareplication.html
http://wiki.infinitegraph.com/2.1/w/index.php?title=Tutorial:_Using_the_Navigator
http://wiki.infinitegraph.com/2.1/w/index.php?title=InfiniteGraph_System_Architecture
http://devnet.objectivity.com/files/docs/objy_docs/latest/java/guide/jgdObjectQualification.html#1180258
Stefan EDLICH, Achim FRIEDLAND, jens HAMPE, benjamin BRAUER, markus BR�CKNER - NoSQL Einstieg in die Welt nichtrelationaler Web 2.0 Datenbanken - Hanser 2011

Quellen der verwendeten Grafiken [1] http://wiki.infinitegraph.com/2.1/w/index.php?title=InfiniteGraph_System_Architecture
[2]http://devnet.objectivity.com/files/docs/objy_docs/latest/java/guide/jgdObjectQualification.html#1180258
[3]http://wiki.infinitegraph.com/2.1/w/index.php?title=Tutorial:_Using_the_Navigator
[4]Objectivity/FTO and Objectivity/DRO Release 5.2

Kategorie Graphen-DB,Neue DB-Entwicklungen, NoSQL, I