Aggregations in Henshin

The language concepts of Henshin are based on graph transformations. As such, aggregations have not been in the scope of Henshin so far. Aggregations are well known from relational database systems and are a powerful tool for counting entities, calculating minima / maxima or average values etc.

How do aggregations and graph transformations fit together? Well, in Henshin we know the concept of nested multi-rules. In graph transformation terminology this is often referred to as amalgamation. In essence, a transformation rule is extended with parts that are applied with a for-all semantics. These for-all parts are referred to as the multi-rule, whereas the core part is referred to as the kernel rule. In the graphical editor of Henshin, the multi-rule parts are indicated using *-actions.

Now, the trick for supporting amalgamations in Henshin is to allow to use the values of parameters of multi-rules in the kernel rule. What happens is that for one match of the kernel rule, the multi-rule is matched with for-all semantics, and that its parameter values are exposed to the kernel rule as a collection. This enables the use of aggregations functions in the kernel rule, which combine the values of parameters of the multi-rules.

Consider the two example rules below. Both match one :Family object (kernel rule) and all :Person objects in that family (multi-rule). Now, the set of persons can be used as basis for aggregations. In our two example rules, we use as aggregation functions COUNT and AVG to resp. count the number of family members and calculate the average age of the family members.

Note that the expressions Aggregations.COUNT(x) and Aggregations.AVG(a) are not some special syntax for aggregations. They are just calls to ordinary Java methods. The special thing about these methods is that they take a collection of values as parameters (not single values). The Henshin interpreter just calls the (possibly user-defined) functions to calculate the aggregated values. For the interpreter to know which class to use, it must be defined as part of the Java imports of the rule, as shown in the screenshot below. Additionally, you need to ensure that this class is in the Java classpath when executing the Henshin transformation.

The aggregation support is currently available in the development branch of Henshin. You can find the above rules with accompanying Java code in the examples plugins.

Henshin 1.2

We are happy to announce the release of Henshin 1.2! Henshin is a model / graph transformation tool for EMF models. The new release comes with new features for the graphical editor and a better integration with Apache Giraph.

The graphical editor now supports attribute conditions, which are used to restrict the applicability of transformation rules. In addition, the editor now supports live validation which gives you an immediate warning if you are trying to add an object to two containers or you are using an invalid JavaScript expression etc.

For me the most important new feature of the new version is the improved code generation facilities for Giraph. The new wizard will generate a full-fledged Java-project with all needed libraries, set up a Maven build and even automatically install a local Hadoop test environment if you like. This means that you can model a graph transformation in Henshin and fully automatically generate executable Giraph code that you can directly run in Eclipse. The video below shows you a demo of this new code generator.

Henshin 1.2 is available at our release update site.

Building the Collatz Graph in Henshin

The other day I saw an online video about a number-theoretical problem called the Collatz conjecture. The video included some visualizations of the problem which were based on force-directed graph drawing. It was immediately clear to me that such visualizations could be also easily done in Henshin. So I built a minimalistic EMF model and sketched two simple rules:

The first one multiplies x by 2, the second one is the inverse of the 3x+1 rule. Technically, it is not exactly the inverse of the Collatz function, but the conjecture is still true if and only if these two rules can generate every natural number (if we ignore the upper bound in the first rule).

Finally I created an instance model for the initial state and set up a state space. In the following video you can see how to use Henshin's state space explorer to generate the Collatz graph. Have fun. 

Why Model Transformations != Graph Transformations

Model transformations are probably the most important application of (the formal theory of) graph transformations. This includes classical source-to-target model transformations, bidirectional transformations and synchronizations, as well as in-place rewriting, e.g., for refactoring. All these applications have in common that the underlying graphs to be transformed are actually EMF- or MOF-based structural data models.

These models have of course a graph structure, but when taking a closer look, they are actually more than just that. The higher expressive power of metamodeling languages like EMF or MOF in comparison to simple graphs has some severe implications when trying to apply formal (mathematical) methods known from the graph transformation research community.

Let's take a look at a concrete example of a Henshin transformation. The following rule is a variation of the Bank Accounts example:

This rule collects all accounts which do not belong to any client and adds them to a designated bank for "orphaned" accounts. The graph transformation semantics of this rule does exactly what is shown: it creates zero or more edges between a bank and a number of account objects. In contrast, the EMF-semantics actually has a twist which is not directly visible here: any of the orphaned accounts which before belonged to a different bank object are removed from their original bank. Thus, this rule can actually also delete edges.

