Разработка языка запросов в бинарной модели знаний и транслятора этого языка в язык SQL (бакалаврская работа) (Разработка языка запросов в бинарной модели знаний и транслятора этого языка в язык SQL (бакалаврская работа))

Посмотреть архив целиком

96



НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

УНИВЕРСИТЕТ

«МЭИ»


Институт Автоматики и вычислительной техники

Кафедра Прикладной математики

В Ы П У С К Н А Я Р А Б О Т А

бакалавра Прикладной математики и информатики


по направлению «Прикладная математика и информатика» (010500)


Тема: Разработка языка запросов в бинарной модели знаний и транслятора этого языка в язык SQL.

Студент А-13-08 Машеров Д.Е.

группа подпись фамилия, и., о.,

Научный

руководитель профессор к.ф.-м.н. Плесневич Г.С.

должность звание подпись фамилия, и., о.,

Консультант

должность звание подпись фамилия, и., о.,

«Работа допущена к защите»

Зав. кафедрой д.т.н. Еремеев А.П.

звание подпись фамилия, и., о.,


Дата_____________


Москва 2012 г.







АННОТАЦИЯ

Даются описание системы «Бинарная модель знаний», описание языков для построения онтологий, язык запросов, транслятор с языка запросов в язык SQL, инструкции по использованию программы, реализующей транслятор.

ВВЕДЕНИЕ

В работе рассматривается задача разработки подсистемы «Язык запросов» (ЯЗ) системы «Бинарная Модель Знаний» (БМЗ). Проект БМЗ был разработан Г.С. Плесневичем. БМЗ предназначена для спецификации онтологий.

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

Онтологии играют центральную роль в Семантическом Вебе, целью которого является создание инфраструктуры, позволяющей сделать информацию в Интернете доступной программным агентам и другим системам математического обеспечения.

К настоящему времени разработано много языков для построения онтологий. Некоторые из этих языков представлены в главе 1 настоящей работы. В главе 2 дано описание системы БМЗ. В главе 3 дано описание языка запроса и транслятор с языка запросов в язык SQL.





ГЛАВА 1
ОБЩИЕ СВЕДЕНИЯ ОБ ОНТОЛОГИЯХ И ЯЗЫКАХ ДЛЯ СПЕЦИФИКАЦИИ ОНТОЛОГИЙ


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

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

Более поздней модификацией определения Грубера является такое определение: Онтология - это формальная спецификация согласованной концептуализации. Под согласованной концептуализацией подразумевается, что данная концептуализация не есть частное мнение, а является общей для некоторой группы людей.

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

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

1.1. Содержание онтологии

Основными компонентами онтологии могут являться:

  • классы (или понятия),

  • отношения (или свойства, атрибуты),

  • функции,

  • аксиомы,

  • экземпляры (или индивиды).

Классы или понятия используются в широком смысле. Понятием может быть любая сущность, о которой может быть дана какая-либо информация. Классы - это абстрактные группы, коллекции или наборы объектов. Они могут включать в себя экземпляры, другие классы, либо же сочетания и того, и другого. Классы в онтологиях обычно организованы в таксономию - иерархическую классификацию понятий по отношению включения. Например, классы Мужчина и Женщина являются подклассами класса Человек, который в свою очередь включен в класс Млекопитающие.

Отношения представляют тип взаимодействия между понятиями предметной области. Формально n -арные отношения определяются как подмножество произведения n множеств:  C1 x C2 x … x Cn, где Сj – классы. В том случае, когда n =2, отношение R называется бинарным. Пример бинарного отношения - отношение ISA («есть некоторое», отношение включения одного класса в другой).

Отношения могут быть организованы в таксономию по включению; например, отношения Быть_отцом_ и Быть_матерью_на множестве людей содержатся в отношении Быть_родителем, которое в свою очередь содержится в отношении Быть_предком.

Функции - это специальный случай отношений, в которых n -й элемент отношения однозначно определяется n-1 предшествующими элементами.

Аксиомы используются, чтобы записать высказывания, которые всегда истинны. Они могут быть включены в онтологию для разных целей, например, для определения ограничений на значения атрибутов, аргументы отношений, для проверки корректности информации, описанной в онтологии, или для вывода новой информации.

1.2 Цели создания онтологий

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

Например, в области медицины созданы большие стандартные, структурированные словари, такие как SNOMED и семантическая сеть Системы Унифицированного Медицинского Языка (Unified Medical Language System, UMLS). Также появляются обширные общецелевые онтологии. Например, Программа ООН по развитию (the United Nations Development Program) и компания Dun & Bradstreet объединили усилия для разработки онтологии UNSPSC, которая предоставляет терминологию товаров и услуг (unspsc.org).

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

Почему возникает потребность в разработке онтологии? Вот некоторые причины, которые ниже будут рассмотрены подробнее:

  • для совместного использования людьми или программными агентами общего понимания структуры информации;

  • для возможности повторного использования знаний в предметной области;

  • для того чтобы сделать допущения в предметной области явными;

  • для отделения знаний в предметной области от оперативных знаний;

  • для анализа знаний в предметной области.

Совместное использование людьми или программными агентами общего понимания структуры информации является одной из наиболее общих целей разработки онтологий. К примеру, пусть несколько различных веб-сайтов содержат информацию по медицине или предоставляют информацию о платных медицинских услугах, оплачиваемых через Интернет. Если эти веб-сайты совместно используют и публикуют одну и ту же базовую онтологию терминов, которыми они все пользуются, то компьютерные агенты могут извлекать информацию из этих различных сайтов и накапливать ее. Агенты могут использовать накопленную информацию для ответов на запросы пользователей или как входные данные для других приложений.

