Graphdatenbanken

Kurz gesagt: Eine Graphdatenbank wie Neo4j speichert Knoten und Beziehungen statt Tabellen, und Cypher-Abfragen suchen Muster und Pfade darin.

Problem

Leute, die Kaffee gekauft haben, kauften auch

Unter jedem Produkt will der Shop eine Zeile „Leute, die das gekauft haben, kauften auch“. Für die Kaffeebohnen sieht die Abfrage auf der SQL-Datenbank so aus:

SQLDatenbank: Shop

SELECT p2.name, COUNT(DISTINCT o2.customer_id) AS buyers
FROM products p1
JOIN order_items i1 ON i1.product_id = p1.id
JOIN orders o1 ON o1.id = i1.order_id AND o1.status <> 'cancelled'
JOIN orders o2 ON o2.customer_id = o1.customer_id AND o2.status <> 'cancelled'
JOIN order_items i2 ON i2.order_id = o2.id
JOIN products p2 ON p2.id = i2.product_id
WHERE p1.name = 'Kaffeebohnen' AND p2.id <> p1.id
GROUP BY p2.id, p2.name
ORDER BY buyers DESC, p2.name
LIMIT 5;

SELECT p2.name, COUNT(DISTINCT o2.customer_id) AS buyers FROM products p1 JOIN order_items i1 ON i1.product_id = p1.id JOIN orders o1 ON o1.id = i1.order_id AND o1.status <> 'cancelled' JOIN orders o2 ON o2.customer_id = o1.customer_id AND o2.status <> 'cancelled' JOIN order_items i2 ON i2.order_id = o2.id JOIN products p2 ON p2.id = i2.product_id WHERE p1.name = 'Kaffeebohnen' AND p2.id <> p1.id GROUP BY p2.id, p2.name ORDER BY buyers DESC, p2.name LIMIT 5;

▶ AusführenAbfrage zurücksetzenNeue Datenbank

Sie geht durch sechs Tabellen: vom Produkt zu den Bestellpositionen, zu den Bestellungen, zum Kunden, zu seinen anderen Bestellungen, zu deren Positionen und zu den Produkten. orders und order_items kommen je zweimal vor. Der nächste Wunsch ist noch schwerer: „die Produkte der Leute, deren Empfehlungen du folgst, und der Leute, denen sie folgen“. Jeder Schritt sind mehr Joins, und „bis zu drei Schritte“ braucht WITH RECURSIVE. Die Frage geht um Verbindungen zwischen Dingen, und in Tabellen sind die Verbindungen über Fremdschlüssel verstreut.

Die Idee

Knoten und Beziehungen

Eine Graphdatenbank hält die Daten als Graph: Knoten (die Dinge, wie ein Kunde und ein Produkt) und Beziehungen zwischen ihnen. Jede Beziehung hat einen Typ (BOUGHT) und eine Richtung (vom Kunden zum Produkt). Knoten haben Labels (:Customer), und sowohl Knoten als auch Beziehungen haben Eigenschaften (name, price, quantity). Die Beziehung ist in der Datenbank gespeichert und wird nicht in jeder Abfrage mit einem JOIN gesucht: Von einem Knoten geht die Datenbank direkt zu seinen Nachbarn.

Die bekannteste Graphdatenbank ist Neo4j, und ihre Sprache heißt Cypher. Ihre Muster sind Zeichnungen aus Zeichen: (c:Customer) ist ein Knoten, und -[:BOUGHT]-> ist ein Pfeil.

Graphdatenbank (wie Neo4j)Simulator

CREATE (m:Customer {name: 'Maria Ivanova', city: 'Sofia'})
CREATE (k:Product {name: 'Kaffeebohnen', price: 14.90})
CREATE (m)-[:BOUGHT {quantity: 2}]->(k);

MATCH (c:Customer)-[b:BOUGHT]->(p:Product)
RETURN c.name, b.quantity, p.name;

CREATE (m:Customer {name: 'Maria Ivanova', city: 'Sofia'}) CREATE (k:Product {name: 'Kaffeebohnen', price: 14.90}) CREATE (m)-[:BOUGHT {quantity: 2}]->(k); MATCH (c:Customer)-[b:BOUGHT]->(p:Product) RETURN c.name, b.quantity, p.name;

