Multitasking

At the moment I feel like I have too many things on the boil. I'm regularly answering OSU/OSL about porting data over from Topaz and Mulgara, I'm supposed to be getting work done on SPARQL Update 1.1 (which suffered last week while I looked around for a way to stay in the USA), I'm trying to track down some unnecessary sorting that is being done by Mulgara queries in a Topaz configuration, I'm trying to catch up on reading (refreshing my memory on some important Semantic Web topics so that I keep nice and current), I'm trying to find a someone who can help us not get kicked out of the country (long story), I'm responding to requests on Mulgara, and when I have some spare time (in my evenings and weekends) I'm trying to make jSPARQLc look more impressive.

So how's it all going?

OSU/OSL

Well, OSU/OSL are responding slowly, which is frustrating, but also allows me the time to look at other things, so it's a mixed blessing. They keep losing my tickets, and then respond some time later apologizing for not getting back to me. However, they're not entirely at fault, as I have sudo access on out server, and could do some of this work for myself. The thing is that I've been avoiding the learning curves of Mailman and Trac porting while I have other stuff to be doing. All the same, we've made some progress lately, and I'm really hoping to switch the DNS over to the new servers in the next couple of days. Once that happens I'll be cutting an overdue release to Mulgara.

SPARQL Update 1.1

I really should have done some of this work already, but my job (and impending lack thereof) have interfered. Fortunately another editor has stepped up to help here, so with his help we should have it under control for the next publication round.

The biggest issues are:

1. Writing possible responses for each operation. In some cases this will simply be success/failure, but for others it will mean describing partial success. For instance, a long-running LOAD operation may have loaded 100,000 triples before failing. Most systems want that data to stay in there, and not roll back the change, and we need some way to report what has happened.
2. Dealing with an equivalent for FROM and FROM NAMED in INSERT/DELETE operations. Using FROM in a DELETE operation looks like this is the graph that you want to remove data from, whereas we really want to describe the list of graphs (and/or named graphs) that affect the WHERE clause. The last I read, the suggestion to use USING and USING NAMED instead was winning out. The problem is that no one really likes it, though they don't like every other suggestion even more. :-)

I doubt I'll get much done before the next meeting, but at least I did a little today, and I've been able to bring the other editor up to speed.

Sorting

This is a hassle that's been plaguing me for a while. A long time back PLoS complained about queries that were taking too long (like, up to 10 minutes!). After looking at them, I found that a lot of sorting of a lot of data was going on, so I investigated why.

From the outset, Mulgara adopted "Set Semantics". This meant that everything appeared only once. It made things a little harder to code, but it also made the algebra easier to work with. In order to accomplish this cleanly, each step in a query resolution removed duplicates. I wasn't there, so I don't know why the decision wasn't made to just leave it to the end. Maybe there was a good reason. Of course, in order to remove these duplicates, it had to order the data.

