Laure Berti-Équille
email: berti@irisa.fr

TRACING DATA POLLUTION IN LARGE BUSINESS APPLICATIONS (Research-in-Progress)

In large business applications, various data processing activities can be done locally or outsourced, split or combined and the resulting data flows have to be exchanged, shared or integrated from multiple data processing units. There are indeed various alternative paths for data processing and data consolidation. But some data flows and data processing applications are most likely exposed to generating and propagating data errors; some of them are more critical too. Actually, we usually ignore the impact of data errors in large and complex business applications because : 1) it is often very difficult to systematically audit data, detect and trace data errors in such large applications, 2) we usually don't have the complete picture of all the data processing units involved in every data processing paths; they are viewed as black-boxes, and 3) we usually ignore the total cost of detecting and eliminating data anomalies and surprisingly we also ignore the cost of "doing nothing" to resolve them. In this paper, the objectives of our ongoing research are the following: to propose a probabilistic model reflecting data error propagation in large business applications, to determine the most critical or impacted data processing paths and their weak points or vulnerabilities in terms of data quality, to advocate adequate locations for data quality checkpoints, and to predict the cost of doing-nothing versus the cost of data cleaning activities.

INTRODUCTION

Estimation of the quality of information produced or exchanged by collaborative data processing applications is difficult because errors from multiple data sources and processing paths are combined in the final output data. In large and complex business applications, it is extremely difficult: i) to establish estimates of the quality of the data delivered or exchanged by composite applications collaborating with each others, ii) to offer convenient means of keeping track of the effects of data error propagation, iii) to predict the cost of control and corrective actions on erroneous data, and iv) to determine and recommend the "best" locations (i.e., with minimal cost) for data quality control and improvement activities. In this context, our initiative is to study the notion of "quality of data dependability" (QoD-dependability) defined as: the trustworthiness of a data processing unit (or application) which allows reliance to be justifiably placed on the data quality it delivers. As cost is a relevant issue for data quality control and improvement activities, the cost of ensuring QoD-dependability has to be kept low. When developing QoD-dependable applications (i.e., that ensure and preserve high or, at least, acceptable quality of the data they process and exchange), it is important to know the characteristics and properties (and weaknesses) of the means at one's disposal for data quality awareness. Moreover, in order to be able to set up and target data quality control and improvement activities where they are the most effective, it is important to know where data errors tend to propagate and have the worse consequences (on strategic decisions, for example). The motivation of this work directly comes from the works related to software dependability [START_REF] Hiller | EPIC: Profiling the Propagation and Effect of Data Errors in Software[END_REF][START_REF] Johansson | Error propagation profiling of operating systems[END_REF] and we apply the same concepts for tracing the propagation of data quality problems through data processing applications. We introduce the garbage-in garbage-out measure, noted GIGO and, based on it, we define a set of related measures that cumulatively provide an insight on the vulnerabilities of the applications related to data quality issues.

Customer Relationship Management (CRM) is a process used to learn more about customers' needs and behaviors in order to develop stronger relationships with them and to identify, acquire, foster and retain loyal and profitable customers. Web-based CRM uses several softwares and applications that enable Web-based customer interaction, Web site analytics, Enterprise Marketing Automation (EMA) (e.g., for the enterprise's electronic surveys, polls, questionnaires, and campaign management to understand customer preferences), and Sales Force Automation (SFA) (for helping executives and salespeople to correctly identify customers and execute sales methods). Call Center softwares or Help Desk softwares are also used for customer service (e.g., for automating emails, call logs, etc.). From a functional point-ofview, Figure 1 depicts a generic architecture of a large CRM application of an airline company consisting of 7 data processing units (S 1 , . . . , S 7 ), 15 input/output data flows (f 1 , . . . , f 14 , f DB ) exchanging information (e.g., flight reservation, reservation confirmation, e-ticket, etc.), the CRM database CRM DB, and Data Quality Control policies (DQCs). DQCs (e.g., DQC[S 1 ], DQC[f 5 ], DQC[CRM_DB], etc.) are applied to data flows, processors, and database. From the user perspective, a scenario involving this CRM solution could be the following one: the customer browses the airline Web site searching for a flight to a given destination and for a given time period. During the browsing process, the Web site analyzer (S 2 ) collects information that identifies the customer and characterizes his profile (e.g., the customer may be a "gold" member of the frequent flyer program and what he is looking for during the current Web session may be of interest for the marketing team). Once the customer has chosen the appropriate flight, he may want to be called back (S 3 ) by the online phone reservation service of the company in order to make the reservation and the payment by phone. Then, he will be called back by the Call Center (S 4 ) and the information related to the customer, the call details and the reservation information will be entered into the CRM database by an operator using the back-office Help Desk (S 5 ). The Enterprise Marketing Automation (EMA) service (S 6 ) may then use the data stored in the CRM database to plan electronic surveys and trigger the actions of the airline marketing team and the commercial executives assisted by the Sales Force Automation (SFA) service (S 7 ) in order to propose commercial offers or to prospect (by (e-)mail or phone) and finally, for the front-line personnel to provide differentiated services to the loyal and profitable customers (e.g., on board by flights attendants). Frontline personnel not only needs information to service the customers, but they can provide critical information and insight back to the organization from their personal contact with each individual (f 12 ), and they may update the data describing the customers in the CRM database (f 14 ) that will increase the CRM knowledge and culture in the enterprise. Since processes and humans can introduce errors, data quality control procedures (DQCs) that can prevent and detect errors are an important component of the global system. They can be applied to data processing units or to data flows. They can eliminate data quality problems of completeness (C) (i.e., missing values), freshness (F) (i.e., obsolete values), uniqueness (U) (i.e., presence of duplicates), and valuation errors (V) (e.g., misspellings, outliers, inconsistencies, contradictions, constraints violations, etc.). Examples of DQCs are depicted in the table appearing within Figure 1. Each DQC policy may combine several techniques (such as ETL, Exploratory Data Mining, data sampling and tracking, etc.) for error detection and correction. Several (potentially overlapping or conflicting) pieces of information describing the customer may come from various data processing units through different paths.

