Re: a new way of thinking about RDF and RDF Schema

From: Sergey Melnik <melnik@db.stanford.edu>
Subject: Re: a new way of thinking about RDF and RDF Schema
Date: Tue, 23 Oct 2001 11:50:35 -0700

> "Peter F. Patel-Schneider" wrote:
> > 
[...]
> > Pat's RDF graphs don't handle order.  However, it is possible to, and has been
> > done (but my reference is at work), add order to a graph that represents
> > RDF and XML information.  There are lots of ways to do this, one would be
> > to add a partial order over edges.
> 
> Well, how do you squeeze the partial order information into the graph?
> I'm not asking for academic reasons. Ordering is a critical feature for
> many applications, and if there is no adequate way of introducing order
> into RDF "as is", we may have to rethink the basics of the RDF model
> (sooner or later). So please let me/RDF Core know about your ideas once
> they are in shape...
> 
> Sergey

Harold Boley has a data model, at
http://www.dfki.uni-kl.de/~boley/xmlrdf.html, that uses total
orders over some of the edges coming out of a node.  This has a
disadvantage when considering multiple ``XML'' documents.  However, it is
an interesting way of proceeding.


Another way, as I said above, is to add a partial order over edges in the
RDF graph.  This would result in something like:

An untidy RDF graph, R, is a four-tuple (that can be considered to be a
partially node labeled, edge-ordered, directed triple-graph) 
		< N, E, LN, EO >
where N is the set of nodes in the graph
      LN :(partial) N -> URI u L gives labels for nodes
      E <= N' x N'' x N is the set of edges in the graph
	where N' = { n : LN(n) is undefined or LN(n) in URI }
	where N'' = { n : LN(n) is defined and LN(n) in URI }
      EO is a partial order over E, i.e., a subset of E x E that is
	 transitive and irreflexive

Now the edge order is only used to order the edges that come out of a node,
so you could also add a condition on EO that edges with different heads are
incomparable or make EO map nodes into partial orders over pairs.

Interpretations then have to be augmented with something like

An interpretation I is a four-tuple 
	< IR, IEXT, ICEXT, IO, IS >
where IR is a non-empty set, called resources
      IEXT : IR -> powerset ( IR x (IR u LV) )
      ICEXT : IR -> powerset ( IR u LV )
      IS : URI -> IR
      IO : IR -> powerset ( (IR x (IR u LV)), (IR x (IR u LV)) )
        such that IO(r) is a partial order
	and if IO(r) contains <s,o> < <s',o'>
	    then <s,o> in IEXT(r) and <s',o'> in IEXT(r)

The notion of a model also has to be extended, perhaps by 

4. for <s,p,o> < <s',p,o'> in EO, <M(s),M(o)> < <M(s'),M(o')> in IEXT(M(p))

(Actually this would probably work better using a <= version of a partial
order, to take care of special cases.)

peter

Received on Tuesday, 23 October 2001 14:59:30 UTC