US2002107828A1PendingUtilityA1

Directory services searching system and methods

30
Priority: Sep 1, 1994Filed: Oct 26, 1999Published: Aug 8, 2002
Est. expirySep 1, 2014(expired)· nominal 20-yr term from priority
Inventors:Richard Hans Harvey
Y10S707/99931Y10S707/99954H04L 61/4552G06F 16/289G06F 16/284Y10S707/99933H04L 61/4517H04L 61/4523G06F 16/288Y10S707/99934Y10S707/99942
30
PatentIndex Score
0
Cited by
0
References
0
Claims

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

exact text as granted — not AI-modified
We claim:  
     
         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.  
     
     
         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.  
     
     
         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.  
     
     
         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.  
     
     
         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.  
     
     
         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.    
     
     
         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.  
 
     
     
         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.  
 
     
     
         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.  
 
     
     
         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.    
     
     
         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.  
     
     
         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 .  
     
     
         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 comprises: 
 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.  
 
     
     
         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.  
     
     
         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.  
     
     
         105 . A method as claimed in any one of claims  1 - 51  and  93  wherein said database supports the structured query language (SQL).  
     
     
         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.

Join the waitlist — get patent alerts

Track US2002107828A1 — get alerts on status changes and closely related new filings.

We store only your email — no account needed. See our privacy policy.