▶ AusführenBefehle zurücksetzenNeue Datenbank

Die Abfrage endet mit ;, sie kann also über mehrere Zeilen gehen. CREATE legt Knoten und Beziehungen an. MATCH findet alles, was zum Muster passt, und RETURN sagt, was angezeigt wird. Unter der Ausgabe zeichnet der Simulator die Knoten und Beziehungen, die er gefunden hat.

Genauer, für Neugierige

Der Simulator kennt einen Teil von Cypher: MATCH, WHERE, CREATE, MERGE, SET, DELETE, DETACH DELETE, RETURN, ORDER BY, SKIP, LIMIT und ein paar Funktionen. Es gibt kein WITH, kein OPTIONAL MATCH, kein UNWIND, keine Indizes und keine Constraints. Die Ausgabe sieht aus wie die Konsole cypher-shell, ohne die Zeile mit der Abfragezeit, und die Fehlermeldungen sind kürzer. Der Simulator zeigt die Eingabeaufforderung vor jeder Zeile einer Abfrage. Neo4j Browser braucht kein ; am Ende und zeichnet das Ergebnis selbst. Ohne ORDER BY liefert der Simulator die Zeilen in der Reihenfolge, in der die Knoten angelegt wurden, und Neo4j verspricht überhaupt keine Reihenfolge.

Probier es aus

Georgi und das Brot

Die Datenbank ist leer. Halte fest, dass der Kunde Georgi Petrov Weißbrot gekauft hat: ein Knoten mit dem Label Customer und einer Eigenschaft name, ein Knoten mit dem Label Product und einer Eigenschaft name, und eine Beziehung BOUGHT vom Kunden zum Produkt.

Graphdatenbank (wie Neo4j)Simulator

CREATE (g:Customer {name: 'Georgi Petrov'});

CREATE (g:Customer {name: 'Georgi Petrov'});

Prüfen▶ Ausführen

Die Idee

Muster

Ab hier ist die Datenbank der Shop: 20 Kunden, 25 Produkte in 6 Kategorien und 109 BOUGHT-Beziehungen, eine für jeden Kunden und jedes Produkt aus den Bestellungen, die nicht storniert wurden. Sie stammen aus der SQL-Datenbank des Kurses. Ein Produkt ist mit seiner Kategorie durch eine IN-Beziehung verbunden.

Ein Muster kann so lang sein, wie du es brauchst: vom Kunden über das Produkt zur Kategorie, ohne ein einziges Join.

Graphdatenbank (wie Neo4j)Simulator

MATCH (c:Customer {name: 'Elena Dimitrova'})-[:BOUGHT]->(p:Product)-[:IN]->(cat:Category)
RETURN p.name, p.price, cat.name
ORDER BY p.name;

MATCH (c:Customer {name: 'Elena Dimitrova'})-[:BOUGHT]->(p:Product)-[:IN]->(cat:Category) RETURN p.name, p.price, cat.name ORDER BY p.name;

▶ AusführenBefehle zurücksetzenNeue Datenbank

Die Richtung im Muster muss zur Richtung der Beziehung passen:

Graphdatenbank (wie Neo4j)Simulator

// Der Pfeil zeigt vom Kunden zum Produkt. In der anderen Richtung gibt es nichts:
MATCH (:Product {name: 'Kaffeebohnen'})-[:BOUGHT]->(c:Customer)
RETURN c.name;

// Dieselbe Beziehung, vom anderen Ende gelesen:
MATCH (:Product {name: 'Kaffeebohnen'})<-[:BOUGHT]-(c:Customer)
RETURN c.name, c.city
ORDER BY c.name;

// Der Pfeil zeigt vom Kunden zum Produkt. In der anderen Richtung gibt es nichts: MATCH (:Product {name: 'Kaffeebohnen'})-[:BOUGHT]->(c:Customer) RETURN c.name; // Dieselbe Beziehung, vom anderen Ende gelesen: MATCH (:Product {name: 'Kaffeebohnen'})<-[:BOUGHT]-(c:Customer) RETURN c.name, c.city ORDER BY c.name;

