The heterogeneity of Web information services poses new problems in the processing of user queries over distributed federated data. It was recerntly proven that the query translation between two information services supporting all Boolean operators can be done in an optimal way. On the Web, however, the situation when at least one Boolean operator is not supported is frequent. We study the case where a Boolean user query cannot be directly translated and should be split into sub-queries. We propose two strategies for query subsumption and discuss in detail the strategy which minimizes the number of submitted sub-queries. We derive an appropriate query form for the minimal strategy and demonstrate how both translation strategies are implemented in the Knowledge Brokers system.

