Describing Structure and Semantics of Graphs Using an RDF Vocabulary

John Punin
puninj@cs.rpi.edu
Mukkai Krishnamoorthy
moorthy@cs.rpi.edu

Abstract

The RDF Graph Modeling Language (RGML) is a W3C RDF vocabulary to describe graph structures, including semantic information associated with a graph. Viewing general graphs as Web resources, RGML defines graph, node, and edge as RDF classes and attributes of graphs (such as label and weight) as RDF properties. Some of these RDF properties establish relationships between graph, node, and edge instances. RDF Statements about graph elements involve subjects, predicates and objects. Subjects and predicates are RDF Resources, while objects are either RDF Resources or RDF Literals. RGML uses the XML Schema datatypes for RDF Literals. RGML can be easily combined with other RDF vocabularies, for example, to add Dublin Core properties. RGML is very useful for describing webgraphs (the structure of a web site), web collections, and sitemaps.

Keywords: RDF; Trees/Graphs

John Punin

Mukkai Krishnamoorthy

Describing Structure and Semantics of Graphs Using an RDF Vocabulary

John Punin [Rensselaer Polytechnic Institute, Department of Computer Science]
Mukkai Krishnamoorthy [Rensselaer Polytechnic Institute, Department of Computer Science]

Extreme Markup Languages 2001® (Montréal, Québec)

Copyright © 2001 John Punin and Mukkai Krishnamoorthy. Reproduced with permission.

Introduction

We present the RDF Graph Modeling Language (RGML), a W3C RDF vocabulary [RDF] to describe graph structures. General graphs can be seen as Web resources. RGML defines graph, node, and edge as RDF classes and attributes of graphs, such as label and weight, as RDF properties. Some of these RDF properties establish relationships between graph, node, and edge instances. Hence, a graph instance "knows" which node and edge instances belong to this graph. There is no restriction on the number of graph, node, and edge instances that can be defined in a RGML file. Neither is there a restriction about nodes and edges shared between several graphs. Graphs can be included in other graphs; such graphs are called subgraphs. We use RDF Schema [RDFS] to provide with the definition of RGML classes and properties. RGML can be easily combined with other RDF vocabularies to add new properties, for example, you can add a Dublin Core [DC] dc:title property to a node instance to assign a string title to a node.

Several examples in this paper show how easy it is to describe different kind of graphs using the RGML vocabulary. Our main interest is to describe webgraphs [WWWPAL]. A webgraph describes the structure of a web site where the nodes are web pages and the edges are hyperlinks. We use the Dublin Core [DC] vocabulary to add information to nodes (web pages) such as dc:title (title of the web page), dc:format (mime of the web page), and dc:date (date of creation of the web page). Using RGML we can also define web collections (a collection of web pages that represent one document) as subgraphs of a webgraph. Site-maps can also be seen as graph instances; hence RGML is a good candidate for describing site-maps.

Motivation

XML [XML] and XML Schema [XMLSCHEMA] provide a syntactic description of an underlying document. The existing XML vocabularies designed to describe graph structures [GRAPHXML] [GXL] [XGMML] provide a means to describe structural information about nodes, edges, subgraphs, etc. RGML, based on the W3C RDF/XML model, describes the semantics of graphs, as well as structural information. RGML files are written with the XML syntax and the semantics use the RDF model. By using RGML, one can describe the graph structures and add statements to describe the elements of the graph. Two graphs may have the same structure even though one may describe network topology while the other may describe a web site. The metadata related to these graphs are different. The RDF model permits the combination of different metadata using XML Namespaces [XMLNS], so it is possible to differentiate between several types of graphs. RGML describes the semantics of an abstract graph based on the appropriate vocabulary. So, for example, when we describe a webgraph, we use the vocabulary of dublin core. The most interesting aspect of RGML is that the semantics of an arbitrary graph can be specified using RDF.

RGML Datatypes

RDF Statements about graph elements involve subjects, predicates and objects. Subjects and predicates are RDF Resources, while objects are either RDF Resources or RDF Literals. It is not possible to distinguish the datatypes of RDF Literal values and hence RGML adopts the XML schema datatypes. RGML follows the same syntax given by DAML+OIL ontology markup language [DAML]. The core RGML datatypes are integer, boolean and string datatypes. These datatypes are the range (properties map from a domain to range.) for some RGML properties.

