Модель семантические сети. Семантическое моделирование

Лабораторная работа №1

Использование семантических сетей

для представления знаний

Цель работы: Научиться использовать семантические сети для представления знаний в информационных аналитических системах.

1. т еоретическая часть

Семантическая сеть – это один из способов представления знаний. Изначально семантическая сеть была задумана как модель представления долговременной памяти в психологии, но впоследствии стала одним из способов представления знаний в экспертной системе.

Семантика – означает общие отношения между символами и объектами из этих символов.

Рис.1. Простейший образец семантической сети.

Вершины – это объекты, дуги – это отношения. Семантическая модель не раскрывает сама по себе, каким образом осуществляется представление знаний. Поэтому семантическая сеть рассматривается как метод представления знаний и структурирования знаний.

Характерная особенность семантических сетей – это обязательное наличие 3 типов отношений.

Пример : класс – элемент класса, свойство – значение.

Пример элемента класса.

Существует несколько классификаций семантических сетей:

1) По количеству отношений

1. Однородные с единственным типом отношений;

2. Неоднородные с различными типами отношений.

2) По типам отношений

1. Бинарные сети – в которых отношения связывают 2 объекта;

2. Парные сети – в которых отношения связывают более чем 2 понятия.

Наиболее часто используются в семантических сетях:

1. Связь “часть – целое” (класс подкласс, элемент - множество);

2. Функциональные связи (производит, владеет);

3. Количественные отношения (A > 0, B < 0);

4. Пространственные отношения (далеко от, близко от, над, за и т. п.);

5. Временные (раньше, позже, одновременно);

6. Атрибутивные (иметь свойство, иметь значение);

7. Логические связи – и, или, не.

Минимальный состав отношений в семантической сети - это элемент класса, атрибутные связи и значение свойства.

При расширении семантической сети в ней возникают другие отношения:

IS – A (принадлежит) и PART OF (является частью) отношение:

целое ® часть .

Ласточка IS – A птица, «нос» PART OF «тело». Например:

Рис.2. Расширение семантической сети

Например, в предложении

«человек» IS - A «млекопитающее»

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

Отношение «целое – часть» можно иллюстрировать предложением

«нос» PART - OF «тела» ,

которое характеризует то, что экземпляры понятия «нос» являются частью любого экземпляра понятия «тело».

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

«все ласточки – птицы»

можно представить графом, содержащим две вершины соответствующие понятиям и дугу, указывающую отношение между ними (рис. 2.1).

Рис. 2.2. Семантическая сеть - 2

Наряду с тем, что с помощью данной сети описаны два факта

«Юка – ласточка»

«ласточка – птица»

из нее можно вынести, используя отношение наследования, факт

«Юка – птица»

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

Семантическими сетями можно также представлять знания, касающиеся атрибутов объекта. Например, факт «Птицы имеют крылья» можно отобразить в виде рис. 25.3.

Рис. 2.3. Семантическая сеть - 3

Это означает, что, используя отношения «IS – A» и «PART – OF» можно вывести факт «Юка имеет крылья».

Вершины в семантической сети обычно показывают объект проблемной области, концепт, ситуацию и т. п., а дуги - это отношения между ними. При расширении семантической сети в ней возникают дополнительные отношения. Например, если рассматриваемую сеть дополнить фактами «Юка владеет гнездом» и «Юка владеет гнездом с весны по осень», то получим семантическую сеть, изображенную на рис. 2.4. Здесь гнездо i – это конкретное гнездо, которым владеет Юка, а для вершины ситуации (владеет j) определено несколько связей. Такая вершина называется надежной рамкой и определяет различные аргументы предиката ситуации.

Рис. 2.4. Семантическая сеть - 4

Получается иерархическая структура понятия ЮКА. Можно разбить на подсхемы. Большой проблемой для семантических сетей является то, что результат вывода не гарантирует достоверности, так как вывод есть просто наследование свойств ветви is-a.

Для отображения иерархических отношений между объектами и введения единой семантики в семантические сети было предложено использовать процедурные сети . Сеть строится на основе класса (понятия); вершины, дуги и процедуры представлены как объекты.

Проблема поиска решения в базе знаний типа семантической сети

сводится к задаче поиска фрагмента сети, соответствующего некоторой подсети, соответствующей поставленному вопросу.

