Суммирование данных до структуры данных дерева (в базе данных графа)

Question

У меня есть структура данных дерева, в которой данные вводятся в листовых узлах. То, что я хочу сделать, это суммировать эти данные по дереву, например. для любого узла в дереве суммируйте все данные под ним.

Есть ли какие-нибудь умные способы сделать это, используя базу данных ?

Answer 1

В шифром (Neo4j), вы можете сделать что-то вроде этого:

start n=node:node_auto_index(id={id}) 
match n-[:parent_of*]->child 
where not(child-[:parent_of]->()) // where the child doesn't have children (leaf) 
return n, sum(child.val); 

http://wes.skeweredrook.com/cypher-summing-data-up-a-tree-leaf-nodes/

Answer 2

Вот решение, используя Gremlin и выборку данных дерева, которые просто выскочил на список aureliusgraphs рассылки:

g = new TinkerGraph() 
root = g.addVertex(['name':'root']) 
c1 = g.addVertex(['name':'1', 'sortIndex':1]) 
c11 = g.addVertex(['name':'1.1', 'sortIndex':1]) 
c12 = g.addVertex(['name':'1.2', 'sortIndex':2]) 
c121 = g.addVertex(['name':'1.2.1','sortIndex':1]) 
c122 = g.addVertex(['name':'1.2.2','sortIndex':2]) 
c13 = g.addVertex(['name':'1.3', 'sortIndex':3]) 
c2 = g.addVertex(['name':'2', 'sortIndex':2]) 
c21 = g.addVertex(['name':'2.1', 'sortIndex':1]) 
c22 = g.addVertex(['name':'2.2', 'sortIndex':2]) 
c3 = g.addVertex(['name':'3', 'sortIndex':3]) 
c31 = g.addVertex(['name':'3.1', 'sortIndex':1]) 
c32 = g.addVertex(['name':'3.2', 'sortIndex':2]) 
g.addEdge(root, c1, 'has') 
g.addEdge(root, c2, 'has') 
g.addEdge(root, c3, 'has') 
g.addEdge(c1, c11, 'has') 
g.addEdge(c1, c12, 'has') 
g.addEdge(c1, c13, 'has') 
g.addEdge(c2, c21, 'has') 
g.addEdge(c2, c22, 'has') 
g.addEdge(c3, c31, 'has') 
g.addEdge(c3, c32, 'has') 
g.addEdge(c12, c121, 'has') 
g.addEdge(c12, c122, 'has') 

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

gremlin> total=0;root.out.sideEffect{total+=it.sortIndex}.loop(2){true} 
gremlin> total 
==>21 

Приведенный выше код инициализирует total переменную, а затем начинает обход от root вершины, пройдя, а затем добавив значение поля sortIndex к итогу. Затем он завершает/повторяет эту операцию над деревом до тех пор, пока не исчерпает его (окончательный true будет контролировать, как долго он петли).

Я использовал TinkerGraph для удобства, но этот код будет работать с Neo4j или OrientDB (я видел те, как и другие теги на этот вопрос), просто изменяя реализацию графа следующим образом:

g = new Neo4jGraph('/tmp/neo4j') 

или

g = new OrientGraph('memory:/graph')