Not formally, the discovery problem is the task of finding web services that match the search request with the maximum degree of similarity. The search request is a hypothetical virtual web service that satisfies the requester's requirements. At the same time, similarity should be considered and evaluated as a complex multidimensional concept, because it is very rarely possible to achieve a full match. The adequacy of the obtained result largely depends on the accuracy and completeness of the formal representation of both the purpose of the search (expressed by the target request) and the available web services. Semantic web services are defined on two levels: functional - with its main characteristics, and procedural, which contains the order, conditions and results of operations within the web service environment.

Depending on the set of web service characteristics, there are several types of the functional models, the most common of which is the IOPE model. It determines the web service by four sets: Input, Output parameters, Preconditions and Effects of the web service. Clearly, IOs (Inputs-Outputs) provide syntactic information about the web service, while PEs (Preconditions-Effects) reflect their semantics. So, this web service model is chosen as the basis for further solving problems. requester’s needs and may be defined as: = { , , , , }, where - the finite set of input parameters of the target web service, – the finite set of output parameters of the target web service, - the finite set of preconditions of the target web service, – the finite set of effects of the target web service, – the finite set of semantic items of the target web service’s context description.

According to the given model, the discovery task at the functional level can be defined as a semantic search and discovery of web services based on a step-by-step matching descriptions of the available web services with the target request, which is the description of the abstract wanted web service. The purpose of this stage is to find a web service that implements the business task, or to form a set of the web services-candidates for the further construction of the composite web service, namely:

determining the discovery goal as target request that is the representation of the virtual wanted web service; analyzed web services; analyzing the web service context and defining the categories of the request and declared web services; matching context descriptions of the target request and the available web services to reduce the set of Considering the fact that the web service specification includes the possibility of defining its short textual description (for example, in the Documentation tag of the web service’s WSDL description). It may contain information about web service’s purpose and functionality that is the web service’s context. It should be noted that this information may be considered in the process of matching the web service with the discovery (or composition) goal. At least, a meaningful structured context can allow to significantly reduce the set of web services that will be subjects to further processing at the initial stage of solving the problem. It may be realized by excluding services that have completely different purpose and functionality.

So, we can extend the IOPE model of the web service [ 1, 2 ] with the context description [ 3 ] and define the web service as: = { , , , , }, where - the finite set of input parameters of the web service, – the finite set of output parameters of the web service, – the finite set of effects of the web service, - the finite set of preconditions of the web service, – the finite set of semantic items of the web service’s context description.

The discovery goal, or the target request, is the definition of the virtual web service which expresses the or at least they are satisfied so easy as the conditions of the target request; the expected effects (defined by the target request) must be satisfied first of all; the effects of the declared web service is not less than the effects of the target request. In other words, the web service produces output parameters, the set of which is not less than the set of output (1) (2) parameters of the target request; parameters of the target request.

the declared web service requires input parameters, the set of which is not greater than the set of input the web service context is not less than the target request context; the preconditions of the declared web service are simpler than the preconditions of the target request, syntactic matching the web services and the discovery goal by their input and output parameters; semantic matching the web services and the discovery goal by their preconditions; semantic matching the web services and the discovery goal by their effects; verification of the web service, matching the web service and its specification using DL resoners; verification of non-functional characteristics of the web services [ 4 ] such as the cost, the authority, the degree of trust in the web service, the reputation of the web service etc. Note, taking into account the nonfunctional web service characteristics increases the quality of the result of the web service selection, but it essentially complicates the task;

determining the degree of a semantic suitability. Evaluating quantitative indicators of compliance of the web services and the target request and ranking the web services according to these degree values. According to the given model, the declared web service responds to the target request if: Formally, for the web service and target request represented by the extended IOPE model, the task of establishing structural correspondence can be defined as follows.

