Gilles Bourquin

Cibiel

F Sthal #

J Imbaud #

M Devel

P Salzenstein #

R Bourquin # # Frequency

Time Department

G Cibiel

Some considerations on acoustic resonator

INTRODUCTION

High-precision quartz oscillators are mainly used in telecommunications, metrology and space applications such as local oscillators in satellites. The short-term stability of such oscillators is essential.

In 1994, J. Norton [START_REF] Norton | Performance of ultrastable quartz oscillators using BVA resonators[END_REF] has measured the best result of short-term stability of a quartz crystal resonator. It was a 5 MHz SC cut mounted in a BVA structure. The result in term of Allan standard deviation was 3.74⋅10 -14 for τ equals to 10 s. In 1999, at 10 MHz, R.J. Besson [START_REF] Besson | 10 MHz Hyperstable quartz oscillators[END_REF] measured two BVA quartz crystal oscillators with 5⋅10 -14 Allan standard deviation. Then, for ten years, there had been no significant improvement of quartz oscillators in the short term stability domain and no real solution had been found to improve the phase noise of BAW resonators. J. Norton's result represented the best acoustic resonator noise performance that could be found in the literature, pretty close to the lowest theoretical estimates. However, recently, better experimental results [START_REF] Chauvin | A new generation of very high stability BVA oscillators[END_REF][START_REF] Salzenstein | Significant step in ultra high stability quartz crystal oscillators[END_REF] have shown that quartz crystal oscillators may still have not said their last word in the short-term stability domain.

The oscillator limitation is theoretically imposed by the resonator. However, few models attempt to explain the 1/f behavior of the quartz crystal resonator. In this paper, we will briefly recall the 1/f quantum noise theory of P. Handel and the thermal boson theory of M. Planat in order to compare the latest published experimental results to the lower limitations computed with these two models. In the case of Handel's model, the noise depends on the resonator volume under the electrodes and the unloaded quality factor (Q) of the resonator. It gives an order of magnitude of the noise, but now some experimental results are below its prediction. In this paper, we will show that a lower theoretical estimate can nonetheless be extracted from Handel's model provided one uses the vibrating volume of the resonator instead of the volume under the electrodes.

II. MODELS

The following part presents a summary of the two models trying to elucidate the physical origin of the 1/f flicker noise of a quartz crystal resonator with a focus on the origin of the 1/f formula. We note, that both models can be seen as the two opposite sides of the fluctuation-dissipation theorem [START_REF] Kubo | The fluctuation-dissipation theorem[END_REF], since Planat studies the energy fluctuations around statistical equilibrium of a population of massless degenerate thermal bosons, whereas Handel proposes an origin for the dissipation occurring when the oscillator comes back to its mode after a small perturbation.

A. Planat's Model

In 2003, M. Planat proposed a statistical thermodynamics based model to explain the 1/f noise in quartz crystal resonators [START_REF] Planat | Thermal 1/f noise from the theory of partitions: application to a quartz resontor[END_REF]. In this paper, Planat considered the case of a population of massless bosons with a degenerate quantum harmonic oscillator energy spectrum which predict a hyperbolic fluctuation spectrum at low frequencies. According to the equipartition law of statistical mechanics, the partition function is introduced using a degeneracy parameter of the energy level nhf with n the number of bosons, h the Planck constant and f the frequency. The free energy F may be approximated in the low frequency part of the spectrum by:

24 x 2 x ln 2 1 x 6 kT F 2 + ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ - - ≈ π π ( 1 )
with x = hf / kT Subsequently, the exposed model keeps only the first term of [START_REF] Norton | Performance of ultrastable quartz oscillators using BVA resonators[END_REF].

According to the Einstein's conventional approach, the energy fluctuations of a system in equilibrium within a larger system of temperature T are:

(

)

T E kT E E 2 2 2 ∂ ∂ = - = ε ( 2 )
One can reformulate this relation for the fluctuations of the energy dE = u(f,T)df in the bandwidth df:

