Example 6.1.1: The query was to “find for each gene located on a particular cytogenetic band of a particular human chromosome as many of its non-human homologs as possible.” Basically, the query means “for each gene in a particular position in the human genome, find dioxyribonucleic acid (DNA) sequences from non-human organisms that are similar to it.”

In 1994, the main database containing cytogenetic band information was the Genome Database (GDB) [7], which was a Sybase relational database. To find homologs, the actual DNA sequences were needed, and the ability to compare them was also needed. Unfortunately, that database did not keep actual DNA sequences. The actual DNA sequences were kept in another database called GenBank [8]. At the time, access to GenBank was provided through the ASN.1 version of Entrez [9], which was at the time an extremely complicated retrieval system. Entrez also kept precomputed homologs of GenBank sequences.

So, the evaluation of this query needed the integration of GDB (a relational database located in Baltimore, Maryland) and Entrez (a non-relational database located in Bethesda, Maryland). The query first extracted the names of genes on the desired cytogenetic band from GDB, then accessed Entrez for homologs of these genes. Finally, these homologs were filtered to retain the non-human ones. This query was considered “impossible” as there was at that time no system that could work across the bioinformatics sources involved due to their heterogeneity, complexity, and geographical locations. Given the complexity of this query, the sSQL solution below is remarkably short.

The first three lines connect to GDB and map two tables in GDB to Kleisli. After that, these two tables could be referenced within Kleisli as if they were two locally defined sets, locus and eref. The next few lines extract from these tables the accession numbers of genes on Chromosome 22, use the Entrez function naget-homolog-summary to obtain their homologs, and filter these homologs for non-human ones. Notice that the from-part of the outer select-construct is of the form {select u …} H. This means that H is the entire set returned by select u …, thus allowing to manipulate and return all the non-human homologs as a single set H.

Besides the obvious smoothness of integration of the two data sources, this query is also remarkably efficient. On the surface, it seems to fetch the locus table in its entirety once and the eref table in its entirety n times from GDB (a naive evaluation of the comprehension would be two nested loops iterating over these two tables). Fortunately, in reality, the Kleisli optimizer is able to migrate the join, selection, and projections on these two tables into a single efficient access to GDB using the optimizing rules from a later section of this chapter. Furthermore, the accesses to Entrez are also automatically made concurrent.

Since this query, Kleisli and its components have been used in a number of bioinformatics projects such as GAIA at the University of Pennsylvania,⁴ Transparent Access to Multiple Bioinformatics Information Sources (TAMBIS) at the University of Manchester [11, 12], and FIMM at Kent Ridge Digital Labs [13]. It has also been used in constructing databases by pharmaceutical/biotechnology companies such as SmithKline Beecham, Schering-Plough, GlaxoWellcome, Genomics Collaborative, and Signature Biosciences. Kleisli is also the backbone of the Discovery Hub product of geneticXchange Inc.⁵

Example 6.3.1: The GenPept report is the format chosen by NCBI to represent information on amino acid sequence. While an amino acid sequence is a string of characters, certain regions and positions of the string, such as binding sites and domains, are of special biological interest. The feature table of a GenPept report is the part of the GenPept report that documents the positions of these regions of special biological interest, as well as annotations or comments on these regions. The following type represents the feature table of a GenPept report from Entrez [9].

