Val Tannen, Susan B. Davidson and Scott Harker

8.1 APPROACH

A number of other techniques have also been developed over the past 11 years in response to the DOE challenge, including link-driven federations and warehouses. In a link-driven federation, users start by extracting entries of interest at one data source and then hop to other related data sources via Web links that have been explicitly created by the developers of the system. The Sequence Retrieval System (SRS) [11] presented in Chapter 5, LinkDB [12], and GeneCards [13] are examples of this approach. While the federation approach is easy to use, especially for novices, it does not scale well: When a new data source is added to the federation, connections between its entries and entries of all existing federation data sources must be added; this is commonly referred to as the N² problem. Furthermore, if users are interested in a join between two data sources in the federation, they must manually perform the join by clicking on each entry in the first data source and following all connections to the second data source.⁴ In contrast, a join can be expressed in a single high-level query in a view or warehouse integration strategy. In general, the query languages supporting view or warehouse integration approaches are much more powerful and allow arbitrary restructuring of the retrieved data.

A warehouse strategy creates a central repository of information and annotations. One such example is the Genomics Unified Schema (GUS) [14], which integrates and adds value to data obtained from GenBank/EMBL/DDBJ, dbEST, and Swiss-Prot (and others) and contains annotated nucleotide (dioxyribonucleic acid [DNA], ribonucleic acid [RNA]), and amino acid (protein) sequences. Note that view integration systems can also be used to create warehouses, which are instantiations of the global schema. The advantage of a warehouse approach over a view integration is one of speed and reliability; because all data are local, delays and failures associated with networks can be avoided. Furthermore, there is greater control over the data. However, a warehouse is not dynamic: Not only must it be kept up-to-date with respect to the underlying data sources, but including a new data source or algorithm is time-consuming. A more extended discussion of the problems and benefits of the link, warehouse, and view integration approaches can be found in articles in the IBM Systems Journal and the Journal of Digital Libraries [14, 15]. K2 is a system for generating mediators. Mediators are middleware components that integrate domain-specific data from multiple sources, reducing and restructuring data to an appropriate virtual view [16]. A major benefit of mediation is the scalability and long-term maintenance of the integration systems structure.

Figure 8.3 is an example of how mediators can help the data integration task. In this example, each of the boxes represents a machine on which a copy of K2 is used to provide a mediator for some local, as well as external, data sources and views. Mediator 1 resides behind a company firewall and was built to integrate data from a local database and local copies of Swiss-Prot and GenBank, accessed through SRS, with the application program BLAST. Mediator 2 was then built outside the firewall to integrate data from some external data sources—PubMed and a patent database, which can only be accessed through a Web interface. An external copy of PubMed was used due to its size and the fact that the most recent version was always needed. Mediator 3 was then built within the company firewall to integrate data from Mediators 1 and 2, and Mediator 1 was enlarged to integrate data from Mediator 3.

K2 (together with Tsimmis [17]) distinguishes itself among approaches based on mediation in that it generates mediators starting from a concise, high-level description. This makes K2 especially appropriate for configurations in which many mediators are needed or in which mediators must be frequently changed due to instability in the data sources or in the client needs. Some of the salient features of K2’s mediation environment are:

The basic functionality of a K2-generated mediator is to implement a data transformation from one or more data sources to one data target. The component contains a high-level (in ODMG/ODL) description of the schemas (for sources and the target) and of the transformation (in K2MDL). From the target’s perspective, the mediator offers a view that, in turn, can become a data source for another mediator.

An overview of the K2 architecture is given in Figure 8.4. In this diagram, clients can issue OQL queries or other commands against an integration schema constructed using K2MDL. The queries are then translated to the K2 internal language using K2MDL and query translators. This internal language expression is then optimized and executed using data drivers to ship sub-queries to external data sources and return results.

