Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Are we supposed to know what this “SPARQL query language” is? – Tsuyoshi Ito Feb 2 '13 at 1:10
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. – Erik Eidt Feb 2 '13 at 21:28
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. – Suresh Venkat Feb 3 '13 at 8:01
SPARQL 1.0 cannot express transitive closure, e.g. which is your first problem. – András Salamon Feb 4 '13 at 16:59
@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." – András Salamon Feb 4 '13 at 19:27
up vote 4 down vote accepted

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.

share|cite|improve this answer
ah so my (crude) intuition was on the right track. Excellent !! – Suresh Venkat Feb 4 '13 at 19:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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