San Jose

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

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

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

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

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

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

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

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

Disjunctive Logic

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

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

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

Multiple Blanks

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

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

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

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

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

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

There are two ways I could manage this situation.

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

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

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

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

Distributed Resolver

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

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

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

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

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

Optional

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

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

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

SPARQL

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

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

Filters

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

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

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

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

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

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

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

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

Filtered Constraints

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

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

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

Sleep

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

Description Logic

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

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

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

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

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

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

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

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

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

Logic and Sleep

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

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

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

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

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

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

So my question of equivalence goes from:

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

To the expression:

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

Or even simpler:

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

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

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

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

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

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

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

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

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

Doh!

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

Description Logic

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

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

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

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

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

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

Maybe I'm reading it wrong.

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

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

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

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

Distributed Queries

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

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

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

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

SOAP on Jetty

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

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

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

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

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

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

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

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

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

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

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

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

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

Zarro Boogs Found

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

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

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

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

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

String Pool

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

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

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

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

String Pool

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

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

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

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

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

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

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

Out of Synch

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

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

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

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

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

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

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

 gNodeToDataFile.force();

Tests

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

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

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

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

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

Transaction Exceptions

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

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

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

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

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

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

RMI Threads

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

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

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

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

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

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

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

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

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

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

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

Dreaming in Code

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

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

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

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

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

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

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

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

A Stratified Profession

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

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

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

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

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

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

Interfaces

Interface design appears to fall into two categories.

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

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

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

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

RDFS and OWL

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

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

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

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

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

RDFS/OWL Interfaces

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

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

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

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

A more interesting question has been object instantiation.

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

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

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

Bytecode Libraries

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

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

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

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

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

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

Vista DRM

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

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

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

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

Time Bugs

A short while ago I received a bug report for Mulgara, where certain Date/Time stamps were being randomly changed. I dreaded to think what this could be, and avoided it in the hope that the reporter (DavidM - but not the DavidM who wrote the storage layer!) or someone actively working in the storage layer (like Andrae) would find the problem.

Another report yesterday made me realize that DavidM didn't know where in the system the problem was to be found. Rather than simply tell him to look at SPObject and SPDateTimeImpl, I decided to have a look myself. After all, I know this area reasonably well.

The latest bug report claims that whenever the following timestamp is entered:
  April 26, 1981, 02:56:00
Then the system always returns:
  April 26, 1981, 03:56:00
(one hour later)

First, I ran the test queries and confirmed that the problem occurs for me too, and that it is definitely the string pool causing the problem. To help me narrow things down more quickly, I copied out some of the relevant code from the string pool so I could play with SPDateTimeImpl in an isolated environment.

I quickly realized that the problem was occurring when a third-party library was parsing XSD dates. So I reported this to the developers list, and stopped looking. There were some alternative library suggestions, and Brian said he would fix it.

Third Party F/OSS

It was still bothering me that this library was failing for us. Given that it was open source software, I decided that I could at least report the problem to the developers. I don't know about taking the time to debug the code, but at least I could give them a heads-up.

(I won't mention the name of the library, because I don't want anyone to think there is anything wrong with their library. Read on.)

So I wrote an example piece of code that parses one of these bad date/times, and sent it to the developers of this library.

A couple of hours later a developer wrote back to tell me that the library works correctly for him, and that the problem may be related to timezone issues. I'm in CST and he is in BST. He gave me a test case, and asked for some details of my system.

So I ran the test, and discovered 2 things. First, the time was still being printed incorrectly, though it worked for him. Second, the tests that he wrote all passed.

Initially I thought that the tests must have been written poorly, but on inspection I discovered that they were perfectly correct. In this case, he was comparing the results of their parsed date/time with a Calendar object from the Sun JDK. Of course, since the printed data was incorrect, I expected it to compare incorrectly to the Calendar object from the Sun JDK. But this wasn't happening.

