Pattern-Based Schema Mapping and Query Answering in Peer-to-Peer XML Data Integration System - Advanced Database Query Systems - page 228

Figure 3. XML schemas, S 1 , S 2 , S 3 , and their instances I 1 , I 2 and I 3 , located in peers P 1 , P 2 , and P 3
target dependencies (STDs) (Abiteboul et al., 1995) are usually used to express schema mappings
(Fagin et al., 2004).
We adopt the approach proposed in (Fagin et al., 2004), but instead of relational schemas we will
deal with XML schemas (Arenas & Libkin, 2005; Pankowski et al., 2007). An XML schema mapping
specifies the semantic relationship between a source XML schema and a target XML schema.
Definition 10. ( schema mapping ) A mapping from a source schema S ( x ) to a target schema T ( x' , y ),
where x' ∧ x , and y ∩ x = ∧ , is a formula of the form
m ST := ∧ x ( S ( x ) ∧ ∧ y T ( x' , y )).
In other words, a mapping m ST states, that for any valuation of variables in x , if this valuation satisfies
a tree-pattern formula S ( x ), then there is such a valuation of y that T ( x' , y ) is also satisfied.
Variable names in a mapping are used to indicate correspondences between text values of paths bound
to variables. In practice, a correspondence can also involve functions that transform values of source and
target variables. These functions are irrelevant to our discussion, so they will be omitted.
The result of a mapping is a canonical instance of the right-hand side schema, where each variable y
∧ y has the ∧ ( null ) value. The target instance can be obtained using the chase procedure (Abiteboul et
al., 1995; Fagin et al., 2005; Pankowski, 2008d). In this work, however, we will propose an algorithm
(Algorithm 1) translating the high-level specification of a mapping into an XQuery program (XQuery,
2002; Pankowski, 2008c) producing the target instance from a given source instance.
Example 4. The mapping m S 3 S 1 from S 3 to S 1 (Figure 3) is specified as:
m S 3 S 1 := ∧ x 1 , x 2 , x 3 ( S 3 ( x 1 , x 2 , x 3 ) ∧ ∧ x 4 S 1 ( x 2 , x 3 , x 1 , x 4 )) =
= ∧ x 1 , x 2 , x 3 (/ authors [ author [ name = x 1 , paper [ title = x 2 , year = x 3 ]]] ∧
∧ ∧ x 4 / pubs [ pub [ title = x 2 , year = x 3 , author [ name = x 1 , university = x 4 ]]]).
Then, for I 3 = ( S 3 ( x 1 , x 2 , x 3 ), {( Ann , XML , 2005 )}),
m S 3 S 1 ( I 3 ) = ( S 1 ( x 2 , x 3 , x 1 , x 4 ), {( XML , 2005 , Ann , ∧ )}).