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

Государственный комитет СССР по народному образованию

Московский ордена Трудового Красного Знамени горный институт

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

ГОЛУ БЕН КО Валерий Евгеньевич

УДК 622:658.512.22.011.56 (043.3)

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

05.13.12 — «Системы автоматизации проектирования (промышленность)»

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

Москва 1991

Работа выполнена в Московском ордена Трудового Красного Знамени горном институте.

Н а у ч н ы й ру ко в од и те л ь академик РАЕН ГОРБАТОВ В. А.

Официальные оппоненты: докт. техн. наук, лроф. РЯБОВ Л. П., канд. техн. наук, с. н. с. КУЗИН В. В.

Ведущая организация: НПО «Альтаир».

Защита диссертации состоится « » «я. 1991 г. ¿Г 00

в ?Ч . час. на заседании специализированного совета

Д. 053.12.12 Московского ордена Трудового Красного Знамени горного института по адресу: 117935, Москва, В-49, Ле-ииский проспект, 6.

С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан « Л'. » . . 1991 Г-

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

доц., канд. техн. паук ТОРХОВ В. Л.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Данная диссертационная работа посвящена вопросам разработки методов и программных средств оптимального поиска в базах данных дяя CAIP горных работ, машиностроительных и приборостроительных производств на базе персональных ЭВМ IBM PC/AT/XT.

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

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

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

Актуальность разработки новых методов оптимального поиска данных обусловлена также следующими объективными причинами:

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

2. Широким распространением персональных рабочих станций САПР, поскольку вопрос поддержки баз данных на персональных ЭВМ имеет свою специфику.

Цель работы заключается в разработке математического обеспечения и его программной реализации на базе персональных ЭВМ 1ВИ РС/АТ/ХТ для осуществления оптимальной обработки запросов на поиск к базе данных САПР.

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

Научные положения, разработанные лично соискателем и новиз-

ца:

1. Введение и характеризация свойства безызбыточности выполнения запроса на поиск по числу доступов к внешней памяти ЭВМ при уча те специфики данных и обработки данных а САГР.

2. Введение классификации запросов на объектные, относящиеся к проектноР базе данных, и множественна, относящиеся к нормативно-справочной сазе данных САГР.

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

4. Расширение понятия производной на гр%.|«е, введенного в

практику проф. В. А. Горбатовым.

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

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

- положительными результата}.« внедрения разработанных методов и программных средств оптимального поиска в базах данных САГР в промышленность, подтверждающими произведённые оценки характеристик созданного пакета прикладных программ.

Практическая ценность работы.

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

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

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

4. Пакет прикладных программ оптимального поиска в базах данных САГР внедрён в практику автоматизации проектных работ, подготовки и организации производства изделий на ПО "Точмап", в НИР/ ОКР "Компас". Эксплуатация показала его эффективность в уменьшении времени проектирования.

