Syntax
Today was spent doing very little coding, which I found quite frustrating. TJ won't be happy, but there was nothing I could do about it.

The constraint implementation described yesterday needed to create a new type of Tuples object so that it perform the correct type of transformation when joined against. This didn't seem quite right, and since the appropriate code belongs to others, I took the time to ask their advice. Of course, I ended up with 4 people offering 5 opinions. So there ended up being a lot of discussion before we could reach consensus.

After considering it for some time I realised that cardinality needs 4 things:

1. A constraint expression.
2. A list of variables (usually just one) from the constraint expression.
3. The type of integer comparison to perform ( > < = ).
4. The scalar integer value to compare against.

The list of variables provides the grouping of item 1 needed for the counts. I couldn't come up with a use-case which would ever need more than one variable in this list, but it's normally best not to place artificial restrictions when they are not needed. Besides, as soon as we decide not to do something like this, we invariably get an email requesting that very feature, normally within 6 months.

Since item 1 is a tuples, and the output is a tuples, then this can really be described as a parameterized mapping from tuples to tuples. Hence it makes sense to consider this as a function (yes, I've been reading more from the text on Predicate Logic). The type of comparison found in item 3 would probably be best described by declaring 3 different functions, which in turn reduces the required parameters.

No one seemed to dispute any of this, but we could not get consensus on the syntax to express any of it. AN liked the idea of using a pure function notation, pointing out that we mostly do that already, particularly with trans() and walk(). AN preferred a function-like syntax, with all the parameters appearing as 3-element statements, separated by "and" keywords. This is exactly what trans() and walk() do. SR came up with a syntax that was much more wordy, making it look like a statement. The first element of this statement was the integer from part 4, the second element was a predicate describing the scalar comparison from part 3 and the third element was like a subquery. Item 2 was the "select" clause of this subquery, and item 1 was the "where" clause.

After spending many hours getting consensus on the semantics of this, I was getting frustrated at the time taken to work out the syntax. I was wondering if it might be possible to implement this function without finalizing the syntax, however I was reluctant to proceed with this as a poor choice in the realization of some of the required items could make the parsing of the syntax into these items much harder than it would need to be.

Finally TJ entered the fray, and asked about using subqueries and count(). To start with this didn't appear to be useful to us, as it only provides a scalar integer as a result, but then TJ showed how it could be left in the results (with its implicit variable name of $k0) and then those lines which didn't match on $k0 could be dumped. After investigating this, it appears to work, and will only require a minimal change.

The required change is the introduction of a "having" clause which can use a constraint with a predicate of occurs, occursLessThan or occursMoreThan. This will be applied as a kind of filter at the last moment.

The advantage of doing things this way is that it involves a minimal change, and should be reasonably fast to implement. The problem with this method is that the result must come with the $k0 variable built in, so it couldn't be used for doing insertions. However, I don't think this kind of query needs that functionality, so it might be OK. Another problem is that the syntax is so incredibly obtuse, that I barely remember it. Tracing through how it was going to work, it took me 5 minutes to see that it would do what we want. Even now I'm not sure I can remember it. For this reason alone I'm concerned about implementing the code in this way, but cardinality is already late, and I really need something done before I go on holidays at the end of this week.

I suppose the best outcome here would be to get it working, but in my absence for someone to discover a problem, and on my return I could do it in the original way... once someone has worked out a syntax!

Inferencing
In the meantime, I've been getting the RDFS inferencing paths working again. Unfortunately I've been using my Mac, which has 2 problems. First, it already has something bound on port 8080, and the http server uses this. Strangely, I couldn't easily figure out what is already using that port, as netstat does not report anything using it. I should just point my browser at it and see if I get a response.

The second problem was when I moved the server over to my desktop machine. It is names "chaos", and I have an entry for it in /etc/hosts. Unfortunately, Java is failing to find a server named "chaos" and so iTQL falls back to 127.0.0.1, which is never going to work, even if the server is on the same machine as the client.

I ended up running both the iTQL client and the server on my desktop machine (with the iTQL GIU coming to be via X), which worked fine. However, running the inferencing rules had the same addressing problems, meaning I would need to move all of the Drools code up there as well. I took that as my cue to leave it until morning.

Cardinality
Cardinality implementation is an elusive beast. I've been working on it this evening, as I didn't get as far as I wanted today. After discussing things with AN this morning, we came up with a good plan for implementation, but turning this into code has not been as simple as I'd hoped for.

To start with, AN has refactored a lot of the constraint resolution for Kowari. I don't have a major problem with that per se, but it invalidates a lot of what I knew about the way things were done. Consequently, I spent quite a bit of time finding code that I knew existed, but I didn't always know where to look for it since it was refactored into a new home.

Cardinality constraints have to be done after everything else has been resolved. To force these constraints to be executed last, I've set the size of the constraint's row count to Long.MAX_VALUE. AN suggested using the size of the graph plus one, but there is no graph for this kind of constraint, so I opted for a number that would be obviously larger than any other.

It may have been possible to tell the execution plan about the need for cardinality constraints to always come last, but I didn't like this idea. The code for the execution plan is clean and generic, so the last thing we want is for it to start making special cases for particular types of constraints. Conversely, setting the size of a constraint to a large number like this is really just subverting the whole execution plan anyway, so perhaps some special knowledge wouldn't be so bad after all. I'll leave it "as is" for the moment.

Essentially, cardinality resolution gets done in one of two ways:

• If the variable of the cardinality constraint is not found in the tuples the constraint is being joined on, then the constraint will be applied to the entire tuples. First, the variable has to be associated with a column (this must be done with another joined constraint, otherwise the variable is completely unbound and will throw an exception). Once associated, that column can be searched for unique values, by joining on a singleton tuples with the variable associated with that column. The rows of the resulting tuples then get joined to the entire set one at a time. If the results are of the correct size, then they get appended to the final result.


• If the variable is found in the tuples to which this constraint will be joined, then a join on that variable will provide a unique list of values. This list can be used one item at a time, to join against the original tuples, and if the sizes of the resulting tuples are correct then they will be appended to the result.

From what I can tell, I'll need to implement this whenever a ConstraintConjunction is executed. Execution of constraints happens inside ExecutionPlan but the work gets delegated to the TuplesOperations.join() method. This creates a problem, since this method is only aware of tuples, and not of the constraints they belong to.

As a result, I'm thinking I need a new type of Tuples which can represent the need to constrain by cardinality. However, it's late, so I'll sleep on it, and get AN's opinion in the morning (maybe even SR, as he is back now).

Timeliness
Recently I've been tending to write these the day after the events described. Hopefully they won't be suffering too much from the lack of attention. It's partly due to needing to help with Luc in the evenings, and also because of my preparations for this year's Noosa.

Cloning
Friday's problem was tracked down through the extra logging I threw into the exception trace. My first problem was because I hadn't implemented cloning on the ConstraintIs class. As a result, the clone() method from the ConstraintImpl superclass was being called, which converted the constraint into a ConstraintImpl. This meant that the wrong constraint resolution method was being called, which was the basis of the problem.

Adding the clone() method fixed this, but not quite as well as I'd hoped, with a number of failures still occurring in the tests. At this point, I decided that I was running into problems associated with inheriting methods (such as clone) from ConstraintImpl, and so I removed that inheritance, and copied a lot of code from ConstraintImpl to ConstraintIs.

It was while copying the code, that I found the problem. This meant that I could probably go back to inheritance, but AN expressed a preference to split the constraint classes up anyway, so I was happy to leave it. Perhaps an abstract constraint class could be created to have them all inherit from, rather than having them all inherit from ConstraintImpl as I had initially done.

The problem I found was fairly simple. I had implemented clone by cloning all the nodes except the KOWARI_IS node, as this will always be fixed. However, I forgot to anticipate that the constraint could be localized, meaning that the node would be changed to a local node, with only a long integer as an identifier. Once I realised this I changed the code to clone the predicate if it isn't equal to KOWARI_IS, and voila, another couple of tests passed.

Subqueries
The next problem was similar to the cloning issue. SubqueryAnswer was creating a new constraint with its own version of a KOWARI_IS predicate. In one instance the predicate was global, and in the other instance it was local. An existing constructor would work for the former, but the latter needed a new method created which would accept the local node. The "query" package that ConstraintIs lies within does not have access to the database, so this node has to be pre-allocated and passed in, rather than having the ConstraintIs class find the node for itself.

Given that subqueries only needed to allocate new ConstraintIs objects, I create a factory method for these new requirements, and put it directly on the ConstraintIs class.

Blank Nodes
The final two failing tests had me stumped for several hours. They were both in JRDFGraphUnitTest and should not have been impacted by any kind of changes to constraints.

I finally discovered that these tests were expecting that a new blank node allocated for a fresh graph with a predetermined number of statements should have an ID of "_node58". Since I had changed the database to no longer allocate nodes for some of the magic predicates, this number was changed.

I spoke with the culprit, and he confessed to thinking that using hard-coded node IDs was lazy as he wrote the code that did this. I know he'll read this, so hopefully he won't be so lazy next time. :-)

