Monday, September 13, 2004

It turned out that the iterators for JRDFmem were not removing items correctly. This first showed up as entries in the index with a subject pointing to a set of predicates, with one of the predicates pointing to nothing.

The problem was due to "super" iterators being moved on immediately after the lowest level iterator (the item iterator) was moved. While this worked fine for normal iteration, it does not work for removal, as the super iterator will have moved on before a remove() can be called on it.

Early in the day I thought I could fix the problem by storing the old position and using this old value for deletion, but this was not carefully thought out, and it kept failing on corner cases. In the end I realised that I can only move the super iterators just as the item iterator is about to be moved. This required some restructuring of OneFixedIterator and TwoFixedIterator. Ironically the code ended up being simpler and smaller. Now that I think about it, perhaps that isn't so ironic. After all, the correct solution is often simpler and smaller.

Unfortunately, this took me until 11:30pm to get right.

There's lots to be done in only a short time for Kowari and TKS. Looks like I'll be leaving the problem of using non-existent URIs and instead getting distributed queries going with the (now working) resolvers. Hopefully I'll get some sleep in the next few weeks...

I had a conversation with Bob today about 1.5 order predicate logic. We started out by discussing what is possible with Prolog versus OWL. He demonstrated how OWL is incapable of describing a "Square" as a subclass of "Rectangle", while this is easy in description logic:

  Square(s) :- Rectangle(l,w), l = w, l = s
Conversely, existential quantifiers are expressible in OWL Full, but not in description logic.

In the course of this discussion he attempted to show me an example of a class system, and proceeded to write up a set of tables which were capable of holding both the class definitions (eg. domain and range on a property) as well as instances of the classes. While these tables wre complete, I was nonetheless struck by how well RDF is able to express the same thing. When I re-wrote the data in RDF it became far more intelligible.

Bob wanted to show me what was possible with first order predicate logic, and what is possible with second order. The idea is that a very useful subset of second order predicate logic exists which can be used to express almost everything from OWL Full. This is often referred to as 1.5 order predicate logic.

It was while going through the kinds of information required from a graph that I was able to demonstrate that iTQL is already able to do everything from first order logic, and many things from second order. Since there are a couple of things that we have yet to nail down for iTQL Bob has suggested that I look at exactly what it required for second order logic (or at least, the 1.5 order subset required to express OWL Full), and compare that to what iTQL is capable of. For those constructs which are still required it would be worthwhile considering how they could be incorporated into the language. If they cannot be added, then what would be lost (it may be insignificant) and if they can be added, then what would be the tradeoffs. Obviously this has implications for the DAWG as well. If I can pull it off effectively then it will help us to evaluate the DAWG language and compare it to what we have in iTQL. It will also help us nail down just what iTQL needs.

This doesn't sound too hard. After all, I have 2 years, part time, and I don't have to actually implement the language. Yet Bob thinks that it would make a decent Masters project. Obviously there's more to it that I realise!

Note that I've been talking about OWL Full here. Bob pointed out that just because a system is undecidable does not mean that it is useless. Turing complete languages (such as Java or C) are not guaranteed to complete (while(true) {...}) and yet these languages are still quite useful. Programmers just have to be careful that their constructs terminate. Conversely, decidable systems are not always useful. Databases are guaranteed to be decidable, and yet they may take a week to execute a query (I spent many nights as a student being paid to monitor a machine that was doing just that), and might run out of memory before the query is complete.

For this reason, Bob thinks that an OWL Full implementation would be quite useful. Given that I've already been thinking along these lines, then I was only too happy to agree. I'll just need to convince database administrators that an undecidable data access language is a good idea.

No comments: