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

• US 7,191,170 B2
• Filed: 05/30/2003
• Issued: 03/13/2007
• 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: Ganguly, Sukanta, Kuo, ChinMing
• Primary Examiner(s): Alam; Shahid
• Application Number:
  US10/448,499
• Publication Number:
  US 20030212863A1
• Time in Patent Office: 1,383 Days
• Field of Search: 707/2, 707/3, 707/7, 707/10, 707/103.R, 709/201, 709/203, 709/213, 709/217, 709/239, 713/20, 714/38
• US Class Current: 707/741
• 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 establishing a cache for access to information stored in a directory, comprising:

locating the information in the directory by use of a predicate reduced to a normal form,

wherein the normal form includes primitive predicates and logic connectors which are associated with the predicate, and

wherein unique numbers for each logical connector and for each primitive predicate associated with predicate are represented in the normal form;

sorting the unique numbers within the cache;

using the primitive predicates as an index to the information in the cache, and wherein the index is dependent on search queries previously satisfied from the directory; and

maintaining and storing the index to the information in the cache.

2. The method of claim 1 wherein in locating, the logical connectors are Boolean operators.

3. The method of claim 1 further comprising receiving a subsequent request having the predicate reduced to normal form and identifying the unique numbers, which are used to gain access to the index and return the information associated with the predicate.

4. The method of claim 1 wherein in using, the cache includes memory and disk storage locations.

5. A method of creating an index in a cache, comprising:

acquiring information that is associated with a query, wherein the query is a compound predicate reduced to normal forms;

associating unique number identifiers for components of each of the normal forms,

wherein each component represents a primitive associated with the query or represents a logical operation associated with the query;

organizing the unique identifiers as the index to the information within the cache, and

wherein the index is dependent on the query and any other previous query used to formulate the index; and

managing and storing the cache index within the cache.

6. The method of claim 5 further comprising using the index to determine if at least a portion of a subsequent query can be satisfied by a portion of the information within the cache.

7. The method of claim 5 further comprising intercepting subsequent queries for a database to determine if the subsequent queries exist at least in part within the index and the cache.

8. A cache, comprising:

information placed in the cache by a proxy server,

wherein the information is acquired by the proxy server using a predicate,

the predicate including terms and logical connectors each term and each logical connector is mapped to its own unique number;

a cache index indexed and sorted by the unique numbers and each entry in the cache index providing a reference to a location having the information, and

wherein the cache index is dependent on the predicate, which is associated with a query and dependent on other previous predicates associated with other previous queries; and

managing and storing the cache index within the cache.

9. The cache of claim 8, wherein the proxy server intercepts a subsequent predicate and uses the subsequent terms and subsequent logical connectors to acquire the unique numbers and to access the cache index in order to locate the information.

10. The cache of claim 8, wherein the proxy server intercepts a subsequent predicate and determines that a match with the unique numbers does not exist and submits the subsequent predicate to a database to acquire subsequent information that is also stored in the cache.

11. The cache of claim 8, wherein the information is organized within the cache based on the cache index.

12. The cache of claim 8, wherein the predicate represents a search query for the information.

13. The cache of claim 12, wherein a subsequent query associated with a subsequent predicate is identified by the proxy server, and wherein at least a portion of the information satisfies the subsequent query.

14. The cache of claim 13, wherein the proxy server issues a partial query to a database to acquire remaining information that is combined with the portion of the information in order to satisfy the subsequent query.

15. The cache of claim 8 wherein the terms and logical connectors are in first order disjunctive normal forms.