W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > May 2003

Re: Blank nodes in OWL DL, resend

From: Jeremy Carroll <jjc@hplb.hpl.hp.com>
Date: Thu, 08 May 2003 19:54:35 +0100
Message-ID: <3EBAA7EB.4080005@hplb.hpl.hp.com>
To: Graham Klyne <gk@ninebynine.org>
CC: w3c-rdfcore-wg@w3.org


I had an action to make comments about the blank node structures as part of 
the process of RDF Core review of S&AS.
  (Particularly section 4)


In terms of why I think RDF Core might wish to consider making these 
comments (at the end of the message)

1: Our semantics doc says:
[[
Specifications of such syntactically restricted semantic extensions MUST 
include a specification of their syntactic conditions which are sufficient 
to enable software to distinguish unambiguously those RDF graphs to which 
the extended semantic conditions apply.
]]

2: RDF has taken blank nodes in one direction; OWL DL takes them in a 
different direction - I at least believe this might cause interoperability 
problems between OWL and RDF.

I think all the comments are jsutified by these two motivations.

Jeremy

Graham Klyne wrote:

> I'm a little puzzled what this has to do with the RDFcore WG.  Is there 
> some piece of context I'm missing?
> 
> #g
> -- 
> 
> At 13:23 08/05/2003 +0100, Jeremy Carroll wrote:
> 
> 
>> Here are some comments:
>>
>>
>> (Note this largely duplicates a report I have sent to jena-devel
>> - I took the same action for two groups)
>>
>>
>>
>>
>>
>> Blank Nodes in OWL DL
>> =====================
>>
>>
>> Here is a report on blank nodes with potential review comments.
>>
>>
>> Blank nodes in OWL Lite/DL can be categorized as:
>> - unnamed individuals
>> - unnamed class descriptions (DL only)
>> - unnamed ontologies
>> - data ranges (DL only)
>> - restrictions
>> - all different (highly restricted idiom)
>> - various sorts of lists
>>   - lists of named individuals
>>   - lists of descriptions/restrictions/classIDs
>>   - lists of literal values (DL only)
>>
>>
>> They are subject to a variety of restrictions,
>> i.e. excluding all triples with predicate
>> owl:equivalentClass and owl:disjointWith we have:
>>
>>
>> - no blank node can be the object of more than one triple
>> - no cycles of blank nodes are permitted
>> - lists and data ranges must be the object of at least one triple
>>
>>
>> In OWL DL restriction and description blank nodes and classIDs
>> may participate in subgraphs labelled with owl:equivalentClass
>> and owl:disjointWith. Blank nodes in such graphs may not be
>> the object of any other triples. They may be the object of
>> many triples in such subgraphs, and such subgraphs may contain
>> cycles. However, the subgraph of an OWL DL graph, consisting
>> of the edges labelled with owl:disjointWith, when viewed as
>> an undirected graph, must be the union of complete subgraphs
>> (i.e. in which every node is connected to every other node)
>> where each pair of subgraphs in the union only intersect
>> in classID nodes (i.e. urirefs).
>> The constraints on the subgraph of an OWL DL graph
>> consisting of the edges labelled with owl:equivalentClass
>> is worse, and involves Hamiltonians cycles, and I don't think
>> I can write it down. Recognizing such structures is NP
>> complete.
>> See
>> http://lists.w3.org/Archives/Public/www-webont-wg/2003Apr/0003
>>
>>
>>
>> Two options for simplifying the blank node structures
>> are:
>>
>>
>> A permit description and restriction nodes to be the
>>   object of multiple triples (still forbidding cycles)
>>
>>
>> B permit unnamed individual nodes to be used cyclically
>>   and to be the object of multiple triples.
>>
>>
>>
>> Option A can be achieved by the following addition
>> to the preamble to the mapping rules in section 4.1:
>> [[
>> Bnode identifiers here are local to each transformation.
>> When the construct being transformed matches the *restriction* or
>> *description* productions from the abstract syntax then
>> the bnode may be shared between multiple identical transformations of
>> identical *restriction*s or *description*s.
>> Otherwise the bnode used in each transformation
>> should be unique for each invocation of a transformation rule.
>> ]]
>>
>>
>> This complete simplifies the mess to do with owl:disjointWith
>> and owl:equivalentClass (The rule becomes that cycles of blank
>> nodes must include an edge labelled with owl:disjointWith or
>> owl:equivalentClass)
>>
>>
>> There are technical difficulties in one of the proofs.
>> These difficulties amount to the validity of the following
>> entailment in OWL Full:
>>
>>
>> <owl:Thing rdf:about="eg:a">
>>  <rdf:type>
>>   <owl:Restriction>
>>    <owl:onProperty rdf:about="eg:p"/>
>>    <owl:allValuesFrom>
>>     <owl:Class>
>>      <owl:intersectionOf rdf:parseType="Collection">
>>       <owl:Class rdf:about="eg:C"/>
>>      </owl:intersectionOf>
>>     </owl:Class>
>>    </owl:allValuesFrom>
>>   </owl:Restriction>
>>  </rdf:type>
>> </owl:Thing>
>> <owl:Thing rdf:about="eg:b">
>>  <rdf:type>
>>   <owl:Restriction>
>>    <owl:onProperty rdf:about="eg:p"/>
>>    <owl:allValuesFrom>
>>     <owl:Class>
>>      <owl:intersectionOf rdf:parseType="Collection">
>>       <owl:Class rdf:about="eg:C"/>
>>      </owl:intersectionOf>
>>     </owl:Class>
>>    </owl:allValuesFrom>
>>   </owl:Restriction>
>>  </rdf:type>
>> </owl:Thing>
>>
>>
>> OWL Full entails
>>
>>
>> <owl:Thing rdf:about="eg:a">
>>  <rdf:type>
>>   <owl:Restriction rdf:nodeID="a">
>>    <owl:onProperty rdf:about="eg:p"/>
>>    <owl:allValuesFrom>
>>     <owl:Class>
>>      <owl:intersectionOf rdf:parseType="Collection">
>>       <owl:Class rdf:about="eg:C"/>
>>      </owl:intersectionOf>
>>     </owl:Class>
>>    </owl:allValuesFrom>
>>   </owl:Restriction>
>>  </rdf:type>
>> </owl:Thing>
>> <owl:Thing rdf:about="eg:b">
>>  <rdf:type>
>>   <owl:Restriction rdf:nodeID="a"/>
>>  </rdf:type>
>> </owl:Thing>
>>
>>
>>
>> The inverse entailment is trivial.
>> (The pattern is a complex description used
>> twice - the premises have two different unnamed
>> instances of the complex description, the conclusions
>> have a single unnamed instance)
>>
>>
>> If this entailment holds (in general), then the suggested change is
>> correct, and a (significant) improvement. If the entailment is not
>> true in general then the OWL Test Cases should include one
>> of the examples of a non-entailment.
>>
>>
>> (Triples with object being a blank description or restriction node
>> must have property:
>>   owl:equivalentClass
>>   owl:disjointWith
>>   rdfs:subClassOf
>>   rdf:type
>>   owl:someValuesFrom
>>   owl:allValuesFrom
>>   rdf:first (in a list of description, which
>>   is then used in an owl:unionOf or owl:intersectionOf triple)
>>
>>
>>
>> Option B
>> concerning unnamed individuals could be achieved by
>> having a semantics for OWL DL which treated blank nodes
>> as existentially quantified names, like in the RDF semantics.
>> Then locally scoped identifiers would be included in
>> the OWL abtstract syntax, and could be used to
>> construct abstract syntax trees that map onto cyclic
>> RDF graphs e.g.
>>
>>
>>
>> individual( locally-scoped-name-A
>>              value( #property locally-scoped-name-A ) )
>>
>>
>> would map onto the triple:
>>
>>
>> _:A <#property> _:A .
>>
>>
>>
>> Comments summary:
>>
>>
>> - It is a mistake that owl:equivalentClass rules
>>   make OWL DL recognition an NP complete problem.
>>   This should be fixed.
>> - The rules concerning blank nodes and
>>   triples labelled with owl:disjointWith and
>>   owl:equivalentClass are very complicated.
>>   S&AS should articulate them. This would help
>>   for example when building an OWL DL recogizer.
>> - Permitting blank nodes representing descriptions
>>   and restrictions to be used as the object of
>>   more than one triple should be considered.
>>   A rationale for not doing so should be given
>>   preferably as a test case in OWL Full showing
>>   an OWL Full non-entailment that would hold in
>>   OWL DL if such a change were made. A sample
>>   test case is included.
>> - RDF Core have found it a mistake to have a
>>   limited syntax for bnodes.
>>   We suggest that permitting cycles of
>>   unnamed individuals, and permitting
>>   unnamed individuals to be the object
>>   of more than one triple would be
>>   advantageous.
>>
>>
>>
>>
>> Jeremy
>>
> 
> -------------------
> Graham Klyne
> <GK@NineByNine.org>
> PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E
> 
Received on Thursday, 8 May 2003 14:54:55 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:57:28 EDT