W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > April to June 2005

More definition comments

From: Bijan Parsia <bparsia@isr.umd.edu>
Date: Mon, 4 Apr 2005 23:38:16 -0400
Message-Id: <d7f01c733ab40b9ec14e5a04377eb283@isr.umd.edu>
To: DAWG Mailing List <public-rdf-dawg@w3.org>


(In basic pattern, I guess it goes without saying that a basic pattern 
is a *finite* set of triple pattens?)

""Definition: Substitution

Substitution is a function from a subset of the set of variables, V, 
the domain of the substitution, dom(S), to the set of RDF terms, T.

  We write S(v) for the substitution of variable."""

Proposed revision

"""**A** substitution is a relation from a subset of V, its 
<em>domain</em>,to RDF-T.

We write dom(S) for the domain of a substitution.

  We write S(v) for the substitution of **a** variable."""

(The articles definitey need to get in there.)

(If the editors want to keep "the set of variables V" etc. for clarity, 
that's fine. But it definitely should be either T or RDF-T everywhere.)

(I have a worry about the S(v) notation, but will take it up below.)

"""Definition: Restriction

  If X is a subset of dom(S) and dom(S')=X and S'(v) = S(v) for all v in 
X then S' is the restriction of S to X, written S|X."""

First, where are restrictions used? I see the word used in constraints 
but it doesn't seem to be doing the same thing (i.e., there it is a 
restriction on the *ranges*, not of the domain of a substitution).

Second, the definitoin and notation are confusing. Esp. if unused :) 
Here's a revision:

"The substitution R is a restriction of S if dom(R) is a subset of 
dom(S) and for all v in dom(R), R(v) = S(v). R is known as the 
restriction of S to dom(R), and written rest(S, dom(R))."

Ok, the recursion on dom(R) is a bit ugly, but I'm unclear why we need 
the restriction of Foo *to* Bar in the first place.


Definition: Pattern Instance

  If S is a substitution then the result of replacing any v in a basic 
pattern P by S(v) is a pattern instance of P, written S(P)."""

So, pattern instances don't have to replace all their query variables? 
In other words, not all pattern instances are rdf graphs, but some are 
themselves patterns?

Where are pattern instances used?

BTW, I find having S(v) and S(P) mean different things *frightfully* 
confusing. Also, S(P) isn't even a function according to the above 
definition, since, given that S is
  	?x = ex:foo
	?y = ex:bar

and a basic pattern
	(?x ex:baz ?y)

S(P) can be (ex:foo ex:baz ?y) and (?x ex:baz ex:bar) and (ex:foo 
ex:baz ex:bar). Is that 'any' up there supposed to be an 'every'? (Or 
read with the force of an 'every', as in 'any variable in P is replaced 
by S(that variable)'?

I asked someone else how they read it and they read it the same as me. 
(Note, I may have biased the reading.)
"""Definition: Pattern Solution

  A Pattern Solution of Graph  Pattern GP on graph G is any substitution 
S such that S(GP) is a subgraph of G."""

Undefined (and unlinked), Graph Pattern, graph, and subgraph. Note that 
the last two are defined:

and are the same *assuming* that S(P) goes to graphs, not basic 
patterns. Which I guess it must or this all makes no sense :)


I'm very unclear how bnodes play out. It seems to me that any query 
with a blank node cannot have a match. On the one hand:

"Blank Nodes and Queries

A blank node can appear in a SPARQL query patterns. It behaves as a 
variable,  although it can not be named in the query result form, such 

But it can never appear in a substition (given the definition of 
substitution and the disjointness of V from RDF-T). I presume that 
bnodes in query patterns are distinct from bnodes in the queried graph, 
regardless of their lexical form, thus any Graph Pattern (GP) with 
bnodes will lack any pattern solutions, since every S(GP) will fail to 
be a subgraph of any other graph (at least, given the RDF Semantics and 
the obvious meaning of subgraph). One could get around this by saying:

"""A Pattern Solution of Graph  Pattern GP on graph G is any 
substitution S such that S(GP) is simply entailed by G."""

Or if one is adverse to simple entailment, one could say:

"""A Pattern Solution of Graph  Pattern GP on graph G is any 
substitution S such that there is a subgraph of G which is an 
RDF-semantics-instance-of S(GP)."""

One could also expand the definition of Substitution, or of variables. 
We've already liberalized the subject position, why not liberalize the 
predicate position as well?

(Ok, I actually don't really want predicate variables to be bnodes 
because I want to generate a OWL Direct model theoretic compatible 
semantics, in which predicate variables are, in fact, metalinguistic. 
But it is a solution. I don't think it'd be hard to extend the RDF 
model theory to handle this extension.)


Received on Tuesday, 5 April 2005 03:38:20 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:23 GMT