You include 2 files in a single "run". Think of it like this: All the included files are put together by PHP to create one big script. Every include or require fetches a file, and pastes its content in that one big script.
The two files you are including, both require the same file, which declares the Database class. This means that the big script that PHP generates looks like this:
class Message
{}
class Database
{}//required by message.php
class User
{}
class Database
{}//required by user.php
As you can see class Database is declared twice, hence the error.
For now, a quick fix can be replacing the require('database.php'); statements with:
require_once 'database.php';
Which checks if that particular file hasn't been included/required before. If it has been included/required before, PHP won't require it again.
A more definitive and, IMHO, better solution would be to register an autoloader function/class method, and let that code take care of business.
More on how to register an autoloader can be found in the docs. If you go down this route, you'd probably want to take a look at the coding standards concerning class names and namespaces here. If you conform to those standards, you don't have to write your own autoloader, and can simply use the universal class loader from Symfony2, or any other framework that subscribes to the PHP-FIG standards (like CodeIgnitor, Zend, Cake... you name it)
database.php, is it? - Álvaro González