Home

GRoundTram Version 0.9.3a User Manual

1. JO 19p10 X 10 91814 O epum mur peye Sung QUIOJSN PIO AOWOISNZ Zumg 8 suns Qo au ppe A TUTORIAL FOR THE GROUNDTRAM SYSTEM CHAPTER 1 10 oseqeje T ILIWH PPIG Suryuosoiday PS ounSrq OAYOL JO 2240 Org LLL 00c Sung 31119 sums 00N 8007 21 91 8007 01 91 ojuN apoo adA1 1001 8007T L0 9T u oureu 1oulo sna 1 3 BIDIRECTIONAL TRANSFORMATION DEVELOPMENT 11 1 3 Bidirectional Transformation Development The development consists of the following three big steps An important feature of the GRoundTram system is that if a transformation from one model to the other is given then updating of either model can be correctly propagated to the other So in the development of our bidirectional transformation between the customer model and the order model we will put effort into development of a transformation mapping the customer graph model to the order graph model 1 3 1 Representing Customers and Orders Graphs To develop bidirectional transformation between two graphs models first of all we should be clear about the structures of the two graphs i e the graph schemas of the two graphs For our running example the structure of the customer graph can be define
2. parenthesized expression isempty expr is the graph empty isBool label isString label isInt label isFloat label isLabel label type testing true false boolean literal not cond cond and conde cond or condg logical op label labels label lt labelg label gt labelg label comparison 3 2 GRAPH CONSTRUCTION 39 A label is either a plain label an integer a floating point number or a string Arithmetic operations and string concatenation can be used label lwar label variable reference literal label literal label label concatenation label label label label label label label label arithmetic operation char NX NN SN literal letter edge label 10 9 decimal integer 0 9 0 o float number _ chart string Here is the operator precedence table Operator Associativity high left 7 left lt gt left not and left low or left UnCAL has two kinds of comments line comments start from and ter minate at the end of the line and block comments start from and terminate at Block comments are allowed to be nested 3 2 Graph Construction Graphs in UnQL and UnCAL are rooted and directed cyclic graphs with no order between outgoing edges They are edge labeled in the sense that all in formation is stored as labe
3. end Output validation message This finishes development of the forward transformation Two remarks are worth making First the command unqlplus is very powerful with many useful options one can get information about the options of the command unqlplus by typing gt unglplus help Second we can alternatively execute the following command to perform the forward transformation which will produce more additional files the ei file that contains more editing information and the xg file that represents the result graph being attached to the abstract syntax tree that are necessary in the backward transformation Note that we omit graph validation here gt fwd_uncal db customers_c uncal uq c2o_c ungl A dot orders_c dot png orders_c png xg orders_c xg ei orders_c ei ge pa One can check the result graph by either seeing the graph in the PNG format i e orders_c png or that in the DOT format i e orders_c dot Note that this forward transformation command without validation is quite convenient and useful because it allows us to test transformation without giving the definition of graph schemas 1 3 3 Type Checking Forward Transformation By specifying KM3 schemas via iv and ov options of the unglplus command we can dynamically check at each run whether the given input graph and the generated output graph meet the KM3 schemas In fact the check can also be done statically
4. gt dot Tpng o a png a dot 8 2 Options The following additional command line options are recognized by uncalcmd dbd file Loads a graph DOT format specified by file and binds it to variable db v 01 png dot cal t oa ea pa sr pi pn cg ht help The meanings are identical to those of unqlplus See section 2 rw Applies rewriting rules This includes fusion rules of two successive appli cations of rec in Buneman et all 2000 rec e2 o 1 rec rec e3 o ei 2 o rec e1 rec A l t rec ea e l t rec e1 t The first rule is applied when 2 1 does not depend on t The second rule is applied otherwise rec Interprets rec using recursive semantics Bulk semantics is used without this option lu Leaves unreachable parts in the result graph Since bulk semantics typically produces many unreachable parts these parts are removed by default Other operators that produces unreachable parts are cycle and This option is useful to examine the formal behavior of these operators le Leaves e edges in the result graph Since rec typically produces many edges especially in bulk semantics they are removed by default Other operators that produces e edges are cycle and U This option is useful to examine the formal behavior of these operators ls Leaves Skolem terms in the result graph Since rec produces Skolem terms which nests according to nesting of rec an
5. datatype String datatype Int class Customer reference name 0 String reference email 0 String reference add 0 Address reference order 0 Order class Address reference type 0 String reference code 0 String reference info 0 String class Order reference date 0 String reference no 0 Int reference order of 0 Customer The difference is that we have added the number constraints 0 to all fields currently chkuncal can deal only with this type of schemas The restriction will be eliminated in a future version For the detailed description of the subset of languages supported by chkuncal please consult Chapter Expected output graphs from c2date uncal should be a collection of date fields capture by the following schema Date km3 1 3 BIDIRECTIONAL TRANSFORMATION DEVELOPMENT 19 package Date datatype String class Date reference date 0 String To verify that the transformation is really correct with respect to the schemas what we need to type is the following one line of command gt chkuncal Customer_tc km3 c2date uncal Date km3 Then we will get the following diagnostics gt chkuncal Customer_tc km3 c2date uncal Date km3 Loading Schema and UnCAL files Converting UnCAL to MSO Generating auxiliary formulas Converting Schemas to MSO Validation process is running may take time Success
6. describing the output type The command line chkuncal in km3 transform uncal out km3 checks whether the transformation transform uncal converts all graphs sat isfying the input KM3 schema in km3 into graphs satisfying out km3 If the check succeeds the command prints Success as follows Loading Schema and UnCAL files Converting UnCAL to MSO Generating auxiliary formulas Converting Schemas to MSO Validation process is running may take time Success and returns exit code 0 If there found some error the command prints Fail ure Moreover it prints a counter example Loading Schema and UnCAL files Converting UnCAL to MSO Generating auxiliary formulas 75 76 CHAPTER 15 UNQL UNCAL TYPECHECKER CHKUNCAL Converting Schemas to MSO Validation process is running may take time Failure For a valid input T b TH the UnCAL program will produce an invalid output 45 T 57 In this case the exit code of the command is 1 15 2 Supported Subset of the Languages Currently the typechecker does not support the full languages of UnQL and UnCAL Here is the list of current restrictions For KM3 e All cardinality constraints must be 0 e Inheritance by extends is ignored e datatypes must be either of type Int or String e Multiple packages are not supported The schema must be closed in a single package e opposite
7. esult d Result of Example O b Result of 6 Example a Input of Examples Dl and c Result of Example Figure 2 1 Result Graphs of Query Examples on Figure This query first matches the graph pattern b G against the graph db and gets bindings for G and then produces the result according to the select part Figure shows the result of this query Example 2 The following query has multiple conditions in the where part and construction of graphs in the select part select 8601 U 8605 where b G in db La G2 in db It returns all subgraphs that are pointed by either b or a from the root Fig ure D 1 c shows the result of this query Regular Path Patterns Regular path patterns similar to XPath are provided for concisely expressing deep queries against a graph Example 3 Consider the following query select result G where _x alb 801 in db 181 805 in 8601 Sika It extracts all subgraphs G according to the regular path a b i e any path ending with an edge labelled a or b keeps those subgraphs that do not contain an edge of a from their root and glues the results with new edges labelled result It returns all subgraphs that are pointed by either b or a from the root Figure shows the result of this query 2 3 GRAPH EDITING 35 2 3 Graph Editing UnQL is a small extension of UnQL to support convenient specificat
8. this step fails Please select another node in this case 4 The user specifies the concrete values for each variable indicated by edges labeled with negative numbers Assume here that there are edges num bered 1003 and 1005 and the user want to fill them respectively with labels a and b gt bwdI_enum_uncal idot db dot q q uncal odot output dot opng result png ipt Hub 2 amp 9 uidot udb dot k 0 uodot uoutput dot nlv 1003 a nlv 1005 b executes similarly to the previous step but with the unspecified labels filled with the concrete values specified by nlv option s 12 2 Options The following additional command line options are recognized by bwdIg_uncal pa Prints the UnCAL expression given by q option Chapter 13 UnCAL Forward Interpreter with Insertion fwdI_uncal This chapter describes the forward transformation part of bidirectional UnCAL interpreter with insertion handling fwdI_uncal which interprets UnCAL source files for input graphs and produces output graphs with trace information for backward evaluation with insertion It also produces an insertion unit the unit of insertion on the view that corresponds to the source The insertion unit can not be produced all at once but incrementally as described in the following section This command is intended to be used with backward interpreter bwdI_uncal described in chapter 13 1 Overview of the Forward Interpreter Th
9. 1 4 R Tarjan Depth first search and linear graph algorithms SIAM J Comput 1 2 146 160 1972 doi http dx doi org 10 1137 0201010 W3C XML Schema WG W3C XML Schema http www w3c org XML Schemal 85
10. A Counter Example from chkuncal gt chkuncal Customer_tc km3 c2date bad uncal Date km3 g counter example dot gt dot counter example dot Tpng o counter example png This will produce the visualized counter example in Figure LA 1 3 4 Testing Backward Transformation One important feature of the GRoundTram system is that it can not only keep trace information between the source input and the target result models but can also propagate the changes on the target model to the source Checking Trace Information We can check the trace information by turning on the option sb set skolem bulk when executing the fwd_uncal command so that the nodes of the result graph can be attached with information showing where the nodes come in the source graph gt fwd_uncal db customers_c uncal uq c2o_c ungl dot orders_c_trace dot png orders_c_trace png xg orders_c_trace xg ei orders_c_trace ei sb ge pa 1 3 BIDIRECTIONAL TRANSFORMATION DEVELOPMENT 21 The generated graph is saved in the file orders_c_trace dot It has the following contents digraph g node shape ellipse FrE FrE FrE FrE FrE FrE FrE FrE FrE FrE FrE FrE FrE FrE FrE C ImT 1047 amp 37 shipping 36 1051 38 String 37 1053 54 type 38 1055 54 info 32 1057 54 35 1059 66 64 1061 55 Address 54 1063 66 55 1065 52 17 1067 52 4 20 1069 14
11. By passing input output KM3 schema files and a transformation described either in UnQL or UnCAL to the chkuncal command we can verify that any graph satisfying the input schema will always be transformed to an output graph satisfying the output schema In other words once we have verified the correctness by chkuncal we can be 18 CHAPTER 1 A TUTORIAL FOR THE GROUNDTRAM SYSTEM sure that for all correct input graphs the output graphs must meet the schema After the static checking we can safely omit the per run checking by ov To use the typechecking facility of chkuncal we need the MONA tool Project to be installed on our system Before trying the following exam ples please download and set up MONA from http www brics dk mona Static Type Checking Example Consider we would like to check the correctness of the following transformation c2date uncal which extracts all the shipping dates from the customer database the examples are placed in the example typecheck directory rec L G if L Customer then amp else if L order then amp else if L Order then amp else if L date then Date date G else db Expected input graphs are those meeting the schema Customer km3 used in the previous section But since for a technical reason the current version of chkuncal does not accept the schema we check the correctness against a slight variant of the schema Customer_tc km3 package Customer_tc
12. Customer 66 1071 52 order_of 14 1073 53 0rder 52 1075 66 order 53 1077 67 Customer 66 1079 label N FrE FrE FrE FrE FrE FrE FrE FrE FrE FrE ImT 1047 amp 37 shipping 36 1051 38 String 37 1053 54 type 38 1055 Here the name of each node is very long containing information of all the edges in the source graph that contribute to the construction of this node For example the first node in the above example shows that it is related to the edges such as 37 shipping 36 38 String 37 in the source graph in Figure LA Editing the Order Graph Before showing how to do backward computation to propagate changes on the order graph to the original customer graph let us see how to change the order graph by editing Since the order graph with trace information is long and difficult to read we shall work on the order graph in the file orders_c dot where all the nodes have simpler names digraph g node shape ellipse n65658 label amp n N n65115 label NN J n65109 label N 22 CHAPTER 1 n44897 label AN n44891 label N n44201 label N n44195 label N n64 L label N n63 label AN 162 label N n65658 gt n65115 n65658 gt n44897 n65658 gt n44201 n65115 gt n17 lab n65115 gt n20 lab n651
13. PutGet property and we check it by another forward transformation and report an error if the PutGet is not satisfied 16 1 Forward Transformation We can run a forward transformation by gt bx_quick f uq c2o_c ungl idot customers_c dot odot orders_c dot which will apply the transformation c2s_c unql to the database customers_c dot and will produce the result in orders_c dot If we want to check if the input database meets the schema Customers km3 during forward transformation we can do so by the following command line gt bx quick f uq c2o_c ungl idot customers c dot odot orders c dot ikm3 Customer km3 79 80 CHAPTER 16 A QUICK BIDIR INTERPRETER BX_QUICK ip Customer Here the last option denotes the input validation package as used in the type checker 16 2 Backward Transformation For the backward transformation we do not allow insertion to be done together with inplace updates or deletion they can be done one after another First of all let us see how to proceed with inplace udpates and deletion Now suppose that we modify the orders_c dot as follows e update the edge 11 16 10 2008 10 to 11 31 01 2010 10 e Update the edge 14 1001 13 to 14 1100 13 e Delete the edge 50 info 26 and save it to orders_c1 dot To reflect these changes to the source database we apply the backward transformation as follows gt bx quick b uq c20_c
14. edge is an input node or has other outgoing edges and the target of the e edge has other incoming edges gluing would introduce a spurious path that is inexistent before the gluing so gluing does not take place Another source of danger is the ambiguity of correspondences 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 edges it is difficult to determine to which edge before gluing the editing effect should be propagated In this situation this option is ignored and gluing does not take place Specifying this option produces a simple graph which is easy to edit while unchecking helps understanding of the forward semantics of the constructors Since rendering a large graph is time consuming it may take several min utes when you execute a query that is expected to produce a large graph if gluing would not be applied this option is recommended sb Uses Skolem terms which are 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 nl 11 n2 and n3 12 n4 can be connected via node IDs n5 if n2 n3 and n5 coincide the Skolem
15. example Figure LO shows the result of the backward transformation in which prop agated modifications on edges or nodes are indicated by the following colors deleted parts are displayed in added parts are displayed in purple and modified labels are displayed in red Unreachable parts if any are displayed in It is worth noting that the current backward transformation can fully sup port propagation of all valid in place modification but only partially support propagation of insertion and deletion that are independent of computation of structural recursions We treat complex insertion and deletion on graphs that are produced by structural recursion in a special way as discussed below Reflecting General Insertion To be concrete assume that we are given three files e a2d xc uncal a transformation to replace all labels a by d and short edges labeled c rec 1 g if 1 a then d amp else if 1 c then amp else 1 amp db e db dot a dot file representing the input graph in Figure IC Note that this dot file can be obtained from the following uncal code db uncal cycle amp f a fa amp z1 b fa k amp z1 c amp z2 amp 21 d amp z2 c amp z2 by the following command gt uncalcmd q db uncal dot db dot e to_be_inserted dot a dot file representing the graph in Figure to be inserted to the view later Note this dot file can be obtained from an uncal file as seen
16. if L1 In then Out rec L2 G2 if L2 keep then G1 else 861 else db It selects a list of elements pointed by edges labeled In in the outer recursion and only when it G1 has an edge labeled keep it is kept for the output and the labeled Out This transformation should conform to the following pair of input output schemas package annot_in class In reference keep 0 In package annot_out class Out reference keep 0 In class In reference keep 0 In To verify that the transformation indeed conforms to the schema we need to annotate type information because the variable G1 is used inside the nested recursion apart from its declaration Otherwise we get an error message like Loading Schema and UnCAL files Converting UnCAL to MSO Error UNSUPPORTED in Typecheck nested recursion requires variable annotation for G1 Here is the annotated version of the transformation rec L1 G1 if L1 In then Dut rec L2 G2 if L2 keep then G1 annot_in km3 BIn else G1 annot_in km3 BIn else db 00 annot_out km3 78 CHAPTER 15 UNQL UNCAL TYPECHECKER CHKUNCAL The annotation is expressed by specifying the name of the schema file followed by the symbol and it asserts that the result of evaluating the expression conforms to the schema The variable G1 itself needs to be annotated and moreover if we
17. label template expr fname template let gvar template let 1 fnameC lpe name Ip in template letrec sfun fname fname fname and and sfun fname frame frame in template guar t3 template U templates if boolcondthen template else templates conditional CHAPTER 2 UNQL label template union of graphs union of graphs value of an expression function application in templates variable binding gp template gp2 templates 9pn y template structural recursion lp11 9p11 template y C lp12 9p12 templates Alp im 9P 1m template 17 templatenm Alpn2 gPne templateng Prim y templatenm mutual structural recursion graph variable The following BNF defines Boolean conditions and or binding conditions bool_cond boolean condition bind_cond binding condition parenthesized expression is the graph empty boolean literal not bool bool cond and bool condo logical op label lt labels label gt label label comparison gp in template binding condition bc bool_cond bool cond isempty template true false bool_cond or bool conde label labels bind cond The following BNF defines label patterns x label
18. terms generated by rec and other constructors enable this coincident to time Sets timeout to time seconds Evaluation is aborted after this time period The bidirectional evaluator takes more time than unidirectional evaluators due to maintenance of trace information This option is useful for batch processing in which a long running execution is undesirable cs Use simplified semantics for cycle in which only mismatched marker re mains Default semantics leaves every input node regardless of combina tion of I O nodes in the operand np Do not prefix output base node number with n This flag is just the opposite effect of pn in unglplus and uncalcmd Since our current edi tor is DOTTY and our variant of it BDOTTY the default behavior is prefixing to align with these tools t Prints elapsed user CPU time broken down to 9 2 OPTIONS e rewriting if rw option is specified e forward execution of UnCAL expression 63 64CHAPTER 9 UNQL UNCAL FORWARD INTERPRETER FWD_UNCAL Chapter 10 UnCAL Backward Interpreter bwd_uncal This chapter describes the backward transformation part of bidirectional UnQL UnCAL interpreter bwd_uncal which interprets UnQL UnCAL source files for modified output graphs and produces input graph in which modification on the output graph is reflected Note that this propagation does not always succeed This command is intended to be used with fwd_uncal described in chapter A 10
19. use annotations inside each rec expression the rec expression itself must be annotated too In other words to use annotated verification we need to declare the types of input parameters and return values of each recursive function In the name of schema files by separating by a whitespace we can also specify a specific type to be used as in annot in km3 BIn If omitted the root type of the schema is used as is in annot out km3 For the names of the types for each Class in the schema two types HClass and BClass can be used The former denotes the head node of the class from which the edge labeled Class should go out The latter denoting the nodes below the edge Class is the type for nodes that have the set of edges labeled by the reference fields in the schema definition An annotation G schema works for typechecker in two ways First the graph obtained by the annotated expression must conform to the schema the verifier is obliged to verify the conformance Second in the body of the rec expression the use of the variable G can be assumed to be bound to a node pointing to an arbitrary graph satisfying the schema the verifier can use this assumption for checking the other parts of the transformation Note that currently the counter example in the case of a verification failure is generated only for the whole transformation and not for each annotation 15 4 Options The following additional command line options are reco
20. variable rpp regular path pattern The following BNF defines graph patterns gp gvar lp1 9p1 const graph variable gpn union of graphs constant 2 2 GRAPH QUERYING 33 The following BNF defines regular path patterns rpp label_const label label rpp rpp concatenation rpp rpp union option rpp one or more zero or more The following BNF defines label expressions label lvar label variable label_const constant label label concatenation Variables start with the sign The label variables Ivar and graph variables gvar are not lexically distinguished letter a z A Z 0 9 _ lvar letter guar n letter letter function name Operator precedence and associativity is Operator Associativity high not isempty left left left right lt gt E and left or left U left low left 2 2 Graph Querying 2 2 1 The select where Construct A query of the form select template where bc bc extracts information from graphs based on the binding and or Boolean conditions bc bc and constructs a graph according to the template Example 1 The following query returns subgraphs that are pointed by b from the root of db select G where b G in db 34 CHAPTER 2 UNQL
21. 1 Overview of the Backward Interpreter This command evaluates an UnQL UnCAL query on specified output graph along with trace information and produces an input graph with modification on the output graph being reflected The command line gt bwd_uncal db src uncal xg result xg ei bd ei dot result dot ucal srcprime uncal png srcprime png loads an input graph specified by file src uncal and binds to variable db interprets UnQL UnCAL source backwards using evaluation mode that had been saved in result xg and result ei by the fwd_uncal command and saves updated source graph to srcprime uncal in UnCAL format It also saves the image of the updated source graph in srcprime png for preview Options db xg ei and dot are mandatory 10 2 Options The following additional command line options are recognized by bwd_uncal v Prints version information 1DOT file can be accepted as well 65 66 CHAPTER 10 UNCAL BACKWARD INTERPRETER BWD_UNCAL udot file Saves updated source graph to file in DOT format pa Prints UnCAL input expression saved in file specified by xg option cm Colors modification to source DB specified by png Modifications propa gated by the backward transformation are indicated by the color of edges or nodes deleted parts are displayed in added parts are dis played in purple and modified labels are displayed in red Unreachable parts if any are displayed in np Do not prefix node
22. 15 gt n64 lab n65115 gt n65109 n64 gt n63 label n63 gt n62 label n54 gt n38 label n54 gt n32 label n54 gt n35 label n49 gt n48 label n48 gt n47 label n38 gt n37 label n37 gt n36 label n35 gt n34 label n34 gt n33 label n32 gt n31 label n31 gt n30 label n20 gt n19 label n19 gt n18 label n17 gt n16 label n16 gt n15 label n13 gt n12 label n12 gt n11 label n10 gt n9 label n9 gt ng label n6 gt n5 label n5 gt n4 label n3 gt n2 label n2 gt ni label A TUTORIAL FOR THE GROUNDTRAM SYSTEM label label label el no el date el customer_name label addr String 1 type info code String Kato String shipping 1 String 200 777 String BiG office of Tokyo String 16 07 2008 Int 1001 String 16 10 2008 Int 1002 String X 16 12 2008 Int 1003 Order 1 Order 1 Order 1 Changes on the order graph can be done by directly editing its dot file For instance we may edit the above file by changing the line n31 to n31 gt n30 label gt n30 label BiG office of To
23. GRound Tram Version 0 9 3a User Manual Soichiro Hidaka Zhenjiang Hu Kazuhiro Inaba Hiroyuki Kato Kazutaka Matsuda Keisuke Nakano National Institute of Informatics Japan University of Tokyo Japan The University of Electro Communications Japan Current affiliation is Google Copyright c 2008 2013 The BiG Team All rights reserved http www biglab org i Acknowledgments This research being one key project in the GRACE Center was supported by the Grand Challenging Project Program of National Institute of Informatics the Grant in Aid for Scientific Research B of MEXT of Japan under Grant No 22300012 the Grant in Aid for Scientific Research C No 20500043 En couragement of Young Scientists B of the Grant in Aid for Scientific Research No 20700035 Encouragement of Young Scientists B of the Grant in Aid for Scientific Research No 11024353 and the National Natural Science Foundation of China under Grant No 60528006 We would like to thank Mary Fernandez from AT amp T Labs Research who kindly provided us with the SML source codes of an UnQL system which helped us a lot in implementing the GRoundTram system in Objective Caml We would like to thank all the users of the GRoundTram for their valuable feedbacks Bernhard Hoisl contributed to improve the readability of the manual by proofreading iii ACKNOWLEDGMENTS Contents A dg Overview A orial for the GRound Iram ste
24. Model Transformation 1 2 The Customer2Order Problem As a concrete example we consider the problem of developing a bidirectional transformation between the customer model customer graph and the order model order graph which is adapted from a similar example in the textbook on model driven software development Pastor and Molina 2007 Figure gives a simple graph representing customers information The graph has a root pointing to two customers each having a name some email addresses several addresses of different types e g shipping or contractual cus tomer address A customer can have many customer orders On the other hand Figure shows orders information which actually corresponds to those orders in the customers graph that are of type shipping Each order contains order information of the date the order number the customer name and the address to which the goods should be delivered We shall show how to construct a bidirectional transformation between these two graphs such that changes on one graph can be propagated to the other one For example if we change the BiG Office of Tokyo to BIG Office at of Tokyo in either graph we should propagate it to the other THE CUSTOMER2ORDER PROBLEM 1 2 aseqeyeq Ingu Iwony Surjyuosoidey F APAI ZT mI 8007 71 91 00 170004 Surddmgs Jo yo 019 TOO 8007 01 91 4 1001 8007 L0 91 3ums uns 1 ung
25. Of is ignored For UnCAL e Nested structural recursion cannot refer to outer variables e g in rec L1 G1 rec L2 G2 e db the body e of the inner rec can use L2 and G2 but not L1 G1 nor db To verify nested recursion a user needs to add annotations to the UnCAL source code For the details see Section 5 3 e In the condition part of if expressions predicates such as isempty or isString cannot be used Comparisons L lab between label vari ables and literal labels and their boolean combination are allowed e let or 11 expressions are not supported Neither is doc For UnQL the above restrictions on UnCAL can be rephrased as follows e Joins i e twice or more occurrence of the same variable in where clause are not allowed To verify joins user needs to add annotations to the UnCAL source code For the details see Section e Variable bindings where x in ie non variable expression in right hand side of in in where clauses are not allowed Querying where in x right hand side of in is a variable is ok e Cannot use isempty isString doc etc In the future these restrictions should be removed 15 3 ANNOTATION 77 15 3 Annotation For verifying an UnCAL transformation that contains nested recursion that refers to variables introduced by the outer structural recursion the user must add type annotations Consider the following simplest example rec L1 G1
26. The message Success means that the transformation is verified that it never produces ill typed outputs To see what happens if we try to verify a type incorrect transformation let us consider another example c2date bad uncal rec L G if L Customer then amp else if L order then amp else if L Order then amp else if L date then Date data G else db Can you see the difference This version has a typo data instead of date which makes the output not conforming to the schema The chkuncal can detect the badness as follows gt chkuncal Customer_tc km3 c2date bad uncal Date km3 Loading Schema and UnCAL files Converting UnCAL to MSO Generating auxiliary formulas Converting Schemas to MSO Validation process is running may take time Failure For a valid input Customer order Order date order Customer the UnCAL program will produce an invalid output Date data When an error was found as above chkuncal always exhibits a counter example i e a graph that satisfies the input schema but yields an output graph not satisfying the output schema to help fixing the bug By using the g option the counter example is exported in the dot format of the graphviz system 20 CHAPTER 1 A TUTORIAL FOR THE GROUNDTRAM SYSTEM Chkuncal a counter example A valid input tree produces an invalid output tree Customer Customer ate date Figure 1 4
27. UnCAL Backward Inter preter for Insertion of Graph based on Enumeration This command performs the reflection of insertion of a graph on the target back to the source graph It provides more direct access to the implementation of the command bwdIg_uncal in chapter budI enum uncal works on the view that reveals trace information in their node IDs epsilon edges and requires selection of a graph to be inserted from the candidates enumerated by the implementation This command is used in the following steps 1 Forward execution gt bwdI enum uncal idot db dot q q uncal odot output dot opng result png loads an input graph specified by file db dot and and binds to variable db interprets UnCAL source q uncal and saves the output target graph in file output dot It optionally saves the PNG file of the output in result png if it is specified Options idot q and odot are mandatory Note that unlike bwdIg uncal the target graph saved in output dot re veals the raw internal representation which includes trace ID of the nodes and epsilon edges The user determines the insertion point in terms of the ID of the node on the target graph by examining output dot or result png Let s assume here that the node Hub 2 amp 9 is selected The node ID enriched with 69 TOCHAPTER 12 INTERPRETER WITH ENUMERATION BASED INSERTION OF GRA trace information may be complex to type in but if you open the dot file with bd
28. above Note that by forward evaluation of a2d_xc on db dot we can easily obtain a view view dot as in Figure C by running gt uncalcmd idot db dot q a2d_xc uncal odot view dot Now to demonstrate reflection of insertion on the view to the input we may execute the following command 1 3 BIDIRECTIONAL TRANSFORMATION DEVELOPMENT 25 Figure 1 6 An Input Graph for a2d_xc Figure 1 7 A View Graph Produced by a2d_xc 26 CHAPTER 1 A TUTORIAL FOR THE GROUNDTRAM SYSTEM Figure 1 8 A Graph to be Inserted to the View Produced by a2d_xc gt bwdIg_uncal idot db dot q a2d_xc uncal odot oview dot ipt 3 tidot to_be_inserted dot uidot udb dot uodot uview dot to insert the to_be_inserted graph to the view at the node say numbered 3 resulting in the graph in Figure LY and reflect this insertion to the input graph resulting in the graph in Figure L TU 1 4 More Examples More examples for bidirectional model transformation can be found at the fol lowing demo page of the GRoundTram system http www biglab org demo html This demo page enables one to test all the functionality of the GRoundTram system without the need to install the system on one s local computer 1 4 MORE EXAMPLES 27 Figure 1 9 An Updated View Figure 1 10 An Updated Input Graph A TUTORIAL FOR THE GROUNDTRAM SYSTEM CHAPTER 1 28 yder 5190103510 8007 71 91 00 ITemovnu
29. ave evaluation time In case of recursive semantics that is based on primary definition of structural recursion FU t O fd it suppress recursion to f t if e l t produces no output marker i e f is essentially non recursive ea Applies Skolem term to each node of the graph generated by the first operand of Users usually do not have to specify this option See Description of bidirectional UnQL UnCAL demonstration for more in formation pa Prints UnCAL expression after desugaring pu Prints UnQL expression before desugaring m Produces unique name for each marker in the body of rec Desugaring module usually reuses marker symbols for different rec bodies However when results of two different rec are unified using operators such as U undesired node sharing may result This form of UnCAL may be produced from an UnQL expression of the form select U select This option suppresses this sharing by using different set of markers for different rec This sharing can be avoided using pi option as well Non recursive rec also uses explicit markers when this option is specified For example rec A l t 1 t db becomes amp 21 rec A l t amp z 1 t db sr Uses Skolem term 51 in Buneman et all 2000 in the evaluation of using recursive semantics Straightforward interpretation of recursive se mantics would not use Skolem term that is usually used for bulk semantics but undesired s
30. d in the schema language KM3 ATLAS group 2006 be concrete we build a file called Customer km3 as follows package Customer datatype String datatype Int class Customer reference name String reference email 1 String reference add 1 Address reference order 0 Order class Address reference type String reference code String reference info String class Order reference date String reference no Int reference order_of Customer Figure gives an instance graph that satisfies this structure This instance graph is clearly specified in UnCAL as follows For later explanation we save it in the file customers_c uncal amp src cycle amp src Customer amp customeri Customer amp customer2 12 CHAPTER 1 A TUTORIAL FOR THE GROUNDTRAM SYSTEM amp customeri name String email String tanaka biglab email String tanaka gmail add Address addi order Order amp orderi order Order korder2 amp customer2 name String Kato email String kato biglab add Address amp addi add Address amp add2 order Order amp order3 amp addl type String shipping code String 200 777 info String BiG office of Tokyo amp add2 type String contractual code String 100 888 info String IPL of Tokyo a
31. d may make the result graph too large to perceive the entire structure they are renamed to flat numbers by default This option is useful to examine the formal behavior of rec Other operators are extended by us to produce similar structured IDs if pi option is specified These U 4 amp output marker with ea option and cycle 8 2 OPTIONS 59 pr Prints UnCAL expression that is actually evaluated This is useful to ex amine the expression after rewriting This is identical to the expression printed by pa option if rw option is not specified rc Renders record shape nodes using node attribute record in DOT format of Graphviz Default is ellipse This option is useful when you edit the DOT format file produced by dot option using DOTTY instead of BDOTTY Please refer to Description of bidirectional UnQL UnCAL demonstration for the usage of record mode 60 CHAPTER 8 UNCAL INTERPRETER UNCALCMD Chapter 9 UnQL UnCAL Forward Interpreter fwd_uncal This chapter describes the forward transformation part of bidirectional UnQL UnCAL interpreter fwd uncal which interprets UnQL UnCAL source files for input graphs and produces an output graph with trace information for backward evaluation This command is intended to be used with bwd_uncal described in chapter ID 9 1 Overview of the Forward Interpreter This command evaluates UnQL UnCAL queries on a specified input graph and produces an output
32. eted from its original graph In contrast the following transformation keeps the persistent classes as result select result class where Association src dest Class class in db is_persistent Boolean true in class So we may consider the delete as the dual of the select 2 3 3 The extend where Construct The extension construct extend where is used to extend a graph with another one For example we may write the following transformation to add a date to each class extend _ Class gt with date 2011 3 4 in db 36 CHAPTER 2 UNQL Association Association dest name pre Association dest Association lass Btring Class src of Class src of String 7 D amp D is_persistent name phone name pttrs Nis persistent Nis persistent name address DO DOS OD Attribute Boolean String Btring Attribute Boolean Attribute Boolean tring QO O M DON type nameNis primary true Phone Address is primary false_ type primary fame true Person G GO CO CO CO CO Cf CO CO CD CO PrimitiveDataType String Boolean Boolean String rimitiveDataType Btring D OO OO gt name number true rue addr tring Btring l Integer String Co Figure 2 2 A Class Model Represented by an Edge Labelled Graph Chapter 3 UnCAL UnCAL is the core graph algebra of the graph query language UnQL IBu
33. ge whose label has the same type and whose destination vertex has no edge This step is repeatedly performed until all vertices in the graph are visited This procedure always terminates because the number of vertices are finite 4 2 VALIDATION package Class datatype String datatype Boolean abstract class NamedElt attribute name String class Association extends NamedElt reference src Class reference dest Class class Class extends NamedElt attribute is_persistent Boolean reference attrs Attribute class Attribute extends NamedElt attribute is_primary Boolean reference type PrimitiveDataType class PrimitiveDataType extends NamedElt Figure 4 2 Schema for UML Classes 46 CHAPTER 4 KM3 Part III Command References Chapter 5 GRoundTram Main Command gtran This chapter describes the main command that invokes subcommands They are described in the following chapters 5 1 Overview of the Main Command This command invokes each subcommand with their respective arguments The following command line gt gtram fwdI_uncal db db dot q trans uncal png result png dot result dot invokes command fwd_uncal described in chapter Note that the arguments for the subcommand should follow a double hyphen The commands that can be invoked are summarized in Table Each command should be ex ecutable by having its inhabiting directory
34. gnized by chkuncal c Compilation only It just generates an MSO formula representing the type correctness and does not carry out its validation g file Saves a counter example graph to file in DOT format Specifying g will output the graph to the standard output help help Prints the help message I Specifies a path to find UnQL UnCAL files o file Specifies the name of the intermediate mona file to be passed to the MONA tool The default file name is obtained by replacing the suffix uncal or ungl of the specified UnQL UnCAL file by mona Speci fying o will output the MSO formula to the standard output q Suppress printing some messages v Prints version information Chapter 16 A Lightweight Quick Bidirectional Interpreter bx_quick This chapter describes how to use the bx_quick command for both forward and backward transformation There are two purposes for implementing this command One is to provide a single command for both forward and backward interpreters The second also very important it does backward transforma tion very quickly in a lightweight way Different from the general backward transformation which reverses the forward transformation step by step we do backward transformation by a direct reflection of the updates on the view to the source by just analysing the tracing information without looking into com putation steps This reflection cannot guarantee the
35. graph with trace information The command line gt fwd uncal db src uncal uq trans unql png result png dot result dot xg result xg ei bd ei loads an input graph specified by file src uncall and binds to variable db interprets UnQL source trans ungl and saves the executed UnCAL ex pression augmented with result graph to result xg It also saves the result graph to DOT file result dot for editing and further backward evaluation with bwd_uncal Various evaluation information is also stored in bd ei These files together with source graph src uncal should be passed to bwd uncal when backward evaluation is necessary Options db dot xg and ei are mandatory As for transformation either uq UnQL query or q UnCAL query should be specified The image of the result graph stored in result png is just for preview and not required for backward evaluation Unlike the unidirectional evaluator uncalcmd bulk semantics is always used for traceability 1DOT file can be accepted as well 61 62CHAPTER 9 UNQL UNCAL FORWARD INTERPRETER FWD_UNCAL 9 2 Options The following additional command line options are recognized by fwd_uncal q file Evaluates an UnCAL query specified by file instead of UnQL V pa rw su ea The meanings are identical to those of uncalcmd See section RA ge Glues source node and target node of each e edge and removes that edge if it is safe to do so In general if the source of an
36. haring might result when transformation is in a specific form described in m option section without this option pi Uses node id based on lexical position of node construction expression Without this option new node id is generated for each evaluation even if node construction expression is lexically identical This option makes expressions referentially transparent albeit with more complicated node IDs that may make visualized graph nodes larger pn Prefixes output base node number with n This is an alignment to the node id format produced by DOTTY and our variant of it BDOTTY This option is necessary if you edit output DOT file with these editors 54 CHAPTER 6 UNQL INTERPRETER UNQLPLUS cg Contracts the output graphs to their normal form based on bisimulation equivalence After contraction no two nodes are bisimilar to each other In particular leaf nodes nodes that has no outgoing edges are bisimilar to each other so they all shrink to one node Since UnQL and UnCAL is based on bisimulation transformation may introduce redundant nodes that are bisimilar to each other This option is useful when such redundancy has to be eliminated Note that the normal forms obtained may have different node ID assign ments although they are isomorphic to each other even if they are generated from bisimilar graphs Since Graphviz which we use as our graph layout tool depends on the ID the difference may result in a d
37. hen rec L code if L code then rec L info if L info then rec L fv1 if L type then 16 CHAPTER 1 A TUTORIAL FOR THE GROUNDTRAM SYSTEM rec L fv2 if L String then rec t fv3 if t shipping then Order date date no no customer_name name addr Address a else 0X fv2 else OX fv1 else OX a else a else a else c else fv4 else c else 0 else 0 else fv5 else 0 else fv7 else fv6 else 1 3 BIDIRECTIONAL TRANSFORMATION DEVELOPMENT 17 db end Executed UnCAL expr Evaluation took 1 629894 CPU seconds begin Output validation message Output validation took 0 000101 CPU seconds Validation succeeded VMap Bid 2 gt datatype Int Bid 5 gt datatype String Bid 8 gt datatype Int Bid 11 gt datatype String Bid 14 gt datatype Int Bid 17 gt datatype String Bid 20 gt datatype String Bid 23 gt datatype String Bid 26 gt datatype String Bid 29 gt datatype String Bid 33 gt datatype String Bid 35 gt klasse kname Address Bid 37 gt klasse kname Address Bid 39 gt klasse kname Address
38. iffer ent layout ht Turns on holistic transitive closure TC computation optimization in rec help for both bulk and recursive semantics rec A l t e db requires computation of TC for every node in the graph bound to db By default this TC is computed on per node basis ht option let the interpreter compute the TC at once enabling the reuse of TC for a node to compute TC of the nodes in the vicinity of the former node However since default TC computation is already efficient for a small num ber of nodes because it performs one depth first search only using index from node to outgoing edges this option may cause a performance slow down It performs better only when the input graph has large strongly connected componentsA i e many of the nodes in the graph are connected to each other either directly or indirectly and query visits most of the nodes Displays list of options 1The partition refinement alogithm by Paige and Tarjan Paige and Tarjan 1957 is used 2Captured by Tarjan s algorithm Tarjan LIZA Chapter 7 UnQL to UnCAL Compiler desugar This chapter describes UnQLt compiler desugar which converts UnQL source files to equivalent UnCAL file 7 1 Overview of the Compiler The command line gt desugar trans ungl translates an UnQL source file trans ungl to UnCAL and prints it to standard output 7 2 Options The following additional command line options are recognized by desugar v a
39. included in the user s command search paths 5 2 Options The following additional command line options are recognized by gtram d Prints debugging information help Displays list of options 49 50 CHAPTER 5 GROUNDTRAM MAIN COMMAND GTRAM command chap description unqlplus execute UnQL transformation validate graph against KM3 schema desugar a converts UnQL file to equivalent UnCAL files uncalcmd execute UnCAL unidirectionally fwd_uncal foward execution of UnQL UnCAL for in place updates bwd_uncal backward execution of UnQL UnCAL for in place up dates bwdIg_uncal bidir execution of UnCAL for insertions bwdI_enum_uncal bidir execution of UnCAL for insertions based on candi date enumeration fwdI_uncal forward execution of UnCAL for insertions based on in sertion units bwdI_uncal backward execution of UnCAL for insertions based on in sertion units chkuncal 15 static typechecking of UnQL UnCAL Chapter 6 UnQL Interpreter unglplus This chapter describes the UnQL interpreter unglplus which interprets UnQL source files for input graphs and produces output graphs in various formats 6 1 Overview of the Interpreter This command evaluates UnQL queries on a specified input graph by trans lating the UnQL to UnCAL graph algebra and then interpret the algebra to produce an output graph Output formats can be DOT for Graphviz package UnCAL and other image formats sup
40. ion of graph transformations model transformations We extend UnQL with three editing constructs for transforming graphs replace delete and extend For graph editing UnQL employs snapshot semantics which is widely used in many query languages such as SQL XQuery XQueryU Flux and so on Snap shot semantics consists of two logical phases of processing first it specifies nodes to be updated then updates are applied to the nodes The semantics of the graph editing is that for a given graph starting from the root node of the graph it traverses every path and specifies nodes to be updated then performs editing on the nodes 2 3 1 The replace where Construct The replacement construct replace where is used to replace a sub graph by a new graph For example consider the Class graph in Figure 2 2 how to prefix every name of the class by class_ can be specified as follows Note that is a built in function which performs string concatenation replace _ Class name String gt u by class_ name in db where name v in u 2 3 2 The delete where Construct The deletion construct delete where is used to describe deletion of part of the graph Consider the Class graph in Figure 2 2 how to delete all persistent classes can be described by delete Association src dest Class gt class db where is_persistent Boolean true in class where the subgraph matched with class will be del
41. is command evaluates UnCAL queries on a specified input graph and pro duces an output graph with trace information It can also produce insertion unit a unit of insertion on the target that corresponds to an inserted edge on the source To produce the insertion unit we have to specify insertion endpoints as two hub nodes on the target The target can be produced by the following command line gt fwdI_uncal db db dot q trans uncal png result png dot result dot that loads the input graph specified by DOT file src dot and binds to variable db interprets UnCAL source trans uncal and saves the result graph to the DOT file result dot as well as a PNG image file in result png Secondly decide insertion endpoints ex Hub 2 amp 9 and Hub 3 amp 9 by viewing these result files 71 72 CHAPTER 13 FWD INTERPRETER WITH INSERTION FWDI_UNCAL Multiple insertion units may be generated depending on the UnCAL ex pression and the input as well as the selected endpoints So the user should tentatively select the first Oth one by the following command line gt fwdI_uncal db db dot q trans uncal png result png dot result dot src Hub 2 9 dst Hub 3 amp 9 iu result iu in 0 id iu dot If the insertion units are generated successfully the number of total units are printed For example the message Total number of insertion units 3 indicates that three different units can be generated Note that inserti
42. known clas sifiers which maps a node number to the name of feature associated with the node is printed BNF for the output syntax is as follows Result VMapt entry entry 3 entry node gt classifier classifier datatype string klasse kname string node Node ID in the UnCAL graph data model For example the output Bid 2 gt datatype Boolean Bid 32 gt klasse kname Attribute denotes that the node No 2 is detected to have a primitive data type Boolean and node No 32 belongs to a class named Attribute ov file op package Validates the output graph using KM3 schema package package defined in file Output format is identical to that of ov and op option bulk Bulk semantics is used for the interpretation of UnCAL structural recur sion rec Recursive semantics is used without this option t Prints elapsed user CPU time broken down to e input validation if iv and ip options are specified e desugaring e execution of UnCAL expression e output validation if ov and op options are specified 6 2 OPTIONS 53 oa Optimizes evaluation of and equivalent operation in evaluation of rec when recursive semantics default is used usually evaluates both operands and connects matching I O nodes However if an I O node does not match the second operand is left unconnected and made un reachable This option suppresses the evaluation of the second operand to s
43. kyo BiG office at NII of Tokyo 1 3 BIDIRECTIONAL TRANSFORMATION DEVELOPMENT 23 and save it to orders_c_mod dot Alternatively we may use our tool Bdotty a small extension of DOTTY editor for this editing The tool should be installed easily if you already have DOTTY installed Please refer to for installation instruc tions Here we assume you have Bdotty command installed With this tool you can for example 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 Figure 1 5 DOTTY screen shot while editing the result of a forward evaluation Performing Backward Updating Now we can propagate the changes on the target graph the order model to the source graph the customer model with the following command gt bwd_uncal db customers_c uncal xg orders_c xg ei orders_c ei dot orders_c_mod dot png customers_c_mod png ucal customers_c_mod uncal udot customers_c_mod dot pa cm This will update the customer model and save the updated result in different formats customers c mod png customers c mod uncal customers c mod dot Note that the current version of the system is 24 CHAPTER 1 A TUTORIAL FOR THE GROUNDTRAM SYSTEM a bit slow in this backward transformation it may take a few minutes for this
44. ls on edges and the labels on nodes serve as a unique identifier and have no particular meaning Figure gives a small example of a directed cyclic graph with six nodes and seven edges Nine data constructors are provided to build arbitrary graphs Bunemanl e 3 constructs a graph with a single node without edges e label expr label expr X constructs a graph with the new root node having n outgoing edges Each edge is labeled label and points to the root node of the graph A label can either be one of the following type of values Normal edge label e g abc String value e g world 40 CHAPTER 3 UNCAL Figure 3 1 A Simple Graph Integer value e g 42 Floating point value e g 3 14 Data valued edges i e edges labeled with string integer or floating point values must point to a node with no further outgoing edges For these edges destination expr can be omitted world 42 is equivalent to world 42 expr U unifies two graphs by creating a new root and connect it to the roots of expr and exprg using e edges e edge is used to represent a shortcut of two nodes and works like e transition in automaton For instance a 100 U b 200 is defined to be the graph e a 100 e b 200 which is equivalent to a 100 b 200 amp x expr adds an input marker amp x to the root of expr A node marked with an input marker i
45. lvar expri Cezpra structural recursion Structural recursion has two equivalent semantics under the graph bisimula tion bulk semantics and recursive semantics The former is the prominent fea ture of structural recursion whereas the latter is the usual recursive semantics with memoization Informally the bulk semantics for the expression rec L G expri is that the function L G expr backslash should be read as A of the lambda calculus is applied independently on all edges of graph expres then the results are joined together with e edges as in the oper ation At each edge the label of the edge is bound to the label variable L and the graph rooted from the destination node of the edge is bound to the variable G For instance amp z rec L G if L a then amp z b amp z else if L c then amp z c G else amp z L amp z db this recursion replaces each edge labeled a by a graph amp z b amp z edge labeled c by c G where G is the destination node of the original edge and other edges labeled L are replaced by amp z L amp z Those graph fragments are glued together by the amp z marker In effect we obtain a graph whose a edges except the ones under c edges are replaced by b edges 42 CHAPTER 3 UNCAL 3 3 2 Input and Output Graphs of Transformations The input graph of a transformation is given to an UnCAL program as the gl
46. mp orderi date String 16 07 2008 no Int 1001 order_of Customer amp customer1 amp order2 date String 16 10 2008 no Int 1002 order_of Customer amp customer1 amp order3 date String 16 12 2008 no Int 1003 order_of Customer amp customer2 1 3 BIDIRECTIONAL TRANSFORMATION DEVELOPMENT 13 This is a rooted graph starting from the node amp src which points to two customers This UnCAL representation of a graph can be mapped to a graph in the DOT format by the following command gt uncalcmd q customers_c uncal dot customers_c dot This will produce a dot file named customers_c dot which can be viewed using the standard graphviz system For example we can produce a graph in the PNG format by the following command gt dot customers_c dot T png o customers_c png This will produce exactly the same graph as in Figure Given a graph schema and a graph we can validate whether the graph sat isfies the schema using the command unqlplus For instance we may validate whether the graph customers c uncal satisfies the schema Customers km3 by the following command gt unglplus db customers c uncal iv Customer km3 ip Customer q c20 c unql The last line specifies the transformation over the customers graph which will be developed later and is not important at this stage One may create the following simple identity tra
47. multiplicity reference number number with lower and upper bound number 1 with lower bound X IS Figure 4 1 KM3 Syntax and a reference type which is a PrimitiveDataType The PrimitiveDataType class has neither an attribute nor a reference besides the inherited attribute name 4 2 Validation We validate a graph by matching each contained edge with a name of a class or a feature in a given schema A validation of a graph proceeds as follows 1 All class inheritances are eliminated from a given schema by expanding features of classes with their super classes The elimination is recursively done since a super class may inherit another super class 2 We associate a vertex following from the root of the graph with a class whose name is the same as the label of the edge between the vertex and the root 3 We match a set of labels on edges from the vertex with a set of names of features of the class Every destination vertex of the edge should have edges which are labelled by the name of a class or a data type of the feature and the number of which is specified by a multiplicity in the KM3 schema such as in Figure A If the label of the edge is the name of the class the destination vertex of the edge is associated with the class and is checked the feature again If the label of the edge is the name of the data type the destination vertex of the edge should have an ed
48. nd m The meanings are identical to those of unqlplus See section EZ 55 56 CHAPTER 7 UNQL TO UNCAL COMPILER DESUGAR Chapter 8 UnCAL Interpreter uncalcmd This chapter describes UnCAL interpreter uncalcmd which interprets UnCAL source files for input graphs and produces output graphs in various formats 8 1 Overview of the Interpreter This command evaluates an UnCAL query on specified input graph and pro duces an output graph The command line gt uncalcmd db db uncal q trans uncal png result png loads input graph specified by file src uncal and binds to variable db inter prets UnCAL source trans uncal and saves the result graph to result png The option q is mandatory It can also be used to perform conversion between DOT and UnCAL formats as follows UnCAL to DOT gt uncalcmd q a uncal dot a dot converts UnCAL file a uncal to DOT file a dot DOT to UnCAL gt uncalcmd dbd a dot q identity uncal cal a uncal converts DOT file a dot to UnCAL file a uncal where identity uncal is a text file that only contains db that represents identity transformation If you want to generate a PNG from UnCAL file or DOT file do the following 57 58 CHAPTER 8 UNCAL INTERPRETER UNCALCMD UnCAL to PNG gt uncalcmd q a uncal png a png DOT to PNG gt uncalcmd dbd a dot q identity uncal png a uncal where identity uncal is a text file described above or you can directly use dot command by
49. nd Tram system to apply the transformation on the customer graph customers_c uncal that meets the schema Customer km3 to generate an order graph say orders_c uncal that should meet the schema Order km3 by the command unglplus gt unqlplus db customers_c uncal q c2o_c ungl cal orders_c uncal iv Customer km3 ip Customer ov Order km3 op Order t pa pu This will produce an order graph in the file orders_c uncal giving a bunch of messages showing the intermediate results in the transformation validating the input graph parsing the transformation query de sugaring the transformation to the internal core graph algebra in UnCAL performing transformation and validating the output begin Input validation message Input validation took 0 000345 CPU seconds Validation succeeded VMap Bid 0 gt klasse kname Customer Bid 3 gt datatype Int Bid 6 gt datatype String Bid 7 gt klasse kname Customer 1 3 BIDIRECTIONAL TRANSFORMATION DEVELOPMENT 15 Bid 10 gt datatype Int Bid 13 gt datatype String Bid 14 gt klasse kname Customer Bid 17 gt datatype Int Bid 20 gt datatype String Bid 23 gt datatype String Bid 26 gt datatype String Bid 29 gt datatype String Bid 32 gt datatype String Bid 35 gt datatype String Bid 38 gt dataty
50. nemanl 202000 and our extension UnQL see Chapter Input and output graphs for an UnQL program are written in the UnCAL format Moreover UnCAL can also describe graph transformations not just graphs themselves So we have two graph transformation languages UnQL and UnCAL in the GRoundTram system Compared to UnQL which is a more high level and user friendly language UnCAL is rather low level and machine friendly indeed in the GRoundTram system all UnQL programs are first compiled into UnCAL and then run Although in most cases UnQL should be sufficient for writing graph transformations you can also write UnCAL pro grams directly Besides since the bidirectional transformation semantics of the GRoundTram system is defined in terms of UnCAL it might be helpful to know the overview of UnCAL for understanding the bidirectional behavior We first show the full grammar of UnCAL in Section ET and then we give brief overview of each feature For those who are interested only in how to write input output graph data by UnCAL Section is the important part You may skip other sections concerning graph transformations in Section BA Note that this manual is not intended to give a rigorous description of the UnCAL language the readers who are interested in the formal definition of the semantics might want to consult the technical papers Buneman et al 2000 Hidaka ef all 2008 200940 3 1 Syntax The hole UnCAL program co
51. nsformation in the file c2o_c unql select db Similarly we can specify the schema of the orders graphs in the file Order km3 as follows package Order datatype String datatype Int class Order reference no Int reference date String reference customer_name String reference addr Address class Address reference type String reference code String reference info String 14 CHAPTER 1 A TUTORIAL FOR THE GROUNDTRAM SYSTEM 1 3 2 Constructing Forward Transformation from Cus tomer Model to Order Model After formalizing the two graph schemas we step to develop transformation from the customer graph to the order graph Suppose that this transformation is to generate from the customers graph a graph that represents those information of those orders that have type of shipping such that its root points to all the orders and each order contains order information of the date the order number the customer name and the address to which the goods should be delivered We can code this in UnQL our graph query transformation language as follows say in the file c20_c ungl select Order date date no no customer_name name addr Address a where Customer order Order o in db order_of Customer c date date no no in o add Address a name name in c code code info info type String t in a t shipping Now we can use the GRou
52. nsists of one graph construction expression defined as in the following BNF Compared to the original definition in 2000 the one implemented in the GRoundTram system adds two constructs let and 11 for ease of programming 37 38 CHAPTER 3 UNCAL expr 4 one node graph label expr label expr new node expr U expra union marker expr label the root node with input marker marker graph with output marker empty graph expr expra disjoint union expr expra append cycle expr graph with cycles expr EXPrn same as expr expry literal same as literal guar variable reference doc char loading another file if cond then expr else ezpre conditional rec lvar expr expra structural recursion let guar expr in expr variable binding llet expr in expra label variable binding Operator precedence and associativity is Operator Associativity high Q left if then else U right left right low left Variables start with the sign and markers start with the amp sign The label variables var and graph variables gvar are not lexically distinguished letter n o az AZz 09 lvar letter gvar n letter marker amp letter Boolean conditions are used as the branching condition for if expressions cond
53. ntext of UnQL UnCAL graph models where bisimilar graphs are treated as the same There are two bisimilar graphs one has only one child at the root node and another has two For a similar reason we cannot deal with oppositeDf relationships ATLAS group LU06 between two classes in UnCAL graphs We will not explain the details of KM3 Instead we explain KM3 informally with an example A KM3 schema is a set of packages which consists of classes data types and enumerations Figure shows an example of a KM3 schema for a simplified UML Class specification The schema consists of four classes Association Class Attribute and PrimitiveDataType A class has some features either references or attributes Every feature has a type either class or data type Since all of them inherit from their super class NamedElt they have an attribute name which is of type String The Association class has two references src and dest which are of type Class The Class class has an attribute is persistent which is Boolean and an arbitrary number of references attrs which are of type Attribute The Attribute class has an attribute is primary which is Boolean 43 44 package classifier feature multiplicity CHAPTER 4 KM3 package name 4 classifier package abstract class name extends name name 4 feature class datatype name primitive datatype attribute name multiplicity name attribute reference name
54. number in the update source DB specified by png or udot DB with n See also the same option of fwd_uncal described in chapter t Prints elapsed user CPU time for the backward execution of the UnCAL expression Chapter 11 UnCAL Backward Interpreter with Insertion of Graph bwdIg uncal 11 1 Overview of the UnCAL Backward Inter preter for Insertion of Graph This command performs the reflection of insertion of a graph on the target back to the source graph It is implemented in a completely different manner than command bwdI_uncal in chapter I and provides a more intuitive interface This command is used in the following steps 1 Forward execution gt bwdIg_uncal idot db dot q q uncal odot output dot opng result png loads input graph specified by file db dot and binds to variable db in terprets UnCAL source q uncal and save the output target graph in file output dot It optionally saves the PNG file of the output in result png if it is specified Options idot q and odot are mandatory 2 User determines the insertion point in terms of the ID of the node on the target graph by examining output dot or result png Let s assume here that the node number 1 is selected 3 User determines the graph to be inserted and prepare it as a dot file Let s assume here that it is saved in tidot dot 4 Reflection of insertion to the input graph gt bwdIg uncal idot db dot q q uncal odot outpu
55. obal variable db which is specified by the db or the dbd option of the command see Chapter E Additionally by using the doc filename expression a graph is read from the UnCAL file filename The name of the file must be supplied by a string literal e g my database uncal Dynamically computed string values cannot be used there The output graph of the transformation is the result obtained by evaluating the whole expression Chapter 4 KM3 The GRoundTram system validates input and output graphs against given schemata of them We employ the Kernel MetaMetaModel KM3 ATLAS group to describe schemata is an architecture neutral language to write metamodels which was developed at INRIA and is supported under the Eclipse platform KM3 is structurally close to EMOF 2 0 and Ecore but much simpler We refer to a metamodel written in KM3 notation as KM3 schema 4 1 Syntax A KM3 schema has a structure similar to an XML schema based on regular tree grammars such as W3C XML schema XML Schema WG in the sense that a schema prescribes which kind of set of nodes must be referred to by node by regular expression Figure T gives the definition of the core of The difference from the original definition ATLAS group 2006 is that the enumeration class is not supported in our system Note that validation with regard to ordered references and multiplicities of features does not make sense in the co
56. on units are not always generated It depends on the input graph query and insertion endpoints selected The above command line saves the first specified by in 0 insertion unit to file result iu For your information a graph in which the generated insertion unit and the target graph are combined are saved to DOT file iu dot In that file insertion endpoints are displayed in red while the subgraph in the insertion unit are displayed in purple These files should be passed to bwdI_uncal when a backward evaluation with insertion is necessary Options db q png dot are mandatory The image of the result graph stored in result png is just for preview and not required for backward evaluation 13 2 Options The following additional command line options are recognized by fwdI_uncal vv Prints debugging information pa Prints UnCAL input expression help Displays list of options Chapter 14 UnCAL Backward Interpreter with Insertion bwdI uncal This chapter describes the backward transformation part of the bidirectional UnCAL interpreter bwdI_uncal which interprets UnCAL source files for possi ble insertions on the target and produces input graphs in which the insertions are reflected Note that this reflection does not always succeed This command is intended to be used with fwdI_uncal described in chapter 14 1 Overview of the Backward Interpreter This command evaluates UnCAL queries on a specified output g
57. oo O XOL JO Tal 888 0014 LLL 007 8 0 01 JO TIN 1 2210 019 TOOT 8007 01 91 4 1001 SOO7 LO 91 Zum Suing Sumy Sunn Suing Sung Suns Suus Surg oy apo 48191409018 apo ed 4471814 exu eur reus Suny s Sso1ppy Suus sso1ppy 1 1 Sung Suns Suus ppg ppe 124101515 Jourojsn Part II Language References Chapter 2 UnQL UnQL is a high level SQL like programming language for describing graph transformations UnQL extends the UnQL graph querying language Bune Iman ef al 2000 with three simple graph editing constructs replace delete and extend 2 1 Syntax UnQL is a small extension of UnQL to support convenient specification of graph transformations model transformations We extend UnQL with three editing constructs for transforming graphs An UnQL expression takes a graph as input and results in a graph The following BNF defines the syntax of UnQL expression expr select template where bc ben selection replace rpp gt gvar by template in templates where bc replacement delete rpp gt gvar in template where bc ben deletion extend gt gvar with template in template where bc bc extension The following BNF defines a graph 31 32 template
58. otty and select print node in the bdotty context menu it prints the id to the console so that you can copy and paste it 3 Enumerate insertion template and choose a template gt bwdI enum uncal idot db dot q q uncal odot output dot opng result png ipt Hub 2 amp 9 uidot udb dot k 0 uodot uoutput dot executes the query q uncal in insertion mode and reflects the insertion of the Oth template at the target graph output dot rooted at node id Hub 2 8 9 and saves the new input graph to udb dot as well as the new target graph to uoutput dot In this step options ipt k uidot and uodot are mandatory The other options and content of the files should be exactly identical to those specified in the first step The target and input graph may include unspecified labels indicated by negative numbers In that case the restriction on them is printed in the form like Restriction neqL c a 1_1003 c 1_1005 a which means that the edge numbered 1003 and 1005 should not be equal to the values c and a respectively If the user is dissatisfied with the template presented by the implementa tion one can change the value specified by option k to see other candi dates As the value increases the size of the inserted graphs may grow Note that this step does not always succeed For example if the node on the source that corresponds to the node on the target that is specified by ipt option does not exist
59. pe String Bid 40 gt klasse kname Order Bid 42 gt klasse kname Address Bid 43 gt klasse kname Address Bid 46 gt datatype String Bid 49 gt datatype String Bid 51 gt klasse kname Order Bid 53 gt klasse kname Order Bid 55 gt klasse kname Address Bid 58 gt datatype String Bid 61 gt datatype String Bid 64 gt datatype String end Input validation message begin Submitted Query select Order date date no no customer name name addr Address a where Customer order Order 0 in db iorder of Customer c date date no no in o iadd Address a name name in c code code info info type String t in a t shipping end Submitted Query Desugaring took 0 000080 CPU seconds begin Executed UnCAL expr rec L fv6 if L Customer then rec L fv7 if L order then rec L 0 if L Order then rec L fv5 if L order_of then rec L c if L Customer then rec L date if L date then rec L no if L no then rec L fv4 if L add then rec L a if L Address then rec L name if L name t
60. ported by the Graphviz package It can optionally validate input and output graphs when a KM3 schema is specified The command line gt unqlplus db src uncal q trans ungl png result png loads an input graph specified by file src uncal and binds to variable db in terprets UnQL source trans ungl and saves the result graph to result png Option db is mandatory Multiple input may be specified using var options as described in the next section If you just want to verify a graph q option is not necessary just specify iv and ip options like gt unglplus db src uncal iv Class km3 ip Class 6 2 Options The following additional command line options are recognized by unglplus v Prints version information 51 52 CHAPTER 6 UNQL INTERPRETER UNQLPLUS oi file Saves the image of result graph to file Format of the image is specified by the extension of the filename Supported formats are the same as those supported by T option of dot command in Graphviz png file Saves PNG image of result graph to file dot file Saves result graph in DOT format to file cal file Saves result graph in UnCAL format to file var v file Binds a graph in UnCAL format specified by file to variable v Multiple variables can be bound by repeatedly using this option iv file ip package Validates the input graph specified by db option using KM3 schema pack age package defined in file If validation succeeds a map of
61. ptions The following additional command line options are recognized by fi2si The meanings are identical to those of uncalcmd See section BZ 83 84 CHAPTER 17 FLAT ID TO STRUCTURED ID CONVERSION FI28I Bibliography ATLAS group KM3 Kernel MetaMetaModel manual brg gnt an3 kn3 doc KernelNetalletaNodel v00 06 pdf 2006 P Buneman M F Fernandez and D Suciu UnQL a query language and algebra for semistructured data based on structural recursion VLDB Journal Very Large Data Bases 9 1 76 110 2000 S Hidaka Z Hu H Kato and K Nakano An algebraic approach to bidirec tional model transformations Technical Report GRACE TR08 02 GRACE Center National Institute of Informatics Sept 2008 S Hidaka Z Hu K Inaba H Kato K Matsuda and K Nakano Bidirection alizing structural recursion on graphs Technical Report GRACE TR09 03 GRACE Center National Institute of Informatics Aug 2009a S Hidaka Z Hu H Kato and K Nakano A compositional approach to bidirectional model transformation In ICSE Companion pages 235 238 IEEE 2009b R Paige and R Tarjan Three partition refinement algorithms SIAM Journal of Computing 16 6 973 988 1987 doi http dx doi org 10 1137 0216062 O Pastor and J C Molina Model Driven Architecture in Practice A Software Production Environment Based on Conceptual Modeling Springer Verlag New York Inc Secaucus NJ USA 2007 T M Project MONA version
62. raph along with trace information and an insertion unit described in chapter and produces an input graph with insertion on the output graph being reflected The command line gt bwdI_uncal db src dot q trans uncal png srcprime png dot result dot iu result iu loads the input graph specified by file src dot and binds to variable db inter prets UnCAL source trans uncal backwards using output graph and the in sertion unit respectively specified by result dot and result iu It also saves the image of the updated source graph in srcprime png for preview Options db q png dot and iu are mandatory 14 2 Options The following additional command line options are recognized by bwdI_uncal v udot pa cm The meanings are identical to those of bwd_uncal See section IZ 73 74CHAPTER 14 BWD INTERPRETER WITH INSERTION BWDI_UNCAL Chapter 15 UnQL UnCAL Typechecker chkuncal This chapter describes the static typechecker chkuncal of the UnQL UnCAL transformations To use this typechecker you first need to install the MONA tool Project and set up the PATH environment variable so that the mona command can be found 15 1 Overview of the Typechecker This command requires three files as arguments Namely a KM3 file e g in km3 describing the type of input graphs an UnQL UnCAL transformation e g transform ungl or transform uncal of which the type correctness is tested and a file e g out km3
63. rn 00 a ey ee een 12 The Customer2Order Problem R Bidirectional Iranstormation Development D Orde onstructing Forward lranstormation trom Custome Model to Order Model 9 pe ecking Forward ranstormation 2 4 esting backward lranstormation 4 More Examples e soa a 24 46 2 A m anguage Reference 2 UnQL 2 2 Graph Querying 4 2 221 The select where Construct Y D d bad Oxo ee 2 9 replace where Construct 2 3 2 delete where Lii The extend where TonstrucH B UNnCAL D cuu ccc D rap ONSLFUCLION 225555444444 0o XX ee D rap TANSIOTMATION ooo A a ee Hana ESTI Structural 5 3 nput and Outpu raphs ot lranstormationg 4 3 1 2 CONTENTS Command References 47 p__GRoundTram Main Command gtram 49 bt Overview the Main Command 49 49 6 UnQL Interpreter unglplus 51 b Overview ol the Interpreten 51 eae Ss Sh oh nad 51 UnQL to UnCAL Compiler desugar 55 tree Gadd dee aes 55 ee e eee 55 8 UnCAL Interpreter uncalcmd 57 the 57 58 9 UnQL UnCAL Forward Interpreter fwd_uncal 61 p Over
64. s sometimes called an input node Intuitively input nodes can be regarded as root nodes of the graph fragment For singly rooted graphs we implicitly use the default marker amp to indicate its single root amp y constructs a graph with a single node which is marked with an output marker amp y Such a node is called an output node An output node can be regarded as a context hole of graphs where an input node with the same marker is plugged later constructs an empty graph which has neither a node nor an edge expr exprg constructs the disjoint union of two graphs Two graphs are simply juxtaposed and no connecting edges like e edges of the U oper ator are added A syntactic sugar expr expr stands for expr expr exprg appends two graphs The resulting graph is obtained by plugging the input nodes of into their corresponding output nodes in expr 3 3 GRAPH TRANSFORMATION 41 e cycle expr connects the input nodes with the output nodes of expr to form cycles As an instance the graph in Figure can be expressed in the following UnCAL expression amp root cycle amp root a a amp 5 b a amp 5 amp 5 d c amp 4 3 3 Graph Transformation 3 3 1 Structural Recursion In addition to the graph constructors structural recursion is essential for writing graph transformations expr rec C
65. t dot ipt 1 tidot tidot dot uidot udb dot uodot uoutput dot 67 68 CHAPTER 11 BWD INTERP WITH INSERTION BWDIG_UNCAL executes the query q uncal in insertion mode and reflects the insertion of the graph tidot dot at the target graph output dot rooted at node id 1 and saves the new input graph to udb dot as well as a new target graph to uoutput dot In this step options ipt tidot uidot and uodot are mandatory The other options and content of the files should be exactly identical to those specified in the first step Note that this step does not always succeed For example if the result graph of insertion on the target side i e to be saved in uoutput dot in the above command line is not within the range of the transformation specified by q uncal then the insertion is inherently impossible because no matter what graph you give as an input the new target graph can never be generated by the transformation In case of this failure you either get the error message no insertion ex ists on the source side or the command does not return i e does not terminate Also note that if you insert a large graph then this step may take a long time 11 2 Options The following additional command line options are recognized by bwdIg_uncal pa Prints the UnCAL expression given by q option Chapter 12 UnCAL Backward Interpreter with Insertion of Graph bwdI enum uncal 12 1 Overview of the
66. tematic development of bidirectional model transformation Figure C depicts an architecture the basic idea of the GRoundTram system A model transformation is described in UnQL which is functional rather than rule based as in many existing tools and compositional with high modularity for reuse and maintenance The model transformation is then desugared to a core graph algebra which consists of a set of constructors for building graphs and a powerful structural recursion for manipulating graphs This graph algebra can have clear bidirectional semantics and be efficiently evaluated in a bidirectional manner The note is intended to demonstrate through a concrete example how to use the GRoundTram system to build a bidirectional transformation between two models graphs The readers who are interested in the technical details are referred to the technical papers Hidaka ef all 2008 ZU0YalD Note that all the sources discussed in this tutorial are available in the examples directory in the distribution 1 Pronounced gr und tram 8 CHAPTER 1 A TUTORIAL FOR THE GROUNDTRAM SYSTEM Model Transformation in UnQL Compositional and Functional Desugaring gt Graph Algebras Graph Construction and Structural Recursion Bidirectional Evaluator Source q Bidirectionalization y Target Model Model Fusion Optimization Figure 1 1 A Compositional Framework for Bidirectional
67. unql idot customers_c dot odot orders_c1 dot The updated source and view will be saved in udb dot and uout dot respec tively as a default We can specify the names of these files for saving these updated results by gt bx quick b uq c20_c unql idot customers c dot odot orders 1 4 uidot xx dot uodot yy dot It is a bit tricky to deal with insertions We adopt a simple way First we specify where a new tree is to be inserted For instance we may want to insert a subtree finfo below the node pointed by the edge 59 Address 50 To do so we can modify the above edge to 59 info 50 and save the modified view to say orders c2 dot Now we can reflect this change to the source by gt bx quick b uq c20_c unql idot customers c dot odot orders c2 dot tdot customer c template dot where customer c template dot denotes an instance of a customer s data fol lowing the schema Customer which should be prepared by the user 16 3 OPTIONS 81 16 3 Options The following additional command line options are recognized by bx_quick vV Print version info f Perform Forward transformation default b Perform backward transformation ulp Do one pass optimization of UnQL experimental to fuse modifications idot textitfile Specify the source db file in DOT uq file Evaluate the UnQL query specified by file idot file Specify the target DOT file for editing and backward inp
68. ut idot file Specify a template input dot file which is used only for reflection of in sertion uidot file Specify the updated DOT db file uodot file Specify the updated DOT view file ikm3 file Specify the source validation schema in KM3 okm3 file Specify the view validation schema in KM3 ip Specify the input validation package the root node type of the source op Specify the output validation package the root node type of the view 82 CHAPTER 16 A QUICK BIDIR INTERPRETER BX_QUICK Chapter 17 Flat ID to Structured ID Conversion fi2si This chapter describes the ID expansion command for traceability 12sil which expands the node ID in the contracted view after stage 2 in fwd_uncal This command is intended to be used with bwdI_enum_uncal to compute can didates for the insertion point 17 1 Overview of the Flat ID Expander This command takes the flat ID of a node in the result of fwd_uncal command invoked with sb cl zn and fi options and the evaluation information file that is also produced by fwd_uncal and prints corresponding structured IDs one per line The command line gt fi2si ei bd ei ipt 5 loads mapping of stage 2 that stores node ID mapping before and after stage 2 from file bd ei and returns the list of nodes that corresponds to node 5 in the structured form at the end of stage 1 The multiplicity of the result is due to the contraction of s edges in stage 1 17 2 O
69. view ot the Forward Interpreten 61 AAA 62 O UnCAL Backward Interpreter bwd uncal 65 65 65 67 67 68 Bwd Interpreter wi numeration Based Insertion of Graphl 69 l Overview the U E terpret t ane Gag eee 69 DETULIT 70 3 Fwd Interpreter with Insertion fwdl_uncal 71 Overview of the Forward Interpreter 71 DAE Geran 72 4 Bwd Interpreter with Insertion bwdI_uncal 73 IO B erprete 73 73 5 UnQL UnCAL Typechecker chkuncal 75 75 re 76 77 CONTENTS 16 A Quick Bidir Interpreter bx quick 16 1 Forward Transformation 17 Flat ID to Structured ID Conversion fi2si l Overview ot the Flat ID Expander CONTENTS Part I Overview Chapter 1 A Tutorial for the GRoundTram System This tutorial will be taking you through a tour of the use of the GRoundTram 4 Graph Roundtrip Transformation for Models system to build a bidirectional transformation between two models graphs 1 1 Introduction Bidirectional model transformation plays an important role in maintaining con sistency between two models and has many potential applications in software development including model synchronization round trip engineering software evolution multiple view software development and reverse engineering The GRoundTram system was developed by the BiG team of the National Institute of Informatics for supporting sys

GRoundTram Version 0.9.3a User Manual

Contents

Download Pdf Manuals

Related Search

Related Contents