Setting up systematically DQCs for each data flow and each service of the global system is cumbersome and impossible in practice. It is thus necessary to determine data quality hot-spots and vulnerabilities impacting data flows and identify the data processing units that generate and propagate data quality problems in order to choose the "best" path (less likely exposed to data quality problems) and target corrective actions depending on the costs they require.

OVERVIEW OF THE FRAMEWORK

In this paper, we consider a large business application as a composition of data processing units, i.e., applications interacting to deliver the requisite functionality for processing, manipulating, transforming or exchanging data. A data processing unit is viewed as a black-box with multiple inputs and outputs. Units communicate with each other in some specified way using various forms of communication (e.g., data exchange, query posting/answering, shared memory, messaging, etc.). A unit performs data processing and management operations using the provided data inputs to generate the data outputs. A number of such units constitute a data-centered application and they are inter-linked as it is illustrated in Figure 2 that represents the CRM example: CRM_DB has four inputs coming from the outputs of three other units (e.g., S 2 , S 5 and S 7 ) and three outputs. In this paper, we define a set of measures for analyzing the propagation of data quality problems, namely:

-the garbage-in garbage-out measure is defined for input/output data flows as the conditional probability of an error occurring on the output data flow given that there is an error on the input data flow. The garbage-in garbage-out measure can also be defined for a data processing unit as the probability of a data error is permeated from the inputs of the data processing unit to its outputs.

-the weight of error propagation path: when one output of a data processing unit is one of the inputs of another data processing unit, errors in the input data flow can propagate along a path to the other processing unit output data flows.

-the data pollution exposure for a data processing unit is the mean of the weights of all the propagation paths of the incoming data flows from the initial inputs to the considered data processing unit. It indicates which units will most probably be the ones exposed to errors propagating through the global system.

-the data pollution impact of a data flow or of a data processing unit: if one could assume independence over all error propagation paths, the impact measure would be the conditional probability of an error in the data flow f propagating all the way to the jth output of data processing unit S. The general interpretation of this measure is that the higher the impact, the higher the risk of an error in the source input generating an error in the output of the data processing unit.

-the criticality of a data flow or a data processing unit on the global system: for cost-efficiency, one may wish to concentrate resources for data quality controls (DQCs) on the most critical output data flows and, therefore, needs to know which data flows that are "best" (in a loose sense) to monitor or clean. Each output data flow of the global system is assigned a criticality measure, which is a value between 0 and 1, where 0 denotes not at all critical and 1 denotes highest possible criticality.

METRICS FOR TRACING DATA POLLUTION

We use the preliminary notations given in Table 1 for analyzing the propagation of data errors in datacentered applications.

Table 1: Preliminary Notations

The Garbage-In Garbage-Out Measure

Consider a pair of input and output data, the garbage-in garbage-out measure is defined as the conditional probability of an error occurring on the output given that there is an error on the input. Thus, for input i and output j, the garbage-in garbage-out measure is defined as follows:

Considering an input/output pair, this measure indicates how "permissive" or "retentive" a data processing unit is to errors occurring on that particular input. One characteristic of this definition is that it is independent of the probability of error occurrence on the input (as it is a conditional probability). On the other hand, GIGO measure is still dependent on the workload of the data processing unit as well as the type of the errors that can occur on the inputs. GIGO measure is defined at the data flow level, i.e., a GIGO value characterizes the error propagation from one input data to one output data. Going to the data processing unit level, we define the GIGO measure of a data processing unit S with m input data and n output data, to be:

Rather, it is an abstract measure that can be used to obtain a relative ordering across data processing units. If all inputs are assumed to be independent of each other and errors on one input data can only generate errors on one output data at a time, then this measure is the actual probability of an error on the input permeating to the output. Note that this does not necessarily reflect the overall probability that an error is permeated from the input of the data processing unit to the output. The larger this value is for a particular data processing unit, the more cleaning efforts have to be spent in order to increase the error detection and correction capabilities of that data processing unit (and decreasing consequently its GIGO measure).

Weighting an Error Propagation Path

As errors in a (source) input data flow can propagate along many different paths to the (destination) output data flow, we must consider this in our definition of the next measures. At the data processing unit level, we define the error propagation path from a data processing unit S k to another data processing unit S k′ of the global application, noted G, when one output of data processing unit S k is one of the inputs of the other data processing unit S k′ . The error propagation path can also be redefined at the input/output data flow level, such as:

is the error propagation path starting from the ith input of the S k data processing unit and ending at the i′th input of the S k′ data processing unit, -is the error propagation path starting from the ith input of the S k data processing unit and ending at the j′th output of the S k′ data processing unit, -is the error propagation path starting from the jth output of the S k data processing unit and ending at the j′th output of the S k′ data processing unit.

We define w(p) the weight of the error propagation path p, as the product of all the garbage-in garbageout measures from the start to the end of the data processing through K units:

(1)

(2)

Measuring the Data Pollution Exposure

Earlier, we had defined the garbage-in garbage-out measures for data processing units, that only consider the GIGO values of data processing units and couplings across units are disregarded.

We now define a set of measures that explicitly consider coupling and aid determining the data quality weak spots and vulnerabilities of the global application. To find units most likely to be exposed to propagating errors, we want to have some knowledge of the "amount" of errors that a data processing unit may be subjected to. Considering all the i′th inputs of the global system G, we define the error exposure measure of a data processing unit S on its inputs as:

where m is the number of inputs of data processing unit S, m G is the total number of inputs of the global application.

The error exposure measure is the mean of the weights of all the propagation paths of the incoming data flows from the initial inputs to the considered data processing unit. This measure does not consider any correlation that may exist between two or more incoming data flows. The error exposure measure indicates which units will most probably be the ones exposed to errors propagating through the global application.

Measuring the Impact of Data Quality Problems

It may be insufficient to only take into account the propagation characteristics of data errors for a global application in order to identify data quality weaknesses. Errors that have a low probability of propagating may still have significant consequences. Taking this into account, we now define measures which let us analyze to what extent errors in data flows (inputs or intermediate data flows) affect the global system output, i.e., what the impact of errors on the output data flows of the global application is. We define the impact of (errors in) the data flow f on the jth output of data processing unit S, as:

where w p is the weight of each possible error propagation path from f to the jth output of data processing unit S. If one could assume independence over all paths, the impact measure would be the conditional probability of an error in f propagating all the way to the jth output of S. The general interpretation of this measure is that the higher the impact, the higher the risk of an error in the source input generating an error in the output of the data processing unit.

Thus, one may consider data flows which have a high impact even though they may have a low error exposure (meaning that errors in this data flows are relatively rare but, should they occur, are likely to be costly). If the data processing unit S has multiple outputs, the corresponding impact value of the flow f which considers all of its outputs can be defined as:

(3) (4)

(5)

The impact of the data flow can be computed on the global output.

where n is the number of outputs of data processing unit S and n G is the total number of outputs of the global application.

Measuring the Criticality

The concept of impact as described above considers the impact on the output data flows generated by errors in input and intermediate data flows. However, when a system has multiple output data flows, these are not necessarily all equally important for the system, i.e., some output data flows may be more critical than others. For cost-efficiency, one may wish to concentrate efforts for data quality control and improvement (DQC) on the most critical output data flows and, therefore, needs to know which data flows that are "best" (in a loose sense) to monitor or to clean. Each global output data flow of the global application is assigned a criticality measure, which is a value between 0 and 1, where 0 denotes not at all critical and 1 denotes highest possible criticality. The criticality of a data flow f is then calculated relatively using the assigned criticality values of the global output data flows and the impact values calculated for the data flow f on the j′th output of the global application. The criticality of the data flow f is compared to the criticality of the jth output of the global application, as:

where Once we have the criticality of f with regard to each output data flow of the global application, we can compute an overall criticality value. We define the criticality of the data flow f for the outputs of the global system as:

At the data processing unit level, the criticality of data processing unit S is defined using the criticality values of all output flows of S, as:

Selecting Locations for DQCs

Consider the case where a data processing unit has low exposure but a high criticality. The low exposure means that there is a low probability of errors propagating to that data processing unit. However, the high (6)

(7) (8)
(9) [START_REF] Redman | Data quality: The Field Guide[END_REF] criticality means that, should an error find its way into that data processing unit, there is a high probability of that error having significant consequences. Thus, one may select data processing units with low exposure and high criticality for setting up data quality control and cleaning activities. From a cost viewpoint, taking care of high criticality events may not be worthwhile if these events have a very low probability of occurring. In this case, the data quality control and improvement policies will determine whether a low-probability event with high criticality will be taken care of or not.

Moreover, one may wish to set a minimum level of error detection, which can be accomplished by setting a maximum level on GIGO values and/or error exposure values. Thus, if a data processing unit or data flow exceeds these thresholds, this indicates that more resources have to be allocated to that data processing unit to increase its error detection and correction capabilities. A similar approach can be used for criticality (or impact). For example, a situation with low error exposure and high criticality (or impact) indicates that any error detection and cleaning mechanism in that location would have to be highly specialized as errors are infrequent and likely to be hard to detect. The opposite situation, i.e., high exposure and low criticality (or impact) indicates that a coarser error detection mechanism in that location may suffice. 2 (e.g., ETL scenarios, Exploratory Data Mining analysis, error detection, etc.), in order to decrease the GIGO value of the considered data processing unit, and subsequently, decrease the exposure and/or criticality values to the acceptable range, i.e., between LQT -Lower Quality Tolerance and UQT -Upper Quality Tolerance thresholds.

Table 2: DQC policies ordered by cost factor and based on the status of the CRM units

We select now the optimal locations for data quality control mechanisms (DQC) based on the profiles obtained from the analysis of the global system. First, we present three basic methods for selecting the locations of these controls: the first one finds flows and units that have the high impact on error propagation, the second one finds flows and units with high exposure, and the last one finds flows and units with high criticality:

