Re: Cardinality in the open world

On Apr 7, 2005, at 10:47 PM, Paul Gearon wrote:

> On 08/04/2005, at 11:20 AM, Bijan Parsia wrote:
>> On Apr 7, 2005, at 2:27 AM, Paul Gearon wrote:
>>> On 06/04/2005, at 3:41 PM, Bijan Parsia wrote:
>>>> What do you mean by "unspecified"?
>>>
>>> I'm thinking in terms of a set of RDF statements, such as those 
>>> found in an RDF database.  An "unspecified" statement is one that 
>>> does not appear in the database.
>>
>> Can it be entailed by the kb?
>
> Ummm, good questions.  Certainly there are statements which are 
> consistent with the knowledge base, and yet cannot be entailed by it.  
> However, if a statement can be entailed, then can I really say that it 
> is unspecified?  I don't think so.  After all, the existence of such a 
> statement is not "unknown" since we can work it out.

That is correct.

> Non-entailable statements which are consistent wiht the knowledge base 
> are definitely unspecified.

Yes.

>   The open world assumes that they could exist.  ie. the existence of 
> these statements is unknown.

Er....*extensions* to the current kb (i.e., things not in the deductive 
closure) don't matter to determining the consistency of the kb. How 
could they?

>>>>>  I interpret this to mean that it is possible for any unwritten 
>>>>> statement
>>>>
>>>> But there are known unwritten statements. Most entailments, for 
>>>> example.
>>>
>>> My ultimate purpose here is to try to work out which are valid 
>>> entailments.  I am also trying to recognise when a set of statements 
>>> contains a contradiction.
>>
>> Can one "contain" a contradiction by entailing one?
>
> I don't know why you've quoted the word "contain" here.

Because I don't know what you mean.

>  Perhaps my idiom was unfamiliar to you, but I mean that the 
> statements "describe" a contraction.  Or perhaps that the statements 
> "are" a contradiction.

I would just say that they are inconsistent :) Thus, they entail a 
contradiction. They may do so by containing an explicit one (e.g., 
C&~C) or by something harder to spot.

> If I can't get this meaning across then I really don't know the 
> language I should be using.
>
> If an obvious contradiction is entailed, then I believe that it was 
> because a not-so-obvious contradiction already existed before 
> entailment took place.  So I don't think that contradictions can 
> appear because of an entailment unless a contradiction already 
> existed.

Of course.
[snip]
>>> True.  However, I would distinguish that as an inconsistency in the 
>>> TBox data.
>>
>> But it can occur where there is no tbox.
>>
>> 	a:minCard(1)
>> 	a:maxCard(0)
>>
>> No tbox. (The ":" means "type"). It's awkward to write this in RDF or 
>> RDF/XML, but so much is :)
>
> Now this I don't understand.  In OWL the domain of minCardinality is a 
> Restriction.

And, if we're going to suffer with that syntax, a Restriction is a 
Class, so something can be of type cRestriction.

> Saying something has a "type" of minCardinality(1) makes no sense to 
> my understanding of the term.

Then you need some fixes to your understanding :)

> Now if I'm describing that something has a minimum cardinality, then 
> that description is TBox.

No.

> If it's not TBox, then it has no meaning about number restrictions, 
> which means no contradictions.  It's therefore irrelevant to me here.

Huh?

>>> While these inconsistencies are important to find, I want to assume 
>>> that the TBox information is correct, and I am looking for 
>>> inconsistencies in the ABox data in relation to the TBox data.
>>
>> 	a:C
>> 	a: ~C
>
> The fact that C and ~C are mutually exclusive, and therefore nothing 
> can be both, is information about the model that "a" appears in.  Is 
> this not TBox?

No.

Where is the tbox statement above? I've introduced no definitions or 
other constraining axioms.

>>> In a practical context, I'd like to check an ontology for 
>>> contradictions upon entry to the database.
>>
>> Usually, this is called checking for concept unsatisfiability. 
>> However, there is always at least one unsatisfiable concept in an 
>> ontology, owl:Nothing. So unsatisfiabiltiy of a class isn't a 
>> devestating problem, unless you assert something as a member of it.
>>
>> But look, do you you think this tbox is contradictory?
>>
>> 	A subClassOf min (3,P)
>> 	B subClassOf max (2, P)
>>
>> Clearly not. Yet,
>>
>> 	x rdf:type A.
>> 	x rdf:type B.
>>
>> is inconsistent.
>
> OK, I see your point.  I'll keep that in mind.  I'm guessing that I 
> should start marking unsatisfiable concepts when they are described,

