Balázs Németh

Péter Gáspár
email: gaspar.peter@sztaki.mta.hu

Zoltán Szabó
email: szabo.zoltan@sztaki.mta.hu

József Bokor

Olivier Sename
email: olivier.sename@gipsa-lab.grenoble-inp.fr

Luc Dugard
email: luc.dugard@gipsa-lab.grenoble-inp.fr

DESIGN OF FAULT-TOLERANT CONTROL FOR TRAJECTORY TRACKING

Keywords: fault-tolerant control, reconfiguration, fault detection, linear parameter varying control, robust control, autonomous systems

The paper proposes a fault-tolerant integrated control system with the brake and the steering for developing a driver assistance system. The purpose is to design a fault-tolerant control which is able to guarantee the trajectory tracking and lateral stability of the vehicle against actuator fault scenarios. Since both actuators affect the lateral dynamics of the vehicle, in the control design a balance and priority between them must be achieved. The method is extended with a fault-tolerant feature based on a robust LPV method, into which the detected fault information are incorporated. The control design is performed by using the Matlab/Simulink software and the verification of the designed controller is performed by using the CarSim software.

INTRODUCTION AND MOTIVATION

The purpose of fault-tolerant trajectory tracking is to follow a road geometry and guarantee the road stability of the vehicle in case of fault events as well. The control system includes the brake and the steering for developing a driver assistance system [START_REF] Zin | An LPV/Hinf active suspension control for global chassis technology: Design and performance analysis[END_REF][START_REF] Rajamani | Demonstration of integrated longitudinal and lateral control for the operation of automated vehicles in platoons[END_REF]. Since the actuators affect the same dynamics of the vehicle, in the operation of autonomous control systems interference or conflicts may occur between the control components. In the control design the interaction between the actuators must be taken into consideration and a balance between them must be achieved. It has been guaranteed by the integration of control components.

The paper proposes a fault-tolerant control system with several active components for developing a driver assistance system. The purpose of the control is to generate control inputs, such as steering angle, difference in brake forces and longitudinal forces, in different directions. The detected fault information is considered in order to guarantee the reconfigurable and fault-tolerant operation of the vehicle. The paper extends the previously published papers in the integrated control design topic [START_REF] Németh | Model-Based Robust Control Deisgn of Integrated Vehicle tracking System[END_REF][START_REF] Németh | Design of actuator interventions in the trajectory tracking for road vehicles[END_REF] with a fault-tolerant reconfiguration strategy.

The paper is organized as follows: in Section 2 the control-oriented formulation of vehicle model is proposed, while the lateral trajectory tracking and the closed-loop interconnection structure are described in Section 3. In Section 4 the architecture and control strategy of fault-tolerant control is presented. Section 5 presents simulation results.

VEHICLE MODEL FOR TRAJECTORY TRACKING CONTROL

In the design of trajectory-tracking assistance systems it is necessary to guarantee that the vehicle must perform the desired motion of the driver. The control system of the lateral vehicle dynamics assists the driver to track road geometry. It has advantages in critical situations, where the driver is not able to ensure vehicle stability. In trajectory tracking the vehicle is moving in the entire plane of the road, thus both the longitudinal and the lateral dynamics must be taken into consideration as Figure 1 shows.

Figure 1: Lateral dynamic model of vehicle

Two actuators are used in the system, i.e., the front-wheel steering angle δ and the differential brake torque br M . In most of the lateral control problems, the lateral dynamics of the vehicle can be approximated by the linear bicycle model of the vehicle:

