L Rincón

G Giraldo
email: glgiraldog@unal.edu.coraul.mazo

R Mazo

C Salinesi
email: camille.salinesi@univ-paris1.fr

An Ontological Rule-Based Approach for Analyzing Dead and False Optional Features in Feature Models

Keywords: Feature Models, Defects, Ontologies, Software Engineering I

Product lines engineering uses Feature Models (FMs) as a notation to represent variability and commonality in families of products. One of the well-known issues of FMs is that they may have defects that can drastically diminish the benefits of the product line approach. Two of these defects are dead features and false optional features. Dead features are features absent from any valid product of the product line. False optional features are features declared as optional but actually required in all valid products. These two types of defects are undesirable in FMs because they give a wrong idea of domain that represents the FM. Several techniques documented in literature help to identify dead and false optional features. However, only few of them tackle the problem of identifying the causes of these defects. Besides, the explanations they provide are cumbersome and hard to understand by humans. In this paper, we propose an ontological rule-based approach to (i) identify dead and false optional features in FMs; (ii) identify certain causes of these defects; and (iii) explain these causes in natural language. Moreover, we propose a collection of rules that (i) formalize some cases that produce dead and false optional features; (ii) find the FM's elements that causes each defect; and (iii) explain why a feature is dead or false optional. This collection of rules helps modelers to correct the defects found in FMs and helps prevent the occurrence of new ones. We illustrate our approach in a reference model from literature. A preliminary empirical evaluation of our approach, using a benchmark composed of 31 FMs of sizes up to 150 features, shows that the proposal is effective, accurate and scalable.

INTRODUCTION

A Software Product Line (SPL) is a family of related software systems with common and variable functions whose first objective is reusability [START_REF] Bosch | Design and Use of Software Architectures[END_REF]. Extensive research and industrial experience have widely proven the significant benefits of Software Product Line Engineering (SPLE) practices. Among them are: reduced time to market, increased asset reuse and increased software quality [START_REF] Clements | Software Product Lines: Practices and Patterns[END_REF]. SPLE usually uses Product Line Models (PLMs) to represent the correct combination of features that represent valid products.

Feature Models (FMs) are a common language to represent PLMs in order to describe the features and their dependencies for creating valid products [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF]. FMs have also proven useful to communicate effectively with customers and other stakeholders such as marketing representatives, managers, production engineers, system architects, etc. Consequently, having FMs that correctly represent the domain of the product line is of paramount importance to the success with the SPLE production approach.

However, creating models with features that correctly represent the domain described by the model is not trivial [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF]. In fact, when a FM is constructed, defects may be unintentionally introduced. Dead and false optional features are two types of defects directly related to the semantic of FMs. A feature is dead if it cannot appear in any product of the product line [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF]. A feature is false optional if it is declared as optional, but it appears in all products of the product line [START_REF] Zhang | A Propositional Logic-Based Method for Verification of Feature Models[END_REF]. Due to the ability of FMs to derive a potentially large number of products, any defect in a FM will inevitably affect many products of the product line [START_REF] Mazo | Conformance Checking with Constraint Logic Programming: The Case of Feature Models[END_REF].

Numerous researches focus on identifying dead and false optional features in FMs [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF], [START_REF] Zhang | A Propositional Logic-Based Method for Verification of Feature Models[END_REF], [START_REF] Czarnecki | Cardinality-based Feature Modeling and Constraints: A progress Report[END_REF][START_REF] Salinesi | Defects in Product Line Models and how to Identify them[END_REF][START_REF] Elfaki | Deficiencies in Feature Models[END_REF][START_REF] Thüm | FeatureIDE: An extensible framework for feature-oriented software development[END_REF]. Others approaches focus on identifying dead and false optional features and identifying the causes that produce these defects [START_REF] Trinidad | Abductive Reasoning and Automated Analysis of Feature models: How are they connected[END_REF], [START_REF] Trinidad | Automated Error Analysis for the Agilization of Feature Modeling[END_REF]. Some others works propose even using ontologies to represent FMs [START_REF] Czarnecki | Feature Models are Views on Ontologies[END_REF][START_REF] Sandkuhl | Enterprise Ontology and Feature Model Integration -Approach and Experiences from an Industrial Case[END_REF][START_REF] Lee | An Approach to Analyzing Commonality and Variability of Features using Ontology in a Software Product Line Engineering[END_REF] and others propose using ontologies for identifying defects in FMs [START_REF] Abo | An OWL-Based Approach for Integration in Collaborative Feature Modelling[END_REF][START_REF] Abo | Applying semantic web technology to feature modeling[END_REF][START_REF] Noorian | Feature Model Debugging based on Description Logic Reasoning[END_REF][START_REF] Wang | Verifying feature models using OWL[END_REF]. However, few researchers have addressed the problem of identifying the causes that produce these defects and explain them in a human understandable language. This means that once defects are found it is necessary to manually inspect models to look for why the defects occurred. Once engineers know why defects occurred, they can try to fix them. Our observation is that this is a cumbersome task. Indeed, looking for the causes of defects is about as complicated as looking for defects themselves even when the defect is already known. Therefore, we believe that it is of paramount importance to solve this key problem if we really want FMs verification methods to be effective in an industry context.

Our general goal is to find a generic technique that will point out the cause of various kinds of defects on product line models specified with different notations. In this paper, we propose a first step to achieve this goal. In particular, we propose an ontological rule-based approach to analyze dead and false optional features in FMs, that is: identify features of a FM that are dead or false optional, identify the causes of these defects, and explain each cause in natural language.

We hope this information helps product line engineers to avoid same mistakes in future work, and to understand why dead and false optional features occur [START_REF] Trinidad | Automated Error Analysis for the Agilization of Feature Modeling[END_REF], [START_REF] Spanoudakis | Inconsistency management in software engineering: Survey and open research issues[END_REF].

Our original contribution can be summarized as follows:

1. We propose a framework that (i) identifies dead and false optional features in FMs; (ii) identifies the causes of these defects; and (iii) creates explanations in natural language about each detected cause. 2. We construct a Feature Model Ontology and we formalize-using first-order logic-six rules for identifying dead features and three rules for identifying false optional features. Each rule defines a case in which a feature is dead or false optional. In that way, we know the causes that origin each defect, and we build the corresponding explanation. We defined these rules based on our experience and on the rules found in literature [START_REF] Elfaki | Deficiencies in Feature Models[END_REF]. 3. We developed an automated tool to implement our approach. The results of our validation show that our approach is effective and scalable until FMs of 150 features. The remainder of the paper is as follows. Section II gives a brief overview of the necessary concepts for understanding the framework presented in Section III. Section IV presents the implementation details. Section V presents the evaluation of the precision, scalability and usability of our approach. Section VI presents related research. Finally, Section VII presents the conclusions and suggests future research directions.

II. GENERAL CONCEPTS

A. Features Models

Feature modeling is a notation proposed in [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF] as part of their method for performing a domain analysis of possible products of a target domain. In the SPLE, feature-oriented domain engineers use Feature Models (FMs) to represent commonality and variability of a target domain. FMs show how the domain features are related and show some trade-off decisions that must be made for creating a valid product in the domain of interest [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF].

Under this notation, a feature is a distinctive element that directly affects final users. Each feature is a node in a tree structure, and the model dependencies are directed arcs. The tree structure represents hierarchical organization of the features. The tree's root of the FM represents whole product line and therefore it is part of all valid products of the product line. Each feature represented by a non-root node can be associated with a product only if the feature represented by the father node is associated with the product too. The elements of the feature notation that we use in this paper are presented in Table 1. An example of FM using this notation is presented in Figure 1.

TABLE I. TYPES OF DEPENDENCIES IN FMS

Notation

Type of Dependency Mandatory [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF] Child feature B should be included in all valid products containing the parent feature A and vice versa. It a feature is mandatory and all its ancestors are also mandatory, then, this feature is a full mandatory feature [START_REF] Der Maßen | Deficiencies in feature models[END_REF].

Optional [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF] Child feature B may or may not be included in valid products containing parent feature A. However, if feature B is included in a product, its father A should be included too.

Group cardinality [START_REF] Czarnecki | Formalizing Cardinality-based Feature Models and their Specialization[END_REF] Represents the minimum (m) and the maximum (n) number of child features (B...C) grouped in a cardinality (<m..n>) that a product can have when the father feature (A) is included in the product. If at least one of the child features is included into a product, the father feature should be included too. Requires [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF] Feature B should be included in valid products with feature A. This dependency is unidirectional. Excludes [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF] Features A and B cannot be in valid product at same time. This dependency is bidirectional.

This paper uses an adapted version the Graph Product-Line (GPL) [START_REF] Lopez-Herrejon | A Standard Problem for Evaluating Product-Line Methodologies[END_REF] as running example. The resulting model is presented in Figure 1. We used this example because it is well-known in the product line community, and it was proposed to be a standard case for evaluating product line methodologies [START_REF] Lopez-Herrejon | A Standard Problem for Evaluating Product-Line Methodologies[END_REF]. In order to illustrate our approach, we intentionally introduced 8 dead features (cf., AF2, AF7, AF11, AF12, AF13, AF14, AF15, Connected) and 3 false optional features (cf., AF1, AF9, AF10) into the original model. We used 15 artificial features and 25 dependencies to produce these defects. All features and dependencies have a name for easier identification. We identified artificial features with a capital AF, and artificial dependencies with a capital AD. In addition, we identified original features of the model with their names, and we used a capital OD to build the name of original dependencies.

