More Programmable Logic

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

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

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

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

Krule Configuration

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

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

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

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

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

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

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

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

Iterations

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

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

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

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

SKOS

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

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

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

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

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

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

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

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

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

General Acceptance

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

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

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

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

Integration

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

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

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

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

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

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

Testing

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

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

The TQL command for this was:

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

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

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

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

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

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

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

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

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

Collections

So I'm trying to work out what is necessary in OWL, and what is necessary and sufficient. Actually, I just want "necessary and sufficient", but knowing the difference helps. :-)

Anyway, while working through this blog, I worked it out. But it probably won't hurt to write it down anyway...

I had narrowed my problem down to the following:

If I had a Collection like:

  <rdf:Description rdf:about="http://example.org/basket">
    <ex:hasFruit rdf:parseType="Collection">
    <rdf:Description rdf:about="ex:banana"/>
    <rdf:Description rdf:about="ex:apple"/>
    <rdf:Description rdf:about="ex:pear"/>
  </ex:hasFruit>

Then this is translated to:

<ex:basket> <ex:hasFruit> _:l1 .
_:l1 <rdf:first> <ex:banana> .
_:l1 <rdf:rest> _:l2 .
_:l2 <rdf:first> <ex:apple> .
_:l2 <rdf:rest> _:l3 .
_:l3 <rdf:first> <ex:pear> .
_:l3 <rdf:rest> <rdf:nil> .

Now is this list open or closed? This is an important question for OWL, since collections are used to construct sets such as intersections.

If it's open, then I could add in another piece of fruit...

<ex:basket> <ex:hasFruit> _:l0 .
_:l0 <rdf:first> <ex:orange> .
_:l0 <rdf:rest> _:l1 .

This would work, but it implies that I can infer that every element of the list can be directly connected to the basket. i.e.

<ex:basket> <ex:hasFruit> _:l0 .
<ex:basket> <ex:hasFruit> _:l1 .
<ex:basket> <ex:hasFruit> _:l2 .
<ex:basket> <ex:hasFruit> _:l3 .

Now this makes sense to me, but I don't recall seeing it anywhere in RDF. For instance, it's not in the semantics document for RDF or RDFS. The section on Collections does say that RDF does not require any well-formedness on the structure of the list (indeed, branched structures are explicitly mentioned), but since only OWL-Full allows arbitrary RDF structures, it isn't generally applicable to what I'm interested in.

I'd come to this question while I was checking that an owl:intersectionOf with "complete" modality was necessary and sufficient. I presumed that it was, but it doesn't hurt to check. After all, I've been caught out in the open world before. :-)

I first went to the abstract syntax for class axioms to find out how "partial" modalities were encoded, vs. "complete". The triples encoding of the abstract syntax shows that "partial" is simply a list of rdfs:subClassOf statements for each element in the intersection, while "complete" uses an RDF collection. Actually, the expression "SEQ" is used, but sequences are then described as being of type rdf:List, and not rdf:Seq (which, incidentally, are extensible, but no OWL aficionado will have anything to do with them, so I knew that wasn't a possibility).

Now to make sure that "complete" really is complete, I needed to ensure that lists couldn't be extended.

There is a hint that lists can't be extended in OWL-DL in the OWL Guide:
"If we wanted to add a new winery in some other ontology and assert that it was disjoint from all of those that have already been defined, we would need to cut and paste the original owl:AllDifferent assertion and add the new maker to the list. There is not a simpler way to extend an owl:AllDifferent collection in OWL DL. In OWL Full, using RDF triples and the rdf:List constructs, other approaches are possible."

That raises the intriguing possibility that in OWL-Full an intersection can never be complete. But since OWL-Full is undecidable anyway, I guess that's not something I need to worry about.

That then brought me back to the description for Set Operators which I haven't read in a while. And in reading this I realized that I was a moron for forgetting it...
The members of the class are completely specified by the set operation.

The text then goes on to describe that an individual that is a member of each element of an intersection is then a member of the intersection. In other words, membership in each element is a necessary and sufficient condition for membership in the intersection. Had lists been open, then membership would have merely been necessary, but not sufficient, since there could be another class in the intersection that has not been asserted (yet).

So complete is indeed "necessary and sufficient". But if I'd just looked at the Guide in the first place I could have saved myself a bit of time. Sometimes I feel like an idiot... and then I go and compound it by writing about my stupidity on my blog.

Oh well, this SPARQL implementation won't write itself. I'm down to OPTIONAL - which I expect to take about an hour, and the algebra integration. I'd better make that transformation clean, as I expect to be doing it again soon for the Sesame algebra.

Somehow I also need to find some time to finish writing that paper about 2 column RDF indexes. Did I mention that I think they're a cool idea? :-)

Theory and Practice

The development of OWL comes from an extensive history of description logic research. This gives it a solid theoretical foundation for developing systems on, but that still doesn't make it practical.

There are numerous practical systems out there which do not have a solid theoretical foundation (and this can sometimes bite you when you really try to push a system), but can still be very useful for real world applications. After all, Gödel showed us that every system will either be incomplete or inconsistent (maybe that explains why Quantum Physics and General Relativity cannot both be right. Since Gödel's Theorem requires that there be an inconsistency somewhere in our description of the universe, then maybe that's it). :-)

