Why HN was down

Re:Why HN was down by mr_luc on Monday February 18, 2013 @03:23PM (#5240393)

If you were using some kind of representation for Nested Sets -- left-to-right depth-first numbering, or a human-readable id.id.id chain -- then it's really easy to write a constraint for that: parent left < myleft, right > myright, or dotted_id.split('.').filter{|first, rest| return false if rest.contains first} (yeah, yeah, that second pseudocode would be unrealistically PITA for some DBs).

More generally:

I'm not a big SQL wonk anymore, but I find a lot of people have the intuition that relational databases are ill-suited for trees.

An intuition that is much closer to the truth is that almost all databases can handle trees pretty well, because there's still an unambiguous concept of ordering and containment, and you can usually arrange things so as to do range/ancestor/inclusion queries efficiently.

It's graphs with loops/without unambiguous concept of ordering/containment that are really hard.

[ Parent | on HN ]

Re:Why HN was down by EEGuy on Monday February 18, 2013 @04:17PM (#5240708)

Found this: The excellent Postgres documentation includes an SQL graph search with two different ways of graph cycle checking, here: http://www.postgresql.org/docs/9.0/static/queries-with.html

One way involves accumulating an array of nodes already visited as the tree gets walked, checking each node as-visited for membership in the array-to-date.

The other method, a bit more of a hack, is just adding a LIMIT clause.

I think the 'WITH' clause is a great addition to the SQL standard, very much worth the learning the weirdness of its syntax and its optional 'RECURSIVE' term (which, as the Postgres documentation points out, isn't really recursion, it's iteration).

[ Parent | on HN ]