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 .
,
,
,
,
Search WWH ::




Custom Search