Now that I'm awake (somewhat) I'll try and write this :)
I'm aware of two algorithms basic for making a tree/graph in SQL. The first takes advantage of modular exponentation. I've seen varients using log and COMPLEX and whathaveyou- but this works on most SQL engines: http://web.archive.org/web/20030629195428/http://www.cs.dartmouth.edu/~apd/archives/000019.html The benefit to this algorithm is that it works pretty much everywhere, and only a useless SQL server would mess it up. It's also really fast. But it can't support "arbitrary" trees or graphs, I only bring it up because it's a useful thought-puzzle. http://www.dbazine.com/oracle/or-articles/tropashko4 This is a really great version. It's not depth-limited, but it requires some "special functions" - which are easy to make with sqlite, and not impossible to emulate with other engines- but they're really not that fast on those systems. Fortunately, we're not writing anything in SQL- we're writing it in C and that produces SQL queries. That makes this a piece of cake- simply implement those functions in C and insert the _results_. I really recommend this way although it cannot handle arbitrary graphs. http://article.gmane.org/gmane.comp.db.sqlite.general/3821/ This method _can_ handle arbitrary graphs, and it's fast. To implement, we'd need a mapping table (%_threads?) that would contain: message id, parent message id, xyz... where xyz is one column per threading style. Of course, inserting is never as simple as simply "finding the parent" because we know for a fact we'll find the wrong one and need to fix it up later. As a result, we need to search the following things quickly: * Order mailbox by thread * which messages are in the tree that contains this message The latter isn't too difficult with any algorithm except the first, but then I don't recommend you use that one anyway :) On Tue, 2005-08-16 at 17:06 +0200, Paul J Stevens wrote: > Geo, > > I'll take your word for it: only REFERENCES threading. > -- Internet Connection High Quality Web Hosting http://www.internetconnection.net/
