# A cross-technology benchmark for incremental graph queries

Georg Hinkel, Antonio Garcia-Dominguez, René Schöne, Artur Boronat, Massimo Tisi, Théo Le Calvar, Frederic Jouault, József Marton, Tamás Nyíri, János Benjamin Antal, et al.

<figure><img src="image_1.png" /></figure>

To cite this version:

Georg Hinkel, Antonio Garcia-Dominguez, René Schöne, Artur Boronat, Massimo Tisi, et al. A cross-technology benchmark for incremental graph queries. Software and Systems Modeling, 2022, 21 (April), pp.755-804. 10.1007/s10270-021-00927-5. hal-03594453

HAL Id: hal-03594453

https://hal.science/hal-03594453

Submitted on 21 Nov 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A cross-technology benchmark for incremental graph queries

Georg Hinkel<fnref n="1" /> · Antonio Garcia-Dominguez<fnref n="2" /> · René Schöne<fnref n="3" /> · Artur Boronat<fnref n="4" /> · Massimo Tisi<fnref n="5" /> · Théo Le Calvar<fnref n="5" />,<fnref n="6" /> · Frederic Jouault<fnref n="7" /> · József Marton<fnref n="8" /> · Tamás Nyíri<fnref n="8" /> · János Benjamin Antal<fnref n="9" /> · Márton Elekes<fnref n="9" /> · Gábor Szárnyas<fnref n="10" />

Received: 12 December 2020 / Revised: 31 August 2021 / Accepted: 14 September 2021 / Published online: 8 December 2021
© The Author(s) 2021

## Abstract

To cope with the increased complexity of systems, models are used to capture what is considered the essence of a system. Such models are typically represented as a graph, which is queried to gain insight into the modelled system. Often, the results of these queries need to be adjusted according to updated requirements and are therefore a subject of maintenance activities. It is thus necessary to support writing model queries with adequate languages. However, in order to stay meaningful, the analysis results need to be refreshed as soon as the underlying models change. Therefore, a good execution speed is mandatory in order to cope with frequent model changes. In this paper, we propose a benchmark to assess model query technologies in the presence of model change sequences in the domain of social media. We present solutions to this benchmark in a variety of 11 different tools and compare them with respect to explicitness of incrementalization, asymptotic complexity and performance.

**Keywords** Graph queries · Graph analytics · Model-driven engineering · Performance benchmark · Graph databases · relational databases · Incremental queries · Incremental computing

Communicated by Alexander Egyed.

<figure><img src="image_3.png" /></figure>

Márton Elekes
elekes@mit.bme.hu

Georg Hinkel
georg.hinkel@gmail.com

Antonio Garcia-Dominguez
a.garcia-dominguez@aston.ac.uk

René Schöne
rene.schoene@tu-dresden.de

Artur Boronat
artur.boronat@leicester.ac.uk

Massimo Tisi
massimo.tisi@imt-atlantique.fr

Théo Le Calvar
theo.le-calvar@imt-atlantique.fr

Frederic Jouault
frederic.jouault@eseo.fr

József Marton
marton.jozsef@vik.bme.hu

Gábor Szárnyas
gabor.szarnyas@cwi.nl

## 1 Introduction

Models are a highly valuable asset in any engineering process as they capture the knowledge of a system in a formal abstraction. This abstraction allows to reason on properties in order to obtain insights on the underlying physical system through analysis.

These insights need to be refreshed as soon as the models of the system change in order to stay meaningful. However, for large systems it is often not viable to recalculate the entire model analysis for every change. Rather, it is desirable to

<footnote n="1">¹ Wiesbaden, Germany</footnote>

<footnote n="2">² Aston University, Birmingham, UK</footnote>

<footnote n="3">³ Technische Universität Dresden, Software Technology Group, Dresden, Germany</footnote>

<footnote n="4">⁴ School of Informatics, University of Leicester, Leicester, UK</footnote>

<footnote n="5">⁵ IMT Atlantique, LS2N (UMR CNRS 6004), Nantes, France</footnote>

<footnote n="6">⁶ DIRO, Université de Montréal, Montreal, Canada</footnote>

<footnote n="7">⁷ ERIS, ESEO-TECH, Angers, France</footnote>

<footnote n="8">⁸ Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, Budapest, Hungary</footnote>

<footnote n="9">⁹ Department of Measurement and Information Systems, Budapest University of Technology and Economics, Budapest, Hungary</footnote>

<footnote n="10">¹⁰ CWI, Amsterdam, The Netherlands</footnote>
propagate these changes to the analysis results incrementally, i.e. only recalculate those parts of the analysis results that are affected by a given change.

Requirements regarding these insights often change over time. This makes it very important to express such analyses in a maintainable and understandable form. Recently, multiple model query technologies [6, 9, 17, 45, 65] have been proposed to aid this problem by deriving an incremental change propagation from a declarative specification. Further, of course one could also use existing and established non-incremental query technology, particularly if some parts of the analysis are more complex and may not be supported by tools that target incremental change propagation. Finally, it is also an option to translate the model into dedicated analysis methods to reuse query technology not based on models. Given this plethora of options, it is difficult to estimate the differences and find the trade-offs between these approaches in terms of understandability, conciseness, efficiency and others. Does the tool fit into my technology space? Is it useful to rely on the incrementalization of a tool or is it better—at least performance-wise—to implement change propagation explicitly? How long does it take to recover from an application crash? How much development effort will be necessary to implement change propagation? How does it scale? Can I speed it up by adding more CPU cores? Is the tool extensible or can it happen that my analysis is not supported at some point?<fnref n="1" />

To aid this comparison and assess how current modelling technologies are capable of offering a concise and understandable language for model analysis, yet still offer a good performance in the presence of frequent model changes, we propose the “Social Media” benchmark. In this benchmark, two queries should be formulated that analyse a model of a social media network. In social networks, new Posts, Comments and likes arrive at a very high frequency and thus cause analyses of the entire network to invalidate quickly. In our benchmark, the analyses shall find the most influential posts and comments, according to selected criteria. While the first query is rather simple in the sense that it can easily be solved with standard query operators, the second query is more complex as graph algorithms are used that are not directly supported by query technologies.

Graph queries are difficult from an incrementalization point of view [31] as they capture a rich family of algorithms and they are often described in an imperative pseudo-code that usually utilizes state. Using a generic incrementalization system, this often spans a state space that is too large for an incrementalization to be efficient. To aid this situation, dynamic algorithms are known for a number of graph

problems that offer strategies to propagate graph changes efficiently, often with a radically different approach than how with the computation was performed in the batch (or initial) scenario. However, there is no comparison yet how and how efficient such dynamic algorithms can be included into incremental query technologies.

We collected 11 implementations of this benchmark that cover most of the possible approaches mentioned above and have mostly been created by authors or active developers of the respective tools. Therefore, we claim that we can compare the tools through the solutions for this benchmark. The tools cover a wide area of model query technology and database management systems; thus, the analysis of the solutions using those tools allows us to reason on the previously mentioned questions.

The benchmark was originally proposed at the Transformation Tool Contest (TTC) 2018 as live contest [51]. At the TTC, several solutions have been submitted [12, 17, 34, 49, 78]. After the TTC, we invited further researchers working in incremental query technology to provide solutions in their favourite tools. In this paper, we present all of these solutions and compare them with respect to their features, complexity of change propagation and overall performance.

The remainder of this paper is structured as follows: Sect. 2 presents the benchmark and the queries that it consists of. Section 3 explains the solutions. Section 4 compares the solutions with respect to the declarativeness of the query language, the used data model, the explicitness of the incrementalization, the durability, support for parallelism and the asymptotic complexity of change propagations. Section 5 presents experimental performance results and their analysis. Section 6 discusses related work, and Sect. 7 concludes the paper.

<figure><img src="image_4.png" /><figcaption>Fig. 1 Metamodel (graph schema) of the social network model</figcaption></figure>

<figure><img src="image_5.png" /></figure>

<footnote n="1">¹ These questions have been selected by the authors. We do not claim that this list of questions is complete and a proper analysis of the needs of developers is out of scope for this paper.</footnote>
# 2 The social media benchmark

In this section, we present the benchmark which we use to compare existing incrementalization approaches. First, Sect. 2.1 explains the metamodel that we use to model a social network graph, and then, Sect. 2.2 presents the two queries used in the benchmark. We describe the change sequences in Sect. 2.3 and the phases of the benchmark in Sect. 2.4.

## 2.1 Metamodel and change sequences

In this benchmark, we use the data from the 2016 DEBS Grand Challenge,<fnref n="2" /> adapted from the LDBC Social Network Benchmark [5,30] and the SIGMOD 2014 Programming Contest [27]. For this version of the benchmark, we created an Ecore metamodel to describe the social network, translated the series of events in the original data sources to models and change sequences and manually tuned the obtained change sequences.<fnref n="3" />

The metamodel of the social network is depicted in Fig. 1. The social network consists of Users, Posts and Comments. Users may have friends, which is a unidirectional edge (i.e. it behaves as a symmetric relationship). Submissions form a tree with a Post in its root and Comments as the rest of its nodes. Users may like Comments (likes edge).

## 2.2 Queries

In the scope of the proposed benchmark, we focus on two model queries. The first query (Q1) is rather easy and is expected to be directly supported by the tools. It shall return the most controversial Posts in the social media network. The second query (Q2) is more sophisticated, and we expected it not to be directly supported by tools and force the solutions into case-specific extensions. It shall return the most influential Comments. The results of both queries are concatenated to strings in order to use them for automated correctness checks.

### 2.2.1 Query 1: Most controversial posts

We consider a Post as controversial, if it starts a debate through its Comments. For this, we assign a score of 10 for each Comment that belongs to a Post. Hereby, we consider a Comment belonging to a Post, if it is a reply to either (1) the Post itself or (2) another Comment that already belongs to the Post. In addition, we also value if Users liked Comments, so we additionally assign a score of 1 for each User that

<figure><img src="image_6.png" /><figcaption>Fig. 2 Graph pattern for Q1</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 3 Graph pattern for Q2</figcaption></figure>

has liked a Comment (Users are counted per Comment liked, i.e. a User can contribute multiple times to the overall score). In short, the score of a Post is calculated by taking all Comments which are in the Submission tree rooted in the Post, and scoring each of them as the 10 plus the number of Users that liked the Comment, then summing up these scores.

The goal of the query is to find the three Posts with the highest score. Ties are broken by timestamps, i.e. more recent Posts should take precedence over older Posts. The result string of this query is a concatenation of the Posts ids, separated by the character | (Fig. 2).

### 2.2.2 Query 2: Most influential comments

In this query, we aim to find Comments that are liked by groups of Users. We identify groups through the friendship relation. Hereby, Users that liked a specific Comment form an induced subgraph where two Users are connected if they are friends (but still, only Users who have liked the Comment are considered). The goal of the second query is to find connected components in that graph. We assign a score to each Comment which is the sum of its squared component sizes.

Similarly to the previous query, we aim to find the three Comments with the highest score. Ties are broken by timestamps, i.e. more recent Comments should take precedence over older Comments. The result string is again a concatenation of the Comment IDs, separated by the character | (Fig. 3).

## 2.3 Change sequences

To measure the incremental performance of solutions, the benchmark uses generated *change sequences*. The changes are available in the form of models. An excerpt of the change

<footnote n="2">² https://web.archive.org/web/20190131182518/https://debs.org/debs-2016-grand-challenge-social-networks/.</footnote>

<footnote n="3">³ We introduced changes that would actually affect the results of the queries defined in Sect. 2.2.</footnote>
<figure><img src="image_8.png" /><figcaption>**Fig. 4** Metamodel of model changes (simplified)</figcaption></figure>

metamodel is depicted in Fig. 4. There are classes for each elementary change operation that distinguish between the type of a feature, whether it is an attribute, association or composition change. Subclasses further specify the kind of operation, i.e. whether elements are added, removed or changed. In these concrete classes, the added, deleted or assigned items are included.<fnref n="4" /> The change metamodel also supports change transactions where a source change implies some other changes, for example, setting opposite references.

The elementary changes can be categorized into the following five change types:

- A new User is added

- A new Post is added

- A new Comment is added as a reply to an existing Submission

- A Comment is liked

- Two existing Users become friends

The changes are always additive, i.e. nodes or edges are never deleted. During the contest, these change sequences were made available in NMF and EMF. However, solutions are also allowed to transform the change models into their own, internal change representation. In such case, the transformation of the change representation is excluded from the time measurements.

An example of an update consisting of five elementary changes is depicted in Fig. 5.

<figure><img src="image_9.png" /><figcaption>(a) Initial model and scores. Comment c2 has two components: c2/a consists of User u1, while c2/b consists of Users u3 and u4. Its total score is the sum of the component sizes, i.e. $1^2 + 2^2 = 5$. The result p1|p2 for Q1 and c2|c1|c3 for Q2.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) Updated model after performing a change sequence that inserted five entities: (1) a friends edge between Users u1 and u4, (2) a likes edge from User u2 to Comment c2, (3) a Comment node c4 with (4) an outgoing commented edge to Comment c1 and (5) an incoming likes edge from User u4. The changes have increased the score of Post p1 by 10 + 2 and also resulted in Comment c2 having a single component of size 4, therefore being awarded a score of $4^2 = 16$. Comment c4 received a score of $1^2 = 1$. The result p1|p2 for Q1 and c2|c1|c4 for Q2.</figcaption></figure>

<caption>**Fig. 5** Example model: initial and updated state with expected query results. The undirected friends edges are denoted with dashed lines</caption>

## 2.4 Benchmark phases

The benchmark consists of the following execution phases:

1. **Initialization:** Setup modelling framework.

2. **Loading:** Load initial models.

3. **Initial evaluation:** Compute selected query for initial model.

4. **Updates:** *Change sequences* are applied to the model. Each change sequence consists of several elementary change operations. After each change sequence, the query result must be consistent with the changed source models, either by entirely creating the view from scratch (*batch*

<footnote n="4">⁴ In a composite insertion, the added element is contained, otherwise only referenced.</footnote>
(evaluation) or by propagating changes to the view result
(incremental evaluation).

Solutions are mainly competing on their *update* perfor-
mance, but are also expected to keep the times of the *loading*
and *initial evaluation* at a reasonable level.

3 Solutions

In this section, we present the solutions developed for the
Social Media benchmark from Sect. 2. We present the fol-
lowing solutions:

- Modelling tools and graph databases running in a managed runtime (JVM<fnref n="5" /> or CLR<fnref n="6" />):

- A solution using the plain .NET query API and NMF to represent the models in memory (Sect. 3.2) and a solution using the incrementalization system of NMF (Sect. 3.3).

- Multiple solutions using the model management system Hawk (Sect. 3.4).

- A solution using the incremental reference attribute grammar tool JastAdd (Sect. 3.5).

- A solution using the model transformation language YAMTL (Sect. 3.6), with a batch variant and two incremental variants (implicit/explicit incremental-ity).

- A batch solution using the ATL model transformation language with the EMFTVM batch execution engine (Sect. 3.7).

- A solution written in Xtend (Sect. 3.8).

- Two incremental solutions based on AOF (Sect. 3.9):
  (1) the AOF solution with Xtend surface language,
  (2) the ATL Incremental solution with ATL surface language.

- Batch and incremental solutions using the Neo4j graph DBMS (Sects. 3.10–3.11).

- Tools using relational or matrix-based representations, running on native runtimes:

- Batch and incremental solutions using the PostgreSQL relational DBMS (Sects. 3.12–3.13).

- Batch and incremental solutions formulated in linear algebra using the GraphBLAS API and the SuiteSparse:GraphBLAS library (Sects. 3.14–3.15), implemented in C++.

- A solution using the Differential Dataflow programming model implemented in Rust (Sect. 3.16).

In broad terms, there have been recurrent approaches for
solving the two queries. To help reduce the length of the
solution descriptions, a first subsection will provide a broad
categorization of the approaches followed by the various
solutions for each query. This will be followed by a sub-
section for each solution: it will start with a description of
the used tool, followed by detailed explanations on how they
implemented the queries. Given that most solutions have
been developed by the tool authors or expert developers, we
assume that the solutions represent the best or close to opti-
mal solution possible for each tool.

Solutions created during the contest were described in
the proceedings of the event [35]. Preliminary version of
the Neo4j and GraphBLAS solutions was discussed in [29]
and [28], respectively.

3.1 Common solution approaches

Further examination of the various solutions showed that sev-
eral common patterns were recurrent through the approaches
chosen to solve the two queries. In this section, we will
provide a broad classification that will be used in the solu-
tion descriptions, in order to allow them to focus on their
technology-specific aspects.

3.1.1 Query 1: Most controversial posts

The solutions for this query can largely be characterized
across two dimensions: whether they were incremental in
their maintenance of the scores, and how they maintained
the set of the top three elements. Table 1 summarizes this
classification.

Regarding the first dimension, we acknowledge similarly
to Giese and Wagner [36] that there can be different degrees
of incrementality in a transformation.<fnref n="7" /> Specifically, we con-
sider these three variants:

- Non-incremental or *batch* solutions, which re-compute
  the scores from scratch after each change.

- Partially incremental solutions, which re-compute scores of Posts impacted by changes from scratch.

- *Fully incremental* solutions that update the scores of the *Posts* impacted by changes as needed, without recomputing them from scratch (for instance, a new like would simply increase the previous score by 1).

In regard to the second dimension, four broad variants
were found:

<footnote n="5">⁵ Java Virtual Machine, the Java runtime.</footnote>

<footnote n="6">⁶ Common Language Runtime, the .NET runtime.</footnote>

<footnote n="7">⁷ While there are some similarities between our “partially/fully” incremental labels and the “effectively/fully incremental” labels of Giese and Wagner, we do not claim our definitions to be equivalent, as they are specific to these queries.</footnote>
<table><caption>**Table 1** Classification of approaches for Q1, ordered by solution name and support for incrementality</caption><thead><tr><th>Solution</th><th>Incrementality</th><th>Sorting</th></tr></thead><tbody><tr><td>AOF</td><td>⊗</td><td>Incremental</td></tr><tr><td>ATL</td><td>○</td><td>Full</td></tr><tr><td>ATL incremental</td><td>⊗</td><td>Incremental</td></tr><tr><td>Differential Dataflow</td><td>⊗</td><td>Full</td></tr><tr><td>GraphBLAS</td><td>○</td><td>Offline top-x</td></tr><tr><td>GraphBLAS incremental</td><td>⊗</td><td>Offline top-x</td></tr><tr><td>Hawk</td><td>∅</td><td>Full</td></tr><tr><td>Hawk (IU)</td><td>∅</td><td>Full</td></tr><tr><td>Hawk (IUQ)</td><td>∅</td><td>Online top-x</td></tr><tr><td>JastAdd</td><td>∅</td><td>Offline top-x</td></tr><tr><td>Neo4j</td><td>○</td><td>Offline top-x</td></tr><tr><td>Neo4j incremental</td><td>⊗</td><td>Incremental</td></tr><tr><td>NMF reference</td><td>○</td><td>Full</td></tr><tr><td>NMF incremental</td><td>⊗</td><td>Incremental</td></tr><tr><td>PostgreSQL</td><td>○</td><td>Online top-x</td></tr><tr><td>PostgreSQL incremental</td><td>⊗</td><td>Online top-x</td></tr><tr><td>Xtend</td><td>○</td><td>Online top-x</td></tr><tr><td>YAMTL-B</td><td>○</td><td>Online top-x</td></tr><tr><td>YAMTL-II</td><td>∅</td><td>Online top-x</td></tr><tr><td>YAMTL-EI</td><td>⊗</td><td>Online top-x</td></tr></tbody></table>

Notation: ⊗ yes; ∅ to some extent; ○ no

- Full sorting solutions, which use a standard sorting algorithm (typically the one in the standard libraries for the chosen language) to sort the elements by score, incurring a cost of $O(n \log n)$.

- Incremental sorting solutions, which use a dedicated data structure to maintain the elements sorted as they appear and as their individual scores change (e.g. a balanced search tree).

- Offline top-x solutions, which keep in memory the full list of scores and do a single pass over the elements, maintaining only the top-x elements in an auxiliary list. This has a reduced cost of $O(n)$.

- Online top-x solutions, which only keep in memory the Posts with the top-x scores at any time. This effectively has the same sorting cost of $O(n)$, but reduces the amount of memory needed.

Note that the *online top-x* is only feasible due to the fact that the possible changes mentioned in Sect. 2.3 never remove likes or delete comments: this means that scores are monotonically increasing. This optimization will typically be one that a generic “top-x” incremental operator would not do, as the sorting key could go down as well as up in value in the general case.

### 3.1.2 Query 2: Most influential comments

The solutions can be characterized across three dimensions: whether they maintained the set of connected components in the graph incrementally, the approach used to compute the set of connected components, and how they sorted the scored results. The general classification is summarized in Table 2.

For the first dimension of incrementality, this is generally easier than in the previous solution, as it is simply whether after each change, they update the set of connected components, or re-compute it. For the second dimension, five broad approaches were followed:

- The most popular approach was to reuse *Tarjan's algorithm* for computing the set of connected components in a graph [84], which has a worst-case performance of $O(|V| + |E|)$.

- The next most popular approach was a *naive recomputation* of the component that each node belonged to after each change, by using breadth-first or depth-first traversals from that node.

- Some solutions took advantage of the fact that the changes never remove links, using a simpler *union-find* data structure and using the union operation whenever a new edge was added. In a way, this is similar to how some solutions of query 1 used this “monotonically growing” graph to simplify the way to maintain the top-x elements.

- There were a few individual solutions that used *specialized algorithms*, such as FastSV [88], or label propagation.

The third dimension is the approach followed to compute the top scoring results, which uses the same four broad variants as in Sect. 3.1.1.

## 3.2 Reference solution: C# query syntax

As reference, we use a solution using NMF [45,50] for the model representation and the standard .NET collection operators through the C# query syntax. During the TTC and throughout the remainder of this paper, this solution is used as a reference in terms of performance and understandability as it represents a solution if one just uses what mainstream programming languages (in this case C#) can provide without a dedicated incremental model query technology.

### 3.2.1 Tool description

The query syntax and the underlying collection operators are features built into the C# programming language and actively used by millions of developers.
<table><caption>**Table 2** Classification of approaches for Q2, sorted by tool and incrementality</caption><thead><tr><td>Solution</td><td>Incremental conn. components</td><td>Algorithm</td><td>Sorting</td></tr></thead><tbody><tr><td>AOF</td><td>⊗</td><td>Breadth-first traversal</td><td>Incremental</td></tr><tr><td>ATL</td><td>○</td><td>Depth-first traversal</td><td>Full</td></tr><tr><td>ATL incremental</td><td>⊗</td><td>Breadth-first traversal</td><td>Incremental</td></tr><tr><td>Differential Dataflow</td><td>⊗</td><td>Fixed-point label propagation</td><td>Full</td></tr><tr><td>GraphBLAS</td><td>○</td><td>FastSV</td><td>Offline top-x</td></tr><tr><td>GraphBLAS incremental</td><td>∅</td><td>FastSV on overestimation + merge</td><td>Online top-x</td></tr><tr><td>Hawk</td><td>○</td><td>Tarjan</td><td>Full</td></tr><tr><td>Hawk (IU)</td><td>○</td><td>Tarjan</td><td>Full</td></tr><tr><td>Hawk (IUQ)</td><td>○</td><td>Tarjan</td><td>Online top-x</td></tr><tr><td>JastAdd</td><td>∅</td><td>Depth-first/Kosaraju</td><td>Offline top-x</td></tr><tr><td>Neo4j</td><td>○</td><td>Union-find variant</td><td>Offline top-x</td></tr><tr><td>Neo4j incremental</td><td>⊗</td><td>Breadth-first traversal</td><td>Incremental</td></tr><tr><td>NMF reference</td><td>○</td><td>Tarjan</td><td>Full</td></tr><tr><td>NMF incremental</td><td>⊗</td><td>Edge changes</td><td>Incremental</td></tr><tr><td>PostgreSQL</td><td>○</td><td>Breadth-first traversal</td><td>Online top-x</td></tr><tr><td>PostgreSQL incremental</td><td>∅</td><td>Overestimation + breadth-first traversal</td><td>Online top-x</td></tr><tr><td>Xtend</td><td>○</td><td>Tarjan</td><td>Online top-x</td></tr><tr><td>YAMTL-B</td><td>○</td><td>Weighted quick-union-find with path compression</td><td>Online top-x</td></tr><tr><td>YAMTL-II</td><td>⊗</td><td>Weighted quick-union-find with path compression</td><td>Online top-x</td></tr><tr><td>YAMTL-EI</td><td>⊗</td><td>Weighted quick-union-find with path compression</td><td>Online top-x</td></tr></tbody></table>

Notation—⊗ yes; ∅ to some extent; ○ no. Overestimation means that all connected components are re-computed that might be affected by the changes

### 3.2.2 Query 1

1. `string.Join('|',`
2. `(from post in SocialNetwork.Posts`
3. `let score = post.Descendants().OfType<Comment>()`
4. `.Sum(c => 10 + c.LikelyBy.Count)`
5. `then by (score, post_TIMESTAMP) descending`
6. `select post.Id).Take(3));`

**Listing 1** A solution for Q1 using the standard collection operators of .NET.

The reference solution for Q1 is depicted in Listing 1. It is a full sorting batch implementation. Lines 3–4 of this listing compute the score of a given *Post* by summing up the scores for the *Comments* of a given *Post*. To get all *Comments* of a *Post*, the solution simply uses the *Descendants* operation available to any NMF model element and combines it with a simple type filter. This implicitly utilizes the composition hierarchy to obtain a collection of all elements contained somewhere in the given *Post*. Line 5 simply states that the collection of *Posts* should be ordered by the score and the timestamp, before Line 6 specifies that we are only interested in the first three entries.

### 3.2.3 Query 2

1. `string.Join('|',`
2. `(from comment in SocialNetwork.Descendants().OfType<Comment>()`
3. `let layering = Layering<IUUser>.CreateLayers`
4. `comment.LikelyBy`
5. `u => u.Friends.Intersect(comment.LikelyBy))`
6. `let score = layering.Sum(l => Square(l.Count))`
7. `then by (score, comment_TIMESTAMP) descending`
8. `select comment.Id).Take(3));`

**Listing 2** A solution for Q2 using the standard collection operators of .NET and an implementation of Tarjan's algorithm.

The reference solution for Q2 is depicted in Listing 2, a full sorting batch implementation using Tarjan's algorithm. It is very similar to Listing 1 in its overall structure except for the slightly more complex score calculation due to the required computation of connected components. For this, we are using the class *Layering*, an implementation of Tarjan's algorithm [84]. This implementation requires specifying the underlying graph through its nodes (for each *Comment*, this is the set of *Users* that have liked the *Comment*) and a function obtaining incident nodes of a given node (in this case the friends of a given *User* that have also liked the *Comment*). The result of the scoring computation is then again ordered and the IDs of the first three elements are returned.
## 3.3 NMF incremental

### 3.3.1 Tool description

NMF Expressions [46,52] is an incrementalization system that uses the feature of the C# language to compile lambda expressions into models of the code, instead of machine code. These models are then used to derive a dynamic dependency graph (DDG) from a given expression and observe changes. These changes originate from elementary update notifications and are propagated through the dependency graph.

Based on the underlying formalization as a categorical functor, NMF Expressions is able to include custom incrementalizations of functions and includes a library of such manually incrementalized operators, including most of the Standard Query Operators (SQO).<fnref n="8" />

### 3.3.2 Query 1

While NMF Expressions includes an incrementalization of most SQOs, the `Take` method used in the reference solution for Q1 is not supported, same as any other query operators of the SQO that deal with indices. The reason for this is that it is costly to find out the index of an element in, for example, a filtered, unsorted list given the index in the source collection. This always requires a linear scan; meanwhile, the SQO implementations generally try to propagate changes in constant or near constant time (logarithmic effort for updating sorted lists). Therefore, the fact that `Take` is not supported is simply because it cannot be implemented efficiently, at least not in the general case.

However, we identified top-x queries, i.e. analyses that sort elements for a given criteria and then report on a small number of elements with the best scores, as a rather common pattern. Therefore, we added dedicated support for this kind of analysis operators into NMF. This operator is called `TopX`. It is essentially a combination of an incremental sort (using balanced binary search trees) and a simple poll for the first x elements upon any change of the balanced binary search tree, assuming that x is small (in comparison with the size of the search tree). The computation of the scores is, however, using the incrementalization system and fully incremental.

1. `query = Observable-YExpression()`
2. `SocialNetwork.Posts.TopX(3,`
3. `post => ValueTuple.Create`
4. `post.Descendants().OfType<Comment>`
5. `.Sum(c => 10 + c.LikedBy.Count)`
6. `post Timestamp))`
7. );

