Work
Since I'm working on commercial software now I'll be doing a lot of logging on the company's internal Wiki instead of here. I'll continue to talk about Kowari or study in here, but there are only so many hours in the day!

Remote Servers
As part of what I'm doing this week, I need to talk to a Wordnet RDF set. With my poor little notebook struggling on all the tasks I'm giving it, I figured that it made more sense to put the Kowari server on my desktop machine (named "chaos"). Unfortunately, I immediately hit a problem with RMI that had me stumped for some time today.

Starting Kowari on the desktop box worked fine. Querying it on that box also worked as expected. But as soon as I tried to access the server from my notebook I started getting errors. Here is what I got when I tried to create a model:

create ;
Could not create rmi://chaos/server1#wn
(org.kowari.server.rmi.RmiSessionFactory) couldn't create session factory for rmi://chaos/server1
Caused by: (ConnectException) Connection refused to host: 127.0.0.1; nested exception is: 
java.net.ConnectException: Connection refused
Caused by: (ConnectException) Connection refused

My first response was confusion at the connection attempt to 127.0.0.1. Trying to be clear on this, I changed the request to talk directly to the IP address:

create ;
Could not create rmi://192.168.0.253/server1#wn
(org.kowari.server.rmi.RmiSessionFactory) couldn't create session factory for rmi://192.168.0.253/server1
Caused by: (ConnectException) Connection refused to host: 127.0.0.1; nested exception is: 
java.net.ConnectException: Connection refused
Caused by: (ConnectException) Connection refused

I started to wonder if this was a problem with a recent change to Kowari's code (which was a scary prospect), and started looking more carefully a the code, and the logged stack traces.

The clue came from the client trace:

Caused by: java.rmi.ConnectException: Connection refused to host: 127.0.0.1; nested exception is:
java.net.ConnectException: Connection refused
at sun.rmi.transport.tcp.TCPEndpoint.newSocket(TCPEndpoint.java:567)
at sun.rmi.transport.tcp.TCPChannel.createConnection(TCPChannel.java:185)
at sun.rmi.transport.tcp.TCPChannel.newConnection(TCPChannel.java:171)
at sun.rmi.server.UnicastRef.invoke(UnicastRef.java:101)
at org.kowari.server.rmi.RemoteSessionFactoryImpl_Stub.getDefaultServerURI(Unknown Source)
at org.kowari.server.rmi.RmiSessionFactory.(RmiSessionFactory.java:132)
at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:39)
at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:27)
at java.lang.reflect.Constructor.newInstance(Constructor.java:274)
at org.kowari.server.driver.SessionFactoryFinder.newSessionFactory(SessionFactoryFinder.java:188)
... 13 more
Caused by: java.net.ConnectException: Connection refused

So the problem appears to be a connection to the local system, which isn't running a Kowari instance, so it fails. The error was occurring in the RmiSessionFactory constructor, but this seemed OK, and the stack above and below it in the stack trace was all Sun code. So what was happening here?

The relevant code in the constructor looked like this:

  Context rmiRegistryContext = new InitialContext(environment);
  // Look up the session factory in the RMI registry
  remoteSessionFactory =
    (RemoteSessionFactory) rmiRegistryContext.lookup(serverURI.getPath().substring(1));
  URI remoteURI = remoteSessionFactory.getDefaultServerURI();

The failure happens on the last line here.

What is the process, and how is this failing? Well, it starts by looking up a name server to get an RMI registry context. The important thing to note here is that this works. Since the RMI registry is running on the server rather than the client, then we know that it spoke to the remote machine and didn't try to use 127.0.0.1. So far, so good.

Next, it pulls apart the path from the server URI and looks for a service in the RMI registry with this name. In this case the name is the default "server1", and the service is a RemoteSessionFactory object. This also works.

The problem appears on the last line when it tries to access the object that it got from the registry. For some reason this object does not try to connect to the machine where the service is to be found, but instead tries to access the local machine. So somehow this object got misconfigured with the wrong IP address. How could that happen?

Since nothing had changed in how Kowari manages RMI, I started to look at my own configuration. Once I saw the problem, realised how obvious it was. Isn't hindsight wonderful? :-)

Nameservers
Once upon a time I ran Linux full time on Chaos. This meant that I could run any kind of service that I wanted, with full time availability. One of those useful services was BIND, allowing me to have DHCP dynamically hand out IP addresses to any machine on my network, and address them all by name. Of course, BIND passed off any names it hadn't heard of to higher authorities.

