Predicate indexing of data stored in a computer with application to indexing cached data

• US 6,629,132 B1
• Filed: 09/20/1999
• Issued: 09/30/2003
• Est. Priority Date: 12/23/1998
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Kuo, Chin-Ming, Ganguly, Sukanta
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Duong, Oanh
• Application Number:
  US09/398,684
• Time in Patent Office: 1,471 Days
• Field of Search: 709/201, 709/203, 709/213-219, 707/3, 707/7, 707/10
• US Class Current: 709/213
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

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.

Claims

1. A method of locating information stored in a directory comprising:

using a predicate to designate said information, said predicate expressed as a plurality of primitive predicates, individual predicates of said plurality of primitive predicates joined by logical connectors;

representing said logical connectors by numbers, and representing terms in each predicate by numbers, said numbers chosen so that each different logical connector and each different term in said plurality of predicates is represented by a unique number;

sorting said logical connectors and said predicates in numerical order of said unique numbers representing said logical connectors and said terms to create a normal form of said predicate; and

storing said information into a cache and using said normal form of said predicate as an index to said information stored in said cache.

2. The method as in claim 1 further comprising:

submitting a client predicate by a client to designate desired information;

sorting said client predicate into a normal form of said client predicate; and

comparing said normal form of said client predicate with index predicates to stored information stored in a cache, and retrieving stored information when said normal form of said client predicate matches said index predicate.

3. The method as in claim 1 further comprising:

choosing said directory as a database.

4. A data structure stored in a computer memory, comprising:

a predicate sorted into normal form, said predicate serving as an index to data stored in a cache, said cache stored in a memory unit of said computer; and

said predicate having at least one logical operator and having a plurality of elements, said logical operator and said plurality of elements each represented by a number, and said normal form of said predicate formed by sorting said numbers representing said logical operators and said plurality of elements into numerical order.