Directory services searching system and methods

• US 7,620,623 B2
• Filed: 01/06/2003
• Issued: 11/17/2009
• Est. Priority Date: 09/01/1994
• Status: Expired due to Fees

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Harvey, Richard Hans
• Primary Examiner(s): Fleurantin; Jean B
• Application Number:
  US10/336,769
• Publication Number:
  US 20030208478A1
• Time in Patent Office: 2,507 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: H04L 61/4517 using open systems interconnection [OSI] directories, e.g. X.500
• CPC Class Codes: H04L 61/4523 using lightweight directory access protocol [LDAP]
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method and apparatus for applying an application of a database service, such as X.500 or LDAP, to a relational database, a database design and use of the database to perform such services. Specifically addressed is the problem of database searching, particularly search speed and complexity of search. The method and apparatus concern searching a directory service database, in which the scope of search area is initially prescribed and/or in which a filter is applied over the search area. Moreover, in dealing with an alias during a search, a unique set of areas is found which define areas of a search tree that need to be searched. A FLAG column is used to indicate if an alias points inside a subtree. The method and apparatus also enable single pass resolution in any one of a search, filter or subtree search of a directory service, the method and apparatus including the use of a path column to simultaneously apply an arbitrary filter over an arbitrary subtree. Further disclosed is a method and apparatus of retrieving data from a directory service database, which includes conducting search, collecting all entries that need to be retrieved, and retrieving entries in parallel.

Claims

1. A method of searching a directory service database, having a plurality of entries arranged in at least one property table, comprising:

initially prescribing, by one or more processors, the scope of a search area for said database, and

conducting, by the one or more processors, a search of said database using said prescribed search area comprising;

accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table decomposed from the at least one property table and comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier,

accessing, using the entry ID, at least one attribute value stored in an object table, the object table decomposed from the at least one property table, the at least one attribute value being accessible only from only from its entry ID, and

searching said database according to the at least one attribute value.

2. A method of searching a directory service database comprising a plurality of entries arranged in at least one entry table and having an alias therein, comprising:

identifying, by one or more processors, a unique set of areas of a tree of the database; and

searching, by the one or more processors, said areas of the tree of the database comprising the steps of;

accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier,

accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry, and

searching the database according to the at least one attribute value.

3. A method of searching a directory service database, having a plurality of entries arranged in at least one of a plurality of entry tables with a plurality of columns and having an alias therein, comprising:

navigating, by one or more processors, entries in at least one entry table comprising the steps of;

accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, and

accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry;

searching, by the one or more processors, the directory service database by;

identifying the presence of an alias during navigation; and

caching to a location to which the alias points.

4. A method of searching a directory service database comprising a plurality of entries arranged in at least one of a plurality of entry tables, comprising:

accessing, by one or more processors, a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry;

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, the hierarchy table further comprising;

one or more aliases within a subtree area to be searched;

accessing, by the one or more processors, using the EID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the entry; and

searching, by the one or more processors, said database by;

accessing a FLAG column to indicate if an alias points inside the subtree; and

conducting a search of said database and, on the basis of a detection of a FLAG, transferring said search to a path inside said subtree.

5. A method of retrieving data from a directory service database, comprising:

conducting, by one or more processors, a search of the database comprising the steps of;

accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, and

accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry; and

retrieving, by the one or more processors, data from the database by;

collecting all entries that satisfy a filter; and

retrieving all the entries in parallel.

6. A method of searching a directory service database having a plurality of subtrees, each represented by a unique base object, and having aliases within at least one subtree to be searched, comprising:

maintaining, by one or more processors, a list of base objects, which define unique subtrees;

conducting a search of a subtree in said database comprising the steps of;

accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, and

accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry; and

searching the database according to the at least one attribute value; and

if an alias is found that points to another entry that is not within the subtree being processed, adding, by the one or more processors, the aliased object to said list of base objects.

7. A method of determining a search area in a directory service database having at least one subtree including at least one alias, each subtree being represented as a unique base object, comprising:

