More phylogeny-related questions that can be written as SQL

Pursuant to my last post (Using SQL to make phylogenetic queries), I've started to dream up some other questions that Names on Nodes will be able to answer:

"What are all dinosaur species that lived during the Maastrichtian Age?"

Possible SQL:

SELECT dinosaur.name
  FROM node_clade(ARRAY(
    SELECT *
      FROM resolve_signifier_identities(ARRAY[
        'urn:isbn:0853010064::Hylaeosaurus_armatus',
        'urn:isbn:0853010064::Iguanodon_bernissartensis',
        'urn:isbn:0853010064::Megalosaurus_bucklandii'
    ])
  ), 0) AS dinosaur_identity
  JOIN signifier AS dinosaur
    ON dinosaur.identity_id = dinosaur_identity
  JOIN signifierannotation
    ON dinosaur.id = signifierannotation.signifier_id
    AND signifierannotation.role
      = 'http://namesonnodes.org/quantities::years_bp'
  JOIN quantity AS years_bp
    ON signifierannotation.id = years_bp.id
  JOIN signifier_categories
    ON signifier_categories.signifier_id = dinosaur.id
  WHERE years_bp.value <= 70600000
    AND years_bp.value >= 65500000
    AND signifier_categories.element = 'species'
  GROUP BY dinosaur.name
  ORDER BY dinosaur.name;

"What are the largest named subtaxa of Angiospermae?"

Possible SQL:

SELECT angiosperm.name
  FROM coarsest(ARRAY(
    SELECT * FROM subsets(
      resolve_signifier_identity(
        'urn:isbn:00800694/146::Angiospermae'),
      , 0)
    EXCEPT
    SELECT resolve_signifier_identity(
      'urn:isbn:00800694/146::Angiospermae')
  ), 0) AS angiosperm_identity
  JOIN signifier AS angiosperm
    ON angiosperm.identity_id = angiosperm_identity
  GROUP BY angiosperm.name
  ORDER BY angiosperm.name;

"Which catalogued specimens represent stem-mammals?"

Possible SQL:

SELECT catalogue.name, specimen.name
  FROM signifier AS specimen
  JOIN authority
    ON specimen.authority_id = authority.id
  JOIN authorityidentity AS catalogue
    ON authority.identity_id = catalogue.id
  JOIN signifier_categories
    ON signifier_categories.signifier_id = specimen.id
    AND signifier_categories.element = 'specimen'
  WHERE specimen.identity_id = ANY(
    SELECT total(
      ARRAY(SELECT
        resolve_signifier_identity(
          'urn:isbn:0853010064::Mammalia')),
      ARRAY(SELECT
        resolve_signifier_identity(
          'urn:doi:10.1051/jp4:20020447::Anthropocene')),
      0)
    EXCEPT
    SELECT subsets(
      ARRAY(SELECT resolve_signifier_identity(
        'urn:isbn:0853010064::Mammalia')),
      0)
  )
  GROUP BY catalogue.name, specimen.name
  ORDER BY catalogue.name, specimen.name;

"How many anseriform species are flightless?"

Possible SQL:

SELECT COUNT(anseriform.identity_id)
    AS flightless_anseriform_count
  FROM signifier AS anseriform
  JOIN signifier_categories
    ON signifier_categories.signifier_id = anseriform.id
    AND signifier_categories.element = 'species'
  WHERE anseriform.identity_id = ANY(
    SELECT * FROM subsets(ARRAY(
      SELECT resolve_signifier_identity(
        'urn:isbn:0853010064::Anseriformes')
    ),
    0)
  )
  AND anseriform.identity_id = ANY(
    SELECT * FROM subsets(ARRAY(
      SELECT resolve_signifier_identity(
        'biofile:9A75AD84C56B43AD681991EBA56D8B4E6E36B311'
        || '::data/flight/absent')
    ),
    0)
  );

Many more possibilities. Note that the "0" in the queries above means "use all available information". Other numbers can be used to restrict information to certain datasets.

Using SQL to make phylogenetic queries

"Computer, can any dinosaurs fly?"

It would be great if we could ask computers questions this easily. Unfortunately, computers lack our natural linguistic skills. But this doesn't mean they are incapable of answering such questions—the questions just need to be rephrased.

SQL (pronounced either as "S.Q.L." or "sequel", and standing for "Structured Query Language") is the most commonly-used language for querying relational databases. This past week I have been adapting the phylogenetic operations in my 2007 paper into SQL (specifically the PostgreSQL version) as part of my Names on Nodes project. There have been a few difficulties to do with the fact that the database only records taxa (sets of organisms), while my published algorithms work at the organism level. But this is a minor difficulty so far, and things seem to be working.

