The coDBz project (http://www.inf.unibz.it/∼franconi/coDBz/) studies the problem of efficient query processing in a network of databases, possibly with different schemas (ontologies), interconnected by means of mapping rules at the ontology level. In the coDBz system the case of GLAV mapping rules with conjunctive queries is considered, possibly containing existential variables both in the body and in the head. Each node can be queried locally for data, which the node can fetch from its neighbours if a mapping rule is involved. There are no restrictions on the topology of the network, in particular, cyclic networks are allowed. Dynamic networks are supported: if nodes and mapping rules appear or disappear during the computation, the query processing will eventually terminate with a sound and complete result. We have studied and evaluated optimisations of the query processing algorithm based on dynamic exploration and analysis of the topology of the network. The coDBz system employs a robust algorithm polynomial both in the size of the (dynamic) network and in the size of the global data. We claim that this approach to ontology-based integration is more suited for inter-operability of information sources in a business scenario, due to its data-centric approach as opposed to the constraint-centric approach of classical approaches to information integration (see Section 3).
Our proposal shares the spirit of the Piazza system [Halevy et al., 2003; Tatarinov and Halevy, 2004]. The vision of the Piazza peer data management system (PDMS) project is to provide semantic mediation between an environment of autonomous and heterogeneous peers, each with its own schema. Rather than requiring the use of a single, uniform, centralised mediated ontology to share data between peers, Piazza allows peers to define schema mappings between pairs of peers (or among small subsets of peers). In turn, transitive relationships among the schemas of the peers are exploited so the entire resources of the PDMS can be used. The original Piazza system is limited in the fact that it does not allow complex mapping rules (i.e., inter-ontology mappings must be safe rules with atomic heads), it does not allow for fully cyclic mapping rules, and it does not allow for dynamic networks (i.e., networks where peers may join or leave anytime).
Together with the work presented in [Halevy et al., 2003; Tatarinov and Halevy, 2004], other researchers investigated the theoretical underpinnings of peer database management systems. The work presented in [Calvanese et al., 2004] proposes a logical analysis of the theory behind a PDMS, but it lacks a distributed algorithm: it assumes that nodes may exchange both data and mappings, so that only the query node will eventually evaluate the query answer in one go – there is no distributed computation and the network may be flooded with data. The work presented in [Bernstein et al., 2002; Serafini et al., 2003] proposes a very general theoretical framework for PDMS, with expressive schema mapping languages (up to first order logic) and constraint languages (up to first order logic) applied to single peers. However, no computational characterisation is given. The paper [Serafini and Ghidini, 2000] describes a local algorithm to compute query answers in a P2P network, but it allows only safe schema mapping rules with atomic heads. The algorithm is exponential in the number of nodes and it floods the network with messages during query evaluation if the network contains cycles. None of the above PDMS approaches supports dynamic networks: in the case of peers joining or leaving the network during the computation, neither the termination of the query answering algorithm nor the properties of the possible query answer are guaranteed.
Starting from the general ideas sketched above, the paper [Franconi et al., 2003] provides the foundations of the coDBz system, and it introduces a general logical and computational characterisation of networks of autonomous sources, interconnected by means of inter-ontology mapping rules between pairs of peers. This paper defines a precise model-theoretic semantics of a PDMS (fully compatible with Piazza and the other PDMS framework presented above), it characterises the general computational properties for the problem of answering queries to a PDMS, and it presents tight complexity bounds and basic distributed procedures for important special cases. The paper [Franconi et al., 2004b] analyses a distributed procedure for the problem of local database update in a network of database peers. The problem of local database update is different from the problem of query answering. Given a PDMS, the answer to a local query may involve data that is distributed over the network, and this may require the participation of many nodes at query time. On the other hand, given a PDMS, a “batch” update algorithm will be such that all the nodes consistently and optimally propagate all the relevant data to their neighbours, allowing for subsequent local queries to be answered locally within a node, without fetching data from other nodes at query time. The update problem has been considered important by the P2P literature; most notably, recent papers focused on the importance of data exchange and materialisation for a stable P2P network [Fagin et al., 2003; Daswani et al., 2003]. The papers [Franconi et al., 2004c] introduce a basic distributed algorithm for query answering in a PDMS, together with the a first prototypical implementation of coDBz in the JXTA framework. The proposed algorithm is polynomial in data complexity, but it is still exponential in the dimension of the network. These papers consider a network of databases, possibly with different schemas, interconnected by means of mapping rules having conjunctive queries both in the body and in the head, with possibly existential variables both in the body and in the head (called GLAV rules) as first suggested by [Calvanese et al., 2004]. Each node can be queried with a conjunctive query over its schema, for data which the node can possibly fetch from its neighbours using appropriate mapping rules. Unrestricted cyclic topologies of the network are allowed. The proposed PDMS framework is robust in the sense that it supports dynamic networks: even if nodes and mapping rules appear or disappear during the computation, the proposed algorithm will eventually terminate with a provably sound and complete result.
Our latest contribution on the foundations of coDBz (submitted) is to extend the results presented in [Franconi et al., 2003; 2004b; 2004c], by introducing and evaluating experimentally a fully distributed query processing algorithm for a PDMS, which is polynomial both in data complexity and in the dimension of the network. As it comes out from the comparison with the unoptimized version of the algorithm, the new version of the algorithm outperforms the unoptimized one exponentially with respect to the size of the network for highly connected networks. We have shown that knowledge of network structure may help to significantly improve the efficiency of query processing, both in the number of exchanged messages and in the time to get a complete answer. However, our optimization methods do not require advance knowledge of this topology, since the topology is discovered during query processing. The contributions of this paper include a definition of soundness and completeness for query processing in dynamically changing networks. Moreover, the query answering algorithm is shown to be efficient with respect to changes of the network. In particular, when the size of the change during query processing is sensibly less than the size of the network itself, query processing time is comparable to that of query processing in a stable network. The assumption that a change is small with respect to the size of whole network is reasonable for large scale networks. 3
Another line of research that is necessary to compare with the PDMS framework
proposed here, is the standard classical logic-based data integration technology,
which has been summarised in [Lenzerini, 2002]; successful examples of
classical logic-based data integration technology are the Information Manifold [Kirk
et al., 1995] and Tsimmis [Garcia-Molina et al., 1997]. The main difference is
in the role of the inter-ontology mapping rules between nodes: in a PDMS a
schema mapping rule is intended for data migration and transformation between
neighbours, as opposed to the role of global logical constraints in classical data
integration systems. It can be proved