The members of the GPL are graphs either Directed or Undirected, their edges are Weighted or Unweighted, and their search algorithms are breadth-first search (BFS) or depth-first search (DFS). All products of this FM implement one or more of the following search algorithms: Vertex Numbering (Number), Connected Components (Connected), Strongly Connected Components (StronglyCon), Cycle Checking (Cycle), Minimum Spanning Tree (MST) and Single-Source Shortest Path (Shortest). Moreover, this FM has dependencies that limit the valid combination of features previously described. For instance, the MST algorithm requires Undirected graphs (cf., OD21) and Weighted edges (cf., OD20), and StronglyCon algorithm requires Directed graphs (cf., OD4) and the DFS search algorithm (cf., OD17).

B. Defects in Feature Models

Defects in PLMs are undesirable properties that adversely affect the quality of the model paper, we are interested in two common on FMs: Dead features and false optional features.

A feature is dead when it is not present in any valid product of the product line [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF], [START_REF] Elfaki | Deficiencies in Feature Models[END_REF], [START_REF] Trinidad | Isolated Features Detection in Feature Models[END_REF], [START_REF] Osman | Knowledge Based Method to Validate Feature Models[END_REF] has dead features, the model is not an accurate representation of the domain [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF]. In fact, if a feature belongs to a FM, the feature is important that domain analysts want to represent. Therefore, it should be possible to incorporate that feature in at least one product of the product line [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF].

|A feature is false optional if it is declared as optional in the FM, but it is required in all valid configurations [START_REF] Elfaki | Deficiencies in Feature Models[END_REF], [START_REF] Trinidad | Abductive Reasoning and Automated Analysis of Feature models: How are they connected[END_REF], [START_REF] Trinidad | Automated Error Analysis for the Agilization of Feature Modeling[END_REF]. This defect also gives a wrong idea of domain that represents the FM.

Generally, dead and false optional features group cardinality is wrong defined [START_REF] Mazo | A Generic Approach for Automated Verification of Product Line Models[END_REF] has a misuse among the dependencies features [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF], [START_REF] Zhang | A Propositional Logic-Based Method for Verification of Feature Models[END_REF], [START_REF] Elfaki | Deficiencies in Feature Models[END_REF]. For instance, if a full mandatory feature requires an optional feature, this optional feature became false optional [START_REF] Elfaki | Deficiencies in Feature Models[END_REF].

Ontologies have proven to be useful for dealing with defects in FMs. For instance, in [START_REF] Abo | An OWL-Based Approach for Integration in Collaborative Feature Modelling[END_REF], [START_REF] Abo | Applying semantic web technology to feature modeling[END_REF] semantic relationships between the ontology concepts to define a set of rules to identify defects related conformance checking [START_REF] Mazo | Conformance Checking with Constraint Logic Programming: The Case of Feature Models[END_REF] of the FMs feature is required and excluded at the same time for another feature). These rules allow authors ontology individuals (features) that cause each defect. Noorian et al also use ontologies to identify and fix defects related to the conformance checking of the FM [START_REF] Noorian | Feature Model Debugging based on Description Logic Reasoning[END_REF]. In particular, they use the Pellet identifying defects in FMs represented with logic.

III. PROPOSED SOLUTION

The framework proposed in this paper this section through two sub-sections. The first one presents how we construct the Feature Model Ontology The Feature Model Ontology represents concepts of a meta-model of FMs. The second one presents we call Defect analyzer. This tool identifies optional features in FMs, identifies its caus in natural language why these defects occur. of our proposal framework is presented in Figure 2. [START_REF] Lopez-Herrejon | A Standard Problem for Evaluating Product-Line Methodologies[END_REF] are undesirable properties that the model [START_REF] Salinesi | Defects in Product Line Models and how to Identify them[END_REF], [START_REF] Benavides | Automated reasoning on feature models[END_REF]. In this paper, we are interested in two common types of defects : Dead features and false optional features. when it is not present in any valid [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF], [START_REF] Elfaki | Deficiencies in Feature Models[END_REF], [START_REF] Trinidad | Isolated Features Detection in Feature Models[END_REF], [START_REF] Osman | Knowledge Based Method to Validate Feature Models[END_REF]. When a FM has dead features, the model is not an accurate . In fact, if a feature important in the domain represent. Therefore, it should be possible to incorporate that feature in at least if it is declared as optional in FM, but it is required in all valid configurations [START_REF] Zhang | A Propositional Logic-Based Method for Verification of Feature Models[END_REF],

This defect also gives a wrong idea of ead and false optional features arise when a [START_REF] Mazo | A Generic Approach for Automated Verification of Product Line Models[END_REF] or when the FM dependencies that relate its if a full mandatory feature requires an optional feature, this optional feature useful for dealing with [START_REF] Abo | An OWL-Based Approach for Integration in Collaborative Feature Modelling[END_REF], [START_REF] Abo | Applying semantic web technology to feature modeling[END_REF] authors use the relationships between the ontology concepts to defects related to the (e.g., identify if a feature is required and excluded at the same time for authors to classify the that cause each defect. use ontologies to identify and fix the conformance checking of the FM use the Pellet [START_REF] Sirin | Pellet: A practical OWL-DL reasoner[END_REF] reasoner for represented with description OLUTION he framework proposed in this paper is presented in sections. The first one Feature Model Ontology. represents concepts of a The second one presents the tool that This tool identifies dead and false its causes and explains in natural language why these defects occur. An overview framework is presented in Figure 2. A. Feature Model Ontology An ontology is a formal explicit specification for a shared conceptualization [START_REF] Borst | Construction of Engineering Ontologies for Knowledge Sharing and Reuse[END_REF], [START_REF] Gruber | Toward Principles for the Design of Ontologies Used for Knowledge Sharing[END_REF] FMs, ontologies help to identify and def basic concepts and the dependencies among them Ontologies comprises classes, properties, constraints, and individuals [START_REF] Horridge | A Practical Guide To Building OWL Ontologies Using The Protege-OWL Plugin and CO-ODE Tools Edition 1[END_REF]. Classes are the m to the ontology domain. Properties properties or object properties. Object properties relate ontology individuals among them, whereas data properties relate ontology individuals with concrete values, for example, an integer value. the restrictions that individuals must class; and individuals represent objects in the domain of interest. In this paper, we use Feature Model Ontology (cf. Figure

Feature Model Ontology: How to built it

An ontology is a formal explicit specification for a [START_REF] Borst | Construction of Engineering Ontologies for Knowledge Sharing and Reuse[END_REF], [START_REF] Gruber | Toward Principles for the Design of Ontologies Used for Knowledge Sharing[END_REF]. In the same way that to identify and define the domain concepts and the dependencies among them. Ontologies comprises classes, properties, constraints, are the main concepts related Properties are the data-type properties or object properties. Object properties relate ontology individuals among them, whereas data-type e ontology individuals with concrete values, for example, an integer value. Constraints describe that individuals must satisfy to belong to a epresent objects in the domain of In this paper, we use ontologies to build our cf. Figure 3).

Proposed ontology to represent FM

The Feature Model Ontology represents the FMs concepts in the form of ontology. This representation allows us to exploit g the semantic relationships among the concepts involved in FMs. For instance, we can ask for features that have the same father, or features that are related by mandatory and exclude depethe same cies at same time.

We constructed the Feature Model Ontology using the guide to construct ontologies proposed in [START_REF] Noy | Ontology Development 101 : A Guide to Creating Your First Ontology[END_REF], and adapting the UML-based FM meta-model proposed in [START_REF] Mazo | Conformance Checking with Constraint Logic Programming: The Case of Feature Models[END_REF] (cf. Figure 4). We separate the meta-model class Feature in the ontology classes NotRootFeature and RootFeature with the aim of representing in the ontology that a FM only has one root feature. In addition, in the Feature Model Ontology the meta-model classes correspond to classes of the ontology; the dependencies between metamodel classes are represented as ontology object properties; and the attributes of the groupCardinality meta-model classes are represented as ontology datatype properties. Besides, the inheritance dependencies among the meta-model classes are represented as isA dependencies. It is worth noting that we do not consider feature attributes in our ontology (nor in our FM metamodel) since attributes are not involved in the FM defects in which we are interested in this paper.

Since we use ontology classes and properties to represent the FM meta-model, if an individual violates the conditions defined for the classes or properties during the population process, the ontology becomes inconsistent (this issue is beyond the scope of this paper, but is covered in [START_REF] Mazo | Conformance Checking with Constraint Logic Programming: The Case of Feature Models[END_REF] and [START_REF] Noorian | Feature Model Debugging based on Description Logic Reasoning[END_REF]).

The use of ontologies to represent FMs is not new; in fact, there are several works that use ontologies to represent FMs because ontologies increase the expressiveness level provided by FMs [START_REF] Czarnecki | Feature Models are Views on Ontologies[END_REF], [START_REF] Sandkuhl | Enterprise Ontology and Feature Model Integration -Approach and Experiences from an Industrial Case[END_REF]. Other authors are motivated by the fact that the ontological representation of FMs makes possible to verify consistency between the feature model and its meta-model [START_REF] Noorian | Feature Model Debugging based on Description Logic Reasoning[END_REF]. Even others are motivated by the fact that the ontological representation allows inferring interesting information regarding the FMs; for instance, obtain sibling features [START_REF] Abo | Applying semantic web technology to feature modeling[END_REF]. B. Defect analyzer Defect analyzer is the tool of our proposal that identifies and explains in natural language dead and false optional features. In particular, it receives as input the Feature Model Ontology and the FM to analyze, and produces as result the identified dead and false optional features (if any), the causes of each defect and one explanation in natural language for each identified cause. The Defect analyzer is composed of three parts: the transformer, the identifier of defects and the explainer. Following sub-sections explain and give details of each one of these modules.

1) Transformer