Definition 1. Let’s the web service S={s| s = (I; O; P; E; D)} from the repository is represented based on the acyclic T-BOX , where P is the finite set of the preconditions of the web service, I is the finite set of its input parameters, E is the finite set of the effects of the web service, O is the finite set of the output parameters of the web service, and the target request Q is defined as the wanted virtual web service Q= (P’; I’; E’; O’; D’), where P’ is the finite set of its preconditions, I’ is the finite set of its input parameters, E’ is the finite set of its effects, O’ is the finite set of its output parameters. The web service S matches the target request Q if D’ ⊑ D, I ⊑ I’, O’⊑ O and it exists such interpretation ℐ[ 5 ] of T-BOX as P’ℐ ⊆ Pℐ, Eℐ ⊆ E’ℐ[ 6 ].

Figure 1 bellow shows the graphic representation of the discovery task.

At the process level the discovery problem solving is complicated by the need to take into account the behavioral aspects of web services and the internal semantics of the process itself. However, it should be noted that the success of the analysis of the process model depends entirely on the quality of semantic annotations of the web services. The main features of the process of the semantic annotations of web services are:  semantic annotations have to be based on a single formal tools that may be easy automated (for example, ontologies, descriptive logics etc.), and on the unified system of concepts of the application domain;  it has to provide the annotations of all elements and steps of the process, which are significant for the web service execution and express its meaning (i.e. the completeness of the annotation system)  it should not define redundant annotations that overload the description of the web service and complicate its processing.

The process of the web service may be considered as a sequence of operations that are significant for the web service performance. Each of them has own characteristics (input and output parameters, execution conditions) and produces certain effects. Actually, these are atomic web services that may or may not depend on each other, so they can be executed sequentially or in parallel. These relations determine the dynamics of the web service and make it necessary to compare the main components of the process as atomic web services, and also to take into account their dependencies in time. To solve tasks this requires using dynamic formalisms, such as, for example, temporal [ 7, 8 ] or dynamic [ 9 ] descriptive logics.

The target request, or the wanted virtual web service, is the goal of the web service task solving. Informally, it is the business-task description that should been solved with existing web services. In real life, it is very difficult to find one web service which satisfies the goal. So, it is necessary to build the composited web service from the existing web services that will solve the given business task, that is, it will be as similar as possible to the target request. In this case, the discovery task is reduced to finding the web services - candidates for composition, and the composition task is to build a complex web service as a chain of the web services – candidates that meets the goal. It should be constructed based on dependencies of the web services and correspondences of their characteristics. In this case, the problem of defining correspondences of the web services is critical, in particular, correspondences of "predecessor-follower" type for ordering services into the chain.

Definition 2. There is a set of the web services – candidates for composition and the target request (the goal) Q ={PQ; IQ; EQ; OQ; DQ} that are represented by the model (1). The web services S1= {PS1; IS1; ES1; OS1; DS1} and S2= {PS2; IS2; ES2; OS2; DS2} may be considered as sequential S1→S2 in the result composited web service, if:  the contexts of the both web services are included in the context of the goal: DS1 ⊑ DQ та DS2 ⊑ DQ,  the output parameters of the first web service provide the values for the input parameters of the second web service: IS2 ⊑ OS1,  the effects produced by the first web service provide the preconditions of the second web service will be truth: 1 ℐ → 2 ℐ.

Note, this definition is reduced as it does not consider complex branching, when the web service follower, for example, has several predecessors.

