Database Reference
In-Depth Information
The conjunction of the form
[
λ
1
]
∧
[
λ
2
] can be expressed by
[
λ
1
,
λ
2
],e.g.,
r
/
country
(
x
)
/
ruler
(
y
)
r
/
country
(
x
)
/
ruler
(
y
)
∧
can be expressed as
r
[
country
(
x
)
/
ruler
(
y
)
,
country
(
x
)
/
ruler
(
y
)]
.
The conjunction
country
(
x
)[
ruler
(
y
)
ruler
(
y
)]
country
(
x
)
/
ruler
(
y
)
∧
→
needs to be expressed as
country
(
x
)[
ruler
(
y
)
,
ruler
(
y
)
→
ruler
(
y
)]
∧
x
=
x
.
The equality
x
=
x
explicitly expresses the fact that the variables
x
and
x
are always equal
to the attribute value of the common node where the patterns are matched.
In general, the conjunction
1
(
x
)[
λ
1
]
∧
α
1
∧
2
(
y
)[
λ
1
]
∧
α
2
can be expressed as
1
(
x
)[
λ
1
,
λ
2
]
∧
α
1
∧
α
2
∧
x
1
=
y
1
∧
x
2
=
y
2
∧···∧
x
n
=
y
n
,
if only
1
(
x
) and
2
(
y
) are
compatible
, i.e.,
1
=
2
or
1
= or
2
= ,and
x
=
x
1
,
x
2
,...,
x
n
,
y
=
y
1
,
y
2
,...,
y
n
.If
1
(
x
) and
2
(
y
) are not compatible, the conjunction is always false. To
express this we allow a special pattern
⊥
, which can be seen as a new element type, never
allowed by the schema.
Classification of patterns
In our analysis we often consider patterns with a restricted set of available axes and com-
parisons. We denote classes of patterns by
is a signature indicating which
axes and comparisons are present. Specifically, we can choose from having the following
features (including navigational axes and comparisons):
Π
(
σ
),where
σ
•↓
(child),
•↓
+
(descendant),
•→
(next-sibling),
•→
+
(following-sibling),
•
(wildcard),
•
= (equality), and
•
= (inequality).
We now explain what it means to say that patterns use these features. All our patterns
will use the simple child navigation (as it corresponds to
(
x
)[
λ
]). If a subpattern of the
form
//
π
is present, then a pattern uses descendant. If a sequence of the form
μ
1
→
μ
2
is
+
present, then a pattern uses next-sibling. If a sequence of the form
μ
1
→
μ
2
is present,