a. accessing, by one or more processors, a hierarchy table describing a tree of a plurality of entries of the plurality of subtrees, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry;

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry; and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier;

b. accessing, by the one or more processors, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry;

c. establishing, by the one or more processors, a list of base objects starting with a first base object;

d. as an alias is located within the first subtree, which alias indicates a second base object of a second subtree outside the first subtree, adding, by the one or more processors, the second base object to the list;

e. repeating, by the one or more processors, steps a. through d. until all alias(es) within the first subtree have been resolved; and

f. searching, by the one or more processors, a search area of the database according to the first subtree.

8. A system, comprising:

a directory service database having a plurality of entries arranged in at least one entry table, the database stored in a memory, and

one or more processors comprising;

means for initially prescribing the scope of a search area for said database, and

means for conducting a search of said database comprising;

means for accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, and

means for accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry.

9. A system, comprising:

a directory service database having a plurality of entries arranged in at least one entry table, the database stored in a memory, and

one or more processors comprising;

means for prescribing a scope of a search area for said database,

means for applying both a filter and scope requirements simultaneously over the search area, and

means for conducting a search of said database comprising;

means for accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, and

means for accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry.

10. A system, comprising:

a directory service database comprising a plurality of entries arranged in at least one entry table and having an alias therein, the database stored in a memory; and

one or more processors comprising;

means for identifying a unique set of areas of a tree of the directory service database; and

means for searching said areas comprising;

means for accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, and

means for accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry.

11. A system, comprising:

a directory service database comprising a plurality of entry tables with a plurality of columns and having an alias therein, the database stored in a memory; and

one or more processors comprising;

means for accessing a hierarchy table describing a tree of a plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry;

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry; and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier;

means for accessing, using the EID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the entry;

means for navigating entries in at least one entry table;

means for identifying the presence of an alias during navigation; and

means for caching to a location to which an alias points.

12. A system, comprising:

a directory service database comprising a plurality of entries arranged in at least one of a plurality of entry tables, the database stored in a memory; and

one or more processors comprising;

means for accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry;

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry; and

an entry ID (ELD), the entry ID comprising an arbitrary numeric identifier;

means for accessing, using the EID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the entry; and

means for enabling single pass resolution in anyone of a search, filter or subtree search of the directory service, by using the path to simultaneously apply an arbitrary filter over a first arbitrary subtree.

13. A system, comprising:

a directory service database comprising a plurality of entries arranged in at least one of a plurality of entry tables, the database stored in a memory; and

one or more processors comprising;

means for accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry;

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, the hierarchy table further comprising;

one or more aliases within a subtree area to be searched;

means for accessing, using the EID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the entry;

means for accessing a FLAG column to indicate if an alias points inside the subtree; and

means for conducting a search of said database and, on the basis of a detection of a FLAG, transferring said search to a path inside said subtree.

14. A system for retrieving data from a directory service database, comprising:

a directory service database stored in a memory; and

one or more processors comprising;

means for accessing a hierarchy table describing a tree of the plurality of entries, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry, and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier, and

means for accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry;

means for collecting all entries that satisfy a filter; and

means for retrieving all the entries in parallel.

15. A system, comprising:

a directory service database having a plurality of subtrees, each represented as a unique base object, and having aliases within at least one subtree to be searched, the database stored in a memory; and

one or more processors comprising a means for determining a search area in said database, said means for determining comprising;

means for accessing a hierarchy table describing a tree of a plurality of entries of the plurality of subtrees, the hierarchy table comprising for each entry of the plurality of entries;

a parent of the each entry,

a path describing an absolute position of the each entry in the tree, the path associating one or more entities from a root of the tree to the each entry; and

an entry ID (EID), the entry ID comprising an arbitrary numeric identifier,

means for accessing, using the entry ID, at least one attribute value stored in an object table, the object table being void of a relative distinguished name associated with the each entry,

means for establishing a list of base objects starting with a first base object, as an alias is located within the first subtree, which alias indicates a second base object of a second subtree outside the first subtree, and

means for adding the second base object to the list, until alias(es) within the first subtree have been resolved.