Data exchange by example - Foundations of Data Exchange - page 6

To complete the description of the rule, we need to clarify the role of variables src , dest ,
airl and dep . The meaning of the rule is that for every tuple (src,dest,airl,dep) in
table FLIGHT we have to create tuples in relations ROUTES and INFO FLIGHT of the target
schema. Hence, finally, the meaning of the first rule is:
∀ src ∀ dest ∀ airl ∀ dep FLIGHT(src,dest,airl,dep) −→
∃ f# ∃ arr ROUTES(f#,src,dest)

∧ INFO FLIGHT(f#,dep,arr,airl) .

Note that this is a query written in relational calculus, without free variables. In other
words, it is a sentence of first-order logic, over the vocabulary including both source and
target relations. The meaning of this sentence is as follows: given a source S ,atarget
instance we construct is such that together, S and T satisfy this sentence.
We now move to the second rule. Unlike the first, it looks at two tuples in the source:
(src,dest,airl,dep) in FLIGHT and (city,country,popul) in GEO . If they satisfy
the join condition city = scr , then a tuple needs to be inserted in the target relation SERVES :

FLIGHT(src,dest,airl,dep) , GEO(city,country,popul) , city = src
−→

SERVES(airl,city,country,phone) .

As with the first rule, the actual meaning of this rule is obtained by explicitly quantifying
the variables involved:
∀ city ∀ dest ∀ airl ∀ dep ∀ country ∀ popul
FLIGHT(city,dest,airl,dep)

∧ −→

GEO(city,country,popul)

∃ phone SERVES(airl,city,country,phone) .

We can also have a similar rule in which the destination city is moved in the SERVES table
in the target:

popul
FLIGHT(src,city,airl,dep) ∧ GEO(city,country,popul) −→
∃

∀ ∀ ∀ ∀ ∀ ∀

city dest airl dep country

phone SERVES(airl,city,country,phone) .

These rules together form what we call a schema mapping : a collection of rules that
specify the relationship between the source and the target. When we write them, we ac-
tually often omit universal quantifiers

∀ , as they can be reconstructed by the following

rule:

• every variable mentioned in one of the source relations is quantified universally.

With these conventions, we arrive at the schema mapping ,shownin Figure 1.3 .

Now, what does it mean to have a target instance, given a source instance and a mapping?
Since mappings are logical sentences, we want target instances to satisfy these sentences,
with respect to the source. More precisely, note that mappings viewed as logical sentences

M