Database Reference
In-Depth Information
(
H
) is
H
itself; if
H
is a directed graph, then
(
H
) is its underlying undirected
then
G
G
graph.
The distance between two elements
a
and
b
in
S
, denoted by
Δ
S
(
a
,
b
) (or
Δ
(
a
,
b
),if
S
is
understood), is the distance between them in
G
(
S
).If
a
is a tuple of elements in D
OM
(
S
),
we define
Δ
(
a
,
b
) as the minimum value of
Δ
(
a
,
b
) where
a
is an element of
a
.
D
OM
(
S
)
m
, we define the instance
N
d
(
a
), called the
d-
neighborhood of
¯
ainS
, as the restriction of
S
to the elements at distance at most
d
from
a
, with the members of
a
treated as distinguished elements. That is, if two neighborhoods
N
S
1
d
Given a tuple
a
=(
a
1
,...,
a
m
)
∈
(
a
) and
N
S
2
d
(
b
) are isomorphic (written as
N
S
1
d
(
a
)
=
N
S
2
d
(
b
)), then there is an isomor-
phism
f
:
N
S
d
(
a
)
N
S
d
(
b
) such that
f
(
a
i
)=
b
i
,for1
→
≤
≤
m
.
Next we define when two tuples in different instances are locally indistinguishable. Let
S
1
and
S
2
be two instances of the same schema, and
a
in D
OM
(
S
1
) and
b
in D
OM
(
S
2
) be two
m
-tuples. We write (
S
1
,
a
)
d
(
S
2
,
b
) if there is a bijection
f
:D
OM
(
S
1
)
→
D
OM
(
S
2
) such
that
N
S
1
d
i
(
ac
)
=
N
S
2
d
(
¯
bf
(
c
)) for every
c
∈
d
relation expresses, in a sense,
the notion that locally two structures look the same, with respect to a certain bijection
f
.
In particular,
f
sends each element
c
into
f
(
c
) that has the same neighborhood.
It is important in the development of our locality tool to understand when the semantics
of a target query in data exchange depends only on the local character of the source data.
In order to do this, we introduce next the concept of
local source-dependence
that relates
notions of locality over source instances with certain answers for target queries. Intuitively,
a target query
Q
is locally source-dependent if the fact that tuples
a
and
b
of constants in
source instance
S
1
and
S
2
, respectively, are locally indistinguishable, implies that
a
and
b
cannot be distinguished by computing certain answers to
Q
over
S
1
and
S
2
. Formally:
D
OM
(
S
1
).The
Definition 7.14 (Locally source-dependent queries) Given a relational mapping
M
=
(R
s
,
R
t
,
Σ
st
) and an
m
-ary query
Q
over R
t
,where
m
≥
0, we say that
Q
is
locally source-
dependent
under
M
if there is a
d
≥
0 such that for every two source instances
S
1
and
S
2
D
OM
(
S
1
)
m
and
b
D
OM
(
S
2
)
m
,
and for every
a
∈
∈
d
(
S
2
,
b
) then
if (
S
1
,
a
)
b
(
a
∈
certain
M
(
Q
,
S
1
)
⇔
∈
certain
M
(
Q
,
S
2
)).
The main result of this section states that this notion applies to all queries that are FO-
rewritable over the canonical universal solution or over the core.
Theorem 7.15
Σ
st
)
be a relational mapping and Q a query over
R
t
.
Assume that Q is
FO
-rewritable over the canonical universal solution or over the core.
Then Q is locally source-dependent under
Let
M
=(R
s
,
R
t
,
M
.
The proof of this result is technically involved, and again depends on model-theoretical
properties of canonical universal solutions and cores (as in the case of the proof of
Theorem
7.13
). More interesting for us is the fact that this theorem is a powerful tool for proving non-
rewritability results for target FO-queries. We explain how to obtain these inexpressibility
results below.
