Marker-directed Optimization of UnCAL Graph
Transformations
Soichiro Hidaka1 , Zhenjiang Hu1 , Kazuhiro Inaba1 , Hiroyuki Kato1 , Kazutaka
Matsuda2 , Keisuke Nakano3 , and Isao Sasano4
1

National Institute of Informatics, Japan,{hidaka, hu, kinaba, kato}@nii.ac.jp
2
The University of Electro-Communications, Japan,
ksk@cs.uec.ac.jp
3
Tohoku University, Japan,
kztk@kb.ecei.tohoku.ac.jp
4
Shibaura Institute of Technology, Japan,
sasano@sic.shibaura-it.ac.jp

Abstract. Buneman et al. proposed a graph algebra called UnCAL (Unstructured CALculus) for compositional graph transformations based on
structural recursion, and we have recently applied to model transformations. The compositional nature of the algebra greatly enhances themodularity of transformations. However, intermediate results generated
between composed transformations cause overhead. Buneman et al. proposed fusion rules that eliminate the intermediate results, but auxiliary
rewriting rules that enable the actual application of the fusion rules are
not apparent so far. UnCAL graph model includes the concept of markers, which correspond to recursive function call in the structural recursion. We have found that there are many optimization opportunities atrewriting level based on static analysis, especially focusing on markers.
The analysis can safely eliminate redundant function calls. Performance
evaluation shows its practical eﬀectiveness for non-trivial examples inmodel transformations.
Keywords: program transformations, graph transformations, UnCAL

1

Introduction

Graph transformation has been an active research topic [9] and plays an important role in model-driven engineering [5, 11]; models such as UML diagrams are
represented as graphs, and model transformation is essentially graph transformation. We have recently proposed a bidirectional graph transformation framework [6] based on providing bidirectional semantics to an existing graph transformation language UnCAL [4], and applied it to bidirectional model transformation by translating from existing model transformation language to UnCAL [10].
Our success in providing well-behaved bidirectional transformation framework
was due to structural recursion in UnCAL, which is a powerful mechanism ofvisiting and transforming graphs. Transformation based on structural recursion

is inherently compositional, thus facilitates modular model transformation programming.
However, compositional programming may lead to many unnecessary intermediate results, which would make a graph transformation program terribly ineﬃcient. As actively studied in programming language community, optimization
like fusion transformation [12] is desired to make it practically useful. Despite
a lot of work being devoted to fusion transformation of programs manipulating
lists and trees, little work has been done on fusion on programs manipulating
graphs. Although the original UnCAL has provided some fusion rules and rewriting rules to optimize graph transformations [4], we believe that further work andenhancement on fusion and rewriting are required.
The key idea presented in this paper is to analyze input/output markers,
which are sort of labels on specific set of nodes in the UnCAL graph model andare used to compose graphs by connecting nodes with matching input and output
markers. By statically analyzing connectivity of UnCAL by our marker analysis,
we can simplify existing fusion rule. Consider, for instance, the following existing
generic fusion rule of the structural recursion operator in UnCAL:
rec(λ($l2 , $t2 ).e2 )(rec(λ($l1 , $t1 ).e1 )(e0 ))= rec(λ($l1 , $t1 ). rec(λ($l2 , $t2 ).e2 )(e1 @ rec(λ($l1 , $t1 ).e1 )($t1 )))(e0 )where rec(λ($l , $t).e) applies transformation e on each edge (whose label isbound to $l and subgraph pointed by the edge is bound to $g) of the input
graph, and combine the results of e to produce the output graph. rec encodes a
structural recursive function which is an important computation pattern and explained later. The graph constructor @ connects two graphs by matching markers
on nodes, and in this case, result of transformation e1 is combined to anotherstructural recursion rec(λ($l1 , $t1 ).e1 ). If we know by static analysis that e1
creates no output markers, or equivalently, rec(λ($l1 , $t1 ).e1 ) makes no recursive function call, then we can eliminate @ rec(λ($l1 , $t1 ).e1 )($t1 ) and further
simplify the fusion rule. Our preliminary performance analysis reports relatively
good evidence of usefulness of this optimization.
The main technical contributions of this paper are two folds:– A sound static inference of markers that is refined over that in [4] (Section 3). In the prior inference, the set of output markers was inferred using
subtyping rule, which could lead to a set that is unnecessarily larger thanactually produced at run time. For example, the set of output markers of
the body of rec was treated as identical to the set of input markers. This
over-approximation missed the chance of expression simplification exemplified above. Our inference can avoid this over-approximation by avoiding
subtyping rule and computing the sets in a bottom-up manner.
– A set of rewriting rules for optimization using inferred markers (Section 4),
that is more powerful than that in [4] in the sense that more expressions are
simplified as exemplified above.

1

0

a b c
2

3

4

1
c

a b

a a

61
5

2

3

c
62

da

a d

51

52

42
c

4
c c

d
6

(a) A Simple Graph

41(b) An Equivalent Graph (c) Result of a2d xc on Fig. 1(a)Fig. 1. Graph Equivalence Based on Bisimulation