Апробация работы. Основные результаты диссертационной работы доложены и обсуждены на XII Всесогзном симпозиуме "Логическое управление с использованием ЭВМ" (Симферополь, 1"звЭ), Всесоюзной научно-гехничоскоЯ конференции "Интегрировалимс системы автон*.тя~

зированного проектирования" (Вологда, 1989), Совещании специалист тов стран-членов СЭВ (Суздаль, 1989), XIII Всесоюзном симпозиуме "Логическое управление с использованием ЭШ" и XII Координационном совещании "Математическое обеспечение интеллектуальных систем САИ^-ТАП" (Симеиз, 1990).

публикации. Основное содержание диссертационной работы отражено в пяти опубликованных статьях и в одном отчёте по НИР.

Структура и объём работы. Диссертационная работа общим объемом 169 страниц машинописного текста состоит из введения, четырёх глав, заключения, списка использованной литературы из 98 наименований, 41 рисунка, одной таблицы и приложения на 4 страницах.

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

Одной из основных задач, возникающих при поддержке баз данных САПР, является оптимизация поиска данных. Необходимость минимизации времени поиска данных возникает как при интерактивном, так и при пакетном режиме работы пользователя с базой данных САГГ. b первом случае в процессе диалогового взаимодействия с подсистемами базы данных пользователь может принимать некоторое решение, в связи о чем возможность интерактивного взаимодействия определяется временем отклика. Б случае пакетной обработки запросов, характеризующейся наличием больяого числа обращений х внешни» памяти, существенно, насколько быстро будет локализована информация.

Задача организации баз данных САГР связана с классическими проблемами организации баз данных и с теоретическими основами построения САГР, значительный вклад в исследование которых внесли В.М.Глувков, В.А.Горбатов, В.В.Девятков, С.В.Емельянов, И.П.Норе-нков, В.П.Ксрячко, О.Н.Перыинов, Л.П.Рябов, Б.Г.Тамм, А.Б.Фролов,

Б.А.Щуккн, М.Брейер, К.Дойг, Е.Кодд, Да.Угьиая я другие учёные.

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

Дяя баз данных САПР характерны разнообразные пзды данных и работы с дамиши. В базе данных САПР осуществляются как действия с отдельны:а объектами, таи и действия со шокествои элементов внутри сложных объоктоз. В базах данных САПР принято условно выделять три части: нормативно-справочную базу данных, проектную базу данных и базу данных и знаний для принятия решений. Для работы с норыатиЕно-справопноЯ базой данных характерна иютоствен-ная обработка, т.е. обработка болъвого количества объектов одкна-ковой структуры; для работы е проектной базой данных характерна объектная обработка, при которой рассматриваются объекты, описания которых а они сами требуют значительных объёмов памяти. Соответственно, возникают две задачи оптимального поиска - дяя множественных запросов, относящихся к множествам однотипных объектов, и для объектных запросов, относящихся к отдельным сложным объектам проектирования.

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

входящих в запрос Ц, а множество робер Еа определяется следующим образом: Ей« {( I, ] ), если запрос О содержит соединение отношений I и J } .

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

Универсальным можно считать принцип оптимального выполнения запросов, сформулированный Дж. Ульманом и заключающийся в максимально возможном пошаговом сужении области поиска во вторичной памяти ЭВМ при обработке запроса.

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

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

Анализ современного состояния задачи оптимального поиска в базах данных САГР позволяет сделать вывод, что для случая объектной обработки данная задача оптимизации поиска не исслнлована и требует своего решения, включал разработку модели представления объектного запроса и метода оптимизации 1-го сыпплненил. Для слу-

тая многествеиной обработки данных требуется учёт специфических особенностей САГР, зазшзчглщкЯся в ориентации на модель данных, адекватную предметным областям САПР. Одной из перспективных является предложенная В, Л. Торховьм модель данных "сущность - связь-ассоциация" (ССА) - развитие известной модели "сухость - связь" П. Чана. В основе модели ССА лежат два понятия: объект а атрибут; объекты разбив газ гея на три категории: сущности, связи и ассоциация. База данных есть мисзестзо объектов, каядыД из которых может обладать атрибутами. Сущности, представляющие в базе дашшх элементарные объекты, определяются значениями своих атрибутов. Сущности о одинаковыми атрибутами объединяются в класс сущностей. Сущности из различных классов сущностей могут бить взаимосвязаны. Связь представляет собой объект, устанавливающий соответствие между объектам* некоторых классов сущностей: Е^, Е2,..., Еа. Набор связей R й х Ег х...х Е^ есть множество кортежей el|v), где е^б Е , e1|V6Ea- суть сущности соответствующих классов сущностей. Объекты нерегулярной структуры представляются в модем данных ССА посредством ассоциаций. Ассоциация есть многое-тво сущностей, связей и других ассоциаций о набором связей на этом множестве. Ассоциации могут образовывать классы и входить в качестве элементов в другие ассоциации.

В диссертационной работе рассматривается представление запросов пользователя к специализированной базе денных САГР в виде совокупности элементарных предикатов, относящихся х некоторым классам (сущностей, связей, ассоциаций; при учёте соответствующих связей между этими классами) и включающих логические условия (из набора { -,«1, <•<«>,}}) по некоторому аспекту (атрибуту) из соответствующего класса. Без потери общности рассмотрение огради-

чано классами сущностей и классами связей внутри одной ассоциации.

Определение. Запрос Q « Q [Е^] пользователя к базе данных (классу сущностей E-t,l»1,...,n.) есть произвольная совокупность элементарных подзапросов вида:

