I solved the same problem a couple years ago with Cascade. It's uses Perl and Postgres (MySQL is supported in some versions) and is available under the GPL.

Ovid's solution is the most intuitive one for handling the "tree" structure of the categories, but it won't provide the best performance as some others methods (as he hints at). It also makes some SQL queries hard. I solved this by adding a "sort_key" in addition to the parent_id, which gives you your exact location in the tree, allowing you answer almost all questions about relationships in the tree in one query. You can peek in my data model and code to see how that works.

But don't go solving the problem again, just use Cascade. :) The demo site is updated to use the 2.1.0 BETA version at the moment, which isn't quite released, but adds several new features. -mark