Ruby

I've recently been making my way through the Pickaxe book, otherwise known as "Programming Ruby". I've been avoiding Ruby for a few years now, but I finally decided there was enough critical mass to make it worth my while.

Initially I thought little of Ruby, as it was just another scripting language. Despite the power and fast turnaround that these languages provide, in the late 90's and early 2000's they had always failed to deliver compelling performance. However, hardware performance has largely overcome that limitation. Even when it became apparent some years ago that performance was no longer an issue, Ruby was not a language with a lot of mindshare. The popular languages were always Perl for sysadmins and the Web, and Python for scientific applications, programs with GUIs, and some web sites. (I won't mention Tcl. Anyone who used that got what they deserved). These are generalizations, but they serve as a picture of the general landscape.

However, the importance of Ruby seemed to change with the advent of Ruby on Rails (RoR). While often criticized as not providing the scalability of the enterprise frameworks, it boasts a pragmatism that gets a lot of very compelling sites up and running in record time. This is the perfect example of the advantages in avoiding premature optimization. The fact that people can just make stuff work in Rails has been enough to see it expand into almost every Web 2.0 site I can think of. Just in case I wasn't paying attention, Sun recently decided this was worth looking at when they hired Thomas Enebo and Charles Nutter, two of the key developers in JRuby. Another indication (if I needed any) is all the interest in ActiveRDF, which is a framework for accessing RDF in a way that is compatible withe existing RoR APIs.

Now everyone I know who uses RoR tells me that I don't need to know Ruby to use it, I'm probably going to spend more time providing services (from Mulgara) than I am to be using it directly. Not to say that I don't want to use RoR... it's just that I usually find myself elsewhere in the programming stack. Besides, I love working at lower levels. So I've been thinking that I should make the time to properly learn this language.

Actually, the thing that finally made me start learning Ruby was when I discovered that there is in-built support for lambdas. Well why didn't anyway just say that before?

Currying

I'm still only partway through the book, but I'm enjoying it a lot. In my "spare time" I'm finding myself torn between reading more, and writing code in Ruby. This is completely ignoring the fact that I'm doing a big refactor in Mulgara (one reason is to improve SOAP support - allowing Ruby to work better), and that I've dabbled with the Talis Platform as well. Because of this I've been restricting myself to playing with language constructs, but I intend to start using it in earnest soon.

One of the things I've been wondering about is currying. I found a reference to doing this in Ruby, but the technique was limited to explicit currying of particular lambdas. It wasn't general, and does not refer to methods.

So I had a look at doing it more generally, and learnt a little on the way.

It would be great if methods in Ruby could be completely compatible with lambdas, but they are separate object types. Initially I despaired of getting a type for a method, as every way I could think of referring to them would call the method instead. This should have clued me into the fact that methods are found by name (as in a string) or by "label". Fortunately, both methods and lambdas respond to the "call" message, meaning they can be used the same way. Instance based Method objects also need to be bound to an object in order to be called, which I also learnt through trial and error. But in the end I found the simple invocation for currying a method:

def curry(fn, p)
  lambda { |*args| fn.call(p, *args) }
end

This doesn't do any checking that the parameters will work with it, but it works if called correctly. The thing I like about it is that it lets you curry down arbitrary lambdas iteratively. For instance, I can take a lambda that adds 3 parameters, and curry it down to a lambda that has no parameters:

add_xyz = lambda { |x,y,z| x+y+z }
add_3yz = curry(add_xyz, 3)
add_35z = curry(add_3yz, 5)
add_357 = curry(add_35z, 7)

puts "add_xyz(3,5,7) = #{add_xyz[3,5,7]}"
puts "add_3yz(5,7) = #{add_3yz[5,7]}"
puts "add_35z(7) = #{add_35z[7]}"
puts "add_357() = #{add_357[]}"

All 4 invocations here return the same number (15).

It also works on methods:

class Multiplier
  def mult(x,y)
    x * y
  end
end

foo = Multiplier.new
double = curry(foo.method(:mult), 2)

puts "double(5) = #{double[5]}"

It's not as elegant as Haskell, but I'm pleased to see that it can be generalized. It gives me faith in the power of the language.

Language Life

In recent weeks I've been having discussions with friends about where I see languages like Ruby and Java, and what we think the future may hold.

Ruby really impresses me with the eclectic approach it has taken to advanced techniques, without going overboard on multiple approaches like Perl did (Perl's infamous TMTOWTDI). The Open World model that it brings via dynamic class extension is also refreshing, and a welcome relief to those programming in Java. Ruby is also heavily OO (much moreso than Java - and very much like Smalltalk) and with lambdas it permits a very functional style of programming, which has also been gaining in popularity recently. (For some reason people often think that functional and OO are at odds with each other. This is not so. Most functional languages make significant use of objects. Functional is the opposite of imperative).

As the engine for Ruby improves (maybe even the JRuby engine), and computers become more capable, then a language like this may become the standard in just a few years. Ruby has been getting a PR boost from people heavily involved in the XP development community, and the buzz around RoR continues to grow.

Java, on the other hand, reminds me of C++ in the late 90's.

Around this time there was a huge community around C++. The ISO standard had been approved, and there were several large software houses getting the final elements of the spec into their compilers. Developers were using it from everything from operating systems and embedded devices through to financial applications and GUI front ends. Many of the major GUI libraries were in C++ (MFC, Qt, among others). Text books written on obscure template constructs were selling well. There was a strong market for good C++ developers.

By contrast, Java was a niche system. It had been publicly released in 1995, and had received quite a bit of criticism. Security flaws were found in the early "sandboxes". The GUI's that could be built were rudimentary. Performance was poor. The most compelling aspect of the system was the "demo" that Sun put together, called an "Applet", which allowed you to insert dynamic content into web pages of the browser they built to handle it. Ultimately, other systems were to overtake this one feature that was generating interest.

But I'm sure that if you're reading this blog, then you know all this stuff.

My point is that C++ seemed to be in a secure position, while Java occupied a niche. For a while there it looked like Java wouldn't make it, when Microsoft set out to "Embrace and Extend" this system, like they'd done to so many before it.

And yet, here we are, a decade later. C++ has almost fallen off the map. Sure, it's still important in some areas, but it's largely been supplanted by more modern systems. Java holds pride of place in many system, from financial, through GUIs, to embedded controllers. In fact, today Java seems to hold the place that C++ held a decade before. This alone should be an indication that Java has crested.

Using history as my guide, I would say that in 10 years time Java will be a very minor player, while something else that is a niche today will dominate the market.

If Java is to have any significance in the future, I would guess it to be in Virtual Machine (VM). While there are many VMs out there, the Java VM has had a lot of work go into it by clever people, and now that it's being open sourced, a lot more clever people will be able to help. It has already been successful enough to have spawned several new systems to run on it, including Jython, JRuby and Groovy.

If we look at Ruby as an example of a possible successor, then some may criticize Ruby for not doing OO as well as Smalltalk, or functional programming as well as Erlang and Haskell. Similar criticisms can be made of any of the other languages that are popular today. However, Java was hardly original in anything it did, and yet that didn't prevent it from the success it ultimately enjoyed. (Personally, I see Ruby's threading support to be an Achilles Heel, especially in today's hardware environment, and the direction the chip manufacturers are taking us.)

Lunar Eclipse

A friend of mine took a series of photos of the recent lunar eclipse, as seen from Brisbane. They're not serious astrophotography, but for someone like me who doesn't have much of a view of the sky any more, they were nice to see. (I miss my telescope).

I particularly like the bright exposure of the final crescent, and again when it re-emerges. It's also a nice example of how even the simplest of telescopic lenses is able to see the Galilean moons.

I recommend using the "Slideshow" view, to watch the progression of the full-size photos.

FOAF

Like David's post yesterday, there have been a number of discussions in recent months about the best practice for URIs that identify people. I've typically stayed out of the public debates, but have been involved in a number of offline conversations.

A popular approach to building these URIs is to configure an HTTP server such that when it receives a request for this URI it responds with an HTTP 303 (which means "See Other"). This lets the server respond with a document pertaining to that URI, but at the same time informs the client that this document is NOT the resolution of that URI. After all, the resolution of the URI is a person, and one can hardly respond with that (for a start, you'd need all that quantum state, and I haven't yet seen the internet protocols for quantum teleportation).

Another approach is to simply use the URI of a document describing the person, and tack an anchor onto the end. Typically this anchor is #me. Like the 303 approach, you can get a retrievable document that can be found from the person's URI, and again that document has a different URI to the URI of the person. The main problem cited with this second approach is that a #me anchor may exist in the document, meaning that the URI resolves to something other than the person (while I recently learned that URI ambiguity is not strictly illegal, it is a really bad idea. After all, we usually rely on these things to identify a unique thing). Other people suggest avoiding possible anchor ambiguity with a query (?key=value on the end of the URL). This is much less popular, and I'll let the public arguments against this stand for themselves.

While looking at the "303" approach the other day, I realized that both Safari and Firefox respond to a 303 as if it were a redirection. This makes sense in several ways. If a user has asked for "something" by address, then they'd like to see whatever data is associated with that address (as opposed to a response of "not here"). Also, the HTTP RFC says that this link should be followed. Even so, since the resulting document is NOT what was asked for, the user should at least be told that they are looking at the "Next Best Thing", rather than silently being redirected.

I came to all of this while updating my FOAF file the other day. While it is possible to describe all of your friends in minute detail, the normal practice is to include just enough information to uniquely identify them (plus a couple of things that are useful to keep locally, like the friend's name). Then when you and your friend's FOAF files are brought into the same store together, all that information will get linked up. This sounds great, until you realize that there is no defined way to find your friends' files. The various FOAF browsers, surfers, etc, that I've tried are all terrible at tracking down people's FOAFs, so whatever they're trying isn't working very well either.

Whether using anchor suffixes or 303s, the URI that people often use for themselves just happens to lead you to their own FOAF files. This would be the solution to the problem of finding your friends' files... if your friends happened to use this approach. While useful, it can't be relied upon for automatic FOAF file gathering. Because of this, I decided that I should try to put explicit links to all of my friends' FOAF URLs that I know about. This led me to tracking down the files of each of the people in my FOAF file (fortunately not many, as most of the people I know don't have a FOAF file), which had me following various 303 links, like the one to Tom's URI. I was using wget, which doesn't follow a "See Other" link automatically, and this was how I discovered that Tom was using a 303. I'm sure if I'd followed his URI with Firefox then I wouldn't have noticed the new address.

After following the links for all these people, I then wanted some way to describe the location of their FOAF in my own FOAF description of them. After some investigation of the FOAF namespace, I discovered that there is no specified way to do this. I suppose this is what led to the de facto standard that people have adopted where their person URI leads you (however indirectly) to their FOAF file. This actually makes perfect sense, as you don't want to invalidate people's links to you just because you chose to move the location of your file, but it's still annoying if you want to be able to link to other people's file. Perhaps everyone should get a PURL address?

The closest thing I could find to a property describing a FOAF file, is the more general <foaf:homepage>. This property lets you link a resource (like a person) to some kind of document describing that resource. This meets the criteria of what I was looking for, but it is also more general than I was after, as it can also be used to point to non-FOAF pages, like a person's home page (the original intent of this property). All the same, I went with it, since it was a valid thing to do. At least it will help any applications that I write to look at my own file. It's a shame that it's so manual.

While thinking about how to automate this process, it occurred to me that I could try the following:

• If a person's URI ends in an anchor, then strip it off, and follow the URI. If the returned document is RDF then treat it as FOAF data (identifying RDF as being FOAF or not FOAF is another problem).
• Follow the person's URI, and if the result is a 303, then follow that URI. If the resulting document is a RDF, the treat it as FOAF.
• Iterate through each URI associated with the person (such as <foaf:homepage>) and if any of these return an RDF file then treat it as FOAF.
• On each of the HTML pages returned from the previous iterations, check for <a href=...> tags to resources that don't end with .html, .jpg, .png, etc. If querying for any of these links returns an RDF file, then treat as FOAF.

Incidentally, Tom's FOAF file would only be picked up via the last message. You have to follow his URI to get a 303, which then leads you to his home page. Then on that page you'll find links to his FOAF file. Frankly, it was just easier to manually add a <foaf:homepage> tag to his file. :-)

Anachronism

During the various conversations I've had (mostly with Tom), it occurred to me that there is an underlying assumption that all URIs will be HTTP. This is particularly true for 303 responses, as this is an HTTP response code. However, nothing in RDF suggests that the protocol (or scheme, according to URI terminology) has to be HTTP. For instance, it isn't unheard of to find resources at the end of an ftp://... URL. It got me wondering how much it would break existing systems if the URIs used for and in a FOAF file were not in HTTP, but something different. If they handle anything else, then it's almost certain to be FTP (and possibly even HTTPS), so these weren't going to really test things. No, the protocol I chose was Gopher.

The GoFish server managed the details for me here, though it took me a bit of debugging to realize that it wasn't starting when it couldn't find a user/group of "gopher" on my system (Apple didn't retain that account on OS X. Go figure). Once I'd found that problem, it then took me a few minutes to discover that addresses for text file in the root are prefixed with 00/. But once that was done I was off and running.

I'm not a huge fan of running services from my home PC, so I can't say that I'll keep it up for a long time. But at the same time, it gives me some perverse pleasure to hand out my FOAF file as a gopher address. :-)

Mulgara on Java 6

I'm nearly at the point where I can announce that Mulgara runs on Java 6 (or JDK 1.6). Many of the problems were due to tests looking for an exact output, while the new hashtables iterate over their data in a different order.

The remaining problems fall into two areas.

The first seems to be internal to the implementation of the Java 6 libraries. In one case the HTTPS connection code is unable to find an internal class that occurs in the same place for both Java 5 and Java 6. In another case, a method whose javadoc explicitly says will contain no caching, claims that it has "already closed the file" for all but the first time you try to open a JAR file using a URL, even though the URL object is newly created for each attempt.

These problems may involve some browsing of Java source code to properly track down. Fortunately, they only show up in rarely-used resolver modules (I've never used them myself).

The other problem is that as of Java 6, the java.sql.ResultSet interface has a new series of methods on it. I'd rather that we didn't, but we implement this interface with one of our classes. This is a holdover from a time when we tried to implement JDBC. While it mostly worked, there was a fundamental disconnect with the metadata requirements of JDBC, and so we eventually abandoned the interface. However, the internal implementation of this interface remains.

Since we don't use any of the new methods, then it is a trivial matter to implement these methods with empty stubs. Eclipse does this with a couple of clicks, so it was very easy to do. Once this was done, the project compiled fine, and I could get onto tracking down the failures and errors in the tests, the causes of which I've described above.

All this was going well, until someone pointed out that there were some issues under Windows. After spending some time getting the OS up and running again, I quickly found that the class implementing ResultSet was missing some methods. How could this be? It had all the methods on OS X.

The simple answer is to run javap on the java.sql.ResultSet interface, and compare the results. Sure enough, on Windows (and Linux) the output contains 14 entries not found in OS X!

WTF?!?

This is easy enough to fix. Implementing the methods with stubs will make it work on Linux and Windows, and will have no effect on OS X. But why the difference? This meets my definition of broken.

OWL Inexpertise

One of my concerns about Talking to Talis yesterday (interesting pun between a verb and a noun there) was in making criticisms of some of the people working on OWL, when I'm really not enough of an expert to make such a call.

I expressed concern over the "logicians" who have designed OWL as being out of touch with the practical concerns of the developers who have to use it. While I still believe there is basis for such an accusation, it is glossing over the very real need for a solid mathematical foundation for OWL, and is also disrespectful to several people in the field whom I respect.

Knowing and understanding exactly what a language is capable of, is vital in its development. Otherwise, it is very easy to introduce features that conflict, or don't make sense in certain applications. Conflicting or vague definitions may work in human language, but is not appropriate when developing systems with the precision that computers require. I have to work hard to get to the necessary understanding of description logic systems, which is why I respect people like Ian Horrocks (or Pat Hayes, or Bijan Parsia, the list goes on...) for whom it all seems to come naturally. Without their work, we wouldn't know exactly what all the consequences of OWL are, meaning that OWL would be useless for reasoning, or describing much of anything at all.

However, coming from a perspective of "correctness" and "tractability", there is a strong desire in this community to keep everything within the domain of OWL-DL (the computationally tractable variant of OWL). Any constructs which fall outside of OWL-DL (and into OWL Full) are often dismissed. Anyone building systems to perform reasoning on OWL seems to be limiting their domain to OWL-DL or less. There appears to be an implicit argument that since calculations for OWL Full cannot be guaranteed to complete, then there is no point in doing them. Use of many constructs is therefore discouraged, on the basis that it is OWL Full syntax.

While this makes sense from a model-theoretic point of view, pragmatically it doesn't work. Turing machines are not tractable (for instance, one can create an infinite loop), and yet no one has suggested that Turing complete languages are not important! Besides, Gödel taught us that tractability is not all that it's cracked up to be.

A practical example of an OWL Full construct is in trying to map a set of RDBMS tables into OWL. It is very common for such tables to be "keyed" on a single field, often a numeric identifier, but sometimes text (like a student number, or SSN). Even if these fields are not the primary key of the table, a good mapping into a language like OWL will need to capture this property of the field.

The appropriate mapping of a key field on a record is to mark that field as a property of type owl:InverseFunctionalPredicate. However, it is not legal to use this property on a number or a string (an RDF literal) in anything less than OWL Full.

There are workarounds to stay within OWL-DL. However, this is one of many common use cases where workarounds are required to stay within the confines of OWL-DL. While theoretically possible that using owl:InverseFunctionalPredicate on a "literal" would cause intractability, most use cases will not lead to this. It would seem safe in many systems to permit this - with an understanding of the dangers involved. Instead, the unwillingness of the experts to let people work with OWL Full, has caused onerous restrictions on many developers. This in turn leads to them simply not bothering with OWL, or to go looking for alternatives.

I can appreciate the need to prevent people from shooting themselves in the foot. On the other hand, preventing someone from taking aim and firing at their feet often leads to other difficulties, encouraging them to just remove the safety altogether.

It's an argument with two sides. There may well be many logicians out there who agree that a practical approach is required for developers, in order to make OWL more accessible to them. However, my own observations have not seen any concessions made on this point.

---

There. It reads much better here than the bald assertion I made for Talis. :-)

Nodalities

Last night Luc was determined to keep me up, and he did a pretty good job of it. This happens frequently enough that it shouldn't be worth a mention in this blog, except that today I had agreed to speak with Paul Miller from Talis, for the Talking with Talis podcast.

So that I'd be compos mentis, I resorted to a little more coffee than usual (I typically have one in the morning, and sometimes have one in the afternoon. Today I had two in the morning). While this had the desired affect of alertness, the ensuing pleonastic babble was a little unfortunate. Consequently, I feel like I've embarrassed myself eight ways to Sunday, though Paul has been kind enough to say that I did just fine.

I was caught a little off guard by questions asking me to describe RDFS and OWL. Rather than giving a brief description, as I ought to have, I digressed much too far into inane examples. I also said a few things which I thought at the time were kind of wrong (by which, I mean that I was close, but did not hit the mark), but with the conversation being recorded it felt too awkward to go back and correct myself, particularly when I'd need a little time to think in order to get it right.

Perhaps more frustratingly, my needless digressions and inaccurate descriptions stole from the time that could have been used to talk about things I believe to me more interesting. In particular, I'm thinking of the Open Source process, and how it relates to a project like Mulgara. David was able to give a lot of the history behind the project, but as an architect and developer, I have a different perspective that I think also has some value. I also think that open source projects are pivotal in the development of "software as a commodity", which is a notion that deserves serious consideration at the moment. I touched on it briefly, but I also ought to have elaborated on how open source commodity software is really needed as the fundamental infrastructure for enabling the semantic web, and hence the need for projects like Mulgara, Sesame and Jena.

But despite my missed opportunity to discuss these things today, I should not consider Talis's podcast to be a forum for expressing my own agenda. If I have a real desire to say these things, then I should be using my own forum, and that is this blog.

As always, time is against me, but I'll mention a few of these things, and perhaps I can have time to revisit the others in the coming weeks.

People

I should also have mentioned some of the other names involved in Mulgara, from both the past and present. Fortunately, David already mentioned some of them (myself included) but since I'm in my own blog I can go into some more detail. Whether paid or not, these people all gave a great deal of commitment into making this a project with a lot to offer the community. However, since there are so many, I'll just stick to those who have some kind of ongoing connection to the project:

• David Wood, who decided we could write Mulgara, made enormous sacrifices to pay for it out of his own pocket... and THEN made it open source! His ongoing contributions to Mulgara are still valuable.
• David Makepeace (a mentor early in my career, who I was fortunate to work with again at Tucana) who was the real genius behind the most complex parts of the system.
• Tate Jones, who kept everyone focused on what we needed to do.
• Simon Raboczi who drove us to use the standards, and ensured the underlying mathematical model was correct.
• Andrew Newman who knew everything there was to know in the semantic web community, and aside from writing important code, he was the one who wouldn't stop asking when we could overcome the commercial concerns and make the system Open Source.
• Andrae Muys, the last person to join the inner cabal, and the guy who restructured it all for greater modularity, and correctness. This contribution alone cannot be overstated, but since Tucana closed shop he has remained the most committed developer on the project.
• Collectively, the guys at Topaz, who have provided more support than anyone else since Tucana closed.

These were just some of the guys who made the project worthwhile, and Tucana a great place to work.

Sorry to those I didn't mention.

Even if I move past Mulgara and into a new type of RDF store, then the open source nature of Mulgara will allow me to bring a lot of that intelligence and know-how forward with me. For this reason alone, I think that the Open Source process deserves some discussion.

Architecture

Back when Mulgara (or TKS/Kowari) was first developed, it was interesting to see the schemas being proposed. Looking at them, there was a clear influence from the underlying Description Logic that RDF was meant to represent. However, I was not aware of description logics back then, and instead only knew about RDF as a graph. Incidentally, I only considered RDF/XML to be a serialization of these graphs (a perspective that has been useful over the years), so a knowledge of this wasn't relevant to the work I was doing (though I did learn it).

Since I was graph focused, and not logic focused, I didn't perceive predicates as having a distinct difference from subjects or objects (especially since it is possible to make statements where predicates appear as subjects). Also, while "objects" are different from "subjects" by the inclusion of literal values, this seemed to be a minor annotation, rather than a fundamental difference. Consequently, while considering the "triple" of subject, predicate and object, I started wondering at the significance of their ordering. This led me to drawing them in a triangle, much as you can see in the RDF Icon.


This then led naturally to the three way index we used for the first few months of the project, and is still the basis of our thinking today. Of course, in a commercial environment, we were acutely aware of the need for security, and it wasn't long before we introduced a fourth element to the mix. Initially this was supposed to provide individualized security for each statement (a requested feature), but it didn't take long to realize that we wanted to group statements together, and that security should be applied to groups of statements, rather than each individual statement (else security administration would be far too onerous, regardless of who thought this feature would be a good idea). So the fourth element became our "model", though a little after that the name "graph" became more appropriate.

Moving to 4 nodes in a statement led to an interesting discussion, where we tried to determine what the minimum number of indices would be, based on our previous 3-way design. This is what led to the 6 indices that Mulgara uses today. I explored this in much more depth some time later in this blog, with a couple of entries back in 2004. In fact, it is this very structure that allows us to do very fast querying regardless of complexity (and if we don't, then it just needs re-work on the query optimizer, and not our data structures). More importantly, for my recent purposes (and my thesis), this allows for an interesting re-interpretation of the RETE algorithm for fast rule evaluation. This then is our basis for performing OWL inferences using rules.

See? It's all tied together, from the lowest conceptual levels to the highest!

I freely acknowledge that OWL can imply much more than can be determined with rules (actually, that's not strictly true, as an approach using magic sets to temporarily generate possible predicates can also get to the harder answers - but this is not practical). To get to these other answers, the appropriate mechanism is with a Tableaux reasoner (such as Pellet). However, from experience I believe that most of what people need (and want) is covered quite well with a complete set of rule-base inferences. This was reinforced for me when KAON2 came up with exactly the same approach (though I confess to having been influenced by KAON2 before it was released, in that I was already citing papers which formed the basis of that project).

All the same, while I think Rules will work for most situations, having a tableaux reasoner to fall back on will give Mulgara a more complete feature set. Hence, my desire to integrate Pellet (originally from MIND Lab).

I have yet to look at the internals of Pellet, to see how it stores and accesses its data. I'd love to think that I could use an indexing scheme to help it to scale out over large data sets like rules can, but my (limited) knowledge of the tableaux algorithm says that this is not likely.

Open Source

There are several reasons for liking Pellet over the other available reasoners. First, is that it is under a license that is compatible with Mulgara. Second, is that I saw the ontology debugger demonstrated at MIND Lab a couple of years ago, and have been smitten ever since. Third, the work that Christian Halaschek-Wiener presented at SemTech on OWL Syndication, convinced me that Pellet is really doing the right thing for scalability on TBox reasoning.

Finally, Pellet is open source. Yes, that seems to be repeating my first point about licenses, but this time I have a different emphasis. The first point was about legal compatibility of the projects. The point I want to make here is that reasoning like this is something that everyone should be capable of doing, in the same way that storing large amounts of data should be something that everyone can do. Open source projects not only make this possible, but if the software is lacking in some way, then it can be debugged and/or expanded to create something more functional. Then the license point comes back again, allowing third party integration and collaboration. This lets people build something on top of all these open source commodities that is a gestalt of all the components. Open source projects enable this, allowing the community to rapidly create things that are conceptually far beyond the component parts.

From experience, I've seen the same process in the commercial and open source worlds. In the commercial world, the growth is extraordinarily slow. This is because of limited budgets, and limited communication between those who can make these things happen. Ideas are duplicated between companies, and resources are spent trying to make one superior to all the others, sometimes ignoring customers' needs (and often trying to tell the customer what they need).

In the open source world, everyone is free to borrow from everyone else's ideas (within license compatibility - a possible bugbear), to expand on them, or to use them as a part of a greater whole. Budgets are less of an issue, as projects have a variety of resources available to them, such as contributing sponsors, and hobbyists. Projects focus on the features that clients want, because often the client is contributing to the development team.

Consider MS-SQL and Oracle. Both are very powerful databases, which have competed now for many years. In a market dominated by these players, it is inconceivable that a new database could rival them. Yet MySQL has been steadily gaining ground for many years, first as a niche product for specialized use, and then more and more as a fully functional server. It still has a way to go to scale up to high end needs as the commercial systems do, but this is a conceivable target for MySQL. In the meantime, I would guess that there are more MySQL installations in the world than almost any other RDBMS available today. Importantly, it got here in a fraction of the time that it took the commercial players.

Semantic Web software has a long way to go before reaching the maturity of products like those I just mentioned. We still have to take semantic web software a long way forward. But history has shown us that the way forward is to make the infrastructural software as open and collaborative as possible, enabling everyone to develop at a much higher level, without being concerned about the layers below them. Higher level development has happened with many layers of computing in the past (compilers, OO toolkits, spreadsheets, databases, web scripting languages for server-side and client-side scripting), and the cheaper and more open the lower levels were, the more rapid and functional the high level development became.

It is at this top level that we can provide real value for the world at large, and not just the IT community. It is this that should be driving our development. We should not be striving to make computing better. Computers are just tools. We should be striving to make the world better.

Sounds pretty lofty, I know. Blame the caffeine from this morning wearing off and leaving me feeling light headed. But there has to be some point to it all. This all takes too much work if we indulge in navel gazing by only enabling IT. IT has to enable people outside of its own field or else there is no reason for it to exist, and we will all get caught in another .com bubble-burst.

WiFi in the Balkans

For some time I've known that there is WiFi all over the place here (such an easy-to-remember name when compared to 802.11). However, using an iPhone really brings it home. Whenever I look something up while out of range of my usual networks (and let's face it, I wouldn't have bought an iPhone if I weren't going to be using it all the time) I get a list of anything from 3 to a dozen networks all within range. And this doesn't consider the networks that aren't being broadcast (though I don't think many people use this option). With the exception of the occasional commercial access system (give us your credit card details and we'll let you in), then all of these access points are locked.

Many people have unlimited, or virtually unlimited, high speed internet access, and they're all attaching these wireless gateways to them. These access points then overlap tremendously in range, causing interference with each other, and slowing each other down. This seems like massive duplication to me. Add to this the fact that most of these networks spend the majority of their time idle, and the pointlessness of the situation is even more frustrating.

I'm not advocating grid networking (I'm skeptical that the technology has the algorithms to efficiently route the massive amount of data it would need to deal with). However, it would seem that if the network were configured such that access point owners could open up their access points and let everyone on, then everyone would benefit. Some points would get more traffic than others, but overall it should even out. Coming from this perspective I can understand why so many cities have looked at providing this service, and why Google decided to roll it out in Mountain View.

Many of the advantages are obvious. More efficient usage of the airwaves (fewer mid-air packet collisions), ubiquitous urban access, and less infrastructure cost to the community as a whole.

Unfortunately, I can see the downside too. It would have to be paid for by the community, rather than the individual. The total cost would be much less than is being paid now (by each individual, with their own access point and their own internet connection), but the money still has to come from somewhere. It may not be much in a city budget, but there are always those who don't feel they need to pay extra taxes for services they don't use. I disagree with this view, but my opinion has no impact on voters, and by extension, my opinions have no influence with politicians.

I can also see the authorities having a hissy fit over it. It's trivial to use the internet anonymously (3 coffee shops within a block of here have free WiFi - not to mention more technical solutions), but ignorance or laziness of most people still allow the police, and others, to track down people of interest. The fact that this kind of tracking can be circumvented, or even redirected to someone innocent is of little consequence here. Those who want to find people engaging in certain activities on the internet would not want to allow universal anonymous access, especially in this age of post-911 paranoia. Authorized (and identified) access is not really feasible in this situation, as it would be nearly impossible to roll out and enforce, and easily circumvented. So the easy solution is just prevent people from having ubiquitous community-sponsored WiFi.

The legal framework for some of these restrictions is already being set up in some jurisdictions. Many concerns are currently around accessing private (sometimes download limited) networks, but as these concerns are removed with the promise of ubiquitous "free" access, then other reasons will be cited.

Even more influential than law enforcement (in this country) are the network providers. These companies have already tried to prevent cities from rolling out ubiquitous WiFi. They are obviously scared it will threaten their business model. I don't really care too much, as they are already being paid a lot of money for under utilized service (all those redundant lines not being used to their capacity), and abuse their market in many other ways as well. Like many other large companies, they are unwilling to try to keep up with their market, preferring to shape the market to their own desires. This works in the short term, but history shows it is doomed to failure in the long run.

In the meantime, I'll continue to use EDGE on my iPhone, and wish that my previous phone hadn't died before Apple brought out a model that included 3G.

I'm struggling to stay awake while I type. Does it show?

Conversations

I've just spent a week working in Novato, CA. While I didn't get much programming done, I did manage a few very productive conversations. I spent the whole week working with Alan, who is interested in Mulgara (for various reasons), and on Wednesday night I finally got to met with Peter from Radar Networks.

While describing the structure of Mulgara, and particularly the string pool, Alan had a number of astute observations. First of all, our 64 bit gNodes don't have a full 64 bit address space to work in, since each node ID is multiplied by the size of an index entry to get a file offset. This isn't an issue in terms of address space (we'd have to be allocating thousands of nodes a second for decades for this to be a problem), but it shows that there are several unused bits of addressable space that are unreachable. This provides opportunities for storing more type information in the ID.

This observation on the address space took on new relevancy when Peter mentioned that another RDF datastore tries to store as much data as possible directly in the indexes, rather than redirecting everything (except blank nodes) through their local equivalent to the string pool. This actually makes perfect sense to me, as the Mulgara string pool (really, it's a "URI and literal" pool) is able to fit a lot of data into less than 64 bits already. We'll only fit in short strings (7 ASCII characters or fewer), but most numeric and data/time data types should fit in here easily. Even if they can't, then we could still map a reduced set of values into this space (How many DateTime values really need more than, say, 58 bits?).

Indeed, I'm only considering the XA store here. When the XA2 store starts to come online it will have run-length encoded sets of triples in the blocks. This means that we can really stretch the length of what gets encoded in the indexes without diverging to the string pool.

The only thing that this approach might break would be some marginal uses of the Node Type and DataType resolvers. These resolvers are usually used to test or filter for node type information, and this function would not be affected. However, both resolvers are capable of being queried for all the contents of the string pool that meet the type criteria, and this function would be compromised. I'm not too worried though, as these functions are really only useful for administrative processes (and marginally at that). The only reason I allowed for this functionality in the first place was because I could, and because it was the natural semantic extension of the required operations. Besides, some of the other changes we might make to the string pool could invalidate this style of selection of "all uses of a given type".

Permanent Strings

The biggest impediment to load speed at the moment appears to the be string pool. It's not usually a big deal, but if you start to load a lot of string data (like from enwiki) then it really shows. Sure, we can cache pretty well (for future lookups), but when you are just writing a lot of string data then this isn't helping.

The use cases I've seen for this sort of thing usually involve loading a lot of data permanently, or loading it, dropping it, and then re-loading the data in a similar form. Either way, optimizing for writing/deleting strings seems pretty pointless. I'm thinking that we really need an index that lets us write strings quickly, at the expense of not being able to delete them (at least, not while the database is live).

I'm not too concerned about over optimizing for this usage pattern, as it can just be written as an alternative string pool, with selection made in the mulgara-config.xml file. It may also make more sense to make a write-once pool the default, as it seems that most people would prefer this.

I've been discussing this write-once pool with a few people now, but it was only while talking with Alan that I realized that almost everything I've proposed is already how Lucene works. We already support Lucene as the backend for a resolver, so it wouldn't be a big step to move it up to taking on many of the string pool functions. Factor in that many of the built in data types (short, int, character, etc) can be put into the indexes online, and the majority of things we need to index in the string pool end up being strings after all, which of course is what Lucene is all about. Lucene is a great system, and integration of projects like this is one of the big advantages of building open source projects.

It's been a while since I wrote to the Lucene API. I ought to pull out the docs and read them again.

Java 1.6

Mulgara currently doesn't work with Java 6 (also called JDK 1.6). I knew I needed to enable this, but have been putting it off in lieu of more important features. But this release made it very plain that Mulgara is in an awkward position between two Java releases: namely JDK 1.4 and JDK 1.6.

The main problem going from Java 1.4 to Java 5 was the change in libraries included in the JRE. Someone had taken advantage of the Apache XML libraries that were in there, but now these had all changed packages, or were no longer available. The other issue was a few incompatibilities in the unicode implementation - some of which were the reason for introducing the CodePoint class last year, and published 8 days ago.

Going to Java 6 is relatively easy in comparison. Sun learnt their lesson about dropping in third party libraries that users may want to override with more recent versions, so this was not an issue. The only real change has been to the classes in java.sql, in which new interfaces and extensions to old interfaces have prevented a few classes from compiling. This is easily fixed with some stub methods to fulfill the interfaces, since we know these methods are not being called internally in Mulgara.

I haven't gone through everything yet (like the failing HTTP tests), but the main problem for Mulgara seems to be in passing the tests, but not in the code itself. The first of these was a query that returned the correct data, but out of order. Now any queries whose results are to be tested should have an ORDER BY directive, so this failure should not have been allowed to happen. It's easily resolved, but that made me wonder about the change in ordering, until I got to the next test failure.

Initially, I was confused with this failure. The "bad output" contained an exception, which is usually a bad sign. But when I looked at the query which caused the exception I realized that an exception was the correct response. So how could it have passed this test for previous versions of Java? Was it a Schrödinbug?

The first step was to see what the initial committer had expected the result to be. That then led to a "Doh!" moment. The idea of this test was to specifically test that the result would generate an exception, and this was the expected output. Why then, the failure?

Upon careful inspection of the expected and actual outputs, I found the difference in the following line from teh Java 6 run:
Caused by: (QueryException) org.mulgara.query.TuplesException: No such variable $k0 in tuples [$v, $p, $s] (class org.mulgara.resolver.AppendAggregateTuples)
Whereas the expected line reads:
Caused by: (QueryException) org.mulgara.query.TuplesException: No such variable $k0 in tuples [$p, $v, $s] (class org.mulgara.resolver.AppendAggregateTuples)
I immediately thought that the variables had been re-ordered due to the use of a hash table (where no ordering can be guaranteed). So I checked the classes which create this message (org.mulgara.resolver.SubqueryAnswer and org.mulgara.store.tuples.AbstractTuples). In both cases, they use a List, but I was still convinced that the list must have been originally populated by a HashSet. In fact, this also ties in with the first so-called "failure" that I saw, where data in a query was returned in a different order. Some queries will use internal structures to maintain their temporary data, and this one must have been using a Set as well.

To test this, I tried the following code in Java 5 and 6:

import java.util.HashSet;
public class Order {
  public static void main(String[] args) {
    HashSet s = new HashSet();
    s.add("p");
    s.add("v");
    s.add("s");
    for (String x: s) System.out.print(x + " ");
    System.out.println();
  }
}

In Java 5 the output is: p s v
In Java 6 the output is: v s p

I checked on this, and the hash codes have not changed. So it looks like HashMap has changed in its storage technique.

Fix

I have two ways I can address me problem. The first is to find the map where the data gets reorganized, and either use an ordered collection type, or else use a LinkedHashSet. The latter is still a set, but also guarantees ordering. However, this is a patch, and a bad one at that.

The real solution is to write some more modules for use in JXUnit, to make it more flexible than the current equal/not-equal comparisons done on strings now. This seems like a distraction from writing actual functionality, but I think it's needed, despite it taking longer that the "hack" solution.

Speaking of which... DavidW just asked if I could document the existing resolvers in Mulgara 1.1 (especially the Distributed Resolver). He didn't disagree with my reasons for releasing without documentation, but he pointed out that not having it written up soon could result in a backlash. Much as I hate to admit it (since I have other things to do), he's right.

Release

The last week or so has not been conducive to sleep, nor blogging. After getting back I've been trying very hard to get Mulgara version 1.1 out the door. This involved cleaning code a little, but mostly getting documentation right, administering Subversion, updating web sites, looking for source code for obsolete libraries we haven't updated yet (there's something I could use some spare time for), and a hundred things I can't remember right now. And to think, I only took on the administration role to expedite my desire to continue developing for the project.

Shortly after release, there was an awkwardnessful^* moment when someone found that the Ant build was broken when a command-line Subversion was unavailable. Fortunately, Ronald fixed this rapidly, and all was well.

Speaking of Ronald, I should mention that a number of other people were involved in this as well. Ronald did some fixes and added a few features. Andrae did some amazing architectural work and implementations. Amit arranged for some of Andrae and Ronald's time. David followed through where few would dare to tread by checking the legal side of our licensing and the libraries we use. Even Brian (who has been MIA until recently) did some proof reading for me. Many thanks to all of these people.

So this leaves me with the rest of my professional life to get back to.

Blogging

So much to talk about, so little time.

I've been talking with a number of people lately on IRC, and IM, about some of the ideas I've had lately. I want to blog this stuff, but with the amount of time I've had lately I'm starting to wonder if I should just post the conversation logs (this was first suggested to me in Twitter by Peter). In the meantime, I hope some of the technical stuff is evolving to a more well thought out plan before I get it all written.

On the other hand, this may also be working out for the best. Some of the blogs I want to write are just rants. This may or may not be justified, but it wouldn't hurt me to get a full night's sleep before indulging in such a diatribe!

In the meantime, tonight I'm just writing something to remind people I'm still here.

Relaxing

With an impending tax refund, plus some frantic saving, I've finally convinced Anne to let me get a piano. One of my lifelong dreams is to own my own baby grand (but that needs more money than I'm likely to have any time soon, plus a bigger house than I'm likely to live in!), with a backup plan of a nice upright. Unfortunately, a decent upright piano is still too expensive, and much too heavy to get up our narrow stairway.

A good compromise at this stage is a digital piano. Now, I've never been a big fan of digital pianos (ironic, coming from an electrical engineer), but I have to say that you can get some pretty nice ones now. The one we finally selected has a very realistic action (essential for proper playing) and very nice sound, achieved through dynamic sampling. This is a fancy way of saying that they recorded every key being hit with varying amounts of force, so the sound played back is a completely different one, depending on how hard you hit the key. It's a great idea, and sounds really good.

But digital piano designers have never really seemed to understood harmonics. Sigh.

All the same, it's almost like the real thing, and it's been an amazing sense of relief to be able to play it. I haven't been able to play now for a few years, and it's always been one of my most enjoyable ways of relaxing the mind. Last night was the first time I got on the new keyboard, and I didn't fire it up until I got the Mulgara fix done (and then I had to spend time assembling it). So I was tired by the time I got to sit and play. But that didn't matter. Two hours later, my right hand was cramping, the fourth and fifth fingers on my left were too exhausted to respond properly, and my back was aching. But I felt so happy that none of that seemed to matter. :-)

Tonight after just a short warmup, I struggled my way through the first movement of the Pathétique sonata. This is way beyond me at the moment, but still fun to struggle through (no, I didn't do the repeat. I could already feel my hand tightening up by the time I got to it). By the end, I was feeling pretty much like I did last night, only now my brain felt fried from trying to read such dense music. Well, it was dense for someone as out of practice as I am.

The fried-brain feeling was unusual. I got to the final page of the first movement (it's 10 pages long) and I started looking at chords and triads that I knew I was capable of understanding, and yet my brain refused to decipher them. I had to stop and look away for 5 seconds before I could look back and understand it. I've never had anything like that happen to me before. I guess I was just using paths in my brain that haven't been used for a very long time. It should get better soon.

Notebook

After 2 years (1.5 in Chicago) at work, I've finally received a computer! Admittedly, I avoided asking to start with, as the standard desktop was Windows (and I've done enough of that, thank you very much), but 7 months ago I realized I was wasting too much time on my slow old PowerBook, so I put in the request. Fortunately, by this time, it was agreed that new Mac would be appropriate, and so I've been waiting ever since.

The order just went in 2 weeks ago, and the computer was supposed to arrive yesterday. However, after 7 months of waiting I wasn't really surprised to get an email forwarded to me from Apple which said that the shipment had been delayed. I was worried it wouldn't be here until after I've left for San Francisco next week, but then it showed up at lunch time today.

Whew!

I used a firewire cable to bring over as much as I could from my previous machine, but there are a few things that aren't working. The first thing I had to do was to get the latest in Java SDKs and documentation. After that, I've been trying to get up to date on the various PPC binaries that I've compiled through Fink. It hasn't been all smooth sailing (the firewire transfer took several hours, during which time I had NO computers available to me), but it's nearly there. I have to say though... it's fast!

Looking forward to actually getting some real work done in the office now!

---

* 10 points to anyone who can say where this word comes from. You can prove it by providing the other word in the same category. :-)

CodePoints

I was just asked about the Code Point code that I discussed last year. This is essentially a fix for java.lang.Character, since Unicode can require more than 16 bits.

I've put the Java file up here. There's also an example class which takes a string on the command line, and returns the characters sorted, with duplicates removed (the original task that led me to write this class). For instance, if the command line is:

$ java SortUnicode bacdaffaabzr

Then the output is:

abcdfrz

Sure, this can be done relatively easily in Java. The advantage of the CodePoint class is that it provides a useful utility interface, and allows a more functional approach. In this case, it's possible to use a single (verbose) line:

CodePoint.toString(
  CodePoint.toArray(
    new TreeSet(
      CodePoint.toList(inputStr)
    )
  )
)

There's nothing fancy here, but I hope it's useful.

OWL with Rules

Yesterday Henry asked me about using EulerSharp (by Jos De Roo) with Mulgara. I've already done the rules engine, and I'm very happy with it, so I told him I won't be replacing it. Admittedly, there's room for optimization - but that's just a matter of finding the time. It runs well as it is.

Of interest though is getting together the rules for making OWL happen. EulerSharp has these in abundance. It may be worthwhile writing an interpreter than can translate them to the Mulgara engine.

There are the obvious rules like:

{?P @has owl:inverseOf ?Q. ?S ?P ?O} => {?O ?Q ?S}.

But the real value would be in rules like:

{?J @has owl:intersectionOf ?L.
 ?L :item ?I1.
 ?I1 owl:onProperty ?P;
     owl:someValuesFrom ?S.
 ?S owl:onProperty ?Q;
    owl:minCardinality ?N.
 ?N math:equalTo 2.
 ?L :item ?I2.
 ?I2 owl:onProperty ?P;
     owl:allValuesFrom ?A.
 ?A @has owl:unionOf ?K.
 ?K :item ?C,
          ?V.
 ?V owl:onProperty ?Q;
    owl:maxCardinality ?M.
 ?M math:equalTo 1.
 ?L :item ?I3.
 ?I3 owl:onProperty ?P;
     owl:allValuesFrom ?D.
 ?C owl:disjointWith ?D}
=> {?J owl:equivalentClass owl:Nothing}.

Which is a convoluted way of testing if a class is an intersection between restrictions with max cardinality of one, and minimum cardinality of 2, where the other possibilities of class membership (via unions, etc) are all eliminated.

Some of the type inferencing on intersections and unions may eliminate the need for complex rules like this (I've been meaning to check out just how far this takes you), but it's cool (scary?) to see it all done in one step like this.

I really need time to write more reasoning code in Mulgara. :-(

Mulgara Nearly There

After my week off, I got back to find that the release candidate had gone fine, and no one had bugs to report. The only suggestions were some documentation shortcomings.

I fixed those parts of the documentation which were really wrong (like the fact that we only run on Java 1.5 at the moment), but decided to leave alone the documentation for the new resolvers. This is because of the time required to write this, and also because none of the existing resolvers are documented anyway! This is a problem for all resolvers, and needs fixing, but since we put 1.0.0 out without this documentation, I figure it won't kill 1.1.0 to be missing it either.

Consequently, the release is ready, and all the files are in place. I was prepared to announce it, but then David got back from vacation and offered to do a legal review. I can't afford to turn him down on this, so it's sitting and waiting until I hear back from him. Fortunately, he said he can have it done by the end of the weekend.

I'm looking forward to getting some new functionality in Mulgara, so I'll be relieved when this is out of the way.

Certificates

When I first set up https on Mulgara (for Subversion access) I used a self signed certificate so I could get it up and running. Since then, I've looked at getting a real certificate from an appropriate authority, but I'm not sure where to go for it.

There are a couple of free options (my favorite being CAcert), but I don't know of any that are included by default in any browsers. This makes them little better than self signed certificates - which aren't worth the bits they're printed on.

So, do I fork over some money for a Thawte, VeriSign or similar certificate? Or is there a better option for a project that is really just my hobby. I already pay for the domain and I keep a server solely for Mulgara tests, so it would be nice to keep the certificate cheap.

Talis

Lately I've been hanging out in #talis on IRC. It's a corporate IRC channel, but unlike other companies (like mine) they've put it on a public server where anyone can find it and join in. Not only that, but some of the staff blogs point out that they can usually be found there.

Well, that seemed like an open invitation, so I've been joining in for the last few days. :-)

It's exactly the sort of thing you'd expect, in that it is just discussion between staff facilitating the various tasks they are involved with. Of course, there is a lot of humor as well, which I've appreciated, since American humor is different to my own. We spell it differently, for a start!

I was particularly interested to see that they hold their daily Scrum meetings in IRC. I suppose this is necessary, given that they have people all over. The other thing is that I've enjoyed saying hello to people who's blogs or emails I've been reading for years, but have never interacted with before. Well, almost never. One of them responded to something I said at the end of a post a few years ago, and I've received very occasional emails from him ever since (and I occasionally pester him with stuff - he'll know who I mean if he's reading this). :-)

Overall, between IRC and their podcasts, they seem to be a bright group of people, and are destined to make waves in the semantic web. I'm curious to see where they go.

Dopplr

PaulM recently made one of his infrequent posts (like I can talk), mentioning Dopplr in the process. Then just last night IanD linked to an interview with Dopplr's lead developer, Matt Biddulph.

Dopplr sounds interesting. It's almost enough to make me regret not traveling enough to justify joining. Almost.

Back when I couldn't afford it, I used to enjoy traveling. I still enjoy it, but leaving the kids and Anne takes the luster off the experience. I'm looking forward to the day when the boys are happy for me to leave, and Anne and I can go somewhere on our own for a weekend... or a week.

I also note that Dopplr want to add in support for calculating your miles for Terrapass. Expedia pointed me to Terrapass on my last flight, and I was very happy to use it. I'm planning on making use of it as much as possible in future.

Most transport has alternatives that can use less emissions, but air travel is one of seems to have no solution. I'm not a big fan of "carbon offsets", as it's usually an excuse for pushing the problem off on someone else, and doesn't provide a solution (besides, carbon is only one of many problems with emissions). However, there are many occasions where there simply is no better alternative, in which case I fully endorse them. Carbon offsets are usually the domain of large corporations, but Terrapass makes them accessible to consumers. I don't think that lets the corporations providing to the consumers off the hook, but it does allow people to get involved.

I was also pleased to note in the news recently that the FAA are looking to clean up the airlines. Even if they're successful, I somehow doubt that Terrapass will charge less per mile. ;-)

Camping

I'll be away camping for the next week. This will be my first time without any kind of access to a computer in a few years. I'm looking forward to it.

I'm also looking forward to the company. Not only will I be able to spend some uninterrupted time with my family, but we'll be with friends whom we haven't spent much time with lately. I'm sure the occasional conversation may end up on physics or philosophy, but in general it will probably be about children.

Outside of Anne and the kids, I've been a bit starved of company lately. We have some good friends here, but aside from them being perpetually busy (what is it with people around here that they have to plan their every waking moment) I don't actually know anyone local who shares my interests. Consequently, I think I've been pestering some of my contacts online a little too much lately, and for any of you who read this and have experienced that, I apologize. Hopefully I'll be a little less annoying after my break.

Slow Debugging

My notebook computer is now officially too slow for me. Unfortunately, I can't afford a new one - at least, not until our house in Australia sells (fingers crossed). In the meantime, it is the only computer I have access to at work.

In February I realized that my own machine was too slow for me, and that it was about time that the company provided me with something I could get work done on. The guy in change of these things agreed, and a new purchase was approved. However, it's now late June and I'm still waiting. I was told last week that they decided to lease the computer instead (which doesn't really impact me at all, since I was never going to own it), and just this week they put the application in. Now they're waiting to hear back from the finance company. Hopefully I'll have something in July, but I'm not counting my chickens just yet.

The reason I've gone into this, is because I spend my days on my current notebook, and have great difficulty getting any work done. I often have to wait for nearly a minute while switching windows, and can regularly type far ahead of the display (it's like being on an old modem). Consequently, using a system like Eclipse to do debugging is just impossible. Because of this, my boss suggested I could work from home more often.

I'm a little hesitant to be isolated from the office, and my notebook is too slow to get away from the kids down at the coffee shop, but getting to use my home PC has caused these concerns to fade into insignificance. I've worked at home every second day this week, and on these days I managed to get an enormous amount of work done. I'd been feeling ineffectual at work recently, and I hadn't realized that my computer was contributing so much to that.

Mulgara 1.1

I'm not supposed to do any Mulgara development when I'm at work, but I managed to get away with it this week. I'm supposed to be building a library on top of Mulgara. However, since the next version of Mulgara is due very soon now (I know, because Andrae and I said it!) then I figure that it doesn't make sense to code the library to the old released version. But the only way there will be a new release is if I do it, meaning that my work on this new library is blocked on my being able to release the next version of Mulgara. This is my justification anyway.

I've spoken with the other guys I work with, including the CTO, and no one disputes my approach. I know that a lot of people have wanted this done, so I'm pleased I've had the opportunity. It can be hard to do it all at night.

Unfortunately, we don't have a re-implementation for the graph-renaming code. Brian had expected to do it, but other commitments have prevented him. Either Andrae or I will do it now. It needs to happen soon, so I'm hoping that Andrae might have it done by the time I get back. Otherwise my evenings in early July will be heavily booked.

Other than that, we have a fix for all the critical bugs in the system. We already had several new features (the new transaction architecture, distributed queries, etc) but we've just been holding off on the next release until we'd fixed the most critical problems. Andrae did a great job with several, and I'm very appreciative to both him and Topaz for making that happen.

Blank Nodes

Just in the last week I've worked on a problem we've had with inserting blank nodes. Both the N3 loader and the distributed resolver had issues with this. In both cases the code would fail to recognize the reuse of a blank node ID, and we would get separate blank nodes in the system. In both cases, the solution needed a similar approach, though it had to happen in very different places.

The N3 loader just needed to make sure that it remembered which blank nodes it had already seen. It turned out there were two problems, with the first being that the loader expected anything after the special "_:" namespace to be a number. This is not true, even with our own internal identifiers (which use a format of _:node###, where each # is a digit). The second problem was that there was no production of new nodes when they were needed, though a reference to a BlankNodeFactory was commented out. Apparently, this is from an earlier iteration of the code, where it appears that the code worked correctly. However, someone changed it without adequate testing.

It turns out that it is not trivial to test for this with our standard testing framework. Our scripted tests look for an explicit set of output values, which we look for exactly. However, blank nodes could be assigned any identifiers, so any check for them can't look for specific values. Instead it has to be clever and make sure that the nodes in the right places all match each other (and not any other nodes). Of course, this can be done, but it will take about a day (on my home computer - I have no idea it would take on my notebook), and I haven't had time to get to it yet.

The distributed resolver also needed to remember nodes it had seen before, but this time the code to do it is inside the internal Localization routine. Blank nodes coming from another computer always get negative identifiers (indicating they are temporary values), and the maps which convert these values into allocated nodes can only accept positive values. However, I couldn't just invert the sign of these values, as insertions of local blank nodes also goes through this code path (something I forgot at one point, but was immediately reminded of).

So then I spent 20 minutes coming up with an elaborate method of making sure that I was only inserting local positive numbers, or foreign negative numbers, only to remember that it is allowable to have both come in at once (I need to write a test for that - it will involved a disjunction across graphs). It was only when I went to fix this that I realized that a positive ID will always be the value of an allocated node. Indeed, it will always be the value of the very node you need, meaning there is no need to map it. Well, at least I realized that before I discovered it during testing (or worse - someone making a bug report on it).

The maps we have are all effective, but they result in file access whenever they are created. This was in the back of my mind as something I should optimize, when I started failing tests. It turned out that there was too much file activity, and I had created too many files. Doh. Some cleanup in the close() method fixed that. But that reminded me that I was still creating these maps, even when no blank nodes needed to be remembered.

The easy optimization here was lazy construction of the maps. Hmmmm, now that I think of it, I should make that lazy construction of only the needed map (since only one is usually needed: either map by numeric ID or by the string URI for the blank node). I noticed that at least one of these maps has a memory cache, but the file is already created. I'm thinking that we need an external cache, which can put off creation of the file until some pre-set mark is reached, like 1000 nodes, or some value like that. This localization routine is used everywhere, so avoiding disk usage is important.

Anyway, all the big bugs have been hit, and I've put it out in SVN as a release candidate. If it hasn't broken by the time I get back from camping, then it gets released as version 1.1.0. Then we have to do the model renaming (again) and that can be rolled in as a relatively quick release for 1.1.1.

Our time between released has been terrible, especially when you consider the fixes and features that have gone in, so a quick release of the next point release should be a step in the right direction.

After that, the next big features have to be in scalability and SPARQL. Frankly, I'm not sure which is more important at this stage. Real scalability changes will take some time to implement, but in the meantime we can do a few small things that will have a noticeable effect. But I don't want to supplant SPARQL development either, so finding the balance will be tricky. Fortunately, Indy is building the SPARQL parser at the moment using JFlex/Beaver (an LALR parser generator), so I know it's in good hands. I've promised to take him through our AST as soon as he's done, so we can hook the two together.

Trans

Tonight I got to spend a bit of time online describing the transitive functionality in Mulgara to Ronald at Topaz. It's a technique I came up with a few years ago, where you join a set of statements against itself iteratively. The result is that each join stretches twice as far as its predecessor across the graph. Consequently, you only have to do at most log₂(n) joins to find the full transitive closure across the graph. You trade space for speed, but it's not too bad, as the only space you use up is for the statements you were looking for.

I looked up various papers on complexity of transitive closure on a directed graph, and they claim that the most efficient algorithm will be polynomial in log(n). Interestingly, all the papers I found presumed that the graph could contain no loops, but this is not a valid assumption in RDF. To get around this, I also kept a set of nodes that have already been visited, so as to avoid iterating indefinitely when a loop occurs. This increases the memory requirements beyond what I mentioned above, but with no increase in complexity.

Another nice feature is that "backward-chaining" does not improve the complexity at all. All it does is reduce the amount of memory being consumed, and the length of some of the loops. However, while having a possible impact on performance, neither of these considerations affect complexity.

Andrew told me that he basically copied my code and then modified it to make the walk functionality. I've never looked at walk but Ronald tells me that they look almost the same. While I never looked at walk, I did notice that Andrew's name is listed as an author of trans. I know I talked some of it through with Andrew, but I also recall writing at least a lot of it on my own. I should ask him about that.

Ronald is a bright guy, but trying to read the algorithm from code had him stumped. I believe that the code is clear about what it's doing, but the reason for doing it was not clear at all. I tried to explain it to him, but he thought it was operating linearly (and not logarithmically) until suddenly I got a message saying that he'd just been blinded by the light.

There are a lot of very bright people in the semantic web, and it can get a little intimidating sometimes, especially when you're off on your own like I am at the moment. It's reassuring to be told that you can do something clever every once in a while. :-)

I'm also thinking of taking this code, and using it again, only this time with an unbound predicate. This would let you find the shortest path between two nodes with the same complexity as transitive closure. The difference here is that the space requirements would grow significantly, but since we back these things with disk-based storage, maybe that's acceptable. I'm told that several people would like to see this feature.

FOAF

While waiting for Eclipse on my notebook to catch up the other day, I finally decided to get around to writing a FOAF file. I didn't go to enormous effort, and just used Leigh Dodds's FOAF-a-matic generator. I'm sure there are more people I can add in, but I didn't have a lot of their details. You can find the file over on the right here.

Once I had the file, I then had to wonder what to do with it? Danny's comment has some useful links, but I was a little disappointed to see how out of date a lot of it is, as some of the services that I tracked down aren't there any more. I was also surprised to learn that there's very little aggregation anywhere.

The FoaF Explorer site requires that you enter an individual's FOAF URL, and then you can just get the details from that file. It picks up on URLs that it finds in the file, and if the file was written to include rdfs:seeAlso links for other people, then it will let you navigate to those people's FOAF pages as well. However, it's all very brittle. Some of the pages suggested on the entry page (like Libby Miller) are no longer accessible. Many people also link directly to other FOAF files that no longer exist. There is no attempt to remember data, nor merge it together. For instance, Dan Brickley knows Eric Miller, and you can then navigate to Eric's page (due to a rdfs:seeAlso link). Eric knows several people, including Dan Brickley. However, even though the system has access to the information that could take you back to Dan (for instance, his email) there has been no attempt to do so. Consequently, navigating my way around on the site kept taking me to dead ends.

FOAfnaut looked more promising, but I can't get it to respond to anything I do. I submitted my own file, and tried my email as a parameter in the URL, but to no avail. However, I've also found that the SVG on the page is very unresponsive anyway, and won't let me enter any text (though I can change tabs).

There are other sites, and other problems. It all looks very promising, and with great potential, but several of these sites were last edited in 2003, and appear abandoned. It's almost like FOAF proved a concept, and now everyone has moved onto new things. I'd suspect that the idea was dead, except that Danny is still talking about it.

In the meantime, I've gone to the trouble of putting it up, so I should add some more detail to my file. For instance, of the few people I have in there, I haven't made use of rdfs:seeAlso for any of them, so I should add that in. Then at least my link will look more interesting in FoaF Explorer.

Scaling Details

I have really wanted to record a lot of the details about scalability in Mulgara, but other commitments have conspired against me. I still don't have the time (it's nearly 1am and my head just ain't working right), but I wanted to get some of this information out there, so people know that it's actually real.

I got a couple of private requests to see this data, and so I put some of the details into point form (using Google Documents). This only gives the basic thrust of each item without giving useful details, but I thought it worth posting until I have the time to describe everything properly. A PDF of the document can be found on the Mulgara Wiki.

LinkedIn

After a recent spate of LinkedIn requests I decided to try expanding my own network. Apparently having a large number of connections is a good thing for one's long term career (or so a few pundits in IT have proclaimed), and it never hurts to look after that.

There's a note asking that you "Only invite people you know well and who know you", and until now I've stuck with that maxim. However, most of the invitations I've received in the past were from people I only knew through brief meetings or correspondence, stretching this guideline a little. Also, when requesting a link to a person, the LinkedIn site provides an option of "I don't know this person". So it seems that the requirement is observed more in the breaking than the observance.

I'm still trying to limit my list to people I've actually met, though there are one or two instances where I've simply conversed online (yes, I know you're reading this!). On the other hand, it could well be argued that I know some of those I've corresponded with better than those I've met in person. The end result is that within a week I went from about 5 connections to 30. This in turn made me realize that my profile was shockingly unrepresentative. After all, I filled it out in about 2 minutes when I was first invited to join. I'm still unhappy with it, but it's now a little more serviceable than it was.

I also invited Anne to join. Coming from industrial design and landscape architecture, she hasn't had as much luck finding people she knows, but she's still looking around. I can't imagine that it's penetrated her professional sphere yet, but once it does (if it does) then her connections should expand accordingly.

Twitter

Danny Ayers was the first to make me think about using Twitter, as he left a note implying that he is now posting tweets. This makes me imagine my mother asking, if Danny jumped off a cliff then would I jump too? Well, if it were Danny then I suppose I would. :-)

Twitter and micro-blogging have also been getting a lot of airplay recently by people referring to Web 2.0, not to mention a few of the Talking with Talis interviews, so I thought I'd check out what the fuss is about.

I tried browsing what strangers are doing at the moment, but I didn't find it particularly interesting. However, there was one post from someone at the Moscone Center that caught my attention, given that Apple's WWDC was on at the time (I'd love to go to this, but could never afford it). Guessing this guy must be involved in IT in some way, I added him to my list to see what he'd do. It didn't tell me much, but following the progress of an individual does have its charm. He was also kind enough to post a link to his blog, giving my some background on what he was doing, and why.

The real test of Twitter for me was whether I'd actually use it after signing up. I thought I'd try for a day or two and reassess at that point. The interface only allows for 140 characters, encouraging me to be brief, hence it didn't take much of my time. At the end of the first day I looked back at my log and realized that it was providing a reasonable breakdown of what I was doing during the day. Consequently, it appears useful for seeing how much time I devoted to certain activities, along with a reminder of just what I was doing and accomplished. My timesheet requirements at fourthcodex only involve a broad description for large blocks of time (as I'm doing internal development, and not customer billable work), but it looks quite useful for my own planning purposes, based on my path to a point, and how effective I was getting there.

I've been keeping at it, and even updated it with my phone a couple of times ("Going home"). Using the IM interface might be nice, but that service has been down since I first logged in. Twitter's technical support say they're working hard on getting that feature back up.

This may turn out like my blog: I started it for my own benefit, and thought that only my colleagues might read it. The idea was so they'd know what part of the code I was modifying, why I was modifying it, and the issues I had in the process. (I was inspired in this by John Carmack's .plan file, but I moved to a blog within a week or so). Since then, my blog has taken me to the other side of the world, and established some extraordinary contacts that I never expected.

This microblog seems to have a use for me as well. Perhaps if I keep it up, it too will evolve into something unexpected. If not, then at least it will help me fill in my timesheets.

Like LinkedIn, I pointed Anne at Twitter, and she now has an account as well. However, I suspect that she only uses it to see what time I'll be home from work. :-)

Linking Data

My LinkedIn flurry took me to a few blogs I hadn't followed before, including Dave Beckett (who is a rather infrequent poster). It's a few months old now, but I really liked his post on Webby Data.

A few weeks ago I mentioned that I think that too few people use RDF to link data together. Here Dave is pointing out that this is all the semantic web really is.

I initially came into this arena as an engineer trying to implement an efficient system for RDF, but not knowing much about the higher layers (RDFS/OWL, etc.). So for me, beyond describing structures, RDF was always about linking resources. Only later, when learning about OWL, and description logics in general, did I understand a lot of the underlying principles behind RDF, leading me to an understanding of what this concept of "semantics" was about.

But while all the academics are off working out how to best describe the world (and I wonder if I could be counted in that number) the real world has data everywhere that describes many of the same things, and yet that data is disconnected. This needs to be linked together in a web of information so that we all benefit, and it doesn't need fancy ontologies to do it. RDF provides a tool to do just this, and yet the central practitioners are all off working on another problem.

I'm not saying the domain of ontologies isn't valuable - I think that ultimately it's the way forward. But I also think it needs to be built on the web of information that we have the standards for, and yet have only just started to implement. This web is the Semantic Web (the semantics are few - but emergent), and "semantic technology" (like OWL) is the next stage that will take it forward. The former we can do today, while the latter is still being worked on (with some very useful results so far). I've noticed that many people lump the two together, and accord the deficiencies of the one still in development to both.

This is another case where I've recently discovered something that interests me, but only after it has been sitting on the web for months. I should be glad I'm catching up now, but it bugs me that it took so long to do it.

Description Logic Handbook

After relying on the PDFs of this book for years, I finally decided to bite the bullet and actually buy a copy. After all, I have to start my thesis soon, and PDFs are hard to read, while laser-printouts are awkward to sort through. So I went to Amazon to get one (along with some other things), only to be told that the book hasn't been published yet. This was confusing, until I realized that the second edition comes out next month.

I'm obviously not paying attention!