Erstellen von hierarchischen Daten (Baum) Strukturen in Neo4j „Baum Keys“

Question

Ich habe Daten aus einer CSV Datei importiert und eine Menge von Knoten erstellt, von denen alle verwandt sind zu anderen Knoten innerhalb des gleichen Datensatzes basiert auf einem „Baum Number“ Hierarchiesystem: der Knoten mit Baumnummer

zum Beispiel istA01.111 ein direkter Nachkomme von Knoten A01, und der Knoten mit BaumnummerA01.111.230 ist eine schreckliche ct Kind des Knotens A01.111.

Was ich versuche zu tun ist schaffen einzigartige Beziehungen zwischen Knoten, die direkte Kinder anderer Knoten sind. Zum Beispiel Knoten A01.111.230 sollte nur haben eine "IS_CHILD_OF" -Beziehung, mit Knoten A01.111.

Ich habe mehrere Dinge ausprobiert, zum Beispiel:

MATCH (n:Node), (n2:Node) 
WHERE (n2.treeNumber STARTS WITH n.treeNumber) 
AND (n <> n2) 
AND NOT ((n2)-[:IS_CHILD_OF]->()) 
CREATE UNIQUE (n2)-[:IS_CHILD_OF]->(n); 

Dieses Beispiel führt zu schaffen einzigartige „IS_CHILD_OF“ Beziehungen aber nicht mit den direkt Eltern ein Knotens. Vielmehr würde der Knoten A01.111.230 mit dem Knoten A01 in Beziehung stehen.

Answer 1

Ich denke, ich habe gerade eine Lösung gefunden! (Wenn jemand eine elegantere hat man bitte tun post)

Ich habe erkannt, dass die „Baum-Nummer“ Codierungssystem verwendet immer 3-stellige Zahlen zwischen den Punkten, dh A01.111.230 oder C02.100, Wenn also ein Knoten das direkte Kind eines anderen Knotens ist, dann sollte die "Baumnummer" nicht nur mit der Baumnummer des Elternknotens beginnen, sondern auch 4 Zeichen länger sein (ein Zeichen für den Punkt '.' und 3 Zeichen für den numerischen Wert).

Daher meine Lösung, die Arbeit zu tun scheint, ist:

MATCH (n:Node), (n2:Node) 
WHERE (n2.treeNumber STARTS WITH n.treeNumber) 
AND (length(n2.treeNumber) = (length(n.treeNumber) + 4)) 
CREATE UNIQUE (n2)-[:IS_CHILD_OF]->(n); 

Answer 2

Für Ihre Anforderung STARTS WITH wird nicht funktionieren, da A01.111.23 in der Tat mit A01 neben Start startet mit A01.111.

Die treeNumber besteht aus mehreren Teilen mit '.' als Trennzeichen. Nehmen wir keine Annahmen über die maximal/minimal möglichen Zeichenlängen der einzelnen Teile. Was wir brauchen, ist es, alle bis auf den letzten Teil jedes Knotens treeNumber mit dem des potentiellen untergeordneten Knotens zu vergleichen, der getestet wird. Sie können dies mit Cypher split() Funktion erreichen Sie wie folgt vor:

MATCH (n1:Node), (n2:Node) 
WHERE split(n2.treeNumber,'.')[0..-1] = split(n1.treeNumber,'.') 
CREATE UNIQUE (n2)-[:IS_CHILD_OF]->(n1); 

Die split() Funktion eine Zeichenfolge teilt, bei jedem Auftreten eines bestimmten Separator in eine Liste von Strings (Teile).In diesem Zusammenhang ist das Trennzeichen "." um alle treeNumber zu teilen. Wir können eine Teilmenge einer Liste in der Chiffre mit der Syntax list[{startIndex}..{endIndex}] auswählen. Negative Indizes für das Reverse-Lookup sind zulässig, beispielsweise das in der obigen Abfrage verwendete.

Diese Lösung sollte auf alle möglichen treeNumber Werte im vorliegenden Format verallgemeinert werden, unabhängig von der Anzahl der Teile und der Länge der einzelnen Teile.

Answer 3

Ich denke, wir können die Abfrage ein wenig verbessern. Stellen Sie zunächst sicher, dass Sie entweder eine eindeutige Integritätsregel oder einen Index für Node.treeNumber haben, da Sie diese benötigen, um die Suche nach übergeordneten Knoten in dieser Abfrage zu verbessern.

Als nächstes passen wir uns an untergeordnete Knoten an, ausgenommen root-Knoten (vorausgesetzt, no.'s in der treeNumber des root) und Knoten, die bereits verarbeitet wurden und bereits eine Beziehung haben.

Dann werden wir die Eltern jedes Knotens durch die Baumnummer mit unserem Index finden und die Beziehung erstellen. Dies setzt voraus, dass eine untergeordnete Baumnummer immer vier weitere Zeichen enthält, einschließlich des Punkts.

MATCH (child:Node) 
WHERE child.treeNumber CONTAINS '.' 
AND NOT EXISTS((child)-[:IS_CHILD_OF]->()) 
WITH child, SUBSTRING(child.treeNumber, 0, SIZE(child.treeNumber)-4) as parentNumber 
MATCH (parent:Node) 
WHERE parent.treeNumber = parentNumber 
CREATE UNIQUE (child)-[:IS_CHILD_OF]->(parent) 

Ich denke, diese Abfrage ein kartesisches Produkt vermeidet, wie Sie von anderen Antworten bekommen können, und sollte um O (n) (jemand korrigieren Sie mich, wenn ich falsch) sein.

EDIT

Für den Fall, dass jede Untergruppe von Zahlen in treeNumbers NICHT bis 3 (wie in Ihrer Beschreibung, tatsächlich, mit ‚A01.111.23‘) gezwungen wird, dann müssen Sie ein anderes Mittel, um die parentNumber Ableiten . Neo4j ist hier ein wenig schwach, da es sowohl eine indexOf() - Funktion als auch eine join() -Funktion zum Umkehren eines split() fehlt. Möglicherweise müssen Sie die APOC Procedures library installiert, um den Zugriff auf eine Join() -Funktion zu ermöglichen.

Die Abfrage Fälle mit variabler zählt der Stellen in den numerischen Untergruppen von treeNumber zu handhaben wird dies:

MATCH (child:Node) 
WHERE child.treeNumber CONTAINS '.' 
AND NOT EXISTS((child)-[:IS_CHILD_OF]->()) 
WITH child, SPLIT(child.treeNumber, '.') as splitNumber 
CALL apoc.text.join(splitNumber[0..-1], '.') YIELD value AS parentNumber 
WITH child, parentNumber 
MATCH (parent:Node) 
WHERE parent.treeNumber = parentNumber 
CREATE UNIQUE (child)-[:IS_CHILD_OF]->(parent) 

Answer 4

ich eine andere allgemeine Lösung vorschlagen möchten, auch ein kartesisches Produkt vermieden wird, wie @InverseFalcon weist darauf hin, .

Lassen Sie sich in der Tat beginnen, indem Sie einen Index für eine schnellere Lookup Erstellen und Einfügen einig Testdaten:

CREATE CONSTRAINT ON (n:Node) ASSERT n.treeNumber IS UNIQUE; 
CREATE (n:Node {treeNumber: 'A01.111.230'}) 
CREATE (n:Node {treeNumber: 'A01.111'}) 
CREATE (n:Node {treeNumber: 'A01'}) 

Dann müssen wir alle Knoten als potentiell Eltern scannen, und suchen Sie nach Kindern, die mit den treeNumber von Anfang an Eltern (STARTS WITH können den Index verwenden) und haben keine Punkte in der "Rest" des treeNumber (dh direkte Kind), statt Spaltung, Fügen, etc .:

MATCH (p:Node), (c:Node) 
WHERE c.treeNumber STARTS WITH p.treeNumber 
    AND p <> c 
    AND NOT substring(c.treeNumber, length(p.treeNumber) + 1) CONTAINS '.' 
RETURN p, c 

Ich ersetzte die Erstellung der Beziehung durch eine einfache RETURN für Profilierungszwecke, aber Sie können es einfach durch CREATE UNIQUE oder MERGE ersetzen.

Eigentlich können wir der p <> c Prädikat loszuwerden und die + 1 auf die Länge, indem die tatsächliche Präfix vor der Berechnung, die übereinstimmen sollten:

MATCH (p:Node) 
WITH p, p.treeNumber + '.' AS parentNumber 
MATCH (c:Node) 
WHERE c.treeNumber STARTS WITH parentNumber 
    AND NOT substring(c.treeNumber, length(parentNumber)) CONTAINS '.' 
RETURN p, c 

zeigt jedoch, dass die Abfrage Profilieren, dass der Index nicht, verwendet und es ist ein kartesisches Produkt (so haben wir einen O (n^2) Algorithmus):

Aber

, wenn wir einfach einen Hinweis hinzufügen, wie so

MATCH (p:Node) 
WITH p, p.treeNumber + '.' AS parentNumber 
MATCH (c:Node) 
USING INDEX c:Node(treeNumber) 
WHERE c.treeNumber STARTS WITH parentNumber 
    AND NOT substring(c.treeNumber, length(parentNumber)) CONTAINS '.' 
RETURN p, c 

den Index nicht nutzen, und wir haben so etwas wie ein O (n * log (n)) Algorithmus (log (n) für den Index lookup):

Compiler CYPHER 3.0 

Planner COST 

Runtime INTERPRETED 

+-------------------------------+----------------+------+---------+----------------------+------------------------------------------------------------------------------------------+ 
| Operator      | Estimated Rows | Rows | DB Hits | Variables   | Other                     | 
+-------------------------------+----------------+------+---------+----------------------+------------------------------------------------------------------------------------------+ 
| +ProduceResults    |    2 | 2 |  0 | c, p     | p, c                      | 
| |        +----------------+------+---------+----------------------+------------------------------------------------------------------------------------------+ 
| +Filter      |    2 | 2 |  6 | c, p, parentNumber | NOT(Contains(SubstringFunction(c.treeNumber,length(parentNumber),None),{ AUTOSTRING1})) | 
| |        +----------------+------+---------+----------------------+------------------------------------------------------------------------------------------+ 
| +Apply      |    2 | 3 |  0 | p, parentNumber -- c |                       | 
| |\       +----------------+------+---------+----------------------+------------------------------------------------------------------------------------------+ 
| | +NodeUniqueIndexSeekByRange |    9 | 3 |  6 | c     | :Node(treeNumber STARTS WITH parentNumber)            | 
| |        +----------------+------+---------+----------------------+------------------------------------------------------------------------------------------+ 
| +Projection     |    3 | 3 |  3 | parentNumber -- p | p; Add(p.treeNumber,{ AUTOSTRING0})              | 
| |        +----------------+------+---------+----------------------+------------------------------------------------------------------------------------------+ 
| +NodeByLabelScan    |    3 | 3 |  4 | p     | :Node                     | 
+-------------------------------+----------------+------+---------+----------------------+------------------------------------------------------------------------------------------+ 

Total database accesses: 19 

beachte, dass ich ein wenig zu betrügen hat, wenn zuvor das Präfix den WITH Schritt der Einführung zu schaffen, wie ich über

01.235.164 es verbessert den Ausführungsplan und DB zugreift bemerkt

MATCH (p:Node), (c:Node) 
USING INDEX c:Node(treeNumber) 
WHERE c.treeNumber STARTS WITH p.treeNumber 
    AND p <> c 
    AND NOT substring(c.treeNumber, length(p.treeNumber) + 1) CONTAINS '.' 
RETURN p, c 

, die den folgenden Ausführungsplan hat:

Compiler CYPHER 3.0 

Planner RULE 

Runtime INTERPRETED 

+--------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------+ 
| Operator  | Rows | DB Hits | Variables | Other                              | 
+--------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------+ 
| +Filter  | 2 |  9 | c, p  | NOT(p == c) AND NOT(Contains(SubstringFunction(c.treeNumber,Add(length(p.treeNumber),{ AUTOINT0}),None),{ AUTOSTRING1})) | 
| |   +------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------+ 
| +SchemaIndex | 6 |  12 | c -- p | PrefixSeekRangeExpression(p.treeNumber); :Node(treeNumber)                 | 
| |   +------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------+ 
| +NodeByLabel | 3 |  4 | p   | :Node                              | 
+--------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------+ 

Total database accesses: 25 

---

schließlich für die Aufzeichnung, ich den Ausführungsplan der ursprünglichen Abfrage geschrieben (d ohne den Hinweis) war:

Compiler CYPHER 3.0 

Planner COST 

Runtime INTERPRETED 

+--------------------+----------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+ 
| Operator   | Estimated Rows | Rows | DB Hits | Variables | Other                                        | 
+--------------------+----------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+ 
| +ProduceResults |    2 | 2 |  0 | c, p  | p, c                                         | 
| |     +----------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+ 
| +Filter   |    2 | 2 |  21 | c, p  | NOT(p == c) AND StartsWith(c.treeNumber,p.treeNumber) AND NOT(Contains(SubstringFunction(c.treeNumber,Add(length(p.treeNumber),{ AUTOINT0}),None),{ AUTOSTRING1})) | 
| |     +----------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+ 
| +CartesianProduct |    9 | 9 |  0 | p -- c |                                          | 
| |\     +----------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+ 
| | +NodeByLabelScan |    3 | 9 |  12 | c   | :Node                                        | 
| |     +----------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+ 
| +NodeByLabelScan |    3 | 3 |  4 | p   | :Node                                        | 
+--------------------+----------------+------+---------+-----------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+ 

Total database accesses: 37 

Es ist nicht das schlechtere ein: das eine ohne den Hinweis, aber mit der vorausberechneten Präfix ist! Deshalb sollten Sie immer messen.