If theoretically solid systems not an absolute requirement for practical applications, then are they really needed? I'd like to think so, but I don't have any proof of this. In fact, the opposite seems to be true. Systems with obvious technical flaws become successful, while those with a good theoretical underpinning languish. There are many reasons for failure, with social and marketing being among the more common. Ironically, the problems can also be technical.

John Sowa's essay on Fads and Fallacies about Logic describes how logic was originally derived from trying to formalize statements made in natural language. He also mentions that a common complaint made about modern logic is its unreadability. But this innocuous statement doesn't do the evolution justice. Consider this example in classical logic:

• All men are mortal.
• Socrates is a man.
• Therefore: Socrates is mortal.

Now look at the following definition of modal logic:

Given a set of propositional letters p₁,p₂,..., the set of formulae of the modal logic K is the small set that:

• contains p₁,p₂,...,
• is closed under Boolean connectives, ∧, ∨ and ¬, and
• if it contains Φ, then it also contains □_Φ and ◇_Φ.

The semantics of modal formulae is given by Kripke structures of M=⟨S,π,K⟩, where S is a set of states, π is a projection of propositional letters to sets of states, and K is the accessibility relation which is a binary relation on the states S. Then, for a modal formula Φ and a state s∈S, the expression M, s⊨Φ is read as "Φ holds in M in state s". So:

• M, s ⊨ p_i     iff s ∈ π(p_i)
• M, s ⊨ Φ₁ ∧ Φ₂    iff M,s ⊨ Φ₁ and M,s ⊨ Φ₂
• M, s ⊨ Φ₁ ∨ Φ₂    iff M,s ⊨ Φ₁ or M,s ⊨ Φ₂
• M, s ⊨ ¬Φ     iff M,s ⊭ Φ
• M, s ⊨ □_Φ     iff there exists s' ∈ S with (s,s') ∈ K and M,s' ⊨ Φ
• M, s ⊨ ◇_Φ     iff for all s' ∈ S if (s,s') ∈ K, then M,s' ⊨ Φ

