;/1994 Japan ......................... .. G06F 17/30
`/1995 Japan ..
`.... .. G06F 17/30
`9605704 8/1994 WIPO ........................... .. G06F 17/30
`
`OTHER PUBLICATIONS
`IBM Technical Disclosure Bulletin, “Tree Traversal Tech
`niques to Implement Enhanced Searches in Tree View,” vol.
`38’ NO‘ 02’ Feb‘ 1995'
`_
`_
`IBM Technical Disclosure Bulletin, “Relational Access
`ligegtiiod Supporting Nested Data View, vol. 27, No. 6, Nov.
`
`Herrin, E.H. II et al., “Schema and tuple treess: an intuitive
`structure for representing relational data,” Computing Sys
`terns, v01. 9, No. 2,1111 92—118, Spring 1996
`Kitakami,
`et a1‘, “Building and Search System for a
`large_scale DNA database,” IEE Colloquium on ‘Molecular
`Bioinformatics’, Digest N0. 1994/029, pp. 6/1—6/9, 1994.
`
`[22]
`
`Filed:
`
`Mar. 30, 1998
`
`7
`Int. Cl. .................................................... .. G06F 17/30
`Cl- ............................................... ..
`[58] Field of Search ................................... .. 707/1—3, 100,
`707/101, 200, 205
`
`Ulllted States Patent [19]
`Bachmann et al.
`
`US006085188A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,085,188
`Jul. 4, 2000
`
`[54] METHOD OF HIERARCHICAL LDAP
`SEARCHING WITH RELATIONAL TABLES
`
`FOREIGN PATENT DOCUMENTS
`802491 4/1996 European Pat. Off. ...... .. G06F 17/30
`
`[75] Inventors: David W- Bachmann, Leander;
`.
`.
`.
`Cynthla Flemmg Corn’ Ausnn; Larry
`George Fichtner, Austin; Rodolfo
`Augusto Mancisidor, Austin;
`Shaw-Ben Shl’ Austm’ an of TeX'
`[73] AssigneeZ International Business Machines
`Corporation, Armonk, NY.
`
`[21] AppL NO‘: 09/050,503
`
`[51]
`
`[56]
`
`References Cited
`
`(List continued on next page.)
`
`US. PATENT DOCUMENTS
`7/1990 Bruffey et a1. ............................ .. 707/1
`3/1994 Bapat
`395/705
`
`Primary Examiner—Maria N. Von Buhr
`‘jugomey’ Agent’ Or Flrm_]effrey S‘ LaBaW; Davld H‘
`‘1 50“
`
`4,945,475
`5,291,583
`
`707/2 707/4
`
`
`
`
`3/1994 SlIIlOIlettl .... .. 1/1995 Heffernan et a1.
`
`5,295,261 5,379,419
`1/1995 Elsenberg et a1
`5,386,559
`707/201
`""" " 707/3
`4/1995 Gllberts‘?“ et a1‘
`574047518
`707/101
`9/1995 Annevelink
`5,448,727
`5,467,471 11/1995 Bader ...................... .. 707/1
`575047879
`4/1996 Eisenberg et a1‘
`7O7/1OO
`575117186
`4/1996 Carhart et a1_
`_____ __ 7070
`5,530,957
`6/1996 Koenig .................................. .. 707/100
`5,581,756 12/1996 Nakabayashi ............................. .. 707/2
`5,592,661
`1/1997 Eisenberg et al.
`707/104
`5,594,899
`1/1997 Knudsen et al- --
`----- -- 707/2
`5,600,832
`2/1997 Elsenberg et a1
`707/203
`576447740
`7/1997 Kluchl """"" "
`345/357
`5’675’784 10/1997 Maxwell et a1‘ "
`707/100
`5,708,806
`1/1998 DeRose et a1.
`.. 707/104
`5,724,577
`3/1998
`5,943,668
`8/1999
`
`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
`h.
`.
`t.
`t .
`.
`.
`h
`d. t ? t
`mven ion, en ries in a naming ierarc y are mappe in 0 rs
`and second relational tables: a parent table, and a'descendant
`table- These tables are used to “?lter” 115$ 0f enmes 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
`'
`
`27 Claims, 5 Drawing Sheets
`
`GET ANCESTOR
`PEIDs FROM
`ldup_desc TABLE
`
`COMPLETE?
`
`REMOVE PEID AND
`EID PAIR FROM
`ldop_desc TABLE
`
`REMOVE EID
`ENTRY FROM THE
`|dup_entry TABLE
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 1
`
`