When SPARQL came along, the pragmatists pointed out that not having duplicates was a cost, and for many applications it didn't matter anyway. So they made duplicates allowable by default, and introduced the DISTINCT keyword to remove them if necessary, just like SQL. Mulgara didn't have this feature (though the Sesame-Mulgara bridge hacked it to work by selecting all variables across the bridge and projecting out the ones that weren't needed), but given the cost of this sorting, it was obvious we needed it.

The sorting in question came about because the query was a UNION between a number of product terms (or a disjunction of conjunctions). In order to make the UNION in order, each of the product terms was sorted first. Of course, without the sorting, a UNION can be a trivial operation, but with it the system was very slow. Actually, the query in question was more like a UNION between multiple products, with some of the product terms being UNIONS themselves. The resulting nested sorting was painful. Unfortunately, the way things stood, it was necessary, since there was no way to do a conjunction (product) without having the terms sorted, and since some of the terms could be UNIONS, then the result of a UNION had to be sorted.

The first thing I did was to factor the query out into a big UNION between terms (a sum-of-products). Then I manually executed each one to find out how long it took. After I added up all the times, the total was about 3 seconds, and most of that time was spent waiting for Lucene to respond (something I have no control over), so this was looking pretty good.

To make this work in a real query I had to make the factoring occur automatically, I had to remove the need to sort the output of a UNION, and I had to add a query syntax to TQL to turn this behavior on and off.

The syntax was already done for SPARQL, but PLoS were using TQL through Topaz. I know that a number of people use TQL, so I wasn't prepared to break the semantics of that language, which in turn meant that I couldn't introduce a DISTINCT keyword. After asking a couple of people, I eventually went with a new keyword of NONDISTINCT. I hate it, but it also seemed to be the best fit.

Next I did the factorization. Fortunately, Andrae had introduced a framework for modifying a query to a fixpoint, so I was able to add to that for my algebraic manipulation. I also looked at other expressions, like differences (which was only in TQL, but is about to become a part of SPARQL) and Optional joins (which were part of SPARQL, and came late into TQL). It turns out that there is a lot that you can do to expand a query to a sum-of-products (or as close to as possible), and fortunately it was easy to accomplish (thanks Andrae).

Finally, I put the code in to only do this factorization if a query was not supposed to be DISTINCT (the default in SPARQL, and if the new keyword is present for TQL). Unexpectedly, this ended up being the trickiest part. Part of the reason was because some UNION operations still needed to have the output sorted if they were embedded in an expression that couldn't be expanded out (a rare, though possible situation, but only when mixing with differences and optional joins).

I needed lots of tests to be sure that I'd done things correctly. I mean, this was a huge change to the query engine. If I'd got it wrong, it would be a serious issue. As a consequence, this code didn't get checked in and used in the timeframe that it ought to have. But finally, I felt it was correct, and I ran my 10 minute queries against the PLoS data.

Now the queries were running at a little over a minute. Well, this was an order of magnitude improvement, but still 30 times slower than I expected. What had happened? I checked where it was spending it's time, and it was still in a sort() method. Sigh. At a guess, I missed something in the code that allows sorting when needed, and avoids it the rest of the time.

Unfortunately, the time taken to get to that point had led to other things becoming important, and I didn't pursue the issue. Also, the only way to take advantage of this change was to update Topaz to use SELECT NONDISTINCT but that keyword was going to fail unless being run on a new Mulgara server. This meant that I couldn't update Topaz until I knew they'd moved to a newer Mulgara, and that didn't happen for a long time. Consequently, PLoS didn't see a performance change, and I ended up trying to improve other things for them rather than tracking it down. In retrospect, I confess that this was a huge mistake. PLoS recently reminded me of their speed issues with certain queries, but now they're looking at other solutions to it. Well, it's my fault that I didn't get it all going for them but that doesn't mean I should never do it, so I'm back at it again.

The problem queries only look really slow when executed against a large amount of data, so I had to get back to the PLoS dataset. The queries also meant running the Topaz setup, since they make use of the Topaz Lucene resolvers. So I updated Topaz and built the system.

Since I was going to work on Topaz, I figured I ought to add in the use of NONDISTINCT. This was trickier than I expected, since it looked like the Topaz code was not only trying to generate TQL code, it was also trying to re-parse it to do transformations on it. The parser in question was Antlr which is one that I've limited experience with, so I spent quite a bit of time trying to figure out what instances of SELECT could have a NONDISTINCT appended to it. In the end, I decided that all of the parsing was really for their own OQL language (which looks a lot like TQL). I hope I was right!

After spending way to long on Topaz, I took the latest updates from SVN, and compiled the Topaz version of Mulgara. Then I ran it to test where it was spending time in the query.

Unfortunately, I immediately started getting regular INFO messages of the form:

MulticastKeepaliveHeartbeatSender> Unexpected throwable in run thread. Continuing...null
java.lang.NullPointerException
 at net.sf.ehcache.distribution.MulticastKeepaliveHeartbeatSender$MulticastServerThread.createCachePeersPayload(MulticastKeepaliveHeartbeatSender.java:180)
 at net.sf.ehcache.distribution.MulticastKeepaliveHeartbeatSender$MulticastServerThread.run(MulticastKeepaliveHeartbeatSender.java:137)

Now Mulgara doesn't make use of ehcache at all. That's purely a Topaz thing, and my opinion to date has been that it's more trouble than it's worth. This is another example of it. I really don't know what could be going on here, but luckily I kept open the window where I updated the source from SVN, and I can see that someone has modified the class:

  org.topazproject.mulgara.resolver.CacheInvalidator

I can't guarantee that this is the problem, but I've never seen it before, and no other changes look related.

But by this point I'd reached the end of my day, so I decided I should come back to it in the morning (errr, maybe that will be after the SPARQL Working Group meeting).

Jetty

Despite that describing a good portion of my day (at least, those parts not spent in correspondence), I also got a few things done over the weekend. The first of these was a request for a new feature in the Mulgara Jetty configuration.

One of our users has been making heavy use of the REST API (yay! That time wasn't wasted after all!) and had found that Jetty was truncating their POST methods. It turns out that Jetty restricts this to 200,000 characters by default, and it wasn't enough for them. I do have to wonder what they're sticking in their queries, but OK. Or maybe they're POSTing RDF files to the server? That might explain it.

Jetty normally lets you define a lot of configuration with system parameters from the command line, or with an XML configuration file, and I was asked if I could allow either of those methods. Unfortunately, our embedded use of Jetty doesn't allow for either of these, but since I was shown exactly what was wanted I was able to track it down. A bit of 'grepping' for the system parameter showed me the class that gets affected. Then some Javadoc surfing took me to the appropriate interface (Context), and then I was able to go grepping through Mulgara's code. I found where we had access to these Contexts, and fortunately the Jetty configuration was located nearby. Up until this point Jetty's Contexts had not been configurable, but now they are. I only added in the field that had been requested, but everything is set up to add more with just two lines of code each - plus the XSD to describe the configuration in the configuration file.

jSPARQLc

My other weekend task was to add CONSTRUCT support to jSPARQLc. Sure, no one is using it yet, but Java needs so much boilerplate to make SPARQL work, that I figure it will be of use to someone eventually – possibly me. I'm also finding it to be a good learning experience for why JDBC is the wrong paradigm for SPARQL. I'm not too worried about that though, as the boilerplate stuff is all there, and it would be could easy to clean it up to something that doesn't try to conform to SPARQL. But for the moment it's trying to make SPARQL look like JDBC, and besides there's already another library that isn't trying to look like JDBC. I'd better stick to my niche.

I've decided that I'm definitely going to go with StAX to make forward-only result sets. However, I'm not sure if there is supposed to be a standard configuration for JDBC to set the desired form of the result set, so I haven't started on that yet.

The result of a CONSTRUCT is a graph. By default we can expect a RDF/XML document, though other formats are certainly possible. I'm not yet doing content negotiation with jSPARQLc, though that may need to be configurable, so I wanted to keep an open mind about what can be returned. That means that standard SELECT queries could return SPARQL Query Result XML or JSON, and CONSTRUCT queries could result in RDF/XML, N3, or RDF-JSON (Mulgara supports all but the last, but maybe I should add that one in. I've already left space for it).

Without content negotiation, I'm keeping to the XML formats for the moment, with the framework looking for the other formats (though it will report that the format is not handled). Initially I thought I might have to parse the top of the file, until I cursed myself for an idiot and looked up the content type in the header. Once the parameters have been removed, I could use the content type to do a "look up" for a parser constructor. I like this approach, since it means that any new content types I want to handle just become new entries in the look-up table.

This did leave me wondering if every SPARQL endpoint was going to fill in the Content-Type header, but I presume they will. I can always try a survey of servers once I get more features into the code.

Parsing an RDF/XML graph is a complex process that I had no desire to attempt (it could take all week to get it right - if not longer). Luckily, Jena has the ARP parser to do the job for me. However, the ARP parser is part of the main Jena jar, which seemed excessive to me. Fortunately, Jena's license is BSD, so it was possible to bring the ARP code in locally. I just had to update the packages to make sure it wouldn't conflict if anyone happens to have their own Jena in the classpath.

Funnily enough, while editing the ARP files (I'm doing this project "oldschool" with VIM). I discovered copyright notices for Plugged In Software. For anyone who doesn't know, Plugged In Software was the company that created the Tucana Knowledge Store (later to be open sourced as Kowari, then renamed to Mulgara). The company changed its name later on to match the software, but this code predated that. Looking at it, I seem to recall that the code in question was just a few bugfixes that Simon made. But it was still funny to see.

Once I had ARP installed, I could parse a graph, but into what? I'm not trying to run a triplestore here, just an API. So I reused an interface I came up with when I built my SPARQL test framework when I needed to read a graph. The interface isn't fully indexed, but it lets you do a lot of useful things if you want to navigate around a graph. For instance, it lets you ask for the list of properties on a subject, or to find the value(s) of a particular subject's property, or to construct a list from an RDF collection (usually an iterative operation). Thinking that I might also want to ask questions about particular objects (or even predicates) I've added in the other two indexes this time, but I'm in two minds about whether they really need to be there.

The original code for my graph interface was in Scala, and I was tempted to bring it in like this. But one of the purposes of this project was to be lightweight (unfortunately, I lost that advantage when I discovered that ARP needs Xerces), so I thought I should try to avoid the Scala JARs. Also, I thought that the exercise of bringing the Scala code into Java would refresh the API for me, as well as refresh me on Scala (which I haven't used for a couple of months). It did all of this, as well as having the effect of reminding me why Scala is so superior to Java.

Anyway, the project is getting some meat to it now, and it's been fun to work on in my evenings, and while I've been stuck indoors on my weekends. If anyone has any suggestions for it, then please feel free to let me know.

More Programmable Logic

In the last post I gave a basic description of how the Krule rules engine works. I left out a number of details, but it provides some details on the overall approach.

The most important detail I skipped was the interaction with resolvers in order to identify resources with particular properties. This includes among other things, finding URIs in a domain, inequality comparisons for numeric literals, regular expression matching on strings, the "type" of a resource (URI, blank node, or literal), and optimized transitivity of predicates. We also manage "subtractions" in our data, in the same way that Evren Sirin described NOT two weeks ago. I should point out that Mulgara does subtractions directly, and not with a combined operation with the OPTIONAL/FILTER/!BOUND pattern. This was introduced this in 2004 (or was it 2005?). I have to say that I'm a little surprised that SPARQL never included anything to express it directly, particularly since so many people ask for it (and hence, the popularization of OPTIONAL/FILTER/!BOUND as a pattern) and because the SPARQL algebra provides a definition of a function called "Diff" that is used internally.

Anyway, these extensions are not necessary to understand Krule or RLog, but I think it's useful to know that they're there.

So now that I've described Krule, I've set the scene for describing RLog.

Krule Configuration

When I first wrote Krule, I was ultimately aiming at OWL, but I had a short term goal of RDFS. I find that I have to take these things one step at a time, or else I never make progress. Since I knew that my rules were going to expand, I figured I should not hard code anything into Mulgara, but that I should instead interpret a data structure which described the rules. That also meant I would be able to run rules for lots of systems: RDFS, SKOS, OWL, or anything else. Of course, some things would need more features than RDFS needed (e.g. both OWL and SKOS need "lists"), but my plan was to work on that iteratively.

At the time, I designed an RDF schema to describe my rules, and built the Krule engine to initialize itself from this. This works well, since the whole system is built around RDF already. I also created a new TQL command for applying rules to data:

  apply <rule_graph_uri> to <data_graph_uri> [<output_graph_uri>]

By default all of the entailed data goes into the graph the rules are being applied to, but by including the optional output graph you can send the entailed data there instead.

This worked as planned, and I was able to build a Krule configuration graph for RDFS. Then life and work interfered and the rules engine was put on the back burner before I got to add some of the required features (like consistency checking).

Then about 18 months ago I thought I'd have a go at writing OWL entailment, at least for that part that the rules engine would support. So I set out to write a new Krule file. The complexity of the file was such that I started writing out the rules that I wanted using a kind of Prolog notation with second order programming, in a very similar way to how Raphael Volz represented the same constructs in some of his papers. This grammar uses binary predicates to represent genereal triples, and unary predicates to indicate "type" statements, ie. statements with a predicate of rdf:type. As an example, the owl:sameAs predicate indicates that if the subject of a statement is the owl:sameAs another resource, then that statement can be duplicated with the other resource as the subject. This was easily expressed this as:

  A(Y,Z) :- A(X,Z), owl:sameAs(X,Y).

I wrote out about 3 rules before I realized that converting these to Krule was going to be tedious and prone to error. In fact, I had unthinkingly demonstrated that I already had a language I wanted to use, and the process of translation was an easily automated task. Since the language was allowing me to describe RDF with logic, I decided to call it RLog (for RDF Logic).

Iterations

Andrae and I had been discussing how much we disliked SableCC for generating the TQL parser for Mulgara, and so I started looking around at other parsers. The power of LALR parsers appealed to me, and so I went with Beaver. Along with the JFlex lexer, this software is a pleasure to use. I had learned how to use them both, and created the RLog grammar in about an hour. I then converted the Krule configuration for RDFS into this new grammar, and convinced myself that I had it right. Then life got in the way again, and I put it away.

Last year while waiting for some tests to complete, I remembered this grammar, and spent some of my enforced downtime making it output some useful RDF in the Krule schema. For anyone who's looked at Krule, they may have noticed that triggers for rules (which rules cause which other rules to be run) are explicitly encoded into the configuration. I did this partly because I already had the list of trigger dependencies for RDFS rules, and partly because I thought it would offer more flexibility. However, I had realized some time before that these dependencies were easy to work out, and had been wanting to automate this. I decided that RLog was the perfect place to do it, partly because it meant not having to change much, but also because it still allowed me the flexibility of tweaking the configuration.

Once I'd finished writing a system that could output Krule, I tested it against my RDFS RLog file, and compared the generated Krule to the original configuration. Initially I was disappointed to see to many dependencies, but on closer inspection I realized that they were all valid. The original dependencies were a reduced set because they applied some of the semantics of the predicates and classes they were describing, which was not something that a grammar at the level of RLog could deal with. Semi-naïve evaluation was going to stop unnecessary rules from running anyway, so I decided that these extra triggers were fine. I ran it against the various test graphs that I had, and was pleased to see that it all worked perfectly.

But once again, work and life got in the way, and I put it aside again.

SKOS

A couple of months ago Brian asked me about running rules for generating SKOS entailments, as he was writing a paper on this topic. I pointed him towards RLog and knocked up a couple of useful rules for him. However, as I got into it, I realized that I could actually do most of SKOS quite easily, and before I knew it, I'd written an entire RLog program for it. The only thing I could not do was "S35", as this requires a predicate for list membership (also a requirement for OWL, and on my TODO list).

The really interesting thing about this document, is that almost everything is an axiom and not a rule. It only requires 2 RDFS rules and 5 OWL rules to make the whole thing work. This is quite important, as the complexity in running the rules is generally exponential in the number of rules.

This is (IMNSHO) the power of ontologies. By providing properties of classes and properties, they reduce the need for many rules. To demonstrate what I mean, I've seen a few systems (such as DLV) which define a predicate to be transitive in the following way:

  pred(A,C) :- pred(A,B), pred(B,C).

This works, but it creates a new rule to do it. Every new transitive predicate also gets its own rule. As I have already said, this has a significant detrimental effect on complexity.

Conversely, models such as OWL are able to declare properties as "transitive". Each such declaration then becomes a statement rather than a rule. Indeed, all the transitive statements get covered with a single second-order rule:

  P(A,C) :- P(A,B), P(B,C), owl:TransitivePredicate(P).

"Second-order" refers to the fact that variables can be used for the predicates (such as the variable P in the expression P(A,B)), and that predicates can appear as parameters for other predicates, such as owl:TransitivePredicate(...). The symmetry of Mulgara indexes for RDF statements allows such second order constructs to be evaluated trivially.

Using the OWL construct for transitivity, any number of predicates can be declared as transitive with no increase to the number of rules. The complexity of rules does have a component derived from the number of statements, but this is closer to linear or polynomial (depending on the specific structure of the rules), and is therefore far less significant for large systems. It is also worth noting that several OWL constructs do not need an exhaustive set of their own rules, as their properties can be described using other OWL constructs. For instance, owl:sameAs is declared as being owl:SymmetricProperty. This means that the entailment rule for owl:sameAs (shown above) need only be written once for owl:sameAs(A,B) and is not needed for symmetric case of owl:sameAs(B,A).

General Acceptance

Brian wasn't the only one to like RLog. I've had reports and feature requests from a few other people who like using it as well. The most commonly requested feature has been the generation of blank nodes. The main reason for this is to handle existential formula, which makes me wary, as this can lead to infinite loops if not carefully controlled. On the other hand, I can see the usefulness of it, so I expect to implement it eventually.

A related feature is to create multiple statements based on a single matched rule. This can usually be handled by introducing a new rule with the same body and a different head, but if a blank node has been generated by the rule, then there needs to be some way to re-use it in the same context.

A problem with general usage is that the domains understood by RLog have been preset with the domains that I've wanted, namely: RDF, RDFS, OWL, XSD, MULGARA, KRULE, FOAF, SKOS, and DC. The fix to this can be isolated in the parser, so I anticipate this being fixed by Monday. :-)

Despite it being limited, RLog was proving to be useful, allowing me to encode systems like SKOS very easily. However, being a separate program that translated an RLog file into Krule configuration files that then had to be loaded and applied to data, was a serious impediment to the usage.

Integration

The Mulgara "Content Handler" interface is a mechanism for loading any kind of data as triples, and optionally writing it back out. The two main ones are the RDF/XML handler and the N3 handler, but there are others in the default distribution as well. There is a MBox handler for representing Unix Mailbox files as RDF, and an MP3 handler which maps ID3 metadata from MP3 files. These handlers compliment the "Resolver" interface which represents external data sources as a dynamic graph.

Since RLog has a well-defined mapping into RDF (something the RLog program was already doing when it emitted RDF/XML) then reimplementing this system as a content handler would integrate it into Mulgara with minimal effort. I had been planning on this for some time, but there always seemed to be more pressing priorities. These other priorities are still there (and still pressing!) but a few people (e.g. David) have been pushing me for it recently, so I decided to bite the bullet and get it done.

The first problem was that the parser was in Beaver. This is yet another JAR file to include at a time when I'm trying to cut down on our plethora of libraries. It also seemed excessive, since we already have both JavaCC and SableCC in our system - the former for SPARQL, the latter for TQL, and I hope to redo TQL in JavaCC eventually anyway. So I decided to re-implement the grammar parser in JavaCC.

Unfortunately, it's been over a year since I looked at JavaCC, and I was very rusty. So my first few hours were spent relearning token lookahead, and various aspects of JavaCC grammar files. I actually think I know it better now than I did when I first did the SPARQL parser (that's a concern). There are a few parts of the grammar which are not LL(1) either, which forced me to think through the structure more carefully, and I think I benefited from the effort.

I was concerned that I would need to reimplement a lot of the AST for RLog, but fortunately this was not the case. Once I got a handle on the translation it all went pretty smoothly, and the JavaCC parser was working identically to the original Beaver parser by the end of the first day.

After the parser was under control I moved on to emitting triples. This was when I was reminded that writing RDF/XML can actually be a lot easier than writing raw triples. I ended up making slow progress, but I finally got it done last night.

Testing

Before running a program through the content handler for the first time, I wanted to see that the data looked as I expected it to. JUnit tests are going to take some time to write, and with so much framework around the rules configuration, it was going to be clear very quickly if things weren't just right. I considered running it all through the debugger, but that was going to drown me in a sea of RDF nodes. That was when I decided that I could make the resolver/content-handler interfaces work for me.

Mulgara can't usually tell the difference between data in its own storage, and data sourced from elsewhere. It always opts for internal storage first, but if a graph URI is not found, then it will ask the various handlers if they know what to do with the graph. By using a file: URL for the graphs, I could make Mulgara do all of it's reading and writing to files, using the content handlers to do the I/O. In this case, I decided to "export" my RLog graph to an N3 file, and compare the result to an original Krule RDF/XML file that I exported to another N3 file.

The TQL command for this was:

  export <file:/path/rdfs.rlog> to <file:/path/rlog-output.n3>

Similarly, for the RDF/XML file was transformed to N3 with:

  export <file:/path/rdfs-krule.rdf> to <file:/path/krule-output.n3>

I love it when I can glue arbitrary things together and it all "just works". (This may explain why I like the Semantic Web).

My first test run demonstrated that I was allowing an extra # into my URIs, and then I discovered that I'd fiddled with the literal token parsing, and was now including quotes in my strings (oops). These were trivial fixes. The third time through was the charm. I spent some time sorting my N3 files before deciding it looked practically identical, and so off I went to run an RLog program directly.

As I mentioned in my last post, applying a set of rules to data is done with the apply command. While I could have loaded the rules into an internal graph (pre-compiling them, so to speak) I was keen to "run" my program straight from the source:

  apply <file:/path/rdfs.rlog> to <test:data:uri>

...and whaddaya know? It worked. :-)

Now I have a long list of features to add, optimizations to make, bugs to fix, and all while trying to stay on top of the other unrelated parts of the system. Possibly even more importantly, I need to document how to write an RLog file! But for the moment I'm pretty happy about it, and I'm going to take it easy for the weekend. See you all on Monday!

SPARQL

Perpetual coding doesn't leave much time for blogging. I'm in the middle of a long-running set of tests, so I figured I should take the time to write, even if I'm too tired. :-)

SPARQL on Mulgara always seems to have more to do than I have time or mandate for. That should be OK, given that SPARQL is now available through the SAIL API, but it's never quite that simple.

To properly work with Sesame/SAIL we need to build (or at least deploy) Mulgara using Maven. Now I understand what Maven does... I've just never used it. On top of that, we have the horrible build scripts that go into Mulgara, making the whole notion of re-creating the build system a little daunting. All the same, I've learned about creating a pom.xml, along with modules and inheritance, but I still need to read more docs on the topic. I'd like to get to this soon, but there are so many other pressing things.

So working with SAIL isn't an out-of-the-box distribution yet, which is an impediment to using SPARQL. At this stage I think the Mulgara SAIL API is more of an advantage to Sesame than it is to us. Another reason why it would be good to get SPARQL going is because people are always asking me for it. So even if I don't get 100% conformance, I should try to get it close. Anyone who needs it perfect can use the SAIL API.

Web Services

The best way to get SPARQL compliance is to run the test suite. That means you need some way to issue the queries and check the results. Now, I could write the code to do this, but I know that other systems for running the test suite exist out there, and it would be better to use one of those if I could. However, those systems will all be using the SPARQL protocol for issuing queries, and that's one part I hadn't really touched yet.

Fortunately, the protocol is just a web service, and Mulgara is already running web services. The response is just in XML, and I've written some code to do that already (though it's not checked in anywhere yet). I just need to glue it to a web service.