Ontological approaches for solving tasks provide the maximum involvement of ontologies at all stages of solution building. It allows achieving a unified strict formalization of all aspects and ensures the possibility of an automated solution with the involvement of reasoners. So, to solve the complex of the web services tasks on all stages of their life cycle [16] it is proposed to use a system of DL ontologies that contains next ontology types:  The named entities taxonomy to categorize the target request and available web services while analyze their contexts [ 3 ]. This taxonomy is in some ways similar to data bases used for matching texts, for example, to the system of classes of named entities proposed by Microsoft [ 10 ], or to the special dictionaries of concepts (for example, Wordnet [ 11 ]). But, taking into account the formalization of the web service representation, this taxonomy should contribute to defining the similarity of the goal and existing declarations, and, first of all, it should allow the categorization of existing web services: by application area, by types of implemented functions, etc. So, it should include all important semantic aspects of the web services contexts. Its main goal is definition of the most complete generalized system of concepts providing the possibility of a structured semantic description of the context of any web service, regardless of its usage area or business purposes. In [ 3 ] it was proposed the prototype of such DL ontology (DocumentationOntology) defined with the description logic ALC. This ontology provides the web services categorization by their purposes, functionalities, knowledge areas etc.  The integrated ontology of the application domain. It describes the application area of the business task which have to be resolved. It should be noted, the business task, in general, can rely on several ontologies in the application domain. In this case, it is efficient to integrate them into a general unified ontology of the domain and use a single T-BOX for all web services that must be annotated in the domain. T-BOX, at the same time, has to include all concepts that must be represented in the application domain.  The top-level web service general ontology. It gives the general web service definition, i.e. it specifies the basic entities of the web service that present its main characteristics. The web service ontology must reflect the definition of the model of the web service. So, its T-BOX depends on the selected representation model. DL ontology of the web service represented by extended IOPE model on functional level will be present bellow.  The web services tasks ontologies. Actually, they are extensions of the top-level general ontology of the web service and supplement its T-BOX with statements and logical rules that formally describe the task itself and enable automated decision-making (for example, on the correspondence of the web service declaration and the goal or on the correspondence of services to each other in the composition chain) through the DL reasoners usage.  The web services ontologies allow translating the web services declarations to the formal DL language. These ontologies rely on the top-level general web service ontology and integrated ontology of application area. Also, they can use the entities from the taxonomy of the general structure of concepts (the special concepts dictionary).

To specify this ontology system previous researches were based on the basic DL . It is the effective tool for knowledge representation and ensures the execution of standard deductions. But, DL-specifications of the web services tasks require the modelling «abstract» objects (parameter, condition, service etc.) and its «specific» characteristics, in particular, time and space characteristics. These specific values can’t be represented in the model as elements of the area △. This is because when moving one interpretation to another, these "specific" elements and the links between them will change, while there is a requirement that they should be unchanged. When using descriptive logics with concrete domains, it is allocated a separate area with a fixed set of predicates. So, the interpretation “in the new sense” consists of the interpretation “in the old sense” («abstract») extended by the fixed «concrete» interpretation (with the set of predicates). Obviously, this also requires using the special roles to link these "abstract" and "concrete" elements of constructors to build concepts based on such roles and "concrete" predicates.

So, the focus of this study is the DL formalization of web services tasks, in particular, the tasks of the web services discovery and composition, using the apparatus of the descriptive logics with concrete domains.

At first, we will present the main theoretical aspects and syntax of DL with concrete domains, which we will rely on further when defining the specified tasks ontologies.

Essentially, a concrete domain is a structure of some predicate signature, i.e. the set with relations specified on it. Formally, it can be defined as follows.

Definition 3 [ 12, 13 ]. The concrete domain is the pair =(D, ), where D is a non-empty set, is a set of predicates defined on D. Assume that the given set of the predicate symbols is PN, each symbol P ∈ PN has valence n, matches it n-ary relation ⊆ . In addition, we will take into account the following agreements:  contains unary predicate, i.e. the symbol ⊤ is always included in PN and interpreted as ⊤ = .  is always closed with respect to the addition, i.e. the n –ary predicate symbol ¬P exists for each nary predicate symbol P in the signature PN and it is interpreted as △n/P .

It is clearly that any domain can be converted into the area satisfying this agreement.

Based on this definition in [14] it was introduced the description logic with the concrete domain ( ).

