2

Do you know any reference where to find SQL queries for traversing trees/graphs?

I found this one: http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html and Celko's book.

Problem is that the majority of resources I found refers to adiacency model trees, I'm using a normal edge list model.

Eg. queries or procedures to extract subpaths, subtrees, etc.

Thanks

Daniele
  • 359
  • 7
  • 15

2 Answers2

2

Nested sets models are best for hierarchical aggregations. Traversals for general graphs are best done with the adjacency list model. But I have used nested sets for convergent graphs by splitting nodes

 A
/ \
B C
\ /
 D

Becomes

 A
/ \
B C
|  |  
D  D

Since nests sets keep nodes in a separate table, this is easy.

You can also do a general graph as a forest of all possible spanning trees

ChrisR
  • 14,370
  • 16
  • 70
  • 107
Joe Celko
  • 36
  • 1
  • I'm really glad the author of the book replied! When you say "splitting nodes", do you mean duplicating nodes? I'm thinking to explore graphDB API, I'll let you know! – Daniele Mar 09 '11 at 18:55
0

If your graph is not frequently updated, using a GRIPP index will let you handle graph traversal queries extremely well. The latter lets you answer parent-child and depth-related queries in more or less fixed time -- irrespective of the graph's number of nodes or density of links.

Denis de Bernardy
  • 75,850
  • 13
  • 131
  • 154
  • @Denis do you have any practical examples of an implementation of the GRIPP index? All I can find are academid papers on the subject which are pretty hard to convert into practice for non-academic developers. – ChrisR Oct 08 '13 at 11:02
  • @ChrisR: I've implemented it myself once, for a side project, but I'm afraid I've no idea where the code is off the top of my head. That said, I seem to recollect me of the academic papers offering pseudo code for a stored procedure, and this is easier to implement than the path I chose myself (using triggers). – Denis de Bernardy Oct 08 '13 at 13:26