Содержание к диссертации
Введение 4.
1. Анализ систем и постановка задачи ІЗ
Трехуровневая концепция и обощенная схема СУЩ і5
Модели данных 5
Проблема автоматизации проектирования схемы базы данных. 26
Проблема эффективной реализации реляционных запросов.... 33
Выводы 43
2. Методы и алгоритмы проектирования лгической и физической схе
мы реляционной базы данных с помощью ЭВМ кЬ
Выбор физической организации базы данных рассматриваемого класса задач kS
F -структура и её свойства 62
Алгоритм 72
Пример работы алгоритма. -. 15
Выводы 80
3. Методы реализации операций реляционной алгебры Кодца в одно
родных вычислительных системах %Z
Некоторые предпосылки 82
Операции реляционной алгебры и некоторые замечания о методах их реализации Я 4-
Общее описание метода 95
Декомпозиция задачи на этапы 97
Метод выполнения реляционных операций в однопроцессорной системе 103
Оценка эффективности предложенного метода 114-
Методы выполнения реляционных запросов в многопроцессорных системах 1ZQ
Выводы -/fZ
4. Реализация /43
Общее описание системы Mf
Основные потоки данных в системе.Трехконтурный принцип 150
Конструирование базы данных /5Ь
Язык манипулирования данными /58.
Реализация методов манипулирования данными
в СУРЭЗ /65
4.6. Форматный вывод /67
Заключение и рекомендации г7$
Литература /86
Приложение I. /92.
Приложение 2.... 2/2
Приложение 3 21Э
Введение к работе
В числе узловых проблем развития народного хозяйства нашей страны на современном этапе ХХУІ съездом КПСС названы ускорение научно-технического прогресса и дальнейшее совершенствование управления экономикой.
Одним из важнейших направлений научно-технического прогресса и совершенствования управления экономикой стали автоматизированные системы управления (АСУ). В настоящее время в стране действуют тысячи АСУ различного назначения и фронт работ в этой области продолжает расширятся. ХХУІ съезд поставил задачу дальнейшего совершенствования АСУ, повышения их эффективности.
Центральным звеном любой АСУ является система обработки данных с помощью электронных вычислительных машин (ЭШ). Объем перерабатываемой информации в современных крупных АСУ непрерывно возрастает и достигает в настоящее время порядка 800 мегабайт для одной АСУ. Вся эта информация непрерывно обновляется с целью поддержания её в актуальном состоянии.
Принятыми в последние годы постановлениями Щ КПСС и Совета Министров СССР , направленными на улучшение планирования и усиление воздействия хозяственного механизма на повышение эффективности производства и качества работы, предусматривается значительное изменение и совершенствование методов планирования и управления в масштабах всей страны и на всех уровнях. Эти изменения хозяйственного механизма, естественно, затрагивают и действующие в стране АСУ, требуют от них быстрой перестройки многих функционирующих подсистем и алгоритмов управления. В связи с этим важное значение приобретают гибкость и адаптируемость используемых программных средств обработки данных, способность их к быстрой настройке на решение новых задач.
В этих условиях поиск эффективной модели организации и обработки данных, позволяющей быстро сформулировать и обработать новые задачи без какой-либо длительной переналадки и трудоемкого программирования, является важной народнохозяйственной задачей, решение которой может оказать решающее влияние на эффективность всех АСУ.
По существу, речь идет о повышении "интеллектуальности" систем, упрощении языков общения человека и ЭВМ до такой степени, что функция ввода в ЭВМ заданий на поиск и необходимую обработку данных может быть передана непосредственно управляющему персоналу.
В последние годы в СССР и за рубежом большое внимание уделяется исследованиям и разработке эффективных моделей и методов обработки данных. Наиболее существенным достижением на пути к решению этих . проблем явилось выделение воп^бов описания, хранения и обновления данных в самостоятельную задачу, решаемую независимо от разнообразных прикладных задач и запросов пользователей. При этом появилась возможность анализа общей структуры информационного фонда АСУ, выявления всех взаимосвязей (отношений) между данными и описания этих взаимосвязей с помощью общей логической модели данных. Этот подход нашел свое отражение в так называемых системах управления базами данных(СУЩ), которые в последнее время развиваются очень активно.
Один из основных моментов организации базы данных - это создание её логической модели, являющейся формализованным представлением некоторой предметной области, интересующей пользователя. В настоящее время принято выделять три основных подхода к построению баз данных: иерархический, сетевой, реляционный. Иерархическая и сетевая модели появились раньше реляционной и нашли широкое применение в различных СУЩ. Обе эти модели достаточно хорошо описывают множество объектов и множество связей между этими объектами, существующих в реальном мире. Однако, в процессе эксплуатации реальных сие-
- Є -
тем скоро обнаружились недостатки этих подходов, главным из которых является недостаточная гибкость иерархических и сетевых моделей при отображении процессов роста и изменения базы данных.
Одно из основных положений диалектического материализма состоит в том, что непрерывный процесс движения (развития) в пространстве и времени является неотъемлемым свойством материи, способом её существования. С этой точки зрения любая модель предметной области (в том числе и реляционная) является лишь застывшим отображением некоторого момента времени и в следующий момент может уже не соответствовать действительности. Возникает необходимость' в непрерывной адаптации модели к изменяющимся условиям её эксплуатации.
Иерархическая и сетевая модели в общем случае препятствуют многим изменениям, необходимым при росте базы; рост базы может привести к излишней громоздкости и сложности эксплуатации этих систем. Изменения, происходящие в реальной предметной области приводят к "отмиранию" старых и появлению новых видов запросов к базе данных, что приводит к необходимости введения новых логических связей между элементами сети или дерева. Б итоге многие системы оказываются очень запутанными и громоздкими в эксплуатации, периодически возникает необходимость в полной реорганизации базы данных.
Реляционная модель свободна от этих недостатков. Она не накладывает никаких ограничений на допустимые изменения не только в самих данных, но и в их логическом представлении - логической схеме. Более того, пользователю предоставляется возможность образовывать любые новые отношения и уничтожать старые непосредственно в тексте своего запроса к базе данных, то есть с максимальной мобильностью следовать за изменениями, происходящими в реальной мире. Помимо этого реляционная модель обладает рядом других преимуществ, благодаря которым реляционный подход получает в настоящее время все большее распространение.
В силу своей перспективности реляционная модель была выбрана в качестве базовой при создании специализированного пакета прикладных программ, предназначенного для автоматизации проектирования типовых ; проектных решений подсистем и задач АСУП для предприятий химической промышленности, в разработке которого автор принимал участие.
При практической реализации реляционного подхода разработчики встретились с серьезными трудностями и проблемами, требовавшими своего разрешения. Аналогичные проблемы и недостатки реляционного подхода отмечались авторами различных цуБликаций по реляционным системам. Можно выделить следующие наиболее существенные препятствия на пути к практическому применению реляционной модели:
низкая эффективность использования оборудования и значительные затраты при прямом выполнении на ЭВМ реляционных запросов (операций реляционной алгебры);
класические операции реляционной алгебры не позволяют образовывать новые отношения из существующих, если для этого требуются логические и математические действия над атрибутами; в этих случаях приходится прибегать к языкам программирования, что резко ограничивает круг возможных пользователей для таких задач;
эффективность реляционной СУВД сильно зависит от физической организации данных и, следовательно, от искусства системного программиста (администратора данных) и его интуиции, так как отсутствуют какие-либо научно обоснованные рекомендации, методики или алгоритмы по вопросу конструирования реляционной базы данных на физическом уровне.
Автором выполнена научно-исследовательская работа, направленная на решение вышеперечислеиных проблем. Работа выполнялась в соответствии с планом ГКНТ при СМ СССР (пост. ЇШ42 от 17.12.75) в рамках создания типовых проектных решений по разработке АСУП в химической промышленности и в соответствии с тематическим планом научно-производственного объединения "Химавтоматика" (заказ-наряд 08-818204298).
В результате работы получены следующие новые теоретические и практические результаты, которые выносятся на запрту:
I. По новому поставлена и решена задача проектирования реляционной базы данных на логическом и физическом уровнях. Показана практическая непригодность существующих подходов. Предлагаемый вариант отличается от существующих тем, что планирование и оптимизация логической и физической схем реляционной базы данных осуществляется не на основе построения полной структуры функциональных зависимостей между атрибутами предметной области, а на основе проекта логической схемы задаваемого пользователем априори с указанием ожидаемых мощностей множеств и отношений.
В процессе решения этой задачи получено ряд новых теоретических результатов, имеющих самостоятельное значение. В частности:
- впервые показано, что на множестве схем отношений реляционной
базы данных существуют бинарные отношения второго порядка (отношения
отношений, которые превращают разрозненные схемы отношений в единую,
семантически связанную структуру (F-структуру). Доказано ряд теорем,'
определяющих свойства /^-структуры и являющихся теоретическим обос
нованием предложенного алгоритма, позволяющего проектировать базу
данных с оптимизацией по ряду критериев, задаваемых проектировщиком
в диалоговом режиме;
доказана целесообразность применения идеи дифференциальных файлов для последовательного метода доступа и, в частности, для физической организации базы данных. Выведено выражение для вычисления оптимального размера дифференциального файла в зависимости от размера основного файла базы данных;
впервые исследовано влияние порядка следования ключевых атрибутов в кортеже и кортедей в отношении на избыточность его физического представления и показано, что расстановка ключевых атрибутов в порядке убывания их весовых коэффициентов Я^ минимизирует эту избыточность. Найдены выражения для вычисления ох и коэффициентов сни-
жения избыточности (КСИ), позволяющие употреблять эти коэффициенты в качестве критериев оптимизации при автоматизированном проектировании базы данных.
2. Предложен новый метод реализации реляционных запросов (совокупности реляционных операций, решающих конкретную задачу) основанный на введенных автором понятиях шагового и операционного наборов кортежей и многоаспектной сортировки. Основные преимущества метода перед существующими:
инвариантность алгоритмов для всего класса задач, сводимых к совокупности реляционных операций. При практической реализации это означает, что реляционный запрос выполняется сразу после ввода в ЭВМ без каких-либо этапов настройки, трансляции или генерации программ;
ориентация на эффективное использование виртуальной памяти с минимальным её расходом (метод "комбайна");
распараллеливание вычислений в системах с мультипрограммированием и многопроцессорных системах.
В процессе разработки и реализации метода получены следующие дополнительные результаты, имеющие самостоятельное практическое значение:
предложено расширение реляционной алгебры, отличающееся тем, что кроме арифметических действий над атрибутами и встроенных функций вводится атрибут, вычисляемый по условию. Расширение осуществлено путем оригинального применения операции "вырезка" к результату любой другой операции.
введено понятие многаспектной сортировки и показано, что применение многоаспектной сортировки сокращает временные затраты тем больше, чем больше число аспектов М. , начиная с Н>.
разработаны синхронный и асинхронный методы организации параллельного вычислительного процесса при выполнении реляционных зап-
- w-
росов в многопроцессорных установках с виртуальной памятью.
Подробное изложение перечисленных результатов составляют содержание настоящей диссертации.
Диссертация состоит из введения, четырех глав и заключения.
Первая глава посвящена анализу общей структуры современных СУЩ и построению некоторой обощенной (типовой ) схемы СУЩ с выделением наиболее существенных функциональных блоков и интерфейсов.
Здесь вводится необходимая терминология, определяется место и роль различных моделей данных в общем процессе обработки данных. Приведенная в этой главе типовая схема СУВД является как бы "системой координат"для дальнейшего изложения. Именно в контексте этой обощенной схемы рассматриваются в последующих главах предлагаемые методы и алгоритмы, каждый из которых может быть отнесен к тому или иному интерфейсу или конкретному блоку системы.
В главе рассматриваются две проблемы, являющиеся предметом исследования в настоящей диссертации: проблема автоматизации проектирования реляционной базы данных и п&шема эффективной реализации реляционных запросов на ЭВМ. По каждой из п^блем проводится сравнительный анализ существующих решений и формулируется соответствующая задача для исследования.
Во второй главе рассматривается и решается первая из поставленных задач - задача построения оптимальной (для выбранной физической организации и критериев) логической и физической схемы базы данных. В главе приведено описание выбранного метода физической организации данных и его обоснование, вводится понятие F-структуры, дается её математическое описание и исследуется ряд свойств, предлагается алгоритм, решающий поставленную задачу.
Третья глава посвящена исследованию операций реляционной алгебры Кодца (РА ), как средства для решения задач обработки данных.
Совокупность операций РА относящихся к некоторой конкретной
задаче рассматривается как некая программа (РА -программа), подлежащая непосредственному выполнению на ЭВМ. На базе понятий ПШК и ОНК разработан эффективный алгоритм выполнения РА -программ, инвариантный для класса задач, сводимых к операциям РА . Главные преимущества алгоритма - однократный просмотр рабочего пространства и минимальный расход памяти при решении задач.
Операторы и переменные в РА -программах определяются и задаются таким образом, что в этих программах отсутствуют распознаватели и циклы, передача управления в РА -программах не зависит от исходных данных. Это позволило эффективно применить синхронную и асинхронную модели параллельных вычислений при реализации РА -прграмм в многопроцессорных системах. В третьей главе описан простой алго*-ч' ритм распараллеливания РА -программ и два возможных практических подхода (синхронный и асинхронный) к организации параллельного вычислительного процесса при выполнении РАК-программ в многопроцессорных системах с виртуальной памятью.
В четвертой главе приводится краткое описание конкретной системы (пакета прикладных программ СУРЭЗ), разработанной под руководством и при непосредственном участии автора, в которой практически реализованы и проверены в эксплуатации методы и алгоритмы, изложенные в главах 2 и 3. Система адресует свои средства непосредственно постановщикам задач, что оказало решающие влияния на разработку форматов языков пользователей. Для решения задач средствами СУРЭЗ пользователь пишет постановку (а не программу) почти в таком же виде, как она выглядит в проектной документации, и эта постановка после ввода её в ЭВМ непосредственно интерпретируется системой с получением необходимых результатов.
В главе подробно рассматривается общая архитектура системы и средства общения её с внешним миром (языки пользователей). Особое внимание уделено языковым и программным компонентам, реализующим реляционную алгебру в соответствии с подходом изложенным в главе 3.
Некоторое внимание уделено также санкции форматного вывода, реализация которой содержит ряд новых элементов и может предстаз -лять интерес для программистов.
Разработка первой версии системы закончена в 1982 году. Система принята в отраслевой фонд алгоритмов и программ (ШАП) Минхимпрома. Управлением автоматизации Шнхимпрома принято решение о широком применении системы при проектировании АСУ на предприятиях отрасли, в связи с чем организованы и проведены двухнедельные курсы по изучения СУРЭЗ специалистами отделов АСУП химических предприятий при Московском институте повышения квалификации руководящих работников и специалистов химической промышленности.
В настоящее время ППП СУРЭЗ применяется при создании АСУ на Киевском производственнмм объединении "Химволокно" - базовой площадке отрасли по отработке типовых проектных решений, в разработке АСУ Харьковским научно-производственным объединением " Монокристаллре-актив" и в ряде других проектов на различных предприятиях отрасли. Использование системы СУРЭЗ при проектировании только одной задачи по учету автомобильного транспорта на Киевском ПО "Химволокно" дало экономический эффект 28,3 тысяч рублей.
В приложениях к диссертации приведены документы, подтверждающие внедрение полученных в диссертации научных результатов и их экономическую эффективность, а также результаты проведенных экспериментов и распечатки, иллюстрирующие работу основных компонентов системы СУРЭЗ.
