Day 2

Once again, I'm writing a lot of my own thoughts here, rather than just trying to keep a track of everything that happened at the conference. If you're interested in that stuff, then I'm sure lots of people wrote about it. For me, I found that it got me thinking about a lot of things, which is the main reason for me to write.

Random Thoughts

This doesn't mention any sessions at all. I just had a series of thoughts on various topics as they got mentioned at the conference, and thought I'd note them down.

AllegroGraph

My last couple of posts mentioned AllegroGraph and immediately started diving into the Mulgara implementation. One justification for this is that such a well advanced system inspired me to examine where Mulgara is, and where we want to take it. However, on some level I confess to feeling a little jealous. After all, we had the chance to be even more advanced than this, but lost it. However, we still seem to have a few unique features, and have more coming (which I'm sure you'll hear about soon).

From a philosophical point of view, having high quality open source infrastructure will help enable the Semantic Web to progress in the same way that it helped the Web and Web 2.0 to develop. Even when a project demands access to some of the features that only commercial vendors provide, an open source alternative can help bootstrap a project in its early phases, and provides competition for all to benefit from.

So while I may feel a little jealous, I'm hoping this will help inspire me to get Mulgara to do more. It can't just be Andrae and I though. Fortunately, this conference appears to have helped us there. We may be getting some more help from places like Topaz, but I'm also hoping to lift the profile of the software. After all, the more people who use it, the more likely it is that someone will need to scratch an itch and submit some code!

Codex/DLV

The core of the fourth codex suite is the Codex system. This is the new commercial name for OntoDLV [PDF]. This blog isn't an advertisement for my current employer, but it's worth mentioning the system all the same, as I find it interesting.

One of the features of Codex is to translate its ontology language into a program that can be run on DLV, a disjunctive logic reasoner. DLV offers an interesting set of features, including closed world reasoning, true negation along with negation as failure, non-monotonicity, and disjunctions in the head of a rule. Some of these are the opposite of OWL reasoning (closed world, negation as failure, non-monotonicity) while the disjunctive feature is completely orthogonal. Building an ontology language on top of this reasoner creates a very different kind of modeling environment to OWL. Interestingly, the guys in Italy have recently been looking at the consequences of importing OWL queries into the "rules" part of the OntoDLV language. This would make for an interesting complement of features.

OWL is built the way it is because of the interactions with the World Wide Web that it was designed to describe. An open world assumption is vital on the web, as things are being added all the time. Being monotonic may not work perfectly (as different sources may disagree) but is still important, as there is no way to assert priority of one source over another. The lack of a unique name assumption is also important, as it is very common that things are referred to by more than one name. In fact, it occurs to me that having a truly open world assumption means that you must not have a unique name assumption, particularly if there is an equality or equivalent operation in a language. Now that I think about it, this make it seem strange that many description logics have an open world assumption, but also presume the unique name assumption.

Contrary to the properties of the web, the corporate environment is often quite different. It may be because "the enterprise" environment is a consequence of decades of training to conform to existing systems, such as relational databases, or the type of modeling needed in this environment is inherently different. Whichever way it is, corporations model, collect, and think about data in a particular way, most of which doesn't work well with OWL. Records are often taken over, and over again, with the same structure each time (yes, corporations may have several nearly identical databases with different record structures, and OWL can help here. But bear with me). Entities have been allocated unique identifiers, and do not need to be "declared" to be distinct. Most importantly, if a company does not know about data, this almost invariably means that such data does not exist. (e.g. an employee record cannot exist until it has been entered by someone authorized to do so. Accountants don't want to know about possible future employees).

While listening to people at the conference I started to recognize that people want each of these different properties, depending on their environment. It seems that Codex has something to offer many people, especially with it's ability to import OWL data.

Reasoning

Another thought that I had while listening at the conference was that OWL reasoning is often done in a semi-closed way. Inferences are usually made in a way that accepts the possibility of unknown facts (open-world), but it can necessarily only reason on the data that it knows. This has a closed world flavor for me, though it is definitely kept consistent with the open world model.

There are lots of things that might be true that we don't consider when reasoning. No one ever declares that all individuals are in fact distinct (when it is known that they are). Classes are never declared to be disjoint, unless there is a specific reason for it (such as sharing a common superclass).

I'm not saying that people make inferences that presume unique names, nor that they do anything which would be invalid were two things revealed to be identical. The math behind valid inferences is too solid for that. But people see reasoning happen on the limited data they provide, and tend to think of that data as being their entire Universe of Discourse (I've wanted to use that phrase again for years). Consequently, people are repeatedly making closed world presumptions, and wonder why inferences and calculations don't come up with the answers they expected.

We also never see the "possible worlds" that a current model allows for. Given the infinite nature of the open world presumption, these possibilities might surprise people. In some cases, the model may prove to be completely inconsistent with reality, indicating that more modeling information is required for the system to be really useful. I know that people like Ian and Bijan know how all this works intimately, but most people are surprised when they see owl:cardinality apparently violated, so this sort of consideration is way beyond where most people are thinking.

I suppose I had this thought partly because almost no-one declares every owl:Thing as owl:differentFrom every other distinct owl:Thing. Similarly, classes are rarely declared as owl:disjointFrom unrelated classes. Sure Man and Woman may be declared disjoint, but I've yet to see Vehicle and BillingCenter get declared as disjoint from one another. This becomes more noticeable when you consider the differences between a closed world reasoner (like Codex) and an open world one. It's not that an open world ontology is any less expressive, it's just that you need more information to encode the same scenario. The funny thing is that people often have this information, but they don't put it in. Consequently, open world reasoners don't come up with as many inferences - not because they are less capable, but because they don't know as much about their system as a closed world reasoner does.

More AllegroGraph and Mulgara

This blog is all about helping me to remember stuff. The fact that anyone else is reading it is just a little too strange for me to remember most of the time. Please remember this when I go on and on about something I'm trying to write about, or when I'm a little too candid for my own good. It's more the former that concerns me in this post.

One important architectural item of AllegroGraph that I forgot to note was the description of their index writer. Richard mentioned that writing to the graph is fast, and that it plays "catch up" in the background while keeping the data live the whole time. If you perform a query during this period, then part of the query will be fast, and the "unindexed" data will come in more slowly. This is so close to the Mulgara XA2 design that I just had to mention it.

Aside from making XA2 faster to read the indexes, we really want to make them faster to write. Reading is actually fine, and I've yet to hear of any index-related problems in reading speed (there have been problems at various times, but they usually come from data type issues).

The fastest way to write triples is to simply write them down in the order they were given to you. You can't do a lot with this, but you can do this faster than any process can practically give them to you. This is the limit we can aim for.

Our original plan (based on skip lists) was going to accept writes in exactly this way. Indeed, this is exactly what you have to do with skip lists, as they are a write-once structure. This means that any new data has to be accumulated before it can be added to the index. Any subsequent query first uses the index (with efficient log(n) complexity) and then adds in the results of a linear search through the "writable" file. A background thread then merges this file in with the main index (into a separate file) and then brings the new file online. This is actually how Lucene does it.

Andrae has since left behind the idea of skip lists (they had a certain advantage in reading, due to forward-file access, but writing can be expensive) but the idea of building up an unordered list and flushing it in a set of background threads is still what we want to do. The result will be a fast write, like AllegroGraph has, but querying will get slower and slower as writes get further ahead of the indexing threads, again - just like AllegroGraph. The big difference is that we only have it planned, while they have it working. If only Mulgara had a dozen programmers still working on it. Oh well - if wishes were fishes...

Thinking of using a flat file with raw writes going into it reminds me of a related architectural piece.

One of the very first features we decided on for XA2 was an ability to have several concurrent writers. The phase trees and two-phase commit process we employ at the moment are perfect for maintaining ACID compliance, but they limit us to only a single writer at a time. If we wanted to go to multiple writers then we'd need some form of merging for multiple concurrent transactions. While it might be possible to merge branches of a phase tree, this approach is guaranteed to make ACID a total nightmare. Besides, it wouldn't really be a phase tree anymore if you try to merge branches (and nodes within those branches). The way to manage this is the way it's always done, and that is to keep transaction logs.

A transaction log is a list of two types of entry: insertions and deletions (or whiteouts). This information is basically what I was describing above. Just as I already stated, the current transaction needs to search this list along with the index whenever a query is resolved.