All have been implemented and tested with graph transformations widely recognized in software engineering research. The source code of the implementation
can be downloaded via our project web site at www.biglab.org.
The rest of this paper is organized as follows. Section 2 reviews UnCAL
graph model, graph transformation language and existing optimizations. Section 3 proposes enhanced static analysis of markers. In Section 4, we build enhanced rewriting optimization algorithm based on the static analysis. Section 5reports preliminary performance results. Section 6 reviews related work, andSection 7 concludes this paper.

2

UnCAL Graph Algebra and Prior Optimizations

In this section, we review the UnCAL graph algebra [3, 4], in which our graphtransformation is specified.
2.1

Graph Data Model

We deal with rooted, directed, and edge-labeled graphs with no order on outgoingedges. UnCAL graph data model has two prominent features, markers and εedges. Nodes may be marked with input and output markers, which are used as
an interface to connect them to other graphs. An ε-edge represents a shortcutof two nodes, working like the ε-transition in an automaton. We use Label todenote the set of labels and M to denote the set of markers.
Formally, a graph G is a quadruple (V, E, I, O), where V is a set of nodes,
E ⊆ V × (Label ∪ {ε}) × V is a set of edges, I ⊆ M × V is a set of pairs of
an input marker and the corresponding node, and O ⊆ V × M is a set of pairsof nodes and associated output markers. For each marker &x ∈ M, there is at
most one node v such that (&x , v) ∈ I. The node v is called an input node withmarker &x and is denoted by I(&x ). Unlike input markers, more than one node
can be marked with an identical output marker. They are called output nodes.
Intuitively, input nodes are root nodes of the graph (we allow a graph to havemultiple root nodes, and for singly rooted graphs, we often use default marker

&x1 ... &xm

a

&z
G1

G
{a : G}{}G2

G&z := GG1 ∪ G2&z&z()&x1 ... &xm&x1 ... &xm&x1’ ... &xm’

G1

G2

&y1 ... &yn&y1 ... &yn
G1G2

G1
&y1 ... &yn
εε&y1 ... &yn&x1 ... &xm
εε&x1 ... &xm
εG2&z1 ... &zp
G1@G2G&x1 ... &xm

εcycle (G)Fig. 2. Graph Constructors& to indicate the root), while an output node can be seen as a “context-hole”
of graphs where an input node with the same marker will be plugged later. We
write inMarker(G) to denote the set of input markers and outMarker(G) to denotethe set of output markers in a graph G.
Note that multiple-marker graphs are meant to be an internal data structure for graph composition. In fact, the initial source graphs of our transformation have one input marker (single-rooted) and no output markers (noholes). For instance, the graph in Fig. 1(a) is denoted by (V, E, I, O) whereV = {1, 2, 3, 4, 5, 6}, E = {(1, a, 2), (1, b, 3), (1, c, 4), (2, a, 5), (3, a, 5), (4, c, 4),(5, d, 6)}, I = {(&, 1)}, and O = {}. DB X
Y denotes graphs with sets of input{&}
markers X and output markers Y. DB Y is abbreviated to DB Y .
2.2

Notion of Graph Equivalence

Two graphs are value equivalent if they are bisimilar. Please refer to [4] for thecomplete definition. For instance, the graph in Fig. 1(b) is value equivalent to
the graph in Fig. 1(a); the new graph has an additional ε-edge (denoted by thedotted line), duplicates the graph rooted at node 5, and unfolds and splits thecycle at node 4. Unreachable parts are also disregarded, i.e., two bisimilar graphs
are still bisimilar if one adds subgraphs unreachable from input nodes.
This value equivalence provides optimization opportunities because we canrewrite transformation so that transformation before and after rewriting produce
results that are bisimilar to each other [4]. For example, optimizer can freely cut
oﬀ expressions that is statically determined to produce unreachable parts.
2.3

Graph Constructors

Figure 2 summarizes the nine graph constructors that are powerful enough todescribe arbitrary (directed, edge-labeled, and rooted) graphs [4]. Here, {} con-e ::= {} | {l : e} | e ∪ e | &x := e | &y | ()| e ⊕ e | e @ e | cycle(e){ constructor }| $g{ graph variable }| let $g = e in e
{ variable binding }| if l = l then e else e{ conditional }| rec(λ($l , $g).e)(e){ structural recursion application }l ::= a | $l
{ label (a ∈ Label ) and label variable }Fig. 3. Core UnCAL Language

structs a root-only graph, {a : G} constructs a graph by adding an edge withlabel a ∈ Label ∪ {ε} pointing to the root of graph G, and G1 ∪ G2 adds two
ε-edges from the new root to the roots of G1 and G2 . Also, &x := G associates
an input marker, &x , to the root node of G, &y constructs a graph with a single
node marked with one output marker &y, and () constructs an empty graph thathas neither a node nor an edge. Further, G1 ⊕ G2 constructs a graph by using acomponentwise (V, E, I and O) union. ∪ diﬀers from ⊕ in that ∪ unifies input
nodes while ⊕ does not. ⊕ requires input markers of operands to be disjoint,
while ∪ requires them to be identical. G1 @ G2 composes two graphs verticallyby connecting the output nodes of G1 with the corresponding input nodes of G2
with ε-edges, and cycle(G) connects the output nodes with the input nodes of
G to form cycles. Formal definitions can be found in the full version of [6]. Thesegraph constructors are, together with other operators, bisimulation generic [4],i.e., bisimilar result is obtained for bisimilar operands.
Example 1. The graph equivalent to that in Fig. 1(a) can be constructed asfollows (though not uniquely).
&z @ cycle((&z := {a : {a : &z1 }} ∪ {b : {a : &z1 }} ∪ {c : &z2 })⊕ (&z1 := {d : {}})⊕ (&z2 := {c : &z2 }))ut

