Algorytm RetePlus

Pamięć robocza i porządek obrad

W trybie wykonywania RetePlus mechanizm reguł działa z pamięcią roboczą i agendą, dodając instancje reguł do wykonania, gdy spełnione są warunki.

Pamięć robocza

W trybie wykonywania RetePlus mechanizm reguł na serwerze Decision Server jest sparowany z pamięcią roboczą. Pamięć robocza zawiera wszystkie obiekty znajdujące się w powiązanym obiekcie Engine . Pamięć roboczą można zmodyfikować, dodając instrukcję w części działania reguły lub za pomocą aplikacyjnego interfejsu programistycznego (API). W ten sposób mechanizm reguł jest świadomy obiektów znajdujących się w pamięci roboczej i powiązanych z nimi obiektów. Mechanizm reguł może używać tylko obiektów, które są dostępne z pamięci roboczej.

Plan

agenda to miejsce, w którym Serwer decyzyjny przechowuje reguły, których wzorce są zgodne. Każda reguła wprowadzana do porządku obrad jest tworzona, a jej instancja staje się instancją reguły. Patrz sekcja Instancje reguł.

W porządku obrad są przechowywane instancje reguł, które kwalifikują się do rund. Jeśli porządek obrad jest pusty, wykonanie nie ma żadnego skutku. Instancje reguł umieszczone w porządku dziennym są następujące: zakwalifikowane. Często, w porządku dziennym, kwalifikuje się kilka zasad. W związku z tym mechanizm reguł musi mieć pewien sposób na podjęcie decyzji, która szczególna zasada w porządku dziennym powinna zostać uruchomiona.

W porządku dziennym instancje reguł są uporządkowane zgodnie z trzema kryteriami, które określają regułę, która powinna być uruchamiana jako pierwsza. Dodatkowe sterowanie wykonywaniem jest oferowane wraz z implementacją bardziej złożonych funkcji, patrz sekcja Powiadomienia o obiektach.

Refrakcja

Instancja reguły, która została uruchomiona, nie może zostać ponownie wstawiona do porządku dziennego, jeśli nie wystąpił żaden nowy fakt, to znaczy, jeśli żaden z obiektów zgodnych z regułą nie został zmodyfikowany, lub jeśli żaden nowy obiekt nie jest zgodny z regułą.

Zasada refrakcji wymusza, że dla danej krotki tworzona jest tylko jedna instancja reguły. Ponieważ jednostka danych dla cyklu mechanizmu jest pamięcią roboczą, mechanizm może łatwo zarejestrować wszystkie możliwe krotki i sprawdzić, czy istnieje tylko jedna instancja reguły dla każdej krotki.

Na przykład należy wziąć pod uwagę następujący zestaw reguł:

class Person {
  Person(int age, boolean sick);
  boolean sick;
  int age;
}