Fortunately, RDF is very kind to us when it comes to keeping a log. Statements either exist, or they don't. This means we only need to consider merging logs where opposite operations are recorded. e.g. If one transaction removes a statement, and a concurrent one removes and re-inserts that statement. In fact, an argument can even be made for not caring about merging these things, since almost any sequence of actions is valid.

Unfortunately RDFS/OWL isn't anywhere near as forgiving. These systems rely on multiple RDF statements for their structures. While the open world may make this perfectly legal (for most purposes), any practical application trying to talk to inconsistent data is going to choke. Merging transaction logs with these constraints will be more challenging, especially if a simple RDF interface is being used for insertion/deletion of statements. An RDFS or OWL (or even SKOS) interface could keep a track of the consistency of the structures, but trying to do this at the RDF level will require a lot of inferring of what the transaction is actually trying to accomplish. Indeed to allow the commit of OWL data, you'll need a full reasoner to check for consistency before allowing for a commit. The problem with doing something at the RDFS/OWL level is that we don't have an API at those levels. Hmmm, that reminds me that I need to get Sofa properly integrated again. That might even help us here.

But these are concerns for another time.

Back to the Conference

After the last talk on Monday we all went to the "Metaland" party. A presentation was going on, but it had been a long day for everyone, and there was free beer on offer. You can imagine how many people were paying attention. Maybe in future the beer can be handed out after the presentation, rather than before and during.

Amit and Rich from Topaz then went out to dinner and drinks with all of us from fourth codex. It was more fun that I thought any evening at a conference was going to be. If I embarrassed myself then no one has mentioned it... yet. Every phase of the evening seemed to involve a new type of drink.

While out, we had two people show up for fourth codex. The first was a new university graduate working for us in sales. This was her first day at work, and the commercial exhibits at the conference were on the next day. Talk about a trial by fire. The other guy was from the Exeura side of fourth codex, and had just flown in from Calabria, after 29 hours of traveling. He must have done something horrible in a previous life to have to go straight into a conference after a trip like that!

Reasoners

As promised, I checked the license for Pellet. It uses the MIT license, making it compatible with practically anything. Yay!

SemTech Day 1 (Still)

After David and Brian's talk I went to lunch, only to happen on Amit and Rich from Topaz. Topaz is an Open Source development group for the Public Library of Science (PLoS).

For anyone who doesn't know, it was Topaz along with the Software Freedom Law Center, who came to our defense when we encountered difficulties dealing with NGC last year. An explanation of this, along with the reason for the name change from Kowari to Mulgara can be heard in a recent podcast interview that David had with Paul Miller of Talis. Topaz has been developing with Mulgara, and used it in the deployment of the PLoS ONE system, which is why our logo made it onto their front page. More recently, they have started contributing to the project, and have even provided some direct funding. I like these guys. :-)

Lunch was spent discussing what Mulgara is doing, and where we hope to take it. Amit also asked about some of the internal operation of Mulgara, and the resulting description took me well into the next session. I hope I didn't miss anything important, but right now I can't even recall what I was hoping to attend, so with that justification I don't feel so bad. The discussions with Amit were worthwhile anyway, and it is my opinion that these impromptu meetings provide the real value of any conference.

AllegroGraph

I wrapped the discussion up in time to attend a talk I was very interested in, by Richard Newman of Franz Inc. It went by the unwieldy title of Working with SPARQL - Large Datasets, Fast Queries: What You Need to Know. This sounded fascinating, and I wasn't disappointed.

I'm embarrassed to say that I didn't know much about Franz Inc, nor the AllegroGraph RDF database. Such an obvious lapse is a clear indication that I need to get out on the web more. Still Richard's talk and subsequent Q&A went a long way to describing the system for me. In some cases he directly described internal details, while the explanation of feature implementations made it clear exactly what they had done in other instances.

It appears that AllegroGraph is architecturally similar to Mulgara in several ways, so I'm going to provide a bit of a comparison here.

Their approach to querying has had the advantage of being directly applied to SPARQL, which Mulgara is still working towards (hopefully soon), but since the basic structure of TQL and SPARQL is the same, then the parallels are easy to draw. There are some distinctions between the two projects, but most of the extras in AllegroGraph are already in the pipeline for Mulgara, such as storing 5-tuples, and a tableaux reasoner (they have Racer, while I'd like to bring in Pellet - which reminds me that I need to check Pellet's license).

Richard's explanation of simple unordered joins returning an immediate solution with no consumption of server memory revealed that AllegroGraph contains the full 6 indexes we use, and also does the same lazy join evaluation as Mulgara. However, when we move to 5-tuples we will only be putting a tuple ID into the first index (and not the remaining 5 indexes). We will also be introducing a new index based on this ID, so that a tuple can be found based on it's ID. Surprisingly, according to their introduction, AllegroGraph doesn't appear to have this index. Then again, maybe that's just a documentation issue. Incidentally, AllegraGraph seems to have a tuple ID for every entry, while our plan is to only include it for those statements which have been reified. This won't affect the storage requirements on the first index (the one being widened to 5), but will save space and time on the new index, which will only get entries when that statement gets reified.

AllegraGraph is using an ID-to-object mapping structure just like our "String Pool". I've commented in the past how this is an historical name, based on it originally storing only URIs and string literals, and that it should be renamed given that it now stores all the XML datatypes (and even user types). Franz must have gone through a similar process with AllegraGraph, given that their equivalent structure is called a "String Dictionary".

Getting back to the talk, Richard spent quite a bit of time talking about the ramifications of UNIQUE and ORDER BY. The UNIQUE keyword results in memory usage at the server end, though the result set is returned immediately. This is pretty obvious, given that the server need not do anything beyond store (and index!) those lines already encountered so they are not duplicated.

More difficult is implementing ORDER BY. Richard referred to server memory, but I suspect he was including secondary memory in that description. In our own case, we use a class called HybridTuples. This is a class that I started, but Andrae was the one to really implement. Now that I think about it, he probably didn't even look at my code. I think this class may have been one of the first things he did for Mulgara. The class uses memory up to a point, but then uses a file. It would be nice to memory map it when it can fit, but on a 32 bit system that is just too difficult to test for in Java, and it could cause other connections to fail with an Out Of Memory error (OOM). So on 32 bit systems HybridTuples uses standard explicit IO for managing the file, while on 64 bit systems it uses memory mapping (yes, even if the file is over 2GB in size).

All up, the talk did not provide me with many useful tips for SPARQL, though that may have been due to my experience with Mulgara. However, I found the description of AllegraGraph, its features and internal details to be invaluable.

After the talk Amit offered to introduce me to Jans Aasman, who is the director of engineering at Franz. When he heard that I was involved with Mulgara he made a comment I was to hear several times during the week, "It was a real shame. You guys were way ahead of the curve 2 years ago!" This comment was a great endorsement of our work, and yet very frustrating that a great opportunity was lost. All the same, Mulgara is starting to move along nicely again, so we should still have something worthwhile to offer.

I also commented to Jans about the internal structure of AllegraGraph, and he admitted that there isn't much you can do to hide the implementation of these things. I suppose much of what we do is straight forward. It's just a matter of competent people integrating the right components and techniques. On those few occasions where you DO come up with something new (like when we started indexing 3 ways on triples, and 6 ways on quads) then it doesn't take long before everyone does it. While I may form an emotional attachment to my own ideas (see the section marked "Indexing" for the reference here), I still love to see everyone helping everyone else improve the current state of the art (and hence, I hate patents - especially on software).

I'm not sure what others got out of it, but overall, I liked Richard's talk, though probably not for the insights into SPARQL, but rather the exposé of the engineering behind AllegraGraph.

Argh

After writing all morning, someone from Italy wanted me to check my email in the office using Zimbra. Of course, this made Firefox crash (again). Fortunately, Blogger autosaves your posts, so I lost nothing. However, after starting Firefox I discovered that editing was very slow. The "top" program revealed that Firefox was using 30% of the CPU, so I decided to restart it. Again, I made sure the blog was saved (I manually pressed "SAVE NOW").

After firing up the program I first confirmed that the CPU wasn't being used heavily, then went back to the blog. Only this time the draft is empty! It's there, but there's nothing in it. Given how much time I put into it (and the links I chased down) I'm kind of miffed. Software has come some way in recent years, and I haven't experienced this kind of data loss for some time. It feels like the 1990's all over again.

Thinking that Blogger would want to know about the potential for data loss, I went looking for a place to report the problem. However, like several other sites I've found recently, making a bug report (or a warranty claim) is not a trivial task. Fortunately, I found it at last, only to discover that when you click the "Report a Bug or Problem" button, and then choose the sub-item of "I found a bug with Blogger" results in a page saying, "Invalid problem". Selecting the more general option of just "Report a Bug or Problem" takes you to a Help page.

So how do I report a bug in the bug reporting system?

SemTech Day 1

After registering, I looked around for where I needed to be, and for any familiar faces. Right off the bat I saw Bernadette talking with Eric Miller. I've been looking forward to seeing Bern again, and DavidW has been telling me for some time that he wanted to introduce me to Eric, so this was a pleasant coincidence. Eric is as sharp as I was led to believe, but far more personal and amusing than I expected. He's a really nice guy, and I can see why he's been so influential in the semantic web community.

The first talk I attended was by Brian and David, titled, Putting the Web Back into the Semantic Web. I already had some notion of what this was about, and I knew that they leverage NetKernel quite heavily.

Brian had shown me last year how NetKernel provides a RESTful interface and allows data and processing operations to be described in URLs. This basically allows efficient remote access to a arbitrary functions, with nestable function calls. It seemed cute when I first saw it, but did see that I needed it, despite the papers on efficiency that Brian had sent me. I certainly didn't understand his desire to use it as a framework inside Mulgara. But he knows what he's doing, so I've been prepared to give him the benefit of any doubt.

I won't go into the details of the talk, but I was very impressed at the ease in which they were able to access and process data using NetKernel. More impressive were the reports of what a NetKernel infrastructure could provide. Efficient transport over HTTP is a given, but near-linear scalability with threads and clustering really caught my attention. I guess it makes sense, since Google get analogous scalability with their stateless Map-Reduce libraries. I could hear similar murmurs of appreciation from the audience.

David went on to describe GRDDL, showing GRDDL markup on his own home page. I've been curious about microformats for some time, but too busy to look into them, so this was a nice, practical introduction. Introduce a NetKernel module for doing GRDDL parsing into RDF, and now you can specify URLs which refer to the RDF from a web page. They've also written another module which takes RDF data and inserts it into a Mulgara database. Using these together, a single call to NetKernel will perform an extraction of RDF from a web page, and insert it into a local RDF store. A little presentation layer work backed by the Mulgara store means that you can now browse through all the extracted RDF. This gets particularly interesting if the RDF contains linkages across the store.

I was impressed by this talk, and have since heard several others say the same thing. But it was a later conversation with Eric that made me really rethink the idea.

RDF can be used in several ways. The most trivial is simply for storing any kind of information. It works particularly well for information with a network topology, but it can be applied to anything really, even binary file formats like MP3 or PNG. I'm not saying that this is necessary a good idea (for a binary format it's a terrible idea), but it is certainly possible.

Another approach to using RDF is for modeling. This uses RDFS, and possibly OWL or SKOS. Almost every application which uses RDF is doing exactly this. Unfortunately, while RDF is a great structure for this type of data, it is a terrible API for developers to work with. This explains the need for projects like ActiveRDF, and Alexandria's upcoming modeling API (which works well, but needs more features).

Yet another approach is simply for linking resources. When I first heard about RDF in 2001, one of my first thoughts for using it was to describe links between arbitrary resources. Since those resources are described with URIs, my natural thought was to link URLs together, thereby creating a "Web" of physical resources. This is already achieved in the World Wide Web by the "anchor" linkages described inside HTML pages, but these links can only be created and modified by a page's author. As an author of a page, I will often link to other pages, but I am unable to link those pages back to mine. There are also occasions when there is value in linking arbitrary third party pages, such as when one page provides specifics for concepts described in another page, or when describing a workflow.

Of course, all 3 of these approaches can be used at once, to varying degrees. RDF is great that way. However, developers usually use RDF to meet a specific need, meaning that the variety of ways that RDF can be used is often overlooked. I think the last approach of linking arbitrary resources is underutilized, though I've seen it used here and there. Some people even complain that you shouldn't use RDF to link pages together, as any application using this data is expecting the resources in question to be URLs which refer to resources with a physical presence on the net. The RDF specification specifically uses URIs to indicate that the resources need not have a physical presence, and many people get upset when you create an application that presumes that a URI is a dereferencable URL. But insisting that those resources cannot have a physical presence is stating that RDF isn't allowed to describe certain types of resources, hence, I disagree. But I digress...

Since NetKernel allows you to reference any operation on any kind of data via a single URL, then using RDF it is possible to link any kind of resource to any data you can dream of. Not just static data as we do now, but real-time, arbitrarily complex, calculated data. Not only that, but it's trivial to do.

This got my head spinning. It opens up a lot of possibilities.

Continued

I put this post down while traveling back to Chicago, so it makes sense to break it here and continue later. There's lots to talk about, and it got me thinking about a lot of things that I want to write down while it's still fresh, so I can clarify my perspective.

San Jose

Sunday saw me brave the torrential rain in order to hail a cab for Midway. These cab trips are expensive, so fingers crossed that the reimbursement comes sooner rather than later.

I met Chris at the airport, and then we were off for San Jose, and my first visit to California outside of an airport. We arrived late, checked in, and went to bed.

Being in a later timezone, and having no children with me, I had no problems waking up early the next day. Looking out from the 14th floor was really impressive. While in the middle of a very urban setting, you don't have to go far to see that we're surrounded by dry hills. It's an attractive contrast.

The immediate local is quintessentially California/Bay area. The bright skies of lower latitudes (I miss that) palm trees (I think I miss them too), and a dense network of trams (cool). The only detractors were that I would be too busy to get out to experience it up close, and the brown tint to the sky down towards the horizon. I've heard that Chicago has very clear air because of the lake. I suppose that it right, as this is a region with fewer people yet the air seemed dirtier than I can ever recall seeing in Chicago (and certainly Brisbane). On the other hand, I don't get up to the height of the 14th floor very often when I'm at home, so maybe that's just a perception thing. If this is the Bay, then I shudder to think Los Angeles would be like.

The room is nice, but I was a little surprised at the water situation. Every hotel I've visited in Australia or the USA for the last couple of years has had a notice saying that they would let you reuse your towels if you hang them up, thereby saving water. California is just on the cusp of a major water problem as the winter snowpack diminishes, and yet there was no such notice about water savings.

I thought that the hotel may be trying to pick up its savings with the reduced (nearly non-existent?) flow of hot water in the bathroom sink. However the cold water and the shower changed my mind. I was pleased to discover that the shower was easily set to a comfortable temperature, but dismayed to learn that the flow control's only settings were "off", and "Help! I can't swim!"

I wanted an early start, so I decided to forgo exercise and go straight down to the conference. I spent money on an exorbitantly priced meal, before discovering that the conference was providing this for free in a separate area. Sigh. At least I knew about it every subsequent day. I'm currently typing this in an antisocial fashion while sitting at breakfast on the final day.

So now I can talk about what I actually did while here...

Disjunctive Logic

Wow. Has it been that long since I last blogged? No wonder people think I've dropped of the face of the earth...

Life has been crazy in the last week. On Friday I spent the whole day with Nicola from UniCal discussing architecture and products, especially OntoDLV. He's a very knowledgeable guy, and it didn't take long for him to set me straight. I also learned a lot about the internal architectural decisions (I knew how it was built, but didn't necessarily know why it was built that way). I also discovered that the apparently non-monotonic behavior which I'd discovered was due to the fact that DLV is non-monotonic by design. Doh!

We didn't leave the office until about 9:30pm, as we wanted to avoid going to work on Saturday morning. That left the guys from Italy with a day to look around Chicago, while I got a day and a half with my family before going to San Jose for the SemTech conference.

Multiple Blanks

It turned out that re-mapping the blanks was quite easy. It required the use of a new getColumnValue method in the AnswerResolution class. This just tests to see if the node being returned from the remote server is blank, and if it is, then to create a different type of blank node instead. This is a new blank node called a ForeignBlankNode. While pretty much identical to existing blank nodes, it takes the server URI that it was returned from as a construction parameter, and it re-implements equals(Object), hashCode() and toString(). These differences allow it to be seen as distinct from another blank node with the same internal ID. Also, the localization process recognizes the node as new (and no longer a conventional blank node) and allocates something new in the temporary string pool.

This worked perfectly, but that interaction with the temporary string pool made me remember bug MGR-43, as it was making use of unknown elements going into a string pool. So I thought I'd have a look at what is involved in a SELECT/INSERT command.

To save myself time, I just attempted an insert from a selection coming from a different server:

insert
  select $s $p $o
  from <rmi://localhost/server1#foo>
  where $s $p $o
into <rmi://localhost/server2#bar>;

Immediately I got a response from the distributed resolver factory telling me that it doesn't support write operations. So that told me that the query went to the server with the model to be read, and not the model to be written to.

To support write operations on a distributed resolver I have to implement the modifyModel(...) method. This takes a Statements object, which is cursor where each location has a subject, predicate, and object. The remote session is happy to accept a Statements object, but this is inappropriate here. If the object were simply sent as it is, then every Cursor.next() call would be done in RMI, along with every call to getSubject(), getPredicate() and getObject(). This would be horrible, even for a tiny set of statements.

There are two ways I could manage this situation.

The first is to not make the distributed resolver writable, and instead send the original INSERT/SELECT to the server containing the INTO model (the model being written to). This server would then use the read-only distributed resolver to do all the querying, and the resulting Statements would be local. This would work, but it would mean doing resolutions for every constraint across the network, even if the entire SELECT part of the query were from the same server. The entire query could be offloaded to the other server for the optimized query resolver, but that is not written yet, and we'll be keeping it commercial for a while anyway. I want/need something that will work for everyone.

The second approach is to make the the distributed resolver writable, while making it possible to send Statements across the network easily. For small statement sets we'd want a simple array of statements, and for large sets we'd want something that paged the statements, thereby minimizing the calls over the network, but still allowing large amounts to data to be moved.

This is exactly the solution I implemented for Answers a few years ago. In fact, I recently revisited the Answer code due to an unexpected interaction with transactions, so I feel familiar with it. While I'm reluctant to extend our usage of RMI even further, it's not going away any time soon, and this seems to be a good place for it.

I had to put the implementation aside a couple of weeks ago, as it was getting late. It's been difficult to get back to it, as I've needed to do some documentation at work. When I tried to set up my notebook computer (which I use in the office) to work with the latest checkout from Subversion, the poor little G4 PowerBook took so long to get anything done in Eclipse that I basically wasted the day. Since then I've had to look at other areas of the project (hmmm, this is starting to sound like my RLog project) and it's only today that I'm getting back to it.

Distributed Resolver

TQL has always allowed multiple models to be mentioned in a query, either in an expression in the from clause, or on individual constraints, via an in clause. This lets you perform selections on expressions describing unions and intersections of models, with arbitrary complexity. However, all the models described must be on the same server.

After 2 years of procrastinating, I finally implemented a resolver for distributing queries. This means that models on other servers (on the same machine, or across the network) can also be accessed. It's not an optimal approach, but it works quite well.

I actually did something similar 2 and a half years ago, but this was for TKS and not Kowari. This means it could never be released as open source code, and I lost access to it once Tucana was sold. It was not particularly difficult to implement in the first place, so I knew I could do it again, but I really didn't want to. I kept putting it off, as it was demoralizing to have to do something from scratch that I'd already done before, even if I did forget the specifics. At least this time I think I did a better job (2.5 years of extra experience will do that for you). I also have the feeling that I may have implemented more Resolver methods than I needed to back then.

One thing that is missing is blank node resolution. At the moment, blank nodes from 2 separate servers may give the same temporary identifiers. This is a bug. The solution I want is to have blank nodes from another server to use extended string representations which include the server IP address, rather than the simple _:## format currently in use. This will require a blank node factory that returns the required type of blank node as needed. The factory will need to be given to the Answer as it is created, so that it can return the correct type of blank nodes as they arrive. I'll have to check more carefully, but I think this can happen in AnswerWrapperRemoteAnswer.

For the moment, the approach is naïve, and does not take into account how much data may try to move across the network. A more scalable approach will get done eventually, but this may be part of a commercial offering from my employer Fourth Codex. I'm expecting to have to add some of the required infrastructure to Mulgara, but keep the "secret sauce" in an optional external module. Of course, this will depend on my time and resources at work.

Optional

One SPARQL feature that we need to implement is the OPTIONAL keyword. It seemed relatively easy to implement, and would work similarly to existing constraint operations.

While a constraint disjunction expands both sides out to contain the union of variables, it does nothing to join the results on both sides. This can leave any created variables unbound. A constraint conjunction does this join, but limits the results to those which have bound values. The optional operation needs to do both. In a sense, it reminds me of when I had to introduce the minus operation to provide a new kind of join operation that was previously impossible.

I'll probably try to introduce this operation shortly, but it won't be of much use until we can use it in a query language. Since SPARQL is still some way off (Inderbir is looking at the grammar parser for me right now) then I should probably introduce it as a language feature in TQL. I guess it would appear like an AND operator, right?

SPARQL

When I needed a break from the DL Handbook, I read the SPARQL Query Language for RDF. I've browsed this enough to have an idea of how to write SPARQL, but I'd never gone through the entire document in detail before now. It's unfortunate that I didn't have a pen with me, as I found a few small errors, mostly where the text disagreed with sample data (probably due to inconsistent revisions of the document).

I found it interesting to see elements which look a lot like TQL in there. Admittedly, I don't know which elements of TQL we borrowed from other languages (Simon would be the best oen to describe that), but I'm pretty sure that some of what we included was original. FROM NAMED, and GRAPH look like TQL FROM and IN clauses. OFFSET and LIMIT also look to have come straight out of TQL. There are many other similarities, but I know that these look a lot like RDQL as well, so they could have come from anywhere. I should ask Simon and Tom just how much influence they had.

Filters

From a performance perspective I've never been too happy about filters. Simple filtering in Mulgara is done more effectively using appropriate resolvers. However, I was never too clear on exactly how expressive filters could be. Consequently, I always wondered if we could perform filtering using Mulgara resolvers. The short answer is that we shouldn't (in my opinion). I know that others (such as Andrae) have also looked at this, and probably have a better idea than I have, but I'll put forward my ideas anyway.

Unfortunately, SPARQL defines filters as "constraints" (which they are), and a pattern to be matched as a TriplesBlock. This is at odds with Mulgara terminology, which defines both concepts as "constraints". This is because the pattern in a TriplesBlock is also a constraint on the data to be returned. I want to refer to the internal structure of Mulgara queries, so I'll say TriplesBlock when I'm talking about the SPARQL construct, Constraint when talking about the Mulgara internal construct, and Filter when talking about SPARQL filters (which are SPARQL constraints).

A filter could be passed into a Mulgara query as a constraint, which is to be resolved against the current group. This has several advantages. The first is that it can be used to great efficiency for some functions (such as when the function returns a set, which is the case for type tests like isBlank and isLiteral). They also work within the current query resolution system.

The first problem I have with this approach is that it requires a mapping of semantics from filtering the output to an inner join against some theoretic set of tuples returned by a resolver. I'm confident that this semantic works, but fiddling with semantics does seem inappropriate. All the same, it is an idea worth thinking through.

Constraints of this type would get mapped to a resolver that knows how to handle filter functions. The main problem is that resolver constraints usually get passed in using some kind of triple pattern, which tends to limit the width of the data. This might work for a simple filter:
 e.g. "?x < 5" could map to "?x mulgara:lessThan '5'^^xsd:integer"
But it starts to fail for complex expressions like:
 ?x > 5 && ?x < 10 & regex(str(?y), "foo$")

I also considered the idea of packaging the entire filter into a string that gets passed to the resolver as a literal. Filter parsing is pretty much a separate stage in SPARQL already, so I don't think it is an issue to put it off into a resolver. The main problem with this is that there is no real mechanism to pass more than a couple of bound variables into a resolver, whereas a filter could refer to an arbitrary number of variables. In theory, the resolver could instead ignore already bound variables, and instead return a set of data to be joined against with a constraint conjunction, but for some functions these sets need to infinite!

It might be possible to break down a filter expression into a constraint expression (constraint conjunctions and disjunctions), but it is still possible to construct difficult filter expressions that don't break down so easily. For instance:
 regex(?z, str(?x + ?y))
This is also ignoring external functions, which might take more than two parameters. The example of geographic distance, shown in section 11.6 demonstrates the importance of supporting such extensions.

There are other reasons to avoid using a resolver, but the restriction on bound variables is a real show stopper.

Filtered Constraints

After deciding not to use the usual constraint conjunction method for filtering, how should solutions be filtered? SPARQL defines filters to operate on a group of patterns. For groups with more than one constraint, this corresponds to a constraint conjunction in TQL. For groups of just one constraint, this is just a simple constraint. For groups containing a GroupPatternNotTriples, this becomes either constraint disjunction, or one of several other constraint operations (I'll get to these later). In effect, every constraint expression we have could find itself as a "group" which requires filtering. So the ConstraintExpr interface will need to include a filter property.

When it comes time to resolve a constraint expression with a filter attached, we can wrap the resolution in a FilteredResolution object, based on the filter expression. Of course, construction of such an object should build some sort of functor which will perform the required operation. In essence, this means that we compile the expression (an obvious thing to do), rather than interpret it on ever iteration <shudder>.

The biggest problem with filtering like this, is that there is no way to count your results without iterating over the entire set. This is highly undesirable, as it blows away many of the time/space efficiencies we have with lazy evaluation. Fortunately, the definition of Tuples.getRowCount() has always been for an upper bound on the size of the tuples. I believe this was so lazy evaluation could guess at the size of a conjunction, though I seem to recall that the concept of filtering was kept in mind for this decision as well.

Sleep

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

Description Logic

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

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

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

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

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

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

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

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

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

Logic and Sleep

After revealing my confusion last night, I went to bed thinking I'd just exposed myself as an idiot. Nothing like that to motivate you to solve a problem for yourself! So after sleeping on it, I finally worked it out for myself.

I sort of understood role restrictions. While it's true that (∀(R|_C).A) returns the same set as (∀(R).(A⊓C)), the semantics of value and role restrictions are different. Value restriction means that every usage of a role must refer to a category, while role restriction is a selection of those usages which refer to that category.

However, I was wrong that it was the inability to see this difference that led me to false conclusions about those properties. My main problem was failing to take proper account of the universal qualifier used in the value restriction (and forgetting that this does NOT imply existence).

I finally "got it" when I thought about some example roles. Consider a town where there are a number of people named Smith and Jones (among other names). I could ask the question, "Who in town knows only the men in the Smith and Jones families?" Note that these people may also know males and females in other families, as this is not a restriction imposed by the question.

I could encode the question according to the original proposition with:
R ≡ knows
C ≡ Smith
D ≡ Jones
A ≡ Male

So then when I say (∀(R|_C).A) this is now equivalent to (∀(knows|_Smith).Male). Once I got that, I realized it was easier to think of a restricted role as a new role altogether (a sub-Property in RDFS parlance). So the new role might be called knows-a-Smith, and the expression (∀knows-a-Smith.Male) means the selection of people who only know Smiths that are male. Since I'm describing this in natural language, I should point out that the expression does not say that these people actually know anybody named Smith, only that if they do, then that Smith must be a male.

So my question of equivalence goes from:

(∀(R|_C).A) ⊓ (∀(R|_D).A)     ≡    ∀(R|_{(C ⊔ D)}).A

To the expression:

(∀(knows|_Smith).Male) ⊓ (∀(knows|_Jones).Male)     ≡    ∀(knows|_{(Smith ⊔ Jones)}).Male

Or even simpler:

(∀(knows-a-Smith).Male) ⊓ (∀(knows-a-Jones).Male)     ≡    ∀(knows-a-Smith-or-Jones).Male

This means that the set of people who know only male Smiths, and also know only male Joneses is the same as the set of people who know "Smiths or Joneses" who are only male. (These things can get hard to parse in English, so it's a good thing we have a syntax that is more exact - even if it is hard to read).

It's easy to see that the intersection of Smith-knowing-people and Jones-knowing-people fall into the union expression of people-who-know-Smiths-or-Joneses. But my problem was that union includes people who only know Smiths (and not Joneses), and people who only know Joneses (and not Smiths), and I couldn't see how these people could be in the intersection expression.

An easy way to find a flaw in the proposition was to think of a counter example. ie. Who could satisfy the union, but not the intersection? There's symmetry when considering Smith or Jones, so I only have to look at one of the names. The relevant interpretations include:

1. People who know male Smiths and also know Male Joneses
2. People who only know male Smiths
3. People who only know make Joneses
4. People who don't know anyone named Jones or Smith

People who know female Smiths or Joneses are not in the intersection of (∀(knows-a-Smith).Male) ⊓ (∀(knows-a-Jones).Male). They are also not in the value union of (∀(knows-a-Smith-or-Jones).Male), since the role restriction (ie. referring to a male) is not met if they know a female with those names.

When thinking of the "union" it is easy to see that all three of the listed groups here are relevant. But for the intersection it wasn't instantly apparent for me that everyone was included:
(∀(knows|_Smith).Male) ⊓ (∀(knows|_Jones).Male)

For this to not be in conflict, we need all the relevant sets present on both sides of this intersection operator.

This is where I was getting caught up with the universal qualifier. Anyone in group 1 (knows both Smiths and Joneses) is on both sides of this intersection. Anyone in group 2 (knows Smiths, but not Jones) is on the left hand side of this intersection... but how are they on the right? The point here is that anyone without use of the role (knows|_Smith) satisfies the condition of (∀(knows|_Smith).Male), since there is a universal qualifier here, and NOT an existential qualifier. The (knows|_Smith) is an empty set for these people (which threw me off), but an empty set doesn't violate the condition because of the use of the universal qualifier.

Doh!

This same reasoning applies for groups 3 and 4, so I find there are no conflicts.

Description Logic

I've been having some issues with description logic recently. I can't tell the difference between value restriction (∀R.C) and role restriction (R|_C). These have the semantics of:

 ∀R.C      {x ∈ ∆^I | ∀y.(x,y) ∈ R^I → y ∈ C^I}
R|_C      {(x,y) ∈ ∆^I × ∆^I | (x,y) ∈ R^I ∧ y ∈ C^I}

Value restriction (∀R.C) uses an "implies" operator (→) to say that any use of the role will refer to an instance of the class C. Implication means that there can be values for y which are not part of the role description, and are still instances of C. However, since we also have a universal qualifier for y when used in the role, then we have no need to consider elements of C which are not used in the role.

Role restriction says that for any use of the role, then the value in that role (y here) will also be an element of C.

Given that value restriction has the universal quantifier on y, I don't see the difference between the implication here, and the conjunction used in role restriction.

So to me, value restriction defines a class where all uses of a role refer to elements of a specified class (C), and role restriction refers to a role that can only refer to elements of a class. They means slightly different things, but then I don't understand how (∀(R|_C).A) is any different to (∀(R).(A⊓C))

Maybe I'm reading it wrong.

Anyway, I think it's because I don't understanding this difference that I can't get the following property:

(∀(R|_C).A) ⊓ (∀(R|_D).A)     ≡    ∀(R|_{(C ⊔ D)}).A

My reading of it says that the right hand side should include an intersection of (C ⊓ D) and not the union (C ⊔ D).

I know I'm wrong here, but I just don't see it. Unfortunately, I don't know where to ask either. Can anyone help?

Distributed Queries

A few weeks ago I was having a chat with the people from Fedora about the things they'd like/need in Mulgara. One of the features that came up was distributed queries. I recall that it was pretty simple when I did this (the naïve way) a few years ago. So I thought I'd have another go at it.

I've had a lot of things to get done lately, but as of this afternoon I have it running again (yay). Unfortunately I haven't had time to set up tests which start 2 servers and query them together, but my manual tests are all working fine. I'm able to describe models from multiple servers in the FROM clause of my queries, and also in the IN clauses.

My first priority is to get the tests written. Then in the longer term I need to get an intelligent algorithm going to properly distribute the query around the network. I know what needs doing, but it requires some help in the query optimizer, and can't be done entirely in the resolver. So I'll be waiting until I'm given some significant time for this feature before I get stuck into it.

In the meantime, I don't actually have any use cases which need optimized network activity for distributed query resolution, so I'm pretty happy that I have the feature going.

SOAP on Jetty

A common way for non-Java users to access Mulgara is through the iTQL client jar, using SOAP. This is very bad, as the iTQL jar uses RMI to talk to the server. This is OK if you're in a JVM and accessing the objects directly, since we put a bit of effort into making objects stream intelligently, but if you're going to chunk up the streamed results into XML, then you'll be introducing a whole series of problems. Not to mention that you now move all the data over sockets twice.

Unfortunately, there hasn't been an alternative to this approach before. There are some options with the descriptors interface, but this is designed for providing results for specific queries. Besides that, I hear it's broken at the moment. Trying to run it seemed to bear this out, but at least the SOAP endpoint is there. I believe Brian is looking into this bug at the moment.

The main problem with putting SOAP (or any other kind of access point, such as the RESTful options being considered) on the server is that the iTQL interpreter is supposed to be on the client. If ItqlInterpreter is naively accessed on the server, then some of its internal session data will not be set up correctly.

Fortunately, the main reason the ItqlInterpreter has internal session data is so that it knows which server to send the query to. If I want a non-RMI service on a Mulgara server, then it won't need to work out which server to go to, since it's already there!

However, this isn't a drop in replacement for the RMI service, as I need to find the appropriate references to Sessions and the like. A cursory inspection suggestions I will only need to change a couple of lines, but I want to be sure I get them right, so I'm going through the code line-by-line to make sure I have a correct understanding of all that is going on. It's a little strange, as I know I wrote some of it. There's a sense of familiarity there, and I even remember some things, but in many ways it also looks like completely new code. I'm probably taking longer than I need to in some of these classes, but I'm using the opportunity to get completely familiar with this code again.

One area I need to spend some time in is the Jetty configuration. It looks relatively straightforward, but I wanted to read the documentation for what certain method calls are doing... and that was when I discovered a problem.

The Jetty we are using is version 4.2.19. It turns out that this is ancient. Jetty is now up to version 6.1. This has a few implications.

• No online Javadoc.
• Difficult to track down the cvs revision for sourcecode.
• Not Java 1.5 compiler-compatible (uses enum as a label).
• Only supports Servlets 2.3, not 2.5.
• Only supports JSP 1.2, not 2.1.
• No longer maintained.

I'm sure there's a lot more, but you get the idea.

My initial reaction is to update to the latest Jetty. Unfortunately, I note that a lot of the interfaces have changed, and this will need learning how Jetty needs to be configured. I should also learn how it WAS put together, so I can work out what I'm updating.

The thing that led me here was trying to find out what an HttpContext is exactly, since a group of these gets set in the Jetty server in Mulgara. However, they don't exist anymore, and neither does the the more generic Context class. So I'll have to work out what these things were in order to make sure I can configure the same functionality in Jetty 6.1.

Fortunately, The download site has old versions, including 4.2.27. This should only involve bug fixes from 4.2.19, so the documentation will stay the same.

Frankly, I hate these distractions. The whole way down these side roads you question the value of the effort of learning a new part of the system just so you can replace something that is currently working. There's no denying the value and enjoyment of learning something new, but it really takes the focus off important things.

Zarro Boogs Found

At the start of this week I tried to integrate several patches submitted to Jira. Unfortunately, there were two impediments to this.

The first problem was simply because XML output has now been configured to provide datatypes and language types to any literal that defines them. This makes a lot of sense to me, and I was happy to integrate it. Unfortunately all the scripted tests are looking for exact textual matches on the output, so many of them are suddenly failing. This is trivial but time consuming to fix. As I write this, I'm running tests over my latest attempt to squash all these bugs. I hope I finally got them all.

The other problem seemed to be easier, but was far more insidious.

I was getting an iTQL error that I didn't understand. The stack trace in the log did not take me far enough, so I added in some more logging. The next time through the tests, the section I was analyzing passed, but something else failed.

This went on for a whole night. Every time I thought I was getting closer, the failing code would move. This generally indicates threaded code with a race, but I couldn't imagine where. I finally tracked one instance of the bug down to a transaction exception, which was the point where I decided I needed to talk to Andrae.

String Pool

In the meantime, Andrae had decided to take on the hard task of the fixing a problem that had been reported with the string pool. I had so much on my plate that I wanted to avoid it, though I knew it was a significant issue, and would compromise confidence in the project.

Since I needed Andrae's help I offered some description on the structure of the string pool. However, I quickly realized how lazy I was being, so I decided to look for myself.

Andrae had managed to narrow down the problem to a very specific behavior. This made it much easier for me to think through exactly what was happening, and how the system had to get there.

The problem was due to an entry in the AVLTree, with no corresponding entry in the IntFile. To understand this, I need to explain some of the basics of the string pool.

String Pool

The string pool gets its name from the fact that it used to store strings in it. The strings were either URIs or string literals for RDF. However, it didn't take long before we needed to store other data types as well, starting with doubles, and eventually moving on to the entire set of XSD datatypes. By this point, we had a lot of code using the name "String Pool", and we were all used to referring to it by that name, so we kept calling it that, despite the fact that it holds much more than strings.

The purpose of the string pool is to map these data objects to a unique number representing a node in the RDF graph, which we call a graph node, or gNode. We also need to map from a gNode back to the data, so we know what that node is supposed to be representing.

The string pool is based on two main structures, with each structure providing one of the two mappings we need.

The first is an AVLTree, which is used to sort all entries (of all data types). This is used to look up data (strings, URIs, numbers, dates, etc) to map it back to a gNode (a "long"). It is also used to find ranges of data, such as all URIs beginning with the rdf domain, or all dates in a range. This tree is phased, in that it contains multiple root nodes, with each root corresponding to a phase. Only tree nodes uniquely belonging to the latest phase can be written to. Older phases are for reading data only, and each phase is associated with Answers obtained when that phase was the most recent. (This is why Answers must be closed - we can't mark nodes from an old phase as free until the Answer no longer needs them).

The other structure is called an IntFile. This is an array integers, which we use to hold an array of string pool entries. These entries each contain exactly the same information as the nodes in the AVLTree (laid out in the same way). The entries are indexed in the array by gNode value. Each entry is 72 bytes, so a gNode ID of 100 would correspond to data starting at byte 7200.

Importantly, this array is not phased. Once a gNode gets allocated in a phase, it represents the same data in all phases. The gNode can only be reused after the data has been deleted, AND all phases that have ever referred to that gNode have been closed.

So we have a tree which maps from data to gNode (the "localization" operation), and the array which maps from gNode to data (the "globalization" operation).

Out of Synch

Back to the problem: we have an entry in the tree that is not in the array. Now the methods that put data in the string pool put that information into both structures at the same time. The structure of this information is identical for both structures (the array doesn't have to store the gNode, since the location of the entry gives this). For a gNode to come up as a "blank node" means that the entry in the array is full of zeros, meaning it hasn't been written to.

The problem is trying to work out how the same data can be written into two files, and only show up in one of them.

Data written in a phase tree is really irrelevant until it is committed. Committing means writing the location of the new root to a separate file (called the metaroot file). So if we see data in the tree, then the tree MUST have been correctly committed to disk. The operation of committing means "forcing" all data to disk in a consistent way. We do this by forcing the tree to disk (if this fails partway through, then the old tree data is still valid), and only once this is finished can we save this new root to the metaroot file (making this new root valid in future). If you look at the prepare() method, then you'll see this data being forced to disk, and only then is the metaroot file updated and forced to disk.

So how can this AVL tree get ahead of the array in the IntFile? This could only happen if the IntFile were not forced to disk when the tree was forced to disk. This would mean that while the data was "written" to the array, it would not have arrived on the disk yet, even though it was committed to the tree. This would be bad, as nothing should be "committed" until it is completely consistent on disk.

So the solution was to find if there was any code path where the tree were forced to disk and the array were not. Looking in the string pool, it turns out that the tree is only forced to disk in one place, and the array is never forced to disk! So this must be the source of the problem.

Write behind at the OS level is generally a safe operation, even when a process is killed. However, it is possible to call write() and have things die before the data makes it to disk. (The libc libraries can do write-behind, the OS could die in some way, power gets pulled, etc). So the lack of synchronization is unlikely, but possible. This is why we've never seen it before now.

The solution is simply to ensure that the IntFile is completely written, before any data relying on that file is consistent enough to be committed. This means we just need the single line before updating the metaroot file:

 gNodeToDataFile.force();

Tests

I believe the bug could be reproduced by inserting a large number of unique literals into the store (sufficient to overflow the caches and force the JVM to buffer IO); followed by a commit(); and then kill -9'ing Mulgara immediately the commit returns.

Andrae's suggestion here is an attempt to fill the write-behind buffers, committing the data in an inconsistent state (since there is necessary data in the write-behind buffer), and then killing the write operation before these buffers can reach the disk.

Since we're trying to prevent the IO operations from operating correctly at the libc/OS level, it's not a problem that is suitable for running in JUnit!

So we're confident we've found the problem, but consistently reproducing it is not
trivial. This makes it similarly difficult to properly test that it's fixed.

I'm the one who understood the string pool structure enough to look for this and find it, but I wouldn't have even been looking in the right place had Andrae not taken me there. This story got played out in a similar way again the following day.

Transaction Exceptions

The String Pool bug was a vital one to find and fix, but it was extremely rare, and really hadn't affected us before this first bug report. It is a testament to how rare the bug is that this was our first report of it in the nearly 6 years that it has existed! However, I still had my transaction bug to find, and I was getting this one all the time.

I had managed to create a test case that was guaranteed to fail for me. My code performed a simple query (a duplicate of one that usually failed in our tests), and then iterated through the Answer, printing the results. However, before iterating, I did exactly what ItqlInterpreterBean does, and checked isUnconstrained() first (in which case the return value should be true).

This almost always failed, but I soon discovered that if I did the query (successfully) in the iTQL shell, then it would sometimes let my test code run correctly. My first approach was to see the difference between my code and the iTQL shell, and I finally realized that the shell would always call beforeFirst() on an Answer before check isUnconstrained(). Doing this in my sample code also fixed the problem. But why?

The exception I was getting was always a MulgaraTransactionException. The problem was happening when the transaction manager detected that an operation was being performed by a different thread to the one that had just registered itself for performing the operation. But I didn't know why this was happening.

While discussing what was happening, I started to gain an appreciation for what was happening inside the transaction manager. Andrae and I (mostly Andrae) even managed to spot some minor problems, which we could clean up. If nothing else, it was helping understand this new part of the system.

Transactions are the area Andrae just spent a couple of months working on, so I asked him to look at it. This was when I discovered that Andrae wasn't seeing these problems at all! I'd already established that a thread race was going on, and it seemed that my Core Duo (unfortunately, it's a 32 bit Core 1, and not the 64 bit Core 2) was demonstrating sufficient difference to a single cored machine to demonstrate the bug. So I gave Andrae an account on my machine, and went to bed.

RMI Threads

The next morning Andrae had some news for me. The transaction was being thrown correctly. For some reason an AnswerPage object was accessing an Answer using a different thread to the one that was asking for isUnconstrained() on the same Answer.

I was confused, as I thought that these two read-only operations would be perfectly safe operating in separate threads. Andrae explained that the semantics of an RMI connection like this required that only one thread be accessing the object at a time. Once he told me this, I immediately understood why, but it had never occurred to me before then.

The purpose of an Answer page is to package a page of Answer data, compress it, and send it over RMI to the client, all completely transparently to the client. This saves the client from making an expensive RMI call every time it needs the next row of an Answer. This is only ever performed on large result sets. The problem was that this would result in a pause for the client every time it ran out of the current page, and it needed to wait for the next one. The solution was to get the next AnswerPage in the background. In other words, they were supposed to operate in a separate thread. I have a blog entry on when I wrote this, back in 2004.

In general operation, using an Answer never resulted in two threads trying to access the server at once. The initial call to beforeFirst() would set the paging thread off, and pretty much all other calls would access local data. The only exceptions (like getRowCount()) were never going to be called while in the process of iterating over the Answer. So while I had not been aware of this issue with multi-threading over RMI when I wrote the code, the operation of the class would not have caused a problem anyway.

This all changed a few months after Answer paging was written, when isUnconstrained() was introduced. This indicates a "match" or true value for a query, even when there are no variable values to be returned. So before iterating over a result set, a client should always check for the value of isUnconstrained(). Unfortunately, the first thing a large Answer does after construction is to build start the paging thread. If isUnconstrained() is called immediately after construction of the Answer, then this will conflict on the server.

There are a few things to note here. A small Answer set will never be paged, so this bug will not manifest for Answers of less than 100 lines (or whatever mulgara.rmi.marshallsizelimit is set to by the user). Also, the form of a query will indicate if isUnconstrained() needs to be called, and only short, non-paged Answers will need this method called. Usually, the only method that will ever be called while paging Answers in the background is the next() method. However, ever since isUnconstrained() was introduced, generic code for handling and printing Answers, such as what is found in ItqlInterpreterBean, will always need to call isUnconstrained() no matter the size of the answer set. In fact, this must be the cause of the "Concurrent access exception" errors that have been reported, and I never understood.

Andrae's new transaction code was written specifically to prevent inappropriate access like this. So by throwing this exception it is doing its job perfectly. It's a godo thing he wrote it, or else this bug would have been around for a lot longer!

Once Andrae explained to me that we now had a situation where two threads could try to speak to the server at once, I realized I had to prevent both threads from operating on the server at the same time. The background thread is only ever started synchronously, in response to a call to the constructor, beforeFirst() or next(), and it ends asynchronously. On the other hand, the other methods which use RMI are all started and finished synchronously with respect to the rest of the client system. The way to handle this then is for any potentially conflicting methods to wait until a page returns.

Fortunately, the mechanism for this page return is already in place. The method is called waitForPrefetchThread(). This is the ideal method to use here, since it manages timeouts, throwing an exception if the server takes too long. All we had to do was put this method into the start of every method which makes an RMI call. It only took a few minutes to add the code, and then for the first time in a long time, every test passed!

Like the first one, this bug has been around for a while. It would also have taken much longer to be found if it were just Andrae or just myself working on it. It's a good thing we're both on it at the moment. I'll have to try to make more time available when we can both be online at once.

I hope Andrae is feeling good about these bug fixes, because I sure am!

Dreaming in Code

Time has been too short for me to comment on a couple of articles I've saw last week, so I'll just write something brief.

The first story was Software is Hard, which is an interview with Scott Rosenberg, the author off Dreaming in Code. Some of this story seems so familiar, and yet some of it seems unaware of modern software production techniques. Not that I can blame anyone for this. No technique works in all situations, and few are taught in schools or universities around the world. The most effective become a "fad" for a while, as those whose projects are most suited to them discover these techniques, but the resulting hype sets unrealistic expectations for people with less compatible project requirements.

Of course, the techniques I'm referring to are the various types of Agile programming, such as XP (the one that suffered the most from hype), Scrumm, and my own company's COSM. It is not a part of my duties to work directly with COSM, but I've still spent some time with it, and I agree that it is impressive, for the project planning as much as for the techniques of integrating business component with code components. But Agile is not the only useful technique out there.

Having defended these techniques, I will also say that they are not a panacea. Most people who use them don't really use them. They pick up on some ideas, but for reasons of practicality of preference, they decline to implement the entire paradigm. Another problem is that programmers are often at fault. It's one thing to have a great plan, but it is completely different to follow it. The type of plan you have is also going to suit different programmers differently. Highly skilled and creative programmers may be better with agile techniques, while those who pass a postgraduate course in programming will often be better suited to more structured environments like the waterfall model. (Note: I've never heard of, let alone seen, the waterfall model actually working).

It is this last part about asking talented (or any) coders to conform to management techniques that aligns most with what Scott has to say on the topic. One point of note is that he points out how good programmers enjoy re-inventing the wheel as it may often be faster than learning the intricacies of how "someone else" did it. The problem with this being that the resulting code is not tested as well, and has not been iteratively improved by running in the real world.

While this comment is true, I think Scott is looking at the problem from a traditional "commercial" viewpoint. Many programmers today, especially those in agile environments, will choose to use an open source project which implements some important functionality. The "challenge" that programmers enjoy is then sated by the integration of the many tools and libraries typical of most projects. Have a look at the library directory in Mulgara for a common example. There are 75 separate Jar files in there, all of which are from external projects.

In summary, he's sort of right, but he's also missed the ability of agile programming to work in some places. He has also seemed to have missed open source software, both as a project paradigm, and as a resource that modern programmers are absolutely ready to use.

By the way, I liked the title of the book. In my early days of programming I had several dreams in C: not about C, they were actually in C. The plot was a set of actions which was represented by functions, with people, places and events being structs. I've heard the experience is common.

A Stratified Profession

A different tone was set by Prof. Neil McBride in his article The Death of Computing. He sets a very cynical tone criticizing those still adhering to computationally pure programming techniques, and advocating the pragmatic approach. In particular, Neil talks about an inter-disciplinary approach for computers.

I like the idea of the interdisciplinary approach. After all, computers were always tools which we use to do jobs. They don't exist for their own benefit (though this has almost changed now with the advent of the internet). When I was younger, I noticed that all the successful approaches to computing relied on mixing skills with computers with expertise in engineering, finances, medicine, and so on. This made sense to me then, and it makes more sense now. This is particularly evident in the field of computational biology, where unbelievably complex systems (like genomes) are finally starting to be managed.

I also agree that in the past universities considered the computational purity above all else, and that rigidly sticking to this path is ignoring the pragmatism that the commercial world today wants. However, there seemed to be no acknowledgment of the continued need for the purists as well.

The idea seems to be that where once there were purists, today we need only pragmatists. I disagree with this. I think we need the purists as much as we ever did, but now there are also roles for the pragmatists. Whereas the profession was once restricted to the academic mindset, today we have a stratification, with different people needed at all levels.

We really do need people who don't understand a lot of the underlying system but who are prepared to be the resources needed for large financial institutions to build their enterprise systems. We need the talented developers who can take an idea, and in a few months turn it into a prototype that can set a new standard on the internet. We also need the theoreticians who analyze logic and modeling systems for completeness, or create new mathematical techniques for representing and transforming data.

I agree with the need to take a pragmatic approach. However, it can be taken too far, as is evident in many learning institutions today. Favoring pragmatism over everything else is throwing the baby out with the bathwater.

Interfaces

Interface design appears to fall into two categories.

The first category is where a set of functionality is to be provided, or is available in some way, and the interfaces are then built to provide access to all of this functionality. These designs are typically obtuse, and force a developer to jump through obscure hoops for their own internal gratification. 90% of interfaces fall into this category.

The second category is where the designer thinks about the task to be performed, and then thinks about how the code they would want to write in order to accomplish this task. Subsequent implementation may force some extra requirements into the design, but it is almost always possible to write implementations that largely fit the initial design.

Of course, the first category is built from the bottom up, and the second is top down. Sometimes it is necessary to use the bottom up approach, particularly when providing access to a pre-existing system, but the results are almost never pretty. Unfortunately, given the difficulty of many interfaces available today bottom up design seems to be the norm for designing interfaces. I want to name names here, but with the exception of Microsoft (MFC, or COM+ anyone?) it hardly seems fair to many of those hard working developers out there. (Actually, MFC doesn't seem to be a bottom up design. It's just full of weird inconsistencies where 6 similar-but-slightly different tasks rely on 6 completely unrelated mechanisms).

As an aside, when I say "interface", I'm not referring to Java interface definitions. I'm referring to the more general concept. These can be defined as Java interfaces, C++ headers, IDL files, XML descriptions, IUnknown querying, and more.

RDFS and OWL

Many interfaces I've seen for interacting with RDFS and OWL have had bottom up interfaces, often because they are trying to provide all of the functionality available in these languages. However, the result is usually very messy, and difficult to work with. For many of these interfaces, you really need to know OWL in order to use the interface.

However, the task that most developers what to achieve is often much simpler than anything that would require a complete knowledge of OWL. Typically, a developer will want to define two things: A model, and instance data.

• The model will generally involve a taxonomy of classes, each with their own specific fields. It will describe properties on those fields, such as data types, lists, which ones are key fields, which ones are optional, and so on. It will also describe relationships between the classes, and possibly restrictions on those relationships.
• The instance data will simply be a set of objects which each have a type defined in the model.

To be sure, all OWL interfaces out there allow all of this, but I personally haven't found them easy to use.

It should also be noted that OWL isn't the only way to do this. UML has done all of this for a long time now. This should be no surprise, as almost all features from each language (OWL and UML) can be mapped into a representation in the other. The exceptions are rarely employed and can be worked around (one of these exceptions is n-m associations in UML). However, UML is typically used statically at design time, and not dynamically at runtime. This makes sense, since UML is a closed world model, and a runtime system would need to allow temporarily incomplete systems while instance data was being built. OWL has a natural advantage in this regard.

RDFS/OWL Interfaces

When I needed a modeling interface, I made a conscious decision to avoid all of the OWL constructs, and only pick what I needed. I reasoned that the underlying language already would support any new required constructs, and trust that it would be possible to make sensible additions to the interface if any new requirements came along. My justification here is in my experience with interface changes usually being trivial, but modifying an underlying construct is often difficult or impossible.

Once I made that choice, my next step was to work out just what I wanted to do. The list was short, being comprised of the class definition, and object instantiation described above.

So what is the easiest way to describe each of these things? To me, a class definition is the name of the class, along with any inheritances it may have. It also contains a collection of fields. So a class definition should be a constructor which accepts a name, a list of other class definitions (or their names if I wanted to get into referencing classes before their definitions), and a list of fields. Fields would also require a name, a datatype (object or simple type), and some flags to indicate if they represented required data, a key field, and if they represented a list.

So was this approach useful? Well other than being verbose (having to describe all the fields, and then construct the class definition), it seems easy to use, and has been quite successful in the code we've used it in.

A more interesting question has been object instantiation.

I decided to take a leaf out of Perl here, where objects are just a hashmap, keyed on field name. This works quite well, and described a cheap way for me to get objects up and running. Wrapping the hashmap in a class that is given a copy of the class definition allows the data to be checked for consistency and completeness, and in some cases inferencing can be performed.

My only regret with this approach has been that it is verbose in a similar way to defining classes. The hashmap has to be created and fully populated, with each field taking its own verbose call for insertion. While easy, it isn't the way I would like to create these objects. Using the objects is similarly verbose, with all access going through get and put methods.

Thinking about it, the most obvious thing that I want to do here, is to simply create the object with an inbuilt language constructor. In the case of Java, this means a call to new, with appropriate parameters. This is what UML would have provided, but UML would have been compiled into Java source code before compilation. What I'm looking for here is dynamic creation of the class.

Bytecode Libraries

This is where my interest in bytecode libraries like ASM and BCEL comes in. Using these libraries it is possible to turn a class definition into a Java class, that can be instantiated with a custom class loader.

Make the custom class loader the current class loader, and you could theoretically use the new keyword. However, you'd have to cheat by doing a bait-and-switch, where you let the compiler build against one instance of a class, but have the class loader provide your class instead. OK, so this is an serviceable hack, but it's fun to know it's possible. Accessing fields isn't so easy though, and reflection is the only effective way.

A bigger problem is evolving class definitions over time. I've dynamically built classes in the past, but never tried to update a class after it has already been loaded once. I suppose the simplest way would be for each modification to get a new version ID that becomes a hidden part of the name, but that could lead to problems.

A better language to do this in is Ruby. Ruby already lets you define classes at runtime. More importantly, it lets you update them at runtime as well. I'm still a Ruby beginner, and I know nothing about the VM, so most of my ideas are just that, but it seems like a good idea.

I haven't had the chance to work on any of this modeling code for some months now, but I'm hoping I'll get the chance again soon. Depending on what seems most "natural" at the time, I may get to do some interesting things yet.

I should point out that most of my API is based on RDFS, with just a little OWL (InverseFunctionalProperty, Transitive, cardinality). While this sounds very restrictive, these few constructs provide a great deal of functionality. I'm looking forward to applying a few more.

Vista DRM

Windows Vista puts a lot of work into preventing what it considers to be "unauthorized" access to copyrighted material. In an attempt to plug every leak (an impossible task) the DRM system pervades every aspect of the OS, from the kernel upwards.

One disturbing aspect is the constant scanning of the system to determine if there are any fluctuations in voltage, unexpected register content, etc. Over time this totals to significant energy consumption. Also consider that the CPU requirements are significantly higher than would otherwise be expected, meaning that power consumption gets even higher.

We often don't pay attention to how much power extra CPU cycles burn in a PC, but it becomes painfully obvious when traveling with a notebook computer. I once had a PC which made it clear whenever I scrolled text in a web browser, as the fan in the power supply would go up in pitch with the extra load from the CPU. So the power difference of CPU use can be significant, despite it being hidden in amongst the hair dryer and air conditioning in your electricity bill.

If 90% of the new computers in the world (Microsoft's approximate market share) are going to be running Vista, then what will be the extra power consumption? This is a worldwide expansion in energy consumption for the sake of the MPAA.