Alexandru Marin

Caroline Chaux

Jean-Christophe Pesquet
email: jean-christophe.pesquet@univ-paris-est.fr

Philippe Ciuciu
email: philippe.ciuciu@cea.fr

IMAGE RECONSTRUCTION FROM MULTIPLE SENSORS USING STEIN'S PRINCIPLE. APPLICATION TO PARALLEL MRI

Keywords: Reconstruction, Stein's principle, wavelets, nonlinear estimation, multiple sensors, pMRI

We are interested in image reconstruction when data provided by several sensors are corrupted with a linear operator and an additive white Gaussian noise. This problem is addressed by invoking Stein's Unbiased Risk Estimate (SURE) techniques. The key advantage of SURE methods is that they do not require prior knowledge about the statistics of the unknown image, while yielding an expression of the Mean Square Error (MSE) only depending on the statistics of the observed data. Hence, they avoid the difficult problem of hyperparameter estimation related to some prior distribution, which traditionally needs to be addressed in variational or Bayesian approaches. Consequently, a SURE approach can be applied by directly parameterizing a wavelet-based estimator and finding the optimal parameters that minimize the MSE estimate in reconstruction problems. Simulations carried out on parallel Magnetic Resonance Imaging (pMRI) images show the improved performance of our method with respect to classical alternatives.

INTRODUCTION

Much attention has been paid to Stein's principle [START_REF] Stein | Estimation of the mean of a multivariate normal distribution[END_REF] in the recent statistical literature in order to derive MSE estimates in statistical problems involving an additive Gaussian noise. In particular, it was successfully used in wavelet-based nonlinear denoising [START_REF] Donoho | Adapting to unknown smoothness via wavelet shrinkage[END_REF]. More recently, such an approach was extended to deconvolution problems [START_REF] Pesquet | A SURE approach for digital signal/image deconvolution problems[END_REF][START_REF] Chesneau | Stein block thresholding for wavelet-based image deconvolution[END_REF] and it was also employed for Poisson data denoising [START_REF] Luisier | Undecimated Haar thresholding for Poisson intensity estimation[END_REF]. The key advantage of Stein's principle [START_REF] Raphan | Learning least squares estimators without assumed priors or supervision[END_REF] is that it does not require prior knowledge about the statistics of the unknown image. Hence, it allows us to circumvent the difficult problem of the estimation of the hyperparameters of a prior distribution as frequently encountered in Bayesian approaches.

In this paper, we propose to further extend the scope of Steinbased approaches by addressing image reconstruction problems. More precisely, we employ Stein's principle in order to propose a wavelet-based estimator relying on Linear Expansion of Thresholds (LET) functions [START_REF] Blu | The SURE-LET approach to image denoising[END_REF][START_REF] Pesquet | A new wavelet estimator for image denoising[END_REF]. This enables us to design efficient medical image reconstruction algorithms whose parameters are optimally computed to achieve the minimum MSE. The estimator operates in the wavelet transform domain and deals with mutiple observations delivered by several sensors. The interest of this method is demonstrated in the parallel Magnetic Resonance Imaging (pMRI) context [START_REF] Pruessmann | SENSE: sensitivity encoding for fast MRI[END_REF][START_REF] Rabrait | High temporal resolution functional MRI using parallel echo volume imaging[END_REF]. Recall that this modality offers a means of significantly reducing the acquisition time at the expense of a degraded signal-tonoise ratio. In a recent work by Chaâri et al. [START_REF] Chaâri | A wavelet-based regularized reconstruction algorithm for SENSE parallel MRI with applications to neuroimaging[END_REF] a novel method based on a wavelet-based variational approach was proposed, which makes use of an iterative optimization algorithm to compute the Maximum A Posteriori (MAP) estimate. We aim here at proposing a faster non-iterative method where the estimator parameters are adjusted automatically. Note also that the proposed approach is very flexible concerning the wavelet choice and the estimator form.

The remainder of the paper is organized as follows. In Section 2, we briefly introduce the notation and describe the considered inverse problem. Then, Section 3 is devoted to the proposed statistical method. In particular, we show how to address the complex-valued nature of the data and build an unbiased quadratic risk estimator, before discussing the estimator choice. Finally, in Section 4, we illustrate the effectiveness of our reconstruction algorithm on a simulated set of pMRI data.

PROBLEM STATEMENT

Notations

We consider here pMRI images generated by considering L acquisition coils and a reduction factor R. Let X × Y be the dimensions of the full Field Of View (FOV) image, along the respective phase and and frequency directions. The reduced FOV image size in phase encoding direction is thus given by ∆X = X R . B will denote the set of spatial indices in the reduced FOV image.

Observation model

At each position x ∈ B we observe an L-dimensional data vector d(x) = [d1(x), . . . , dL(x)] ⊤ , which is obtained by applying an L × R sensitivity matrix S(x) given by S(x) = Here ρ(x) is an R-dimensional random field which is assumed to be independent of n(x). The between-coil noise covariance matrix is given by Cov {n(x), n(x

′ )} = Ψδ(x -x ′ ), ∀(x, x ′ ) ∈ B 2 .
The resulting model is consequently described by the following linear model:

d(x) = S(x)ρ(x) + n(x), ∀x ∈ B. (1)
The objective of this work is to recover ρ from d knowing S.

PROPOSED METHOD

Complex nature of the data

In MRI, the acquired data are complex-valued even if the magnitude is only considered for visualization purpose. Let •R and •I be the subscripts indicating the real and imaginary parts (namely, ℜ{•} and ℑ{•}) of the data. The observed data can thus be expressed by

» dR(x) dI(x) - = » SR(x) -SI(x) SI(x) SR(x) -» ρR(x) ρI(x) - + » nR(x) nI(x)
so that Model (1) can be reexpressed under the form

dC (x) = SC (x)ρC (x) + nC (x), ∀x ∈ B, (2)
where the involved vectors and matrices are real-valued. Assuming that we are able to compute the pseudo-inverse S † C (x) of SC (x) defined by

S † C (x) = " SC (x) ⊤ SC (x) " -1 SC (x) ⊤ , (3)
it follows that e ρC (x) = ρC (x) + e nC (x) where e ρC (x) = S † C (x)dC (x) and e nC (x) = S † C (x)nC (x). Furthermore, the following relations regarding the second-order statistics of the random field e nC (x) will be useful for the quadratic risk computation:

