Reuse is not a new concept in software engineering. Ideas, abstractions, and processes have been reused by programmers since the very early days of software development. In the beginning, since storage media was very expensive, software reuse was basically to serve computers and their mechanical resources, as it substantially conserved memory. When the limitations on physical resources started to diminish, software engineers began to invent reuse approaches to save human resources as well. In addition, as the size and complexity of software systems constantly grow, organized and systematic reuse becomes essential in order to develop those systems in timely and cost-effective fashion. That is one main reason why new technologies and approaches for building software systems, such as object-oriented and component-based development, emerged in the last two or three decades. The focus of this thesis is on software components as building blocks of today's software systems. We consider components as software black boxes whose specification and external behavior are known. We assume that this information can somehow be extracted for each deployed software component. The first and basic assumption then would be the availability of a searchable repository of software components and their external behavioral specifications. Web services are a good example of such components. The most important advantage of software components is that they can be reused repeatedly in building different software systems. Reuse presents challenging problems, one of which is studied in this thesis. This problem, the composition problem, simply is creating a composite component from a collection of available components that, by interacting with each other, provide a requested functionality. When there are a large number of components available to be reused, finding a solution to the composition problem manually would require a considerable time and human effort. This could make the search practically impossible or unwieldy. However, performing the search automatically would save a significant amount of development time, cost and human effort. Solving this problem would be a huge step forward in the component-based software development. In this thesis, we concentrate on a subproblem of the composition problem, composition planning or synthesis, which is defined as finding a collection of useful components from the repository and the necessary communications among them to satisfy a requested functionality. For scalability purposes, we study automatic solutions to composition planning and propose two approaches in this regard. In one, we take advantage of graphs to model the repository, which is the collection of available components along with their behavioral specification. Graph search algorithms and a few composition-specific algorithms are used to find solutions for given component requests. In the other approach, we extend a logical reasoning algorithm and come up with algorithms for solving the composition planning problem. In both approaches we provide algorithms for finding the possibility of a composition, as well as finding the composition itself. We propose different types of composition and show how applying each would impact the behavior of a composite component. We provide the necessary formalism for capturing these types of composition through two different models: interface automata and composition algebra. Interface automata is an automaton-based model for representing the behavior of software components. The other model in this regard is composition algebra, which is an algebraic model based on CSP (Communicating Sequential Processes), CCS (Calculus of Communicating Systems), and interface automata. These formal models are used to validate the results returned by the composition approaches. We also compare the two composition approaches and show why each of them is suitable for specific types of the problem according to the repository attributes. We then evaluate the performance of the reasoning-based approach and provide some experimental results. In these experiments, we study how different attributes of the repository components could impact the performance of the reasoning-based approach in solving the composition planning problem.

Reuse is not a new concept in software engineering. Ideas, abstractions, and processes have been reused by programmers since the very early days of software development. In the beginning, since storage media was very expensive, software reuse was basically to serve computers and their mechanical resources, as it substantially conserved memory. When the limitations on physical resources started to diminish, software engineers began to invent reuse approaches to save human resources as well. In addition, as the size and complexity of software systems constantly grow, organized and systematic reuse becomes essential in order to develop those systems in timely and cost-effective fashion. That is one main reason why new technologies and approaches for building software systems, such as object-oriented and component-based development, emerged in the last two or three decades. The focus of this thesis is on software components as building blocks of today's software systems. We consider components as software black boxes whose specification and external behavior are known. We assume that this information can somehow be extracted for each deployed software component. The first and basic assumption then would be the availability of a searchable repository of software components and their external behavioral specifications. Web services are a good example of such components. The most important advantage of software components is that they can be reused repeatedly in building different software systems. Reuse presents challenging problems, one of which is studied in this thesis. This problem, the composition problem, simply is creating a composite component from a collection of available components that, by interacting with each other, provide a requested functionality. When there are a large number of components available to be reused, finding a solution to the composition problem manually would require a considerable time and human effort. This could make the search practically impossible or unwieldy. However, performing the search automatically would save a significant amount of development time, cost and human effort. Solving this problem would be a huge step forward in the component-based software development. In this thesis, we concentrate on a subproblem of the composition problem, composition planning or synthesis, which is defined as finding a collection of useful components from the repository and the necessary communications among them to satisfy a requested functionality. For scalability purposes, we study automatic solutions to composition planning and propose two approaches in this regard. In one, we take advantage of graphs to model the repository, which is the collection of available components along with their behavioral specification. Graph search algorithms and a few composition-specific algorithms are used to find solutions for given component requests. In the other approach, we extend a logical reasoning algorithm and come up with algorithms for solving the composition planning problem. In both approaches we provide algorithms for finding the possibility of a composition, as well as finding the composition itself. We propose different types of composition and show how applying each would impact the behavior of a composite component. We provide the necessary formalism for capturing these types of composition through two different models: interface automata and composition algebra. Interface automata is an automaton-based model for representing the behavior of software components. The other model in this regard is composition algebra, which is an algebraic model based on CSP (Communicating Sequential Processes), CCS (Calculus of Communicating Systems), and interface automata. These formal models are used to validate the results returned by the composition approaches. We also compare the two composition approaches and show why each of them is suitable for specific types of the problem according to the repository attributes. We then evaluate the performance of the reasoning-based approach and provide some experimental results. In these experiments, we study how different attributes of the repository components could impact the performance of the reasoning-based approach in solving the composition planning problem.

In this thesis, we present a hybrid semantic web service discovery framework that exploits both the signatures and specifications of a web service, whilst adopting logical and non-logical service matching methods. For signature level service matching, we have developed two techniques: (i) logical similarity measures applied to the services’ input/output concepts; and (b) non-logical matching based on a Structure Preserving Semantic Matching algorithm. For specification level service matching, we have applied a unique short sentence matching approach on the textual-description of a web service. We evaluated the performance of our S5 Web Service Matchmaker using the OWLS-TC dataset, and furthermore compared its performance with the OWLS-MX discovery model. Our results indicate that S5 Web Service Matchmaker offers an improved web service matching performance with a significant increase in recall and subtle improvements in precision. / Web services are independent software systems designed to offer machine-to-machine interactions over the WWW to achieve well-described operations. The description of a web service entails (a) a syntactic component detailing the service’s operations and data structures in terms of the Web Services Description Language (WSDL), and (b) a semantic component that offers a semantic description, in terms of an ontology, of the services’ data and operations. Typically, service providers expose their services to the public by providing brief descriptions of the service’s operations; the challenge is to discover the right service based on rather sparse service descriptions in response to a specific service request. In this thesis, we present a hybrid semantic web service discovery framework that offer semantic web service discovery at both the signature and specification levels of a web service, whilst exploiting logical and non-logical service matching methods. For signature level service matching, we have developed two techniques: (i) logical similarity measures applied to the services’ input/output concepts; and (b) non-logical matching based on a Structure Preserving Semantic Matching algorithm. For specification level service matching, we have applied a unique short sentence matching approach on the textual-description of a web service. The cumulative similarly measures determine the overall similarity of a services’ description with the service request. We evaluated the performance of our S5 Web Service Matchmaker using the OWLS-TC dataset, and furthermore compared its performance with the OWLS-MX discovery model. Our results indicate that S5 Web Service Matchmaker offers an improved web service matching performance with a significant increase in recall and subtle improvements in precision.