rule incrementAge {
when {
  p: Person(!sick; age < 50);
} then {
  p.age += 1;
  update p;
}

rule cure {
when {
  p: Person(sick);
} then {
  p.sick = false;
  update p;
}

Jeśli obiekt Person(18,true) zostanie wstawiony do pamięci roboczej, to w zasadzie refrakcji zostanie utworzony następujący ślad wykonania:

1. cure
2. incrementAge

Istnieje możliwość dodania właściwości powtarzalnej w regule incrementAge :

rule incrementAge {
 property com.ibm.rules.engine.repeatable=true;
when {
  p: Person(!sick; age < 50);
} then {
  p.age += 1;
}

Jeśli obiekt Person(18,true) zostanie wstawiony do pamięci roboczej, to właściwość powtarzalna tworzy następujące dane śledzenia wykonania:

1. cure
2. incrementAge
3. incrementAge
4. incrementAge
5. ...
6. incrementAge

   Dopóki warunek age < 50 nie ma wartości false.

Powtarzalne reguły

Aby złamać zasadę refrakcji, można użyć właściwości reguły boolowskiej com.ibm.rules.engine.repeatable. W silniku decyzyjnym należy użyć tej właściwości w celu oznaczenia zestawów reguł, które mają być powtarzalne.

• Jeśli reguła nie jest powtarzalna, zasada refrakcji uniemożliwia ponowne opublikowanie instancji reguły do porządku obrad.
• Jeśli reguła jest powtarzalna, może zostać wstawiona ponownie jako instancja reguły w porządku dziennym, jeśli modyfikacja wystąpi w odniesieniu do jej obiektów warunków.

Aktualność

Jeśli dwie instancje reguł mają ten sam priorytet, reguła, która jest zgodna z najnowszym obiektem (ostatnio wstawiony, zmodyfikowany lub ponownie śledzony obiekt) jest uruchamiana jako pierwsza.

Priorytet i aktualność są używane do rozstrzygania konfliktów, gdy kilka instancji reguł jest kandydatami do wykonania w tym samym czasie. Jeśli po użyciu wszystkich określonych metod rozwiązywania konfliktów kandydaci pozostają kandydaci, wówczas mechanizm używa wewnętrznych metarułów; zapewnia to, że zawsze następuje ta sama sekwencja wykonywania reguł, biorąc pod uwagę te same warunki.

Przykład reguły wykonania reguły

W poniższym przykładzie reguły technicznej przedstawiono kolejność uruchamiania reguł:

rule init {
   when {
      angel();
   }
   then {
      insert clown();
      insert dascyllus();
   }
};
rule last {
   priority = -100;
   when {
      dascyllus();
   }
   then {
      System.out.println("last");
   }
};
rule first {
   priority = 100;
   when {
      angel();
      clown();
      dascyllus();
   }
   then {
      System.out.println("first");
   }
};
rule second {
   priority = 0;
   when {
      angel();
      dascyllus();
      clown();
   }
   then {
      System.out.println("second");
   }
};
rule third {
   priority = 0;
   when {
      angel();
      clown();
      dascyllus();
   }
   then {
      System.out.println("third");
   }
};

Załóżmy, że obiekt angel został wstawiony z aplikacji przy użyciu interfejsu API i dlatego został wstawiony do pamięci roboczej i że uruchamiamy wszystkie reguły, które mogą być uruchamiane.

Poniżej znajduje się kolejność uruchamiania reguł:

1. Reguła init : Ponieważ obiekt angel został wstawiony z aplikacji, reguła init jest jedyną regułą, która może zostać uruchomiona. Wstawia on obiekty clown , a następnie obiekt dascyllus do pamięci roboczej. Najnowszym obiektem jest więc dascyllus.

2. Reguła first : ta reguła jest uruchamiana przed regułą second . Najbardziej aktualny obiekt zgodny z tymi dwoma regułami jest taki sam. Jednak pierwszy obiekt ma wyższy priorytet niż drugi, który określa ich kolejność wykonywania.

3. Reguła second : ta reguła jest uruchamiana przed regułą third . Drugi i trzeci reguły mają ten sam priorytet, ale obiekt dascyllus jest bardziej aktualny niż obiekt clown.

4. Reguła third : ta reguła jest uruchamiana przed regułą last . Mimo że obiekt dascyllus jest nowszy niż clown, reguła third ma wyższy priorytet niż reguła last .

5. last .

Instancje reguł

Instancja reguły jest dodawana do porządku dziennego, gdy obiekty w pamięci roboczej spełniają warunek tej reguły.

Zastanówmy się nad następującą zasadą techniczną:

rule rule1 {
   when {
      Fish(color == green; type == shark);
      Fish(type == trigger);
   }
   then {...}
};

Następujące instancje reguł zostaną umieszczone w porządku dziennym:

W tym przykładzie można zauważyć, że instancja reguły jest pojęciem dynamicznym: instancja reguły jest tworzona przez dowolną kombinację obiektów w pamięci roboczej, które są zgodne z wzorcami określonymi w regule. Z kolei reguła jest pojęciem statycznym.

Wzorce negatywne

Standardowe warunki reguły mogą być opisane jako egzystencjalne, w tym sensie, że można je dopasować za pomocą jednego lub kilku obiektów, które rzeczywiście istnieją. W trybie wykonywania RetePlus istnieje komplementarna koncepcja znana jako wzorce negatywne. Aby wyrazić nieistnienie określonego obiektu w pamięci roboczej, należy umieścić słowo kluczowe not przed warunkiem, w którym znajduje się obiekt, jak pokazano poniżej:

not Fish(type==eel);

Ten ujemny wzorzec powoduje pomyślne dopasowanie, ponieważ nie istnieje żaden obiekt pasujące do odpowiadającego mu wzorca dodatniego:

Fish(type==eel);

I odwrotnie, ten negatywny wzór:

not Fish(type==angel);

nie powoduje pomyślne dopasowanie z prostego powodu, dla którego istnieje obiekt zgodny z odpowiednim wzorcem:

Fish(type==angel);

Powiadomienia o obiektach

W trybie wykonywania RetePlus dostępne są instrukcje sterowania poszczególnymi operacjami:

• Wstawianie obiektu
• ponawianie obiektu
• Aktualizacja obiektu
• #concept_cfl_nsj_hkb__attribute_modification

Wstawienie obiektu

Instrukcja insert umożliwia utworzenie nowego obiektu i wstawienie go do pamięci roboczej. Po tym słowie kluczowym występuje nazwa klasy oraz wartości atrybutów obiektu, który ma zostać utworzony.

Poniżej przedstawiono przykład, który obejmuje utworzenie nowego obiektu Course , którego atrybuty department i number przyjmują wartości odpowiednio History i 324:

insert Course(History,324);

Istnieją dwie możliwości przetwarzania operacji insert :

• Obiekt znajduje się już w pamięci roboczej. W tym przypadku operacja wstawiania jest równoznaczna z aktualizacją.

• Obiekt nie znajduje się w pamięci roboczej. W tym przypadku obiekt jest wstawiany do pamięci roboczej, a demon wstawiania odpowiedniej klasy i jego nadklas, jeśli istnieje, jest wywoływany, a porządek obrad jest aktualizowany.

Ponowienie obiektu

Instrukcja retract umożliwia usunięcie z pamięci roboczej obiektu, który jest powiązany ze zmienną reguły.

W poniższym przykładzie operacja podstawowa retract usuwa obiekt powiązany ze zmienną ?c :

rule RemoveCourse {
   when {
      ?c: Course(department == History; number == 254);
   }
   then {
      retract ?c;
   }
};

Demon retract odpowiedniej klasy, jeśli istnieje, jest wywoływany, a porządek obrad jest odpowiednio aktualizowany. Ponowne śledzenie obiektu z pamięci roboczej może spowodować utratę przez obiekt logiczny jednego lub kilku jego uzasadnień.

Aktualizacja obiektu

Gdy obiekt jest modyfikowany przez program Java™, modyfikacje nie są widoczne w produkcie Decision Server. Oznacza to, że dane obsługiwane przez produkt Decision Server nie będą spójne z nową treścią zmodyfikowanego obiektu.

Aby uniknąć niespójności, instrukcja update powinna zostać wywołana dla takiego obiektu. Ta instrukcja umożliwia serwerowi decyzyjnym aktualizowanie struktur wewnętrznych zgodnie z nową treścią zmodyfikowanego obiektu.

W następującej regule pierwsze działanie modyfikuje atrybut liczbowy. Następnie operacja podstawowa update jest wywoływana w celu poinformowania serwera Decision Server o tym, że obiekt został zmodyfikowany.

rule NumberingUpdate {
   when {
      ?c: Course(department equals "history"; number > 300);
   }
   then {
      ?c.updateNumbering(); // This call modifies ?c 
      update ?c;
   }
};

Operacja sieciowa

Sieć RetePlus może zminimalizować liczbę reguł i warunków:

• Operacja sieci RetePlus
• Przykład sieci RetePlus
• Struktura sieci RetePlus
• Dodanie obiektu
• Usuwanie obiektu

Operacja sieci RetePlus

Siatka RetePlus indeksuje reguły tak, aby zminimalizować liczbę reguł i warunków, które muszą być wartościowane za każdym razem, gdy pamięć robocza zostanie zmieniona. Sieć minimalizuje liczbę ocen, dzieląc się testami między regułami i przyrostowo propagować zmiany. Po zakończeniu wszystkich testów sieć wyznacza regułę.

W większości przypadków wykonywanie reguły modyfikuje pamięć roboczą. Obiekty w pamięci roboczej przywoływane przez te reguły mogą być wstawiane, usuwane i modyfikowane. Sieć przetwarza zmiany, o których mowa w wyniku wykonania reguły, i tworzy nowy zestaw reguł do wykonania.

Gdy w pamięci roboczej wystąpi zmiana, może się zdarzyć, że dwie rzeczy mogą się zdarzyć, w zależności od rodzaju zmiany:

• Jeśli istnieje wstawianie obiektu do pamięci roboczej (dodatniej), reguła może zostać wykonana.

• Jeśli istnieje usunięcie obiektu z pamięci roboczej (ujemnej), reguła musi zostać usunięta z porządku obrad. Porządek obrad to miejsce, w którym utrzymany jest obecny zbiór zasad, które mają być wykonane.

Proces ten jest cyklicznie powtarzany do momentu, aż w porządku dziennym nie zostanie pozostawiona żadna kolejna instancja reguły.

Przykład sieci RetePlus

Aby zilustrować nasz opis sieci RetePlus, skorzystamy z trywialnej reguły filter , napisanej w języku reguł, która odnosi się do klas o nazwach A, Bi C:

rule filter {
   when {
      A (a1==3; ?x:a2);
      B (b1==2; ?y:b2; b3==?x);
      C (c1==?y);
   }
   then {
      System.out.println("filter");
   }
}

Atrybuty klasy są następujące:

• Klasa A ma dwa atrybuty o nazwach a1 i a2.

• Klasa B ma trzy atrybuty o nazwach b1, b2i b3.

• Klasa C ma jeden atrybut o nazwie c1.

Załóżmy, że pamięć robocza zawiera następujące obiekty:

A( a1=3 a2=10 )
B( b1=2 b2=4 b3=10 )
B( b1=2 b2=7 b3=10 )
C( c1=4 )

Struktura sieci RetePlus

Sieć RetePlus może być reprezentowana jako wykres złożony z trzech stref:

Drzewo dyskryminacji

Dyskryminacja drzewo to proces dopasowywania wzorca, który wykonuje testy. Testy te są reprezentowane przez diamentowe kształty w górnej części sieci. Testy dotyczą klas obiektów i wartości ich atrybutów. Dane wejściowe dla tego drzewa składają się z tokenów reprezentujących każdy z bieżących obiektów w pamięci roboczej.

Gdy wzorzec dotyczy tylko jednego obiektu i jego atrybutów, jest on powtarzany jako test dyskryminacji. Gdy jest to kombinacja, jest ona nazywana łączeniem; te pojawiają się w dolnej części wykresu.

Węzły alfa

Węzeł alfa jest tworzony na następnym poziomie sieci, dla każdego tokenu, który przekazuje testy drzewa dyskryminacji. Każdy węzeł składa się z jednego lub kilku leksemów, reprezentowanych przez okrągłe zakręcone prostokąty (na rysunku znajdują się trzy węzły alfa). Jeden węzeł alfa zawiera dwa leksemy klasy B. Pozostałe dwa węzły zawierają tylko jeden znacznik klasy-odpowiednio-tokeny klasy A i klasy C.

Testy i krotki

Trzecia strefa sieci jest zgodna z tokenami kilku klas obiektów. Wynikowe węzły są nazywane krotkami, które będą składać się z kilku tokenów. Test równości między atrybutami a2 i b3 powoduje powstanie węzła składanego z dwóch par leksemów, a test między atrybutami b2 i c1 następnie odfiltrowuje triplet leksemów. W sieci RetePlus często odwołujemy się do krotek tego typu jako węzłów join .

Dodawanie obiektów

Aby zademonstrować ten pomysł w sieci RetePlus, przypuśćmy, że dodatkowy obiekt zostanie wstawiony do pamięci roboczej. Dodany obiekt jest klasy C, a wartość jego atrybutu c1 to 7.

C( c1=7 )

Na tym etapie, gdy wszystkie testy węzłów są przeprowadzane, tylko trzeci test C (c1==?y); (class of object = C) jest spełniony. Testy węzłów podrzędnych są kontynuowane w miarę, jak token jest zstępujący przez sieć.

W tym miejscu nie ma węzła podrzędnego w drzewie dyskryminacji. Z tego powodu obiekt jest przechowywany bezpośrednio w węźle alfa.

Gdy token osiągnie drugi węzeł łączenia B (b1==2; ?y:b2; b3==?x), test jest przeprowadzany między każdym obiektem B par zapisanych obok pamięci węzła łączenia i obiektem C zawartym w znaczniku, który właśnie dotarł do węzła łączenia. Test jest spełniany dla obiektu B drugiej pary. W związku z tym możemy kontynuować i utworzyć triplet utworzony przez drugą parę i obiekt w tokenie.

Tworząc ten tryplet, w rzeczywistości zstąpimy po całej sieci, a nowa instancja reguły filter może zostać wykonana.

Usunięcie obiektu

Załóżmy, że teraz usuwamy obiekt, który właśnie dodaliśmy do pamięci roboczej.

Postęp leksem przez drzewo dyskryminacji jest taki sam, jak w przypadku dodawania obiektów, ale pojaw się ujemnego tokenu w węźle alfa powoduje usunięcie obiektu zawartego w tokenie.

Gdy token dociera do drugiego węzła łączenia, wszystkie trójki zawierające obiekt w tokenie są usuwane, a token kontynuuje jego postęp w sieci.

Podobnie jak w przypadku dodawania obiektów, węzeł reguły jest osiągalny. Instancja reguły filter , której obiekty spełniają warunki odpowiadające obiektom w tokenie, są usuwane z porządku obrad.