br r f M l C l C J + - α α ψ 2 2 1 1 = & & (1) r f C C mv α α β ψ 2 1 = ) ( + + & & (2)
where m is the mass, J is the yaw-inertia of the vehicle, 1 l and 2 l are geometric parameters, 1 C , 2 C are cornering stiffnesses, ψ& is the yaw rate of the vehicle, β is the side-slip angle. Moreover,

v l f / = 1 ψ δ β α & ⋅ - + - and v l r / = 2 ψ β α & ⋅ + -
are the tyre side slip angles at the front and rear, respectively.

Two control systems will be designed based on the state space representation of the vehicle:

u B x A x ) ( ) ( = ρ ρ + & (3)
where the state vector consists of the yaw-rate and the side-slip angle of the vehicle . Note that in the operation of the driver assistance system the reference signal of the yaw-rate, ref ψ& , is also required.

LPV-BASED CONTROL DESIGN STRATEGY

In the driver assistance system the performance is the minimization of the tracking error of the yaw-rate

! ] [ = 1 min z T ref → -ψ ψ & & (4)
where ref ψ& is the reference yaw rate defined by the driver. Simultaneously, actuator saturations must be avoided. The maximal control input of the steering is determined by their physical construction limits, while in case of the braking system the constraints are determined by the tyre-road adhesion. These constraints will be built into the weighting strategy applied in the control design. The other performance of the system considering the control input is formulated as

! | =| 2 min u z → (5)
The generation of the different actuators is based on the following weighting strategy.

The weighting for the front wheel steering and that for the brake yaw-moment are

max st st act W δ ρ / = , ( 6
) brmax br Mbr act M W / = , ρ (7)
respectively, where max δ is determined by the constructional maximum of the steering, while brmax M is the maximum of the brake yaw-moment. Weighting factors br st ρ ρ , are chosen to influence the actuation of the steering and the brake yaw-moment. The formulated act W and Mbr act W , weights are considered in the control design to influence actuator intervention. The actuator selection procedure and the priorities of actuators depending on vehicle dynamic situations can be found in [START_REF] Gáspár | Design of an integrated control for driver assistance systems based on LPV methods[END_REF].

The control design is based on a weighting strategy, which is formulated through a closed-loop interconnection structure, see Figure 2. In the trajectory tracking problem the yaw-rate reference signal is introduced in order to guarantee the tracking of the road geometry:

T ref R ] [ = ψ&
. Usually the purpose of weighting function p W is to define the performance specifications in such a way that a trade-off is guaranteed between them. The weighting function for performance specification is selected in a secondorder proportional form. The purpose of the weighting functions w W and n W is to reflect the disturbance and sensor noises. Weighting functions, act W , are applied for the actuators one for the brake yaw-moment and the other one for the steering angle.

The control design is based on the LPV method that uses parameter-dependent Lyapunov functions, see [START_REF] Wu | Induced l 2 -norm control for LPV systems with bounded parameter variation rates[END_REF]. The quadratic LPV performance problem is to choose the parameter-varying controller

) (ρ K
in such a way that the resulting closed-loop system is quadratically stable and the induced 2 L norm from the disturbance and the performances is less than the value γ . The existence of a controller that solves the quadratic LPV γ-performance problem can be expressed as the feasibility of a set of Linear Matrix In-equalities (LMIs), which can be solved numerically. Finally, the state space representation of the LPV control K(ρ) is constructed, see [START_REF] Packard | Theory and application of linear parameter varying control techniques[END_REF]. When the controller has been synthesized, the relation between the state and the variable is used such that a nonlinear controller is obtained. Stability and performance are guaranteed by the design procedure.

ARCHITECTURE AND RECONFIGURATION OF THE CONTROL SYSTEM

The purpose of control design is to calculate the necessary front steering angle and brake yaw moment. The design of this upper level controller is based on the LPV method. Then the designed longitudinal force and brake yaw moment are distributed between the four wheels of the vehicle. Moreover, a third layer is also necessary since the required control forces must be tracked by using a low-level controller. This controller transforms the wheel forces and the values of the steering angle into a real physical parameter of the actuator. These components are implemented by Electronic Control Units (ECUs).

The design of a low-level steering controller might use more specific techniques that fit the specific nonlinear properties of the actuator. The steer-by-wire front steering system transforms the steering angle into a real physical parameter of the actuator. The real physical input of the system is the Pulse Width Modulated (PWM) signal of the electric servo motor, which moves the rack. The physical construction of electric steering has several variations, see e.g. [START_REF] Claeys | Modeling and control of steering actuator for heavy duty vehicle[END_REF]. Figure 3 shows the architecture of the low-level steering controller. The architecture of the controlled supervisory system is shown in Figure 4. In the fault-tolerant scheme fault detection and isolation filters (FDIs) for actuators are assumed to be used. In this paper two kind of actuator faults are considered: the fault of the steering control system and the fault of the braking circuits. There may be various fault scenarios, e.g the leakage of the hydraulic systems in braking or steering servo, or the steering mechanism becomes jammed. The different change in the operation of an actuator makes it possible to realize the detection of fault. The filters are able to detect different types of faults in the operation of the actuators. An ∞ H method to design a fault detection and isolation LPV filter was presented by [START_REF] Bokor | Detection filter design for LPV systems -a geometric approach[END_REF]. Two actuators are operated in cooperation in order to provide a reconfigurable faulttolerant control system. In case of a detected fault either the brake yaw moment br M or the front wheel steering δ can be changed, which have similar dynamic effects.

When a fault occurs in the operation of the steering system, all the lateral control tasks must be realized by using the braking system with the generation of the brake yaw moment br M . In the fatal error in the operation of the steering system the weight of steering is masked:

0 = st ρ (11)
When a fault occurs in the operation of a brake circuit the actuated brake yawmoment is reduced. Moreover, the reduction of the brake yaw-moment is asymmetric. For example, in case of the fault of a brake circuit on the left-hand side of the vehicle, the generated positive brake yaw-moment is reduced, or it is zero. In this case steering is activated to substitute for the actuation of braking and provide trajectory tracking. However, the negative br M can be realized by the healthy right brake circuits. Consequently, the weight of braking br ρ depends on the sign of the desired br M . In the case of a left-hand-side brake circuit fault, positive br M is not allowed, therefore where i κ is selected according to Figure 5.

Figure 5: Weighting functions at brake faults

SIMULATION RESULTS

The vehicle is traveling along a predefined road, while the integrated control system supports the driver to guarantee trajectory tracking. During the simulations different faults occur and these faulty cases are compared with a healthy simulation. A typical E-Class automobile is applied in the simulation. The mass of the 6-gear car is 2023 kg its engine power is 300 kW ( 402 hp ). The width of the track is 1605 mm and the wheel-base is 3165 mm . In the simulation examples the vehicle is traveling along a section of Waterford Michigan Race Track with a given velocity, which are shown in Figure 6. In the first simulation a steering fault occurs in the controlled system. Note that the driver assistance system is not able to modify front wheel steering angle, but the driver can steer the front wheels. The control system actuates only brake yaw-moment br M . Figure 7 shows the faulty simulation case compared with a healthy one. The lateral error of the system and the yaw-rate tracking are illustrated in Figure 7 In the second simulation example in both of the rear brake circuits are faults occured. In Figure 8 the effects of brake faults are shown. In the first curve the lateral error of the vehicle increases significantly, because only steering actuator can be actuated during the vehicle maneuver, see Figure 8(b). Since differential braking actuation cannot be used because of the fault, see Figure 8(c), the intervention of brake must be replaced by additional steering angle. However, Figure 8(a) illustrates that lateral error of the vehicle in faulty scenario is smaller, compared to an uncontrolled vehicle. It means that the integrated control system can be used effectively not only in healthy, but also in faulty situations as well.

.

  In the brake control case the input of the system is br M u = , while in the steering control case the input is δ = u . The measured output of both systems is the yaw-rate, ψ& = y

Figure 2 :

 2 Figure 2: Closed-loop interconnection structure

Figure 3 :

 3 Figure 3: The low-level driveline control structure

Figure 4 :

 4 Figure 4: Architecture of fault-tolerant control system

Figure 6 :

 6 Figure 6: Trajectory and velocity of vehicles

  (a) and Figure 7(b).

Figure 7 :Figure 8 :

 78 Figure 7: Steering fault example compared to healthy scenario

CONCLUSION

The paper has proposed the design of a supervisory integrated reconfigurable driver assistance system which is able to track road geometry. The actuators of the control system are the front-wheel steering and the brake yaw-moment. The paper extends the control design with an actuator selection procedure, which is built in the design of the supervisor of the system. The control design of actuators is based on the robust optimal LPV method, in which both performance specifications and model uncertainties are taken into consideration. A possible realization of the required control system has also been presented. The integrated system makes it possible to achieve a reconfigurable and fault-tolerant system. The fault-tolerance of the controlled system is demonstrated by simulation examples.

ACKNOWLEDGEMENT

This work was supported by the TÁMOP-4.2.2.A-11/1/KONV-2012-0012: Basic research for the development of hybrid and electric vehicles. and the PICS-CROTALE projects.


Masayuki Yabuki

David J Scott

Loı ¨c Briand

Andrew J Taylor
email: andy.taylor@nott.ac.uk

Dynamics of Odorant Binding to Thin Aqueous Films of Rat-OBP3

Keywords: APCI-MS, capillary, in vitro, mass transfer, odorant-binding protein, olfactory mucus, peri-receptor

Uptake, retention and release of 5 selected odorants (benzaldehyde, 2-methylpyrazine, 2-isobutyl-3-methoxypyrazine, 2-isobutylthiazole, and 2,4,5-trimethylthiazole) by recombinant rat odor-binding protein 3 (rat-OBP3) were measured in a model system under nonequilibrium conditions. Gaseous odorants were introduced into a 100 mm section of a polar deactivated capillary in which aqueous rat-OBP3 films were formed to mimic the olfactory epithelium (OE), and the change in the gas-phase concentration of the outflow gas was monitored in real time using atmospheric pressure chemical ionizationmass spectrometry (APCI-MS). The 5 odorants were chosen because they exhibited a broad range of dissociation constants with rat-OBP3 and because they were amenable to detection by on-line APCI-MS. All 5 odorants were quantitatively bound by rat-OBP3, which resulted in an effective concentration of the odorants in the aqueous layer (about 50 000-fold). Odorant release from the rat-OBP3-odorant complex into the gas phase showed that odorant release was governed by the dissociation constant of the complex and the flow rate of odorant-free air. When 2 odorants were introduced into the system, odorant uptake and release were influenced by the method of introduction and their relative affinities for the protein. Because rat-OBP3 exhibits typical odorant-binding characteristics, the results not only provide fundamental information on the kinetics of odorant mass transfer induced by the presence of OBPs in the olfactory mucus layer but also support the possibility that vertebrate OBPs may facilitate the accumulation of odorants in the OE.

Introduction

In vertebrates, the initial stage of the olfaction process involves several interlinked mass transfer processes. Initially, odorants in the gas phase are transported differentially through the nasal cavity, then they transfer from the gas phase into the liquid mucus layer close to the olfactory epithelium (OE) and may bind with odor-binding proteins (OBPs). This is the so-called the peri-receptor stage [START_REF] Pelosi | Perireceptor events in olfaction[END_REF]. The next stage involves binding of the odorant to the olfactory receptor (OR) and the subsequent transduction mechanisms. Whereas OR-odorant binding is well researched and the general principles understood [START_REF] Breer | The sense of smell-reception of flavors[END_REF], the peri-receptor stage is a highly dynamic process, which is not so well characterized. In particular, the role of the OBP is unclear and several different hypotheses have been proposed to explain their function. In addition to their odorant-binding property, their high concentrations (0.1-1 mM) [START_REF] Pelosi | Perireceptor events in olfaction[END_REF] and spatial expression in vivo [START_REF] Pevsner | Odorant-binding protein-localization to nasal glands and secretions[END_REF] suggest that OBPs play an active role in olfaction, such as in peripheral odor coding [START_REF] Steinbrecht | Odorant-binding proteins: expression and function[END_REF][START_REF] Lo ¨bel | Odorants of different chemical classes interact with distinct odorant binding protein subtypes[END_REF], solubilizing odorants (Pevsner et al. 1990), transferring odorants to and from the ORs [START_REF] Pevsner | Odorant-binding protein-localization to nasal glands and secretions[END_REF][START_REF] Bignetti | Specificity of an immunoaffinity column for odorant-binding protein from bovine nasal-mucosa[END_REF]Pevsner and Snyder 1990;[START_REF] Pelosi | Odorant-binding proteins[END_REF] or the buffering effect [START_REF] Taylor | Role of odor binding protein: comparing hypothetical mechanisms with experimental data[END_REF].

To elucidate the role of OBPs in the olfaction process, odorant binding to OBP has been studied to determine fundamental parameters such as the dissociation constant (K d ). K d indicates the potential of the odorant-OBP liquid phase system to react to concentration changes. It is a value that is measured at equilibrium in the liquid phase, using bulk phase conditions and long time periods [START_REF] Nespoulous | Odorant binding and conformational changes of a rat odorant-binding protein[END_REF]). Few publications have considered the overall air-liquid-OBP mass transfer process where several mass transfer processes are linked for example, the gas phase concentration, the air-liquid partition coefficient, diffusion through the liquid phase, and odorant-OBP binding. Because the odorant concentration in the air phase will cycle between zero (on exhalation) to the measured value (on inspiration), the overall mass transfer is a highly dynamic process, which is unlikely to achieve equilibrium. Previous work [START_REF] Borysik | Rapid odorant release in mammalian odour binding proteins facilitates their temporal coupling to odorant signals[END_REF]) used a system that mimicked the overall mass transfer process, and results suggested that the interdependency of the mass transfer processes gave different emphasis to the values obtained from classical kinetic measurements. For instance, the slow off-rates observed in odorant-OBP measurements (using liquid-only phases; [START_REF] Lazar | Molecular and functional characterization of an odorant binding protein of the Asian elephant, Elephas maximus: implications for the role of lipocalins in mammalian olfaction[END_REF] are not observed in systems that couple the mass transfer processes [START_REF] Borysik | Rapid odorant release in mammalian odour binding proteins facilitates their temporal coupling to odorant signals[END_REF]. Other factors like airflow, surface area, and partition coefficients are also involved in overall mass transfer and they may exert significant effects on the odorant-OBP binding through a ''push-pull'' effect.

The effect of airflow in the nose has been studied by several research groups to understand the relative flows through the convoluted nasal passages and the proportion of air entering the nostrils that actually passes over the OE. Several studies have used computed tomography scans to determine the exact structure of the nasal passages in humans (e.g., [START_REF] Keyhani | Numerical simulation of airflow in the human nasal cavity[END_REF][START_REF] Zhao | Effect of anatomy on human nasal air flow and odorant transport patterns: implications for olfaction[END_REF][START_REF] Croce | In vitro experiments and numerical simulations of airflow in realistic nasal airway geometry[END_REF][START_REF] Ishikawa | Visualization of flow resistance in physiological nasal respiration: analysis of velocity and vorticities using numerical simulation[END_REF][START_REF] Ishikawa | Flow mechanisms in the human olfactory groove numerical simulation of nasal physiological respiration during inspiration, expiration, and sniffing[END_REF] and in dogs [START_REF] Craven | The fluid dynamics of canine olfaction: unique nasal airflow patterns as an explanation of macrosmia[END_REF]). These structures have been used with computational fluid dynamic (CFD) techniques to obtain values for linear gas flow at different nasal locations during normal ''resting'' breathing. For example, the work of [START_REF] Croce | In vitro experiments and numerical simulations of airflow in realistic nasal airway geometry[END_REF] reported a linear velocity of 0.4 m/s in the human olfactory region, a value which agrees closely with the work of [START_REF] Ishikawa | Flow mechanisms in the human olfactory groove numerical simulation of nasal physiological respiration during inspiration, expiration, and sniffing[END_REF] (0.3-0.4 m/s). These papers suggest that under resting breathing conditions, only a small proportion of the airflow passes over the OE on inspiration but more flows over the OE during expiration. In odorant perception terms, this equates to orthoand retronasal stimulation of the OE. During orthonasal sniffing (when greater volumes of air are inhaled), the flow patterns are shifted so that a greater proportion of the total flow passes the OE during inspiration [START_REF] Ishikawa | Flow mechanisms in the human olfactory groove numerical simulation of nasal physiological respiration during inspiration, expiration, and sniffing[END_REF]). These studies provide accurate values for overall nasal flow and values for the linear velocities near the OE. Deposition of odorants and nanoparticles during orthonasal breathing have been predicted by adding a partition coefficient term to the CFD calculation [START_REF] Kurtz | Experimental and numerical determination of odorant solubility in nasal and olfactory mucosa[END_REF][START_REF] Jiang | Airflow and nanoparticle deposition in rat nose under various breathing and sniffing conditions: a computational evaluation of the unsteady and turbulent effect[END_REF], although none of the published papers studied appears to use OBP-specific terms in their calculation of odorant deposition.

Given the continuing uncertainty about the role of OBP in peri-receptor events, an experimental system (Dynamic Biomimetic assay for Odorant Binding System [DyBOBS]) was developed to mimic the conditions found in the human OE and to encompass the mass transfer processes involved [START_REF] Yabuki | DyBOBS: a dynamic biomimetic assay for odorant-binding to odor-binding protein[END_REF]. The airflow, the thickness of the liquid layer, the surface area, the odorant concentration, and the concentration of the OBP were all set to values reported in the literature [START_REF] Yabuki | DyBOBS: a dynamic biomimetic assay for odorant-binding to odor-binding protein[END_REF]. Because functional hu-man OBP was not available, rat-OBP3 was substituted as it had a close sequence match to human OBP. A known concentration of odorant was passed at known flow rates (volumetric and linear) through a capillary tube coated with a solution of rat-OBP3 and the concentration of odorant leaving the capillary was monitored in real time using gas phase APCI-MS. This simple experimental system was validated [START_REF] Yabuki | DyBOBS: a dynamic biomimetic assay for odorant-binding to odor-binding protein[END_REF] and showed that isobutylthiazole uptake in the presence of OBP was very different compared with a bovine serum albumin (BSA) control, therefore indicating that OBP changed the mass transfer of this compound during the peri-receptor phase.