The next step was to work out why this was happening, so I asked the third-party library to print its internal long value, and compare it to the internal long value from the Calendar. But the Calendar was also giving the wrong value. That's when I realized something was screwy with the JDK, and not the third-party library.

Timeslip

A quick test class shows the problem:

import java.util.Calendar;
public class TimeTest {
  public static void main(String[] args) {
    Calendar cal = Calendar.getInstance();
    cal.clear();
    cal.set(1981, Calendar.APRIL, 26, 2, 56);
    System.out.println("Time @2:56 in millis: " + cal.getTimeInMillis());
    cal.clear();
    cal.set(1981, Calendar.APRIL, 26, 3, 56);
    System.out.println("Time @3:56 in millis: " + cal.getTimeInMillis());
  }
}

If you live in Australia or Great Briton, then this code will work perfectly. For instance, running this is Australia will give you:

Time @2:56 in millis: 357065760000
Time @3:56 in millis: 357069360000

Note that there is a time difference between 2:56 and 3:56 of 3600000 milliseconds.

However, if you happen to live in the Central American timezone, then you will get this:

Time @2:56 in millis: 357123360000
Time @3:56 in millis: 357123360000

Note that these numbers are identical! They both represent 3:56am on that day.

I tried this with Java 1.4, 1.5 and 1.6 on my Mac. I also tried with with Java 1.5 on x86/Linux and Windows. All of these configurations return identical results.

Could Sun have created a problem here? Why does it only affect timezones in the USA?

At this point it was getting late, and I was startled at what I was seeing. Andrae was online, so I showed him. I was too tired to look in the source for java.util.Calendar and java.util.GregorianCalendar, so he offered to look for me. But rather than letting me go to bed, he insisted I should blog about it so that it was written up somewhere.

Fortunately, it takes a little while for me to write a blog entry. This allowed Andrae time to discover what was happening. It comes down to the following:

The Uniform Time Act of 1966 (15 U.S. Code Section 260a) [see law], signed into Public Law 89-387 on April 12, 1966, by President Lyndon Johnson, created Daylight Saving Time to begin on the last Sunday of April and to end on the last Sunday of October. Any State that wanted to be exempt from Daylight Saving Time could do so by passing a state law.

According to comments in java.util.GregorianCalendar, the hour sequence on that night is:

  12 Std -> 1 Std -> 3 Dst -> 4 Dst

This means that there was no such time as 02:56 on that morning. So the Mulgara date/time bug is not a bug at all, but required behavior.

Disambiguation

The Mulgara behavior may be correct from one perspective, but it can still be troublesome. A time like this can be supplied from a non-US source, but it cannot be entered into a US system. This demonstrates that Mulgara date/times do not support timezones, even though they are described in the XSD specification that they implement.

I'm thinking that the default behavior in Mulgara should be to assume the local timezone (as it does now), but to allow for explicit timezones as well. That way any ambiguity can be removed.

Date/times on the input should allow the timezone to be included, as per the spec. I was disappointed to learn that we don't support that at the moment, but it should be easy enough to add the option to the parser.

That leaves the issue of the output. At the moment, it will be converted to the client's local timezone though it will be printed without timezone information. I'd rather not change the default behavior, so I think we should introduce an option of printing the timezone. Strictly speaking, the timezone used won't matter, as the times will be converted according the timezone being used. However, it would still be nice to specify the exact zone to be used. The time is stored relative to UTC, and the conversion to the time in a specific locality is only really relevant when it needs to be presented to a person. This means that we only need to worry about it at the client end. The infrastructure doesn't exist to store a timezone at the server, so it is only really feasible to make the conversion at the client end anyway.

I expect to put in a system property to control the output format in a few days. I have a lot of travel ahead of me tomorrow, so perhaps I'll get the time then.

Object Interfaces

Last year I wrote some code for work for managing objects in Mulgara. It started out as a quick hack, but quickly extended into something properly structured and significant. Unfortunately, most of my hours at work seem to be very inefficient, but I spent many long evenings on it, and got something quite useful going in just 2 weeks.

The idea was to define objects using standard RDFS, and to store instances of those objects all in the same model. This is similar to an object database, or Castor, or even Hibernate, but the object definitions are more malleable, and the instances need not be complete, and can even have fields filled with inferencing.

I thought the result was reasonably compelling, and it enabled someone else to build a nice little Rails application that we used a few times in a demo. Unfortunately, since then we've gone in another direction, essentially orphaning the code.

I'd love to take this code and run with it, but I did write it for work. Even though the majority of the development time was after hours, and the idea was my own, I still spent some work time on it, and it was definitely for a work project. But that's OK. Now I get to implement a Second System. I'll just have to be careful not to overdo it.

Interface Options

One of the biggest problems with objects and object definitions in the previous system was the manual detail needed to build simple things. Every field had to be defined up front, including the name and datatype (including lists). There are also optional attributes such as the field being a key, required, and even transitive. These were encoded using owl:InverseFunctionalProperty, owl:minCardinality and owl:TransitiveProperty, which left the door open to start doing some more interesting things with OWL.

Defining all these fields made for a powerful system, but hardly a friendly one. I'd like to keep an interface like this, but also allow for more natural creation of objects.

The original style of interface was inspired by Perl. In this interface object definitions use a simple map, where each field name is mapped to it's type data (this includes the optional modifiers). I've also added in a couple of methods for finding fields via the properties. The object instances are similar, in that the field names map to the data. It's easy, and it works well, but it involves a lot of messy calls to Map.get() and Map.put().

The first alternative that comes to mind is to build objects by example. By this, I mean to create a Java class definition (sans methods, and with annotations for some more interesting features, like transitivity), and to construct the RDF via reflection. With a system like this, it would be easy to pass any java.lang.Class to create a new definition, or just pass an object and have the object and definition stored at once.

Reading objects back out of the store would take only a little more work. First of all, the name of the object definition can be tested in the class loader. If it exists, then create the object via reflection, and populate it. Otherwise, use ASM (or BCEL, or whatever appeals most to me at the time) to create a new class definition, and hand it off to the class loader to build in the same way as above. I'm still figuring out the bytecode for annotations, but ASM seems to handle them just fine.

