Няма грешка в избора на база данни дори след като е избран db

Забравихте да предадете променливата $link като параметър на връзката.

     mysql_select_db('database', $link) or die(mysql_error());

РЕДАКТИРАНЕ: Опитайте да предадете базата данни в параметъра FROM като

     SELECT * FROM `database`.`table`