<caption>Listing 3 Incremental NMF Solution for Q1.</caption>

The solution to Q1 is shown in Listing 3. We simply calculate the top-3 `Posts` where the score of a `Post` is calculated as a tuple of the score and the timestamp in order to break ties. The result of the lambda expression in Line 2 is an array of tuples of the `Posts` and their scores (actual score and timestamp). Lines 3 to 6 determine how this tuple is created: we iterate over all `Comments` in a `Post` and, for each, sum up 10 plus the number of `Users` that have liked the `Comment`.

Lines 1 and 7 surround this lambda expression with a call to *NMF Expressions* to obtain an incrementalization of this analysis. With that call, we tell *NMF Expressions* to create a DDG for us. The return value of this function is the root node of this DDG. This node implements a generic interface `INotifyValue` that provides the current analysis result as well as an event to notify clients when the analysis result changes. In the benchmark solution, we do not make use of this event but repeatedly query the current value of the DDG node. This call is fast, because each node in the DDG always references its current value.

### 3.3.3 Query 2

The solution for Q2 is very similar to the solution of Q1, except for the fact that for each `Comment`, it involves finding connected components in a graph spanned by `Users` that liked the `Comment` and their friendship relations. There is no incremental implementation for finding connected components available that is built into NMF.

From an algorithmic point of view, the incrementalization of the connected components will be rather simple: we cache the current set of connected components and re-compute whenever an edge is added to the graph between two nodes of different components. This incremental algorithm can be isolated into a class `ConnectedComponents` that is theoretically reusable in different contexts.

With this algorithmics class, we can solve Q2 as in Listing 4. Similar to Q1, the solution is an incremental solution with incrementally maintained full sort and an incremental version of Tarjan's algorithm. In Lines 1 and 2, we create a function that, given a `Comment` and a `User`, creates the collection of `Users` who (1) are friends with the given `User` and (2) like the `Comment`. Because we do not care about changes of the incident function, the function to get the connected `Users` is used as compiled code, using the `Func` class. This is slightly more efficient than the format of lambda

<footnote n="8">⁸ http://msdn.microsoft.com/en-us/library/bb394939.aspx. Even though the term SQO may not be common to many developers, the syntax is very commonly used in the .NET community, in particular through the LINQ technology that translates queries to SQL or other declarative languages.</footnote>
1 Func<IC Comment, Func<IU s, IordsableExpression<IU s>>
2 friendsBuilder = c => (u =>
3 u.Friends.Intersect(c.LiketedBy));
4 query = Observable .Expression( () =>
5 SocialNetwork .Descendants() .OfType<IC Comment> ()
6 .TopX(3, comment => ValueTuple .Create(
7 ConnectedComponents<IU s> .Create(
8 comment.LiketedBy,
9 friendsBuilder( comment))
10 .Sum(group => Squared(group.Count())) ,
11 comment Timestamp))
12 );

<caption>**Listing 4** Incremental NMF Solution for Q2.</caption>

expressions that *NMF Expressions* can use for the incremen-
talization. However, *NMF Expressions* currently has some
problems to integrate compiled lambda expressions, so we
need to specify this function separately, outside the scope of
*NMF Expressions*.

In Lines 4 and 12, we frame the actual analysis with
*NMF Expressions*, allowing it to create the DDG for the
inner analysis that is in Lines 5 to 11. In particular, we first
iterate all elements in the social network model and filter
for *Comments* in Line 5. From these, we pick the topmost
elements according to the tuple of scores and timestamps,
similar to the solution of Q1. To calculate the score of a *Post*,
we simply run the analysis of connected components where
the incident nodes of a given *User* are the subset of his friends
that also liked that *Comment* (Lines 7 to 9). Given these con-
nected components, we calculate the sum of the squared sizes
(Line 10) and break ties using the timestamps (Line 11).

3.3.4 Transactions and parallelism

NMF Expressions has some support for transactions and par-
allelism. The support for transactions means that a DDG node
is only processed if all of its dependencies have been pro-
cessed. Because each transaction may invalidate a different
set of DDG nodes, this implies that changes in the DDG need
to be processed in a two-pass fashion: in the first pass, the set
of potentially affected DDG nodes is calculated, while in the
second pass, the changes are actually propagated. Because
the transactional behaviour guarantees that each DDG node
is only updated at most once in each transaction, the overhead
of two passes may be saved. However, whether or not this
is the case largely depends on the analysis and the change
sequence.

Q1 cannot profit from transactions at all, because whether
the changes to any DDG node come at once or one after
another does not matter. For Q2, this is slightly different
because we are recalculating the connected components in
multiple cases. If a change sequence contained multiple
events that would cause to re-compute the connected com-

ponents for a Comment, this calculation is only needed once
if the changes are propagated in a transaction.

The transactional support in *NMF Expressions* is very easy
for a developer to use: all that needs to be done is to put
the changes inside a transaction. Because in the scope of
the benchmark, these changes come in a dedicated change
sequence object, we just need to wrap the application of such
a change sequence in a transaction as done in Listing 5.

1 ExecutionEngine.Current.BeginTransaction();

2 changesnos Apply();

3 ExecutionEngine.Current com itTransaction();

<caption>**Listing 5** Wrapping the application of the change sequence in a transaction.</caption>

Lastly, *NMF Expressions* also allows to propagate the
changes within such a transaction in parallel. This is done by
changing the execution engine implementation as depicted
in Listing 6.

1 ExecutionEngine.Current = new ParallelExecutionEngine();

<caption>**Listing 6** Enabling parallel change propagation in NMF.</caption>

The parallel change propagation then allows changes
within a transaction to be propagated in parallel on differ-
ent threads, synchronizing at each DDG node.

3.4 Hawk

3.4.1 Tool description

Eclipse *Hawk* is a tool to manage models that have been
fragmented (e.g. for versioning purposes) by incrementally
indexing the various connected fragments into a common
graph database [8]. *Hawk* can watch over a local folder or
a version control system and update the graph whenever the
model files change. For this case study, *Hawk* was config-
ured with the ability to index EMF models, maintain a graph
database using one of three backends (Neo4j, SQLite, or
Greycat [42]) and run queries in a dialect of the Epsilon
Object Language (EOL) [61]. Greycat implements a graph-
oriented data model on top of existing key-value stores, such
as LevelDB or RocksDB. For the present work, LevelDB was
chosen as the underlying key-value store.

Further, *Hawk* provides the concept of “derived attributes”,
which extend a type with pre-computed expressions which
are updated incrementally as the graph changes. These
attributes are also indexed for fast lookup.

3.4.2 Query 1

Several versions of the first query were implemented. For
the sake of clarity, we will call these “batch”, “incremental
update” (IU) and “incremental update and query” (IUQ). As
mentioned in Table 1, all Hawk variants have partial incrementality. Batch and IU use full result sorting, and IUQ uses an “online top-x” approach.

The batch mode is the most direct use of *Hawk*. In this version, the tool is told to watch a folder that contains the initial version of the model. An EOL script replays the change sequences on the model, and *Hawk* updates the graph based on the new versions of the model. The *Post* type is extended with the *score* derived attribute, which is updated incrementally by *Hawk*. The definition of *score* is as follows, using *self* as the *Post* being extended:

1. `return self.closure(s | s.comments).flatten`

2. `.collect(s | 10 + s.likedBy.size).sum();`

**Listing 7** Hawk Q1: Derived attribute score for Post.

With this derived attribute, it is simple to implement the main query itself. However, in order to sort the Posts with the Java Collections `sort` method, a native Java class implementing the `Comparator` interface is needed:

1. `var scored = Post.all.collect(p | Sequence {`

2. `p.id, p.score, p.timestamp)).asSequence;`

3. `Native('java.util.Collections').sort scored,`

4. `new Native('org.hawk.ttc2018.queries.ResultComparator');`

5. `return scored.subList(0, scored.size.min(3));`

**Listing 8** Hawk Q1: Use of derived attribute score in the batch and incremental update solutions.

The incremental update mode uses an alternative graph update class, `ChangeSequenceAware Updater`. This speeds up the process by directly applying the change sequence on the graph, without touching the original model file. The query itself remains the same as the one in the batch mode, using the same derived attribute.

Finally, the incremental update and query mode reuses the same custom `updater`, while changing the way the query is run. A graph change listener is attached to *Hawk*: on each new model version, only the updated Posts are re-scored before selecting the new top-3 elements. The re-scoring is done by invoking the expression in Listing 7 on each *Post* that has been updated.

### 3.4.3 Query 2

The second query goes through the same three versions: `batch`, `incremental update` and `incremental update and query`.

The actual query is noticeably more complex, since it essentially requires implementing Tarjan’s strongly connected components algorithm [84] in about 37 lines of EOL. As indicated in Table 2, Tarjan is re-run after each change, and IUQ uses an “online top-x” sorting approach instead of doing a full sort.

In this case, the `Comment` class is extended with a `score` derived attribute. A high-level view of the query shows how it loops over the `Users` that liked the `Comment`, detecting connected components in each of them and computing the score of the `Comment` as the sum of the squares of the sizes of each component:

1. `var components: Sequence;`

2. `var indexes: Map;`

3. `for (user in self.likedBy) {`

4. `if (not indexes.containsKey(user.id)) {`

5. `// strongconnect is 37 lines of EOL code`

6. `user.strongconnect(self);`

7. `}`

8. }

9. `return components.collect(c | c.size * c.size).sum();`

**Listing 9** Hawk Q2: Outline of the derived attribute score for Comment.

The queries for the *batch* and *incremental update mode* are the same, with a collection of all the IDs, scores and timestamps, and sorting to get the top-3 elements:

1. `var scored = Comment.all.collect(c | Sequence {`

2. `c.id, c.score, c.timestamp)).asSequence;`

3. `Native('java.util.Collections').sort scored,`

4. `new Native('org.hawk.ttc2018.queries.ResultComparator');`

5. `return scored.subList(0, scored.size.min(3));`

**Listing 10** Hawk Q2: Use of derived attribute score in the batch and incremental update solutions.

The *incremental update and query mode* works the same as in the previous query. A graph change listener detects the Comments that should be re-scored, and the new scores are merged with the old ones to keep the top-3 elements up to date.

## 3.5 JastAdd

### 3.5.1 Tool description

Attribute Grammars [60] can be used to describe the structure of context-free data along with their static semantics. Reference Attribute Grammars (RAGs) [43] extend this paradigm such that attributes are allowed to return other nodes of the abstract syntax tree (AST) as a result of their computation.

The tool *JastAdd* [44] is based on Reference Attribute Grammars and offers *non-terminal attributes* [86] and *circular attributes* [62], used to represent a part of the model and to compute parts of the second query, respectively. In *JastAdd*, a grammar specified in BNF with inheritance and attributes specified written in Java are woven together to generate plain
Java code. It contains a Java class for every non-terminal specified within the grammar, uses the code of the attributes inside its methods and has additional boilerplate code, e.g. to handle caching.

JastAdd does not work with EMF models directly, but requires users to transform the input metamodel into an AST representation using a dedicated syntax [67].

1 abstract ModelElement ::= <Id:Long> ;
2 SocialNetwork : ModelElement ::= User* Post* ;
3 User : ModelElement ::= <Name: String> ;
4 abstract Submission : ModelElement ::= <Timestamp:Long> <Content: String> Comment* ;
5 Comment : Submission ::= /<Post:Post>/ ;
6 Post : Submission ::= ;
7 rel User. friends* -> User ;
8 rel User. submissions* -> Submission ;
9 rel User. likes* <-> Comment. likedBy* ;

<caption>Listing 11 JastAdd Grammar for a SocialNetwork.</caption>

Listing 11 shows the grammar representing the metamodel of Fig. 1. All identifiable nodes inherit from ModelElement giving them a unique number. Also, the root node SocialNetwork is identifiable to later be able to insert new Users and Posts. The two non-containment references friends and submissions are replaced by explicit unidirectional relations, whereas the likes and likedBy edges are modelled using an explicit bidirectional relation (Line 9 in Listing 11).

3.5.2 Query 1

To solve the first query, all Comments referring to a Post
are computed, and afterwards, the score of this Post can be
calculated with the following attribute:

1 syn int Post.score() {
2   int result = 0;
3   for (Comment comment :
        commentsForPost()) {
4     result += 10 +
        comment.likedBy().size();
5   }
6   return result;
7 }

After gathering all scores, a simple iteration over all Posts
and keeping the top-3 is performed to get the final result.

3.5.3 Query 2

For the second query, two variants are evaluated, show-
ing two different approaches within the JastAdd solution.
Those variants differ in the way how the Users liking
the same Comment are calculated. For the first variant,
a circular attribute User.getCommentLikerFriends
(shown below) is used.

1 syn Set<User> User.getCommentLikerFriends(Comment comment) circular
   [new HashSet<User>());
2 eq User.getCommentLikerFriends(Comment comment) {
3 Set<User> s = new HashSet<>();
4 s.add(this);
5 for (User f : friends()) {
6   for (Comment otherComment : f.likes()) {
7     if (otherComment == comment) {
8       s.add(f);
9     for (User commentLikerFriend :
           f.getCommentLikerFriends(comment)) {
10       s.add(commentLikerFriend);
11     }
12   }
13 }
14 }
15 }
16 return s;
17 }

This attribute will start with the set containing the User it
should compute the friends for. Then, if another friend likes
the Comment, it adds this friend and calls itself recursively.
The recursion always terminates as the number of Users is
finite and the circular attribute is only invoked again if the
returned set has changed.

The second variant follows the approach described in [66] highlighting reuse of application-independent analysis. In fact, the algorithm for computing an SCC presented in that work was reused without modification for solving the subproblem of query 2 to compute Users liking the same Comment. To integrate it, a mapping from User to Component was established, while the friend relationship served as a basis to connect those components.

To compute the score of a Comment using the second vari-
ant, the squared size of every set of components is summed:

1 refine Queries eq Comment.score() {
2   int score = 0;
3   Set<Set<Component>> sccs = this.toDependencyGraph().SCC();
4   for (Set<Component> userSet : sccs) {
5     int usize = userSet.size();
6     score += usize * usize;
7   }
8   return score;
9 }

To get the final result, the same iteration as for the first
query is used (not shown here).

3.6 YAMTL

3.6.1 Tool description

YAMTL [16] is a model transformation language for EMF
models, with support for incremental execution [18], designed
as an internal DSL of Xtend. The solution to the Social
Media benchmark uses query rules that only consist of
input patterns, whose filters define the queries, and uses the
YAMTL pattern matcher for evaluating them. Queries are
defined using Xtend and the Java Collections Framework.
The YAMTL solutions implement the online top-x approach,
keeping the best three candidates at all times, with the oper-
ation bestThreeCandidates.
Three variants of the solutions have been implemented: batch (YAMTL-B), implicitly incremental (YAMTL-II) and explicitly incremental (YAMTL-EI). YAMTL-B disables dependency tracking enabling a faster initial transformation but subsequent updates compute queries from scratch. YAMTL-II detects which matches need to be re-computed according to updates to the input model, without requiring additional logic in the queries. For each impacted match, the filter expression is re-evaluated from scratch, and the solution is therefore partially incremental. YAMTL-EI exposes model updates affecting an impacted match so that these can be processed explicitly in the filter expression, and the solution is therefore fully incremental. The additional logic that handles incremental updates explicitly in YAMTL-EI has been highlighted in grey. YAMTL-B and YAMTL-II solutions can be obtained by deleting this code. Enabling incremental evaluation and explicit handling of updates is done via configuration parameters.

### 3.6.2 Query 1

Q1 is implemented as a query rule, whose input pattern is formed by an `in` element that will match Posts that contain Comments as indicated in the filter. In particular, the EMF method `post.eAllContents()` fetches all contained Comments within the matched Post. The implementation of the query is shown in Listing 12.

```javascript
1 rule('Q1').in('post', SN.post).filter[
2   val post = 'post'.fetch as Post
3   var score = 0
4   if (post.comments?.size > 0) {
5     val map = this.fetch('dirtyObjects')
6     as Map<EObject, List<YAMTLChangeType>>
7     if (map === null || map.isEmpty) {
8       val allComments = post.eAllContents
9     while (allComments.hasNext) {
10       score += 10 + (allComments.next
11                 as Comment).likedBy.size
12     }
13   }
14   else {
15     for (comment: map.keySet) {
16       score += 10 + (comment as Comment).likedBy.size
17     }
18   }
19   threeBestCandidates.addIfIsThreeBest(post,
20                                     score)
21   return true
22 }
23 ].query
```

<caption>Listing 12 Q1 in YAMTL.</caption>

The expression `this.fetch('dirtyObjects')` returns the objects that are added under the Post object being matched. For each such added object that is a Comment,