This is because in EMF, adding an object to a container also means that it is removed from its old container. Implicit deletion of edges can also occur for edges with multiplicity 1. Another semantical difference to graph transformations exists for the handling of bidirectional references (eOpposite-references). In this case, EMF automatically maintains the opposite references in a consistent state which can have the effect that EMF removes or creates edges. It can actually get more complicated when you have a combination of containment and multiplicity constraints, and opposite edges.

These phenomena can be considered as side effects of rules -- they are actions performed by EMF even if they are not explicitly specified in the transformation rules. Henshin does not prevent these side effects (that is actually not possible), but it will print warning messages when such side effects occur during the execution.

From the EMF / MOF perspective, the described effects are intended and desirable. What is problematic though is to assume that model transformations per se have graph transformation semantics and (what is more dangerous) to apply formal verification methods from the graph transformation domain without taking into account these possible side effects of rules.

There are also other related, partly surprising, phenomena when dealing with EMF models. For example, copying an object does not necessarily yield an identical object, i.e., the expression:

EcoreUtil.equals(eObject, EcoreUtil.copy(eObject))

does not always return true. This is because the copy mechanism in EMF won't make any changes which would alter the original model (e.g. bend an opposite reference).

The lesson learned is that models are more than graphs, and model transformations are more complicated than graph transformations.

Henshin 1.0 (Update)

8 years after the first PoC and 4 years after its official launch, we are proud to announce the release of Henshin 1.0 -- a model transformation language and framework for EMF. Henshin 1.0 is ready for Eclipse Luna and Java 8 (including its new JavaScript engine Nashorn). The primary domain of Henshin is model-driven development and formal verification methods. With its new multi-threaded pattern matching engine and its code generator for Apache Giraph, big data is a new third main domain of Henshin.

The new version of Henshin comes with an extended transformation language with support for specifying Java imports and annotations, and a couple of new utility APIs. Besides the changes under the hood, the 1.0 release also comes with a number of visible new features, including a reworked interpreter wizard and new preferences for the diagram editor. As an eye candy, we also added a new color mode for the diagram editor which goes well together with Luna's Dark theme.

You can obtain Henshin 1.0 from the release update site or clone our Git repo to try it out!

Update from 30-07-2014

And of course we've build a critical bug into the release! Anyway, the fixed version is available at the release update site.

Parallel Graph Pattern Matching in Henshin (Update)

In my last post, I reported on an improvement of the graph pattern matching algorithm in Henshin that showed a major performance boost for rules where the nodes in the left-hand sides are connected only by <<require>> nodes and edges. As a concrete example, we used the transformation rule below to find couples of actors / actresses in the IMDB movie database which starred together in at least three movies.

Thanks to the tweak in the pattern matching engine we were able to apply this rule to much larger input graphs. Unfortunately, the synthetic test data that we used for our last benchmark does not have the same complexity as the real data from IMDB. In our test data, every person played in not more than 10 movies and every movie had a similarly low number of actors / actresses. In reality, the IMDB data contains movies with more than 1000 actors and obviously also persons that played in a large number of movies.

So I executed our find-couples example on the real IMDB data (thanks for the data import, Tassilo!). Not surprisingly, the results were much worse than for the synthetic data. The reason for this is that the real IMDB data is much more interconnected. So I started tweaking the pattern matcher of Henshin again. Eventually, I realized that I need something more to crack this nut.

SAP Coding Masters 2013

A possible way to improve the performance is to parallelize the graph pattern matching algorithm. In the current development version of Henshin, this is actually implemented! Here is how you can enable it:

int partitions = 10;
EGraph graph = new PartitionedEGraphImpl(model,partitions);
Engine engine = new EngineImpl();
engine.getOptines.put(Engine.OPTION_WORKER_THREADS,
   partitions);

// Execute transformation

engine.shutdown();

You need to use the new implementation of EGraph called PartitionedEGraphImpl. It basically splits up the graph to be transformed into N disjoint partitions. The second change you need to do is to set the number of worker threads in the transformation engine. In theory, this number can be different to the number of partitions, but the easiest setup is to just use the same amount of threads as there are partitions. The third point you need to ensure is that your rule uses *-stereotypes for nodes and edges (essentially it transforms all matches at once). Finally, you should shutdown the engine when your done to get rid of the worker threads.

