Database Reference
In-Depth Information
Algorithm 15.3 I
NL
P
ATTERN
(
π
,
D
)
Require:
(
x
) is a tree pattern compatible with
D
.
Ensure: The returned query is a conjunctive query over I
NL
S
CHEMA
(
D
).
for all nodes
v
of
T
π(
x
)
of form
(
x
v
) do
Construct a query
Q
v
(
x
v
) as follows
if
v
is marked then
Let
π
Q
v
(
x
v
) :=
∃
id
v
∃
id
μ(
v
)
∃
zR
(
id
v
,
x
v
,
id
μ(
v
)
,
z
)
,
where
z
is a tuple of fresh variables, and the positions of variables
id
v
,
x
v
and
id
μ(
v
)
are consistent with the attributes
id
,
A
D
(
) and
id
μ(
)
respectively in
attr
(
R
).If
=
r
,then
Q
v
does not use
id
μ(
v
)
.
else
{
}
v
is not marked
v
:=
(
v
);
:=
lab
(
v
);
μ
Let
Q
v
(
x
v
) :=
∃
id
v
∃
id
μ(
v
)
∃
id
v
∃
zR
(
id
v
,
id
μ(
v
)
,
id
v
,
x
v
,
z
)
,
where
z
is a tuple of fresh variables, and the positions of the variables
id
v
,
id
μ(
v
)
,
id
v
and
x
v
are consistent with the attributes
id
,
id
μ(
)
,
id
and
A
D
(
) respectively
in
attr
(
R
).If
=
r
,then
Q
v
does not use
id
μ(
v
)
.
end if
end for
for all nodes
v
of
T
π(
x
)
do
Q
v
(
x
v
) :=
∃
y
v
ϕ
(
x
v
,
y
v
)
end for
return
y
v
∈
T
π(
x
)
ϕ
v
(
x
v
,
y
v
),where
y
has all the variables in
y
v
's without repetitions.
∃
Translating conjunctive queries over trees
Now that we have a translation of patterns, we can define a translation of conjunctive
queries based on them. Since our pattern language is quite limited, as we need to ensure
tractability, we can define queries using explicit conjunction. That is, we deal with the class
CTQ(
↓
,
=) of queries which, under our restrictions, can be defined by
Q
:=
π
|
Q
∧
Q
|∃
xQ
,
where
ranges over patterns as defined earlier. The semantics naturally extends the se-
mantics of patterns. The output of
Q
on a tree
T
is denoted by
Q
(
T
).
A query
Q
is
compatible
with the DTD
D
if every pattern used in it is compatible with
D
.
The inlining of queries
Q
compatible with
D
is given by the simple algorithm I
NL
Q
UERY
.
This algorithm ensures that Requirement 3 is satisfied: that is, the answer to every query
Q
in CTQ(
π
,
=) can be computed by its inlining on the inlining of its input (assuming, of
course, compatibility with a DTD).
↓
