W3C home > Mailing lists > Public > www-webont-wg@w3.org > March 2003

5.26 OWL DL Syntax - Formal Objection

From: Jeremy Carroll <jjc@hpl.hp.com>
Date: Fri, 28 Mar 2003 10:51:11 +0100
To: www-webont-wg@w3.org
Message-Id: <200303281051.11827.jjc@hpl.hp.com>


This objection is based on the unnecessary implementation difficulty for OWL 
DL systems (particularly OWL Syntax Checkers) resulting from the omission of 
parts B.1 and B.2 from the resolution of this issue; and the resulting lack 
of clear exposition in the Semantics and Abstract Syntax Draft of what 
implementors need to do.

This objection does not concern either OWL Lite or OWL Full, and only impacts 
OWL DL ontologies making use of the EquivalentClasses or DisjointClasses 
constructs to compare descriptions. (i.e. the owl:equivalentClass and 
owl:disjointWith properties between blank nodes).


0. Summary
==========
The resolution of this issue results in:
- a recommendation that does not adequately inform implementors what they 
need to do
And for the two identified features of OWL DL
- is unnecessarily difficult to implement correctly
- will often be implemented incorrectly 
- may result in interoperability failures between implementations

1. Background
=============
I raised the OWL DL Syntax issue [2] with the goal of making it possible to 
both articulate and implement systems that can recognise which RDF graphs 
correspond to OWL DL abstract ontologies.
This ability is fundamental to the operation of OWL DL, since it is part of 
the link between Web documents in OWL and their meaning as specified in 
section 3 of the Semantics and Abstract Syntax WD [3].
The resolution [4] of the issue without B.1 and B.2, is a significant 
improvement on the earlier WDs (such as [5]).
However, the omission of parts B.1 and B.2 leaves a significant hole 
concerning the abstract syntax constructs DisjointClasses and 
EquivalentClasses and their RDF/XML equivalents: triples with predicate 
owl:disjointWith and owl:equivalentClass.
Also, the resolution meant that the alternative characterisation of OWL Lite 
and OWL DL graphs [1], without reference to the mapping rules, became too 
difficult to articulate correctly.

2. Example of problem
=====================

2.1 EquivalentClasses
=====================
Given an OWL DL document (namespaces omitted) such as:

<rdf:RDF>

<!-- definitions of descriptions and/or restrictions -->
   <owl:Class rdf:nodeID="a">
     <owl:unionOf rdf:parseType="Collection">
        <owl:Class rdf:ID="A"/>
     </owl:unionOf>
   </owl:Class>

   <owl:Class rdf:nodeID="b">
     <owl:unionOf rdf:parseType="Collection">
        <owl:Class rdf:ID="B"/>
     </owl:unionOf>
   </owl:Class>

   <owl:Class rdf:nodeID="c">
     <owl:unionOf rdf:parseType="Collection">
        <owl:Class rdf:ID="C"/>
     </owl:unionOf>
   </owl:Class>

<!-- equivalent and disjoint classes -->
   <owl:Class rdf:nodeID="a">
     <owl:equivalentClass rdf:nodeID="b"/>
   </owl:Class>

   <owl:Class rdf:nodeID="b">
     <owl:equivalentClass rdf:nodeID="c"/>
   </owl:Class>

</rdf:RDF>

An implementation has to run the mapping rules [6] in reverse to find the 
abstract form:

EquivalentClasses( unionOf( <A> )
                    unionOf( <B> )
                    unionOf( <C> ) )

This is made decidedly difficult when subtly different variants of the 
RDF/XML cannot be subject to such a reverse mapping.
For example the following is not in OWL DL, according to the last call 
candidate, but is, in fact, in OWL Full:

<rdf:RDF>

<!-- definitions of descriptions and/or restrictions -->
as above
<!-- equivalent and disjoint classes -->
   <owl:Class rdf:nodeID="a">
     <owl:equivalentClass rdf:nodeID="b"/>
   </owl:Class>

   <owl:Class rdf:nodeID="a">
     <owl:equivalentClass rdf:nodeID="c"/>
   </owl:Class>

</rdf:RDF>

However, in OWL Full it has exactly the same meaning as the original document.

2.2 DisjointClasses
===================

Correct treatment of the DisjointClasses construct involves checking that 
the owl:disjointWith triples form non-overlapping cliques with sufficient 
crosslinks between them. e.g.


<rdf:RDF>

<!-- definitions of descriptions and/or restrictions -->
as above
<!-- equivalent and disjoint classes -->
   <owl:Class rdf:nodeID="a">
     <owl:disjointWith rdf:nodeID="b"/>
   </owl:Class>

   <owl:Class rdf:nodeID="a">
     <owl:disjointWith rdf:nodeID="c"/>
   </owl:Class>

   <owl:Class rdf:nodeID="b">
     <owl:disjointWith rdf:nodeID="c"/>
   </owl:Class>

