Re: The Mel99 semantics for RDF

At 10:15 PM 5/16/01 -0500, Dan Connolly wrote:
>I. Abstract syntax.
>
>An RDF formula is a set of
>atomic formulas; each atom
>is a triple (p, s, o) where
>p, s, and o are terms; a term
>is either a URI
>(i.e. an absolute URI with
>optional fragment identifier)
>or an existentially quantified variable;
>we don't say what the variables
>look like; this is abstract syntax after
>all.
>
>We can look at this in traditional
>first-order syntax by introducing
>one 3-place predicate; let's call
>it PropertyValue. Then an RDF
>formula is a set of atoms
>PropertyValue(p, s, o).
>
>II. Semantics.
>
>An interpretation I is a directed,
>labelled graph; the vertices
>and the edge labels come from the
>same set; let's call it N[I], for nodes.
>Let's call the labelled
>vertices S[I]; so S[I] \subset N[I] x N[I] x N[I].

Did you really mean labelled vertices here?  Labelled edges makes more 
sense to me.

(Roughly, each edge in the graph is an interpretation of an atomic formula, 
whose three URI/variable terms are interpreted as members of N.  Each 
_vertex_ would be interpreted as a single member of N.)

>As seems to be traditional, I'll leave the [I]
>implicit when it seems convenient and clear.
>
>URI terms work like first-order constants;
>each is mapped, by the interpretation,
>to an element of N.
>
>An interpretation I satisfies a formula F
>if there exists an assignment A of
>the existentially quantified variables
>in F to N[I] such that
>for each atom (p, s, o) in F,
>the triple of what I and A say those terms
>denote, (p', s', o'), is in S[I].

This seems to miss something.  I thought the definition of satisfaction 
required some notion of truth value.  Also, my reference defines 
satisfaction in terms of a formula F, an interpretation I and a 
substitution A, as "A satisfies F (under interpretation I)..."   It might 
be easier to consider F by cases.  E.g. for a given formula F and 
interpretation I, and some assignment A of members of N to variables in F:

Case 1:  F contains a single atomic formula with no variables; i.e. the 
interpretation of all terms in F is a specific member of N.
   A satisfies F iff I assigns the truth value TRUE to the member of 
F.  (i.e. irrespective of A)

Case 2:  F contains a single atomic formula with one or more variables.
   A satisfies F iff I assigns the truth value TRUE to the single member of F',
   where F' is obtained by substituting the member of N assigned by A for
   each occurrence of a variable in F.

Case 3:  F contains more than one atomic term:
   A satisfies F iff A satisfies every F'' that contains a single atomic 
formula contained in F.

Case 4:  [by convention?] if F is the empty set, A satisfies F (for any A 
or I).

>An interpretation is a model for a
>set of formulas if it satisfies all the formulas.

The definition of model that I have is more strict here:

defn:  A formula F is true for I iff every assignment A of N to variables 
satisfies F

defn:  An interpretation I is a model for a set of formulae {Fj} iff every 
Fj is true for I.

The key difference here is that, to be a model, the interpretation must 
provide satisfaction for *every* set of variable assignments.

>That's it for the basics.
>
>Note that the prinicple of erasure holds:
>any interpretation that satisfies {A1, A2, A3}
>also satsifes {A1, A2}.

I think this follows pretty directly from my case 2 above.  I think this 
bit captures the "conjunctive semantics" of RDF.


>Then we have a few layers.
>
>III. Reification.
>
>An interpreation I is elaborated to
>have nodes type[I], predicate[I],
>subject[I], object[I], and Statement[I].
>
>In every interpretation I, the term
>   http://www.w3.org/1999/02/22-rdf-syntax#type
>denotes type[I], and so on.
>
>Each interpretation also has
>a partial function Rf[I]
>         Rf: N x N x N -> N

Nit:  I'm not sure what it means for an interpretation to "have" a partial 
function Rf[I];  I'd be inclined to present this as:

For each interpretation there exists a a partial function Rf[I]
   Rf: N x N x N -> N
such that:
>(p, s, o) \elt S
>   iff
>   r = Rf(p, s, o) \elt N
>and
>   (type, r, Statement) \elt S
>and
>   (predicate, r, p) \elt S
>and
>   (subject, r, s) \elt S
>and
>   (object, r, o) \elt S
>
>There are some other details/layers, like
>splitting N into literals and resources
>and properties, but I don't feel like going
>into those here; see Sergey's paper for details.
>
>
>Does that answer the sorts of questions
>that a model-theoretic semantics is supposed
>to answer?

It seems to tell us that for every valid interpretation of RDF, for each 
statement there exists a unique resource with certain properties.  It don't 
think it says anything about how statements about this resource relate to 
the corresponding statement.  Question: If we apply model operators to this 
resource, do we need something outside the semantics of the model operator 
to tell us that it applies to the corresponding statement?

I'm not sure that having a unique resource for each statement is quite what 
RDF anticipates.  It seems to me that RDF allows multiple resources (i.e. 
interpretations of different URIs) that have a similar relationship to the 
original statement.  Maybe Rf would be more usefully defines as a relation? 
(e.g. Rf( p, s, o, r ) being TRUE if r is a reification of (p,s,o) in S.)

>Pat asks, in his message of Wed, 16 May 2001 20:54:38 -0400 (EDT)
>| it isnt entirely clear  whether or not relations can
>| be objects
>
>Yes and no; existential variables can go in the 'predicate'
>slot in formulas, but the (p, s, o) structure in
>an interpretation is just like one first-order relation;
>so there aren't any actual logical relations
>in N.

I don't understand this bit.

>| (if so, the model theory
>| required is going to be a bit more complicated)
>
>I have been trying, without success, to get my head
>around semantics of lambda calculus and all that.
>By this account of things, it seems that I don't need to.

Hmmm... echoes of Scott&Strachey denotational semantics?

>| and it isnt clear
>| what the anonymous nodes range over (I see they are like existential
>| quantifiers, but what domain do those quantifiers range over? A lot
>| turns on the answer, if that domain contains relations).
>
>They range over N, whatever N is for an interpretation.
>Is that good enough?

That's what I would expect.  Indeed, doesn't the model theory make that 
explicit by its reference to "an assignment A of the existentially 
quantified variables in F to N[I]".

[...]
>| And
>| when reification appears, it seems that we have to put the triples
>| themselves into the domain.
>
>By Sergey's account, only indirectly, thru the Rf thingy.

I'm getting out by depth, but... I think this is a difference between an 
interpretation to (semantics over?) a reflexively defined domain compared 
with semantics of relexion.  I think that using a denumerable, reflexively 
defined domain doesn't introduce any hard problems.

>| What *is* a triple, then? What kinds of
>| properties does it have? Are the triples in the domain of
>| quantification the same triples used in RDF syntax,
>
>No; the syntax has URIs and anonymous terms (i.e. existentially
>quantified variables); the domain of quantification
>is N.

"Domain of quantification" is a new one on me.  Is this the same as the 
"domain of dioscourse"?

>(of course, N may contain some strings and URIs and such,
>but that's beside the point, right?)

Ummm... that might be the edge of a precipice.  It seems to be OK for the 
model theory you've outlined, but also seems to fall outside the expected 
interpretation of URIs discussed elsewhere.

I guess the real problem comes if you then want to introduce (and define 
semantics for) some function that operates in the domain of discourse to 
map a string to some proposition.

>| or are they
>| abstract things denoted by the RDF syntax?
>
>Yes.
>
>Of course, this is that funny use the word 'abstract';
>in fact, an interpretation's domain might be
>very concrete things: people, places, rocks, houses, no?

Hmmm... see above.

#g


------------
Graham Klyne
GK@NineByNine.org

Received on Thursday, 17 May 2001 09:35:36 UTC