% by Mirella M. Moro; version: September/23/2011 @ 05:01pm
% -- 09/03/2010: bib file with names for proceedings and journals; cls with shrinked {received}
% -- 08/27/2010: appendix, table example, more explanation within comments, editors' data

\documentclass[jidm,a4paper]{jidm} % NOTE: JIDM is published on A4 paper
\usepackage{graphicx,url}  % for using figures and url format
\usepackage[T1]{fontenc}   % avoids warnings such as "LaTeX Font Warning: Font shape 'OMS/cmtt/m/n'
\usepackage{algorithm}
%\usepackage{algorithmic}
\usepackage{algpseudocode}
\algrenewcommand{\algorithmicforall}{\textbf{foreach}}

%\usepackage{cite} % NOTE: do **not** include this package because it conflicts with jidm.bst

% Standard definitions
\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newdef{definition}[theorem]{Definition}
\newdef{remark}[theorem]{Remark}
\newenvironment{latexcode}
{\vspace{0.1in}\setlength{\parindent}{18pt}}
{\vspace{0.1in}}


% ALL FIELDS DOWN TO BEGIN{document} ARE MANDATORY
% The following data (volume, number and page) are given by the editors prior to publishing your

\jidmVolume{3}
\jidmNumber{1}
\jidmYear{12}
\jidmMonth{February}
\setcounter{page}{1}


% Includes headers with simplified name of the authors and article title
\markboth{M. Yamashita, K. Becker, R. Galante}
{JIDM - Journal of Information and Data Management}

% Title of the article
\title{A Flexible Approach for Assessing Service Compatibility \\ at Feature Level}

% List of authors
\author{Marcelo Yamashita, Karin Becker, Renata Galante}


%Affiliation and email
\institute{Universidade Federal do Rio Grande do Sul, Brazil \\ \email{\{marcelo.yamashita,
karin.becker, galante\}@inf.ufrgs.br}
}


% Article abstract - it should be from 100 to 300 words
%[karin] itroduzi uma frase de contexto, e mexi no frase dos experimentos do abstract.
\begin{abstract}
The ability of dealing with changes is one of the driving forces behind the adoption of
service-oriented computing. Service evolution requires sound strategies to appropriately manage
versions resulting from changes during service lifecycle.
Compatibility addresses the graceful evolution of services by considering the effects of changes on
client applications.
However, providers cannot always guarantee that the necessary changes yield compatible service
descriptions.
In practice, providers describe the changes in release notes, focusing on the explicit changes, very
often disregarding their cascading effects.
Thus, typically it is the responsibility of client's developers to assess the extent of the change
and their impact in their particular usage scenario.
This paper addresses service evolution on a finer grain manner, referred to as features.
It describes a versioning model and a compatibility assessment algorithm at service feature level,
which allows the identification of changes impact points,
and propagation effects, as well as the assessment of changes' compatibility.
The paper also reports an experiment based on a real service, which explores the versioning model to
detect implicit and explicit changes, and validates the algorithm to assess the compatibility of
these changes.
\end{abstract}


% ACM Computing Classification System categories
\category{H. Information Systems}{H.2 Database Management}{Miscellaneous}
% Categories and Descriptors are available at the 1998 ACM Computing Classification System
% http://www.acm.org/about/class/1998/
%  -> \category{}{}{}
%         takes 3 arguments for the Computing Reviews Classification Scheme.
%         ex: \category{D.3.3}{Programming Languages}{Language Constructs and Features}
%                   [data types and structures]
%                   the last argument, in square brackets, is optional.

% Article keywords
\keywords{Service compatibility, service evolution management, service versioning}


% THE ARTICLE BEGINS
\begin{document}

% This is optional:
\begin{bottomstuff}
% similar to \thanks
% for authors' addresses; research/grant statements
This research is financially supported by FAPERGS, CNPq and CAPES - Brazil. 
%The authors would like to thank the anonymous referees whose comments helped to improve earlier versions of this paper.

%We are also grateful to the anonymous referees that helped to improve this paper.
\end{bottomstuff}

\maketitle


% ARTICLE NEW SECTION
\section{Introduction}

% [karin] adicionei uma frase de contexto, para dizer o que queremos dizer com serviço
% [karin] mudei o estilo de citação dos trabalhos, a pedido
The adoption of service-oriented computing is highly motivated
by the ability of dealing with the inevitable changes. SOA (Service-oriented architecture) and web
services have become \emph{de facto} industry standards for the development of loosely-coupled,
platform-independent enterprise applications. Like traditional software, services are also
subject to constant changes, requiring appropriate strategies to support and manage
multiple versions throughout their lifetime.
Service evolution management encompasses the creation, maintenance and decommission of different
versions in a service provider environment, which leads to the maintenance of several concurrent
versions ~\cite{PapazoglouAB11}.
In order to minimize the impact on clients, a common approach to manage service versions
from the provider perspective, is the versioning of service interface description
~\cite{AndrikopoulosBM11}.