In the present work, dynamic binding and release of a wider range of compounds (benzaldehyde (BA), 2methylpyrazine (MP), 2-isobutyl-3-methoxypyrazine (IBMP), 2-isobutylthiazole (IBT), and 2,4,5-trimethylthiazole (TMT)) was studied using DyBOBS. The 5 odorants were used at typical concentrations found in the nasal passages during eating of food [START_REF] Linforth | Retronasal transport of aroma compounds[END_REF]. The choice of compounds was based on 4 criteria. First, they represent the range of physicochemical properties found in odorants (Table 1). Second, because online APCI-MS could monitor them at the concentrations used. Third, because their binding properties with rat-OBP3 in the liquid phase are known [START_REF] Lo ¨bel | Odorants of different chemical classes interact with distinct odorant binding protein subtypes[END_REF][START_REF] Nespoulous | Odorant binding and conformational changes of a rat odorant-binding protein[END_REF]) and fourth, because they exhibit a broad range of dissociation constants with OBP (Table 1). DyBOBS only monitors the odorant concentration in the gas phase and hence measures the net effect of odorant uptake and release. Methods to separate these 2 effects were developed.

We shed some light on various aspects of the initial steps in olfaction under simulated physiological conditions, namely 1. how easily is OBP saturated by an odor ligand? 2. how fast does rat-OBP3 bind and release odor ligands? and 3. how do conditions in the nasal passages (gas flow rate, tidal breathing, and the presence of multiple odorants) affect odorant uptake and release?

For the first part of the investigation, experiments were carried out over long time periods (about 13 min), but for the second part of the investigation, the exposure times were more consistent with physiological conditions.

Experimental procedures

Materials and methods

Odorants (BA, MP, IBMP, IBT, and TMT) >95% purity; Sigma-Aldrich) were dissolved in deionized water at concentrations that delivered gas phase concentrations from 7 to 112 nM (equivalent to 125 and 2500 nl L -1 respectively; calculated from the solution concentration using the air-water partition coefficients in Table 1). Portions of odorant solutions (20 mL) were placed in a gas-tight syringe (100 mL; SGE Analytical Science) and allowed to equilibrate, then odorant delivery from the syringe to DyBOBS was achieved using a syringe pump (KD Scientific). The required flow rate was set on the syringe pump and linear velocities were calculated from the capillary diameter (0.53 mm). Humidified odorant-free air was prepared by equilibrating 20 mL of deionized water in a gas-tight syringe.

Rat-OBP3 was over-expressed using Escherichia coli M15 cells containing both pREP4 and pQE31, as previously described [START_REF] Yabuki | DyBOBS: a dynamic biomimetic assay for odorant-binding to odor-binding protein[END_REF]. BSA (97% purity; Sigma-Aldrich) was used as a control protein. Each protein was dissolved into phosphate-buffered saline (PBS; 137 mM NaCl, 2.7 mM KCl, 10 mM sodium phosphate dibasic, 2 mM potassium phosphate monobasic, pH 7.4) and used for capillary coating using the conditions described before [START_REF] Yabuki | DyBOBS: a dynamic biomimetic assay for odorant-binding to odor-binding protein[END_REF].

Isothermal titration calorimetry

Isothermal titration calorimetry (ITC) measurements were carried out on a MicroCal AutoITC system (MicroCal). Solutions of each odorant were prepared in PBS (300 mM). Titrations were carried out at 21 °C with 30 mM OBP in PBS solution. An initial injection of the odorant solution was followed by 20 more injections of the same solution (14.03 lL each). Blank ligand titrations were also performed to remove the heats of dilution from the odorant/ OBP isotherms. The data were analyzed with ORIGIN 7.0 software using the one-site-per-protein-monomer model that is based on the Wiseman Isotherm [START_REF] Wiseman | Rapid measurement of binding constants and heats of binding using a new titration calorimeter[END_REF].

Dynamic odorant-binding assay using APCI-MS

The preparation of thin aqueous OBP and BSA films followed the method of [START_REF] Yabuki | DyBOBS: a dynamic biomimetic assay for odorant-binding to odor-binding protein[END_REF]. The calculated film thickness for the capillaries used in this study was 1.28 ± 0.07 lm. Five 100-mm capillary sections were taken from a 0.6 m capillary that was internally coated with either a rat-OBP3 PBS solution (0.5-1.25 mM) or a BSA PBS solution (0.5-1.25 mM). The molar amounts of OBP3 in each capillary were calculated from the concentration of the OBP3 solution and the dimensions of the thin film and ranged from 108 (±7) to 271 (±13) picomoles of OBP3. Capillaries were stored in a sealed glass container at room temperature to minimize dehydration and used for experiments within 6 h of preparation.

Online mass spectrometry

A quadrupole mass spectrometer (Platform II) fitted with a custom-built gas phase APCI interface [START_REF] Taylor | Direct mass spectrometry of complex volatile and non-volatile flavour mixtures[END_REF] was used. Gas was sampled into the ionization source at 30 mL min -1 through a heated (105 °C) deactivated fused-silica tube (1 m • 530 lm inner diameter). Figure 1 shows the system schematically. Odorants were ionized by a 4-kV positive ion corona pin discharge source with a dwell-time of 0.2 s to produce protonated molecular ions. The measured masses were m/z 107 for BA, m/z 95 for MP, m/z 167 for IBMP, m/z 142 for IBT and m/z 128 for TMT. Calibration of the APCI-MS was carried out by introducing an odorant solution (hexane) of known concentration into the APCI-MS at a constant flow rate using a syringe pump [START_REF] Taylor | Direct mass spectrometry of complex volatile and non-volatile flavour mixtures[END_REF]. Masslynx 3.2 software (Micromass) was used to record the ion intensity as a function of time.

Calculation of uptake and release of odorants

The uptake of odorant by OBP was calculated using gas flow rates, gas-phase concentrations, and the time to breakthrough, which was defined as the point when the gas-phase odorant concentration reached half-maximal intensity. The amount of odorant released from the aqueous protein film was determined from the area under the release trace, by monitoring the change in gas phase concentration data with time (area under curve).

Dissociation kinetics

The release curve data from the APCI-MS trace was analyzed using GraphPad Prism 5 (GraphPad Software Inc.). The observed off-rate constants for an odorant and rat-OBP3 at a flow rate of 1-20 mL min -1 were determined using the first order exponential decay model equation (Equation 1).

I c À m=z; t Á = ae -kt ; ð1Þ
where I c (m/z, t), refers to the time-dependent ion current for a protonated molecular ion of a particular mass-to-charge ratio and a and k are the amplitude and first-order rate constants describing the decay in the gas-phase odorant concentration during each experiment, respectively. This assumption was derived from the following 2 equations that describe the mass transfer processes involved (Equations 2 and 3).

½OBP: O b Ð k off k on ½OBP + ½O 1 ð 2Þ ½O 1 Ð k v k c  O g à / k ms N ð3Þ
where k off , k on , k v , k c , and k ms are the respective microscopic rate constants for dissociation, association, odorant release, odorant deposition, and APCI-MS consumption.

[OBP:O b ], [OBP], [O l ], [O g ]
are the molar concentrations of the odorant-OBP3 complex, free OBP3, free aqueous odorant, and gas-phase odorant respectively, and N is a sink to the mass spectrometer. Because the OBP and BSA films used in this study were thin (around 1 lm), odorant mass transfer in the liquid phase will be by diffusion and will be of the order of 1 ms [START_REF] Taylor | Role of odor binding protein: comparing hypothetical mechanisms with experimental data[END_REF]. Previous work indicated that changes in the gas phase odorant concentration should be followed by a change in the liquid phase odorant concentration within a period of 100-200 ms [START_REF] Taylor | Role of odor binding protein: comparing hypothetical mechanisms with experimental data[END_REF]. Thus, when the APCI-MS sampling rate, k ms is faster than the time needed for the gas phase odorant to reestablish the steady state, time-dependent changes in free aqueous odorant concentration can be inferred from the changes in gas-phase odorant concentration in the capillary.

Results

Selection of odorants

