Database Reference
In-Depth Information
then a pattern uses following-sibling. If we have a subpattern of the form (
x
)[
],thena
wildcard is used in a pattern. For patterns not using the wildcard, only
(
x
) with
λ
∈
Γ
are
allowed.
Equality and inequality require some additional explanation. Having
= in
σ
means that
we can use conjuncts of the form
x
means that we can
use explicit equalities
x
=
y
in patterns, as well as reuse variables. If = is not in
=
y
in the patterns; having = in
σ
σ
,weare
only allowed to reuse variables in inequalities (if
= is in
σ
)ornowhereatall.
↓
) is the class of patterns only using the child axis. Patterns in this class
can be described as follows:
For instance,
Π
(
•
if
is a label in Γ,then
(
x
) is a pattern in Π(
↓
);and
•
if
π
1
,...,
π
m
are patterns in
Π
(
↓
),thensois
(
x
)[
π
1
,...,
π
m
].
+
,
+
, ,
=
,
The class
=) describes all (generalized) patterns.
To save space, we often write:
Π
(
↓
,
↓
→
,
→
+
,
),
•⇓
for the triple (
↓
,
↓
+
,
),and
•⇒
for the triple (
→
,
→
•∼
for the pair (=
,
=).
For example, the class of all patterns is
Π
(
⇓
,
⇒
,
∼
).
Semantics of patterns via homomorphisms
We now present a different way of defining the semantics of patterns that resembles the
semantics of conjunctive queries. One way of checking if, for a relational database
D
and a
conjunctive query
Q
(
x
),wehave
a
Q
(
D
) is to check whether we have a
homomorphism
from the tableau (
T
Q
,
x
) of
Q
into (
D
,
a
). Or, equivalently, we want to see if there is a
homomorphism
h
from
T
Q
to
D
such that
h
(
x
)=
a
.
We now apply the same approach to patterns. First, we need an analog of the notion
of tableau for patterns: that is, we need to view patterns as structures. Indeed, a pure tree
pattern can be seen as a tree-like structure
∈
+
,
+
,
lab
,
S
π
=(
U
,
↓
,
↓
→
,
→
π
,
ρ
)
,
where
U
is the set of (occurrences of) subpatterns of
π
of the form
(
x
)[
λ
], with
lab
and
ρ
naturally defined as:
•
lab
(
(
x
)[
λ
]) =
;
•
ρ
(
(
x
)[
λ
]) =
x
.
Other relations are defined as follows:
•
the relation
↓
contains all pairs
π
1
,
π
2
∈
U
such that the set under the head of
π
1
contains
μ
π
2
μ
,
λ
],where
+
,and
a list that contains
π
2
, i.e.,
π
1
=
(
x
)[
λ
,
is
→
or
→
λ
,
μ
can be empty;
all
λ
,
μ
,
+
iff
λ
];
•
(
π
1
,
π
2
)
∈↓
π
1
=
(
x
)[
λ
,//
π
2
,
