A Distributed Case-Based Query Rewriting

1 Introduction

Nowadays, information systems can be thought as collections of information sources and information consumers that are often distributed in world-wide networks. This means that sources and consumers can be autonomous and thus are often heterogenous and dynamic. Information sources are heterogenous due to discrepancies at the physical level (different DBMSs, software and hardware platforms), logical level (different data models), and conceptual level (different schemas, concept and relation names).

Example 1.1 Figure 1 shows an example of three information sources about articles on computer science and their authors. Let us suppose that the three sources receive the query ✂ ✄ ✆ ✝ ✞ ✟ ✡ ☞ ✆ ✍ ✏ . ✒ ✓ can answer to ✂ ✄ (it finds a view that matches with ✂ ✄ ), whereas ✒ ✖ and ✒ ✘ can not. Indeed, the schema of ✒ ✖ is different (heterogeneity of schemas). Notice that, if we rewrite the query as ✂ ✚ ✄ ✆ ✝ ✞ ✟ ✡ ☞ ✆ ✞ ✢ ✤ ✦ ✒ ★ ✩ ✫ ✆ ✬ ✮ ✯ ✱ ✚ ✚ ✲ , ✒ ✖ is able to answer since ✞ ✟ ✡ ☞ ✆ ✞ ✢ ✤ ✦ ✒ ★ ✩ ✫ ✆ ✬ ✮ ✯ ✱ ✚ ✚ ✲ is part of its schemas. For what concerns ✒ ✓ , it is not a matter of heterogeneity, ✒ ✓ simply does not have the required information.

Information consumers are heterogeneous as well, since each consumer may have different customization needs due to distinct business objectives. Moreover autonomous information sources are dynamic, since they may be added to the system, may become (temporarily or definitively) unavailable, or, sometimes, may also vary their conceptual schemas. Information consumers are also dynamic. Indeed new consumers can be inserted or removed. Furthermore, their information needs can change very often. Our work deals with information integration in distributed, heterogeneous, and dynamic information systems, i.e., constructing answers to query from consumers. Our primary goal consists on rewriting a consumer's query into queries to specific information sources. In [M. Panti, L. Spalazzi, A. Giretti, 2000] we proposed a distributed case-based approach to the problem of rewriting queries. According to this approach we have a dynamic mediated schema (the case memory) instead of a static one (as in other systems). Indeed, our mediator's schema is dynamically updated through the cooperation with information sources and other mediators, strongly influenced by the queries submitted by a consumer. In this paper we focus on the cooperation strategies of the distributed case-based reasoner. Indeed, we compare different strategies from a theoretical point of view and discuss the results. The paper is organized as follows. Section 2 reports the related work. An overview of our work is provided in Section 3. Section 4 summarizes results about local query rewriting (i.e. when a query can be reformulated by a single mediator). Section 5 describes the distributed query rewriting (i.e., when a query can be reformulated only through cooperation among mediators) and discuss some theoretical results. Finally, some conclusions are given in Section 6.

2 RelatedWork

Intelligent Information Integration (I ✓ ). The most significative approach to information integration relies on the so called mediator architecture [Wiederhold, 1992]: an architecture with three-layers. A layer is devoted to information consumers, another layer is devoted to information sources, the middle layer (i.e. the mediator) deals with the reformulation of a given query in a set of queries, each targeted at a selected source. Intuitively, such a reformulation would be equivalent to the original query (i.e., denote the same set of instances). Nevertheless, often this is not possible. Therefore, a query reformulation contained in (instead of equivalent to) the original query is considered adequate (see for example [Ullman, 1997; Beeri et al., 1997]). Furthermore, when a description logic (e.g. [Borgida and Patel-Schneider, 1994]) is used as data modeling and query language (e.g. [Beeri et al., 1997; Kirk et al., 1995; Ullman, 1997]), the problem of query containment corresponds to the subsumption problem.

There are two basic approaches to intelligent information integration: the procedural approach and the declarative approach. In the procedural approach (e.g., TSIMMIS [GarciaMolina et al., 1997]), mediators integrate information from sources through ad-hoc procedures defined with respect to a set of predefined information needs. When such needs or sources change (i.e., we have a dynamic information system), a new mediator must be generated. In the declarative approach (e.g., SIMS [Arens et al., 1993], Information Manifold [Kirk et al., 1995], and Infomaster [Duschka and Genesereth, 1997]), mediators use suitable mechanisms to rewrite queries according to source descriptions. Usually, the proposed systems do not allow automatic adaptation of such descriptions when something changes.

