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

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

0 голосов
/ 22 мая 2018

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

Example graph

Каждый узел имеет свою метку (большой, жирный символ) и свойство с именем 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 секунды.

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

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

Ответы [ 2 ]

0 голосов
/ 23 мая 2018

У 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 (фильтр не применяется к начальному узлу расширения по умолчанию, который работает в вашемслучай здесь, хотя это настраивается).

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

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

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

ОБНОВЛЕНИЕ

Начиная с APOCЛетние выпуски в 2018 году (3.3.0.4 вдоль линии 3.3.x и 3.4.0.2 вдоль линии 3.4.x) теперь вы можете указывать без установления типа только для направления в relationsFilter: relationshipFilter:'>'

0 голосов
/ 22 мая 2018

Поскольку вас волнует только путь 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 входящих связей, но все же его необходимо удалить.

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

...