Data processing system and method for multi-level directory searches

• US 6,625,615 B2
• Filed: 12/19/2000
• Issued: 09/23/2003
• Est. Priority Date: 12/19/2000
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Hill, Reginal R., Shi, Shepherd
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/740,251
• Publication Number:
  US 20020078032A1
• Time in Patent Office: 1,008 Days
• Field of Search: 707/103.R, 707/100, 707/102, 707/10, 707/3, 707/201, 707/9, 707/2, 701/202, 701/201, 702/2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24566 Recursive queries
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/45 Network directories; Name-to-address mapping
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

An apparatus and method for performing a multi-level directory search are implemented. The directory information may be stored in a backing store in accordance with a relational database. An ancestor table is generated which maps each node in the directory which is an ancestor of one or more descendant nodes to each of its ancestor nodes. Each node is associated with a unique identifier, which may be used to relate ancestor and descendant nodes. The table includes the identifier of each ancestor in association with all the corresponding descendants. Additionally, the table maps the distance between the ancestor and each descendant. For a search initiated at a given node the distance values may be used to delimit a search in accordance with a specified search scope. The search scope may be specified as a parameter in a Lightweight Directory Access Protocol (LDAP) search request.

Claims

1. A search method comprising the steps of:

retrieving one or more second node identifiers, and an associated distance value in response to a first node identifier; and

for each node corresponding to one of said one or more second identifiers having a corresponding one of said associated distance value not greater than a preselected distance value, matching said node to a first parameter, wherein the first node identifier comprises a directory node distinguished name search parameter, and the associated distance value comprises a number of levels between the directory node having the first node identifier and a directory node having the second node identifier.

2. The method of claim 1 further comprising the step of returning a value of each of one or more selected members of each node having a match in response to said matching step.

3. The method of claim 1 wherein said one or more second node identifiers and said associated distance value are retrieved from a table, said table including an entry corresponding to each said second node identifier, each entry having a first portion for containing said second node identifier and a second portion for containing said associated distance.

4. The method of claim 3 further comprising the step of generating said table.

5. The method of claim 3 wherein each entry of said table includes a third portion for containing an identifier of an ancestor node of a node corresponding to the second node identifier contained in the second portion.

6. The method of claim 5 wherein said second node identifier is retrieved in response to said identifier of said ancestor node corresponding to said first node identifier.

7. The method of claim 1 wherein said preselected distance value is determined in response to a second parameter.

8. The method of claim 7 wherein said first, and second parameters each comprise Lightweight Directory Access Protocol (LDAP) search parameters.

9. The method of claim 1 further comprising the step of mapping a value of a second parameter to said first node identifier, wherein said second parameter comprises a search parameter.

10. A computer program product embodied in a tangible storage medium, the program product comprising a program of instructions for performing the method steps of:

retrieving one or more second node identifiers, and an associated distance value in response to a first node identifier; and

for each node corresponding to one of said one or more second identifiers having a corresponding one of said associated distance value not greater that a preselected distance value, matching said node to a second parameter, wherein the first node identifier comprises a directory node distinguished name search parameter, and the associated distance value comprises a number of levels between the directory node having the first node identifier and a directory node having the second node identifier.

11. The program product of claim 10 further comprising instructions for performing the step of returning a value of each of one or more selected members of each node having a match in response to said matching step.

12. The program product of claim 10 wherein said one or more second node identifiers and said associated distance value are retrieved from a table, said table including an entry corresponding to each said second node identifier, each entry having a first portion for containing said second node identifier and a second portion for containing said associated distance.

13. The program product of claim 12 further comprising instructions for performing the step of generating said table.

14. The program product of claim 12 wherein each entry of said table includes a third portion for containing an identifier of an ancestor node of a node corresponding to the second node identifier contained in the second portion.

15. The program product of claim 14 wherein said second node identifier is retrieved in response to said identifier of said ancestor node corresponding to said first node identifier.

16. The program product of claim 10 wherein said preselected distance value is determined in response to a second parameter.

17. The program product of claim 16 wherein said first and second parameters each comprise Lightweight Directory Access Protocol (LDAP) search parameters.

18. The program product of claim 10 further comprising instructions for performing the step of mapping a value of a second parameter to said first node identifier, wherein said second parameter comprises a search parameter.

19. A data processing system comprising:

circuitry operable for retrieving one or more second node identifiers, and an associated distance value in response to a first node identifier; and

circuitry operable for, for each node corresponding to one of said one or more second identifiers having coresponding one of said associated distance value not greater that a preselected distance value, matching said node to a first parameter, wherein the first node identifier comprises a directory node distinguished name search parameter, and the associated distance value comprises a number of levels between the directory node having the first node identifier and a directory node having the second node identifier.

20. The system of claim 19 further comprising circuitry operable for returning a value of each of one or more selected members of each node having a match in response to said matching step.

21. The system of claim 20 wherein said one or more second node identifiers and said associated distance value are retrieved from a table, said table including an entry corresponding to each said second node identifier, each entry having a first portion for containing said second node identifier and a second portion for containing said associated distance.

22. The system of claim 21 further comprising circuitry operable for generating said table.

23. The system of claim 21 wherein each entry of said table includes a third portion for containing an identifier of an ancestor node of a node corresponding to the second node identifier contained in the second portion.

24. The system of claim 23 wherein said second node identifier is retrieved in response to said identifier of said ancestor node corresponding to said first node identifier.

25. The system of claim 19 wherein said preselected distance value is determined in response to a second parameter.

26. The system of claim 25 wherein said first and second parameters each comprise Lightweight Directory Access Protocol (LDAP) search parameters.

27. The system of claim 19 further comprising circuitry operable for mapping a value of a second parameter to said first node identifier, wherein said second parameter comprises a search parameter.