Wednesday, September 15, 2004

My health has been terrible today, so my writing here will be necessarily brief.

Today was spent converting the OWL Lite Horn clauses into iTQL. Mostly easy, but it come up with a couple of surprises.

First of all, it seems that it is quite easy to convert from simple DL (description logic) statements into iTQL. An informal set of rules to do this results in something like:

  • The head of a DL statement gets translated directly to a "select" clause in iTQL.
  • Property statements, which are binary functions, are the only function type allowed. Functions with three or more parameters are not permissible.
  • Instance declarations and variable restrictions are the only other allowable constructs.
  • Instance declarations get converted into RDF "type" statements.
  • Property statements get converted into RDF statements of "subject,property,object".
  • Variable restrictions are converted into RDF statements using iTQL "magic" predicates.
Following these rules is actually quite simple, and I was able to get through many of them today. However, there were a couple of occasions when it is better to step outside of these rules.

A transitive predicate like owl:subClassOf can find a set of inferred predicates with an iTQL query like:
select $x <owl:subClassOf> $z

from source
where $x <owl:subClassOf> $y and $y <owl:subClassOf> $z;
This will require the rules engine to iteratively insert the results of this query until the query generates no new statements. To optimise this into a single operation we have created the trans() function in iTQL:
select $x <owl:subClassOf> $y

from source
where trans($x <owl:subClassOf> $y);

Almost all of the conversions that I mentioned above could be done automatically. This would be great, as it would let us create a restricted Horn clause interpreter for Kowari. However, finding special cases for optimisation, like transitivity, could get very difficult in an automated interpreter. Failure to find these special cases would not even show up as a bug, as the program would execute correctly, just non-optimally.

Another problem is in the limitations of DL. For instance, the owl:transitiveProperty property can be applied to properties in OWL, but this is illegal in DL. The DL for owl:transitiveProperty is:
  P(X,Z) :- P(X,Y), P(Y,Z).
This is fine, as far as it goes, but it needs the system to apply to every possible "P" in the datastore. This would occur outside of the DL framework. What would be ideal would be something like:
  P(X,Z) :- P(X,Y), P(Y,Z), transitiveProperty(P).
But this is illegal, as "P" is a property, not a class.

Fortunately, iTQL doesn't have any such restriction, and the code can be created accordingly:
select $x $p $z

from source
where $x $p $y and $y $p $z and $p <rdf:type> <owl:transitiveProperty>;
Of course, since this is a transitive property (by definition) and we have a backward chaining optimisation for that kind of operation, then it should be possible to further optimise this particular example:
select $x $p $z

from source
where trans($x $p $z) and $p <rdf:type> <owl:transitiveProperty>;
However, trans() wasn't really written with the idea of a variable predicate in mind, so I'll have to lower its priority during execution to make sure that the predicate variable gets bound before it gets resolved. I think this will make it work correctly. SR agrees that it should.

Language Restrictions
While I'm discussing restrictions on DL, I should point out an observation that SR made. I mentioned that Kowari does not support the existential quantifier (as DL systems are unable to express this). SR pointed out that while RDF does not support this, Kowari is quite capable of it. For instance, to declare that a node has a property, all that is needed is to include a statement which has that node as the subject, and a blank node as the property. It may be possible later to resolve the blank node to be the "sameAs" another property, but in the meantime it provides existential quantifier functionality.

Unfortunately, the interfaces into Kowari do not permit a blank node to be a property (or predicate). This is simply due to the standard RDF class hierarchy which we are using. Similarly, it is not possible to use a literal as a subject, although the underlying database supports it. I'll confess that this last restriction can be frustrating, as it prevents the provision of types on literals using RDF statements.

Because there are some useful things to be done with Kowari when these restrictions are not in place, SR, AN, and I had a short discussion about providing a less restricted version of the interfaces. With such a system, and a supporting language, it may be possible to come very close to a complete second order predicate logic system.

This then brought me back to Monday's discussion with Bob, when he suggested that I work out the differences between iTQL, descriptive logic, and second order predicate logic (description logic and second order predicate logic have some overlap, but some features are exclusive). Working out where iTQL overlaps with these systems can help us work out what iTQL needs to have added. It can also help us work out the tradeoffs involved with some features, particularly when working out which features will be impossible when another feature gets added. It should also help me to follow the DAWG a little better.

The more I look at iTQL the more I think that it may be possible to get a very good degree of overlap of the two competing logic systems. I don't pretend that we can squeeze in every feature of both, but I've already been shown that some features which I thought were solely the domain of only one system or the other, can all be expressed in iTQL.

No comments: