The Mel99 semantics for RDF

Here's one view of semantics for RDF that
I looked at a few years ago, did not
understand/appreciate, and then rediscovered
recently, after having learned a little
bit about model theory:

  Algebraic Specification for RDF Models
  Sergey Melnik, meknik@db.stanford.edu
  July 1999.
  http://www-diglib.stanford.edu/diglib/ginf/WD/rdf-alg/rdf-alg.ps

(for a bit of context, see the GINF stuff
  http://www-diglib.stanford.edu/diglib/ginf/)

I've been trying to understand it by transcribing
it into larch, the way I digest lots of stuff...
  http://www.w3.org/XML/9711theory/RDFSemantics.lsl

I'm not all the way thru (in particular, I'm
leaving out the collection stuff; I expect to
be able to layer that on top), but it seems to make sense.

I'm becoming increasingly comfortable with the
explanation it gives for things like the
fact that rdfs:Class is an rdfs:Class.

It seems to parallel the KIF PropertyValue
stuff quite closely: where Sergey
writes (p, s, o) \elt S , we
see (PropetyValue pp ss oo) in KIF,
where p is what pp denotes, s is what ss
denotes, and o is what oo denotes.

After studying this, I have to take back
what I said about the term 'model' in
the RDF spec having nothing to do with
'model' in model-theoretic semantics;
in Sergey's algebra, a model for
an RDF document *is* a graph of
nodes/resources.

I don't think the specification of a
model for an RDF document in the RDF 1.0
spec is quite right; it seems to prescribe
exactly one model for each document, rather
than saying how a document constrains a model.
But I'm starting to think maybe it's not
completely out in left field either.
I need to go over it again.

Meanwhile, I wonder if I can summarize Mel99:

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

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

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

That's it for the basics.

Note that the prinicple of erasure holds:
any interpretation that satisfies {A1, A2, A3}
also satsifes {A1, A2}.

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

Every RDF interpretation I is constrained
so 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?

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.

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

| 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?
I gather that's pretty much the way KIF works
(aside from some details about what N has to include,
like lists and numbers and strings).


| (It is a bit 
| worrying when one sees triples being used to encode things that seem 
| to have no obvious relational interpretation, but never mind....)

Is the relational interpretation above suffuciently clear/obvious?

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

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

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

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

| And so on... those are the 
| kinds of questions that I want to see answered. 

How did I do? (or rather: how did Sergey do?)

-- 
Dan Connolly, W3C http://www.w3.org/People/Connolly/

Received on Wednesday, 16 May 2001 23:15:08 UTC