BiG team
Aug. 2009
Nodes consist of three components, two of which are missing in normal nodes. Uppermost part shows input markers surrounded by curly braces ({}) if any. The middle part, which is always present, shows id. The bottom part shows output markers rendered in the same way as input markers, if any. Figure 1 shows an example. It includes a cycle which consists of the edge labeled with ``c'' from node n1 to itself. A default input marker & is shown at the root node n5 explicitly.
Readers who had read an old version of this document may have noticed the difference in the node format. Previously, nodes are rendered in rectangles, in which markers and id's are separated by horizontal lines as shown in Figure 2. This format is still supported and can be activated by setting global node ``shape'' attribute to ``record'' in dot file.
From a theoretical point of view, the forward evaluator produces
a result graph under a set of variable bindings, which consists of pairs
of variable name and bound (graph) value. The pairs are collectively
called environment. At the beginning of the evaluation,
we assume only one2
global variable $db, which is bound to an input graph,
resides in the environment.
During the backward evaluation, the evaluator produces, using updated
result graph, original environment and input expression, a new environment
in which the bound values (graphs) reflect the modification by users on
the result graph.
We can extract the modified input graph by extracting the value
bound to $db.
As for limitation, you can edit only the portion that comes
from the input graph. For example, assume the forward transformation is
{result: $db}3, which prepend an edge ``result'' on top of
the input graph (bound to $db). Then, if you edit the edge ``result'',
there is no way to reflect the effect back to input graph, because
that edge is not produced by the input graph. System captures this
situation by raising an exception (error message).
Putting it more precisely, this kind of modification violates one of the required round-trip properties called PutGet [2]: another forward computation using the modified environment should reproduce the same (modified) graph. In this case, the forward evaluation would produce the original graph (g instead of g' in Figure 3).
The most simple case in which a backward modification is guaranteed
to succeed, is the case when forward transformation expression is $db
itself. In this case (variable reference case in general), the backward evaluator
simply replace the bound value of the variable $db with the updated value.
By looking up the binding of $db, which obtain the updated value,
you can obtain the new source graph.
One of the crucial parts of the backward evaluation is to determine
to which operands should we propagate the updating effect, given an operator.
In case of the singleton (or edge constructor) as in {result:$db} above,
we decompose modified graph g' into top-level edge and the rest of the graph.
Backward evaluation is applied recursively on these components.
As another example, consider the append (
) case. It glues
the output nodes in the left hand side with input nodes
on the right hand side who has matching markers.
Figure 4 shows the result of forward computation of expression
![\includegraphics[width=4.0cm]{bd_db.uncal_elliptic.eps}](img1.png)
![\includegraphics[width=4.0cm]{bd_db.uncal.eps}](img2.png)
![\includegraphics[width=6.0cm]{failcase.eps}](img3.png)
![\includegraphics[width=4.0cm]{bd_append.uncal.eps}](img5.png)
(&z1 := {a : {src : &}},
&z2 := {b : {src : &}}) @ $db
Had the graph bound to $db been actually glued with the result of evaluating
(&z1:={a:{src:&}}, &z2:={b:{src:&}}), it would have been much
difficult to decompose since we should split glued (I/O) nodes.
We instead deliberately leave
edges between these nodes. These are
shown in Figure 4 as two edges labeled with ``!'' (bang) between
node n1015 and n5 as well as n1012 and n5.
The most interesting case is that of
rec operator. For the sake of
decomposition, we use bulk semantics for bidirectionalised evaluator.
This semantics generates a lot of
edges as well as unreachable
parts. The latter also participates in backward evaluation, whereas
the former also plays an important role in decomposition of the modified graph.
Please refer to
section 4 of [3]
for details.
$db.
select $G where {b : $G} in $db
$db.
select ($G1 U $G2) where {b : $G1} in $db,
{a : $G2} in $db
$db ended with an edge labeled ``a'' or ``b'', keeps those subgraphs that do
not contain an edge of ``a'' from their root, and glues that results with
new edges labeled 'result'.
select {result : $G1} where {_*.(a|b): $G1} in $db,
{$l : $G2 } in $G1,
not ($l = a)
select letrec
sfun a2d_xc({$l : $g}) =
if $l = a then {d : (a2d_xc($g))}
else if $l = c then a2d_xc($g)
else {$l : (a2d_xc($g))}
in a2d_xc($db)
select
letrec
sfun h({b : $g}) = {b : (a2e($g))}
| h({$l : $g}) = h($g)
and sfun a2e {a : $g} = {e : (a2e($g))}
| a2e {$l : $g} = {$l : (a2e($g))}
in h($db)
cycle((
& := {a:{a:&z1},b:{a:&z1},c:&z2},
&z1:= {d:{}},
&z2:= {c:&z2}
))
rec(\ ($l,$g).
if $l = a then {d: &}
else if $l = c then &
else {$l: &})($db)
associated with
union sequence
, just like nil
at the end of list in functional programming
--
and
are
(bisimulation) equivalent.
rec(\ ($l,$G).& := if $l = a then { b: & }
else { $l: & } )($db)
rec(\ ($l,$g).
if $l = a
then rec(\($l',$g').
if $l' = b
then $g'
else {})($g)
else {})($db)
select
{order:
{date: $date,
no: $no,
customer_name: $name,
addr: $a}
}
where
{customer.order: $o} in $db,
{order_of:$c, date:$date, no:$no} in $o,
{add:$a, name:$name} in $c,
{code:$code, info:$info, type:shipping} in $a
replace $G by {tgt:$G1}
where {Association: $G} in $db,
{dest: $G1} in $G
$db.
{result:$db}
$db via variable binding of $v.
let $v = $db in {result:$v}
This example shows the backward propagation of modification via variable binding
constructs. The sample modification provided renames the edge from
n0 to itself (cycle) to ``ModC''. You can see the reflection of this
modification back to source after backward evaluation.
&z1@rec(\ ($L,$T).
if $L=a then (&z1:= {xa:&z2},&z2:={$L:&z2})
else (&z1:= {$L:&z1},&z2:={$L:&z2})
)($db)
Considering that the input data includes a cycle, this example shows
our framework, as with the case of the original UnCAL, works in the
presence of cycles.
In the result graph of the forward evaluation, there are a lot of
edges (denoted by edges marked with ``!'') as well as unreachable parts.
These parts should not be visible to end users since they are not allowed to
edit. We plan to hide these parts in the graph presented to the end users.
But here these are exposed to demonstrate how it works.
The sample modification provided renames the label of edge between n1009 and
n1008 to ``ModD''. You can see after backward evaluation, the modification
is reflected to the edge from n2 to n1 in the input graph.
(&z1 := {a : {src : &}},
&z2 := {b : {src : &}}) @ $db
Since this forward transformation expression includes input and output marker
as well as disjoint union (the expression (e1, e2) is a syntactic
sugar of
e1 
e2), this example demonstrates the treatment of these constructors as well.
![\includegraphics[width=3.0cm]{g2.eps}](img12.png)
cycle((&z1 := {src: &z2, back: &z1},
&z2 := $db))
While
connects matching I/O nodes between two graphs,
cycle do the same thing within a graph.
The operand of
cycle here has two components: one
with I/O markers (
,
)
and the other
with I/O markers (
,{}).
Matching I/O nodes marked
& z1 in the first component
forms cycle, while another matching pair marked
& z2
forms inter-component connection from first component
to the second, which is further connected to graph bound to
$db.
Whether the expression you edit is interpreted as UnQL+/UnQL or not depends on whether you have selected UnQL+/UnQL sample or not. If you want to submit your own UnCAL query, you should select an UnCAL example at the first page.
You can see the ``Query or input has been edited'' checkbox below the textarea in which you can edit the query. This is checked automatically if the presented query is edited and informs the system of the fact so that the ready-made modified target example is invalidated because the result produced by the custom query and the ready-made example may no longer be consistent.
If you submit large or complex queries, system may time out (current setting is 5 minutes) to prevent server overloading.
[Show unreachable parts] shows nodes and edges that are
not reachable by traversing from the root node. Cycle,
and
rec operators may introduce unreachable parts, because
these operators glue subgraphs generated by subexpressions
by producing
edges that connects matching input and
output nodes of the subgraphs. Input nodes that has no
counterpart will leave the node and reachable parts thereof
unreachable.
Since unreachable parts as well as reachable parts
participates in backward evaluation, checking this option
would help understanding of not only forward semantics
but also backward semantics.
[Glue safe
in the view] glues source node and target node
of each epsilon edges and remove that edge if it is safe to do so. In general,
if source of
edge is an input node or has other outgoing edges,
and target of the
edge has other incoming edges,
gluing would introduce spurious path that is inexistent
before the gluing, so gluing does not take place.
Another source of danger is the ambiguity of correspondence
between graphs before and after gluing. If the two edges
end up with sharing their source and target as a result
of gluing, and users edit either of both of the edge,
it is difficult to determine to which edge
before gluing the editing effect should be propagated.
In this situation, check is ignored and gluing does not take
place.
Checking this option produces simple graph and easy to edit, while unchecking helps understanding of the forward semantics of the constructors.
Since rendering large graph is time-consuming (it may take several minutes), if a query that is expected to produce large graph if gluing would not have been applied is selected, this checkbox is checked and disabled.
[Apply Skolem terms] uses constructors that enables rendezvous between connected subgraphs. For example, bulk semantics uses Hub(nodeid,marker,exprid) 4 where expid identifies subexpression, and nodeid itself is a node ID. Bulk semantics generates nodes and edges independently from each input node and edge. Connecting these components are possible thanks to the Skolem terms. While edges (n1, l1, n2) and (n3, l2, n4) can be connected via node IDs n5 if n2, n3 and n5 coincide, the Skolem terms generated by rec and other constructors enable this coincident.
[Apply rewriting] applies UnCAL-level rewriting rules. This includes fusion rules of two successive applications of rec in [1].
[Escape 1st operand of
] applies Skolem term to each node of the graph
generated by the first operand of
. Users usually do not have to
check this option.
This option makes difference when you submit the following query.
let $v = {a: &} in
($v @ {b}) U ($v @ {c})
You can see in the result graph that the result of 
produced only
one
edge. This is because the first operands of both of the
operators are shared because they are produced by the same variable
reference
$v. This makes backward evaluation fail. Checking this
option will prevent this failure by splitting the two results of references
of
$v using expression id assigned differently for the two
.
Bdotty, our small extension of DOTTY editor, should be used in this editing. The tool should be installed easily if you already have DOTTY installed, which can be compiled on most of the operating systems. Please refer to Bdotty User's guide for installation instructions. Here we assume you have Bdotty command installed.
At the ``UnQL+/UnCAL expression evaluation result'' page, switch the radio button from ``Use edited sample dot file'' to ``Edit the sample edited dot file and upload my own:'' and follow the link ``download'' to obtain the result graph in DOT format. In Figure 6, the node n0 and the associated edge labeled ``c'' is about to be deleted.
You can also edit the label of an edge by selecting ``set edge label'' on the context menu that appears when it is called while pointing on the circle on the edge. On the text box in the dialog window, type in ``XXX'' to set the label to value ``XXX''. Select ``save graph'' on the same context menu (or type keyboard shortcut 's') and upload the DOT file by specifying the file in the file upload box on the demo page. Press ``submit'' to see the result of the backward evaluation.
![\includegraphics[width=8.0cm]{bdottyscreen.eps}](img17.png)