DSGRN Documentation

Ultimately, we will have wonderful web interfaces to examine this database, but for right now, since it is an SQLite database, we can use the SQL query interface. So what follows is a tutorial to SQL, tailored to the needs of using it to query the database of dynamic sigatures computed by DSGRN.

Let’s fire up SQLite’s interactive interface:

Now we should see the prompt:

So far, so good.

A database is comprised of tables; we can ask SQLite about what tables we have:

The information produced by Signatures is in these tables. Each table has a number of columns and rows. The columns are named. We can find out about the columns of each table by asking about the database’s "schema":

What we see here are the commands that were invoked to create the tables and indices. Indices are data structures formed on tables to speed up different types of queries. Indexing is extremely important; we’ll talk about it later. For now, we’ll focus on the tables. Consider the Signatures table. There are two columns: ParameterIndex and MorseGraphIndex. Both hold integer data. The ParameterIndex is marked INTEGER PRIMARY KEY, which tells SQLite that it doesn’t need to add its customary implicit rowid column; it can assume the ParameterIndex data can serve that function equally well (in particular, we will never attempt to insert two rows with the same ParameterIndex value).

To learn more about tables we will want to see their contents. In order to get at the contents of a table, we use the SELECT command. Time for an example. The table MorseGraphViz contains a list of MorseGraphs in a somewhat human-readable graphviz format, so let’s take a look at that one.

We’ll type

The * here says you want to know the values for all the columns.

skip a few…​

skip a few more…​

As we can see, the database computation recorded 28 distinct Morse graphs. By way of example, we notice Morse graphs 18 and 19 are isomorphic, so by distinct we mean having a distinct representation rather than not being isomorphic. Later, we will add a feature that attempts to reduce the number of Morse graphs by heuristic approaches to graph canonicalization. For now, we can query about both representations at the same time, which is a nice example anyway. We will look in the table Signatures, which provides a mapping between parameter indices and the Morse graphs that occur:

Let’s stop a moment and think about how the database answered that last query. Was it efficient? One approach which would be absolutely terrible is if the database software scanned the Signature table in entirety and returned all the matching rows. For large databases, this would be ridiculously slow. It is called a full table scan. Full table scans are to be prevented whenever possible. The means of preventing full table scans is indexing. With indexes, the database maintains a copy of the database sorted by other columns. So having sorted the Signatures table by the MorseGraphIndex column, one can pull out the matching rows extremely efficiently (just as one can look up a word in a dictionary efficiently). Looking back at the schema, we see that such an index was in fact constructed by DSGRN’s computation:

Thus, these sorts of queries should be fast. We can actually ask SQLite how it plans to accomplish a query, and make sure it is using our index to do it right, rather than do a full table scan:

Seems legit. What happens if it didn’t have that index?

Oh no! The dreaded full table scan! Quick, rebuild the index!

Let’s try another query. For the network we are considering, there were 4 cohorts of 400 parameters. We might only be interested in a particular cohort (i.e. ordering of thresholds) so we only care about, for instance, parameters 0 through 399. We could make a similar query, but restricted to the first 400 parameters:

Here SQLite should again use the index, first quickly determining which rows satisfy MorseGraphIndex=18 or MorseGraphIndex=19 and then among these rows using the sorting of ParameterIndex to quickly retrieve the rows associated with the ParameterIndex < 400 cohort. This is a more complex usage of the index; see SQLite’s nice explanation of query planning for more details.

Back to the example. Let’s say we do not care which parameter was assigned Morse graph 18 and which was assigned 19 since they are, after all, isomorphic. We can instruct to only give the column corresponding the parameter index, dropping the column which distinguishes between 18 and 19:

We could also ask for the columns out of order, or the same column more than once. For example:

We may prefer a comma separated list rather than a long column, so we can use the GROUP_CONCAT feature:

If this seems sort of strange, good. It’s an example of an aggregate function, and we’ll talk about those more later.

