Finding the minimum set of properties that describe a referent in a set of entities

Question

I was wondering if someone could help me get pointers to solve this problem. A link to algorithms would be great, but pointers to papers/info is also good.

The problem is as follows. Suppose I have a set E of entities E={car1, car2, bicycle} and a set of properties P ={red, blue, small}. I also have a knowledge base such that red(bicycle), blue(car1), blue(car2), small(car2). Suppose I also have a referent r which belongs to E.

The problem consists of finding the minimum set of properties P' \subseteq P such that it unequivocally picks out r from E. Thus, if r is car2, then P'={small}.

Any ideas? I guess something like the set covering problem or functional dependencies (as in DB theory) might provide some insight, but I thought I'd ask before going into that literature. Yet another possibility is building graphs and find algorithms for subgraph isomorphisms... maybe.

Thanks.

Answer 1

First find the set of all properties that r has. Call it S. For each property p in S, find e(p), all the entities that have the property p. It is clear for each p in S that e(p) contains r. Now take the intersections of e(p) for each p in S. If the intersection contains more than one entity, there is no solution, and we end the algorithm.

So we have a set S of properties that uniquely determine the entity r. Now we need to find a minimal subset of S that uniquely determines r. We can remove any property p from S for which there exists a property q in S so that e(p) is a superset of e(q). If you do that exhaustively you will eventually end up with a reduced set of properties T so that the intersection of e(p) for all the p in T will still be {r}, but no further property in T can be removed. This set T is then minimal.

I haven't thought of anything to make finding a property you can remove any more efficient than just trying all combinations, but it seems to me that there should be some way.