Sometimes you just need to update the menu information in batch using SQL. use the following to find where this information is held.

Menu by itself is a taxonomy in WP. It means that you can find all menus in wp_terms table, by running following query:

SELECT * 
  FROM wp_terms AS t
  LEFT JOIN wp_term_taxonomy AS tt ON tt.term_id = t.term_id
 WHERE tt.taxonomy = 'nav_menu';

Menu item is custom post type in WP. They are stored in wp_posts table. You can find all of them by using this query:

SELECT * 
  FROM wp_posts 
 WHERE post_type = 'nav_menu_item';

Relations between menus and menu items are stored in wp_term_relationships table. To find all items of specific menu you can use this query:

SELECT p.* 
  FROM wp_posts AS p 
  LEFT JOIN wp_term_relationships AS tr ON tr.object_id = p.ID
  LEFT JOIN wp_term_taxonomy AS tt ON tt.term_taxonomy_id = tr.term_taxonomy_id
 WHERE p.post_type = 'nav_menu_item'
   AND tt.term_id = /*your menu ID*/;