An important tool to use database structures is the join. This lets us combine two tables based on matches in a certain way. Let’s consider an example. Suppose we want to find all parameters where the Morse graph has at least 4 vertices. Since vertices in a Morse graph are indexed contiguously beginning at zero, this is the collection of parameters for which the Morse graph contains the vertex 3. This gives us a hackish trick for quickly selecting them by querying the MorseGraphVertices table for Vertex=3. The select will be fast, since we have the following index available:

SQLite will use this index to quickly answer the following query:

But wait; these aren’t the parameters with Morse graphs having at least 4 vertices; these are the Morse graphs themselves. We need to turn around and look up parameters associated with these Morse graphs. Here is how NOT to do it:

Nope! Ack! Don’t do that. Instead, try this:

Now GotAtLeastFour is the table of results we were just considering. We told SQLite it was temporary, so it knows this isn’t going to be a permanent citizen of our database. We can use it with the Signatures table as follows:

The natural join was the magic mustard here. The natural keyword is shorthand to tell it to perform a join on the columns with the same name. A join is a procedure whereby two tables are combined together into a single table on the basis of matching entries.

We can get rid of that temporary table now:

Good riddance. In fact, we never needed that pesky tempory table in the first place:

We should stay in the habit of always making sure the queries we run are efficient:

We see its plan involves using the proper indices, so it seems right.

The last example was pretty fancy, so let’s do something a little more basic: counting.

There is a command COUNT which lets you count things:

Those are our 1600 parameters. There is also a distinct keyword, which lets us select only when a new item is found. Here is an example of its use:

Looks great, but beware! You might assume these are fast operations, the former taking \(O(1)\) time and the latter taking (for an indexed table) \(O(n \log N)\) time, where \(n\) is the count returned and \(N\) is the number of rows. However, SQLite has apparently made a deliberate design decision which forces a full table scan whenever COUNT is used. We can actually speed up the latter:

This still runs a full table scan with COUNT, but it does it on the small table returned by the interior SELECT. Meanwhile, the select distinct MorseGraphIndex from Signatures does the right thing:

Well, hopefully does the right thing. Technically, the asymptotically best solution is based on skipping from key to key with repeated binary searches, not scanning the entire indexed table. Word on the street is that this so-called skip-scan algorithm is only considered when there are more than 50 rows for each distinct value. In the current example, there are around 57 (we’ll see this later in an example), but the database is very small, so it might not bother. Definitely worth checking out as things scale up!

The two expressions we have seen, GROUP_CONCAT and COUNT are examples of what are known as aggregate functions. The idea of an aggregate function is that it takes a column and compresses it into a single item. If A is an aggregate function, then there is some seed value (for GROUP_CONCAT it is the empty string, for COUNT it is 0) and upon processing a new item it updates the value according to what it sees. For GROUP_CONCAT it affixes the next item with a comma delimiter. For COUNT it adds one.

In fact, we can combine aggregate functions together in queries in comma-concatenated lists. When we do this, we can regard vanilla column entries as aggregate functions as well: MorseGraphIndex can be understood as the aggregate function that reads a row and updates its value to be the entry in the MorseGraphIndex column. Here is an example:

Which yields:

The 89 makes sense; this is the total number of vertices in all the Morse graphs combined. But what is the 27? It isn’t the number of Morse graphs; there are 28 of them. The answer is that it is simply the last value of the ``MorseGraphIndex`` field encountered while processing the rows with the aggregate function.

For a very ridiculous example (purely to illustrate the behavior of aggregate functions):

This has made comma-concatenated lists out of every MorseGraphIndex field and every Vertex field, and made a row with two columns out of them.

At this point one might get the idea that aggregate functions are a one-trick pony, good for counting the number of rows or concatenating entries from a single column but yielding nonsense in all other situations. This is because we have not yet covered the GROUP BY syntax, which makes aggregate functions far more useful.

The GROUP BY command tells a SELECT statement to break the rows into groups based on chosen columns. For example, GROUP BY MorseGraphIndex would tell SQLite you wanted to look at the table in several groups, each group having some given value in the MorseGraphIndex field. It automatically assumes you mean to use aggregate functions. The aggregate functions don’t process the entire table and produce a single row, but rather process each group and produce a table with rows corresponding to each group. This is quite useful.