`

`6,085,188
`Page 2
`
`OTHER PUBLICATIONS
`
`Waugh, T.C., et al., “The GEOVIEW design: a relational
`database approach to geographical data handling,” Proceed
`ings of the Second International Symposium on Spatial Data
`Handling, pp. 193—212, 1986.
`Severance, C., “Could LDAP be the neXt killer DAP?”
`Computer, vol. 30, No. 8, pp. 88—89, Aug. 1997.
`
`Gaf?n, A. et a1., “Intranets,” Network World, vol. 4, No. 12,
`pp. 26—28, 30, 32, Feb. 1997.
`Blum, D.J., “LDAP: helping directories get along,” Business
`Communications RevieW, vol. 26, No. 12, pp. 37—40, Dec.
`1996.
`Jose, R.J.P. et a1., “Providing multiple external vieWs on
`directory user interfaces,” Computer Networks and ISDN
`Systems, vol. 28, No. 4, pp. 543—550, Feb. 1996.
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 2
`
`

`

`U.S. Patent
`
`Jul. 4,2000
`
`Sheet 1 of5
`
`6,085,188
`
`FIG. 1
`(PRIOR ART)
`
`11
`
`DIRECTORY SERVER
`
`25\ LDAP RUNTIME
`
`CLIENT
`
`1O
`\
`
`25
`\
`LDAP RUNTIME
`
`NEIWORK
`:SSL
`
`21\
`
`DIRECTORY
`//
`
`"1'2
`
`DIRECTORY
`
`ROOT
`
`FIG. 2
`(PRIOR ART)
`
`RDN
`
`RDN
`RON
`
`29
`/
`ENTRY (ATTRIBuTEs)
`
`40\
`
`INITIALIZE
`LDAP sEssION
`I
`42\ OPEN CONNECTION
`I
`44\ AUTHENTICATION
`I
`OIREOTORY
`46\
`sERvER OPERATION
`‘
`
`48/ mm RESULTS
`I
`CLOSE sEssION
`
`50/
`
`FIG. 3
`(PRIOR ART)
`
`27
`
`34
`\
`
`O0
`
`wk
`
`<3
`38b
`—
`
`LDAP CLIENT
`
`3
`é
`38H
`LDAP sERvER L
`
`FIG. 4A
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 3
`
`

`

`U.S. Patent
`
`Jul. 4, 2000
`
`Sheet 2 0f 5
`
`6,085,188
`
`NETWORK
`DISPATCHER
`
`05/2 CLIENT +
`LDAP SERVER
`
`FIG- 4B
`
`LDAP CLIENTS
`
`NETWORK
`DISPATCHER
`
`05/2 SERVERS
`
`DB/2 CLIENT+
`LDAP SERVER
`
`FIG 4C
`
`LDAP CLIENTS
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 4
`
`

`

`U.S. Patent
`
`Jul. 4, 2000
`
`Sheet 3 0f 5
`
`6,085,188
`
`ROOT (1)
`
`41
`r/
`
`C=GB (2)
`
`c = us (3)
`
`o = IBM (4)
`
`0 = NETSCAPE (5)
`
`FIG. 5
`(PRIOR ART)
`
`0U = IBM AUSTIN (6)
`
`CN =JOHN FOO(8)CN = MARY BUR (9) CN = PEIER WANG (1o)
`
`ou = IBM ROCHESTER (7)
`
`/
`
`s\
`
`m
`
`% 1 1 1 1 1 1 1 11331033334444.4667
`
`5113344667 P
`
`D
`
`D
`
`H23456789w
`
`FIG. 6A
`
`FIG. 6B
`
`D
`
`B23456789m456789m670090890 D 1 1
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 5
`
`

