Достаточные условия для корректных адаптивных гипермедиа систем

Введение

Адаптивные Гипермедиа Системы (или AHS) предоставляют автоматически персонализированный доступ к информационным гипермедиа ресурсам, чаще всего в форме Web сайтов. Большинство AHS обеспечивают поддержку адаптивной навигации и адаптивное содержание. Структура ссылок или представление указателей ссылок различна для каждого пользователя. Реальное содержание информационных страниц также отличается для различных пользователей. Обзор систем, методов и техник адаптивной гипермедиа можно найти в [B96]. Мы разработали эталонную модель архитектуры адаптивных гипермедиа приложений: Модель Адаптивного Гипермедиа Приложения (AHAM) [DHW99]. AHAM описывает AHS на абстрактном уровне, используя архитектуру, состоящую из трех частей:

Модель предметной области (DM), которая описывает, каким образом структурировано содержание приложения (используя концепты и отношения концептов).

Детализированная модель пользователя (UM), которая представляет предпочтения, знания, цели, историю навигации и другие релевантные аспекты пользователя.

Модель адаптации (AM), состоящую из правил адаптации. Правила определяют процесс генерации адаптивного представления и обновления модели пользователя.

Такая архитектура обеспечивает четкое разделение интересов при создании адаптивного гипермедиа приложения.

Исполнительная часть AHS, называемая механизмом (движком) адаптации (AE), является программным обеспечением, которое выполняет адаптацию (описанную правилами AM). Проблемы создания механизма адаптации общего назначения (AE) обсуждались в более ранней статье [WDD01]. Мы определили язык правил для AHS, AHAM-CA и предложили метод статического анализа для принятия решения о том, что для данных DM, UM и AM, механизм адаптации всегда конечен, и будет ли он конфлюэнтным¹ (это означает, что система будет генерировать предсказуемые результаты). В этой статье мы обсудим, как (достаточные, но не необходимые) условия, которые гарантируют конечность и конфлюэнтность, могут быть ослаблены (оставаясь достаточными).

Язык правил адаптации

Из-за отсутствия достаточного места мы не даем полное определение синтаксиса нашего (абстрактного) языка правил, а иллюстрируем его на примере. Подробности смотрите в [WDD01]. Правило C→A в AHAM состоит из условия (C) и действия (A). Поскольку свойства языка не зависят от используемого синтаксиса, для простоты мы применяем SQL-подобный синтаксис. Пример AHAM-CA правила:

C: select C1.knowledge

where C1.knowledge _ “known”

A: update C2.ready_to_read := true

where prerequisite(C1,C2) and

not exists ( select C3

where prerequisite(C3,C2) and

C3.knowledge < “known” )

Это общее правило, содержащее переменные концепты C₁, C₂ и С₃. Язык также разрешает (более или менее) специальные правила, которые используют концепты вместо переменных концептов. Правило в примере объявляет, что когда знание концепта C₁ изменяется на такое, что оно становится, по меньшей мере “known (знакомо)”, тогда все концепты C₂, для которых C₁ было последним предварительным условием, которое еще не было “known (знакомо)”, теперь становится “ready_to_read (готовы_к_чтению)”. В данном языке правил слишком легко написать правило, которое может привести к бесконечным циклам или непредсказуемым результатам. Пример такого правила:

C: select C1.attr

where C1.attr > 0

A: update C2.attr := C2.attr + 1

where rel(C1,C2)

Этот пример также демонстрирует, что это правило может генерировать бесконечный цикл, в зависимости от того имеет ли циклы отношение “rel”.

Достаточные условия для завершения и слияния в AHS

Язык правил AHAM-CA является очень мощным, но его выразительная мощность всегда отражается на поведении системы. Не существует полной гарантии того, что система будет вести себя корректно. Мы предложили метод статического анализа для проверки конечности и конфлюэнтности [WDD01] для основных случаев в AHS. Анализ или говорит нам, что набор правил конечен и конфлюэнтен, или что это не может быть определено. Этот раздел определяет некоторые ограничения, накладываемые на правила AHAM-CA, которые гарантируют конечность и конфлюэнтность, сохраняя в тоже время бóльшую свободу автору при описании процесса распространения, чем достаточные условия из [WDD01]. Сначала мы определяем некоторые термины и функции, которые будут использованы позднее.