Transformer module is the responsible of populating the Feature Model Ontology with the elements of the FM to analyze. Populate an ontology consists in creating individuals in the classes of the ontology. First, the Transformer reads each element of the input FM, and second, it creates one individual in the corresponding ontology class and fills the properties of each individual.

In our populated Feature Model Ontology, FM dependencies are individuals of one of the following ontology classes: Optional, Mandatory, Requires and Excludes. The class in which the Transformer creates each individual depends of the type of dependency in the FM. For instance, dependency OD2 (cf., Figure 1) is an individual of the Mandatory ontology class.

All features of the FM are individuals by inheritance of the Feature class. Moreover, the FM root is an individual of the RootFeature ontology class, and all other features are individuals of the NotRootFeature ontology class. For instance, in our running example, GPL is an individual of the RootFeature ontology class, and Search is an individual of the NoRootFeature ontology class.

Transformer fills the properties of each individual that it created using information obtained from the input. For instance, according to our Feature Model Ontology, individuals of ontology class Dependency (e.g., R3 in our running example) have the properties hasDependencySource (GPL) and hasDependencyDestination (Search).

Henceforth other components of the Defect analyzer use Feature Model Ontology populated with the information of the FM for analyzing the FM.

2) Identifier of defects Identifier of defects is the module that identifies dead and false optional features and their causes in the populated Feature Model Ontology.

We define a set of rules that represent six specific cases of misuse among the FM dependencies that cause dead features, and three specific cases that cause false optional features. Thus, when the Identifier of defects applies these rules on the populated Feature Model Ontology, the identified features are considered as dead or false optional, and each used rule is a cause that originates the identified dead or false optional features.

The use of rules to detect dead and false optional features is not new. For instance, Van der Massen and Lichter [START_REF] Elfaki | Deficiencies in Feature Models[END_REF] define six rules to identify defects in FODA models (using a feature notation with group cardinalities, as we do, these six rules become two because boolean dependencies can be represented using group cardinalities). However, the approach presented in this paper considers these two rules and seven more that we identified through our academic and industrial experience working with FMs. For each rule, we (i) specify the cause as a general explanation about the defect; (ii) specify the rule in first-order logic; (iii) present an explanation template; and (iv) present an example based in our running example (cf., Figure 1).

We describe each rule with one or more Horn Clauses [START_REF] Van Emden | The Semantics of Predicate Logic as a Programming Language[END_REF]. In our Horn Clauses, antecedents are conditions that must occur together for producing the analyzed defect, and the consequent is that a feature is dead or false optional.

Our collection of 9 rules intends to find and explain the causes of dead and false optional features. The first rule is about optional features that become false optional when they are required by full mandatory features. The second rule is about optional features that become false optional when they make part of a group cardinality (with a full mandatory father) having one or several dead features into the bundle. The third rule is about optional features that become false optional when they are required by another false optional feature. The fourth rule refers to optional features that become dead when they are excluded by full mandatory features. The fifth rule is about optional features that become dead when they are excluded by false optional features. The sixth rule deals with optional features that become dead when one of their ancestors is also dead. The seventh rule is about optional features that become dead when they require dead features. The eighth rule is about optional features that become dead when they make part of a group cardinality that has one or several false optional features into the bundle. Finally, the ninth rule refers to optional features that become dead when they require features that make part of a group cardinality (with a full mandatory father), but the number of required features exceeds the upper bound of the group cardinality.

In the rest of this section (i) we formalize in first-order logic each one of these rules; (ii) we present the template in natural language that each rule use to explain the cause of the particular defect that raise the rule-we call that "explanation template"; and (iii) we show how this rule can be used in our running example (cf. Figure 1). We use the following first-order logic predicates, functions and sets to formalize the rules as Horn Clauses:

• requires(x,y): This predicate indicates that feature x requires feature y. In our running example requires (Cicle,DFS). • excludes(x,y): This predicate indicates that feature x and feature y are mutually exclusives. In our running example excludes(BFS,F2). • ancestor(x,y): This predicate indicates that feature x is an ancestor of feature y. In our running example ancestor (GPL,Weighted) and ancestor (GPL,Search). For the sake of presentation of rules, false optional features with the acronym FO and dead features will be referred with the acronym DF.

Rule FO1: an optional feature becomes false optional when a full mandatory feature requires an optional feature. Formalization:

∀x∈ FMSet , ∀y ∈ OpSet: requires(x,y)→ y ∈ FalseOptionalSet Explanation template: Feature y is false optional because it is required for the full mandatory feature x in the dependency nameDependency(x,y). Application to the running example: Feature AF1 is false optional because it is required for the full mandatory feature Search in the dependency AD15.

Rule FO2: an optional feature becomes false optional when it is grouped by a group cardinality (with a fullmandatory father) having dead features. The feature must be selected to satisfy the lower group cardinality. Formalization: z= group cardinality (with father feature being full mandatory) of the FM at hand m =Lower bound of z DFGroupSet= {Dead features that belong to z} NotDFGroupSet={Features not dead that belongs to z} GroupFeaturesSet= {Features grouped by the group cardinality z} Where,

GroupFeaturesSet ⊆ ModelFeaturesSet ˄ NotDFGroupSet = GroupFeaturesSet \ DFGroupSet Then, |NotDFGroupSet |= m → NotDFGroupSet ⊆ FalseOptionalSet
Explanation template: Feature y is false optional because it must be selected to satisfy the lower bound m of the group cardinality z to which it belongs. Application to the running example: Feature AF10 is false optional because it must be selected to satisfy the lower bound 1 of the group cardinality AD24 to which it belongs.

Rule FO3: an optional feature becomes false optional when it is required by another false optional feature.

Formalization:

∀x ∈ FalseOptionalSet, ∀y ∈ OpSet: requires(x,y)→ y ∈ FalseOptionalSet Explanation template: Feature y is false optional because it is required by the false optional feature x through the dependency nameDependency(x,y). Application to the running example: Feature AF9 is false optional because it is required by the false optional feature AF1 through dependency AD20 Rule DF1: an optional feature becomes dead when it is excluded by a full mandatory feature. Formalization: ∀x ∈ FMSet, ∀y ∈ OpSet: excludes(x,y)→ y ∈ DeadSet Explanation template: Optional feature y is dead because it is excluded by the full mandatory feature x through the dependency nameDependency(x,y). Application to the running example: Optional feature AF11 is dead because it is excluded by the full mandatory feature AF8 through dependency AD17.

Rule DF2: an optional feature becomes dead when it is excluded by a false optional feature. Formalization: ∀x ∈ FalseOptional, ∀y ∈ OpSet : excludes(x,y)→ y ∈ DeadSet Explanation template: Optional feature y is dead because it is excluded by the false optional feature x through the dependency nameDependency(x,y). Application to the running example: Optional feature AF7 is dead because it is excluded by the false optional feature AF9 through dependency AD18.

Rule DF3: a feature becomes dead when one of its ancestors is dead. Formalization: ∀x ∈ DeadSet, ∀y ∈ ModelFeaturesSet: ancestor(x,y)→ y ∈ DeadSet Explanation template: Feature y is dead because x, its ancestor feature, is a dead feature too. Application to the running example: Feature AF14 is dead because AF11, its ancestor feature, is a dead feature too. Features AF12 and AF13 are also identified as dead features for this rule.

Rule DF4: a feature becomes dead when it requires another dead feature. Formalization: ∀x ∈ ModelFeaturesSet, ∀y ∈ DeadSet: requires(x,y)→ x ∈ DeadSet Explanation template: Feature x is dead because it requires the dead feature y. The name of the requires dependency is nameDependency(x,y). Application to the running example: Feature AF15 is dead because it requires the dead feature AF12. The name of the requires-type dependency is AD16. It is worth noting that aforementioned rules are interrelated. These relationships are presented in Figure 5. In this figure, identification process begins with the dead features found by rule DF1 and false optional features found by rule FO1. Then, rules DF2, DF5 and DF6 receive as input the identified false optional features, and identify dead features. Inversely, rule FO2 receives as input dead features and identifies false optional features. Rule FO3 receives false optional features as input and identifies new false optional features, and rules DF3 and DF4 receive dead features as input and identify new dead features. The process ends when the Identifier of defects executes all rules and it does not find new dead or false optional features. On the contrary, if new dead and false optional features appear, the Identifier of defects runs again all rules using false optional and dead features as input to find new ones.

Rule

3) Explainer

Once the Identifier of defects identifies dead and false optional features and their causes, the Explainer constructs explanations in natural language according to the rule used to find each defect. In the explanation process, the Explainer executes the following tasks:

• It obtains the rule used to identify each false optional or dead feature. • It takes the explanation template associated with the rule identified in the previous task. • It fills the explanation template at hand with the corresponding instances from the populated Feature Model Ontology. It is worth noting that if a feature is involved in more than one rule, the Identifier of defect identifies all different rules used to identify this dead or false optional feature. Consequently, the Explainer makes for each rule a different explanation. This is the case of F2 in our example: (i) rule DF1 identifies that feature F2 is dead because it is excluded by the full mandatory feature F3; and (ii) rule DF5 identifies that feature F2 is dead because it belongs to a group cardinality <1..1> where one the features of the bundle (i.e., the children of F1) is a false optional feature (due to the dependency A15). In that case, the Explainer provides an explanation corresponding to (i) and another one corresponding to (ii).

IV. IMPLEMENTATION DETAILS

The method, ontology and rules presented above were implemented into the prototype tool called Defect analyzer using Java, and the JESS (Java Expert System Shell) 1 reasoner to execute queries in SQWRL [START_REF] O'connor | SQWRL: a Query Language for OWL[END_REF]. The tool was tested with the Graph Product Line case study, and with 30 random FMs generated with the BEnchmarking and TesTing on the analYsis (BeTTy) [START_REF] Segura | BeTTy: benchmarking and testing on the automated analysis of feature models[END_REF] tool. Our approach was implemented in two stages. In the first stage, we used Protégé 3.4.8 for creating the Feature Model Ontology to represent concepts of the FMs metamodel. In the second stage, we developed the Defect analyzer.

