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

• Автор: Майер, Юрген
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 121 c. : ил.

Содержание
ВВЕДЕНИЕ. У

Глава I. ПОСТАНОВКА ЗАДАЧИ КАНОНИЧЕСКОГО СТРУКТУРИРОВАНИЯ.

1.1. Основные определения .

1.2. Постановка задачи канонического

структурирования

1.3. Методы канонического структурирования

Шводы по главе I

Глава П. ГРАФ КОНЦЕПТУАЛЬНОЙ СХЕМЫ

2.1. Представление концептуальной схемы

в виде ориентированного графа

2.2. Взаимосвязь структуры графа концептуальной схемы и нормальных форм
2.3. Связность графа концептуальной схемы
2.4. Формирование матрицы путей графа концептуальной схемы
2.5. Формирование матрицы расстояний графа
концептуальной схемы . и
2.6. Матрица расстояний и ее оптимальная
реализация
2.7. Минимально эквивалентный граф концептуальной схемы .
Выводы по главе П
Глава Ш. МЕТОД КАНОНИЧЕСКОГО СТРУКТУРИРОВАНИЯ.
3.1. Общая схема метода канонического струк
стр.
турирования
3.2. Формирование локальных схем пользователей
3.3. Формирование концептуальной схемы первой нормальной формы6
3.4. Построение графа концептуальной схемы
дг .
3.5. Построение оптимальной реализации ма

З.б. Формирование концептуальной схемы
3.7. Области использования метода канонического структурирования и направления его
усовершенствования . г
Выводы по главе Ш .
Глава 1У. РЕАЛИЗАЦИЯ МЕТОДА КАНОНИЧЕСКОГО СТРУКТУРИРОВАНИЯ .
4.1. Комплекс программ М
4.2. Методические вопросы использования ме
тода канонического структурирования 4.3. Некоторые вопросы формирования схем
хранения базы данных .
Выводы по главе 1У.
ЗАКЛЮЧЕНИЕ Ю
СПИСОК ЛИТЕРАТУ


Метод позволяет проектировать отношения концептуальной схеиы второй нормальной формы Кодца баз данных больших размерностей с учетом количественных параметров использования данных. Разработаны алгоритмы анализа графа концептуальной схемы, позволяющие провести проверку принадлежности концептуальной схемы второй нормальной форме Кодда. Данные алгоритмы имеют вычислительную сложность не превышающую 0(п(п+т)) , где п -количество отношений концептуальной схемы, а >*? ОССпгт)*) . Разработан алгоритм нахождения оптимальной реализации матрицы расстояний, позволяющий решать задачу проектирования сетей с минимальной суммарной протяженностью при условии, что каждая вершина сети достижима из произвольной заданной вершины по пути, длина которого не превышает заданную величину. Разработанный алгоритм имеет вычислительную сложность 0(п ) , где /? Программно реализован автоматизированный метод канонического структурирования. Спроектированы концептуальные схемы баз данных информационных систем специального назначения в ГВЦ МВД ГДР с использованием разработанной программной системы. Реализация результатов работы. ГДР. На основании полученных результатов разработан комплекс программ, реализующий разработанный метод определения концептуальных схем данных. T^SO операционной системы ОС/ЕС и используются для разработки концептуальных схем баз данных специального назначения в ГВЦ МВД ГДР . Апробация работы. Московской городской конференции общества НТО "При-борпром. С.А. Вавилова " Современные проблемы разработки и реализации АСУТП " , май г. Головного центра по прикладным исследованиям Комбината обработки данных ГДР и в ГВЦ МВД ГДР / г. Берлин - гг. Диссертационная работа состоит из введения, четырех глав и заключения. В первой главе дана постановка задачи канонического структурирования и проведен анализ методов Грохла, Дёрин-гера, Рогге, Бири и Бернштейна, Феттера . Показано, что решение задачи автоматизированного определения концептуальной схемы баз данных больших размерностей данными методами не приводит к удовлетворительным результатам. Во второй главе дано определение графа концептуальной схемы базы данных. Она посвящена изучению свойств и разработке эффективных алгоритмов анализа и преобразования графа концептуальной схемы. В ней показано, что использование взвешенных графов позволяет разработать методы канонического структурирования гарантирующие единственность решения. Разработан алгоритм оптимальной реализации матрицы расстояний. В методе используется разработанный алгоритм оптимальной реализации матрицы расстояний для минимизации дуг графа концептуальной схемы. Четвертая глава посвящена вопросам реализации разработанного метода канонического структурирования. В ней изложены основные сведения о комплексе программ, реализующих данный метод. Рассмотрены действия администратора банка данных в процессе разработки концептуальной схемы при помощи данного метода. Работа выполнена на кафедре Прикладной математики МЭИ. Большую помощь в работе над диссертационной работой автору оказала научный руководитель к. Грачева Е. К. , сотрудники Головного центра по прикладным исследованиям Комбината Обработки данных и сотрудники ГВЦ МВД ГДР. Всем им автор приносит свою благодарность. В данной главе проводится анализ методов канонического структурирования данных с целью выяснения вопроса о возможности их автоматизации и применения для проектирования структуры баз данных больших размерностей. Лежащий в основе современных методов проектирования баз данных многоуровневой подход описания данных окончательно сложился в середине -х годов [-5/, , *5, ? На внешнем уровне изучаются объекты реального мира, имеющие некоторые свойства и взаимоотношения между ними. Информационные потребности конечных пользователей базы данных выражаются на внешнем уровне в виде приложений. На концептуальном уровне объекты реального мира и их взаимоотношения рассматриваются в терминах абстрактных моделей данных. Приложения конечных пользователей представляются в локальных схемах. Общее описание всех объектов реального мира и их взаимоотношение представляется в концептуальной схеме базы данных.