W3C home > Mailing lists > Public > public-owl-dev@w3.org > October to December 2008

Updates to FuXi (support for Magic Sets, fixes for other modules, etc.)

From: Chimezie <chimezie@gmail.com>
Date: Sat, 20 Dec 2008 22:11:41 -0800 (PST)
Message-ID: <5adce9b6-2a45-40a8-94c1-5082499e9b82@t26g2000prh.googlegroups.com>
To: fuxi-discussion <fuxi-discussion@googlegroups.com>
Cc: public-cwm-talk@w3.org, public-owl-dev@w3.org

I've committed several changes to SVN for FuXi 0.99b (I've annotated
the changes via google code [1]).

This is the last round of major feature addition prior to 1.0 release
candidates.  I had wanted to wait until I finished the Generalized
Magic Set Transformation implementation (Catriel Beeri et.al. 1991.) ,
which was much more difficult than I anticipated. Basically, given a
list of RDF tuples we wish to prove, a ruleset, and a fact graph, the
MST method will return a modified version of the ruleset that
simulates the prolog-like / backward-chained (or top-down) derivation
of the goal(s).  The modified rule should significantly reduce the
number of redundant inferences and the size of the original ruleset.
So, this method can be used (independent) of N3 implementations to
optimize N3 rulesets relative to a particular query and a fact

Running testOWL.py, the following is the percentage that the original
pD ruleset was reduced via application of MST against the test
factGraphs and the expected RDF conclusions:

- OWL/AllDifferent/premises001 (60%)
- OWL/allValuesFrom/premises001 (94%)
- OWL/complementOf/premises001 (87%)
- OWL/differentFrom/premises001 (60%)
- OWL/differentFrom/premises002 (60%)
- OWL/disjointWith/premises001 (60%)
- OWL/disjointWith/premises002 (60%)
- OWL/distinctMembers/premises001 (60%)
- OWL/FunctionalProperty/premises002 ( .. MST doesn't apply .. )
- OWL/FunctionalProperty/premises003 (65%)
- OWL/FunctionalProperty/premises004 (63%)
- OWL/intersectionOf/premises001 (33%)
- OWL/InverseFunctionalProperty/premises002 ( ..MST doesn't apply ..)
- OWL/InverseFunctionalProperty/premises003 (65%)
- OWL/InverseFunctionalProperty/premises004 (63%)
- OWL/inverseOf/premises001 (76%)
- OWL/oneOf/premises002 (.. MST doesn't apply ..)
- OWL/oneOf/premises003 ( .. MST doesn't apply ..)
- OWL/SymmetricProperty/premises001 (87%)
- OWL/TransitiveProperty/premises001 (82%)
- OWL/unionOf/premises001 (88%)
- OWL/unionOf/premises002 (85%)

For example,  OWL/allValuesFrom/premises001 starts with the original
pD ruleset:

[Forall ?SC ?A ?C ( rdfs:subClassOf(?A ?SC) :- And( rdfs:subClassOf(?
C ?SC) rdfs:subClassOf(?A ?C) ) ),
 Forall ?A ?C ( And( rdfs:subClassOf(?C ?A) rdfs:subClassOf(?A ?
C) ) :- owl:equivalentClass(?C ?A) ),
 Forall ?SC ?C ( owl:equivalentClass(?C ?SC) :- And( rdfs:subClassOf(?
C ?SC) rdfs:subClassOf(?SC ?C) ) ),
 Forall ?Y ?C ?B ?M ( owl:differentFrom(?M ?Y) :- And( owl:disjointWith
(?C ?B) ?C(?M) ?B(?Y) ) ),
 Forall ?Q ?P ( owl:FunctionalProperty(?Q) :- And( owl:inverseOf(?P ?
Q) owl:InverseFunctionalProperty(?P) ) ),
 Forall ?Q ?P ( owl:InverseFunctionalProperty(?Q) :- And( owl:inverseOf
(?P ?Q) owl:FunctionalProperty(?P) ) ),
 Forall ?Y ?P ?S ?O ( owl:sameAs(?O ?Y) :- And( owl:FunctionalProperty
(?P) ?P(?S ?O) ?P(?S ?Y) ) ),
 Forall ?Y ?P ?S ?O ( owl:sameAs(?S ?Y) :- And
( owl:InverseFunctionalProperty(?P) ?P(?S ?O) ?P(?Y ?O) ) ),
 Forall ?S ?T2 ?T1 ( owl:sameAs(?S ?T2) :- And( owl:sameAs(?T1 ?T2)
owl:sameAs(?S ?T1) ) ),
 Forall ?P ?T2 ?O ?T1 ( ?P(?T2 ?O) :- And( ?P(?T1 ?O) owl:sameAs(?T1 ?
T2) ) ),
 Forall ?X ?C ?L ?P ( owl:InverseFunctionalProperty(?P) :- And
( owl:oneOf(?C ?L) rdf:first(?L ?X) rdf:rest(?L rdf:nil) rdfs:domain(?
P ?C) ) ),
 Forall ?X ?C ?L ?P ( owl:FunctionalProperty(?P) :- And( owl:oneOf(?C ?
L) rdf:first(?L ?X) rdf:rest(?L rdf:nil) rdfs:range(?P ?C) ) ),
 Forall ?S ?O ( owl:differentFrom(?O ?S) :- owl:differentFrom(?S ?
O) ),
 Forall ?S ?O ( owl:complementOf(?O ?S) :- owl:complementOf(?S ?O) ),
 Forall ?S ?O ( owl:disjointWith(?O ?S) :- owl:disjointWith(?S ?O) ),
 Forall ?tuljFkbB539 ?X ( first:c(?tuljFkbB539) :- And( first:r(?X)
first:p(?X ?tuljFkbB539) ) )]

which is reduced to the following logic program via the MST algorithm:

Forall ?VAR ?X ( first:c(?VAR) :- And( first:c_magic(?VAR) first:p(?X ?
VAR) first:r(?X) ) )

And the 'seed fact' (from the single goal triple) is introduced to
trigger the process:

first:o, rdf:type, first:c_magic

The other rules (which would fire redundantly with a niave
implementation) are removed

Other changes were included and the collective changelog is below.
Most importantly, the OWL test suite has been updated to (by default)
use magic sets to derive the concluded triples for each test.  It adds
a method that demonstrates how to use the new
FuXi.Rete.Magic.MagicSetTransformation (see: [2]).  FuXi's ReteNetwork
instance is now able to build a network from a set of clauses
explicitely, and the DLP transformation method [3] can be used to
transiently generate a logic program from an OWL-DL graph w/out
updating the given network .  Rules with existential variables in the
head are supported via a specific skolemization technique.  The DLP
algorithm was intuitively extended to support generating customized
symmetry rules from owl:SymmetricProperty assertions.  A
FuXi.Horn.HornRules.HornFromN3 method [4]  was added that takes a N3
stream and returns a corresponding list of horn rules. I plan to
update the Wiki with examples of how to use the MST functionality with
(arbitrary) N3  and rules extracted from OWL-DL RDF graphs via DLP.

- added fix for support of 'full sips' (see Ramakrishnan R. (1988)
- added support for performing MST on a set of query literals (not
just one)

- added extent descriptor for classes (returns generator over class
- added equivalence relation between Restriction instances (useful for
symbolic manipulation)

- added HornFromN3 method.  Takes a N3 stream and returns a
corresponding Horn ruleset
- added equivalence / fixed relation for Rule instances

- skipBNodes parameter added to constructor of HashablePatternList
(triple pattern equivalence can
now disregard BNodes in terms - neccessary for skolemization of
existential variables in the head of
a rule)
- added buildNetworkFromClause method to networks for building network
directly from clauses
- added constructNetwork parameter to setupDescriptionLogicProgramming
to allow the return of
corresponding LP rather w/out constructing a network
- added clear method to network
- fixed handling of skolemization of existentials in rule heads

Positive Conditions
- added equivalence operators for DLP clauses (different from horn
- propagated constructNetwork parameter to ExtendN3Rules
- fixes for handling skolem terms in rule heads
- extended DLP to support DL symmetric property assertions

-- Chimezie

[1] http://code.google.com/p/python-dlp/source/list
[2] http://code.google.com/p/python-dlp/source/browse/trunk/fuxi/test/testOWL.py?spec=svn249&r=249#156
[3] http://code.google.com/p/python-dlp/source/browse/trunk/fuxi/lib/Rete/Network.py?spec=svn247&r=247#231
[4] http://code.google.com/p/python-dlp/source/browse/trunk/fuxi/lib/Horn/HornRules.py?spec=svn247&r=247#12
Received on Sunday, 21 December 2008 06:12:23 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:58:17 UTC