Glossar

ACID

ACID ist ein Akronym für Atomicity Consistency Isolation Durability. Sie gelten als Voraussetzung für die Verlässlichkeit von Datenbanktransaktionen.

Atomarität

Eine Transaktion ist eine Folge von Datenbankoperationen, die entweder vollständig oder gar nicht ausgeführt werden.

Konsistenz

Transaktion, die nach Beendigung einen konsistenten Zustand hinterlässt. Dabei werden vor Abschluss der Transaktion die im Datenbankschema definierten Integritätsbedingungen überprüft.

Isolation

Nebenläufige Transaktionen dürfen sich nicht beeinflussen. Realisiert wird dies üblicherweise mit Locking, das die Nebenläufigkeit einschränkt.

Durability

Daten müssen nach erfolgreicher Transaktion dauerhaft in der Datenbankgespeichert bleiben und kann z.B. durch das Schreiben eines Transaktionslogs sichergestellt werden.

BASE

BASE ist ein Akronym für Basically Available, Soft State, Eventually Consistent und als Gegenbegriff zu ACID entstanden.

Dabei wird ein sehr optimistischer Konsistenzbegriff verwendet, der ohne Locking auskommt. Locks sind in mehrerlei Hinsicht problematisch, da Zugriffe nicht möglich sind, solange Datensätze durch andere Transaktionen gesperrt sind. Zudem ist die Übereinkunft zum Setzen eines Locks bereits sehr aufwändig.

Konsistenz der Daten wird als ein Zustand betrachtet, der irgendwann erreicht werden kann. Dies ist die Idee der Eventual Consistency.

Konkurrierende Zugriffe werden bei BASE durch MVCC – Multiversion Concurrency Control vermieden. Es gibt jedoch eine große Bandbreite von Lösungen für die verschiedenen verteilten Datenbanksysteme:

  • Causal Consistency

    ist der Konsistenz in ACID vergleichbar.

  • Read Your Writes

  • Session Consistency

  • Monotonic Read Consistency

  • Monotonic Write Consistency

CAP-Theorem

CAP ist ein Akronym für Consistency, Availability (Verfügbarkeit) und Partition Tolerance (Ausfalltoleranz). Die Erkenntnisse des CAP-Theorems spielen bei der Auswahl eines verteilten Datenbanksystems eine zentrale Rolle.

Das CAP-Theorem besagt, dass in verteilen Systemen die drei Anforderungen Konsistenz, Verfügbarkeit und Ausfalltoleranz nicht vollständig vereinbar und nur maximal zwei von dreien erreichbar sind. Für jede Anwendung muss daher individuell entschieden werden, ob eine CA-, CP-, AP-Applikation realisiert werden soll.

Cassandra

Cassandra ist ein Spaltenorientierte Datenbanksysteme, und wurde ursprünglich von Facebook entwickelt um Suchen im E-Mail-Engang zu optimieren. Heute wird es unter dem Dach der Apache Software Foundation weiterentwickelt.

Das Datenmodell von Cassandra hat weder eine logische Struktur noch ein Schema. Für die Modellierung wird empfohlen «First write your queries, then model your data». Meist wird dann eine Column Family für jede erwartete Anfrage erstellt. Dabei werden die Daten zwar denormalisiert, aber jede Column Family antwortet auf eine bestimmte Art von Anfragen.

In Cassandra kann für jede Anfrage die Konsistenz angegeben werden. Das ermöglicht, dass spezifische Anfragen sehr konsistent sein können während andere die Konsistenz der Geschwindigkeit opfern. Für die Schreibkonsistenz gibt es z.B. die folgenden vier Ebenen:

ANY

gewährleistet, dass die Daten in mindestens einem Knoten gespeichert sind.

ONE

gewährleistet, dass die Daten im Commit-Log von mindestens einer Replica gespeichert sind.

QUORUM

gewährleistet, dass die Daten in einen Quorum von Replicas gespeichert sind.

ALL

gewährleistet, dass die Daten auf alle Replicas gespeichert sind.

Cassandra stellt zwei verschiedene APIs zur Verfügung: Thrift und CQL (Cassandra Query Language).

Column Family

Column Families entsprechen Tabellen in relationalen Datenbanken. Sie gruppieren Spalten gleichen oder ähnlichen Inhalts, z.B.:

profile = {
    cusy: {
        name:       "Cusy GmbH",
        email:      "info@cusy.io",
        website:    "cusy.io"
    },
    veit: {
        name:       "Veit Schiele",
        email:      "veit.schiele@cusy.io",
    }
}
CouchDB

