Directory services searching system and methods

• US 20030208478A1
• Filed: 01/06/2003
• Published: 11/06/2003
• Est. Priority Date: 09/01/1994
• Status: Active Grant

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Harvey, Richard Hans
• Granted Patent: US 7,620,623 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 of a plurality of tables, comprising:

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

conducting a search of said database using said prescribed search area.

2. A method as claimed in claim 1, wherein said search is a base object search, and the scope of said search area is prescribed by the entry itself.

3. A method as claimed in claim 2, wherein each entry is identified by an entry ID (EID), further comprising:

navigating to the base object;

storing the EID; and

in a table, reading data on the basis of a match with the stored EID.

4. A method as claimed in claim 3, further comprising applying filter criteria.

5. A method as claimed in claim 1, wherein said search is a one level search, and the scope of said search area is prescribed by a parent.

6. A method as claimed in claim 5, wherein each entry is identified by an EID, further comprising:

navigating to the base object;

storing the EID;

returning a list of EID'"'"'s which have a parent EID matching the stored EID in a first table; and

in a second table, reading data on the basis of said returned EID.

7. A method as claimed in claim 6, further comprising applying filter criteria.

8. A method as claimed in claim 6, wherein said first table is a HIERARCHY table and said second table is an OBJECT table.

9. A method as claimed in claim 1, wherein said search is a whole subtree search, and the scope of said search area is prescribed by a path prefix.

10. A method as claimed in claim 9, wherein each entry is identified by an EID, further comprising:

navigating to the base object;

storing the EID;

returning a list of EID'"'"'s which have a path like that of a base object in a first table; and

in a second table, reading data on the basis of said returned EID.

11. A method as claimed in claim 10, further comprising applying filter criteria.

12. A method as claimed in claim 10, wherein said first table is a HIERARCHY table and said second table is an OBJECT table.

13. A method as claimed in claim 1, wherein said search is a whole subtree search defined by a path, wherein the path is broken into a number of ‘

level’

columns, and the scope of said search is prescribed by a selected level.

102. A computer program product, including a storage medium for storing a computer program, the computer program being executable to perform a method as claimed in any one of claims 1-51 and 93.

103. A method as claimed in any one of claims 1-51 wherein said directory service is a X.500 or LDAP service.

105. A method as claimed in any one of claims 1-51 and 93 wherein said database supports the structured query language (SQL).

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

prescribing a scope of search area for said database,

applying a filter over the search area, and

conducting a search of said database using said prescribed search area and said filter.

15. A method of searching a directory service database as set forth in claim 14, wherein said step of prescribing a scope and said step of applying a filter are performed simultaneously.

16. A method as claimed in claim 14, wherein the filter is a combination of one or more filter items connected by operators AND, OR or NOT.

17. A method as claimed in claim 14, wherein a table comprises at least one of path, parent or LEV columns, and said filter is applied using said path, parent or LEV columns.

18. A method as claimed in claim 15, wherein a table comprises at least one of path, parent or LEV columns, and said filter is applied using said path, parent or LEV columns.

19. A method as claimed in claim 16, wherein a table comprises at least one of path, parent or LEV columns, and said filter is applied using said path, parent or LEV columns.

20. A method as claimed in claim 14, wherein the filter is applied to a search area which includes only a base object.

21. A method as claimed in claim 15, wherein the filter is applied to a search area which includes only a base object.

22. A method as claimed in claim 16, wherein the filter is applied to a search area which includes only a base object.

27. A method as claimed in claim 19, wherein said table comprises a path or a parent column, said method further comprising, applying a filter using said path or parent column.

28. A method as claimed in claim 20, wherein said table comprises a path or a parent column, said method further comprising, applying a filter using said path or parent column.

29. A method as claimed in claim 21, wherein said table comprises a path or a parent column, said method further comprising, applying a filter using said path or parent column.

30. A method as claimed in claim 22, wherein said table comprises a path or a parent column, said method further comprising, applying a filter using said path or parent column.

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

identifying a unique set of areas of a tree; and

searching said areas.

24. A method as claimed in claim 23, wherein predetermined areas are defined by alias pointers, comprising

caching alias pointers;

and

searching on the basis of said alias pointers.

25. A method as claimed in claim 23, further comprising, applying a filter to each area of said tree.

26. A method as claimed in claim 24, further comprising, applying a filter to each area of said tree.

31. A method of performing a directory service search comprising:

navigating an incoming distinguished name to its appropriate entry ID (EID), and

thereafter performing the search.

32. A method of searching a directory service database, having a plurality of entries arranged in at least one of a plurality of tables with a plurality of columns, comprising:

navigating entries in at least one table;

identifying the presence of an alias during navigation; and

caching a location to which the alias points.

33. A method as claimed in claim 32, wherein one of said columns is an alias entry ID (A_EID) column and caching is preformed in an A_EID column.

35. A method as claimed in claim 33 further comprising:

determining whether a path is broken into a number of ‘

level’

columns,

and if so, setting the scope at a selected level; and

conducting a search of a directory service.

