Taxonomy pt 3

In my last adventure in taxonomies I had hopes of using Neo4J and Neo4JClient to implement a taxonomy. However, I could never implement the Cypher-queries that worked in Neo4J through the .Net-library Neo4JClient. I got a "400 bad request"-error, struggled, tore my imaginary hair, gave up and changed the route to QuickGraph.

QuickGraph is a graph engine and not a database. It is not a big issue when it comes to a small taxonomy, but would pose problems for huge taxonomies since it holds all data in memory. For me it was a relief, since QuickGraph is something I know and feel comfortable with.

Installation of QuickGraph is straightforward. Just download, build and set a reference.

As a reminder a taxonomy is something where the meaning of a certain term is valid over a specific time. In this case the time is in which revision the term was defined. Like this:

I am using a directed graph where each revision of the taxonomy is descendant of the last revision.

As a practice set I used the gulls in the last blog (check it out).

Step 1.  Create an object that will hold each gull.


    public class Taxon 
    {
        public Guid TaxonId { get; set; }
        public string ScientificName { get; set; }
        public string CommonName { get; set; }
        public int Revision { get; set; }
    }


Since each scientific name can be used in several revisions I use a guid to know which unique taxon it is.

Step 2. Instantiate a directed graph.

BidirectionalGraph<Taxon, IEdge<Taxon>> graph = new BidirectionalGraph<Taxon, IEdge<Taxon>>();

This basically means that the nodes will be of the type Taxon and that the edges will connect two Taxon objects. Bidirectional means that each nod will no who it is descendent from and who derives from it.

Step 3. Implement the InsertTaxon function.


        public void InsertTaxon(Taxon taxon, List<Taxon> ancestors, BidirectionalGraph<Taxon, IEdge<Taxon>> graph)
        {
            graph.AddVertex(taxon);
            foreach (Taxon item in ancestors)
            {
                TaggedEdge<Taxon, double> outEdge = new TaggedEdge<Taxon, double>(taxon, item, 1);
                graph.AddEdge(outEdge);

            }
        }

We're basically inserting the taxon for a new revision of a taxonomy and connects it to all taxons it derives from. By using a TaggedEdge we have a weighted graph. I just default it to one though.

Step 4. Implement the FindTaxon method.


        public IEnumerable<Taxon> FindTaxon(String scientificName, int fromRevision, int toRevision)
        {
            //Find the taxon with the same scientific name from the chosen revision
            Taxon searchTaxon = graph.Vertices.Where(s => s.ScientificName == scientificName && s.Revision == fromRevision).First();
            //use that taxon to find the possible taxons at the to revision
            List<Taxon> results = new List<Taxon>();
            results.AddRange(GetAllDescendantsAtTime(searchTaxon, toRevision));
            return results.Distinct();
        }


        private List<Taxon> GetAllDescendantsAtTime(Taxon searchTaxon, int toRevision)
        {
            List<Taxon> results = new List<Taxon>();
            foreach (Taxon inNode in graph.InEdges(searchTaxon).Where(s => s.Source.Revision <= toRevision && s.Source.Revision > searchTaxon.Revision).Select(n => n.Source))
            {
                if (inNode.Revision != toRevision)
                    results.AddRange(GetAllDescendantsAtTime(inNode, toRevision));
                else
                    results.Add(inNode);
            }
            return results;
        }

So what we basically do is to find what say a Herring Gull was at revision 1 of the taxonomy and then see what it might be at revision 3.
We accomplish this by walking the graph recursively until we find all revision 3 species that are  based on the Herring Gull. The answer would be European Herring Gull, Yellow Legged Gull, Vega Gull, Caspian Gull and American Herring Gull. 

To note: This approach would need a specific graph for each taxonomy and, yeah, there are probably some algorithms that solves the problem faster than mine.

For me: This is perfect! Now I will just make a complete interface to it and use it in all my birding projects!

See you!

Taxonomy pt 2

In my last entry I discussed the special constraints and problems that occur when you need to implement a classification system that changes over time.

This time we will take the discussion a little bit deeper and look at the basic API of a taxonomy component.

A taxonomy is a graph where each taxon has a limited life span and is traceable through previous revisions of the taxonomy.
If I would use birds as an example (and I really like to do that). The Armenian gull, Larus armenicus, is considered a specie by The Association of European Rarities Committees.
It was first considered a sub specie of Herring Gull (L. argentatus), but after that specie was split into European Herring Gull, Larus argentatus, American Herring Gull, Larus smithsonianus, Caspian Gull, Larus cachinnans, Yellow-legged Gull, Larus michahellis, Vega Gull, Larus vegae and the Armenian Gull, Larus armenicus.

To complicate stuff further another taxonomy, namely birdlife.org, doesn't consider it to be a valid specie but lumps it together with Yellow-legged Gull (Larus michahellis).

So... depending on when you see this gull and which taxonomy you use it can be either a Herring gull, an Armenian gull or a Yellow-legged gull and then you're only checking two taxonomies and believe me, there are more out there...

