How do you argue a query is impossible in a query language like SPARQL or SQL? I've been investigating the ability of the SPARQL query language to represent certain basic tasks in graph theory and machine learning, and have come to believe that it is not possible to do some. For example, I suspect that it is not possible to test (s,t)-connectivity without using Property Paths (but simple with them).  Also, I suspect that it is not possible to list the k nearest neighbors of a list of vectors with a single query.

Is there a proof technique or general approach to show, or at least provide some evidence, that a search or decision problem cannot be represented as a single query in a query language like SPARQL or SQL?
From page 52 of Leonid Libkin's Elements of Finite Model Theory textbook:


  Since we know that graph connectivity is not Hanf-local and transitive closure is not Gaifman-local, we immediately obtain, without using games, that these queries are not FO-definable.


SQL and (original) SPARQL are based on fragments of first-order logic, without fixed-point or transitive-closure operations.  The basic idea is that first-order formulas can only express things that are "local" in some sense, with the reach of locality increasing with the length and complexity of the formula.  (The definitions of Gaifman and Hanf locality make this precise.)  Transitive closure and graph connectivity require either a more powerful way of talking about arbitrarily long paths (like property paths in (new) SPARQL, or a fixed point operator), or arbitrarily long formulas.  So one can't capture path expressions of arbitrary length without explicitly adding support for them to a first-order-based query language.

If you want to know more, have a look at the above textbook, or at the paper:


Leonid Libkin, Logics capturing local properties, ACM Transactions on Computational Logic 2, 135–153, 2001.  doi:10.1145/371282.371388


which has a brief overview of the history with further references.