For simplicity, we often write {a1 : G1 , . . . , an : Gn } to denote {a1 : G1 } ∪· · · ∪ {an : Gn }, and (G1 , . . . , Gn ) to denote (G1 ⊕ · · · ⊕ Gn ).
2.4

UnCAL Syntax

UnCAL (Unstructured CALculus) is an internal graph algebra for the graphquery language UnQL, and its core syntax is depicted in Fig. 3. It consists of thegraph constructors, variables, variable bindings (let is our extension and is used
for rewriting), conditionals, and structural recursion. We have already detailed
the data constructors, while variables, variable bindings and conditionals are self
explanatory. Therefore, we will focus on structural recursion, which is a powerfulmechanism in UnCAL to describe graph transformations.
A function f on graphs is called a structural recursion if it is defined by thefollowing equations

f ({})= {}f ({$l : $g}) = e @ f ($g)
f ($g1 ∪ $g2 ) = f ($g1 ) ∪ f ($g2 ),and f can be encoded by rec(λ($l , $g).e). Despite its simplicity, the core UnCAL
is powerful enough to describe interesting graph transformation including all
graph queries (in UnQL) [4], and nontrivial model transformations [8].
Example 2. The following structural recursion a2d xc replaces all labels a withd and removes edges labeled c.
a2d xc($db) = rec(λ($l , $g). if $l = a then{d : &}
else if $l = c then {ε : &}else{$l : &}) ($db)
The outer if of the nested if s corresponds to e in the above equations. Applying
the function a2d xc to the graph in Fig. 1(a) yields the graph in Fig. 1(c). ut
2.5

Revisiting Original Marker Analysis

There were actually previous work on marker analysis by original authors of
UnCAL. The original typing rules appeared in the technical report version of [2].
Note that we call type to denote sets of input and output markers. Compared toour analysis, these rules were provided declaratively. For example, the rule forif says that if sets of output markers in both branches are equal, then the result
have that set of output markers. It is not apparent how we obtain the output
marker of if if the branches have diﬀerent sets of output markers.
Buneman et al. [4] did mention optimization based on marker analysis, toavoid evaluating unnecessary subexpressions. But it was mainly based on runtime analysis. As we propose in the following sections, we can statically computethe set of markers and further simplify the transformation itself.
2.6

Fusion Rules and Output Marker Analysis

Buneman et al. [3, 4] proposed the following fusion rules that aim to remove
intermediate results in successive applications of structural recursion rec.
rec(λ($l2 , $t2 ).e2 )(rec(λ($l1 , $t1 ).e1 )(e0 ))rec(λ($l1 , $t1 ). rec(λ($l2 , $t2 ).e2 )(e1 ))(e0 ) if $t2 does not appear free in e2= rec(λ($l1 , $t1 ). rec(λ($l2 , $t2 ).e2 )for arbitrary e2(e1 @ rec(λ($l1 , $t1 ).e1 )($t1 )))(e0 )(1)
If you can statically guarantee that e1 does not produce any output marker,
which means the rec is “non-recursive”, then the second rule is promoted to thefirst rule, opening another optimization opportunities.

&x := (&z := e) −→ &x.&z := ee ∪ {} −→ e&x := (e1 ⊕ e2 ) −→ (&x := e1 ) ⊕ (&x := e2 ){} ∪ e −→ e() @ e −→ ()e ⊕ () −→ e() ⊕ e −→ ee :: DB XYX ∩Y =φcycle(e) −→ e

Fig. 4. Auxiliary Rewriting Rules

Non-recursive Query. Now questions that might be asked would be how often
do such kind of “non-recursive” queries appear. Actually it frequently appears as
extraction or join. Extraction transformation is a transformation in which some
subgraphs are simply extracted. It is achieved by direct reference of the boundgraph variable in the body of rec. Join is achieved by nesting of these extraction
transformations. Finite steps of edge traversals are expressed by this nesting.
Example 3. The following structural recursion consecutive extracts subgraphsthat can be accessible by traversing two connected edges of the same label.
consecutive($db) = rec(λ($l , $g). rec(λ($l 0 , $g 0 ).
if $l = $l 0 then {result : $g 0 }else{})($g))($db)(
For example, we have consecutive

a/ X/
• •
◦rLL& a / Y /b • • •
ar8•)=◦

result /

•

X /

•.

