The XTT Knowledge Representation
Introduction
XTT is a knowledge representation formalism for rules.
XTT allows for structurization of the rules base, by introducing:
tables, used, to group rules.
intertable links, used to provide inference control between tables.
Rules use an expressive attribute language.
So going deeper, general issues are as follows:

the
Rule syntax, and semantics, what it means to fire a
single XTT rule,
the table structure, how we encode a table using XTT rules
the inference control, how do we interpret a table, and a set of tables
Now, considering a system, containing knowledge expressed in XTT, some other issues are:
environment interaction: how do we exchange information with the env?
interpreter model: when, how, do we run/query the XTT rulebase
Some issues include:
Attributive language
Introduction
We need attributes to build descriptions of state of the system.
The language we use is based on attributes.
So the expressiveness of the attributive language limits the expressiveness of the rule language.
The aspects of the attributive language are:
attribute definition, the basic notions
attribute algebra, what can we do with attributes, expressions, and how we do it
Attribute description
Type
For each attribute a type has to be stated.
A type is named and it specifies:
primitive type
domain
a group (optional)
Primitive Types
What do we need types for anyway?
Not all languages use types, e.g. Lisp, Prolog after all.
We want attribute types because:
they allow to be more specific about certain properties,
certain types allow for certain intuitive operations, e. g. aritithmetic,
we want to be able to calculate, so we need a way to distinguish between numeric and not numeric attributes,
types allow for more specific constraints – domains,
it is hoped, that certain level of formal verification may be easier.
we want to be able to map to lowlevel languages, e.g. Java, SQL, C, to perform execution, certain operations on attribute values.
Name  Prolog  Java  C  RDB 
Bool  basic use  java.lang.Boolean  int  bool 
Integer  integer  java.lang.Number.Integer  int  integer 
Numeric (fixedpoint)  float  java.lang.Number.Float  float  float 
Symbol  atom  java.lang.String  char*  var char 
Symbol might also be called String.
Integer is a subset of Numeric. An integer value is a numeric value with scale set to zero.
With numeric type there exist a predefined upper and lower limit enforced by the implementation, simply referenced as MAX
, and MIN
.
Primitive types:
in Prolog there are no types (on the lowlevel)

byte short int long,
float double,
char String,
boolean,
so these Java types correspond to XTT primitive types
please note: at this level the Java system is NOT exandable at all!!!
so primitive types map to the above Java primitive types, but we have
integer (a special case of numeric) for (byte short int long),
numeric (general) for (float double),
symbolic for (char String),
bool for (boolean),
Complex types:
Now, the next step in Java/C are vectors are single dim arrays, which simply map to lists in Prolog.
When these are not enough, there are structures that allows for any type of composition.
In our attributive language we have different (narrower?) semantics:
an attribute (a “variable reference” ?) can have a single value
multiple values, which allows to provide functionality of vectors but with different semantics (multivalue is not a simple composition as in vector)
In the XTT+ there was a proposal of grouped attributes.
This is a coherent extension to attributes.
While it might look similar to structures, it still does have a different semantics.
Type mappings
Current type specs has Prolog, SQL and Java mapping in mind (we map to Java object, not basic types, so Integer, not int).


Java/Prolog types mapping in
JPL
There is no
binary
type (blob)
really?
Domains
A domain is a discrete, finite set of allowed attribute values.
So in a general case we have the following cases:
a set of numbers (always ordered),
a set of symbols, e.g. red, green, blue,
an ordered set of symbols, e.g. low, mid, high.
Bool is a trivial case (unordered).
Allowed values are expressed as a sum of ranges/values:
<1,5> U <7,9> U {12}
High U Medium U Low
Such a sum may be ordered or unordered.
With numbers, we do not allow real (infinite) domains.
We always assume a finite domain.
Floating point number are allowed but it has to be explicitly stated how many digits are allowed before and after the decimal point.
Additionally a set of values, narrowing the above, can be introduced.
Ordered symbolic domains
In the original XTT there was a feature called enum.
This was in fact an ordered symbolic domain.
In this way, one might have a named att. dayofweek
of type symbolic, and be able to:
In this case it is still a symbolic domain, so we store “mon” not 2!!!
This corresponds to the socalled linguistic variables in other formalisms.
Contexts
In the original XTT attributes could be used in four contexts:
conditional, assert, retract, decision.
This is a legacy concept.
We assume, that assert/retract, or the KB manipulation, is an operation not a context of an attribute, see HOPs.
For the XTT^2 we should simply consider:
conditional context
decision context
Values
Attributes can have atomic or nonatomic values (multiple) – this has to be specified explicitly.
Number of values, for nonatomic attributes, is not bounded.
So an attribute value, for nonatomic values, is an ordered set.
This set can be treated in different ways depending on semantics as a regular set or an ordered one.
There should be operators defined which treat the set accordingly: as a set, as an ordered set, or other type.
Upon setting attribute value the same notation as for the domains should be used (a sum of ranges or values), i.e. S=<5,8>u{3}
Description
In a general sense, an attribute
Grouped attributes
The original desc
(as from the progrulesext papers))
\emph{Grouped Attributes} provide means for putting together some number of attributes to express relationships among them and their values.
As a result a complex data structure, called a \emph{group}, is created which is similar to constructs present in programming languages (i.e. C language structures).
A group is expressed as:
\[
Group(Attrinbute1,Attribute2,\ldots,AttributeN)
\]
Attributes within a group can be referenced by their name:
\[
Group.Attribute1
\]
or position within the group:
\[
Group/1
\]
An application of Grouped Attributes could be expressing spatial coordinates:
\[
Position(X,Y)
\]
where $Position$ is the group name, $X$ and $Y$ are attribute names.
Discussion
Now, considering the primitive types discussion, as well as type system extension possiblity I would refine the GA proposal, as it might/should? be the key to type expressiveness.
I would propose certain simplification to the above definition:
Grouped attribute is a mean to put certain named attributes in a common single context.
GA provides a certain namespace
attributes within a group can be referenced by their name only
GAs are a way of expanding the type system, not structuring the data
In this case to support date, we would:
define a named attribute year as integer
with domain <0,upper>
define a named attribute
month as
integer
with domain <112> (see ordered symbolic domains
)
define a named attribute day as symbolic
with domain {monsun}
define a GA date with named atts year, month, day in its scope.
Such a GA can is named date, and could possibly be used “like a type”.
A group can function as an attribute, or attribute type.
Defining Attributes
…or the short attribute quickstart with examples.
suppose we have a natural language
spec, we have “some temperature”
create attribute type
pick a attribute type name, e.g. “Temperature”
decide what primitive type to use
define the domain by specifying constraints
decide whether the domain is ordered  in case of symbolic base type, 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 atomic values, or also multiple or nonatomic values
Another example with grouped attributes.
Let's suppose we want to represent a “date of birth” and “current date”.
So, we need a “date”, then think what is a date.
we define “day” as a numeric integer attribute with constraints <1,30>
we define “month” as a symbolic attribute with values jandec
and an ordered domain 112
we define “year” as a numeric integer attribute with constraints e.g. 1970MAX
we define a guped attribute type “date” having day, month, and year.
we define two physical attributes “date of birth” and “current date” having the type of “date”
The CASE tools should support a concept of an attribute library, where some predefined types are available.
Attributes and ARD
We should try to establish relationship/s (if any?) between:
groupped attributes
attribute types
scope as in ARD
gen
spec/composition and finalization/split
Attribute Markup
Rule syntax
imported from xtt+ refined
It should be kept in mind, that we must not mix he issues such as:
This discussion should be about single rules.
Intro
In the HeKatE project an extended rule language is proposed.
It is based on the XTT language described in the original XTT papers.
The version used in the project is currently called XTT+.
The XTT+ rule language is based on the classic concepts of rule languages for rulebased systems (liebowitz), with certain important extensions and features, such as:
explicit rulebase structurization,
strong formal foundation based on attributive logic,
extended rule semantics.
Here, 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.
This way, a set of tables is interconnected using links, corresponding to inference control.
This makes up a decisiontree like structure, with tables in the tree nodes.
In the general case, the XTT is a graph, with optionally cycles 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 (benari:2001,alibookspringer), that is:
!cond1 v !cond2 v ... v !condN v decision
or transformed to:
cond1 ^ cond2 ^ ... ^ condN > decision
The decision expression could 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 (bratko).
In XTT these expressions are in the the attributive logic (alibookspringer) described in more detail elsewhere.
This gives much more power than the propositional logic, but does not introduce problems of the predicate logicbased inference.
In XTT an extended rule semantics is used.
These extensions were introduced in (gjn2007enase), and refined in (gjn2007inap).
They are:
Grouped Attributes, and
AttributeAttribute Comparison
Other (gjn2007enase) extensions such as
Link Labeling,
NotDefined Operator, and
the Scope Operator.
work on the intertable inference level, so they are not included here.
Rule Semantics and Firing
In XTT it is assumed, that the whole system state is described by the means of attributes.
The XTT+ rule firing process is coherent with the regular RBS sematics.
It involves:
condition checking and
decision execution.
The condition checking can be decribed as a pattern matching process,
where the whole condition evaluates true or false.
The condition is an expression in the CNF build of expressions in the ALSV(FD).
The condition is an expression in the ALSV(FD) language. Period.
The decision execution is where actions are possible.
In a general case, the XTT+ rule decision involves:
For now, it is simply assumed, that
the decision is expressed in a different way, comparing with the condition.
Rule Condition in ALSV(FD)
ALSV(FD)
A discussion of the current extension of the attribute logic to Attribute Logic with Set Values over Finite Domains is contained in two papers for:
ECAI2008, (p_salrules/salrules.tex) where the larger logical context is presented, and
KI2008, (p_salrules/salruleski.tex) where an excerpt of a simple interpreter is given.
in the final version some discussion from the papers could be imported.
Condition
Bottom line:
ALSV(FD) provide means to express conditions.
Currently it is not being used for decions.
the rule format with ALSV(FD) is as follows
cond1 ^ cond2 ^ … ^ condN  decision
In the above condI
are {A,O,V}
, where
A is attribute name
O is a relational operator, working on a single attribute references, and single set of vals, O evaluates true or false!
V is a value, or a set of vals
The valid ALSV(FD) expressions are (as of salrulesruleapps):
While the set of operators is not really closed,
the general structure of the expression holds, thus limiting other possiblities.
The structure of the ALSV(FD) expression is always:
{current attribute values set} 2arg_relational_operator {conditional values set}.
so in fact we always have:
two sets of values, and
2 arg. relational operator R, that evalutes true or false depending on the sets.
the attribute values set is referenced by the attribute name, e.g. A
the conditional values set is referenced by a V.
in XTT such a 3 element expression corresponds to a XTT cell, with attribute reference written in a corresponding column in the XTT table scheme, and operator R as well as the value set V written in the cell content.
(See AVR for some possible exception.)
Features of this approach are:
formal description,
formally defined inference for all valid expressions,
multivalued attributes fully supported,
Now the full formal description of logical cond
evaulation is in the papers.
This is called ALSV(FD) inference.
It is single step, non recursive matching for every expression, that is every cond
.
So condition checking is a simple pattern matching, where the conjunction:
cond1 ^ cond2 ^ ... ^ condN
is evaluated. If it evaluates true, the rule fires.
Rule Condition
We assume the format discussed in ALSV(FD), that is:
cond1 ^ cond2 ^ ... ^ condN
See that section for inference, satisfaction, etc.
Attribute values notation
MV Notation
Value representation notation.
It is assumed, that SV (abbrev. single valued) (previously atomic attributes) and values are written as:
A, V for single valued and
{A}, {V} for multiple valued.
This was prposed by ALi and is a sane method to tell them apart from the very first sight.
This should be supported by the design tools!
Intensional MV Encoding
From the logical point of view:
From practical point of view:
these sets can be large
we want to be able to use intensional representation, such as: “integers from 10 to 1000”
we want to have a noncontinous specification, such as “0 and integers from 10 to 1000 and 2005 to 3000”
Now, all this applies to numerics only!!!
Attribute vals having symbolic domain are always explicitely enumerated!
The proposal is to have an Intensional NonAtomic Specs as follows:
NonAtomVal := NonatomVal sum NonAtomVal
NonAtomVal := val  RegionSpec
RegionSpec := <val, val>
Where val
is of base/primitve type.
So this shoould map to an ordered set, a list.
It is used in
MV semantics
MultiValue semantics:
NDS, no duplicates set (as setof)
WDS, a set with duplicates
NDL, no duplicates list (ordered set) (as setof)
WDL, a list with duplicates
WDL seems to be a generic data structure, a Prolog list.
Before defining operators we should check, what are builtins to process lists as sets., e.g.:
Attribute Value Reference
The AVR is a situation such as:
A1<A2
in condition
A1 is A2
in decision
select({A1},lt(3),assert({A2}))
meaning select values less then 3 from A1, assert to values of A2, in decission.
AVR is both powerful but evil!
It is very expressfull, but makes analysis, or sometimes the design, painful, or even not possible.
So we do want to have some cases where we do not use AVR.
There is no calculations or operations allowed on AVR, it just represents an attribute value.
AVR is related to the socalled AttributeAttribute Comparison of XTT+.
Rule decision
This is antoher aspect of the rule lang expressiveness.
It is assumed, that the decision is expressed in a different way, comparing with the the condition!
Some aspects are described below.
In the original XTT the general format was the same as the condition, that is:
dec1 ^ dec2 ^ ... ^ dec2
Actually we might ask what ^
means in this case.
Since there is no logical evaluation in the decision, it is simply a conjuction.
We could/should that these are interpreted sequentially. (this would help escape oprator expressions)
The decision spec also includes the inference control spec tablenr+rulenr!
The next step is to define what dec
is.
Decision expressions
In the original XTT there are some general actions in the socalled decision context.
The vague interpretation is “in a given cell do something on/using/with att H that appears in the table scheme”.
Examples of table decisions can be shown :
 H 
