Онтологии и правила Две установленные парадигмы в моделировании знаний Играют важную роль для Semantic Web. - презентация

1 Онтологии и правила Две установленные парадигмы в моделировании знаний Играют важную роль для Semantic Web

2 Преимущества интеграции Онтологии базируются на Дескриптивных логиках (и т.о. на логиках первого порядка). Web – открытая среда. Повторное использование / интероперабельность. Онтологии – модель, простая для понимания Правила основываются на логическом программировании. Для сохранения разрешимости, языки онтологий жертвуют выразительностью (например, не предоставляют конструкторов составных свойств). Тогда как, правила это делают хорошо. Существует эффективная поддержка суждений. Правила – хорошо известны на практике.

3 Правила Правила в основном основываются на подмножестве Логики 1-го порядка (FOL) + возможные расширения. Базовые формализмы правил(в Semantic Web): Semantic Web Rule Language (SWRL) Answer Set Programming (ASP) (Datalog ¬ )

4 Основные трудности интеграции Монотонные/ Немонотонные Свойства Open-world / Closed-world assumption отрицание-как-невыполнение/классическое отрицание Строгое отрицание / классическое отрицание эквивалентность разрешимость Логика 1 порядка / Логическое программирование

5 Не-базовый вывод Семантики LP определяются в терминах минимальной модели Herbrand, т.е. множествами не базовых фактов. Пример: likesFootball(x) liverpoolSupporter(x) liverpoolSupporter(x) liverpoolPlayer(x) liverpoolPlayer(gerrard). И в LP и в классической логике выводятся факты liverpoolSupporter(gerrard), likesFootball(gerrard). Только классическая логика позволяет дальнейший не фактические выводы, liverpoolPlayer(x) likesFootball(x)

6 Open-world / Closed-world assumption Логическое программирование – CWA If KB |= a, then KB = KB a Классическая логика – OWA Сохраняет мир открытым. KB: Man Person, Woman Person Bob Man, Mary Woman Запрос: найти все индивиды, которые не являются женщинами

7 Отрицание как невыполнение / Классическое отрицание Пример: KB LP :likesFootball(x) liverpoolSupporter(x) didNotCelebrateLVPEuroCup(x) not liverpoolSupporter(x) likesFootball(gerrard). KB CL : x liverpoolSupporter(x) likesFootball(x) x liverpoolSupporter(x) didNotCelebrateLVPEuroCup(x) likesFootball(gerrard). KB LP |= didNotCelebrateLVPEuroCup(gerrard)!

8 Строгое/ Классическое отрицание Строгое отрицание: способ имитации классического отрицания в LP. Пример: KB LP : footballPlayer(x) liverpoolPlayer(x) ~footballPlayer(me). ~liverpoolPlayer(me). KB CL : liverpoolPlayer(x) footballPlayer(x) ~footballPlayer(me). ~liverpoolPlayer(me). DL-KB повлечет me ~liverpoolPlayer (ошибка согласованности). В ASP: liverpoolPlayer(x) ~ liverpoolPlayer(x)

9 Эквивалентность LP ----> Unique Name Assumption (UNA) Классическая Логика ----> различные имена могут представлять один и тот же атом Пример: differentPlayers(x,y) player(x), player(y), x=y player(gerrard_of_liverpool). player(gerrard_of_england). В LP, можно сделать заключение: differentPlayers(gerrard_of_liverpool, gerrard_of_england)

10 Разрешимость Самое большое препятствие! Компромисс между выразительностью и разрешимостью. Проблема разрешимости под разными углами В LP: конечность домена В классической логике(и т.о. в ДЛ): комбинация конструкторов Проблема: Комбинация простых ДЛ и логики Horn неразрешима. (Levy & Rousset, 1998)

11 Правила + Онтологии Существует множество различных подходов: SWRL, DLP, dl-programs, DL-safe rules, Conceptual Logic Programs (CLP), AL-Log, DL+log. 2 основные стратегии: Тесная семантическая интеграция(Гомогенные подходы) Строгое семантическое разделение(Гибридные подходы)

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

13 Гомогенный подход Взаимодействие с жесткой семантической интеграцией. И онтологии и правила встраиваются в общий логический язык. Нет различий между предикатами правил и предикатами онтологии. Правила могут использоваться для определения классов и свойств онтологии. Пример: SWRL, DLP

14 Гибридный подход Онтологии обеспечивают общую разделенную концептуализацию домена, но могут существовать различные программы правил, специфичные для различных приложений домена. Онтология остается неизменной и правила надстраиваются сверху онтологии. Это делает возможной интеграцию существующего резонера правил с резонером существующей онтологией для суждений в гибридной языке, скорее чем разработку нового резонера с нуля. Правила не могут определять классы и свойства онтологии, но могут - некоторые специфичные для приложения отношения. Коммуникация через безопасный интерфейс. Пример: Answer Set Programming (ASP)

15 SWRL и правила DL-safe OWL добавляет существенную выразительную мощность Semantic Web, однако, сохранение разрешимости ключевых задач вывода в OWL DL и OWL Lite, OWL имеет ограничения выразительности (например, нет композиции). SWRL – попытка расширить OWL некоторыми формами языка правил. SWRL неограничен объединением OWL DL (т.е. приблизительно SHOIN(D)) и (бинарной) логики Хорна без функций. Результат - очень выразительный формализм, который, неразрешим. Разрешимость восстанавливается наложением условий безопасности на SWRL правила - DL-Safety (DL-Safe SWRL Rules): по сути, возможные значения (явных) переменных в SWRL правилах ограничены только именованными индивидами, что ограничивает действие таких правил на ABox

