Help on Custom Post Types

You want Posts 2 Posts which allows you to create many to many (or one to many or many to one) relationships between post objects — including custom post types.

To related stores and deals you might do something like this…

<?php
add_action('p2p_init', 'wpse102461_connection');
function wpse102461_connection()
{
    p2p_register_connection_type(array(
        'name' => 'stores_to_deals',
        'from' => 'STORES', // or whatever your custom post type actual is
        'to'   => 'DEALS', // or whatever your deals type is
    ));
}

This will create the admin interface (which you can customize) for you and provide a way to fetch associated deals.

Or you could overload post_parent to do what you need.