-Impact-driven method (M1): If we take into account the impact of the data processing units or data flows on the global system outputs, we only consider the data flows with high impact for being guarded by DQCs. Flows and units with zero or low impact will not be selected for DQCs.

-Exposure-driven method (M2): If the exposure of a data flow f is zero, it means that errors in the inputs of the emitting data processing unit are unlikely to propagate through the data processing unit S. Thus, although the GIGO may be quite high, we'll not select the flow f as a location for a DQC. We don't consider the units or data flows with low exposure values for being guarded by DQCs (i.e., lower than the LQT E threshold). We do not select recursive flows with zero or low exposure on an output flow as well. We focus on flows and units with exposure higher than the UQT E threshold.

-Criticality-driven method (M3): If we take into account the criticality of the units and data flows on the global system outputs, we only consider the units or data flows with high criticality for being guarded by DQCs (i.e., greater than the UQT C threshold). Flows or units with zero or low criticality will not be selected for DQC.

Each data quality control policy has a cost, noted cost(DQC). Table 2 gives the cost coefficients that are applied to the CRM example. DQC's cost depends on the number, the processed data volume, and complexity of the techniques involved. When we predict that the data processing unit S introduces or propagates pollutions from its input data flows to its outputs, we need to consider the risk of this prediction because this may lead to set up non legitimate DQCs that have a non negligible cost. We can define empirically this notion based on N obs observations, as a quadratic function, noted Improv describing the data quality improvement for the data processing unit S when a DQC is applied:

where Cost(DQC) is the total cost of the data quality control policy DQC applied to the data processing unit S, and GIGO DQC [S] is the new GIGO value of the data processing unit S measured after the application of the DQC[S] policy to data processing unit S. Complementary to the methods M1, M2 and M3, our objective is to search for the locations on the data processing paths (i.e., data flows or data processing units) where DQCs have minimal cost and maximal improvement function in reducing the data quality problems.

Obtaining numerical values for the GIGO measures may prove to be quite difficult, given that many factors, such as error type, misclassification problem on error detection, have to be taken into account. Thus, an experimental method based on error injection for obtaining estimates of error GIGO values is used. Experimentally estimating values for GIGO of a data processing unit is done by injecting errors in the input data flows of the data processing unit and logging its output data flows. Suppose, for a global application such as the CRM example, we inject n inj distinct errors in input i and, at output j, we observe n err differences, then we can directly estimate the GIGO measure to be n err /n inj . The values of the improvement function per data processing unit where one DQC is applied are computed using the cost factors listed in Table 2.

To illustrate our experiments on the synthetic data set of the CRM example, we've identified the most impacted, exposed and critical data processing paths and we found the most relevant DQC locations with minimal cost maximizing the improvement function for the different methods. Figure 4 illustrates for the CRM example the most impacted data processing paths. As an example, considering the impact-driven method (M1), the main DQC locations would be on f 8 , f 9 and f 12 data flows.

Figure 4: Impact of data pollution propagation through the CRM application

RELATED WORK

Data quality is a multidimensional, complex and morphing concept [START_REF] Dasu | Exploratory Data Mining and Data Cleaning[END_REF]. Since a decade [START_REF] Wang | A Framework for Analysis of Data Quality Research[END_REF][START_REF] Wang | A Product Perspective on Total Data Quality Management[END_REF][START_REF] Wang | Journey to Data Quality[END_REF], there has been a significant body of work in the area of information and data quality management initiated by several research communities (i.e., statistics, database, information system, workflow and project management, knowledge engineering and discovery from databases), ranging from various techniques in assessing information quality to building large-scale data integration systems over heterogeneous data sources and in improving data quality in databases [START_REF] Dasu | Exploratory Data Mining and Data Cleaning[END_REF], in information systems [START_REF] Redman | Data Quality For the Information Age[END_REF][START_REF] Redman | Data quality: The Field Guide[END_REF][START_REF] Wang | A Framework for Analysis of Data Quality Research[END_REF][START_REF] Wang | A Product Perspective on Total Data Quality Management[END_REF][START_REF] Wang | Journey to Data Quality[END_REF] or in cooperative information systems and in data warehouse systems. Various data quality definitions, metrics, models, methodologies, cleaning and Extraction-Transformation-Loading (ETL) tools have been proposed by practitioners and academics with the aim of tackling the following main classes of data quality problems (outliers, inconsistencies, duplicates, (disguised) missing values, obsolete data, etc.). Many surveys and empirical studies showed the importance of quality in the design of information systems. Many works in the fields of information systems and software engineering address the quality control and assessment for the information and for the processes which produce this information [START_REF] Bobrowski | A Software Engineering View of Data Quality[END_REF][START_REF] Pipino | Data Quality Assessment[END_REF], but very few focused on the dynamics of data quality problems propagation. Alternatively, Web service composition has been a very active research area recently focusing on the dynamic selection of services based on user requirements and on the quality of service. In [START_REF] Zeng | Quality Driven Web Services Composition[END_REF], the authors propose the dynamic service composition using a global planning approach where the tasks (that can be accomplished by several potential Web services) are selected during the execution using the Multiple Attribute Decision Making method based on five quality criteria describing the service (e.g., execution price, execution duration, reputation, reliability, and availability). Our approach does not consider the dynamic composition of services. Instead, it focuses on analyzing and predicting the data pollution propagation and advocates the location of data quality controls to be integrated to the services. Our approach is initially proposed for the case where there are not several potential Web services available for processing a task, but it could be extended to dynamically select potential services based on their "data pollution retention" capabilities (i.e., low GIGO values). In the field of hard-and software engineering, a significant amount of research has been reported on the subject of dependability of computer systems, and a large number of analytical models and related approaches exist to predict reliability for such systems [START_REF] Hiller | EPIC: Profiling the Propagation and Effect of Data Errors in Software[END_REF][START_REF] Johansson | Error propagation profiling of operating systems[END_REF][START_REF] Kaaniche | Dependability Engineering of Complex Computing Systems[END_REF].

