MySQL Workbench – Why It Creates Multiple Foreign Keys for Many-to-Many Relations

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.

Lets start with your first link. It says clearly:

Working on large databases with referential integrity just does not perform well.

And that is right. Just you likely have no clue that "large database" is terabyte size with billions of rows in a table. A simple select may cascade into hundreds of millions of related elements to be deleted, and then you have a performance problem.

This is a non-issue for regular small databases such as a wordpress log or most CMS - it turns into a problem if you do something like facebook, or handle financial simulation data. I regularly deal with multi billion row tables and deletes that work in stored procedures outside of transactions in batches of x - because the end delete may easily clean up some hundred million rows.

Will they benefit going away from MySQL to a NoSQL kind of server?

Hardly. They are useful when a professional uses them as appropriate.

On other hand, can applications coded in a way to make use of foreign keys feature without running into issues?

Yes.

Is noSQL/redis better if we are using database only for storage and managing "relations" at application/script layer?

I once did a application review for a technology upgrade in a bank that uses no referential integrity (to get the performance up). Loading the data into SQL Server (which was supposed to replace their aging Adabas installation) it failed with integrity constraint violations. Happens 40% of the historical records were invalid because some * had deleted lookup table values not in use any more (such as old customer classification codes, which got replaced for all active customers, just not the old ones). No referential integrity warning ever came up. The result was some fired people and a problem stuck in workaround and a partially useless data warehouse build on top.

So much for managing relations at application / script layer. Errors WILL happen. Data is valuable, applications change.

Most people complaining about SQL level features would be more advised to read a book about them, and try to understand them, instead of complaining. Sadly a lot of the advice on the internet is written by people that refuse to read even documentation. Always be careful with that. Most advice to NoSql is based strongly on ignorance.