На рис. 3, 4 и 4-1 изображены примеры семантической сети.

Рисунок 3 – Модель

Рис. 4 Семантическая сеть, показывающая взаимоотношения птицы и самолета.

Рис. 4-1 Семантическая сеть, являющейся описанием объекта автомобиль и ряда связанных с ним понятий

В частности для рис. 4-1 присутствует следующая цепочка понятий:

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

Преимущества модели:

Совпадает с тем, как человек познает мир;

Соответствие долговременной памяти человека.

Недостатки:

Сложность с поиском вывода.

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

Возможные в семантических сетях отношения приведены в таблице.

Прямой и обратный вывод в экспертной системе продукционного типа.

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

Механизм вывода выполняет две основные функции:

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

· определение порядка просмотра и применения правил. Порядок может быть прямым или обратным.

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

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

Для выполнения указанных функций механизм вывода включает компоненту вывода и управляющую компоненту. Действие компоненты вывода основано на применении правила логического вывода Modus Ponendo Ponens. Суть применения этого правила в продукционных системах состоит в следующем. Если в рабочей памяти присутствует истинный факт А и в базе правил существует правило вида «если А, то В», то факт В признается истинным и заносится в рабочую память. Такой вывод легко реализуется на ЭВМ, однако при этом часто возникают проблемы, связанные с распознаванием значений слов, а также с тем, что факты могут иметь внутреннюю структуру, и между элементами этой структуры возможны различного рода связи. Например, пусть имеется факт А - «автомобиль Иванова - белый» и правило «если автомобиль - белый, то автомобиль легко заметить ночью». Человек легко выведет заключение «автомобиль Иванова легко заметить ночью», но это не под силу экспертной системе чисто продукционного типа. Она не сможет сформировать такое заключение, потому что А не совпадает точно с антецедентом правила. Кроме того, невысокая интеллектуальная мощность продукционных систем обусловлена тем, что человек выводит заключения, имея в своем распоряжении все свои знания, то есть база знаний огромного объема, в то время как экспертные системы способны вывести сравнительно небольшое количество заключений, используя заданное множество правил. Из сказанного можно сделать вывод о том, что компонента вывода в экспертных системах должна быть организована так, чтобы быть способной функционировать в условиях недостатка информации.

Управляющая компонента определяет порядок применения правил, а также устанавливает, имеются ли еще факты, которые могут быть изменены в случае продолжения работы (при немонотонном выводе). Механизм вывода работает циклически, при этом в одном цикле может сработать только одно правило. Схема цикла приведена на рис. 5. В цикле выполняются следующие основные операции:

· сопоставление - образец (антецедент) правила сравнивается с имеющимися в рабочей памяти фактами;

· разрешение конфликтного набора - выбор одного из нескольких правил в том случае, если их можно применить одновременно;

· срабатывание правила - в случае совпадения образца некоторого правила из базы правил с фактами, имеющимися в рабочей памяти, происходит срабатывание правила, при этом оно отмечается в базе правил;

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

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

Рис. 5 Цикл работы вывода.

Рассмотрим простейшие примеры прямого и обратного вывода в системах продукционного типа.

Пример прямого вывода. Пусть в базе правил имеются следующие правила:

Правило 1. «если двигатель не заводится, и фары не горят, то сел аккумулятор».

Правило 2. «если указатель бензина находится на нуле, то двигатель не заводится».

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

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

2. Действие сработавшего правила 2. В рабочую память заносится заключение этого правила, то есть образец: двигатель не заводится.

3. Второй цикл сопоставления фактов в рабочей памяти с образцами правил. Теперь срабатывает правило 1, так как совпадение условий в его антецеденте становится истинной.

4. Действие правила 1, которое заключается в выдаче пользователю окончательного диагноза - сел аккумулятор.

5. Конец работы (база правил исчерпана).

Пример прямого вывода с конфликтным набором. Теперь допустим, что в базе правил кроме правила 1 и правила 2 присутствует правило 3: «если указатель бензина находится на нуле, то нет бензина». В рабочей памяти находятся те же факты, что в предыдущем примере. В результате сопоставления в первом же цикле возможно применение двух правил - правила 2 и правила 3, то есть возникает конфликтный набор и встает задача выбора: какое из этих правил применить первым. Если выберем правило 2, то в рабочей памяти добавится факт «двигатель не заводится» и на следующем шаге опять возникнет конфликтный набор, так как можно будет применить правило 1 и правило 3. Если будет выбрано правило 1, то к заключению «сел аккумулятор» придем за два шага. При любом другом выборе порядка применения правил к этому же заключению приходим за три шага. Если завершение цикла работы экспертной системы наступает после просмотра всех правил, то число шагов будет равно трем, причем порядок применения правил не будет иметь какого-либо значения.

