Tuyet-Tram Dang-Ngoc * -Georges Gardarin

Evaluating XQuery in a full-XML Mediation architecture

Keywords: Mediation Architecture, XML Algebra, XQuery Evaluation MOTS-CLEFS : Architecture de médiation, Algèbre XML, Evaluation XQuery

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.

RÉSUMÉ : 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. Enfin, nous parlerons d'extensions que nous étudierons qui permettrons d'améliorer les performances du médiateur.

Introduction

In recent years, there have been many research projects focusing on heterogeneous information integration. Typical information integration systems have adopted a wrapper-mediator architecture [START_REF] Wiederhold | Intelligent Integration of Information[END_REF]. In this architecture, mediators provide a uniform user interface to query integrated views of heterogeneous information sources. Wrappers provide local views of data sources in a global data model. The local views can be queried in a limited way according to wrapper capabilities. Although the local as view (LAV) approach has been considered in some systems [START_REF] Levy | Querying Heterogeneous Information Sources Using Source Descriptions[END_REF] [START_REF] Manolescu | Answering XML Queries over Heterogeneous Data Sources[END_REF], most systems follow the global as views (GAV) approach, in which the integrated views are designed in terms of the local views of sources. Well-known research projects and prototypes based on this architecture include 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] and Yat [START_REF] Cluet | Your Mediators Need Data Conversion[END_REF]. While in the 90's most studies were based on using the object model as data integration model, the focus has come to XML as global model at the beginning of the new century.

The advantages of XML as an exchange model, (i.e., it is rich, clear, extensible and secure), makes it the best candidate for supporting the integrated data model. In addition, using XML views for local data sources hides the local specificities of each system. Furthermore, the richness of the XML schema model simplifies wrapper mappings. Also, the emergence of XQuery as a powerful universal query language for XML makes it possible to query XML global and local views in a uniform way based on a standard interface. Thus, these advantages explain that several research projects have emerged to query in a uniform way heterogeneous data sources based on XML as exchange model, see for example (Christophides et al., 2000) (Manolscu et al., 2001) [START_REF] Shanmugasundaram | Querying XML Views of Relational Data[END_REF]. e-XMLMedia is providing one of the first products based on XML to integrate heterogeneous data sources, namely the e-XML mediator (see www.e-xmlmedia.fr). It is the result of a technology transfer from the university of Versailles (PRiSM Laboratory). This mediator with the associated wrappers provides the required functionalities to query in a uniform way heterogeneous data sources. It is a sophisticated component composed of several packages in charge of decomposing queries into mono-source sub-queries, efficiently shipping local sub-queries to data sources, getting results in XML through a SAX interface, processing and assembling them. Queries as well as sub-queries are expressed in XQuery. In addition, capabilities are associated to wrapper so that the mediator sends only supported queries to wrappers. In summary, the mediator uses XML to represent disparate data in a common format and create a unified view of that data. Using advanced distributed query processing technology, the mediator provides an application with the services it needs to integrate on demand heterogeneous information. This paper describes a version of the mediator called XMedia. This version differs from the industrial version in some ways, notably it is based on an original algebra for XML processing called the XAlgebra. The contributions of this paper are three-fold. First we describe the modular system architecture of the XMedia Mediator. Second, we describe the query processing algorithm, which is based on query transformations and the algebra operating on tuples of XML trees. A critical result is that the mediator is capable of processing most queries in pipeline on XML event flows. Third, we report on a benchmark of the architecture showing the weaknesses and strengths of the main system components, thus leading to new ideas for query optimization. Some of them should be integrated in a future version of XMedia.

The rest of this paper is organized as follows. The next section focuses on the middleware objectives and architecture. Section 3 describes the XAlgebra, a simple extension of relational algebra to process XML forests. Then, we give an overview of the unique query processing technology embedded in the XMedia mediator through a query example. Section 5 reports on some performance measurement based on the TPC/R benchmark adapted to XML. In section 6, we discuss possible extensions of the query processing engine. We conclude by summarizing the contributions and discussing future developments.

System Overview and Architecture

Integrating and Querying XML Views

XMedia mediator is a data integration middleware managing XML views of heterogeneous data sources. It follows the global as view approach. Global views are defined by administrators through Queries referencing local collections of XML documents. They are queried by users through a Java API extending JDBC to XQuery, called XML/DBC. Data sources can be of various types, including relational databases, XML files, XML databases, legacy applications, etc. Specific wrappers delivering metadata through introspection and providing at least a subset of XQuery on exported collections encapsulate them. Ideally, a wrapper can provide mapping functionalities as XML views to achieve local mappings of data and metadata at the source.

The mediator aims at supporting fully XML standards, including XML schema, XQuery, DOM and SAX interfaces. XML schemas are used intensively for metadata representation. In particular, schemas describe wrapped data sources and views at any layer. XQueries are type-checked through schemas. We support currently most XQuery use-cases. Finally, we internally process XML as SAX event flows for efficiency reasons. Indeed, DOM is in general too costly to instantiate XML documents during processing. However, the user can if required get DOM trees as results and we sometimes use DOM inside the mediator to keep XML documents for latter processing.

Queries are decomposed in optimal mono-source sub-queries and global query plans expressed in a specific algebra (the XAlgebra), extending the relational algebra to process trees. Queries are optimized in a simple but efficient way. Simple heuristics are supported in the current version, while cost-based query optimization could be introduced in the future. Heuristics include the XML counter-part of classical relational detachment of selections and semi-join transformations. Several algorithms are implemented for processing XAlgebra operators.

To discover relevant sites for a query and decompose it, metadata are maintained describing the sources. When a wrapper is registered to a mediator, metadata describing the source are sent to the mediator through a configuration file. This file contains an XML document containing a schema for each collection exposed by the source wrapper. If the schema of a collection is not known, a schema by default is generated, which describes the path set of the collection; it is a form of dataguide [START_REF] Goldman | DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases[END_REF]. Metadata schemas are kept in the mediator memory and indexed by source, namespace, collection and path for fast access during query processing.

A Recursive Dataflow-based Architecture

The mediator architecture is represented in Figure 1. The XML/DBC API is the only interface with external components. Thus, notice that the mediator ships requests to wrappers through XML/DBC and thus get results through it. This makes possible for a mediator to see another mediator as a wrapper. Furthermore, results are supplied in XML/DBC through SAX readers. Thus, flows of events are transferred between mediators and wrappers, avoiding the overhead generated by the allocation of intermediate memory structures. The recursive and data flow-based architecture is interesting for applications that can perform data integration at multiple stages without much performance degradation. Evaluating XQuery in a full-XML mediation architecture 5

The major sub-components are the XQuery parser, the metadata manager, the query evaluator, the query decomposer, and the result reconstructor. All components are briefly described below.

Parser:

The parser parses the query and generates the query structure if the query is syntactically and type correct. Otherwise, it returns a documented error.

Canoniser:

The canoniser first normalizes the query and generates a query in normal form. Normalization applies the transformation rules described in (Manolscu et al., 2001). For example, let clauses are treated as temporary variable definitions and eliminated. Expressions of the form FLWR(FLWR) are unnested when possible. Second, the canoniser transforms normalized queries in simple queries plus a reconstruction operator. A simple query is a query in which all return expressions are simple path expressions. The reconstruction operator is a sequence of element constructors whose tags and data are either constants or come from simple path expressions.

Decomposer:

The decomposer decomposes each simple query in atomic queries, i.e., query involving only one global collection. It also generates a join tree (possibly empty) to keep track of the dependency between the atomic queries. Nesting and unnesting operators may also be generated to restructure intermediate results. Moreover, the decomposer identifies from the metadata the relevant data sources and the collection localization. Based on this information, it translates the atomic queries on a global collection in a union of queries on local collections. In particular, it translates global paths with regular expressions in local paths replacing jokers by the possible paths extracted from the metadata. Finally, it creates a first execution plan for the query.

Optimizer:

The execution plan is composed of operators of the XAlgebra. The role of the optimizer is to transform and annotate it to get the best possible plan. Simple optimizations of the query plan are performed in the current version, but more complex ones are planned based on a cost model. For example, the optimizer groups the operators that refer the same source in a single query for shipping once. It also orders the global operators according to query heuristics and selects the best processing method (parallel, sequence or pipeline) for global operators. It should also choose the best algorithm for each algebra operator.

Executor: The executor is in charge of shipping the sub-queries to the wrappers using XML/DBC and collecting the results in cache memory. In general, results are not fully instantiated in main memory but SAX events are produced and directly processed by the evaluator when possible. We represent each ordered collection of XML tree shipped from a wrapper as an XTuple, i.e., a tuple of references to forest of XML trees instantiated in cache.

Evaluator: Based on the query plan, the evaluator evaluates the remaining global query and applies the algebraic operators in main memory. The XAlgebra operators are able to perform XPath-based projection, restriction, product, join, nesting, sorting, union, intersection and difference of ordered collections of XTuples. For each operator, we implement one or more specific algorithms. For example, several global join algorithms are possible. The evaluator may work with intermediate collections fully stored in main memory, but can also work on a SAX flow of events, thus implementing pipelining and hash joins. Dependent join algorithms requesting XTuple to one source and querying the other based on the results are also possible.

