Active issue rdfms-graph; formal description of properties of an RDF graph

After getting this wrong several times, here's an attempt at a formal 
definition of an RDF graph. This is worded to make it align naturally 
with the Ntriples syntax.

-----

An RDF graph <N,E,oo,ss,gl> is a special labelled directed 
multigraph, consisting of:
two disjoint sets: N of nodes and E of edges;
three maps: ss:E -> N, oo:E -> N, gl:(N u E) -> L, where L is a set 
which contains urirefs, literals and the special value *blank*.
(ss and oo define the 'ends' of each edge; gl specifies the 'label', 
but 'label' is defined idiosyncratically.)
Urirefs and literals are called *labels*. Blank is not a label. If 
gl(x)=blank then x is called a *blank* or *anonymous* or *unlabeled* 
node or edge.
An RDF graph must satisfy the following conditions:
for any e in E:
gl(ss(e)) is not a literal  (no literals in subject position)
gl(e) is not a literal (no literal properties)
gl(e) =/= blank (no anonymous properties)
for any n in N:
if gl(n) is a uriref, then if gl(n)=gl(m) then n=m (tidiness of 
non-literal nodes)

(The exclusion of literals in that last clause is a recent 
improvement which is harmless in simple RDF but essential for 
datatyping of literals. Thanks to Peter for that one.)

A graph which is like an RDF graph except for the last condition is 
called an *untidy* graph. Any untidy graph has a unique *tidying*, 
gotten by identifying nodes labelled with the same uriref under the 
mappings ss, oo.

A 'triple' in the graph is <ss(e), e, oo(e)> for some e in E. There 
is exactly one triple for each edge in the graph. A graph can be 
considered to be a bag (set?) of triples.

Mapping between graphs and Ntripledocs. (If we say 'set' above then 
the following needs to be slightly re-stated)

Suppose bb is a 1:1 (invertible) mapping from blank nodes to bNode 
identifiers. Any such mapping establishes a 1:1 mapping between RDF 
graphs and (unordered) nTriples documents defined by bb on blank 
nodes and gl on other nodes and edges, in the obvious way: there is 
one line in the document for each triple in the graph, written in the 
form
hh(ss(e))  hh(e)  hh(oo(e)) .
where hh is bb on blank nodes and gl on everything else. Since hh is 
1:1, the inverse mapping defines a unique RDF graph from any 
unordered Ntriples document.

Merging

The *untidy merge* of a set S of graphs is simply the graph defined 
as the union of the sets of triples in the graphs in S. (The only 
condition on S is that the nodes in one graph cannot be the edges of 
another graph.) The *tidy merge*, or simply *merge*, is gotten by 
tidying the untidy merge.

-------

Have we decided on sets versus bags of triples in a graph?

Pat


-- 
---------------------------------------------------------------------
IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
phayes@ai.uwf.edu 
http://www.coginst.uwf.edu/~phayes

Received on Thursday, 11 October 2001 12:04:01 UTC