Definition 4. Let’s some concrete domain is given. It includes the set of the predicate symbols PN and following finite sets of the predicate symbols: CN is the set of atomic concepts, RN is the set of atomic roles, AF ⊆ RN is the set of atomic abstract attributes, CF is the set of atomic concrete attributes. Composed concrete attribute is the chain 1… ℎ with k≥1 of atomic abstract attributes ∈ and one concrete attribute h ∈ CF.

Definition 5 (Syntax of the ( ) logic). Concepts of the ( ) logic are defined by grammar: ⊤ | ⊥| | ¬ | ⊓ | ⊔ | ∃ . | ∀ . | ∃[ 1, … , ]. , where A ∈ CN, R ∈ RN, 1, … , – arbitrary (composed) attributes, P ∈ PN – n-ary concrete predicate. So, it should be noted that only new concept type ∃[ 1, … , ]. is added to syntax of DL .

Definition 6 (Semantic of ( )) [14]. Interpretation = (△, .ℐ) is defined similarly as for logic but there are next additions:  the sets △ and D do not intersect each other;  the function ℐ : △→△ is matched to each atomic attribute ∈ AF;  the function hℐ : △→ D is matched to each atomic concrete attribute h ∈ CF;  the composed concrete attribute = 1… ℎ is interpreted as the composition of the partial functions: ℐ( ) = ℎℐ( ℐ(… 1ℐ … )), its result is the partial function ℐ : △→ ;  the new concept type ∃[ 1, … , ]. is interpreted as follow:

(∃[ 1, … , ]. )ℐ = { ∈△| ∃ 1, … , ∈ : 1ℐ( ) = 1 ⋀ . . ℐ ( ) = ⋀〈 1, … , 〉 ∈ }. If all functions ℐ are defined in the point e then the formula above may be reduced:

(∃[ 1, … , ]. )ℐ = { ∈△| 〈 1ℐ( ), . . . , ℐ ( )〉 ∈ }

The concept ∃ . ⊤ expresses a set of all points where the attribute u is defined. ⊤ is not concept here, it is a concrete predicate. So, the concepts of this logic are closed under the negation operator: ¬∃[ 1, … , ]. ≡ ¬∃ 1. ⊤ ⊔ … ⊔ ¬∃ . ⊤ ⊔ [ 1, … , ]. ¬ .

Authors in [ 13 ] consider examples of the concrete domains and, also, issues of resolvability of DLs with concrete domains in general and for given domains in particular. It is proved that [15]:  if the domain is resolvable then the logic ( ) is resolvable too;  if the domain belongs to the class Pspace by complexity then the logic ( ) is PSpace-full [17].

The ontology system and the specification of DL ( ) presented above are led in the basis of DL-definition of the web services discovery and composition tasks.

composition

As mentioned above, the ontology of the web service task, in fact, is a set of DL statements, which is an extension of the top-level general ontology of the web service and it depends on the model of the web service representation. Based on the extended IOPE functional model, we define the T-BOX of the top-level general ontology of the web service ServiceOntology as follows (the prototype of the DocumentationOntology is given in [ 3 ]).

T-BOX Service, Condition, Effect, Parameter, Name, Value, Type, Context, DocItem; Service ⊑ has.DocItem; Service ⊑ has.Context; DocItem ⊑ Context; DocItem ⊑ has.ItemName; DocItem ⊑ has.ItemValue;

DocItem ⊑ BusinessDomenCategory / *link to DocumentationOntology (defines the business domain category)

