Databases Reference
In-Depth Information
If there is no such an e, then set Dm = Dm* and go to stage m + 1.
Otherwise do the following:
Define em = (
µ
e)(
∃
z
,
x
,
yall
≤
m) R(z
,
e
,
x
,
y
,
e
,
m)
xm = (
µ
e)(
∃
z
,
yboth
≤
m) R(z
,
em
,
x
,
y
,
e
,
m)
ym = (
µ
e)(
∃
z
≤
m) R(z
,
em
,
xm
,
y
,
e
,
m)
where
µ
e is the least number e satisfying the condition.
For convenience let em, xm, ym be e, x, y, respectively. In step 3 of the
program it will be ensured that:
x
∈
PP
[Public] NOT
≡
y
∈
PP
[Public]
where NOT
is the not equivalent symbol.
The application of step 3 on e is called an attack on e.
≡
Step 3:
(a) Delete Pe;
(b) Reintroduce al labels Ps such that s depends on e. Let the resulting
graph be Dm+;
(c) Construct Dm from Dm+ a follows:
Case 1:
y belongs to the connected component of 0 in Dm+.
1.1 It is not the case that y
→
0inDm+.
(t(x), r(0)) (see Fig. 4a)
(That is, Dm results from Dm+ by joining the line (t(x), r(0)).
1.2 Case 1.1 does not hold
Set Dm = Dm+.
Set Dm = Dm
∪
Case 2:
y belongs to the connected component x in Dm+
2.1 x
y(Dm+)
Set Dm = Dm+
→
∪
(t(y*), r(0)) (Fig. 4b)
2.2 y
x(Dm+)
Set Dm = Dm+
→
∪
(t(x*), r(0)) (Fig. 4c)
2.3 x/y (Dm+)
Set Dm = Dm+
∪
(t(x), r(0)) (Fig. 4d)
Case 3:
Case 1 and Case 2 do not hold.
3.1 The connected component of y does not have a label.
Set Dm = Dm+
3.2 The connected component of y has a label Pj.
(i) If j
e, delete Pj and reintroduce it
Set Dm = Dm+
∪
(t(x), r(0)) (Fig. 4e)
(ii) If j
e, record that e depends on j.
Set Dm = Dm+
∪
(t(x), r(0)) (Fig. 4e)
