Hacker News Reader

Comment by swah | Hacker News Reader

The kind of assertion he needed though, could only be ensured by the database, not application code (my impression).

Agreed, infinite loops are a little hard to protect using asserts.

When I hit the first infinite loop bug on a code path, I frequently add code to assert that the number of calls is less than $A_LARGE_NUMBER to catch future occurrences of the same root cause.

I dimly remember a language that just hard-limited loops. I thought it was John Pane's HANDS system, but I can't seem to find a reference in the thesis...can anybody refresh my memory?

http://www.cs.cmu.edu/~pane/research.html

http://www.cs.cmu.edu/~pane/thesis/

Pretty cool work regardless, I really like the way it deals with aggregates, for example.

This is similar to the "while with timeout" that is common in embedded code (of course, watchdogs are better...)

> Agreed, infinite loops are a little hard to protect using asserts.

    assert(is_tree(comment_graph))

Typically, a composite entity (like an "item" on HN which has many "comments") will define invariants to ensure data integrity. In this case, the invariant is that an "item"'s comments form a tree.

The database layer often contains this logic, but it depends on how you're building your application; NoSQL backends for example typically must put validation in the application layer. Since HN just uses files, a well-developed application layer should be riddled with invariants like this.

The kind of assertion he needed could not be ensured by the database. The kind of assertion he needed was there are no cycles in the graph. How would you ensure that in a database?

Also, HN uses flat files, not database.

A constraint on the parent-child link table "Child creation time stamp > Parent creation timestamp" would do it.

Might not be a bad idea, if the site were to have the two requirements "maintenance must be done on the live site from a repl" and "5 nines availability".

How are you modelling your data? I think this should be a self reference.

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

How will you place the check constraint? You only have parent_id and child_id, not parent and child entities. You will have to write a trigger.

I am not saying this can't or shouldn't be done. I am saying a db won't directly solve it.

However, you example will work perfectly for enforcing constraints in the code via the mutator which can compare child and parent timestamps, provided pg was doing it via a mutator, and not directly changing the ids.

Following http://stackoverflow.com/questions/3438066/check-constraint-..., and assuming that ID's get doled out in increasing order:

    create table post (
      id int primary_key,
      parent_id int references post(id),
      CONSTRAINT foo CHECK (id > parent_id)
    );

I was thinking something like (supposing the comments were stored as "closure tables" like Karwin suggests):

  CREATE TABLE comment_tree (
   ascestor_id REFERENCES comments(id) NOT NULL,
   descendant_id REFERENCES comments(id) NOT NULL,
   CHECK ( ascestor_id <> descendant_id )
  )

but I'm probably overlooking something. (I'm aware that HN uses flat files, I was just making a counter-point to the "simple assert" solution...)

That will prevent a child being its own parent. It won't work for more than one level i.e a post being its own grandchild. Assume (post_id, parent_id) sequence: (1, 3) -> (2, 1) -> (3, 2).

you can assert that "post_id > parent_id", assuming comments are always created subsequent to the creation of their parents (as is the case here) and that integer identifiers are always increasing (otherwise use timestamps). (1, 3) above would indicate an invalid case (not necessarily a cycle, but a precondition for one).

Please note that the "Closure Table solution involves storing all paths through the tree, not just those with a direct parent-child relationship."

My bad. I was speed reading, and didn't read the "Closure Table" part.

Reply on news.ycombinator.com