Database Reference
In-Depth Information
consisting of a binary predicate
Manager
and a unary predicate
SelfManager
.More-
over, assume that
M
12
=(R
1
,
R
2
,
Σ
12
) and
M
23
=(R
2
,
R
3
,
Σ
23
),where
Σ
12
consists
of the following st-tgd:
Employee
(
x
)
→∃
y
Manager
(
x
,
y
)
,
and
Σ
23
consists of the following st-tgds:
Manager
(
x
,
y
)
,
Manager
(
x
,
y
)
→
Manager
(
x
,
x
)
→
SelfManager
(
x
)
.
Use the property shown in
Exercise 22.3
to prove that the composition of
M
12
and
M
23
cannot be defined by an equality-free SO tgd.
18. (Source:
Fagin et al.
(
2005b
))
Let R
1
be a schema consisting of unary predicates
P
1
,...,
P
n
,
R
1
,...,
R
n
, R
2
a schema
consisting of unary predicates
S
1
,...,
S
n
and R
3
a schema consisting of unary predicate
T
.Moreover,let
M
12
=(R
1
,
R
2
,
Σ
12
) and
M
23
=(R
2
,
R
3
,
Σ
23
),where
Σ
12
consists of
the following st-tgds:
P
i
(
x
)
→
S
i
(
x
)
,
i
= 1
,...,
n
,
R
i
(
x
)
→
S
i
(
x
)
,
i
= 1
,...,
n
,
and
Σ
23
consists of the following st-tgd:
S
1
(
x
)
∧···∧
S
n
(
x
)
→
T
(
x
)
.
Prove that if
M
13
is a mapping specified by an SO tgd and defining the composition
M
13
hasatleast2
n
conjuncts.
19. (Source:
Amano et al.
(
2009
))
Show that
of
M
12
with
M
23
,then
12
and
23
+
,
M
M
↓
,
↓
there are mappings
in SM(
=)
such that
23
) is undecidable. Prove the same for SM(
M
12
,
M
↓
,
→
,
=) and
C
OMPOSITION
(
=). Hint: Use the idea from
Theorem 19.15
20. (Source:
Amano et al.
(
2009
))
C
ONS
C
OMP
(σ ) is the following decision problem: Given mappings
M,M
∈
SM(
SM(
↓
,
→
,
M
σ
), decide if
the composition of
M
and
is consistent. Show that
) is in E
XPTIME
.
21. (Source:
Amano et al.
(
2009
))
Show that the complexity of C
ONS
C
OMP
(
C
ONS
C
OMP
(
⇓
,
⇒
σ
),definedin
Exercise 22.3
, is at least as
high as that of C
ONS
(
σ
). (In particular C
ONS
C
OMP
(
⇓
,
=) and C
ONS
C
OMP
(
↓
,
→
,
=)
are undecidable and C
ONS
C
OMP
(
) is E
XPTIME
-hard.) Show that the same holds
even if both input mappings for C
ONS
C
OMP
(
⇓
,
⇒
σ
) are assumed to be consistent.
22. (Source:
Amano et al.
(
2009
))
Let
D
1
=
{
r
→
ε
}
and
D
3
=
{
r
→
c
1
?
c
2
?
c
3
?
}
with no attributes. For each of the
classes SM
nr
(
+
),SM
nr
(
),SM
nr
(
+
),SM
nr
(
=) give an example of two
mappings whose composition is the mapping between
D
1
and
D
3
consisting of pairs
of trees (
r
,
T
),where
T
matches either
r
/
c
1
or
r
/
c
2
.
↓
,
↓
↓
,
→
↓
,
→
↓
,