Re: example SQL mapping to direct graph

On Wed, Jan 19, 2011 at 7:30 PM, Lee Feigenbaum <> wrote:
> On 1/19/2011 5:07 PM, Alexandre Bertails wrote:
>> Hi Lee,
>> On Wed, 2011-01-19 at 13:40 -0500, Lee Feigenbaum wrote:
>>> On 1/19/2011 11:43 AM, David McNeil wrote:
>>>> On Wed, Jan 19, 2011 at 10:29 AM, Eric Prud'hommeaux<
>>>> <>>  wrote:
>>>>     At the end of 2006, Fred Zemke interceded to keep the
>>>>     SPARQL semantics from having ambiguous cardinality, which cost
>>>> months
>>>>     but gave us invaluable definition in the semantics.
>>>> Eric - Can you elaborate on this and/or provide a link to what you are
>>>> referring to? In particular I am trying to understand the cardinality
>>>> semantics defined by SPARQL.
>>> The SPARQL algebra operates over multisets of solutions, and the algebra
>>> operations all define how they affect the cardinality of the solutions.
>>> To take a very simple example:
>>> {
>>>    ?s :p :o
>>> } UNION {
>>>    ?s :p :o
>>> }
>>> against the data:
>>> :s :p :o .
>>> Results in this solution (multi)set:
>>> ?s
>>> --
>>> :s
>>> :s
>>> In the absence of the DISTINCT or REDUCED keywords, any compliant SPARQL
>>> implementation must give you 2 copies of the ?s=:s solution in response
>>> to this query.
>> Does it mean that SPARQL cannot be implemented using Datalog? If I
>> understand well, there will be no way to be correct against the
>> semantics as Datalog relies on sets.
> Hi Alexandre,
> I'm not at all familiar with datalog, but if it's not capable of returning
> duplicate solutions to a query, then yes, it's not capable of implementing
> SPARQL in a fully compliant manner.
> lee

Hi Lee, Alexandre,

There are some simple versions of datalog that can deal with duplicate
solutions. For example, some of the key contributions about optimizing
conjunctive queries over databases with duplicates were done by
considering a version of datalog that can deal with duplicate tuples:

S. Chaudhuri, M. Y. Vardi: Optimization of Real Conjunctive Queries.
PODS 1993: 59-70

This version of datalog associates to each tuple an annotation that
corresponds to the multiplicity of the tuple in the database. This
annotation function corresponds to the function card in the definition
of the semantics of SPARQL in:

E. Prud'hommeaux, A. Seaborne: SPARQL Query Language for RDF. W3C
Recommendation 15 January 2008.

Hence, SPARQL can be implemented by using this version of datalog
(with safe negation).

We will use this version of datalog to solve the problems in the
datalog specification of the direct mapping (thank you very much for
all your comments about this).

All the best,


Received on Thursday, 20 January 2011 01:03:29 UTC