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

ВВЕДЕНИЕ. ?

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

§ I.I. Основные определения . &

§ 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. Формирование концептуальной схемы первой нормальной формы

§ 3.4. Построение графа концептуальной схемы

§ 3.5. Построение оптимальной реализации матрицы расстояний грас&а Q

§ З.б. Формирование концептуальной схемы Q, . 7-

§ 3.7. Области использования метода канонического структурирования и направления его усовершенствования. г*

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

Глава 1У. РЕАЛИЗАЦИЯ МЕТОДА КАНОНИЧЕСКОГО СТРУКТУРИРОВАНИЯ

§ 4.1. Комплекс программ лвзтя.

§ 4.2. Методические вопросы использования метода канонического структурирования

§ 4.3. Некоторые вопросы формирования схем хранения базы данных . fOS

Выводы по главе 1У.fOB

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

Практический опыт показывает, что задача определения структуры данных является одной из наиболее сложных и трудоемких задач, решаемых в процессе проектирования систем обработки данных. Вопросам определения структуры данных посвящено множество работ. Среди них можно выделить работы Кодца, Берн-штейна, Мартина, Хаббарда, Савинкова, Цаленко и других авторов.

Разработка реляционной модели данных Кодам явилась важным событием в процессе формирования теории проектирования баз данных. Можно считать, что эта теория к настоящему моменту сформировалась. Главным результатом математической теории проектирования баз данных необходимо считать разработку точных методов определения структур данных, обеспечивающих возможность реализации всех запросов пользователей базы данных. Таким образом, задача определения структуры данных с теоретической точки зрения решена. Однако показано также, что задача определения структуры данных точными методами обладает /vp -полнотой. Это означает, что точные методы определения структуры данных неприменимы в процессе проектирования реальных баз данных.

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

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

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

Научная новизна полученных результатов заключается в следующем :

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

- Разработаны алгоритмы анализа графа концептуальной схемы, позволяющие провести проверку принадлежности концептуальной схемы второй нормальной форме Кодца. Данные алгоритмы имеют вычислительную сложность не превышающую 0(n(n+mj) , где п -количество отношений концептуальной схемы, а - количество атрибутов; известные алгоритмы имеют вычислительную сложность Otfntmf) .

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

О(п), где >? - количество вершин графа, что на порядок меньше известных методов.

Практическая ценность работы состоит в следующем :

- Программно реализован автоматизированный метод канонического структурирования.

- Спроектированы концептуальные схемы баз данных информационных систем специального назначения в ГВЦ МВД ГДР с использованием разработанной программной системы.

Реализация результатов работы. Работа была выполнена в рамках работ по реализации приказа Совета Министров ГДР от 13.09. 1974 года о формировании большой базы данных в области коммунального управления ГДР. На основании полученных результатов разработан комплекс программ, реализующий разработанный метод определения концептуальных схем данных. Программы данного комплекса объединены в командном процессоре jO^S^ системы разделения времени 7"<$0 операционной системы ОС/ЕС и используются для разработки концептуальных схем баз данных специального назначения в ГВЦ МВД ГДР •

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались :

- на Московской городской конференции общества НТО "При-борпром." им. С.А. Вавилова 11 Современные проблемы разработки и реализации АСУТП " , май 1982 г. ;

- на семинарах кафедры Прикладной математики МЭИ ;

- на рабочих совещаниях Головного центра по прикладным исследованиям Комбината обработки данных ГДР и в ГВЦ МВД ГДР / г. Берлин 1978 - 1983 гг. / .

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

Выводы по главе 4

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

1. Изложены основные сведения о комплексе программ который реализует разработанный метод канонического структурирования.

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

3. Работоспособность разработанного метода продемонстрирована на изложенном примере.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

- по формы с оптимальным учетом количественных параметров приложений.

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

8. Приведены основные сведения о разработанном автором комплексе программ D&2T/1, - реализующем предложенный метод канонического структурирования, и разработаны методические указания проектирования концептуальных схем баз данных, основанные на комплексе программ ДвЗ^Я .

1. Ахо А.В. и др. Построение и анализ вычислительных алгоритмов М.: Мир, 1979. - 536 с.

