Graph-structured databases and Php
There's some work going on to make the Neo4j graph database available from PHP, see this wiki page for more information! Regarding how to model your domain as a graph, the user mailing list tends to be pretty awesome.
Update: there's now a short getting started blog post for a PHP neo4j REST client.
Sounds to me a little bit like a "typical" Prolog problem... which is a quite different programming language than PHP. But perhaps you could work with popen.
Or you define an SQL table with columns [ id, predicate, atom1, atom2 ], to store the truthness of "Mary has Green Eyes": predicate = "has", atom1 = "Mary", atom2 = "Green Eyes".
Now you could join and filter the predicates and attributes with the SQL of your choice.
It looks like a semantic web problem. So you have to figure out how you can use PHP and the semantic web together. Maybe this link http://bnode.org/blog/2009/05/25/back-from-new-york-semantic-web-for-php-developers-trip can help?