Re: Cardinality in the open world

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.

Non-entailable statements which are consistent wiht the knowledge base 
are definitely unspecified.  The open world assumes that they could 
exist.  ie. the existence of these statements is unknown.

>>>>  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.  Perhaps my 
idiom was unfamiliar to you, but I mean that the statements "describe" 
a contraction.  Or perhaps that the statements "are" a contradiction.  
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.

>>>>   (If I'm wrong here, then let me know as the rest of this message 
>>>> is based on this assumption).
>>>
>>> This doesn't seem to be the most helpful way to conceive of it. 
>>> Better to think in terms of model theory (though, it's possible that 
>>> your version will line up with the model theoretic one...it's just 
>>> nicer to use standard terminology).
>>
>> Unfortunately I don't have a background in model theory.  Can you 
>> suggest a primer for me?
>
> Actually, the RDF semantics document has a pretty nice intro.
>
> Otherwise, I'd just read some logic books.
> [snip]

Done that.  :-)  I've gone through a couple of log books, but the one 
I've spent the most time on is "Symbolic logic and mechanical theorem 
proving" by Chang and Lee.

I'm comfortable with logic, but not "model theory", hence my question.

>>>> minCardinality of 1:
>>>> This describes existence.  Any statements with this predicate make 
>>>> the model valid.
>>>
>>> Not if there were a maxCardinailty of 0.
>>
>> 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.  Saying something has a "type" of minCardinality(1) makes 
no sense to my understanding of the term.

Now if I'm describing that something has a minimum cardinality, then 
that description is TBox.  If it's not TBox, then it has no meaning 
about number restrictions, which means no contradictions.  It's 
therefore irrelevant to me here.

>> 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?

>> 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, 
rather than reporting a problem.  Then as anything tries to become a 
member it I can report the problem then.

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.

>>  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.

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.  That makes sense.  This is getting me closer to an 
understanding.  Unfortunately, it doesn't seem to have a practical 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.

>> This is because the database does not contain any statements to make 
>> this restriction consistent, so the existence of these statements is 
>> "unknown".
>
> Let's make the restriction a free standing expression in a typical dl. 
> To do that, it has to be an abox statement (i.e., a ground formula), 
> or a tbox statement (i.e., a universally quantified conditional). So 
> consider
>
> 	a:minCard(1, P)
>
> Is that consistent? Yes, for sure!!! Why? Because there's an 
> interpretation underwhich it is true (i.e., it has a model).
>
> Oh, you say, but there is a "database" statement. Well, consider the 
> tbox statement:
>
> 	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.

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).  The count is restarted for each subject.  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.

>>> 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, but I was not prepared to accept a class that 
can't be instantiated.

A class is a part of a model for the instances.  A model for instances 
is meta-data for the instances, and I understand TBox information to be 
meta-information.  Perhaps you'd like to correct this view?

> 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.

However, what I've come to is a situation where minCardinality either 
leads to an unsatisfiable condition, or else it is always satisfiable.  
Finding instances of an unsatisfiable class is easy to do.  However, if 
the minimum cardinality is satisfiable, then the system will always be 
consistent.  Does this restriction provide any useful information in 
this case?  It would seem not.

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

(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).

Regards,
Paul Gearon

Received on Friday, 8 April 2005 02:47:45 UTC