Both sides previous revision
Previous revision
Next revision
|
Previous revision
|
hekate:ardplus [2009/03/19 13:04] kinio |
hekate:ardplus [2009/03/23 08:53] kinio |
| |
The main concepts behind ARD+ are: | The main concepts behind ARD+ are: |
* **attributive logic** based on the use of //attributes// for denoting certain properties in a system (ali-book-springer),[[hekate:bib:hekate_bibliography#ali2007flairs-granular|ali2007flairs-granular)]]. | * **attributive logic** based on the use of //attributes// for denoting certain properties in a system (ali-book-springer), [[hekate:bib:hekate_bibliography#ali2007flairs-granular|ali2007flairs-granular)]]. |
* **functional dependency** is a general relation between two or more attributes (or attribute sets), called "dependent" and "independent"; the relation is such as in order to determine the values of the dependent attributes, the values of the independent ones are needed. | * **functional dependency** is a general relation between two or more attributes (or attribute sets), called "dependent" and "independent"; the relation is such as in order to determine the values of the dependent attributes, the values of the independent ones are needed. |
* **graph notation** provides simple, standard, yet expressive means for knowledge specification, and transformation. | * **graph notation** provides simple, standard, yet expressive means for knowledge specification, and transformation. |
==== Syntax ==== | ==== Syntax ==== |
| |
The ARD+ method aims at capturing relations between //attributes// in terms of //Attributive Logic// (AL)~\cite{ali-book-springer,ali2007flairs-granular,gjn2008ruleapps}. | The ARD+ method aims at capturing relations between //attributes// in terms of //Attributive Logic// (AL)(ali-book-springer),([[hekate:bib:hekate_bibliography#ali2007flairs-granular|ali2007flairs-granular]]),([[hekate:bib:hekate_bibliography#gjn2008ruleapps|gjn2008ruleapps]]). |
It is based on the use of //attributes// for expressing knowledge about facts regarding world under consideration. | It is based on the use of //attributes// for expressing knowledge about facts regarding world under consideration. |
A typical atomic formula (fact) takes the form ''A(o) = d'', where ''A'' is an attribute, ''o'' is an object | A typical atomic formula (fact) takes the form ''A(o) = d'', where ''A'' is an attribute, ''o'' is an object |
and ''d'' is the current value of ''A'' for ''o''. | and ''d'' is the current value of ''A'' for ''o''. |
More complex descriptions take usually the form of conjunctions of such atoms and are omnipresent in the AI literature. | More complex descriptions take usually the form of conjunctions of such atoms and are omnipresent in the AI literature. |
Please read the separate [[.:ardplus:ardplussyntax|ARD+ SYNTAX]] page for details. | |
| === Attribute === |
| |
| Let there be given the following, pairwise disjoint sets of symbols:\\ |
| ''O'' -- a set of object name symbols,\\ |
| ''A'' -- a set of attribute names,\\ |
| ''D'' -- a set of attribute values (the //domains//). |
| |
| An attribute ''A<sub>i</sub>'' is a function (or partial function) of the form: |
| |
| A<sub>i</sub>:o → D<sub>i</sub>. |
| |
| where ''o ∈ O''. |
| |
| A generalized attribute $A<sub>i</sub>$ is a function (or partial function) of the form ''A<sub>i</sub>:o → 2<sup>D<sub>i</sub></sup>'', where ''2<sup>D<sub>i</sub></sup>'' is the family of all the subsets of D<sub>i</sub>, to let the attribute take more than a single value at a time. |
| |
| A relaxed attribute definition, regarding a single object can be stated as: |
| ''A<sub>i</sub>: A<sub>i</sub> → D<sub>i</sub>''. |
| |
| === Conceptual Attribute === |
| A conceptual attribute //A// is an attribute describing some general, abstract aspect of the system |
| to be specified and refined. |
| |
| Conceptual attribute names are capitalized, e.g.: ''WaterLevel''. |
| Conceptual attributes are being //finalized// during the design process, into, possibly multiple, physical attributes, see Def. [[#finalization_transformation|finalization]]. |
| |
| === Physical Attribute === |
| A physical attribute //a// is an attribute describing an aspect of the system with its domain defined. |
| |
| Names of physical attributes are not capitalized, e.g. ''theWaterLevelInTank1''. |
| By finalization, a physical attribute origins from one or more (indirectly) conceptual attributes, see Def. [[#finalization_transformation|finalization]]. |
| Physical attributes cannot be finalized, they are present in the final rules capturing knowledge about the system. |
| |
| === Property === |
| ''P'' is a non-empty set of attributes representing knowledge about certain part of the system being designed. |
| Such attributes //describe// the property. |
| |
| === Simple Property === |
| ''PS'' is a property which consists of (is described by) a //single// attribute. |
| |
| === Complex Property === |
| ''PC'' is a property which consists of (is described by) //multiple// attributes. |
| |
| === Dependency === |
| A dependency ''D'' is an ordered pair of properties |
| ''D<sub>1,2</sub>=[P<sub>1</sub>, P<sub>2</sub>]'', |
| where ''P<sub>1</sub>'' is the independent property, and ''P<sub>2</sub>'' depends functionally on ''P<sub>1</sub>''. |
| |
| === Derivative === |
| ''V'' is an ordered pair of properties, such as: |
| ''V=[P<sub>1</sub>, P<sub>2</sub>]'', |
| where ''P<sub>2</sub>'' is derived from ''P<sub>1</sub>'' upon transformation. |
| |
| === DPD === |
| A Design Process Diagram is a triple |
| ''R=[P,D,V]'' where ''P'' is a set of properties, ''D'' is a set of dependencies and ''V'' is a set of derivatives. |
| |
| === ARD+ === |
| An Attribute Relationship Diagram\\ |
| ''G'' is a pair\\ |
| ''G=[P, D]'',\\ |
| where ''P'' is a set of //properties//, and ''D'' is a set of //dependencies// if there is a //DPD// ''G=[P,D,V]''. |
| |
| |
| ===== Diagram Restrictions ===== |
| The diagram constitutes a //directed graph// with possible cycles. |
| |
| === TPH === |
| A Transformation Process History ''TPH'' is a pair: |
| ''TPH=[P,V]'' if there is a //DPD// ''G=[P,D,V]''. |
| |
| The ''TPH'' can be expressed as a directed graph with properties being nodes and derivatives being edges. |
| |
==== Transformations ==== | ==== Transformations ==== |
A transformed diagram ''G<sub>2</sub>'' constitutes a more detailed //diagram level//. | A transformed diagram ''G<sub>2</sub>'' constitutes a more detailed //diagram level//. |
| |
Please read the [[.:ardplus:ardplustransformation|ARD+ TRANSFORMATION]] page for details. | === Finalization Transformation === |
| Finalization ''TF'' is a function |
| which transforms a //DPD// ''R'' into ''R<sub>TF</sub>'' by transforming a simple property ''PS'' consisting of a single conceptual attribute into a ''P<sub>new</sub>'', where the attribute belonging to ''PS'' is substituted by one or more conceptual or physical attributes belonging to ''P''; |
| appropriate dependencies must be transformed as well and a derivative has to be introduced. |
| |
| It introduces more attributes (more knowledge) regarding particular property. |
| An interpretation of the substitution is, that new attributes belonging to ''P'' are more detailed and specific than attributes belonging to ''PS''. |
| |
| === Split Transformation === |
| A split transforms a //DPD// ''R'' into ''R<sub>TS</sub>'' by transforming a complex property ''PC'' into some number of properties (a set) ''P<sub>new</sub>''; appropriate dependencies and derivatives must be introduced. |
| |
| This transformation introduces new properties and defines functional relationships among them. |
| |
| === Attribute Disjunction === |
| Attribute sets belonging to each of the properties ''P<sub>1</sub> ... P<sub>r</sub>'' have to be disjoint. |
| |
| === Attribute Matching === |
| All attributes ''PC'' consists of have to belong to properties ''P<sub>1</sub>, ... P<sub>r</sub>''. |
| No new attributes can be introduced for properties ''P<sub>1</sub> ... P<sub>r</sub>''. |
| Such introduction is possible through //finalization// only (see Def. [[#Finalization_Transformation|finalization]]). |
| |
| === Attribute Pool === |
| All attributes ''PC'' consists of have to belong to ''[P<sub>1</sub>, ... P<sub>r</sub>]''. |
| |
| === Dependency Inheritance === |
| All dependencies in ''D<sub>PC</sub>'' have to be covered by dependencies in ''D<sub>new</sub>''. |
| If a ''PC'' depends on some property ''P<sub>x</sub>'' (or some property depends on it), such a dependence must be stated (in ''D<sub>new</sub>'') regarding at least one of the elements from ''P<sub>new</sub>'' and ''P<sub>x</sub>''. |
| |
| === Transformation Limit === |
| A number of transformations in a single design step |
| is limited to //one per property//. |
| It means that a property can be either //split// or //finalized// but not both. |
| |
==== Refactoring ==== | ==== Refactoring ==== |
| |
==== Semantics ==== | ==== Semantics ==== |
| The semantics of ARD+ will be explained and visualized using a reworked //Thermostat example//, discussed in (ali-book-springer), ([[hekate:bib:hekate_bibliography#gjn2005:kkio|gjn2005:kkio]]). |
| The goal of the system is to set the temperature in the office to the given set-point, based on the current time. |
| |
| A property always consists of a set of attributes, these attributes identify such a property uniquely. |
| The single most important concept in ARD+ is the concept of the //property functional dependency//. |
| It indicates that in order to evaluate a dependent property, all independent properties have to be evaluated first. |
| It means, that in order to calculate dependent property attribute values, independent properties attribute values have to be calculated first. |
| It indicates that a property described by ''Temperature'' depends on a property described by ''Time''. |
| |
| Identifying all possible properties and attributes in a system could be a very complex task. |
| Transformations (see [[#transformations|transformation]]) allow to gradually refine properties, attributes and functional dependencies in the system being designed. |
| This process ends when all properties are described by //physical attributes// and all functional dependencies among properties are defined. |
| |
| An example of the //finalization// is given in Figures: |
| |
| {{ .:ard-finalization-ex1.png?273x140 }} |
| |
| The top diagram represents the system before the finalization. |
| The property described by attribute ''Time'' is finalized. |
| As a result new attributes are introduced: ''Date'', ''Hour'', ''season'', ''operation''. |
| The outcome is the bottom diagram. |
| Semantics of this transformation is that the system property described by a //conceptual attribute// ''Time'', can be more adequately described by a set of more detailed attributes: ''Date'', ''Hour'', ''season'', ''operation'', which more precisely define the meaning ''Time'' in the design. |
| The two latter attributes are //physical// ones, used in the final rule implementation. |
| Finalization of properties based on such attributes is not allowed. |
| |
| An example of //simple finalization// is given in Figure: |
| |
| {{ .:ard-finalization-ex2.png?292x100 }} |
| |
| A property described by a //conceptual attribute// //Temperature// is finalized into a property described by a single //physical attribute// ''thermostat_settings''. |
| In other words, a general concept of temperature, represented by ''Temperature'', is to be represented by an attribute ''thermostat_settings''. |
| |
| Another ARD+ transformation is the //split//. |
| An example is given in Figure: |
| |
| {{ .:ard-split-dep1.png?353x136 }} |
| |
| The top diagram shows a situation before, and the bottom one after, the //split transformation//. |
| This //split// allows to refine new properties and define functional dependencies among them. |
| A property described by attributes: ''Date'', ''Hour'', ''season'', ''operation'', is split into two properties described by ''Date'', ''Hour'', and ''season'', ''operation'' appropriately. |
| Furthermore there is a functional dependency defined such as ''season'' and ''operation'' depend on ''Date'' and ''Hour''. |
| |
| During the split, some of the properties can be defined as functionally independent. |
| An example of such a split is given in Figure: |
| |
| {{ .:ard-split-indep1.png?306x154 }} |
| |
| Properties described by ''season'' and ''operation'' are functionally independent. |
| |
| The ARD+ design process based on transformations leads to a diagram representing properties described only by ''physical attributes''. |
| An example of such a diagram is given in Figure: |
| |
| {{ .:ard-therm-01.png?420x151 }} |
| |
| All properties of the designed system are identified. |
| Each of them is described by single //physical attribute//. |
| All functional dependencies are defined as well. |
| |
| Each transformation creates a more detailed diagram, introducing new attributes (//finalization//) or defining functional dependencies (//split//). |
| These more detailed diagrams are called //levels of detail// or just //diagram levels//. |
| In the above examples, transitions between two subsequent levels are presented. |
| A complete model consists of all the levels capturing knowledge about all //splits// and //finalizations//. |
| |
==== Hierarchical Model ==== | ==== Hierarchical Model ==== |
* big picture of the designed system. | * big picture of the designed system. |
| |
The implementation of such hierarchical model is provided through storing the lowest available, most detailed diagram level, and, additionally, information needed to recreate all of the higher levels, so called //Transformation Process History//, TPH for short (see Def. [[.ardplus:ardplussyntax#TPH|TPH]]). | The implementation of such hierarchical model is provided through storing the lowest available, most detailed diagram level, and, additionally, information needed to recreate all of the higher levels, so called //Transformation Process History//, TPH for short (see Def. [[#TPH|TPH]]). |
| |
The TPH captures information about changes made to properties at consecutive diagram levels. | The TPH captures information about changes made to properties at consecutive diagram levels. |
These changes are carried out through the transformations: split or finalization. | These changes are carried out through the transformations: split or finalization. |
The TPH forms a tree structure then, denoting what particular properties is split into or what attributes a particular property attribute is finalized into, according to Def. [[.ardplus:ardplussyntax#TPH|TPH]]. | The TPH forms a tree structure then, denoting what particular properties is split into or what attributes a particular property attribute is finalized into, according to Def. [[#TPH|TPH]]. |
| |
An example TPH for the transformation is given in Figure: | An example TPH for the transformation is given in Figure: |
| |
| |
Having a complete TPH and the most detailed level (namely ARD+), which constitute the //DPD// (according to Def. [[.:ardplus:ardplussyntax#DPD|DPD]]) it is possible to automatically recreate any, more general, level. | Having a complete TPH and the most detailed level (namely ARD+), which constitute the //DPD// (according to Def. [[#DPD|DPD]]) it is possible to automatically recreate any, more general, level. |
| |
===== Rule Prototyping Algorithm ===== | ===== Rule Prototyping Algorithm ===== |
| |
| The goal of the algorithm is to automatically build prototypes for rules from the ARD+ design ([[hekate:bib:hekate_bibliography#gjn2008aaia|gjn2008aaia]]). |
| The targeted rule base is structured, grouping rule sets in decision tables with explicit inference control. |
| It is especially suitable for the XTT rule representation. |
| Moreover, this approach is more generic, and can be applied to any forward chaining rules. |
| |
| The input of the algorithm is the most detailed ARD+ diagram, that has all of the physical attributes identified |
| (in fact, the algorithm can also be applied to higher level diagrams, generating rules for some parts of the system being designed). |
| The output is a set of //rule prototypes// in a very general format (''atts'' stands for attributes): |
| |
| <code> |
| rule: condition atts | decision atts |
| </code> |
| |
| The algorithm is //reversible//, that is having a set of rules in the above format, it is possible to recreate the most detailed level of the ARD+ diagram. |
| |
| In order to formulate the algorithm some basic subgraphs in the ARD+ structure are considered. |
| These are presented in Figures: |
| |
| {{ .:ard-case0.png?100x112 }} \\ |
| {{ .:ard-case1.png?100x112 }} |
| |
| Now, considering the ARD+ semantics (functional dependencies among properties), the corresponding rule prototypes are as follows: |
| |
| * for the case in Figure //ard-case0//: |
| |
| rule: e | f, g, h |
| |
| * for the case in Figure //ard-case1//: |
| |
| rule: a, b, c | d |
| |
| In a general case a subgraph in Figure: |
| |
| {{ .:ard-case-gen.png }} |
| |
| is considered. |
| |
| Such a subgraph corresponds to the following rule prototype: |
| <code> |
| rule: alpha, beta, gamma, aa | bb |
| rule: aa | xx, yy, zz |
| </code> |
| |
| Analyzing these cases a general prototyping algorithm has been formulated. |
| Assuming that a dependency between two properties is formulated as: |
| ''D(IndependentProperty,DependentProperty)'', |
| the algorithm is as follows: |
| * choose a dependency ''D: D(F,T), F ≠ T'', from all dependencies present in the design, |
| * find all properties ''F'', that ''T'' depends on: \\ let ''F<sub>T</sub> = [F<sub>Ti</sub>: D(F<sub>Ti</sub>,T), F<sub>Ti</sub> ≠ F]'', |
| * find all properties which depend on ''F'' and ''F'' alone:\\ let ''T<sub>F</sub>=[T<sub>Fi</sub>: D(F,T<sub>Fi</sub>), T<sub>Fi</sub> ≠ T, ¬∃ T<sub>Fi</sub>: (D(X,T<sub>Fi</sub>), X ≠ F )]'' |
| * if ''F<sub>T</sub> ≠ ∅, T<sub>F</sub> ≠ ∅'' then generate rule prototypes: |
| <code> |
| rule: F, FT1, FT2,... | T |
| rule: F | TF1, TF2,... |
| </code> |
| |
| * if ''F<sub>T</sub> = ∅, T<sub>F</sub> ≠ ∅'' then generate rule prototypes: |
| <code> |
| rule: F | T, TF1, TF2,... |
| </code> |
| |
| * if ''F<sub>T</sub> ≠ ∅, T<sub>F</sub> = ∅'' then generate rule prototypes: |
| <code> |
| rule: F, FT1, FT2,... | T |
| </code> |
| |
| * if ''F<sub>T</sub> = ∅, T<sub>F</sub> = ∅'' then generate rule prototypes: |
| <code> |
| rule: F | T |
| </code> |
| |
| * if there are any dependencies left goto step 1. |
| |
| Rule prototypes generated by the above algorithm can be further optimized. |
| If there are rules with the same condition attributes they can be merged. |
| Similarly, if there are rules with the same decision attributes they can be merged as well. |
| For instance, rules like: |
| <code> |
| rule: a, b | x ; rule: a, b | y |
| </code> |
| can be merged into a single rule: ''rule: a, b | x, y'' |
| |
| |
| The practical support form the ARD+ design method, including logical modelling, visualization, and the prototyping algorithm has been implemented in the VARDA. |
| |
===== Design Tool Prototype ===== | ===== Design Tool Prototype ===== |
| |
===== SPOOL ===== | ===== SPOOL ===== |