Определение 1: R_i может активировать R_j, если выполнение действия A_i может перевести базу данных (вместе DM и UM) из состояния, в котором условие C_j ложно, в состояние, в котором C_j истинно. R_i может деактивировать R_j, если выполнение действия A_i может перевести базу данных из состояния, в котором C_j истинно, в состояние, в котором C_j ложно.

Определение 2: Набор правил завершает свое выполнение, если правила не могут активировать друг друга бесконечно.

Определение 3: Состояние выполнения правила S является парой (d, R_A), где d – состояние базы данных (DM и UM) и R_A Í AM – набор активных правил.

Определение 4: Последовательность выполнения правил – это последовательность σ, состоящая из серий состояний выполнения правил, связанных с (выполняемыми) правилами. Последовательность выполнения правил является законченной, если последним состоянием является (d, Æ), т.е. в последнем состоянии нет активных правил. Последовательность выполнения правил является валидной, если она представляет правильную последовательность выполнения: выполняются только активные правила и пары смежных состояний надлежащим образом представляют эффект выполнения соответствующего правила; более подробно смотрите [AHW95].

Определение 5: Набор правил является конфлюэнтным если для каждого начального состояния выполнения правила S (получаемого из исходного состояния базы данных множеством воздействий пользователя) каждая валидная и законченная последовательность выполнения правил, начинающаяся с состояния S, имеет одно и тоже конечное состояние.

Определение 6:

Пусть R: C→A. Функция num определяет количество отношений, используемых в операторе where для части A (действие) правила (А.where) (точное определение не приводится из-за ограниченного объема работы).

Пусть R: C→A.

S(R) = набор атрибутов, которые выбраны в C

U(R) = набор атрибутов, которым присвоены значения в A

E(R) = набор атрибутов, используемых в правой части выражений присваивания в A

st-rule (стартовое правило) – это правило, которое запускается внешними или внутренними сгенерированными событиями. Его действие только модернизирует концепты, выбранные по его условию. Оно описывает изменение значений внутри того же концепта. St-rule представляет набор стартовых правил.

pr-rule (правило распространения) – это правило, которое передает изменения значений различным концептам через отношения между этими концептами. Это может быть признаком плохого проектирования, если правила передают изменения с помощью иных средств, нежели отношения концептов в AHS. Pr-rule представляет набор правил распространения.

Pri(R) – это число для представления приоритета порядка выполнения правила R.

AM(rel)ÍPr-rule – набор правил, которые распространяют изменения “через” отношения типа rel.

Далее мы рассмотрим ограничения, которые гарантируют, что выполнение набора правил конечно и конфлюэнтно, но оставляют автору известную степень выразительной мощности при написании правил распространения. Несколько первых ограничений показывают, что непосредственный прямой подход приводит к очень жестким ограничениям, что ограничивает свободу автора.

Ограничение 1: "R_i,R_jÎAM: S(R_i)ÇU(R_j) = Æ.

Это ограничение означает, что правилам не позволено запускать друг друга.

Теорема 1: Набор правил AM, удовлетворяющий Ограничению 1, конечен.

Мы пропускаем (легкое) доказательство данной теоремы. Это ограничение является очень жестким, так как оно мешает процессу распространения. Тем не менее, оно, однако, не является достаточным, чтобы гарантировать конфлюэнтность.

Ограничение 2: "R_i,R_jÎAM:

R_i не зависит от R_j: (S(R_i)ÈU(R_i)ÈE(R_i)) Ç U(R_j) = Æ.

R_i является самонезависимым: (S(R_i)ÈE(R_i)) Ç U(R_i) = Æ.

Это ограничение означает, что правилам не позволено воздействовать (активировать или деактивировать) друг друга или самих себя и порядок выполнения правил не будет влиять на конечный результат.

Теорема 2: Набор правил AM, удовлетворяющий Ограничению 2, конечен и конфлюэнтен. Мы также пропускаем (легкое) доказательство данной теоремы.