If this transformation is followed by rec(λ($l2 , $t2 ).e2 ) where e2 refers to $t2 ,the second condition of fusion rule applies, but it will be promoted to the first,
since the body of rec in consecutive, which corresponds to e1 in the fusion rule,
does not have output markers. We revisit this case in Example 4 in Section 4.
2.7

Other Prior Rewriting Rules

Apart from fusion rules, the following rewriting rules for rec are proposed in [4]for optimizations. Type of e is assumed to be DB Z
Z . They simplify the argumentof rec and increase chances of fusions. Some of them are recapped below.
⊕rec(λ($l , $t).e)({})= 1 &z∈Z &z := {}rec(λ($l , $t).e)({l : d}) = e[ l/$l ][ d/$t ] @ rec(λ($l , $t).e)(d)The first rule eliminates rec, while the second rule eliminates an edge from theargument.
Additional rules proposed by (full version of) Hidaka et al. [8] to further
simplify the body of rec are given in Fig. 4. The rules in the last line in Fig. 4
can be generalized by static analysis of the marker in the following section. And
given the static analysis, we can optimize further as described in Section 4.
1

Original right hand side was {} in [4], but we corrected here.

def(&x · &y) · &z = &x · (&y · &z)& · &x = &x · & = &x

X · Y = {&x · &y | &x ∈ X , &y ∈ Y}Γ ` {} :: DB ∅

Γ ` l :: LabelΓ ` e :: DB YΓ ` {l : e} :: DB YΓ ` () :: DB ∅∅Γ ` e :: DB Z
Y{&x}·ZΓ ` &x := e :: DB YΓ ` e1 :: DB X
Y1
Γ ` e2 :: DB X
Y2
Γ ` e1 ∪ e2 :: DB X
Y1 ∪Y2Γ ` &y :: DB {&y}X1 ∩ X 2 = ∅1Γ ` e1 :: DB X
Y12
Γ ` e2 :: DB X
Y2

X1 ∪X2Γ ` e1 ⊕ e2 :: DB Y
1 ∪Y21Γ ` e1 @ e2 :: DB X
Y2

X1
Γ ` e1 :: DB Y12
Γ ` e2 :: DB X
Y2

Γ ($g) = DB XYΓ ` $g :: DB XYΓ ` e :: DB X
Y5

Γ ` cycle(e) :: DB X
Y\X

Γ ` ea :: DB X
Yi
Γ {$l 7→ Label , $g 7→ DB Y } ` eb :: DB Z
Zo

Γ ` l1 :: LabelΓ ` et :: DB X
Yt

Z = Zi ∪ Zo·Z
Γ ` rec(λ($l , $g).eb )(ea ) :: DB X
Y·Z

Γ ` l2 :: LabelΓ ` ef :: DB X
Yf

Γ ` if l1 = l2 then et else ef :: DB X
Yt ∪Yf1
Γ ` e1 :: DB X
Y1
X2
1
Γ {$g 7→ DB X}`e
2 :: DB Y2
Y12
Γ ` let $g = e1 in e2 :: DB X
Y2

Fig. 5. UnCAL Static Typing (Marker Inference) Rules: Rules for Label are Omitted

3

Enhanced Static Analysis

This section proposes our enhanced marker analysis. Figure 5 shows the proposed
marker inference rules for UnCAL. Dot notation (·) between markers and setsof markers represents “concatenation” of markers that satisfies the properties at
the top of the figure. Static environment Γ denotes mapping from variables totheir types. We assume that the types of free variables are given. Since we focus
on graph values, we omit rules for labels. Roughly speaking, DB X
Y is a type forgraphs that have X input markers exactly and have at most Y output markers,
which will be shown formally by Lemma 1.
The original typing rules were provided based on the subtyping ruleΓ ` e :: DB XYY ⊆ Y0Γ ` e :: DB X
Y0

and required the arguments of ∪, ⊕, if to have identical sets of output markers.
Unlike the original rules, the proposed type system does not use the subtyping
5

Original rule (let’s say @o ) which requires Y1 = X2 is relaxed here. Our @ can be
defined by g1 @ g2 = (g1 @o IdX2 \Y1 ) @o (BotY1 \X2 ⊕ g2 ), where Bot and Id are definedin Section 4.2.1. This particular definition in which markers Y1 \ X2 are peeled oﬀ isclose to the original semantics because final output markers coincide. Extension inwhich these excess output markers remain would be possible, allowing the markers
to be used later to connect to other graphs.

rule directly for inference. Combined with the forward evaluation semantics F[[]]
that is summarized in [6], we have the following type safety property.
Lemma 1 (Type Safety). Assume that g is the graph obtained by g = F[[e]]for an expression e. Then, ` e :: DB X
Y implies both inMarker(g) = X andoutMarker(g) ⊆ Y.
Lemma 1 guarantees that the set of input markers estimated by the type inference is exact in the sense that the set of input markers generated by evaluation
exactly coincides with that of the inferred type. For the output markers, thetype system provides an over-approximation in the sense that the set of output
markers generated by evaluation is a subset of the inferred set of output markers.
Since the treatment of the input markers are identical to that in [4], we focus
that on the output markers and prove it. The proof, which is based on induction
on the structure of UnCAL expressions, is in the full version [7] of this paper.
Between the original typing rules in [4], the following property holds: for all
X0
X and Y, e :: DB X
Y for some Y ⊇ Y if and only if e has a type DB Y 0 in theoriginal type system. The proof appears in the full version [7].