the score is computed. The solution to Q2 shows how this case could be handled.

### 3.6.3 Query 2

The computation of connected components has been implemented using Sedgewick and Wayne's weighted quick unionfind with path compression algorithm [80].<fnref n="9" /> The query, including logic handling updates explicitly, is shown in Listing 13. The instantiation of the class `FriendComponentUtil UF` computes the connected components of the graph whose nodes are the set of Users who liked the Comment, i.e. `comment.likedBy`. Comment scores are stored so that they can be subject to updates.

The expression `this.fetch('dirtyFeatures')` returns the collection of features for the Comment being matched, which have been updated so that they can be handled explicitly. The original union find algorithm has been extended to enable incremental updates of the computed components when a Comment is liked by a User (`add LikedBy()`) and when a new friendship is declared (`addFriendship()`). When there are less than three Comments with a score different from zero, Comments from `candidatesWithNilScore` are used to complete the list.

```javascript
1 rule('Q2').in('comment', SN comment).filter[
2   val comment = 'comment'.fetch as Comment
3   var score = 0
4   var matches = false
5   if (comment.likedBy.size > 0) {
6     var FriendComponentUtil UF fc
7     fc = componentMap.get(comment)
8     if (fc === null) {
9       fc = new FriendComponentUtil_UP(comment.likedBy)
10     } else {
11       val map = this.fetch('dirtyFeatures')
12       as Map<EObject, List<YAMTLFeatureValueChange>>
13       for (e: map.entrySet) {
14         for (fv: e.value) {
15           switch(fv featureName) {
16             case 'likedBy': fc.add LikedBy(fv.value as User)
17             case 'friends': fc.addFriendship(e.key as User,
18                                      fv.value as User)
19           }
20         }
21       }
22     }
23   }
24   score = fc.score
25   threeBestCandidates.addIfIsThreeBest(comment, score)
26   matches = true
27   } else {
28     if (threeBestCandidates.size <= 3)
29       candidatesWithNilScore.add(comment)
30   }
31   matches
32 ].query
```

<caption>Listing 13 Q2 in YAMTL.</caption>

<footnote n="9">⁹ This solution is different from the one presented at the contest [17] and has been developed to facilitate the analysis together with the other tools involved in this study.</footnote>
1 `query topPosts = SN!Post.allInstances()->sortedBy(e | e.timestamp)->sortedBy(e | e.score)->reverse()->subSequence(1, 3);`
2 `helper context SN!Submission def : allComments : Sequence(SN!Comment) =`
3 `self.comments->union(self.comments->collect(e | e.allComments)->flatten());`
4 `helper context SN!Post def : countLikes : Integer = self.allComments->collect(e | e.likedBy.size())->sum();`
5 `helper context SN!Post def : score : Integer = 10*self.allComments->size() + self.countLikes;`

<caption>Listing 14 Q1 in ATL.</caption>

1 `query topComments = SN!Comment.allInstances()->sortedBy(e | e.timestamp)->sortedBy(e | e.score)->reverse()->subSequence(1, 3);`
2 `helper context SN!Comment def : score : Integer = self.allComponents->collect(c | c.size()*c.size())->sum();`
3 `helper def : allFriends(u: SN!User, s:Sequence(SN!User)) : TupleType(component : Sequence(SN!User), remaining : Sequence(SN!User)) = ...`
4
5 `helper context SN!Comment def : allComponents : Sequence(Sequence(SN!User)) =`
6 `self.likedBy->iterate(u;`
7 `acc : TupleType/components : Sequence(Sequence(SN!User)), visited : Sequence(SN!User)) =`
8 `Tuple<components=Sequence(), visited=Sequence{T}) |`
9 `if (acc.visited->includes(u))`
10 `then acc`
11 `else let component : TupleType(component : Sequence(SN!User), remaining : Sequence(SN!User)) =`
12 `thisModule.allFriends(u, self.likedBy->excluding(acc.visited)).`
13 `component in`
14 `Tuple<components = acc/components.append(component), visited = acc.visited->union(component)}`
15 `endif).components;`

<caption>Listing 15 Q2 in ATL.</caption>

## 3.7 ATL

### 3.7.1 Tool description

ATL [55] is one of the most common model transformation languages. The solution to the Social Media benchmark only uses ATL queries, i.e. the ATL constructs that allow users to define expressions in the ATL flavour of OCL. ATL queries can call helper OCL functions and libraries and are evaluated over the source model(s) by the ATL virtual machine, that is optimized for model operations.

The vanilla ATL that was used to implement the benchmark does not have support for incremental execution. Classical engines that execute ATL incrementally [56,63] do not support the incremental evaluation of OCL expressions. Changes on the source model trigger the recomputation only of the impacted OCL expressions, but the whole expressions are re-computed. In Sect. 3.9, we describe a solution that achieves incremental OCL expression evaluation for ATL code, by compiling it towards AOF.

The solution is a pure ATL query and executed on the most recent ATL virtual machine (EMFTVM). Since ATL queries are OCL expressions, this solution includes a complete encoding of the case study as declarative and functional OCL code.

### 3.7.2 Query 1

The full code for Q1 is presented in Listing 14. The recursive `allComments` helper gathers the set of Comment 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 these Comments. The main query `topPosts` sorts the set of Posts by score (and timestamp) and picks the top-3 Posts.

### 3.7.3 Query 2

The code for Q2 is shown in Listing 15. In particular, the `allComponents` helper implements a one-pass algorithm for the detection of all the connected components. The algorithm iterates on the liker Users: if the liker has not been visited, then compute a new component by the `allFriends` helper. 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-3 Comments are identified similarly to Q1 (Lines 1–2).
## 3.8 Xtend

### 3.8.1 Tool description

Xtend<fnref n="10" /> [13] is a modern Java dialect suited for rapid prototyping thanks to its flexibility and expressiveness. Like ATL, the vanilla Xtend does not support incremental execution.

### 3.8.2 Query 1

We have written a first batch implementation of Q1 and Q2 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 16) 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.

```java
1 def private queryQ1() {
2     return socialNetwork posts.parallelStream.collect Collector.of {
3         new Greatest3(Comparator.comparingInt {
4             if(it == null) { Integer.MIN_VALUE } else { computeScore }
5         ).thenComparing(Comparator.comparing(timestamp))
6         }
7     }, [$0.add($1)], [$0.merge($1)], [asList]).map[id].join("|")
8 }
9 def private computeScore(Post p) {
10     val comments = p.eAllContents.filter(Comment).toList
11     return comments.size*COMMENT SCORE +
12     comments.parallelStream.mapToInt(likedBy.size).sum*LIKE SCORE
13 }
```

<caption>Listing 16 Q1 in Xtend with Java Streams.</caption>

### 3.8.3 Query 2

The code of Q2 (Listing 17) 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's algorithm [84].

## 3.9 AOF and ATL incremental

### 3.9.1 Tool description

Active operations [9] are OCL-like operations equipped with incremental propagation algorithms. They may thus be used to incrementally evaluate OCL expressions [19, Section 5] such as the one found in ATL-like model transformations. It

is therefore possible to use active operations to write incremental queries and transformations.

```java
1 def private queryQ2() {
2     return socialNetwork posts
3     .map[eAllContents.filter(Comment).toList]
4     .flatten.toList.parallelStream
5     .collect Collector.of {
6         new Greatest3(Comparator.comparingInt {
7             if(it == null) { Integer.MIN_VALUE } else { computeScore }
8         }).thenComparing(Comparator.comparing(timestamp))
9         }, [$0.add($1)], [$0.merge($1)], [asList]).map[id].join("|")
10 }
11 def private computeScore(Comment c) {
12     val layering = new Layering[User u |
13         ufriends.filter[likes.contains(c)]]
14     return layering.createLayers(c.likedBy).
15     map[CSize*Size].reduce[$0+$1] ?: 0
16 }
```

<caption>Listing 17 Q2 in Xtend with Java Streams.</caption>

The AOF implementation [53] of active operations supports EMF models and is based on the Observer design pattern, although alternative execution strategies [22] have been explored. It is implemented in Java and can be used from Java, Xtend, or ATL code. Each mutable value is wrapped in an observable box, which is either a collection, or a singleton value.

Though AOF provides enough basic active operations to implement the case study, creating specific operations sometimes helps [54] achieve a better performance. For this case study, we developed four new operations:

1. sortedBy returns a sorted copy of its source collection using one or more criteria using balanced binary trees.

2. take returns the *n* first elements of a collection.

3. allContents retrieves all model elements contained in a given source element, filtering them by type.

4. layering implements an incremental connected component algorithm.

From these, layering is more specific to some graph-related transformations, and the others are relatively generic. We present two variants of this solution:

1. The AOF solution is written in Xtend, as shown in Listings 18 and 19.

2. The ATL Incremental solution is written in ATL and leverages the ATOL [23] compiler that translates it to Java code that makes use of AOF. It is basically a transliteration of the Xtend code from Listings 18 and 19 into ATL syntax. The main advantage of this variant w.r.t. the AOF variant is that it makes it possible to use the declarative ATL syntax.

### 3.9.2 Query 1

The implementation of Q1 in AOF is depicted in Listing 18. The actual computation is stored in a hash table such that it

<footnote n="10">¹⁰ https://www.eclipse.org/xtend/.</footnote>
does not have to be computed repeatedly. Within the score calculation, we use a method that iterates through the containment hierarchy in conjunction with a type filter, similar to the NMF solution. To calculate the score based on likes, we use the lifting mechanism of OCL that implicitly lifts the property likedBy to collections.

```java
1 def private queryQ1() {
2   return socialNetwork._posts
3     .sortedBy([computeScore], [_timestamp.asOne(null)])
4     .take(3).collect[id]
5 }
6 val scoreByPost = new HashMap<Post, IOne<Integer>>
7 def private computeScore(Post p) {
8   return scoreByPost.get(p) ?: {
9     val comments = p._allContents[Comment]
10    val score = comments.size * COMMENT SCORE +
11      comments.likedBy.size.sum * LIKE SCORE
12    val r = score.asOne(0)
13    scoreByPost.put(p, r)
14    r
15 } )
16 }
```

<caption>Listing 18 Q1 in Xtend using AOF.</caption>

The ATL Incremental implementation of Q1 is shown in [23, Listing 6]. It is very similar to the code from Listing 14, with the most notable difference being that the ATOL compiler does not support the query keyword.

### 3.9.3 Query 2

The solution for Q2 is depicted in Listing 19. Again, the actual score calculation is moved to a helper method. The score calculation itself is then making use of the layering operation.

```java
1 def private queryQ2() {
2   return socialNetwork._allContents[Comment]
3     .sortedBy([computeScore], [_timestamp.asOne(null)])
4     .take(3).collect[id]
5 }
6 val scoreByComment = new HashMap<Comment, IOnelestInteger>>
7 def computeScore(Comment c) {
8   return scoreByComment.get(c) ?: {
9     val s = c.likedBy[u |
10       u._friends
11     .selectMutable[f | f._likes.select[u == c].notEmpty]
12   ].collectMutable[u7.size?.square ?: emptyOne].sum
13   scoreByComment.put(c, s)
14   s
15 } )
16 }
```

<caption>Listing 19 Q2 in Xtend using AOF.</caption>

## 3.10 Neo4j Batch

### 3.10.1 Tool description

Neo4j is a graph database management system using the property graph data model. Such graphs consist of labelled entities, i.e. nodes and edges, which can be described with properties encoded as key-value pairs. Neo4j uses the Cypher query language [33] which offers both read and update constructs [37]. While the main focus of Neo4j is to run graph

queries in an online transaction processing (OLTP) setup, it also supports graph analytical algorithms with the Graph Data Science library<fnref n="11" /> [71].

```sql
1 MATCH (p:Post)
2 OPTIONAL MATCH (p)<-[:COMMENTED*]-(c:Comment)
3 OPTIONAL MATCH (c)<-[:LIKES]-(u:User)
4 RETURN p.id AS id, 10*count(DISTINCT c) + count(u) AS score,
5 p.timestamp AS timestamp
6 ORDER BY score DESC, timestamp DESC LIMIT 3
```

<caption>Listing 20 Neo4j batch implementation of Q1.</caption>

### 3.10.2 Query 1

Q1 Cypher query in Listing 20. The Cypher language uses node labels (e.g. Post, Comment, User), edge types (e.g. COMMENTED, LIKES) to express graph patterns. The query matches every node with label Post, then all its Comments via a series of COMMENTED edges, then the Users via direct LIKES edges. The OPTIONAL MATCH clause denotes an optional pattern, where variables are set to NULL values if there is no match. The RETURN clause is used to group and aggregate. The results are grouped by the id and timestamp properties of the Posts, aggregated, and then, the top-3 scores are returned. The aggregation counts the likes using the number of Users (a User can like multiple Comments) and counts the number of Comments (DISTINCT is used to remove duplicate Comments).

```sql
1 MATCH (c:Comment) WHERE (c)<-[:LIKES]-(:User)
2 CALL gds.wcc.stream({
3   nodeQuery: "MATCH (c:Comment)<-[:LIKES]-(u:User) (")
4     WHERE id(c) =" + id(c) + "
5     RETURN id(u) AS id",
6   relationshipQuery: "MATCH (u1:User)<-[:FRIEND]->(u2:User)
7     RETURN id(u1) AS source, id(u2) AS target", (*)
8   validateRelationships: false})
9 YIELD componentId
10 WITH c, componentId, count(componentId) AS componentSize(*)
11 WITH c, componentSize * componentSize AS componentSize_2
12 RETURN c.id AS id, sum(componentSize_2) AS score, c.timestamp
13 ORDER BY score DESC, c.timestamp DESC LIMIT 3(*)
14 UNION ALL
15 MATCH (c:Comment) (")
16 WHERE NOT (c)<-[:LIKES]-(:User)
17 RETURN c.id AS id, 0 AS score, c.timestamp
18 ORDER BY c.timestamp DESC LIMIT 3(*)
```

<caption>Listing 21 Neo4j batch implementation of Q2.</caption>

### 3.10.3 Query 2

Listing 21 shows the batch solution for Q2 using the variant of the union-find algorithm [68] implemented in the Neo4j Graph Data Science library. The procedure `gds.wcc.stream` is used to find connected components of the subgraph given by Cypher queries matching the nodes and the edges. For each Comment with likes, the first Cypher query in Lines 3-7 selects Users who like the Comment, and the second query selects all FRIEND edges as pairs of Users. The library loads

<footnote n="11">¹¹ https://neo4j.com/docs/graph-data-science/1.5/.</footnote>
each subgraph into an in-memory projected subgraph before running the computations. The procedure returns the ID of the component containing the User node. Lines 10–13 calculate the squared sum of the component sizes and select the top-3 scores. On Lines 15–18, the query enumerates the top-3 Comments without likes and the UNION of the two sets are returned. For a detailed comparison of strategies to compute Q2, we refer the reader to [29].

## 3.11 Neo4j incremental

### 3.11.1 Tool description

The incremental solution for Neo4j uses node properties and new nodes to materialize the result of previous iterations. For every batch of updates these elements are refreshed, then the top-3 scores are collected. While Q1 can be computed efficiently with only Cypher constructs, the solution for Q2 uses the fixed-point calculation, dynamic node manipulation and reachability procedures of Neo4j’s APOC stored procedure library.<fnref n="12" />

### 3.11.2 Query 1

To incrementally evaluate Q1, we initially compute the score for each Post as in the Neo4j Batch solution but, instead of returning it, we store it in the score property as shown in Listing 22. Based on this property, the current top-3 scores can be computed using Listing 25. The score property is indexed to improve lookup times. After new elements of an update are inserted, the score property of new Posts is initialized to zero, Listings 23-24 maintain the property for new Comment nodes and LIKES edges, and then, Listing 25 is used to get the top-3 elements.

1. MATCH (p:Post)
2. OPTIONAL MATCH (p)<-[:COMMENTED*]-(c:Comment)
3. OPTIONAL MATCH (c)<-[:LIKES]-(u:User)
4. WITH p, 10*count(DISTINCT c) + count(u) AS score
5. SET p.score = score

<caption>Listing 22 Neo4j incremental implementation of Q1 – initial evaluation.</caption>

1. WITH $commentVertex AS c
2. MATCH (p:Post)<-[:COMMENTED*]-(c:Comment)
3. SET p.score = p.score + 10

<caption>Listing 23 Neo4j incremental implementation of Q1 – maintenance after the insertion of new Comment nodes.</caption>

1. WITH $likesEdge AS l
2. MATCH (p:Post)<-[:COMMENTED*]-(:Comment)<-[:LIKES]-(:User)
3. SET p.score = p.score + 1

<figure><img src="image_11.png" /><figcaption>Fig. 6 ER diagram of the database schema</figcaption></figure>

1. MATCH (p:Post)
2. WHERE p.score >= 0 // query hint to use index
3. RETURN p.id AS id, p.score AS score, p.timestamp AS timestamp
4. ORDER BY score DESC, timestamp DESC LIMIT 3

Listing 25 Neo4j incremental implementation of Q1 – get top-3 results.

### 3.11.3 Query 2

The incremental Neo4j solution for Q2 materializes the components of the subgraph for each Comment *comm* by converting the $User \mathrel{\substack{\xrightarrow{\text{LIKES}} \\ \xleftarrow{\text{Comment}}}} \text{Comment}$ edges to a Component node and inserting two edges:

<figure><img src="image_12.png" /></figure>

where the Component node connects all Users who know each other directly or via friends who also liked the Comment *comm*. The conversion is executed for each component one by one using the fixed-point query execution mechanism of APOC. To achieve this, first the solution marks the nodes of each subgraph with dynamically named labels (Listing 41) and finds reachable nodes using the APOC library (Listing 42). The incremental evaluation is performed by merging the components then maintaining their sizes and the resulting scores (Listings 43–44).

## 3.12 PostgreSQL Batch

### 3.12.1 Tool description

To study the usability and performance of relational database management systems (RDBMSs), we implemented a batch solution in PostgreSQL. Figure 6 shows the database schema capturing the social network model. Instances of each node type (e.g. Comment) and the edge type with many-to-many cardinality (friends) are stored in relations (tables) with the following schemas:

<figure><img src="image_13.png" /></figure>

<footnote n="12">¹² https://neo4j.com/labs/apoc/.</footnote>
- comments(id, ts, content, submitterid, parentid)

- posts(id, ts, content, submitterid)

- likes(id, name)

- users(id, name)

- friends(user1id, user2id)

Each relation representing a node has a primary key. Many-to-many edges are represented in association tables with two foreign keys. Many-to-one edges are stored as a foreign key in the table representing the node at the endpoint of the edge with a cardinality of “one”. Additionally, indexes were defined on the foreign keys. This supports the SQL optimizer in choosing arbitrary join orders.

Evaluating both Q1 and Q2 require checking transitive reachability between nodes, a common recursive query which cannot be expressed in first-order logic or relational algebra [4]. However, it is possible to express such queries using a relational database by

1. either defining additional data structures and running a sequence of SQL queries in a loop until reaching a fixed point [26] or

2. or using SQL:1999's `WITH RECURSIVE` construct, which allows the formulation of recursive queries.

In this solution, we use `WITH RECURSIVE` as it is widely available in modern SQL implementations [89].

### 3.12.2 Query 1

To evaluate Q1, for each Comment, we need to first find the root Post of the Comment-chain, which is computed as the transitive closure of the Comment-parentid-Comment/Post edge type.

Having the transitive closure enables us to match the corresponding `(Post, Comment, User)` triples, where the Comment is a response rooted in the Post and the User is someone who liked the Comment. We use two left outer joins to ensure that Posts without Comments and Comments without likes are kept with NULLs. This is followed by an aggregation computing the score and finalized with a top-3 selection as shown in Listing 26.

### 3.12.3 Query 2

To evaluate Q2, we need to determine the connected components of the induced subgraphs on the User-friends-User edge type, which is computed using the transitive closure on the graph.

```
1 with recursive
2 comments_with_ancestors(id, ancestorid) as (
3   select c.id, c parentid AS ancestorid
4   from comments c
5   union
6     select cr.id, c parentid AS ancestorid
7       from comments_with_ancestors cr
8       , comments c
9     where cr.ancestorid = c.id
10  )
11 select p.id, 10*count(distinct c.id) + count(l.userid) as score
12 from posts p
13 left join comments_with_ancestors c on (p.id = c.ancestorid)
14 left join likes l on (c.id = l commentid)
15 group by p.id, p.ts
16 order by score desc, p.ts desc limit 3
```

<caption>Listing 26 Batch PostgreSQL solution for Q1.</caption>

The outline of our Q2 implementation is shown in Listing 27. (The full query is given in Listing 30.) The implementation defines interim views using four subqueries and computes the result with the final (5th) query:

1. `commentFriends(commentid, user1id, user2id)`: for a given Comment, pairs of Users who liked it and are friends.

2. `commentFriends_closed(commentid, head_userid, tail_userid)`: the transitive closure of `cf relations`, i.e. for a given Comment, all pairs of Users who are reachable from each other through friends edges.

3. `connected_components(commentid, userid, componentid)`: for a given Comment, the Users who belong to a given component of the friendship graph.

4. `comment_component_sizelands(commentid, componentid, component_size)`: for a given Comment, the component IDs and their size.

5. Finally, the resulting relation contains the top-3 Comments with the highest scores.

## 3.13 PostgreSQL incremental

To improve performance for repeated query executions, we have extended the PostgreSQL Batch solution (Sect. 3.12) with support for incremental updates. This section discusses the changes introduced in the schema and presents the queries that maintain the results upon changes.

### 3.13.1 Tool description

For the incremental solution, we have extended the database schema as shown in Fig. 7. Compared to the batch schema, this has three auxiliary relations and an extra attribute: (1) `q1_scoring` for maintaining the scores and timestamps of the Posts as defined in Q1, along with (2) `cf` and (3) `cfc` with the same semantics as in the Batch solution of Q2. The attribute (4) `comments.postid` is where Q1 maintains the root Post reference for each Comment, which is then used in Q1. Additionally, we have employed a horizontal parti-
<figure><img src="image_14.png" /><figcaption>**Fig. 7** ER diagram of the database schema, extended for incremental processing with 3 tables, 1 attribute to hold the root Post reference of the Comments and 5 status attributes added to the existing tables (highlighted in yellow boxes with dashed borders)</figcaption></figure>

tioning strategy [1] on each table. The partitioning uses an attribute status consisting of a single character “B” or “D”. During a particular update phase, rows that were already in the database are stored in the “B” (*before*) partition, while rows that have just been inserted are temporarily stored in the “D” (*diff*) partition. At the end of each update phase, rows from the *diff* partition migrate to the *before* partition. For both queries, we implemented algebraic incremental view maintenance with delta queries derived using the rules given in [38] and [81, Appendix E].