`

`U.S. Patent
`
`Jul. 4, 2000
`
`Sheet 4 015
`
`6,085,188
`
`@112
`
`GET A UNIQUE 10 /64
`FOR THE ENTRY (ETD)
`
`ENTRY
`EXISTS?
`
`/70
`
`GET PARENT
`EID (PEID)
`1
`ADD AN ENTRY mm
`ldop_entry TABLE /72
`WITH ElD AND PE10
`
`1
`
`74
`GET ANCESTORS E103
`FROM 110M681; TABLE /
`
`5,
`
`76
`
`COMPLETE?
`
`MAP 0N To E10
`
`52
`
`54
`0E1 ANCESTOR
`PEIDS FROM /
`|dop__desc TABLE
`=
`"
`
`56
`
`COMPLETE?
`
`P
`
`T
`REMOYE PEID AND
`EID PAIR FROM
`|dop_desc TABLE
`|
`
`REMOVE EID
`ENTRY FROM THE \60
`ldop_entry TABLE
`
`@ ADD AN ENTRY 1NTo
`THE DESCENDANT TABLE \
`FIG. 7
`WITH E10 AND AE10
`78
`____I
`
`FIG. 8
`
`FIN‘TSH
`68
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 6
`
`

`

`U.S. Patent
`
`Jul. 4, 2000
`
`Sheet 5 0f 5
`
`6,085,188
`
`@80
`
`RETRIEVE ENTRY EIDs
`WHICH MATCH THE /82
`FILTER CRITERIA FROM
`THE ATTRIBUTE TABLES
`
`OUTPUT=
`EID SET SET 1
`IT
`MAP BASE
`ON TO ENTRY EID
`
`f84
`
`OUTPUT BASE DH EID=
`BASE EID
`
`T
`RETRIEVE THE
`DESCENDANTS EIDS /86
`FROM |dop_desc TABLE
`USING THE BASE EID
`
`OUTPUT=
`: EID SET SET 2
`TI
`88 END
`
`96
`/
`SEND BACK
`END OF SEARCH
`COMMAND
`
`IS IT
`
`IN SET 2? @ 98
`
`RETRIEVE ENTRY DATA
`FROM ldop_entry TABLE \92
`I
`SEND BACK
`THE RESULTS
`—_I
`FIG. 9
`
`\94
`
`@100
`
`RETRIEVE ENTRY EIDs
`WHICH MATCH THE fI02
`FILTER CRITERIA FROM
`THE ATTRIBUTE TABLES
`
`OUTPUT=
`EID SET SET 1
`
`TI
`MAP BASE
`DN TO ENTRY EID
`
`/IO4
`
`OUTPUT BASE DH EID=
`BASE EID
`IT
`RETRIEVE THE
`CHILDREN ElDs FROM /ID6
`ldop_entry TABLE
`USING THE BASE EID
`
`OUTPUT=
`V EID SET SET 2
`IT
`
`OF SET? 116
`/
`SEND BACK
`END OF SEARCH
`COMMAND
`
`IS IT
`
`IN SET 2'? @ 118
`
`RETRIEVE ENTRY DATA
`FROM |d0p_entry TABLE \112
`I
`SEND BACK
`\114
`THE RESULTS
`é
`FIG. 10
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 7
`
`

