--- hekate:alsvfd [2008/11/19 18:44]
ligeza
+++ hekate:alsvfd [2019/06/27 15:49]
@@ Line 1: / Line 1: @@
-====== The XTT^2 ALSV(FD) Specification ======
-**Author**: Grzegorz J. Nalepa, based on the work with Antoni Ligêza
-**Version**:  Draft 2008Q3
-===== Introduction to Attributive Logics =====
-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.
-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 description of AL presented here is based on several papers, including
-  * [[hekate:bib:hekate_bibliography#ali2005thebook|(ali2005thebook)]]
-  * [[hekate:bib:hekate_bibliography#ali2008flairs|(ali2008flairs)]]
-  * [[hekate:bib:hekate_bibliography#gjn2008ruleapps|(gjn2008ruleapps)]]
-  * [[hekate:bib:hekate_bibliography#ali2008aaia|(ali2008aaia)]]
-===== 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.
-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>
-$A_{i}\colon O \to D_{i}$.
-</latex>
-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
-<latex>
-$A_{i}\colon O \to 2^{D_{i}}$
-</latex>
-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.
-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:
-  * 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).
-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 ====
-The legal atomic formulae of ALSV for //simple attributes// are presented in the Table 1.
-<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>
-Table 1: Simple attribute formulas 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>
-Table 2: Generalized attribute formulas syntax
-In case V_i is an empty set (the attribute takes in fact no value) we shall write A_i = ' '.
-See [[hekate:alsvdf#any and null]]
-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.//
-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.
-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.
-==== Semantics ====
-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
-A_i \in t
-is that it takes //one// or //some// 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.
-The semantics of $A = V$ is basically the same as the one of basic SAL.
-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:
-<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), and
-<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.
-==== 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:
-<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
-<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).
-These rules seem a bit trivial, but they must be implemented for enabling inference, e.g they are used in the rule precondition checking.
-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.
-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.
-<latex>
-\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>
-Table 3: Inference rules for atomic formulae for simple attributes
-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.
-<latex>
-\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>
-Table 4: Inference rules for atomic formulae for generalized attributes
-In Tables 3 and 4 the conditions are //satisfactory// ones.
-However, 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.
-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.
-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>
-\begin{table}
-\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>
-Table 5: Inconsistency conditions for pairs of atomic formulae
-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 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.
-===== 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.
-==== Rule Format ====
-Consider a set of //n// attributes
-A = A_1,A_2, ..., A_n
-Any rule is assumed to be of the form:
-<latex>
-$(A_{1}\propto_{1} V_{1})\wedge (A_{2}\propto_{2} V_{2})\wedge \ldots (A_{n}\propto_{n} V_{n}) \longrightarrow \mathit{RHS}$
-</latex>
-where //alpha_i// is one of the admissible relational symbols in ALSV(FD),
-and RHS is the right-hand side of the rule covering conclusion and perhaps the retract and assert definitions if necessary.
-==== 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.).
-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>
-//Eq: state-formula//
-where
-<latex>
-$S_{i} = d_{i}$ ($d_{i}\in D_{i}$)
-</latex>
-for simple attributes and
-<latex>
-$S_{i}= V_{i}$, ($V_{i}\subseteq D_{i}$)
-</latex>
-for complex.
-==== Any and NULL ====
-FIXME ALi
-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).
-The semantics can be: "any value", "not important", etc.

hekate/alsvfd.txt · Last modified: 2019/06/27 15:49 (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