Looking at it, the protocol is so simple that the service should be implementable with a relatively straightforward servlet. Servlets are quite easy to write, but deploying them is system dependent, so I thought I'd get the deployment part going first. I built a simple "hello world" servlet with the intent of expanding it into the real thing once it was integrated correctly.

Servlets

To start with, I followed the directions given for deploying a servlet in the Quick Start guide, and it all worked fine. Then I went to Mulgara to see how this would work.

Now I'd been aware that Jetty hadn't been updated in Mulgara for a while, and I thought that this would be a good chance to update it. However the existing version was 4.2.19, while the latest (released) version is 6.1.19. Some of the APIs appeared to be completely incompatible, and while there was an upgrade guide from Jetty 5 to Jetty 6, there was nothing about Jetty 4. Obviously this task had been left for too long.

So the first order of the day was not to get a servlet deployed in Mulgara, but rather to upgrade Mulgara to use the latest Jetty. This also dovetailed with another task I've been wanting to do for some time, which was to clean up the file where all of the Jetty configuration happens: EmbeddedMulgaraServer.

Upgrade

I eventually want to completely remove EmbeddedMulgaraServer and replace it with a lightweight program that loads up configurable modules. This will give us the benefits of having those modules ready for other types of deployment (another request I often get) as well as letting people customize the server, which is currently monolithic and unwieldy. I don't have time to get all of that done right now, but at least I got to tidy the code up to the point where this will be less intimidating. It also gave me a better view of what was going on in there (it regularly confuses developers who look at it).

Mulgara had been deploying two sets of static pages and 2 web services in Jetty. The static pages included the documentation that is both obsolete (to be replaced by the gradually expanding Wiki), and available on the website. The other pages are all data files, which I believe are used for example scripts. I think it's a terrible idea to have these in the system, so I ripped them out. Moments later I thought better of it, and so I emailed the list to see what people thought. I was bemused to see that not only was this a welcome move, people wanted to get rid of the HTTP server altogether! (These people obviously want to access those individual modules I mentioned earlier). So then I created both an option in the config file, and a system property which can both disable the server (the system property takes precedence).

That just left me with the 2 web applications in Web ARchive files to deploy. This is where I came unstuck.

WAR Files