Cov {e nC (x), e nC (x)} = S † C (x)ΨC `S † C (x) ´⊤ (4) Cov {e nC (x), nC (x)} = S † C (x)ΨC . ( 5
)
where Cov {nC (x), nC

(x ′ )} = ΨC δ(x -x ′ ), ∀(x, x ′ ) ∈ B 2 .

Derivation of the SURELET estimator

For every x ∈ B and k ∈ {1, . . . , K}, let ϕ k (x) ∈ R 2L be an analysis vector and let e ϕ k (x) ∈ R 2R be a synthesis vector. In the case of a decomposition onto a basis of the FOV image, K = XY and the need of 2K functions stems from the fact that the real and imaginary parts of the data are considered. We choose an estimator of the form

∀k ∈ {1, . . . , 2K}, b ρ k = θ k (w k ) (6)
where w k = P x∈B ϕ k (x) ⊤ dC (x) and θ k : R → R is some differentiable estimating function (the choice of this function will be discussed in Section 3.4). Then the estimator of ρC (x) is given by

b ρC (x) = 2K X k=1 b ρ k e ϕ k (x) (7)
The objective now is to compute the estimator parameters that minimize the quadratic risk.

Unbiased risk estimate

The risk corresponding to a MSE estimation is defined as: ∀x ∈ B,

E ˘ b ρC (x) -ρC (x) 2 = E ˘ b ρC (x) -e ρC (x) + e nC (x) 2 = E ˘ b ρC (x) -e ρC (x) 2 ¯+ 2E n b ρC (x) ⊤ e nC (x) o -2E n e ρC (x) ⊤ e nC (x) o + E ˘ e nC (x) 2 ¯. (8)
Here, we focus on the second term which, by using [START_REF] Blu | The SURE-LET approach to image denoising[END_REF], reads:

E n b ρC (x) ⊤ e nC (x) o = 2K X k=1 e ϕ k (x) ⊤ E {b ρ k e nC (x)}.
In addition, applying the analysis vectors ϕ k (x) to dC (x) yields coefficients w k which can be decomposed as w k = u k + n k , where

u k = X x∈B ϕ k (x) ⊤ SC (x)ρC (x) n k = X x∈B ϕ k (x) ⊤ nC (x),
so that b ρ k can be rewritten as

b ρ k = θ k (w k ) = θ k (u k + n k ). (9)
Then, by applying Stein's principle [START_REF] Stein | Estimation of the mean of a multivariate normal distribution[END_REF], it follows that:

E {b ρ k e nC (x)} = E ˘θ′ k (w k ) ¯E {n k e nC (x)}. (10)
After some tedious calculations, it follows that the quadratic risk estimate reads:

E ˘ b ρC (x) -ρC (x) 2 ¯= E ˘ b ρC (x) -e ρC (x) 2 + 2 2K X k=1 E ˘θ′ k (w k ) ¯e ϕ k (x) ⊤ S † C (x)ΨC ϕ k (x) -tr " S † C (x)ΨC `S † C (x)
´⊤" .

An unbiased estimate of the resulting global MSE is:

b E( b ρC -ρC ) = b E( b ρC -e ρC ) + ∆ (11)
where

b E( b ρC -e ρC ) = 1 XY X x∈B b ρC (x) -e ρC (x) 2 and ∆ = 2 XY 2K X k=1 θ ′ k (w k ) X x∈B e ϕ k (x) ⊤ S † C (x)ΨC ϕ k (x) - 1 XY X x∈B tr " S † C (x)ΨC `S † C (x)
´⊤" .

Note that the risk estimate is expressed in terms of observed data only. Now, the next step consists of specifying the form of the estimating functions θ k in order to find the parameters that minimize the global error measure b E(•).

Estimating function choice

Assume that the coefficients (w k ) 1≤k≤2K are classified according to M ∈ N * distinct nonempty index subsets (e.g. wavelet subbands) Km, m ∈ {1, . . . , M }. For every m ∈ {1, . . . , M } and k ∈ Km, we choose subband-dependent estimating functions of the form:

θ k (w k ) = Im X i=1 am,i fm,i(w k ) (12)
where (am,i) 1≤i≤Im are scalar real-valued weighting factors and, for every i ∈ {1, . . . , Im}, fm,i : R → R is a differentiable function. These functions are the Linear Expension of Thresholds (LET) estimating functions introduced in [START_REF] Blu | The SURE-LET approach to image denoising[END_REF][START_REF] Pesquet | A new wavelet estimator for image denoising[END_REF] and correspond to a linear combination of Im ∈ N * given univariate functions fm,i applied to w k (note that we use the same estimating function for a given Km).

Computation of (am,i) 1≤i≤Im parameters

As mentioned earlier, we want to compute the parameters (am,i) 1≤i≤Im that minimize the quadratic risk in [START_REF] Chaâri | A wavelet-based regularized reconstruction algorithm for SENSE parallel MRI with applications to neuroimaging[END_REF]. It can be shown that this amounts to solving the following set of linear equations:

∀m ∈ {1, . . . , M }, ∀i ∈ Im, M X n=1 In X j=1 an,j X x∈B βm,i(x) ⊤ βn,j(x) = X x∈B βm,i(x) ⊤ e ρC (x) - X k∈Km f ′ m,i (w k ) X x∈B e ϕ k (x) ⊤ S † C (x)ΨC ϕ k (x)
where βm,i(x) = P k∈Km fm,i(w k ) e ϕ k (x).

SIMULATION RESULTS

Context

In our experiments, the families of analysis/synthesis functions are chosen such that

ϕ k (x) = SC (x) " SC (x) ⊤ SC (x) + λI " -1 | {z } G(x) ψ k (x) e ϕ k (x) = e ψ k (x)
where λ > 0, I is the identity matrix and the components of vector ψ k (x) (resp. e ψ k (x)) are obtained from shifted versions of a 2D separable wavelet analysis function (resp. synthesis function). A scheme summarizing the proposed reconstruction approach is given in Fig. 1.

Concerning the estimating functions, we choose Im = 2. fm,1 is the identity function and

