I'm sure bags cause some trouble, but I had something much "simpler" in mind. For instance, JOIN elimination is a powerful tool implemented by most modern RDBMS' optimisers.

Take this query:

    SELECT c.*
    FROM customer c
    JOIN address a
    ON c.address_id = a.address_id

With a foreign key on customer(address_id), the above JOIN can easily be proven useless, and thus eliminated. Furthermore, take this query:

    SELECT c.*
    FROM customer c
    LEFT JOIN address a
    ON c.address_id = a.address_id

In this case, we don't even need the foreign key as long as there is a unique constraint on address(address_id).