RGML Classes

The RGML classes of a general graph are Graph, Node, and Edge. Properties of these classes allow to establish relationship of these three classes. This will enable a graph instance which relates with several node and edge instances. Two node instances relate with an edge instance.

Graph Class

The Graph class is a RDF class that defines a general graph. This is the Graph class that is the domain of the RDF properties: label and directed. The nodes and edges RDF properties help to relate instances of the Graph class with instances of Node and Edge classes. Other kind of graphs such as webgraphs, RDF graphs, and network graphs can be subclasses of this Graph Class.

  <rdfs:Class rdf:ID="Graph" 
    rdfs:label="Graph"
    rdfs:comment="A Graph Description">
    <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/>
  </rdfs:Class>

Node Class

The Node class is an RDF class that defines a general node. The label and weight RDF properties have Node class as domain. All nodes of a graph are instances of these class. Webnodes (web pages) of a webgraph can be subclasses of the Node class.

  <rdfs:Class rdf:ID="Node" 
    rdfs:label="Node"
    rdfs:comment="A Node Description">
    <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/>
  </rdfs:Class>

Edge Class

The Edge class is a RDF Class that defines a general edge. The label and weight RDF properties are related to the Edge class. The source and target RDF properties of the Edge class allow it to relate two node instances or, in case of a hypergraph, many node instances. (The instances of edges that have a list of nodes are called hyperedges. A hyperedge is defined as a subset of a set of nodes. Graphs that contain hyperedges are called hypergraphs. ) Webedges (Hyperlinks) of a webgraph can be subclasses of the Edge class.

  <rdfs:Class rdf:ID="Edge" 
    rdfs:label="Edge"
    rdfs:comment="An Edge Description">
    <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/>
  </rdfs:Class>

RGML Properties

The domain of the RGML properties are the Graph, Node and Edge RDF classes. These properties allow to relate instances of the RGML classes to build the structure of a general graph.

label Property

The label property is a global property for all instances of RGML classes. It gives a unique string identifier to the instances of the graphs, nodes and edges.

 <rdf:Property ID="label"
    rdfs:label="label"
    rdfs:comment="Text representation of the graph elements">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Node"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>
 </rdf:Property>

directed Property

The directed property has a Boolean range and a Graph domain. The values that can be assigned to this property are either true or false. This indicates whether the graph is directed or not. Mixed graphs allow directed and undirected edges in the same graph. The directed property also belongs to a specific edge instance to indicate whether that edge is directed or not. This edge property will allow one to describe mixed graphs.

 <rdf:Property ID="directed"
    rdfs:label="directed"
    rdfs:comment="Boolean value to indicate whether the Graph is directed or not">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#boolean"/>
 </rdf:Property>

nodes Property

The nodes property is an RDF Bag list of the node instances that belongs to the graph. This gives an idea of inclusion so we can determine what nodes are members of the graph. The nodes property can belong to the Edge class. The instances of edges that have a list of nodes are called hyperedges. A hyperedge is defined as a subset of a set of nodes. Graphs that contain hyperedges are called hypergraphs. If the hypergraph is directed, the nodes property of the hyperedges is an RDF Seq. The RDF Seq gives an order to the list of nodes in the hyperedge.

 <rdf:Property ID="nodes"
   rdfs:label="Nodes"
   rdfs:comment="List of the nodes belong to the graph">
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/>
 </rdf:Property>

edges Property

The edges property is an RDF Bag list of the edge instances that belongs to the graph. This gives an idea of inclusion so we can determine what edges are members of the graph.

 <rdf:Property ID="edges"
   rdfs:label="Edges"
   rdfs:comment="List of the edges belong to the graph">
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Bag"/>
 </rdf:Property>

graphs Property

The graphs property is an RDF Bag list of the subgraph instances of the graph parent. By using this property, we can relate subgraphs with the graph that they originated from.

 <rdf:Property ID="graphs"
   rdfs:label="Subgraphs"
   rdfs:comment="List of subgraphs belong to the graph">
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Bag"/>
 </rdf:Property>

weight Property

The weight property belongs to node and edge instances. The weight is usually a numerical value assigned to a node or edge in a weighted graph.

 <rdf:Property ID="weight"
    rdfs:label="weight"
    rdfs:comment="Value (usually numerical) to show the node or edge weight">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Node"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>
 </rdf:Property>

source Property

The source property is used to indicate the source node instance of a edge instance.

 <rdf:Property ID="source"
    rdfs:label="source"
    rdfs:comment="The rdf:ID the source node of the edge">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/>
 </rdf:Property>

target Property

The target property is used to indicate the target node instance of an edge instance.

 <rdf:Property ID="target"
    rdfs:label="node"
    rdfs:comment="The rdf:ID of the target node of the edge">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/>
 </rdf:Property>

RGML Examples

Simple Graph Example

Figure 1: Example: simple graph
[Link to open this graphic in a separate page]

This is a simple graph with three nodes and two edges. See 1 for a graphical representation of this simple graph.

<?xml version="1.0" encoding="utf-8"?> 

<rdf:RDF 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
  xmlns="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:rgml="http://purl.org/puninj/2001/05/rgml-schema#"
> 

<Graph rdf:ID="g1" rgml:directed="true">
   <nodes>
      <rdf:Bag>
         <rdf:li resource="#n1"/>
         <rdf:li resource="#n2"/>
         <rdf:li resource="#n3"/>
      </rdf:Bag>
   </nodes>

   <edges>
      <rdf:Bag>
         <rdf:li resource="#e1"/>
         <rdf:li resource="#e2"/>
      </rdf:Bag>
   </edges>
</Graph>

<Node rdf:ID="n1"/>
<Node rdf:ID="n2"/>
<Node rdf:ID="n3"/>

<Edge rdf:ID="e1">
    <source rdf:resource="#n1"/>
    <target rdf:resource="#n2"/>
</Edge>
<Edge rdf:ID="e2">
    <source rdf:resource="#n1"/>
    <target rdf:resource="#n3"/>
</Edge>

</rdf:RDF>

Webgraph Example

Figure 2: Example: webgraph
[Link to open this graphic in a separate page]

This graph is a webgraph where the two nodes represent two web pages and the edges represent the hyperlinks between these web pages. We used the Dublin Core vocabulary to add properties to the nodes, such as dc:title, dc:format, and dc:date. The dc:title indicates the title of the web page, the dc:format indicates the mime type of the web page, and the dc:date indicates the date of creation of the web page. The rgml:weight property indicates the size in bytes of the web page. The rgml:label of the node is used to hold the URL of the web page and the rgml:label of the edge is used to hold the anchor text of the hyperlink. See 2 for a graphical representation of this webgraph.

<?xml version="1.0" encoding="utf-8"?> 

<rdf:RDF 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
  xmlns="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:rgml="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:dc="http://purl.org/dc/elements/1.1/"> 

<Graph rdf:ID="g1" rgml:directed="true">
   <nodes>
      <rdf:Bag>
         <rdf:li resource="#n1"/>
         <rdf:li resource="#n2"/>
         <rdf:li resource="#n3"/>
      </rdf:Bag>
   </nodes>

   <edges>
      <rdf:Bag>
         <rdf:li resource="#e1"/>
         <rdf:li resource="#e2"/>
      </rdf:Bag>
   </edges>
</Graph>

<Node rdf:ID="n1" rgml:label="http://www.cs.rpi.edu/" 
      rgml:weight="3678">
  <dc:title>Rensselaer Computer Science Department</dc:title>
  <dc:date>2001-03-01</dc:date>
  <dc:format>text/html</dc:format>
</Node>
<Node rdf:ID="n2" rgml:label="http://www.cs.rpi.edu/people/" 
      rgml:weight="10611">
  <dc:title>People at Rensselaer Computer Science Department</dc:title>
  <dc:date>2001-02-26</dc:date>
  <dc:format>text/html</dc:format>
</Node>
<Node rdf:ID="n3" rgml:label="http://www.cs.rpi.edu/courses/"
      rgml:weight="6968">
  <dc:title>Courses at Rensselaer Computer Science Department</dc:title>
  <dc:date>2001-01-25</dc:date>
  <dc:format>text/html</dc:format>
</Node>

<Edge rdf:ID="e1" rgml:label="Courses">
    <source rdf:resource="#n1"/>
    <target rdf:resource="#n2"/>
</Edge>
<Edge rdf:ID="e2" rgml:label="People">
    <source rdf:resource="#n1"/>
    <target rdf:resource="#n3"/>
</Edge>

</rdf:RDF>

RDF Graph Example

Figure 3: Example: RDF graph
[Link to open this graphic in a separate page]

This is the RGML description of the famous RDF Graph [RDF] that represents the statement: "Ora Lassila is the creator of the resource http://www.w3.org/Home/Lassila". See 3 for a graphical representation of this simple graph.

<?xml version="1.0" encoding="utf-8"?> 

<rdf:RDF 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
  xmlns="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:rgml="http://purl.org/puninj/2001/05/rgml-schema#">

<Graph rdf:ID="g1" rgml:directed="true">
   <nodes>
      <rdf:Bag>
         <rdf:li resource="#n1"/>
         <rdf:li resource="#n2"/>
      </rdf:Bag>
   </nodes>

   <edges>
      <rdf:Bag>
         <rdf:li resource="#e1"/>
      </rdf:Bag>
   </edges>
</Graph>

<Node rdf:ID="n1" rgml:label="http://www.w3.org/Home/Lassila"/>
<Node rdf:ID="n2" rgml:label="Ora Lassila"/>

<Edge rdf:ID="e1" rgml:label="Creator">
    <source rdf:resource="#n1"/>
    <target rdf:resource="#n2"/>
</Edge>

</rdf:RDF>

Hypergraph Example

A hypergraph is defined as a set of vertices and a set of edges called hyperedges. A hyperedge is a subset of the set of vertices. If the hypergraph is directed the hyperedge is an ordered set of vertices and, if the hypergraph is undirected, the hyperedge is an unordered set of vertices. The following RGML example describes a directed hypergraph.

<?xml version="1.0" encoding="utf-8"?> 

<rdf:RDF 
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
  xmlns="http://purl.org/puninj/2001/05/rgml-schema#"
  xmlns:rgml="http://purl.org/puninj/2001/05/rgml-schema#"
> 

<Graph rdf:ID="g1" rgml:directed="true">
   <nodes>
      <rdf:Bag>
         <rdf:li resource="#n1"/>
         <rdf:li resource="#n2"/>
         <rdf:li resource="#n3"/>
         <rdf:li resource="#n4"/>
      </rdf:Bag>
   </nodes>

   <edges>
      <rdf:Bag>
         <rdf:li resource="#e1"/>
         <rdf:li resource="#e2"/>
      </rdf:Bag>
   </edges>
</Graph>

<Node rdf:ID="n1"/>
<Node rdf:ID="n2"/>
<Node rdf:ID="n3"/>
<Node rdf:ID="n4"/>


<Edge rdf:ID="e1">
    <source rdf:resource="#n1"/>
    <target rdf:resource="#n2"/>
</Edge>

<Edge rdf:ID="e2">
   <nodes>
      <rdf:Seq>
         <rdf:li resource="#n2"/>
         <rdf:li resource="#n3"/>
         <rdf:li resource="#n4"/>
      </rdf:Seq>
   </nodes>
</Edge>

</rdf:RDF>

Adding graph rules using RGML and Logic primitives

Tim Berners-Lee has designed a new language, Notation 3 [NOT3], to describe the RDF data model. Using Notation 3, we can add logic primitives to RGML to generate RDF properties that are commonly used to describe graph information such as, cycle, adjacent, path, etc. We will add simple rules to define two graph concepts: adjacency and paths between nodes. The latter is a modification of the example given by the Euler proof engine [EULER].

Two nodes are adjacent if they are connected by an edge. This can be expressed using two simple rules, where e is an edge, and u and v are nodes:

forall (e, u, v) : source(e,u) and target(e,v) -> adjacent(u,v) 
forall (u,v) : adjacent(u,v) -> adjacent(v,u) 