However, obtuse hardware, Windows only software, and expensive VM software that suddenly stopped working one day (it died after the free support period ended, and no, I can't afford support), slowly took their toll. I finally succumbed and installed that other OS.

Once Chaos started rebooting, I could no longer rely on it for DHCP or BIND. DHCP was easily handled by my Snapgear firewall/router, but I was left without a local nameserver.

New computers to my network are usually visitors wanting to access the net. This doesn't require them to know my local machine names, nor do my other machines need to access them by name. So I figured I could just manually configure all of my local machines to know about each other and I'd be fine. This is where I came unstuck.

The problem was that I had the following line in /etc/hosts on Chaos:

127.0.0.1  localhost chaos

I thought this was OK, since it just said that if the machine saw its own name then it should use the loopback address. I've seen countless other computers also set up this way (back in the day when people still used host files). For anyone who doesn't know, 127.0.0.1 is called the "loopback address", and always refers to the local computer.

This confused RMI though. When a request came in for an object, the name service sent back a stub that was supposed to connect to a remote machine named "Chaos". However, to prevent the stub from looking up the name server every time, it recorded the IP address of the server instead of the server's name. In this case it looked up /etc/hosts and discovered that the IP for that "chaos" was 127.0.0.1. The object stub then got transferred across the network to the client machine. Then when the client tried to use the stub, it attempted a connection to 127.0.0.1 instead of to the server.

The fix was to modify /etc/hosts on Chaos to read:

127.0.0.1  localhost
192.168.0.253  chaos

So now the stub that gets passed to the client will be configured to connect to 192.168.0.253. This worked just fine.

So now I know a little more about RMI. I also know that if I ever get any money, I really want a spare computer so I can boot up Windows and not have to take my Linux server offline to do it.

Logic
Work is keeping me busy in Chicago at the moment. That's not to say that I'll write more when I get home, but I hope I will.

Yesterday I was in a meeting being told about the semantic products provided by Exeura. Exeura is a commercialization spin off from the University of Calabria, so many of the products are using new technologies that are not fielded commercially elsewhere yet. In the course of the meeting, one of the products was described to be based on "Disjunctive Logic". When queried on this, the explanation was that Disjunctive Logic is a type of logic used commonly around the world.

Now I know there are a lot of logic families, but I hadn't heard of this one. So I went looking. Funnily enough, most of the useful references I found were publications from the very people at Exeura. That's not to say they invented Disjunctive Logic, but they are some of the co-authors of the DLV project, which is one of the only disjunctive logic processing systems. I'll confess that this made me a little cautious about it's readiness for commercialization, but I'll have to reserve judgment until I see it.

I looked up Disjunctive Logic to try to learn what makes this branch of logic special. The first paper I decided to read was co-authored by the same people at Exeura, so at least I knew I'd be looking at the same thing. Almost straight away I saw the following:
Disjunctive logic programs are logic programs where disjunction is allowed in the heads of the rules and negation may occur in the bodies of the rules.

That's when the little light came on for me!

Everything I read over the next few pages was exactly what I expected to read. This is because I've been running into this all the time recently. I've been using cascading equations in ordinary description logic in order to avoid disjunctions in the heads, and here is a tool that is specifically designed to allow for that. I still have to read all the details, but I can see how useful this could be.

Sudoku
The first example of disjunctive logic that I can think of is in a non-trivial game of Sudoku. I first played this 2 weeks ago, discovering quickly that it was just a simple logic puzzle. I expect that most programmers were like me, and immediately started thinking about how to solve the puzzle with a computer program. It seems to come down to 3 simple rules, and I've noticed that the "harder" the puzzle (according to the rating system in the book I have), the more of the rules you have to employ in order to solve it.

I use the name "group" for all the squares in a 3x3 grid, a row, or a column. I'll do that here for clarity.

It's my third rule which is relevant to disjunctive logic. It states:
If there are n squares in a group which contain exactly the same n possible numbers, then those numbers are not possibilities in any other square of that group.

(Actually, there's a corollary: If there are n squares in a group which contain at least the same n possible numbers, and those n numbers appear in no other squares of the group, then any other possible numbers in those n squares may be eliminated)

So what is this saying? For instance, consider a column with several empty squares. For two of these squares we've determined that they could only be the numbers 2 or 3. That means that we know that if the contents of one square is a 2, then the other must be a 3, and vice versa. However, which don't yet know which way around. However, this is enough to tell us that no other square can be a 2 or a 3. If there were another square which had been narrowed down to being a 2 or a 5, then the 2 can be eliminated, letting us put a 5 in there.

So even though we only had partial information of the contents of 2 squares (we knew the numbers, but not which way around to put them), it was still enough to tell us how to fill in another square. This is a case of disjunctive logic, as our result (the head of an equation) was an OR between two possibilities, but this was still enough to solve for the body of the equation.

OWL
This also works with OWL, particularly the cardinality questions I was struggling with some time ago.

If a class has a restriction:

  <owl:Class rdf:ID="MyClass">
    <owl:intersectionOf rdf:parseType="Collection">
      <owl:Class rdf:ID="MyOtherClass">
      <owl:Restriction>
        <owl:onProperty rdf:resource="#myProperty"/>
        <owl:maxCardinality>2</owl:maxCardinality>
      </owl:Restriction>
    </owl:intersectionOf>
  </owl:Class>

Then objects of type MyClass can only refer to two objects with the myProperty predicate. So if I have the following:

  <namespace:MyClass rdf:about="#myClassInstance">
    <myProperty rdf:resource="namespace:A"/>
    <myProperty rdf:resource="namespace:B"/>
    <myProperty rdf:resource="namespace:C"/>
  </namespace:MyClass>

Then I know that two of A, B or C must be the same thing. eg. If A and B are the same:

  <rdf:Description rdf:about="namespace:A">
    <owl:sameAs rdf:resource="namespace:B"/>
  </rdf:Description>

Of course, the possibilities are: A=B or A=C or B=C. (where I'm using = like owl:sameAs).

So this is a similar situation to the Sudoku example. We know there are only 2 objects, but we have 3 labels for them. That means that we have partial information, but like the Sudoku example, the partial information is still useful.

The question is, how do I process this partial information? Until today I had no idea. Now it appears that Disjunctive Logic was specifically designed for this situation. :-)

Of course, this is only relevant if there is useful processing to be done. Unlike Sudoku, OWL can say lots of things with no consequences. For instance, using a predicate more often than specified in an owl:maxCardinality restriction will not create an invalid document unless there are sufficient owl:differentFrom statements to differentiate the objects. It is impossible to violate owl:minCardinality unless the range of the property is too restricted in number (an uninstantiable class, or a class of owl:oneOf). I've talked about this in the past.

So with such an open system, with the extra processing allowed by Disjunctive Logic actually gain me anything? I'm not sure yet. Give me some time to find out.

Work in the USA
There is no technical content here at all, so I hope you're not expecting any. Hey, these are my notes, so I can write about whatever interests me, right? :-)

After my last day with NGC, I still had some things to do before I went home.

Some months ago, Herzum Software from Chicago got in touch with me about doing some work with them. They'd previously been doing business with Tucana, and were interested in Kowari and the inferencing work I've been doing. After several phone calls, etc, these discussions turned into an offer of work, based in Chicago.

I thought about this for a while. There were a lot of reasons to turn them down. Things have been going really well for me this year, and I've been enjoying the opportunity to work for myself, and concentrate on those areas of interest to me. I've also been looking forward to working with Andrae on full time Kowari work. I love the lifestyle in Brisbane, and I've been earning enough that we have been living quite comfortably. Considering this, it seemed like an unnecessary move, particularly with a second baby on the way. In Brisbane we have friends and relatives nearby who can help out.

On the other hand, contracting has its downsides. There is always the concern of finding the next job, and the bank being unwilling the finance the move to a bigger house (no more expensive than what we have, but Australian banks won't talk to someone without a guaranteed income).

I've also wanted the experience of permanent work overseas, and it would be much better to do it while the children are young. The requirement of a visa means that I've have to work for someone else, no matter how much I like my current independence. So it seemed that it would be worthwhile considering their offer.

There were also a couple of opportunities on the east coast of the US. I was interested in these, partly because of proximity to other large companies involved in semantic web technologies, MINDSWAP, friends like DavidW, and quick trips to Europe. However, Anne liked the idea of an architectural city like Chicago, and everyone we spoke to had great things to say about the place (except for the cold in winter).

After swinging back on forth on the idea, I decided to visit Herzum at the end of my trip to help me work out what I wanted to do.

Chicago
This time I flew out of BWI (I couldn't have handled another trip to Dulles during peak hour). I killed a few hours in the bar there with one of the guys from NGC (thanks Clay!), before catching my flight to Midway. As usual, the plane was delayed through bad weather.

Herzum keep their own apartment very close to their office (both are located in the "Loop" in the city), and they'd offered to put me up there while I visited. This was my first opportunity to meet the CTO, Bill, whom I'd been conversing with for some time. He was every bit as hospitable as our conversations had led me to believe.

I spent the Friday talking with the developers, discussing what it is that they do, while also discussing aspects of RDF and semantics that may be of benefit to them. In general, I was impressed with everything I heard.

There did appear to be a singular focus on the design paradigms set out in the book written by the company founder Peter Herzum (who was travelling at the time, and not available to meet, unfortunately). However, it also made sense that this would be the case.

I got an opportunity to have lunch with everyone there, and a few of them took me out to dinner nearby as well. Afterwards I was taken on a quick walk up to the Tribune building (quite a famous landmark, and the inspiration for many scenes from "Batman" comics), and got to see some of the other architecture on the way back to the apartment. So far I was having fun. :-)

After a slow start on Saturday, I met with one of the guys to visit "Bodyworks" at the museum, though the tickets were sold out. I still enjoyed getting to see a lot of the sights as we drove about, and we finally went back into town to see the John Hancock building. We had a drink at the bar while admiring the view, and then met another developer to have a late lunch. We then caught a movie and finally headed on home.

I'm glossing over all of this, but I had a great time. More importantly, I quite enjoyed the conversation of the people I was with. They all seemed quite intelligent, and demonstrated a great knowledge of their field. I could definitely learn something from each of them. It is important to me for my co-workers to have these qualities, and it is the reason I enjoyed working at Tucana so much. This reason alone was enough for me to give greater consideration to the position.

Wandering Sunday
I got back to the apartment reasonably early on Saturday evening. Bill had left that day to fly home to California, so I was on my own. I was missing my family and didn't want to be on my own, so I decided to go out to find a bar. I did my best to speak with people in the hope that my accent would land me in some interesting company. :-) This worked out OK, and I met up with quite a few people. I even stopped in at a McDonalds late at night for a snack on the way home (I was already gaining weight on this trip, so why fight it?) ;-) That mightn't seem like a big deal, but I don't normally eat at places like that, and Anne would have roused on me. As a point of trivia, I discovered later that this McDonalds was one of the largest in the world (It did sort of seem large at the time!)

Sunday morning I was supposed to meet up with Luigi, the VP at Herzum, who had just arrived back in town. He had to catch up with family, so he suggested that I go up to Lincoln Park to look around at a potential place to stay if we move over (I don't know if we can afford it, but it was worth a look anyway). I walked down to "State and Lake" to catch a train north, and then walked east towards the park.

I tried dropping into a general store for a light snack for lunch, but I was disappointed to discover nothing more nutritious than Twinkies and crisps. I really hope that place wasn't indicative of the general standard of snack food in the States!

I started with the Conservatory at the park, and then moved into the zoo. It was an enjoyable walk, but warmer than I expected Chicago to be. Not as hot as Brisbane gets, but still uncomfortably warm (why did I go into the Conservatory on a day like that? I must have been slightly crazy from walking in the heat!).

Walking along the lake back down to the city I saw just how many people go to the "beach" on a hot day in Chicago. It looked quite inviting, despite the lack of surf. I've never seen anything like the great lakes before, and this more than anything else made Lake Michigan look to me like an "inland sea".

That night I got to meet Luigi for the first time as we went to a nearby tapas bar for dinner.

Home Stretch
Monday was a little quieter. After packing, I went down to Herzum's office where I spent my morning talking with some of the staff and looking at Peter's book. Luigi went through some of the details of the offer, but at this stage I wasn't sure that it looked all that good. Besides, I was tired and missing my family, so I didn't trust myself to make a decision (though any decision to take the job would need agreement from Anne!).

Steve, the CFO, took me to lunch, and then I was off to the airport to get home (thanks to Dan for making sure I caught the right train to get to Midway on time).

I met some nice people on both flights home. On the Midway-LA flight I met an Ironman triathlete (I look up to these guys) who told me about the XTerra series, one of which she had just competed in. And crossing the Pacific I met a Melbourne lady I've now become friends with who's husband is about to take a job in the triangle are in North Carolina (one of the few places in America that I've been to).

Job
Since getting home I've spent quite a bit of time just trying to get over jet lag and spending time with Luc. This is one of the reasons why my blogging has been so sporadic recently.

After some further talks with Luigi, Anne and I decided that I should take the job. This is a big deal, and has us both a little intimidated!

To start with, I'm a contractor working remotely with Herzum until I can get a visa to become a full time employee. Fortuitously, Australians are now eligible for an E3 visa, instead of the old H1-B, which should make things a little easier for us (it will let Anne return to work eventually). All the same, the visa application will take a little while, so we have to wait while that comes through.

Part of my agreeing to the position was that we wouldn't have to move until January. This is just because the baby is due on the 3rd of November. For reasons of both cost and family support we definitely want to have it here in Brisbane. We're told that we shouldn't be making a major move with a newborn for at least 6 weeks, which takes us right into Christmas. Even if we wanted to move then (which we don't), it would be insane to try it during the peak travelling season. So we'll spend a couple of weeks seeing each of our families over Christmas (they will want to spend time with the grandchildren before we go overseas) and then move to Chicago in the first week of January. What a wonderful time of year to move to Chicago! :-)

In the meantime, I'm learning as much about Herzum as I can, and also looking into some of the software I may be working with. I'll continue to blog, but since I'll be working with commercial systems I may have to narrate in generalities. I don't expect things to be a real problem, as part of my work will be on open source systems (such as Kowari, or Lucene) so I should still be able to make comment on what I find.

I already have a few things to say about what I've been reading lately, but given the current late hour, I'll leave that for another time.

Out of Hours
The rest of my week was almost as busy as the time I spent elucidating Kowari.

On Tuesday DavidW and I went down to the University of Maryland's MIND lab to meet some of the MINDSWAP group. We were shown a very impressive demonstration of ontology debugging in Pellet, using a couple of different methods labelled white-box debugging and black-box debugging. As the names imply, the white-box method carefully follows the reasoning used by Pellet, while the black-box method looks at inputs and outputs. I'm not sure how much of this could be automated, but as a tool for debugging it was really impressive. It was enough to make me consider hooking Kowari into the back end of Pellet.

In fact, hooking Pellet into Kowari has a couple of things going for it. First, it gives me a point of comparison for my own work, both in terms of speed and correctness. Ideally, my own code will be dramatically faster (I can't see why it wouldn't be). However, having followed Pellet for a little while, I'd expect it to provide a more complete solution, in terms of entailment, and particularly with consistency. The second reason is to provide a good set of ontology debugging tools.

Kowari Demo
I was also asked to give a demonstration of the new rules engine in Kowari. I'd been running it for a couple of weeks at this point, and trusted it, but it still made me nervous to show it to a room full of strangers, all of whom understand this stuff. Everyone seemed happy, but it gave me a little more motivation to get back to work on completing the implementation.

Fujitsu has a lab upstairs from MINDSWAP, and a couple of their people had asked to come along to meet me. While we were there, they asked me several questions about how to make Kowari load data quickly. It seemed that they were sending insertions one statement at a time, so we suggested blocking them together to avoid some of the RMI overhead. They also invited me back the following day to see what they've been doing.

OWL for Dinner
Afterwards, DavidW and I went to dinner with Jim Hendler. Nice guy, and he was quite happy to answer some of my questions about RDFS and OWL. The one thing I remember taking away from that night was a better understanding of the agendas of the data modellers and the logic people participating in OWL. This culminated in the explanation that RDFS is that part of OWL that everyone could easily agree to in the short term, thereby enabling an initial release of a standard for this kind of work. This explains quite a lot.

It wasn't explicitly mentioned, but I sort of inferred that the separation of OWL DL and OWL Full was the compromise arrived at between the ontologists who needed to express complex structures (OWL Full) and the logic experts who insisted on decidability (OWL DL).

Fujitsu
The following night I was back down at the University of Maryland, this time visiting Fujistsu labs.

The evening started with a follow up question about bulk loads. There were two problems. The first was that they were running out of memory with insertions, and the second was the speed.

The memory problem turned out to be a result of their insertion method. It seemed that they were using a single INSERT iTQL statement, with all of the statements as a part of a single line. Of course, this was being encoded as a Java String which had to be marshalled and unmarshalled for RMI. Yuck. As a quick fix I suggested limiting the size of the string and using several queries (this worked), but I also suggested using N3 as the input format to avoid RMI altogether.

The speed problem was partly due to the RMI overhead (it was marshalling a LOT of text to send over the network!), but mostly because the insertions were not using transactions. I explained about this, and showed them how to perform a write in a single transaction. The result was a speed improvement of an order of magnitude. I'm sure that made me look very good. :-)

While there I was also shown a project for a kind of "ubiquitous computing environment". This integrated a whole series of technologies that I was familiar with, but hadn't seen together like this before.

The idea was to take data from any device in the vicinity, and direct it to any other device that was compatible with the data type. Devices were found dynamically on the network (with Zeroconf, IIRC) and then queried for a description of their services. These descriptions were returned in OWL-S, providing enough info to describe the name of the service, the data formats accepted or provided by the service, URLs for pages that control the service, and so on. They even had a GUI configuration tool for graphically describing a work flow by connecting blocks representative of the services.

As I said, there was no new technology in this implementation, but it's the first time I've ever seen anyone put it all together and make it work. The devices they had working like this included PDAs, desktops, intelligent projectors, cameras, displays, databases, file servers and telephones. It looked great. :-)

Final Week
Once making it to the final week, the plan was to go through the remaining layers of the storage code, and use any remaining time to go through examples and questions.

There are three main areas components of functionality in Kowari's storage layer: The node pool, the string pool, and the statement store. Once upon a time these three operated together, but now the statement store is off on its own behind the new Resolver interface, while the node and string pools are accessible to the whole system. However, their unified functionality has not changed.

All three components handle transactions autonomously, managing the phases of all their underlying components. The overall Session class uses a two-phase commit operation to keep the transactions of each component in synch with the others. It is also in these top level components that the files are all managed. The files which are created and manipulated at this level are generally used by the classes at lower levels (for instance, the BlockFiles and IntFiles which are used by FreeList and AVLTree) but there are also other files which handle session locking, and persistence of phase information for the transactions.

Once I'd reached this level, I had all of the information needed to explain the data formats in each file. It was awkward to explain the structures before this stage, since several important structures (notably, the phase information) contain information from every layer. Trying to describe a single layer leaves large holes in the structure, and has led me into confusing conversations in the past when I try to skip over these holes. But at this point I was finally able to write up the file structures, one byte at a time (the values are typically 64-bit longs, but ints and bytes are occasionally used).

I'd like to properly document each of these components, along with the associated file formats, but for the moment I'll just give an overview.

Node Pool
The idea of the node pool is to allocate a 64-bit number to represent each resource in the RDF data. We call these numbers "graph nodes", or just gNodes. GNodes get re-used if they are freed. The re-use is for several reasons, the most notable being to prevent an numeric overflow (it also helps the string pool if there are few holes in the address space for nodes). However, a resource ID cannot be re-used if there are any old reading phases which still expect the ID to refer to the old data.

These requirements are exactly met by a FreeList, so the node pool just a FreeList along with all the code required for file management and transactions.

String Pool
The string pool holds all of the URI References and Literals in the database. When it was first written, the only literals we stored were strings, and since URI's are also represented with a string, we called the component the "string pool". The string pool stores lots of other data types as well, but the name has stayed.

The string pool provides a mapping from gNodes to data objects, and from those objects back to the gNode. It also provides a consecutive ordering for data so that it can be used to easily work with a range of values.

The mapping of a gNode to the data is done with a simple IntFile. Each data element can be represented with a buffer of fixed length (overflows for long data types such as string are stored at a location referred to in this buffer). To find the data buffer for a given gNode, the gNode number is multiplied by the record size of the buffer. This is why the string pool prefers the node pool to re-use gNodes, rather than just incrementing a counter. Given that these records are all the same length, I'm not sure why a BlockFile was not used instead of an IntFile, but the effect is the same.

The mapping of data back to the gNode is accomplished by putting all data into an AVLTree. The records in this tree are identical to the records in the IntFile, with an addition of the gNode to the end of the record. The tree also provides the ordering for the data. This allows strings to be searched for by prefix, URIs to be searched for by domain, and date or numeric ranges to be found.

One problem with this structure, is that it is impossible to search for strings by substring or regex. This is why we have a resolver for creating Lucene models. However, it's been in the back of my mind that I'd love to see if I could build a string pool based on a trie structure. (Maybe one day).

The data structure holds up to 72 bytes in the record. Anything longer than this (typically a string) has the remainder stored in a separate file. We have a series of 20 files to handle the overflow, each storing blocks twice the size of the blocks in the previous file. This lets us have random access to the data, while reducing fragmentation. It also allows us to store data objects of up to several GB, though we don't expect to ever need to handle anything that large.

When the string pool and node pool are combined, they provide a mechanism for storing and retrieving any kind of data and associating each datum with a numeric identifier.

Statement Store
The statement store is the heart of Kowari's approach to storing RDF.

Each RDF statement is stored as a quad of the form subject, predicate, object and model. We originally stored a triple of subject, predicate, object, but quickly realised that we needed the model (or graph) element as well. Again, the interfaces already existed, so the statements are referred to throughout the code as triples rather than quads.

These statements are stored in 6 different AVL trees, with each tree providing a different ordering for the statements. I've already discussed the reason for this at length. Ordering the statements like this allows use to treat the storage as an index.

Of course, the representation of the statements is with the gNode IDs for each resource, rather than the resources themselves. This means that the indexes contain numbers and nothing else.

While simple in principle, the code here is actually quite complex, as it has numerous optimisations for writing to multiple indexes at once. Unfortunately for me, several of these optimisations were introduced after I last had a hand in writing the code, so it needed a little effort for me to understand it sufficiently to explain it to others.

Each of the indexes is handled by a class called TripleAVLFile. This class knows about its required ordering, and manages its own AVLFile. The nodes in this tree actually represent a range of RDF statements, with a minimum, a maximum and a count. By handling blocks of statements like this, the overhead of maintaining the tree is reduced, and searching is increased by a significant linear amount (since it's linear it doesn't show up in a complexity calculation, but this is the real world we're talking about, so it matters). Once the correct node in the tree is found, then it contains a block ID for a block in a separate ManagedBlockFile which contains all of the RDF statements represented by the node.

The 6 TripleAVLFiles manage both their trees and the files full of blocks (the AVLFile and the ManagedBlockFile). This is simple enough when simply reading from the index, but takes some work when performing write operations. Trying to insert into a full block requires that block to be "split" in a similar way to node-splitting in B-trees, but with co-ordination between the AVL tree and the block file. Writes are also performed in a thread owned by the TripleAVLFile, so that multiple modifications to a single location in the index can be serialised rather than being interspersed with writes to the other 5 indexes.

The details of these and other optimisations makes this code a complex subject in itself, so I'll leave a full description for when I get around to proper documentation. I should comment that each of these optimisations were only adopted when they were proven to provide a benefit. Complexity can be the bane of performance, but DavidM did his work well here.

Reads and writes are managed by the statement store, with reads being directed to the appropriate index, and writes being sent to all 6 indexes. The other job of the statement store is to manage transactions, keeping all of the indexes reliably in synch.

Integrating
A description of the storage layer is completed by describing how the Node Pool, the String Pool, and the Statement Store are all tied together.

When a query is received by the server, it must first be localized (I'm using the American "z" here, since the methods names use this spelling). This operation uses the String Pool to convert all URIs and literals into gNode numbers. If an insert is taking place, then the Node Pool is also used to allocate new gNodes where needed.

A query's principal components are a FROM clause (which is an expression containing UNIONS and INTERSECTIONS between models) and a WHERE clause (which is an expression of conjunctions and disjunctions of constraints). Each constraint in the WHERE clause may have a model specified, else it will operate on the expression in the FROM clause. To evaluate a query, the FROM and WHERE expressions need to be merged. This results in a more complex constraint expression, with each constraint having its model specified. The operations in the FROM clause get transformed into disjunctions and conjunctions in the new constraint expression, hence the increase in complexity for the expression, though the individual constraints are still quite simple.

The server then iterates over the constraints and works out which resolver should be used to evaluate each one. In most cases, this is the "System Resolver" as defined by the PersistentResolverFactory tag in the kowari-config.xml file. By default, this is set to the Statement Store described above.

Once the resolvers for each constraint are found, the constraints are sent off to be resolved. The Statement Store resolver tests the constraint for the location of variables, and uses this to determine which index is needed. It finds the extends of the solution, and returns an object containing this information and a reference to the index, so that the results can be extracted through lazy evaluation.

Next, the results are "joined" according to the structure of the constraint expression. These operations are done with lazy evaluation, so it is not quite as simple as it sounds, particularly when optimisation is considered, but the method calls at a higher level are all straightforward (as you'd expect).

The final results are then globalized by using the String Pool to convert all the numbers back into URIs and literals. The globalized answer then gets serialized and sent to the client.

Insertions and deletions use a similar process to what I've just described.

This really glosses over the details quite a bit, but it provides an outline of the process, and explains what I was doing for most of the week. When I get time I hope to document it properly, at which point this post should help by providing me with an outline.

End of the Week
OK, so I've written about a lot of the first week, but there is still a bit to go.

Towards the end of the week I took a step back and tried to present an overview of a query, giving some perspective on how BlockFiles and FreeLists sit at the bottom. Once I'd done that I dived back into the details again, this time going into ManagedBlockFile.

ManagedBlockFile is actually pretty simple, as it simply wraps a BlockFile and a FreeList. It uses the FreeList to allocate and release Blocks inside the BlockFile. This is very important at higher levels, where blocks need to be re-used where possible, but should also be consistent from one phase to another.

Sitting on top of ManagedBlockFile comes AVLTree and AVLNode. These manage the structure of Kowari's AVL trees, and define the whole phase-tree concept. All of the work is done in AVLNode, while AVLTree stores the root of the tree, and manages the phases. It was while describing the phases at this level that people finally started to "get it". We're planning on abandoning phase trees for the XA2 data store so that we can have multiple writers at once, but phase trees are still pretty cool. Once the concept was explained, then the people who'd been frustrated at the single-writer restriction suddenly expressed admiration for the way the system works. It was DavidM's idea to use phase trees (not mine), but I did help write the code, so it was nice to get such positive feedback. :-)

Going through the details of AVLNode started getting quite laborious, so I think everyone was grateful when we got to the end of the week. Fortunately, at this point all of the utility classes were described, meaning that I could get into the higher level architecture as soon as we got back on the following Monday.

Evenings
I had hoped to get a bit of programming done during my evenings, but somehow it didn't work out that way. One night was spent trying to organise flight changes at the end of my trip and doing laundry. Another evening was spent catching up with DavidW.

One of the most interesting evenings was spent over drinks with a couple of people from Mantech, including Greg who'd been paying me for the previous 6 months. This was my first chance to meet anyone from Mantech, so it was a real shame that the evening could not have gone on a little longer than it did. Working remotely reduces the amount of feedback you get, so I was pleased to hear that Greg was happy with my work to that point. You can run into periods of self doubt when working on your own (a phenomenon I've often heard PhD student complaining about), and it really helped to hear someone appreciating what I've done.

The other thing I did in my evenings was to use an iSight camera and iChat to talk to Anne and Luc while they had breakfast. H.264 dynamically sacrifices clarity in order to keep the framerate up, which gives a nice, natural feeling interface. It doesn't really bother me (too much) when things go blurry, but systems that give clear pictures with large delays between them don't feel like you're in direct communication with the person at all. So I really like iChat, though there were occasions when the bandwidth into the house in Brisbane was painful. Telstra's broadband network does leave something to be desired on occasion.

I was missing Anne and Luc a lot, but being able to see them helped a little. Luc thought it was great too, though it took a while to convince him that this was not like the TV, and that he could interact with me. We finally managed it when Anne tickled the screen, and I squirmed like she was really tickling me. He thought that was hilarious. :-)

Second Weekend
Anticipating the coming weekend, I drove to Circuit City (Google Maps are great for finding that kind of thing), and bought a new camera. I'd forgotten to bring ours from Australia, and besides it was starting to show signs of age. My criteria was an ability to take longish videos, a short delay from button press to shutter release, and a small size (so it's not awkward to take around as a tourist). I found what I wanted in the Casio Exilim EX-S500. Fortunately it wasn't too expensive (though I used up the last of my credit card to get it). It was nice enough to elicit a few comments from the people who saw it on Friday morning (I enjoy showing off new toys).

With work over on Friday, I had to drive down to Dulles (and I started right next door to BWI! Talk about frustrating!) to catch an evening flight to Pittsburgh. Despite doing the drive during peak hour traffic and in heavy rain (I was listening to local flash flood warnings coming over the radio), I made it with some time to spare. I then waited a couple of hours for a flight that was delayed due to bad weather. :-)

From Pittsburgh to Salem, OH, by car. From here I enjoyed a weekend of rural America with DavidW and his family. Despite some unforeseen problems, I enjoyed the weekend, and I might even try to make it back for the 200th anniversary parade next year. Then it was a road trip back to Virginia on Sunday, and a drive up to Baltimore on Monday morning for work.

So by Monday morning I was feeling pretty tired, and I had only just made it past the halfway point in the trip!

Trip
It's been a couple of weeks now, and the details are fading, but I'll give a brief run down on what happened while I was away...

Nothing Technical (yet)
Of course, the Brisbane to LA trip was the hard part. I woke up at 4:30am Wednesday morning with Luc being sick. I thought that his irritability was just a reaction to the natural stress of preparations for my trip, but he cheered up immensely as soon as he threw up all over me. :-)

I made the mistake of reading and watching movies for the first part of the trip (I got to see "Robots" at last). So by the time I decided to do some "work" on my notebook I was too tired to think clearly. Sure, I can work while I'm tired, but I'm only really effective if I'm already in the middle of something. Picking up the notebook from a cold start just didn't work. I did some Javadoc, but that was about it. After that I went back to books and movies. This continued into my flight from LA to D.C.

The Atlantic flight was delayed a little, so I barely had time to clear customs and run across the airport to my next flight. I made the flight, but my luggage didn't. That was unpleasant when I got into Dulles. All I wanted to do was clean up, and get a change of clothes, but I had to wait for several hours first. By the time I landed it was 5:30pm on Wednesday (same day, since I'd crossed the dateline). I'd been in the air for over 18 hours, and I'd been up for 29 hours straight. I'm glad I don't do that trip too often!

The second day was at a relaxed pace, though it was a little depressing hearing about the bombings in London that morning. A couple of years ago I spent a month travelling in the London tube every day, and it's hard to imagine something so catastrophic imposing on such an everyday thing. I checked out of the hotel, went back to the airport and picked up a rental car (they "upgraded" me to an SUV. Yuck). Then I was off to David and Bern's place to use their internet and catch up on news. I also rang my brother Rowan, which ended up having consequences for the weekend.

