Database Reference
In-Depth Information
A lot of research has been focused on the development of logic languages for
semantic mapping between data sources and mediated schemas [
7
,
14
,
30
,
38
,
45
,
64
], and algorithms that use mappings to answer queries in data sharing systems
[
3
,
10
,
39
,
40
,
42
,
46
,
51
,
58
,
77
].
We consider that a
mapping
between two database schemas
A
=
(S
A
,Σ
A
)
and
B
=
(S
B
,Σ
B
)
is expressed by an union of “conjunctive queries with the same head”.
Such mappings are called “view-based mappings”, defined by a set of FOL sen-
tences
∀
x
i
q
Ai
(
x
i
)
⇒
q
Bi
(
y
i
)
|
≤
i
≤
n
,
with
y
i
⊆
x
i
,
1
where
is the logical implication between these conjunctive queries
q
Ai
(
x
i
)
and
q
Bi
(
x
i
)
, over the databases
⇒
, respectively.
Schema mappings are often specified by the source-to-target tuple-generating
dependencies (tgds), used to formalize a data exchange [
21
], and in the data inte-
gration scenarios under a name “GLAV assertions” [
9
,
38
]. A tgd is a logical sen-
tence (FOL formula without free variables) which says that if some tuples satisfying
certain equalities exist in the relation, then some other tuples (possibly with some
unknown values) must also exist in another specified relation.
An equality-generating dependency (egd) is a logical sentence which says that
if some tuples satisfying certain equalities exist in the relation, then some values
in these tuples must be equal. Functional dependencies are egds of a special form,
for example, primary-key integrity constraints. Thus, egds are only used for the
specification of integrity constraints of a single database schema, which define the
set of possible models of this database. They are not used for inter-schema database
mappings.
These two classes of dependencies together comprise the
embedded implication
dependencies
(EID) [
19
] which seem to include essentially all of the naturally-
occurring constraints on relational databases (we recall that the bold symbols
x
,
y
,...
denote a nonempty list of variables):
A
and
B
Definition 2
We introduce the following two kinds of EIDs [
19
]:
1. A
tuple-generating dependency
(
tgd
)
x
q
A
(
x
)
q
B
(
x
)
,
∀
⇒
where
q
A
(
x
)
is an existentially quantified formula
∃
y
φ
A
(
x
,
y
)
and
q
B
(
x
)
is an
existentially quantified formula
z
ψ
A
(
x
,
z
)
, and where the formulae
φ
A
(
x
,
y
)
and
ψ
A
(
x
,
z
)
are conjunctions of atomic formulae (conjunctive queries) over the
given database schemas. We assume the safety condition, that is, that every
dis-
tinguished
variable in
x
appears in
q
A
.
We will consider also the class of
weakly-full
tgds for which query answering
is decidable, i.e., when
q
B
(
x
)
has no existentially quantified variables, and if each
y
i
∈
∃
y
appears at most once in
φ
A
(
x
,
y
)
.
2. An
equality-generating dependency
(egd)
x
q
A
(
x
)
z
)
,
(
y
.
∀
⇒
=
