Two arrays, two nested foreach and one site map

Frozen_Kiwi

First, an explanation: I can easily make this darn sitemap using nested WHILE and MySQL queries, but I'm trying to lessen the load on a poor database. So I'm building two arrays: one contains all categories, the other - all subcategories:

$query = mysql_query("SELECT categ_name, categ_id FROM main_categ ...");
$main_categories = array();
while ($row = mysql_fetch_array($query)) {
    $main_categories[$row['categ_id']] = array('categ_id'   => $row['categ_id'], 'categ_name' => $row['categ_name'] );                                                           

}

$query = mysql_query("SELECT categ_name, categ_id, subcateg_id FROM sub_categ ...");
$sub_categories = array();
while ($row = mysql_fetch_array($query)) {
    $sub_categories[$row['subcateg_id']] = array('categ_id'    => $row['categ_id'],  'subcateg_id' => $row['subcateg_id'],  'categ_name'  => $row['categ_name'] );
}

So far so good and I get a couple of cute associative arrays:

$main_categories = Array (
    [chirp] => Array (
            [categ_id] => chirp
            [categ_name] => Birds
        )

[meow] => Array (
        [categ_id] => meow
        [categ_name] => Cats
    )
...
)

$sub_categories = Array (
    [ln] => Array (
            [categ_id] => meow
            [subcateg_id] => ln
            [subcateg_name] => Lions            

        )
    [tgr] => Array (
            [categ_id] => meow
            [subcateg_id] => tgr
            [subcateg_name] => Tigers   

        )
...
)

Now I'm trying to loop through both arrays to build a site map and that's where I'm stuck. I can't for the life of me display only those subcategories that have the current category as parent. Sure thing the inner foreach should be altered and I was messing around with it - to no avail... 🙁

foreach ($mainmenus as $value) {
    echo '<a href="/' . $value['categ_name'] . '/">' . $value['categ_name'] . '</a><br />';

foreach ($submenus as $value2) {
   echo '<a href="/' . $value['categ_name'] .'/' . $value2['subcateg_name'] . '/">' .   $value2['subcateg_name] . '</a><br />';
}
}

I've got a feeling I'm walking in the dark. Either the arrays structures are incorrect or foreach is the improper construct here. Or maybe what I'm trying to do is not possible at all. In any case, shedding some light is highly appreciated. 🙂