▶ AusführenBefehle zurücksetzenNeue Datenbank

Es gibt keine BOUGHT-Pfeile vom Produkt zu einem Kunden, deshalb findet die erste Abfrage niemanden. <-[:BOUGHT]- liest dieselbe Beziehung von ihrem anderen Ende. -[:BOUGHT]- ohne Pfeilspitze findet die Beziehung in beiden Richtungen.

Genauer, für Neugierige

Der Graph hält nicht die einzelnen Bestellungen: Eine BOUGHT-Beziehung sagt nur, dass der Kunde das Produkt gekauft hat. Brauchst du auch die Bestellungen, werden sie zu Knoten: (:Customer)-[:PLACED]->(:Order)-[:CONTAINS {quantity: 2}]->(:Product). Was ein Knoten und was eine Beziehung ist, hängt von den Fragen ab, die du stellen wirst, genau wie beim Schema einer SQL-Datenbank.

Sieh es dir an

Dieselbe Frage, ein Muster

So sieht „Leute, die Kaffee gekauft haben, kauften auch“ in Cypher aus:

Graphdatenbank (wie Neo4j)Simulator

MATCH (:Product {name: 'Kaffeebohnen'})<-[:BOUGHT]-(c:Customer)-[:BOUGHT]->(p:Product)
RETURN p.name, count(c) AS buyers
ORDER BY buyers DESC, p.name
LIMIT 5;

MATCH (:Product {name: 'Kaffeebohnen'})<-[:BOUGHT]-(c:Customer)-[:BOUGHT]->(p:Product) RETURN p.name, count(c) AS buyers ORDER BY buyers DESC, p.name LIMIT 5;

▶ AusführenBefehle zurücksetzenNeue Datenbank

Die Antwort ist Zeile für Zeile dieselbe wie bei der SQL-Abfrage am Anfang. Das Muster liest sich von links nach rechts: der Kaffee, gekauft von einem Kunden, der auch ein anderes Produkt gekauft hat. Der Kaffee wird nicht gegen sich selbst gezählt: In einem MATCH kann dieselbe Beziehung nicht zweimal vorkommen, und die Beziehung zum Kaffee ist schon vergeben. In SQL war das eine eigene Bedingung (p2.id <> p1.id). Nur drei Leute haben Kaffee gekauft, deshalb haben alle fünf Produkte je zwei Käufer und sind nach Namen geordnet.

Der Unterschied ist nicht nur die Länge. Die SQL-Datenbank schlägt jedes Join in einem Index oder in der ganzen Tabelle nach. Die Graphdatenbank beginnt beim Kaffee und folgt nur seinen Beziehungen: Die Arbeit hängt davon ab, wie viele Beziehungen um den Kaffee liegen, nicht davon, wie viele Bestellungen der Shop hat.

Die Idee

Pfade variabler Länge

Sagen wir, der Shop hat Profile, und jeder Kunde kann den Empfehlungen anderer Kunden folgen: (:Customer)-[:FOLLOWS]->(:Customer). Diese Beziehungen sind für die Lektion ausgedacht; die SQL-Datenbank hat sie nicht.

-[:FOLLOWS*1..2]-> ist ein Pfad aus einem bis zwei FOLLOWS-Schritten. p = … gibt dem ganzen Pfad einen Namen, und length(p) ist seine Anzahl an Schritten:

Graphdatenbank (wie Neo4j)Simulator

// Alle Wege aus einem oder zwei Schritten. Viktoria kommt zweimal vor: Zwei Pfade führen zu ihr
MATCH (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..2]->(f:Customer)
RETURN f.name;

// Jede Person einmal, mit dem kürzesten Pfad zu ihr
MATCH p = (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..3]->(f:Customer)
WHERE f <> me
RETURN f.name, min(length(p)) AS steps
ORDER BY steps, f.name;

// Alle Wege aus einem oder zwei Schritten. Viktoria kommt zweimal vor: Zwei Pfade führen zu ihr MATCH (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..2]->(f:Customer) RETURN f.name; // Jede Person einmal, mit dem kürzesten Pfad zu ihr MATCH p = (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..3]->(f:Customer) WHERE f <> me RETURN f.name, min(length(p)) AS steps ORDER BY steps, f.name;