Пример обратного вывода. Предположим, что в базе правил имеется два правила (правило 1 и правило 2), а в рабочей памяти - те же факты, что в предыдущих примерах с прямым выводом.

Алгоритм обратного вывода содержит следующие шаги.

1. Выдвигается гипотеза окончательного диагноза - сел аккумулятор.

2. Отыскивается правило, заключение которого соответствует выдвинутой гипотезе, в нашем примере - это правило 1.

2. Исследуется возможность применения правила 1, то есть решается вопрос о том, может ли оно сработать. Для этого в рабочей памяти должны присутствовать факты, совпадающие с образцом этого правила. В рассматриваемом примере правило 1 не может сработать из-за отсутствия в рабочей памяти образца «двигатель не заводится». Этот факт становится новой целью на следующем шаге вывода.

3. Поиск правила, заключение которого соответствует новой цели. Такое правило есть - правило 2.

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

5. Действие правила 2, состоящее в занесении заключения «двигатель не заводится» в рабочую память.

6. Условная часть правила 1 теперь подтверждена фактами, следовательно, оно срабатывает, и выдвинутая начальная гипотеза подтверждается.

7. Конец работы.

При сравнении этого примера с примером прямого вывода нельзя заметить преимуществ обратных выводов перед прямыми выводами.

Пример обратного вывода с конфликтным набором. Предположим, что в базе правил записано правило 1, правило 2, правило 3 и правило 4: «если засорился бензонасос, то двигатель не заводится». В рабочей памяти присутствуют те же самые факты: «фары не горят и указатель бензина находится на нуле». В данном случае алгоритм обратного вывода с конфликтным набором включает следующие шаги.

1. Выдвигается гипотеза сел аккумулятор.

2. Поиск правила, заключение которого совпадает с поставленной целью. Это правило 1.

3. Исследуется возможность применения правила 1. Оно не может сработать, тогда выдвигается новая подцель «двигатель не заводится», соответствующая недостающему образцу.

4. Поиск правил, заключения которых совпадают с новой подцелью. Таких правил два: правило 2 и правило 4. Если выберем правило 2, то дальнейшие шаги совпадают с примером без конфликтного набора. Если выберем правило 4, то оно не сработает, так как в рабочей памяти нет образца: «засорился бензонасос». После этого будет применено правило 2, что приведет к успеху, но путь окажется длиннее на один шаг.

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

Семантическая сеть как Пролог - программа

Важнейшей концепцией формализма семантических сетей является иерархия понятий и связанное с ней наследование атрибутов между уровнями иерархии IS - A.

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

На рис. 6 представлена структура сети, аналогичная примеру предыдущего раздела.

Рис. 6. Семантическая сеть

Эта сеть может быть реализована в Пролог - программе

является (ласточка, птица)

является (Юка, ласточка)

имеет (крылья, птица)

имеет (X, Y): - является (Y, Z), имеет (X , Z).

/* учитывает иерархию наследования */

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

имеет (черный цвет, ласточка)

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

летает (птица)

но и правила, которое должно реализовать иерархию наследования, т. е.

летает (Х):- является (Х, Y), летает (Y).

Элементы семантической сети

Семантическая сеть представляет собой ориентированный граф с помеченными (поименованными) дугами и вершинами. Основными элементами сети являются вершины и дуги. При этом вершинам семантической сети соответствуют понятия, события и свойства (рис. 7).

Рис. 7. Вершины семантической сети

Понятия представляют собой сведения об абстрактных или физических объектах предметной области (реального мира).

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

Указание типа действия;

Указание ролей, которые играют объекты в этом действии.

Свойства используются для уточнения понятий и событий. Применительно к понятиям они описывают их особенности и характеристики (цвет, размер, качество), а применительно к событиям - продолжительность, время, место.

Дуги графа семантической сети отображают многообразие семантических отношений, которые условно можно разделить на четыре класса (рис. 8).

