(Dagstuhl Edition, April 25, 2002)

uncommented document type definition: gxl-1.0.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

<!-- Extensions -->

<!ENTITY % gxl-attr-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.
-->

<!-- Attribute values -->

<!--
The val entity groups together attribute types available in GXL, which are the OCL standard data types bool, int, float, string, seq, set, and bag. The composite data types tuples (tup) and enumeration values (enum) are also available. The locator data type is used to to link to arbitrary hyper documents and identifiable XML elements.

Additional data types can be adding by redefining %value-extension;.
-->
 

<!-- gxl -->

<!--
This tag is used to delineate a GXL document, which may contain multiple graphs.  In particular, it is possible to keep an data (represented as a GXL graph), schema (represented as a GXL graph), meta schema (which is represented as a GXL graph), and so on in one document.

GXL uses XLink to refer to object possibly defined outside the current GXL document. This requires declaration of XLink namespace. The fixed xmlns:xlink attribute makes the prefix xlink available within the gxl element. The XLink attributes can now be used in GXL documents (including their definition in the DTD) as xlink:[attribute]

XML requires all identifiers used in one document (not in one graph) to be disjoint.  Consequently, identifiers must be unique across graphs in GXL documents containing multiple graphs. GXL forbids references between graph elements of different graphs in the same document except for type allocation and within locator attributes.

Further elements may be added to GXL documents by redefining %gxl-extension;. Further attributes of GXL documents can be added by redefining %gxl-attr-extension;.

-->

<!-- type -->

<!--
type elements denote XLink references to corresponding elements in the schema. They are modelled as simple XLinks, where the xlink:href attribute point to an element representing the required schema information. This link represents the isInstanceOf relationship. In the conceptual model, the references to type information is modeled by the aggregation relationships refersType (to a GXL element) and refersDocument (to the proper document). In GXL these associations are subsumed in the URI valued attribute xlink:href.

There are restrictions on what the correspendences that can be established using the type entity; in other words, the type entity cannot be used to create relationships arbitrarily between any entity in the instance graph and any entity in the schema.

Specifically, GXL requires type elements associated with a

• graph element to point to a schema graph (node element of type GraphClass (cf. GXL Meta Schema) in the schema graph)
• node element to point to a graph element representing a node type (node element of type NodeClass ((cf. GXL Meta Schema)  in the schema graph)
• edge element to point to a graph element representing an edge type (node element of type EdgeClass (cf. GXL Meta Schema) in the schema graph)
• relation element point to a graph element representing a relation type (node element of type RelationClass (cf. GXL Meta Schema)  in the schema graph)
• attr element point to a graph element representing an attribute type (node element of class Domain (cf. GXL Meta Schema)  in the schema graph)

<!-- graph -->

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

A graph may link to its schema, which is accessible by following the xlink:href link defined in its (optional) type element. 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. The edgeids  attribute is true for graphs where edges  and relations possess their own identifiers, it is "false" for graphs without edge  or relation identifiers. The hypergraph parameter allows the existence of hyperedges if its value is "true". Hyperedges are general relationships which connect an arbitrary number of elements instead of two elements (in the case directed or undirected edges). The edgemode attribute indicates how the edges or hyperedges of the current graph are interpreted. edgemode = "directed" or edgemode = "undirected" indicates that all edges and hyperedges are interpreted as directed or undirected edges. In this case, overwriting the interpretation of specific edges and relations is impossible. If edgemode = "defaultdirected" or edgemode = "defaultundirected",  it is possible to overwrite the interpretation of edge orientations for specific edges and relations.

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 -->

<!--
A node contains a possibly empty list of attributes, and an optional list of graphs.

A node may link to its node type, using the xlink:href link defined in its (optional) type element. GXL requires the target element to define a node type in the corresponding schema graph. Finally, a node has a node unique identifier id.

Graph 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.

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 -->

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

An edge may link to its edge type, which is accessible by following the xlink:href link defined in its (optional) type element. GXL requires the target element to define an edge type in the corresponding schema graph.  Edges may have an edgeid (mandatory for graphs with edgeids = "true").

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 graphs where edges must be traverse in a fixed order, 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 where it does not conflict with the edgemode attribute of  the surrounding  graph element.  If surrounding graph has been set to edgemode = "directed" or edgemode = "undirected" the edge orientation MUST follow this specification. If edgemode = "defaultdirected" or edgemode = "defaultundirected", this predefined orientation can overwritten using the isdirected attribute.

Graph 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 -->

<!--
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 rel type, which is accessible by following the xlink:href relend defined in its (optional) type element. GXL requires that the element which is accessible by this xlink defines a relation type in the corresponding schema graph. Relations may possess an edge id.

Each rel contains  a possibly empty list of attributes, an optional list of graphs, 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 where it does not conflict with the edgemode attribute of  the surrounding  graph element.  If the surrounding graph has been set to edgemode = "directed" or edgemode = "undirected" the relation orientation must follow this specification. If edgemode = "defaultdirected" or edgemode = "defaultundirected", this predefined orientation can be overwritten using the isdirectedattribute. Please note, that graphs are directed by default while relations are undirected by default. Thus, we recommend to define the edgemode for relations explicitly.

Graph 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 -->

<!--
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 (e.g. for layout data on the instance level).  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. Although the role attribute is defined as optional, the GXL Validator expects that all relation ends have a role and prints an error otherwise.

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;.
-->

<!-- attr -->

<!--
An attribute has a name and a value part. GXL provides values from the OCL standard types (bool, int, float, string, seq, set, and bag), as well as tuple and enum, and values which define references to other documents or elements (locator). Attributes may in turn have attributes (e.g. for storing layout).

The kind attribute is provided to distinguish between different varieties of attributes, for example,  to mark attributes as derived. GXL also optionally supports direct access to attributes by unique attribute identifiers.
-->

<!-- locator -->

<!--
Locators provide XLinks (the URI attribute defined in the conceptual model as implemented by XLink) to additional documents or document elements. Those values are used for both referencing arbitrary web documents and other graphs  and their elements (nodes, edges, rel).
-->

<!-- atomic values -->

<!--
Atomic values describe boolean, integer, real and string values.  GXL uses the grammar rules from Java for the basic types.
 

• Legal values for bool are true and false (lower case).
• Legal ints (INT) and floats (FLOAT) are decimal numbers and are represented using the following regular expression.

• Strings are encoded using Unicode and inherit further restrictions are from XML.

<!-- enumeration value -->

<!--
Values of an enumeration type
-->

<!-- composite values -->

<!--
GXL supports sequence, set, bag, and tuple container values. Sequences, sets and bags contain further values. All components within a container must have the same type (values).
-->
 

<!-- (S. Sim, A. Winter -  April 17, 2001) -->