GXL Ric Holt , Andy Schürr, Susan Elliott Sim, Andreas Winter
Graph eXchange Language


    Background
    Graph Model
    Examples



    DTD




    Metaschema



    Tools
    Publications
    Links



    Change Requests
    Future
GXL 1.1 
Graph Module

(alpha release, December 6, 2002)

[gxl-1.1]  [attribute-module]

uncommented document type definition: gxl-1.1.dtd,  gxl-1.1_attribute.dtd,  gxl-1.1_graph.dtd

copyright by

  Andy Schuerr
    Real-Time Systems Lab
    Darmstadt University of Technology
    Merckstr. 25, D-64283 Darmstadt, Germany
    andy.schuerr@es.tu-darmstadt.de

  Susan Elliott Sim
    School of Information and Computer Science
    444 Computer Science Bldg.
    University of California, Irvine
    ses@ics.uci.edu

  Ric Holt
    Department of Computer Science
    University of Waterloo
    Waterloo N2L 3G1, Canada
    holt@plg.uwaterloo.ca

  Andreas Winter
    Institute for Software Technology
    University of Koblenz-Landau
    Universitaetsstrasse 1, D-56070 Koblenz, Germany
    winter@uni-koblenz.de

GXL has been developed to be an open standard.  No licensing or other legal arrangements are required  for its use, whether commercial and non-commercial.  The specification of GXL is copyright by its authors, to allow control of its evolution. The specification can be reproduced and used without charge, but with explicit acknowledgement of its authors.
-->

<!-- Extensions -->

<!ENTITY % graph-extension   "" >
<!ENTITY % node-extension    "" >
<!ENTITY % edge-extension    "" >
<!ENTITY % rel-extension     "" >
<!ENTITY % relend-extension  "" >
<!ENTITY % graph-attr-extension   "" >
<!ENTITY % node-attr-extension    "" >
<!ENTITY % edge-attr-extension    "" >
<!ENTITY % rel-attr-extension     "" >
<!ENTITY % relend-attr-extension  "" >

<!--
Predefined "empty" Macros for extending information to GXL documents. GXL provides extending  gxl, graph, node, edge, relation, value, and relend elements with further child objects ([element]-extension)  and with further attributes ([element]-attr-extension).

Extending GXL by redefining these macros facilitates specializations of GXL e.g. for graph transformation and graph drawing.

Warning: Using extensions results in a DTD that deviates from the predefined GXL standard. In general, extensions are not supported by GXL tools and should be used with care.
-->

<!-- graph -->

<!ELEMENT graph (attr* , ( node | edge | rel )* %graph-extension;) >

<!ATTLIST graph
    id                  ID       #REQUIRED
    type                CDATA    #IMPLIED
    role                NMTOKEN  #IMPLIED
    defaultDirected     (true | false) "true"
    dafaultAttrValidity (valid | unknown)    #REQUIRED
    %graph-attr-extension;
>

<!--
The attributes edgeids and hypergraph were deleted here, because they do not belong in the instance-level. If they are necissary, they can be defined as attributes in the graph schema. This was requested in CR #11 (Schema settled instance).

The attribute defaultDirected can be used to set the direction of edges that are not explicitly defined es directed or undirected. It replaces the attribute 'edgemode'.

The need for the defaultAttrValidity-attribute was discovered during a discussion on CR #9 (Attribute kinds). It indicates, whether the attributes of the graph are valid (that is the case when they are normal) or their validity is unknown (that is the case when they are derived). This dafault value can be overwritten by the validity attribute of the attribute element.
-->

<!--
The graph-tag is used to enclose a graph within a GXL document.

A graph may link to its schema, which is accessible by following the link defined in its (optional) type-attribute. GXL requires that the resource which is accessible by this link is a schema graph document (i.e. a GXL graph matching the GXL meta schema).  A graph contains a possibly empty list of attributes, and a possibly empty list of nodes, edges, or relations.

A role may be specified for graph, for example, if it is a component of a hierarchical graph.

By redefining %graph-extension; further sub-elements may be added to  graph elements. Further attributes of graphs can be added by redefining %graph-attr-extension;.
-->

<!-- node -->

<!ELEMENT node (attr*, (graph|graphref)* %node-extension;) >

