Re: Cardinality in the open world

On Apr 10, 2005, at 9:58 AM, Paul Gearon wrote:

> Hi again,
>
> I seem to be gradually converging on what you've been explaining.  You  
> may not have picked up on it, but some of my past emails have started  
> out with one point of view and ended on another as I've understood the  
> flaws in what I'm trying to explain.

Yep.

> Anyway, on to the adversarial part of the email....   ;-)
>
> On 10/04/2005, at 2:02 PM, Bijan Parsia wrote:
>>> 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.
>
> This is frustrating.
>
> I always understood that the usage of assertions in the syntax was not  
> relevant to that part of the discussion.  I wasn't going to mention it  
> all.  However, at the time I was trying to say that assertions did not  
> appear in the expression.

A class expression, by itself, is not an assertion. It's a formula with  
a free variable. To get asserted, that variable must be bound. It can  
be bound by grounding it, i.e., replacing the variable with a singular  
term (in OWL, a logical constant), or by a quantifier. In owl, you can  
only use the universal quantifier over a conditional in which class  
expressions (with the same variable) appear on both sides.

Nominals (hasValue, oneOf) complicate the picture because they let you  
insert individuals' names into *parts* of class expressions.

(Just repeating for context.)

> The problem with that statement was that the syntax *did* use an  
> assertion.

Yep. In OWL full at least.

> Since I didn't consider this assertion relevant (being for syntax) I  
> decided to mention that I was aware of it, but that it was irrelevant  
> to my argument.

Remember that I'm responding to:

""" but I was under the impression that the assertion of this property
 >> was just the RDF way of expressing a higher order concept.
...
 >> Am I wrong in thinking that it is possible to express TBox
 >> information in RDF"""

So, there are several readings of "express" (as we've discussed). It's  
perfectly possible to *write down* TBox information in RDF abstract  
syntax (i.e., triples). Those triples have normal assertional (abox)  
force *as well* (in owl full; in OWL DL they are "compiled away").  
However, their *TBox* meaning is entirely first order...you are not  
quantifying over sets of elements of the domain. The usually way to  
link the abox syntax expressions with the tbox meaning is via a bunch  
of axioms (see the LBase note).

If you are trying to *axiomatize* TBox axioms in RDF, using only RDF  
semantics, then you are doomed to failure. No negation or disjunction,  
hence no conditionals. (Let's not even get started with the troubles  
with nested quantifiers!).

> I thought I'd mention that I was aware of it, so that I couldn't be  
> accused of claiming that there was no assertion, when the syntax used  
> one.  The fact that you think that I believed this assertion to be  
> relevant in any way demonstrates my lack of clarity, and I apologise.

Hey, as long as you are going from lack of clarity to clarity there's  
yay there.

This sort of confusion is why I think it's a good idea to start with  
OWL DL when trying to understand these things, especially if you are  
using 'TBox' and 'ABox' to help organize your investigation. That's  
really the take away message. There's vastly more literature on the  
correspondence between DLs and FOL, than there is on OWL Full style  
(there is some literature; SKIF papers, LBase, HiLog, the appropriate  
sections of the OWL Semantics and Abstract Syntax, the RDF Semantics,  
Simple Common Logic).

Ok, this seems a dead horse ;)
[snip]
> This makes me think of something else I've been doing...
>
> I already mentioned that I've used intrinsic statements to track down  
> descriptions for individuals.  To do this I used an predicate in my  
> own namespace so it wouldn't look like rdf:type.  I didn't want to use  
> rdf:type because descriptions are not quite classes, and I didn't want  
> erroneous statements showing up when an individual's type was queried.
>
> Looking at this discussion I'm starting to think that I should just  
> use rdf:type for restrictions, since they *are* classes.
>
> I also think that I should still use the internal predicate for union,  
> intersection, complementOf and oneOf, since these are not classes.

They are classes. (Ok, not syntactically in RDF/XML. But union is v  
(or), intersection is & (and) , complementOf is ~ (not), so in a sane  
syntax, if you have classes C, D, then ~C, C & D, and C v D are all  
also class descriptions).

However, it sounds like you are reinventing abstract syntax ;) Check:
	http://www.w3.org/TR/2004/REC-owl-semantics-20040210/ 
syntax.html#2.3.2.2

you'll see that restrictions, named classes, and the boolean  
combinations are all on a par.

> (This is based heavily on the expository text, with a little reference  
> to the spec.  Since you can read the spec better than I, I thought it  
> worth asking)
>
>>> <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 :)
>
> My concern was how you've said that class expressions can be part of  
> ABox assertions, and that they are also a part of TBox expressions.   
> So when are they one, and when are they the other?