To get an idea of how the system works, let's look at the question posited at the beginning of this post. How can the question be translated into a SQL query?

First, a quick summary of what's in the database: taxa (sets of organisms) of all kinds are represented by a table of "signifiers". Each signifier references an "authority", which could be anything from a publication to a nomenclatural code to a systematics dataset to a personal opinion. Each signifier also has a name which is unique under that authority. For example, under the authority of the International Code of Zoological Nomenclature (ICZN for short), the name "Homo sapiens" signifies a particular taxon (a species). Under the authority of the Yale Peabody Museum's Vertebrate Paleontology collection, the name "1450" refers to a specimen, and by proxy the set of organisms (in this case, just one) which that specimen represents. Under the authority of a particular NEXUS file, "data/flight/present" may refer to a character state, and by proxy the set of all organisms exhibiting that state.

Each authority is represented by one or more Universal Resource Identifiers, or URIs. Website addresses (URLs) are one kind of URI, so, for example, the Yale Peabody Museum's Vertebrate Paleontology collection can be represented as http://www.peabody.yale.edu/collections/vp. ISBN numbers are another type of URI, so the ICZN can be represented as urn:isbn:0853010064. Systematics files are a little trickier; my current solution is to use a custom schema and a unique "hash" string of characters programmatically derived from the data in the file, e.g., something like biofile:08192A3 (actually longer, but I'll keep it short for this discussion).

Each signifier can be represented as a "qualified name" (or "QName"), which combines the authority's URI and the signifier's name. Examples:

• http://www.peabody.yale.edu/collections/vp::1450
• urn:isbn:0853010064::Homo_sapiens
• biofile:08192A3::data/flight/present

(A fuller discussion of the Names on Nodes database can be found in this earlier post.)

Definitions may be stored as MathML, as indicated in my 2007 paper. Let's suppose that someone defines Dinosauria as, "the final common ancestor of Megalosaurus bucklandii von Meyer 1832, Hylaeosaurus armatus Mantell 1833, and Iguanodon bernissartensis Boulenger in Beneden 1881, plus all descendants of that ancestor." This can be rendered as:

<apply xmlns="http://www.w3.org/1998/Math/MathML">

<csymbol definitionURL="http://namesonnodes.org/phylo/math​::nodeClade"/>

<csymbol definitionURL="urn:isbn:0853010064​::Hylaeosaurus_armatus"/>

<csymbol definitionURL="urn:isbn:0853010064​::Iguanodon_bernissartensis"/>

<csymbol definitionURL="urn:isbn:0853010064​::Megalosaurus_bucklandii"/>

</apply>

Basically, this means, "Apply the nodeClade function to the the union of the signified taxa." The nodeClade function corresponds to the phrase, "the final common ancestors and all descendants thereof". It relies on three other phylogenetic functions: allDescendants, maximal, and commonAncestors. ("Maximal" in this context means "all members of a set which are not ancestral to any other members in that set"—a more precise way to say "final".)

Names on Nodes will take a MathML definition like this and convert it into a SQL query like this:

  SELECT * FROM node_clade(
    ARRAY(SELECT * FROM resolve_signifier_identities(
      ARRAY[
        'urn:isbn:0853010064::Hylaeosaurus_armatus',
        'urn:isbn:0853010064::Iguanodon_bernissartensis',
        'urn:isbn:0853010064::Megalosarus_bucklandii'
      ])),
  0);

The resolve_signifier_identities function converts an array of qualified names into a set of identity numbers corresponding to signifiers, using a query like this:

  SELECT identity_id
  FROM signifier
  WHERE qname = ANY(qname_list);

This is a relatively simple SQL query. The grammar is fairly intuitive (at least for a computer language). The query for the node_clade function is far more complex, though. To discuss that, I'll have to go into the database structure a bit more.

A phylogenetic definition cannot be applied without some kind of phylogenetic hypothesis. Names on Nodes is capable of reading phylogenies encoded as Newick trees, including those in NEXUS files. Let's suppose someone uploaded a NEXUS file with this Newick tree in it:

((Iguano_bern, Hylaeo_arma), (Megalo_buck, (Tyrann_rex, (Anas_plat, Passer_dome))))

Let's suppose the URI for this file is biofile:08192A3. Then this file authorizes some new signifiers:

• biofile:08192A3::taxa/Iguano_bern
• biofile:08192A3::taxa/Hylaeo_arma
• biofile:08192A3::taxa/Megalo_buck
• biofile:08192A3::taxa/Tyrann_rex
• biofile:08192A3::taxa/Anas_plat
• biofile:08192A3::taxa/Passer_dome

