Tuyêt-Trâm Dang-Ngoc

Virginie Sans

Dominique Laurent

Classifying XML Materialized Views for their Maintenance on Distributed Web Sources

Ces dernières années ont mis en évidence la croissance et la grande diversité des informations électroniques accessibles sur le web. C'est ainsi que des systèmes d'intégration de données tels que des médiateurs ont été conçus pour intégrer ces données distribuées et hétérogènes dans une vue uniforme. Pour faciliter l'intégration des données à travers différents systèmes, XML a été adopté comme format standard pour échanger des informations. XQuery est un langage d'interrogation pour XML qui s'est imposé pour les systèmes basés sur XML. Ainsi XQuery est employé sur des systèmes de médiation pour concevoir des vues définies sur plusieurs sources. Pour optimiser l'évaluation de requêtes, les vues sont matérialisées. La difficulté est de maintenir incrémentalement des vues matérialisées lors de la mise à jour des sources, car dans le contexte de sources web, très peu d'informations sont fournies par les sources. Les méthodes habituellement proposées ne peuvent pas être appliquées. Cet article étudie comment mettre à jour des vues matérialisées XML sur des sources web, au sein d'une architecture de médiation.

Introduction

In industry as well as in research, data information systems were often built separately. This results in highly heterogeneous and distributed systems, which generates fragmented views of data and information. In 1992, Wiederhold proposed a mediation architecture [START_REF] Wiederhold | Mediators in the Architecture of Future Information Systems[END_REF] for combining information from multiple data sources. The goal of a mediation architecture is to integrate the sources in order to present a uniform view to the final user or application. Generally speaking, a mediation architecture is composed of mediators and wrappers. A wrapper is associated to each source with the roles of extracting and transmitting information from the sources to the integrator. Before transmission, the data are transformed into a predefined format used by the mediator. The mediator integrates information provided by the wrappers and presents a queryable uniform view to the user application.

To facilitate the integration of data across different systems, XML has been adopted as the standard format for information exchange and XQuery, a standard query language for querying XML, has become a major requirement for XML-based systems. Recently, mediation architectures based on XML and XQuery have been proposed and implemented (Dang-Ngoc and Gardarin 2003) [START_REF] Draper | The Nimble Integration Engine[END_REF]. We also note that previous works as [START_REF] Gupta | XML-based information mediation with MIX[END_REF]) use other formats for representing semistructured data (eg. OEM) for querying these data (eg. Lorel, XML-QL) with a similar approach.

In such applications, the use of views is crucial. Indeed, similarly to the case of relational databases, an XML view can be seen as a collection defined by an XQuery request. XQuery is used to filter data and integrate them to present the different data sources as a single source to the user.

View materialization consists in processing the view in a local cache for better response delay during execution time. However, maintaining materialized views when the source data are updated is not an easy task in general. This problem has been studied in [START_REF] Laurent | Monotonic Complements for Independant Data Warehouses[END_REF] for data warehouses. In the context of XML views, the additional following points have to be taken into account: (a) In a distributed environment information exchanges must be optimized. (b) In a web context, the sources are autonomous and thus do not notify their changes, and do not provide internal properties (such as oids).

When a data source is modified, materialized XML views defined on this data source have to be updated accordingly in order to remain consistent. As noticed in [START_REF] Abiteboul | Incremental Maintenance for Materialized Views over Semistructured Data[END_REF] it is not reasonable to recompute the whole view at each source update, but it is better to use incremental techniques as [START_REF] Abiteboul | Incremental Maintenance for Materialized Views over Semistructured Data[END_REF][START_REF] El-Sayed | An Algebraic Approach for Incremental Maintenance of Materialized XQuery Views[END_REF]. [START_REF] Abiteboul | Incremental Maintenance for Materialized Views over Semistructured Data[END_REF] has proposed an incremental maintenance algorithm for materialized views for semi-structured data based on the data model OEM (different than XML) and the query langage LOREL. However, the query operations, the possible update operations and the update method form only a very limited subset of possible requests on semi-structured data. Moreover in this approach, the internal identifiers of the objects must be known to import the data in the materialized view, which is not conceivable in the case of autonomous sources. Recently in the RAINBOW project, [START_REF] El-Sayed | An Algebraic Approach for Incremental Maintenance of Materialized XQuery Views[END_REF] has proposed a method based on the decomposition of an XML source document update into basic primitive update operations (insert/delete/change of attribute or element) which apply to an identified position in the XML tree. However the assumption that the position of an update is known cannot apply to autonomous web sources, which do not provide this kind of information.

In this paper, we consider materialized views on web sources defined by an XQuery request on a mediator/wrapper architecture. We assume that the contents of the views are stored in a local XML database. This solution leads to two main questions: (1) what information is needed for updating the views ? and (2) how to process updates on the materialized views ?

In this paper, we answer these questions as follows: (1) we classify the different kinds of updates and propose a solution to maintain the materialized view, based on the notion of fragment, and (2) starting with the case of view defined by one operator, we study the general case of views defined by the combinaison of several operators. The rest of this paper is organized as follows. The next section focusses on update notification information and Section 3 describes the various update cases. We conclude in Section 4 by summarizing the contributions and discussing future research.

RNTI -1 2 Update Information

The interface between the mediator and the wrapper for querying sources with XQuery / XML (Dang-Ngoc and Gardarin 2003) has been extended to support materialized view maintenance. To this purpose, XML View registration and update notification from the wrapper have been incorporated in the wrapper functionnalities. The web wrapper loads web sources and keeps necessary information (essentially checksum and RDF) to check if sources have changed since last time it has been loaded, and send the necessary modification to the mediator.

Moreover, we assume, in this section and in Sections 3.1 and 3.2 that the view is defined by one operation: projection, restriction, cartesian product or join. The general case of a view definition involving several operators is outlined in Section 3.3. We refer to (Dang-Ngoc et al. 2004a) for more details.

Update Information

To know the information needed to update the view, we consider the parameters that charaterize the view computation and the source update. To do so, we first introduce the notions of collections and fragments.

Collections and fragments

An XML collection is a set of XML documents representing the same entity. In other words, a collection is a set of objects having a similar structure. For example, a collection of libraries should only have library objects. With semi-structured data, the structures of two objects in a collection can be equal or not (e.g an author object can be composed of a firstname only, whereas another is composed of a lastname, and a firstname).

An XML fragment is an identified subtree of an XML tree. A collection can be either a full web site where each page is a document relative to the collection, or a single page, where each XML fragment at the same level represents an object of this collection.

By analysing the XQuery request that defines the view, we can deduce the paths in the data source used by the request. We call this path set S the useful XML fragment. This fragment is a subtree of the tree collection of the source.

For example, let us apply the following XQuery request applied on the XML document of Figure 1 (b).

FOR $i in ("libraries.xml")/library/authors/ WHERE $i/author/year=1973 RETURN <result> {$i/author/firstname} {$i/author/books/book/title} </result>