Service interface description exposes the service version as a \emph{contract} established by the
provider, which guides clients on how to access the service functionality.
However, current notations for service interface description, including the standard WSDL/XSD, do
not properly handle versioning ~\cite{AndrikopoulosBM11}.
Typically, the whole interface description document is versioned, despite the fact that many service
features (e.g. types, operations, message
calls) remain unchanged.  This practice leads to difficulties on recognizing and measuring the
actual impact of a change, especially
regarding each particular usage scenario.
In the absence of proper support, very often providers publish new versions using unique version
numbers or timestamps, together with release notes that hopefully will help clients to
adjust to changes (e.g. eBay, Google, Amazon).
Release notes usually describe the explicit changes (e.g. changes on schema types of service
calls), but fail to properly identify how changes propagate their effect throughout the entire
service ~\cite{ZouFL08}~\cite{FokaefsMT11}.
For instance, if a change is applied to a type that is referenced (directly or indirectly) by an
operation, then this operation is implicitly changed due to the ripple-effect.
As interface description versions (and corresponding release notes) are traditionally large
documents, the task of finding whether the introduced changes impact client applications is hard,
labor-intensive and error-prone ~\cite{ZouFL08}~\cite{BeckerLM08}.

Service change management requires mechanisms for the identification and classification of changes
in order to plan for compensatory actions for their side effects.
Thus, service stakeholders need to \emph{quantify} the scope of changes and \emph{qualify} their
impact.
In other words, they need to easily identify explicitly and implicitly changed features in a new
version, if
compared to previous ones, and whether these features were changed in a way clients are not broken.
The need for a smaller grain of change representation is highlighted in different works, for
purposes such as client synchronization ~\cite{ZouFL08}, change impact quantification
~\cite{WangC09}, accurate recognition of changes ~\cite{FokaefsMT11}, and usage oriented
compatibility
assessment ~\cite{YamashitaVBG12}.

Compatibility is a central issue on service evolution, because its assessment can provide valuable
information regarding the effects of changes on client applications ~\cite{BeckerLM08}.
However, traditional compatibility approaches (e.g. ~\cite{FangLF07}) are also document-oriented,
which means that the assessment of compatibility among different versions focuses on the worst-case
of total service compatibility.
Establishing compatibility relationship between service versions does not necessarily capture the
(in)compatibility impact of the change, because client applications are not bound to the whole
service as described by the interface, but rather to specific features they provide. Related work
~\cite{YamashitaBG11}~\cite{YamashitaVBG12}~\cite{PonnekantiF04}~\cite{AndrikopoulosBM08} suggests
the benefits of assessing
compatibility in terms of specific client usage.

%[karin] inclui frase sobre experimentos no final do paragrafo
The objective of this work is to detect explicit and implicit changes between service versions in
order to pinpoint incompatible changes.
The contribution of this paper is twofold: a) it describes a feature-oriented versioning model that
allows to version services, operations and types individually,
whilst maintaining their relationships and b) a compatibility assessment algorithm for services
versioned according to this model.
The versioning model handles the structural service description from the abstract perspective of
service features,
which correspond to fragments of a service interface description document.
This small-grained versioning model enables to locate and quantify the impact of changes, whereas
the assessment of compatibility at feature level enables to qualify it. An experiment was developed
using  a real eBay web service, and it revealed that less than 5\% of detected changes correspond to
explicit changes. The remaining 95\% of changes is a consequence of the ripple-effect, and they are
difficult to track because most of them are not covered by the corresponding release notes. The
compatibility of these changes were also successfully assessed, and we realized eBay compatibility rules are more flexible than the ones suggested in the literature 
~\cite{BrownE04}~\cite{FrankLF08}~\cite{PapazoglouAB11}~\cite{FangLF07}.

The approach discussed in this paper lays foundation for a wide spectrum of applications in the
context of service evolution. The analysis of change impact propagation,
which is a straightforward consequence of feature-oriented versioning, allows the quantification of
the ripple effect of changes ~\cite{WangC09}. It could also support the
automatic creation of more detailed release notes based on usage analysis
~\cite{ZouFL08}. Compatibility assessment at feature level enables service evolution
based on usage profiles ~\cite{YamashitaVBG12}, reduction of provisioned versions based on proxy
redirections ~\cite{FrankLF08}, and load balance management among
implemented versions ~\cite{TreiberAD10}.

The remaining of this paper is structured as follows. Section 2 describes related work. Section 3
presents the feature-oriented versioning model and Section 4 details the
corresponding compatibility
assessment algorithm. Section 5 reports experiments in a real case scenario.
Conclusions and future work are addressed in Section 6.


%karin: trouxe para a seção 2
%mudei o estilo de citação
\section{Related Work}
\label{sec:relatedWork}