Reconstructor: It applies the reconstruction operator to the intermediate results represented as XTuples and generates the query answer. In other words, it nests and tags the data so as to construct the final result. Finally it built the SAX event flow to deliver the results to the user.

Metadata manager: This package manages the schemas of all registered sources. Further, for each source, it maintains the collection names with the associated queryable path set. The path set is a kind of dataguide giving an overview of all paths instantiated in the source. If a path is missing, it will not be queried. The path set has to be given by the wrapper when registering the source (on command XDescribe).

Physical Algebra

As mentioned above, XQuery requests are translated in a physical algebra simple enough to be amenable to optimization and implementation. Several algebras have been recently proposed (Christophides et al., 2000) [START_REF] Jagadish | TAX: A Tree Algebra for XML[END_REF]) [START_REF] Fernandez | An Algebra for XML Query[END_REF] [START_REF] Galanis | Following the Paths of XML: an Algebraic Framework for XML Query Evaluation[END_REF] for XML. Our goal is to be as close as possible to some extended relational algebra [START_REF] Zaniolo | The Representation and Deductive Retrieval of Complex Objects[END_REF], but to be able to manipulate trees and ordered collections of trees. We now introduce our extended relational data model and its associated algebra for processing XML collections.

Data model

A relation is classically a subset of the Cartesian product of a list of domains. With simple relations, domains are simple set of values; with object relations, domains can be set of objects or values. We introduce XRelation, that can be considered as a special case of object relations, domains being XML trees. Classically, an XML tree is a set of labeled ordered rooted trees. In addition, crosstree hyperlinks can be supported as special edges.

With XRelation, domains are XML trees of given path set. Attributes are XPath referencing nodes in the XML trees (see Figure 2). Each attribute can be multivalued, i.e., refers several sub-trees. XRelation are ordered collections of XTuples. Thus, each XTuple is composed of XPath named attributes, values of which reference subtrees in the collection of trees. As a result, the schema of an XRelation is of type R(XPath+, [Path+]), where XPath's are defining the attributes and Path's compose the path set of the XML trees.

XAlgebra Operators

The XAlgebra includes both relational operations to process the tables of references and navigation in the XML trees. The algebra is a physical algebra in the sense that algebraic expressions are used to process XML flows and that algorithms are directly implementing them.

XML documents are sent to the mediator in the form of event flows (based on SAX). XTuples are created "on the fly" when XML documents of known schemas are received from the wrappers. Non-blocking operators work in pipeline on the event flows. Blocking operators require the full instantiation of an input flow in cache memory. Non-blocking N-ary operators works in general in parallel on the input flows.

All operators of the XAlgebra receive a collection of XTuples as input and return a collection of XTuples as output. In general, we modify directly the XRelation in memory. Operators also have specific parameters; we only give the some logical ones in the sequel.

The evaluation process of each operator is composed of two steps: a preparation step and an execution one. The preparation step analyzes the input XRelation(s) and the parameters associated to the operator to determine what will be the exact operation to do when the XTuples will flow in. For example, for an operation that requires merging trees, the preparation step determines to which reference node the new sub-tree will have to be linked and which paths will be in common. Thus, the execution step is efficient, as the major part of processing has already been done.

Xsource: XSource is the starting operation to process an XML data source. XSource takes a particular XRelation of schema (Root, [P1, … Pn]) representing a data source as input and generates an XRelation of given schema (a, b, c,… [P1,… Pn]), where a, b, c, … are XPaths over P1, …, Pn. In practice, XSource ships a query to a data source and returns the result as an XRelation. For that, it parses the SAX flow result "on the fly" and generates the collection of XTuples by constructing the trees and identifying the nodes that must be referenced in the references part of the XTuples. XSource preserves the order of the source documents. It is a non-blocking operator, which can construct XTuples as soon as the SAX reader has began to send events.

XRestrict:

The XRestrict operator filters each XTuple of an XRelation on a predicate logical expression, each elementary predicate comparing an attribute to constants or checking range constraints over an attribute. If the condition is true, the XTuple is kept. Otherwise, it is removed with its associated XML trees. XRestrict is order-preserving and non-blocking. XProject: XProject generalizes the classical projection to XRelations. It takes an XRelation as input and returns an XRelation with only the selected XAttributes in table; non-referenced sub-trees are also removed. In practice, it processes the reference part of the XTuples to determine if the XAttribute must be kept. If not, it deletes the reference and suppresses non-referenced paths in the tree part. Figure 3 illustrates an example of XProject. As well as XSource, XProject is order-preserving and non-blocking.

XSort, XNest, Xunnest: XSort is a simple operator sorting an XRelation on a given list of XPath, by ascending or descending order.

