Software Product Line Engineering (SPLE) is a software engineering domain in which families of similar softwares (called products) are built reusing common artifacts. This requires to analyze commonalities and variabilities, for example to detect which parts are common to several products and which parts differ from one product to another. Such software characteristics that may be present or not in a product are called features. Several approaches in the literature exist to organize features and product configurations in terms of features. In this paper we review those approaches and show that concept lattices are a relevant structure to organize features and product configurations. We also address scaling issues related to formal context computation in the domain of SPLE.
Software Product Line Engineering (SPLE) focuses on the reuse of common software pieces to reduce the building and maintenance cost of similar software systems (called products). An important step of this methodology consists in analyzing and modeling variability, i.e. mainly extracting "features", a feature being a discriminating characteristic common to several products or specific to a product. A product configuration is then a set of these features. Different formalisms are used in SPLE to organize features and product configurations. Some of these formalisms focus on features, while others represent product configurations. Some are canonical, while others are not, and depend on the designer point of view.
In this paper, we review the main used formalisms and we show that concept lattices might be a relevant (canonical) structure for representing variability, while highlighting information on relationships between product configurations, and between product configurations and features, that other formalisms hardly represent. Besides explaining what is the contribution of concept lattices to variability representation, we propose a solution to address some scaling issues of concept lattices in this domain. Actually, scaling issues can occur at two levels when computing: (1) the formal context, and (2) the concept lattice. Here, we focus on scaling issues related to formal context computation; we investigate implicative systems on attributes as closure operators to build a feature closed sets lattice without building the formal context. We show that implicative systems are another representation of the variability that can be useful for designers.
The remaining of the paper is organized as follows. Section 2 presents the various formalisms found in the literature to capture the variability of a software product line. Section 3 shows that concept lattices are an interesting formalism to analyse variability, and presents related work concerning the use of formal concept analysis for product lines. Section 4 explains how using implicative systems allows to face scaling issues related to formal context computation for variability management. 2
Existing Formalisms for variability representation
To capture and describe the variability of a software product line, almost all
approaches in the literature use feature-oriented representations [
Feature models (FMs) are graphical representations that include a decorated feature tree and a set of textual cross-tree constraints which complements information given in the tree. The vertices of the tree are the features (from F ), while the edges (in F F ) correspond to refinement or sub-feature (part of) relationships in the domain. Edges can be decorated by a symbol meaning that if the parent feature is selected, the child feature can be selected or not (optional ). Another symbol indicates that if the parent feature is selected, the child feature is necessarily selected (mandatory ). Groups of edges rooted in a feature represent: xor-groups (if the parent feature is selected, exactly one feature has to be selected in the group), and or-groups (if the parent feature is selected, at least one feature has to be selected in the group). Fig. 1 shows a simple FM for e-commerce websites.
Such a software necessarily includes a catalog for proposing products, and this catalog is displayed using a grid or (exclusive) using a list. Optionnally, a basket functionality is proposed. A payment_method may also be optionally proposed. Two payment methods are proposed: credit_card or (inclusive) check. A crosstree constraint, written below the tree, indicates that if a basket is proposed, a payment method is also proposed (and reciprocally).
A variability representation conveys ontological information (ontological semantics): the edges of the feature tree and the groups correspond to domain knowledge, e.g. the group grid, list indicates a semantic refinement of catalog; the edge (e_commerce, catalog) indicates that catalog is a subpart of the website.
Xor
Or Optional
Mandatory Double include catalog payment_method
basket grid list credit_card
check payment_method $ basket
A variability representation also has a logical semantics: for example an
alternative representation of the FM is an equivalent propositional formula with
jF j variables and constraints defined using propositional connectives (^; _; !; $
and :) [
An important property of a formalism is canonicity. Given a set of configurations that are to be represented, and considering a chosen formalism, there are often different ways of writing a representation of a given set of configurations following this formalism. For example different feature models can have the same configuration-semantics. Concision is also an interesting property: a variability representation can be extensional if it enumerates all the possible configurations, or intensional if it represents these configurations in a more compact way. For example, the formal context of Table 1 is an extensional representation of the
In this section, we study graph-like representations which have been used in the literature to express software product line variability of a feature model starting from a propositional formula. For each representation, we give a definition and discuss its canonicity, concision, configuration semantics and ontological semantics.
A binary decision tree (BDT) is a tree-like graph used to represent the
truth table of a boolean function equivalent to a propositional formula: it is an
extensional representation. This representation has redundancies which can be
avoided by node sharing, which results in a graph called binary decision
diagram [
The upper part of Table 2 compares the different formalisms used in SPLE domain with respect to canonicity and their ability to encompass or highlight the different semantics. Besides, it shows which kinds of relationships can be read in the formalism: between features only, between configurations and features, or between configurations. Then it indicates if this is a textual or a graphical formalism, and if this is an intensional or an extensional representation. In SPLE domain, all representations (except the set of configurations and the BDT) consider an intensional point of view with only feature organization. FM is the only representation which clearly expresses all ontological information, but it is not canonical, since many relevant FMs can be built from domain information. Implication hypergraph and feature graph preserve the notion of groups, but refinement and mandatory information of features are lost.
To sum up, these formalisms concentrate on feature organization (except the set of configurations and the BDT), are more or less respectful of initial semantics of the FM they represent and none of them considers a mixed representation of features and configurations. In the next section, we show the benefits of having such a mixed representation and in general, the contributions that a concept lattice based representation may bring to the SPLE domain as a complement to the existing representations.
Contribution of concept lattices to variability
representation and related work
Formal Concept Analysis [
Concept_EC_13 grid 1
Concept_EC_15 e_commerce
catalog Concept_EC_14 payment_method
basket Concept_EC_9
Concept_EC_11 check
Concept_EC_12 credit_card
Concept_EC_10 list 5 Concept_EC_8 Concept_EC_6
Concept_EC_7
Concept_EC_5
Concept_EC_3
Concept_EC_4 3 2 7
6 Concept_EC_2
Concept_EC_1 4
8
Concept_EC_0 Fig. 3: Concept lattice for the formal context of Table 1, built with RCAExplore3
A concept lattice organizes configurations and features in a single structure, which has a canonical form (only one concept lattice can be associated with a formal context). If the configurations in the formal context are the valid configurations of a feature model, the configuration semantics of the concept lattice is the same and the configurations can be read from the lattice. The logical semantics is the same too. However, the ontological semantics is incomplete as in the structure, we cannot distinguish ontological relationships: for example, when a feature F2 is in a sub-concept of a concept that introduces another feature F1, we cannot know whether F2 implies F1 (having a basket implies having a payment_method) or F2 refines F1 (pay by check is a kind of payment_method).
The concept lattice has many qualities regarding the variability representation and relationships between configurations, features, as well as between configurations and features, including highlighting: – bottom features that are present in all configurations (e.g. catalog, e_commerce) – mutually exclusive features (in concepts whose supremum is the top) – feature co-occurrence (introduced in the same concept, e.g. basket and payment_method) – feature implication (one is introduced in a sub-concept of another one, e.g.
credit_card implies basket) – how a configuration is closed to or specializes another one, or a merge of other configurations. E.g. 8 is a specialization of 5,6,7.
– features that are specific to a configuration, or shared by many. The concept lattice is also an interesting structure to navigate between these features and configurations, and is a theoretical support for association rule extraction, a domain that has not been explored yet in SPLE, as far as we know.
Besides, lattice theory defines irreducible elements, useful for identifying irreducible features and configurations (in a polynomial time), that are used for defining canonical representations of a context or a rule basis. In lattice theory, an element is called join-irreducible if it cannot be represented as the supremum of strictly lower elements. They are easily identifiable in a lattice because they have only one predecessor in lattice transitive reduction. All join-irreducible elements are present in the formal context, so they all correspond to valid configurations.
Research work done in the framework of reverse engineering exploits some of
the relevant properties of the concept lattice. Formal Concept Analysis has been
used to organize products, features, scenarios, or to synthesize information on the
product line. In [
Different artifacts are classified in [
Several proposals investigate with FCA the relationships between features
and source code of existing products. References [
FCA is also used in several approaches to study the feature organization
in feature models. Concept structures (lattices or AOC-poset) are used to
detect constraints in feature models, and propose a decomposition of features into
sub-features. The authors of [
Concept lattice could also be a tool in the framework of forward engineering,
using a transformation chain starting from a FM, building with the existing
tools, as FAMILIAR [
From feature models dependencies to implicative systems The set of all valid attribute implications of a formal context represent a closure operator, which produces attribute closed sets corresponding to concept intents of the context. The associated attribute closed set lattice is thus isomorphic to the concept lattice of the formal context. It is noteworthy that (1) FMs represent features interaction by graphically depicting a set of features and dependencies between them, and that (2) the set of all valid implications also describes dependencies between attributes (i.e. features). Thus, an analogy can be done between implicative systems and FMs dependencies.
We have previously mentioned a method to build a concept lattice from a FM,
which consists in enumerating all the FM configurations (i.e. all combinations of
4 http://www.splot-research.org/
features w.r.t its dependencies) in a formal context. However, FMs are intensional
representations which can potentially depict a large number of configurations,
making difficult their enumeration and the context computation. In order to
avoid this enumeration, we propose a way to express FMs dependencies as sets
of implications P(F ) F , without building the formal context. We made an
experiment in which we generated several FMs of small size (< 10 features) and
built their equivalent formal contexts, from which we extracted a complete set of
valid implications with the tool Concept Explorer5 [
The root feature traditionally represents the name of the modeled software system, and thus is present in all configurations. This peculiarity is translated by ; ! root, requiring the presence of root in all closed sets. Hierarchy constraints (subpart relationships) require that a child feature can be selected only if its parent feature is already selected, and thus produce a child ! parent implication. Optional relationships actually express the absence of dependencies between a feature and its child, and do not generate any implication. Mandatory relationships imply that a child feature is necessarily selected with its parent and produce a parent ! child implication. Or-groups behave as optional relationships with an obligation to select at least one feature: this kind of constraints do not produce any implication. Finally, xor-groups require that two of their features cannot appear together in any configuration: each pair of features thus implies the set of all features.
We can also determine implications for cross-tree constraints, i.e. include and exclude constraints. Let F be the set of all features and f1; f2 2 F two features. f1 includes f2 can naturally be translated by f1 ! f2, and f1 excludes f2 can be translated by f1 f2 ! F , as in xor-groups.
Table 3 thus permits to translate FM dependencies in implicative systems without building a formal context. The fact that the obtained implicative system is exactly the system corresponding to the original FM can be proved by construction. When adding a new feature (resp. feature group) to a FM, this adds
new dependencies which only involve the added feature (resp. feature group) and its parent. It does not change the previous dependencies expressed in the FM, but only adds new ones. In our approach, we first identify the implications corresponding to each type of feature groups and optional/mandatory relationships. Then, if we construct the FM step by step, we can create the implications corresponding to each added feature (resp. feature group), and thus no implication is missing, nor needs to be changed afterward. We applied our method on the FM of Fig. 1 and obtained the implicative system presented in Fig. 4. root : hierarchy : mandatory : xor-group : cross-tree : ? ! Ec Ca ! Ec ; G ! Ca ; L ! Ca ; P m ! Ec ; Cc ! P m ; Ch ! P m ; B ! Ec Ec ! Ca G; L ! Ec; Ca; G; L; P m; Cc; Ch; B
P m ! B ; B ! P m These implications can be extracted by performing a graph search on the FM, and their number can be predicted by analysing its dependencies (# stands for "number of"): 1 + #child-parent relationships + #mandatory relationships +#pairs of f eatures in each xor-group + #cross-tree constraints
For example, a representative FM of SPLOT (e-commerce) with 19 features and 768 configurations is equivalent (with the configuration-semantics) to an implicative system with 27 implications. 4.2 Identification of the set of possible configurations In a concept lattice representing a FM, an object introduced in a concept extent represents a valid configuration, which corresponds to the feature set of the concept intent. Because each configuration in a FM is unique, a concept can introduce at most one object. Thus, for SPLE, a concept intent represents either a valid configuration or an invalid one. In the isomorphic feature closed set lattice, each closed set corresponds to a concept intent from the context: therefore, each valid configuration of the FM matches a feature closed set. However, the feature closed set lattice does not display objects and thus we cannot identify which closed set corresponds to a valid configuration. To be able to retrieve knowledge about configurations as in concept lattices, their identification in feature closed set lattice is necessary.
As previously said, all join-irreducibles correspond to valid configurations. But there can exist valid configurations which do not correspond to join-irreducibles, and thus they cannot be discerned from invalid ones in feature closed set lattices. A solution is to add a unique attribute for each configuration, as an identifier. Thus, we change the lattice structure to make each configuration correspond to a join-irreducible element, which can be detected. However, the obtained lattice is not isomorphic to the original concept lattice, and its size is larger. A way to keep the isomorphism is to add "reducible" attributes, which do not modify the lattice structure and which can label the lattice’s elements.
In what follows, we investigate a way to label feature closed sets to help the identification of valid configurations. We seek to produce a labelled implicative system that generates a labelled feature closed set lattice, isomorphic to the concept lattice associated with the formal context. We recall that a valid configuration is a combination of features w.r.t. all the FM dependencies: thus, we seek to retrieve valid configurations by detecting which feature closed sets respect all these dependencies.
Features linked by mandatory relationships always appear together in closed sets: this type of dependencies is respected. Optional relationships express the absence of dependencies and do not create difficulties. Or-groups and xor-groups, however, are more problematic. Let us consider the or-group in Table 3, composed of B and C, which are two sub-features of A. fA; Bg and fA; Cg are two valid combinations of features of this group. Because our feature closed set family is closed under intersection/join, fA; Bg \ fA; Cg = fAg is also a feature closed set of the family, but it does not respect the dependencies induced by the or-group (i.e. contains at least B or C). The same reasoning can be applied to xor-groups. To identify if a feature closed set respects the dependencies induced by or-groups and xor-groups, we choose to make constraints related to feature groups appear directly in feature closed sets, as labels.
Let ff1; : : : ; fng be a subset of features involved in a feature group. If they form an or-group, each feature closed set containing the parent feature of this group will be labeled (f1; : : : ; fn), defining the constraint: "this feature closed set must have at least one feature from ff1; : : : ; fng to correspond to a valid configuration". If they form a xor-group, each feature closed set containing the parent feature of the group will be labeled [f1; : : : ; fn], defining the constraint: "this feature closed set must have exactly one feature from ff1; : : : ; fng to correspond to a valid configuration". As example, the FM of Fig. 1 produces two different labels: one for the xor-group of the feature catalog (Ca), and another for the or-group of the feature payment_method (P m). Each feature closed set possessing catalog has to be labeled [grid; list], and each feature closed set possessing payment_method has to be labeled (check; credit_card).
We choose to represent these labels in the labelled implicative system as attributes. A label is attached to a feature by adding to the original implicative system a double implication between the feature and the corresponding labelattribute. Fig. 5 presents the implications added to the implicative system of Fig. 4 in order to take into account labels [grid; list] ([G; L]) and (check; credit_card) ((Ch; Cc)).
A feature closed set with a (check; credit_card) label is a valid configuration if it contains at least features credit_card or check. A feature closed set with a labels :
P m ! (Ch; Cc) ; (Ch; Cc) ! P m ;
Ca ! [G; L] ; [G; L] ! Ca [grid; list] label is a valid configuration if it contains grid or list, but not both. A feature closed set respecting the constraints expressed by all its labels represents a valid configuration. A label is associated with the parent feature of the group, and thus does not change the original lattice structure.
Closed_set_15 e_commerce, catalog
[grid, list]
Closed_set_14 payment_method, basket
(check, credit_card) Closed_set_13
grid Closed_set_9
Closed_set_11 check
Closed_set_12 credit_card
Closed_set_10
list Closed_set_8 Closed_set_6
Closed_set_7
Closed_set_5
Closed_set_3
Closed_set_4 Closed_set_2
Closed_set_1
Closed_set_0
Fig. 6 represents the feature closed set lattice associated with the labeled implicative system of Fig. 4 plus Fig. 5: feature closed sets which respect all the constraints defined by their labels are colored, and correspond to the 8 configurations of the formal context of Table 1. In the lattice, "label features" are inherited from top to bottom, as usual features. For example, Closed_set_3 possesses features fe_commerce; catalog; list; basket; payment_method; checkg and the two labels [grid; list] and (check; credit_card). This feature closed set possesses feature list and not feature grid, and thus respects the constraint of label [grid; list]. Moreover, it possesses feature check, and thus also respects the constraint of label (check; credit_card). The constraints corresponding to all its labels are respected: Closed_set_3 is thus a valid configuration of the software product line. Note that in this particular case, the valid configurations are all irreducible.
To conclude, the labelled implicative system permits to construct a lattice from a FM without enumerating all its configurations: the obtained feature closed set lattice is a canonical representation, isomorphic to the concept lattice of a formal context, in which one can retrieve exactly the same information about features and configurations. 5
In this paper, we compare the various formalisms used in the literature to represent and manage the variability of a software product line. Especially, we study their different semantics, their canonicity and the type of information they can highlight. We investigate formal concept analysis and concept lattices to represent a software product line originally described by a feature model. Contrary to FMs, concept lattices represent commonalities and variabilities in a canonical form. Moreover, they permit to extract relationships between features, between features and configurations and between configurations.
Constructing a concept lattice from a FM requires to enumerate all its configurations in a formal context, but this method can be difficult to realize when their number is too high. We propose a method to extract feature implications directly from feature models dependencies. The obtained implicative system produces a feature closed set lattice isomorphic to the concept lattice which can be built from the context. We also propose a method to label these implicative systems in order to identify the set of valid configurations, and thus retrieve the same informations as in concept lattices.
In the future, we will make experiment on the existing FMs repositories in order to assess the size of FMs, implicative systems, and closed set lattices and how frequent are the FMs that have reducible configurations. We will also expand our study to multiple software product lines. We will study relational concept analysis to connect several software product lines represented by concept lattices, and analyze their properties and the issues they permit to answer.