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 Attributive Language on which the rule is built,
• 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:

• XML serialization of the XTT model
• Prolog representation

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 low-level 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 (fixed-point) 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:

1. in Prolog there are no types (on the low-level)
2. in Java/C there are the so-called primitive data types, these are:

byte short int long, float double, char String, boolean,

1. so these Java types correspond to XTT primitive types
2. please note: at this level the Java system is NOT exandable at all!!!
3. 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).

• For RDB2Prolog see SWI ODBC
• 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. day-of-week of type symbolic, and be able to:

• use 1 instead of sun and vice versa
• compare mon < tue

In this case it is still a symbolic domain, so we store “mon” not 2!!!

This corresponds to the so-called 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 non-atomic values (multiple) – this has to be specified explicitly. Number of values, for non-atomic attributes, is not bounded.

So an attribute value, for non-atomic 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

• is identified by name
• can have an abbreviated name
• can have a description

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:

1. define a named attribute year as integer with domain <0,upper>
2. define a named attribute month as integer with domain <1-12> (see ordered symbolic domains )
3. define a named attribute day as symbolic with domain {mon-sun}
4. 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

1. suppose we have a natural language spec, we have “some temperature”
2. create attribute type
1. pick a attribute type name, e.g. “Temperature”
2. decide what primitive type to use
3. define the domain by specifying constraints
4. decide whether the domain is ordered - in case of symbolic base type, numbers are ordered
3. create new attribute, with given
1. attribute type, in this case of “Temperature”
2. name, e.g. sensor_temperature
3. decide whether the attribute can take only atomic values, or also multiple or non-atomic 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.

1. we define “day” as a numeric integer attribute with constraints <1,30>
2. we define “month” as a symbolic attribute with values jan-dec and an ordered domain 1-12
3. we define “year” as a numeric integer attribute with constraints e.g. 1970-MAX
4. we define a guped attribute type “date” having day, month, and year.
5. 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

check how current ATTML correspnds to the above

Rule syntax

imported from xtt+ refined

It should be kept in mind, that we must not mix he issues such as:

• rules with multiple valued attributes vs.
• rule syntax vs.
• rule inference vs.
• rule environment interaction

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 rule-based 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 decision-tree 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 (ben-ari:2001,ali-book-springer), 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 (ali-book-springer) described in more detail elsewhere. This gives much more power than the propositional logic, but does not introduce problems of the predicate logic-based inference.

In XTT an extended rule semantics is used. These extensions were introduced in (gjn2007enase), and refined in (gjn2007inap). They are: Grouped Attributes, and Attribute-Attribute Comparison

Other (gjn2007enase) extensions such as Link Labeling, Not-Defined 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:

1. condition checking and
2. 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:

• attribute value change
• context switching through inference control links
• event triggering - action execution.

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/salrules-ki.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 salrules-ruleapps):

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:

• Attribute always have finite sets of values. (refernece A)
• In rule condition we always have finite sets of values.(refernece V)

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 non-continous 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

• rule condition (and markup!) (the Vs),
• as well as the attribute domain specification

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 so-called Attribute-Attribute 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.

Decision format

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 so-called 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 modops are proposed.

Assignement

Denoted as =

The simplest case

• SVM –> A is V is(A,V)
• MVM –> {A} is {V}, from logical p-o-v: A = {V}, that is A is a singleton, is({A},{V})
Assert/Retract

Assert Denoted as +

• SVM –> N.A.
• MVM –> {A} assert {V}, the value V is asserted to the set of values (sov) of A

Retract Denoted as -

• SVM –> N.A.
• MVM –> {A} retract {V}, the value V is retracted, removed from the sov A

Now, depending on the multivalue semantics, we could consider

• asserta/z, retracta/z
• retractall given vals from the set
• etc. …

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 OO-like 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, evalops for short. i.e. arithmetic expressions can be calculated this way.

evalops could be nested, i.e.

add(2,div(3,sin(d)))

evaluates as: 2+(3/(sin(d)))

evalops 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 type-dependent.

• SVM –> N.A.
• MVM –> {A} select (C) …, e.g. select({A},lt(3))

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?

Metas

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

• SVM –> we should be able to use arithmetic expressions with + - * /
• MVM –> {A}

So we support any artithemtic expression, including a set of predefined math-only 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 evalops 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 OO-like proposal, the action has to bound with the att whose value it changes.

OO-like 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                  |              nrgrades|grmean
--------++------------------------+----------------------+---------------------
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

see the XTTML