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

На правах рукописи

ХТЕТ МИН ПЬЮ

РАЗРАБОТКА ГРАФОВЫХ БАЗ ДАННЫХ ДЛЯ УСКОРЕНИЯ ОПЕРАЦИИ ВЫБОРКИ В АВТОМАТИЗИРОВАННЫХ СИСТЕМАХ УПРАВЛЕНИЯ

ПРОИЗВОДСТВОМ

Специальность: 05.13.06 — "Автоматизация и управление технологическими процессами и производствами" (в приборостроении)

Автореферат

- 8 ИЮЛ 2015

диссертации на соискание ученой степени кандидата технических наук

Москва - 2015 г.

005570414

005570414

Работа выполнена на кафедре «Информатики и программного обеспечения вычислительных систем» Национального исследовательского университета «МИЭТ»

Научный руководитель: Гагарина Лариса Геннадьевна

доктор технических наук, профессор, заведующий кафедрой «ИПОВС» НИУ МИЭТ

Официальные оппоненты: Черников Борис Васильевич

доктор технических наук, старший научный сотрудник, заместитель директора Центра информационных технологий ООО "Газпром ВНИИГАЗ"

Федоров Алексей Роапъдович кандидат технических наук, директор ООО «Радис РРЛ»

Ведущая организация; Открытое акционерное общество научно-

производственный центр «Электронные вычислительно-информационные системы» (ОАО НПЦ «ЭЛВИС»)

Защита диссертации состоится «fQ/®^ 2015 г. в^ч.^1' мин. на заседании диссертационного совета Д 212.134^04 при Национальном исследовательском университете «МИЭТ» по адресу: 124498 Москва, Зеленоград, площадь Шокина.д.1.

С диссертацией можно ознакомиться в библиотеке МИЭТ и на сайте http://miet.ru/.

Автореферат разослан «_1_»_ ОЯ~_2015 г.

Ученый секретарь диссертационного совета

д.т.н., профессор : /?': Z А' И. Погалов

Общая характеристика работы

Актуальность проблемы. В настоящее время успешное функционирование автоматизированных систем управления производством (АСУП) и автоматизированных систем управления технологическими процессами производства (АСУТП) возможно трлько с применением интегрированной информационной среды (ИИС), базирующейся на использовании информационного обеспечения и сопровождения жизненного цикла изделий (ЖЦИ) с помощью, так называемых CALS'-технологий. При этом сама ИИС обеспечивает процесс комплексной автоматизации производства, корректность, актуальность, сохранность и доступность данных субъектам производственной деятельности и представляет собой совокупность распределенных баз данных, содержащих сведения об изделиях и их параметрах, производственных мощностях, ресурсах и процессах. Такие данные характеризуются сложностью организации, большим количеством элементов, высокой степенью их связности, многоуровневыми структурами иерархической вложенности и детализации. Это, с одной стороны, дает возможность повысить эффективность управляемых объектов, значительно снизив затраты на их создание и эксплуатацию, уменьшив их габариты, массу, потребляемую мощность, с другой же, приводит к совершенно новым проблемам, связанным с порчей, утратой и уничтожением нормативной, производственной и технологической информации о ЖЦИ.

Исследованиям в области комплексной автоматизации с помощью CALS-технологий посвящен ряд работ зарубежных специалистов Уйэла Н., Michael A. Rossi, Mark S. Dopfman, G. Rejda, S. Breidenbach, а также отечественных ученых Прохорова Н.Л., Рейзмана Я.А., Бондаревского A.C., Панасенко С.П. и др. Однако все они связаны с изучением отдельных аспектов автоматизации, а вышеуказанная проблема остается довольно слабоизученной в силу следующих причин.

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

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

Таким образом, проблема повышения быстродействия выборки иерархических данных в СУБД, применяемых при автоматизации и управлении технологическими

1 CALS-технологии (от англ. Continuous Acquisition and Lifecycle Support — непрерывная информационная поддержка поставок и жизненного цикла изделий), или ИПИ (информационная поддержка процессов жизненного цикла изделий) — подход к проектированию и производству высокотехнологичной и наукоемкой продукции, заключающийся в использовании компьютерной техники и информационных технологий на всех стадиях жизненного цикла изделия

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

