Source-linked AI summary
An Integrated Semantic Web Service Discovery and Composition Framework
Pablo Rodriguez-Mier, Carlos Pedrinaci, Manuel Lama, Manuel Mucientes
TL;DR
The paper addresses the limited integration between service discovery and graph-based composition, especially the need for efficient discovery during composition. It proposes an integrated framework with fine-grained I/O discovery, optimal composition search, and graph optimisations, and reports scalability and flexibility in empirical analysis. The framework remains data-flow centric and is constrained by repository size and DAG-based composition limitations.
Problem
Service discovery and composition have largely evolved independently despite their dependency, leaving integrated performance and scalability insufficiently addressed.
Method
The paper integrates graph-based composition with fine-grained semantic I/O discovery, optimal search, graph optimisations, and a reference implementation combining iServe and ComposIT.
Results
The empirical analysis shows that typical discovery approaches are unsuitable for integrated composition, while appropriate discovery granularity and indexing optimisations achieve top performance.
Takeaways & Limitations
The analysis provides insights for designing scalable and flexible integrated composition systems in distributed real-world settings.
Takeaways & Limitations
The framework remains data-flow centric, and graph generation can still be bottlenecked by repository size.
Abstract
from arXiv · showhide
In this paper we present a theoretical analysis of graph-based service composition in terms of its dependency with service discovery. Driven by this analysis we define a composition framework by means of integration with fine-grained I/O service discovery that enables the generation of a graph-based composition which contains the set of services that are semantically relevant for an input-output request. The proposed framework also includes an optimal composition search algorithm to extract the best composition from the graph minimising the length and the number of services, and different graph optimisations to improve the scalability of the system. A practical implementation used for the empirical analysis is also provided. This analysis proves the scalability and flexibility of our proposal and provides insights on how integrated composition systems can be designed in order to achieve good performance in real scenarios for the Web.
1 INTRODUCTION
Service discovery is essential to composition but has evolved largely separately from it, creating response-time, granularity, registry-integration, and scalability challenges. The paper proposes an integrated graph-based framework addressing these challenges through fine-grained discovery, optimal search, and graph optimisation.
- Service discovery must be performed repeatedly during composition, despite discovery and composition research having evolved largely independently.
- Existing discovery interfaces assume fully specified requests, while composition engines require fine-grained partial input-output discovery.
- Discovery response times can be orders of magnitude too slow for composition engines that may issue thousands of requests during composition.
- Many composition engines reimplement discovery locally and assume all services are available through local preloading.
- The proposed framework integrates graph-based composition with semantic I/O discovery, optimal search, and graph optimisations for scalability.
- The framework is data-flow centric and leaves preconditions and effects aside because fewer than 5% of semantic Web services include them.
2 RELATED WORK
Prior work addresses discovery or composition effectively in selected settings, but commonly lacks their integrated treatment, fine-grained discovery, registry integration, optimal search, or scalable graph optimisation. The paper positions its framework as combining these capabilities.
- Service-composition research includes AI planning and graph-based input-output approaches, with different assumptions about expressiveness, availability, and search.
- AI-planning approaches handle expressive preconditions and effects but generally assume locally available services, high response times, and no redundancy-reduction optimisation.
- Leading graph-based approaches can achieve good performance and low response times, but some lack optimality, fail on large datasets, or omit registry integration.
- An integrated prior framework supports semantic discovery and composition but lacks fine-grained requests, graph-size optimisation, and optimal composition search.
- The proposed framework combines fine-grained I/O discovery, reduced composition-discovery overhead, optimal search, and graph optimisations.
3 WEB SERVICE COMPOSITION PROBLEM
The paper formulates semantic service composition as constructing an invokable composite service whose outputs satisfy a request, using semantic input-output matching and a DAG. It also identifies expressiveness and usability boundaries of this data-flow formulation.
- A semantic Web service is modeled by its ontology-linked input and output concepts within a service registry.
- Semantic matchmaking uses exact, plugin, subsume, and fail degrees, but exact and plugin matches are retained for semantically complete compositions.
- Fine-grained input and output discovery identifies services that partially match available inputs or produce some or all target outputs.
- Composition requires finding a composite service invokable from the request inputs and producing all requested outputs.
- The composition is represented as a DAG whose service nodes and semantic-match arcs encode execution order.
- The DAG representation cannot explicitly invoke a service twice, while concept-based requests are less user-friendly than keyword-based requests.
4 COMPOSITION FRAMEWORK
The framework begins with an input-output composition request, generates a graph of relevant services and semantic relations, and interleaves graph construction with discovery. The section presents generic strategies for these phases.
- The framework provides a graph-based process for automatic semantic Web service composition.
- A composition request specifies user inputs and expected outputs, which trigger composition-graph generation.
- Graph generation builds a graph containing relevant services and semantic relations among their inputs and outputs.
- Composition-graph generation is interleaved with discovery, which retrieves relevant services for data available at different stages.
- The framework section analyses each phase and provides generic strategies based on the formal composition problem.
4.1 Semantic Matchmaking
Semantic matchmaking assesses compatibility between service input and output concepts using ontology-based semantic reasoning. The resulting match function supports discovery and composition, with worst-case complexity O(m·n) for concept sets of sizes n and m.
- Semantic matchmaking: Semantic matchmaking assesses compatibility between concepts using an ontology and semantic reasoning, notably subsumption.It supports discovering services with semantically compatible inputs or outputs and generating composition-graph relations.
- Match function: The match function applies compatible matching to concept pairs between source and target concept sets.It calls cmatch for each pair and uses the semantic reasoner to determine their semantic relation.
- Complexity: O(m) is the best-case complexity, whereas O(m·n) is the worst-case complexity for concept sets of sizes n and m.The worst case entails at most m×n calls to cmatch and, ultimately, the semantic reasoner.
4.2 Semantic Service Discovery
Semantic service discovery for composition must retrieve partially matching services from partial input or output information, rather than requiring complete service descriptions. The discovery algorithm scans the repository and uses semantic matching to identify relevant services.
- Discovery requirements: Composition requires fine-grained discovery that rapidly returns services matching some available inputs or expected outputs.This relaxed interface supports exploring combinations of services that may jointly satisfy a request.
- Discovery algorithm: The discovery algorithm sequentially scans all services and tests input or output relevance with the matchmaker.A service is relevant when at least one input or output is compatible with the supplied concepts.
- Complexity: O(w) is the discovery complexity, or O(w·m·n) when each service has at most m outputs and n inputs.The worst case makes at most |W| calls to Match across a repository of w services.
4.3 Service Composition Graph Generation
The composition graph is a layered DAG connecting concepts and services whose inputs can be matched from preceding outputs. Forward generation selects relevant services layer by layer, while indexing reduces repository-dependent discovery costs but does not remove repository size as a bottleneck.
- Graph representation: The composition graph is a layered DAG whose vertices contain services and concepts, with edges for input, output, and semantic concept relations.Its layers group services invokable from concepts produced in previous layers, with dummy boundary services representing request inputs and outputs.
- Graph representation: The graph contains services that can be directly or indirectly invoked from the request inputs and organizes them by invocation layer.The initial and final dummy layers encode the request inputs and goal outputs.
- Forward graph generation: Forward generation selects input-relevant services for each layer, removes matched inputs, and places services with no unmatched inputs into the current layer.The process begins with services fully matched by the request inputs and continues using outputs from preceding layers.
- Index-Based Optimisations: The repository size w remains a graph-generation bottleneck despite search-time improvements from indexing.The repository is usually orders of magnitude larger than the other parameters in the complexity.
- Index-Based Optimisations: Indexing maps ontology concepts to input- or output-relevant services, enabling constant-time relevant-service retrieval during graph generation.The inverted index is independent of composition requests and can be built from services and ontologies.
- Index-Based Optimisations: With indexes, relevantIO′ provides O(1) retrieval per concept and reduces the indexed complexity to O(l·m(1 + w/k)).For w = 1000, l = 10, m = 5, n = 5, and k = 100, the example requires approximately 2.55·10^3 operations, two orders of magnitude below the non-indexed version.
4.4 Graph-Based Optimisations
The framework reduces composition graphs through backward pruning and interface-based abstractions while preserving the functionality needed for optimal composition search.
- Backward pruning: Output-relevant services are identified recursively by matching their outputs to a target service’s inputs.Services at increasing distances are added through repeated application of X(w).
- Backward pruning: Backward pruning removes services that are neither directly nor indirectly relevant to the output goals.The method computes the transitive closure of output-relevant services and deletes all other graph services.
- Interface dominance: Input-dominant services require only a subset of the information needed by the services they dominate.The paper illustrates this relationship with w7 being input-dominant over w6.
- Interface dominance: Interface equivalence and dominance compare services according to how their inputs and outputs connect to the rest of the graph.Input equivalence concerns the services supplying inputs, whereas output equivalence concerns services consuming outputs.
- Interface dominance: Interface-dominance optimisation substitutes services with abstract interfaces, reducing the search space while preserving functionality.The original services can be restored after the optimal workflow is found.
4.5 Optimal Composition Search
The composition problem is formulated as state-space search over graph concepts and services, with transitions applying service actions to satisfy request goals efficiently.
- Search objective: The search seeks a succession of actions with minimum cost, such as fewer services, shorter execution paths, or better QoS.The state representation can vary with the selected forward or backward strategy.
- Search formulation: Composition search is modelled as a state-transition system Σ = (S, A, γ) with states, actions, and a transition function.The corresponding problem includes an initial state and a set of goal states.
- Search formulation: States represent sets of graph concepts, while actions represent sets of services that can be applied during composition.For backward search, states contain unsatisfied concepts and actions contain graph services.
- State transitions: Applying an action removes concepts matched by service outputs and adds the services’ input concepts as newly unsatisfied requirements.This transition defines how the search moves between composition states.
- Search optimisation: Search efficiency improves by pruning actions that create dead ends, duplicate equivalent choices, or cannot yield a better solution.These optimisations are applied to the available actions for each state.
5 REFERENCE IMPLEMENTATION
The reference implementation integrates iServe’s fine-grained semantic discovery with ComposIT’s graph-based composition engine, then searches the generated graph for an optimal workflow.
- Architecture: The implementation combines iServe as the service registry and discovery component with ComposIT as the graph-based composition engine.Integration adapters delegate semantic discovery and matchmaking from ComposIT to iServe.
- Architecture: Composition requests generate graphs layer by layer by discovering semantically relevant services through iServe’s fine-grained I/O support.The Semantic Discovery Engine uses the Service Manager and KB Manager for retrieval and semantic reasoning.
- iServe: iServe provides a Linked Data service registry, semantic reasoning, advanced discovery, and analysis components for generating semantic service descriptions.This work primarily uses its registry and discovery functionality.
- iServe: The discovery infrastructure uses service and knowledge-base managers to retrieve services, concepts, properties, and hierarchical concepts.Implementations combine indexes with SPARQL queries over the triple store.
- Evaluation configurations: The evaluated configurations range from pure SPARQL discovery and matchmaking to indexed discovery with caching and fully indexed operation.Full indexing avoids SPARQL queries during discovery and matchmaking after load-time population.
- Composition search: ComposIT uses A* search to select a shortest composition with the minimum number of services from the generated graph.Multiple workflows may exist because different services can produce outputs matching the same concept.
6 EVALUATION
The evaluation measures scalability, discovery impact, and configuration performance on WSC’08 datasets ranging from 158 to 8,119 services. Indexed discovery and caching substantially reduce composition time, while discovery and matchmaking remain the dominant computational cost.
- Experimental setup: The evaluation uses WSC’08 datasets containing 158 to 8,119 services to measure scalability across increasingly large service sets.Services were transformed into MSM descriptions and imported into iServe.
- Experimental setup: Table 2 compares composition-graph size, graph-generation time, SPARQL-query counts, optimized graph size, and composition-search time across Discovery/Matchmaking configurations.Composition search includes graph optimisations and optimal A* backward search.
- Results: 77% of total composition time is spent on Full Indexed Discovery/Matchmaking on average, showing that discovery and matchmaking dominate even in the optimal configuration.Without index and cache optimisation, their share rises to about 99%.
- Results: 1,656 seconds is required by direct backend querying on the largest dataset, making the SPARQL D/M configuration prohibitively slow.The graph requires semantic matching and relevant-service discovery at every layer, producing thousands of SPARQL queries.
- Results: The indexed-and-cached configuration calculates almost every composition in less than a minute and reduces generated SPARQL queries by up to 91%.The larger WSC’08-08 dataset still requires 15,844 queries and 78 seconds with caching alone, whereas full indexing avoids composition-time SPARQL evaluation.
- Results: The framework shows similar scalability on WSC’09-10 datasets and solves all datasets with optimal results.The reported optimal results are provided through the project resource.
7 CONCLUSIONS
The paper integrates service discovery and matchmaking into a graph-based composition framework and evaluates the resulting implementation across different configurations. Its analysis shows that fine-grained interfaces and indexing can support efficient composition without requiring local, in-memory service registries.
- Contributions: The paper presents a theoretical analysis of service composition based on its dependency on service discovery.The framework integrates discovery and matchmaking within the composition process.
- Contributions: A reference implementation combines iServe and ComposIT to empirically study discovery and matchmaking during service composition.The implementation provides three configurations with varying performance.
- Findings: Typical discovery-engine approaches produce prohibitive execution times and are unsuitable as efficient foundations for service composition.This conclusion follows from the empirical analysis of discovery and matchmaking performance.
- Findings: Fine-grained interfaces and indexing enable efficient composition without requiring local availability or in-memory preloading of service registries.The resulting performance is described as akin to that of the fastest composition engines.
- Implications: The proposal is presented as scalable and flexible for distributed real-world settings involving registries and composition frameworks controlled by diverse organisations.The conclusion frames the work as providing design insights for integrated composition systems.