Writing

I've been trying to sit down and write for over a week, but each time I try I end up writing code instead. I've even fallen behind reading Slashdot. I've been getting a lot of messages from people wanting to know what happened last week, what our plans are for Mulgara, etc, but I just haven't been able to respond. That's what happens when a developer tries to work in the real world. I handle the real world, and I can handle code, but not at the same time. :-(

For the moment, I have priorities with work that I have to see to, so I'll be concentrating on technical things for a while. However, there are a few things happening with Mulgara, so I'll try to mention them as I go. In the meantime, I'm working on SPARQL queries.

SPARQL

The two main features that we're missing now are OPTIONAL and FILTER. Looking at OPTIONAL some time ago I realized that it's a hybrid between ConstraintConjunction (the inner join aspect), and ConstraintDisjunction (matches on the left side leaving unbound columns). I worked on something similar when I did ConstraintDifference a few years ago, so I know that this is easy. Hence, I put this part off until last.

In the last week or so (in between the meeting in San Francisco, and getting a nasty virus) I've been on filters. Right now I'm down to some classes to represent the operator definitions for all the functions like bound(), isIRI() and regex(). I already have the functionality implemented, but you still need to represent it in an abstract syntax if you're going to construct expressions at query time. So it's all just some boiler plate code to represent the parameters and pass the context on down to any variables that need resolving. After that, I'm on to the unit tests. In an ideal world, I'd test everything but in reality I have less time than that. Many of the functions are so similar that I'll just be testing a good sample of each of them.

Looking at the list in the SPARQL definition, you might think that there aren't too many functions at all, but you would be wrong. For a first approximation, many of the functions have to be reimplemented for each type of parameter. I've even gone to the effort of making sure that working on an <xsd:int> returns an <xsd:int> (when appropriate), and that an <xsd:short> returns an <xsd:short>. Since I was already trying to keep floating point numbers and integers apart, then this seemed to be a natural extension. Then I have to consider the types of numbers typed into the SPARQL query, literal numbers typed in to the query, and variables that get bound to numbers during processing. This raises the complexity considerably.

My first attempt had me doing largish methods that have copious "if (value instanceof ...)" statements in them. This is clunky and brittle. The moment I went to do it a second time, I decided to throw it out, and do it all with maps to functors (where are closures?!?). This actually worked well, and has the advantage of giving short and simple functions, and consistent patterns to follow in implementations. I'd have liked to use generics a little more, but they are really suited for interpreting code you are writing, rather than code that is being structured from a parser. Consequently, in one class I ended up writing a little Ruby script to write the series of functor classes I needed for arithmetic operations! Scary, I know, but it works quite well. It was either that or a series of if/then/else blocks taking me down dark passages I never want to enter.

The frustrating thing is that via autoboxing, you can write the same arithmetic over and over again, and have it do different things. For instance, the expression:

x * y

can result it totally different return types depending on whether x and y are Doubles, Floats, Integers, etc. This is common when programming in Java using the native types (like double and int) but this must be established at compile time, not when processing query. That means you want to have access to every combination of parameters at run time. This can be done with autoboxing, and defining classes with interfaces that return java.lang.Numbers. Then the code x*y can be written over and over, and it means something different each time. Java generics are nice, but they are a long way short of C++ templates, a fact especially obvious when you want to use them on native types (along with a hundred other reasons). But Generics + Autoboxing can sometimes get you some of the way.

OK, so that gave me access to each combination of parameters, but surely there's a better way to do it dynamically? Well, not in Java. The only approaches I've seen in the past either use heuristics to work out which version of arithmetic to run, or else it promotes everything into a standard type (like Double). The latter has arithmetic problems, and gives an inappropriate type for the result. The former can just be complex to read, write, and verify.

The problem comes back the CPU having different instructions for the different forms of arithmetic. A compiler has no problems selecting which one to use, but that is because it has access to the entire library of instructions. Conversely, a parser is not expected to have access to all instructions, leading to the problems I'm talking about. So you either choose a subset of instructions to work with (ie. upcast everything), or else you provide all instructions in a library, and then map the parameters into the correct instruction - either with the heuristic tree or something like a hash map.

Dynamic languages have a much easier time of it. For a start, they usually have all instructions at their disposal in the interpreter. Many (though not all) of them also simplify their numeric types to only a couple of types. Whatever they use, the poor programming schmuck writing their own interpreter (that would be me) need only write x*y and let the dynamic language developer work out what he wanted. At the very least, we can emit it in a string and do an eval().

Oh well, I shouldn't complain. I have all the functions written out (via Ruby) and a hash map that lets me get what I need trivially. With the exception that there is a lot of machine generated code that looks like the same thing over and over, the whole system comes down to just a few lines of easily verifiable code - which is what I like to see. Following the code path you'll see that any kind of operation just goes through a few steps and it's done.

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.