(Courtesy of The Description Logic Handbook. Sorry if it doesn't render properly for you... I tried! The UniCode character ⊨ (⊨) is rendered in Safari, but not in Firefox on my desktop - though it shows up on my notebook.)

While several generations removed, it can still be hard to see how this formalism descended from classical logic. Modal logic is on a firm theoretical foundation, and it is apparent that the above is a precise description, yet it is not the sort of tool that professional programmers are ever likely to use. This is because the complexity of understanding the formalism is a significant barrier to entry.

We see this time and again. Functional programming is superior to imperative programming in many instances, and yet the barrier to entry is too high for many programmers to use it. Many of the elements that were considered fundamental to Object Oriented Programming are avoided or ignored by many programmers, and are not even available in some supposedly Object Oriented languages (for instance, Java does not invoke methods by passing messages to objects). And many logic formalisms are overlooked, or simply not sufficiently understood for many of the applications for which there were intended.

After working with RDF, RDFS and OWL for some years now, I've started to come to the conclusion that these systems suffer from these same problems with the barrier to entry. It took me long enough to understand the complexities introduced in an open world model without a unique name assumption. Contrary to common assumption, RDFS domain and range is descriptive rather than prescriptive. And Cardinality restrictions rarely create inconsistencies.

Part of the problem stems from the fact that non-unique names and an open world are a complete different set of assumptions from the paradigms that programmers have been trained to deal with. It takes a real shift in thinking to understand this. Also, computers are good at working with the data they have stored. Working with data that is not stored is more the domain of mathematics: a field that has been receiving less attention in the industry in recent years, particularly as professionals have moved away from "Computer Science" and into "Information Technology". Even those of us who know better still resort to the expediency of using many closed world assumptions when storing RDF data.

Giving RDF, RDFS, and OWL to the general world of programmers today seems like a recipe for implementations of varying correctness with little hope of interoperability - the very thing that these technologies were designed to enable.

However, the RDF, RDFS and OWL were designed the way they are for very sound reasons. The internet is and open world. New information is being asserted all the time (and some information is being retracted, meaning that facts on the web are both temporal and non-monotonic, neither of which is dealt with by semantic web technologies, but let's deal with one problem at a time). There are often many different ways of referring to the same things (IP addresses and hostnames are two examples). URIs are the mechanism for identifying things on the internet, and while URIs may not be unique for a single resource, they do describe a single resource, and no other. All of these features were considered when RDF and OWL were developed, and the decisions made were good ones. Trying to build a system that caters to programmers presumptions by ignoring these characteristics of the internet would be ignoring the world as it is.

So I'm left thinking that the foundations of RDF and OWL are correct, but somehow we have to present them in such a way that programmers don't shoot themselves in the foot with them. Sometimes I think I have some ideas, but it's easy to become disheartened.

Certainly, I believe that education is required. To some extent this has been successful, as I've seen significant improvement in developers' understanding (my own included) in the last few years. We also need to provide tools which help guide developers along the right path, even if that means restricting some of their functionality in some instances. These have started to come online, but we have a long way to go.

Overall, I believe in the vision of the semantic web, but the people who will make it happen are the people who will write software to use it. OWL seems to be an impediment to the understanding they require, and the tools for the task are still rudimentary. It leaves me wondering what can be done to help.

OWL Inexpertise

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

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

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

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

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

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

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

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

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

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

---

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

Nodalities

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

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

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

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

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

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

People

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

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

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

Sorry to those I didn't mention.

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

Architecture

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

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


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

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

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

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

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

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

Open Source

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

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

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

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

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

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

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

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

OWL with Rules

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

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

There are the obvious rules like:

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

But the real value would be in rules like:

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

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

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

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

Another SemTech Day

Writing about SemTech is taking so long because I've had to do a lot of offline writing as well (not to mention my day job). Quite a bit of my writing was Mulgara related, so it'll end up here shortly - promise.

I'm still only halfway through recalling the conference. I suppose that's because a lot happened. More importantly, I met a lot of people, all of whom I wish I could have given more time.

For instance, Henry Story and I had a series of short discussions, involving RDF, Sun, and Mulgara. He was interested in learning more about Mulgara, but the lack of SPARQL was a major impediment for him. I know how important that feature is, so it's something I hope we have soon. Indy is working on that in his own time, so we may have something soon. However, Indy is on vacation at the moment, so I won't hear any more about it until he gets back. Henry also introduced me to one of the managers at Sun, pointing out that Mulgara was developed way back at the start of 2001, and was using NIO from the outset. He didn't seem to know much about RDF, but was interested in our early use of NIO. We had a brief discussion about 64 bit support (which we manage with NIO, but not without jumping through hoops). I was pleased to hear that Sun are planning on new APIs to address the 64 bit problem.

I kept trying to find time (over lunch for instance) when I could sit down and have a long and uninterrupted conversation with Henry, but somehow it never eventuated. Maybe next time. In the meantime, I now have a face to put with his emails. Somehow, having spoken to a person about their work gives their emails much more meaning.

Another person I wanted to speak with was Eyal Oren, due to his work on ActiveRDF. One of the places that Mulgara needs to be used is as the backend for web applications, and in this day and age that means Ruby on Rails. SOAP support (which we have) is only a stopgap measure, and doesn't cut it. We need a real API for non-Java languages. In fact, given the importance of RoR, I fully support an API specifically for Ruby, and ActiveRDF looks like the best option, particularly since it's starting to get wider use.

I saw Eyal from a distance on the first day, but I wasn't sure that the guy I was looking at was the same one I'd seen in Eyal's photo. Even when I realized it was definitely him, I always seemed too busy to give him the time and attention I wanted, so I held back. Finally, on the last day I introduced myself, and we had a productive conversation. The guys in ActiveRDF would like to get another store behind their API, so our goals are aligned there. Also, Eyal tells me that they only use simple SPARQL queries, so these might already parse fine as TQL (since Andrae added features to the parser to make it mostly compatible). We have someone new at fourthcodex who needs to learn about programming with and in Mulgara, so this may be one of the earlier tasks we set him (not the very first task - I'd like him to get some experience with simpler things first).

I have to get in touch with Eyal soon to make this happen.

Wednesday Morning

So after being given 2 beers and 1 (large) glass of red wine on Tuesday night (all over a period of 6 hours), I thought I'd be fine by morning. After all, I'd had much more on Monday night, with no ill effects (surprisingly). Yet, I woke up on Wednesday feeling a little "seedy". The beer was the same I'd had on Monday, so it must have been the red wine. I'll have to be more careful when someone offers me a glass like that (even if it was my boss).

The consequence was that I didn't feel like concentrating during the first session. I'd picked something on NLP. I've done a little work here, but it's not that relevant to me at the moment, so I decided to catch up on emails and RSS instead. I guess that turned out well, as this was when I learned about Danny's new job at Talis, before meeting the Talis guys just a little later that morning.

I ran into Henry again just before the next session, and we went into the presentation given by Susie Stephens, now from Eli Lilly (despite the hundred bios on the web which still say she's from Oracle) and Jeff Pollock from Oracle, who were discussing practical (and commercial) "Enterprise" semantic web systems. Features of various systems were discussed, such as Dartgrid mapping RDBMSs to one another (this had a nice accessible look to it), TopQuadrant's TopBraid IDE for integrating RDBMSs, and also a recap on the WebMethods acquisition of Cerebra to gain their RDF product (WebMethods had been looking at TKS before Tucana went the way it did). I think I was the only person in the room who hadn't realized that Jeff used to work for Cerebra.

Jeff also pointed out a number of commercial RDF systems, including the TKS system from Northrop Grumman, which left me bemused. We already have some improved features over TKS, but I'm looking forward to leaving it in our dust. Should be Real Soon Now. ;-)

Next came lunch, and another exhibit session. Fortunately, this was less crazy than the night before, so there was opportunity to take a break in order to eat. Unfortunately it conflicted with a couple of commercial sessions, and dragged into a standard conference session that I wanted to get to. These included a presentation from AllegroGraph that would have been interesting to see, and talks by both Eyal and Elisa Kendall from Sandpiper Software. Fortunately, I got to hear Elisa speak later, even if it was just a SIG.

Reverse NLP

The next session I made was called Applications of Analogical Reasoning and was by John Sowa from VivoMind Intelligence. I'd heard of John before, but wasn't sure what to expect in this session. Regardless, this was the only session of the whole conference that made me take a step back and say, "Wow".

John started out with the quote,
  A technique is a trick you use twice.
The idea is that analogies allow us to use tricks (or techniques) in multiple places that may not appear to be equivalent at first glance.

Analogical reasoning is the process of finding correlations for objects and relationships in separate ontologies. He provided an example of an analogy discovery system called VAE, which was applied to WordNet to compare the concept types of cat and car. The automatically generated result was:

Cat	Car
head	hood
eye	headlight
cornea	glass plate
mouth	fuel cap
stomach	fuel tank
bowel	combustion chamber
anus	exhaust pipe
skeleton	chassis
heart	engine
paw	wheel
fur	paint

The correlation of paths of relationships, and any similarities along the way can help these algorithms that search for analogies. So "paws" matched to "wheels" because they had a similar function, and there were 4 of each of them. The algorithms specifically cater for extra, or missing, elements along path, with these elements being recorded as a "deviation". So the paths of:

Cat: mouth, esophagus, stomach, bowel, anus
Car: fuel cap, fuel tank, combustion chamber, muffler, exhaust pipe

matched, but received reduced confidence due to the esophagus not matching anything in the car, and the muffler not matching anything in the cat.

This is all given in much more detail in a paper written by John on his site.

Anyway, it all sounded good, but what can it be used for?

I didn't record all the details (so apologies if I get some of the specifics wrong), but the example given was a task of documenting a banking system in preparation of merging with another system. There were some 30 years of development with source code in several languages, including Cobol and Java. Every stage of development had used extensive documentation, the process had continued over 30 years, building up to a corpus of 100MB of documentation. Consequently there was a need for new documentation in the form of:

• A glossary.
• Data flow diagrams.
• Process architecture.
• System context diagrams.
• Data dictionary.

All of this was supposed to be done in about 6 weeks (a seemingly impossible task).

It is well understood that NLP isn't good enough today to understand the documentation to the extent required here. However, one of the developers working on this decided to approach the problem laterally. Instead of trying to parse the unstructured documentation, instead he adjusted the NLP system to parse the source code. Of course, the source code must be parseable else it would be much good as source code, would it? The results were then put into a concept graph, which was combined with ontologies to provide the "analogy" for the 100MB of documentation, which could then be parsed with relative ease.

I love it when someone shifts my brain sideways with an idea like this.

Initially the developers asked the system to flag if the deviation between the concept graphs of the code and the documentation was greater than a couple of percent. These were then perused by hand. It didn't take long to decide that the system was proceeding just fine, and the deviation cut-off was increased to something significantly higher. However, a couple of items were still flagged, indicating possible contradictions that had to be manually reviewed to figure out why.

One such item started with the following pair of facts:

• No humans are computers
• All employees are human

The problem was flagged when the system tried to describe 2 employees as computers. After carefully going back through the system it was discovered that 20 years before an employee in one department received assistance from 2 computers. However, at the time there was no way to bill for computer time. The workaround was to name the computers "Bob" and "Sally" and enter them into the system as employees. The unintended consequence of this was that Bob and Sally had been issued paychecks for 20 years that they had not been cashing!

So not only did this approach successfully document the system, it also discovered contradictions between the document and the implemented system. This was my "Wow" moment.

Evening

The keynote didn't really capture me that afternoon, so it was tempting when the others from fourthcodex trid to invite me to lounge on the pool deck. But I stuck with it, and made it into the talk on Advanced OWL by Deborah McGuinness from Stanford and Elisa Kendall (whom I mentioned earlier).

When I first considered postgraduate research at UQ, I tried to get some idea of the research background of those who might be interested in supervising me. Bob was at the top of the list, and in looking him up I found that he had done a lot of work with IBM Almaden, DSTC, and Sandpiper Software. The last was specifically with Elisa Kendall. I was fortunate enough to be introduced to her on Tuesday evening, so I was pleased to get a chance to see one of her talks.

In this case, the talk was really a Special Interest Group meeting (SIG) where various details of OWL were discussed, rather than the formal "Sessions". I would have gained more if there was some discussion about OWL 1.1, which I'm only just starting to look at seriously. However, I was already pretty comfortable with the various concepts in OWL that were being discussed.

The one point I picked up on was to be very careful about using owl:InverseFunctionalProperty (IFP) as it can lead to OWL Full. This is worth noting, because many modeling/schema environments want to use IFP to simulate the RDBMS concept of the "primary key" of an object. However, IFP cannot be used on datatype properties in OWL-DL, which is what you usually want IFP for if you want to use it to indicate a primary key. Not using IFP on datatype properties is well documented for OWL-DL, but the whole "primary key" thing is likely to lead to forgetting this rule in heat of moment when just trying to make it work.

I spent the rest of the time working out that I can build a rule for owl:IntersectionOf using the TQL minus operator. Unfortunately, the resulting query is nested into several parts (of the form: A and B minus (C and (D minus E))), making me think that I should really write a resolver to do it easily. Algorithmically it's easy: once you have an intersection, you just have to check that an object has all of those types in order to meet it. The hard part of a new resolver is usually the syntax for providing everything that it needs. In this case, how do I tell the resolver which graphs to query?

Zepheira

That night was a little soirée put on by Zepheira in a hotel suite backing onto the pool deck. I was invited by Bernadette, but told that it would be focused on potential clients, and I may not want to stay long. Besides, it would only be running for 90 minutes.

Ha!

The party had included people of all ilks engaged in everything from flirting to deep technical discussions on semantic technologies. The latter by the younger, single set, and the former by at least half the room. A couple of times I noticed both going on in the same conversation. The 90 minute limit came and went, and the party went on until sometime around midnight. I got to meet Dave Beckett (mentioned several blog entries ago), several W3C notables, and a number of people from all over, each with their own contribution to make to the semantic web. It was a lot of fun.

Due to the exhibit that day, I was still wearing my fourthcodex shirt. After the exhibition sessions I knew that fourthcodex had products providing something unique and useful, and there had been some buzz around what we were offering. But I was surprised when seemed to be accorded minor celebrity status in some areas of the room. I was even cornered by one potential client who wanted to grill me over the features of our products. Luigi would have been thrilled.

Oracle

I also got to speak with Susie Stephens about the Oracle RDF implementation.

Susie's a lovely girl, and I enjoyed the conversation. She is also on a horrible conference circuit at the moment, spending the previous 4 weeks going from conference to conference, and about to head the Austria for another one the following week. She'd been getting a couple of days at home to water the plants every few weeks, and then she was off again. It seems a little rough of Eli Lilly to put Susie through this immediately after joining them, but she seemed to be coping. She had my sympathy nonetheless.

I have lamented before that Oracle had the opportunity to do this right, but instead their implementation has become an advertisement for using Mulgara. The reason is because the implementation is done entirely at the application layer. TKS/Kowari/Mulgara was developed specifically because we discovered that this approach didn't work, and we reasoned that a storage layer specifically designed to handle triples rather than a table of arbitrary arity could be much more efficient. I even recall discussing this with DavidM in the Toowong food court, back in 2000. <Insert nostalgia here>

Now Oracle have pretty much captured the scalable data storage market, so they should have the know how and resources to build the appropriate structures that would make an RDF system fly. But instead they build it at the application layer. My question was, "Why?"

Susie explained that it was her who built the RDF layer. She's a biologist, and she built it as a tool for another project she was working on at the time. The RDF layer is actually built on Oracle's Network Database layer (which is also built at the application layer). So while it offers nice abstraction, this is where the scalability fails.

Susie didn't initially anticipate that her code would go into wide circulation. However, it was apparently in the right place, at the right time, and even showcased the Network Database layer. So the powers-that-be picked it up and ran with it. The rest is history.

Conference Discussions

A couple of ideas came out of SemTech which I wanted to write down.

Mulgara Reasoning

The first is the reasoning engine in Mulgara. I've been thinking for a little while that we wanted more than one reasoner, but I've finally worked out what we want and why:

1. The Krule engine, for running OWL inferencing rules scalably over large TBox and ABox sets after loading. OK, I have a personal attachment to this, but it works very well, for several reasons - all of which will be mentioned in my upcoming thesis. :-)
2. A Rete engine, for change management. This is required for data that is coming into an existing system. Running the full set of rule calculations in this case is prohibitively expensive, so a system that handles changes efficiently will be important. This will be based on Krule (since Krule uses Rete principles, but leverages the indices instead of using memory). I'm also hoping to use some ideas from Christian's work, if I can. Adding data isn't really an issue, but deleting it efficiently is trickier.
3. A tableaux reasoner. While most queries are managed quite well by inferred data, there are some questions that cannot be solved without infinite inferences. This happens when there are two or more alternate paths that could satisfy a query, and the ontology describes that one of the path will be taken, but does not provide the details of which one. The classic one described in chapter 2 of the DL handbook as the Oedipus example. For this reasoner I want to use Pellet.

I noticed that all the professional systems that are using tableaux reasoners are using Racer. This isn't an option for Mulgara, as Racer is a commercial product. However, Pellet has some unique features which make it quite worthwhile. It stays up to date with the standards very well, and the OWL debugger has some really valuable features going for it. Finally, you never know, but I might be able to find some way to hook it into the indexes to let it do some of the tableaux reasoning on disk. I don't know about that one, but you never know.

Mulgara Security

Mulgara has never had security, but the hooks have always existed. In the commercial product, authentication and authorization was just handled with JAAS. Once these were established, then an RDF description of the accessible models for the current user could be intersected with the models requested.

Since JAAS is easy to implement, I've been wondering about putting this in again. There may be a bit of missing code (or code that suffered bit-rot) but the idea of performing the intersections is an easy one, so it wouldn't be hard. However, David told me that he'd heard from a few people that the JAAS approach is the wrong one to take.

It seems that security conscious people don't like security being managed in the database. Fair enough. So where do we put it?

David had the idea that maybe we put permissions into the database, as always, but then access and authentication gets done outside of the store, in a gateway interface. Any incoming queries to this interface can be modified to intersect on the models accessible by the currently authenticated party. Any RDF databases that perform efficient model intersections (ie. Mulgara) would work well, while everyone else would merely work correctly.

David thinks this sounds like a good open source project. I like the idea so much that I just had to write it down. It would be very cool to provide something like this for every SPARQL compliant database.

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...