q - a(Ej ) в с ( <\ - а(0(.гц,) б с ) (I)

или q - a(Ej ) в b(Efc ) ( q - a(0jnj ) в b(O^) ), (2)

где j ,{; « 1 , 2,...,M; а - атрибут класса сущностей Ej при множественной обработке (некоторого объекта Ojaj « flj» 1 , 2,..., Nj ( класса сущностей Ej при объектной обработке, где Nj - мощность класса Ej ); Ь - атрибут класса сущностей Е^ (некоторого объекта , л^» 1 , 2,...,Hg, где - модность класса

с - константа; 6 - операция сравнения из множества { <»{»>• И .

Поскольку поиск данных связан с доступом к определённым данным во внешней памяти ЭВМ с целью ответа на запрос, под оптимальным поиском понимается минимизация функционала (Q ), определяемого количеством доступов к внешней памяти для некоторого I -го варианта обработки запроса Q при существующих ограничениях на оС ьем оперативной памяти V0(M - для данных из внешней памяти и VDni - для промежуточных данных формирования ответа на запрос Q :

mtn (?. (Q) (3)

1

Поскольку для случая элементарных подзапросов вида (2) существуют следующие возможности:

1) атрибут b имеет некоторое конкретное значение, т.е. выражения (2) и (I) идентичны;

2) а и Ь - различные атрибуты разных классов сущностей, т. е. несравнимы вследствие различных областей своих значений;

3) "а" и - различило обозначения одного и того ко атрибута некоторого класса сущностей,- ' р"сс;.:атр;:2?л"гсл только злемзнтаркиэ подзапросы о «да (I).

В качество обобщённого представления объектного запроса

кепользузтея дизгвгаиеизная нормальная форма (ДЯЗ):

И tlj

Q[E] - V .& п., , (4)

l-.tj-l 'Ч

или Q [Е] « Q1vQzv...vQri( Гдо при L - 1 , 2,..., rt

Qi - $ q4 •

Оггродолск::-э. Де1 элеизнтаршх подзапроса и Cj4j одинаковы в обобщенной смысле; 3 , если I) они здзнпгзш:

ЯгЬ-Яи i 2>Чг*" А 0<с1» Я*£ " А с2» ГД9 - опера-

ции ерглннгея, с < I! Ст. - произвольные константы, А - некоторый общий атрибут для и q^ ,

Поскольку р^злзтаагй порядок обработки некоторой пзры подзапросов исходного запроса коравнозначе:! по числу доступов я внешней памяти, в начоствэ исходной теоротияо-графовоЯ иоделк запроса используется следующая орграфовая модель: запросу пользователя Q сталптсл в соствотстзиэ взвегегашЗ помэчзкикЯ oprpe j G « - <V,(U,V/u,Lu)>» каздая верззш. V^eV ( l- ,...,^) которого взаимно-однозначно соответствует подзапросу Qj,( I - i,..., ft)} шаздой упорддочзниой rcipo подзапросов

Ч " Д Ч* й °с - Ь ^

таких, что 3 » 4 ,...,'4 t Яг& 4 Я^Ь

взагото-одаознечно ставятся з сеответствяо дуга u.^ » i^tfj , помеченная киснси общего атрибута ц взвешенная величиной "Uf^e ~ чи~ слом доступоз к внепнеП памяти (его оценкой) для просмотра еЧ об-

л остей по нужному атрибуту для всего запроса; и каждоцу подзапросу ах

Ох в & Я^х »- »ькому, что

^ - I (311-1.....а*»1г=;|.....

ставится в соответствие множество помеченних петель.

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

При обработка объектных оопросоз должна быть учтена собственно специфика взаимодействия пользователя с проектной базой данных САП?, а шгшш: объекты, р&ссиатривйемыо пользователем в процессе проектирования, имеют значительный объём, н ток как их рассмотрение ведётся по некоторым общим аспектом (атрибутам), по меньшей мере два объекта одновременно долены поддерживаться о оперативной памяти. Весьма малый объём оперативной пшти приводит к ограничению, по которому одновременно в оперативной памяти можно разместить не более двух объектов. Следовательно, существуют такие запроси, которые невозможно обработать безызбыточным образом, т.о. без дополнительных обргщанкй с внесшей памяти (связо-1шых с буферированная одного иди нескольких объектов). Поскольку временные затраты но зависят от парадка обработки дизъюнктивных подвапросов по общему атрибуту, рассматриваются конъюнктивные вопросы.

Адекватной моделью для интерпретация объектного запроса является теоретико-графовая модель <V, (и,"\Л>в которой множество вершин соответствует множеству присутствующих в запросе

Ц объектов, и две серпмны соедннени рзбром, если для соответствующих объектов су,-зе?зузт общий аспект, присутствующий в запросе Ц и взвс^изанщий данкоо ребро временем своего просмотра во пто-ричной памяти.

Утвертдсшаэ I. Если введённый граф запрос» содергкт э качзствэ собственного подграфа щ«с.ч произвольной длины или Фигуру, прздставлс'нуп ¡га рпс.1, базызбсточиоз по числу доступов :: внсиюй плклти вьтолненкз запроса невогмопио.

Поскольку но каждой запрос допускает ноизбнточнос еыполпсн:«, задача преобразования его в допускающий кзизбьггочюо выполненна является пембтааторноЗ. Мсщнь:! средством построения комбинаторных алгоритмов язляотся теор;п х&рактеризадаокного анализа, разрабо'.".".-ннак проф. Б. Л. Горбатовым.

Метод оптимального выпояиенгм объектного запроса осноегл на процедурной реализации конструктивного преобразования грсДа запроса и допускающий безызбыточнуа обработку:

1) ОбъоктныЯ запрос О представляется п евдо графа запроса

ва.

2) Если граф запроса &<а не содержит запрещённые фигуры свойства безызбыточности выполнения запроса О , переход к п. 5).

3) Сормировгнае и покрытие семантической таблицы.

4) Определение минимального количества расцепляемые вериин.

5) Формирование результирующей последовательности обработки объектного запроса.

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