What does this tell us?

1. A taxon has a time span.
2. A taxon is derived from one or more taxons.
3. A taxon is dependent of its taxonomy and several parallel taxonomies may exist.
4. To find a taxon from its key (the latin name in this case), you will need to know the key, the time and the taxonomy.

To find out that the Armenian gull nowadays is considered a sub specie of Yellow-legged gull in Birdlife, I would have to backtrack the taxonomy graph to find the Armenian gull and then follow it to present time to see that it has been included in Yellow-legged gull. 

Even though this example is about birds, the same will apply more or less to any other type of taxonomy.

In pseudo-code the core functions would be:

• Taxon InsertTaxon(Taxon taxon, List<Taxon> ancestors, DateTime validFrom) to insert a taxon based on zero or more ancestors.
• Taxon FindTaxon(String key, DateTime when, Taxonomy string) to find a taxon given a key, time and a certain taxonomy.

The signature can of course differ, but the basic design will be the same.

Next time we will take a look on how we can implement this.

Til then... Bye, bye!

The deadly flat foot

A long time ago I made a system for health statistics and I was demoing it for the stakeholders who of course knew a lot about epidemiology. One of them asked if I could use my system to find out the most common cause of death in Sweden over a time period. I was eager to show off my system and generated the query.

The result was flat foot.
I didn't feel that sure about my system after that.

So what had happened?

I had tons and tons of statistical material with gender, ages and cause of death over several years. The cause of death was marked with a diagnostic number, a so called ICD (International Classification of Disease). This ICD-code was versioned so you had a ICD-6, ICD-7, ICD-8 and so on.

Now, what I didn't know was that Sweden made a shift from ICD-7 to ICD-8 at a certain point of time. My stakeholders (stake holders?) knew this of course and set the trap with a smile.

In ICD-7 the code 746 stands for flat foot but in ICD-8 the code 746 stands for congenital anomalies of heart. So when I summarized the statistics using ICD-7 terminology for ICD-8 data... well, I guess you get the idea.

ICD is an interesting example of taxonomy, the science of classification. Other types of classifications can be the futile attempt to classify the internet into a hierarchy of subjects by yahoo, the classification of plants by Linnae or the subject classification at a library (the strange combinations of letter like Pcj:k that somehow describes a books subject).

Classifications is hierarchic by nature, a subdivision from all into smaller and smaller parts. An approach that is easy but has drawbacks when something fits equally well in two or more classes. (consider a book that is both about History and Math for example)

Classifications also change over time as we saw with the flat foot case. In ICD-8 flat foot had moved from 746 to 736. A change that is vital to know about in order to get correct statistics.

So each version of classification connects to the previous version. In ICD-7 the flatfoot at code 746 points to the 736 flat foot in ICD-8.

Other diagnoses had one code in ICD-7 and got several codes in ICD-8.

Ischaemic Heart Disease for example was 420 in ICD-7 but was covered by the codes 410-414 in ICD-8.

A fork.

This of course made it impossible to know which ICD-8 diagnose a person with the ICD-7 diagnose of  Ischaemic Heart Disease had.
All that could be said was that it was one of the diagnoses between 410 and 414 and maybe, maybe if we knew the relative distribution between the diagnoses 410-414 we could guess that it was 40% chance of 410, 15% chance of 411 and so on stumbling through fuzzy logic.

The opposite could also happen of course, that two classes in the old version is represented by a single class in the new. A join.

Similarly some classes may not have a representation in the new version and totally new classes could appear. You will not find HIV in the ICD-7 because originates from 1955 when the disease was unknown.

To complicate matters even more there can be several different classifications that each has their own versioning with forks and joins, but who's classes also connect to classes in other taxonomies.

With birds you have the Sibley-Ahlquist classification that sees the species differently from the traditional Clemens classification.

The national symbol of New Zeeland, the kiwi bird, is considered to be part of the kiwi order Apterygiformes in Clemens but in the Sibley-Ahlquist it is seen as a part of the ostrich order Struthioniformes.

Still, a kiwi is a kiwi and there is a very strong relationship between the kiwi class in the Clemens classification and its Sibley-Ahlquist sibling.

So how do we fit this thing called classifications into SQL Server?

We have seen that a classification consists of a hierarchy of classes that are connected to other versions of the classification and also to other classes in totally different classifications.

We do have pretty good possibilities to implement hierarchies in SQL Server, but a hierarchy only covers one version of a classification. If we want to be able to track changes and translate between different versions of a taxonomy, a hierarchy is not enough because it is not a hierarchy. It is a graph. And maybe it is a directed acyclic graph and maybe, maybe even a weighted variant.

You can put graphs in a relational database, but it is painful.

Better to use a dedicated graph database such as Neo4J or maybe use a mix of graph engine and a relational database.

More on this next time.

A nice example on ink functionality and how to save and load images in Win 8 RT

Hi,

A new year and although I didn't made a promise to blog more this year, it still feels like I have a little more energy this year. After all, the world didn't vanish the 21st of December and the European Union hasn't collapsed yet.

