4 ms·
The kind of assertion he needed though, could only be ensured by the database, not application code (my impression).
by swah 14y ago
The kind of assertion he needed though, could only be ensured by the database, not application code (my impression).
- luser001 14y agoAgreed, 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.
- badgar 14y ago> 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.
- mpweiher 14y agoI 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/research.html http://www.cs.cmu.edu/~pane/thesis/ http://www.cs.cmu.edu/~pane/thesis/ Pretty cool work regardless, I really like the way it deals with aggregates, for example.
- swah 14y agoThis is similar to the "while with timeout" that is common in embedded code (of course, watchdogs are better...)
- irahul 14y agoThe 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.
- swah 14y agoI 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...)
- irahul 14y agoThat 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).
- zzzeek 14y agoyou 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).
- swah 14y agoPlease note that the "Closure Table solution involves storing all paths through the tree, not just those with a direct parent-child relationship."
- irahul 14y agoMy bad. I was speed reading, and didn't read the "Closure Table" part.