The remainder of this chapter walks through the architecture by describing the data model, illustrating K2MDL and OQL, and briefly discussing the internal language, data drivers, query optimization, and user interfaces. The chapter closes with a discussion of scalability and impact.

8.2 DATA MODEL AND LANGUAGES

ODMG was founded by vendors of object-oriented database management systems and is affiliated with the Object Management Group (OMG), who created the Common Object Request Broker Architecture (CORBA). The ODMG standard has two main components: The first is ODL, a data definition language that is used to define data elements. ODL is an extension of CORBA’s Interface Definition Language (IDL). The second is OQL, an enhanced SQL92-like language that is used for querying. By building on these standards, K2 leverages the following features:

K2 uses ODMG’s ODL to represent the data sources to be integrated. It turns out that many biological data sources can be described as dictionaries whose keys are simple strings and whose entries are complex values.

A dictionary is simply a finite function. Therefore, it has a domain that is a finite set and associates to each element of the domain (called a key) a value (called an entry). The type of dictionary in ODL is denoted by dictionary<T1, T2> where T1 is the type of the keys and T2 is the type of the entries. In OQL, the entry in the dictionary, L, corresponding to the key, k, is denoted by L [k]. Because OQL has no syntax for the domain of a dictionary L, dom (L) is an addition to OQL for this purpose. Note that if L has type dictionary<T1, T2> then dom (L) has type set<Tl>.

Complex value data are built by arbitrarily nesting records (tuples); collections—such as sets, bags (multisets), and lists; and variants. Variants are pieces of data representing tagged alternatives (also known as tagged unions). To illustrate complex values (including variants), Figure 8.5 presents an ODL declaration for a class whose objects correspond to (parts of) Swiss-Prot entries. The attribute Ref returns complex values obtained by nesting sets, lists, records (struct in ODL), and variants, the latter identified by the keyword choice.

K2’s approach to data integration consists of two stages. In the first stage users specify data transformations between multiple sources and a single target. The target is virtual (unmaterialized) and is, in effect, a new view. The sources may consist of materialized data or virtual views that have been defined previously through similar data transformations.

In the second stage users formulate queries against the virtual views. OQL is an excellent vehicle for the second stage, but because it does not construct new classes as output, it is not expressive enough for the first stage. Hence, for defining sources-target transformations, K2 uses a new language, (K2MDL), which combines the syntax of ODL and OQL to express high-level specifications of middleware components called mediators, as explained previously. Some examples of K2MDL syntax are in the next section.

The rich type system used in K2 has allowed us to model a large range of practical data sources in a transparent and friendly manner.

8.3 AN EXAMPLE

The K2 approach is illustrated with an example where the target data could be called an ontology, that is, a schema agreed upon by a class of users. It shows how a mediator generated by K2 could implement it in terms of standard data sources. Consider the following data description, which is given in ODL syntax:⁵

Data about proteins is recorded using a Swiss-Prot accession number, a recommended name, a set of alternate names, the protein sequence and its length, and a set of references to the genes that code for the protein. Data about genes consists of the name of the gene, the name of the organism from which it comes, the location of the gene in the genome, and a reference to the protein for which it codes. While most of our attributes have simple values, strings, and integers, alternateNames is a set of strings and location is a record. The schema also specifies that hasSource in Protein and hasProduct in Gene are more than just attributes; they form a relationship between the extents of the two classes and are inverses. This means that the two following statements are validated:

Now assume that the data about proteins and genes reside in (for illustration purposes) four materialized data sources: Swiss-Prot, Orgs, Genes, and ProteinSynonyms. Swiss-Prot contains some protein data, which can be accessed through an SRS driver that presents an object-oriented schema (i.e., a class). Orgs and Genes contain organism and gene data, respectively, in two relations (in the same or in separate relational databases). The SQL data description is given here for these relations, but in fact K2 uses an equivalent description in ODL syntax, based on the observation that relations are simply sets of records. Finally, a Web-based data source contains protein name synonyms and is modeled as a dictionary.

