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

Re: subgraph/entailment

From: Enrico Franconi <franconi@inf.unibz.it>
Date: Tue, 6 Sep 2005 14:53:34 +0200
Message-Id: <4C72EE80-EBA2-4F3E-8FE6-64C6BB77D567@inf.unibz.it>
Cc: RDF Data Access Working Group <public-rdf-dawg@w3.org>
To: andy.seaborne@hp.com

On 6 Sep 2005, at 13:13, Seaborne, Andy wrote:
>> I don't see why we need to maintain in the document the wording   
>> "subgraph of"; we could write "entailed by" and say that the type  
>> of  entailment is decided by the service.
>> Why not?
>
> I am advised, by PatH, that subgraph is sufficient (he did actually  
> draft this definition in rq23).  In previous discussions in the  
> working group, using "entails" just begged the question of what  
> sort of entailment so it left a gap in the definition of SPARQL  
> that was subject to implementation interpretation.

Well, PatH is plain wrong.

Let me re-consider the example I gave in <<http://lists.w3.org/ 
Archives/Public/public-rdf-dawg/2004JulSep/0069>.
Allow me to be sloppy in the syntax.

OWL-Lite ontology, expressed in some RDF-based formalism:
the class WORKER is declared equivalent to the union of the classes  
EMPLOYEE and MANAGER:
WORKER = EMPLOYEE \or MANAGER

RDF data:
Paul rdf:type WORKER
Andrea rdf:type WORKER
Simon rdf:type EMPLOYEE
Caroline rdf:type MANAGER
Paul ns:has-friend Andrea
Paul ns:has-friend Simon
Simon ns:has-friend Andrea
Andrea ns:has-friend Caroline

The query:
Tell me the workers having a friend which is an employee, which in  
turn should have a friend which is a manager.
  q(X) :- worker(X), has-friend(X,Y), employee(Y), has-friend(Y,Z),  
manager(Z).

The answer is the set {Paul}.

There is *no* way to complete the ontology+data in some graph so that  
the answer to the query would come out from that completion (as a  
subgraph), since there is reasoning by cases going on. See my  
original email for a technical explanation. Quoting the conclusion of  
that email:
"The main thing that this simple example shows is that it is  
impossible to find a unique completion (a unique deductive closure)  
over which the query can be evaluated. There are *three* incompatible  
completions, i.e., none of them is minimal (i.e., none of them is  
included in all the others)."

So, if you want to allow SPARQL to handle in the future such (simple)  
cases like this, where you have (simple) RDF-based ontologies  
together with plain RDF data, you have to drop the notion of subgraph  
and resort to entailment. Please note that these cases are already  
well understood, implemented, and tools are available. By limiting  
SPARQL now, we will tell the ontology community to use another query  
language for anything than RDF (and possibly RDFS), while SPARQL  
would be a natural candidate for any RDF-based ontology language  
(like, e.g., OWL-DL).

cheers
--e.

Enrico Franconi                  - franconi@inf.unibz.it
Free University of Bozen-Bolzano - http://www.inf.unibz.it/~franconi/
Faculty of Computer Science      - Phone: (+39) 0471-016-120
I-39100 Bozen-Bolzano BZ, Italy  - Fax:   (+39) 0471-016-129
Received on Tuesday, 6 September 2005 12:54:15 GMT

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