16 SWRL Основная идея - расширить OWL DL формой правил, при сохранении максимальной обратной совместимости с существующим синтаксисом и семантиками OWL. Для этого, SWRL добавляет новый тип аксиом к OWL DL, а именно правила клозов Хорна, расширяющие абстрактный синтаксис OWL и прямые модельно – теоретические семантики для OWL DL, чтобы обеспечить формальные семантики и синтаксис для OWL онтологий, включающих такие правила. SWRL правила имеют форму импликации между предшественником (body) и последователем (header). Неформальное значение правила может читаться как: всякий раз, когда выполняются условия в предшественнике, условия в последователе тоже должны выполняться.

17 SWRL Множество атомов в body обрабатывается как конъюнкция. Пустой body, обрабатывается как тривиальная истинна (т.е. удовлетворяется каждой интерпретацией), т.о., header тоже должен удовлетворяться каждой интерпретацией. Множество атомов в header обрабатываются как отдельные последовательности, т.е. они все должны удовлетворяться. Пустой header обрабатывается как тривиальная ложь (т. е. не удовлетворяется любой расширенной интерпретацией). Такие правила удовлетворяются предшественник не удовлетворяется ни одной расширенной интерпретацией. правила с множественными атомами в header могут быть просто преобразованы в множественные правила, каждое с атомным последователем.

18 SWRL Расширяет OWL аксиомами, чтобы включить Horn- подобные положения (clauses). Максимальная совместимость с OWL Надстройка над OWL (те же семантики) Общая формула: a 1 … a n b 1... b k Ограничения Отрицание, Дизъюнкция Неразрешимость Не очень хорошо понятен: для него не существует родных механизмов суждений (reasoners), не размечены четко отношения с другими формализмами, фактически нет опыта использования SWRL для моделирования онтологий.

19 Синтаксис Абстрактный Человеко-читаемый Конкретный

20 Абстрактный синтаксис абстрактный синтаксис для правил определяется посредством версии Расширенного BNF. В этой системе обозначений, терминальные символы заключаются в кавычки; не терминальные символы выделяются жирным и в кавычки не заключаются. Альтернативы либо разделяются вертикальной чертой ( | ). Компоненты, которые могут встречаться не более одного раза заключаются в квадратные скобки ([..]);компоненты, которые могут встречаться произвольное количество раз (включая 0) заключаются в фигурные скобки ({... }). Пробелы - игнорируются. Имена – это ссылки RDF URI. Значение каждого конструктора в абстрактном синтаксисе для правил неформально описывается, когда он вводится.

21 Правила в АС SWRL расширяет аксиомы аксиомами правил, путем добавления постановки: axiom ::= rule SWRL онтология может содержать смесь правил и других конструкторов OWL DL, включая аннотации онтологий, аксиомы о классах и свойств, и факты об OWL индивидах, также как и сами правила Аксиома правила состоит из body и header, каждое из которых состоит из (возможно пустого) множества атомов. Как и для аксиом классов и свойств, аксиома правила может иметь аннотации; может назначаться URI ссылке Атомы могут ссылаться на индивиды, литералы данных, переменные индивидов или переменные данных. Переменные обрабатываются как квантор универсальности, с их областью, ограниченной заданным правилом. Только переменные, которые встречаются в предшественнике правила, могут встречаться в последователе

22 Человеко-читаемый АС подробный и не является легко читаемым часто используется относительно неформальная человеко читаемая форма правило имеет форму: antecedent consequent, где оба: предшественник и последователь, являются конъюнкциями атомов, записанными a 1... a n Переменные указываются, используя префиксы со знаком вопроса (?x).

23 Конкретный синтаксис SWRL обеспечен как конкретным синтаксисом XML, так и RDF. Конкретный синтаксис XML - комбинация синтаксиса представления XML языка онтологий OWL с синтаксисом RuleML XML. Он имеет несколько преимуществ: произвольные OWL классы (например, дескрипции) могут использоваться как предикаты в правилах; могут свободно смешиваться аксиомы правил и онтологии; упрощена интероперабельность между OWL и RuleML, содействие развитию/адаптации инструментов и расширение SWRL дополнительными свойствами из RuleML. существующая таблица стилей XSLT может быть расширена, чтобы обеспечить отображение в RDF графы, которое расширяет синтаксис обмена OWL RDF/XML.

24 Определение SWRL SWRL содержит OWL DL как часть свойств (все аксиомы OWL DL являются аксиомами SWRL). Кроме того, БЗ SWRL может содержать набор правил, состоящих из условия (body) и следствия (header), которые сами являются наборами SWRL атомов. Atom 1... Atom n Atom n+1... Atom m Условие (body)Следствие (header)

25 SWRL атомы Унарные атомы: C(arg1), где C – произвольное выражение класса OWL DL D(dataArg1) где D – тип данных URI или диапазон перечисленных значений Бинарные атомы: P(arg1, arg2) где P – свойство объекта Q(arg1, dataArg1) где Q - свойство типа данных arg1 = arg1 равенство, илиsameAs arg2 arg2 неравенство, или differentFrom Аргументы arg1 | arg2 - либо индивиды, обозначающие URI, либо переменные, задающие диапазон индивидов dataArg1 - либо литералы данных, либо переменные, задающие диапазон значений данных