Broadly, each component of the Defect analyzer works as follows:

(i) Transformer: It uses a library available in the SPLOT website 2 , for reading FMs in the Simple XML Feature Model (SXFM) format. Then, this component uses Jena 3 to manipulate the ontology inside Java for creating individuals in the Feature Model Ontology with the information of the analyzed FM. When the Transformer ends populating the ontology, it creates a new OWL 4 file with the Feature Model Ontology populated with the information of the analyzed FM. The OWL file of our Feature Model Ontology populated with the running example is available online 5 . (ii) Identifier of defects: It uses SQWRL to implement the rules proposed in the Section III. A SQWRL query comprises an antecedent and a consequent expressed in terms of OWL classes and properties. The antecedent defines the criteria that individuals must satisfy to be selected, and the consequent specifies the individuals to select in the query results. In our approach, SQWRL use classes and properties defined in the Feature Model Ontology to query for information of the FM represented as ontology individuals. Identifier of defects executes and manipulates all rules from Java.

For the sake of space, we only present the source code of the first rule (i.e., FO1), in which full mandatory features require optional features. Nevertheless, our nine rules have a similar structure. The whole code is available for download from Internet 5 .

(1) Requires(?z) ^ (2) Optional(?w) ^ (3) hasDependencyDestination(?w, ?a) (4) hasDependencySource(?z, COMODIN) ^ ( 5) hasDependencyDestination(?z, ?a) ^ -> (6) sqwrl:selectDistinct(?a) Lines 1 to 5 define conditions under which a feature can be considered false optional. Line 1 represents any instance of the ontology class Requires and line 2 The Ontology Web Language (OWL) is a language used to describe the classes and dependencies between ontologies. For more information, please visit http://www.w3.org/TR/owl-guide/ 3). Lines 3 to 5 use properties hasDependencyDestination and hasDependencySource to link a dependency with its related features (cf. Figure 3).First argument of these properties is an individual of the class Dependency and the second is an individual of the class Feature. Word COMODIN in line 3 is an argument that takes the values of individuals identified as full mandatory features. The value of COMODIN depends of each rule (e.g., in rule DF2 COMODIN corresponds to false optional features, but in rule DF3, corresponds to dead features). Line 6 is the consequent of this query, which consists in selecting the feature ?a. Note that the SQWRL rule to identify dead or false optional features only selects in the consequent the false optional feature ?a that satisfy the rule, but it does not select the dependencies related to the defect. For each obtained defect, the Explainer executes another SQWRL query to get the necessary information to complete the explanation, as follows:

(iii) Explainer: Once the false optional or dead features are identified by the rules presented in (ii), the Explainer executes a new SQWRL query to get dependencies and other features related to the defect at hand and fill the explanation template of the corresponding rule. For instance, the following SQWRL obtains the dependency and the features related to each false optional feature obtained from rule FO1.

(1) Requires(?z) ^ ( 2) hasDependencyDestination(?z,COMODIN)^ (3) hasDependencySource(?z,?b) -> (4) sqwrl:selectDistinct(?b) ^ (5) sqwrl:selectDistinct(?z) Lines 1 to 3 define necessary conditions that must satisfy individuals ?b and ?z to be selected in the query. Line 1 represents any instance of the ontology class Requires. Lines 2 and 3 define the features source and destination of the ontology class Requires. Word COMODIN in line 2 is the false optional feature found with the query presented in (ii). The consequent of this SQWRL query consists in selecting feature ?b requiring the false optional feature COMODIN and the requires-type dependency ?z from ?b to COMODIN. Thus, the explanation corresponding to the rule FO1 is as follows.

"Feature COMODIN is false optional because it is required for the full mandatory feature ?b in the dependency ?z."

V. PRELIMINARY EVALUATION We assessed the precision, scalability and usability of our approach with 31 models clustered as presented in Table III.

Our preliminary evaluation was undertaken in the following environment: Laptop with Windows 7 Ultimate of 32 bits, processor Intel® Core™ i5-2410M, CPU 2.30 GHz, and RAM memory of 4,00 GB, of which 2.66 GB is usable by the operating system.

1) Precision

We tested our approach in three steps. First, we verified that it did not generate false positives. Second, we verified that the proposed solution identified 100% of dead and false optional features considered in our collection of rules. Finally, if the FMs had dead or false optional features, we manually validated that explanations corresponded to the case that produced the defect, and that the filled spaces in the explanation templates corresponded to real situation for each one of the models.

In the first stage, we compared the dead and false optional features with the results obtained using FaMa [START_REF] Trinidad | Fama framework[END_REF] and VariaMos [START_REF] Mazo | VariaMos : a Tool for Product Line Driven Systems[END_REF]. We found that our proposal identified the 100% of the dead and false optional features that satisfied our rules, with 0% false positive. For the second and third stage, we made a manual inspection of correctness over the running example and two models(randomly selected) of each cluster. We found that our proposal constructed correct explanations; i.e., they corresponded to the cause(s) that originated each defect.

Figure 6 presents the number of dead and false optional features found in each analyzed FM.

2) Computational Scalability

In order to make performance measurement, we executed five times each of the 31 models, which means 155 (31x 5) queries.

The time measures presented in Figure 7 are the average of the five executions of each model. Y-axis corresponds to computation time in milliseconds (ms) that took the Defect analyzer to execute all the tasks of our approach, and X-axis corresponds to the number of features of each model. According to results, our approach took less than 5 sg (5000 ms) executing the Defect analyzer in FM up to 100 features and took about two minutes on models with 150 features.

3)

Usability In order to make more usable our approach, we developed a graphic presentation of our Defect analyzer. Our tool receives a FM, the one selected by the user with the "Choose file" button, in SXFM format. Then, when the user presses the "Analyze" button, the Transformer module, populating the Feature Model Ontology with the elements of the FM at hand. Then, the modules Identifier of defects and Explainer process the Feature Model Ontology with the individuals of the analyzed FM and present results to the user. Figure 8 corresponds to a snapshot of part of the feedback obtained from our tool when we analyzed dead and false optional features in our running example. For each found defect, our tool says what it corresponds to, the cause that origins it, and gives the corresponding explanation in natural language. From the first category, Wang et al. [START_REF] Wang | Verifying feature models using OWL[END_REF] propose representing FMs and their constraints in OWL ontology language. In their proposal, the authors represent each feature as an ontology class, and each dependency as an ontology property. Their study identifies inconsistencies in FMs configurations and provides explanations for inconsistencies. However, their approach does not analyze the FM itself to identify the shortcomings. Abo et al. [START_REF] Abo | Applying semantic web technology to feature modeling[END_REF] propose to use ontologies to represent FMs and facilitate their integration when they represent different views of a product line. Additionally, these authors describe SWRL (Semantic Web Rule Language) rules to validate model consistency. They define each situation that creates an inconsistency as an antecedent, and the elements involved as the consequent. However, their research aims at facilitating integration of different FMs, whereas that our approach focuses on identifying and explaining dead and false optional features and their causes. Moreover, Lee et al. [START_REF] Lee | An Approach to Analyzing Commonality and Variability of Features using Ontology in a Software Product Line Engineering[END_REF] propose to use ontologies to represent FMs in order to analyze their variability and commonality. Even if they use ontologies to represent FM, their approach is different to ours. They use ontologies to analyze the semantic similarity of the FM, whereas our approach uses ontologies to identify dead features and explain their causes. Noorian et al. [START_REF] Noorian | Feature Model Debugging based on Description Logic Reasoning[END_REF] propose to use descriptive logic to: (i) identify inconsistencies in FMs represented in SXFM; (ii) identify inconsistencies in products configured from the product line; and (iii) propose possible corrections.

