The HeKatE Project aims at providing a complete hierarchical design and implementation framework for rules. Principal ideas of the project include an integrated hierarchical design process covering stages from conceptual, through logical to physical design. These stages are supported by specic knowledge representation methods: ARD+, XTT2, and HMR. Practical design and implementation support using these methods is provided by the HeKatE design environment called HaDEs. A complete custom rule runtime environment HeaRT is provided to run XTT2 rule bases. The engine oers a number of rule-base quality analysis plugins.
Rule-based systems [
In this paper a new rule runtime and design framework is presented. The
HeKatE project (see hekate.ia.agh.edu.pl ) aims at providing an integrated
methodology for the design, implementation, and analysis of rule-based
systems [
The main paradigm for rule representation, namely the eXtended Tabular
Trees (XTT) [
A top-down design methodology based on successive renement of the project is introduced. It starts with development of an Attribute Relationship Diagram (ARD) which describes relationships among process variables. Based on the ARD model, a scheme of particular XTT tables and links between them are generated. The tables are lled with expert-provided denitions of constraints over the values of attributes; they are in fact the rule preconditions. The code for rules representation is generated and interpreted with provided inference engine. A set of tools supporting the design and development stages is described.
This paper provides an overview of the project, its objectives and tools in Sec. 2. The rule formulation with XTT is shortly described in Sec. 3. Then in Sec. 4 HeKatE design toolchain called HaDEs is introduced. The HeaRT inference engine described in Sec. 5. Then a short comparison to selected existing solutions is given in Sec. 6. Concluding remarks are given in the nal section. 2
The main principles of the HeKatE project are based on a critical analysis of
the state-of-the art of the rule-based systems design (see [
Internal Knowledge Base Structure . Rules working within a specic context, are grouped together and form the extended decision tables. These tables are linked together forming a structure which encodes the ow of inference. Systematic Hierarchical Design Procedure . A complete, well-founded design process that covers the main phases of the system lifecycle, from the initial conceptual design, through the logical formulation, all the way to the physical implementation, is proposed. Verication of the system model w.r.t. critical formal properties, such as determinism and completeness is provided.
In the HeKatE approach the control logic is expressed using forward-chaining
decision rules. They form an intelligent rule-based controller or simply a business
logic core. The controller logic is decomposed into multiple modules represented
by attributive decision tables. The emphasis of the methodology is its possible
application to a wide range of intelligent controllers. In this context two main
areas have been identied in the project: control systems, in the eld of intelligent
control, and business rules [
HeKatE introduces a formalized language for rule representation [
HeKatE also provides a complete hierarchical design process for the creation of the XTT-based rules.
The main phase of the XTT rule design is called the logical design. This phase is supported by a CASE tool called HQed.
The logical rule design process may be supported by a preceding conceptual
design phase. In this phase the rule prototypes are built with the use of
ARD. The principal idea is to build a graph, modelling functional
dependencies between attributes on which the XTT rules are built. The version
used in HeKatE is called ARD+ as discussed in [
The practical implementation on the XTT rule base is performed in the physical design phase. In this stage the visual XTT model is transformed into an algebraic presentation syntax called HMR. A custom inference engine, HeaRT, runs the XTT model.
Let us now shortly describe the main aspects of the XTT rule formalization. 3
Main Aspects of the XTT Rule Language Formalization
The so-called ALSV(FD) attributive logic [
After [
The atomic formulae can have the following four forms: Ai = d, Ai = t,
Ai ∈ t, and Ai ⊆ t, where d ∈ D is an atomic value from the domain D of the
attribute and t ⊆ D, t = {d1, d2, . . . , dk}, is a (nite) set of such values. The
semantics of Ai = d is straightforward the attribute takes a single value. The
semantics of Ai = t is that the attribute takes all the values of t (see [
An important extension in ALSV(FD) over previous versions of the logic [
From the logical point of view the state is represented by the current values of all attributes specied within the contents of the knowledge-base, as a formula: (A1 = S1) ∧ (A2 = S2) ∧ . . . ∧ (An = Sn) (1) where Ai are the attributes and Si are their current values; note that Si = di (di ∈ Di) for simple attributes and Si = Vi, (Vi ⊆ Di) for generalised ones, where Di is the domain for attribute Ai, i = 1, 2, . . . , n.
Now, consider a set of n attributes A = {A1, A2, . . . , An}. Any XTT rule is assumed to be of the form:
(A1 ∝1 V1) ∧ (A2 ∝2 V2) ∧ . . . (An ∝n Vn) −→ RHS where ∝i is one of the admissible relational symbols in ALSV(FD), and RHS is the right-hand side of the rule covering conclusions. In practise the conclusions are restricted to assigning new attribute values, thus changing the system state. State changes trigger external callbacks that allow for communication with the environment. The values that are no longer valid are removed from the state.
Based on the ALSV(FD) logic the XTT rule language is provided [
Knowledge representation with XTT incorporates extended attributive table format. Similar rules are grouped within separated tables, and the whole system is split into such tables linked by arrows representing the control strategy. Consider a set of m rules incorporating the same attributes A1, A2, . . . , An: the preconditions can be grouped together and form a regular matrix, as in Table 1.
In Table 1 the symbol ∝ij ∈ {=, 6=, ∈, 6∈} for simple attributes and ∝ij ∈ {= , 6=, ⊆, ⊇, ∼, 6∼} for the generalized ones. In practical applications, however, the most frequent relations are =, ∈, and ⊆, i.e. the current values of attributes are restricted to belong to some specic subsets of the domain.
Ecient inference is assured thanks to ring only rules necessary for achieving the goal. It is achieved by selecting the desired output tables and identifying the The HeKatE design process is supported by a number of tools. They help with the visual design and the automated implementation of rule-based systems (see https://ai.ia.agh.edu.pl/wiki/hekate:hades ). The complete framework including the previously discussed methods and tools is depicted in Fig. 1.
Logical Model ARD+
Automated Implementation V1
V2
V3
VIEWS HQEd
XTT2
Analysis
Human readable Machine readable
HMR HML XML serialization jvm/C++ HeaRT HaThoR
CONTROLLER
MODEL SWRL RIF Drools Conceptual
Logical
Physical
Visual Design HJEd/Varda s s e c o r P n g i s e D
Implementation Process
The ARD+ design process is supported by the HJEd visual editor. It is a cross-platform tool implemented in Java. Its main features include the ARD+ diagram creation with on-line design history available through the TPH diagram. An example of a design capturing functional dependencies between system attributes is shown in Fig. 2. Once created, the ARD+ model can be saved in a XML-based HML (HeKatE Markup Language) le. The le can be then imported by the HQEd design tools supporting the logical design.
VARDA is a prototype semivisual editor for the ARD+ diagrams implemented in Prolog, with an on-line model visualization with Graphviz. The tool also supports prototyping of the XTT model, where table headers including a default inference structure are created, see Fig. 3. The ARD+ design is described in Prolog, and the resulting model can be stored in HML.
HealthCare
Medication
HQEd provides support for the logical design with XTT, see Fig. 4. It is able to import a HML le with the ARD+ model and generate the XTT prototype. It is also possible to import the prototype generated by VARDA. HQEd allows to edit the XTT structure with on-line support for syntax checking on the table level. Attribute values entered are checked against domains and some possible anomalies are eliminated.
The editor is integrated with a custom inference engine for XTT 2 called HeaRT. The role of the engine is twofold: run the rule logic designed with the use of the editor, as well as provide on-line formal analysis of the rulebase. The communication uses a custom TCP-based protocol.
HaThoR is the HeKatE rule translation framework. Its goal is to provide rule import and export modules for other languages including RDF and OWL for ARD and RIF and SWRL (possibly R2ML) for XTT. It is mainly implemented in XSLT with some extra plugins integrated with HeaRT implemented in Prolog. An experimental module allows to translate visual XTT representation to a dedicated UML representation using an XMI-based serialization. 5
HeKatE RunTime (HeaRT) is a dedicated inference engine for the XTT 2 rule bases, (see https://ai.ia.agh.edu.pl/wiki/hekate:heart ). It is implemented in Prolog in order to directly interpret the HMR representation which is generated by HQEd. HMR (HeKatE Meta Representation) is a textual representation of the XTT2 logic designed by HQEd. It is a human readable form, as opposed to the machine readable HML format. HeaRT allows to: store and export models in HMR les, and verify HMR syntax and logic. An example excerpt of HMR is: xschm th: [today,hour] ==> [operation]. xrule th/1:
[today eq workday, hour gt 17] ==> [operation set not_bizhours]. xrule th/4: [today eq workday, hour in [9 to 17]] ==> [operation set bizhours].
The rst line denes an XTT table scheme, or header, dening all of the attributes used in the table. Its semantics is as follows: the XTT table th has two conditional attributes: today and hour and one decision attribute: operation . Then two examples of rules are given. The second rule can be read as: Rule with ID 4 in the XTT table called th : if value of the attribute today equals (=) value workday and the value of the attribute hour belongs to the range ( ∈) < 9, 17 > then set the value of the attribute operation to the value bizhours .
The engine implements the inference based on ALSV(FD). It supports four
types of inference process, Data and Goal Driven, Fixed Order, and Token
Driven [
HeaRT also provides a modularized verication framework, also known as HalVA (HeKatE Verication and Analysis). Verication and analysis module implements: simple debugging mechanism that allows tracking system’s work, logical verication of models (several plugins are available, including completeness, determinism and redundancy checks), and syntactic analysis of HMR les using a DCG grammar of HMR. The verication plugins can be run from the interpreter or indirectly from HQEd using the communication protocol.
The engine has communication and integration facilities. HeaRT supports Java integration based on callbacks mechanism and Prolog JPL library. It allows for a direct interaction via Prolog console based on callbacks mechanism. HeaRT can operate in two modes, stand-alone and as TCP/IP server, oering TCP/IP integration mechanism with other applications. It is possible to create console or graphical user interface build on Model-View-Controler design pattern.
There are two types of callbacks related to attributes in HMR les. 1) input used to get attribute value from user. This can be done by console or graphical user interface. 2) output used to present an attribute value to user. Callbacks can be use to create GUI with JPL and SWING in Java.
To make HeaRT integration easier, there are three integration libraries, JHeroic, PHeroic or YHeroic. JHeroic library was written in Java. Based on JHeroic one can build applets, desktop application or even JSP services. It is also possible to integrate HeaRT with database using ODBC, or Hibernate. YHeroic is a library created in Python. It has the same functionality as JHeroic but is easier to use because of Python language nature. PHeroic is the same library but created in PHP5. It can be used in a dynamic web page based on PHP. 6
Here, the focus is on two important solutions: CLIPS and its Java-based incarnation Jess, as well as Drools, which inherits some of the important CLIPS features, while providing a number of high-level integration features. Other environments include LPA VisiRule.
XTT provides an expressive, formally dened language to describe rules. The language allows for formally described inference, property analysis, and code generation. Additional callbacks in rule decision provide means to invoke external functions or methods in any language. This feature is superior to those found in both CLIPS/Jess and Drools. On the other hand, the main limitation of the HeKatE approach is the state-base description of the system, where the state is understood as the set of attribute values.
The implicit rule base structure is another feature of XTT. Rules are grouped into decision tables during the design, and the inference control is designed during the conceptual design, and later on rened during the logical design. Therefore, the XTT representation is highly optimized towards rulebase structurization. This feature makes the visual design much more transparent and scalable.
In fact all the Rete-based solutions seek some kind of structurization. In the
case of CLIPS it is possible to modularize the rulebase (see chapter 9 in [
A complete design process seems to be in practice the most important issue. Both CLIPS and Jess are classic expert system shells, providing rule languages, and runtimes. They are not directly connected to any design methodology. The rule language does not have any visual representation, so no complete visual editors are available. Implementation for these systems can be supported by a number of external environments (e.g. Eclipse). However, it is worth emphasizing, that these tools do not visualize the knowledge contained in the rule base.
Drools 5 is decomposed into four main parts: Guvnor, Expert, Flow, Fusion. It oers several support tools, including an Eclipse-based environment. A design support feature, is the ability to read Excel les with simple decision tables. While this is a valuable feature, it does not provide constant syntax checking.
It is crucial to emphasize, that there is a fundamental dierence between a
graphical user interface like the one provided by generic Eclipse-based solutions,
and visual design support and specication provided by languages such as XTT
for rules, and in software engineering by UML. Other dedicated visual rule design
languages include URML [
The primary area of interest of this paper is to introduce the main concepts of the HeKatE project, its methods and tools. The main motivation behind the project is to speed up and simplify the rule-based systems design process, while assuring the formal quality of the model. The HeKatE design process is practically supported by a number of tools presented in the paper. These include the HeKatE design environment called HaDEs and the rule runtime called HeaRT. The up-to-date results of the project, as well all the relevant papers are available at the project website see http://hekate.ia.agh.edu.pl .
HeKatE project ends in November 2009. Therefore, future work includes a tighter tool integration, as well as modeling complex cases in order to identify possible limitations of the methodology. Providing a comparative studies modelling the same cases in XTT, CLIPS and Drools is planned.