Well, our tool Swoop reports unsatisfiable classes. They generally 
*are* a modeling mistake. But they don't necessarily make the ontology 
inconsistent.

>  rather than reporting a problem.  Then as anything tries to become a 
> member it I can report the problem then.

Our paper might help:
	http://www.mindswap.org/papers/debuggingOWL.pdf

> What this does is raise minCardinality from not doing anything to 
> being a tool for describing an unsatisfiable class.  That's not much 
> of an endorsement.

Dude, you are still massively confused. How is this different from any 
other owl construct?

Plus, you totally miss the point of my example above. *There is no 
unsatisfiable class*, yet the combination is contradictory.

>>>  I don't think it would make sense to check for consistency and 
>>> perform entailments with an inconsistent ontology.
>>
>> Of course I didn't suggest that.
>
> I get this now that you've pointed out that I should accept 
> unsatisfiable classes as a legitimate part of the ontology.
>
>>> Re: minCardinality 1
>>>>>   However, if there are no statements with the predicate then the 
>>>>> model is still consistent, as those statements could exist.
>>>
>>> Reword this to: If there are no statement with the predicate then 
>>> the consistency of this is "unknown".
>>
>> No. If nothing contradicts it, then it is consistent.
>
> I thought that if there was no usage of this predicate for the subject 
> then that *is* a contradiction.

No.

> I suppose you are saying that this cardinality restriction tells us 
> that at least one such statement exists, only there is no way of 
> knowing what it is.

Yep. And it need not be the same statement in every model.

>  That makes sense.  This is getting me closer to an understanding.  
> Unfortunately, it doesn't seem to have a practical use.

At this point, I send you to the literature, and to the ontologies.

Actually, at this point, I don't understand why you think ANY construct 
in OWL has a use.

>>  We don't know if anything is a member of that class, but it is 
>> consistent of many things that they are a member of that class.
>>
>> e.g.,
>> 	bob: minCard(1, P)
>>
>> It's consistent even if we don't know any other *facts* about bob.
>>
>> If our kb enatils (or states):
>> 	bob: maxCard(0,P)
>>
>> then we're in trouble again.
>>
>> It's perhaps better for you to think of consistency to be a feature 
>> of a *set of statements*. A set of statements is consistent if it is 
>> *possible* for them to all be true together. That is, there is an 
>> interpretation of the set such that every statement comes out true.
>>
>> So, unless a statement is self-contradictory (i.e, *always false*), 
>> it's going to be consistent with itself. So to get inconsistency joy 
>> you'll have to add more statements.
>
> OK, I'm getting all of this now.  However, while my understanding has 
> improved, I still don't see the use of minCardinality, except to 
> create a unsatisfiable condition.

Again, how is this different in general? This is how first order logic 
works.

Though, I wouldn't describe it as "creating an unsatisfaible 
condition". You use this to model the world. Your model establishes 
certain constraints. With the open world assumption, those constriants 
tend to be looser than many expect. So you have to say more explicitly 
in order to violate them.