We’ll illustrate this by example. Let’s figure out which Morse graphs have more than 50 parameters corresponding to them. We tackle this by first creating a table with rows reporting the number of parameters associated to each Morse graph. Then we select those rows for which there are more than 50 parameters.

Wonderful! But how did it work? There are several new pieces of syntax. First, we see the count(*) as Frequency. This tells SQLite that the thing it is computing with the aggregate function count(*) is something that you want to refer to by the name Frequency. Later, we have the phrase order by Frequency desc which tells SQLite you want the final table to be ordered by the Frequency column in descending order. Finally, saving the best for last, we have the group by MorseGraphIndex. The GROUP BY feature tells SQLite that we want to break the table into groups based on the value of the MorseGraphIndex column. It then "evaluates" the aggregate function MorseGraphIndex,COUNT(*) over each group, and the output for each group is the row consisting of the MorseGraphIndex for the group and the number of rows in that group. Which is what we wanted! So along with GROUP BY, aggregate functions become powerful tools.

As a quick aside, we can now calculate the average number of parameters associated to a Morse graph by using the AVG aggregate function:

Anyhow, we are now ready to give the list of all Morse graphs have more than 50 parameters corresponding to them:

Let’s do an even more glamorous example of grouping. Let’s create a table with three columns. The first column will be MorseGraphIndex, the second column will be Frequency, and the third column will be ParameterIndices. Also, let’s make sure the table is sorted in descending order on the Frequency column.

Is this table what we want? Instead of SELECT * FROM MorseGraphClasses, let’s instead go with

Great! Just what we wanted. But is it doing it efficiently? You’d think because we told it order by Frequency desc it would know that it could use binary search to do this query. Nope!

Ah, the dreaded full table scan. Probably the rationale is that you could later insert rows which break this property, so it cannot make this assumption. To prevent the full table scan we could index our new table:

Now the database software has twigged to the better plan:

Let’s revisit the example with finding Morse graphs with a certain number of vertices. Before, we used a hackish trick that relied on the fact a Morse graph had a vertex with index \(k\) if and only if it had at least \(k+1\) vertices. Using grouping, we don’t need to rely on such tricks.

We’ll make a table which lists each Morse graph according to the number of vertices it has in descending order.

Now let’s select the ones with more than 3 vertices:

This is the same collection of Morse graphs we found earlier, albeit in a different order.

Our Morse graphs come equipped with annotations. These are visible in the graphviz records, but they are also available in the MorseGraphAnnotations table. This lets us use the querying capabilities. We might be interested in querying for various logical combinations of annotations applied to a Morse graph, and then learning which parameters are associated.

Let’s say we are interested in finding all parameters which have a Morse graph that has an annotation "FP OFF", an annotation "FC", but do not have the annotation "FP ON". We can accomplish this as follows:

We check the query plans to make sure this is happening efficiently:

Looks good.

It is important to make sure that the database is being efficient in answering queries. Just because there is an efficient way to do something does not mean that SQLite will translate our intent into an efficient search. We earlier saw an example where we needed to create an index to get SQLite to do the right thing. We noticed with the COUNT function that SQLite forced full table scans. Here we give another example where SQLite actually has the correct indices, but doesn’t do the most efficient thing. To this end we try using the distinct keyword with GROUP_CONCAT:

This result is a little bit disturbing: it is simply the Morse graph indices occurring in the Signatures table in the order which they appear. This implies that SQLite chose a full table scan to satisfy this query! Let’s check:

A full table scan! Terrible! The culprit is the GROUP_CONCAT and not distinct, as the following shows:

which returns

This indicates the query used the index efficiently:

Is this a bug in SQLite? Well, we could argue that SQLite believed that we were very much interested in the order the distinct MorseGraphIndex elements occurred, row by row, in the Signatures table. Thus a full table scan was required to ascertain this ordering.

So if I wanted the comma-separated list without a slow full-table scan, a solution would be

The moral of the story here is to check the query plans, especially when you are using aggregate functions. The difference between \(O(N)\) time full table scan versus a \(O(n \log N)\) time binary search is dramatic for usual choices of \(n\) and \(N\).