▶ AusführenBefehle zurücksetzenNeue Datenbank

Im ersten Ergebnis kommt Viktoria zweimal vor: Elena folgt Maria und Dimitar, und beide folgen Viktoria. MATCH liefert jeden Pfad, nicht jede Person. In der zweiten Abfrage entfernt WHERE f <> me Elena selbst: Nach drei Schritten kommt der Pfad zu ihr zurück (Elena, Maria, Viktoria, Elena).

Wer auf dem Pfad liegt, zeigt nodes(p):

Graphdatenbank (wie Neo4j)Simulator

MATCH p = (:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*2]->(:Customer {name: 'Aleksandar Iliev'})
RETURN [n IN nodes(p) | n.name] AS route;

MATCH p = (:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*2]->(:Customer {name: 'Aleksandar Iliev'}) RETURN [n IN nodes(p) | n.name] AS route;

▶ AusführenBefehle zurücksetzenNeue Datenbank

In SQL ist dasselbe WITH RECURSIVE über einer Tabelle follows: ein Anfang, UNION ALL und ein Schritt, der follows mit den vorigen Zeilen verbindet, dazu ein Schrittzähler. Hier ist es *1..3.

Sieh es dir an

Ein Pfad ohne Grenze

Ein Muster ohne Typ und ohne Richtung, „alles, was mit Elena verbunden ist“, mit einem immer längeren Pfad:

Graphdatenbank (wie Neo4j)Simulator

// Alles, was mit Elena verbunden ist, über jede Beziehung, in jede Richtung
MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..2]-(x)
RETURN count(*) AS routes;
MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..3]-(x)
RETURN count(*) AS routes;
MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..4]-(x)
RETURN count(*) AS routes;

// Ohne obere Grenze
MATCH (:Customer {name: 'Elena Dimitrova'})-[*]-(x)
RETURN count(*) AS routes;

// Alles, was mit Elena verbunden ist, über jede Beziehung, in jede Richtung MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..2]-(x) RETURN count(*) AS routes; MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..3]-(x) RETURN count(*) AS routes; MATCH (:Customer {name: 'Elena Dimitrova'})-[*1..4]-(x) RETURN count(*) AS routes; // Ohne obere Grenze MATCH (:Customer {name: 'Elena Dimitrova'})-[*]-(x) RETURN count(*) AS routes;

▶ AusführenBefehle zurücksetzenNeue Datenbank

98 Wege, dann 688, dann 4.370. Jeder Schritt vervielfacht sie mit sechs bis sieben, weil ein Produkt wie Weißbrot mit vielen Kunden verbunden ist und jeder von ihnen mit vielen Produkten. * ohne obere Grenze probiert jeden Weg. Der Simulator hält nach 100.000 Schritten an, und Neo4j hält nicht von selbst an: Die Abfrage läuft, bis ihr die Zeit oder der Speicher ausgeht. Schreibe also immer eine obere Grenze, und wenn du kannst, auch den Typ und die Richtung der Beziehung.

Übung

Empfehlungen

1. Auch der Käse braucht eine Zeile „Leute, die das gekauft haben, kauften auch“.

Welche drei Produkte haben die Leute, die Weißkäse gekauft haben, am meisten gekauft? Zeige den Namen und die Anzahl der Käufer (buyers), die meisten zuerst, und bei gleicher Anzahl nach Namen.

Graphdatenbank (wie Neo4j)Simulator

MATCH (:Product {name: 'Weißkäse'})<-[:BOUGHT]-(c:Customer)
RETURN c.name;

MATCH (:Product {name: 'Weißkäse'})<-[:BOUGHT]-(c:Customer) RETURN c.name;

Prüfen▶ Ausführen

2. Maria Ivanova folgt ein paar Leuten, und die folgen anderen.

Zeige die Kunden, die Maria Ivanova über FOLLOWS in einem oder zwei Schritten erreicht, jeden einmal, nach Namen geordnet.

Graphdatenbank (wie Neo4j)Simulator

MATCH (:Customer {name: 'Maria Ivanova'})-[:FOLLOWS]->(f:Customer)
RETURN f.name;

MATCH (:Customer {name: 'Maria Ivanova'})-[:FOLLOWS]->(f:Customer) RETURN f.name;

Prüfen▶ Ausführen

3. Jetzt die echte Empfehlung.

Finde die Produkte, die die Leute gekauft haben, denen Elena Dimitrova in einem oder zwei Schritten folgt und die sie selbst noch nicht gekauft hat. Zeige die drei, die von den meisten verschiedenen Leuten (people) gekauft wurden, und bei gleicher Anzahl nach Namen.

Graphdatenbank (wie Neo4j)Simulator

MATCH (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..2]->(f:Customer)
RETURN DISTINCT f.name;

MATCH (me:Customer {name: 'Elena Dimitrova'})-[:FOLLOWS*1..2]->(f:Customer) RETURN DISTINCT f.name;

Prüfen▶ Ausführen

Die Idee

Wann eine Graphdatenbank, und wann nicht

Eine Graphdatenbank ist gut, wenn die Frage um Verbindungen geht, oft über mehrere Schritte: Empfehlungen („Leute, die das gekauft haben, kauften auch“), soziale Netzwerke, Betrugserkennung (Konten, die ein Telefon oder eine Adresse teilen), Wege und Abhängigkeiten, Zugriffsrechte über Gruppen. Sie ist nicht gut für Berichte, die Zahlen aus allen Datensätzen addieren, wie der Umsatz pro Monat: Eine solche Abfrage folgt keinen Beziehungen, sie liest alles der Reihe nach. Das ist eine Aufgabe für SQL mit GROUP BY oder für eine Datenbank, die für Berichte gebaut ist (OLAP). Ein Graph steht also meist neben der SQL-Datenbank: Die Bestellungen und das Geld bleiben in SQL, und eine Kopie der Verbindungen geht für die Empfehlungen in den Graphen.

Genauer, für Neugierige

Neben Neo4j verstehen auch Memgraph und Amazon Neptune Cypher (dort heißt die Sprache openCypher; Neptune versteht auch Gremlin und SPARQL), und die Erweiterung Apache AGE bringt Cypher in PostgreSQL. 2024 erschien der internationale Standard GQL (ISO/IEC 39075), der sich stark auf die Ideen von Cypher stützt. Eine andere Art von Graphdatenbank ist der RDF-Store mit der Sprache SPARQL, in dem alles ein Tripel aus „Subjekt, Prädikat, Objekt“ ist.

Test

Teste dich

1. Was sagt das Muster (c:Customer)-[:BOUGHT]->(p:Product)?

Die Tabelle Customer wird mit der Tabelle Product verbundenDie Kunden und die Produkte mit demselben NamenEin Knoten mit dem Label Customer, verbunden mit einem Knoten mit dem Label Product durch eine Beziehung vom Typ BOUGHT, die auf das Produkt zeigt

2. MATCH (me)-[:FOLLOWS*1..2]->(f) RETURN f.name liefert Viktoria zweimal. Warum?

Viktoria ist doppelt gespeichertDie Datenbank hat einen FehlerZwei verschiedene Pfade führen zu ihr, und MATCH liefert jeden Pfad

3. Was passiert mit einem Muster -[*]- ohne obere Grenze in einem großen Graphen?

Nichts Besonderes, sie ist nur ein wenig langsamerDie Datenbank hält von selbst bei 3 Schritten anDie Wege vermehren sich wie eine Lawine, und die Abfrage wird vielleicht nie fertig

4. Du brauchst den Umsatz pro Monat für die letzten zwei Jahre. Wohin gehört diese Abfrage?

In die SQL-Datenbank (oder eine spaltenorientierte für Berichte), mit SUM und GROUP BYIn die Graphdatenbank, weil die Bestellungen mit den Kunden verbunden sindIn den Cache

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Bäume und Folgen: WITH RECURSIVE · Beziehungstypen: 1:1, 1:N, M:N · Indizes · OLTP und OLAP
• Geht weiter in: Wie du eine Datenbank wählst
• Aufgaben zum Thema: Arten von Datenbanken