37. A method as claimed in claim 35 further comprising:

detecting the presence of an alias, and

if an alias is detected, simultaneously applying an arbitrary filter to a path column over a second subtree.

34. A method of enabling single pass resolution in any one of a search, filter or subtree search of a directory service, said directory service comprising at least one table having a plurality of columns, including a path column, the method comprising the step of:

using the path column to simultaneously apply an arbitrary filter over a first arbitrary subtree.

36. A method as claimed in claim 34 further comprising:

detecting the presence of an alias, and

if an alias is detected, simultaneously applying an arbitrary filter to a path column over a second subtree.

38. A method of enhancing the application of a filter to a search service of a directory service, the method including the steps of:

storing the “

path”

of each entry as a string in a manner that results in each path being prefixed by the path of its parent entry.

39. A method of searching a directory service database having aliases within a subtree area to be searched, comprising:

defining a FLAG column for use 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.

40. A method as claimed in claim 39, wherein, if an alias points inside the subtree, the alias does not need to be followed.

41. A method of retrieving data from directory service database, the method including the step of:

conducting search,

collecting all entries that need to be retrieved,

retrieving entries in parallel.

42. 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 a list of base objects, which define unique subtrees;

conducting a search of a subtree in said database and,

if an alias if found that points outside the subtree being processed, adding the aliased object to said list of base objects.

43. A method as claimed in claim 42, wherein, said adding step is not conducted if one or more of the base objects is subordinate to that aliased object, and

in such case replacing said subordinate base object with the aliased object.

44. 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, the method including the steps of:

a. establishing a list of base objects starting with a first base object;

b. 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 the second base object to the list, and

repeating step b. until alias(es) within the first subtree have been resolved.

45. A method as claimed in claim 44, further comprising:

as further alias(es) are located, adding further base object(s) to the list.

48. A method of searching a directory service database having a plurality of subtrees, each represented by a unique base object, the method including executing a search over an area determined in accordance with claim 44.

49. A method of searching a directory service database having a plurality of subtrees, each represented by a unique base object, the method including executing a search over an area determined in accordance with claim 45.

46. A method of determining a search area in a database having at least one subtree, the method comprising:

determining a set of non-overlapping subtree(s) in which all aliases, if any, point to an object inside the set.

47. A method as claimed in claim 46, wherein the set includes subtree(s) which are not subordinate to another subtree.

50. A method of searching a directory service database having a plurality of subtrees, each represented by a unique base object, the method including executing a search over an area determined in accordance with claim 46.

51. A method of searching a directory service database having a plurality of subtrees, each represented by a unique base object, the method including executing a search over an area determined in accordance with claim 47.

52. An argument for conducting a directory search service comprising:

a baseObject identifying where to start the search (baseObject),

a subset, identifying the scope of the search,

a filter, identifying the conditions to apply, and

a selection, identifying what information should be returned, as herein disclosed.

53. An argument for conducting a directory service as claimed in claim 52 wherein said directory service is a X.500 or LDAP service, as herein disclosed.

54. The argument as set forth in claim 52, further comprising a flag to indicate whether aliases should be dereferenced, as herein disclosed.

55. The argument as set forth in claim 52, wherein subset comprises one of a first value, a second value and a third value, wherein said first value indicates that a search filter will only be applied to attributes and values within the base object, said second value indicates a search filter will be applied to the immediate subordinates of the base object and said third value indicates a search filter will be applied to the base object and all of its subordinates, as herein disclosed.

56. A system comprising a processor executing a method and a memory for storing a directory service database, having a plurality of entries arranged in at least one table, comprising:

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

means for conducting a search of said database using said prescribed search area.

57. A system as claimed in claim 56, wherein said search is a base object search, and the scope of said search area is prescribed by the entry itself.

58. A system as claimed in claim 57, wherein each entry is identified by an ENTRY ID (EID), further comprising:

means for navigating to the base object;

means for storing the EID; and

means for reading data, from a table, on the basis of a match with the stored EID.

59. A system as claimed in claim 58, further comprising a filter for application of filter criteria to said table.

60. A system as claimed in claim 56, wherein said search is a one level search, and the scope of said search area is prescribed by a parent.

61. A system as claimed in claim 60, wherein each entry is identified by an EID, further comprising:

means for navigating to the base object;

means for storing the EID;

means for returning a list of EID'"'"'s which have a parent EID matching the stored EID in a first table; and

means for reading data in a second table, on the basis of said returned EID.

62. A system as claimed in claim 61, further comprising a filter for application of filter criteria to said table.

63. A system as claimed in claim 61, wherein said first table is a HIERARCHY table and said second table is an OBJECT table.

64. A system as claimed in claim 56, wherein said search is a whole sub tree search, and the scope of said search area is prescribed by a path prefix.

65. A system as claimed in claim 64, wherein each entry is identified by an EID, further comprising:

means for navigating to the base object;

means for storing the EID;

means for returning a list of EID'"'"'s which have a path like that of a base object in a first table; and

means for reading data in a second table, on the basis of said returned EID.

