====== 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 [[xtt#Attributive Language]] on which the rule is built,
* the [[xtt#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:
- in Prolog there are no types (on the low-level)
- in Java/C there are the so-called //[[http://java.sun.com/docs/books/tutorial/java/nutsandbolts/datatypes.html|primitive data types]]//, these are:
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).
* For RDB2Prolog see [[http://www.swi-prolog.org/packages/odbc.html#sec:2.6|SWI ODBC]]
* See also [[http://www.unixodbc.org/|UnixODBC]]
* Java/Prolog types mapping in [[http://www.swi-prolog.org/packages/jpl/prolog_api/overview.html#JPL_types_Java_types_as_seen_by|JPL]] FIXME
* There is no ''binary'' type (blob) FIXME 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:
- define a named attribute //year// as ''integer'' with domain <0,upper>
- define a named attribute //month// as ''integer'' with domain <1-12> (see ordered symbolic domains FIXME)
- define a named attribute //day// as ''symbolic'' with domain {mon-sun}
- 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 //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.
- we define "day" as a numeric integer attribute with constraints ''<1,30>''
- we define "month" as a symbolic attribute with values ''jan-dec'' and an ordered domain ''1-12''
- we define "year" as a numeric integer attribute with constraints e.g. ''1970-MAX''
- 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
FIXME
==== Attribute Markup ====
see: [[hekate markup language]]
FIXME
check how current ATTML correspnds to the above
===== Rule syntax =====
imported from [[hekatedev:xtt_rules#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:
- 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:
* 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.
FIXME 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 :=
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 //V//s),
* 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.:
* [[http://gollem.science.uva.nl/SWI-Prolog/Manual/lists.html|List/Set Manipulation]]
* [[http://gollem.science.uva.nl/SWI-Prolog/Manual/nbset.html|Non-backtrackable set]]
* [[http://gollem.science.uva.nl/SWI-Prolog/Manual/ordsets.html|Ordered Set Manipulation]]
* [[http://gollem.science.uva.nl/SWI-Prolog/Manual/clpfd.html|Constraint Logic Programming over Finite Domains]]
=== Attribute Value Reference ===
The AVR is a situation such as:
* ''A1 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. ...
FIXME
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? FIXME 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).
FIXME
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 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.
FIXME
All of these apply only to the MVM?
FIXME
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
''[[wp>math.h]]'' or rather ''[[http://java.sun.com/javase/6/docs/api/java/lang/Math.html|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 OO-like proposal, the action has to bound with the att whose value it changes.
=== OO-like proposal ===
FIXME
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 [[hekatedev: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
===== Table structure =====
===== Inference control =====
===== Environmental interaction =====
===== Interpreter model =====
===== XML serialization =====
see the [[hekate:hekate_markup_language#XTTML]]
===== Prolog representation =====