3
$\begingroup$

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?

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ Are we supposed to know what this “SPARQL query language” is? $\endgroup$
    – Tsuyoshi Ito
    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$
    – Suresh Venkat
    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$
    – András Salamon
    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$
    – András Salamon
    Feb 4, 2013 at 19:27

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ ah so my (crude) intuition was on the right track. Excellent !! $\endgroup$
    – Suresh Venkat
    Feb 4, 2013 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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