Air-water partition coefficients, water solubility values, and ITC results (n, binding stoichiometry; K d , dissociation constant) for the 5 odorants used in this study are summarized in Table 1. Odorant concentrations are expressed either in molar or in volume terms depending on context as partition and stoichiometry are expressed as a molar ratios, wheras release is expressed in volumes. The odorants exhibited a wide range of binding affinities for rat-OBP3 from 0.067 • 10 -6 M to 687 • 10 -6 M (K d ) and a range of water solubilities. Air-water partition coefficients were experimentally measured on the APCI-MS [START_REF] Marin | Volatile release from aqueous solutions under dynamic headspace dilution conditions[END_REF] as values in the literature varied considerably for some compounds. Water solubility values were estimated using an on-line software program (ALOGPS 2.1, http://www.vcclab.org). ITC experiments were carried out to determine the dissociation constants (K d values) of the odorants used and to confirm the integrity of the protein. The K d value obtained for IBT (0.067 • 10 -6 M) was 7 times smaller than previously reported in the literature (0.47 • 10 -6 M) [START_REF] Lo ¨bel | Identification of a third rat odorant-binding protein (OBP3)[END_REF]. The inability of BSA, a control protein, to bind the 5 tested odorants was also confirmed using ITC (data not shown).

Binding and release traces using APCI-MS

To compare the effect of OBP concentration on odorant uptake, each odorant was introduced independently into the capillaries coated with a thin film of rat-OBP3 in PBS solution (0.5, 0.75, 1, and 1.25 mM). Control experiments used capillaries coated with the same concentrations of BSA to monitor the effect of dissolution of odorants in the aqueous phase and to assess any nonspecific binding by the BSA protein.

To assess binding capability, the experiment was run over long time periods to saturate the OBP with odorant and determine binding stoichiometry. Figure 2 shows typical APCI-MS traces of gas-phase binding and release of BA from BSA and OBP3 at different concentrations. BA in air (28.4 nM % 640 ppbv) was passed through the OBPcoated capillary for 13 min at 1 mL min -1 , then substituted by odorant-free air from another syringe (same flow rate) up to 35 min. The on-line APCI-MS monitored the concentration of odorant in the gas phase exiting the capillary and the trace can be interpreted as follows. No signal on the trace denoted that the odorant was being completely taken up by the protein film in the capillary while the appearance of odorant signal denoted breakthrough of odorant (in the period up to 13 min) and release of odorant (after 13 min).

Odorant uptake by 0.5 mM BSA was marginal (Figure 2A) as the introduction of BA into the capillary resulted in a rapid rise in the gas-phase odorant concentration, up to the signal level found when a 28.4 nM BA concentration was analyzed directly by the APCI-MS. The rapid rise in APCI signal around t 0 showed that BA binding to BSA was insignificant. The introduction of odorant-free air at 13 min (t r ) caused a sharp decline in the gas-phase odorant concentration to baseline values within 0.5 min. Traces obtained using 0.75-1.25 mM BSA concentrations showed very similar patterns to Figure 2A (data not shown).

In contrast, when BA was introduced into rat-OBP3-coated capillaries, the shapes of the traces were different compared with the BSA trace. Initially, the gas-phase odorant signal remained at baseline level for 3.3 min for the 0.5 mM OBP3 capillary (Figure 2B). This was followed by a sudden increase in the gas-phase odorant concentration. The time (t s ) for BA to break through to the end of the capillary (and achieve a signal level equivalent to 28.4 nM) was delayed as the concentration of OBP3 increased (Figure 2B-E). When the flow was switched to odorant-free air, a gradual decrease in the gas-phase odorant concentration occurred. As OBP3 concentrations increased, the amount of odorant released (as well as the time taken for release) also increased.

Figure 2 Typical APCI-MS traces from capillaries coated with 0.5 mM BSA (A) or with different concentrations of rat-OBP3 (B-E) (t 0 = introduction of odorant-containing air, t s = time when the capillary become saturated with the odorant, t r = introduction of odorant-free air, t f = time when the odorant-free air delivery terminates). BA (28.4 nM) was introduced into the protein-coated capillaries from time 0 to 13 min at 1 mL min À1 . Odorant-free air was introduced into the capillaries for 20 min (from 13 to 33 min) at the same flow rate, and the gas delivery was then turned off at 33 min. The gas-phase BA concentration was monitored (m/z 107) and sub-figures A through E are all on the same y axis scale.

The APCI-MS traces for the 4 other odorants showed similar patterns, but there were differences in the binding and release behaviors, which are analyzed in the following sections.

Odorant uptake by OBP

The amount of OBP on each capillary was calculated (picomoles) and the uptake of odorant by the protein films was calculated from the APCI traces between the t 0 and t s times since the gas flow rate and odorant concentration in the gas phase were known. These calculations were carried out for all 5 odorants tested (see Table 1) and at each OBP3 concentration (0.5-1.25 mM). Stoichiometry values (Table 2) were calculated as the molar ratio between the amount of odorant taken up, divided by the OBP content in a capillary. Overall, there was a small (but insignificant) trend of higher values at low OBP concentrations. Most stoichiometry values were around 1 with only MP showing a value >1. The behavior of MP can be rationalized as it is much more soluble in water than the other odorants tested and its K aw favors the aqueous phase (Table 1). Therefore, over the time to breakthrough, the MP is taken up by both the OBP and the aqueous film and the contribution from the latter may over-estimate the stoichiometry value. By assuming 1:1 MP:OBP stoichiometry, the concentration of MP in the purely aqueous phase was 75 lM. If we assume that equilibrium between the gas and liquid phases is achieved in the condition that DyBOBS was operated in, we can compare the expected liquid phase concentration (248 lM) against the observed value (75 lM). This comparison acts as a sense check in that the liquid phase concentration cannot be more than the equilibrium value (248 lM). Although these calculations are subject to error amplification (as any error in the K aw value exerts a large effect through the calculation process), the values support the hypothesis that the physicochemical properties of MP can explain the fact that the stoichiometry value calculated in this system is an over-estimate. Inspection of the physicochemical data for the other compounds shows that TMT is the only other compound with a K aw value that might encourage water solubility over OBP binding. However, the water solubility of TMT is much lower than MP and this may affect the relative amounts of TMT in the aqueous and bound forms. A simple calculation shows that there is the potential to significantly concentrate odorants in the OBP film. If the gas-phase odorant concentrations are around 20 nM and the OBP concentration is 1 mM, then a 50 000 fold concentration is possible.

Odorant release from OBP

To investigate the dynamics of odorant release from rat-OBP3, the time-dependent changes for the amount of the 5 selected odorants released were calculated from the data used for the calculation of uptake amount. Examples of release traces for BA are shown in Figure 2B-E (from 13 to 33 min). Figure 3A-E shows the total amount of each odorant that was released from the capillary coated with 0.5 mM OBP3 (black triangles) or 1.25 mM OBP3 (black circles). The starting points of the release curves (0 min) in Figure 3A-E correspond to the injection time of odorantfree air as shown at 13 min (t r ) for BA in Figure 2B-E. There was an upward trend in the release amount with an increase in the dissociation constant of the odorant tested (see Table 1), suggesting that the differences in the release amounts between the odorants were attributable to the affinity of the odorant for rat-OBP3. For BA and IBMP, the release amounts from the capillaries coated with a higher (1.25 mM) concentration of OBP3 were greater than those from capillaries with a lower (0.5 mM) concentration of OBP3 film.

Figure 3F-J shows the percentage of released odorant, which is based on the amount of odorant taken up before the introduction of odorant-free air for 0.5 mM rat-OBP3 (open triangles) or 1.25 mM rat-OBP3 (open circles). Overall, at the same OBP concentration, the proportion of the amount released, to the uptake amount, depended on the affinity for OBP3. For example, release of BA, which has the weakest affinity for rat-OBP3 among tested odorants (Table 1), was significant, reaching 84% at the 0.5 mM concentration level (Figure 3F). Full release of BA took about 9 min from the 0.5 mM OBP3 film. At 1.25 mM OBP3, approximately 54% of the BA odorant molecules were released over 5 min. Release of MP and IBMP, which have intermediate affinities for rat-OBP3 of the selected 5 odorants, was moderate, and both exhibited similar release curves (Figure 3G,H). The release of MP at 5 min post-introduction of odorant-free air reached 36% and 21% at 0.5 mM and 1.25 mM, respectively. The release of IBT and TMT, which have small dissociation constants, was insignificant (Figure 3I,J). The release amounts of TMT at 5 min were 19% and 12% at 0.5 and 1.25 mM, respectively (Figure 3I). MP, IBMP, IBT, and TMT were not fully released in the 20 min introduction of odorant-free air. The proportion of odorant molecules released by odorant-free air decreased as the OBP3 concentration increased.

Effect of airflow rate on odorant release

To investigate the effect of airflow rate on odorant release, OBP was fully loaded with odorant, then odorant-free air was introduced at different flow rates. The changes in the release traces for BA and IBT, which were the weakest and strongest binding odorants, respectively (Table 1), are Each odorant (at the concentration in Table 1) was introduced at 1 mL min À1 into the capillary.

shown in Figures 4 and5. Each odorant was introduced into the OBP3-coated capillaries (0.5 mM) at 1 mL min -1 until the system was fully saturated with odorants (6 min). Once saturation was reached, odorant-free air was introduced at a flow rate of 1-20 mL min -1 (linear velocity of 8-153 cm s -1 ) (Table 3). The rate of BA release was strongly affected by the flow rate of odorant-free air (Figure 4A). At 20 mL min -1 , the release rate reached a maximum value of about 13 times faster than the value obtained at 1 mL min -1 and rapid odorant release continued for about 0.5 min. Almost all the BA molecules were released from the aqueous OBP film within 1.5 min. When lower flow rates of the odorant-free air were used, values for the maximum release rate decreased, and the time-dependent changes in the release rate became gradual. The decay curve of the gas-phase BA concentration starting from their highest concentration (C g,max ) fitted well (R 2 > 0.99) to a single exponential equation (Equation 1). The observed off-rate constants calculated increased from 0.01 s -1 at 1 mL min -1 to 0.1 s -1 at 20 mL min -1 (Figure 4B). Although the initial rate of release was affected by the flow rate of odorant-free air, the change in the release curve for IBT was moderate (Figure 5) in comparison to the changes observed for BA. For example, as the flow rate of odorant-free air increased to 20 mL min -1 , the maximum IBT release rate increased to 7 times that of the value obtained at 1 mL min -1 ; however, a rapid decrease in the release rate was observed within 0.5 min of odorant-free air introduction, and the gas-phase odorant concentration decreased.

Cycling airflows to mimic nasal tidal flow

To study how fast rat-OBP3 binds and releases odor ligands and to test the reversibility of odorant binding, BA, the weakest-binding odorant was chosen as the model odorant because rapid release from the OBP-odorant complex was observed in previous experiments (Figures 3A and4A). BA (125 ppbv % 7 nM in air) was introduced into aqueous 0.5 mM BSA-or

Figure 5 Examples of the effect of airflow rate on odorant release for IBT. IBT (at the listed concentration in Table 1) and odorant-free air were sequentially introduced into the rat-OBP3 capillary (0.5 mM OBP3) in the same manner for BA in Figure 4. ). BA (at the concentration in Table 1) was introduced into the rat-OBP3 capillary (0.5 mM OBP3) at 1 mL min À1 until the capillary was fully saturated with the odorant. Different flow rates (1, 2, 5, 10, or 20 mL min À1 ) of odorant-free air were then introduced into the system. Changes in the observed off rates of BA OBP3 complex at different flow rates (B). The k obs was determined by fitting the release curves starting from the highest headspace concentration (C g,max ) to the first-order exponential decay model equation. For calculation, the averaged thickness of aqueous OBP film (1.28 lm), which was determined from the results of 20 independently performed coating experiments (the 5 odorants • the 4 concentrations), was used.

OBP3-coated capillaries at 20 mL min -1 for 45 s. Subsequently, 15 s of odorant-free air was followed by 15 s of BA in air and the cycle repeated 3 times (each 15 s). Finally, odorant-free air was introduced for 75 s (Figure 6A,B). In the BA trace from the BSA-coated capillary, rapid increases and decreases in the gas-phase concentration were observed as the flow changed in each cycle (Figure 6A). Full saturation of the rat-OBP3 capillary (0.5 mM) with BA was obtained at about 40 s (Figure 6B). After replacing the BA gas with odorant-free air, a gradual decrease in the gas-phase BA concentration by about 4.5 nM was observed. When the second BA flow was introduced, a decline in the gas-phase BA concentration continued, ultimately reaching about 2.5 nM. The OBP3-film became saturated again and the gas-phase BA concentration started to increase. When odorant-free air was reintroduced, the gas-phase BA concentration increased to about 4.8 nM. Increases and decreases in BA gas-phase concentrations repeatedly occurred during subsequent cycles. When the final volume of odorant-free air (75 s) was introduced, the gas-phase concentration of BA reached approximately 4.5 nM then decreased gradually and approached the base line.

Competitive binding

To investigate competitive odorant uptake and release by rat-OBP3, 2 odorants were first introduced into the capillary sequentially. IBMP and IBT (at the concentrations in Table 1) were chosen because these 2 odorants have different binding affinities for rat-OBP3 (medium and high, respectively; Table 1). Figure 7A shows the gas-phase IBMP trace when IBMP and odorant-free air were sequentially introduced into the OBP3 capillary (0.75 mM) at 3 mL min -1 over three 5 min cycles. Odorant uptake and release by OBP3 occurred on a regular, periodic basis which followed the cycle of IBMP and odorant-free air introduction, although with a time lag. Release of IBMP during the 5 min cycle with clean air was not quantitative as the time for the OBP to become fully loaded in the second and third cycles was shorter, than the first cycle. Figure 7B shows the results when the experiment was repeated but with IBT in place of the clean airflow. IBT has a lower K d (0.067 • 10 -6 M) than IBMP and should bind more strongly to OBP. The competitive effect can be clearly seen at 6 min on the trace in Figure 7B where IBMP is displaced from the OBP when IBT is introduced into the gas phase. A similar but smaller effect is seen in cycles 2 and 3 (16 and 26 min).

