Incremental model queries are a key solution to apply model-driven engineering to rapidly evolving models. This paper describes alternative solutions to the live competition of the Transformation Tool Contest 2018. The case study requires to query large models of social networks to derive the most influential and controversial contributions. We compare two batch solutions implemented in a general-purpose language (Xtend) and a model transformation language (ATL), to one incremental solution implemented by the Active Operations Framework.
understandability, and performance. As outcome of this evaluation, our team won two awards: the "Most Concise Solution Award" for the ATL solution, and the "Audience Award" for the AOF solution.
The remainder of this paper is structured as follows. The thee submitted solutions are presented in Section 2 for ATL, Section 3 for Xtend, and Section 4 for AOF. Then, all these solutions are evaluated and compared in Section 5, where we draw some conclusions. Our first solution is written as a pure ATL query and executed on the most recent ATL virtual machine (EMFTVM). Queries in ATL are OCL expressions, that can call helper OCL functions and libraries. Thus, this solution includes a complete encoding of the case study as declarative and functional OCL code.
The main objective of the solution is maximizing conciseness and readability. The whole program comprises only 13 lines (Q1) + 31 lines (Q2) = 44 lines. The execution in standard ATL is not incremental, but it has good batch performance since both queries are implemented by algorithms with linear complexity.
The full code for Q1 is presented in Listing 1. The recursive allComments helper gathers the set of comments for a given post, and a score for the post is computed by the given formula (line 11) considering the number of comments and likes to the post. The main query topPosts sorts the set of posts by score (and timestamp) and picks the top three posts.
The code for Q2 is shown in Listing 2. In particular, the allComponents helper implements a one-pass algorithm for the detection of all the connected components. The algorithm iterates on the likers: if the liker has not been visited then compute a new component by the allFriends function. The allFriends helper (whose implementation is not shown in the listing) is just a standard depth-first traversal, limited to the subgraph s. Finally a score is computed for each comment (line 5), and the top three comments are identified similarly to Q1 (lines 1-2). 9 10 helper context SN ! Comment def : a l l C o m p o n e n t s : Sequence ( Sequence ( SN ! User ) ) = 11 self . likedBy >iterate ( u ; 12 acc : T u p l eT y p e ( c o m p o n e n t s : Sequence ( Sequence ( SN ! User ) ) , visited : Sequence ( SN ! User ) ) = 13 Tuple { c o m p o n e n t s=Sequence {} , visited=Sequence {}} | 14 i f ( acc . visited >includes ( u ) ) 15 then acc 16 else l e t c o m p on e n t : T u p l eT y p e ( c o m po n e n t : Sequence ( SN ! User ) , r e m a in i n g : Sequence ( SN ! User ) ) = 17 t h i s M o d u l e . a l l F r i e n d s ( u , self . likedBy >e x c l ud i n g ( acc . visited ) ) . c o m p on e n t in 18 Tuple { c o m p o n e n t s = acc . c o m p o n e n t s . append ( c o m po n e n t ) , visited = 19 acc . visited >union ( c o m po n e n t ) } 20 endif ) . c o m p o n e n t s ;
The solution being completely declarative, some degree of implicit incrementality can be added by switching to an incremental execution engine, without requiring to modify the user code. Incremental engines for ATL exist [JT10, MTD17] and perform an on-demand activation of transformation rules. However they do not incrementally update the computation of OCL expressions. Hence, they would not have an impact on pure queries like the one we present. In Section 5 we show the performance of this ATL code on an experimental execution mode for ATL that leverages Active Operations for incrementality (see Section 4). 3
In parallel with the ATL solution, an implementation of both queries has been made in Xtend3, a modern Java dialect suited for rapid prototyping thanks to its flexibility and expressiveness. Results obtained with this solution have been used to validate results of both ATL and AOF solutions.
We have written a first batch implementation of Q1 and Q2 (i.e., without incrementality) in pure Xtend, using the Eclipse Modeling Framework (EMF) plugin to perform loading and navigation into models. In a second step, we optimize this solution using Java 8 Streams to parallelize some operations on collections. The Xtend code used for the implementation of Q1 (Listing 3) shows that this mechanism is used two times: (1) to process all posts in parallel, and (2) to compute the sum of all likes received by comments of a post in the computeScore method. For better performance, we have also implemented a specific Stream operation, called Greatest3, to avoid sorting the whole list of posts while only the top 3 posts can be considered.
The code of Q2 is similar to the implementation of Q1 except for the computeScore method. Indeed, the second query requires to find connected groups of users through the friend relationship. For this purpose, the computeScore method uses a connected components algorithm based on Tarjan algorithm [Tar72].
Listing 3: Q1 in Xtend with Java Streams 1 def private queryQ1 ( ) { 2 return s o c i a l N e t w o r k . posts . p a r a l l e l S t r e a m . collect ( C o l le c t o r . of ( [ 3 new G r e at e s t 3 ( 4 C o m p a r a t o r . c o m p a r i n g I n t [ 5 i f ( i t === null ) { Integer . M I N _V A L U E } else { c o m p u t e S c o r e } 6 ] . t h e n C o m p a r i n g ( C o m p a r a t o r . c o m pa r i n g [ t i m es t a m p ] ) 7 ) 8 ] , [ $0 . add ( $1 ) ] , [ $0 . merge ( $1 ) ] , [ asList ] ) ) . map [ id ] . join ( " | " ) 9 } 10 def private c o m p u t e S c o r e ( Post p ) { 11 val comments = p . e A l l C o n t e n t s . filter ( Comment ) . toList 12 return comments . size C O M M E N T _ S C O R E + comments . p a r a l l e l S t r e a m . mapToInt [ likedBy . size ] . sum L I K E _ S C O R E 13 } 4
Active operations [BBBJ10] are OCL-like operations such as collect, select, etc. equipped with incremental propagation algorithms. Each operation is able to perform an initial computation, and then to update its result when its source changes (and vice versa when possible). Furthermore, it is possible to build complex incremental expressions by composing active operations. They may thus be used to incrementally evaluate OCL expressions [BCD+14, Section 5] such as found in ATL-like model transformations. It is therefore possible to use active operations to write incremental queries and transformations.
The AOF implementation [JB15] of active operations is based on observation, and notably supports EMF models. It is implemented in Java, and can be used from Java or Xtend code. Each mutable value is wrapped in an observable box, which is either a collection, or a singleton value. Each active operation observes its source box, and updates its target box upon changes by applying its propagation algorithm.
3https://www.eclipse.org/xtend/
AOF provides enough basic active operations to implement the case study. However, building complex queries out of basic operations does not always guarantee scalability. We observed that creating specific operations sometimes helps [JB16]. Listing 4 shows how AOF can be used in Xtend to implement the first query. The code corresponding to the second query in given in Listing 5. For this case study, we developed four new operations: 1. sortedBy (see line 2 in Listing 4, and line 2 in Listing 5) returns a sorted copy of its source collection using one or more criteria. This is a standard OCL operation for which AOF does not have a specific implementation yet. We implemented this operation around a balanced binary tree, which makes it possible to have a logarithmic change propagation time. 2. take (see line 3 in Listing 4, and line 3 in Listing 5) returns the n first elements of a collection. 3. allContents (see line 8 in Listing 4, and line 2 in Listing 5) retrieves all model elements contained in a given source element, filtering them by type. This is not a standard OCL operation but is rather a kind of mix between closure applied on the contents of an element, and select. This operation can be implemented relatively efficiently on observable EMF models, which already provide access to all transitively contained elements of a given element.
4. layering (see line 8 in Listing 5) implements an incremental connected component algorithm. The first two operations (i.e., sortedBy, and take) are relatively generic, and may ultimately be integrated into AOF. allContents is not a basic operation, but should prove useful in other transformations. Finally, layering is more specific to some graph-related transformations.
Listing 4: Q1 in Xtend using AOF 4Some scalability issues of our AOF solution have been solved since the submission to the live competition. results for the initial computation but, as a batch solution, it lacks performance on performing changes. The ATL solution on the standard engine is relatively slow, and not incremental. AOF seems to be slightly more efficient than NMF on Figure 2 but the slight differences may be in part due to the fact that measures are performed differently for .Net-based NMF and Java-based AOF. The very last high update time measure for NMF is likely due to a too small heap size requiring too much garbage collection. In conclusion, the pure ATL solution maximizes conciseness and readability while the pure AOF solution optimizes incremental performance. The AOF-powered backend for ATL aims to jointly address the two dimensions, and the experimental results in figures are promising. We plan in future work to extend this initial prototype to a full fledged solution for efficient incremental execution of declarative query and transformation code.