To expand on RabidDog's idea using a recursive solution, I am in agreement with that.

The first solution I provided was just the SQL solution, which can be taken in a global applicative solution, depending on what he needs as an approach vertical/horizontal/both.

Horizontal:

SELECT c.ID_CATEGORY, c.NAME CATEGORY, ID_SUB_CATEGORY, c2.NAME_CATEGORY FROM CATEGORY c JOIN RELATION r ON (c.ID_CATEGORY=r.ID_CATEGORY) JOIN CATEGORY c2 ON(ID_SUB_CATEGORY=c2.ID_CATEGORY) ORDER BY c.ID_CATEGORY 

Vertical, something looking like that:

function single_genealogy($category, $level = 0)
{
	$q = "SELECT ID_SUB_CATERORY, NAME_CATEGORY FROM RELATION JOIN CATEGORY c USING(ID_CATEGORY) WHERE c.ID_CATEGORY=".$category;
	$r = mysql_query($q); //or die/mail/echo mysql_error()
	if(mysql_num_rows($r))
	{
		$level++;
		while($d = mysql_fetch_row($q))
		{
			//displaying current node : $d[1]...
			//recursive call :
			single_genealogy($d[0], $level);
		}
	}
}

for a given category, that'll show :

level(<=given one)
   level
      level
      level
   level
   level

Very importantly, a category mustn't be twice in a single genealogical tree otherwise it'll turn the recursive solution into a perpetual one! 🙂

You could make 2 tables:

CATEGORY and SUB_CATEGORY

The first table CATEGORY would hold the info about each category no matter what it is hierarchically.

The second table SUB_CATEGORY would hold (unique) couples of associations ID_CATEGORY to ID_SUB_CATEGORY.
A category could be in ID_CATEGORY, in all the rows showing her "daughters" and also in ID_SUB_CATEGORY in the rows showing her "mothers"

CATEGORY:

ID_CATEGORY
NAME_CATEGORY

RELATION

ID_CATEGORY
ID_SUB_CATERORY

ALL the categories have an entry in the first table. The second show all the subcategory for each ID_CATEGORY that has got at least one, in fact, if you want to register a subcategory you put in the id of the mother ID_CATEGORY and it's own id ID_SUB_CATEGORY, that'll list all the subcategories of one category :

SELECT ID_SUB_CATERORY, NAME_CATEGORY FROM RELATION JOIN CATEGORY c USING(ID_CATEGORY) WHERE c.ID_CATEGORY=CAT_WHAT_CATEGORY_ARE_SEARCHED

You can also check if a category is a subcategory:

SELECT c.ID_CATERORY, NAME_CATEGORY FROM RELATION JOIN CATEGORY c USING(ID_CATEGORY) WHERE ID_SUB_CATEGORY=CAT_WHAT_MOTHER_CATEGORY_ARE_SEARCHED

If you want unlimited levels you could look at using a recursive solution. This would allow for scenarios like:

Level
  level
  level
  level
   level
   level
  level
    level
      level
  level

Using one of the solutions provided here you would be limited to:

Level
  level
  level
level
  level
level

Recursive solutions can however become resource-intensive (unless designed properly).