GXL (1.0) Change Requests

While working with GXL (1.0) and building tools for GXL, some requests for extending or changing GXL emerged. These change requests are summarized on this page. The list is completed by some remarks concerning the status of change requests and the adoption into the next version of GXL.
[#1] XML Schema
[#2] Packages
[#3] Hierarchical graphs (graph valued attributes) and Schemadiscussion
[#4] Free Type attributes
[#5] Structs
[#6] Namespace
[#7] Public Identifier
[#8] Header
[#9] attribute kinds
[#10] XLink values
[#11] schema-setled instance
[#12] attributes of attributes
[#13] explicit elementorder
[#14] contains-constraint
[#15] partial graphs
[#15] implicit nodes
[#16] Multiplicities in Metaschema
[#17] zero or nothing and infinity
[#18] common classes
If you want to suggest further extensions to GXL, or request changes of GXL, please use the GXL mailinglist.
Thanks to all, who submitted change requests and helped us to improveGXL.

#1XML Schema[send us your comment on this CR]

Change Request by:

Description:

XML Schema is the upcoming XML-based language for describing document structures. XML Schema might replace XML document type definitions (DTD). In comparison to DTDs XML Schema offers additional support for defining document structures like using generalizations and defining (simple) constraints. Using XML Schema for defining the GXL documents might even offer a more sophisticated means for deriving spezializations of GXL (e.g. for graph transformation systems or graph drawing)

Status:

The structure of the next GXL-version will be described both in DTD and XML Schema.

#2Packages[send us your comment on this CR]

Change Request by:

Description:

Since GXL (or subparts) might be included into other graph based exchange formats, it seems reasonable to separate GXL subparts into various packages. At the 2nd GXL/GTXL meeting it was suggested to spread the GXL DTD in packages containing

#3Hierarchical graphs (graph valued attributes) and Schemadiscussion[send us your comment on this CR]

Change Request by:

Status:

During a meeting in Aachen in March 2002, the approaches 'graph valued attributes' and 'references to graphs' were dicussed. At the moment ist seems that both the attribute-solution and the reference-solution will become part of GXL 2. Including the current way of representing hierarchy (nested graphs) there will be three different hierarchy-solutions:

History

At the GXT/GTXL meeting various ways for representing hierarchical graphs were discussed:
  1. links to separate graphs or graph documents. In GXL this is done by using locator attributes). Disadvantage: these links can only be viewed in one direction (from origin to target)
  2. flagged edges. Edges of predefined types obtain a flag indicating that these edges represent hierarchy Disadvantage: The inner graph has to be calculated from the nodes reached by these edges. Here the (regular) edges between those nodes are not connected directly to the node containing a hierarchical graph. Graph hierarchies over edges requires hierarchy edges starting in edges.
  3. graphs as elements of nodes, edges, rels This version is realized in GXL 1.0.
  4. graph valued attributes All attributable objects might contain attributes of type graph. Mark Minas favors this representation.
Giorgio Busatto (Bremen) compared these approaches.

Schemadiscussion

There is currently a discussion whether a graph-element shall be seen as a graph. This would make graph-hierarchie much simpler.

""

open questions:

#4Free Type attributes[send us your comment on this CR]

Change Request by:

Description:

Some applications require to exchange attributes of types, whose type is only declared inside the application. E.g. an attribute is of a complex type, declared in a C++ program, but the type is not exported within the exchanged document. Things like these require means for exchanging attributes of freely defined types (e.g. a freeType tag).

#5Structs[send us your comment on this CR]

Change Request by:

Description:

The GXL 1.0 DTD does not offer clear support for exchanging struct attributes:
Example:
attr_group = { int_attr = 1, float_attr = 1.0 }
GXL 1.0:
< attr name="attr_group" >
  < attr name="int_attr" > < int > 1 < /int > < /attr >
  < attr name="float_attr" > < float > 1.0 < /float > < /attr >
  < !-- Value -- >
< /attr >

#6Namespace[send us your comment on this CR]

Change Request by:

Description:

Up to now, there is no unique namespace-URI suggested for GXL. Neither is there a possibility for using namspaces with GXL implemented in the dtd. Due to the known problems that occour when mixing namespace and dtd, it has to be discussed, in which way namespaces should be used with GXL.

#7Public Identifier[send us your comment on this CR]

Change Request by:

Description:

Boris suggests that a public identifier for GXL should be added, like

-//GXL//DTD GXL V1.0//EN .

#8Header[send us your comment on this CR]

Change Request by:

Description:

GXL should be added a header that contains information about the used GXL version and the tool that created the file, as well as attribute-value-pairs of any number.

< !ELEMENT header (attr*) >
< !ATTLIST header
  GXLVersion CDATA #IMPLIED
  generatorTool CDATA #IMPLIED
>

#9attribute kinds[send us your comment on this CR]

Change Request by:

Description:

Allow the definition of attribute kinds for graph schemas. These definitions shall not be used on the graph instance level. For GRAS/GXL three kinds of attributes are necessary Attributes of kind (1) need no special support in GXL since they are already contained in it. Support for attribute kinds (2) and (3) is lacking in GXL. Kind (2) is used to derive the value of an attribute based on the values of other graph elements. An example for this is the age of a person which can be computed from the birthday and today. This concept is supported in the UML by denoting attributes with "/". The problem with this is that it should be possible to exchange the function which is used to compute the derived value so that you do not only exchange a snapshot of the graph but also have the possibility to modify it without breaking the validity of the derieved attribute. Possible solutions: Kind (3) is used to model constant or frozen, as they are called in UML, values which cannot be modified in an instance graph. GXL supports this concept partially because it allows default values for attributes. But since there is no way to express that this value cannot be modified in the graph schema this has to be added.

Status:

During the meeting in Aachen we realized that the attribute kind is a schema information and doesn't belong in the instance level. The influence for the instance lies in the validity of the graph. If all derived attributes can be calculated the graph is valid, otherwise it's validity is unknown. That leads us to the necessity of a global Attribut 'attrValidity' that can hold the values 'valid' and 'unknown'.

< !ELEMENT gxl (graph* %gxl-extension;) >
< !ATTLIST gxl
  xmlns:xlink CDATA #FIXED "http://www.w3.org/1999/xlink"
  attrValidity (valid | unknown) #REQUIRED
  %gxl-attr-extension;
>

#10XLink values[send us your comment on this CR]

Change Request by:

Description:

The values of the XLinks should be reduced to the filename for the graph element and the target for all other emelents. This makes possible a hierarchie of graph-schemas.
currently:
< type xlink:href="filename#target"/ >
new:
graph: < type xlink:href="filename"/ >
other: < type xlink:href="target"/ >

#11schema-setled instance[send us your comment on this CR]

Change Request by:

Description:

The following schema-related information should not be stored in instance:

#12attributes of attributes[send us your comment on this CR]

Change Request by:

Description:

Attributes should have no attributes anymore. In the past, these attributes where only used to store layout-information for the representation of the attributes. Since we are searching for a sepearte layout-solution, such attributes are not necessary.

#13explicit elementorder[send us your comment on this CR]

Change Request by:

Description:

In GXL 1.0, the graphs and graphelements are ordered implicit by the sequence of their appearance in the GXL-file. In the next version, it should be possible to give the elements and graphs an explicit order.

#14contains-constraint[send us your comment on this CR]

Change Request by:

Description:

Contains-edges connect GraphClasses and GraphElementClasses - and maybe specialisations of GraphElementClasses. Andreas requests that those edges only connect to the top-classes of the hierarchy.

Status:

All GraphElementClasses are connected to the surrogat via contains-edges.

#15partial graphs[send us your comment on this CR]

Change Request by:

Description:

Gabriele suggests that GXL should allow storage of partial graphs. That is to say there may be edges that come from nothing or go to nothing, or come from and connect to nodes outside the graph. It would be necessary to make the from- and to-attribute in the DTD implied:

< !ELEMENT edge (type?, attr*, graph* %edge-extension;) >
< !ATTLIST edge
  id ID #IMPLIED
  from IDREF #IMPLIED
  to IDREF #IMPLIED
  fromorder CDATA #IMPLIED
  toorder CDATA #IMPLIED
  isdirected ( true | false ) #IMPLIED
  %edge-attr-extension;
>

#15implicit nodes[send us your comment on this CR]

Change Request by:

Description:

A node, that doesn't exist in a graph but is connected through an edge that is part of the graph should be generated automaticly.

#16Multiplicities in Metaschema[send us your comment on this CR]

Change Request by:

Description:

The GXL-Metaschema requires that each GraphElementClass-object is contained in exactly one GraphClass-object. Thus, with GXL 1 it is not possible to define node, edge or rel-classes to be contained as multiple graphs e.g. within a hierarchical graph having disjopint "inner graphclasses" for certain graph-elemenmts. In order to provide using node, edge and rel-classes in multiple Graphclasses, the multiplicity of the contains-association GraphClass -(1)-contains-(0..n)-> GraphElementClass has to be changed to GraphClass -(1..n)-contains-(0..n)-> GraphElementClass. This change also requires changing the composition into an aggregation.

#17zero or nothing and infinity[send us your comment on this CR]

Change Request by:

Description:

GXL needs some well defined way to express undefined values. We need a notation of "undefined" for all basic value domains (bool, int, float, enum, string). and also for the composite domains. This could be done by
  1. a special element ' < undef/ > ' -> < int > < undef/ > < int/ >
  2. a special value 'undef' -> < int > undef < int/ > .
For the < float > domain, there should be some additional predefined values representing the IEEE 754 standards for 'Not a number' (sth. like sqrt(-1) ) and 'positive/negative infinity' (sth. like 1/0 or -1/0). This could be done by special values 'NaN', '+Inf' and '-Inf' in the < float > element.

Discussion

The DTD defines the scalars as #PCDATA. I would like solution (2) because it is simpler and compatible with the existing DTD. But unfortunately, this doesn't work for the composites, while (1) would be fine here. Additional problems with (2) are the < string > and < enum > domains, because the special value 'undef' would make a valid string/enum (this in fact rules out (2) ). In addition, markup elements are not allowed in #PCDATA (this rules out (1) ). Any clever ideas?

#18common classes[send us your comment on this CR]

Change Request by:

Description:

In GXL 1, node-, edge- and rel-classes are viewed as disjoint sets of GraphElementClasses. In the GXL-Metamodel, GraphElementClass is declared as abstract. According to the generalisation hierarchy, isA-edges are only allowed between classes of the same type. Thus, defining node-, edge- or rel-calsses with the same attribute structure require seperate definitions of attribute structure for node-, edge and rel-classes. Inheritance from a general class is not provided. The successor of GXL 1 should provide inheritance fromgraph element class-definitions. E.g. GraphElementClass in the metamodel has to be concrete (instead of abstract). nheritance (isA) has to be allowed from node-, edge- and rel-classes to classes of type (not class) GraphElementClass and between GraphElementClasses of same type. For the GXL-Schema-Notation this requires a new stereotype for GraphClassElements.