This paper presents advances in Set Attributive Logic and its application to develop tabular rule-based systems within the XTT framework. The primary goal is to extend the expressive power of simple attributive languages so that it becomes satisfactory for complex applications, including the business rules support. A formal framework of extended Attributive Logic with Set Values over Finite Domains (ALSV(FD)) is presented and specific inference rules are provided with their corresponding prototype in PROLOG.
Rule-based systems (RBS) are one of the most efficient paradigms
for knowledge representation and automated inference. This is an
intuitive and well-established language [
This paper presents advances in Set Attributive Logic and its application to develop tabular rule-based systems within the XTT framework. The primary goal is to extend the expressive power of simple attributive languages so that it becomes satisfactory for complex monitoring, control, decision support and business rules applications. A formal framework of extended Set Attributive Logic is presented and specific inference rules are provided. The practical representation and inference issues both at the logical and implementation level are tackled.
In the HEKATE project (hekate.ia.agh.edu.pl) an extended
rule language is proposed. It is based on the XTT language described
in [
The XTT+ rule language is based on the classic concepts of rule
languages for rule-based systems [
In this paper the XTT+ language will be simply referred to as XTT.
In XTT there is a strong assumption, that the rule base is explicitly structured. The rules with same sets of attributes are grouped within decision tables. On the rule level explicit inference control is allowed. In this way, a set of tables is interconnected using links, corresponding to inference control. This makes up a decision-tree like structure, with tables in the tree nodes. In a general case, the XTT is a directed graph, with cycles optionally allowed.
In RBS, a rule has a general format: IF condition THEN decision This format can be used in both forward and backward chaining systems. However, here we focus on the production rule systems, based on the forward chaining paradigm. The power of a rule language stems from the syntax and semantics of the conditional and decision expressions. Number of systems implicitly assume, that this rule format can be extended to the conjunctive normal form (CNF), that is: IF cond1 AND cond2 AND ... AND condN THEN decision
which in fact corresponds to a Horn clause ϕ [
The decision expression can also be a compound one in the CNF.
Now the question is what are the conditional and decision
expressions. In number of systems these correspond to expressions in the
propositional calculus, which makes the semantics somehow limited.
Some systems try to use some subsets of predicate logic, which gives
much more flexibility, but may complicate a RBS design and the
inference process. This is the case of the PROLOG language [
Let us now move to attributive logic that provides a formal foundation for the rule language. 3
Consider a simple piece of knowledge expressed with natural language as follows.
The regular class hours are from 8:00 to 18:00. If all the teaching hours are located within regular class hours then the salary is regular. If the teaching hours goes beyond the regular class hours then the salary is special.
The problem is to formalize these two rules with attributive logic. Let RCH stays for regular class hours, and TH for teaching hours. We can define a fact like:
RCH = {8, 9, 10, 11, 12, 13, 14, 15, 16, 17},
TH = {10, 11, 12, 16, 19, 20} to specify a case of teaching hours. Note that teaching hours may form any subset of {0, 1, 2, 3, . . . , 23} (not necessarily a convex interval).
Now, to express the rules we need an extended attributive logic employing set values of attributes and some powerful relational symbols. For example, we can have:
R1 : TH ⊆ RCH −→ Salary =0 regular 0
R2 : TH ∼ NRCH −→ Salary =0 special 0
NRCH = {0, 1, 2, 3, 4, 5, 6, 7, 18, 19, 20, 21, 22, 23} is a specifications of non-regular class hours, and sim means a nonempty intersection. Note that an attempt to specify the rules with attribute logic based on atomic values (even if relational symbols such as <, ≤, > and ≥ are allowed) would lead to a very long and at least clumsy set of hardly readable rules. 4
Attributive logics constitute a simple but widely-used tool for
knowledge specification and inference. In fact in a large variety of
applications in various areas of Artificial Intelligence (AI) [
However, it is symptomatic that although Propositional Logic and
Predicate Logic (in the form of First-Order Predicate Calculus) have
well-elaborated syntax and semantics, presented in details in
numerous books covering logic for knowledge engineering [
In a recent book [
The very basic idea is that attributes can take atomic or set values.
After [
The SAL as introduced in [
In this paper an improved and extended version of SAL is presented in brief. For simplicity no object notation is introduced. The formalism is oriented toward Finite Domains (FD) and its expressive power is increased through introduction of new relational symbols. The practical representation and inference issues both at the logical level and implementation level are tackled. The main extension consists of a proposal of extended set of relational symbols enabling definitions of atomic formulae. The values of attributes can take singular and set values over Finite Domains (FD). 4.1
An extension of SAL was proposed in [
The basic element of the language of Attribute Logic with Set Values over Finite Domains (ALSV(FD) for short) are attribute names and attribute values. Let us consider: A – a finite set of attribute names, D – a set of possible attribute values (the domains).
Let A = {A1, A2, . . . , An} be all the attributes such that their values define the state of the system under consideration. It is assumed that the overall domain D is divided into n sets (disjoint or not), D = D1 ∪ D2 ∪ . . . ∪ Dn, where Di is the domain related to attribute Ai, i = 1, 2, . . . , n. Any domain Di is assumed to be a finite (discrete) set.
As we consider dynamic systems, the values of attributes can change over time (or state of the system). We consider both simple attributes of the form Ai: T → Di (i.e. taking a single value at any instant of time) and generalized ones of the form Ai: T → 2Di (i.e. taking a set of values at a time); here T denotes the time domain of discourse.
Let Ai be an attribute of A and Di the sub-domain related to it. Let Vi denote an arbitrary subset of Di and let d ∈ Di be a single element of the domain. The atomic formulae of ALSV(FD) are defined as follows.
Definition 1 The legal atomic formulae of ALSV for simple attributes are: Definition 2 The legal atomic formulae of ALSV for generalized attributes are:
Ai = d, Ai 6= d, Ai ∈ Vi, Ai 6∈ Vi.
Ai = Vi, Ai 6= Vi, (1) (2) (3) (4) (5) In case Vi is an empty set (the attribute takes in fact no value) we shall write Ai = {}. In case the value of Ai is unspecified we shall write Ai = NULL (a database convention). If we do not care about the current value of the attribute we shall write A = _ (a PROLOG convention).
The semantics of the atomic formulae as above is straightforward and intuitive. In case of the first three possibilities given by (1), (2), (3) and (4) we consider Ai to be a simple attribute taking exactly one value. In case of (1) the value is precisely defined, while in case of (3) any of the values d ∈ Vi satisfies the formula. In other words, Ai ∈ Vi is equivalent to (Ai = d1) ⊗ (Ai = d2) ⊗ . . . ⊗ (Ai = dk), where Vi = {d1, d2, . . . , dk} and ⊗ stays for exclusive-or. Here (2) is a shorthand for Ai ∈ Di \ {d}. Similarly, (4) is a shorthand for Ai ∈ Di \ Vi.
The semantics of (5), (2) (7),(8), (9), and (10) is that Ai is a generalized attribute taking a set of values equal to Vi (and nothing more), different from Vi (at at least one element), being a subset of Vi, being a superset of Vi, having a non-empty intersection with Vi or disjoint to Vi, respectively.
More complex formulae can be constructed with conjunction (∧) and disjunction (∨); both the symbols have classical meaning and interpretation.
There is no explicit use of negation. The proposed set of relations is selected for convenience and as such is not completely independent. For example, Ai = Vi can perhaps be defined as Ai ⊆ Vi ∧ Ai ⊇ Vi; but it is much more concise and convenient to use “=” directly. Various notational conventions extending the basic notation can be used. For example, in case of domains being ordered sets symbols such as >, >=, <, =< can be used. 4.2
Since the presented language is an extension of the SAL (Set
Attributive Logic) presented in [
ALSV(FD) has been introduced with practical applications for rule
languages in mind. In fact, the primary aim of the presented language
is to extend the notational possibilities and expressive power of the
XTT-based tabular rule-based systems [
Consider a set of n attributes A = {A1, A2, . . . , An}. Any 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 conclusion and
perhaps the retract and assert definitions if necessary; for details see
[
Knowledge representation with eXtended Tabular Trees (XTT) incorporates extended attributive table format. Further, 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. In such a case the preconditions can be grouped together and form a regular matrix. Together with the conclusion part this can be expressed as in Tab. 3
In Table 3 the symbol ∝ij ∈ {=, 6=, ∈, 6∈} for simple attributes and ∝ij ∈ {=, 6=, ⊆, ⊇, ∼, 6∼} for the generalized ones. In practical i.e. if the values of an attribute takes values located within a certain set they must also belong to any superset of it (upward consistency). These rules seem a bit trivial, but they must be implemented for enabling inference, e.g they are used in the rule precondition checking.
The summary of the inference rules for atomic formulae with simple attributes (where an atomic formula is the logical consequence of another atomic formula) is presented in Table. 1. In Table 1 and applications, however, the most frequent relation are =, ∈, and ⊆, i.e. the current values of attributes are restricted to belong to some specific subsets of the domain. If this is the case, the relation symbol can be omitted (i.e. it constitutes the default relation which can be identified by type of the attribute and the value).
The current values of all the attributes are specified with the contents of the knowledge-base (including current sensor readings, measurements, inputs examination, etc.). From logical point of view it is a formula of the form: (A1 = S1) ∧ (A2 = S2) ∧ . . . ∧ (An = Sn), (13) where Si = di (di ∈ Di) for simple attributes and Si = Vi, (Vi ⊆ Di) for complex.
Having a table with defined rules the execution mechanism searches for ones with satisfied preconditions. The satisfaction of preconditions is verified in an algebraic mode, using the dependencies specified in the first row of Table 1 for simple attributes and the first row of Table 2 for the complex ones.
The rules having all the preconditions satisfied can be fired. In
general, rules can be fired in parallel (at least in theory) or
sequentially. For the following analysis we assume the classical, sequential
model, i.e. the rules are examined in turn in the top-down order and
fired if the preconditions are satisfied. Various mechanisms can be
used to provide a finer inference control mechanism [
It is assumed that for each XTT attribute a type has to be stated. A type is named and it specifies: the base type and the domain. In the design of the XTT+ attributive language the set of base types was introduced in a way that simplifies the low-level interpreter integration with Prolog, Java, and RDBMS.
An example definition could be as follows: • suppose we have a natural language specification: “some temperature”, • create attribute type, – pick a attribute type name, e.g. “Temperature” – decide what base type to use, in this case it could be a float, – define the domain by specifying constraints, e.g. -100, 100 depending on the conditions, – decide whether the domain is ordered – in case of symbolic base type, in this case numbers are ordered, • create new attribute, with given, – attribute type, in this case of “Temperature”, – name, e.g. sensor_temperature, – decide whether the attribute can take only single values, or also multiple values.
Generalized attributes are unordered or ordered sets (lists). This means attributes are in fact multi-valued . Some applications for this features are e.g.: a set of languages a person speaks, or storing subsequent values (changing in time). 4.5
The XTT+ rule firing process is coherent with the regular RBS semantics. It involves: condition checking and decision execution.
The condition checking can be described as a pattern matching process, where the condition evaluates true or false. The condition is an expression in the CNF build of expressions in the ALSV(FD).
The decision execution is where actions are possible. In a general case, the XTT+ rule decision involves: attribute value change context switching through inference control links event triggering. In XTT it is assumed, that the whole system state is described by the means of attributes. 5
In the prototype implementation of the knowledge base, rules and the interpreter are developed in PROLOG. A meta-programming approach is followed. This allows for encoding virtually any structured information. Note that in such a case the built-in P ROLOG inference facilities cannot be used directly, there is a need for a meta-interpreter (however, this gives more flexibility in terms of rule processing).
Example domains and attributes specification in PROLOG follows:
domain(d7,[
The atomic formulae (facts) are represented as terms of the type fact/4 with four arguments; here are some examples: %%% fact(<attribute-type>,<attribute-name>, % <relation>,<attribute-domain>) fact(atomic,aDN,eq,7). fact(atomic,aDD,in,[monday,wednesday,friday]). fact(set,sDD,sim,[monday,wednesday,friday]). fact(set,sSE,subseteq,[spring,summer,autumn]).
Facts are used mostly in rule preconditions. The meaning of the above facts is as follows: f1: sDN=7, f2: aDD∈[monday,wednesday,friday], f3: sDD∼[monday, wednesday,friday], and f4: sSE⊆[spring,summer,autumn]. PROLOG list are used to represent set values.
The state of the system is represented by all the facts true in that state. Recall that the form A = d and A = V are allowed for state specification.
Note that using set values in state specification increases
drastically the expressive power. This is a bit similar to the Cartesian
Product: in state s17 the attribute sDN takes all the values from
[
Inference, i.e. checking logical consequence defined by first rows of Table 1 and Table 2 is performed with the valid/s predicate defined as follows: valid(f(atomic,A,eq,Value),State):state(State,A,atomic,StateValue),
Value == StateValue,!. valid(f(atomic,A,neq,Value),State):state(State,A,atomic,StateValue),
Value =\= StateValue,!. valid(f(atomic,A,in,SetValue),State):state(State,A,atomic,StateValue), member(StateValue,SetValue),!. valid(f(atomic,A,notin,SetValue),State):state(State,A,atomic,StateValue), \+member(StateValue,SetValue),!. valid(f(set,A,eq,SetValue),State):state(State,A,set,StateValue), eqset(SetValue,StateValue),!. valid(f(set,A,neq,SetValue),State):state(State,A,set,StateValue), neqset(SetValue,StateValue),!. valid(f(set,A,subseteq,SetValue),State):state(State,A,set,StateValue), subset(SetValue,StateValue),!. valid(f(set,A,supseteq,SetValue),State):state(State,A,set,StateValue), subset(StateValue,SetValue),!. valid(f(set,A,sim,SetValue),State):state(State,A,set,StateValue), intersect(SetValue,StateValue,[_|_]),!. valid(f(set,A,notsim,SetValue),State):state(State,A,set,StateValue), intersect(SetValue,StateValue,[]),!.
The excerpt of the implementation code presented above includes only symbolic domains. The definitions for the remaining domains are similar to the ones presented here. Currently the use of CLP (Constraint Logic Programming) PROLOG extensions are being investigated. 6
Providing an expressive yet formally described rule language is of a
high importance for practical rule design and implementation. This
paper presents extensions of Set Attributive Logic as presented in
[
In the paper new inference rules specific for the introduced logic are presented and examined. New inference possibilities constitute a challenge for efficient precondition matching algorithm. Algebraic solutions are proposed. Knowledge representation and some excerpt from inference engine implemented in PROLOG is described. Components of a rule-based system in form of extended attributive decision tables (the so-called XTT paradigm) are presented and their characteristics and applications are outlined.
Future work includes a more robust implementation of the type system, tighter integration with a Java-based runtime, as well as an interface do RDBMS.
The paper is supported by the Hekate Project funded from 2007– 2009 resources for science as a research project.