Where would I find Custom menu attributes in the database?

Nav menu items are posts of the type nav_menu_item. They are combined to a nav menu by an assigned term from the taxonomy nav_menu. Each nav menu is a collection of posts under a term.

The function wp_get_nav_menu_items() is probably the best start to explore this.

1. The tables {$prefix}_terms and {$prefix}_term_taxonomy are queried for the current nav menu.
2. {$prefix}_term_relationships and {$prefix}_term_taxonomy are queried to find the posts assigned to that menu (term).
3. {$prefix}_posts is queried to get the posts.
4. {$prefix}_postmeta is queried to get the post meta data.

So the data for a nav menu are spread over four tables.

To see all the queries, add the following to your wp-config.php:

define( 'WP_DEBUG',         TRUE );
define( 'SAVEQUERIES',      TRUE );

The install and activate the plugin Debug Bar, go to a page with a menu and open the debug menu. There is a tab Queries with all the queries WordPress has done for that page.