I could not find any documentation on how to deploy a WAR file using the APIs in Jetty. So I muddled through the JavaDocs, picking up anything that looked promising. After an entire night of this, I eventually got something I thought might work, replacing WebApplicationContext class with the WebAppContext and trying to translate the differences in their APIs. I immediately got back an IllegalStateException that occurred while the system was accessing the WAR file. While trying to work it out I delved into the Java libraries, and discovered that something had closed off the archive file while it was still in the process of reading it. It seemed too far down in the system to be anything I could have caused (or prevented), so I went searching online to see if anyone knew about it.

It didn't take me long to see people mentioning this bug in relation to Jetty 5 about 2 years ago. It seemed strange that there wouldn't be a more recent reference, but that was the best I could get. Unfortunately, the response at the time was that the problem was indeed a bug with some of the Apache libraries that were used for this, which meant I was out of luck (sure, I could fix it, but that won't get me a deployed version of those libs any time soon).

I saw Brian online (apparently traveling as a passenger in a car) and he told me that he'd heard of the problem, and suggested that I "expand" the archive to deploy it. I did this by manually pulling the WAR files into a temporary directory before pointing the WebAppContext at it. This avoided the IllegalStateException.

Class Paths

The deployment of these WAR files into Jetty 4 had a few things that didn't translate so well. The first was the configuration of something called a SocketListener, which I figured out was replaced a Connector. The second was in setting up the class paths. The code for this used to be:

  HttpContext contexts[] = httpServer.getContexts();
  for (int i = 0; i < contexts.length; i++) {
    contexts[i].setParentClassLoader(this.getClass().getClassLoader());
  }

This seemed reasonable, though I wasn't sure why it was being done. I was about to learn.

Jetty 6 no longer has the Context.setParentClassLoader() method, though it is now possible to set the actual class loader for the context. However, the class loader I had available in that context (this.getClass().getClassLoader()) was the same one that was already being used by that class. So I wasn't sure what to replace this with. Unfortunately, I made the mistake of choosing to set the class loader here anyway.

When I tried running the program again, I was immediately being told of missing classes. Of course, neither these classes, nor any code for them existed on my system. I eventually worked out that these were classes that were generated from Java Servlet Pages (JSPs), which took me into the configuration for generating these pages.

I hadn't realized we had JSPs in the system (will the cruft never end?!?) and I'd eventually like to get rid of these, even if I keep the web applications they're a part of. But for the moment, I had to upgrade those libs, and then update various build scripts which were trying to refer to the libs by name, and not with a generic variable (which we do for everything else - this lets us change versions relatively easily). I also discovered a "Tag" library for accessing Mulgara from JSPs. We don't seem to use it anywhere ourselves, and it just seems to be provided as a utility for users. The presence of this has me feeling reluctant to remove JSPs, but I'm still considering it.

Embedded JARs

Once the JSPs were running, I started getting errors about missing libraries that I expected were already in the class path. However, when I checked, I found that those libraries had NOT been included. It used to work, so I kept searching, and it didn't take me long to find them in the WAR file.

So this was the reason for the fancy classloader stuff. The classloader was supposed to find these JARs in the WAR file, and include them in its search. Only there was no such class loader in place. Hence my error.

The Javadoc mentions a class called WebAppClassLoader, which looked like an obvious candidate. However, the documentation made it appear that this class may not do very much, as it just extended the standard library class URLClassLoader. All the same, I tried it, but it didn't seem to do anything. (This was my big mistake).

I finally started adding the sources for all my libraries into my Eclipse environment, so I could debug it and see exactly what was happening. While time-consuming, it finally got me over the line. I also had a nice side benefit of learning just how the architecture of Jetty 6 works.

Deployed At Last

Tracing through the program, I found that a WebAppContext calls configureClassLoader on a WebInfConfiguration that it creates. This explicitly checks if the class loader is a WebAppClassLoader, and if it is, then it goes through the lib/ directory of the application, and adds any JAR files that it finds into its classpath.

Since the configuration is checking for this specific class loader, then this is obviously the only way to do it, unless you write a class loader for yourself. The application never creates one for you, which seems strange. The creation of the object is also strange in that it needs to be provided the web application that it works on (so it knows where to find the classes and libs), and it has to be explicitly set as the class loader for that application. So you need to say something like:

  webapp.setClassLoader(new WebAppClassLoader(webapp));

I'm confused why WebAppContext doesn't create automatically create a WebAppClassLoader for itself, giving it a this reference. You can always override it, but it would be rare to need to.

Anyway, I now knew what to do, and so I did it. Of course, it still didn't work. More debugging. That was when I ran headlong into that class loader code I wrote back at the start of this process. After setting the class loader for the WebAppContext this code was setting it back to the normal system class loader. That'll teach me for including code blindly.

Threads

So now everything was running "error free". I decided to throw a web browser at the WebUI application. Only, it wouldn't respond at all. I got a connection to the server, but it just sat there doing nothing.

Finally, I tried duplicating what I was doing in a short application using a simple servlet. It all looked OK, so I wen through step by step, making sure I had it exactly the same... and it locked up there too. So then I started changing settings one at a time until I found the one that was causing the problem.

On Jetty 4, two of the options we were setting on the SocketListener were minThreads and maxThreads, however neither of these were options for Connector. So I decided to make do with AbstractConnector.setAcceptors(int), which does a similar thing. However, I made the mistake of setting the number of acceptors to our previous madThreads value, which was 255.

If the number of acceptors is set this high, then the server is guaranteed to lock up. So I looked for the threshold at this this occurred. It turned out that the maximum value I could use was 24. It consistently works fine right up to this level, but any more and the system just blocks indefinitely. I checked out the source code, and discovered that all the acceptors are Runnable objects that get invoked by threads in a thread pool, but there is nothing about the size of that pool or anything else I could see that would create this limit of 24.

It also doesn't seem to matter what kind of Connector I'm using either, as the Acceptors are always the same.

A New Servlet

I'm finally at a point where the system works as well as it did at the beginning of the week, only now it's doing it with Jetty 6. It needed to happen, but I wish it hadn't been so painful.

I have other things to get to now, but I'll be trying to write this new SPARQL servlet soon. At least I have a modern framework to do it with now.

Mulgara Alpha

My last few weeks were spent trying to get Mulgara's SPARQL interfaces ready before the Semantic Technology Conference 2008. I met the criteria Amit (from Topaz) and I had agreed to beforehand, which allowed me to get out an Alpha release for the next version of Mulgara. There are still a couple of things missing, but the basics are all there now.

The road to SPARQL took a couple of turns I hadn't expected.

Back in February we were approached by Aduna who asked if we would be willing to support a level of integration between Sesame and Mulgara. While none of the Mulgara developers had the time to work with them directly, we said that we would be very happy to try to support Aduna where we could. The majority of this work was done by James Leigh (a programmer who commands my respect more and more on a daily basis), and he was able to get it all done in remarkable time. Even more impressive was that his integration work is 100% SPARQL compliant, even though some of the underlying structure isn't quite there yet!

My own work was to:

• Parse SPARQL queries.
• Convert this into the Mulgara Algebra.
• Write new algebraic operations in the Mulgara query engine.

The work by Aduna was going to overcome the need for the first and second tasks, but I had already completed the first when we heard from Aduna, with most of the work left to be done required for both the SAIL interface and my own SPARQL implementation. Since this was the case, I decided to continue with my own interface, since there wasn't going to be much redundant work from that point onwards. Even with both interfaces working correctly, the SAIL API will be the one to use, as it also includes a SPARQL Protocol endpoint, which I haven't looked at yet.

While the SAIL integration may have appeared to be independent from my own work, it turned out that James's contribution was invaluable. His need to pass all the SPARQL tests drove a lot of my query engine work, pointing out both missing features and bugs I was unaware of. I still have a couple of things to go, but James has been able to work around them at the higher layers for the time being. This has a performance penalty, but these will be dealt with in the next couple of weeks.

Notable Feature Implementations

Language Tags

One missing feature that completely floored me was that Mulgara was not supporting language tags on untyped literals. It turns out that this was slated for addition just as Tucana was closed, which is why it never made it. Even so, I must admit that I was surprised that it took that long for this feature to be scheduled!

Fortunately, language tags were quick and easy to implement. The main issue was in the existing tests, as nearly half of our files use literals with language tags in them, and none of the "expected results" included them.

Repeating Variables

Another issue was in "basic graph patterns" that use a repeating variable. Mulgara already had some code to deal with this, but it was failing in most cases. Unfortunately, I responded to this as a "bug report", and fell into the trap of fixing the existing code. I got it working after a day, only to be told the next day that it still failed if the variable is repeated in the position of the graph name.

At that point I stepped back from the problem, and realized that the solution was actually quite easy. All you need do is replace the repeating variable with a set of unique names, and create a conjunction of the constraint repeated with the variables in rotating positions. After mentioning this to Andrae he informed me that he'd worked this out a few years before (even though someone else was implementing the code at the time), but he forgot to let me know. Oh well, at least I'm doing it correctly now.

While looking to implement this fix, I realized that the best way to perform this substitution would be via Andrae's query transformation SPI. This lets you search through a query structure, and replace elements with something more appropriate for the engine to work with. It was while working with this I realized that it provides me with a tool that will let me solve a problem I've had for some time.

Transitive

The trans feature in Mulgara is a mechanism that lets the user mark the predicate in a constraint as transitive. While it works really well, the syntax in TQL is ugly. However, the query transformer offers an alternative. Instead of wrapping a standard constraint in a trans(...) operator, the predicate can be typed as being transitive in a separate constraint. I was tempted to use the URI of owl:TransitivePredicate for this task, but this will interfere with declarations in ontologies, so a local URI will be much more appropriate (something like mulgara:TransitivePredicate). The really cool thing is that this will be sharable with SPARQL queries as well. That means we can start opening some of our functionality up to SPARQL users, while not needing to extend the syntax of that language. In fact, there are a few functions we can implement in this way, allowing us to do a lot in SPARQL without sacrificing the speed and functionality of TQL.

Date Times

One question I regularly received from James was about date times. Unfortunately, Mulgara stores these canonically (using UTC), and hence does not round-trip these values. The solution is to store the timezone offset along with the value. Another tricky thing is to record if a time of "midnight" is recorded as "00:00:00" or as "24:00:00", as both are valid, and both need to be returned as they were provided, and not in a normalized form. I haven't done this one yet, but I expect to get it done by the end of the week.

I had a comment from Andy Seaborne that despite timezones being described in hours and minutes, this only requires a resolution of quarter-hour intervals, so I can probably squeeze this into some existing storage somewhere. I appreciate the advice, but it leaves me wondering which timezone appears with a 15 minute offset from its nearest neighbors!

In the meantime, James got around the problem by removing the xsd:dateTime specific code from the version of Mulgara he is working with, so it gets treated as an unknown type. This modification can be removed as soon as I fix the issue (which I expect to be by the end of this week).

Memorial Day

There is still an enormous amount of information to cover on Mulgara, SPARQL, and especially the SemTech conference, but I'm falling asleep as I type. It's currently Memorial Day here in the USA, and since getting back from the conference on Friday night, I've had a huge weekend with my family. Yesterday I took both of the boys in a trailer for "Bike the Drive", which is a lot more cycling than I've done for a few months. Swimming and running have kept me relatively fit, but it still tired me out! Consequently I just can't think now, so I'll pick this up again later.

Indexing

I'm in the process of writing a number of things up at the moment, including the following description of RDF storage. But since academic papers take so long to write, and they're boring, I thought I'd blog the main bit of one of the things I'm writing about.

This all came about due to a description I wrote a few years ago about the number of columns needed to store data that was N columns wide. (Wow! Is it really 4 years?) It came down to a process and equation, of finding the minimum value of an expression, as S varies from 1 to N:

minS=1..N (N!/(N-S)!S!)

This gives a result of 3 indices for symmetrically storing triples, 6 indices for quads, 10 indices for quintuples, and so on. Note that this is the number of indices needed if you want to be able to use any search criteria on your tuples. This may indeed be the case for triples and quads, but if an element of the tuple becomes a unique ID (like it does for reification), then there is no need for symmetric indexing.

The rapid growth of this equation is a clear indicator that we want to keep the number of columns as low as possible. For expediency Mulgara moved from 3 columns to 4, so that we could encode graph identifiers with the triples, but that came at the expense of doubling the number of indices. This is really a big deal, as each index in Mulgara takes several files for managing the resources in the index, and for holding the index itself. Each piece of information that has to be read or written means another disk seek. This can be mitigated by read and write-back caching by the operating system, but as the amount of data exceeds what can be handled in memory, then these benefits evaporate. So keeping the number of indices down is a big deal.

Ronald Brachman's work in '77 shaped the future direction of description logics, including the use of the idea that everything can be represented using binary and unary predicates. RDF is defined using binary predicates, and unary predicates are simulated using the rdf:type predicate, which means that RDF is inherently capable of representing description logics, and indeed, any kind of knowledge representation. The issue is that it can be inefficient to represent certain kinds of structures.

The RDF representation of reification requires 3 statements for reification (plus one that can be inferred) and these are independent of the actual statement itself. An extra column can eliminate these 3 statements altogether, but the indexes grow accordingly. Graph membership can be accomplished using extra statements as well, and again, this can be trivially eliminated with an extra column. The question is, when do the extra columns (with the consequent factorial growth) become more expensive than adding in more statements? Should the number of indices be limited to 4? To 3?

2 Columns

I always found it interesting that the equation above has a solution for N=2. I considered this to be an artifact of the equation, but it bugged me all the same. So then a couple of years ago I gave it some thought, and realized that it is indeed possible to represent a triple using "doubles". Of course, once a triple can be represented, then anything can be represented. The question is efficiency.

If the indices were to contain only 2 columns, then this means that only unary predicates could be used. This implies that the predicates define a type. After some thought I realized that I could use unique types to identify each element of an RDF statement, and then a unique type to represent the statement itself. Of course, there is nothing new under the sun, and just recently I discovered that the CLASSIC system introduced unique atomic concepts for each individual in the system in a similar way.

To map the following triple:

  <my:subject> <my:predicate> <my:object<

to unary predicates, I used a scheme like the following:

  Statement(_statement_x)
  SubjectIdentifier(_subject_x)
  PredicateIdentifier(_predicate_x)
  ObjectIdentifier(_object_x)
  _statement_x(_subject_x)
  _statement_x(_predicate_x)
  _statement_x(_object_x)
  _subject_x(my:subject)
  _predicate_x(my:predicate)
  _object_x(my:object)

Where each of _statement_x, _subject_x, _predicate_x and _object_x are unique identifiers, never to be used again. In fact, my use of underscores as a prefix here indicates that I was thinking of them as a kind of blank node: unique, but without a distinguishing label.

When I first came up with this scheme, I thought it a curiosity, but hardly useful. It seemed that significant work would need to be done to reconstruct a triple, and indexing so many items would require a lot of seeking on disk. I was also concerned about the "reckless" use of the address space for identifiers in creating unique IDs for so many elements.

Then recently I was describing this scheme to a friend, and I realized that when I considered some other ideas I'd been working on lately, then there was something to this scheme after all.

Disk Seeking

I've been very disappointed with Mulgara's loading speed on certain types of data recently. If the data has a lot of unique URIs and strings, then the size of the store was getting too large, and the length of time taken to store the data was too long. I was also surprised at the gigabytes of file storage being used when the data files were only a few hundred megabytes. Mulgara is supposed to be scalable, and this wasn't acceptable behavior.

Consequently, I've been doing more work with algorithms and data structures recently. I have not been trying to supplant Andrae's work but was instead hoping to tweak the existing system a little in order to improve performance.

The first thing that becomes apparent is that the plethora of files in Mulgara is a real bottleneck. Each file on its own may be efficient (not all are), but cumulatively they cause a disk to seek all over the place. Since this is probably the single most expensive action a computer can take (other than a network request), then reducing the seeks is a priority.

Profiling the code led to a couple of improvements (these have been rolled into the Mulgara 1.2 release), but also showed that the biggest issue is the String Pool (more properly called the "Data Pool" since it now stores any kind of data). This is a facility that maps any kind of data (like a URI or a string) to a unique number, and maps numbers into the data they represent. With a facility like this, Mulgara is able to store triples (or quads) as groups of numbers. We call these numbers "Graph Nodes", or gNodes.

The string pool was spending a lot of time just searching to see if a URI or string to be inserted into the graph was already mapped to a number, and inserted it if not. Some work was also being done to keep track of what had been allocated in a given transaction phase, so that any allocated resources (like disk blocks) could be freed and reallocated if the data were ever removed. However, items are rarely removed from the string pool. Removals mostly occur when an entire graph is dropped, and these graphs are often dropped just before a slightly modified version of the same data is to be inserted. In this case, the same data will be removed from the string pool, and then re-inserted. That's a lot of work for nothing. It makes much more sense to leave everything in the string pool, and only remove unused items when explicitly requested, or perhaps as a background task. (Unused items can be easily identified since they don't exist in the statement indices).

