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

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

Введение

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

Модель предметної області (DM), що описує, як структуроване зміст докладання (використовуючи концепти й стосунку концептов).

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

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

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

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

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

Из-за відсутності достатнього місця ми даємо повне визначення синтаксису нашого (абстрактного) мови правил, а ілюструємо його з прикладу. Подробиці дивіться в [WDD01]. Правило C? A в AHAM полягає з умови (З) і дії (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»).

Это загальне правило, що містить перемінні концепти C1, C2 і С3. Мова також дозволяє (більш-менш) спеціальні правила, що використовують концепти замість змінних концептів. Правило в прикладі оголошує, що коли і знання концепту C1 змінюється на, що його стає, по меншою мері «known (знайоме)», всі концепти C2, для яких C1 було останнім попереднім умовою, яке не було «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: Ri може активувати Rj, якщо виконання дії Ai може перевести базі даних (разом DM і UM) з стану, у якому умова Cj брехливо, до стану, у якому Cj істинно. Ri може деактивировать Rj, якщо виконання дії Ai може перевести базі даних зі стану, у якому Cj істинно, до стану, у якому Cj ложно.

Определение 2: Набір правил завершує своє виконання, якщо правила що неспроможні активувати одне одного бесконечно.

Определение 3: Стан виконання правила P. S є парою (d, RA), де d — стан бази даних (DM і UM) і RA Í AM — набір активних правил.

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

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

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

Пусть R: C? A. Функція num визначає кількість відносин, які у операторі where частині A (дію) правила (А.where) (точне визначення не наводиться через обмеженого обсягу работы).

Пусть R: C? A.

S® = набір атрибутів, які обрані в C.

U® = набір атрибутів, яким надано значення A.

E® = набір атрибутів, які у правій частині висловів присвоювання в A.

st-rule (стартове правило) — цього правила, яке запускається зовнішніми чи внутрішніми сгенерированными подіями. Його дію лише модернізує концепти, обрані з його умові. Воно описує зміна значень всередині тієї самої концепту. St-rule представляє набір стартових правил.

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

Pri® — їх кількість до подання пріоритету порядку виконання правила R.

AM (rel)ÍPr-rule — набір правил, які поширюють зміни «через» відносини типу rel.

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

Ограничение 1: «Ri, RjÎAM: S (Ri)ÇU (Rj) = Æ.

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

Теорема 1: Набір правил AM, задовольняє Обмеження 1, конечен.

Мы пропускаємо (легке) доказ даної теореми. Це обмеження є у дуже жорсткий, бо вона заважає процесу поширення. Проте, воно, проте, перестав бути достатнім, щоб гарантувати конфлюэнтность.

Ограничение 2: «Ri, RjÎAM:

Ri залежить від Rj: (S (Ri)ÈU (Ri)ÈE (Ri)) Ç U (Rj) = Æ.

Ri є самонезависимым: (S (Ri)ÈE (Ri)) Ç U (Ri) = Æ.

Это обмеження означає, що правилам зась впливати (активувати чи деактивировать) одне одного чи себе і порядок виконання правил нічого очікувати проводити кінцевий результат.

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

В нас саме Обмеження 1 гарантує лише кінцівку, Обмеження 2 є достатньою передумовою кінцівки і конфлюэнтности. Обчислювальна складність алгоритму перевірки цих обмежень O (N2xM2), де N кількість правил, а M — кількість атрибутів. Ці обмеження дуже суворі тому, що організувати неможливо описати ніякої процес поширення (правило, яке активує інші правила). Ми визнач Обмеження 3−7 (і аналогічних сім'), щоб дати авторам бóльшую виразну свободу.

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

Правило є семантично коректним в AHS, якщо воно задовольняє даному обмеження. Це означає, що набір правил складається з стартових правив і правил поширення. Дане обмеження також описує те що кожної фазі переходу стартові правила виконуються перед поширенням. Пріоритети допомагають, та їх недостатньо для гарантування кінцівки і конфлюэнтности.

Ограничение 4: «Граф» кожному за типу стосунків концептів (виключаючи гіперпосилання) ацикличен.

Гиперссылки не йдуть на поширення змін — у моделі користувача, отже є підстави циклічними. Інші відносини йдуть на поширення змін між різними концептами. Найчастіше не є ознакою хорошого проектування, якщо тип відносин циклічний, бо тоді поширення змін може будь-коли закінчитися. (Наприклад, цикли у взаєминах вказують значно проходження матеріалу немає сенсу.) Але із ациклическими типами відносин, відносини різних типів можуть продовжувати взаємодіяти і служити причиною нескінченних циклов.

Ограничение 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).