Database Reference
In-Depth Information
.
(a)
1
(b)
start
c
a
3
5
a
c
2
*
|
b
q
I
c
7
b
8
.
6
3
4
a
b
b
c
b
4
7
8
c
b
Fig. 2.
(a) tree representation of
r
=(
a|b
)(
cb
)
∗
and (b) the Glushkov automaton of
r
Finally, let us define subquery
Q
i
used in (3) (1
≤ i ≤ n
).
m
+1
/x/ ···/x /B
c
i
/c/ ···/c /T
c
/ ↑
n−i
+1
/c/ ···/c /T
c
Q
i
=
::
c
(12)
n
+1
m
+1
/ ↑
::
c/ ···/ ↑
::
c/↑
::
B
c
/ ↑
::
x/ ···/ ↑
::
x/↑
::
r
(13)
Starting from the root
r
, subquery (12) checks if clause
C
i
is true. Then the
context node goes back to the root
r
by subquery (13).
Now it is easy show that
φ
is satisfiable
iff
q
is satisfiable under
D
.
4 Satisfiability Problem without Upward Axis
As shown in the previous section, the satisfiability problem is intractable under
fixed DTDs if upward axes are allowed. In this section, we consider the satisfiabil-
ity problem without upward axes, i.e., SAT(XP
{↓,↓
∗
,→
+
,←
+
}
) under fixed DTDs.
It is shown that SAT(XP
{↓,→
+
,←
+
}
) is NP-complete under unfixed DTDs [10].
On the other hand, we show in this section that SAT(XP
{↓,↓
∗
,→
+
,←
+
}
)isin
PTIME under fixed DTDs.
In the following, we first show Glushkov automaton, which is used in the
algorithms proposed in this and the next sections. Then we show a polynomial-
time algorithm for solving SAT(XP
{↓,↓
∗
,→
+
,←
+
}
) under fixed DTDs.
4.1 Glushkov Automaton
Let
r
be a regular expression. We associate each label occurring in
r
with a unique
number to identify the label; we use the tree representation of
r
(Fig. 2(a)), and
assume that each node is numbered in prefix order, called
position
.By
r
#
we
mean the
superscripted
regular expression of
r
obtained by superscripting each
label occurring in
r
by its corresponding position. By
sym
(
r
#
)wemeantheset
of superscripted labels occurring in
r
#
. For example, if
r
=(
a|b
)(
cb
)
∗
,then
r
#
=
(
a
3
.Let
a
i
be a superscripted label of
a
.By(
a
i
)
we mean the label resulting from
a
i
by dropping the superscript of
a
i
,thatis,(
a
i
)
=
a
.
|b
4
)(
c
7
b
8
)
∗
and
sym
(
r
#
)=
{a
3
,b
4
,c
7
,b
8
}