The concept of versioning was initially proposed for controlling design evolution and co-authoring on computer aided 
design~\cite{Katz90} and software engineering~\cite{WestfechtelMC01}.
In those environments, versioning is applied to files, such that different alternatives or revisions of a document 
(e.g. source code, electronic models, product descriptions) are stored on different files.
On the context of database systems, versioning is applied for managing the evolution of different elements of the data. 
A distinguished functionality of the version concept appears when applied to structured data and managed by database systems. 
In this context, it is possible to control the evolution of different elements of the data depending on the respective data model 
(e.g. relations, tuples, columns for relational model and classes, attributes, relationships, methods for object oriented model). 
The versioning concept allows the existence of several alternatives for the evolution of database. 
With the migration of such database applications to a Web environment, they adopt the XML language
%\footnote{\url{http://www.w3.org/XML/}}
as a standard format for representation and exchange of their internal data. 
Such applications require a mechanism for the representation and manipulation of the evolution of the content of a XML document
that goes through modifications along time. Recent examples are XML version management applications \cite{MozafariZZ10}\cite{BrahmiaBGO11}\cite{CavalieriGM11}. 


While most related work focuses on different aspects of the concepts, designing models, and processing of versions efficiently, 
there is currently a lack of notations
and mechanisms for effective version management in the services domain ~\cite{PapazoglouAB11}.
Current notations for service description (i.e. WSDL/XSD) do not
properly handle versioning.
Common approaches for service versioning include the use of XML namespaces for each version that
potentially breaks the client;
version identifiers for unambiguously naming versions; or a combination of these
~\cite{BrownE04}~\cite{AndrikopoulosBM11}.
However, all these approaches address the versioning of the entire interface description document,
which leads to difficulties on measuring the actual impact of a change, either for locating the
change ~\cite{ZouFL08} or assessing its compatibility ~\cite{FokaefsMT11}. A finer-grain versioning
model based on the object-oriented paradigm is proposed in ~\cite{BeckerLM08}, but it does not fit
W3C current standards.
An abstract model for the description of services is described in
%~\cite{Papazoglou08}
~\cite{AndrikopoulosBM11}, which details all components of a WSDL service
description,
but it is targeted at the formal verification of the compatibility of service interface versions,
not addressing the service versioning problem.

Different works highlight the need for the easy detection of changes and assessment of their impact.
An approach for generating customized release notes is described in ~\cite{ZouFL08}, which includes
a service delta analyzer for detecting explicit changes between service versions represented as WSDL
documents. This approach is based on the automatic detection of differences in XML descriptions, and
it does not address the ripple effect of changes (implicit changes). A service dependency model to
quantify the ripple effect of changes in SOA is reported in ~\cite{WangC09}. It assumes that changes
are explicitly annotated in every new WSDL service description, such that they can be detected and
their ripple effect in other services can be calculated. For developing an empirical study of web
service evolution, a change detection method based on edition distance and clustering was proposed
in ~\cite{FokaefsMT11}. This method measures the similarity of a service operation in two versions
of a service. None of these approaches address the compatibility of changes.

Previous works ~\cite{BrownE04}~\cite{FangLF07}~\cite{PapazoglouAB11} discuss backward compatibility
rules, i.e. changes  that can be applied on service descriptions that do not break client
applications. However, the set of backward compatible changes is very restricted: a) addition of new
operations to an existing WSDL interface, and b) addition of new XML schema types that are not
contained within previously existing types. These are considered the core cases for compatibility in
most works that address functional components for dealing with effects of changes in the SOA (e.g.
~\cite{FrankLF08}~\cite{TreiberAD10}~\cite{Leitner2008}~\cite{FangLF07}). More recent works  propose
less restrictive rules, such as input compatibility ~\cite{BeckerLM08} or T-Shape changes
~\cite{AndrikopoulosBM11}. An algorithm that automatically detects the compatibility of service
descriptions is presented in ~\cite{BeckerLM08}, but it assumes object-oriented service
descriptions. A conceptual framework for formal compatibility assessment is discussed in
~\cite{AndrikopoulosBM11}, but this work does not include an algorithm for automatic verification.
Another algorithm for automatic compatibility detection is described in ~\cite{PonnekantiF04}, which
examines the interoperability of a specific client with regard to the aspects of a service it uses,
in order to find substitutable services. This approach is restricted to the perspective of a
particular client application, but it is one of the pioneers is mentioning the advantages of a
finer-grain unit for service versioning. Similar benefits are mentioned for service contract
compliance analysis ~\cite{AndrikopoulosBM08} and discovery of usage profiles for usage-oriented
assessment of change impact ~\cite{YamashitaBG11}~\cite{YamashitaVBG12}.

The work described in this paper complements the above mentioned works as follows: a) it proposes a
feature-oriented versioning model for the management of service evolution, which is adapted to the
W3C service description standards, b) it discusses how to automatically detect differences in WSDL
descriptions and version these differences according to this finer-grained versioning model, and c)
it adapts the compatibility assessment algorithm reported in ~\cite{BeckerLM08} to the
feature-oriented version model. In doing so, explicit changes are automatically detected, as well as
their ripple effect, and the specific compatibility of each individual change
can be assessed.
The result of this work supports various applications, such as service evolution management based on
usage profiles ~\cite{YamashitaBG11}~\cite{YamashitaVBG12}~\cite{SilvaVBG12},
reduction of provisioned versions based on proxy redirection ~\cite{FrankLF08}, and load balance
management among implemented versions,
which is proceeded by a  finer-grain deployment ~\cite{TreiberAD10}.


\section{Feature-Oriented Versioning Model}


