<p>From page 52 of Leonid Libkin's <em>Elements of Finite Model Theory</em> textbook:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

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

<ul>
<li>Leonid Libkin, <em>Logics capturing local properties</em>, ACM Transactions on Computational Logic <strong>2</strong>, 135–153, 2001.  <a href="http://dx.doi.org/10.1145/371282.371388" rel="noreferrer">doi:10.1145/371282.371388</a></li>
</ul>

<p>which has a brief overview of the history with further references.</p>

CC BY-SA 3.0
2013-02-04T19:13:25.827Z
ah so my (crude) intuition was on the right track. Excellent !!
Suresh Venkat
CC BY-SA 4.0
2024-02-06T20:32:31.143Z
SQL language admits the transitive closure since the 1999 version of the standard...
SQLpro
CC BY-SA 3.0
2013-02-04T17:34:39.807Z
2013-02-04T17:34:39.807Z
András Salamon
<p>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 <a href="https://stackoverflow.com/questions/14388864/finding-shortest-path-with-sparql-query">test (s,t)-connectivity without using Property Paths (but simple with them)</a>.  Also, I suspect that it is not possible to <a href="https://stackoverflow.com/questions/14571546/finding-k-nearest-neighbors-with-sparql-query">list the k nearest neighbors of a list of vectors with a single query</a>.</p>

<p>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?</p>

