Method and system for transitive traversal service discovery
A computer system includes a processor and an electronic storage. The processor provides a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other; translates service composition trees and the relationships of the services represented in the trees into a directed acyclic graph (DAG) that represents the service composition trees, the DAG being redundancy-free; and performs a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other. The electronic storage stores the DAG accessed by the processor. A method according to the above will perform a transitive traversal service discovery of a DAG that is redundancy-free, and optionally is minimal weighted. A non-transitory computer-readable medium can perform the method.
1. A computer system, comprising:
a processor, the processor is configured to:
provide a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other;
translate plural trees of service composition and the relationships of the services represented in the plural trees into a directed acyclic graph (DAG) that represents the plural trees of service composition, the DAG being redundancy-free; and
perform a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other; and
an electronic storage cooperatively operable with the processor, and configured to store the DAG,
wherein a service composition is a collection of interdependent services, each of the services in the service composition is represented as its own separate structure which is separate from other services in the service composition,
wherein links in the DAG are weighted with regard to performance characteristics of the services.
2. The computer system of claim 1 , wherein
the services which are in the service composition tree are formatted according to a service description language format, and data of the services contained in the service description language format in the service composition tree are translated into the DAG, and
a direction among nodes representing services within the DAG is prescribed from interdependencies of the services which are determined from the plural trees of service composition.
3. The computer system of claim 1 , wherein the DAG is further structured to conserve links that already associate services represented by nodes in the service composition tree with each other, interpreted through a transitive path traversal of the links.
4. The computer system of claim 1 , wherein the processor is further configured to
receive a search query that specifies a requested service;
propagate, in response to the search query, in the DAG, the search query for the requested service; and
return a query result from the search query that was propagated in the DAG.
5. The computer system of claim 1 , wherein the processor is further configured to
perform service discovery in the DAG using query filter criteria and selective conditions.
6. The computer system of claim 1 , wherein the processor is further configured to
orchestrate services in the DAG to keep a consistency in a service composition throughout the DAG.
7. The computer system of claim 1 , wherein the processor is further configured to
determine a closest path connecting involved services with each other.
8. The computer system of claim 1 , wherein the DAG G is a tuple G=(N, L, F, W) which includes:
a finite set of vertices or nodes N,
a finite set of vertices connecting transitions or links L,
a set of functions F describing a general dynamic behavior of a defined graph, such as bidirectional relationship like ancestor, predecessor or adjacency matrix, and
a weighting function W: L→ , where is a real number, of the DAG is defined consistent with the following:
for s sequential, p parallel, i iterative, b boolean, c a total amount of service calls, e kpi an empirical coefficient, and d a distance between a source node and a destination node of a traversal of a one of the service calls,
w
(
l
)
=
∑
source
destination
(
(
s
+
p
+
i
+
b
2
)
*
c
*
e
kpi
)
d
(
source
,
destination
)
.
9. A method to perform a transitive traversal service discovery, comprising:
providing, by a processor, a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other;
translating, by the processor, plural trees of service composition and the relationships of the services represented in the plural trees into a directed acyclic graph (DAG) that represents the plural trees of service composition, the DAG being redundancy-free; and
performing, by the processor, a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other,
wherein the DAG is stored in an electronic storage that is accessed by the processor,
wherein a service composition is a collection of interdependent services, each of the services in the service composition is represented as its own separate structure which is separate from other services in the service composition,
wherein links in the DAG are weighted with regard to performance characteristics of the services.
10. The method of claim 9 ,
wherein the services which are in the trees of service composition are formatted according to a service description language format,
further comprising translating data of the services contained in the service description language format in the service composition tree are translated into the DAG, and
prescribing a direction among nodes representing services within the DAG from interdependencies of the services which are determined from the plural trees of service composition.
11. The method of claim 9 , further comprising structuring the DAG to conserve links that already associate services represented by nodes in the service composition tree with each other, interpreted through a transitive path traversal of the links.
12. The method of claim 9 , further comprising
receiving a search query that specifies a requested service;
propagating, in response to the search query, in the DAG, the search query for the requested service; and
returning a query result from the search query that was propagated in the DAG.
13. The method of claim 9 , further comprising
performing service discovery in the DAG using query filter criteria and selective conditions.
14. The method of claim 9 , further comprising
orchestrating services in the DAG to keep a consistency in a service composition throughout the DAG.
15. The method of claim 9 , further comprising
determining a closest path connecting involved services with each other.
16. The method of claim 9 , wherein the DAG G is a tuple G=(N, L, F, W) which includes:
a finite set of vertices or nodes N,
a finite set of vertices connecting transitions or links L,
a set of functions F describing a general dynamic behavior of a defined graph, such as bidirectional relationship like ancestor, predecessor or adjacency matrix, and
a weighting function W: L→ , where is a real number, of the DAG is defined consistent with the following:
for s sequential, p parallel, i iterative, b boolean, c a total amount of service calls, e kpi an empirical coefficient, and d a distance between a source node and a destination node of a traversal of a one of the service calls,
w
(
l
)
=
∑
source
destination
(
(
s
+
p
+
i
+
b
2
)
*
c
*
e
kpi
)
d
(
source
,
destination
)
.
17. A non-transitory computer readable medium comprising executable instructions for a method for transitive traversal service discovery, the instructions being executed to perform:
providing a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other;
translating plural trees of service composition and the relationships of the services represented in the plural trees into a directed acyclic graph (DAG) that represents the plural trees of service composition, the DAG being redundancy-free; and
performing a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other,
wherein the DAG is stored in an electronic storage,
wherein a service composition is a collection of interdependent services, each of the services in the service composition is represented as its own separate structure which is separate from other services in the service composition,
wherein links in the DAG are weighted with regard to performance characteristics of the services.
18. A computer system, comprising:
a processor, the processor is configured to:
provide a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other;
translate plural trees of service composition and the relationships of the services represented in the plural trees into a directed acyclic graph (DAG) that represents the plural trees of service composition, the DAG being redundancy-free; and
perform a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other; and
an electronic storage cooperatively operable with the processor, and configured to store the DAG,
wherein a service composition is a collection of interdependent services, each of the services in the service composition is represented as its own separate structure which is separate from other services in the service composition,
wherein the DAG includes: a set of functions describing a general dynamic behavior of a defined graph, and a weighting function with regard to performance characteristics of the services.
19. A method to perform a transitive traversal service discovery, comprising:
providing, by a processor, a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other;
translating, by the processor, plural trees of service composition and the relationships of the services represented in the plural trees into a directed acyclic graph (DAG) that represents the plural trees of service composition, the DAG being redundancy-free; and
performing, by the processor, a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other,
wherein the DAG is stored in an electronic storage that is accessed by the processor,
wherein a service composition is a collection of interdependent services, each of the services in the service composition is represented as its own separate structure which is separate from other services in the service composition,
wherein the DAG includes: a set of functions describing a general dynamic behavior of a defined graph, and a weighting function with regard to performance characteristics of the services.
20. A non-transitory computer readable medium comprising executable instructions for a method for transitive traversal service discovery, the instructions being executed to perform:
providing a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other;
translating plural trees of service composition and the relationships of the services represented in the plural trees into a directed acyclic graph (DAG) that represents the plural trees of service composition, the DAG being redundancy-free; and
performing a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other,
wherein the DAG is stored in an electronic storage,
wherein a service composition is a collection of interdependent services, each of the services in the service composition is represented as its own separate structure which is separate from other services in the service composition,
wherein the DAG includes: a set of functions describing a general dynamic behavior of a defined graph, and a weighting function with regard to performance characteristics of the services.