Because we believe that these models provide an excellent theoretical foundation for computing dependability, we applied the approach of Suri et al. [START_REF] Hiller | EPIC: Profiling the Propagation and Effect of Data Errors in Software[END_REF][START_REF] Johansson | Error propagation profiling of operating systems[END_REF] to the problem of data pollutions propagation in complex data-centered application in order to optimally recommend adequate actions for detection and correction of the data quality problems. We introduce the notion of QoD-dependability and we compute an improvement function when DQCs are applied.

CONCLUSION

This paper presents a framework for analysis of the propagation of data pollutions in a data processing unit composition. The proposed framework provides metrics for analyzing the data quality problems propagation for a given data processing unit composition and it allows the assessment of the vulnerability of data processing units and data flows to upcoming data quality problems. We introduced four measures both defined at the data processing unit and the data flow levels: 1) the garbage-in garbage-out measure, 2) the error exposure, 3) the error impact, and 4) the criticality of a data flow/data processing unit as a part of a complex data-centered application.

Based on the results of ongoing experiments on synthetic data and simulation of complex CRM application configurations, we have illustrated and how one may interpret the measurement results of the framework to determine potential data quality weaknesses in the global application.

Figure 1 :

 1 Figure 1: Data processing in the CRM example

Figure 2 :

 2 Figure 2: Data processing in the CRM example

Figure 3 :

 3 Figure 3: Status of the data processing units in the CRM example

* Work conducted when visiting AT&T Labs-Research, supported by the Marie Curie International Fellowship within the 6th European Community Framework Programme (FP6-MOIF-CT-2006-041000).


Laure Berti-Equille

Multi-Source Model and Architecture for Quality Negotiation and Integration of Biological Data

Introduction

Maintaining a certain level of quality of data and data sources is challenging in distributed multiple source environment. In practice, assessing data quality in database systems is mainly conducted by professional assessors with more and more cost-competitive auditing practices. Well-known approaches from industrial quality management and software quality assessment have beenadapted for data quality and came up with an extension of metadata management [START_REF] Reddy | Estimating data accuracy in a federated database environment[END_REF][START_REF] Jarke | Vassiliadis[END_REF][START_REF] Strong | Data quality i n context[END_REF][START_REF] Walpole | Quality of service semantics for multimedia database systems[END_REF][START_REF] Sheth | Q-data : Using deductive database technology to improve data quality[END_REF]. Classically, the database literature refers to data quality management as ensuring : 1) syntactic correctness (e.g. constraints enforcement, that prevent "garbage data" from being entered into the database) and 2) semantic correctness (i.e. data in the database truthfully re ect the real world situation). This traditional approach of data quality management has lead to techniques such a s i n tegrity constraints, concurrency control and schema integration for distributed and heterogeneous systems. Techniques such as data tracking, data cleaning and data quality controlling are costly in practice and time-consuming to adapt and con gure e ciently in a speci c application domain. Although critical to data quality for a single database, these techniques fail to address some issues that are important in a distributed and heterogeneous environment. As recent studies show, applications built on top of data warehouses often experience several problems due to the reliability a n d the quality o f integrated data (see Chapter 7 in 13]). The main reason is that the local databases participating in providing their data contain incorrect, inaccurate, outdated or poor quality data. The quality of integrated data then becomes even worse unless suitable methods and techniques are employed during the multi-source environment design. Despite the amount o f w ork focuses on semantic heterogeneity among data and metadata 12], the quality of integrated data has not beenaddressed so far. Only few research projects addressed the issues of multi-source data quality control and the management of enriched metadata in which speci c analysis and optimization techniques are embedded 7, 18, 3]. Data quality mainly has been and still is an important research topic independent of data base integration. Another bodyof research literature recently focuses on improving aspects of quality of service in information and database systems 1, 24], or on the particular problems of trade-o between freshness of data, system performance and precision by minimizing data transfer through incremental view maintenance 19].

In this extended abstract, we focus on data quality in a multi-source environment. We claim that data con icts often occur due to the di erence of local data quality a n d i t s v ariation over time. Considering quality dimensions implies that there is not a unique resolution of data con icts for integration, several solutions are possible and should be transparent to users : for example, if the values of two objects referring to the same real world concept di er and if one value is known to be more accurate and the other one is known to be more up-to-date, a con ict needs to besolved considering aspects of data accuracy versus data freshness. Note that we assume that accurate data does not necessarily imply up-to-date data and vice-versa. So, for the resolution of this con ict, a unique data integration rule is not su cient and not exible enough. Therefore, in the context of a standard wrapper-mediator architecture, we suggest to di er data con ict conciliation using quality requirements for the query results. Rather than data integration, we propose data recommendation based on data and source quality. Quality dimensions are formalized by a quality contract which is negotiated by the mediator. We propose a negotiation algorithm included into the query and mediation processing. The negotiation allows to customize multi-source integration according to end-users' requirements. This technique embeds implicitly quality control into the multi-source data extraction. Our application context is biological databanks.