+++
0  vmo operation(Arguments) 
1  = 3 
2  = mean(H) 
3  + {3} 
4   {4,5} 
5  = G + H * 2 
6  = run_robot(G) 
7   x run_robot(G)
In a general sense, an XTT cell in the decision context is:
H vmo operation(Arguments).
vmo
is the value modification operator, or modop
for short.
What operations are available in a XTT cell depends on the attribute primitive type!
Only some of these discussed below are generic.
In the decision, references to ANY attributes present in the same table can appear.
Such references are not in the column of the table scheme.
The scheme presents a single attribute which value is/or can be modified.
Value Modification
The following modop
s are proposed.
Assignement
Denoted as =
The simplest case
SVM –> A is V is(A,V)
MVM –> {A} is {V}, from logical pov: A = {V}, that is A is a singleton, is({A},{V})
Assert/Retract
Assert
Denoted as +
Retract
Denoted as 
Now, depending on the multivalue semantics, we could consider
I believe this (MVS) requires some sensible restriction.
Void
Denoted as x
Disregard the value returned by an operation,
thus not modifying the attribute value.
This VMO could/should/is? allowed only with actions –> some actions might not modify the att value, but they can be somehow related to the attribute (see tho OOlike proposal).
this is under cnsideration
Values
modop
arguments are values.
These values are either given or evaluated during the inference process.
The evaluation regards values referenced by attributes or values calculated as results of application of Evaluaion Operators, evalop
s for short.
i.e. arithmetic expressions can be calculated this way.
evalop
s could be nested, i.e.
add(2,div(3,sin(d)))
evaluates as: 2+(3/(sin(d)))
evalop
s should be considered in SVM and MVM (abbrev. single and multi value) modes.
The following evalops
are proposed:
Selection
There could a whole range of these, including regexps for strings.
Can also be considered a restriction operation.
They do depend on the attribute type, since the selection criteria is typedependent.
now what happens with the selection? maybe we should consider:
MVM –> {A} select (C) …, e.g. select({A},lt(3),{A2})
, such as A1={1,2,3,4} → select({A},lt(3),{A2}) → A2={1,2}
MVM –> {A} restrict (C) …, e.g. restrict({A},lt(3))
, such as A1={1,2,3,4} → restrict({A},lt(3)) → A1={1,2}
MVM –> {A} select (C) …, or simply e.g. select({A},lt(3),{A1})
, such as A1={1,2,3,4} → select({A},lt(3),{A1}) → A1={1,2}, or even _
instead of self reference?
Maybe the criteria in the selects, can be expressed by exactly the same relational operators as in the conditinal part?
These allow to get some information about a set of attribute values.
This information could be assigned, used, etc.
All of these apply only to the MVM?
Maybe we do not this a separate class? this is just a part of calculation class?
count({A},_X), how many values are there in the {A}? (length)
count({A},_X,value(3)), how many 3s are there in the {A}?
count({A},_X,_), how many values are there in the {A}???
Calculation
This probably applies only to Numerics
So we support any artithemtic expression, including a set of predefined mathonly functions.
(So in fact, we could use any predefined arithemtic function.
This does not mean ANY “function” (as in prog lang), only math functions operating on numeric values, and returning numeric values.)
Now, we could consider implementing a sensible set of functions, based
math.h
or rather java.lang.Math
In simple words there is a need for a set of operators providing arithmetic operations:
i.e. add(X,Y) which adds X and Y and returns the result.
X and Y in this case can be evalop
s as well.
Actions
In the classic production rules and RBS there is often operational semantics, e.g. if some condition is met DO sth.
Specs and Syntax:
an action can:
trigger sth outside the system in env, and not change the att value
as above, but do change the value
action(A1...An)
action(A1...An)
Where action is simply a C function, Java method, Prolog pred…
In the 1st case Att valus is modified, the function returns the value.
Can we restrict it any further?
In the OOlike proposal, the action has to bound with the att whose value it changes.
OOlike proposal
This is an experiemntal stuff that needs integration with the groupped attributes concept.
An idea: think of an attribute as an object (yes, really!).
It is a container for data of the form of a value/list/set.
It also has methods, that can be triggered from the system (only from the decision!) or from the environment, or possibly both.
This is an extension of the discussion we had in the attributive_language.
To define data, we also define ways to handle it (data+processing, datastructs+algorithms, kr+predicates → it might one of the essential problems of AI/CS ).
This solution would enforce binding the actions to attributes they work on.
Example:
we have a robot,
a grouped att position
, with pos.x
, pos.y
is related to the actions such as go
,
because such an action changes the position, even thought it might be executed as go(forward, 5cm)
One can imagine actions that are triggered from the env.
e.g. when the robot changes the position, it triggers a method pos.update
Rule types
One should keep in mind, that in some cases we have some simplified rule schemes, or types.
We should at least consider a rule with no precondition, one that fires always.
Considering ARD restrictions, we cannot just omit the condition, but put ANY
as value.
E.g.
There is a student with several grades indicated by attribute grades.
A grade could be: 2,3,4,5 I need a count how many 2 grades he has (nrfail),
how many grades in total (nrgrades), and what is the mean (grmean).
{grades}nrfail  nrgradesgrmean
++++
ANY count(nrfail,{grades},2)count(nrfail,{grades})mean(grmean,{grades})
A rule without decision could serve as context switching point.
(Concerning the legacy
Contexts
we only have general
Conditional and
Decision now.)
Table classes
It is important to identify certain table classes.
These depend on the table contents.
Not all of these should be identified before the table design.
They could/should be identified during the design, before the analysis, or in order to asses the analysis possibilities.
The classes are not related to rule types, but to rule contents.
Some possible table types:
values only – no actions, assignment operator only (maybe some selection operators)
setting only – the same as the above, no actions, just att value modification
avr – the same as above, as above with AVR
full – with AVR and actions
Table structure
Inference control
Environmental interaction
Interpreter model
XML serialization
Prolog representation