For the example of finding couples in the IMDB database, this parallel graph pattern matching approach works actually quite well. Below you can see the performance gains achieved on an ordinary desktop computer.

With this new parallel graph pattern matcher in the interpreter, and the recently introduced Giraph code generator, Henshin really is becoming a big-data tool, which I find very exciting.

Update (07 February 2014)

I realized that the performance in absolute number is still quite bad. As I wrote in my earlier post, the optimized match finder uses path constraints to check the existence of the movies which connect the actors. The problem was though that the match finder still made an additional check whether the <<require>> elements exist, i.e., it performed a complete matching of the PAC (positive application condition). This is actually not necessary here because the path constraint is sufficient already.

To fix this problem, I added a static analysis which finds out once in the beginning whether path constraints are enough to check the PAC. This significantly reduces the run-times as you can see below. Using 12 worker threads, the processing of 2 million nodes takes 173 seconds. But to be honest, I have my doubts whether these engine optimizations will be helpful also in other cases.

Nodes	Couples	Time (ms)
499,995	79,470	6,582
1,004,463	244,627	27,239
1,505,143	585,689	87,721
2,000,900	1,017,752	173,142

Path Constraints in Henshin

In our recent paper on the Giraph code generator in Henshin, we conducted some benchmarks using a real-data example. For this we used the publicly available data sets from the IMDB movie database. We parsed the movie, actor and actress records into an EMF model as shown below. Note that I omitted the attributes here for simplicity.

The goal of our transformation on the IMDB data set was to find all pairs of persons (actors or actresses) which starred together in at least three movies. For every such pair we want to create an instance of the Couple class. We used the Henshin rule below to do this. First, note that all nodes / edges have *-actions and thus the rule is applied to all found matches at once. Second, we used <<require*>>-actions for the movies, and not <<preserve*>>. This is important because we want to ensure the existence of these movies, but be don't want to generate separate matches for every combination of movies. There is only one small subtlety in this rule: due to the symmetry of person nodes, we will actually create two couple nodes for every pair. But this could be easily fixed by enforcing an alphabetical order of the persons' names using an attribute condition.

To compare the performance of the Giraph-based engine, we also tried to execute this example with the normal Henshin interpreter. To our surprise, even for a small part of the IMDB data set, the Henshin interpreter was not able to compute a match. To study the problem in a more controlled setting, we defined a small transformation that generates a synthetic test data set of variable size. We then ran the interpreter again and got the following numbers.

Nodes	Couples	Time (ms)
1,700	200	1,625
3,400	400	3,753
5,100	600	7,828
6,800	800	14,386
8,500	1,000	23,301

This looks pretty bad. The input graphs are very small (< 10,000 nodes) and it already takes more than 20 seconds. The main problem is that the execution time grows non-linearly (should be O(n²)) with the size of the input graph. What is the reason for this? Well, the Henshin interpreter first fixes a match for the LHS (<<preserve>> and <<delete>> elements), and after that it tries to match the application conditions (<<require>> and <<forbid>> elements). In our example, this means that it first picks to arbitrary persons, and then checks whether they starred together in 3 movies. Thus. it is basically a brute-force approach that the interpreter runs here.

The pattern matching is implemented in Henshin as a constraint-solving problem. To fix the bad performance of the movies example (and similar problems), we added a new type of constraint to the pattern matching algorithm: path constraints. Path constraints are internally used to check whether there exists a path between two EObjects along a given list of EReferences. The neat thing about these paths is that they can also go via <<require>> nodes. In our example, this indeed works because the movies-reference has an opposite reference: persons. If we now fix one of the two persons, the path constraint via the references [movies, persons] allows the match finder to restrict the solution set for the second person to only those persons who played together with the first one in at least one movie. This drastically prunes the search space which gives us a much better performance.

Nodes	Couples	Time (ms)
1,700	200	133
3,400	400	89
5,100	600	35
6,800	800	36
8,500	1,000	49
...	...	...
170,000	20,000	1,419
850,000	100,000	6,183
1,700,000	200,000	9,836

This looks much better: now we can process 1.7 million nodes in less than 10 seconds. This should be also enough to run the example on the original IMDB data set. The example including the benchmark is part of the examples plug-in of the development version of Henshin.

Henshin + Giraph: Enforced Parallelism

