Predicate indexing for locating objects in a distributed directory

• US 6,345,266 B1
• Filed: 09/20/1999
• Issued: 02/05/2002
• 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: Yang, Cheng, Ganguly, Sukanta, Kuo, Chin Ming
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/398,685
• Time in Patent Office: 869 Days
• Field of Search: 707/3-4, 707/1, 707/2, 707/5, 707/10, 707/100, 707/3.4, 707/103.R, 707/104.1, 707/501.1, 709/203-207, 709/226, 709/229, 713/201, 714/4, 714/38
• US Class Current: N/A
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

The invention relates to a distributed directory service that is constructed based on a predicate, i.e., a query from a client. The predicate is formed by the query (request) issued by the client. The predicate is used as an index for retrieving data from a plurality of directory servers. Retrieving the data has the following steps. Each directory server is designated by a designation predicate giving a range of data values stored in the directory server. A client predicate indicates desired information. The client predicate is compared with the designation predicates to determine which directory servers may contain information requested by the client predicate. In the event that a particular designation predicate indicates that a portion of the desired information may be stored on a particular directory server, an inquiry is sent to the particular directory server for the desired information. The retrieved information is transferred to the client computer. 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 logical connectors and the predicates are sorted in numerical order of the numerical representation to form the normal form of the predicate. The directory may be chosen to be a database.

Claims

1. A method of indexing information stored in a distributed 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;

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

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;

comparing said normal form of said client predicate with index predicates to stored information stored in a directory; 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.

7. Electromagnetic signals travelling on a computer network comprising:

said electromagnetic signals to operate the process of claim 1.

4. A method for retrieving data from a plurality of directory servers, comprising:

designating each directory server, of said plurality of directory servers, by a designation predicate giving a range of data values stored in said each directory server;

using a client predicate to indicate desired information;

comparing said client predicate with at least one of said designation predicates to determine which directory servers may contain information requested by said client predicate, and in the event that a match between said client predicate and a particular designation predicate indicates that at least a portion of said desired information may be stored on a particular directory server pointed to by said particular designation predicate, sending an inquiry to said particular directory server for said desired information;

retrieving desired information from said particular database server in the event that said client predicate designates information stored on said particular database server, as retrieved information; and

,

storing said retrieved information in a memory of a client computer.

8. Electromagnetic signals travelling on a computer network comprising:

said electromagnetic signals to operate the process of claim 4.

5. A method of indexing information stored in a distributed 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;

storing said information into a particular directory of said distributed directory, and using said normal form of said predicate as an index to said information, and using a directory index based on a normal form of a predicate to designate said particular directory.

9. Electromagnetic signals travelling on a computer network comprising:

said electromagnetic signals to operate the process of claim 5.

6. A distributed directory comprising:

a plurality of directory units, each said directory unit designated by a designation predicate, said designation predicate giving a range of information stored on its particular directory unit;

a memory to hold a client predicate, said client predicate seeking information which may be stored in said distributed directory, said client predicate submitted to said distributed directory by a client;

a processor to compare said client predicate with at least one of said designation predicates in order to find a directory unit which may have information requested by said client predicate stored therein;

a search engine to search any of said directory units which are indicated by their designation predicates as directory units which may have said information requested by said client predicate stored therein, and said search engine producing discovered information as output where said discovered information is information requested by said client predicate and which was found on a particular directory unit by said search engine;

an output unit to transfer any discovered information to said client.

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

a predicate sorted into normal form, said predicate designating a range of values stored in a particular directory server of a distributed directory system, said distributed directory system having a plurality of said particular directory servers;

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.