--- hekate:ardplus [2009/03/19 10:47]
kinio
+++ hekate:ardplus [2019/06/27 15:49] (current)
@@ Line 18: / Line 18: @@
 The KE approach assumes that information about how the system works can be inferred automatically from what is known about the system.
-In real life the **design** process support (as a process of building the design) is much more important than just providing means to visualize and construct the **design** (which is a kind of knowledge snapshot about the system).
+In real life the //design// process support (as a process of building the design) is much more important than just providing means to visualize and construct the //design// (which is a kind of knowledge snapshot about the system).
-Another observation can be also made: **designing** is in fact
+Another observation can be also made: //designing// is in fact
-a knowledge-based process, where the **design** is often
+a knowledge-based process, where the //design// is often
 considered a structure with procedures needed to build it (it is at least
 often the case in the SE).
@@ Line 30: / Line 30: @@
 The next stage is the rule implementation.
 It is usually targeted at specific rule engine.
-Some examples of such engines are: **CLIPS**, **Jess**, and **JBoss Rules** (formerly **Drools**).
+Some examples of such engines are: //CLIPS//, //Jess//, and //JBoss Rules// (formerly //Drools//).
 The rule engine enforces a strict syntax on the rule language.
 Another aspect of the design - in a very broad sense - is a rule encoding, in a machine readable format.
 In most cases it uses an XML-based representation.