The K2MDL description of the integration and transformation that is performed when the sources Swiss-Prot, Orgs, Genes, and ProteinSynonyms are mapped into the ontology view. K2MDL descriptions look like the ODL definition in the ontology, enhanced with OQL expressions that compute the class extents, the attribute values, and the relationship connections (a related idea appears in a paper from the 1991 International Conference on Management of Data [18]).

The definition of the class Protein as a K2MDL classdef starts with an OQL statement that shows how to compute the extent proteins of this class by collecting the accession numbers from SwissProt. The elements of the extent are used as object identifiers (OIDs) for the objects in the class. The rest of the definition shows how to compute the value of each attribute for a generic object identified by the OID (denoted by the keyword self). The OQL function element (c) extracts the unique element of the collection, c, when c is a singleton, and raises an exception otherwise.

Note, for example, the computation of the value of the attribute alternateNames. For an object identified by self, find the Swiss-Prot entry, s, whose accession number is self, then use the description of s as a key in the dictionary ProteinSynonyms. The entry retrieved from the dictionary ProteinSynonyms [s.Description] is a set of records. Select from this set the records with names in English and collect those names into the answer. The value of the attribute is a set of strings. A further query posed against the class Protein may, for example, select objects whose alternateNames attribute contains a given synonym.

This example illustrates that relatively complex integrations and transformations can be expressed concisely and clearly, and can be easily modified.

8.4 INTERNAL LANGUAGE

The key to making ODL, OQL, and K2MDL work well together is the expressiveness of the internal framework of K2, which is based on complex values and dictionaries. ODL classes with extents are represented internally as dictionaries with abstract keys (the object identities). This framework opens the door to interesting optimizations that make the approach feasible.

The K2 internal language is organized by its type structure. There are base types such as string and number; record and variant types; collection types, namely sets, bags, and lists; and dictionary types. For each type construction there are two classes of operations: constructors, such as empty set and set union, and deconstructors, such as record field selection. The operations for collection types are inspired from the theory of monads [19] and are outlined in an article in Theoretical Computer Science [20]. For details specific to aggregates and collection conversions see Proceedings of the 7th International Conference on Category Theory and Computer Science [10]; the operations on dictionaries are described in the 1999 Proceedings of the International Conference on Database Theory [9].

The internal language derives its expressiveness from its flexibility. The primitives are chosen according to the principle of orthogonality, which says that their meaning should not overlap and that one should not be able to simulate one primitive through a combination of the others. This produces a language with fewer, but better understood, primitives. As an example, consider the following basic query statement:

This translates internally into

where SetU (x in S) T (x) is the set deconstructor suggested by the theory of monads and sngset (e) is a singleton set (i.e., the set with just one element, e).

The semantics of the set deconstructor is that of the union of a family of sets. For example, if S = {a₁, …, a_n} then

This approach increases the overall language expressiveness by allowing any type-correct combination of the primitives (the language is fully compositional). At the same time it provides a systematic approach to the identification of optimization transformations by yielding an equational theory for the internal language. The formulas of such a theory are equalities between equivalent parts of queries, and they are used for rewriting queries in several of the stages of the optimizer. Finally, K2 exploits known efficient physical algorithms for operations such as joins by automatically identifying within queries the groups of primitives that compute these operations.

8.5 DATA SOURCES

K2 maps data from external sources into its internal language, as described previously. K2 also has a notion of functions, which are used to provide access both to stand-alone applications such as BLAST (a sequence similarity package) and to pre-defined and user-defined data conversion routines. This flexibility allows K2 to represent most data sources faithfully and usefully.

K2 accesses external information through data drivers. This is an intermediate layer between the K2 system proper and the actual data sources. There are two kinds of drivers in K2: those that are tightly integrated with the server and those that are more loosely connected.