That afternoon I drove to Baltimore through torrential rain, on roads I'd never seen before, on a side of the road that I'm not used to. Thank goodness for MapQuest (though now I've started converting to Google).

Finally, on Friday I started work. The centre was just a couple of hundred meters away, so I could walk down. The day was just an introduction, and an overview of what was to come over the coming weeks. We went over the directory structure of the project, what can be found at Sourceforge, etc.

Things like the directory structure were tricky to explain, because some of it is unintuitive, and I didn't agree with how it should be structured. It's kind of like debating, where you're given a point of view and you have to sound convincing when you defend it, regardless of whether you agree with it or not. I had to do that a few times while I was there. Sometimes the best argument is just that it was someone else's decision, and the benefits in changing it are not worth the effort required.

When I'd spoken to Rowan he reminded me that it was his 30th birthday that weekend, and asked if I could make it down to Houston to see him. I checked out prices, but it was all looking too expensive. When I rang him back to let him know I couldn't make it, I got my sister-in-law instead, and she was able to organise a cheap stand-by flight for me on Continental (where he Dad works). So my first weekend was spent in Houston. I cleared out of work and went to BWI with one of the guys from Florida (he was commuting every week).

At BWI I was singled out for special testing in a booth that shot me with puffs of air (presumably testing for the presence of Nitrogen compounds). It was kind of interesting, and I got through the line just as fast as the people who weren't singled out... only I got to sit down while they looked through my bag. It ended up being less inconvenient for me than if I'd been left in line, since they did all the work searching my bag while I watched. I noticed that most people seemed happier than usual with the delays, probably because of the events in London two days before. As a PR exercise, the TSA seem to be doing a good job. I'll let others comment on their effectiveness.

Houston was fun, and the look on my brother's face when he saw me was priceless (he thought I couldn't come). I enjoy visiting new places, so I had a great time over the rest of the weekend. I should comment though... the quality of Houston's roads is TERRIBLE. I understand why, but you'd think they'd look for a solution.