CouchDB ein Akronym für Cluster of unreliable commodity hardware Data Base. Dabei handelt es sich um ein Dokumentenorientierte Datenbanksysteme.

Eventual Consistency

»Konsistenz als Zustandsübergang, der irgendwann erreicht wird.«

Der Begriff wurde für BASE als Alternative zu ACID entwickelt.

Graph traversal

Graph traversal wird meist zur Suche von Knoten verwendet. Es gibt verschiedene Algorithmen für solche Suchanfragen in einem Graphen, die sich grob einteilen lassen in

  • Breiten- und Tiefensuche (engl: breadth-first search, BFS und depth-first search, DFS)

    Die Breitensuche beginnt mit allen Nachbarknoten des Startknotens. Im nächsten Schritt werden dann die Nachbarn der Nachbarn durchsucht. Die Pfadlänge erhöht sich mit jeder Iteration.

    Die Tiefensuche verfolgt einen Pfad solange, bis ein Knoten ohne ausgehende Kanten gefunden wird. Der Pfad wird anschließend zurückverfolgt bis zu einem Knoten, der noch weitere ausgehende Kanten hat. Dort wird die Suche dann fortgesetzt.

  • Algorithmische Traversierung

    Beispiele für die algorithmische Traversierung sind

    • Hamiltonweg (Traveling Salesman)

    • Eulerweg

    • Dijkstra-Algorithmus

  • Randomisierte Traversierung

    Der Graph wird nicht nach einem bestimmten Schema durchlaufen, sondern der nächste Knoten wird zufällig ausgewählt. Dadurch kann vor allem bei großen Graphen wesentlich schneller ein Suchergebnis präsentieren, dieses ist jedoch nicht immer das beste.

Graphenmodell

Ein Graph besteht aus einer Menge an Knoten und Kanten. Graphen werden genutzt, um eine Vielfalt an Problemen durch Knoten, Kanten und ihren Beziehungen darzustellen, z.B. in Navigationssystemen, in denen die Wege in Form von Graphen gespeichert werden.

Graphpartitionierung

Mit Graphpartitionierung werden Graphen in kleinere Teilgraphen unterteilt. Dabei gibt es jedoch keine mathematisch exakte Methode, um die Anzahl der durchschnittenen Kanten zu minimieren, sondern nur ein paar heuristische Algorithmen, z.B. Clustering-Algorithmen, die stark vernetzte Teilgraphen zu abstrakten Knoten zusammenziehen.

Von sich überlappenden Partitionierung spricht man bei Graphen, die nicht komplett geteilt werden können und in mehreren Teilgraphen existieren.

HBase

HBase ist ein Spaltenorientierte Datenbanksysteme, welches auf verteilten Dateisystemen aufbaut und für real-time-Zugriffe auf großen Datenbeständen konzipiert ist.

Hypertable

Hypertable ist ein Spaltenorientierte Datenbanksysteme und auf verteilten Dateisystemen basiert. Das Datenmodell ist das einer mehrdimensionalen Tabelle, die mit Schlüsseln durchsucht werden kann. Die erste Dimension ist der sog. row-key, die zweite die Column Family die dritte Dimension der Column Qualifier und die vierte Dimension die Zeit.

Konsistente Hashfunktion

Konsistente Hashfunktionen minimieren die Anzahl der Neuzuordnungen, da bei einer Änderung nicht alle Schlüssel neu zugeordnet werden müssen sondern nur die Größe einer Hash-Tabelle geändert wird.

Konsistenz

Der Zustand einer Datenbank wird als konsistent bezeichnet, wenn die gespeicherten Daten alle Anforderungen for Semantische Integrität erfüllen.

Locking

Als Locking bezeichnet man das Sperren von Daten für nebenläufige Transaktionen.

Je nach Art des Zugriffs gibt es unterschiedliche Lock-Verfahren:

MapReduce

MapReduce ist ein von Google Inc. 2004 eingeführtes Framework, das für die nebenläufige Berechnungen enorm großer Datenmengen auf Computerclustern verwendet wird. Es wurde durch die, in der funktionalen Programmierung häufig verwendeten Funktionen map und reduce inspiriert auch wenn die Semantik von diesen etwas abweicht.

MongoDB

MongoDB ist eine schemafrei Dokumentenorientierte Datenbanksysteme, die Dokumente im BSON-Format verwaltet.

MVCC – Multiversion Concurrency Control

MVCC werden kontrolliert konkurrierende Zugriffe auf Datensätze (Lesen, Einfügen, Ändern, Löschen) durch verschiedene, unveränderliche Versionen dieser Datensätze. Die verschiedenen Versionen werden in eine zeitliche Reihenfolge gebracht, indem jede Version auf ihre Vorgängerversion verweist. MVCC hat sich gerade bei NoSQL-Datenbanken zu einer zentralen Basistechnologie entwickelt, die es ermöglicht, konkurrierende Zugriffe auch ohne das Locking von Datensätzen zu koordinieren.

Optimistic Concurrency

Optimistic Concurrency, auch Optimistisches Locking ist eine Form des Locking, die davon ausgeht, dass wenige schreibende Zugriffe auf der Datenbank stattfinden und lesende Zugriffe keine Sperre auslösen. Bei Änderungen wird dann zunächst geprüft, ob der Zeitstempel seit dem Lesen der Daten unverändert geblieben ist.

Paxos

Paxos ist eine Familie von Protokollen zur Herstellung von Konsens in einem Netzwerk unzuverlässiger oder fehlbarer Prozessoren.

Pessimistic Locking

Pessimistic Locking geht von vielen Schreibzugriffen auf die Datenbank aus. Daher sperren auch lesende Zugriffe die Daten werden erst wieder freigegeben, wenn die Änderungen gespeichert sind.

Property-Graph-Modell
PGM

Knoten und Kanten bestehen aus Objekten mit darin eingebetteten Eigenschaften (Properties). Es wird nicht nur ein Wert (Label) in einer Kante bzw. einem Knoten gespeichert, sondern ein Schlüssel/Wert-Paar.

Riak

Im Wesentlichen ist Riak ein dezentraler Schlüssel/Wert-Paar mit einer flexiblen MapReduce-Engine.

Redis

Redis ist ein Schlüssel-Werte-Datenbanksysteme, die üblicherweise alle Daten im RAM speichert.

Schlüssel/Wert-Paar

Ein Wert ist immer einem bestimmten Schlüssel zugeordnet, der aus einer strukturierten oder willkürlichen Zeichenkette bestehen kann. Diese Schlüssel können in Namensräume und Datenbanken aufgeteilt werden. Die Werte können neben Strings auch Listen, Sets oder Hashes enthalten.

Semantische Integrität

Semantische Integrität ist immer dann gegeben, wenn die Eingaben richtig und in sich stimmig sind. Dann wird auch von konsistenten Daten gesprochen. Ist dies nicht der Fall, sind die Daten inkonsistent. In SQL kann die semantische Integrität mit TRIGGER und CONSTRAINT überprüft werden.

Two-phase locking (2PL)

Das Zwei-Phasen-Sperrprotokoll unterscheidet zwei Phasen von Transaktionen:

  1. Die Wachstumsphase, in welcher Sperren nur gesetzt, aber nicht freigegeben werden dürfen.

  2. Die Schrumpfungsphase, in welcher Sperren nur freigegeben, aber nicht angefordert werden dürfen.

Das Zwei-Phasen-Sperrprotokoll kennt dabei drei Sperrzustände:

SLOCK, Shared Lock oder Read-Lock

wird bei lesendem Zugriff auf Daten gesetzt

XLOCK, Exclusive Lock oder Write-Lock

wird bei schreibendem Zugriff auf Daten gesetzt

UNLOCK

hebt die Sperren SLOCK und XLOCK auf.

Vektoruhr

Eine Vektoruhr ist eine Softwarekomponente zum Zuweisen von eindeutigen Zeitstempeln an Nachrichten. Sie erlaubt, den Ereignissen in verteilten Systemen aufgrund eines Zeitstempels eine Kausalordnung zuzuweisen und insbesondere die Nebenläufigkeit von Ereignissen zu ermitteln.

XPATH

XPATH verarbeitet die Baumstruktur eines XML-Dokuments und erzeugt dabei Ausschnitte aus XML-Dokumenten. Um als Ergebnis vollständige XML-Dokumente zu erhalten, müssen diese z.B. mit XQuery oder XSLT erstellt werden. XPATH ist keine vollständige Abfragesprache, da sie auf Selektionen und Extraktionen beschränkt ist.

XPATH ist ein Bestandteil von XQuery seit Version 1.1 und ab Version 2.0 wird XPATH durch XQuery erweitert.

XQuery

XQuery steht für XML Query Language und ist hauptsächlich eine funktionale Sprache, bei der während einer Abfrage auch verschachtelte Ausdrücke ausgewertet werden können.

XSLT

XSLT ist ein Akronym für Extensible Stylesheet Language Transformation. Mit ihr lassen sich XML-Dokumente transformieren.