Ограничение 5: "rel1, rel2ÎDM-rel, rel1¹ rel2:
"RiÎAM(rel1), "RjÎAM(rel2): U(Ri)ÇS(Rj) = Æ.
Это ограничение означает, что правила, использующие различные типы отношений, не могут активировать друг друга.
Теорема 3: Набор правил AM конечен, если он удовлетворяет Ограничениям 3-5.
Доказательство (в общих чертах): набор правил AM состоит из конечного числа стартовых правил и правил распространения. Стартовые правила не будут запускать друг друга; они запускаются внешними или внутренними событиями. Стартовые правила могут запускать правила распространения, и правила распространения также могут запускать правила распространения. Процесс распространение правил, использующих один тип отношений, всегда конечен, поскольку граф отношений является ориентированным ациклическим графом (ОАГ). И правила, использующие различные типы отношений, не могут запускать друг друга, так что различные ОАГ не могут быть объединены для формирования цикла.
Ограничение 6: "relÎDM-rel: "Ri, RjÎAM(rel), Ri¹Rj: U(Ri)ÇU(Rj) = Æ.
Это ограничение говорит, что каждая пара правил, содержащая одинаковые типы отношений, обновляет непересекающиеся наборы атрибутов. В случае простого распространения каждый атрибут устанавливается только однажды за переход[2].
Определение 7: "rel1, rel2ÎDM-rel:
Условие Независимость(rel1, rel2) удовлетворяется, если "RiÎAM(rel1), "RjÎAM(rel2), Ri¹Rj:
(S(Ri)ÈU(Ri)ÈE(Ri)) Ç U(Rj) = Æ and (S(Rj)ÈU(Rj)ÈE(Rj)) Ç U(Ri) = Æ.
Это определение говорит, что все типы отношений независимы; порядок выполнения правил, использующих различные типы отношений, не влияет на конечный результат.
Ограничение 7: "rel1, rel2ÎDM-rel, rel1¹rel2, Независимость(rel1, rel2) удовлетворяется.
Ограничение 7’: "RÎAM, R:C®A: num(A.where) £ 1 and
"rel1, rel2ÎDM-rel: ("RiÎAM(rel1), "RjÎAM(rel2), rel1¹ rel2: Pri(Ri)>Pri(Rj)) or
("RiÎAM(rel1), "RjÎAM(rel2), rel1¹ rel2: Pri(Ri)<Pri(Rj))
Это ограничение означает, что каждое правило распространения имеет самое бóльшее одно отношение, и порядок распространения через все графы отношений предопределен. Ограничение 7 требует вычисления многих наборов атрибутов и во многих случаях нам необходимо использовать различные типы отношений раздельно, так что более естественно просто определить для них некоторый порядок выполнения. В таком случае мы можем использовать Ограничение 7’ вместо Ограничения 7.
Теорема 4: Набор правил AM является конфлюэнтным, если он удовлетворяет ограничениям 3-7 (или 7’).
Доказательство (в общих чертах): Ограничения 3-5 гарантируют конечность AM, с Ограничением 6 AM станет конфлюэнтным при распространении через каждый отдельный граф отношений. Более того, с Ограничением 7 или 7’ AM становится конфлюэнтным при распространении через все графы отношений.
Ограничения 3-7 (или 7’) легки для понимания автора и могут быть использованы в большинстве распространенных AHS. Ограничение 3 легко проверить, в то время как Ограничения 4 и 7’ основываются только на DM и известны перед анализом набора правил. Так как количество типов отношений невелико, время, необходимое алгоритму для проверки Ограничений 3-7 (или 7’) приблизительно равно времени для проверки Ограничения 2.
Заключение
В этой статье мы предложили некоторые ограничения, накладываемые на правила адаптации, для достижения достаточных условий, гарантирующих конечность и конфлюэнтность в AHS. Проверка этих ограничений имеет намного меньшую вычислительную сложность, чем метод статического анализа, предложенный в [WDD01]. Наложенные Ограничения 3-7 (или 7’), тем не менее, позволяют автору писать распространяющиеся через среду правила адаптации для большинства существующих AHS.
Списоклитературы
[AHW95] Aiken, A., Widom, J., Hellerstein, J.M., “Static Analysis Techniques for Predicting the Behavior of Database Production Rules”. ACM Transactions on Database Systems, Vol. 20, nr. 1, pp. 3-41, 1995.
[B96] Brusilovsky, P., “Methods and Techniques of Adaptive Hypermedia”. User Modeling and User-Adapted Interaction, 6, pp. 87-129, 1996. (Reprinted in Adaptive Hypertext and Hypermedia, Kluwer Academic Publishers, pp. 1-43, 1998.)
[DHW99] De Bra, P., Houben, G.J., Wu, H., “AHAM: A Dexter-based Reference Model for Adaptive Hypermedia”. Proceedings of ACM Hypertext’99, Darmstadt, pp. 147-156, 1999.
[WDD01] Wu, H., De Kort, E., De Bra, P., “Design Issues for General Purpose Adaptive Hypermedia Systems”. Proceedings of the 12th ACM Conference on Hypertext and Hypermedia, Arhus, Denmark, 2001 (to appear).
[1] Если на входной канал автомата, при одинаковых начальных состояниях подаются одинаковые сигналы, и на его выходном канале также будут получены одинаковые сигналы, причем последовательность изменения его состояний может быть различной, то такой автомат является конфлюэнтным (см. далее Определение 5). Данное понятие близко к понятию “детерминированность”, но более “мягко” по сравнению с ним. – Прим. пер.
[2] Т.е. за время перехода системы из одного состояния в другое, вызванное выполнением (распространением) правил. – Прим. пер.