Primeiro, crie um backup de {database}:
mysqldump -u {user} -p {database} > /home/$USER/Documents/backup.sql
Para remover qualquer vestígio de mariadb instalado através do apt-get:
sudo service mysql stop
sudo apt-get --purge remove "mysql*"
sudo rm -rf /etc/mysql/
e tudo se foi. Incluindo bancos de dados e qualquer arquivo de configuração.
Para verificar se algo chamado mysql desapareceu, faça um
sudo updatedb
e um
locate mysql
Deve estar bastante vazio (talvez algumas páginas de manual ou um conector). Se você ver um my.cnf entre os resultados, remova-o também.