<!--
According to CR #3 (Hierarchical Graphs), nodes may have graphrefs, which are links to other graphs to relize graph-hierarchy.
-->


<!ATTLIST node
    id          ID       #REQUIRED
    type        CDATA    #IMPLIED
    order       CDATA    #IMPLIED

<!--
CR #13 (explicit elementorder) requests the possibility to give the graph-elements an order besides their implicit order (occurance in the gxl-file). The order-attribute may contain a number to give the according elements an explicit order. This attribute is optional, so there may be elements that are not ordered explicitly. Each ordering-number may appear only once.
-->

    %node-attr-extension;
>

<!--
A node contains a possibly empty list of attributes, and an optional list of graphs or graphrefs. Graph elements and graphref elements associated to a node, represent graphs on a lower level of hierarchy. A node can be associated with multiple child graphs. Their structure has to follow the graph class specifying the type of the sub graph.

A node may link to its type using the link defined in its (optional) type attribute. Type-links in graph-elements are local links within the schema-document that is linked via the graph's type-link. Thus, the type attribute for nodes, edges and rels may only be used if it is used for graph as well. GXL requires the target element to define a node type in the corresponding schema graph. Finally, a node has a node unique identifier id.

By redefining %node-extension; further sub elements may be added to  node elements. Further attributes of node elements can be added by redefining %node-attr-extension;.
-->

<!-- edge -->

<!ELEMENT edge (attr*, (graph|graphref)* %edge-extension;) >
<!ATTLIST edge
    id            ID       #IMPLIED
    type        CDATA       #IMPLIED
    order       CDATA      #IMPLIED

<!--
CR #13 (explicit elementorder) requests the possibility to give the graph-elements an order besides their implicit order (occurance in the gxl-file). The order-attribute may contain a number to give the according elements an explicit order. This attribute is optional, so there may be elements that are not ordered explicitly. Each ordering-number may appear only once.
-->

    from          IDREF    #REQUIRED
    to            IDREF    #REQUIRED

<!--
We chose not to change the attributes from and to from #REQUIRED to #IMPLIED. This was requested in CR #15 (partial graphs) to allow edges to come from or go to nothing. Since edges are nothing more than a special case of relation (a two-end-relation), GXL already provides this feature. Thus, a one-end-relation should be used to store partial graphs.
-->


    fromorder     CDATA    #IMPLIED
    toorder       CDATA    #IMPLIED
    isdirected    ( true | false ) #IMPLIED
    %edge-attr-extension;
>

<!--
An edge is a special binary relationship. (In contrast to relends, edges are first class GraphElements.)

An edge may link to its type, which is accessible by following the link defined in its (optional) type attribute. The type-link is a local link within the graph-schema-document. This attribute may only be used in combination with the type attribut of the graph element. GXL requires the target element to define an edge type in the corresponding schema graph. 

Each edge contains a possibly empty list of attributes, and an optional list of graphs.

The two graph elements (node, edge, relation) connected by an edge are accessed by following the reference defined in the from- and to-attributes. GXL only allows from/to connections within the same GXL graph element, including components of hierarchical graphs. Those edges point from the graph element referenced in the from attribute to the graph element referenced in the to attributes.

In ordered graphs, the ordering of incidences is recorded using the fromorder and toorder attributes.  The order of incidence on the entity that the edge came from is given by the fromorder, and the order of incidence on the entity that the edge is going to is given toorder attribute. Since incidence information is stored on the edges (and relends), the collection of  values in the fromorder and toorder attributes of all edges (and endorder attributes of all relends) incident to a node must define a proper ordering of  these incidences. The values of fromorder and toorder are required to be numbers.

The isdirected attribute is used to specify an edgemode (directed or undirected) for an edge, overwriting the default edgemode (defaultDirected attribute) of  the surrounding graph element. 

Graph elements or graphref elements are associated with an edge to represent graphs on a lower level of hierarchy. An edge can be associated with multiple child graphs. Their structure has to follow the graph class specifying the type of the sub graph.

By redefining %edge-extension; further sub-elements may be added to edge elements. Further attributes of edge elements can be added by redefining %edge-attr-extension;.
-->

<!-- rel -->

