FOL Axiomatic semantics of DL and RETE - was Berkeley DB is a non-relational high-performance system/paradigm

On Fri, 15 Sep 2006, William Bug wrote:
> I also believe Chemezie done very useful work in this arena 
> (http://copia.ogbuji.net/blog/keyword/data), though,
> again, he'd be able to tell us more specifically how relevant it is to 
> OWL-based applications.

Most of my recent rumination on reasoners has been shaped 
first by Benjamin N. Grosof, Ian Horrocks, and Raphael 
Volz's 2003 paper 'Description Logic Programs: Combining Logic Programs with 
Description Logic' [1], by the work done by Bijan Parsia, Yarden 
Katz, and Kendall Clark on Pychinko [2] , and by Jos Deroo's set of OWL 
rules [3].

Pychinko was the first attempt (that I know of) to implement Notation 3 
reasoning with Charles Forgy's RETE algorithm, with *very* impressive 
performance results (which should come as no shock to those familiar 
with the superiority of the RETE algorithm).

Unfortunately, most work in this area was focused on either adhoc rules - 
standard expert system scenario - or rules written specifically to express 
DL semantics.  Jos Deroo's great work with euler has 
demonstrated that the OWL & RDF test cases can be passed by an explicit 
set of N3 rules that express DL semantics.

There is ofcourse a concern with the use of N3 as the KR language - since 
it's not 'officially' sanctioned, but my preference for it is mostly that 
it more akin to Horn logic and full FOL than vanilla RDF/OWL.  The 
additional expressiveness is very valuable for scenarios that require this 
- DL reasoning primarily.

Ofcourse, as articulated in 'Description Logic Programs: Combining Logic Programs with Description 
Logic', not *all* of DL can be expressed by such a transposition, but 
there is plenty of precendent in mappings from DL to FOL - which can be 
expressed in N3 rules (and a good portion of which has already been 
captured in the rules used to pass the OWL/RDF tests).

Along this line, I've been working [5] on a second generation (if you 
will) attempt to implement a RETE-like N3 reasoning algorithm (it must be 
called RETE-like because the original algorithm isn't even FOL-oriented).

The main problems I've run into are not with the function-free horn-like subset of Notation 3 (where the 
only builtins are filters and not N-ary functions) but with the issues of 
variable dependence in a forward chaining system when you attempt to 
support n-ary 'functions' on top of the RETE algorithm.  It begins to feel more like a bastardization of 
the algorithm that was really only meant for pattern matching.

This is mostly not an issue with DL semantics as a *majority* of it can be 
expressed in function-free logical rules.

Ultimately, in my opinion, I think there is much value in research in this 
area due to the unprecedented ability for logic programming algorithms 
such as RETE (and it's derivatives RETE II, TREAT, SOAR) to handle *very* 
large scale facts and rules.  And the reality is that the set of logic 
rules that express DL semantics (mappings from DL to FOL) are quite 
miniscule compared to the normal rulesets that logic programming systems 
are built to handle and so the great potential exists to:

  - handle *much* larger fact bases and ontologies than standard tableaux-based reasoners
  - develop expert systems that allow the use of *both* adhoc rulesets in tandem with DL axiomatic rulesets

This latter point could even accomodate reasoning scenarios that fall 
outside the capabilities of DL (such scenarios are well outlined in the first paper)

My $0.02 (plus a little more)

[1] http://citeseer.ist.psu.edu/grosof03description.html 
[2] http://www.mindswap.org/~katz/pychinko/
[3] http://lists.w3.org/Archives/Public/semantic-web/2005Aug/0059.html
[4] http://www.w3.org/2000/10/swap/doc/CwmBuiltins
[5] http://copia.ogbuji.net/blog/2006-07-14/fuxi-mapping-from-rete-to-n3

Chimezie Ogbuji
Lead Systems Analyst
Thoracic and Cardiovascular Surgery
Cleveland Clinic Foundation
9500 Euclid Avenue/ W26
Cleveland, Ohio 44195
Office: (216)444-8593
ogbujic@ccf.org

Received on Friday, 15 September 2006 17:59:25 UTC