26 Трансляция в SWRL Ψ = ψ1... ψn ψn+1... ψm - SWRL правило, такое что Var(Ψ) = V1... Vk - все SWRL переменные в атомах ψ1... ψm. π – функция трансляции X и Y – мета-переменные, пробегают диапазон SWRL переменных (имена индивидов и переменные объектов - x, y, z) A - произвольный атомный концепт, C и D - произвольные выражения класса, a и b - произвольные константы, P - произвольная роль.

27 Трансляция в SWRL Атомы ТерминТрансляция π (x) или π (y) или π (V) y или x или V(соот.) π (A,X) A(X) π (P,X,Y) P(X,Y) Аксиомы АксиомаТрансляция π (Ψ) V 1... V k ( π (ψ 1 )... π (ψ n ) π (ψ n+1 )... π (ψ m )) где ψ имеет форму A(X) или P(X,Y)

28 Трансляция в SWRL SWRL правила могут полностью заместить аксиомы ролей SH АксиомаFOL o Trans(P) x, y, z(P(x, y) P(y, z) P(x, z)) o P(X, Y ) P(Y,Z) P(X, Z) X, Y,Z(P(X, Y ) P(Y,Z) P(X,Z)) o P Q x, y(P(x, y) Q(x, y) o P(X, Y ) Q(X, Y ) X, Y (P(X, Y ) Q(X, Y )

29 Ограничение безопасности Вводится специальный предикат ДЛ, O, который - истинный для всех именованных индивидов (т.е. существует факт O(a) для всех имен индивидов, a, встречающихся в онтологии) и не встречается в каком-либо выражении концепта онтологии (и, таким образом, не попадает в область квантора существования). Затем, для каждой переменной в правиле ДЛ- безопасности, к телу добавляется O-атом с этой переменной.

30 Ограничение безопасности Трансляция расширяется в FOL с.о.: Пусть Ω(K) = c 1... c n – множество имен индивидов, встречающихся в БЗ K. K = K {c 1 : O... c n : O}. Затем к элементам K применяется Π. Пусть Ψ dls = α 1... α n α n+1 - правило ДЛ- безопасности такое, что каждый α является атомом и V ar (Ψ dls ) = v 1... v k – это все SWRL переменные в атомах α 1... α n+1. Тогда: Аксиома трансляции π (Ψdls) v 1... v k ( π (α 1 )... π (α n ) O(v 1 )... O(v k ) π (α n+1 ))

31 Пример DL-safety версия SWRL слабее, чем SWRL Foot partOf.Leg (1) BurnOnFoot locatedIn.Foot (2) LegInjury locatedIn.Leg (3) : locatedIn (4) : partOf (5) leg1 : Leg (6) foot1 : Foot (7) burn2 : BurnOnFoot (8) locatedIn(X, Y) partOf(Y, Z) locatedIn(X, Z) (9) Если мы интерпретируем (8) как неограниченное SWRL правило, то можем вывести (10)-(13), а если DL -safe, то только (10) и (11): : locatedIn (10) burn1 : LegInjury (11) BurnOnFoot LegInjury (12) burn2 : LegInjury (13)

32 Встроенные модули Это атомы с фиксированной, предопределенной интерпретацией. SWRL утверждение включает, среди других, встроенные модули для сравнения значений, математических и строковых манипуляций. Основная проблема: Как интерпретировать встроенные модули, если их переменные находятся под-экземплярами, при оценивании (т.е., они должны интерпретироваться как произвольные ограничения или более процедурно, например, выбрасывание ошибки, когда ограничительным является неподходящий тип)

33 Прямые модельно- теоретические семантики Модельно-теоретические семантики для SWRL - простое расширение семантик для OWL DL Основная идея - мы определяем привязки (bindings) расширения OWL интерпретаций, которые отображают переменные в элементы домена. Правило удовлетворяется интерпретацией, если каждая привязка, удовлетворяющая body удовлетворяет также header. Семантические условия относительно аксиом и онтологий не меняются, т. o. интерпретация удовлетворяет онтологии, если она удовлетворяет каждой аксиоме (включая правила) и факту в онтологии.

34 Правила интерпретации Абстрактная интерпретация OWL - кортеж вида = R,EC,ER,L, S, LV, где R – множество ресурсов, LV R - множество значений литералов, EC – отображение из классов и типов данных в подмножества R и LV, соответственно, ER – отображение из свойств в бинарные отношения на R, L – отображение из типизированных литералов в элементы LV, S – отображение из имен индивидов в элементы EC(owl : Thing).

35 Правила интерпретации - абстрактная OWL интерпретация привязка B() - абстрактная OWL интерпретация, расширяющая т.о., что S отображает i-переменные в элементы EC(owl : Thing) и L отображает d-переменные в элементы LV. Условия интерпретации АтомУсловие интерпретации C(x) S(x) EC(C) D(z) S(z) EC(D) P(x, y) S(x), S(y) ER(P) Q(x, z) S(x),L(z) ER(Q) sameAs(x, y) S(x) = S(y) differentFrom(x, y) S(x) S(y) builtIn(B, z 1,..., z n ) S(z 1 ),..., S(z n ) Ext(B)

36 Правила интерпретации Атом удовлетворяется привязкой B() при условиях, заданных выше, где C – дескрипция OWL DL, D – ранг данных OWL DL, P - свойство individual-valued OWL DL, Q - OWL DL data-valued Property, B - встроенный предикат, x, y - переменные или OWL индивиды, z, z 1,..., z n - переменные или значения данных OWL, и Ext – отображение из встроенных предикатов в подмножество 1..n LV n. Данная интерпретация встроенных предикатов очень гибкая и разрешает, например, предикаты с переменной арностью и использование предикатов с неправильным количеством аргументов: если S(z 1 ),..., S(z n ) не является расширением встроенного предиката, то атом просто не удовлетворяется.

37 Правила интерпретации Привязка B() удовлетворяет body A, если A - пустое или B( ) удовлетворяет каждому атому в A. Привязка B() удовлетворяет header C, если C – пусто и B( ) удовлетворяет каждый атом в C. Правило удовлетворяется интерпретацией, если для каждой привязки B такой, что B() удовлетворяет body, B() также удовлетворяет header. Семантические условия относительно аксиом и онтологий не меняются. В частности, o интерпретация удовлетворяет онтологию, если она удовлетворяет каждой аксиоме (включая правила) и факту в онтологии; o онтология согласована, если она удовлетворяется по крайней мере одной интерпретацией; o онтология O2 влечется онтологией O1, если каждая интерпретация, которая удовлетворяет O1 также удовлетворяет O2.

38 Пример Свойство uncle – импликация свойств parent и brother Parent, brother, uncle – individualvaluedPropertyID, задана интерпретация = R,EC,ER,L, S, LV, привязка B() расширяет S для отображения переменных ?a, ?b, и ?c в элементы EC(owl : Thing); a, b и c, соответственно, используются для обозначения этих элементов Body правила удовлетворяется B(), если (a, b) ER(parent) и (b, c) ER(brother). Header правила удовлетворяется B(), если (a, c) ER(uncle). Т.о., правило удовлетворяется интерпретацией, если для каждой привязки B() такой, что (a, b) ER(parent) и (b, c) ER(brother), выполняется (a, c) ER(uncle), т.е.: a, b, c EC(owl : Thing). ((a, b) ER(parent) (b, c) ER(brother)) (a, c) ER(uncle)

39 Мощность правил В OWL, только отношение между свойствами, является subsumption между именами атомных свойств, например, hasFather - subPropertyOf hasParent. Правило может утверждать более сложные отношения между свойствами. повышенная выразительная мощность приводит к неразрешимости ключевых задач вывода, в частности, согласованности онтологии Расширенные языки требуют возможность представления бесконечный 2-мерный грид, чтобы согласованность стала неразрешимой. С добавлением правил, такое кодирование тривиально.

40 Мощность правил x-succ и y-succ – свойства Правило x-succ(?a, ?b) y-succ(?b, ?c) y-succ(?a, ?d) x-succ(?d, ?e) sameAs(?c, ?e), вместе с утверждением, что каждый узел грида связан точно с одним другим узлом посредством каждого x-succ и y-succ, позволяет представить такой грид. SWRL правила выходят за рамки базовых клозов Хорна в следующих моментах: конъюнктивные последовательности; дескрипции классов также как и имена классов как предикаты в атомах класса; и равенства и неравенства.

41 Мощность правил Однако большинство из них не добавляет мощности языка. Конъюнктивные последовательности можно исключить, используя стандартное преобразование Lloyd-Topor: Например, правило вида A C1 C2 можно преобразовать в семантически эквивалентную пару пару:A C1, A C2. Дескрипция d может быть исключена из правила просто добавлением OWL аксиомы, которая вводит новое имя класса и утверждает, что оно эквивалентно d, например, EquivalentClasses(D d) - d заменяется именем класса D.

42 Эквивалентность атомов - свойство sameAs можно заменить подстановкой определенное пользователем owl свойство – например, Eq. Оно может быть задано подходящим значением, используя правило вида Thing(?x) Eq(?x, ?x) и утверждая, что это функционал. Интерпретация Eq соответствует равенству элементов в EC(owl : Thing), т.е., x, y EC(owl : Thing).x, y ER(Eq) x = y, и поэтому Eq может использоваться вместо sameAs без изменения значения онтологии Неравенства. Можно ввести owl свойство Neq, чтобы охватить некоторые из значений свойства differentFrom путем добавления правила вида Eq(?x, ?y) Neq(?x, ?y) Nothing(?x) Интерпретация Neq не пересекается с интерпретацией Eq, т.е., x, y EC(owl : Thing).x, y ER(Neq) x y, и это приводит к правилу импликации Neq(?x, ?y) differentFrom(?x, ?y). Т.е. можно исключить differentFrom в header правила, путем подстановки Neq. Но Neq не полностью охватывает значение неравенства, т.к. это могут быть пары элементов в EC(owl : Thing), которые ни в расширении Eq ни Neq, т.е., differentFrom не означает Neq. Т.е. нельзя использовать Neq, чтобы исключить вхождения differentFrom в body правила: чтобы это сделать, потребуется чтобы Neq было равно отрицанию Eq.

43 Фрагменты правил OWL Программы Дескриптивных Логик (DLP) Horn – SHIQ Определение Пример Связь с логическим программированием (LP)

44 Определение DLP Семантический фрагмент OWL (т.е. мы на время абстрагируемся от конкретного синтаксиса) Каждое OWL положение, которое является семантически эквивалентным – в смысле логики первого порядка – (конечному) множеству функционально свободных клозов Хорна, составляет действительное DLP высказывание. Разрешены ограничения целостности - DLP IC. Разрешены ограничения целостности и эквивалентности - DLP ICE. DLP+ - (семантический) фрагмент, общий для OWL DL и (функционально свободного недизъюнктивного) Datalog. Аналогично, DLP+ IC, IC+, и т.п.

45 ABox C(a) (утверждение индивида) R(a, b) (утверждение свойства) a = b (ICE) (эквивалентность индивидов) Характеристики свойств: R Q (эквивалентность) R Q (подсвойство) R.C (C ) (домен) R.C (C ) (ранг) R Q (инверсия) R R (симметрия) 1R (ICE) (функциональность) 1R (ICE) (обратная функциональность)

46 TBox Для DLP разрешается, чтобы имело одну из форм C, {o 1,..., o n }, или, а Right может быть C или. Для DLP IC - C, {o 1,..., o n }, или, а Right - C, или. Для DLP ICE - C, {o 1,..., o n }, или, а Right - C,, или {o}. Для версий DLP+ мы дополнительно разрешаем, чтобы Right имел форму R ().{a}. Аксиома OWL будет в DLP, если результатом трансляции в синтаксис ДЛ будет конечное множество положений выше упомянутой формы.

47 Пример Для TBox, мы моделируем следующие положения: (1) Каждый мужчина или женщина является взрослым человеком (2) Взрослый (grown-up) - это человек, который является взрослым (adult) (3) Женщина, имеющая кого-либо в качестве ребенка, это мать (4) Сирота – это ребенок людей, которые умерли (5) Одинокий ребенок не имеет братьев и сестер (6) AIFB исследователи работают в Университете Karlsruhe

48 Пример ДЛ - ALCIODLP Man Woman Adult GrownUp Human Adult Woman childOf. Mother Orphan childOf.(Dead Human) LonelyChild siblingOf. AIFBResearcher employedBy.{UKARL} Man Adult Woman Adult GrownUp Human GrownUp Adult Woman childOf. Mother Orphan childOf.Dead Orphan childOf.Human LonelyChild siblingOf. AIFBResearcher employedBy.{UKARL}

49 Пример для RBox parentOf childOf parentOf и childOf инверсные роли. parentOf ancestorOf parentOf - подроль роли ancestorOf. fatherOf parentOf fatherOf - подроль роли parentOf. ancestorOf.Human Human – домен роли ancestorOf. 1fatherOf fatherOf инверсный функционал.

50 ABox {Ian, Benjamin, Raphael, Horrocks} Man {Yue, Ulrike} Woman Ian = Horrocks : employedBy... Yue : Woman Ulrike : Woman. {Yue, Ulrike} Woman Включения классов не могут быть в общем случае заменены эквивалентностями.

51 Связь с логическим программированием (LP) БP DLP может быть транслирована в логику Horn, а затем выражена посредством синтаксиса LP (Datalog). Зададим БЗ в форме Datalog. TBox Adult(y) Man(y) Adult(y) Woman(y) Human(y) GrownUp(y) Adult(y) GrownUp(y) Mother(y) childOf(x, y) Woman(y) Dead(y) Orphan(x) childOf(x, y) Human(y) Orphan(x) childOf(x, y) LonelyChild(x) siblingOf(x, y) (5) y = UKARL AIFBResearcher(x) employedBy(x, y)

52 Связь с логическим программированием (LP) RBox parentOf(x, y) childOf(y, x) childOf(x, y) childOf(y, x) ancestorOf(x, y) parentOf(x, y) parentOf(x, y) fatherOf(x, y) Human(y) ancestorOf(x, y) y = z fatherOf(y, x) fatherOf(z, x) Формальная связь между семантиками OWL и DLP Теорема 1. Пусть K – база знаний DLP и пусть K – трансляция K в синтаксис Datalog. Пусть C – именованный класс и – именованный индивид. Тогда K |= OWL C() под семантиками OWL, если K |= Datalog C() под семантиками Datalog.

53 Определение Horn - SHIQ Аксиома SHIQ C D – Horn-аксиома, если выражение концепта C D имеет форму C + 1 как определено контекстно-свободной грамматикой. БЗ SHIQ с экстенционально сокращенным ABox находится в Horn- SHIQ, если все аксиомы его TBox являются Horn. Horn-SHIQ добавляет в DLP свободное использование ограничений роли, как, например, может свободно использоваться экзистенциональное ограничение.

54 Грамматика для определения Horn - SHIQ А A, R, и S обозначают множества всех имен понятий, имен ролей, и имен простых ролей, соответственно.

55 Пример онтологии в Horn- SHIQ TBox/Rbox (1) Parent hasChild. (2) Person childOf.Person (3) ManyChildren 2hasChild. (4) NoSiblings Person childOf.(1 hasChild. ) (5) childOf hasChild1 Abox : hasChild Lancelot du Lac : noSiblings : childOf

56 Трансляция в логику Horn person(X) nosiblings(X). person(Xf3) person(X), S f3 (X,X f3 ). parent(X) haschild(X, Y ). parent(X) manychildren(X). haschild(Y,X) childof(X, Y ). haschild(X,X f1 ) manychildren(X), S f1 (X,X f1 ). haschild(X,X f2 ) parent(X), S f2 (X,X f2 ). haschild(X,X f0 ) manychildren(X), S f0 (X,X f0 ). childof(X,X f3 ) person(X), S f3 (X,X f3 ). childof(Y,X) haschild(X, Y ). Y1 Y2 nosiblings(X), childof(X,Z), haschild(Z, Y 1 ), haschild(Z, Y 2 ). inc manychildren(X), nosiblings(X 0 ), childof(X 0,X). inc X f1 X f0, manychildren(X), S f1 (X,X f1 ), S f0 (X,X f0 ). Правила, непосредственно созданные в этой трансляции Ограничения целостности. Предикат inc истинный, если нарушается ограничение целостности

57 Трансляция в логику Horn S f (X, f(X)) O(X). HU(X) O(X). HU(f(X)) O(X). (for f {f 0, f 1, f 2, f 3 }) X X HU(X). X Y Y X,HU(X),HU(Y ). X Z X Y, Y Z,HU(X),HU(Y ),HU(Z). C(Y ) C(X),X Y,HU(X),HU(Y ). (для C {person, parent, manychildren, nosiblings}) R(Y 1, Y 2 ) R(X 1,X 2 ),X 1 Y 1,X 2 Y 2,HU(X 1 ),HU(X 2 ),HU(Y 1 ),HU(X 2 ). (для R {childof, haschild}) O(Elaine). O(Sir Lancelot). O(Lancelot du Lac). вспомогательные предикаты, необходимые для корректности трансляции Предикат O - определяет индивиды (из Abox), для которых применяется программа. O позволяет определить S f. S f (X,Y) сохраняется тогда и только тогда, когда Y = f(X). Предикат HU определяет, какие выражения рассматриваются в программе, а именно, индивиды из O и их непосредственные преемники для каждого символа функции. Остальные правила дают необходимую теорию равенства, ограниченную выражениями в HU.

58 Связь с LP Horn-SHIQ может быть транслирована в синтаксис Datalog, т.е. может пониматься как фрагмент правила SHIQ. это преобразование не является трансляцией эквивалентности в том смысле, что исходная онтология и ее трансляция имеют одни и те же модели. Теорема 2. Пусть K – БЗ Horn-SHIQ и пусть D(K) – преобразование K в синтаксис Datalog, полученное в результате применения алгоритмов преобразования KAON2 (алгоритмы трансляции). Тогда выполняется следующее. 1. K не выполнима D(K) не выполнима. 2. K |= α D(K) влечет за собой α под семантиками Datalog, где α имеет форму A(a) или R(a, b), и A – атомный концепт. 3. K |= C(a) для не атомного концепта C для Q - новый атомный концепт, Q(a) вытекает из D(K {C Q}) под семантиками Datalog.

59 Идея гибридного подхода R - LP язык правил и S - язык онтологий, основанный на ДЛ. Полагаем, что они разделяют алфавит переменных и алфавит констант индивидов, но их алфавиты символов предикатов не пересекаются. оба языка поддерживаются reasoners, отвечающими на запросы в соответствующих языках запросов, QR и QS Примеры языков правил - Datalog с семантиками наименьшей Herbrand модели, и нормальный свободный от функций LP с семантиками ASP. Пример языка онтологий - OWL DL (SHOIN). Гибридное правило на R и S – это правило вида H B1... Bm Q1... Qn, где, m, n 0, H, B i - литералы, Q j - запросы в языке запросов S Гибридное правило, где m = n = 0, называется фактом.

60 Гибридная БЗ K = (S,R) – конечное множество S аксиом ДЛ в языке онтологии S и конечное множество гибридных правил R на R и S, включая атомы не ДЛ. Под компонентом ДЛ гибридной БЗ, подразумевается множество всех аксиом ДЛ, включая терминологические аксиомы и утверждения. Семантики гибридного языка порождаются из семантик их компонент. Гибридное правило r получается из LP правила r 0, посредством добавления запросов ДЛ в body. Интуитивно, последние – это дополнительные ограничения на использования правила r 0, которые должны удовлетворяться, чтобы сделать выводы из r 0. Они могут разделять переменные и константы с литералами из r 0. Так как семантика компоненты ДЛ не меняется, семантики гибридного языка получаются путем адаптации семантик компоненты правил. Чтобы R был языком логических программ, гибридные правила являются формулами FOL и их семантики могут формализоваться в терминах логических интерпретаций и моделей

61 Reasoners для гибридных языков, построенные путем интеграции reasoners компонент, должны быть прочными и полными относительно этих семантик. Типично резонеры используются для ответов на запросы Язык запросов гибридного языка правил синтаксически совпадает с языком запросов QR компоненты правил. Ответ на запрос - экземпляр запроса, который влечется из гибридной БЗ Однако, предикаты гибридной БЗ определяются гибридными правилами с ограничениями на body, которые должны удовлетворяться при получении ответа.

62 Гибридный подход Существует множество подходов для гибридных систем, которые включают как суждения классического OWL, так и традиционные подходы, основанные на правилах, подобные логическому программированию в различных вариантах. 2 основных подхода: основан на БЗ Hybrid MKNF - автоэпимистическое расширение OWL DL DL-безопасными правилами. В результате получается бесшовная интеграция суждений открытого и закрытого миров в рамках единой структуры, охватывающей суждения OWL DL и известные формы немонотонных суждений. базируется на интеграции суждений OWL DL с ASP, реализовано как система dlvhex. Интеграция менее строгая, чем для БЗ Hybrid MKNF, и в основном состоит из двух механизмов суждений, взаимодействующих при суждениях на БЗ двунаправленным способом.

63 Гибридный подход R - LP язык правил S - язык онтологий, основанный на ДЛ оба языка разделяют алфавит переменных и алфавит констант индивидов, но их алфавиты символов предикатов не пересекаются. оба языка поддерживаются резонерами, отвечающими на запросы в соответствующих языках запросов, QR и QS. Гибридное правило на R и S – это правило вида H B1... Bm Q1... Qn где, m, n 0, H, B i - литералы, Q j - запросы в языке запросов S. Гибридное правило, где m = n = 0, обычно называется фактом.

64 Гибридный подход Гибридная БЗ K = (S,R) – это конечное множество S аксиом ДЛ в языке онтологии S и конечное множество гибридных правил R на R и S, включая атомы не дескриптивной логики. Компонент ДЛ гибридной БЗ - множество всех аксиом ДЛ, включая терминологические аксиомы и утверждения. Семантики гибридного языка порождаются из семантик их компонент. Гибридное правило r получается из LP правила r0, посредством добавления запросов ДЛ в тело. Так как семантика компоненты ДЛ не меняется, семантики гибридного языка получаются путем адаптации семантик компоненты правил. Чтобы R был языком определенных LP, гибридные правила являются формулами FOL и их семантики могут формализоваться в терминах логических интерпретаций и моделей.

65 Гибридный подход Язык запросов гибридного языка правил синтаксически совпадает с языком запросов QR компоненты правил. Ответ на запрос является экземпляром запроса, который влечется из гибридной БЗ. предикаты гибридной БЗ определяются гибридными правилами с ограничениями на body, которые должны удовлетворяться при получении ответа

66 Cистемы, интегрирующие правила и ДЛ Язык AL-log [1] - гибридная интеграция Datalog и ДЛ Запросы ДЛ в body правил AL-log ограничены запросами членства экземпляр-класс; не разрешаются запросы членства свойства. ДЛ запросы – это вводимые ограничения на переменные. AL-запросы - конъюнкции атомных формул, построенных с не-ДЛ предикатами. Задача ответа на запрос в AL-log - разрешима. Алгоритм ответа на запросы вначале строит ДЛ ограничения для запроса, используя обратную цепочку, а затем использует резонер таблицу для проверки, что дизъюнкции полученных ограничений ДЛ влекутся компонентом ДЛ БЗ AL- log.

67 Cистемы, интегрирующие правила и ДЛ CARIN Семейство языков, направленных на обеспечение гибридной интеграции Datalog с различными ДЛ. Расширяет AL-log путем интеграции Datalog с более выразительной ДЛ и путем допущения более общих ДЛ запросов в теле гибридных правил. Цена этой всеобщности -неразрешимость задачи ответов на запросы. Разрешимые подмножества CARIN могут быть получены путем ограничения не рекурсивных правил или путем ограничения на способ появления переменных в правилах в ДЛ запросах к экземплярам свойств, т.е. если тело правила включает ДЛ запрос вида p(x, y), где x и y переменные, то по крайней мере один из них встречается в не-ДЛ атомах тела этого правила, предикаты которого могут встречаться только в фактах или в атомах тела, но не заголовках правила.

68 Cистемы, интегрирующие правила и ДЛ CARIN [2] Для обоих ограниченных подмножеств CARIN описывает полный алгоритм суждений, работающий в два шага: шаг ДЛ-суждения и шаг суждения правил. На шаге ДЛ суждений, ДЛ-компонент заданной БЗ используется для построения множества его дополнений, каждое из которых представляется конечным множеством ДЛ-атомов и определяет каноническую модель программы. Компонент правила БЗ CARIN, состоящий из всех гибридных правил и фактов, теперь может быть дополнен множеством ДЛ-утверждений, определенным дополнением ДЛ компоненты. Существует конечное число таких дополненных компонент правил. На шаге суждений правил делается стандартная прямая цепочка для каждой дополненной компоненты правил, используя добавленные ДЛ-утверждения в качестве новых фактов. Не-ДЛ атом влечется БЗ, если он влечется каждой из его дополненных компонент правил.

69 Cистемы, интегрирующие правила и ДЛ Интеграция ASP с ДЛ Существует ряд подходов к интеграции свободных от функций правил с AS семантиками и ДЛ: [3] ДЛ-запросы в качестве ограничений в теле правил. Правила разрешают дизъюнктивные заголовки. [4] представляет семантики с бесконечными открытыми доменами, которые способны иметь дело с интересующими фрагментами OWL DL, расширенными правилами [5] представляет гибридную интеграцию OWL DL (и OWL Lite) (или точнее DL SHOIN(D) (и SHIF(D)) с нормальными правилами под AS семантиками

70 Cистемы, интегрирующие правила и ДЛ нормальные правила могут включать два вида отрицаний (NAF и строгое) и дизъюнкцию assign(?p,?r) candidate(?p,?r) ~ ¬assign(?p,?r) ¬assign(?p,?s) candidate(?p,?s) assign(?p,?r) ?rs - статья p в кластере статей может быть назначена ровно одному из кандидатов обозревателей: - 1) статья не известно почему исключенная из назначений кандидату обозревателей, может быть назначена этому обозревателю - 2) исключает новые назначения для уже назначенных статей AS семантики тогда определяют различные назначения обозревателей, обеспечивая различные множества ответов

71 Cистемы, интегрирующие правила и ДЛ Новизна подхода - в обобщении формы ДЛ- запросов, разрешенных в телах гибридных правил, с помощью dl-атомов. Общая интуиция обобщенного запроса в том, что он может ссылаться на вариант ДЛ-компонента, полученного посредством модификации его утверждений путем добавления расширений не-ДЛ- предикатов. Т.е. ДЛ-запросы разрешают спецификацию входа из компонента правила, и т.о., поток информации из компонента правила в ДЛ-компоненту, и обратный поток, заданный любым ДЛ-запросом.

72 Cистемы, интегрирующие правила и ДЛ Подход позволяет построение правил сверху онтологий, но также (до некоторой степени) построение онтологий сверху правил. Это достигается с помощью операторов динамического обновления, посредством которых дополнительная часть (т.е., член класса или свойства) ДЛ- компонента может быть модифицирована в построение субъективных запросов.

73 Пример ДЛ-компонент имеет свойства keyword и inArea, ассоциированные с релевантными ключевыми словами и областями исследовательских статей. компонент правил (dlprogram) определяет предикат kw, связывающий статьи с ключевыми словами, и предикатом paperArea, связывающим статьи с областями Kw может определяться некоторыми фактами и правилами, устанавливающими, что если статья имеет ассоциированное ключевое слово, и есть некоторые связанные с этим словом другие ключевые слова, то они должны быть ассоциированы с этой статьей kw(?p,?w) kw(?p,?z) related(?z,?w) paperArea может определяться гибридным правилом, содержащим dl-атом, который запрашивает свойство inArea в ДЛ-компоненте, дополненной дополнительными утверждениями по свойству keyword (которое влияет на inArea), определяемым заданными гибридными правилами. Такой dl-атом используется следующим образом: paperArea(?p,?a) DL[keyword kw; inArea](?p,?a)

74 Не-ДЛ предикаты, определенные в таком dl-атоме, наз. входными предикатами. Помимо операции, добавляющей расширение не-ДЛ предиката, имеются операции для расширения дополнения, соответственно, ограничивающие расширение класса или свойства, облегчая использование не монотонных dl-атомов. Таким способом в ДЛ-компоненту до выполнения запросов могут поставляться дополнительные знания (накопленные в программе). Можно определить и использовать вовлеченные связи между классами и/или свойствами Полный резонер для гибридного языка может быть получен посредством комбинации существующего AS резонера для правил с существующим ДЛ резонером.

75 Инструменты Редакторы онтологий Protégé, Swoop, TopBraid Composer Редакторы правил Protégé (SWRL-Tab) Движки суждений онтологий (Reasoners) RacerPro, Bossam, Pellet, Fact++ Движки правил (RuleEngines) Bossam, Jess, Jena Framework (JRules) ASP solvers: DLV, Smodels, nomore++

76 Ограничения Поддержка вывода правил не интегрирована с OWL классификатором. Т.о., новые утверждения посредством правил могут нарушать существующие ограничения в онтологии. Новые выведенные из классификации знания могут, в свою очередь, производить знания, полезные для правил. Ontology Classification Rule Inference Inferred Knowledge Inferred Knowledge 12 43

77 Ограничения Существующее решение: Решать в ручную эти возможные конфликты. Идеальное решение: Иметь один модуль как для классификации онтологий, так и для вывода правил. Если мы хотим скомбинировать не монотонные свойства с классической логикой? Частичные решения: ASP Внешне(с использованием соответствующих движков правил)

78 Литература (1) Francesco M. Donini, Maurizio Lenzerini, Daniele Nardi, Werner Nutt, and Andrea Schaerf. An epistemic operator for description logics. Artificial Intelligence, 100(1– 2):225–274, (2) Alon Y. Levy and Marie-Christine Rousset. Combining Horn rules and description logics in CARIN. Artificial Intelligence, 104(1–2):165–209, (3) R. Rosati. Towards expressive KR systems integrating Datalog and Description Logics. In Proc Int. Workshop on Description Logics (DL- 1999), pages 160–164, (4) Stijn Heymans, Davy Van Nieuwenborgh, and Dirk Vermeir. Semantic web reasoning with conceptual logic programs. In Grigoris Antoniou and Harold Boley, editors, RuleML, volume 3323 of Lecture Notes in Computer Science, pages 113–127. Springer, (5) Thomas Eiter, Thomas Lukasiewicz, Roman Schindlauer, and Hans Tompits. Combining Answer Set Programming with Description Logics for the Semantic Web. In Didier Dubois, ChristopherWelty, and Mary-AnneWilliams, editors, Proceedings Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR 2004), June 2-5, Whistler, British Columbia, Canada, pages 141–151. Morgan Kaufmann, 2004.

79 Литература Handbook on Ontologies. S.STAAB, S.STUDER Editors