Ubuntu 16.04 : can t apt due to mysql-server-5.7 issue

I managed to fix this without having to purge everything. It seems the problem is that the sys schema database was never created, so here's the solution:

• Clone https://github.com/mysql/mysql-sys and cd into the cloned folder.
• In a terminal, run mysql -u root -p < ./sys_57.sql (or sys_56.sql, depending on your version)
• Enjoy mysql_upgrade working again.

I guess this probably was, as @skerit said, an upgrading scripts mess-up.

Someone messed up the upgrade scripts, and in an LTS release no less.

The main problem lies in the upgrading of the system schema. If you don't want to delete all your data, you can force the update like this:

mysql_upgrade -uroot -p --verbose --skip-sys-schema

This is a dirty workaround, of course, since the system schema is now not what it's supposed to be, but at least you can continue using mysql.