Re: Grist for layering discussion

As it appears that some participants in this debate prefer an operational
view of the situation, let me try to couch my comments in an operational
setting.  (I believe that Pat would agree with the following, but I'm sure
that he will speak for himself as well.)

Suppose you want to build a representation formalism, like, say, RDF.  You
design a syntax (and, maybe, an API) that lets you create information bases
and you specify a retrieval mechanism that lets you see what you have
created.  SQL is a not-very-good example of such as retrieval 
mechanism for databases.  The retrieval mechanism wasn't really done for
RDF, so lets just say that we can ask whether an information base contains
a particular triple.  

Now you want to extend RDF.  OK, lets add mechanisms for creating a class
taxonomy and for typing the domains and ranges of roles, and call it RDFS.
We'll use the same syntax to create information bases, but modify the
retrieval mechanism to make it correspond to the wording in the RDF Schema
Candidate Recommendation.  Now you definitely get more out of the
information base than you put in.  In particular, you get 

	rdfs:Class rdfs:subClassOf rdfs:Resource .

out of an information base that has not had any information added to it.

So far so good.  

We have:

1/ All RDF syntax is also RDFS syntax.
2/ Given an RDF information base, i.e., an information base created using
   only the syntax in RDF, the RDFS retrieval mechanism produces everything
   that the RDF retrieval mechanism would produce, and maybe more.

This is precisely what it means to be an extension.

However, RDF and RDFS have a very uncommon relationship because they also
share a syntax.  Let's try to create a same-syntax extension of RDFS to
encompass some of propositional logic, namely the part that allows us to
create related disjunctions such as John is either married to Susan or
friends with Jake. 

[Why do this extension in particular?  Well it is an extension that shows
some of the problems, but it also has a construction that can be fairly
naturally expressed as triples.]

What doesn't work is to directly encode the missing logical
construction.  A direct encoding of this would be something like 

IB1	John rdfo:or _:x .
	_:x married Susan .
	_:x friend Jake .

We construct a formal specification of RDFO to incorporate this
construction.  In particular, from

IB2	John rdfn:or _:x .
	_:x married Susan .

RDFO retrieval will produce

	John married Susan .

Now is everything OK?  NO!  There are two problems:

1/ Because RDFO is an extension of RDFS RDFO retrieval will also produce

	_:x married Susan . 
 
   from IB2.  In fact, every RDFO disjunction also creates several
   extraneous consequences.  

   Well you might argue that the 

	John rdfn:or _:x .

   consequence is benign because it mentions the special RDFO property.
   However, the other consequences do not mention any special RDFO
   properties and they are definitely not benign.  RDFO has failed in its
   goal of capturing related disjunctions.

2/ RDFO is non-monotonic.  The retrievals from IB2 include information that
   cannot be retrieved from IB1.

It is possible to overcome these problems, at least partly, by exploiting
the reflective properties of RDF.  We can encode the disjunctions using a
special construction, something like

IB3	John rdfor:or _:l1 .
	_:l1 rdfor:fact _:f1 .
	_:l1 rdfor:rest _:l2 .
	_:l2 rdfor:fact _:f2 .
	_:l2 rdfor:rest rdfor:nil .
	_:f1 rdfor:predicate married .
	_:f1 rdfor:object Susan .
	_:f2 rdfor:predicate friend .
	_:f2 rdfor:object John .
	 
Now retrieval for RDFOR can (probably) be designed so that 
1/ All the extra consequences involve special the RDFOR constructs, and so
   can be regarded as benign.  
2/ RDFOR is monotonic.

Have we succeeded?  Partly, but at three prices, two that show up right
away and one that shows up in other extensions.

The first price is that the construction is much more complicated than
a syntax extension.  

The second price is that the construction adds a lot of extra consequences.
These consequences can be considered to be benign, but they are still
there.  To make the formalism work correctly in the presence of these
consequences requires a lot of work (and may not be possible, even here).

The third price is that we have introduced a form of reification and a
construct that can assert the truth of reification constructs.  This
(probably) doesn't cause any problems here because the extension is so
expressively limited.  However, for more powerful extensions reification
produces paradoxes, and thus cannot be used.  


Why is there a problem?  The problem arises, as Pat has stated, from the
attempt to extend a representation formalism while not extending the
syntax.  This cannot be done in many circumstances and can only be easily
done in very limited circumstances.



Peter F. Patel-Schneider
Bell Labs Research

Received on Friday, 11 January 2002 09:18:05 UTC