Antonio Sansonetti
email: sansonetti@icvbc.cnr.it

Jana Striova

Danilo Biondelli

Irene Aliatis

Laura Rampazzi

Hidden colours in stuccowork damaged by fire: a multi-analytical investigation for revealing the original decorative pattern

Keywords: -Raman, -FTIR, fire damage, plaster gildings, coloured grounds, chrome green

come

Introduction

Gilts are among the most common decorative finishes on architectural elements, painting details, and art objects.

Several manuals provided instructions regarding their execution technique [START_REF] Thompson | The practice of tempera painting[END_REF][START_REF] Merrifield | Medieval and renaissance treatises on the arts of painting[END_REF]. The compositional and morphological characterization of gilts is very useful in the reconstruction of the historical and technical assessment of the artwork and in the selection of restoration treatments, such as cleaning, integration of the missing parts, and consolidation [START_REF] Sandu | Ancient 'gilded' art objects from European cultural heritage: a review on different scales of characterization[END_REF].

A few authors examined the technical execution of gilt on plaster surfaces [START_REF] Rampazzi | The stucco decorations from St. Lorenzo in Laino: the materials and the techniques employed by the "Magistri Comacini[END_REF][START_REF] Sansonetti | Colored grounds of gilt stucco surfaces as analyzed by a combined microscopic, spectroscopic and elemental analytical approach[END_REF][START_REF] Gulotta | Gildings and false gildings of the baroque age: characterization and conservation problems[END_REF], nevertheless their wide spread on historical buildings. These studies highlight that mordant gilding prevailed over other techniques (water gilding on bole, gold in powder mixed with mineral charges) in the decoration of plaster surfaces [START_REF] Fedrigo | Applications of mass spectrometry in cultural heritage: identification of ligands employed for mordant gilding[END_REF].

This paper focus on a vast neoclassical ballroom in the Milan Royal Palace (Hall of Caryatides), with an examination of the gilt remnants and their grounds, and of the finishes applied on adjacent plaster elements blackened by the fire due to bombing during the Second World War. Fire and bombing are a serious threat to the cultural heritage. When architectural decorations are involved in a fire, decisions regarding the possible reconstruction are challenging. The first step involves fully understanding the changes induced by the fire and by the local temperature increases.

Three techniques, used in combination were effective in revealing the composition and morphology behind the gilt remnants. Raman spectroscopy, known for its spatial and spectral resolution, can probe the pigment particles and differentiate their spectral response from the surrounding matrix. Another advantage is easy access to the low wavenumber region. FTIR contributes with the investigation of the organic compounds. SEM-EDS, beside the basic knowledge of the elemental composition and its distribution, helps by providing morphological and dimensional information on the examined layers.

Materials and methods

Materials and historical notes

In the 18 th century the Hall of Caryatids in the Milan Royal Palace was the greatest ballroom in Europe, decorated with neoclassical plaster-works consisting of a sequence of forty caryatids. Gilded mouldings, capitals and frames adorned the hall. In this interior important plasterers, such as Albertolli, worked under the direction of the architect Piermarini.

The Royal Palace was damaged during bombing in 1943. The damage was repaired in the post-war period, and the stucco surfaces have been conserved at different steps: the general aspect of the Hall recalls ruins and the artworks are missing many parts. The fire caused by the bomb led to the loss of the decorative pattern. Most of the relieves have blackened surfaces, whose level of blackening depends on the distance from the combustion nucleus. The black layers hide the original colours of the ornaments apart from the gold leaf remnants (Fig. 1a,1b).

Samples

17 micro-fragments were sampled from the gilt stucco elements, such as the column's base, capitals and mirror frames.

Analytical methods

Samples were observed with a Leitz Wild M420 stereomicroscope, then embedded into epoxy resin; Cross sections were examined in reflected light using a Leitz Ortholux microscope with Ultropack illuminator and a digital capture system.

Raman micro-spectroscopy was performed with a Senterra -Raman spectrometer (Bruker) coupled to an Olympus BX51 microscope using 785 nm light (maximum power 100mW, cut off at 100 cm -1 by an edge filter). The laser beam was focused on the pigments grains using 20× (numerical aperture NA=0.40) and 50× (NA=0.75) Olympus objectives.

Raman signals were detected with a Peltier cooled CCD detector (1024×255 pixels) operating at -70°C. The laser power at the sample surface, was about 1 mW. The spectra were collected in 100-2500 cm -1 range (spectral resolution ~3 cm - 1 ). The acquisition time was 30-60 seconds according to the signal to noise ratio, repeated 6-10 times. FTIR spectra were recorded using a Nicolet spectrophotometer combined with a Continum microscope and a Graseby Specac diamond cell. Spectra were acquired in transmission mode (4000-700cm -1 ; 128 scans; resolution 4cm -1 ).

Back-scattered images, micro-beam EDS analyses and X-ray maps were collected on carbon coated polished crosssections with a JEOL 5910LV SEM system (IXRF Systems). Qualitative EDS spectra of areas or spots and elemental maps were registered from 0 to 20 keV and at 1-3x10 -7 A.

Results

To facilitate the interpretation of the data, the results were divided into two groups: (a) gilts, containing fragments with a single or two distinct and subsequent gold leaves, and (b) blackened surfaces. Two representative samples are described in Tables 1 and2.

Gilts

The gilts had originally been applied on small ornaments such as egg shaped elements, acanthus leaves on the capitals, fillets at the base of the columns. Examinations of the cross-sections under the optical microscope revealed a stratigraphy consisting of up to five layers. The older gilts were placed on a double-layer ground: an orange or deep yellow layer directly on the stucco body (1, Fig. 2), composed of red particles in a yellowish matrix, and a light yellow one (2, Fig. 2). The first layer was applied to cover the stucco body, the orange pigment particles helped to warm up the gold leaf hue. The white yellowish ground was applied as an underlying ground for the gold leaf (3, Fig. 2). In double gilt elements, a yellowish ground (4, Fig. 2) separated the two leaves, suggesting that the gilts were applied at different times and the latter leaf (5, Fig. 2) was probably applied during a conservation work. The gold leaves had a thickness of around one micron. EDS elemental analyses indicated gold as the sole element; no copper or silver were detected.

In both the inner ground layers (1 and 2, Fig. 2), yellow ochre and lead white were detected. Raman spectra of the yellow particles displayed bands at 299, 388, 549 cm -1 , attributable to goethite, (-FeOOH), the main component of yellow ochre, and a weak band at 1050 cm -1 , attributable to  s (CO 3

2-

) of lead white [START_REF] Bell | Raman spectroscopic library of natural and synthetic pigments (pre-≈ 1850 AD)[END_REF]. When mixed with siccative oils, saponification reactions produce lead soaps. Because of its excellent workability, this mix is suitable for the gold leaf and for burnishing.

Red lead allowed to distinguish layers 1 and 2 and was responsible for the orange tone of the layer 1. In fact, Raman spectra collected on the red particles of layer 1 (Fig. 2) displayed bands at 122, 152, 228, 312, 391, 550 cm -1 which are characteristic of red lead (Pb 3 O 4 ), used since antiquity as a natural occurring mineral. The uppermost gilt was applied on a yellowish ground layer (layer 4, Fig. 2) of a similar composition to the possibly original ground: yellow ochre and lead white. The small red particles were, in this case, identified as hematite (-Fe 2 O 3 ), according to its characteristic Raman lines at 222, 294, 409, 497, 609 cm -1 . The weak 660 cm -1 line might have had a different origin: it is attributed to a disorder-activated mode in the hematite crystalline structure, or to magnetite traces (Fe 3 O 4 ). The latter scattering could also be attributed to the partial thermal transformation of hematite to magnetite under reducing conditions occurring around 250 °C [START_REF] De Faria | Raman microspectroscopy of some iron oxides and oxyhydroxides[END_REF].

