Databases Reference
In-Depth Information
pre-solution in Fig.
5.3
a. In
Fagin et al.
[
2005a
], the notion of a
weakly-acyclic
set of
tgds was introduced to guarantee that the chase terminates and generates a universal
solution.
After a canonical pre-solution has been generated by chasing the s-t tgds, to
generate an actual universal solution it is necessary to chase the target dependencies.
Notice that the chase of target tgds can be defined exactly in th
e
same way, with the
variant that it only works for assignments such that
J
.a.x//
.However,inthis
example, there is no need to chase the target tgd: the pre-solution is also a solution
for tgd
t
1
. In fact, the target tgd states that, whenever a tuple is inserted into the
Grant
table, a corresponding tuple must exist in the the
Company
table, and this is
the case in our pre-solution. Generating tgds that have this property is one of the
main intuitions behind the Clio algorithms
Miller et al.
[
2000
];
Popa et al.
[
2002
],
whichwillbediscusse
d
inmoredetailinSect.
3
.
To chase an egd
.x/
ˆ
!
.x
i
D
x
j
/
over an instance
J
, for each assignment
a
such that
J
h.x
j
/
, the chase tries to equate the two values.
We distinguish two cases: (1) both
h.x
i
/
and
h.x
j
/
are constants; in this case, the
chase procedure
fails
, since it attempts to identify two different constants; (2) at least
one of
h.x
i
/
,
h.x
j
/
is a null - say
h.x
i
/
- in this case chasing the egd generates a
new instance
J
0
obtained from
J
by replacing all occurrences of
h.x
i
/
by
h.x
j
/
.To
give an example, consider egd
e
1
:
ˆ
.a.x//
,if
h.x
i
/
¤
n;n
0
;i;i
0
;s
Company
.i
0
;n
0
;s/
i
0
/
n
0
/:
e
1
:
8
W
Company
.i;n;s/
^
!
.i
D
^
.n
D
On the two tuples generated by chasing the tgds,
Company
.23;
Yahoo
Š;
YHOO
/
,
Company
.N
2
;
Yahoo
Š;
YHOO
/
, chasing the egd equates
N
2
to the constant
23
,
based on the same value for the symbol attribute,
YHOO
. Chasing the egds returns
the canonical universal solution in Fig.
5.3
b. Notice how the canonical universal
solution is not the core universal solution, which in turn is represented in Fig.
5.3
c.
Based on these ideas, it is possible to introduce the following procedure to solve
a mapping scenario
M
given a source instance
I
:
First, chase the s-t tgds in
˙
st
on
I
to generate a canonical pre-solution,
J
pre
;
Then, chase the target constraints (target tgds and especially egds) on
J
pre
to
generate a canonical universal solution,
J
;
Minimize
J
by looking for endomorphic subsets that are still universal solutions
to generate the core universal solution,
J
0
There currently exist chase engines capable of doing this [
Savenkov and Pichler
2008
], which we will discuss thoroughly in the remainder of this chapter.
Chasing with SQL.
As an alternative, the naive chase of a set of tgds on a
g
iven
s
ou
rce
inst
ance
I
can be naturally implemented
u
sing SQL. Given a tgd
.x/
!
9
y. .x;y//
,
to
chase it over
I
we may see
.x/
as a first-order query
Q
with
free variables
x
over
S
. We may execute
Q
.I/
using SQL to find all vectors of
constants that satisfy the premise.
We
now need to insert the appropriate tuples into the target instance to satisfy
.x;y/
. However, to do this, we need to find a way to properly “invent” some fresh