I recently announced the availability of a Giraph code generator for Henshin, which allows you to execute graph transformations in a parallel and distributed manner. It is important to know that there is a fundamental difference in the execution semantics of graph transformations in this approach. Concretely, the application of rules is always maximum parallel, i.e., every rule is always applied to all found matches in parallel. The idea behind this is that we want to enforce the use of parallelism already at the modeling level and to make it hard for developers to use conventional sequential algorithms that cannot be parallelized automatically. For example, the rule AddTriangles below would be applied to all found triangles in parallel. Executing the iterated unit BuildSierpinski to a 3-node triangle therefore generates the full Sierpinski triangle of depth N.

Due to the change in the execution semantics of rules, other existing and also some new modeling concepts specifically tailored for parallel graph transformations become important. For example, vertices and edges with <<require>> and <<forbid>> stereotypes are particularly useful to avoid overlapping matches which could result in inconsistent parallel rule applications. We also introduced concepts that allow you to aggregate over attribute values of all found matches. I will discuss this in more detail in another post.

Henshin + Giraph = Big Data Graph Transformations

Henshin is a graph and model transformation tool for Eclipse that lets you define rules and workflows for transformation in a graphical editor. By default, these transformations are executed using an interpreter on an in-memory EMF model.

Apache Giraph is a distributed and parallel graph processing framework built for high scalability. Giraph is for instance used at Facebook to analyze the underlying graphs of social networks.

So how do Henshin and Giraph fit together? Easy: Henshin provides an expressive graph transformation language with an intuitive graphical syntax. Giraph provides an infrastructure for highly parallel and distributed graph processing. The sort of obvious way of combining the two is to use Henshin as modeling tool and Giraph as execution engine. And that is what we are currently working on.

We implemented a code generator that produces Java code for Giraph from Henshin models. This generated code contains pattern matching code and graph manipulations for rules, and the required coordination to execute transformation units (workflows). The code generation is still an experimental feature but we plan to stabilize it and ship it with the next release of Henshin. We have already a small test suite and conducted some promising benchmarks. More details later.

The Giraph code generator is available in the development version of Henshin (for Eclipse Kepler). You can get it from our nightly build update site or by getting the source code directly.

Parallel State Space Exploration in Henshin

Back from the summer break, I read an interesting article on combining OCL expressions with CTL formulas. Apart from the modeling approach itself, it was interesting to me that the authors used Henshin to generate their state spaces and also compared their modeling and the performance of Henshin's state space generator with GROOVE.

While the GROOVE tool does not really provide an API for its simulator and state space generator, it is fairly easy to do this programmatically in Henshin:

// Set-up:
StateSpace stateSpace = new StateSpaceImpl();
stateSpace.getRules().addAll(rules);
StateSpaceManager manager = 
   new ParallelStateSpaceManager(stateSpace, 4);
manager.createInitialState(new ModelImpl(resource));

// Exploration:
StateSpaceExplorationHelper helper = 
   new StateSpaceExplorationHelper(manager);
helper.doExploration(-1, monitor);

That's it. After you have generated the state space, you can either save it or use a validator to check invariants or to do model checking etc.

The authors of the OCL-meets-CTL paper mention that there is room for improving the performance of Henshin's state space generator, which I fully agree to. Nevertheless, I want to show here that we have put a lot of effort to make Henshin's state space generator as fast as possible. A key difference to GROOVE is that state space generation in Henshin can be parallelized. Let me show you some numbers.

The chart shows the time needed to generate the state space of the dining philosophers example for 10 philosophers. What you can see is that by using multi-threaded state space generation, we obtain a speed-up of factor 3. In absolute numbers, the generator explores around 2000 states per second. That is just half a millisecond to find all rule matches for a state graph, make a copy and transform it for every match, and look up states and update the state space. If you compare it with the performance of the Henshin interpreter itself (see e.g. here), these numbers are top notch. Note also that the speed can be greatly improved simply by increasing the cache sizes of the state space generator (which requires more main memory though).

That being said, there is still of course room for improvement. For example, the scale-up for a high number of processors and threads is not as good as we have hoped. The required locking of the state space seems to be the main bottleneck. The performance can be probably tweaked but it will of course never be as fast as model checkers that work on vector-based data (as opposed to graphs).

Henshin 0.9.10 on its way. We are working on the new version of Henshin which we hope to release in November 2013. It will target and require Eclipse Kepler. The most exciting new feature will be a new execution platform for Henshin transformations. More on this later.