В то время как Ограничение 1 гарантирует только конечность, Ограничение 2 является достаточным условием для конечности и конфлюэнтности. Вычислительная сложность алгоритма проверки этих ограничений O(N²xM²), где N количество правил, а M – количество атрибутов. Эти ограничения очень строги в том смысле, что невозможно описать никакой процесс распространения (правило, которое активирует другие правила). Мы определи Ограничения 3-7 (и 7’), чтобы дать авторам бóльшую выразительную свободу.

Ограничение 3: AM = St-ruleÈPr-rule, "R_iÎSt-rule, "R_jÎPr-rule: Pri(R_i)>Pri(R_j).

Правило является семантически корректным в AHS, если оно удовлетворяет данному ограничению. Это значит, что набор правил состоит из стартовых правил и правил распространения. Данное ограничение также описывает то, что в каждой фазе перехода стартовые правила выполняются перед распространением. Приоритеты помогают, но их не достаточно для гарантирования конечности и конфлюэнтности.

Ограничение 4: “Граф” для каждого типа отношений концептов (исключая гиперссылки) ацикличен.

Гиперссылки не используются для распространения изменений в модели пользователя, так что они могут быть циклическими. Остальные отношения используются для распространения изменений между различными концептами. Чаще всего это не является признаком хорошего проектирования, если тип отношений циклический, поскольку тогда распространение изменений может никогда не закончиться. (Например, циклы в отношениях указывающих на порядок прохождения материала не имеют смысла.) Но даже с ациклическими типами отношений, отношения различных типов могут продолжать взаимодействовать и служить причиной бесконечных циклов.

Ограничение 5: "rel₁, rel₂ÎDM-rel, rel₁ ¹ rel₂:

"R_iÎAM(rel₁), "R_jÎAM(rel₂): U(R_i)ÇS(R_j) = Æ.

Это ограничение означает, что правила, использующие различные типы отношений, не могут активировать друг друга.

Теорема 3: Набор правил AM конечен, если он удовлетворяет Ограничениям 3-5.

Доказательство (в общих чертах): набор правил AM состоит из конечного числа стартовых правил и правил распространения. Стартовые правила не будут запускать друг друга; они запускаются внешними или внутренними событиями. Стартовые правила могут запускать правила распространения, и правила распространения также могут запускать правила распространения. Процесс распространение правил, использующих один тип отношений, всегда конечен, поскольку граф отношений является ориентированным ациклическим графом (ОАГ). И правила, использующие различные типы отношений, не могут запускать друг друга, так что различные ОАГ не могут быть объединены для формирования цикла.

Ограничение 6: "relÎDM-rel: "R_i, R_jÎAM(rel), R_i ¹ R_j: U(R_i)ÇU(R_j) = Æ.

Это ограничение говорит, что каждая пара правил, содержащая одинаковые типы отношений, обновляет непересекающиеся наборы атрибутов. В случае простого распространения каждый атрибут устанавливается только однажды за переход¹.

Определение 7: "rel₁, rel₂ÎDM-rel:

Условие Независимость(rel₁, rel₂) удовлетворяется, если "R_iÎAM(rel₁), "R_jÎAM(rel₂), R_i ¹ R_j:

(S(R_i)ÈU(R_i)ÈE(R_i)) Ç U(R_j) = Æ and (S(R_j)ÈU(R_j)ÈE(R_j)) Ç U(R_i) = Æ.

Это определение говорит, что все типы отношений независимы; порядок выполнения правил, использующих различные типы отношений, не влияет на конечный результат.

Ограничение 7: "rel₁, rel₂ÎDM-rel, rel₁ ¹ rel₂, Независимость(rel₁, rel₂) удовлетворяется.

Ограничение 7’: "RÎAM, R:C®A: num(A.where) £ 1 and

"rel₁, rel₂ÎDM-rel: ("R_iÎAM(rel₁), "R_jÎAM(rel₂), rel₁ ¹ rel₂: Pri(R_i)>Pri(R_j)) or

("R_iÎAM(rel₁), "R_jÎAM(rel₂), rel₁ ¹ rel₂: Pri(R_i)<Pri(R_j))

Это ограничение означает, что каждое правило распространения имеет самое бóльшее одно отношение, и порядок распространения через все графы отношений предопределен. Ограничение 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 12^th ACM Conference on Hypertext and Hypermedia, Arhus, Denmark, 2001 (to appear).