It is an interesting type because one of its fields (#feature) is a set of records, one of whose fields (#anno) is in turn a list of records. More precisely, it is a record with four fields #uid, #title, #accession, and #feature. The first three of these store values of types num, string, and string respectively. The #uid field uniquely identifies the GenPept report. The #feature field is a set of records, which together form the feature table of the corresponding GenPept report. Each of these records has four fields: #name, #start, #end, and #anno. The first three of these have types string, num, and num respectively. They represent the name, start position, and end position of a particular feature in the feature table. The #anno field is a list of records. Each of these records has two fields #anno_name and #descr, both of type string. These records together represent all annotations on the corresponding feature.

In general, the types are freely formed by the syntax:

Here num, string, and bool are the base types. The other types are constructors and build new types from existing types. The types {t}, {|t|}, and [t] respectively construct set, bag, and list types from type t. The type (l₁ : t₁, …, l_n : t_n) constructs record types from types t₁, …, t_n. The type <l₁ : t₁, …, l_n : t_n> constructs variant types from types t₁, …, t_n. The flat relations of relational databases are basically sets of records, where each field of the record is a base type; in other words, relational databases have no bags, no lists, no variants, no nested sets, and no nested records. Values of these types can be represented explicitly and exchanged as follows, assuming that the instances of e are values of appropriate types: (l₁ : e₁, …, l_n : e_n) for records; <l : e> for variants; {e₁, …, e_n} for sets; {|e₁, …, e_n|} for bags; and [e₁, …, e_n] for lists.

Example 6.3.2: Part of the feature table of GenPept report 131470, a tyrosine phosphatase 1C sequence, is shown in the following.

The particular feature goes from amino acid 0 to amino acid 594, which is actually the entire sequence, and has two annotations: The first annotation indicates that this amino acid sequence is derived from a mouse DNA sequence. The second is a cross reference to the NCBI taxonomy database.

The schemas and structures of all popular bioinformatics databases, flat files, and software are easily mapped into this data model. At the high end of data structure complexity are Entrez [9] and AceDB [18], which contain deeply nested mixtures of sets, bags, lists, records, and variants. At the low end of data structure complexity are the relational database systems [17] such as Sybase and Oracle, which contain flat sets of records. Currently, Kleisli gives access to more than 60 of these and other bioinformatics sources. The reason for this ease of mapping bioinformatics sources to Kleisli’s data model is that they are all inherently composed of combinations of sets, bags, lists, records, and variants. Kleisli’s data model directly and naturally maps sets to sets, bags to bags, lists to lists, records to records, and variants to variants without having to make any (type) declaration beforehand.

The last point deserves further consideration. In a dynamic, heterogeneous environment such as that of bioinformatics, many different database and software systems are used. They often do not have anything that can be thought of as an explicit database schema. Further compounding the problem is that research biologists demand flexible access and queries in ad hoc combinations. Thus, a query system that aims to be a general integration mechanism in such an environment must satisfy four conditions. First, it must not count on the availability of schemas. It must be able to compile any query submitted based solely on the structure of that query. Second, it must have a data model that the external database and software systems can easily translate to without doing a lot of type declarations. Third, it must shield existing queries from evolution of the external sources as much as possible. For example, an extra field appearing in an external database table must not necessitate the recompilation or rewriting of existing queries over that data source. Fourth, it must have a data exchange format that is straightforward to use so it does not demand too much programming effort or contortion to capture the variety of structures of output from external databases and software.

Three of these requirements are addressed by features of sSQL’s type system. sSQL has polymorphic record types that allow to express queries such as:

which defines a function that returns names of people in R earning more than $1000. This function is applicable to any R that has at least the name and the salary fields, thus allowing the input source some freedom to evolve.

In addition, sSQL does not require any type to be declared at all. The type and meaning of any sSQL program can always be completely inferred from its structure without the use of any schema or type declaration. This makes it possible to plug in any data source logically without doing any form of schema declaration, at a small acceptable risk of run-time errors if the inferred type and the actual structure are not compatible. This is an important feature because most biological data sources do not have explicit schemas, while a few have extremely large schemas that take many pages to write down—for example, the ASN.l schema of Entrez [1]—making it impractical to have any form of declaration.

As for the fourth requirement, a data exchange format is an agreement on how to lay out data in a data stream or message when the data is exchanged between two systems. In this context, it is the format for exchanging data between Kleisli and all the bioinformatics sources. The data exchange format of Kleisli corresponds one-to-one with Kleisli’s data model. It provides for records, variants, sets, bags, and lists; and it allows these data types to be composed freely. In fact, the data exchange format completely adopts the syntax of the data representation described earlier and illustrated in Example 6.3.2. This representation has the interesting property of not generating ambiguity. For instance, a set symbol { represents a set, whereas a parenthesis (denotes a record. In short, this data exchange format is self describing. The basic specification of the data exchange format of Kleisli is summarized in Figure 6.2. For a more detailed account, please see Wong’s paper on Kleisli from the 2000 IEEE Symposium on Bioinformatics and Bio-engineering [19].

A self-describing exchange format is one in which there is no need to define in advance the structure of the objects being exchanged. That is, there is no fixed schema and no type declaration. In a sense, each object being exchanged carries its own description. A self-describing format has the important property that, no matter how complex the object being exchanged is, it can be easily parsed and reconstructed without any schema information. The ISO ASN.1 standard [20] on open systems interconnection explains this advantage. The schema that describes its structure needs to be parsed before ASN.1 objects, making it necessary to write two complicated parsers instead of one simple parser.

Example 6.4.1: The query below “extracts the titles and features of those elements of a data source DB whose titles contain ‘tyrosine’ as a substring.”

This query is a simple project-select query. A project-select query is a query that operates on one (flat) relation or set. Thus, the transformation such a query can perform is limited to selecting some elements of the relation and extracting or projecting some fields from these elements. Except for the fact that the source data and the result may not be in first normal form, these queries can be expressed in a relational query language. However, sSQL can perform more complex restructurings such as nesting and unnesting not found in SQL, as shown in the following examples.

Example 6.4.2: The following query flattens the source DB completely. 12s is a function that converts a list into a set.

The next query demonstrates how to express nesting in sSQL. Notice that the entries field is a complex object having the same type as DB.

The next couple of more substantial queries are inspired by one of the most advanced functionalities of the EnsMart interface of the EnsEMBL system [21].

Example 6.4.3: The feature table of a GenBank report has the type below. The field #position of a feature entry is a list indicating the start and stop positions of that feature. If the feature entry is a CDS, this list corresponds to the list of exons of the CDS. The field #anno is a list of annotations associated with the feature entry.

Given a set DB of feature tables of GenBank chromosome sequences, one can extract the 500 bases up stream of the translation initiation sites of all disease genes—in the sense that these genes have a cross reference to the Online Mendelian Inheritance of Man database (OMIM)—on the positive strand in DB as below.

Similarly, one can extract the first exons of these same genes as follows:

These two example queries illustrate how a high-level query language makes it possible to extract very specific output in a relatively straightforward manner.

The next query illustrates a more ambitious example of an in silico discovery kit (ISDK). Such a kit prescribes experimental steps carried out in computers very much like the experimental protocol carried out in wet-laboratories for a specific scientific investigation. From the perspective of Kleisli, an in silico discovery kit is just a script written in sSQL, and it performs a defined information integration task very similar to an integrated electronic circuit. It takes an input data set and parameters from the user, executes and integrates the necessary computational steps of database queries and applications of analysis programs or algorithms, and outputs a set of results for specific scientific inquiry.

Example 6.4.4: The simple in silico discovery kit illustrated in Figure 6.3 demonstrates how to use an available ontology data source to get around the problem of inconsistent naming in genes and proteins and to integrate information across multiple data sources. It is implemented in the following sSQL script.⁶ With the user input of gene name G, the ISDK performs the following tasks: “First, it retrieves a list of aliases for G from the gene nomenclature database provided by the Human Genome Organization (HUGO). Then it retrieves information for diseases associated with this particular protein in OMIM, and finally it retrieves all relevant references from MEDLINE.”

For instance, this query get-info-by-genename can be invoked with the transcription factor CEBPB as input to obtain the following result.

Such queries fulfill many of the requirements for efficient in silico discovery processes: (1) Their modular nature gives scientists the flexibility to select and combine specific queries for specific research projects; (2) they can be executed automatically by Kleisli in batch mode and can handle large data volumes; (3) their scripts are re-usable to perform repetitive tasks and can be shared among scientific collaborators; (4) they form a base set of templates that can be readily modified and refined to meet different specifications and to make new queries; and (5) new databases and new computational tools can be readily incorporated to existing scripts.

The flexibility and power shown in these sSQL examples can also be experienced in Object-Protocol Model (OPM) [22] and to a lesser extent in DiscoveryLink [23]. With good planning, a specialized data integration system can also achieve great flexibility and power within a more narrow context. For example, the EnsMart tool of EnsEMBL [21] is a well-designed interface that helps a non-programmer build complex queries in a simple way. In fact, an equivalent query to the first sSQL query in Example 6.4.3 can be also be specified using EnsMart with a few clicks of the mouse. Nevertheless, there are some unanticipated cases that cannot be expressed in EnsMart, such as the second sSQL query in Example 6.4.3.

While the syntactic basis for sSQL is SQL, its theoretical inspiration came from a paper by Tannen, Buneman, and Nagri [24] where structural recursion was presented as a query language. However, structural recursion presents two difficulties. The first is that not every syntactically correct structural recursion program is logically well defined [25]. The second is that structural recursion has too much expressive power because it can express queries that require exponential time and space.

In the context of databases, which are typically very large, programs (queries) are usually restricted to those that are practical in the sense that they are in a low complexity class such as LOGSPACE, PTIME, or TC⁰. In fact, one may even want to prevent any query that has greater than O(n × log n) complexity, unless one is confident that the query optimizer has a high probability of optimizing the query to no more than O(n × log n) complexity. Database query languages such as SQL, therefore, are designed in such a way that joins are easily recognized because joins are the only operations in a typical database query language that require O(n²) complexity if evaluated naively.

Thus, Tannen and Buneman suggested a natural restriction on structural recursion to reduce its expressive power and to guarantee it is well defined. Their restriction cuts structural recursion down to homomorphisms on the commutative idempotent monoid of sets, revealing a telling correspondence to monads [15]. A nested relational calculus, which is denoted here by NRC, was then designed around this restriction [16]. NRC is essentially the simply typed lambda calculus extended by a construct for building records, a construct for decomposing records by field selection, a construct for building sets, and a construct for decomposing sets by means of the restriction on structural recursion. Specifically, the construct for decomposing sets is ∪ which forms a set by taking the big union of e₁ [o/x] over each o in the set e₂.

The expressive power of NRC and its extensions are studied in numerous studies [16, 26–29]. Specifically, the NRC core has exactly the same power as all the standard nested relational calculi and when restricted to flat tables as input-output, it has exactly the same power as the relational calculus. In the presence of arithmetics and a summation operator, when restricted to flat tables as input-output, it has exactly the power of entry-level SQL. Furthermore, it captures standard nested relational queries in a high-level manner that is easy for automated optimizer analysis. It is also easy to translate a more user-friendly surface syntax, such as the comprehension syntax or the SQL select-from-where syntax, into this core while allowing for full-fledged recursion and other operators to be imported easily as needed into the system.

Example 6.5.1: Create a warehouse of GenPept reports and initialize it to reports on protein tyrosine phosphatases. Kleisli provides several functions to access GenPept reports remotely from Entrez [9]. One of them is aa-get-seqfeat-general, which retrieves GenPept reports matching a search string.

In this example, a table genpept is created in the local Oracle database system. This table has two columns, uid for recording the unique identifier and detail for recording the GenPept report. A LONG data type is used for the detail column of this table. However, recall from Example 6.3.2 that each GenPept report is a highly nested complex object. There is therefore a mismatch between LONG (which is essentially a big, uninterpreted string) and the complex structure of a GenPept report. This mismatch is resolved by the Kleisli system, which automatically performs the appropriate encoding and decoding. Thus, as far as the Kleisli user is concerned, x.detail has the type of GenPept report as given in Example 6.3.1. So the user can ask for the title of a report as straightforwardly as x. detail. title. Note that encoding and decoding are performed to map the complex object transparently into the space provided in the detail column; that is, the Kleisli system does not fragment the complex object to force it into third normal form.

There are two possible techniques to use a flat relational database system as a nested relational store. This first is to add a layer on top of the underlying flat relational database system to perform automatic normalization of nested relations into the third normal form. This is the approach taken by systems such as OPM [22]. Such an approach may lead to performance problems as the database system may be forced to perform many extra joins under certain situations. The second technique is to add a layer on top of the underlying flat relational database system to perform automatic encoding and decoding of nested components into long strings. This is the technique adopted in Kleisli because it avoids unnecessary joins and because it is a simple extension—without significant additional overhead—to the handling of Kleisli’s data exchange format.

Example 6.6.1: Let us consider the webomim-get-detail function used in Example 6.4.4. It uses an OMIM identifier to access the OMIM database and returns a set of objects matching the identifier. The output is of type:

Note that this is a nested relation: It consists of a set of records, and each record has three fields that are also of set types, namely #gene_map_locus, #alternative_titles, and #allelic_variants. This type of output would definitely present a problem if it had to be sent to a system based on the flat relational model, as the information would have to be re-arranged in these three fields to be sent into separate tables.

Fortunately, such a nested structure can be mapped directly into Kleisli’s exchange format. The wrapper implementor would only need to parse each matching OMIM record and write it out in a format as illustrated in the following:

Instead of needing to create separate tables to keep the sets nested inside each record, the wrapper simply prints the appropriate set brackets { and } to enclose these sets. Kleisli will automatically deal with them as they were handed over by the wrapper. This kind of parsing and printing is extremely easy to implement. Figure 6.4 shows the relevant chunk of Perl codes in the OMIM wrapper implementing webomim-get-detail.

Example 6.7.1 Vertical loop fusion.:

Example 6.7.2: The BottomUpOnce strategy applies rules in a leaves-to-root pass. It tries to rewrite each node at most once as it moves toward the root of the query expression. Here is its control component:

The following class of rules requires the use of multiple rule-application strategies. The scope of rules like the vertical loop fusion in the previous section is over the entire query. In contrast, this class of rules has two parts. The inner part is context sensitive, and its scope is limited to certain components of the query. The outer part scopes over the entire query to identify contexts where the inner part can be applied. The two parts of the rule can be applied using completely different strategies.

A rule base RDB is represented in the system as an SML record of type:

The Rules field of RDB stores the list of rules in RDB together with their names. The Trace field of RDB stores a function f that is to be used for tracing the usage of the rules in RDB. The DoTrace field of RDB stores a flag to indicate whether tracing is to be done. If tracing is indicated, then whenever a rule of name N in RDB is applied successfully to transform a query Q to Q′, the trace function is invoked as f N Q Q′ to record a trace. Normally, this simply means a message like “Q is rewritten to Q′ using the rule N” is printed. However, the trace function f is allowed to carry out considerably more complicated activities.

It is possible to exploit trace functions to achieve sophisticated transformations in a simple way. An example is the rule that rewrites if e₁ then … e₁ … else e₃ to if e₁ then … true … else e₃. The inner part of this rule rewrites e₁ to true. The outer part of this rule identifies the context and scope of the inner part of this rule: limited to the then-branch. This example is very intuitive to a human being. In the then-branch of a conditional, all sub-expressions identical to the test predicate of the conditional must eventually evaluate to true. However, such a rule is not so straightforward to express to a machine. The informal “…” are again in the way. Fortunately, rules of this kind are straightforward to implement in Kleisli.

Example 6.7.3: The if-then-else absorption rule is expressed by the AbsorbThen rule below. The rule has three clauses. The first clause says the rule should not be applied to an IfThenElse whose test predicate is already a Boolean constant because it would lead to non-termination otherwise. The second clause says the rule should be applied to all other forms of IfThenElse. The third clause says the rule is not applicable in any other situation.

The second clause is the meat of the implementation. The inner part of the rewrite if e₁ then … e₁ … else e₃ to if e₁ then … true … else e₃ is captured by the function Then, which rewrites any e identical to e₁ to true. This function is then supplied as the rule to be applied using the TopDownOnce strategy within the scope of the then-branch … e₁ … using the ContextSensitive rule generator given as follows.

This ContextSensitive rule generator is re-used in many other context-sensitive optimization rules, such as the rule for migrating projections to external relational database systems to be presented shortly.

Example 6.7.4: The rule for migrating projections to a relational database is implemented by MigrateProj in this example. The rule requires a function FullyProjected x N that traverses an expression N to determine whether x is always used within N in the context of a field projection and to determine what fields are being projected; it returns NONE if x is not always used in such a context; otherwise, it returns SOME L, where the list L contains all the fields being projected. This function is implemented in a simple way using the ContextSensitive rule generator from Example 6.7.3.

The MigrateProj rule is defined below. The function SQL. PushProj is one of the many support routines available in the current release of Kleisli that handle manipulation of SQL queries and other SYN abstract syntax objects.

Besides the four migration rules mentioned previously, Kleisli has various other rules, including reordering joins on two relational databases, parallelizing queries, and large-scale code motion, the description of which is omitted in the chapter due to space constraints.

 New is the constructor of a record. For example, to create a record such as(#anno_name: “db_xref”, #descr: “taxon: 10090”) in a Perl program, one writes:

where $rec becomes the reference of this record in the Perl program.

 Project gets the value of a specified field in a record. For example,

will return the value of the field #descr in the record referenced by $rec in the Perl program.

 new is the constructor of bulk data such as a list, a bag, or a set. It works the same way as a list initialization in Perl:

where $1 will be the reference of this list in the Perl program.

 Open1 opens the specified Kleisli-formatted data file and returns the handle of this file in Perl. It supports all the input-related features of the usual open operation of Perl, including the use of pipes. For example, the following expression opens a Kleisli-formatted file “sequences.val”:

 Openla is another version of the Openl function, which can take a string as input stream. The first parameter specifies the child process to execute and the second parameter is the input string. An example that calls Kleisli from CPL2Perl to extract accession numbers from a sequence file is expressed as follows:

 Open2 differs from Openla in that it allows a program to communicate in both directions with Kleisli or other systems. It is parameterized by the Kleisli or other systems to call. It returns a list consisting of a reference of CPLIO object and an input stream that the requests can be sent into. For example:

 Parse is a function that reads all the data from an opened file until it can assemble a complete object or a semicolon (;) is found. The return value will be the reference of the parsed object in Perl. For example, printing the values of the field #accession of an opened file may be expressed by:

 LazyRead is a function that reads data lazily from an opened file. This function is used when the data type in the opened file is a set, a bag, or a list. This function only reads one element into memory at a time. Thus, if the opened file is a very big set, LazyRead is just the right function to access the records and print accession numbers:

Example 6.8.1: Assume that Kleisli produces a file $SPEC of type { (#actor: string, #interaction: string, #patient: string) } which describes a protein interaction pathway. The records express that an actor inhibits or activates a patient. The relevant parts of a Perl implementation of the module MkGif that accepts this file, converts it into a directed graph specification, invokes Graphviz to layout, and draws it as a GIF file $GIF using CPL2Perl is expressed as follows:

The first three lines establish the connections to the Kleisli file $SPEC and to the Graphviz program dot. The next few lines use the LazyRead and Project functions of CPL2Perl to extract each interaction record from the file and to format it for Graphviz to process. Upon finishing the layout computation, Graphviz draws the interaction pathway into the file $GIF.

This example, though short, demonstrates how CPL2Perl smoothly integrates the Kleisli exchange format into Perl. This greatly facilitates both the development of data drivers for Kleisli and the development of downstream processing (such as pretty printing) of results produced by Kleisli.