Related Works

Classically, the methods and techniques described in this paper are in uenced by t wo main areas : data cleaning and data quality as metadata management. The aim of this section is to confront the research propositions of these areas to some speci cities of the biological databanks.

Mediation and cleaning of multi-source data

Data cleaning objectives are to detect matching records from several input extensional data structures (relational tables, object classes, DTDs), to nd out and eliminate duplicate records in the integration process. As mentioned in 6], the main drawback of data cleaning methods is that, besides being a knowledge and time intensive task (since it implies several passes on the data), nding the suitable key for putting together similar records is very di cult. As another drawback, the support for cleaning rules o ered in 17] allows matching rules to be applied only to pairs of neighbour records in the same le. Although, the problem of the possible con ict in data values was recognized, few speci c solutions were o ered [START_REF] Rothenberg | Metadata to support data quality and longevity[END_REF][START_REF] Kashyap | So far (schematically) yet so near (semantically)[END_REF]. Another problem arising from the proliferation of independent sources, some of them with overlapping information, is the inconsistency of information content, and hence there is a need for methods to resolve such inconsistencies in global answers. Inconsistencies result in multiple candidate answers the dual problem also exists, that is a global query might h a ve no answer at all. The usual approaches to reconciling the heterogeneities in data values are (1) to prefer the values from a more reliable database, (2) attach tags with data source identi cations to data items and rely on the reputation of the data source 33], (3) store reliability measures of data sources from which a data item originated along with the data item itself 26]. These approaches also su er from several drawbacks. First, it is not clear how to determine which of the sources is more reliable and how to measure reliability o f a source. Second, even if the reliability o f the data sources is somehow p r o vided, it is implicitly assumed that the reliability remains the same for all data items from a particular data source. However, the reliability of the data items may besigni cantly di erent in the di erent parts of the source. And third, storing the reliability information or the data source tags along with the data items requires signi cant modi cations in the conventional query processing mechanisms and increases data storage requirements.

Multi-source data quality and meta-data management

There are a number of research i n vestigating issues related to models and methodologies for data quality improvement 34, 32, 29], speci cations and metrics for data quality dimensions 14]. Currently, data quality audits are the only practical means for determining quality of data in databases by using the appropriate statistical techniques. Since databases model a portion of the real world which constantly evolves, the data quality estimates become outdated as time passes. Therefore, the estimation process should berepeated periodically depending on the dynamics of the real world. The statistical aspects of data quality have been the primary focus with statistical methods of imputation (i.e., inferring missing data from statistical patterns of available data), predicting accuracy of the estimates based on the given data, data edits (automating detection and handling of outliers in data). The use of machine learning techniques for data validation and correction is considered in 27]. For example, 28] describes a prototype system for checking correctness of the existing data (called data validation and cleanup). Utilization of statistical techniques for improving correctness of databases and introduction of a new kind of integrity constraints were proposed in 11]. The constraints are derived from a database instance using the conventional statistical techniques (e.g., sampling and regression), and every update of the database is validated against these constraints. If an update does not comply with them, then a user is alerted and prompted to check correctness of the update. Despite the fact that there is much research growing the importance impact of data quality for end-users and that many techniques have been proposed to improve and maintain quality o f local databases, very few projects try to use quality metadata for multivalued attributes in distributed and quality-heterogeneous environment (DWQ 3], HiQiQ 18], 7]). The use of metadata for data quality e v aluation and improvement w as advocated in 25]. The author argued that information producers should perform Veri cation, Validation, and Certi cation (VV&C) of their data. The data quality metadata should also be supplied along with a database. The metadata help in the process of estimating and maintaining the quality of data. A great amount of e ort has beeninvested in the development of metadata standard vocabularies for the exchange of information across di erent applications domains (such as geographic information systems 8] or digital libraries (Dublin Core 35]). We a r e n o t a ware of any kind of project that tries to specify metadata for biological data and, furthermore, data quality has not been addressed so far in the biological domain and in the current standardization works.

Example of Biological Information Retrieval from Distributed Databanks

Searching across distributed, disparate biological databases is increasingly di cult and timeconsuming for biomedical researchers. Bioinformatics is coming to the forefront t o address the problem of drawing e ectively and e ciently information from a growing collection of 511 multiple and distributed databanks1 .). For example, suppose a biological researcher working with a protein and wanting to know what are the protein functions, its cellular location, what gene it is and its DNA sequence, whether the rRNA sequence is known, how the gene is transcribed into mRNA, how the mRNA is translated into that protein... With the currently available biological banks and tools the researcher has to search the relevant databases one by one and then to locate the information items of interest within the return results.

Example 1

