Database Reference
In-Depth Information
We now show an algorithm for deciding if a query
q
=
/ax
[1] ::
lb
[1]
/ ···/ax
[
m
] :
lb
[
m
]inXP
{↓,↓
∗
,↑,↑
∗
,→
+
,←
+
}
is satisfiable under a fixed
nonrecursive DTD
D
. The algorithm computes for each
t
∈
T
(
s
)andfor
each
i
=1
···m
,set
S
i
of nodes reachable from the root of
t
via
/ax
[1] ::
lb
[1]
/ ···/ax
[
i
]::
lb
[
i
]. The algorithm returns “yes” if
S
m
=
∅
for some
t ∈ T
(
s
),
∈{↓, ↓
∗
, ↑, ↑
∗
}
returns “no” otherwise. If
ax
[
i
]
,then
S
i
is easily obtained from
S
i−
1
and
ax
[
i
]::
lb
[
i
] (lines 6 to 13). Let us consider the case where
ax
[
i
]=
+
.
The algorithm (i) computes the s-partition
P
1
, ··· ,P
k
of
S
i−
1
(line 15), (ii) finds
S
i,j
for each
P
j
(lines 16 to 21), where
S
i,j
is the set of nodes in
t
reachable from a
node in
P
j
via location step
ax
[
i
]::
lb
[
i
], and (iii) computes
S
i
=
S
i,
1
∪···∪S
i,k
(line 22). To obtain
S
i,j
, the algorithm first computes the set
St
of states in
G
type
(
n
p
)
that the nodes in
P
j
belong to (line 18) (by the definition of
T
(
a, r
),
for a node
n
and its parent
n
p
label
l
(
n
)mustbeastatein
G
type
(
n
p
)
). Then it
finds the set
St
of states reachable from a state in
St
in
G
type
(
n
p
)
via location
step
→
+
::
lb
[
i
] (line 19). Finally, the set
S
i,j
of nodes belonging to a state in
St
is obtained (line 20).
→
Input: A query
q
=
/ax
[1] ::
lb
[1]
/ ···/ax
[
m
]::
lb
[
m
]inXP
{↓,↓
∗
,↑,↑
∗
,→
+
,←
+
}
and a fixed nonrecursive DTD
D
=(
d, s
).
Output: “yes” or “no”.
begin
1. Compute
T
(
s
).
2.
for
each
t
∈ T
(
s
)
do
t
)with
3.
t ← n
root
(
l
(
n
root
)=
root
; /
n
root
is the “dummy” root of
t
4.
S
0
←{n
root
}
;
5.
for
i
=1
to
m
do
6.
if
ax
[
i
]=
↓
then
7.
S
i
←{n | n
is a child of a node in
S
i−
1
,l
(
n
)
=
lb
[
i
]
}
;
8.
else if
ax
[
i
]=
↓
∗
then
9.
S
i
←{n | n
isadescendantofanodein
S
i−
1
,l
(
n
)
=
lb
[
i
]
}
;
10.
else if
ax
[
i
]=
↑
then
11.
S
i
←{n | n
is the parent of a node in
S
i−
1
,l
(
n
)
=
lb
[
i
]
}
;
12.
else if
ax
[
i
]=
↑
∗
then
13.
S
i
←{n | n
is an ancestor of a node in
S
i−
1
,l
(
n
)
=
lb
[
i
]
}
;
else if
ax
[
i
]=
→
+
then
14.
15.
Find the s-partition of
S
i−
1
.Let
P
1
, ··· ,P
k
be the result.
for
j
=1
to
k
do
16.
17.
Let
n
p
be the parent of
P
j
;
18.
St←{l
(
n
)
| n ∈ P
j
}
;
19.
St
←{q
h
| q
h
is reachable from a state in
St
in
G
type
(
n
p
)
,(
q
h
)
=
lb
[
i
]
}
;
20.
S
i,j
←{n | n
is a child of
n
p
l
(
n
)
∈ St
}
;
in
t
,
21.
end
22.
S
i
← S
i,
1
∪···∪S
i,k
;
23.
else if
ax
[
i
]=
←
+
then
24. Find the s-partition of
S
i−
1
.Let
P
1
, ··· ,P
k
be the result.
25.
for
j
=1
to
k
do
26.
Let
n
p
be the parent of
P
j
;
27.
St←{l
(
n
)
| n ∈ P
j
}
;
St
←{q
h
q
h
in
28.
| St
contains a state reachable from
G
type
(
n
p
)
,
(
q
h
)
=
lb
[
i
]
}
;
l
(
n
)
∈ St
}
;
29.
S
i,j
←{n | n
is a child of
n
p
in
t
,
