Method of hierarchical LDAP searching with relational tables

• US 6,085,188 A
• Filed: 03/30/1998
• Issued: 07/04/2000
• Est. Priority Date: 03/30/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bachmann, David W., Shi, Shaw-Ben, Fichtner, Larry George, Mancisidor, Rodolfo Augusto, Corn, Cynthia Fleming
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US09/050,503
• Time in Patent Office: 827 Days
• Field of Search: 707/1-3, 707/100, 707/101, 707/200, 707/205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method of hierarchical LDAP searching in an LDAP directory service having a relational database management system (DBMS) as a backing store. According to the invention, entries in a naming hierarchy are mapped into first and second relational tables: a parent table, and a descendant table. These tables are used to "filter" lists of entries returned from a search to ensure that only entries within a given search scope are retained for evaluation. Thus, for example, the parent table is used during an LDAP one level search, and the descendant table is used during an LDAP subtree search. In either case, use of the parent or descendant table obviates recursive queries through the naming directory.

Claims

1. A method of searching a directory organized as a naming hierarchy having a plurality of entries each represented by a unique identifier, comprising the steps of:

generating a relational table associating unique identifier pairs in the naming hierarchy having a given hierarchical relationship;

in response to a search query having a given filter criteria and search scope, returning a list of entries that satisfy the given filter criteria; and

using the relational table to filter out entries in the list according to the given search scope.

2. The method as described in claim 1 wherein the relational table summarizes parent-child relationships in the naming hierarchy.

3. The method as described in claim 2 wherein the relational table is generated by:

for each entry that is a parent of a child entry in the naming hierarchy, associating the unique identifier of the parent entry with the unique identifier of each entry that is a child of that parent entry; and

indexing each respective parent entry unique identifier together with "its respective" child entries unique identifiers in an ordered list.

4. The method as described in claim 3 wherein the search query is a one level search.

5. The method as described in claim 1 wherein the relational table summarizes ancestor-descendant relationships between the unique identifier pairs.

6. The method as described in claim 5 wherein the relational table is generated by:

for each entry that is an ancestor of one or more descendent entries in the hierarchy, associating the unique identifier of the ancestor entry with the unique identifier of each entry that is a descendent of that ancestor entry; and

indexing the ancestor entries'"'"' unique identifiers together with their associated descendent entry unique identifiers in an ordered list.

7. The method as described in claim 6 wherein the search query is a subtree search.

8. The method as described in claim 1 wherein the directory is a client/server directory service having a backing store.

9. The method as described in claim 8 wherein the backing store includes a relational database management system.

10. A method of searching a directory organized as a naming hierarchy having a plurality of entries each represented by a unique identifier, comprising the steps of:

generating first and second relational tables associating unique identifier pairs in the naming hierarchy having first and second given relationships;

in response to a search query having a given filter criteria and search scope, returning a list of entries that satisfy the given filter criteria; and

using at least one of the first and second relational tables to filter out entries in the list according to the given search scope to avoid recursive queries through the list of entries.

11. The method as described in claim 10 wherein the first relational table summarizes parent-child relationships in the naming hierarchy.

12. The method as described in claim 11 wherein the first relational table is generated by:

for each entry that is a parent of a child entry in the naming hierarchy, associating the unique identifier of the parent entry with the unique identifier of each entry that is a child of that parent entry; and

indexing each respective parent entry unique identifier together with its respective child entries unique identifiers in an ordered list.

13. The method as described in claim 12 wherein the search query is a one level search.

14. The method as described in claim 10 wherein the second relational table summarizes ancestor-descendant relationships in the naming hierarchy.

15. The method as described in claim 14 wherein the second relational table is generated by:

for each entry that is an ancestor of one or more descendent entries in the hierarchy, associating the unique identifier of the ancestor entry with the unique identifier of each entry that is a descendent of that ancestor entry; and

indexing the ancestor entries'"'"' unique identifiers together with their associated descendent entry unique identifiers in an ordered list.

16. The method as described in claim 15 wherein the search query is a subtree search.

17. The method as described in claim 10 wherein the directory is a client/server directory service having a backing store.

18. The method as described in claim 17 wherein the backing store includes a relational database management system.

19. A computer program product in a computer-readable media for use in a computer to search a directory organized as a naming hierarchy having a plurality of entries each represented by a unique identifier, the computer program product comprising:

means for generating first and second relational tables associating unique identifier pairs in the naming hierarchy having first and second given relationships;

means responsive to a search query having a given filter criteria and search scope for returning a list of entries that satisfy the given filter criteria; and

means for using at least one of the first and second relational tables to filter out entries in the list according to the given search scope to avoid recursive queries through the list of entries.

20. The computer program product as described in claim 19 wherein the first relational table is a parent table generated by associating the unique identifier of each parent entry with the unique identifier of each entry that is a child of that parent entry.

21. The computer program product as described in claim 19 wherein the second relational table is a descendant table generated by associating the unique identifier of each ancestor entry with the unique identifier of each entry that is a descendant of that ancestor entry.

22. A directory service system, comprising:

a directory organized as a naming hierarchy having a plurality of entries each represented by a unique identifier;

a relational database management system having a backing store for storing directory data;

means for searching the directory, comprising;

means for generating first and second relational tables associating unique identifier pairs in the naming hierarchy having first and second given relationships;

means responsive to a search query having a given filter criteria and search scope for returning a list of entries that satisfy the given filter criteria; and

means for using at least one of the first and second relational tables to filter out entries in the list according to the given search scope to avoid recursive queries through the list of entries.

23. The directory service system as described in claim 22 wherein the first relational table is a parent table generated by associating the unique identifier of each parent entry with the unique identifier of each entry that is a child of that parent entry.

24. The directory service system as described in claim 22 wherein the second relational table is a descendant table generated by associating the unique identifier of each ancestor entry with the unique identifier of each entry that is a descendant of that ancestor entry.

25. The method as described in claim 22 wherein the directory is a client/server directory service.

26. The directory service system as described in claim 22 wherein the relational database management system is DB/2.

27. In a directory service having a directory organized as a naming hierarchy, the hierarchy including a plurality of entries each represented by a unique identifier, the improvement comprising:

a relational database management system having a backing store for storing directory data;

means for searching the directory, comprising;

means for generating first and second relational tables associating unique identifier pairs in the naming hierarchy having first and second given relationships;

means responsive to a search query having a given filter criteria and search scope for returning a list of entries that satisfy the given filter criteria; and

means for using at least one of the first and second relational tables to filter out entries in the list according to the given search scope to avoid recursive queries through the list of entries.