These can be objectively equated with other signifiers:

• urn:isbn:0853010064::Iguanodon_bernissartensis
• urn:isbn:0853010064::Hylaeosaurus_armatus
• urn:isbn:0853010064::Megalosaurus_bucklandii
• urn:isbn:0853010064::Tyrannosaurus_rex
• urn:isbn:0853010064::Anas_platyrhynchos
• urn:isbn:0853010064::Passer_domesticus

(The last two could conceivably be equated with vernacular names from a field guide as well, e.g., urn:isbn:0679428518::Mallard and urn:isbn:0679428518::House_Sparrow, respectively) Equated signifiers share the same identity. This file also authorizes some less visible signifiers: the hypothetical ancestors, such as the ancestor of Iguano_bern and Hylaeo_arma, the ancestor of Anas_plat and Passer_dome, etc. Names on Nodes assigns these ancestors arbitrary, numerical names.

The phylogeny in the Newick tree can be represented as a set of arcs, each pointing from a parent signifier (or "head") to a child signifier (or "tail"):

  ~1 → ~2
  ~1 → ~3
  ~2 → Iguano_bern
  ~2 → Hylaeo_arma
  ~3 → Megalo_buck
  ~3 → ~4
  ~4 → Tyrann_rex
  ~4 → ~5
  ~5 → Anas_plat
  ~5 → Passer_dome

These get stored in the database as rows representing parentage relations. Similar relations are used for supersets and subsets (e.g., to indicate that Tyrannosaurus includes Tyrannosaurus rex). Phylogenetic functions, such as maximal, all_ancestors, and common_ancestors, utilize the data in these relations.

Some of these functions use another function called find_parentage_arcs to get a list of all parent-child relations which involve any of a given set of signifiers. For example, maximal uses a query like this:

  SELECT id
    FROM signifieridentity
    WHERE id = ANY(identity_list)
  EXCEPT
  SELECT arc.head
    FROM find_parentage_arcs(identity_list, context_id)
      AS arc;

