The invention relates to a directory proxy caching system that is constructed based on a predicate, i.e., a query from a client. Broadly stated, the predicate is formed by the query (request) issued by the client. Once the data is found in the directory, then the data is stored in a cache of a proxy server. The data is indexed in the proxy server by the predicate. The predicate is used to form an index by sorting the predicate into a normal form. Steps in sorting the predicate into the normal form include the following. Each symbol of the predicate is represented by a numerical representation, for example the ASCII value used to represent the symbol in ordinary text files. The predicate is expressed as a plurality of primitive predicates, and individual predicates of the plurality of primitive predicates are joined by logical connectors. The logical connectors, and each term in the primitive predicates are represented by numbers. The logical connectors and the predicates are sorted in numerical order of the numbers to form the normal form of the predicate. The information retrieved by the predicate is stored into a cache using the normal form of the predicate as an index. The next request using a previously used predicate can then be found in the cache by the next request being sorted into normal form and used as an index into the cache.