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?

  • 2
    $\begingroup$ Are we supposed to know what this “SPARQL query language” is? $\endgroup$ Feb 2, 2013 at 1:10
  • 3
    $\begingroup$ It seems to me that one of the complications involved in this question is you're asking about the complexity of a query language yet not necessarily about it's corresponding logic (which in this case is Description Logic of RDF(S)/OWL). I'm wondering if there is a formal field of complexity analysis of query languages that is more or less independent from the logic form they query over? As an example, Jena, which supports SPARQL, has query language extensions that allow more expressive queries (e.g. path), while still querying over RDF statements. $\endgroup$
    – Erik Eidt
    Feb 2, 2013 at 21:28
  • 2
    $\begingroup$ If it doesn't have fixed point operators, then there should be a problem in P that can be expressed as a single SPARQL query. $\endgroup$ Feb 3, 2013 at 8:01
  • 2
    $\begingroup$ SPARQL 1.0 cannot express transitive closure, e.g. thefigtrees.net/lee/sw/sparql-faq#transitive which is your first problem. $\endgroup$ Feb 4, 2013 at 16:59
  • 2
    $\begingroup$ @AbrahamDFlaxman: I am not sure I fully understand what you mean by k nearest neighbours, but a Hanf locality argument seems to apply there. From the paper I cited: "In essence, Hanf's theorem states that two structures cannot be distinguished by sentences of quantifier rank k whenever they realize the same multiset of d-neighborhoods of points; here d depends only on k." $\endgroup$ Feb 4, 2013 at 19:27

1 Answer 1


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.

  • 1
    $\begingroup$ ah so my (crude) intuition was on the right track. Excellent !! $\endgroup$ Feb 4, 2013 at 19:13
  • $\begingroup$ SQL language admits the transitive closure since the 1999 version of the standard... $\endgroup$
    – SQLpro
    Feb 6 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.