There is an effect on IBMP uptake in cycles 2 and 3 presumably because IBT is occupying the OBP-binding sites and IBMP can only partially displace some of the IBT molecules. In cycle 2 of the IBT, the OBP becomes fully loaded with IBT in a shorter time than in cycle 1, showing that limited release/displacement occurred in the cycle time between 11 and 16 min.

Figure 7C shows the situation when IBMP and IBT are introduced simultaneously. Traces a-e show how the concentration of IBT affects the release of IBMP with time. IBMP concentration was held at 190 ppbv (%8.4 nM), whereas IBT levels were 0, 250, 500, 1000, or 2500 ppbv (0, 11, 22, 45, or 112 nM, respectively). Rat-OBP3 concentration was 0.75 mM and total flow rate was 6 mL min -1 . In the absence of IBT, the aqueous OBP3 layer took about 2.7 min to become saturated with IBMP (Figure 7C-e); however, in the presence of IBT, the amount of IBMP uptake became smaller. With the same concentration of IBT, the aqueous OBP3 layer was saturated within 1.4 min and the uptake amount of IBMP was about half of the original amount. At a low concentration of IBT (250 ppbv % 11 nM), a steady release rate was observed (Figure 7C-d); whereas at higher concentrations of IBT (500-2500 ppbv), the IBMP peak shape became sharper as the IBT concentration increased (Figure 7C-a to c). The decay curve of the gas-phase IBMP concentration starting from their highest concentration fitted well to a single exponential equation (Equation 1; R 2 > 0.97), and the values were in the range from 4 to 15 min -1 . Corresponding half-life values of IBMP-OBP3 complex were between 3 and 10 s.

Figure 6 BA traces when introduced in cycles into a BSA capillary (A) or rat-OBP3 capillary (B) to mimic the nasal tidal flow and to study the uptake and release kinetics of odorant binding to OBP under physiologically relevant gas flow conditions. BA gas (7 nM % 160 ppbv) was introduced at 20 mL min À1 into the protein-coated capillaries (0.5 mM BSA or OBP3) from 0 to 0.75 min (45 s). Odorant-free air and BA were introduced in turn into the capillary at the same flow rate 3 times, each for 0.25 min (15 s). Finally, odorant-free air was introduced into the system for 1.25 min (75 s).

Discussion

The DyBOBS system measures odorant binding to OBP indirectly that is, by monitoring the change in odorant concentration in the outflow of the system (Figure 1). Previous work [START_REF] Yabuki | DyBOBS: a dynamic biomimetic assay for odorant-binding to odor-binding protein[END_REF]) has established the validity of this indirect approach through a series of control experiments, which studied potential confounding factors. The results showed that there was no significant binding to components of the DyBOBS system (e.g., the capillary itself) and that nonspecific binding to proteins like BSA was insignificant. Aqueous solubility of the odorants is known (Table 1) and this contribution can be calculated (see earlier discussion in Odorant uptake by OBP).

The purpose of the first experiments was to investigate the uptake and release behavior of 5 odorants under simulated OE conditions. A comparison of stoichiometry values obtained by ITC and DyBOBS shows good agreement (Tables 1 and2), with only the values for MP (ITC 0.81; DyBOBS 1.12) showing disparity. Given the discussion in previous sections about the high solubility of MP in water and the fact that the ITC results were corrected for dissolution of odorants in water, this is not really surprising. The other key outcome of the stoichiometry data is that with near 1:1 binding, the potential concentration factor for odorants can be up to 50 000 times (based on 1 mM OBP and an odorant gas phase concentration of 20 nM). Another outcome is to estimate the odorant flux in the system. At 1 mL min -1 flow and a concentration of 20 nM, about 20 pmol of odorant min -1 were delivered and taken up by the OBP layer as no odorants exited the capillary and were detected by the APCI-MS during this time. This suggests that the speed of odorant mass transfer from the gas to the liquid phase in the model system was faster than the rate of odorant delivery in the gas phase. Assuming the probability for an odorant to contact the OR can be estimated as the concentration of the odorant in the OE multiplied by the residence time of the odorant, the concentrating effect could potentially increase the chance for odorants to contact the OR. [START_REF] Firestein | The relation between stimulus and response in olfactory receptor-cells of the tiger salamander[END_REF] have reported that the ORs are not only responsive to the odorant concentration, but that they also sense the accumulated effects of the stimulus over time. In such a situation, OBPs could potentially enhance the output signal from the receptor cells. Pevsner et al. (1990) studied the odorant release kinetics of bovine OBP utilizing the infinite dilution technique for blocking the reassociation of dissociated odorants and bovine OBP. They reported that the dissociation of IBMP was very slow with negligible dissociation after 1 h. In the present study, the dissociation of MP, IBMP, IBT, and TMT were slow in comparison to BA, but the percentage of the released odorants were between 10% and 36% over A and B). IBMP (at the concentration in Table 1) was introduced into the rat-OBP3 capillary (0.75 mM) at 3 mL min À1 . After the OBP3 capillary was saturated with odorant, odorless air (A) or IBT at the concentration in Table 1 ( 5 min of odorant-free air introduction. It is likely, in DyBOBS, that the release occurs in much shorter time periods under the conditions where the reassociation of IBMP and rat-OBP3 are blocked.

To study the dynamic odorant binding to OBPs, model systems need to take into account the OE airflow profile in vivo. [START_REF] Keyhani | A numerical model of nasal odorant transport for the analysis of human olfaction[END_REF] have employed an anatomically correct 3D finite model, and their computational airflow simulations have shown that the average olfactory air speed was about 0.90 m s -1 for resting breathing. [START_REF] Ishikawa | Flow mechanisms in the human olfactory groove numerical simulation of nasal physiological respiration during inspiration, expiration, and sniffing[END_REF] recently investigated human nasal airflows using a CFD method and compared the inspiratory phase, expiratory phase, and sniffing flow patterns at different nasal locations. They reported that the velocity in the region of the OE during normal respiration was about 0.4 m s -1 . The linear velocities in the DyBOBS system were between 0.08 m s -1 (a flow rate of 1 mL min -1 [Reynolds number 3]) and 1.53 m s -1 (20 mL min -1 [Reynolds number 51]) to fully encompass the average olfactory air speed found by Keyhani et al and Ishikawa et al (Table 3).

In our model system, the residence time and rate of odorant release were strongly dependent on the odorant affinities for the protein and the amount of OBP3 (Figure 3F-J). When odorant-free air was introduced at a flow rate of 1-20 mL min -1 (a velocity of 0.08-1.53 m s -1 ) into the system after the aqueous OBP3 layer was fully saturated with BA, the release of BA, a weakly binding odor ligand, was greatly affected by the airflow rate. Under high flow conditions, odorant release was accelerated (Figure 4). The dramatic changes in release can be explained by reference to basic chromatography principles. Simply speaking, at high flow rates, a molecule that is released into the gas phase is swept down the column and has fewer chances of rebinding with OBP in the liquid phase, so exits the capillary faster. At a flow rate of 20 mL min -1 , the theoretical evacuation time of the capillary is calculated to be 70 ms (Table 3). Therefore, the evacuation rate constant, k ms should be greater than the time needed for achieving equilibrium between the gas and liquid phases (k v and k c ), meaning that the observed time-dependent changes in gas-phase odorant concentration directly relates to the change in free odorant concentration in the liquid phase. The results suggest that the gas flow rate (velocity) significantly affects the odorant residence time in the OE and that high airflow rates may contribute to the clearance of odorants so that OBPs can readily bind air-borne odorants within breathing airstreams.

To test how fast OBPs bind and release odorants, BA and odorant-free air were alternately introduced into the OBP3coated capillary at short time intervals (Figure 6). When odorant-free air was introduced into the system after the aqueous rat-OBP3 layer was first saturated with BA, an initial decrease in the gas-phase concentration was observed (Figure 6B). As shown in the BSA data (Figure 6A), the gasphase odorant took 10 s to dissipate once the syringe pump controlling introduction of the gaseous BA was turned off and the syringe pump controlling introduction of the odorant-free air was turned on. This is because a gas-tight syringe that works by a pressure-driven mechanism experiences lag time before the syringe actually stops or starts delivering either the gas-phase odorant or the clean odorant-free air into the OBP3 capillary. After an initial drop, a small peak can be seen in gas-phase odorant concentration (Figure 6B), indicating that there may have actually been a release of odorant by the OBP, and this was masked by the excess odorant overflowing from the gas-tight syringe containing the BA solution. When odorant-free air was introduced into the system, in which the aqueous rat-OBP3 film was not saturated with BA, as the second or the third introduction, small peaks due to the overflow of the odorant, followed by an increase in the gas-phase odorant concentration, were observed. The gas-phase BA concentration started to increase prior to the introduction of odorant-free air in all cases after the initial BA injection, indicating the OBP3-film became saturated again. It is unclear if partitioning between the 2 phases at the OE occurs in vivo as often as in the model system that utilized a relatively long (100 mm) but narrow capillary tubing (internal volume ; 22 lL). Therefore, although complete odorant release was not observed in the 15-s intervals used in this study (Figure 6A,B), it seems possible that odorants with binding affinities for rat-OBP3 much weaker than BA are released at normal breath cycles, which occur at 4-5 s for humans [START_REF] Keyhani | Numerical simulation of airflow in the human nasal cavity[END_REF]) and around 0.4 s for rats [START_REF] Walker | Breath timing, volume and drive to breathe in conscious rats: comparative aspects[END_REF], to prepare for the next odor stimulus.

To investigate uptake and release properties in the presence of a competitive binder, IBMP and IBT, which have different affinities for rat-OBP3 (see Table 1), were introduced sequentially into the OBP capillary (Figure 7B). Whereas continuous IBMP uptake and release occurred repeatedly in the absence of IBT (Figure 7A), which is a tight-binding odor ligand, odorant uptake for IBMP was limited in the presence of IBT. This result suggests that when a tight-binding odor ligand is introduced, displacement occurs easily; conversely, when OBPs bind to a strong-binding odor ligand, uptake of a weak-binding odor ligand is limited. When IBMP and IBT were introduced simultaneously into the rat-OBP3 capillary, the IBMP uptake amount was altered (Figure 7C). Moreover, the residence time of IBMP became shorter, and the rate of IBMP release rate became faster. The release of IBMP from aqueous OBP3 film occurred within very short time periods (3-10 s). The half-life value for IBMP-OBP3 complex was as short as 3 s when 2500 ppbv (112 nM) concentration of IBT was introduced; the value is 2 orders of magnitude faster than the literature (Pevsner et al. 1990) has previously suggested. These results indicate that multiple binding and release from OBPs occur in vivo, where diverse odorants exist, and occur simultaneously with release rate constants (k off ) that are actually relevant to detecting odors. As rat-OBP3 exhibits typical OBP characteristics [START_REF] Lo ¨bel | Odorants of different chemical classes interact with distinct odorant binding protein subtypes[END_REF][START_REF] Lo ¨bel | Identification of a third rat odorant-binding protein (OBP3)[END_REF], it is likely that vertebrate OBPs generally display similar results to those shown in this study.

