Re: Blank nodes in OWL DL, resend

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 10:28:11 UTC