Обеспечение возможности использования знаний предметной области стало одной из движущих сил недавнего всплеска в изучении онтологий. Например, для моделей многих различных предметных областей необходимо сформулировать понятие времени. Это представление включает понятие временных интервалов, моментов времени, относительных мер времени и т.д. Если одна группа ученых детально разработает такую онтологию, то другие могут просто повторно использовать ее в своих предметных областях. Кроме того, если нам нужно создать большую онтологию, мы можем интегрировать несколько существующих онтологий, описывающих части большой предметной области. Мы также можем повторно использовать основную онтологию, такую как UNSPSC, и расширить ее для описания интересующей нас предметной области.

Создание явных допущений в предметной области, лежащих в основе реализации, дает возможность легко изменить эти допущения при изменении наших знаний о предметной области. Жесткое кодирование предположений о мире на языке программирования приводит к тому, что эти предположения не только сложно найти и понять, но и также сложно изменить, особенно непрограммисту. Кроме того, явные спецификации знаний в предметной области полезны для новых пользователей, которые должны узнать значения терминов предметной области.

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

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

Часто онтология предметной области сама по себе не является целью. Разработка онтологии сродни определению набора данных и их структуры для использования другими программами. Методы решения задач, доменно-независимые приложения и программные агенты используют в качестве данных онтологии и базы знаний, построенные на основе этих онтологий.

1.3. Области применения онтологий

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

электронная коммерция;

биоинформатика;

юридические информационные системы;

электронное обучение;

технология агентов;

построение баз данных;

программная инженерия;

обработка естественного языка;

информационный поиск;

Семантический Веб;

Веб-сервисы .



1.4. Формальная концептуализация и формальные онтологии


В книге [Genesereth et al., 1987], определяя понятие концептуализации, авторы пишут: «Блок формально представленного знания основан на концептуализации: объекты, понятия и другие сущности, которые существуют, как предполагается, в некоторой области интереса, а также отношения, которые существуют между ними. Концептуализация – абстрактный, упрощенный взгляд на мир, который мы хотим представить с некоторой целью. Каждая база знаний, система, основанная на знаниях, или агент на уровне знаний фиксирует, явно или неявно, некоторую концептуализацию».

Несмотря на сложность ментальной природы понятия «концептуализация», Дженесерет и Нильссон выбирают для его объяснения очень простое математическое представление – экстенсиональную реляционную структуру.

Экстенисинальная реляционная структура (концептуализация по Дженесерету и Нильссону) – это пара (U,R), где

Uмножество, называемое универсумом;

R – множество отношений, заданных на U.

Заметим, что по этому определению элементами множества R являются обычными математическими отношениями, т.е. некоторыми множествами кортежей, составленными из элементов D. Таким образом, элемент Rэто экстенсиональное отношение, отражающее конкретное состояние мира.

Пример 1.1. Рассмотрим предметную область «Компания», связанную с хранением сведений о работниках некоторой компании. Предположим, что в компании работает 300 человек, каждый из которых идентифицируется номером ИНН (индивидуальный номер налогоплательщика). Пусть универсум U содержит всех этих работников. Мы интересуемся отношениями между ними. Таким образом, R содержит некоторые унарные отношения (т.е. подмножества) такие, как Работник, Менеджер и Исследователь, а также бинарные отношения подчинен и сотрудничает_с. Соответствующая экстенсиональная реляционная структура (U,R) такова:

U = ИНН всех работников компании;

R = {Работник, Менеджер, Исследователь, подчинен, сотрудничает_с}.

Экстенсионалы отношений отражают конкретный мир. Здесь мы предполпгаем, что множество Работник совпадает с универсумом U, а множества Работник, Менеджер, Исследователь являются собственными подмножествами универсума. Бинарные отношения подчинен, сотрудничает_с являются множествами пар, которые указывают иерархию подчинения и совместную работу работников. На Рис.1.1 некоторые из этих пар изображены в виде ориентированного графа. Здесь исследователь 110104675801 подчинен менеджеру 11010382002 и сотрудничает с другим исследователем 110104444303, который также подченен менеджеру 11010382002.


Менеджер(110103482002)

подчинен


Исследователь(110104675801) подчинен

Работает_вместе_с

Исследователь(110104444303)

Работник(110105000027)


Рис.1.1

Работник = U;

Менеджер = {…, 110103482002,…};

Исследователь = {…, 110104444303,…, 110104675601,…};

подчинен = {…, (110104675801,1103482002),…,

(110104444303,110103482002),…};

сотрудничает_с = {…, (110104675601,110104444303),…};

Несмотря на простоту понятия «экстенсиональная концептуализация», это понятие на самом деле плохо соответствует нашим нуждам и отвечает нашей интуиции, главным образом, потому, что оно слишком зависит от конкретного состояния предметной области. Концептуализация должна зависеть только от понятий, а не от состояний (примеров понятий). Следует ли понятию «подчинен» изменяться тогда, когда иерархическая стуруктура компании меняется? В работе [Guarino et al.,1995] обсуждается, следует ли изменять концептуализации предметной области при изменении сосотяний это предментной области. Если в соответствии с взглядами Дженесерета и Нильссона считать, что это так, то каждый новый конкретный граф отношения «подчинен» такой, как в примере 1.1., давал бы новую концептуализацию.

Пример 1.2. Рассмотрим следующую модификацию примера 1.1.:

R* = { Работник, Менеджер, Исследователь, подчинен*, сотрудничает_с },

где подчинен*= подчинен U {(110103482001,110105000005)}.

