Databases Reference
In-Depth Information
a tuple
t
of
J
into a tuple
t
0
of
J
0
, we may be certain that
t
0
contains at least “as
much information as”
t
. Similarly, if
h
maps
J
into
J
0
,then
J
0
contains at least as
much information as
J
. If, on the contrary, there exists a tuple
t
in
J
that contains a
constant (like
80;000
in our example) that does not appear in
J
0
, i.e., if
J
contains
some “extra” information that is not in
J
0
, then there cannot be any homomorphism
of
t
into a tuple of
J
0
and therefore no homomorphism of
J
itself into
J
0
.
This allows us to formalize the notion of a
universal solution
. A solution
J
for
M
and source instance
I
is
universal
[
Fagin et al. 2005a
] (denoted
J
2
USol.
M
;I/
)
iff for every other solution
K
for
and
I
there is an homomorphism from
J
to
K
.
In the following, we shall only consider universal solutions.
Among these, we prefer those of minimal size. Given a scenario
M
M
,andan
instance
I
,a
core universal solution
[
Fagin et al. 2005b
]
J
2
USol.
M
;I/
, denoted
C
J
such that there is a homomorphism from
J
to
C
, but there is no homomorphism from
J
to a proper subinstance of
C
.Cores
of universal solutions are themselves universal solutions [
Fagin et al. 2005b
], and
they are all isomorphic to each other. It is therefore possible to speak of
the core
solution
as the “optimal” solution, in the sense that it is the universal solution of
minimal size [
Fagin et al. 2005b
].
The chase.
A natural question is how it is possible to derive universal solutions
for a mapping scenario and a source instance. It turns out that this can be done by
resorting to the classical
chase procedure
[
Fagin et al. 2005a
].
The chase w
o
rks differently for
t
gds and egds. Given a vector of variables
v
,an
assignment
for
v
is a mapping
a
2
Core.
M
;I/
, is a subinstance
C
NULLS
t
ha
t associates with ea
ch
universal variable a constant in
CONS
T
.
Givenaformula
.x/
with free variable
s
x
,
andaninstance
I
, we write
I
W
v
!
[
CONST
.a.x//
, whene
ve
r
I
satisfies
the formula
.a.x//
,
that is whenever
I
contains all the atoms in
.a.x//
.
Giv
en in
stances
I;J
, during the
naive chase
[
ten Cate et al.
20
09
]
1
atgd
.x/
ˆ
!
9
y. .x;y//
i
s
fired for all assignments
a
such that
I
ˆ
.a.x//
; to fire the tgd,
a
is extended to
y
by
inje
c
tively assigning to each
y
i
2
y
a fresh null, and then adding
the facts in
.a.x/;a.y//
to
J
. Consider tgd
m
2
in our example:
m
2
:
8
n;c;a;pi;n
W
Public-Company
.n;c/
^
Public-Grant
.a;pi;n/
!
9
I;S
W
Company
.I;n;S/
^
Grant
.a;I/:
On source tuples
Public-Company(Adobe, SJ)
,
Public-Grant(Adobe., Anne C.,
50,000)
it
will
generate
two
target
tuples,
Company
.N
1
;Adobe;N
2
/
,and
Grant
.50;000;N
1
/
,where
N
1
;N
2
are fresh nulls.
A solution generated by the (naive) chase is called a
canonical solution
.Itis
possible to prove [
Fagin et al. 2005a
] that each canonical solution is a universal solu-
tion. Chasing the s-t tgds in our example scenario generates the canonical, universal
1
We refer to naive chase rather than to the
standard
chase used in
Fagin et al.
[
2005a
], since
the naive chase is much simpler and rather straightforward to implement in SQL. Such chase is
sometimes calles
oblivious chase
, e.g., in
Marnette
[
2009
].
