1. A method for query evaluation, comprising: receiving a query over a set of distributed data sources; decomposing the query into a set of sub-queries of the query; evaluating each sub-query in the set of sub-queries with respect to each data source in the set of distributed data sources, wherein evaluating comprises determining which data sources in the set of distributed data sources are capable of answering each sub-query; computing a set of distributed plans by composing one or more of the sub-queries in one or more of the data sources; evaluating each plan in the set of distributed plans; selecting a sub-set of plans from the set of distributed plans to be executed for responding to the query; executing the selected sub-set of plans; and returning results of the query; wherein the receiving, decomposing, evaluating each sub-query, computing, evaluating each plan, selecting, executing and returning steps are performed via a processing device and a memory.