Using Q-Grams in a DBMS for Approximate String Processing

String data is ubiquitous, and its management has taken on particular importance in the past few years.  Approximate queries are very important on string data.  This is due, for example, to the prevalence of typographical errors in data, and multiple conventions for recording attributes such as name and address.  Commercial databases do not support approximate string queries directly, and it is a challenge to implement this functionality efficiently with user-defined functions (UDFs).  In this paper, we develop a technique for building approximate string processing capabilities on top of commercial databases by exploiting facilities already available in them.  At the core, our technique relies on generating short substrings of length q, called q-grams, and processing them using standard methods available in the DBMS.  The proposed technique enables various approximate string processing methods in a DBMS, for example approximate (sub)string selections and joins, and can even be used with a variety of possible edit distance functions.  The approximate string match predicate, with a suitable edit distance threshold, can be mapped into a vanilla relational expression and optimized by conventional relational optimizers.