О [Е*3 . & G-.CE г), (5)

поскольку ответ на дизъюнктивный запрос нонет быть представлен кап объединение ответов на подзапросы-дизъюнкты.

Вследствие того, что выражение (5) не споцифицируот процедуру поиска данных, в запросе пользователя необходимо указывать классы связей 1?ао1« ЯЛ Л+<1 ••«•»КрД, меаду каздой парой классов сущностей Еа и Е^ (а, Ь » 1 , 2,..., IX), входящих о подзапросы О^в выражении (5).

Предложена следующая теоретико-графовая интерпретация ынокос-твенного запроса пользователя: запросу Ц[Е*] ставится о соответствие граф й ■ Ф^У/уХ^Л помеченный соршшы которого соответствуют классам сущностей, входящий в правую часть выракенил (5), непомеченные - промежуточный классзд сущностей, относящихся к некоторой паре специфицированных классов свяэой, и классам связей. Вершина, соответствующая классу сущностей Е* , объекты которого сформируют ответ на исходный запрос,- также помечается и называется конечной.

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

М/Ъ(А) * /2 6(А) (6)

+Ау)), ?Ц(Е)(с-а,)/(п2-г11) + Г2б(А)(Пг-п,)/(1)(А)(пг.-о)) (7) !

1Ч=(А<с; !

Сиг ^(ЕНчг-с)/^ ♦ ^(А)М/(Ь(А)(пг-с)), (8)

где В (Л) - количество различных значений атрибута А, [гц, ] -область значений атрибута А. Ьсли некоторый конъюнктивный подзапрос вкачает в себя несколько элементарных подзапросов, оценка иг +д<Л для ного находится э соответствии с выражением (9): (1ХГ + Дггг)|^ ^^^ * Ы+дзд)^ + (9)

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

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

Утверждение 2. В оптимальной последовательности обработки мно-г.ественного запроса продаяуто'иыа перлини для каядой ветви графа запроса 6 расположены последовательно.