### 3.13.2 Query 1

The incremental solution for Q1 consists of three steps, each affecting the *q1_scoring* auxiliary relation, i.e. an initial step, then, for each update of the graph, a sequence of interim result maintenance and final result retrieval queries.

1. The initial step consists of two substeps:

(a) We compute the root Post reference for all Comments (Listing 31) and materialize in attribute *comments.postid*.

(b) We compute the score for all Posts (Listing 32)— similarly to the batch solution of Q1 except that we materialize each Post in relation *q1_scoring* with its timestamp and score.

2. The interim result maintenance is again split into two substeps:

(a) In preparation, we compute the root Post reference for all new Comments (Listing 33) and materialize in attribute *comments.postid*.

(b) Posts' score maintenance (Listing 34) is implemented using three subqueries, each computing the increment in score for certain types of changes:

- The *diff posts* subquery calculates the score of the new Posts. The Comments and likes of the new Posts must also be new, so the *diff* partition of all 3 relations are joined together. A left outer join is applied to include each new Post regardless of whether it has received any Comments and/or likes yet.

- The *diff comments* subquery calculates the extra score for old Posts gained by new Comments and the likes for them. This is expressed as the inner join of the *before* partition of Posts and *diff* partition of Comments. Then, a left outer join of the *diff* partition of likes is applied, as only new likes can refer to new Comments, and we need to calculate scores of all new Comments regardless of whether it received any likes.

- The *diff likes* subquery computes extra score for old Posts based for the new likes of their old Comments. This is expressed as the inner join of the *before* partition of Posts and Comments, and the *diff* partition of likes.

In each subquery, one operand of the inner join is the *diff* partition of either the *posts*, *comments* or *likes* relations. Their usually small record count can be exploited by the SQL query optimizer to speed up joins. Using the calculations above, *q1_scoring* is updated by increasing the scores of old Posts and inserting new Posts along with their scores.

The relational algebraic formula for this interim result maintenance query is given in Fig. 13 and proved in Fig. 14.

3. The retrieval step is a simple top-3 query on *q1_scoring* (Listing 35).

### 3.13.3 Query 2

Similarly to Q1, the incremental solution for Q2 again consists of three steps, i.e. an initial step, then, for each update of the graph, an alternating sequence of interim result maintenance and final result retrieval queries. Both the initial and the maintenance steps are further divided into two queries affecting the *cf* and *cfc* interim relations.

1. During the initial step, we first compute the *before* partition of the *cf* relation (Listing 36), then its closure in the *cfc* relation (Listing 38). The queries to perform this are analogous to the corresponding subqueries of the PostgreSQL Batch solution for Q2 (Listing 27).

2. The maintenance step consists of two substeps:

<figure><img src="image_15.png" /></figure>
```sql
1 WITH RECURSIVE
2 commentFriends(commentid, userid, user2id) AS (...), --1
3 commentFriends_closedown(commentid, head_userid, tail_userid) AS --2
4 SELECT 1 commentid
5 , 1.userid AS head_userid, 1 userid AS tail_userid
6 FROM likes 1
7 UNION
8 SELECT cfc commentid, cfc head_userid, f.user2id AS tail_userid
9 FROM commentFriends_closed cfc, commentFriends f
10 WHERE cfc.tail_userid = f.userlid
11 AND cfc commentid = f commentid
12 ), comment_components AS ( --3
13 SELECT commentid, head_userid AS userid
14 , min(tail_userid) AS componentid
15 FROM commentFriends_closed
16 GROUP BY commentid, head_userid
17 ), comment_component_size AS ( --4
18 SELECT cc commentid, cc.componentid, count(*) AS component_size
19 FROM comment_components cc
20 GROUP BY cc commentid, cc.componentid
21 )
22 --5 consider all comments including those without likes
23 SELECT c.id AS commentid
24 , coalesce( sum( power(ccs.component_size, 2) ), 0) AS score
25 FROM comments c
26 LEFT JOIN comment_component_size ccs ON (ccs commentid = c.id)
27 GROUP BY c.id, c.ts
28 ORDER BY sum( power(ccs.component_size, 2) ) DESC NULLS LAST
29 , c.ts DESC LIMIT 3
30 ;
```

<caption>Listing 27 Batch PostgreSQL solution snippet for Q2.</caption>

(a) Updating the *cf* relation with a union of new *commentFriends* edges induced (Listing 37). Considering the *friends.user1id* as the left side on the join, and *friends.user2id* as its right side, a new edge is included by either:

i. the new likes on the left side of all friendships with all likes on the right side,

ii. the old likes on the left side of new friendships and all likes on the right side, and

iii. old likes on the left side of old friendships and new likes on the right side.

(b) Updating the transitive closure is done in three successive subqueries (denoted as `commentFriends_closed_stage{0,1,2}` in Listing 39):

i. Each new like on a particular Comment is a new zero-length path in the closure.

ii. Instead of performing the computation on the *cf* graph, we use new edges (*commentFriends_diff*) to reach a fixed point in fewer steps.

iii. The optimization in the previous step omitted the edges in the existing transitive closure, and hence, we add these to the result as a final step.

3. The retrieval step, similarly to the PostgreSQL Batch solution for Q2, computes the component sizes, and then, the scores for all Comments are computed to retrieve the top-3 scored Comments (Listing 40).

## 3.14 GraphBLAS Batch

### 3.14.1 Tool description

GraphBLAS is a recently proposed standard built on the theoretical framework of matrix operations on semirings [57], which allows concise and portable formulation of graph algorithms [58]. The goal of GraphBLAS is to create a layer of abstraction between the graph algorithms and the graph analytics framework, separating the concerns of the algorithm developers from those of the framework developers and hardware designers. The GraphBLAS standard defines a C API [20] that can be implemented on a variety of hardware components including GPUs.

**Data format** An untyped graph can be represented as an adjacency matrix $A \in \mathbb{N}^{|V| \times |V|}$, where rows and columns both represent nodes of the graph and element $A_{ij}$ represents the number of edges from node $i$ to node $j$. If the number of edges is not important, the adjacency matrix is defined over Boolean values, i.e. $A \in \mathbb{B}^{|V| \times |V|}$, with $A_{ij} = 1$ if there is an edge from node $i$ to node $j$ and $A_{ij} = 0$ otherwise. Bipartite graphs can be represented with a non-square adjacency matrix $A \in \mathbb{N}^{|V_1| \times |V_2|}$, where $V_1$ and $V_2$ are the sets of vertices in the two partitions. Typed graphs such as the ones used in this paper can be represented as using a bipartite adjacency matrix for each edge type, where $V_1$ represents the source nodes and $V_2$ represents the target nodes, e.g. **Likes** $\in \mathbb{B}^{|users| \times |comments|}$. The graphs used in practical applications such as social networks are *sparse*. The adjacency matrices representing these graphs are also *sparse*, i.e. most elements in their adjacency matrix are zero values. These *sparse matrices* can be represented efficiently using matrix compression techniques such as CSR (Compressed Sparse Row).

A graph can also be stored as an incidence matrix $B \in \mathbb{B}^{|V| \times |E|}$, where rows and columns represent nodes and edges (resp.). For undirected graphs, each column contains two 1 values in the positions of the source and the target nodes of the edge, and other elements are 0. Incidence matrices are sparse for all graphs with more than a few nodes.

**Notation** We follow the notation conventions of GraphBLAS as presented in [25]. Table 3 contains the list of GraphBLAS operations and methods used in this paper. Matrices are typeset in **bold** and start with an uppercase letter, e.g. **Friends**. Vectors are typeset in **bold** and start with a lowercase letter, e.g. **scores**. Additionally, sets are typeset in *italic* and start with a lowercase letter, e.g. *posts*.

**Implementation** For this solution, we used SuiteSparse:GraphBLAS [25], a parallel GraphBLAS imple-
<table><caption>**Table 3** Notation of the GraphBLAS operations and methods used in this paper (based on [25])</caption><thead><tr><th>Operation/method</th><th>Name</th><th>Notation</th></tr></thead><tbody><tr><td>mxm</td><td>Matrix-matrix multiplication</td><td>C⟨M⟩ = A ⊕ . ⊗ B</td></tr><tr><td>vxm</td><td>Vector-matrix multiplication</td><td>w⟨m⟩ = u ⊕ . ⊗ A</td></tr><tr><td>mxv</td><td>Matrix-vector multiplication</td><td>w⟨m⟩ = A ⊕ . ⊗ u</td></tr><tr><td>eWiseAdd</td><td>Element-wise addition,<br>Union of patterns</td><td>C⟨M⟩ = A ⊕ B<br>w⟨m⟩ = u ⊕ v</td></tr><tr><td>eWiseMult</td><td>Element-wise multiplication,<br>Intersection of patterns</td><td>C⟨M⟩ = A ⊗ B<br>w⟨m⟩ = u ⊗ v</td></tr><tr><td>extract</td><td>Extract submatrix<br>Extract subvector</td><td>C⟨M⟩ = A(I, J)<br>w⟨m⟩ = u(I)</td></tr><tr><td>apply</td><td>Apply unary operator</td><td>C⟨M⟩ = f(A)<br>w⟨m⟩ = f(u)</td></tr><tr><td>select</td><td>Select elements<br>equal to scalar k</td><td>C⟨M⟩ = SELECT(A(i, j) == k)<br>w⟨m⟩ = SELECT(u(i) == k)</td></tr><tr><td>reduce</td><td>Reduce matrix to column vector<br>Reduce matrix to scalar</td><td>w⟨m⟩ = [⊕<sub>j</sub>A(i, j)]<br>s = [⊕<sub>i,j</sub>A(i, j)]</td></tr><tr><td>transpose</td><td>Transpose matrix</td><td>C⟨M⟩ = A<sup>T</sup></td></tr><tr><td>extractTuples</td><td>Extract (i, j, A<sub>ij</sub>) tuples<br>Extract (i, u<sub>i</sub>) tuples</td><td>{(i, j, A<sub>ij</sub>)} ← A<br>{(i, u<sub>i</sub>)} ← u</td></tr><tr><td>build</td><td>Build matrix from tuples<br>Build vector from tuples</td><td>A ← {(i, j, A<sub>ij</sub>)}<br>u ← {(i, u<sub>i</sub>)}</td></tr><tr><td>nvals</td><td>Number of non-empty elements</td><td>nvals = |A|<br>nvals = |u|</td></tr></tbody></table>

Matrices and vectors are typeset in bold, starting with uppercase (A) and lowercase (u) letters, respectively. Scalars including indices (s, i, j) are lowercase italic, while index arrays (I, J) are uppercase italic. ⊕ and ⊗ are the addition and multiplication operators of an arbitrary semiring, and masks ⟨M⟩ are used to selectively write to the result. The pattern of a matrix/vector is the position of its non-empty elements

mentation and LAGraph [64], a library of GraphBLAS algorithms. We also implemented an incremental solution in GraphBLAS, described in Sect. 3.15.

up the values. The score for each Post is the element-wise sum of the two vectors (Line 15). Figure 8a shows an example calculation.

### 3.14.2 Query 1

Q1 (Algorithm 1) computes the score for each Post, then selects the top-3 Posts. We use an auxiliary **RootPost**T adjacency matrix to denote the Post a Comment belongs to (possibly through a series of Comments). The algorithm receives direct Comments on Posts (**CommentedP**T) and Comments on other Comments (**CommentedC**T) separately. Starting from the former (Line 7), BFS is used to find child Comments level by level and collect them to the Post they belong to until there are no more left (Lines 8-10). In Line 12, the row-wise summation of **RootPost**T matrix produces the number of (direct and indirect) Comments per Post, and then, an apply operation multiplies the vector elements by 10. Line 14 sums up the number of likes the Post has via its Comments. For each Post, the **RootPost**T adjacency matrix selects the elements of the **likesCount** vector corresponding to the Comments of the Post and then sums

<table><caption>**Algorithm 1** GraphBLAS algorithm for Q1.</caption><tr><td>1:</td><td><strong>Input</strong></td><td></td></tr><tr><td>2:</td><td>CommentedP<sup>T</sup> ∈ B<sup>|posts|×|comments|</sup></td><td>▷ adjacency matrix</td></tr><tr><td>3:</td><td>CommentedC<sup>T</sup> ∈ B<sup>|comments|×|comments|</sup></td><td></td></tr><tr><td>4:</td><td>likesCount ∈ N<sup>|comments|</sup></td><td>▷ # of incoming likes</td></tr><tr><td>5:</td><td><strong>Output</strong></td><td></td></tr><tr><td>6:</td><td>scores ∈ N<sup>|posts|</sup></td><td></td></tr><tr><td>7:</td><td>RootPost<sup>T</sup> = Next = CommentedP<sup>T</sup></td><td></td></tr><tr><td>8:</td><td>while |Next| ≠ 0 do</td><td>▷ selected Comments are not empty</td></tr><tr><td>9:</td><td>Next = Next ⊕ . ⊗ CommentedC<sup>T</sup></td><td>▷ child Comments</td></tr><tr><td>10:</td><td>RootPost<sup>T</sup> = RootPost<sup>T</sup> ⊕ Next</td><td>▷ collect all Comments to the Posts they belong to</td></tr><tr><td>11:</td><td><strong>end while</strong></td><td></td></tr><tr><td>12:</td><td>sum = [⊕<sub>j</sub> RootPost<sup>T</sup>(:, j)]</td><td>▷ row-wise sum</td></tr><tr><td>13:</td><td>repliesScores = 10 ⊗ sum</td><td>▷ apply multiply-by-10 op.</td></tr><tr><td>14:</td><td>likesScores = RootPost<sup>T</sup> ⊕ . ⊗ likesCount</td><td></td></tr><tr><td>15:</td><td>scores = repliesScores ⊕ likesScores</td><td></td></tr><tr><td>16:</td><td><strong>return scores</strong></td><td></td></tr></table>
<figure><img src="image_16.png" /><figcaption>**Fig. 8** Execution of the GraphBLAS algorithms on the example graph (Fig. 5): the *Initial evaluation* step (used by both the batch and incremental solutions) and the *Update and re-evaluation* step (used by the incremental solution). Recall that the update in the example inserts</figcaption></figure>

the following relevant entities (highlighted with grey background): a friends edge between Users u1 and u4, a likes edge from User u2 to Comment c2, a Comment node c4 with a root Post of p1 and an incoming likes edge from User u4

### 3.14.3 Query 2

A batch evaluation example of Q2 (Algorithm 2) is depicted in the upper part of Fig. 8b. Q2 computes the score for each Comment and then selects the top-3 Comments. To collect the Users of each subgraph, in Lines 8 and 10, Step ① extracts the elements of the **Likes**$^T$ matrix as (c, u, 1) tuples and collects them into sets of User IDs (u) per Comment (c). To produce the subgraph for each Comment, Step ② extracts a submatrix based on the Users selected (Line 11). Step ③ finds connected components in the induced subgraph using the FastSV algorithm [88] of the LAGraph library (Line 12). This produces a vector containing the component ID for each User. Step ④ yields the squared sum of component sizes, i.e. the score for each Comment (Line 14).

**Algorithm 2** GraphBLAS algorithm for Q2.

1: **Input**
2:     comments = {1, ..., n}
3:     **Likes**$^T$ ∈ $\mathbb{B}^{\text{comments} \times |\text{users}|}$
4:     **Friends** ∈ $\mathbb{B}^{\text{users} \times |\text{users}|}$
5: **Output**
6:     scores ∈ $\mathbb{N}^{\text{comments}}$
7: **function** SCOREVECQ2
8:     likes_tuples ← **Likes**$^T$
9:     **for all** c ∈ comments **do**
10:         users_c = {u : (c, u, c) ∈ likes_tuples}
11:         **Friends**_c = **Friends**(*users*_c, *users*_c)
12:         **comp_ids** = FASTSV(**Friends**_c)
13:         scores (c) =
14:         ∑$_{k \in \text{comp_ids}} |\text{SELECT}(\text{comp_ids}(i) == k)|^2
15:     **end for**
16:     return scores
17: **end function**

## 3.15 GraphBLAS incremental

### 3.15.1 Tool description

To incrementalize the GraphBLAS Batch solution (Sect. 3.14), we have reworked the solution to compute changes to the results upon updates instead of running a full re-evaluation.

**Approach** The incremental version performs a full batch evaluation for the first run and computes the scores. Then, for each update only those parts of the model are re-evaluated which might be affected by the update. Finally, the previous top-3 scores and the new ones are compared to maintain the result. Incremental computation of Q1 uses fine-grained maintenance as it stores the scores of each Post and updates them when new Comment nodes and likes edges appear. The granularity of the incremental version of Q2 is coarser, as it collects the Comments whose scores can change and re-evaluates them.

**Notation** The updated variables are denoted with prime, e.g. the updated version of vector **scores** is **scores'**, which contains the scores for the new nodes and the updated scores for the existing ones. The changes can be stored as *incremental matrices/vectors*, denoted with a superscript plus symbol (+) and are applied with the $\oplus$ operation to the original values, e.g. **scores'** = **scores** $\oplus$ **scores」$. Another option is to store the changed values, denoted with $\Delta$, and apply them by overwriting the existing values: the new vector is initialized with the original one: **scores'** = **scores**, then the new values overwrite the existing ones via a mask, which preserves the unaffected values from modification: **scores'** $\ll \Delta$**scores**$\gg$ = $\Delta$**scores**.
### 3.15.2 Query 1

To incrementally evaluate Q1, Algorithm 3 updates the scores as follows. Lines 9 and 10 compute the increment of the score induced by new Comments. In Line 11, the number of likes the Comments newly received is summed up per Post. The two types of increments are summed up in Line 12. For subsequent evaluations, the scores are updated using the increment vector (Line 13). To find the top-3 scores, only the previous maximum values and the Posts with updated scores are considered. Line 14 yields the updated score values by assigning the scores' vector via the scores⁺ increment vector as a mask, which allows changes in the result only if the mask has an element at the corresponding position. Figure 8a shows an example calculation. Using the output of this algorithm, merging the previous top-3 scores and the new ones yields the new result.

<caption>**Algorithm 3** GraphBLAS update algorithm for Q1.</caption>

1. **Input**
2.   scores ∈ $\mathbb{N}^{|posts|}$ ▷ previous scores
3.   likesCount⁺ ∈ $\mathbb{N}^{|comments|}$ ▷ new incoming likes
4.   ΔRootPostT ∈ $\mathbb{B}^{|posts| \times |comments|}$ ▷ new root Posts<fnref n="13" />
5.   RootPostT ∈ $\mathbb{B}^{|posts| \times |comments|}$ ▷ all root Posts
6. **Output**
7.   Δscores ∈ $\mathbb{N}^{|posts|}$ ▷ only changed scores
8.   scores' ∈ $\mathbb{N}^{|posts|}$ ▷ all updated scores
9.   sum = $[\bigoplus_j \Delta RootPostT(\cdot, j)]$ ▷ # of new comments
10.  repliesScores⁺ = $10 \times \text{sum}$
11.  likesScores⁺ = $\text{RootPostT} \oplus \otimes \text{likesCount}⁺$
12.  scores⁺ = $\text{repliesScores}⁺ \oplus \text{likesScores}⁺$ ▷ increment vec.
13.  scores' = $\text{scores} \oplus \text{scores}⁺$ ▷ update scores
14.  Δscores = $\langle \text{scores}⁺ \rangle = \text{scores}'$ ▷ collect updated scores
15.  return Δscores, scores'

### 3.15.3 Query 2

The incremental evaluation of Q2 is depicted in the lower part of Fig. 8b. Algorithm 4 returns the Comments with new scores (Δscores) by re-evaluating the Comments which the updates might impact on. Merging the previous top-3 scores and the new ones yields the new result. (New scores overwrite existing ones.) The first phase of the algorithm (Steps 1–5), Lines 14–20) collects the Comments which might be affected by the updates (affected comments, acSet set), and then, the second phase (Steps 6–9, Line 21) computes the new scores of these Comments using the batch algorithm described in Algorithm 2.

A Comment might be affected by an update if (1) it is a new Comment, or (2) the Comment receives a new incoming likes edge from a User, resulting in a new component

or the expansion of an existing one, or (3) two Users who like the Comment become friends, which merges the components the Users belong to (if they previously belonged to different components). Case (3) is covered by Lines 14-18, where Steps 1–4 compute the Comments which might be affected by new friends edges. NewFriends incidence matrix represents each new friendship by a column having two 1-/valued elements for the two Users. For each new friendship (i.e. pair of Users), Step 1 computes how many User of the pair likes each Comment (0, 1, or 2). During the matrix–matrix multiplication, each column of new friendships selects two columns of $\text{Likes}'^T$ matrix and sums them up into AC matrix (Line 15). In Line 16, Step 2 keeps only 2-/valued elements, i.e. where both Users of a friendship liked the Comment, so both of them are present in the subgraph and the new friendship might merge components. Then, Step 3 produces a row-wise sum using the logical or operator $\lor$ (Line 17). Step 4 extracts $(c, 1)$ tuples from the result vector and collects the Comment IDs from these tuples, then Step 5 collects all the Comments which might be affected by the update (Line 19). Cases (1) and (2) are covered by Line 20, which produces the union of all the three cases. The next steps re-evaluate the scores of these Comments (Line 21).

<caption>**Algorithm 4** GraphBLAS update algorithm for Q2 using the SCOREVECQ2 function of Algorithm 2.</caption>

