Mind Your Vocabulary: Query Mapping Across Heterogeneous Information Sources

Abstract

In this paper we present a mechanism for translating constraint queries, i.e., Boolean expressions of constraints, across heterogeneous information sources. Integrating such systems is difcult in part because they use a wide range of constraints as the vocabulary for formulating queries. W e describe algorithms that apply userprovided mapping rules to translate query constraints into ones that are understood and supported in another context, e.g., that use the proper operators and value formats. W e show that the translated queries minimally subsume the original ones. Furthermore, the translated queries are also the most compact possible. Unlike other query mapping work, we effectively consider inter-dependencies among constraints, i.e., we handle constraints that cannot be translated independently . Furthermore, when constraints are not fully supported, our framework explores relaxations (semantic rewritings) into the closest supported version. Our most sophisticated algorithm (Algorithm TDQM ) does not blindly convert queries to DNF (which would be easier to translate, but expensivinstead it performs a top-down mapping of a query tree, and does local query structure conversion only when necessary .