How about:

SELECT a.category_id, a.category
  FROM test a, test b
 WHERE b.main_category = a.category_id
[download]

From there you can make the individual menu split based on the category_id.

Warning: This is untested and may require some tweaking to make work in the exact way you require.