Следстзиэ. Оптиыальная последовательность обработки иноаест-венного запроса инвариантна относительно редукции групп непомеченных вершин (&-»&').

Утверждение 3. Задача оптимального выполнения множественного запроса ЫР-полна.

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

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

в процессе некоторого субопткмалы-юго перехода от одной помеченной вершины графа С к следующей - до тех пор, пока но будут обработаны все такие вершины, и заключительного парохода к коночной вершина Е*,- в рассмотрении постоянно находятся две вершили - соответствующая просматриваемому б данный момент классу сущностей и Берлина,' в которую будет совершён переход для дальнейшей обработки,- в качество эвристики для определения такой пары вершин прод-локена эвристика, основанная на двуместной операции - производной на графе. Применено расширенное понятно производной на графе со свойством антикоммутативности (частотная матрица, отраяаищоя в качество события Н , по которому берётся производная, "интенсивность участия помеченных вершин своими объектами в формировании текущего ответа на исходный запрос", несимметрична):

эс/эн (Е£,. е|| ) - (ю)

эс/эн с^ , е1 ) - (^ <1А>

где - собственные частоты участия вершин Е^ и Ej в

событии Н (определяемые оценками иГ+Дго" для помеченных вершин и величинами N (Е ^ ) и ) - для непомечонных); {у

взаимные частоты участия вершин Е ^ и Ej в событии Н.

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

1) Включить в формирующуюся последовательность оптимальной обработки ветвь с максимальным значением производной на графе С •

2) Удалить выбранную ветвь из графа ; если в результате граф станет несвязным, запомнить компоненту, не содеркащую конечную вершину Е ; рассмотреть в качестве 6 компоненту, не содержащую коночную вершину Е* , и вершину, степень которой в результате уда-

лешгя выбранной ветви уменьшилась на единицу, считать конечной (Е*); если в результате удаления выбранной ветви граф остаётся связным, рассмотреть его в качестве б'.

3) Если последняя вершина в формирующейся последовательности но есть Е*, включить в формирующуюся последовательность множество ветвей, соединяющее последнюю верагау с конечной вершиной Е*

4) Если не все компоненты графа &' рассмотрены, рассмотреть в качестве О' следующую компоненту.

Предложенное математическое обеспечение решения задачи оптимального выполнения запросов к базам данных САПР р хлизовано в виде пакета прикладных программ оптимального поиска в базах данных САПР, написанного на язызсе Си для 1ЕМ РС/АТУХТ. Экспериментальное исследование зависимости качества пакета (относительного уменьшения числа доступов к внешней памяти по сравнения с естественной процедурой обработки запроса) от размерности задачи (количества подзапросов в исходном запросе) показало, что для прогрэн-ггы объектной обработки оно примерно равно 20$, для программ, реализующих точную и приближённую ннозсественну» обработку, соответственно, 20-403 и Ю-20&. Полученные в результате экспериментального исследования временные зависимости показали, что время реае-нил задача оптимального поиска в базах данных САПР аппроксимируется квадратичной зависимостью от размерности задачи как в случае объектных запросов, так и и случав июзественкых запросов.

\

В качестве одного из объектов проектирования для разработанных котодов н программных средств рассматривается технология специальных способов проходки стволов подземных сооружений в тресте "Шахтспецстрой". Назначение создаваемой САПР специальных способов проходки заключается в разработке проекта тампонирования водонос-