Blackened surfaces

Some of the finishes, exhibited a stratigraphy (Fig. 3), with a morphology complicated by the heat and which contained bubbles, voids, and detachments. The analyses revealed no gold leaf and no substance that might suggest the presence of a fake gilt. Instead, several superimposed green layers (layers 2 and 3, Fig. 3), between the yellow stucco finish (layer 1, Fig. 3) and the blackened surface (layer 4, Fig. 3) were detected. Green layers underneath were lighter in colour than the upper ones. Some of the samples, were completely blackened in each of the layers (Fig. 1c), suggesting the differentiated influence of the heat based on the distance from the fire. In the samples less influenced by the heat, the main components of the light green layers were identified by Raman spectroscopy as celadonite, goethite and lead white. The green pigment characterized in the Raman spectra (Fig. 4) by 272, 389, 543, 701 cm -1 lines was attributed to celadonite. This mineral of approximate composition K[(Al,Fe 3+ ),(Fe 2+ ,Mg)](AlSi 3 ,Si 4 )O 10 (OH) 2 is one of the principal green clay minerals belonging to the green earth class. As demonstrated by Ospitali et al. [START_REF] Ospitali | Green earths': vibrational and elemental characterization of glauconites, celadonites and historical pigments[END_REF], celadonite can be distinguished from glauconite on the basis of the medium intensity Raman line occurring in the 272-279 and 263-266 cm -1 range for celadonite and glauconite, respectively. Other differences were observed in the OH stretching region, which was probed using a green excitation line (532 nm). Green earths are reported to be stable up to 500°C; then a possible turning into brown is observed, even if the specific thermal decomposition mechanisms are not fully known [START_REF] Rickerby | Heat alterations to pigments painted in the fresco technique[END_REF]. The external dark green layers (3 and 4 in Fig. 3) did not resemble the composition of the deeper ones. The spectra recorded on the bluish-green areas exhibited the Raman lines of Prussian blue, observed at 276, 532, 2094, 2150 cm -1 , together with lines at 988 and 1050 cm -1 due to sulphate and carbonate stretching modes of barite, and lead white, respectively (Fig. 5a). The identification of the Prussian blue was surprising as no clearly distinct blue areas were visible under the optical microscope. An example of the spectrum acquired on the same dark green layer is shown in Fig. 5b, which highlights the presence of chrome yellow although no yellow particles were visible. Raman features at 138, 358, 399, 840 cm -1 could be attributed to PbCrO 4 , also known as chrome yellow, a lemon yellow pigment discovered at the beginning of the 19 th century and introduced onto the market in 1809. Its main Raman peak (CrO 4 2-) is positioned from 820 to 840 cm -1 according to the pigment hue: for the orange hue, it appears at lower Raman shifts probably due to the presence of PbO in crystal lattice, while for the yellow hue, it is shifted to higher ones.

Red and yellow ochres were also detected in layer 3, in small coloured grains. FTIR analysis confirmed Prussian blue, lead white and barite. Chrome yellow was not detected by FTIR as it was probably present in low concentrations.

FTIR spectra collected on the coloured layers exhibited the absorption bands of a blend composed of a siccative oil and lead white. The interaction of oil and lead compounds can lead to saponification, given that cerussite has a lower tendency to saponification than hydrocerussite. Hence, the microstructure of these layers varied from areas mainly composed of lead compounds, areas mainly composed of oil, and areas where a good mix had been produced by extended grinding and stirring.

The absorption pattern of the FTIR spectra thus depended on the point of sampling. What changed from one spectrum to another was the intensity ratio between peaks that could be attributed to oil, and peaks due to lead white. The spectrum recorded on a sample from the base of a column, displayed the following peaks due to oil -2927, 2854, 1738, 1707, 1176, 1103 cm -1 ; due to lead white -(OH) at 3538 cm -1 ,  as+s (CO 3 2-) at 1411+1044 cm -1 , CO 3 2-rocking at 680 cm -1 , while the peak at 1527 cm -1 is due to saponified groups. The peak of lead carboxylate ranged from 1514 to 1557 cm -1 most likely due to the contribution of fatty acids such as azelaic, stearic and palmitic. The intensity ratio between the peaks at 1738, 1707 cm -1 and the lead carboxylate one was variable, however the peak at 1738 cm -1 of ester carbonyl was always present.

A completely different situation was noted in the spectra, acquired on the brownish oily substances, sampled from the blackened stucco surfaces attributed to the partially decomposed and heat-affected siccative oil. The thermal degradation of linseed oil starts gradually from 100-300 °C, and reaches its maximum at 300-600 °C. At temperatures above 100 °C, the peroxide groups decompose with the formation of radicals whose reactions with double bonds give rise to cross-linking. At the same time the secondary process of fragmentation takes place [START_REF] Lazzari | Drying and oxidative degradation of linseed oil[END_REF]. Glycerol moieties are released and disappear in the form of acrolein starting from 300 °C. Consequently, in the FTIR spectra, the absorption band due to (C=O) ester at 1738 cm -1 decreases.

The spectra of the black oily substance (Fig. 6) can be described as follows. The absorption bands at 3400 and 1737 cm - 1 due to alcohol/hydroperoxide and ester groups, respectively, are nearly absent and the band at 1707 cm -1 is of low intensity, while the band of lead carboxylate is still present. In fact, the lead salts of aliphatic acids such as lead palmitate and stearate have been reported to decompose in a higher temperature range (300-500 °C). In addition, the spectra do not exhibit the band at 3536 cm -1 due to (OH) of lead white, most likely due to the thermal decomposition of this pigment which starts by de-hydroxylation at 260 °C [START_REF] Cohen | Dosimetry of paintings: determination of the degree of chemical change in museum exposed test paintings (lead white tempera) by thermal analysis and infrared spectroscopy[END_REF]. The weak band still present at around 838 cm -1 was assigned to C-O vibration in lead carbonate. Two forms of lead oxide were also ascertained by X-ray diffraction: litharge and massicot, which coexist in the range 320 and 500 °C [START_REF] Aze | Chromatic alterations of red lead pigments in artworks: a review[END_REF]. A strong band centred at 2091 cm -1 (CN stretching of Prussian blue) was evident only in the spectra of the samples not affected by heat: Prussian blue decomposes at around 220 °C to yield amorphous ferric oxide of black colour [START_REF] Allen | Thermal decomposition of Prussian blue: Isotopic labelling with Mössbauer-inactive Fe-56[END_REF]. In several spectra of the blackened surface, the presence of barite (decomposition temperature above 1400 °C) was ascertained. These findings suggest that the temperatures of the stucco surfaces reached during the fire, at least locally, were in the range of 300-500 °C. It is known from historical records that the fire was contained in the west corner of the Hall; hence the action of the heat was most probably very different from point to point.

Discussion

Mixed colours were prepared industrially starting from the 18 th century [START_REF] Alderson | Re-creating a 19th century Paint Pallette[END_REF][START_REF] Gettens | Pigments materials. A short encyclopaedia[END_REF][START_REF]Artists' Pigments: A Handbook of Their History and Characteristics[END_REF]. Unlike a colour mixed on an artist's palette, these industrially-made colours were blended so that the individual components cannot be distinguished microscopically. Chrome green, sold to the artists under different names, is often reported as a mixture of Prussian blue with a paste of barites, china clay and chrome yellow [START_REF] Winter | Artists' Pigments[END_REF].

