Database Reference
In-Depth Information
Hint: Design
{
S
n
}
n
>
0
,
M
,and
Q
so that
Q
(S
OL
M
(
S
n
)) behaves like the family
T
n
from
Exercise 16.3
.
16. (Source:
David et al.
(
2010
))
A pattern or a tree is
ground
if it uses only constants, i.e., it does not use vari-
ables/nulls. For a set of trees
T
,Th
gr
(
T
) denotes the set of ground patterns that are
satisfied in each tree from
T
. A ground pattern
π
is a
ground max-description
of
T
if
Mod(
π
)=Mod(Th
gr
(
T
)).
(a) Let ground(
π
) be a ground pattern obtained from
π
by dropping all the subpat-
terns
(
a
,
x
)[
...
] with nonempty
x
. Show that if
π
is a max-description of
T
,then
T
.
(b) Show that for every nonempty set of ground trees
ground(
π
) is a ground max-description of
T
, a ground max-description
) are recursive.
17. Show that the set of trees
r
[
a
(
x
1
,
x
2
)
,
a
(
x
2
,
x
3
)
,...,
a
(
x
n
−
1
,
a
n
)
,
a
(
x
n
,
x
1
)]
n
exists, and can be computed if
T
and Th
gr
(
T
∈
N
has no max-description.