% [karin] estruturei como o revisor C pediu
% [Karin] coloquei uma referencia para modelo de features
This section describes a feature-oriented versioning model, which aims at supporting service version
management. This model suits a number of different applications
~\cite{FrankLF08}~\cite{ZouFL08}~\cite{FrankLF08}~\cite{WangC09}~\cite{TreiberAD10}
~\cite{YamashitaVBG12}~\cite{SilvaVBG12}, but this paper focuses on its contribution for measuring
the scope of changes and
assessing compatibility on a fine-grained manner.
For this purpose, a service description is abstracted as a composition of operations that can be
requested by
client applications. Through these operations, clients and service exchange messages that are bound
to a particular format, which is recursively
described by schema elements, i.e. data \emph{types}. Because \emph{services}, \emph{operations} and
\emph{types} represent the relevant aspects that describe service functionality \cite{FangLF07},
these three concepts are referred to as service \emph{features} \cite{Kwanwoo2002}.
This abstract representation of services as features and their relationship is described in
Figure~\ref{fig:abstract_service_representation} using a UML class diagram.

\begin{figure}[b]
\begin{center}
\includegraphics[scale=0.35]{imagens/abs_service_representation2.png}
\end{center}
\vspace{-15pt}
\caption{Abstract service representation}
\label{fig:abstract_service_representation}
\vspace{-10pt}
\end{figure}


The idea of feature versioning is to provide the abstract management of the different parts of the
interface description in order to
version only the changed features, rather than the entire service. Each feature corresponds to a
portion of a WSDL/XSD service description document. Features are versioned separately, and their
dependency  relationships are maintained at version level. Hence, when a new service interface
document is exposed, it is converted into this abstract internal
representation. The features are extracted from the document, their respective descriptions and
relationships are compared to the ones of the existing  versions of the corresponding features, and
new versions are created only when changes occurred. As a consequence, a new service is represented
by interdependent features associated to existing or new versions, according to the changes. This
finer-grain of service representation allows us to control the actual modified pieces of a service
description.

The versioning model is depicted in Figure~\ref{fig:versioning_model} using a UML class diagram. A
feature is generalization of service, operation and type.
Each feature has at least one version, which in turn can depend on other versions of different
features (for instance, an \emph{operation} may depend on a set of \emph{types}).
Versions are uniquely identified by a pair <\emph{Feature.Name}, \emph{Version.Number}>, referenced
throughout the remaining of this paper as \emph{v\scriptsize{featureName,versionNumber}}.
The \emph{Version.Description} attribute corresponds to the textual description of the WSDL
document, according to the feature type.
The compatibility between two versions of a same feature is also maintained and assessed, as
described in Section~\ref{sec:compatibilityAssessment}.

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.4]{imagens/versioning_model.png}
\end{center}
\vspace{-15pt}
\caption{Versioning Model at Feature Level}
\label{fig:versioning_model}
\vspace{-5pt}
\end{figure}

\subsection{Feature Level Representation}

The feature-oriented version model establishes the following correspondences to the WSDL/XSD service
representation:

\begin{itemize}
  \item \emph{Operation}: related to the content of the tag <\emph{operation}> within both
<\emph{portType}> and <\emph{binding}> tags;
  \item \emph{Type}: related to the content of tags <\emph{element}>, <\emph{complexType}> or
<\emph{simpleType}> within <\emph{schema}> tag or the content of <\emph{message}> tag.
When addressing types, versioning is applied only to those defined outside the context of XSD
complex elements, which means that only types meant for reuse are versioned.
Hence, both primitive types (e.g. string, double, etc) and complex types, which cannot be
referenced elsewhere, are not versioned.
  \item \emph{Service}: related to all the remaining content of the interface description
document, such as the <\emph{service}> tag and the remaining content of <\emph{schema}>,
<\emph{portType}> and <\emph{binding}> tags.
\end{itemize}
 
This mapping was developed considering WSDL 1.6, but it could be easily adapted to the more recent
WSDL 2.0 with minor changes.
Figure~\ref{fig:wsdl_fragments} illustrates the mapping of the fragments of a WSDL 1.6
description to the proposed representation, using the \emph{StockQuote} service (Figure~\ref{fig:wsdl_fragments}(i)).
The description is separated into fragments to represent the
service, its operation and types, resulting in a rooted graph containing the features versions
(Figure~\ref{fig:wsdl_fragments}(ii)).
Each feature version description is associated with the corresponding WSDL fragment, as examplified in
Figures~\ref{fig:wsdl_fragments}(iii), ~\ref{fig:wsdl_fragments}(iv) and
\ref{fig:wsdl_fragments}(v).

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.43]{imagens/WSDL_fragments_v3.png}
\end{center}
\vspace{-15pt}
\caption{Example of a WSDL 1.1 description and the proposed representation}
\label{fig:wsdl_fragments}
\vspace{-5pt}
\end{figure}


\subsection{Versioning the features of an interface description document}
\label{sec:WSDLConvertion}

In order to version the features of a WSDL description document, it is necessary to identify the
features
within the document, relate them to the appropriate versions, possibly by creating new ones in
this process, and store this abstract representation in a repository.
The feature-oriented versioning process requires two steps: a) the conversion of the interface
description document into the fine-grained perspective of features, and b) the analysis of each
feature in order to discover whether it has changed with regard to existing versions
in the repository.