</rdf:RDF>

Can be mapped in reverse to

DisjointClasses( unionOf( <A> )
                    unionOf( <B> )
                    unionOf( <C> ) )

Because the last three parts of the RDF/XML form a complete (undirected) 
graph K3 over the nodes _:a, _:b and _:c.

The related


<rdf:RDF>

<!-- definitions of descriptions and/or restrictions -->
as above
<!-- equivalent and disjoint classes -->
   <owl:Class rdf:nodeID="a">
     <owl:disjointWith rdf:nodeID="b"/>
   </owl:Class>

   <owl:Class rdf:nodeID="a">
     <owl:disjointWith rdf:nodeID="c"/>
   </owl:Class>

</rdf:RDF>

Does not have any such inverse mapping, and is hence not in OWL DL, but in 
OWL Full - however, it's meaning in OWL Full is the same as documents 
corresponding to the abstract syntax form:

DisjointClasses( unionOf( <A> )
                    unionOf( <B> ) )
DisjointClasses( unionOf( <A> )
                    unionOf( <C> ) )

More complicated examples involving say two cliques of four and three 
description nodes could be formed - if there are seven distinct nodes then 
the example is in OWL DL, if any of the nodes is shared between the two 
cliques then the example is in OWL Full, but its meaning is unchanged.


3. Articulation of the RDF graphs in OWL DL
===========================================

Earlier working drafts had text [8] trying to articulate which RDF graphs 
are in OWL DL, in a fashion that did not rely on running the mapping rules 
backwards. This text did not attempt to articulate the constraints on 
owl:disjointWith and owl:equivalentClass (was known as owl:sameClassAs).

I proposed a clearer and more correct articulation such as [1] allowing 
implementors a view of OWL DL that does not require understanding a complex 
inverse mapping, however this text relies on the mapping rules being 
sufficiently regular. B.1, B.2 was the WGs favorite approach to making these 
two mapping rules more regular.

It would be possible to augment [1] with extra text describing the results of 
these two mapping rules in graph theoretic terms - roughly that 
owl:disjointWith should color subgraphs that are cliques, and 
owl:equivalentClass should color subgraphs that have directed Hamiltonian 
paths (does that mean that OWL DL Syntax is NP complete?)

4. Proposed solution
===================

This is articulated in [4] parts B.1 and B.2 and was made at the technical 
plenary in Cambridge in March 2003, by Patel-Schneider.
This removes the irregularities by allowing fairly arbitrary sharing of the 
bnodes involved.
The constraints on bnode structures are then as in [1].
All the examples in this message are then in OWL DL.

5. Pros and Cons of Proposed Solution
=====================================
The group has rejected this solution because of agreed potential 
technical difficulties with an important proof [9]. While the desire for 
proven correctness is important, my judgement is that, in the absence of 
such a proof, the risk of many incorrect implementations resulting in a lack 
of interoperability (with the WG's resolution) should be given priority over 
the very slight risk that there is a technical error making the proposed 
solution unsound. (Incorrect implementations would suffer this risk of 
unsoundness in any case).

I fully agree with the WG judgement that there is significant techical 
difficulty with the proof of the soundness of the B.1, B.2 proposal. The 
disagreement is about balance of risks rather than technical substance. 

6. Implementation report
===================
An implementation report that showed that this part of the spec is correctly 
implemented by many, and incorrectly implemented by few would go a long way 
to addressing this concern.

References
==========

[1] OWL DL as triples (my proposal)
http://lists.w3.org/Archives/Public/www-archive/2003Mar/att-0089/m
[2] Issue raising message
http://lists.w3.org/Archives/Public/www-webont-wg/2003Jan/0489.html
[3] OWL Direct Semantics
http://www.w3.org/TR/owl-semantics/direct.html
[4] Initial proposal to close
http://lists.w3.org/Archives/Public/www-webont-wg/2003Mar/0066.html
[5] Earlier WD
http://www.w3.org/TR/2003/WD-owl-semantics-20030203/
[6] unused?
http://www.w3.org/TR/owl-semantics/mapping.html#4.1
[7] unused?
http://www.w3.org/TR/owl-semantics/rdfs.html#5
[8] Earlier description of OWL DL as RDF graph
http://www.w3.org/TR/2003/WD-owl-semantics-20030203/mapping.html#4.2
[9] Proof that is difficult to fix
http://www.w3.org/TR/owl-semantics/proofs.html#A.1
Received on Friday, 28 March 2003 04:50:36 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:57:58 GMT