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

Введение.4.

1. Анализ систем и постановка задачи.

1.1. Трехуровневая концепция и обощенная схема СУЩ.<

1.2. Модели данных.£

1.3. Проблема автоматизации проектирования схемы базы данных.

1.4. Проблема эффективной реализации реляционных запросов.

1.5. Выводы.

2. Методы и алгоритмы проектирования лгической и физической схемы реляционной базы данных с помощью ЭВМ.

2.1. Выбор физической организации базы данных рассматриваемого класса задач. .hS

2.2. F -структура и её свойства.

2.3. Алгоритм.

2.4. Пример работы алгоритма.

2.5. Выводы.SO

3. Методы реализации операций реляционной алгебры Кодца в однородных вычислительных системах.

3.1. Некоторые предпосылки.

3.2. Операции реляционной алгебры и некоторые замечания о методах их реализации.Si

3.3. Общее описание метода.

3.4. Декомпозиция задачи на этапы.

3.5. Метод выполнения реляционных операций в однопроцессорной системе.

3.6. Оценка эффективности предложенного метода.114"

3.7. Методы выполнения реляционных запросов в многопроцессорных системах. 1IQ

3.8. Выводы,

4. Реализация./

4.1. Общее описание системы.

4.2. Основные потоки данных в системе.Трехконтурный принцип.

4.3. Конструирование базы данных./544.4. Язык манипулирования данными./58.

4.5. Реализация методов манипулирования данными в СУРЭЗ./

4.6. Форматный вывод./

В числе узловых проблем развития народного хозяйства нашей страны на современном этапе ХХУ1 съездом КПСС названы ускорение научно-технического прогресса и дальнейшее совершенствование управления экономикой.

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

Центральный звеном любой АСУ является система обработки данных с помощью электронных вычислительных машин OEM). Объем перерабатываемой информации в современных крупных АСУ непрерывно возрастает и достигает в настоящее время порядка 800 мегабайт для одной АСУ. Вся эта информация непрерывно обновляется с целью поддержания её в актуальном состоянии.

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

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

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

В последние годы в СССР и за рубежом большое внимание уделяется исследованиям и разработке эффективных моделей и методов обработки данных. Наиболее существенным достижением на цути к решению этих . проблем явилось вццеление воп^ов описания, хранения и обновления данных в самостоятельную задачу, решаемую независимо от разнообразных прикладных задач и зацросов пользователей, фи этом появилась возможность анализа общей структуры информационного фовда АСУ, выявления всех взаимосвязей (отношений) между данными и описания этих взаимосвязей с помощью общей логической модели данных. Этот подход нашел свое отражение в так называемых системах управления базами данных(СУВД), которые в последнее время развиваются очень активно.

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

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

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

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

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

