A database solution can be had without backtracking if it's designed properly. I think the right combination of references and indirection would do it. If the first table listed the object's name, a unique ID# of some sort, and bits to indicate if it was an object, operator, or both, the second table would simply be tuples of object, operator, object. Index all three columns separately on the second table, and any of the sample queries you describe should be straightforward.
in reply to Choosing a data structure for AI applications
To address the problem of 'real' objects only being in one place at a time, that's a programming issue: The object ID# in question has records that indicate it is real, and with Kudra. The definition for real things could specify that they can only be with one person at a time. The code would check before adding a new assertion that the book is with someone that it can be with more than one person at once.
The data structure isn't the hard part. Figuring out the tuples to put in the database is. I'm not sure what format OpenCYC is in, but it might be a good start, depending on what you want your AI to do.
Spring: Forces, Coiled Again!