Sleep

All Thursday night and Friday I was doing a sleep study at Northwestern Memorial Hospital. If you are ever given the choice to do one of these, then try to avoid it. It's horribly boring, and you won't get as much sleep as you think you will. (Though you probably wouldn't be doing one if you were sleeping properly anyway).

Description Logic

Knowing that I'd have a lot of time on my hands, I brought some reading material that I've been procrastinating about for some time: The Description Logic Handbook and a printout of The SPARQL Query Language for RDF.

Some of my thoughts on SPARQL bear going into in detail, so I'll write about that in a separate post.

I have the Description Logic (DL) Handbook in electronic form, and I've only really browsed it in the past. However, I figured that I should really get into it, and have now discovered how vital it is to a proper understanding of description logics - including RDF-OWL. I already knew a lot about this area from all the papers I've read in the last couple of years, but this book is filling in a lot of the gaps, including those I never knew I had. You didn't think that those logic equations in previous posts were things I made up on my own, did you? They were from the start of Chapter 3, which is the chapter I was reading while in the hospital.

The book is useful in a few different ways. Other than providing a basic understanding of a lot of principles, it reads very much like a literature review on various topics in knowledge management. Fortunately, this means that it also cites references (since I need to cite original sources when I finally get my thesis written, and I could hardly cite a textbook).

Each chapter is written by someone who is an expert in that particular area, which is both good and bad. It's good, in that the complete story is told, but it's bad in terms of consistency of the chapters. For instance, I found chapter 2 to be highly accessible, while chapter 3 was a real slog. Part of my difficulty with chapter 3 was that the topic is about complexity of reasoning, whereas I only possess a general understanding of complexity.

As an engineering undergraduate I learnt how to determine complexity for constant, linear, logarithmic and exponential algorithms, but that was about it. From cryptography (and it's relevance to Shor's and Grover's algorithms in quantum computing) I learnt about NP-complete problems (and the question of P=NP: the solution of which would make a good techno-thriller in my opinion). In just the last couple of years I've learnt about more of the various complexity classes, especially in relation to logic reasoning. However, I've avoided getting into a deep understanding of these, in lieu of more pressing reading. I'm starting to wonder if I can really afford to take that approach. At the very least, I should probably read the various Wikipedia articles on each class, though I may need to devote the time to read Complexity Theory: A Modern Approach.

Even considering my shortcomings in complexity, I still found chapter 3 of the DL Handbook to be difficult. The proofs and lemmas often refer to back to propositions made several pages before, after the context has been lost. This makes it look like variables and concepts have been introduced at random. For instance: Therefore G={....}, which is equivalent to C_T. Huh? What's C_T? Oh, here it is... 3 pages ago.

A few times I had to re-write the proof, so that the various substitutions could all be seen in the context of one another.

Many of the so-called proofs were also supposed to demonstrate a particular complexity, but what they really did show a length of a chain in a structure. It was left up to the reader's own understanding of complexity to understand that this would therefore lead to a particular complexity class. I understood this, but was unable to see the relationship myself, due to my lack of background in complexity. Considering that this is a book on logic, and when compared to the other chapters, I found this one chapter to be quite obtuse. Hopefully I won't encounter many more like this one.