Approximate Query Translation

Across Heterogeneous Information Sources

Users access information sources by asking a query to retrieve the desired data.  For instance, a query [fname = Tom] AND [lname = Hanks] for an online media store (to find the movies by Tom Hanks) may return data (title: "Apollo 13", price: $30, shipping: $5).  Integrating heterogeneous sources is difficult because of their non-uniform query languages and data representations.  For instance, to search source amazon.com, we must translate the example query as [actors contains "Tom Hanks"].  To uniformly present data from different sources, we may also need to map the result as (title: "Apollo 13", cost: $35).  This mapping must transform differences in attributes (e.g., lname and fname to actors), values (e.g. 30 plus 5 to 35), and operators (e.g., ``'=' to ``contains').

This work focuses on mapping queries across disparate contexts.  Such translation is critical especially since the Internet has brought together information sources worldwide.  In particular, the mapping is essential for many important applications such as meta-searching (querying many sources by a mediator), e-commerce (e.g., comparison shopping), and web mining (by querying sources and analyzing data).

Exact Query Translation:  Our work started with developing a query translation mechanism for exact query processing [6].  The mechanism will find the minimal-superset mappings that do not miss any answers (i.e., no false-negatives) and that incur as few extra ones as possible (i.e., minimal false-positives).  To obtain the exact query results, we also designed the derivation of filter queries for removing false-positives [5].  The algorithms guarantee that the translated queries minimally subsume the original ones and that the filter queries are of minimal cost.  Furthermore, since the translation machinery relies on separately-supplied rules for rewriting basic query constraints, I also developed algorithms for rewriting IR predicates commonly used for document retrieval [2], and evaluated the post-filtering cost for such rewritings [10].

Approximate Query Translation:  We have then further developed general approximate query translation that finds the closet mappings under virtually anycloseness criteria, such as minimal-superset, maximal-subset, or some hybrid scheme that combines both precisionand recall[15].  I defined a customizable notion of closeness and designed a general translation machinery.  As the basis, I have studied fundamental theorems on the constraint dependencies and the separabilityacross query conjuncts and disjuncts.  The results are essential for any algorithm that attempts approximate query translation.


Last update: Mar. 9 2000
Chen-Chuan K. Chang,  kevin@db.stanford.edu