6

I have a table in a relational database, in which I encode a tree using the technique known as Materialized path (also known as Lineage column). That is, for each node in my tree I have a row in the table, and for each row I have a string column named ancestry where I store the path from the root node to the node represented by this row.

Is it possible, and if yes - how, to select the rows in the table orderd by preorder, that is they should appear in the result set in the order that would result by visiting the tree depth-first. I use MySQL - so no recursive queries and no ltree extension.

For example, a tree, it's table, and selected ordered by preorder:

 1        SELECT * FROM nodes   SELECT * FROM nodes ORDER BY ?depth_first_visit_order?
| \       id | ancestry         id | ancestry
2   3     -------------         -------------
|  | \    1  | NULL             1  | NULL           NOTE: I don't care about the
4  5  6   2  | 1                2  | 1                    order of siblings!
   |      3  | 1                4  | 1/2
   7      4  | 1/2              3  | 1
          5  | 1/3              5  | 1/3
          6  | 1/3              7  | 1/3/5
          7  | 1/3/5            6  | 1/3

Note: I am interested explicitly in doing this over a materialized path encoding!
Related: What are the options for storing hierarchical data in a relational database?

Community
  • 1
  • 1
clyfe
  • 23,695
  • 8
  • 85
  • 109
  • Similar http://stackoverflow.com/questions/2797720/sorting-tree-with-a-materialized-path – clyfe Feb 01 '12 at 15:56

2 Answers2

1

I believe what you want is an alphabetic sort.

SELECT id, ancestry, ancestry + '/' + CAST(id as nvarchar(10)) AS PathEnumeration
FROM nodes
ORDER BY 3 ASC;

I don't really remember how MySQL concatenates, but I'm sure my meaning is clear.

1
1/2
1/2/4
1/3
1/3/5
1/3/5/7
1/3/6

Note that it is an alphabetic sort, so 11 will show up before 2. But, you said you didn't care about sibling ordering. I, of course, would rewrite it as a nested set ;)

Toto
  • 89,455
  • 62
  • 89
  • 125
Ion Freeman
  • 512
  • 4
  • 19
  • 1
    I will probably rewrite it as a nested set since I have many short trees. Thing is my data already is "materialized path" encoded naturally (domain names to be precise a.b.c). I'll have to ponder on this for a while because I'm not quite sure it works yet, in the general case. – clyfe Feb 14 '12 at 10:35
0

this will order by the last number of your "ancestry"

select *, 
Substring(ancestry,LEN(ancestry) - Charindex('/',Reverse(ancestry))+2, LEN(ancestry)) as END_CHAR
from nodes
order by END_CHAR desc

I didn't try with numbers bigger that 9, you may have to cast to int

Diego
  • 34,802
  • 21
  • 91
  • 134
  • Sorry, just realized this doesn’t answer your question, I misunderstood it. Ill leave the query, it may give you some idea. – Diego Feb 01 '12 at 16:43