Database Reference
In-Depth Information
.
=
equality
z
j
f
i,j
(
x
)
from
χ
i
and replace every remaining occurrence of
z
j
in
χ
by
f
i,j
(
x
)
.
•
(
Construct
SOtgd)
If
S
AB
={
χ
1
,...,χ
n
}
is the set where
χ
1
,...,χ
n
are all the implications from
the previous step, then SOtgd is the formula
∃
∀
x
1
χ
1
∧···∧∀
x
n
χ
n
)
,
f
is the
tuple of all function symbols that appear in any of the implications in
S
AB
, and
the variables in
x
i
are all the variables found in the implication
χ
i
,for1
f
(
≤
i
≤
n
.
Return
the SOtgd
∃
f
(
∀
x
1
χ
1
∧···∧∀
x
n
χ
n
)
.
Every SOtgd is equivalent to an SOtgd in a
normal form
, where the right-
hand sides (i.e., the formulae
ψ
i
) are atomic formulae rather than conjunctions of
atomic formulae. For example,
∃
f
∀
x(r(x)
⇒
(r
1
(x,f (x))
∧
r
2
(f (x),x)))
is logi-
cally equivalent to
∃
f(
∀
x(r(x)
⇒
r
1
(x,f (x)))
∧∀
x(r(x)
⇒
r
2
(f (x),x)))
.Thisis
unlike the situation for (first-order) tgds (with existential quantifiers on the right-
hand sides of implications), where we would lose expressive power if we required
that the right-hand sides consist only of atomic formulae and not conjunctions of
atomic formulae.
It was shown that the composition of SOtgds is also definable by an SOtgd (with
algorithm given in [
5
]), and that the computing of certain answers of conjunctive
queries in data exchange settings specified by SOtgds can be done in
polynomial
time in the size of source database instance. The class of SOtgds is obtained from
(first-order) tgds by Skolemizing the existential first-order quantifiers into existen-
tial quantified functional symbols. This process gives rise to a class of existential
second-order formulae with no equalities, but having equalities is not sufficient to
expressively define the composition of finite sets of (first-order) tgds.
In the study of data exchange [
5
], one usually assumes an open-world assumption
(OWA) semantics, making it possible to extend instances of target schema. The
closed-world assumption (CWA) semantics was considered in [
6
] as an alternative
that only moves 'as much data as needed' from the source instance into the target
instance to satisfy constraints of a inter-schema mapping. It extends instances with
nulls as well (incomplete information), and their language of CQ-SkSTDs slightly
extends the syntax of SOtgds and is closed under composition. It was shown [
6
]
that the Skolemized constraints are closed under composition not only under OWA
but also under the CWA. If only conjunctive queries are used in mappings then,
under both OWA and CWA, the composition problem is generally NP-complete
(a model-checking for SOtgds, i.e., determining whether a given instance over the
source and target schema satisfies a SOtgd can be NP-complete, in contrast with the
first-order case, where such model-checking can be done in polynomial time). It is
valid for composition of inter-schema mappings that mix open and closed attributes
in mapping tgds.
There is subtle issue about the choice of universe in the semantics of SOtgds.
In [
5
], the universe has been taken to be a countably infinite set of elements that
included
active domain
. We recall that for a given instance
(A,B)
∈
Inst(
M
AB
)
of
an inter-schema mapping
the active domain consists of those values
that appear in
A
and
B
, so that the second-order variables (here functional symbols
M
AB
:
A
→
B