Our mediator is designed to provide information about proteins. A protein (Pr) related to a species (Sp) has a sequence (Sq) with an identi cation number(Id) and a set of bibliographic references (Rf). The mediator of our example will query three existing sources S 1 (EMBL 2 ), S 2 (GeneCards 3 ) and S 3 (SWISS-PROT 4 ). The raw values are automatically extracted by scripts using the DTD of sources. In order to de ne an appropriate data integration rules for these sources, obviously data con icts have t o b e r e s o l v ed due to the di erent v alues recorded for the same concept. Traditional data integration approaches suggest a con ict resolution method that either chooses one value over the other (or that computes the average in case of the numerical values). A global query for the protein sequence would retrieve one data value from the source according to the speci ed data integration rule. Note that the same source (S 1 ) may propose several values for the same concept. Now assume the following scenarii :

Scenario 1 : S 1 updates their data every night, S 2 monthly and S 3 weekly. In this case, the global query may determine from which data source the most up-to-date data are retrieved.

Scenario 2 : S 3 is the server of an institute which does its own sequencing for human species.

Sequence data are highly accurate for this species. S 2 data may h a ve sometimes parsing errors and may come from other sites.

Scenario 3 : S 1 and S 2 cover more biological domains than S 3 . S 1 is one of the main genetic databanks and S 3 is one of the main databanks on proteins. Information items of S 1 are usually less complete and accurate than those of S 3 for the protein domain.

The above scenarii brie y show t h a t t h e w ay o f h o w and when data is populated into the local sources plays an important r o l e f o r i n tegrating local data for global queries. They also describe source dependencies and data quality dimensions such as freshness, accuracy, completeness or coverage. Up-date data does neither imply most accurate data nor most complete data. Actually, a global user might b e i n terested in most complete data, and another one might be rather interested in most accurate data. In both cases, it should be possible for these users to specify tolerance thresholds for data and source quality (or, at least, to give t e c hnical means to estimate the quality o f query results from the di erent sources). We propose quality c o n tract speci cation for enhancing and using dynamically source and data quality requirements in the query processing. This technique enables to di er data integration to end-user according to exible quality criteria. Our approach is a standard mediator-wrapper architecture including new functionalities such as quality s o u r c e c o n tract negotiation included into mediation. The negotiation algorithm we propose selects the multi-source data as query results considering the quality of sources. Inter-linked objects are detected beforecombining the results. A implicit assumption underlying this research is that we incorporate a set of controls on the top of data sources to enhance the global system's reliability and its data quality the nal aim is to maintain a high probability of preventing, detecting and eliminating data non-quality for data integration in an application domain where data quality has not been addressed.

A Description of the Multi-Source Architecture

We argue that database techniques such a s h a ving an expressive i n ternal data model and query language, together with a meta-information repository and meta-information analysis techniques constitutes a necessary foundation for a mediator system. In order to alleviate the problem of information overload and confusion when results of a query are presented, the classical solution is to rank the results according to consistent r e l e v ance assessments. Our approach is to include quality speci cations for sources and send them with the query. Such a functionality for retrieval and integration of information must be supported by an easily extensible, scalable and customizable architecture for addressing a wide range of speci c applications such as the biological data domain. In this perspective, we propose a multi-source architecture (see Figure 1). From the application layer, the user can submit a global query to the mediator which conjointly sends the query and a quality contract type to the sources' wrappers. The wrappers send the corresponding local query to their respective source. Information sources may becross-referenced, structured or not and with or without a meta-information repository. They respond to their wrapper with the query result and a contract instance. At the mediation layer, the mediator computes 1) a conformance score for each source corresponding to the constraint satisfaction with respect to the contract speci cation, and 2) a con ict score for the query result. The mediator negotiates with the best sources and combines the query results for data recommendation, and sends it back to the user. The main features of the multi-source data model are summarized by a reference model, will be used in the rest of the paper for the discussion. The reference model should not be interpreted as a new model, rather it is similar to the core m o del Object Exchange Model OEM described for the TSIMMIS project 2]. We distinguish the mono-source objects level and the multi-source objects level. A concept of the real world is described by n mono-source objects extracted from n sources and also by o n e m ulti-source object.

De nition 1: A mono-source object

A mono-source object is a quintuple < oid label type value sid > where oid is the mono-source object's identi er, label is a character string, type is either complex or some identi er denoting an atomic type (like integer, string, gif-image...) w h e n t y p e is atomic and its value is an atomic value of that type. Otherwise, the type is complex and its the valueis a set of oids (identi ers of so called subobjects). sid is the data source's identi er.

A mono-source object may be considered as a tree structure and we de ne that it has the rst depth level (noted level(o) = 1 ) .

A source S contains a set of mono-source objects O s composed with objects o i , : : : , o. S accepts queries over O s . A q u e r y over S simply speci es values for some of the objects of O s . Thus, a query Q is an assignment o f v alues v 1 , : : ,v to the objects o i , : : : , o of O s .

A s u b object o 0 has the same structure than its root object o, but its depth level is level(o 0 ) = level(o) + 1 .

De nition 3 : A multi-source object

A multi-source object is a quintuple < ofid list(label) type value list(sid) > where ofid is the multi-source object's identi er. Its value is composed with a set of pairs (value sid) extracted from the mono-source level which describe the same concept of the real world. The multi-source object has a list of labels considered as synonyms (concatenation of the di erent labels of mono-source objects referring the same real object). The value of a multi-source object is composed by aggregating several values of mono-sources objects under the conditions that : i) those values refer to the same concept of the real world ii) the data con icts raised between more or less contradictory values are negligible (i.e. under a given threshold) and still allow d a t a aggregation into the value of the multi-source object. The list of sources' identi ers is also mentioned in the multi-source object.

Example 2

The multi-source object aggregating all the available values for a query asking for the species (Sp) and the sequence (Sq) of YWHAZ protein is built as follows :

In order to provide <of, "YWHAZ"],set(ofid),fof1,of2,of3g, S1 S 2 S 3]> * l i s t o f l a b e l s <of1, "DE","GeneCard for","Protein name"],set((string,sid)), f("Human phospholipase A2 mRNA, complete cds",S1), ("YWHAZ ",S2),("14-3-3 PROTEIN ZETA/DELTA",S3)g, S1 S 2 S 3]> * list of source's IDs <of2, "OS","FT /organism=","from"],set((string,sid)), f("Homo Sapiens(Human)",S1),("Homo Sapiens",S1), * 4 pairs (value sid) ("Homo Sapiens(Human) Bos taurus(Bovine)",S3)g, S1,S1,S3]> <of3, "FT /translation=","SQ Sequence","Representative Sequence","Sequence information:"], set((string,sid)), f("MDKNELVQK...",S1), adequate level of quality, the mediator needs to include capabilities such as negotiation, monitoring and adaptation. These capabilities all require the expected and the provided quality levels to beexplicitly speci ed. Quality dimensions can bespeci ed statically at the time of source integration or dynamically at deployment or runtime. We characterize quality of data and quality o f source along named dimensions (mentioned non-exhaustively in Table 1). Specifying abstractly quality dimensions with a name and a d o m a i n v alue gives a exible approach for deciding which dimension should be provided and implemented for a given application. The transparency of user's global query processing is weakened by the fact that the user can specify quality contracts for the query results. Based on the matching of user's quality requirements and the quality for each local source, negotiation and mediation are generated dynamically by the global query processor of the mediator to ensure the retrieval of high quality d a t a f r o m t h e multiple local sources. For our particular application, these quality dimensions may be speci ed in a contract type which represents quality dimensions, speci es the name, the domain and possibly user-de ned User grade based on presentation of data results and ease of understanding and using 2 also presents the instance of contract type 6 . A c o n tract is an instance of a contract type that represents a set of quality dimensions speci cations for the source. A contract aggregates a n umber of constraints. Conformance corresponds to constraint satisfaction (as a boolean function noted C S ). We de ne a conformance score for each source S j as a w eighted function F on the i speci ed contract types and their k dimensions.

8S j contractType i dimensionName k Conformance(S j ) = F(w i w k C S (ContractT ype i dimensionName k S j ))

Each c o n tract type may has also particular weights w i for computing the conformance score of each source S j (e.g. the contract type on Freshness is more important than the one on Completeness). Each dimensions of a contract type has particular weights w k indicating the relative importance of the kth dimension for the contract (e.g. dataAge is more important than updateFrequency). The conformance scores range from 0 to 1. The con ict score Conflict(S Q o) of source S for query Q corresponds to the distance b etween o the object of S and q the queried o b j e ct of Q. The distance Dis(o q) is the sum of data con ict importances de ned as follows :

Dis(o q) = P n j=1 I j with I j the jth data con ict importance such a s : I j = 8 < : 0 if there is no con ict 0:1 if the con ict is weak 1 if the con ict is strong The values of con ict score range from 0 to 1.

Conclusion

In order to facilitate the multi-source data integration in the context of distributed biological databanks, we propose a technique based on the notions of quality c o n tract and source negotiation. Our approach is based on a standard wrapper-mediator architecture. A quality contract with a source allows to specify quality dimensions necessary to the mediator for data selection between several distributed applications. The selectivity of data sources is dynamically computed by the algorithm of contract negotiation we propose to associate with the global query processing and before data acquisition. Our article proposes to evaluate the importance of data con icts and to use the quality conformance of sources : the integration of the data is carried out according to the quality of the data required by users. The approach is original and exible with respect to data mediation and conciliation because it includes source quality of service speci cations into the query processing. From the biological application point-of-view, we rst introduce the notion of multi-source data quality and data recommendation for biologists and our objective is that the current standardization e orts take i n to account the quality of biological data and promote operational techniques and tools to evaluate and improve it.

Figure 1 :

 1 Figure 1: Multi-source Architecture

Figure 2 :

 2 Figure 2: Example of quality source contract types and instances Each object o in the result for query Q is ranked according to a conformance score Conformance(S Q o) of the source S and a con ict score Conflict(S Q o) which are computed by the mediator. Query results are then ranked according to Conformance(S Q o) a n d Conflict(S Q o) scores De nition 5

Table 1 :

 1 General De nitions of Quality Contract Types ordering for each dimension. We can specify examples of source contract types such a s : Availability, F reshness, Coverage and Completeness.Figure

For more details, see the Public Catalog of Databases : DBcat, http://www.infobiogen.fr/services/dbcat

EMBL (European Molecular Biology Laboratory), http://www.ebi.ac.uk/embl/

GeneCards, http://bioinformatics.weizmann.ac.il/cards/

SWISS-PROT, http://www.expasy.ch/sprot/sprot-top.html

The values used to compute the conformance score are extracted from the current release of EMBL, Genecards and SWISS-PROT available on-line