Sunday night I flew back into BWI for work that week.

Project Structures
Since my task was to describe the storage code at the lowest levels in Kowari, I decided to go with a bottom-up approach. This had advantages and disadvantages, but I hope it worked out OK in the long run. Every so often (particularly when DavidW suggested that he could hear the sound of people's brains frying) I'd step back and try to give an overview, often coming back in with a top-down approach to where we were in the code.

One thing that would have been nice to have, was a diagram of file structure. That would have made it easier to see what the code was trying to accomplish. Unfortunately, I have no idea where the original diagrams would be (they'd be 4 years old by now, and DavidM and myself never thought too much of them, as they were easy enough to work out again), and I did not have enough preparation time to write them out again (plus, I'd have missed a few things if I'd tried).

Most of the code was perfectly familiar, but while showing some of it I discovered a few new features I'd never seen before. It would normally take me a few minutes to work out what something was doing, and I probably floundered a little on occasion, but I'd get through it in the end. I comfort myself with the knowledge that I'm one of the only people who knew enough about the system to be capable of working these things out, even if I didn't know them when I started. By the time I finished presenting a section of the code I ended up understanding it better than I did when I started. Ideally I'd have had enough preparation time to be all over it, but that wasn't available, so I can't really kick myself for not knowing it perfectly. They got a few free hours out of me on most evenings as I refreshed myself on code in preparation for the following day.

Having documented this code, and presented it in nauseating detail, I came away with a very clear idea of every layer for the storage code. This allowed me to write up those diagrams on file structure very easily, during the last couple of days. A couple of people said that they would have liked to see them at the beginning (something I'd already lamented), but I think they all appreciated getting to see them in the end.

Now that I'm back in touch with this code, I've been thinking that I should write up an overview of most of it, and also provide the file structure diagrams. I've since explained it to a couple of people here in Brisbane, and I think I've structured my thoughts on it well enough to build some developer documentation on it. However, that will take some time to write up and I'm about to start a new job, so I won't commit to it all straight away. I'll do what I can.

Block Files and Free Lists
The first week was spent entirely in the util-xa package.

Starting at the bottom, this includes the BlockFile interface, along with AbstractBlockFile, MappedBlockFile and IOBlockFile. These handle files with fixed-length records called Blocks, and transparently hide if the file is being accessed with normal I/O operations, or if it is memory mapped. Almost all files in Kowari are accessed with these classes, with the only exceptions being IntFile from the util package.

On top of this file abstraction is built the FreeList class. This name is a little misleading, as it only describes a single aspect of the class. However, it is there for historical reasons and it's not going to change any time soon.

Free lists are really a resource manager. Resources in this context are identified by a numerical ID. A FreeList will hand out resources when requested, and will collect resources when they are no longer in use. Resources will be recycled whenever possible (there are a lot of reasons for this, regardless of the resource type, but it always comes down to performance), and so the list of "freed" items has to be maintained in order to hand them out again when it is permissible to do so. This internal list of free items is where the class gets its name. A better name would be something like ResourceManager.

The list of free items is kept in a BlockFile. The blocks in this file form a circular, doubly-linked, linked list. It is in this file that the concept of Phase first appears, which is the basis of Kowari's transaction support. At this level, phases are handled as pointers to the first and last freed items within a phase, and a set of heuristics which manage those items which may and may not be re-allocated, according to the currently opened phases.

Phases don't make a lot of sense until the higher level phase trees are examined, but these rely on the functionality of FreeLists so much that it becomes difficult to to describe phase trees without first describing FreeLists. I've tried to do a top down explanation to a few people in the past, but they invariably question how resources are managed between phases. Hence, my approach of describing phases from the ground up, starting with FreeLists.

I'll describe this all in more detail when I document the FreeList shortly. I'll just say here, that this code took the best part of the first full week, and forms the basis of all the storage code Kowari's XA datastore.

Paper
Yesterday ended up being busier than I expected. After I helped Anne and Luc get out the door, I went to town to meet a friend (Hi Brad) for a discussion on Resolvers in Kowari. This took some time, as I also discussed several other things, like my recent trip, etc. Once I get home, I went straight to UQ to meet with Bob. Again, I discussed my trip, and then got down to some of the work I should be doing now that I'm back.

Given my upcoming work, I don't expect to have a lot of time for my research degree. So Bob suggested that I should try to get a paper out of the way as soon as possible. He has a point, so I thought I'd aim for Australasian Ontology Workshop later this year. That gives me about 3 weeks to write something. Anything I write here should be a good starting point for a thesis too, so it will be useful in more ways that one.

My plan is to write about 6 way indexing of quads in RDF, and how this leads to easy constraint resolution. This then forms the basis for set-at-a-time rule operations which can then be used for OWL entailment and consistency checking (by extension of the KAON2 rule work). I'm busy tomorrow, but I'll start trying to write something on Monday.

While visiting the MIND lab, I was really impressed with the ontology debugging work in Swoop. I explained to Bob that while I expect my methods to quickly find an inconsistency, it will never provide enough information to track down complex problems in the same way that Swoop can. I thought that it might be worthwhile to use set-at-a-time processing to work with data on a larger scale, and then drop back to tableaux reasoning (or others) when a problem is discovered, so the source of the problem can be identified.

Funnily enough, Bob thought that this would be enough to write up as an MPhil thesis. I think it's funny, as I always thought Bob wanted me to do a lot more than I've been doing, and now he's suggesting that I need to do less. It's also funny, since I've always been much more interested in entailing new data quickly than in checking consistency. Consistency is important (OK, it's vital), but my purpose for this thesis has always been to entail new data efficiently. I find it ironic to be told that I don't need to do the part that I thought was more important (or more interesting).

Recent Break
I haven't written in a while because of my recent trip to the US. Once I got there I was jet-lagged, but still had to get straight into work. Even after the jet-lag wore off, I was spending my days working, and my evenings were also kept very busy (meeting people, reading code and sleeping). I got back last week, but I've been so wrecked that I've avoided spending too much time on the computer. I've managed to get a few things done (mostly some Kowari support), but haven't yet taken the time to blog.

I have a lot to write at the moment. I want to:

• Document some of what I was teaching in the US.
• Write about what I learnt at MIND lab.
• Talk about what I learnt about RDF and OWL over dinner with Jim Hendler
• Document some of my ideas for storing Java ASTs in RDF (including an API for manipulating the AST, and a dynamic class loader).
• Talk about some of the questions I've been asked about Kowari, and how certain problems should be addressed.
• My visit to Chicago and Herzum Software.
• My future plans for work.

Unfortunately, writing about all of this in one go just seems too intimidating to attempt in one hit. The only way I'll get through any of this material is to take it one piece at a time.

It's late right now, so tonight's entry won't cover anything of significance. I just thought it would be a good idea to write something, simply to make a start. I'm meeting with a couple of people tomorrow, but I should be able to get some time to record something useful.

USA
I hate jet lag. I'm currently 9 hours (and one day) away from home, and I don't feel so good. Hopefully I'll get over it soon.

The flights took me to LA, then on to Dulles in Virginia. I got to relax for a day, then that night drove 2 hours through pouring rain to Baltimore. It was a bit rough given how tired I was. The next day (Friday) I worked until 4pm. At that point I was supposed to sit back and take it easy, but my sister-in-law decided to get me a cheap flight and fly me down to Houston for my brother's 30th birthday. I'm still exhausted (especially after a few drinks and a late night with my brother last night), but it's all starting to slow down for me now.

Hopefully I can have a quiet day tomorrow before flying back to Baltimore in preparation for work on Monday.

Other than the unpleasant physical effects, I enjoy traveling. I still miss Anne and Luc though.

Consistency
I spent most of the trip reading and watching videos, but I did get to write a bit of code. However, it was mostly documentation, so there's no new functionality to report. However, I've had time to re-prioritize what I'm doing, and I expect to do the consistency checks soon. This shouldn't be too hard, so I hope to put them in during my evenings in the coming week.

Consistency will be good for a couple of reasons. The first will be for specific applications to write consistency tests for particular implementations. It will also be useful for implementing OWL. I don't have all the functionality needed for OWL yet (subsumption being the biggest problem), but I can still get a lot done without it. It makes a lot of sense to implement as much of OWL as I can, and then incrementally improve the support.

Tests
All the W3C entailment tests are now scripted, working, and checked in. It's very nice to see. :-)

There are a few caveats to these tests, but that is by design.

First, there are no datatype entailments. I'm not sure what you can entail from a datatype. The only test for it says that the following results in a "False" document:

  <http://example.org/prop> <rdfs:range> <rdf:XMLLiteral>
  <http://example.org/foo> <http://example.org/prop> "<"^^<rdf:XMLLiteral>

I could write a resolver to check this kind of thing, only it would need to create statements like:

  <rdf:XMLLiteral> <tucana:isTypeFor> "<"

But I'm skeptical about working too closely with data types for RDFS, since I may need to consider the different types of literals as well. I may look at this later.

Next is that there are no consistency checks. There are a few reasons for this. Consistency checks don't entail new data (well, you could say that they entail a false document, but no new statements). Next is that I planned on making consistency checks a part of OWL, and hadn't really considered it before now. However, just as I was getting to the last tests I found one which checks that the following is wrong:

  <http://example.org/foo> <rdf:type> <rdf:Property>
  <http://example.org/bar> <rdfs:subClassOf> <http://example.org/foo>

It is supposed to use <rdfs:subPropertyOf> instead. This is actually legal in OWL Full (but not DL). It will be tricky making OWL Full a superset of RDFS if I go testing for conditions like that.

Anyway, I can do consistency checks very easily, and it should only take a day of code. However, they were not a part of what I said I'd do for the moment, so I'll put them off until I get a little time (I actually thought I might get them done on the flight... see how I go).

The only other thing I've avoided in the tests is RDF parsing. However, that is already being done elsewhere, and is not relevant to entailment.

This means that I just need to document the format of the RDF for rules, and I've met my current commitments for this code. I still have to make OWL work, but it's still a milestone, and I feel good for it. :-)

Extras
While doing all the tests I added some minor extras as I went.

• I fixed the Http resolver test that was looking at Sourceforge. It seems that the page changed from html to xml. I'm skeptical of any test that relies on external resources like this, but I can see the usefulness.
• I added an explicit rollback() when the rule insertions fail.
• Added some feedback when rules complete.
• Put in a Dummy Rule loader (at Andrae's request) and made this the default when none is supplied. I couldn't work out how to make the RuleLoader tag optional in the XSD for the configuration file though.
• When using a model as a rule model, check it for rules or axioms. If none are found then report it as a problem.

There are all sorts of extra bit and pieces that I want to get working. I need to prioritize my time, but it would be nice to get some of them done. They include:

• A shortcut command to select all statements from a model (without needing to select the subject, predicate and object and give all three in a constraint as well). This should save on some typing!
• A similar shortcut to count the result of a query. At the moment a count has to be a subquery. When you just want the results of a query that means you need a superfluous model and where clause that has to evaluate to something.
• More detailed results to applying a set of rules (number of rules, number of axioms, number of generated statements).

The problem with these sorts of things is that they can be a distraction from the real work, but they'd be great to have. If anyone else would like these features, then please feel free to implement them for me. :-)

Batteries
I forgot to mention in my last post that I went and bought a couple of batteries for the PowerBook. Three batteries should give me a good chunk of my upcoming trip with access to the notebook. I'm hoping to get some work done (on about three separate projects) as well as get in some movie time. :-) I have a couple of new DVDs that I've wanted to put some time aside for. I'm guessing that watching a DivX is a lot less power-hungry than spinning the drive of a DVD, so I'll convert them to DivX first. Kind of like ripping a CD for an iPod: morally it's just fine, as all I'm doing it transferring from one media to another, but legally you can't do it (at least, not in Australia. No "fair use" here). Then again, legally I can't listen to my CD's on an iPod either. :-)

Other than movies, I'm hoping to write a few more notes on the structure of the data files in Kowari. Some of this is obscure, and is really only documented in the class implementations (where "documented" means that the code tells you how it's done). I understand it in a general sense, and the code helps clear up anything I forget, but it will be very useful to have real documents that explain it. I've already started on this with the Free Lists (probably the hardest format to follow). This slowed down the Javadoc work, so I'll probably put aside the file format until the flight so I can get through Javadoc before I leave.

Other than that, I still have OWL code to write (I want to put together some subsumption code soon), and I'd love to do a bit more on jCarbonMetadata, which I haven't touched for weeks. Speaking of which, I started on an objective-C tutorial and meant to get back to it. After all, instead of porting the missing Carbon functionality to Java, why not learn objective-C and write a bridge from Cocoa to Carbon? :-)

