Database Reference
In-Depth Information
•
for every inequality
x
=
y
in
α
,wehave
h
(
x
)
=
h
(
y
).
In either case we write
h
:
T
.
An immediate observation is that the semantics of tree pattern satisfaction can be stated
in terms of homomorphisms:
π
→
T
instead of the more formal
h
:
S
π
→
Lemma 11.5
For each pattern
π
(
x
)
1. T
|
=
π
(
a
)
iff there is a homomorphism h
:
π
→
T such that a
=
h
(
x
)
;
2. T
|
=
π
iff there is a homomorphism from
π
to T .
Evaluation of tree patterns
We now look at basic decision problems related to the evaluation of tree patterns, as well
as their satisfiability. We start with evaluating tree patterns, formulated as follows.
PROBLEM
:
ATTERN
E
VAL
.
INPUT:
A tree pattern
π
,atree
T
, a tuple
a
.
|
QUESTION
: D s
T
=
π
(
a
)?
The problem P
ATTERN
E
VAL
corresponds to the combined complexity of pattern evalua-
tion. For each fixed pattern
π
, we have a problem P
ATTERN
E
VAL
(
π
), whose input consists
only of
T
and
a
, with the question whether
T
|
=
π
(
a
). This corresponds to data complexity
of pattern evaluation.
Since patterns are essentially conjunctive queries over trees, the data complexity is in
L
OGSPACE
(and the bound cannot be lowered in general, since transitive closures of
↓
and
→
may have to be computed). And since they are tree structured conjunctive queries, the
combined complexity is tractable as well. More precisely, we have:
Proposition 11.6
The problem
P
ATTERN
E
VAL
(
π
)
is in
L
OGSPACE
for each pattern
π
;
moreover, there exist patterns
π
so that
P
ATTERN
E
VAL
(
π
)
is
L
OGSPACE
-complete. The
problem
P
ATTERN
E
VAL
is solvable in
P
TIME
.
Proof
Take a tree pattern
π
(
x
), a tuple
a
,andatree
T
. Checking that
T
|
=
π
(
a
) can
be done in P
TIME
by a bottom-up evaluation of the subpatterns of
π
(
a
), i.e., the pattern
π
(
x
) with variables
x
evaluated according to
a
. The idea is to annotate each node
v
with
aset
Φ
(
v
) of the subformulae of
π
(
a
) satisfied in
v
. More precisely, if
v
is a leaf labeled
and storing a tuple
b
,let
σ
(
b
),
with
σ
Φ
(
v
) contain all subpatterns of
π
(
a
) of the form
σ
∈{
σ
with
, having children
v
1
,
v
2
,...,
v
k
,and
storing a tuple
b
,letΦ(
v
) contain all subpatterns of π(
a
) of the form σ
(
b
)[λ
1
,
λ
2
,...,
λ
p
]
satisfying
,
}
.If
v
is an internal node labeled with
σ
•
σ
∈{
σ
,
}
,
•
for each
λ
i
=
//
π
1
there exists a node
v
j
such that
//
π
1
∈
Φ
(
v
j
) or
π
1
∈
Φ
(
v
j
),
•
for each
λ
i
=
π
1
1
π
2
2
...
r
−
1
π
r
there exists a sequence 1
≤
n
1
<
n
2
<...<
n
r
≤
k
such that
π
j
∈
Φ
(
v
n
j
),andif
j
=
→
then
n
j
+1
=
n
j
+1forall
j
,
