- From: Dan Connolly <connolly@w3.org>
- Date: Wed, 16 May 2001 22:15:05 -0500
- To: www-rdf-logic@w3.org
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