Рис. 8. Классификация семантических отношений

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

Глагольные (время, вид, род, залог, наклонение);

Атрибутивные (цвет, размер, форма);

Падежными (см. ниже).

Логические отношения - это операции, используемые в исчислении высказываний (алгебра логики): дизъюнкция, конъюнкция, инверсия, импликация.

Теоретико-множественные - это отношение подмножества, отношение части целого, отношение множества и элемента. Примерами таких отношений являются IS-A, PART-OF.

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

Рассмотренные выше примеры семантических сетей отображали знания о структуре понятий и их взаимосвязях. Далее рассмотрим использование семантических сетей для представления событий и действий.

Представление структуры понятий семантической сетью

Основой для определения любого понятия является множество его отношений с другими понятиями. Обязательными отношениями являются:

Класс, которому принадлежит данное понятие;

Свойства, выделяющие понятие из всех понятий данного класса;

Примеры (экземпляры) данного понятия.

Так как термы, используемые в определении понятия, сами являются понятиями, то их определение организуется по той же схеме. В итоге связи понятий образуют структуру, в общем случае сетевую, в которой используется как минимум два типа связей (IS - A и PART – OF).

Пример : Семантическая сеть, отображающая связи понятий при описании знаний о структуре понятия юридическое лицо будет иметь вид (рис. 9):

0 " style="border-collapse:collapse;border:none">

Падеж

Лингвистическое (падежное) отношение,
определяющее связь действия с:

Предметом, являющимся инициатором действия

Предметом, подвергающимся действию

источник

Размещение предмета перед действием

приемник

Размещение предмета после действия

Моментом выполнения действия

Местом проведения действия

Действием другого события

Так, например, семантическая структура знания о событии «Директор завода «Салют» остановил 30.03.96 цех №4 чтобы заменить оборудование» будет представлена в виде рис. 10.

https://pandia.ru/text/80/351/images/image017_7.jpg" width="563" height="136 id=">

Рис. 11. Семантическая сеть «Подчиненность сотрудников организации»

Приведенные связи показывают подчиненность первого сотрудника. Остальные сотрудники связываются через вершины сети. Остальные сотрудники связываются через вершины сети «руководит 2», «руководит 3» и т. д.

