If you ever need to downgrade from MySQL 5.x to MySQL 4.x (hope you don’t), chances are you are going to run into a problem with apt-get. You will most likely receive cryptic, unhelpful dpkg errors.

If this is the case, try the command below.

sudo aptitude purge mysql-common mysql-client mysql-server && sudo aptitude install mysql-server-4.1 mysql-client-4.1

This should purge whatever is left of the MySQL 5.x installation, and then install the MySQL 4.x version. If this fails, proceed to bang head against nearest hard object.

If MySQL won’t start due to corrupt InnoDB tables, you can add
[mysqld]
innodb_force_recovery = 4
to the /etc/my.cnf file, and restart MySQL. This will allow MySQL to start even with the corrupt InnoDB tables. I’m not quite sure if this fixes the tables or merely allows MySQL to run despite the warnings.

More Info