Integrated data drivers (IDDs) are created by extending the two abstract Java classes that form K2’s driver API. The IDDs export a set of entry points to K2, connect to the data source, send queries to it, receive results from it, and package the results for use in the rest of the K2 system. The tight coupling of IDDs with the K2 system minimizes the overhead associated with connecting to the data source and allows for additional optimizations. K2 can also cache results of queries sent to the IDDs to improve overall speed.

K2 comes with an IDD that can connect to any relational database system that implements Sun’s JDBC API. A Sybase-specific IDD is also available, which takes advantage of some features of Sybase that are not available through JDBC. Oracle- and MySQL-specific versions are currently under development. To connect to a new relational database that supports JDBC, one merely needs to add the connection information to a configuration file, and K2 will automatically expose the underlying schema for querying. When the underlying schema changes, the K2 administrator must restart the IDD so it can rediscover the new schema. A procedure for automatically detecting and rediscovering schema changes is planned as a future enhancement.

Another IDD provided with K2 makes use of the World Wide Web Wrapper Factory (W4F), also developed at the University of Pennsylvania.⁶ W4F is a toolkit for the generation of wrappers for Web sources. New wrappers can easily be generated using W4F’s interface and can then be converted automatically to K2 drivers. Changes to the format of Web sources are partly handled by W4F’s declarative wrapper specification language. Large format changes require human intervention to re-define and re-generate wrappers.

A very powerful feature of K2 is its ability to distribute query execution using its IDD for Java RMI. This IDD can make an RMI connection to a remote K2 server and send it part of the local query for processing. Therefore, all that is required to connect to the remote K2 server and start distributing queries is a change to the local K2 configuration file.

Sometimes it is difficult to develop an IDD for a new type of data source. For example, to treat a group of flat files as a data source it is often easier to write a Perl script to handle the string manipulations involved rather than implementing them in Java, as would be required in an IDD. In fact, some data sources cannot be accessed at all from Java but only through APIs in other languages. To handle this, K2 has an IDD called the PipeDriver that does not connect to the data source directly, but to a decoupled data driver (DDD).

A DDD is a simple, stand-alone application, written in any language at all, that accepts queries through its standard input stream and writes results to its standard output. The PipeDriver takes care of sending queries to the DDD and converting the results into K2’s internal representation. It can run multiple DDDs at once to take advantage of parallelism, and it can make use of the caching mechanism built into IDDs, all of which simplifies the job of the DDD writer.

The DDD is responsible for establishing a connection to the data source (often nothing is required in this step), telling the PipeDriver it has made the connection, and waiting for a query to come in. When the DDD receives a query, it extracts the appropriate result from the data source and writes it out in a simple data exchange format. It then returns to waiting for the next query. This loop continues until the K2 server is brought down, at which point the PipeDriver tells the DDD to terminate.

DDDs have been written to connect with SRS, KEGG, and BLAST, as well as a number of Web-based sources. The time it takes to create a new DDD depends greatly on the capabilities of the data source for which it is being written and on how much intelligence is to be built into the DDD. For example, it only takes an hour or two to write a Perl script to connect to a simple document storage system; the script must be written to receive an ID, retrieve the document, and print it out in K2’s exchange format, taking into account any error conditions that might occur.

However, the DDD writer has the flexibility to create special-purpose DDDs of any complexity. One DDD has been written that performs queries over a collection of documents that come from a remote Web site. This DDD maintains a local disk cache of the documents to speed access. It is responsible for downloading new versions of out-of-date documents, taking concurrency issues into account, and parsing and indexing documents on the fly. It also supports a complex language for querying the documents and for retrieving structured subsets of their components. This DDD was written over the course of two weeks and has been expanded periodically since.

8.6 QUERY OPTIMIZATION

K2 has a flexible, extensible query optimizer that uses both rewrite rules and a cost model. The rewrite rules are used to transform queries into structurally minimal forms whose execution is always faster than the original query; this is independent of the nature of the data. On the other hand, a cost model uses information about the nature of the data, such as the size of the data sets, selectivity of joins, available bandwidth, and latency of the data sources. The cost information is used to choose between minimal queries that are incomparable with respect to the rewrite rules.