The model assumes the creation of a new version for a feature only if it has been explicitly
changed, or indirectly
affected by the ripple effect of a change.
A feature is \emph{changed} if it has its description fragment changed somehow, depends on
feature it did not previously depended on, or, conversely, no longer depends on a feature it
previously depended on.
A feature is \emph{affected} when it was not explicitly changed, but it depends on a feature that has
changed.

This process is illustrated in Figure~\ref{fig:wsdl_fragments}. First, the interface description
document (e.g. Figure~\ref{fig:wsdl_fragments}(i)) is converted into
the feature level representation, which results in a graph representing the features' versions and
their dependency relationships (e.g. Figure~\ref{fig:wsdl_fragments}(ii)).
Then, each feature is analyzed with regard to its corresponding feature in the repository, in order
to compare to existing related versions.
The analysis is done in a bottom-up manner regarding the graph of features in order to properly
verify all dependencies changes.
This analysis leads to four possibilities:

\begin{itemize}
  \item If the feature does not exist, then it is created together with its first version.
  \item If the feature already exists (it was previously versioned) and its description differs from
all existing versions of this particular feature, then it
is marked as changed in the graph and a new version for this feature is created.
  \item If the feature already exists and its description is equal to an existing version:
\begin{itemize}
  \item If it depends on another feature that has been already marked as changed, then a new version
is created due propagation effects.
  \item If it does not depend on any changed feature, then every other feature that depends on this
one is referenced to an already existing (equal) version.
\end{itemize}
\end{itemize}

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.5]{imagens/versions_v3.png}
\end{center}
\vspace{-10pt}
\caption{Example of versioning StockQuote}
\label{fig:versions_graph}
\vspace{-5pt}
\end{figure}

To illustrate the idea of feature versioning, suppose a provider exposes the interface description
for the first version of \emph{StockQuote}
service as depicted in Figure~\ref{fig:wsdl_fragments}(i).
The interface description is converted into the feature representation and versioned, such that each
feature is associated
with its first version (Figure~\ref{fig:wsdl_fragments}(ii)).
Suppose now that the provider exposes a new interface for this service that has two major changes:
a) a new operation with related types exchanged in messages, and b) changes the type of an existing
feature.
For the latter, suppose that the primitive type associated with \emph{TradePrice} is changed from
\emph{float} (Figure~\ref{fig:wsdl_fragments}(v)) to \emph{double}.
This new description is converted to the feature representation, and the change in \emph{TradePrice}
description is identified.
So a new version is created, and associated with this feature.
By propagation, features \emph{GetLastTradePriceOutput}, \emph{GetLastTradePrice} and
\emph{StockQuote} are affected, and hence equally versioned.
In addition, features, together with the respective versions, are created for the new operation
\emph{GetBestOffer},
which in turn depends on the newly created features \emph{GetBestOfferInput} and
\emph{GetBestOfferOutput}.
These in turn depend on other features, which either previously existed (\emph{TradePrice}) or need
to be created (\emph{BestOffer}, \emph{StatusType}).
The resulting version graph is depicted in Figure~\ref{fig:versions_graph}.

%[karin] coloquei o paragrafo inicial que o revisor C pediu
\section{Compatibility Assessment Algorithm}
\label{sec:compatibilityAssessment}

The process described in the previous section transforms an existing standard WSDL/XSD service
description into an internal representation, in which only the portions of the service explicitly
changed or affected by the change are related to new versions. Otherwise, previously existing
versions are associated to the features that constitute the service. In this way, any service
description corresponds internally to a rooted graph of versions, where each version is related to a
feature. The graph also defines the dependencies between features' versions (e.g. a service with
regard to its operations, an operation with regard to the types that describe its messages).
In addition to identifying which aspects of a service interface have changed, it is necessary to
assess if each change is backward compatible with regard to previous versions.

The algorithm proposed in this paper aims to assess compatibility between any two versions of a
service, which implies examining recursively the compatibility of all the features that describe the
service.
The assessment of compatibility at feature level is an adaptation of the algorithm
proposed in \cite{BeckerLM08}, which assesses compatibility on object-oriented service descriptions.
We have adapted this algorithm to address the compatibility checking on smaller fragments of the
WSDL/XSD
interface description, as represented by our feature-oriented versioning model.

As mentioned in Section~\ref{sec:relatedWork}, most work considers a very restricted set of backward
compatible change operations
\cite{BrownE04}\cite{FangLF07}\cite{PapazoglouAB11}\cite{BrownE04}\cite{FangLF07}: a) addition of
new operations, and b) addition of new types that are not contained within previously existing
types. These are also the compatible changes  considered in this work.
Table~\ref{table:change_cases} describes the cases addressed by the algorithm, in terms of change
operations that can be applied over the versioning model. Any other change not mentioned in
Table~\ref{table:change_cases}  is considered incompatible.


%\begin{center}   % TABLES SHOULD BE CENTERED
\begin{table}[t]
  \caption{Change cases for version compatibility} % ALWAYS INCLUDE CAPTIONS IN YOUR TABLES
  \label{table:change_cases} 
