# Formal Definition

## Preliminaries

• $\mathcal{N}$ – a set of all the possible value names,
• $n \in \mathcal{N}$ – a value name,
• $\mathcal{F}$ – a set of all the possible feature names,
• $f \in \mathcal{F}$ – a feature name,
• $F \subseteq \mathcal{F}$ – a feature set,
• $V \subseteq \mathcal{F} \times \mathcal{N}$ – feature/value relation, a set of $\langle f, n \rangle$ ordered pairs, i.e. a binary relation between $\mathcal{F}$ and $\mathcal{N}$.

Example:

• F1 = {lang,type} – a feature set containing two feature names lang and type,
• V1 = {(lang,en),(lang,de),(type,text / plain) - feature/value relation contianig three ordered pairs.

## Profile

A profile is a tuple $P = \langle F_P, V_P\rangle$ describing some input/output data for a web service:

• $F_P \subseteq \mathcal{F}$ – profile features, a feature set of data features,
• $V_P: F_P \mapsto \mathcal{N}$ – profile feature/value map , a function from profile features to their values representing input data.

Example:

• $F_{P_1} = \{lang, type\}$
• $V_{P_1} = \{(lang,en),(type,text/plain)\}$

## Input

A web service input is a tuple $I = \langle F_I, V_I, F_{IU}, V_{IS}\rangle$

• input features $F_I \subseteq \mathcal{F}$ a set of features that must be present in the input of a web service,
• input feature/value relation $V_I \subseteq \mathcal{F_I} \times \mathcal{N}$ a relation representing possible values of the input features of a web service,
• user specifiable input features $F_{IU} \subseteq F_I$ features that a user may specify,
• input selected feature/value map $V_{IS} : F_I \mapsto \mathcal{N}, V_{IS} \subseteq V_I$ a total function mapping each input feature to its selected value.

Example:

• $F_{I_1} = \{lang, type\}$,
• $V_{I_1} = \{(lang,en),(lang,de),(type,text/plain),(type,application/pdf)\}$,
• $F_{ {UI}_1} = \{lang\}$,
• VIS = {(lang,en),(type,text / plain)}.

## Output

A web service output is a tuple $O = \langle F_O, V_O, V_{OS}, D, new\rangle$

• output features $F_O \subseteq \mathcal{F}$ a feature set representing an output of a web service,
• output feature/value relation $V_O \subseteq \mathcal{F_O} \times \mathcal{N}$ a relation representing possible values of the output features of a web service,
• output selected feature/value map $V_{OS} : F_O \mapsto \mathcal{N}, V_{OS} \subseteq V_O$ a total function mapping each output feature to its selected value.
• input dependence map $D: V_I \mapsto V_D$, where $V_D \subseteq 2^{V_O}$, such that $\bigcap V_D = \varnothing$ maps input feature/value pair to a set of dependent output feature/value pairs.
• new - a web service output does not include its input, i.e. $V_I \cap V_O = \varnothing$.

Example:

• $F_{O_1} = \{lang, type\}$,
• $V_{O_1} = \{(lang,en),(type,text/html)\}$,
• VOS = {(lang,en),(type,text / html)},
• $D_1 = \varnothing$,
• new1 = true.

## Service

A web service chaining description is a tuple $S = \langle I, O\rangle$.

• input I a web service input,
• output O a web service output.

## Chaining Requirements

• required input features $F_{IR} = F_I \setminus F_U$,
• matching profile values $V_{PM} = \{(f,v) \in V_P : f \in F_{I} \}$.

Example:

• $F_{ {IR}_1} = F_{I_1} \setminus F_{ {UI}_1} = \{type\}$,
• $V_{ {PM}_1} = \{(lang,en), (type,text/plain)\}$.

## Match Function

A match function $M: \langle \mathcal{S} \times \mathcal{P} \rangle \mapsto \{0,1\}$ from a set of all the possible web service/profile tuples into zero or one. If the value is one then profile $P \in \mathcal{P}$ describes a possible input of web service $S \in \mathcal{S}$. M is defined as follows: $M(S,P) = \begin{cases} 1, & F_{IR} \subseteq F_P \text{, and}\\ &V_{PM} \subseteq V_I \text{, and}\\ &\text{if }new=true \text{ then } F_O \cap F_P = \varnothing\\ 0, & otherwise \end{cases}$

Example:

Profile $P_1=\langle F_{P_1}, V_{P_1}\rangle$ describes a possible input of service $S_1=\langle I_1, O_1\rangle$ where:

• $I_1=\langle F_{I_1}, V_{I_1}, F_{ {IU}_1}, V_{ {IS}_1}\rangle$,
• $O_1=\langle F_{O_1}, V_{O_1}, V_{ {OS}_1}, D_1, new_1\rangle$

because:

• $F_{ {IR}_1} \subseteq F_{P_1}$, i.e. $\{type\} \subseteq \{lang, type\}$, and
• $V_{PM} \subseteq V_I$, i.e. $\{(lang,en),(type,text/plain)\} \subseteq \{(lang,en),(lang,de),(type,text/plain),(type,application/pdf)\}$, and
• the output is new i.e new1 = true.

## Specialisation Function

A specialisation function $E: \langle \mathcal{S} \times \mathcal{P} \rangle \mapsto \mathcal{S}$. E is defined as follows: $E(S,P) = S_N = \langle I_N, O_N\rangle$ such that:

• $I_N=\langle F_I, V_{I_N}, F_{IU}, V_{ {IS}_N}\rangle$, where:
• $V_{ {IS}_N} = \{(f,v) \in V_{IS} : f \in F_P \rightarrow (f,v) \in V_{PM}\}$,
• $V_{I_N} = \{(f,v) \in V_I : f \in F_P \rightarrow (f,v) \in V_{PM}\}$,

and

• $O_N=\langle F_{O}, V_{O_N}, V_{ {OS}_N}, new \rangle$, where:
• $V_T = \bigcup_{v \in V_{ {IS}_N} } D(v)$,
• $V_{ {OS}_N} = V_T \cup \{(f,v) \in V_{OS} : f \notin domain(V_T)\}$,
• $V_{O_N} = \{(f,v) \in V_O : f \in domain(V_T) \rightarrow (f,v) \in V_T\}$,