XNest applies a grouping operator to an XRelation. It groups XTuples that have the same values on a set of attributes (i.e., XPath's) by merging their common subtrees and inserting the non common branches in a unique composed tree. Multivalued references are in general created. This is a costly operator that first applies an XSort and then a merging of trees with similar path set.

XUnnest is the reverse of XNest: it decomposes multi-valued sub-trees of similar path set in the XRelation by replicating common sub-trees in the reference part and creating as mono-valued trees as needed in the tree part.

Xproduct, Xjoin: The XProduct operation takes two collections as input and computes the Cartesian product of them. Moreover, the trees of each XTuple are merged if their path set overlaps from the roots. In general, the Cartesian product can be pipelined but order is then non-preserved. It is possible to preserve the order of one input relation using a nested-loop algorithm, but then the operator is blocking. In general, these parameters depend on the implementation algorithm as well as for relational algebra.

XJoin is the generalization of a relational join. It is an XProduct combined with an XRestrict. The XJoin is a core operator of the physical algebra. Several algorithms have been implemented for the XJoin including nested loops, sort-merge and "query one source with the other". While the nested loop can be pipelined, others cannot. Only non-pipelined nested loops are order-preserving, but sort-merge can produce an interesting order.

Xaggregate:

As with extended relational algebra, the purpose of aggregation is to apply a MIN, MAX, COUNT, AVG or SUM function to a collection of values. The collection is simply given by an XPath attribute of the XRelation. Except with COUNT that counts directly the number of references, the functions apply to the values referred by the attributes, which have to be correctly typed (numeric with classical functions). XAggregate is a blocking operation non order-preserving.

XReconstruct: Reconstruction is in general the final operation in an algebraic tree to publish the final SAX event flow as result. It takes as input parameters an XRelation and an XML document in which values are replaced by attributes of the XRelation (i.e., XPaths). The effect is to produce one result instance per XTuple. The operation is order-preserving and non-blocking.

XUnion, XDifference, XIntersection: They are classical set operations applied to set of XTuples.

XQuery Processing Example

As introduced in the architecture section, the construction of an execution plan follows the following steps: (1) Normalization and canonization (2) Atomization and join extraction (3) Source identification (4) Execution plan creation (5) Execution plan optimization.

We are now going to illustrate these steps with a simple example. For our experiments, we adapted the TPC-R benchmark to a scenario suitable for a federated and semi-structured system. We basically grouped some tables together to obtain hierarchical data. Figure 4 describes the schema and distribution of data extracted from the TPC-R benchmark. To illustrate the query processing steps described above, we assume the following query: "Display for each nation having iron in comment, the list of suppliers (name and phone) located there with nested partsup (partkey and supplycost) having an available quantity greater than 45." The formal query can be written in XQuery as follows: As there is not any LET clause in the example, the query is directly unnested. Applying rules similar to that defined in [START_REF] Manolescu | Answering XML Queries over Heterogeneous Data Sources[END_REF], we unnest subqueries from the request and purge them of all reconstruction tagging. We call them elementary queries. Then, the canonization phase generates the reconstruction query (XReconstruct operator) plus the elementary query. The reconstruction query is simply the returned document with XPath expressions in place of constants. Next, the atomization step extracts from the elementary query the maximum subqueries for each logical collection with associated restrictions and other unary operators as sort or aggregate. It also generates the final join conditions possibly followed by aggregate, sort and a final nest operator to get the resulting XTuple's correctly nested for reconstructing the final XML documents. In our simple case with only restrictions and joins, we obtain three atomic queries and two joins followed by a nest. They can be expressed as follows in XQuery-like syntax. The request is then analyzed further to identify the data sources that may contribute to the result. The metadata describing each registered source are used both to determine source relevance and to complete XPath's with jokers. Notice that a source can handle several collections and that a collection can be found on several sources. For atomic queries t1, t2 and t3, we obtain: The execution plan can now be constructed in terms of XAlgebra operator. For each atomic request, an XSource operator is created. Its role is to ship the request to the wrapper and get the result under the form of XTuple's. The global request is used to compose the join tree and the nest operator. Finally, the XReconstruct operator is added to generate the correct XML result. The proposed execution plan for the example request is represented in Figure 5. Of course, this one should be further optimized.

Figure 5. Proposed execution plan for the request

The algebraic tree can be optimized using traditional rules of the nested relational algebra: perform restriction at first, push project and nest operator up the tree, order joins, select the best algorithm for each operator. This last optimization requires either user hints or a cost model. We shall discuss that further in the sequel.

Performance Measurement

To further understand the system bottlenecks and determine useful optimizations, we experiment with a beta version of the industrial system. In this section, we describe some results of our experiments that try to capture the overhead induced by each component of the architecture.

Evaluated Architecture

We use client-server architecture with two servers. The client processor is a Celeron 600 MHz with 64 Mb RAM, while the servers are both Pentium 4 1.6 GHz with 256 Mb RAM. The network is 10 Mbits/second. All systems are running Linux. 2.4

Figure 6. The compared mediation architecture

To compare various architectures, we use different arrangements of mediators and wrappers, as shown in Figure 6. M0, M1, M2, M3 and M4 are mediators. They are all run on the client computer. A1, A2, A3 are wrappers on top of a relational databases. A4, A5, A6 are wrappers on top of a semi-structured database (this is indeed the e-XML Repository of e-XMLMedia). A7 is a wrapper on top of a relational database that contains exactly all the data of A1, A2 and A3. M1 is connected to mediators while all others are connected to wrappers. This is possible as mediators and wrappers have the same interfaces.

Time per step

The processing of a request follows the steps below:

1. Request parsing that transforms the XQuery request into an internal form. 2. Algebra tree construction that normalizes, canonizes, atomizes the request and finally constructs the algebraic tree.

Evaluating XQuery in a full-XML mediation architecture 15 3. Execution initialization establishing the connection to the wrappers and getting the first XTuple. 4. Local execution of the request on the wrapper including sending the request to the wrapper, getting the result by XML/DBC in the SAX format and transforming the SAX flow in XTuple. 5. Global execution of the request and reconstruction, i.e., processing the XTuples through the algebraic tree to return the result. Steps 1, 2 and 3 compose the initialization phase of request processing.

The time spent for the initialization phase, for steps 4, 5, and for complete processing are depicted on Figure 7. The initialization step is almost insignificant with regards to other times. The total time is still approximately the double of the wrapper time. The evaluation on the wrapper consists of: (1) Transforming the request into SQL (2) Executing the request on the database (Oracle) (3) Getting the tuples and changing them into XML document.

As the results are measured with a hot database, the tuples are in cache and SQL requests are executed in main memory. This confirms that the dominant time is XML construction and shipping. In Figure 8, we detail the initialization time between time to parse the query, time to generate the execution plan and time to get the first result. All these times are small. Request parsing is very short (< 10 ms). Generating the execution plan takes a little more time (< 15 ms). Getting the first result requires a little more time, showing again that exchange time is dominant.

Mediation Cost Overhead

To evaluate the costs of the mediator overhead, we consider a set of queries of the modified TPC/R benchmark introduced above. The following simple query for $O in collection("ORDERS") where $O/orderkey < N return <result> <O>$O/comment</O></result> is executed successively on mediator M0, mediator M4 and wrapper A3. N varies from 1 to 3000 to get different result size. In this way, we can compare the overhead cost of a mediator on another mediator, and of a mediator on a wrapper. To compare with a direct access to wrapper A3, all orders are managed by wrapper A3. Figure 9 hows the execution time depending on the number of resulting documents for each type of execution. The Figure 9 shows that the execution time of the query on M1 accessing M2 then A3 differs by less than 10% from the execution time of M0 accessing directly A3. This demonstrates the value of our recursive architecture and in general the small overhead induced by the mediator for simple queries. Notice that running the query directly on the wrapper takes approximately half time. This is due to the time required for transferring and converting the data in XML.

Intersite join

We now submit a set of requests that perform a join between two tables. The request is as follows: As previously, N varies from 1 to 3000 to change selectivity. We first evaluate the request on the mediator M4 and then on the mediator M2. In the first case, the join is executed by the data source (Oracle) in the server memory, in the second case, the join is performed on the mediator and XML tuples are transferred on the network. Again, the result (see Figure 10) shows that the transfer time is dominant. It also shows that intersite joins are costing operations that should be pushed to the wrapper when possible.

Possible Improvements

The results of the experiments, some being reported above, demonstrate the high communication cost to exchange XML documents between wrappers and mediators. Thus, this is the first point to improve. We propose several improvements that should reduce this cost drastically.

XML Compression and Bulk Transfers

Transferring XML documents between wrappers and mediators appears to be costly. Each XTuple is encoded in an XML message and sent over the network. The XML message is then parsed on the client and transformed internally in an XTuple descriptor and XML trees as event flows. Thus, the number of messages is important and the processing time is high. One may argue that our network is slow (10 M bits), but this is not sufficient to explain the results.

To save in number of messages, we could use bulk transfer, and send several messages in one block. The number of messages per block should be tuned such that the pipeline on the client continues to proceed smoothly. Nevertheless, this does not save parsing and unparsing of lengthy messages. This is somehow inherent to XML and may degrade performances forever.

One solution is to use a compressed format for transferring XTuples. Schemas of XTuples are known both by the client and the server under the form of a list of paths. The types of values (leaves of XML trees) are also known through XML schemas. Thus, an obvious compression mechanism consists in sending an XTuple as a sequence of path identifiers (16 bits is sufficient) followed by the leaf value encoded according to its type. Parsing will then be an obvious task. However, we may loose the purity of XML and the generality of the communication mechanism.

Although it is a bit contrary to XML principles, we believe that a compression device saving parsing time is crucial.

Operator Algorithms

The benchmarked version of the mediator uses a simple join algorithm (optimized nested loops). It is obvious that other algorithms should be considered for joins notably, but for other operators as well (e.g., nest is quite complex). Implementing dependent joins, i.e., join by reading an XRelation and querying the other with the read value, could be helpful to save in number of messages in case of small answers. Merge join and hash join could also be useful. Thus, we are currently integrating a library of algorithms for each XAlgebra operator. The problem is then how to select the best plan. A possible answer is to develop a cost model.

Cost Model

The classical solution for choosing the best execution plan is to compare plan costs using a cost model. We propose a cost model somehow inspired from DISCO [START_REF] Tomasic | Scaling Heterogeneous Databases and the Design of DISCO[END_REF]. The mediator has a generic cost model derived from a relational cost model extended with tree manipulation. Then each wrapper can export specifics statistics and formulas to the mediator. The generic cost model is generally used with the exported statistics (to evaluate cardinalities), but specific formulas exported by a wrapper can override generic formulas. This approach gives a framework to compute the global cost of a query plan integrating local information on sources.

To communicate their cost model to the mediator, a wrapper uses a cost model language. In an XML environment, the cost language has to be defined in XML. As formulas and statistics definitions use a lot of mathematics notations, we based our cost language on MathML. MathML is a specification of the W3C for coding in XML the representation or the structure of a mathematical object. Only the semantic information about a mathematical object is interesting for our purpose. The advantages of using MathML for describing cost formulas are three-fold: it is full XML, it supports general formulas, and calculation software can be used to compute formulas.

Parameters used for evaluation of a cost model are statistics relative to the system (system statistics) and statistics relative to the data (data statistics). For semistructured data, some other system parameters should be defined, such as comparison between two typed values, comparison between two trees, navigation in a tree (pointer chasing). Data statistics depends on data and collections of data contained in the source. Classical data statistics used are: cardinality of a collection, distribution of an attribute in a collection, minimum and maximum values taken by an attribute. For semi-structured data, one must add some parameters such as average depth and width of trees in a collection. Such information could be derived from XML schemas.

A mediation cost model depends on its system parameters and its data parameters. One or more formulas are defined in order to calculate the evaluation cost of a request in this system (large granularity) or a predicate in a particular operator (thin granularity). Formulas for the thinner granularity are specifics to the sources and can be expressed with specific parameters. Formulas for the larger granularity consist of cardinality, total cost and execution cost.

In summary, developing a complete generic cost model with overloading per wrapper is possible in an XML mediator. Cost formulas can be exchanged in XML. A cost model is required to select the best execution plans, based on estimators of communication costs and processing costs.

Wrapper Capabilities

In the described version of the mediator, source capabilities are taken into account by classes. We support three classes of sources: XQuery source, SQL source, XML file. Basically we push XQuery queries to our XQuery source, basic SQL to the SQL sources, and just selection to files wrapped by a filter. This is nice but insufficient for distinguishing detailed functionalities of sources. To go further and take into account detailed functionalities of sources at the mediator level, a precise description of source capabilities is required. This can be done globally for a source by sending an XML file associated to the metadata detailing what XML operator is allowed globally on all collections or specifically on one collection, the specific prevailing.

Semantic Cache

Another way to save messaging is implementing a semantic cache at the mediator level. XTuples answering a given query run by the mediator could be kept in cache. XML format will not be appropriate as too large; we would rather use the compressed format introduced above. Thus a table of queries ordered by execution time with associated results should be kept in cache and used to answer new queries. Of course, update on source data will not be taken into account. Thus, semantic caching is only possible for certain collections of XML documents not updated frequently. It is very valuable in the case of slow sources, e.g., Web sources.

With semantic caching, a new request should be first checked against the cache to determine if it can answer the request or a part of it. If yes, the request is split in two parts (one part can be null): a local request that can be answered by the cache and a source request that must be answered by the distant sources. The two results have to be correctly assembled. This can be done by comparing the algebraic trees in canonical form of the request with the one of each cached request. If one computes a subset of the other, the cache can be used to process part of the request. The request algebraic tree has to be pruned to replace the common part by a call to the XRelation in the cache. Using an XML semantic cache for XQuery is a complex subjects that has to be further worked out.

Conclusion

We have presented the XMedia system for querying integrated views of heterogeneous data. A first version of the system has been developed at the university at the end of the 90's, and then transferred to the industry from 2000 to 2002 where it was completely redesigned. Currently, a new research project is planned to develop an improved mediator, which should take into account lessons from the past. The second version is commercialized and has several ongoing applications and planned ones, notably on tourism data, health data, and chemistry data.

The version described in this paper has unique features. XQueries are compiled in execution plans expressed in an extended relational algebra capable of processing in pipeline XML trees. Query processing is clearly divided in steps. We isolated the query rewrite step from the decomposition step that generates algebraic trees processing localized data sources. Localization of collections is performed using metadata under the form of XML schemas. The optimization step requires a cost model to be fully efficient. Hints have been introduced in the industrial version.

Performance measurement demonstrates the validity of the approach but the cost of transferring XML files from wrappers to mediators appears to be excessive. Several possible improvements that should be partly implemented in XMedia have been suggested. We would like also to develop a more efficient X-machine to process XAlgebra expressions on XML flows.

Figure 1 .

 1 Figure 1. Overview of the mediator architecture

Figure 2

 2 Figure 2 shows an example of an XRelation composed of four XTuples. The schema of the XRelation is Example (person/fname, person/address, person/address/street, person, book/title, book/author/lname, book/date [ person/fname, person/lname, person/address, person/address/street, person/address/town, book/title, book/author, book/author/lname, book/date ]). An XTuple refers to nodes and can be perceived as an index of XML trees. Processing through references computed once is much more efficient than processing the trees through direct navigation.

Figure 2 .

 2 Figure 2. Example of an XRelation

Figure 3 .

 3 Figure 3. An example of XProject operation

Figure 4 .

 4 Figure 4. Schema and distribution of data

  for $n in Collection("*")/nation where contains ($n/comment, "iron") return <nation> <name>{$n/name}</name> <suppliers> for $s in Collection ("*")/supplier, $ps in Collection ("*")/partsupp where $s/id/suppkey = $ps/suppkey and $ps/availqty > 45 and $s//nationkey = $n

  for $n in Collection("*")/nation where contains ($n/comment, "iron") return ($n/nationkey, $n/name) Elementary query 2 let t2 := for $t in $t1; $s in Collection ("*")/supplier, $ps in Collection ("*")/partsupp where $ps/availqty > 45 return($s/contact/localisation/nationkey,$s/id/suppkey,$s/name,$s/contact/phone, ($ps/suppkey , $ps/partkey, $ps/supplycost)

  for $n in Collection("*")/nation where contains ($n/comment, "iron") return ($n/nationkey, $n/name) -Atomic Request t2 let t2 := for $s in Collection ("*")/supplier return($s/contact/localisation/nationkey,$s/id/suppkey,$s/name, $s/contact/phone) -Atomic Request t3 let t3 := for $ps in Collection ("*")/partsupp where $ps/availqty > 45 return ($ps/suppkey , $ps/partkey, $ps/supplycost) -Global Request for $n in t1, $s in t2, $ps in t3where $s/id/suppkey = $ps/suppkey and $s/ /nationkey = $n/nationkey return($n/name,($s/name,$s/contact/phone, ($ps/partkey, $ps/supplycost)))

Figure 7 .

 7 Figure 7. Execution time for each step Figure 8. Execution time of init steps

Figure 9 .Figure 10 .

 910 Figure 9. Execution time on M0, M1, A3

  for $L in collection("LINEITEM"), $O in collection("ORDERS") where $O/orderkey = $L/orderkey and $L/orderkey < N


G Gardarin
email: georges.gardarin@e-xmlmedia.fr

A Mensch

T Tuyet Dang-Ngoc

L Smit

Integrating Heterogeneous Data Sources with XML and XQuery

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 e-XMLMedia 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. Further, we evoke the various applications that are currently being experimented with the e-XMLMedia Mediator.

Introduction

In recent years, there have been many research projects focusing on heterogeneous information integration. Typical information integration systems have adopted a wrappermediator architecture [START_REF] Wiederhold | Intelligent Integration of Information[END_REF]. In this architecture, mediators provide a uniform user interface to query integrated views of heterogeneous information sources. Wrappers provide local views of data sources in a uniform data model. The local views can be queried in a limited way according to wrapper capabilities. Well-known research projects and prototypes based on this architecture include 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] and Yat [START_REF] Cluet | Your Mediators Need Data Conversion[END_REF]. While in the 90's most studies were based on using the object model as data integration model, the focus has come to XML as pivot model at the beginning of the new century.

The advantages of XML as an exchange model, (i.e., it is rich, clear, extensible and secure), makes it the best candidate for supporting the integrated data model. In addition, using XML views for local data sources hides the local specificities of each system. Furthermore, the richness of the XML schema model simplifies wrapper mappings. Also, the emergence of XQuery as a powerful universal query language for XML makes it possible to query XML global and local views in a uniform way based on a standard interface. Thus, these advantages explain that several research projects have emerged to query in a uniform way heterogeneous data sources based on XML as exchange model, see for example [START_REF] Christophides | On Wrapping Query Languages and Efficient XML Integration[END_REF][START_REF] Manolescu | Answering XML Queries over Heterogeneous Data Sources[END_REF][START_REF] Shanmugasundaram | Querying XML Views of Relational Data[END_REF].

e-XMLMedia is providing one of the first products based on XML to integrate heterogeneous data sources, namely the e-XML Mediator. The mediator (with the associated wrappers) provides the required functionalities to query in a uniform way heterogeneous data sources. It is a sophisticated component composed of several packages in charge of decomposing queries into mono-source subqueries, efficiently shipping local sub-queries to data sources, getting results in XML through a SAX interface, processing and assembling them. Queries as well as sub-queries are expressed in XQuery. In addition, capabilities are associated to wrapper so that the mediator sends only supported queries to wrappers. In summary, the mediator uses XML to represent disparate data in a common format and create a unified view of that data. Using advanced distributed query processing technology, the mediator provides an application with the services it needs to integrate on demand heterogeneous information.

This paper gives an overview of the e-XML Mediator. The next section focuses on the middleware objectives. Then, we briefly describe the system architecture. In section 4, we give an overview of the unique query processing technology embedded in the component. In conclusion, we focus on typical applications for the mediator.

Mediator Functional Objectives

The mediator is a data integration middleware receiving XQueries from user applications and returning XML. Internally, XML is managed as event flows using SAX. In an effort to broaden the interoperability of products in this market segment, e-XMLMedia has defined a standard XML XQuery API for the access to XML based data products, called XML/DBC. The XML/DBC API consists of two closely related APIs. The Java API is a JDBC extension to query XML collections using XQuery. The Web Services API is based on SOAP and is designed to provide a SOAP style server interface to clients. Thus, the mediator as well as other e-XMLMedia products, receives queries through its XML/DBC API either from SOAP client or from Java clients.

The mediator objectives are summarized in the following sections.

Querying heterogeneous data sources

The mediator provides views of sources containing collections of XML documents that can be queried through XQuery, the W3C emerging standard. It takes into account the capabilities of the data source, to avoid sending not executable sub-queries to a source. Each data source is encapsulated within a wrapper that supports at least a subset of XQuery. Ideally, a wrapper can provide mapping functionalities as XML views to achieve local mappings of data and metadata.

Querying distributed data sources

The data sources can be distributed on various sites interconnected through intranets or the Internet. Various interconnection protocols can be supported, including HTTP, IIOP and, at a higher level, RMI and SOAP. A mediator can appear itself as a data source, thus allowing several layers of mediation.

Composing data from distributed sources

Each wrapper and the mediator itself support XQuery and provide XML results. The data from the sources can be combined using various operations such as union, cross product, join, fusion, reordering, nesting and arranged to comply with the requested output defined in the return clause of the XQuery.

Processing queries in an efficient way

Queries are decomposed in optimal monosource sub-queries and global query plans are optimized in a simple but efficient way. Simple heuristics are supported in a version 1, while cost-based query optimization should be introduced in the future. Heuristics include the XML counter-part of classical relational detachment of selections and semi-join transformations.

Efficiently caching metadata

To discover relevant sites for a query and decompose it, metadata are maintained describing the sources. At mediator start, only first level metadata are brought in main memory. These metadata are given to the mediator through a configuration file. Further metadata are searched on demand through a wrapper interface and kept in cache on a last recently used basis.

Supporting efficiently multiple users

Multiple users are able to process queries in parallel with little overhead due to query processing sharing and multi-threading. The mediator is multi-threaded and manages multiple connections to data sources.

Mediator architecture

The mediator architecture is represented in Figure 1. The XML/DBC API is the only interface with external components. Thus, notice that the mediator ships requests to wrappers through XML/DBC and thus get results through it. This makes possible for a mediator to see another mediator as a wrapper. Futhermore, results are supplied in XML/DBC through SAX readers. Thus, flows of events are transferred between mediators and wrappers, avoiding the overhead generated by the allocation of intermediate memory structures.

The major sub-components are the XQuery parser, the metadata manager, the query evaluator, the query decomposer, and the result reconstructor. They are briefly described below.

XML/DBC API

This is a common API for both the mediator and the wrapper to receive external queries and ship XML results. This interface provides functions to manage components (start and stop a connection) and to retrieve data or meta-data.

Parser

The parser parses the query and generates the query structure if the query is syntactically correct. Otherwise, it returns a documented error.

Canoniser

The canoniser normalizes the query and generates a query in canonical form. Canonization consists in extracting simple queries from the external query and in building the encapsulating global query, which is composed of a tagging operator and may include specific nesting and aggregation operators.

Decomposer

The decomposer decomposes each simple query in atomic queries, according to the data localization, which is extracted from the metadata. In general, the decomposition moves further operators in the global query.

Optimizer

The optimizer identifies the relevant data sources based on metadata and create an execution plan for the query. The execution plan is composed of operators of a specific algebra designed for XML. Simple optimizations of the query plan are performed in the current version, but more complex ones are planned based on a cost model. For example, the optimizer groups the operators which refers the same source in a single query for shipping once. It also orders the global operators according to query heuristics and finally selects the best processing method (parallel, sequence or pipeline) for global operators.

Executor

The executor is in charge of shipping the subqueries to the wrappers using XML/DBC and collecting the results in cache memory. In general, results are not fully instantiated in main memory but SAX events are produced and directly processed by the evaluator when possible. We represent each ordered collection of XML tree shipped from a wrapper as an Xtuple, i.e., a tuple of references to forest of XML trees instanciated in cache.

Evaluator

Based on the query plan, the evaluator evaluates the remaining global query and applies the algebraic operators in main memory. We use a specific algebra designed for processing Xtuple. The operators are able to perform XPath-based projection, restriction, product, join, grouping, sorting, union, intersection and difference of ordered collections of Xtuples. For each operator, we implement one or more specific algorithms. For example, several global join algorithms are possible. The evaluator may work with intermediate collections fully stored in main memory, but can also work on a SAX flow of events, thus implementing pipelining and hash joins. Dependent join algorithms requesting Xtuple to one source and querying the other based on the results are also possible.

Reconstructor

It applies the result generation part of the global query to the intermediate results generated by the evaluator and the sources to construct the final result. Finally it tags the results in the required way and built the SAX event flow.

Metadata manager

This package manages the schemas of all registered sources. Further, for each source, it maintains the collection names with the associated queryable path set. The path set is a kind of data-guide giving an overview of all path instantiated in the source. If a path is not given, it will not be queried. The path set has to be given by the wrapper when registering the source (on command XDescribe).

Query processing

Globally, queries are normalized, i.e., transformation rules are applied to eliminate nested queries and replace them by several mono-bloc queries. Next, canonization is applied, which transforms a query in subqueries nested in a reconstruction operator. Each sub-query is in turn divided in atomic query, one for each relevant source. Local subqueries are processed in one or multiple shots according to wrapper capabilities and shipped to local wrappers. Results are then post-processed to compute the global answer based on our XML algebra. Finally, a reconstruction process applying a tagging operator completes the query processing steps.

Canonical queries

There exist several forms of queries. External queries are any queries that can be issued by a user. Simple queries are the XML counterpart of SPJ queries in relational systems, i.e., queries performing selections and joins over collections of XML trees, but returning tuples as results. They are of the form: for X1 in P1, X2 in P2, … Xn in Pn where Condition(X1, X2, …Xn) return Tuple(X1, X2, …Xn) where the Xi's are variables, the Pi's are simple path expressions, Condition a logical expression constructed from the Xi's and usual comparison operators, Tuple a simple constructor of Xi's tuples. The result of such a query can be stored in a temporary table of schema [X1, X2, …Xn]. Note that depending on the data sources and path expressions, the Xi's can range in complexity from atomic values to complex XML sub-trees.

Canonical queries are more complex and have the same selection power of external queries, but they are arranged as flat queries without imbrications giving Xtuples as results. They are more complex than simple queries as they can include aggregates and functions. They are nested in a global query that performs result reconstructions. For distributed queries, the global query may also include distributed joins and aggregate computations and in general algebraic operators. After completing the distributed processing, the global query processes the results of the nested queries to perform result restructuring as derived from the XQuery return clause.

Query rewriting

Atomic queries are queries involving a single collection. Notice that atomic queries may refer to several XPath expressions on the same collection. Atomic queries are simple queries, but simple queries are in general not atomic, as they may involve several collections. They are introduced for processing localization of data.

Internally, two data structures are manipulated for representing queries: The request structure is the result of parsing. It is a parse tree representing the query, which is supported by a complex main memory structure. A query plan is a tree of algebraic operators representing the query to be shipped to local sources and a global query to evaluate locally. The query plan could be enriched in the future with annotations of operators, at least at the level of the global query, e.g., to indicate pipelined hash-join, dependant join, etc.

Query plan optimization

The query processing component is composed of several packages in charge of decomposing XQuery queries into mono-source sub-queries, efficiently shipping local queries to data sources, gathering results, processing and assembling them. In particular this component chooses an execution strategy for the query.

The Mediator makes three key decisions during query processing. First the Mediator determines the localization of the relevant sources to process a query among those accessible by the Mediator. Using the metadata information on each data source, the location of data that appears in a query is determined. Second the Mediator determines the amount of sequential or parallel execution that occurs during execution. The mix between parallel and sequential is determined by the binding relationship between different data sources as expressed by join predicates. Independent data sources are contacted in parallel. Dependent data sources are accessed in a pipelined fashion. Third, the Mediator determines the amount of query processing that can be offloaded onto the data source. This determination is the result of a comparison of the requirements of a particular query and the query processing power available to a data source.

Further, the mediator creates query plans that are trees of XML algebra operators. It also executes them. As explained above, these operators process collections of Xtuples. They can be re-ordered in query plans according to equivalence rules derived from the relational algebra and from specific navigation rules. Each operator can have several implementations. Thus, generating the best query plan for a request is a complex problem. A cost-based solution has been designed but only simple heuristics are implemented so far.

The Mediator also provides a way to structure the result in an integrated XML document, according to the RETURN clause of the query. The three main facilities provided at this level are the following:

-Renaming Tags;

-Changing the initial data structure; -Composing results when coming from multiple data sources.

Wrapping Data Sources

Data sources are managed through an XML based configuration file. Data sources are wrapped with a standard interface. They are distinguished as wrapped relational data sources, wrapped XML data sources not supporting complex queries other than selections, and XML Repositories supporting XQuery via the XML/DBC interface. Wrappers are available for SQL (object-relational DBMS accessed through JDBC), XQuery (Repository and Mediator), and HTML pages. Specific wrappers can be added; they have to comply with the XML/DBC interface and define their capabilities as a class.

Metadata management

If the Mediator did not have knowledge about where to find data relevant to a given query, it would have to scan all the registered data sources. This would not be acceptable in terms of performance, as this scan should have to be done each time a query is processed. The solution to this problem is to maintain metadata describing the sources. When a source is registered with a mediator, the mediator asks for the source metadata. The metadata must be passed to the mediator as an XML document containing the source schema. Metadata are used to determine the location of data on the sites, both to identify and ship every subpart of the request to the appropriate gateway. They are also used to retrieve for the user the metadata structure available for requested objects. If metadata are modified in a source, the metadata associated with the source must be refreshed.

Figure 1 -

 1 Figure 1 -Overview of the mediator architecture

Typical applications

Several applications are currently built using the e-XML Mediator. A simple kind of application is the publishing of relational data as integrated data in XML. We packaged our XML/DBC wrapper for object-relational databases as a component marketed under the name XMLizer, to transform any relational source in an XML data source supporting XQuery. For example, the XMLizer is a key component in several database interchange, XML EDI and XML portal applications. More complex applications using the Mediator include portals for querying multiple heterogeneous databases. We have also developed applications in cooperation with European partners for a tourism Web site federating multiple data sources, for a virtual hospital federating patient dossiers constituted from several pieces, and for an active document publisher composing documents from several sources including databases and reports. In general, the mediator is ideal for extracting and composing disparate information as unique XML documents. Coupled with the other products of e-XMLMedia, XML Repository and XForms Engine (XFE), the Mediator and XMLizer are ideal to develop gateways between existing information systems and new XML consuming applications.


Tuyet Tram

Dang Ngoc

Dominique Laurent

Virginie Sans

On the Maintenance of Materialized XML Views

Providing services by integrating information available in web resources is one of the main goals of a mediation architecture. In this paper, we consider the standard wrapper-mediator architecture under the following hypothesis: (i) the information exchanged between wrappers and the mediator consists in XML documents, (ii) wrappers have limited resources, and (iii) to answer queries even if sources are not available, materialized XML views are stored at the mediator level. In this setting, we focus on the problem of maintaining materialized XML views, when the sources change. In our context, wrappers send the updated document without providing any information about the type and the localization of the update in the document. Then, the problems we address are, first, identifying the updates, and, second, updating the view in such a way that accesses to the sources are restricted. Our approach is based on the XAlgebra, which allows to consider XQuery requests on XML documents as relational tables. Moreover, our solution uses identifier annotations for XAlgebra and a diff function.

Introduction

The issue of integrating heterogeneous and distributed data has been adressed in [START_REF] Wiederhold | Mediators in the Architecture of Future Information Systems[END_REF] by means of mediation architectures. Given heterogeneous and distributed data sources to be integrated, a mediation architecture roughly consists of two components: wrappers and a mediator.

Each wrapper is associated to a given data source and is in charge of (i) extracting information from this source, (ii) transforming this information in an appropriate format understandable by the mediator, and (iii) sending the transformed information to the mediator.

On the other hand, the mediator integrates the information coming from the wrappers and provides the result to the final application. In order to make mediation architectures dealing with web sources efficient, the following issues have to be investigated further:

1. Accessibility of the data. On the web, data may not be reachable, and thus accessing the sources as few as possible is important. This is why, we propose a mediation architecture in wich materialized views stored at the mediator level are used. In this way, queries are addressed to the mediator (instead of being addressed to the sources). However, this implies that the views be mantained up to date, which is precisely one of the topics of the paper. 2. Querying the web sources. When querying a web source, the answer is the whole content of the source. In other words, for such queries, there is no query language allowing to answer sophiticated queries, as for instance, SQL which allows to query a part of a database. As a consequence, we consider in our approach that, for each access to a data source, we get the whole content of that source. 3. Non cooperative mode. Since web sources are autonomous, they use a push model to notify about their changes. This means that we can only assume that a wrapper knows that its associated source has changed, without any further information on the type or the localization of the change. In this paper, we propose a method for update detection that computes the needed information for the maintenance of materialized views.

Summing up the contributions of our work, we propose an approach to integrate efficiently heterogeneous and distributed web sources under the following assumptions: (i) the web sources are integrated through materialized XML views that are defined by an XQuery request and stored at the mediator level, and (ii) wrappers have limited computational resources, meaning in particular that data sources cannot be duplicated at the wrapper level.

As mentioned above, in such a mediation architecture, querying the sources amounts to querying the materialized views, thus avoiding to access the sources. However, it is well known that the price to pay with such an approach is that materialized views must be maintained up to date. Our approach to maintain the materialized views up to date follows an incremental processing, as in [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF], which is based on the XAlgebra, introduced in [START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF]. The XAlgebra allows to represent an XML document as a relational table, called XRelation, on which relational operators, called XOperators, are applied. In this setting, a materialized view is seen as an XRelation, on which updates are performed in response to updates on the data sources.

On the other hand, as stated earlier (see item 3 above), the sources do not provide complete information about their changes. Since this information is necessary to maintain the views, we present an approach of update detection that can be summarized as follows:

When the wrapper is informed that a source has been updated, it sends the whole content of the source to the mediator. Since at the mediator level, the definitions of the views are known, the part of the source used to compute the view can be recovered as an XRelation, say X. Consequently, by applying a standard diff function on X and the new state of the source sent by the wrapper, the mediator can identify the type and the localization of the update.

It is important to note that, in our approach, we annotate components of the tuples in XRelations with identifiers, that we call XTIDs. We also would like to emphasize that, in our approach, the computation of the part of the source used in the materialized view, allows for an efficient maintenance, since, except in restricted cases, this information prevents from accessing the data sources.

The maintenance of materialized views in the case of relational databases has been the subject of many research works these last decades, and regained interest recently in the context of relational data warehouses, that are based on a mediator/wrapper architecture (e.g. see [START_REF] Laurent | Monotonic complements for independent data warehouses[END_REF]). However, although our approach is based on a relational representation of XML documents, relational approaches do not apply in the case of semi-structured data, because, for instance, multivalued attributes are considered in our case.

On the other hand, techniques specially designed for semi-structured data have been introduced in the literature. For example, in [START_REF] Abiteboul | On views and xml[END_REF], the maintenance of materialized views is studied in the Object Embedded Model (OEM) and in the context of the language Lorel, for views that are defined with selections, projections and joins. However, the process in [START_REF] Abiteboul | On views and xml[END_REF] is based on the fact that internal Ids are available, which is not the case for autonomous web sources.

In the Rainbow project [START_REF] Ei-Sayed | An algebraic approach for incremental maintenance of materialized xquery views[END_REF], the authors consider the query language XQuery as we do, but their approach requires to know the exact position in the XML tree where the update should be done. We recall that, in our approach, we assume that this information is not provided by the source.

A closer approach to ours is given in [START_REF] Cobena | Detecting changes in xml documents[END_REF]. This work gives a solution for the maintenance of materialized views defined over non cooperative sources. However, this work differs from ours, because in [START_REF] Cobena | Detecting changes in xml documents[END_REF], wrappers are assumed to store a complete copy of the source, whereas in our work, when the wrapper detects a change, the complete source is sent to the mediator.

The paper is organized as follows. The next Section 2 introduces the main concepts of the mediation architecture we consider in our work and the XAlgebra. Section 3 presents our update detection mechanism, and Section 4 deals with the view update processing. Finally, Section 5 concludes the paper.

Background

Mediation Architecture

According to [START_REF] Wiederhold | Mediators in the Architecture of Future Information Systems[END_REF], the major two components of a mediation architecture system are: (i) a mediator and (ii) wrappers, each of which being associated with one source. Among all the available platforms for mediation, we consider in our work, the XLive architecture, first proposed in [START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF].

In its current state, the mediation architecture XLive does not support materialized XML views. To do so, the following components have to be added:

-A local XML database at the mediator level. The materialized XML views we consider are stored at the mediator level in an XML database than can support view materialization. -A view manager at the mediator level. This component is meant to allow the mediator to partially reconstruct the sources, and to compute the XQuery requests necessary to the maintenance of the views. -A notification component at the wrapper level. Usually, a wrapper is simply a translator, whereas, in our approach, a notification component, which we call logger, is needed in order to detect updates in the source. We recall in this respect that, upon changes on a source, the corresponding wrapper sends the modified document to the mediator.

This architecture, that we are currently implementing, is shown in Figure 1.

XAlgebra

To query an XML document, many languages have been proposed such as Lorel ( [START_REF] Abiteboul | The Lorel Query Language for Semi-Structured Data[END_REF]), XML-QL ( [START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF]) or XQuery ( [START_REF] W3c | An XML Query Language (XQuery 1.0[END_REF]). In our work, we consider the language XQuery as this language provides more possibilities than the others. Moreover, in [START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF], it has been shown that an XQuery request can be associated with an expression from an algebra, called the XAlgebra, which is based on relational operators designed for XML. In [START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF], this algebra has been used to construct execution plans for the evaluation of XQuery requests. In our work, we consider the XAlgebra for the maintenance of materialized XML views.

Roughly speaking, the XAlgebra is a set of operators, called XOperators, inspired by those from the standard relational algebra, that operate on "tabular" structures called XRelations. In what follows, we recall the basics of XRelations and of the XAlgebra.

XRelations An XRelation is composed of two distinct parts called the XAttributes Part and the Trees Part, respectively. In the Trees Part, the domain is a set of XML trees of given path sets. In the XAttributes Part, attributes, called XAttributes, are XPaths and their respective domains are sets of references to XML trees.

Fig. 2. XML Tree

Contrary to standard relations, each XAttribute can be multi-valued (when referencing several sub-trees), or empty (when referencing no subtree). Moreover, XTuples in an XRelation are stored according to a specific ordering that reflects the structure of the corresponding subtrees: if an XTuple x appears before an XTuple y, then, in the XML tree, the subtree corresponding to x appears on the left hand side of the subtree corresponding to y. Thus, XRelations are seen as ordered collections of XTuples, where each XTuple is:

an XML tree, say t, in its Trees Part, and a tuple of sets of reference to subtrees of t, in its XAttributes Part.

As a result, the schema of an XRelation R is of type (XP ath + , [P ath + ]), where XP aths are the XAttributes and P aths compose the path set of the corresponding XML tree.

Figure 3 shows an XRelation with two XTuples that have been obtained from the XML tree of Figure 2. We note that the second XAttribute is multivalued in the first XTuple, whereas this XAttribute is empty in the second XTuple. For the sake of lisibility, we simply write XTuples as ordered sets of values, ignoring references. It is important to note that this simplification implies that we consider the values in the leaves of trees.

XOperators The subset of relational XOperators from the XAlgebra considered in this paper is limited to the following ones: union, intersection, projection, restriction, join, and cartesian product.

These operators are defined in a similar way as in the relational algebra, we refer to [START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] for more details. However, it is important to note that, the above simplification implies that we consider duplicates in XRelations.

Furthermore, the XAlgebra contains two specific operators, called XSource and XConstruct, that work as follows, respectively:

-Given an XML document, the operator XSource transforms the content of the source into an XRelation. -Given an Xrelation, the operator XConstruct transforms the XRelation into an XML document. Now, given a view V defined as an XQuery request over data sources, V can be seen as an expression of the XAlgebra, using XOperators. As a consequence, the answer to V , which is an XML document, can be seen as an XRelation.

In Figure 4, the computations of this XRelation and of the answer to V are represented in the particular case where V is defined over one single source (the case of more than one source is similar). Moreover, in this figure, the star associated with the grey box represents the fact that more than one XOperator can be used in the computations. The process of these computations works according to the following steps:

1. All sources involved in the XQuery defining V are transformed into XRelations, using the XSource operator. 2. The analysis of the XQuery request defining V allows to define an expression of the XAlgebra involving only XOperators among union, intersection, projection, restriction, join and cartesian product. This expression is computed against the XRelations obtained at the previous step. 3. The XRelation output at the previous step is transformed into an XML document, using the XConstruct operator.

Mandatory, Optional and Hidden Paths

The XQuery syntax allows us to distinguish three kinds of paths, namely the mandatory paths, the optional paths, and the hidden paths. Given a view V defined by an XQuery request Q, these kinds of paths are defined as follows:

-Every path appearing in the return clause of Q is said to be optional.

-Every path appearing in the where clause of Q is said to be mandatory.

-Every path that is mandatory but not optional is said to be hidden.

Intuitively, hidden paths are those that are necessary to compute the answer to Q but that do not appear in the answer. It is important to note that hidden paths are necessary in our method for maintaining materialized views. Therefore, in our approach, hidden paths are stored but not displayed when the view is queried.

As an example, let us compute the following XQuery request Q on the XML document represented in Figure 2. 3, the corresponding column is displayed as a grey colomn.

FOR $i

Update Detection and Reconstruction

As mentioned earlier in the paper, we consider autonomous data sources associated with light wrappers that just send the updated document to the mediator, without providing any further information about the type and localization of the update in the document. In this case, in order to maintain materialized views, we have to identify the update. We note in this respect that the approach of [START_REF] Cobena | Detecting changes in xml documents[END_REF] does not meet our restriction that wrappers have limited computational resources, since in [START_REF] Cobena | Detecting changes in xml documents[END_REF], sources are duplicated at the wrapper level.

In our approach, the logger component of the wrapper is in charge of checking whether the source has changed. This can be done by computing a checksum on the source and comparing the value with a previous computed checksum. If the two values are different, then the source has been modified, and in this case, the content of the source is sent to the mediator.

Next, we show how the mediator can precisely determine which update has been performed on the source. Our method is based on the facts that (i) we associate XTuples from the sources with identifiers, called XTIDs, and (ii) the parts of the sources that have been used in the computation of the view can be reconstructed, based on XTIDs and on the expression of the XAlgebra that defines the view.

XTID Identifiers

Let X be an XRelation associated to an XQuery request Q. We associate each set of pointers in any XTuple in X with a set of identifiers called XTIDs. The role of XTIDs associated to a set S of pointers is to identify the sources and the tuples in these sources pointers in S come from.

An XTID is a pair (s, id), where s is a source identifier and id the XTuple identifier from source s. Let x = (x 1 , . . . , x p ) be an XTuple in X, and let P k be the XPath associated to x k , for k = 1, . . . , p. Assume that x is obtained as a combination of x 1 , . . . , x n where, for every j = 1, . . . , n, x j is an XTuple from the XRelation X j associated to source j. Then, for every k = 1, . . . , p, x p is associated with a set of TIDs as follows:

For every k = 1, . . . , p such that P k occurs in the XPaths that define x j , the XTID (j, id) is inserted into the set of XTIDs associated to x k .

It is important to note that id is a unique identifier associated with x j , which implies that duplicate XTuples have distinct XTIDs. On the other hand, recalling that an XRelation is an ordered collection of XTuples, the assignment of XTIDs from a given source is done in such a way that their ordering matches the storage ordering in the XRelation. In other words if, for a given source, XTuple x appears before the XTuple y in the corresponding XRelation, then the identifer assigned to x is smaller than the identifier assigned to y. Moreover, once such XTID is fixed for each XAttribute of each XTuple, it cannot be changed by any computation applied to the XRelation.

Figure 5 shows the annotation with XTIDs for the XRelation of Figure 3. For instance, with the source 1 and the first fragment, the XTuple is associated to XTID [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Wiederhold | Mediators in the Architecture of Future Information Systems[END_REF].

John

Reconstruction

Let Q be an XQuery over sources S 1 , S 2 , ..., S n , and let V be the corresponding expression of the XAlgebra. Let us denote by X 1 , X 2 , ..., X n the XRelations generated by the application of the operator XSource to S 1 , S 2 , ..., S n , repectively, and let X be the XRelation associated to V .

In what follows, we consider V as a mapping, denoted by v, that associates n XRelations to one XRelation. Thus, using our notation, we have v(X 1 , X 2 , ..., X n ) = X.

As shown below, our reconstruction method is based on the inverse of v.

For a given integer σ in {1, . . . , n} identifying a data source involved in the computation of V , let us denote by v -1 σ (X) the set x∈X v -1 σ (x). Intuitively, v -1 σ (X) is the part of the original XRelation associated to the source σ, that has been used in the processing of the view. In the remainder of the paper, v -1 σ (X) is called the useful part of the XRelation X σ . Let us consider an XTuple x = (x 1 , . . . , x m ) in the XRelation X. Then, for every k = 1, . . . , m, x j is of the form c XT ID where c is the content value, and XT ID = {xtid 1 , xtid 2 , ..., xtid p } is the set of XTIDs associated to c.

For every k = 1, . . . , m, xtid k can be written as xtid k = (s k , i k ), where s k is a source identifier and i k an XTID associated with an XTuple in s k . The XRelation v -1 σ (X) can be computed from the XRelation X, using the following rules:

-Rule 1. If XT ID contains a pair (σ, i), then c belongs to a tuple in v -1 σ (X). -Rule 2. For all k, l in {1, . . . , m}, if XT ID k ∩ XT ID l contains a pair (σ, i),
then c k and c l belong to the same XTuple in v -1 σ (X). -Rule 3. For every k in {1, . . . , m}, every s k appearing in the set XT ID associated to c k XT ID , the column number of the corresponding tuple containing c k in the source s k can be retrieved by comparing the positions of the XPaths occurring in the for and return clauses of the XQuery request Q that defines the view.

-Rule 4. Given a source σ and an XTuple x = (c 1 XT ID1 , . . . , c mσ XT IDm σ ) computed by rules 1-3 above, if there exist i and j such that (σ, i) ∈ c k XT ID k and (σ, j) ∈ c l XIT D l , then i = j. This value is denoted by row(x, σ). If x and x ′ are two XTuples such that row(x, σ) ≤ row(x ′ , σ), then x is inserted in v -1 σ (X) before x ′ . Figure 6 shows an example of the previous rules applied on two data sources S 1 and S 2 and the following XQuery request: for $n in document ("note.xml")/note for $p in document ("person.xml")/person where $n/name = $p/name and $age >= 18 return <result> {/p/age} {/p/name} {/n/note} </result>

The view computation box shows the computation of the view from the XRelations generated by XSource applied to S 1 and to S 2 . On the other hand, the source reconstruction box shows the four steps for reconstructing the useful part of source S 1 .

-Rule 1: Only values concerned by source S 1 are kept. [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] 23 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF] 18

Recomputation

Computation View 7,1 (1,1) pierre (1,1) (2,6) 8,5 (1,2) paul (1,2) (2,3) 9,2 (1,4) martin (1,4)
(2,3) pierre (1,1) (2,6) paul (1,2) (2,3) 21 (2,5) 18 (2,4) martin (1,4) (2,4) jean (1,5) (2,5) 7,1 (1,1) 8,5 (1,2) 9,2 (1,4) 9,2 (1,5)
18 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] 18 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Abiteboul | The Lorel Query Language for Semi-Structured Data[END_REF] 21 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] 21 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] 18 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] 18 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Abiteboul | The Lorel Query Language for Semi-Structured Data[END_REF] 23 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF] 9,2 [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] martin