-There are some well-established standards for rule markup languages:, e.g. **RuleML** and notably **RIF** (see [[http://www.w3.org/2005/rules]]).
+There are some well-established standards for rule markup languages:, e.g. //RuleML// and notably //RIF// (see [[http://www.w3.org/2005/rules]]).
 ==== History and Related Documents ====
-The original ARD method was first proposed by A. Ligęza in (ali-book) and later on developed and described by G. J. Nalepa and A. Ligęza in [[hekate:bib:hekate_bibliography#gjn2005:kkio|(gjn2005:kkio)]](ali-book-springer).
+The original ARD method was first proposed by A. Ligęza in [[hekate:bib:hekate_bibliography#ali-book|(ali-book)]] and later on developed and described by G. J. Nalepa and A. Ligęza in [[hekate:bib:hekate_bibliography#gjn2005:kkio|(gjn2005:kkio)]], (ali-book-springer).
 It was a supportive, and potentially optional, design method for XTT [[hekate:bib:hekate_bibliography#gjn2005:syssci:xtt|(gjn2005:syssci:xtt)]].
 It provided simple means of attribute identification for the XTT method.
@@ Line 52: / Line 52: @@
 that would support the hierarchical and gradual design aspect covering the entire process.
 Such a method should be formalized with use of some logic-based calculus in order to allow a formal analysis.
-The research presented in this paper is a part of the **HeKatE** project,
+The research presented in this paper is a part of the //HeKatE// project,
 that aims at providing an integrated  and hierarchical
 rule design and implementation method for rule-based systems.
@@ Line 62: / Line 62: @@
 ==== Preliminary Concepts ====
+The ARD+ method aims at supporting the rule designer at a very general design level, where the conceptualization of the design takes place [[hekate:bib:hekate_bibliography#gjn2008flairs-ardformal|(gjn2008flairs-ardformal)]], [[hekate:bib:hekate_bibliography#gjn2008aaia|(gjn2008aaia)]].
+It is a knowledge-based approach, based on some classic AI methods (norvig).
+ARD+ covers //requirements specification// stage.
+Its //input// is a general systems description in the natural language.
+Its //output// is a model capturing knowledge about relationships among attributes describing system properties.
+The model is subsequently used in the next design stage, where the actual logical design with //rules// is carried out.
+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)]].
+  * **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.
+  * **visualization** is the key concept in the practical design support, provided by this method.
+  * **gradual refinement** is the main design approach, where the design is being specified in number of steps, each step being more detailed than the previous one.
+  * **structural transformations** are  //formalized//, with well defined syntax and semantics.
+  * **hierarchical model** captures all of the subsequent design steps, with no semantic gaps; it holds knowledge about the system on the different abstraction levels [[hekate:bib:hekate_bibliography#gjn2007iwk|(gjn2007iwk)]].
+  * **knowledge-based approach** provides means of the //declarative// model specification.
+Based on these concepts, a formalization of the method is put forward in the following section.
 ==== Syntax ====
+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.
+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''.
+More complex descriptions take usually the form of conjunctions of such atoms and are omnipresent in the AI literature.
+=== 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 ====
+Diagram transformations are one of the core concepts in the ARD+.
+They serve as a tool for diagram specification and development.
+For the transformation ''T'' such as ''T: G<sub>1</sub> → G<sub>2</sub>'', where ''G<sub>1</sub>'' and ''G<sub>2</sub>'' are both diagrams, the diagram ''G<sub>2</sub>'' carries more system related knowledge, is more specific and less abstract than the ''G<sub>1</sub>''.
+All of the transformations regard //properties//.
+Some transformations are required to specify additional //dependencies// or introduce new //attributes// though.
+A transformed diagram ''G<sub>2</sub>'' constitutes a more detailed //diagram level//.
+=== 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 ====
+During the design process some properties or attributes can be missed or treated as not important, hence not included in the diagram.
+Refactoring allows to incorporate such artifacts or remove unnecessary ones.
+Refactoring consists in modifying any of the existing transformations: //finalization// or //split// in a particular ARD+ diagram.
+=== Finalization ===
+A //Finalization Refactoring// consist in adding or removing an attribute, modifying a past finalization transformation.
+Removing an attribute ''A<sub>r</sub>'' results in removing it from all already defined complex properties.
+If there is a simple property which regards such an attribute, it should be removed then.
+The //Finalization Refactoring// with adding an attribute implies that at some point a split has to be performed on a property involving the new attribute.
+Furthermore, appropriate dependencies between the property which consists of the introduced attribute and other properties have to be stated as well.
+This constitutes a //Split Refactoring//
+=== Split ===
+In general a //Split Refactoring// regards:
+  * adding or removing properties upon already defined splits,
+  * rearranging already defined dependencies.
+Removing a property implies that all other properties that were split from it, even transitionally, have to be removed.
+Adding a property leads to defining its dependencies, between the property and other already defined ones.
+In general adjusting dependencies can be based on:
+  * defining dependencies between the property and other existing properties at the //most detailed// diagram level, or
+  * adjusting appropriate  past split transformations gradually (at previous diagram levels) to take this new property into consideration.
+In the first case the dependencies are defined for the most detailed diagram level only.
+Since there is a hierarchical design process (see Sec. [[ardplus#Hierarchical_Model|Hierarchical Model]]), these changes are taken into consideration at previous levels  automatically.
+The second case implies that the designer updates appropriate past splits in a gradual refinement process.
+Stopping this process at more general level than the most detailed one, generates appropriate splits in all more detailed levels automatically.
 ==== 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 ====
+During the design process, upon splitting and finalization, the ARD+ model grows, becoming more and more specific.
+This process constitutes the //hierarchical model//.
+Consecutive levels make a hierarchy of more and more detailed diagrams describing the designed system.
+The purposes of having the hierarchical model are:
+  * gradual refinement of a designed system, and particularly,
+  * identification where given properties come from,
+  * ability to get back to previous diagram levels for refactoring purposes,
+  * 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. [[#TPH|TPH]]).
+The TPH captures information about changes made to properties at consecutive diagram levels.
+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. [[#TPH|TPH]].
+An example TPH for the transformation is given in Figure:
+{{ :hekate:final-tph.png }}
+It indicates that a property described by an attribute ''Time'' is refined into a property described by attributes: ''Date'', ''Hour'', ''season'', ''operation''.
+Another TPH example for the split transformation is given in Figure:
+{{ :hekate:split-tph.png }}
+It indicates that a property described by attributes: ''Date'', ''Hour'', ''season'', ''operation'' is refined into two properties described by: ''Date'', ''Hour'' and ''season'', ''operation'' attributes respectively.
+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 =====
+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 =====
 ===== SPOOL =====

hekate/ardplus.1237456032.txt.gz · Last modified: 2019/06/27 16:00 (external edit)

Show page Old revisions

Media Manager Back to top

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

HeKatE

Differences