Целью диссертации является повышение эффективности информационной поддержки и сопровождения ЖЦИ в интегрированной информационной среде АСУП/АСУТП за счет разработки и программной реализации методики и алгоритма повышения быстродействия выборки иерархических данных в СУБД на основе графовой модели данных.

Для достижения поставленной цели в работе решаются следующие основные задачи:

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

2. Формализация оценки эффективности организации иерархических данных с точки зрения быстродействия их выборки.

3. Разработка методики повышения быстродействия выборки иерархических данных в СУБД на основе графовой модели данных.

4. Разработка алгоритма преобразования схемы данных для повышения быстродействия выборки в СУБД на основе графовой модели данных.

5. Программная реализация предложенной методики и алгоритма повышения быстродействия выборки иерархических данных в СУБД в виде комплекса программных средств.

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

Предмет исследования составляют методы повышения эффективности специализированного информационного обеспечения АСУП/АСУТП.

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

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

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

1. На основе анализа базовых процессов функционирования современных АСУП /АСУТП определены требования к быстродействию СУБД информационного обеспечения и сопровождении ЖЦИ при непрерывном росте сложности изделий и увеличении сложности структур данных и степени связанности элементов данных.

2. Предложена методика повышения быстродействия выборки иерархических данных об изделии с использованием СУБД на основе графовой модели данных.

3. Разработано формализованное представление оценки эффективности организации иерархических данных с точки зрения быстродействия их выборки.

4. Предложен алгоритм преобразования схемы данных для повышения быстродействия выборки в СУБД на основе графовой модели данных.

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

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

Практическая ценность работы заключается в том, что основные положения, выводы и рекомендации диссертации ориентированы на широкое применение методики повышения быстродействия выборки иерархических данных в СУБД АСУП/АСУТП в области микроэлектроники, приборостроения и других высокотехнологичных отраслей промышленности. Результаты исследования доведены до конкретных алгоритмов, методики и программной реализации.

Самостоятельное практическое значение имеют:

• методика повышения быстродействия выборки иерархических данных в СУБД на основе графовой модели данных;

• алгоритм преобразования схемы данных для повышения быстродействия выборки в СУБД на основе графовой модели данных;

• верификация методики повышения быстродействия выборки иерархических данных в СУБД на основе графовой модели данных;

• программная реализация методики и алгоритма преобразования схемы данных для повышения быстродействия выборки в СУБД на основе графовой модели данных.

Практическая значимость подтверждена актами внедрения результатов диссертационной работы в учебном процессе МИЭТ и в НИР.

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

1. Исследованы базовые процессы функционирования современных АСУП/ АСУТП; выработаны требования к быстродействию СУБД для информационного обеспечения и сопровождения ЖЦИ при непрерывном росте сложности изделий и увеличении сложности структур данных и степени связанности элементов данных.

2. Разработана методика повышения быстродействия выборки иерархических данных в СУБД на основе графовой модели данных.

3. Разработано формализованное представление оценки эффективности организации иерархических данных сточки зрения быстродействия их выборки.

4. Предложен алгоритм преобразования схемы данных для повышения быстродействия выборки в СУБД на основе графовой модели данных.

5. Осуществлена программная реализация методики и алгоритмов повышения быстродействия выборки иерархических данных в СУБД в виде комплекса программных средств, внедрение которого практически подтвердило повышение быстродействия выборки данных о составе изделия более чем в 3 раза.

Реализация полученных результатов. Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры "Информатика и программное обеспечение вычислительных систем» Национального исследовательского университета «МИЭТ» и являлась составной частью исследовательских мероприятий в рамках НИР 59-ИПП «Разработка основ теории, принципов построения и алгоритмов работы высоконадежных систем управления силовыми агрегатами».