They implement their approach in a framework that uses OWL-DL to represent FMs and their configurations, and Pellet [START_REF] Sirin | Pellet: A practical OWL-DL reasoner[END_REF] as reasoner. We also use SXFM to represent FMs and description logic to represent our ontology. However, we focus on identifying and explaining dead and false optional features and not on conformance checking [START_REF] Mazo | Conformance Checking with Constraint Logic Programming: The Case of Feature Models[END_REF] as Noorian et al. do. Moreover, our approach could detect structural defects if we verify (using the corresponding Protégé's function) the consistency of the ontology after populating it.

Regarding the second category, several works were carried out to automatically identify dead features (and other defects) on FMs [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF], [START_REF] Zhang | A Propositional Logic-Based Method for Verification of Feature Models[END_REF], [START_REF] Czarnecki | Cardinality-based Feature Modeling and Constraints: A progress Report[END_REF][START_REF] Salinesi | Defects in Product Line Models and how to Identify them[END_REF][START_REF] Elfaki | Deficiencies in Feature Models[END_REF][START_REF] Thüm | FeatureIDE: An extensible framework for feature-oriented software development[END_REF]. However, none of these works deals with identification of causes or explanations of dead and false optional features.

Trinidad et al. [START_REF] Trinidad | Automated Error Analysis for the Agilization of Feature Modeling[END_REF] present an automated method for identifying and explaining defects, such as dead features or false optional features in FMs. The authors transform FMs into a diagnostic problem and then into a constraint satisfaction problem. They automated their approach in FaMa [START_REF] Trinidad | Fama framework[END_REF], an Eclipse Plug-in for automatic analysis of FMs. Their proposal identifies the dead features and false optional features, and minimum set of dependencies necessary to create such features. However, their approach works like a black box, hard-coded in FaMa, where user cannot create new rules to interrogate the FM. Besides, explanations generated by FaMa are not in natural language, but they are rather a list of dependencies that modeler should modify to remove the defect. Thus, FaMa gives the dependencies participating in the defect, but it does not explain the defect itself, which our approach does.

In a more recent work, Trinidad et al. [START_REF] Trinidad | Abductive Reasoning and Automated Analysis of Feature models: How are they connected[END_REF] use abductive reasoning to identify dead features and their causes. Unfortunately, authors do not provide any details or even an algorithm to implement their proposal.

It is worth noting that FaMa finds and explains other dead and false optional features that our approach did not identify. This is because we have not implemented all the cases to identify and explain all causes of dead features or false optional features. FaMa identifies all cases because it uses a constraint satisfaction approach to identify dead features, false optional features and other defects on FMs. However, our rule-based approach is extensible, it allows us to explain in natural language why defects occur, and it allows us to analyze dead and false optional features when FMs are void [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF], three aspects that FaMa does not support.

VII. CONCLUSIONS AND DISCUSSION

In this paper, we proposed an ontological rule-base approach to analyze dead and false optional features. Our defect analysis consists in identifying dead and false optional features in FMs, identifying certain causes of these defects, and explaining these causes in natural language. To operationalize our proposal, we propose an OWL ontology for representing FM and we propose 9 rules that represent certain causes that produce dead or false optional features and have associate an explanation in natural language. These rules were formalized in firstorder logic and implemented in SQWRL and Java. We validated our proposal with a well-known case study and with 30 random features models with until 150 features.

The approach developed in this paper represents an innovative alternative to the ones found in literature [START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF], [START_REF] Zhang | A Propositional Logic-Based Method for Verification of Feature Models[END_REF], [START_REF] Czarnecki | Cardinality-based Feature Modeling and Constraints: A progress Report[END_REF][START_REF] Salinesi | Defects in Product Line Models and how to Identify them[END_REF][START_REF] Elfaki | Deficiencies in Feature Models[END_REF][START_REF] Thüm | FeatureIDE: An extensible framework for feature-oriented software development[END_REF][START_REF] Trinidad | Abductive Reasoning and Automated Analysis of Feature models: How are they connected[END_REF][START_REF] Trinidad | Automated Error Analysis for the Agilization of Feature Modeling[END_REF], [START_REF] Abo | An OWL-Based Approach for Integration in Collaborative Feature Modelling[END_REF][START_REF] Abo | Applying semantic web technology to feature modeling[END_REF][START_REF] Noorian | Feature Model Debugging based on Description Logic Reasoning[END_REF][START_REF] Wang | Verifying feature models using OWL[END_REF], because we not only identify dead and false optional features, but we also identify their causes and build explanations in a human compressible language. We believe that this information could avoid modelers take the same mistakes in others FMs. However, there are other cases outside of the scope of this proposal (e.g. identifying dead features when they are produced for mandatory features whose predecessor is an optional feature). Indeed, it is necessary to continue extending our solution to identify with other rules dead and false optional features.

We are also interested in exploring dependency between dead features and void models, because we detected that many of our rules could identify void models if they are applied with mandatory and false optional features.

Figure 1 .

 1 Figure 1.

Figure 1 .

 1 Figure1. GLP Feature Model based on the one proposed in[START_REF] Lopez-Herrejon | A Standard Problem for Evaluating Product-Line Methodologies[END_REF]

Figure 2 .

 2 Figure 2. Proposed framework overview

Figure 3 .

 3 Figure 3. Proposed ontology to represent FM

Figure 4 .

 4 Figure 4. FM meta-model based on the one proposed in[START_REF] Mazo | Conformance Checking with Constraint Logic Programming: The Case of Feature Models[END_REF]

  • nameDependency(x,y): This function returns the name of a given dependency that relates feature x with feature y. In our running example nameDependency(GPL,Search) returns OD2. • ModelFeaturesSet: This set represents the collection of all features of a feature model. • OpSet: This set represents the collection of all optional features of a feature model. • FMSet: This set represents the collection of all full mandatory features of a feature model. • DeadSet: This set represents the collection of all dead features of a feature model. • FalseOptionalSet: This set represents the collection of all false optional features of a FM. Where OpSet ˄ FMSet ˄ DeadSet ˄ FalseOptionalSet ⊆ ModelFeaturesSet

1 http:

 1 //herzberg.ca.sandia.gov 2 http://www.splot-research.org 3 http://jena.apache.org 4

Figure 5 .

 5 Figure 5. Relationship among our collection of rules represents any instance of the ontology class Optional. Ontology classes Requires and Optional are subclasses of the ontology class Dependency in the Feature Model Ontology (cf.Figure3). Lines 3 to 5 use properties hasDependencyDestination and hasDependencySource to link a dependency with its related features (cf. Figure3).First argument of these properties is an individual of the class Dependency and the second is an individual of the class Feature. Word COMODIN in line 3 is an argument that takes the values of individuals identified as full mandatory features. The value of COMODIN depends of each rule (e.g., in rule DF2 COMODIN corresponds to false optional features, but in rule DF3, corresponds to dead features). Line 6 is the consequent of this query, which consists in selecting the feature ?a. Note that the SQWRL rule to identify dead or false optional features only selects in the consequent the false optional feature ?a that satisfy the rule, but it does not select the dependencies related to the defect. For each obtained defect, the Explainer executes another SQWRL query to get the necessary information to complete the explanation, as follows:(iii) Explainer: Once the false optional or dead features are identified by the rules presented in (ii), the Explainer executes a new SQWRL query to get dependencies and other features related to the defect at hand and fill the explanation template of the corresponding rule. For instance, the following SQWRL obtains the dependency and the features related to each false optional feature obtained from rule FO1.

Figure

Figure 6 .Figure 7 .

 67 Figure 6. Number of defects identified by model size

Figure 8 .

 8 Figure 8. Snapshot corresponding to a part of the results generated from analyzing our FM running example VI. RELATED WORK Two collections of approaches for FM defects cause identification can be met in the literature: those that use ontologies to represent and reason on FMs and the others.From the first category, Wang et al.[START_REF] Wang | Verifying feature models using OWL[END_REF] propose representing FMs and their constraints in OWL ontology language. In their proposal, the authors represent each feature as an ontology class, and each dependency as an ontology property. Their study identifies inconsistencies in FMs configurations and provides explanations for inconsistencies. However, their approach does not analyze the FM itself to identify the shortcomings. Abo et al.[START_REF] Abo | Applying semantic web technology to feature modeling[END_REF] propose to use ontologies to represent FMs and facilitate their integration when they represent different views of a product line. Additionally, these authors describe SWRL (Semantic Web Rule Language) rules to validate model consistency. They define each situation that creates an inconsistency as an antecedent, and the elements involved as the consequent. However, their research aims at facilitating integration of different FMs, whereas that our approach focuses on identifying and explaining dead and false optional features and their causes. Moreover, Lee et al.[START_REF] Lee | An Approach to Analyzing Commonality and Variability of Features using Ontology in a Software Product Line Engineering[END_REF] propose to use ontologies to represent FMs in order to analyze their variability and commonality. Even if they use ontologies to represent FM, their approach is different to ours. They use ontologies to analyze the semantic similarity of the FM, whereas our approach uses ontologies to identify dead features and explain their causes. Noorian et al.[START_REF] Noorian | Feature Model Debugging based on Description Logic Reasoning[END_REF] propose to use descriptive logic to: (i) identify inconsistencies in FMs represented in SXFM; (ii) identify inconsistencies in products configured from the product line; and (iii) propose possible corrections.They implement their approach in a framework that uses OWL-DL to represent FMs and their configurations, and Pellet[START_REF] Sirin | Pellet: A practical OWL-DL reasoner[END_REF] as reasoner. We also use SXFM to represent FMs and description logic to represent our ontology. However, we focus on identifying and explaining dead and false optional features and not on conformance checking[START_REF] Mazo | Conformance Checking with Constraint Logic Programming: The Case of Feature Models[END_REF] as Noorian et al. do. Moreover, our approach could detect structural defects if we verify (using the corresponding Protégé's function) the consistency of the ontology after populating it.Regarding the second category, several works were carried out to automatically identify dead features (and other defects) on FMs[START_REF] Kang | Feasibility Study Feature-Oriented Domain Analysis ( FODA )[END_REF],[START_REF] Zhang | A Propositional Logic-Based Method for Verification of Feature Models[END_REF],[START_REF] Czarnecki | Cardinality-based Feature Modeling and Constraints: A progress Report[END_REF][START_REF] Salinesi | Defects in Product Line Models and how to Identify them[END_REF][START_REF] Elfaki | Deficiencies in Feature Models[END_REF][START_REF] Thüm | FeatureIDE: An extensible framework for feature-oriented software development[END_REF]. However, none of these works deals with identification of causes or explanations of dead and false optional features.

  DF5: a feature becomes dead if it belongs to a group cardinality and the number of false optional features is equal to the cardinality upper bound. Feature y is dead because it cannot be selected from its group cardinality z, since the upper bound n of the group cardinality z is attained with the following false optional features FOGroupSet. Application to the running example: Feature AF2 is dead because it cannot be selected in its group cardinality AD23, since the upper group cardinality 1 of AD23 is satisfied with the following false optional features: F1. OpSet, ∀x ∈ GroupFeaturesSet: includes(y,x) → x∈ IncludesFeaturesSet |IncludesFeaturesSet| ≥ n →y ∈ deadSet Explanation template: Feature y is dead because it requires the feature(s) IncludesFeaturesSet that belong(s) to the group cardinality z. Required feature(s) exceed(s) the upper bound n of the group cardinality z. Application to the running example: Feature Connected is dead because it requires the feature(s) Directed, Undirected that belong(s) to the group cardinality OD26. Required feature(s) exceed(s) the upper bound 1 of the group cardinality OD26.

	Then,
	∀y ∈
	Formalization:
	Z: group cardinality of the FM at hand
	n: Upper cardinality of z
	FOGroupSet: set of false optional
	features that belong to z
	NotFOGroupSet: set of features not
	false optional that belongs to z}
	GroupFeaturesSet= set of features
	grouped by the group cardinality z
	Where,
	FOGroupSet ⊆ GroupFeaturesSet⊆
	ModelFeaturesSet ˄
	NotFOGroupSet = GroupFeaturesSet \
	FOGroupSet
	Then,
	|FOGroupSet| = n → NotFOGroupSet ⊆
	DeadSet
	Explanation template: Rule DF6: an optional feature becomes dead if it requires
	features that belongs to group cardinality, but the number
	of required features is greater than the upper bound of the
	group cardinality.
	Formalization:
	z: group cardinality (with father
	feature being full mandatory) of the
	FM at hand
	n: upper cardinality of z
	DFGroupSet: set of dead features that
	belong to z
	IncludesFeaturesSet: set of features
	that belong to z and are includes by
	another feature of the FM
	GroupFeaturesSet: set of features
	grouped by z
	Where,
	IncludesFeaturesSet ⊆
	GroupFeaturesSet⊆ ModelFeaturesSet

TABLE II

 II

				.
	FEATURE MODELS COLLECTION BENCHMARK
	Number of	5	25	32	50	75	100	150
	features
	Number of models	5	5	1	5	5	5	5
	% of requires
	and excludes	40	40	18	40	40	40	40
	relationship

ACKNOWLEDGMENT

We perform this research under the stage of the Master of Engineering -Engineering Systems financed by the National University of Colombia and the Informatics Research Center (CRI) at University Paris I Pantheon Sorbonne in France.


Mathias Kleiner
email: mathias.kleiner@ensam.eu

Marcos Didonet
email: marcos.ddf@inf.ufpr.br

Del Fabro

Davi De Queiroz

Santos
email: daqsantos@inf.ufpr.br

Transformation As Search

In model-driven engineering, model transformations are considered a key element to generate and maintain consistency between related models. Rule-based approaches have become a mature technology and are widely used in different application domains. However, in various scenarios, these solutions still suffer from a number of limitations that stem from their injective and deterministic nature. This article proposes an original approach, based on non-deterministic constraint-based search engines, to define and execute bidirectional model transformations and synchronizations from single specifications. Since these solely rely on basic existing modeling concepts, it does not require the introduction of a dedicated language. We first describe and formally define this model operation, called transformation as search, then describe a proof-of-concept implementation and discuss experiments on a reference use case in software engineering.

Introduction

In existing Model-driven Engineering (MDE) approaches, model transformations are a key element for performing operations between different models. These operations may be of different nature, such as migration, evolution, composition, exchange, and others. Despite the existing solutions being very different on the set of available capabilities (see [START_REF] Czarnecki | Feature-based survey of model transformation approaches[END_REF] for a survey), most of them are rule-based approaches.

These approaches have a simple and efficient principle: given a source metamodel M M a and a target metamodel M M b, the developer defines a set of pattern-matching rules to transform all the model elements from M M a into elements of M M b. These transformation engines have a deterministic behavior, i.e., one source model always produces the same target model. In addition, the transformation rules are unidirectional and need to be fully-specified, i.e., it is necessary to write rules that cover all the (relevant) elements of M M b.

These properties limit the scope of most transformation languages in various scenarios [START_REF] Czarnecki | Bidirectional transformations: A cross-discipline perspective[END_REF]. For instance it may be hard to write rules that cover all the transformation cases. Similarly, it is sometimes desirable to produce more than one target model in order to study the alternatives. Bidirectional behavior requires to write or derive a reverse transformation. Finally, these approaches hardly allow to maintain models consistency without additional mechanisms.

Some of these limitations are directly linked to the fact that most tools do not allow for disjunctions (i.e., choice points in the sense of combinatorial problems) and take decisions solely on the basis of the source model. Indeed searching for multiple target models requires non-deterministic properties: a given source model may produce zero, one or multiple target models that satisfy a set of constraints.

In this paper, we present a novel approach that uses constraint-based search for executing model transformations and synchronizations. At this stage, our challenge is to present this approach to the community and to integrate it at its best in current MDE practices. To this aim, we reuse and extend a model search operation proposed in previous work [START_REF] Kleiner | Model search: Formalizing and automating constraint solving in MDE platforms[END_REF] as well as its notion of partial model: a model whose known constituents actually conform to their corresponding metamodel, but that should be interpreted with a weaker conformance than the classical closed-world interpretation used in the MDE community.

The core idea is to create a unified metamodel containing source, transformation and target constraints. Different scenarios (creation of target model(s), synchronization of existing models, and others) then mainly resolve to searching for conforming model(s). First, we define a (potentially partial) set of correspondences (i.e., transformation constraints) between the source and target metamodels using basic modeling concepts. Second, we transform the input artifacts into a solver which executes the scenario through a generic model search operation. As a result the engine produces none, one or several output models that contain the solution(s) and its generation traces. The specifications are bidirectional and flexible: they can be used to produce either the source or the target model, or even propagate changes from one model to the other depending on the chosen scenario. Another interesting property is that one could introduce an optimization criterion that will be used by the search process to produce one specific solution (the "best" one).

Plan of the article Section 2 briefly introduces the context of model-driven engineering, constraint programming main principles, and recalls necessary definitions from previous work on model search. Section 3 formally defines the transformation as search operation, and describes a generic process for its realization along with a running example. Section 4 proposes a prototype implementation and discusses preliminary experiments on a reference use case. Finally, Section 5 discusses related work and Section 6 concludes.

Context

Introduction to MDE and model transformation

Model Driven Engineering considers models, through multiple abstract representation levels, as a unifying concept. The central concepts that have been introduced are terminal model, metamodel, and metametamodel. A terminal model is a representation of a system. It captures some characteristics of the system and provides knowledge about it. MDE tools act on models expressed in precise modeling languages. The abstract syntax of a modeling language, when expressed as a model, is called a metamodel. The relation between a model and the metamodel of its language is called conf ormsT o. Metamodels are in turn expressed in a modeling language for which conceptual foundations are captured in an auto-descriptive model called metametamodel. The main way to automate MDE is by executing operations on models. For instance, the production of a model M b from a model M a by a transformation M t is called a model transformation. The OMG's Query View Transform (QVT) [START_REF][END_REF] defines a set of useful model operations languages. In particular, it defines a language called QVToperational which is restricted to unidirectional transformations scenarios, and a language called QVT-relational which can be used for bidirectional and synchronization scenarios. There are multiple model definitions in the literature (see [START_REF] Kühne | Matters of (meta-)modeling[END_REF] for a deep study), we refine in this article the ones introduced in [18]3 .

Definition 1 (model).

A model M is a triple < G, ω, µ > where:

-G is a directed labelled multigraph, ω (called the reference model of M) is either another model or M itself (i.e., self-reference) µ is a function associating nodes and edges of G to nodes of G ω (the graph associated to its reference model ω)

Definition 2 (conformance). The relation between a model and its reference model is called conformance and noted conf ormsT o.

Definition 3 (metametamodel).

A metametamodel is a model that is its own reference model (i.e., it conf ormsT o itself ).

Definition 4 (metamodel).

A metamodel is a model such that its reference model is a metametamodel.

Definition 5 (terminal model).

A terminal model is a model such that its reference model is a metamodel.

Constrained metamodels

The notion of constraints is closely coupled to MDE. Engineers have been using constraints to complete the definition of metamodels for a long time, as illustrated by the popular combination UML/OCL [START_REF]OCL 2.0 specification[END_REF]. Constraints can be, for instance, checked against one given model in order to validate it. In our approach we will always consider metamodels with potential constraints attached. We refine in this article definitions from [START_REF] Kleiner | Model search: Formalizing and automating constraint solving in MDE platforms[END_REF] to formally define the combination:

Definition 6 (constrained metamodel). A constrained metamodel CM M is a pair < M M, C > where M M is a metamodel and C is a set (a conjunction) of predicates over elements of the graph G associated to M M . We will consider an oracle that, given a model M , returns true (noted M ∈ C(M M ) where C(M M ) is the set of all valid models) iff M satisfies all predicates from C.

The conformance relation between a model and its reference is then naturally extended to constrained metamodels.

Definition 7 (constrained conformance). A model M conformsTo a con- strained metamodel CM M iff it conf ormsT o M M and M ∈ C(M M ).
Many languages can be used to define predicates (i.e., constraints) with different levels of expressiveness. OCL supports operators on sets and relations as well as quantifiers (universal and existential) and iterators. To ease the specification of metamodel static constraints, we use in this article an OCL-compatible extension (OCL+ [START_REF]OCL+ usecase[END_REF]) that extends it with multi-context constraints.

Introduction to constraint programming

Constraint programming (CP) is a declarative programming technique to solve combinatorial (usually NP-hard) problems. A constraint, in its wider sense, is a predicate on elements (represented by variables). A CP problem is thus defined by a set of elements and a set of constraints. The objective of a CP solver is to find an assignment (i.e, a set of values for the variables) that satisfy all the constraints. There are several CP formalisms and techniques [START_REF] Jaffar | Constraint logic programming: A survey[END_REF] which differ by their expressiveness, the abstractness of the language and the solving algorithms.

Introduction to model search

A solver-independent integration of constraint programming, called model search, for the automatic generation (or completion) of constrained models has been described in [START_REF] Kleiner | Model search: Formalizing and automating constraint solving in MDE platforms[END_REF]. This article builds on those foundations to propose a generic model transformation method based on constrained search. Therefore we need to briefly recall here the main principles and definitions of the model search operation.

Definition 8 (relaxed metamodel). Let CM M =< M M, C > (with M M =< G, ω, µ >) be a constrained metamodel. CM M r =< M M r , C r > (with M M r =< G r , ω, µ >) is a relaxed metamodel of CMM (noted CM M r ∈ Rx(CM M )) if and only if G M Mr ⊆ G M M and C r ⊆ C.
In other words, a relaxed metamodel is a less constrained (and/or smaller) metamodel. A simple one can be obtained by the removal of all constraints. Computing such a relaxed metamodel, a simple operation which can obviously be done easily with existing techniques, is called relaxation in the following.

Definition 9 (partial model, p-conformsTo). Let CM M =< M M, C > be a constrained metamodel and M r a model.

M r p-conf ormsT o CM M iff it conforms to a metamodel CM M r such that CM M r is a relaxed metamodel of CM M (CM M r ∈ Rx(CM M )). M r is called a partial model of CM M .
Informally, a partial model is simply understood as being an incomplete model.

Definition 10 (model search). Let CM M =< M M, C > be a constrained metamodel, and M r =< G r , M M r , µ r > a partial model of CM M . Model search is the operation of finding a (finite) model M =< G, M M, µ > such that G r ⊆ G, µ r ⊆ µ (embedding i.e, ∀x ∈ Gr, µ(x) = µ r (x)), and M conf ormsT o CM M .
In other words, model search extends a partial model into a "full" model conforming to its constrained metamodel (or generates one when an empty request M r is given). An example process to achieve this operation in a MDE framework We may thus consider model search as a model transformation where the source (metamodel and model) is an instance of a non-deterministic (combinatorial) problem and the target model is a solution (if any exists). From the CP point of view, the target metamodel acts as the constraint model whereas the source model (the request) is a given partial assignment that needs to be extended. For deeper information on how this operation is formalized, achieved and integrated as a first-class MDE operation, the reader is kindly referred to [START_REF] Kleiner | Model search: Formalizing and automating constraint solving in MDE platforms[END_REF].

Transformation As Search

The following proposes to generalize model search to constraint-based model transformation/synchronization by considering different source and target metamodels. The main idea is to define the transformation/synchronization as a set of relations and constraints between elements of the metamodels that are to be related (these may be called weaving links). All these artifacts are then unified into a transformation metamodel. By applying model search on this unified metamodel, a model which contains valid solution model(s) is created.

In the following, we first introduce a running example of a classic transformation scenario (creation of a single target model out of a single source model) which is then used to illustrate the generic process. Its adaptation to other scenarios is then briefly discussed.

Running example

The chosen use case is a transformation of a class schema model (M M A ) into a relational schema model (M M B ), known as the Class2Relational transformation. This use case is well-known due to its large applicability and it has been studied in other works to demonstrate different aspects about transformation languages, such as [START_REF][END_REF], [START_REF] Lawley | Practical declarative model transformation with tefkat[END_REF], and others. The initial metamodels are extracted from the public transformation repository at [START_REF]ATL Class to Relational transformation[END_REF] and illustrated at both sides of Figure 2 (some elements have been omitted to improve readability).

The main scenario, which process is described in the following is the creation of a target model (a relational schema) from a source model (a class schema). Definition 12 (transformation metamodel). We call transformation metamodel between metamodels

Process

CM M A =< M M A , C A > and CM M B =< M M B , C B >, using a weaving metamodel CM M W , a constrained metamodel CM M T defined by CM M T =< M M T , C T >, where M M T = M M A ∪ M M B ∪ M M W and C T = C A ∪ C B ∪ C W .
Obviously, unification turns inter-model references in the weaving metamodel into intra-model references in the transformation metamodel. Searching for a target model Figure 4 shows how a target model can be created by applying model search to the transformation metamodel. In this scenario we have an exogenous unidirectional transformation from one source model (M A ) to a target model (M B ). The first step is to define the model search request. In this scenario it is simply a copy of the source model. In our running example, it corresponds to the "Family" class schema at the top of Figure 5. From definition 10, a valid request must be a partial model of the transformation metamodel (CM M T ). This property is ensured by the following proposition:

Proposition 1. For all model M A that conformsTo CM M A , M A is a partial model of (or p-conf ormsT o) CM M T . Proof. From definition 9 of p-conf ormsT o, it resolves to finding a relaxed meta- model CM M T r =< M M T r , C T r >∈ Rx(CM M T ) such that M A conf ormsT o CM M T r .
From definition 7 of conformance, this requires that (1)

M A conf ormsT o M M T r and (2) M A ∈ C(M M T r ). Let CM M T
r be the relaxed metamodel of CM M T such that M M T r = M M T and C T r = ∅ (i.e., the one obtained by removing all constraints). ( 2) is obviously true as there are no predicates to satisfy. (1) requires that M M T r can be a reference model of M A , i.e., its graph G T r contains all nodes (meta-elements) targeted by the graph G A of M A . This is clearly true since by definition 12 of Fig. 5. Input and ouput from the running example (scenario 1) as instance diagrams CM M T we have M M A ⊂ M M T (in particular G A ∈ G T ), and on the other hand M M T r = M M T (in particular G T r = G T ). The second step is to perform the model search. This operation extends any model M A that conforms to CM M A into a model M T that conforms to CM M T (when there are solutions). By extending the source model, search produces a model M T which contains both the target elements and the weaving elements (these can be understood as the transformation traces). Additionally, model search ensures that the target elements satisfy their metamodel constraints, and optimization or preferences may be applied to discriminate between different solutions. To avoid adding source elements to the produced model, as usually expected in classical target creation scenarios, a set of model-level constraints can be added to CM M T in order to "freeze" the source model. The final step is to isolate the target model M B that conforms to CM M B . This can easily be obtained by removing from M T any element that is not associated to CM M B . In our example, a sample result is the "Family" relational schema illustrated at the bottom of Figure 5.

Other scenarios

The described scenario is a unidirectional one-to-one operation, but the approach is naturally bidirectional and can be used for different scenarios by varying the search request. Indeed, it suffices to use M B as the request to obtain the reverse transformation (production of a model M A ). Additionally, the synchronization scenario (propagating source or target model modifications to the other one) can also be achieved with the same specifications: by using the union of the two models (M A and M B ) as the request, model search will extend them to satisfy the transformation constraints, and thus update source, target or both models (depending on the desired behaviour). Note that many CP solvers are restricted to constructive modifications since allowing for removal of elements from the request may yield tractability issues. However the approach itself does not prevent it and is only limited in this sense by the capabilities of the chosen underlying solver. All these scenarios are described and experimented on the running example in the next Section. Finally, though these are not studied nor experimented in this paper, multisource and/or multi-target transformations could also be achieved: it suffices to add the corresponding metamodels and weaving constraints to CM M T , and corresponding models to the request. Indeed, constraints may have any arity (i.e., a single constraint may weave multiple metamodels elements). In all these scenarios, the preceding propositions naturally hold as long as requests are partial models of CM M T .

Implementation and experiments

In this section we first present the components used for implementing a prototype software chain. Second, we further describe the chosen use case and its realization on different scenarios. Finally, we summarize the experimentation results.

Implementation

The transformation as search (TAS) components were implemented using:

the Eclipse Modeling Framework (EMF) [START_REF]EMF[END_REF] for defining, viewing and manipulating the various (meta)models presented in the preceding Section. the ATL engine [START_REF] Jouault | Transforming models with ATL[END_REF] for writing/executing the rule-based transformations of the process (unifying into CM M T , projecting Ecore-OCL+ to/from the solver language, isolating the target model from the solution model). -Alloy/SAT [START_REF] Jackson | Automating first-order relational logic[END_REF] as the constraint language/solver. The software chain is freely available from a single package at [START_REF]Class-Relational usecase[END_REF].

Use case

We have defined 3 scenarios: The first goal was to experiment whether one single specification could handle different scenarios. The specification consists of a weaving metamodel, shown in the middle of Figure 2, which provides the basic correspondences between left and right metamodels. The figure shows correspondences between first-class elements (e.g., classes "Class" and "Table ", classes "Attribute" and "Column", etc.). We defined a set of additional constraints, written in OCL+ (as illustrated in the code listing below), to further specify the weaving. Similarly to other transformation techniques, these specifications may be written in different ways.

We provide results with two versions of the specifications, each of them used throughout all scenarios, to test the capabilities and behavior of the search. The first version (V1) mimics the behavior of the original (ATL) use case, in particular it creates simple integer columns for foreign keys. The second version (V2) has a more explicit (and better) handling of table primary/foreign keys. It also defines different weaving tables for each connected elements, allowing to write more specific constraints. Both versions can be found in package [START_REF]Class-Relational usecase[END_REF].

As an example, the (V1) OCL+ excerpt below depicts 4 different kind of constraints attached to the weaving metamodel from Figure 2. Constraint (1) specifies equality between the "name" attribute of weaved "Datatype" and "Type" (similar constraints are given for "Attribute", "Class", "Table " and "Column"). Constraint (2) maps mono-valued attributes to columns (a similar constraint is given for multi-valued attributes/tables and classes/tables). Constraint (3) ensures that weaved attributes/columns have a weaved datatype/type (a similar constraint handles classes and integer key columns). Constraint (4) ensures that attributes cannot have both a weaved table and a weaved column (a similar constraint handles tables with classes and attributes).

Experiments

We experimented on the Family use case [START_REF]ATL Class to Relational transformation[END_REF], which class schema is illustrated on the top of Figure 5. This application is used as a proof-of-concept of our approach.The Alloy solver needs a specified pool of available elements: we set a maximum of 25 instances. We executed the model operations on an Intel Core Duo machine with 2.4GHz and 4GB of RAM. We used the Alloy Analyzer 4.2 with the MiniSat solver for generating search solutions. We summarize the results in Table 1. The given execution times correspond to the search of the first satisfying instance. They do not include the problem generation (projections from/to Ecore/Alloy, Alloy's compilation into SAT) since these are negligible in all our experiments and the metamodel projection only has to be done once for a given specification. Alloy does not natively support strings as datatypes, we thus used predefined atoms and scalar equality (i.e., "nameS" is the string "name"). Both versions of the specifications generate the relational schema illustrated on the bottom of Figure 5. However, if we cycle through the solutions, V1 also proposes solutions with additional "orphan" tables. This can be prevented with a constraint that forbids creation of elements without a weaving association. In the reverse transformation scenario (2), we used the exact generated target model (the Family table schema) as input request, freezing again the initial model through the pool of 25 available instances. Both versions generate the original class schema. However in V1, it is not the first found solution. Indeed, the first proposition is a class schema with an "EmailAdresses" class (referenced by "Person") and a "Members" class (referenced by "Family" and with an outgoing reference to "Person"). This is a valid but nevertheless surprising solution at first. If desired, it is possible to prevent such behaviour with a weaving constraint that forces tables to become attributes whenever possible. This is done in V2 using the (explicit) table keys as conditions. In the synchronization scenario (3), we used the whole transformation result from scenario 1 to create the input request: the class and relational schemas (as shown in Figure 5), plus the generated weaving elements between them (transformation traces, not shown in the Figure ). We then added to the class schema an "Animal" class and its outgoing "owner" reference to the "Person" class. The goal was to test the propagation of changes to the table schema. Both versions update accordingly the relational schema, adding an "Animal" table with an "owner" (foreign) key column. The lower execution times are easily explained: search space is reduced since most of the model is given as input (only a limited number of SAT variables have to be assigned).

Analysis and future work

Experiments on these examples show that valid models can be created in different scenarios using single specifications, and that different solutions can be proposed to the designer. Although it is only a first step to assess the potential and flexibility of the approach, this prototype implementation can serve as a proof of feasibility. It is obvious that the produced models could already be obtained using existing transformation techniques, though this may require to write (or derive) additional specifications to handle all scenarios. Also, these experiments raise a number of modeling and operational challenges that will be considered in future work. From the modeling point of view, defining specifications as weaving elements and constraints can be confusing for a designer used to traditional rule-based engines. For a given set of constraints, cycling through solutions or testing different scenarios may reveal a need to incrementally narrow some constraints, but also exhibit unexpected valid solutions. To ease the writing of specifications, a set of weaving templates can be provided as guidelines. Similarly, a mapping from a more specific language (such as QVT-relations [START_REF][END_REF]) to an equivalent set of weaving templates can be studied. Also, additional scenarios can be considered. For instance, two independently-obtained models can be given to test (and exhibit) whether a valid mapping is able to relate them. The optimization/preferences capabilities of the approach are also to be experimented more deeply. Overall, an extensive evaluation on different sets of examples is necessary to confirm and exhibit the benefits that can be envisioned compared to existing techniques. From the operational point of view, this prototype implementation will be extended and experiments conducted to assess tractability on larger models. Early experiments on a larger application, a graduate course management system extracted from a real-world system, show that the current Alloy-based implementation does not easily scale to medium-size models. The size of the instance pool is a major factor, and SAT compilation rapidly induces a combinatorial explosion in transformation scenarios (about 30000 variables and 10 minutes execution time). The propagation scenario seems more tractable (about 1 minute). Source and details of these experiments are also included in the package for reference. It is obvious that constraint solving is more (time) expensive than rule-based approaches (both theoretically and practically). However the constraint programming community has developped a large set of techniques to counter combinatorial explosion (structure-based symmetry breaking, decomposition, heuristics, etc.). The current implementation uses none of these. Clearly, our aim is not to replace techniques that have proven suitable in many applications, but to show that the properties inherent to this approach are relevant for various problems, and how to integrate it in current MDE practices.

Related work

There are several approaches studying model transformations. A classification can be found at [START_REF] Czarnecki | Feature-based survey of model transformation approaches[END_REF]. In particular, the OMG standard QVT [START_REF][END_REF] has defined specifications for different type of model operations. Its QVT-operational part has been implemented by various tools such as the popular ATL [START_REF] Jouault | Transforming models with ATL[END_REF], TEFKAT [START_REF] Lawley | Practical declarative model transformation with tefkat[END_REF], VIATRA [START_REF] Ehrig | Model transformation by graph transformation: A comparative study[END_REF], and others. These approaches allow for fast and efficient unidirectional transformations. QVT-relations defines a broader set of capabilities, such as incremental transformations, but has fewer (and only partial) implementations such as [1].

Further studies have tackled bidirectional model transformations or synchronizations (see [START_REF] Czarnecki | Bidirectional transformations: A cross-discipline perspective[END_REF] for a survey), often through mechanisms which require additional specifications to an existing rule-based transformation. For instance, [START_REF] Hettel | Towards model round-trip engineering: An abductive approach[END_REF] proposes, based on abductive reasoning, to reverse an unidirectional transformation in order to provide synchronization of the source model with the previously obtained target model. In particular, it shares our ability to compute different alternative solutions through combinatorial logic inference. A number of so-called incremental approaches [START_REF] Hearnden | Incremental model transformation for the evolution of model-driven systems[END_REF][START_REF] Vogel | Incremental model synchronization for efficient run-time monitoring[END_REF][START_REF] Bergmann | Incremental pattern matching in the viatra model transformation system[END_REF] allow to update a target model by taking into account incremental changes to the source model. Triple Graph Grammars (TGGs) [START_REF] Schürr | 15 years of triple graph grammars[END_REF] are an approach for defining correspondences between two graphs. The TGG definition is similar to our model unification (i.e., a unique graph created from one left, one right and one correspondence graph) though not grounded in usual metamodelling principles. TGGs are also used for generating transformations (e.g., the [START_REF]Fujaba Tool Suite[END_REF] tool), but without search capabilities. [START_REF] Akehurst | A relational approach to defining and implementing transformations between metamodels[END_REF][START_REF] Del Fabro | Metadata management using model weaving and model transformations[END_REF] also expore the notion of weaving relationships but do not use them as direct transformation specifications. However, the described patterns may be useful in our context as specifications templates. Due to the high number of other existing transformation approaches and their spreading among different research communities, this overview can hardly be exhaustive. Clearly, many of these techniques have their own benefits over our approach, such as easier removal of elements or faster execution times. However, non-deterministic constrained search offers an original combination of properties: flexibility of having a single specification for different scenarios, ability to provide various solutions, automatic checking/optimizing capabilities, and in our case the sole use of existing modeling concepts. Finally, the MDE community has also been using constraint-based solvers for various model operations such as model checking [START_REF] Gogolla | Use: A uml-based specification environment for validating uml and ocl[END_REF][START_REF] Cabot | Umltocsp: a tool for the formal verification of uml/ocl models using constraint programming[END_REF][START_REF] White | Automated diagnosis of product-line configuration errors in feature models[END_REF], finding optimized transformations [START_REF] Kessentini | Model transformation as an optimization problem[END_REF], or extending transformation capabilities [START_REF] Petter | Solving constraints in model transformations[END_REF]. Although there are definitely similarities in the use of constraint tools, and in particular alternative mappings to solver languages, the pursued goals are different.

Conclusion

As model transformations have gained maturity in the past years, novel scenarios have arised that cannot be handled using classical rule-based solutions, mainly because of their non-deterministic nature. In this paper we described an original approach in which the core idea is to search for a solution model by satisfying a set of weaving relations and constraints. The approach is built on a previously defined operation, called model search, for the automatic generation of complete valid models conforming to a metamodel and its constraints. Both model search and transformation as search operations are based on the concepts of partial model and partial conformance. The paper also describes how this model transformation technique is formalized and automated as a first-class model operation, independently from the solving engine, in order to fit in current MDE practices. The nature of the operation provides original properties: bidirectionality, ability to explore and discriminate different target alternatives based on optimization criteria, synchronization of existing models, etc. However a larger set of examples and an extensive evaluation are required to assess practical benefits. Indeed, the provided prototype implementation on a reference usecase is only a first step that raises a number of modeling and operational challenges for future research.

Fig. 1 .

 1 Fig. 1. Model search: example process

Fig. 2 .

 2 Fig. 2. Extract of the running example transformation metamodel (V1) as an ecore diagram. Initial metamodels are on the sides, weaving metamodel is in the middle.

Fig. 3 .

 3 Fig. 3. Obtaining the transformation metamodel by unification (application on the running example shown in italics)

Fig. 4 .

 4 Fig. 4. Transformation as search operation (application on the running example shown in italics)

1. ( 1 )

 1 the forward transformation presented in the running example (from class to relational) 2. (2) the reverse transformation (from relational to class) 3. (3) a synchronization scenario (propagation of changes from one model to another after adding new elements to the class schema).

Table 1 .

 1 Summary of the experiments (Family model)

	scenario-version #variables #constraints execution
		(primary) (unfolded) time (ms)
	(1) -V1	9956	845357	3432
	(1) -V2	7179	866894	2483
	(2) -V1	10114	791167	5529
	(2) -V2	5725	866894	1655
	(3) -V1	6496	505227	324
	(3) -V2	5448	1231787	666

Though these may not be the most precise on object-oriented concepts and different model relationships, simple graph-based definition will prove useful in our context

Acknowledgements this article was partially funded by project CNPq Universal (481715/2011-8) and Convênio Fundação Araucária/INRIA.