Distributed Case-Based Reasoning (DCBR). A distributed case-based reasoner [Prasad et al., 1996; Plaza et al., 1997] learns by experience and cooperation how problems can be solved. Therefore, it is appropriate for distributed and dynamic application domains, when it is impossible to have predefined solutions. Nevertheless, as far as we know, its application to information integration is a novelty. In DCBR, there are several agents; each agent has its own case memory since it could have acquired its own independent problemsolving experiences. A new problem is solved through agent cooperation. Indeed each agent reuses the local past case that best contributes to the overall case. Description logic is applied to case-based reasoning (and thus DCBR) as well (e.g. [Koehler, 1994]). Indeed, in case-based reasoning, subsumption becomes a powerful tool to automatically derive case hierarchies that can be used in case retrieval and case retention.

3 Work Overview

Our goal is to build an information system capable of interconnecting information consumers and sources. Previous approaches solve several problems concerned with distributed, heterogeneous information systems. Their main limitation is related to the capability of evolving according to dynamic information systems. We propose (see also [M. Panti, L. Spalazzi, A. Giretti, 2000]) a multi-agent system which is based on a mediator architecture, i.e. mediators, sources, and consumers are agents. All the agents adopt a description logic called C-CLASSIC [Borgida and Patel-Schneider, 1994] as data modelling and query language. Indeed, subsumption in C-CLASSIC can be computed in polynomial time.