66. A system as claimed in claim 65, further comprising applying filter criteria.

67. A system as claimed in claim 65, wherein said first table is a HIERARCHY table and said second table is an OBJECT table.

68. A system as claimed in claim 56, wherein said search is a whole sub tree search defined by a path, wherein the path is broken into a number of ‘

level’

columns, and the scope of said search is prescribed by a selected level.

69. A system comprising a processor executing a method and a memory for storing a directory service database, having a plurality of entries arranged in at least one table, comprising:

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

means for applying a filter over the search area, and

means for conducting a search of said database using said prescribed search area and said filter.

70. A system for searching a directory service database as set forth in claim 69, wherein said means for prescribing a scope and said means for applying a filter are operative simultaneously.

71. A system as claimed in claim 69, wherein the filter is a combination of one or more filter items connected by operators AND, OR or NOT.

72. A system as claimed in claim 69, wherein a table comprises at least one of path, parent or LEV columns, and said filter is applied using said path, parent or LEV columns.

73. A system as claimed in claim 70, wherein a table comprises at least one of path, parent or LEV columns, and said filter is applied using said path, parent or LEV columns.

74. A system as claimed in claim 71, wherein a table comprises at least one of path, parent or LEV columns, and said filter is applied using said path, parent or LEV columns.

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

identifying a unique set of areas of a tree; and

searching said areas.

76. A system as claimed in claim 75, wherein predetermined areas are defined by alias pointers, comprising

means for caching alias pointers;

and

means for searching on the basis of said alias pointers.

77. A system as claimed in claim 75, further comprising, means for applying a filter to each area of said tree.

78. A system as claimed in claim 76, further comprising, means for applying a filter to each area of said tree.

79. A system as claimed in claim 75, wherein said table comprises a path or a parent column, said system further comprising, a filter for applying a filter criteria using said path or parent column.

80. A system as claimed in claim 76, wherein said table comprises a path or a parent column, said system further comprising, a filter for applying a filter criteria using said path or parent column.

81. A system as claimed in claim 77, wherein said table comprises a path or a parent column, said system further comprising, a filter for applying a filter criteria using said path or parent column.

82. A system as claimed in claim 78, wherein said table comprises a path or a parent column, said system further comprising, a filter for applying a filter criteria using said path or parent column.

83. A system for performing a directory service search comprising:

means for navigating an incoming distinguished name to its appropriate entry ID (EID), and

means thereafter for performing the search.

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

means for caching where an alias points during navigation.

85. A system as claimed in claim 84, wherein caching is preformed in an alias entry ID (A_EID) column.

86. A system for searching a directory service database comprising a plurality of entries arranged in at least one of a plurality of tables having a plurality of columns including a path column, comprising:

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

87. A system as claimed in claim 86 further comprising:

means for determining whether a path is broken into a number of ‘

level’

columns,

means responsive a determination that a path is broken into a number of “

level”

columns for setting the scope at a selected level; and

means for conducting a search of a directory service.

88. A system as claimed in claim 86 further comprising:

means for detecting the presence of an alias, and

means, if an alias is detected, for simultaneously applying an arbitrary filter to a path column over a second subtree.

89. A system as claimed in claim 87 further comprising:

means for detecting the presence of an alias, and

means, if an alias is detected, for simultaneously applying an arbitrary filter to a path column over a second subtree.

90. A system of enhancing the application of a filter to a search service of a directory service, the system comprising:

means for storing the path of each entry as a string in a manner that results in each path being prefixed by the path of its parent entry.

91. A system for searching a directory service database having aliases within a subtree area to be searched, comprising:

means for defining a FLAG column for use 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.

92. A system as claimed in claim 91, wherein, if an alias points inside the subtree, the alias does not need to be followed.

93. A method for retrieving data from a directory service database, the method comprising the step of:

conducting a search;

collecting all entries that need to be retrieved; and

retrieving entries in parallel.

94. In a system for searching 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, a means for determining a search area in said database, said means for determining comprising:

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.

95. A system as claimed in claim 94 wherein the means for determining further completes:

means for adding further base object(s) to the list if further alias(es) are located.

96. A system as claimed in claim 94 further comprising:

means for executing a search over an area determined by the means for determining.

97. A system as claimed in claim 95 further comprising:

means for executing a search over an area determined by the means for determining.

98. A system as claimed in claim 96, wherein the set includes subtree(s) which are not subordinate to another subtree.

99. A system as claimed in claim 98 further comprising:

means for executing a search over an area determined by the means for determining.

100. In a system for searching 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, a means for determining a search area in said database, said means for determining comprising:

means for determining a set of non-overlapping subtree(s) in which all aliases, if any, point to an object inside the set.

101. A system as claimed in claim 100 further comprising:

means for executing a search over an area determined by the means for determining.

104. A system for performing a directory service as claimed in any one of claims 56-92 and 94-101 wherein said directory service is a X.500 or LDAP service.

106. A system as claimed in claims 52-92 and 94-101 wherein said database supports the structured query language (SQL).

107. The invention as herein disclosed.