potresti effettuare la query e ricostruirti tutto in un array

codice:
$menu = array();
$result = mysql_query("SELECT id, categoria, pid FROM tabella");
while(list($id, $categoria, $pid) = mysql_fetch_row($result)) {
     $menu[$pid][$id] = $categoria;
}
e poi gestirti l'array