Re: Reflexivity and antisymmetry uses cases?

On 17 Jan 2007, at 17:53, Shepherd, Michael wrote:

>
> Alan states: "Performance can be scary because of the constraint that
> solutions be complete. I think there ought to be more effort to  
> develop
> algorithms that trade completeness for speed - I have seen at least  
> one
> already."
>
> Regarding commercial activities which are learning to use the Semantic
> Web technologies, this is a very important point to us.  Even though I
> can deploy a useful knowledge-base and reasoner to the field for a
> particular application, if I cannot guarantee the reasoner will run in
> polynomial time, variation in the field could cause the A-box to get
> sufficiently large to render my application useless.
>
> I agree with Alan's assertion that performance can be scary, so  
> much so,
> that we cannot deploy the technology in our products.  There is
> reference to algorithm(s) which emphasize completeness.  Does this  
> also
> include execution in polynomial time?  Are these algorithms available
> publicly/commercially?
>
> Also, is it possible to analyze a knowledge-base to know that the
> reasoning will occur in polynomial time?  What type of logic  
> assertions
> and individuals can cause reasoning in exponential time?

If you check out the Tractable Fragments document from the OWL 1.1  
submission (http://owl1-1.cs.manchester.ac.uk/tractable.html) you  
will see that it describes a number of fragments for which tractable  
reasoning is possible. For some of these, implementations are already  
available (see, e.g., CEL http://lat.inf.tu-dresden.de/systems/cel/).  
Obviously, if an OWL ontology happens to fall within one of these  
fragments, then the relevant performance guarantee is possible.

Unfortunately, while incredibly useful, worst case complexity  
analysis is still a relatively coarse grained tool, and doesn't tell  
us anything about the likely behaviour of reasoners on KBs that use a  
potentially problematic combination of constructors, but in an  
"apparently harmless" way - in fact it is interesting to note that  
most implemented algorithms actually have much higher worst case  
complexities than the known worst case for the underlying problem. On  
the other hand, we do have a reasonably good (empirical and  
theoretical) understanding of what constitutes a "dangerous" KB -  
i.e., one for which reasoning is likely to be hard (we know, e.g.,  
that problems almost invariably arise when GCIs cannot be fully  
absorbed, or when the KB is not very "modular"); there is no reason  
why tools could not include this kind of analysis (recent work by  
Cuenca Grau and Kazakov on provides, e.g., a very nice way to  
determine how "modular" a KB is) and so at least warn users as/when  
their KB became "dangerous" - in fact I expect this sort of  
functionality to be added to tools in the near future.

Regards,

Ian



>
> Thanks,
> Mike
>
> -----Original Message-----
> From: public-owl-dev-request@w3.org
> [mailto:public-owl-dev-request@w3.org] On Behalf Of Alan Ruttenberg
> Sent: Tuesday, January 16, 2007 11:45 PM
> To: Holger Knublauch
> Cc: public-owl-dev@w3.org
> Subject: Re: Reflexivity and antisymmetry uses cases?
>
>
> Data point: I asked for antisymmetry to better support part-of
> relations. My own goal was to have the extra information act as a
> constraint so that inconsistencies would occur if  there were errors,
> as my experience is that life sciences data is plagued by
> inconsistencies and OWL could really help clean things up.
>
> QCRs were another one that I asked for (among many other people). I
> have two use cases for them: 1 being the work I've done with Jeremy
> Zucker, tutored by folks at Manchester, in representing chemical
> reactions so that multiple metabolic databases with the same
> reactions can be merged with same reactions being computed to be
> equivalent. Another recent use for them is for the ACPP group which
> is part of the HCLSIG, where they wish to represent diagnoses of the
> form : if you have 4 of these 6 symptoms, then you might have a  
> disease.
>
> Neither of these features, I believe, represent recent advances in DL
> research, but then, I'm not an expert.
>
> The features that do, I believe, represent relatively recent advances
> are the property chains and the datatype extensions. I believe that
> these features are well motivated. The property chains are modeled
> (at least) on the transfersThrough relationship from CYC, which I
> learned more than 15 years ago. It allows one to state useful things
> like if you own a car, then you own the parts of a car. Although I
> haven't experimented with this yet, I also believe it should make the
> use of reified properties more effective.
>
> I suspect it wouldn't be too hard to find many use cases for the
> datatype extensions either. I've certainly read papers that have used
> them - in fact I'd argue that one should expose the full datatype
> extensibility that the current research allows.
>
> Although I initially had questions about whether punning was a good
> idea, I am convinced that the experience gained in using them will be
> useful and contribute to further development of OWL. Of course the
> main thing they bring is the ability to annotate classes with more
> structured properties than was previously possible. Not having the
> ability to do that has long been a complaint. Still, here, I believe,
> there is more potential for confusion than in the other areas.
>
> I will offer some reasons that I consider to be the cause of
> difficulties around OWL.
>
> 1) Lack of simple textual formats for using OWL, and the lack of a
> syntax extension mechanism. There is already buy in on the need for
> simpler syntaxes, and I expect that syntax extension will be a topic
> discussed at OWLED and in the working group.
>
> 2) Need for better education and educational materials. Many more
> realistic worked examples. Knowledge representation is hard. OWL is a
> way to do a hard thing. It's not that surprising that OWL is
> consequently hard. But I do think both knowledge representation and
> OWL can be taught.
>
> 3) A certain skirting around the issue of how RDF and OWL semantics
> differ from the usual database view of the world. Domain and Range
> are a constant source of confusion. Open world assumptions also
> makes, e.g. cardinality restrictions, not behave the way one would
> expect them to. I think the choice of open world assumption is well
> motivated, but we do need some ability to do closed-world reasoning
> such as constraint checking, and from a messaging point of view a
> more head-on approach to discussing  how and why both OWL and RDF
> differ from databases.
>
> 4) Performance can be scary because of the constraint that solutions
> be complete. I think there ought to be more effort to develop
> algorithms that trade completeness for speed - I have seen at least
> one already. The tractable subsets defined in the current OWL 1.1
> also address the performance issue, though I think more subsets can
> be enumerated and simple algorithms for implementing reasoners for
> them can be make more accessible.
>
> Personally, I think that the line of thinking that says "OWL is too
> complicated, lets slow development of it down" is misplaced. Rather I
> think there is an under appreciation of the level of educational
> effort is required to move the concepts it deals with into the
> mainstream, and the need to plan for greater educational efforts.  I
> see the effort as a large constant, only incrementally added to by
> new features being added to the language. On the other hand, people
> who are experienced in using OWL generally want either more features
> or better performance. That constituency is the seed that will
> generate new use cases, applications, and teach others how to do so.
> I don't think denying them advances the cause.
>
> -Alan
>
>
> On Jan 16, 2007, at 7:13 PM, Holger Knublauch wrote:
>
>>
>> Thanks for these example use cases.  I have also received another
>> one in a private email, plus the one from Pierluigi.  Makes so far
>> three groups who are interested in this.
>>
>> While I see that a lot of OWL properties could be made irreflexive
>> and antisymmetric, I wonder about what the ontology users would get
>> out of it.  Would they expect to get different inference results,
>> or would the extra information act as constraints to validate user
>> input, or what else?
>>
>> On a more general level, I am a bit concerned that the addition of
>> these extra features may be more driven by theoretical advances in
>> DL reasoners than by real user requirements.  Let's face it, we
>> have a trade-off here if we add more and more features to a
>> language that a lot of people already find much too complex: while
>> some users may argue that they need the additional expressiveness,
>> these additional features also increase the learning curve,
>> implementation overhead, and perception of OWL as a ivory tower
>> language.  During my time in the Protege community and even more so
>> at TopQuadrant, I don't remember anyone asking for reflexivity and
>> antisymmetry.  Maybe the people of this list have more use cases to
>> show?
>>
>> Holger
>>
>>
>> John Goodwin wrote:
>>>> we are looking into the user interface requirements that will be
>>>> needed to support OWL 1.1. Toward this end, we are interested in
>>>> understanding the use cases in support of the various new
>>>> features of OWL 1.1.  I can easily make sense of user-defined
>>>> datatypes and QCRs, but I don't think I had seen a lot of
>>>> examples for some of the other proposed features so far (except
>>>> for toy ontologies):
>>>>
>>>>   - owl:SelfRestriction
>>>>   - owl:IrreflexiveProperty
>>>>   - owl:AntiSymmetricProperty
>>>>
>>>> If you know of a published list of use cases (either formal or
>>>> informal), or if you have your own use case for any of these
>>>> features, I would be interested in seeing them.
>>> Holger,
>>> It is argued that reflexivity is required when modelling
>>> mereology. See
>>> http://www.w3.org/2001/sw/BestPractices/OEP/SimplePartWhole/
>>> index.html
>>> I think these properties of OWL 1.1 could certainly have
>>> applications in
>>> the geospatial domain. For example we might want to say that all
>>> rivers
>>> flow into rivers, seas or lakes but they cannot flow into
>>> themselves. I
>>> guess we could do this as follows:
>>> River -> flowsInto some (River or Sea or Lake) and not flowsInto  
>>> Self
>>> Many topological relationships (for example those of RCC8) would be
>>> irreflexive and antisymmetric. These properties might also be
>>> useful in modelling topology with some
>>> notion of orientation. Properties such as "northOf", "eastOf",
>>> "leftOf",
>>> "above" etc. would be antisymmetric and antisymmetric. As we
>>> experiment more with OWL1.1 I can probably come up with more
>>> examples.
>>> John
>>> Dr John Goodwin
>>> Research Scientist
>>> Research Labs, Ordnance Survey Room C530, Romsey Road,
>>> SOUTHAMPTON, United Kingdom, SO16 4GU Phone: +44 (0) 23 8030 5756
>>> | Mobile: +44 (0) 7xxx xxxxxx | Fax: +44 (0)
>>> 23 8030 5072 www.ordnancesurvey.co.uk |
>>> john.goodwin@ordnancesurvey.co.uk Please consider your
>>> environmental responsibility before printing this
>>> email. .
>>> This email is only intended for the person to whom it is addressed
>>> and may contain confidential information. If you have received
>>> this email in error, please notify the sender and delete this
>>> email which must not be copied, distributed or disclosed to any
>>> other person.
>>> Unless stated otherwise, the contents of this email are personal
>>> to the writer and do not represent the official view of Ordnance
>>> Survey. Nor can any contract be formed on Ordnance Survey's behalf
>>> via email. We reserve the right to monitor emails and attachments
>>> without prior notice.
>>> Thank you for your cooperation.
>>> Ordnance Survey
>>> Romsey Road
>>> Southampton SO16 4GU
>>> Tel: 08456 050505
>>> http://www.ordnancesurvey.co.uk
>>
>
>
>
>

Received on Thursday, 18 January 2007 10:41:42 UTC