Database Reference
In-Depth Information
The class of mappings
SM
nr
(
Theorem 19.21
,
=
,
F
UN
)
is closed under composition.
Moreover, the composition of two given mappings can be computed in single-exponential
time.
↓
The composition procedure is given in
Algorithm 19.2
. We use the notation
X
←
Y
for
π
→
π
we write
h
(
X
:=
X
∪
Y
and for a homomorphism
h
:
ϕ
) to denote the substitution
of
with their images under
h
.
In this algorithm we also use two operators from
Chapter 13
: the completion operator
cpl
D
and the merge operator mrg
D
, defined on page
191
.
π
's variables in
ϕ
Algorithm 19.2 Composing XML schema mappings
Require:
SM
nr
(
M
12
=(
D
1
,
D
2
,
Σ
12
)
,
M
23
=(
D
2
,
D
3
,
Σ
23
)
∈
↓
,
=
,
F
UN
)
Require: no variables introduced on target sides
Require: pure patterns on the source side use only variables
Σ
12
:=
ϕ
−→ ⊥
ϕ
−→
ψ
∈
Σ
12
and
not satisfiable wrt
D
2
ψ
cpl
D
2
ψ
ϕ
−→
ψ
∈
Σ
12
and
ϕ
−→
satisfiable wrt
D
2
Σ
12
←
ψ
2:
{
Skolemize to remove variables introduced by cpl
D
2
}
13
:=
ϕ
−→ ⊥ ∈
Σ
12
Σ
ϕ
−→ ⊥
4:
m
:= max
(ϕ
→
ψ)
∈
Σ
23
ϕ
6:
for all
ϕ
k
−→
ψ
k
∈
Σ
12
,
k
ϕ
1
−→
ψ
1
,
ϕ
2
−→
ψ
2
, ...,
≤
m
do
{
in case of repetitions, rename variables
}
ρ
∧
η
:= mrg
D
2
(
ψ
1
∧···∧
ψ
k
)
8:
ϕ
1
∧···∧
ϕ
k
−→
η
Σ
13
←
for all
π
∧
α
−→
ψ
∈
Σ
23
and all homomorphisms
h
:
π
→
ρ
do
10:
ϕ
1
∧···∧
ϕ
k
∧
)
Σ
13
←
h
(
α
)
−→
h
(
ψ
12:
end for
end for
14:
return (
D
1
,
D
3
,
Σ
13
)
The procedure is similar to the one for relational mappings (
Algorithm 19.1
), but there
are several important differences:
Σ
12
with Σ
12
(lines 1-3);
•
Σ
13
is initialized differently (line 4);
•
ρ
•
some preprocessing replaces
is not just the conjunction of the target sides of dependencies from
Σ
12
(line 8); and
•
additional dependencies are inserted to
Σ
13
(line 9).
Let us briefly discuss these differences.
One aim of the preprocessing phase is to ensure that in Σ
12
the target side patterns are
either satisfiable with respect to
D
2
or are equal to
. In the relational case, we have this for
free, as each conjunctive query without constants is satisfiable. Observe that a dependency
ϕ
→⊥
⊥
M
12
imposes a restriction on source instances rather than solutions. Indeed, if
T
has a solution with respect to
in
M
12
,then
T
must not satisfy
ϕ
.Clearly,if
T
is to have