`

`1
`METHOD OF HIERARCHICAL LDAP
`SEARCHING WITH RELATIONAL TABLES
`
`6,085,188
`
`BACKGROUND OF THE INVENTION
`
`10
`
`20
`
`25
`
`30
`
`35
`
`15
`
`1. Technical Field
`This invention relates generally to providing directory
`services in a distributed computing environment.
`2. Description of the Related Art
`A directory service is the central point Where netWork
`services, security services and applications can inform other
`entities in the netWork about their services, thus forming an
`integrated distributed computing environment. The current
`use of directory services may be classi?ed into several
`categories. A “naming service” (e.g., DNS and DCE Cell
`Directory Service (CDS)) uses a directory as a source to
`locate an Internet host address or the location of a given
`server. A “user registry” (e.g., Novell NDS) stores informa
`tion of all users in a system composed of a number of
`interconnected machines. The central repository of user
`information enables a system administrator to administer the
`distributed system as a single system image. Still another
`directory service is a “yelloW pages” lookup provided by
`some e-mail clients (e.g., Netscape Communicator, Lotus
`Notes, Endora and the like).
`With more and more applications and system services
`demanding a central information repository, the neXt gen
`eration directory service Will need to provide system admin
`istrators With a data repository that can signi?cantly ease
`administrative burdens. In addition, the future directory
`service must also provide end users With a rich information
`data Warehouse that alloWs them to access department or
`company employee data, as Well as resource information,
`such as name and location of printers, copy machines, and
`other environment resources. In the Internet/intranet
`environment, it Will be required to provide user access to
`such information in a secure manner.
`To this end, the LightWeight Directory Access Protocol
`(LDAP) has emerged as an Internet Engineering Task Force
`(IETF) open standard to provide directory services to appli
`cations ranging from e-mail systems to distributed system
`management tools. LDAP is an evolving protocol that is
`based on a client-server model in Which a client makes a
`TCP/IP connection to an LDAP server, sends requests, and
`receives responses. The LDAP information model, in
`particular, is based on an “entry”, Which contains informa
`tion about some object. Entries are typically organiZed in a
`speci?ed tree structure, and each entry is composed of
`attributes.
`LDAP provides the capability for directory information to
`be queried or updated. It offers a rich set of searching
`capabilities With Which users can put together compleX
`queries to get desired information from a backing store. As
`originally implemented (at the University of Michigan),
`LDAP used several freely available b-tree packages, such as
`the GNU dbm and Berkeley db44 packages. This reference
`implementation, hoWever, does not provide a reliable and
`scaleable enterprise directory, in part, because of the use of
`a btree-based backing store.
`One problem is that different vendors provide different
`mechanisms for the tree structure. For example, DB/2 pro
`vides the WITH clause in a Structured Query Language
`(SQL) SELECT statement to provide subtree transversal
`With arbitrary depth. Oracle, hoWever, used CONNECT BY
`65
`PRIOR and START WITH clauses in the SELECT statement
`to provide partial support for reachability and path enumera
`
`40
`
`45
`
`50
`
`55
`
`60
`
`2
`tion. Other database management systems used different
`SQL semantics. In any case, all such mechanisms end up
`using recursive queries to handle hierarchical structures such
`LDAP entries. Recursive queries do not scale up Well as the
`number of records in a relation table increases. Indeed, in a
`simple eXample involving 1000 LDAP entries, using DB/2
`recursive queries, a simple SELECT takes more than several
`minutes to complete.
`Thus, there is a need to provide a faster and more ef?cient
`method to support LDAP searches With relational tables
`Without the overhead of recursive queries. This invention
`addresses and solves this problem.
`
`BRIEF SUMMARY OF THE INVENTION
`A primary object of this invention is to represent a
`directory service naming hierarchy With relational tables to
`facilitate fast and ef?cient directory service search capabil
`ity.
`Another primary object of this invention is to support
`hierarchical directory service searching With relational
`tables in a manner that obviates recursive queries, especially
`during one level and subtree traversal.
`A further, more speci?c object of this invention is to
`provide hierarchical LDAP searches using relational tables
`in an LDAP directory service having a relational database
`management system (DBMS) as a backing store.
`A more general object of this invention is to provide a
`reliable and scaleable enterprise directory solution.
`These and other objects of the invention are provided by
`mapping entries in a naming hierarchy into ?rst and second
`relational tables: a parent table, and a descendant table. The
`naming hierarchy has a plurality of entries each represented
`by a unique identi?er (EID). A preferred implementation is
`LDAP using a DB/2 backing store.
`In one preferred embodiment, the parent table is generated
`as folloWs. For each entry that is a parent of a child entry in
`the naming directory, the unique identi?er of the parent entry
`is associated With the unique identi?er of each entry that is
`a child of that parent entry. The parent table then comprises
`tWo (2) columns, a ?rst column listing the parent entries’
`unique identi?ers (in order), and a second column listing the
`associated child entries’ unique identi?ers. Thus, a given
`roW of the parent table includes a parent entry and its
`associated child entry. The parent table summariZes parent
`child relationships in the hierarchy.
`The descendant table is preferably generated as folloWs.
`For each entry that is an ancestor of one or more descendent
`entries in the naming hierarchy, the unique identi?er of the
`ancestor entry is associated With the unique identi?er of each
`entry that is a descendent of that ancestor entry. The descen
`dant table then comprises tWo (2) columns: a ?rst column
`listing the ancestor entries unique identi?ers (in order), and
`a second column listing the associated descendant entries’
`unique identi?ers. Thus, a given roW of the descendant table
`includes an ancestor entry and one of its associated descen
`dant entries. The descendant table summariZes ancestor
`descendant relationships in the hierarchy.
`These tables are used to “?lter” 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.
`The foregoing has outlined some of the more pertinent
`objects and features of the present invention. These objects
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 8
`
`

`

`6,085,188
`
`3
`should be construed to be merely illustrative of some of the
`more prominent features and applications of the invention.
`Many other bene?cial results can be attained by applying the
`disclosed invention in a different manner or modifying the
`invention as Will be described. Accordingly, other objects
`and a fuller understanding of the invention may be had by
`referring to the folloWing Detailed Description of the Pre
`ferred Embodiment.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`A block diagram of a representative LDAP directory
`service in Which the present invention may be implemented
`is shoWn in FIG. 1. As is Well-knoWn, LDAP is the light
`Weight directory access protocol, and this protocol has been
`implemented in the prior art, e.g., as either a front end to the
`X500 directory service, or as a standalone directory service.
`According to the protocol, a client machine 10 makes a
`TCP/IP connection to an LDAP server 12 through netWork
`11, sends requests and receives responses. LDAP server 12
`supports a directory 21 as illustrated in a simpli?ed form in
`FIG. 2. Each of the client and server machines further
`include a directory “runtime” component 25 for implement
`ing the directory service operations as Will be described
`beloW. The directory 21 is based on the concept of an “entry”
`27, Which contains information about some object (e.g., a
`person). Entries are composed of attributes 29, Which have
`a type and one or more values. Each attribute 29 has a
`particular syntax that determines What kinds of values are
`alloWed in the attribute (e.g., ASCII teXt, binary characters,
`and the like) and hoW these values are constrained during a
`particular directory operation.
`The directory tree is organiZed in a predetermined
`manner, With each entry uniquely named relative to its
`sibling entries by a “relative distinguished name” (RDN).
`An RDN comprises at least one distinguished attribute value
`from the entry and, at most, one value from each attribute is
`
`40
`
`45
`
`55
`
`60
`
`65
`
`For a more complete understanding of the present inven
`tion and the advantages thereof, reference should be made to
`the folloWing Detailed Description taken in connection With
`the accompanying draWings in Which:
`FIG. 1 is a representative LDAP directory service imple
`mentation;
`FIG. 2 is a simpli?ed LDAP directory;
`FIG. 3 is a ?oWchart of an LDAP directory session;
`FIGS. 4A—4C shoW representative LDAP directory ser
`vice implementations having relational database backing
`store;
`FIG. 5 is a representative LDAP naming hierarchy for
`illustrative purposes;
`FIG. 6A is a parent table generated from the LDAP
`naming hierarchy of FIG. 5;
`FIG. 6B is a descendant table generated from the LDAP
`naming hierarchy of FIG. 5;
`FIG. 7 is a ?oWchart illustrating a routine for deleting
`entries;
`FIG. 8 is a ?oWchart illustrating a routine for adding
`entries;
`FIG. 9 is a ?oWchart illustrating a subtree LDAP search
`according to the invention; and
`FIG. 10 is a ?oWchart illustrating a one level LDAP
`search according to the invention.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`4
`used in the RDN. According to the protocol, a globally
`unique name for an entry, referred to as a “distinguished
`name” (DN), comprises a concatenation of the RDN
`sequence from a given entry to the tree root.
`LDAP includes an application programming interface
`(API), as described in “The C LDAP Application Program
`Interface”, IETF Task Force Working Draft, Jul. 29, 1997,
`Which is incorporated herein by reference. An application on
`a given client machine uses the LDAP API to effect a
`directory service “session” according to the ?oWchart of
`FIG. 3. At step 40, an LDAP session With a default LDAP
`server is initialiZed. At step 42, an API function ldapiinit()
`returns a handle to the client, and this handle alloWs multiple
`connections to be open at one time. At step 44, the client
`authenticates to the LDAP server using, for eXample, an API
`ldapibind() function. At step 46, one or more LDAP
`operations are performed. For eXample, the API function
`ldapisearch() may be used to perform a given directory
`search. At step 48, the LDAP server returns the results. The
`session is then closed at step 50 With the API ldapiunbind()
`function then being used to close the connection.
`It may be desirable to store LDAP directory data in a
`backing store. FIGS. 4A—4C illustrates several representa
`tive LDAP directory service implementations that use a
`relational database management system (RDBMS) for this
`purpose. These systems merely illustrate possible LDAP
`directory services in Which the present invention may be
`implemented. One of ordinary skill should appreciate,
`hoWever, that the invention is not limited to an LDAP
`directory service provided With a DB/2 backing store. The
`principles of the present invention may be practiced in other
`types of directory services (e.g., X500) and using other
`relational database management systems (e.g., Oracle,
`Sybase, InformiX, and the like) as the backing store.
`In FIG. 4A, an LDAP client 34 can connect to a number
`of netWorked databases 38a—38n through an LDAP server
`36. The databases 38a—38n contain the directory informa
`tion. HoWever, from the user’s perspective, the LDAP server
`36 actually stores all the information Without knoWing the
`database 38 in Which the data is actually located. With this
`con?guration, the LDAP server 36 is freed from managing
`the physical data storage and is able to retrieve information
`from multiple database servers 38 Which Work together to
`form a huge data storage.
`FIG. 4B illustrates a multiple client/multiple server
`LDAP/DB2 enterprise solution. In this environment, a DB/2
`client preferably runs on each LDAP server 36. Each such
`DB/2 client can connect to any database server 38 contain
`ing directory information. The collection of database servers
`38a—38n form a single directory system image, and one or
`more of the LDAP servers 36 can access such information.
`Because all the LDAP servers 36 see the same directory
`image, a netWork dispatcher 37 may be deployed to route
`requests among the LDAP servers 36.
`FIG. 4C illustrates a multiple client/parallel super server
`con?guration. In certain environments, Where users need to
`store large amounts of information into the directory, this
`con?guration automatically partitions the database into dif
`ferent machines 38. In addition, database queries are divided
`into smaller, independent tasks that can eXecute
`concurrently, Which increases end user query response time.
`This con?guration enables users to store up to terabytes of
`data into the database.
`FIG. 5 represents an illustrative LDAP directory service
`naming hierarchy 41. It is an object of the present invention
`to provide a scheme for mapping the naming hierarchy 41
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 9
`
`

`

`5
`into preferably a pair of so-called relational tables 43 and 45,
`as illustrated in FIGS. 6A—6B, respectively. For
`convenience, table 43 illustrated in FIG. 6A is a “parent
`child” or so-called “parent” table for short, and table 45
`illustrated in FIG. 6B is an “ancestor-descendant” or
`so-called “descendant” table for short. Mapping the naming
`hierarchy 41 into the ?rst and second tables 43 and 45
`provides the signi?cant advantage of obviating recursive
`queries during the performance of certain LDAP searches.
`The folloWing discussion of the naming hierarchy in FIG.
`5 and its associated relational tables in FIGS. 6A—6B is
`merely illustrative. As seen in FIG. 5, the LDAP naming
`hierarchy includes a number of entries or nodes, With each
`entry or node represented by a unique entry identi?er (EID).
`Thus, for example, the root node has an EID=1. Root has
`tWo (2) children, entry GB (“Great Britain”) having an
`EID=2, and entry US (“United States”) having an EID=3.
`Child node US itself has tWo (2) children, O=IBM (With
`EID=4) and O=Netscape (With EID=5). The remainder of
`the naming directory includes several additional entries at
`further sublevels.
`Aparticular entry thus may be a “parent” of one or more
`child entries. An entry is considered a “parent” if it is located
`in a next higher level in the hierarchy. Likewise, a particular
`entry may be an ancestor of one or more descendant entries
`across many different levels of the hierarchy. Aparent-child
`entry pair Will thus also represent an ancestor-descendant
`pair.
`According to the invention, the parent table is created as
`folloWs. For each entry that is a parent of a child entry in the
`naming directory, the unique identi?er of the parent entry
`(PEID) is associated With the unique identi?er of each entry
`that is a child of that parent entry. For the naming directory
`of FIG. 5, this association creates the parent table illustrated
`in FIG. 6A. Thus, PEID 1 is associated With EID 2 and EID
`3, PEID 3 is associated With EID 4 and EID 5, and so on.
`Each roW of the parent table includes a PEIDzEID pair.
`The descendant table is created as folloWs. For each entry
`that is an ancestor of one or more descendent entries in the
`hierarchy, associating the unique identi?er of the ancestor
`entry (AEID) With the unique identi?er of each entry that is
`a descendent (DEID) of that ancestor entry. The AEID ?eld
`is the unique identi?er of an ancestor LDAP entry in the
`LDAP naming hierarchy. The DEID ?eld is the unique
`identi?er of the descendent LDAP entry. Thus, in the naming
`directory 41, AEID 1 has DEIDs 2—10, because each of
`entries 2—10 are also descendants of the root node. AEID 3
`has DEIDs 4—10, AEID 4 has DEIDs 6—10, and so on. Each
`roW in the descendant table thus includes AEIDzDEID pair.
`The invention thus implements tWo relations or tables in
`order to support LDAP search: parent/child and ancestor/
`descendants. In the parent table, the EID ?eld is the unique
`identi?er of an entry in the LDAP naming hierarchy. The
`PEID ?eld is the unique identi?er of the parent entry in the
`naming hierarchy. In the descendant table, the AEID ?eld is
`the unique identi?er of an ancestor LDAP entry in the LDAP
`naming hierarchy. The DEID ?eld is the unique identi?er of
`the descendent LDAP entry.
`LDAP provides a number of knoWn functions including
`query (search and compare), update, authentication and
`others. The search and compare operations are used to
`retrieve information from the database. For the search
`function, the criteria of the search is speci?ed in a search
`?lter. The search ?lter typically is a Boolean expression that
`consists of attribute name, attribute value and Boolean
`operations like AND, OR and NOT. Users can use the ?lter
`
`45
`
`55
`
`15
`
`65
`
`6,085,188
`
`6
`to perform complex search operations. The ?lter syntax is
`de?ned in RFC 1960 (RFC stands for Request For
`Comments, See http://WWW.cis.ohiostate.edu/hypertext/
`information/rfc.html).
`In addition to the search ?lter, users can also specify
`Where in the directory tree structure the search is to start. The
`starting point is called the base DN. The search can be
`applied to a single entry (a base level search), an entry’s
`children (a one level search), or an entire subtree (a subtree
`search). Thus, the “scope” supported by an LDAP search
`are: base, one level and subtree. LDAP does not support
`search for arbitrary tree levels and path enumeration.
`According to the invention, the relation tables model the
`relationship betWeen the LDAP entries to facilitate one level
`and subtree searches Without recursive queries. In both
`cases, the search begins by going into the database and using
`the LDAP ?lter criteria to retrieve a list of entries matching
`the ?lter criteria. If the search is a one level search, the
`parent table is then used to ?lter out EIDs that are outside the
`search scope (based on the starting point or base DN).
`Likewise, if the search is a subtree search, the descendant
`table is then used to ?lter out EIDs that are outside the search
`scope (again, based on the base DN). Generally, the tables
`are not required to be used in a base level search.
`In a preferred embodiment, each LDAP attribute that can
`be searched by the user is mapped to an attribute relation that
`consists of tWo columns: EID and normaliZed attribute
`value. As described above, each LDAP entry is assigned a
`unique identi?er (EID). Based on the attribute syntax, the
`attributes are converted (or normaliZed) so that the invention
`can apply Structured Query Language (SQL) queries to the
`attribute values. For example, if the attribute syntax is case
`insensitive (CIS), the attribute value Will be converted to all
`upper case and stored in an attribute table. The attribute table
`is used mainly for search operations to ?nd the entries that
`match the ?lter criteria. The actual entry data is preferably
`stored in an ldapientry table, as Will be described. Thus, the
`generated SQL queries use the attribute table to locate the
`entry EIDs that match the ?lter expression. Then, the EIDs
`are used to retrieve the entry data from the ldapientry table.
`Various routines are provided for manipulating entries and
`for searching using the relational tables described above. As
`described beloW, the ldapientry table includes the parent
`table, and the descendant table is the ldapidesc table. These
`routines are noW described generally.
`FIG. 7 is a ?oWchart illustrating an ldapidelete (or
`delete) routine that removes entries from the database. It
`begins at step 50. At step 52, the routine maps the distin
`guished name (DN) to the entry identi?er (EID). The routine
`then continues at step 54 by obtaining the ancestor (PEID’s)
`from the ldapidesc table. For each PEID retrieved, the
`routine then performs a processing loop at step 56. In
`particular, the routine removes the PEID and EID pair from
`the descendant table (ldapidesc table), at step 58, and then
`cycles. When step 56 is complete (ie all PEIDs have been
`processed), the routine branches to step 60 to remove the
`EID entry from the ldapientry table. This completes the
`processing.
`FIG. 8 is a ?oWchart for a routine called ldapiadd for
`adding entries to the database. Because the directory struc
`ture Will be changed When entries are added into the
`database, the parent table (or ldapientry) and the descen
`dant table (ldapidesc) are updated to re?ect the change. In
`other Words, after all tables get created, the ldapiadd
`routine is used to populate the tables With correct informa
`tion.
`
`IPR2017-01839
`Ubisoft, et al. EX1009 Page 10
`
`

`

`6,085,188
`
`8
`
`7
`The routine begins at step 62. At step 64, the routine
`retrieves the EID for the entry. A test is then performed at
`step 66 to determine Whether the entry eXists. If so, the
`routine branches to step 68 and eXits. If, hoWever, the output
`of the test at step 66 indicates that the entry does not exist,
`the routine continues at step 70 to obtain the parent identi?er
`(PEID). At step 72, the routine adds an entry into the
`ldapientry table, using the EID and its associated PEID.
`Then, the routine continues at step 74 to the ancestor EIDs
`(AEIDs) from the ldapidesc table. For each ancestor EID
`(AEID), the routine then performs a processing loop begin
`ning at step 76. In particular, at step 78, the routine adds a
`roW in the descendant table With the EID and its associated
`AEID. The routine then cycles back to step 76 until all
`AEIDs are processed, at Which point the routine is ?nished.
`FIG. 9 is a ?oWchart illustrating a subtree search.
`As described above, this search preferably uses the
`descendant table to obviate recursive queries through a list
`of entries returned from an initial search query. The routine
`begins at step 80. At step 82, the routine retrieves entry EIDs
`Which match the ?lter criteria from the attribute tables. Step
`82 thus outputs a ?rst set of EIDs that appear to match the
`search criteria. This set is then ?ltered using the descendant
`table as Will be seen. In particular, at step 84, the routine
`maps the base DN to the entry EID. Step 84 outputs a base
`DN EID:base EID. The routine then continues at step 86 to
`retrieve the descendants EIDs from the descendant table
`(ldapidesc) using the base EID. The output of step 86 is a
`second set of EIDs. The routine then enters the processing
`loop 88 until all EIDs in the ?rst set have been tested. In
`particular, the routine performs a test at step 90 to determine
`Whether the EID under test is in the second set. If not, the
`routine cycles back to step 88 to get the neXt EID. If the
`outcome of the test at step 90 is positive, hoWever, the
`routine retrieves the entry data from the ldapientry table at
`step 92, and then sends back the results at step 94. The
`routine then cycles back to step 88 until complete. When all
`EIDs in the ?rst set have been tested, the routine branches
`to step 96 to send back the end of search command. The
`routine then terminates at step 98.
`FIG. 10 is a ?oWchart for a one level search. As described
`above, this search uses the parent table to obviate recursive
`queries through a list of entries returned from an initial
`search query. The routine begins at step 100. At step 102, the
`routine retrieves entry EIDs that match the ?lter criteria
`from the attribute tables. Step 102 outputs a ?rst set of EIDs.
`At step 104, the routine maps the base DN to the entry EID.
`At step 106, the routine retrieves the children EIDs from the
`ldapientry table using the base EID. This outputs a second
`set of EIDs. The routine then enters the processing loop 108
`until all EIDs in the ?rst set have been tested. In particular,
`the routine performs a test at step 110 to determine Whether
`the EID under test is in the second set. If not, the routine
`cycles back to step 108 to get the neXt EID. If the outcome
`of the test at step 110 is positive, hoWever, the routine
`retrieves the entry data fro