|
|
FuXi
FuXi (pronounced foo-shee) is a forward-chaining production system for Notation 3 Description Logic Programming.
DOAP file: /trunk/fuxi/FuXi.rdf
requires: RDFLib 2.4.0 - available: debian
Introduction
FuXi (pronounced foo-shee) is a forward-chaining production system for Notation 3 Description Logic Programming. It is implemented as a companion to RDFLib – which it requires for its various RDF processing.
What is with the Name?
In the beginning there was as yet no moral or social order. Men knew their mothers only, not their fathers. When hungry, they searched for food; when satisfied, they threw away the remnants. They devoured their food hide and hair, drank the blood, and clad themselves in skins and rushes. Then came Fu Hsi and looked upward and contemplated the images in the heavens, and looked downward and contemplated the occurrences on earth. He united man and wife, regulated the five stages of change, and laid down the laws of humanity. He devised the eight trigrams, in order to gain mastery over the world.
Originally, it was an idea to express the underlying constructs of the Yi Jing / I Ching in Description & First Order Logic in order to reason over them.
= README =0.85b.dev-r23
Details
Semantics
New: FuXi has a sketched out formal semantics (based on classic Logic Programming), see: FuXiSemantics
Packages
- Rete.Network: Rete network
- Rete.Proof: Proof generation / serialization
- Rete.DLP: Description Logic Programming core
- Horn: RIF Horn rules core API
- Syntax.InfixOWL: InfixOWL API
Background of RETE and RETE/UL Algorithms
It relies on Charles Forgy's Rete algorithm 4 for the many pattern/many object match problem. It also implements algorithms outlined in the PhD thesis (1995) of Robert Doorenbos:
Production Matching for Large Learning Systems.
Robert's thesis describes a modification of the original Rete algorithm that (amongst other things) limits the fact syntax (referred to as Working Memory Elements) to 3-item tuples (which corresponds quite nicely with the RDF abstract syntax). The thesis also describes methods for using hash tables to improve efficiency of alpha nodes and beta nodes.
An introductory description from the above:
Rete (usually pronounced either "REET" or "REE-tee," from the Latin word for "network") deals with a production memory (PM) and a working memory (WM). Each of these may change gradually over time. The working memory is a set of items which (in most systems) represent facts about the system's current situation - the state of the external world and/or the internal problem-solving state of the system itself. Each item in WM is called a working memory element,or a WME.
The production memory is a set of productions (i.e., rules). A production is specified as a set of conditions, collectively called the left-hand side (LHS), and a set of actions, collectively called the right-hand side (RHS).
Python Idioms (hashing efficiently)
- compiles an RDFLib N3 rule graph into AlphaNode and BetaNode instances
- takes a fact (or the removal of a fact, perhaps?) and propagates down, starting from it's alpha nodes
- stores inferred triples in provided triple source (an RDFLib graph) or a temporary IOMemory Graph by default
Like RDFLib, FuXi is very idiomatic and uses Python hash / set / list mechanism to maximize the matching efficiency of the network. The extent of the efficiency has not been fully explored and there is much more that can be done to improve the already impressive performance.
Network
Rete "Legend"
An OWL/RDFS Example
FuXi's Network intances can be exported to a Graphviz DOT file and rendered to any image format. Boost Graph Library - Python Bindings is used for this. This provides a nice visual feedback to the discrimination network built to a ruleset.
Beta (Join) Nodes
(<x> ^self <y>) /* C1 */ (<x> ^color red) /* C2 */ (<y> ^color red) /* C3 */ ... /* other conditions */
Roadmap & Limitations
The full unlinking algorithm has the following FSM:
FuXi currently implements production capabilities for a limited subset of Notation 3. In particular built-ins are not implemented as they have a significant impact on the efficiency of a RETE network (which was really only intended for pattern matching). Robert's thesis includes algorithms / heuristics for implementing support for:
- Negation
- Non-equality tests (read: built-in support)
- Live addition/removal of rules
- Support for removal of triples / WMEs
Proof Generation
See: Proof generation / visualization
Installation
Fuxi is now setuptools integrated and can be installed via:
wget http://peak.telecommunity.com/dist/ez_setup.py python ez_setup.py easy_install fuxi Fuxi
Command-line Program
Command-line help:
USAGE: Fuxi [options] factFile1 factFile2 ...
Options:
--closure If present, the inferred triples are serialized
along with the original triples if asked for. Otherwise
(the default behavior), only the inferred triples
are serialized
--output=OUT Determines whether to serialize the inferred triples
to STDOUT using the specified RDF syntax ('xml','pretty-xml',
'nt','turtle',or 'n3') or to print a summary of the conflict set
(from the RETE network) if the value of this option is
'conflict'. If the DLP mechanism is invoked (via --dlp) then
a value of 'rif' will cause the generated ruleset to be rendered
in the RIF format. If the proof generation mechanism is
activated then a value of 'pml' will trigger a serialization
of the proof in PML.
--man-owl If present, either the closure (or just the inferred triples) are serialized
using an extension of the manchester OWL syntax
with indications for ontology normalization
(http://www.cs.man.ac.uk/~rector/papers/rector-modularisation-kcap-2003-distrib.pdf)
--normalize Will attempt to determine if the ontology is 'normalized' [Rector, A. 2003]
--help
--input-format=<FORMAT> Determines the format of the RDF document(s) which
serve as the initial facts for the RETE network.
One of 'xml','n3','trix', 'nt', or 'rdfa'. The default
is 'xml'.
--optimize Suggest inefficiencies in the ruleset and exit
--stdin Parse STDIN as an RDF graph to contribute to the
initial facts for the RETE network using the
specified format
--ns=PREFIX=NSURI Register a namespace binding (QName prefix to a
base URI). This can be used more than once
--graphviz-out=<FILE> A filename to write a graphviz diagram of the RETE
network to
--rules=FILE1,FILE2,.. The Notation 3 documents to use as rulesets for the
RETE network
---ruleFacts Determines whether or not to attempt to parse
initial facts from the rule graph. Default by default
--dlp This switch turns on Description Logic Programming
(DLP) inference. In this mode, the input document
is considered an OWL ontology mostly comprised of
Description Horn Logic (DHL) axioms. ontology. An
additional ruleset is included to capture those
semantics outside DHL but which can be expressed in
definite Datalog Logic Programming. The DHL-compiled
ruleset and the extensions are mapped into a RETE-UL
Network for evaluateion.
--proove A N3 string consisting of a single RDF assertion to proove
against the rules and facts provided. Depending on the
--output switch, the proof can be rendered as a Graphviz dot
graph, as a PML proof document, or in a human-readable printout
Sign in to add a comment