In our work, the capability of a mediator agent to face heterogeneous and dynamic systems relies on a thesaurus and a distributed case-based reasoner. Each mediator has its own thesaurus in order to solve name heterogeneity. A thesaurus is composed by a set of classes of synonyms. Each element of a class has the reference to information sources that use it as term. Every time a new query arrives, its terms are translated in standard terms by means of the thesaurus. The reverse process occurs when the rewritten query must be sent to information sources. The thesaurus must be dynamically updated when a change in the system occurs. The classes of the thesaurus are modified by means of clustering. The explanation of this technique is out of the scope of the paper, for more details we remind to [Diamantini and Panti, 1999]. Therefore, in the rest of the paper we assume that no name heterogeneity occurs (i.e., the thesaurus has a maximum precision). Each mediator has also its own case-based reasoner in order to solve heterogeneity of schemas and consumer's needs. Each case contains a query and the corresponding reformulation, and it is stored in the mediator's case memory. When a new query from the consumer arrives, the mediator looks for past queries subsumed by the new one and adapts the corresponding solutions in order to obtain a reformulation of the new query. This means that the mediated schema is strongly influenced by the queries submitted by consumers (mediator's experience). When this experience does not help, the mediator cooperates with other mediators and/or information sources. This approach allows the mediator to update its schemas and therefore to take into account changes in information sources and consumer's needs. This can be considered a kind of distributed case-based reasoning.

In our system, information source agents 1 are able to cooperate with mediators through a query reformulation based on local schemas. Indeed each source is able to find a view over its schema that is subsumed by an input query.

Example 3.1 Let us consider the distributed information system of Figure 1 (Example 1.1). According to the above assumption, we consider that all the (concept and role) names have been already translated by a thesaurus and thus no name heterogeneity occurs. Nevertheless, conceptual schemas are different (as showed in Example 1.1).

1 Notice that when a source is a non-agent software, we need a wrapper as interface between the source and the rest of the system.

Let us suppose that source ✒ ✖ receives a query ✂ ✖ ✆ ✝ ✞ ✉ ✈ ✦ ✟ ✤ ✆ ✬ ✇ ✩ ✍ ① ② ✲ . ✒ ✖ finds that ✂ ✖ subsumes acm trans and ieee trans and thus returns the corresponding instances (denoted by ✱ ◗ ❙ ③ ✍ ④ ⑤ ✈ ✩ ✍ ① ② ⑥ ⑦ ✱ ◗ ❙ ③ ✏ ✤ ✤ ✤ ✈ ✩ ✍ ① ② ⑥ ).

4 Local Query Rewriting

Generally speaking, a case is an arbitrary set of features (attribute-value pairs). Some features are devoted to represent a problem (in our application the query to be reformulated) in order to make easier the retrieval of a past problem similar to the current situation. The rest of features are devoted to represent the problem solution (the reformulated query and information sources where the reformulated query has been sent) to reuse it in the current problem. Furthermore, the problem of rewriting queries has a fundamental condition that must be satisfied: the rewritten query must be contained in the original query [Beeri et al., 1997; Ullman, 1997]. We use C-CLASSIC as a language for representing queries and thus cases. The subsumption relation is used as query containment and thus for case retrieval. According to above considerations, a case is a structure as the following: ⑨ ✂ ⑩ ❷ ★ ❹ ③ ✂ ⑥ ⑩ ⑨ ③ ✂ ✖ ⑩ ✒ ✖ ⑥ ⑩ ✆ ✆ ✆ ③ ✂ ❆ ⑩ ✒ ❆ ⑥ ❺ ❺ where ✒ ✖ ⑩ ✆ ✆ ✆ ⑩ ✒ ❆ are information sources and ✂ ✖ ⑩ ✆ ✆ ✆ ⑩ ✂ ❆ are queries to ✒ ✖ ⑩ ✆ ✆ ✆ ⑩ ✒ ❆ respectively. ✂ is a given query and ❷ ★ ❹ ③ ✂ ⑥ is its reformulation, i.e., a set of arbitrary combinations of ✂ ✖ ⑩ ✆ ✆ ✆ ⑩ ✂ ❆ such that each element of ❷ ★ ❹ ③ ✂ ⑥ is subsumed by ✂ . A collection of cases is called case memory. A terminology (i.e., a set of concept definitions and their relations) is always associated to a case memory. ❼ ⑩ ❽ represent the top and bottom concepts, respectively. The initial case memory can be built as static mediated schemas of traditional mediators (e.g. SIMS [Arens et al., 1993]). In our system, the added value is that the DCBR works to maintain updated such a schema.

Example 4.1 Figure 2 and Figure 3 show the case memory and the terminology of a mediator of Example 3.1.

Query Retrieval. Every time a new query arrives, it is inserted in the terminology and classified by means of subsumption. If there exists a past problem equal to the new query, then its solution can be used as solution for the new query. Otherwise, the solutions of past problems that are subsumed by the new query can be used as solution for the new problem. The closest to the new query the retrieved cases are, the best the solutions are. This drives us to the notion of problems maximally contained in the new query. This notion allows the definition of the retrieval function ❾ ❑ ❆ ❿ ③ ✂ ⑩ ➁ ⑥ as a set of conjunctions of concepts (➂ ❑ ➃ ✖ ➄ ❑ ) of the given terminology ( ➁ ). For each conjunction of concepts there does not exist another conjunction of concepts of the same terminology (➂ ❂ ➃ ✖ ➅ ❂ ) such that ③ ➂ ❑ ➃ ✖ ➄ ❑ ⑥ ➆ ③ ➂ ❂ ➃ ✖ ➅ ❂ ⑥ ➆ ✂ .

Example 4.2 Let us suppose to have ✂ ✘ ✆ ✝ ✞ ✟ ✡ ☞ ✆ ③ ✍ ✏ ➂ ✫ ☞ ⑥ as input query in Example 4.1. Applying the retrieval function we obtain: ❾ ❑ ❆ ❿ ③ ✂ ✘ ⑩ ➁ ⑥ ✝ ✬ ➉ ⑩ ➊ ➂ ➌ ✲

Query Reuse. The basic reuse algorithm (➎ ❑ ❆ ❿ ③ ✂ ⑩ ➁ ⑥ ) simply copies past solutions of past problems returned by the retrieval function.

Example 4.3 Applying the basic reuse algorithm to Example 4.2, we obtain: ➎ ❑ ❆ ❿ ③ ✂ ✘ ⑩ ➁ ⑥ ✝ ❷ ★ ❹ ③ ➉ ⑥ ⑦ ③ ❷ ★ ❹ ③ ➊ ⑥ ➂ ❷ ★ ❹ ③ ➌ ⑥ ⑥ 2

Now we have all the building blocks to define the local reuse algorithm ( ➑ ③ ✂ ⑩ ➁ ⑥ ). Such an algorithm decomposes each consumer's query in basic components, applies the basic reuse algorithm to each component, and finally assembles the corresponding results (a more detailed description can be found in [M. Panti, L. Spalazzi, A. Giretti, 2000]).

Example 4.4 Let us suppose to have ✂ ✓ ✆ ✝ ✞ ✟ ✡ ☞ ✆ ✍ ✏ ➂ ✞ ✟ ✡ ☞ ✆ ✍ ④ ⑤ as input query in Example 4.1. Applying the reuse algorithm we obtain:

Notice that this is just one possible answer, another mediator with a different case memory may rewrite the query in a different way and thus return a different answer.

It is easy to prove that each element of ➎ ❑ ❆ ❿ ③ ✂ ⑩ ➁ ⑥ and ➑ ③ ✂ ⑩ ➁ ⑥ is subsumed by ✂ . Therefore, a reformulation is contained in the original query as required in the definition of case. Finally, notice that in general ➎ ❑ ❆ ❿ ③ ✂ ⑩ ➁ ⑥ → ✝ ➑ ③ ✂ ⑩ ➁ ⑥ .

Query Evaluation. When the mediator has a reformulation of the received query, it must send such a reformulation to related information sources and wait for their answers.

Example 4.5 The evaluation of ❷ ★ ❹ ③ ➊ ⑥ consists on querying sources ✒ ✖ , ✒ ✘ , and ✒ ✓ with ✞ ✟ ✡ ☞ ✆ ✉ ★ ✡ ✩ ① ✍ ❹ , ✞ ✟ ✡ ☞ ✆ ✫ ☞ , and ✞ ✟ ✡ ☞ ✆ ✍ ✏ respectively, and integrating the related answers. The semantics of concepts helps us on integrating the answers. Let ✱ ◗ ❙ ③ ✞ ✟ ✡ ☞ ✆ ✉ ★ ✡ ✩ ① ✍ ❹ ⑥ , ✱ ◗ ❱ ③ ✞ ✟ ✡ ☞ ✆ ✫ ☞ ⑥ , and ✱ ◗ ❲ ③ ✞ ✟ ✡ ☞ ✆ ✍ ✏ ⑥ be answers from ✒ ✖ , ✒ ✘ , and ✒ ✓ respectively, then the answer to ✞ ✟ ✡ ☞ ✆ ③ ✉ ★ ✡ ✩ ① ✍ ❹ ➂ ✫ ☞ ⑥ is: ③ ✱ ◗ ❙ ③ ✞ ✟ ✡ ☞ ✆ ✉ ★ ✡ ✩ ① ✍ ❹ ⑥ ➙ ✱ ◗ ❱ ③ ✞ ✟ ✡ ☞ ✆ ✫ ☞ ⑥ ⑥ ⑦ ③ ✱ ◗ ❲ ③ ✞ ✟ ✡ ☞ ✆ ✍ ✏ ⑥ ➙ ✱ ◗ ❱ ③ ✞ ✟ ✡ ☞ ✆ ✫ ☞ ⑥ ⑥ .

Failures. We have a local failure in query reuse when a mediator is not able to rewrite a given query ✂ , i.e., ❷ ★ ❹ ③ ✂ ⑥ ✝ ❽ 3 . This means that the mediator's case memory contains no past cases that can be used to reformulate ✂ . Usually this is due to the fact that it is the first time that the consumer formulates such a query, i.e., the consumer has a new information need.

2 ➜ ➝ ➞ ➟ ➠ ➡ ➢ ➜ ➝ ➞ ➟ ➤ ➡ means that each element of ➜ ➝ ➞ ➟ ➠ ➡ is conjuncted with each element of ➜ ➝ ➞ ➟ ➤ ➡ .

3 Notice that ➥ ➟ ➦ ➡ ➨ ➩ .

❪ ❀ ❀ ❀ ❂ ❃ ✾ ❅ ❆ ❈ ❉ ➭ ➯ ➲ ■ ● ✿ ➭ ➯ ➲ ■ ❈ ❑ ➭ ➯ ➲ ■ ❈ a113 ❭ ❆ a114 ❨ ➭ ➯ ❈ ❑ ■ ❈ ➳ ➵ ❀ ➸ ✻ ✽ ✾ ✿ ❉ ❑ ❨ ❬ ❭ ❅ ❀ ❪ ❫ ❵ ❛ ❝ a115 ❣ ■ ❈ ➳ ➵ a114 ❅ ❈ ❆ ❨ ❀ ➸ ❈ ➳ ➵ ❊ ✻ ❂ a114 ♥ ✽ ❭ ❀ ❪ ➺ ❅ ❈ ❆ ❨ ❣ ■ ✹ ❀ ➸ ✻ ✽ ✾ ✿ ❀ ✺ ❂ ❃ ✾ ❅ ❆ ❈ ❉ ❊ ● ✿ ❍ ■ ❳ ❀ ➸ ✻ ✽ ✾ ✿ ❀ ❈ ➳ ➵ ■ ❦ ❀ ➸ ✻ ✽ ✾ ✿ ❀ ❈ ❑ ■ ♣ ❀ ➸ ✻ ✽ ✾ ✿ ❀ ✺ ❈ a113 ❭ ❆ a114 ❨ ❊ ● ✿ ❍ ❀ ❀ ❀ ❣

Figure 3: An example of terminology.

Example 4.6 Let us consider the case memory of Example 4.1 and the query ✂ ➻ ✆ ✝ ✞ ✟ ✡ ☞ ✆ ✍ ✏ ➂ ✞ ✍ ➼ ➼ ✏ ❹ ✏ ✍ ✈ ✏ ★ ① ✆ ✬ ✮ ❷ ✈ ✍ ① ➼ ★ ✩ ✫ ➽ ✲ . The mediator is not able to rewrite the query. Indeed, we have

Furthermore, we have a local failure in query evaluation when a mediator sends a rewritten query to related sources and receives at least an empty answer. This means that the case memory of the mediator is not updated. Typically, an information source has been removed from the system or changed its schema.

Example 4.7 Let us suppose that source ✒ ✖ has been (perhaps temporarily) removed, then the evaluation of the reformulated query in Example 4.4 fails. Indeed ✱ ◗ ❙ ③ ✞ ✟ ✡ ☞ ✆ ✞ ✢ ✤ ✦ ✒ ★ ✩ ✫ ✆ ✬ ✮ ✯ ➾ ✤ ① ✈ ② ➽ ✲ ⑥ ✝ ✱ ◗ ❙ ③ ✞ ✟ ✡ ☞ ✆ ✉ ★ ✡ ✩ ① ✍ ❹ ⑥ ✝ ✱ ◗ ❙ ③ ✞ ✟ ✡ ☞ ✆ ✞ ✟ ✡ ☞ ❹ ✏ ② ➪ ✤ ✩ ✆ ✬ ✮ ✯ ➶ ❾ ✚ ✚ ✲ ⑥ ✝ ✱ ◗ ❙ ③ ✞ ✟ ✡ ☞ ✆ ✞ ✢ ✤ ✦ ✒ ★ ✩ ✫ ✆ ✬ ✮ ✯ ✱ ➽ ✲ ⑥ ✝ ➹

5 Distributed Query Rewriting

Even if a local failure (in query reuse or evaluation) occurs, the distributed case-based reasoning has still a possibility of solving the problem by means of cooperation with other mediators and sources. Notice that this provides the system the most important way of learning. Indeed, if the query is reformulated, the new rewritten query and/or the new sources can be stored as a new case. In such a way the mediator can support dynamic information systems. Furthermore, it does not need to maintain consistent its case memory every time something changes, but only when a consumer sends a query that fails. Therefore, the distributed information system is not overloaded with consistency maintenance operations, that usually are time consuming. On the contrary, traditional mediation systems can only update mediated schema with expensive hand-made procedures.

Cooperation strategies can be classified according to three parameters: partners, queries, and answers. In the following we describe such strategies, we also analyse them (from a theoretical point of view), since the choice of the right cooperation strategy is crucial for effectiveness and efficiency, and discuss the results.

Partners. When a mediator (say ❾ ) fails, it can cooperate with other mediators asking them to rewrite a query according to their own case memories. If they succeed, ❾ can store the result as a new case in its case memory. The mediators involved in this strategy can be all the mediators of the system, just mediators that have never been in touch with M, or mediators that successfully cooperated with ❾ in the past. The mediator ❾ can directly cooperate with information sources as well. This strategy can involve all the sources (it is very expensive), sources responsible of the local failure (this strategy takes into account changes of schemas), recently added sources (this strategy takes into account new sources), or the sources that successfully cooperated with ❾ in the past (when a user has a new information need, the application of this strategy supposes that the new need involves the same sources of the past). Each source classifies the query and returns the subsumed concepts. Let us analyse such strategies focusing on recall and precision ratios in order to evaluate the effectiveness of the strategy. We also evaluate the information redundancy that such strategies produce.

First, let us consider a mediator ❾ that cooperates with other mediators, sends them the original query, and asks for receiving a rewritten query. This strategy has a possible disadvantage that another mediator can send a wrong rewriting. This fact has harmful consequences on the precision, as stated by the following theorem.

Theorem 5.1 Let ❷ ✖ ⑩ ✆ ✆ ✆ ⑩ ❷ ❆ be ① information sources. Let ➴ be a view of ❷ ✖ ⑩ ✆ ✆ ✆ ⑩ ❷ ❆ . ➴ is represented as a casememory that does not change. Let ❾ , ➷ be two mediators such that ❾ interacts with ➷ when ❾ fails. Let ➬ ❆ ③ ❾ ⑥ be the case memory of ❾ after ① interactions with ➷ . Then

In the above theorem, ➬ ❆ ③ ❾ ⑥ denotes the case memory of the mediator ❾ (e.g. see Figure 2). ➴ denotes the information need of a given consumer, i.e., it is the schema to which ➬ ❆ ③ ❾ ⑥ must converge. Such a theorem states that when the mediator ➷ sends a rewriting that is part of ➴ the recall and the precision grow, otherwise the recall does not change and the precision decreases. This means that is crucial the choice of what and how many mediators to cooperate with. Another possible disadvantage of such a strategy is that asymptotically all the mediators may have the same case memory, i.e. this strategy produces a certain redundancy. This result is a consequence of the following theorem.

Theorem 5.2 Let ❾ , ➷ be two mediators such that ❾ interacts with ➷ when ❾ fails. Let ➬ ❆ ③ ❾ ⑥ be the case memory of ❾ after ① interactions with ➷ . Let ➬ ③ ➷ ⑥ be the case memory of ➷ such that it does not change while ➷ interacts with ❾ . Then

The above theorem states that the case memory of ❾ converges to the case memory of ➷ when ❾ cooperates with ➷ . This seems to suggest that when the mediator cooperates with other mediators it would directly ask data instead of the rewritten query. This would allow any mediator to maintain its expertise and avoid redundancy.

As a second strategy, let us consider a mediator ❾ that directly cooperates with information sources, sends them the original query, and receives the rewritten query (and eventually the data). This strategy guarantees a given consumer that the mediator ❾ converges to the consumer's information need. Indeed it is possible to prove the following theorem.

Theorem 5.3 Let ❷ ✖ ⑩ ✆ ✆ ✆ ⑩ ❷ ❆ be ① information sources. Let ➴ be a view of ❷ ✖ ⑩ ✆ ✆ ✆ ⑩ ❷ ❆ . ➴ is represented as a case memory that does not change. Let ❾ be a mediator such that ❾ interacts with ❷ ✖ ⑩ ✆ ✆ ✆ ⑩ ❷ ❆ when it fails. Let ➬ ❆ ③ ❾ ⑥ be the casememory of ❾ after ① interactions with ❷ ✖ ⑩ ✆ ✆ ✆ ⑩ ❷ ❆ . Then

Recall: ➮ ➱ ✃ ❆ ❐ ❒ ➳ ❈ ❅ ● ✺ ❮ ❰ ✺ ❝ ❍ a207 a208 ❍ ➳ ❈ ❅ ● ✺ a208 ❍ ✝ a210 Precision: ➮ ➱ ✃ ❆ ❐ ❒ ➳ ❈ ❅ ● ✺ ❮ ❰ ✺ ❝ ❍ a207 a208 ❍ ➳ ❈ ❅ ● ✺ ❮ ❰ ✺ ❝ ❍ ❍ ✝ a210

The above theorem states that the mediator will asymptotically satisfy the information need of a given consumer (denoted by ➴ ). Indeed, under the hypothesis that no name heterogeneity occurs (see Section 3), it is impossible that the source has wrong schemas. Therefore, the information source has either the right answer or no answer at all. This means that the choice of sources to cooperate with is crucial only for efficiency of the system, i.e. how fast the mediator's case memory converges to user's needs.

Example 5.1 In the situation of Example 4.7, let us suppose that the mediator chooses to look for new sources and cooperate with them. Let us suppose that ✒ ➻ is a new information source which contains ACM publications and has the following concepts in its schema:

a213 a214 a215 a216 ➝ a217 a218 a219 ➨ a220 a221 a222 a213 a215 a223 a219 a224 a225 a226 a227 a228 ➜ a229 a229 a230 ➢ a220 a231 a232 a234 ➞ a235 a218 a236 a223 a237 a219 a224 a225 a238 a239 a240 a241 a230 a213 a214 a215 a216 ➝ a214 ➞ a219 ➨ a220 a221 a222 a213 a215 a223 a219 a224 a225 a226 a227 a239 a243 a229 a229 a230 ➢ a220 a231 a232 a234 ➞ a235 a218 a236 a223 a237 a219 a224 a225 a238 a239 a240 a241 a230 a213 a214 a215 a216 ➝ a235 a218 a219 ➨ a220 a221 a222 a213 a215 a223 a219 a224 a225 a226 a227 ➥ ➜ a229 a229 a230 ➢ a220 a231 a232 a234 ➞ a235 a218 a236 a223 a237 a219 a224 a225 a238 a239 a240 a241 a230

The mediator decomposes the query ✂ ✓ and sends each component to ✒ ➻ . For example, when ✒ ➻ receives ✞ ✟ ✡ ☞ ✆ ✞ ✟ ✡ ☞ ❹ ✏ ② ➪ ✤ ✩ ✆ ✬ ✮ ✯ ➶ ❾ ➽ ✲ , it looks for maximally contained concepts and obtains ❾ ❑ ❆ ❿ ③ ✞ ✟ ✡ ☞ ✆ ✞ ✟ ✡ ☞ ❹ ✏ ② ➪ ✤ ✩ ✆ ✬ ✮ ✯ ➶ ❾ ➽ ✲ ⑩ ➁ ⑥ ✝ ✬ ✞ ✟ ✡ ☞ ✆ ✍ ④ ⑤ ✈ ★ ✫ ② ⑩ ✞ ✟ ✡ ☞ ✆ ✍ ④ ⑤ ✈ ★ ④ ❹ ⑩ ✞ ✟ ✡ ☞ ✆ ✍ ④ ⑤ ✈ ★ ✏ ② ✲ . When the mediator receives the answer, retains as new case:

a244 a220 a231 a232 a234 a219 a213 a214 a215 a245 a244 a220 a231 a232 a234 a219 a213 a214 a215 a216 ➝ a217 a218 a245 a220 a231 a232 a234 a219 a213 a214 a215 a216 ➝ a214 ➞ a245 a220 a231 a232 a234 a219 a213 a214 a215 a216 ➝ a235 a218 a246 a245 a244 ➟ a220 a231 a232 a234 a219 a213 a214 a215 a216 ➝ a217 a218 a245 a247 a248 ➡ a245 ➟ a220 a231 a232 a234 a219 a213 a214 a215 a216 ➝ a214 ➞ a245 a247 a248 ➡ a245 ➟ a220 a231 a232 a234 a219 a213 a214 a215 a216 ➝ a235 a218 a245 a247 a248 ➡ a246 a246

Queries. Cooperation strategies can also be classified according to queries. Indeed ❾ can send the query as received by the consumer (this is a strategy that takes into account the new user's need). It can send the retrieved query (if any), i.e. the problem returned by the retrieval function (this is a strategy that takes into account the need of maintaining consistent the mediator's case memory). Finally, the mediator can send the reformulated query (if any). In the latter case the "approximation of the solution grows", as stated by the following theorem.

Theorem 5.4 Let ✂ be the original query. Let ✂ ✚ a249 ❾ ❑ ❆ ❿ ③ ✂ ⑩ ➁ ⑥ be one of the past queries retrieved by ❾ . Let ❷ ★ ❹ ❝ ③ ✂ ✚ ⑥ be one of the reformulations of ✂ ✚ used by ❾ as rewriting of ✂ . Let ➷ be the mediator or source that cooperates with ❾ . Let ❷ ★ ❹ a212 ③ a251 ⑥ be the query rewritten by ➷ if ➷ receives a251 as input query. Then

As a consequence, the solution returned by ➷ is more distant from ✂ than ✂ ✚ when ❾ does not send the original query.

Cooperation strategies can also be classified depending on the fact that the query can be sent as it is or be decomposed in basic components. This second strategy is applicable since it is straightforward to prove that the following theorem holds when we use C-CLASSIC:

Theorem 5.5 Let ✂ ✖ ⑩ ✆ ✆ ✆ ⑩ ✂ ❆ be queries. Let ✂ ✝ ➼ ③ ✂ ✖ ⑩ ✆ ✆ ✆ ⑩ ✂ ❆ ⑥ be the user's query. Let ➷ be the mediator or source that cooperates with ❾ . Let ❷ ★ ❹ a212 ③ a251 ⑥ be the query rewritten by ➷ if ➷ receives a251 as input query. Then

The theorem above states that ❾ does not need to decompose a query before its sending, since the query is directly decomposed by partners. This suggests that decomposition is convenient (efficient) only if ❾ failed to reformulate / evaluate just some components of the query.

Answers. Finally, cooperation strategies can be classified according to answers. ❾ can ask for rewriting the query. Its goal is to update its case memory with a rewritten query obtained from its collaborators. ❾ can also ask for data that answer the query. In such a situation, it stores in the case memory the addresses of the mediators/sources that answered. We can analyse such strategies depending on partners. Table 1 reports the results of cooperation with only one agent. We assume that such an agent (say a source ❷ or a mediator ➷ ) does not change while the strategy is in progress. We also suppose that ➷ has ⑨ ✂ ⑩ ❷ ★ ❹ a252 ③ ✂ ⑥ ⑩ ❷ ❺ in its case memory. For each strategy, Table 1 reports the new case that ❾ stores in its case memory, the set of instances related to the reformulation, the number of messages to obtain instances of ✂ (when ❾ receives ✂ the first time and the next time), and the results about redundancy (see Theorem 5.2). When we consider cooperation with mediators, it seems more efficient to ask for a rewriting, since ❾ interacts with ➷ only the first time, the next time ❾ directly interacts with ❷ . On the other hand, the strategy of requiring data does not produce redundancy, even if it is less efficient. Notice that, for what concerns such evaluation parameters, the strategy of cooperating with sources requiring data seems to be the most appropriate when the number of sources is comparable to the number of mediators.

6 Conclusions

We considered the problem of rewriting queries by means of distributed case-based reasoning. As far as we know, this is a novel approach. This allows us to have dynamic mediated schemas instead of static ones. We showed that a real dynamic mediator is obtained by means of distributed query reformulation, i.e., cooperation with other mediators and sources. Thanks to this approach, the mediator is able to be updated when sources and consumers are added/removed or change their schemas/needs. This operation is performed only when a consumer sends a query that fails and not every time something changes. This allows us to avoid of overloading the distributed information system with expensive consistency maintenance operations. In distributed case-based reasoning, the choice of the right cooperation strategy is crucial. We hinted several possible strategies and discussed their advantages. From such an analysis arises that we can obtain good results for effectiveness and efficiency when a mediator directly cooperates with information sources when the number of information sources is small. Otherwise, the most efficient strategy is the cooperation with other mediators. Finally, notice that the choice of C-CLASSIC is appropriate since the algorithm complexity for query retrieval and reuse is polynomial.

Acknowledgements

We thank J. Mylopoulos for suggestions and useful discussions about the topics presented in this paper. We also thank P. Coupey and S. Gianfelici that have participated to the development of the C-CLASSIC reasoner.