If the string pool were changed to be a write-once-read-many pool, then a lot of the structures that support resource reuse (Free Lists, which are a few files each) can be removed from the string pool. Of course, the reduced reading/writing involved with removing and re-inserting data would also benefit. So this looked promising.

Another idea is to take any data that fits into less than 64 bits (say, 58 bits) and store it directly in the ID number instead of in the pool. The top bits can then indicate the type of the value, and whether or not it is "stored" or if it is simply encoded in the ID. This covers a surprising range of required numbers, and most dates as well. This idea was mentioned to me in SF last year, and it sounded good, only I had completely forgotten that Andrae had already proposed it a year before (sorry Peter, you weren't first). But wherever the idea came from, it promised to dramatically help dates and numbers. In fact, it helps all the data, since the tree no longer has as many elements stored in it.

There were also other ideas, such as moving the tree type of the index. We mitigated the use of AVL trees in the indices by using pointers to large blocks of data. However, this becomes a subtraction of a constant in the complexity analysis, while a wider tree becomes a division by a constant. Constants don't usually mean much in complexity analysis, but when each operation represents a disk seek, then the difference becomes significant. While this is something that must be looked at, it didn't make sense when we knew that XA2 is coming, and that the trees will change anyway.

Address Space

You may have noticed that I'm talking a lot about resource reallocation, and 64 bits in the same breath. This shows some of the history of Mulgara. The system originally ran on 32 bits, where not reusing resources was a guaranteed way to wrap around in the number space and cause no end of problems. When the system was upgraded to 64 bits, it still made sense to manage resources for reallocation, as some resources were still limited. However, resources that represented IDs in an address space were not reconsidered, and they ought to have been. Looking at what literals could be encoded in a 64 bit value (and how many bits should be reserved for type data) was the impetus I needed to make me look at this again.

Given that every resource we allocated took a finite time that was often bounded by disk seeks, it occurred to me that we were not going to run out of IDs. If we only used 58 bits, then we could still allocate a new resource every microsecond and not run out of IDs for over 9000 years. A more reasonable design period is 100 years (yes, this is a wide margin of safety), and constant allocation of resources at a microsecond per resource means that we still only need 52 bits. So we're safe not reusing IDs, and indeed, we have over a byte of information we can use in this ID to do some interesting engineering tricks.

Structure

So I had a number of these lessons fresh in mind when I recently tried to describe just why a 2 column store was inefficient. During the course of the conversation I started seeing ways in which I could apply some of these techniques in a useful way. It took a while for it to come together, but I now have something that really shows some promise.

The details here are reasonably detailed, so it makes sense to take a break here, and write it all up in a fresh post in the next day or so. A little more sleep might also help prevent the rambling that I've noticed coming into this post. :-)

Review

You know you've been lax keeping up with your blog when your mother comments that you haven't updated it in a while.

Part of the reason for my silence has been due to a lot of changes going on for me lately, some of which I was obliged to keep quiet about at the time. More recently, I've been working hard on Mulgara, and when it's come to a choice between coding or blogging, then coding had a higher imperative. But today I find myself in SFO feeling to wrung out to code, so it seems like a good opportunity to play some catch up on my blog.

Talis

Way back in the middle of 2007 I was contacted by Talis who were wondering if I would be interested in working with them on semantic web systems, and possibly on Mulgara. My job at the time (with Herzum Software and the spin-off fourthcodex) was supposed to be based on Semantic Web technology, with a sizable proportion devoted to Mulgara. However, this had not happened for the 2 years I had been there, and so I was willing to consider this proposal. Also, I was getting great enjoyment and occasional inspiration from Paul Miller's Talking with Talis interviews (and even gaining an interest in libraries, courtesy of Richard Walis's productions). I'd also met Ian Davis at SemTech earlier in the year, and had noted with interest that Danny Ayers had recently made the move as well.

So in August I took a few days from work and flew to England for an interview. I was really impressed with the guys in Birmingham, both technically and personally, and had a great time. While my understanding of the details has changed at various times, it seems that Talis have an approach of investing in Semantic Web technology without an requirement of immediate return. They are also providing support to a growing Semantic Web community with the expectation that this will lead to a data infrastructure on which they can layer semantic applications at a higher level than is possible today. To me this seems to be both very forward thinking, as well as operating for the mutual benefit of themselves and the community at large. As an Australian I also found that the similarities in culture with the British gave me a level of comfort beyond what I usually have here in America.

Whether I would be working in semantics, or in the storage layer to enable semantic work by others, this really seemed like a place I'd enjoy working. However, the position would be telecommuting, and I need a visa sponsor while I live here in the USA. Talis were aware of this, and though they said they were in the process of setting up a legal entity over here, the delays this brought about have led to events overtaking this opportunity.

That said, I'm still trying to keep channels open with everyone there, and I'm hoping that I'll be able to work with them in the future, in whatever capacity that may be.

Google

Shortly before the trip to England, I found myself thinking of distributing immutable tree nodes (from Mulgara's internal storage) over a cluster, with the idea of improving scalability of speed and size for RDF storage. These thoughts led to ideas of leveraging a system like the GFS or BigTable. Hadoop is also interesting in this regard, but not as advanced or scalable as the systems at Google. With this in mind, and being particularly frustrated at work, I checked out the Google jobs page, and discovered that they had engineering positions available in Chicago. So I filled in their online forms and sent it off. Disappointingly, the next day I received a form-reply email explaining that I wasn't what they were after.

A few weeks later I met Eric Olson at Tech Cocktail. Eric was still working at Google at the time, and said that he'd mention my name. I have no idea if he did or not, but a couple of weeks later, a Google recruiter in California rang me and asked if I would be available for a phone interview. This was delayed while I went to England, and then delayed further as that recruiter left and another took on my case, but it finally happened in September. It was very strange to do an interview again, when I've conducted so many in the last couple of years. I've also managed to avoid the "normal" interview process for most of the last decade, since I have usually been interviewed or offered positions by people who already knew me, either personally or by reputation.

All the same, this interview went well, as did the next phone interview. So Google organized tickets for me to fly out to Mountain View and interview on site. I hadn't seriously considered a job with them to this point, but I thought it would be interesting to follow the process through.

Visiting the Mountain View campus was quite an experience. It is vast, and has been gradually subsuming the surrounding business district in recent years. Getting around is often done by shuttle bus, or bicycle. People bring their own bikes, but there are a number of Google bikes parked around the place, with helmets available in large bins in the lobby of each building. Not having been given a building number to go to, I started at the central building, where I was quickly spotted and assisted by a security guard. Indeed, I was very impressed at the rapid and efficient response of on-campus security, especially as they were also very helpful and courteous.

The receptionist I was directed to was also helpful, showing where I needed to go, arranging a shuttle bus, providing a visitor's badge and directions, and a fruit juice (Google have large fridges full of Naked juice in every lobby I saw. They also have more exotic flavors available than I have seen anywhere before or since).

Passing by the truck that had come to provide cheap haircuts to staff, I proceeded by a central courtyard which had a full sized Tyrannosaurus Rex skeleton (with pink flamingo in it's mouth - several of it's cousins scattered the lawn) and a large sign proclaiming that there would be a Farmers' Market there at 11am that day.

One bus trip later, I was where I needed to be, and being given a tour of the building. The variety of free coffee and other beverages was really impressive, as was the local version of Google's famous cafeterias. But the thing that really got me was seeing a projected list of Google's text searches scrolling up the wall. These are not done in real time (they would go by too fast) and have been filtered for inappropriate content (no searches for pornography, for instance), but they still served to drive home exactly where you were. This was ground zero. Those searches were resolved here.

The queries were also interesting to watch go by. There were questions on movies, Britney Spears, medical conditions, landmarks, and many questions in foreign languages, some of which were in foreign character sets, like Simplified Chinese. Watching these going by, it is immediately apparent where ideas like Google Zeitgeist came from.

I then went on to have my interviews. There were about 4 of them, with a break for lunch which I had with one of the people I'd had a phone interview with. While a few of the questions were more general, most of them were about how I'd solve programming problems, with an emphasis on doing things to a "Google level of scaling". Funnily enough, my last few years of Mulgara work were perfect for this. On a couple of occasions I even found myself describing code I had written, rather than describing an abstract answer. I also got the chance to ask more about how Google works, and what it's like to be there. I was impressed by everyone's enthusiasm for their work, and for the company culture in general. A couple of people I spoke with also had children, and while they admitted that in the past Google had not been very good at supporting people with young children, in recent years this had improved significantly. But the thing that everyone talked about the most was the "perks". These extend into areas you couldn't imagine, and they are constantly evolving. Unlike most companies who occasionally institute a perk for their staff, possibly guided by a suggestion box, Google has a department whose sole mission it is to identify and implement perks.

Finally the day came to an end, and I was able to head up to San Francisco. I had a very enjoyable evening with Peter and Trish, and the next day spent several hours having Mulgara discussions with Amit and Ronald at Topaz. I was very pleased to get in this last meeting, and had shuffled things around with Google to make sure it could happen.

As most of my friends know, a few weeks later Google made me an offer. While the base salary was simple enough, I was bemused at the complexity of the arrangements for paying bonuses, stock options, and common stock. It is the first job offer I've ever had that came with a set of equations attached. While not going into details, I will say that it was very lucrative - if you came close to meeting your goals. I hadn't really considered accepting an offer until this point, but an offer like that would make anyone seriously reconsider. Consequently I agonized over this for a couple of weeks, right up to the deadline that Google set. In the meantime, I visited the Chicago site (where I insisted I would want to work, despite being asked several times if I'd move to Mountain View), and again was impressed with their setup. In fact, I've had a few people suggest that the setup at Mountain View is getting a little out of control in some ways, but this was not an issue for Chicago at all.

I finally decided to turn Google down, and let them know as soon as I got back from Thanksgiving. I'd had advice from a few people, including some from inside of Google, who all pointed out that my work in the Semantic Web would be totally subsumed by working at Google. I had thought to do something with the "20% projects" that Google is known for, but it was pointed out that because bonuses are based on meeting (and exceeding) goals, then the option to use 20% of your time on something not related to your immediate work was often forgone. You also have to wonder how much of your bonuses, options, and common stock you'd get to see if you tried to keep a balanced lifestyle and didn't achieve your annual goals (apparently these are supposed to be set at a level that is challenging to achieve).

Another serious consideration was one I hadn't expected. Despite having signed an NDA, I learned nothing about Google that isn't already known to the public. Consequently, to an outsider it looked like the company was not doing anything really "interesting". I'm sure they are, but there was nothing inspiring about what they had to tell me. For most of the things I considered to be "cool" technology, I was told that those things were pretty much done, and the work they now do is in different areas altogether. In fact, the majority of the people I spoke to worked in AdWords and Billing. They were very enthusiastic about their work, and given the novelty of their service and the scale they have to work at, then I'm sure it's challenging and interesting work, but it didn't inspire me at all.

Most of all, I've spent my career working with people who know a lot more than I do, to my enjoyment and benefit, and yet, no one I spent time with really impressed me with their knowledge of skills. Don't get me wrong - they were all quite competent and intelligent people. But I really expect something special out of the people I work with, if they are to bring out the best in me. Now I know that Google has employed some of the brightest people in the industry, but the sheer size of the company convinced me that I'm unlikely to find myself working with those people.

For those not paying attention, these last few paragraphs are all a means of justifying to myself that I made the right choice. It wasn't an easy choice to make, since Google does seem like a cool company, the perks were huge, and the remuneration was potentially substantial. But I'm pretty sure I did the right thing, and as one friend said, he thinks it is much cooler to say that you've turned down a Google offer than to have accepted one. :-)

Fedora Commons

Coming up to Christmas, I was finally getting a chance to do some Mulgara work during office hours. This was a huge thing for me, as I had been getting more and more frustrated about it for the previous two years when I was supposed to be doing this. Then in the final days before Christmas my boss, and several others I worked with in fourthcodex, decided that they wanted to do something different in semantic technologies, and resigned. Without a team to work with, there wasn't a lot of scope for me to do semantic work any more, and I was told to stop working on Mulgara again. Sigh.

While some semantic options were being pursued, the fact remained that Herzum Software desperately needed some more senior coders, and it looked very much like I would end up on projects that were of little interest to me. A notable one here was a .Net project that would have me working on site in Pittsburgh. This was something that nobody wanted, including my family, and everyone I was working with on Mulgara.

Talis tried to help at this point (and I'm very grateful that they did), but their interim solution would have made it illegal for Anne to keep her new business running, and I couldn't do that to her. But then, Topaz and Fedora Commons came back to me with an offer to work for them (which distinct organizations, there is an administrative relationship between them, and both are contributing to the Public Library of Science). I've already written about my decision to accept this, which brings me up to today.

I've officially been working for Fedora Commons for about a month now. I've been dividing my time between the SPARQL implementation and responding to support and debugging requests. However, this week has been different. We got all the developers from Topaz and Fedora Commons together, to discuss our plans for the year, and how to manage the process. Mulgara has also been generating some more external interest again, and since we form the core of the active developers, we wanted to discuss ways in which we can work with the community, particularly developers.

Features

The most important features we are implementing in the coming year are SPARQL, multiple concurrent writers, and significantly greater scalability. We have been talking about the last one for a long time, but no one has had the time (or money) to do anything about it. This has now changed, and the work is commencing very soon now. It's been a long time in coming, so I'm quite inspired to get it done now.

Andrae was present for the meeting, and presented some very impressive results to his research on transactionality for multiple writers on an RDF graph. Not only has he demonstrated a mathematically sound foundation for this work, but he has also included an impressive level of engineering for scalability in his designs.

In the meantime, I have come up with a new scheme for indexing RDF, which appears to have significantly better complexity results than what we currently do. Fortunately, the majority of this work is orthogonal to Andrae's designs, with the consequence that the improvement to scalability will be cumulative between both redesigns. I'm pretty chuffed at this. :-) I will be writing more on the indexing shortly, but I have been under some pressure to write this up as an academic paper as well, so that may take priority over my blog.

Significantly, we had James Leigh from Aduna at the meeting as well. Aduna are the company behind the Sesame RDF store, which has been one of the big open source alternatives to Mulgara. They are interested in merging our systems to a certain extent, to the benefit of both. After hearing James out, it sounds like a really good idea (though I may end up throwing away the SPARQL parsing that I've finished - sigh again). I'm not sure when it will happen as everyone as a lot of immediate priorities to get through, but everyone has expressed support for implementing the SAIL API on Mulgara. This is very significant for us, as it will provide a host of new reasoning features, the ability for existing Sesame users to easily try Mulgara, and a SPARQL protocol interface (I'd just been working on the query language for the moment). In turn, I'm hoping that we can demonstrate these new levels of scalability and concurrency for Sesame.

A lot more came out of the meeting, but that was the crux of it. Rather than pre-empt some of the things that are still in motion, I'll let others explain their end of things.

I'm very happy to see this level of interest in Mulgara, and I'm excited to see all these new features starting to be realized at last.

More Correspondence

Going back through my emails with Andy, I realize there's still a lot that might be of interest to include here. Hopefully the parts I choose to copy/paste don't appear to disjoint.

JRDF

Andy was confused about the role of JRDF in Mulgara, as well he might be. He was trying to work with a minimal set of classes, yet he kept needing JRDF even when he wasn't using the JRDF interfaces.

You can think of JRDF as having 2 faces. First, it provides definitions for classes that represent RDF nodes - URIResource, Literal, BlankNode. Second, there's an interface for inserting and querying for RDF statements. Initially, someone decided to use JRDF as the definition for nodes (I think it was Andrew, and I think he chose to use it since he'd already written this code while he was at home, and it made sense for him to reuse it). Some time later, Andrew decided that the interfaces for manipulating and querying for statements should also be implemented, since we were already using the JRDF code. (Now this is in my blog, I'm sure Andrew will clarify this point!)

So internally, yes we use JRDF. It's mostly for the interfaces and abstract classes associated with URIResource, Literal, and BlankNode. There are also interfaces for SubjectNode, PredicateNode, and ObjectNode which are used when putting triples in and out of Mulgara. At the lower levels, Mulgara is 100% symmetric around all 4 nodes (it used to be 3 nodes, but as most people should know now, we moved it up to 4). However, when the data gets pushed through these interfaces, this imposes certain type restrictions. This is why Mulgara won't let you use a literal as a subject, or a blank node as a predicate.

For this reason, you'll need the JRDF classes, even if you never use the JRDF interfaces. Yes, I know it's annoying. One of the many reasons I want to reimplement a lot of Mulgara (another big reason is that I want to use a less restrictive licence - specifically Apache).

Blank Nodes

Blank nodes can have any label an implementor chooses to use, so long as it meets certain criteria. In Mulgara, they are shown as an underscore, colon, and then a number. Andy was trying to figure out the significance of the numbers shown here, and how they get allocated.

These numbers are actually the raw graph node identifiers (a 64 bit long), or gNodes. All gNodes are allocated from the Node Pool, which is just a Free List.

... describing free lists..... Oh boy.....

To start with, any new requests for gNodes just come from an incrementing long. However, if you ever delete all the statements that use a gNode, then that gNode will be "released", meaning that it's added to the FreeList. So now, whenever you ask for a new gNode, the FreeList will try to give you any released gNodes first before it returns the incremented internal long value.

However, that's a vast simplification. If you released a gNode in the current transaction, then these will be given back to you first (until exhausted). Next, it will try to give you any nodes released in old transactions that are not part of a currently "open" result set. Once all open resources that refer to a set of gNodes have been closed, then the FreeList is able to hand them out. Finally, it uses the incrementing long.

All of this reflects the 32 bit thinking that the system started with. There is little need to re-use gNode values when you have a 64 bit system (if you allocate a gNode every millisecond, then it will take you half a billion years to use them all up, so I think we're safe). We need to update it, but unfortunately, there are arrays which are indexed by the gNode ID, meaning we can't just increment the long all the time. With the 32 bit approach this was OK, since the ID values were packed from the bottom. But if we move to an incrementing number for gNodes (simplifying things greatly - and speeding them up) then we will need a new on-disk structure for this array.

OK, this isn't describing Mulgara now. It's really my recent musings on making it all faster.

The Server

Andy was waiting for the server to start up, and his TQL client appeared to be getting confused with the intermediate startup state. There wasn't a lot said here, but I want to reiterate it anyway.

IMHO The server is WAY too heavy. I'm all for the services provided... but I think they need to be provided in an external framework, and let the database be a module that gets loaded by that framework. The fact that it starts so many services really bothers me. I'd fix this, if I had time.

Mind you, I'm being a bit harsh when I say "fix". It works. It's just I believe it needs to be made of smaller parts, which are either independent, or build on one another. The current server is monolithic.

Mulgara Correspondence

Recently I've been in a few email discussions with Andy Seaborne about the architecture of Mulgara. He's been looking at a new Jena-Mulgara bridge, but when he's had the time it appears he's been looking into how Mulgara works. There are certainly areas where Mulgara could be a lot better (distressingly so), so we will be changing a number of things in the not-to-distant-future. But in the meantime I'm more than happy to explain how things currently work. It's been a worthwhile exchange, as Andy knows what he's on about, so he's given me some good ideas. It's also nice to talk about some of the issues with indexing with someone who understands the needs, and can see the trade offs.

Since I wrote so much detail in some of these emails, I asked Andy (just before he suggested it himself) if he'd mind me posting some of the exchange up here. One could argue that if I hadn't been writing to him then I'd have had the time to write here, but the reality is that his questions got me moving whereas the self-motivation required for blogging has failed me of late.

There will be a lack of context from the emails, but hopefully I'll be able to edit it into submission. I should also issue a warning that what I wrote presumes you have some idea of what RDF is, and that you can look at the Mulgara code.

AVL Trees

If you want to keep read/write data on disk, and have it both ordered and efficient to search at the same time, then a tree is usually the best approach. There are other things you can do, but they all involve a tradeoff. Trees are usually considered the best thing to go with.

Databases usually have B-trees of some type (there are a few types). These work well, but Mulgara instead opted to go with AVL trees, with a sorted list associated with each node. This structure is much more efficient for writing data, but less efficient for deletion. This suits us well, as RDF is often loaded in bulk, and it gets updated regularly, but bulk deletions are less frequent. I mention the complexity of this later on.

Andy asked about our AVL trees, with comments showing that he was only looking at one of their uses. I think that understanding a particular application of this structure is easier if the general structure is understood first.

AVL trees are used in two places: The triple indexes (indices), and the "StringPool" (which is really an Object pool now).

The trees themselves don't hold large amounts of data. Instead each node holds a "payload" which is specific to the thing they are being used to index. In the case of the "triples" indexes, this payload includes:

• The number of triples in the block being referenced.
• The smallest triple stored in the block.
• The largest triple stored in the block.
• The ID of the 8K block where the triples are stored (up to 256 of them).

I'm only using the word "triple" because that's what we stored once upon a time (circa 2001). In reality, we store quads. On the first pass, the fourth value was a set of security values, but this quickly became a graph ID. Unfortunately, this happened back when everyone referred to graphs as "models", so you'll see the code uses the name "model" instead of "graph" everywhere. (I'd like to change this).

There is also some inefficiency, as we use a lot of 64 bit values, which means that there are a lot of bits set to zero. There are plans to change the on-disk storage this year to make things much more efficient. Fortunately, the storage is completely modular, so all we need to do to use a new storage mechanism is to enter the factory classes into an XML configuration file.

The code in org.mulgara.store.statement.xa.XAStatementStoreImpl, shows that there are 6 indices. These are ordered according to "columns" 0, 1, 2, and 3, with the following patterns: 0123, 1203, 2013, 3012, 3120, 3201. The numbers here are just a mapping of: Subject=0, Predicate=1, Object=2, Model=3. Of course, using this set of indices lets you find the result of any "triple pattern" (in SPARQL parlance) as a range inside the index, with the bounds of the range being found with a pair of binary searches.

We use AVL trees because they are faster for writing than B-Trees. This is because they have an O(1) complexity for write operations when doing insertions. They can have O(log(n)) complexity while deleting, but since RDF is supposed to be about asserting data rather than removing it, then the extra cost is usually OK. :-)

The other important thing to know about Mulgara AVL trees is that they are stored in phases. This means we have multiple roots for the trees, with each root representing a phase. All phases are read-only, except the most recent. The moment a phase updates a node, then it does a copy-on-write for that node, and all parents (transitively) up to a node that has already been copied for the current phase, or the root (whichever comes first). In this way, there can be multiple representations of the data on disk, meaning that old read operations are always valid, no matter what write operations have occurred since then. Results of a query are therefore referencing phases, the nodes of which can be reclaimed and reused when the result is closed, or garbage collected (we log a warning if the GC cleans up a phase).

Because all reads and writes are done on phases, the methods inside TripleAVLFile are of less interest than the methods in the inner class TripleAVLFile.Phase. Here you will find the find methods that select a range out of an index, based on one, two, or three fixed values.

The String Pool also uses an AVL tree (just one), though it has a very different payload. However, the whole phase mechanism is still there.

Object Pool

Andy noted that the comments for the ObjectPool class say that it is for reducing constructor overhead, but a cursory inspection revealed that they did more.

There's some complexity to avoid pool contention between multiple threads. Each pool contains an array of "type pools" (see the inner type called ObjectStack), indexed by an (manually) enumerated type. You want an object of type ID=5, then you go to element 5 in that array, and you get a pool for just that type. This pool is an ObjectStack, which is just an array that is managed as a stack.

Whenever a new ObjectPool is created it is chained onto a singleton ObjectPool called the SHARED_POOL. To avoid a synchronization bottleneck, each thread uses the pool that it created, but will fall back to using the "next" pool in the chain (almost always the SHARED_POOL) if it has run out of objects for some reason. Since this is only a fallback, then there shouldn't be much waiting.

I know that some people will cringe at the thought of doing object pooling with modern JVMs. However, when Mulgara was first written (back when it was called TKS) this sort of optimization was essential for efficient operation. With more recent JVMs, we have been advised to drop this pooling, but there have been a few reasons to hold back on making this change. First, we have tried to maintain a level of portability into new versions of the JVM (this is not always possible, but we have tried nonetheless), and this change could destroy performance on an older JVM. Second, we do some level of caching of objects while pooling them. This means that we don't always have to initialize objects when they are retrieved. Since some of this initialization comes from disk, and we aren't always comfortable relying on the buffer cache having what we need, then this may have an impact. Finally, it would take some work to remove all of the pooling we do, and recent profiles have not indicated that it is a problem for the moment. I'd hate to do all that work only to find that it did nothing for us, or worse, that it slowed things down.

32/64 Bits and Loading

Andy was curious about our rate of loading data on 32 bit system or 64 bit systems, given simple data of short literals and URIs (<100 characters or so). Unfortunately, I didn't have many answers here.

In 2004 Kowari could load 250,000,000 triples of the type described in under an hour on a 64 bit Linux box (lots of RAM, and a TB of striped disks). However, it seems that something happened in 2005 that slowed this down. I don't know for certain, but I've been really disappointed to see slow loads recently. However, I don't have a 64 bit Linux box to play with at the moment, so it's hard to compare apples with apples. After the SPARQL implementation is complete, profiling the loads will be my highest priority.

64 bit systems (excluding Apples, since they don't have a 64 bit JVM) operate differently to 32 bit systems. For a start, they memory map all their files (using an array of maps, since no single map can be larger than 2GB in Java). Also, I think that the "long" native type is really an architecturally native 64 bit value, instead of 2x32 bit values like they have to be on a 32 bit system. Since we do everything with 64 bit numbers, then this helps a lot.

After writing this, Inderbir was able to run a quick profile on a load of this type. He immediately found some heavily used code in org.mulgara.store.xa.Block where someone was doing a copy from one ByteBuffer to another by iterating over characters. I cannot imagine who would have done this, since only DavidM and I have had a need to ever be in there, and we certainly would not have done this. I also note that the operation involves copying the contents of ByteBuffers, but this doesn't make a lot of sense either, since the class was built an an abstraction to avoid exactly that (whenever possible).

I haven't seen the profile, but Inderbir said that a block copy gave him an immediate improvement of about 30%. I'd also like to check the stack trace to confirm if a block copy is really needed here anyway. Thinking about it, it might be needed for copying one part of a memory-mapped file to another, but it should be avoided for files that are being accessed with read/write operations.

Embedded Servers

Andy was also intrigued at the (sparse) documentation for Embedded Mulgara Servers. While on this track, he pointed out that LocalSession has "DO NOT USE" written across it. I've seen this comment, but don't know why it's there. I should look into what LocalSession was supposed to do. In the meantime, I recommended not worrying about it - I don't.

The Session implementation needed for local (non-client-server) access is org.mulgara.resolver.DatabaseSession. It should be fine, as this is what the server is using.

When doing RMI, you use RemoteSessionWrapperSession. I didn't name these things, but the standard here is that the part before "Wrapper" is the interface being wrapped, and the thing after "Wrapper" is the interface that is being presented. So RemoteSessionWrapperSession means that it's a Session that is a wrapper around a RemoteSession. The idea is to make the Session look completely local. The reason for wrapping is to pick up the RemoteExceptions needed for RMI and convert them into local exceptions. At the server end, you're presenting a SessionWrapperRemoteSession to RMI. This is wrapping a Session to look like a RemoteSession (meaning that all the methods declare that they throw RemoteException). Obviously, from the server's perspective, the Session being wrapped here must be local. And the session that is local for the server is DatabaseSession. So to "embed" a database in your code, you use a DatabaseSession.

The way to get one of these is to create an org.mulgara.resolver.Database, and call Database.newSession(). Databases need a lot of parameters, but most of them are just configuration parameters that are handled automatically by org.mulgara.resolver.DatabaseFactory. Look in this factory for the method:

 public static Database newDatabase(URI uri, File directory, MulgaraConfig config);

A MulgaraConfig is created with using the URL of an XML configuration file. By default, we use the one found in conf/mulgara-x-config.xml, which is loaded into the jar:

 URL configUrl = ClassLoader.getSystemResource("conf/mulgara-x-config.xml");
 MulgaraConfig config = MulgaraConfig.unmarshal(new InputStreamReader(configUrl.openStream()));
 config.validate();

(configUrl has a default of: jar:file:/path/to/jar/file/mulgara-1.1.1.jar!/conf/mulgara-x-config.xml)

As an aside, it's supposed to be possible to do all of this by creating an EmbeddedMulgaraServer with a ServerMBean parameter that isn't doing RMI. Unfortunately, there are no such ServerMBeans available. (Maybe I should write one?)

Also, I believe that the purpose of the embedded-dist Ant target is to create a Jar that has these classes along with all the supporting code, but without anything related to RMI. So the embedded Jar should be all you need for this, but I haven't used it myself, so I'm just making an educated guess. :-)

SPARQL

Since I had been working on this up until mid-December, it is worth noting where I am with it.

TQL includes graph names as a part of the query, and graph names have been URLs (not URIs) - meaning that they include information on how to find the server containing the graph. Unfortunately, the guys who wrote TQL integrated the session management into the query parsing (if that doesn't make you shake your head in disbelief then you're a more forgiving person than I am). I've successfully decoupled this, and now return an AST that a session manager can work with. This also means that graph names no longer have to describe the location of a server, meaning we can now support arbitrary URIs as graph names. This now puts the burden on the session manager to find a server, but that's easy enough to set up with configuration, a registry, or scanning the AST for graph names if we want backward compatibility.

The next part has been parsing SPARQL. (Something that Andy should be intimately familiar with, given that his name is all over the documents I reference).

With so many people talking about extensions to SPARQL, and after discussing this with a few other people, we decided to go with an LALR parser. This means I've had to write my own lexer/parser definition, instead of going with one of the available definitions, like the JavaCC definition written by Andy. We do have SableCC already in Mulgara, but everyone present agrees that this is a BAD LALR parser so I had to use something new. I chose Beaver/JFlex. It's going well, but I still have a lot of classes to write for the CST. The time taken to do this has me wondering if everyone is being a little too particular about the flexibility of an LALR solution, and maybe I should just go back to Andy's JavaCC definition. OTOH, I really like Beaver/JFlex and having an independent module that can do SPARQL using this parser may be a good thing.

Fortunately the SPARQL spec now has a pretty good grammar specification and terminals, though one or two elements seemed redundant, and I've jumped over them (such as PNAME_LN. Instead I defined IRIref ::= IRI_REF | PNAME_NS PN_LOCAL? ). I've been getting some simple CSTs out of it so far, but have a way to go yet.

Once I have it all parsing, of course, I have to transform the result into an AST. Fortunately, most of the SPARQL AST is compatible with Mulgara. The only exceptions are the FILTER operator (SPARQL's "constraints") and the OPTIONAL operator. I'm pretty sure I can handle OPTIONAL as a cross between a disjunction (which can leave unbound variables) and conjunctions (which matches variables between the left and the right). Filters should be easy, since all our resolutions are performed through nested, lazy evaluation of conjunctions and disjunctions. Handling the syntax of filters is another matter, but I expect it to be more time consuming than difficult.

Holdup

Since writing these comments about implementing SPARQL, I haven't had time to work on it again. Hopefully that will change soon with the new job. But in the meantime, the loss of time has me thinking that I should reconsider using a pre-built SPARQL definition for a less expressive parser, and come back to Beaver/JFlex at a later date.

I've heard that the Jena JavaCC grammar may be a little heavily geared towards Jena, but I've been given another definition by my friend Peter which is more general and apparently passes all the relevant tests. I suppose I should go and learn JavaCC now.