WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 11 |
В.Г. МОКРОЗУБ ГРАФОВЫЕ СТРУКТУРЫ И РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ В АВТОМАТИЗИРОВАННЫХ ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ Москва Издательский дом "Спектр" 2011 Научное издание МОКРОЗУБ Владимир Григорьевич ГРАФОВЫЕ СТРУКТУРЫ И РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ В АВТОМАТИЗИРОВАННЫХ ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ Редактор Л.В. К о м б а р о в а Инженер по компьютерному макетированию И.В. Е в с е е в а Сдано в набор 22.11.2011 г. Подписано в печать 22.11.2011 г.

Формат 60 84/16. Бумага офсетная. Гарнитура Times New Roman Усл. печ. л. 6,27. Уч.-изд. л. 6,75 Тираж 400 экз. Заказ № 515 ООО "Издательский дом "Спектр", 119048, Москва, ул. Усачева, д. 35, стр. 1 Нttp://www.idspektr.ru. E-mail: idspektr@rambler.ru Подготовлено к печати и отпечатано в Издательско-полиграфическом центре ФГБОУ ВПО "ТГТУ" 392000, г. Тамбов, ул. Советская, д. 106, к. 14 По вопросам приобретения книги обращаться по телефону 8(4752)638108 E-mail: izdatelstvo@admin.tstu.ru В.Г. МОКРОЗУБ ГРАФОВЫЕ СТРУКТУРЫ И РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ В АВТОМАТИЗИРОВАННЫХ ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ Москва, 2011 1 УДК 681.142(075.8) ББК 32.973я73 М168 Р е ц е н з е н т ы :

Доктор технических наук, профессор, заведующий кафедрой компьютерно-интегрированных систем в химической технологии Российского химико-технологического университета им. Д.И. Менделеева В.Ф. Егоров Доктор технических наук, профессор, проректор по информатизации ФГБОУ ВПО "ТГТУ" В.Е. Подольский Мокрозуб В.Г.

М168 Графовые структуры и реляционные базы данных в автомати- зированных интеллектуальных информационных системах. – М.:

Издательский дом "Спектр", 2011. – 108 с. – 400 экз. – ISBN 978-5-904270-89-6.

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

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

УДК 681.142(075.8) ББК 32.973яISBN 978-5-904270-89-6 © Мокрозуб В.Г., ВВЕДЕНИЕ Современное общество невозможно представить без развитых информационных технологий, которые используются в настоящее время практически во всех областях человеческой деятельности. Эти технологии объединяют в себе знания и труд специалистов как в области самих информационных технологий, так и в тех областях, в которых они используются (медицина, обучение, техника и др.).

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

Интеллектуализация информационных систем требует развития:

- подходов к описанию знаний специалистов;

- способов представления и обработки этих знаний в информационных системах;

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

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

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

Математическое обеспечение базируется на представлении объектов различной природы гиперграфами. В качестве базового программного обеспечения приняты реляционные базы данных.

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

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

Во втором разделе описываются операции над N-ориентированными гиперграфами в реляционной базе данных: добавление новой вершины, добавление нового ребра, удаление вершины и удаление ребра. Для указанных операций представлены запросы на языке SQL, позволяющие выполнять их, не нарушая целостность базы данных.

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



Четвертый раздел посвящен описанию способов разработки интерфейса пользователя, который не знает язык структурированных запросов (SQL), с реляционной базой данных. Подобный интерфейс необходим, как для ввода правил, например, размещения объекта, так и для составления обращения (запроса) к информационной системе.

В пятом разделе описывается применение N-ориентированных гиперграфов для структурного и параметрического синтеза технических систем. Исходными данными для структурного синтеза являются функции системы, заданные в техническом задании на создании объекта. Приведена классификация правил в зависимости от операции, например, ребро вводится в граф, вершина добавляется в ребро и др.

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

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

Работа выполнена в рамках федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009 – 2013 гг.

1. ГРАФЫ С ОГРАНИЧЕНИЯМИ И ИХ ПРЕДСТАВЛНИЕ В ИНФОРМАЦИОННЫХ СИСТЕМАХ Графы, теория и методы, основанные на графах, часто применяются в автоматизированных системах. В работах Овчинникова В.А., Ивано- вой Г.А., Батищева Д.И., Старостина Н.В. для моделирования и синтеза сложных структур предложены методы, основанные на графах, гиперграфах и ультраграфах.

В [7] представлены графовые модели задач структурного синтеза.