The fix was to put markers into the array that is compared against the blank nodes, and replace those markers with the correct IDs as soon as the blank nodes are allocated. That way any further changes will not affect these tests.

Visitor Pattern
After getting through some email this morning, my first task was to clean up my modifications (ie. clean up code that is calling methods I've yet to write) and make sure it all works. During this period I started wondering about the use of the visitor pattern for resolving constraints, and if this would work for the subclass of a constraint.

Binding the function to call is done at compile time, and my concern was that ConstraintIs might not be passed into the visit() method correctly. ConstraintIs extends the ConstraintImpl class. The problem happens because of an overloaded method (in the ConstraintResolver class) which takes a ConstraintImpl in one implementation, and a ConstraintIs in the other. If code in the resolver class takes a ConstraintImpl object and passes this object into the overloaded method, then the compiler will make a selection of the method to call based on the type of that parameter. The compiler has to choose one method or the other, and it has no idea that I might be passing in a ConstraintIs, so it chooses the method which takes a ConstraintImpl.

The only way that Java can select a method at runtime is when it is calling a method on a class reference. The reference to the class provides the indirection necessary to find the method. For instance, this is how I can call toString() on any class derived from Object. Using overloaded methods on another class, and choosing to pass in differing objects at run time provides no mechanism for Java to work out where to go.

Fortunately, my concerns were unfounded and demonstrated my lack of understanding of the use of the visitor pattern. This pattern is specifically designed to circumvent the very problem I was concerned about. By calling accept on the destination class (either ConstraintImpl or ConstraintIs) then the compiler is able to go through the reference to the correct class. The implementation of the accept method is a trivial call to visit(this) on the originating class, providing the correct type (via the this parameter) for the compiler to statically bind.

AM took me through much of this, and once I "got it" I realised that I hadn't implemented the trivial accept method on ConstraintIs. This meant that it would inherit the accept method from ConstraintImpl which was not what I wanted. It's always nice to find bugs before you run them.

I was still curious about the use of the visitor pattern, as I didn't see why the constraint resolver would want to have a different method to resolve each different type of constraint, and not call a method on a constraint to do the work for it. This would remove the method binding problem as well. It turns out that the forthcoming resolver interface will want to provide different mechanisms for resolution, meaning that we need numerous classes able to do the constraint resolution, on identical constraint objects. Sure, it can be done without the visitor pattern, but then the constraint objects will need to know far too much about the internal workings of the classes which are to do the resolving.

Cloning
After getting everything tidied up and compiling, I had a go at testing the new setup. This didn't work, and it was because of the tucana:is predicate.

Logging during tests is particularly bad, as most logs get swallowed up, with just an exception string being saved in the output. So I added a lot more information (including a stack trace) to the exceptions I was seeing, and this helped me track down the problem to the clone method on ConstraintImpl. Since I had ConstraintIs extending ConstraintImpl it was picking up the inherited clone method, and hence lost all type meaning. Reimplementing clone at the ConstraintIs level changed the error I was seeing, but didn't fix the problem. I'll be working on that on Monday.

Constraint Resolution
Nothing more happened in terms of design today, but I was pretty happy with the progress nonetheless. I've changed the structure of the code back into a working system, and made a start on the code for cardinality.

By moving the recognition of the kowari:is predicate out into the parser, it has solved several problems, and made the code a lot simpler. These benefits are carrying through to the other constraints, so the design change seems to be a good one.

Using a factory method to create the appropriate type of constraint is the only part of the code which is doing a lot of if()...else statements, and even this is reasonably simple. More importantly, because the predicates are being recognised at parse time instead of execution time, there is no need to have the magic predicates stored in the database on initialization, so they can be recognised while resolving the constraint. With the advent of different database back-ends with the new Resolver SPI, it won't always be possible to add magic predicates to a database, so this change turned out to be quite important anyway.

There are other advantages as well. Checking of the constraint parameters used to be done on the server while the constraint was being evaluated, but now this is done by the constructors of the constraints. This catches problems earlier, and simplifies the execution code on the server. Finally, the fact that AN has already changed the ConstraintResolver to using the visitor pattern has meant that new constraint types can be introduced trivially, simply by adding a visit() method with a parameter of the constraint type required.

Moving over to this arrangement removed 29 lines of kowari:is code from a visit() method which was handling all types of constraints, and added a one line visit() method which accepts a ConstraintIs class. It's simpler, easier to read, does not involve myriad if() statements, and is far more maintainable.

The new ConstraintIs class was trivial as well. It just extends the standard ConstraintImpl class, with a few minor changes. The constructor does not need the predicate, as this is defined already by the nature of the class. It also does checks on the types of the data. At this point we only permit kowari:is to be used with a variable subject and a fixed-value object, so the constructor can check for these as well. Finally, a couple of convenience accessor methods return the value and the variable without the need to cast.

Chang and Lee
At Bob's suggestion, I've been reading Chang and Lee's Symbolic Logic and Mechanical Theorem Proving. I'm only up to chapter 4, but it has proven to be an easy read so far.

Predicate logic is so applicable to our querying that I'm a little ashamed at not having read it already. Admittedly, so far the book has been about verifying the truth of a formula, rather than finding all "interpretations" (RDF statements) which fit it, but it is still talking about exactly the kind of things our queries need to do. SR was all over this stuff when the query layer was designed, but I realise now that I should have known it as well. Fortunately I was working on the datastore layer at that time, but I should still have learned about formal predicate logic when I first started working on optimizing queries. Oh well, better late than never.

Constraint Design
Started the rearrangements for constraints, but I've decided not to go "all the way" with them. This is basically because the poor design of constraints is too endemic to fix in only a few days.

The problem is clearly evident in ConstraintImpl. This class both extends the abstract class AbstractConstraintExpression and implements the Constraint interface. AbstractConstraintExpression implements (partially) the ConstraintExpression interface. Constraint extends the ConstraintExpression interface.

So the ConstraintImpl class is getting declarations of methods from one parent (Constraint), and implementations of those methods from another parent (AbstractConstraintExpression).

Constraints and ConstraintExpressions were once distinct, with Constraint being the class that ConstraintImpl now holds the position of. Fortunately AN has already changed that, but it's a shame that it didn't end up as a parent of AbstractConstraintExpression, as this would solve a few problems by creating a single inheritance path. It's a little problematic to do this, as the methods declared by Constraint and ConstraintExpression are unrelated, and some classes implement ConstraintExpression without implementing Constraint.

For the moment I've create a new ConstraintFactory class. This can be used by ConstraintExpressionBuilder instead of directly creating a new ConstraintImpl object. The point of this modification is to automatically create a different kind of constraint object when a magic predicate is used. By using different constraint object types, the constraint code can avoid the use of numerous "if" statements.

Magic Predicates
Magic predicates are described in AbstractDatabase. This class declares methods for getting the node numbers for each of the predicates, such as "KOWARI_IS". However, these do not describe the URI used for any of the predicates. Currently this is done in XADatabaseImpl, and would be duplicated in any "implementing" database.

XADatabaseImpl actually creates nodes in the datastore for each magic predicate. The generated node numbers appear to have no use except to recognize when a magic predicate is being used. This generation is done during the init() method, and it defines the string for the predicate inline. An example is:

 KOWARI_IS = initSession.preallocate(new URIReferenceImpl(new URI(Tucana.NAMESPACE + "is")));

This has the undesirable effect of tying the URI of the predicate directly to this particular implementation of the code. The only reason a query can be made which matches this predicate is because of user documentation. There is no connection at all between iTQL and these predicates. It's just asking for one of the predicates to start failing due to a typo when a change is made. To make things worse, these predicate URIs are duplicated in SubqueryAnswer.

As a first priority, I've started moving these URI definitions to a new class called SpecialPredicates. From here they can be accessed by any class which wants to refer to the URI of the predicate, making them consistent across the system. This can also be used by the iTQL parser to recognize when one of these predicates is used, so that an appropriate kind of constraint object can be created.

Once these new constraint objects are created, there should be no need for node numbers to be created. The only reason I could see to keep them might be to prevent a magic predicate from being explicitly added to the database. I should ask AN about this and see what he thinks.

Xcode
Well, I'm getting used to the new interface. It has its strong points, but also a lot of weaknesses.

As a Java editor, it seems to be somewhat lacking. For a start, the only awareness of code in the editor is a selection widget which lets you navigate to any method in the current class. While this is nice, there is no list of member variables, nor is there any code checking for declared members, methods, or any other context relevant information. More annoyingly, comments are not detected during paste operations, meaning that when I paste a header into a new file, it thinks it is seeing tags which need special indenting treatment.

Another feature I was looking for was a hierachical class viewer. Xcode has one, but interfaces are kept separate from classes. This made it useless for tracking the genealogy of classes like ConstraintImpl, with its combination of interface and abstract class parents. I found it was faster and much easier to just look at the source code.

One useful feature I've found is CVS support, though it took me a little while to work out how to turn it on. It seems pretty good, but it appears to be a relatively simple wrapper around the "cvs" command.

I'm still discovering features, and I'm still struggling against my natural tendency to use vi commands, so I'll be giving it a bit longer yet. At this stage it looks like Xcode is really better for C and C++ development, and that I might want to consider something else for Java. KA has been using Eclipse, and I might give that a go shortly.

Luc
I wrote this a day late as Brisbane is having a public holiday for the Brisbane Exhibition, and I decided to have a restful night. I was happy to be home today, because I discovered Luc's first tooth has poked through. So all that lack of sleep has been worth it... I guess. Ask me again when he's two. :-)

Delays
I've been neglecting the blog over the last few days. Shouldn't bother anyone but me (it'll bother me when I come back later to figure out what I was doing on these days). The main reason for the lack of effort was my lack of progress to report on. The other reason was because Luc is on the verge of teething, and I'm suffering from a proportionate lack of sleep. :-)

Friday
Friday was spent trawling through code, and making few modifications. I did little bits and peices, mostly fixing obvious bugs and documentation, but nothing substantial. The majority of the time was spent reading the ItqlInterpreter class and working out just what it is doing with Constraint objects. All too often I've found that I've started coding before I was really ready, and I'm trying not to this time.

Monday
Monday was spent reviewing the same code. Constraints are badly in need of refactoring. Too many implementations of classes, which leads to some horrible workarounds for subclasses. It needs more interfaces, and the code which uses them needs to refer to these objects by interface references.

I also spent some time setting up Xcode. I'd been looking forward to using Xcode, but hadn't taken the time to set it up or work it out.

Xcode is fine for working with Java, but it doesn't really have full Ant integration. I followed a couple of pages which talk about using Ant, but really all they do is create a blank project, and then set the build command to call Ant instead. This didn't work all that well for Kowari, as it uses its own script called build.sh to launch Ant with a series of required parameters.

I resolved the problems by calling build.sh directly, and by modifying this script to suit my local system. I wouldn't normally want to modify a file in this way, but build.sh is very short, and mostly just manipulates environment variables. The first change was to tell it about my local JAVA_HOME when it's not already set. I do have it set in my bash environment, but it's not global where Quartz applications can pick it up. I've considered doing this with ANT_HOME as well, but since every other system is using the ant-1.6.1 jar in the lib directory of Kowari, I thought it might be safer to just go with that. Mac OSX comes with ant-1.5.3 as part of the J2EE packages, but I've since upgraded it to ant-1.6.2, which should be perfectly compatible with the Kowari version of Ant.

The other change was based on how the building script is called by Xcode. To do an ordinary build, the script is called with no arguments, and to do a "clean" then the script is called with a parameter of "clean". Since the ant script always needs a parameter I needed to test if none was passed to build.sh and if so then pass a parameter of "dist". While I could just change the default in the Ant build.xml file, the build.sh script is a much better place to change it. That's because this script almost never changes, while the build.xml file needs to be updated occasionally by myself and others. Keeping build.xml file untouched allows it to synchronize with CVS much better.

I then learned all about adding files into the project. I started by adding the files I needed manually, but these are so dispersed through the filesystem that I thought there must be a better way. I then found that by adding the directories out of "src" then it recursively picks up everything under it. Of course, if there'd been real Ant integration then it could have found all the files I needed, but this would be a huge amount of work on Apple's part.

I found that I couldn't go adn include to "org" directories which are two layers down from src, as these are not merged. As a result I ended up with several "org" directories with no indication of their contents. Using the directories like "store" is a little annoying, as there are sometimes files in the same package under different directories, and also because I have to go down through directories such as "store/java" to find "org".

At least it seems to know about CVS, as the CVS directories were not imported. Since that is the case I should look to see if I can do updates and commits from teh Xcode GUI.

I like the editing features I now have, particularly the persistent, named bookmarks. Finding files is pretty good too, once you get the hang of it. I'm sure that I'll learn more about the configuration later so I can make editing Kowari easier still. It will be a while before I'm proficient with Xcode though, as I'm still trying to unteach my fingers about vi.

Breakpoints, errors, and the like are unlikely to come naturally, as I think that Xcode is too far removed from the build system at the moment, but as I get more used to it I might see what kind of class path options I have, and whether or not I can tweak it into something more powerful than a fancy editor.

I've already downloaded Xcode 1.5, but I have not played with it yet. It seems to have better Ant support, but from what I understand this is so new projects can be built for Ant. I believe there is little support for importing existing Ant projects.

Inferencing for OWL
This morning I had a discussion with AN about the next thing to move on to. Of course, it makes sense to fully integrate the inferencing code with the rest of the system, but AN pointed out that this should be done after the move to resolvers. I agree, as the selection of the source and destination models for the inferences will depend on how we talk to the models.

In the meantime I'm moving onto an iTQL construct that will allow us to select cardinality, which is an OWL requirement.

AN's document on Kowari/TKS inferencing describes cardinality as a "magic" predicate in the "tucana" namespace. This is similar to the <tucana:is> predicate used to constrain on equality. I can work with this, and so I went to find wherever tucana:is gets mentioned.

It's a little messy, with XADatabaseImpl and Subquery both defining the same predicate. I decided to ignore what subqueries do, as I needed the more general case. The string for this predicate was being put into a constant called KOWARI_IS, and I tracked down all instances of its use. This then led me to the getKowariIs() method, on the Database interface.

It was a simple matter to add the new cardinality predicates wherever I saw getKowariIs(). Then I needed to apply them when I found them.

I found that the application of these predicates was happening in ConstraintResolver. This class had been introduced to enable the use of the Visitor Pattern on constraint classes. This removed the need for lots of switch statements, as had been the case when everything used to be done in LocalQuery. Unfortunately, the magic predicates were still being done with if statements interrupting the normal flow of data. Any attempts to do the same with the cardinality predicates was going to get very messy.

Discussing the code with AN, we worked out that the current implementation of magic predicates is messy and unmaintainable in the query engine. This is because existing constraints have to behave differently if they see one of these predicates. By moving the code for handling magic predicates up into the language layer, then a different constraint object can be constructed altogether. This is more object oriented, and will definitely help with maintainability.

Unfortunately it won't be as quick to implement this as it would have been to put in a dodgy hack to get cardinality. It should be cleaner and easier though.

Proof Reading
Once again it's way too late to spend any further time on this to tidy it up. I still haven't proof read yesterday's blog! (addendum: I have now).

In the meantime, I hope that it's not too difficult to read.

N3 Once Again
The class path was resolved quickly this morning, allowing me to finish the N3 importing.

First of all, blank nodes were parsed correctly, but an exception occurred when creating a URIReference from them. This was because subject nodes were not being checked properly to see if they were blank. After that the load worked fine.

So then I started a series of tests. I took the Jena camera ontology and loaded it into a model called "camera". I wanted to look at blank nodes, and this RDF file contains several. Then I saved it out as N3 to a file named "camera.n3", and was able to manually confirm that everything looked fine.

Next, I created a new model and named it "c2". I used the new N3 parser to load camera.n3 into the c2 model. Then I exported it to disk as "c2.n3" and compared it to camera.n3. Unfortunately, they were identical.

At first glance it would be a good thing for these files to be the same, as they represent the same data. However, when loading blank nodes into a system a whole set of new nodes must be allocated for each blank node. The fact that the nodes were being reused was a bug.

I mentioned the problem to AN, and this helped me to think about what the problem was. I realised that the caches which are used to map blank nodes must not be getting cleared out. A quick check confirmed this, and so I added calls to the clear methods on these caches within the startDocument method of the parser's event handler. This fixed it.

After N3 importing and exporting was working I started downloading the entailment tests from the RDF test page. It was a little annoying downloading each in turn, and this prompted me to check further down the page to find all the tests in a zip file.

Inferencing Goals
While swimming tonight I gave some thought to Bob's suggestion that I write a couple of pages on a real world example of what I'd like to achieve. The trite answer is to base it on the sorts of things we would ultimately like to do at work. The general idea here is to be able to take disparate databases, and to infer new and interesting information.

Maybe we'd like to say that a person "A" who is considered a threat, is a known associate of person "B", who traveled on the same flight as person "C" who works for a weapons manufacturer. Frankly, for this kind of inference I'm really reaching, particularly as I don't even know exactly what security experts would really want to see. Of course, we'd like to be able to provide the ability to do inferences like this, but if I try to come up with inferences of this type, then I run a much greater risk of choosing something which isn't really useful.

To start with, I'd need to show that a particular ontology can be mapped into RDF. If not, then I need to pick a different system. I don't have to actually map such an ontology into RDF, but I need to show that in principle it can be. Once I am confident that the information I know is in RDF, then I need to determine if it would be possible to infer information that I didn't originally know.

So I started thinking of the kind of inferences that I've personally made in the past. My goal then would be to create an inferencing system which can infer the same things I was able to. The first thing to come to mind was the fact that the light of a supernovae is preceded by a burst of neutrinos.

I was once describing the process of a supernova to a friend (in fact, it was AM, some years before he came to work at Tucana). I explained how a collapsing star has so much gravity that its inward rush is not stopped by electron degeneracy, but just continues on through it. Now if it continues to collapse through electron degeneracy, then the electrons simply can't continue to exist in their current form, due to the Pauli exclusion principle (electron degeneracy is the boundary of the Pauli exclusion principle where every possible electron state for the volume is being occupied). The way the star can continue collapsing is to merge its electrons with their corresponding protons (remember, stars are mostly hydrogen, with is just an electron-proton pair). Merging like this creates a neutron, and a neutrino. With all these neutrons being created, eventually neutron degeneracy is reached, and this is normally strong enough to make the whole collapsing star "bounce" back out. This is the explosion that we call a supernova. (If it kept going through neutron degeneracy then the star would become a black hole).

This process had been described to me in an astrophysics subject without the mention of neutrino generation. But as I mentioned to AM the electron-proton reaction part of the process, I inferred the part about the emitted neutrino, as my knowledge of that reaction told me that neutrinos had to be generated. At this point I realised that during the collapse preceding a supernova, an enourmous number of neutrinos must be created. The collapse takes place over several days (remember that stars are huge, so the speeds involved are still staggering), so neutrinos will be produced for the whole of this period. This reminded me of a media story I'd once heard about how the world's neutrino detectors would always show higher activity a few days before a supernova. Now I know why.

So the knowledge of the process of a supernova, the types of particles which make up a star, the rules governing the reactions of these particles, and the types of reactions which would occur during a supernova, all let me infer that a neutrino burst would precede a supernova by a few days. To a better physicist this may have been obvious, but for me it was a significant inference. If I can make a computer able to infer something like this, then I believe I'll have accomplished something significant. My immediate task is to convince myself that this is possible with RDF, with an inferencing system that is either OWL or an extension thereof.

Can I build the knowledge of the supernova process into RDF? I believe so.

I'd be describing a class called "Star" which is a subclass of "Stellar Body" (which is then a subclass of "Body"). It would have several properties, including size, which is the determining property for working out if it will go supernova (too small and it settles to a while dwarf, too large and it becomes a black hole). So the property of having a "supernova event" at some point in a star's existence can be inferred reasonably easily. The event itself has a sequence of sub events. These involve the collapse to electron degeneracy, the collapse to neutron degeneracy, and the bounce back. The collapse to neutron degeneracy has an associated electron-proton particle reaction. So I can trace this route of relationships down to stars of a certain size having a particle reaction as an event in their existence.

This then leads to an ontology for particle reactions. The electron-proton reaction has a neutrino produced. Linking the two ontologies shows that a star of a certain size will emit a neutrino at some point in its existence. In fact, going back to the size of the star, the number of electron-proton pairs can be inferred, and this can then lead to a number of neutrinos which can be emitted. If an ontology says that any emission over about 10¹⁰⁰ (I pulled that number out of the air here) can be called a "burst", then it will be possible to infer that the star with the right properties will emit a burst of neutrinos.

I need to break it down more than that, and then I need to work out what kind of operations would need to be done to allow this sort of inference, but intuitively I feel confident that it can be done.

Indexing Numbers
While building and testing Kowari today I started giving serious thought to the concept of our indexes as vectors in a space.

When Kowari started we had 3 indices. Our indices were actually orderings of statements, based on the first column, followed by the second, and finally the third. By having 3 indices we were able to define a constraint as 1, 2 or 3 nodes, and there would always be an index which would provide the resulting statements as a contiguous group. The start and end of this group can be found with a binary search, meaning that the data can always be found in O(log n) time. I've discussed this here in the past.

Moving on to 4 nodes (subject, predicate, object and meta) meant that we needed to use a minimum of 6 indexes to be able to quickly find a contiguous group of statements. But where did that number 6 come from? How many indexes do we need for a large number of columns? Does this represent some larger structure that we might be able to take advantage of. I've come up with some of the answers to these questions.

For a given system of N nodes in a single statement (N=4 for Kowari) then there will be a need to search when given a constraint of 1 node, 2 nodes, 3 nodes, and all the way up to N nodes (searching when you have a constraint of N nodes is the equivalent of doing an "exists" operation on a statement). It turns out that a search done with S nodes in the constraint will define a minimum number of indexes, which I'll call min_S. Finding the maximum value of min_S as S varies from 1 to N gives the minimum number of indexes required to be able to completely search the statement space. The indexes chosen to meet this figure will need to cover all the cases of other values of S.

Note that I have not proven that a set of indexes which meets the maximum min_S will always be able to meet the index requirements for all other values of S. However, the selection of indexes to search on S constraints must always take into account the other values for S. It appears that this is always possible, and after gaining the experience of choosing a few sets of indexes it seems that this would indeed be provable, particularly when S is less than the S for the maximum min_S.

The value for min_S for statements of N nodes can be determined with some simple combinatorial algebra, and it comes down to:
  min_S = N!/(N-S)!S!
(where is MathML when you need it?)

These maximum values are shown here for the first few values of N. The corresponding value for S is in brackets:

N

2       2  (1)

3       3  (2)

4       6  (2)

5       10 (3)

6       20 (3)

7       35 (4)

8       70 (4)

9       126 (5)

10      252 (5)

11      462 (6)

12      924 (6)

Hyperspace
Yesterday I discussed how a set of statements on N nodes forms an N-hypergraph.

Working with this supposition, one could assume that an index (of the type described already) forms a vector within an N-hyperspace. Perhaps category theory will show that this mapping into topology will let us determine something about our indices that we have not already seen.

Suppose that each index forms a unit vector, which is normal to a hyperplane. In 3-D (which is were normal RDF stands) these planes then form a cube. The three indices of:

  subject-predicate-object

  predicate-object-subject

  object-subject-predicate

form the normals of 3 sides of this cube. The opposite set of useful indices:

  object-predicate-subject

  predicate-subject-object

  subject-object-predicate

form the normals of the other 3 sides to the cube.

The dimensions here are the 3 labels (subject,predicate,object), and the index's vector is along the dimension of the first label. The curl of that vector corresponds to the remaining dimensions, and so subject-predicate-object is along the same line as subject-object-predicate, but in the negative direction. So the curl of a vector describes a path through the nodes of a statement. We can also see that the first three vectors are in the opposite direction to the second three vectors, and are functionally equivalent. This is why either set of indices can be used.

This is all fine for 3 dimensions, but does it hold for 4 dimensions and above? The answer seems to be yes.

In 3 dimensions we have 3 faces of a cube which define all our required indices. In 4 dimensions we have a hypercube, which has 24 faces. Since each face has 3 "opposite" faces, there are 4 functionally equivalent vectors normal to those faces. 24/4 = 6, which is the number of indices needed for statements of 4 nodes.

For 5 dimensions we no longer want to consider the number of faces on the hypercube. Going back to the maximum min_S table, note that the S value for N=3 and N=4 was 2, but for N=5 then S=3. Remember that S corresponds to the number of nodes to constrain on, which gets mapped to the number of dimensions we are searching on. By moving up from 2 dimensions to 3 dimensions we are instead looking for the number of opposing 3D volumes defined by the hypercube, rather than the opposing 2D planes. In 5 dimensions the hypercube has 40 volumes. Dividing this by the the number of opposing volumes (4) gives the 10 indexes required.

This pattern continues. For any hypercube of dimension N, take the S value for N from the table above, and use that to select the number of dimensions of the "sides" of the hypercube you are interested in, and find out how many of those "sides" the hypercube has. The required number of indexes shown above will divide evenly into that number, by a factor of a power of 2.

The number of sides of various dimensions can be easily determined by following the instructions here. The first few are shown here. The first column defines the vertices, the second is the edges, the third is the sides, the fourth is the volumes, the fifth is the hypervolumes, and so on:

N

0:    1

1:    2     1

2:    4     4     1

3:    8    12     6     1

4:   16    32    24     8     1

5:   32    80    80    40    10     1

6:   64   192   240   160    60    12     1

7:  128   448   672   560   280    84    14     1

8:  256  1024  1792  1792  1120   448   112    16     1

Programs
In case you've made it this far, yes the 2 tables above were generated with code that I wrote. Both a pretty trivial, but I might post them if I get some time.

In the meantime I have to get to bed.

Caveat Emptor I normally try and take the time to proof read what I write here. But this is a little lengthy, and it's now 12:45am. You'll just have to take the spelling and grammatical errors as they come until I get time to come back and fix them up. Jars The first order of the day was to establish my priorities again. While we know that better externalization will increase RMI speeds for AnswerPageImpl, TJ doesn't want to get bogged down in it for the moment. So I'm back onto the inferencing code. I'll probably try and do the externalization in my own time soon. In the meantime I ran the full test suite for the current changes, and when they passed I checked everything in. That reminded me that I have a checkout that continues to fail the Lucene tests. I guess I should blow that checkout away. Because RDFS tests are mostly defined with N3 files, I went back to trying to load N3 again. The first step was to rebuild everything with the latest checked out code. Well it turns out that there have been build changes again and now TKS isn't building with the latest Kowari core. The build is complaining that it can't find a method that appears to be there. I'm not going to get bogged down in a problem like this again when the code belongs to someone else, so I decided to do the work directly on Kowari. Since this is all for inferencing, I thought I'd get the inferencing code working with the current checkout. This is because I need it working when I get off the N3 task, and because I thought I could try saving the inferred data in N3. Only this ended up being easier said than done. The latest Kowari updates have changed version numbers on the jar files, and this ruined all the class paths. Worse, the contents of the jars appear to be different. When I extracted all the inner jars from itql-1.0.5.jar it had a shorter list than the contents of itql-1.0.4.jar, and I can't get the inferencing code to run anymore. Just like the TKS code, I had no desire to go chasing down jars, so I decided to leave it until I need it running. N3 Again I finally ran a Kowari instance, loaded some data into it, saved it to N3, and tried to reload it. The first thing that happened was an exception which complained of bad tokens in the Prolog of a file. A check confirmed that the file was being loaded with the RDF loader, which was definitely the wrong thing. It turned out that the RDFLoader.canParse method is erroneously returning true on N3 files. I should check out what this method does for its test. Since my test for parsability of N3 is really only interested in the filename extension for the moment, I figured that it can't hurt to test for N3 before RDF/XML, and if it matches then attempt to use the N3 loader. I know it's a hack, and just writing about it now makes it seem worse. However, it works for the moment, and the correct loader is being run. Unfortunately the Jena N3 parser wouldn't run initially because of missing Antlr classes. This seemed strange, as I'd explicitly added this jar into the path in the build.xml. A little checking showed that I'd only done it for TKS, so I ported it back over to Kowari. However, while I found many of the appropriate build targets, I had to ask AN before I could find the last one, which has since been moved out into an external XML file. After a fresh rebuild I discovered that the Antlr jar was still missing. I'm now looking directly in the main jars, at the list of all the sub jars. The build code is definitely including Antlr, but the resulting jar files do not have it included. I'm stumped. I'm going to have to start running Ant with full verbose output, and maybe even run the jar program by hand. This sort of thing gets really annoying when you have coding you want to get back to. Yes, I'm overtired today, so I'm allowed to be irritable. Masters I had another meeting with Bob today. As usual, he had some great insights for me, and I have a couple of things I want to get accomplished in the next 2 weeks. For a start, I need to sit down and come up with a concrete example of what I want to do, and why. "Scalable OWL Inferencing" doesn't cut it. I need to be able to say, "I have this data, and I want to be able to infer this other data, and OWL is what can provide it for me". Or maybe "OWL can't do it for me, but I need it in order to build the inferencing system that can do it for me". Does anyone have a suggestion of some useful, real world information that OWL can either derive or help me to derive? If not, then what's OWL good for? I have some ideas of my own, but I'd love some feedback. The other thing that Bob pointed out is that I really need to look at a couple of texts, rather than just reading papers. The texts provide the foundation of knowledge, while the papers really only seek to expand on it. The first one I'm looking for is on First Order Predicate Calculus, by Chang and Lee. Apparently the field hasn't changed all that much since this book was first written. I've yet to confirm, but I think the book is "Symbolic Logic and Mechanical Theorem Proving".
Indexes and Hypergraphs While thinking about role of directed Hypergraphs in modelling RDF, it occurred to me that I hadn't considered the "direction" enough. After all, it's a directed 3-hypergraph. The direction forms a loop around the triangle of subject, predicate and object, but I hadn't really considered a starting or ending point. That's when I realised that Kowari's indexes reflect this already, as they are quite symmetric, with no emphasis on any point defining a beginning or end:

  subject predicate object
  predicate object subject
  object subject predicate

I also noticed that if this loop were in the opposite direction then it would form the other set of 3 indexes which can be used for these statements:

  object predicate subject
  predicate subject object
  subject object predicate

Now each statement is a plane intersecting 3 nodes in the graph (in a 3 dimensional space). Each plane has 2 normals, which are perpendicular. The direction of the loop that the statements form would correspond to the curl of those normals, with one normal defining the subject-predicate-object direction, and the other normal defining the object-subject-predicate direction. I thought this was interesting, and so I speculated on whether it can be extended to higher dimensions. This is relevant, as Kowari moved from a 3-hypergraph to a 4-hypergraph some time ago. I had speculated that each normal of a 3 dimensional plane was corresponding to a direction around the nodes, and this in turn corresponds to a set of indices that can be used to do a search. I've been wondering how many "normals" there are to a 4-dimensional plane, and if they would each correspond to a set of indices that can be used to search the space. To do that I'd need to know how many normals there are to a 4 dimensional plane (a question I haven't checked the answer to yet) and how many sets of indices there are which can search "quad" statements instead of triples. We had found about a dozen 3 years ago in an ad hoc approach, but I needed to search the whole set of possibilities exhaustively so I knew I had them all correct. Indexes Calculations Thanks to AM for helping me on the following. There are 24 possible indices on the 4 elements of a quad (that's 4!. Note that I'm saying "4 factorial" and not just adding emphasis). It doesn't take long to show that to be able to match any individual node will take a minimum of 4 indices, and a pair of nodes will need a minimum of 6 indices (these 6 subsume the first 4). Each of the indices must be selected from one of 6 groups of 4 indices. To allow searching on 3 nodes restricts the choice from these groups, as certain combinations are mutually exclusive. Searching on 4 nodes need not be considered, as any index will do this for you. Searching for 2 nodes in quad statements proves that 6 indices are required (no I'm not going to put a proof here - it's after midnight). So we know we need at least 6 indices. It's actually pretty easy to select a set (and we did), but for this exercise I'm interested in finding out how many sets are valid. If we consider all possible combinations of 6 indices from the 24 possible we get (24 * 23 * 22 * 21 * 20 * 19), or 24!/18! = 96909120. However, this includes a lot of index combinations which won't let you search for certain node combinations. It took a little while, but we eventually arrived at the final figure. The number of sets of indexes which can be used to do any kind of search on 4-hypergraph is 3520. This was a LOT larger than I'd expected, but we went over it several times, and I'm now confident that it's correct. At this point I decided that each set does NOT correspond to a normal to the hyperplane. I still think that some sets will correlate with 4 dimensional loops through the points, and perhaps there is a normal to describe this loop, but I no longer think that every possible set will correspond to a loop. Many of the index sets are almost identical, with only two of the indices swapping the order of their least significant nodes. They would seem to be parallel in their most significant dimensions, and hence demonstrate a lot of redundancy. AM wants to see if we can extend this calculation to n nodes. After what we had to consider to find this number for just 4 nodes (a fixed number of nodes for a start) then that would be a major undertaking. In the meantime I'm thinking I should write up what we did to find this value. I'll try and make a start on that on Saturday.

Weekends
I thought that I might take some time over the weekend to do some more work on either the N3 loader or moving Answer pages over RMI. Between family, DVDs and fitness it never happened. Oh well, I guess we're supposed to clear our minds on the weekend. At least I have a new first aid certificate from St John's to show for it.

Paging All Answers
I went back to the externalization of AnswerPageImpl today. I planned to spend the whole day making all of the components of an answer externalizable. That's externalizable, as opposed to serializable, in order to avoid the metadata overhead. This is possible because there are no real parent classes to consider for any of the components of an answer.

In many cases it's possible to represent a component of an answer as a string and a datatype. Datatypes include URIReference, BlankNode and Literal (although Literals may require their own datatype). Representing components in this way has very little overhead, and should reduce the significant time we seem to be spending on the default serialization employed by RMI. At this stage I'm thinking of using the default serialization of a java.lang.String as there seems to be a lot of work in the JVM to handle this class, and I'm assuming that RMI is probably pretty good with strings as well. Besides that, if I tried to do it myself with a char array and a length, then I'd probably make some erroneous assumption about Unicode for non-latin alphabets.

In the first instance I pulled apart the AnswerPageImpl at a higher level. Other than a few integers and booleans, the entire dataset is a java.util.ArrayList of Object[], with each array being of fixed length. This was easy enough to encode as a pair of integer dimensions, followed by all the elements as an unstructured list. This didn't cover the expense of serializing each of those elements, but it did take two seconds off a 73 second transfer. Given that this only addresses the small amount of data in the wrapping objects, and does not consider the 3000 elements in each page of the answer, then this modest improvement shows that this is certainly on the right track.

However, testing this small change ended up being more difficult than expected. Because the tests involved a transfer between two computers, I've been using TJ's computer for a lot of the work. This is partly because TJ has been with me quite a bit during Friday and today to help out and see how I've been progressing. I checked for differences in the source code to CVS this morning, but I didn't realise that TJ decided to update the source code shortly afterwards. In the process it pulled down a modification that AN made to an RMI class, which resulted in a need for a new serialization ID. The consequence was a class that wasn't being rebuilt, but which needed to see the new ID, and that led to lots of RMI failures.

Since I had been making changes to the serialization of objects which are sent over RMI, I naturally assumed that the bugs were my own. I spent an inordinate period of time adding logging to my code, and seeing it all fail without a single log message. Finally TJ asked how I was going, and when I told him of my consternation he explained that he'd updated the source. After removing all compiled classes that were dependent on AN's new modifications, a rebuild got it all working again.

Well, it worked right up to the NullPointerException that I caused! It was that old gotcha that I keep forgetting... readExternal (and readObject) does not run the default constructor (yes, I know that's a C++ism). Hence, the ArrayList was not instantiated yet. Easy to find, easy to fix.

Once it was going it was easy to see that we'd gained a little in speed, and that I was on the right track. It is frustrating when these things take so much longer than they should though.

Compression Revisited
While restructuring the externalization code, the readExternal and writeExternal methods started getting unwieldy, so I started pulling sections out and into their own methods. While showing some of these to TJ, and describing parts of the compression/decompression code that he hadn't seen, I realised that I'd missed an obvious optimization.

As I mentioned in my last post, compression was slightly faster when it was performed on an entire data buffer at once, rather than streaming on an ObjectStream. On reflection, this made sense. Correspondingly, it made sense to decompress the entire buffer at once. This needed a length prepended to the byte stream, but otherwise didn't need too many changes.

The original code to get an ObjectStream was:

byte[] byteArray = (byte[])in.readObject();

InputStream byteStream = new ByteArrayInputStream(byteArray);

ObjectInputStream data = new ObjectInputStream(new InflaterInputStream(byteStream));

My first attempt to decompress the data in one hit appeared like this:

int uncompressedSize = in.readInt();

byte[] byteArray = (byte[])in.readObject();

InputStream byteStream = new ByteArrayInputStream(byteArray);

byteArray = new byte[uncompressedSize];

(new InflaterInputStream(byteStream)).read(byteArray, 0, byteArray.length);

byteStream = new ByteArrayInputStream(byteArray);

ObjectInputStream data = new ObjectInputStream(byteStream);

This code threw an exception which described an unexpected termination of the data stream. Logging what was going on showed that the read method was only returning 611 bytes, when I expected 55620. Since I knew that the buffer size of the InflaterInputStream is 512 (I'm assuming this number is in bytes, but there's nothing to confirm this) it appeared that the read method is restricted to the current buffer page. So it was easy enough to overcome by looping on the read method until all the data was read.

The result of this was to knock 14 seconds off a compressed transfer that had taken 88 seconds with the previous implementation of compression. That brought it to within a few seconds of an uncompressed transfer.

Buffer Sizing
Since it had become apparent that InflaterInputStream.read() needed to be called numerous times because of the buffer size in the InflaterInputStream, it seemed reasonable to revisit the issue of buffer size.

I initially thought that using the same buffer size on both ends would be appropriate, but it quickly became apparent that this was not the case. Increasing the compression buffer size had a very small effect, but only when the page size was increased significantly, to about 8kB. I also tried up to 16kB, but this was just a little slower, so I stayed at 8. The result of this was about a half second improvement, which was almost lost in the noise.

The decompression buffer size had a much more significant effect. Increasing from 512 bytes to 1024 took 2 seconds off straight away. Going up to 8kB or higher started to slow it down again. In the end I settled on 4kB. This may not be exactly the perfect size, but it provided the greatest improvement for the tests which I'd tried. Different shapes of data may result in slightly different buffer sizes being the most appropriate, so I saw little point in doing a binary search to look for the "perfect" buffer size.

The final result is a compressed transfer which takes exactly the same length of time on our network as an uncompressed transfer. On slower or congested networks this should offer a good alternative. Hopefully I'll get even better speed improvements tomorrow with properly externalized answer elements.

Compression
I still didn't get to testing the N3 import code today.

TJ has been concerned about the time taken to return large amounts of data over RMI. He has wanted to compress this data for some time, and so he started doing so today.

When the code first failed for him I came in to have a look, and discovered that he hadn't been looking at the right file. I offered a few points of advice, but then ended up staying for a bit longer. A bit longer went on until mid-afternoon when TJ had a conference call, at which point I continued on trying to do compression.

Using some standard examples, TJ was trying to compress all communication with an RMI object by making sure that the object was an extension of UnicastRemoteObject, and then he provided his own socket factories in the constructor. This worked well, so long as he didn't try to wrap the data streams with a compression object.

To start with, TJ had tried to use ZipInputStream and ZipOutputStream, but these are designed for file compression, and the decompression call immediately complained about the item number. This was resolved by moving to an appropriate compression utility such as java.util.zip.DeflaterOutputStream or java.util.zip.InflaterInputStream.

As soon as the correct compression streams were in place then it would all come to a halt. This was happening because the server was not sending back its response. I realised that this was because of buffering on the compression stream, and that it just needed to be flushed to make sure the data was sent through. However, RMI normally works across a socket which doesn't need to be flushed, so it never bothers to flush.

Externalizing
After thinking about it, I decided that there was really only one time that data really needed to be compressed, and that was in the return of AnswerPageImpl objects across the network. If these could be serialized to a compressed form then most of the network traffic would be reduced. So I moved onto implementing readObject and writeObject. TJ pointed out that profiling had already showed significant time was being spent in reflection during serialization, so I pulled back and went on to readExternal and writeExternal in the Externalizable interface instead. This is because of a lot of metadata about the class is avoided when using Externalization over Serialization.

Now that I was writing to the compression stream myself, I was able to flush the data stream, but again the server would just sit there and not respond to the client. I talked with DM about this, and tried a few other things, before it occurred to me to close the stream instead of flushing it. This worked correctly. So now I know that flushing to a DeflatorOutput does nothing. It won't be prepared to send data until it is closed.

Compression Performance
Once compression on the returned data was working correctly TJ and I could start timing the responses. TJ loaded WordNet into the database, and performed a query which returned all the data to the client. The queries went over a 100Mb network, through 2 switches.

With compression we were able to return the data in about 1 minute 40 seconds (1:40), with a compression ratio of about 80%.

Without compression we retrieved the same data in 1:13. Something was obviously wrong here. The compression/decompression was being run on 2.8GHz P4 processors, and they should not have even blinked at this kind of operation.

This led to me checking all sorts of things, ranging from compression ratios and times of execution, through to buffer sizes and compression levels.

Double Buffering
I had initially created an object writing stream with the following code:

  ByteArrayOutputStream data =  new ByteArrayOutputStream();

  ObjectOutputStream objectData = new ObjectOutputStream(new DeflaterOutputStream(data));

  // write to objectData

I could then use data.toByteArray() to get the resulting bytes. However, this wouldn't tell me how much compression we were achieving. So I changed it to look like this:

  ByteArrayOutputStream data =  new ByteArrayOutputStream();

  ObjectOutputStream objectData = new ObjectOutputStream(data);

  ... // write to objectData

  ByteArrayOutputStream zData = new ByteArrayOutputStream();

  DeflaterOutputStream deflater = new DeflaterOutputStream(zData);

  deflater.write(outputData);

  deflater.close();

The result of this was that data.toByteArray() could provide the raw, uncompressed data, while zData.toByteArray() provided the compressed data.

While the presence of both sets of bytes allowed me to obtain more information about the compression rates we'd achieved, I assumed that there was some cost, since an extra byte buffer was being unnecessarily created. I assumed incorrectly. When I compared the times of both methods, the code with the two ByteArrayOutputStream objects was consistently 3 seconds faster (over the ~1:40 time period). Having both objects available is handy, especially for metrics, so I was more than happy to get this result.

Why did the use of a second buffer speed things up? I can only guess that writing the entire data stream in one hit was faster than compressing it by parts, as the first method does.

Bad Compression
Out of frustration with the longer times taken to return compressed data, I started playing with the compression level and buffer size.

Looking at the Deflater code, I discovered that the default buffer size is 512. I was not able get any real performance change out of varying this size.

The other thing to try was the compression level. Neither the documentation nor the provided source shows what the default level is. So I did some comparisons with compression set to 1 (minimal) and 0 (no compression). The results here surprised me.

Minimal compression still gave me a compression ratio of about 80%. This could mean that the default level is 1, or close to it.

Even more surprising, a compression level of 0 took almost exactly the same length of time to execute as a compression level of 1. ie. ~1:40. This was surprising, as 0 compression should have taken no time, and yet the code was still being slowed down by over 20 seconds compared to no compression at all. So there is significant overhead in calling the compression library, but actually doing compression while there was not taking an excessively long time.

So where is the overhead in compression coming from?

The Deflation classes use JNI calls to do the actual compression (even when the compression level is 0). So the problem has to be either in crossing the JNI boundary, or in the compression algorithm itself.

Java relies pretty heavily on JNI, and it is normally quite efficient. I've certainly never seen it behaving slowly in the past. That leads me to think that the compression algorithm is at fault, possibly in scanning the data to be compressed (which would happen even with a compression level of 0). DM pointed out that Sun ignore the zlib libraries on *nix platforms and that they implement these libraries for themselves. Given the performance I've seen here I'm guessing that they have done a terrible job of it.

Compromise
While it offers nothing yet, compression may still be of benefit across a slower network. I've introduced a system property for a compression level, and I use this to select in compression when the level is above 0. If the level is undefined, or defined at 0 then the uncompressed byte array is used as the serialized data, compression is not performed at all, and there is no performance penalty.

Fortunately, having the uncompressed byte array hanging around was speeding things up, so there was no performance penalty in using it.

For the moment, the system property is necessarily defined at the server side. This is because it is the server which sends the pages back over the wire, and it is at this point that the compression is performed. If compression is to be used seriously in the future then the client should be the one to set the level. This means that client requests for pages should include the desired compression level as a parameter. This is easy, but unnecessary for the moment.

Future Speedups
There are two ways I can speed up returning pages like this.

The first is to use a decent compression algorithm. The ones that come with Java 1.4 are obviously too inefficient to be of use. Most implementations are unlikely to be blindingly fast unless they are done in native code, in which case there is the major problem of portability.

On the other hand, I may be too quick to assume that a pure Java compression would not be as fast. This should be the subject for some future study.

The second option is to improve serialization of the AnswerPageImpl class. Profiling has shown that at least a third of the time taken to return a query is spent performing reflection to serialize this code. Since we know exactly the kind of data that can be found in a page, it would be much more efficient to write only what we need to the data stream. This would save on both the amount of data sent, and the reflection needed to find this data. It is this approach which I'll be taking in the near future.

Lucene Index Locks
After Wednesday night's blog I was able to find all the build problems and compile everything. The problems were due to using the right import statements, in the wrong files. Well, it was getting late. As I said at the time, I just needed a break in order to find the problem.

I didn't get to Thursday's blog since I didn't get to do much productive work. Before proceeding with testing the N3 loader I wanted to make sure that I had a stable system and hadn't broken anything. So of course, when the Lucene tests started failing I had to start wondering what I'd broken, and how.

My first thought was that I could not have possible broken the Lucene code, as the N3 loading code was in a completely unrelated area. However, I've been mistaken in the past when I thought that two pieces of code were completely unrelated, so I wasn't prepared to dismiss the possibility of the problem being in my code.

The test failure was caused by Lucene failing to obtain a lock on a file. Perhaps it was some file access I'd done which prevented the lock from being acquired.

Each time I ran the tests it took quite a long period to get through them all. I was able to track the Lucene tests down to the store-test target, so I tried to concentrate on running this test only. I quickly discovered that the Lucene tests would always pass when the tests were restricted to the set of tests in store-test, and they would always fail when run as the full set of tests for Kowari. So now I started to think that it was some test which ran before the Lucene tests which was causing the problem. Perhaps I'd influenced this other test in some way.

To confirm that it was definitely my code which was causing the problem, I got a fresh checkout of Kowari, and tried a full build with all the tests. All the tests passed, further indicating that it was my changes which had caused a problem, though I still couldn't work out how.

I asked advice from AN and TJ, but they couldn't help. TJ was able to tell me that these errors had been seen before, but was unable to say what they were indicative of.

Finally I started copying my files from my normal Kowari checkout to the clean checkout, one file at a time. I did this to see which file could be causing the problem. By the end of the day I had copied over every file, and the fresh checkout could still run all of the tests with no errors. I finally started comparisons between all the files in both checkouts, and there were no differences.

So at the end of the day I had two sets of identical files. One would build and pass its tests every time. The other would build but fail its Lucene test every time. This morning I even used find to run through all the files and do an MD5 comparison, but they came up the same.

All I could do in the end was to abandon the checkout with the failing test. I have no idea why two identical sets of files can behave differently. Time to stick to the working checkout and move on.

Nearly There With N3
I was feeling tired and belligerent last night as I wrote my blog. Consequently I wrote that I was going to use a regex to parse N3. This isn't as bad to implement as it sounds, but I still had no real intention of doing it. Going about it in this way would mean re-inventing the wheel. Worse yet, it means that every little corner case of N3 that I hadn't considered was going to be plaguing me for months.

I wrote what I did last night in the hope that someone would say, "You moron! Why aren't you using the XXX parser?" I'd done a quick look for parsers, but the ones I'd found were too heavily tied to their applications and using them was going to be more work than they were worth, so I was hoping to be directed at something more portable. The response I received was from AN (and it was more pleasant than calling me a "moron") when he suggested I use the Jena N3 parser.

Fortunately, the Jena parser is event based, making it easy to hook into it. It only took me a half an hour to knock up some quick code that would parse and print an example N3 file (less than that to use the built in N3EventPrinter class, but I needed to try it for myself). So I ended up thinking that I should be able to make up for the last few days when I feel I haven't really done all that much. But it's now after 10:30pm, and I've only just now finished the main structure of it.

There was a LOT of glue to put this parser together with Kowari. I was able to base a lot of it on the RDF-XML parser that Kowari already has, but there were still significant differences. All up, it took over 700 lines of code.

The biggest hassle was converting from Antlr AST nodes to Literal nodes or URI references. I didn't have all of the Antlr code available to me (I just had the jar, but I could possibly find the source if need be), and I couldn't find any documentation easily. The N3EventPrinter offers some tantalizing hints, but it leaves a lot open to the imagination. Also there is a plethora of Antlr types, and I'm pretty sure that most of them aren't applicable to N3, but I couldn't work out which ones were. There are a few obvious ones, particularly anonymous nodes, literals, and URIs, but beyond that I don't really know.

At this point I'm thinking that the best approach might be to just "suck it and see".

I'm still a way off running though, as I have a compilation complaining that it doesn't know about classes I've included, and put into the class path. Once I got to that point I thought it worth blogging where I am and then taking a break.

N3 Parsing
AN pointed me to the class he'd been talking about, which is RDFSyntaxLoader. He'd given me the impression that I'd be finding a class that did a significant portion of the work, but when I saw the name I realised that this was not the case. Instead, it demonstrated the use of an IntFile as a map from anonymous node IDs to internal node IDs, and a StringToLongMap as a map from blank node names to internal nodes. These are important, as they can be disk-backed, which means that the maps are not bound by memory so they can scale.

If I'm only having to load anonymous nodes from our own N3 files then I don't need the name mapping, though the IntFile map is still needed. If I'm loading more general N3 files then I'll need to map by name, but it will also depend on whether I can spot anonymous node formats.

I'm just using a regex to parse the first part of each line. It's easy enough to pick everything out from the < and > characters. Unescaping text is reasonably straight forward as well, particularly as many escaped characters are only legal for literals, meaning that they don't affect subjects and predicates. What I haven't done yet is the last part of the line, which can be either a resource or a literal. It shouldn't be too hard, given that the first and last characters tell you exactly what the type is (a resource or a literal).

Syntax and Semantics
I spent a little time responding to suggestions from AN about how we implement a NOT operator in iTQL. There's the semantic issue of negation vs. and inverse, and that is still being argued. SR pointed out that depending on the semantic we choose, then the word "not" may not even be appropriate.

There's also the syntactic issue of how to express the construct in iTQL. Should it be a unary operator, preceding constraints in brackets, or should it be a "magical" predicate like <tucana:is>? Of course, different syntactic choices imply different semantics, so this question is not completely divorced from the first. Until semantics are determined then syntax can't be decided either.

You'd think that this would mean the semantics should be settled first, and then syntax decided, but these things are never quite that straight forward. People often like to conceptualise a semantic in terms of some expression, ie. the syntax. So it can be very difficult to pin down exactly what semantic is to be used without expressing it in some kind of formal language. Instead of introducing something as formal as predicate logic, it makes more sense for most people to think of the semantics in terms of the iTQL which is likely to represent it. So the semantics and syntax end up getting decided in parallel.

AN has lots of suggestions for both, and I spent a little time giving him feedback on it.

Short Entry
I know it's not much, but that's it. I didn't get as much done as I'd have liked today as I had to spend some time with a physiotherapist treating an injury, and it took longer than I anticipated.

N3 Reading
Not a lot to talk about today.

The N3 export is now working, after taking longer than I expected. Part of the effort (and this includes Friday) involved changing some of the exporting code to handle multiple export modules. This was a little further reaching than I thought, since the original code was heavily tied to class implementations without any use of interfaces. Note to self: have a chat about it to RT.

I should mention that RT is still very new at coding, so he's still learning a lot. However, this was my first real opportunity to go through his code, and overall I'm impressed. Better than I was at his age.

After a little more discussion on the command to be used for exporting, AN and TJ confirmed that it should definitely be based on the backup. Whether or not this is the cleanest thing to do, it means that the iTQL language does not need to be changed significantly, which in turn restricts the modifications to the documentation, tests, and training material for TKS. I have to admit that this alone makes it the right way to go.

At the moment the type of export is entirely based on the filename extension. Files are assumed to be for N3 format if they end in ".n3" or ".nt". As a compromise, a future extension will add a modifier to the backup command which allows an override of the file format.

N3 Writing
I'm now partway through N3 importing. I'm expecting to hook in an N3 reader and not have to do a lot more, but I've yet to see if it will be that simple. For a start, the N3 reader was not where I expected to see it, so I'm still hunting for it. More importantly I don't know if it will import blank nodes correctly.

Blank nodes are currently being exported in a format of: <_node##>. Since there is no standard for this in N3 (or am I wrong there?) then I'm happy to leave it like this. I'm just going to have to make sure that they get loaded correctly. If I can't make an importing module read this correctly then it won't be difficult to load the N3 myself. That's one of the big advantages of the format.

Directions
As I said on Thursday, there are lots of things to do next, and I was trying to work out hte best direction to take next. AN suggested that exporting and importing N3 would be a good idea, as other people need it as well. This suited me well, as it let me put the decision off for another day.

After creating an "export" command in the iTQL grammar, I learned that the "backup" command already writes either binary backups, or RDF. Since this function is already overloaded, it made sense to back out the "export" command, and just overload the "backup" command a little more. I didn't quite finish, but it will soon write N3 files if the output filename has a .n3 extention.

XQuery
The main reason I didn't get a trivial thing like N3 exporting done was a longish video conversation with SR. We discussed a number of things, including the appropriateness of XQuery for the DAWG.

It seems that XQuery can query RDF data with few technical problems. I had thought that this would be the answer to all potential problems, and that XQuery would therefor be a suitable strawman. However, SR made the important observation that while XQuery can find any required data easily, providing an API base on XQuery is problematic.

The easiest way to describe the problem is to go back to that old comparison with SQL. SQL is very restrictive, partly in the structure for querying, and particularly in the structure of the returned data. However, for programming an API it is this very structure that makes it so useful. Any returned data comes back with elements formatted in rows of typed columns. This allows an API to retrieve any element, typically with statements which iterate over the rows, and accesses the elements by column.

XQuery is much more open, both in methods of retrieving data, but also in the returning format. While the flexibility of the query structure is advantageous, the same characteristic is a problem for the returned data. XQuery has the ability to format returned data in any manner of format, from an RDF document through to an Excel spreadsheet. This felxibility is a liability for a potential API, as there is no consistent way to access the returned data. Unlike SQL, it is possible for a user to create a query that returns data in any possible format. Even if a return format is specified, then a user can always create a query that doesn't follow it, breaking any API that tries to wrap it.

While a full-featured and flexible query language is useful, one which cannot be effectively wrapped in an API is a liability.

I'm sure SR has more to say on this, and I'm looking forward to how the DAWG approaches his results.

Comments
For anyone interested in the response I received from Jeff Pollock regarding his submissions to the DAWG, I added a reply to his comment. Comments can get lost down there in the fine print, so I thought I should make a significant reference to it here.

BTW, thanks for responding Jeff. It's always nice when someone pays attention. :-)

Duplicate Variables
AN had a look at the problem of repeating a variable name in a select clause, and spotted a simple way around it. I know it isn't ideal from the perspective of AM, but personally I prefer it as it makes sense to be able to make a query like this. Consequently I was able to change rules 5b and 7b to match the other rules.

In a similar vein, I discovered that count statements also have a problem in select clauses. Count statements are used for "grouping" on variables (as they do in SQL). However, if a count is used without any accompanying variables then a RuntimeException is thrown from the server. Of course, this is appropriately caught and dealt with, but the fact that an exception like this can be thrown is a bug. The only exceptions to be thrown during a query should be thrown from the iTQL interpreter, and no lower. The interpreter should not pass down any kind of construct that is illegal, and if it isn't illegal then the code that executes the query should not throw an exception (except under exceptional circumstances, like a server being unreachable). If anything lower down the stack than the iTQL interpreter throws an exception due to a grammatical construct then it indicates a major problem.

In the meantime I've logged the count problem on Sourceforge.

Tweaking
I tweaked the rules a bit today in order to make them faster. There was a little re-coding, and I re-ordered the tests in the .drl file. It seemed to help, but I'm still not completely happy with it.

Given the way that the system is currently built, the biggest problem is due to all of the rules objects having the same type. Drools needs to test everything in the working memory by label in order to make sure that it has the objects required for a rule. This is really because Drools was designed to work on data which is in its working memory, rather than rules objects which in turn work on the data. It's made me think that it might be a little to heavyweight a framework to provide what we need, but I'm sticking with it for now. After all, it is working.

As I mentioned yesterday, it may be possible to make Drools operate a little more efficiently if each rule is given its own type. However, I don't really like that idea, as it doesn't scale to new rules at all. I'm also thinking that Drools might simply find its variables via instanceof statements, meaning that a label comparison is almost as efficient anyway.

The other change I could make would be to have the rules objects operate on Kowari/TKS at a lower level than iTQL. However, this means that each rule would need to be coded in Java, and not really configurable. So long as efficient iTQL commands are available then I don't see that much would be gained by this approach. For the moment, not all of the rules have efficient iTQL at their disposal, so it's a tempting avenue to take, but I think it should be avoided as long as possible.

Shortcomings
Rule XI is desperately in need of prefix matching to be made available from the Kowari/TKS string pool. This would be relatively easy, given that strings are stored in lexical order, but no one has the time to implement it.

While on the string pool, another problem is a lack of types. This has a major implication for finding anonymous nodes. Since statements are being inserted into the inferrence graph in bulk, then the only way to remove anonymous nodes is to go through after the insert and remove them one at a time. This is the second worst possible solution (the worst would be to filter the inferred statements before inserting them one at a time). Types would let us select all statements containing a "resource" in the appropriate position, skipping the anonymous nodes.

The other immediate problem is tautalogies. That is, inferred statements which exist in the base data. It's a shame that inferred data has to go into a separate model, as redundant insertions into the base model would get silently and efficiently dropped.

Testing and Integration
With RDFS going I'll need to check the tests on the RDF site. Unfortunately I'll need to build a translation layer, as Kowari doesn't yet allow for N3 output (which these tests rely on).

I talked with AN about integrating the inferencing rules with the rest of the system, but he hasn't yet worked out where he'd like them inserted. I know that he doesn't want to make a decision that makes it hard to use the rules for backward chaining, but I think that the choice of Drools is never going to work for that anyway. Hopefully we can discuss that in the morning.

Extending the Rules
RDFS is only the first step on a long road of inferencing. Next will be OWL Lite. I have yet to determine what the rules will look like there, but I know that many of them won't be like the ones for RDFS.

Apparently Jena tried to go with simple rules for OWL, but had to incorporate a lot of Java code to do it instead. I think I'll go through the list of available inferences first, and see which ones map easily to iTQL-based rules. Then I'll see what is needed for the remaining ones (the obvious one that comes to mind is cardinality). These should individually be easy enough to implement, but a generic framework would certainly be better.

Non-Rules Solutions
The whole rules-based structure has not left me feeling impressed with their efficiency. It is possible to make each individual rule more efficient (such as we did the trans statement, but the overall structure has not received all that much attention. I asked Bob what he knew of alternatives, and he suggested something called tableaus. I know nothing of these yet, but I'm thinking I should check into them shortly.