Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-09-24
2002-03-12
Vu, Kim (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06356892
ABSTRACT:
This application includes subject matter protected by copyright. All rights are reserved.
BACKGROUND OF THE INVENTION
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 form an integrated distributed computing environment. Typical uses of a directory services may be classified into several categories. A “naming service” (e.g., DNS and DCE Cell Directory Service (CDS)) uses the 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 information about 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 “white 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 generation directory service will need to provide system administrators with a data repository that can significantly 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 IETF open standard to provide directory services to applications 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 information about some object. Entries are typically organized in a specified tree structure, and each entry is composed of attributes.
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 specified in a search filter. The search filter typically is a Boolean expression that consists of qualifiers including attribute name, attribute value and Boolean operators like AND, OR and NOT. Users can use the filter to perform complex search operations. One filter syntax is defined in RFC 2254.
LDAP thus provides the capability for directory information to be efficiently 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. Increasingly, it has become desirable to use a relational database for storing LDAP directory data. Representative database implementations include DB/2, Oracle, Sybase, Informix and the like. As is well known, Structured Query Language (SQL) is the standard language used to access such databases.
One of main goals for implementing an LDAP directory service with an relational database backing store (e.g., DB/2) is to provide a design and implementation such that all LDAP search queries can be executed efficiently with SQL. Implementing LDAP search queries with SQL, however, is a non-trivial task. On the one hand, because both LDAP and SQL use the same AND, OR and NOT logical operators, one possible solution to implementing LDAP search queries with SQL might simply involve mapping each LDAP operator to its corresponding SQL operator. This approach, however, does not work well in practice. Another approach, characterized by known prior art implementations (e.g., the Netscape b-tree LDAP server), involves retrieval of a superset of candidate entries, together with post-processing on those entries. There are several problems with this technique. The two-step process is time consuming. More problematic, however, is that negation and existence queries give rise to a sequential search through the whole database. For a LDAP directory with a large number of entries, search results cannot be returned in an efficient manner.
The present invention addresses the problem of efficiently mapping an LDAP filter into an SQL query.
BRIEF SUMMARY OF THE INVENTION
It is a primary object of this invention to provide a method for searching a relational database using hierarchical, filter-based queries, such as LDAP.
Another primary object is to provide an algorithm that combines basic LDAP filter expressions into a preferably single SQL query that retrieves target entries that exactly match given search criteria.
Still another important object of this invention is to provide a mechanism that can map even complicated LDAP queries having infinite logical depth into SQL to facilitate a relational database search.
Yet another important object of this invention is to map LDAP logical operators efficiently for use in an LDAP relational database search mechanism.
A more specific object of this invention is to efficiently implement LDAP search queries with SQL wherein simple queries are combined together to form an arbitrary complex query that can retrieve target entries, preferably with no post-processing involved.
It is also an object of the present invention to provide a method for mapping LDAP search queries into an SQL query that is efficient and does not degenerate into a sequential search.
It is another more specific object of the present invention to provide a recursive algorithm that can deal with LDAP filter operators in a consistent way, and that deals with complicated LDAP queries with infinite number of logical operators.
A more general 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, wherein a preferred implementation is LDAP using a DB/2 backing store.
The present invention solves the problem of efficiently mapping an LDAP filter into an SQL query using unique entry identifier (EID) sets. According to the inventive method, a SQL subquery is first generated for each LDAP operator based on given translation rules. The SQL subquery generates a set of entry EIDs that match the LDAP basic operation. Thereafter, the SQL subqueries are combined into a single SQL query according to a set of combination rules chosen corresponding to the logical operators of the LDAP filter query. Thus, for example, if the LDAP logical operator is OR(|), the invention then preferably uses an SQL UNION to union the sets generated from the subquery. If the LDAP logical operator is AND (&), the invention preferably uses an SQL INTERCEPT to intercept the sets generated from the subquery. If the LDAP logical operator is NOT, the invention preferably excludes entries by negating the IN operation before the subquery. Thus, the combination rules includes, for example, mapping the LDAP logical OR operation to an SQL UNION, mapping the LDAP logical operation AND to SQL INTERCEPT, and mapping the LDAP logical operation NOT to SQL NOT IN.
Generalizing, according to the preferred embodiment, a method for searching a relational database using hierarchical, filter-based queries begins by parsing a filter-based query for elements and logical operators of the filter query. For each filter element, the method generates an SQL subquery according to a set of translation rules. For each SQL subquery, the method then generates a set of entry identifiers for the filter query.
Corn Cynthia Fleming
Fichtner Larry George
Mancisidor Rodolfo Augusto
Shi Shaw-Ben
International Business Machines - Corporation
LaBaw Jeffrey S.
Ly Anh
Vu Kim
Winstead Sechrest & Minick P.C.
LandOfFree
Efficient implementation of lightweight directory access... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient implementation of lightweight directory access..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient implementation of lightweight directory access... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2843789