The graph system needs to be able to push a search/query down to a connector, and we need to develop a query model (in the form of concrete classes, probably immutable). Connectors can optionally support queries, and if they do they will process the query and return the results.
Particular language bindings would be put on top of this query model. For example, JCR 1.0 defines an XPath language. Support for each language would parse a query in that language and produce a query model.