From: Pat Hayes <phayes@ai.uwf.edu>

Date: Thu, 11 Oct 2001 11:04:03 -0500

Message-Id: <p05101059b7eb5f110b00@[205.160.76.193]>

To: w3c-rdfcore-wg@w3.org

Cc: pfps@research.bell-labs.com

Date: Thu, 11 Oct 2001 11:04:03 -0500

Message-Id: <p05101059b7eb5f110b00@[205.160.76.193]>

To: w3c-rdfcore-wg@w3.org

Cc: pfps@research.bell-labs.com

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/~phayesReceived on Thursday, 11 October 2001 12:04:01 EDT

*
This archive was generated by hypermail pre-2.1.9
: Wednesday, 3 September 2003 09:41:00 EDT
*