144
Omar Boucelma, Mehdi Essid, and Yassine Lassoued
Let us consider, for instance, a basic query Q e and its binding B = {M i , i ∈
1 . . . n} where n is the number of sources that support the feature queried by Q e and
M i , i ∈ 1 . . . n, are their respective mappings. To extract the maximum of information from the local sources, first we rewrite Q e with a given mapping of the binding,
then we try to look for the unsupported attributes (if they exist) using the other mappings of the binding. To do this we use the notion of prefix query and suffix query.
Given a mapping M i of a source S i , a prefix query Q p is a subquery of Q e that
consists in extracting only the attributes supported by S i . Note that M i provides a
full-binding for query Q p . The suffix query Q s is the subquery consisting in extracting the remaining attributes (plus the key’s attributes).
Given these definitions, for each mapping M i ∈ B, Q e is processed as follows:
1. compute Q p and Q s of the query Q e and the mapping M i ;
2. let B s = {M j , M j ∈ B, j i};
3. let B i = {M i };
4. the execution plan of query Q e using the binding B i is the join between Q p and
the execution plan of Q s using the binding B s .
Since queries that are responsible for extracting feature information are executed
by the WFS servers, they are reformulated, using the mapping rules, into queries
that are expressed in terms of local schemas (each feature is replaced by the corresponding feature, each attribute is replaced by the corresponding attribute, and
the conditions of the rule (cf. Sect. 7.4) are added to the set of conditions of the
query). This reformulation generates a problem because the answer to this query
(the answer of the WFS) is written in terms of the local schema. To alleviate this
problem, an additional GQuery query is added to perform the inverse transformation. Queries query03 and query04 illustrated in Fig. 7.11 are examples of such
queries.
Let us now discuss constraints of the prefix and the suffix queries. It is easy to
see that the prefix query contains only the subset of conditions over attributes of
the prefix query. However, the suffix query contains the subset of conditions over
attributes of the suffix query extended by the set of conditions of the prefix query.
This extended set is used to refine the prefix query in adding more conditions. This
allows us to minimize the number of extracted tuples, hence minimizing the execution time. Finally, a condition that is not supported by a data source is added to the
GQuery expression, which is responsible for the transformation of the result: this is
the case where the source contains the attributes on which the condition is made but
the capabilities of the source cannot support it.
Figure 7.10 illustrates the rewriting algorithm which, given an elementary query
Q e and its binding B, computes the execution plan expressed in terms of the local
sources. As we may notice, B s is defined as {M j ∈ B, j > i} and not as {M j ∈
B, j i} as mentioned in the beginning of this section. We made this change in order
to eliminate duplicated answers. In fact, the subset of mappings {M k ∈ B, k < i} has
already been treated in the previous step; hence it is useless to compute it again.
To compute the final execution plan, we rewrite each elementary query of the
GEP. As an example, let us process the first query of the global execution plan of
Omar Boucelma, Mehdi Essid, and Yassine Lassoued
Let us consider, for instance, a basic query Q e and its binding B = {M i , i ∈
1 . . . n} where n is the number of sources that support the feature queried by Q e and
M i , i ∈ 1 . . . n, are their respective mappings. To extract the maximum of information from the local sources, first we rewrite Q e with a given mapping of the binding,
then we try to look for the unsupported attributes (if they exist) using the other mappings of the binding. To do this we use the notion of prefix query and suffix query.
Given a mapping M i of a source S i , a prefix query Q p is a subquery of Q e that
consists in extracting only the attributes supported by S i . Note that M i provides a
full-binding for query Q p . The suffix query Q s is the subquery consisting in extracting the remaining attributes (plus the key’s attributes).
Given these definitions, for each mapping M i ∈ B, Q e is processed as follows:
1. compute Q p and Q s of the query Q e and the mapping M i ;
2. let B s = {M j , M j ∈ B, j i};
3. let B i = {M i };
4. the execution plan of query Q e using the binding B i is the join between Q p and
the execution plan of Q s using the binding B s .
Since queries that are responsible for extracting feature information are executed
by the WFS servers, they are reformulated, using the mapping rules, into queries
that are expressed in terms of local schemas (each feature is replaced by the corresponding feature, each attribute is replaced by the corresponding attribute, and
the conditions of the rule (cf. Sect. 7.4) are added to the set of conditions of the
query). This reformulation generates a problem because the answer to this query
(the answer of the WFS) is written in terms of the local schema. To alleviate this
problem, an additional GQuery query is added to perform the inverse transformation. Queries query03 and query04 illustrated in Fig. 7.11 are examples of such
queries.
Let us now discuss constraints of the prefix and the suffix queries. It is easy to
see that the prefix query contains only the subset of conditions over attributes of
the prefix query. However, the suffix query contains the subset of conditions over
attributes of the suffix query extended by the set of conditions of the prefix query.
This extended set is used to refine the prefix query in adding more conditions. This
allows us to minimize the number of extracted tuples, hence minimizing the execution time. Finally, a condition that is not supported by a data source is added to the
GQuery expression, which is responsible for the transformation of the result: this is
the case where the source contains the attributes on which the condition is made but
the capabilities of the source cannot support it.
Figure 7.10 illustrates the rewriting algorithm which, given an elementary query
Q e and its binding B, computes the execution plan expressed in terms of the local
sources. As we may notice, B s is defined as {M j ∈ B, j > i} and not as {M j ∈
B, j i} as mentioned in the beginning of this section. We made this change in order
to eliminate duplicated answers. In fact, the subset of mappings {M k ∈ B, k < i} has
already been treated in the previous step; hence it is useless to compute it again.
To compute the final execution plan, we rewrite each elementary query of the
GEP. As an example, let us process the first query of the global execution plan of