CC BY-SA 3.0
2013-02-02T01:10:35.353Z
Are we supposed to know what this “SPARQL query language” is?
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-02T06:17:37.620Z
Google for "descriptive complexity".
Kaveh
CC BY-SA 3.0
2013-02-02T07:08:47.667Z
@TsuyoshiIto sorry for getting stuck in my jargon.  SPARQL is defined in [this document](http://www.w3.org/TR/2012/PR-sparql11-query-20121108/) and some theoretical analysis is developed in the paper [Semantics and Complexity of SPARQL](http://users.dcc.uchile.cl/~cgutierr/papers/sparql.pdf)
Abraham D Flaxman
CC BY-SA 3.0
2013-02-02T07:21:55.753Z
@Kaveh I think that this could be a useful direction, but your elaboration could help.  The paper paper I've linked above shows that the decision version of SPARQL query evaluation is PSPACE-complete, for example. Is this relevant to my question?
Abraham D Flaxman
CC BY-SA 3.0
2013-02-02T08:27:49.260Z
Descriptive Complexity categorized the expressive power of a query language. I don't know the expressive power of this particular one, however if the descriptive complexity of it is PSpace it means that it can only express queries that are computable in PSpace and it can express any of those. See the wikipedia page for descriptive complexity.
Kaveh
CC BY-SA 3.0
2013-02-02T08:30:30.113Z
If you change your question and make it more general then more people might be interested in it and it is likely that you will get answers that help you with your problem. For example, in place asking specifically for this particular query language you can ask for general techniques for showing that a particular problem cannot be expressed in a query language.
Kaveh
CC BY-SA 3.0
2013-02-02T21:13:15.250Z
One question is if it can handle fixed point operators. Languages that deal with graphs need to handle things like connectivity, and from descriptive complexity we know that we need a fixed point operator to handle P-time problems.
Suresh Venkat
CC BY-SA 3.0
2013-02-02T21:28:12.980Z
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
CC BY-SA 3.0
2013-02-02T23:33:55.753Z
@ErikEidt I think you are on to something here.  To connect this to an explicit example, I know how to map any instance of (s,t)-connectivity testing to a dataset and query, but what I am after is an implementation of (s,t)-connectivity as a query that works for any dataset.
Abraham D Flaxman
CC BY-SA 3.0
2013-02-02T23:39:24.910Z
@SureshVenkat I don't know enough to answer this question about fixed point operators, but I am interested in what can be represented as a single query (maybe that is irrelevant).  Based on [wikipedia's page on fixed point combinators](http://en.wikipedia.org/wiki/Fixed-point_combinator), it seems likely that without property paths SPARQL does not have a fixed point operator.  I don't know how this fits with it being PSPACE-complete...
Abraham D Flaxman
CC BY-SA 3.0
2013-02-03T01:22:51.823Z
Yeah, logic and query languages go hand in hand but not necessarily 1-1, as Jena and other examples show that you can upgrade the expressiveness of the query language for the same statement logic.  What I've seen of complexity theory doesn't tease these apart, or perhaps put another way, focuses on the expressiveness of a system's logic statements, over it's query capabilities.
Erik Eidt
CC BY-SA 3.0
2013-02-03T08:01:45.037Z
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
CC BY-SA 3.0
2013-02-04T16:59:02.340Z
SPARQL 1.0 cannot express transitive closure, e.g. http://thefigtrees.net/lee/sw/sparql-faq#transitive which is your first problem.
András Salamon
CC BY-SA 3.0
2013-02-04T19:02:10.677Z
@AndrásSalamon Thank you, this is exactly the sort of thing I am looking for.  For the k-NN of a list, I believe that transitive closure is not necessary, but SPARQL is still not capable of representing the query.  Do you know of methods relevant to this case?
Abraham D Flaxman
CC BY-SA 3.0
2013-02-04T19:27:24.580Z
@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
<complexity-classes><db.databases>
How do you argue a query is impossible in a query language like SPARQL or SQL?
Abraham D Flaxman
# How do you argue a query is impossible in a query language like SPARQL or SQL?

(Asked by: username_0 on 2013-02-02)

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)](https://stackoverflow.com/questions/14388864/finding-shortest-path-with-sparql-query). Also, I suspect that it is not possible to [list the k nearest neighbors of a list of vectors with a single query](https://stackoverflow.com/questions/14571546/finding-k-nearest-neighbors-with-sparql-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?

**Tags:** complexity-classes, db.databases
> **Comments:**
> **username_1**: Are we supposed to know what this “SPARQL query language” is?  
> **username_2**: Google for "descriptive complexity".  
> **username_0**: @TsuyoshiIto sorry for getting stuck in my jargon.  SPARQL is defined in [this document](http://www.w3.org/TR/2012/PR-sparql11-query-20121108/) and some theoretical analysis is developed in the paper [Semantics and Complexity of SPARQL](http://users.dcc.uchile.cl/~cgutierr/papers/sparql.pdf)  
> **username_0**: @Kaveh I think that this could be a useful direction, but your elaboration could help.  The paper paper I've linked above shows that the decision version of SPARQL query evaluation is PSPACE-complete, for example. Is this relevant to my question?  
> **username_2**: Descriptive Complexity categorized the expressive power of a query language. I don't know the expressive power of this particular one, however if the descriptive complexity of it is PSpace it means that it can only express queries that are computable in PSpace and it can express any of those. See the wikipedia page for descriptive complexity.  
> **username_2**: If you change your question and make it more general then more people might be interested in it and it is likely that you will get answers that help you with your problem. For example, in place asking specifically for this particular query language you can ask for general techniques for showing that a particular problem cannot be expressed in a query language.  
> **username_3**: One question is if it can handle fixed point operators. Languages that deal with graphs need to handle things like connectivity, and from descriptive complexity we know that we need a fixed point operator to handle P-time problems.  
> **username_4**: 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.  
> **username_0**: @ErikEidt I think you are on to something here.  To connect this to an explicit example, I know how to map any instance of (s,t)-connectivity testing to a dataset and query, but what I am after is an implementation of (s,t)-connectivity as a query that works for any dataset.  
> **username_0**: @SureshVenkat I don't know enough to answer this question about fixed point operators, but I am interested in what can be represented as a single query (maybe that is irrelevant).  Based on [wikipedia's page on fixed point combinators](http://en.wikipedia.org/wiki/Fixed-point_combinator), it seems likely that without property paths SPARQL does not have a fixed point operator.  I don't know how this fits with it being PSPACE-complete...  
> **username_4**: Yeah, logic and query languages go hand in hand but not necessarily 1-1, as Jena and other examples show that you can upgrade the expressiveness of the query language for the same statement logic.  What I've seen of complexity theory doesn't tease these apart, or perhaps put another way, focuses on the expressiveness of a system's logic statements, over it's query capabilities.  
> **username_3**: 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.  
> **username_5**: SPARQL 1.0 cannot express transitive closure, e.g. http://thefigtrees.net/lee/sw/sparql-faq#transitive which is your first problem.  
> **username_0**: @AndrásSalamon Thank you, this is exactly the sort of thing I am looking for.  For the k-NN of a list, I believe that transitive closure is not necessary, but SPARQL is still not capable of representing the query.  Do you know of methods relevant to this case?  
> **username_5**: @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."  

---

## 1 answers

### Answer by username_5 on 2013-02-04. Score: 5 | Accepted answer

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](http://dx.doi.org/10.1145/371282.371388)

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

> **Comments:**
> **username_3**: ah so my (crude) intuition was on the right track. Excellent !!  
> **username_6**: SQL language admits the transitive closure since the 1999 version of the standard...  

---