Yes, this is a lot to do on one flight... but I'll be traveling from 11am in Brisbane until 5pm in D.C., all in one day. That's a total travel time of 20 hours. And no, I can't sleep effectively on flights. My plan is to keep myself busy, which is why I need several things to keep my attention (so I can swap when I lose concentration).

Huxley
The other thing I'm planning on doing on the flight is continuing the novel I've just picked up. I'm finally reading Aldous Huxley's A Brave New World. It's always strange to read old science fiction, as the authors had no idea how far we would come in the twentieth century (computers weren't even invented for decades after Huxley wrote this novel). It's easy to get distracted by thinking different the real world is to the story, so it can take some real concentration to see the point the author was trying to make. However, I'm only into the second chapter and already I love it.

I particularly love the noise-aversion and shock therapy given to Delta babies to make them hate nature and books. It turned my stomach, which was obviously the intent. But the reasoning was masterful. Discouraging Deltas from reading prevent them from wasting time on something they didn't need (something logical for this future world). But it was the reason for hating nature that really struck a chord for me.

Deltas were once allowed to enjoy nature, as they would then consume transport, but that's all they consumed. Nature was gratuitous, and kept no factories busy. So it was decided to abolish a love of nature. However, the desire remained to have Deltas go out to the country to consume transport, even though they now hated the country. So Deltas were made to love country sports, which required the use of expensive and elaborate equipment (thus creating more consumerism). Beautiful.

The scary part about this concept is that modern society mirrors it so much. Sure, we don't condition children with shock therapy... we use advertising instead. However, the end goals are the same, and in my opinion, the fact that we do it to children is just as deplorable.

Huxley wrote this book as a warning to the world about the direction we appeared to be going in. It has had enough influence to slow down some development over the years, but it never really stopped it. It's obviously an insightful story, and I'm looking forward to reading more of it.

Chicago
Advertising at children brings me to a new point. When Luc wants to watch TV we let him see ABC-Kids. This is a brilliant service, as it is government funded and has no commercials. I don't want him to watch too much TV, but at least there is something he can watch that I approve of (the kid is a "Wiggles" addict). I'm wondering if there is a similar TV station in the US? From what I've seen, I really doubt it.

This is just one of many questions I've been pondering lately. I'm considering a move to Chicago to take on a new job. Three years ago I'd have agreed at the drop of a hat, but now that Anne and I have a family it changes the rules. We have a great lifestyle here, and there seem to be some good opportunities coming up if we stay here. It also looks like it would take a bit of money to move to the States (on top of what we've been offered to help us move), and we don't really have any at the moment.

From what I've learned about Chicago, we'd be taking a backward step in our lifestyle (based on what I'd be earning). On the other hand, I've been wanting the experience of working overseas, and this could be the opportunity to do it. Besides, even if we take a backward step, then we can still take forward steps in the future.

The other thing is that (almost) everyone I've spoken to about Chicago has recommended it as a great city to be in (though I haven't heard any specific reasons why). Alternatively, Anne is scared about managing two kids (including a newborn) in a city where she knows no-one. So it's a bit of a toss-up for us. I'll be going to Chicago at the end of my trip to have a look around. Hopefully that will help us to make the decision (though I'll need Anne's support).

I'm mentioning it here in case anyone knows Chicago (and the US in general) and has an opinion to share. :-)

Axioms
Well the test didn't work, but I had to go to bed. When I got up in the morning yesterday, I spent 15 minutes looking at the problem, and discovered it wasn't really a problem. The code was working just fine, but I had a typo in the RDF for the axioms. Doh! :-)

It's really impressive how many entailments come out of the axioms alone. There are 33 axioms and this was increases to 120 statements after the entailments. When I ran the RDFS rules over the RDFS model (and it's OWL description) then it turned 643 RDF statements into over 1259 statements.

It was while I was looking at this that I discovered how useful entailments are, even simple ones like this. For a start, all of the types suddenly become available, even those that are not immediately evident. This in turn showed up a couple of simple errors I had in the RDF which had slipped past me before. It turns out that entailments from bad data can lead to a lot of statements that are very obviously wrong. Quite handy.

I didn't get to work much more on this, as I needed to get back to the NGC preparation.

XA Store
Yesterday I was lucky to have DavidM online while writing Javadoc for the transaction layer. This helped me to learn a lot about the newer parts of the code much faster than if I'd had to do it on my own. This will definitely help with the handover.

Today I spent several hours working out a timetable for the handover. I expected to do this in a couple of days, but DavidW needed something from me quickly. So I tried to write an email with a broad outline. However, I ended up writing a lot more than I thought I would, and I think I'm halfway to the full preparation. :-)

One more thing I'd like to do is to write up some diagrams of the file formats. This is all available by reading the source files, but they have to be carefully interpreted to work it out. Having diagrams on hand should be very useful.