Conclusion

What is currently missing from our understanding of olfactory perception is a detailed knowledge of the mass transfer mechanisms that occur when odorants in the gas phase pass over the OE and odorants transfer from the gas phase to the liquid phase and finally to the ORs. The observations presented in this paper provide fundamental information on the first peri-receptor events in olfaction and contributes to the current knowledge concerning the role of OBPs. The investigation could be further continued by including a secondary phase to study the transfer of odorants from OBPs to ORs. The lack of a functional stable human OBP is a current limitation. The effects of various OBP subtypes also need to be studied. The dynamic release and displacement of odor ligands and the mass transfer of dissociated odorants between the gas and liquid phases within the time scale relevant to odor detection suggest that dissociated odorants could be involved in peripheral event(s) in olfaction. Because rat-OBP3 has been shown to display typical OBP characteristics, the data indicate that vertebrate OBPs may play a role in increasing the mucus-phase odorant concentration, which could potentially enhance the frequency and duration of odorant access to the olfactory neurons.

The transport of odorants through the DyBOBS system is clearly mediated by the presence of OBP: an apparent retardation in odorant release is seen quite clearly (Figure 2). The degree to which each odorant is affected differs, and this therefore needs to be explained in terms of the kinetics of transfer from the gas phase, how these kinetics are affected by OBP3 in the solution phase, and the intrinsic binding affinity of OBP3 for these odorants. The experiments provide access to 2 parameters: A. The intrinsic solution-based affinity of OBP3 for a particular odorant, as determined by isothermal titration calorimetry and B. The time-dependent concentration of the odorant in the gas phase as it emerges from the DyBOBS system.

Our ligands can be broadly categorized into 4 classes:

1. Hydrophilic with a high affinity (low K d ) for OBP3.

2. Hydrophobic with a high affinity (low K d ) for OBP3.

3. Hydrophilic with a low affinity (high K d ) for OBP3. 4. Hydrophobic with a low affinity (high K d ) for OBP3.

Each of these will show a distinct behavior in the DyBOBS system in the presence of OBP3. In the absence of OBP3, the odorant partition between the gas and the liquid phase will depend upon the rate of condensation of the odorant into the liquid phase, the rate of volatilization out of the liquid phase, and the flow rate of carrier gas through the system. In the presence of OBP3 there are further processes. We assume that OBP3 cannot directly obtain odorants from the gas phase and therefore interacts only with those in the solution phase. Hence, if a hydrophilic ligand that binds tightly to OBP3 is introduced into DyBOBS, then there is a strong effect of retardation, and hence a slower rate of release is observed. If the ligand is hydrophobic, a rate of release is still seen, but its magnitude is much less as there will be less soluble ligand available. If a ligand does not bind tightly to OBP3, then the rate of release will more closely depend on the off-rate of the ligand/protein complex.

Figure 1

 1 Figure 1 Schematic of the DyBOBS system (Yabuki et al. 2010).

Figure 3

 3 Figure3Time-dependent curves for the release amount (pmol) of the5 selected odorants from 0.5 mM aqueous rat-OBP3 film (black triangles) and from 1.25 mM aqueous rat-OBP3 film (black circles) (A-E). Time-dependent curves for the percentage of the 5 selected odorants released from 0.5 mM aqueous rat-OBP3 film (open triangles) and from 1.25 mM aqueous rat-OBP3 film (open circles) (F-J). Each odorant (at the concentration in Table1) was introduced at 1 mL min À1 into the capillary.

Figure 4

 4 Figure4Examples of the effect of airflow rate on odorant release for BA (A). BA (at the concentration in Table1) was introduced into the rat-OBP3 capillary (0.5 mM OBP3) at 1 mL min À1 until the capillary was fully saturated with the odorant. Different flow rates (1, 2, 5, 10, or 20 mL min À1 ) of odorant-free air were then introduced into the system. Changes in the observed off rates of BA OBP3 complex at different flow rates (B). The k obs was determined by fitting the release curves starting from the highest headspace concentration (C g,max ) to the first-order exponential decay model equation.