Using Notation 3 we can express these rules as:

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix rgml: <http://purl.org/puninj/2001/05/rgml-schema#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .
@prefix : <rgml_rules#> .

:adjacent  rdfs:domain rgml:Node; rdfs:range rgml:Node.

{{:e rgml:source :u. :e rgml:target :v.} log:implies { :u :adjacent :v } } 
    a log:Truth; log:forAll :e, :u, :v.
{{ :u :adjacent :v. } log:implies { :v :adjacent :u. }; } 
   a log:Truth; log:forAll :u, :v.

A path is a sequence of consecutive nodes in a graph. Two nodes, u and v, are said to be consecutive if there is a directed edge from u to v, where u is the parent of v (rule 1). The second rule states that if the node u is the parent of the node v, there is a directed path from u to v. The third, a recursive rule, states the condition for the existence of a path from nodes u to w. These three rules are the following (where u, v, w are nodes; e is an edge and g is a graph):

forall (g,e,u,v) : g is directed and source(e,u) and target(e,v) -> parent(u,v) 
forall (g,u,v) : g is directed and parent(u,v) -> path(u,v) 
forall (g,u,v,w) : g is directed and parent(u,v) and path(v,w) -> path(u,w) 

Using Notation 3 we can express these rules as:

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix rgml: <http://purl.org/puninj/2001/05/rgml-schema#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .
@prefix : <rgml_rules#> .

:parent  rdfs:domain rgml:Node; rdfs:range rgml:Node.
:path  rdfs:domain rgml:Node; rdfs:range rgml:Node.

{{ :g rgml:directed "true". :e rgml:source :u. :e rgml:target :v.} 
   log:implies { :u :parent :v. }; } 
   a log:Truth; log:forAll :e, :u, :v , :g.

{{ :g rgml:directed "true". :u :parent :v} 
   log:implies {:u :path :v}} 
   a log:Truth; log:forAll :g, :u, :v.

{{ :g rgml:directed "true". :u :parent :v. :v :path :w} 
   log:implies {:u :path :w}} 
   a log:Truth; log:forAll :g, :u, :v, :w.

To express the rules we use the logic properties log:implies and log:forAll that are part of the logic schema [NOT3]. We use the cwm engine [CWM] to process these rules on a simple graph expressed in RGML.

Conclusion

In this paper, we defined a new RDF vocabulary (RGML) to describe the structure and semantics of graphs. We showed how to combine different vocabularies in order to add rich metadata to the graph components, and we defined logic rules to express graph properties. We are currently expanding our logic rules to express many other graph properties. Future RGML modules will add new vocabularies to describe different types of graphs, such as webgraphs, network graphs, organization charts, UML graphs, etc.

RDF/XML Serialization of the RGML RDF Schema

<?xml version="1.0" ?> 
<!-- 
     RDF Schema declaration for RDF Graph Modeling Language (RGML) 1.0 
     <http://purl.org/puninj/2001/05/rgml-schema#>
-->
<rdf:RDF 
     xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
     xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#">

<!-- Class Declarations -->

<!-- Graph Class declaration -->

  <rdfs:Class rdf:ID="Graph" 
    rdfs:label="Graph"
    rdfs:comment="A Graph Description">
    <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/>
  </rdfs:Class>

<!-- Node Class declaration -->

  <rdfs:Class rdf:ID="Node" 
    rdfs:label="Node"
    rdfs:comment="A Node Description">
    <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/>
  </rdfs:Class>

<!-- Edge Class declaration -->

  <rdfs:Class rdf:ID="Edge" 
    rdfs:label="Edge"
    rdfs:comment="An Edge Description">
    <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/>
  </rdfs:Class>

<!-- Property declarations -->

<!-- Global Properties -->

 <rdf:Property ID="label"
    rdfs:label="label"
    rdfs:comment="Text representation of the graph elements">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Node"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>
 </rdf:Property>