Well I'm exhausted tonight, so I'll leave it here and get to more Javadoc in the morning.

TKS
For anyone who missed it, the rights to TKS have been purchased by Northrop Grumman. Importantly, they've agreed to support the Kowari project. Wow.

I've agreed to do a handover of the code, and as a part of this I'm writing Javadoc for the XA store. I helped write this over 4 years ago, so I sort of know it, and I sort of don't. DavidM has modified a few things since I was last in that code, so it's been a learning experience for me. Fortunately the process of Javadoc is helping me learn it all.

I'll be flying to the US next week on the 6th of July, and will be returning on the 27th of July. I'm not looking forward to missing Luc (and Anne). On the other hand, I love traveling for work, particularly to the States, so it won't be all bad. It will definitely slow my blogging down though.

Rules
In the meantime I'm still working on the rules engine and the tests. It appears to work remarkably well. Must be all that effort I put into it. :-)

Since I have to work all day for NGC at the moment, I'm spending my evenings (and the upcoming weekend) working on the rules. All that is left of my paid work is the proper set of tests, and perhaps a short document describing how to write a rule configuration (in case something more than RDFS is desired). I'm pretty sure I can get all that done before I fly out.

Many of the tests specified by the W3C are quite trivial, but they reminded me that RDFS requires axiomatic statements. That is fine, as I could just load them into the destination as a separate RDF file. This bothered me though, as it's a very manual process, and a necessary one for many rule systems. So rather than expanding on the tests tonight I've been encoding the axioms into the rules engine. Now the RDFS rules file includes all the axioms, and the rules engine knows how to read them in and insert them at the beginning of execution. I still need to test that this is working correctly, and it is compiling as I type.

It's now 1am, and I have to give Luc his bottle when he wakes up in the morning, so I'd better run this thing and get to bed (please work first time!)

Tests and Improvements
The tests for the rules seem to be going fine. I could continue to write tests for it forever, with each one getting more complex, so it's hard to know how far to go. After all, they can take a long time to write. At the moment, I'm looking to test each RDFS entailment one at a time. Eventually I'll be moving on to how entailments interact, but I'll only go so far with that, as I really want to move on to the next part, which is OWL entailment.

Still, the code (without tests) is checked in. Have a look in the "rules" directory for an example of running the RDFS rules against the RDF for the RDFS rules. ;-)

I had a talk with Andrae today about how RDFS/OWL and how the Rules engine in Kowari works with it. I also showed him some of the internal structure, and he had a couple of ideas that will help with efficiency. I'm starting to accumulate a list. It's frustrating, as I want to make it all as fast as I can, but I also want to make it as functional as I can, and I can only work on one objective at a time. :-(

The efficiency things I want to do are:

• Make the various implementations of Tuples.getRowCount() run in log time, rather than linear time (this needs a count in the nodes of the AVL tree).
• Add a new version of Session.insert() which accepts an Answer rather than a query
• Properly merge the source and destination models for rules if they are the same model
• Keep a map of Constraints to their counts for each rule, and ensure that answers are using these Constraints.

There's more, but I can't think of them at the moment.

Javadoc
I've also been adding some long-needed documentation to the storage layer.

I pair programmed with with DavidM starting 4 years ago. I worked with him on it for over a year before moving onto other things. So I mostly know how it works, but there are subtle changes since I saw it last. Plus it's been nearly 3 years since I last worked in that area. Back when this code was written, David and I were really pushed for time. To help us get it done in time we were told that we could skip the documentation. It allowed us to meet the deadline that we had, but of course we were never given the time to go back and document it like we were supposed to.

It's been an interesting experience coming back to something so complex after so long. I don't remember all of it clearly, but this process of documenting the methods is really helping me work it out. It's also interesting discovering some of the changes which have come about since I last worked on it.

Whew
The rules engine works. Yay. :-)

While thinking about the RMI problem on Thursday night, I realised that I do want the rule configuration to serialize (I use the American spelling, with the "z" here, since all the interface and method names are spelt that way). The reason for this is because the server with the rules might be different to the server with the data.

My concern with serializing like this is unnecessarily serializing from the server to the client and back again, particularly when the client is on a separate machine to the server. Serendipitously, I'd already wrapped the rule structure in a remoteable class. This works well, because nothing gets moved to the client at all. When the server gets this reference and asks for the rules then this is the only time that the rules get serialized. If the two servers are separate then the RMI serialization is necessary, and this approach works just fine. If the server for the rules is the same as the server holding the data, then the rules will still be serialized, but it only happens once, and the RMI transfer is within the one JVM, so it should be very fast. Either way, there is no unnecessary transfer to the client.

It's amazingly satisfying to see the entailments being generated. :-)

Merging
For stability purposes, I've been coding against a version of Kowari that I picked up a couple of months ago. My code has been largely independent of other modification in the system, so this should be safe. Nevertheless, I'm about to update everything and confirm that it all still works.

Once that's done, I'll need to tidy up my tests in order to check everything in. Since it's all working (and can't break any other components), I might check it in without all of the tests. That's because a few people have been asking after these rules. Hopefully they'll like them. :-)

The algorithm for running the rules is not quite complete. At the moment each rule is dependent on finding a change in the total result of a query in order to determine if it needs to run. This requires processing, even when the rule does not need to run. The completed algorithm tests each individual constraint for changes, before testing the joined result. This means that there will be no join processing for (almost all) rules that don't need to be run, and no additional expense for those rules which do need to be run. I expect these changes to take just a few days, but they are not needed straight away.

One feature that might be nice to add would be to keep a total of all entailed statements and return this to the user when done. I'll look at doing this soon as well.

Eclipse
I've gained quite a bit out of using Eclipse, but it's been frustrating me lately. I often find myself typing up to a line ahead of the rendering, and often have to wait for the IDE to finish processing before I can do anything. As a result, I've started using VIM again whenever I want to do fast changes. I'll have to work out some way to use Eclipse again without having to spend half my day waiting for it.

Maybe it's just that my notebook is too slow. It's only a 1.33 GHz G4 (with a GB of RAM). This isn't as fast as many desktop systems, but it's quite responsive on every other application I use, so I expected that it should be fast enough.

Last night I had a go at running Eclipse on my Linux desktop, and piping the display to the X server on this notebook, but that kept crashing. On the Linux-GTK setup it crashed with a GTK Window error whenever I selected the "File" menu. So I tried the Linux-Motif setup, but that caused a Hotspot error. Yuck. I haven't tried it on the local display, plus I was using Java 1.5, so there are a few things that could be causing these errors. I guess that will keep me occupied for a day or so, when I get the time to look at it.

Slow and Steady
I've been plodding along with the rules engine over the last week. Unfortunately, I'd initially planned to be done by now (not planning on getting sick, etc), and so I'd already committed myself for some other modeling work. That meant that I had to juggle the two together. However, I really need to finish the rules work quickly. I want to get it working, so I can move on to the next part of OWL support (needed for my thesis) and also because I won't get any money for my last couple of months until it's done. I think I'm actually supposed to invoice for time rather than the product, but I made a commitment to complete this phase, so I'll have it working before sending in the invoice. I just hope that the payment won't be too long after! :-)

After this last week, the RDF seems to be configured correctly, the code reads it all as required, and the elements all work properly. But it's tough getting them to work together in the way that I want. I'm half tempted to glue it all together in a way that I've already seen work, but I need the more general solution. At the moment, the problem is RMI. That figures.

When I tell ItqlInterpreter to apply a set of rules, I want to read the rules structure and return a result to the ItqlInterpreter. Then ItqlInterpreter can change it's current session to point to the data to be worked on, and run the rules. This all seems to work (it's not fully tested, but what I've done so far works) if I have it all occur in one step on the serve, but then the rules can't be separated from the data to be worked on (though I am presuming it is all found on the same server). I need to make it happen in the two steps I've outlined.

Unfortunately, I'm having real trouble getting the rules structure to pass over RMI correctly. By default, getting the rule structure from ItqlInterpreter would serialize the structure and create it in the client space. This has two problems. The first is that it's inefficient. There's no reason to move all that data over to the client, since it will only ever get used at the server. The more important problem is that the client would need to have access to the rule structure classes for de-serialization, and I'm trying to keep the client completely oblivious to all but the interfaces.

The better way to manage this situation is to pass back a remote reference to the class. I struggled for some time getting this right (I forgot how annoying RMI can be in this regard). To simplify things I decided not to ship a reference to the entire object (since the methods on that object should never be called remotely), and instead created a remotable wrapper to hold a local reference. The remote reference to the wrapper can be shipped over RMI, and when it comes back it can be queried for the local object that I want. Only that's not what I'm getting.