After translating the query into an abstract syntax tree, which K2 uses to represent queries internally, it is manipulated by applying a series of rewrite rules. This is where the bulk of K2’s optimization work is done.

First, a collection of rules is applied that simplifies the query by taking pieces expressed using certain kinds of tree nodes and replacing them with others. This reduces the number of types of nodes needed to deal with, thus reducing the number and complexity of the rewrite rules that follow.

Next, the query is normalized. Normalization rules include steps such as taking a function applied to a conditional structure and rewriting it so the function is applied to each of the expressions in the condition. Another normalization rule removes loops that range over collections known to be empty. Repeated application of the normalization rules, which currently number more than 20, reduces the query to a minimal, or normal, form.

A final set of rewrite rules are then applied to the normalized query. These rules include parallelizing the scanning of external data sources and pushing selections, projections, and joins down to the drivers where possible.

Even after all the rewrite rules have been applied, there may still be room for further optimization. In particular, a query may have a family of minimal forms rather than a single one. To choose between the minimal forms, the expected execution time of each version of the query is estimated using a cost model, and the fastest query form is chosen. The current cost model is still in the development stage. While it is functional and works well most of the time, it does not always choose the optimal form of the query.

8.7 USER INTERFACES

K2 has been developed using a client–server model. The K2 server listens for connections either through a socket or through Java RMI. It is easy to develop a client that can connect to K2 through one of these paths, issue queries, and receive results. Three basic clients come with K2: a text-based client, an RMI client, and one that runs as a servlet.

The interactive, text-based client connects to a K2 server through a socket connection. It accepts a query in OQL through a command-line-style interface, sends it to the server, gets the result back as formatted text, and displays it; then it waits for the next query to be entered. This simple client generally is used to test the socket connection to K2 and to issue simple queries during the development process. It is not intended to be an interface for end users.

The other type of user connection is through RMI. These connections are capable of executing multiple queries at once and can halt execution of queries in progress. This is the connection method that K2 servers use to connect to other K2 servers to distribute the execution of a query.

There is a client that makes an RMI connection to a K2 server with administrator privileges. The server restricts these connections to certain usernames connecting from certain IP addresses and requires a password. Currently, an administrator can examine the state of the server, add and remove connections to individual drivers, stop currently running queries, disconnect clients, and bring the server to a state where it can be stopped safely. More functionality is planned for administrators in the future.

A client that runs as a servlet is also included with K2. Using code developed at the Computational Biology and Informatics Laboratory (at the University of Pennsylvania), this servlet allows entry of ad hoc K2 queries and maintains the results for each username individually.

A major component of any user interface is the representation of the data to the user. As exemplified previously, a user (perhaps one serving a larger group) can define in K2MDL a transformed/integrated schema for a class of users and applications and can specify how the objects of this schema map to the underlying data sources. Users of this schema (called an ontology by some) can issue vastly simplified queries against it, without knowledge of the data sources themselves.

8.8 SCALABILITY

In theory, the K2 system can be used to interconnect an arbitrarily large number of data sources. In practice, the system has been configured with up to 30 data sources and software packages, including GUS, PubMed, MacOStat, GenBank, Swiss-Prot, BLAST, KEGG, and several relational databases maintained in Oracle, Sybase, and MySQL. Even when querying using this configuration, however, it has been rare to access more than five data sources and software packages in the same query.

The primary obstacles to scaling K2 to a larger system are (1) writing data drivers to connect to new data sources and (2) peak memory consumption. The difficulty of writing data drivers to external data sources has been mitigated to some extent by the fact that they are type specific rather than instance specific. For example, once an Oracle driver is written, it can be used for any Oracle data source. On the other hand, an AceDB driver must take into account the schema of the AceDB source and is therefore not generic. Drivers are also relatively simple in K2 because they merely perform data translation. Any complex, semantic transformations are performed by K2MDL code, which is high-level and therefore more maintainable.