Автором выполнена научно-исследовательская работа, направленная на решение вышеперечисленных проблем. Работа выполнялась в соответствии с планом ГКНТ при СМ СССР (пост, !l"542 от 17.12.75) в рамках создания типовых проектных решений по разработке АСУП в химической промышленности и в соответствии с тематическим планом научно-производственного объединения "Химавтоматика" (заказ-наряд 08-818204298).

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

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

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

- впервые показано, что на множестве схем отношений реляционной базы данных существуют бинарные отношения второго порядка (отношения отношений, которые превращают разрозненные схемы отношений в единую,, семантически связанную структуру (F-структуру). Доказано ряд теорем,' определяющих свойства /^-структуры и являющихся теоретическим обоснованием предложенного алгоритма, позволяющего проектировать базу данных с оптимизацией по ряду критериев, задаваемых проектировщиком в диалоговом режиме;

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

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

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

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

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

- распараллеливание вычислений в системах с мультипрограммированием и многопроцессорных системах;

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

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

- введено понятие многаспектной сортировки и показано, что применение многоаспектной сортировки сокращает временные затраты тем больше, чем больше число аспектов М , начиная с H>Z.

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

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

Диссертация состоит из введения, четырех глав и заключения.

3.8. ВЬВОДЫ

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

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

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

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

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

4. РЕАЛИЗАЦИЯ

В настоящей главе содержится краткое описание архитектуры и основных компонентов конкретной промыпленной системы обработки данных - пакета прикладных программ, предназначеного для автоматизации проектирования и управления решением задач экономического и управленческого характера (ППП СУРЭЗ).

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

Целью создания системы СУРЭЗ, определенной в техническом задании на её разработку, являлась автоматизация процесса проектирования и решения задач обработки данных в разрабатываемых АСУ предприятий министерства Химической промышленности. Ставилась задача избавится от длительного и трудоемкого процесса написания и отладки программ на алгоритмических языках для решения простых экономических задач, а сделать понятной для ЭВМ непосредственно постановку задачи.

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

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

Таким образом, система адресует свои средства непосредственно постановщикам задач. Для решения задачи средствами СУРЭЗ пользователь пишет постановку (а не программу) почти в таком же виде, как она выглядит в проектной документации, и эта постановка после ввода её в ЭВМ интерпретируется системой как некая программа (РА-программа) и сразу же выполняется системой с получением необходимых результатов.

Первая версия системы, переданная в отраслевой фонд алгоритмов и программ в 1981 году, реализована в операционной системе ОС ЕС на алгоритмических языках PLji и Кобол. В качестве рабочего пространства в первой версии используется внешняя дисковая память. Автору принадлежит разработка общей архитектуры системы, внешних спецификаций, языка манипулирования данными, а также разработка и отладка программ планирования схемы базы данных и реализации языка манипулирования данными.

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

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

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

4.1. ОЩЕЕ ОПИСАНИЕ СИСТЕМЫ

Учитывая прикладную направленность описываемого пакета программ, в СУРЭЗ применяется несколько отличающаяся от реляционной и более привычная пользователям терминология.

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

В ППП СУРЭЗ такие имена называются внешними. Наряду б|внешшми именами существуют внутренние имена, более короткие и удобные для обращения к даннш. Внутренние имена множеств представляют собой слова не более чем из пяти символов: "цех ,", "табн " и т.д.

Внутреннее имя входного сообщения имецуется в пакете шифром входного сообщения (1ДВС), для обозначения которого принято сочетание двух букв латинского или русского афавита: ОП ,/4/3, EF Термин атрибут употребляется в ППП СУРЭЗ в том же смысле, что и в реляционной терминологии, однако, "наряду с ятим термином употребляется термин "реквизит" или "реквизит сообщения", которые следует рассматривать как синонимы термина "атрибут". Для обращения к кокретноцу реквизиту кокретного сообщения служит имя реквизита, которое образуется из шифра сообщения с добавлением двухзначного порядкового номера реквизита. Например AB0I есть имя первого атрибута из входного сообщения АВ, £/16 - имя шестнадцатого атрибута из сообщения £ F .

С помощью внешних и внутренних имен множеств, сообщений и атрибутов пользователь ППП СУРЭЗ описывает логическую схему базы данных, а также использует их при маницулировании данными.

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

Как ввдно из рисунка, СУРЭЗ имеет четко вьраженцую трехуровневую архитектуру.

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

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

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

В качестве рабочего пространства в первой версии ППП СУРЭЗ выступает так называемый Файл сообщений, представляющий экземпляры данных на логическом уровне. Зцесь и только здесь данныз представлены в виде нормализованных отношений, точно совпадающих т{дм инцстрвтер.

Six St/ 3

Программы чнатескои с.кмы

Системный курная ftp ozp анны доступа So.3-е ъ&ннб'Ы-(сру ЛУ) I I

Фай 4

ХзаЭа* / S

W///A

Генератор программ бёода.

Программы контроля, и сор-pexstris/>o6/ei*

-а npotpAMMH евоз^ - (б/Мл. внешний И

Цаиоку/шроСяни*. I Пот 3oga.mt.fii-/ -^^tnpetpaMHuemr^— I I

Y2 форматный ёи&оЭ

Отчеты

Внутренний уровень fcpyj \ Логическии. уровень (ЛУ) [

Внешни и уровень (ВУ)

Рис.28. Структурная схема системы СУРЭЗ с их логической схемой, здесь они доступны для обработки средствами языка манипулирования данными.

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

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

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

Внешний уровень представлен в СУРЭЗ ДЕумя компонентами: системой ввода, контроля и корректировки вводимых данных и комплексом программ форматного вывода. Основным структурным интерфейсом здесь является внешний файл. Порядок размещения атриСутов во

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

В ППП СУРЭЗ принят метод раздельного хранения текстовых и цифровых данных. При вводе данных из вшшнего уровня на логический происходит отбор текстовых атрибутов в отдельную словарную базу (см. интерфейс 7 на рис. 28 ), а на их место в сообщении записывается адрес хранения текста в словарной базе. При выводе сообщения во внешний файл происходит обратный шэоцесс: по имеющемуся в сообщении адресу текст вытаскивается из словаря и присоединяется к выводимоцу сообщению.

Такой подход является возможнш и целесообразным в ощу того, что в экономических и упраленческих задачах текстовая информация не подвергается каким-либо преобразования или вычислениям, а в операции сравнения её вполне может заменить цифровая свертка (хеш-код). В ППП СУРЭЗ такая свертка используется в качестве адреса хранения информации в словарной базе. Таким образом, длинные текстовые "хвосты" не присутствуют в ВД и не*участвуют в процессе манипулирования данными, благодаря чецу экономится и память и машинное время.

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

Все компоненты системы СУРЭЗ размещены в трех библиотечных наборах данных: библиотеке загрузочных модулей ^VRZA , библиотеке процедур SURPR и библиотеке эксплуатационных документов SURD0K. Эти библиотеки находятся на дистрибутивной ленте, поставляемой пользователям. На этой же ленте находятся все необходимые задания для сброса системы на диск и подготовку к работе.

4.2. ОСНСВНЬЕ ПОТОКИ ДАННЫХ В СИСТЕМЕ . ТРЕХКОНГУРНЫЙ ПРИНЦИП.

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

Элементарный анализ задач АСУП позволяет утверждать, что в АСУП существует довольно много задач ( около 60© при решении которых обрабатывается большой поток входных сообщений, необходимых только для того, чтобы выполнить некоторьв элементарные арифметические действия и получить итоговые данные небольшого объёма. После этого основная масса данных больше не цужна, а для дальнейшей обработки и хранения используются только полученные результаты. В этом случае действия по занесению всех обрабатываемых данных в Щ и последующая их обратная выборка для решения задачи выглядит как бессмысленная потеря времени. Кроме того, значительная часть циркулирующих в АСУ данных, несмотря на довольно большой период хранения, имеют низкую степень использования (один раз за период и только одной задачей) и целесообразность занесения их в Щ должна быть тщательно проанализирована. И, наконец, данные, имеющие длительный период хранения и многократно используемые в различных задачах составляют всего около ЗС$ обрабатываемой информации. Целесообразность их хранения на физическом уровне в базе данных не вызывает сомнений.

Исходя из вышеизложенного при разработке общей архитектуры ППП СУРЭЗ реализован принцип трехконтурности системы, который состоит в следующем: система предоставляет пользователям средства, с помощью которых обрабатываемые данные могут быть разделены на три потока - те, которые присутствуют только на внешнем уровне и обрабатываются только средствами ввода и вывода ( с возможностью выполнения элементарной арифметики и накопления итогов); те, которые заносятся на логический уровень для обработки развитыми средствами языка маницулирования данными (совместно"с данными хранящимися в Щ); и, наконец, те данные, которые заносятся в Щ для длительного хранения и обновления и вызываются на логический уровень по запросу пользователя для совместной обработки,

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

Трехконтурный принцип в самом общем виде проиллюстрирован на рис. Z9а. фи проектировании ППП СУРЭЗ трехконтурный принцип был осуществлен путем обеспечения соответствующих интерфейсов между компонентами системы. Остановимся подробнее на всех возможных потоках данных в СУРЭЗ, показанных на рис.Я9^.

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

Входные да. нные фазичвс/саи уровень Логический уробемь виешнаи уробем}

Система обработки, данных: а

Ьыхсдные данные V С

SJ

JL Q

Рис.29. Прищип трехконтурности: а) общая схема, б) реализация в пакете прикладных программ СУРЭЗ. чего преобразование их в логическую структуру не производится, а сразу же осуществляется обработка их средствами форматного вывода (см. рис.£9<Г). Кроме получения требуемого отчета, интерпретаторы форматного вывода позволяют получать итоговые показатели и выполнять арифметические действия над атрибутами. Этого часто достаточно для решения многих простых задач оперативного учета и анализа. Результаты решения подлежащие хранению или дальнейшей обработке формируются в структуру внешнего файла и могут быть записаны в ВД обычным цутем. сть исходных данных из внешнего файла поступает в файл сообщений и здесь происходит их обработка с помощью языка манипулирования данными. В этот же файл предварительно могут быть вызваны для совместной обработки данные, ранее записанные в ВД. Любш результаты, как промежуточные так и окончательные, по указанию пользователя могут быть выведены на внешний уровень для распечатки и (или) переданы на внутренний уровень для записи в ВД.

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

-

4.3. КОНСТРУИРОВАНИЕ ШЫ ДАННЫХ

В соответствии с подходом изложенным во второй главе, первьм шагом в процессе конструирования базы данных является определение проекта логической схемы. В ППП СУРЭЗ администратор описывает схему базы данных пользуясь специальным бланком, показанным на V} рис. 30 . На бланке последовательно, одно за одним описываются все сообщения, которьв предполагается хранить в базе данных, либо обрабатывать в файле сообщений (сообщения, которыз обрабатываются только на внешнем уровне можно не описывть). Каждое сообщение содержит группу показателей (атрибутов сообщения), описывающих реальные объекты предметной области или их свойства.

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

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

Содержимое заполненного бланка переносится на машинный носитель и служит исходнш текстом для процедуры gfnlfp . Эта цро-цедура реализует алгоритм описанный во второй главе. Процедура обеспечивает: йШ 1 г ts! Ж

Наименование ?хо9мо^о соо5а{еиия и ре^&иьитоб ш имя множее-К тЬа i to giL-lto*! 1 I I l—i

0|3 iGtg(/7jggHiCi0i^ibitfi |Ci4|e'mi

JLJL-t—l I I I 9 I I I I a 1 I M

Q|g ^ifxiyipi ifiipiQiU Ji^Qi^icjmi^eiHirikirt i3iq[n7|piai^

111' I | |l ' I I.UL

M 11 i j i i i 11 i i i i j 111 I} i i M

I M 1 . I I I I [ I I I I .I 1 t,^ I I I I I I I I I lb|0>М|с|к[КГ(у7|Л|т'у|р|i4| |сгп]а1гр|в|й lpi^l^iMit

-LX

JL

J-JL

I M I

1 Utepct i H. i £ Щп»з| г .V. I £.

Ll lilMOi

I 3 о

J—L c\mh ill

JL

PuC.^ fS6

1. Ввод подготовленного описания логической схемы и запись её на магнитный носитель.

2. Анализ логической схемы и выполнение дейстшй по её оптимизации, преду смотренных шагами 2*5 алгоритма.

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

4. Проектирование физической схемы в соответствии сшагами 7 т- 9 алгоритма и запись её на носитель.

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

Текущие характеристики каящого файла (количество записей, состав сообщений, пароли) а также сведения о последнем и предпоследнем обращении к нему (дата, фамилия пользователя, тип действия) также хранятся в физической схеме, которая в ППП СУГОЗ называется системным журналом. Пользователю (администратору Щ) предоставляется возможность внесения изменений в системный журнал.

Диалог с администраторм Щ осуществляется через дисплей либо через печатающее устройство и ПМ-консоль, причем администратору предоставляется возможность после любого законченного этапа внести изменения и начать процесс либо сначала, либо с любого предыдущего этапа. Рис. 31 иллюстрирует процесс конструирования Щ, осуществляема процедурой G£NLFP , Как ввдно из рисунка, прцедура имеет три точки входа, позволяющие начать работу с распечатки и внесения изменений в уже существующую логическую или физическую схец? Щ.

ЗАКЛЮЧЕНИЕ И РЕКОМЗВДАЦИИ

В работе рассмотрены наиболее существенные вопросы построения системы обработки данных в АСУ предприятия, основанной на реляционной модели данных.

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

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

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

Исследование влияния порядка следования атрибутов в ключе на физическую избыточность отношения позволило автору определить понятие весового коэффициента ключевого атрибута и показать, что перестановка ключевых атрибутов в порядке убывания их весовых коэффициентов минимизирует избыточность хранения отношения на физическом уровне. Введено также понятие коэффициента снижения избыточности базы данных,(КСИ), достигаемого при изменении порядка ключевых атрибутов, объединении отношений и построении древовидных физических структур. Найдены соответстЕующие выражения для вычисления и КСИ. Наличие в проекте лшчвской схемы числовых оценок позволяет вычислять и КСИ непосредственно в процессе проектирования Щ, используя их в качестве критерия при автоматическом поиске оптимальных вариантов и для принятия решения администратором в процессе диалога.

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

Прежде всего, следует отметить расширение возможностей реляционной алгебры цутем введения нового понятия: проекции результата на целевой список пользователя - R[w] . Такая модернизация совершенно не изменяет сгути реляционных операций, однако резко повышает их "вычислительную силу" - новое отношение может быть порчено с применением арифметических и логических действий над атрибутами. Это дает возможность с помощью расширенных операций РАК реализовывать алгоритмы решения большинства задач, используемых в АСУ предприятий (за исключением тех, которш требуют примене-шя специальных математических методов).

В диссертации показано, что выполнение любой операции РАК можно представить как циклический (периодически повторяющийся) процесс, где на казвдом шаге цикла выполняется одна и та же последовательность действий над некоторой совокупностью кортежей из отношений-операндов, в результате чего получается одна порция результата. Совокупность кортежей, необходимых для выполнения одного шага операции названа автором шаговым набором кортежей (ШНК), а совокупность всех ШНК, необходимых для полного выполнения одной операции получила название операционного набора кортежей (ОНК).

Главная идея предложенного метода реализации операций РАК в ЭВМ состоит в доказательстве возможности выполнения любой операции РАК или даже любой совокупности несвязанных операций РАК цутем однократного просмотра некоторого рабочего пространства -участка оперативной, виртуальной либо дисковой памяти, вмещающей только все кортежи операндов и ничего более. Э1?Ь достигается цутем создания в рабочем пространстве памяти последовательности ОНК, каждая из которых содержит последовательность ШНК. Создание такой последовательности осуществляется с помощью предложенного автором метода многоаспектной сортировки.

Однократность просмотра рабочего пространства, а также некоторые свойства операций РАК определили следующий существенный момент предложенного метода реализации операций - запись результата осуществляется в том же (просматриваемом в данный момент) рабочем поле на уже просмотренный ранее участок памяти. Это позволяет отказаться от необходимости выделения какой-либо дополнительной памяти кроме той, которая требуется для размещения исходных данных.

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

Метод "комбайна"открыл новые возможности для дальнейшего усовершенствования модели. Показано, что при таком подходе некоторые операции РАК (ОБВДИНЕНИЕ, ПЕРЕСЕЧЕНИЕ, РАЗНОСТЬ) алгоритмически представляют собой частные случаи операции СОЕДИНЕНИЕ. Это позволило сократить количество алгоритмов,интерпретирующих операции , до четырех. Сущность этих алгоритмов вытекает из понятия ШНК.

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

Несмотря на такую простоту, РА -программы позволяют решать алгоритмически сложные задачи с разветвленной логикой. Это объясняется тем, что все условия и циклы как бы "спрятаны" в узлах граф-схемы (то есть вцутри операций РАК).

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

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

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

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

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

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

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

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

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

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

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

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

Трехконтурный принцип в полной мере реализован в первой версии ППП СУРЭЗ щтен создания необходимых интерфейсов на всех уровнях.

Манипулирование данными в системе СУРЭЗ осуществляется с помощью алгоритма выполнения РА ,-программм в однопроцессорной ЭВМ, описанного в разделе 3.5 настоящей диссертации. Универсальность алгоритма, инвариантность по отношению к конкретным задачам, небольшое число реляционных операций позволили создать на его основе язык очень высокого уровня (DML ), который, тем не менее, не переводится на какой-либо внутренний язык (типа ассемблера), а выполняется в режиме интерпретации. Эксплуатация языка -DML показала достаточность его изобразительных средств для решения большинства задач, психологическую естественность операторов и быструю осваивавмость языка постановщиками задач. Несмотря на столь высокий уровень, очевидно, что на базе Ш1, (а точнее, на базе внутренней формы его представления в виде РА ^-программы) можно построить различные языки ещё более высокого уровня, по отношению к которым HML будет играть роль ассемблера. Эти языки не обязательно должны быть построены на основе реляционного исчисления. Единстве ннш обязательным условием является наличие алгоритма редукции, сводящего предложения этих языков к набору операций реляционной алгебры.

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

Внедрение пакета прикладных программ СУРЭЗ на предприятиях министерства Химической промышленности показало его достаточно высокую эффективность, что подтверждается актами, приведенными в приложении

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

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

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

1. Материалы ХХУ1 съезда КПСС. М., Политиздат, 1982г.2. (\US\/хз/SPARC study Otoujo on da/e Sase Мела^етелё tyste/rrs1 Inleilrrt gepozl. Baft of ACM ClGtfOP, /973, 7. А/г

2. ЛЕНИН В.И. Философские тетради. М., Политиздат, 1978г., стр.163.

3. ОЛЛЕ Т. В. Предложения КОДАСИЛ по управлению базами данных. iJep. с англ. В. И.Филиппова и С.М.Кругловой. М.: Финансы и статистика, 1981.

4. Cham/oine С. Л. Си-ггед-/ Trends гп Date 'Base tfystestzs. Соm/ou-£es , May /9?9, />. 27~4q,

5. Codd F.F. A Refectc-onaC of 2>a6e. fa сСъг^г Shaded

6. Comm. JCM, l3,4(t9?oJ, />■ SJ7-387.

7. Codcl f.F. A Base ^uSFarr^ua^e, Tourrd^d w r/Ле PeAz&bsraJ

8. CaCcue^s, Рго* . /97/, 4CM SiariDfT Workshop, />. SS-36.

9. Attl^tzuny Ш. И/. g-6 г of Ра^-с. -SW Фе&п/слsht'pj. T/tf01. Смраы, p.S&O.

10. НЕКЛЮДОВА E.A., ЦАЛЕНКО М.Ш. Синтез логической схемы реляционнойбазы данных, Программирование, 1979, № 6. 14. ^eeat С. Р. А. ^ А/. А. I* £ г ос/иа -6 -to2.a~io- Ъа-Se. AAorma £ijca~6ro/9 ^ог^, о/ 4бЬ Conf. он

11. Ve-гу Дг^ 2Wa 3as<s f Ц/ч-st gepte*? 6ет> /3.

12. Тэ. Уасц'п g, <//,<=> ^eco/rtfost'/t'ov lAezso>s tfr-e Synt^st;*. Л/о/аг&^сА:io Sdafagase — Pzo<t. Сэл/, on

13. XazffC Sdatar Sases . T^cyo, *9?7, />. 4У/-rre.

14. Ts£o*> z S. 4» tfrf/, Sfrv/iCiet-Ct; foz1. Ttezc/ tfeta W^&jft ^/aw

15. Tunefrowt Aoe.of 2»t. А*»/. О* Fast ft* ft, W.17. В

16. Vest$/> of ma £ ^ Scfttmes. ACM Jtq»S .e.ff VbaicLgose , /9?9, v. 4, nj, />■ So-s9.

17. Реляционные и сетевые модели баз данных: языки и вопросы реализации. Тезисы докладов семинара РГБД. г. Шрну, 1979.

18. ВОЛШЕНГАГЕН В. Э., КУЗИН JI. Т., САРКИСЯН В. И. Реляционные методы проектирования банков данных. К., Вища школа, 1979.

19. ПДЛЕНКО М.Ш. Реляционные модели баз данных (обзор). В сб.: Алгоритмы и организация решения экономических задач. Вып. 9,10. М.: Статистика, 1976.

20. КУЗИН JI. Т. Основы кибернетики^ Т.2. М.: Энергия, 1979.

21. ДРИБАС В. ППРеляционные модели баз данных. Минск, БГУ, 1982.

22. АХО А. ,Х0ПКР0ФТ ДЖ.,УЛЬМАН ДЖ7 Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

23. КОПЕЙКИН М.В.,ОСМОЛОВСКИЙ Л.Г.,ПЕТУХОВ О.А. Линейная модель базы данных. В кн.: Проблемы системотехники и АСУ. Л.: СЗПИ, 1980.

24. КОПЕЙКИН М.В.,ОСМОЛОВСКИЙ Л.Г., 1ЕТУХ0В О.А. Обобщенная модель базы дагных. В кн.: Проблемы системотехники и АСУ. JL : СЗПИ, 1980.

25. ГЛУШКОВ В. М. и др. Обработка информационных массивов в автоматизированных системахбуправления. Киев, Наукова думка, 1970.

26. ЗАЙЦЕВ Н.Г. Общесистемное математическое обеспечение ЭВМ третьего поколения для обработки данных. М.: Статистика, 1980.

27. МОРОЗ В.В. Об одном языке описания технико-экономической информации. УСиМ, № 5, 1979.

28. БЕЗРУКОВ Н.Н. ,ВЕРНЙК JI.B. Ореализации языка обработки данных, основанного на реляционной модели Кодда. УСиМ, № 2, 1980.

29. ГЛУ1Ж0В В. М., БАКАЕВ А.А. ,КРАМАРЕНКО Р. П. Система управления базами данных "ПАЛЬМА". УСи1^ № 5, 1980.

30. ИЛЬИНСКИЙ Н.И.,КУЗИН Л.Т. ,СТРИЖЕВСКИЙ B.C. Интеллектуальная система программирования. В кн.: Вопросы кибернетики. Вып. 55.

31. М.: АН СССР, 1979, с. 93 131.

32. СТОГНИЙА.А. и др. ^ловеко-машинная система решения задач обрабо тки данных. В сб.: Алгоритмы и организация решения экономических задач. Вып. 14. М.: Статистика, 1980.

33. КАЛЬНИНШ Г. И. Формализованный синтез программ обработки данных

34. АСУ методом подстановок. УСиМ, № I, 1980.

35. Kirn \U. feiatton^ System. Comp. Sfcr??.,197 9, V./f, Л/3, f. /SS-3/Z.

36. U). f, %<> &t.ttPrze£ ^>a.6aSaie Systems: £-£a ncl ~Jode*.y.-In: 1F1P lufotinckiiori Jo&yo -Meeiavne, (<9hot p. 36S-J&/.

37. Soop К. y Sfimnteot? P.j iVtKtozrt-. <C. Eл Pefe-tc'or&g

38. Date- base. Systems- . °J COiVS-tV/cj &y TOU J. Г.,

39. Plenum Pzcss f /974, />./03-//7.

40. ГОЛОВКИН Б.А. Параллельная обработка информации, программирование, вычислительные методы, вычислительные системы. Изв. АН СССР. Техническая кибернетика, № 2, 1979.

41. САВИНКОВ В.М. ,КА30Р0В М. С. ,РЫСЕВИЧ Ю.К. Использование систем управления базами данных в АСУ. В сб.: Алгоритмы и организация решения экономических задач. Вып. 13. М.: Статистика, 1979.

42. МАРТИН ДК. Организация баз данных в вычислительных системах. М.: Мир, 1980.

43. ТИМОФЕЕВ Б. Б., ЛИТВИНОВ В. А. Технология обработки данных в АСУП. Киев: Техника, 1978.

44. Цроектирование структуры внутримашинной информационной базы АСУ. Калинин: Центрпрограмсистем, 1979.

45. БАРТКУС А.-А. Т. ДИЛИНСКАС Р. Г. Сравнение различных структур данных по эффективности поиска. УСиМ, № 5, 1980

46. Я. У. Setre JoUa* Ш Jdiffe^tcad fi£*s : Лес*l о Ut Matte, па r?se of /ал^> ДсЖ J3a^es. J СА/ fzanScacAcon on QccUiase Systems, Vo?. ^ /УЗ, SepiemSez p.

47. КАЛИНИЧЕНКР Л.А. ,РАМВДЛГ A.E. Логика отображения сетевой модели данных в реляционную. Программирование, Р 2, 1979.

48. РАЗМЫСЛОВ Ю.П. ЯзбкА%-/в реляционной модели Кодца. В сб.: Алгоритмы и организация решения экономических задач. М.: Статистика, 1978, № II.

49. ЯКИМЧУК П. С. К вопросу использования концепции базы данных в АСУП. В сб.: АСУП 80. М.: НИИТЭХИМ, 1980.

50. ХАРДИ Г.Х. и др. Неравенства. М.: 1948.

51. ЯГЛСМ И.М. Математические структуры и математическое моделирование. М.: Сов. радио, 1980.

52. ХОТЯШОВ Э.Н. и др. Система обработки экономической информации на ЭВМ. М.: Статистика, 1969.

53. ЗАЙЦЕВ Н. Г. Информационное и математическое обеспечение АСУП. Киев: Техника, 1977.

54. БАКАЕВ А. А., СКЛЯРОВ А.В. ,Л03НИЦА А. С. Проектирование и организация операционных систем АСУ. Киев, Техника, 1978.

55. ЮЩЕНКО Е. Л. и др. ЯОД-75 система решения задач обработки данных. В кн.: Программное обеспечение задач АСУ и ЭВМ. М.: ЦСУ СССР, 1975.

56. ГЛУПКОВ В.М.,ЦЕЙТЛИН Г.Е.,ЮЩЕНКО Е.Л. Алгебра. Языки. Программирование. Киев: Наукова думка, 1978.

57. КОРОЛЕВ М.А. Обработка экономической информации на электронныхмашинах. М.: Экономика, 1965.

58. ГРЕЙСУХ В.Л. К построению математической модели обработки данных. В кн.: Цы|)ровая вычислительная техника и программирование.1. Вып. 8, 1974.

59. ПОСПЕЛОВ Д.А. Введение в теорию вычислительных систем. М.: Сов. радио, 1972.

60. ГОЛОВКО Г. П. ,ЯКИМЧУК П. С. и др. Решение комплекса задач по материально-техническому снабжению в условиях АСУП на системно-ориентированном уровне математического обеспечения. Механизация и автоматизация управления, № 5, 1975.

61. ГОЛОВКО Г. П., ШЕМЕТ Г. К. ,ЯКИМЧ/К П. С. Информационное и математическое обеспечение АСУП, ориентированное на применение банка данных. В сб.: Организация банков данных. М.: МДНТП, 1975.

62. КНУТ Д. Искусство программирования для ЭВМ. Том 3. Сортировкаи поиск. М.: Мир, 1978.60. iPi-i&ty V. К. Л Re-Ealionai /?<у{е Mznaptmerrt Syjien?. /гг/о*/nation SpsUw. Ргос оf C'OJMS-iV/£d. ty ?Ol/ lffPte»ent p^u,1W, p.SJ-66.

63. КОТОВ B.E. ,НАРИНЬЯНИ А. С. Теория параллельного программирования. Кибернетика, № 1,2,3,5, 1974.

64. ЕРШОВ А. П. Теория программирования и вычислительные системы. М.: Знание, сер. Математическая кибернетика, 1972.

65. ТРАХТЕНГЕРЦ Э.А. Программное обеспечение автоматизированных систем управления. М.: Статистика, 1973.

66. ЛАВРОВ С. С., ГОНЧАРОВА Л. И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971.

67. ЖЕНЬ Ю.М. и др. Программирование на ЯРО в ЕС ЭВМ. М.: Статистика, 1977.

68. Пакет прикладных программ "Система вывода" (ПППСВ). Калинин, НЕЮ "Центрпрограммсистем".

69. РЕДЬКО В. Н. Композиции программ и композиционное программирование. Программирование, 1978, № 5, с. 3 - 23.

70. РЕДЬКО В.Н. Основания композиционного программирования. -Программирование, 1979,И- 3, с. 3 13.

71. РЕДЬКО В.Н. Семантические структуры программ. Программирование, 1979,№1, с. 3 - 19.

72. БАСАРАБ И. А. Именные модели баз данных. В кн.: Модели и системы обработки информации. Киев, Выща школа, 1982.

73. БАСАРАБ И.А.,РЕДЬКО В.Н. Базы данных с логико-функциональной точки зрения. Программирование, 1984, № 2.

74. БИРЕКОВ А. Д. , ЯКИМЧУК а С. и др. Типовыэ проектные решения в АСУП Обзорная информация. СЕРИЯ: Системы и средства автоматизации химических производств. М.: НИШЭХИМ, 1976.

75. ЯКИМЧУК П. С. Математическое обеспечение типовых проектных решений АСУП на основе банка данных. В сборнике тезисов докладов научно-технической конференции молодых ученых и специалистов ОКБА. Северодонецк: ОКБА, 1977.

76. ЯКИМЧУК П.С.,САНИН В.Ф. Реализация формализованного запроса к базе данных на магнитной ленте в типовом математическом обеспечении ТГР. В сб.:Тезисы докладов научно-технической конференции молодых ученых и специалистов ОКБА. Северодонецк: ОКБА, 1976.

77. ЯКИМЧУК П.С. /"-структура и алгоритм планирования логической и физической схемы реляционной базы данных. Программирование, 1982, № 4.

78. ЯКИМЧУК П. С. Реализация операций реляционной алгебры в однопроцессорных и многопроцессорных системах с виртуальной памятью. -Информационный бюлетень СЭВ по химической промышленности.

79. М.: Секретариат СЭВ, 1982, № 5.- 19Z