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


    Background
    Introduction
    FAQ
    Examples
    Publications




    DTD
    XML Schema




    Graph Model
    Metaschema




    Tool Catalogue
    Downloads




    Change Requests
    Future
    GXL 1.1

[3. Exchanging Graphs with GXL] << [Table of Contents] >> [5. Using GXL]

4 Exchanging Graph Schemas

(
4.1 GXL schemas as UML class diagrams | 4.2 GXL schemas represented as graphs | 4.3 GXL metaschema)

Graphs are used for describing objects (nodes) and their interrelationships (edges, hyperedges). In a particular application domain, it is commonly appropriate to constrain the form of the graph, for example by limiting the types of the nodes. A schema provides a means for describing and constraining the graph. In particular, a schema determines:

  • which node, edge, and hyperedge classes (types) can be used;
  • which relations can exist between nodes, edges, and hyperedges of given classes;
  • which attributes can be associated with nodes, edges and hyperedges;
  • which graph hierarchies are supported; and
  • which additional constraints (such as ordering of incidences, degree restrictions) have to be imposed.
These constraints specialize a graph to represent the domain of interest.

4.1 GXL schemas as UML class diagrams    [top]

This section explains how GXL schemas are written and used. We start by giving three example schemas, i) the schema in Figure 10 for use with the simple graph in Figure 2, ii) the schema in Figure 11 for use with the hypergraph in Figure 4, and iii) the schema in Figure 12 for use with the hierarchical graph in Figure 6. We also show how GXL schemas are exchanged using a particular form of a graph. The next section after this one shows how this format is itself described by another schema (by a metaschema).

Simple Schema Graph
Figure 10: Simple Schema Graph

As illustrated in Figure 10, Figure 11 and Figure 12, we can represent GXL schemas as UML class diagrams [57]. Each node, edge, or hyperedge of a particular type in the instance graph has a corresponding class in the schema diagram. The schema in Figure 10 has classes representing node classes (FunctionCall, Function, and Variable) used in Figure 2, and it has associations (isCaller, isCallee, isInput, and isOutput) representing edge classes. The edge class isCaller has an integer attribute named line, which reflects the fact that in Figure 2, isCaller edges are attributed with line numbers. The orientation of edges is depicted by a filled triangle [57, p. 155]. Multiplicities denote degree restrictions. Ordering of incidences is indicated by the keyword {ordered}.

The schema for the hypergraph in Figure 4 is given by Figure 11. The hyperedge's class is shown in Figure 11 as a diamond with attached tentacles. These tentacles can be annotated by multiplicity information to specify cardinalities, and by names indicating the roles of participating classes. The keyword {ordered} can be used to require ordering of tentacles in instance graphs.

Hypergraph Schema
Figure 11: Hypergraph Schema

The schema for the hierarchical graph in Figure 6 is given by Figure 12. This schema uses a UML stereotype <<GraphClass>> named asg (Abstract Syntax Graph) to distinguish classes containing subgraphs from (ordinary) node classes. Ownership of subgraphs is expressed by composition (filled diamond). Nodes of class Function can contain graphs of graph class asg.

Hierarchical Graph Schema
Figure 12: Hierarchical Graph Schema

4.2 GXL schemas represented as graphs    [top]

GXL provides a great deal of flexibility in the handling of various kinds of data, by allowing the user to transmit a graph's schema along with the graph itself. This is done by translating the schema so it becomes an ordinary graph and encoding this graph in GXL the same way that any other graph is handled.

Graph for schema in Figure 10
Figure 13: Graph for schema in Figure 10

Figure 13 shows the result of translating the schema in Figure 10 into a graph. Each node is translated to a corresponding node, for example, the Function node is translated to a NodeClass named Function. Each edge, attribute or attribute type is translated to a corresponding node, for example, the isCaller edge is translated to the node isCaller of type EdgeClass. The connections of isCaller edges are translated into edges of type to and from.

Attribute information is translated into hasAttribute and hasDomain edges. Multiplicities of associations are stored in limits attributes (infinity is represented by -1). The boolean attribute isOrdered indicates ordered incidences. Attribute types and extended concepts such as graph hierarchy, classes of hyperedges, aggregation and composition, generalization and default attribute values are modeled analogously.

Each schema has a node of type GraphClass which is attached by contains edges to all nodes which represent elements of the schema (see Figure 13). This node is referred to by data graphs which use this schema. Elements in a data graph refer to corresponding nodes in their schema graph. The GXL Validator [62] checks that data graphs conform to their schemas.

In contrast to the strategy proposed by XML Meta Data Interchange (XMI) [63], GXL schemas are not translated into XML documents based on MOF (Meta Object Facility) [64]. The MOF approach to representing UML class diagrams generates a new (and verbose) DTD for each diagram. In contrast, GXL uses the same DTD for all schemas. Consequently, both GXL instance data and schemas use the same DTD. This consistent (re-)use of the schema results in greater compatibility of GXL tools.

4.3 GXL Metaschema    [top]

Every GXL schema is translated into a graph having the same structure (same types of nodes, edges, etc.) In other words, there is a single GXL metaschema that gives the format of all GXL schemas. The class diagram in Figure 14 shows this GXL metaschema (except for the part defining attributes).

GXL Metaschema (attribute part omitted)
Figure 14: GXL Metaschema (attribute part omitted)

Attributes are added to GraphElementClasses by connecting them to AttributedElementClass. The definition of attribute structures supports the structured attributes used in GXL including the definition of default values. Generalization is provided for all GraphElementClasses by isA edges. GraphElementClasses containing subgraphs are associated with the representation of the lower level GraphClass by contains edges. The GraphClass contains those node, edge, and hyperedge classes representing its structure. Aggregation (AggregationClass) and composition (CompositionClass) are modeled by specializations of EdgeClasses.

As with instance graphs, GXL schema graphs have to comply to some constraints that cannot be expressed with class diagrams [62]. In addition to the constraints discussed in Section [3.4], the following conditions are imposed:

  • Schema graphs define graph classes. A schema graph contains at least one GraphClass node.
  • Generalization hierarchies are acyclic. A schema graph does not contain a cycle of isA edges.
  • Generalization is only permitted between classes of the same kind. In each schema graph isA edges only connect NodeClass nodes with other NodeClass nodes, EdgeClass nodes with others of its kind, and so on.

The GXL metaschema is itself a schema. Like all GXL schemas it is an instance of the GXL metaschema. It follows that that the GXL metaschema is its own schema.

[3. Exchanging Graphs with GXL] << [Table of Contents] >> [5. Using GXL]
top
July 17, 2002

[change log]
[printable version of this page]