Поскольку (U,R) ≠ (U,R*), то в соответствии с Дженесеретом и Нильссоном мы имеем две различные экстенсиональные концептуализации. Проблема в том, что принадлежащие R экстенсиональные отношения отражают конкретные состоянии предметеной области. Однако, мы должны сосредоточиться на смысле (значении) понятий, которые не зависимы от кокретного состояния. Например, смысл отношения сотрудничает_с лежит в конкретном способе как два работника действуют в компании.

В примере 1.1 предметная область состоит из элементов универсума U и имен Работник, Менеджер, Исследователь, подчинен и сотрудничает_с. Приведенную в этом примере экстенсиональную концептуализацию можно представить себе как назначение именам Работник, Менеджер и Исследователь конкретных подмножеств множества U, а именам подчинен , сотрудничает_с назначение конкретных отношений, т.е. подмножеств множества U x U.

С каждой парой (Менеджер, х), где хU, свяжем булеву переменную ξ«Менеджер,х» , которая равна 1 в том и только том случае, если х является примером понятия Менеджер (т.е. х есть ИНН некоторого менеджера). Точно так же, введем булевы переменные ξРаботник,х и ξИсследователь,х . Таким образом, в примерах 1.1 и 1.2 имеем, что ξРаботник,х = 1 для всех хU (поскольку универсум U состоит из ИНН всех работников), а ξ«Менеджер,110103482002» = 1 и ξ«Менеджер,110104444303» = 0 (так как работник с ИНН 110103482002 является менеджером, а работник с ИНН 110104444303 менеджером не является).

С каждой тройкой (подчинен,х,у), где х,уU, свяжем булеву переменную ξ«подчинен,х,у», которая равна 1 в том и только том случае, если работник с ИНН х подчинен работнику с ИНН у. Точно так же, введем булеву переменную ξ«сотрудничает_с,х,у» .

Итак, с предметной облстью из примеров 1.1 и 1.2 связано следующее множество булевых переменных:

{ξ«Работник,х», ξ«Менеджер,х», ξ«Исследователь,х»,

ξ«подчинен,х,у», ξ «сотрудничает_с» | х, уU}.

Состоянием этой предметной области назовем присваивание этим переменным конкретных значений 0 или 1.

Рассмотрим общий случай задачи моделирования некоторой системы (или приложения) S. Пусть PS – предметная область для этой задачи. Пусть Var = Var(PS) – множество всех переменных, связанных с предметной областью PS. (Заметим, что в основном Var состоит из булевых переменных; но в Var могут входить и не булевы пременные.) Состоянием σ предметной области PS назовем присваивание булевых значений переменным из Var. Другими словами, состояние σ можно отождествить с функцией, заданной на множестве Var и принимающая значения в {0,1}, т.е. σ: Var → {0,1}. Однако, вообще говоря, не любую функцию σ: Var → {0,1} следует считать допустимым состоянием. Обозначим А(PS) множество всех допустимых состояний предметной области PS. Это множество выражает смысл понятий, входящих в эту предметную область.

Пусть rимя какого-либо отношение предметной области PS. Предположим, что r имеет арность (местность) n. Тогда для заданных (х1,х2,…,хn) Un имеем булеву переменную ξ«r1,х2,…,хn». Каждое состояние σ предметной области PS задает n-местное отношение rσ = {(х1,х2,…,хn) | σ(ξ«r1,х2,…,хn») = 1}. Определим семейство n-местных отношений r = {rσ | σА(PS)}, состоящее из всех отношений rσ , когда σ пробегает все допустимые состояния предметной области PS. Семейство rотношений rσ называется интенсиональным отношением.

Замечание. Сказанное является общим способом выражения интенсиональных свойств, восходящим к Рудольфу Карнапу, [Карнап, 1959]. Данное нами определение интенсионального отношения является модификацией определения, данного в [Guarino et al., 2004]. Гуарино называет интенсиональные отношения также концептуальными.

Интуитивное понимание смысла отношения сотрудничает_с связано с некоторым правилом, определяющим кооперацию работников. Предположим, в нашем случае, два работника сотрудничают друг с другом, если: (1) оба они заявляют, что имеют одну и ту же цель; (2) оба делают что-то для достижения этой цели. Тогда смысл отношения сотрудничает_с можно определить как функцию, которая для каждого допустимого состояния дает множества всех пар работников, которые удовлетворяют условиям (1) и (2).

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

Пусть U - универсум и Г – множество точек соотнесения, взаимно однозначно соответствующих допустимым состояниям предметной области. Концептуализация (или интенсиональная реляционная структура) – это тройка (U,Г,R), где R – множество концептуальных (интенсиональных) отношений.

Пример 1.3. Возьмем опять предметную область, рассмотренную в примерах 1.1 и 1.2. Положим:

Г = {…, γ1,…, δ2,…};

R – следующее множество концептуальных отношений:

Работник (γ) = U для всех γГ;

Менеджер(γ) = {…, 110103482002,…} для всех γГ;

Исследователь(γ) = {…, 110104444303,…, 110104675801,…, 1101001243005}

для всех γГ;

подчинен

={…,(110104675801,110103482002),…,(110104444303,110103482002),…};

подчинен2) = {…, (110104675801,110103482002),…, (110104444303,110103482002),

, (1101001243005,110103482002) };

…………………………….

Сотрудничает_с1) = {…};

Сотрудничает_с2) = {…};

……………………………. .

Здесь для простоты мы предполпгаем, что унарные (одноместные) предикаты Работник, Менеджер и Исследователь «жесткие», т.е. каждый имеет один и тот же экстенсионал для всех γГ. Но для бинарных предикатов подчинен и сотрудничает_с нет предположения «жесткости».

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

