International Journal of Web & Semantic Technology (IJWest) Vol.1, Num.4, October 2010

## 5.3 Algorithm For Detecting Spurious Conflicts With Respect **To The Back-End Databases** Algorithm 2: **Verify The Conflicts On Back-End Database**

1 **Initialize a hash table** Ht;
/* In the hash table H
t, a set of variables v forms the key, which is mapped to the AssignableSet of the variable set v */
2 foreach **conflicting query** q do 3 v ← **The set of instantiated variables specified in** q; 4 if VerifyConflict(v) **then**
5 Report mismatch on variable v **at database level;**
6 else **Report the conflict as spurious;**
7 end

## Function **Verifyconflict(**V)

1 vrestrict ← **The RestrictSet for the variable set** v; 2 vsplit ← **The SplitSet for the variable set** v; 3 v s restrict ← MakeSets(v**restrict**);
4 Construct a priority queue Γ **of variable sets;**
/* Γ is ordered according to the order of the instantiations of its variable sets */
5 forall the **variable set** vi ∈ v s restrict do 6 **Enqueue** vi in Γ;
7 end 8 **Table set** S
t **← {}**;
9 while Γ **is not empty** do 10 u ← **Dequeue (**Γ);
11 if (VerifyConflict(u)) **then**
/* The set of possible valuations for u is not empty */
12 t ← **Search** H
t**and return the table containing** u ;
13 if t /∈ S
t**then**
14 S
t ← S
t ∪ {t};
15 end 16 **else**
/* The set of possible valuations for u is empty, so the conflict is spurious */
17 **return false;**
18 end 19 end 20 Find the query q **that instantiates variable set** v; 21 if vsplit != ∅ **then**
22 c ← The RelevantConditionSet on the variable set v**split**;
23 δ ← SplitAssignableSet(δ, vsplit, c);
24 end 25 if δ == ∅ **then**
26 Report the conflict on v **as spurious;**
27 **return false;**
28 **else**
29 **Insert** δ in H
t; 30 **return true;**
31 end