\sffamily 
\begin{tabular}{c|c|c|c|c}
\hline
\emph{Cases} & \emph{Change} & \emph{Feature Type} & \emph{Description} & \emph{Compatibility
Verdict} \\ \hline
1 & Add & Operation & Add new operation to a service & \emph{Compatible} \\ \hline
2 & Add & Type & Add new type as dependency of a new operation/type & \emph{Compatible} \\ \hline
3 & Add & Type & Add new type as dependency of an existent operation/type & \emph{Incompatible} \\
\hline
4 & Update & Type & Change in description due to order, cardinality or type & \emph{Incompatible} \\
\hline
5 & Remove & Operation & Remove operation dependency & \emph{Incompatible} \\ \hline
6 & Remove & Type & Remove type dependency & \emph{Incompatible} \\ \hline
\end{tabular}
\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
\end{table}
%\end{center}

\floatname{algorithm}{Listing}
\begin{algorithm}[b]
\caption{: compatibilityAssessment(\emph{v\scriptsize{feature,p}},   
\emph{v\scriptsize{feature,q}})}
\begin{algorithmic}[1]
 \State boolean {$compat\gets true;$}
 \State {$compat \gets evaluateRemovedDependencies(\emph{v\scriptsize{feature,p}},
   \emph{v\scriptsize{feature,q}});$}
 \State {$compat \gets compat \land evaluateDescription(\emph{v\scriptsize{feature,p}},
   \emph{v\scriptsize{feature,q}});$}
 \ForAll {$\emph{v\scriptsize{dep,Qj}} \in setOfDependencies(\emph{v\scriptsize{feature,q}})$}
%  \State {// If there is a dependency feature version with the same name but different version}
  \If{\textbf{exists} $\emph{v\scriptsize{dep,Pi}} \in
setOfDependencies(\emph{v\scriptsize{feature,p}}) \land 
(depP = depQ) \land (i \not= j)$}
 %   \State {// Verify recursively if these two versions of a same feature are in turn compatible}
   \State{$compat \gets compat \land 
compatibilityAssessment(\emph{v\scriptsize{depP,i}}, \emph{v\scriptsize{depQ,j}});$}
  \EndIf
 \EndFor
 \State{$setVerdict(\emph{v\scriptsize{feature,q}}, \emph{v\scriptsize{feature,p}}, compat);$}
 \State{\textbf{return} $compat;$}
\end{algorithmic}
\label{algorithm:compatibilityAssessment}
\end{algorithm}

The algorithm aims to recursively evaluate the compatibility relationship between two feature
versions according to the rules of Table~\ref{table:change_cases},
and to establish the compatibility relationship between them (Figure~\ref{fig:versioning_model}), with the corresponding verdict.
The pseudo-algorithm is presented in Listing 1.
It receives two feature versions as input, \emph{v\scriptsize{feature,p}} and
\emph{v\scriptsize{feature,q}}, and assess the compatibility of the latter with regard to the
former.
We assume that both versions relate to the same feature (i.e. have the same name).
The algorithm verifies if dependencies of features present in \emph{v\scriptsize{feature,p}} have
not been removed from \emph{v\scriptsize{feature,q}} (line 2),
compares the description fragment associated with the compared versions (line 3), and then
recursively evaluates the compatibility of all
corresponding dependent feature versions (lines 4-11), when it finally sets the compatibility
relationship and verdict (line 12).
The version graph rooted \emph{v\scriptsize{feature,q}}, is traversed in a depth-first manner, which
enables the propagation of detected incompatibilities to dependent versions.

Initially, the algorithm (line 2) evaluates whether feature dependencies were removed
from \emph{v\scriptsize{feature,q}} compared to \emph{v\scriptsize{feature,p}} (cases 5 and 6 of
Table~\ref{table:change_cases}). Function
\emph{evaluateRemovedDependencies} verifies if all features in the set of dependencies of
\emph{v\scriptsize{feature,p}} still exist in the set of dependencies of
\emph{v\scriptsize{feature,q}}.
In line 3, cases  3 and 4 of
Table~\ref{table:change_cases} are verified, by analyzing the textual description associated with versions
\emph{v\scriptsize{feature,q}} and \emph{v\scriptsize{feature,p}}, as described in Listing 2.

Finally, the algorithm traverses all features upon which \emph{v\scriptsize{feature,q}} depends in
order to assess their compatibility against the corresponding ones in the dependency set of
\emph{v\scriptsize{feature,p}}. For all dependencies of \emph{v\scriptsize{feature,q}} (line 4), if
there is a dependency in \emph{v\scriptsize{feature,p}} with the same feature name and different
version number (line 6),
then the algorithm is called recursively to assess the compatibility of these two versions (line 8).
If any dependency is incompatible, then the algorithm updates the
verdict to incompatible due to the ripple effect. If there is a dependent version of
\emph{v\scriptsize{feature,q}} that does not exist in
\emph{setOfDependencies}(\emph{v\scriptsize{feature,p}}),
then this situation is related to the compatible cases 1 and 2 of Table~\ref{table:change_cases}.
Finally, the algorithm returns the compatibility assessment of \emph{v\scriptsize{feature,q}}
regarding \emph{v\scriptsize{feature,p}}.
Notice that the algorithm could stop at any point where incompatibility is detected if the goal were
to detect the compatibility of the whole service. We continue the assessment to assess each feature individually. 

Function \emph{evaluateDescription}, detailed in Listing 2, currently evaluates true if: a) descriptions are exactly the same (line 2); and
b) in the case of \emph{Type} features, interpret the XML for the rules of case 4 of Table~\ref{table:change_cases} (lines 3-18). It relies on function \emph{setOfElements}, which parses the excerpt of WSDL corresponding to the description field
in order to extract the description elements and their properties for examining this case.
In the future we plan to adopt less restrictive compatibility rules (e.g.
\cite{BeckerLM08}\cite{AndrikopoulosBM11}).