To determinate the place of the fragment as precisely as possible and to minimize the necessary information for updates, we calculate what we call the maximal prefix. The maximal prefix is the longuest prefix common to the paths of the set S. Then, the minimal fragment template is created by using only the useful paths and is annotated as in (Chen et optional paths (resp. in solid and dotted links in Figure 1 (a)). In the previous XQuery example, all the paths used by the request have the path library/authors in common, and thus, this path is the maximal prefix.

Necessary information

The necessary update information provided by the wrappers to notify an update to the materialized view is: (i) the XML minimal fragment (before and after update), (ii) the position of the fragment in the collection and the triple (datatype, update, operation). where type is the datatype concerned by the source update (collection, fragment), update the type of source update (insertion, deletion, modification), and operation the operation defining the view (projection, restriction, cartesian product and join, see Section 3.3 for the general case).

Moreover, an analysis of the operators appearing in the view definition has enabled us to build a classification (see next section) of the different maintenance cases and has also allowed us to characterize the additional information necessary for the view maintenance. As we shall see in the next section, this information can be computed, either from the view itself or from the source.

Update Process

Having characterized the necessary information provided by the wrappers, we give an overview of the way views are maintained. The process to maintain the view can now be decomposed into two or three steps as follows:

1. Update detection and notification / Analysis of the triple: When an update on the source has been detected by the wrapper, the view materializer is notified about the update. The only information given at that time is the triple (datatype, update, operation). Based on this triple, it is possible to determine which additional information is needed in order to maintain the view.

2. Additional information (optional): a request builder queries the source or the view itself about the eventual additional information needed to maintain the views. We note that in the context of web sources, it is important to minimize the access to the sources. Thus, when the additional information is present in the view, we do not query the sources.

RNTI -1 3. Build the view update request / update the view: At this stage of the process, we know the triple, and the information necessary for processing the update.

Based on our analysis of each case, the view update request can be generated and processed.

In the architecture, we propose the following components for the processing of updates: A request analyzer, in order to know which operator (or sequence of operators) is used in the view definition. The other component is a request builder, in order to query the source or the view (when needed), and to compute the XQuery update request that is stored and processed according to a specified policy (see end of Section 2.1).

Update Classification

We present our method of view maintainance, using an example. To do so, we first recall from (Dang-Ngoc and Gardarin 2003) the notions of XRelation and XTuple.

XRelation

(Dang-Ngoc and Gardarin 2003) presents the physical algebra XAlgebra based on the relational operators designed for XML. These operators are called XOperators. This algebra aims to construct execution plans for the evaluation of XQuery and processes tuples (called XTuples) of tree structures. In an XRelation, domains are XML trees of given path sets, attributes (called XAttribute) are XPaths referencing nodes in the XML trees. Each XAttribute can be multi-valued (when referencing several sub-trees), or empty (when referencing no subtree). XRelations are ordered collections of XTuples, where each XTuple is composed of XPath named attributes, whose values reference subtrees in the collection of trees. As a result, the schema of an XRelation is of type R(XP ath+, [P ath+]), where XP ath's are the attributes and P ath's compose the path set of the XML trees. Figure 2 shows an XRelation and two of its XTuples. We note that the second attribute is multivaluated in the first XTuple, whereas this attribute is empty in the second XTuple.

RNTI -1

For the sake of lisibility, we simply write XTuples as ordered sets of values sets, ignoring references. It is important to note that this simplification implies that we consider the values in the leaves of trees. We refer to (Dang-Ngoc et al. 2004a) for the general case, including internal nodes. Let R be an XRelation defined by an expression of the XAlgebra on sources. Now, we introduce XTuple Identifiers (XTID). An XTID is a pair (source num, XTuple num). Each XTuple from the sources involved in the construction of one XTuple of R is associated with a distinct XTID (XTuple num are generated incrementally). This XTID is associated to each XAttribute of the XTuple so that all its XAttributes have the same XTID. Once this XTID is fixed for each XAttribute of each XTuple, it cannot be changed in any operation applied to the XRelation. Duplicate XTuples have distinct XTID.

Referring to the XRelation in Figure 2 RNTI -1

Classification

We study all update cases introduced in Section 2.1.1. More precisely, we consider the following cases: for the type of element to modify: (i) a whole XML fragment, (ii) a part of an existing single element, (iii) a multivalued element, and (iv) a non-existing element. The update types we consider are insertion, deletion and modification ( even though a modification can be seen as a deletion followed by an insertion). Finally, every elementary view operation is studied separately.

Identifying an XTuple

The method for identifying an XTuple, even after a succession of XOperations having combined columns, deleted or duplicated XTuples is the following: (a) from the succession of XOperations, we can deduce the initial range of each column, (b) from the XTID, we can know to which initial XTuple an XAttribute belongs. Finally, we can identify the original XTuple in spite of the mix implied by the XOperators. Note that by extending this method, we could also deduce which part of each original source has been used in the views.

Insertion of a fragment

Suppose a new fragment F represented by the new XTuple N is added in source S 1 . An XTID is computed for the new XTuple and is added to every XAttribute of the Xtuple.

Projection Cartesian product: In this case, all XTuples N M for all XTuples M in S 2 have to be inserted into the view. To create these XTuples, we identify XTuples belonging to S 2 in the view itself, using the XTIDs.

RNTI -1

For example, the insertion of ({T homas} 15 , {} 15 , {5678} 15 , {London} 15 ) into S 1 gives the following XRelation C 2 . To compute C 2 , we have considered an XTuple in the S 1 part with XTID 11 and selected all XTuples where 11 appears in. The columns associated to S 2 of these XTuples constitute the content of S 2 .

C

Deletion of a fragment

Suppose a fragment F is deleted from source S 1 , and that F is represented by the XTuple N with XTID a. Then to maintain the view, all XTuples such that at least one of their XAttribute has this XTID, are deleted from the XRelation. For example, let us consider the deletion from S 1 of the fragment F = ({John}, {red, green}, {4242}, {Roma}). First, we identify all XTuples in the view matching the fragment, i.e., the two XTuples with XTIDs 11 and 13. Considering one of these XTIDs, for example 11, we remove all XTuples in the view having XTID 11 in their XAttributes. The resulting XRelations of this deletion for each XOperation considered in this example, are shown below.

• P 3 : the resulting state of P 1 after deleting F from S 1

P 3 pers/name pers/car/col pers/num {M ickael}12 {}12 {3710}12 {John}13 {red, green}13 {4242}13 {M ary}14 {}14 {3710}14
• R 3 : the resulting state of R 1 after deleting F from S 1 R 3 pers/name pers/car/col pers/num pers/city {John}13 {red, green}13 {4242}13 {Roma}13

RNTI -1 We note that modifications of fragments are treated by deletions followed by insertions.

Inserting, Deleting and Modifying an Element

Insertion: We consider the case of inserting a node (which can be the root of a whole subtree) N in an existing fragment F of the source S 1 used by the XTuple N with XTID a. In this case, we just have to add the new node in the set of nodes of the XAttributes identified by the XTID a. Note that prefix/suffix must be considered, because, all XAttributes referencing the path must be updated. For example, in S 1 , consider the insertion of element color blue in the fragment, for which the minimal fragment after projection gives:

({John}, {red, green}, {4242}, {Roma})

. By identifying a matching XTuple (see Section 3.2.1), we see that the insertion affects the XTuples in the view P 1 having XTIDs 11 and 13. As these Xtuples are equal in the view, we take one of them, for example the one having XTID 11, and we add the value blue in the set ({red, green} 11 ). We obtain the following XRelation. We note that in the case of elements, modifications are treated by identifying the element in the value set and replacing it by the new value.

Deletion: We consider the deletion of a node (which can be the root of a subtree) N from an existing fragment F of the source S 1 used by the XTuple N with XTID a. In this case, we have to delete the node from the set of nodes of the XAttributes identified by the XTID a in the right column. If the node is alone in the set in a column used as a predicate in the XOperation, all final XTuples having an XAttribute with XTID a must be removed. Note that, here again, prefix/suffix must be considered, because all XAttributes referencing the path must be updated.

For example, in S 1 , we consider the deletion of element color green in one occurence of the fragment ({John},{red,green},{4242},{Roma})

Combination of XOperators

In this section, we outline the case where the view is defined by a combination of XOperators. In order to maintain it when sources change, we must introduce the notion of hidden columns. A column is marked hidden when a projection eliminates it, while it is used in a predicate in XOperators (as restriction, or join). Notice that if a hidden column does not appear in the client application using the view, then this column is manipulated as all other columns when maintaining the view.

Figure 3 (a) shows a detailed example of an XAlgebra tree representing a view defined on two sources S 1 and S 2 mapped to the XRelations R 1 and R 2 respectively. For the sake of lisibility, only the P part of XRelations has been represented, but Figure 3 (b) and Figure 3 (c) show how the second (resp. third) XTuple of S 1 (resp. S 2 ) is really represented. Figure 3 (d) shows the second XTuple of the final XRelation. Every lower case letter represents a distinct set of values references, and numbers on the right side are XTIDs. Upper case letters represent names of columns (i.e., paths expressions). Note that in this example, we have duplicate rows (2 nd and 3 rd on R 1 ) and multivaluated nodes (g 12 ). During XOperations (restriction, join, projection), columns and rows are combined, deleted or created, but it is alway possible to compute the useful columns. In our example, in the final XRelation R F , we can reconstruct the useful part of the third initial XTuples. Finally, hidden columns can appear after projection. They are represented in grey on the figure.

In (Dang-Ngoc et al. 2004a), we describe how to support combinations of XOperations in the view definition based on the final view, and the simple operations in the view definition. To do so, we replace in the triple as defined in Section 2.1.1, operation by request where request is the XML request.

In our example, suppose we insert a new fragment in the source S 1 represented by the XTuple (a 16 , y 16 , g 16 , h 16 ). Applying the projection on B, C, D gives (y 16 , g 16 , h 16 ). Then applying the join means that from the final XRelation, we are able to rebuild the M, N columns of XTuples where N = h. For example, we select the M and N columns of XTuples with XTID 12, and we get the pairs (h 23 , u 23 ) and (h 24 , w 24 ) that are combined with (y 16 , g 16 , h 16 ). So finally, the XTuples to be added to the final view are (y 16 , g 16 , h 16,23 , u 23 ) and (y 16 , g 16 , h 16,24 , w 24 ). (See insertion in Figure 3 (a)).

RNTI -1

Conclusions and Future Works

Integrating web information has become an urgent need, and taking into account the specificities of web information is a challenge. Indeed, web sources are semi-structured, the sources can be unreachable and they frequently change but do not provide any information about their changes.

In this paper, we have proposed a solution for integrating web sources into a mediation architecture based on materialized view. Update information are sent to the mediator as an XML minimal fragment. Then we have given a classification of all cases of maintenance of materialized views by considering the update type, the datatype concerned by the update and the operations defining the view.

We are currently implementing our approach through a module called XML View Refresher to be integrated in the full XML mediation architecture XLive.

In this paper, we have considered materialized views whose definitions do not incorporate any reconstruction phase. However this feature is commonly used in XQuery requests in order to output the resulting data according to a format specified in this phase. As this point is important for view definition, we are currently studying the impact of the reconstruction phase in our approach.

Figure 1 :

 1 Figure 1: Useful fragment of an XQuery request

  Figure 2: XTuple.

Figure 3 :

 3 Figure 3: An execution plan with XRelations and XTID.

  , the two XTuples are written as: ({John} 11 , {red, green} 11 , {4242} 11 , {Roma} 11 ) and ({M ary} 15 , {} 15 , {3710} 15 , {Berlin} 15 ).Below are examples of XRelations computed from two sources S 1 and S 2 . : Cartesian product of S 1 and S 2 (in the resulting XRelation of a join or of a cartesian product, an XAttribute can be associated with more than one XTID).

		pers/name	pers/car/col	pers/num pers/city
	S 1	{John}11 {M ickael}12 {}12 {red, green}11 {4242}11 {3710}12	{Roma}11 {London}12	S 2	sal/num sal/stat {3710}21 {baker}21
		{John}13	{red, green}13 {4242}13	{Roma}13	{9999}22 {grocer}22
		{M ary}14	{}14		{3710}14	{Berlin}14
			pers/name	pers/car/col	pers/num
		P 1	{John}11 {M ickael}12 {}12 {red, green}11 {4242}11 {3710}12
			{John}13	{red, green}13 {4242}13
			{M ary}14	{}14	{3710}14
		• R 1 : Restriction of S 1 on pers/num > 4000
		R 1	pers/name pers/car/col {John}11 {red, green}11 {4242}11 pers/num pers/city {Roma}11
			{John}13	{red, green}13 {4242}13	{Roma}13
		J 1	pers/name {M ickael}12 {}12 pers/car/col pers/num, sal/num pers/city {3710}12,31 {London}12 {baker}21 sal/stat
			{M ary}14	{}14	{3710}14,31	{Berlin}14	{baker}21
		pers/name {John}11 {M ickael}12 {}12 pers/car/col {red, green}11 {4242}11 pers/num pers/city {Roma}11 {3710}12 {London}12 {3710}21 {baker}21 sal/num sal/stat {3710}21 {baker}21 {John}13 {red, green}13 {4242}13 {Roma}13 {3710}21 {baker}21 • C 1 C 1 {M ary}14 {}14 {3710}14 {Berlin}14 {3710}21 {baker}21
		{John}11	{red, green}11 {4242}11	{Roma}11	{9999}22 {grocer}22
		{M ickael}12 {}12	{3710}12	{London}12 {9999}22 {grocer}22
		{John}13	{red, green}13 {4242}13	{Roma}13	{9999}22 {grocer}22
		{M ary}14	{}14	{3710}14	{Berlin}14	{9999}22 {grocer}22

• P 1 : Projection of S 1 on pers/name, pers/car/col, pers/num.

• J 1 : Join of S 1 and S 2 on per/num and sal/num.

:

  Unprojected columns of the new XTuple are removed and the new XTuple is added to the result XRelation.For example: the insertion of ({T homas} 15 , {} 15 , {5678} 15 , {London} 15 ) into S 1 gives the following XRelation P 2 . The XTuple is added to the resulting XRelation if the predicate is satisfied.For example, insertion of ({P eter} 16 , {} 16 , {1234} 16 , {Roma} 16 ) does not change R 1 , and the insertion of ({T homas} 15 , {} 15 , {5678} 15 , {London} 15 ) into S 1 gives the following XRelation R 2 .

		pers/name	pers/car/col	pers/num
		{John}11	{red, green}11 {4242}11
	P 2	{M ickael}12 {}12 {John}13 {red, green}14 {4242}13 {3710}12
		{M ary}14	{}14	{3710}14
		{T homas}15 {}15	{5678}15
	pers/name {John}11 Restriction: R 2 {John}13	pers/car/col {red, green}11 {4242}11 pers/num pers/city {Roma}11 {red, green}13 {4242}13 {Roma}13
		{T homas}15 {}15	{5678}15	{London}15

  We first compute from the view, the set of all XTuples from S 2 that must be joined with N . We distinguish two cases: (1) If the resulting set is not empty, the new XTuples are created as in the cartesian product. (2) Otherwise, loading S 2 is necessary to compute the join with N .For example, the insertions of ({Helen} 15 , {} 15 , {3710} 15 , {London} 15 ) (case (1)), and of ({Steve} 16 , {} 16 , {9999} 16 , {London} 16 ) (case (2)) into S 1 gives the following XRelation J 2 . Moreover, the insertion of ({Bill} 17 , {} 17 , {8888} 17 , {Roma} 17 ) does not change J 2 . Note that S 2 has to be loaded to reach this conclusion.

		pers/name	pers/car/col	pers/num pers/city	sal/num sal/stat
		{John}11	{red, green}11 {4242}11	{Roma}11	{3710}21 {baker}21
		{M ickael}12 {}12	{3710}12	{London}12 {3710}21 {baker}21
		{John}13	{red, green}13 {4242}13	{Roma}13	{3710}21 {baker}21
		{M ary}14	{}14	{3710}14	{Berlin}14	{3710}21 {baker}21
	2	{John}11	{red, green}11 {4242}11	{Roma}11	{9999}22 {grocer}22
		{M ickael}12 {}12	{3710}12	{London}12 {9999}22 {grocer}22
		{John}13	{red, green}13 {4242}13	{Roma}13	{9999}22 {grocer}22
		{M ary}14	{}14	{3710}14	{Berlin}14	{9999}22 {grocer}22
		{T homas}15 {}15	{5678}15	{London}15 {3710}21 {baker}21
		{T homas}15 {}15	{5678}15	{London}15 {9999}22 {grocer}22
	Join: J 2	pers/name {M ickael}12 {}12 pers/car/col pers/num, sal/num pers/city {3710}12,31 {London}12 {baker}21 sal/stat {M ary}14 {}14 {3710}14,31 {Berlin}14 {baker}21
			{Helen}15	{}15	{3710}15,31	{London}15 {baker}21
			{Steve}16	{}16	{9999}16,32	{London}16 {grocer}22

  • C 3 : the resulting state of C 1 after deleting F from S 1

		pers/name	pers/car/col	pers/num pers/city	sal/num sal/stat
		{M ickael}12 {}12	{3710}12	{London}12 {3710}21 {baker}21
	C 3	{John}13 {M ary}14	{red, green}13 {4242}13 {}14 {3710}14	{Roma}13 {Berlin}14	{3710}21 {baker}21 {3710}21 {baker}21
		{M ickael}12 {}12	{3710}12	{London}12 {9999}22 {grocer}22
		{John}13	{red, green}13 {4242}13	{Roma}13	{9999}22 {grocer}22
		{M ary}14	{}14	{3710}14	{Berlin}14	{9999}22 {grocer}22
	• J 3 : the resulting state of J 1 after deleting F from S 1
		J 3	pers/name {M ickael}12 {}12 pers/car/col pers/num, sal/num pers/city {3710}12,31 {London}12 {baker}21 sal/stat

  . In C 1 , this deletion affects one of the XTuples having XTID 11 or 13. If we choose 11, then we delete the element RNTI -1 color green in each Xtuple where the element color has the XTID 11, and get the following XRelation C 4 .

		pers/name	pers/car/col	pers/num pers/city	sal/num sal/stat
		{John}11	{red}11	{4242}11	{Roma}11	{3710}21 {baker}21
		{M ickael}12 {}12	{3710}12	{London}12 {3710}21 {baker}21
	C 4	{John}13 {M ary}14	{red, green}13 {4242}13 {}14 {3710}14	{Roma}13 {Berlin}14	{3710}21 {baker}21 {3710}21 {baker}21
		{John}11	{red}11	{4242}11	{Roma}11	{9999}22 {grocer}22
		{M ickael}12 {}12	{3710}12	{London}12 {9999}22 {grocer}22
		{John}13	{red, green}13 {4242}13	{Roma}13	{9999}22 {grocer}22
		{M ary}14	{}14	{3710}14	{Berlin}14	{9999}22 {grocer}22

Summary

In the last years, with the growing and diversity of information in electronic form accessible from the Web, data integration systems -such as mediators-were designed to integrate these distributed and heterogeneous data in a uniform view. To facilitate the integration of data across different systems, XML has been adopted as the standard format for information exchange. XQuery, a powerful language for querying XML, has become a major requirement for XML-based systems, and is used in mediation systems to design views on several data sources. To optimize query evaluation, views are materialized. The difficulty is to maintain incrementally materialized views while sources are updated. In the context of web sources, very few informations are provided by sources, and methods usually proposed do not apply in this context. This paper studies how to update materialized XML views on web sources in the context of a mediation architecture.

RNTI -1


Tuyet-Tram Dang-Ngoc -Georges Gardarin
email: georges.gardarin@prism.uvsq.fr

Architecture de médiation « Tout-XML » Conception et évaluation

Keywords: MOTS-CLÉS : XML, architecture de médiation, algèbre XML, XQuery XML, Mediation Architecture, XML Algebra, Xquery

XML s'est imposé comme le méta-langage permettant de représenter et d'échanger des données non seulement sur le web mais aussi de façon générale en entreprise. XQuery s'impose comme le langage de requête standard pour XML. En conséquence, des outils sont nécessaires pour interroger des sources de données hétérogènes avec XQuery, et ainsi intégrer des données hétérogènes en temps réel sur demande. Cet article présente le médiateur XMedia, un outil permettant d'intégrer et d'interroger des informations hétérogènes distribuées sous la forme de vues XML unifiées. Il décrit l'architecture du médiateur et se concentre sur la technique d'analyse de requêtes distribuées qui a été implémentée dans ce composant. L'évaluation de requête est basée sur une algèbre XML étendant simplement les opérateurs classiques de l'algèbre relationnelle à des traitements de tuples d'éléments arborescents. De plus, nous présentons un ensemble d'évaluation de performances sur un banc d'essai de type relationnel distribué, ce qui conduit à discuter d'éventuelles futures optimisations.

ABSTRACT. XML has emerged as the leading language for representing and exchanging data not only on the Web, but also in general in the enterprise. XQuery is emerging as the standard query language for XML. Thus, tools are required to mediate between XML queries and heterogeneous data sources to integrate data in XML. This paper presents the XMedia mediator, a unique tool for integrating and querying disparate heterogeneous information as unified XML views. It describes the mediator architecture and focuses on the unique distributed query processing technology implemented in this component. Query evaluation is based on an original XML algebra simply extending classical operators to process tuples of tree elements. Further, we present a set of performance evaluation on a relational benchmark, which leads to discuss possible performance enhancements.

Introduction

Ces dernières années ont vu apparaître beaucoup de projets de recherche basés sur l'intégration d'informations hétérogènes. Les systèmes typiques d'intégration d'information ont adopté une architecture médiateur-adaptateurs [START_REF] Wiederhold | Intelligent Integration of Information[END_REF]. Dans cette architecture, les médiateurs fournissent une interface utilisateur uniforme pour interroger des vues intégrées de sources d'informations hétérogènes. Les adaptateurs fournissent des vues locales des sources de données dans un modèle global de données. Les vues locales peuvent être interrogées d'une manière limitée selon les possibilités des adaptateurs. Bien que l'approche local-as-view (LAV) ait été considérée dans quelques systèmes [START_REF] Levy | Querying Heterogeneous Information Sources Using Source Descriptions[END_REF] [START_REF] Manolescu | Answering XML Queries over Heterogeneous Data Sources[END_REF], la plupart des systèmes suivent l'approche global-as-view (GAV), dans lesquelles les vues intégrées sont conçues en termes de vues locales des sources. Les projets de recherche et les prototypes les plus connus basés sur cette architecture incluent GARLIC [START_REF] Haas | Optimizing Queries across Diverse Data Sources[END_REF], TSIMMIS [START_REF] Chawathe | The TSIMMIS Project : Integration of Heterogeneous Information Sources[END_REF], IRO-DB [START_REF] Fankhauser | Experiences in Federated Databases: From IRO-DB to MIRO-Web[END_REF] et YaT [START_REF] Cluet | Your Mediators Need Data Conversion[END_REF].

Alors que dans les années 90 la plupart des études étaient basées sur le modèle objet comme modèle d'intégration de données, la recherche s'est concentré sur XML en tant que modèle global au début de ce nouveau siècle. Les avantages de XML comme modèle d 'échange, (c.-à-d., riche, clair, extensible et sûr), le placent comme le meilleur candidat pour supporter les modèles de données intégrées. En outre, employer des vues XML pour des sources de données locales permet d'occulter les spécificités locales de chaque système. De plus, la richesse du modèle de schéma XML (XML-Schema) simplifie le travail des adaptateurs. Enfin, l'apparition de XQuery comme puissant langage d'interrogation universel pour XML permet d'interroger des vues globales et locales XML d'une manière uniforme basée sur une interface standard. Ainsi, tous ces avantages expliquent que plusieurs projets de recherche ont émergé pour interroger des sources des données hétérogènes d'une manière uniforme en se basant sur le modèle d'échange XML, par exemple (Christophides et al., 2000), [START_REF] Manolescu | Answering XML Queries over Heterogeneous Data Sources[END_REF] et [START_REF] Shanmugasundaram | Querying XML Views of Relational Data[END_REF].

XMedia est l'un des premiers systèmes basés sur XML permettant d'intégrer des sources de données hétérogènes. Une première version a été développée à l'Université de Versailles (laboratoire PRiSM) puis industrialisée par la start-up e-XMLMedia (voir http://www.e-xmlmedia.fr/). Le système est actuellement disponible en logiciel libre (open source). Ce médiateur et les adaptateurs associés fournissent les fonctionnalités nécessaires pour interroger des sources de données hétérogènes de manière uniforme avec XML et XQuery. C'est un composant complexe composé de plusieurs paquetages responsables: 1-des fonctionnalités de décomposition de requêtes en des sous-requêtes mono-sources; 2-de la transmission efficace des sous-requêtes locales aux sources de données; 3-de la récupération des résultats en XML depuis une interface SAX; 4-du traitement et de l'intégration des flots; et enfin 5-de l'assemblage des résultats. Les requêtes comme les sous-requêtes sont exprimées en XQuery. En outre, des descriptions de capacités de traitement sont associées aux adaptateurs de sorte que le médiateur ne puisse envoyer que des requêtes supportées aux adaptateurs. En résumé, le médiateur utilise XML pour représenter des données disparates dans un format commun et pour créer une vue unifiée de ces données. En utilisant la technologie de traitement de requêtes distribuées, le médiateur fournit aux applications les services requis pour intégrer des informations hétérogènes sur demande via des requêtes.

Cet article décrit une version du médiateur appelé XMedia. Cette version diffère de la version industrielle par certains côtés. Elle est basée notamment sur une nouvelle algèbre pour le traitement de XML appelée XAlgebra. Les contributions de cet article sont triples. Tout d'abord nous décrivons l'architecture système modulaire du médiateur XMedia. En second lieu, nous décrivons l'algorithme de traitement de requêtes, qui est basé sur des transformations de requêtes et une algèbre fonctionnant sur des tuples d'arbres XML. Un résultat important est que le médiateur est capable de traiter la plupart des requêtes sous forme de flux d'évènements XML. Troisièmement, nous utilisons un banc d'essai sur notre architecture montrant les faiblesses et les forces des composants principaux du système. Cela nous mène à de nouvelles idées pour l'optimisation de requêtes. Certaines d'entre elles devraient être intégrées dans une future version de XMedia.

Le reste de cet article est organisé comme suit. La section suivante se concentre sur les objectifs et l'architecture du médiateur. La section 3 décrit l'algèbre proposée (XAlgebra), une extension simple de l'algèbre relationnelle pour traiter des forêts d'arbres XML. Puis, nous donnons une vue d'ensemble de la technologie de transformation de requêtes incluse dans le médiateur XMedia à l'aide d'un exemple de requête. La section 5 présente des mesures de performance basées sur le banc d'essai TPC/R adapté à XML. Dans la section 6, nous discutons des extensions possibles du moteur d'exécution de requêtes. Nous concluons en récapitulant les contributions et en discutant de développements futurs possibles.

Vue d'ensemble et architecture

Intégration et interrogation de vues XML

Le médiateur XMedia est un middleware d'intégration de données gérant des vues XML de sources de données hétérogènes. Il suit l'approche global-as-view (GAV). Des vues globales sont définies par les administrateurs à l'aide de requêtes intégrant les collections locales de documents XML. Elles sont interrogées par les utilisateurs par une API Java étendant JDBC à XQuery, appelée XML/DBC. Les sources de données peuvent être de divers types : des bases de données relationnelles, des fichiers XML, des bases de données XML, des applications propriétaires, etc. Des adaptateurs spécifiques donnant les métadonnées par introspection et fournissant au moins un sous-ensemble de XQuery sur les collections exportées les encapsulent. Idéalement, un adaptateur peut supporter la définition de vues XML interrogeables en XQuery permettant de réaliser les transformations des données de la source en données XML conformes au modèle exporté.

Le médiateur respecte et s'appuie sur les normes XML, y compris XML Schéma, XQuery, les interfaces DOM et SAX. Les "XML Schemas" sont intensivement employés pour la représentation de métadonnées. En particulier, ils décrivent les sources et les vues de données situées sur n'importe quelle couche. Le typage d'une requête XQuery est vérifié à l'aide des schémas. Nous supportons actuellement la plupart des cas d'utilisation de XQuery. Nous traitons XML de façon interne sous forme de flux d'événement SAX pour des raisons d'efficacité. En effet, DOM est en général trop coûteux pour instancier des documents XML pendant le traitement. Cependant, l'utilisateur peut s'il y a lieu obtenir des arbres DOM comme résultat et nous employons parfois DOM à l'intérieur du médiateur pour conserver des documents XML pour des traitements futurs.

Les requêtes sont décomposées en sous-requêtes optimale mono-sources ainsi qu'en plans globaux de requêtes exprimés en algèbre spécifique (XAlgebra), étendant l'algèbre relationnelle pour traiter des arbres. Les requêtes sont optimisées d'une manière simple mais efficace. Des heuristiques simples sont supportées dans la version courante, mais une optimisation basée sur une estimation de coût des plans pourrait être introduite dans une version future. L'heuristique inclut l'adaptation à XML de la remontée classique en relationnel des sélections et des transformations de semi-jointure en sélections. Plusieurs algorithmes sont mis en application pour exécuter les opérateurs de la XAlgebra, le choix étant pour l'instant dicté par l'utilisateur au moyen d'indications ajoutées aux requêtes (hints).

Pour identifier les sources appropriées pour une requête et la décomposer, des métadonnées décrivant les sources sont gérées. Lorsqu'un nouvel adaptateur est enregistré sur un médiateur, les métadonnées décrivant la source sont envoyées au médiateur sous la forme d'un fichier de configuration. Ce fichier contient un document XML spécifiant le schéma pour chaque collection exposée par l'adaptateur de source. Si le schéma d'une collection n'est pas connu, un schéma par défaut est produit. Ce schéma décrit l'ensemble des chemins de la collection, c'est une forme de guide de données (dataguide). Les schémas de métadonnées sont maintenus dans la mémoire du médiateur et classés par source, espace de noms, collection et chemin pour un accès rapide lors du traitement des requêtes.

Une architecture récursive traitant des flux de données

L'architecture de médiateur est représentée figure 1. L'API XML/DBC est la seule interface avec les composants externes. On note ainsi que le médiateur envoie les requêtes aux adaptateurs via XML/DBC et obtient les résultats par XML/DBC. Ceci permet à un médiateur de voir un autre médiateur comme un adaptateur. Les résultats sont fournis via XML/DBC par l'intermédiaire de lecteurs SAX. Ainsi, des flux d'événements sont transférés entre les médiateurs et les adaptateurs, évitant les surcoûts produits par l'allocation de structures mémoire intermédiaires. L'architecture récursive traitant les flux de données est intéressante pour les applications qui peuvent effectuer l'intégration de données à de multiples étapes de leur exécution sans trop de dégradation de performance.

Les sous-composants principaux sont : l'analyseur XQuery, le gestionnaire de métadonnées, l'évaluateur de requête, le décomposeur de requête, et le reconstructeur de résultat. Tous ces composants sont brièvement décrits ci-dessous.

Décomposeur (Decomposer)

Le décomposeur décompose chaque requête simple en des requêtes atomiques, c.-à-d., des requêtes impliquant une seule collection globale. Il produit également un arbre de jointure (qui peut être vide) pour maintenir la dépendance entre les requêtes atomiques. Des opérateurs d'imbrication et de désimbrication peuvent également être produits pour restructurer des résultats intermédiaires. Le décomposeur identifie les métadonnées des sources de données appropriées et localise les collections. Basé sur ces informations, il traduit les requêtes atomiques sur une collection globale en une union de requêtes sur des collections locales. En particulier, il traduit les chemins globaux avec des expressions régulières dans des chemins locaux remplaçant les jokers par les chemins possibles extraits des métadonnées. En d'autres termes, il crée un premier plan d'exécution pour la requête.

Optimiseur (Optimizer)

Le plan d'exécution se compose d'opérateurs de la XAlgebra. Le rôle de l'optimiseur est de le transformer pour obtenir le meilleur plan possible. Des optimisations simples du plan de requête sont mises en oeuvre dans la version actuelle du médiateur, mais des optimisations plus complexes basées sur un modèle de coût sont prévues. Par exemple, l'optimiseur groupe les opérateurs qui référencent la même source en une seule requête pour l'expédier en une fois. Il trie également les opérateurs globaux selon l'heuristique choisie et retient la meilleure méthode de traitement (parallèle, en séquence ou en pipeline) pour les opérateurs globaux. Il choisit également le meilleur algorithme disponible pour chaque opérateur de l'algèbre.

Exécuteur (Executor)

L'exécuteur est responsable de l'expédition des sous-requêtes aux adaptateurs en utilisant XML/DBC. En retour, il rassemble les résultats en mémoire cache. En général, les résultats ne sont pas instanciés entièrement dans la mémoire cache mais des événements SAX sont produits et sont directement traités par l'évaluateur si possible, notamment dans les cas simples (union de résultats). Nous représentons chaque collection d'arbre XML envoyé par un adaptateur comme un XTuple, c.-àd., un tuple contenant des références à la forêt d'arbres XML instanciée dans le cache.

Evaluateur (Evaluator)

En se basant sur le plan de requête, l'évaluateur évalue la requête globale restante et applique les opérateurs algébriques dans la mémoire principale. Les opérateurs de la XAlgebra peuvent effectuer les opérations basées sur XPath mais aussi les projections, restrictions, produits, jointures, imbrications, désimbrications, unions, intersections et différences de collections ordonnées de XTuples. Pour chaque opérateur, nous mettons en application un ou plusieurs algorithmes spécifiques. Par exemple, plusieurs algorithmes de jointures globales sont possibles. L'évaluateur peut travailler avec les collections intermédiaires entièrement stockées dans la mémoire principale, mais peut également travailler avec un flux d'évènements SAX, et de ce fait, implémenter l'évaluation en pipeline avec la jointure par hachage. Sont possibles également les algorithmes de jointures dépendantes demandant un XTuple à une source et interrogeant l'autre en se basant sur les résultats précédents.

Reconstructeur (Reconstructor)

Le reconstructeur applique l'opérateur de reconstruction aux résultats intermédiaires représentés comme des XTuples et produit la réponse à la requête. En d'autres termes, il imbrique et étiquette les données afin de construire le résultat final. Enfin il construit le flux d'événement SAX pour fournir les résultats à l'utilisateur.

Gestionnaire de métadonnées (metadata manager)

Ce composant contrôle les schémas de toutes les sources enregistrées. De plus, pour chaque source, il maintient les noms de collection avec l'ensemble associé des chemins interrogeables. L'ensemble des chemins constitue une sorte de dataguide donnant une vue d'ensemble de tous les chemins instanciés dans la source. Si un chemin est absent, la source ne sera pas interrogée. L'ensemble des chemins doit être fourni par l'adaptateur au médiateur lors de l'enregistrement de la source (sur commande getMetaData).

Algèbre physique

Comme décrit ci-dessus, les requêtes XQuery sont traduites dans une algèbre physique assez simple pour être susceptible d'être optimisée et exécutée. Plusieurs algèbres pour XML ont récemment été proposées [START_REF] Jagadish | TAX: A Tree Algebra for XML[END_REF], [START_REF] Fernandez | An Algebra for XML Query[END_REF], (Christophides et al., 2000), [START_REF] Galanis | Following the Paths of XML: an Algebraic Framework for XML Query Evaluation[END_REF]. Notre but est d'être aussi près que possible de l'algèbre relationnelle étendue [START_REF] Zaniolo | The Representation and Deductive Retrieval of Complex Objects[END_REF], tout en permettant la manipulation des arbres et des collections ordonnées d'arbres efficacement. Nous présentons maintenant notre modèle de données relationnel étendu et son algèbre associée pour traiter des collections XML.

Modèle de données

XAggregate

Comme avec l'algèbre relationnelle étendue, le but de l'agrégation est d'appliquer une fonction MIN, MAX COUNT, AVG ou SUM à une collection de valeurs. La collection est simplement indiquée par un attribut XPath de la XRelation. Excepté avec COUNT qui compte directement le nombre de références, les fonctions s'appliquent aux valeurs référées par les attributs, qui doivent être correctement typés (numériques avec les fonctions classiques). Les XAggregate sont des opérations bloquantes ne préservant pas l'ordre.

XReconstruct

La reconstruction est en général l'opération finale dans une expression algébrique pour éditer le flux final d'événements SAX comme résultat. Elle prend comme paramètres d'entrée une XRelation et un document XML dans lequel les valeurs sont remplacées par des attributs de la XRelation (c.-à-d., XPaths). Une instance de résultat par XTuple est alors produite. L'opération préserve l'ordre et est non bloquante. Cet opérateur est introduit lors de la canonisation des requêtes XQuery introduite ci-dessus.

XUnion, XDifference, XIntersection

Ce sont les opérateurs ensemblistes classiques appliqués à des ensembles d'XTuples.

Exemple de traitement d'une XQuery

Comme introduit dans la section architecture, la construction d'un plan d'exécution suit les étapes suivantes :

-Normalisation et canonisation.

-Atomisation et extraction des jointures.

-Identification des sources.

-Création du plan d'exécution.

-Optimisation du plan d'exécution.

Nous allons maintenant illustrer ces étapes avec un exemple simple. Pour nos expériences, nous avons adapté le banc d'essai TPC-R à un scénario approprié pour un système fédéré semi-structuré. Nous avons pour cela groupé quelques tables ensemble pour obtenir des données arborescentes. La figure 7 décrit le schéma et la distribution des données extraites à partir du banc d'essai TPC-R. Comme il n'y a pas de clause LET dans l'exemple, la requête est désimbriquée directement. En appliquant une règle similaire à celle définie dans [START_REF] Manolescu | Answering XML Queries over Heterogeneous Data Sources[END_REF], la requête est désimbriquée en sous-requêtes qui sont ensuite purgées de tout balisage de reconstruction. Nous les appelons requêtes élémentaires. Puis la requête de reconstruction est générée: il s'agit simplement du document XML à retourner avec des expressions XPath au lieu des constantes.

Requête canonisée

Requête élémentaire 1 let t1 ::= for $n in Collection("*")/nation where contains ($n/comment, "iron") L'arbre algébrique peut être optimisé en utilisant des règles traditionnelles de l'algèbre relationnelle imbriquée : exécution des restrictions au début, remontée des projections, ordonnancement des jointures, choix du meilleur algorithme pour chaque opérateur. Cette dernière optimisation exige des indications de l'utilisateur (hints) ou un modèle de coût. Nous discuterons de ce point dans la suite.

Mesures de performance

Pour comprendre où se trouvent les goulots d'étranglement du système et déterminer les optimisations qu'il serait utile d'étudier, nous avons expérimenté avec une version bêta du système industriel. Dans cette section, nous décrivons quelques résultats de nos expériences montrant les surcoûts induits par chaque composant de l'architecture.

Architecture d'évaluation

Nous avons utilisé une architecture client/serveur avec deux machines serveurs. Le processeur de la machine cliente est un Celeron 600 Mégahertz avec 64 Mo de RAM. Les machines serveurs sont toutes les deux des Pentium 4 à 1,6 Gigahertz avec 256 Mo de RAM. Le réseau est à 10 Mbits/seconde. Le système d'exploitation de ces trois machines est Linux. 2.4.

Pour comparer les diverses architectures, nous avons employé différents arrangements de médiateurs et d'adaptateurs, comme représenté sur la figure 9. M0, M1, M2, M3 et M4 sont des médiateurs. Ils sont tous lancés sur l'ordinateur client. A1, A2, A3 sont des adaptateurs sur les bases de données relationnelles. A4, A5, A6 sont des adaptateurs sur une base de données semi-structurée (c'est en effet le repository e-XML de e-XMLMedia). A7 est un adaptateur sur une base de données relationnelle qui contient exactement toutes les données d'A1, A2 et A3. M1 est relié aux médiateurs tandis que tous les autres sont reliés aux adaptateurs. Ceci est rendu possible car les médiateurs et les adaptateurs ont les mêmes interfaces.

Coût par étapes

Comme détaillé ci-dessus, le traitement d'une requête suit les étapes ci-dessous: Analyse de la requête qui transforme la requête XQuery sous format interne. Construction d'arbre algébrique qui normalise, canonise, et atomise la requête et construit finalement l'arbre algébrique. Initialisation de l'exécution établissant la connexion aux adaptateurs et obtenant le premier XTuple.

Exécution locale de la requête sur l'adaptateur comprenant l'envoi de la requête à l'adaptateur, l'obtention du résultat par XML/DBC dans le format SAX et la transformation du flux SAX en XTuple.

Exécution globale de la requête et reconstruction, c.-à-d., le traitement des XTuples par l'arbre algébrique pour renvoyer le résultat.

Les étapes 1, 2 et 3 composent la phase d'initialisation de traitement de requête.

Les temps passés pour la phase d'initialisation et pour les étapes 4, 5, et pour le traitement complet sont décrits dans la figure 11. L'étape d'initialisation est négligeable devant les autres temps. Le temps total est encore approximativement le double du temps pris par l'adaptateur. L'évaluation sur l'adaptateur se compose de :

-La transformation de la requête en SQL.

-L'exécution de la requête sur la base de données (Oracle).

-La récupération des tuples et la transformation en documents XML.

Comme les résultats sont mesurés sur une base de données à chaud, les tuples sont dans le cache et les requêtes SQL sont exécutées dans la mémoire centrale. Ceci confirme que le temps dominant est la construction et la communication de documents XML. Comme précédemment, N varie de 1 à 3000 pour faire varier la sélectivité. Nous évaluons d'abord la requête sur le médiateur M4, puis sur le médiateur M2. Dans le premier cas, la jointure est exécutée par la source de données (Oracle) dans la mémoire du serveur; dans le deuxième cas, la jointure est exécutée sur le médiateur et des tuples XML sont transférés sur le réseau. Encore une fois, le résultat (voir figure 13) prouve que le temps de transfert est dominant. Il prouve également que la jointure intersite est une opération coûteuse qui devrait être poussée vers l'adaptateur si possible.

Compression XML et transfert brut

Transférer des documents XML entre les adaptateurs et les médiateurs semble être coûteux. Chaque XTuple est codé dans un message XML et envoyé sur le réseau. Le message XML est alors analysé au niveau client et transformé en interne en un descripteur de XTuple et en arbres XML au fil du flux d'évènements. Ainsi, le nombre de messages est important et la durée de la transformation est longue. On peut arguer du fait que notre réseau est lent (10 Mbits), mais ce n'est pas suffisant pour expliquer les résultats.

Pour gagner en nombre de messages, nous pourrions employer le transfert en masse, et envoyer plusieurs messages dans un bloc. Le nombre de messages par bloc devrait être accordé de telle sorte que le pipeline sur le client puisse continuer à travailler sans à-coup. Néanmoins, ceci n'empêche pas l'analyse et la transformation des messages très longs. C'est de toute façon inhérent à XML et ceci dégradera toujours les exécutions.

Une solution est d'employer un format compressé pour transférer les XTuples. Les schémas de XTuples sont connus par le client et le serveur sous la forme d'une liste de chemins. Les types de valeurs (feuilles des arbres XML) sont également connus par des schémas XML. Ainsi, un mécanisme évident de compression consiste à envoyer un XTuple comme une séquence d'identifiants de chemin (16 bits sont suffisants) suivie de la valeur de feuille codée selon son type. L'analyse sera alors une tâche évidente. Cependant, nous nous éloignons alors de la philosophie de XML et de la généralité du mécanisme de communication. Bien que ce soit un peu contraire aux principes de XML, nous croyons qu'un dispositif de compression permettant d'économiser du temps d'analyse est crucial.

Algorithmes implantant les opérateurs

La version testée du médiateur utilise un algorithme simple de jointure (boucles imbriquées optimisées). Il est évident que d'autres algorithmes devraient être considérés, pour la jointure notamment, mais aussi pour d'autres opérateurs (par exemple, pour l'imbrication qui est assez complexe). Implémenter la jointure dépendante, c.-à-d., une jointure lisant une XRelation et en interrogeant l'autre avec la valeur lue, pourrait être utile pour gagner en nombre des messages en cas de résultat de faible cardinalité. La jointure par tri-fusion et la jointure par hachage pourraient également être utiles. Ainsi, nous intégrons actuellement une bibliothèque d'algorithmes pour chaque opérateur de la XAlgebra. Le problème est alors de choisir le meilleur plan. Une solution sophistiquée consiste à développer un modèle de coût.

Modèle de coût

La solution classique pour choisir le meilleur plan d'exécution est de comparer les coûts des différents plans en utilisant un modèle de coût. Nous proposons un modèle de coût fortement inspiré de DISCO [START_REF] Tomasic | Scaling Heterogeneous Databases and the Design of DISCO[END_REF]. Le médiateur est muni d'un modèle de coût générique dérivé d'un modèle de coût relationnel étendu avec la manipulation d'arbre. Chaque adaptateur peut alors exporter des statistiques et des formules détaillées de coût vers le médiateur. Le modèle générique de coût est généralement employé avec des exportations de statistiques (pour évaluer des cardinalités), et les formules spécifiques exportées par un adaptateur peuvent surcharger les formules génériques. Cette approche donne un cadre pour calculer le coût global d'un plan de requête intégrant l'information locale des sources.

Pour communiquer leur modèle de coût au médiateur, un adaptateur emploie un langage de modèle de coût. Dans un environnement XML, le langage de coût doit être défini en XML. Comme les formules et les définitions de statistiques emploient beaucoup de notations mathématiques, nous avons construit une proposition de langage de coût sur MathML. MathML est une spécification du W3C pour coder en XML la représentation ou la structure d'un objet mathématique. Seules les informations structurelles sur un objet mathématique sont intéressantes dans notre cas. Les avantages d'employer le format MathML pour décrire des formules de coût sont triples: il est entièrement en XML, il supporte des formules générales, et des logiciels courant de calcul peuvent être employés pour calculer les formules.

Les paramètres utilisés pour l'évaluation d'un modèle de coût sont des statistiques relatives au système (statistiques système) et des statistiques relatives aux données (statistiques de données). Pour des données semi-structurées, quelques autres paramètres système devraient être définis, comme la comparaison entre deux valeurs typées, la comparaison entre deux arbres, la navigation dans un arbre (suivi de pointeurs). Les statistiques de données dépendent des données et des collections des données contenues dans la source. Les statistiques classiques de données utilisées sont: la cardinalité d'une collection, la distribution d'un attribut dans une collection, les valeurs minimum et maximum prises par un attribut. Pour des données semi-structurées, on doit ajouter certains paramètres tels que la profondeur et la largeur moyennes des arbres dans une collection. Une telle information pourrait être dérivée des schémas XML.

Un modèle de coût de médiation dépend des paramètres système et des paramètres de données choisis. Une ou plusieurs formules sont définies afin de calculer le coût d'évaluation d'une requête dans ce système (grosse granularité) ou un attribut dans un opérateur particulier (granularité fine). Les formules pour les granularités les plus fines sont spécifiques aux sources et peuvent être exprimées avec des paramètres spécifiques. Les formules pour les granularités les plus grandes se composent de la cardinalité, du coût total et du coût d'exécution.

En résumé, développer un modèle générique complet de coût avec surcharge des adaptateurs est possible dans un médiateur XML. Des formules de coût peuvent être échangées en XML. Un modèle de coût est nécessaire pour choisir les meilleurs plans d'exécution, basés sur des estimateurs des coûts de communication et des coûts de traitement.

Capacité des adaptateurs

Dans la version décrite du médiateur, les capacités de source sont prises en considération par catégorie. Nous supportons trois catégories des sources: Des sources XQuery, des sources SQL, et des fichiers XML. Fondamentalement nous poussons les requêtes XQuery aux sources XQuery, SQL de base aux sources SQL, et les sélections aux fichiers gérés par un filtre. Cela est insuffisant pour prendre en compte des capacités de traitement détaillées des sources. Pour aller plus loin et tenir compte des capacités de traitement détaillées des sources au niveau du médiateur, une description précise des capacités de traitement de l'adaptateur est exigée. Ceci peut être fait globalement pour un adaptateur en envoyant un fichier XML associé aux métadonnées détaillant quels opérateurs XML sont autorisés sur toutes les collections ou spécifiquement sur une collection. Les règles les plus spécifiques prévalent toujours.

Cache sémantique

Une autre manière de réduire la transmission de messages est de mettre en oeuvre un cache sémantique au niveau du médiateur. Les XTuples répondant à une requête exécutée sur le médiateur peuvent être conservés dans un tel cache. Le format XML n'est pas approprié car trop volumineux; nous employons plutôt le format comprimé présenté ci-dessus. Ainsi une table des requêtes exécutée ordonnée par horodate d'exécution avec résultats associés devrait être maintenue dans le cache. Celle-ci serait employée pour répondre à de nouvelles requêtes. Naturellement, la mise à jour sur les données des sources ne peut être prise en considération sans mécanisme de remontée d'événements. Ainsi, le cache sémantique est seulement utilisable sous certaines collections de documents XML non mis à jour fréquemment. Il est cependant de grande utilité dans le cas de sources lentes, par exemple, les sources web.

Avec le cache sémantique, une nouvelle requête devrait d'abord être vérifiée par le cache pour déterminer si il peut répondre totalement ou en partie à la requête. Si oui, la requête est divisée en deux parties (une partie peut être nulle): une requête locale qui peut être exécutée par le cache et une requête de source qui doit être exécutée par les sources distantes. Les deux résultats doivent être correctement assemblés. Ceci peut être fait en comparant les formes canoniques des arbres algébriques associés à la requête à celle de chaque requête du cache. Si l'une est un sous-ensemble de l'autre, le cache peut être employée pour traiter une partie de la requête. L'arbre algébrique de requête doit être élagué pour remplacer la partie commune par un appel aux XRelations du cache. Employer un cache sémantique XML pour XQuery est un sujet complexe qui doit être encore étudié, mais qui pourrait être très bénéfique aux performances.

Conclusion

Nous avons présenté le système XMedia permettant d'interroger en XQuery des vues intégrées de données hétérogènes. Une première version du système a été développée à l'université à la fin des années 90, puis transférée à l'industrie de 2000 à 2002 où elle a été complètement remodelée. La deuxième version est commercialisée et a eu plusieurs applications utilisées ou planifiées, notamment dans le domaine du tourisme, de la santé, et de la pharmacie. Elle va être disponible en logiciel libre. Actuellement, un nouveau projet de recherche est en cours visant à développer un médiateur amélioré, qui devrait tenir compte des leçons du passé.

La version décrite dans cet article a des fonctionnalités uniques. Les requêtes XQuery sont compilées dans des plans d'exécution exprimés en algèbre

Figure 1 :

 1 Figure 1: Vue d'ensemble de l'architecture du médiateur

Figure 2 :

 2 Figure 2: Exemple de XRelation

Figure 3 :

 3 Figure 3: Exemple d'une opération utilisant XProject

Figure 4 :

 4 Figure 4: Exemple d'une opération utilisant XProduct

Figure 5 :

 5 Figure 5: Exemple d'une opération de jointure naturelle utilisant XJoin (sur / personne/adresse/ville)

Figure 6 :

 6 Figure 6: Exemple d'une opération utilisant XNest

Figure 7 :

 7 Figure 7 : Schéma et distribution des données

  'exécution peut maintenant être construit en termes d'opérateur de la XAlgebre. Pour chaque requête atomique, un opérateur XSource est créé. Son rôle est d'envoyer la requête à l'adaptateur et d'obtenir le résultat sous la forme de XTuple. La requête globale est utilisée comme moyen de recomposer l'arbre de jointure et l'opérateur d'imbrication. En conclusion, l'opérateur XReconstruct est ajouté pour produire le résultat XML correct. Le plan d'exécution proposé pour la requête d'exemple est représenté figure 8. Celui-ci devra évidement encore être optimisé.

Figure 8 :

 8 Figure 8: Plan d'exécution proposé pour la requête

Figure 9 :

 9 Figure 9: Comparaison d'architectures de médiation

Figure

  Figure 10: Coût d'une exécution sur M0, M1 et A3

Figure 11 :

 11 Figure 11: Temps d'exécution pour chaque phase

Figure 12 :

 12 Figure 12: Temps d'exécution pour les différentes étapes de la phase d'initialisation

Figure 13 :

 13 Figure 13: Temps d'exécution sur M2 et sur M4

  Le parseur analyse la requête et produit la structure de requête interne si la requête est syntaxiquement correcte et bien typée. Autrement, il renvoie une erreur documentée.

	(Manolescu et al., 2001). Par exemple, les clauses LET sont traitées en tant que
	définitions temporaires de variables et éliminées. Les expressions de la forme
	FLWR (FLWR) sont désimbriquées si possible. Dans un second temps, le
	canoniseur transforme les requêtes normalisées en des requêtes simples plus un
	opérateur de reconstruction. Une requête simple est une requête dans laquelle toutes
	les expressions de retour sont des expressions simples de chemin organisées en
	séquence. La canonisation permet donc de décomposer une requête normalisée en
	requêtes simples traitant les données issues des sources et en une requête de
	reconstruction en mémoire. L'opérateur de reconstruction est une séquence
	d'éléments de construction dont les balises et les données sont des constantes ou qui
	proviennent d'expressions simples de chemin.
			XML/DBC
		API XML/DBC
	executeQuery (XQuery)		getXMetaData ()
		XML	METADATA
	PARSEUR
	Requête
		RECONSTRUCTEUR
	CANONISEUR
	Requête Canonique	EVALUATEUR	Cache XML
	DECOMPOSEUR
	atomique Requête	OPTIMISEUR	d'exécution Plan	EXECUTEUR	XML/DBC
	Canoniseur (Canonizer)
	Le canoniseur normalise d'abord la requête et produit des requêtes sous forme
	canoniques. La normalisation applique les règles de transformation décrites dans

  Classiquement, une relation est un sous-ensemble du produit cartésien d'une liste de domaines. Avec des relations simples, les domaines sont de simples ensemble de valeurs; avec des relations d'objets, les domaines peuvent être des ensembles d'objets ou de valeurs. Nous introduisons la XRelation, qui peut être considérée comme un cas spécial des relations d'objets, un domaine pouvant des arbres XML. Classiquement, un arbre XML est un ensemble d'arbres ordonnés étiquetés. En outre, les liens croisés peuvent être supportés en tant qu'arêtes spéciales. Avec les XRelations, les domaines sont des arbres XML construit sur un ensemble donné de chemins (le guide de données). Les attributs sont des XPath mettant en référence des noeuds dans les arbres XML (voir le schéma 2). Chaque attribut peut être multi-valué, c.-à-d., référencer plusieurs sous-arbres. Les XRelations sont des collections ordonnées de XTuples. Ainsi, chaque XTuple se compose d'attributs appelés XPath, dont les valeurs mettent en référence des sousarbres dans la collection d'arbres. En conséquence, le schéma d'une XRelation est du type R (XPath+, [Path+]), où XPath définit les attributs et Path un ensemble de chemins définissant un arbre XML. La figure 2 montre un exemple d'une XRelation composée de quatre XTuples. Le schéma de la XRelation est Example (personne/prenom, personne/nom; personne/adresse/rue, personne/titre, livre/auteur/nom, livre/date [personne/prenom, personne/nom, personne/adresse, personne/adresse/rue, personne/adresse/ville, livre/titre, livre/auteur, livre/auteur/nom, livre/date]). Un XTuple se rapporte à des noeuds et peut être considéré comme un index d'arbres XML. Le traitement par des références calculées une seule fois est beaucoup plus efficace que le traitement des arbres par navigation directe.

  La phase d'atomisation extrait de la requête élémentaire le maximum de sousrequêtes pour chaque collection logique avec les restrictions associées et les autres opérateurs unaires comme les tris ou les agrégats. Elle produit également la condition de jointure finale éventuellement suivie d'agrégats et de tris. Elle se termine généralement en générant un opérateur d'imbrication pour obtenir le XTuple résultat correctement imbriqué pour reconstruire les documents XML finaux. Dans notre cas simple avec seulement des restrictions et des jointures, nous obtenons trois requêtes atomiques et deux jointures suivi d'une imbrication. Elles peuvent être exprimés suivant la syntaxe XQuery de la façon suivante : La requête est encore analysée afin d'identifier les sources de données contribuant au résultat. Les métadonnées décrivant chaque source enregistrée sont employées pour déterminer la pertinence de la source et pour remplir les jokers de XPath. Notons qu'une source peut gérer plusieurs collections et qu'une collection peut être trouvée sur plusieurs sources. Pour les requêtes atomiques T1, T2 et T3, nous obtenons:

	-Requête atomique t1
	let t1 ::= for $n in Collection("*")/nation
	where contains ($n/comment, "iron")
	return ($n/nationkey, $n/name)
	return ($n/nationkey, $n/name) -Requête atomique t2
	Requête élémentaire 2 let t2 := for $s in Collection ("*")/supplier
	let t2 := for $t in $t1 return ($s/contact/localisation/nationkey,	$s/id/suppkey,	$s/name,
	for $s in Collection ("*")/supplier $s/contact/phone)
	-Requête atomique t3 for $ps in Collection ("*")/partsupp let t3 := for $ps in Collection ("*")/partsupp
	where $ps/availqty > 45 where $ps/availqty > 45
	return	($s/contact/localisation/nationkey,	$s/id/suppkey,	$s/name,
	$s/contact/phone, ($ps/suppkey , $ps/partkey, $ps/supplycost,))
	Requête de reconstruction
	<nation>
	<name>$t1/name</name>
	<suppliers>
	<supplier>$s/name</supplier>
	<phone>$s/contact/phone</phone>
	<partsupp>
	<partkey>$ps/partkey</partkey>
	<supplycost>$ps/supplycost</supplycost>
	</partsupp>
	</suppliers>
	</nation>
	Requête	Chemins utilisés		sources
	atomique
	t1	Collection("NATION")/nation/comment	A6
		Collection("NATION")/nation/nationkey
		Collection("NATION")/nation/name
	t2	Collection("SUPPLIER")/		A4, A6
	supplier/contact/localisation/nationkey
	Collection("SUPPLIER")/supplier/id/suppkey
	Collection("SUPPLIER")/supplier/id/name
	Collection("SUPPLIER")/supplier/contact/phone
	Requête décomposée

return ($ps/suppkey , $ps/partkey, $ps/supplycost) -Requête globale for $n in t1, $s in t2, $ps in t3 where $s/id/suppkey = $ps/suppkey and $s/ /nationkey = $n/nationkey return ($n/name, ($s/name, $s/contact/phone, ($ps/partkey, $ps/supplycost)))

Ingénierie des Systèmes d'Information Volume X -n° X/2002

Ingénierie des Systèmes d'Information Volume X -n° X/2002

Ingénierie des Systèmes d'Information Volume X -n° X/2002

Ingénierie des Systèmes d'Information Volume X -n° X/2002