Databases Reference
In-Depth Information
every s-t tgd
8
x
.'.
x
/ !9
y
.
x
;
y
//
in ˙ and for every tuple
a
of constants from the active domain of I, such that I ˆ
'.
a
/, if there does not exist a tuple
b
of constants or labeled nulls, such that .
a
;
b
/
exists in
chase
M
.I/, then we add to
chase
M
.I/ all facts in .
a
;
N
/,where
N
is a
tuple of new, distinct labeled nulls interpreting the existential quantified variables
y
.
We sometimes say that
M
has been applied to
I
to produce chase
M
.I/ to mean
that I has been chased with
to produce
chase
M
.I/.
We end this section by giving two examples of the chase in action. Variations of
the schemas and the mappings used in these examples will appear throughout the
paper. First, let
M
M
1
be a LAV schema mapping specified by:
Takes
.n;m;
co
/ !9s.
Student
.s;n;m/^
Enrolled
.s;co//
Here, we assume that the source schema has a ternary relation symbol
Takes
and
the target schema has two binary relation symbols,
Student
and
Enrolled
.The
mapping takes input tuples of the form .n;m;
co
/ in
Takes
,wheren represents a
student name, m represents a major for the student, and
co
represents a course that
the student takes. For each such input tuple, the mapping asserts the existence of
two target tuples: a tuple .s;n;m/in
Student
, and a tuple .s;
co
/ in
Enrolled
.
These tuples are related by the fact that the same student id s occurs in both.
Let I be the source instance consisting of the following two facts:
Takes
(John, CS, CS101)
,
Takes
(Ann, Math, MATH203)
.
The chase of I with
M
1
will then produce a target instance J that consists of the
following four facts:
Student
.
N
1
;
John, CS
/;
Enrolled
.
N
1
;
CS101
/,
Student
.
N
2
;
Ann
;
Math
/;
Enrolled
.
N
2
;
MATH203
/.
In the above instance, N
1
and N
2
are nulls (representing student ids for
John
and
Ann
, respectively). The chase of I with
M
1
works by exhaustively determining
facts in the source instance that can “trigger” the s-t tgd in
M
1
to generate new
target facts. The first fact in I, namely,
Takes
.
John
;
CS
;CS101/, triggers the s-t
tgd in
M
1
, resulting in the addition of two target facts:
Student
.N
1
;
John, CS
/
and
Enrolled
.N
1
;CS101/. Observe that this
chase step
instantiates the existen-
tially quantified variable s in the tgd with the null N
1
, which effectively associates
the newly created
Student
and
Enrolled
facts together. Similarly, the sec-
ond source fact also triggers the s-t tgd in
M
1
to generate two target facts:
Student
.N
2
;
Ann
;
Math
/ and
Enrolled
.N
2
;
MATH203
/. After this, no other
source facts could trigger the s-t tgd in
M
1
to generate new target facts. Hence,
the chase terminates with the target instance that consists of the above four facts.
As another example, let
M
2
be a GAV schema mapping specified by:
Student
.s;n;m/^
Enrolled
.s;
co
/ !
Takes
0
.s;n;
co
/
