International Journal of Web & Semantic Technology (IJWest) Vol.1, Num.4, October 2010 Definition 4. The assignable set of values for a variable ϕ **is the set of values that can be assigned to** ϕ during the instantiation and it is denoted as **AssignableSet(**ϕ).

Suppose in a protocol P, a query q has variable set v = {ϕ1, ..., ϕn} and concept set C = {C1**, ..., C**m}.

Let us also assume that in P all the variables of q are uninstantiated **variables. The notion of assignable**
set in the presence of the previously instantiated variables is discussed later. The evaluation of the query basically assigns a values to each of the variables in that query. All the variables together form a tuple τ = hval1, val2, . . . , valni such that if any variable ϕk is common between class Ci **and class** Cj then both the classes have to assign same value to the variable ϕk**. All such possible tuples that**
can be populated by the evaluator side, form the assignable set of values for v **and the assignable set**
for a variable ϕiis:
AssignableSet(ϕi) = {val | ∃τ ∈ AssignableSet(v) ∧ τ = hval1, val2, ..., valni ∧ vali = val}
The dependencies **among the variables play an important role for determining the AssignableSet for a** variable. Definition 5. **In a query, if some of the variables are previously instantiated, we say that the previously**
instantiated set of variables is constraining **the set of values of the uninstantiated variables. Suppose**
in the same query q, among the variables specified in q, ϕ1, · · · , ϕk **are previously instantiated and** ϕk+1, · · · , ϕn are the variables that are instantiated by the evaluation of q. We define the **constrain**
relation RC and the ConstrainSet **as follows.**

$$\mathcal{R}_{\mathcal{C}}=\{(\varphi_{i},\varphi_{j})\ \big{|}\ \ \text{where}\varphi_{i}\in\{\varphi_{1},\cdots,\varphi_{k}\}\ \text{and}\varphi_{j}\in\{\varphi_{k+1},...,\varphi_{n}\}\}.$$  _ConstraintSet$(\varphi_{i})=\{\varphi_{k+1},\varphi_{k+2},\cdots,\varphi_{n}\}$_
Consider the same query q. The AssignableSet for the set of variables of q **is the set of all tuples** τ =
hval1, val2, . . . ..., valni **such that the following conditions hold.**

- If any variable ϕk **is placed in more than one concepts, all the concepts assign same values to** ϕk.

- (val1 ∈ A1) ∧ ... ∧ (valk ∈ Ak), where A1, · · · , Ak are the assignable sets of variable ϕ1, · · · , ϕk respectively.
Definition 6. The RestrictSet for a variable set v **is obtained by computing the transitive closure of** the RC on v.

We use the notion of the split **operation on the assignable set of values of a variable and it works**
as follows. Let a query, q, consists of concept Ci with a uninstantiated variable ϕi**, and a previously** instantiated variable ϕj . Suppose a decision is made on the variable ϕj **. In each branch, the possible** values of ϕj forms a subset of its assignable set. Since the value of ϕiis dependent on ϕj **, in each** branch the possible values for ϕi **also forms a subset of the assignable set of** ϕi.

Definition 7. The SplitSet for a variable set v is a subset of RestrictSet(v**) and is defined as:**
SplitSet(v) = {ϕj | ϕj ∈ RestrictSet(ϕi) and ϕj **appears in a condition in the path of the protocol**
from the start of the protocol to the query with ontological conflict ϕi}
Definition 8. RelevantConditionSet of a variable set v **is the set of conditions in true form on the**
variable set vsplit**, which have to be true for reaching the conflicting query.**
38