Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-05-02
2004-08-31
Channavajjala, Srirama (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06785677
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to the field of Structured Query Language (SQL) and in particular to a method for significantly improving the performance of executing pattern matching queries in which the special characters used in the pattern are limited to single and multi-character wild cards, rather than full regular expressions.
BACKGROUND OF THE INVENTION
Structured Query Language (SQL) is a widely used language for accessing data stored in relational databases. To allow the selective retrieval of data, SQL provides predicates that can be applied to data to determine which records are retrieved. For example, the following SQL query uses a comparison predicate to select those employee records for any employee whose last name is “Smith”:
Select*From employee Where last_name=‘Smith’
One particularly powerful predicate found in all SQL implementations is the LIKE predicate, which determines whether string-valued fields in the database conform to a particular pattern:
Select*From employee Where last_name Like ‘% son’
The pattern, represented in the above query by ‘% son’ describes a set consisting of all strings ending in “son”. The multi-character wild card “%” matches any sequence of characters, including the empty string. An underscore “_”) can be used to match a single arbitrary character. Aside from these two “wild card” metacharacters, characters occurring in the pattern are matched only by the same character in the string being tested against the pattern.
The pattern language defined by the LIKE predicate is a subset of a notation known as regular expressions. In addition to single- and multi-character wild card matching, regular expressions may contain syntax specifying grouping, choice, and repetition of subpatterns. Regular expressions are commonly used in performing the lexical analysis phase of compilation of computer program source code, breaking the input stream into distinct entities called tokens that are input to a parser for the language.
The most efficient solutions to this problem employ finite automata to represent the patterns for the token types used in the language. There are two different types of automata that may be used to represent regular expressions. A deterministic finite automaton (DFA) has the defining property that for any given input symbol in any given state, there is at most one transition to a new state that can be made. In a nondeterministic finite automaton (NFA), it is possible that there are two or more possible transitions from a given state for a given input symbol. Simulation of NFAs is difficult due to the potential ambiguity of nondeterministic state transitions, so DFAs are generally used as recognizers for regular expressions. As each symbol is read, a state transition is made based on the input symbol and the current state. The most efficient transition function involves a simple table lookup, where the table contains the transition state for each symbol/state pair. This requires a significant amount of memory for single-octet character sets such as ASCII, and a prohibitive amount for multi-octet character sets such as Unicode. Sparse matrix techniques can be employed to reduce the storage requirements of the transition table, but this results in reduced efficiency for the transition function.
The restrictive nature of the pattern language used with SQL's LIKE predicate makes it possible to derive a simpler, more efficient algorithm that does not require construction of automata and tracking of state changes for each character processed during evaluation of the predicate. While suitable for evaluation of fully general patterns based on unrestricted regular expressions, automata-based algorithms are overkill for the LIKE predicate. The present invention achieves significantly accelerated performance for evaluation of patterns such as those permitted by the LIKE predicate, which utilize only wild card operators (single-character and multi-character).
One prior art method to which the method of the present invention generally relates is described in U.S. Pat. No. 5,926,652 entitled MATCHING OF WILD CARD PATTERNS TO WILD CARD STRINGS ASSOCIATED WITH NAMED COMPUTER OBJECTS. The prior art method of matching computer wild card patterns involves comparing first and second character strings associated with named objects residing on a computer system to determine whether the first character string defines a first group of computer objects which is a logical subset of a second group of computer objects defined by the second character string. The first character string is provided by a user; such as in a command line, and the second character string is pre-defined, such as by a network administrator. The method can be performed by examining whether the second character string has any wild card character which can substitute for one and only one character, or by examining whether the second character string has any wild card character which can substitute for any number of characters, including no characters (a universal character). The second character string can further be examined to see if it contains any embedded sequence of characters having no universal wild card character.
The present invention differs from the prior art in that the prior art method is concerned with matching a pair of patterns to determine whether one is a logical subset of the other. The method of the present invention seeks instead to determine whether a text string (which is a literal value rather than another pattern) is a member of the set of strings derivable from the pattern. That is, it determines whether the string matches the pattern. Unlike the prior art method, the present invention decomposes the pattern into segments of literal text bounded by multi-character wild cards, and employs a string-matching algorithm modified to take single-character wild cards into account to search for the substrings within the target string.
Another prior art method to which the method of the present invention generally relates is detailed in U.S. Pat. No. 6,047,283 entitled FAST STRING SEARCHING AND INDEXING USING A SEARCH TREE HAVING A PLURALITY OF LINKED NODES. This prior art is a fast string indexing method that efficiently stores, searches, and removes alphanumeric or binary strings utilizing a compacted search tree. The number of levels in the search tree is minimized by having a node represent more than one character when possible. Each inner node of the tree contains a hash table array for successive hashing, which also minimizes the time required to traverse a given node. Searches may be performed for partial matches, such as wild cards at the character level. Multiple indices may be opened independently and concurrently on the same table of string entries.
The present invention differs from the prior art in that the prior art method is used as an access method on a database, and is comprised of a search tree that indexes strings so those strings may be looked up quickly in a database search. The intent is to overcome limitations of other access methods such as linear searching, hashing, and conventional search trees. Strings searched for in the search tree described in the prior art method can contain single-character wild cards, but not wild cards that match substrings of arbitrary length as in the present invention. The prior art method finds matching strings by traversing a tree structure containing representations of the strings being searched, while the current invention instead matches strings against a pattern without requiring those strings to be indexed. Another difference is that the present invention uses a string-matching algorithm to match literal substrings between wild cards, whereas the prior art method searches by traversing the nodes of its search tree.
It is therefore an object of the present invention to improve the performance of matching string patterns containing wild card characters.
Still another object of the present invention is to increase the efficiency of database transactions involving
Channavajjala Srirama
Kozak Alfred W.
Rode Lise A.
LandOfFree
Method for execution of query to search strings of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for execution of query to search strings of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for execution of query to search strings of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3306724