The are the former when they appear in a fact, and the latter when they  
appear in an axiom (using the OWL Abstract Syntax).

In other words, they are Abox when they appear on the right hand side  
of a type assertion, and tbox when appearing on the left or right hand  
side of a subclass/equivalence axiom.

> I understand that saying that something is an instance of a class is  
> ABox.  Unfortunately, I thought that the definition of that class was  
> TBox...

Don't think of it as *defining* a class, but *describing* them.

The abox is about the relation between individuals and descriptions  
(class membership) or individuals and individuals.

The tbox is about the relation *between class descriptions*.

>  though now I suppose I see that this just defines a structure, with  
> no meaning to any of it (for instance, there's no way to know how any  
> parts of that structure interacts with each other).

That doesn't sound right. They are formulas with free variables. Those  
have plenty of meaning!:
	http://www.w3.org/TR/2004/REC-owl-semantics-20040210/direct.html#3.2

(Check out the embedded constructs vs. the axioms and facts table, and  
then the definition of satsifaction, consistency, and entailment.)

A typical difference between the abox and tbox is how that variable  
gets bound (nominals break this). The other key distinction is that the  
tbox is nothing but conditionals and the abox has no conditionals  
(except in so far as you can express them in class expressions in the  
standard way).

[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.
>
> 1.5 order logic was described to me as containing some, but not all,  
> second order logic constructs.

I've never heard that. I think it's bogus.

>   So if the logic contains elements that are not first order, then  
> it's 1.5.  I thought OWL Full met this definition.

OWL is syntactically second order but semantically first order.

> I'm surprised that you say that OWL Full's semantics are all first  
> order.  I thought that the ability to treat predicates (properties) as  
> full classes moved it out of being purely first order?

You can't really treat predicates as *full* classes. You aren't really  
quantifying over them. The RDF semantics explains this pretty well.

>   Are you saying that there are limits to what this allows which  
> prevent non-first order statements from being written?

The hilog papers might have the best explanation. Essentially, to keep  
the first orderness you "reify" all the relations. That is, instead of  
mapping bob loves mary directly to a two place predicate Loves(bob,  
mary), you map it to a *three* place predicate triple(bob, loves,  
mary), or rdf(bob, loves, mary). *When* you quantify over "predicates"  
you are quantifying over the second position of that first order  
statement.

Now all that's left is to recover the predicate meaning. So you add an  
axiom like:
	if rdf(bob, loves, mary) then Loves(Bob, Mary)

(only, you'd want to make it more general, obviously).

The hard part is getting all those axioms to come out right. But notice  
that everything is entirely first order. You've *punned* the name of  
the predicate...in one context its a singular term, in another, a  
predicate.

[snip a lot of stuff; running out of energy]

>> 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.
>
> I followed all your reasoning (that was all in the stuff I snipped),  
> and it makes sense for a lot of constructs, only I don't really see  
> where min cardinality could enter that picture.  In this example you  
> broke (technical word there, I know) counting max cardinality by  
> demonstrating there were more unique statements than specified.
>
> I believe that the only way to break counting on min cardinality is if  
> you can demonstrate there can be no more statements with the  
> predicate.  You said, "When you have mins you have to generate the  
> appropriate number of successors", but do you have to generate them?   
> I thought that the open world would usually protect you from this?

Well, if there are existing (or prior) successors, you don't have to  
generate any new ones. So you generally check the number of existing  
ones.

I'm not saying this maps into your sense of "counting for consistency"  
:) I'm just saying that you do need to check the number of successors  
when reasoning. You *can* just add the right number of successors to  
meet the mincard, but then any max card is going to hurt because it  
will have a lot of nondeterministic merging to do.

> I said "usually" because restricted classes such as classes of "oneOf"  
> can create a limit to generating statements, and I think I've  
> specifically mentioned this before.

Yep.

> I'm not saying that you're wrong, but I don't really see counting for  
> minCardinality working with this kind of example.

Counting along can't prove that the mincard is consistent.
[snip]
>> 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).
>
> True, but languages like Java can create an infinite loop, yet it's  
> still useful.  In other words, just because it's possible to create  
> something that is very inefficient (or impossible) to resolve in the  
> system, it doesn't mean that the system isn't worth building.

Well, of course, I think OWL systems are worth building, having had a  
major hand in building one :) My *point* was that you can't fit the  
bigger box into the smaller one. You can't write a JVM in pure datalog.
[snip]

Cheers,
Bijan.

Received on Sunday, 10 April 2005 16:00:36 UTC