[snip]
>>
>> 	for all x, if A(x), then minCard(1,P)x
>>
>> (ok, this is ugly, since normal first order doesn't have counting 
>> quantifiers. Let's see, the expansion would be something like:
>>
>> 	for all x, (if A(x), then some y, Pxy)
>>
>> Hmm. That seems right, but I'm wee bit tired so who knows :) You get 
>> the idea though.
>>
>> (Eek, my first one was nuts. I just reduced this to the existential. 
>> Higher cardinalities are more tersely expressed with counting 
>> quantifiers)
>
> But minCardinality 1 (which we're still talking about) is the 
> existential.  So you're OK for the moment.

All minCardinalities are. The larger ones just are *more* existentials 
with some inequalities.

> OK, I'm following you, and you're describing the same points in 
> different ways to address my questions here, so I'll skip a bit.
>
>>> Incidentally, you can probably tell from my working here, but I'm 
>>> making the assumption that the above statement is in relation to a 
>>> single subject.  All of the tests I describe here need to be 
>>> performed over each subject-predicate in turn.
>>
>> Lost me. You seem to be dealing with class expressions, which, in a 
>> dl, are never free standing. either they are (mostly) ground, or 
>> parts of quantified conditionals. (ok, it's a leetle more 
>> complicated)
>
> I was talking about how the use of the predicate is counted for each 
> individual subject (where the subject is an instance of the restricted 
> class).

Ah.

>  The count is restarted for each subject.

Yep.

>  Since I was relating it to specific examples, then I wanted to be 
> clear that by restricting my argument to a single instance of a class 
> with the restriction, I was not allowing for other instances of the 
> class to be treated differently.  You made this point at one stage, 
> and so I tried to be explicit.  Obviously I failed.  :-)  It doesn't 
> seem important, so don't worry about it.

Ok.

>>>> Not necessarily. For example, and still trivial, say you had a 
>>>> minCard= 4 and a maxCard = 2. Oops.
>>>
>>> Yes, though this is the TBox error I mentioned above.
>>
>> You don't understand what you mean here. :)
>
> I believe that I do,

You're still wrong, from what I can tell.

>  but I was not prepared to accept a class that can't be instantiated.

You also aren't willing to distinguish class expressions from tbox 
axioms. Class expressions appear in *both* the tbox and the abox.

> A class is a part of a model for the instances.

This isn't going to help you.

> A model for instances is meta-data for the instances,

This *really* isn't going to help you.

> and I understand TBox information to be meta-information.  Perhaps 
> you'd like to correct this view?

I've tried :)

abox == ground assertions involving one or two place formulas. I.e., 
type assertions and role/property assertions. In your type assertions, 
you can have arbitrarily complex formula.

tbox == universially quantified conditionals and biconditionals (which 
can contain further universal and existential quantifiers of very 
specific sorts

>> Sorry, I don't have the time/energy to go through the rest of this. 
>> Let me know if there's something that isn't clarified by the 
>> discussion thus far and I'll try to repond.
>
> Well, as I've said, I wasn't accepting the idea of an unsatisfiable 
> condition.  Now that I do, it changes things a little.

You're also not accepting the idea that the tbox and abox are just 
collections of sentences, or that abox statements can involve 
non-atomic class expressions.

> However, what I've come to is a situation where minCardinality either 
> leads to an unsatisfiable condition, or else it is always satisfiable.

No. Check my examples again.

Or rather, this is vacuous. depends on the scope of the "always"

>   Finding instances of an unsatisfiable class is easy to do.

Not really.

> However, if the minimum cardinality is satisfiable, then the system 
> will always be consistent.

No. Plus, you need to look at more complex class definitions.

>   Does this restriction provide any useful information in this case?  
> It would seem not.

I think you need to relax your presumptions. Clearly they were based on 
a faulty understanding in the first place. You need to generalize your 
investigation and understanding.

> I find it ironic that my understanding has changed, but the 
> consequences are still the same.  :-)

Well, if you misunderstand in the first place, and *still* 
misunderstand in the second place (albeit with *some* clearing up), 
*and* you are, as one generally is, attached to one's conclusions, then 
it's certainly not *surprising*. It's probably not ironic either.

> (OK, the consequences of a unsatisfiable class are now different, but 
> the idea that using minCardinality to actually count anything is 
> useless has not changed at all).

Sigh. At this point, i really suggest you change your methodology. I 
mean, given your misundertanding on the above point (i.e., that an 
unstatisfiable class meant a contradictory ontology), don't you think 
you should check the rest of your understanding? Especially when your 
conclusion is so strong and so implausible (i.e., there's an excellent 
prima facie case against your conclusion based on the fact that people 
demand cardinality, systems implement it, most if not all expressive 
dls have it, etc. etc.)

What the open world doesn't give you easily is validation of your data. 
I.e., knowing that something is card(3, P) doesn't mean you'll know 
*which* three things  I'm Ped at. There are lots of scenarios where 
just knowing I'm min3,P isn't going to help me (e.g., determining what 
data goes on the wire for a web service call). This is true for lots of 
things in owl, disjunction for example. Knowing that you are male or 
female doesn't mean I have any knowledge of *which* you are (where as, 
generally, knowing that a value is of a union type string or integer 
generally *does* mean that you know, or at least, can force the issue.)

Notice the vast difference between "isn't useful for foo", or even , 
"isn't useful for this wildly common and popular case foo" and "isn't 
useful".

Cheers,
Bijan.

Received on Friday, 8 April 2005 12:49:38 UTC