Concept lattices: a representation space to structure software variability

50 %
50 %
Information about Concept lattices: a representation space to structure software variability
Software

Published on July 24, 2014

Author: THEEMPERORRAFAT

Source: slideshare.net

Description

Concept lattices: a representation space to structure software variability

Concept lattices: a representation space to structure software variability R. AL-msie’deen1, M. Huchard1, A.-D. Seriai1, C. Urtado2, S. Vauttier2and A. Al-Khlifat3 1LIRMM / CNRS & Montpellier 2 University, Montpellier, France {al-msiedee, huchard, seriai}@lirmm.fr 2LGI2P / Ecole des Mines d’Al`es, Nˆımes, France {Christelle.Urtado, Sylvain.Vauttier}@mines-ales.fr 3Al-Balqa’ Applied University Salt, Jordan {amak n}@hotmail.com 1

Introduction • Software variants – Are similar software • Share some features, called common features, and differ in others, called optional features (variability) • Software product Line (SPL) – SPL supports efficient development of related software products (software family) . – Manages common and optional features (variability management). – Central and unique to SPLE is the management of variability 2

The context • Variability in SPL is an assumption about how members of a family may differ from each other. • Variability may be identified from different viewpoints. • Feature model is presently the most popular technique to model variability. 3

• Software Product Line – Feature model (FM) • Is a tree-like graph of features and relationships among them (constraints) • Used to represent commonality and variability of SPL members at different levels of abstraction The context

Software Product Line Engineering (SPLE): • A software product line (SPL) is ”a set of software intensive systems sharing a common, managed set of features that satisfy the specific needs of a particular market segment or mission and are developed from a common set of core assets in a prescribed way” [Clements, 2001]. 5

Software Product Line Engineering (SPLE): Domain Engineering Application Engineering e.g., Source code FM F1 F0 Feature Model F2 6 Reengineering existing software variants into a software product line.

Copy-paste-modify (delete, add, modify)

SPLE: Variability • Central and unique to SPLE is the management of variability. It is one of the fundamental principles to successful SPLE. Variability management of a product family is the core aspect of SPLE [Al-Msie’deen, 2013]. Product Gamma Product AlfaProduct Beta The common source code elements among all software product variants The shared source code elements between Alfa and Beta products source code elements unique to product Beta 8

SPLE: Feature Model Fig. 1. Cell Phone SPL Feature Model (using FeatureIDE plugin). Requires Excludes 1. Group of features constraints : or + Xor 2. Cross-tree constraints 9

Issue • Software variants – Difficulties for : • Reuse • Maintenance • Comprehension • Impact analysis • Software Product Line – Design from scratch is a hard task (domain engineering) 10 Software_A I1 I1I2 I3 Implementation Space Software_B F1 F1F2 F3 Feature Space

Our Goal • Reengineering existing software variants into a software product line. A C B 3 AB 3 B C A Formal concept analysis

Introduction: Formal Concept Analysis • Formal Concept Analysis (FCA) is a theoretical framework which structures a set of objects described by properties. • Formal Concept Analysis is a classification technique that takes data sets of objects and their attributes, and extracts relations between these objects according to the attributes they share. • FCA is a methodology for: (application) 1 - data analysis, data mining. 2- knowledge representation. 12

Formal Concept Analysis: Formal Context • A formal context is a triple K = (O, A, R) where O and A are sets (objects and attributes, respectively) and R is a binary relation, i.e., R ⊆ O × A. flying nocturnal feathered migratory with crest with membrane flying squirrel x X bat X X X ostrich X flamingo X X X chicken X X X Table 1: A formal context for describing animals. objects attributes 13

Formal Concept Analysis: Formal Concept • Formal Concept: Given a formal context K = (O, A, R), a formal concept is a pair (E, I) composed of an object set E ⊆ O and an attribute set I ⊆ A. E = {o ∈ O|∀a ∈ I, (o, a) ∈ R} is the extent of the concept, I = {a ∈ A|∀o ∈ E, (o, a) ∈ R} is the intent of the concept. Intent Extent 14

Formal Concept Analysis: Concept Lattice • Let CK be the set of all concepts of a formal context K. This set of concepts provided with the specialization order (CK, ≤s) has a lattice structure, and is called the concept lattice associated with K.  Concept : maximal group of entities sharing characteristics.  Concept lattice : concepts with a partial order relation. 15

Top Concept Bottom Concept Intent Extent Formal Concept Figure 1: The concept lattice for the formal context of Table 1. More general concept More specific concept 16

Formal Concept Analysis: AOC-poset • In our approach, we will consider the AOC-poset (without empty concepts). • The AOC-poset (for Attribute-Object-Concept poset) is the sub-order of (CK, ≤s) restricted to object-concepts and attribute-concepts. 17

For our example, it would correspond to the concept lattice of Figure 1 deprived of Concept_0, Concept_4 and Concept_5 (cf. Figure 2). Tools (rename). Cont …. Figure 2. The AOC-poset for the formal context of Table 1.

Concept Lattice & AOC-poset • There is a drastic difference of complexity between the two structures, because the concept lattice may have 2min(|O|,|A|) concepts, while the number of concepts in the AOC-poset is bounded by |O|+|A|. • Algorithms for building AOC-posets are introduced in [Ganter, 1997]. • Extents and intents are presented in a simplified form, removing top- down inherited attributes and bottom- up included objects. 19

SPL reverse engineering approaches • Ziadi et al. [Ziadi, 2012] proposed semi-atomic approach to identify feature from OO source code. • Their approach takes as input the source code of a set of product variants. • They propose an ad hoc algorithm to identify the feature candidates of a given set of products. • Their algorithm gathers all construction primitives that common to all product variants as one feature (base feature). • For the construction primitives that unique to a single product or common to two or more products but not all products their algorithm gathers these construction primitives as one feature.  Feature Identification from the Source Code of Product Variants 20

SPL reverse engineering approaches Table 3. A formal context describing bank systems by construction primitives. CreatePackage(bs) … … … … … … … CreateAttribute(cons,Bank) Product1Bank x … … … … … … … x Product2Bank x … … … … … … … Product3Bank x … … … … … … … x Product4Bank x … … … … … … … Product5Bank x … … … … … … … x Product6Bank x … … … … … … … Product7Bank x … … … … … … … x Product8Bank x … … … … … … … 21 First, a formal context, where objects are product variants and attributes are construction primitives (Table 3), is defined. The corresponding AOC-poset is then calculated.  Feature Identification from the Source Code of Product Variants

SPL reverse engineering approaches In the AOC-poset, the intent of each concept represents construction primitives common to two or more products. As concepts of AOC-posets are ordered, the intent of the most general (top) concept gathers primitives that are common to all products. They constitute the mandatory features. The intents of all remaining concepts are block of variation (variability). They gather sets of primitives common to a subset of products and correspond to the implementation of one or more features. The extent of each of these concepts is the set of products having these primitives in common. 22  Feature Identification from the Source Code of Product Variants

Figure 5. Concept Lattice of formal context in Table 3. Common features Or Mandatory features Variable features Empty Concept 23

Figure 6. The AOC-poset for the FC of Table 3. 24 Excludes Requires

SPL reverse engineering approaches • Acher et al. [Acher, 2012] present an procedure (semi-automatic procedure) to synthesize FM based on the product descriptions. • Their approach takes as input product description for a collection of product variants to build the FM. • Products are described by characteristics (language, license) with different patterns on values (many-valued, one-valued). • Product descriptions are interpreted to build as much FMs as there are products. • Finally, the FMs of the products are merged, producing a new FM that compactly represents valid combinations of features supported by the set of products.  Extracting Feature Models From Product Descriptions 25

SPL reverse engineering approaches Table 4. A formal context describing wiki systems by characteristics. License Unicode RSS … … LicenseCostFree Community Confluence x x x … … Pbwiki x x x … … MoinMoin x x x … … DokuWiki x x x … … PmWiki x x x … … DrupalWiki x x x … … Twiki x x x … … x MediaWiki x x x … … The formal context, where objects are wiki variants and attributes are characteristics (Table 4), is defined. The corresponding AOC- poset is then calculated.  Extracting Feature Models From Product Descriptions

Figure 5. Concept Lattice of formal context in Table 3. Common features feature Language_PHP requires feature Licence_GPL2 Atomic set of features 10,1,3 27 feature storage _files excludes feature LCF_Differeent L requires

Cell phone SPL feature model Excludes Requires

SPLE: Software Configurations Cell_Phone Wireless Infrared Bluetooth Accu_Cell Strong Medium Weak Display Games Multi_Player Single_Player Artificial_Opponent P1 x x x x x x x P2 x x x x x x x P3 x x x x x x x P4 x x x x x x x x x P5 x x x x x x x x P6 x x x x x x x x x x P7 x x x x x x x x x P8 x x x x x x x x P9 x x x x x x x x x x P10 x x x x x x x x x P11 x x x x x x x x P12 x x x x x x x x x x P13 x x x x x x x x x P14 x x x x x x x x x x P15 x x x x x x x x x P16 x x x x x x x x x x x Table 2. product-by-feature matrix (i.e., formal context) of cell phone SPL. 29

Figure 3. The AOC-poset for the FC of Table 2. SPLE: Restructuring Variability in SPLs using Concept Analysis of Product Configurations 30 Mandatory features requires Root feature

Tools: • Erca plugin. • Erca is a framework that eases the use of Formal and Relational Concept Analysis, a neat clustering technique. • Link: https://code.google.com/p/erca/ 31

Conclusion • In this paper, we focused on concept structures and the opportunities they offer for structuring variability. • Concept structures can be seen a summary of known data (artifacts, features, etc.) for a set of products. • In this paper, we revisit two papers (to show some illustrative example) from the literature of the software product line domain. We point to key contributions and limits of the representation of variability by concept lattices, with illustrative examples. We present tools to implement the approach and open a discussion. 32

Future Direction 1/2 • Reverse engineering feature models (FM) from software variants source code (object-oriented). • Feature location in collection of software product variants (functional feature == source code implementation). • Split source code elements of each concept into a set of features based on the lexical similarity (based on LSI method). 33

Future Direction 2/2 S/F F_1 F_2 F_3 S_1 x x S_2 x x S_3 x x Reverse Engineering Source code Configurations Product-by-feature matrix Feature model Forward Engineering Build systems Reverse Engineering FMs SynthesisFeature location & documentation variant 1 Product configurations Configuration files Requirements 34

References • [Ganter, 1997] B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, 1st ed. Secaucus, NJ, USA: Springer-Verlag New York, Inc., 1997. • [Clements, 2001] P. C. Clements and L. M. Northrop, Software product lines: practices and patterns. Addison-Wesley, 2001. • [Al-Msie’deen, 2013] R. Al-Msie’deen, A. Seriai, M. Huchard, C. Urtado, S. Vauttier, and H. E. Salman, “Feature location in a collection of software product variants using formal concept analysis,” in ICSR. Springer, 2013, pp. 302–307. • [Ziadi, 2012] T. Ziadi, L. Frias, M. A. A. da Silva, and M. Ziane, “Feature identification from the source code of product variants,” in CSMR, 2012, pp. 417–422. • [Acher, 2012] M. Acher, A. Cleve, G. Perrouin, P. Heymans, C. Vanbeneden, P. Collet, and P. Lahire, “On extracting feature models from product descriptions,” in VaMoS, 2012, pp. 45–54. 35

Thank You For Your Attention 36

Concept lattices: a representation space to structure software variability R. AL-msie’deen1, M. Huchard1, A.-D. Seriai1, C. Urtado2, S. Vauttier2and A. Al-Khlifat3 1LIRMM / CNRS & Montpellier 2 University, Montpellier, France {al-msiedee, huchard, seriai}@lirmm.fr 2LGI2P / Ecole des Mines d’Al`es, Nˆımes, France {Christelle.Urtado, Sylvain.Vauttier}@mines-ales.fr 3Al-Balqa’ Applied University Salt, Jordan {amak n}@hotmail.com 37

Add a comment

Related presentations

Speaker: Matt Stine Developing for the Cloud Track Marc Andressen has famou...

This presentation explains how to develop a Web API in Java using (JAX-RS or Restl...

1 App,

1 App,

November 10, 2014

How to bring innovation to your organization by streamlining the deployment proces...

Cisco Call-control solutions can handle voice, video and data

Nathan Sharp of Siemens Energy recently spoke at the SAP Project Management in Atl...

Related pages

Concept lattices: A representation space to structure ...

Concept lattices: A representation space to structure ... which structures a set of ... representation of variability by concept lattices, ...
Read more

Concept lattices: a representation space to structure ...

... a representation space to structure software variability . Ra'Fat ... Concept lattices: a representation space to structure software variability.
Read more

Concept lattices: A representation space to structure ...

Page 1. Concept lattices: a representation space to structure software variability R. AL-msie’deen1, M. Huchard1, A.-D. Seriai1, C. Urtado2, S ...
Read more

www.researchgate.net

www.researchgate.net
Read more

Formal concept analysis - Wikipedia, the free encyclopedia

... formal concept analysis is a ... A concept, in this representation, ... survey many algorithms that have been developed for constructing concept lattices.
Read more

Lattice (group) - Wikipedia, the free encyclopedia

... (dropping its geometric structure) a lattice is a finitely ... representation, ... than the lattice itself. Lattices in complex space ...
Read more

1. Crystal structures - Harvard John A. Paulson School of ...

Crystal structures 1.1 Primitive ... when repeated in space it forms the crystal structure. ... We are often familiar with the concept of Fourier series in ...
Read more

Reciprocal Lattices and DiffractionReciprocal Lattices and ...

Reciprocal Lattices and ... Reciprocal Lattice • Vector representation of ... * plane in real space; it is the reciprocal lattice ...
Read more

A Linear Delay Algorithm for Building Concept Lattices ...

A Linear Delay Algorithm for Building Concept Lattices ... concepts, the combinatorial structure ... space compared to the full representation ...
Read more

Concepts (Stanford Encyclopedia of Philosophy)

... the ontology of concepts, (2) the structure ... representations “concepts 1 ... variability is consistent with concepts ...
Read more