"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::1450urn:isbn:0853010064::Homo_sapiensbiofile: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_bernbiofile:08192A3::taxa/Hylaeo_armabiofile:08192A3::taxa/Megalo_buckbiofile:08192A3::taxa/Tyrann_rexbiofile:08192A3::taxa/Anas_platbiofile:08192A3::taxa/Passer_dome
These can be objectively equated with other signifiers:
urn:isbn:0853010064::Iguanodon_bernissartensisurn:isbn:0853010064::Hylaeosaurus_armatusurn:isbn:0853010064::Megalosaurus_bucklandiiurn:isbn:0853010064::Tyrannosaurus_rexurn:isbn:0853010064::Anas_platyrhynchosurn: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.