Все работы по разработке и реализации методики и алгоритма преобразования схемы данных для повышения быстродействия выборки иерархических данных в СУБД на основе графовой модели данных проводились под руководством или при непосредственном участии автора. Результаты диссертационной работы используются в учебном процессе кафедры ИПОВС в материалах курсов "Управление программными проектами", "Проектирование и архитектура программных систем", "Методология программной инженерии", НИР «Разработка основ теории, принципов построения и алгоритмов работы высоконадежных систем управления силовыми агрегатами», шифр 59-ИПП.

В результате проведенных исследований получены и выносятся на защиту следующие основные научные результаты:

1. Методика повышения быстродействия выборки иерархических данных в СУБД на основе графовой модели данных.

2. Формализованное представление оценки эффективности организации иерархических данных с точки зрения быстродействия их выборки.

3. Алгоритм преобразования схемы данных для повышения быстродействия выборки в СУБД на основе графовой модели данных.

4. Программная реализация методики и алгоритмов повышения быстродействия выборки иерархических данных в СУБД в виде комплекса программных средств.

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

1. Микроэлектроника и информатика - 2011. 18-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ, 2011.

2. Актуальные проблемы информатизации в науке, образовании и экономике -2011. 4-я Всероссийская межвузовская научно - практическая конференция. МИЭТ, 2011

3. Микроэлектроника и информатика - 2012. 19-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ, 2012.

4. Молодежь и наука. 15-я Международная телекоммуникационная конференция молодых ученых и студентов. НИЯУ МИФИ, 2012.

5. Микроэлектроника и информатика - 2013. 20-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ, 2013.

6. Современные вопросы науки и образования - 21век. Международная заочная научно-практическая конференция. Тамбов, 2012.

Публикации. По материалам диссертации опубликовано семь тезисов докладов и три статьи в журналах, входящих в перечень ВАК. Подана заявка на регистрацию программы для ЭВМ "Программное средство повышения быстродействия выборки иерархических данных в СУБД".

Структура и объём диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 127 страниц основного текста, включая 28 рисунков, 5 таблиц, а также список литературы из 60 наименований и 2 приложения.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проводится анализ современного состояния проблемы реализации информационного обеспечения и сопровождения ЖЦИ в АСУП/АСУТП.

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

Таким образом, интегрированная информационная среда АСУП/АСУТП должна реализовывать как хранение всеобъемлющей информации о всех аспектах ЖЦИ, так и механизмы (способы) передачи данных и разрешения конфликтов.

Средством обеспечения информационной интеграции в ИИС процессов ЖЦИ являются САЬЗ-технологии, направленные на обеспечение безбумажной поддержки жизненного цикла продукта от маркетинга до утилизации, для проектирования, анализа и реинжиниринга бизнес-процессов, связанных с обеспечением качества продукции.

Использование САЬЗ-технологий в АСУП/АСУТП возможно только при наличии БТЕР^информации об изделии, т.е. набора данных, которые используются в процессе

2 STEP_(от англ. STandard for Exchange of Product model data — стандарт обмена данными модели изделия)

_совокупность стандартов ISO 10303; позволяет описать весь жизненный цикл изделия, включая технологию

изготовления и контроль качества продукции

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

В таком случае, ИИС представляет собой хранилище данных, содержащее сведения, создаваемые и используемые всеми подразделениями и службами предприятия - участниками ЖЦИ в процессе их производственной деятельности, а также общую базу данных об изделии (ОБДИ). С ОБДИ связаны процессы на всех стадиях ЖЦИ. (рис. 1)

Маркегинг, определение требований к изде.

Упразление проектом

и)Д(Ли* * мглронмои форм*

;*« ируктуро: я сосг (конфигурация}

Проектировочные расчеты и моделирован;

Проверочные оасчеты и моделирование

Соэдан-ие геометрической модели издел:

Электроинав дсталмро

Коктроле-^аа сборча (промрка ж-формационг«

Разработка маршрутной и олеэациоп*

Разработка технологи» сборки и монтажа

Разработка технологии контроля и испытаний

Оперативно-календарное планирование

Закупка материалов и комплеитующи»

Рисунок 1. Общая база данных об изделиях в структуре ИИС

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

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

Таким образом, в процессе аналитического обзора исследованы базовые процессы

информационного сопровождения ЖЦИ, определена проблема повышения требований к возможностям СУБД и ОБДИ при непрерывном росте сложности изделий и степени их связанности.

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

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

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

Таким образом, задачу хранения информации об изделии можно рассматривать как

задачу хранения иерархического графа G - (V, Е) (набора иерархических графов).

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

Несмотря на преимущества XML-файлов (традиционное представление данных для восприятия человеком; обработка данных посредством любого языка программирования; платформенная независимость данных; необязательность лицензирования; гибкость описания данных, в том числе графов; объединение описания структуры и содержимого) в области решения поставленных задач существуют ограничения их использования такие, как:

• размер XML-документа существенно больше бинарного представления;

• время обработки массивного XML-графа значительно больше времени обработки графа с помощью вновь созданной специализированной СУБД.

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

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

Тем не менее, реляционная БД зачастую уступает навигационным в скорости

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

Рассмотрим процессы манипулирования иерархическими данными в реляционных

БД.

Простейший способ хранения графа-дерева в одной таблице формально представим отношением:

^ узла ' С1XVузла ' родителя ^

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

< ¡¿уыа'МГу,»^' родителя ' потомка ^

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

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

• хранение вместо идентификатора «родителя» последовательного списка всех «предков»;

• добавление атрибутов обхода дерева (только для иерархического графа);

• добавление отношения, хранящего все пути, содержащиеся в графе (начальная вершина, конечная вершина).

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

Сравнительный анализ известных способов организации иерархических данных в

реляционной БД _Таблица 1

Подход

Преимущества Недостатки

^ = (Ык,{уг}к,Ык„аг>

• Автоматическая поддержка • Необходимость использования

ссылочной целостности. сложных рекурсивных запросов.

• Простота добавления нового

- узла.

V* = (Ык,{уг}к, -^Экраго'Юкрагь)

• Простота запросов с предками и • Необходимость дополнительных

потомками. средств поддержания целостности.

• Простота удаления промежуточных узлов. • Простота манипуляций с поддеревьями. • Сложность манипулирования с отдельными узлами.

V„ = ({vJbWfUE™ = ({v.^.iv,}^)

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

Vw = ({v,}Vf{vfUPni = <{v,}k,.{v,}„,>

• Возможность хранения пересекающихся деревьев. • Простота запросов со списками предков и потомков. • Необходимость хранения и заполнения дополнительной таблицы.

В таблице: V- количество вершин в графе, Е - количество ребер.

Представим объект в виде совокупности его свойств - хранимых в БД атрибутов:

Vk = CvJ Ijcv,}

Логическая связь между объектами:

Ещ = ({Vi}ml.{Vi}m2)

Путь в графе между объектами:

Pm = ((ViU, Ыт2)

Известны новые, так называемые NoSQL-подходы, к организации хранимых в БД данных. Не являясь абсолютной заменой реляционной модели, новые модели данных ориентированы на преодоление ограничений реляционной модели. В диссертационной работе рассмотрены преимущества трех из них в рамках указанных NoSQL-подходов.

Первая модель «ключ - значение» (Key - value store), в отличие от реляционной модели, которая плохо поддается масштабированию, позволяет легко масштабировать БД за счет использования простой универсальной схемы, ограничивающей сложность выполняемых запросов, тем самым предоставляя широкие возможности для увеличения быстродействия обработки данных. В связи с тем, что указанная модель ориентирована на работу с записями, т. е. вся информация, относящаяся к данной записи, хранится вместе с ней, домен может содержать практически неограниченное количество различных записей. Это приводит к избыточному хранению данных, что позволяет все связанные данные хранить в одном месте, в то время как при использовании реляционной БД потребовалось бы использовать соединения таблиц, чтобы собрать нужную информацию. Исключение необходимости соединения таблиц улучшает масштабируемость данных. На вышеизложенных принципах построены системы BerkeleyDB, MemcacheDB, Amazon DynamoDB.

Вторая модель - «колоночные данные» (Column oriented data), - использует

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

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

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

В диссертации предложен новый подход решения означенной проблемы -совместное использование реляционной и графовой СУБД с применением разработанной в ходе исследования и представленной в главе 3 методики повышения быстродействия выборки иерархических данных.

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

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

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

Время выборки данных из БД в общем случае пропорционально количеству запрашиваемых строк (для реляционной модели) или узлов (для графовой модели). Для выборки некоторой иерархической структуры из БД имеем:

T~K = l + K1 + K2 + -+KL=l + Zh=1Kl, где Т- время выполнения запроса, К, - количество строк на данном уровне иерархии, L - количество уровней иерархии.

После определения среднего количества узлов нижнего уровня а;, связанных с

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

Точная оценка для реляционной БД (РБД) имеет вид:

Трел-оц = 1 +И{"=1.(П}=1а)).

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

т2 _ VI. ,1 'рел-оц ^1=0 а ■

По аналогии, точная оценка для графовой БД (ГБД) имеет вид:

Т^оц^ + пЕиП^а)).

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

ТГр-оц= И-пЕ^а1.

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

Тогда степень эффективности применения дополнительной графовой БД (рис. 2). выражается отношением:

Рел 1 = 1\| = 1 /' 1 = 0 _

Интегрированйая информационная среда систем управления производстом

V, = {»()* УК)к Ет = (у,}т2)

Рисунок 2. Применение дополнительной графовой БД для увеличения быстродействия операций с данными в ИИС

На основе приближенных оценок времени выполнения запросов Тр2ел_0Ц И ТТ2р-оц построена качественная зависимость эффективности использования дополнительной ГБД от коэффициента а и количества уровней Ь отражена ниже (рис.3).

-Р6Д

-ГБД {п=0,75)

---ГВД|Л=0.5)

Рисунок 3. Графическая интерпретация зависимости времени выборки иерархических

данных от количества уровней иерархии и коэффициента ускорения доступа к

связанным данным

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

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

Этап 1. Оценка глубины и степени связанности данных. Глубина определяется как среднее значение эксцентриситетов корневых вершин хранимых иерархий. Связность данных определяется по формуле:

где N - количество хранимых иерархий,

и; - количество вершин в иерархии,

и-" - количество вершин, не имеющих дочерних вершин.

Этап 2. Выборка идентификационных атрибутов элементов иерархии в РБД с помощью языка манипулирования реляционными данными: {(г^Д £ = 1,./ -количество вершин.

Этап 3. Добавление элементов иерархии в ГБД в качестве узлов с помощью языка

манипулирования графовыми данными:

{<*;>*} -» {(^>с).

Этап 4. Выборка связей между элементами иерархии в РБД с помощью языка манипулирования реляционными данными:, {(ид; )дУ = 1,../; I — количество связей.

Этап 5. Добавление связей между узлами в ГБД с помощью языка манипулирования графовыми данными:

{(^1;У)2>К} -» {(у)1; у]2>с}.

Количество уровней иерархии « изделии

Этап 6. Удаление данных о связях между элементами иерархии из РБД {(уд; Vj2)R}-С целью программной реализации вышеприведенной методики разработан алгоритм преобразования схемы данных для повышения быстродействия выборки в СУБД на основе использования графовой модели данных (рис. 4).

Рисунок 4. Алгоритм преобразования схемы данных В четвертой главе рассмотрены и определены требования к характеристикам комплекса программных средств (КПС), предназначенного для использования в составе АСУП/АСУТП, и особенности их программной реализации в соответствии с заданной функциональностью. Выявлены системообразующие требования к параметрам и функциям комплекса программных средств, оказывающие влияние на быстродействие выборки данных об изделиях со сложной структурой.

Разработана структура программного обеспечения АСУП/АСУТП (рис.5),

15

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

Интерфейсы пользователя

/V

Система ауте мтифи ка ци и

V

Структурный блок

Функциональный Елок

А

блок БД у

Ж

Ж

БД о технологической среде

БДИ (элементы)

БДИ (связи)

Рисунок 5. Структура программного обеспечения АСУП при использовании разработанной методики

■иным

*' < -f Модуль управлений ,

t * Модуль оценки - f- 1 ;М одул ь п ре о бра зо вания V'' ~ ;"схвмы РБД.С''/ 1 . •¡¡¿Модуль формирования--: : схемы ГБД

*

. -Модуль формирования запросов дляЖ- : Модуль формирования допросов для. * J V , /• >4 ■■РбД/SQL). ■ ; ' . ГВД(СС51).. С

Рисунок 6. Структура комплекса программных средств преобразования схемы данных

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

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

16

Модуль формирования запросов к графовой БД преобразует входные команды в структурированный вид, соответствующий языку CQL.

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

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

Модуль формирования схемы графовой БД создает графовую структуру данных и реализует связи между ее элементами, соответствующие реляционной модели.

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

Parent

Id Level Name Description Type Quantity Jd

1 Project_Board Board Component 1

2 GS M_C lick_B oar 2 d Board Component 1 1

3 2 GSM_SmartG100 Board Component 1 1

4 Motion_S ens or_B 2 oard Board Component 1 1

5 NFM21CC102R1 3 H3D capacitor Subcomponent 1 2

6 NFM21CC223R1 3 H3D capacitor Subcomponent 1 2

7 TZC03P300A110 3 TOO capacitor Subcomponent 3 2

8 TZC03Z060A110 3 TOO capacitor Sub_Component 3 3

9 GRM188R61A475 3 KE15D Capicitor Subcomponent 4 3

10 GRM18 8R61C225 3 KE15D Capicitor Subcomponent 1 3

И ЕМК212ВП06К 3 G_T Capicitor Subcomponent 2 4

12 TC J 24_JR_0722R 3 L Resistor Subcomponent 4 2

13 TC 124_JR_07220 3 RL Resistor Subcomponent 4 2

14 3 PIC18F45k22

15 3 LED

16 3 GL85QUAD

17 3 ТХВ0Ю6

18 3 CN1

19 3 CE0682

SIM. Holder SD.

20 3 7SDCN

21 3'Switch

22 3,CN2Jieader

23 3 Screw

24 3 AMN11112

Controller Lamp

GSM_Module

Voltage

Translator

Power supply connector uBloxLeon-G100

GSM/GPRS module

Subcomponent

Subcomponent Sub_Component

Subcomponent

Subcomponent

Subcomponent

1 2 1 2 1 2

SIM Card holder Subcomponent DIP switch Subcomponent 2x5 male header Subcomponent GSM anttena

screw . Subcomponent

Motion_Sensor Subcomponent

1 2 1

1 1

3 3 3

3

4

I

Таблица 2. Данные об изделии, подвергшемся тестированию Ниже приведена графическая интерпретация полученных результатов, подтверждающая эффективность функционирования КПС, основанного на предлагаемой методике повышения быстродействия выборки иерархических данных и алгоритме преобразования схемы данных для повышения быстродействия выборки иерархических данных, в составе АСУП/ АСУТП (рис. 7 - 9)._

3 15 " ' 11. ' - 16

а 20 11 115

5 щФЩ 1 1S2

б 30 17 152

7 35 17 159

Рисунок 7. Зависимость времени выборки иерархических данных от количества уровней

18

-Рид Пртми. >М -1Т./1 Ьрсмя. Л«.

1 .'К^цЧкгъа.' чад ЩШнШШШ «¿Я 1 Время, *яс. 1

3 30 17 132

4 Л0 22 135

5 50 30 ' 152

6 60 203 191

7 70 гп 192

Рисунок 8. Зависимость времени выборки иерархических данных от количества уровней

иерархии (для а=10)

Рисунок 9. Зависимость времени выборки иерархических данных от количества уровней

иерархии (для а=20)

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

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

При низких и средних значениях Ь применение графовых СУБД не имеет смысла. Быстродействие системы снижается.

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

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

Основные результаты и выводы

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

1. Исследованы базовые процессы функционирования современных АСУП/АСУТП; требования к быстродействию СУБД в информационном обеспечении АСУП/АСУШ при непрерывном росте сложности изделий и увеличении сложности структур данных и степени связанности элементов данных. Рассмотрена зависимость быстродействия систем от моделей данных, лежащих в основе применяемых СУБД.

2. Разработана методика повышения быстродействия выборки иерархических данных в СУБД автоматизированных систем управления производством на основе графовой модели данных.

3. Разработано формализованное представление оценки эффективности организации иерархических данных с точки зрения быстродействия их выборки.

4. Предложен алгоритм преобразования схемы данных для повышения быстродействия выборки в СУБД на основе графовой модели данных.

5. Осуществлена программная реализация методики и алгоритмов повышения быстродействия выборки иерархических данных в СУБД в виде комплекса программных средств. Применение разработанной методики позволило повысить быстродействие выборки иерархических данных в 3,8 раза.

6. Результаты работы внедрены в учебный процесс Национального исследовательского университета«МИЭТ», а также в НИР 59-ИПП «Разработка основ теории, принципов построения и алгоритмов работы высоконадежных систем управления силовыми агрегатами».

Основные результаты диссертационной работы представлены в следующих

публикациях:

1. Хтет Мин Пью. Анализ критериев выбора СУБД, Web-серверов и языка программирования серверов для АСУ // Микроэлектроника и информатика -2011. 18-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. — М.: МИЭТ, апр. 2011г. - 316 с. С. 170.

2. Хтет Мин Пью. Повышение производительности в распределенных базах данных // Актуальные проблемы информатизации в науке, образовании и экономике - 2011. 4-я Всероссийская межвузовская научно - практическая конференция. М.: МИЭТ, 2011. - 196 с. С 177.

3. Хтет Мин Пью. Оптимизация SQL запросов в СУБД MySQL // Микроэлектроника и информатика - 2012. 19-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. -М.: МИЭТ, апр. 2012г. - 324с. С. 156.

4. Хтет Мин Пью. Инф о логическое проектирование базы данных. // «МОЛОДЕЖЬ И НАУКА». 15-я Международная телекоммуникационная конференция молодых ученых и студентов. В 3-х частях. Ч. 3. М.: НИЯУ МИФИ, 2012. -204с. С. 122.

5. Тин Чжо, Хтет Мин Пью. Использование графовых баз данных в системах управления процессами // Микроэлектроника и информатика - 2013. 20-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. - М.: МИЭТ, апр. 2013г. - 340с. С. 172.

6. Тин Чжо, Хтет Мин Пью. Оптимизационный подход к задаче выбора подмножества объектов // Микроэлектроника и информатика - 2013. 20-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. - М.: МИЭТ, апр. 2013г. - 340с. С. 221.

7. Тин Чжо, Хтет Мин Пью. Выбор подмножества объектов с помощью алгоритмов линейного программирования // Современные вопросы науки и образования -21век. Международная заочная научно-практическая конференция: Российская Федерация, г. Тамбов, 29 января 2012 г. С. 137-138.

8. Хтет Мин Пью, Тин Чжо, Чжо Зо Е. К вопросу повышения производительности систем распределенной обработки данных. «Естественные и технические науки. » № 4 2012. С. 277-278. (Перечень ВАК)

9. Киселев Д.В, Киселева Т.П, Тин Чжо, Хтет Мин Пью. Оптимизация выбора элементов технической системы с помощью интеллектуального анализа данных. «Фундаментальные и прикладные проблемы техники и технологии » № 6(296)2012. С. 123-127. Ноябрь-декабря. Госуниверситет-УНПК.' (Перечень ВАК)

10. Хтет Мин Пью, Гагарина Л.Г. Чжо Зо Е. Методика оптимизации однопроцессорной обработки запросов к реляционным базам данных// «Информационные технологии в проектировании и производстве». -М.: ФГУП "ВИМИ",-№2(167). 2014 . С. 35-39 (Перечень ВАК)

Подписано в печать: Формат 60x84 1/16. Уч.-изд.л. ^ Тираж ВС экз. Заказ № £0 Отпечатано в типографии ИПК МИЭТ.

124498, г. Москва, г. Зеленоград, площадь Шокина, дом 1, МИЭТ