Figure 7

 7 Figure 7 Differences in IBMP traces (m/z 167) in the absence and presence of IBT (A and B). IBMP (at the concentration in Table1) was introduced into the rat-OBP3 capillary (0.75 mM) at 3 mL min À1 . After the OBP3 capillary was saturated with odorant, odorless air (A) or IBT at the concentration in Table1 (B) was introduced at the same flow rate and for the same duration. A pair of gases was presented three times, one after the other. Differences in IBMP traces with different concentrations of IBT introduced into the capillary simultaneously (C). IBMP (190 ppbv % 8.4 nM) and IBT (0-2500 ppbv air) were introduced into the rat-OBP3 capillary (0.75 mM) at 3 mL min À1 . The chromatogram a-e show IBMP traces in the presence of decreasing concentrations of IBT (a, IBT 2 500 ppbv; b, 1 000 ppbv; c, 500 ppbv; d, 250

  Figure 7 Differences in IBMP traces (m/z 167) in the absence and presence of IBT(A and B). IBMP (at the concentration in Table1) was introduced into the rat-OBP3 capillary (0.75 mM) at 3 mL min À1 . After the OBP3 capillary was saturated with odorant, odorless air (A) or IBT at the concentration in Table1 (B) was introduced at the same flow rate and for the same duration. A pair of gases was presented three times, one after the other. Differences in IBMP traces with different concentrations of IBT introduced into the capillary simultaneously (C). IBMP (190 ppbv % 8.4 nM) and IBT (0-2500 ppbv air) were introduced into the rat-OBP3 capillary (0.75 mM) at 3 mL min À1 . The chromatogram a-e show IBMP traces in the presence of decreasing concentrations of IBT (a, IBT 2 500 ppbv; b, 1 000 ppbv; c, 500 ppbv; d, 250 ppbv and e, 0 ppbv). The half-life values of IBMP-OBP3 complex were calculated by fitting the release curves starting from the highest headspace concentration to the first-order exponential decay model equation (D).

Table 1

 1 Physicochemical and biophysical properties of the 5 odorants used in this study

	Odorant	Molecular mass	Air-water partition	Gas phase	Odorant water	ITC stoichiometry (n) and
			coefficient a	[odorant] a (nM)	solubility (mM)	dissociation constant (K d )
						n	K d • 10 À6 (M)
	BA	106	1.4 • 10 À3	28.4	51	0.92	687
	MP	94	7.1 • 10 À5	17.6	3548	0.81	1.7
	IBMP	166	1.5 • 10 À3	16.7	126	0.96	0.47
	IBT	141	1.8 • 10 À3	22.3	4.6	0.89	0.067
	TMT	127	4.8 • 10 À4	22.3	9.1	0.91	0.026

a Determined experimentally using APCI-MS; n = 4 typical variation Ô 5%. The air-water partition coefficient values are the means of 4 replicate measurements, typical variation Ô 5%.

Table 2

 2 Stoichiometry of odorant binding to rat-OBP3 at different OBP concentrations in the DyBOBS system

	OBP	BA	MP	IBMP	IBT	TMT
	concentration
	(mM)
	0.5	1.06	1.35	0.97	0.76	1.07
	0.75	0.78	1.08	0.97	0.94	0.86
	1	0.86	1.06	0.96	0.77	0.93
	1.25	0.80	1.00	0.92	0.82	0.82
	Mean values	0.87	1.12	0.96	0.83	0.92
	Values are the mean of 5 replicates.

Table 3

 3 Hydrodynamic parameters of odorant-free air used for BA and IBT dissociation kinetics study and the theoretical evacuation time of the capillary

	Flow	Linear	Reynolds	Theoretical
	rate	velocity	number	evacuation
	(mL/min)	(cm/s)	(Re dimensionless)	time (ms)
	1	8	3	1 310
	2	15	5	655
	5	38	13	262
	10	76	26	131
	20	153	51	66

M. Yabuki et al. by Thierry Thomas-Danguin on September 14, 2011 chemse.oxfordjournals.org Downloaded from

by Thierry Thomas-Danguin on September 14, 2011 chemse.oxfordjournals.org Downloaded from

M. Yabuki et al. by Thierry Thomas-Danguin on September 14, 2011 chemse.oxfordjournals.org Downloaded from

chemse.oxfordjournals.orgDownloaded from

M. Yabuki et al. by Thierry Thomas-Danguin on September 14, 2011 chemse.oxfordjournals.org Downloaded from

Acknowledgements

M.Y. acknowledges Kao Corporation for sabbatical leave and financial support to carry out this project. We thank Heinz Breer for the gift of the rat-OBP3 cells and Katherine L. Portman, who contributed expertise in recombinant protein production. We also thank Robert S. T. Linforth and Guy A. Channell for their help in developing the OBP-binding assay.


Victor Felea

Violeta Felea
email: violeta.felea@femto-st.fr

Algorithm for Term Linearizations of Aggregate Queries with Comparisons

We consider the problem of rewriting queries based exclusively on views. Both queries and views can contain aggregate functions and include arithmetic comparisons. To study the equivalence of a query with its rewriting query, the so called "linearizations of a query" need to be computed. To find the linearizations of a query, the linearizations of terms from the query need to be generated. We propose an algorithm to find these term linearizations and give a bound for its time-complexity.

Introduction

The problem of rewriting queries using views (RQV ) is expressed, informally, as follows: given Q a query over a database schema, and V a set of view definitions, is it possible to answer the query Q using only the answers to the views from V? One of the application fields of RQV concerns extracting and gathering information on the environment, based on sensor networks. Small inexpensive devices, namely sensors, communicate information to collecting points, called sinks or base stations. In this context, of information collection out of several sources (stored in views), located on sensor nodes, expressing queries using views. In [START_REF] Madden | Supporting aggregate queries over ad-hoc wireless sensor networks[END_REF], the authors apply the notions of query interface for data integration to sensor networks.

In case of finding a query Q , corresponding to a given query Q, and expressed by the views from V, such that Q is equivalent to Q , the problem of (RQV ) for the query Q has a solution. This query Q is called a rewriting query of Q.

The equivalence problem of two aggregate queries with comparisons was investigated in [START_REF] Cohen | Deciding equivalences among conjunctive aggregate queries[END_REF], [START_REF] Afrati | Rewriting queries using views in the presence of arithmetic comparisons[END_REF], [START_REF] Cohen | Containment of aggregate queries[END_REF], [START_REF] Grumbach | On the equivalence and rewriting of aggregate queries[END_REF]. The equivalence problem of the two queries is achieved using the equivalence of their reduced queries. A reduced query associated to a query Q uses the so-called "linearizations" (or complete ordering) of the set of all terms from Q.

In [START_REF] Cohen | Rewriting aggregate queries using views[END_REF], query equivalence between view-based query and schema query, using linearizations, is proven; no linearization computation has been given. This is the main aim of this work: to propose an algorithm to compute linearizations. By our best knowledge, an algorithm to obtain all linearizations of terms from a query has not been proposed in the literature.

In the paper, we consider the problem of generating all linearizations corresponding to a query that uses arithmetic comparisons and aggregate functions; we consider a motivated example (see section 2) and give an algorithm that computes these linearizations, and its time complexity in section 3. We finally conclude.

Motivating Example

Let us give an example about a schema regarding sensor networks used in statistical applications concerning the weather. The network nodes are organized in clusters [START_REF] Heinzelman | Energy-efficient Communication Protocol for Wireless Microsensor Networks[END_REF], one common architecture used in sensor networks.

Example 1. We assume there exist sensors for the following type of data: humidity, mist and temperature. One sensor can retrieve unique or multiple environmental data, e.g. temperature and humidity, or only temperature values. Sensors are placed in several locations, and have an identifier, a type, and they are grouped by regions. The type of a sensor characterizes the set of data types that it senses. A location is identified by two coordinates lat, long, where lat is the latitude and long is the longitude. A region has an identifier and a unique name. Let us consider the relational schema S consisting of {REG, POINT, SENSOR, DATA}, where REG represents regions and has idReg as region identifier, and regName as region name; POINT represents the locations from the regions, and uses the idReg attribute as the region identifier, and the lat, long attributes as the coordinates of a location from the region identified by idReg; SENSOR represents information about sensors with idS the sensor identifier, lat, long -the sensor coordinates, typeS its type related to the sensing capacity (e.g. typeS equals 1 for temperature and humidity, 2 for temperature and mist, 3 for humidity and mist, and so on), and chS designs if the sensor is a cluster head (its value equals 1 or 2). We assume here that the type of the sensors that can sense temperature equals either 1 or 2; DATA represents the values registered by sensors, and has the following attributes: idS -the sensor identifier, year, month, day, period -the date of the sensed information, the daily frequency of sensed data, expressed in seconds, and temp, humid, mist -the temperature, humidity, and mist values, respectively.

Let us consider the following views:

V 1 : Compute all pairs of the form (idReg, regName), where idReg is the region identifier, and regName is the name of the region identified by idReg, such that in the region idReg at least a cluster head exists. V 2 : Compute the maximum temperature for each region, each network location, and for every year.

Let us consider the following queries: To obtain a condition associated to Q 1 , we replace the variables y 1 , t 2 by c 1 , 1, respectively. Since y 2 = x, z 2 = y 3 , z 3 = y 4 , and z 5 = z 1 , the query Q 1 is expressed as the following condition:

Q 1 :
Q 1 : h(x, max(t)) ← D(z 1 , z 6 , z 7 , z 8 , z 9 , t, z 11 , z 12 ) ∧ R(x, c 1 ) ∧ S(z 1 , y 3 , y 4 , t 1 , 1) ∧ P (x, y 3 , y 4 ) ∧ C, where C ≡ ((t 1 = 1) ∨ (t 1 = 2)) ∧ (z 6 ≥ c 2 ) ∧ (z 6 ≤ c 3 ).
The query Q 2 , and the views V 1 , V 2 defined in Example 1, have similar expressions.

Term Linearizations of Aggregate Queries

In this section we specify some notions about the term linearizations and give an algorithm to compute these linearizations constructed by the terms from the conditions contained in the aggregate query. For other notions, see [START_REF] Cohen | Rewriting aggregate queries using views[END_REF].

Two aggregate queries Q 1 and Q 2 having identical heads are said equivalent, if their answers are equal, i.e. Q 1 (D) = Q 2 (D), for any database D defined on Dom. Let f i be the body of Q i . Since each f i is a disjunction of relational atoms and of an expression constructed from comparison atoms using the conjunction and the disjunction operators, it can contain comparisons of terms. The comparisons of an expression f i induce, in general, a partial order among the constants and variables of the query. To study the equivalence of two queries, we need to consider linear orderings such that a given partial ordering of the set of terms is compatible with a set of linear orderings of the same set of terms.

The set of all terms from a query can be considered as a set of groups, where all attributes of a group correspond to the same value domain. Let C be a set of comparison atoms, and t 1 < t 2 be a comparison atom. We say that C implies t 1 < t 2 , denoted C |= t 1 < t 2 , if for each substitution τ , the statement (τδ= true for each δ ∈ C) implies τt 1 < τt 2 . For a comparison atom having the form t 1 = t 2 or t 1 > t 2 the implication relation of a comparison atom from a set of comparison atoms is similar. Let T be a set of terms (variables or constants) that are semantically equivalent. A linearization of T is a set of comparisons L having the terms in T such that for any two different elements t 1 , t 2 from T , exactly one of the following comparisons: t 1 < t 2 , t 2 < t 1 , or t 1 = t 2 is implied by L. If T has t 1 , . . . , t p as elements, let (t 1 , . . . , t p ) be a permutation of the elements t j , 1 ≤ j ≤ p. Then we can represent a linearization L of T as t 1 ρ 1 t 2 ρ 2 . . . t p-1 ρ p-1 t p , where the operators ρ i are '<' or '='. We say that a substitution τ from {t 1 , . . . , t p } into Dom, that preserves constants, satisfies the linearization L, denoted τ (L) = true, if for each i, 1 ≤ i < p, τt i = τt i+1 , when ρ i is '=', and τt i < τt i+1 , when ρ i is '<'. We denote by t 1 = t 2 = . . . = t h , the set of comparisons t i = t i+1 contained in L, for any i, 1 ≤ i < h. Intuitively, a linearization is a list of different variables and constants such that between two elements of the list there exists one of the '=' or '<' operators. In this way, a linearization produces a partition of all terms into equivalence classes; an equivalence class contains all terms t 1 , . . . , t h such that t 1 = t 2 = . . . = t h .

We say that a set of comparisons C is satisfiable, if there exists a substitution τ from terms into Dom such that τ satisfies all comparisons from C. We say that τ satisfies

C or τ (C) = true, if τt 1 < τt 2 if C ≡ t 1 < t 2 , and τt 1 = τt 2 if C ≡ t 1 = t 2 .
The value of τ (C) is extended naturally to expressions C obtained from basic comparisons using the conjunction and disjunction operators. We say that a linearization L of T , and a set of comparisons C are compatible, if L ∪ C is satisfiable.

In the following we give a method to obtain all linearizations of T , compatible with C. Let C be the conjunction of the comparisons t i σ i t i , i.e. C = (t 1 σ 1 t 1 ) ∧ . . . ∧ (t h σ h t h ), where the operators σ i are relational operators. Let C be the formula obtained from C, by replacing (t i ≤ t j ) with (t i < t j ) ∨ (t i = t j ), and (t i ≥ t j ) with (t j < t i ) ∨ (t i = t j ). Using for the expression C , the distributivity of the conjunction versus the disjunction, we obtain a formula C having the form: [START_REF] Afrati | Rewriting queries using views in the presence of arithmetic comparisons[END_REF], where E j is a conjunction of comparisons of the form t i < t j or t i = t j . In this disjunction, we take only consistent conjunctions by eliminating those conjunctions that are inconsistent, i.e. which contain at least two comparisons of the form: t 1 < t 2 and t 1 = t 2 , or two comparisons of the form t 1 < t 2 and t 2 < t 1 . Let E be an arbitrary conjunction from C . Associated to E, we construct a forest, denoted G E . Firstly, for the set of all comparisons S E of the form t i = t j from E, we take the transitive and symmetrical closure of S E . This closure produces a set of equivalence classes Cl 1 , . . . , Cl q . Let us denote by T erm1 = {t 1 , . . . , t p }, the remainder of the variables and the constants from E. The forest G E associated to E is defined as follows: its nodes are labeled with Cl j , 1 ≤ j ≤ q and t i , 1 ≤ i ≤ p. Let V ar(C) be the set of variables from C and Const(C) the set of constants from C.

C = E 1 ∨E 2 ∨. . .∨E p
The edge set N of the forest G E is specified as follows:

-

= . . . = t s }. Example 3. Let C ≡ (x 1 ≤ x 2 ) ∧ (x 2 > x 3 ) ∧ (y 1 ≤ x 2 )
. The formula corresponding to C has the form:

