Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-11-19
2001-03-06
Kulik, Paul V. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06199062
ABSTRACT:
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.
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.
LDAP entries consist of attribute-value pairs. Within the relational database (e.g., DB/2), a separate table is created for each of the attributes allowed within the LDAP schema. Within this table, the attribute values are stored, along with an entry ID (EID) to which the attribute values belong. If the value of the attribute is less than the value for an indexable column, then an index is created based on the attribute value and the eid. Further, if the value exceeds the maximum length for an indexable column, an additional column is created that contains a truncated value. By generating the index (referred to below as a “forward” index for reasons that will be seen), the database is much faster at retrieving data during searches.
Wildcard search support is imperative when creating any searchable database. Although the use of the above-described index speeds most searches, searches beginning with a wildcard “*” (e.g., the string “*something”) do not perform nearly as well within relational databases such as DB/2. Primarily, this is because such databases use b-trees for indexing. In such known schemes, the b-tree search is then based on the leading characters of the search string. If a wildcard is present at the beginning of the string, the b-tree search algorithm has a difficult time finding a starting point. As a result, the search cannot be performed efficiently.
The present invention addresses the problem of inefficient wildcard searching in a relational database.
BRIEF SUMMARY OF THE INVENTION
It is a primary object of this invention to provide a method for wildcard searching of a relational database using hierarchical, filter-based queries, such as LDAP.
Another primary object of this invention is to force a wildcard search character into a position that is optimal for a particular database search algorithm.
Still another important object of this invention is to provide a mechanism that reverses a given character string (or some portion thereof) to optimize wildcard searching of a relational database.
Yet another important object of this invention is to map a given character string having a wildcard operator into a character string that may be optimally searched given the available database search strategy.
A more specific object of this invention is to efficiently implement LDAP SQL search queries having wildcard search characters.
These and other objects of the invention are described in a method for wildcard searching a relational database, e.g., by using hierarchical, filter-based queries. The method begins by generating a forward index of the character strings in the database. The method then generates a reverse index of the character strings in the relational database. The reverse index is generating, preferably by mirroring (i.e. creating a mirror image of) the forward index. Upon receipt of a hierarchical, filter-based query having a search string with a wildcard, the reverse index is then used to generate the corresponding relational database query (e.g., in SQL) if the wildcard is at a given position within the search string. Thus, for example, the given position is a leading position in the search string. Alternatively, the given position is an intermediate position in the search string and a number of characters trailing the wildcard is greater than a number of characters leading the wildcard. If the wildcard is not at the given position within the search string, the forward index is used to generate the relational database query. In either case, the relational database query is then used to access the relational database and return search results.
In a preferred embodiment, the filter-based query is a Lightweight Directory Access Protocol (LDAP) directory service query and the relational database is DB/2.
According to another aspect of the present invention, both forward and reverse indices may be used to search portions of the same search string. In this method of wildcard searching, the forward and reverse indices are first generated. Upon receipt of the hierarchical, filter-based query having the search string with the wildcard, a determination is made regarding whether the forward index, the reverse index, or both indices, should be used to generate the relational database query. This determination typically depend on the relative position of the wildcard in the search string. As a result of the determination, the relational database query is then generated and used to access the relational database. When both indices are used, typically the search is performed on a first portion of the string up to the wildcard using the forward index. The search is performed on the remaining portion of the string (after the wildcard) using the reverse index on the reverse of the second portion.
Byrne Debora Jean
McConaughy John Mark
Shi Shaw-Ben
Shu Chin-Long
Tran Trung Minh
International Business Machines - Corporation
Kulik Paul V.
LaBaw Jeffrey S.
Newberger Barry S.
Winstead Sechrest & Minick P.C.
LandOfFree
Reverse string indexing in a relational database for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reverse string indexing in a relational database for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reverse string indexing in a relational database for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2519098