В работе [8] описаны представления графов, мультиграфов, неориентированных и ориентированных гипер- и ультраграфов матрицами смежности и инцидентности. В [27] предлагается единый подход к определению понятий ультра-, гипер- и обыкновенных графов. Приведены формальные правила, связывающие матричное и аналитическое представления для каждого вида графов, а также выражения для оценки характеристик компонент графа. Для представления дополнительной информации в [1] на вершинах и гиперребрах гиперграфа задается множество атрибутов. Для формализованного представления свойств множества и его элементов Павловым В.В. разработан аппарат теории полихроматических множеств и графов [29 – 31]. Применение многодольных графов для решения задач структурного синтеза на элементах с ограниченной сочетаемостью представлено в [3]. В [1] подробно представлены методы декомпозиции гиперграфовых структур, в [28] описаны операции над ультра- и гиперграфами, представленными в аналитическом виде.

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

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

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

1.1. ПРОСТЫЕ ОРИЕНТИРОВАННЫЕ ГРАФЫ Обозначим простой граф Go(X, U ), где X = {xi}, i = 1, I – множество вершин графа, xi – i-я вершина графа; U = {um(xi, xj )}, m = 1, M, i =1, I, j = 1, I – множество ребер графа, um (xi, x ) – m-е ребро графа, j соединяющее вершины xi и x.

j Ребро, соединяющее вершину саму с собой, um (xk, xk ), m 1, M, k 1, I, называется петлей. Простой граф не будет иметь петель, если выполняется ограничение O1 : ¬um(xk, хk ) U; m = 1, M ; k = 1, I.

Если две вершины могут иметь несколько связывающих их ребер, то такой граф называется мультиграфом. Таким образом, простой граф не будет мультиграфом, если выполняется ограничение O : um(xi, x ) U; m = 1, M ; i 1, I; j 1, I j ¬ul (xi, х ) U; l m; l 1, M.

j Граф называется ориентированным, если ребро имеет направление, например от xi (вершина-источник) к x (вершина-приемник). Если j вершина-приемник связана только одним ребром с только одной вершиной-источником, то такой граф называется направленным деревом.

Введем ограничение O3 – вершина-приемник связана только с одной вершиной-источником (ограничения на число связей нет) O3 : um(xi, x ) U; m 1, M ; i 1, I; j 1, I j ¬un(xk, хj ) U; m n; i k; n 1, M ; k 1, I.





С учетом введенных ограничений граф будет направленным деревом, если одновременно выполняются условия O1, O2, O3.

На рисунке 1.1 представлены примеры простых ориентированных графов.

Добавим к классическому обозначению графа G(X, U ) перечисленные выше ограничения. С учетом ограничений графы на рис. 1.1 формально можно представить следующим образом:

- G(X, U, O1 O2 O3) – рис. 1.1, a;

- G(X, U, O1 O3) – рис. 1.1, б;

- G(X, U, O1 O2) – рис. 1.1, в;

- G(X, U, O1) – рис. 1.1, г;

- G(X, U, O1 O2) – рис. 1.1, д.

xxxu1 uu1 uu1 uuu3 xxxxx2 xа) б) в) uu1 x2 xxuu1 ux1 uuux2 uxxxг) д) Рис. 1.1. Примеры ориентированных графов Реляционная база данных (РБД) BDо, описывающая графы на рис. 1.1, представляет собой кортеж:

ВDо=, где X,U,G – следующие отношения, X – вершины графа, U – ребра графа, G – граф (связи вершин и ребер).

В свою очередь отношения X,U,G можно представить как:

X={PK_ID_X, ID_X, Наименование_вершины}, где PK_ID_X – первичный ключ, ID_X – поле первичного ключа;

U={PK_ID_U, ID_U, Наименование_связи}, где PK_ID_U – первичный ключ, ID_U – поле первичного ключа;

G={PK_ID_G, FK_ID_U, FK_ID_XI, FK_ID_XJ, ID_G, ID_U, ID_XI, ID_XJ}, где PK_ID_G – первичный ключ, FK_IDU, FK_ID_XI, FK_ID_XJ – внешние ключи (по полям ID_U, ID_XI, ID_XJ), ID_G – поле первичного ключа, ID_XI, ID_XJ – поля первичного ключа вершины-источника и вершины-приемника.

Так как ребро в графе всегда уникально, то нет необходимости вводить отношение U, достаточно в отношении G добавить поле Наименование_связи. Тогда база данных, описывающая графы, представленные на рис. 1.1, описывается двумя отношениями ВDо=, где X={PK_ID_X, ID_X, Наименование_вершины}, G={PK_ID_G, FK_ID_XI, FK_ID_XJ, ID_G,ID_XI, ID_XJ, Наименование_связи}.

