MODELS2010: Incremental Model Queries over EMF Models

In the MODELS2010 article Incremental Model Queries over EMF Models we introduced EMF-IncQuery, a framework for defining declarative queries over EMF models, and executing them efficiently without manual coding}. For the query language, we reuse the concepts of graph patterns as a concise and easy way to specify complex structural model queries. High runtime performance is achieved by adapting incremental graph pattern matching techniques. This webpage displays the technicalities of the case-study used in the paper.


Gábor BergmannÁkos Horváth, István Ráth, Dániel Varró, András Balogh, Zoltán Balogh and András Ökrös

Case study: AUTOSAR

In the paper, we demonstrate our model query technique by checking well-formedness constraints over AUTOSAR models. AUTOSAR (Automotive Open System Architecture, AUTOSAR}) is an open and standardized automotive software architecture, jointly developed by automobile manufacturers, suppliers and tool developers. The objectives of the AUTOSAR partnership include the implementation and standardization of basic system functions while providing a highly customizable platform which continues to encourage competition on innovative functions. The common standard should help the integration of functional modules from multiple suppliers and increase scalability to different vehicle and platform variants. It aims to be prepared for the upcoming technologies and to improve cost-efficiency without making any compromise with respect to quality.

The Example Validation Rules

This section presents three well-formedness constraints from the AUTOSAR standard, which form the basis of our measurements.

ISignal constraint check

The two metamodel elements for this constraint are SystemSignal and ISignal. A SystemSignal is the smallest unit of data (it is unique per System) and it is characterized by its length (in bits). (Also two optional elements can be specified, Datatypes and DataPrototype constants, but they are not used in this example.) An ISignal must be created for each SystemSignal (these will be the signals of the Interaction Layer). Its graph pattern representation:

Graph Pattern












Corresponding AUTOSAR metamodel segment

Every object in AUTOSAR is inherited from the common ARObject class. If an element has to be identified, it has to inherit from the Identifiable class, and the shortName attribute has to be set. ARElement is a common base class for stand-alone elements, while specializations of FibexElement represent elementary building blocks within the FIBEX package. Instances of ARPackage class are arranged in a strict containment hierarchy by the subPackage association, and every PackageableElement can be aggregated by one of the ARPackage using the element association.









Signal group mapping constraint check

To ensure the atomic transfer of a SystemSignalGroup, we must pay attention to pack them properly into SignalIPdus. This means, if we refer to a SignalGroup from a SignalIPdu (with an ISignalToIPduMapping), then every Signal in it should be referenced as well from that IPdu. Note that an ISignalToIPduMapping references ISignals, but as every SystemSignal and SystemSignalGroup must have an ISignal it is not a problem. Its graph pattern representation:













Corresponding AUTOSAR metamodel segment

A PDU (Protocol data unit) is the smallest information which is delivered through a network layer. It is an abstract element in AUTOSAR, and has multiple different subtypes according to the available network layers. In this case study, we will only examine IPdus (Interaction Layer PDU), and more precisely SignalIPdus. These SignalIPdus used to transfer ISignals. The positions of these ISignals are defined by the ISignalToIPduMappings. The ISignal can be a SystemSignal and a SystemSignalGroup as well. A signal group refers to a set of signals that must always be kept together to ensure the atomic transfer of the information in them.




Simple PhysicalChannel consistency check

The following constraint has to be satisfied for a physical channel: if a CH PhysicalChannel contains an IPDU SignalIPdu (through an IPduTriggering), then all of the S ISignal, contained by IPDU (through an ISignalToIPduMapping), must have a related STR ISignalTriggering in the CH channel. In other words the channel is invalid if there is at least one S ISignal that has no related ISignalTriggering in the channel. If the CC_Channel(CH) pattern can be matched for a Physical channel CH, then it is considered to be invalid. Its graph pattern representation:













Corresponding AUTOSAR metamodel segment

In AUTOSAR, ECU (Electronic Control Unit) instances can communicate with each other through a communication medium represented by a PhysicalChannel. Physical Channels are aggregated by a CommunicationCluster, which is the main element to describe the topological connection of communicating ECUs. A Physical Channel can contain ISignalTriggering and IPduTriggering elements. The IPduTriggering and ISignalTriggering describe the usage of IPdus and Signals on physical channels. ISignalTriggering defines the manner of triggering of an ISignal on the channel, on which it is sent. IPduTriggering describes on which channel the IPdu is transmitted.

AUTOSAR Metamodel segment




For a benchmarking evaluation, we designed a randomized model generator to create sample models of increasing size. For the three constraint cases, we used two different model families: (A) for ISignal and SSG and (B) for Channel. Both families contain an approximately equal number of valid and invalid model elements. The size of the sample model families ranges from a few thousand elements up to 600.000 (A) and 1.500.000 (B).

SSG and ISignal - Model Family A