In other words, select all signifier identities from a given list, except those which are the parent (head) in any parent-child arc whose parent and child are in that list. (The context_id variable specifies which datasets to use and which to ignore, but that's an essay unto itself.)

The node_clade function uses a query like this:

  SELECT * FROM all_descendants(ARRAY(
    SELECT * FROM maximal(ARRAY(
      SELECT * FROM common_ancestors(identity_list,
      context_id)),
    context_id)),
  context_id);

In other words, select all descendants/members of all maximal members of the common ancestors of the specified signifiers. (Again, context_id specifies which datasets to use; a value of zero means that all datasets should be used.)

Running the Dinosauria SQL query mentioned earlier will now yield a set including all of the signifiers mentioned so far. In other words, according to the provided definition and the provided phylogenetic hypothesis, I. bernissartensis, H. armatus, M. bucklandii, T. rex, A. platyrhynchos, and P. domesticus are all members of Dinosauria (as are the hypothetical ancestors in the phylogenetic tree).

Suppose the aforementioned NEXUS file also had a character matrix including the character "flight". This would be scored as "present" in Anas_plat and Passer_dome. Thus, the table of inclusions would include these arcs:

  flight/present → Anas_plat
  flight/present → Passer_dome

(Names on Nodes also extrapolates the arc flight/present → ~5, but, again, that's another essay.)

A function called subsets retrieves all signifiers indicated as subsets of a given signifier. Thus, the question that began this essay can be written in SQL as:

  SELECT COUNT(dinosaur) > 0 AS verdict
  FROM node_clade(
    ARRAY(SELECT * FROM resolve_signifier_identities(
      ARRAY[
        'urn:isbn:0853010064::Hylaeosaurus_armatus',
        'urn:isbn:0853010064::Iguanodon_bernissartensis',
        'urn:isbn:0853010064::Megalosarus_bucklandii'
    ])),
  0) AS dinosaur
  JOIN subsets(
    resolve_signifier_identity(
      'biofile:08192A3::data/flight/present'
    ),
  0) AS flier ON dinosaur = flier;

The verdict: true.

The Wonderful Process of Refactoring

In many ways, programming is as much an art as a science. Good code is like good writing: crisp, clear, streamlined, and well-structured. But it's not always possible to foresee the best structure. When working on a project, you just do what seems best at the time. Eventually you'll finish it and work out the bugs, but the underlying code may not be elegant. There may be duplicated code, unclear functionality, unoptimized sections, and sections that do too much with sections that do too little. When you come back to the code to add or refine features, you often face a major headache.

This is why many developers use a general process called refactoring. Refactoring means that you change the design of the code without changing the functionality. An analogy would be rewriting a news article so that it reads better without changing what the article is actually about.

Ensuring that the functionality remains the same is not always easy. It involves frequent testing and retesting. Changing one section might affect another section, so the retesting has to be thorough. Testing a particular section during development is called unit testing.

Sometimes it's worth the extra time to create a program that actually does the testing for you. During heavy refactoring, this can save oodles of time. If you make changes, then you can just run a test that takes a few seconds, quickly showing whether you broke anything (and generally showing exactly what you broke).

I went through this process recently while working on March of Man.

The Setup

Typically a rich Internet application (RIA) has three tiers. The client-side application is something you view in a browser (for example, this website). The database is an application on the server that stores data. The server-side application facilitates communication between the database (and potentially other server-side information) and the client-side. To sum up:

user ↔ client-side app ↔ server-side app ↔ database

In case you were curious, for March of Man, the client-side application is an interactive Flash movie made with Flex Builder, the server-side application uses Java running on JBoss, and the database is PostgreSQL.

All this communication between tiers can get a bit complicated. Fortunately, Adobe provides an excellent tool called LiveCycle Data Services (LCDS) for communicating between the client- and server-side applications. What exactly does it do? Well, March of Man deals with certain types of data: user accounts, images, hominin taxa, location/time ranges, etc. In programming, these types are referred to as classes, and classes are instantiated (i.e., realized) as objects. Specifically, these ones would be considered value objects. So, for example, there is a class called Account that specifies certain types of data, like email address, personal name, password, etc. An instance of Account (i.e., an Account object) might represent a particular person. For the client-side, the Account class is written in ActionScript. For the server-side, it's written in Java. What LiveCycle does is take care of all of the translation: when I send an ActionScript Account object to the server, it is automatically recreated as a Java Account object, and vice versa when the server reports to the client.

As an example, when you log in, the client collects your email address and password, and sends them (encrypted) to the server, specifying a login method. That method looks up the information for the specified account, packages it as an Account object, and sends it back to the client. Voilà, you are logged in.

Unfortunately, there isn't a similarly easy tool for translating from the server-side application to the database, where data is stored in tables as rows and columns. The only way to interface is using SQL, a common language used for database queries. Java provides some ways to facilitate this (the java.sql package of classes), but it can't do everything.

So I created a package of classes called org.marchofman.mappers to map the information from Java to PostgreSQL and back. Each mapper class corresponds to a type of value object, e.g. AccountMapper handles Account objects, ImageMapper handles Image objects, etc. They all have certain functionality in common, such as what are called the "CRUD" commands: create, retrieve, update, and delete. When you register, the Java service uses the AccountMapper.create method. When you log in, it uses AccountMapper.retrieve. When you change your information, it uses AccountMapper.update. And, should you ever decide you don't want an account any more (heavens forfend), it would use AccountMapper.delete.

The Problem

For the initial version of the site (still up as of this writing, but soon to be upgraded), the "mapper" classes did their job. But all was not well under the hood. Since there were many different ways to select data, I sometimes had to make multiple mapper classes for the same type of value object. For example, a user might want to pull up information on a particular image, on their own images, on the images corresponding to a particular taxon, or just on all images. Each of these required a completely different method, and I had to struggle to keep the levels of duplicated code down. Duplicated code might sound like a minor annoyance, but it can have serious effects. It really complicates both testing and updating code.

Eventually I realized that the mapper classes should not be concerned with how to decide which objects to handle, only with how to handle them once they were specified. I created a new type of object, called a Qualifier, to store information on how to specify certain objects. As an example, a TotalQualifier object specifies all value objects of a given type. A FieldQualifier object specifies all value objects with a certain piece of data, for example, all accounts with a given email address. A KeyQualifier specifies one particular object by a unique identifier. And a ConjunctionQualifier qroups other qualifiers and selects only those objects which satisfy all of those qualifiers.

Formerly I had to write methods like retrieveForOwner, retrieveAll, retrieve, retrieveForTaxon, retrieveForLogin, etc. With the new structure, I could just have one method, retrieve, and pass it any kind of Qualifier object I wanted. The number of classes in the org.marchofman.mappers package shrunk down to a fraction of what it had been. Now it was down to the ideal: one mapper class for each type of value object.

Doing all this was a fair bit of work. Fortunately, I had already built automated unit tests using the excellent flexunit framework. Once I finished my initial refactoring work, I just ran the tests and could instantly see what I still needed to fix.

The Payoff

Now not only do I have a more streamlined and flexible server-side architecture, but also some generalized mapping classes which may greatly facilitate work on future projects. Is the code perfect? No, but it's much better than it was. And I can always refactor again if I need to....