Information Technology Reference
In-Depth Information
Proof:
Supposethat thereisafeasiblesolution
x
.Then,
x
mustbeasubnet
of
N
S
because
N
S
contains all the data relations in this service portfolio.
Our decomposition algorithm finds all ASWP and conflict-free subnets
of
N
S
by iterating on all possible selection tuples, and we denote the
derived subnets set as
Vð
N
S
Þ
. Because
x
is also ASWP and conflict-free,
x 2 Vð
and that is, if there is a feasible solution, our decomposition
algorithm can find it.
N
S
Þ
3.4.2 Complexity Analysis
The complexity of each run of the decomposition algorithm equals the
complexity of traversing the reduced service net, that is, O(
)
where
V
and
E
are the vertex and edge sets of the reduced service net,
respectively. If
RSN
contains
n
OR-split places, each with
m
branches,
we have
m
n
selection tuples. In the worst case, from each tuple, we
run the decomposition algorithm and obtain one distinctive subnet.
Thus, we can have
m
n
subnets altogether. In the worst case, the
computational complexity is O((
j
V
jþ j
E
j
m
n
), that is, O(
m
n
).
In practice,
m
and
n
are usually not large. Moreover, it is observed
that some selection tuples may derive nonfeasible subnets, and
some different tuples derive identical subnets. By detecting these cir-
cumstances, many selection tuples can be simply ignored. One
circumstance is
dead path elimination
, that is, to detect whether
different selection tuples lead to the same decomposition.
As shown in Figure 3.9a, if
h
j
V
jþj
E
j
)
stands for arbitrary
value), when we apply the decomposition algorithm on the net,
p
c
3
is
removed. We can conclude that once
p
c
1
selects
t
1
, the selection value of
¼ð
t
1
; ; Þ
(
p
c
3
, that is,
Q
h
ð
, does not make a difference in terms of the result.
Thus, many different selection tuples will lead to the same decomposi-
tion result, and by using this fact, we do not have to run the decompo-
sition algorithm for each selection tuple.
The other circumstance is
lack-of-synchronization detection
, that
is, to detect whether one valuation will derive nonfeasible subnets.
When we run the decomposition algorithm, if
p
c
3
Þ
t
t
,
p
is
9
t
,
j
j >
1
^
(
9
p
2
t
such that any path from
i
to
p
does not
contain any conflict place), then this subnet must be the one with lack-
of-synchronization. At this point, the algorithm can stop and we
conclude that no feasible solution can be derived from this selection
a dead source place)
^
(
9
p
2
tuple. In Figure 3.9b,
t
d
1,
p
1
2
t
d
and
p
1
is a dead source place;
>