\begin{algorithm}[t]
\caption{: evaluateDescription(\emph{v\scriptsize{feature,p}},\emph{v\scriptsize{feature,q}})} 
\begin{algorithmic}[1]
 \State boolean {$compat\gets true;$}
 \If{$\emph{v\scriptsize{feature,p}}(description) \not=
\emph{v\scriptsize{feature,q}}(description)$}
  \If{$\emph{v\scriptsize{feature,p}}(Feature.Type) = \emph{type}$}
   \ForAll {$\emph{e\scriptsize{j}} \in setOfElements(\emph{v\scriptsize{feature,q}})$}
    \If{\textbf{not exists} $\emph{e\scriptsize{i}} \in
setOfElements(\emph{v\scriptsize{feature,p}}) \land 
\emph{e\scriptsize{i}}(name) = \emph{e\scriptsize{j}}(name)$}
     \State {$compat\gets false;$}
    \ElsIf{$(\emph{e\scriptsize{i}}(order) \not= \emph{e\scriptsize{j}}(order) \lor 
\emph{e\scriptsize{i}}(type) \not= \emph{e\scriptsize{j}}(type) \lor 
\emph{e\scriptsize{i}}(cardinality) \not= \emph{e\scriptsize{j}}(cardinality))$}
     \State {$compat\gets false;$}
    \EndIf
   \EndFor
   \ForAll {$\emph{e\scriptsize{i}} \in setOfElements(\emph{v\scriptsize{feature,p}})$}  
    \If{\textbf{not exists} $\emph{e\scriptsize{j}} \in
setOfElements(\emph{v\scriptsize{feature,q}}) \land 
\emph{e\scriptsize{i}}(name) = \emph{e\scriptsize{j}}(name)$}
     \State {$compat\gets false;$}
    \EndIf
   \EndFor
  \Else
   \State {$compat\gets false;$}
  \EndIf
 \EndIf

 \State{\textbf{return} $compat;$}
\end{algorithmic}
\label{algorithm:evaluateDescription}
\end{algorithm}


%[karin] inclui o que o revisou pediu do protótipo, e incorporei uma estrutura de texto para
% acomadar uma versão diferente do ICWS. Mantive boa parte do texto original.

\section{Experiments}

To develop experiments with the versioning model and the compatibility assessment algorithm, we
built a prototype that follows the architecture displayed at
Figure~\ref{fig:VersionManagerArchitecture}. The \emph{WSDL/Feature Converter} module transforms a
new WSDL description into the internal versioning model as described in
Section~\ref{sec:WSDLConvertion}, and the \emph{Compatibility Analyzer} module implements the
compatibility assessment algorithm detailed in Section~\ref{sec:compatibilityAssessment}. The
\emph{Version Evolution Repository} persists the resulting features and versions in an XML file,
according to the versioning model described in Figure~\ref{fig:versioning_model}. The prototype was
developed using Java, DOM Parser and JGraphT library for
handling the versions graph.
%~\footnote[2]{\url{https://http://jgrapht.org/}}
%[karin] tirei o footnote

The eBay \emph{Trading} service
\footnote[3]{\url{https://www.x.com/developers/ebay/products/trading-api}} was selected for the
experiments.
eBay introduces a new version of this service every two weeks and supports each version for at least
18 months.
For each version, there is a release notes entry on eBay website that reports the explicit points of
change with regard to the previous version.
However, there is no information on how these changes affect other parts of the service.
The manual analysis of propagation effects is a hard task since the interface document is huge (e.g.
the most recent version of Trading service has almost 130.000 lines).
Thus, client developers are responsible for detecting whether changes affect their applications. The
release notes also report wversions are backward compatible with regard to the previous one.

We have developed two experiments examining 40 versions of \emph{Trading} service, using version 653
as baseline. The first experiment compares the advertised changes in respective the release notes
with the actual changes detected by the \emph{WSDL/Feature Converter} module. The second experiment
assesses the compatibility of each feature changed with regard to the corresponding ones in the
immediately previous version. We were not able to compare our approach with existing work that
automatically detects changes and assess compatibility due to the following reasons: a) the
algorithm we extended ~\cite{BeckerLM08} assumes an object-oriented description of service, thus
incompatible with WDSL descriptions; b) results reported in ~\cite{FokaefsMT11} do not allow
comparison, because these results are limited to the presentation of percentages of changes
categorized as inclusion, deletion and update; c) ~\cite{ZouFL08}~\cite{PonnekantiF04} focus on
detecting changes between a specific client and a service, and do not report results that compare
the changes on service versions and their compatibility; and d) code is unavailable for reproducing
the results of all aforementioned works.   

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.6]{imagens/versionManagerSketch_v2.pdf}
\end{center}
\vspace{-15pt}
\caption{Prototype Architecture}
\label{fig:VersionManagerArchitecture}
\vspace{-5pt}
\end{figure}

