Hacker News Reader

Comment by chernevik | Hacker News Reader

I am but an egg, I have two questions.

One, if the data were held in a database, should a change like this be captured in the database logs? I am seeing more and more situations where I want these, I notice that they are by default turned off for mysql and wonder if this reflects a de facto judgment that logging slows performance more than is usually worthwhile.

Two, if the data were kept in a database, wouldn't something like this be prevented by a constraint preventing a comment from making itself an ancestor? But I suppose there is a slight performance hit in checking such constraints, and the case arises so rarely that this hit isn't generally worthwhile.

View on HN

> I notice that they are by default turned off for mysql and wonder if this reflects a de facto judgment that logging slows performance more than is usually worthwhile.

I think it's more like your application is doing the logging already(probably; most of the frameworks do). If you really need it, turn it on yourself.

> Two, if the data were kept in a database, wouldn't something like this be prevented by a constraint preventing a comment from making itself an ancestor?

Copy pasting the table from another comment.

    create table post (id int primary_key, parent_id int references post(id), child_id int references post(id), created_at timestamp)

There isn't a simple check constraint you can place to ensure a parent's, or a grand-parent's, or a grand-grand-parent's parent_id isn't child.id You will have to write a trigger.

This isn't really a big problem to solve. pg simply overlooked this problem. Had he not, he would have checked child.created_at > parent.created_at in his mutator method. So, when you do a post.parent = some_post(assuming mutator is parent=; replace it with post.setParent or (send post set-parent some-post) or whatever), it checks if post.created_at > some_post.created_at, and then assigns post.parent_id = some_post.id

Databases, at least the SQL kind, really aren't good at dealing with hierarchical data, and I don't know how you'd even begin to express that kind of constraint. I don't think a traditional database is the answer here. (If it were me, once I'd done it more than twice I'd write a "move thread" admin tool in the UI, and after I screwed it up like this I'd have a place to add such a check to).

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.

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).

I think if you want the family tree, you can write a self referential(assuming post table is self referential as it should be) recursive query.

But in this case, writing a before insert/update trigger which ensure some_post.created_at < parent.created_at before setting parent.parent_id = some_post will do the trick.

Reply on news.ycombinator.com