As a first step, the model generator creates an ARPackage element which contains all the generated models. Next, a constant number of SignalIpdus are created, with each containing a fixed number of blocks. These blocks, in turn, may contain four combinations of elements (the generator picks all combination types with equal probability):

  • In the first case, an ISignalToIPduMapping, which correctly refers an ISignal. This ISignal instance may, in approximately half of the overall cases, not contain a SystemSignal, which constitutes a match where the CC_ISignal constraint is violated, however the CC_SSGMapping_1 constraint still holds. In the other half of the cases, this ISignal does have a SystemSignal, so it will correctly match against both the CC_ISignal and CC_SSGMapping_1 patterns.

    All other cases only concern the CC_SSGMapping_1 constraint and the CC_ISignal pattern will match correctly against them.

  • In the second case, the block contains two instances of ISignalToIPduMapping, which correspond to a correct match (a SystemSignalGroup containing a SystemSignal, both have an ISignal, referred by the ISignalToIPduMappings).

    The last two cases correspond to violated constraint matches.

  • The third block type corresponds to the case where a ISignalToIPduMapping is created along with a SystemSignal and a SystemSignalGroup, but only the SystemSignal is connected to the mapping through an ISignal.
  • The third block type corresponds to the case where a ISignalToIPduMapping is created along with a SystemSignal and a SystemSignalGroup, but only the SystemSignalGroup is connected to the mapping through an ISignal.

Channel consistency checking - Model Family B

The model generator creates a CommunicationCluster instance, containing a fixed number of PhysicalChannels. Each of these refer to a random number of IPduTriggering elements containing a SignalIPdu. In turn, each of the SignalIPdus contain a random number of ISignalToIPduMappings containing an ISignal. Finally, the generator, in approximately half of the cases, creates a valid configuration by instantiating the ISignalTriggering element connecting the Channel and ISignal. In the other half of the cases, this element is omitted to make the Channel invalid in terms of the constraint described in subsec:constraint:Channel.

Model manipulation operations

We define the model manipulation sequences as follows:

  • for the ISignal case the manipulator randomly picks 10 ISignal instances, deletes their corresponding systemSignal edge (if present).
  • for the SSG case, the manipulator randomly picks 10 SignalIPdus, and deletes their first mapping (this may cause new invalid locations, or also valid ones).
  • for the Channel case, the manipulator randomly picks 5 ISignals, and "inverts" the validity of the match by either deleting the ISignalTriggering connection (if it was present) or creating a new one to the appropriate Channel (if not present).


The benchmark simulates the typical scenario of model validation. The user is working with a large model, the modifications are small and local, but the result of the validation needs to be computed as fast as possible. To emulate this, the benchmark sequence consists of the following sequence of operations:

  • First, the model is loaded into memory. In the case of EMF-IncQuery, most of the overhead is expected to be registered in this phase, as the pattern matching cache needs to be constructed. Note however, that this is a one-time penalty, meaning that the cache will be maintained incrementally as long as the model is kept in memory. To highlight this effect, we recorded the times for the loading phase separately.
  • Next, in the first query phase, the entire matching set of the constraints is queried. This means that a complete validation is performed on the model, looking for all elements for which the constraint is violated.
  • After the first query, model manipulations are executed. These operations only affect a small fixed subset of elements, and change the constraint's validity.
  • Finally, in the second query phase, the complete validation is performed again, to check the net effect of the manipulation operations on the model.

Source and Executing the case Study


The demo setup (eclipse+workspace) can be downloaded from here:


To get the case study running, an Eclipse Galileo(=3.5) instance is needed with the Plug-in Development Environment, EMF and JUnit features installed; the most straightforward way is simply installing the Eclipse Modeling distribution. Additionally, the contents of this drop-in archive has to be extracted into the "dropins" folder of the Eclipse installation, preserving the directory structure (e.g. eclipse/dropins/IncQueryBenchmarkDropins). These drop-ins contain the run-time component of EMF-IncQuery, and a simple EMF representation of a subset of the AUTOSAR metamodel.

Finally, after starting Eclipse, the Java source code projects in this project archive should be imported into the Eclipse workspace (File / Import / Existing Projects into Workspace / From archive file). The project hu.optxware.benchmark.queries contains the EMF-specific query descriptions generated from VIATRA2 graph patterns, while the other two projects generate test models and execute the benchmark.

Case Study Execution

First, the parameters defined in the class hu.optxware.benchmark.common.GeneratorConstants in project hu.optxware.benchmark should be inspected. They govern the extent of the generated instance models. If their values are satisfactory, this step does not have to be repeated.

Afterwards for each measurement, the following steps have to be carried out. Each step is defined in a .java file in the project, and has to be executed by right clicking on the file, and issueing Run As / JUnit Plug-In Test.

  1. Run to clean up any previously generated instance model.
  2. Run to generate an instance model belonging to Model Family A (SSG and ISignal checks) according to the parameters defined in GeneratorConstants, OR run to generate an instace in Model Family B (Channel consistency check) instead.
  3. Navigate to package to measure the ad-hoc Java implementations of consistency checks, to for the OCL-based solution, or to for the EMF-IncQuery versions.
  4. Select a consistency check (SSG or ISignal checks for Model Family A, and Channel for Model Family B), and execute the Java class in the package, whose file name refers to the selected consistency check.
  5. The JUnit Plug-In Test will start a run-time Eclipse workbench, load the EMF instance model, execute the consistency check, modify the model and executing again, and conduct various measurements. Results will be available in the Console view of (the parent) Eclipse.