\subsection{Experiment 1 : Quantifying Changes}

The goal of this experiment is to compare the updates reported in the provider's release notes and
the ones detected by our prototype. For this purpose, we quantified all the explicit and cascaded
changes of each new service version with regard to the previous one by counting the newly created versions, and classifying them as
changed and affected. The results are displayed in Figure~\ref{fig:change_analysis}. eBay identifies versions using odd numbers, and because version 653 is the baseline, the graph starts at version 655.

%\vspace{-10pt}
\begin{figure}[b]
\begin{center}
\includegraphics[width=6in]{imagens/exp_change.png}
\end{center}
\vspace{-15pt}
\caption{Change analysis of eBay Trading service interface versions at feature level}
\label{fig:change_analysis}
\vspace{-5pt}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=6in]{imagens/exp_compat.png}
\vspace{-10pt}
\caption{Trading Service Compatibility Analysis}
\label{fig:compatibilityAnalysis}
\vspace{-5pt}
\end{figure}

We verified that all changed features made explicit due to our versioning model are described in the
release notes, but none of the affected ones are mentioned.
Explicitly changed features correspond in total to less than 5\% of the overall detected changes,
which means that more than 95\% of changes are not addressed in the release notes.
For instance, version 659 has introduced a single explicit change on a type feature, which is
reported in the release notes
\footnote[4]{\url{http://developer.ebay.com/Devzone/XML/docs/WebHelp/ReleaseNotesArchive.html#659}}.
However, this change affects 36 operations and 100 types that depend on it directly or indirectly,
and which are not covered by the release notes.

We observed that 99\% of explicit changes are done to types, whereas the ripple
effect reaches an average of 26\% for operations and 74\% for types.
Hence, typically a change is done to a type, and in most cases it does not directly affect an operation.
Instead, its effects cascade through several types until it affects an operation.
This experiment confirms that current information provided by release notes is insufficient for
client developers to detect which changes affect them.  We conclude that the proposed versioning model supported the efficient identification
and quantification of changes impact.

\subsection{Experiment 2 : Qualifying Changes}

In this experiment, we analyzed at feature level the compatibility of each service version with the
preceding one using our compatibility assessment algorithm. The results are presented in
Figure~\ref{fig:compatibilityAnalysis}. According to the compatibility rules we adopt
(Table~\ref{table:change_cases}), none of the service versions are backward compatible with the
previous one. This result differs from the information available in the release notes for these
versions, which report only 3 out of the 40 as backward incompatible, namely versions 689, 717 and 719.
This discrepancy is explained by eBay evolution policy, which requires that developers build client
applications that handle unrecognized data (e.g. non expected additional output
arguments). In other words, it assumes as compatible the case 3 of Table
\ref{table:change_cases}, which is reported as incompatible in related literature
~\cite{BrownE04}~\cite{FangLF07}~\cite{PapazoglouAB11}~\cite{BeckerLM08}. Hence, clients that do not
comply with their
evolution policy may be affected in every change, depending whether or not they  use the
incompatible
changed features.


This experiment indicates the usefulness of automatic compatibility assessment algorithms,
consistent with compatibility
rules  adopted by providers. In such a way, providers can easily understand the effects of their
intended
changes and even of the compatibility rules assumed.


\section{Conclusion}

We presented a versioning model and compatibility assessment algorithm for supporting evolution on a
finer grain than the typical service description WSDL/XSD documents.
The approach enables to easily identify which are the changed (or affected) features in a new
service version, and whether these features were changed in a way client applications are not
broken.
Hence, we address the identification of impact points, propagation effects, and the qualification of
changes.
We have experimented our approach in a real service, and were able to
demonstrate its usefulness for pointing out the changes performed in a service description and their
compatibility,
particularly if compared to the release notes.
The approach also provides important information for supporting service evolution by either
maximizing version reusability (e.g redirecting of requests, overload balancing, etc.)
and/or pinpointing the change impact points that basis usage based approaches
\cite{FrankLF08}\cite{TreiberAD10}\cite{ZouFL08}\cite{YamashitaVBG12}.

Future work will integrate the versioning model and compatibility assessment algorithm into the
framework designed for usage profiles analysis presented in \cite{YamashitaVBG12}\cite{SilvaVBG12}.

%\begin{bottomstuff}
%This research is financially supported by FAPERGS, CNPq and CAPES - Brazil. The authors would like to thank the anonymous referees whose comments helped to improve earlier versions of this paper.
%\end{bottomstuff}

% INCLUDE BIBLIOGRAPHY WHICH MUST FOLLOW jidm.bst TEMPLATE
\bibliographystyle{jidm}
% \bibliographystyle{plain}
\bibliography{jidmb}
% For information on how to write bibliography entries,
% see file jidmb.bib

\begin{received}
\end{received}


\end{document}