Blank nodes in OWL DL, resend

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 Thursday, 8 May 2003 08:24:23 UTC