4Enhanced Rewiring Optimization

This section proposes enhanced rewriting optimization rules based on the static
analysis shown in the previous section.
4.1

Rule for @ and Revised Fusion Rule

Statically-inferred markers enable us to optimize expressions much more. We
can generalize, for example, the rewriting rule () @ e −→ () in the last row ofFig. 4 to the following, by not just referring to the pattern of subexpressions but
its estimated markers.
e1 :: DB X∅
(2)e1 @ e2 −→ e1
As we have seen in Sect. 2, we have two fusion rules (1) for rec. Although
the first rule can be used to gain performance, the second rule is more complex
so less performance gain is expected. Using (2), we can relax the first conditionof the fusion rule (1) to increase chances to apply the first rule as follows.
rec(λ($l2 , $t2 ).e2 )(rec(λ($l1 , $t1 ).e1 )(e0 ))= rec(λ($l1 , $t1 ). rec(λ($l2 , $t2 ).e2 )(e1 ))(e0 )if $t2 does not appear free in e2 , or e1 :: DB X∅
Here, the underlined part is added to relax the entire condition.
4.2

Further Optimization with Static Marker Information

In this section, general rules for e1 @ e2 is investigated. First to eliminate @ e2 ,and then to statically compute @ by plugging e2 into e1 .

4.2.1 Static Output Marker Removal Algorithm and Soundness
For more general cases of @ where connections by ε do not happen, we have thefollowing rule.
e1 :: DB X
Y12
e2 :: DB Y
Y1 ∩ Y2 = ∅ RmY1 hhe1 ii = eZ
e1 @ e2 −→ e

RmY hheii denotes static removal of the set of output markers, i.e., if ` e :: DB X
Y,then ` RmW hheii :: DB X.
Without
this,rewritingresultinspurious
outputY\Wmarkers from e1 remained in the final result. The formal definition of RmY hheii
is shown below.
Rm∅ hheii = e RmX ∪Y hheii = RmY hhRmX hheiiii RmY hh{}ii = {}RmY hh()ii = () Rm{&y} hh&yii = {} Rm{&y} hh&x ii = &x
RmY hhe1 e2 ii = RmY hhe1 ii RmY hhe2 ii ( ∈ {∪, ⊕})RmY hh&x := eii = (&x := RmY hheii)
RmY hh{l : e}ii = {l : RmY hheii}
RmY hhe1 @ e2 ii = e1 @ RmY hhe2 ii
RmY hhif b then e1 else e2 ii = if b then RmY hhe1 ii else RmY hhe2 ii
Since the output markers of the result of e1 @ e2 are not aﬀected by those of e1 ,e1 is not visited. In the following, IdY and BotY are respectively⊕ in the rule of @⊕defined as &z∈Y &z := &z and &z∈Y &z := {}.
e :: DB X&y ∈ (Y \ X ) Rm{&y} hheii = e0
e :: DB X&y ∈/ (Y \ X )YY
0
Rm{&y} hhcycle(e)ii = cycle(e )Rm{&y} hhcycle(e)ii = cycle(e)$v :: DB X
$v :: DB X&y ∈/Y&y ∈ YY
Y
Rm{&y} hh$v ii = $v Rm{&y} hh$v ii = $v @ (Bot{&y} ⊕ IdY\{&y} )The first rule of $v says that according to the safety of type inference, &y is
guaranteed not to result at run-time, so the expression $v remains unchanged.
The second rule actually removes the output marker &y j , but static removal is
impossible. So the removal is deferred till run-time. The output node marked &y j
is connected to node produced by &y := {}. Since the latter node has no output
marker, the original output marker disappears from the graph produced by theevaluation. The rest of the &y k := &y k does no operation on the marker. Since
estimation Y is the upper bound, the output maker may not be produced at runtime. If it is the case, connection with ε-edge by @ does not occur, and the nodes
produced by the := expressions are left unreachable, so the transformation is stillvalid. As another side eﬀect, @ may connect identically marked output nodes
to single node. However, the graph before and after this “funneling” connection
are bisimilar, since every leaf node with identical output markers are bisimilar
by definition. Should the output nodes are to be further connected to other
input nodes, the target node is always single, because more than one node with

