W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > July to September 2010

Re: Signalling entailment in queries

From: Chimezie Ogbuji <ogbujic@ccf.org>
Date: Wed, 21 Jul 2010 09:27:39 -0400
To: "Steve Harris" <steve.harris@garlik.com>, "Sandro Hawke" <sandro@w3.org>
cc: "SPARQL Working Group" <public-rdf-dawg@w3.org>
Message-ID: <C86C6E0B.1285A%ogbujic@ccf.org>
On 7/21/10 5:04 AM, "Steve Harris" <steve.harris@garlik.com> wrote:
> I'm not sure I follow what this approach does.

We have URIs that identify entailment regimes, which determine additional
answers beyond basic graph pattern matching.  We have a way for the server
to indicate the entailment regime used for basic graph pattern matching
(available within a service description), but we don't have a way for the
end user to indicate an entailment regime that the server should use when
answering the given query.  The general idea here (there are some
differences in the details) is to provide a way for this to be indicated in
the query. 

> What about the case where the service just runs all the triples through a
> reasoner (Pellet etc.) and then imports the output? Would everything then be
> regarded as ground facts?

I'm not quite sure I understand your scenario, but assuming you mean that
the triple store does this prior to answering the query, then yes.   If you
meant this to be the way that the service implements the answering of a
query in the face of an entailment regime, then it is an implementation
detail of *one* way to provide additional answers.

> Or would you still want to distinguish between step
> 0. ground facts, and the inferred, but also now ground ones?

If, the output of a reasoning process constitutes the SG to begin with
(i.e., this happens before the query), there is no distinguishing necessary
because basic graph pattern matching alone will give you the answers
appropriate for the entailment used by the reasoner.  Even if the steps you
describe are done *during* the answering of the query, there is no need to
distinguish between these steps (which is a procedural interpretation of
entailment), all the service is required to do is give the proper answers.

Let me try with an example.

Lets say you have the following data:

## <G1> ##

:Bobby       :hasFather :Cletus
:Cletus      :hasFather :BillyJo
:hasFather   rdfs:subPropertyOf :hasAncestor
:hasAncestor a owl:TransitiveProperty

And the following query:

SELECT ?PERSON ?ANCESTOR {?PERSON :hasAncestor ?ANCESTOR}

If a reasoner was used to calculate the 'closure' graph a priori via OWL2 DL
or OWL 2 RL entailment, then you would have:

## <G1Closure> ##

:Bobby       :hasFather         :Cletus
:Bobby       :hasAncestor       :Cletus
:Bobby       :hasAncestor       :BillyJo
:Cletus      :hasFather         :BillyJo
:Cletus      :hasAncestor       :BillyJo
:hasFather   rdfs:subPropertyOf :hasAncestor
:hasAncestor a owl:TransitiveProperty

Now, if the server uses G1Closure and the query is evaluated against this as
the SG using basic graph pattern matching, then the (proper) answer is
returned:

?PERSON | ?ANCESTOR
___________________
:Bobby  | :Cletus
:Bobby  | :BillyJo
:Cletus | :BillyJo

Now if <G1> is the SG instead, and the relevant entailment regime (either
specified in the SD or by the query) is OWL 2 DL or OWL 2 RL, the server is
only required to provide the 'proper' answers and this can be done in at
least two ways:

# bottom-up / forward-chaining #

In which rules / axioms are applied in a forward fashion until termination
and <G1Closure> derived.  Then, basic graph pattern matching is applied
against this graph.

# top-down-driven query re-writing #

In which queries are re-written, dispatched (against <G1>), and the answers
are combined appropriately to give the proper top-level answers:

SELECT ?PERSON ?ANCESTOR {?PERSON :hasAncestor ?ANCESTOR}

-- re-written to --

SELECT ?PERSON ?ANCESTOR {?PERSON :hasFather ?ANCESTOR}

-- evaluated against G1 --

?PERSON | ?ANCESTOR
___________________
:Bobby  | :Cletus     [1]
:Cletus | :BillyJo    [2]

For [1], a follow-up query is dispatched (using the given bindings):

SELECT ?PERSON ?ANCESTOR { :Cletus :hasFather ?ANCESTOR  }

-- evaluated against G1 --

?PERSON | ?ANCESTOR
___________________
:Bobby  | : BillyJo   [3]

Similarly, for [2]:

SELECT ?PERSON ?ANCESTOR { :BillyJo :hasFather ?ANCESTOR  }

-- evaluated against G1, giving no answers --

The final, top level answers (correct for the indicated entailment regime)
are {1] + [2] + [3]

In this approach, the distinction between the given graph and a
(materialized) entailed graph is irrelevant for determining the proper
answers. 

-- Chime


===================================

P Please consider the environment before printing this e-mail

Cleveland Clinic is ranked one of the top hospitals
in America by U.S.News & World Report (2009).  
Visit us online at http://www.clevelandclinic.org for
a complete listing of our services, staff and
locations.


Confidentiality Note:  This message is intended for use
only by the individual or entity to which it is addressed
and may contain information that is privileged,
confidential, and exempt from disclosure under applicable
law.  If the reader of this message is not the intended
recipient or the employee or agent responsible for
delivering the message to the intended recipient, you are
hereby notified that any dissemination, distribution or
copying of this communication is strictly prohibited.  If
you have received this communication in error,  please
contact the sender immediately and destroy the material in
its entirety, whether electronic or hard copy.  Thank you.
Received on Wednesday, 21 July 2010 13:33:04 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:43 GMT