Computing Laboratory
University of Kent
Below is an XML DTD and worked example to show how a Grrr program might be stored in an form that allows conversion to other graph transformation systems. This is GRXL draft version 0.1.
A major consideration in the design of this specification was depth and consistency verses shallow readability. The XML DTD grammar forces each level to be explicitly marked up. For full extensibility and generality in the DTD this entails a large amount of markup for each graph transformation system stored. The alternative is to take a much shallower approach, as given here, where the important attributes are included explicitly in the ATTLIST at the highest reasonable level. This implies that any extra user defined attributes can only be included at a different conceptual level by using the attr element, and also that there is a degree of redundancy in the grammar definition. However, the shallow approach taken here allows for easier understanding of the resultant XML, and helps hand coding and editing.
There are some clear advantages to using XML: tools, parsers, stability and visiblity. However, as a method for storing graph transformation information XML has some deficiencies. XML is a system for linear text markup, and as such storing graph and other structure information is not well catered for. Firstly, the notion of inheritance needs to be explicitly defined by a tree of links. Secondly, it does not contain a concept of constraints, not even implied via a typing system. So, for instance it is not possible to ensure that edges reference nodes in the same graph. Thirdly, XML markup is not very concise and where the grammar depth is great the storage overhead is significant.
<!ELEMENT grxl (attr*, nodetype*, edgetype*, hostgraph*,
transformation*)>
<!ATTLIST grxl
id ID #IMPLIED>
<!ELEMENT nodetype (attr*)>
<!ATTLIST nodetype
id ID #REQUIRED
parent IDREF #IMPLIED
shape CDATA #IMPLIED
height CDATA #IMPLIED
width CDATA #IMPLIED>
<!ELEMENT edgetype (attr*)>
<!ATTLIST edgetype
id ID #REQUIRED
parent IDREF #IMPLIED
directed (true | false) "true">
<!ELEMENT hostgraph (attr*, node*, edge*)>
<!ATTLIST hostgraph
id ID #REQUIRED>
<!ELEMENT transformation (attr*, rewrite*)>
<!ATTLIST transformation
id ID #REQUIRED>
<!ELEMENT rewrite (attr*, lhsgraph, rhsgraph)>
<!ATTLIST rewrite
id ID #REQUIRED>
<!ELEMENT lhsgraph (attr*, node*, edge*)>
<!ATTLIST lhsgraph
id ID #REQUIRED>
<!ELEMENT rhsgraph (attr*, node*, edge*)>
<!ATTLIST rhsgraph
id ID #REQUIRED>
<!-- match allows morphisms to be encoded -->
<!ELEMENT node (attr*)>
<!ATTLIST node
id ID #REQUIRED
type IDREF #IMPLIED
match IDREF #IMPLIED
label CDATA #IMPLIED
xpos CDATA #IMPLIED
ypos CDATA #IMPLIED
variable (true | false) "false"
negative (true | false) "false">
<!ELEMENT edge (attr*)>
<!ATTLIST edge
id ID #REQUIRED
type IDREF #IMPLIED
match IDREF #IMPLIED
begin IDREF #REQUIRED
end IDREF #REQUIRED
label CDATA #IMPLIED
variable (true | false) "false"
negative (true | false) "false">
<!-- attr has both a singleton attribute, plus attrelement to allow collections -->
<!ELEMENT attr (attrelement)*>
<!ATTLIST attr
name CDATA #REQUIRED
value CDATA #IMPLIED>
<!ELEMENT attrelement EMPTY>
<!ATTLIST attrelement
name CDATA #REQUIRED
value CDATA #IMPLIED>
<!DOCTYPE grxl SYSTEM "grxl.dtd">
<grxl>
<nodetype
id = "Top">
</nodetype>
<nodetype
id = "Trigger"
parent = "Top"
shape = "rectangle"
height = "20"
width = "30">
</nodetype>
<nodetype
id = "NonExecutable"
parent = "Top">
</nodetype>
<nodetype
id = "Data"
parent = "NonExecutable"
shape = "oval"
height = "30"
width = "30">
</nodetype>
<nodetype
id = "Information"
parent = "NonExecutable"
shape = "oval"
height = "20"
width = "30">
</nodetype>
<edgetype
id = "Function">
</edgetype>
<hostgraph
id = "Start">
<attr name = "step" value = "0"></attr>
<node
id = "hostn1"
type = "Trigger"
label = "AddAge"
xpos = "60"
ypos = "20">
</node>
<node
id = "hostn2"
type = "Information"
label = "25"
xpos = "30"
ypos = "60">
</node>
<node
id = "hostn3"
type = "Information"
label = "43"
xpos = "120"
ypos = "60">
</node>
<node
id = "hostn4"
type = "Data"
label = "Harry"
xpos = "30"
ypos = "120">
</node>
<node
id = "hostn5"
type = "Data"
label = "Fred"
xpos = "120"
ypos = "120">
</node>
<edge
id = "hoste1"
type = "Function"
begin = "hostn4"
end = "hostn2"
label = "age">
</edge>
<edge
id = "hoste2"
type = "Function"
begin = "hostn5"
end = "hostn3"
label = "age">
</edge>
<edge
id = "hoste3"
type = "Function"
begin = "hostn5"
end = "hostn4"
label = "employs">
</edge>
</hostgraph>
<transformation id = "AddAge">
<rewrite id = "AddAge1">
<lhsgraph id = "LHS1">
<node
id = "n1"
type = "Trigger"
label = "AddAge"
xpos = "30"
ypos = "30"
variable = "false">
</node>
<node
id = "n2"
type = "Data"
label = "X"
xpos = "40"
ypos = "60"
variable = "true">
<attr name = "once
only" value = "yes"></attr>
</node>
<node
id = "n3"
type = "Information"
label = "Y"
xpos = "100"
ypos = "30"
variable = "true">
</node>
<edge
id = "e1"
type = "Function"
begin = "n2"
end = "n3"
label = "age"
variable = "false">
</edge>
</lhsgraph>
<rhsgraph id = "RHS1">
<node
id = "n11"
type = "Trigger"
label = "AddAge"
xpos = "30"
ypos = "30"
variable = "false">
</node>
<node
id = "n12"
type = "Data"
label = "X"
xpos = "40"
ypos = "60"
variable = "true">
<attr name = "once
only" value = "yes"></attr>
</node>
<node
id = "n13"
type = "Information"
label = "Y"
xpos = "100"
ypos = "70"
variable = "true">
</node>
<node
id = "n14"
type = "Trigger"
label = "Add"
xpos = "110"
ypos = "20"
variable = "false">
</node>
<node
id = "n15"
type = "Information"
label = "1"
xpos = "120"
ypos = "70"
variable = "true">
</node>
<edge
id = "e11"
type = "Function"
begin = "n12"
end = "n14"
label = "age"
variable = "false">
</edge>
<edge
id = "e12"
type = "Function"
begin = "n14"
end = "n13"
label = "arg1"
variable = "false">
</edge>
<edge
id = "e13"
type = "Function"
begin = "n14"
end = "n15"
label = "arg2"
variable = "false">
</edge>
</rhsgraph>
</rewrite>
<rewrite id = "AddAge2">
<lhsgraph id = "LHS2">
<node
id = "n21"
type = "Trigger"
label = "AddAge"
xpos = "30"
ypos = "30"
variable = "false">
</node>
</lhsgraph>
<rhsgraph id = "RHS2">
</rhsgraph>
</rewrite>
</transformation>
</grxl>