2. Басакер Р. и Саати Т. Конечные графы и сети М.: Наука, 1974. - 366 с.

3. Берзтисс А.Т. Структуры данных. -М.: Статистика, 1974. 408 с.к Бойко В.В., Савинков В.М. Проектирование информационной базы автоматизированной системы на основе СУБД М.: Финансы и статистика, 1982. - 174 с.

4. Дэйт К. Введение в системы управления базами данных М.: Наука, 1980

5. Йордан Э. Структурное проектирование и конструирование программ М.: Мир, 1979.- 415 с.

6. Кнут Д. Искусство программирования для ЭВМ. т.1 М.: Мир, 1976. - 735 с.

7. Майника Э. Алгоритмы оптимизации на сетях и графах -М.: Мир, 1981 323 с.

8. Мартин Д. Организация без данных в вычислительных системах М.: Мир, 1980, 2 изд.доп. - 662 с.

9. Яссен Е. Теоретические проблемы развития информационных систем в сб.: Модели данных и системы баз данных - М.: Наука, 1979 - с.5-30.- из

10. Armstrong W. W. Dependency structures of data base relationships Proc.,1974 IFIP Congress , North Holland Amsterdam , 1974. - pp .530-583

11. Beeri C. and Bernstein P. A. Computational problems related to the design of normal form relation schemes -ACM Trans, on Database Systems, Vol 4, Nr. 1 , 1979. -pp.30-59

12. Beeri C. , Bernstein P. A. and Goodman N. A sophisticated introduction to database Normalisation theory -Proc. ACM Intl. Conf. on Very Large Data Bases , 1978. -pp.113-124

13. Bernstein P. A. Synthesizing third normal form from functional dependencies ACM Trans, on Database Systems, Vol 1, Nr. 4 , 1976.- pp.277-298

14. Biskup D. , Dayal U. and Bernstein P. A. Synthesizing in dependent database schemes ACM/SIGMOD International Symposium on Management of Data , 1979.- pp.196-210

15. Codd E. F. A relational model for large shared data banks Comm. ACM , Vol 13 , Nr. 6 , 1970.- pp.377-387

16. Codd E. F. Further normalization of the data baserelational model. In Data Base Systems ( R. Rustin, ed. ) Prentice Hall , Englewood Cliffs , New Dersey , 1972. -pp .33-64

17. De P . , Haseman W. D. and Kriebel С. H. Toward of a Network Database from Relational Descriptions Operating research , Vol 26, Nr. 5, 1978.- pp .805-823

18. Doringer H. Eine Methodik zur Strukturierung von Daten-banken Angewandte Informatik , Nr. 3, 1978.- S.93-103

19. Goldman A. 0. Realizing the distance matrix of a graph-D. Res. Nat. Bur. Standards B70 (1966) pp.153-354

20. Grochla E. u.a. Gestaltungskriterien fur den Aufbau von Datenbanken , Westdeutscheг Verlag Opladen , 1973.

21. Flubacher A. IMS Erfahrungen in der offentlichen Ver-waltung IBM-Nach richten (25) , 1975 , Heft 224 , S.16-20, Heft 225 , S .103-110

22. Hakimi S. L. and Yau S. S. Distance matrix of a graph and its realizability Quart. Appl. Math. 12 (1965) -pp .305-317

23. Horst von der Heide Vom Dateiverwaltungssystem UD3 zum Datenbanksystem IMS IBM-Nachrichten (25) , 1975 , Heft 227 , S.252-256

24. Т. C. Optimum communication spanning trees SIAM D .

25. Comput. , Vol 3, Nr. 3, 1974. pp.108-195 57. Hsu H. T. An Algorithm for Finding a Minimal Equvalent Graph of a Digraph - 3. ACM , Vol 22, Nr. 1, 1975.-pp .11-16

26. Mitteilung SPK/Rechcnzentrum , Abteilung Projektierung una' Programmierung Makropaket COLA zur Unterstutzung der st rukturierten Programmierung in e'er Assemblersprache , Berlin , 15.06.1981

27. UDB Antvendungshandbuch , Aufbau und Fortfuhrung von Dateien im Einvvohnerwesen , IBM-Form 80730-0 g # Vctter M. Data Base Design by applied Data Synthesis