Because of its excellent hiding power and low cost, chrome green had a great success. Industrially prepared, it was probably introduced in the first quarter of the 19 th century, and certainly after the first documented use of yellow chrome in a painting by Thomas Lawrence dated to 1810. Edwards et al. [START_REF] Edwards | Pepper M Raman spectroscopic analysis of the enigmatic Comper pigments[END_REF] found a green of a similar composition, referred to as Comper green, in a 19 th century church decoration. Rosi et al. [START_REF] Rosi | Identification of nineteenth century blue and green pigments by in situ x ray fluorescence and microRaman spectroscopy[END_REF] also report on chrome green, mixed with barite, in 19 th century wall paintings. The authors attribute barite to the impurity of chrome yellow, however in our opinion the painter could have used industrially prepared pigment, which included barite in the original recipe as reported by Gettens.

The presence of barite and chrome yellow, and the fact that no blue or yellow particles were identified during our examination, corroborate the thesis that the green layers observed were prepared with such a mixing formula. The costeffectiveness and the possibility of covering large areas with the tint of the ready-made colour might make it a better choice over the more laborious hand mixing. The use of the green hue that gives an earthy tone was identified only on those elements of the column's base which alternate with the gilt elements. The mixture of green earth and yellow ochre was later repainted with a chrome green blend.

The pattern of alternating green painted fillets and gilt mouldings created a play of light and shadow, which was totally lost due to the consequences of the heat developed from the combustion of the wooden hall roof.

Conclusions

Detailed analyses of the gilt samples together with the altered finishes enabled the decorative pattern to be reconstructed of the column bases in the Hall of Caryatides located in the Royal Palace in Milan. This consisted in alternate green and gilt mouldings with a chiaroscuro effect. The blackened layers were originally of a green colour. Two distinct applications were distinguished: green earth with yellow ochre, probably used in the original finishes, and chrome green applied during later over-painting. Both pigments produced an earthy tone, which was probably used to create the semblance of a bronze surface.

The gold leaves exhibited an orange ground based on lead white with minium or ochres, bound with siccative oil. The tone of the blackened surfaces is attributed to a partial combustion of the oil used as a binder and to the thermal decomposition of pigments present in the finishes.

The use of cold colours in combination with gold leaves is quite unusual, especially as regards Italian style of ornamental patterns, and is possibly a reflection of middle-European 18 th century taste, which preferred cold hues to warm ones.

Fig. 1 :

 1 Fig. 1: View of the examined surfaces showing gilt remnants (a), blackened surfaces (a, b) and details of a sample coming from a black surface (c).

Fig. 2 :

 2 Fig. 2: Cross section with double gilt layer (3 and 5) observed under optical (a) and electron (BES) (b) microscope; bar= 120 m. Back scattered electrons.

Fig. 3 :

 3 Fig. 3: Cross section with blackened surfaces observed under optical (a) and electron microscope (b) back scattered electrons.

Fig. 4 :

 4 Fig. 4: Raman spectrum of light green particles, present in the inner layers in blackened samples, showing lines attributable to celadonite.

Fig. 5 :

 5 Fig. 5: Raman spectra, acquired on the external dark green layers of blackened samples, showing: (a) lines attributable to Prussian blue, lead white and barite, (b) lines attributable to chrome yellow.

Fig. 6 :

 6 Fig. 6: FTIR spectrum of the black oily substance sampled from a blackened stucco surface.

Table 1 :

 1 Stratigraphy of a representative gilt element (Figure2)

	Layer Description	Composition
	5	Gilt	gold
	4	yellow grayish ground	yellow ochre, lead white, hematite, oil
	3	Gilt	gold
	2	white yellowish ground	yellow ochre, lead white, oil
	1	orange/deep yellow ground yellow ochre, lead white, red lead, oil
		stucco body	gypsum and magnesite

Table 2 :

 2 Stratigraphy of a representative blackened surface with green pigments (Figure3)

	Layer Description	Composition
	4	blackened surface	partially decomposed oil, Prussian blue, lead carbonate, barite
	3	dark green	Prussian blue, chrome yellow, lead white, barite, ochres, oil
	2	light green	green earth, yellow ochre, lead white, oil
	1	yellow stucco finish lead white, oil
		Stucco body	magnesian lime and limestone powder


Philippe Boisse
email: philippe.boisse@insa-lyon.fr

Alain Gasser

Benjamin Hagege

Jean-Louis Billoet

Analysis of the mechanical behavior of woven fibrous material using virtual tests at the unit cell level

The determination of the mechanical properties of fabrics in biaxial tension and in-plane shearing is made from 3D finite element analyses of the unit woven cell. Compared to experimental tests these virtual tests have several advantages. They can easily be carried out for sets of varied parameters, they provide local information inside the woven material and above all they can be performed on woven materials that have not yet been manufactured. The 3D computations are not classical analyses because the yarns are made up of several thousands of fibres and their mechanical behaviour is very special. Several specific aspects of the analysis are detailed, especially the use of a hypoelastic law based on an objective derivative using the rotation of the fibre which allows a strict evolution of the directions of orthotropy according to the fibre direction. Examples of analyses are presented in biaxial tension and in-plane shear for woven reinforcements and in the case of the biaxial tension of a knitted fabric. The results obtained are in good agreement with experimental results.

Introduction

The development of finite element codes for the simulation of textile composite forming or textile draping [1][2][3] requires the knowledge and modelling of the mechanical behaviour of woven reinforcements. These are highly specific because of the internal structure of the fabrics (see Section 2). The mechanical behaviour can be investigated by experimental tests such as biaxial tensile tests and in-plane shear tests [4][5][6][7].

Section 3 briefly presents two of these tests that will be used for further validations. However, these experimental tests are rather difficult to perform and above all it is sometimes necessary to obtain information on the mechanical behaviour of a fabric which has not yet been manufactured. For instance it may be interesting to know the influence of certain fabric parameters (yarn geometry, yarn density, fibre material, type of weaving. . . ) on a forming process. To this end, virtual tests permit the mechanical properties of a woven reinforcement to be obtained relatively easily, without performing the experiments and hence without necessarily manufacturing the fabric under con-sideration. The virtual tests that are presented in this paper are 3D finite element simulations performed on a unit woven cell. Because of the specific mechanical behaviour of woven material (Section 2), tensile biaxial tests and in-plane shear tests are performed. The finite element of the unit woven cell must account for the constitution of the yarn that is made of thousands of fibres. The specificities of the numerical models will be presented in Sections 3 and 4. This paper will focus particularly on the transverse compaction behaviour and on a hypoelastic model based on an objective derivative using the fibre rotation. Section 5 presents the results obtained in the case of biaxial tension of an unbalanced fabric. Virtual tests in in-plane shear are presented in Section 6. In this case the computation gives correct results but the convergence is not reached after the shear locking angle. Finally a tensile biaxial virtual test on a knitted fabric is presented in Section 7. For all these virtual tests the results are compared to experimental results obtained as described in Section 1. Virtual and experimental tests are in good agreement.

Mechanical behaviour specificities of woven materials

