4 ms·

Care to elaborate on your last sentence? I'm really curious about some corners of software history and this seems like a hint of a corner I never knew existed..

• jacques_chester 14y ago
  Basically, hierarchical and network databases were around before relational databases. Both of them have the problem that they require a lot of up-front planning. When you build a hierarchy, you need to know how it's going to be used as that will determine the structure. Turning hierarchies into networks -- ie trees into graphs -- eases this a bit but you still have the problem of arranging things for easy navigation to nodes. Say you build a project management system. Under a hierarchical system you might build it around the central concept of a Work Breakdown Structure. There are standard ways to produce these and they have a strictly hierarchical structure. But here comes trouble, because now you've privileged the WBS over all other views into the model. So if for instance you're interested in an activity-based breakdown (percentage $ spent on documentation vs manufacturing etc), you're going to have to walk the entire WBS to work it out. Lucky you. If you've ever queried an XML document in a way it wasn't originally set up for, this will seem familiar. When relational databases introduced joins, lots of heads exploded. Pretty much anything that can be logically derived from relations can be expressed with joins, projections etc, without having to modify the database structure to accomodate those queries. Now you can create a schema that relates WBS items to activities to cost accounts to whatever else. Now you can query them in any direction you like. Relational algebra means that the database can provably answer questions without having to waste time walking through a graph or visiting, potentially, ever node. The historical systems to look for are IMS (the original hierarchical system) and CODASYL (a standard for network database programming).
  • ams6110 14y ago
    Though interestingly, for quite a while the one thing hierarchical database were good at was the one thing RDBMS was bad at: reconstructing an arbitrary-depth hierarchy. Take the classic "bill of materials"... easy in a hierarchical database, but in an RDBMS you have to recursively query to walk the hierarchy, or use special support like Oracle's "CONNECT BY PRIOR"
    • mercurial 14y ago
      Alternatively, you can use nested sets [1], optionally storing the hierarchy in a different table. Unless you're really interested in good write performance. 1: http://en.wikipedia.org/wiki/Nested_set_model http://en.wikipedia.org/wiki/Nested_set_model
    • andrewflnr 14y ago
      I actually read a paper a while back describing how to do trees in an RDBMS by encoding the parent hierarchy of a row in a string primary key or something like that. To get everything in a subtree, just check for keys with a certain prefix. I can't seem to find it now, though. EDIT: should have gone to HNSearch first. Here's the comment where I found it: https://news.ycombinator.com/item?id=4921541 https://news.ycombinator.com/item?id=4921541 . Specifically, http://www.tetilab.com/roberto/pgsql/postgres-trees.pdf http://www.tetilab.com/roberto/pgsql/postgres-trees.pdf EDIT 2: tetilab link seems broken. Try this: http://darwin.zoology.gla.ac.uk/~rpage/MyToL/www/downloads/trees.pdf http://darwin.zoology.gla.ac.uk/~rpage/MyToL/www/downloads/t...
  • nnq 14y ago
    Kudos for the history lesson. I can't believe IBM still has a market for IMS (!?!), with all the nice ways of combining SQL and "NoSQL" nowadays... Are they hypnotizing their clients or what?