df ) f ( S df T u kT d u 2 2 = ∂ ∂ = ε ( 3 )
with u the energy spectral density and S u (f) the power spectral density of the fluctuations of u.

Thus, energy fluctuations in the bandwidth df are given by:

Vf A kTf 1 V 4 hc 9 u ) f ( S ph 3 3 ph LF 2 u = = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ π ( 4 ) With 3 A 3 B 3 C 3 ph c / 1 c / 1 c / 1 c / 3 + + =
, c A , c B and c C the velocities of the longitudinal mode A and the shear modes B and C, respectively. Considering [START_REF] Gagnepain | Relation between 1/f noise and Q-factor in quartz resontors[END_REF][START_REF] Handel | Nature of 1/f frequency fluctuations in quartz resonators[END_REF], the fractional frequency fluctuations in a quartz crystal resonator are:

f h Vf A Q 1 ) f ( S ) f ( S 1 ph 4 2 y - = = = ω ω ( 5 )
(5) has been used to give an order of magnitude of the power spectral density of the fractional frequency fluctuations of a 5 MHz 5 th overtone (OT 5), AT-cut quartz crystal resonator.

B. Handel's Model

P. H. Handel proposes in [START_REF] Handel | Quantum 1/f effect in resonant biochemical piezoelectric and MEMS sensors[END_REF] a summary of his 1/f quantum theory. According to him, the general origin of the intrinsic 1/f noise is due to a quantum self-interference process caused by very small spontaneous bremsstrahlung energy losses. The rate Γ of phonon interactions which remove phonons from the main quartz resonator mode is modulated by the quantum 1/f effect. The time-derivative of the polarization vector P of the quartz crystal is affected. According to bremsstrahlung, when the phonon is removed, a constant energy is radiated away per unit frequency interval at any frequency, its expression is:

( ) 3 2 0 c 3 P ) 4 ( 1 E & Δ πε = ( 6
)
With P & Δ , the variation of current density of the quartz crystal.

Then the number of photon emitted as bremsstrahlung of frequency f, per Hertz is given by dividing (6) by the energy of photon hf:

( ) 2 2 2 c πfe 3 P Δ α 2 Z & = ( 7 ) With 137 / 1 ) hc / e 2 )( 4 / 1 ( 2 0 = = π πε α , the Sommerfeld's fine structure constant.
Thus the one side spectrum is inversely proportional to f:

( ) 2 2 2 / c fe 3 P 4 ) f ( S π Δ α Γ Γ δ & = ( 8
)
If the main resonant mode is described as a forced harmonic oscillator with losses then the quantum 1/f fluctuations are present in the loss coefficient Γ of the following equation:

) t ( F x dt dx 2 dt x d 2 0 2 2 = + + ω Γ (9)
The quality factor of the resonator is defined as:

Γ ω 2 / Q r = ( 1 0 )
The resonant frequency is given by:

2 2 0 2 r 2Γ ω ω - = ( 1 1 )
Thus ) f ( S Q 4 1 ) f ( S / 4 y Γ Γ δ = ( 1 2 )
Where y = Δf/f 0 is the relative frequency fluctuation.

The vibrational energy of the crystal can be written as:

() 2 2 2 2 P Ne m dt dx 2 Nm 2 n W & h χ ω ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = = ( 13
)
With m the reduced mass of the elementary oscillating dipoles, e their charge, N their number in the crystal, χ a polarization constant, <ω> the average circular frequency of a thermal phonon interacting with phonons in the main resonator mode and n the average number of phonons in that typical thermal phonon mode.

Thus with:

( ) 2 2 2 4 e n N P χ ω Δ h & = ( 1 4 )
We can write:

⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = 4 y Q V f ) f ( S β ( 1 5 ) With: 3 2 2 0 cm / 1 mc n 12 n = = χ π ω α β h
, n 0 the number of dipoles per volume unit and V in cm 3 .

III. ACOUSTIC VOLUME ESTIMATION

The acoustic volume estimation is carried out using Tiersten's definitions as e. g. in [START_REF] Stevens | An analysis of doubly rotated quartz resonators utilizing essentially thickness modes with transverse variation[END_REF]. Due to the plano-convex shape, the thickness of the resonator 2h is given by the following expression (Fig. 1):

⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ + ≅ 0 2 3 2 1 0 4Rh ) x (x - 1 2h 2h ( 1 7 )
The amplitude of the mechanical displacement in the resonator is: Where n = 1, 3, 5, … the overtone number, m, p = 0, 2, 4, …, label the different mode shapes in the plane of the resonator, H m and H p are Hermit polynomials, R is the curvature radius, 2h 0 is the thickness of the resonator center, M n and P n are the dispersion constants and c ˆis the effective elastic constant associated to the propagation of the (C) mode.

( ) ( ) t nmp j ) 2 / 2 3 x ( n - ) 2 / 2 1 x ( n - 3 n p 1 n m 2 nmp e e e x H x H 2h x n sin A = u ω β α β α π ⋅ ( 1 8 ) with:
For the 3 rd overtone (OT 3), we have: In the case of SC-cut quartz resonator [START_REF] Bourquin | SC-cut resonator operating in anharmonic modes with B-mode reduction[END_REF], the cut is defined by a doubly rotation (ϕ = 22°45', θ = 34°) and in N/m²: The energy of the acoustic wave is given by:

t 300 j ) 2 / 2 3 x ( 3 - ) 2 / 2 1 x ( 3 -
dV e e x 2h 3 cos 2h 3 c 2 1 W V 2 2 2 3 x 3 - 2 2 1 x 3 - 2 2 1 ∫∫∫ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ≅ β α π π ( 2 2 )
To define the acoustic volume, we can consider the vibration amplitude which remains constant over the surface S eq , then we compute a cylindrical volume that has the same energy than the acoustic wave.

3 c 2 1 W × ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ≅ ∫ π π ( 2 3 ) Thus: 3 1 2 S 2 2 3 x 3 β 2 2 1 x 3 α eq 2 1 dx dx e e S W W ∫∫ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ = ⇒ = - - ( 2 4 )
Consequently, the acoustic volume is defined by:

0 eq ac 2h S V = ( 2 5 )

IV. APPLICATION OF THE MODELS TO EXPERIMENTAL

MEASUREMENTS

As seen in [START_REF] Salzenstein | Significant step in ultra high stability quartz crystal oscillators[END_REF], the best measured resonators are the 5 MHz BVA SC-cut, OT 3, resonator from Oscilloquartz (Neuchatel, Switzerland). In [START_REF] Schneuwly | Quartz clocks[END_REF], a succinct description of the resonator is given which allows us to compute an order of magnitude of our approach. The diameter of the resonant part of the resonator is around 20 mm, the electrodes diameter D is about 11 mm. The thickness of the resonator is chosen to vibrate on the OT 3 at 5 MHz. The acoustic velocity for the thickness shear C-mode of a SC-cut in quartz crystal is about 3610 m/s. Thus, the thickness at the center of the resonator 2h 0 is given by 3λ/2 formula and is approximately equal to 1.15 mm. The energy trapping is quasi-independent of the electrodes dimension, in contoured resonators. It influences the motional resistance and the static capacitor. The displacement can be computed from the center of the resonator to the external edge of the resonator. The radius of curvature is one of the most important parameter. Usually, sufficient energy trapping is obtained when the lateral boundary has no effect on the vibration. Thus, we will consider an attenuation of the mechanical displacement of about 10 -7 between the center and the boundary of the resonator. This trapping corresponds to a curvature radius R of about 290 mm (fig. 2).

Τhe Q factor of this kind of resonator can be found from the dissipative matrix η ij of the quartz crystal [START_REF] Lamb | Anisotropic acoustic attenuation with new measurements for quartz at room temperatures[END_REF]. These constants must be expressed in the SC-cut orientation. Then, the values are considered as the imaginary part of the effective elastic coefficients. Resolution of the Christoffel equations [START_REF] Bourquin | SC-cut resonator operating in anharmonic modes with B-mode reduction[END_REF] gives the complex eigenvalue η î c ˆ+ . Then, an order of magnitude of the Q factor can be obtained using the following equation:

X 3 f 2 ˆc Q π η = ( 2 6 )
In our case, . A SC-cut quartz crystal resonator, at 5 MHz, OT 3, gives a maximum of quality factor of about 2.8⋅10 6 . This value corresponds with the one given in [START_REF] Chauvin | A new generation of very high stability BVA oscillators[END_REF]. Consequently, we can compute the motional resistor R mot from the motional capacitance C mot using:

Q f 2 L f 2 QC 1 R mot mot mot π π = = ( 2 7 )
In the case of OT 3, C mot is given by [START_REF] Stevens | An analysis of doubly rotated quartz resonators utilizing essentially thickness modes with transverse variation[END_REF]: The computing value of C mot is around 280 fF. We obtain R mot equals to 42 Ω, L mot is about 3.6 H. These results are closed to the measured value in [START_REF] Chauvin | A new generation of very high stability BVA oscillators[END_REF].

The static capacitor C 0 can be also computed with the following formula [START_REF] Handel | Quantum 1/f effect in resonant biochemical piezoelectric and MEMS sensors[END_REF]: Table 1 presents the comparison between measurements and the results proposed by both models. For Planat's model, only the velocity of the C-mode of the acoustic wave is used to the computation. The result is really higher than the experiment. Using the acoustic volume in this model is not relevant because of the invert proportionality. (oscillator measurement) 3.75⋅10 -14

σ y_floor_exp [START_REF] Salzenstein | Significant step in ultra high stability quartz crystal oscillators[END_REF] (oscillator measurement) 2.5⋅10 -14

The flicker noise seems to be the limit of the short-term stability of a quartz crystal resonator. An order of magnitude of this limit is given by the previous calculus around 1.6 10 -14 with the Handel's model using the definition of the acoustic volume.

If it was possible to eliminate this noise, the noise limit should be given by the thermal noise of the resonator. In term of Allan standard deviation, its expression is usually [START_REF] Walls | Phase Noise "Fundamental limits on the frequency stabilities of crystal oscillators[END_REF]:

τ τ σ P 2 kT Q 1 ) ( L therm _ y = ( 32
)
With a loaded Q-factor Q L around 1.6⋅10 6 for the previous resonator and a excitation power of 60 µW, we get around T = 80°C: At 1s, without 1/f noise, the short-term stability limit should be 4⋅10 -15 .

V. CONCLUSION

Regarding the experimental results, the 1/f story of the quartz crystal is not over. The considered models should be the fundamental limit of the flicker noise of a resonator. Values of Handel's model are under the experimental measurements if the volume is considered as the acoustic volume. The experimental results seem to be now very close to the fundamental limit. The model validity could be proved by varying the acoustic volume while keeping the Q factor of the resonator constant.

Figure 1 .

 1 Figure 1. Geomeric definition of a plano-convex resonator

Figure 2 .

 2 Figure 2. Energy trapping of a plano-convex resonator, SC-cut 5 MHz, OT3, R = 290 mm. (red curve: along x 3 axis, green curve: along x 1 axis).

  With ε 22 = 39.78⋅10-12 F/m the permittivity constant in SCcut.We have C 0 around 3.4 pF. Short-term stability is usually given in the time domain with an Allan variance. The Allan variance is computed from the Fourier frequency and from the power spectral density of the frequency fluctuations[START_REF] Cutler | Some aspects of the theory and measurment of frequency fluctuations in frequency standards[END_REF]: of the flicker frequency noise (which is the resonator noise), relation between the Allan standard deviation and the power spectral density (PSD) of relative frequency fluctuations S y (f), is given by[START_REF] Sthal | Phase noise measurements of 10 MHz BVA quartz crystal resonators[END_REF]:

3 RESONATORFrequency

 3 COMPARISON OF THE SHORT-TERM STABILITY IN TERM OF ALLAN STANDARD DEVIATION σY_FLOOR OF A SC-CUT, 5 MHZ, OT

TABLE I .

 I

ACKNOWLEDGMENT

The authors thank M. Planat for his helpful discussion and the CNES for financial support of the work.


O Boussaid
email: boussaid@univ-lyon2.fr

F Bentayeb
email: bentayeb@eric.univ-lyon2.fr

J Darmont
email: jerome.darmont@univ-lyon2.fr

An MAS-Based ETL Approach for Complex Data

Keywords: Data integration, Complex data, ETL process, Multi-Agent Systems

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The data warehousing and OLAP (On-Line Analytical Processing) technologies [START_REF] Inmon | Building the data Data Warehouse[END_REF][START_REF] Kimball | The data warehouse toolkit[END_REF] are now considered mature in management applications, especially when data are numerical. With the development of the Internet, the availability of various types of data (images, texts, sounds, videos, databases...) has increased. These data, which may be structured or unstructured, are called "complex data". Structuring and exploiting these data is a difficult task and requires the use of efficient techniques and powerful tools to facilitate their integration into a data warehouse. It actually consists in Extracting and Transforming complex data before they are Loaded in the data warehouse (ETL process).

In this paper, we propose a new approach for complex data integration, based on a Multi-Agent System (MAS). Our approach consists in physically integrating complex data into a relational database (an ODS -Operating Data Storage) that we consider as a buffer ahead of the data warehouse. We are then interested in extracting, transforming and loading complex data into the ODS.

The aim of this paper is to take advantages of Multi-Agent Systems that are intelligent programs, composed of a set of agents, each one offering a set of services, to perform complex data integration. We can indeed assimilate the different tasks of the integration process, which is technically difficult, to services carried out by agents. Data extraction: This task is performed by an agent in charge of extracting data characteristics from complex data. The obtained characteristics are then transmitted to an agent responsible for data structuring. Data structuring: To perform this task, an agent deals with the organization of data according to a well-defined data model. Then, this model is transmitted to an agent responsible for data storage. Data storage: This task is performed by an agent that feeds the database with the source data, using the model supplied by the data structuring agent.

In order to validate this approach, we have designed an MAS for complex data integration. This system is composed of a set of intelligent agents offering the different services that are necessary to achieve the integration process of complex data. It is based on an evolutionary architecture that offers a great flexibility. Our system indeed allows to update the existing services or to add/create new agents.

The remainder of this paper is organized as follows. Section 2 presents a state of the art regarding data integration approaches and agent technology. In Section 3, we present the issue of complex data integration and our approach. We explain the advantages of MASs in Section 4 and show why they are adapted to carry out this approach via our proposed architecture. Finally, we conclude this paper and present research perspectives in Section 5.

State of the art

We present in this section an overview of the techniques our proposal relies on, namely those regarding data integration, the ETL (Extracting, Transforming, and Loading) process, and Multi-Agent Systems.

Data integration

Nowadays, two main and opposed approaches are used to perform data integration over the Web.

In the mediator-based approach [START_REF] Rousset | Knowledge representation for information integration[END_REF], the different data remain located at their original sources. The user is provided an abstract view of the data, which represents distributed and heterogeneous data as if they were stored in a centralized and homogeneous system. The user's queries are executed through a mediator-wrapper system [START_REF] Goasdoué | The use of CARIN language and algorithms for information integration: the PICSEL system[END_REF]. A mediator reformulates queries according to the content of the various accessible data sources. A wrapper is data source-specific, and extracts the selected data from the target source. The major interest of this approach is its flexibility, since mediators are able to reformulate and/or approximate queries to better satisfy the user. However, when the data sources are updated, modified data are lost, which is not pertinent in a decision support context where historicity is important.

On the opposite, in the data warehouse approach [START_REF] Inmon | Building the data Data Warehouse[END_REF][START_REF] Kimball | The data warehouse toolkit[END_REF], all the data from the various data sources are centralized in a new database, the data warehouse. The multidimensional data model of a data warehouse is analysis-oriented: data represent indicators (measures) that can be observed according to axes of analysis (dimensions). A data warehouse actually characterizes and is optimized for one given analysis context. In a data warehouse context, data integration corresponds to the ETL process that accesses to, cleans and transforms the heterogeneous data before they are loaded in the data warehouse. This approach supports the dating of data and is tailored for analysis. However, refreshing a data warehouse is a complex and time-consuming task that implies running a whole ETL process again each time an update is required.

ETL process

The classical ETL process, as its name hints, proceeds in three steps [START_REF] Kimball | The data warehouse toolkit[END_REF]. The first extraction phase includes understanding and reading the data source, and copying the necessary data in a buffer called the preparation zone. Then, the second transformation phase proceeds in several successive steps: clean the data from the preparation zone (syntactic errors, domain conflicts, etc.); discard some useless data fields; combine the data sources (by matching keys, for instance); create new keys for dimensional records to avoid using keys that are specific to data sources; and build aggregates to optimize the more frequent queries. In this phase, metadata are essential to store the transformation rules and various correspondences. Eventually, the third loading phase stores the prepared data into multidimensional structures (data warehouse or data marts). It also usually includes an indexing phase to optimize later accesses.

Multi-Agent Systems

An agent software is a classical program that is qualified as "intelligent". Intelligent agents are used in many fields such as networks, on-board technologies, human learning... An intelligent agent is supposed to have the following intrinsic characteristics: intuitive -it must be able to take initiatives and to complete the actions that are assigned to it; reactive -it must be aware of its environment and act in consequence; sociable -it must be able to communicate with other agents and/or users [START_REF] Klusch | Information agent technology for the internet: A sur-vey[END_REF]. Moreover, agents may be mobile and can independently move through an acceptor network in order to perform various tasks.

A Multi-Agent System designates a collection of actors that communicate with each other [START_REF] Sycara | Coordination of multiple intelligent software agents[END_REF]. Each actor is able to offer specific services and has a well-defined goal. This introduces the concept of service: each agent is able to perform several tasks, in an autonomous way, and communicates the results to a receiving actor (human or software). The MAS must respect the programming standards defined by the FIPA (Foundation for Intelligent Physical Agents) [FIP02].

MAS-based approach

for complex data ETL

Complex data integration approach

Data integration corresponds to the ETL phase in the data warehousing process. To achieve the integration of complex data, the traditional ETL approach is however not adapted. We present in this paper our approach to accomplish the extracting, transforming, and loading process on complex data in an original way.

In order to integrate complex data captured from the Web, for instance, into a decision support database such as a data warehouse, we have proposed a full modelling process (Figure 1). We first designed a conceptual UML model for a complex object representing a superclass of all the types of complex data we consider (text, multimedia documents, relational views from databases) [START_REF] Darmont | Warehousing web data[END_REF]. The UML conceptual model is then directly translated into an XML schema (DTD or XML-Schema), which we view as a logical model. The last step in our (classical) modelling process is the production of a physical model in the form of XML documents that are stored in relational database. We consider this database as an ODS (Operational Data Storage), which is a data repository that is typically used in a traditional ETL process before the data warehouse proper is constituted. However, note that our objective is not only to store data, but also to truly prepare them for analysis.

MAS-based prototype

The integration of complex data is more difficult than a classical ETL process. This technically difficult integration process requires a succession of tasks that we assimilate to services that may be carried out by agents. To effectively achieve this goal, we have designed an MAS-based prototype. Its architecture is presented in Figure 2. It is based on a platform of generic agents. We have instantiated five agents offering services that allow the integration of complex data. The purpose of this collection of agents is to perform several tasks. Each agent is able to offer specific services and has a well-defined goal.

The first main agent created in our prototype, MenuAgent, pilots the system, supervises agent migrations, and indexes the accessible sites from the platform. Some others default pilot agents help in the management of the agents and provide an interface for the agent development platform.

The essential of the integration process is achieved through services about collecting, structuring, generating and storing data, provided by the remaining agents we To develop our prototype, we have built a platform using JADE version 2.61 [START_REF] Jade | The java agent development framework[END_REF] and the Java language [START_REF]The Source for Java Technology[END_REF], which is portable across agent programming platforms. The prototype is freely available online [BE03].

Complex data ETL

Extracting

Recall that our modelling approach corresponds to the complex data integration process. The conceptual level helps the user selecting the data and establishing its analysis goals. The Extraction phase is thus carried out by the DataAgent agent that collects the data concerning the documents. This task consists in extracting the attributes of the complex object that has been se-lected by the user. A particular treatment is applied, depending on the subdocument class (image, sound, etc.), since each subdocument class bears different attributes. The DataAgent agent uses three ways to extract the actual data: (1) it communicates with the user through graphical interfaces, allowing a manual capture of data;

(2) it uses standard Java methods and packages; (3) it uses other ad-hoc automatic extraction algorithms [DBB + 02b]. Our objective is to progressively reduce the number of manually-captured attributes and to add new attributes that would be useful for later analysis and that could be obtained with data mining techniques. This work is completed by the WrapperAgent agent that instantiates the UML structure based on the data supplied by the DataAgent agent.

Transforming

The logical level coincides with the Transforming phase.

Our UML conceptual model is directly translated by the XML-Creator agent into an XML schema (DTD or XML-Schema), which we view as a logical model. XML is the format of choice for both storing and describing the data. The schema indeed represents the metadata. XML is also very interesting because of its flexibility and extensibility, while allowing straight mapping into a conventional database if strong structuring and retrieval efficiency are needed for analysis purposes.

Loading

The last level in our modelling process corresponds to the Loading phase. It consists in the production of a physical model in the form of XML documents and their loading into a relational database. This is achieved by the XMLCreator and XML2RDBAgent agents. The principle of the XMLCreator agent's service is to parse the XML schema recursively, fetching the elements it describes, and to write them into the output XML document, along with the associated values extracted from the original data, on the fly. Missing values are currently treated by inserting an empty element, but strategies could be devised to solve this problem, either by prompting the user or automatically. The XML documents obtained with the help of the XMLCreator agent are mapped into a relational database by the XML2RDBAgent agent. It operates in two steps. First, a DTD parser exploits our logical model (XML schema) to build a relational schema, i.e., a set of tables in which any valid XML document (regarding our DTD) can be mapped. To achieve this goal, we mainly used the techniques proposed by [ABK + 00, KKR00]. Note that our DTD parser is a generic tool: it can operate on any DTD. It takes into account all the XML element types we need, e.g., elements with +, *, or ? multiplicity, element lists, selections, etc. The last and easiest step consists in loading the valid XML documents into the previously build relational structure.

Justification

The variety of data types (images, texts, sounds, videos, databases...) increases the complexity of data. It is thus necessary to structure them in an "un-classical" way. Because data are complex, they necessitate more information. Furthermore, it is im-portant to consider this information and to represent it in the form of metadata. Then, the choice of the XML formalism is fully justified. Since our proposal is based on a classical modelling process, it allows the user to determine what are his/her analysis objectives, to select how to represent the data and how to store them into a database. It constitutes a whole process permitting to carry out the integration of complex data. This is also the objective of the ETL process.

Our proposed process necessitates several tasks that must be performed, repetitively. These tasks are not necessarily sequential, and are assimilated to services offered by well-defined agents in a system intended to achieve such an integration process. With this goalin mind, we have developed a MASbased prototype that is based upon a flexible and evolutive architecture on which we can updated services, and even create new agents to consider data refreshing, analysis and so on.

Conclusion and Perspectives

In this paper, we have proposed a new approach for complex data integration based on both the data warehouse technology and multi-agent systems. This approach is based on a flexible and evolutive architecture on which we can add, remove or modify services, and even create new agents. We then developped a MAS-based prototype that allows this integration with respect to the following three steps of the ETL process. Two agents named DataAgent and WrapperAgent, respectively, model the input complex data into UML classes. The XMLCreator agent translates UML classes into XML documents that are mapped in a relational database by the XML2RDBAgent agent. Moreover, note that the different agents that compose our system are mobile and that the services they propose coincide with the ETL asks of the data warehousing process.

We plan to extend the services offered by our MAS-based prototype, especially for extracting data from their sources and analyzing them. For example, the DataAgent agent could converse with on-line search engines and exploit their answers. On the other hand, we could also create new agents in charge of modelling data multidimensionally in order to apply analysis methods such as OLAP or data mining.

Figure 1 :

 1 Figure 1: Classical modelling process for complex data integration

Figure 2 :

 2 Figure 2: MAS-based ETL architecture for complex data integration


Kamel Aouiche
email: kaouiche@eric.univ-lyon2.fr

Jérôme Darmont
email: jdarmont@eric.univ-lyon2.fr

Le Gruenwald
email: ggruenwald@ou.edu

Frequent itemsets mining for database auto-administration

With the wide development of databases in general and data warehouses in particular, it is important to reduce the tasks that a database administrator must perform manually. The aim of auto-administrative systems is to administrate and adapt themselves automatically without loss (or even with a gain) in performance. The idea of using data mining techniques to extract useful knowledge for administration from the data themselves has existed for some years. However, little research has been achieved. This idea nevertheless remains a very promising approach, notably in the field of data warehousing, where queries are very heterogeneous and cannot be interpreted easily. The aim of this study is to search for a way of extracting useful knowledge from stored data themselves to automatically apply performance optimization techniques, and more particularly indexing techniques. We have designed a tool that extracts frequent itemsets from a given workload to compute an index configuration that helps optimizing data access time. The experiments we performed showed that the index configurations generated by our tool allowed performance gains of 15% to 25% on a test database and a test data warehouse.

Introduction

Large-scale usage of databases requires a Database Administrator (DBA) whose principal role is data management, both at the logical level (schema definition) and the physical level (files and disk storage), as well performance optimization. With the wide development of Database Management Systems (DBMSs), minimizing the administration function has become critical to achieve acceptable response times even at load peaks [START_REF] Weikum | Selftuning database technology and information services: from wishful thinking to viable engineering[END_REF]. One important DBA task is the selection of suitable physical structures to improve the system performances by minimizing data access time [START_REF] Finkelstein | Physical database design for relational databases[END_REF].

Indexes are physical structures that allow a direct access to the data. From the DBA's point of view, performance op-timization lies mainly in the selection of indexes and materialized views [START_REF] Agrawal | Materialized view and index selection tool for Microsoft SQL Server[END_REF][START_REF] Gupta | Selection and maintenance of views in a data warehouse[END_REF]. These physical structures play a particularly significant role in decision-support databases such as data warehouses due to their huge volume and complex queries.

The problem of selecting an optimal index set for a database has been studied since the seventies. The most recent studies regarding index selection use the DBMS' query optimizer to estimate the cost of various configurations of candidate indexes [START_REF] Agrawal | Automated selection of materialized views and indexes in SQL databases[END_REF][START_REF] Chaudhuri | An efficient cost-driven index selection tool for Microsoft SQL Server[END_REF][START_REF] Chaudhuri | Autoadmin 'what-if' index analysis utility[END_REF][START_REF] Frank | Adaptive and automated index selection in RDBMS[END_REF]. However, the idea of using data mining techniques to extract useful knowledge for administration from the data themselves has been around for some years [START_REF] Chaudhuri | Data mining and database systems: Where is the intersection?[END_REF]. Little work has been done, though. In this paper, we designed and coded a tool that exploits data mining to recommend a relevant index configuration.

Assuming that index utility is strongly correlated to the usage frequency of the corresponding attributes within a given workload, the search for frequent itemsets [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] appeared well adapted to highlight this correlation and facilitate index selection. Our tool parses the transaction log file (the set of queries executed by the DBMS) to build a context for mining frequent itemsets. This context connects queries from the input workload to the attributes that may be indexed. The output frequent itemsets are sets of attributes forming a configuration of candidate indexes. Finally, various strategies can be applied to select the indexes to effectively build from within this configuration.

In the remainder of this paper, we present our proposal in Section 2 and some preliminary experimental results in Section 3, and then finally conclude the paper and present future research perspectives in Section 4.

Frequent itemsets mining for index selection 2.1 Principle

Our approach exploits the transaction log to extract an index configuration. The queries from the transaction log constitute a workload that is treated by an SQL query analyzer. The SQL query analyzer extracts all the attributes that may be indexed (indexable attributes). Then, we build a "query-attribute" matrix, the rows of which are the workload queries, and the columns are the indexable attributes. The role of this matrix is to link each indexable attribute to the workload queries it appears in.

This matrix represents the extraction context for frequent itemsets. To compute these frequent itemsets, we selected the Close algorithm [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF][START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF], because its output is the set of the frequent closed intemsets (closed regarding the Galois connection [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF]), which is a generator for all the frequent itemsets and their support. In most cases, the number of frequent closed itemsets is much lower than the total number of frequent itemsets obtained by classical algorithms such as Apriori [START_REF] Agrawal | Fast algorithms for mining association rules[END_REF]. In our context, using Close enables us to obtain a smaller (though still significant) configuration of candidate indexes faster.

Finally, we select from the configuration of candidate indexes (that corresponds to the input workload) the most relevant indexes and create them.

Workload extraction

We assume that a workload similar to the one presented in Figure 1 is available. Such a workload can be easily obtained either from the DBMS' transaction logs, or by running an external application such as Lumigent's Log Explorer [START_REF]Log Explorer for SQL Server[END_REF].

Indexable attributes extraction

To reduce response time when running a database query, it is best to build indexes on the very attributes that are used to process the query. These attributes belong to the WHERE, ORDER BY, GROUP BY, and HAVING clauses of SQL queries [START_REF] Chaudhuri | An efficient cost-driven index selection tool for Microsoft SQL Server[END_REF].

We designed a syntactic analyzer that is able to operate on any SQL query type (selections and updatessubqueries are allowed), and extracts all the indexable attributes. This process is applied to all the queries from the workload.

Building the extraction context for the frequent closed itemsets

We build a matrix (Figure 2) the rows of which represent the workload queries, and the columns represent the set of all the indexable attributes identified in the previous step. This "query-attribute" matrix links each query to the indexable attributes within it. Attribute presence in a query is symbolized by 1, and absence by 0.

Attributes

Queries A B C D E Q1 1 0 1 1 0 Q2 0 1 1 0 1 Q3 1 1 1 0 1 Q4 0 1 0 0 1 Q5 1 1 1 0 1 Q6 0 1 1 0 1 Figure 2. Sample extraction context

Frequent closed itemsets mining

The Close algorithm scans in breadth first a lattice of closed itemsets in order to extract the frequent closed itemsets and their support. Its input is an extraction context such as the one presented in Figure 2.

Intuitivelty, a closed itemset is a maximal set of items (attributes) that are common to a set of transactions (queries). For instance, in Figure 2's extraction context, the BCE itemset is closed because it is the largest set of common attributes for the set of queries {Q2, Q3, Q5, Q6}. On the other hand, the BC itemset is not closed since all the queries containing attributes B and C (Q2, Q3, Q5, and Q6) also contain attribute E. Eventually, a closed itemset is said frequent when its support is greater or equal to a threshold parameter named minsup (minimal support).

The application of Close on the context presented in Figure 2 outputs the following set of frequent closed itemsets (and their support) for a minimal support equal to 2/6: {(AC, 3/6), (BE, 5/6), (C, 5/6), (ABCE, 2/6), (BCE, 4/6)}.

We consider this set as our configuration of candidate indexes.

Indexes construction

The higher the size of the input workload is, the higher the number of candidate indexes obtained with our approach becomes. Thus, it is not feasible to build all the proposed indexes. Index creation time, and later update time, would both be too costly. Hence, it is necessary to devise filtering methods or processes to reduce the number of indexes to generate.

The first naive method is to build all the candidate indexes. This method is only applicable when the number of indexes is relatively small. In that particular case, creation and update times remain acceptable.

In the context of decision-support databases, and more particularly, of data warehouses, building indexes is a fundamental issue because of the huge volume of data stored in fact tables and some dimension tables. Thus, it is more critical to build indexes on large tables. Index contribution on small tables can indeed prove negligible, and even sometimes, costly.

Statistical input, such as the cardinality of the attributes to be indexed, may also be exploited to build indexes. An attribute's cardinality is the distinct number of values for this attribute within a given relation. Depending on the cardinality, indexing may be more or less efficient. If the cardinality is very large, an index degenerates toward a sequential scan (of the index structure itself); and if it is very small, an index might not bring a very significant improvement [START_REF] Vanichayobon | Indexing techniques for data warehouses' queries[END_REF]. Hence, the best choice might be to build indexes on attributes with an "average" cardinality.

In this first study, we took a particular interest in table sizes. We indeed established two strategies to build indexes from the union of the frequent closed itemsets provided by Close. The first strategy systematically builds all the proposed indexes (naive method). In this case, each frequent closed itemset corresponds to an index to be created. The second strategy takes the size of the tables an index refers to into account. In this case, the DBA must define whether a table is large or not, and only indexes on attributes from these large tables are built.

Comparison with the existing methods

Unlike the index selection methods that have been recently developed, the tool that we propose does not communicate with the DBMS' query optimizer. The communication between the index selection tool and the optimizer is usually costly and must be minimized. An index configuration computing time is indeed proportional to the size of the workload, which is typically large. Our method based on frequent itemsets mining is also greedy in terms of computing time, but it is currently difficult for us to determine which approach generates the heaviest overhead for the system.

However, we are more interested in the quality of the generated indexes. For instance, the Index Selection Tool (IST) developed by Microsoft within the SQL Server DBMS [START_REF] Chaudhuri | An efficient cost-driven index selection tool for Microsoft SQL Server[END_REF] exploits a given workload and provides a configuration of mono-attribute candidate indexes. A greedy algorithm selects the best indexes from this configuration, using estimated costs computed by the query optimizer. The process then reiterates to generate two-attribute indexes using the mono-attribute indexes, and similarly, to generate multiattribute indexes of higher order. By mining frequent closed itemsets, our tool directly extracts a set of mono-attribute and multi-attribute indexes. Hence, we do not build an initial mono-attribute index configuration a priori, and we do not need to use any heuristic to build multi-attribute candidate indexes by successive iterations like IST. We believe that this approach avoids the generation and cost evaluation of irrelevant indexes.

Experiments

In order to validate our approach, we have applied it on a test database and a test data warehouse. Our objective here is more to find out whether our proposal makes sense in practice than to perform true performance tests.

We have chosen the TPC-R decision-support benchmark [START_REF]TPC Benchmark R Standard Specification[END_REF] for our experiments on a relational database because it is a standard that should allow us to easily compare our approach to the other existing methods in the future. We have generated the TPC-R 1 GB database and used the benchmark's 22 read-only queries (labeled Q1 to Q22). In this first experiment, we suppose refresh operations occur off-line. However, in order to take index management overhead into account, future performance tests will also include TPC-R's RF1 and RF2 refresh functions.

On the other hand, to the best of our knowledge, there is no standard benchmark for data warehouses yet (TPC-DS is still in development [START_REF] Poess | TPC-DS: Taking decision support benchmarking to the next level[END_REF]). Hence, we worked on a small datamart that had been previously developed in our laboratory. This accidentology datamart is composed of an Accident fact table and four dimension tables: Place, Condition, Date and PersonResponsible. It occupies 15 MB on disk. Starting from our previous analyses on this datamart, we also designed a realistic decision-support workload that is specifically adapted to it. This workload includes both selection and update operations. We cannot present it in detail here due to lack of space; interested readers are referred to [START_REF] Aouiche | Accidentology datamart schema and workload[END_REF].

Both the TPC-R database and the accidentology datamart have been implanted within the SQL Server 2000 The test protocol we adopted is presented in Figure 3. This algorithm has been executed for various values of the Close minsup (minimal support) parameter. In practice, this parameter helps us limiting the number of indexes to generate by selecting only those that are the most frequently used by the workload. At each step corresponding to a value of minsup, we compute the mean response time for the input workload.

Experiments on TPC-R

The results we obtained are presented in Figure 4 and5. The results from Figure 4 correspond to the creation of all the candidate indexes obtained with Close, while the results of Figure 5 correspond to a filter on this configuration (indexes on large tables only; cf. Section 2.6).

Figure 5. TPC-R results -Indexes on large tables

Figure 4 and 5 show that, in comparison with a sequential scan with no indexes, we achieve a gain in performance for the two strategies regardless of the value of minsup. The maximum response time gain, which is computed as the difference between the mean response time without indexes and the lowest mean response time with indexes, is close to 22% in the first case and 25% in the second case. The average response time gains computed over all values of minsup are 14.4% and 13.7% in the first and second case, respectively. In the first case, the response time improves until minsup reaches 15%, and then degrades at a steady rate, while in the second case, it remains at its lower value in a broader range (from 20% minsup to 50% minsup) before degrading abruptly. The large number of indexes to be generated in the first case can explain this behavior. Considering only indexes associated with large tables helps reducing the number of generated indexes and avoids index creation for small tables (since they induce a low benefit).

Finally, for high values of minsup, the mean response time becomes close to that obtained without generating any index in both cases. This was predictable since for a very high minsup, no or very few indexes are actually generated. In the second case, this state is reached sooner since fewer indexes are built, which explains the lower average gain.

Data warehouse experiments

For this series of experiments, we applied the same protocol (Figure 3). However, we did not employ the large table index creation strategy since all the tables in our test datamart have similar sizes.

The results we obtained are presented in Figure 6. The maximum gain in performance is close to 15% while the average gain is 6.4%. Figure 6 shows that building indexes is actually more costly than not building them for minsup values ranging between 10% and 25%. This may be explained by the high number of generated indexes, and thus a high index generation time. Furthermore, since the 15 MB datamart is stored completely in the main memory, the indexes are useful only when it is first loaded. In this context, many sparsely used indexes must also be loaded, which penalizes global performance.

Figure 6. Accidentology datamart results

The best gain in response time appears for minsup values ranging between 30% and 85%, when the number of indexes is such that the index generation overhead is lower than the performance increase achieved when loading the datamart. Beyond that point, response time degrades and becomes close to that obtained without indexes because there are a few or no indexes to generate.

Another possible explanation to the lower performances obtained for our datamart, in comparison to the results achieved on the TPC-R database, may come from the structure of the created indexes. Bitmap and star-join indexes are best adapted to data warehouses [START_REF] Neil | Multi-table joins through bitmapped join indices[END_REF][START_REF] Neil | Improved query performance with variant indexes[END_REF], while the default indexes in SQL Server are variants of B-trees.

Conclusions and perspectives

We presented in this paper a novel approach for automatic index selection in DBMSs. The originality of our study rests on the extraction of frequent itemsets to determine an index configuration. Indeed, we assume that the importance of an indexable attribute is strongly correlated with its frequency of appearance in the workload's queries. In addition, the use of a frequent itemsets mining algorithm such as Close enables us to generate mono-attribute and multi-attribute indexes on the fly, without having to implement an iterative process that successively creates increasingly large multi-attribute indexes based on an initial set of mono-attribute indexes.

Our first experimental results show that our technique indeed allows response time improvements of 20% to 25% for a decision-support workload applied to a relational database (TPC-R benchmark). We also proposed two strategies to carry out an index selection among the candidate indexes: the first strategy systematically creates all the candidate indexes, while the second only creates the indexes that are related to so-called large tables. The second strategy allows better performance improvements because it proposes a better compromise between the space occupied by the indexes (the number of created indexes is limited to those that are defined on attributes from large tables) and the use of creating an index (it is not beneficial to create an index on a small table).

We also performed tests on an accidentology datamart, on which we applied an ad hoc decision-support workload. The gain in response time, about 14%, is less significant than in the case of TPC-R. This can be explained by the fact that the default indexes created by SQL Server are B-tree variants and not bitmap or star-join indexes, which would be better adapted for a data warehouse.

Our study shows that using data mining techniques for DBMS auto-administration is promising. However, it is only a first approach and it opens up many prospects for research. Our first research perspective is to improve index selection by designing more elaborated strategies than the exhaustive use of a configuration or the exploitation of relatively basic information relating to table sizes. A more accurate cost model regarding table features (other than size), or a strategy for weighting the workload's queries (by type of query: selection or update), could help us. The use of other unsupervised data mining methods such as clustering could also provide smaller sets of frequent itemsets.

It also appears essential to test our method further to bet-ter evaluate the overhead it generates, both in terms of indexes generation time and maintenance time. In particular, it is necessary to apply it on large data warehouses, while exploiting adapted indexes. It would also be very interesting to compare it in a more systematic way to the IST tool that has been developed by Microsoft, either through complexity computations of the index configuration generation heuristics (overhead), or by experiments aiming at evaluating the quality of these configurations (response time improvement and overhead due to index maintenance).

Extending or coupling our approach with other performance optimization techniques (materialized views, buffer management, physical clustering, etc.) also constitutes a promising research perspective. Indeed, in the context of data warehouses, it is mainly in conjunction with other physical structures (primarily materialized views) that indexing allows the most significant performance gains [START_REF] Agrawal | Automated selection of materialized views and indexes in SQL databases[END_REF][START_REF] Agrawal | Materialized view and index selection tool for Microsoft SQL Server[END_REF][START_REF] Gupta | Selection and maintenance of views in a data warehouse[END_REF].

Finally, it would also be interesting to study how algorithms for mining functional dependencies [START_REF] Lopes | Efficient discovery of functional dependencies and Armstrong relations[END_REF] or inclusion dependencies [START_REF] Marchi | Efficient algorithms for mining inclusion dependencies[END_REF] in databases might be exploited in our context. Many join operations (natural joins) are indeed carried out following inclusion dependencies (concept of foreign key). Discovering hidden dependencies within the data could thus help us generating relevant indexes or materialized views without needing an input workload.

Q1:Figure 1 .

 1 Figure 1. Sample workload

Figure 3 .

 3 Figure 3. Test protocol


Fadila Bentayeb

Jérôme Darmont

Cédric Udréa

Efficient Integration of Data Mining Techniques in Database Management Systems

Keywords: Databases, Data mining, Supervised machine learning, Decision trees, Contingency table, Performance

In this paper, we propose a new approach for applying data mining techniques, and more particularly supervised machine learning algorithms, to large databases, in acceptable response times. This goal is achieved by integrating these algorithms within a Database Management System. We are thus only limited by disk capacity, and not by available main memory. However, the disk accesses that are necessary to scan the database induce long response times. Hence, we propose an original method to reduce the size of the learning set by building its contingency table. The machine learning algorithms are then adapted to operate on this contingency table. In order to validate our approach, we implemented the ID3 decision tree construction method and showed that using the contingency table helped us obtaining response times equivalent to those of classical, in-memory software.

Introduction

The application of data mining operators to very large databases is an interesting challenge. However, data mining algorithms usually operate only on main memory data structures, more precisely on attributevalue tables. This limits the size of the processed databases. Traditional data mining approaches thus use techniques for preprocessing the data, such as feature selection [START_REF] Lia | Feature Selection for knowledge discovery and data mining[END_REF] or sampling [START_REF] Chauchat | A new sampling strategy for building decision trees from large databases[END_REF].

In order to apply data mining algorithms to large databases, several approaches have been proposed. They consist in integrating data mining meth-ods in Database Management Systems (DBMSs) [START_REF] Chaudhuri | Data mining and database systems: Where is the intersection?[END_REF]. The first studies about integrating data analysis methods into DBMSs came with the development of data warehousing and On-Line Analysis Processing (OLAP) in particular [START_REF] Codd | Providing OLAP (On-Line Analytical Processing) to user-analysts: An IT mandate[END_REF]. Other related research efforts include the generation of association rules and their generalization [START_REF] Agrawal | Fast discovery of association rules[END_REF][START_REF] Meo | A new SQL-like operator for mining association rules[END_REF][START_REF] Sarawagi | Integrating mining with relational database systems: Alternatives and implications[END_REF]. However, few studies exist regarding the integration of classical data mining or analysis techniques such as clustering. In this domain, research indeed principally focuses on improving data mining methods for large databases [START_REF] Gehrke | Rainforest -a framework for fast decision tree construction of large datasets[END_REF]. Nevertheless, most DBMS vendors included data mining features into their products [START_REF]DB2 intelligent miner scoring[END_REF][START_REF] Oracle | Oracle 9i data mining[END_REF][START_REF] Soni | Performance study of Microsoft data mining algorithms[END_REF]. However, these integration attempts all took the form of "black boxes" requiring either extensions of the SQL language or the use of Application Programming Interfaces (APIs).

Hence, we proposed a different approach for integrating decision tree-like data mining methods, using only the tools offered by DBMSs [START_REF] Bentayeb | Decision tree modeling with relational views[END_REF]. More precisely, we implemented the ID3 method [START_REF] Quinlan | Induction of decision trees[END_REF] within the Oracle DBMS as a PL/SQL stored procedure, by exploiting relational views. We showed that we could process very large databases with this approach, theoretically without any size limit, while classical, in-memory data mining software could not. However, processing times remained quite long because of multiple accesses to the database.

In order to improve these processing times, preparing the data before the data mining process becomes crucial. In this paper, we propose an original method to achieve this goal. We build a contingency table, i.e., a table that contains the frequencies and whose size is normally much smaller than the whole training set. The data mining methods are then adapted so that they can apply to this contingency table. To the best of our knowledge, no data mining method currently uses such a data preparation phase.

To illustrate and validate our approach, we adapted our first implementation of ID3 and applied it to the contingency table obtained from a given training set. We show that using the contingency table allows clear improvements in terms of processing time, in comparison to our first, view-based implementation of ID3. Moreover, the processing times we achieve by using a contingency table are equivalent to those of classical, in-memory data mining software.

The remainder of this paper is organized as follows. Section 2 explains the principle of integrating decision tree-based methods within DBMSs. Section 3 details our contingency table-based decision tree construction method. Section 4 presents the experimental results and the complexity study that validate our proposal. Finally, Section 5 concludes this paper and presents research perspectives.

Integrating decision tree-based methods in DBMSs

Principle of decision trees

Decision trees are data mining models that produce "if-then"-like rules. They take as input a set of objects (tuples, in the relational databases vocabulary) described by a collection of variables (attributes). Each object belongs to one of a set of mutually exclusive classes. The induction task determines the class of any object from the values of its attributes. A training set of objects whose class is known is needed to build the tree. Hence, a decision tree building method takes as input a set of objects defined by predictive attributes and a class attribute, which is the attribute to predict.

These methods apply successive criteria on the training population to obtain a succession of smaller and smaller partitions of an initial training set, wherein the size of one class is maximized. This process builds a tree, or more generally a graph. Rules are then produced by following the paths from the root of the tree (whole population) to the different leaves (groups wherein the one class represents the majority in the frequency). Figure 1 provides an example of decision tree with its associated rules, where p(Class #i) is the probability of objects to belong to Class #i.

Decision tree modelling with relational views

In our first integrated approach [START_REF] Bentayeb | Decision tree modeling with relational views[END_REF], the key idea is to associate each node in the decision tree with its cor-responding relational view. Hence, the root node of the decision tree is represented by a relational view corresponding to the whole training dataset. Since each subnode in the decision tree represents a sub-population of its parent node, we build for each node a relational view that is based on its parent view. Then, these views are used to count the frequency of each class in the node with simple GROUP BY queries. These counts are used to determine the criteria that helps either partitioning the current node into a set of disjoint sub-partitions based on the values of a specific attribute or concluding that the node is a leaf, i.e., a terminal node. To illustrate how these views are created, we represent in Figure 2 the SQL statements for creating the views associated with the sample decision tree from Figure 1. This set of views constitutes the decision tree.

In order to validate this approach, we implemented the ID3 method within the Oracle DBMS as a PL/SQL stored procedure named V iew ID3. We showed that we could process very large databases with this approach, theoretically without any size limit, while classical, in-memory data mining software could not. We compared V iew ID3 to the in-memory ID3 implementation from the Sipina data mining software [START_REF] Rakotomalala | Sipina research[END_REF]. These results are presented in Figure 3, where the classical ID3 implementation is labelled Sipina ID3. Figure 3 shows that processing times remain quite long because of multiple accesses to the database. To reduce these processing times, we propose in this paper a new approach that uses a contingency table.

Contingency table-based decision tree construction

A contingency table is usually represented by means of a multidimensional table of frequencies that may contain NULL values. In our approach, since data mining algorithms are integrated within DBMSs and hence operate onto relational data structures, we represent contingency tables with relational tables or views that include an additional attribute to represent non NULL frequency values. set (and at most as large as the training set). Therefore, the gain in terms of processing time is normally significant.

Construction of the contingency table

Running example

To illustrate our approach, we use the TITANIC training set, which contains 2201 tuples defined by:

• three predictive attributes:

-Class (1st, 2nd, 3rd, Crew), -Age (Adult, Child), -Gender (Male, Female);

• one class attribute: Survivor (Yes, No).

A sample from the TITANIC training set is provided in Table 1.

The classical contingency table corresponding to the TITANIC training set is provided in Table 2. Its relational representation is obtained with a simple SQL query (Figure 5). Its result contains only 24 tuples (Table 3).

Entropy and information gain

In the ID3 algorithm [START_REF] Quinlan | Induction of decision trees[END_REF], the discriminating power of an attribute for segmentating of a node of the de-cision tree is expressed by a variation of entropy. The entropy h s of a node s k (more precisely, its entropy of Shannon) is:

h s (s k ) = - c i=1 n ik n k log 2 n ik n k (1)
where n k is the frequency of s k and n ik the number of objects of s k that belong to class C i . The information carried by a partition S K of K nodes is then the weighted average of the entropies:

E(S K ) = K k=1 n k n j h s (s k ) (2)
where n j is the frequency of the segmented node s j . Finally, the information gain associated to S K is

G(S K ) = h s (s j ) -E(S K ) (3)

New formula for information gain

To show that our approach is efficient and pertinent, we adapted the ID3 method to apply to a contingency table. This induces changes for computing the information gain for each predictive attribute, and consequently for computing the entropy. To compute the information gain for a predictive attribute, our view-based ID3 implementation reads all the tuples in the whole partition corresponding to the current node of the decision tree, in order to determine the tuple distribution regarding the values of each predictive attribute value and the class attribute. In our contingency table-based approach, it is quite simple to obtain the size of a subpopulation satisfying a given set of rules E r (e.g., Age = Child AN D Gender = F emale) by summing the values of the Frequency attribute from the contingency table, for the tuples that satisfy E r . Hence, we reduce the number of read operations to one only to calculate the information gain for a predictive attribute. Indeed, as presented in section 3.3, the usual calculation of the information gain for an attribute having k possible values and with a class attribute having c possible values is:

G(S K ) = h s (s j ) - K k=1 n k n j × - c i=1 n ik n k × log 2 n ik n k (4)
where n j is the node frequency, n k is the frequency of the subnode having value V k for the predictive attribute, n ik is the frequency of the subnode partition having value V k for the predictive attribute and value C i for the class attribute. However, if we develop For-mula 4, and since log 2 a b = log 2 a -log 2 b, by adding up n ik and n k , we obtain:

G(S K ) = h s (s j )+ 1 n j × K k=1 c i=1 n ik × log 2 n ik - K k=1 n k × log 2 n k
(5) By applying Formula 5 to the contingency table (that we read only once), we obtain the information gain easily. Indeed, in this formula, it is not necessary to know at the same time various frequency (n j , n k , n ik ), and we obtain n k by summing the n ik and n j by summing the n k .

Validation

Implementation

We use Oracle to implement our adaptation of ID3 to contingency tables, under the form of a PL/SQL stored procedure named CT ID3, which is part of a broader package named decision tree that is available on-line1 . We have tested this implementation under Oracle version 8i and 9i.

Class Age Gender

Experimental results

In order to validate our contingency table-based approach and to compare its performances to those of the previous approaches, we carried out tests on different views of the CovType database2 . The CovType database contains 581 012 tuples defined by 54 predictive attributes and one class (with seven different values). We created five views containing each a part of the Covtype database defined by three predictive attributes (each has five different values) and the class. The predictive attributes used and the size for each view are provided in Table 4.

First, we compare the processing times of our ID3 implementations (the view-based approach V iew ID3 and the contingency table-based approach CT ID3). 6) clearly underline the gain induced by CT ID3, that has a much lower processing time than V iew ID3 on an average, while producing the same result. Then, we compare the processing times of CT ID3 to the ID3 implementation available in Sipina (Sipina ID3). On small databases, we observe that our contingency table-based approach presentes similar processing times than Sipina ID3. Furthermore it can also process larger databases while Sipina ID3 remains limited by main memory (Figure 7).

The processing time of our approach depends mainly on the size of the contingency table. In conclusion, we hint the effectiveness of our approach, since it generally considerably reduces the size of the training set. Thus, the use of a contingency table as an optimization tool within the framework of integrating data mining methods in DBMSs improves processing times sig- nificantly. Nevertheless, in extreme cases, the size of the contingency table may be so close to that of the whole training set that the profit becomes negligible. However, this is very rare in real-life cases and scanning the contingency table can never be worse than scanning the whole database.

Complexity study

Our objective is to compare the complexity of our both integrated approaches (CT ID3 and V iew ID3) in terms of processing time. We suppose that both algorithms are optimized in their implementation so that only the necessary tuples are read. In this study, we are interested in the time spent reading and writing data, since these are the most expensive operations. We consider that a tuple is read or written in one time unit. Finally, we consider that the obtained decision tree is balanced and whole, i.e., that at each level of the tree, the union of the populations of the various nodes equals the whole database.

Let N be the total number of tuples in the training set. Let K be the number of predictive attributes. Let T be the size of the corresponding contingency table.

With V iew ID3, to reach level i+1 from an unspecified level i of the tree, each node must be read as many times as there are predictive attributes at this level, i.e., (K -i). As the sum of the frequencies at this level corresponds to the frequency of the starting database, it is thus necessary to read N tuples (K -i) times (number of tuples × size of a tuple × number of attributes). Hence, the total reading time for level i is N (K -i).

In order to reach this level, it is also necessary to write the corresponding tuples. The writing time is thus N . Since K i=1 i = K(K + 1)/2, we obtain the following final complexity, from the root to the leaves (level K):

• reading complexity: N (K 2 /2 -K/2) time units, therefore N K 2 ;

• writing complexity: N K time units. In our contingency table-based approach, we first create the contingency table the writing time is thus T . To compute the contingency table, we read the whole database once. The reading time is thus N . When reaching level i + 1 from level i, we read all the T tuples (K -i) times, for a total time by level of T (K -i).

Hence, with CT ID3, the complexity results are:

• reading complexity:

T (K 2 /2 -K/2) + N time units, therefore T K 2 or N if N > T K 2 ;
• writing complexity: T time units.

In conclusion, in terms of processing time, our contingency table-based approach allows an improvement of N/T or K 2 (if N > T K 2 ) for reading, and of N K/T for writing. Since N is usually much greater than T , this improvement is significant.

Conclusion and Perspectives

In order to apply data mining algorithms to large databases, two main approaches are proposed in the literature: the classical approach and the integrated approach. The classical approach is limited by the size of the processed databases since it operates in main memory. The main objective in this approach is then to reduce the size of databases, either by using techniques for preprocessing data or by sampling. The integrated approach consists in processing data mining methods within DBMSs using only the tools offered by these systems. By exploiting their management of persistent data, the database size limit is toppled. Our first contribution in this domain was the integration of the ID3 method within Oracle by means of relational views associated to the nodes of a decision tree (V iew ID3) [START_REF] Bentayeb | Decision tree modeling with relational views[END_REF]. However, creating and exploiting views generates multiple accesses to the database, and hence long processing times.

Following the integrated approach, we proposed in this paper an original method to apply data mining algorithms by taking into account not only the size of processed databases, but also processing time. Our key idea consists in replacing the whole training set by its contingency table represented by means of a relational view. Our approach presents two advantages. First, it is easy to build this contingency table with a simple SQL query. Second, the size of the contingency table is much smaller than the whole training set in most practical cases.

To validate our approach, we implemented the ID3 method as a PL/SQL stored procedure named CT ID3, and showed that processing times were greatly improved in comparison to V iew ID3. We also showed that the performances of CT ID3 were comparable to those of a classical, in-memory implementation of ID3.

The perspectives opened by this study are numerous. In order to enrich our decision tree software package, we are currently implementing other data mining methods, such as C4.5 and CART, using contingency tables. Moreover, we plan to compare the performances of these implementations to their equivalent in the Sipina software (that operate in memory) on real-life databases. Moreover, we plan to add in the decision tree package other procedures to supplement the offered data mining tools, such as sampling, missing values management, and learning validation tech-

Figure 2 .

 2 Figure 2. Relational views associated to the sample decision tree

Figure 3 .Figure 4 .

 34 Figure 3. Performance comparison of V iew ID3 and Sipina ID3

Figure 6 .

 6 Figure 6. Performance comparison of CT ID3 and V iew ID3

Figure 7 .

 7 Figure 7. Performance comparison of CT ID3 and Sipina ID3

  Within a DBMS, the contingency table corresponding to a given training dataset can be computed by a simple SQL query. Let T S be a training set defined by n predictive attributes A 1 , . . . , A n and the class attribute C. The associated contingency table CT is obtained by running the SQL query displayed in Figure4.Since the contingency table contains frequencies, its size is usually much smaller than the whole training

				Node #0	Class #1: 50 (50%)
					Class #2: 50 (50%)
				att1 = A	att1 = B
			Node #1.1	Class #1: 20 (33%)	Class #1: 38 (95%)	Node #1.2
				Class #2: 40 (67%)	Class #2: 02 (05%)
			att2 = 0		att2 = 1
	Node #2.1	Class #1: 02 (05%)	Class #1: 05 (25%)	Node #2.2
			Class #2: 38 (95%)	Class #2: 15 (75%)
			Rule #1: if att1 = A and att2 = 0 then p(Class #2) = 95%
			Rule #2: if att1 = A and att2 = 1 then p(Class #2) = 75%
			Rule #3: if att1 = B then p(Class #1) = 95%
			Figure 1. Example of decision tree
	Node #0:	CREATE VIEW v0 AS SELECT att1, att2, class FROM training set
	Node #1.1: CREATE VIEW v11 AS SELECT att2, class FROM v0 WHERE att1='A'
	Node #1.2: CREATE VIEW v12 AS SELECT att2, class FROM v0 WHERE att1='B'
	Node #2.1: CREATE VIEW v21 AS SELECT class FROM v11 WHERE att2=0
	Node #2.2: CREATE VIEW v22 AS SELECT class FROM v11 WHERE att2=1

Table 2 .

 2 These tests have been carried out on a PC computer with 128 MB of RAM and the Personal Oracle DBMS version 9i. The use of Personal Oracle ensures that the DMBS client and server were on the same machine, hence no network traffic can interfere with our per-Classical contingency table for TITANIC

				Adult		Child
			Male	Female	Male	Female
	1st	Yes	57	140		5	1
		No	118	4		0	0
	2nd	Yes	14	80		11	13
		No	154	13		0	0
	3rd	Yes	75	76		13	14
		No	387	89		35	17
	Crew Yes	192	20		0	0
		No	670	3		0	0
		Class Age Gender Survivor Frequency
		1st	Adult	Male	Yes	57
		1st	Adult	Male	No	118
		1st	Adult	Female	Yes	140
		1st	Adult	Female	No	4
		1st	Child	Male	Yes	5
		1st	Child	Female	Yes	1
		2nd	Adult	Male	Yes	14
		2nd	Adult	Male	No	154
		2nd	Adult	Female	Yes	80
		2nd	Adult	Female	No	13
		2nd	Child	Male	Yes	11
		2nd	Child	Female	Yes	13
		3rd	Adult	Male	Yes	75
		3rd	Adult	Male	No	387
		3rd	Adult	Female	Yes	76
		3rd	Adult	Female	No	89
		3rd	Child	Male	Yes	13
		3rd	Child	Male	No	35
		3rd	Child	Female	Yes	14
		3rd	Child	Female	No	17
		Crew Adult	Male	Yes	192
		Crew Adult	Male	No	670
		Crew Adult	Female	Yes	20
		Crew Adult	Female	No	3

Table 3 .

 3 Relational representation of the TITANIC contingency table formance measurements. The results we obtain (Figure

Table 4 .

 4 Views used in CovType tests

	View name Predictive attributes used	View size	Size of contingency table
	view1	1,2,3	116202 tuples	322 tuples
	view2	4,5,6	232404 tuples	265 tuples
	view3	7,8,9	348607 tuples	214 tuples
	view4	1,4,10	464810 tuples	202 tuples
	view5	2,5,8	581012 tuples	264 tuples

http://bdd.univ-lyon2.fr/download/decision tree.zip

http://ftp.ics.uci.edu/pub/machine-learningdatabases/covtype/

niques.

Finally, to improve their processing time, in-memory data mining methods could also use contingency tables instead of original learning sets.