DocItem ⊑ BFunctionType /* link to DocumentationOntology (defines the type of the function realized by the web service)

DocItem ⊑ MainEntitiesTypes / *link to DocumentationOntology (defines types of the entities from the named entity taxonomy)

ItemName ⊑ hasType.{String}; ItemValue ⊑ hasType.Type; Parameter ⊑ has.Name; Parameter ⊑ has.Value; Name ⊑ hasType.{String}; Value ⊑ hasType.Type; Condition ⊑ hasValue.Boolean; Service ⊑ hasInputParameters.Parameter; /* I – component of the web service Service ⊑ hasOutputParameters.Parameter /* O – component of the web service Service ⊑ hasPreCondition.Condition; /* P – component of the web service Service ⊑ hasEffect.Effect; /* E – component of the web service Service ⊑ hasServiceContext.Context; /* extension of IOPE web service model by context Type = {String, Numeric, Boolean, …}.

This study focuses on the first stage of the specification of the discovery task by means of ( ), namely, for the extended IO model of the web service, and foresees further development to the extended functional IOPE model of the web service given above, as well as to the process model of the web service.

Now let’s define the concrete domain ℎ={ , }, where = ⊔ is the union of both sets: − the set of the possible subsets of instances of the concept Parameter and is the set of the possible subsets of instances of the concept Context, is the set of the predicates defined on . For now, we will consider with unary (P1) and binary (P2) predicate symbols: P1 = {⊤}, P2= {⊆, ⊇, ≅, ≇, ⊈, ⊉}. Note that we use set theory operators. This is due to the features of the chosen domain: elements of the domain are the sets of the instances.

4.1.

Let’s define T-BOX of the discovery task ontology MatchingOntology based on ( ℎ) logic as follow. S ⊑ Service; /*link to the top-level general web services ontology ServiceOntology; Q ⊑ Service; /* link to the top-level general web services ontology ServiceOntology.

Let’s introduce the complex concept DiscoveryObject that will separate abstract services (target requests) from the web services available in the registry. Its instances are pairs “web service - target request” that correspond or do not correspond to each other.

DiscoveryObject ⊑ hasService.Service /*link with ServiceOntology; DiscoveryObject ⊑ hasQuery.Service; /* link with ServiceOntology;

Let’s hasAvailableValues is the concrete attribute in ( ℎ) description logic with values in . In this case, the concepts InputMatching and OutputMatching define the set of objects that describe the pairs “web service – target request” that match each other by the input/output parameters. Immediately, it should be noted that all the given chains use only functional roles, where:

InputMatching ≡ DiscoveryObject ⊓ (hasService hasInputParameters hasAvailableValues ⊆ hasQuery hasInputParameters hasAvailableValues),

OutputMatching ≡ DiscoveryObject ⊓ (hasQuery hasOutputParameters hasAvailableValues ⊆ hasService hasOutputParameters hasAvailableValues) and ContextMatching ≡ DiscoveryObject ⊓ (hasQuery hasContext hasAvailableValues ⊆ hasService hasContext hasAvailableValues).

So, the concept DiscoveryServices ≡ InputMatching ⊓ OutputMatching ⊓ ContextMatching specifies the set of objects that describe the pairs “web service – target request” match each other by input, output parameters and contexts, together.

4.2.

CompositionOntology.

Let’s define the T-BOX of the composition task ontology CompositionOntology based on ( ℎ) as follow.

S1 ⊑ Service; /*link with ServiceOntology S2 ⊑ Service; /*link with ServiceOntology Q ⊑ Service; /* link with ServiceOntology

Let’s introduce the special complex concept CompositionObject. Its instances are pairs “web service – web service" match (or not) each other.

CompositionObject ⊑ hasService1.Service /*link with ServiceOntology; CompositionObject ⊑ hasService2.Service; /*link with ServiceOntology; CompositionObject ⊑ hasQuery.Service; /*link with ServiceOntology.

Let’s hasAvailableValues is the concrete attribute in ( ℎ) description logic with values in . In this case, the concept ServiceMatching ≡ CompositionObject ⊓ (hasService2 hasInputParameters hasAvailableValues ⊆ hasService1 hasOutputParameters hasAvailableValues)⊓ (hasService2 hasContext hasAvailableValues ⊆ hasQuery hasContext hasAvailableValues) ⊓ (hasService1 hasContext hasAvailableValues ⊆ hasQuery hasContext hasAvailableValues) specifies the set of objects describing the pairs “web service – web service” that match each other by input/output parameters. I.e. we can construct the composited web service from the web services S1 and S2 as their sequence chain S1→S2. Note that contexts of the both web services must be included into the context of the target request. This condition may seem too strict. Really, it may be sufficient to have a non-empty intersection of the value sets of the web service contexts and the target request.

The further development of the given tasks ontologies is related to extending them with concepts that will define the pairs “web service- target request” that are similar by preconditions and effects, respectively. In the future they should expand the definition of complex concepts DiscoveryServices and CompositionObject, improving tasks definitions by additional characteristics of the web services suitability. In addition, it should be noted that the composition chain, in reality, is much wider than a sequence of web services compatible by input/output. It may contain branches, the definition of which also involves the further development of the CompositionObject ontology.

The purpose of this study is creating effective solutions for matching web services within the framework of solving the main web services tasks, in particularly, the discovery and composition problems. Proposed approach is based on the idea of maximal usage of ontologies for resolving the tasks. This implies using DL ontologies for formally describing the web services and the goal (as the virtual web service) and to represent the tasks, data, processes and algorithms. Five main types of ontologies were defined: (1) the general taxonomy of the named entities, (2) the top-level general web service ontology, (3) the unified ontology of the application domain, (4) the web services tasks ontologies and (5) the specific web services ontologies. The set of these ontologies forms the unified information system, all ontologies of which are related. Thus, the ontologies of the specific web services include relations with the ontologies of all other four types. To represent all these ontologies the descriptive logic tools were applied. In this research solving the problems was based on using DLs with concrete domains. In particularly, the logic ( ℎ) was proposed. In this logic the concrete domain is specified by the set of all subsets of the instances of the concept Parameter. It includes all possible parameters of available and wanted web services with set theoretic operations on it. Applying ( ℎ), defined in this way, allows to represent the main features of the web service by functional roles of the description logic. Also, it permits to build concepts which instances give solutions of the specified tasks. The obtained solutions are complex concepts constructed from chains of the functional roles of the ontology, concrete attributes of the concepts and set theoretic operations of descriptive logics. Thus, the concept DiscoveryServices defines the pairs of the web services (“web service – target request”) that match one other, and the concept CompositionObject determines the pairs of web services (“web service-web service”) related as «predecessor-follower». Taking into account the great formalization opportunities and available DL reasoners, this approach provides the possibility of automated and effective solving the specified tasks.

But, it should be noted that proposed tasks ontologies are reduced because: 1. They propose the solutions based on the simplified model of the web services representation which only includes matching input, output parameters and contexts. 2. Only the full compliance is considered for the discovery task. To form sets of web services – candidate that cover he target request it is necessary ease compliance conditions and consider target decomposition options. 3. For the web service composition task the different variants of complex branching and the cases of several predecessors that ensure the execution of the follower service are not included.

However this approach is open, and the proposed tasks ontologies provide the extension possibilities to create solutions of the tasks with step-by-step reducing the limits indicated above. It is the subject of further investigations.

Another important aspect is the evaluation of solvability of the ( ℎ) logic which actually leads to defining the solvability of the ℎ domain. It is also the subject of further investigations.

The author would like to thank the Institute of Software Systems of the National Academy of Sciences of Ukraine for supporting this research. [14] F. Baader, D. Calvanese, D. McGuinness, D. Nardi, P. Patel-Schneider, The Description Logic Handbook.

Cambridge University Press, 2003. [15] F. Baader, P. Hanskle, A schema for integrating concrete domains into concept languages, in: Proceeding of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI-91), pp. 452-457, Sydney, 1991. [16] O. Zakharova, The technique of using Description Logics in the process of constructing a composite service at the functional level. Problems in programming. № 1 (2018) 77-91. [17] S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090.