identical input marker is disallowed by the data model. So this connection does
no harm. Note that the second rule increases the size of the expression, so it
may increase the cost of evaluation.
·Z
rec(λ($l , $t).eb )(ea ) :: DB X
&y ∈ Y Rm{&y} hhea ii = e0a
Y·Z
Rm{&y.&z|&z∈Z} hhrec(λ($l , $t).eb )(ea )ii = rec(λ($l , $t).eb )(e0a )For rec, one output marker &y in ea corresponds to {&y} · Z = {&y.&z | &z ∈ Z}
in the result. So removal of &y from ea results in removal of all of the {&y} · Z.
So only removal of all of {&y.&z | &z ∈ Z} at a time is allowed.
Lemma 2 (Soundness of Static Output-Marker Removal Algorithm).
Assume that G = (V, E, I, O) is a graph obtained by G = F[[e]] for an expression e, and e0 is the expression obtained by RmY hheii. Then, we have F[[e0 ]] =(V, E, I, {(v, &y) ∈ O | &y ∈/ Y}).
Lemma 2 guarantees that no output marker in Y appears at run-time if RmY hheii
is evaluated.
4.2.2 Plugging Expression to Output Marker Expression
The following rewriting rule is to plug an expression into another through correspondingly marked node.
{l : &y} @ (&y := e) −→ {l : e}This kind of rewriting was actually implicitly used in the exemplification of
optimization in [4], but was not generalized. We can generalize this rewriting as{0
if &y ∈ Y where e :: DB X
RmY\{&y} hheii[ e /&y ]0Ye @ (&y := e ) −→RmY hheiiotherwise.
0

where e[ e /&y ] denotes substitution of &y by e0 in e. Since nullrary constructors{}, (), and &x 6= &y do not produce output marker &y, the substitution takes
no eﬀect and the rule in the latter case apply. So we focus on the former casein the sequel. For most of the constructors the substitution rules are rather
straightforward:&y[ e/&y ] = e(e1 e2 )[ e/&y ] = (e1 [ e/&y ]) (e2 [ e/&y ])00(&x := e)[ e /&y ] = (&x := (e[ e /&y ]))(∈ {∪, ⊕})

00{l : e}[ e /&y ] = {l : (e[ e /&y ])}(e1 @ e2 )[ e/&y ] = e1 @ (e2 [ e/&y ])(if b then e1 else e2 )[ e/&y ] = if b then (e1 [ e/&y ]) else (e2 [ e/&y ])Since the final output marker for @ is not aﬀected by that of e1 , e1 is not visitedin the rule of @. For cycle, we should be careful to avoid capturing of marker.
{
0e0 :: DB Y 0
cycle(e[ e /&y ]) if (Y 0 ∩ X ) = ∅ where e :: DB X
0Yecycle(e)[ /&y ] =0cycle(e)[ e /&y ] otherwise.

The above rule says that if Y 0 will be “free” markers in e, that is, the output
markers in e0 , namely Y 0 will not be captured by cycle, then we can plug e0 into
output marker expression in e. If some of the output markers in Y 0 are included
in X , then the renaming is necessary. As suggested in the full version of [3],markers in X instead of those in Y 0 should be renamed. And that renaming canbe compensated outside of cycle as follows:⊕defcycle(e) = (&x := &tmpx ) @ cycle(e[ &tmp x1/&x 1 ] . . . [ &tmp xM/&x M ])&x∈X

where &x 1 , . . . , &x M = X are the markers to be renamed, and X of e :: DB X
Y
is used. Note that in the renaming, not only output markers, but also input
markers are renamed. &tmp x1 , . . . , &tmp xM are corresponding fresh (temporary)markers. The left hand side of @ recovers the original name of the markers. Afterrenaming by cycle, no marker is captured anymore, so substitution is guaranteed
to succeed. For variable reference and rec, static substitution is impossible. So
we resort to the following generic “fall back” rule.
e ∈ {$v , rec( )( )} e :: DB X
Y = {&y 1 , . . . , &y j , . . . , &y n }Y()&y 1 := &y 1 , . . . , &y j−1 := &y j−1 , &y j := e0 ,0e[ e /&y j ] = e @&y j−1 := &y j−1 , . . . , &y n := &y n
The “fall back” rule is used for rec because unlike output marker removal
algorithm, we can not just plug e into ea since that will not plug e butrec(λ($l , $t).eb )(e) in the result. We could have used the inverse rec(λ($l , $t).eb )−1
to plug rec(λ($l , $t).eb )−1 (e0 ) instead, but the inverse does not always exist in
general.
The overall rewriting is conducted by two mutually recursive functions asfollows: a driver function first applies itself to subexpressions recursively, andthen applies a function that implements −→ and other rewriting rules recursively
such as fusions described in this paper, on the result of the driver function. The
implemented rewriting system is deterministic by imposing consistent order ofrule applications by these functions.
With respect to proposed rewriting rules in this section, the following theorem
holds.
Theorem 1 (Soundness of Rewriting). If e −→ e0 , then F[[e]] is bisimilar
to F[[e0 ]].
It can be proved by simple induction on the structure of UnCAL expressions,and omitted here.
Example 4. The following transformation that apply selection after consecutive
in Example 3rec(λ($l1 , $g1 ). if $l1 = a then {$l1 : $g1 } else {})(consecutive($db))
is rewritten as follows:={ expand definition of consecutive and apply 2nd fusion rule }rec(λ($l , $g). rec(λ($l1 , $g1 ). if $l1 = a then {$l1 : $g1 } else {})(rec(λ($l 0 , $g 0 ). if $l = $l 0 then {result : $g 0 } else {})($g)@ rec(λ($l , $g). rec(λ($l 0 , $g 0 ).
if $l = $l 0 then {result : $g 0 } else {})($g))($g)))($db)={ (2) }rec(λ($l , $g). rec(λ($l1 , $g1 ). if $l1 = a then {$l1 : $g1 } else {})(rec(λ($l 0 , $g 0 ). if $l = $l 0 then {result : $g 0 } else {})($g)))($db)={ 2nd fusion rule, (2), rec rule for if and {l : d}, static label comparison }rec(λ($l , $g). rec(λ($l 0 , $g 0 ).{})($g))($db)
This example demonstrates the second fusion rule promotes to the first. The
top level edges of the result of consecutive are always labeled result while theselection selects subgraphs under edges labeled a. So the result will always be
empty, and correspondingly the body of rec in the final result is {}.
utMore examples can be found in the full version [7] of this paper.
The following remark summarizes how far can we remove intermediategraphs. Proof can be found in the full version [7].
Remark 1 (Removal of Intermediage Graph). Suppose we have a composition of
the formrec(λ($l2 , $t2 ).e2 )(C[rec(λ($l1 , $t1 ).e1 )(e0 )])where C[] denotes context using constructors and if expressions. Then, (i) if $t2
does not appear free in e2 , then the composition of the above form, including
the ones that are generated during fusion, are removed. (ii) if $t2 appears freein e2 but e1 :: DB ∅ , and e1 consists of nested rec with context not using @ or
cycle with body of type DB ∅ , then the composition, including the ones that are
generated during the fusion rule application, are removed.

5

Implementation and Performance Evaluation

This section reports preliminary performance evaluations. All of the transformations in the paper are implemented in GRoundTram, or Graph Roundtrip
Transformation for Models, which is a system to build a bidirectional transformation between two models (graphs). All the source codes are available online atwww.biglab.org. The following experimental results are obtained by the system.
Performance evaluation was conducted on GRoundTram, running on MacOSX
over MacBookPro 17 inch, with 3.06 GHz Intel Core 2 Duo CPU. An UnCAL
transformation runs in time exponential to the size (number of compositions
or nesting of recs) of the transformation (and polynomial to the size of input
graph [4]). Thus, the proposed rewriting, which can reduce the size of transformation, may change the elapsed time drastically even for the small graphs (upto a hundred of nodes) used in the experiments.

Table 1. Summary of Experiments (running time is in CPU seconds)
direction no rewriting previous [4, 8]
ours
forward
1.18
0.68
0.68
Class2RDB
backward
14.5
7.99
7.89
forward0.08
0.77 (2*3) 0.07 (2*13)
PIM2PSMbackward
1.62
3.64
0.75
forward0.04
0.04 (2*1) 0.05 (2*11)
C2Oselbackward
2.26
0.26
0.27
forward0.05
0.06 (2*1) 0.04 (2*11)
C2Osel’backward
2.53
2.58
1.26
forward0.022
0.016 (1*1) 0.010 (1*1)
Ex1 [4]
backward
0.85
0.30
0.15

Table 1 shows the experimental results. Each running time includes timefor forward and backward6 transformations [6], and for backward transformations, algorithm for edge-renaming is used, and no modification on the target isactually given. However, we suppose presence of modification would not makemuch diﬀerence in the running time. Running time of forward transformation inwhich rewriting is applied (last two columns) includes time for rewriting. Rewriting took 0.006 CPU seconds at the worst case (PIM2PSM, ours). Class2RDB
stands for class diagram to table diagram transformation, PIM2PSM for platform independent model to platform specific model transformation, C2Osel isfor transformation of customer oriented database into order oriented database,followed by a simple selection, and Ex1 is the example that is extracted fromour previous paper [8], which was borrowed from [4]. It is a composition of two
recs.
The numbers in parentheses show how often the fusion transformation happened. For example, PIM2PSM led to 3 fusions based on the second rule, andfurther enhanced rewriting led to 10 more fusion rule applications, all of which
promoted to the first rule via proposed rewriting rule (2). Same promotions
happened to C2Osel. Except for C2Osel’, a run-time optimization in which unreachable parts are removed after every application of rec is applied. Enhanced
rewriting led to performance improvements in both forward and backward evaluations, except C2Osel. Comparing “previous” with “no rewriting”, PIM2PSM
and C2Osel’ led to slowdown. This slowdown is explained as follows. The fusion turns composition of recs to their nesting. In the presence of the run-time
optimization, composition is more advantageous than nesting when only smallpart of the result is passed to the subsequent recs, which will run faster thanwhen passed entire results (including unreachable parts). Once nested, intermediate result is not produced, but the run-time optimization is suppressed because
6

Since we are conducting research on bidirectional transformations, we are not onlyinterested in the performance of forward transformations, but also that of backward
transformations.

every execution of the inner rec traverses the input graph. C2Osel’ in which runtime optimization is turned oﬀ, shows that the enhanced rewriting itself lead toperformance improvements.

6

Related Work

Although some of our optimization rules were mentioned in [8], the relationshipwith static marker analysis was not covered in depth. Our optimization, based on
the enhanced marker analysis in Sect. 3 , generalizes all the rules in [8] uniformly.
In our previous paper [6], an implementation of rewriting optimizations wasreported, but concrete strategies were not included in the paper.
Plugging constructor-only expressions into output marker expressions was
discussed in the full (technical report) version of [3]. Their motivation was toexpress semantics of @ at the constructor expression level and not graph data
level as in [4]. It also mentioned renaming of markers to avoid capture of theoutput markers in cycle expressions. We do attempt the same thing at theexpression level but we argue here more formally.
Our rewriting rules are inspired by the technical report but the idea there
is not yet exploited fully. They discussed the semantics of rec on the cycle
expressions, even when the body refered to graph variables, although marker
environment that maps markers to connected subgraphs introduced there makes
the semantics complex. But we could use the semantics to enhance rewriting
rules for rec with cycle arguments.
The journal version [4] mentioned run-time optimization in which, assuming
top-down evaluation, only necessary components of structural recursion are executed. For example, only &z 1 component of rec in &z 1 @ rec( )( ) is evaluated.
It is not applicable to our bidirectional settings which rely on bulk semantics [6].
A static analysis of UnCAL was described in [1], but the main motivation
was to analyze the structure of graphs using graph schema, whereas our analysis
focus on the connectivity of graphs.

7

Conclusion

In this paper, under the context of graph transformation using UnCAL graphalgebra, enhanced static marker inference is first formalized. Fusion rule becomes
more powerful thanks to the static marker analysis. Further rewriting rules basedon this inference are also explored. Marker renaming for capture avoidance isformalized to support the rewriting rules. Under the context of bidirectionalgraph transformations [6], one of the advantage of static analysis is that we cankeep implementation of bidirectional interpreter intact. The marker analysis andrewriting proposed can be considered as dead-code detection and elimination.
We believe this technique can be used for other graph languages that basedon graph model that have named connecting points like input/output nodes.
Preliminary performance evaluation shows the usefulness of the optimization forvarious non-trivial transformations in the field of software engineering research.

Future work under this context includes reasoning about eﬀects on the backward updatability. Although rewriting is sound with respect to well-behavednessof bidirectional transformations, backward transformation before and after
rewriting may accept diﬀerent update operations. Our conjecture is that simplified transformation accepts more updates, but this argument requires further
discussions.
Acknowledgments We thank reviewers and Kazuyuki Asada for their thorough comments on the earlier versions of the paper. The research was supported
in part by the Grand-Challenging Project on “Linguistic Foundation for Bidirectional Model Transformation” from the National Institute of Informatics, Grantin-Aid for Scientific Research No. 20700035, Grant-in-Aid for Research Activity
Start-up No. 22800003, and Kayamori Foundation of Informational Science Advancement.

References
1. A. A. Benczúr and B. Kósa. Static analysis of structural recursion in semistructured
databases and its consequences. In ADBIS, pages 189–203, 2004.
2. P. Buneman, S. Davidson, M. Fernandez, and D. Suciu. Adding structure to unstructured data. In ICDT, volume 1186 of LNCS, pages 336–350, 1997.
3. P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language andoptimization techniques for unstructured data. In SIGMOD, pages 505–516, 1996.
long version appears as U.Penn TR MS-CIS-96-09.
4. P. Buneman, M. F. Fernandez, and D. Suciu. UnQL: a query language and algebra
for semistructured data based on structural recursion. VLDB J., 9(1):76–110, 2000.
5. K. Ehrig, E. Guerra, J. de Lara, L. Lengyel, T. Levendovszky, U. Prange,
G. Taentzer, D. Varró, and S. Varró-Gyapay.
Model transformation bygraph transformation: A comparative study.
Presented at MTiP 2005.
http://www.inf.mit.bme.hu/FTSRG/Publications/varro/2005/mtip05.pdf, 2005.
6. S. Hidaka, Z. Hu, K. Inaba, H. Kato, K. Matsuda, and K. Nakano. Bidirectionalizing graph transformations. In ACM SIGPLAN International Conference on
Functional Programming, pages 205–216. ACM, 2010.
7. S. Hidaka, Z. Hu, K. Inaba, H. Kato, K. Matsuda, K. Nakano, and I. Sasano.
Marker-directed Optimization of UnCAL Graph Transformations (revised version).
Technical Report GRACE-TR-2011-06, GRACE Center, National Institute of Informatics, Nov. 2011.
8. S. Hidaka, Z. Hu, H. Kato, and K. Nakano. Towards a compositional approach
to model transformation for software development. In SAC 2009, pages 468–475,
2009.
9. G. Rozenberg, editor. Handbook of Graph Grammars and Computing by Graph
Transformations, Volume 1: Foundations. World Scientific, 1997.
10. I. Sasano, Z. Hu, S. Hidaka, K. Inaba, H. Kato, and K. Nakano. Toward bidirectionalization of ATL with GRoundTram. In ICMT, pages 138–151, June 2011.
11. P. Stevens. Bidirectional model transformations in QVT: Semantic issues and open
questions. In MoDELS 2007, pages 1–15, 2007.
12. P. Wadler.
Deforestation: Transforming programs to eliminate trees.
In
Proc. ESOP (LNCS 300), pages 344–358, 1988.