Database Reference
In-Depth Information
3. each formula
n
) is a conjunction of relational atomic formulae of the form
R
(
t
1
,...,
t
),where
R
is an
-ary relation symbol of R
t
and
t
1
,
...
t
are terms built from
x
i
and
f
1
,
...
,
f
m
,and
4. each variable in
x
i
(1
ψ
i
(1
≤
i
≤
≤
i
≤
n
) appears in some relational atom of
ϕ
i
.
Functions
f
1
,...,
f
m
are often referred to as
Skolem functions
.
An example of a SO tgd
is the dependency
Takes
(
n
,
c
)
→
Enrolled
(
f
(
n
)
,
c
),
seen earlier. In the syntax of
Definition 19.4
it is written as
∃
f
∀
n
,
c
(
Takes
(
n
,
c
)
→
Enrolled
(
f
(
n
)
,
c
)).
To define the semantics of SO tgds, it is necessary to specify the semantics of the ex-
istential second-order quantifiers in these dependencies. In particular, in deciding whether
(
S
,
T
)
, what should the domain and range of the functions instanti-
ating the existentially quantified function symbols be? The previous example clearly sug-
gests that such functions should operate on both constants and nulls, so we always assume
that a function symbol
f
of arity
d
is instantiated as a function
f
0
: (C
ONST
|
=
σ
,foranSOtgd
σ
V
AR
)
d
∪
→
V
AR
.
Such a function is called a
valuation
of the function symbol
f
.
Given a term
t
using variables
x
, a tuple
a
, and a valuation
f
=
f
1
,
f
2
,...,
f
n
of the func-
tion symbols used in
t
,by
t
[
f
,
a
] we denote the value obtained by evaluating the term
t
with
variables
x
substituted by
a
and the function symbols treated as corresponding functions in
f
. For instance, if the interpretation of the function symbol
f
is such that
f
0
(1)=2and
f
0
(2)=3, then for the term
t
=
f
(
f
(
x
)) we have
t
[
f
0
,
1]=
f
0
(
f
0
(1)) =
f
0
(2)=3.
Let
I
be an instance of schema R. For a relational atom
R
(
t
1
,...,
t
k
) over R, a valuation
f
of function symbols used in
t
1
,...,
t
n
, and a valuation of variables (a tuple)
a
we write
C
ONST
∪
=
R
(
t
1
,...,
t
k
)[
f
,
a
]
if
I
contains the fact
R
(
b
1
,
b
2
,...,
b
k
) where
b
i
=
t
i
[
f
,
a
]. Similarly,
I
I
|
=(
t
1
=
t
2
)[
f
,
a
] if
t
1
[
f
,
a
]=
t
2
[
f
,
a
]. The notation is naturally extended to conjunctions of relational atoms
and equalities.
|
Definition 19.5 (Semantics of SO tgds) Let
σ
be an SO tgd from R
s
to R
t
given by
ϕ
n
→
ψ
n
)
,andlet
S
be an instance of
R
s
and
T
an instance of R
t
. We say that (
S
,
T
) satisfies
∃
f
1
···∃
f
m
∀
the formula
x
1
(
ϕ
1
→
ψ
1
)
∧···∧∀
x
n
(
,if
there exists a
witnessing valuation
of symbols
f
1
,...,
f
m
, that is, a valuation
f
such that
T
σ
, denoted by (
S
,
T
)
|
=
σ
ψ
i
[
f
,
a
] whenever
S
ϕ
i
[
f
,
a
] for
i
= 1
,
2
,...,
n
.
|
=
|
=
Example 19.6 Let R
s
be a source schema consisting of a unary relation
P
,andR
t
atarget
schema consisting of a unary relation
R
,and
σ
the following SO tgd from R
s
to R
t
:
f
R
(
x
))
.
∃
∀
x
(
P
(
x
)
∧
x
=
f
(
x
)
→
Let
S
be an instance of R
s
defined as
P
S
=
{
a
}
, and assume that
T
is the empty instance
of R
t
. According to the above definition, (
S
,
T
)
since a witnessing valuation of
f
can
be any function that maps
a
to an element
b
such that
a
|
=
σ
=
b
. On the other hand, if one is
