6

I am trying to set up some sort of collaboration app/forum with unlimited threading; no difference between posts, threads, or forums. Any post can be answered an unlimited amount of time, and the same post can have several children, themselves having several children, and so on. Each post can also have several parents. The final result would look more like a mind-map than a forum, although usage as a regular forum would also be possible.

How I see people using it: say a team discusses the making of a project website. After a few threads, the conversation splits in parallel conversations about coding & design. Then after a while, the two end nodes get linked. The conversation continues for a while...A third, unrelated conversation about bauhaus-style websites gets linked too, for reference...etc.

I am trying right now to build a proof of concept, and I am at loss at what database design to choose.

As I understand it, there is two possible patterns: adjacency list model, and nested set model. And as I understand it, the nested set is usually preferred. I have built an app based the on nested set model, and I know why it is more useful, in most cases.

Something bothers me here though: since I intend to have a lot of users adding a lot of leafs on a lot of different nodes, and since the N.S.M. needs to move left or right a whole bunch of leaves each time a sibling is added, what would be my best database schema? I do not intend to release a fully optimized application yet, but I would still like to start on the right foot.

Here are a few of my thoughts, I would like opinions on them:

  • Leave a lot of space between nodes, so parents nodes would be numbered 0, 10000, 20000, etc. This is not an elegant solution, but might work
  • Go back to the adjacency list model, and use a node_node table to link nodes. Less efficient in tree retrieval, but more efficient in adding/deleting nodes
  • Ditch databases completely, and go back to file-based, with a mix of directories/xml to store data. I have never worked with filesystems to retrieve and search large amounts of data, I don't know how that would work out
  • Is there any DB schema more adapted to my case that you know of?

Thanks in advance

Improve this question
7
  • 1
    Which database engine(s) are you considering? Many relational databases have "common table expressions" (aka WITH) that make recursion (and thus tree building) easy as pie. This'd be a totally different solution than you'd see if you wanted to use a key/value store or a document database instead.
    – Charles
    May 11, 2011 at 23:32
  • @Charles you should put common table expression as answer instead of comment. Hierarchical data is a solved problem with common table expression.
    – Endy Tjahjono
    May 12, 2011 at 12:51
  • @Endy, unfortunately I don't have any experience working with CTEs and could not provide a working cross-implementation demonstration -- I merely know that they are available as a tool.
    – Charles
    May 12, 2011 at 15:55
  • @Charles sample of CTE in postgresql
    – Endy Tjahjono
    May 12, 2011 at 16:18
  • I don't exactly know which DB engine I am going to use. I would like my code to be as portable and open-source-ready as possible, so ideally I'd go with a DB wrapper such as PDO (in PHP), with mySQL as a standard on install. I don't think CTEs are available in all major databases, are they?
    – Xananax
    May 14, 2011 at 22:50

5 Answers 5

Reset to default
2

If you're willing to go for adjacency lists, then why doesn't a simple foreign key to the parent of each post do the trick for you?

At any rate, stay away from nested sets for situations with many insertions. Anything you do to try to keep it efficient will make things complex and lose any advantage that the elegant trick might have had.

And for God's sake, don't go file-based - you'll just end up reinventing the database yourself, poorly.

Improve this answer
1
  • I am indeed in a situation needing many insertions. But I am also in a situation where a node can have an unlimited amount of parents. So I would need a table to store relationships. I don't see anything particularly difficult or weird there; I am just wondering if there isn't anything better, specially to retrieve large amounts of relations, and be able to stop loading of nodes after a certain level of recursion.
    – Xananax
    May 14, 2011 at 23:04
4

I've been enjoying Materialized Path with django-treebeard. Basically it stores the complete path for every nesting level, so you can do a full select starting at a root and order by the path to retrieve the full hierarchy.

It's slower for inserts and moving nodes, but reading is much faster than recursion and CTEs. I wouldn't worry too much about performance here. Even if you are adding posts a lot, you're still going to be ahead of the game if the majority of the actions are reads (which in a forum's case, they are by far).

Treebeard also stores number of children and current depth in each record, but those aren't strictly necessary.

For example, this is how it's stored in the database

path         item

0001         Item 1 (root)
00010001     Item 1.1  
00010002     Item 1.2
00010003     Item 1.3
000100030001 Item 1.3.1
00010004     Item 1.4
Improve this answer
2
  • 1
    After over 6 years working with large, arbitrary hierarchies, I can say without hesitation that this is the ideal model as long as update activity isn't ridiculous. If the most common modification is single-row addition, you can denormalize the leaf path for better performance. SQL Server also has the hierarchyid type which scales better and is easier to code/script against than a hand-rolled MP.
    – Aaronaught
    May 12, 2011 at 15:57
  • This is very interesting. If anyone's still following, I found info on materialized paths (had never heard of them) and more here: communities.bmc.com/communities/docs/DOC-9902. However, I am really having trouble wrapping my head around this. It still seems the easiest way to go for now though
    – Xananax
    May 14, 2011 at 22:59
2

Why are we stuck on SQL-based, table-focused databases to solve a triangular problem? I would definitely go with something schema-less and document based here, especially for the proof of concept stage where you won't be doubling up every major change as you won't have a schema to modify.

Improve this answer
4
  • +1 I don't know if this is the right answer, but NoSQL certainly seems worth considering here.
    – James
    May 13, 2011 at 8:30
  • It is worth considering, but my main problem is, even at the stage of POC, I'd like to provide a working theory, even though the DB calls could be unoptimized. I'd rather have a good theoretical backbone with slow calls and iterate optimizations. And frankly I can't really see a file structure that would be actually efficient. If you have anything to propose I am open to all sorts of suggestions
    – Xananax
    May 14, 2011 at 23:01
  • What I'm talking about is actually pretty optimized and isn't any more a file-based structure than a SQL database. Check out RavenDb or CouchDb for a few examples.
    – Wyatt Barnett
    May 15, 2011 at 1:32
  • the read about couchDB was very interesting and I see what you mean. It is a viable solution (probably, I haven't looked into it extensively), but I would like my app to be portable and flexible, so I'd rather not be tied to a particular technology. I'll still read further before deciding
    – Xananax
    May 15, 2011 at 8:20
1

I was about to comment & upvote on a post that just got deleted, simply for: "don't do file based - you'll just end up reinventing the database yourself, poorly".

Spot on. I've worked in a company that did this, it wasn't pretty. You'll start out all nice and easy, it'll be great, you'll think DBs are rubbish and your amazing.

Then you'll have to add something simple that DBs do out of the box for you, and the next thing you know your writing 5 pages of Python code just to move a record from one location to the other. So glad I don't work there anymore.

Improve this answer
1
  • it was "Kilian Foth" who said this originally, seems to be back now, something odd happening somewhere ...
    – James
    May 13, 2011 at 8:44
0

Binary trees are awesome if you need a sorted list. You do not need a sorted list for this project. You have a parent-child relationship chain also known as a single linked list, that can be associated with one root node. This root node belongs to one category.

I would a use a Foreign-Key to the ParentId that builds a chain. I would also use a Foreign-Key to the Root-Node for quick retrevial of the entire thread.

If a child record gets deleted and it has it's own child record, that child record ParentId needs to point to the new parent record.

Improve this answer
1
  • It's not a single linked list...In fact, my bad, this is not clear in my original post. I am looking for a mixup of forum/mindmap, so any node can have an unlimited amount of siblings/parents/childs.
    – Xananax
    May 14, 2011 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.