Re: Cardinality in the open world

On Apr 9, 2005, at 2:20 AM, Paul Gearon wrote:

> I should point out that I'm very grateful for the detailed responses 
> I've been getting.  Thank you Bijan...

You are welcome.

> On 09/04/2005, at 1:54 PM, Bijan Parsia wrote:
>
>> I'm going to presume throughout that we're talking OWL DL. I don't 
>> believe there are any difficulties with transferring it to OWL Full, 
>> but hey.
>
> Actually, I'm not considering OWL DL at all.  At least, I'm trying not 
> to be.  In places where there is a difference I'll be trying to 
> discuss things in terms of OWL Full.

But OWL Full only introduces irrelevant complications, for the purposes 
of current discussion. For example, it really doesn't seem to affect 
anything that OWL Full class expression syntax also has assertional 
force. But it seems to have confused you.

[snip]
>>> Since restrictions are used to describe the class,
>>
>> What class?
>
> The class that the restriction applies to

The restriciton doesn't *apply to* a class. It *is* a class.

More precisely, it's a formula with one free variable. To make an Abox 
assertion, you replace that variable with a logical constant (i.e., a 
name). To make a Tbox axiom, you put it on one side of a conditional, 
where the other side has a formula with the same free variable, and 
universally quantify the whole conditional on that variable.

> .  As in: http://www.w3.org/TR/owl-ref/#Restriction
> "It describes an anonymous class, namely a class of all individuals 
> that satisfy the restriction"

In general, I avoid expository text and stick to normative 
specifications. But, still, clearly this defines the restriction *as* a 
class. It applies *to individuals*.

[snip]
>> So an individual can be of type restirction without an intervening 
>> class definition.
>
> Sorry, I presumed that individuals could not have an anonymous class 
> type.

Even if they didn't, if you set up a definition (i.e., a single 
definition with an atomic class on one side of a biconditional), the 
effect would be the same.

There's not a big logically difference. There's a practical difference 
in that you can separate out the sentences (thereby changing the 
meaning of the type assertion).

>  Now that I have to think about it I realise that I'm wrong.
>
> <snip/>
>> Thus class expressions can be part of abox assertions.
>>
>> Class expressions are also part of tbox expressions. The tbox consist 
>> of definitions and constraints. These are all universally quantified 
>> conditionals.
>
> OK, I'm going to have to take some time to read up and learn exactly 
> where the boundaries lie, so I won't go into it now.

Well, for what it's worth, I've just told you exactly where the 
boundaries lie :) More importantly, the boundaries are insignificant. 
It's not like a C++ class definition or a database schema.