It took a LONG time to get a stack trace that was useful (it's being completely hidden in RMI, and was never being thrown from where I thought it was being thrown), but I finally worked out that the problem is coming from the server when it tries to extract the local reference to the rules structure. At this point it tries to serialize the rules structure, which is not legal (intentionally so). I believe that this is because the object doesn't know that it is now back on its machine of origin, and does not know that it can just pass back a local reference.

Perhaps I'm approaching it all wrong. Now that I have the RMI compiling and running correctly (this took me some time) I could possibly drop the indirection of the wrapping object, and pass back the rule structure as a remote reference (like I originally tried). My only concern is that calling run() needs to pass in a DatabaseSession, and I want it to take the local session without trying to serialize it. I'll have a go in the morning anyway, and see what happens. In the worst case I can always keep a local map of the remotable objects to the local rules structures they represent. Then when an object comes in for a "run request" I can get the local rules out of the map.

It's late. I'll think about this overnight and have a go in the morning.

OWL
Bob asked that I work with him on looking at extensions to OWL. He knows I've been thinking about this lately, and it turns out that he has some ideas as well.

Yesterday was the first opportunity I've had to really see how he works on these problems, and I have to say that I'm impressed. While he doesn't have a strong background in OWL, he is able to draw on a good formal understanding of category theory, E-R diagrams, and other areas. It allows him to see where OWL is missing functionality, or how certain functionality might be achieved using OWL constructs. There were a few occasions when I could suggest using an OWL or RDF construct to achieve something, and he could quickly show why this would or wouldn't work, and if it wouldn't work then why not.

The most impressive thing is that he really knows the boundaries of his knowledge, and he knows where to go looking when he doesn't know something. Conversely, I don't know how much I don't know,. Even when I recognise that I need to learn more about something, I don't even know the name of the field that I need to learn more about. I guess that just comes with experience.

The two big things to come out of our conversation was Cartesian product classes, and predicate composition. Cross products allow for several important relationships, but most importantly they would permit the description of a pair of relationships which may be individually repeated, but together must be unique (like composite keys in a database table). Predicate composition ends up covering a couple of the ideas I've already described, such as Euclidean predicate relationships, only it does it in a single construct.

I know that Ian Horrocks has explained that things like predicate composition can lead to undecidability, which needs to be considered for OWL DL. While that is no problem for OWL Full, a lot of people are more interested in OWL DL for the moment, so I think that it is important that any new constructs have some use in OWL DL. However, decidability is not something that either of us know a lot about. Fortunately, I've been given a reading list by Guido, plus I have those pointers from Ian. I just need to find some time to sit down and read them! :-)

Quiet
Just like every night lately, I'm tired... so this will be short.

Testing and debugging went well over the last week. Since I found the dynamic compiling and error reporting of Eclipse to be so useful I decided to sink a bit of time into making the project integrate properly. I made some real progress, but it's still not done completely. Fortunately Eclipse still lets me run programs when errors are present in the build, otherwise the work I'd done would be a waste of time. It would still be nice to get everything working though. In the meantime, I decided I've spent enough time on it for now, else I won't be saving any more time than I've spent.

There are so many details that I learnt in setting this up, and it's annoying that I didn't blog them all as I went... particularly the problems. For instance, CVS didn't pick up one of the directories on SourceForge. Why not? No idea. But I could use the CVS perspective to "Check out" a subdirectory to an already existing project. So I just had to find the missing directories, and give them the correct destination.

The debug environment that I have running now lets me use breakpoints, and lets me properly analyse Kowari while it's running. The last class loader (with embedded jar loading) prevented this from working, so it's a significant step over what I used to have. However, it's still annoying that I can't get Log4J working properly. I've discovered that the correct config file is loading (I put an error into the XML, and looked for an error message), but it ignores the "Category" statements which stipulate that Debug messages should go to the appenders. The debugging environment helps here, but logging is still important (especially when you consider how slow Eclipse is). For the moment I use warning messages instead of debug messages, and I'll have to remember to change them all back before checking in.

Anyway, the configuration now works (of course, the problems were all in those areas I tacked on to the RDF at the last minute), and I've traced all of the problems, which I'm currently working on. It should be finished by the end of the week, but I still need time to write all the tests.

Public Holiday
Yesterday was a public holiday here (the Queen's birthday - not that anyone seemed to care about that). I worked for some of the weekend, and I planned on working for Monday as well, but Anne also needed to work. She's supported me a lot with work lately, so I agreed to look after Luc on my own. I spend a lot of time with him every day, but yesterday was the first time in a long while that I spent an entire day with him, where he was the centre of attention. No internet access, just taking him places and doing things with him. He's doing very well at the moment, trying out new words and solving lots of everyday problems.

We had a great day, and I'm pleased that I was "forced" into it. I'd better concentrate on work for another few weeks, but when it's done I should take another full day like that. It's good for the soul. :-)

Substantive Coding Done
I spent the last few days concentrating on coding rather than blogging, as I have been getting close to the end. I've now finished the substantive coding for the first iteration of the rules engine. That doesn't mean it's done, but I feel good about it anyway. :-)

What I mean by substantive effort is that the code is all written, and it compiles... but that's it. Except for iterative testing during the process of coding, I haven't even tried to run it yet. I plan on starting the debugging tomorrow. This always takes time, but just starting on the debugging stage makes me feel like I'm in the home stretch.

The current implementation is based on performing the equivalent of a "select", followed by an "insert/select" if needed. This is a lot like the original proof-of-concept code, only now it is fully integrated and is being done on the server side. This is not the ideal implementation, but it will work, and should demonstrate that everything is implemented correctly. It should work pretty quickly too.

I think I'm on schedule for completion of this round of the paid work, but a few sick days recently mean that I'll need to go beyond my scheduled finishing date. I believe I'll have everything written that I'm supposed to have written, but in reality I'm being paid for time, not for completed code. The other reason to keep working on this full time is that I'm enjoying it! However, I can only afford to go for the extra time needed to make up those days I was sick. Hopefully the system will be so useful and show so much promise for further development that someone will pay me to do more of it! (Well... I can dream, can't I?) :-)

Once I have it working, and RDFS is executing correctly, I can move on to the next stage. This version will count the size of each individual constraint, rather than the size of a completed Answer, making it much more efficient. More importantly, it will match the design I'm writing my thesis about! The initial code to do this should take less than a day, but I'll need to spend some time in the query engine to make sure that constraints are being cached and re-used correctly. I'm not sure if that time should be considered "coding" or "debugging", as I'll be using constraints in a manner slightly outside of their original design (which feels like re-designing and coding), but I'll be approaching any problems like I would any unexpected error (which is debugging).

Rules vs. Ontologies
A more pressing concern is the need to make transitive constraints accept a variable predicate. This is not needed for RDFS (since the only transitive predicate is rdfs:subClassOf) but it will be needed for OWL. Once OWL is introduced, the specific rule for transitivity of sub-classes can be dropped in lieu of a declaration in OWL that rdfs:subClassOf (and owl:subClassOf) is a transitive property.

This brings me to a point that I've been thinking about for a while. I sort of understood it before, but I think I've only just started to really get it. What does an ontology language give us that we don't get from rules? After all, ontology inferencing (and consistency checking, but I won't go there right now) is performed by rules. Rules also allow much greater flexibility than we can achieve with a ontology languages like OWL. The commonly cited example of OWL's limitations is that it can't express the "uncle" relationship. An "uncle" relationship is relatively straightforward. If person A has parent B, and person B has brother C, then A has an uncle C. This is easy to describe in rules, and impossible in OWL.

If we can do everything in rules, and OWL is limited, then why use OWL?

The answer (for me) is demonstrated with the transitivity of subClassOf. If we just had a rule system, then we would need to have a rule for inferences on this predicate. ie:

  if A rdfs:subClassOf B
  and B rdfs:subClassOf C
  then A rdfs:subClassOf C

That's fine, but what about "less than"? We need a new rule:

  if A < B
  and B < C
  then A < C

How about "greater than"? New rule. "Equal to"? New rule. Every time a new transitive predicate appears we need a new rule to handle it. This means that rules have to be very domain specific. They can't handle anything that wasn't known about at the time they were created.

However, using OWL a predicate can be declared to be an owl:TransitiveProperty. Suddenly we have just one rule:

  if property is transitive
  and A property B
  and B property C
  then A property C

Whenever a new property is introduced which is transitive, then we can just declare it in OWL. Of course, this goes for all of the properties of properties that are definable in OWL. So the ability to describe the properties of a property means that we can write generalised rules to make deductions on them.

I've sort of understood this for a while, but it was only while thinking about Euclidean properties that it finally crystallised for me. Ideally, it would be possible to assert something like:

  parentOf isEuclideanTo siblingTo

So we could end up with a rule like:

  if property1 isEuclideanTo property2
  and A property1 B
  and A property1 C
  then B property2 C

Of course, isEuclideanTo would not be symmetric, though it would be possible to infer backwards on it (a person's parent must be the same as their sibling's parent).

There are more complex types of relationships between relationships. Uncle is a good one to demonstrate this, as it requires 3 different types of relationship which are all related to each other. While possible, the RDF required to describe something like this is starting to get messy. Complexity is introduced when you realise that one of the relationships can actually be either "brother" or "brother-in-law". Also, an uncle relationship can be deduced, as can a nephew/niece, but the parent in the middle of the relationship cannot be.

All the same this kind of knowledge about properties is something we use every day. If an ontology is to describe real world objects and relationships then it will need to be capable of describing relationships between relationships.

With this in mind, I ask the OWL mailing list what people thought of such a construct. I half expected to be shouted down, but at least I'd get to find out why. Instead the response was encouraging. Ian Horrocks (who wrote half of the papers I cite) explained that property relationships are indeed useful, but that care must be taken to ensure they are decidable. He's suggested I read one of his papers on the topic.

Who knows? Maybe one day OWL can include something like this.