Как эффективно удалить узлы, к которым можно обратиться из другого узла, не пропуская другие узлы и имеющие только 1 входящее отношение?

Question

Я использую Property Graph и Cypher из Neo4j. Как описано в заголовке, я пытаюсь удалить несколько узлов, к которым можно обратиться из другого узла, не пропуская другие узлы и которые имеют только 1 входящее отношение. Вот пример этого случая:

Каждый узел имеет свою метку (большой, жирный символ) и свойство, называемое nodeId, который является уникальным среди узлов. Метки отношений опущены, потому что мы не можем полагаться на это по некоторым причинам. nodeId свойство уже проиндексировано с уникальным ограничением.

Теперь, начиная с узла A {nodeId: 1}Я хочу удалить его и все остальные узлы, которые:

• может быть достигнуто с A {nodeId: 1} без прохождения другого узла A-метки.
• только 1 входящие отношения

Итак, узлы будут удалены: A {nodeId: 1}, B {nodeId: 3}, C {nodeId: 4}, а также C {nodeId: 8},

Ниже мой код Cypher:

MATCH p = (s:A {nodeId: 1 }) -[*1..10]-> (e)
WHERE NONE (x in NODES(p) WHERE x:A AND NOT x.nodeId = 1)
WITH s, e
MATCH (e) <-[r]- ()
WITH count(r) AS num_r, s, e
WHERE num_r < 2
DETACH DELETE e
DETACH DELETE s

Код работает нормально, но по мере роста моего графика он становится все медленнее и медленнее. В начале это занимает менее 10 мс. Но теперь, когда у меня есть около 1 миллиона узлов и 2 миллиона отношений, это занимает более 1 секунды.

Что я должен сделать, чтобы улучшить производительность этого кода?

Спасибо за помощь.

Answer 1

Поскольку вас волнует только наличие пути A, вы должны использовать shorttestPath вместо (a)-[*]->(b), Таким образом, Cypher просто нужно найти 1 действительный путь вместо всех возможных путей (это может быть спасателем в больших наборах). Кроме того, вы можете использовать TAIL, чтобы отрезать первый элемент в списке, чтобы вы могли (Cypher может) пропустить эту проверку.

В зависимости от вашей версии Neo4j, Использование MATCH <path> WHERE <stuff> WITH DISTINCT startnode ,endnode может быть более эффективным, так как более поздние планировщики Cypher могут использовать подсказку WITH DISTINCT для более быстрого и менее исчерпывающего сопоставления пути. В более ранних версиях будет зависать Neo4j, и вам нужно будет использовать библиотеку APOC neo4j.

MATCH (s:A {nodeId: 1 })
WITH s MATCH p=shortestPath((s)-[*1..10]->(e))
WHERE NONE (x in TAIL(NODES(p)) WHERE x:A) AND NOT ()-->(e)<--()
WITH DISTINCT s, e
DETACH DELETE e
DETACH DELETE s

Вы также можете изменить NOT ()-->(e)<--() в SIZE(()-->(e)) < 2 если вам нужно изменить это число. Первый может работать лучше в некоторых Cypher Planner, хотя. Возможно, вам придется изменить это значение на "Все родители e содержатся в пути", если это сценарий, в котором e может иметь более 2 входящих отношений, но все же его необходимо удалить.

Если ваша логика становится более сложной, чем эта (где удаляемые узлы могут изменить другие узлы, которые можно удалить

Answer 2

Tezra имеет правильную идею для Cypher-версии этого запроса (но без использования shorttestPath()).

Альтернативный подход, который может работать лучше в более сложном графе, - это использовать процедуры APOC, которые имеют процедуры расширения пути, которые будут хорошо работать в вашем случае использования, находя только отдельные пути к каждому отдельному узлу и эффективно фильтруя по меткам.

Вот как вы можете использовать это, используя apoc.path.subgraphNodes()

MATCH (s:A {nodeId: 1 })
CALL apoc.path.subgraphNodes(s, {maxLevel:10, labelFilter:'-A'}) YIELD node as e
WITH s, e 
WHERE size((e)<--()) = 1
DETACH DELETE e
WITH distinct s
DETACH DELETE s

LabelFilter в вызове процедуры гарантирует, что ни один узел в расширении не имеет :A label (фильтр не применяется к начальному узлу расширения по умолчанию, который работает в вашем случае здесь, хотя это настраивается).

РЕДАКТИРОВАТЬ

Однако одним из недостатков этого подхода является то, что это расширяет любые отношения в любом направлении.

Несмотря на то, что RelationshipFilter может фильтровать по направлению, в настоящее время есть ошибка, которая не позволяет нам указывать только направление отношения без типа.