C = [(x 1 < x 2 ) ∨ ((x 1 = x 2 )] ∧ (x 3 < x 2 ) ∧ [(y 1 < x 2 ) ∨ (y 1 = x 2 )].
The expression C has the form:

C = E 1 ∨ E 2 ∨ E 3 ∨ E 4
, where

E 1 = (x 1 < x 2 ) ∧ (x 3 < x 2 ) ∧ (y 1 < x 2 ), E 2 = (x 1 < x 2 ) ∧ (x 3 < x 2 ) ∧ (y 1 = x 2 ), E 3 = (x 1 = x 2 ) ∧ (x 3 < x 2 ) ∧ (y 1 < x 2 ), E 4 = (x 1 = x 2 ) ∧ (x 3 < x 2 ) ∧ (y 1 = x 2 ).
The forests associated to each of the four expressions are given in the following figure, where nodes are labeled β i .

A Method to Obtain the Linearizations of C

In this subsection, we specify a method to obtain all linearizations of V ar(C) ∪ Const(C) compatible with C and corresponding to a forest G E associated to an expression E from C . The construction of this set of linearizations will be done recursively in function of the number of edges from G E .

-The base step: Let G E having zero edges, and β 1 , . . . , β p its nodes. Let i 1 , . . . , i p be a permutation of the indexes 1, 2, . . . , p. Let us denote by M L GE the set of linearizations defined by G E . For this base step, we take:

M L GE = {β i1 σ 1 β i2 σ 2 . . . β ip-1 σ p-1 β ip |(i 1 , . . . , i p ) is a permutation of {1, 2, . . . , p}, σ i ∈ { < , = }}.
We make the following convention:

{t 1 = t 2 = . . . = t s } = {t 1 = t 2 = . . . = t r } becomes: {t 1 =t 2 =. . .=t s =t 1 =t 2 =. . .=t r }.
-The inductive step: Assume that we have computed the set of linearizations corresponding to any forest G having at most n edges, where n is a natural number. Let G be a forest having n+1 edges. Let t 0 be an initial node from G, and γ 1 , . . . , γ k the immediate successors of t 0 . Let G be the forest obtained from G by deleting the edges (t 0 , γ j ), 1 ≤ j ≤ k, and deleting the node t 0 . Since G has at most n edges, by induction we have computed M L G . Using the linearizations of G , we compute the linearizations for G. Let L ≡ s 1 < s 2 < . . . < s m be an element of M L G , where m is the number of the nodes of G . An element s i contains a set of terms from V ar(C) ∪ Const(C). The label γ j belongs to a unique s i , for each j, 1 ≤ j ≤ k (γ j ⊆ s i ). Let us denote by ind(j) this natural number i. Let i 0 be the minimum of ind(j), for each j, 1 ≤ j ≤ k. Now, we define a set of linearizations for G corresponding to L by inserting t 0 in L before s i0 . Let us denote by Insert(t 0 , L, l) the linearizations obtained from L by inserting t 0 between the positions l and l + 1. There are two linearizations in Insert(t 0 , L, l) in case l ≥ 1, denoted L 1 , L 2 , where L 1 ≡ s 1 < s 2 < . . . < s l < t 0 < s l+1 < . . . < s m , and L 2 ≡ s 1 < s 2 < . . . < {s l = t 0 } < s l+1 < . . . < s m . If l = 0 the insertion takes place before s 1 and Insert(t 0 , L, l) consists of one sequence, namely L 1 , where L 1 ≡ t 0 < s 1 < s 2 < . . . < s m . For the linearization L and the node t 0 , we consider the union of the sets Insert(t 0 , L, l), for each l, 0 ≤ l < i 0 . Let us denote this set by M(t 0 , L). Now, we define the set of linearizations corresponding to G as follows:

M L G = {L |(∃L)(L ∈ M L G ) such that L ∈ M(t 0 , L)}. Let E j be an expression from relation (1), 1 ≤ j ≤ p. Let G Ej be the forest corresponding to E j . Let M L GE j
be the set of linearizations computed for the forest G Ej . Let M(C) be the union of the M L GE j sets, for each j, 1 ≤ j ≤ p. Regarding these notations, we have the following results. Lemma 1. Let E be a consistent conjunction of comparisons of the form t i < t j or t i = t j . Let L be a linearization compatible with E, and G E the forest associated to E. Then, we have L ∈ M L GE .

Proof. Using the induction on the number of the comparisons of the form '<' from E (this number is equal to the number of the edges from G E ).

Theorem 1. Let L be a linearization of V ar(C) ∪ Const(C) and M(C) the set of linearizations computed for C as above. Then, we have:

L is compatible with C iff L ∈ M(C).
Proof. Let L be a linearization from M(C). There exists an integer j,

1 ≤ j ≤ p such that L ∈ M L GE j
. The linearization L can be represented as Cl(t 1 ) < Cl(t 2 ) < . . . < Cl(t m ), where Cl(t i ) are equivalence classes corresponding to L, and t i is an element from that class. A class Cl(t i ) consists of a single variable, a single constant, or a set of terms {t 1 , . . . , t h }, h ≥ 2, and this set contains at most one constant. The union of the classes Cl(t i ) is V ar(C) ∪ Const(C). Let us define the substitution τ as follows: if Cl(t i ) = {t 1 , . . . , t h }, then τt j = τt l , 1 ≤ j < l ≤ h. The substitution τ is extended to classes: τCl(t j ) = τt j . For two classes, we take the values for τ such that if Cl(t i ) < Cl(t j ), then τt i < τt j . In this manner, we have τ (L) is true. Using the method to construct M L GE j , we obtain τ (E j ) is true, hence τ (C) is true. That means L ∪ C is satisfiable.

Conversely, let L be a linearization compatible with C. It results that there exists an integer j, 1 ≤ j ≤ p such that L is compatible with E j . Using Lemma 1, we obtain L ∈ M L GE j

, hence L ∈ M(C).

Using Theorem 1, we obtain an algorithm that computes the set of all linearizations for a conjunction of comparisons.

Algorithm to Compute Linearizations of M(C)

Firstly, let us denote by LinearizationsComp(G,L) an algorithm that computes the set L of all linearizations corresponding to the forest G. Let us consider some notations used in this algorithm. We denote by h the number of levels from G. The terminal nodes of G are considered on level 1. Let N j be the set of all nodes on level j, 1 ≤ j ≤ h. We denote by L j the set of all linearizations for nodes situated on the levels l in G, where l ≤ j. We use the notation M(γ, L) for a set of linearizations obtained by inserting the node γ into a linearization L, as specified in subsection 3.1. By L j,l we denote a set of linearizations of nodes from G, that is a subset of L j . The algorithm proceeds level by level, beginning with the first level.

Algorithm LinearizationsComp (input G, output L) compute h the number of levels from G for all j=1 to h do compute N j , the set of all nodes on level j endfor compute L 1 the set of linearizations for N 1 (see base step from Subsection 3.1) if h=1 then L = L 1 exit endif for all j=2 to h do

L j = ∅ let N j = {γ 1 , . . . , γ k } L j,0 = L j-1 for all l=1 to k do L j,l = ∅ let L j,l-1 = {L 1 , . . . , L p } for all s = 1 to p do compute M(γ l , L s ) (see Subsection 3.1) L j,l = L j,l ∪ M(γ l , L s ) endfor endfor L j = L j,h endfor L = L h
Secondly, we specify the computing of the linearizations corresponding to the expression C that has comparison atoms as base expressions, and is formed of base atoms using the conjunction or disjunction operators. The expression C is equivalent to a disjunction of conjunctions, i.e. E ≡ E 1 ∨ . . . ∨ E p . For each expression E j , we construct the forest G Ej , and call the algorithm Lineariza-tionsComp with the parameters G Ej and L j . The set of the linearizations for C, denoted M(C), is the union of all L j , i.e. M(C) = ∪ p j=1 L j . Example 4. Let us consider Example 2. Let C be the comparison expression from

Q 1 . Since z 6 ≥ c2 is equivalent to (z 6 > c2) ∨ (z 6 = c 2 ), and z 6 ≤ c 3 is equivalent to (z 6 < c 3 )∨(z 6 = c 3 ), the expression C is equivalent to C ≡ 3 i=1 [(t 1 = 1)∧E i ] 3 i=1 [(t 1 = 2)∧E i ], where E 1 ≡ (c 2 < z 6 )∧(z 6 < c 3 ), E 2 ≡ (c 2 < z 6 )∧(z 6 = c 3 ), E 3 ≡ (z 6 = c 2 ) ∧ (z 6 < c 3 ). The expression (z 6 = c 2 ) ∧ (z 6 = c 3
) is non satisfiable because all constants are considered different. Concerning the constants c 2 and c 3 , we assume c 2 < c 3 , otherwise the expression C is not satisfiable. As we specified in Section 3, we represent a linearization as a set of groups, where a group is a linearization of all terms corresponding to the same value domain. For the group {z 6 , c 2 , c 3 }, and the first conjunction from C , we obtain one linearization: c 2 < z 6 < c 3 . Hence, to the first conjunction of C , we have two groups denoted g 1 , g 2 , where g 1 ≡ (t 1 = 1), g 2 ≡ c 2 < z 6 < c 3 . We consider an order of linearizations as follows: L 1 for the first conjunction of C , L 2 for the fourth, L 3 for the second, L 4 for the fifth, L 5 for the third, and L 6 for the sixth. Thus, the linearizations L i have the following forms: L 1 ≡ (t 1 = 1, c 2 < z 6 < c 3 ), L 2 ≡ (t 1 = 2, c 2 < z 6 < c 3 ), L 3 ≡ (t 1 = 1, z 6 = c 3 ), L 4 ≡ (t 1 = 2, z 6 = c 3 ), L 5 ≡ (t 1 = 1, z 6 = c 2 ) and L 6 ≡ (t 1 = 2, z 6 = c 2 ).

Complexity Issues

Let us compute the time complexity of algorithm 1. Let G be a forest, with n nodes and p edges and h its number of levels (corresponding to the depth of the forest) with h ≤ p + 1. For every level j, 1 ≤ j ≤ h, let N j be the number of nodes on level j. We have h j=1 N j = n. The set L j from the algorithm gives all the linearizations obtained using nodes from levels 1 to j. The number of terms for each linearization from L j is length j = j k=1 N k . Let us denote by |L j | the cardinal of the L j set. We have |L 1 |=N 1 ! because there is no edge between the nodes on the first level. For the other levels, we have:

|L j+1 | ≤ N j+1 * length j * |L j |, 1 ≤ j ≤ h -1.
We

Conclusion

In the paper, we propose an algorithm to compute linearizations and evaluate its complexity. These are useful in the process of constructing and proving the query equivalence between query expressed on the database schema and its rewritings using views. Queries and views considered here contain aggregate functions and arithmetic comparisons. Future work will focus on the aspects concerning using linearizations in the problem of queries equivalence when queries and views contain negations.

  Let us consider the schema, queries, and views from Example 1. We denote the attributes idReg, regName from REG by x, y 1 , respectively, idReg, lat, long from POINT by y 2 , y 3 , y 4 , and idS, lat, long, typeS, chS from SENSOR by z 1 , z 2 , z 3 , t 1 , t 2 , and the attributes from the schema DATA by z 5 , z 6 , z 7 , z 8 , z 9 , t,z 11 , z 12 . To be short, we denote by D, R, S, P the relational symbols DATA, REG, SENSOR, POINT, respectively. Let c 1 ="NORTH", c 2 = 2003 and c 3 = 2010.

	Example 2.
	Find the maximum of temperature values for the "NORTH" region, between
	2003 and 2010, considering data sensed only by cluster head sensors.
	Q 2 : Find the maximum temperature corresponding to the "NORTH" region, on
	September 22nd, 2009.

  -Let Cl j , Cl h be two different classes. If there exist the terms t 1 , t 2 , where t 1 ∈ Cl j and t 2 ∈ Cl h such that t 1 < t 2 appears in E, then (Cl j , Cl h ) ∈ N .Since the labels associated to different nodes contain disjoint sets of terms, we identify the nodes with their labels. If a class Cl j consists of the elements t 1 , . . ., t s , we denote it as {t 1 , . . . , t s } or {t 1

Let t 1 and t 2 be variables or constants. If t 1 < t 2 appears in E, and t 1 and t 2 occur in T erm1, then (t 1 , t 2 ) ∈ N . -Let Cl j be a class and t 2 from T erm1. If there exists t ∈ Cl j such that t < t 2 occurs in E, then (Cl j , t 2 ) ∈ N . -Let t 1 be from T erm1, and Cl h a class. If there exists t ∈ Cl h such that t 1 < t occurs in E, then (t 1 , Cl h ) ∈ N .

  obtain |L h | ≤ N h * N h-1 * . . . * N 1 * (N h-1 + . . .+ N 1 ) * . . . * (N 2 + N 1 ) * N 1 !.The set of terms can be grouped in classes, a class contains all terms having the same value domain. If m is the maximum number of elements in these classes, then m is the number of the forest nodes in the given algorithm.