(If I wanted to get really fancy, I could even store the methods for a class by storing the AST in RDF. This has been something I've wanted to do for a while, but it really belongs in another project, and including it at this stage really sounds like an example of the second system effect.)

The main problem with this system is that it requires that objects to be stored are already statically defined (you don't want your users to use a bytecode manipulator to dynamically build their classes). That makes the system similar to Hibernate, when it should be much more dynamic.

A simpler alternative might be to allow object definitions with a simple syntax, which I parse as a string. That kind of appeals, since it makes the API easy for the developer, while passing the hard work into the engine, where it belongs.

For the time being, it may be better to stick to the map-style implementation, and add features only once I have it all going again in an open source way.

Pitfalls

Implementing this the first time around showed up some of the difficulties in actually building something like this.

Atomicity

One important problem was a difficulty in querying all the data needed to construct objects in an atomic way. I had hoped that subqueries could solve this, but I didn't find a way through it. If it isn't atomic, then a structure could be inconsistent if someone were modifying the data at the same time.

So far my code has all been "client side", but the requirement of atomicity has me wondering if I need to move to a server side API. I should talk with Andrae about transactions.

Updates

There is also the question of updating the data. This is an important question, while at the same time it is a non-issue for RDF.

RDF asserts simple statements of subject-predicate-object. A statement either exists, or it doesn't. If I have a statement like:
  [ S O P1 ]
and I want to change the predicate so that the statement becomes:
  [ S O P2 ]
then I have not changed this statement at all! Instead I have removed the first statement, and inserted a new one. So RDF only handle assertions and denials, nothing else. Keeps everything simple.

However, any structures built on RDF (such as RDFS) do require the ability to modify them. I suppose that it is possible to naïvley remove the whole structure, and insert a new one, but this is both inefficient, and possibly disastrous for any links to that object. However, keeping track of object deltas is not very easy. I also have concerns (that I haven't addressed yet) of how to ensure any changes are compatible with related structures.

Open World

Another problem is that the real world wants object structures to be in a "closed world" definition. This isn't the time to justify this assertion, but there are a lot of practical reasons for it. To date I've taken a couple of liberties with RDFS, where I've required that fields in an instance must have type definitions in the object definition, but this is not RDF. The closed world is certainly more practical for computer applications, but I'm thinking I should explore an open world interface, while still keeping the API practical.

Datatype Properties

I also ran into an unusual issue with strings.

While I could have used the org.mulgara.query.Query interface (like I know Andrae does) I have chosen to use iTQL instead. There were several reasons, but the most compelling at the time was the need to create the code quickly and to debug easily.

However, I have to say that I hate working with strings. They're messy, prone to typos, and reek like magic numbers. That's a problem with iTQL, where all the queries are constructed from strings. To counteract this effect, I created a series of classes and enumerations which did all the iTQL building for me. The irony was that I ended up with a similar looking interface to using org.mulgara.query.Query directly. I like to think that I gained a few important features though. :-)

One part of the code passes all subjects, predicates and object to a method to get the appropriate iTQL representation. For URIs this is simply the URI wrapped in angle brackets. For blank nodes during insertion, this becomes a variable. And for literals, the data is converted to a string, placed between single quotes, and gets followed by the datatype. It even spots the difference between a URI and a URI Literal.

Reconstructing data from a literal is also straightforward, using an enumeration which maps the XSD datatypes back to the required Java constructor.

The problem is that all strings end up looking like this:
  'A string'^^<http://www.w3.org/2001/XMLSchema#string>

Now strictly speaking, this is right. Unfortunately no one ever writes RDF data that uses typed literals for strings. It appears that untyped literals are always used for strings, and typed literals for anything else. Just to be clear, Mulgara considers a typed string to be distinct from the same value in an untyped string, making strings incompatible between imported RDF and the data I construct.

For the moment I've left the string datatype where I found it, as I haven't tried to integrate data from other sources yet. However, I will probably need to make an exception for strings, where they have the datatype stripped off during a write, and missing datatypes inferred as strings during a read.

This problem did point out that these two types of strings are incompatible in Mulgara. Subsequently I've been wondering for a while whether we need to address this. Maybe I should go and look at some more RDF theory. I suspect that they are intended to be distinct, but I'm not sure I see a practical reason for it.

New API

I've been thinking for a while that Mulgara needs an API at a higher level than RDF. I'm not talking about RDFS or OWL inferencing (which is what I'm usually discussing) but a solid way to manipulate structures at this level of abstraction. I'm even prepared to use a different abstraction to RDFS and OWL, though it makes sense to pursue these ones.

Everything I wrote here is really about object definitions and instances (MOF levels 0 and 1), rather than addressing RDFS or OWL directly. In fact, only a couple of OWL constructs are used, so I can't say that it supports OWL in any meaningful way, only that it uses a subset of OWL to represent some structural information.

I want to pursue this style of API for the time being, since many real applications want to refer directly to objects and their definitions. I think this is a very practical approach, and can even be extended to encompass most (or maybe all) of OWL. But I'm also thinking that I should consider a real honest-to-goodness OWL API as well. Perhaps something that resembles the OWL abstract syntax. After all, there are a lot of people using OWL out there, who may want direct access to OWL structures, but don't want to manipulate RDF (which can be verbose for simple OWL constructs). But before going too far down this road, I should take a closer look at others attempts at an OWL API (such as Sofa, which was integrated into Kowari at one point).

Late

As usual, I've stayed up much too late to write this, leaving no time to proof read. Caveat emptor.

Numbers

Here I was, hoping to get more blogging done on my "working vacation", when I suddenly discover that I'm leaving Australia tomorrow! Oh well, it was nice to get some family time in. We have more planned for today.

I got an email this morning telling me that a link to some code I wrote has gone stale in an old blog entry. Oops.

The code isn't a big deal, but if anyone wants to generate a lot of RDF based on cardinal numbers, then I've put the file up on Mulgara.

See you in the USA.

New Look

I had to change some of the elements on this page (I was still linking to Kowari!), so while I was at it I decided to change the look a little bit.

The color change is mostly because someone anonymous complained about it. I couldn't tell if the complaint was spam, but I figured I was due for a change. The change in width is because the narrow columns have been bugging me for years. Unfortunately, I know next to no CSS, so I fiddled until I liked it a little better. Please let me know if I killed the layout in some horrible manner.

Mulgara Progress

Mulgara is going ahead nicely at the moment, thanks mostly to Andrae. He has implemented some major changes and bug fixes which were sorely needed. My only problem with any of this has been that my main support has been administrative, rather than technical.

Once upon a time I was writing TKS/Kowari/Mulgara code every day. It was very challenging and very satisfying. I also found that the whole process of blogging was useful to help keep my thoughts focussed, and keep other people in touch with what I was up to.

These days I'm involved in a lot of other people's code, and I can't blog about at all. It also keeps me away from coding, which is very frustrating, as I don't get that rush of implementing something cool, and seeing it all the way through to completion. That leaves me to do the interesting work at night, but after a long day at work, and time with family, I don't have the motivation to put in long hours of coding. Of course, two young boys mean that my weekends are packed as well.

Any remaining time does go to Mulgara, but the less frequently I work on it, the more I have to re-learn the context of where I was the "last time I was here". Just yesterday someone sent me an email, where they included a message they received 2 months ago. The email was coherent, and apparently written by someone who really knew the issues. I found myself agreeing with a lot of it and thinking, "this guy knows more than I do". Unfortunately (or fortunately?) I soon realized that the original author was myself.

It can be difficult to make a lot of progress when you have to bring yourself back up to speed every time you look at something.

I'm not sure what to do about this lack of time for non-work activities, but I'll have to resolve it soon. I'm supposed to start back at university shortly, and without any free time available I won't be writing a thesis! That's particularly frustrating, since I've been making all sorts of progress in processing OWL recently.

RLog

So what have I been doing in Mulgara/OWL?

Some time ago I realized that I needed to get an OWL processor out there, even if it were only partly complete. Hey, I can call it OWL-Lite if I want to! The specification explicitly says that there is no list of requirements to fulfill, so I'm covered. Fortunately, there are a lot of simple OWL inferences that I can perform already, courtesy of Raphael Volz. A number of others also come to mind, given some of the operations in iTQL, so this looked like a good first step.

The problem is that most of this work is easy to code using description logic (as Raphael has done in the paper I mentioned), but converting it into the RDF format I've created for the Krule engine is tedious and prone to bugs.

I found myself wishing that someone would write a programs that would parse the description logic, and convert it into Krule syntax. Even better, the dependencies could be automatically generated, based on the the format of the output of one rule, and the input to another. This would avoid many of the bugs I could potentially introduce through manual transposition, and make all future rules MUCH easier to encode.

So I'm motivated by laziness (who wants to manually encode all those OWL/RDFS rules and axioms?), impatience (why should I have to find all those dependencies, when computers are better at that kind of thing?), and hubris (hey, I could write a program to do it for me, and it would be cooler than every other logic interpreter out there because it works on my database).

So it looks like I want to re-write Prolog (yes, I've even looked at an interruption function in the algorithm to permit "cut" operations, à la Prolog). That takes hubris to a whole new level for me. But the funny thing is that it would be so easy. The hard work is in the rule engine, and I've already written that!

The language isn't really Prolog, or even the simpler logic languages, like Datalog. The main difference is in the allowable syntax. For a start, I want to allow domains on the predicates (so I can write owl:sameAs(x,y), for instance). I also want to use lower case letters for variables (instead of the upper case letters required by other logic processors). But in essence it's all the same.

So it's a type of logic, and it's based on RDF. Without anything better, I decided to call it RLog (which I pronounce Arr - Log). Who knows, if I finish it, it might even take off. (OK, OK, I don't have that much hubris).

It's funny that I'm looking to implement this. A couple of years ago I realized that Kowari could form the basis of a Prolog engine, though I knew that there was a lot of coding needed before we could do it. Now I'm on the verge of having written it, and I never really intended that.

Where Am I? How Did I Get Here? And What Am I Doing In This Handbasket?

I started all of this some time ago, but for the reasons I've mentioned above, I still have some way to go.

I started out by encoding my first set of OWL rules in RLog. The language didn't need much definition, just standard predicate logic, along with variables, domained predicates, comments, and so on. So then I converted all the RDFS rules, and added in the OWL rules that I want for the first cut. This showed up some interesting cases that I had to consider.

RLog tricks

The first thing I found was in rule 4b on RDFS. Strictly speaking, it should be:
  rdfs:Resource(u) :- a(x,u).
Meaning that for any triple <x a u> the element labeled "u" is a resource (or rdfs:Resource). That's what the RDF documents say anyway. However, this violates RDF, since u might be a literal. Literals are unable to have types like this, since it requires that they be the subject in a statements, which is illegal in RDF.

The way I've been getting around this in Krule so far has been to use a "type" model in Mulgara. The result removed all resources which were literals (via the "minus" operator). I decided that the best way to achieve this in RLog is with the following:
  rdfs:Resource(u) :- a(x,u), ~rdfs:Literal(u).
So now RLog has negation. Wonder how I'll make that work in the general case?

The next issue is a little trickier. Rule XI (Why Roman numerals? I never worked that out, except that this rule is weird) states that if a predicate URI starts with the RDF domain and an underscore, then it is a ContainerMembershipProperty.
  eg. http://www.w3.org/1999/02/22-rdf-syntax-ns#_1
This isn't quite right, as anything after the underscore is supposed to be a number, but it's not too bad. Sesame seems to get away with this rule.

Since Mulgara is using "magic" predicates for certain operations, it made sense to extend this into RLog:
  rdfs:ContainerMembershipProperty(i) :- i(x,y), mulgaraprefix(i,"&rdf;_").

Fortunately, none of the OWL rules needed anything fancy, though I suspect I may need to when I get deeper into subsumption.

Beaver

I think that I've already discussed the various compiler-compiler options I looked at. To recap, I chose Beaver as an LALR parser, and JFlex as the lexer.

JFlex is under the GPL, which would normally be bad (since Mulgara is OSL), but fortunately they state that any code generated by JFlex can be under any license you like. I don't plan on changing or extending JFlex, so that's fine (I'd be more than happy to contribute back any changes I made).

The incompatibility of the OSL and the GPL means that I can't distribute JFlex to generate the lexing code, but I have two other options. The first is that I just provide the lexing code, and the original .lex file. That would let anyone use the code just fine, since the lexer can just be taken "as is". A developer would only need to download JFlex for themselves if they needed to change the lexing rules.

The other option is to add an Ant task to download JFlex if needed. This seems to be the better, option, but I haven't done it yet.

As far as using Beaver/Flex is concerned, I've finished the parser, and can easily print out the Abstract Syntax Tree (AST). Now I need to write the code that walks over the tree, finds the dependencies, and converts the AST into Krule.

None of it seems to hard, but it's a matter of finding time. Meanwhile, the boys woke up a short time ago, so I'd better go and play "Daddy" for a while...