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

AS+S Comments: [was Re: Blank nodes in OWL DL, resend]

From: Brian McBride <bwm@hplb.hpl.hp.com>
Date: Fri, 09 May 2003 11:26:39 +0100
Message-Id: <5.1.0.14.0.20030509100603.03972e00@localhost>
To: Jeremy Carroll <jjc@hplb.hpl.hp.com>, w3c-rdfcore-wg@w3.org

Wow, this is pretty hairy stuff.  I agree with Graham about interfering in 
another WG's design.

I found it pretty hard to separate out what you are proposing RDFCore say 
to webont.  Only the summary at the end looks appropriate.  I also found 
some surprises in these, e.g. the restrictions on b-nodes, so I'm 
suggesting in another message adding a further general comment.

I suggest the following amendments:

------------------------------

owlsas-rdfcore-np-complete

RDFCore notes the a consequence of the rules for owl:equivalentClass is 
that distinguishing OWL DL from OWL Full has complexity NP complete and 
suggests WEBONT investigate whether this complexity can be reduced.

-------------------------------

owlsas-rdfcore-rules-complexity

The rules concerning blank nodes and triples labelled with owl:disjointWith 
and owl:equivalentClass are complicated and difficult to 
understand.  RDFCore suggests WEBONT consider whether a clearer exposition 
of these rules is possible.  This would help implementors, for example, 
when building an OWL DL recognizer.

-------------------------------

owlsas-rdfcore-bnodes-restrictions

RDFCore are concerned that restrictions placed on b-nodes will limit the 
applicability of OWL DL to an unecessarily restricted subset of RDF 
instance data, for which no such restrictions apply.  Specifically we 
request, that in Owl DL and Owl lite:

  a) that a b-node representing an individual may be the object of more 
than one triple
  b) that cycles of b-nodes representing individuals be allowed.

-------------------------------

Brian



>- It is a mistake that owl:equivalentClass rules
>   make OWL DL recognition an NP complete problem.
>   This should be fixed.

Softened this - I'm not sure we know enough to say that its a 
mistake.  Anyway, as I understand this, this is helpful comment as WEBONT 
already have a fix and just need a comment to hang it on to.

>- 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.

I'm not sure this is a matter for RDFCore.  This is an aspect of the design 
of Owl DL.  I don't understand the bit about articulate.  Are these rules 
not implied in the spec?  I guess you mean they are, but they should be 
spelled out more clearly.  That's what I've written above.

>- 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.

This seems like an internal matter for Owl.  Why does RDFCore care about this?

>- 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.

Its not clear to me that RDFCore understand the issues well enough to say 
that its a mistake.  We can say we don't like it.



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
>
Received on Friday, 9 May 2003 06:34:01 EDT

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