Запрос: «Кто руководит Сидоровым?», представим в виде подсети (рис. 12.

DIV_ADBLOCK277">

Выделим основные факты этих знаний, соответствующие действиям:

F1 - станок закончил обработку

F2 - работник грузит

F3 - робокар перевозит

F4 - кассета содержит детали

Заметим, что при описании фраз естественного языка факты часто называют высказываниями. Схема семантической сети будет следующей (рис. 13):

Рис. 13. Построение семантической сети

Пример фрагмента программы прямой цепочки рассуждений приведен на рис. 14. Для простоты предполагается, что правила не содержат переменных.

Рис. 14. Пример фрагмента программы прямой цепочки рассуждений

Поиск решения:

1. На основании фактов, известных на момент решения задачи, можно решить только правило %3. В результате состав фактов станет таким:

Вода(гостиная)

Сухо(ванная)

Закрыто (окно)

Неисправность (кухня)

2. Делается попытка решить очередное правило. Таким правилом станет правило %4. В результате к фактам добавится ещё один:

Вода(гостиная)

Сухо(ванная)

Закрыто (окно)

Неисправность (кухня)

НеПоступает (вода, снаружи)

3. Становится возможным решение правила %2, и получается ответ YES

Необходимо отметить ряд преимуществ семантической сети:

Описание понятий и событий производится на уровне, очень близком к естественному языку;

Обеспечивается возможность сцепления различных фрагментов сети;

Отношение между понятиями и событиями образуют достаточно небольшое и хорошо формализованное множество;

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

1. Изучить теоретическую часть по приведенным выше данным и дополнительной литературе;

2. Просмотреть демонстрационные примеры;

3. Получить у преподавателя вариант задания для выполнения;

4. Построить семантическую модель заданного объекта;

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

3. Варианты заданий

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

1. географии какого-либо региона. Дуги: государство, страна, континент, широта.

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

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

10. иерархической структуры БД. Дуги: система, состояние, назначение, взаимодействие составляющих.

4. К онтрольные вопросы

1. Что такое семантическая сеть и для чего ее применяют?

2. В чем состоит идея создания семантической сети?

3. Каким образом представляются данные в семантической сети?

4. Существуют ли ограничения на число связей элементов, свойств и сложность при построении семантической сети?

5. Какие отношения предложены в качестве операторов отношения для группировки вершин?

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

Прежде чем мы коротко рассмотрим особенности распространенных семантических моделей, остановимся на их возможных применениях.

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

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

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

Семантическая модель Entity-Relationship (Сущность-Связь)

Одной из наиболее популярных семантических моделей данных является модель "Сущность-Связь" (часто ее называют кратко ER-моделью).

На использовании разновидностей модели ER-модели основано большинство современных подходов к проектированию баз данных (главным образом, реляционных). Модель была предложена Ченом (Chen) в 1976 г. Моделирование предметной области базируется на использовании графических диаграмм, включающих небольшое число разнородных компонентов. В связи с наглядностью представления концептуальных схем баз данных ER-модели получили широкое распространение в системах CASE, поддерживающих автоматизированное проектирование реляционных баз данных.

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

Термин «объект» не поддается всеобъемлющему определению. Достаточно сказать, что объект -это нечто существующее и различимое, т. е. мы можем отличать один объект от другого. Например, каждый стул есть объект. Объектами являются также конкретные человек и автомобиль. Можно считать объектом любого муравья, если имеется способ отличать его от других муравьев. В противном случае мы не воспринимаем муравья как объект. Объектами могут быть и понятия более высокого уровня, например, паук, грызун, бабуин и растение в биологической базе данных. Если не быть слишком строгими, то к объектам можно отнести и такие понятия, как любовь и ненависть.

Группа всех подобных объектов образует набор объектов. Так, наборами объектов могут быть все люди, все автомобили, все животные, все эмоции.

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

Атрибуты и ключи

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

Выбор подходящих атрибутов для наборов объектов является вторым ключевым моментом в проектировании модели реального мира. Атрибут или множество атрибутов, значения которых уникально идентифицируют каждый объект в наборе объектов, называется ключом этого набора объектов. В принципе, каждый набор объектов имеет ключ, поскольку мы приняли гипотезу о том, что каждый объект отличим от остальных. Но если для набора объектов мы выбрали совокупность атрибутов, не содержащую ключа, то отличить один объект в наборе от другого окажется невозможным. Часто в качестве атрибута, который служит ключом, предоставляется произвольно выбранный последовательный номер. Например, в наборе объектов, включающем только граждан США, может использоваться в качестве ключа единственный атрибут -«номер социальной безопасности».

Возможны случаи, когда объекты в наборе различаются не по атрибутам, а по их связи с объектами другого типа. Наиболее важным видом «встроенных» связей (связи, определенные пользователем, будут описаны позднее) является связь “есть”. Мы говоримAесть В и записываем «AестьB», если набор объектов В является обобщением набора объектовA, или, что равносильно,Aесть специальный вид В.

Рассмотрим базу данных автомобилей с набором объектов МАРКИ, имеющим атрибуты ТИП и МОДЕЛЬ. Объектом в наборе МАРКИ является, например, «Datsun-280».Мы могли бы рассмотреть и набор объектов АВТОМОБИЛИ с атрибутом СЕРИЙНЫЙ-НОМЕР, который можно было бы считать ключом этого набора. Однако вполне вероятно, что два типа автомобилей используют одни и те же серийные номера. Чтобы сделать объекты в наборе АВТОМОБИЛИ уникальными, нам потребуется связь между наборами АВТОМОБИЛИ и МАРКИ, представляющая тот факт, что любой автомобиль имеет конкретную марку. Тогда каждый экземпляр из набора объектов АВТОМОБИЛИ будет однозначно определяться по его СЕРИЙНОМУ-НОМЕРУ и атрибуту ТИП связанного с ним объекта из набора МАРКИ.

Связь между наборами объектов представляет собой просто упорядоченный список наборов объектов. Конкретный набор объектов может появляться в этом списке более одного раза. Если имеется связь RELмежду наборами объектов Е 1 , Е 2 , ..., E k ,то предполагается, что существует множество кортежей размерности k,имя которого REL.Такое множество мы называем набором связей. Каждый кортеж (е 1 , е 2 , ...,е k) в множествеRELподразумевает, что объекты е 1 , е 2 , ...,е k , где е i принадлежит набору E i , находятся в связи RELдруг с другом как группа. Наиболее общим, несомненно, является случай, когда k=2, но иногда списки состоят из трех или более наборов объектов.

Допустим, мы имеем набор объектов ЛЮДИ и связь ЯВЛЯЕТСЯ- МАТЕРЬЮ, список наборов объектов которой есть ЛЮДИ, ЛЮДИ. Мы предполагаем, что набор связей ЯВЛЯЕТСЯ-МАТЕРЬЮ включает все пары (p i ,р j), такие, что человек р i является матерью человека p j .

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

Понятия делятся на:

- События

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

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

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

Атрибуры

Комплексы признаков

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

В семантических сетях используются следующие отношения:

Элемент класса;

Атрибутные связи;

Значение свойства;

Пример элемента класса;

Связи типа «часть-целое»;

Функциональные связи, определяемые глаголами «производит», «влияет»;

Количественные (больше, меньше, равно …);

Пространственные (далеко от, близко от, за, под, над …);

Временные (раньше, позже, в течение…);

Логические связи (и, или, не) и др.

Минимальный состав отношений в семантической сети - это элемент класса, атрибутные связи и значение свойства.

На рис. 8 изображен пример семантической сети.

Рис. 8 Семантическая сеть, показывающая взаимоотношения птицы и самолета.

Проблема поиска решения в базе знаний типа семантической сети сводится к задаче поиска фрагмента сети или подсети, соответствующей поставленному вопросу.

Вывод знаний в сетевой модели

Для вывода знания события в сетевой модели делятся на исход­ные (признаки) и целевые (гипотезы).

Значения признаков предполагаются известными.

Все призна­ки, помимо присущих им значений: Истинно (Да) и Ложно (Нет) - имеют еще два стандартных значения: Пока неизвестно и Неизвестно. При задании последнего значения признак исключает­ся из рассмотрения. Значения исходных атрибутов либо выбирают­ся из определенного списка, либо вводятся извне. Объектами вывода в рассматриваемой модели являются гипоте­зы. К ним относятся рекомендации, диагнозы, прогнозы и другие решения, определяемые спецификой ПО. Условием вывода должно быть существование хотя бы одной гипотезы. В этом случае реше­нием является оценка ее истинности.

Виды семантических связей

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

Внелексические свойства СС выражаются через:

Rf - рефлексивность;

Nrf - нерефлексив­ность;

Arf - антирефлексивность (ни одной рефлексии);

Sm - симметричность;

Ns - несимметричность;

Ans - антисим­метричность (ни одной симметрии);

As - асимметричность (кон­текстное свойство - обращение связи дает иную связь из списка);

Тг - транзитивность;

Ntr - нетранзитивность.

Внелексические свойства семантических связей в суждениях проверяются следующим образом.

Относительно сочетания перечисленных свойств СС делятся на типы, представленные в (табл. 2.1.).

1. Рефлексивность определяется по критерию подстановки:

вме­сто объекта А подставляется объект В(АгВ -> ВгВ) и выбирается один из следующих ответов:

вполне возможно (тавтология) ~» Rf;

не исключено -> Nrf;

невозможно -> Arf.

Пример. Вегетативные расстройства сопровождаются вегета­тивными расстройствами. Ответ 1 для Com.

2. Симметричность определяется по критерию перестановки: объекты А и В меняются местами (АгВ -» ВгА) и выясняется спра­ведливость полученного предложения. При утвердительном ответе высказыванию приписывается свойство Sm, в противном слу­чае - свойство Ns.

Пример. Головная боль всегда сопровождается вегетативными расстройствами, и Вегетативные расстройства всегда сопровожда­ются головной болью. Ответ «Нет» для Com. Это соответствует свой­ству Ns. Свойство Ns уточняется на более сильные свойства: Ans и As. Первое имеет место для любых примеров анализируемой связи. Например, для связи Com имеет место свойство Ans.

Плюс модели: Легка в реализации.

Минус модели: Плохо структурирована – при большом количестве элементов можно запутаться, а при увеличении объема информации – может произоти комбинаторный взрыв.При создании любой вещи, любого изделия, любого произведения человек встает перед необходимостью неизбежного выбора среди огромного числа возможных вариантов. К чему при этом может привести простой перебор этих вариантов проследим на следующем явлении. Это явление известно в кибернетике под названием комбинаторный взрыв. Что это за "зверь" нетрудно продемонстрировать на простом примере. Допустим, что имеется некий алфавит, состоящий всего из 10 символов (букв).

Из такого алфавита можно составить 10^^100 текстов длиной по 100 букв. Гипотетический компьютер, обладающий возможностью обрабатывать 10^^18 таких текстов в секунду, потратит на общий анализ всех текстов 10^^74 лет. Для сравнения – по современным космогоническим представлениям с момента Большого взрыва исследованной части Вселенной прошло ~10^^10 лет.

Строгого, единого определения для понятия «система» в на­стоящее время нет. В качестве «рабочего» определения в литера­туре под системой в общем случае понимается совокупность эле­ментов и связей между ними, обладающая определенной целост­ностью.

Рассматривая систему относительно построения ИС, более полно это определение можно пояснить на основе понятия мо­дели.

Пусть А и В - два произвольных множества. Функция f, одно­значно ставящая в соответствие каждому элементу элемент f(а) В, называется отображением множества А в множество В и обозначается как f: АВ.

Элемент f(а)=b называется значением элемента а при ото­бражении f, или образом а; А - область определения, В - область значений отображения f.

Если есть элементы , не являющиеся образом никакихэлементов , то отображение f называется отображением «в» в В.

Если f(А) = В, то отображение f называется отображением «на» В.

Функция - множество элементов из А, образы которых принадлежат В, называется прообразом множества В, то есть

В общем случае может не быть отображением «в» или «на» А, так как функция может быть неоднозначной.

Отображение f называется взаимно однозначным, если каж­дый элемент множества В является образом не более чем одного элемента из А. Отображение f множества А на (в) В называется гомоморфиз­мом множеств, если выполняется условие (а 1 , а 2 , ... , a n) f (а 1 ,), f (а 2 ,) f (а 3 ,) f (а 4 ,) ..... f (а n ,), где

Изоморфизм множества А на В является взаимно однознач­ным гомоморфизмом, т. е. (a 1 , а 2 ,.. , a k) А <=> (f (а 1 ,) f (а 2)..,

Введенные понятия позволяют определить модель как изомор­физм А в , где А - множество фиксированных элементов пред­метной области с исследуемыми связями, отношениями между эти­ми элементами, - абстрактное множество, задаваемое кортежем

=<{M}, P 1 ,Р 2 ,…, Р n > , (1)

{M} – множество элементов модели, соответствующих элементам предметной области, называемое носителем модели;

Р 1 , Р 2 ,..., Р n - предикаты, отображающие наличие того или иного отношения между элементами предметной области.

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

Носитель модели является содержательной областью преди­катов Р 1, Р 2 ,...,Р n . Предикаты называются сигнатурой модели .

Выбор носителя и сигнатуры при построении модели опреде­ляется предметом исследования.

Уточним теперь понятие системы, ориентированное на зада­чи декомпозиции, анализа и синтеза, то есть на проведение преобра­зования между двумя подмоделями.

Системой называется кортеж

S = < >. (2)

Подмодель, определяющая поведение системы. Иногда эта подмодель может рассматриваться как «черный ящик», о котором известно лишь то, что на определенные воздействия он реагирует опреде­ленным образом;

Подмодель, определяющая структуру системы при ее внутреннем рассмотрении;

Предикат целостности, определяющий назначение системы, семантику (смысл) моделей и , а также семантику преобразования

1, если преобразование существует при взаимно однозначном соответствии между элементами носите­лей моделей и , в противном случае = 0. Наличие предиката целостности позволяет говорить о том, что система - это семантическая модель, имеющая внутреннюю интерпретацию.

Подмодель может быть представлена в виде кортежа, вклю­чающего пять объектов:

х = x(t) - входной сигнал, то есть конечное множество функций времени t: <х 0 (0, ..., x k (t)>;

у = y(t) - выходной сигнал, представляющий собой конечное множе­ство функций у = < y 1 ..., у n >;

z= z(t) - переменная состояния модели , также характеризующаяся конечным множеством функций z= < z 1 (t)…z n (t) >, знание которых в заданный момент времени позволяет определить значения выходных характеристик модели – функционалы (глобальные уравнения системы), задающие текущие значения выходного сигнала у(t) и внутреннего состояния z(t)

y(t) = g(z(t),x(t)); (4)

z(t) = f(z(t 0), x(τ)), τ . (5)

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

Кроме выражения (2) систему задают тремя аксиомами.

Аксиома 1. Для системы определены пространство состо­яний Z, в которых может находиться система, и параметрическое пространство Т, в котором задано поведение системы.

В связи с этим математические описания вида (3) приня­то называть динамическими системами, так как они отражают способность систем изменять состояния z (t) в параметрическом пространстве Т.

В отличие от динамических статические сис­темы таким свойством не обладают. В качестве параметрического пространства обычно рассматривается временной интер­вал от нуля до бесконечности.

Аксиома 2 . Пространство состояний Z содержит не менее двух элементов. Эта аксиома отражает естественное представле­ние о том, что сложная система может находиться в разных со­стояниях.

Аксиома 3 . Система обладает свойством функциональной эмерджентности.

Эмерджентностъ (целостность) - это такое свойство систе­мы S, которое принципиально не сводится к сумме свойств эле­ментов, составляющих систему, и не выводится из них:

где: - i-я характеристика системы S; т - общее количество характеристик.

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

В рамках изучаемой дисциплины под сложной кибернетичес­кой системой понимается реальный объект с управлением и его отображение в сознании исследователя как совокупность моде­лей, адекватная решаемой задаче.

Упражнения

1. Опишите в виде черного ящика известный Вам бытовой прибор.

2. Рассмотрите примеры функционирования известной Вам системы.

3. Докажите системность дерева, Солнечной системы, озера и других объектов.

Литература:

1. Богданов А.А. Всеобщая организационная наука (тектология)/ в 3 т. - М., 1905-1924

2. Винер Н. Кибернетика. М.: Сов. радио. 1968.

3. Пригожин И., Стенгерс И. Порядок из хаоса. М.: Прогресс, 1986.

4. Уемов А.И. Системный подход и общая теория систем. М.: Мысль, 1978

5. Шэннон Р. Имитационное моделирование систем искусство и наука. М.: Мир, 1978

Нормализация

Основная статья: Нормальная форма

При проектировании реляционных баз данных обычно выполняется так называемая нормализация.

Модели «сущность-связь»

Основная статья: ER-модель данных

Модель «сущность-связь» (англ. “Entity-Relationship model” ), или ER-модель, предложенная П. Ченом в 1976 г., является наиболее известным представителем класса семантических (концептуальных, инфологических) моделей предметной области. ER-модель обычно представляется в графической форме, с использованием оригинальной нотации П. Чена, называемой ER-диаграмма , либо с использованием других графических нотаций (Crow"s Foot , Information Engineering и др.).

Основные преимущества ER-моделей:

· наглядность;

· модели позволяют проектировать базы данных с большим количеством объектов и атрибутов;

· ER-модели реализованы во многих системах автоматизированного проектирования баз данных (например, ERWin).

Основные элементы ER-моделей:

· объекты (сущности);

· атрибуты объектов;

· связи между объектами.

Сущность - объект предметной области, имеющий атрибуты.

Связь между сущностями характеризуется:

· типом связи (1:1, 1:N, N:М);

· классом принадлежности. Класс может быть обязательным и необязательным. Если каждый экземпляр сущности участвует в связи, то класс принадлежности - обязательный, иначе - необязательный.

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

Семантическое моделирование стало предметом интенсивных исследований с конца 1970-х годов. Основным побудительным мотивом подобных исследований (т.е. проблемой, которую пытались разрешить исследователи) был следующий факт. Дело в том, что системы баз данных обычно обладают весьма ограниченными сведениями о смысле хранящихся в них данных. Чаще всего они позволяют лишь манипулировать данными определенных простых типов и определяют некоторые простейшие ограничения целостности, наложенные на эти данные. Любая более сложная интерпретация возлагается на пользователя. Однако было бы замечательно, если бы системы могли обладать немного более широким объемом сведений и несколько интеллектуальнее отвечать на запросы пользователя, а также поддерживать более сложные (т.е. более высокоуровневые) интерфейсы пользователя.
[…]
Идеи семантического моделирования могут быть полезны как средство проектирования базы данных даже при отсутствии их непосредственной поддержки в СУБД.

Наиболее известным представителем класса семантических моделей является модель «сущность-связь» (ER-модель).