Context: Despite model querying being an important practical problem, existing solutions lack either usability, expressiveness, or generality. The Visual Model Query Language (VMQL) is a query byexample solution created to satisfy these requirements simultaneously. Objective: In the present paper we study whether VMQL queries can be executed in an e cient way, such that VMQL is suitable for ad-hoc model querying in practical settings involving large models. Method: We study VMQL query execution performance on sets of models ranging over a broad spectrum of sizes and degrees of complexity. The models are based on large and realistic case studies. Results: We observe that our approach exhibits competitive performance, while providing superior usability and generality.
Interactive model querying is an important task in most modeling scenarios. However, manually browsing the model for query purposes is only practical for trivially small models. Consequently, several model querying approaches have been proposed.
Query By Full-Text Search is very easy to use. All major modeling tools support this feature, with varying degrees of re nement (e. g., wildcards, regular expressions, lters, logical connectors). However, it o ers only limited expressiveness, and often yields a large number of false positive results. Furthermore, it cannot be used to search for structural or meta-level information in a model.
Query By Navigation provides search results by traversing a model via
links between model elements. This includes APIs for programming queries
explicitly, and executing queries expressed in the Object Constraint Language
(OCL [
Query By-Example allows expressing queries as small, possibly annotated,
model fragments that are matched against a source model. Wherever a su cient
degree of similarity is found, a binding between the two models can be
established, which corresponds to one query result. One of the exponents of this
approach is the Visual Model Query Language (VMQL [
In previous work we have shown that VMQL queries are easier to understand
and formulate than their OCL counterparts, even when OCL is enhanced with
a query API partially hiding meta-model complexity [
VMQL addresses the ad-hoc querying application scenario, where a user (often a domain expert) explores a model interactively. Ad-hoc model querying depends on (a) an expressive query language of high usability, and (b) query processing that is fast enough to satisfy an interactive operation.
However, query by-example approaches generally do not scale well, since both source and query models are treated as graphs. Executing a query amounts to mapping the query model graph Q to the source model graph S, and returning bindings b : Q ! S between the elements of the query and source models. A valid binding must bind all query elements, i. e., every b is total, so there are up to B = jSjjQj bindings. Enumerating all the bindings is only an option for small values of S and Q. In the case of ad-hoc queries, jQj << jSj and jQj is not very large (typically in the range 5::20 model elements). S, on the other hand, can be very large: models with jSj 103:::105 elements are common. Thus, a naive approach cannot deliver the performance required for ad-hoc querying.
The remainder of this paper is structured as follows. Section 2 brie y presents VMQL, Section 3 describes the algorithms underlying the execution of VMQL queries and provides implementation details, Section 4 presents an evaluation of VMQL query execution performance, Section 5 highlights related work, and Section 6 concludes the paper and outlines future work. 2
Our running example represents a process model for handling insurance bene t claims. The source model is the UML Activity Diagram \Coverage Quote Processing" in Figure 1, while the query model is the UML Activity Diagram \Query A" in the same gure. The red dashed lines highlight a valid binding. In this case, this is the only binding. Since \Query A" does not use any annotations or variables, it is a base query. Additional queries are shown in Figure 2.
Query B introduces VMQL variables: strings starting with the $ character which typically store the value of a source model meta-attribute. The query nds all Actions which can raise an exception to be handled by the \manual coverage quote processing" Action. It returns two bindings, with the $FailingAction variable instantiated to the names of the matching Actions: \compute quotable coverage o ering" and \verify customer account", respectively.
Query C introduces VMQL constraints represented as Comments stereotyped by <<vmql>>. The steps constraint indicates that matches may include paths of inde nite length containing only Flows of the same type as the Flow to which the constraint is anchored. The name constraint implies a particular name for a model element (in this case, any string starting with \check"). Thus, the query Query:AD Query A
check general coverage
check coverage limit
Binding
AD Coverage Quote Processing receive plan coverage
quote request check general coverage
check coverage limit compute quotable coverage offering set up standard leetr No 42
Action is bound to the source model Actions \check general coverage" and \check coverage limit", respectively.
Query D is a more general version of Query A, using wildcards. Executing
query D will result in the same binding as Query A. Queries A through D only
illustrate the most basic constructs of VMQL; a complete list is available in [
VMQL queries are executed by computing a set B = fb1; b2; :::; bng of bindings between the elements of a query model and those of a source model. A binding bi = f(q id 1; s id 1); (q id 2; s id 2); :::; (q id m; s id m)g is a set of m pairs, each consisting of the ID of a query model element and that of the matching source model element, where m is the number of elements of the query model.
Query model matching is performed in two stages. First, source model elements that do not match any query model element are quickly discarded. This activity Query A
activity Query B activity Query C check general coverage check coverage limit
«vmql» steps=*
«vmql» name=check*
«vmql» steps=* activity Query D $FailingAction is achieved by only considering element types and meta-attributes with xed values, while ignoring meta-attributes that represent references to neighbouring model elements.
In the second stage, Algorithm 1 also takes into account references between query model elements. It terminates upon the convergence of two binding lists: old bindings and new bindings. At each iteration, a new version of the bindings is computed by considering each query/source model element pair and verifying its consistency with the rest of the bindings through the VERIFY LINKS function, which checks if model element references in the query model are re ected by the source model. Additional functions are required for applying VMQL constraints to the results of Algorithm 1. Since constraints are applied locally to binding elements, their processing time is linear in the size of the query model.
VMQL is implemented by the MQ-2 tool [
Unsuccessful queries are executed faster than successful ones (see Figure 4). Also, the execution time of unsuccessful queries is less dependant on source model size. This is due to the \fail early" approach of our algorithms: easily veri able properties are considered rst in order to prune the search space.
Table 2 shows the observations for executing the more complex queries
introduced in Section 2. The base query (Query A) and the query containing a
wildcard constraint (Query D) have the lowest execution times. Query B has a
slightly higher execution time, likely due to the extra variable instantiation step.
As expected, the path constraint in Query C makes it the most time consuming
in our sample. Paths of inde nite length require computing transitive closures,
which is problematic for most model querying approaches (see [
Query size = 50 Fig. 4. Execution times for successful and unsuccessful queries Successful queries Unsuccessful queries The largest threat to validity of our evaluation is the nature of the models it is based on: they originate in academical course work. However, the models are realistic in the sense that their structure, size, and complexity resemble those of models that we have encountered in industry. The same caveat applies to the queries, as we cannot assert that the sample used is representative of practical applications. Furthermore, there is no research on what realistic queries are. We attempt to mitigate this threat by considering a variety of query sizes and types. 4.4
Comparison and Discussion Models an order of magnitude larger than the ones we have considered are not uncommon in practice. Based on Figure 3b, we estimate that a VMQL query consisting of 20 model elements will be executed on a model containing 104 elements in 10 seconds. Similarly, based on Figure 3b, we deduce that queries containing more than 50 elements lead to execution times in the order of seconds on moderately large models. Therefore, scenarios such as large-scale online model di erencing for model version control are outside the scope of our solution.
Table 3 summarizes performance experiments reported for model and
process querying approaches. The performance of VMQL is comparable to existing
ad-hoc model querying solutions, but is surpassed by model repository querying
approaches which employ o ine element indexing, a process requiring up to
several hours to complete [
As mentioned in Section 1, query by-example solutions are more di cult
to scale than navigational approaches (e. g. OCL) due to the large number of
source model elements to be considered at the start of the matching process.
To address this issue, the VMQL matching algorithm prunes the search space
based on element types and xed-valued meta-attributes. Local-search based
graph pattern matching improves this heuristic by taking into account common
structures identi ed in a set of typical models or in the source model itself [
Due to the generality of the matching algorithm, the performance gures reported for VMQL are independent of modeling language and diagram type. 5
Model querying is an important topic in Model-Based Software Engineering
(MBSE), both in itself and as a part of other operations (e. g. model
transformation). In this area, the topic of fast ad-hoc querying has been addressed by
EMF-IncQuery [
In Business Process Modeling (BPM), model querying plays several roles,
including compliance veri cation and process template discovery. BP-QL [
The related problem of e ciently querying model repositories has been
addressed by both the MBSE and BPM communities. Approaches originating in
MBSE (IncQuery-D [
In this paper we have shown that the performance of VMQL is adequate for the task of interactive, ad-hoc model querying. On the other hand, VMQL is outperformed by approaches designed for model repository querying. However, such approaches require substantial model pre-processing, which makes them less suitable for the ad-hoc model querying scenario addressed by VMQL.
We have previously shown that, compared to other model query languages,
VMQL o ers superior usability and generality [
As future work, we intend to study the scalability of our implementation to ultra-large sized models, as well as the impact of VMQL annotations on performance. We also plan to extend our approach to address model warehouse querying. This will likely demand a redesign of the matching algorithm to take advantage of caching techniques and other types of pre-processing.