So I got a question on how to load and save bitmaps in Windows 8 RT and planned to blog about it.

However... one of my rules in coding is to never ever try something new without googling first. So I did.

Here is a nice sample on using the ink and how to do a lot more than I would have done if I would have made it.

Hmm... now to some serious coding!

Windows Phone 8 SDK is out!

I really, really need a Windows 8 phone right now. It is the creeping uneasiness that only a gadget junkie can understand.

I also need a 3d-printer, some new Win8-tablets and a .Net Gadgeteer. I also need the time to play around with them. Hey, I hardly have time to blog these days.

Most of the positive talk regarding Windows Phone 8 has been about the shared core with Windows 8, that you finally can use it on decent hardware and that you now have THREE different sizes of tiles instead of  a meager two.

The negative talk touched the fact that those who bought 7.5 phones can forget the possibility to upgrade them to version 8.

They are dinosaurs, soon extinct.

The thing I find most interesting in 8 is something else, the Company Hub and the new ways of deploying apps for companies who don't want their apps to be hanging on the Marketplace.

For you that might not sound so impressive.

For me it means that I can finally have a slight hope of working with coding Windows Phone 8 apps to customers.

Windows Phone is a much more interesting alternative for enterprise customers than to end customers (read: releasing stuff on the marketplace) as long as the market shares are the way they are. (Why release an app to 1.7% of all smart phone users instead of 50%?)

So if some company wants to use a mobile as an internal tool, I believe Windows Phone 8 could be a strong competitor right away. And maybe, maybe that could give me the chance to start developing WP8-apps outside of my apartment.
After all, there is so much more time at work than home.

Oh yeah... If you would like to start coding you can find the SDK here!

A generic way to read data from an SqlDataReader

Through the years I have been struggling to find a really good way to read data from a datareader. If you know me, you also know that I prefer good old reliable methods that puts me in control to object relational mapping..

Consider the following code (didn't compile it so forgive me for eventual bugs):



    private static List<Book> ReadData(string connectionString)
    {
        List<Book> books = new List<Books>();
        string queryString =
            "SELECT Author, Title, Year FROM Books";

        using (SqlConnection connection =
                   new SqlConnection(connectionString))
        {
            SqlCommand command =
                new SqlCommand(queryString, connection);
            connection.Open();

            SqlDataReader reader = command.ExecuteReader();

            while (reader.Read())
            {
                Book book = new Book();
                book.Author = reader("Book");
                book.Title= reader("Title");
                book.Year= reader("Year");
                books.Add(book);
            }

            reader.Close();
            return books;
        }
    }
}

This code should work pretty well, the problem comes when you start using nullables. If year were int? instead of int this code this would throw an exception as soon as a null value appears in the reader.

Null in Sql Server and in c# are two different things.
From the database points of view a field has three values:

1. A value. For example 1993.
2. A null value. We left the year empty because we didn't know the year.
3. Empty, the book does not exist.

Now you might argue that if the row was empty a try would anyway give you an error and the pragmatical side of me totally agrees, but still, the issue stems from the fact that null in C# is the absence of a reference to an object, while null in a database is an uninitialized or empty value. It exists and we have to deal with it.

I like solving this with extension methods (actually I am generally pretty hooked on extension methods).

The standard approach is to use something like this:

public static int? ToNullableInt(this int value)

{

    return value.IsNull ? (int?) null : value.Value;

}

And then call the reader like:

book.Year= reader("Year").ToNullableInt();

It is a reasonable solution. But you would have to write those extension methods for every nullable data type.

A single function version that handles all data types plus basic conversion but also is slightly slower looks something like this:

           private static T Get<T>(this SqlDataReader reader, string index, T defaultValue = default(T))

          {

                    var t = reader[index];

                    if (t == DBNull.Value)

                                return defaultValue;

                   Type type = typeof(T);

                   if (type.IsGenericType && type.GetGenericTypeDefinition() == typeof(Nullable<>))

                   {

                               var subType = Nullable.GetUnderlyingType(type);

                               return (T)Convert.ChangeType(t, subType);

                   }

                   return (T)System.Convert.ChangeType(t, typeof(T));

           }

This would be called like this:

book.Year= reader.Get<int?>("Year");

When microseconds are not the issue, I prefer that solution, but I am always looking for something even better. Ideas? :)

My populator is beginning to take shape

I have been knee deep into my populate project the last days and I truly believes that meta programming is somewhat like LSD. It seriously fucks up your mind.

When you take a step away from your usual garbage in - garbage out project and enter the realm of reflection and generics stuff can be, well, abstract.

I hopefully will finish the project before ending up in an asylum.

In the meanwhile I am happy to see that there will be a Build conference this year. Read all about it here.

I went to the conference last year and loved it, will definitely take a talk with my boss about this one. So far there is no more info than that the registration will start at 8, the 8th day in month 8. Why are developers so beautifully nerdy? :)

Now back into the code again! See you!