Схема данных этой базы представлена на рис. 1.2.

G X FK_G_XI ID_G ID_X ID_XI Наименование_вер- шины ID_XJ FK_G_XJ Наименование_ребра Рис. 1.2. Схема данных базы, описывающей ориентированные графы Описанная база данных не включает ограничения O1, O2, O3. Внешние ключи FK_ID_XI, FK_ID_XJ гарантируют ссылочную целостность базы, т.е в таблице G не будет значений ID_XI и ID_XJ, не входящих в домен ID_X таблицы X. Ограничения O1, O2, O3 относятся к доменной целостности базы данных. Рассмотрим представление этих ограничений в базе данных BDо.

Проверка доменной целостности в РБД может осуществляться при выполнении операций удаления, редактирования и добавления записей.

Ограничение O1 – граф не должен иметь петель. Это означает, что в отношении G не может быть записи, у которой G.ID_XJ=G.ID_XI. Это ограничение может быть добавлено к BDо следующим выражением:

alter table G add constraint CK_O1 check (ID_XI<>ID_IG) (1.1) Ограничение O2 – граф не является мультиграфом. Это ограничение может быть добавлено двумя способами:

а) добавлением к отношению G уникального индекса по полям ID_XI и ID_XJ:

create unique index IX_O2 on G (ID_XI, ID_XJ); (1.2) б) проверкой истинности условия:

(not exists (select * from G where G.ID_XI=@ID_XI and G.ID_XJ = @ID_XJ )), (1.3) где @ID_XI, @ID_XJ – значения G.ID_XI и G.ID_XJ добавляемой записи (или новые значения редактируемой записи).

Ограничение O3 – вершина-приемник связана только с одной вершиной-источником (ограничения на число связей нет). Это ограничение может быть нарушено при добавлении или редактировании записи. Ограничение О3 не будет нарушено если:

– добавляется ребро с вершиной приемником, у которой нет связей;

– связываются две вершины, у которых уже есть связь.

Обозначим @ID_XI, @ID_XJ – значения G.ID_XI и G.ID_XJ добавляемой записи (или новые значения редактируемой записи). Тогда ограничение O3 не будет нарушено, если истинно выражение:

(not exists (select * from G where G.ID_XJ=@ID_XJ)) or (exists (select * from G where G.ID_XI=@ID_XI (1.4) and G.ID_XJ = @ID_XJ ) Выражения (1.1) и (1.2) создают отдельные объекты РБД, а именно CK_O1, IX_O2. Выражения (1.3) и (1.4) могут проверять тригеры.

Обозначим тригеры, проверяющие выражения (1.3) и (1,4), как TR_O2 и TR_O3.

Обозначим G1={PK_ID_G, FK_ID_U, FK_ID_XI, FK_ID_XJ, ID_G, ID_U, ID_XI, ID_XJ}. Тогда с учетом ограничений таблица G для графов, представленных на рис. 1.1 будет выглядеть следующим образом:

- G={G1, CK_O1, IX_O2 или TR_O2, TR_O3} – рис. 1.1, a;

- G={G1, CK_O1, TR_O3} – рис. 1.1, б;

- G={G1, CK_O1, IX_O2 или TR_O2} – рис. 1.1, в;

- G={G1, CK_O1} – рис. 1, г;

- G={G1, CK_O1, IX_O2 или TR_O2} – рис. 1.1, д.

1.2. НЕОРИЕНТИРОВАННЫЕ ГИПЕРГРАФЫ С ОГРАНИЧЕНИЯМИ Обозначим гиперграф Gg (X, U ), где X = {xi}, i = 1, I – множество вершин гиперграфа, xi – i-я вершина; U = {um (Ym )}, m = 1, M – множество ребер гиперграфа, um(Ym) – m-е ребро гиперграфа, Ym – множество вершин, инцидентных m-му ребру Ym X, Ym = {xk}, k Km, Km 1, I.

При этом два множества вершин равны Ym = Yn, если у них одинаковое число элементов, т.е. равны их мощности Ym = Yn, и для любого элемента xk Ym, k 1, I во множестве Yn существует точно такой же элемент. Например, множества {x1, x5, x3} и {x3, x1, x5} равны.

Примеры неориентированных гиперграфов представлены на рис. 1.3.

uux1 x2 x3 xx5 xа) uuuuб) x7 xx1 x2 x3 xux5 xuв) x1 x2 x3 xuxu3 xРис. 1.3. Примеры неориентированных гиперграфов Два ребра, имеющие одинаковые вершины, называются смежными.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 11 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.