# Re: First order logic and SPARQL

From: Juan Sequeda <juanfederico@gmail.com>
Date: Fri, 3 Sep 2010 16:40:05 -0500
Message-ID: <AANLkTinA38QsVtMP-qFiDF3b_ftt2fT7KoC=H4U-BubB@mail.gmail.com>
To: Jitao Yang <jitao.yang@gmail.com>

```Quick answer

"SPARQL and non-recursive safe Datalog with negation have equivalent
expressive power, and hence, by classical results, SPARQL is equivalent from
an expressiveness point of view to Relational Algebra"

Angles and Gutierrez. The Expressive Power of SPARQL

Juan Sequeda
+1-575-SEQ-UEDA
www.juansequeda.com

On Fri, Sep 3, 2010 at 3:30 PM, Jitao Yang <jitao.yang@gmail.com> wrote:

> Dear all,
>
> Do you know if we can find the some connections between First order logic
> and SPARQL?
>
> SUCH AS, for the First order logic QUERY: DescPr(x, author,y) AND DescPr(y,
> country,'IT'),
> (DescPr(x, author,y) means that x's author is y)
> we can map it to SPARQL like:
>
> PREFIX dc: ...
>
> SELECT ?x
> WHERE {
>                  ?x, dc:author,?y .
>                  ?y, dc:country,'IT' .
> }
>
> It means that for this query we can map the 'AND' in First order logic to
> the 'AND' in SPARQL.
>
> However, if *we want to QUERY the books whose authors are ALL from ITALY.*
>
> 1/ we can express it using First order logic like:
> *(note that: E* means Existential, *U* means Universal,
> DescCl(x, book) means that x is an instance of CLASS book)
>
> *(E* x) DescCl(x, book) AND (*U* y)(DescCl(y, author)) AND DescPr(x,
> author, y)
> --> DescPr(y, country, 'IT')
>
> 2/ we can use SPARQL like:
>
> PREFIX dc: ...
> PREFIX vcard: ...
>
> SELECT ?bookName
> WHERE {
>                 ?x     vcard:fullname    ?bookName .
>                 OPTIONAL{
>                                    ?x      dc:author      ?y .
>                                    ?y      dc:country     ?z .
>                                    FILTER (?z != "IT") .
>                  }
>                  FILTER(!bound(?y)) .
> }
>
>
> But, it seems that it is difficult to translate 1/ into 2/,
> such as how to translate Existential in First order logic to SPARQL
> expressions,
> what kinds of expressions in First order logic should be translated to
> SPARQL using OPTIONAL, FILTER and so on...
>
> Do you have any suggestions on the above problems?
>
> Thank you!
> Jitao
>
>
>
>
>
>
>
>
```
Received on Friday, 3 September 2010 21:40:59 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 1 March 2016 07:42:22 UTC