On the other hand, the answer to the query “Is there a flight from Paris to Santiago?” is
“yes”, as the tuple including Paris and Santiago will be in every solution. Intuitively, what
we want to do in query answering in data exchange is to return answers that will be true in
every solution. These are called certain answers ; we shall define them formally shortly.
XML data exchange
Before outlining the key tasks in data exchange, we briefly look at the XML representation
of the above problem. XML is a flexible data format for storing and exchanging data on the
Web. XML documents are essentially trees that can represent data organized in a way more
complex than the usual relational databases. But each relational database can be encoded
as an XML document; a portion of our example database, representing information about
the Paris-Santiago flight and information about Santiago, is shown in the picture below.
The tree has a root r with two children, corresponding to relations FLIGHT and GEO .
Each of these has several children, labeled t 1 and t 2 , respectively, corresponding to tuples
in the relations. We show one tuple in each relation in the example. Each t 1 -node has four
children that correspond to the attributes of FLIGHT and each t 2 -node has three children,
with attributes of GEO . Finally, each of the attribute nodes has a child holding the value of
To reformulate a rule in a schema mapping in this language, we show how portions of
trees are restructured. Consider, for example, the rule
FLIGHT(city,dest,airl,dep) ∧ GEO(city,country,popul) −→
∃ phone SERVES(airl,city,country,phone)