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

Введение к работе

Данная диссертационная работа посвящена вопросам разработки методов и программных средств оптимального поиска в базах данных для САГР горных работ, машиностроительных и приборостроительных производств на базе персональных ЭЕЧ IBM PC/AT/XT. Актуальность темы.

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

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

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

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

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

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

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

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

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

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

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

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

6. Расширении понятия производной на графе, введенного в

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

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

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

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

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

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

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

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

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

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

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

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

Структура и объём работы. Диссертационная работа общим объемом 169 страниц машинописного текста состоит из введения, четырёх глав, заключения, списка использованной литературы из 98 наименований, 41 рисунка, одной таблицы и приложения на 4 страницах. СОДЕРЙАНИЕ РАБОТЫ.

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

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

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

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

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

Наиболее распространённой моделью вапроса пользователя к боев данных является графовая модель, мли граф аапроса. С целью отображения логических связей элементов дакклх запросу Q к реляционной базе данных ставится в соответствие граф G_a-<\^,E_a\ в котором множество вершин Vq соответствует множеству отновенкй.

входящих в запрос Q, а множество рёбер Е _Q определяется следующим образом: E_Q« {( L,j ), если запрос Q содержит соединение отношений I и J } .

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

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

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

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

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

чал многествекной обработки данных требуется учёт специфических особенностей САПР, заключающийся в ориентации на модель данных, адекватную предметным областям САПР. Одной кз перспективных является предложенная В, Л. Торховьм модель данных "сущность - связь-, ассоциация" (ССА) - развитие известной модели "сущность - связь" П. Чена. В основе модели ССА лежат два понятия: объект а атрибут; объекты раэбявавтсл на три категории: сущности, связи н ассоциация. База данных есть множество объектов, каждый из которых может обладать атрибутами. Сущности, представляющие в базе данных элементарные объекты, определяются значениями своих атрибутов. Сущности о одинаковыми атрибутами объединяются в класс сущностей. Сущности из различных классов сущностей могут бить взаимосвязаны. Связь представляет собой объект, устанавливающий соответствие между объектами некоторых классов сущностей: Б*, Е_г,..., Е_а. Набор связей R й Е< х Е_г х...х Е^ есть множество кортежей r_L»(e^,..., ^eln?» ^{гдв в}<1⁶ ^ ^віп.⁶^п*"* ^СУ^ТЪ сущности соответствующих классов сущностей. Объекты нерегулярной структуры представляются в модели данных ССА посредством ассоциаций. Ассоцкацхя есть множество сущностей, связей и других ассоциаций о набором связей на этом множестве. Ассоциации могут образовывать классы и входить ж качестве элементов в другие ассоциации.

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

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

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

q - a(Ej ) в с ( Я - а(0ігц,) 6 с ) (I)

или q - a(Ej ) в b(Efc ) ( q - a(0jrvj ) Є 0(0(^) ), (2)

где j ,k « 1 , 2,...,R,; a - атрибут класса сущностей Ej при множественной обработке (некоторого объекта Оіяі , П-j і 2,..., Ni , класса сущностей Ej при объектной обработке, где Nj - мощность класса Е< ); Ь - атрибут класса сущностей (некоторого объекта 0(од , fif < , 2,...,Ng, где *Ц -мощность класса Е^); с - константа; 6 - операция сравнения из множества { =,Л < » < » > »

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

mtn и. (Q) (3)

I '¹

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

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

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

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

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

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

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

или Q [Е] > Q,,vQ_zv...vQ_n, _ГД0 при L - 1 , 2,..., гг

Опродолекга. Дез элементарных подзапроса q_r и (\^ одинаковы в обобщенном смысле: Qj.a 3 CJj( , если І) онн идентичны: Ягі-Яії 5 ²>Чг*^{я А 9}<^С1» ЧіЄ " ^{А 6}г с₂» где в,,Єі - операции ерглненкя, с< к с а - произвольные константы, А - некоторая обіцяй атрибут для Cj_r и q^ ,

Поскольку р^злітаагй порядок обработки некоторой пзры подзапросов исходного эапроса коравнозначем по числу доступов к внешней памяти, в качества исходной теорзтіко-графовой модели запроса используется елвдушззя орграфовая модель: аапросу пользователя Q стзіптея в соответствие взвегеккыЯ помеченный oprpej G « - (4(U,VAjtLy^X каддая верпкна V_L V (I* 4 ,,..,№) которого взаимно-однозначно соответствует подзапросу Qj,( 1-1,...,^-)} каддой упорядоченной паре подзапросов

Ч " Д ч* ^{й Q}t - Ь я*і .-

таких, что 3 г» 4,..#,П-ь, *<,,,.,n.f г q_p^ S q _{,-взогото-однознечно ставится з сеответствяо дуга u.^ « i^tfj , помеченная кненси общего атрибута ц вэвешешшд величиной "U^t - числом доступов к внепней памяти (его оценкой) для просмотра еЧ ort-}

ластей по нужному атрибуту длл всего запроса} и каядоыу подзапросу Q*^! а_х

Q_x & Я^х »- такому, ч«>

^ ^Qs " ии I ^(ЗІ^^{1 а}*'^1г=;| ^^:W»-

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

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

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

Адекватной моделью для интерпретация объектного запроса является теоретико-графовая модель Gq» (V,(U,Wu)>, в которой множество вершин соответствует множеству присутствующих в запросе

-II -

Q объектов, и дзе верпеты соединеїш ребром, если для соответствующих объектов существует обідий аспект, присутстзуицкй в запросе Q и взвснизаікций донное ребро временем своего просмотра во вторичной ПИЛЯТИ.

Утвертдснпе- I. Если введённый граф запрос» Gq содержит и качества собственного подграфа Ш"СЧ произвольной длины или Ф'ігуру, прздетавлениуп на рпс.1, базизбсточноз по числу доступов :: внсиюЯ плклти Еьтачнеіиїз запроса невозможно.

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

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

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

2. Если граф запроса Gq не содержит запрещённые фигуры свойства боэкзбыто-вюсти выполнения запроса Q , переход к п. 5).

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

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

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

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

Q [E*] - & G-.CE;), (5) ,.

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

Вследствие того, что выражение (5) не споцифицируот процедуру поиска данных, в запросе пользователя необходимо указывать классы связей R_aot« R,* _Л+,| «Rfl.b "вЗДу каждой парой классов сущностей Е_а и Е^ (a, b » 1 , 2,..., IX), входящих в подзапросы Q^b выражении (5).

Предлозена следующая теоретико-графовая іштерпретация ынокос-твенного запроса пользователя: запросу Q[E*] ставится о соответствие граф G 4V,Wv)|U^i помеченные верпины которого соответствуют классам сущностей, входящим в правую часть выракеаил (5), непомеченные - промежуточным классам сущностей, относящихся к ноко-торой паре специфицированных классов свяэой, и классам связей. Ве-ршина, соответствующая классу сущностей Е* , объекты которого сформируют ответ на исходный запрос,- также помечается и называется конечной.

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

(W аи>Ц_щ(Лт0аМ(Е)/В(А) /26(A) (6)

(vr ₊₄vl), ^(ЕИс-аО/иг-гц) + І2Б(А)(Пг-п,)/(М)<Пг.-о)) (7) !

ІЧ=(А<с; !

(W +t\* И /_А>С^И (E) (42-0)/(.^ + ^(А)(л^/(Ь(А)(Пг-«)). <в)

- ІЗ -

где В (Л) - количество различных значений атрибута А, [»ц,п.гЗ -область значений атрибута А. Ьсли некоторый конъюнктивный подзапрос вкхэчает в себя несколько элементарных подзапросов, оценка иг +avJ дял ного находится з соответствии с выражением (9): (іГ + д^г)|_а^ * (vr+дад), + (^+aw)| -('J+A^^-W+i^i /(fJ(E)) (9)

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

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

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

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

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

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

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

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

ЭС/ЭН (Ej, . Ej ) - (ftl+{jj+fy+{it)/flj <Ю>

SG/ЭН (Ej , E_t ) - (fj/ +ia+fji + bj)/iji. ^(I1>

где ^n _tjy. - собственные частоты участия вершин Е^ a Ej в событии Н (определяемые оценками иГ+Дго" для помеченных верппн и величинами N (Е [,) и fj (Еj > — для непомеченных); fcj ,-fjj, взаимные частоты участия вершин E*_t и Ej в событии Н.

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

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

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

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

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

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

Предложенное математическое обеспечение решения задачи оптимального выполнения запросов к базам данных САПР р їлизовано в виде пакета прикладных программ оптимального поиска в базах данных САПР, написанного на языке Си для Шк РС/АТ/ХТ. Экспериментальное исследование зависимости качества пакета (относительного уменьшения числа доступов к внешней памяти по сравнения с естественной процедурой обработки запроса) от размерности задачи (количества подзапросов в исходном запросе) показало, что для програнім объектной обработки оно примерно равно 2056, для програмі.», реализующих точну» и приближённую ннозсествекну» обработку, соответственно, 20-40 и 10-20. Полученные в результате экспериментального исследования временные зависимости показали, что время реае-нил задача оптицального поиска в базах данных САПР аппроксимируется квадратичной зависнмостыэ от размерности задачи как в случае объектных запросов, так a d случае июзественных запросов.

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

І

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

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

В результате контрольного бурения и сбора исходных геологе» гидрогеологических данных выделено 20 слоев, который соответствуют объекты Oj, 0₂,..., Одр класса сущностей "Слой". В результате анализа исходных данных'по слоям выделены, в свою очередь, водоносные слои Оц, 0₈- 0₄₂, 0_W , 0_lg (рис.2). Одним из запросов, поступивших из модуля Труттировка водоносных горизонтов", является следующий запрос к классу сущностей Е^ "Слой":

Q[E,1 - (А(0_к,)^с₁)(А(0_э)6с₁+с_г)(А(0₉)<с_&)(А(0₄)<с₃+с₄)-(А(0„ )$с,+с₅)(А(0₄, Нс₆)(А(0,_г)йс_с+с,)(В(0_1О)5с₈).

-(8(0^)^+09)(8(0^)^08+0^)(8(0^)60^)(8^2,)504,40,2). (А(0„)4с_4Ь)(А(0„)$с,_&+с_41|) с целью^определить, возможно ли выделенные слои рассматривал в совокупности (чтобы с поиощьп модуля "Выбор насоса" подобрать насос подходящей мощности) по следующим общий аспектам: "сходные геодого-гидрогеологические данные для смежных водоносных слоев" (c,-C4«c_s-c_T»c,«,«0,05 м/час; с,, о_ь, с₆, с_п - исходные даиныэ) исходя иа значений атрибута А - А_40#,₀ "Расчётный приток подземных вод из всех горизонтов", и "расстояние меаду водоносными слоями" (c_g, с,, - исходные данныо; с». ^с,₀* ^си " технологические данные), исходя из значений атрибута В - А^ (R,) "Горизонт". Зап-

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

(О 1 Ч ю

_{W Я Г}⁴_?

'" ЦП—п—nfo

ігОрГ-о, cL-Ъ о—о,, П ¹¹ tt F. ю іг F₃

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

Рис.3. Граф Рис. 4. Запрещённые

запроса. фигуры.

vСН-ОіГ-ОіГ⁰« ^

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

росу QtE_A] соответствует граф запроса Ga на рис.3. Запрещённые фигуры свойства безызбыточности выполнения запроса Q представлены на рис.4.

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

Существуют четыре минимальные покрытия столбцов семантической таблицы её строками: Я,,» (Г₂ , г_гі ), 1Г_г = ( г_г , r_tl ), Jtj » ( Ґ_в ,г_ц ), Яц ( ^r6 . Чв ). Вследствие того, что каждое из таких покрытий включает в себя преобразования, относящиеся к различным аспектам, они являются одинаковыми по суммарным временным затратам. Каждому

из указанных номинальных покрытий соответствуют модифицированные графы запроса G, , G>_t , G( , G^, (рис.5). Поскольку анализ двух объектов по второму аспекту требует меньшего времени, так кед рассматривается один атрибут В , а не несколько атрибутов, соответствующих некоторой совокупности геолого-гидрогеологических данных (один из них - атрибут А,₀,₀ ), обеспечению минимального времени отклика в интерактивном режиме удовлетворяют покрытия JCj и %х Они определяют, соответственно, две оптимальные последовательности обработки запроса :

Q« - (0/,,0,2.)(0^,0^(0^,0^)(0^,0,,)(0^,0,,)(0^,0^)

(Ом.о;'о)(о;.о₉)(о₉Л) и Qrt (о;,,о,_г)(о₍₁,о;')(о;,о_1в)(о,_?.о₁₈)(о_1Я,о₁₀ )(oJ.o_w)

(О,", ,0,₀)(0,₀,0_Э)(0_Э,0,). В случав естественной процедуры выполнения запроса Q[E,1 получаемая последовательность обработки следующая:

Q« (0,0.0,)(09.0,)(0^.0,,)(0,,,0^)(0^,0,,)(0,,.0^

(0ц.О<Н»⁰И.>.⁽⁰Г|.0»»). где "* " обозначает повторное размещение соответствующего объекта в оперативной памяти. Таким образом, в случае, когда подзапросы обрабатываются в том порядке, в каком они представлены пользователем, требуется 13 доступов к внешней памяти в отличие от 10 - з случае процедуры оптимального поиска, которая позволяет, следовательно, примерно на 20-254 уменьвить время обработки запроса Qt

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

- 19 .-

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

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

Одной из важнейших объектных функций системы автоматизации вы-емочно-погрузочных работ на сланцевом разрезе является решение оптимизационной задачи на математической модели производственного процесса, что обеспечивает оптимальное согласованное функционирование оборудования на траншее. Эта задача сводится к задаче линейного программирования с максимизацией функции производительности вскрышной мехлопаты ЭВГ-35.65Ы при существующих ограничениях: норме добычи сланца, интенсивности бурения водоотводной канавы с помощь» CES-2Ы, постоянстве расстояния между карьерной мехлопатой ЭКГ-4.6"Б" и вскрышной мехлопатой, требованиях ТБ по безопасным расстояниям между единицами оборудования. Фрагмент схемы процесса подвигания оборудования на одной ааходке траншеи показан на рис.7.

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

смена

дата добыча

координаты

координаты

/

О"

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

ЭВГ-^5,65Ы

4L-. ^кЪ -

і- зона экска-

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

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

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

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

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

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

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

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

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

Исследование и разработка методов проектирования баз данных САПР Горшков Сергей Николаевич

Визуальный метод разработки объектно-ориентированных баз данных для систем автоматизированного проектированияБелых, Александр Валерьевич

Разработка методов построения адаптивных УИСАПР на базе гипермедиа технологииВалько, Александр Федорович

Разработка системы проектирования гибких полиимидных носителей на базе геометрических методов трассировкиВласов, Сергей Евгеньевич

Разработка методов и средств анализа и контроля диаграмматики бизнес-процессов в проектировании автоматизированных системГайнуллин Ринат Фаязович

Исследование и разработка методов и средств проектирования сложных вычислительных комплексов на уровне малоформализованных структурных элементовСебто, Юрий Геньевич

Исследование и разработка методов и средств реализации диаграммных графических языков САПРШаров Олег Геннадьевич

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

Разработка методов и средств обработки лингвистических структурно-функциональных моделей цифровых аппаратных средств на основе нейро-семантических сетейИгонин Андрей Геннадьевич

Разработка метода и средств формирования и развития интегрированной среды поддержки создания САПР машиностроительного назначенияВолодин Дмитрий Александрович