>> ....Ontologies incorporate information about classes, properties, and 
>> individuals"""
>>
>> So, in OWL, the ontology is not the TBox.
>
> ???  I thought that at least some of this was TBox?

So, in OWL, the ontology is not exactly and only the TBox. The TBox and 
ABox distinction is not what distinguishes OWL ontologies from OWL 
"data". In fact, all OWL "data" is found in OWL Ontolgies. OWL 
ontologies can lack TBox axioms altogether. Every (solely) RDF documetn 
is such an OWL ontology.
[snip]
>>>  but I was under the impression that the assertion of this property 
>>> was just the RDF way of expressing a higher order concept.
>>
>> Er....No. OWL is first order all the way. Even owl full.
>
> Oh?  I thought it was 1.5?

I don't know what you are talking about. It is certainly the case that 
all variants of OWL are strictly first order. OWL Full has some second 
order syntax, but the semantics are first order.

>>> Am I wrong in thinking that it is possible to express TBox 
>>> information in RDF?
>>
>> Well, in OWL DL, the tbox *and* class expressions are *encoded* in 
>> RDF (I wouldn't say they are *expressed*).
>
> This show up some of the problems we've had.

Perhaps not as you expect.

>  You obviously have a different semantic for these words in this 
> context, whereas I have the same.

Thus you conceal a distinction I think important. Instead of trying to 
understand my distinction, you seize upon your lack of such a 
distinction as evidence that I misunderstand you.

>   I expect you've often seen me say the "wrong thing" when I've meant 
> something different.

I expect that the something different is also wrong. Why is this a 
problem?

> I'd improve this if I knew how.

Well, if you understood the distinction I was making above and why and 
why I made it in response to your question, I think you'd have a better 
understanding of OWL.

Notice that this all is orthogonal to understanding the nature of 
cardinality restrictions in any flavor of OWL *except* in that it's 
part of your confusion about TBox and ABox and what can be said and, 
consequently, the types of contradictions that may arise in OWL 
knowledge bases (to be a bit more neutral).

>> In OWL Full, they are also so encoded, and their encoding also has 
>> assertional force.
>> [snip]
>>
>>> A lot of your email takes exception to my statement that 
>>> minCardinality is not useful.  I'll confess that I intentionally use 
>>> strongly written statements like "this is useless" to get a solid 
>>> response.
>>
>> Perhaps not every interlocutor you enconuter enjoys being 
>> manipulated, or enduring being presumed to require goading to produce 
>> "solid responses", esp. when they have shown good faith with 
>> extensive answers.
>
> While the initial statement (before you started responding) was of 
> this form, I really haven't persisted with it, though it may have 
> appeared that way.  I've appreciated the help.

Great. Amend my point to, "not every interlocutor enjoys people 
claiming to manipulate them this way" :)

> I've persisted with the expression "useful" in the context of the 
> tools I've hoped to use.  Many other OWL expressions have been more 
> evident in how to go about using them.

That seems generally, but not entirely, true. It's unclear if people 
*do* know how to go about using other OWL expressions. The combination 
of open world assumption and lack of unique name assumptions means you 
have to say a lot more negative stuff to get various entailments 
(including contradictions) out of OWL.

> I suppose I came into this confused, because there are a lot of people 
> who expect that cardinality support (of some level) will involve 
> comparing the cardinality values to the number of times a predicate 
> gets used (for instances of the classes described).

If by this you mean that cardinality does not *validate* the data in 
your KB, and people expect that, you are correct. It's one of the tough 
things to get past. The K or epistemic operator can help (as Jos 
acknowledged in his OWL Flight paper). With the K operator, you can 
define the class of people who have three *known* children. For 
something to be a member of that class, there must be three distinct 
individuals in the kb in the has child relation to that something. 
(roughly). We have a preliminary implementation of the K operator for 
ALC (so no counting quantifiers yet) in Pellet.

> I think we've established that this is an incorrect view, though it is 
> a very common one.
>
> All the same, I take the point.  I've persisted unnecessarily and I'll 
> back off.

It's ok to persist in questioning when you don't understand, obviously. 
I'd be more cautious in persisting with your conclusions as the 
foundations of your argument get successively knocked out :) And that's 
not a matter of an offense against me. I just think it's better 
methodologies.

[snip]
>>> As we've discussed, it is possible to see that minCardinality is 
>>> being used inconsistently when it is used to describe unsatisfiable 
>>> class,
>>
>> I really wish you'd make the "next leap". I can get inconsistency 
>> even if all my classes are satisfiable. Take the following tbox 
>> statements:
[snip]
> I'm sorry.  Reading it, I see that I was not clear.

That's ok. If you understand this point and aren't backsliding, I'm 
fine :)

[snip]
> Which, like yours, shows a pair of completely satisfiable classes 
> which are disjoint.

We agree.

> There are lots of other cases where minCardinality can create a 
> situation with inconsistency due to class definitions and instances 
> thereof.  eg. Instances of a class can't exist because the class is 
> not satisfiable.  Or instances can't be of these several class types, 
> because they are disjoint.  The list goes on.  There are also some 
> subtle interactions with other classes and restrictions which make it 
> even more complex.  I know it's not simple.  I'm sure it will give me 
> many sleepless nights trying to calculate this.

I advise reading the literature. People have done those sleepless 
nights already. With proofs.

I'm pretty sure you are taking on the very tough challenge of trying to 
combine OWL reasoning with large ABoxen held in secondary storage based 
database. The current work in this area (that I know of) is DLDB from 
Leigh (which I suspect is incomplete, but don't know), and 
InstanceStore from U. of Manchester (which, currently, is limited to 
role-free aboxes).

[snip]
> The distinction I am being so unsuccessful at conveying has to do with 
> comparing the number of usages of a predicate with the cardinality 
> associated with that predicate.  The common presumption is this can be 
> used as a consistency check.

Yep, it don't work here.

> In a closed world I might have been clearer.  If this were all closed 
> then it may have been possible to distinguish between a consistency 
> problem due to how class definitions interact vs. a class instance 
> which just doesn't use a predicate the right number of times.

Hmm. Maybe. I'm a bit skeptical. Well, it's really another type of 
clash, i.e., with the fact that with negation as failure, not provably 
min 3 is not min 3.

>   The principle difference is that one type of check needs to 
> explicitly count the predicate usage, while the other one does not.
>
> However, as I argue this I'm starting to wonder about this artificial 
> line I'm drawing between the two.  If I want minCardinality to 
> interact with a oneOf class then I'd need to count there as well, even 
> though I'm not counting the usage of the predicate on instances of any 
> class.  Perhaps if I look carefully enough then I'll discover that 
> there really was no line between the two types of consistency check.
>
> Now that I think of all the complex cases where minCardinality can be 
> used to create an inconsistency I think I finally get what it's for.  
> Even as I slowly came to understand this I've been avoiding it.  I was 
> expecting to see (and had been told to look for) some kind of closed 
> world assumption (ie. counting the usage of a predicate), even though 
> my understanding of this said that this was wrong.

Yes. This is precisely the problem Jos and I mentioned earlier; me as 
an education problem, jos more as a reason to adopt something else.

There is a bit of a dogma that the Web *requires* the open world 
assumption because of the "open nature of the web". I think that 
particular argument is ubercrap, though I've heard more sophisticated 
ones. However, I think having the open world assumption is useful and 
fun in many circumstances.

[snip]
>>> I started out with an expectation that I could use minCardinality 
>>> for consistency checking using some kind of counting mechanism.  
>>> I've now come to understand that this was wrong.
>>
>> You can, but not like you thought. This is in fact how reasoners work 
>> (for some value of "some kind of counting mechanism).
>
> This is interesting.  Can you give an example please?  The only place 
> where I can think this could happen would be if the range of a 
> cardinality restricted predicate were finite and countable (eg. 
> oneOf).  Is this the sort of thing you mean, or have I missed the 
> point again?

Consider a tableau algorithm. (This is going to lie a bit, for 
simplicity of exposition. Please don't internalize this discourse!) The 
basic idea is to build a structure that represents some "completion" of 
the ABox that respects the constraints expressed in the ontology (both 
TBox and Abox and RBox, and usually, the "query" you are posing, e.g., 
is C a subclass of D). Let's consider a simple example where we have 
only on individual and no TBox (or an "eliminated" Tbox):

	x:C&D

So, the tableau expansion rules tell us if you see a type assertion on 
an individuals that is a conjunction, add a type statement for each 
conjunct, if they are missing. So:

	x:C&D
	x:C
	x:D

Now we're done! There's no other rule we could apply that would change 
anything. So this "completion" is consistent! It corresponds to a model 
of the original KB. This on the other hand:

	x:C&~C

Will obviously die as:
	
	x:C&~C
	x:C
	x:~C

Contains an "obvious" clash. (i.e., by just looking to the type 
assertions with atomic classes and their negations, we can find a 
particular atomic class and its negation).

What happens with so called "generating" rules like someValuesFrom or 
min cardinality? We have to add *successor nodes*. That is fresh 
relations. So:

	x:some(p, C)
	x:all(p, ~C)

is going to be a problem, since, by the some rule, I need to add a x p 
something that is C to the KB:
	x:some(p, C)
	x:all(p, ~C)
	x p anon1.
	anon1:C.

But the all rule says that all of x's p's must be ~Cs, so:
	x:some(p, C)
	x:all(p, ~C)
	x p anon1.
	anon1:C.
	anon1:~C

So a clash.

When you have mins you have to generate the appropriate number of 
successors and with maxs, you have to make sure you don't have too many 
successors. For example, take:
	x:max(1, p)
	x:some(p, C)
	x:some(p, ~C)

(Note that this is all easier with qualified number restrictoins. Bare 
number restrictions, well, suck!!!!)

So each some expression generates a successor. Thus far no problem:
	x:max(1, p)
	x:some(p, C)
	x:some(p, ~C)
	x p anon1.
	anon1:C.
	x p anon2.
	anon2: ~C.

Whoops! We have too many ps for x! So we try to *merge* anon1 and 
anon2. But any way we do it, we'll end up with a clash. So no dice.

Of course, practical reasoners try to detect such things before 
generating too many nodes (or nondeterministically merging them). If 
you see a min and a max on the same node where the max is less than the 
min...well, clash there partner!

>>> The final mechanism of entailment cannot use minCardinality either.
>>
>> Oh piffle.
>
> That's a very leading comment,

I think you mean "dismissive" :)

>  particularly when it comes with no explanation.

Er..then it doesn't lead very far.

> So what sort of thing are you referring to?

Well, I don't know what you are referring to either.

>   Now that you've said this, I'm thinking about it, and the only thing 
> that comes to mind is something like:
>   minCardinality(P, x)
>   hasRange(P, C)
>   oneOf(C, set)
>
> If the cardinality of the set is x, then I could entail that each 
> element of the set is distinct.

Well, my favorite is that ParentsWithAtLeastThreeChildren is entailed 
to be a subclass of ParentsWithAtLeastTwoChildren (defined in the 
obvious way)..

> Is that the sort of thing that you mean?  I can't think of anything 
> else (I know that's a poor reflection on my imagination).

Subsumption is the big set of entailments in a lot of ontology 
languages, esp. DLs. So they are the ones I tend to pick on.
[snip]
>>> When you've said that if minCardinality is useless then so too is 
>>> the rest of OWL, I have not found this to be the case at all.  Other 
>>> expressions in OWL provide some very useful tools for consistency 
>>> checking and entailment,
>>
>> Examples? I mean, I have a reasoner that can reason with all of owl 
>> (if not all of it at once; now that shoiq is cracked that will 
>> change).
>
> Well there's lots of trivial stuff for a start:
> sameAs(b, a) :- sameAs(a, b).
> sameAs(a, c) := sameAs(a, b), sameAs(b, c).
>
> Or for a functional property P:
> sameAs(a,c) :- P(a,b), P(a,c).
>
> The list is huge, and in some places it's complex (as opposed to these 
> simple ones).  But I know you know this, so I suspect you're asking 
> about something else.  I can't tell what, sorry.

Oh, I see where we've parted here. I'm just warning you that there are 
other places where the open world assumption might clash with many 
people's expectations.

Disjunctions are one (something that is A or B isn't necessarily known 
to be A or known to be B).

that the members of an owl oneOf aren't all distinct is another.

People often expect that differently named things are distinct by 
default, unless you asset they are the same.

Lists...oy, lists. There's so much badness there! :)

>>> much of which has already been defined (though I've seen different 
>>> papers and the w3c site sometimes defining different things... I 
>>> won't get into that today).  I was just expecting to use 
>>> minCardinality in a similar way,
>>
>> I would like to know the other way.
>
> Off the top of my head... Raphael Volz, among others, has tried to 
> describe a lot of these in horn clauses,

Raphael, Ben, Ian, and others have workd on Description Logic Programs, 
the datalog friendly subset of OWL (Jos's paper on OWL Flight builds on 
this work). That's a very tiny bit of OWL.

Remember that datalog's decision procedure is polynominal whereas OWL 
DL's is NEXPTIME and OWL Full is doesn't *have* a decision procedure 
(i.e., it's only semi-decidable). You ain't going to shoehorn the 
latter into the former without a trim...with a sledgehammer :)

[snip]
> While I've yet to see anyone describe an entailment that conflict with 
> someone else, there seem to be lots of different lists out there.  In 
> couple of cases I'm looking at entailments which are consistent,

Er...Mr. Term Pedant time again. Sets of sentences are usually what's 
called "consistent". You mean "sensible"?

> but don't appear to be deductive.  That bothered me until I learnt 
> about abduction.

Well, hmm. Entailment usually *is* a deductive notion (and semantic, 
i.e., P entails C iff C is true in all interpretations P is true). But, 
be that as it may.

> Still, I'm looking at deductive systems, so abductive entailments seem 
> beyond me for the moment.
[snip]

They are hairy.

Cheers,
Bijan.

Received on Sunday, 10 April 2005 04:02:52 UTC