The mechanical behaviour of fabrics is complex due to the intricate interactions of the yarns. It is a multi-scale problem. The macroscopic behaviour is highly dependent on the interactions of yarns at the meso-scale (i.e. the woven unit cell) and at the micro-scale (i.e.the fibres constituting yarns). Despite extensive research in the field, there is no widely accepted model that describes accurately all the main aspects of fabric mechanical behaviour. The different model families differ by the scale at which they are defined. A first family of models is obtained by homogenizing the mechanical behaviour of the underlying meso-structure and considering the fabric as an anisotropic continuum [8][9][10]. While these models can easily be integrated in F.E. classical shell or membrane elements in order to simulate fabric forming, the identification of homogenized material parameters is very difficult, especially because these parameters change when the fabric is strained and when, consequently, the directions of the yarns change. Currently, the continuum models proposed in the literature do not generally account for the interactions between warp and weft yarns (crimp change, locking. . ...). Other authors, in contrast, present fully discrete models of fabrics. Each yarn is modelled and is assumed to be a straight or a curved beam or truss. Springs are usually used to model warp and weft yarn interactions. Many models have been proposed to describe in this way the mechanical behaviour of the unit woven cell submitted to in-plane tension and shear [11,12]. Some models are extended to the whole woven structure [13,[START_REF] B E N B O U Ba K E R | Finite Element European Revue[END_REF]. However, the large number of woven cells in a woven structure leads to high computational cost. We consider a fabric made of two directions (warp and weft) of woven yarns (the classical case) and yarns that are made of juxtaposed fibres (the case for most fabrics used as composite reinforcements) (Fig. 1). All the stiffnesses of a single fibre are very small except for the tensile rigidity in the fibre direction. This is also the case for a yarn because fibres can relatively slide. Consequently the Cauchy stress tensor in the yarn can be assumed to be in the form:

σ σ σ = σ 11 h 1 ⊗ h 1 (1)
where h 1 is the unit vector tangent to the yarn. If a woven domain is considered (Fig. 1b), the stress tensor is in the form:

σ σ σ = σ 11 h 1 ⊗ h 1 + σ 22 h 2 ⊗ h 2 (2)
where h 1 and h 2 are the vectors in warp and weft directions. The tensions are defined from these stresses:

T 11 = A σ 11 dS T 22 = A σ 22 dS (3)
A is the section of the yarn. The tension tensor is limited to:

An in-plane shear rigidity of the fabric is due to the weaving of warp and weft yarns. For a warp-weft angle variation, it can be assumed that a couple C, normal to the fabric, is applied on each crossover, or set of crossovers in the case of more complex woven unit cells. If all the other stiffnesses are neglected, a simplified equilibrium equation can be written for a textile structure with ncell woven unit cells:

ncell p=1 p ε 11 (η η η) P T 11 L 1 + p ε 22 (η η η) P T 22 L 2 + ncell p=1 p C p γ (η η η) -T ext (η η η) = 0 ∀η η η/η η η = 0 on u (5)
ncell is the number of woven unit cells of the textile structure, p A, means that the quantity A is considered for the woven unit cell number p. T ext (η η η) is the virtual work of the exterior prescribed loads. ε(η η η) = ∇ s η η η = ε αβ (η η η)h α ⊗ h β is the symmetrical gradient in the virtual displacement η η η (α and β are indices with the value of 1 or 2). h 1 , h 2 are the contravariant vectors related to h 1 , h 2 i.e. h α . h β =δ α β . γ (η η η) is the virtual relative rotation between warp and weft fibres (or virtual shear angle). L 1 and L 2 are the lengths of the warp and weft yarns in the mid-plane of the fabric.

u is the part of the frontier of the domain with prescribed displacements. This equation is much simpler that the general equilibrium equation as it only considers the tensile and in-plane shear strain energy of the fabric. It has been shown on several forming simulation cases that this is sufficient for most of the fabrics used as composite reinforcements [15,[START_REF] O I S S E | [END_REF]. The simplified form of the internal loads virtual power in ( 5) can be used to build some finite elements made of woven cells in biaxial tension and in-plane shear in order to simulate fabric forming without computing the strain energies that are absent in the case of fabrics [3,[START_REF] O I S S E | [END_REF]. In Equation 5 the mechanical behaviour of the fabric is determined by T 11 and T 22 and C for a given woven cell p. The tensions are function of the strains in both warp and weft directions because of the weaving. Consequently the use of the simplified equilibrium equation requires the knowledge of two tensile biaxial surfaces (T 11 (ε 11 , ε 22 ), T 22 (ε 11 , ε 22 )) and of the shear curve (C(γ )). The objective of the next sections is the determination of these quantities using virtual and more precisely meso-scale 3D finite element computations of the unit woven cell submitted to biaxial tensions or in-plane shear.

Experimental analysis

As seen above, bending and shear stiffnesses are small with respect to the tension stiffness. Therefore, the first point to analyse is tensile behaviour, and, to be more precise, biaxial tension. Indeed, due to the weaving, the change of yarn undulation in one direction has an influence on the other yarn direction. Furthermore, the in plane shear behaviour must be taken into account, since shear is the principal mode of fabric deformation during shaping, and because wrinkling appears when the shear angle exceeds a limit angle (locking angle). The two experiments presented will be important to validate the analyses of the behaviour made using numerical at the unit cell level.

Biaxial tensile tests

The biaxial tensile device (2a) allows cross specimens to be tested. One of the two deformable lozenges has a modifiable length to obtain different ratios (noted k) between warp and weft strains [7]. Fig. 7 shows the results obtained for different ratios k, for an unbalanced glass plain weave. The curves are different in warp and weft directions because the fabric is unbalanced. The curves exhibit two parts. The first is non linear, due to a change of undulation and/or yarn crushing. The second is linear, and represents the yarn stiffness. The behaviour is the most non linear for a uniaxial tensile test (when a direction stays free of load). With these results, it is possible to build biaxial tensile-strain surfaces [3] which represent the load in a yarn direction versus strain in warp and weft directions. Fig. 2b presents one of these surfaces (in warp direction) in the case of the unbalanced glass plain weave.

Shear tests

Different in-plane shear tests exist [4][5][6][17][18][19][20]. In the present study, the tests are performed with a picture frame (3a), made with a deformable frame that prescribes a uniform shear strain field [21]. A camera takes pictures which are processed with a software that gives displacement and strain fields using an image correlation method [22,23]. Pictures are taken at two scales (macro and meso) to obtain the displacement fields of the whole specimen, but also within a single yarn. The global shear strain field obtained during the deformation is presented in Fig. 4a. The shear curve (shear force versus shear angle), presented in Fig. 3b in the case of a glass plain weave, shows three parts. In the first part (up to 35 • ), the shear force is very small. It corresponds only to yarn rigid rotation as shown in Fig. 4b by the optical method, without yarn deformation: the shear force is due only to friction at crossovers. In the second part, the force begins to increase. Some yarns are in contact with their neighbours and are laterally compressed (see Fig. 4c). In the third part, all the yarns are in contact and compressed (see Fig. 4d) which leads to a marked load increase and to fabric wrinkling. The locking angle (that must not be exceeded to avoid wrinkling) is given by the transition between zones two and three.

3D finite element analyses of the woven unit cell 4.1. Specificities of the analysis

The fabric mechanical behaviour can also be obtained using biaxial tension and shear simulation tests. These virtual tests, i.e. 3D finite elements analyses of a unit woven cell (representing the periodicity of the fabric) under loading are an interesting alternative. They allow the simulation of many tests that would be costly and difficult to perform in reality, but above all, these virtual tests may be made before the manufacture of the fabric. They also give local information within the material that is very difficult to obtain experimentally. 3D finite element models of the woven unit cell are defined. Contacts between yarns are modelled using a master/slave technique with Coulomb friction. Fabric periodicities, and possible elementary cell symmetry, are represented by boundary conditions. The main difficulty in the analysis is to represent the yarn behaviour with continuum elements while yarns are made of thousands of fibres that can more or less slide relatively. Therefore, like the fabric, yarns have very small stiffnesses in bending and shear. This particular behaviour can be modelled by an elastic orthotropic material, with small transverse Young's modulus (perpendicular to the fibre direction) and small shear modulus with respect to the longitudinal Young's modulus (fibre direction). Longitudinal Young's modulus is identified using a tension test on a single yarn. Transverse Young's modulus is not a constant: it is small at the beginning, but increases as a function of transverse and longitudinal strains. Indeed, the more the yarn is compressed in transverse direction, and tensed in fibre direction, the higher the modulus. Therefore, the crushing law is chosen as follows:

E i = E 0 ε m 11 |ε ii | n + E ε (6)
where 1 is the fibre direction, 2 and 3 the transverse directions, i is equal to 2 or 3, E ε is the initial transverse modulus (usually very small), E 0 , m and n three material constants. To identify these constants, it is difficult to perform a compression test under different tensions on a single yarn. Hence, they are determined using an equibiaxial tension test on the fabric, coupled with an inverse method [24,25].

Very weak stiffnesses can lead to numerical problems, such as spurious modes. To avoid these problems, finite elements with reduced integration and hourglass control are used [26]: a stabilization matrix is added to the element stiffness, based on some orthogonality properties of the added fields, to remove the spurious modes.

Since displacements and strains are large, it is necessary to work within a large strain theory. Because Young's moduli are very different in longitudinal and transverse directions, it is important that material directions are followed carefully during analysis. To prescribe these orthotropic axes, the yarn behaviour law is associated with an objective derivative based on the spin of the fibre. This enables the fibre direction to be strictly followed, unlike approaches classically developed in the finite element codes.

Definition of an equivalent continuum model for fibrous materials

The presented formulation takes the specific mechanical behaviour of fibrous reinforcements into account and is important in 3D finite element analyses of fabric forming. The formulation consists in a hypo-elastic continuous orthotropic model able to cope with large deformations. The specificity lies in the definition of a rotation tensor which we call the "fiber rotation". The latter allows us to model both the evolution of fiber bundles with one strong anisotropic direction and to define a strain measure representative of the transformation of such a medium. This is achieved because enables the fiber direction to be strictly followed, unlike approaches traditionally developed in finite element codes (i.e. Jaumann's corotational formulation [27,28] or the Green Naghdi approach [28,29]). When building the FEM, the user has to define the initial orientation of the orthotropic axes along the continuum elements. Generally, these constitutive axes are represented at each Gauss point with the aid of several orthonormal bases κ 0 defined by a rotation tensor field O that transforms the unitary vectors of the global basis {G}:

κ 0 i = O • G i (7)
The material rotation is then used to update the initial constitutive axes {κ 0 } to the current constitutive axes {κ t } (see Fig. 5): Some developments of Equation 8( [START_REF] C R I S F I E L D | Non Linear Finite Element Analysis of Solids and Structures, Volume II: Advanced Topics[END_REF]) lead to the set of formula ( 9) that explicitly give the constitutive axes {κ t } as functions of the initial constitutive axes {κ 0 } and the deformation gradient F:

κ t i = • κ 0 i (8)
κ t 1 = F • κ 0 1 F • κ 0 1 κ t 2 = κ 0 2 - b 2 1 + b 1 κ 0 1 + κ t 1 κ t 3 = κ 0 3 - b 3 1 + b 1 κ 0 1 + κ t 1 (9) with b k = κ t 1 • κ 0 k and b k = 1.
Note that in this formulation the fiber direction, i.e. the strong anisotropic direction, remains aligned with the first vector of {κ t }. The constitutive behaviour is then fully defined at each time. In fact, the projection (10) of the initial constitutive tensor 0 C has known components that can be computed with the traditional engineer's constants ( [START_REF] O N E S | Mechanics of Composite Materials[END_REF]):

0 C = 0 C i jkl κ 0 i ⊗ κ 0 j ⊗ κ 0 k ⊗ κ 0 l ( 10
)
In addition, because the current constitutive tensor C is supposed to be an objective tensor, it can be deduced from 0 C by a rotational transport based on the fourth order rotation tensor R:

C = R : 0 C : R T ( 11
)
In Equation 11, the components of R are computed from the components of the second order rotation tensor :

R i jkl = ik jl (12)
Lastly, the definition (10) combined with the evolution law (11) entails that the projection (13) of C is fully known:

C = 0 C i jkl κ t i ⊗ κ t j ⊗ κ t k ⊗ κ t l (13)
Thus, the constitutive tensor C can be used in a hypoelastic law written:

L ⊥/ (σ ) = C : D (14)
In Equation 14, D is the strain rate tensor and the left member is the Lie derivative of the Cauchy stress tensor with respect to the rotational flow . The geometric definition of this derivative is given by:

L ⊥/ (σ ) = • d dt ( T • σ • ) • T (15)
The cumulated tensorial strain tensor ε and stress tensor σ associated with such an objective derivative are given by:

ε = • t 0 T • D • dt • T (16) σ = • t 0 T • C : D • dt • T (17)
It can be shown that Equation 16will always give a logarithmic strain in the strong anisotropic direction and that Equation 17 ensures the summation of the stress increments along this direction.

Finally, the use of the material rotation tensor for the Lie derivative (15) and the evolution law (11) entails a consistent approach for fibrous media with one strong anisotropic direction.

Simulations of a woven unit cell under a biaxial tension

Several elementary cells of different fabrics were analysed for different warp weft strain ratios k. The studied unbalanced glass plain weave is presented Fig. 6a. Elementary cell is shown in Fig. 6b. Due to symmetry, only one quarter is analysed. In the case of equibiaxial load, the obtained transverse strains are large (see Fig. 7a). In the case where one direction is free (uniaxial tension test), it can be seen that the principal mode of deformation is the change of yarn undulation (with small transverse strains). The curves load versus strain for different strain ratios k obtained by the simulations are shown in Fig. 7b andc and compared to experimental results. A good correlation is found. Curves are different in warp and weft directions since fabric is unbalanced. It can be observed on Fig. 7c that the small yarn (weft) has little influence on the great yarn (warp). These analyses (and all those of fabric used for composite materials [3]) show that there is a high degree of crushing and that it is a main aspect of fabric biaxial tension.

Simulations of a woven unit cell under in-plane shear

To impose a pure shear on an elementary cell, the kinematics of the picture frame is prescribed as boundary conditions. Furthermore, it was shown experimentally that fabric shear corresponds to yarn rotation without yarn shear (see Section 3.2). Therefore, the yarn sections must stay perpendicular to the middle line. This condition is prescribed to the model.

The finite element analyses are performed using an implicit approach. The results are presented in Fig. 8 for a carbon 2×2 twill, and in Fig. for glass plain weave. The predicted shear curve (Fig. 9) is close to the experimental curve, but the analysis presents a problem of convergence after 45 • due to a problem of contact management. It is probably possible to improve this maximum value by using a finer mesh or by performing the analysis with an explicit approach. But the implicit analysis is sufficient to determine the locking angle which is the angle that must not be exceeded during forming if wrinkles are to be avoided.

Simulation of the biaxial tension test

on a knitted structure Because of the generality of the formulation described in Section 4.2, knitted structures can also be analysed in case of a biaxial deformation mode. The presented simulation is performed for a biaxial ratio k=1 and the FEM is solved using an explicit code (Abaqus/Explicit). The user routines of this code have permit to implement the approach described in Section 4.2. The studied knitted material is made with aramid yarns and is used as reinforcement in rubber tubes (automotive applications). The deformed virtual sample is very realistic (see Fig. 10) and the loaddisplacement curves in the directions of loading fit the experimental data obtained from the biaxial tensile test presented in Section 3 (see Fig. 11).

Conclusion

The determination of woven fabric mechanical characteristics by mesoscopic 3D finite element analyses of the unit woven cell is an alternative to experimental tests. These 3D simulations present several advantages • It is easy to vary some parameters of the analysis such as the loading as well as the material characteristics (yarn geometry, yarn density, fibre material, type of weaving. . .). • They avoid carrying out experimental tests which can be tricky to perform. • They give information on the local deformation mechanism within the fabric. • They can be performed on a fabric that has not yet been manufactured, especially in order to determine its optimal parameters for a given use.

The main difficulty with these simulations lies in the fibrous nature of the yarns that are made of thousand of fibres and the mechanical behaviour of which is very different from a glass or carbon continuous domain. It has been shown that the use of a hypoelasic law based on an objective derivative using the fibre rotation permits to strictly keep the orthotropy directions coinciding with fibre directions. The transverse behaviour law is also an important point since the mesh crushing in a biaxial tension is very large (often larger than 40%). The transverse compression law that is used in the present work relates the transverse Young modulus both to transverse strain and strain in the fibre direction. Complementary studies and especially experimental ones will have to be performed in order to define more physically based models and take them into account in the simulations [START_REF] Tow S K I | [END_REF]33].

The presented simulation of the in-plane shear test does not converge when the shear locking angle is exceeded. This difficultly mainly comes from the very complex shape and of the highly localized nature of the contact zone between warp and weft yarns. Work is in progress to overcome this difficulty. In particular, analyses are performed including a local remeshing which considerably increases the number of elements in the contact zone of the warp and weft yarns.

Figure 1

 1 Figure 1 (a) Yarn made of juxtaposed fibres (b) Woven yarns.

Figure 2

 2 Figure 2 (a) biaxial tensile device, (b) biaxial tensile-strain surface in warp direction of an unbalanced glass plain weave.

Figure 3

 3 Figure 3 Shear test: (a) picture frame and camera, (b) experimental shear curve on a glass plain weave.

Figure 4

 4 Figure 4 Shear test: Displacement field at macro scale (a), Displacement at meso scale (within the yarn) in zones 1 (b), 2 (c) and 3 (d) of the shear curve (see Fig. 3b).

Figure 5

 5 Figure 5 2D representation of the definition of the constitutive axes {κ t }.

Figure 6

 6 Figure 6 Mesh the elementary cell (b) of an unbalanced glass plain weave (a).

Figure 7

 7 Figure 7 Biaxial tensile simulation on an unbalanced glass plain weave: transverse logarithmic strain for an equibiaxial load (a), experimental/prediction comparisons in weft (b) and warp (c) directions for different values of strain ratio k.

Figure 8

 8 Figure 8 Shear simulation of carbon 2 × 2 twill elementary cell.

Figure 9

 9 Figure 9 Test/prediction comparison for in plane shear load on glass plain weave.

Figure 10

 10 Figure 10 Biaxial test on a knitted reinforcement (Deformed and undeformed virtual samples).

Figure 11

 11 Figure 11 Experimental and numerical load-displacement curves for a biaxial test on a knitted fabric.


Abderrahmen Kammoun

Syed Gillani

Julien Subercaze

Stéphane Frénot

Kamal Singh

Frédérique Laforest

Jacques Fayolle

Stephane Frenot

All that Incremental is not Efficient: Towards Recomputation Based Complex Event Processing for Expensive Queries

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

INTRODUCTION

Complex Event Processing (CEP) matches a sequence of events within a stream against a complex query pattern that specifies constraints on the extent, order, values, and quantification of the matching events. Most of the CEP systems incrementally produce matched patterns, where partial matches are stored and then computed to avoid the recomputation cost [START_REF] Mei | Zstream: A cost-based query processor for adaptively detecting composite events[END_REF][START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF]. That is, with the arrival of an event, a CEP system (i) can generate a new partial match by matching incoming event with the prefix of the defined query pattern; (ii) checks with the existing partial matches if the incoming event can be part of them or complete them. The number of partial matches for such strategy can be polynomial or exponential to the number of events within a window [START_REF] Agrawal | Efficient pattern matching over event streams[END_REF][START_REF] Kolchinsky | Lazy evaluation methods for detecting complex events[END_REF][START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF]: some partial matches lead to the complete matches while others fail. This results in extensive memory and CPU utilisations. In the following, we present a real-world CEP query to showcase the issues of incrementally processing partial matches.

Example 1. A stock market application processes thousands of financial transactions per second to detect patterns that signify emerging profit opportunities. An example of such a pattern, called V-shaped pattern [START_REF] Poppe | Complete event trend detection in high-rate event streams[END_REF][START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF], is described in Query 1 using the syntax from SASE [START_REF] Wu | High-performance complex event processing over streams[END_REF]. Query 1 detects an increasing and then decreasing pattern per company. Hence, the price of the events must first increase from an initial value (a.price < b.price), then the events should show an uptrend (b.price < NEXT(b.price)) using the Kleene+ operator, and then the price of the matched events should decrease such that it is less than the first reported increase (c.price < FIRST(b.price)). All the matched events should To reveal all the profit opportunities, Query 1 detects all the combinations of patterns using an operator called as skip-tillany-match event selection strategy in the literature [START_REF] Agrawal | Efficient pattern matching over event streams[END_REF][START_REF] Poppe | Complete event trend detection in high-rate event streams[END_REF][START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF]. This operator assists in ignoring the local price fluctuations to preserve opportunities for detecting longer and thus more reliable patterns. Fig. 1 shows the evaluation of Query 1 over an event stream. From Fig. 1 (a), before the arrival of an event c 1 , six partial matches (shown with the connected lines) for a 1 and a 2 are produced, and one for each b 1 and b 2 . Note that the prefix of the Query 1 is highly unselective ( a.price < b.price) and any event can start a partial match. Consequently, there can be a large number of partial matches that would not produce full matches, which result in wasted computation. The complete set of matches, after the arrival of a trigger event c 1 are shown in Fig. 1 (b).

c 1 b 2 b 1 a 2 a 1 time Window (a 1 , b 1 , c 1 ) (a 1 , b 2 , c 1 ) (a 1 , b 1 ,b 2 , c 1 ) (a 2 , b 1 , c 1 ) (a 2 , b 2 , c 1 ) (a 2 , b 1 ,b 2 , c 1 ) (a) (b)
State of the art and limitations. The issues with a large number of partial matches and their effect on the memory and CPU resources have been acknowledged in the literature [START_REF] Agrawal | Efficient pattern matching over event streams[END_REF][START_REF] Kolchinsky | Lazy evaluation methods for detecting complex events[END_REF][START_REF] Poppe | Complete event trend detection in high-rate event streams[END_REF][START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF]. The usual remedy proposed for such issues is to factorise the commonalities between the partial matches that originate from the same set of events [START_REF] Poppe | Complete event trend detection in high-rate event streams[END_REF][START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF]. Hence, the query evaluation is broken into two phases. The first phase tracks the commonalities between the partial matches and compresses them using an additional data structure, e.g. an events graph. The second phase constructs the complete matches while decompressing the set of common partial matches, e.g. through depth-first-search. This strategy can reduce the memory requirements from exponential to polynomial, at the cost of the compression/decompression operations. Moreover, since a sub-partial match can be part of multiple complete matches, this strategy recomputes common sub-partial matches for each match that contains one. This results in redundant computations, and the high cost of maintaining additional structure and reconstruction of the matches remains quite significant. For instance, in Fig. 1 (a), all the partial matches are kept -and computed -even if a trigger event, i.e. c 1 , never arrives within a window. Finally, due to the high space complexity, these systems spend a considerable amount of time in repeated memory allocation and reclamation with the expiration of a window.

Contributions. This paper initiates the study of a recomputationbased CEP that addresses the following two main points.

• Since storing partial matches is expensive, only events should be stored in a window. This reduces the memory cost from polynomial or exponential to linear • The matches should be recomputed only when the trigger events' arrive and results should be directly stored on the disk. Hence, redundant computations are not performed and only the subsets of events are processed to produce the matches. Furthermore, since matches are directly stored on the disk, repeated in-memory allocation and reclamation operations are avoided. In theory, both recomputation and incremental evaluation techniques have the same worst-case run-time cost. However, in practice, recomputation process provides the following properties: (1) it is performed for a fewer number of times (depending on the trigger events); (2) it alleviates the redundant computations that arrive due to the partial matches that would not produce a complete match; (3) it avoids the cost of creation and deletion of partial matches.

The detailed structure and contributions of this paper are as follow. We first provide the compilation of the query tree for a CEP query ( § 2.2). We then present the design of an algorithm for recomputing matches and analyse its complexity( § 2.3). Based on this algorithm, we present the techniques to process joins between events and to execute the Kleene+ operator ( § 2.4). We implemented our solution and demonstrate that it outperforms existing solutions both in terms of memory and CPU cost ( § 3).

RECOMPUTATION BASED CEP 2.1 Preliminaries

In this section, we present the CEP specifics definitions, query representation and query evaluation techniques.

Event. An event e is tuple (A, t), where

A = {A 1 , A 2 , . . . , A m } (m ≥ 1
) is a set of attributes and t ∈ T is an associated timestamps that belongs to a totally ordered set of time points (T, ≤).

Event Stream. An event stream S is a possibly infinite set of events such that for any given timestamps t and t ′ , there is a finite amount of events occurring between them.

Event Sequence. A chronological ordered sequence of events, with a total ordering given by T is represented as ì E = ⟨e 1 , e 2 , . . . , e n ⟩ with e 1 refer to the first event and e n to the last. CEP Query. A CEP query Q has the following form:

PATTERN P [ WHERE Θ ] WITHIN w SLIDE s
where P = SEQ(p 1 , . . . , p k ) is a sequence of pairwise disjoint variables of the form p and p + , Θ = θ 1 , . . . , θ l is a set of predicates (constant and variable) over the variables in P (see Query 1 in Example 1), ω is the time window and s is slide of the window to define the scope of event stream. A variable p ∈ P binds a sequence of a single event ⟨e i ⟩, while the qualified variables p + ∈ P binds a sequence of one or more events ⟨e 1 , . . . , e n ⟩, n ≥ 1 for a query match.

CEP Query Match. To define the matching of a CEP query Q, we use a substitution γ ={p 1 / ì E 1 , . . . , p k / ì E k } to bind the event sequences ( ì E) with the variables. Given Q and the event stream S, a substitution γ is a match of Q in S, iff (i) all the predicates Θ in Q evaluate to true, (ii) for events in the two event sequences e ∈ ì E i and e ′ ∈ ì E i+1 , we have e.t < e ′ .t and (iii) all the events in each event sequence ì E i has timestamps less than the defined window w. Since no order is imposed on the selected events, it complies to the skip-till-any-match selection strategy.

Query Tree

Given the CEP query, we need to compile it from the high-level language into some form of automaton [START_REF] Agrawal | Efficient pattern matching over event streams[END_REF][START_REF] Brenna | Cayuga: A high-performance event processing engine[END_REF][START_REF] Flink | [END_REF][START_REF] Wu | High-performance complex event processing over streams[END_REF] or a treelike [5,[START_REF] Mei | Zstream: A cost-based query processor for adaptively detecting composite events[END_REF] structure to package the semantics and execution framework. Since we are working with the recomputation-based model, a traditional tree structure customised for the streaming and recomputation settings would suit our needs. Given Q we construct a tree, where leaf nodes are the substitution pairs, i.e. (p i / ì E i ), to store the primitive events and the internal nodes represent the joins on the defined predicates Θ and temporal ordering. We call it a query tree T q . Our model differs from other tree-structures [5, 11] since we do not store any partial matches.

An example of such a tree for Query 1 is shown in Fig 2, where we have three leaf nodes for the variables bindings a/ ì

E 1 , b/ ì E 2
and c/ ì E 3 . The internal nodes in Fig. 2 evaluate the defined Θ in terms of joins (denoted as Θ ) for all the variables p ∈ P. Furthermore, since for a CEP query, the matched events should follow the sequential order, joins on the timestamps (denoted as t ) are also provided in the T q .

! "

Θ a Θ b # a / E 1 # b+ / E 2 # c / E 3 # a / E 1 # b+ / E 2 # c / E 3 (a) (b) ! " Θ b Θ c ! " Θ a Θ b ! " Θ b Θ c

Query Evaluation

We now present the algorithm to evaluate the query tree over the event stream without storing the partial matches. Algorithm 1 shows the query evaluation and is divided into three main steps.

Step 1. For each incoming event e, we add e to the compatible event sequence ì E i , such that constant predicates (e.g. a.price > 10 ) filter the unwanted events for each ì E i in T q . For instance, for a constant predicate a.price > 10, all the events in a/ ì E i , should have the price > 10. This step (lines 4-6) constitutes to the accumulation of events within a defined window.

Step produces the matches only when an event of type c arrives. Hence, we execute the query tree for a trigger event. By execution, we mean executing the joins between events within each ì E i using the predicates Θ and timestamps t. This step (lines 7-8) assembles all the events, in a batch manner, for each ì E i that can produce the set of matches.

Step 3. For a p + i ∈ P, we need to compute all the combinations for the events in p + i / ì E i , i.e. a power set of events in ì E i . For instance, in Fig. 1 and using Query 1, each a event has 2 |2| -1 matches for two b events. This step (line 9) groups all the combinations by following the one or more semantics of the Kleene+ operator.

Detailed Analysis

We now present the details of the two main processes of Algorithm 1, i.e. joining the set of events and computing the power set of events for the Kleene+ operator.

Execution of Joins.

Let ì E i and ì E j are two event sequences with theta-join ì E i t Θ ì E j over the timestamp t and predicates Θ. Hence, we have joins on multiple relations for the Step 2.

The generic cost of such joins, i.e. pairwise join, is

O(| ì E i || ì E j |)
and the problem of its efficient evaluation resembles the traditional theta-joins with inequality predicates [START_REF] Khayyat | Fast and scalable inequality joins[END_REF]. The wide range of methods for this problem includes: the textbook merge-sort, hash-based, band-join and various indices such as Bitmap [START_REF] Garcia-Molina | Database systems -the complete book[END_REF]. These techniques are mostly focused on equality joins using a single join relation, however. The inequality joins on multiple join relations are notoriously slow and multi-pass projection-based strategies [START_REF] Bentley | Data structures for range searching[END_REF][START_REF] Khayyat | Fast and scalable inequality joins[END_REF] are usually employed. These strategies, however, require multiple sorting operations, each for a distinct relation, and are only optimised for the static datasets, where indexing time is not of much importance. Considering this, we employ the general nested-loop join for our preliminary algorithm. Our experimental analysis showcase that even such a naive algorithm provides competitive performance.

Execution of Kleene+ Operator. For Step 3, we need to create all the possible combinations of matches over the joined events. That is, enumerating the powerset of event sequences' with p + bindings. A traditional solution in this context would be to generate Gray code sequence of events with p + bindings, where a new match can be constructed from its immediate predecessor by adding or removing an event. However, this would require storing the predecessor matches to produce the next one and would result in an extra load on the memory resources. To implement Kleene+ operator efficiently, we use the joined results (from Step 2) while generating the binary representation of the

c 1 b 2 b 1 a 2 a 1 b 2 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 ! a / E 1 ! b+ / E 2 ! c / E 3
Figure 3: Execution of the Kleene+ operator using the Banker's sequence and generated binary numbers possible matches using the Banker's sequence [START_REF] Loughry | Efficiently enumerating the subsets of a set[END_REF]. That is, we check the number of events in event sequences' with p + bindings after the join process. For |m| number of such events, we need to create 1 to 2 m -1 matches. This means if we generate all binary numbers from 1 to 2 |m | -1, and translate the binary representation of numbers according to the location of the events in the p + / ì E i , we can produce all the matches for the Kleene+ operator in a batch manner. For instance, consider Fig. 3 (using Query 1), where there are three b events for the Kleene+ operator. Hence, we generate binary numbers from 1 to 2 3 -1. Now equates 1 as take element at the specified location of the ì E 2 and 0 as do not take the element. Then using the generated binary numbers, we generate all the combinations of matched events.

Complexity Analysis. Herein, we briefly present the complexity analysis for the three steps described in Algorithm 1.

Step 1 results in a constant time operation since an incoming event can be directly added to an event sequence.

Step 2 has a polynomial time-cost (pair-wise joins) and depends on the number of patterns P defined in a CEP query. For n events in a window and k = |P |, we have O(n k ).

Step 3 requires producing an exponential number of matches for a Kleene+ operator. For n events in a window, we have O(2 n ). The memory cost for the Algorithm 1 is linear to the number of events within a window.

EXPERIMENTAL EVALUATION

In this section, we report the results of our experimental study on both incremental and recomputation-based methods for CEP. Our proposed techniques have been implemented in Java and our system is called RCEP. All the experiments were performed on a machine equipped with Intel Xeon E3 1246v3 processor and 32 GB of memory. For robustness, each experiment was performed 3 times and we report median values.

Datasets. We employ both real and synthetic datasets to compare the performance of our proposed techniques. Synthetic Stock Dataset (S-SD): We use the SASE++ generator, as used in [START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF], to produce the synthetic dataset. Each event carries a timestamp, company-id, volume and the price of a stock. This dataset enables us to tweak the selectivity measures of matches #of Matches #of event s to evaluate the performance of the systems at different workloads. In total, the generated dataset contains 1 million events.

Real Credit Card Dataset (R-CCD): We use a real dataset of credit card transactions [START_REF] Artikis | A prototype for credit card fraud management: Industry paper[END_REF]. Each event is a transaction accompanied by several arguments, such as the time of the transaction, the card ID, the amount of money spent, etc. This dataset contains around 1.5 million events.

Queries. We consider 8 different variations of Query 1 (Section 1) against the stock dataset. These queries variations differ by the constant predicates and time window to control the selectivity of produced matches. For the credit card dataset, we use a CEP query describing "Big after Small"pattern [START_REF] Artikis | A prototype for credit card fraud management: Industry paper[END_REF] using the SEQ(a, b+) template. That is, an outstandingly large amount of transactions after one or a series of small amounts.

Methodology. We compare RCEP with the SASE++ [START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF] and the open source streaming system Apache Flink [START_REF] Flink | [END_REF]. All of these systems support skip-till-any-match and Kleene+ operator: both SASE++ and Flink employ incremental evaluation of partial matches. Flink guarantees that events are processed in parallel but in-order by their timestamps. Unless otherwise specified, all experiments use a slide granularity s = 1. We measure two standard metrics common for the CEP systems: throughput and memory requirements [START_REF] Agrawal | Efficient pattern matching over event streams[END_REF][START_REF] Poppe | Complete event trend detection in high-rate event streams[END_REF][START_REF] Zhang | On complexity and optimization of expensive queries in complex event processing[END_REF]. The memory requirements were measured by considering the resident set size (RSS) in MBs. RSS was measured using a separate process that polls the /proc Linux file system, once a second. We use the selectivity measures #of Mat ches #of Event s and window size to test different workloads. Memory Cost. Figs. 4 (a) and (b) show the memory consumption of all the systems for both datasets. As expected, increase in the selectivity measures (subsequently window sizes) results in a large number of partial matches and an extensive memory cost for both SASE++ and Flink. In particular, Apache Flink consumption is exponential in terms of the number of events in the window. SASE++ managed to sustain memory requirement due to the superior compression of Kleene+ matches. However, with the increase in the number of events that prefixed a new partial match, its memory utilisation increases to about two orders of magnitude compared to our recomputation-based approach. This phenomenon is largely observed in Fig. 4 (b), where the credit card dataset contains a large number of events that can initiate a new partial match. In contrast, RCEP scales linearly to the number of events within a window and not the partial matches. CPU Cost. Figs. 4 (c) and(d) show the relative performance of the CEP systems over both datasets. We can see that, in general, RCEP have much higher throughput (more than an order of magnitude) than Flink and SASE++. As a matter of fact, SASE++ and Flink do not produce results for several hours for the moderate selectivities and window sizes. This is because the cost of SASE++ and Flink is highly dependent on the number of partial matches within a window. As the window size (subsequently selectivity) increases, both systems produce a large number of partial matches and spend most of their time in compressing and decompressing of the common events within the partial matches. That is, traversing through the stack of pointers using depth-first-search to extract all the matches. In contrast, (i) RCEP initiates the recomputation of matches only if the triggered events' arrive; (ii) the execute joins over the stored events; and (iii) the Kleene+ operator is executed only for the events that can be part of the final matches. Hence, RCEP performs much better and consume less memory than SASE++ and Flink, often by 1-2 orders of magnitude.

LOOKING AHEAD

In this preliminary study, we have highlighted the utility of recomputation-based CEP for expensive CEP queries. We have proposed our first algorithm for recomputing the matches with the arrival of new events. To our knowledge, ours is the first algorithm of this kind in the context of CEP. Our experimental results show that recomputation-based approach outperforms the incremental approach used by the existing systems.

Our study opens up several directions for the future work. A major direction is to establish techniques to efficiently store and index events within a defined window. Without this, we cannot discard events within an event sequence unless it is accessed and compared with all the other events. Hence, the indexing of events would enable us to prune irrelevant events before the joining process. Further, we plan to consider new algorithms for the multi-relational and inequality joins in the streaming settings since existing algorithms are only effective for the static workloads and require extensive indexing time. Finally, we would like to incorporate our solution in the open-source Apache Flink framework.

Figure 1 :Query 1 .

 11 Figure 1: (a) Partial matches for Query 1 over the event stream, (b) complete matches for the Query 1

Figure 2 :

 2 Figure 2: (a) Left-deep and (b) Right-deep Query tree for Query 1 in Example 1

Figure 4 :

 4 Figure 4: Memory cost and throughput analysis of the CEP systems over the two datasets S-SD and R-CCD

  Query Tree T q and an event stream S Output: A set of query matches 1 Q ← (P, Θ, ω, s) ; // CEP Query

	2 ì E ← { ì E 1 , ì E 2 , . . . , ì E k }, k = |P | ;	// Event sequences for T q
	3 for each e ∈ S do
	4	for each ì E i ∈ ì E do
	5	if isCompatible( ì E i ,e) then
	6	ì E i = ì E i ∪ e ;	// Step 1
	7	if isCompatible( ì E k ,e) then
	8	ExecuteJoins( ì E, Θ);	// Step 2
	9	ExecuteKleenePlus( ì E, Θ);	// Step 3

2. For each incoming event e, check if it can trigger the query evaluation to produce matches. That is, if e can be part of ì E k (k = |P |), it can complete a set of matches; since it contains the highest timestamp within the window. For instance, Query 1 Algorithm 1: CEP Query Evalution Input: