With reference to:  
http://rdfweb.org/people/danbri/2001/11/distquery/

How about using the original full query as the basis for a service query?


About (service query):
  (dig:sha1 ?vid ?sha)
  (dc:title ?vid ?t)
  (dc:identifier ?vid ?loc)
  (foaf:page ?vid
    http://example.com/videocatalog/someshow/episode_1001.html)


Response from Service A:

(dig:sha1 #vid #sha)
(dc:title #vid #t)
(foaf:page #vid http://example.com/videocatalog/someshow/episode_1001.html)


Response from Service B:

(dig:sha1 #vid #sha)
(dc:identifier #vid #loc)


I'm thinking here that, presuming that an RDF lookup service can determine without searching some indication of the number of matching values, the response would be those parts of the original query to which it can provide some answers, and the query variable placeholders be replaced by some indication of the value count that can be used by the original requester for query optimization.

The counts would be rough estimates, not guaranteed counts, so that performance of the service query of not compromised by the need to gather accurate statistics.  Also, I envisage that the value counts would not be cross-tabulated.  E.g. the counts for (dig:sha1 #vid #sha) would be the total number of different subject and object values associated with property dig:sha1.