Предположим теперь, что Lязык логики первого порядка с сигнатурой {110104675801, 110104444303, подчинен, сотрудничает_с}. Как мы можем быть уверены, что такие имена интерпретируются в соответствии с концептуализацией, которую мы намерены установить? Но в логике допустимы произвольные интерпретации сигнатуры в данном универсуме. Другим словами, когда мы делаем онтологические установки для данной концептуализации, мы должны быть уверены, что допустимыми будут только те модели, которые соответствуют нашим намерениям.

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

Здесь выявляется роль онтологии как «явной спецификации концептуализации». В принципе мы можем явно специфицировать концептуализацию двумя путями: экстенсионально и интенсионально. В наших примерах экстенсиональная спецификация данной концептуализации потребовала бы создания списков экстенсионалов каждого отношения в каждой точки соотнесения. Но это невозможно в большинстве случаев (например, в принципе когда бесконечны универсум U или множество Г точек соотнесения) или, по крайней мере, это весьма непрактично. Все-же в некоторых случаях имеет смысл частично специфицировать концептуализацию экстенсиональным образом посредством выписывания примеров и конрпримеров экстенсионалов в отдельных выбранных точек соотнесения, ссылающихся на стереотипические состояния. В общем случае, однако, более эффективный способ спецификации – фиксировать формальный язык и записать в нем ограничения на интерпретации интенсионально посредством аксиом, называемых в [Карнап, 1959] постулатами значения (meaning postulates). Например, можно написать простые аксиомы, утверждающие, что отношение подчинен асимметрично и интранзитивно, а отношение сотрудничает_с симметрично, иррефлексивно и симметрично.

Пример 1.4. В определении Грубера онтологии как «явной спецификации концептуализации» слово «явная» означает, что речь должна идти о конкретном символическом объекте. Рассматрим пример Дженесерета и Нильссона. Они анализируют ситуацию, где имеются две составленные из блоков башни (см. рис.1.2). Возможная концептуализация этой сцены дается следующей структурой:

({a, b, c, d, e}, {на, сверху, свободно, на_столе}),

где {a, b, c, d, e} – блоки, а {на, над, свободен, на_столе} – отношения между блоками, причем на и сверху – бинарные отношения, а свободен и на_столе – унарные отношения. Универсум U состоит из 9 объектов – пяти индивидных объектов a, b, c, d и четырех отношений на, сверху, свободно, на_столе. Эти отношения связывают объекты следующим образом:

FB1 = {на(a,b), на(b,c), на(d,c), на_столе(c), на_столе(e), свободно(a), свободно(d)}.

Здесь FB1 обозначает базу фактов, которая рассматривается как состояние предметной области. Другое состояние предметной области изображено на рис.1.3. Сосответствующей базой фактов является

FB2 = {на(b,c), на(a,d), на(d,e), на_столе(c), на_столе(e), свободно(a), свободно(b)}.

a

b d

c e



Рис.1.2

a

b d

c e





Рис.1.3


В кчаестве онтологии для рассматриваемой предметной области можно взять следующие предложения, записанные в языке модальной логики первого порядка:

О = {ху(на(х,у) → над(х,у),

хуz(на(х,у) /\ на(y,z) → на(х,z)),

хуz(над(х,у) /\ над(y,z) → над(х,z)),

ху(на(х,у) → на(х,у)),

у (на(х,у) → над(х,у)),

ху (на(х,у) → свободен(у))

х (на_столе(х) →у над(х,у),

х (свободен(x) → <>y на(у,х))

}.

Эта онтология формализует следующее знание, представленное неформально (в есетественном языке):

если объект х лежит на объекте у, то х находится сверху у;

если х лежит на у и у лежит на z, то х лежит на z;

если х лежит на у, то у не лежит на х;

если х лежит на у, то х находится над у;

если х лежит на у, то у не свободен;

если х лежит на столе, то не существует объекта у, такого, что х находится над у.

на объект х можно положить объект у только тогда, когда х свободен.

Замечание. Последнее предложение в онтологии О содержит модальный оператор возможности <>. Предложение это можно прочитать так:

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

В данном примере имеются две базы знаний, соотвествующие двум базам фактов:

KB1 = O U FB1 и KB2 = O U FB2.


1.5. Формальная модель понятия и концептуальные языки

Американский толковый словарь Webster следующим образом определяет термин «понятие»: An abstract or general idea inferred or derived from specific instances (Абстрактная или общая идея, выведенная или произведенная из конкретных примеров.)

Понятие есть ментальная сущность (объект), а ее примерами (экземплярами) могут быть как физические, так и ментальные сущности. Для того чтобы моделировать понятия в компьютере, необходимо символическое, формальное представление понятий и их примеров. Такое представление основано на именах, которые присваиваются (реально или потенциально) моделируемым объектам. Между именами и моделируемыми объектами имеется отношение референции ref, которое назначает объекту его имя. Вообще говоря, данный объект о может иметь не одно имя, а несколько. Мы скажем, что имена a и b кореферентны и запишем a ~ b, если они обозначают один и тот же объект. Таким образом, a ~ b тогда и только тогда, когда существует объект о такой, что о ref a и o ref b. Ясно, что кореференция является отношением эквивалентности.

Понятие имеет два аспекта – экстенсионал и интенсионал. Экстенсионал (или объем) понятия – это множество всех его примеров. Интенсионал – это совокупность условий, характеризующих примеры понятия.

Формальное понятие строится из имен. В экстенсиональном аспекте формальное понятие имеет следующие компоненты.

Имя понятия С.

Универсум понятия UCмножество всех имен, которые могут обозначать примеры понятия С.

Множество точек соотнесения Г.

Подмножество ЕСγUC для каждой точки соотнесения γГ – множество всех примеров (экземпляров) в этой точке (точнее, имен примеров).

Отношение эквивалентности ~γ , заданное на множестве ЕСγ для каждой точки соотнесения γГ – кореференция в этой точке.

Счетное множество Surr специальных имен, называемых суррогатами. Суррогаты служат идентификаторами объектов. Для каждого имени еЕСγ существует единственный суррогат sSurr, кореферентный этому имени: e ~ s.

Пара ExtСγ = (ЕСγ, ~γ) для каждой точки соотнесения γГ – экстенсионал понятия С в этой точке.

Семейство ExtС = { ExtСγ | γГ} – полный экстенсионал понятия С.

Объекты предметной области обладают, как правило, свойствами, или атрибутами. Атрибут А формального понятия С можно рассматривать как функцию, заданную на множестве ЕС = U{ ЕСγ | γГ}. Значением этой функции служит имя примера другого понятия (или этого же понятия) или элемент некоторого типа данных.

Пример 1.5. Рассмотрим задачу построения системы, хранящей сведения об учебном процессе. Тогда можно ввести такие понятия, как «студент», «преподаватель», «предмет» и т.п. Предположим, что понятие «студент» имеет атрибуты ФИО, ГодРожд (год рождения), Руков (руководитель). Формальное понятие «студент» определим как имеющее следующий компоненты.

Имя понятия: Студент;

Универсум понятия:

UСтудент = iName U Surr U {[ФИО:x, ГодРожд:y, Руков:z] | xString, yInteger zSurr}. Здесь iName – тип данных, элементы которого используются для имен индивидных объектов, а Surr – тип данных, элементами которого служат суррогаты. Элементами Surr будем считать #1, #2, #3,… .

Множество точек соотнесения: Г = {сем1, сем2,…, сем10}. Эти точки представляют семестры. Они выбраны потому, что информация об учебном процессе меняется каждый семестр.

Экстенсионалы ЕxtСтудентсемj (j = 1,2,…,10) могут быть представлены таблицами. Например, для ЕxtСтудентсем2 можно указать следующую таблицу.




Студент

Surr

Coref

ФИО

ГодРожд

Руков

#60

[‘староста группы А13’]

АндреевВ.М.’

1993

#11

#61

[]

Борисов И.В

1992

#11

:





#97

[]

Яковлев Л.Я

1992

#12


Здесь Surr – атрибут, значениями которого служат суррогаты, а Coref – атрибут, значениями которого служат списки кореферентных имен. Первая строка таблицы представляет три кореферентных имени:

#61 ~ ‘староста группы А13’ ~ [ФИО:‘Андреев В.М.’,ГодРожд:1993,Руков:#11].

Таким образом, имеем

ЕСтудентсем2 = {#60, #61, #97, ‘староста группы А13’,

[ФИО:‘Борисов И.В.’,ГодРожд:1993,Руков:#11],…,

[ФИО:‘Яковлев Л.Я.’,ГодРожд:1993,Руков:#11]}.

Отношение кореференции ~Студентсемj определяется из строк таблицы для точки соотнесения семj так, как это было показано выше.

Экстенсионал понятия Студент в точке соотнесения семj есть пара

ЕxtСтудентсемj = (ЕСтудентсемj, ~Студентсемj).

Полный экстенсионал понятия Студент есть семейство

ЕxtСтудент = { ЕxtСтудентсем1, ЕxtСтудентсем2 ,…, ЕxtСтудентсем10}.

Мы предполагаем, что руководителем студента является некоторый преподаватель. В формальном понятии Студент этому соответствует атрибут Руков, значениями которого служат суррогаты, обозначающие примеры понятия Препод. Экстенсионал этого понятия также может быть представлен таблицей, например, таблицей с атрибутами ФИО, Должность и Кафедра (кроме стандартных атрибутов Surr и Coref). Предположим, что эта таблица содержит следующую строку.


#11

[]

Вагин В.Н.

профессор

Прикладная математика


В формальном понятии Студент этому соответствует атрибут Руков, значениями которого Применение атрибута А к имени е, обозначающего пример понятия, записывается как е.А. В данном случае, например, имеем

#60.ФИО =‘Андреев В.М.’, #60.ГодРожд =1993,

староста группы А13’.ФИО =‘Андреев В.М.’,

#60.Руков =#11, #60.Руков.ФИО =#11.ФИО =‘Вагин В.Н.’.

(Конец примера.)

Как мы видели, экстенсионал понятия С в каждой точке соотнесения γГ есть пара (ЕСγ, ~γ), состоящая из множества имен ЕСγ, обозначающих примеры понятия, и отношения кореференции ~γ, заданного на этом множестве имен. Если взять фактор-множество ЕСγ / ~γ множества ЕСγ по отношению эквивалентности ~γ , то это множество будет состоять из абстрактных объектов, которые взаимно однозначно соответствуют объектам предметной области, рассматриваемых в точке соотнесения γ.

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

Данное выше определение формального понятия относится к экстенсиональному аспекту термина «понятие». Но имеется также интенсиональный аспект этого термина, связанный со спецификацией компонентов формального понятия. Мы используем термин «спецификация», а не термин «определение», имея в виду, что результат определения однозначен, но результат спецификации может быть неоднозначен.

В примере 1 два понятия Студент и Препод связаны друг с другом с помощью атрибута Руков. Кроме того, эти понятия имеют одни и те же точки соотнесения.

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

Формальной онтологией для системы понятий Е назовем конечное множество предложений О некоторого формального языка, специфицирующих формальные понятия из Е. (В дальнейшем, говоря о формальных понятиях, будем опускать слово «формальные».)

Замечание. Нечеткие понятия и нечеткая онтология определяются аналогично. Нужно только считать, что ЕСγ являются нечеткими подмножествами UC, а атрибуты – нечеткими одноместными функциями.

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

Структуральные предложения. Специфицируют универсумы понятий.

Логические предложения. Специфицируют экстенсионалы понятий равномерно по точкам соотнесения.

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

Замечание. Фактически спецификация универсума является определением, т.е. результат спецификации однозначен (как это видно в примере 1.5).

Пример 1.6. Для спецификации указанного в примере 1 универсума UСтудент понятия Студент можно взять структуральное предложение

Студент[ФИО:String,ГодРожд:Integer,Руков:Препод].

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

FORALL Студент X,Y (IF X.Группа = Y.Группа

THEN X.Руков.Кафедра = Y.Руков.Кафедра).

Транзитные предложения представляют ограничения, выражающие изменения экстенсионалов при переходах в соответствие с бинарным отношением, заданным на точках соотнесения. В данном случае естественно взять отношение Позже, определяемое следующим образом: семj Позже семk ódf j>k. Возьмем ограничение, состоящее в том, что для каждого студента допускается только одна смена руководителя. Тогда это ограничение можно представить следующим предложением:

FORALL Студент Х; Por Y

(IF EXIST Por Z;Z Позже Y;(X.Руков<Y> =/= X.Руков<Z>)

THEN FORALL Por V; V Позже Z; (X.Руков = X.Руков).

Здесь Por обозначает тип данных «точка соотнесения» (point of reference). Выражение X.Руков<Y> обозначает значение X.Руков в точке соотнесения Y.

(Конец примера.)

Пусть Е – система понятий, отвечающая данной концептуализации, а О – формальная онтология, специфицирующая Е. Тогда Е служит моделью онтологии О. В соответствующей интерпретации все предложения из О будут истинными. Эту интерпретацию назовем главной. Но, поскольку результат спецификации, как правило, неоднозначен, существуют другие интерпретации онтологии О (соответствующие другим системам понятий). Используя эти интерпретации, можно определить отношение |= логического следствия между онтологией О и предложением s языка онтологии: О |= s ódf не существует интерпретации, в которой все предложения из О истинны, а предложение s ложно.












ГЛАВА 2
БИНАРНАЯ МОДЕЛЬ ЗНАНИЙ


2.1. Синтаксис имен, используемых в БМЗ

Суррогаты будут обозначаться #1, #2, #3 и т.д. Множество суррогатов Surr = {#1,#2,#3,…} мы будем рассматривать как стандартный тип данных. Также через Surr будем обозначать атрибут, который, будучи примененным к имени объекта, дает суррогат этого объекта.

Если aимя объекта obj, то этот объект называется референтом (или денотатом) этого имени: ref(a) = obj. Если имена a и b имеют один и тот же референт, ref(a) = ref(b), то эти имена называются кореферентными. Ясно, что кореферентность имен является отношением эквивалентности. Мы будем писать a ~ b, если имена. В частности, имеем a ~ a .Surr, т.е. имя а кореферентно суррогату a .Surr этого имени.

Формальные понятия строятся из имен. Пусть U – универсум имен (т.е. потенциальное множество имен для понятий и их примеров). Входящие в него имена разделяются на имена понятий, имена типов данных (значений), имена атрибутов и имена (индивидных) объектов.

Эти имена имеют следующий синтаксис.

Имена атрибутов и простые имена понятий записываются как слитные (т.е. без пробелов) строчки символов клавиатуры, начинающиеся с заглавной буквы и не включающие знаков пунктуации, скобки и символов #, %, ^, + , | , <, >, “, \ , /. Множество всех таких строчек обозначим String1.

Через String0 обозначим множество строчек, получающихся из строчек множества String1 путем замены начальной большой буквы на малую. Простые имена вида w#j, где wString0 и jнатуральное число (j{0,1,2,…}), называются суррогатами, ассоциированными с именем w. Эти суррогаты используются в качестве идентификаторов для индивидных объектов моделируемой ПО. Множество всех суррогатов обозначается Surr. (Заметим, что множество Surr не пересекается в String0, так как суррогаты содержат символ #, но строчки из String0 этот символ не содержат.)

Пусть СString1 и с – соответствующее имя из String0. Обозначим SurrC= {c#j | j = 0,1,2,…}. Например, если в качестве С возьмем имя Студент, то элементами множества SurrC служат слова студент#j (j = 0,1,2,…).

Простыми именами объектов считаются строчки из String0, суррогаты и произвольные строчки, взятые в одиночные кавычки.

Составные имена понятий имеют следующие формы:

C1 | C2 |…| Cn , где Cj String1 (1jn);

С(*), где С String1;

(K1, K2,…, Kn), где Kj String1 или Kj есть пара вида E: D с E, D String1;

С(α), где С String1 и α – атрибутное условие. Синтаксис атрибутных условий будет рассмотрен в п. 2.5. Синтаксис составных имен для типов данных будет рассмотрен позднее в п. 2.3.1.

Составные имена объектов имеют форму

[A1: e1, A2: e2,…, Am: em],

где Ai имена атрибутов, а ei имена индивидных объектов (1im).

Примеры 2.1:

Студент, Профессор, Доцент, P@mt_ab21 – простые имена понятий;

ФИО, ГодРожд, Price – имена атрибутов;

Доцент | Профессор , Студент(*) – составные имена понятий;

студент#1, студент#27, ‘староста группы А13-05’ – простые имена объектов;

SurrСтудент = {студент#0, студент#1, студент#2,…};

[ФИО: ‘А.П. Иванов’, ГодРожд: 1985] – составное имя объекта.

Замечание. В составном имени объекта ‘А.П. Иванов’ использованы одиночные кавычки, так как, если снять кавычки, то получится строчка, которая уже не является именем в системе БМЗ.

Множество всех строчек обычно рассматривают как примитивный (предопределенный) тип данных, обозначаемый String. На этом типе данных действует операция конкатенации: если x, y - произвольные строчки символов, то их конкатенация xy есть строчка, получаемая присоединением строчки у к строчке х. При этом конкатенацией строчек, взятых в одиночные кавычки, ‘x’ и ‘y’ считается строчка ‘xy’, а не ‘x’‘y’.


2.2. Бинарная Модель Данных

В системе БМЗ имеется подсистема «Бинарная Модель Данных» (БМД). В БМД используются следующие языки:

язык описания данных – ЯОД. Используется для спецификации универсумов понятий, т.е. фактически для определения структуры объектов – примеров и контрпримеров понятий. Поэтому предложения ЯОД называются структурными. Таким образом, ЯОД является языком структурной спецификации систем понятий;

язык для спецификации типов данных (значений) – ЯТД. Этот язык можно рассматривать как подъязык ЯОД;

язык запросов к базе данных – ЯЗД;

язык атрибутных условий – ЯАУ. Эти условия являются компонентами запросов.

языки для спецификации логических отношений между понятиями. Предложения этих языков называются логическими. Заметим, что язык атрибутных условий ЯАУ можно рассматривать как логический (условие является булевой комбинацией бинарных отношений между селекторами, которые являются атрибутами или итерациями атрибутов);

языки для спецификации модальных отношений (включая темпоральные отношения);

язык продукций – ЯП.





2.2.1. Спецификация типов данных


В БМЗ используются два вида имен для типов данных – простые (примитивные, предопределенные) имена и составные имена. Простыми именами для типов данных являются:

Boolean = {true, false} . На этом типе данных действуют логические операции NOT x, x AND y, x OR y, x IMP y (x IMPy = false тогда и только тогда, когда x =false и y =true);

Number = {0,1,2,…} (в ASCII представлении). На этом типе данных действуют стандартные бинарные операции (Number,Number)à Number: сложение x+y ; умножение x*y ; усеченная разность x-y (x-y=0, если х меньше y ; возведение в степень x**y; действуют также операции сравнения (Number,Number)àBoolean: , x<y ( x<y =true тогда и только тогда, когда x меньше y), x =<y, x>y, x>=y, x=/y (x не равно y);

Integer = {0,1,-1,2,-2,…} и Real – вещественные числа (в ASCII представлении). На этих типах данных действуют те же операции, что и на типе Number (но вычитание не усеченное);

Char – тип знаков, т.е. букв и символов клавиатуры в ASCII представлении:

A a B b C c D d E e F f G g H h I i J j K k L l M m N n O o P p Q q R r S s T t U u V v W w X x Y y Z z А а Б б В в Г г Д д Е е Ж ж З з И и Й й К к Л л М м Н н О о П п Р р С с Т т У у Ф ф Х х Ц ц Ч ч Ш ш Щ щ Ъ ъ Ь ь Ы ы Э э Ю ю Я я ~ ` @ # $ % & * / \ ^ _ - " # ; : < > ? . , | + ( ) '

String – строчки символов клавиатуры (в ASCII представлении). На этом типе действует операция конкатенации x^y (к строчке x приписывается без пробела строчка y) и операция LNG: String à Nat(LNG(x) – длина сточки x . (Например, если x = ‘100$ abc’ и y = ‘De’, то LNG(x) = 10 и x^y = ‘100$ abc’’De’ .)

Составные имена для типов данных специфицируют производные типы данных, которые получаются из примитивных типов путем применения конструкторов типов.

2.2.2. Конструкторы типов данных


Пусть Alpha - какая-либо спецификация некоторого типа данных. Через "Alpha" обозначим этот тип значений (точнее, множество всех элементов типа значений, специфицированного выражением Alpha).

Замечание. Вообще, двойные кавычки, заключающие произвольное выражение exp, обозначают смысл (значение) этого выражения. Например, если переменная X приняла значение true, а переменная Y приняла значение false, т.е. “X” = true и “Y” = false, то “X ANDY” = false.

n-Местный конструктор F по спецификацям типов Alpha1, Alpha2,…, Alphan (синтаксически) дает спецификацию F(Alpha1,Alpha2,...,Alphan). Семантически, этот конструктор есть n-местная функция, которая для данных типов значений "Alphaj" определяет новый тип значений

"F(Alpha1,Alpha2,...,Alphan)".

Любую спецификацию типа значений Alpha можно рассматривать как имя того типа "Alpha", который определяется этой спецификацией. Поэтому, следуя обычной практике, мы будем, говоря о типе значений "Alpha", часто использовать его имя Alpha.

Замечание. На любом типе данных Alpha действуют два оператора сравнения =, /= : (Alpha,Alpha) à Boolean: “x=y x” = “y” и “x/= y xy”. Выражение x/=y эквивалентно выражению NOT x=y : “NOT x=yсовпадает с x/=y”.

Конструктор (*).

Alpha à Alpha(*),

Alpha(*)” = {{x1,x2,...,xp} | xj "Alpha" (1 j p), p = 0,1,2,...}.

Другими словами, элементами типа Alpha(*) являются выражения, представляющие произвольные конечные множества, которые составлены из элементов типа Alpha. Точнее, элементами типа Alpha(*) являются выражения вида {e1,e2,...,ep}, которые можно рассматривать как (составные) имена для соответствующих конечных множеств, состоящих из имен – элементов типа Alpha. Поэтому, если элементы ej Alpha” в {e1,e2,...,ep} записать в другом порядке, то получим выражение, обозначающее то же самое множество, т.е. имеем кореферентные имена: {e1,e2,...,ep} ~ {ei1,ei2,...,eip}, где i1, i2,…, ip – числа от 1 до p, записанные в произвольном порядке. (Например, {a, b, c, d} ~ {d, a, c, b}.)

Конструктор объединения

Этот конструктор образует объединение типов:

Alpha, Beta --> Alpha | Beta,

Alpha | Beta” = {x | xAlpha” или xBeta}.

Конструктор {}.

Если Alpha – произвольный тип значений и e1, e2,...,en какие-либо элементы этого типа, то {e1,e2,...,en} есть спецификация конечного типа, состоящего из этих элентов, т.е. “{e1,e2,...,en}” – множество из элементов e1, e2,...,en .

Конструктор декартова произведения ( , ,…)

Этот конструктор дает декартово произведение типов:

Alpha1, Alpha2,..., Alphan à (Alpha1,Alpha2,...,Alphan),

(Alpha1,Alpha2,...,Alphan)” = {(x1,x2,...,xn) | xj “Alphaj (1jn)}.

Таким образом, элементами декартова произведения служат выражения – упорядоченные n-наборы, составленные из элементов типов Alphaj .

С конструктором декартова произведения ассоциированы операция "точка", с помощью которой можно находить компоненты элементов декартова произведения: если e = (e1,e2,...,en) и 1 j n, то e.j = ej ; если же j > n, то значение e.j не определено.

Конструктор «метка».

Пусть L String1 – "метка", рассматриваемая как атрибут.

Alpha, L à L: Alpha,

L: Alpha” = { L: x | x“Alpha”}.

Таким образом, элементами “Alpha” являются выражения вида L: e , где е – произвольный элемент типа Alpha.

На этом типе значений действует операция применения атрибута L : если переменная X приняла значение L: е, то X.L = e. Если конструктор «метка» используется в комбинации с декартовым произведением, то получается так называемое помеченное декартово произведение:

Alpha1, L1, Alpha2, L2,..., AlphaN, Ln à

(L1: Alpha1, L2: Alpha2,..., Ln: Alphan),

(L1: Alpha1, L2: Alpha2,..., Ln: AlphaN)” =

{(L1: x1, L2 :x2,..., Ln:xn) | xj Alphaj (1jn)}.

Метка, примененная как атрибут к элементу е = (L1: e1, L2 : e2,..., Ln: en) помеченного декартова произведения, позволяет получать ту компоненту, которая помечена этой меткой:

(L1: e1, L2 : e2,..., Ln: en).Lj = ej .

Вариантом конструктора L: является конструктор /L: /. Различие между этими конструкторами лишь в том, что когда /L: / входит в помеченное декартово произведение, компонента L: может быть пропущена. Рассмотрим, например, следующую спецификацию составного типа:

(/L: Alpha/, M: Beta, /N: Gamma/).

Эта спецификация дает тип данных

(/L: Alpha/, M: Beta, /N: Gamma/)” =

{(L: x, M: y, N: z) | xAlpha, yBeta, zGamma}

{(L: x, M: y) | xAlpha, yBeta}

{(M: y, N: z) | yBeta, zGamma} { M: y | yBeta}.

Конструктор списков LIST.

Этот конструктор по данному типу значений строит новый тип, элементами которого служат всевозможные списки, составленные из элементов исходного типа. Мы выбираем синтаксис списков такой, как в Прологе. Например, выражения [], [0,1,2], [[],[0,1,2],1,0], [[[0]]] и т.п. являются элементами типа значений LIST(Nat).

Alpha à LIST(Alpha),

LIST(Alpha)” – множество всех списков, использующих элементы типа Alpha в качестве атомов.

С конструктором списков ассоциированы стандартные операции Лиспа:

сar: LIST(Alpha) à Alpha | {nil},

cdr: LIST(Alpha) à LIST(Alpha),

cons: (Alpha | LIST(Alpha), LIST(Alpha)) à LIST(Alpha).

Например, если переменные X, Y и Z приняли соответственно значения 2, [0,[1]], [[1,2],[0,0],3], то будем иметь:

car(Y) = 0, car(Z) = [1,2], car(X) и cdr(X) не определены,

cdr(Y) = [[1]], cdr(Z) = [[0,0],3], cons(X,Y) = [2,[0,1]],

cons(Y,Z) = [[0,[1]],[1,2],[0,0],3].

Операцию cons можно также обозначать :: и использовать в инфиксной нотации, считая, что выражения cons(X,Y) и X::Y эквивалентны, т.е. “cons(X,Y)” = “X::Y”. Таким образом, X::Y обозначает список, получаемый из списка “Y” путем вставки “X” на первое место (т.е. перед первым элементом списка “Y”).

Введем также операцию соединения двух списков, которую обозначим :-: и будем использовать ее в инфиксной нотации. (Эта операция соответствует функции append Лиспа.) Если, например, переменные X и Y прияли соответственно значения [2,[0,1],3] и [[],1,2,[3,0]], то “X:-:Y” = [2,[0,1],3,[],1,2,[3,0]].

Конструктор линейного списка LLIST.

Этот конструктор строит тип данных, элементами которого служат линейные (т.е. неразветвленные) списки, составленные из элементов данного типа данных:

Alpha à LLIST(Alpha),

LLIST(Alpha)” = {[x1,x2,...,xp] | xj Alpha” (1