(1,4) (2,4) 9,2 (1,5) jean (1,5) (2,5) 8,5 (1,2) paul (1,2) (2,3) name score 7,1 (1,1) pierre (1,1) (2,6) 7,1 (1,1) 9,2 (1,4) 9,2 (1,5) 8,5 (1,2) 7,1 (1,1) 9,2 (1,4) 9,2 (1,5) 8,5 (1,2)
martin [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] paul (1,2) [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Abiteboul | The Lorel Query Language for Semi-Structured Data[END_REF] jean [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] jean [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] martin [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] paul [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF] [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Abiteboul | The Lorel Query Language for Semi-Structured Data[END_REF] pierre (1,1) [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF] 9,2 [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] 23 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF] 21 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] 17 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Abiteboul | On views and xml[END_REF] 18 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] 18 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Abiteboul | The Lorel Query Language for Semi-Structured Data[END_REF] 23 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF]

pierre (1,1) (2,6)
(1,2)

(1,3) (1,4) (1,5) (1,5) (1,5) (1,4) (1,4) (1,3) (1,3) (1,2) (1,2) (1,1) (1,1)
23 [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF]

21

(2,5)

18

(2,4)

18

(2,3)

22

(2,2)

17

(

paul (1,2) (2,3) score 9,2 (1,4) 7,1 (1,1) 8,5 (1,2) 9,2 (1,5) score 9,2 (1,5) 8,5 (1,2) 7,1 (1,1) 9,2 (1,4)
name name jean (1,5) [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] martin

(1,4) (2,4) pierre (1,1) (2,6) paul (1,2) (2,3) jean (1,5) (2,5) name group a b b a a (1,1) (1,2) (1,3) (1,4) (1,5)
pierre [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Abiteboul | On views and xml[END_REF] paul [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF] jacques [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Abiteboul | The Lorel Query Language for Semi-Structured Data[END_REF] martin [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] jean [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] (2,6)

(2,5) (2,4) (2,1)
(2,3) age score 7,1 8,5 8,5 9,2 9,2 Finally, the useful part of S 1 has been reconstructed.

(1,5) (1,4) (1,3) (1,2) (1,1)

Update Detection

In this subsection, we use the same notation as in the previous sections, and we suppose that the wrapper associated to the source σ detects a change in σ.

As explained earlier, the wrapper sends the updated content of σ, without any further information. Consequently, the XSource operator is applied and then, based on the XAlgebra expression V , an XRelation Y σ associated to this new version of the data source can be computed.

In order to detect which updates have to be performed on the XRelation X, v -1 σ (X) is computed using the previous reconstruction rules. Then, we use the diff operator on v -1 σ (X) and Y σ to identify the differences between these two XRelations.

The diff operator, introduced in [START_REF] Hunt | An algorithm for differential file comparison[END_REF], is an algorithm that has been initially designed for comparing lines of two files. In our setting, the result of the algorithm is a set of update instructions, that an have one of the following three forms: delete(pos), insert(pos, new) or replace(pos, new), where pos is a row number indicating the row that has to be deleted, inserted or modified, respectively, and where new is the new tuple to be taken into account for the insertion or the modification.

The next section describes for each type of update and for every relational XOperator (projection, restriction, join, union, intersection), how to update the view.

In Figure 7, we show how, starting from the XRelation X, and applying the reconstruction rules as explained in the previous subsection (also shown in Figure 6), we can get the update notification by using the diff operator. Then, by applying these updates to the XRelation X as described in next section, we get the updated view.

Computation of the XQuery Update Request

Let X be the XRelation associated to the view defined by an XAlgebra expression V , and let us assume a change on source σ, specified as indicated in the previous section. In this section, we show how to update X, for each type of update (deletion, insertion or modification), and in the case where only one of the operators of projection, restriction, join, union or intersection appears in V .

We note that, in the case of insertion or modification, if in the XPaths that define the XTuple new, at least one mandatory XPath is missing, then no update has to be performed in X. Intuitively speaking, this is so because values over non mandatory XPaths have no impact in the computation of X. In what follows, we assume that all mandatory XPaths have a corresponding value in the XTuple new involved in the insertion or modification. [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF] jean [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] 9,2 [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] martin [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] [START_REF] Abiteboul | Incremental maintenance for materialized views over semi structured data[END_REF][START_REF] Cobena | Detecting changes in xml documents[END_REF] 9,2 [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] jean [START_REF] Abiteboul | On views and xml[END_REF][START_REF] Dang-Ngoc | Federating heterogeneous data sources[END_REF] In this case, let y XT ID be the XTuple in v -1 σ (X) such that row(y, σ) = pos, and let i be such that xtid = (σ, i) belongs to XT ID.

Then, in the final XRelation view X, all XTuples for which xtid appears among their associated XTIDs must be deleted from X. In other words, all XTuples x = (c 1 XT ID1 ...c k XT ID k ) where (σ, i) ∈ XT ID 1 ∪ ... ∪ XT ID k are deleted from X, and this applies for any of the XOperators projection, restriction, join, union and intersection.

The Case of an Insertion: insert(pos, new)

In this case, the XTuple new must be inserted at row pos in v -1 σ (X) and a new XTID of the form xtid new = (σ, l) is generated. Notice that, as ordering is important for future reconstruction (see Rule 4), the identifier l must be chosen so as it reflects the order of the XTuples in Y σ . Then, considering the XTuple new whose components are annotated by (σ, l), the following insertions are performed in X, according to which XOperator occurs in V . Projection In the case of a projection, the projection of new over the XPaths in X is inserted into X.

Restriction

In the case of a restriction, if new satisfies the restriction predicate then new is inserted into X, otherwise X remains unchanged. Join In the case of a join between sources σ and σ ′ , in order to compute the XTuples that have to be inserted into X, we calculate: v -1 σ (X) 1 new = Z. If Z = ∅, then the XTuples of Z must be inserted into X. Otherwise, that is if Z = ∅, then the source σ ′ must be queried and joined with new to get the set of XTuples to be inserted into X.

Union and Intersection Since we consider duplicates, the case of a union is treated as a restriction where the restriction predicate is true. On the other hand, the case of an intersection is treated as the case of a join.

Note In all cases above, the insertion into X is simply processed by appending the new XTuple, without any ordering consideration, unless an order-by operator appears in the definition of the view. In this case, the specified ordering is of course taken into account for the insertion.

The Case of a Modification: replace(pos, new)

As for deletions, let y XT ID be the XTuple in v -1 σ (X) such that row(y, σ) = pos, and let i be such that xtid = (σ, i) belongs to XT ID.

For every c XT ID in y that is changed by the update, the column of the corresponding tuple in X containing c can be retrieved by using the XTIDs in XT ID and by comparing the positions of the XPaths occurring in the for and return clauses of the XQuery request Q. Then, the following updates are performed, according to the operator in V .

Projection Since the XTuple and its columns to be modified are known, the modification can be performed accordingly.

Restriction As above, in the case of restriction, the modification can easily be performed, but only under the condition that the modified XTuple satisfies the restriction predicate. Otherwise, the corresponding XTuple is deleted from X.

Join The case of a join can be treated through a deletion followed by an insertion, that is we perform delete(pos) and then insert(pos, new).

Union and Intersection

As for insertions, the case of a union is treated as a restriction where the restriction predicate is true, and the case of an intersection is treated as the case of a join.

Remark We would like to end this section by pointing out that, in our approach, the maintenance of materialized XML views does not require to query the sources except in specific cases of insertions or modifications in the presence of joins or intersections. We recall in this respect that accessing the sources as few as possible is an important issue, when dealing with the integration of web sources.

Conclusion and Future Works

We have presented an approach to maintain materialized XML views by means of reconstruction of the sources, based on the content of the view only. The reconstruction aims to detect the changes in the sources, in the case where they cannot be duplicated at the wrapper level.

We are currently implementing of our method, focussing on the reconstruction module and on the management of XTIDs. Our future work will deal with other XOperations of the XAlgebra such as nesting and unnesting, and then the general case of any combinasion of XOperators will be addressed.

Fig. 1 .

 1 Fig. 1. Our framework

Fig. 3 .

 3 Fig. 3. XRelation

Fig. 4 .

 4 Fig. 4. Steps of the computation of an XQuery request

Fig. 6 .-Rule 2 :

 62 Fig. 6. Computing a view and reconstructing a source from the view

Fig. 7 .

 7 Fig. 7. Update notification and applying updates

  In this case, the XPath persons/person/city is mandatory, whereas the XPaths persons/person/name and persons/person/lastname are optional. Since person/city is mandatory but not optional, this path is hidden. In Figure

	in ("persons.xml")/persons
	WHERE $i/person/city=Berlin
	RETURN
	<result>
	{$i/person/name}
	{$i/person/car/color}
	{$i/person/car/number}
	</result>