(

пых горизонтов специальным;! растворами (цементными, глинистыми и др.) с помощью специальных скважш. Основной подсистемой САП? является специализированная система поддеркки база данных. Обращение в базу данных производится с помощью програьгйшх ыодулой.

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

В результате контрольного бурения и сбора исходных геолога» гидрогеологических данных выделено 20 слоев, который соответствуют объекты 0(, 02,..., О^р класса сущностей "Слой". В результате анализа исходных данных'по слоям выделены, в свою очередь, водоносные слои 0^, 08- 042, 017, 018 (рис.2). Одниы из запросов, поступивших из модуля "Группировка водоносных горизонтов", является следующий запрос к классу сущностей Е1 "Слой":

(ИЕ,1 = (А(01о)^с1)(А(0э)6с1+сг)(А(09)<с&)(А(04)<с3+с4)-

•(А(0„ )$с4+с5)(А(041 )^с6)(А(01г)йсс+с,)(В(01О)5с8). • (В(018 )*с8+с9)(В(О^) * с8+с<0) (В(0,,) ^ сл1)(В(0и) С см-«!1г )• •(А(0„)4 с4Ь)(А(04? ) $ с,&-№4/|) с целью »определить, возможно ли ввделешше слои рассматривал в совокупности (чтобы с помощью модуля "Выбор насоса" подобрать насос подходящей мощности) по следующим общий аспектом: "сходные геолого-гидрогеологические данные для смежных водоносных слоев" (с1"с^»с5»ст-с1«)«0,05 м/час; с4, оь, с6, оп - исходные данныэ) исходя иа значений атрибута А ■ А<оио "Расчетный приток подземных вод из всех горизонтов", и "расстояние между водоносными слоями" (с8, - исходные данныо; Сд, с,0, с^ - технологические данные), исходя из значений атрибута В » А^ (К^) "Горизонт". Зап-

Рис.1. Запрещённая фщ>ура безубыточной обработки объектного запроса.

(О ^ ч ю

Рис.2. Водоносные слои.

П 11 и Р. ю 12 Р3

10^ 10 р ,в (7П-Г)-П(0

Рно.З. Граф

запроса.

Рис. 4. Запрещённые фигуры.

-Я

О * '

Дг О(т~О<0' *

Рис.5. Преобразованные графы запроса.

росу соответствует граф запроса Сана рис.3. Запрещённые

фигуры свойства безызбыточности выполнения запроса & представлены на рис.4.

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

ч Ь Рг ь, р»

I I 1 I

I I I I I

Ъ I I I I

I I I I

Г5 I I I I I

Ч I I I I I

»> I I I I

По I I I

I I I

гч I I I I

Пэ I I I I

ь I I I I

ги I I I

1г» I I I I I

Существуют четыре минимальные покрытия столбцов семантической таблицы её строками: Я,,» (Г2 , ), <кг «. ( , ), Яз » ( Гв ,ГЦ).

*Сц > ( Г6 , Ггв ). Вследствие того, что каждое из таких покрытий включает в себя преобразования, относящиеся к различным аспектам, они являются одинаковыми по суммарным временным затратам. Каждому

из указанных ша<имальн№с покрытий соответствуют модифицированные граф* запроса 6,' , 0>2. » , С^ (рис.5). Поскольку анализ двух объектов по второму аспекту требует меньшего времени, так кед рассматривается один атрибут В , а не несколько атрибутов, соответствующих некоторой совокупности геолого-гидрогеологических данных (один из них - атрибут А1(мо ), обеспечению минимального времени отклика в интерактивном рехиме удовлетворяют покрытия ^ и • Они определяют, соответственно, две оптимальные последовательности обработки запроса :

Он - К .°12.)<0<г..О^)(0(о .04)(0^.018)(0,?,0,а)(018> (Ом.о;'о)(о;,оэ)(о9,о4)

и о« ■ (о;,,о,г)(о,1,о;')(о;,о1в)(о1?.о18)(о1!1,о10 щ,о„)

(О,", ,0<о)(0<о,0э)(0э,0,).

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

<а» ■ (о10,о9но9,оаио* ,о„ )<0М .01г)(0*^,014){0„ ,0А) ) (0*8 ,0,?),

где "* " обозначает повторное размещение соответствующего объекта в оперативной памяти. Таким образом, в случае, когда подзапросы обрабатываются в том порядке, в какой они представлены пользователем, требуется 13 доступов к внешней памяти в отличие от 10 - з случае процедуры оптимального поиска, которая позволяет, следовательно, примерно на 20-25* уменьшить время обработки запроса Ц[Е<1 .

Специализированная система поддержки базы денных создаётся на основе инструментального комплекса ИНДО-САГР (МГИ, кафедра "Вычислительные машины"). Внедрение САПР специальных способов проходки позволяет сократить сроки проектирования технологий проходки в 510 раз. Внедрение собственно подсистемы оптимального поиска поаво-

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

Пакет прикладных программ оптимального поиска используется при взаимодействии с создаваемой специализированной базой данных сланцевого разреза "Октябрьский". База данных сланцевого разреза содержит модель месторождения, проект разреза и информации по материальным и трудовым ресурсам. Ассоциация "Разрез1', состоящая из ассоциации "Карьерное поле", объектов "Административный корпус", "Обогатительная фабрика" и классов связей "Проектно-плановые работы", "Оперативные сводки", "Транспортировка" и "Отвалообраэование", показана на рис.6.

Одной из важнейших объектных функций системы автоматизации вы-емочно-погрузочных работ на сланцевом разрезе является решение оптимизационной задачи на математической модели производственного процесса, что обеспечивает оптимальное согласованное функционирование оборудования на траншее. Эта задача сводится к вадаче линейного программирования с максимизацией функции производительности вскрышной мехлопаты ЭВГ-35.65Ы при существующих ограничениях: норме добычи сланца, интенсивности бурения водоотводной канавы с помощь» СЕВ-

V . ' -

2Ы, постоянстве расстояния между карьерной ыехлопатой ЭКГ-4.6"Б" и вскрышной ыехлопатой, требованиях ТБ по безопасным расстояниям между единицами оборудования. Фрагмент схемы процесса подвигания оборудования на одной ааходке траншеи показан на рис.7.

Автоматизированная система технологической подготовки производства выемочно-погрузочных работ на разрезе "Октябрьский" разработана для ПЭВМ 1ВМ РС/АТДТ и совместимых ("Нейрон"). Система позво-

смена

дата добыча

>координаты

Он

О**

> название (_) координаты границы земельного отвода Рис.6. Ассоциация "Разрез".

СВБ-2Ы

дрена«- бурений штрек ние

водоотводной канавы

ЭКГ-4.6 _.100 , отгруэ-' ка сланца

100 (---—» взрываемый блок

СВБ-5М

А

пром-пласта

обури-ваемый блок (сланец)

ЭКГ-4.6 «100„_, зачистка про-мпласта

,101 он ас-ная зона

I- э

коЬ

она экскавации известняка

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

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

Практическое использование разработанного пакета прикладных программ оптимального поиска в базах данных для САПР (ПО "Точмаш", НИР/ОКР "Компас") показало его эффективность (существенное уменьшение сроков проектирования специализированных систем поддержки баз данных САПР и сокращение времени отклика в интерактивном режиме в среднем на 20$). Суммарный экономический эффект, полученный в результате внедрения программных средств оптимального поиска, составил 36300 рублей. Все внедрения подтверждены соответствующими актами о внедрении.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РА1ЮТЫ.

1. Произведена классификация запросов пользователя к базе данных САПР на объектные и множественные.

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

3. На основе найденных запрещённых фигур указанного свойства разработан метод оптимального поиска для объектных запросов к базе данных САГР.

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

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

5. На основе предложенных методов созданы алгоритмы оптимального поиска для объектных и множественных запросов к базе данных САГР.

6. На основе разработанных алгоритмов создан пакет прикладных программ, обеспечивающий выполнение запроса пользователя к базе данных СА1Р, оптимальное по критериям минимального значения:

- числа обращений к внешней памяти;

- объема оперативной памяти;

- времени отклика в интерактивном режиме.

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

V. Разработанное программное обеспечение в составе комплекса инструментальных средств ИН40-САПР внедрено в практику автоматизации проектных работ, подготовки и организации производства изделий на ПО "Тошен", в НИР/ОКР "Компас", что позволило в среднем на 20-2ЕЛ уменьшить время отклика подсистемы поиска данных в соответствующих базах данных САПР. В качестве важного компонента инструментальных средств ИНФО-САПР разработанное программно'! обеспечение оптимального поиска служит обеспечению эффективного функционирования систем поддержки баз данных САГР.

(•снппньк* положения диссертации изложены в слидумцих работах:

I. 1'олубкнго й.К. Автоматизированная система технологической

подготовки производства выемочно-погрузочных работ на сланцевом разрезе.- В кн.: Логическое управление с использованием ЭВМ,- Ы.-Симеиз, 1990, 401-402.

2. Голубенко В.Б. Автопокрытие запросной таблицы.- В кн.: Логическое управление с использованием ЭШ.- U.- Симферополь, 1989, 228-232.

3. Голубенко В.Е. Оптимизация поиска в базах данных в системах автоматизации планово-проектных работ.- В кн.: Логическое управление с использованием ЭШ.- М,- Симеиз, 1990, 294-298.

4. Голубенко В.Е. Оптимизация поиска в базах данных для АРМ САПР.- В кн.: Интегрированные системы автоматизированного проектирования.- М,- Вологда, 1989, 54^55.

5. Горбатов В.А., Торхов В.Л., Голубенко В.Е. Инструментарий поддержки интеллектуальных баз данных САПР для ГСЭШ.- В сб.; Персональные ЭШ в задачах проектирования и поддержки решений.- М.Суздаль, 1989, 14-15.

Подписано в печать 3.04.1991 г. Формат 60 х 30/16 Объём I печ. л. Тира« 100 экз. Заказ

Типография Московского ордена Трудового Красного Знамени горного института. Ленинский пр-т., 6.