Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:miw:2009:present:alsvfd [2009/05/19 18:44] jsi08 |
pl:miw:2009:present:alsvfd [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 9: | Linia 9: | ||
| ===== Introduction to Attributive Logics ===== | ===== Introduction to Attributive Logics ===== | ||
| - | Attributive logics constitute a simple yet widely-used tool for knowledge specification and development of rule-based systems. | + | * Attributive logics constitute a simple yet widely-used tool for knowledge specification and development of rule-based systems. |
| - | In fact in a large variety of applications in various areas of Artificial Intelligence (AI) and Knowledge Engineering (KE) attributive languages constitute the core knowledge representation formalism. | + | * In fact in a large variety of applications in various areas of Artificial Intelligence (AI) and Knowledge Engineering (KE) attributive languages constitute the core knowledge representation formalism. |
| - | The most typical areas of applications include rule-based systems, expert systems (ones based on rule formalism) and advanced database and data warehouse systems with knowledge discovery applications and contemporary business rules and business intelligence components. | + | * The most typical areas of applications include rule-based systems, expert systems (ones based on rule formalism) and advanced database and data warehouse systems with knowledge discovery applications and contemporary business rules and business intelligence components. |
| + | |||
| + | ===== Introduction to Attributive Logics ===== | ||
| The description of AL presented here is based on several papers, including | The description of AL presented here is based on several papers, including | ||
| Linia 22: | Linia 24: | ||
| ===== ALSV(FD) ===== | ===== ALSV(FD) ===== | ||
| - | In SAL (//Set Attributive Logic//) as well as in its current version ALSV(FD), the very basic idea is that attributes can take //atomic// or //set// values. | + | * In SAL (//Set Attributive Logic//) as well as in its current version ALSV(FD), the very basic idea is that attributes can take //atomic// or //set// values. |
| - | After [[hekate:bib:hekate_bibliography#ali2005thebook|(ali2005thebook)]] it is assumed that an //attribute// A_i is a function (or partial function) of the form | + | * After [[hekate:bib:hekate_bibliography#ali2005thebook|(ali2005thebook)]] it is assumed that an //attribute// A_i is a function (or partial function) of the form <latex> |
| - | <latex> | + | |
| $A_{i}\colon O \to D_{i}$. | $A_{i}\colon O \to D_{i}$. | ||
| - | </latex> | + | </latex> Here //O// is a set of objects and //D_i// is the domain of attribute //A_i//. |
| - | Here //O// is a set of objects and //D_i// is the domain of attribute //A_i//. | + | |
| - | A //generalized attribute// A_i is a function (or partial function) of the form | + | * A //generalized attribute// A_i is a function (or partial function) of the form <latex> |
| - | <latex> | + | |
| $A_{i}\colon O \to 2^{D_{i}}$ | $A_{i}\colon O \to 2^{D_{i}}$ | ||
| - | </latex> | + | </latex> where 2^D_i is the family of all the subsets of D_i. |
| - | where 2^D_i is the family of all the subsets of D_i. | + | |
| - | The basic element of the language of //Attribute Logic with Set Values over Finite Domains// (ALSV(FD) for short) are attribute names and attribute values. | + | ===== ALSV(FD) ===== |
| - | For simplicity of presentation no objects are considered here; in practice, the same attribute applied to two (or more) different objects can be considered as two (or more) new, different, object-labelled attributes. Moreover, unless two (or more) different objects are considered at the same time, no explicite reference to an object is necessary. | + | |
| - | Let us consider: | + | * The basic element of the language of //Attribute Logic with Set Values over Finite Domains// (ALSV(FD) for short) are attribute names and attribute values. |
| - | * A -- a finite set of attribute names, | + | * For simplicity of presentation no objects are considered here; in practice, the same attribute applied to two (or more) different objects can be considered as two (or more) new, different, object-labelled attributes. |
| - | * D -- a set of possible attribute values (the domains). | + | * Unless two (or more) different objects are considered at the same time, no explicite reference to an object is necessary. |
| - | Let | + | ===== ALSV(FD) ===== |
| - | A = A_1, A_2, ... ,A_n | + | |
| - | be all the attributes such that their values define the state of the system under consideration. | + | |
| - | It is assumed that the overall domain //D// is divided into //n// sets (disjoint or not), | + | |
| - | D = D_1 u D_2 u ... u D_n, | + | |
| - | where D_i is the domain related to attribute | + | |
| - | A_i, i=1,2, ... ,n. | + | |
| - | Any domain D_i is assumed to be a finite (discrete) set. | + | * Let us consider: |
| - | The set can be ordered, partially ordered, or unordered; in case of ordered (partially ordered) sets some modifications of the notation are allowed. | + | * A -- a finite set of attribute names, |
| + | * D -- a set of possible attribute values (the domains). | ||
| + | * Let A = A_1, A_2, ... ,A_n be all the attributes such that their values define the state of the system under consideration. It is assumed that the overall domain //D// is divided into //n// sets (disjoint or not), D = D_1 u D_2 u ... u D_n, where D_i is the domain related to attribute A_i, i=1,2, ... ,n. | ||
| + | * Any domain D_i is assumed to be a finite (discrete) set. The set can be ordered, partially ordered, or unordered; in case of ordered (partially ordered) sets some modifications of the notation are allowed. | ||
| - | As we consider dynamic systems, the values of attributes can change over time (or state of the system). | + | ===== ALSV(FD) ===== |
| - | We consider both //simple// attributes of the form | + | |
| - | A_i : T -> D_i | + | |
| - | (i.e. taking a single value at any instant of time) and | + | |
| - | //generalized// ones of the form | + | |
| - | A_i: T -> 2^D_i | + | |
| - | (i.e. taking a set of values at a time); here //T// denotes the time domain of discourse. | + | |
| - | ==== Syntax ==== | + | * As we consider dynamic systems, the values of attributes can change over time (or state of the system). |
| + | * We consider both //simple// attributes of the form A_i : T -> D_i (i.e. taking a single value at any instant of time) and //generalized// ones of the form A_i: T -> 2^D_i (i.e. taking a set of values at a time); here //T// denotes the time domain of discourse. | ||
| - | The legal atomic formulae of ALSV for //simple attributes// are presented in the Table 1. | + | ===== Syntax ===== |
| - | + | ||
| - | + | ||
| - | <latex> | + | |
| - | \begin{table} | + | |
| - | \begin{tabular}{|l|l|l|l|} | + | |
| - | \hline | + | |
| - | Syntax & Description &Relation & Example\\ \hline \hline | + | |
| - | $A_{i} = d$ & %\label{atom-element-equal} | + | |
| - | the value is precisely defined & \texttt{eq} & \\\hline | + | |
| - | + | ||
| - | $A_{i} \neq d$ & %\label{atom-element-notequal} | + | |
| - | shorthand for $A_{i} \in D_{i}\setminus \{d \}.$ & \texttt{neq}& \\\hline | + | |
| - | + | ||
| - | $A_{i} \in V_{i}$ & %\label{atom-element-subset} | + | |
| - | any of the values $d\in V_{i}$ satisfies the formula% | + | |
| - | \footnote{equivalent to $(A_{i} = d_{1})\otimes (A_{i} = d_{2})\otimes\ldots \otimes (A_{i} = d_{k})$, where $V_{i} = \{d_{1}, d_{2},\ldots,d_{k} \}$ and $\otimes$ is stay for exclusive-or}% | + | |
| - | & \texttt{in}& \\\hline | + | |
| - | + | ||
| - | $A_{i} \not\in V_{i}$ & %\label{atom-element-notsubset} | + | |
| - | is a shorthand for $A_{i} \in D_{i}\setminus V_{i}$.& \texttt{notin}& \\ \hline | + | |
| - | \end{tabular} | + | |
| - | \end{table} | + | |
| - | </latex> | + | |
| {{:hekate:salrules-flairs-table1.png|}} | {{:hekate:salrules-flairs-table1.png|}} | ||
| - | Table 1: Simple attribute formulas syntax | + | ===== Syntax ===== |
| - | + | ||
| - | The legal atomic formulae of ALSV for //generalized attributes// are presented in the Table 2. | + | |
| - | + | ||
| - | <latex> | + | |
| - | \begin{table} | + | |
| - | \begin{tabular}{|l|l|l|l|} | + | |
| - | \hline | + | |
| - | Syntax & Description & Relation & Example\\ \hline \hline | + | |
| - | + | ||
| - | $A_{i} = V_{i}$ & %\label{atom-set-equal} | + | |
| - | equal to $V_{i}$ (and nothing more) & \texttt{eq} & \\\hline | + | |
| - | + | ||
| - | $A_{i} \neq V_{i}$ & %\label{atom-set-notequal} | + | |
| - | different from $V_{i}$ (at at least one element) & \texttt{neq} & \\\hline | + | |
| - | + | ||
| - | $A_{i} \subseteq V_{i}$ & %\label{atom-set-subset} | + | |
| - | being a subset of $V_{i}$ & \texttt{subset} & \\\hline %\texttt{subseteq} & | + | |
| - | + | ||
| - | $A_{i} \supseteq V_{i}$ & %\label{atom-set-supset} | + | |
| - | being a superset of $V_{i}$ & \texttt{supset}& \\\hline %\texttt{superseteq} & | + | |
| - | + | ||
| - | $A \sim V_{i}$ & %\label{atom-set-sim} | + | |
| - | having a non-empty intersection with $V_{i}$ <del>or disjoint to $V_{i}$</del> & \texttt{sim}& \\\hline | + | |
| - | + | ||
| - | $A_{i} \not\sim V_{i}$ & %\label{atom-set-notsim} | + | |
| - | having an empty intersection with $V_{i}$ (or disjoint to $V_{i}$) & | + | |
| - | \texttt{notsim} & \\ \hline | + | |
| - | \end{tabular} | + | |
| - | \end{table} | + | |
| - | </latex> | + | |
| {{:hekate:salrules-flairs-table2.png|}} | {{:hekate:salrules-flairs-table2.png|}} | ||
| - | Table 2: Generalized attribute formulas syntax | + | ===== Syntax ===== |
| - | In case V_i is an empty set (the attribute takes in fact no value) we shall write A_i = ' '. | + | * In case V_i is an empty set (the attribute takes in fact no value) we shall write A_i = ' '. |
| + | * More complex formulae can be constructed with //conjunction// ''^'' ($\wedge$) and //disjunction// ''v''; both the symbols have classical meaning and interpretation. | ||
| + | * //There is no explicit use of negation.// | ||
| - | See [[hekate:alsvfd#any and null]] | + | ===== Syntax ===== |
| - | More complex formulae can be constructed with //conjunction// ''^'' ($\wedge$) and //disjunction// ''v''; | + | * The proposed set of relations is selected for convenience and as such is not completely independent. For example, A_i = V_i can perhaps be defined as A_i \subset V_{i} ^ A_i \supset V_i; but it is much more concise and convenient to use ''='' directly. |
| - | both the symbols have classical meaning and interpretation. | + | * Various notational conventions extending the basic notation can be used. For example, in case of domains being ordered sets, relational symbols such as >, >=, <, =< can be used with the straightforward meaning. |
| - | //There is no explicit use of negation.// | ||
| - | The proposed set of relations is selected for convenience and as such is not completely independent. | + | ===== Semantics ===== |
| - | For example, A_i = V_i can perhaps be defined as A_i \subset V_{i} ^ A_i \supset V_i; | + | * In SAL the semantics of A_i=d is straightforward -- the attribute takes a single value. |
| - | but it is much more concise and convenient to use ''='' directly. | + | * The semantics of A_i=t is that the attribute takes //all// the values of //t// (the so-called //internal conjunction//) while the semantics of A_i \in t is that it takes //one// (in case of simple attributes) or //some// (in case of generalized attributes) of the values of //t// (the so-called //internal disjunction//). |
| + | * As an example for the necessity of SAL one can consider the specification of working days (denoted with //WDay//) given as //WDay = D//, where D is the set of working days, D = { Monday,Tuesday,Wednesday,Thursday,Friday }. Now one can construct an atomic formula like CurrentDay \in D, or a rule of the form: DayOfInterest \in D -> Status(OfficeOfInterest) = open. | ||
| - | Various notational conventions extending the basic notation can be used. | + | ===== Semantics ===== |
| - | For example, in case of domains being ordered sets, relational symbols such as | + | |
| - | >, >=, <, =< | + | |
| - | can be used with the straightforward meaning. | + | |
| + | * The semantics of <latex>$A = V$</latex> is basically the same as the one of basic SAL. | ||
| + | * If <latex>$V = \{d_{1}, d_{2},\ldots, d_{k} \}$</latex> then <latex>$A = V$</latex> is equivalent to <latex> $A \supseteq \{d_{1}\}\wedge A \supseteq \{d_{2}\}\wedge\ldots\wedge A \supseteq \{d_{k}\}$ </latex> i.e. the attribute takes all the values specified with <latex>$V$</latex> (and nothing more). | ||
| + | * The semantics of <latex>$A\subseteq V$</latex>, <latex>$A \supseteq V$</latex> and <latex>$A \sim V$</latex> is defined as follows: | ||
| + | * <latex> $A\subseteq V \equiv A=U$ </latex> where //U subset V//, i.e. //A// takes //some// of the values from //V// (and nothing out of //V//), | ||
| + | * <latex> A\supseteq V \equiv A=W, </latex> where //V subset W//, i.e. //A// takes //all// of the values from //V// (and perhaps some more), | ||
| + | * <latex> A\sim V \equiv A= X, </latex> where <latex> $V \cap X \neq \emptyset$, </latex> i.e. //A// takes //some// of the values from //V// (and perhaps some more). | ||
| + | * As it can be seen, the semantics of ALSV is defined by means of relaxation of logic to simple set algebra. | ||
| - | ==== Semantics ==== | + | ===== Inference Rules ===== |
| - | In SAL the semantics of A_i=d is straightforward -- the attribute takes a single value. | + | |
| - | The semantics of A_i=t is that the attribute takes //all// the values of //t// (the so-called //internal conjunction//) while the semantics of | + | * Let //V// and //W// be two sets of values such that //V subset W//. We have the following straightforward inference rules for atomic formulae: <latex> $\frac{A \supseteq W}{A \supseteq V}$ </latex> i.e. if an attribute takes all the values of a certain set it must take all the values of any subset of it (downward consistency). |
| - | A_i \in t | + | * Similarly <latex> $\frac{A \subseteq V}{A \subseteq W}$ \end{equation} </latex> i.e. if the values of an attribute takes values located within a certain set they must also belong to any superset of it (upward consistency). |
| - | is that it takes //one// (in case of simple attributes) or //some// (in case of generalized attributes) of the values of //t// (the so-called //internal disjunction//). | + | * These rules seem a bit trivial, but they must be implemented for enabling inference, e.g they are used in the rule precondition checking. |
| - | As an example for the necessity of SAL one can consider the specification of working days (denoted with //WDay//) given as | + | ===== Inference Rules ===== |
| - | //WDay = D//, | + | |
| - | where D is the set of working days, D = { Monday,Tuesday,Wednesday,Thursday,Friday }. | + | |
| - | Now one can construct an atomic formula like CurrentDay \in D, or a rule of the form: | + | |
| - | DayOfInterest \in D -> Status(OfficeOfInterest) = open. | + | |
| + | {{:hekate:salrules-flairs-table3.png|}} | ||
| - | The semantics of $A = V$ is basically the same as the one of basic SAL. | + | * The table is to be read as follows: if an atomic formula in the leftmost column holds, and a condition stated in the same row is true, the to appropriate atomic formula in the topmost row is a logical consequence of the one from the leftmost column. |
| - | If $V = \{d_{1}, d_{2},\ldots, d_{k} \}$ then $A = V$ is equivalent to | + | |
| - | <latex> | + | |
| - | $A \supseteq \{d_{1}\}\wedge A \supseteq \{d_{2}\}\wedge\ldots\wedge A \supseteq \{d_{k}\}$ | + | |
| - | </latex> | + | |
| - | i.e. the attribute takes all the values specified with $V$ (and nothing more). | + | |
| - | The semantics of $A\subseteq V$, $A \supseteq V$ and $A \sim V$ is defined as follows: | + | ===== Inference Rules ===== |
| - | <latex> | + | {{:hekate:salrules-flairs-table4.png|}} |
| - | $A\subseteq V \equiv A=U$ | + | |
| - | </latex> | + | |
| - | where | + | |
| - | //U subset V//, | + | |
| - | i.e. //A// takes //some// of the values from //V// (and nothing out of //V//), | + | |
| - | <latex> | + | FIXME |
| - | A\supseteq V \equiv A=W, | + | (The rules must be checked; simple rules are for matching preconditions to the state formula. More complex rules can be for establishing truth-value propagation among atoms of preconditions within a table). |
| - | </latex> | + | 8-O 8-O 8-O |
| - | where | + | |
| - | //V subset W//, | + | |
| - | i.e. //A// takes //all// of the values from //V// (and perhaps some more), and | + | |
| - | <latex> | + | ===== Inference Rules ===== |
| - | A\sim V \equiv A= X, | + | |
| - | </latex> | + | |
| - | where | + | |
| - | <latex> | + | |
| - | $V \cap X \neq \emptyset$, | + | |
| - | </latex> | + | |
| - | i.e. //A// takes //some// of the values from //V// (and perhaps some more). | + | |
| - | As it can be seen, the semantics of ALSV is defined by means of relaxation of logic to simple set algebra. | + | * In Tables 3 and 4 the conditions are //satisfactory// ones. |
| + | * It is important to note that in case of the first rows of the tables (the cases of A=d_i and A=V, respectively) all the conditions are also //necessary// ones. | ||
| + | * The interpretation of the tables is straightforward: if an atomic formula in the leftmost column in some row //i// is true, then the atomic formula in the topmost row in some column //j// is also true, provided that the relation indicated on intersection of row //i// and column //j// is true. | ||
| + | * The rules of Table 3 and Table 4 can be used for checking if preconditions of a formula hold or verifying subsumption among rules. | ||
| - | ==== Inference Rules ==== | + | ===== Inference Rules ===== |
| - | Let //V// and //W// be two sets of values such that //V subset W//. We have the following straightforward inference rules for atomic formulae: | + | {{:hekate:salrules-flairs-table5.png|}} |
| - | <latex> | + | |
| - | $\frac{A \supseteq W}{A \supseteq V}$ | + | |
| - | </latex> | + | |
| - | i.e. if an attribute takes all the values of a certain set it must take all the values of any subset of it (downward consistency). | + | |
| - | Similarly | + | * The interpretation of the Table 5 is straightforward: if the condition specified at the intersection of some row and column holds, then the atomic formulae labelling this row and column cannot simultaneously hold. Note however, that this is a satisfactory condition only. |
| - | <latex> | + | * The Table can be used for analysis of determinism of the system, i.e. whether satisfaction of precondition of a rule implies that the other rules in the same table cannot be fired. |
| - | $\frac{A \subseteq V}{A \subseteq W}$ | + | |
| - | \end{equation} | + | |
| - | </latex> | + | |
| - | i.e. if the values of an attribute takes values located within a certain set they must also belong to any superset of it (upward consistency). | + | |
| - | These rules seem a bit trivial, but they must be implemented for enabling inference, e.g they are used in the rule precondition checking. | + | ===== State, State Representation and Inference ===== |
| - | The summary of the inference rules for atomic formulae with simple attributes (where an atomic formula is the logical consequence of another atomic formula) is presented in Table 3. | + | * When processing information, the current values of attributes form the state of the inference process. |
| - | The table is to be read as follows: if an atomic formula in the leftmost column holds, and a condition stated in the same row is true, the to appropriate atomic formula in the topmost row is a logical consequence of the one from the leftmost column. | + | * The values of attributes can, in general, be modified in the following three ways: |
| + | - by an independent, external system, | ||
| + | - by the inference process, and | ||
| + | - as some clock-dependent functions. | ||
| - | <latex> | + | ===== State, State Representation and Inference ===== |
| - | \begin{table} | + | |
| - | \caption{Inference rules for atomic formulae for simple attributes} | + | |
| - | \begin{center} | + | |
| - | %\begin{tabular}{|c||c|c|c|c|} | + | |
| - | {\small | + | |
| - | \begin{tabular}{|p{10mm}||p{13mm}|p{14mm}|p{13mm}|p{15mm}|} | + | |
| - | \hline | + | |
| - | $\models$ & $A=d_{j}$ & $A\neq d_{j}$ & $A \in V_{j}$ & $A \not\in V_{j}$ \\ | + | |
| - | \hline\hline | + | |
| - | $A=d_{i}$ & $d_{i} = d_{j}$ & $d_{i}\neq d_{j}$ & $d_{i}\in V_{j}$ & $d_{i}\not\in V_{j}$ \\ | + | |
| - | \hline | + | |
| - | $A \neq d_{i}$ & \_ & $d_{i} = d_{j}$ & $V_{j} = D\setminus \{d_{i}\}$ & $V_{j} = \{d_{i} \}$ \\ | + | |
| - | \hline | + | |
| - | $A \in V_{i}$ & $V_{i} = \{d_{j} \}$ & $d_{j}\not\in V_{i}$ & $V_{i}\subseteq V_{j}$ & $V_{i}\cap V_{j} = \emptyset$ \\ | + | |
| - | \hline | + | |
| - | $A \not\in V_{i}$ & $D\setminus V_{i} = \{d_{j}\}$ & $V_{i} = \{d_{j}\}$ & $V_{j}=D\setminus V_{i}$ & $V_{j}\subseteq V_{i}$ \\ | + | |
| - | \hline | + | |
| - | \end{tabular} | + | |
| - | } | + | |
| - | \end{center} | + | |
| - | \label{table1} | + | |
| - | \end{table} | + | |
| - | </latex> | + | |
| - | {{:hekate:salrules-flairs-table3.png|}} | + | * The first case concerns attributes which represent some process variables, which are to be incorporated in the inference process, but depend only of the environment and external systems. |
| + | * As such, the variables cannot be directly influenced by the XTT system. | ||
| + | * Examples: external temperature, the age of a client or the set of foreign languages known by a candidate. | ||
| + | * Values of such variables are obtained as a result of some measurement or observation process. | ||
| + | * They are assumed to be put into the inference system via a //blackboard// communication method; in fact they are written directly into the internal memory whenever their values are obtained or changed. | ||
| - | Table 3: Inference rules for atomic formulae for simple attributes | + | ===== State, State Representation and Inference ===== |
| - | The summary of the inference rules for atomic formulae with generalized attributes (where an atomic formula is the logical consequence of another atomic formula) is presented in Table 4. | + | * The second case concerns the values of attributes obtained at certain stage of reasoning as the result of the operations performed in RHS of XTT. |
| + | * The new values of the attributes can be: | ||
| + | * asserted to global memory (and hence stored and made available for any components of the system), or | ||
| + | * kept as values of internal process variables. | ||
| - | <latex> | + | ===== State, State Representation and Inference ===== |
| - | \begin{table*} | + | |
| - | \caption{Inference rules for atomic formulae for generalized attributes} | + | |
| - | \begin{center} | + | |
| - | \begin{tabular}{|c||c|c|c|c|c|c|} | + | |
| - | \hline | + | |
| - | $\models$ & $A=W$ & $A\neq W$ & $A\subseteq W$ & $A \supseteq W$ & $A \sim W$ & $A \not\sim W$ \\ | + | |
| - | \hline\hline | + | |
| - | $A=V$ & $V=W$ & $V\neq W$ & $V\subseteq W$ & $V\supseteq W$ & $V\cap W\neq \emptyset$ & $V\cap W = \emptyset$ \\ | + | |
| - | \hline | + | |
| - | $A\neq V$ & \_ & $V=W$ & $W = D$ & \_ & $W = D$ & \_ \\ | + | |
| - | \hline | + | |
| - | $A \subseteq V$ & \_ & $V \subset W$ & $V\subseteq W$ & \_ & $W = D$ & $V\cap W = \emptyset$ \\ | + | |
| - | \hline | + | |
| - | $A \supseteq V$ & \_ & $W \subset V$ & $W = D$ & $V\supseteq W$ & $V\cap W \neq \emptyset$ & \_ \\ | + | |
| - | \hline | + | |
| - | $A \sim V$ & \_ & $V\cap W=\emptyset$ & $W = D$ & \_ & $V=W$ & \_ \\ | + | |
| - | \hline | + | |
| - | $A\not\sim V$ & \_ & $V\cap W\neq\emptyset$ & $W = D$ & \_ & $W=D$ & $V=W$ \\ | + | |
| - | \hline | + | |
| - | \end{tabular} | + | |
| - | \end{center} | + | |
| - | \label{table2} | + | |
| - | \end{table*} | + | |
| - | </latex> | + | |
| - | {{:hekate:salrules-flairs-table4.png|}} | + | |
| - | Table 4: Inference rules for atomic formulae for generalized attributes | + | * The first solution is offered mostly for permanent changes; before asserting new values typically and appropriate retract operation is to be performed so as to keep a consistent state. In this way also the history (trajectory) of the system can be stored, provided that each value of an attribute is stored with a temporal index. |
| + | * The second solution is offered for value passing and calculations which do not require permanent storage. For example, if a calculated value is to be passed to some next XTT component and it is no longer used after, it is not necessary to store it in the global memory. | ||
| - | FIXME | + | ===== The State of the System ===== |
| - | (The rules must be checked; simple rules are for matching preconditions to the state formula. More complex rules can be for establishing truth-value propagation among atoms of preconditions within a table). | + | |
| - | 8-O 8-O 8-O | + | |
| - | In Tables 3 and 4 the conditions are //satisfactory// ones. | + | * The current state of the system is considered as a complete set of values of all the attributes in use at a certain instant of time. |
| - | However, it is important to note that in case of the first rows of the tables | + | * The concept of the state is similar to the one in dynamic systems and state-machines. |
| - | (the cases of A=d_i and A=V, respectively) all the conditions are also //necessary// ones. | + | * The representation of the state should satisfy the following requirements: |
| - | The interpretation of the tables is straightforward: if an atomic formula in the leftmost column in some row //i// is true, then the atomic formula in the topmost row in some column //j// is also true, provided that the relation indicated on intersection of row //i// and column //j// is true. | + | - the specification is //internally consistent//, |
| - | The rules of Table 3 and Table 4 can be used for checking if preconditions of a formula hold or verifying subsumption among rules. | + | - the specification is //externally consistent//, |
| + | - the specification is //complete//, | ||
| + | - the specification is //deterministic//, | ||
| + | - the specification is //concise//. | ||
| - | For further analysis, e.g. of intersection (overlapping) of rule preconditions one may be interested if two atoms cannot simultaneously be true and if so --- under what conditions. | + | ===== The State of the System ===== |
| - | For example formula | + | |
| - | <latex> | + | |
| - | $A\subseteq V\wedge A\subseteq W$ | + | |
| - | </latex> | + | |
| - | is inconsistent if | + | |
| - | <latex> | + | |
| - | $V\cap W=\emptyset$. | + | |
| - | </latex> | + | |
| - | Table 5 specifies the conditions for inconsistency. | + | |
| - | <latex> | + | * The first postulate says that the specification itself cannot be inconsistent at the syntactic level. For example, a simple attribute (one taking a single value) cannot take two different values at the same time. In general, assuming independence of the attributes and no use of explicit negation, each value of an attribute should be specified once. |
| - | \begin{table} | + | * The second postulate says, that only //true// knowledge (with respect to the external system) can be specified in state. In other words, facts that are syntactically correct but false cannot occur in the state formula. |
| - | \caption{Inconsistency conditions for pairs of atomic formulae} | + | |
| - | \begin{center} | + | |
| - | {\small | + | |
| - | \begin{tabular}{|c||c|c|c|c|} | + | |
| - | \hline | + | |
| - | $\not\models$ & $A=W$ & $A\subseteq W$ & $A \supseteq W$ & $A \sim W$ \\ | + | |
| - | \hline\hline | + | |
| - | $A=V$ & $W\neq V$ & $V \not\subseteq W$ & $W\not\subseteq V$ & $V\cap W \neq \emptyset$ \\ | + | |
| - | \hline | + | |
| - | $A \subseteq V$ & $W\not\subseteq V$ & $V\cap W = \emptyset$ & $W\not\subseteq V$ & $W\cap V =\emptyset$ \\ | + | |
| - | \hline | + | |
| - | $A \supseteq V$ & $V\not\subseteq W$ & $V\not\subseteq W$ & \_ & \_ \\ | + | |
| - | \hline | + | |
| - | $A \sim V$ & $V\cap W \neq \emptyset$ & $W\not\subseteq V$ & \_ & \_ \\ | + | |
| - | \hline | + | |
| - | \end{tabular} | + | |
| - | } | + | |
| - | \end{center} | + | |
| - | \label{table21} | + | |
| - | \end{table} | + | |
| - | </latex> | + | |
| - | {{:hekate:salrules-flairs-table5.png|}} | + | ===== The State of the System ===== |
| - | Table 5: Inconsistency conditions for pairs of atomic formulae | + | * The third postulate says, that //all// the knowledge true at a certain instant of time should be represented within the state. |
| + | * The four postulate says that there can be no disjunctive knowledge specification within the state. | ||
| + | * Finally, the fifth postulate says that no unnecessary, dependent knowledge should be kept in the state. In databases and most of the knowledge bases this has a practical dimension: only true facts are represented explicitly. | ||
| - | The interpretation of the Table 5 is straightforward: if the condition specified at the intersection of some row and column holds, then the atomic formulae labelling this row and column cannot simultaneously hold. Note however, that this is a satisfactory condition only. | + | ===== The State of the System ===== |
| - | The Table can be used for analysis of determinism of the system, i.e. whether satisfaction of precondition of a rule implies that the other rules in the same table cannot be fired. | + | * The current values of all the attributes are specified with the contents of the knowledge-base (including current sensor readings, measurements, inputs examination, etc.). |
| + | * From logical point of view it is a formula of the form:<latex> | ||
| + | $(A_{1}=S_{1})\wedge(A_{2}=S_{2})\wedge \ldots \wedge (A_{n}=S_{n})$ | ||
| + | </latex> where <latex>$S_{i} = d_{i}$</latex> (<latex>$d_{i}\in D_{i}$</latex>) for simple attributes and <latex>$S_{i}= V_{i}$</latex>, (<latex>$V_{i}\subseteq D_{i}$</latex>) for complex. | ||
| + | ===== The State of the System ===== | ||
| + | * In order to cover realistic cases some explicit notation for covering unspecified, unknown values is proposed; this is so to deal with the data containing the NULL values imported from a database. | ||
| + | * The first case refers to unspecified value of an attribute as a consequence of inappropriateness. A formula of the form <latex>$A=\bot$</latex> means that the attribute <latex>$A$</latex> takes an empty set of values (no value at all) at the current instant of time (or forever) for the object under consideration. | ||
| + | * For example, the attribute ''Maiden_Name'' or ''The_Year_of_Last_Pregnancy'' for a man is not applicable and hence it takes no value for all men. | ||
| - | ===== ALSV(FD) and State, State Representation and Inference ===== | + | ===== The State of the System ===== |
| + | * The second case refers to a situation that the attribute may be applied to an object, but it takes no value. This will be denoted as <latex>A=\emptyset</latex>. | ||
| + | * For example, the formula ''Phone_Number''=//\emptyset// means that the considered person has no phone number. | ||
| + | * The third case is for covering the ''NULL'' values present in relational databases. A formula of the form <latex>A=\mathtt{NULL}</latex> means that attribute <latex>$A$</latex> takes an unspecified value. | ||
| - | When processing information, the current values of attributes form the state of the inference process. The values of attributes can, in general, be modified in the following three ways: | ||
| - | - by an independent, external system, | ||
| - | - by the inference process, and | ||
| - | - as some clock-dependent functions. | ||
| - | The first case concerns attributes which represent some process variables, which are to be incorporated in the inference process, but depend only of the environment and external systems. As such, the variables cannot be directly influenced by the XTT system. Examples of such variables may be the external temperature, the age of a client or the set of foreign languages known by a candidate. Values of such variables are obtained as a result of some measurement or observation process. They are assumed to be put into the inference system via a //blackboard// communication method; in fact they are written directly into the internal memory whenever their values are obtained or changed. | ||
| - | The second case concerns the values of attributes obtained at certain stage of reasoning as the result of the operations performed in RHS of XTT. The new values of the attributes can be: | + | ===== State and rule firing ===== |
| - | * asserted to global memory (and hence stored and made available for any components of the system), or | + | |
| - | * kept as values of internal process variables. | + | |
| - | The first solution is offered mostly for permanent changes; before asserting new values typically and appropriate retract operation is to be performed so as to keep a consistent state. In this way also the history (trajectory) of the system can be stored, provided that each value of an attribute is stored with a temporal index. | + | |
| - | The second solution is offered for value passing and calculations which do not require permanent storage. For example, if a calculated value is to be passed to some next XTT component and it is no longer used after, it is not necessary to store it in the global memory. | + | |
| - | ==== The State of the System ==== | + | * In order to fire a rule all the precondition facts defining its LHS must be true within the current state. |
| + | * The verification procedure consists in matching these fact against the state specification. | ||
| + | * A separate procedure concerns simple (single-valued) attributes, and a separate one is applied in case of complex attributes. | ||
| - | The current state of the system is considered as a complete set of values of all the attributes in use at a certain instant of time. The concept of the state is similar to the one in dynamic systems and state-machines. The representation of the state should satisfy the following requirements: | + | ===== State and rule firing ===== |
| - | - the specification is //internally consistent//, | + | {{:hekate:salrules-flairs-table6.png|}} |
| - | - the specification is //externally consistent//, | + | |
| - | - the specification is //complete//, | + | |
| - | - the specification is //deterministic//, | + | |
| - | - the specification is //concise//. | + | |
| - | The first postulate says that the specification itself cannot be inconsistent at the syntactic level. For example, a simple attribute (one taking a single value) cannot take two different values at the same time. In general, assuming independence of the attributes and no use of explicit negation, each value of an attribute should be specified once. | + | |
| - | The second postulate says, that only //true// knowledge (with respect to the external system) can be specified in state. In other words, facts that are syntactically correct but false cannot occur in the state formula. | + | |
| - | The third postulate says, that //all// the knowledge true at a certain instant of time should be represented within the state. | + | |
| - | The four postulate says that there can be no disjunctive knowledge specification within the state. | + | |
| - | Finally, the fifth postulate says that no unnecessary, dependent knowledge should be kept in the state. In databases and most of the knowledge bases this has a practical dimension: only true facts are represented explicitly. | + | |
| - | The current values of all the attributes are specified with the contents of the knowledge-base (including current sensor readings, measurements, inputs examination, etc.). From logical point of view it is a formula of the form: | + | ===== State and rule firing ===== |
| - | <latex> | + | |
| - | $(A_{1}=S_{1})\wedge(A_{2}=S_{2})\wedge \ldots \wedge (A_{n}=S_{n})$ | + | |
| - | </latex> | + | |
| - | where $S_{i} = d_{i}$ ($d_{i}\in D_{i}$) for simple attributes and $S_{i}= V_{i}$, ($V_{i}\subseteq D_{i}$) for complex. | + | |
| - | + | ||
| - | In order to cover realistic cases some explicit notation for covering unspecified, unknown values is proposed; this is so to deal with the data containing the NULL values imported from a database. | + | |
| - | The first case refers to unspecified value of an attribute as a consequence of inappropriateness. A formula of the form | + | |
| - | $A=\bot$ | + | |
| - | means that the attribute $A$ takes an empty set of values (no value at all) at the current instant of time (or forever) for the object under consideration. For example, the attribute ''Maiden_Name'' or ''The_Year_of_Last_Pregnancy'' for a man is not applicable and hence it takes no value for all men. | + | |
| - | %% | + | |
| - | The second case refers to a situation that the attribute may be applied to an object, but it takes no value. This will be denoted as //A=\emptyset//. | + | |
| - | For example, the formula ''Phone_Number''=//\emptyset// means that the considered person has no phone number. | + | |
| - | %% | + | |
| - | The third case is for covering the ''NULL'' values present in relational databases. A formula of the form | + | |
| - | //A=\mathtt{NULL}// | + | |
| - | means that attribute $A$ takes an unspecified value. | + | |
| - | + | ||
| - | + | ||
| - | ==== State and rule firing ==== | + | |
| - | + | ||
| - | In order to fire a rule all the precondition facts defining its LHS must be true within the current state. The verification procedure consists in matching these fact against the state specification. A separate procedure concerns simple (single-valued) attributes, and a separate one is applied in case of complex attributes. | + | |
| - | The following tables provide a formal background for preconditions matching and rule-firing procedure: | + | |
| - | Tab.~6 | + | |
| - | defines when a precondition of the form //A\propto d// is satisfied with respect to given state, | + | |
| - | and | + | |
| - | Tab.~7 | + | |
| - | defines the principles for matching precondition defined with set-valued attributes against the state formula. | + | |
| - | + | ||
| - | + | ||
| - | {{:hekate:salrules-flairs-table6.png|}} | + | |
| - | Table 6: Inference principles for firing rules, case of single-valued attributes. | + | |
| {{:hekate:salrules-flairs-table7.png|}} | {{:hekate:salrules-flairs-table7.png|}} | ||
| - | |||
| - | Table 7: Inference principles for firing rules, case of general attributes. | ||
| ===== ALSV Rules ===== | ===== ALSV Rules ===== | ||
| + | * ALSV(FD) has been introduced with practical applications for rule languages in mind. | ||
| + | * In fact, the primary aim of the presented language is to extend the notational possibilities and expressive power of the XTT-based tabular rule-based systems. | ||
| + | * An important extension consist in allowing for explicit specification of one of the symbols eq, neq, in, notin, subset, supset, sim, notsim, with an argument in the table. | ||
| - | ALSV(FD) has been introduced with practical applications for rule languages in mind. | + | ===== Rule Format ===== |
| - | In fact, the primary aim of the presented language is to extend the notational possibilities and expressive power of the XTT-based tabular rule-based systems. | + | |
| - | An important extension consist in allowing for explicit specification of one of the symbols | + | |
| - | eq, | + | |
| - | neq, | + | |
| - | in, | + | |
| - | notin, | + | |
| - | subset, | + | |
| - | supset, | + | |
| - | sim, | + | |
| - | notsim, | + | |
| - | with an argument in the table. | + | |
| - | + | ||
| - | ==== Rule Format ==== | + | |
| Consider a set of //n// attributes | Consider a set of //n// attributes | ||
| Linia 423: | Linia 223: | ||
| and RHS is the right-hand side of the rule covering conclusion and perhaps the retract and assert definitions if necessary. | and RHS is the right-hand side of the rule covering conclusion and perhaps the retract and assert definitions if necessary. | ||
| - | ==== Rule Firing ==== | + | ===== Rule Firing ===== |
| The current values of all the attributes are specified with the contents of the knowledge-base (including current sensor readings, measurements, inputs examination, etc.). | The current values of all the attributes are specified with the contents of the knowledge-base (including current sensor readings, measurements, inputs examination, etc.). | ||
| Linia 441: | Linia 241: | ||
| for complex. | for complex. | ||
| - | ==== ANY and NULL ==== | + | ===== ANY and NULL ===== |
| - | In case the value of A_i is unspecified we shall write A_i = NULL (a database convention). | + | * In case the value of A_i is unspecified we shall write A_i = NULL (a database convention). |
| - | + | * Following a Prolog convention and logic, a //ANY// attribute value is possible in comparison (see''_'' in Prolog). | |
| - | Following a Prolog convention and logic, a //ANY// attribute value is possible in comparison (see''_'' in Prolog). | + | * The semantics can be: "any value", "not important", etc. |
| - | + | * The solution: | |
| - | The semantics can be: "any value", "not important", etc. | + | * in preconditions, we can only use //ANY//, i.e. an atom such as ''A=_'' can be specified, meaning "any value", "all possible values of the attribute", "we don't care" |
| - | + | * on the other hand, attribute A unspecified, in the state formula means ''A=NULL'', so we store NULL in state | |
| - | The solution: | + | * here we come to an inference rule: ''A=NULL'' ==> ''A=_''. Seems to be valid... This rules should be optionally disabled/enabled in the inference engine. |
| - | * in preconditions, we can only use //ANY//, i.e. an atom such as ''A=_'' can be specified, meaning "any value", "all possible values of the attribute", "we don't care" | + | |
| - | * on the other hand, attribute A unspecified, in the state formula means ''A=NULL'', so we store NULL in state | + | |
| - | * here we come to an inference rule: ''A=NULL'' ==> ''A=_''. Seems to be valid... This rules should be optionally disabled/enabled in the inference engine. | + | |
| - | + | ||
| - | FIXME It seems, we could have three types of NULL-like values: Not-applicable, Potentially-applicable but taking no value empty/no-defined, Applicabe-and-takin-value but unknown. | + | |