While peak memory consumption has not as yet been an issue for the queries handled by K2 in the past, it could become a problem as applications become larger. K2 provides a means of limiting the number of queries it will run simultaneously and the number of data source connections it will maintain. This allows an administrator to tune the system to the capabilities of the machine on which it is running.

Because K2 is a view integration environment, it does not store any data locally; however, it may need to store intermediate results for operations that cannot be streamed (i.e., processed on the fly). At present, intermediate results are stored in main memory.

Examples of operations that cannot be streamed include sorting, set difference, nesting, and join. For example, when the difference of two data sets is taken, no output can be issued until both data sets are read; one of the data sets may have to be cached while the other is streamed and the difference is calculated. Similarly, although a join output can be produced as soon as a match is found between elements of the two data sets, data cannot be discarded until it is known not to match any future input from the other data set (see two International Conference on the Management of Data (SIGMOD) articles [21, 22] for discussions of implementations of operators in streaming environments). Thus, when data sets are large, these operations may need to cache temporary results in persistent memory. Such techniques are not currently part of the K2 system and require futher development.

Another difficulty of scaling to an arbitrarily large environment is the sheer complexity of understanding what information is available. To mitigate this, smaller mediated components can be composed to form larger mediated components. Thus, users need not be aware of the numerous underlying data sources and software systems, but they can interact with the system through a high-level interface representing the ontology of data.

8.9 IMPACT

As with Kleisli, a tremendous enhancement in productivity is gained by expressing complicated integrations in a few lines of K2MDL code as opposed to much larger programs written in Perl or C++. What this means for the system integrator is the ability to build central client-server or mix-and-match components that interoperate with other technologies. Among other things, K2 provides:

K2 has been used extensively in applications within the pharmaceutical company GlaxoSmithKline. Some of the major benefits of the system exploited in these applications have been the ease with which ontologies can be represented in K2MDL and the ability to conveniently compose small mediators into larger mediators.

K2 was also used to implement a distributed genomic-neuroanatomical database. The system combines databases and software developed at the Center for Bioinformatics at the University of Pennsylvania—including databases of genetic and physical maps, genomic sequences, transcribed sequences, and gene expression data, all linked to external biology databases and internal project data (GUS [14])—with mouse brain atlas data and visualization packages developed at the Computer Vision Laboratory and Brain Mapping Center at Drexel University. The biological and medical value of the activity lay in the ability to correlate specific brain structures with molecular and physiological processes. The technological value of the activity was that K2 was ported to a Macintosh operating system environment (MacOSX), visualization packages were tightly integrated into the environment, and both an ethernet and a gigabit network were used in the application. The work was significantly facilitated by the fact that K2 is implemented in Java.

K2 now runs on Linux, Sun Solaris, Microsoft Windows, and Apple MacOS platforms.

8.10 SUMMARY

This chapter presented the K2 system for integrating heterogeneous data sources. K2 is general purpose, written in Java, and includes JDBC interfaces to relational sources as well as interfaces for a variety of special-format bioinformatics sources. The K2 system has a universal internal data model that allows for the direct representation of relational, nested complex value, object-oriented, information retrieval (dictionaries), and a variety of electronic data interchange (EDI) formats, including XML-based sources. The internal language features a set of equivalence laws on which an extensible optimizer is based. The system has user interfaces based on the ODMG standard, including a novel ODL–OQL combined design for high-level specifications of mediators.

ACKNOWLEDGMENTS

The authors would like to acknowledge the contributions of David Benton, Howard Bilofsky, Peter Buneman, Jonathan Crabtree, Carl Gustaufson, Kazem Lellahi, Yoni Nissanov, G. Christian Overton, Lucian Popa, and Limsoon Wong.

REFERENCES