1. **Input**
2.   comments' = comments $\cup$ Δcomments
3.   Δlikes $\subseteq$ comments' $\times$ users'
4.   Δfriends $\subseteq$ users' $\times$ users' ▷ friend pairs in both orders
5.   LikesT $\in$ $\mathbb{B}^{|comments'| \times |users'|}$
6.   Friends' $\in$ $\mathbb{B}^{|users'| \times |users'|}$
7. **Output**
8.   Δscores ∈ $\mathbb{N}^{|comments|}$
9. **Data**
10.  NewFriends $\in$ $\mathbb{B}^{|users'| \times \frac{1}{2} |Ifriends|}$ ▷ incidence matrix
11.  AC $\in$ $\{0, 1, 2\}^{|comments'| \times |Ifriends|}$ ▷ affected Comments
12.  ac $\in$ $\mathbb{B}^{|comments|}$ ▷ Comments affected by new friends
13.  acSet $\subseteq$ comments' ▷ affected Comments, to reevaluate
14.  NewFriends = $\text{BUILDINDICENCE MATRIX}(\Delta friends)$
15.  AC = $\text{Lik es}^T \oplus \otimes \text{NewFriends}$ ▷ 1
16.  AC = $\text{SELECT}(AC(i, j) == 2)$ ▷ 2
17.  ac = $[\bigvee_j AC(\cdot, j)]$ ▷ 3
18.  acTuples $\leftarrow$ ac ▷ 4
19.  acSet = $\{c : (c, 1) \in acTuples\}$ ▷ 5
20.  acSet = $\Delta comments \cup \{c : (c, u) \in \Delta likes\} \cup acSet$ ▷ 5
21.  Δscores = $\text{SCOREVECQ2}(acSet, \text{Lik es}^T, \text{Friends}')$ ▷ 6–9
22.  return Δscores

<footnote n="13">¹³ Computed from previous $\text{RootPostT}$ and new commented edges.</footnote>
## 3.16 Differential dataflow

### 3.16.1 Tool description

Dataflow-based computational models were proposed to perform complex analytics on high-volume data sets: the timely dataflow [69,70] model targets batch processing, while its extension, differential dataflow [65], targets incremental processing.

We created two differential dataflow-based solutions:

**.NET-based implementation** Naiad<fnref n="14" /> is a data processing prototype system developed at Microsoft Research<fnref n="15" /> between 2011 and 2014. Naiad supports both the timely and differential dataflow computational models. The Naiad implementation was written in C#.

**Rust-based implementation** The computational models of Naiad have been implemented in the Rust programming language<fnref n="16" /> [59] as two separate projects: Timely Dataflow<fnref n="17" /> and Differential Dataflow.<fnref n="18" />

For the sake of brevity, we only discuss the Rust-based implementation here—the one using Naiad is available online but has been omitted from this paper.

**Data representation** To represent the graph, the Differential Dataflow solution uses unordered collections containing tuples with the following semantics:

* `comms`: (id, ts, content, creator, parent)

* `posts`: (id, ts, content, creator)

* `knows`: (user1, user2)

* `likes`: (user, comment)

### 3.16.2 Query 1

The implementation of Q1 (shown in Listing 28) uses the `comms`, `posts`, and `likes` collections. In Line 8, we extract the Comments and their direct parent objects, which can either be a `Post` or another `Comment`. In Lines 19–13, we determine the direct replies for each `Post`. Next, in Lines 14–25, we collect all transitive replies for each `Post` using the `iterate` operator, which executes the specified function until a stable result set is reached. In Lines 26–31, we collect the number of likes for each `Comment`, each having a cardinality of 1 (corresponding to their contribution to the

overall score). Then, in Line 32, we collect each Comment that belongs to the `Post` with a cardinality of 10 (as they are worth 10 points). Next, in Lines 33–38, we concatenate the collections containing the likes and the reply Comments and count their total cardinality. Finally, in Lines 39–41, we add the timestamps of each `Post` and get the top-3 values.

```c
1 fn query_l_G, Submission, User, Date> {
2     comms: &Collection&lt;G, (Submission, Date, String, User, Submission)&gt;,
3     posts: &Collection&lt;G, (Submission, Date, String, User)&gt;,
4     likes: &Collection&lt;G, (User, Submission)&gt;,
5     probe: &mut ProbeHandle&lt;G::Timestamp&gt;,
6 } -> TraceAgent&lt;OrdKeySpine&lt;String, G::Timestamp, isize&gt; &gt;
7 {
8     let comms = comms.map(|(id,_,_,_, parent)| (parent,
9                                 id)); (**)
10    let direct_replies = posts (**)
11        .map(|(post_id,_,_,_)| (post_id.clone(), ()))
12        .join_map(&commsello parents,
13                   |post_id, _dummy, comm_id| (post_id.clone(),
14                                                comm_id.clone())
15        ); (**)
16     let allreplies = direct_replies (**)
17     .iterate|transitive| {
18         let commsello parents = commsello parents. enter(&transitive. scope());
19         let direct_replies = direct_replies. enter(&transitive. scope());
20         return transitive
21     }
22     .map(|(post_id, comment_id)| (comment_id.clone(),
23                                 post_id.clone()))
24     .join_map(&commsello parents,
25                |_parent_comment, post_id, child_comment| (post_id.clone(),
26                child_comment.clone())
27         )
28     .concat(&direct_replies)
29     .distinct();
30 };
31
32 let likedcomments = likes (**)
33     .map(|(_user,comm)| (comm, ()))
34     .join_map(
35         &allreplies.map(|(post_id, comment_id)| (comment_id,
36                                     post_id)),
37     )
38
39 let post score = posts (**)
40     .map| (post | post.0) // ensure all posts get a score
41     .concat(&likedcomments) // likes contribute to posts
42     .concat(&comms_themselves) // comments contribute to posts
43     .count()
44     .join(&posts.map| (post | (post.0, post.1.clone())); (**)
45
46 let arrangement = limit(&post_score, 3) (**)
47     .map| [vec | format!("{}|{}|{}", vec[0], vec[1], vec[2])]
48     .arrange_by self(); (**)
49
50 arrangement.stream.probe_with(probe);
51
52 return arrangement.trace;
53 }
```

<caption>Listing 28 Differential Dataflow implementation of Q1.</caption>

### 3.16.3 Query 2

The implementation of Q2 (shown in Listing 29) uses the `comms`, `knows` and `likes` collections. First, in Lines 8–25, we use iterative label propagation to find connected components. Initially, we add the labels based on the `likes` edges and then propagate them across the `knows` edges. When the propagation reaches its fixed point, we will have a list of (user, label, comment) tuples, where each tuple shows that the given User is part of the connected component of the given Comment, and the smallest User id in this connected is the label. Then, in Lines 26–35, we aggregate the labels to get the size of each connected component and get the final score

<footnote n="14">14 https://github.com/TimelyDataflow/Naiad</footnote>

<footnote n="15">15 https://www.microsoft.com/en-us/research/project/naiad/</footnote>

<footnote n="16">16 https://www.rust-lang.org/</footnote>

<footnote n="17">17 https://github.com/TimelyDataflow/timely-dataflow.</footnote>

<footnote n="18">18 https://github.com/TimelyDataflow/differential-dataflow.</footnote>
by summing the squared component sizes. Finally, we add
the timestamps of each Comment and get the top-3 values.

1 fn query_2<6, Submission, User, Date>(
2     comms: &Collection<6, (Submission, Date, String, User, Submission)
3
4     knows: &Collection<6, (User, User)
5     likes: &Collection<6, (User, Submission)
6 ) -> TraceAgent<OrdKeySpine< String, G::Timestamp, isize>>
7 {
8     let labels: Collection_<, ((User, Submission), User)> = (**)
9     likes
10     .filter(|_| false)
11     .map(|(user, comm)| ((user.clone(), comm), user))
12     .iterate(|labels| {
13         let knows = knows enter(&labels scope());
14         let likes = likes enter(&labels scope());
15     labels
16     .map(|((node, comment), label)| (node, (label, comment)))
17     .join_map(&knows, _node, (label, comment), dest|
18                 ((dest.clone(), comment.clone()),
19                 label.clone()))
19     .concat(&likes.map(|(user, comm)| ((user.clone(), comm),
20                                     user.clone()))
21     .reduce(|_key, input, output| {
22         // only produce output, if 'input' contains '__key.0'
23         if input .iter() .any(|(label, _wtg) | *label == __key.0) {
24             output.push((input[0].0.clone(), 1));
25         }
26     )
27     ); (**)
28 let comm_score = labels (**)
29     .map(|(( _node, comment), label)| (label, comment))
30     .count()
31     . explode |(( _label, comment), count)| Some((comment, count *
32         count))
33     .concat(&comms.map |(comm| comm.0.clone()))
34     .count()
35     .join(&comms.map |(comm| (comm.0.clone(), comm.1.clone())));
36 let arrangement = limit(&comm_score, 3)
37     .map |(vec| format!("{!} {!} {!}", vec[0], vec[1], vec[2]))
38     .arrange_by self(); (**)
39 arrangement .stream .probe_with (probe);
40 return arrangement.trace;
41 }

<caption>Listing 29 Differential Dataflow implementation of Q2.</caption>

4 Classification

In this section, we compare the solutions according to
our predefined classification criteria, evaluating general tool
properties as well as case-specific applications of them.
Aligned with the research questions, we used the following
classification criteria:

**Declarative query language** To aid the development of the solutions using the respective tools, it is helpful for the tool to adhere to a standard declarative query language.

**Data model** For a usage integrated into a modelling tool set, ideally model query tools should be able to use models created and maintained in a modelling environment as they are, without adapters.

**Explicitness of incrementalization** Ideally, tools are able to incrementalize the query in an implicit manner, i.e. the developer only has to specify the query, but not how changes are propagated or how the query is broken down

into chunks. This criterion does not apply to batch solu-
tions, i.e. ones that recalculate the query from scratch
after each model change.

**Persistence** To enable a failsafe operation, it is a desirable property for an analysis tool to continue the analysis even if the process is unexpectedly shut down. For this, data structures to save intermediate results have to be persisted, which is why we call this category query persistence. Further, in order to process models beyond the size of the main memory, it is desirable to persist the models in a database such that solutions do not have to have all model elements in memory. We refer to this as model persistence.

**Parallelism** As modern CPUs have multiple cores, it is desirable for a query technology to be able to make use of these resources by running parts of the query or its incremental change propagation in parallel.

**Asymptotic complexity to propagate changes** We present an estimated asymptotic complexity of the steps required to propagate changes. For this, we consider the necessary steps to propagate changes to both queries for all of the five possible changes (Sect. 2.3). The derived complexity values are specific to the particular scenario of the Social Media benchmark and thus should not be interpreted as a generic characterization of the tools.

In the following sections, we discuss the criteria for each
of the solutions individually and summarize the results after-
wards in Table 4, except for the asymptotic complexities that
are depicted in Tables 5 and 6.

4.1 Declarative query language

NMF makes use of the SQO (Standard Query Operators), which is a common standard on the .NET platform. Similarly, the Xtend solution uses the standard collection operators of Java. ATL uses (a slightly adapted version of) OCL. The SQL and Neo4j solutions use the standard query languages of these databases: SQL:1999 and Cypher.

EOL used by Hawk is standard in Epsilon, but the com-
munity of Epsilon is much smaller than the community of
relational databases, .NET or Neo4j.

AOF and YAMTL have their tool-specific query languages which are declarative (both solutions can be executed incrementally from the query specification) but not yet standards.

JastAdd uses its own language to specify synthesized and
inherited attributes with tool-specific extensions like circular
rules.
<table><caption>**Table 4** Comparison of the tools used in the paper</caption><thead><tr><th>Tool</th><th>Version</th><th>Data model</th><th>Engine</th><th>Solution</th><th>Decl.</th><th>Batch</th><th>Implicit</th><th>Explicit</th><th>DB</th><th>MV</th><th>Parallel</th></tr></thead><tbody><tr><td>AOF</td><td>v201806</td><td>EMF</td><td>Java 8</td><td> Xtend</td><td> ⊘</td><td>○</td><td>⊗</td><td>○</td><td>○</td><td>○</td><td>○</td></tr><tr><td>ATL</td><td>3.8.0</td><td>EMF</td><td>Java 8</td><td> ATL</td><td> ⊗</td><td>⊗</td><td>○</td><td>○</td><td>○</td><td>○</td><td>○</td></tr><tr><td>ATL Incremental</td><td>v201904</td><td>EMF</td><td> Xtend</td><td> ATL/AOF</td><td> ⊗</td><td>○</td><td>⊗</td><td>○</td><td>○</td><td>○</td><td>○</td></tr><tr><td>Differential Dataflow</td><td>0.11.0</td><td>relations</td><td>Rust</td><td>Rust</td><td>○</td><td>○</td><td>⊗</td><td>○</td><td>○</td><td>○</td><td>⊗</td></tr><tr><td>GraphBLAS</td><td>4.0.3</td><td>matrices</td><td>C</td><td>C++</td><td>○</td><td>⊗</td><td>○</td><td>⊗</td><td>○</td><td>○</td><td>⊗</td></tr><tr><td>Hawk</td><td>2.1.0</td><td>EMF</td><td>Java 8</td><td> EOL</td><td> ⊘</td><td>⊗</td><td> ⊘</td><td> ⊘</td><td> ⊘</td><td> ⊘</td><td>○</td></tr><tr><td>JastAdd</td><td>2.3.5</td><td>EMF</td><td>Java 11</td><td> Java 11</td><td>○</td><td>⊗</td><td>⊗</td><td>○</td><td>○</td><td>○</td><td>○</td></tr><tr><td>Neo4j</td><td>4.2.4</td><td>property graph</td><td> Java 11</td><td> Java 11</td><td> ⊗</td><td>⊗</td><td>○</td><td>⊗</td><td>⊗</td><td>⊗</td><td>○</td></tr><tr><td>NMF</td><td>2.0.169</td><td>NMF</td><td>C#</td><td>C#</td><td> ⊗</td><td>⊗</td><td>⊗</td><td>○</td><td>○</td><td>○</td><td>⊗</td></tr><tr><td>PostgreSQL</td><td>12.4</td><td>relations</td><td>C</td><td> Java 11/SQL</td><td> ⊗</td><td>⊗</td><td>○</td><td>⊗</td><td>⊗</td><td>⊗</td><td>○</td></tr><tr><td>Xtend</td><td>2.20.0</td><td>EMF</td><td>Java 8</td><td> Xtend</td><td> ⊗</td><td>⊗</td><td>○</td><td>○</td><td>○</td><td>○</td><td>⊗</td></tr><tr><td>YAMTL</td><td>0.1.5</td><td>EMF</td><td> Java 11</td><td> Xtend</td><td> ⊘</td><td>⊗</td><td>⊗</td><td>⊗</td><td>○</td><td>○</td><td>○</td></tr></tbody></table>

*Data Model:* the data model exposed to the user. *Engine:* programming language used to implement the engine (model transformation engine, database query engine, etc.), *Solution:* programming language and query language (if applicable) used to implement the solution, *Decl.*: the solution specified the queries using a declarative query language, *Batch:* only batch mode is supported, *Implicit:* implicit incrementalization is supported, *Explicit:* a solution with explicit incrementalization was implemented, *DB:* database-backed, i.e. the tool persists the model on disk after each transaction, *MV:* materialized views, *Parallel:* parallelization is supported. *Notation*—⊗ yes; ⊘ to some extent; ○ no; ⊗ yes, using Java 8 streams

<table><caption>**Table 5** Asymptotic complexities to propagate a model update for Q1 in selected solutions</caption><thead><tr><th>Solution</th><th>Add User</th><th>Add Post</th><th>Add Comment</th><th>Add like</th><th>Add friendship</th></tr></thead><tbody><tr><td>NMF reference (batch)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td></tr><tr><td>ATL (batch)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td></tr><tr><td>Xtend</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td><td>Θ(p log p + c)</td></tr><tr><td>PostgreSQL (batch)</td><td>Ω((p + c) log cl + l)</td><td>Ω((p + c) log cl + l)</td><td>Ω((p + c) log cl + l)</td><td>Ω((p + c) log cl + l)</td><td>Ω((p + c) log cl + l)</td></tr><tr><td>YAMTL-B (batch)</td><td>Θ(p + c)</td><td>Θ(p + c)</td><td>Θ(p + c)</td><td>Θ(p + c)</td><td>Θ(p + c)</td></tr><tr><td>NMF</td><td>O(1)</td><td>O(log p)</td><td>O(h + log p)</td><td>O(h + log p)</td><td>O(1)</td></tr><tr><td>Hawk (IU)</td><td>O(n)</td><td>O(n)</td><td>O(n + p log p)</td><td>O(n + p log p)</td><td>O(n)</td></tr><tr><td>JastAdd</td><td>Θ(p)</td><td>Θ(p)</td><td>O(p + n)</td><td>O(p + n)</td><td>Θ(p)</td></tr><tr><td>AOF</td><td>O(1)</td><td>O(log p)</td><td>O(h + log p)</td><td>O(h + log p)</td><td>O(1)</td></tr><tr><td>ATL (incremental)</td><td>O(1)</td><td>O(log p)</td><td>O(h + log p)</td><td>O(h + log p)</td><td>O(1)</td></tr><tr><td>Differential Dataflow</td><td>O(1)</td><td>O(log p)</td><td>O(h + log p)</td><td>O(log p)</td><td>O(1)</td></tr><tr><td>YAMTL-II (incremental)</td><td>O(1)</td><td>O(1)</td><td>O(n)</td><td>O(n)</td><td>O(1)</td></tr><tr><td>Hawk (IUQ)</td><td>O(n)</td><td>O(n)</td><td>O(n + p log p)</td><td>O(n + p log p)</td><td>O(n)</td></tr><tr><td>PostgreSQL (incremental)</td><td>O(1)</td><td>Θ(log p)</td><td>Θ(log p + log c)</td><td>Θ(log p log c)</td><td>O(1)</td></tr><tr><td>Neo4j (incremental)</td><td>O(log u)</td><td>O(log p)</td><td>O(h + log p + log c)</td><td>O(h + log puc)</td><td>O(log u)</td></tr><tr><td>YAMTL-EI (incremental)</td><td>O(1)</td><td>O(1)</td><td>O(1)</td><td>O(1)</td><td>O(1)</td></tr></tbody></table>

The solutions are categorized as *batch*, *implicit incrementalized* and *explicit incrementalized*

## 4.2 Data model

Given that the benchmark was originally presented at the TTC, it is not surprising that most solutions can operate directly on EMF models.

NMF uses its own metamodel NMeta but includes a transformation from Ecore and uses the same serialization format [45].

For JastAdd, it is necessary to reformulate the metamodel as grammar.

The solutions for Differential Dataflow, Neo4j, GraphBLAS and PostgreSQL do not operate on models directly but require dedicated adapters to feed the data from models into their input formats (CSV files).
<table><caption>**Table 6** Asymptotic complexities to propagate a model update for Q2 in selected solutions</caption><thead><tr><th>Solution</th><th>Add User</th><th>Add Post</th><th>Add Comment</th><th>Add like</th><th>Add friendship</th></tr></thead><tbody><tr><td>NMF reference (batch)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td></tr><tr><td>ATL (batch)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td></tr><tr><td>Xtend</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td><td>O(l · f + c log c)</td></tr><tr><td>PostgreSQL (batch)</td><td>Ω(l · log lf + l)</td><td>Ω(l · log lf + l)</td><td>Ω(l · log lf + l)</td><td>Ω(l · log lf + l)</td><td>Ω(l · log lf + l)</td></tr><tr><td>YAMTL-B (batch)</td><td>O(l · f · α(l) + c)</td><td>O(l · f · α(l) + c)</td><td>O(l · f · α(l) + c)</td><td>O(l · f · α(l) + c)</td><td>O(l · f · α(l) + c)</td></tr><tr><td>NMF incremental</td><td>O(1)</td><td>O(1)</td><td>O(log c)</td><td>O(f<sup>2</sup> + log c)</td><td>O(l · f + c log c)</td></tr><tr><td>Hawk (IU)</td><td>O(c log c)</td><td>O(c log c)</td><td>O(c log c)</td><td>O(f<sup>2</sup> + c log c)</td><td>O(l · f + c log c)</td></tr><tr><td>JastAdd</td><td>Θ(c)</td><td>Θ(c)</td><td>Θ(c)</td><td>O(c + f<sup>2</sup>)</td><td>O(l · f)</td></tr><tr><td>AOF</td><td>O(1)</td><td>O(1)</td><td>O(log c)</td><td>O(f<sup>2</sup> + log c)</td><td>O(l · f + c log c)</td></tr><tr><td>ATL (incremental)</td><td>O(1)</td><td>O(1)</td><td>O(log c)</td><td>O(f<sup>2</sup> + log c)</td><td>O(l · f + c log c)</td></tr><tr><td>Differential Dataflow</td><td>O(1)</td><td>O(1)</td><td>O(log c)</td><td>O(f<sup>2</sup> + log c)</td><td>O(l · f + c log c)</td></tr><tr><td>YAMTL-II (incremental)</td><td>O(1)</td><td>O(1)</td><td>O(1)</td><td>O(l · f · α(l))</td><td>O(l · f · α(l))</td></tr><tr><td>Hawk (IUQ)</td><td>O(1)</td><td>O(1)</td><td>O(1)</td><td>O(f<sup>2</sup>)</td><td>O(l · f)</td></tr><tr><td>PostgreSQL (incremental)</td><td>Ω(l · f)</td><td>Ω(l · f)</td><td>Ω(l · f)</td><td>Ω(l · f + c<sup>2</sup> f<sup>2</sup>)</td><td>Ω(l · f + c<sup>2</sup> f<sup>2</sup>)</td></tr><tr><td>Neo4j (incremental)</td><td>O(log u)</td><td>O(log p)</td><td>O(log c)</td><td>O(u · f + log c)</td><td>O(c<sup>2</sup>)</td></tr><tr><td>YAMTL-EI (incremental)</td><td>O(1)</td><td>O(1)</td><td>O(1)</td><td>O(f · α(l))</td><td>O(α(l))</td></tr></tbody></table>

The solutions are categorized as *batch*, *implicit incrementalized* and *explicit incrementalized*.

## 4.3 Explicitness of incrementalization

The NMF reference solution, the ATL solution, the Xtend solution and the batch versions of SQL, Neo4j and Graph-BLAS solutions are not incremental.

The incrementalization in the incremental NMF solution and in the AOF solution is implicit: the framework deducts a dependency graph from a model of the code that is available at runtime. This dependency graph is at the level of individual operations, so that only those operations really affected by a change need to be re-computed. However, these frameworks require data structures that explicitly support incrementalization. Both NMF and AOF already contain support for a wide range of common operations and allow Users to add new algorithms and data structures when needed, such as for calculating the connected components in Q2.

In the Hawk solutions, there are two aspects to incrementalization: the way that the persistent graph is updated and the way that the query is run. The batch solution uses derived attributes to cache the scores of Comments and Posts, which are implicitly updated incrementally if the nodes used to compute them change: however, the queries run in batch mode, and every change in the social network requires a full re-serialization to disk before the indexing process can update the graph. The incremental update solution uses the same approach for querying, but it does not re- serialize the social network model: instead, it applies the change sequences directly to the internal graph used for querying. The incremental update and query solution uses an explicitly

incrementalized version of the query, using graph listeners to trigger the rescoring of Comments and Posts, and uses the same approach to directly update the underlying graph database from the NMF change sequences.

JastAdd and YAMTL support a completely implicit incrementalization by tracking all read operations to the model from which a dependency graph is set up. If the result of a rule depends on a read operation that is invalidated due to model changes, this attribute instance (JastAdd) or rule instance (YAMTL) is executed again. Therefore, the granularity of the incrementalization is given by the granularity of the attributes/rules.<fnref n="19" />

In the incremental versions of the SQL, Neo4j and Graph-BLAS solutions, the incrementality is achieved explicitly. That is, these solutions all keep the scores of Posts or Comments through a table, additional nodes or vectors, respectively. Then, the solutions use explicit algorithms developed for the respective tool to update the scores in case of model updates.

In case of the SQL solution, this effort to explicitly reengineer existing queries for incremental change propagation is guided [38,81]. Such guidance can help the developer incrementalize a given query and could be automated when sufficient tooling becomes available.

The Differential Dataflow solution works similar to NMF and AOF. However, the notion of time during the calculation of the query allows this tools to support temporary state,

<footnote n="19">¹⁹ YAMTL can also expose model updates affecting a rule instance so that these can be explicitly handled with fine-grained incrementality.</footnote>
in particular the *iterate* call in Listing 29. This temporary state allows to support also more complex cases such as computing *connected components* in Q2 using only built-in algorithms and data structures [70].

In total, we have nine non-incremental solutions. PostgreSQL, Neo4j, YAMTL-EI and GraphBLAS are explicitly incrementalized, so developers have to approach the problem conceptually differently than in the batch solution. Hawk provides slight implicit incrementalization capabilities, but much of the solution must be provided by the developer in order to get the solution incremental; therefore, we categorized it as an explicit incremental tool. In NMF, JastAdd, AOF, YAMTL-II, Incremental ATL Incremental and Differential Dataflow, the incrementalization happens entirely implicitly, though partially with restrictions. Namely, JastAdd and YAMTL require the developer to adapt to their programming model, whereas NMF and AOF restrict the used operations to those that are supported in the framework, even if this set is extensible. Differential Dataflow does not have such restrictions.

## 4.4 Persistence

Most of the presented solutions keep the data only in memory without any features for fault-tolerance. This means that the solutions require a separate tooling to ensure a failsafe operation.

The exceptions to this are Hawk, Neo4j and PostgreSQL, which make use of database systems internally and are therefore durable, in the sense that models and intermediate query results for their incremental variants are available even if the application gets terminated unexpectedly.

For many of the other tools, model persistence could be achieved through persistence systems such as Eclipse CDO.<fnref n="20" /> However, although the model sizes used in the scope of the benchmark went up to a few million model elements and connections, solutions were always able to handle the models in main memory. Therefore, the need for solutions with model persistence to hit the disk for an update led to performance penalties in comparison with other solutions.

The advantage that Hawk and the incremental versions of Neo4j and PostgreSQL take out of the persistence of the intermediate results is that after a restart, they do not require the performance penalty of an initial run again and can process updates straight away after a restart. The exception to that is the incremental update and query solution for Hawk, since this keeps an in-memory list of the top-3 elements.

## 4.5 Parallelism

Since GraphBLAS is based on matrix operations, it is well suited for parallel processing. Differential Dataflow also supports executing the query in parallel. The Xtend solution makes use of the Java streams feature to enable parallelism, but only on a task level, i.e. the solution runs different parts of the query in a pipeline.

NMF also has some built-in support for parallelism, but it is restricted only to the incremental change propagation. The initial query execution does not profit from the parallel execution.

The other solutions do not make use of parallelism.

## 4.6 Asymptotic complexity to propagate changes

Recall that in Sect. 2.3, the following change operations were presented: (1) a new User is added, (2) a new Post is added, (3) a new Comment is added to an existing Post, (4) a Comment is liked, and (5) two existing Users become friends.

In the remainder of this section, we denote the number of Users in a model with *u*, the number of Posts with *p*, the number of Comments with *c* and the number of likes with *l*. A Post may have up to *n* Comments including transitive replies. The maximum hierarchy depth of Comments is denoted by *h*. A group of Users that like the same Comment and are connected through friendships has the maximum size *f*.

### 4.6.1 NMF Batch, Xtend, ATL

The NMF reference solution and the ATL solution are batch implementations where all changes result in a complete recalculation of the analysis. For Q1, calculating the scores of each Post takes $\Theta(p + c)$ time, plus $\Theta(p \log p)$ for the sorting. This amounts to $\Theta(p \log p + c)$. For Q2, Tarjan's algorithm or a similar algorithm to obtain connected components is executed for each Comment. Tarjan's algorithm has a linear complexity in both nodes and edges where there are at most $f^2$ edges, leading to a complexity of $O(c \cdot f^2)$. However, because Users only need to be considered for Comments they have liked and every like corresponds to exactly one node in the induced graph for the liked Comment, this can be reduced to $O(l \cdot f)$. Together with $O(c \log c)$ for sorting the Comments, this leads to $O(l \cdot f + c \log c)$ for Q2. For Xtend, the sorting step is avoided by a dedicated stream operator in both queries. Furthermore, the usage of streams in the Xtend solution theoretically allows to calculate the scores of the individual Comments or Posts in parallel.

<footnote n="20">²⁰ https://www.eclipse.org/cdo/.</footnote>
### 4.6.2 NMF incremental, AOF, ATL incremental, differential dataflow

In the incremental NMF solution as well as in the AOF, incremental ATL and Differential Dataflow solutions, the analysis is slightly more complex. Adding a new User does not touch the dependency graph for Q1, and thus, the effort for change propagation is constant, same for the change that two Users become friends. When a new Post is added, it does not have any Comments, but has to be inserted in the binary search tree of Posts. This has an effort of $O(\log p)$. Adding a new Comment will ripple through the Descendants or AllInstances operation and cause an effort of $O(h)$, followed by $\Theta(\log p)$ to update the position of the Post in the binary search tree. When a Comment is liked, this only causes constant effort to update the sum, but $O(h)$ to find the corresponding Post and $\Theta(\log p)$ to update the position in the search tree.

For Q2, the insertion of a new User does not touch the dependency graph because the new User does not have friends and has not liked any Comments yet. Similarly, the insertion of a Post only causes constant effort to the change propagation. The insertion of a Comment only requires to calculate connected components of an empty graph (the Comment is not liked, yet) and inserting it into the binary search tree, which takes $O(\log c)$. Liking a Comment requires to re-compute the connected components for this Comment and updating the score in the search tree, which is $O(f^2+\log c)$ since the connected components are computed from scratch. If two Users become friends, this potentially changes the subgraphs for all Comments, which has a complexity of $O(l \cdot f+c \log c)$ just as if we were to recalculate the entire query, though in the average case, many new friendships will likely not affect all Comments.

The parallel execution of NMF and Differential Dataflow does not change the complexity to perform a change, and it is rather used to propagate the changes within the transaction in parallel.

### 4.6.3 Hawk

In Hawk, the batch update process needs to check the entire model for changes, which clearly is $\Omega(p+c+u \cdot f)$. For incremental updates, the time to perform the graph updates is constant. However, in both cases, the indices need to be re-computed. For Q1, this takes $\Theta(n)$ time plus $O(p \log p)$ for sorting the Posts as soon as the score for a Post needs to be re-computed, i.e. when adding or liking a Comment. The incremental query eliminates the sorting step, explicitly taking advantage of the monotony of the scores in this scenario.

For Q2, similarly to the incremental NMF and AOF solutions, the insertion of a User or a Post does not have any effect

because they do not invalidate the score of any Comment. However, the solution still requires the sorting, which takes $O(c \log c)$, unless the solution is run in the incremental query mode (in which case the sorting is replaced by constant effort, using the monotony of the scores). If a Comment is liked, the calculation of connected components is invalidated and recalculated for this Comment, which takes $O(f^2)$. A new friendship requires the score of all Comments to be re-evaluated, which is complexity of $O(l \cdot f)$.

### 4.6.4 JastAdd

JastAdd tracks accesses to model elements when an attribute (score) of a model element is computed and uses this to invalidate these attributes upon a model change. However, the maximum always has to be computed. Adding a new User or two Users becoming friends in Q1 (changes that do not affect any model feature used in computing the scores) has a complexity of $\Theta(p)$. This complexity also dominates the score calculation for a new Post (without Comments). Adding or liking a Comment will invalidate the score for the Post and cause JastAdd to re-compute the score for this Post, which requires a complexity of $O(n)$ in addition to the $\Theta(p)$.

For Q2, finding the maximum takes $\Theta(c)$ and for inserting a User or Post, that is the overall complexity because the new User or Post is not being read in any score calculation. A new Comment only requires to calculate the score for that Comment in addition, which takes only constant effort. Liking a Comment will invalidate the score for this Comment, which again takes $O(f^2)$ and a new friendship takes $O(l \cdot f)$ as this friendship may affect the score for many Comments.

### 4.6.5 YAMTL

In the YAMTL solutions, only the three best candidates are retained and this simplifies the sorting step, which becomes constant. Discarding a candidate has constant time, and when the candidate is valid, it takes up to two comparisons to update the list.

In Q1, YAMTL-B calculates the scores by traversing all Posts and then all of their Comments, $O(p+c)$. When adding Comments or likes, YAMTL-II re-computes the score for each matched Post affected by a change, traversing all of its contained Comments, $O(n)$. Instead, YAMTL-EI only processes the new Comment that has been added to the Post or that has been liked by another User for each impacted Post, so the update is $O(1)$ in those cases.

In Q2, for each Comment, Sedgewick and Wayne's weighted quick union find with path compression initializes components in linear time, $O(l \cdot f)$, where the initial size of components is given by $l$. Find and union operations have an amortized cost that corresponds to the inverse of Ackermann's function, $O(\alpha(l))$. YAMTL solu-
tions match Comments instead of Posts in Q2. For comput-
ing a Comment score, YAMTL’s solution applies the union
operation for any friend that has liked the Comment, so
processing each Comment involves $O(l \cdot f \cdot \alpha(l))$. In propa-
gation mode, YAMTL-B initializes the data structures for the
weighted quick union find with path compression for Users $l$
in each Comment, and the cost is $O(l \cdot f \cdot \alpha(l)+c)$. YAMTL-
II visits the Comments affected by changes and initializes
the connected components of friends from scratch, so the
cost is $O(l \cdot f \cdot \alpha(l))$ when adding a like and when adding a
friendship. YAMTL-EI is sensitive to finer changes, adding
a like by a new User triggers the update of connected com-
ponents with the friends $f$ of the new User, $O(f \cdot \alpha(l))$,
whereas a new friendship only involves computing the union
of two components, $O(\alpha(l))$.

4.6.6 PostgreSQL batch

Compared to solutions working on object models, an RDBMS
has the problem that references to other models are not
directly available as object references but usually lead to
an indirect reference that must be resolved using an index.
The choice of this index and also the exact query strategy
is generally specific to the RDBMS and may differ from our
estimation here. In the remainder, we assume search trees are
used that resolve such a reference in log time. This allows
to manage data beyond main memory limitations but is of
course slower than following a direct reference.

For Q1, the root Post reference for each Comment is computed first in $\Omega(c \cdot \log c)$, which stands for the cost of the first self-join of Comments when computing the transitive closure. Then Posts are outer joined with their Comments in $\Omega(p \cdot \log c + p + c)$ steps to produce an interim result size proportional to $p + c$, which is then outer joined with their likes in $\Omega((p + c) \cdot \log l + p + c + l)$ and the count of likes has to be computed in $\Omega(l)$ steps. In-memory solutions, by contrast, can easily read the count as it is usually directly available for array list implementations of collections. Thus, the batch implementation has a complexity of $\Omega(c \cdot \log c + p \cdot \log c + (p + c) \cdot \log l + p + c + l)$, which can be further simplified to $\Omega((p + c) \cdot \log c + l)$.<fnref n="21" />

In Q2, we first compute the transitive closure of the friend-
ship subgraphs<fnref n="22" /> in $\Omega(l \cdot \log l f l + l + f + l)$, which stands
for the cost of the first recursive step. The size of the transi-
tive closure is $\Omega(l)$, which is fed as input to the subsequent
aggregations that can be done in linear time w.r.t. their input
size. The result of the aggregations has again a size of $\Omega(l)$,

and as it exists only in memory, no index is available. Thus,
the final join to Comments is assumed to be done using
hash join with a complexity of $\Omega(c + l)$. Summing up
the former gives the batch implementation a complexity of
$\Omega(l \cdot \log l f l + l + f + l + l + c + l)$, which can be simplified
to $\Omega(l \cdot \log l f + l)$.<fnref n="23" />

4.6.7 PostgreSQL incremental

For Q1, any score update of a Post in the incremental SQL
solution yields a complexity of $\Theta(\log p)$. However, adding a
new User or friendship does not cause a score update and has
therefore constant effort. Apart from that, adding a Post only
requires to left join an empty table with constant effort and
migrating the Post to the new partition, which we assume is
constant effort. Adding a Comment requires to resolve its
Post with a complexity of $\Theta(\log p + \log c)$, adding a like
causes $\Theta(\log p \cdot \log c)$. For Q2, the result-retrieval is non-
trivial even in the presence of an index and has an effort of
$\Omega(l \cdot f)$. Adding a User, Post or Comment changes neither
friends nor likes relations, which is why all join operations
to update the commentFriends relation in stages 0 and 1
inner join an empty table and thus become constant in the
maintenance phase. Computing stage 2 and inserting into
the commentFriends relation require to process all $O(c^2 f^2)$
entries of stage 2. Liking a Comment or a new friendships
adds an overhead to the computation of stage 1 and stage 2
(possibly recursively), but we assume this effort to be domi-
nated by $O(c^2 f^2)$.

4.6.8 Neo4j incremental

The Neo4j solution saves the score as a property on Post
and Comment nodes and indexes these properties using
B-trees.<fnref n="24" /> For Q1, this implies that inserting a new Post
necessitates a cost of $O(\log p)$ (maintaining the index on
the score property). Adding a Comment or a like can result
in an increase of the score of the root Post, which costs $O(h)$
for finding the Post and $O(\log p)$ to update the score. For
Q2, the incremental solution materializes each Comment's
connected components which need to be maintained upon
inserting a new likes edge. The non-trivial operations are
as follows. When a Comment is initially inserted, it has
a score of 0. Maintaining the index on the score property
incurs a cost of $O(\log c)$. When a User usr adds a new
like to Comment cmt, the solution merges all connected
components of cmt containing friends of usr with a cost of
$O(u \cdot f)$. Additionally, maintaining the index on the score

<footnote n="21">²¹ This assumes an optimal query execution under the assumption that $p < c$ and $p < l$.</footnote>

<footnote n="22">²² In Listing 30, this is composed of two subqueries for clarity, i.e. commentFriends and commentFriends_closed, but we assume the former is inlined for execution.</footnote>

<footnote n="23">²³ This assumes an optimal query execution under the assumption that $f < l$ and $c < l$.</footnote>

<footnote n="24">²⁴ https://neo4j.com/docs/operations-manual/4.1/performance/index-configuration/.</footnote>
property of the Comments has $O(\log c)$ cost. Finally, adding a new friends edge necessitates checking which components of which Comments can be merged, incurring a cost of $O(c^2)$ and maintaining the index for cost $O(\log c)$.

Apart from this, since Neo4j indexes store identifiers of nodes in search trees and checks uniqueness constraints, adding a User requires an effort of $\Theta(\log u)$, adding a Post $\Theta(\log p)$ and adding a Comment $\Theta(\log c)$. Liking a Comment requires at least $\Theta(\log u + \log c)$ and Users becoming friends at least $\Theta(\log u)$ cost.

### 4.6.9 GraphBLAS

For GraphBLAS, stating algorithmic complexities for query calculation is difficult because the engine automatically chooses from a variety of algorithms for matrix multiplication given that the matrices are usually very sparse. For example, the adjacency matrix to calculate the Comments of a root Post in the Q1 batch version is sparse because Comments only belong to one root Post. A naïve implementation of calculating this sum would therefore take an effort of $O(p \cdot c)$, but this analysis does not take into account the optimizations that GraphBLAS applies to this computation. Therefore, we do not provide results for asymptotic complexity for GraphBLAS.

### 4.6.10 Summary

The asymptotic complexities for Q1 are summarized in Table 5. The table is divided into solutions that are not incremental at all at the top (including non-incremental executions of tools that are able to implicitly incrementalize the query), those that are implicitly incremental and derive the algorithm to propagate incremental changes from a declarative specification in the middle, and explicitly incremental solutions at the bottom.

One can see in Table 5 that whereas the non-incremental tools have a linear complexity with respect to the number of Posts and Comments, many incremental tools have a better asymptotic complexity and therefore should scale much better in presence of changes as they have constant or logarithmic update efforts. However, there is a notable difference between NMF and AOF, which take a rather fine-grained approach to incremental change propagation, compared to JastAdd, Hawk and YAMTL that rely on chunks in the form of (derived) attribute or rule calculations. While the latter can speed up recalculation to constant times in some cases, the former approaches can get down to logarithmic efforts even when Comments are added or liked as they allow partial recalculation of the score of a Comment. These complexities also could be beaten by solutions where the incremental change propagation is explicitly specified by the developer, at least using the approaches studied.

The results for asymptotic complexities for Q2 are summarized in Table 6. The solutions are ordered in the same way as in Table 5. While for adding Users, Posts or Comments, the results look very similar to Q1 with incremental approaches achieving a strictly better asymptotic complexity, the results for liking a Comment or especially Users becoming friends are not as good. This is partially because the analysis of asymptotic complexities is not very detailed,<fnref n="25" /> but it is also a consequence of the effect that these changes simply have a large impact on the computations that get invalidated. A new friendship changes the connected components in the induced subgraphs of the Comments that both Users have liked.

## 5 Performance evaluation

In this section, we present the results of the performance measurements with respect to the time required to load the models, to run the initial query evaluation, and to propagate changes. We first present the benchmark setup and experiment design and then analyse the results. Finally, we discuss potential threats to validity.

### 5.1 Benchmark setup

#### 5.1.1 Input models

We executed the benchmark on models of increasing sizes, denoted by scale factors (SFs) of power of 2. The number of elements per node/edge type in each SF is shown in Table 7. The largest model has 0.86M nodes and 2.25M edges. The number of changes varies between 45 and 132 model elements.

#### 5.1.2 Benchmark framework

The benchmark framework is based on the one of the TTC 2017 Smart Grid case [48] and supports automated build and execution of solutions as well as a correctness check and visualization of the results using R. The correctness is checked by comparing the query result against a pre-computed reference both after the initial transformation and after each update. The source code and documentation of the benchmark as well as metamodels, solutions, input models and change sequences used for benchmarking are publicly available online.<fnref n="26" /> The benchmark repository also contains instructions on how to

<footnote n="25">²⁵ A more detailed analysis might take the maximum number of Comments a User has liked into account, which is certainly smaller than c.</footnote>

<footnote n="26">²⁶ https://github.com/TransformationToolContest/ttc2018liveContest.</footnote>
<table><caption>**Table 7** Model sizes for each scale factor: number of nodes and edges, number of changes</caption><thead><tr><th>Type\scale factor</th><th>1</th><th>2</th><th>4</th><th>8</th><th>16</th><th>32</th><th>64</th><th>128</th><th>256</th><th>512</th><th>1024</th></tr></thead><tbody><tr><td>Comments</td><td>640</td><td>1064</td><td>2315</td><td>5056</td><td>9220</td><td>18,872</td><td>39,212</td><td>76,735</td><td>148,470</td><td>273,418</td><td>540,905</td></tr><tr><td>Posts</td><td>554</td><td>889</td><td>1845</td><td>2270</td><td>5518</td><td>10,929</td><td>18,083</td><td>37,228</td><td>74,668</td><td>167,299</td><td>314,510</td></tr><tr><td>Users</td><td>80</td><td>118</td><td>190</td><td>204</td><td>394</td><td>595</td><td>781</td><td>1158</td><td>1678</td><td>2606</td><td>3699</td></tr><tr><td>Total number of nodes</td><td>1274</td><td>2071</td><td>4350</td><td>7530</td><td>15,132</td><td>30,396</td><td>58,076</td><td>115,121</td><td>224,816</td><td>443,323</td><td>859,114</td></tr><tr><td>friends</td><td>53</td><td>102</td><td>262</td><td>298</td><td>904</td><td>1827</td><td>2752</td><td>5695</td><td>11,118</td><td>24,387</td><td>45,386</td></tr><tr><td>replyTo</td><td>640</td><td>1064</td><td>2315</td><td>5056</td><td>9220</td><td>18,872</td><td>39,212</td><td>76,735</td><td>148,470</td><td>273,418</td><td>540,905</td></tr><tr><td>likes</td><td>6</td><td>24</td><td>66</td><td>129</td><td>572</td><td>1598</td><td>4770</td><td>13,374</td><td>36,815</td><td>102,276</td><td>268,432</td></tr><tr><td>submitter</td><td>1194</td><td>1953</td><td>4160</td><td>7326</td><td>14,738</td><td>29,801</td><td>57,295</td><td>113,963</td><td>223,138</td><td>440,717</td><td>855,415</td></tr><tr><td>Total number of edges</td><td>2533</td><td>4207</td><td>9118</td><td>17,865</td><td>34,654</td><td>70,970</td><td>143,241</td><td>286,502</td><td>568,011</td><td>1,114,216</td><td>2,251,043</td></tr><tr><td>Total number of changes</td><td>67</td><td>120</td><td>132</td><td>104</td><td>110</td><td>117</td><td>68</td><td>86</td><td>45</td><td>112</td><td>74</td></tr></tbody></table>

run the benchmark in Docker containers and there are Docker images of all solutions available in Docker Hub.<fnref n="27" />

best variant. A comparison of the solution variants for NMF, Hawk, JastAdd and YAMTL can be found in the appendix.

### 5.1.3 Benchmark environment

We ran the solutions on a cloud virtual machine with 8 cores of an Intel® Xeon® Platinum 8167M CPU, a base clock speed of 2.0 GHz and a turbo clock speed of 2.4 GHz. Hyper-Threading was turned off. The machine was running the Ubuntu 20.04.2 LTS operating system. To help reproducibility, the experiments were executed in containers managed by Docker 20.10.6. The runtime environments for Java- and .NET-based solutions were OpenJDK 1.8.0 update 282, OpenJDK 11.0.10 and .NET Core 3.1.14. Each tool was measured 5 times, and the geometric mean of the results is used. The timeout value for each run was set to 10 minutes.

The modelling tools used XML-based representations (e.g. XMI files) to load the data and the change set sequences. For the rest of the tools (Neo4j, GraphBLAS, PostgreSQL and Differential Dataflow), both the initial model and the change sequences were loaded from CSV files.

## 5.2 Analysis

We grouped execution times by query, tool family and phase. To save space, we do not show the exact results, but these can be obtained from the GitHub repository of the benchmark. From the phases listed in Sect. 2.4, we omitted the initialization phase and kept the other three, i.e. (1) loading the models, (2) the initial run and (3) the time to apply a set of changes and update the result accordingly. In the following, we compare the solutions across tool boundaries. For each family of solutions, we only include the results for the

### 5.2.1 Batch solutions

The results for all batch tools are depicted in Fig. 9. One can immediately see that most lines in all of these diagrams have approximately the same slope. This confirms that query execution times grow approximately linearly with the size of the models.

The results for the initial execution times and the times to update the graph are also very similar. This is clear, given that after changing the model, the batch solutions all evaluate the entire query again. Particularly for small models, there is an overhead attached with the first execution, which is why the execution times for updates are slightly smaller. This overhead differs between the tools and is constant, thus hard to perceive on a log scale.

For the update times, one can see clear distances between the graphs, especially for Q1 where plotted execution times appear almost parallel, indicating constant factors, i.e. the solutions have different execution speeds but very similar scalability characteristics. The GraphBLAS batch solution outperforms all other batch solutions by more than one order of magnitude. JastAdd and YAMTL that come next are still faster than NMF by a factor of 3 and faster than the remaining by at least an order of magnitude for Q1.

For Q2, many solutions had severe performance problems which is why they did not complete for larger model sizes. One can also see that in particular for the SQL solution and the JastAdd solution, the slope is steeper for the larger model sizes, indicating the chosen algorithm implementation does not scale equally well.

For Hawk, one can see how the choice of the underlying database implementation affects performance: the perfor-

<footnote n="27">²⁷ https://hub.docker.com/r/ftsrg/ttc2018/tags.</footnote>
<figure><img src="image_17.png" /><figcaption>Fig. 9 Execution times of solutions with batch evaluation</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Fig. 10 Execution times of solutions with implicit incremental evaluation</figcaption></figure>
<figure><img src="image_19.png" /><figcaption>Fig. 11 Execution times of solutions with explicit incremental evaluation</figcaption></figure>

mance using SQLite is mostly better, which is clear given
that the entire models for all sizes fit into main memory.

5.2.2 Implicit incremental solutions

For the implicitly incremental solutions, the results depicted
in Fig. 10 look very different. While one can see a slope
in the load times and in the initial query evaluations, the
times to propagate a change sequence appear constant across
model sizes for all solutions except JastAdd. These solutions
require few milliseconds or less to propagate the changes
even for the largest input model sizes.<fnref n="28" /> For JastAdd, the
execution times for an update have the same slope as for
the initial execution, so the incremental change propagation
cannot reduce the complexity but allows a constant speedup
(or even slowdown, cf. Sect. A.2.3).

Because the Differential Dataflow solution was the only
solution in this category that is not using a modelling frame-
work underneath but uses plain CSVs as inputs, it is faster
in loading the models by multiple orders of magnitude. This
is due to the fact that the parsers used in the modelling tools
(EMF or NMF) both work with a much more diverse set

of inputs than CSV and therefore have a much higher com-
plexity. Furthermore, both modelling frameworks induce an
overhead to the model elements.

With regard to the initial execution, one can see that the
slope for AOF and the incremental ATL solution is smaller
than for the others. Apparently, AOF has a bigger constant
overhead that gets less important as models grow. In contrast,
the NMF solution has an initial time that is more than an order
of magnitude slower than the other solutions. Apart from
this, one can observe that Differential Dataflow, JastAdd and
YAMTL are the fastest in the initial run.

5.2.3 Explicit incremental solutions

Surprisingly, the results for the explicitly incremental tools depicted in Fig. 11 are worse than for the implicitly incremental tools in the sense that they all have a slope, i.e. the execution times to update the query results grow with growing model sizes. The only exception here is YAMTL, where the incrementalization itself is obtained implicitly but is manually and explicitly tuned. For GraphBLAS, this seems not critical for the model sizes benchmarked because the solution is faster than the others by multiple orders of magnitude and the time to propagate the changes is still below the tenth of a second. For all the other solutions, however, the scalability is much worse than for most of the implicit incremental

<footnote n="28">28 The NMF solution appears to be slower than a millisecond, but this
is only due to the fact that the first *Update* phase includes a just-in-time
compilation which takes about 10–50 ms.</footnote>
<figure><img src="image_20.png" /><figcaption>Fig. 12 Execution times of selected incremental solutions</figcaption></figure>

tools: they run out of memory and have runtimes of multiple seconds.

This result is surprising because one would expect that the incrementality of solutions, i.e. to which extent the update times depend on the model sizes depend on the input size, would be better if the solutions are explicitly developed for this use case. However, the results imply the opposite. This is because the implicit incremental tools create very fine-grained dependency graphs that allow implicit incremental tools to keep the effort of propagating a change to a minimum, whereas the explicit solutions apply rather coarse-grained schemes and need to re-evaluate larger parts of the query.

For Hawk, the differences between the Neo4j and the SQLite backend are more severe than in the batch version. While Neo4j is slower, particularly in the *Update* phase, it is capable of processing the largest model, while the SQLite backend runs out of memory.

### 5.2.4 Selected incremental tools

To allow a better comparison between the implicitly and explicitly incremental solutions, we plotted a selected subset of the incremental tools in Fig. 12. The results show again large differences in the runtime for the initial query computation of about three orders of magnitude. The load times show the differences between solutions that operate on plain CSVs

and those that use a modelling framework or have to set up a database.

The results for the change propagation just confirm what we found in the previous sections: while the explicitly incrementalized solutions have a slope, indicating that the time for updating the results grows with the size of the models, the implicitly incrementalized solutions essentially ignore the size of the models when propagating updates. Furthermore, while the times of the implicitly incremental tools are all within one order of magnitude, the times for the explicitly incremental tools differ significantly and are generally much worse, again with the exception of GraphBLAS.<fnref n="29" />

## 5.3 Threats to validity

### 5.3.1 Internal threats to validity

**Query Selection** The queries used in the benchmark are artificial. They have been created by the first author in such a way that they would represent typical queries. The design goal of the second query in particular was to include some kind of graph algorithm in order to evaluate the flexibility of the tools on a concrete example. We chose the calculation of

<footnote n="29">²⁹ Here, we again consider the explicitly incrementalized version of the YAMTL solution as essentially implicitly incrementalized with an additional explicit tuning.</footnote>
connected components because it is a well-studied algorithm
and was applicable for the chosen scenario.

**Technologies** There is a difference of the used languages, runtimes and technologies because the solutions use different modelling approaches. Therefore, differences in response times may be due to the difference of the used framework instead of the difference in the used incremental tool. Clearing this effect from the measurements would necessitate re-implementing both the solutions and the underlying tools (in many cases large libraries or even database management systems) in another technology stack, an overhead which is not justified by this confounding effect. Further, users will likely choose a tool that actively supports the modelling approach they are using.

**Tools versus solutions** The paper claims to compare tools where we in fact compare solutions using these tools. However, the solutions have been created by the authors of the tools or at least experienced developers. Therefore, we think that it is realistic to assume that the solutions are optimal for the provided tool. However, this optimum may vary between solutions. A good example is the calculation of the top-3 elements from a collection with scores. Some tools realize this by taking the first elements of a sorted collection, because keeping the sorted collection speeds up the following calls and this way, the analysis is very readable. Others calculate the 3 maximal elements because the sorted collection would be discarded and is therefore not efficient.

**Noise during measurements** Due to repetition of measurements, we think that the influence of garbage collection and just-in-time compilation is much smaller than the observed differences between incremental and non-incremental tools. However, we ran our benchmarks on virtual machines in the cloud, where we could not control the resource isolation from other tenants.

**Different input formats** To account for the format of model change sequences, we reproduced the change format also in EMF and generally took the serialization, deserialization and conversion of model changes into the tools' respective native formats out of the time measurements.

### 5.3.2 External threats to validity

**Generalizability** It is unclear to what degree the obtained results can be generalized for other applications, input model characteristics and change sequences. Further, it is unclear to what extent the solutions represent the tools, even though many solutions have been implemented by tool authors. The analysis of the algorithmic complexities shows that these

complexities heavily depend on the query, the characteristics of the inputs and the change sequences and all of these will be different in other applications. However, we expect that observed difference between the orders of magnitude of the update times for incremental vs. non-incremental tools is (to some degree) representative to real-world use cases which run global graph queries on continuously changing graph models.

**Limited types of changes** Though the change sequence used in the various case studies has been generated, they depend on the selection of changes and their proportion. In particular, we only considered incremental changes, i.e. additions of Posts, Comments or friendships. We did not consider decremental changes such as deleting Posts, Comments or breaking friendships. Those potentially require additional change propagation rules that did not have to be considered in the scope of this paper. In the scope of a benchmark, it is important to exactly specify the possible changes to the inputs because the presence of decremental changes can have an impact on the choice of algorithms to implement the change propagation [46], so the possibility of decremental changes has an impact even if they do not actually occur.

## 6 Related work

In this section, we review related work. We begin by reviewing studies that compare existing tools of related fields in Sect. 6.1. In Sect. 6.2, we then review existing incremental tools that we have not so far taken into account for the comparison.

### 6.1 Comparative studies

The present paper is an outcome of TTC 2018, but this is not the first time that the TTC has considered incremental queries. The Train Benchmark [82] by Szárnyas et al. compared query technology based on an example metamodel and queries motivated by the railway domain. A separate TTC version of this benchmark also exists that focuses more on modelling tools [83]. Both versions of this benchmark have in common that they use homogeneous change sequences. This means that solutions generally only have to react to one kind of model changes that will always affect the query result. In the benchmark presented in this paper, we use heterogeneous change sequences independent of the query, as we think that this is more realistic. Furthermore, we added a query where pure querying technology is not sufficient.

Apart from the Train Benchmark, there have been a number of other TTC contests in the recent years that took incremental change propagation into account. The TTC 2016 live contest was about a meta-transformation to transform
an abstract dataflow model into an executable model trans-
formation, with the goal to achieve an incremental change
propagation as well. However, no change sequences were
provided and there was only one incremental solution.<fnref n="30" /> Sim-
ilarly, the TTC 2017 Smart Grids case [48] featured a query
joining information from two models, if possible with incre-
mental change propagation. However, only two solutions
were submitted [47,72] from which only one supported incre-
mental change propagation. The 2017 Families to Persons
case [6] focused more on bidirectional change propagation
but also considers incremental change propagation (in both
directions). In contrast to the present social media bench-
mark, input and output models are isomorphic in the Families
to Persons case. A complete list of the TTC cases up to 2018
can be found in [81, p.112].

A related field to incremental computation is reactive pro-
gramming, where the goal is to get notifications for changes.
An overview of 15 languages for reactive programming was
created by Bainomugisha et al. [7]. Reactive programming
approaches are built upon an important assumption, namely
that signals do not change once they are processed. That is,
they operate on a (potentially infinite) sequence of immutable
data. This is a contrast to model analysis tools where the
model usually has an approximately fixed size, but is muta-
ble.

In the Social Media case, this difference boils down to
the question whether one looks at the events that enter the
system such as adding a new User, adding a friendship,
etc., or whether the state of the system is looked at in its
entirety. Model-driven tools make the system state explicit
(in a model); meanwhile, reactive programming approaches
make it rather implicit. We think that the question which of
these is better highly depends on the application scenario.

## 6.2 Incrementality

Incrementality is a desirable property as it promises to save
computational effort when analyses are computed repeatedly.
Therefore, it has been a subject of research for decades [75],
for example, with the search for incremental compilers [76].
Common to all of these approaches is that they take advantage
of assumptions they make on the computation to perform at
the cost of limited applicability.

The approach by Reps [77] for attribute grammars is
among the first incrementalization systems, which special-
ized on a limited class of problems. This approach works by
using a static dependency graph for attribute evaluations for
which Reps has shown that an optimal-time re-evaluation
strategy can be found by re-evaluating the attributes in a

topologically sorted order of a static dependency graph. This
approach rests on the assumption that the data processed by
the attribute grammar are immutable. As Reps applies this
technique for parse trees, this assumption is reasonable, but
it does not hold for models in general. The JastAdd tool in
our comparison uses this technology.

Pugh and Teitelbaum [73] then applied memoization
to incremental computation. Memoization is applicable to
any referential transparent function (such as getting refer-
ences to the three topmost elements of Q1 or Q2 is) but
rests on the assumption that the data structures it operates
on are immutable—an assumption not met with models.
Immutable data structures cannot represent cyclic data struc-
tures natively and therefore make it difficult to create analyses
requiring them. In the Social Media benchmark, we have vari-
ous cross-references between Users to represent their friends.
Further, in general it is unclear which functions should be
memoized to actually get a performance benefit.

Acar and others created Self-Adjusting Computation
(SAC), a framework to support the development of incre-
mental programs [2] using the then newly introduced DDGs.
A good overview on SAC is provided by Acar [3]. The rough
idea is to memoize the computation made for a given analy-
sis. Closely related, Hammer and others introduced the idea
of demanded computation graphs, implemented in Adap-
ton [40,41]. Demanded computation graphs make sure that a
change propagation is only performed if the result is actually
needed. Both for SAC and Adapton, the modelling technol-
ogy currently is a big obstacle as they are implemented in
programming languages that do not have good support for
models.<fnref n="31" /> We therefore could not take these approaches into
account.

A popular approach to specify queries, especially in graph
transformation, is *Graph Patterns*. Bergmann et al. have cre-
ated *INCQUERY*, an incremental pattern matching system for
*Graph Patterns* [10,11]. This approach uses a Rete network
[32], a static dependency graph, whose nodes are primitive
filter conditions or joins of partial pattern matches. Each node
represents a set of (partial) pattern matches. This approach
can support mutable models because the notification API
of models can be used to determine when matches must be
revoked or new matches arise.

In relational databases research, incrementalization man-
ifests in the topic of incremental view maintenance [14].
An overview on the research can be found in [24,39,79].
However, we are not aware of an open-source relational man-
agement system that implements any of these techniques.

Other approaches to incremental computation include
entirely new programming models that allow an easy
incrementalization or parallelization. An example of these
approaches is revision-based computing [21].

<footnote n="30">³⁰ Nevertheless, a publication of the results has been attempted but failed, mainly due to the lack of significant contributions given the low number of submissions and the difficulty to generalize results.</footnote>

<footnote n="31">³¹ Furthermore, for SAC there is no publicly available compiler.</footnote>
# 7 Conclusion and future work

## 7.1 Conclusion

We have presented a simple benchmark for incremental graph queries and demonstrated how it can be implemented on 11 tools from different technological spaces (modelling tools, databases, graph analytical frameworks). The results allow us to reason on the questions raised in the introduction.

**Does the tool fit into my technology space?** A complete overview of the tools considered can be found in Table 4. Most solutions work directly with EMF models. NMF has its own modelling framework but claims compatibility of the serialized models [45]. The solutions in Differential Dataflow, GraphBLAS, Neo4j and PostgreSQL implement conversions from EMF to their native formats.

**Is it useful to rely on the incrementalization of a tool or is it better [...] to implement change propagation explicitly?** The analysis of asymptotic complexities in Sect. 4.6 has foreshadowed what could be confirmed by actual performance measurements on realistic graph instances in Sect. 5: in the present benchmark, several implicit incrementalization tools were able to keep up and even outperform not only solutions developed for batch execution but also solutions that have been developed explicitly to be incremental, sometimes by multiple orders of magnitude for propagating changes. Just by specifying the query in the format of those tools, developers can gain a performance improvement for incremental change propagation that seems very hard to beat otherwise and gain that essentially for free. Only the GraphBLAS solution without the performance penalty of a modelling framework was faster, but it required the developer to rephrase the problem with matrix multiplications and explicitly deal with incrementality. This is complex, error-prone and hence expensive to develop even for such simple queries. Further, it is in contrast to the implicit solutions, in particular when their front-end language matches common standards such as OCL, EOL, SQO or Java Collections queries.

The performance results demonstrate how the explicitly incrementalized solutions, which use dependency structures on a much coarser granularity, save only few intermediate results and are slower on average than the implicitly incrementalized solutions. This is because every type of change requires dedicated code to update intermediate results. The implicit tools create a much more fine-grained dependency graph that allows to reach better asymptotic complexities and better runtimes. The only exception here is YAMTL-EI, because it is essentially a tuned version of YAMTL-II and therefore uses the same granularity.

The results also show that the implicit incremental tools NMF, AOF, ATL, YAMTL-II and Differential Dataflow have similar performance characteristics (with Differential Dataflow in front due to not having the overhead of a modelling framework), so the choice which of them to use is largely a matter of the context where the problem needs to be tackled (modelling framework, programming language, etc.).

**How long does it take to recover from an application crash?** The implicit incrementalization tools we compared in the scope of this benchmark do not support query persistence (cf. Sect. 4.4) or currently cannot (yet?) catch up with dedicated solutions where the queries have been explicitly designed for change propagation, even when being slightly bent towards the specific problem (the incremental query version of Hawk). The explicitly incrementalized durable solutions in SQL and Neo4j are more difficult to understand but are performant, making it an interesting future research topic to generalize these kind of solutions and hide their complexity behind a high-level frontend language.

For relational databases, the lack of an out-of-the-box solution for incrementalization is particularly surprising, given the huge body of research in incremental view maintenance [24,39]. Their advantage in the scope of this benchmark would have been clear as the incremental SQL solution is much harder to understand than its batch counterpart. However, these ideas did not yet make their way into the common or open-source database management systems.

**How much development effort will be necessary to implement change propagation?** Of course, the development effort to implement change propagation heavily depends on the tool and how experienced the developer is with the tool. Because the solutions in this benchmark have been developed by different authors, we did not even attempt to collect data about the development effort necessary. However, the discussion in Sect. 4.3 shows that the magnitude of development effort is quite different for the tools, in particular depending on whether the incrementalization happens implicitly or requires explicit implementation. While for JastAdd and YAMTL (in the implicitly incremental solution), no changes are necessary at all and tools like NMF or AOF only require to implement extensions (which can be shared among multiple projects, so that maybe one day comprehensive libraries exist), other tools such as in particular GraphBLAS, Neo4j and SQL require a completely different approach for supporting incremental change propagation.

**How does it scale?** The analysis of complexities and the performance results on actual hardware gives an impression of the scalability of the tools for the benchmark queries. As discussed in Sect. 5.3, this does not mean that the same scala-
bility is reached on a different use case. Rather, the discussion in Sect. 4.6 unveils what is actually happening under the covers for a given change and this discussion could be adapted for other use cases as well. The actual performance results then show the implementation constant for the tools in comparison to each other, which likely hold also for other use cases. Thus, the results can be used to estimate the scalability also in other contexts.

**Can I speed it up by adding more CPU cores?** The parallelism support of the tools compared in this paper is discussed in Sect. 4.5. The results show that while the parallelism for GraphBLAS and Differential Dataflow does bring performance advantages, these are not present (yet?) for NMF or YAMTL.

**Is the tool extensible [...]?** When originally selecting the queries for the benchmark, we expected that the calculation of connected components could not be handled natively by any approach so that solutions had to prove the extensibility of the tools. However, although this strategy has worked for a number of tools, it has not worked for all of them as some tools (Differential Dataflow, JastAdd to some degree) could indeed handle also Q2 without an extension of the tool. For the database solutions, algorithms such as calculating connected components usually have to be developed from scratch, using relational algebra.

## 7.2 Future work

We have future plans to extend the Social Media benchmark, both by covering more tools and algorithms in our experiments as well as by making the benchmark more challenging. To cover more techniques, we plan to include modelling tools such as VIATRA [85], relational databases which support intra-query parallelism such as the DuckDB embeddable analytical database [74], and make use of recently developed connected components algorithms [15]. Finally, we plan to incorporate change sequences that include deletions [87] which is expected to make it more challenging to perform the incremental maintenance of the queries and the connected components algorithm.

**Acknowledgements** We would like to thank Frank McSherry for providing an initial implementation of the Differential Dataflow solution. René Schöne was supported by German Federal Ministry of Education and Research within the research project "OpenLicht". Márton Elekes's research was funded by the European Commission and the Hungarian Authorities (NKFIH) through the Arrowhead Tools project (EU Grant Agreement No. 826452, NKFIH Grant 2019-2.1.3-NEMZ ECSEL-2019-00003) and by the NRDI Fund based on the charter of bolster issued by the NRDI Office under the auspices of the Ministry for Innovation and Technology. Gábor Szárnyas was partially supported by the SQIREL-GRAPHS NWO project.

**Funding** Open access funding provided by Budapest University of Technology and Economics.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

# A Appendix

## A.1 Detailed solution listings

- Listings 30–40 contain the code for the Batch and Incremental PostgreSQL solutions of Q2.
```sql
1 WITH RECURSIVE-- recursive stands here regardless of the fact
2         that the 2nd subquery is the recursive one
2
3 commentFriends (commentid, userid, user2id) AS (
4     SELECT 11(commentid, f userid, f.user2id
5         , friends f
6     WHERE 11 userid = f userid
7         AND f.user2id = 12 userid
8         AND 11 commentid = 12 commentid
9 )
10 , commentFriends_closed (commentid, head userid, tail userid)
11     AS (
12         -- transitive closure (reachability-only, no path is recorded)
13         -- of friendship-subgraphs defined by comment likes
14
15         -- start with the users that liked a specific comment.
16         -- They are the nodes of the projected users graph for a
17             comment
18     SELECT 1(commentid
19         , 1, userid AS head userid, 1, userid AS tail userid
20         FROM likes 1
21     UNION
22         SELECT cfc(commentid, cfc head userid, f, user2id AS
23             tail userid
24         FROM commentFriends_closed cfc
25         , commentFriends f
26         WHERE cfc tailsid userid = f, userid
27         AND cfc commentid = f, commentid
28 )
29
30 , comment_components AS (
31     SELECT commentid, head userid AS userid
32         , min(tail userid) AS componentid
33         FROM commentFriends_closed
34         GROUP BY commentid, head userid
35 )
36
37         -- consider all comments including those without likes
38 SELECT c.id AS commentid
39         , coalesce( sum( power (ccs.component_size, 2) ), 0) AS
40             score
41     FROM comments c
42         left join comment_component_size sccs on (ccs commentid =
43             c.id)
44 GROUP BY c.id, c.ts
45 ORDER BY sum( power (ccs.component_size, 2) ) DESC NULLS LAST
46         , c.ts DESC LIMIT 3
47;
```

### Listing 30 Batch PostgreSQL solution for Q2.

```sql
1 WITH RECURSIVE
2
3 comments_with_rootpost_stagel(id, ancestorid) AS (
4     SELECT c.id, c. parentid AS ancestorid
5         FROM comments c
6     UNION
7         SELECT cr.id, c. parentid AS ancestorid
8         FROM comments_with_rootpost_stagel cr
9
10         WHERE 1=1
11             -- join
12         AND cr. ancestorid = c.id
13 )
14         -- calculate rootpost: when ancestor's id matches a post's
15             id, then it is the root post
16
17 SELECT c.id, c. ancestorid AS postid
18         FROM comments_with_rootpost_stagel c
19             , posts p
20         WHERE 1=1
21     AND c. ancestorid = p.id
22 )
23
24 UPDATE comments c
25         SET postid = cr.postid
26         FROM comments_with_rootpost cr
27     WHERE c.id = cr.id
28;
```

### Listing 31 SQL query to initialize Comments' root Post reference for the Incremental PostgreSQL solution for Q1.

```sql
1 insert into q1_scoring (postid, postts, score)
2 select p.id, p.ts, 10*count (distinct c.id) +
3     count (1. userid) as score
3 from posts p
4 left join comments c on (p.id = c.postid)
5 left join likes 1 on (c.id = 1. commentid)
6 group by p.id, p.ts
7;
```

### Listing 32 SQL initial query for the Incremental PostgreSQL solution for Q1.

```sql
1 WITH RECURSIVE
2
3 comments_with_rootpost_stagel(id, ancestorid) AS (
4     SELECT c.id, c. parentid AS ancestorid
5         FROM comments_d_c
6     UNION
7         SELECT cr.id
8             -- when we reach a comment for which the root post
9                 is known,
10             -- we jump directly to that without traversing the
11             whole comment tree
12         FROM comments_with_rootpost_stagel cr
13         , comments c
14     WHERE 1=1
15     -- join
16         AND cr. ancestorid = c.id
17 )
18
19 SELECT c.id, c. ancestorid AS postid
20         FROM comments_with_rootpost_stagel c
21             , posts p
22     WHERE 1=1
23         AND c. ancestorid = p.id
24 )
25
26 UPDATE comments_d_c
27         SET postid = cr.postid
28         FROM comments_with_rootpost cr
29     WHERE c.id = cr.id
30;
```

### Listing 33 Interim step to maintain root Post reference of all Comments' of the Incremental PostgreSQL solution for Q1.
```sql
1 WITH diff posts AS (
2   select p.id, p.ts
3   , 10*count(distinct c.id) + count(l.userid) as score
4   from posts_d p
5   left join comments_d c on (p.id = c.postid)
6   left join likes_d l on (c.id = l commentid)
7   group by p.id, p.ts
8 )
9 , diff comments AS (
10   select p.id, p.ts
11   , 10*count(distinct c.id) + count(l.userid) as score
12   from posts_b p
13   inner join comments_d c on (p.id = c.postid)
14   left join likes_d l on (c.id = l commentid)
15   group by p.id, p.ts
16 )
17 , diff likes AS (
18   select p.id, p.ts
19   , count(l.userid) as score
20   from posts_b p
21   inner join comments_b on (p.id = c.postid)
22   inner join likes_d l on (c.id = l commentid)
23   group by p.id, p.ts
24 )
25 INSERT INTO q1 scoring AS r (postid, postts, score)
26   select id, ts, sum score as score
27   from (
28     select * from diff posts
29     UNION ALL
30     select * from diff comments
31     UNION ALL
32     select * from diff likes
33   ) t
34   group by id, ts
35 ON CONFLICT (postid) DO UPDATE SET score = EXCLUDED.score +
36     r.score
37;
```

**Listing 34** Interim result maintenance step of the Incremental PostgreSQL solution for Q1.

1. `select postid, score`

2. `from q1 scoring`

3. `order by score desc, postts desc limit 3;`

**Listing 35** SQL result retrieval phase for the Incremental PostgreSQL solution for Q1.

1. `INSERT INTO commentFriends (status, commentid, userid, user2id)`

2. `SELECT 'B' AS status`

3. `11 commentid, f.userid, f. user2id`

4. `FROM likes 11, likes 12`

5. `f. friends f`

6. `WHERE 11. userid = f. userid`

7. `AND f. user2id = 12. userid`

8. `AND 11. commentid = 12. commentid;`

**Listing 36** Initialization phase for the Incremental PostgreSQL solution for Q2, initializing the *commentFriends* relation.

1. `INSERT INTO commentFriends (status, commentid, userid, user2id)`

2. `SELECT 'D' AS status`

3. `11. commentid, f. userid, f. user2id`

4. `FROM likes_d 11, likes 12`

5. `f. friends f`

6. `WHERE 11. userid = f. userid`

7. `AND f. user2id = 12. userid`

8. `AND 11. commentid = 12. commentid`

9. `UNION ALL`

10. `SELECT 'D' AS status`

11. `11. commentid, f. userid, f. user2id`

12. `FROM likes_b 11, likes 12`

13. `f. friends_d f`

14. `WHERE 11. userid = f. userid`

15. `AND f. user2id = 12. userid`

16. `AND 11. commentid = 12. commentid`

17. `UNION ALL`

18. `SELECT 'D' AS status`

19. `11. commentid, f. userid, f. user2id`

20. `FROM likes_b 11, likes_d 12`

21. `f. friends_b f`

22. `WHERE 11. userid = f. userid`

23. `AND f. user2id = 12. userid`

24. `AND 11. commentid = 12. commentid;`

**Listing 37** SQL maintenance phase for the Incremental PostgreSQL solution for Q2: updating the *commentFriends* relation.
<table><caption>Listing 38 SQL initialization phase for the Incremental PostgreSQL solution for Q2: initializing the *commentFriends* relation's closure.</caption><thead><tr><th>Step</th><th>Command</th><th>Description</th></tr></thead><tbody><tr><td>1</td><td>WITH RECURSIVE</td><td>commentFriends_closed_init()</td></tr><tr><td>2</td><td>commentid, head_userid, tail_userid) AS</td><td>(</td></tr><tr><td>3</td><td>-- transitive closure</td><td>(reachability-only, no path is recorded)</td></tr><tr><td>4</td><td>-- of friendship-subgraphs defined by comment likes</td><td></td></tr><tr><td>5</td><td>6</td><td>-- start with the users that liked a specific comment.</td></tr><tr><td>7</td><td>-- They are the nodes of the projected users graph for a comment</td><td></td></tr><tr><td>8</td><td>SELECT 1commentid, 1.userid AS head_userid, 1.userid AS tail_userid</td><td></td></tr><tr><td>9</td><td>FROM likes 1</td><td></td></tr><tr><td>10</td><td>UNION</td><td></td></tr><tr><td>11</td><td>-- expand the closure with the edges of the projected graph,</td><td></td></tr><tr><td>12</td><td>-- which is stored in commentFriends table</td><td></td></tr><tr><td>13</td><td>SELECT cfccommentid, cfchead_userid, f.user2id AS tail_userid</td><td></td></tr><tr><td>14</td><td>FROM commentFriends_closed_init cfc</td><td></td></tr><tr><td>15</td><td>, commentFriends f</td><td></td></tr><tr><td>16</td><td>WHERE cfc.tail_userid = f.userid</td><td></td></tr><tr><td>17</td><td>AND cfccommentid = fcommentid</td><td></td></tr><tr><td>18)</td><td>19 INSERT INTO</td><td>commentFriends_closed(commentid, head_userid, tail_userid)</td></tr><tr><td>20</td><td>select commentid, head_userid, tail_userid</td><td></td></tr><tr><td>21</td><td>from commentFriends_closed_init w</td><td></td></tr><tr><td>22</td><td>left join</td><td>commentFriends_closed q using (commentid, head_userid, tail_userid)</td></tr><tr><td>23</td><td>where qcommentid IS NULL;</td><td></td></tr></tbody></table>

<table><caption>Listing 39 SQL maintenance phase for the Incremental PostgreSQL solution for Q2: updating the *commentFriends* relation's closure.</caption><thead><tr><th>Step</th><th>Command</th><th>Description</th></tr></thead><tbody><tr><td>1</td><td>WITH RECURSIVE</td><td>-- note: though not the 1st query is the recursive one, the RECURSIVE keyword needs to be at the beginning</td></tr><tr><td>2</td><td>commentFriends_closed_stage0 AS</td><td></td></tr><tr><td>3</td><td>-- in order to maintain the transitive closure in commentFriends_closed</td><td></td></tr><tr><td>4</td><td>-- we build on the transitive closure built so far and the new likes.</td><td></td></tr><tr><td>5</td><td>-- We need the new likes because users that liked a specific comment</td><td></td></tr><tr><td>6</td><td>-- are the nodes of the projected users graph for a comment</td><td></td></tr><tr><td>7</td><td>SELECT commentid, head_userid, tail_userid</td><td></td></tr><tr><td>8</td><td>FROM commentFriends_closed</td><td></td></tr><tr><td>9</td><td>UNION ALL</td><td></td></tr><tr><td>10</td><td>SELECT 1commentid, 1.userid AS head_userid, 1.userid AS tail_userid</td><td></td></tr><tr><td>11</td><td>FROM likes_d 1</td><td></td></tr><tr><td>12)</td><td>13, commentFriends_closed_stage1(commentid, head_userid, tail_userid) AS</td><td></td></tr><tr><td>14</td><td>-- the transitive closure computed so far (reachability-only, no path is recorded)</td><td></td></tr><tr><td>15</td><td>-- is expanded by paths built from the new friendships</td><td></td></tr><tr><td>16</td><td>SELECT commentid, head_userid, tail_userid</td><td></td></tr><tr><td>17</td><td>FROM commentFriends_closed_stage0</td><td></td></tr><tr><td>18</td><td>UNION</td><td></td></tr><tr><td>19</td><td>SELECT cfccommentid, cfchead_userid, f.user2id AS tail_userid</td><td></td></tr><tr><td>20</td><td>FROM commentFriends_closed_stage1 cfc</td><td></td></tr><tr><td>21</td><td>, commentFriends_d f</td><td></td></tr><tr><td>22</td><td>WHERE cfc.tail_userid = f.user1id</td><td></td></tr><tr><td>23</td><td>AND cfccommentid = fcommentid</td><td></td></tr><tr><td>24)</td><td></td><td></td></tr><tr><td>25</td><td>, commentFriends_closed_stage2 AS</td><td></td></tr><tr><td>26</td><td>-- transitive closure having the new friendships is then expanded using the</td><td></td></tr><tr><td>27</td><td>-- previous transitive closure stage</td><td></td></tr><tr><td>28</td><td>SELECT distinct cfccommentid, cfchead_userid, r.tail_userid</td><td></td></tr><tr><td>29</td><td>FROM commentFriends_closed_stage1 cfc</td><td></td></tr><tr><td>30</td><td>inner join commentFriends_closed r on (cfc.tail_userid = rhead_userid AND cfccommentid = rcommentid)</td><td></td></tr><tr><td>31</td><td>-- LEFT JOIN and WHERE ... IS NULL is the antijoin</td><td></td></tr><tr><td>32</td><td>-- used to eliminate edges already present in the previous closure</td><td></td></tr><tr><td>33</td><td>-- this is to prevent unnecessary CONFLICTs in the INSERT statement below.</td><td></td></tr><tr><td>34</td><td>left join commentFriends_closed s0 on (cfccommentid = s0commentid AND cfchead_userid = s0head_userid AND cfc.tail_userid = s0.tail_userid)</td><td></td></tr><tr><td>35</td><td>WHERE s0commentid IS NULL</td><td></td></tr><tr><td>36</td><td>UNION</td><td></td></tr><tr><td>37</td><td>SELECT commentid, head_userid, tail_userid</td><td></td></tr><tr><td>38</td><td>FROM commentFriends_closed_stage1</td><td></td></tr><tr><td>39)</td><td>40 INSERT INTO</td><td>commentFriends_closed(commentid, head_userid, tail_userid)</td></tr><tr><td>41</td><td>select commentid, head_userid, tail_userid</td><td></td></tr><tr><td>42</td><td>from commentFriends_closed_stage2 w</td><td></td></tr><tr><td>43</td><td>left join commentFriends_closed q using (commentid, head_userid, tail_userid)</td><td></td></tr><tr><td>44</td><td>where qcommentid IS NULL</td><td></td></tr><tr><td>45</td><td>ON CONFLICT DO NOTHING;</td><td></td></tr></tbody></table>
```sql
1 WITH comment_components AS (
2 SELECT commentid, head_userid AS userid
3 , min(tail_userid) AS componentid
4 FROM commentFriends_closed
5 GROUP BY commentid, head_userid
6 )
7 , comment_component_sizeS AS (
8 SELECT cc commentid,
        cc.componentid, count(*) AS component_size
9 FROM comment_components cc
10 GROUP BY cc commentid,
        cc.componentid
11 )
12 -- consider all comments including
13 those without likes
14 SELECT c.id AS commentid
15 , coalesce( sum(
16 power(ccs.component_size,
        2) ), 0) AS score
17 FROM comments c left join
18 comment_component_sizeS ccs
19 on (ccs commentid = c.id)
20 GROUP BY c.id, c.ts
21 ORDER BY sum(
22 power(ccs.component_size, 2) )
23 DESC NULLS LAST
24 , c.ts DESC LIMIT 3;
```

<caption>**Listing 40** SQL result retrieval phase for the Incremental PostgreSQL solution for Q2.</caption>

```sql
1 MATCH (c)<-[:LIKES]-(u:User)
2 WITH c, collect(u) AS users
3 CALL apoc.create.addLabels(userS,
4   ['Likes_' + c.id]) YIELD node
4 RETURN count(*)
```

**Listing 41** Neo4j incremental implementation of Q2 – initial step that materializes the subgraph by dynamic labelling of Users liking the Comment.

- Figure 14 contains the proof for the relational algebra formula for the join of relations with a positive delta (change set).

- Listings 41–42 contain the initial queries of the incremental Neo4j solution for Q2.

- Listings 43–44 contain the incremental maintenance queries of the Neo4j solution for Q2.

- Algorithm 5 shows a GraphBLAS algorithm to build the incidence matrix from an adjacency matrix.
$$ \bowtie_{i=1}^{N} (r_i \cup \Delta r_i) = (\bowtie_{i=1}^{N} r_i) \cup \bigcup_{i=1}^{N} ((\bowtie_{j=1}^{i-1} (r_j)) \bowtie \Delta r_i \bowtie (\bowtie_{j=i+1}^{N} (r_j \cup \Delta r_j))) $$

<caption>**Fig. 13 Relational algebra formula for join of relations with positive delta**</caption>

$$ (r_1 \cup \Delta r_1) = (r_1) \cup \bigcup_{i=1}^{1} (\Delta r_i) $$

Inductive step: show that for any $k > 1$, if $P(k-1)$ holds, then $P(k)$ also holds.

$$ \begin{align*} (\bowtie_{i=1}^{k-1} (r_i \cup \Delta r_i)) \bowtie (r_k \cup \Delta r_k) &= \\ \text{using the formula for } P(k-1) \end{align*} \begin{align*} &= ( (\bowtie_{i=1}^{k-1} r_i) \cup \bigcup_{i=1}^{k-1} ((\bowtie_{j=1}^{i-1} (r_j)) \bowtie \Delta r_i \bowtie (\bowtie_{j=i+1}^{k-1} (r_j \cup \Delta r_j))) ) \bowtie (r_k \cup \Delta r_k) \\ &= (\bowtie_{i=1}^{k-1} r_i) \bowtie (r_k \cup \Delta r_k) \cup \left( \bigcup_{i=1}^{k-1} ((\bowtie_{j=1}^{i-1} (r_j)) \bowtie \Delta r_i \bowtie (\bowtie_{j=i+1}^{k-1} (r_j \cup \Delta r_j))) \right) \bowtie (r_k \cup \Delta r_k) \\ &= (\bowtie_{i=1}^{k} r_i) \cup (\bowtie_{i=1}^{k-1} r_i) \bowtie \Delta r_k \cup \bigcup_{i=1}^{k-1} ((\bowtie_{j=1}^{i-1} (r_j)) \bowtie \Delta r_i \bowtie (\bowtie_{j=i+1}^{k-1} (r_j \cup \Delta r_j)) \bowtie (r_k \cup \Delta r_k)) \end{align*} $$

the 2nd component of the union is exactly the expression inside the big union for $i = k$, thus

$$ (\bowtie_{i=1}^{k} r_i) \cup \bigcup_{i=1}^{k} ((\bowtie_{j=1}^{i-1} (r_j)) \bowtie \Delta r_i \bowtie (\bowtie_{j=i+1}^{k} (r_j \cup \Delta r_j))) $$

which is $P(k)$. Thus the proposition holds by induction.

<caption>**Fig. 14 Proof for the relational algebra formula for join of relations with a positive delta (change set)**</caption>

1 CALL apoc.periodic.commit(""
2 MATCH (c:Comment)<-[:LIKES]-(u1:User)
3 WITH c, min(u1) AS u1
4 CREATE (c)-[:COMPONENT]->(comp:Component)
5 WITH c, u1, comp
6 CALL apoc.path.subgraphNodes(u1,
{labelFilter: 'Likes_' + c.id,
7 relationshipFilter: 'FRIEND'}) YIELD
node AS u2
8 CREATE (comp)-[:USER]->(u2)
9 WITH c, comp, u2
10 MATCH (c)<-[:LIKES]-(u2)
11 DELETE 1
12 WITH c, comp, count(*) AS componentSize
13 SET comp.size = componentSize
14 RETURN count(*)
15 // limit - to bypass mandatory limit
16")

**Listing 42** Neo4j incremental implementation of Q2 - grouping components using fixed-point and the reachability function apoc.path.subgraphNodes of the APOC library.

1 WITH $friendEdgeId AS friendEdgeId
2 MATCH (comp1:Component)-[:USER]->
3 (u1:User)-[friendEdge]->(u2:User)
4 // comp1 <> comp2, because COMPONENT edges
are different
5 (comp1)<-[:COMPONENT]-(c:Comment)
6 -[:COMPONENT]->(comp2)
7 WHERE id(friendEdge) = friendEdgeId
8 WITH c, comp1, comp2,
9 comp1.size AS comp1Size,
10 comp2.size AS comp2Size,
11 comp1.size + comp2.size AS newCompSize
12 // mergeRels: to avoid parallel COMPONENT
edges
13 CALL apoc.refactor.mergeNodes([comp1,
comp2], {mergeRels: true}) YIELD
node AS newComp
14 SET newComp.size = newCompSize,
15 c.score = c.score -
comp1Size*comp1Size -
comp2Size*comp2Size +
newCompSize*newCompSize

**Listing 43** Neo4j incremental implementation of Q2 - merging components when a new FRIEND edge is inserted and the two users belonged to separate components.

1 WITH $likesEdgeId AS likesEdgeId
2 MATCH (c:Comment)<-[:likesEdge]-(u:User)
3 WHERE id(likesEdge) = likesEdgeId
4 CREATE (c)-[:COMPONENT]->(uComp:Component (size: 1))-[:USER]->(u)
5 WITH c, uComp, u
6 // OPTIONAL: to proceed if there is no such component to merge with
7 OPTIONAL MATCH
     (c)-[:COMPONENT]->(comp2:Component)
8 WHERE (comp2)-[:USER]->(:User)<-[:FRIEND]->(u)
9 WITH c,
10 uComp + collect(comp2) AS components,
11 1 + sum(comp2.size) AS newCompSize,
12 sum(comp2.size * comp2.size) AS scoreDecrease
13 // mergeRels: to avoid parallel COMPONENT edges
14 CALL apoc.refactor.mergeNodes/components,
       (mergeRels: true))
15 YIELD node AS newComp
16 SET newComp.size = newCompSize,
17 c.score = c.score - scoreDecrease + newCompSize*newCompSize

**Listing 44** Neo4j incremental implementation of Q2 – creating single-node components for the new LIKES edges, then merge them with all components where the User has friends (if any), and maintain the component sizes and the score of the Comment.

<caption>**Algorithm 5** Build incidence matrix from edges.</caption>

1: **Input**
2:   es = {(i₁, j₁), (j₁, i₁), ..., (iₘ, jₘ), (jₘ, iₘ)} ⊆ {1, ..., n}²
3: **Output**
4:   B ∈ {0, 1}ⁿ×m ▷ incidence matrix
5: **function** BUILDINCIDENCE MATRIX
6:   b_tuples ← ∅, k ← 1
7:   **for all** (i, j) ∈ es **do**
8:     **if** i < j **then**
9:       b_tuples ← b_tuples ∪ {(i, k, 1), (j, k, 1)}
10:      k ← k + 1
11:   **end if**
12:   **end for**
13:   B ← b_tuples
14:   **return** B
15: **end function**

## A.2 Comparison of solution variants

### A.2.1 NMF

Figure 15 shows the results for the different variants of the NMF solution. The results show that the difference between the standard *incremental mode* and the *transactional mode* is marginal, i.e. the engine could not take advantage of propagating all changes at once instead of propagating each change separately. This is because the changes affect different parts of the dependency graph. However, executing these propagations in different threads also does not lead to speedups because there is usually one change propagation dominating the others. Instead, we see that the additional overhead of

synchronization makes the *parallel mode's* change propagation slightly slower in this case.

### A.2.2 Hawk

Figure 16 shows the execution times of all different variants of the Hawk solution. Unfortunately, it appears that the initial load process did not complete within the timeout past model size 64 across the solutions: this is due to the use of monolithic single-file models in the benchmark framework, whereas Hawk is optimized towards models which have been fragmented into many files. The results show that the initial load is somewhat slower for the *batch* and *incremental update* (IU) solutions, as they need to calculate the derived attributes used to cache scores. These derived attributes allow the initial execution of the query to be much faster in the *batch* and IU modes than in the *incremental update and query* (IUQ) mode: the IUQ mode has to do a first full execution of the query. The updates are the slowest in the *batch* solution due to the need to both recalculate derived attributes and reserializing the changed social network model between updates. The IU mode has slightly faster updates, as it skips the reserializing and instead applies the changes directly to the graph used for querying. The IUQ mode speeds this up even further by replacing derived attributes with graph listeners, using them to detect changed comments and posts and re-score them.

### A.2.3 JastAdd

Figure 17 shows the execution times of all different variants of the JastAdd solution. The results show that the approaches using bidirectional relations (Relast variants) are strictly better than their counterparts, both in terms of initial execution and time to propagate updates. As can be expected, the incremental variants are also slower than the *batch* variants in the initial query computation. However, because the JastAdd solution needs to sort the results also in the incremental case which dominates the complexity, the performance results for the incremental variants are not significantly faster than the *batch* variants. With unidirectional references as in the original metamodel, the change propagation in the incremental execution is even slower than the *batch* variant.

### A.2.4 YAMTL

Figure 18 shows the execution times of all YAMTL solutions. They indicate that the performance improvements of the YAMTL-EI solutions over the purely implicit variant are rather small, except for Q2 where the time for an update propagation could be further reduced.
<figure><img src="image_21.png" /><figcaption>Fig. 15 Execution times of NMF solutions</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>Fig. 16 Execution times of Hawk solutions. Notation: IU: Incremental Update, IUQ: Incremental Update + Query</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Fig. 17 Execution times of JastAdd solutions</figcaption></figure>