rsity of Manchester, United Kingdom
{
hwang,pan
}
@cs.man.ac.uk
2
National University of Singapore, Singapore
liyf@comp.nus.edu.sg
3
The University of Auckland, New Zealand
j.sun@cs.auckland.ac.nz
4
RMIT University, Australia
hongyu@cs.rmit.edu.au
Abstract.
Feature models are widely used in domain engineering to capture
common and variant concepts among systems in a particular domain. However,
the lack of a formal semantics of feature models has hindered the development
of this area. This paper presents a Semantic Web environment for modeling and
verifying feature diagrams using ontologies. We use OWL DL (a decidable di-
alect of OWL) to precisely capture the relationships among features in feature
diagrams and congurations. OWL reasoning engines such as RACER are de-
ployed to check for the inconsistencies of feature congurations fully automati-
cally. As part of the environment, we also develop a CASE tool to facilitate the
visual development, interchange and reasoning of feature diagrams represented
as ontologies.
1
Introduction
Domain engineering is a software reuse approach that focuses on a particular applica-
tion domain such as word processing, inventory management systems, etc. In domain
engineering, we perform domain analysis and capture domain knowledge in the form
of reusable software assets. By reusing the domain assets, an organization will be able
to deliver a new product in the domain in a shorter time and at a lower cost. In industry,
domain engineering forms a basis for software product line practices [14].
Feature modeling [3] plays an important role in domain engineering. Features are
prominent and distinctive user visible characteristic of a system. Systems in a domain
share common features and also differ in certain features. In feature modeling, we iden-
tify the common and variant features and capture them as a graphical feature diagram.
Feature modeling is considered as the greatest contribution of domain engineering to
software engineering [3].
Quite a number of feature-based reuse approaches have been proposed, such as
FODA (Feature-Oriented Domain Analysis) [12], FORM (Feature-Oriented Reuse Method) [13]
and FeatuRSEB [8]. However, due to the absence of a formal semantics of features and feature modeling, there is no automated tool that can check the correctness of a partic-
ular feature conguration based on the constraints specied in a feature model.
Works in the description logics area also inspired us to apply Semantic Web tech-
nologies to feature modeling. For instance, various description logics systems have been
applied to solving complex conguration problems [17, 6] and verifying the consistency
of UML diagrams [1]. However, to our best knowledge, Semantic Web and ontology
languages have not been applied to feature modeling problems before. Moreover, the
Semantic Web approach that we adopt provides an semantic foundation and working
environment that facilitates model creation, verication, integration, maintenance, etc.
Ontology languages such as OWL [11] play a key role in realizing the full potential
of Semantic Web as they prescribe how data are dened and related. We feel that there
is a strong similarity between Semantic Web ontology engineering and feature model-
ing, both of which represent concepts in a particular domain and dene how various
properties relate among them. Hence, we believe that Semantic Web can play important
roles in domain engineering, and vice versa.
In this paper, we explore the synergy of domain engineering and Semantic Web. We
propose methods for transforming a feature model into an OWL DL ontology. Being
based on XML, the OWL format facilitates storage and exchange of the feature models.
We then use OWL reasoning engine such as RACER [10] to perform automated analysis
over an OWL representation of the feature model. The analysis helps us detect possible
inconsistencies in feature congurations. We illustrate our approach using an example
of the Graph Product Line (GPL) feature model, which is a standard problem proposed
in [15] for evaluating product line technologies. Furthermore, we developed a CASE
tool to facilitate visual development, reasoning and distribution of feature models in the
Semantic Web environment.
The remainder of the paper is organized as follows. In Section 2, we give a brief
overview of feature modeling and Semantic Web ontology languages and tools. Sec-
tion 3 presents our proposal of feature model using OWL. We also show how Semantic
Web reasoning engines, can be used to perform automated analysis over the OWL rep-
resentation of the feature congurations. In Section 4, we demonstrate the CASE tool
we developed to facilitate the visual creation and reasoning of feature models. Section 5
concludes the paper and describes future work.
2
Background Information
2.1
Feature Modeling - Preliminary
Concepts & Features
Feature research has its root in conceptual modeling and cognitive science. In classical
conceptual modeling, we describe concepts by listing their features, which differentiate
instances of a concept. In software engineering, software features differentiate software
systems. Features of a software system are not only related to user-visible functional
requirements, but also related to non-functional requirements (quality attributes), design
decisions, and implementation details. In domain engineering and software product line
context, features distinguish different members of a product line. A product line can be seen as a concept, and members of the product line can be seen as instances of
the concept. Product line members share common features and also differ in certain
features.
Feature Diagrams & Feature Relations
Conceptual relationships among features can be expressed by a feature model as pro-
posed in [12].
Table 1.
Features types
Type
Notation
Mandatory
C
F
Optional
C
F
Alternative
F1
F2
C
Or
F1
F2
C
A feature model consists of a feature diagram and other associated information
(such as rationale, constraints and dependency rules). A feature diagram provides a
graphical tree-like notation that shows the hierarchical organization of features. The
root of the tree represents a concept node. All other nodes represent different features.
Table 1 provides an overview of some commonly found feature types. The graphical
notation introduced in [3] are used here. In Table 1, assuming the concept C is selected,
we have the following denitions on its child features: Mandatory The feature must be included into the description of a concept in-
stance. Optional The feature may or may not be included into the description of a concept
instance. Alternative Exactly one feature from a set of features can be included into the
description of a concept instance. Or One or more features from a set of features can be included into the description
of a concept instance. A feature diagram itself cannot capture all the inter-dependencies among features.
We have identied two additional relations among features: requires and excludes. Requires The presence of some feature in a conguration requires the presence
of some other features. Excludes The presence of some feature excludes the presence of some other fea-
tures.
As the Requires and Excludes relations do not appear in a feature diagram, they are
usually presented as additional constraints in a textual description.
The Graph Product Line (GPL) feature model
The Graph Product Line (GPL) example was proposed by Lopez-Herrejon and Batory
as a standard problem for evaluating software product line technologies [15]. We use
it as a case study to demonstrate the effectiveness of our approach in verifying feature
models using OWL. The GPL is a family of classical graph applications in the Computer
Science domain. Members of GPL implement one or more graph algorithms, over a
directed or undirected graph that is weighted or unweighted, and one search algorithm
if required
1
. We summarize it as follows.
GPL is a typical software product line in that different GPL applications are distin-
guished by a set of features. Lopez-Herrejon and Batory have identied the following
features in GPL: Algorithms A graph application implements one or more of the following algo-
rithms: Vertex numbering (Number), Connected Components (Connected), Stro-
ngly Connected Components (StronglyConnected), Cycle Checking (Cycle), Mini-
mum Spanning Trees (MST), and Single-Source Shortest Path (Shortest). Graph Type A graph is either Directed or Undirected, and its edges can be either
Weighted or Unweighted. Search A graph application requires at most one search algorithms: Breadth-First
Search (BFS) or Depth-First Search (DFS).
Based on the above feature classication, a feature diagram for the Graph Product
Line (GPL) applications can be dened as shown in Figure 1.
Not all combinations of the features described in the above feature diagram (Fig-
ure 1) are valid in a GPL implementation. For example, if a graph application imple-
ments the Minimum Spanning Trees (MST) algorithm, we have to use the Weighted and
Undirected graph types and require no search algorithm. Table 2 shows the additional
constraints among the GPL features for representing a valid combination, adapted from
Lopez-Herrejon and Batory [15].
From the GPL model presented in Fig. 1 above and additional constraints, we can
see that (GPL, GraphType, Directed, Unweighted, Algorithms, Number) is a possible
conguration derived from the GPL feature model. However, not all combinations of
1
More information about the GPL example can be found online at:
http://www.cs.
utexas.edu/use