Database Reference
In-Depth Information
the forests or contexts that can be substituted, which will be essential in handling arbitrary
regular schemas.
r
r
r
r
...
···
a
(0)
b
(1)
b
(
n
)
c
c
c
···
a
(0)
b
(1)
a
(0)
b
(
n
)
b
(
n
)
(a) A source tree
c
(b) Partial solutions
a
(0)
b
(1)
(c) The combined solution
...
r
c
c
◦
◦
b
(1)
◦
b
(
n
)
a(0)
(e) Substituted contexts
(d) A generalized kind
Figure 12.3 Combining partial solutions under recursive schemas
Example 12.15 Let us look at the following mapping:
D
s
=
r
(
ab
)
∗
,
D
t
=
r
ab
∗
,
→
→
Σ
st
=
r
[
a
(
x
)
b
(
y
)]
.
→
b
(
y
)]
−→
r
[
a
(
x
)
→
Figures 12.4
(a) and
12.4
(b) show a source tree
T
and a possible set of partial solutions.
Unless
n
= 0, these partial solutions cannot be combined into a full solution, because in fact
there is no solution at all for
T
. This shows that extending our algorithm to mappings using
sibling order requires additional requirements on kinds. Intuitively, to ensure that partial
solutions can always be combined, we demand that large enough areas of the tree around
each port are specified. We formalize this in terms of margins, introduced in
Section 12.5
.
An example of a kind that allows combining solutions (for the mapping we are considering)
is shown in
Figure 12.4
(c). Note that this kind does not provide all the partial solutions for
T
, and this is exactly what we need: if there is no full solution, no kind should provide all
partial solutions.
...
r
r
r
r
a
(0)
b
(1)
···
b
(
n
)
a
(0)
b
(1)
a
(0)
b
(
n
)
a
(0)
b
(
i
)
◦
(a) A source tree
(b) Partial solutions
(c) A possible generalized kind
Figure 12.4 Combining partial solutions in the presence of sibling order
Thus there are two main challenges: complex schemas and sibling order. In the following