A SAT approach to query optimization in mediator systems

Mediator systems integrate distributed, heterogeneous and autonomous data sources, but their effective use requires the solution of hard query optimization problems. This is usually done in two phases: the selection of a set of data sources is similar to a set covering problem, and their ordering into a feasible and efficient query is a capability restricted join order problem. However, a two-phase approach is unlikely to find optimum queries. We describe a new single-phase approach that, under a simple cost model, can be encoded and solved as a SAT problem. Results on artificial benchmarks indicate that this is an interesting problem from the encoding and search viewpoints, and we use them to address three of the ten SAT challenges posed by Selman, Kautz and McAllester in 1997.