<!-- Graph Properties -->

 <rdf:Property ID="directed"
    rdfs:label="directed"
    rdfs:comment="Boolean value to indicate whether the Graph is directed or not">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#boolean"/>
 </rdf:Property>

 <rdf:Property ID="nodes"
   rdfs:label="Nodes"
   rdfs:comment="List of the nodes belong to the graph">
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Resource"/>
 </rdf:Property>

 <rdf:Property ID="edges"
   rdfs:label="Edges"
   rdfs:comment="List of the edges belong to the graph">
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Bag"/>
 </rdf:Property>

 <rdf:Property ID="graphs"
   rdfs:label="Subgraphs"
   rdfs:comment="List of subgraphs belong to the graph">
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Graph"/>
   <rdfs:range rdf:resource="http://www.w3.org/1999/02/22-rdf-syntax-ns#Bag"/>
 </rdf:Property>

<!-- Node Properties -->

 <rdf:Property ID="weight"
    rdfs:label="weight"
    rdfs:comment="Value (usually numerical) to show the node or edge weight">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Node"/>
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/>
 </rdf:Property>

<!-- Edge Properties -->

 <rdf:Property ID="source"
    rdfs:label="source"
    rdfs:comment="The rdf:ID the source node of the edge">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/>
 </rdf:Property>

 <rdf:Property ID="target"
    rdfs:label="target"
    rdfs:comment="The rdf:ID of the target node of the edge">
   <rdfs:isDefinedBy rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#"/> 
   <rdfs:domain rdf:resource="http://purl.org/puninj/2001/05/rgml-schema#Edge"/>
   <rdfs:range rdf:resource="http://www.w3.org/2000/01/rdf-schema#Resource"/>
 </rdf:Property>

</rdf:RDF>


Bibliography

[CWM] Tim Berners-Lee. Semantic Web Area for Play: Closed World Machine. http://www.w3.org/2000/10/swap/Overview.html, February, 2001.

[DAML] DARPA Agent Markup Language (DAML). http://www.daml.org/

[DC] S. Weibel, J.Kunze, C. Lagoze, and M. Wolf. Dublin Core Metadata for Resource Discovery, Internet RFC 2413. http://purl.oclc.org/dc/, 1998.

[EULER] Jos De Roo. Euler proof mechanism. http://www.agfa.com/w3c/euler/, June, 2001.

[GRAPHXML] Herman I, Marshall MS. GraphXML - An XML-based graph description format. Proceedings of the Symposium on Graph Drawing, 2000; 52-62

[GXL] R. C. Holt, A. Winter, A. Schurr. GXL: Towards a Standard Exchange Format Proceedings 7th Working Conference on Reverse Engineering (WCRE 2000)

[NOT3] Tim Berners-Lee. Notation 3. http://www.w3.org/DesignIssues/Notation3.html, April, 2001.

[RDF] O. Lassila and R. Swick. W3C, Resource Description Framework (RDF) Model and Syntax Specification. http://www.w3.org/TR/REC-rdf-syntax, 1999.

[RDFS] D. Brickley and R.V. Guha. W3C, Resource Description Framework (RDF) Schema Specification 1.0. http://www.w3.org/TR/rdf-schema/, 2000.

[WWWPAL] J. Punin, M. Krishnamoorthy. WWWPal System - A System for Analysis and Synthesis of Web Pages. In Proceedings of the WebNet 98 Conference, Orlando, November, 1998.

[XGMML] J. Punin, M. Krishnamoorthy. XGMML, Extensible Graph Markup and Modeling Language Specification, 1999. http://www.cs.rpi.edu/~puninj/XGMML/draft-xgmml.html

[XML] T. Bray, J. Paoli and C. M. Sperberg-McQueen, Extensible Markup Language (XML 1.0) - http://www.w3.org/TR/REC-xml, 2000.

[XMLNS] T. Bray, D. Hollander and A. Layman. Namespaces in XML, http://www.w3.org/TR/REC-xml-names, 1999.

[XMLSCHEMA] H. Thompson et al. XML Schema Part 1: Structures. http://www.w3.org/TR/xmlschema-1, 2001.



Describing Structure and Semantics of Graphs Using an RDF Vocabulary

John Punin [Rensselaer Polytechnic Institute, Department of Computer Science]
puninj@cs.rpi.edu
Mukkai Krishnamoorthy [Rensselaer Polytechnic Institute, Department of Computer Science]
moorthy@cs.rpi.edu