∀ρ ∈ R, fm,2(ρ) = " 1 -exp " - ρ 8 (ωσm) 8 " « ρ
where ω ∈]0, ∞[ and σm is the standard deviation of (n k ) k∈Km . These LET estimating functions were introduced in [START_REF] Blu | The SURE-LET approach to image denoising[END_REF]. We compare our results with SENSE reconstruction [START_REF] Pruessmann | SENSE: sensitivity encoding for fast MRI[END_REF], which is based on a weighted least-squares estimator:

b ρSENSE(x) = " `S * (x) ´⊤Ψ -1 S(x) " †`S * (x) ´⊤Ψ -1 d(x).

Pointwise nonlinear estimation operator

Estimated wavelet coefficients

Wavelet decomposition

Wavelet reconstruction

Observed data

Estimated data

Operator

( e ϕ k ) k (θ k ) k dC b ρC (ψ k ) k (w k ) k (b ρ k ) k G ⊤ Fig. 1.
Flowchart of the proposed reconstruction method.

Numerical results

To assess the performance of the proposed method, we simulated synthetic data from a full FOV reference image displayed in Fig. 2(a) according to model [START_REF] Stein | Estimation of the mean of a multivariate normal distribution[END_REF]. Note that the dynamic range of the absolute value of the pixels is large.

The number of antennas is here equal to L = 8 and the reduction factor is R = 4. The covariance matrix of the noise ψ is chosen to be diagonal (no between coil correlation) and all the diagonal entries are chosen equal to σ 2 (homoscedasticity). Next, we compared our results with those provided by the classical SENSE reconstruction. Here, an orthonormal wavelet analysis (symlets of length 8) is performed on 4 resolution levels. The regularization parameter λ was chosen empirically. Typical values around 0.001 were observed to provide accurate and reliable results. The performance was measured in terms of Peak Signal-to-Noise Ratio (PSNR) as reported in Table 1. In short, our method enables a significant gain in PSNR values with respect to the SENSE approach. Interestingly, the larger the noise, the stronger the PSNR improvements we observed in favour of the proposed approach. For visualization purposes, the reconstructed images by SENSE and Stein-Let methods are shown in Fig. 2(b)-(c) when σ 2 = 5 10 6 . The main differences can be observed in the center of the images where more residual noise is found for SENSE reconstruction. Note that the Stein-LET reconstruction in Fig. 2(c) is achieved in about 15 s. on a Xeon(R) CPU X5450@3.00GHz.

CONCLUSION

We proposed a new reconstruction method based on Stein's principle and LET functions which was applied to pMRI. In this context, our approach provides more accurate results than the classical SENSE alternative. In our approach, most of the parameters are set in an unsupervised manner. In addition, the computational complexity is quite reasonable. In the future, we plan to validate this restoration method in a more realistic context i.e. without knowing the amount of noise and using an unperfectly known sensitivity matrix. Furthermore, we will consider 3D decomposition to extend the present contribution and enable the reconstruction of all slices simultaneously. It would be also interesting to apply this approach to other reconstruction strategies [START_REF] Petr | Parallel image reconstruction using B-spline approximation (PROBER)[END_REF][START_REF] Samsonov | On optimality of parallel MRI reconstruction in k-space[END_REF].

  , x2) . . . S1(x1, x2 + (R -1)∆X) . . . • • • . . . SL(x1, x2) . . . SL(x1, x2 + (R -1)∆X)

3 7 5 ,

 5 to an R-dimensional vector of pixel values in the original (unknown) image ρ(x) = [ρ(x1, x2), ρ(x1, x2 + ∆X), . . . , ρ(x1, x2 + (R -1)∆X)] ⊤ and by adding a complex Gaussian circular noise vector corrupting samples from all coils: n(x) = [n1(x), . . . , nL(x)] ⊤ .

Fig. 2 .

 2 Fig. 2. (a): Magnitude of the reference image: range in [0,91496]. (b)-(c): Magnitude of the restored images by SENSE and the proposed Stein-LET approach, respectively. (d)-(f): zoomed versions of images (a)-(c) on the central part of the brain to illustrate the noise reduction using the Stein-LET estimator.

Table 1 .

 1 PSNR values for reconstructed images (in dB).

	Method	Real Part Imag. Part Magn.
			σ 2 = 5 10 6
	SENSE	36.29	35.48	38.75
	λ = 10 -3	38.28	36.77	40.43
	Proposed λ = 10 -4	38.30	36.79	40.46
	λ = 10 -5	38.30	36.79	40.46
			σ 2 = 12.5 10 5
	SENSE	42.94	42.40	45.58
	Proposed λ = 10 -4	43.57	42.74	46.35
			σ 2 = 2 10 7
	SENSE	30.00	28.57	32.03
	Proposed λ = 10 -4	33.72	31.69	34.92


Tuyet-Tram Dang-Ngoc
email: tram.dang-ngoc@prism.uvsq.fr

Georges Gardarin
email: georges.gardarin@prism.uvsq.fr

FEDERATING HETEROGENEOUS DATA SOURCES WITH XML

Keywords: Cooperation in Heterogeneous System, Mediation Architecture, XML Algebra, XQuery Evaluation

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

Introduction

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. Wellknown 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 [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 (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 monosource 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. In section 4, 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 subqueries 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. 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.

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 [START_REF] Manolescu | Answering XML Queries over Heterogeneous Data Sources[END_REF]. 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 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 [START_REF] Christophides | On Wrapping Query Languages and Efficient XML Integration[END_REF][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. ). 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.

Data model

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. 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.

Performance optimization by additional modules

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 structural 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: Example of an XRelation 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.

Figure 3

 3 Figure3shows the different steps of an XQuery request on the mediator. Measures shows the execution time (in millisecond) depending on the number of resulting documents for each type of execution. The most above graph is the total execution time. The graph just under represents the evaluation time on the mediator. Just under, there is the graph representing the time spent on the wrapper and finally the most below graph represents the initialization time of the request. The experiment shows the high cost of communication for XML documents exchange between the wrappers and the mediator. It's the first point to optimize. We propose several optimization that should reduce this cost.

Figure 3 :

 3 Figure 3: Execution time for each step

  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, cross-tree hyperlinks can be supported as special edges.

	XPath's are defining the attributes and Path's compose the
	path set of the XML trees.
	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, 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 ]
					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 multi-valued,
					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


Georges Gardarin

Fei Sha

Tram Dang

XML-based Components for Federating Multiple Heterogeneous Data Sources

Several federated database systems have been built in the past using the relational or the object model as federating model. This paper gives an overview of the XMLMedia system, a federated database system mediator using XML as federating model, built in the Esprit Project MIRO-Web. The system is composed of four main components: a wrapper generator using rule-based scripting to produce XML data from various source formats, a mediator querying and integrating relational and XML sources, an XML DBMS extender supporting XML on top of relational DBMSs, and client tools including a Java API and an XML query browser. The results demonstrate the ability of XML with an associated query language (we use XML-QL) to federate various data sources on the Internet or on Intranets.

Introduction

In the past few years, research in semistructured data has become a hot topic [START_REF] Abiteboul | Querying Semistructured Data[END_REF], [START_REF] Buneman | Semistructured Data[END_REF]. Different approaches have been proposed for efficiently managing semistructured data from diverse sources. Significant experiences are the Lore system [START_REF] Mchugh | Lore: A Database Management System for Semistructured Data[END_REF] developed at Stanford University built from scratch for managing semistructured data, Ozone built on top of the O2 object-oriented DBMS, and STRUDEL [START_REF] Fernandez | A Query Language for a Web Site Management System[END_REF] developed at AT&T for managing web-based data.

In this paper we present our experience in federating multiple data sources using XML and XML-QL, a query language jointly developed by AT&T and INRIA [START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF]. This work is part of the European ESPRIT project MIRO-Web [START_REF] Fankhauser | Experiences in Federated Databases: From IRO-DB to MIRO-Web[END_REF], a federated database system integrating relational, object-oriented and semistructured data. MIRO-Web is federating heterogeneous data sources using a semistructured data model. The model is a slight variation of OEM [START_REF] Mchugh | Lore: A Database Management System for Semistructured Data[END_REF]. Data are exchanged among sources using XML and XML-QL, i.e., a query language based on XML patterns [START_REF] Deutsch | XML-QL: A Query Language for XML[END_REF]. As repository to store and retrieve XML documents, we use Oracle 8.0, the well known objectrelational DBMS.

In the following, we give an overview of our federated database system architecture and describe the main components of the system. The system is now called XMLMedia (for Mediating in XML) and is on his way to be commercialized by a Frenchbased company. Components include an XML wrapper using a rule-based data extraction technology developed at GMD IPSI in Germany, an XML extender (also called a cartridge) to store and query XML documents in a relational DBMS, an XML mediator which receives XML-QL queries from client sites, then decomposes them in either SQL or XML subqueries, routes the resulting subqueries to the source wrapper and assemble the results in XML. Finally, it also includes an XML query browser to formulate queries in XML-QL and present the results, plus a Java DOM API for submitting queries in Java and manipulating results.

The paper is organized as follows. Section 2 introduces the objectives of the XMLMedia system and gives some background on related projects. Section 3 describes the system architecture and introduces the components. Section 4 details the XML extender for relational DBMSs. Section 5 presents the principles of the mediator. We conclude in Section 6 and summarize the advantages of XML for mediation

Objectives and Backgrounds

In this section, we summarize the objectives of our system and present some backgrounds on semisructured databases.

System Objectives

The goal of the XMLMedia system is to provide in an efficient way integrated access to multiple data sources on the Internet or on intranets using XML protocols and tools based on Java components. The components can be assembled together or used separately in different application contexts. Possible applications are the constitution of electronic libraries from existing sources, the collect of information for trading systems, the assembling of fragments of data for technology watch, and more generally knowledge management and information diffusion in the enterprise. Used together, the components form a unique solution to support iterative definition and manipulation of semistructured databases derived from existing data sources or loosely structured files in Internet/Intranet environments. They are based on the new emerging standard XML and its derivative such as XML-QL, a query language for XML proposed at W3C by AT&T and INRIA.

Today Intranet/Internet platforms support access to existing files, databases, data warehouses, and legacy applications from a single browser interface. However, the existing tools do not allow the integration of multiple data sources, due to the lack of metadata generators, metadata integrators, and distributed query evaluators including update transactions. In such a context, some data sources are well structured, while others are not. The XMLMedia components provide a nice way to merge structured and non-structured data and make it accessible through established standards, namely SQL3, JDBC, and XML, on the Internet or Intranets.

Related Work

There has been recently a lot of work on semistructured data. Some systems pioneered a storage model based on object DBMSs. TSIMMIS [START_REF] Papakonstantinou | Object Exchange Across Heterogeneous Information Sources[END_REF], Lore [START_REF] Mchugh | Lore: A Database Management System for Semistructured Data[END_REF], and Strudel [START_REF] Fankhauser | Cooking XML : An Extraction Tutorial for Jedi[END_REF] store their data as graphs. [START_REF] Roelof Van Zwol | Implementing Semi Structured Data with MOA[END_REF] presents an original approach based on binary relations (one for each label) storing object identifiers and values in the context of the Monet DBMS. They use the MOA algebra to deal with type coercion and object assembling. [START_REF] Christophides | From Structured Documents to Novel Query Facilities[END_REF] proposes an object-oriented schema derived from the DTD to store SGML documents. We further detail relational storage techniques for semistructured object in the next subsection.

Experiences in federating data sources through a semistructured model have been conducted in several projects, including TSIMMIS, Lore and YATL. This last system focuses on rule-based translation techniques and object typing [START_REF] Abiteboul | Querying Semistructured Data[END_REF]. For optimizing queries, several approaches have been studied. Optimization techniques are for example surveyed in [START_REF] Buneman | Semistructured Data[END_REF]. More specifically, [START_REF] Fernandez | Optimizing Regular Path Expressions Using Graph Schemas[END_REF] optimizes regular path expressions using graph schemas.

The management of metadata is also an important problem in (federated) semistructured DBMS. Originally proposed in [START_REF] Goldman | DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases[END_REF], strong dataguides can help in query formulation or in query processing [START_REF] Mchugh | Lore: A Database Management System for Semistructured Data[END_REF]. Panoramic dataguide [START_REF] Goldman | Interactive Query and search in Semistructured Databases[END_REF] were introduced for query formulation. They are quite similar to path index introduced in object systems. Recently, [START_REF] Goldman | Approximate Dataguides[END_REF] pioneered the idea of using approximate dataguides, which group together dataguide paths when their target sets are "almost" equal.

Storing Semistructured Objects in Tables

There are obviously many ways to map graphs into tables. Hence, several mapping schemes are possible for storing semistructured objects in an object-relational DBMS. Our first experiences demonstrate that simple mapping schemes can differ a lot in performance for a given query workload according to very specific detailed choices, such as OIDs assignation, clustering and indexing schemes, number of tables to open, etc. In a first phase, we investigated the following mapping schemes:

The bulk data type. A bulk data type can be used to store directly XML documents with tags and data. Access to individual structural elements is then realized by parsing. This approach is rather efficient for assembling documents, but requires specific index structures for retrieval.

The single-edge table.

A table can be used to represent each individual edge of the object network as a tuple, consisting of parent-OID, label, type, order, and child-OID. Conventional relational operators, including select, join, recursive join, project, and aggregate, can be used for evaluating queries over such structures.

With appropriate indices for values and links the inefficient scan can be avoided to a large extent. In contrast to using a bulk-data type, the approach is rather efficient for accessing small substructures, whereas the overhead involved in assembling complex documents could be rather high.

The multiple-edge table. This scheme is a variation of the previous one where a generic table is used, but one tuple contains all edges going out from a given node. This requires nested tables. A typical scheme for the generic table consists of pairs parent-OID, array of edges, each edge being described by a label, a type, and a child-OID. A first advantage of this solution is that the order is encoded within the array; also, edges outgoing a given node are grouped together; however, searching in array-valued attributes remain a difficult operation in most object-relational DBMSs.

The single-edge attribute tables. The idea is to store all the edges with the same label in a separate table having the name of the label [START_REF] Roelof Van Zwol | Implementing Semi Structured Data with MOA[END_REF]. This approach can be understood as a variation of the single-edge table but with several edge-tables, one for each edge name. A variant can be obtained by clustering or indexing the single-edge table on the label attribute. The document assembling is difficult with the single-edge attribute tables approach. However, it is efficient for selecting elements of a given label. As manipulating table names is less efficient than manipulating indexed attribute values in most object-relational DBMSs, we prefer the single-edge approach with clustering or indexing.

The structured tables with overflow. An explicit relational schema can be derived from a collection of semistructured objects. The schema can be composed of several tables, each designed to group repetitive structures. STORED [START_REF] Deutsch | Storing Semistructured Data with Stored[END_REF] proposes a declarative query language to specify the mapping between the semistructured data model and the relational model. The mapping exploits regular patterns that can be found in semistructured data to compose multiattribute tables. Furthermore, an overflow graph is managed to store data that do not fit the relational schema.

Querying XML documents

Several query languages have been proposed to query semistructured data and XML documents, among them LOREL, XML-QL and XQL.

The LOREL language [START_REF] Mchugh | Lore: A Database Management System for Semistructured Data[END_REF] was one of the most complete query language built for querying semistructured data, more specifically OEM graphs. LOREL is basically an extension of OQL with extended path expressions. A simple path expression is a root name followed by a sequence of tags, for example Guide.Restaurant.Adress.Street. This expression refers to all objects reachable from the root following the edges with the given tags. Path expressions can be used to specify collections and in place of attributes for conditions and projections. They are generalized to express search patterns with string profiles, disjunction be-tween tags, optional tags and regular expressions with the Kleen star, allowing 0 to N repetition of a tags. For example, the following request retrieve all attributes of restaurants in cities or streets containing the substring "puy" : SELECT GUIDE.Restaurant.# WHERE Guide.restaurant.Adresse.(Ville|Rue) LIKE "%puy%". LOREL is powerful and elegant, but requires the support of OQL, which is quite complex in federated database systems.

XML-QL is another query language specifically designed for XML document collections. XML-QL is based on XML patterns, i.e., XML documents with elements replaced by variables and predicates. XML-QL provides facilities to filter document collections, but also to construct query results as new XML documents. A typical query is of the form : WHERE <template> CONSTRUCT <template>. A template can be either an XML document with variables and conditions including joins, but can also be a condition with regular expressions or function calls, including Skolem functions to create new nodes. A template can also be an XML-QL query, which allows to nest queries and express powerful constructs. A simple example of an XML-QL query is : WHERE <Guide> <restaurant> r <Address> <City> c </City> <Street> s </Steeet> (c LIKE "%puy%" OR s LIKE "%puy%") </Address> </restaurant> </Guide> CONSTRUCT <Guide> r </Guide> A derivative of such languages called XQL is under a standardization by the W3C. The language is similar to XML-QL but has a different rather complex syntax. The basic idea is to extend URLs and hierarchical designators to represent queries. Special characters are introduced to encode search patterns, such as / to look for the child of a node, // to look for all descendants, * to designate any label, @ to capture an attribute, [ …] to nest sub-queries, ? to return a node and ?? to return a node and all its descendants. XQL could be part of the XSL standard or a stand alone component.

System Architecture and Components

In this section, we present an overview of the system architecture and summarize the functions of the main components.

Architecture Overview

As mentionned in introduction, the XMLMedia system federates multiple data sources using a semistructured data model and XML as the basic exchange vehicle. The system follows the DARPA I3 architecture including three layers of functions : the translation layer, the mediation layer and the coordination layer. The overall system architecture is represented in figure 1. It is composed of Java packages constituting components (they should be arranged as JavaBeans). For accessing relational DBMSs, we use JDBC. For the rest, we developed our own components.

The Three Tiers

The system follows a three-tiered architecture, with clients, application servers running the mediating components, and the data tier including most of the translation services. More precisely, we distinguish three layers as follows :

The translation layer includes the data sources and wrappers to wrap them in XML or SQL. XML wrappers are built from the JEDI toolkit developed at GMD in Germany [START_REF] Fernandez | A Query Language for a Web Site Management System[END_REF]. JEDI is a powerful tool based on production rules. The rule allows the wrapper implementor to write search patterns in source documents and to produce variables. The variables can later be bundled in XML. Rules can call each other and can be recursively applied. Different formats of sources are supported including text, HTML, RTF, PS, DOC, XML, etc. Queries can be expressed against the source using a subset of OQL.

The mediation layer includes the key components we will describe in the two next sections. The XML Extender extends any JDBC compatible DBMS to support XML document storage and querying. This component provides the necessary tools to store efficiently XML in relational tables and to run SQL3 queries extended with generalized path expressions. The query language is similar to LOREL, but built on SQL. Also, it allows result restructuring through a special AS clause. The XML Mediator does mediation between all the sources, including XML and SQL ones. It processes XML-QL queries, divides them in sub-queries according to the source capabilities, collects the results in XML, assembles them, and sends an integrated answer to the client.

The coordination layer includes all the client tools. It is composed of an XML-QL browser to formulate queries and present results, and of a JAVA API. This API allows Java programs to send XML-QL queries and to get the results as an XML document. The document can further be exploited in Java using the DOM tools.

The XML Database Extender

In this section, we describe the XML Database Extender (sometimes also called cartridge), which is able to store XML documents in any object-relational DBMS and which provides an extended SQL3 with path expressions to retrieve XML document fragments and reassemble them.

XML Document Modeling

As in many research projects, we use labeled directed graph for modeling semistructured object. Our modeling is an ordered version of the OEM model [START_REF] Mchugh | Lore: A Database Management System for Semistructured Data[END_REF] extended with different edge types. A document consists of a collection of objects, in which each object is either complex or atomic. A complex object is an optionally ordered set of <name, object> pair. An atomic object is a value of type int, real, string, image, video, and more generally of any type supported by the underlying object-relational DBMS (user data types are possible). The optional order gives the relative order of edges among those going out from a given node. To better model related XML documents, we distinguish two types of edges, as shown in Fig. 1: an edge originated and targeted within the same document is called an aggregation link, and an edge between different documents is called an association link. Hence, a document is a graph, with edges labeled by names and leaves labeled by values. Documents can be linked together by association links.

When assembling a document, only links of aggregation type are considered as relevant. This information is particularly important to model XML documents, which includes M to N relationships (i.e., association links). The order is simply memorized through an ordinal number. This is important to assemble XML document items in the correct order. Figure 2 shows on an example how we model XML linked documents.

Storing Documents in Tables

For simplicity and efficiency in retrieval, we selected the single-edge table approach. Edges in the graph are stored in a table called the edge table. In the database, each node is identified by a unique identifier. For allowing efficient clustering of the document edges, the root node identifier of each document is repeated as the first attribute of each edge of the document. Hence, each edge is represented by a flat tuple [root, origin, target, label, link type, node type, order]. The root attribute indicates the object root OID from which the edge is a descendent. The origin and target attributes memorizes the node OID of the origin and target node respectively. Label is the label of the link. In the edge table both aggregation and association links are stored. Hence, link type indicates whether a link is a composite aggregation or an association. Node type is the type of the value attached to the target node. For internal nodes, it is simply "NODE", while it is the name of the leaf table containing the value for a leaf node. The structure of the edge table is exemplified in Figure 3. To group edges of a document in one or more pages, the edge table is clustered on root_oid. A clustered index is maintained by the RDBMS to give direct access to edges of a document, e.g., to join efficiently with a relational

Fig. 3. An instance of the edge table

Leaf nodes with their values are stored in leaf tables. By default, one leaf table is used to store leaves of each type. Special mapping specifications can be used to define target tables for several leaf nodes. For the time being, the mapping language allow the administrator to stipulate which XML element is going to be stored in a table. The element has to be a tuple conforming to the value table schema. We envision to extend the mapping language for mapping complex values in a unique object-relational table in the future.

As mentioned above, this storage structure is quite efficient for query processing. Indices can be declared on origin and taget OIDs and labels, to accelerate selection and join when querying. The problem with this approach is the cost of assembling full documents data from the leaf tables. As tuples are randomly distributed within the leaf table, assembling a complex document may require several I/Os in the leaf table. To reduce the high cost of assembling document values, we use a clever node OID allopolicy. A unique integer value is assigned to each node as its identifier using a sequence number (provided by the RDBMS). Within an XML document, ascending node OIDs are assigned to each node in the breath-first traversal order. Thus, identifiers of leave nodes of a document are close together. We cluster leave tables on their identifiers and index them on that identifier. To retrieve the data of a document, range queries can be used in each leaf table containing data from that document. Figure 4 illustrates a simple leaf table for storing the string data type values. Notes that leaf tables are clustered on NODE ID, to group chunks of documents together.

No-deID

Value

3

"Dupont" 6 "des Vignes" 8 "BMW" 9 "blue"

Fig. 4. Example of a leaf table for string values

Document Query Processing

As already mentioned, we use an extended SQL to query XML documents. The extension for SQL is similar to LOREL for OQL, i.e., we mainly support generalized path expressions in SQL queries. Generally, relational systems are considered inefficient for processing queries containing path traversals. However, in the context of semistructured data, some characteristics of relational systems can compensate the handicap. First, in object-relational systems, path traversals can be processed in a setoriented manner using successive joins on indexed attributes (the source and target OIDs). Second, in systems supporting recursive queries, path expressions can be processed using them. For example, in Oracle 8, the hierarchical recursive query is well suited for evaluating path expressions.

Obviously, the cost of path traversals increases as the path length increases. To optimize long path traversals, our implementation support the concept of path index. A path index is simply a join index of the edge table with itself, using target equals origin as join predicate. The path name is kept by concatenating the edge names. By joining again the path index with the edge table, we can generate path index of length 3, and so on up to path index of length n. Path index tables can become large. To reduce the size of path index tables, we can choose to store only paths frequently occurring in the graph. A no match will then requires normal processing against the full edge table. A path index reduces the number of joins or level of hierarchical traversal in processing path expressions. To traverse a given path expression, we first search within the path index corresponding to the maximum covered path length, and then follow up within the edge table. A path index of length n cannot be used directly to evaluate path expressions of length shorter than n.

In semistructured databases, regular path expressions with Kleene stars have special importance. Semistructured data have irregular and changing structures. By means of regular path expressions, users can query the database without the full knowledge on data structures. Although convenient to use, regular path expressions in general cannot be evaluated directly due to their prohibitive cost. Up to now, the proposed solutions for optimizing regular path expressions are all based on pruning techniques [START_REF] Fernandez | Optimizing Regular Path Expressions Using Graph Schemas[END_REF]. To apply pruning, some sort of metadata is required. Several variations of the representative objects [START_REF] Nestorov | Representative Objects: Concise Representations of Semistructured, Hierarchial Data[END_REF] and dataguides [START_REF] Goldman | DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases[END_REF] including the approximate dataguides [START_REF] Goldman | Approximate Dataguides[END_REF] have been proposed. They are useful to keep track of the possible nesting of labels and avoid full scan of the database.

In our system, any label can be accessed directly regardless the distance from the root. This is due to the existence of an index on the labels. In addition, the graphs can be traversed in forward or reverse direction through joins. The traversal can be efficient if path index are maintained, as explained above. These features are quite helpful for processing path expressions with wildcard and more generally Kleene stars.

To further accelerate path expression processing, we maintain a specific sort of metadata called the longest path set. Informally, this is the set of longest paths in the graphs. Queries based on path expressions search for nodes but are formulated from labels. Hence, in our structure, we keep only labels. We model the possible paths as a regular language where labels are letters from an alphabet, and where regular path expressions are words (infinite words in the event of loops in the graph). The goal being to determine words that belong to this language, we do not keep words that are factors of a longer word. Regular path expressions have the following format: l 0 .l 1 ...l i .*.l j .l j+1 …l n . where the Kleene star matches any path of any length. The goal of the rewriting is to find all sub-words from the set of words in the longest path set which start with l 0 .l 1 ...l i and finish with l j .l j+1 …l n . Then, the query can be transformed in a query with a disjunction of fully documented path expressions in qualification.

In summary, we expand regular path expressions using the longest path set words and sub-words. For simplicity, we assume that graphs have no loop. It is possible to handle loops, but they have to be detected at document loading and expanded with special labels to encode infinite longest paths.

The XML Mediator

The XML mediator is the other key component of the mediation layer. Through the browser, the client issues an XML-QL query to the mediator and waits for an answer. As usual in mediation systems, the mediator accepts the query and decomposes it into subqueries, one for each source, with in addition a recomposition subquery. Subqueries are routed to a gateway in charge of shipping the query to the appropriate wrapper. The gateway is able of managing a pool of data source connections to save overhead. When the connection has been allocated, the gateway issues the subqueries to the wrappers and waits for a response. The wrappers process the subqueries by consulting the associated data sources and generate subanswers that are returned to the mediator. The mediator combines the subanswers by using the composition subquery and generates the final answer that is returned to the client In addition, the mediator provides some facilities to translate queries according to the capabilities of the wrapper. To perform this translation, specialized components called doors are included. A door is a generic class and can be extended by query and result translation methods. Figure 5 The role of the main components of the mediator can be summarized as follows :

The Decomposer decomposes XML-QL queries in query graphs.

The Evaluator identifies local subqueries to ship and run the recomposition query.

The Exchanger routes the query to the appropriate gateway and collects the result back.

The Gateway manages connection pools to data sources and submits subqueries to wrappers.

The Door translates queries for local wrappers and translates answer back in OEM graphs

The Recomposer recomposes an XML answer for the client.

The Metadata manager collects and maintains schemas and label paths for each data source.

In summary, the XML mediator is somehow similar to a relational mediator except that it is based on XML-QL and returns data in XML. The semi-structured OEM+ model supported by data and query graphs is the basis of our internal implementation. Thus, XML data are internally represented as extended OEM graphs similar to that manipulated in the XML extender described in the previous section. Queries are also represented as graphs with constraints (i.e., restrictions) and links (i.e., joins). Extended OEM graphs support easily the mixing of relational data and true semistructured data provided by XML wrappers or SGML databases.

Conclusion

In this paper, we have presented XMLMedia, a mediating system based on XML. XMLMedia federates both XML documents and SQL tables and unify them in a virtual XML digital library. The XML Extender provides the necessary functionnalties to store and manipulate XML documents on top of an object-relational DBMS. Coupling the capabilities of the extender with multimedia features now available in most objectrelational DBMSs gives powerful functions to retrieve documents by contents, e.g., using similarity search on keywords or image features. The mediator offers the XML-QL query language to query the virtual libraries of XML documents.

A first version of the system is already experimented in several applications as a test-bed, including a tourism virtual Web site in Tyrol, an Intranet in a Spanish hospital and a trading application. Performance is achieved by the nice features well established of object-relational systems and by appropriate pools of buffers and connections. The mediator can also be used to feed Web data in a datawarehouse and more generally to collect and disseminate information in the enterprise. A demonstration of the system can be found on the Web at http://nora.prism.uvsq.fr/miroweb/.

Our experience in federating data sources through XML and XML-QL demonstrates the advantages of the semistructured data model for exchanging data. First, it is flexible and auto-documented. No type requires to be predefined, as with the object model for example. Second, it is easy to merge semistructured data and relational one through direct mapping, which can be more or less sophisticated for optimization purpose. Third, XML is an appropriate exchange model on the Web and writing wrappers is an easy task, especially with a powerful wrapper generator as is JEDI. Fourth, XML-QL is appropriate for client-server dialog, as it is XML uniform (a query can be seen as an XML document). Fifth and it is probably the most important, XML gives good opportunities to unify classical database processing with information retrieval approaches. The power of the resulting tool is not well evaluated yet.

OFig. 1 .

 1 Fig. 1. System Architecture

Fig. 5 .

 5 Fig. 5. The mediator architecture

  table.

	root	origin	target	label	ltype	ntype
	1	1	2	name	AGGR	STRING
	1	1	3	manager	AGGR	INTEGER
	1	1	4	address	AGGR	NODE
	1	4	5	number	AGGR	INTEGER
	1	4	6	street	AGGR	STRING
	1	1	7	drive	ASSC	NODE
	7	7	8	mark	AGGR	STRING
	7	7	9	color	AGGR	STRING

Acknowledgments

We would like to thank Peter Fankhauser, Dana Florescu, Henri Laude and Patrick Valduriez for helpful discussions, particularly in the context of the MIRO-Web project. We owe them many ideas.


Miro Web: Integrating Multiple Data Sources through Semistructured Data Types Luc Bouganim, Tatiana Chan-Sine-Ying, Tuyet-Tram Dang-Ngoc, Jean-Luc Darroux, Georges Gardarin, Fei Sha To cite this version: Luc Bouganim, Tatiana Chan-Sine-Ying, Tuyet-Tram Dang-Ngoc, Jean-Luc Darroux, Georges Gardarin, et al.. Miro Web: Integrating Multiple Data Sources through Semistructured Data Types. International Conference on Very large DataBases (VLDB 1999), 1999, Edinsburgh, Scottland, European Union. p. 750-753. hal-00733489


Tuyêt-Trâm Dang-Ngoc

Clément Jamard
email: clement.jamard@prism.uvsq.fr

Nicolas Travers
email: nicolas.travers@prism.uvsq.fr

XLive: An XML Light Integration Virtual Engine

Introduction

On the Internet, data are distributed on heterogeneous sources. To integrate them in a uniform view, lots of systems based on the famous mediator/wrapper architecture defined by [START_REF] Wiederhold | Mediators in the Architecture of Future Information Systems[END_REF] have been designed [START_REF] Ahmed | An Overview of Pegasus[END_REF] [START_REF] Gardarin | IRO-DB: a Distributed System Federating Object and relational Databases[END_REF]. The data model now admitted for representing data is semi-structured data represented by the XML standard format. Thus now, as well in industry as in research, integration systems using XML-based standards have emerged [START_REF] Chawathe | The TSIMMIS Project: Integration of Heterogeneous Information Sources[END_REF] [START_REF] Baru | XML-Based Information Mediation with MIX[END_REF].

XLive is such an integration system based on XML standards. It is the sequels of our experiences on mediation design in research project (MIROWEB [START_REF] Fankhauser | Experiences in Federated Databases: From IRO-DB to MIRO-Web[END_REF], XML-KM) and in industry XMLMedia.

The XLive prototype is designed to be a light mediation system with high modularity and extension capabilities. It is a running research vehicle designed for assessing the integration system at every stage of the process starting from sources extraction to the user interface, including query parsing and modeling, optimization and evaluation, and also benchmarking.

System architecture

As most mediation systems, XLive is composed of three layers: Presentation, Integration and sources Connection.

Each of these layers is composed of several components that are all "exchangeable". Indeed, all components have a defined interface.

Figure 1: XLive Architecture

The integration system is shown in Figure 1. Components are shown as boxes and intermediate structures are shown as ovals. Structures and components can all be differently designed, but structures are bounded to the component. For example, for the XQuery query language we have two different Parsing Components, both parsing XQuery and for another query language; let's say XML-QL, we should use a dedicated XML-QL Parsing component. The XLive Integration System is composed of the following components:

•
The Wrapper is a component for accessing a specific source for querying and retrieving result. As sources have specific access methods, the role of the wrapper is to translate the wrapper specificity to a common access method.

•

The Wrapper Information Manager is for integrating information about wrapped sources. It provides to the mediator sources metadata, capabilities, and costs statistics on source data.

•

The View local Management is a special source. It is used to define views that are implemented in two ways depending on data and source type.

•

The Query Parsing parses a query language and translates it into a query model.

•

The Plan Generator translates a query model to one or more execution plan. The optimal execution plan that would be evaluated is chosen by using cost information.

•

The Evaluator evaluates the execution plan by querying relevant sources and merging results.

Modules

All components described above can be designed and implemented in different ways. Based on this modularity, XLive is used in different research projects (WebSI, SemWeb) by designing appropriate component to achieve project objectives. Thus, each component can be replaced by another implementation matching the same interface in order to test performance of different kind of algorithms and methods. In the following, we describe research algorithms and concepts that have been implemented and tested using the prototype. All implementation of XLive components (mediator and wrappers) is done in Java.

Evaluation Model

From a query language, the query parser designs a model for representing queries. Two models have been designed: RXQuery and TGV.

RXQuery and XQuery Rules

RXQuery is an intermediate structure for representing an XQuery. Each clause of the FLWOR expression of an XQuery is mapped to a specific structure (XFor, XWhere and XReturn). The following steps are then applied to create an execution plan from this model.

The first phase of decomposition transforms the query in canonical forms, i.e., without imbrications, using equivalence rules described in [START_REF] Manolescu | Answering XML Queries over Heterogeneous Data Sources[END_REF]. The RXQuery structure is transformed in several ones where imbrications are replaced by join constraints between flat RXQuery structures.

The second phase analyses the pending queries resulting from canonization to create atomic queries, i.e., requests processing only one collection that can be delegated to a wrapper. The join conditions and the final reconstruction allow the mediator to build the query plan.

Tree Graph View

The idea is to propose a representation of queries as graphs of trees, more precisely as tree pattern graphs interconnected by hyperlinks. The structure called Tree Graph View (TGV) [START_REF] Dang-Ngoc | Tree Graph View: On Efficient Evaluation of XQuery in an XML Mediator[END_REF] is an extension of the Generalized Tree Pattern graph proposed in [START_REF] Chen | From Tree Patterns to Generalized Tree Patterns: On efficient Evaluation of XQuery. Very Large Data Bases[END_REF] as a concise and practical representation of an XQuery. It is designed to be a more intuitive model of queries and to allow direct optimization before generating the physical execution plan. In Figure 2, the bottom right XQuery is mapped to the TGV graph on the left. Annotated Tree Patterns represents the request schema associated to sources and (hyper)links between them are used respectively for representing joins and reconstruction.

Execution plan

The mediator Plan Generator creates an execution plan from an evaluation model. The execution plan needs an algebra to represent operations to evaluate. XAlgebra [START_REF] Dang-Ngoc | Federating Heterogeneous Data Sources[END_REF] is an extended relational algebra able to process XML trees in pipeline. The XAlgebra is designed to manipulate semi-structured data, thus it includes both relational operations to process tables of references on needed XPaths and navigation in XML trees. This representation is called XTuple; XOperators manipulate XRelations composed of XTuples. The XAlgebra is a physical algebra, which means that algebraic expressions are used to process XML flows and that algorithms are directly implementing them.

Wrappers

Wrappers translate sources from their native query language and result format to the common ones used by the mediator: XQuery and XML. Several wrappers have been implemented for XLive. Relational Database Sources: Wrappers for relational databases have been implemented allowing the mapping from relational data to semistructured data. They are available for Oracle and MySQL using JDBC.

XML Database Sources: Wrappers for native XML databases have also been implemented. They are available for XHive and Xyleme [START_REF] Abiteboul | The Xyleme Project[END_REF]. Web Service Sources: Two wrappers using web services provided respectively by amazon and google has been implemented. In the case of google, the wrapper sees the whole World Wide Web as a huge collection of documents, using the specific structure defined by google. In the case of Amazon, it is the whole amazon database that is seen as a collection.

View Local Management

The mediator integrates two view systems. The Text View integrates XQuery Text functionalities for non-capable sources. Materialized Views address the problem of interrogating web sources.

Text oriented indexed views

A module for creating indexed views on distributed sources is available for XQuery Text oriented queries. It uses an element identification scheme based on a structural guide of the view to determine the virtual position of indexed terms in the view. A global index maps a virtual document in the view to the local document in the source. On a query on the view, virtual documents identifiers answering the query are retrieved from the index, wrappers load values from sources using virtual-to-local document mapping and there is only to reconstruct results in the mediator. For better performance, we index references on distant data instead of materializing the view in the mediator.

This indexing system allows answering XQuery Text queries over distributed sources and bypasses the eventual lack of textual capabilities of sources. Moreover it also provides a uniform relevance ranking scheme, allowing choice between various formulas depending on research domain.

Materialized views for web sources

To optimize query evaluation on web sources, views are materialized in a local XML warehouse. The difficulty is to maintain incrementally the view as the sources change [START_REF] Abiteboul | On Views and XML[END_REF]. In the special case of web sources, maintenance is all the more difficult as web sources do not communicate any information about their update and about the data structure and ids.

In the context of web sources, very few information are provided by sources, and methods usually proposed cannot be applied in this context. This component is for testing how to update materialized XML views on web sources in the context of mediation architecture.

In this approach, we introduce XTID in the XAlgebra which is a pair of number incrementally generated by the wrapper for each sources. By using XTuples comparison and XTID, we are able to report updates from the source to the view materialization by comparing diff fragments. More about it can be found in [START_REF] Abiteboul | On Views and XML[END_REF].

Wrapper Information Management

Information provided by wrappers are used in the mediator to validate queries, resolve sources and capacities. Metadata: A generic Metadata Manager has been implemented based on path set. The path set describes each collection structure and associates each target sources. We now plan to implement another one based on XML-schema. Capabilities: Wrappers provide capabilities rules to the mediator. The Plan Generator is able to understand these rules to optimize the execution plan by delegating as much as possible work to sources. Operations not supported by sources should be processed by the mediator and are included as operators in the execution plan. It leads to a valid execution plan, i.e., that can be evaluated at execution time. The mediator handles main operations (Join, Construct, Union, Sort …) and also text research operations. Data information: Other wrapper information should be provided to the wrapper as plug-ins, like a generic cost model.

Benchmarking

A benchmark [START_REF] Dragan | Benchmarking an XML Mediator[END_REF] created in the context of distributed semi-structured model on heterogeneous sources have been specified and applied to XLive.

It performs comparisons between queries evaluated on single sources and through the mediator. Mediator performance is shown in Figure 3 for a set of representative queries: selection and projection (q01-q02-q07), join (q09-q10), reconstruction (q11). We use two kinds of XML data in our scenarios, data oriented and structure oriented. XLive stores those data in different systems: native XML repositories (XHive, Xyleme), relational systems (Oracle, MySQL) and web sources (Google, Amazon). Generally the overhead due to the mediation process raises the execution time between 1.4 and 2 compared to single source evaluation.

Figure 2 :

 2 Figure 2: TGV representation for an XQuery

The Demonstration

The XLive prototype is now used in several projects and works entirely. It means that several heterogeneous distributed sources based on semistructured data can be registered to the mediator and that an XQuery given to the mediator on these sources return the correct result into XML format in a reasonable delay. The demonstration will go through the execution process of an XQuery, from parsing to plan generation of a large set of queries on several distributed heterogeneous sources. Every step of the process is detailed allowing users to test and compare different query model, execution plans and evaluation. The graphical administration console displays intermediate structures (RXQuery, TGV, XAlgebra execution plan) for better process information.

The demonstration will show the ability to easily exchange components through our interface in Figure 4. We then compare performances of the mediator with different component combination (query and plan optimization, views management for XQuery Text).


Georges Gardarin
email: georges@gardarin.org

Tuyet-Tram Dang-Ngoc

Tuyet-Tram Dang

Mediating the Semantic Web

Introduction

Typical information integration systems have adopted a wrapper-mediator architecture [Wiederhold, 1992]. In this architecture, mediators provide a uniform user interface to queriesy 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. 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. Mediator architects are used to distinguish the local as view (LAV) approach versus the global as views (GAV) approach, in which the integrated views are designed in terms of the local views of sources. To meet a given ontology in a given domain, the LAV approach seems more appropriate, but the GAV approach makes easier to take into account existing data sources schemas. Thus, mixed approaches are possible supported by schema design tools [Haas, 1999]. Well-known research projects and prototypes in mediation include Garlic [Haas, 1999], Tsimmis [Garcia-Molina, 1997], Tukwila [Ives, 1999].], Artemis [Castano, 2000], Enosys EXIP [Papakonstantinou, 2003], and XLive [Dang-Ngoc, 2003], a descendant of e-XML mediator [Gardarin, 2002]. Tim Berners-Lee, the inventor of the WWW, thought up the Semantic Web. The goal is to give well-defined meaning to Web information, better enabling intelligent Web applications requiring searching or reasoning, make them exchange meaning rather than information. There are a lot of (sometimes confusing) activities at W3C along this line. The