<!ELEMENT rel (attr*, (graph|graphref)*, relend* %rel-extension;) >
<!ATTLIST rel
    id          ID            #IMPLIED
    type        CDATA         #IMPLIED
    order       CDATA         #IMPLIED

<!--
CR #13 (explicit elementorder) requests the possibility to give the graph-elements an order besides their implicit order (occurance in the gxl-file). The order-attribute may contain a number to give the according elements an explicit order. This attribute is optional, so there may be elements that are not ordered explicitly. Each ordering-number may appear only once.
-->

    isdirected    ( true | false ) #IMPLIED
    %rel-attr-extension;
>

<!--
The rel element allows the definition of n-ary relationships, which connect multiple graph elements. In graph theory, these relations are usually called hyperedges (a database designer would prefer the name "table").

A rel may link to its type, which is accessible by following the link defined in its (optional) type element. The type-link is a lokal link within the schema-document. This attribute may only be used in combination with the type-attribute of the according graph element. GXL requires that the element which is accessible by the type-link defines a relation type in the corresponding schema graph.

Each rel contains  a possibly empty list of attributes, an optional list of graphs or graphrefs, and a possibly empty list of incident relation ends (relend). These relends are often also called "tentacles" (or "columns" by a database designer).  GXL distinguishes between incoming and outgoing relends.

Further sub-elements may be added to relation elements, by redefining %rel-extension; .

The isdirected attribute is used to specify an edgemode (directed or undirected) for a relation, overwriting the default edgemode (defaultDirected attribute) of  the surrounding  graph element.

Graph elements or graphref elements associated to a relation represent graphs on a lower level of hierarchy. An relation can be associated with multiple child graphs. Their structure has to follow the graph class specifying the type of the sub graph.

By redefining %rel-extension; further sub-elements may be added to rel elements. Further attributes (of relation elements) can be added by redefining %rel-attr-extension;.
-->

<!-- relend -->

<!ELEMENT relend (attr* %relend-extension;) >
<!ATTLIST relend
    target      IDREF                 #REQUIRED
    role        NMTOKEN               #IMPLIED
    direction   ( in | out | none)    #IMPLIED
    startorder  CDATA                 #IMPLIED
    endorder    CDATA                 #IMPLIED
    %relend-attr-extension;
>
 

<!--
A rel's relation end list defines the list of connected graph elements. In contrast to edges, relends are not first class GraphElements.

A relend may have its own attributes.  Further sub-elements may be added to relend elements by redefining %relend-extension;.

A single relend element defines an incidence together with its optional role (name/tentacle/relend name) and direction according the covering relation element.

GXL distinguishes between incoming and outgoing relends.  Relends with direction = "in" model tentacles pointing into the relation, and relends with direction = "out" model tentacles pointing out of the relation. Missing direction value or direction = "none" indicates undirected tentacles. A direction attribute is required for relends contained in a relation element with isdirected = "true". They are ignored  for those relends contained in a relation element with isdirected ="false".  The same holds for those relations whose orientation is inherited from the surrounding graph element.

The target attribute refers to those graph elements which are incident to the parent rel. To facilitate relations between edges and rel's the references are not restricted to node elements only. Here GXL provides node, edge and rel elements.

The ordering of relends according their target (association end) is given by the endorder attribute.  The ordering of relends according their incident relation (association start) is given by the startorder attribute. The incidence order for a given node is given in by the collection of all endorder attributes of relends (and fromorder and toorder attributes of edges) incident to a the node; these attributes together must define a proper ordering of  incidences. Analogously, all values of startorder attributes of relends incident to a given relation have to define a proper ordering. The values of startorder and endorder must be numbers.

Further attributes (of relend elements) can be added by redefining %relend-attr-extension;.
-->

<!-- graphref -->

<!ELEMENT graphref EMPTY >
<!ATTLIST graphref
    xlink:type       (simple) #FIXED   "simple"
    xlink:href       CDATA    #REQUIRED
>

<!--
According to CR #3 (Hierarchical Graphs), the graphref-element is another possibility to represent graph-hierarchy. The xlink:href-attribute contains the url that points to the graph-element that represents the inner graph.
-->

<!-- (O. Heinen -  December 6, 2002) -->. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

top
July 17, 2002

[change log]
[printable version of this page]