MySQL many to many relation

It looks like you've used the option to create an Identifying relationship (this is the one with the unbroken line in the toolbox).

An Identifying relationship assumes that the primary key in the referenced table should be part of primary key of the referencing table.

Because Company_id is now part of Department's Primary Key, it must also be part of the foreign key of Employee, hence your problem #1.

What you're probably wanting to do is create a Non-identifying relationship. This can be done by either selecting the dashed line from the toolbox, or unticking "Identifying relationship" in the Foreign Key tab of the Relationship properties.

A Non-identifying relationship is a classic foreign key constraint, and simply ensures that any value in the referencing table exists in the referenced table.

Technically this should resolve your problems, but there are still potential issues with the underlying database design.

For example, there's nothing to stop multiple companies existing with the same name, or multiple departments with the same name, even within the same company.

This could be solved by adding unique key constraints, but another way to tackle the same problem would be to use the Company and Department names as primary keys.

If you were doing this, you'd actually want to use an Identifying relationship, so that the Company name becomes an integral part of the Department.

(You may wish to read up on database theory and database normalisation, as it will help you avoid a lot of traps that you're likely to come up against when building a database)

I'm not suggesting that this is a better database design, simply that this is one where an Identifying relationship is valid / useful.

The Shipping Address is a property of each and every order, not of the customer. Even if it was a property of the Customer, it would be necessary to know where past orders were shipped to if a customer relocated.

Therefore all that can be stored as a Customer property are the Default Shipping Address (and Default Billing Address), for pre-populating each order and invoice as they are created. This is not a denormalization, because it directly reflects and captures the required business rules.

Now that the historical accounting records are taken care of, there should be a CustomerLocation table with FK's to three Address records in an Address table: Physical Address; Default Billing Address; and Default Shipping Address. The first of these records should be associated with an EffectiveDate, so that again a historical record exists as changes occur.