[sdeming]

Actually, you don't really need the other table as Technobard noted in his response. It's a design decision as to whether or not you'll ever want multiple heirarchies and categories with multiple parents. The design principles that say you should keep the heirarchy definition separate are based on normalization rules and keeping your data guidance separate from your data.

The primary key should be on both fields together, cat_id and parent_id so you can have duplicates of each but not a duplicate of the same combination.

Now on to your code troubles. The easiest way to resolve your problems is to use recursion. Create a function that traverses a single categories children then calls itself on each child. By nature while it's processing a the child it'll be calling itself again for each of the childs child infinitely until it reaches the end. This is common for traversing any tree.

I'd be interested in seeing your code when you do this! I've not even considered doing any of this in PHP yet.